FNV-32
Algorithm creator(s)
Glenn Fowler, Phong Vo, Landon Curt Noll
PB author(s)
Wayne Diamond
Description
A very simple algorithm designed for high-speed hashing resulting in highly dispersed hashes with minimal collisions. Compiles to just 33 bytes!
Note
See the FNV homepage for more information and C source code.
Source
https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/24260-fnv-fowler-noll-vo-32-bit-hash?t=23623
See also
n/a
Source Code
Download source code file fnv32.bas (Right-click -> "Save as ...")
'FNV 32-bit Hash
'===============
'Ported by Wayne Diamond for the PB Forum, 9th December 2002
'Original source: http://www.isthe.com/chongo/src/fnv/hash_32.c
'See also: http://www.isthe.com/chongo/tech/comp/fnv/index.html
'
'FNV (Fowler/Noll/Vo) is a very simple hash designed for
'high-speed hashing, but with minimal collisions.
'The algorithm pseudo-code is something like this:
' hash = offset_basis
' for each byte_of_data to be hashed
' hash = hash * FNV_prime
' hash = hash xor byte_of_data
' return hash
#COMPILE EXE
FUNCTION FNV32(BYVAL dwOffset AS DWORD, BYVAL dwLen AS DWORD, BYVAL offset_basis AS DWORD) AS DWORD
#REGISTER NONE
! mov esi, dwOffset ;esi = ptr to buffer
! mov ecx, dwLen ;ecx = length of buffer (counter)
! mov eax, offset_basis ;set to 0 for FNV-0, or 2166136261 for FNV-1
! mov edi, &h01000193 ;FNV_32_PRIME = 16777619
! xor ebx, ebx ;ebx = 0
nextbyte:
! mul edi ;eax = eax * FNV_32_PRIME
! mov bl, [esi] ;bl = byte from esi
! xor eax, ebx ;al = al xor bl
! inc esi ;esi = esi + 1 (buffer pos)
! dec ecx ;ecx = ecx - 1 (counter)
! jnz nextbyte ;if ecx is 0, jmp to NextByte
! mov FUNCTION, eax ;else, function = eax
END FUNCTION
FUNCTION PBMAIN() AS LONG
DIM Buffer AS STRING, Hash AS DWORD
Buffer = "chongo /\../\" 'FNV test string
'FNV-0 call - only use to test the FNV test string to create the offset_basis value
Hash = FNV32(BYVAL STRPTR(Buffer), BYVAL LEN(Buffer), 0)
'FNV-1 (preferred) call: Hash = FNV32(BYVAL STRPTR(Buffer), BYVAL LEN(Buffer), 2166136261)
IF Hash = 2166136261 THEN
STDOUT "Calculated correctly. The hash is: " & STR$(Hash) & " (&h" & HEX$(Hash,8) & ")"
ELSE
STDOUT "Calculation failed! The hash SHOULD be 2166136261, but I calculated " & STR$(Hash)
END IF
WAITKEY$
END FUNCTION