Необычное использование аппаратного умножителя Опции

[Rst7]

Вот, сижу, мастерю один проектик. Понадобилось сделать Хаффмана. В принципе, ничего сложного, однако работа с битовыми полями - это всегда узкое место процов с отсутствием комманд для обработки данных такого класса. Например, при упаковке по Хаффману необходима процедура, которая запишет в выходной поток n бит значения - вызывается примерно так:

Код

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;
}

Компилятор - 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

Конечно, если есть возможность, выжимку кода необходимо вставлять прямо в цикл генерации символов, чтобы меньше оверхеда было на загрузку/выгрузку. В этом случае добавление битового поля будет занимать 10 или 12 тактов, в зависимости от того, происходит переход через границу байта или не происходит.

Опять же, если есть возможность, надо хранить размеры символов в виде масок, а не в обычном виде - это уберет оверхед на функцию write_n_bits (7 тактов).

Такая функция, кстати, будет полезна тем, кто пишет вывод пропорциональных символов на графический дисплей - вывод можно здорово ускорить.

Вообще, подобный подход можно использовать там, где необходимо организовывать сдвиги на произвольное количество бит.

[Rst7]

Ну, продолжим наши игры. На этот раз под руки попало деление. 16 бит беззнаковое на 16 бит беззнаковое. Обычное деление в столбик - почти 200 тактов (зависит от операндов).

Если не жмет место во флеше и необходимо ускорить деление 16 на 16, предлагаю такую процедуру (код великоват, спрятал под спойлером)

CODE

#define ZL R30
#define ZH R31

PUBLIC fast_divu16

RSEG CODE:CODE:NOROOT(1)

// 92 UINT16 fast_divu16(UINT16 a, UINT16
fast_divu16:
// 93 {
LDI ZH,shift_mask_and_log>>8
CLR R3
// 101 if ((d=b>>8)!=0)
TST R19
BREQ byte_div
large_div:
// 103 UINT8 __flash *p=shift_mask_and_log+d;
// 104 s=*p;
MOV ZL,R19
LPM R22,Z ;s - R22
INC ZH
// 105 p=shift_mask_and_log+((b*s)>>8)+0x100;
MUL R19,R22
MOV ZL,R0
MUL R18,R22
ADD ZL,R1
// 106 c=*p<<8;
LPM R23,Z
// 107 p+=0x100;
INC ZH
// 108 c|=*p;
LPM ZH,Z
// 109 c=(UINT32)((UINT32)c*a)>>16;
MUL R23,R17
MOVW R21:R20,R1:R0
MUL ZH,R16
MOV R2,R1
MUL R23,R16
ADD R2,R0
ADC R20,R1
ADC R21,R3
MUL ZH,R17
ADD R2,R0
ADC R20,R1
ADC R21,R3
// 110 c=(UINT32)((UINT32)c*s)>>8;
MUL R21,R22
MOV R21,R1
MOV R2,R0
MUL R20,R22
MOV R20,R2
OR R20,R1
// 111 a-=b
SUB R16,R18
SBC R17,R19
; BRCS zero_result
//b - R19:R18, c - R21:R20, a - R17:R16, s - R22, e - ZH:ZL
// 112 e=b*c-a;
MUL R19,R20
MOV ZH,R0
MUL R18,R21
ADD ZH,R0
MUL R18,R20
MOV ZL,R0
ADD ZH,R1
SUB ZL,R16
SBC ZH,R17
// if (e>b) c--;
CP R18,ZL ;b-e, carry=1 if b<e
CPC R19,ZH
SBC R20,R3
SBC R21,R3
// 122 return c;
MOVW R17:R16,R21:R20
RET
;zero_result:
; LDI R16,0
; LDI R17,0
; RET
result_a_or_fault:
BREQ result_a
SER R16
SER R17
result_a:
RET
// 126 if ((d=>1)
byte_div:
CPI R18, 2
BRCS result_a_or_fault
MOV ZL,R18
// 129 s=*p;
LPM R22,Z
// 130 p+=0x100;
INC ZH
// 131 c=*p<<8;
LPM R19,Z
// 132 p+=0x100;
INC ZH
// 133 c|=*p;
LPM R18,Z
// 134 c=(UINT32)((UINT32)c*a)>>16;
MUL R19,R17
MOVW R21:R20,R1:R0
MUL R18,R16
MOV R2,R1
MUL R19,R16
ADD R2,R0
ADC R20,R1
ADC R21,R3
MUL R18,R17
ADD R2,R0
ADC R20,R1
ADC R21,R3
// 135 a-=b;
SUB R16,ZL
SBCI R17,0
; BRCS zero_result
// 136 e=d*c-a;
MUL R21,ZL
MOV R19,R0
MUL R20,ZL
MOV R18,R0
ADD R19,R1
SUB R18,R16
SBC R19,R17
// if (e>b) c--;
CP ZL,R18 ;b-e, carry=1 if b<e
CPC R3,R19
SBC R20,R3
SBC R21,R3
// 122 return c;
MOVW R17:R16,R21:R20
RET

ASEGN NEAR_F:CODE:ROOT,0FD00H
//Таблица масок и обратных величин. Должна быть с круглого адреса
shift_mask_and_log:
DB 255, 128, 64, 64, 32, 32, 32, 32, 16, 16, 16, 16, 16, 16, 16, 16, 8
DB 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 4, 4, 4, 4, 4, 4, 4, 4
DB 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
DB 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
DB 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
DB 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 128, 85, 64, 51, 42, 36, 32, 28, 25
DB 23, 21, 19, 18, 17, 16, 15, 14, 13, 12, 12, 11, 11, 10, 10, 9, 9, 9
DB 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5
DB 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
DB 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
DB 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
DB 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
DB 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1
DB 86, 1, 52, 171, 147, 1, 114, 154, 70, 86, 178, 74, 18, 1, 16, 57
DB 122, 205, 49, 163, 34, 171, 62, 217, 124, 37, 212, 137, 67, 1, 194
DB 136, 81, 29, 236, 189, 145, 103, 63, 25, 245, 210, 177, 145, 115, 86
DB 58, 31, 6, 237, 213, 190, 168, 147, 126, 106, 87, 69, 51, 34, 17, 1
DB 241, 225, 211, 196, 182, 169, 156, 143, 130, 118, 106, 95, 84, 73
DB 62, 52, 42, 32, 22, 13, 4, 251, 242, 233, 225, 217, 209, 201, 193
DB 186, 178, 171, 164, 157, 150, 144, 137, 131, 125, 119, 113, 107, 101
DB 95, 90, 84, 79, 74, 68, 63, 58, 53, 49, 44, 39, 35, 30, 26, 21, 17
DB 13, 9, 5, 1, 253, 249, 245, 241, 237, 234, 230, 226, 223, 219, 216
DB 213, 209, 206, 203, 200, 196, 193, 190, 187, 184, 181, 179, 176, 173
DB 170, 167, 165, 162, 159, 157, 154, 152, 149, 147, 144, 142, 139, 137
DB 135, 132, 130, 128, 126, 123, 121, 119, 117, 115, 113, 111, 109, 107
DB 105, 103, 101, 99, 97, 95, 93, 91, 89, 88, 86, 84, 82, 81, 79, 77
DB 75, 74, 72, 71, 69, 67, 66, 64, 63, 61, 60, 58, 57, 55, 54, 52, 51
DB 49, 48, 47, 45, 44, 42, 41, 40, 38, 37, 36, 34, 33, 32, 31, 29, 28
DB 27, 26, 25, 23, 22, 21, 20, 19, 18, 16, 15, 14, 13, 12, 11, 10, 9, 8
DB 7, 6, 5, 4, 3, 2


END

Собственно деление представляет из себя выборку из таблицы значения, обратного делителю, и умножение на него делимого с последующей коррекцией результата. При делителе меньше 256 выборка производится непостредственно (таблица на 256 значений), а вот при большем делителе делается хитрость:

1. Определяется двоичный порядок делителя (в виде маски для последующего сдвига при помощи mul)
2. Делитель быстро сдвигается (нормализуется) в диапазон 0x80...0xFF.
3. Эта мантисса служит индексом в таблице обратных значений.
4. Обратное значение опять сдвигается при помощи умножений на ту же маску. Т.е. (1/(b*n))*a*n=a/b;
5. Умножение на делимое и коррекция, как и в случае делитель<256.

Вот такие пироги в худшем случае занимают 69 тактов и 176+768 байт флеша на собственно функцию и таблички.

Единственно что, лень доводить до ума, при делимом больше чем ~40000 и делителе в районе 256...512 бывает ошибается на 1 - возвращает результат на 1 больше чем надо. Если кому сильно необходимо, могут допилить (судя по всему, необходима отдельная ветка для делителей 0x100...0x1FF c отдельной табличкой обратных значений).