Версия для печати


Почти всё, что вы хотели узнать, но боялись спросить о Crc32

---

http://www.delphikingdom.com/asp/viewitem.asp?catalogID=422

Andrew Rybin
дата публикации 04-06-2001 00:00

Изначально цель методик обнаружения ошибок была в том, чтобы дать возможность получателю сообщения, передаваемому по зашумленному каналу, определить, не было ли оно испорчено. Для этого отправитель формировал значение, именуемое контрольной суммой ("checksum" - КС), как функцию от сообщения и добавлял его к сообщению, получатель, используя ту же самую функцию, мог посчитать КС полученного сообщения и в случае равенства, считать сообщение безошибочно принятым. Самый первый алгоритм подсчета КС был очень прост: все байты сообщения суммировались (отсюда и пошло название <контрольная сумма>) по модулю степени двойки. Главное достоинство этого метода - простота, главный недостаток - ненадежность. Например, он не <замечает> перестановки байт местами.

Высокую степень безопасности данных обеспечивают алгоритмы контроля за достоверностью информации, использующие циклические избыточные коды (Cyclic Redundancy Code - CRC).

Использование CRC представляет собой сверхмощный метод обнаружения ошибок.
Авторам изученной мной литературы ;-) известны три различных теоретических аспекта расчета CRC, приводящих на практике к идентичным результатам:

• матричная запись циклического кода,
• метод деления на образующий полином над полем GF(2) и
• способ образования CRC с помощью регистра сдвига с обратными связями.

Именно последний способ удобен с вычислительной точки зрения - особенно если разрядность компьютера равна (или кратна) длине сдвигового регистра.

Для простоты считайте CRC остатком от деления БОЛЬШОГО бинарного числа (передаваемых данных) на <магическое> число, в зависимости от разряда старшего бита этого числа выделяют CRC16 и CRC32.

Теория этого дела весьма обширна и хорошо описана в литературе, но думаю, большинство читателей этой статьи гораздо больше волнует её практическая реализация.

Алгоритм получения CRC32 такой:

1. 1. CRC-32 инициализируется значением $FFFFFFFF
2. 2. Для каждого байта "B" входной последовательности CRC-32 сдвигается вправо на 1 байт. Если байты CRC-32 были [C1,C2,C3,C4] (C1 - старший, C4 - младший), сдвиг дает [0,C1,C2,C3]. Младший байт C4 побитно складывается с B по модулю 2 (C4 xor B). Новым значением CRC-32 будет его сдвинутое значение, сложенное побитно по модулю 2 (xor) с 4-байтовой величиной из "магической" таблицы с использованием [B xor C4] в качестве индекса.

   Было:
     CRC-32 = [C1,C2,C3,C4] и получили очередной байт B.
   
   Стало:
     CRC-32 = [0,C1,C2,C3] xor Magic[B xor C4].
   
     PAS: { CRC - LongWord, Magic - array[byte] of LongWord}
     CRC := (CRC shr 8) xor Magic[B xor byte(CRC and $FF)];
   

3. 3. Инвертировать все биты: CRC:= NOT CRC;

Код на паскале:-)

Const
  Crc32Init = $FFFFFFFF;
  Crc32Polynomial = $EDB88320;

Var
  CRC32Table: array [Byte] of Cardinal;


function  Crc32Next   (Crc32Current: LongWord; const Data; Count: LongWord):
LongWord; register;
Asm file://EAX - CRC32Current; EDX - Data; ECX - Count
  test  ecx, ecx
  jz    @@EXIT
  PUSH  ESI
  MOV   ESI, EDX  file://Data

@@Loop:
    MOV EDX, EAX                       // copy CRC into EDX
    LODSB                              // load next byte into AL
    XOR EDX, EAX                       // put array index into DL
    SHR EAX, 8                         // shift CRC one byte right
    SHL EDX, 2                         // correct EDX (*4 - index in array)
    XOR EAX, DWORD PTR CRC32Table[EDX] // calculate next CRC value
  dec   ECX
  JNZ   @@Loop                         // LOOP @@Loop
  POP   ESI
@@EXIT:
End;//Crc32Next

function  Crc32Done   (Crc32: LongWord): LongWord; register;
Asm
  NOT   EAX
End;//Crc32Done

<Магическую> таблицу можно хранить в исполняемом файле, но мы, как настоящие программисты, будем формировать её в run-time:

function  Crc32Initialization: Pointer;
Asm
  push    EDI
  STD
  mov     edi, OFFSET CRC32Table+ ($400-4)  // Last DWORD of the array
  mov     edx, $FF  // array size

@im0:
  mov     eax, edx  // array index
  mov     ecx, 8
@im1:
  shr     eax, 1
  jnc     @Bit0
  xor     eax, Crc32Polynomial  // <магическое> число - тоже что у
ZIP,ARJ,RAR,:
@Bit0:
  dec     ECX
  jnz     @im1

  stosd
  dec     edx
  jns     @im0

  CLD
  pop     EDI
  mov     eax, OFFSET CRC32Table
End;//Crc32Initialization

Для удобной работы добавим функцию подсчета Crc32 для Stream'a:

function  Crc32Stream (Source: TStream; Count: Longint): LongWord;
var
  BufSize, N: Integer;
  Buffer: PChar;
Begin
  Result:=Crc32Init;
  if Count = 0 then begin
    Source.Position:= 0;
    Count:= Source.Size;
  end;

  if Count > IcsPlusIoPageSize then BufSize:= IcsPlusIoPageSize else
BufSize:= Count;
  GetMem(Buffer, BufSize);
  try
    while Count <> 0 do begin
      if Count > BufSize then N := BufSize else N := Count;
      Source.ReadBuffer(Buffer^, N);
      Result:=Crc32Next(Result,Buffer^,N);
      Dec(Count, N);
    end;
  finally
    Result:=Crc32Done(Result);
    FreeMem(Buffer);
  end;
End;//Crc32Stream

Получаемый на выходе CRC32 совпадает с генерируемым такими программами как PkZip, ARJ, RAR и многими другими.

И, конечно, тестовая программка:

program Crc32;
{$APPTYPE CONSOLE}
uses
  SysUtils,Classes,IcsPlus;

var
  FS: TFileStream;
  Crc: LongWord;

Begin
  if ParamCount<>1 then begin
    WriteLn('Crc32 v1.0  Copyright (c) 2001 by Andrew P.Rybin
[magicode@mail.ru]');
    WriteLn('  Usage: crc32 filename');
    EXIT;
  end;

  Crc32Initialization;
  FS:= TFileStream.Create(ParamStr(1),fmOpenRead);
  try
    Crc:=Crc32Stream(FS,0);
    WriteLn('Crc: ',IntToHex(Crc,8),' = ',Crc);
  finally
    FS.FREE;
  end;
End.

В файле IcsPlus_.zip содержится используемый мною в работе модуль IcsPlus.pas, который включает вышеописанные функции, и тестовая программка. Автор будет признателен за возможные советы, пожелания и bugfix'ы.

Andrew P.Rybin
Специально для Королевства Delphi