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 アルゴリズムを実装する必要があります。

A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS INDEX V3.00 (9/24/96) の 第 10 章を参照してください。

于 2010-09-28T07:40:55.223 に答える
2

Jedi コード ライブラリの jclMath.pas ユニットから CRC ルーチンを探します。CRC ルックアップ テーブルを使用します。

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

于 2010-09-28T07:54:20.870 に答える
2

変数Resultは ですWord。つまり、内側のループに入るときに 64k の可能な値が存在する可能性があります。ループが生成できる 64k の可能な結果を​​計算し、それらを配列に格納します。次に、入力バッファーの各バイトに対して 8 回ループする代わりに、配列内のチェックサムの次の値を検索するだけです。このようなもの：

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。そのパラメーターが一連の値の間で変化する場合は、同じテーブルを繰り返し計算して時間を無駄にしないように、生成したルックアップ テーブルをキャッシュすることを検討してください。

常に$1021 の場合Polynomは、パラメータを設定する必要さえありません。事前に 64k の値をすべて計算し、それらを大きな配列にハードコーディングして、関数全体を上記の関数の最後の 3 行だけに減らします。

于 2010-09-28T07:51:29.457 に答える
1

古いスレッド、知っています。これが私の実装です（ループは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 に答える