Fowler Noll Vo hash

Fowler/Noll/Vo is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Phong Vo.

History

The first version of FNV was FNV-0. The problem with FNV-0 was that it used an offset basis (see below) of 0, meaning that wherever an empty input or an input consisisting entirely of null bytes was encountered, the resulting hash would be 0. This, of course, meant rather a lot of collisions.

The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zero offset bases.

The hash

One of FNV's key advantages is that it is very simple to implement. Start with "hash" = "offset_basis" (see below). For each byte in the input, multiply "hash" by the "FNV prime", then XOR it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.

There are several different "offset bases" for various bit lengths. These offset bases are computed by running FNV-0 on the string "chongo /../", which is Noll's signature line. This is the only current practical use for the deprecated FNV-0.

"FNV primes" are a much more difficult problem. Noll says on his webpage that "The theory behind which primes make good FNV_primes is beyond the scope of this web page." One notable feature of FNV primes is that when represented as hexadecimal, they are found to bear this appearance:

* The high byte is 1.
* The next-to-low byte is 1.
* The low byte is chosen so that the number is prime.
* All bytes in between are zero.

For any given size, there are a number of different low byte values which satisfy the above constraints. It is not known what criteria were used to select the particular values.

Note that the values are in notation used by C and some other popular programming languages. So "1<<24" means 1 shifted left 24 bits, or 2²⁴. The prefix "0x" on numbers means that the subsequent numbers are in hexadecimal.

Other considerations

FNV currently comes in 32-, 64-, 128-, and 256-bit flavors. For pure FNV implementations, this is determined solely by the availability of FNV primes for the desired bit length; however, the FNV webpage discusses methods of adapting one of the above versions to a smaller length that may or may not be a power of two.

External links

* [http://www.isthe.com/chongo/tech/comp/fnv/ Landon Curt Noll's webpage on FNV]

ee also

* MD2
* MD4
* MD5
* SHA family
* RIPEMD