2017-12-15

Navigation

Skip Navigation Links

Hash algorithms

Asymmetric Algorithms

Symmetric Cipher Algorithms

Encoding Algorithms

Compression Algorithms

Pseudo Random Number Algorithms

Steganography

Library Wrappers

String Comparison

Others

Syntax highlighting by Prism
PBCrypto.com Mirror

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

Mirror provided by Knuth Konrad