7885c3ed2d1863dedc1eb7ba88e25759d269735a
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 */
61 #include <stdlib.h>
62 #include "fnv.h"
65 /*
66 * 32 bit magic FNV-0 and FNV-1 prime
67 */
68 #define FNV_32_PRIME ((Fnv32_t)0x01000193)
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(
89 const void *buf,
90 size_t len,
91 Fnv32_t hval)
92 {
93 const unsigned char *bp = (const unsigned char *) buf; /* start of buffer */
94 const unsigned char *be = bp + len; /* beyond end of buffer */
96 /*
97 * FNV-1 hash each octet in the buffer
98 */
99 while (bp < be) {
101 /* multiply by the 32 bit FNV magic prime mod 2^64 */
102 hval *= FNV_32_PRIME;
104 /* xor the bottom with the current octet */
105 hval ^= (Fnv32_t) *bp++;
106 }
108 /* return our new hash value */
109 return hval;
110 }
113 /*
114 * fnv_32_str - perform a 32 bit Fowler/Noll/Vo hash on a string
115 *
116 * input:
117 * str - string to hash
118 * hval - previous hash value or 0 if first call
119 *
120 * returns:
121 * 32 bit hash as a static hash type
122 *
123 * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval
124 * argument on the first call to either fnv_32_buf() or fnv_32_str().
125 *
126 * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval
127 * argument on the first call to either fnv_32_buf() or fnv_32_str().
128 */
129 Fnv32_t fnv_32_str(
130 const char *str,
131 Fnv32_t hval)
132 {
133 const unsigned char *s = (const unsigned char *) str; /* unsigned string */
135 /*
136 * FNV-1 hash each octet in the buffer
137 */
138 while (*s) {
140 /* multiply by the 32 bit FNV magic prime mod 2^64 */
141 hval *= FNV_32_PRIME;
143 /* xor the bottom with the current octet */
144 hval ^= (Fnv32_t) *s++;
145 }
147 /* return our new hash value */
148 return hval;
149 }
151 /* a wrapper function for fnv_32_str */
152 unsigned long FnvHash(
153 const char *str)
154 {
155 return fnv_32_str(str, FNV1_32_INIT);
156 }