| |
 Необычное использование аппаратного умножителя |
|
|
|
|
  May 7 2008, 17:14
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Вот, сижу, мастерю один проектик. Понадобилось сделать Хаффмана. В принципе, ничего сложного, однако работа с битовыми полями - это всегда узкое место процов с отсутствием комманд для обработки данных такого класса. Например, при упаковке по Хаффману необходима процедура, которая запишет в выходной поток 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 тактов). Такая функция, кстати, будет полезна тем, кто пишет вывод пропорциональных символов на графический дисплей - вывод можно здорово ускорить. Вообще, подобный подход можно использовать там, где необходимо организовывать сдвиги на произвольное количество бит.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
May 7 2008, 18:22
|
Гуру
Группа: Свой
Сообщений: 2 712
Регистрация: 28-11-05
Из: Беларусь, Витебск, Строителей 18-4-220
Пользователь №: 11 521
|
Цитата(Rst7 @ May 7 2008, 21:14)  Вообще, подобный подход можно использовать там, где необходимо организовывать сдвиги на произвольное количество бит. Интересно! Я тоже в одном месте использовал нестандартно FMUL. Правда если есть возможность организовывать групповые сдвиги (например маска и значение), то условиями меньше места займёт. По такому принципу. Код maska =0x3;
if((X & 2)==0)
{
maska = 0x30;
Color <<= 4;
}
if((X & 1)==0)
{
maska <<=2;
Color <<=2;
}
|
|
|
|
|
|
|
|
May 7 2008, 18:50
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Цитата Правда если есть возможность организовывать групповые сдвиги (например маска и значение), то условиями меньше места займёт. В этом случае конечно да. Ну а как Вам такой способ? Код // 110 char maska =0x3;
LDI R18, 3
// 111 if (X&1) maska=0x0C;
SBRC R16,0
LDI R18, 12
// 112 if (X&2) maska=__swap_nibbles(maska);
SBRC R16,1
SWAP R18
// 114 c=(Color*0x55)&maska;
LDI R16, 85
MUL R17, R16
AND R0, R18 На входе R16 - X, R17 - Color, на выходе R0 - цвет, R18 - маска. К сожалению, тут компилятор красоту с SBRC ниасилил, это руками писано.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
May 8 2008, 07:24
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Цитата(galjoen @ May 7 2008, 22:49) А вот мне только-что мысль пришла - ещё не проверял. Так-что если глупость написал - не пинайте.
Мне кажется, что с помощью MUL можно узнать чётное или нечётное кол-во единиц в байте. Если байт, кол-во единичных битов которого на чётность проверяется, на FF умножить, то в b7 результа будет ТОЛЬКО от чётности зависеть. Я прав? Теоретически вроде так получается. К сожалению не работает, но ход мысли понятен, ведь в 7ом бите получается сумма всех бит. Правда, вот переносы из младших разрядов все портят. Могу предложить такой вариант - обработать по половине бит с принятием мер против распространения переноса (вроде тоже самый быстрый получается) Код ;Вход R16 - байт для подсчета
;abcdefgh
;
MOV R18,R16
LDI R17,0x55
AND R16,R17 ;0b0d0f0h
FMUL R16,R17
;теперь в R0 суммы
;b0d0f0h0
;d0f0h000
;f0h00000
;h0000000
;как видим, перенос в седьмой бит отсутствует в любом случае
MOV R16,R0 ;Сохраняем результат по половине битов и повторяем для второй
LSR R18 ;0abcdefg
AND R18,R17 ;0a0c0e0g
FMUL R18,R17
;теперь в R0 суммы
;a0c0e0g0
;c0e0g000
;e0g00000
;g0000000
EOR R16,R0 ;Выход - бит 7 R16 - бит четности
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
May 8 2008, 07:54
|
Знающий
Группа: Свой
Сообщений: 550
Регистрация: 16-06-04
Из: Казань
Пользователь №: 32
|
сдвигами четность все равно шустрее выйдет: Код MOV tmp,@0
SWAP tmp
EOR tmp,@0
MOV @0,tmp
LSR @0
EOR @0,tmp
SBRS @0,2
SUBI @0,1; мл.бит регистра @0 равен 1, если в байте четное число единиц UPD: убрал выдвигание мл.бита в C для немедленного ветвления
--------------------
Главная линия этого опуса ясна мне насквозь!
|
|
|
|
|
|
|
|
May 29 2008, 19:41
|
;
Группа: Участник
Сообщений: 5 646
Регистрация: 1-08-07
Пользователь №: 29 509
|
Америки не открою, и особой экзотики в использовании умножения не будет, но... Самое быстрое деление 16-битного делимого на 8-битный делитель без остатка. Методом поразрядного приближения. Код div16x8:
// yL = (zL:zH)/yH
// registers used yL,yH,zL,zH,r0,r1 (6)
ldi yL,0x80
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv00
clr yL
dv00:
ori yL,0x40
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv01
andi yL,0xbf
dv01:
ori yL,0x20
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv02
andi yL,0xdf
dv02:
ori yL,0x10
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv03
andi yL,0xef
dv03:
ori yL,0x08
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv04
andi yL,0xf7
dv04:
ori yL,0x04
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv05
andi yL,0xfb
dv05:
ori yL,0x02
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv06
andi yL,0xfd
dv06:
ori yL,0x01
mul yL,yH
cp zL,r0
cpc zH,r1
brsh dv07
andi yL,0xfe
dv07:
ret // result = yL
// total clocks = 56 + call/ret Может, кому пригодится 
|
|
|
|
|
|
|
|
May 31 2008, 18:57
|
;
Группа: Участник
Сообщений: 5 646
Регистрация: 1-08-07
Пользователь №: 29 509
|
Цитата(ae_ @ May 31 2008, 14:55) Как быть, когда результат (zL:zH)/yH > 255? Вычесть из делимого и повторить деление остатка. Код mul yL,yH
sub zL,r0
sbc zH,r1
brcc pc+2
ret
push yL
;repeat div
pop yh
add yL,yH
...etc Ну, в данном случае такое не применимо. А применимо оно в операциях вида N= M*256 / K, где M и K примерно равны. И там, где при этом надо очень быстро все считать.
|
|
|
|
|
|
|
|
Dec 13 2008, 21:05
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Цитата(vet @ May 8 2008, 09:54) сдвигами четность все равно шустрее выйдет: Код MOV tmp,@0
SWAP tmp
EOR tmp,@0
MOV @0,tmp
LSR @0
EOR @0,tmp
SBRS @0,2
SUBI @0,1; мл.бит регистра @0 равен 1, если в байте четное число единиц UPD: убрал выдвигание мл.бита в C для немедленного ветвления Случайно пришла в голову мысль (не подумайте, что я тут полгода моск себе парил ), что шестой бит выражения __multiply_unsigned((v^(v>>1))&0x55,0x55) будет соответствовать четности переменной v Код ;R16 - вход
LDI R17, 85
MOV R18, R16
LSR R18
EOR R16, R18
ANDI R16, 0x55
MUL R16, R17
;6й бит R0 - четность 12 байт, 7 тактов
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Dec 14 2008, 19:11
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Rst7 @ Dec 14 2008, 00:05) Случайно пришла в голову мысль что шестой бит выражения __multiply_unsigned((v^(v>>1))&0x55,0x55) будет соответствовать четности переменной v Код ;6й бит R0 - четность ИМХО, очень красиво...  но я бы умножал на 0xAA для дальнейшего сдвига в С, но это так в качестве дальнейшего улучшения...
|
|
|
|
|
|
|
|
Dec 14 2008, 19:57
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Цитата(singlskv @ Dec 14 2008, 21:11) ИМХО, очень красиво... но я бы умножал на 0xAA для дальнейшего сдвига в С, но это так в качестве дальнейшего улучшения... Да вообщем пофиг, что в перенос двигать, что bst делать, что sbrs/sbrc. Кстати, для ARM'а весьма красиво смотрится выражение типа if (((v^(v<<1))&0xAA)*0x55)&0x80) - конечно, в arm-режиме, в тумбе - так себе.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Dec 14 2008, 20:08
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Rst7 @ Dec 14 2008, 22:57) Да вообщем пофиг, что в перенос двигать, что bst делать, что sbrs/sbrc. я в том смысле что есть выбор, толи в перенос толи sbrs/sbrc. Цитата Кстати, для ARM'а весьма красиво смотрится выражение типа if (((v^(v<<1))&0xAA)*0x55)&0x80) - конечно, в arm-режиме, в тумбе - так себе. А v -8ми битный ? Аа... Вы о том как это оттранслирует компилятор ?
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
