Improve speed on Crc16 calculation

Question

I need to calculate Crc16 checksums with a $1021 polynom over large files, below is my current implementation but it's rather slow on large files (eg a 90 MB file takes about 9 seconds).

So my question is how to improve my current implementation (to make it faster), I have googled and looked at some samples implementing a table lookup but my problem is that I don't understand how to modify them to include the polynom (probably my math is failing).

{ based on http://miscel.dk/MiscEl/CRCcalculations.html }
function Crc16(const Buffer: PByte; const BufSize: Int64;
  const Polynom: WORD=$1021; const Seed: WORD=0): Word;
var
  i,j: Integer;
begin
  Result := Seed;

  for i:=0 to BufSize-1 do
  begin
    Result := Result xor (Buffer[i] shl 8);

    for j:=0 to 7 do begin
      if (Result and $8000) <> 0 then
        Result := (Result shl 1) xor Polynom
      else Result := Result shl 1;
    end;
  end;

  Result := Result and $FFFF;
end;

Answer 1

Old thread, i know. Here is my implementation (just one loop):

function crc16( s : string; bSumPos : Boolean = FALSE ) : Word;
var
 L, crc, sum, i, x, j : Word;

begin
  Result:=0;
  L:=length(s);
  if( L > 0 ) then
   begin
    crc:=$FFFF;
    sum:=length(s);
    for i:=1 to L do
    begin
            j:=ord(s[i]); 
            sum:=sum+((i) * j);
            x:=((crc shr 8) xor j) and $FF;
            x:=x xor (x shr 4);
            crc:=((crc shl 8) xor (x shl 12) xor (x shl 5) xor x) and $FFFF;
    end;
    Result:=crc+(Byte(bSumPos) * sum);
   end;
end;

Nice thing is also that you can create an unique id with it, for example to get an unique identifier for a filename, like:

function uniqueId( s : string ) : Word;
begin
 Result:=crc16( s, TRUE );
end;

Cheers, Erwin Haantjes

Answer 2

If you want this to be fast, you need to implement a table-lookup CRC algorithm.

See chapter 10 of A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS INDEX V3.00 (9/24/96)

Answer 3

Look for CRC routines from jclMath.pas unit of Jedi Code Library. It uses CRC lookup tables.

http://jcl.svn.sourceforge.net/viewvc/jcl/trunk/jcl/source/common/

Answer 4

Your Result variable is a Word, which means there are 64k possible values it could have upon entry to the inner loop. Calculate the 64k possible results that the loop could generate and store them in an array. Then, instead of looping eight times for each byte of the input buffer, simply look up the next value of the checksum in the array. Something like this:

function Crc16(const Buffer: PByte; const BufSize: Int64;
  const Polynom: Word = $1021; const Seed: Word = 0): Word;
{$J+}
const
  Results: array of Word = nil;
  OldPolynom: Word = 0;
{$J-}
var
  i, j: Integer;
begin
  if (Polynom <> OldPolynom) or not Assigned(Results) then begin
    SetLength(Results, 65535);
    for i := 0 to Pred(Length(Results)) do begin
      Results[i] := i;
      for j := 0 to 7 do
        if (Results[i] and $8000) <> 0 then
          Results[i] := (Results[i] shl 1) xor Polynom
        else
          Results[i] := Results[i] shl 1;
    end;
    OldPolynom := Polynom;
  end;

  Result := Seed;
  for i := 0 to Pred(BufSize) do
    Result := Results[Result xor (Buffer[i] shl 8)];
end;

That code recalculates the lookup table any time Polynom changes. If that parameter varies among a set of values, then consider caching the lookup tables you generate for them so you don't waste time calculating the same tables repeatedly.

If Polynom will always be $1021, then don't even bother having a parameter for it. Calculate all 64k values in advance and hard-code them in a big array, so your entire function is reduced to just the last three lines of my function above.