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

[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]

Я собственно собираюсь переписать всё на асм.

Гм. Я разве не на асме код выложил? Для тех, кто в танке - была написана рыба на Си, отлажена в MSVS, затем собрана IAR'ом, и листинг допилен вручную.

Щас продолжу, случайно не ту кнопку нажал

Я не пойму, что Вас смущает?

a - делимое;
b - делитель;
с - результат, сначала приближение, потом он корректируется;
e - ошибка, равная b*c-a;

Если внести a-=b в выражение ошибки, то это эквивалентно e=b*c-( a - b )=b*c-a+b=b*(c+1)-a;

Если ошибка превышает делитель, то корректируем результат (уменьшением).