Алгоритм хеширования XXHash32 на Ассемблере
Алгоритм хеширования XXHash32 на Ассемблере
xxHash32 - это быстрая некриптографическая хеш-функция, генерирующая 32-битный хеш. Ее автор - Yann Collet, разработчик библиотеки xxHash, также широко известный как создатель высокоскоростного алгоритма сжатия LZ4. Сам xxHash представляет собой чрезвычайно быстрый хеш-алгоритм, работающий практически на пределе скорости доступа к оперативной памяти. Существует несколько его вариантов: XXH32, XXH64, а также более современные XXH3_64bits и XXH3_128bits. В данном случае речь пойдет о классическом XXHash32.
Алгоритм выделяется крайне высокой производительностью, до нескольких гигабайт в секунду на современных процессорах, при этом обеспечивая качественное распределение хеш-значений и низкую вероятность коллизий. Поддержка seed позволяет гибко управлять результатом хеширования, что особенно полезно при построении хеш-таблиц или генерации идентификаторов. Важно помнить, что XXHash32 не предназначен для криптографического использования, он не обеспечивает защиту от преднамеренных атак и не подходит для хранения паролей или цифровых подписей.
XXH32 широко используется в современных API и библиотеках, хотя и не входит в стандартные библиотеки большинства языков программирования. Обычно его подключают через популярные сторонние пакеты. По качеству хеша, равномерности распределения и устойчивости к простым паттернам, он сопоставим с такими решениями, как MurmurHash или SipHash, и другими "быстрыми" некриптографическими хешами. При этом XXH32 выигрывает за счет простоты реализации, хорошо проанализированного, предсказуемого поведения и поддержки начального значения (seed), что позволяет гибко управлять результатом хеширования, например, для изоляции хеш-таблиц или генерации разных хешей из одних и тех же данных.
Code (Assembler) : Убрать нумерацию
- ;---------------------------------------------
- ; Функция вычисления хеша XXHash32
- ;---------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; dSize - длина строки
- ; dSeed - параметр инициализации
- ; На выходе:
- ; EAX = полученный хеш
- ;---------------------------------------------
- proc XXHash32 lpData:DWORD, dSize:DWORD, dSeed:DWORD
- ; 32-битные константы XXHash32
- PRIME32_1 = 0x9E3779B1
- PRIME32_2 = 0x85EBCA77
- PRIME32_3 = 0xC2B2AE3D
- PRIME32_4 = 0x27D4EB2F
- PRIME32_5 = 0x165667B1
- push esi edi ebx ecx edx
- mov esi,[lpData]
- mov ecx,[dSize]
- mov edx,[dSeed]
- mov eax,edx
- add eax,PRIME32_5
- add eax,ecx
- cmp ecx,16
- jb .loc_skip_main
- ; Инициализация 4-х аккумуляторов
- mov eax,edx
- add eax,PRIME32_1
- add eax,PRIME32_2
- mov ebx,edx
- add ebx,PRIME32_2
- mov edi,edx
- sub edi,PRIME32_1
- mov ebp,edx
- sub ebp,PRIME32_2
- .loc_loop:
- cmp ecx,16
- jb .loc_after_main
- ; Aккумуляторов 1
- mov edx,[esi]
- imul edx,PRIME32_2
- add eax,edx
- rol eax,13
- imul eax,PRIME32_1
- ; Aккумуляторов 2
- mov edx,[esi+4]
- imul edx,PRIME32_2
- add ebx,edx
- rol ebx,13
- imul ebx,PRIME32_1
- ; Aккумуляторов 3
- mov edx,[esi+8]
- imul edx,PRIME32_2
- add edi,edx
- rol edi,13
- imul edi,PRIME32_1
- ; Aккумуляторов 4
- mov edx,[esi+12]
- imul edx,PRIME32_2
- add ebp,edx
- rol ebp,13
- imul ebp,PRIME32_1
- add esi,16
- sub ecx,16
- jmp .loc_loop
- .loc_after_main:
- rol eax,1
- mov edx,ebx
- rol edx,7
- add eax,edx
- mov edx,edi
- rol edx,12
- add eax,edx
- mov edx,ebp
- rol edx,18
- add eax,edx
- ; Обработка 4‑байтных кусков
- .loc_skip_main:
- cmp ecx,4
- jb .loc_tail
- mov edx,[esi]
- imul edx,PRIME32_3
- add eax,edx
- rol eax,17
- imul eax,PRIME32_4
- add esi,4
- sub ecx,4
- jmp .loc_skip_main
- ; Обработка оставшихся байт
- .loc_tail:
- cmp ecx,0
- je .loc_final
- movzx edx,byte [esi]
- imul edx,PRIME32_5
- add eax,edx
- rol eax,11
- imul eax,PRIME32_1
- inc esi
- dec ecx
- jmp .loc_tail
- .loc_final:
- ; Финальная лавина
- mov edx,eax
- shr edx,15
- xor eax,edx
- imul eax,PRIME32_2
- mov edx,eax
- shr edx,13
- xor eax,edx
- imul eax,PRIME32_3
- mov edx,eax
- shr edx,16
- xor eax,edx
- pop edx ecx ebx edi esi
- pop ebp
- retn
- endp
Интересный факт: константы, используемые в XXHash32, например, 0x9E3779B1 и 0x85EBCA77, традиционно используются в теории хеширования как "золотые" числа. Это значение связано с золотым сечением и специально выбрано, чтобы минимизировать систематические коллизии при хешировании последовательных ключей, целых чисел или регулярных паттернов. Комбинация нескольких подобных констант на разных этапах алгоритма - основном цикле, обработке хвоста и финальной "лавине", создает более хаотичное и равномерное распределение хеш-значений, что повышает общую надежность функции.
В приложении пример программы с исходным текстом, которая считает хеш XXHash32 для введенной строки.
Пример программы с исходным текстом (FASM)
Просмотров: 271 | Комментариев: 0
Комментарии
Отзывы посетителей сайта о статье
Комментариeв нет
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 37,937 раз
Поблагодарили 37,937 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 330 |
 |
 |