GoodOAAT
Code: Select all
; GoodOAAT algorithm by Sokolov Yura aka funny-falcon
Procedure.l GoodOAAT(*key.Ascii, len, seed.l = 0)
!mov edx, [p.v_seed]
!mov ecx, [p.v_len]
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!mov rax, [p.p_key]
!push rbx
!push rsi
!mov rsi, rax
CompilerElse
!mov eax, [p.p_key]
!push ebx
!push esi
!mov esi, eax
CompilerEndIf
!mov eax, edx
!xor edx, 0x3b00
!rol eax, 15
!sub ecx, 1
!jc .l1
!.l0:
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!movzx ebx, byte [rsi]
!add rsi, 1
CompilerElse
!movzx ebx, byte [esi]
!add esi, 1
CompilerEndIf
!add edx, ebx
!lea edx, [edx+edx*8]
!add eax, edx
!rol eax, 7
!lea eax, [eax+eax*4]
!sub ecx, 1
!jnc .l0
!.l1:
!mov ecx, eax
!xor edx, eax
!rol ecx, 14
!add edx, ecx
!mov ecx, edx
!xor eax, edx
!rol ecx, 26
!add eax, ecx
!mov ecx, eax
!xor edx, eax
!rol ecx, 5
!add edx, ecx
!mov ecx, edx
!xor eax, edx
!rol ecx, 24
!add eax, ecx
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!pop rsi
!pop rbx
CompilerElse
!pop esi
!pop ebx
CompilerEndIf
ProcedureReturn
EndProcedure
Larson hash
Code: Select all
Procedure.l LarsonHash(*String); Paul Larson hash
!xor eax, eax
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!mov rdx, [p.p_String]
!jmp larsonhash_l1
!larsonhash_l0:
!imul eax, 101
CompilerIf #PB_Compiler_Unicode
!add rdx, 2
!add eax, ecx
!larsonhash_l1:
!movzx ecx, word [rdx]
CompilerElse
!add rdx, 1
!add eax, ecx
!larsonhash_l1:
!movzx ecx, byte [rdx]
CompilerEndIf
CompilerElse
!mov edx, [p.p_String]
!jmp larsonhash_l1
!larsonhash_l0:
!imul eax, 101
CompilerIf #PB_Compiler_Unicode
!add edx, 2
!add eax, ecx
!larsonhash_l1:
!movzx ecx, word [edx]
CompilerElse
!add edx, 1
!add eax, ecx
!larsonhash_l1:
!movzx ecx, byte [edx]
CompilerEndIf
CompilerEndIf
!test ecx, ecx
!jnz larsonhash_l0
ProcedureReturn
EndProcedure
s.s = "Paul Larson hash test"
t1 = ElapsedMilliseconds()
For i = 1 To 10000000
hash.l = LarsonHash(@s)
Next
t2 = ElapsedMilliseconds()
MessageRequester(Str(hash),Str(t2-t1))
FastHash64 (x64)
updated implementation
Code: Select all
; FastHash64 algorithm by Zilong Tan
Procedure.q FastHash64(*Buffer, Len, Seed.q=0)
!mov r10, 0x2127599bf4325c37
!mov r11, 0x880355f21e6d1965
!mov rdx, [p.p_Buffer]
!mov rcx, [p.v_Len]
!mov rax, rcx ; h = seed ^ (len * m);
!imul rax, r11
!xor rax, [p.v_Seed]
!jmp .l1
; 8 byte loop
!.l0:
!mov r8, [rdx] ; v = *pos++;
!add rdx, 8
; -- mix(v) start --
!mov r9, r8
!shr r9, 23
!xor r8, r9
!imul r8, r10
!mov r9, r8
!shr r9, 47
!xor r8, r9
; -- mix end --
!xor rax, r8 ; h ^= mix(v);
!imul rax, r11 ; h *= m;
!.l1:
!sub rcx, 8
!jnc .l0
; remaining bytes
!and ecx, 7
!jz .l5
!xor r8, r8
!btr ecx, 2
!jnc .l2
; get 4 bytes
!mov r8d, [rdx + rcx]
!.l2:
!btr ecx, 1
!jnc .l3
; get 2 bytes
!shl r8, 16
!mov r8w, [rdx + rcx]
!.l3:
!btr ecx, 0
!jnc .l4
; get 1 byte
!shl r8, 8
!mov r8b, [rdx]
!.l4:
; -- mix(v) start --
!mov r9, r8
!shr r9, 23
!xor r8, r9
!imul r8, r10
!mov r9, r8
!shr r9, 47
!xor r8, r9
; -- mix end --
!xor rax, r8 ; h ^= mix(v);
!imul rax, r11 ; h *= m;
; -- mix(h) start --
!.l5:
!mov r9, rax
!shr r9, 23
!xor rax, r9
!imul rax, r10
!mov r9, rax
!shr r9, 47
!xor rax, r9
; -- mix end --
ProcedureReturn ; return mix(h);
EndProcedure
old implementation
Code: Select all
; FastHash64 algorithm by Zilong Tan
Procedure.q FastHash64(*Buffer, Len, Seed.q=0)
!mov r10, 0x2127599bf4325c37
!mov r11, 0x880355f21e6d1965
!mov rdx, [p.p_Buffer]
!mov rcx, [p.v_Len]
!mov rax, rcx ; h = seed ^ (len * m);
!imul rax, r11
!xor rax, [p.v_Seed]
!sub rcx, 8
!jc .l1
; 8 byte loop
!.l0:
!mov r8, [rdx] ; v = *pos++;
!add rdx, 8
; -- mix(v) start --
!mov r9, r8
!shr r9, 23
!xor r8, r9
!imul r8, r10
!mov r9, r8
!shr r9, 47
!xor r8, r9
; -- mix end --
!xor rax, r8 ; h ^= mix(v);
!imul rax, r11 ; h *= m;
!sub rcx, 8
!jnc .l0
; remaining bytes
!.l1:
!add rcx, 8
!jz .l5
!xor r8, r8
!test rcx, 4
!jz .l2
; get 4 bytes
!mov r8d, [rdx]
!add rdx, 4
!ror r8, 32
!.l2:
!test rcx, 2
!jz .l3
; get 2 bytes
!movzx r9d, word [rdx]
!add rdx, 2
!xor r8, r9
!ror r8, 16
!.l3:
!test rcx, 1
!jz .l4
; get 1 byte
!movzx r9d, byte [rdx]
!xor r8, r9
!ror r8, 8
!.l4:
!and rcx, 7
!shl rcx, 3
!rol r8, cl
; -- mix(v) start --
!mov r9, r8
!shr r9, 23
!xor r8, r9
!imul r8, r10
!mov r9, r8
!shr r9, 47
!xor r8, r9
; -- mix end --
!xor rax, r8 ; h ^= mix(v);
!imul rax, r11 ; h *= m;
; -- mix(h) start --
!.l5:
!mov r9, rax
!shr r9, 23
!xor rax, r9
!imul rax, r10
!mov r9, rax
!shr r9, 47
!xor rax, r9
; -- mix end --
ProcedureReturn ; return mix(h);
EndProcedure
FastHash64 (x86)
Code: Select all
; FastHash64 algorithm by Zilong Tan
Macro FH64___mix_v()
; v ^= v >> 23;
!mov ebx, eax
!shrd ebx, edx, 23
!xor eax, ebx
!mov ebx, edx
!shr ebx, 23
!xor edx, ebx
; v *= 0x2127599bf4325c37ULL;
!imul edx, 0xf4325c37
!imul ebx, eax, 0x2127599b
!add ebx, edx
!mov edx, 0xf4325c37
!mul edx
!add edx, ebx
; v ^= v >> 47;
!mov ebx, edx
!shr ebx, 15
!xor eax, ebx
EndMacro
Macro FH64___h_mul_m()
; h *= m;
!imul ebp, 0x1e6d1965
!imul ebx, edi, 0x880355f2
!mov eax, 0x1e6d1965
!add ebp, ebx
!mul edi
!add ebp, edx
!mov edi, eax
EndMacro
Macro FH64___h_xor_v()
; h ^= v;
!xor ebp, edx
!xor edi, eax
EndMacro
Procedure.q FastHash64(*buf, size, seed.q=0)
!mov edx, [p.p_buf]
!mov ecx, [p.v_size]
!lea eax, [p.v_seed]
!push ebp
!push edi
!push esi
!push ebx
!mov esi, edx
; h = seed
!mov ebp, [eax+4]
!mov edi, [eax]
; v = len * m
!imul ebx, ecx, 0x880355f2
!mov eax, 0x1e6d1965
!mul ecx
!add edx, ebx
FH64___h_xor_v()
!sub ecx, 8
!jc .l1
; >> main loop <<
!.l0:
!mov edx, [esi+4]
!mov eax, [esi]
!add esi, 8
FH64___mix_v()
FH64___h_xor_v()
FH64___h_mul_m()
!sub ecx, 8
!jnc .l0
; >> remaining bytes <<
!.l1:
!and ecx, 7
!jz .l6
!xor edx, edx
!cmp ecx, 4
!jb .l3
!je .l2
; >> 4-7 bytes <<
!mov edx, [esi+ecx-4]
!imul ecx, -8
!shr edx, cl
!.l2:
!mov eax, [esi]
!jmp .l5
; >> 0-3 bytes <<
!.l3:
!xor eax, eax
!test ecx, 2
!jz .l4
!movzx eax, word [esi+ecx-2]
!.l4:
!test ecx, 1
!jz .l5
!movzx ebx, byte [esi]
!shl eax, 8
!or eax, ebx
!.l5:
FH64___mix_v()
FH64___h_xor_v()
FH64___h_mul_m()
!.l6:
; v = h
!mov eax, edi
!mov edx, ebp
FH64___mix_v()
!pop ebx
!pop esi
!pop edi
!pop ebp
ProcedureReturn
EndProcedure