FNV (Fowler/Noll/Vo) 32-bit hash

[Wayne Diamond]

'FNV 32-bit Hash
'===============
'Ported by Wayne Diamond for the PB Forum, 9th December 2002
'Original source: [url="http://www.isthe.com/chongo/src/fnv/hash_32.c"]http://www.isthe.com/chongo/src/fnv/hash_32.c[/url] 
'See also: [url="http://www.isthe.com/chongo/tech/comp/fnv/index.html"]http://www.isthe.com/chongo/tech/comp/fnv/index.html[/url] 
' 
'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 <Landon Curt Noll> /\../\"  '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

------------------
The PowerBASIC Crypto Archives - What's mine is yours...

[Chris Chancellor]

There is a bug in this function, it can GPF if buffer len = 0 ... i think the folllowing will fix it
any better suggestion?

FUNCTION FNV32(BYVAL dwOffset AS DWORD, BYVAL dwLen AS DWORD, BYVAL offset_basis AS DWORD) AS DWORD
    ' Exits function if string len = 0 otherwise can GPF
      IF dwLen = 0 THEN
         FUNCTION = 0
         EXIT FUNCTION
      END IF              

#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

[Pierre Bellisle]

Hey Chris, better, maybe not, but using asm to do it give a lil "je ne sais quoi" that looks good to me.

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)
 ! cmp ecx, 0             ;compare ecx buffer lenght to zero
 ! je bye                 ;Jump to bye if Equal to zero
 ! 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
 bye:

END FUNCTION

[Chris Chancellor]

Pierre yours is a better code... cheers

[Raymond Leech]

I usually try to find an on-line source to test hashes and encryption algos. The only page I found returned results that did not match the code above. After review of the published test vectors, I think the calculator is returning bad results. So beware if you try to verify your results.
https://fnvhash.github.io/fnv-calculator-online/

I did find a reference page that had test vectors:
Site: http://www.isthe.com/chongo/tech/comp/fnv/
Test Vectors: http://www.isthe.com/chongo/src/fnv/test_fnv.c

For ease of use, I converted it into a spreadsheet.
https://docs.google.com/spreadsheets...6uBUNs/pubhtml

Every test I tried matched the result from the spreadsheet. Just be careful when using the spreadsheet. There are TEST0 for FNV-0 and TEST for FNV-1. Make sure you compare the right test!

Hope someone finds it helpful.

[Mike Doty]

Hash&=FNV32(s$)

FUNCTION PBMAIN() AS LONG  'FNV32.BAS
 LOCAL hash AS DWORD
 LOCAL s    AS STRING
 s = "chongo <Landon Curt Noll> /\../\"
 hash = FNV32(s)   'FNV32-1
 hash = FNV32(s,0) 'FNV32-0
END FUNCTION

FUNCTION FNV32(BYVAL s AS STRING,OPT FNV320 AS DWORD) AS DWORD
 'https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/24260-fnv-fowler-noll-vo-32-bit-hash
 'this is not FNV32-1a which some may prefer
 #REGISTER NONE     'required to get correct test results
 LOCAL dwOffset     AS DWORD
 LOCAL dwLen        AS DWORD
 LOCAL offset_basis AS DWORD
 dwOffSet = STRPTR(s)
 dwLen    = LEN(s)
 IF ISMISSING(FNV320) THEN    'if no extra value passed use FNV32-1 (preferred)
   offset_basis = 2166136261  'FNV32-1 2573183428 s ="chongo <Landon Curt Noll> /\../\"
 ELSE
  offset_basis = 0            'FNV32-0 2166136261 s = "chongo <Landon Curt Noll> /\../\"
 END IF

 ! mov esi, dwOffset      ;esi = ptr to buffer
 ! mov ecx, dwLen         ;ecx = length of buffer (counter)
 ! cmp ecx, 0             ;compare ecx buffer lenght to zero
 ! je bye                 ;Jump to bye if Equal to zero
 ! 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
 bye:
END FUNCTION