1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#=====================#
# Fowler/Noll/Vo hash #
#=====================#
The basis of this hash algorithm was taken from an idea sent
as reviewer comments to the IEEE POSIX P1003.2 committee by:
Phong Vo (http://www.research.att.com/info/kpv)
Glenn Fowler (http://www.research.att.com/~gsf/)
In a subsequent ballot round:
Landon Curt Noll (http://www.isthe.com/chongo)
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. See:
http://www.isthe.com/chongo/tech/comp/fnv/index.html
for more details as well as other forms of the FNV hash.
Comments, questions, bug fixes and suggestions welcome at
the address given in the above URL.
#==================#
# FNV hash utility #
#==================#
Two hash utilities (32 bit and 64 bit) are provided:
fnv032 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
fnv132 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
fnv1a32 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
fnv064 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
fnv164 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
fnv1a64 [-b bcnt] [-m] [-s arg] [-t code] [-v] [arg ...]
-b bcnt mask off all but the lower bcnt bits (default: 32)
-m multiple hashes, one per line for each arg
-s hash arg as a string (ignoring terminating NUL bytes)
-t code 0 ==> generate test vectors, 1 ==> test FNV hash
-v verbose mode, print arg after hash (implies -m)
arg string (if -s was given) or filename (default stdin)
The fnv032, fnv064 implement the historic FNV-0 hash.
The fnv132, fnv164 implement the recommended FNV-1 hash.
The fnv1a32, fnv1a64 implement the recommended FNV-1a hash.
This is the original historic FNV algorithm with a 0 offset basis.
It is recommended that FNV-1, with a non-0 offset basis be used instead.
To test FNV hashes, 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
If you are compiling, try:
make check
#==================#
# FNV hash library #
#==================#
The libfnv.a library implements both a 32 bit and a 64 bit FNV hash
on collections of bytes, a NUL terminated strings or on an open file
descriptor.
Here is the 32 bit FNV 1 hash:
Fnv32_t fnv_32_buf(void *buf, int len, Fnv32_t hval); /* byte buf */
Fnv32_t fnv_32_str(char *string, Fnv32_t hval); /* string */
Here is the 32 bit FNV 1a hash:
Fnv32_t fnv_32a_buf(void *buf, int len, Fnv32_t hval); /* byte buf */
Fnv32_t fnv_32a_str(char *string, Fnv32_t hval); /* string */
Here is the 64 bit FNV 1 hash:
Fnv64_t fnv_64_buf(void *buf, int len, Fnv64_t hval); /* byte buf */
Fnv64_t fnv_64_str(char *string, Fnv64_t hval); /* string */
Here is the 64 bit FNV 1a hash:
Fnv64_t fnv_64a_buf(void *buf, int len, Fnv64_t hval); /* byte buf */
Fnv64_t fnv_64a_str(char *string, Fnv64_t hval); /* string */
On the first call to a hash function, one must supply the initial basis
that is appropriate for the hash in question:
FNV-0: (not recommended)
FNV0_32_INIT /* 32 bit FNV-0 initial basis */
FNV0_64_INIT /* 64 bit FNV-0 initial basis */
FNV-1:
FNV1_32_INIT /* 32 bit FNV-1 initial basis */
FNV1_64_INIT /* 64 bit FNV-1 initial basis */
FNV-1a:
FNV1A_32_INIT /* 32 bit FNV-1a initial basis */
FNV1A_64_INIT /* 64 bit FNV-1a initial basis */
For example to perform a 64 bit FNV-1 hash:
#include "fnv.h"
Fnv64_t hash_val;
hash_val = fnv_64_str("a string", FNV1_64_INIT);
hash_val = fnv_64_str("more string", hash_val);
produces the same final hash value as:
hash_val = fnv_64_str("a stringmore string", FNV1_64_INIT);
NOTE: If one used 'FNV0_64_INIT' instead of 'FNV1_64_INIT' one would get the
historic FNV-0 hash instead recommended FNV-1 hash.
To perform a 32 bit FNV-1 hash:
#include "fnv.h"
Fnv32_t hash_val;
hash_val = fnv_32_buf(buf, length_of_buf, FNV1_32_INIT);
hash_val = fnv_32_str("more data", hash_val);
To perform a 64 bit FNV-1a hash:
#include "fnv.h"
Fnv64_t hash_val;
hash_val = fnv_64a_buf(buf, length_of_buf, FNV1_64_INIT);
hash_val = fnv_64a_str("more data", hash_val);
=-=
chongo <Landon Curt Noll> /\oo/\
http://www.isthe.com/chongo
Share and Enjoy!
|
