
FNV quick index
(top)
FNV hash history
The basis of the FNV hash algorithm was taken from an idea sent
as reviewer comments to the IEEE POSIX P1003.2 committee by
Glenn Fowler and
Phong Vo back in 1991.
In a subsequent ballot round:
Landon Curt Noll
improved on their algorithm.
Some people tried this hash and found that it worked rather well.
In an EMail message
to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
FNV hashes are designed to be fast while maintaining
a low collision rate.
The FNV speed allows one to quickly hash lots
of data while maintaining a reasonable collision rate.
The high dispersion of the FNV hashes makes them
well suited for hashing nearly identical strings such as
URLs, hostnames, filenames, text, IP addresses, etc.
The IETF has an informational draft on
The
FNV NonCryptographic Hash Algorithm
The FNV hash is in wide spread use:
 calc
 Domain Name Servers
 mdbm key/value data lookup functions
 Database indexing hashes
 major web search / indexing engines
 high performance EMail servers
 Netnews history file MessageID lookup functions
 Antispam filters
 NFS implementations (e.g.,
FreeBSD 4.3,
IRIX, Linux (NFS v4))
 Cohesia MASS project
server collision avoidance
 spellchecker programmed in Ada 95
 flatassembler's
open source x86 assembler 
userdefined
symbol hashtree
 PowerBASIC inline assembly routine
 text based referenced resources for video games on the PS2, Gamecube
and XBOX
 noncryptographic file fingerprints
 FRET  a tool
to identify file data structures / helps to understand file formats
 used to in the process of computing Unique IDs in DASM (DTN Applications for Symbian Mobilephones)
 Used by Microsoft in their hash_map implementation for VC++ 2005
 Used in an implementation of
libketama
for use in items such as
memcache.
 Used in the realpath cache in
PHP 5.x (php5.2.3/TSRM/tsrm_virtual_cwd.c).
 Used to
improve
the fragment cache
at twitter (see slide 31).
 Used in the BSD
IDE project
 Used in the deliantra game server
for it's shared string implementation
 Used to improve
Leprechaun,
an extremely fast word list creator
 Favored as a hash for IPv6 Flow Labels in a
University
of Auckland Computer Science Technical Report (2012002) of March 2012
 Used in the speedsensitive guts of twistylists,
an opensource structured namespace manager
FNV hash algorithms and
source code
have been released into the public domain.
The authors of the FNV algorithmm look deliberate steps
to disclose the algorhtm in a public forum soon after
it was invented.
More than a year passed after this public disclosure and the
authors deliberatly took no steps to patent the FNV algorithm.
Therefore it is safe to say that the FNV authors have
no patent claims on the FNV algorithm as published.
If you use an FNV function in an application, why not tell
tells us about it by sending EMail to:
There is no requirement to tell us.
But if you do, we will be happy to add your application to the above list.
Comments are welcome.
(top)
The core of the FNV hash
The core of the FNV1 hash algorithm is as follows:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash * FNV_prime
hash = hash xor octet_of_data
return hash
The offset_basis and
FNV_prime can be found in the
parameters of the FNV1/FNV1a hash section below.
NOTE: We recommend that you use the FNV1a
alternative algorithm instead of the FNV1 hash where possible.
(top)
FNV1a alternate algorithm
There is a minor variation of the FNV hash algorithm known as
FNV1a:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash xor octet_of_data
hash = hash * FNV_prime
return hash
The only difference between the FNV1a hash and the FNV1 hash
is the order of the xor and multiply.
The FNV1a hash
uses the same FNV_prime and offset_basis
as the FNV1 hash of the same nbit size.
The offset_basis and
FNV_prime can be found in the
parameters of the FNV1/FNV1a hash section below.
Some people use FNV1a instead of FNV1
because they see
slightly better dispersion for tiny (<4 octets) chunks of memory.
One person reported that the FNV1 hash was not as good as
the FNV1a hash, for their purpuses, because the final
octet is not as well dispersed.
They reported that the FNV1a hash was better for error
detection, for example.
Other people report that either FNV1 or FNV1a make a fine hash.
(Try it with with
just a dash of Sage and ground Cloves :))
NOTE: We recommend that you use the FNV1a
alternative algorithm instead of the FNV1 hash where possible.
(top)
Parameters of the FNV1/FNV1a hash
The FNV1 hash parameters are as follows:
 hash is an n bit unsigned integer,
where n is the bit length of hash.
 The multiplication is performed modulo 2^{n}
where n is the bit length of hash.
 The xor is performed on the low order
octet (8 bits) of hash.
 The FNV_prime is dependent on n, the size of the hash:
32 bit FNV_prime =
2^{24} + 2^{8} + 0x93 = 16777619
64 bit FNV_prime = 2^{40} + 2^{8} + 0xb3 = 1099511628211
128 bit FNV_prime = 2^{88} + 2^{8} + 0x3b = 309485009821345068724781371
256 bit FNV_prime = 2^{168} + 2^{8} + 0x63 = 374144419156711147060143317175368453031918731002211
512 bit FNV_prime = 2^{344} + 2^{8} + 0x57 =
35835915874844867368919076489095108449946327955754392558399825615420669938882575
126094039892345713852759
1024 bit FNV_prime = 2^{680} + 2^{8} + 0x8d =
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573
Part of the magic of FNV is the selection of the FNV_prime
for a given sized unsigned integer.
Some primes do hash better than other primes for a given integer size.
 The offset_basis for FNV1 is dependent on n, the size of the hash:
32 bit offset_basis = 2166136261
64 bit offset_basis = 14695981039346656037
128 bit offset_basis = 144066263297769815596495629667062367629
256 bit offset_basis =
100029257958052580907070968620625704837092796014241193945225284501741471925557
512 bit offset_basis =
96593031294966694980094354007163104660904187456726378961083743294344626579945829
32197716438449813051892206539805784495328239340083876191928701583869517785
1024 bit offset_basis =
14197795064947621068722070641403218320880622795441933960878474914617582723252296
73230371772215086409652120235554936562817466910857181476047101507614802975596980
40773201576924585630032153049571501574036444603635505054127112859663616102678680
82893823963790439336411086884584107735010676915
NOTE: Older versions of this web page incorretly indicated that the 128 bit
FNV_prime was 2^{168} + 2^{8} + 0x59.
This was not correct.
While that satisfied all of the significant FNV_prime properties,
it was not the smallest 128 bit FNV_prime.
The 128 bit offset_basis
changed from
275519064689413815358837431229664493455
to
144066263297769815596495629667062367629
was changed as a result of the 128 bit FNV_prime correction.
(Sorry about that!)
These nonzero integers are the FNV0 hashes of
the following 32 octets:
chongo <Landon Curt Noll> /\../\
The \'s in the above string are not Cstyle escape characters.
In Cstring notation, these 32 octets are:
"chongo <Landon Curt Noll> /\\../\\"
Regarding the offset_basis value:
The switch from FNV0 to FNV1 was purely to change the offset_basis to a
nonzero value.
The selection of that nonzero value is arbitrary. The string:
chongo <Landon Curt Noll> /\../\
was used because the tester was looking at an EMail message from
Landon in Landon's standard EMail signature line.
Actually the person who did that did not see very well.
Landon, today, uses ()'s instead of <>'s and his
ASCII bats
use "oo" eyes instead of ".." as in:
chongo (Landon Curt Noll) /\oo/\
We didn't bother correcting her error because it does not matter.
In the general case, almost any offset_basis will serve so long as it
is nonzero.
The following
calc
script was used to compute the offset_basis
for FNV1 hashes:
hash_bits = insert_the_hash_size_in_bits_here;
FNV_prime = insert_the_FNV_prime_here;
offset_basis = 0;
offset_str = "chongo <Landon Curt Noll> /\\../\\";
hash_mod = 2^hash_bits;
str_len = strlen(offset_str);
for (i=1; i <= str_len; ++i) {
offset_basis = (offset_basis * FNV_prime) % hash_mod;
offset_basis = xor(offset_basis, ord(substr(offset_str,i,1)));
}
print hash_bits, "bit offset_basis =", offset_basis;
NOTE: The above code fragment example is written in the
calc
language, not in C.
FNV0 Historic note:
The FNV0 is the historic FNV algorithm that
is now deprecated.
It has an
offset_basis of 0.
Unless the FNV0 hash is required for historical purposes,
the FNV1 or FNV1a
should be used in place of the FNV0 hash.
Use FNV1 and FNV1a hashes, with their nonzero
offset_basis instead.
The FNV0 hashes all buffers that contain only 0 octets to a
hash value of 0.
The FNV1 and FNV1a hash do not suffer from this minor problem.
(top)
A few remarks on FNV primes
While theory behind FNV_prime's
is beyond the scope of this web page,
the following text may suffice to satisfy the curious:
One of the key properties to look for in an FNV_prime is how
it impacts dispersion.
When s is an integer and
4 < s < 11, then FNV_prime is the smallest
prime of the form:
256^{int((5 + 2s)/12)} + 2^{8} + b
such that:
 0 < b < 2^{8}
 The number of onebits in b is 4 or 5
An FNV_prime that matches the above constraints tend to have
better dispersion properties.
They improve the polynomial feedback characteristic when an
FNV_prime multiplies an intermediate hash value.
The hash values produced are more scattered throughout the nbit
hash space.
It is a nice side effect that FNV_prime may be
optimized by some compilers for some hardware.
On some hardware, replacing the FNV_prime multiply
with a set of shifts and adds will improve performance.
In other cases where multiply may be pipelined (such as in vector mode),
the set of shifts and adds may be suboptimal.
The FNV_prime were not selected for compiler optimization,
they were selected for the quality of resulting hash function.
The case where s < 5 is not considered because the resulting hash
quality is too low.
Such small hashes can, if desired, be derived
from a 32 bit FNV hash by xorfolding.
The case where s > 10 is considered because the doubtful utility
of such large FNV hashes and because the criteria for such large FNV_Primes
is more complex, due to the sparsity of such large primes, and would
needlessly clutter the criteria given above. The criteria above is
a simplified form that fails to generate 2048bit FNV_prime
and a 4096bit FNV_prime, for example. For such large
primes we would need to use a more extensive prime selection criteria.
(top)
Changing the FNV hash size  xorfolding
If you need an xbit hash where x is not a power of 2, then
we recommend that you compute the FNV hash that is just larger
than xbits and xorfold the result down to xbits.
By xorfolding we mean shift the excess high order bits down
and xor them with the lower xbits.
For example to produce a 24 bit FNV1 hash in C
we xorfold fold a 32 bit FNV1 hash:
#define MASK_24 (((u_int32_t)1<<24)1) /* i.e., (u_int32_t)0xffffff */
#define FNV1_32_INIT ((u_int32_t)2166136261)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
hash = (hash>>24) ^ (hash & MASK_24);
To produce a 16 bit FNV1 hash in C
we xorfold fold a 32 bit FNV1 hash:
#define MASK_16 (((u_int32_t)1<<16)1) /* i.e., (u_int32_t)0xffff */
#define FNV1_32_INIT ((u_int32_t)2166136261)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
hash = (hash>>16) ^ (hash & MASK_16);
To produce a 56 bit FNV1 hash in C (on a machine
with 64 bit unsigned values)
we xorfold fold a 64 bit FNV1 hash:
#define MASK_56 (((u_int64_t)1<<56)1) /* i.e., (u_int64_t)0xffffffffffffff */
#define FNV1_64_INIT ((u_int64_t)14695981039346656037)
u_int64_t hash;
void *data;
size_t data_len;
hash = fnv_64_buf(data, data_len, FNV1_64_INIT);
hash = (hash>>56) ^ (hash & MASK_56);
The above process assumes that you are using an FNV hash
that at most twice as large as the xbits that you need.
For x < 16, there is no 16 bit (or less) FNV1
hash to use.
For tiny x < 16 bit values, we recommend using a 32 bit FNV1
hash as follows:
/* NOTE: for 0 < x < 16 ONLY!!! */
#define TINY_MASK(x) (((u_int32_t)1<<(x))1)
#define FNV1_32_INIT ((u_int32_t)2166136261)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
hash = (((hash>>x) ^ hash) & TINY_MASK(x));
At the expense of CPU performance, one may use a larger
FNV1 hash that is normally required in any of the above
xorfolding examples.
This will not produce the same standard output,
but it may provide slightly better dispersion at the expense of more CPU time.
All that is needed is to use a larger FNV1 hash
and to move the mask outside of the expression
on the final statement.
For example, to produce a 24 bit FNV1 hash could have used
a 64 bit FNV1 hash, in a nonstandard way, as follows:
/* NOTE: nonstandard use of a larger hash */
#define MASK_24 (((u_int64_t)1<<24)1) /* i.e., (u_int64_t)0xffffff */
#define FNV1_64_INIT ((u_int64_t)14695981039346656037)
u_int64_t hash;
void *data;
size_t data_len;
hash = fnv_64_buf(data, data_len, FNV1_64_INIT);
hash = (((hash>>24) ^ hash) & MASK_24);
Replacing a 32 bit FNV1 hash with a 64 bit FNV1 hash
during xorfolding might yield better dispersion at the expense
of CPU time.
However using an even larger FNV1 hash is
almost certainly a waste of CPU time.
If you are going to use this nonstandard xorfolding
method, we recommend that you only do it for x < 32 bits, and
only replace the 32 bit FNV1 hash with a 64 bit FNV1 hash.
NOTE: One may substitute the FNV1a hash for the
FNV1 hash in any of the xorfolding examples.
Some people believe that FNV1a xorfolding gives then
slightly better dispersion without any impact on CPU performance.
See the FNV1a hash description for more information.
If you really need an xbit hash
for x > 1024 bits, send us EMail.
(top)
Changing the FNV hash size  nonpowers of 2
The FNV hash is designed for hash sizes that are a power of 2.
If you need a hash size that is not a power of two, then you have
two choices.
One method id called the
lazy mod mapping method
and the other is called the
retry method.
Both involve mapping a range that is a power of 2 onto an
arbitrary range.
 Lazy mod mapping method:
The lazy mod mapping method
uses a simple mod on an nbit hash
to yield an arbitrary range.
To produce a hash range between 0 and X
use a nbit FNV hash where n is smallest
FNV hash that will produce values larger than X
without the need for
xorfolding.
For example, to produce a value between 0 and 2142779559
using the
lazy mod mapping method, we select a 32bit FNV
hash because:
2^{32} > 2142779559
We compute the 32bit FNV hash value and then perform a final mod:
#define TRUE_HASH_SIZE ((u_int32_t)2142779560) /* range top plus 1 */
#define FNV1_32_INIT ((u_int32_t)2166136261)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
hash %= TRUE_HASH_SIZE;
An advantage of the lazy mod mapping method
is that it requires only 1 more operation:
only an additional mod is performed at the end.
The disadvantage of the lazy mod mapping method
is that there is
a bias against the larger values.
To understand this bias consider the a need
to produce a value between 0 and 999999.
We will compute a 32bit FNV hash value because:
2^{32} > 999999
We compute the 32bit FNV hash value using the
and then perform the final mod:
#define TRUE_HASH_SIZE ((u_int32_t)1000000) /* range top plus 1 */
#define FNV1_32_INIT ((u_int32_t)2166136261)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
hash %= TRUE_HASH_SIZE;
The bias introduced by the final mod is slight.
The values 0 through 967295 will be created by
4295 different 32bit FNV hash values whereas
the values 967296 through 999999 will be created by
only 4294 different 32bit FNV hash values.
In other words, the values 0 through 967295 will
occur ~1.0002328 times as often as the values 967296
through 999999.
The bias can be larger when the range is nearly as large as the
range of values produced by the FNV hash.
Consider using the lazy mod mapping method
to produce
values between 0 and 9999999999999999999.
We use a 64bit FNV hash because:
2^{64} > 9999999999999999999
We compute the 64bit FNV hash value using the
and then perform the final mod:
#define TRUE_HASH_SIZE ((u_int64_t)10000000000000000000) /* range top plus 1 */
#define FNV1_64_INIT ((u_int64_t)14695981039346656037)
u_int64_t hash;
void *data;
size_t data_len;
hash = fnv_64_buf(data, data_len, FNV1_64_INIT);
hash %= TRUE_HASH_SIZE;
Here the bias introduced by the final mod is more noticeable.
The values 0 through 9999999999999999999 will be created by
2 different 64bit FNV hash values whereas
the values 10000000000000000000 through 18446744073709551615 will be created by
only 1 64bit FNV hash value.
NOTE:
This bias issue may not be of concern to you, but we thought we should
point out this issue just in case you care.
Many applications should / will not care about this bias.
Most applications can use the lazy mod mapping method without
any problems.
Your application, may vary however.
NOTE: One may substitute the FNV1a hash for the
FNV1 hash in any of the lazy mod mapping method examples.
Some people believe that FNV1a lazy mod mapping method gives then
slightly better dispersion without any impact on CPU performance.
See the FNV1a hash description for more information.
 Retry method:
The retry method also performs a final mod in order
to produce a hash range between 0 and X.
Unlike lazy mod mapping method,
the retry method avoids the bias by
additional computation.
To produce a hash range between 0 and X
use a nbit FNV hash where n is smallest
FNV hash that will produce values larger than X
without the need for
xorfolding.
For example, to produce a value between 0 and 49999
using the
retry method, we select a 32bit FNV
hash because:
2^{32} > 49999
Before the final mod 50000 is performed, we check to
see if the 32bit FNV hash value is one of the upper
biased values.
If it is, we perform additional loop cycles until is below
the bias level.
For example:
#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;
The disadvantage of the retry method
is that it sometimes requires additional calculations.
An advantage of the retry method
it avoids slightly biased values.
For another example, we will
produce a value between 0 and 999999999999
using the
retry method, we select a 64bit FNV
hash because:
2^{64} > 999999999999
Before the final mod 1000000000000 is performed, we check to
see if the 64bit FNV hash value is one of the upper
biased value.
If it is, we perform additional loop cycles until it is not.
#define TRUE_HASH_SIZE ((u_int64_t)1000000000000) /* range top plus 1 */
#define FNV_64_PRIME ((u_int64_t)1099511628211)
#define FNV1_64_INIT ((u_int64_t)14695981039346656037)
#define MAX_64BIT ((u_int64_t)0xffffffffffffffff) /* largest 64 bit unsigned value */
#define RETRY_LEVEL ((MAX_64BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int64_t hash;
void *data;
size_t data_len;
hash = fnv_64_buf(data, data_len, FNV1_64_INIT);
while (hash >= RETRY_LEVEL) {
hash = (hash * FNV_64_PRIME) + FNV1_64_INIT;
}
hash %= TRUE_HASH_SIZE;
NOTE: One may substitute the FNV1a hash for the
FNV1 hash in any of the retry method examples.
Some people believe that FNV1a retry method gives then
slightly better dispersion without any impact on CPU performance.
See the FNV1a hash description for more information.
 To summarize:
When dealing with an application that needs to
generate a hash value over an
arbitrary range, one can do one of the following:
 Change the application to use hash values that range
between 0 and 2^{n}1.
Use a nbit FNV hash or
xorfolding if needed.
Pro: Yields the best results in the shortest
amount of CPU time.
Con: Requires source code change to force hash range to be
a power of 2 in size.
 Use the
lazy mod mapping method
if one does
not care about the slight hash bias and does not want (or cannot change)
the hash range.
Pro: Yields the fastest results for a nonpower
of 2 range.
Con: Produces a slight bias against larger hash values.
However if one does not care about the slight bias, then there
is no problem using this technique.
 Use the
retry method
if one wants to avoid the
hash bias and does not want / cannot change
the hash range.
Pro: Produces nonbiased values for a nonpower
of 2 range.
Con: Requires slightly more CPU time in some cases.
(top)
FNV source
FNV reference source
In the C source< below, primes are provided
for 32 bit and 64 bit unsigned integers.
For compilers that do not implement the unsigned long long
type, code is provided to quickly simulate the 64 bit multiply
by the particular FNV_prime.
 fnv5.0.3.tar.gz 
(all the bits) [updated: 2012 May 20]
 hash_32.c 
(32 bit FNV1 algorithm)
 hash_64.c 
(64 bit FNV1 algorithm)
 hash_32a.c 
(32 bit FNV1a algorithm)
 hash_64a.c 
(64 bit FNV1a algorithm)
 fnv.h 
(FNV header file)
 fnv32.c 
(32 bit FNV0, FNV1, and FNV1a hash tool/demo) [updated: 2012 May 20]
 fnv64.c 
(64 bit FNV0, FNV1, and FNV1a hash tool/demo) updated: 2012 May 20]
 README 
(brief comments about FNV0, FNV1, and FNV1a)
 Makefile 
(how to compile/install)
 have_ulong64.c 
(64 bit unsigned integer type detector)
 test_fnv.c 
(FNV test vectors)
NOTE: As of version 5.0, the above source include test vectors
for 32 bit and 64 bit versions of the
FNV0, FNV1, and FNV1a algoritms.
The test_fnv.c file
contains validated test vectors. To verify a compiled code, try:
make check
For compiled code, try:
 fnv032 t 1 v
 fnv132 t 1 v
 fnv1a32 t 1 v
 fnv064 t 1 v
 fnv164 t 1 v
 fnv1a64 t 1 v
(top)
Other FNV source code
Andy Allinger sent us this 32 bit FNV1a subroutine written in
FNV1 in FORTRAN.
Nicola Bonelli
has an implementation of FNV using the iovec interface:
Nicola Bonelli
also wrote the following C++ FNV implementation:
Georgi Marinov (Georgi 'Kaze' 'Sanmayce') posted his very fast FNV1a
implementation:
Wayne Diamond implemented 32bit FNV algorithm in
PowerBASIC inline x86 assembly:
FUNCTION FNV32(BYVAL dwOffset AS DWORD, BYVAL dwLen AS DWORD, BYVAL offset_basis AS DWORD) AS DWORD
#REGISTER NONE
! mov esi, dwOffset ;esi = ptr to buffer
! mov ecx, dwLen ;ecx = length of buffer (counter)
! mov eax, offset_basis ;set to 2166136261 for FNV1
! mov edi, &h01000193 ;FNV_32_PRIME = 16777619
! xor ebx, ebx ;ebx = 0
nextbyte:
! mul edi ;eax = eax * FNV_32_PRIME
! mov bl, [esi] ;bl = byte from esi
! xor eax, ebx ;al = al xor bl
! inc esi ;esi = esi + 1 (buffer pos)
! dec ecx ;ecx = ecx  1 (counter)
! jnz nextbyte ;if ecx is 0, jmp to NextByte
! mov FUNCTION, eax ;else, function = eax
END FUNCTION
Wayne said:
''Just thought I should let you know that I've ported the 32bit
FNV algorithm over to inline assembly. It's actually in PowerBASIC
(www.powerbasic.com) format  a compiler I use, but the main function
is all assembly. It could be optimized further in terms of saving a
couple of clock cycles, but it's fairly optimized al ready  only 6
instructions in the main loop, plus 5 setup instructions, and compiles
to just 33 bytes.''
M.S.Schulte sent us these 32bit FNV1 and FNV1a x86 assembler
implementations (written in flat
assembler), half of which were optimized for speed, the other half
were optimized for size:
small_fnv32: ;FNV1 32bit (size: 31 bytes)
; Intel Core 2 Duo E6600: 354.20 mb/s
push esi
push edi
mov esi, [esp + 0ch] ;buffer
mov ecx, [esp + 10h] ;length
mov eax, [esp + 14h] ;basis
mov edi, 01000193h ;fnv_32_prime
next:
mul edi
xor al, [esi]
inc esi
loop snext
pop edi
pop esi
retn 0ch
small_fnv32a: ;FNV1a 32bit (size: 31 bytes)
; Intel Core 2 Duo E6600: 327.68 mb/s
push esi
push edi
mov esi, [esp + 0ch] ;buffer
mov ecx, [esp + 10h] ;length
mov eax, [esp + 14h] ;basis
mov edi, 01000193h ;fnv_32_prime
nexta:
xor al, [esi]
mul edi
inc esi
loop nexta
pop edi
pop esi
retn 0ch
fast_fnv32: ;FNV1 32bit (size: 36 bytes)
; Intel Core 2 Duo E6600: 565.12 mb/s
push ebx
push esi
push edi
mov esi, [esp + 10h] ;buffer
mov ecx, [esp + 14h] ;length
mov eax, [esp + 18h] ;basis
mov edi, 01000193h ;fnv_32_prime
xor ebx, ebx
next:
mul edi
mov bl, [esi]
xor eax, ebx
inc esi
dec ecx
jnz next
pop edi
pop esi
pop ebx
retn 0ch
fast_fnv32a: ;FNV1a 32bit (size: 36 bytes)
; Intel Core 2 Duo E6600: 574.95 mb/s
push ebx
push esi
push edi
mov esi, [esp + 10h] ;buffer
mov ecx, [esp + 14h] ;length
mov eax, [esp + 18h] ;basis
mov edi, 01000193h ;fnv_32_prime
xor ebx, ebx
nexta:
mov bl, [esi]
xor eax, ebx
mul edi
inc esi
dec ecx
jnz nexta
pop edi
pop esi
pop ebx
retn 0ch
M.S.Schulte also sent us these 64bit FNV1 and FNV1a
x86 assembler implementations:
;FNV64 x8664bit assembler implementation (written in flat assembler)
;FNV641 and FNV641a, both 37 bytes, (~284.13 mb/s Intel E8400)
;invoke fnv64,buffer,length,base (x64 Calling Convention)
fnv64:
mov rax, r8
mov r8, rdx
mov r9, 100000001b3h ;fnv_64_prime
xor r10, r10
next:
mul r9
mov r10b, [rcx]
xor rax, r10
inc rcx
dec r8
jnz next
ret
fnv64a:
mov rax, r8
mov r8, rdx
mov r9, 100000001b3h ;fnv_64_prime
xor r10, r10
nexta:
mov r10b, [rcx]
xor rax, r10
mul r9
inc rcx
dec r8
jnz nexta
ret
(top)
gcc optimization
It has been reported by several people that under the gcc compiler
with O3 on many AMD & Intel CPUs, that replacing the
FNV_prime multiply with a expression of shifts and adds
will improve the performance.
Limited testing on our part confirmed that one can gain a few %
in speed on an 1.6GHz AMD Athlon using gcc version 3.2.2 with O3 optimization.
For a 32 bit FNV1, we used:
while (bp < be) {
/* multiply by the 32 bit FNV magic prime mod 2^32 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
hval *= FNV_32_PRIME;
#else
hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
#endif
/* xor the bottom with the current octet */
hval ^= (Fnv32_t)*bp++;
}
For a 32 bit FNV1a, we used:
while (bp < be) {
/* xor the bottom with the current octet */
hval ^= (Fnv32_t)*bp++;
/* multiply by the 32 bit FNV magic prime mod 2^32 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
hval *= FNV_32_PRIME;
#else
hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
#endif
}
For a 64 bit FNV1, we used:
while (bp < be) {
/* multiply by the 64 bit FNV magic prime mod 2^64 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
hval *= FNV_64_PRIME;
#else
hval += (hval << 1) + (hval << 4) + (hval << 5) +
hval << 7) + (hval << 8) + (hval << 40);
#endif
/* xor the bottom with the current octet */
hval ^= (Fnv64_t)*bp++;
}
For a 64 bit FNV1a, we used:
while (bp < be) {
/* xor the bottom with the current octet */
hval ^= (Fnv64_t)*bp++;
/* multiply by the 64 bit FNV magic prime mod 2^64 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
hval *= FNV_64_PRIME;
#else
hval += (hval << 1) + (hval << 4) + (hval << 5) +
hval << 7) + (hval << 8) + (hval << 40);
#endif
}
(top)
Can you help solve some of the zerohash challenges?
We are interested in finding the shortest data sets, under certain constraints, that produce
a FNV hash value of zero for the various sizes of the FNV1 and FNV1a hash function.
Those who offer the best solution will receive fame and credit on the FNV web page.
If you have a zerovalue hash solution to an unsolved challenge, or if you have a better
(shorted data segment) solution than one that is shown below, please send EMail to:
Please use the subject line:
zerohash challenge solution
NOTE: Please use the solution format used by Russ Cox (see below), if possible.
Please include the following information in your EMail message:
 The challenge number you claim to have solved
 The name of the challenge you claim to have solved
 The length, in octets (8 bit bytes) of your proposed solution
 Who should we credit (i.e., how do you want us to credit you on our web page) for solving the challenge?
 A URL containing your proposed solution (optional)
NOTE: If your solution is large, please do not send the data set in the EMail.
Instead send is a URL where we can download your proposed challenge solution.
Zerohash challenges:
 SOLVED! What is the shortest binary data set for which the 32bit FNV1 hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
There are 254 solutions of length 5, ranging from
FNV32_1(01 47 6c 10 f3) = 0
to
FNV32_1(fd 45 41 08 a0) = 0
 SOLVED! What is the shortest binary data set for which the 64bit FNV1 hash is 0?
Scott Pakin
<>
on 2011Aug22 reported that there are
no solutions for binary data sets of length 7 or less.
64bit solution by an anonymous scientist
<>
on 2011Oct23:
There are no solutions for length 8.
These are the solutions for length 9:
FNV64_1(92 06 77 4c e0 2f 89 2a d2) = 0
FNV64_1(fb 6c 4f db 00 41 db c0 fe) = 0
FNV64_1(9f 72 72 35 80 4b 8d 6b 06) = 0
FNV64_1(3d 82 76 00 80 7c 52 62 1a) = 0
FNV64_1(58 21 f5 a2 e1 01 9d 80 e0) = 0
FNV64_1(52 a1 eb 10 a0 e9 45 96 05) = 0
FNV64_1(be 64 8a 14 e1 46 17 18 ff) = 0
FNV64_1(9e 50 1d f2 41 75 55 ac 05) = 0
FNV64_1(b3 92 a9 6f 80 e4 29 a4 63) = 0
FNV64_1(82 ba b3 41 81 0f db 83 15) = 0
FNV64_1(92 f4 6e 0e e1 b9 e5 45 2d) = 0
FNV64_1(3c ea 57 50 81 67 67 9b e0) = 0
FNV64_1(36 e3 96 34 e2 1d 36 00 61) = 0
FNV64_1(af fa ff ee 61 b0 5e c4 04) = 0
FNV64_1(d5 c9 88 15 02 2f d3 38 c2) = 0
FNV64_1(bc a7 38 51 e2 2f b1 1b 22) = 0
FNV64_1(70 f2 10 ba 02 45 37 b3 e8) = 0
FNV64_1(5b a3 a0 4e 81 fc 4f 32 5b) = 0
FNV64_1(cd 50 99 68 22 d4 78 2f b0) = 0
FNV64_1(fa ff 0d fa e2 f0 43 b4 9a) = 0
FNV64_1(16 3f ba 47 43 94 44 fe 86) = 0
FNV64_1(46 e0 03 71 c2 57 f0 bc da) = 0
FNV64_1(60 74 4a 52 e3 06 42 36 f2) = 0
FNV64_1(97 20 3a f8 a2 f6 8a 62 a6) = 0
FNV64_1(98 f5 cc d5 03 32 22 1a e2) = 0
FNV64_1(5d d5 14 e8 e3 43 8b 5a 9e) = 0
FNV64_1(95 b8 11 62 03 5a ed d2 cb) = 0
FNV64_1(f9 cb 23 1d 03 71 c5 ca 5c) = 0
FNV64_1(c3 04 1c 59 82 a5 aa 9b 55) = 0
FNV64_1(68 10 80 61 a3 5e 72 31 48) = 0
FNV64_1(43 0a eb 89 c2 c1 9d d8 2a) = 0
FNV64_1(5a a3 e3 40 23 ce 90 bc a2) = 0
FNV64_1(27 e1 3f aa a3 8f af 6a 51) = 0
FNV64_1(0c 5b ac 36 24 22 a2 7c 24) = 0
FNV64_1(ea bc d7 7c 24 49 58 66 57) = 0
FNV64_1(5a 30 62 51 83 9c 97 c3 75) = 0
FNV64_1(7a 18 75 d3 c3 88 65 0b 3a) = 0
FNV64_1(02 38 25 95 25 0b 3b 0c a8) = 0
FNV64_1(33 1c ae dd 83 fc 55 f4 63) = 0
FNV64_1(cb 87 3d b9 e5 38 0b bd ca) = 0
FNV64_1(3a 25 ba 67 a4 c7 49 80 e9) = 0
FNV64_1(49 14 3b 94 05 63 b5 de d6) = 0
FNV64_1(45 fb 0d 28 45 19 66 63 27) = 0
FNV64_1(92 7a e5 a6 e5 88 ba 55 68) = 0
FNV64_1(c3 93 7c 11 c4 1a 2f e0 8b) = 0
FNV64_1(a1 d8 5e 71 a5 6a 96 5e 64) = 0
FNV64_1(77 7b d7 7d 05 dc 73 64 c3) = 0
FNV64_1(3d 3f d4 d6 a6 71 b2 9d 65) = 0
FNV64_1(8d 45 9e d0 27 66 b4 46 34) = 0
FNV64_1(f1 da 16 a1 85 fe 43 a7 30) = 0
FNV64_1(97 6b 02 e3 66 10 3d 6e ab) = 0
FNV64_1(84 2b d9 13 a7 25 5a 8a 22) = 0
FNV64_1(0c 2b 2f d2 28 3a 91 df 95) = 0
FNV64_1(1c 01 ed aa 47 2f 64 6a 8b) = 0
FNV64_1(71 66 6f 98 47 74 48 eb 39) = 0
FNV64_1(2b b3 61 de e8 6c 33 fd 32) = 0
FNV64_1(c5 33 7e c3 87 9c 0c 24 4b) = 0
FNV64_1(b7 44 ea 2c a8 59 bc fc c5) = 0
FNV64_1(b2 8c 40 98 67 46 6f ce 35) = 0
FNV64_1(04 34 61 b3 87 d4 e5 1a 7f) = 0
FNV64_1(20 ba 15 17 e8 dd d9 f6 19) = 0
FNV64_1(36 c4 d3 ef 88 53 6e 86 56) = 0
FNV64_1(32 55 ce f0 48 73 af 8d 9d) = 0
FNV64_1(18 3c d8 70 08 71 6a 47 a3) = 0
FNV64_1(a8 ad fb 29 a8 e4 8e 82 c4) = 0
FNV64_1(47 47 bf 58 08 7f ab bc 34) = 0
FNV64_1(8f 68 71 3a e9 56 8f d0 0f) = 0
FNV64_1(64 5e dc 14 88 93 8d b4 35) = 0
FNV64_1(b4 33 d0 6d 48 bb 3a 5d 3d) = 0
FNV64_1(22 e4 4d 0a 48 bd 95 1e 8e) = 0
FNV64_1(78 6e 06 7d 48 ce db 12 33) = 0
FNV64_1(7e 1f 4d 02 48 f8 d2 a5 c2) = 0
FNV64_1(90 6b 26 4e c7 ef 12 f2 20) = 0
FNV64_1(90 10 a8 21 09 16 22 57 bc) = 0
FNV64_1(5b 1a 8c bc 09 2c a4 2d 9c) = 0
FNV64_1(2c 1a 6e 44 a9 7d 98 e0 39) = 0
FNV64_1(8a 2b 35 ab 49 97 d5 f7 bc) = 0
FNV64_1(29 bc 62 5e 0a 4e 9e 34 40) = 0
FNV64_1(e7 e6 c7 00 aa d3 26 5a 4a) = 0
FNV64_1(7e 65 e5 51 2b 66 e8 b5 b2) = 0
FNV64_1(2b d7 cf 6a 6a 6f b4 56 c9) = 0
FNV64_1(33 51 09 af ab 42 80 8b 07) = 0
FNV64_1(d1 78 30 6b c9 9c af 1f d4) = 0
FNV64_1(c6 00 f9 bf 4b 38 f0 00 c6) = 0
FNV64_1(a1 81 99 9a c9 f2 8e 4c 6f) = 0
FNV64_1(b3 d1 6c 57 2c 62 3c b0 5c) = 0
FNV64_1(c7 50 c1 4d ec de 91 e8 fd) = 0
FNV64_1(54 51 fe aa ec e9 6b f2 a2) = 0
FNV64_1(5d dc 27 f3 4b c8 b0 9a c9) = 0
FNV64_1(d2 4d e1 77 8c 0a 8f 2d 44) = 0
FNV64_1(ce e4 e5 80 ca 8a 07 dc 67) = 0
FNV64_1(0f d0 8f 67 ca 9f 94 a5 86) = 0
FNV64_1(89 e9 ed dd ed 84 84 50 26) = 0
FNV64_1(76 f5 be 03 ac 82 5a 09 26) = 0
FNV64_1(f8 71 02 ca 6c 6d a5 ae fc) = 0
FNV64_1(e8 cb 80 56 ad 00 a0 d1 d2) = 0
FNV64_1(88 89 0c dd 0c cf b2 5d d7) = 0
FNV64_1(69 ad 8f db 0d 03 8a ca 37) = 0
FNV64_1(96 58 24 93 cb bf d7 f1 fe) = 0
FNV64_1(ee b1 f6 d2 6d 9b 46 7d 3f) = 0
FNV64_1(de 64 18 d6 2e 86 5b 3c 0c) = 0
FNV64_1(24 05 66 e4 0d f1 c8 b1 d3) = 0
FNV64_1(77 d7 5f 5f ef 81 2d b3 37) = 0
FNV64_1(58 53 f5 b5 2e ec 51 fe 25) = 0
FNV64_1(ba 65 2a 3b 8e c6 bb a8 b6) = 0
FNV64_1(e5 81 4f 09 f0 0c ec f9 fa) = 0
FNV64_1(50 5b e8 f9 f0 6a 47 b4 64) = 0
FNV64_1(d3 0e f4 c7 6e d9 60 31 b5) = 0
FNV64_1(58 e4 4a 3c cd 97 d6 fd 84) = 0
FNV64_1(6f 82 aa ca 2f e7 1a 8d b1) = 0
FNV64_1(8f 50 ec 2f 2f e7 30 4c db) = 0
FNV64_1(f0 3b 01 db 6f 33 db 82 41) = 0
FNV64_1(13 3c 71 e4 8f 75 46 48 8f) = 0
FNV64_1(2f a5 a5 41 cd f5 b4 c6 45) = 0
FNV64_1(8b 1a 4c 12 30 38 c3 61 08) = 0
FNV64_1(6f 9c 5c 3f 8f d6 47 70 f7) = 0
FNV64_1(c1 0e 16 18 50 1b 47 48 f8) = 0
FNV64_1(2b 94 3f ad 30 ad 5e c4 85) = 0
FNV64_1(5f 55 92 c6 ce b9 f5 05 08) = 0
FNV64_1(42 8e 3a bb f1 bd 08 09 25) = 0
FNV64_1(28 84 f5 2b ce f1 3e 47 41) = 0
FNV64_1(25 d1 2c bf 90 5c 71 24 85) = 0
FNV64_1(d0 25 3d f3 90 64 67 ae f9) = 0
FNV64_1(c5 1d e5 36 11 a9 7b 4d e0) = 0
FNV64_1(88 c2 24 da 50 f9 55 03 dc) = 0
FNV64_1(ff 54 4f 75 cf 6d bb c4 4b) = 0
FNV64_1(9e 49 c2 63 11 d7 b0 74 25) = 0
FNV64_1(ac b1 42 65 cf 7d 84 0e 37) = 0
FNV64_1(05 a5 28 18 11 e3 0d 6a aa) = 0
FNV64_1(03 8d 11 ce f2 6f 0e 0a cf) = 0
FNV64_1(bf d6 88 3d 51 75 18 67 0e) = 0
FNV64_1(69 a2 dd 69 cf e4 94 5e e3) = 0
FNV64_1(e4 62 0b 95 b1 58 a1 d4 25) = 0
FNV64_1(c0 75 c6 ec 51 9e d4 c7 4c) = 0
FNV64_1(83 9d b3 97 32 54 9b 04 ec) = 0
FNV64_1(9a 7f 71 94 32 cf bb 97 38) = 0
FNV64_1(7a 4f e4 60 13 93 fd 7d 50) = 0
FNV64_1(76 48 71 f5 52 2f cb f7 e2) = 0
FNV64_1(da 0e 88 1f 13 ba d5 a7 2f) = 0
FNV64_1(2a be ca e7 33 12 4e 33 26) = 0
FNV64_1(79 ce 5e ee 92 27 5d c7 17) = 0
FNV64_1(36 91 77 d3 72 5a de 9f 0b) = 0
FNV64_1(3a 33 cd 8d 52 7a b8 2a d8) = 0
FNV64_1(25 66 ec c3 52 8b d0 13 4f) = 0
FNV64_1(de d7 a1 1f b2 58 65 d8 d7) = 0
FNV64_1(8a e5 cb 54 33 b0 de 92 42) = 0
FNV64_1(71 49 0a bb 33 d8 35 b3 59) = 0
FNV64_1(03 36 3b 64 f4 98 4b 21 99) = 0
FNV64_1(8c f5 50 02 d2 10 db 86 1d) = 0
FNV64_1(c3 4f cf 6e 93 4e b5 d8 b4) = 0
FNV64_1(2a fb 95 75 73 8c 85 76 82) = 0
FNV64_1(35 c0 2a 8b f5 56 45 66 45) = 0
FNV64_1(68 2a 76 44 73 cf 31 3a 8e) = 0
FNV64_1(98 4c a0 05 93 9a cf 65 a1) = 0
FNV64_1(a5 3e 3b f8 94 0e 6e 74 73) = 0
FNV64_1(4b 75 16 e9 35 47 e2 af 21) = 0
FNV64_1(3c 84 fb ee f6 10 6c 09 3f) = 0
FNV64_1(45 52 87 53 74 7c 1b 2c a1) = 0
FNV64_1(a0 8b 28 e0 d3 34 be 90 cb) = 0
FNV64_1(67 57 50 d0 16 3c 23 af e1) = 0
FNV64_1(a8 a6 4d 44 16 52 57 ba 95) = 0
FNV64_1(9e 0c be 6a 75 1d 3f 6c 20) = 0
FNV64_1(14 1b 43 7a b5 4e 40 88 b0) = 0
FNV64_1(68 3b bd d6 f7 ae d7 f9 28) = 0
FNV64_1(ab c0 61 a3 76 20 b8 f7 3b) = 0
FNV64_1(05 e8 00 91 b5 dd be 7e af) = 0
FNV64_1(14 dd 60 a4 96 19 04 05 16) = 0
FNV64_1(7e e5 14 cd 76 87 03 4c 2d) = 0
FNV64_1(07 f0 09 29 18 7d 7d fe 8a) = 0
FNV64_1(b9 b4 a5 c6 37 99 fd 49 ff) = 0
FNV64_1(d2 dd 5a 63 37 e4 08 8e d4) = 0
FNV64_1(a2 0b f2 5e 76 fd 65 2c 80) = 0
FNV64_1(c8 d7 df ba 37 e8 d9 2b 0c) = 0
FNV64_1(6e 40 03 eb 37 ea eb a6 93) = 0
FNV64_1(27 f9 53 0f 37 fc 0e 28 60) = 0
FNV64_1(c2 72 49 23 d5 ce 7e bb ef) = 0
FNV64_1(3e 11 d8 6b b6 e9 30 2f ab) = 0
FNV64_1(0e dd b7 d7 19 45 86 d7 79) = 0
FNV64_1(a3 f7 21 85 97 07 7d e1 4b) = 0
FNV64_1(4e 76 21 ee 19 67 54 55 23) = 0
FNV64_1(0f 19 18 da 38 60 1c 0b 9c) = 0
FNV64_1(a4 91 5d 2c 77 7f b4 cb c6) = 0
FNV64_1(c1 b7 ee 41 19 7a 60 4d 7e) = 0
FNV64_1(88 47 7b 0c d6 4c e0 c1 20) = 0
FNV64_1(73 88 eb 4f d6 53 4f 7c 6a) = 0
FNV64_1(f4 5a e5 b3 f9 cf 96 88 8f) = 0
FNV64_1(ba 5c b1 28 58 2f 33 16 cc) = 0
FNV64_1(04 cd 1f c8 1a 7a 20 f1 d0) = 0
FNV64_1(5f 2c 1c 63 b8 48 83 82 a4) = 0
FNV64_1(22 f5 ed a6 98 51 eb a3 f8) = 0
FNV64_1(f8 6b 6d 33 fa 65 24 bd 5c) = 0
FNV64_1(10 3b b6 ae d7 86 73 25 d3) = 0
FNV64_1(52 31 6c 5a 79 03 be 55 95) = 0
FNV64_1(af c9 ab 5e 1b 54 de 1d 84) = 0
FNV64_1(c2 ed f4 36 79 77 81 0d ee) = 0
FNV64_1(36 f5 db eb d8 30 d9 69 f6) = 0
FNV64_1(43 84 92 b9 79 90 66 a4 e6) = 0
FNV64_1(7d e9 4d 0e 1b da 69 eb 57) = 0
FNV64_1(2d 03 20 62 fb 3b 6e 88 65) = 0
FNV64_1(e5 69 ec d2 79 be d8 aa 8e) = 0
FNV64_1(ac 26 0a dd fb 68 43 1f 6d) = 0
FNV64_1(3c 96 c1 be 3a be 22 ae 76) = 0
FNV64_1(de 73 09 f1 1c 39 67 8a 0c) = 0
FNV64_1(56 2e 5f 2c 3a fd 30 40 7d) = 0
FNV64_1(68 57 ce 1c 59 e0 e0 eb 04) = 0
FNV64_1(df f7 e6 75 1c 66 88 86 90) = 0
FNV64_1(fd af f5 8b 5a 06 ae 0b 40) = 0
FNV64_1(4e cf a7 e9 1c 93 af 36 a8) = 0
FNV64_1(56 dc 13 cf fc 12 88 bb b8) = 0
FNV64_1(1f 5f c2 b2 3b 75 fb 7c 92) = 0
FNV64_1(4e 9c bb ba 5a 74 e3 a4 e1) = 0
FNV64_1(0b a0 c8 c5 1d 99 06 87 5e) = 0
FNV64_1(ff ef b0 25 1d f4 9d df db) = 0
FNV64_1(09 67 cb 8f 7c 13 3c 75 97) = 0
FNV64_1(05 bf fe 4d fd d2 6e 61 64) = 0
FNV64_1(a4 d7 4b 6d 3d 2a bb ee 4c) = 0
FNV64_1(b9 8c 01 cb 5b f2 50 15 f0) = 0
FNV64_1(31 45 17 91 1e a3 7f 25 52) = 0
FNV64_1(10 6c 0c 98 db 0f 9b 1e 88) = 0
FNV64_1(06 ec cc b6 9b da a2 3a 16) = 0
FNV64_1(23 66 38 19 7c ac 80 d3 78) = 0
FNV64_1(b8 f3 d7 98 bc 11 60 0f bf) = 0
FNV64_1(27 24 2d a8 db c2 99 28 65) = 0
FNV64_1(64 61 39 c2 bc 79 b5 b1 a6) = 0
FNV64_1(df ff 2a 12 5c fb 42 6d 01) = 0
FNV64_1(af 1d ea 4e ff 0d 46 95 5e) = 0
FNV64_1(2a b0 c6 54 9c e9 98 43 e1) = 0
FNV64_1(7c e5 9e 74 7d c8 44 ef 9e) = 0
FNV64_1(56 14 d1 31 dc ce 77 17 c3) = 0
FNV64_1(ed 6b 65 68 3f 05 36 41 9b) = 0
FNV64_1(2f d2 24 7e dd 19 4f 91 72) = 0
FNV64_1(c8 96 f0 54 9d 92 5b cc b1) = 0
FNV64_1(47 5d 76 63 be 17 24 ad d4) = 0
FNV64_1(4f 88 0b 03 9e 4a 48 ee 14) = 0
FNV64_1(26 ec 1b 56 5e b8 5d 5e 39) = 0
FNV64_1(c3 a8 2d 1a 5e fc b7 81 49) = 0
FNV64_1(14 3a 3b 0b be e7 b2 4d 75) = 0
FNV64_1(27 a0 f4 22 df b5 b6 5e 4a) = 0
 Partial solution: What is the shortest binary data set for which the 128bit FNV1 hash is 0?
Richard Heylen
<>
found a 128bit FNV1 solution on 2011Dec01:
The following is a solution of length 17:
FNV128_1(20 28 4e 43 40 55 6f 99 25 1b 89 f4 a8 18 ec 76 c0) = 0
NOTE: It is not known if the above solution is the shortest 128bit FNV1
solution.
Can you find a shorter solution or prove that the shortest solutions are
of length 17?
 Partial solution: What is the shortest binary data set for which the 256bit FNV1 hash is 0?
Richard Heylen
<>
found a 256bit FNV1 solution on 2011Dec17:
The following is a solution of length 37:
FNV256_1(04 03 F4 7D 37 15 6D DB 3B 06 68 6F 07 0E 0E 3B 67 6E 43 53 0B
5F 5A 08 93 09 16 29 47 D9 4C 1B BD 7E 04 17 38) = 0
NOTE: It is not known if the above solution is the shortest 256bit FNV1
solution.
Richard Heylen speculates that the shortest solution might
be 32 or 33 in length.
Can you find a shorter solution or prove that the shortest solutions are
of length 37?
 What is the shortest binary data set for which the 512bit FNV1 hash is 0?
 What is the shortest binary data set for which the 1024bit FNV1 hash is 0?
 SOLVED! What is the shortest binary data set for which the 32bit FNV1a hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 4 are:
FNV32_1a(cc 24 31 c4) = 0
FNV32_1a(e0 4d 9f cb) = 0
 SOLVED! What is the shortest binary data set for which the 64bit FNV1a hash is 0?
Scott Pakin
<>
on 2011Aug22 reported that there are
no solutions for binary data sets of length 7 or smaller.
64bit solution by an anonymous scientist
<>
on 2011Oct23:
The only solution for length 8 is:
FNV64_1a(d5 6b b9 53 42 87 08 36) = 0
 What is the shortest binary data set for which the 128bit FNV1a hash is 0?
 What is the shortest binary data set for which the 256bit FNV1a hash is 0?
 What is the shortest binary data set for which the 512bit FNV1a hash is 0?
 What is the shortest binary data set for which the 1024bit FNV1a hash is 0?
NOTE: By binary data set we mean any arbitrary collection of bits that
is a multple of 8 bits (1 octet) in length.
 SOLVED! What is the shortest set of consecutive NUL octets for which the 32bit FNV1 hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 64bit FNV1 hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 128bit FNV1 hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 256bit FNV1 hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 512bit FNV1 hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 1024bit FNV1 hash is 0?
NOTE: Russ Cox's solution below is for the set of 6 challenges immediately above
General FNV solution by Russ Cox
<>
on 2011Mar02:
There is no such stream of NUL octets.
Xor with an odd byte flips the parity of the hash.
Xor with an even byte leaves it alone, as does multiplying
by any of the (odd) FNV primes. Thus the final hash has
the same parity as the initial offset if and only if there
are an even number of odd bytes in the input. This is
the reason that all the offset bases have the same parity
(odd, it turns out), and it implies that any consecutive
stream of NULs will have an odd (nonzero) hash.
 SOLVED! What is the shortest set of consecutive NUL octets for which the 32bit FNV1a hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 64bit FNV1a hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 128bit FNV1a hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 256bit FNV1a hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 512bit FNV1a hash is 0?
 SOLVED! What is the shortest set of consecutive NUL octets for which the 1024bit FNV1a hash is 0?
NOTE: Russ Cox's solution below is for the set of 6 challenges immediately above
General FNV solution by Russ Cox
<>
on 2011Mar02:
There is no such stream of NUL octets.
Xor with an odd byte flips the parity of the hash.
Xor with an even byte leaves it alone, as does multiplying
by any of the (odd) FNV primes. Thus the final hash has
the same parity as the initial offset if and only if there
are an even number of odd bytes in the input. This is
the reason that all the offset bases have the same parity
(odd, it turns out), and it implies that any consecutive
stream of NULs will have an odd (nonzero) hash.
NOTE: By set of consecutive NUL octets we mean consecutive octets of 0 value.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 32bit FNV1 hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
428876705 0xff octets.
Peter de Rivaz
<>
independently confirmed this result.
Richard Heylen
<>
independently confirmed this result.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 64bit FNV1 hash is 0?
64bit solution by
Peter de Rivaz
<>
on 2011Dec13:
9896220416391497057 0xff octets.
Richard Heylen
<>
independently confirmed this result.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 128bit FNV1 hash is 0?
128bit solution by
Richard Heylen
<>
on 2011Dec14:
152812075112152085146780705563019820097 0xff octets.
Peter de Rivaz
<>
independently confirmed this result.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 256bit FNV1 hash is 0?
256bit solution by
Richard Heylen
<>
on 2011Dec14:
971310111339922874984865931636119693708047768520568964839262806324177446
08641 0xff octets.
Peter de Rivaz
<>
independently confirmed this result.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 512bit FNV1 hash is 0?
512bit solution by
Richard Heylen
<>
on 2011Dec14:
612806956068056576215461080927099484400241024395026354420378459322301684
399722907408508285157251830003265846176457230616192353760639874361657361
1559921729 0xff octets.
Peter de Rivaz
<>
independently confirmed this result.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 1024bit FNV1 hash is 0?
Richard Heylen
<>
on 2011Dec14 found a
1024bit solution, one that may not be the shortest:
416676424643376760772449487657397580462250574503060952762179226758571093
761689059455392577969506880247688215845019822014535567311051405867916840
497646798425786609620276239990874926250263846724497488057368971095038212
934393820920453733216924021449681744199270750560657371464991242494173425
0024772314731200245 0xff octets.
Peter de Rivaz
<>
independently confirmed this partial solution.
NOTE: Russ Cox
<>
also observed that as a consequence of his solution to the
consecutive NUL octet challences, any consecutive stream
of 0xff with a zero FNV1 or FNV1a hash of any size must be of odd length.
 SOLVED! What is the shortest set of consecutive 0xff octets for which the 32bit FNV1a hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
3039744951 0xff octets.
Peter de Rivaz
<>
independently confirmed this result.
Richard Heylen
<>
independently confirmed this result.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 64bit FNV1a hash is 0?
Peter de Rivaz
<>
on 2011Dec13 found a
64bit solution that may not be the shortest:
5125902172520635575 0xff octets.
Richard Heylen
<>
independently confirmed this partial solution.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 128bit FNV1a hash is 0?
Peter de Rivaz
<>
on 2012Mar22 found a
128bit solution that may not be the shortest:
195988526173479582814801599910495893127 0xff octets.
Richard Heylen
<>
independently confirmed this partial solution.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 256bit FNV1a hash is 0?
Peter de Rivaz
<>
on 2012Mar22 found a
256bit solution that may not be the shortest:
121365261308607922778298441917362349745681574069429011964286973126957522
07543 0xff octets.
Richard Heylen
<>
independently confirmed this partial solution.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 512bit FNV1a hash is 0?
Peter de Rivaz
<>
on 2012Mar22 found a
512bit solution that may not be the shortest:
445359075217293949446034810045247904893303946817563293272717969680141569
129699002471949546033702514868111823565737421304575683326671821385410536
5691076111 0xff octets.
Richard Heylen
<>
independently confirmed this partial solution.
 Partial solution: What is the shortest set of consecutive 0xff octets for which the 1024bit FNV1a hash is 0?
Peter de Rivaz
<>
on 2012Mar22 found a
1024bit solution that may not be the shortest:
712131032390661212423469446429778580303529367161714287727915539272088837
388997682828851224650621762650604398414532544740385461220466517818153731
651665570936392160298954932547331005615954561744064764751259871084045735
302812555692177957250787849447135140298017119914349292668850620197682629
52245579219890855775 0xff octets.
Richard Heylen
<>
independently confirmed this partial solution.
NOTE: Russ Cox
<>
observed that as a consequence of his solution to the
consecutive NUL octet challences, any consecutive stream
of 0xff with a zero FNV1 or FNV1a hash of any size must be of odd length.
NOTE: By set of consecutive 0xff octets we mean consecutive octets of 0xff value.
 SOLVED! What is the shortest nonNUL ASCII string for which the 32bit FNV1 hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 5 are:
FNV32_1(07 65 76 4a 3b) = 0 \a e v J ;
FNV32_1(27 0f 56 47 0a) = 0 ' ^O V G \n
FNV32_1(30 17 22 62 62) = 0 0 ^W " b b
FNV32_1(30 33 53 42 5b) = 0 0 3 S B [
FNV32_1(54 20 75 7b 5b) = 0 T space u { [
FNV32_1(62 61 2c 31 71) = 0 b a , 1 q
 SOLVED! What is the shortest nonNUL ASCII string for which the 64bit FNV1 hash is 0?
64bit solution by Peter de Rivaz
<>
on 2011Mar11:
The shortest solution is of length 10:
FNV64_1(10 17 34 7c 28 61 38 72 64 4d) = 0 ^P ^H 4 ! ( a 8 r d M
While there are other solutions of length 10, there are no solutions shorter
than length 10.
 What is the shortest nonNUL ASCII string for which the 128bit FNV1 hash is 0?
 What is the shortest nonNUL ASCII string for which the 256bit FNV1 hash is 0?
 What is the shortest nonNUL ASCII string for which the 512bit FNV1 hash is 0?
 What is the shortest nonNUL ASCII string for which the 1024bit FNV1 hash is 0?
 SOLVED! What is the shortest nonNUL ASCII string for which the 32bit FNV1a hash is 0?
32bit solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 5 are:
FNV32_1a(12 3b 5b 23 20) = 0 ^R ; [ # space
FNV32_1a(2b 21 3d 79 47) = 0 + ! = y G
FNV32_1a(2f 06 3c 37 71) = 0 / ^F < 7 q
FNV32_1a(36 38 6d 2a 20) = 0 6 8 m * space
FNV32_1a(40 24 1b 38 42) = 0 @ $ Esc 8 B
FNV32_1a(4c 39 59 56 11) = 0 L 9 Y V ^Q
FNV32_1a(59 08 26 60 62) = 0 Y \b & ` b
FNV32_1a(60 4a 63 6f 11) = 0 ` J c o ^Q
FNV32_1a(65 53 4e 2e 31) = 0 e S N . 1
 What is the shortest nonNUL ASCII string for which the 64bit FNV1a hash is 0?
 What is the shortest nonNUL ASCII string for which the 128bit FNV1a hash is 0?
 What is the shortest nonNUL ASCII string for which the 256bit FNV1a hash is 0?
 What is the shortest nonNUL ASCII string for which the 512bit FNV1a hash is 0?
 What is the shortest nonNUL ASCII string for which the 1024bit FNV1a hash is 0?
NOTE: By nonNUL ASCII string we mean any arbitrary collection of
nonNUL ASCII 8bit characters in the range: [0x01  0x7f].
Obviously the Cstyle terminating NUL octet is not included.
 SOLVED! What is the shortest printable ASCII string for which the 32bit FNV1 hash is 0?
32bit hash solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 5 are:
FNV32_1(30 33 53 42 5b) = 0 0 3 S B [
FNV32_1(54 20 75 7b 5b) = 0 T Space u { [
FNV32_1(62 61 2c 31 71) = 0 b a , 1 q
 What is the shortest printable ASCII string for which the 64bit FNV1 hash is 0?
 What is the shortest printable ASCII string for which the 128bit FNV1 hash is 0?
 What is the shortest printable ASCII string for which the 256bit FNV1 hash is 0?
 What is the shortest printable ASCII string for which the 512bit FNV1 hash is 0?
 What is the shortest printable ASCII string for which the 1024bit FNV1 hash is 0?
 SOLVED! What is the shortest printable ASCII string for which the 32bit FNV1a hash is 0?
32bit hash solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 5 are:
FNV32_1a(2b 21 3d 79 47) = 0 + ! = y G
FNV32_1a(36 38 6d 2a 20) = 0 6 8 m * Space
FNV32_1a(65 53 4e 2e 31) = 0 e S N . 1
 What is the shortest printable ASCII string for which the 64bit FNV1a hash is 0?
 What is the shortest printable ASCII string for which the 128bit FNV1a hash is 0?
 What is the shortest printable ASCII string for which the 256bit FNV1a hash is 0?
 What is the shortest printable ASCII string for which the 512bit FNV1a hash is 0?
 What is the shortest printable ASCII string for which the 1024bit FNV1a hash is 0?
NOTE: By printable ASCII string we mean any arbitrary collection of
printable ASCII 8bit characters in the range: [0x20  0x7e].
Obviously the Cstyle terminating NUL octet is not included.
 SOLVED! What is the shortest alphanumeric ASCII string for which the 32bit FNV1 hash is 0?
32bit hash solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 6 are:
FNV32_1(33 64 37 41 35 4b) = 0 3 d 7 A 5 K
FNV32_1(39 71 36 4d 71 33) = 0 9 q 6 M q 3
FNV32_1(48 48 59 53 4c 45) = 0 H H Y S L E
FNV32_1(54 72 4c 64 5a 31) = 0 T r L d Z 1
FNV32_1(56 4c 33 42 71 43) = 0 V L 3 B q C
FNV32_1(57 41 64 32 60 57) = 0 W A d 2 ` W
FNV32_1(59 55 6f 31 39 6c) = 0 Y U o 1 9 l
FNV32_1(59 66 36 68 50 36) = 0 Y f 6 h P 6
FNV32_1(68 49 72 6a 46 6a) = 0 h I r j F j
FNV32_1(6e 60 62 76 33 52) = 0 n ` b v 3 R
FNV32_1(70 6c 49 7a 6c 60) = 0 p l I z l `
FNV32_1(75 4d 6b 60 39 51) = 0 u M k ` 9 Q
FNV32_1(79 73 6f 70 48 6c) = 0 y s o p H l
FNV32_1(7a 63 49 6b 43 65) = 0 z c I k C e
 What is the shortest alphanumeric ASCII string for which the 64bit FNV1 hash is 0?
 What is the shortest alphanumeric ASCII string for which the 128bit FNV1 hash is 0?
 What is the shortest alphanumeric ASCII string for which the 256bit FNV1 hash is 0?
 What is the shortest alphanumeric ASCII string for which the 512bit FNV1 hash is 0?
 What is the shortest alphanumeric ASCII string for which the 1024bit FNV1 hash is 0?
 SOLVED! What is the shortest alphanumeric ASCII string for which the 32bit FNV1a hash is 0?
32bit hash solution by Russ Cox
<>
on 2011Mar02:
The solutions of length 6 are:
FNV32_1a(33 70 6a 4e 71 4d) = 0 3 p j N q M
FNV32_1a(35 52 30 4c 67 37) = 0 5 R 0 L g 7
FNV32_1a(37 6f 45 34 38 36) = 0 7 o E 4 8 6
FNV32_1a(42 52 34 32 71 66) = 0 B R 4 2 q f
FNV32_1a(46 6f 75 42 53 72) = 0 F o u B S r
FNV32_1a(47 6b 6b 7a 46 44) = 0 G k k z F D
FNV32_1a(48 56 47 5a 71 39) = 0 H V G Z q 9
FNV32_1a(49 77 50 53 64 54) = 0 I w P S d T
FNV32_1a(60 6e 72 59 33 47) = 0 ` n r Y 3 G
FNV32_1a(71 7a 73 30 55 44) = 0 q z s 0 U D
FNV32_1a(73 58 62 73 73 72) = 0 s X b s s r
FNV32_1a(75 68 34 74 53 49) = 0 u h 4 t S I
 What is the shortest alphanumeric ASCII string for which the 64bit FNV1a hash is 0?
 What is the shortest alphanumeric ASCII string for which the 128bit FNV1a hash is 0?
 What is the shortest alphanumeric ASCII string for which the 256bit FNV1a hash is 0?
 What is the shortest alphanumeric ASCII string for which the 512bit FNV1a hash is 0?
 What is the shortest alphanumeric ASCII string for which the 1024bit FNV1a hash is 0?
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of
alphanumeric ASCII 8bit characters in the range: [0x30  0x39, 0x41  0x5a, 0x60  0x7a]
Obviously the Cstyle terminating NUL octet is not included.
