4

I'm trying to integrate FNV hashing algorithm on a PHP-based project as part of a requirement to produce hashes for a variety of data (e.g. URLs, keywords).

I saw this implementation by Neven Boyanov. He mentioned that due to arithmetic limitations in PHP, he was forced to use bitwise-shifting and addition instead of multiplication. Is his implementation correct? My knowledge is somehow limited in this area of computer science so I can't 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 variants but using the above implemention 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 hex results:

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

Why is this so? I'm expecting a 16-character hex result from the 64-bit FNV. Are the 'flavors' referring only to the kind of arithmetic operations and seeds that would be used and not to the length of the result? (i.e. if I say 64-bit FNV, the hashing function would use 64-bit operations and seed but the result would still be 32-bit)

A bit of enlightenment would be greatly appreciated :)

PJ.
  • 1,196
  • 2
  • 12
  • 25
  • 1
    You can check what the values from FNV should be in Easy Hash program (free): http://ziin.pl/en/easy_hash – Tom Jun 11 '12 at 22:10

2 Answers2

2

I wrote PHP FNV hash function long ago and it was for a particular purpose, so at that time the 32-bit implementation was sufficient.

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

If you want to implement the 64-bit (or 128-bit) version yourself you should change first the FNV_offset_basis but also the expression on line 73 which currently is:

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

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

For 64-bit you should multiply by 1099511628211 - binary 10000000000000000000000000000000110110011 ... expression: 2^88 + 2^8 + 2^7 + 2^5 + 2^4 + 2^1 + 2^0.

I don't know how the expression $hash << 88 will be handled by PHP but you should experiment yourself. On my PHP 5.2.x it did not work well for numbers greater than 31.

Finally, you may need to modify the $hash = $hash & 0x0ffffffff; to remove some garbage from the result. I figured that out through experiments. For the 64-bit ot should be like $hash = $hash & 0x0ffffffffffffffff;. Verify if it works correctly with PHP.

You can also use other PHP libraries for higher arithmetic precision. In my opinion using bitwise shifts is faster.

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

nevvermind
  • 3,302
  • 1
  • 36
  • 45
Neven Boyanov
  • 749
  • 8
  • 14
  • why would you use 5 shifts and 4 additions instead of a single multiplication? It is 2014, and this is PHP -- an interpreted language without any reasonable compiler optimizations. Every instruction is followed literally, so these are at least 9 operations per byte (probably more as access to $hash is also an operation). Is this beacuse with shifts it is less likely that PHP will convert number to float? – qbolec Jan 23 '14 at 09:26
  • 1
    I was (1) following the original algorithm; and (2) this illustrates how to go to larger number of bit, i.e. 64-bits, where multiplication without loss of precision is not always possible ... unless you use shift & adds. – Neven Boyanov Jan 23 '14 at 14:22
  • For 32-bit prime you can try to use multiplication and test it in the border cases - very small and very large numbers. I suspect that for numbers larger than 2147483647 (largest signed 32-bit integer) the PHP will start using floats or doubles that will lead to loosing precision. – Neven Boyanov Jan 23 '14 at 14:26
0

It turns out that the implementation I cited is for 32-bit FNV1 only. I managed to compile the C-source of FNV and used the binary and Tom's suggested tool to verify that 64-bit FNV indeed returns 16-character hex hashes

PJ.
  • 1,196
  • 2
  • 12
  • 25