Blog. Just Blog

Расчет CRC32 на Ассемблере

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

Примеры программ с исходными текстами (FASM)Примеры программ с исходными текстами (FASM)

CRC32.Demo.zip (7,879 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 13027 | Комментариев: 9

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

Комментарии

Отзывы посетителей сайта о статье
heil (15.11.2022 в 16:17):
Не сочтите за дерзость.

Цитатаand     ebx,0FFh
занимает 7 байт, аналогичная команда: movzx ebx,bl занимает всего 4 байта.

Цитатаxor     eax,-1
занимает 4 байта, аналогичная ей: neg eax занимает 3 байта

*fasm
Petya (08.08.2022 в 20:02):
В функции бестабличного расчёта
Цитатаxor     eax,eax

выглядит лишним,
Цитатаand     edx,0FFFFFFh

тоже, а тут
Цитатаjnc     @f
xor     ebx,0EDB88320h 
@@:

можно по вкусу избавиться от условного перехода
Цитатаsbb     eax,eax
and     eax,0EDB88320h
xor     ebx,eax

(что это даст, вопрос. Версия изначально оптимизирована под размер, а не под скорость)
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
spolyr (19.05.2011 в 10:30):
Спасибо, пригодится, буду разбиратся
ManHunter (30.03.2011 в 11:55):
chak_xakep, иногда лучше жевать, чем говорить.

len_s = $-crcstr ; Длина строки

CRC считается от бинарных данных, в том числе и от 00h
chak_xakep (30.03.2011 в 07:34):
Там в строке
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

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (27), AJAX (5), Assembler (348), COM (39), CSS (39), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (48), iconBIT (4), JavaScript (68), MySQL (13), Nikon (19), PDF (9), PHP (119), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (22), аксессуары (12), анализаторы файлов (8), архиваторы (5), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (18), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (120), выпечка (27), выставки (116), генератор ПСЧ (10), графика (118), десерты (31), Египет (8), заготовки на зиму (45), закуска (21), закуска к пиву (24), зарядные устройства (23), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (306), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (68), мониторы (6), музеи (72), мультимедиа (70), мясо (59), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (47), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (127), полезные функции (39), прохождения (4), процессы (25), птица (20), путешествия (25), распаковка (22), реверсинг (51), рыба (34), салаты (18), сброс триала (4), сеть (36), система (177), Сокольники (8), соусы (14), супы (14), телефоны (8), Тунис (6), умный дом (12), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (17), Яндекс (10)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 34,323 раза
<< 2024 - АПРЕЛЬ >>
Пн Вт Ср Чт Пт Сб Вс
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          
Национальный день донора крови
Всемирный день цирка
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 380
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.12 сек. / MySQL: 2 (0.0104 сек.) / Память: 4.5 Mb
Наверх