改善速Crc16計算

Question

かを計算する必要がありCrc16チェックサムと$1021polynom以上の大きなファイルで、以下では私の現在の実装では遅いの大きなファイル(例えば90MBのファイル約9秒)があります。

その後、私の問題は、これらの改善に私の現在の実装(で)私ンターネットで調べたものサンプルの実施テーブルのルックアップが私の問題はいかに修正するのpolynom(おそらく私の数学が不合格）.

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

A無痛GUIDE TO CRCエラー検出ALGORITHMS INDEX V3.00の章10を参照してください（9 / 24/95） の

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;

このコードrecalculatesのルックアップテーブル他 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