Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

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

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

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

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

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

    Code:
    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

    Comment


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

      Code:
      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

      Comment


      • #4
        Pierre yours is a better code... cheers

        Comment


        • #5
          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.

          Comment

          Working...
          X