Восстановить полином CRC16 по функции табличного рассчета Опции

[Dima_G]

Добрый день!
Нужно восстановить полином (для реализации его в FPGA) по следующему алгоритму расчета CRC16

Код

unsigned crc16_table[256] = {

    0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,

    0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,0xe97e,0xf8f7,

    0x1891,0x0918,0x3b83,0x2a0a,0x5eb5,0x4f3c,0x7da7,0x6c2e,

    0x94d9,0x8550,0xb7cb,0xa642,0xd2fd,0xc374,0xf1ef,0xe066,

    0x3122,0x20ab,0x1230,0x03b9,0x7706,0x668f,0x5414,0x459d,

    0xbd6a,0xace3,0x9e78,0x8ff1,0xfb4e,0xeac7,0xd85c,0xc9d5,

    0x29b3,0x383a,0x0aa1,0x1b28,0x6f97,0x7e1e,0x4c85,0x5d0c,

    0xa5fb,0xb472,0x86e9,0x9760,0xe3df,0xf256,0xc0cd,0xd144,

    0x6244,0x73cd,0x4156,0x50df,0x2460,0x35e9,0x0772,0x16fb,

    0xee0c,0xff85,0xcd1e,0xdc97,0xa828,0xb9a1,0x8b3a,0x9ab3,

    0x7ad5,0x6b5c,0x59c7,0x484e,0x3cf1,0x2d78,0x1fe3,0x0e6a,

    0xf69d,0xe714,0xd58f,0xc406,0xb0b9,0xa130,0x93ab,0x8222,

    0x5366,0x42ef,0x7074,0x61fd,0x1542,0x04cb,0x3650,0x27d9,

    0xdf2e,0xcea7,0xfc3c,0xedb5,0x990a,0x8883,0xba18,0xab91,

    0x4bf7,0x5a7e,0x68e5,0x796c,0x0dd3,0x1c5a,0x2ec1,0x3f48,

    0xc7bf,0xd636,0xe4ad,0xf524,0x819b,0x9012,0xa289,0xb300,

    0xc488,0xd501,0xe79a,0xf613,0x82ac,0x9325,0xa1be,0xb037,

    0x48c0,0x5949,0x6bd2,0x7a5b,0x0ee4,0x1f6d,0x2df6,0x3c7f,

    0xdc19,0xcd90,0xff0b,0xee82,0x9a3d,0x8bb4,0xb92f,0xa8a6,

    0x5051,0x41d8,0x7343,0x62ca,0x1675,0x07fc,0x3567,0x24ee,

    0xf5aa,0xe423,0xd6b8,0xc731,0xb38e,0xa207,0x909c,0x8115,

    0x79e2,0x686b,0x5af0,0x4b79,0x3fc6,0x2e4f,0x1cd4,0x0d5d,

    0xed3b,0xfcb2,0xce29,0xdfa0,0xab1f,0xba96,0x880d,0x9984,

    0x6173,0x70fa,0x4261,0x53e8,0x2757,0x36de,0x0445,0x15cc,

    0xa6cc,0xb745,0x85de,0x9457,0xe0e8,0xf161,0xc3fa,0xd273,

    0x2a84,0x3b0d,0x0996,0x181f,0x6ca0,0x7d29,0x4fb2,0x5e3b,

    0xbe5d,0xafd4,0x9d4f,0x8cc6,0xf879,0xe9f0,0xdb6b,0xcae2,

    0x3215,0x239c,0x1107,0x008e,0x7431,0x65b8,0x5723,0x46aa,

    0x97ee,0x8667,0xb4fc,0xa575,0xd1ca,0xc043,0xf2d8,0xe351,

    0x1ba6,0x0a2f,0x38b4,0x293d,0x5d82,0x4c0b,0x7e90,0x6f19,

    0x8f7f,0x9ef6,0xac6d,0xbde4,0xc95b,0xd8d2,0xea49,0xfbc0,

    0x0337,0x12be,0x2025,0x31ac,0x4513,0x549a,0x6601,0x7788

};


/* compute 16 bit CCITT crc using the table */

unsigned crc16(unsigned crc,unsigned b)

{

    unsigned ret = crc16_table[(b ^ crc) & 0xff] ^ (crc >> 8);

    return ret;

}

Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает
Пробовал сравнивать с иными полиномами - тоже безуспешно.
Железяка защищает этой CRC данные по HDLC

Может кто-нибудь сталкивался и сможет помочь?

[MrYuran]

Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает

А задом наперед?

[Dima_G]

А задом наперед?

Вы про данные? Крутил и так и сяк (q[7:0], q[0:7])

[MrYuran]

Вы про данные?

Не, про полином... (полиномы)

Сдается мне, первое значение в таблице (не нулевое) и есть искомый полином.

[Dima_G]

Не, про полином... (полиномы)

Сдается мне, первое значение в таблице (не нулевое) и есть искомый полином.

Хм, пробовал крутить 1189 на калькуляторе
http://zorc.breitbandkatze.de/crc.html

В качестве тестового примера взял байт '0'==0x30
Расчет с помощью функции из первого поста дает значение
29B3

с помощью калькулятора

Код

(polynom reverse=0,data reverce=0) 1B2B
(polynom reverse=0,data reverce=1) CAC6
(polynom reverse=1,data reverce=0) 9956
(polynom reverse=1,data reverce=1) B7DD

[klop]

Когда то игрался с подобным. Вроде для реверсивного полинома надо в конце накопленные 16 бит инвертировать и байты в них местами поменять.

[Dima_G]

Когда то игрался с подобным. Вроде для реверсивного полинома надо в конце накопленные 16 бит инвертировать и байты в них местами поменять.

Попробовал сделать инверсию, не помогло (или не так делаю )

[des00]

Попробовал сделать инверсию, не помогло (или не так делаю )

может инициализация не правильная ? например надо с 0xFFFF начинать.

[Dima_G]

может инициализация не правильная ? например надо с 0xFFFF начинать.

Я в тестовом примере пробовал инициализацию с нуля (так именно та плата считает)
те

Код

  
unsigned short crc = 0;
crc = crc16(crc, 0x30);
printf("CRC=0x%X\n"m crc);

Соответственно и в калькуляторах начальное значение 0 делал. В принципе, пока из положения вышел (ПЗУ в FPGA + расчет аналогичный как в плате), но ИМХО это не сильно красиво да и свои минусы есть (либо создавать по инстансу ПЗУ для каждого контроллера (а их десятки будут, те затраты Nx256*2), либо продумывать разделение доступа к одному

[klop]

было приблизительно так

Код

// 0x1021
function [15:0] fn_crc_ccitt;
input[15:0] crc_current;
input[7:0] data;
begin
fn_crc_ccitt[0]  = data[4] ^ data[0] ^ crc_current[8] ^ crc_current[12];
fn_crc_ccitt[1]  = data[5] ^ data[1] ^ crc_current[9] ^ crc_current[13];
fn_crc_ccitt[2]  = data[6] ^ data[2] ^ crc_current[10] ^ crc_current[14];
fn_crc_ccitt[3]  = data[7] ^ data[3] ^ crc_current[11] ^ crc_current[15];
fn_crc_ccitt[4]  = data[4] ^ crc_current[12];
fn_crc_ccitt[5]  = data[5] ^ data[4] ^ data[0] ^ crc_current[8] ^ crc_current[12] ^ crc_current[13];
fn_crc_ccitt[6]  = data[6] ^ data[5] ^ data[1] ^ crc_current[9] ^ crc_current[13] ^ crc_current[14];
fn_crc_ccitt[7]  = data[7] ^ data[6] ^ data[2] ^ crc_current[10] ^ crc_current[14] ^ crc_current[15];
fn_crc_ccitt[8]  = data[7] ^ data[3] ^ crc_current[0] ^ crc_current[11] ^ crc_current[15];
fn_crc_ccitt[9]  = data[4] ^ crc_current[1] ^ crc_current[12];
fn_crc_ccitt[10] = data[5] ^ crc_current[2] ^ crc_current[13];
fn_crc_ccitt[11] = data[6] ^ crc_current[3] ^ crc_current[14];
fn_crc_ccitt[12] = data[7] ^ data[4] ^ data[0] ^ crc_current[4] ^ crc_current[8] ^ crc_current[12] ^ crc_current[15];
fn_crc_ccitt[13] = data[5] ^ data[1] ^ crc_current[5] ^ crc_current[9] ^ crc_current[13];
fn_crc_ccitt[14] = data[6] ^ data[2] ^ crc_current[6] ^ crc_current[10] ^ crc_current[14];
fn_crc_ccitt[15] = data[7] ^ data[3] ^ crc_current[7] ^ crc_current[11] ^ crc_current[15];
end     
endfunction     


// 0x8408
function [7:0] fn_reverse_data;
input[7:0] data;
integer    i;
begin
for(i=0;i<8;i=i+1)  fn_reverse_data[i]    = data[7-i];
end     
endfunction     

function [15:0] fn_reverse_inverse_crc;
input[15:0] crc;
integer    i;
begin
for(i=0;i<16;i=i+1)  fn_reverse_inverse_crc[i]    = ~crc[15-i];
end     
endfunction

always@(negedge ireset or posedge cp2)
begin:state_machines_seq
if(!ireset)// Reset
begin
crc_current <= {16{1'b1}}; <<<<<<<<<

[thermit]

Dima_G:
Хоть в коде и написано что CCITT ( == 1021), но при проверке тестовых значений на онлайн калькуляторах CRC - не совпадает sad.gif
Пробовал сравнивать с иными полиномами - тоже безуспешно.
Железяка защищает этой CRC данные по HDLC

Может кто-нибудь сталкивался и сможет помочь?

Полином правильный, табличка с алгоритмом - тоже. Инициализация регистра - 0xFFFF. В качестве CRC берется поразрядная инверсия последнего содержимого регистра. СRC посылается начиная с младшего байта. При проверке байты crc тоже обрабатываются в порядке поступления байт. Если пакет корректный - регистр должен всегда содержать константу 0xF0B8. CRC можно и не обрабатывать, но тогда придется поразрядно инвертировать последнее содержимое регистра, переставлять байты и сравнивать полученное значение с пришедшим CRC.

Сообщение отредактировал thermit - Aug 17 2011, 09:25

[Dima_G]

Полином правильный, табличка с алгоритмом - тоже. Инициализация регистра - 0xFFFF. В качестве CRC берется поразрядная инверсия последнего содержимого регистра. СRC посылается начиная с младшего байта. При проверке байты crc тоже обрабатываются в порядке поступления байт. Если пакет корректный - регистр должен всегда содержать константу 0xF0B8. CRC можно и не обрабатывать, но тогда придется поразрядно инвертировать последнее содержимое регистра, переставлять байты и сравнивать полученное значение с пришедшим CRC.

Что-то у меня не получается.. Загоняю в функцию из первого поста 1 байт данных 0x30;
Начальное значение FFFF. crc=0x5EC4
Начальное значение 0000. crc=0x29b3

Если Вам не трудно, покажите на калькуляторе ту же CRC
http://zorc.breitbandkatze.de/crc.html
(где стоят галки, какие поля чем заполняли)

[thermit]

Вот

Эскизы прикрепленных изображений

 

[Dima_G]

Вот

что-то у меня не получилось для моих данных (0х30)

[thermit]

Все нормально получается. У Вас-то что выходит?

[Dima_G]

Все нормально получается. У Вас-то что выходит?

Используя функцию из первого поста: 0x5EC4
Используя калькулятор с вашими настройками 0x3E04
5EC4 != 3E04

Или я что-то не так понимаю?

[thermit]

Табличка какая-то левая.
У меня такая:

Код

        0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
    0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
    0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
    0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
    0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
    0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
    0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
    0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
    0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
    0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
    0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
    0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
    0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
    0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
    0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
    0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
    0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
    0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
    0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
    0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
    0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
    0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
    0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
    0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
    0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
    0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
    0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
    0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
    0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
    0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
    0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
    0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78

[Dima_G]

Табличка какая-то левая.
У меня такая:

Ага, ясно. Я такую тоже встречал - начинает отличаться с третьей строчки...
А поиском по строчке из моей таблицы выдает всего пару исходников (причем, похоже что родственных).
Похоже, не судьба полином подобрать будет
Спасибо всем, кто старался помочь!

[MrYuran]

Табличку можно самому сформировать для любого полинома.
Чтобы не было недоразумений.

[Ixt]

Нужно восстановить полином (для реализации его в FPGA) по следующему алгоритму расчета CRC16

Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.

[Dima_G]

Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.

http://electronix.ru/forum/index.php?showt...st&p=962810

В принципе, пока из положения вышел (ПЗУ в FPGA + расчет аналогичный как в плате), но ИМХО это не сильно красиво да и свои минусы есть (либо создавать по инстансу ПЗУ для каждого контроллера (а их десятки будут, те затраты Nx256*2), либо продумывать разделение доступа к одному

[MrYuran]

Так может проще не искать полином? Просто зашейте эту таблицу в FPGA.

Ага, а потом сравните затраты на полкило таблицы и один 16р сдвиговый регистр с обратными связями.
К тому же, как оказалось, таблица неправильная.

[Dima_G]

К тому же, как оказалось, таблица неправильная.

В том то и беда, что неправильная. Девайс генерит CRC именно по этой, неправильной таблице. А вносить изменения в девайс пока нет ни времени, ни возможности.

[MrYuran]

В том то и беда, что неправильная. Девайс генерит CRC именно по этой, неправильной таблице. А вносить изменения в девайс пока нет ни времени, ни возможности.

Значит, это уже не ЦРЦ, а чертечто. Можно ещё граблей наловить.

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

[Dima_G]

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

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

[i-mir]

Проблема в том что ваши таблицы не простые, а разбиты по блокам из 16 значений,
для которых есть свое число инициализации. Например таблица из поста 17:

- Для первых 16 значений [0x0000, 0x1189, 0x2312 ... ] CRC poly : $1189 CRC init: $0000
- Для вторых 16 значений [0x1081, 0x0108, 0x3393 ... ] CRC poly : $1189 CRC init: $5DEF
- Для третьих 16 значений [0x2102, 0x308b, 0x0210 ... ] CRC poly : $1189 CRC init: $BBDE

Честно говоря сам полином и числа инициализации выбраны не стандартные.

Можно проверить и на калькуляторе, для числа $10, CRC poly : $1189 CRC init: $5DEF
результат будет 0x1081 (по таблице).