Алгоритм вычисления
контрольной суммы (CRC, англ. cyclic redundancy code, циклический избыточный код) - способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения ее циклического избыточного кода. Алгоритм CRC32 основан на примитивном полиноме 0EDB88320h и применяется в архиваторах, системах шифрования, протекторах исполняемых файлов и многих других программах. Он прост в реализации и с большой вероятностью может подтверждать неизменность данных, причем чем меньше размер контролируемой информации, тем выше эта вероятность. Для расчета CRC32 требуется сперва подготовить так называемую таблицу инициализации. В сегменте данных таблица резервируется как 256 двойных слов, по одному dword на каждый возможный байт:
Code: assembler
; Сегмент данных
section '.data' data readable writeable
; Таблица инициализации для расчета CRC32
crc32table rd 256
После этого таблица заполняется данными, это делается при помощи следующей функции. Она вызывается только один раз до первого вызова функции расчета CRC32.
Code: assembler
;-----------------------------------------------------------------------
; Функция создания таблицы инициализации для расчета CRC32
;-----------------------------------------------------------------------
proc init_CRC32
push eax ebx ecx edi
mov edi,crc32table ; Указатель на выделенную под таблицу память
xor ebx,ebx ; Расчитать значения для всех 256 байт
calc_crc32table:
mov eax,ebx
mov ecx,8
do_polynom:
shr eax,1 ; Проверить четность байта
jnc @f ; XOR выполняется только если байт нечетный
xor eax,0EDB88320h
@@:
loop do_polynom ; Следующий бит
stosd ; Записать полученный dword в таблицу
inc ebx
cmp ebx,256
jb calc_crc32table ; Следующий байт
pop edi ecx ebx eax
ret
endp
Таблица инициализации получается всегда одинаковой (при условии неизменности полинома), так что ее можно даже не расчитывать, а хранить в виде массива констант. Если требуется таблица инициализации CRC32 отдельно для использования в других проектах или языках программирования, то она приведена ниже. Под синтаксис вашего языка программирования адаптируйте ее самостоятельно.
Code: assembler
;-----------------------------------------------------------------------
; Таблица инициализации CRC32, размер: 256 х 4 байт
;-----------------------------------------------------------------------
crc_tbl dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah, 0076dc419h
dd 0706af48fh, 0e963a535h, 09e6495a3h, 00edb8832h, 079dcb8a4h
dd 0e0d5e91eh, 097d2d988h, 009b64c2bh, 07eb17cbdh, 0e7b82d07h
dd 090bf1d91h, 01db71064h, 06ab020f2h, 0f3b97148h, 084be41deh
dd 01adad47dh, 06ddde4ebh, 0f4d4b551h, 083d385c7h, 0136c9856h
dd 0646ba8c0h, 0fd62f97ah, 08a65c9ech, 014015c4fh, 063066cd9h
dd 0fa0f3d63h, 08d080df5h, 03b6e20c8h, 04c69105eh, 0d56041e4h
dd 0a2677172h, 03c03e4d1h, 04b04d447h, 0d20d85fdh, 0a50ab56bh
dd 035b5a8fah, 042b2986ch, 0dbbbc9d6h, 0acbcf940h, 032d86ce3h
dd 045df5c75h, 0dcd60dcfh, 0abd13d59h, 026d930ach, 051de003ah
dd 0c8d75180h, 0bfd06116h, 021b4f4b5h, 056b3c423h, 0cfba9599h
dd 0b8bda50fh, 02802b89eh, 05f058808h, 0c60cd9b2h, 0b10be924h
dd 02f6f7c87h, 058684c11h, 0c1611dabh, 0b6662d3dh, 076dc4190h
dd 001db7106h, 098d220bch, 0efd5102ah, 071b18589h, 006b6b51fh
dd 09fbfe4a5h, 0e8b8d433h, 07807c9a2h, 00f00f934h, 09609a88eh
dd 0e10e9818h, 07f6a0dbbh, 0086d3d2dh, 091646c97h, 0e6635c01h
dd 06b6b51f4h, 01c6c6162h, 0856530d8h, 0f262004eh, 06c0695edh
dd 01b01a57bh, 08208f4c1h, 0f50fc457h, 065b0d9c6h, 012b7e950h
dd 08bbeb8eah, 0fcb9887ch, 062dd1ddfh, 015da2d49h, 08cd37cf3h
dd 0fbd44c65h, 04db26158h, 03ab551ceh, 0a3bc0074h, 0d4bb30e2h
dd 04adfa541h, 03dd895d7h, 0a4d1c46dh, 0d3d6f4fbh, 04369e96ah
dd 0346ed9fch, 0ad678846h, 0da60b8d0h, 044042d73h, 033031de5h
dd 0aa0a4c5fh, 0dd0d7cc9h, 05005713ch, 0270241aah, 0be0b1010h
dd 0c90c2086h, 05768b525h, 0206f85b3h, 0b966d409h, 0ce61e49fh
dd 05edef90eh, 029d9c998h, 0b0d09822h, 0c7d7a8b4h, 059b33d17h
dd 02eb40d81h, 0b7bd5c3bh, 0c0ba6cadh, 0edb88320h, 09abfb3b6h
dd 003b6e20ch, 074b1d29ah, 0ead54739h, 09dd277afh, 004db2615h
dd 073dc1683h, 0e3630b12h, 094643b84h, 00d6d6a3eh, 07a6a5aa8h
dd 0e40ecf0bh, 09309ff9dh, 00a00ae27h, 07d079eb1h, 0f00f9344h
dd 08708a3d2h, 01e01f268h, 06906c2feh, 0f762575dh, 0806567cbh
dd 0196c3671h, 06e6b06e7h, 0fed41b76h, 089d32be0h, 010da7a5ah
dd 067dd4acch, 0f9b9df6fh, 08ebeeff9h, 017b7be43h, 060b08ed5h
dd 0d6d6a3e8h, 0a1d1937eh, 038d8c2c4h, 04fdff252h, 0d1bb67f1h
dd 0a6bc5767h, 03fb506ddh, 048b2364bh, 0d80d2bdah, 0af0a1b4ch
dd 036034af6h, 041047a60h, 0df60efc3h, 0a867df55h, 0316e8eefh
dd 04669be79h, 0cb61b38ch, 0bc66831ah, 0256fd2a0h, 05268e236h
dd 0cc0c7795h, 0bb0b4703h, 0220216b9h, 05505262fh, 0c5ba3bbeh
dd 0b2bd0b28h, 02bb45a92h, 05cb36a04h, 0c2d7ffa7h, 0b5d0cf31h
dd 02cd99e8bh, 05bdeae1dh, 09b64c2b0h, 0ec63f226h, 0756aa39ch
dd 0026d930ah, 09c0906a9h, 0eb0e363fh, 072076785h, 005005713h
dd 095bf4a82h, 0e2b87a14h, 07bb12baeh, 00cb61b38h, 092d28e9bh
dd 0e5d5be0dh, 07cdcefb7h, 00bdbdf21h, 086d3d2d4h, 0f1d4e242h
dd 068ddb3f8h, 01fda836eh, 081be16cdh, 0f6b9265bh, 06fb077e1h
dd 018b74777h, 088085ae6h, 0ff0f6a70h, 066063bcah, 011010b5ch
dd 08f659effh, 0f862ae69h, 0616bffd3h, 0166ccf45h, 0a00ae278h
dd 0d70dd2eeh, 04e048354h, 03903b3c2h, 0a7672661h, 0d06016f7h
dd 04969474dh, 03e6e77dbh, 0aed16a4ah, 0d9d65adch, 040df0b66h
dd 037d83bf0h, 0a9bcae53h, 0debb9ec5h, 047b2cf7fh, 030b5ffe9h
dd 0bdbdf21ch, 0cabac28ah, 053b39330h, 024b4a3a6h, 0bad03605h
dd 0cdd70693h, 054de5729h, 023d967bfh, 0b3667a2eh, 0c4614ab8h
dd 05d681b02h, 02a6f2b94h, 0b40bbe37h, 0c30c8ea1h, 05a05df1bh
dd 02d02ef8dh
Сама функция расчета CRC32 будет такой:
Code: assembler
;-----------------------------------------------------------------------
; Функция вычисления CRC32 с таблицей инициализации
;
; Параметры:
; lData - указатель на участок памяти для расчета CRC32
; dLen - размер участка в байтах
; dCRC32 - начальное значение CRC32, при первом расчете должно быть -1,
; при промежуточном равняется CRC32 предыдущего блока
; dFlag - TRUE - финализировать CRC32, FALSE - не финализировать (для
; расчета промежуточного значения CRC32 некольких блоков памяти)
; На выходе:
; EAX = CRC32 заданного участка памяти
;-----------------------------------------------------------------------
proc calc_CRC32 lData:dword, dLen:dword, dCRC32:dword, dFlag:dword
push ebx ecx edx esi
mov edx,[dCRC32] ; Начальное значение CRC32
mov esi,[lData] ; Указатель на блок данных
mov ecx,[dLen] ; Длина блока
xor eax,eax
calc_crc32:
lodsb ; Получить следующий символ строки
mov ebx,edx ; Скопировать текущее значение CRC32
and ebx,0FFh
xor bl,al ; XOR с текущим символом блока данных
shl ebx,2 ; Вычисление смещения нужного dword в таблице
shr edx,8
and edx,0FFFFFFh
xor edx,[crc32table+ebx] ; XOR CRC32 со значением из таблицы
loop calc_crc32 ; Перейти к следующему символу
mov eax,edx ; В регистре EAX записана CRC32 строки
; Если дальнейшая обработка не требуется, то проXORить CRC32
; для завершения расчетов
cmp [dFlag],TRUE
jne @f
xor eax,-1
@@:
pop esi edx ecx ebx ; Восстановить измененные регистры
ret
endp
Параметры вызова функции calc_CRC32 следующие: lData - указатель на участок памяти, для которого надо посчитать контрольную сумму, dLen - размер этого участка в байтах. dCRC32 - начальное значение CRC32. Если требуется подсчитать контрольную сумму только для одного участка памяти, то начальное значение CRC обязательно должно быть равно -1. Для нескольких блоков, например при расчете контрольной суммы файла, когда данные из него читаются по частям, первоначальное значение должно быть также -1, а все последующие должны быть равны CRC32 из предыдущего вызова функции. dFlag - флаг-указатель, значение TRUE - финализировать CRC32 и FALSE - не финализировать. Для расчета контрольной суммы одиночного блока памяти этот флаг должен иметь значение TRUE, для нескольких последовательных блоков - FALSE для всех кроме последнего и TRUE для последнего блока. Вы можете всегда выставлять значение флага равное FALSE, но в этом случае после всех расчетов придется выполнить команду XOR EAX,-1 (подразумевается, что в регистре EAX содержится полученное значение CRC32). Примеры использования:
Code: assembler
; Сегмент данных
section '.data' data readable writeable
; Таблица инициализации для расчета CRC32
crc32table rd 256
...
crcstr db 'Dima' ; Строка для расчета CRC32
len_s = $-crcstr ; Длина строки
; Сегмент кода
section '.code' code readable executable
...
; Вызов функции инициализации
stdcall init_CRC32
; Обычный вызов функции
stdcall calc_CRC32,crcstr,len_s,-1,TRUE ; EAX=98D2A4FDh
; Вызов функции без флага финализации
stdcall calc_CRC32,crcstr,len_s,-1,FALSE
xor eax,-1 ; EAX=98D2A4FDh
; Последовательный вызов функции для нескольких участков памяти
; В данном случае расчет CRC32 последовательно для первого,
; второго и последних двух символов в строке
stdcall calc_CRC32,crcstr+0,1,-1,FALSE
stdcall calc_CRC32,crcstr+1,1,eax,FALSE
stdcall calc_CRC32,crcstr+2,2,eax,TRUE ; EAX=98D2A4FDh
...
; Расчет CRC32 файла
mov [crc],-1
@@:
; Читаем файл блоками по 1024 байта
invoke _lread,[desc],buff,1024
or eax,eax
jz @f
; Рассчитать CRC32 для нового блока с учетом уже рассчитанной
stdcall calc_CRC32,buff,eax,[crc],FALSE
mov [crc],eax
jmp @b
@@:
; Теперь в переменной [crc] содержится CRC32 файла. Флаг финализации
; не был установлен, поэтому значение CRC надо подкорректировать
xor [crc],-1
Для личных нужд я модифицировал функцию расчета CRC32, чтобы она работала вообще без таблицы инициализации. Ее не рекомендуется использовать при расчете контрольных сумм очень больших участков памяти и при расчетах с критичным временем выполнения, так как в функции используется дополнительный вложенный цикл. Но для небольших участков памяти вполне можно использовать именно модифицированную функцию, потому что она полностью самодостаточна, не требует вызова дополнительных процедур и хранения в памяти каких-либо данных.
Code: assembler
;-----------------------------------------------------------------------
; Функция вычисления CRC32 без дополнительной таблицы инициализации
; by ManHunter / PCL
; http://www.manhunter.ru
;
; Параметры:
; lData - указатель на участок памяти для расчета CRC32
; dLen - размер участка в байтах
; dCRC32 - начальное значение CRC32, при первом расчете должно быть -1,
; при промежуточном равняется CRC32 предыдущего блока
; dFlag - TRUE - финализировать CRC32, FALSE - не финализировать (для
; расчета промежуточного значения CRC32 некольких блоков памяти)
; На выходе:
; EAX = CRC32 заданного участка памяти
;-----------------------------------------------------------------------
proc calc_CRC32 lData:dword, dLen:dword, dCRC32:dword, dFlag:dword
push ebx ecx edx esi
mov edx,[dCRC32] ; Начальное значение CRC32
mov esi,[lData] ; Указатель на блок данных
mov ecx,[dLen] ; Длина блока
xor eax,eax
calc_crc32:
lodsb ; Получить следующий символ строки
mov ebx,edx ; Скопировать текущее значение CRC32
and ebx,0FFh
xor bl,al ; XOR с текущим символом блока данных
shr edx,8
and edx,0FFFFFFh
push ecx ; Сохранить счетчик символов
mov ecx,8 ; Вложенный цикл расчета полинома
do_polynom:
shr ebx,1 ; Проверить четность байта
jnc @f ; XOR выполняется только если байт нечетный
xor ebx,0EDB88320h
@@:
loop do_polynom ; Следующий бит
pop ecx ; Восстановить счетчик
xor edx,ebx ; XOR CRC32 с вычисленным значением
loop calc_crc32 ; Перейти к следующему символу
mov eax,edx ; В регистре EAX записана CRC32 строки
; Если дальнейшая обработка не требуется, то проXORить CRC32
; для завершения расчетов
cmp [dFlag],TRUE
jne @f
xor eax,-1
@@:
pop esi edx ecx ebx ; Восстановить измененные регистры
ret
endp
Параметры вызова у модифицированной функции те же самые, что и у обычной. В приложении две программы для расчета CRC32 с использованием таблицы инициализации и без нее, а также отдельно сама таблица инициализации.
Примеры программ с исходными текстами (FASM)
CRC32.Demo.zip (7,879 bytes)