CRC 16 и CRC 32

123kill12 0

22 декабря, 2010

Опубликовано 22 декабря, 2010 · Жалоба

Нашел такое описание.

Табличный алгоритм. Его суть состоит в следующем: при выполнении операции XOR содержимого регистра с постоянной величиной при различных её сдвигах всегда будет существовать некоторое значение, которое при применении операции XOR с исходным содержимым регистра даст тот же самый результат. А значит, можно составить таблицу таких величин, где индексом является исходное содержимое регистра. Эта таблица позволяет значительно ускорить расчёт CRC заменой восьми операций сдвига одной операцией поиска по таблице.

Всего значений в таблице 256. Поэтому при ее расчёте выполняется цикл по 256 значениям (от 0 до 255):

1.Очередной индекс помещается в регистр. Так как индекс представляет собой один байт, а величина полинома и регистра - два байта, индекс помещается в старший байт регистра, а младший байт заполнен нулями.

2. Содержимое регистра восемь раз сдвигается влево по одному биту. Каждый раз проверяется выдвинутый бит. Если из регистра был выдвинут бит со значением "1", то содержимое регистра комбинируется по XOR с полиномом. Если значение бита равно "0", XOR не выполняется.

3. Полученная двухбайтовая величина заносится в таблицу по индексу.

После того как таблица рассчитана, можно использовать табличный алгоритм CRC:

1. Сдвиг регистра на 1 байт влево с чтением нового байта сообщения.

2. XOR старшего байта, только что выдвинутого из регистра с новым байтом сообщения, что даёт индекс в таблице [0..255].

3. XOR табличного значения с содержимым регистра.

4. Если ещё есть байты данных, перейти к шагу 1.

В данной статье используется описанный выше табличный алгоритм.

Код для расчёта таблицы:

Word MakeCRC16Table(void)

{

Word r;

for(int i=0; i<256; i++)

{

r = ((Word)i)<<8;

for(byte j=0; j<8; j++)

{

if(r&(1<<15)) r=(r<<1)^0x8005;

else r=r<<1;

}

crctable=r;

}

Код для расчёта CRC:

Word GetCRC16(byte *buf, Word len)

{

Word crc;

crc = 0xFFFF;

while(len--)

{

crc = crctable[((crc>>8)^*buf++)&0xFF] ^ (crc<<8);

}

crc ^= 0xFFFF;

return crc;

}

но это алгоритм для вычисление CRC 16 одного байта. а как высчитать CRC16 последовательности байт.

есть например UDP пакет

заголовок

Src Port: 47202 (47202), 68:62

Dst Port: vce (11111) 26:67

Length: 28 00:1C

Checksum: 0x0000 (none) 00:00 (это контрольная сумма что нужно получить)

Data--11:00:48:25:be:0a:5a:0a:7f:ff:ff:ff:00:03:20:00:24:cd:ff:00

CRC=GetCRC16(0x6862, 16);

CRC=CRC+GetCRC16(0x2667, 16);

CRC=CRC+GetCRC16(0x001C, 16);

....

так или его нужно какие "финты ушами" делать при сложении CRC???

А вообще для CRC в UDP пакете используется полином 0x8005?

аналогично для CRC в IP пакете?

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

rezident 0

22 декабря, 2010

Опубликовано 22 декабря, 2010 · Жалоба

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

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

123kill12 0

22 декабря, 2010

Опубликовано 22 декабря, 2010 · Жалоба

вообще то я не это спрашивал.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

xvr 12

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

так или его нужно какие "финты ушами" делать при сложении CRC???

Вы и так уже 'нафинтили ушами' при 'сложении CRC' :wacko:

Откуда у вас эти магические числа (0x6862/0x2667/0x001C) в параметре, где ожидается адрес буфера? И почему параметр 'длинна' всегда 16? У вас там по 16 байтов где то лежит?

но это алгоритм для вычисление CRC 16 одного байта.

Это код для вычисления CRC16 массива в памяти, а не одного байта

CRC=CRC+GetCRC16(0x2667, 16);

Это в корне неправильно. Если вам надо 'накапливать' CRC, то процедуру GetCRC16 придется изменить:

Word GetCRC16(byte *buf, Word len, Word crc)
{
while(len--)
  {
   crc = crctable[((crc>>8)^*buf++)&0xFF] ^ (crc<<8);
  }
return crc;
}

Word crc=0xFFFF;
crc=GetCRC16(buf1,len1,crc);
crc=GetCRC16(buf2,len2,crc);
crc=GetCRC16(buf3,len3,crc);
crc ^= 0xFFFF;

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

123kill12 0

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

я эти числа взял из wireshark. нашел udp пакет и хотел разобраться.

Простой алгоритм расчёта CRC выполняется следующим образом:

1. В регистр CRC заносится начальное значение FFFFh.

2. В конец сообщения добавляется W нулевых битов

3. Содержимое регистра сдвигается влево на 1 бит, и в последнюю (нулевую) позицию заносится очередной, ещё не обработанный бит данных.

4. Если из регистра был выдвинут бит со значением "1", то содержимое регистра комбинируется по XOR с полиномом. Если значение бита равно "0", XOR не выполняется.

5. Шаги 3 и 4 выполняются, пока не будут обработаны все данные.

6. Окончательное содержимое регистра комбинируется по XOR со значением FFFFh.

у меня есть массив данных arr=11:00:48:25:be:0a:5a:0a:7f:ff:ff:ff:00:03:20:00:24:cd:ff:00

то

1. шаг - CRC=FFFF

2. шаг - В конец сообщения добавляется W нулевых битов. то есть я в конец массива данных добавляю 00:00 и получаю новый -

11:00:48:25:be:0a:5a:0a:7f:ff:ff:ff:00:03:20:00:24:cd:ff:00:00:00

3. шаг - if(CRC&(1<<15)) {

CRC<<1;

CRC=CRC XOR 0x8005;

}

else

{

CRC<<1;

}

CRC=CRC OR arr[1]>>8; в последнюю (нулевую) позицию заносится очередной, ещё не обработанный бит данных.

arr[1]<<1;

4. шаг - выполняем 3 шаг 8 раз.

5. шаг - инкрементируем счетчик массива на следующее число.

6. шаг - выполняем шаг 3-5 пока массив не закончится.

7. шаг - CRC = CRC XOR 0xFFFF;

и CRC это та контрольная сумма массива arr.

Я верно все понял?

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

xvr 12

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

Я верно все понял?

Нет, не верно. Это алгоритм для расчета таблицы. В нем входные данные не участвуют.

Для побитового подсчета CRC от входных данных в п4 выдвинутое значение надо проXORить с битом входных данных, далее по тексту.

В реальности используется таблицы, и входные данные обрабатываются побайтно, а не побитно.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

rezident 0

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

Зачем какие-то нули в конец пакета добавлять? :blink: Нужно вызвать функцию подсчета CRC с требуемыми аргументами.

1-й аргумент: указатель на начало буфера (начало массива),

2-й аргумент: размер буфера для расчета (количество символов пакета, но не размер всего массива, отведенного для хранения данных!),

3-й аргумент: начальное значение CRC. 3-й аргумент д.б. равен 0xFFFF, если расчет с начала пакета данных идет, либо равен предыдущему значению CRC, если расчет идет по "кусочкам" (по одному байту, например) пакета данных.

В результате значение CRC, возвращаемое функцией после расчета по всему пакету данных, должно быть равно нулю. Если оно не равно нулю, то пакет испорчен и данным пакета доверять нельзя.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

123kill12 0

23 декабря, 2010

Опубликовано 23 декабря, 2010 (изменено) · Жалоба

Для побитового подсчета CRC от входных данных в п4 выдвинутое значение надо проXORить с битом входных данных, далее по тексту.

я делаю -> CRC=CRC OR arr[1]>>8;

В реальности используется таблицы, и входные данные обрабатываются побайтно, а не побитно.

бббб. я не понимаю.

объясните на примере.

вот у меня есть массив 11:00:48:25:be:0a:5a:0a:7f:ff:ff:ff:00:03:20:00:24:cd:ff:00

и есть таблица

CRCTable : Array [0..255] of Word= (

$0000, $C0C1, $C181, $0140, $C301, $03C0, $0280, $C241,

$C601, $06C0, $0780, $C741, $0500, $C5C1, $C481, $0440,

$CC01, $0CC0, $0D80, $CD41, $0F00, $CFC1, $CE81, $0E40,

$0A00, $CAC1, $CB81, $0B40, $C901, $09C0, $0880, $C841,

$D801, $18C0, $1980, $D941, $1B00, $DBC1, $DA81, $1A40,

$1E00, $DEC1, $DF81, $1F40, $DD01, $1DC0, $1C80, $DC41,

$1400, $D4C1, $D581, $1540, $D701, $17C0, $1680, $D641,

$D201, $12C0, $1380, $D341, $1100, $D1C1, $D081, $1040,

$F001, $30C0, $3180, $F141, $3300, $F3C1, $F281, $3240,

$3600, $F6C1, $F781, $3740, $F501, $35C0, $3480, $F441,

$3C00, $FCC1, $FD81, $3D40, $FF01, $3FC0, $3E80, $FE41,

$FA01, $3AC0, $3B80, $FB41, $3900, $F9C1, $F881, $3840,

$2800, $E8C1, $E981, $2940, $EB01, $2BC0, $2A80, $EA41,

$EE01, $2EC0, $2F80, $EF41, $2D00, $EDC1, $EC81, $2C40,

$E401, $24C0, $2580, $E541, $2700, $E7C1, $E681, $2640,

$2200, $E2C1, $E381, $2340, $E101, $21C0, $2080, $E041,

$A001, $60C0, $6180, $A141, $6300, $A3C1, $A281, $6240,

$6600, $A6C1, $A781, $6740, $A501, $65C0, $6480, $A441,

$6C00, $ACC1, $AD81, $6D40, $AF01, $6FC0, $6E80, $AE41,

$AA01, $6AC0, $6B80, $AB41, $6900, $A9C1, $A881, $6840,

$7800, $B8C1, $B981, $7940, $BB01, $7BC0, $7A80, $BA41,

$BE01, $7EC0, $7F80, $BF41, $7D00, $BDC1, $BC81, $7C40,

$B401, $74C0, $7580, $B541, $7700, $B7C1, $B681, $7640,

$7200, $B2C1, $B381, $7340, $B101, $71C0, $7080, $B041,

$5000, $90C1, $9181, $5140, $9301, $53C0, $5280, $9241,

$9601, $56C0, $5780, $9741, $5500, $95C1, $9481, $5440,

$9C01, $5CC0, $5D80, $9D41, $5F00, $9FC1, $9E81, $5E40,

$5A00, $9AC1, $9B81, $5B40, $9901, $59C0, $5880, $9841,

$8801, $48C0, $4980, $8941, $4B00, $8BC1, $8A81, $4A40,

$4E00, $8EC1, $8F81, $4F40, $8D01, $4DC0, $4C80, $8C41,

$4400, $84C1, $8581, $4540, $8701, $47C0, $4680, $8641,

$8201, $42C0, $4380, $8341, $4100, $81C1, $8081, $4040);

нужно получить CRC16.

Изменено 23 декабря, 2010 пользователем 123kill12

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

rezident 0

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

Я извиняюсь, а вы на каком языке пишете программу? И чем вас не устроил Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си, приведенный ранее в указанной статье из Википедии? Там всего лишь один параметр (начальное/промежуточное значение CRC) добавить (вынести как аргумент функции) нужно.

unsigned short Crc16(unsigned char * pcBlock, unsigned short len, unsigned short crc)
{ while (len--)
    crc = (crc >> 8) ^ Crc16Table[(crc & 0xFF) ^ *pcBlock++];
  return crc;
}

Естественно, что таблицу CRC из того примера тоже нужно включать в исходник.

Допустим пакет располагается у вас а массиве который объявлен как

unsigned char UDPpocketArray[1043];

Размер вашего пакета 11:00:48:25:be:0a:5a:0a:7f:ff:ff:ff:00:03:20:00:24:cd:ff:00 - 20 байт.

Тогда вызов функции подсчета CRC16 будет

crc=Crc16(&UDPpocketArray[0], 20, 0xFFFF);

Если в результате после вызова функции переменная crc имеет значение 0, то пакет валидный.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

123kill12 0

23 декабря, 2010

Опубликовано 23 декабря, 2010 · Жалоба

так вот пример кода.

скажите я правильно понял как работает код программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си

LIBRARY ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_bit.all;

entity crc2 is 
  port ( data_in : bit_vector (7 downto 0);
    rst, clk, set: in std_logic;
    W:            out bit_vector (15 downto 0);
    crc_out : out bit_vector (15 downto 0));
end crc2;

architecture imp_crc2 of crc2 is    
type rom_1_type is array (255 downto 0) of integer;
signal table: rom_1_type:=(
    16#0000#, 16#C0C1#, 16#C181#, 16#0140#, 16#C301#, 16#03C0#, 16#0280#, 16#C241#,
    16#C601#, 16#06C0#, 16#0780#, 16#C741#, 16#0500#, 16#C5C1#, 16#C481#, 16#0440#,
    16#CC01#, 16#0CC0#, 16#0D80#, 16#CD41#, 16#0F00#, 16#CFC1#, 16#CE81#, 16#0E40#,
    16#0A00#, 16#CAC1#, 16#CB81#, 16#0B40#, 16#C901#, 16#09C0#, 16#0880#, 16#C841#,
    16#D801#, 16#18C0#, 16#1980#, 16#D941#, 16#1B00#, 16#DBC1#, 16#DA81#, 16#1A40#,
    16#1E00#, 16#DEC1#, 16#DF81#, 16#1F40#, 16#DD01#, 16#1DC0#, 16#1C80#, 16#DC41#,
    16#1400#, 16#D4C1#, 16#D581#, 16#1540#, 16#D701#, 16#17C0#, 16#1680#, 16#D641#,
    16#D201#, 16#12C0#, 16#1380#, 16#D341#, 16#1100#, 16#D1C1#, 16#D081#, 16#1040#,
    16#F001#, 16#30C0#, 16#3180#, 16#F141#, 16#3300#, 16#F3C1#, 16#F281#, 16#3240#,
    16#3600#, 16#F6C1#, 16#F781#, 16#3740#, 16#F501#, 16#35C0#, 16#3480#, 16#F441#,
    16#3C00#, 16#FCC1#, 16#FD81#, 16#3D40#, 16#FF01#, 16#3FC0#, 16#3E80#, 16#FE41#,
    16#FA01#, 16#3AC0#, 16#3B80#, 16#FB41#, 16#3900#, 16#F9C1#, 16#F881#, 16#3840#,
    16#2800#, 16#E8C1#, 16#E981#, 16#2940#, 16#EB01#, 16#2BC0#, 16#2A80#, 16#EA41#,
    16#EE01#, 16#2EC0#, 16#2F80#, 16#EF41#, 16#2D00#, 16#EDC1#, 16#EC81#, 16#2C40#,
    16#E401#, 16#24C0#, 16#2580#, 16#E541#, 16#2700#, 16#E7C1#, 16#E681#, 16#2640#,
    16#2200#, 16#E2C1#, 16#E381#, 16#2340#, 16#E101#, 16#21C0#, 16#2080#, 16#E041#,
    16#A001#, 16#60C0#, 16#6180#, 16#A141#, 16#6300#, 16#A3C1#, 16#A281#, 16#6240#,
    16#6600#, 16#A6C1#, 16#A781#, 16#6740#, 16#A501#, 16#65C0#, 16#6480#, 16#A441#,
    16#6C00#, 16#ACC1#, 16#AD81#, 16#6D40#, 16#AF01#, 16#6FC0#, 16#6E80#, 16#AE41#,
    16#AA01#, 16#6AC0#, 16#6B80#, 16#AB41#, 16#6900#, 16#A9C1#, 16#A881#, 16#6840#,
    16#7800#, 16#B8C1#, 16#B981#, 16#7940#, 16#BB01#, 16#7BC0#, 16#7A80#, 16#BA41#,
    16#BE01#, 16#7EC0#, 16#7F80#, 16#BF41#, 16#7D00#, 16#BDC1#, 16#BC81#, 16#7C40#,
    16#B401#, 16#74C0#, 16#7580#, 16#B541#, 16#7700#, 16#B7C1#, 16#B681#, 16#7640#,
    16#7200#, 16#B2C1#, 16#B381#, 16#7340#, 16#B101#, 16#71C0#, 16#7080#, 16#B041#,
    16#5000#, 16#90C1#, 16#9181#, 16#5140#, 16#9301#, 16#53C0#, 16#5280#, 16#9241#,
    16#9601#, 16#56C0#, 16#5780#, 16#9741#, 16#5500#, 16#95C1#, 16#9481#, 16#5440#,
    16#9C01#, 16#5CC0#, 16#5D80#, 16#9D41#, 16#5F00#, 16#9FC1#, 16#9E81#, 16#5E40#,
    16#5A00#, 16#9AC1#, 16#9B81#, 16#5B40#, 16#9901#, 16#59C0#, 16#5880#, 16#9841#,
    16#8801#, 16#48C0#, 16#4980#, 16#8941#, 16#4B00#, 16#8BC1#, 16#8A81#, 16#4A40#,
    16#4E00#, 16#8EC1#, 16#8F81#, 16#4F40#, 16#8D01#, 16#4DC0#, 16#4C80#, 16#8C41#,
    16#4400#, 16#84C1#, 16#8581#, 16#4540#, 16#8701#, 16#47C0#, 16#4680#, 16#8641#,
    16#8201#, 16#42C0#, 16#4380#, 16#8341#, 16#4100#, 16#81C1#, 16#8081#, 16#4040#);
  signal CRC: integer;
  signal CRC_s: bit_vector (15 downto 0);
  signal reg: bit_vector (7 downto 0);
  signal number_table: bit_vector (15 downto 0);
  signal count: integer;
  signal table_w: integer;
  signal flag:      std_logic:='0';

begin 
  process(clk, rst, set)
  begin
  if(rst='1') then
    CRC<=16#FFFF#;
    crc_out<=b"0000000000000000";
    W<=b"0000000000000000";
    count<=16#0000#;
  end if;
  if(set='1') then
    reg<=data_in;
    flag<='1';
  end if;
  if(clk'event and clk='1') then
    if(flag='1') then
        --(crc & 0xFF) ^ *pcBlock++
        number_table<=(To_BitVector(STD_LOGIC_VECTOR(IEEE.numeric_std.To_Unsigned(CRC,16))) and b"0000000011111111") XOR reg;
        --Crc16Table[(crc & 0xFF) ^ *pcBlock++]
        table_w<=table(to_integer(signed (number_table)));
        --(crc >> 8) ^ Crc16Table[(crc & 0xFF) ^ *pcBlock++]
        CRC_s<=((To_BitVector(STD_LOGIC_VECTOR(IEEE.numeric_std.To_Unsigned(CRC,16)))) srl 8) 
                XOR To_BitVector(STD_LOGIC_VECTOR(IEEE.numeric_std.To_Unsigned(table_w,16)));
        CRC<=to_integer(signed (CRC_s));
        count<=count+1;
        flag<='0';
        crc_out<=CRC_s;
        W<=To_BitVector(STD_LOGIC_VECTOR(IEEE.numeric_std.To_Unsigned(count,16)));
    end if;
  end if;
  end process;
end architecture imp_crc2;