2

我需要在大文件上使用 1021 美元的多项式计算 Crc16 校验和，下面是我当前的实现，但它在大文件上相当慢（例如，90 MB 文件大约需要 9 秒）。

所以我的问题是如何改进我当前的实现（使其更快），我用谷歌搜索并查看了一些实现表查找的示例，但我的问题是我不明白如何修改它们以包含多项式（可能是我的数学失败）。

{ 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;
4

4 回答 4

6

如果你想让这个速度更快，你需要实现一个查表 CRC 算法。

请参阅CRC 错误检测算法索引 V3.00 (9/24/96) 的无痛指南 第 10 章

于 2010-09-28T07:40:55.223 回答
2

您的Result变量是 a 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 值并将它们硬编码到一个大数组中，这样你的整个函数就减少到上面我函数的最后三行。

于 2010-09-28T07:51:29.457 回答
2

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

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

于 2010-09-28T07:54:20.870 回答
1

老线程，我知道。这是我的实现（只有一个循环）：

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;

干杯，欧文·汉杰斯

于 2011-11-03T15:55:03.750 回答