2. FNV Basics

Cette section conserve le texte RFC relatif a FNV, y compris FNV primes, offset_basis, endianism, XOR folding, constants, non-cryptographic security guidance, source code, test code, Makefile et les comparaisons avec SHA-1 and SHA-256.

Texte RFC original

2.  FNV Basics

   This document focuses on the FNV-1a function, whose pseudocode is as
   follows:

     hash = offset_basis
     for each octet_of_data to be hashed
         hash = hash XOR octet_of_data
         hash = hash * FNV_Prime mod 2**HashSize
     return hash

   In the pseudocode above, hash is a power-of-2 number of bits
   (HashSize is 32, 64, 128, 256, 512, or 1024), and offset_basis and
   FNV_Prime depend on the size of hash.

   The FNV-1 algorithm is the same, including the values of offset_basis
   and FNV_Prime, except that the order of the two lines with the "XOR"
   and multiply operations is reversed.  Operational experience
   indicates better hash dispersion for small amounts of data with FNV-
   1a.  FNV-0 is the same as FNV-1 but with offset_basis set to zero.
   FNV-1a is suggested for general use.

2.1.  FNV Primes

   The theory behind FNV_Primes is beyond the scope of this document,
   but the basic property to look for is how an FNV_Prime would impact
   dispersion.  Now, consider any n-bit FNV hash where n >= 32 and is
   also a power of 2 -- in particular, n = 2^s.  For each such n-bit FNV
   hash, an FNV_Prime p is defined as follows:

   *  When s is an integer and 4 < s < 11, FNV_Prime is the smallest
      prime p of the form:

                        256**int((5 + 2**s)/12) + 2**8 + b

   *  where b is an integer such that:

                                     0 < b < 2**8

   *  The number of one bits in b is four or five

   *  and where

            ( p mod (2**40 - 2**24 - 1) ) > ( 2**24 + 2**8 + 2**7 )

   Experimentally, FNV_Primes 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.

   The case where s < 5 is not considered due to the resulting low hash
   quality.  Such small hashes can, if desired, be derived from a 32-bit
   FNV hash by XOR folding (see Section 3).  The case where s > 10 is
   not considered because of the doubtful utility of such large FNV
   hashes and because the criteria for such large FNV_Primes would be
   more complex, due to the sparsity of such large primes, and would
   needlessly clutter the criteria given above.

   Per the above constraints, an FNV_Prime should have only six or seven
   one bits in it: one relatively high-order one bit, the 2^9 bit, and
   four or five one bits in the low-order byte.  Therefore, some
   compilers may seek to improve the performance of a multiplication
   with an FNV_Prime by replacing the multiplication with shifts and
   adds.  However, the performance of this substitution is highly
   hardware dependent and should be done with care.  The selection of
   FNV_Primes prioritizes the quality of the resulting hash function,
   not compiler optimization considerations.

2.2.  FNV offset_basis

   The offset_basis values for the n-bit FNV-1a algorithms are computed
   by applying the n-bit FNV-0 algorithm to the following 32-octet ASCII
   [RFC0020] character string:

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

   or, in C notation [C], the following string:

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

   In the general case, almost any offset_basis would serve as long as
   it is non-zero.  However, FNV hashes calculated with different
   offset_basis values will not interoperate.  The choice of a non-
   standard offset_basis may be beneficial in some limited circumstances
   to defend against attacks that try to induce hash collisions as
   discussed in Section 6.1.  Any entity that can observe the FNV hash
   output and can cause the null string (the string of length zero) to
   be hashed will thereby be able to directly observe the offset_basis
   which will be the hash output.

2.3.  FNV Endianism

   For persistent storage or interoperability between different hardware
   platforms, an FNV hash shall be represented in the little-endian
   format [IEN137].  That is, the FNV hash will be stored in an array
   hash[N] with N bytes such that its integer value can be retrieved as
   follows:

     unsigned char   hash[N];
     for ( i = N-1, value = 0; i >= 0; --i )
         value = ( value << 8 ) + hash[i];

   However, when FNV hashes are used in a single process or a group of
   processes sharing memory on processors with compatible endianness,
   the natural endianness of those processors can be used, as long as it
   is used consistently, regardless of its type -- little, big, or some
   other exotic form.

   The code provided in Section 8 has FNV hash functions that return a
   little-endian byte vector for all lengths.  Because they are more
   efficient, the code also provides functions that return FNV hashes as
   32-bit integers or, where supported, 64-bit integers, for those sizes
   of FNV hash.  Such integers are compatible with the same-size byte
   vectors on little-endian computers, but the use of the functions
   returning integers on big-endian or other non-little-endian machines
   will be byte-reversed or otherwise incompatible with the byte vector
   return values.