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 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 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 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 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