| |
 Быстрое вычисление 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, 12:23
|
Местный
Группа: Участник
Сообщений: 328
Регистрация: 1-06-06
Из: USA
Пользователь №: 17 672
|
Цитата(Oldring @ Sep 3 2006, 06:16) Ускорение примерно в два раза может дать обработка по нибблам - при этом таблицу констант размером 16 байт следует предварительно скопировать в RAM и разместить в начале или конце 256-байтной страницы. См. инструкцию SWAP. А вот RAM, как раз очень жалко, a 256 байт флеша - нисколько!
--------------------
|
|
|
|
|
|
|
|
Sep 4 2006, 05:11
|
Местный
Группа: Свой
Сообщений: 204
Регистрация: 5-01-06
Пользователь №: 12 860
|
Вот мой код расчета CRC16,
не скажу, что я придумал такой алгоритм, т.к. видел аналог для другого полинома, но это и не таблица и не цикл
; По модулю 0x11021
; IN R18 - DATA
; IN, OUT R4, R5 - аккумулятор
CRC16Update:
push R18
push R19
eor R4, R18
ldi R18, 0x00
mov R19, R4
andi R19, 0xF0
eor R18, R19
swap R19
eor R4, R19
add R19, R19
eor R5, R19
mov R19, R4
andi R19, 0x0F
eor R18, R19
swap R19
eor R5, R19
add R19, R19
brcc CRC16Skip
clr R4
inc R4
eor R5, R4
CRC16Skip:
eor R18, R19
mov R4, R5
mov R5, R18
pop R19
pop R18
ret
Сообщение отредактировал ivstech - Sep 4 2006, 05:28
|
|
|
|
|
|
Сообщений в этой теме
 =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 Oldring Цитата(ivstech @ Sep 4 2006, 09:11) Вот м... Sep 4 2006, 11:07 =GM= Цитата(Oldring @ Sep 3 2006, 09:16) Цитат... Sep 3 2006, 20:31 Oldring Цитата(=GM= @ Sep 4 2006, 00:31) Oldring,... Sep 3 2006, 20:44 singlskv Цитата(Oldring @ Sep 4 2006, 00:44) Цитат... Sep 3 2006, 21:28 =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
|
|
|
