Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail 05.01.2015 | Категория: Образ мышления: Assembler | Автор: ManHunter
CRC24 - еще одна разновидность контрольной суммы. Как можно увидеть из названия, ее размер составляет 24 бита, или 3 байта. Я пока не нашел практического применения этому хешу, так же как и программ, использующих его. Но раз есть алгоритм, то почему бы его не реализовать на Ассемблере? Начнем с наиболее компактной реализации без использования таблицы.
Code (Assembler) : Убрать нумерацию
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша CRC24
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       EAX = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    CRC24 lpData:DWORD, dSize:DWORD
  13.         push    ebx ecx edx esi
  14.  
  15.         CRC24_POLYNOM = 1864CFBh
  16.  
  17.         ; Инициализация
  18.         mov     eax,0B704CEh
  19.  
  20.         ; Длина строки
  21.         cmp     [dSize],0
  22.         je      .loc_ret
  23.  
  24.         ; Указатель на начало строки
  25.         xor     ecx,ecx
  26. @@:
  27.         ; Получить символ из строки
  28.         mov     ebx,[lpData]
  29.  
  30.         movzx   edx,byte [ebx+ecx]
  31.         shl     edx,16
  32.         xor     eax,edx
  33.  
  34.         xor     esi,esi
  35. .loc_cycle:
  36.         shl     eax,1
  37.         test    eax,1000000h
  38.         jz      .loc_next
  39.         xor     eax,CRC24_POLYNOM
  40.         jmp     .loc_next
  41. .loc_next:
  42.         inc     esi
  43.         cmp     esi,8
  44.         jb      .loc_cycle
  45.  
  46.         ; Следующий символ
  47.         inc     ecx
  48.         cmp     ecx,[dSize]
  49.         jb      @b
  50.  
  51. .loc_ret:
  52.         and     eax,0FFFFFFh
  53.  
  54.         pop     esi edx ecx ebx
  55.         ret
  56. endp
По скорости работы этот алгоритм мало чем отличается от безтабличных реализаций CRC32 или CRC16, а для хранения результатов все равно надо будет использовать переменную размера DWORD. Так что каких-то особых преимуществ перед этими хешами у CRC24 нет.

Более объемный в плане хранимых данных, но более быстрый в скорости выполнения - это табличный вариант алгоритма хеширования. Вот так выглядит заранее рассчитанная таблица размером 256 DWORD.
Code (Assembler) : Убрать нумерацию
  1. crc24table:
  2.         dd 00000000h, 00864CFBh, 008AD50Dh, 000C99F6h, 0093E6E1h
  3.         dd 0015AA1Ah, 001933ECh, 009F7F17h, 00A18139h, 0027CDC2h
  4.         dd 002B5434h, 00AD18CFh, 003267D8h, 00B42B23h, 00B8B2D5h
  5.         dd 003EFE2Eh, 00C54E89h, 00430272h, 004F9B84h, 00C9D77Fh
  6.         dd 0056A868h, 00D0E493h, 00DC7D65h, 005A319Eh, 0064CFB0h
  7.         dd 00E2834Bh, 00EE1ABDh, 00685646h, 00F72951h, 007165AAh
  8.         dd 007DFC5Ch, 00FBB0A7h, 000CD1E9h, 008A9D12h, 008604E4h
  9.         dd 0000481Fh, 009F3708h, 00197BF3h, 0015E205h, 0093AEFEh
  10.         dd 00AD50D0h, 002B1C2Bh, 002785DDh, 00A1C926h, 003EB631h
  11.         dd 00B8FACAh, 00B4633Ch, 00322FC7h, 00C99F60h, 004FD39Bh
  12.         dd 00434A6Dh, 00C50696h, 005A7981h, 00DC357Ah, 00D0AC8Ch
  13.         dd 0056E077h, 00681E59h, 00EE52A2h, 00E2CB54h, 006487AFh
  14.         dd 00FBF8B8h, 007DB443h, 00712DB5h, 00F7614Eh, 0019A3D2h
  15.         dd 009FEF29h, 009376DFh, 00153A24h, 008A4533h, 000C09C8h
  16.         dd 0000903Eh, 0086DCC5h, 00B822EBh, 003E6E10h, 0032F7E6h
  17.         dd 00B4BB1Dh, 002BC40Ah, 00AD88F1h, 00A11107h, 00275DFCh
  18.         dd 00DCED5Bh, 005AA1A0h, 00563856h, 00D074ADh, 004F0BBAh
  19.         dd 00C94741h, 00C5DEB7h, 0043924Ch, 007D6C62h, 00FB2099h
  20.         dd 00F7B96Fh, 0071F594h, 00EE8A83h, 0068C678h, 00645F8Eh
  21.         dd 00E21375h, 0015723Bh, 00933EC0h, 009FA736h, 0019EBCDh
  22.         dd 008694DAh, 0000D821h, 000C41D7h, 008A0D2Ch, 00B4F302h
  23.         dd 0032BFF9h, 003E260Fh, 00B86AF4h, 002715E3h, 00A15918h
  24.         dd 00ADC0EEh, 002B8C15h, 00D03CB2h, 00567049h, 005AE9BFh
  25.         dd 00DCA544h, 0043DA53h, 00C596A8h, 00C90F5Eh, 004F43A5h
  26.         dd 0071BD8Bh, 00F7F170h, 00FB6886h, 007D247Dh, 00E25B6Ah
  27.         dd 00641791h, 00688E67h, 00EEC29Ch, 003347A4h, 00B50B5Fh
  28.         dd 00B992A9h, 003FDE52h, 00A0A145h, 0026EDBEh, 002A7448h
  29.         dd 00AC38B3h, 0092C69Dh, 00148A66h, 00181390h, 009E5F6Bh
  30.         dd 0001207Ch, 00876C87h, 008BF571h, 000DB98Ah, 00F6092Dh
  31.         dd 007045D6h, 007CDC20h, 00FA90DBh, 0065EFCCh, 00E3A337h
  32.         dd 00EF3AC1h, 0069763Ah, 00578814h, 00D1C4EFh, 00DD5D19h
  33.         dd 005B11E2h, 00C46EF5h, 0042220Eh, 004EBBF8h, 00C8F703h
  34.         dd 003F964Dh, 00B9DAB6h, 00B54340h, 00330FBBh, 00AC70ACh
  35.         dd 002A3C57h, 0026A5A1h, 00A0E95Ah, 009E1774h, 00185B8Fh
  36.         dd 0014C279h, 00928E82h, 000DF195h, 008BBD6Eh, 00872498h
  37.         dd 00016863h, 00FAD8C4h, 007C943Fh, 00700DC9h, 00F64132h
  38.         dd 00693E25h, 00EF72DEh, 00E3EB28h, 0065A7D3h, 005B59FDh
  39.         dd 00DD1506h, 00D18CF0h, 0057C00Bh, 00C8BF1Ch, 004EF3E7h
  40.         dd 00426A11h, 00C426EAh, 002AE476h, 00ACA88Dh, 00A0317Bh
  41.         dd 00267D80h, 00B90297h, 003F4E6Ch, 0033D79Ah, 00B59B61h
  42.         dd 008B654Fh, 000D29B4h, 0001B042h, 0087FCB9h, 001883AEh
  43.         dd 009ECF55h, 009256A3h, 00141A58h, 00EFAAFFh, 0069E604h
  44.         dd 00657FF2h, 00E33309h, 007C4C1Eh, 00FA00E5h, 00F69913h
  45.         dd 0070D5E8h, 004E2BC6h, 00C8673Dh, 00C4FECBh, 0042B230h
  46.         dd 00DDCD27h, 005B81DCh, 0057182Ah, 00D154D1h, 0026359Fh
  47.         dd 00A07964h, 00ACE092h, 002AAC69h, 00B5D37Eh, 00339F85h
  48.         dd 003F0673h, 00B94A88h, 0087B4A6h, 0001F85Dh, 000D61ABh
  49.         dd 008B2D50h, 00145247h, 00921EBCh, 009E874Ah, 0018CBB1h
  50.         dd 00E37B16h, 006537EDh, 0069AE1Bh, 00EFE2E0h, 00709DF7h
  51.         dd 00F6D10Ch, 00FA48FAh, 007C0401h, 0042FA2Fh, 00C4B6D4h
  52.         dd 00C82F22h, 004E63D9h, 00D11CCEh, 00575035h, 005BC9C3h
  53.         dd 00DD8538h
В принципе, таблицу можно было бы немного сократить за счет неиспользуемых нулевых байтов, то есть хранить в ней только три значимых байта. Но это повлечет за собой дополнительные операции в самом цикле хеширования, что, в свою очередь, негативно скажется на скорости. А ведь именно ради скорости затевалась вся эта возня с таблицей. Так что пусть остаются DWORD'ы.
Code (Assembler) : Убрать нумерацию
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша CRC24
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       EAX = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    CRC24 lpData:DWORD, dSize:DWORD
  13.         push    ebx ecx edx
  14.  
  15.         ; Инициализация
  16.         mov     eax,0B704CEh
  17.  
  18.         ; Длина строки
  19.         cmp     [dSize],0
  20.         je      .loc_ret
  21.  
  22.         ; Указатель на начало строки
  23.         xor     ecx,ecx
  24. @@:
  25.         ; Получить символ из строки
  26.         mov     ebx,[lpData]
  27.  
  28.         mov     edx,eax
  29.         shr     edx,16
  30.         xor     dl,byte [ebx+ecx]
  31.         and     edx,0FFh
  32.         shl     edx,2
  33.         shl     eax,8
  34.         xor     eax,[crc24table+edx]
  35.  
  36.         ; Следующий символ
  37.         inc     ecx
  38.         cmp     ecx,[dSize]
  39.         jb      @b
  40.  
  41. .loc_ret:
  42.         and     eax,0FFFFFFh
  43.  
  44.         pop     edx ecx ebx
  45.         ret
  46. endp
Функция принимает два параметра: lpData - указатель на блок данных, для которых надо посчитать CRC24, dSize - размер блока данных. На выходе в трех младших байтах регистра EAX возвращается результат вычисления контрольной суммы.

В приложении два варианта программ расчета CRC24 - с использованием таблицы и без нее.

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

CRC24.Demo.zip (7,251 bytes)


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

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

Комментарии

Отзывы посетителей сайта о статье
user (04.01.2015 в 18:24):
Это да,
начать с того, что накапливать сумму в регистре.
ManHunter (04.01.2015 в 18:00):
Нерационально как-то :) Можно оптимизировать и оптимизировать.
user (04.01.2015 в 16:05):
Вверну в качестве оффтопа.
Пару раз использовал для идентификации файлов простенький алгоритм подсчёта контрольной суммы PE-EXE, выдранный из микрософтовского линкера:

    ;;- - - - - -- - - - - - - - -- - -- - - - - -- - - - - -- - - ->8
     xor     edx,edx              ;;clear edx
     mov     SUM32,edx            ;;clear SUM32
     mov     ecx,length_of_file
     inc     ecx                  ;;round up to WORD
     mov     byte ptr [esi+ecx],0 ;;clear additional byte
     shr     ecx,1                ;;ecx=words in file
@@next_word:
     mov     dx,[esi]             ;;load next word of file
     add     SUM32,edx
     shr     SUM32,10h
     mov     dx,word ptr SUM32
     add     SUM32,edx
     add     esi,2                ;;esi->next word of file
loop @@next_word
     mov     eax,SUM32
     add     eax,length_of_file   ;;eax+=length_of_file
     mov     checksum,eax         ;;checksum=SUM32+length_of_file
    ;;- - - - - -- - - - - - - - -- - -- - - - - -- - - - - -- - - ->8
user (04.01.2015 в 15:48):
Упс.. Память подвела. Проверил - действительно, CRC16,32,*48*,64.
24 нет. По кратности спутал с CRC48..
ManHunter (04.01.2015 в 08:42):
ЦитатаНапример, в ревизоре ADINF в своё время опционально использовалась CRC24

Если я не ошибаюсь, из нестандартных хешей там использовалась CRC48, по крайней мере, в версии под MS-DOS. CRC24 в адинфе я что-то не припомню.

ЦитатаADinf32 пoзвoляет назначить различные виды кoнтpoля файлoв:
- полный контроль файлов с использованием алгоритмов CRC16 или CRC32,
- полный контроль файлов одновременно двумя алгоритмами (CRC48)

И то CRC48 тут - это совмещение CRC16 и CRC32
user (04.01.2015 в 02:04):
Приходит на ум только одно преимущество перед 32-бит контрольной суммой - при хранении большой базы данных о файлах экономится 25% места, если данные плотно упакованы в структурах..
Например, в ревизоре ADINF в своё время опционально использовалась CRC24, наверное, именно с целью экономии места для базы данных в сочетании с большей надёжностью, чем у CRC16.

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

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

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (30), AJAX (5), Assembler (362), COM (41), CSS (41), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (51), iconBIT (4), JavaScript (73), MySQL (13), Nikon (19), PDF (10), PHP (122), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (125), выпечка (28), выставки (119), генератор ПСЧ (10), графика (120), десерты (31), Египет (8), заготовки на зиму (47), закуска (22), закуска к пиву (24), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (316), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (69), мониторы (6), музеи (78), мультимедиа (76), мясо (62), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (49), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (130), полезные функции (42), прохождения (4), процессы (25), птица (20), путешествия (25), распаковка (22), реверсинг (52), рыба (35), салаты (19), сброс триала (4), сеть (36), система (178), Сокольники (8), соусы (14), супы (14), телефоны (10), Тунис (6), умный дом (13), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 35,173 раза
<< 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} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

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

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