FNV 'flavors' and PHP implementation

I am trying to integrate the FNV hash algorithm into a PHP based project as part of the requirement to create hashes for a variety of data (e.g. URLs, keywords).

I saw this implementation of Neven Boyanov. He mentioned that due to arithmetic restrictions in PHP, he was forced to use bitwise offset and addition instead of multiplication. Is its implementation correct? My knowledge is somehow limited in this area of ​​computer science, so I can not verify it myself.

Another question that I have is about the different “flavors” of FNV. I saw that it offers 32-bit, 64-bit and 128-bit options, but using the above implementation, I always get 8-character hex hashes (I convert the integer result to hex using dechex ()).

Given the input "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin at libero mi, quis luctus massa.", I get the following hexadecimal results:

  • (32 bit offset) 5b15c0f2
  • (64 bit offset) 6ea33cb5

Why is this so? I expect a 16-character hexadecimal result from a 64-bit FNV. Are "aromas" a reference only to the types of arithmetic operations and seeds to be used, and not to the length of the result? (i.e. if I say 64-bit FNV, the hash function will use 64-bit operations and seed, but the result will still be 32-bit)

A little enlightenment will be greatly appreciated :)

+4
source share
2 answers

I wrote a PHP FNV hash function for a long time, and this was for a specific purpose, so at that time a 32-bit implementation was enough.

To answer your first question - the implementation was tested against other (C and C ++) implementations by comparing the algorithm (code) and the results of the selection. Therefore, for 32-bit results, it works as it should.

If you want to implement the 64-bit (or 128-bit) version yourself, you must first change FNV_offset_basis, as well as the expression on line 73, which is currently:

$hash += ($hash<<1) + ($hash<<4) + ($hash<<7) + ($hash<<8) + ($hash<<24); 

... this is equivalent to multiplying by the number 16777619 (FNV_prime_32), which in binary format 1000000000000000110010011 is broken down into this expression: 2^24 + 2^8 + 2^7 + 2^4 + 2^1 + 2^0 .

For 64-bit multiplication, multiply by 1099511628211 - the binary expression 100000000000000000000000000000000000110110011 ... expression: 2^88 + 2^8 + 2^7 + 2^5 + 2^4 + 2^1 + 2^0 .

I don’t know how the expression $hash << 88 PHP will be processed, but you should experiment. On my PHP 5.2.x, this did not work for numbers greater than 31.

Finally, you may need to change $hash = $hash & 0x0ffffffff; to remove trash from the result. I realized this through experimentation. For 64-bit ot should be like $hash = $hash & 0x0ffffffffffffffff; . Check if it works correctly with PHP.

You can also use other PHP libraries for higher arithmetic accuracy. In my opinion, the use of bitwise shifts is faster.

In fact, you can use FNV Hash for any number of bits.

+2
source

It turns out that the implementation I quoted is for 32-bit FNV1 only. I managed to compile C-source FNV and use binary files, and Tom suggested to make sure that 64-bit FNV really returns 16-character hex hashes

0
source

All Articles