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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
|
/*++
/* NAME
/* hash_fnv 3
/* SUMMARY
/* Fowler/Noll/Vo hash function
/* SYNOPSIS
/* #include <hash_fnv.h>
/*
/* HASH_FNV_T hash_fnv(
/* const void *src,
/* size_t len)
/*
/* HASH_FNV_T hash_fnvz(
/* const char *src)
/* DESCRIPTION
/* hash_fnv() implements a modified FNV type 1a hash function.
/*
/* hash_fnvz() provides the same functionality for null-terminated
/* strings, avoiding an unnecessary strlen() call.
/*
/* To thwart collision attacks, the hash function is seeded
/* once with ldseed(). To disable seeding (typically, to make
/* tests predictable), specify the NORANDOMIZE environment
/* variable; the value does not matter.
/*
/* This implementation works around a "sticky state" problem
/* with FNV hash functions: when an input produces a zero hash
/* state, and the next input byte is zero, then the hash state
/* would not change. To avoid this, hash_fnv() adds 1 to each
/* input value. Compile with -DSTRICT_FNV1A to get the standard
/* behavior.
/*
/* The default HASH_FNV_T result type is uint64_t. When compiled
/* with -DUSE_FNV_32BIT, the result type is uint32_t. On ancient
/* systems without <stdint.h>, define HASH_FNV_T on the compiler
/* command line as an unsigned 32-bit or 64-bit integer type,
/* and specify -DUSE_FNV_32BIT when HASH_FNV_T is a 32-bit type.
/* SEE ALSO
/* http://www.isthe.com/chongo/tech/comp/fnv/index.html
/* https://softwareengineering.stackexchange.com/questions/49550/
/* LICENSE
/* .ad
/* .fi
/* The Secure Mailer license must be distributed with this software.
/* AUTHOR(S)
/* Wietse Venema
/* Google, Inc.
/* 111 8th Avenue
/* New York, NY 10011, USA
/*--*/
/*
* System library
*/
#include <sys_defs.h>
#include <stdlib.h>
#include <unistd.h>
/*
* Utility library.
*/
#include <msg.h>
#include <ldseed.h>
#include <hash_fnv.h>
/*
* Application-specific.
*/
#ifdef USE_FNV_32BIT
#define FNV_prime 0x01000193UL
#define FNV_offset_basis 0x811c9dc5UL
#else
#define FNV_prime 0x00000100000001B3ULL
#define FNV_offset_basis 0xcbf29ce484222325ULL
#endif
/*
* Workaround for the sticky all-zero hash state: when the next input byte
* is zero, then the operations "hash ^= 0" and "hash *= FNV_prime" would
* not change the hash state. To avoid that, add 1 to the every input value.
*/
#ifdef STRICT_FNV1A
#define HASH_FNV_NEW_BITS(new_bits) (new_bits)
#else
#define HASH_FNV_NEW_BITS(new_bits) (1 + (new_bits))
#endif
static HASH_FNV_T hash_fnv_basis = FNV_offset_basis;
static int hash_fnv_must_init = 1;
/* hash_fnv_init - seed the hash */
static void hash_fnv_init(void)
{
HASH_FNV_T seed;
if (!getenv("NORANDOMIZE")) {
ldseed(&seed, sizeof(seed));
hash_fnv_basis ^= seed;
}
hash_fnv_must_init = 0;
}
/* hash_fnv - modified FNV 1a hash */
HASH_FNV_T hash_fnv(const void *src, size_t len)
{
HASH_FNV_T hash;
HASH_FNV_T new_bits;
if (hash_fnv_must_init)
hash_fnv_init();
hash = hash_fnv_basis;
while (len-- > 0) {
new_bits = *(unsigned char *) src++;
hash ^= HASH_FNV_NEW_BITS(new_bits);
hash *= FNV_prime;
}
return (hash);
}
/* hash_fnvz - modified FNV 1a hash for null-terminated strings */
HASH_FNV_T hash_fnvz(const char *src)
{
HASH_FNV_T hash;
HASH_FNV_T new_bits;
if (hash_fnv_must_init)
hash_fnv_init();
hash = hash_fnv_basis;
while ((new_bits = *(unsigned char *) src++) != 0) {
hash ^= HASH_FNV_NEW_BITS(new_bits);
hash *= FNV_prime;
}
return (hash);
}
#ifdef TEST
#include <stdlib.h>
#include <string.h>
#include <msg.h>
int main(void)
{
int pass = 0;
int fail = 0;
/*
* Sanity check.
*/
#ifdef STRICT_FNV1A
msg_fatal("This test requires no STRICT_FNV1A");
#endif
/*
* Force unseeded hash, to make tests predictable.
*/
if (putenv("NORANDOMIZE=") != 0)
msg_fatal("putenv(\"NORANDOMIZE=\"): %m");
/*
* Test: hashing produces the expected results.
*/
{
struct testcase {
HASH_FNV_T hval;
const char *str;
};
static struct testcase testcases[] =
{
#ifdef USE_FNV_32BIT
0x1c00fc06UL, "overdeeply",
0x1c00fc06UL, "undescript",
0x1e1e52a4UL, "fanfold",
0x1e1e52a4UL, "phrensied",
#else
0xda19999ec0bda706ULL, "overdeeply",
0xd7b9e43f26396a66ULL, "undescript",
0xa50c585d385a2604ULL, "fanfold",
0x1ec3ef9bb2b734a4ULL, "phrensied",
#endif
0,
};
struct testcase *tp;
HASH_FNV_T hval;
int test_failed;
for (tp = testcases; tp->str; tp++) {
test_failed = 0;
if ((hval = hash_fnvz(tp->str)) != tp->hval) {
msg_warn("hash_fnv(\"%s\") want %lu, got: %lu",
tp->str, (unsigned long) tp->hval,
(unsigned long) hval);
test_failed = 1;
}
if (test_failed) {
fail += 1;
msg_info("FAIL: %s", tp->str);
} else {
pass += 1;
msg_info("PASS: %s", tp->str);
}
}
}
/*
* Test: hash_fnvz(s) is equivalent to hash_fnv(s, strlen(s)). No need to
* verify the actual result; we already did that above.
*/
{
const char *strval = "foobar";
HASH_FNV_T h1 = hash_fnv(strval, strlen(strval));
HASH_FNV_T h2 = hash_fnvz(strval);
if (h1 == h2) {
pass += 1;
msg_info("PASS: hash_fnvz(\"%s\") == hash_fnv(\"%s\", %ld)",
strval, strval, (long) strlen(strval));
} else {
fail += 1;
msg_info("FAIL: hash_fnvz(\"%s\") == hash_fnv(\"%s\", %ld)",
strval, strval, (long) strlen(strval));
}
}
/*
* Wrap up.
*/
msg_info("PASS=%d FAIL=%d", pass, fail);
return (fail != 0);
}
#endif
|
