Расчет MurmurHash на Ассемблере
MurmurHash - семейство простых и быстрых хеш-функций. Необычное название произошло от двух базовых операций - умножение (MUltiply) и циклический битовый сдвиг (Rotate), которые используются в основном цикле хеширования. К достоинствам алгоритма Murmur можно отнести простоту реализации, хорошее распределение, мощный лавинный эффект, высокую скорость работы и сравнительно высокую устойчивость к коллизиям. Первая версия, разработанная Остином Апплеби (Austin Appleby), самая простая в реализации:Code (Assembler) : Убрать нумерацию
- ;-----------------------------------------------------------------------
- ; Функция вычисления хеша Murmur
- ; Автор: ManHunter / PCL
- ; http://www.manhunter.ru
- ;-----------------------------------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; dSize - длина строки
- ; dSeed - соль
- ; На выходе:
- ; EAX = полученный хеш
- ;-----------------------------------------------------------------------
- proc Murmur lpData:DWORD, dSize:DWORD, dSeed:DWORD
- push ebx ecx edx esi edi
- MAGIC = 0xC6A4A793
- mov ebx,[dSize]
- imul ecx,ebx,MAGIC
- mov edx,[dSeed]
- xor ecx,edx
- mov esi,[lpData]
- .loc_loop:
- cmp ebx,4
- jb .loop_done
- mov eax,dword [esi]
- add ecx,eax
- imul ecx,MAGIC
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- add esi,4
- sub ebx,4
- jmp .loc_loop
- .loop_done:
- cmp ebx,3
- je .loc_tail_3
- cmp ebx,2
- je .loc_tail_2
- cmp ebx,1
- je .loc_tail_1
- jmp .loc_finish
- .loc_tail_3:
- movzx eax,byte[esi+2]
- shl eax,16
- add ecx,eax
- .loc_tail_2:
- movzx eax,byte[esi+1]
- shl eax,8
- add ecx,eax
- .loc_tail_1:
- movzx eax,byte[esi]
- add ecx,eax
- imul ecx,MAGIC
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- .loc_finish:
- imul ecx,MAGIC
- mov eax,ecx
- shr eax,10
- xor ecx,eax
- imul ecx,MAGIC
- mov eax,ecx
- shr eax,17
- xor eax,ecx
- pop edi esi edx ecx ebx
- ret
- endp
Более улучшенный вариант алгоритма получил название Murmur2. Улучшения, в первую очередь, были сделаны для сокращения количества возможных коллизий. По скорости работы и объему кода от первоначального алгоритма отличается не намного. Есть варианты для подсчета 32-битного или 64-битного хеша.
Code (Assembler) : Убрать нумерацию
- ;-----------------------------------------------------------------------
- ; Функция вычисления хеша Murmur2 (32-bit)
- ; Автор: ManHunter / PCL
- ; http://www.manhunter.ru
- ;-----------------------------------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; dSize - длина строки
- ; dSeed - соль
- ; На выходе:
- ; EAX = полученный хеш
- ;-----------------------------------------------------------------------
- proc Murmur2 lpData:DWORD, dSize:DWORD, dSeed:DWORD
- push ebx ecx edx esi edi
- MAGIC = 0x5BD1E995
- mov esi,[lpData]
- mov ebx,[dSize]
- mov ecx,[dSeed]
- xor ecx,ebx
- .loc_loop:
- cmp ebx,4
- jb .loop_done
- imul ecx,MAGIC
- movzx edx,byte [esi+1]
- movzx eax,byte [esi]
- shl edx,8
- or eax,edx
- movzx edx,byte [esi+2]
- shl edx,16
- or eax,edx
- movzx edx,byte [esi+3]
- shl edx,24
- or eax,edx
- imul eax,MAGIC
- mov edx,eax
- shr edx,24
- xor eax,edx
- imul eax,MAGIC
- xor ecx,eax
- add esi,4
- sub ebx,4
- jmp .loc_loop
- .loop_done:
- cmp ebx,3
- je .loc_tail_3
- cmp ebx,2
- je .loc_tail_2
- cmp ebx,1
- je .loc_tail_1
- jmp .loc_finish
- .loc_tail_3:
- movzx eax,byte[esi+2]
- shl eax,16
- xor ecx,eax
- .loc_tail_2:
- movzx eax,byte[esi+1]
- shl eax,8
- xor ecx,eax
- .loc_tail_1:
- movzx eax,byte[esi]
- xor ecx,eax
- imul ecx,MAGIC
- .loc_finish:
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,MAGIC
- mov eax,ecx
- shr eax,15
- xor eax,ecx
- pop edi esi edx ecx ebx
- ret
- endp
Последняя на сегодняшний день версия Murmur получила название, как несложно догадаться, Murmur3. Она также обладает равномерным распределением и большой скоростью. Есть варианты реализации 32-битного или 128-битного хеша.
Code (Assembler) : Убрать нумерацию
- ;-----------------------------------------------------------------------
- ; Функция вычисления хеша Murmur3 (32-bit)
- ; Автор: ManHunter / PCL
- ; http://www.manhunter.ru
- ;-----------------------------------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; dSize - длина строки
- ; dSeed - соль
- ; На выходе:
- ; EAX = полученный хеш
- ;-----------------------------------------------------------------------
- proc Murmur3 lpData:DWORD, dSize:DWORD, dSeed:DWORD
- push ebx ecx edx esi edi
- MAGIC1 = 0xCC9E2D51
- MAGIC2 = 0x1B873593
- mov ebx,[dSize]
- mov ecx,[dSeed]
- mov esi,[lpData]
- .loc_loop:
- cmp ebx,4
- jb .loop_done
- mov eax,dword [esi]
- imul eax,MAGIC1
- mov edx,eax
- shr edx,17
- shl eax,15
- or eax,edx
- imul eax,MAGIC2
- xor ecx,eax
- mov edx,ecx
- shr edx,19
- shl ecx,13
- or ecx,edx
- imul ecx,5
- add ecx,0xE6546B64
- add esi,4
- sub ebx,4
- jmp .loc_loop
- .loop_done:
- mov edx,0
- cmp ebx,3
- je .loc_tail_3
- cmp ebx,2
- je .loc_tail_2
- cmp ebx,1
- je .loc_tail_1
- jmp .loc_finish
- .loc_tail_3:
- movzx eax,byte[esi+2]
- shl eax,16
- xor edx,eax
- .loc_tail_2:
- movzx eax,byte[esi+1]
- shl eax,8
- xor edx,eax
- .loc_tail_1:
- movzx eax,byte[esi]
- xor edx,eax
- imul edx,MAGIC1
- mov eax,edx
- shr eax,17
- shl edx,15
- or edx,eax
- imul edx,MAGIC2
- xor ecx,edx
- .loc_finish:
- mov eax,[dSize]
- xor ecx,eax
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- imul ecx,0x85EBCA6B
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,0xC2B2AE35
- mov eax,ecx
- shr eax,16
- xor eax,ecx
- pop edi esi edx ecx ebx
- ret
- endp
По просьбам трудящихся выкладываю ассемблерную версию алгоритма Murmur3 для вычисления 128-битного хеша. К сожалению, я так и не нашел официальных векторов для тестирования алгоритма, поэтому будьте внимательны при его использовании. Но вроде бы нигде не накосячил. Если что - пишите в камменты.
Code (Assembler) : Убрать нумерацию
- ;-----------------------------------------------------------------------
- ; Функция вычисления хеша Murmur3 (128-bit)
- ; Автор: ManHunter / PCL
- ; http://www.manhunter.ru
- ;-----------------------------------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; dSize - длина строки
- ; dSeed - соль
- ; На выходе:
- ; EAX:EBX:ECX:EDX = полученный хеш
- ;-----------------------------------------------------------------------
- proc Murmur3 lpData:DWORD, dSize:DWORD, dSeed:DWORD
- locals
- h1 dd ?
- h2 dd ?
- h3 dd ?
- h4 dd ?
- endl
- push esi edi
- MAGIC1 = 0x239B961B
- MAGIC2 = 0xAB0E9789
- MAGIC3 = 0x38B34AE5
- MAGIC4 = 0xA1E38B93
- mov ebx,[dSize]
- mov ecx,[dSeed]
- mov [h1],ecx
- mov [h2],ecx
- mov [h3],ecx
- mov [h4],ecx
- mov esi,[lpData]
- .loc_loop:
- cmp ebx,16
- jb .loop_done
- mov eax,dword [esi+4*0]
- imul eax,MAGIC1
- mov edx,eax
- shr edx,17
- shl eax,15
- or eax,edx
- imul eax,MAGIC2
- xor [h1],eax
- mov eax,[h1]
- mov edx,eax
- shr edx,13
- shl eax,19
- or eax,edx
- add eax,[h2]
- imul eax,5
- add eax,0x561CCD1B
- mov [h1],eax
- mov eax,dword [esi+4*1]
- imul eax,MAGIC2
- mov edx,eax
- shr edx,16
- shl eax,16
- or eax,edx
- imul eax,MAGIC3
- xor [h2],eax
- mov eax,[h2]
- mov edx,eax
- shr edx,15
- shl eax,17
- or eax,edx
- add eax,[h3]
- imul eax,5
- add eax,0x0BCAA747
- mov [h2],eax
- mov eax,dword [esi+4*2]
- imul eax,MAGIC3
- mov edx,eax
- shr edx,19
- shl eax,17
- or eax,edx
- imul eax,MAGIC4
- xor [h3],eax
- mov eax,[h3]
- mov edx,eax
- shr edx,17
- shl eax,15
- or eax,edx
- add eax,[h4]
- imul eax,5
- add eax,0x96CD1C35
- mov [h3],eax
- mov eax,dword [esi+4*3]
- imul eax,MAGIC4
- mov edx,eax
- shr edx,14
- shl eax,18
- or eax,edx
- imul eax,MAGIC1
- xor [h4],eax
- mov eax,[h4]
- mov edx,eax
- shr edx,19
- shl eax,13
- or eax,edx
- add eax,[h1]
- imul eax,5
- add eax,0x32AC3B17
- mov [h4],eax
- add esi,16
- sub ebx,16
- jmp .loc_loop
- .loop_done:
- xor edx,edx
- cmp ebx,15
- je .loc_tail_15
- cmp ebx,14
- je .loc_tail_14
- cmp ebx,13
- je .loc_tail_13
- cmp ebx,12
- je .loc_tail_12
- cmp ebx,11
- je .loc_tail_11
- cmp ebx,10
- je .loc_tail_10
- cmp ebx,9
- je .loc_tail_9
- cmp ebx,8
- je .loc_tail_8
- cmp ebx,7
- je .loc_tail_7
- cmp ebx,6
- je .loc_tail_6
- cmp ebx,5
- je .loc_tail_5
- cmp ebx,4
- je .loc_tail_4
- cmp ebx,3
- je .loc_tail_3
- cmp ebx,2
- je .loc_tail_2
- cmp ebx,1
- je .loc_tail_1
- jmp .loc_finish
- .loc_tail_15:
- movzx edx,byte[esi+14]
- shl edx,16
- .loc_tail_14:
- movzx eax,byte[esi+13]
- shl eax,8
- xor edx,eax
- .loc_tail_13:
- movzx eax,byte[esi+12]
- xor edx,eax
- imul edx,MAGIC4
- mov eax,edx
- shr eax,14
- shl edx,18
- or edx,eax
- imul edx,MAGIC1
- xor [h4],edx
- .loc_tail_12:
- movzx edx,byte[esi+11]
- shl edx,24
- .loc_tail_11:
- movzx eax,byte[esi+10]
- shl eax,16
- xor edx,eax
- .loc_tail_10:
- movzx eax,byte[esi+9]
- shl eax,8
- xor edx,eax
- .loc_tail_9:
- movzx eax,byte[esi+8]
- xor edx,eax
- imul edx,MAGIC3
- mov eax,edx
- shr eax,15
- shl edx,17
- or edx,eax
- imul edx,MAGIC4
- xor [h3],edx
- .loc_tail_8:
- movzx edx,byte[esi+7]
- shl edx,24
- .loc_tail_7:
- movzx eax,byte[esi+6]
- shl eax,16
- xor edx,eax
- .loc_tail_6:
- movzx eax,byte[esi+5]
- shl eax,8
- xor edx,eax
- .loc_tail_5:
- movzx eax,byte[esi+4]
- xor edx,eax
- imul edx,MAGIC2
- mov eax,edx
- shr eax,16
- shl edx,16
- or edx,eax
- imul edx,MAGIC3
- xor [h2],edx
- .loc_tail_4:
- movzx edx,byte[esi+3]
- shl edx,24
- .loc_tail_3:
- movzx eax,byte[esi+2]
- shl eax,16
- xor edx,eax
- .loc_tail_2:
- movzx eax,byte[esi+1]
- shl eax,8
- xor edx,eax
- .loc_tail_1:
- movzx eax,byte[esi+0]
- xor edx,eax
- imul edx,MAGIC1
- mov eax,edx
- shr eax,17
- shl edx,15
- or edx,eax
- imul edx,MAGIC2
- xor [h1],edx
- .loc_finish:
- mov eax,[dSize]
- xor [h1],eax
- xor [h2],eax
- xor [h3],eax
- xor [h4],eax
- mov eax,[h1]
- add eax,[h2]
- add eax,[h3]
- add eax,[h4]
- mov [h1],eax
- add [h2],eax
- add [h3],eax
- add [h4],eax
- mov ecx,[h1]
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- imul ecx,0x85ebca6b
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,0xc2b2ae35
- mov eax,ecx
- shr eax,16
- xor eax,ecx
- mov [h1],eax
- mov ecx,[h2]
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- imul ecx,0x85ebca6b
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,0xc2b2ae35
- mov eax,ecx
- shr eax,16
- xor eax,ecx
- mov [h2],eax
- mov ecx,[h3]
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- imul ecx,0x85ebca6b
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,0xc2b2ae35
- mov eax,ecx
- shr eax,16
- xor eax,ecx
- mov [h3],eax
- mov ecx,[h4]
- mov eax,ecx
- shr eax,16
- xor ecx,eax
- imul ecx,0x85ebca6b
- mov eax,ecx
- shr eax,13
- xor ecx,eax
- imul ecx,0xc2b2ae35
- mov eax,ecx
- shr eax,16
- xor eax,ecx
- mov [h4],eax
- mov eax,[h1]
- add eax,[h2]
- add eax,[h3]
- add eax,[h4]
- mov [h1],eax
- mov ebx,[h2]
- mov ecx,[h3]
- mov edx,[h4]
- add ebx,eax
- add ecx,eax
- add edx,eax
- pop edi esi
- ret
- endp
Есть еще несколько вариантов алгоритма Murmur, основанных на различных версиях оригинальных алгоритмов. Здесь я их приводить не буду, при желании можете найти их сами и доработать приведенные в статье функции в соответствии с вашими потребностями.
В приложении примеры программ с исходными текстами, реализующие все четыре перечисленные в статье варианта алгоритма Murmur.
Просмотров: 2992 | Комментариев: 12
Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье
ManHunter
(20.12.2020 в 18:30):
Может быть когда-нибудь.
FFFF
(20.12.2020 в 17:51):
А 64-бит murmur2?
Petya
(10.12.2020 в 16:37):
Странно, что нет картинки с котиком...
ManHunter
(15.02.2017 в 17:29):
Из википедии :) Название понравилось.
DimitarSerg
(15.02.2017 в 17:25):
Если не секрет, откуда ? :)
Ну то есть я повидал кучу всего за годы реверса, но такого ни в одной проге не припомню.
Ну то есть я повидал кучу всего за годы реверса, но такого ни в одной проге не припомню.
ManHunter
(08.02.2017 в 19:10):
В JS-реализациях Murmur-128 есть свои особенности, из-за которых результат отличается от Сишного. Совпадает результат только если строка короче 16 символов и цикл хеширования не задействуется. Я портировал на Ассемблер Сишный вариант.
darkz
(08.02.2017 в 19:00):
Для колекции.)Хеширует все правильно,я проверил через онлайн сайтик http://murmurhash.shorelabs.com
ManHunter
(08.02.2017 в 17:24):
Если не секрет, а нафига?
darkz
(08.02.2017 в 14:06):
thanks
ManHunter
(08.02.2017 в 13:47):
Готово
ManHunter
(08.02.2017 в 07:50):
Чтобы выложить, его сначала написать надо :))
darkz
(08.02.2017 в 03:45):
ManHunter Привет! Вы писали "Есть варианты реализации 32-битного или 128-битного хеша" Вы не могли бы выложить алгоритм Murmur3 для подсчета 128-битного хеша.
Добавить комментарий
Заполните форму для добавления комментария