Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Подземелье Магов
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  08:30[Войти] | [Зарегистрироваться]

Почти всё, что вы хотели узнать, но боялись спросить о Crc32

Andrew Rybin
дата публикации 04-06-2001 00:00

Почти всё, что вы хотели узнать, но боялись спросить о Crc32

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

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

Использование 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_.zip содержится используемый мною в работе модуль IcsPlus.pas, который включает вышеописанные функции, и тестовая программка. Автор будет признателен за возможные советы, пожелания и bugfix'ы.

Andrew P.Rybin
Специально для Королевства Delphi






Смотрите также материалы по темам:
[TStream] [TFileStream] [Шифрование, контрольная сумма, хэш] [Контроль целостности кода]

 Обсуждение материала [ 09-12-2007 16:43 ] 4 сообщения
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования