1 /*
2 * Copyright (C) 1997-2004, Michael Jennings
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies of the Software, its documentation and marketing & publicity
13 * materials, and acknowledgment shall be given in the documentation, materials
14 * and software packages that this Software was used.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
20 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23
24 static const char __attribute__((unused)) cvs_ident[] = "$Id: builtin_hashes.c,v 1.3 2004/07/23 21:38:39 mej Exp $";
25
26 #ifdef HAVE_CONFIG_H
27 # include <config.h>
28 #endif
29
30 #include <libast_internal.h>
31
32 #define BUILTIN_RANDOM_SEED (SPIF_CAST(uint32) 0xf721b64d)
33
34 /*
35 * Bob Jenkins' hash algorithm as published in December 1996. Public
36 * domain. See http://burtleburtle.net/bob/hash/
37 */
38
39 /**
40 * Hashes a variable-length key into a 32-bit unsigned integer value.
41 *
42 * This function hashes a bitstream of a given length into a 32-bit
43 * hash value suitable for use in hash tables. Note that this
44 * function should NOT be used for cryptography. About 6n+36
45 * instructions for an n-byte key.
46 *
47 * For a hash value of w bits, the returned value should be
48 * bitwise-AND'd with SPIFHASH_MASK(w), and the hash table should
49 * have SPIFHASH_SIZE(w) buckets.
50 *
51 * @param key Pointer to bitstream holding key.
52 * @param length Number of bytes in bitstream.
53 * @param seed The last hash value returned, or an arbitrary seed
54 * value.
55 * @return A 32-bit hash value.
56 *
57 */
58 spif_uint32_t
spifhash_jenkins(register spif_uint8_t * key,register spif_uint32_t length,register spif_uint32_t seed)59 spifhash_jenkins(register spif_uint8_t *key, register spif_uint32_t length, register spif_uint32_t seed)
60 {
61 register spif_uint32_t a, b, c, len;
62
63 len = length;
64 a = b = BUILTIN_RANDOM_SEED; /* This can be any 32-bit value. */
65 c = seed;
66
67 /* The loop below handles most of the key (all but the last
68 length % 12 bytes). */
69 while (len >= 12) {
70 a += (key[0] + (SPIF_CAST(uint32) key[1] << 8) + (SPIF_CAST(uint32) key[2] << 16) + (SPIF_CAST(uint32) key[3] << 24));
71 b += (key[4] + (SPIF_CAST(uint32) key[5] << 8) + (SPIF_CAST(uint32) key[6] << 16) + (SPIF_CAST(uint32) key[7] << 24));
72 c += (key[8] + (SPIF_CAST(uint32) key[9] << 8) + (SPIF_CAST(uint32) key[10] << 16) + (SPIF_CAST(uint32) key[11] << 24));
73 SPIFHASH_JENKINS_MIX(a, b, c);
74 key += 12;
75 len -= 12;
76 }
77
78 /* The switch below handles the last length % 12 (0 through 11)
79 bytes. All cases drop through to the next case. */
80 c += length;
81 switch (len) {
82 case 11: c += (SPIF_CAST(uint32) key[10] << 24);
83 case 10: c += (SPIF_CAST(uint32) key[9] << 16);
84 case 9: c += (SPIF_CAST(uint32) key[8] << 8);
85 case 8: b += (SPIF_CAST(uint32) key[7] << 24);
86 case 7: b += (SPIF_CAST(uint32) key[6] << 16);
87 case 6: b += (SPIF_CAST(uint32) key[5] << 8);
88 case 5: b += key[4];
89 case 4: a += (SPIF_CAST(uint32) key[3] << 24);
90 case 3: a += (SPIF_CAST(uint32) key[2] << 16);
91 case 2: a += (SPIF_CAST(uint32) key[1] << 8);
92 case 1: a += key[0];
93 /* case 0: nothing left to add */
94 }
95 SPIFHASH_JENKINS_MIX(a, b, c);
96
97 return c;
98 }
99
100 /**
101 * Hashes a variable-length key into a 32-bit unsigned integer value.
102 *
103 * This function hashes a series of 32-bit unsigned integers of a
104 * given length into a 32-bit hash value suitable for use in hash
105 * tables. This hash is basically identical to spifhash_jenkins(), except
106 * that the key length must be a whole number of 32-bit dword's, and
107 * the length is given in spif_uint32_t's, not bytes. It is much
108 * faster than spifhash_jenkins(), so if padding keys to 32 bit chunks is
109 * inexpensive, this function is probably preferable.
110 *
111 * @param key Pointer to bitstream holding key.
112 * @param length Number of 32-bit integers in bitstream.
113 * @param seed The last hash value returned, or an arbitrary seed
114 * value.
115 * @return A 32-bit hash value.
116 *
117 */
118 spif_uint32_t
spifhash_jenkins32(spif_uint8_t * key,register spif_uint32_t length,register spif_uint32_t seed)119 spifhash_jenkins32(spif_uint8_t *key, register spif_uint32_t length, register spif_uint32_t seed)
120 {
121 register spif_uint32_t a, b, c, len;
122 register spif_uint32_t *key_dword = SPIF_CAST_PTR(uint32) key;
123
124 len = length;
125 a = b = BUILTIN_RANDOM_SEED; /* This can be any 32-bit value. */
126 c = seed;
127
128 /* The loop below handles most of the key (all but the last
129 length % 3 uint32's). */
130 while (len >= 3) {
131 a += key_dword[0];
132 b += key_dword[1];
133 c += key_dword[2];
134 SPIFHASH_JENKINS_MIX(a, b, c);
135 key_dword += 3;
136 len -= 3;
137 }
138
139 /* The switch below handles the last length % 3 (0 through 2)
140 uint32's. All cases drop through to the next case. */
141 c += length;
142 switch (len) {
143 case 2: b += key_dword[1];
144 case 1: a += key_dword[0];
145 /* case 0: nothing left to add */
146 }
147 SPIFHASH_JENKINS_MIX(a, b, c);
148
149 return c;
150 }
151
152 #if !(WORDS_BIGENDIAN)
153 /**
154 * Hashes a variable-length key into a 32-bit unsigned integer value.
155 *
156 * This function hashes a bitstream of a given length into a 32-bit
157 * hash value suitable for use in hash tables. This hash is basically
158 * identical to spifhash_jenkins(), except that it only works on
159 * little-endian machines (e.g., Intel x86 and VAX). It is faster
160 * than spifhash_jenkins(), so it should be preferred on little-endian
161 * systems.
162 *
163 * @param key Pointer to bitstream holding key.
164 * @param length Number of bytes in bitstream.
165 * @param seed The last hash value returned, or an arbitrary seed
166 * value.
167 * @return A 32-bit hash value.
168 *
169 */
170 spif_uint32_t
spifhash_jenkinsLE(register spif_uint8_t * key,register spif_uint32_t length,register spif_uint32_t seed)171 spifhash_jenkinsLE(register spif_uint8_t *key, register spif_uint32_t length, register spif_uint32_t seed)
172 {
173 register spif_uint32_t a, b, c, len;
174
175 len = length;
176 a = b = BUILTIN_RANDOM_SEED; /* This can be any 32-bit value. */
177 c = seed;
178
179 /* The loop below handles most of the key (all but the last
180 length % 12 bytes). */
181 if ((SPIF_CAST(uint32) key) & 3) {
182 /* Not 32-bit aligned. Use old method. */
183 while (len >= 12) {
184 a += (key[0] + (SPIF_CAST(uint32) key[1] << 8) + (SPIF_CAST(uint32) key[2] << 16) + (SPIF_CAST(uint32) key[3] << 24));
185 b += (key[4] + (SPIF_CAST(uint32) key[5] << 8) + (SPIF_CAST(uint32) key[6] << 16) + (SPIF_CAST(uint32) key[7] << 24));
186 c += (key[8] + (SPIF_CAST(uint32) key[9] << 8) + (SPIF_CAST(uint32) key[10] << 16) + (SPIF_CAST(uint32) key[11] << 24));
187 SPIFHASH_JENKINS_MIX(a, b, c);
188 key += 12;
189 len -= 12;
190 }
191 } else {
192 /* 32-bit aligned. Use speedier method. */
193 while (len >= 12) {
194 /* These three lines are the only ones which differ from
195 spifhash_jenkins(). */
196 a += *(SPIF_CAST_PTR(uint32) key);
197 b += *(SPIF_CAST_PTR(uint32) (key + 4));
198 c += *(SPIF_CAST_PTR(uint32) (key + 8));
199 SPIFHASH_JENKINS_MIX(a, b, c);
200 key += 12;
201 len -= 12;
202 }
203 }
204
205 /* The switch below handles the last length % 12 (0 through 11)
206 bytes. All cases drop through to the next case. */
207 c += length;
208 switch (len) {
209 case 11:
210 c += (SPIF_CAST(uint32) key[10] << 24);
211 case 10:
212 c += (SPIF_CAST(uint32) key[9] << 16);
213 case 9:
214 c += (SPIF_CAST(uint32) key[8] << 8);
215 case 8:
216 b += (SPIF_CAST(uint32) key[7] << 24);
217 case 7:
218 b += (SPIF_CAST(uint32) key[6] << 16);
219 case 6:
220 b += (SPIF_CAST(uint32) key[5] << 8);
221 case 5:
222 b += key[4];
223 case 4:
224 a += (SPIF_CAST(uint32) key[3] << 24);
225 case 3:
226 a += (SPIF_CAST(uint32) key[2] << 16);
227 case 2:
228 a += (SPIF_CAST(uint32) key[1] << 8);
229 case 1:
230 a += key[0];
231 /* case 0: nothing left to add */
232 }
233 SPIFHASH_JENKINS_MIX(a, b, c);
234
235 return c;
236 }
237 #endif
238
239
240 /**
241 * The rotating hash.
242 *
243 * This is an implementation of a rotating hash algorithm with a
244 * slight modification so that it can be used with a 32-bit bitmask
245 * and a power-of-two table size (so as to avoid the expensive
246 * "hash % prime" step).
247 *
248 * This algorithm uses 8n+6 instructions to hash a key of n bytes.
249 * The mix step is a left bitwise rotation by 4, so systems with a
250 * rotate instruction will save 2 instructions per loop.
251 *
252 * @param key The arbitrary-length key.
253 * @param len The length of the key, in bytes.
254 * @param seed An arbitrary seed value.
255 * @return A 32-bit hash value.
256 *
257 */
258 spif_uint32_t
spifhash_rotating(spif_uint8_t * key,spif_uint32_t len,spif_uint32_t seed)259 spifhash_rotating(spif_uint8_t *key, spif_uint32_t len, spif_uint32_t seed)
260 {
261 spif_uint32_t hash, i;
262
263 if (!seed) {
264 seed = BUILTIN_RANDOM_SEED;
265 }
266 for (hash = seed, i = 0; i < len; i++) {
267 hash = (hash << 4) ^ (hash >> 28) ^ key[i];
268 }
269 return (hash ^ (hash >> 10) ^ (hash >> 20));
270 }
271
272 /**
273 * The one-at-a-time hash.
274 *
275 * This is an implementation of the one-at-a-time hash. It is similar
276 * to spifhash_rotating(). It uses 9n+9 instructions to hash a key of n
277 * bytes. A full 32-bit key is produced. No funneling weaknesses are
278 * known.
279 *
280 * @param key The arbitrary-length key.
281 * @param len The length of the key, in bytes.
282 * @param seed An arbitrary seed value.
283 * @return A 32-bit hash value.
284 *
285 */
286 spif_uint32_t
spifhash_one_at_a_time(spif_uint8_t * key,spif_uint32_t len,spif_uint32_t seed)287 spifhash_one_at_a_time(spif_uint8_t *key, spif_uint32_t len, spif_uint32_t seed)
288 {
289 spif_uint32_t hash, i;
290
291 if (!seed) {
292 seed = BUILTIN_RANDOM_SEED;
293 }
294 for (hash = seed, i = 0; i < len; i++) {
295 hash += key[i];
296 hash += (hash << 10);
297 hash ^= (hash >> 6);
298 }
299 hash += (hash << 3);
300 hash ^= (hash >> 11);
301 hash += (hash << 15);
302 return hash;
303 }
304
305 /**
306 * The FNV hash.
307 *
308 * This is the Fowler/Noll/Vo (FNV) hash. This code is a modified
309 * version of that which appears at
310 * http://www.isthe.com/chongo/tech/comp/fnv/
311 *
312 * @param key The arbitrary-length key.
313 * @param len The length of the key, in bytes.
314 * @param seed An arbitrary seed value.
315 * @return A 32-bit hash value.
316 *
317 */
318 spif_uint32_t
spifhash_fnv(spif_uint8_t * key,spif_uint32_t len,spif_uint32_t seed)319 spifhash_fnv(spif_uint8_t *key, spif_uint32_t len, spif_uint32_t seed)
320 {
321 spif_uint8_t *key_end = key + len;
322 spif_uint32_t hash;
323
324 if (!seed) {
325 seed = SPIF_CAST(uint32) 0x811c9dc5; /* FNV-1a 32-bit init. */
326 }
327 for (hash = seed; key < key_end; key++) {
328 hash ^= SPIF_CAST(uint32) (*key);
329
330 #ifdef __GNUC__
331 hash += (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
332 #else
333 hash *= SPIF_CAST(uint32) 0x01000193; /* 32-bit FNV-1 prime. */
334 #endif
335 }
336
337 return hash;
338 }
339