Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
MurmurHash - семейство простых и быстрых хеш-функций. Необычное название произошло от двух базовых операций - умножение (MUltiply) и циклический битовый сдвиг (Rotate), которые используются в основном цикле хеширования. К достоинствам алгоритма Murmur можно отнести простоту реализации, хорошее распределение, мощный лавинный эффект, высокую скорость работы и сравнительно высокую устойчивость к коллизиям. Первая версия, разработанная Остином Апплеби (Austin Appleby), самая простая в реализации:
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша Murmur
  3. ; Автор: ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ;       dSeed  - соль
  10. ; На выходе:
  11. ;       EAX = полученный хеш
  12. ;-----------------------------------------------------------------------
  13. proc    Murmur lpData:DWORD, dSize:DWORD, dSeed:DWORD
  14.         push    ebx ecx edx esi edi
  15.  
  16.         MAGIC = 0xC6A4A793
  17.  
  18.         mov     ebx,[dSize]
  19.         imul    ecx,ebx,MAGIC
  20.         mov     edx,[dSeed]
  21.         xor     ecx,edx
  22.  
  23.         mov     esi,[lpData]
  24.  
  25. .loc_loop:
  26.         cmp     ebx,4
  27.         jb      .loop_done
  28.  
  29.         mov     eax,dword [esi]
  30.         add     ecx,eax
  31.         imul    ecx,MAGIC
  32.         mov     eax,ecx
  33.         shr     eax,16
  34.         xor     ecx,eax
  35.  
  36.         add     esi,4
  37.         sub     ebx,4
  38.         jmp     .loc_loop
  39.  
  40. .loop_done:
  41.         cmp     ebx,3
  42.         je      .loc_tail_3
  43.         cmp     ebx,2
  44.         je      .loc_tail_2
  45.         cmp     ebx,1
  46.         je      .loc_tail_1
  47.         jmp     .loc_finish
  48.  
  49. .loc_tail_3:
  50.         movzx   eax,byte[esi+2]
  51.         shl     eax,16
  52.         add     ecx,eax
  53. .loc_tail_2:
  54.         movzx   eax,byte[esi+1]
  55.         shl     eax,8
  56.         add     ecx,eax
  57. .loc_tail_1:
  58.         movzx   eax,byte[esi]
  59.         add     ecx,eax
  60.         imul    ecx,MAGIC
  61.         mov     eax,ecx
  62.         shr     eax,16
  63.         xor     ecx,eax
  64.  
  65. .loc_finish:
  66.         imul    ecx,MAGIC
  67.  
  68.         mov     eax,ecx
  69.         shr     eax,10
  70.         xor     ecx,eax
  71.  
  72.         imul    ecx,MAGIC
  73.  
  74.         mov     eax,ecx
  75.         shr     eax,17
  76.         xor     eax,ecx
  77.  
  78.         pop     edi esi edx ecx ebx
  79.         ret
  80. endp
На входе функции передаются три параметра: lpData - указатель на строку данных, для которых надо подсчитать хеш, dSize - размер данных (длина строки), dSeed - соль для пользовательской модификации хеша.

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

Последняя на сегодняшний день версия Murmur получила название, как несложно догадаться, Murmur3. Она также обладает равномерным распределением и большой скоростью. Есть варианты реализации 32-битного или 128-битного хеша.
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша Murmur3 (32-bit)
  3. ; Автор: ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ;       dSeed  - соль
  10. ; На выходе:
  11. ;       EAX = полученный хеш
  12. ;-----------------------------------------------------------------------
  13. proc    Murmur3 lpData:DWORD, dSize:DWORD, dSeed:DWORD
  14.         push    ebx ecx edx esi edi
  15.  
  16.         MAGIC1 = 0xCC9E2D51
  17.         MAGIC2 = 0x1B873593
  18.  
  19.         mov     ebx,[dSize]
  20.         mov     ecx,[dSeed]
  21.  
  22.         mov     esi,[lpData]
  23.  
  24. .loc_loop:
  25.         cmp     ebx,4
  26.         jb      .loop_done
  27.  
  28.         mov     eax,dword [esi]
  29.         imul    eax,MAGIC1
  30.  
  31.         mov     edx,eax
  32.         shr     edx,17
  33.         shl     eax,15
  34.         or      eax,edx
  35.  
  36.         imul    eax,MAGIC2
  37.  
  38.         xor     ecx,eax
  39.  
  40.         mov     edx,ecx
  41.         shr     edx,19
  42.         shl     ecx,13
  43.         or      ecx,edx
  44.         imul    ecx,5
  45.         add     ecx,0xE6546B64
  46.  
  47.         add     esi,4
  48.         sub     ebx,4
  49.         jmp     .loc_loop
  50.  
  51. .loop_done:
  52.         mov     edx,0
  53.  
  54.         cmp     ebx,3
  55.         je      .loc_tail_3
  56.         cmp     ebx,2
  57.         je      .loc_tail_2
  58.         cmp     ebx,1
  59.         je      .loc_tail_1
  60.         jmp     .loc_finish
  61.  
  62. .loc_tail_3:
  63.         movzx   eax,byte[esi+2]
  64.         shl     eax,16
  65.         xor     edx,eax
  66. .loc_tail_2:
  67.         movzx   eax,byte[esi+1]
  68.         shl     eax,8
  69.         xor     edx,eax
  70. .loc_tail_1:
  71.         movzx   eax,byte[esi]
  72.         xor     edx,eax
  73.  
  74.         imul    edx,MAGIC1
  75.  
  76.         mov     eax,edx
  77.         shr     eax,17
  78.         shl     edx,15
  79.         or      edx,eax
  80.  
  81.         imul    edx,MAGIC2
  82.  
  83.         xor     ecx,edx
  84.  
  85. .loc_finish:
  86.         mov     eax,[dSize]
  87.         xor     ecx,eax
  88.  
  89.         mov     eax,ecx
  90.         shr     eax,16
  91.         xor     ecx,eax
  92.         imul    ecx,0x85EBCA6B
  93.         mov     eax,ecx
  94.         shr     eax,13
  95.         xor     ecx,eax
  96.         imul    ecx,0xC2B2AE35
  97.         mov     eax,ecx
  98.         shr     eax,16
  99.         xor     eax,ecx
  100.  
  101.         pop     edi esi edx ecx ebx
  102.         ret
  103. endp
Параметры вызова и значения параметров точно такие же, как и у предыдущих функций Murmur.

По просьбам трудящихся выкладываю ассемблерную версию алгоритма Murmur3 для вычисления 128-битного хеша. К сожалению, я так и не нашел официальных векторов для тестирования алгоритма, поэтому будьте внимательны при его использовании. Но вроде бы нигде не накосячил. Если что - пишите в камменты.
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша Murmur3 (128-bit)
  3. ; Автор: ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ;       dSeed  - соль
  10. ; На выходе:
  11. ;       EAX:EBX:ECX:EDX = полученный хеш
  12. ;-----------------------------------------------------------------------
  13. proc    Murmur3 lpData:DWORD, dSize:DWORD, dSeed:DWORD
  14.  
  15.         locals
  16.                 h1 dd ?
  17.                 h2 dd ?
  18.                 h3 dd ?
  19.                 h4 dd ?
  20.         endl
  21.  
  22.         push    esi edi
  23.  
  24.         MAGIC1 = 0x239B961B
  25.         MAGIC2 = 0xAB0E9789
  26.         MAGIC3 = 0x38B34AE5
  27.         MAGIC4 = 0xA1E38B93
  28.  
  29.         mov     ebx,[dSize]
  30.         mov     ecx,[dSeed]
  31.  
  32.         mov     [h1],ecx
  33.         mov     [h2],ecx
  34.         mov     [h3],ecx
  35.         mov     [h4],ecx
  36.  
  37.         mov     esi,[lpData]
  38.  
  39. .loc_loop:
  40.         cmp     ebx,16
  41.         jb      .loop_done
  42.  
  43.         mov     eax,dword [esi+4*0]
  44.         imul    eax,MAGIC1
  45.  
  46.         mov     edx,eax
  47.         shr     edx,17
  48.         shl     eax,15
  49.         or      eax,edx
  50.  
  51.         imul    eax,MAGIC2
  52.         xor     [h1],eax
  53.  
  54.         mov     eax,[h1]
  55.         mov     edx,eax
  56.         shr     edx,13
  57.         shl     eax,19
  58.         or      eax,edx
  59.         add     eax,[h2]
  60.         imul    eax,5
  61.         add     eax,0x561CCD1B
  62.         mov     [h1],eax
  63.  
  64.         mov     eax,dword [esi+4*1]
  65.         imul    eax,MAGIC2
  66.  
  67.         mov     edx,eax
  68.         shr     edx,16
  69.         shl     eax,16
  70.         or      eax,edx
  71.  
  72.         imul    eax,MAGIC3
  73.         xor     [h2],eax
  74.  
  75.         mov     eax,[h2]
  76.         mov     edx,eax
  77.         shr     edx,15
  78.         shl     eax,17
  79.         or      eax,edx
  80.         add     eax,[h3]
  81.         imul    eax,5
  82.         add     eax,0x0BCAA747
  83.         mov     [h2],eax
  84.  
  85.         mov     eax,dword [esi+4*2]
  86.         imul    eax,MAGIC3
  87.  
  88.         mov     edx,eax
  89.         shr     edx,19
  90.         shl     eax,17
  91.         or      eax,edx
  92.  
  93.         imul    eax,MAGIC4
  94.         xor     [h3],eax
  95.  
  96.         mov     eax,[h3]
  97.         mov     edx,eax
  98.         shr     edx,17
  99.         shl     eax,15
  100.         or      eax,edx
  101.         add     eax,[h4]
  102.         imul    eax,5
  103.         add     eax,0x96CD1C35
  104.         mov     [h3],eax
  105.  
  106.         mov     eax,dword [esi+4*3]
  107.         imul    eax,MAGIC4
  108.  
  109.         mov     edx,eax
  110.         shr     edx,14
  111.         shl     eax,18
  112.         or      eax,edx
  113.  
  114.         imul    eax,MAGIC1
  115.         xor     [h4],eax
  116.  
  117.         mov     eax,[h4]
  118.         mov     edx,eax
  119.         shr     edx,19
  120.         shl     eax,13
  121.         or      eax,edx
  122.         add     eax,[h1]
  123.         imul    eax,5
  124.         add     eax,0x32AC3B17
  125.         mov     [h4],eax
  126.  
  127.         add     esi,16
  128.         sub     ebx,16
  129.         jmp     .loc_loop
  130.  
  131. .loop_done:
  132.         xor     edx,edx
  133.  
  134.         cmp     ebx,15
  135.         je      .loc_tail_15
  136.         cmp     ebx,14
  137.         je      .loc_tail_14
  138.         cmp     ebx,13
  139.         je      .loc_tail_13
  140.         cmp     ebx,12
  141.         je      .loc_tail_12
  142.         cmp     ebx,11
  143.         je      .loc_tail_11
  144.         cmp     ebx,10
  145.         je      .loc_tail_10
  146.         cmp     ebx,9
  147.         je      .loc_tail_9
  148.         cmp     ebx,8
  149.         je      .loc_tail_8
  150.         cmp     ebx,7
  151.         je      .loc_tail_7
  152.         cmp     ebx,6
  153.         je      .loc_tail_6
  154.         cmp     ebx,5
  155.         je      .loc_tail_5
  156.         cmp     ebx,4
  157.         je      .loc_tail_4
  158.         cmp     ebx,3
  159.         je      .loc_tail_3
  160.         cmp     ebx,2
  161.         je      .loc_tail_2
  162.         cmp     ebx,1
  163.         je      .loc_tail_1
  164.         jmp     .loc_finish
  165.  
  166. .loc_tail_15:
  167.         movzx   edx,byte[esi+14]
  168.         shl     edx,16
  169. .loc_tail_14:
  170.         movzx   eax,byte[esi+13]
  171.         shl     eax,8
  172.         xor     edx,eax
  173. .loc_tail_13:
  174.         movzx   eax,byte[esi+12]
  175.         xor     edx,eax
  176.         imul    edx,MAGIC4
  177.         mov     eax,edx
  178.         shr     eax,14
  179.         shl     edx,18
  180.         or      edx,eax
  181.         imul    edx,MAGIC1
  182.         xor     [h4],edx
  183.  
  184. .loc_tail_12:
  185.         movzx   edx,byte[esi+11]
  186.         shl     edx,24
  187. .loc_tail_11:
  188.         movzx   eax,byte[esi+10]
  189.         shl     eax,16
  190.         xor     edx,eax
  191. .loc_tail_10:
  192.         movzx   eax,byte[esi+9]
  193.         shl     eax,8
  194.         xor     edx,eax
  195. .loc_tail_9:
  196.         movzx   eax,byte[esi+8]
  197.         xor     edx,eax
  198.         imul    edx,MAGIC3
  199.         mov     eax,edx
  200.         shr     eax,15
  201.         shl     edx,17
  202.         or      edx,eax
  203.         imul    edx,MAGIC4
  204.         xor     [h3],edx
  205.  
  206. .loc_tail_8:
  207.         movzx   edx,byte[esi+7]
  208.         shl     edx,24
  209. .loc_tail_7:
  210.         movzx   eax,byte[esi+6]
  211.         shl     eax,16
  212.         xor     edx,eax
  213. .loc_tail_6:
  214.         movzx   eax,byte[esi+5]
  215.         shl     eax,8
  216.         xor     edx,eax
  217. .loc_tail_5:
  218.         movzx   eax,byte[esi+4]
  219.         xor     edx,eax
  220.         imul    edx,MAGIC2
  221.         mov     eax,edx
  222.         shr     eax,16
  223.         shl     edx,16
  224.         or      edx,eax
  225.         imul    edx,MAGIC3
  226.         xor     [h2],edx
  227.  
  228. .loc_tail_4:
  229.         movzx   edx,byte[esi+3]
  230.         shl     edx,24
  231. .loc_tail_3:
  232.         movzx   eax,byte[esi+2]
  233.         shl     eax,16
  234.         xor     edx,eax
  235. .loc_tail_2:
  236.         movzx   eax,byte[esi+1]
  237.         shl     eax,8
  238.         xor     edx,eax
  239. .loc_tail_1:
  240.         movzx   eax,byte[esi+0]
  241.         xor     edx,eax
  242.         imul    edx,MAGIC1
  243.         mov     eax,edx
  244.         shr     eax,17
  245.         shl     edx,15
  246.         or      edx,eax
  247.         imul    edx,MAGIC2
  248.         xor     [h1],edx
  249.  
  250. .loc_finish:
  251.         mov     eax,[dSize]
  252.  
  253.         xor     [h1],eax
  254.         xor     [h2],eax
  255.         xor     [h3],eax
  256.         xor     [h4],eax
  257.  
  258.         mov     eax,[h1]
  259.         add     eax,[h2]
  260.         add     eax,[h3]
  261.         add     eax,[h4]
  262.         mov     [h1],eax
  263.  
  264.         add     [h2],eax
  265.         add     [h3],eax
  266.         add     [h4],eax
  267.  
  268.         mov     ecx,[h1]
  269.         mov     eax,ecx
  270.         shr     eax,16
  271.         xor     ecx,eax
  272.         imul    ecx,0x85ebca6b
  273.         mov     eax,ecx
  274.         shr     eax,13
  275.         xor     ecx,eax
  276.         imul    ecx,0xc2b2ae35
  277.         mov     eax,ecx
  278.         shr     eax,16
  279.         xor     eax,ecx
  280.         mov     [h1],eax
  281.  
  282.         mov     ecx,[h2]
  283.         mov     eax,ecx
  284.         shr     eax,16
  285.         xor     ecx,eax
  286.         imul    ecx,0x85ebca6b
  287.         mov     eax,ecx
  288.         shr     eax,13
  289.         xor     ecx,eax
  290.         imul    ecx,0xc2b2ae35
  291.         mov     eax,ecx
  292.         shr     eax,16
  293.         xor     eax,ecx
  294.         mov     [h2],eax
  295.  
  296.         mov     ecx,[h3]
  297.         mov     eax,ecx
  298.         shr     eax,16
  299.         xor     ecx,eax
  300.         imul    ecx,0x85ebca6b
  301.         mov     eax,ecx
  302.         shr     eax,13
  303.         xor     ecx,eax
  304.         imul    ecx,0xc2b2ae35
  305.         mov     eax,ecx
  306.         shr     eax,16
  307.         xor     eax,ecx
  308.         mov     [h3],eax
  309.  
  310.         mov     ecx,[h4]
  311.         mov     eax,ecx
  312.         shr     eax,16
  313.         xor     ecx,eax
  314.         imul    ecx,0x85ebca6b
  315.         mov     eax,ecx
  316.         shr     eax,13
  317.         xor     ecx,eax
  318.         imul    ecx,0xc2b2ae35
  319.         mov     eax,ecx
  320.         shr     eax,16
  321.         xor     eax,ecx
  322.         mov     [h4],eax
  323.  
  324.         mov     eax,[h1]
  325.         add     eax,[h2]
  326.         add     eax,[h3]
  327.         add     eax,[h4]
  328.         mov     [h1],eax
  329.  
  330.         mov     ebx,[h2]
  331.         mov     ecx,[h3]
  332.         mov     edx,[h4]
  333.  
  334.         add     ebx,eax
  335.         add     ecx,eax
  336.         add     edx,eax
  337.  
  338.         pop     edi esi
  339.         ret
  340. endp
Параметры вызова также не отличаются от предыдущих функций, только результат хеширования тут возвращается в четырех регистрах EAX:EBX:ECX:EDX.

Есть еще несколько вариантов алгоритма Murmur, основанных на различных версиях оригинальных алгоритмов. Здесь я их приводить не буду, при желании можете найти их сами и доработать приведенные в статье функции в соответствии с вашими потребностями.

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

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

MurmurHash.Demo.zip (11,295 bytes)


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

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

Комментарии

Отзывы посетителей сайта о статье
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-битного хеша.

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

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

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