Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
CRC24 - еще одна разновидность контрольной суммы. Как можно увидеть из названия, ее размер составляет 24 бита, или 3 байта. Я пока не нашел практического применения этому хешу, так же как и программ, использующих его. Но раз есть алгоритм, то почему бы его не реализовать на Ассемблере? Начнем с наиболее компактной реализации без использования таблицы.
  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.
  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'ы.
  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)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 4593 | Комментариев: 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 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2020
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.29 сек. / MySQL: 2 (0.2145 сек.) / Память: 4.75 Mb
Наверх