| |
 Быстрое вычисление 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, 12:56
|
Местный
Группа: Участник
Сообщений: 328
Регистрация: 1-06-06
Из: USA
Пользователь №: 17 672
|
Код для onewire от Texas Instruments avr-gcc. Перенос на любой другой компилятор не должн быть проблемой. Код #include <avr/pgmspace.h>
typedef unsigned char byte;
byte crc_tab [256] PROGMEM = {
0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53
};
// One-wire device routines - single slave, external power
byte crc8 ( byte *ptr, byte cnt ) { // pointer to & length of the string
byte crc;
for ( crc = 0; cnt--; ) crc = pgm_read_byte ( &crc_tab[crc ^ *ptr++]);
return crc;
}
Сообщение отредактировал pitt - Sep 1 2006, 13:00
--------------------
|
|
|
|
|
|
|
|
Sep 1 2006, 15:11
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(=GM= @ Sep 1 2006, 17:59) Цитата(IgorKossak @ Sep 1 2006, 11:54) =GM=, почитайте внимательно о методах оптимизации у IAR, проникнитесь их изощрённостью и больше не удивляйтесь. Примите как есть и пользуйтесь на здоровье  Да какая ж там изощренность, если на ОДИН байт тратится 75 циклов, а у моего собственного кода - 11 циклов на тот же самый ОДИН байт! Как тут не удивляться! Попробую переложить собственный асм-код на си и опубликовать. Так опубликуйте на ASM, здесь его многие знают.
|
|
|
|
|
|
|
|
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:10
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(pitt @ Sep 1 2006, 21:28) Или цена таблицы во флеше слишком высока? Иногда высока, а иногда нет. Скомпилируйте Ваш код для AVR, напишите сколько байтов(слов) у Вас получилось, сколько памяти FLASH заняла Ваша таблица, и т.д., и т.п. И тогда обсудим ... Цитата(pitt @ Sep 1 2006, 21:28) Чего я не понял, так это мы о скорости говорим или о чем? Ну если чисто о скорости, то можно вообще без цикла обойтись, типа для 7 байт повторить последовательно вот этот код Код 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;
} Я думаю, что по размеру/скорости такой вариант окажется лучше чем табличный на 256 значений.
|
|
|
|
|
|
|
|
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 байт флеша - нисколько!
--------------------
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
