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;
Advertisements

2 thoughts on “Notes on bitwise CRC32

  1. Seems to be inefficient to make Dividend by Concatenating 3 arrays together, would it be more efficient to do them “incrementally”?? Like streaming each buffer in own part (If other code supports it)

    If there is lot of data the Reallocation would be quite expensive operation..

    • The code just shows how to calculate the standard CRC32 using polynomial division and is not optimized at all. For example first 32 iterations of PolyModRevers just move first 32 bits of the dividend into the work register in bit-reversed order. Optimizations do not make much sense because effective CRC implementations are table-based, working on whole bytes, not separate bits.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s