Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > CRC-8

Автор: podval 3.11.2004, 18:44

Нужно посчитать 8-битное CRC для строки из N байт.

Полином: X^8 + X^4 + X^3 + X^2 + 1

Начальное заполнение регистра: 0F или 00001111

не получается

Автор: Crait 4.11.2004, 02:11

Podval, а что именно не получается ?

Мобыть, несколько не в тему, но когда-то и мне
нужно было сделать CRC8. Так я по ленности своей ;-)

вычислял CRC16 (имелся под рукой такой модуль),
а потом ксорил старший и младший байты результата.
Работало (всмысле, определяло ошибки, а также и в качестве хеш-функции).

Кстати, если не секрет, откуда порождающий полином для CRC8 ?

Автор: podval 4.11.2004, 08:55

Я пробовал так:

Код


#define CRCPOLY 0x1D     // полином

static unsigned char crc8_table[256];

void crc8init (void) 
{ 
// заполнение таблицы
       unsigned char r; 
       int i, j; 

       for (i = 0; i < 256; i++) 
       { 
                for (r = (unsigned char)i, j = 0; j < 8; j++) 
                      r = (r >> 1) ^ ((r & 1) ? CRCPOLY : 0); 
    
                crc8_table[i] = r; 
       } 
}


unsigned char crc8_compute(unsigned char *str, unsigned char byte)
{
// str - указатель на строку, byte - ее длина в байтах

       unsigned char crc8 = 0x0F;    // начальное заполнение
	
       while (byte) 
       {
             crc8 = crc8_table[crc8 ^ * str++];
              --byte;
       }

       return crc8;
}

Проблема в том, что crc8 возвращается не то, какое надо.

Пробовал и это:

Код


unsigned char crc8_compute(unsigned char *str, unsigned char byte)
{
       unsigned char crc8 = 0x0F; // init state
       unsigned char i, j;

       while (byte--)
      {
             j = *str++;
             for (i = 0; i < 8; i++)
            {
                  if ((crc8 ^ j) & 1)
                  {
                       crc8 >>= 1;
                       crc8 ^= 0x8c;
                  } 
                  else 
                       crc8 >>= 1;
      
                  j >>= 1;
            }
     }
}

Получается другой результат и тоже неправильный. Я так понимаю, что второй вариант не адаптирован под мой полином. Может как-то можно адаптировать?

Но более всего непонятно, почему первый вариант выдает не то.

З.Ы. Полином из спецификации SBC-кодека.
Добавлено @ 09:00

Цитата(Crait @ 4.11.2004, 03:11)

а потом ксорил старший и младший байты результата.

Как? Друг с другом?

Автор: Crait 4.11.2004, 11:06

Цитата

Как? Друг с другом?

Ну да.

Могу еще посоветовать перебрать все 8-бит полиномы
и инициирующие значения - это не так и много - 65536 вариантов.

ЗЫ
А может еще и результат с чем-нибудь ксорится
- тут без анализа нескольких вариантов вход-выход не обойтись.

Автор: podval 4.11.2004, 11:14

Не, результат ни с чем не ксорится.

Автор: Crait 4.11.2004, 11:34

Вот, откопал у себя еще вариант CRC8. ПисАл не я.

crc8.h :

Код


#ifndef _CRC8_H_
#define _CRC8_H_
extern unsigned char crc8;
extern void crc8_compute(unsigned char *, unsigned char);

#endif /*_CRC8_H_ */

crc8.cpp :

Код


/*****************************************************
* Вычисление CRC8
* ----------------------------------------------------
* Автор: Александр Зайцев
* Дата: 10.03.2003
* www.alex-uc.narod.ru
* [email protected]
*****************************************************/

        #include    "crc8.h"
        
unsigned char crc8=0;
const unsigned char crc8_tabl[]={
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};

void
crc8_compute(unsigned char * str, unsigned char byte)
{
    while (byte) {
        crc8=crc8_tabl[crc8 ^ * str++];
        --byte;
    }
}

Автор: podval 4.11.2004, 11:41

Дык это ж то же самое

Только таблица сформирована из другого полинома и начальное заполнение нулевое.

Автор: Crait 4.11.2004, 11:54

Ага. Подумал, может, полином у тебя именно такой,
как в этом исходнике.

Автор: podval 5.11.2004, 11:18

Нашел! Таблицу надо формировать "зеркально":

Код


void crc8init (void)
{
     int i,j;
     unsigned char r;

     for (i = 0; i < 256; i++) 
    {
         r = (unsigned char) i;
         for (j = 0; j < 8; j++)
             r = (unsigned char) ((r << 1) ^ ((r & 0x80) ? CRCPOLY : 0));
  
         crc8_table[i] = (unsigned char)(crc & 0xFF);
    }
}

Автор: podval 26.11.2004, 14:56

Как переделать этот алгоритм, чтобы он обрабатывал не байты, а полубайты?
smile

Проблема в том, что мне надо обработать строку, которая не умещается в целое число байт. Остановить подсчет CRC надо именно на последнем полубайте. Последний же из приведенных здесь табличных алгоритмов разработан под обработку целого числа байт и не может обработать, например 6 и 1/2 байта.

Автор: oleg1973 27.11.2004, 19:22

Код


format PE GUI 4.0
entry start
include '%fasminc%\win32a.inc'
include '%fasminc%\api.inc'
section '.code' code readable executable writeable
start:
        mov ecx,5  ;кол-во 4 байтных элементов 
        mov esi,mydata  ;массив данных
        xor eax,eax
        xor edx,edx
go:
        mov al,[esi]
        shr al,4
        add edx,eax
        dec ecx
        jz exit
        mov al,[esi]
        and al,0xf
        add edx,eax
        inc esi
        dec ecx
        jnz go
exit:
        and edx,0xff
        invoke wsprintf,buff,form,edx
        invoke MessageBox,0,buff,txt,0
        invoke ExitProcess,0
form:
        db '%d',0
buff:
        dd 0
txt:
        db 'CRC8',0
mydata:
        db 255,55,83,95,45,25,250,85,78,32,150

а вот для полубайтов smile

))

Автор: Crait 27.11.2004, 22:57

Могу рассказать, как формировать CRC побитно.
Это актуально, podval ?

Автор: podval 29.11.2004, 10:06

Crait
Я думал, что и так это знаю, только у меня почему-то побитный результат не совпал с табличным. smile

Вручную на бумаге получается такой же результат, как и у побитного. Но я точно знаю, что табличный алгоритм правильный - он дает те же результаты, что и reference кодек.

Я считал для такой строки: 2С 2А 00 00 00 0 . У меня получилось 8D, а правильный ответ Е8.
Вот еще и код слепил:

Код



#define CRCPOLY 0x1D

unsigned char crc8_lob(unsigned char *str, int bit_number)
{
  int    bits_from_byte = 8  // счетчик бит в байте
        , full_bits;                   

  unsigned char reg = 0x0F    // начальное заполнение регистра
                , tmp_byte;

  full_bits = bit_number + 8; // дописываем 8 нулей
  tmp_byte = *str;                // текущий обрабатываемый байт

  while(full_bits)
  {
    if( (reg & 0x80) == 0x80 ) // если из регистра вытолкнется единица
    {
      reg <<= 1;
      
      if ( (tmp_byte & 0x80) == 0x80 )
        reg |= 1;    // единица, выталкиваемая из старшего бита строки

      tmp_byte <<= 1;
      --bits_from_byte;
      --full_bits;
      
      if(!bits_from_byte)
      {
        tmp_byte = *(++str);   // чтение следующего байта
        bits_from_byte = 8;
      }

      reg ^= CRCPOLY;         
    }
    else
    {
      reg <<= 1;                        // все то же, но не ксорим регистр
      
      if ( (tmp_byte & 0x80) == 0x80 )
        reg |= 1;

      tmp_byte <<= 1;
      --bits_from_byte;
      --full_bits;

      if(!bits_from_byte)
      {
        tmp_byte = *(++str);
        bits_from_byte = 8;
      }    
    } 
  } 

  return reg;
}

Что не так? Если я и правда что-то недоучил, то с меня пол-литры smile

Еще раз попытаюсь объяснить ситуацию. Кодек-образец и мой кодек (с табличным алгоритмом) работают в плане вычисления CRC одинаково до тех пор, пока надо вычислять CRC на целом количестве байт.
КАК ИМЕННО надо вычислять CRC в ситуации, когда данные занимают сколько-то с половиной байт, в спецификации не указано (руки оторвать писателям! smile

).

Однако такой же CRC, как я выяснил, используется в GSM/TCH/EFS Precoder. Может кто-то знает, как там разруливается эта ситуация?

Добавлено @ 10:09
oleg1973
Я попытасюсь вспомнить асм smile

Только че-то не скачивается ехе.

Автор: podval 29.11.2004, 10:41

Поигрался сейчас с отбрасыванием лишних пол-байт и дополнением нулями до байта - туфта выходит. Не совпадает с refrence codec.

Наверное, в консерватории надо что-то поправить. Поможите, люди добрые! smile

Автор: podval 29.11.2004, 17:17

Кажись, обнаружил пробел в "консерватории". Вот так работает, если ксорить на каждом шаге содержимое регистра с байтом сообщения и проверять старший бит результата:

Код



...

tmp = reg ^ tmp_byte;

if( (tmp& 0x80) == 0x80 )
{
     ...
}

...

Автор: LuLok 19.2.2007, 15:27

я реализовал CRC8 вот так:

Код


void __fastcall TForm1::FormCreate(TObject *Sender)
{
   BYTE mass[] = {0x03,0x5b, 0};
   BYTE poly = 0x98;

   int N = (sizeof(mass) / sizeof(mass[0]));
   BYTE reg = 0;
   for (int i = 0; i < N; i++)
      {
      for(int j = 0; j < 8; j++)
         {

         if (reg & 0x80)
            {

            reg = reg ^ poly;

            }

         reg <<= 1;
        
         if (mass[i] & (0x80 >> j))
            reg = reg | 0x01;

         } 
      }
}

Если верить книжке Ross N. Williams. "Элементарное руководство по CRC-алгоритмам обнаружения ошибок", то считает правильно...