Blog. Just Blog

Алгоритм хеширования MaHash8 на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
MaHash8 - эффективная функция с высокой производительностью, которая позволяет выполнять операции хеширования с минимальным количеством коллизий. Она основана на простых операциях, имеет очень понятную структуру и легко реализуется на различных языках программирования.

В алгоритме MaHash8 для хеширования используется таблица подстановки, позаимствованная из криптоалгоритма Skipjack. Если не хотите таскать готовую таблицу, то ее можно создавать динамически, используя формулы по приведенной ссылке.
  1. sTable  db 0a3h,0d7h,009h,083h,0f8h,048h,0f6h,0f4h,0b3h,021h,015h,078h
  2.         db 099h,0b1h,0afh,0f9h,0e7h,02dh,04dh,08ah,0ceh,04ch,0cah,02eh
  3.         db 052h,095h,0d9h,01eh,04eh,038h,044h,028h,00ah,0dfh,002h,0a0h
  4.         db 017h,0f1h,060h,068h,012h,0b7h,07ah,0c3h,0e9h,0fah,03dh,053h
  5.         db 096h,084h,06bh,0bah,0f2h,063h,09ah,019h,07ch,0aeh,0e5h,0f5h
  6.         db 0f7h,016h,06ah,0a2h,039h,0b6h,07bh,00fh,0c1h,093h,081h,01bh
  7.         db 0eeh,0b4h,01ah,0eah,0d0h,091h,02fh,0b8h,055h,0b9h,0dah,085h
  8.         db 03fh,041h,0bfh,0e0h,05ah,058h,080h,05fh,066h,00bh,0d8h,090h
  9.         db 035h,0d5h,0c0h,0a7h,033h,006h,065h,069h,045h,000h,094h,056h
  10.         db 06dh,098h,09bh,076h,097h,0fch,0b2h,0c2h,0b0h,0feh,0dbh,020h
  11.         db 0e1h,0ebh,0d6h,0e4h,0ddh,047h,04ah,01dh,042h,0edh,09eh,06eh
  12.         db 049h,03ch,0cdh,043h,027h,0d2h,007h,0d4h,0deh,0c7h,067h,018h
  13.         db 089h,0cbh,030h,01fh,08dh,0c6h,08fh,0aah,0c8h,074h,0dch,0c9h
  14.         db 05dh,05ch,031h,0a4h,070h,088h,061h,02ch,09fh,00dh,02bh,087h
  15.         db 050h,082h,054h,064h,026h,07dh,003h,040h,034h,04bh,01ch,073h
  16.         db 0d1h,0c4h,0fdh,03bh,0cch,0fbh,07fh,0abh,0e6h,03eh,05bh,0a5h
  17.         db 0adh,004h,023h,09ch,014h,051h,022h,0f0h,029h,079h,071h,07eh
  18.         db 0ffh,08ch,00eh,0e2h,00ch,0efh,0bch,072h,075h,06fh,037h,0a1h
  19.         db 0ech,0d3h,08eh,062h,08bh,086h,010h,0e8h,008h,077h,011h,0beh
  20.         db 092h,04fh,024h,0c5h,032h,036h,09dh,0cfh,0f3h,0a6h,0bbh,0ach
  21.         db 05eh,06ch,0a9h,013h,057h,025h,0b5h,0e3h,0bdh,0a8h,03ah,001h
  22.         db 005h,059h,02ah,046h
Ассемблерный вариант 32-битной версии функции MaHash8 выглядит примерно так. Я постарался ее максимально оптимизировать, в результате этого функция не использует никакие внешние данные и не требует выделения дополнительной памяти, все расчеты выполняются внутри нее.
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша MaHash8
  3. ; Автор: ManHunter / PCL
  4. ; https://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       EAX = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    MaHash8 lpData:DWORD, dSize:DWORD
  13.         locals
  14.                 hash1 dd ?
  15.                 hash2 dd ?
  16.         endl
  17.  
  18.         push    ebx ecx edx esi edi
  19.  
  20.         mov     esi,[lpData]
  21.         mov     eax,[dSize]
  22.         mov     [hash1],eax
  23.         mov     [hash2],eax
  24.         xor     ecx,ecx
  25. .loc_loop:
  26.         cmp     ecx,[dSize]
  27.         je      .loc_done
  28.  
  29.         mov     al,byte[esi]
  30.         add     eax,ecx
  31.         movzx   eax,al
  32.         movzx   edx,byte[sTable+eax]
  33.         add     [hash1],edx
  34.  
  35.         mov     edx,[hash1]
  36.         shl     edx,6
  37.         mov     eax,[hash1]
  38.         shr     eax,11
  39.         xor     eax,edx
  40.         add     eax,[hash1]
  41.         rol     eax,14
  42.         mov     [hash1],eax
  43.  
  44.         lodsb
  45.         add     eax,ecx
  46.         movzx   eax,al
  47.         movzx   edx,byte[sTable+eax]
  48.         add     [hash2],edx
  49.  
  50.         mov     edx,[hash2]
  51.         shl     edx,6
  52.         mov     eax,[hash2]
  53.         shr     eax,11
  54.         xor     eax,edx
  55.         add     eax,[hash2]
  56.         rol     eax,18
  57.         mov     [hash2],eax
  58.  
  59.         mov     ebx,[hash1]
  60.         mov     edi,[hash2]
  61.  
  62.         mov     eax,ebx
  63.         shr     eax,16
  64.         movzx   edx,ax
  65.         mov     eax,edi
  66.         shl     eax,16
  67.         or      eax,edx
  68.         mov     [hash1],eax
  69.  
  70.         mov     eax,edi
  71.         shr     eax,16
  72.         movzx   edx,ax
  73.         mov     eax,ebx
  74.         shl     eax,16
  75.         or      eax,edx
  76.         mov     [hash2],eax
  77.  
  78.         inc     ecx
  79.         jmp     .loc_loop
  80.  
  81. .loc_done:
  82.         mov     eax,[hash2]
  83.         xor     eax,[hash1]
  84.  
  85.         pop     edi esi edx ecx ebx
  86.         ret
  87. endp
На выходе передаются два параметра: lpData - указатель на блок данных, которые надо прохешировать, и dSize - длина этих данных. Результат возвращается в регистре EAX.

Еще более надежный вариант функции MaHash8v64, как можно догадаться из названия, выдает 64-битный хеш. Алгоритм расчета в точности совпадает с предыдущей функцией, разница только в том, что для формирования финального результата два 32-битных суб-хеша не сжимаются в один DWORD, а возвращаются каждый как самостоятельная часть хеша.
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша MaHash8v64
  3. ; Автор: ManHunter / PCL
  4. ; https://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       EAX:EDX = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    MaHash8v64 lpData:DWORD, dSize:DWORD
  13.         locals
  14.                 hash1 dd ?
  15.                 hash2 dd ?
  16.         endl
  17.  
  18.         push    ebx ecx esi edi
  19.  
  20.         mov     esi,[lpData]
  21.         mov     eax,[dSize]
  22.         mov     [hash1],eax
  23.         mov     [hash2],eax
  24.         xor     ecx,ecx
  25. .loc_loop:
  26.         cmp     ecx,[dSize]
  27.         je      .loc_done
  28.  
  29.         mov     al,byte[esi]
  30.         add     eax,ecx
  31.         movzx   eax,al
  32.         movzx   edx,byte[sTable+eax]
  33.         add     [hash1],edx
  34.  
  35.         mov     edx,[hash1]
  36.         shl     edx,6
  37.         mov     eax,[hash1]
  38.         shr     eax,11
  39.         xor     eax,edx
  40.         add     eax,[hash1]
  41.         rol     eax,14
  42.         mov     [hash1],eax
  43.  
  44.         lodsb
  45.         add     eax,ecx
  46.         movzx   eax,al
  47.         movzx   edx,byte[sTable+eax]
  48.         add     [hash2],edx
  49.  
  50.         mov     edx,[hash2]
  51.         shl     edx,6
  52.         mov     eax,[hash2]
  53.         shr     eax,11
  54.         xor     eax,edx
  55.         add     eax,[hash2]
  56.         rol     eax,18
  57.         mov     [hash2],eax
  58.  
  59.         mov     ebx,[hash1]
  60.         mov     edi,[hash2]
  61.  
  62.         mov     eax,ebx
  63.         shr     eax,16
  64.         movzx   edx,ax
  65.         mov     eax,edi
  66.         shl     eax,16
  67.         or      eax,edx
  68.         mov     [hash1],eax
  69.  
  70.         mov     eax,edi
  71.         shr     eax,16
  72.         movzx   edx,ax
  73.         mov     eax,ebx
  74.         shl     eax,16
  75.         or      eax,edx
  76.         mov     [hash2],eax
  77.  
  78.         inc     ecx
  79.         jmp     .loc_loop
  80.  
  81. .loc_done:
  82.         mov     eax,[hash1]
  83.         mov     edx,[hash2]
  84.  
  85.         pop     edi esi ecx ebx
  86.         ret
  87. endp
Параметры вызова точно такие же, как и у предыдущей функции, а результат возвращается в паре регистров EAX:EDX.

В приложении примеры программ с исходными текстами, реализующие вычисление хеша по алгоритму MaHash8 и MaHash8v64.

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

MaHash8.Demo.zip (6,996 bytes)


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

Метки: Assembler, хеши

Комментарии

Отзывы посетителей сайта о статье
DRON (22.10.2024 в 15:56):
Таблица тут явно лишняя: чисто математически она вообще ни на что не влияет, потому что просто переводит входной байт в байт с другим значением.
Такое может работать только если нужно подогнать хеш-функцию к конкретным входным данным (например языку текста https://doxygen.reactos.org/d7..._source.html ), но для универсальной хеш-функции это бессмысленно.
ManHunter (22.10.2024 в 01:01):
Ну как сказать.. Если учесть, что CRC32 реализовано уже на уровне базовых команд современных процессоров, то в глобальном масштабе, скорее всего, этот алгоритм проиграет. Но если опять же учесть современные мощности процессоров, то подобные микро-нано-секунды в реальных проектах вряд ли будут иметь прям капец какое принципиальное значение. А вот когда речь зайдет о практическом применении в прошивках микропроцессоров, где важен каждый байт, то вопрос выбора может иметь место.

В конце концов, кто мешает засечь время и прохешировать стопицот раз какой-нибудь HD-видосик на 40-50 гигов?

Кстати, по коллизиям этот алго вполне сопоставим с CRC32.
Zeroes (22.10.2024 в 00:50):
А нет сравнения скорости расчёта по сравнению например с CRC32? в инете сходу не нашёл :)

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

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

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