Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail 30.11.2010 | Категория: Образ мышления: Assembler | Автор: ManHunter
CRC (Cyclic Redundancy Code - циклический избыточный код) - алгоритм расчета контрольной суммы для передаваемого сообщения, основанный на полиномиальной арифметике. Основная идея алгоритма CRC состоит в представлении сообщения в виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка от этого деления в качестве контрольной суммы. Получив сообщение, приемник должен выполнить аналогичное действие и сравнить полученный результат с принятой контрольной суммой. Сообщение считается достоверным, выполняется это равенство. Классический алгоритм CRC16 часто используется в архиваторах для контроля целостности данных служебных заголовков архивов, также его удобно использовать для сравнения строки с каким-либо значением, когда по соображениям безопасности сравниваемое значение не хранится в открытом виде. Для контроля целостности файлов функцию CRC16 лучше не использовать, так как из-за небольшой длины ее научились подделывать. Чтобы выполнить расчет CRC16 требуется сперва подготовить так называемую таблицу инициализации. В сегменте данных таблица резервируется как 256 слов, по одному word на каждый возможный байт:
Code (Assembler) : Убрать нумерацию
  1. ; Сегмент данных
  2. section '.data' data readable writeable
  3.  
  4. ; Таблица инициализации для расчета CRC16
  5. crc16table rw 256
В классическом варианте для расчета CRC16 используется полином 0a001h, на его основе таблица слов заполняется значениями. Для этого используется следующая вспомогательная функция:
Code (Assembler) : Убрать нумерацию
  1. ;-----------------------------------------------------------------------
  2. ; Функция создания таблицы инициализации для расчета CRC16
  3. ;-----------------------------------------------------------------------
  4. proc init_CRC16
  5.         push    eax ebx ecx edi
  6.  
  7.         ; Указатель на выделенную под таблицу память
  8.         mov     edi,crc16table
  9.         ; Расчитать значения для всех 256 слов
  10.         xor     edx,edx
  11. CRC16_Polynom:
  12.         mov     eax,edx
  13.         mov     ecx,8
  14. CRC16_NL:
  15.         shr     ax,1
  16.         jae     CRC16_NoXOR
  17.         ; Magic Number!
  18.         xor     ax,0a001h
  19. CRC16_NoXOR:
  20.         loop    CRC16_NL
  21.         ; Записать значение в таблицу полиномов
  22.         stosw
  23.         inc     edx            ; Счетчик +1
  24.         cmp     edx,256        ; Всю таблицу сгенерировали?
  25.         jne     CRC16_Polynom  ; Нет, работаем дальше
  26.  
  27.         ; Восстановить измененные регистры
  28.         pop     edi ecx ebx eax
  29.         ret
  30. endp
Таблица инициализации получается всегда одинаковой (при условии неизменности полинома), так что ее можно даже не раcчитывать, а хранить в виде массива констант. Если требуется таблица инициализации CRC16 отдельно для использования в других проектах или языках программирования, то она приведена ниже. Для некоторых других разновидностей алгоритма CRC16, например, CRC-CCITT или CRC16-IBM, полином будет другим, и, соответственно, таблица также будет другой.
Code (Assembler) : Убрать нумерацию
  1. ; Таблица инициализации для расчета CRC16
  2. crc_tbl dw 00000h, 0C0C1h, 0C181h, 00140h, 0C301h, 003C0h, 00280h, 0C241h
  3.         dw 0C601h, 006C0h, 00780h, 0C741h, 00500h, 0C5C1h, 0C481h, 00440h
  4.         dw 0CC01h, 00CC0h, 00D80h, 0CD41h, 00F00h, 0CFC1h, 0CE81h, 00E40h
  5.         dw 00A00h, 0CAC1h, 0CB81h, 00B40h, 0C901h, 009C0h, 00880h, 0C841h
  6.         dw 0D801h, 018C0h, 01980h, 0D941h, 01B00h, 0DBC1h, 0DA81h, 01A40h
  7.         dw 01E00h, 0DEC1h, 0DF81h, 01F40h, 0DD01h, 01DC0h, 01C80h, 0DC41h
  8.         dw 01400h, 0D4C1h, 0D581h, 01540h, 0D701h, 017C0h, 01680h, 0D641h
  9.         dw 0D201h, 012C0h, 01380h, 0D341h, 01100h, 0D1C1h, 0D081h, 01040h
  10.         dw 0F001h, 030C0h, 03180h, 0F141h, 03300h, 0F3C1h, 0F281h, 03240h
  11.         dw 03600h, 0F6C1h, 0F781h, 03740h, 0F501h, 035C0h, 03480h, 0F441h
  12.         dw 03C00h, 0FCC1h, 0FD81h, 03D40h, 0FF01h, 03FC0h, 03E80h, 0FE41h
  13.         dw 0FA01h, 03AC0h, 03B80h, 0FB41h, 03900h, 0F9C1h, 0F881h, 03840h
  14.         dw 02800h, 0E8C1h, 0E981h, 02940h, 0EB01h, 02BC0h, 02A80h, 0EA41h
  15.         dw 0EE01h, 02EC0h, 02F80h, 0EF41h, 02D00h, 0EDC1h, 0EC81h, 02C40h
  16.         dw 0E401h, 024C0h, 02580h, 0E541h, 02700h, 0E7C1h, 0E681h, 02640h
  17.         dw 02200h, 0E2C1h, 0E381h, 02340h, 0E101h, 021C0h, 02080h, 0E041h
  18.         dw 0A001h, 060C0h, 06180h, 0A141h, 06300h, 0A3C1h, 0A281h, 06240h
  19.         dw 06600h, 0A6C1h, 0A781h, 06740h, 0A501h, 065C0h, 06480h, 0A441h
  20.         dw 06C00h, 0ACC1h, 0AD81h, 06D40h, 0AF01h, 06FC0h, 06E80h, 0AE41h
  21.         dw 0AA01h, 06AC0h, 06B80h, 0AB41h, 06900h, 0A9C1h, 0A881h, 06840h
  22.         dw 07800h, 0B8C1h, 0B981h, 07940h, 0BB01h, 07BC0h, 07A80h, 0BA41h
  23.         dw 0BE01h, 07EC0h, 07F80h, 0BF41h, 07D00h, 0BDC1h, 0BC81h, 07C40h
  24.         dw 0B401h, 074C0h, 07580h, 0B541h, 07700h, 0B7C1h, 0B681h, 07640h
  25.         dw 07200h, 0B2C1h, 0B381h, 07340h, 0B101h, 071C0h, 07080h, 0B041h
  26.         dw 05000h, 090C1h, 09181h, 05140h, 09301h, 053C0h, 05280h, 09241h
  27.         dw 09601h, 056C0h, 05780h, 09741h, 05500h, 095C1h, 09481h, 05440h
  28.         dw 09C01h, 05CC0h, 05D80h, 09D41h, 05F00h, 09FC1h, 09E81h, 05E40h
  29.         dw 05A00h, 09AC1h, 09B81h, 05B40h, 09901h, 059C0h, 05880h, 09841h
  30.         dw 08801h, 048C0h, 04980h, 08941h, 04B00h, 08BC1h, 08A81h, 04A40h
  31.         dw 04E00h, 08EC1h, 08F81h, 04F40h, 08D01h, 04DC0h, 04C80h, 08C41h
  32.         dw 04400h, 084C1h, 08581h, 04540h, 08701h, 047C0h, 04680h, 08641h
  33.         dw 08201h, 042C0h, 04380h, 08341h, 04100h, 081C1h, 08081h, 04040h
Теперь сама функция расчета CRC16 блока памяти:
Code (Assembler) : Убрать нумерацию
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления CRC16 с таблицей инициализации
  3. ;
  4. ; Параметры:
  5. ; lData  - указатель на участок памяти для расчета CRC16
  6. ; dLen   - размер участка в байтах
  7. ; На выходе:
  8. ; EAX = CRC16 заданного участка памяти
  9. ;-----------------------------------------------------------------------
  10. proc calc_CRC16 lData:dword, dLen:dword
  11.         push    ebx ecx edx esi
  12.  
  13.         mov     esi,[lData]     ; Указатель на блок данных
  14.         mov     ecx,[dLen]      ; Длина блока
  15.  
  16.         ; Обнулить первоначальное значение CRC16
  17.         xor     eax,eax
  18. @@:
  19.         xor     ebx,ebx
  20.         mov     bl,al
  21.         ; Получить следующий байт данных
  22.         lodsb
  23.         xor     bl,al
  24.         shl     bx,1
  25.  
  26.         ; ПроXORить с word из таблицы
  27.         mov     bx,word [crc16table+ebx]
  28.  
  29.         xor     bl,ah
  30.         mov     ax,bx
  31.         loop    @b              ; Следующий байт
  32.  
  33.         ; Восстановить измененные регистры
  34.         pop     esi edx ecx ebx
  35.         ret
  36. endp
Параметры вызова функции: lData - указатель на блок памяти, у которого надо посчитать контрольную сумму, dLen - размер блока. Подразумевается, что таблица инициализации уже была рассчитана. Пример использования функции расчета CRC16:
Code (Assembler) : Убрать нумерацию
  1. ; Сегмент данных
  2. section '.data' data readable writeable
  3.  
  4. ; Таблица инициализации для расчета CRC16
  5. crc16table rw 256
  6.         ...
  7. crcstr     db 'Dima'      ; Строка для расчета CRC16
  8. len_s      =  $-crcstr    ; Длина строки 
  9.  
  10. ; Сегмент кода
  11. section '.code' code readable executable
  12.         ...
  13.         ; Вызов функции инициализации
  14.         stdcall init_CRC16
  15.  
  16.         ; Расчет CRC16 строки
  17.         stdcall calc_CRC16,crcstr,len_s    ; EAX=9429h
  18.         ...
Если в вашем приложении не требуется расчет контрольной суммы больших участков памяти и не критично время выполнения, то можете использовать мою модифицированную функцию расчета CRC16 без использования таблицы инициализации. Она полностью самодостаточна, не требует вызова дополнительных процедур и хранения в памяти каких-либо данных.
Code (Assembler) : Убрать нумерацию
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления CRC16 без использования таблицы инициализации
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru 
  5. ;
  6. ; Параметры:
  7. ; lData  - указатель на участок памяти для расчета CRC16
  8. ; dLen   - размер участка в байтах
  9. ; На выходе:
  10. ; EAX = CRC16 заданного участка памяти
  11. ;-----------------------------------------------------------------------
  12. proc calc_CRC16 lData:dword, dLen:dword
  13.         push    ebx ecx edx esi
  14.  
  15.         mov     esi,[lData]     ; Указатель на блок данных
  16.         mov     ecx,[dLen]      ; Длина блока
  17.  
  18.         ; Обнулить первоначальное значение CRC16
  19.         xor     eax,eax
  20. @@:
  21.         xor     ebx,ebx
  22.         mov     bl,al
  23.         ; Получить следующий байт данных
  24.         lodsb
  25.         xor     bl,al
  26.  
  27.         ; Динамический расчет полинома
  28.         push    ecx
  29.         mov     ecx,8
  30. CRC16_NL:
  31.         shr     bx,1
  32.         jae     CRC16_NoXOR
  33.         ; Magic Number!
  34.         xor     bx,0a001h
  35. CRC16_NoXOR:
  36.         loop    CRC16_NL
  37.         pop     ecx
  38.  
  39.         ; ПроXORить со значением из таблицы
  40.         xor     bl,ah
  41.         mov     ax,bx
  42.         loop    @b              ; Следующий байт
  43.  
  44.         ; Восстановить измененные регистры
  45.         pop     esi edx ecx ebx
  46.         ret
  47. endp
Параметры вызова у модифицированной функции те же самые, что и у обычной. В приложении две программы для расчета CRC16 с использованием таблицы инициализации и без нее, а также отдельно сама таблица инициализации.

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

CRC16.Demo.zip (6,218 bytes)


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

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

Комментарии

Отзывы посетителей сайта о статье
ManHunter (27.12.2010 в 15:45):
Alex81524, выйди в окно, не засоряй собой генофонд.

"В классическом варианте для расчета CRC16 используется полином 0a001h, на его основе таблица слов заполняется значениями. Для этого используется следующая вспомогательная функция"
Alex81524 (27.12.2010 в 15:44):
А как рассчитывается таблица инициализации?

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 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.1 сек. / MySQL: 2 (0.0079 сек.) / Память: 4.5 Mb
Наверх