Fowler Noll Vo hash
Fowler/Noll/Vo is a non-cryptographic message digest function created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
Table of contents |
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 version is 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 <Landon Curt Noll> /\../\", 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_prime's 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 low byte is some number which varies. (Presumably, whatever value will make the whole number prime.)
- All bytes in between are zero.
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 is not a power of two.