Код
write_bits(huff->codes[val],huff->bits[val])
где первый параметр - код, а второй - собственно его размер в битах. Вот обычно эта функция - write_bits и несет основные затраты по времени выполнения. Почему так происходит - понятно, надо сдвигать входные биты в нужное положение, вычислять новое положение в буфере и т.д.
Посему, сразу кодить не стал, сел - подумал...
И вот что надумал...
У нас есть аппаратный умножитель, который за 2 такта даст нам сдвинутый сразу в двух направлениях байт - и влево, и вправо. Конечно, в качестве множителя надо использовать маску - 0x01,0x02,...,0x80 и в результате, после выполнения комманды MUL в R0 будем иметь байт данных, сдвинутый влево, в R1 - сдвинутый вправо. Это уже отлично, одной коммандой мы готовим данные для OR с текущим байтом и для занесения следующих данных в накопитель. Однако, соответствующую текущему моменту маску еще надо получить. Она зависит как от текущей битовой позиции в выходном буфере, так и от размера битовых данных. Опять пришлось поразмышлять. Размышления натолкнули на идею хранить битовую позицию в буфере тоже в виде маски:
Код
0x80(биты 7...0 свободны),0x40(бит 7 с данными, биты 6...0 свободны),....,0x01(биты 7...1 с данными, бит 0 свободен)
Если размер символа в битах тоже задать в виде маски, то происходит чудо
- умножение (аппаратное, конечно) размера на битовую позицию даст новую позицию и она же является необходимым (точнее, в 2 раза меньше) множителем для сдвига символа. Причем, в зависимости, от того, какой байт результата, старший или младший, не равен 0 - то это и есть выбор двух альтернатив - новый символ требует перехода через границу байта или не требует.Осталась маленькая тонкость, что новая позиция как множитель данных в 2 раза меньше (т.е. сдвинута вправо). Можно конечно сдвинуть при помощи LSL, но лучше использовать тот факт, что FMUL - есть Rs*Rd<<1, это поможет в оптимизации.
Букаф много (могут ниасилить), посему код:
Код
//Кластеризация вручную, при необходимости изготавливается нормальная структура
struct
{
char bitstream_byte;
char bitstream_bit;
char *bitstream;
};
//Инициализация битового потока
//p - указатель на первый байт выходного буфера
void init_bitstream(char *p)
{
bitstream_byte=0;
bitstream_bit=0x80;
bitstream=p;
}
//Финализация потока - слив неслитого
//bp - указатель на первый байт выходного буфера (для расчета размера)
//на выходе - размер потока в байтах
unsigned int finish_bitstream(char *bp)
{
char *p=bitstream;
if (bitstream_bit!=0x80) *p++=bitstream_byte;
return p-bp;
}
void write_bits_by_mask(char sym, char msb);
//Запись n бит из символа sym, необходимо, чтобы неиспользуемые биты равнялись 0
void write_n_bits(char sym, char n)
{
//Генерация обратной маски
static __flash const char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
write_bits_by_mask(sym,mask[n-1]);
}
//Записать в битовый поток биты из sym
//Биты записываются от 0 до бита, определенного установленным битом в msb в обратном порядке
//msb=0x80 sym=0000000a
//msb=0x40 sym=000000ab
//msb=0x20 sym=00000abc
//msb=0x10 sym=0000abcd
//msb=0x08 sym=000abcde
//msb=0x04 sym=00abcdef
//msb=0x02 sym=0abcdefg
//msb=0x01 sym=abcdefgh
//Запись идет от 7 к 0, например запись символов 000abcde, 0000xyzt будет лежать в байтах как
//[abcdexyz][t.......]
//Если есть возможность хранить msb, лучше применять эту функцию, меньше накладных расходов
void write_bits_by_mask(char sym, char msb)
{
char b=bitstream_byte;
char m=bitstream_bit;
char *p=bitstream;
//--> Если есть возможнось, эта часть инлайнится во внешний цикл
unsigned short i;
i=__multiply_unsigned(m,msb); //ih - множитель для sym, чтобы согласовать положение
if (i>>8)
{
//Требуется сдвиг влево
m=i>>8;
i=__fractional_multiply_unsigned(sym,m);
b|=i;
}
else
{
//Требуется сдвиг вправо
m=i;
i=__fractional_multiply_unsigned(sym,m);
b|=i>>8;
*p++=b;
b=i;
}
//<-- Конец части для инлайна
bitstream=p;
bitstream_byte=b;
bitstream_bit=m;
}
struct
{
char bitstream_byte;
char bitstream_bit;
char *bitstream;
};
//Инициализация битового потока
//p - указатель на первый байт выходного буфера
void init_bitstream(char *p)
{
bitstream_byte=0;
bitstream_bit=0x80;
bitstream=p;
}
//Финализация потока - слив неслитого
//bp - указатель на первый байт выходного буфера (для расчета размера)
//на выходе - размер потока в байтах
unsigned int finish_bitstream(char *bp)
{
char *p=bitstream;
if (bitstream_bit!=0x80) *p++=bitstream_byte;
return p-bp;
}
void write_bits_by_mask(char sym, char msb);
//Запись n бит из символа sym, необходимо, чтобы неиспользуемые биты равнялись 0
void write_n_bits(char sym, char n)
{
//Генерация обратной маски
static __flash const char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
write_bits_by_mask(sym,mask[n-1]);
}
//Записать в битовый поток биты из sym
//Биты записываются от 0 до бита, определенного установленным битом в msb в обратном порядке
//msb=0x80 sym=0000000a
//msb=0x40 sym=000000ab
//msb=0x20 sym=00000abc
//msb=0x10 sym=0000abcd
//msb=0x08 sym=000abcde
//msb=0x04 sym=00abcdef
//msb=0x02 sym=0abcdefg
//msb=0x01 sym=abcdefgh
//Запись идет от 7 к 0, например запись символов 000abcde, 0000xyzt будет лежать в байтах как
//[abcdexyz][t.......]
//Если есть возможность хранить msb, лучше применять эту функцию, меньше накладных расходов
void write_bits_by_mask(char sym, char msb)
{
char b=bitstream_byte;
char m=bitstream_bit;
char *p=bitstream;
//--> Если есть возможнось, эта часть инлайнится во внешний цикл
unsigned short i;
i=__multiply_unsigned(m,msb); //ih - множитель для sym, чтобы согласовать положение
if (i>>8)
{
//Требуется сдвиг влево
m=i>>8;
i=__fractional_multiply_unsigned(sym,m);
b|=i;
}
else
{
//Требуется сдвиг вправо
m=i;
i=__fractional_multiply_unsigned(sym,m);
b|=i>>8;
*p++=b;
b=i;
}
//<-- Конец части для инлайна
bitstream=p;
bitstream_byte=b;
bitstream_bit=m;
}
Компилятор - IAR 5.10
Ну и листинг, который особо радует глаз (приведу только внутренности функции write_bits_by_mask)
Код
54 void write_bits_by_mask(char sym, char msb)
\ write_bits_by_mask:
55 {
\ 00000000 2F5B MOV R21, R27
\ 00000002 2F6A MOV R22, R26
\ 00000004 2F20 MOV R18, R16
56 char b=bitstream_byte;
\ 00000006 .... LDI R30, LOW(_A_bitstream_byte)
\ 00000008 .... LDI R31, (_A_bitstream_byte) >> 8
\ 0000000A 8130 LD R19, Z
57 char m=bitstream_bit;
58 char *p=bitstream;
\ 0000000C 81A2 LDD R26, Z+2
\ 0000000E 81B3 LDD R27, Z+3
\ 00000010 8101 LDD R16, Z+1
59 //--> Если есть возможнось, эта часть инлайнится во внешний цикл
60 unsigned short i;
61 i=__multiply_unsigned(m,msb); //ih - множитель для sym, чтобы согласовать положение
\ 00000012 9F01 MUL R16, R17
62 if (i>>8)
\ 00000014 2011 TST R1
\ 00000016 F021 BREQ ??write_bits_by_mask_0
63 {
64 //Требуется сдвиг влево
65 m=i>>8;
\ 00000018 2D41 MOV R20, R1
66 i=__fractional_multiply_unsigned(sym,m);
67 b|=i;
\ 0000001A 032C FMUL R18, R20
\ 0000001C 2930 OR R19, R0
\ 0000001E C005 RJMP ??write_bits_by_mask_1
68 }
69 else
70 {
71 //Требуется сдвиг вправо
72 m=i;
\ ??write_bits_by_mask_0:
\ 00000020 2D40 MOV R20, R0
73 i=__fractional_multiply_unsigned(sym,m);
\ 00000022 032C FMUL R18, R20
74 b|=i>>8;
75 *p++=b;
\ 00000024 2931 OR R19, R1
\ 00000026 933D ST X+, R19
76 b=i;
\ 00000028 2D30 MOV R19, R0
77 }
78 //<-- Конец части для инлайна
79 bitstream=p;
\ ??write_bits_by_mask_1:
\ 0000002A 83A2 STD Z+2, R26
\ 0000002C 83B3 STD Z+3, R27
80 bitstream_byte=b;
\ 0000002E 8330 ST Z, R19
81 bitstream_bit=m;
\ 00000030 8341 STD Z+1, R20
82 }
\ 00000032 2FA6 MOV R26, R22
\ 00000034 2FB5 MOV R27, R21
\ 00000036 9508 RET
\ write_bits_by_mask:
55 {
\ 00000000 2F5B MOV R21, R27
\ 00000002 2F6A MOV R22, R26
\ 00000004 2F20 MOV R18, R16
56 char b=bitstream_byte;
\ 00000006 .... LDI R30, LOW(_A_bitstream_byte)
\ 00000008 .... LDI R31, (_A_bitstream_byte) >> 8
\ 0000000A 8130 LD R19, Z
57 char m=bitstream_bit;
58 char *p=bitstream;
\ 0000000C 81A2 LDD R26, Z+2
\ 0000000E 81B3 LDD R27, Z+3
\ 00000010 8101 LDD R16, Z+1
59 //--> Если есть возможнось, эта часть инлайнится во внешний цикл
60 unsigned short i;
61 i=__multiply_unsigned(m,msb); //ih - множитель для sym, чтобы согласовать положение
\ 00000012 9F01 MUL R16, R17
62 if (i>>8)
\ 00000014 2011 TST R1
\ 00000016 F021 BREQ ??write_bits_by_mask_0
63 {
64 //Требуется сдвиг влево
65 m=i>>8;
\ 00000018 2D41 MOV R20, R1
66 i=__fractional_multiply_unsigned(sym,m);
67 b|=i;
\ 0000001A 032C FMUL R18, R20
\ 0000001C 2930 OR R19, R0
\ 0000001E C005 RJMP ??write_bits_by_mask_1
68 }
69 else
70 {
71 //Требуется сдвиг вправо
72 m=i;
\ ??write_bits_by_mask_0:
\ 00000020 2D40 MOV R20, R0
73 i=__fractional_multiply_unsigned(sym,m);
\ 00000022 032C FMUL R18, R20
74 b|=i>>8;
75 *p++=b;
\ 00000024 2931 OR R19, R1
\ 00000026 933D ST X+, R19
76 b=i;
\ 00000028 2D30 MOV R19, R0
77 }
78 //<-- Конец части для инлайна
79 bitstream=p;
\ ??write_bits_by_mask_1:
\ 0000002A 83A2 STD Z+2, R26
\ 0000002C 83B3 STD Z+3, R27
80 bitstream_byte=b;
\ 0000002E 8330 ST Z, R19
81 bitstream_bit=m;
\ 00000030 8341 STD Z+1, R20
82 }
\ 00000032 2FA6 MOV R26, R22
\ 00000034 2FB5 MOV R27, R21
\ 00000036 9508 RET
Конечно, если есть возможность, выжимку кода необходимо вставлять прямо в цикл генерации символов, чтобы меньше оверхеда было на загрузку/выгрузку. В этом случае добавление битового поля будет занимать 10 или 12 тактов, в зависимости от того, происходит переход через границу байта или не происходит.
Опять же, если есть возможность, надо хранить размеры символов в виде масок, а не в обычном виде - это уберет оверхед на функцию write_n_bits (7 тактов).
Такая функция, кстати, будет полезна тем, кто пишет вывод пропорциональных символов на графический дисплей - вывод можно здорово ускорить.
Вообще, подобный подход можно использовать там, где необходимо организовывать сдвиги на произвольное количество бит.
