Hash Functions

idle · **Posted:** Wed Aug 24, 2011 12:45 am

FNV32a

Code:

Procedure.q FNV32(*pdata.i,len)
 !mov esi,  [p.p_pdata]     
 !mov ecx, [p.v_len]        
 !mov eax, 2166136261  
 !mov edi, 0x01000193   
 !xor ebx, ebx
 !ntbyte:
 !mov bl, [esi]
 !xor eax, ebx
 !mul edi
 !inc esi
 !dec ecx
 !jnz ntbyte
 ProcedureReturn 
 
EndProcedure  

Thorium · **Joined:** Sat Aug 15, 2009 6:59 pm **Posts:** 1024

You need to preserve ebx, edi and esi.
Otherwise it could cause unexpected behaviour.

Code:

Procedure.q FNV32(*pdata.i,len)
!push ebx
!push edi
!push esi

!mov esi,  [p.p_pdata+12]     
!mov ecx, [p.v_len+12]       
!mov eax, 2166136261 
!mov edi, 0x01000193   
!xor ebx, ebx
!ntbyte:
!mov bl, [esi]
!xor eax, ebx
!mul edi
!inc esi
!dec ecx
!jnz ntbyte

!pop esi
!pop edi
!pop ebx
ProcedureReturn

EndProcedure  

idle · **Posted:** Sun Aug 28, 2011 5:51 am

thanks

evilgravedigger · **Joined:** Thu Feb 23, 2012 1:06 pm **Posts:** 8

Thorium wrote:

You need to preserve ebx, edi and esi.
Otherwise it could cause unexpected behaviour.

Code:

Procedure.q FNV32(*pdata.i,len)
!push ebx
!push edi
!push esi

!mov esi,  [p.p_pdata+12]     
!mov ecx, [p.v_len+12]       
!mov eax, 2166136261 
!mov edi, 0x01000193   
!xor ebx, ebx
!ntbyte:
!mov bl, [esi]
!xor eax, ebx
!mul edi
!inc esi
!dec ecx
!jnz ntbyte

!pop esi
!pop edi
!pop ebx
ProcedureReturn

EndProcedure  

Nice, but why not PUSHAD/POPAD ?

Thorium · **Joined:** Sat Aug 15, 2009 6:59 pm **Posts:** 1024

No specific reason, you can use them as well.

wilbert · **Posted:** Mon Feb 27, 2012 7:44 pm

MurmurHash 3 (32 bit version)
http://code.google.com/p/smhasher/

Code:

; **********************************************
; * MurmurHash3 was written by Austin Appleby, *
; * and is placed in the public domain.        *
; * The author disclaims copyright to this     *
; * source code.                               *
; *                                            *
; * PureBasic conversion by Wilbert            *
; * Last update : 2012/02/29                   *
; **********************************************

Procedure.l MurmurHash3(*key, len.l, seed.l = 0)
  EnableASM
  MOV eax, seed
  MOV ecx, len
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    MOV edx, *key 
    !push ebx
    !push ecx
  CompilerElse
    MOV rdx, *key
    !push rbx
    !push rcx
  CompilerEndIf
  !mov ebx, eax
  !sub ecx, 4
  !js mh3_tail
  ; body
  !mh3_body_loop:
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !mov eax, [edx]
    !add edx, 4
  CompilerElse
    !mov eax, [rdx]
    !add rdx, 4
  CompilerEndIf
  !imul eax, 0xcc9e2d51
  !rol eax, 15
  !imul eax, 0x1b873593
  !xor ebx, eax
  !rol ebx, 13
  !imul ebx, 5
  !add ebx, 0xe6546b64
  !sub ecx, 4
  !jns mh3_body_loop
  ; tail
  !mh3_tail:
  !xor eax, eax
  !add ecx, 3
  !js mh3_finalize
  !jz mh3_t1
  !dec ecx
  !jz mh3_t2
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !mov al, [edx + 2]
    !shl eax, 16
    !mh3_t2: mov ah, [edx + 1]
    !mh3_t1: mov al, [edx]
  CompilerElse
    !mov al, [rdx + 2]
    !shl eax, 16
    !mh3_t2: mov ah, [rdx + 1]
    !mh3_t1: mov al, [rdx]
  CompilerEndIf
  !imul eax, 0xcc9e2d51
  !rol eax, 15
  !imul eax, 0x1b873593
  !xor ebx, eax
  ; finalization
  !mh3_finalize:
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !pop ecx
  CompilerElse
    !pop rcx
  CompilerEndIf
  !xor ebx, ecx
  !mov eax, ebx
  !shr ebx, 16
  !xor eax, ebx
  !imul eax, 0x85ebca6b
  !mov ebx, eax
  !shr ebx, 13
  !xor eax, ebx
  !imul eax, 0xc2b2ae35
  !mov ebx, eax
  !shr ebx, 16
  !xor eax, ebx
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !pop ebx
  CompilerElse
    !pop rbx  
  CompilerEndIf
  DisableASM
  ProcedureReturn
EndProcedure

wilbert · **Posted:** Tue Feb 28, 2012 6:09 pm

While I was converting MurmurHash3, I noticed the FNV32a procedure can be made significantly faster.
First a remark, the return type of FNV32a should be a long instead of a quad.

Here's the improved FNV32a code

Code:

Procedure.l FNV32a(*key, len.l)
  EnableASM
  MOV edx, *key
  MOV ecx, len
  !push ebx
  !mov eax, 2166136261 
  !fnv32a_loop:
  !movzx ebx, byte [edx]
  !xor eax, ebx
  !imul eax, 0x01000193
  !inc edx
  !dec ecx
  !jnz fnv32a_loop
  !pop ebx
  DisableASM
  ProcedureReturn
EndProcedure

I also created an alternative one for zero terminated strings that doesn't require a length parameter

Code:

Procedure FNV32s(*key)
  EnableASM
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    MOV edx, *key
  CompilerElse
    MOV rdx, *key
  CompilerEndIf
  !mov eax, 2166136261
  !jmp fnv32s_entry
  !fnv32s_loop:
  !xor eax, ecx
  !imul eax, 0x01000193
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    CompilerIf #PB_Compiler_Unicode
      !add edx, 2    
      !fnv32s_entry:
      !movzx ecx, word [edx]
    CompilerElse
      !add edx, 1
      !fnv32s_entry:
      !movzx ecx, byte [edx]
    CompilerEndIf
  CompilerElse
    CompilerIf #PB_Compiler_Unicode
      !add rdx, 2    
      !fnv32s_entry:
      !movzx ecx, word [rdx]
    CompilerElse
      !add rdx, 1
      !fnv32s_entry:
      !movzx ecx, byte [rdx]
    CompilerEndIf
  CompilerEndIf
  !cmp ecx, 0
  !jne fnv32s_loop
  DisableASM
  ProcedureReturn
EndProcedure

A speed comparison of the FNV32 code with the 'push' fix added by Thorium, the modified version I made and MurmurHash3.

Code:

s.s = "The quick brown fox jumps over the lazy dog"
s_len.l = Len(s)
cycles.l = 10000000

cycles - 1
tm1 = ElapsedMilliseconds()
For i = 0 To cycles
  a.l = FNV32(@s, s_len)
Next
tm2 = ElapsedMilliseconds()
For i = 0 To cycles
  a.l = FNV32a(@s, s_len)
Next
tm3 = ElapsedMilliseconds()
For i = 0 To cycles
  a.l = MurmurHash3(@s, s_len)
Next
tm4 = ElapsedMilliseconds()

result.s = "FNV32 : " + Str(tm2 - tm1) + Chr(10)
result   + "FNV32a : " + Str(tm3 - tm2) + Chr(10)
result   + "MurmurHash3 : " + Str(tm4 - tm3) 

MessageRequester("Result", result)

The results of this test on my computer :
FNV32 : 796
FNV32a : 499
MurmurHash3 : 280

wilbert · **Posted:** Fri Mar 09, 2012 4:53 pm

Very fast hash algorithm

Code:

; ******************************************
; * The Meiyan hash algorithm              *
; * was written by Sanmayce                *
; * http://www.sanmayce.com/Fastest_Hash/  *
; *                                        *
; * PureBasic conversion by Wilbert        *
; * Last update : 2012/03/09               *
; ******************************************

Procedure MeiyanHash(*key, len.l)
  EnableASM
  MOV ecx, len
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    MOV edx, *key
    !push ebx
    !mov ebx, edx
  CompilerElse
    MOV r8, *key
  CompilerEndIf
  !mov eax, 2166136261
  !sub ecx, 8
  !js meiyan_tail
  ; body
  !meiyan_body_loop:
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !mov edx, [ebx]
    !rol edx, 5
    !xor eax, edx
    !mov edx, [ebx + 4]
    !add ebx, 8
  CompilerElse
    !mov edx, [r8]
    !rol edx, 5
    !xor eax, edx
    !mov edx, [r8 + 4]
    !add r8, 8
  CompilerEndIf
  !xor eax, edx
  !imul eax, 709607
  !sub ecx, 8
  !jns meiyan_body_loop
  ; tail
  !meiyan_tail:
  !add ecx, 8
  !test ecx, 4
  !jz meiyan_t2
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !movzx edx, word [ebx]
    !xor eax, edx
    !imul eax, 709607
    !movzx edx, word [ebx + 2]
    !add ebx, 4
  CompilerElse
    !movzx edx, word [r8]
    !xor eax, edx
    !imul eax, 709607
    !movzx edx, word [r8 + 2]
    !add r8, 4
  CompilerEndIf
  !xor eax, edx
  !imul eax, 709607
  !meiyan_t2:
  !test ecx, 2
  !jz meiyan_t3
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !movzx edx, word [ebx]
    !add ebx, 2
  CompilerElse
    !movzx edx, word [r8]
    !add r8, 2
  CompilerEndIf
  !xor eax, edx
  !imul eax, 709607
  !meiyan_t3:
  !test ecx, 1
  !jz meiyan_t4
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !movzx edx, byte [ebx]
  CompilerElse
    !movzx edx, byte [r8]
  CompilerEndIf
  !xor eax, edx
  !imul eax, 709607
  !meiyan_t4:
  !mov edx, eax
  !shr edx, 16
  !xor eax, edx
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    !pop ebx
  CompilerEndIf
  DisableASM
  ProcedureReturn
EndProcedure

MurmurHash3 seems to have less collisions compared to MeiyanHash.

PureBasic Forum

Hash Functions

Who is online