提高CRC16计算速度

Question

我需要计算CRC16校验以$ 1021多项式过大的文件，下面是我目前的实现，但它是相当缓慢的大文件（例如，一个90 MB的文件需时约9秒）。

所以我的问题是如何提高我目前的执行情况（使其更快），我用Google搜索，看着执行表查找一些样品，但我的问题是，我不知道如何对它们进行修改，以包括多项式（可能是我的数学失败）。

{ 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

查找从绝地代码库的jclMath.pas单元CRC例程。它使用CRC的查找表。

http://jcl.svn.sourceforge.net / viewvc / JCL /中继/ JCL /源/普通/

Answer 2

如果你想这是快，你需要实现查表CRC算法。

请参阅无痛GUIDE TO CRC检错算法INDEX V3.00的第10章（9 / 24/96）

Answer 3

您Result变量是一个Word，这意味着有64K其可以具有在进入内循环可能的值。计算64K可能的结果是，循环可以产生并存储在一个数组。然后，代替循环八次输入缓冲器的每一个字节，简单地查找该阵列中的校验和的下一个值。是这样的：

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;

这代码重新计算查询表的任何时间Polynom变化。如果该参数的设定值各不相同，则考虑缓存你为他们生成的查找表，所以你不要浪费时间重复计算相同的表。

如果Polynom会的总是的为$ 1021那么甚至不打扰有它的参数。提前计算和大阵列他们硬编码的所有64K值，所以你的整个功能被减少到了最后三行我上面的功能。

Answer 4

旧螺纹，我知道。下面是我的实现（只是一个循环）：

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;

好处是还可以使用它创建一个唯一的ID，例如获得一个唯一的标识符输入一个文件名，如：

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

干杯， 欧文Haantjes