Fowler-Noll-Vo hash function
From Wikipedia, the free encyclopedia
Fowler/Noll/Vo is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
Contents |
[edit] Overview
The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zero FNV offset basis. FNV currently comes in 32-, 64-, 128-, 256-, 512-, and 1024-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. [1][2]
The FNV hash algorithms and sample FNV source code have been released into the public domain. [3]
FNV is not a cryptographic hash.
[edit] The hash
One of FNV's key advantages is that it is very simple to implement. Start with an initial hash value of FNV offset basis. 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.
[edit] FNV-1 hash
The FNV-1 hash algorithm is as follows: [4]
hash = FNV_offset_basis for each octet_of_data to be hashed hash = hashFNV_prime hash = hash XOR octet_of_data return hash
In the above pseudocode, all variables are unsigned integers. All variables, except for octet_of_data, have the same number of bits as the FNV hash. The variable, octet_of_data, is an 8 bit unsigned integer.
As an example, consider the 64-bit FNV-1 hash:
- All variables, except for octet_of_data, are 64-bit unsigned integers.
- The variable, octet_of_data, is an 8 bit unsigned integer.
- The FNV_offset_basis is the 64-bit FNV offset basis value: 14695981039346656037.
- The FNV_prime is the 64-bit FNV prime value: 1099511628211.
- The multiply (indicated by the symbol) 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 an 64-bit unsigned integer.
The values for FNV prime and FNV offset basis may be found in this table.[5]
[edit] 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: [6]
hash = FNV_offset_basis for each octet_of_data to be hashed hash = hash XOR octet_of_data hash = hash
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. The small change in order leads to much better avalanche characteristics. [1]
