1 /*
2 * hash_32 - 32 bit Fowler/Noll/Vo hash code
3 *
4 *
5 ***
6 *
7 * Fowler/Noll/Vo hash
8 *
9 * The basis of this hash algorithm was taken from an idea sent
10 * as reviewer comments to the IEEE POSIX P1003.2 committee by:
11 *
12 * Phong Vo (http://www.research.att.com/info/kpv/)
13 * Glenn Fowler (http://www.research.att.com/~gsf/)
14 *
15 * In a subsequent ballot round:
16 *
17 * Landon Curt Noll (http://reality.sgi.com/chongo/)
18 *
19 * improved on their algorithm. Some people tried this hash
20 * and found that it worked rather well. In an EMail message
21 * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
22 *
23 * FNV hashes are architected to be fast while maintaining a low
24 * collision rate. The FNV speed allows one to quickly hash lots
25 * of data while maintaining a reasonable collision rate. See:
26 *
27 * http://reality.sgi.com/chongo/tech/comp/fnv/
28 *
29 * for more details as well as other forms of the FNV hash.
30 ***
31 *
32 * NOTE: The FNV-0 historic hash is not recommended. One should use
33 * the FNV-1 hash instead.
34 *
35 * To use the 32 bit FNV-0 historic hash, pass FNV0_32_INIT as the
36 * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
37 *
38 * To use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the
39 * Fnv32_t hashval argument to fnv_32_buf() or fnv_32_str().
40 *
41 ***
42 *
43 * Please do not copyright this code. This code is in the public domain.
44 *
45 * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
46 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
47 * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
48 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
49 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
50 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
51 * PERFORMANCE OF THIS SOFTWARE.
52 *
53 * By:
54 * chongo <Landon Curt Noll> /\oo/\
55 * http://reality.sgi.com/chongo/
56 * EMail: chongo_fnv at prime dot engr dot sgi dot com
57 *
58 * Share and Enjoy! :-)
59 */
60
61 #include <stdlib.h>
62 #include "fnv.h"
63
64
65 /*
66 * 32 bit magic FNV-0 and FNV-1 prime
67 */
68 #define FNV_32_PRIME ((Fnv32_t)0x01000193)
69
70
71 /*
72 * fnv_32_buf - perform a 32 bit Fowler/Noll/Vo hash on a buffer
73 *
74 * input:
75 * buf - start of buffer to hash
76 * len - length of buffer in octets
77 * hval - previous hash value or 0 if first call
78 *
79 * returns:
80 * 32 bit hash as a static hash type
81 *
82 * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval
83 * argument on the first call to either fnv_32_buf() or fnv_32_str().
84 *
85 * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval
86 * argument on the first call to either fnv_32_buf() or fnv_32_str().
87 */
88 Fnv32_t
fnv_32_buf(const void * buf,size_t len,Fnv32_t hval)89 fnv_32_buf(const void *buf, size_t len, Fnv32_t hval)
90 {
91 const unsigned char *bp = (const unsigned char *)buf; /* start of buffer */
92 const unsigned char *be = bp + len; /* beyond end of buffer */
93
94 /*
95 * FNV-1 hash each octet in the buffer
96 */
97 while (bp < be) {
98
99 /* multiply by the 32 bit FNV magic prime mod 2^64 */
100 hval *= FNV_32_PRIME;
101
102 /* xor the bottom with the current octet */
103 hval ^= (Fnv32_t)*bp++;
104 }
105
106 /* return our new hash value */
107 return hval;
108 }
109
110
111 /*
112 * fnv_32_str - perform a 32 bit Fowler/Noll/Vo hash on a string
113 *
114 * input:
115 * str - string to hash
116 * hval - previous hash value or 0 if first call
117 *
118 * returns:
119 * 32 bit hash as a static hash type
120 *
121 * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval
122 * argument on the first call to either fnv_32_buf() or fnv_32_str().
123 *
124 * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval
125 * argument on the first call to either fnv_32_buf() or fnv_32_str().
126 */
127 Fnv32_t
fnv_32_str(const char * str,Fnv32_t hval)128 fnv_32_str(const char *str, Fnv32_t hval)
129 {
130 const unsigned char *s = (const unsigned char *)str; /* unsigned string */
131
132 /*
133 * FNV-1 hash each octet in the buffer
134 */
135 while (*s) {
136
137 /* multiply by the 32 bit FNV magic prime mod 2^64 */
138 hval *= FNV_32_PRIME;
139
140 /* xor the bottom with the current octet */
141 hval ^= (Fnv32_t)*s++;
142 }
143
144 /* return our new hash value */
145 return hval;
146 }
147
148 /* a wrapper function for fnv_32_str */
FnvHash(const char * str)149 unsigned long FnvHash(const char *str)
150 {
151 return fnv_32_str(str,FNV1_32_INIT);
152 }
153