Изначально цель методик обнаружения ошибок
Раздел Подземелье Магов |
Изначально цель методик обнаружения ошибок была в том, чтобы дать возможность получателю сообщения, передаваемому по зашумленному каналу, определить, не было ли оно испорчено. Для этого отправитель формировал значение, именуемое контрольной суммой ("checksum" - КС), как функцию от сообщения и добавлял его к сообщению, получатель, используя ту же самую функцию, мог посчитать КС полученного сообщения и в случае равенства, считать сообщение безошибочно принятым. Самый первый алгоритм подсчета КС был очень прост: все байты сообщения суммировались (отсюда и пошло название ) по модулю степени двойки. Главное достоинство этого метода - простота, главный недостаток - ненадежность. Например, он не перестановки байт местами.
Высокую степень безопасности данных обеспечивают алгоритмы контроля за достоверностью информации, использующие циклические избыточные коды (Cyclic Redundancy Code - CRC).
Использование CRC представляет собой сверхмощный метод обнаружения ошибок.
кода,
Для простоты считайте CRC остатком от деления БОЛЬШОГО бинарного числа (передаваемых данных) на число, в зависимости от разряда старшего бита этого числа выделяют CRC16 и CRC32.
Теория этого дела весьма обширна и хорошо описана в литературе, но думаю, большинство читателей этой статьи гораздо больше волнует её практическая реализация.
Алгоритм получения CRC32 такой:
- 1. CRC-32 инициализируется значением $FFFFFFFF
- 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. Инвертировать все биты: CRC:= NOT CRC;
И, конечно, тестовая программка:
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
Специально для