| |
 Быстрое вычисление CRC-8, Потенциальные возможности не табличных методов |
|
|
|
|
 Sep 1 2006, 12:32
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Недавно поднимался вопрос об оптимизации сишного кода, в частности был представлен такой код (немного отрихтовал для приличия) Цитата(µµC @ Aug 25 2006, 14:26)  Приятный алгоритм, возьму на вооружение. IAR - 515 циклов. Код U8 crc8_3(U8 *buff, U8 num)
{
U8 i, crc=0;
do
{
crc^=*buff++;
i=8;
do
{
if(crc&0x01)
{
crc>>=1;
crc^=0x8C;
}
else crc>>=1;
}
} while(--i);
} while(--num);
return crc;
} Для семи байтов ИАР-код выполняется за 525 циклов, т.е. вгрубе 75 циклов на байт. У меня весь ASM-код (не табличный) для 7 байт выполняется за 80 циклов. Может я чего не понимаю, или полиномы неправильные?
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
 |
Ответов
|
|
Sep 1 2006, 15:17
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Цитата(aaarrr @ Sep 1 2006, 13:08) Цитата(=GM= @ Sep 1 2006, 16:32)
У меня весь ASM-код (не табличный) для 7 байт выполняется за 80 циклов. Может я чего не понимаю, или полиномы неправильные?
Похоже, что что-то у Вас не так - одних сдвигов получается на 56 тактов... Хорошо, давайте начнем с расчета ЦКС8. Вот такой код для расчета ЦКС8 одного байта, только на ассемблере, у меня занимает 16/32 цикла для двух вариантов. Код uchar crc8 (uchar crc, uchar byte)
{
byte^=crc;
crc=0;
if(byte&0x01) crc =0x5E;
if(byte&0x02) crc^=0xBC;
if(byte&0x04) crc^=0x61;
if(byte&0x08) crc^=0xC2;
if(byte&0x10) crc^=0x9D;
if(byte&0x20) crc^=0x23;
if(byte&0x40) crc^=0x46;
if(byte&0x80) crc^=0x8C;
return crc;
} Проверьте, правильно считает(:-)? Ещё было бы любопытно, если бы кто-нибудь представил ассемблерный листинг для ИАР-компилера. У меня он есть, но не установлен, заглушка куда-то делась(:-). Интересно, насколько ИАР оптимизирует код.
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
|
Sep 1 2006, 15:21
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(=GM= @ Sep 1 2006, 19:17) Цитата(aaarrr @ Sep 1 2006, 13:08) Цитата(=GM= @ Sep 1 2006, 16:32)
У меня весь ASM-код (не табличный) для 7 байт выполняется за 80 циклов. Может я чего не понимаю, или полиномы неправильные?
Похоже, что что-то у Вас не так - одних сдвигов получается на 56 тактов... Хорошо, давайте начнем с расчета ЦКС8. Вот такой код для расчета ЦКС8 одного байта, только на ассемблере, у меня занимает 16/32 цикла для двух вариантов. Код uchar crc8 (uchar crc, uchar byte)
{
byte^=crc;
crc=0;
if(byte&0x01) crc =0x5E;
if(byte&0x02) crc^=0xBC;
if(byte&0x04) crc^=0x61;
if(byte&0x08) crc^=0xC2;
if(byte&0x10) crc^=0x9D;
if(byte&0x20) crc^=0x23;
if(byte&0x40) crc^=0x46;
if(byte&0x80) crc^=0x8C;
return crc;
} Проверьте, правильно считает(:-)? Ещё было бы любопытно, если бы кто-нибудь представил ассемблерный листинг для ИАР-компилера. У меня он есть, но не установлен, заглушка куда-то делась(:-). Интересно, насколько ИАР оптимизирует код. Перечитайте еще раз ту ветку, такой вариант там был  Это ПолуТабличный способ.
|
|
|
|
|
|
|
|
Sep 1 2006, 16:33
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Цитата(singlskv @ Sep 1 2006, 14:21) Перечитайте еще раз ту ветку, такой вариант там был Это ПолуТабличный способ. Прошу пардону, не заметил. Хоть и не претендую на первооткрывателя(:-), но горжусь, что сам до этого додумался. Даже потом нашел в сети. Но это только первый шаг в вычислении срс, а вот второго шага почему-то никто не сделал(:-)! Значит, я первый буду! Что такое полутабличный способ, я не совсем понимаю. Это ваше определение? Так что, никто не поможет с листингом компилированного варианта?
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
|
Sep 1 2006, 20:37
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(=GM= @ Sep 1 2006, 20:33) Но это только первый шаг в вычислении срс, а вот второго шага почему-то никто не сделал(:-)! Значит, я первый буду! Ну например, вторым шагом может быть, запоминание всех этих констант 0x5E,0xBC,0x61,0xC2,0x9D,0x23,0x46,0x8C в регистрах, типа чтобы для каждого байта их не грузить. Ну или еще что-то в том же духе. Опубликуйте код на ASM, и тогда обсудим.
|
|
|
|
|
|
|
|
Sep 3 2006, 08:55
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Цитата(singlskv @ Sep 1 2006, 19:37) Ну например, вторым шагом может быть, запоминание всех этих
констант 0x5E,0xBC,0x61,0xC2,0x9D,0x23,0x46,0x8C
в регистрах, типа чтобы для каждого байта их не грузить.
Ну или еще что-то в том же духе.
Опубликуйте код на ASM, и тогда обсудим. Ну вот, отдаю на суд общественности. Код z – указатель на входной массив
bytcnt – счетчик байт минус 1
byte – рабочий регистр
temp – рабочий регистр
calcrc – рассчитанная КЦК
crc8:
ld byte,z+
ldi bytcnt,8-1;счетчик байт минус 1
orbit:
ld temp,x+
eor byte,temp
dec bitcnt
brne orbit
clr calcrc
ldi temp,0x5E
sbrc byte,0
eor calcrc,temp
ldi temp,0xBC
sbrc byte,0
eor calcrc,temp
ldi temp,0x61
sbrc byte,0
eor calcrc,temp
ldi temp,0xC2
sbrc byte,0
eor calcrc,temp
ldi temp,0x9D
sbrc byte,0
eor calcrc,temp
ldi temp,0x23
sbrc byte,0
eor calcrc,temp
ldi temp,0x46
sbrc byte,0
eor calcrc,temp
ldi temp,0x8C
sbrc byte,0
ret Всего 69 МЦ. Кстати, КЦК одного байта считается за 24 МЦ и если использовать расчет КЦК для каждого байта, то получится 24*7=161 МЦ. Сравните с 525 МЦ(:-).
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
|
Sep 3 2006, 20:31
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Цитата(Oldring @ Sep 3 2006, 09:16) Цитата(=GM= @ Sep 3 2006, 12:55) Это круто )) P.S. Соревноваться в крутости оптимизации с сишным компилятором глупо, так как результат заранее очевиден. P.P.S. Предлагаемый алгоритм - 3 такта на бит - не дает никаких преимуществ по сравнению с просто развернутым побитовым циклом со сдвигами. Ускорение примерно в два раза может дать обработка по нибблам - при этом таблицу констант размером 16 байт следует предварительно скопировать в RAM и разместить в начале или конце 256-байтной страницы. См. инструкцию SWAP. Да, спасибо за замеченные опечатки и ошибки (копи-паст, понимаете ли(:-(). Вот исправленный вариант. Код crc8:
ld byte,z+
ldi bytcnt,8-1;счетчик байт минус 1
orbit:
ld temp,x+
eor byte,temp
dec bitcnt
brne orbit
clr calcrc
ldi temp,0x5E
sbrc byte,0
eor calcrc,temp
ldi temp,0xBC
sbrc byte,1
eor calcrc,temp
ldi temp,0x61
sbrc byte,2
eor calcrc,temp
ldi temp,0xC2
sbrc byte,3
eor calcrc,temp
ldi temp,0x9D
sbrc byte,4
eor calcrc,temp
ldi temp,0x23
sbrc byte,5
eor calcrc,temp
ldi temp,0x46
sbrc byte,6
eor calcrc,temp
ldi temp,0x8C
sbrc byte,7
eor calcrc,temp
ret Oldring, здесь на 7*8=56 бит расходуется 69 машинных циклов или вгрубе по 69/56=1.23 МЦ на бит.
Сообщение отредактировал =GM= - Sep 3 2006, 20:35
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
|
Sep 3 2006, 21:28
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Oldring @ Sep 4 2006, 00:44) Цитата(=GM= @ Sep 4 2006, 00:31)
Oldring, здесь на 7*8=56 бит расходуется 69 машинных циклов или вгрубе по 69/56=1.23 МЦ на бит.
без учета ret - да. Только это - не CRC  Это точно не CRC. ИМХО, проблемма в том что у Вас не обнуляеться временное значение CRC при переходе к следующему байту. Вот так: Код crc8: ;Input: r31:r30 buffer; r18 - number of bytes
;Output: r16 = CRC
ldi r16,0x5e
mov r8,r16
ldi r16,0xbc
mov r9,r16
ldi r16,0x61
mov r10,r16
ldi r16,0xc2
mov r11,r16
ldi r16,0x9d
mov r12,r16
ldi r16,0x23
mov r13,r16
ldi r16,0x46
mov r14,r16
ldi r16,0x8c
mov r15,r16
clr r16
crc8_0:
ld r17,z+
eor r17,r16
clr r16
sbrc r17,0
eor r16,r8
sbrc r17,1
eor r16,r9
sbrc r17,2
eor r16,r10
sbrc r17,3
eor r16,r11
sbrc r17,4
eor r16,r12
sbrc r17,5
eor r16,r13
sbrc r17,6
eor r16,r14
sbrc r17,7
eor r16,r15
dec r18
brne crc8_0
ret Получаем 177 тактов (не учитывая ret) НО, используем 8 лишних регистров 
|
|
|
|
|
|
Сообщений в этой теме
 =GM= Быстрое вычисление CRC-8 Sep 1 2006, 12:32 IgorKossak =GM=, почитайте внимательно о методах оптимизации ... Sep 1 2006, 12:54  =GM= Цитата(IgorKossak @ Sep 1 2006, 11:54) =G... Sep 1 2006, 13:59 singlskv Цитата(=GM= @ Sep 1 2006, 17:59) Цитата(I... Sep 1 2006, 15:11 pitt Код для onewire от Texas Instruments avr-gcc. Пере... Sep 1 2006, 12:56 pitt Цитата(Oldring @ Sep 3 2006, 06:16) Ускор... Sep 3 2006, 12:23 ivstech Вот мой код расчета CRC16,
не скажу, что я придум... Sep 4 2006, 05:11 Oldring Цитата(ivstech @ Sep 4 2006, 09:11) Вот м... Sep 4 2006, 11:07 =GM= Цитата(Oldring @ Sep 4 2006, 00:44) Это т... Sep 5 2006, 12:28 _artem_ Цитата(=GM= @ Sep 3 2006, 11:55) Цитата(s... Sep 3 2006, 16:07 pitt Чего я не понял, так это мы о скорости говорим или... Sep 1 2006, 17:28 singlskv Цитата(pitt @ Sep 1 2006, 21:28) Или цена... Sep 1 2006, 20:10 aaarrr Цитата(_artem_ @ Sep 3 2006, 20:07) =GM=,... Sep 3 2006, 17:52 Oldring Цитата(aaarrr @ Sep 3 2006, 21:52) А если... Sep 3 2006, 19:13 _Bill Цитата(aaarrr @ Sep 3 2006, 20:52) В поря... Sep 4 2006, 07:41 Oldring Для тех кто интересуется добавлю, что рассматривае... Sep 3 2006, 22:22 aaarrr Цитата(_Bill @ Sep 4 2006, 11:41) Без вся... Sep 4 2006, 08:00 _Bill Цитата(aaarrr @ Sep 4 2006, 11:00) Цитата... Sep 4 2006, 10:22 aaarrr Цитата(_Bill @ Sep 4 2006, 14:22) Накладн... Sep 4 2006, 11:31 Oldring Цитата(aaarrr @ Sep 4 2006, 15:31) Цитата... Sep 4 2006, 11:51 _Bill Цитата(aaarrr @ Sep 4 2006, 14:31) Как эт... Sep 4 2006, 12:33 aaarrr Цитата(Oldring @ Sep 4 2006, 15:51) Завис... Sep 4 2006, 12:09 aaarrr Цитата(_Bill @ Sep 4 2006, 16:33) Поэтому... Sep 4 2006, 13:06 _Bill Цитата(aaarrr @ Sep 4 2006, 16:06) Цитата... Sep 4 2006, 13:13 Smen Дяденьки, подскажите, плиз!
Если у меня прини... Jul 1 2013, 13:37 zombi Цитата(Smen @ Jul 1 2013, 16:37) какой ал... Jul 1 2013, 19:01 Smen Цитата(zombi @ Jul 1 2013, 23:01) Считайт... Jul 2 2013, 06:02
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
