При вычислении CRC суммы обычно используется lookup таблица, чтобы ускорить вычисление.
Я задумал вычислять эту таблицу (а не задавать на этапе написания кода в виде констант).
Нашел такую ссылку:
http://www.piclist.ru/S-CRC16-RUS/CRC16.html
Где описана функция для заполнения lookup таблицы.
Заимплементил эту фунцкию.
Однако.
Согласно данным из википедии

В секции "Пример программы табличного (быстрого) расчёта CRC-16 CCITT на языке Си " для полинома
Poly : 0x1021 x^16 + x^12 + x^5 + 1
таблица получается такая:

const unsigned short Crc16Table[256] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,

Я привожу начало таблицы, она именно такая у меня и вычисляется.

А вот в секции "Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си" для полинома:
Poly : 0x8005 x^16 + x^15 + x^2 + 1
таблица должна быть:

const unsigned short Crc16Table[256] = {
    0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,

У меня же начало таблицы выглядит так

  0x0000, 0x8005, 0x800F ....

Причем, в силу особенностей приведенной функции для вычисления таблицы, второй элемент в таблице всегда должен быть равен полиному (в данном случае 0x8005), потому я в принципе не понимаю, почему же в примере из википелии второй элемент таблицы равен 0xC0C1. CRC, выполненное по моей таблице, не принимается устройством, а вычисленное по таблице из википедии — принимается.
При всем при этом для полинома 0x1021 таблица вычисляется правильно.
Правда, для полинома 8005 в википедии написано "Revert: true", но куда мне это приткнуть, я не понимаю...


Собственно вопрос — как же вычислить lookup таблицу для быстрого вычисления CRC16 с полиномом 8005?

Здравствуйте, dlk, Вы писали:

dlk>А вот в секции "Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си" для полинома:
dlk> Poly : 0x8005 x^16 + x^15 + x^2 + 1
dlk>таблица должна быть:
dlk>

dlk>const unsigned short Crc16Table[256] = {
dlk>    0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
dlk>

dlk>У меня же начало таблицы выглядит так
dlk>

dlk>  0x0000, 0x8005, 0x800F ....
dlk>

dlk>Причем, в силу особенностей приведенной функции для вычисления таблицы, второй элемент в таблице всегда должен быть равен полиному (в данном случае 0x8005), потому я в принципе не понимаю, почему же в примере из википелии второй элемент таблицы равен 0xC0C1. CRC, выполненное по моей таблице, не принимается устройством, а вычисленное по таблице из википедии — принимается.

Скорее всего разница в том, что в википедии названо RefIn. Для линий связи принято начинать с младшего бита.

dlk>При всем при этом для полинома 0x1021 таблица вычисляется правильно.
dlk>Правда, для полинома 8005 в википедии написано "Revert: true", но куда мне это приткнуть, я не понимаю...

В программу, вестимо.:)) Или сдвигать влево и брать самый левый до сдвига, или сдвигать вправо и брать младший бит.

Здравствуйте, netch80, Вы писали:

N>Скорее всего разница в том, что в википедии названо RefIn. Для линий связи принято начинать с младшего бита.
N>В программу, вестимо. Или сдвигать влево и брать самый левый до сдвига, или сдвигать вправо и брать младший бит.

Спасибо, Вы правы
Вот работающий алгоритм на паскале, для
Name : CRC 16
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D

procedure TCrc16Calculator.Init(Polynomial: word);
var
  I, r: word;
  j: byte;
begin
  for I:= 0 to 255 do
  begin
    r:= I;
    for j:= 0 to 7 do
    begin
      if (r AND $0001) = $0001 then
        r:= (r shr 1) xor Polynomial
      else
        r:= r shr 1;
    end;
    FCrcTable[I]:= r;
  end;
end;

type
  TByteArray = packed array[1..(MaxInt-1)] of byte;
  PByteArray = ^TByteArray;

function TCrc16Calculator.calcCrc(Data: Pointer; DataSize: Integer): word;
var
  DataPtr: PByteArray;
  I: Integer;
  idx: Integer;
begin
  DataPtr:= Data;
  Result:= 0;
  for I:= 1 to DataSize do
  begin
    Idx:= ((Result and $FF) xor DataPtr^[I]);
    Result:= FCrcTable[Idx] xor (Result shr 8);
  end;
end;

procedure testStdSequence();
var
  calc: TCrc16Calculator;
  arr: string;
begin
  arr:= '123456789';
  calc:= TCrc16Calculator.Create($A001);//$A001 == реверсированное $8005
  Assert(calc.calcCrc(@arr[1], 9) = $BB3D);
end;