Расчет CRC16 для Modbus

@Sharpix · Регистрация: 07.10.2013

Author24 — интернет-сервис помощи студентам

Здравствуйте.
Пишу расчет CRC16 для Modbus по описанию: http://piclist.ru/S-CRC16-RUS/CRC16.html
1. В регистр CRC заносится начальное значение FFFFh.
2. В конец сообщения добавляется 16 нулевых битов.
3. Содержимое регистра сдвигается влево на 1 бит, и в последнюю (нулевую) позицию заносится очередной, ещё не обработанный бит данных.
4. Если из регистра был выдвинут бит со значением "1", то содержимое регистра комбинируется по XOR с полиномом 8005h. Если значение бита равно "0", XOR не выполняется.
5. Шаги 3 и 4 выполняются, пока не будут обработаны все данные.
6. Окончательное содержимое регистра комбинируется по XOR со значением FFFFh.

Вроде алгоритм работает, но результат не совпадает с верным. Расчитываю CRC16 для пакета 6 байт, результат должен быть 14988($3A8C), у меня получается 14014. В чем ошибка? Или может быть, описание алгоритма не совсем точное?

@Sharpix · 17.09.2017, 12:06 **[ТС]**

Тема еще актуальна.
Решил взять другой, табличный метод расчёта CRC16 из того же источника. Там есть пример на Си, перевёл на Паскаль расчёт таблицы, возник один нюанс. Для полинома $1021 этот код работает верно, а для $8005, согласно Википедии есть 2 флага, RefIn и RefOut, оба имеют значение True. Где это нужно учитывать в расчётах?

Delphi

// создание таблицы
procedure TForm1.Button2Click(Sender: TObject);
var
  i, j: byte;
  r: word;
 
begin
  for i := 0 to 255 do
  begin
    r := i;
    r := r shl 8;
    for j := 0 to 7 do
    begin
      if r and (1 shl 15) <> 0 then
        r := (r shl 1) xor $8005
      else
        r := r shl 1;
    end;
 
    Memo1.Lines.Append(IntToStr(r));
  end;
end;

@Animalia · 17.09.2017, 15:59

В свое время нарытый в интернете код

Кликните здесь для просмотра всего текста

Delphi

function Reflect(inp: Cardinal): Cardinal;
var
  i: byte;
begin
  Result := 0;
  for i := 0 to 15 do
  begin
    Result := (Result shl 1) or (inp and $0001);
    inp := inp shr 1;
  end;
end;
 
function CRC16(Buffer: String; Polynom, Initial: Cardinal): Cardinal;
var
  i, j: Integer;
begin
  Result := Initial;
  for i := 1 to Length(Buffer) do
  begin
    Result := Result xor (ord(Buffer[i]) shl 8);
    for j := 0 to 7 do
      if (Result and $8000) <> 0 then
        Result := (Result shl 1) xor Polynom
      else
        Result := Result shl 1;
  end;
  Result := Result and $FFFF;
end;
 
function CRC16Reverse(Buffer: String; Polynom, Initial: Cardinal): Cardinal;
var
  i, j: Integer;
begin
  Result := Initial;
  for i := 1 to Length(Buffer) do
  begin
    Result := Result xor ord(Buffer[i]);
    for j := 0 to 7 do
      if (Result and $0001) <> 0 then
        Result := (Result shr 1) xor Polynom
      else
        Result := Result shr 1;
  end;
end;

При вызове CRC16Reverse полином надо отразить при помощи Reflect.
Работает правда медленнее табличных вариантов, но за то правильно, по крайней мере с викой совпадает

@Sharpix · 19.09.2017, 15:22 **[ТС]**

Спасибо, да, этот код работает, результат совпадает. Но всё-таки хотелось бы написать свой алгоритм, хотя бы для практики написания алгоритмов вообще и CRC, в частности.
Так что построение таблицы всё ещё актуально. Вот написал свою функцию инвертирования порядка бит, проверял отдельно - работает верно.
Согласно Википедии должно быть так:
-начало и направление вычислений: начиная с младшего значащего бита;
-порядок битов регистра инвертируется при входе на элемент XOR.

Кликните здесь для просмотра всего текста

Delphi

// Построение таблицы
procedure TForm1.Button2Click(Sender: TObject);
var
  i, j: byte;
  r: word;
 
function invert(input: word): word;  // инвертирование порядка бит
var
  i,j: byte;
  array1: array[0..15] of byte;
  x: word;
begin
  x := 0;
 
  for i := 0 to 15 do
  begin
    if input and (1 shl 15) <> 0 then  // массив заполняется 16-битным input
      array1[i] := 1                   // 0-й элемент - старший бит
    else
      array1[i] := 0;
 
    input := input shl 1;
  end;
 
  for j := 15 downto 0 do
  begin
    if array1[j] = 1 then
      x := x or 1;
 
    if j <> 0 then
      x := x shl 1;
  end;
 
  result := x;
end;
 
begin
  for i := 0 to 255 do
  begin
    r := i;
    r := r shl 8;  // здесь
    for j := 0 to 7 do
    begin
      if r and (1 shl 15) <> 0 then
        r := (r shl 1) xor $8005  // и здесь
      else
        r := r shl 1;
    end;
 
    Memo1.Lines.Append(IntToStr(r));
  end;
end;

Пробовал и там и там и вместе и по отдельности - результат неудовлетворительный.
Начало таблицы должно быть таким:
0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,...
Куда же подставлять функцию invert?

@Animalia · 19.09.2017, 17:40

Я как-бы тоже не сидел без дела, и нашел сайт с которого утащил тот код

CRC calculations - там и табличный вариант есть, а еще CRC8 и CRC32 (да и вообще калькулятор интерестный)
Таблица по идее глобальна - ее размер всего-то 1кб, ну разве что при каждом новом ключе ее надо будет пересчитать.

По поводу инверсии на пальцах сложно обьяснить, да и не математик я. Но как я понимаю, для инверсного варианта мы обращаем полином и меняем направление просмотра бит в сообщении. Само сообщение переворачивать в таком случае не требуется.

Delphi

// было
if (Result and $8000)<>0 then Result:=(Result shl 1) xor Polynom
// стало
if (Result and $0001)<>0 then Result:=(Result shr 1) xor Polynom

Хотя повторюсь - это мое понимание, и если кто поправит и обьяснит толковее я только за.

@Sharpix · 21.09.2017, 15:27 **[ТС]**

Нашёл в чём загвоздка. В Википедии приведена методика Ross N. Williams, а я использую какую-то другую методику. Много их, оказывается. Т. е. функцию invert надо подставлять не туда, куда я пробовал. Но, думаю, дело всё-таки в инверсии порядка бит в определённом месте вычислений.

Сообщение от Animalia

да и не математик я

Спасибо за наводку, мне действительно сейчас нужна помощь математиков или криптографов.

@Sandmansss · 03.09.2019, 12:21

Я конечно некропостер, но бился и подобной проблемой, правда для расчета CRC8.

Вот мое рабочее решение.
Ниже приведены функции прямого и реверсного расчета.
В данные функции как параметр передаются массив байт а не строка.

Pascal

/////////////////////////////////////////////////////////////////////////////
//Прямой расчет CRC
function TfrmMain.CRC8(const dar:array of byte): word;
  var
    Value: Byte;
    i, j: Integer;
  begin
    Result:=0;
    Value:=$07;
    for i:=0 to High(dar) do
      begin
        Value:= Value xor Ord(Dar[i]) ;
        for j:= 1 to 8 do
          begin
            if (Value and $80) <> 0 then
              Value:=((Value shl 1) xor $A)
            else
              Value:=(Value shl 1);
          end;
      end;
 
    Result:=Value;
  end;
 
/////////////////////////////////////////////////////////////////////////////
//Реверс расчет CRC
function TfrmMain.CRC8_Reverse(const dar:array of byte): word;
  var
    Value: Byte;
    i, j: Integer;
  begin
    Result:=0;
    Value:=ByteReverseLoop($07);
    for i:=0 to High(dar) do
      begin
        Value:= Value xor Ord(Dar[i]);
        for j:=1 to 8 do
          begin
            if (Value and $01) <> 0 then
              Value:=(Value shr 1) xor ByteReverseLoop($A)
            else
              Value:=(Value shr 1);
          end;
      end;
    Result:=Value;
  end;
/////////////////////////////////////////////////////////////////////////////
// Реверс Byte
function TfrmMain.ByteReverseLoop(b: byte): byte;
  var i: integer;
  begin
    Result:= 0;
    for i:= 1 to 8 do
      begin
        Result:= Result shl 1;
        if Odd(b) then Result:=Result or 1;
        b:=b shr 1;
      end;
  end;
/////////////////////////////////////////////////////////////////////////////

Добавлено через 10 минут
До кучи, если кому понадобится.

Pascal

/////////////////////////////////////////////////////////////////////////////
//Перевод строки в массив байт
 
function TfrmMain.Str2ByteArray(S: String):ArrayOfByte;
  var
    iLenghS, i, n: integer;
    StrByte, sTemp: string;
  begin
    StrByte:=AnsiUpperCase(Trim(StringReplace(S,' ','',[rfReplaceAll])));
    iLenghS:=Length(StrByte);
 
    if (iLenghS mod 2) <> 0 then
      begin
        sTemp:=StrByte[iLenghS];
        StrByte[iLenghS]:='0';
        StrByte:=StrByte + sTemp;
        iLenghS:=iLenghS+1;
      end;
      SetLength(Result, (iLenghS div 2));
 
      n:=0;
      for i:=1 to iLenghS do
        begin
          if not((i mod 2)=0) then
            begin
              sTemp:=StrByte[i] + StrByte[i+1];
              Result[n]:=Str2Byte(sTemp);
              n:=n+1;
            end;
        end;
  end;
/////////////////////////////////////////////////////////////////////////////
//Перевод строки в байт
 
function TfrmMain.Str2Byte(S : String):Byte;
  const C:string[16]='0123456789ABCDEF';
  begin
    if Length(S) < 2 then
      Result := Pos(S, C) - 1
   else
      Result := (Pos(S[1], C) - 1)*16 + Pos(S[2], C)-1
  end;

@Sharpix 6 / 6 / 0 Регистрация: 07.10.2013 Сообщений: 96
	21.09.2017, 15:27 [ТС]	6
	Нашёл в чём загвоздка. В Википедии приведена методика Ross N. Williams, а я использую какую-то другую методику. Много их, оказывается. Т. е. функцию invert надо подставлять не туда, куда я пробовал. Но, думаю, дело всё-таки в инверсии порядка бит в определённом месте вычислений. Сообщение от Animalia да и не математик я Спасибо за наводку, мне действительно сейчас нужна помощь математиков или криптографов. 0

	03.09.2019, 12:21