1 /* $NetBSD: hash_fnv.c,v 1.3 2023/12/23 20:30:46 christos Exp $ */
2
3 /*++
4 /* NAME
5 /* hash_fnv 3
6 /* SUMMARY
7 /* Fowler/Noll/Vo hash function
8 /* SYNOPSIS
9 /* #include <hash_fnv.h>
10 /*
11 /* HASH_FNV_T hash_fnv(
12 /* const void *src,
13 /* size_t len)
14 /*
15 /* HASH_FNV_T hash_fnvz(
16 /* const char *src)
17 /* DESCRIPTION
18 /* hash_fnv() implements a modified FNV type 1a hash function.
19 /*
20 /* hash_fnvz() provides the same functionality for null-terminated
21 /* strings, avoiding an unnecessary strlen() call.
22 /*
23 /* To thwart collision attacks, the hash function is seeded
24 /* once with ldseed(). To disable seeding (typically, to make
25 /* tests predictable), specify the NORANDOMIZE environment
26 /* variable; the value does not matter.
27 /*
28 /* This implementation works around a "sticky state" problem
29 /* with FNV hash functions: when an input produces a zero hash
30 /* state, and the next input byte is zero, then the hash state
31 /* would not change. To avoid this, hash_fnv() adds 1 to each
32 /* input value. Compile with -DSTRICT_FNV1A to get the standard
33 /* behavior.
34 /*
35 /* The default HASH_FNV_T result type is uint64_t. When compiled
36 /* with -DUSE_FNV_32BIT, the result type is uint32_t. On ancient
37 /* systems without <stdint.h>, define HASH_FNV_T on the compiler
38 /* command line as an unsigned 32-bit or 64-bit integer type,
39 /* and specify -DUSE_FNV_32BIT when HASH_FNV_T is a 32-bit type.
40 /* SEE ALSO
41 /* http://www.isthe.com/chongo/tech/comp/fnv/index.html
42 /* https://softwareengineering.stackexchange.com/questions/49550/
43 /* LICENSE
44 /* .ad
45 /* .fi
46 /* The Secure Mailer license must be distributed with this software.
47 /* AUTHOR(S)
48 /* Wietse Venema
49 /* Google, Inc.
50 /* 111 8th Avenue
51 /* New York, NY 10011, USA
52 /*--*/
53
54 /*
55 * System library
56 */
57 #include <sys_defs.h>
58 #include <stdlib.h>
59 #include <unistd.h>
60
61 /*
62 * Utility library.
63 */
64 #include <msg.h>
65 #include <ldseed.h>
66 #include <hash_fnv.h>
67
68 /*
69 * Application-specific.
70 */
71 #ifdef USE_FNV_32BIT
72 #define FNV_prime 0x01000193UL
73 #define FNV_offset_basis 0x811c9dc5UL
74 #else
75 #define FNV_prime 0x00000100000001B3ULL
76 #define FNV_offset_basis 0xcbf29ce484222325ULL
77 #endif
78
79 /*
80 * Workaround for the sticky all-zero hash state: when the next input byte
81 * is zero, then the operations "hash ^= 0" and "hash *= FNV_prime" would
82 * not change the hash state. To avoid that, add 1 to the every input value.
83 */
84 #ifdef STRICT_FNV1A
85 #define HASH_FNV_NEW_BITS(new_bits) (new_bits)
86 #else
87 #define HASH_FNV_NEW_BITS(new_bits) (1 + (new_bits))
88 #endif
89
90 static HASH_FNV_T hash_fnv_basis = FNV_offset_basis;
91 static int hash_fnv_must_init = 1;
92
93 /* hash_fnv_init - seed the hash */
94
hash_fnv_init(void)95 static void hash_fnv_init(void)
96 {
97 HASH_FNV_T seed;
98
99 if (!getenv("NORANDOMIZE")) {
100 ldseed(&seed, sizeof(seed));
101 hash_fnv_basis ^= seed;
102 }
103 hash_fnv_must_init = 0;
104 }
105
106 /* hash_fnv - modified FNV 1a hash */
107
hash_fnv(const void * src,size_t len)108 HASH_FNV_T hash_fnv(const void *src, size_t len)
109 {
110 HASH_FNV_T hash;
111 HASH_FNV_T new_bits;
112
113 if (hash_fnv_must_init)
114 hash_fnv_init();
115
116 hash = hash_fnv_basis;
117 while (len-- > 0) {
118 new_bits = *(unsigned char *) src++;
119 hash ^= HASH_FNV_NEW_BITS(new_bits);
120 hash *= FNV_prime;
121 }
122 return (hash);
123 }
124
125 /* hash_fnvz - modified FNV 1a hash for null-terminated strings */
126
hash_fnvz(const char * src)127 HASH_FNV_T hash_fnvz(const char *src)
128 {
129 HASH_FNV_T hash;
130 HASH_FNV_T new_bits;
131
132 if (hash_fnv_must_init)
133 hash_fnv_init();
134
135 hash = hash_fnv_basis;
136 while ((new_bits = *(unsigned char *) src++) != 0) {
137 hash ^= HASH_FNV_NEW_BITS(new_bits);
138 hash *= FNV_prime;
139 }
140 return (hash);
141 }
142
143 #ifdef TEST
144 #include <stdlib.h>
145 #include <string.h>
146 #include <msg.h>
147
main(void)148 int main(void)
149 {
150 int pass = 0;
151 int fail = 0;
152
153 /*
154 * Sanity check.
155 */
156 #ifdef STRICT_FNV1A
157 msg_fatal("This test requires no STRICT_FNV1A");
158 #endif
159
160 /*
161 * Force unseeded hash, to make tests predictable.
162 */
163 if (putenv("NORANDOMIZE=") != 0)
164 msg_fatal("putenv(\"NORANDOMIZE=\"): %m");
165
166 /*
167 * Test: hashing produces the expected results.
168 */
169 {
170 struct testcase {
171 HASH_FNV_T hval;
172 const char *str;
173 };
174 static struct testcase testcases[] =
175 {
176 #ifdef USE_FNV_32BIT
177 0x1c00fc06UL, "overdeeply",
178 0x1c00fc06UL, "undescript",
179 0x1e1e52a4UL, "fanfold",
180 0x1e1e52a4UL, "phrensied",
181 #else
182 0xda19999ec0bda706ULL, "overdeeply",
183 0xd7b9e43f26396a66ULL, "undescript",
184 0xa50c585d385a2604ULL, "fanfold",
185 0x1ec3ef9bb2b734a4ULL, "phrensied",
186 #endif
187 0,
188 };
189 struct testcase *tp;
190 HASH_FNV_T hval;
191 int test_failed;
192
193 for (tp = testcases; tp->str; tp++) {
194 test_failed = 0;
195 if ((hval = hash_fnvz(tp->str)) != tp->hval) {
196 msg_warn("hash_fnv(\"%s\") want %lu, got: %lu",
197 tp->str, (unsigned long) tp->hval,
198 (unsigned long) hval);
199 test_failed = 1;
200 }
201 if (test_failed) {
202 fail += 1;
203 msg_info("FAIL: %s", tp->str);
204 } else {
205 pass += 1;
206 msg_info("PASS: %s", tp->str);
207 }
208 }
209 }
210
211 /*
212 * Test: hash_fnvz(s) is equivalent to hash_fnv(s, strlen(s)). No need to
213 * verify the actual result; we already did that above.
214 */
215 {
216 const char *strval = "foobar";
217 HASH_FNV_T h1 = hash_fnv(strval, strlen(strval));
218 HASH_FNV_T h2 = hash_fnvz(strval);
219
220 if (h1 == h2) {
221 pass += 1;
222 msg_info("PASS: hash_fnvz(\"%s\") == hash_fnv(\"%s\", %ld)",
223 strval, strval, (long) strlen(strval));
224 } else {
225 fail += 1;
226 msg_info("FAIL: hash_fnvz(\"%s\") == hash_fnv(\"%s\", %ld)",
227 strval, strval, (long) strlen(strval));
228 }
229 }
230
231
232 /*
233 * Wrap up.
234 */
235 msg_info("PASS=%d FAIL=%d", pass, fail);
236 return (fail != 0);
237 }
238
239 #endif
240