Any CRC algorithm

TForge 0.73 is released.

The theme of the release is implementing any CRC algorithm of size up to 64 bits. New TCRC class implements Rocksoft™ Model of CRC algorithms using one-bit-at-a-time CRC calculation; the details will be published on the related project’s wiki page.

Notes on bitwise CRC32

CRC algorithms calculate remainder from division of a message polynomial by a generator polynomial over GF(2) field. There are many explanations how it works (see wikipedia for example), but there are also practical details omitted that you should care about if you want to obtain an implementation compatible with the standard table implementation.

The standard CRC32 implementation uses reversed bit ordering; in code it means right shifts instead of left shifts. The CRC32-compatible polynomial division implementation is

function PolyModRevers(const Dividend: ByteArray; G: LongWord): LongWord;
var
  I, L: Cardinal;
  P: PByte;
  B: Byte;
  Carry: Boolean;

begin
  L:= Dividend.Len;
  Result:= 0;
  P:= Dividend.RawData;
  while L > 0 do begin
    B:= P^;
    Inc(P);
// push B through the Result register
    I:= 8;
    repeat
      Carry:= Odd(Result);
      Result:= Result shr 1;
      if Odd(B) then
        Result:= Result or $80000000;
      B:= B shr 1;
      if Carry then Result:= Result xor G;
      Dec(I);
    until I = 0;
    Dec(L);
  end;
end;

The function calculates remainder from division by a generator polynomial G. A generator is stored as 32-bit value; actually a generator for CRC32 algorithms is a 33-bit value, but the senior bit is always 1 and so can be omitted and used implicitly. Since the function uses reverse bit ordering in dividend polynomial, the generator polynomial should also be bit-reversed (for the standard CRC32 algorithm the bit-reversed generator is 0xEDB88320).

The dividend for a general CRC32 algorithm is obtained by appending a message with 4 zero bytes and optionally prefixing with some byte sequence. I did not find the prefix for standard CRC32 algorithm using Google, and calculated it by using brute force:

procedure Find;
var
  Dividend: ByteArray;
  N, R: LongWord;

begin
  N:= 0;
  repeat
    Dividend:= ByteArray.FromInt(N, SizeOf(N), True) + ByteArray.Allocate(4, 0);
    R:= PolyModRevers(Dividend, $EDB88320);
    if R = $FFFFFFFF then begin
      Writeln('N: ', Dividend.ToHex);
      Exit;
    end;
    Inc(N);
    if N and $ffffff = 0 then writeln(n);
  until N = 0;
  Writeln('Failed');
end;

The function takes time to obtain the result, so it outputs some values during the search; the final result is funny magic number $62F52692.

Putting it all together, the bitwise CRC32 code compatible with reference table implementation is:

function CalcBitCRC32(const Msg: ByteArray): LongWord;
var
  Dividend: ByteArray;
  Prefix: LongWord;

begin
  Prefix:= $62F52692;
  Dividend:= ByteArray.FromInt(Prefix, SizeOf(Prefix), True) + Msg + ByteArray.Allocate(4, 0);
  Result:= not PolyModRevers(Dividend, $EDB88320);
end;