2017-10-20

### Others

Syntax highlighting by Prism

## FNV-32

### Algorithm creator(s)

Glenn Fowler, Phong Vo, Landon Curt Noll

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!

### Source

n/a

#### Source Code

``````'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
'
'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
``````