Статьи Королевства Дельфи

Изначально цель методик обнаружения ошибок


Раздел Подземелье Магов


Изначально цель методик обнаружения ошибок была в том, чтобы дать возможность получателю сообщения, передаваемому по зашумленному каналу, определить, не было ли оно испорчено. Для этого отправитель формировал значение, именуемое контрольной суммой ("checksum" - КС), как функцию от сообщения и добавлял его к сообщению, получатель, используя ту же самую функцию, мог посчитать КС полученного сообщения и в случае равенства, считать сообщение безошибочно принятым. Самый первый алгоритм подсчета КС был очень прост: все байты сообщения суммировались (отсюда и пошло название ) по модулю степени двойки. Главное достоинство этого метода - простота, главный недостаток - ненадежность. Например, он не перестановки байт местами.

Высокую степень безопасности данных обеспечивают алгоритмы контроля за достоверностью информации, использующие циклические избыточные коды (Cyclic Redundancy Code - CRC).

Использование CRC представляет собой сверхмощный метод обнаружения ошибок.
кода,
  • метод деления на образующий полином над полем GF(2) и
  • способ образования CRC с помощью регистра сдвига с обратными связями.
    • Именно последний способ удобен с вычислительной точки зрения - особенно если разрядность компьютера равна (или кратна) длине сдвигового регистра.

    Для простоты считайте CRC остатком от деления БОЛЬШОГО бинарного числа (передаваемых данных) на число, в зависимости от разряда старшего бита этого числа выделяют CRC16 и CRC32.

    Теория этого дела весьма обширна и хорошо описана в литературе, но думаю, большинство читателей этой статьи гораздо больше волнует её практическая реализация.

    Алгоритм получения CRC32 такой:

    1. 1. CRC-32 инициализируется значением $FFFFFFFF
    2. 2. Для каждого байта "B" входной последовательности CRC-32 сдвигается вправо на 1 байт. Если байты CRC-32 были [C1,C2,C3,C4] (C1 - старший, C4 - младший), сдвиг дает [0,C1,C2,C3]. Младший байт C4 побитно складывается с B по модулю 2 (C4 xor B). Новым значением CRC-32 будет его сдвинутое значение, сложенное побитно по модулю 2 (xor) с 4-байтовой величиной из "магической" таблицы с использованием [B xor C4] в качестве индекса. Было: CRC-32 = [C1,C2,C3,C4] и получили очередной байт B. Стало: CRC-32 = [0,C1,C2,C3] xor Magic[B xor C4]. PAS: { CRC - LongWord, Magic - array[byte] of LongWord} CRC := (CRC shr 8) xor Magic[B xor byte(CRC and $FF)];
    3. 3. Инвертировать все биты: CRC:= NOT CRC;
    Код на паскале:-) Const Crc32Init = $FFFFFFFF; Crc32Polynomial = $EDB88320; Var CRC32Table: array [Byte] of Cardinal; function Crc32Next (Crc32Current: LongWord; const Data; Count: LongWord): LongWord; register; Asm file://EAX - CRC32Current; EDX - Data; ECX - Count test ecx, ecx jz @@EXIT PUSH ESI MOV ESI, EDX file://Data @@Loop: MOV EDX, EAX // copy CRC into EDX LODSB // load next byte into AL XOR EDX, EAX // put array index into DL SHR EAX, 8 // shift CRC one byte right SHL EDX, 2 // correct EDX (*4 - index in array) XOR EAX, DWORD PTR CRC32Table[EDX] // calculate next CRC value dec ECX JNZ @@Loop // LOOP @@Loop POP ESI @@EXIT: End;//Crc32Next function Crc32Done (Crc32: LongWord): LongWord; register; Asm NOT EAX End;//Crc32Done <Магическую> таблицу можно хранить в исполняемом файле, но мы, как настоящие программисты, будем формировать её в run-time: function Crc32Initialization: Pointer; Asm push EDI STD mov edi, OFFSET CRC32Table+ ($400-4) // Last DWORD of the array mov edx, $FF // array size @im0: mov eax, edx // array index mov ecx, 8 @im1: shr eax, 1 jnc @Bit0 xor eax, Crc32Polynomial // число - тоже что у ZIP,ARJ,RAR,: @Bit0: dec ECX jnz @im1 stosd dec edx jns @im0 CLD pop EDI mov eax, OFFSET CRC32Table End;//Crc32Initialization Для удобной работы добавим функцию подсчета Crc32 для Stream'a: function Crc32Stream (Source: TStream; Count: Longint): LongWord; var BufSize, N: Integer; Buffer: PChar; Begin Result:=Crc32Init; if Count = 0 then begin Source.Position:= 0; Count:= Source.Size; end; if Count > IcsPlusIoPageSize then BufSize:= IcsPlusIoPageSize else BufSize:= Count; GetMem(Buffer, BufSize); try while Count <> 0 do begin if Count > BufSize then N := BufSize else N := Count; Source.ReadBuffer(Buffer^, N); Result:=Crc32Next(Result,Buffer^,N); Dec(Count, N); end; finally Result:=Crc32Done(Result); FreeMem(Buffer); end; End;//Crc32Stream Получаемый на выходе CRC32 совпадает с генерируемым такими программами как PkZip, ARJ, RAR и многими другими.

    И, конечно, тестовая программка:

    program Crc32; {$APPTYPE CONSOLE} uses SysUtils,Classes,IcsPlus; var FS: TFileStream; Crc: LongWord; Begin if ParamCount<>1 then begin WriteLn('Crc32 v1.0 Copyright (c) 2001 by Andrew P.Rybin [magicode@mail.ru]'); WriteLn(' Usage: crc32 filename'); EXIT; end; Crc32Initialization; FS:= TFileStream.Create(ParamStr(1),fmOpenRead); try Crc:=Crc32Stream(FS,0); WriteLn('Crc: ',IntToHex(Crc,8),' = ',Crc); finally FS.FREE; end; End.

    В файле содержится используемый мною в работе модуль IcsPlus.pas, который включает вышеописанные функции, и тестовая программка. Автор будет признателен за возможные советы, пожелания и bugfix'ы.

    Andrew P.Rybin
    Специально для


    Содержание раздела