FNV-1 hash

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.

FNV-1a hash

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]

FNV-0 hash (deprecated)

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]

FNV offset basis

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]

FNV prime

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]

FNV hash parameters

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

More information ...

FNV parameters ^[4][14]

Size in bits ${\displaystyle n=2^{s}}$	Representation	FNV prime	FNV offset basis
32	Expression	224 + 28 + 0x93
	Decimal	16777619	2166136261
	Hexadecimal	0x01000193	0x811c9dc5
64	Expression	240 + 28 + 0xb3
	Decimal	1099511628211	14695981039346656037
	Hexadecimal	0x00000100000001B3	0xcbf29ce484222325
128	Representation	288 + 28 + 0x3b
	Decimal	309485009821345068724781371	144066263297769815596495629667062367629
	Hexadecimal	0x0000000001000000000000000000013B	0x6c62272e07bb014262b821756295c58d
256	Representation	2168 + 28 + 0x63
	Decimal	374144419156711147060143317 175368453031918731002211	100029257958052580907070968620625704837 092796014241193945225284501741471925557
	Hexadecimal	0x00000000000000000000010000000000 00000000000000000000000000000163	0xdd268dbcaac550362d98c384c4e576ccc8b153 6847b6bbb31023b4c8caee0535
512	Representation	2344 + 28 + 0x57
	Decimal	358359158748448673689190764 890951084499463279557543925 583998256154206699388825751 26094039892345713852759	965930312949666949800943540071631046609 041874567263789610837432943446265799458 293219771643844981305189220653980578449 5328239340083876191928701583869517785
	Hexadecimal	0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000157	0xb86db0b1171f4416 dca1e50f309990ac ac87d059c9000000 0000000000000d21 e948f68a34c192f6 2ea79bc942dbe7ce 182036415f56e34b ac982aac4afe9fd9
1024	Representation	2680 + 28 + 0x8d
	Decimal	501645651011311865543459881103 527895503076534540479074430301 752383111205510814745150915769 222029538271616265187852689524 938529229181652437508374669137 180409427187316048473796672026 0389217684476157468082573	14197795064947621068722070641403218320 88062279544193396087847491461758272325 22967323037177221508640965212023555493 65628174669108571814760471015076148029 75596980407732015769245856300321530495 71501574036444603635505054127112859663 61610267868082893823963790439336411086 884584107735010676915
	Hexadecimal	0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000010000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 000000000000018D	0x0000000000000000 005f7a76758ecc4d 32e56d5a591028b7 4b29fc4223fdada1 6c3bf34eda3674da 9a21d90000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 000000000004c6d7 eb6e73802734510a 555f256cc005ae55 6bde8cc9c6a93b21 aff4b16c71ee90b3

Close