Улучшить скорость при расчете Crc16 - PullRequest
Новая
       10

Улучшить скорость при расчете Crc16

2 голосов
/ 28 сентября 2010

Мне нужно вычислить контрольные суммы Crc16 с полиномом $ 1021 для больших файлов, ниже приведена моя текущая реализация, но она довольно медленна для больших файлов (например, файл размером 90 МБ занимает около 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 ]

6 голосов
/ 28 сентября 2010

Если вы хотите, чтобы это было быстро, вам нужно реализовать алгоритм CRC для поиска в таблице.

См. Главу 10 из РУКОВОДСТВО ПО БЕЗ БЕЗОПАСНОСТИ К ИНДЕКСУ АЛГОРИТМОВ ОБНАРУЖЕНИЯ ОШИБОК CRC V3.00 (9 /24/96)

2 голосов
/ 28 сентября 2010

Ищите подпрограммы CRC из модуля jclMath.pas библиотеки кодов джедаев.Он использует таблицы поиска CRC.

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

2 голосов
/ 28 сентября 2010

Ваша переменная Result является Word, что означает, что существует 64 000 возможных значений, которые она может иметь при входе во внутренний цикл. Рассчитайте 64 тыс. Возможных результатов, которые цикл может генерировать, и сохраните их в массиве. Затем вместо восьми циклов для каждого байта входного буфера просто ищите следующее значение контрольной суммы в массиве. Примерно так: 

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, то даже не беспокойтесь о параметре для него. Вычислите все значения 64 КБ заранее и жестко закодируйте их в большом массиве, чтобы вся ваша функция была сокращена до последних трех строк моей функции выше.

1 голос
/ 03 ноября 2011

Старая тема, я знаю. Вот моя реализация (всего один цикл): 

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;

Приятно то, что вы можете создать уникальный идентификатор с ним, например, чтобы получить уникальный идентификатор для имени файла, например: 

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

Ура, Эрвин Хаантес

...