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

---

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

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

Алгоритм получения 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

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

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

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

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