The Fash Fast Hash Family. It should be easy to translate to FB I suppose:
https://github.com/douglascrockford/fash
The Fash Fast Hash Family
-
- Posts: 8586
- Joined: May 28, 2005 3:28
- Contact:
Re: The Fash Fast Hash Family
I translated only "fash.c" to "fash.bas" not tested !
Joshy
file: fash.bas
Joshy
file: fash.bas
Code: Select all
/' fash.bas
Douglas Crockford
2017-07-24
Public Domain
This contains the FreeBASIC implementation of
fash64
fash256
rash64
srash64
This implementation trades away performance for portability.
'/
function high_umul64(a as ulongint, b as ulongint) as ulongint
' Make the four pieces.
dim as ulongint a_low = a and &HFFFFFFFF
dim as ulongint a_high = a shr 32
dim as ulongint b_low = b and &HFFFFFFFF
dim as ulongint b_high = b shr 32
' Make the four sub products.
dim as ulongint low = a_low * b_low
dim as ulongint ab = a_high * b_low
dim as ulongint ba = a_low * b_high
dim as ulongint high = a_high * b_high
' Add the two middle sub products. If there is carry, add the carried bit
' to the high sub product.
dim as ulongint mid64 = ab + ba
if (ab > mid64) then high += &H100000000
' We don't need the low part, but we do need to know if adding the mid part
' to the low part causes a carry.
if (low > low + ((mid64 and &HFFFFFFFF) shl 32)) then high += 1
' Add the upper part of the mid sum to the high product.
high += (mid64 shr 32)
return high
end function
function low_umul64(a as ulongint, b as ulongint) as ulongint
return (a * b) and &HFFFFFFFFFFFFFFFFLL
end function
dim shared as ulongint f64_product
dim shared as ulongint f64_sum
sub fash64_begin()
f64_product = 8888888888888888881LL
f64_sum = 3333333333333333271LL
end sub
sub fash64_word(word64 as ulongint)
word64 xor= f64_product
dim as ulongint low = low_umul64 (word64, 9999999999999999961LL)
dim as ulongint high = high_umul64(word64, 9999999999999999961LL)
f64_sum += high
f64_product = f64_sum xor low
end sub
sub fash64_block(block as ulongint ptr, length as ulongint )
for i as uinteger = 0 to length-1
fash64_word(block[i])
next
end sub
function fash64_end() as ulongint
return f64_product
end function
dim shared as ulongint f256_a_result
dim shared as ulongint f256_b_result
dim shared as ulongint f256_c_result
dim shared as ulongint f256_d_result
dim shared as ulongint f256_a_sum
dim shared as ulongint f256_b_sum
dim shared as ulongint f256_c_sum
dim shared as ulongint f256_d_sum
sub fash256_begin()
f256_a_result = 8888888888888888881LL
f256_b_result = 6666666666666666619LL
f256_c_result = 4444444444444444409LL
f256_d_result = 2222222222222222177LL
f256_a_sum = 7777777777777777687LL
f256_b_sum = 5555555555555555533LL
f256_c_sum = 3333333333333333271LL
f256_d_sum = 1111111111111111037LL
end sub
sub fash256_word(word64 as ulongint)
' Mix the word64 with the current state of the hash
' and multiply it with the big primes.
dim as ulongint a_low = low_umul64(f256_a_result xor word64, 11111111111111111027LL)
dim as ulongint b_low = low_umul64(f256_b_result xor word64, 9999999999999999961LL)
dim as ulongint c_low = low_umul64(f256_c_result xor word64, 7777777777777777687LL)
dim as ulongint d_low = low_umul64(f256_d_result xor word64, 5555555555555555533LL)
dim as ulongint a_high = high_umul64(f256_a_result xor word64, 11111111111111111027LL)
dim as ulongint b_high = high_umul64(f256_b_result xor word64, 9999999999999999961LL)
dim as ulongint c_high = high_umul64(f256_c_result xor word64, 7777777777777777687LL)
dim as ulongint d_high = high_umul64(f256_d_result xor word64, 5555555555555555533LL)
' Add the high parts to the sums.
f256_a_sum += a_high
f256_b_sum += b_high
f256_c_sum += c_high
f256_d_sum += d_high
' Mix the low parts with sums from another quadrant.
f256_a_result = a_low xor f256_d_sum
f256_b_result = b_low xor f256_a_sum
f256_c_result = c_low xor f256_b_sum
f256_d_result = d_low xor f256_c_sum
end sub
sub fash256_block(block as ulongint ptr, length as ulongint )
for i as uinteger = 0 to length-1
fash256_word(block[i])
next
end sub
sub fash256_end(result as ulongint ptr)
result[0] = f256_a_result
result[1] = f256_b_result
result[2] = f256_c_result
result[3] = f256_d_result
end sub
dim shared as ulongint r64_result
dim shared as ulongint r64_sum
dim shared as ulongint r64_counter
sub rash64_seed(seed as ulongint)
r64_result = seed
r64_sum = 3333333333333333271LL
r64_counter = 0
end sub
function rash64() as ulongint
r64_result xor= r64_counter
r64_counter += 1
r64_sum += high_umul64(r64_result, 9999999999999999961LL)
r64_result = low_umul64 (r64_result, 9999999999999999961LL) xor r64_sum
return r64_result
end function
dim shared as ulongint sr_a_product, sr_a_sum
dim shared as ulongint sr_b_product, sr_b_sum
dim shared as ulongint sr_c_product, sr_c_sum
dim shared as ulongint sr_d_product, sr_d_sum
dim shared as ulongint sr_e_product, sr_e_sum
dim shared as ulongint sr_f_product, sr_f_sum
dim shared as ulongint sr_g_product, sr_g_sum
dim shared as ulongint sr_h_product, sr_h_sum
dim shared as ulongint sr_counter
sub srash64_seed(seeds as ulongint ptr)
sr_a_product = seeds[ 0] : sr_a_sum = seeds[1]
sr_b_product = seeds[ 2] : sr_b_sum = seeds[3]
sr_c_product = seeds[ 4] : sr_c_sum = seeds[5]
sr_d_product = seeds[ 6] : sr_d_sum = seeds[7]
sr_e_product = seeds[ 8] : sr_e_sum = seeds[9]
sr_f_product = seeds[10] : sr_f_sum = seeds[11]
sr_g_product = seeds[12] : sr_g_sum = seeds[13]
sr_h_product = seeds[14] : sr_h_sum = seeds[15]
sr_counter = 0
end sub
function srash64() as ulongint
sr_a_product xor= sr_counter
sr_counter += 1
dim as ulongint a_low = low_umul64(sr_a_product, 11111111111111111027LL)
dim as ulongint b_low = low_umul64(sr_b_product, 9999999999999999961LL)
dim as ulongint c_low = low_umul64(sr_c_product, 8888888888888888881LL)
dim as ulongint d_low = low_umul64(sr_d_product, 7777777777777777793LL)
dim as ulongint e_low = low_umul64(sr_e_product, 6666666666666666619LL)
dim as ulongint f_low = low_umul64(sr_f_product, 5555555555555555533LL)
dim as ulongint g_low = low_umul64(sr_g_product, 4444444444444444409LL)
dim as ulongint h_low = low_umul64(sr_h_product, 3333333333333333271LL)
sr_a_sum += high_umul64(sr_a_product, 11111111111111111027LL)
sr_b_sum += high_umul64(sr_b_product, 9999999999999999961LL)
sr_c_sum += high_umul64(sr_c_product, 8888888888888888881LL)
sr_d_sum += high_umul64(sr_d_product, 7777777777777777793LL)
sr_e_sum += high_umul64(sr_e_product, 6666666666666666619LL)
sr_f_sum += high_umul64(sr_f_product, 5555555555555555533LL)
sr_g_sum += high_umul64(sr_g_product, 4444444444444444409LL)
sr_h_sum += high_umul64(sr_h_product, 3333333333333333271LL)
sr_a_product = a_low xor sr_h_sum
sr_b_product = b_low xor sr_a_sum
sr_c_product = c_low xor sr_b_sum
sr_d_product = d_low xor sr_c_sum
sr_e_product = e_low xor sr_d_sum
sr_f_product = f_low xor sr_e_sum
sr_g_product = g_low xor sr_f_sum
sr_h_product = h_low xor sr_g_sum
return ( ((sr_a_product + sr_e_product) xor (sr_b_product + sr_f_product)) + _
((sr_c_product + sr_g_product) xor (sr_d_product + sr_h_product)) )
end function
sub srash64_dump(seeds as ulongint ptr)
seeds[ 0] = sr_a_product : seeds[ 1] = sr_a_sum
seeds[ 2] = sr_b_product : seeds[ 3] = sr_b_sum
seeds[ 4] = sr_c_product : seeds[ 5] = sr_c_sum
seeds[ 6] = sr_d_product : seeds[ 7] = sr_d_sum
seeds[ 8] = sr_e_product : seeds[ 9] = sr_e_sum
seeds[10] = sr_f_product : seeds[11] = sr_f_sum
seeds[12] = sr_g_product : seeds[13] = sr_g_sum
seeds[14] = sr_h_product : seeds[15] = sr_h_sum
end sub
Re: The Fash Fast Hash Family
For absolutely no reason I did the code for fash64 in Linux AMD64:
It checks out consistent with D.J.Peters' conversion:
Code: Select all
type fash64
product as ulongint
sum as ulongint
declare sub begin()
declare sub hash(x as ulongint)
declare sub hashblock(xptr as ulongint ptr,n as ulongint)
declare function finished() as ulongint
end type
sub fash64.begin()
product=8888888888888888881ULL
sum=3333333333333333271ULL
end sub
function fash64.finished() as ulongint
return product
end function
sub fash64.hash naked (x as ulongint)
asm
mov rax,qword ptr [rdi]
mov rbx,qword ptr [rdi+8]
movabs rdx,9999999999999999961
xor rax,rsi ' rax is mixed with the word
mul rdx ' rdx,rax is the unsigned product of r0 * prime
add rbx,rdx ' rbx is the sum of the high halves
xor rax,rbx ' rax is the mix of the low product and sum
mov qword ptr [rdi+8],rbx
mov qword ptr [rdi],rax
ret
end asm
end sub
sub fash64.hashblock naked (xptr as ulongint ptr,n as ulongint)
asm
mov rcx,rdx
mov rax,qword ptr [rdi]
mov rbx,qword ptr [rdi+8]
movabs r8,9999999999999999961
test rcx,rcx ' compare length with 0
jz rethashblock ' done if the input is empty
.align 16
hbeach:
xor rax,[rsi] ' rax is mixed with the data
lea rsi,[rsi+8] ' point rsi to the next word
mul r8 ' rdx,rax is the unsigned product of r0 * prime
add rbx,rdx ' rbx is the sum of the high halves
xor rax,rbx ' rax is the mix of the low product and sum
sub rcx,1 ' decrement the length
jnz hbeach ' repeat for each thing
mov qword ptr [rdi+8],rbx
mov qword ptr [rdi],rax
rethashblock:
ret
end asm
end sub
dim as fash64 f,g
dim as ulongint x(2)={123,456,789}
f.begin()
g.begin()
f.hash(x(0))
f.hash(x(1))
f.hash(x(2))
g.hashblock(@x(0),3)
print f.finished(),g.finished()
getkey
Code: Select all
function high_umul64(a as ulongint, b as ulongint) as ulongint
' Make the four pieces.
dim as ulongint a_low = a and &HFFFFFFFF
dim as ulongint a_high = a shr 32
dim as ulongint b_low = b and &HFFFFFFFF
dim as ulongint b_high = b shr 32
' Make the four sub products.
dim as ulongint low = a_low * b_low
dim as ulongint ab = a_high * b_low
dim as ulongint ba = a_low * b_high
dim as ulongint high = a_high * b_high
' Add the two middle sub products. If there is carry, add the carried bit
' to the high sub product.
dim as ulongint mid64 = ab + ba
if (ab > mid64) then high += &H100000000
' We don't need the low part, but we do need to know if adding the mid part
' to the low part causes a carry.
if (low > low + ((mid64 and &HFFFFFFFF) shl 32)) then high += 1
' Add the upper part of the mid sum to the high product.
high += (mid64 shr 32)
return high
end function
function low_umul64(a as ulongint, b as ulongint) as ulongint
return (a * b) and &HFFFFFFFFFFFFFFFFLL
end function
dim shared as ulongint f64_product
dim shared as ulongint f64_sum
sub fash64_begin()
f64_product = 8888888888888888881LL
f64_sum = 3333333333333333271LL
end sub
sub fash64_word(word64 as ulongint)
word64 xor= f64_product
dim as ulongint low = low_umul64 (word64, 9999999999999999961LL)
dim as ulongint high = high_umul64(word64, 9999999999999999961LL)
f64_sum += high
f64_product = f64_sum xor low
end sub
sub fash64_block(block as ulongint ptr, length as ulongint )
for i as uinteger = 0 to length-1
fash64_word(block[i])
next
end sub
function fash64_end() as ulongint
return f64_product
end function
dim as ulongint x(2)={123,456,789}
fash64_begin()
fash64_word(x(0))
fash64_word(x(1))
fash64_word(x(2))
print fash64_end()
getkey