Быстрое вычисление CRC-8, Потенциальные возможности не табличных методов Опции

[=GM=]

Недавно поднимался вопрос об оптимизации сишного кода, в частности был представлен такой код (немного отрихтовал для приличия)

Приятный алгоритм, возьму на вооружение. 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 циклов. Может я чего не понимаю, или полиномы неправильные?

[pitt]

Код для 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