Fowler–Noll–Vo hash function

The FNV-1 hash algorithm is as follows:[8][9]

algorithm fnv-1 is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash × FNV_prime
        hash := hash XOR byte_of_data

    return hash

In the above pseudocode, all variables are unsigned integers. All variables, except for byte_of_data, have the same number of bits as the FNV hash. The variable, byte_of_data, is an 8 bit unsigned integer.

As an example, consider the 64-bit FNV-1 hash:

• All variables, except for byte_of_data, are 64-bit unsigned integers.
• The variable, byte_of_data, is an 8-bit unsigned integer.
• The FNV_offset_basis is the 64-bit FNV offset basis value: 14695981039346656037 (in hex, 0xcbf29ce484222325).
• The FNV_prime is the 64-bit FNV prime value: 1099511628211 (in hex, 0x100000001b3).
• The multiply returns the lower 64-bits of the product.
• The XOR is an 8-bit operation that modifies only the lower 8-bits of the hash value.
• The hash value returned is a 64-bit unsigned integer.

The FNV-1a hash differs from the FNV-1 hash by only the order in which the multiply and XOR is performed:[8][10]

algorithm fnv-1a is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash XOR byte_of_data
        hash := hash × FNV_prime

    return hash

The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. The change in order leads to slightly better avalanche characteristics.[8][11]

The FNV-0 hash differs from the FNV-1 hash only by the initialisation value of the hash variable:[8][12]

algorithm fnv-0 is
    hash := 0

    for each byte_of_data to be hashed do
        hash := hash × FNV_prime
        hash := hash XOR byte_of_data

    return hash

The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode.

A consequence of the initialisation of the hash to 0 is that empty messages and all messages consisting of only the byte 0, regardless of their length, hash to 0.[12]

Use of the FNV-0 hash is deprecated except for the computing of the FNV offset basis for use as the FNV-1 and FNV-1a hash parameters.[8][12]

There are several different FNV offset bases for various bit lengths. These offset bases are computed by computing the FNV-0 from the following 32 octets when expressed in ASCII:

chongo <Landon Curt Noll> /\../\

which is one of Landon Curt Noll's signature lines. This is the only current practical use for the deprecated FNV-0.[8][12]

An FNV prime is a prime number and is determined as follows:[4][13]

For a given ${\displaystyle s}$:

• ${\displaystyle s\in \mathbb {Z} ^{*}~}$ (i.e., s is an integer)
• ${\displaystyle 4<s<11}$

where ${\displaystyle n}$ is:

• ${\displaystyle n=2^{s}}$

and where ${\displaystyle t}$ is:

• ${\displaystyle t=\left\lfloor {\frac {5+n}{12}}\right\rfloor }$

NOTE: ${\displaystyle \lfloor x\rfloor \,}$ is the floor function

then the n-bit FNV prime is the smallest prime number ${\displaystyle p}$ that is of the form:

${\displaystyle 256^{t}+2^{8}+\mathrm {b} \,}$

such that:

• ${\displaystyle 0<b<2^{8}}$
• The number of one-bits in the binary number representation of ${\displaystyle b}$ is either 4 or 5
• ${\displaystyle p\mod (2^{40}-2^{24}-1)>(2^{24}+2^{8}+2^{7})}$

Experimentally, FNV prime matching the above constraints tend to have better dispersion properties. They improve the polynomial feedback characteristic when an FNV prime multiplies an intermediate hash value. As such, the hash values produced are more scattered throughout the n-bit hash space.[4][13]

The above FNV prime constraints and the definition of the FNV offset basis yield the following table of FNV hash parameters: