
Расчет CRC32 на Ассемблере
Алгоритм вычисления контрольной суммы (CRC, англ. cyclic redundancy code, циклический избыточный код) - способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения ее циклического избыточного кода. Алгоритм CRC32 основан на примитивном полиноме 0EDB88320h и применяется в архиваторах, системах шифрования, протекторах исполняемых файлов и многих других программах. Он прост в реализации и с большой вероятностью может подтверждать неизменность данных, причем чем меньше размер контролируемой информации, тем выше эта вероятность. Для расчета CRC32 требуется сперва подготовить так называемую таблицу инициализации. В сегменте данных таблица резервируется как 256 двойных слов, по одному dword на каждый возможный байт:Code (Assembler) : Убрать нумерацию
- ; Сегмент данных
- section '.data' data readable writeable
- ; Таблица инициализации для расчета CRC32
- crc32table rd 256
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
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
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
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
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
Просмотров: 13495 | Комментариев: 9

Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье

Petya
(08.08.2022 в 20:02):
В функции бестабличного расчёта
выглядит лишним,
тоже, а тут
можно по вкусу избавиться от условного перехода
(что это даст, вопрос. Версия изначально оптимизирована под размер, а не под скорость)
выглядит лишним,
тоже, а тут
можно по вкусу избавиться от условного перехода
(что это даст, вопрос. Версия изначально оптимизирована под размер, а не под скорость)

ManHunter
(25.07.2012 в 14:14):
Ассемблер тем и хорош, что оптимизацию кода в нем можно проводить практически бесконечно :)

ALgraFx
(25.07.2012 в 12:37):
calc_crc32:
xor dl,[esi]
mov al,dl
shr edx,8
xor edx,[crc32table+eax*4]
inc esi
loop calc_crc32
xor dl,[esi]
mov al,dl
shr edx,8
xor edx,[crc32table+eax*4]
inc esi
loop calc_crc32

spolyr
(19.05.2011 в 10:30):
Спасибо, пригодится, буду разбиратся

ManHunter
(30.03.2011 в 11:55):
chak_xakep, иногда лучше жевать, чем говорить.
len_s = $-crcstr ; Длина строки
CRC считается от бинарных данных, в том числе и от 00h
len_s = $-crcstr ; Длина строки
CRC считается от бинарных данных, в том числе и от 00h

chak_xakep
(30.03.2011 в 07:34):
Там в строке
crcstr db 'Dima'
должен стоять нулевой терминатор,
crcstr db 'Dima',0
;) хотя это дэмка, статья отличная!
crcstr db 'Dima'
должен стоять нулевой терминатор,
crcstr db 'Dima',0
;) хотя это дэмка, статья отличная!

ManHunter
(27.04.2009 в 16:43):
Zummenix, ты имеешь в виду добавить проверку длины строки? Это ж просто демонстрационный пример с минимальным кодом, естественно его можно доработать как надо, можно даже проверку длины строки добавить в саму функцию расчета CRC32. Тут уже полный полет фантазии.

Zummenix
(27.04.2009 в 16:33):
Позволил себе некоторое вмешательство в код, а то не хорошо с ошибкой :)
.wmencode:
invoke GetDlgItemText,[hwnddlg],ID_TXT,buff,255
test eax,eax
je .null
invoke lstrlen,buff
stdcall calc_CRC32,buff,eax,-1,TRUE
.null:
invoke wsprintf,buff,mask,eax
add esp,12
invoke SetDlgItemText,[hwnddlg],ID_CRC,buff
jmp .processed
.wmencode:
invoke GetDlgItemText,[hwnddlg],ID_TXT,buff,255
test eax,eax
je .null
invoke lstrlen,buff
stdcall calc_CRC32,buff,eax,-1,TRUE
.null:
invoke wsprintf,buff,mask,eax
add esp,12
invoke SetDlgItemText,[hwnddlg],ID_CRC,buff
jmp .processed

Добавить комментарий
Заполните форму для добавления комментария

занимает 7 байт, аналогичная команда: movzx ebx,bl занимает всего 4 байта.
занимает 4 байта, аналогичная ей: neg eax занимает 3 байта
*fasm