]>
Commit | Line | Data |
---|---|---|
36923392 WD |
1 | /* |
2 | * Routines to provide a memory-efficient hashtable. | |
3 | * | |
ed4b3448 | 4 | * Copyright (C) 2007-2022 Wayne Davison |
36923392 WD |
5 | * |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 3 of the License, or | |
9 | * (at your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License along | |
17 | * with this program; if not, visit the http://fsf.org website. | |
18 | */ | |
19 | ||
20 | #include "rsync.h" | |
21 | ||
22 | #define HASH_LOAD_LIMIT(size) ((size)*3/4) | |
23 | ||
24 | struct hashtable *hashtable_create(int size, int key64) | |
25 | { | |
b3347e2a | 26 | int req = size; |
36923392 | 27 | struct hashtable *tbl; |
d6e6333a | 28 | int node_size = key64 ? sizeof (struct ht_int64_node) |
36923392 WD |
29 | : sizeof (struct ht_int32_node); |
30 | ||
31 | /* Pick a power of 2 that can hold the requested size. */ | |
32 | if (size & (size-1) || size < 16) { | |
36923392 WD |
33 | size = 16; |
34 | while (size < req) | |
35 | size *= 2; | |
36 | } | |
37 | ||
11eb67ee WD |
38 | tbl = new(struct hashtable); |
39 | tbl->nodes = new_array0(char, size * node_size); | |
36923392 WD |
40 | tbl->size = size; |
41 | tbl->entries = 0; | |
42 | tbl->node_size = node_size; | |
60c25caa | 43 | tbl->key64 = key64 ? 1 : 0; |
36923392 | 44 | |
b3347e2a WD |
45 | if (DEBUG_GTE(HASH, 1)) { |
46 | char buf[32]; | |
47 | if (req != size) | |
48 | snprintf(buf, sizeof buf, "req: %d, ", req); | |
49 | else | |
50 | *buf = '\0'; | |
51 | rprintf(FINFO, "[%s] created hashtable %lx (%ssize: %d, keys: %d-bit)\n", | |
52 | who_am_i(), (long)tbl, buf, size, key64 ? 64 : 32); | |
53 | } | |
54 | ||
36923392 WD |
55 | return tbl; |
56 | } | |
57 | ||
58 | void hashtable_destroy(struct hashtable *tbl) | |
59 | { | |
b3347e2a WD |
60 | if (DEBUG_GTE(HASH, 1)) { |
61 | rprintf(FINFO, "[%s] destroyed hashtable %lx (size: %d, keys: %d-bit)\n", | |
62 | who_am_i(), (long)tbl, tbl->size, tbl->key64 ? 64 : 32); | |
63 | } | |
36923392 WD |
64 | free(tbl->nodes); |
65 | free(tbl); | |
66 | } | |
67 | ||
f8005578 WD |
68 | /* Returns the node that holds the indicated key if it exists. When it does not |
69 | * exist, it returns either NULL (when data_when_new is NULL), or it returns a | |
70 | * new node with its node->data set to the indicated value. | |
71 | * | |
72 | * If your code doesn't know the data value for a new node in advance (usually | |
73 | * because it doesn't know if a node is new or not) you should pass in a unique | |
74 | * (non-0) value that you can use to check if the returned node is new. You can | |
75 | * then overwrite the data with any value you want (even 0) since it only needs | |
76 | * to be different than whatever data_when_new value you use later on. | |
77 | * | |
78 | * This return is a void* just because it might be pointing at a ht_int32_node | |
79 | * or a ht_int64_node, and that makes the caller's assignment a little easier. */ | |
80 | void *hashtable_find(struct hashtable *tbl, int64 key, void *data_when_new) | |
36923392 | 81 | { |
d6e6333a | 82 | int key64 = tbl->key64; |
36923392 WD |
83 | struct ht_int32_node *node; |
84 | uint32 ndx; | |
85 | ||
60c25caa WD |
86 | if (key64 ? key == 0 : (int32)key == 0) { |
87 | rprintf(FERROR, "Internal hashtable error: illegal key supplied!\n"); | |
88 | exit_cleanup(RERR_MESSAGEIO); | |
89 | } | |
90 | ||
f8005578 | 91 | if (data_when_new && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) { |
36923392 WD |
92 | void *old_nodes = tbl->nodes; |
93 | int size = tbl->size * 2; | |
94 | int i; | |
95 | ||
11eb67ee | 96 | tbl->nodes = new_array0(char, size * tbl->node_size); |
36923392 WD |
97 | tbl->size = size; |
98 | tbl->entries = 0; | |
99 | ||
b3347e2a WD |
100 | if (DEBUG_GTE(HASH, 1)) { |
101 | rprintf(FINFO, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n", | |
102 | who_am_i(), (long)tbl, size, key64 ? 64 : 32); | |
103 | } | |
104 | ||
36923392 WD |
105 | for (i = size / 2; i-- > 0; ) { |
106 | struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i); | |
107 | int64 move_key = HT_KEY(move_node, key64); | |
108 | if (move_key == 0) | |
109 | continue; | |
f8005578 WD |
110 | if (move_node->data) |
111 | hashtable_find(tbl, move_key, move_node->data); | |
112 | else { | |
113 | node = hashtable_find(tbl, move_key, ""); | |
114 | node->data = 0; | |
115 | } | |
36923392 WD |
116 | } |
117 | ||
118 | free(old_nodes); | |
119 | } | |
120 | ||
121 | if (!key64) { | |
122 | /* Based on Jenkins One-at-a-time hash. */ | |
123 | uchar buf[4], *keyp = buf; | |
124 | int i; | |
125 | ||
df6350a8 | 126 | SIVALu(buf, 0, key); |
36923392 WD |
127 | for (ndx = 0, i = 0; i < 4; i++) { |
128 | ndx += keyp[i]; | |
129 | ndx += (ndx << 10); | |
130 | ndx ^= (ndx >> 6); | |
131 | } | |
132 | ndx += (ndx << 3); | |
133 | ndx ^= (ndx >> 11); | |
134 | ndx += (ndx << 15); | |
135 | } else { | |
136 | /* Based on Jenkins hashword() from lookup3.c. */ | |
137 | uint32 a, b, c; | |
138 | ||
139 | /* Set up the internal state */ | |
140 | a = b = c = 0xdeadbeef + (8 << 2); | |
141 | ||
142 | #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k)))) | |
4ecf3e06 | 143 | #if SIZEOF_INT64 >= 8 |
36923392 | 144 | b += (uint32)(key >> 32); |
4ecf3e06 | 145 | #endif |
36923392 WD |
146 | a += (uint32)key; |
147 | c ^= b; c -= rot(b, 14); | |
148 | a ^= c; a -= rot(c, 11); | |
149 | b ^= a; b -= rot(a, 25); | |
150 | c ^= b; c -= rot(b, 16); | |
151 | a ^= c; a -= rot(c, 4); | |
152 | b ^= a; b -= rot(a, 14); | |
153 | c ^= b; c -= rot(b, 24); | |
154 | #undef rot | |
155 | ndx = c; | |
156 | } | |
157 | ||
158 | /* If it already exists, return the node. If we're not | |
159 | * allocating, return NULL if the key is not found. */ | |
160 | while (1) { | |
161 | int64 nkey; | |
162 | ||
163 | ndx &= tbl->size - 1; | |
164 | node = HT_NODE(tbl, tbl->nodes, ndx); | |
165 | nkey = HT_KEY(node, key64); | |
166 | ||
167 | if (nkey == key) | |
168 | return node; | |
169 | if (nkey == 0) { | |
f8005578 | 170 | if (!data_when_new) |
36923392 WD |
171 | return NULL; |
172 | break; | |
173 | } | |
174 | ndx++; | |
175 | } | |
176 | ||
177 | /* Take over this empty spot and then return the node. */ | |
178 | if (key64) | |
179 | ((struct ht_int64_node*)node)->key = key; | |
180 | else | |
aad635f7 | 181 | node->key = (int32)key; |
f8005578 | 182 | node->data = data_when_new; |
36923392 WD |
183 | tbl->entries++; |
184 | return node; | |
185 | } | |
cc29b94d SM |
186 | |
187 | #ifndef WORDS_BIGENDIAN | |
188 | # define HASH_LITTLE_ENDIAN 1 | |
189 | # define HASH_BIG_ENDIAN 0 | |
190 | #else | |
191 | # define HASH_LITTLE_ENDIAN 0 | |
192 | # define HASH_BIG_ENDIAN 1 | |
193 | #endif | |
194 | ||
195 | /* | |
196 | ------------------------------------------------------------------------------- | |
197 | lookup3.c, by Bob Jenkins, May 2006, Public Domain. | |
198 | ||
199 | These are functions for producing 32-bit hashes for hash table lookup. | |
200 | hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() | |
201 | are externally useful functions. Routines to test the hash are included | |
202 | if SELF_TEST is defined. You can use this free for any purpose. It's in | |
203 | the public domain. It has no warranty. | |
204 | ||
205 | You probably want to use hashlittle(). hashlittle() and hashbig() | |
206 | hash byte arrays. hashlittle() is is faster than hashbig() on | |
207 | little-endian machines. Intel and AMD are little-endian machines. | |
208 | On second thought, you probably want hashlittle2(), which is identical to | |
209 | hashlittle() except it returns two 32-bit hashes for the price of one. | |
210 | You could implement hashbig2() if you wanted but I haven't bothered here. | |
211 | ||
212 | If you want to find a hash of, say, exactly 7 integers, do | |
213 | a = i1; b = i2; c = i3; | |
214 | mix(a,b,c); | |
215 | a += i4; b += i5; c += i6; | |
216 | mix(a,b,c); | |
217 | a += i7; | |
218 | final(a,b,c); | |
219 | then use c as the hash value. If you have a variable length array of | |
220 | 4-byte integers to hash, use hash_word(). If you have a byte array (like | |
221 | a character string), use hashlittle(). If you have several byte arrays, or | |
222 | a mix of things, see the comments above hashlittle(). | |
223 | ||
224 | Why is this so big? I read 12 bytes at a time into 3 4-byte integers, | |
225 | then mix those integers. This is fast (you can do a lot more thorough | |
226 | mixing with 12*3 instructions on 3 integers than you can with 3 instructions | |
227 | on 1 byte), but shoehorning those bytes into integers efficiently is messy. | |
228 | */ | |
229 | ||
230 | #define hashsize(n) ((uint32_t)1<<(n)) | |
231 | #define hashmask(n) (hashsize(n)-1) | |
232 | #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) | |
233 | ||
234 | /* | |
235 | ------------------------------------------------------------------------------- | |
236 | mix -- mix 3 32-bit values reversibly. | |
237 | ||
238 | This is reversible, so any information in (a,b,c) before mix() is | |
239 | still in (a,b,c) after mix(). | |
240 | ||
241 | If four pairs of (a,b,c) inputs are run through mix(), or through | |
242 | mix() in reverse, there are at least 32 bits of the output that | |
243 | are sometimes the same for one pair and different for another pair. | |
244 | This was tested for: | |
245 | * pairs that differed by one bit, by two bits, in any combination | |
246 | of top bits of (a,b,c), or in any combination of bottom bits of | |
247 | (a,b,c). | |
248 | * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | |
249 | the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | |
250 | is commonly produced by subtraction) look like a single 1-bit | |
251 | difference. | |
252 | * the base values were pseudorandom, all zero but one bit set, or | |
253 | all zero plus a counter that starts at zero. | |
254 | ||
255 | Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that | |
256 | satisfy this are | |
257 | 4 6 8 16 19 4 | |
258 | 9 15 3 18 27 15 | |
259 | 14 9 3 7 17 3 | |
260 | Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing | |
261 | for "differ" defined as + with a one-bit base and a two-bit delta. I | |
262 | used http://burtleburtle.net/bob/hash/avalanche.html to choose | |
263 | the operations, constants, and arrangements of the variables. | |
264 | ||
265 | This does not achieve avalanche. There are input bits of (a,b,c) | |
266 | that fail to affect some output bits of (a,b,c), especially of a. The | |
267 | most thoroughly mixed value is c, but it doesn't really even achieve | |
268 | avalanche in c. | |
269 | ||
270 | This allows some parallelism. Read-after-writes are good at doubling | |
271 | the number of bits affected, so the goal of mixing pulls in the opposite | |
272 | direction as the goal of parallelism. I did what I could. Rotates | |
273 | seem to cost as much as shifts on every machine I could lay my hands | |
274 | on, and rotates are much kinder to the top and bottom bits, so I used | |
275 | rotates. | |
276 | ------------------------------------------------------------------------------- | |
277 | */ | |
278 | #define mix(a,b,c) \ | |
279 | { \ | |
280 | a -= c; a ^= rot(c, 4); c += b; \ | |
281 | b -= a; b ^= rot(a, 6); a += c; \ | |
282 | c -= b; c ^= rot(b, 8); b += a; \ | |
283 | a -= c; a ^= rot(c,16); c += b; \ | |
284 | b -= a; b ^= rot(a,19); a += c; \ | |
285 | c -= b; c ^= rot(b, 4); b += a; \ | |
286 | } | |
287 | ||
288 | /* | |
289 | ------------------------------------------------------------------------------- | |
290 | final -- final mixing of 3 32-bit values (a,b,c) into c | |
291 | ||
292 | Pairs of (a,b,c) values differing in only a few bits will usually | |
293 | produce values of c that look totally different. This was tested for | |
294 | * pairs that differed by one bit, by two bits, in any combination | |
295 | of top bits of (a,b,c), or in any combination of bottom bits of | |
296 | (a,b,c). | |
297 | * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | |
298 | the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | |
299 | is commonly produced by subtraction) look like a single 1-bit | |
300 | difference. | |
301 | * the base values were pseudorandom, all zero but one bit set, or | |
302 | all zero plus a counter that starts at zero. | |
303 | ||
304 | These constants passed: | |
305 | 14 11 25 16 4 14 24 | |
306 | 12 14 25 16 4 14 24 | |
307 | and these came close: | |
308 | 4 8 15 26 3 22 24 | |
309 | 10 8 15 26 3 22 24 | |
310 | 11 8 15 26 3 22 24 | |
311 | ------------------------------------------------------------------------------- | |
312 | */ | |
313 | #define final(a,b,c) \ | |
314 | { \ | |
315 | c ^= b; c -= rot(b,14); \ | |
316 | a ^= c; a -= rot(c,11); \ | |
317 | b ^= a; b -= rot(a,25); \ | |
318 | c ^= b; c -= rot(b,16); \ | |
319 | a ^= c; a -= rot(c,4); \ | |
320 | b ^= a; b -= rot(a,14); \ | |
321 | c ^= b; c -= rot(b,24); \ | |
322 | } | |
323 | ||
324 | ||
325 | /* | |
326 | ------------------------------------------------------------------------------- | |
327 | hashlittle() -- hash a variable-length key into a 32-bit value | |
328 | k : the key (the unaligned variable-length array of bytes) | |
329 | length : the length of the key, counting by bytes | |
330 | val2 : IN: can be any 4-byte value OUT: second 32 bit hash. | |
331 | Returns a 32-bit value. Every bit of the key affects every bit of | |
332 | the return value. Two keys differing by one or two bits will have | |
333 | totally different hash values. Note that the return value is better | |
334 | mixed than val2, so use that first. | |
335 | ||
336 | The best hash table sizes are powers of 2. There is no need to do | |
337 | mod a prime (mod is sooo slow!). If you need less than 32 bits, | |
338 | use a bitmask. For example, if you need only 10 bits, do | |
339 | h = (h & hashmask(10)); | |
340 | In which case, the hash table should have hashsize(10) elements. | |
341 | ||
342 | If you are hashing n strings (uint8_t **)k, do it like this: | |
343 | for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); | |
344 | ||
345 | By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this | |
346 | code any way you wish, private, educational, or commercial. It's free. | |
347 | ||
348 | Use for hash table lookup, or anything where one collision in 2^^32 is | |
349 | acceptable. Do NOT use for cryptographic purposes. | |
350 | ------------------------------------------------------------------------------- | |
351 | */ | |
352 | ||
b012cde1 | 353 | #define NON_ZERO_32(x) ((x) ? (x) : (uint32_t)1) |
f3f5d842 | 354 | #define NON_ZERO_64(x, y) ((x) || (y) ? (y) | (int64)(x) << 32 | (y) : (int64)1) |
b012cde1 | 355 | |
cc29b94d SM |
356 | uint32_t hashlittle(const void *key, size_t length) |
357 | { | |
358 | uint32_t a,b,c; /* internal state */ | |
359 | union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ | |
360 | ||
361 | /* Set up the internal state */ | |
362 | a = b = c = 0xdeadbeef + ((uint32_t)length); | |
363 | ||
364 | u.ptr = key; | |
365 | if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { | |
366 | const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ | |
367 | const uint8_t *k8; | |
368 | ||
369 | /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ | |
370 | while (length > 12) | |
371 | { | |
372 | a += k[0]; | |
373 | b += k[1]; | |
374 | c += k[2]; | |
375 | mix(a,b,c); | |
376 | length -= 12; | |
377 | k += 3; | |
378 | } | |
379 | ||
380 | /*----------------------------- handle the last (probably partial) block */ | |
381 | k8 = (const uint8_t *)k; | |
382 | switch(length) | |
383 | { | |
384 | case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |
385 | case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ | |
386 | case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ | |
387 | case 9 : c+=k8[8]; /* fall through */ | |
388 | case 8 : b+=k[1]; a+=k[0]; break; | |
389 | case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ | |
390 | case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ | |
391 | case 5 : b+=k8[4]; /* fall through */ | |
392 | case 4 : a+=k[0]; break; | |
393 | case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ | |
394 | case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ | |
395 | case 1 : a+=k8[0]; break; | |
b012cde1 | 396 | case 0 : return NON_ZERO_32(c); |
cc29b94d SM |
397 | } |
398 | } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { | |
399 | const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ | |
400 | const uint8_t *k8; | |
401 | ||
402 | /*--------------- all but last block: aligned reads and different mixing */ | |
403 | while (length > 12) | |
404 | { | |
405 | a += k[0] + (((uint32_t)k[1])<<16); | |
406 | b += k[2] + (((uint32_t)k[3])<<16); | |
407 | c += k[4] + (((uint32_t)k[5])<<16); | |
408 | mix(a,b,c); | |
409 | length -= 12; | |
410 | k += 6; | |
411 | } | |
412 | ||
413 | /*----------------------------- handle the last (probably partial) block */ | |
414 | k8 = (const uint8_t *)k; | |
415 | switch(length) | |
416 | { | |
417 | case 12: c+=k[4]+(((uint32_t)k[5])<<16); | |
418 | b+=k[2]+(((uint32_t)k[3])<<16); | |
419 | a+=k[0]+(((uint32_t)k[1])<<16); | |
420 | break; | |
421 | case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ | |
422 | case 10: c+=k[4]; | |
423 | b+=k[2]+(((uint32_t)k[3])<<16); | |
424 | a+=k[0]+(((uint32_t)k[1])<<16); | |
425 | break; | |
426 | case 9 : c+=k8[8]; /* fall through */ | |
427 | case 8 : b+=k[2]+(((uint32_t)k[3])<<16); | |
428 | a+=k[0]+(((uint32_t)k[1])<<16); | |
429 | break; | |
430 | case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ | |
431 | case 6 : b+=k[2]; | |
432 | a+=k[0]+(((uint32_t)k[1])<<16); | |
433 | break; | |
434 | case 5 : b+=k8[4]; /* fall through */ | |
435 | case 4 : a+=k[0]+(((uint32_t)k[1])<<16); | |
436 | break; | |
437 | case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ | |
438 | case 2 : a+=k[0]; | |
439 | break; | |
440 | case 1 : a+=k8[0]; | |
441 | break; | |
b012cde1 | 442 | case 0 : return NON_ZERO_32(c); /* zero length requires no mixing */ |
cc29b94d SM |
443 | } |
444 | ||
445 | } else { /* need to read the key one byte at a time */ | |
446 | const uint8_t *k = (const uint8_t *)key; | |
447 | ||
448 | /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ | |
449 | while (length > 12) | |
450 | { | |
451 | a += k[0]; | |
452 | a += ((uint32_t)k[1])<<8; | |
453 | a += ((uint32_t)k[2])<<16; | |
454 | a += ((uint32_t)k[3])<<24; | |
455 | b += k[4]; | |
456 | b += ((uint32_t)k[5])<<8; | |
457 | b += ((uint32_t)k[6])<<16; | |
458 | b += ((uint32_t)k[7])<<24; | |
459 | c += k[8]; | |
460 | c += ((uint32_t)k[9])<<8; | |
461 | c += ((uint32_t)k[10])<<16; | |
462 | c += ((uint32_t)k[11])<<24; | |
463 | mix(a,b,c); | |
464 | length -= 12; | |
465 | k += 12; | |
466 | } | |
467 | ||
468 | /*-------------------------------- last block: affect all 32 bits of (c) */ | |
469 | switch(length) /* all the case statements fall through */ | |
470 | { | |
471 | case 12: c+=((uint32_t)k[11])<<24; | |
ad17b218 | 472 | /* FALLTHROUGH */ |
cc29b94d | 473 | case 11: c+=((uint32_t)k[10])<<16; |
ad17b218 | 474 | /* FALLTHROUGH */ |
cc29b94d | 475 | case 10: c+=((uint32_t)k[9])<<8; |
ad17b218 | 476 | /* FALLTHROUGH */ |
cc29b94d | 477 | case 9 : c+=k[8]; |
ad17b218 | 478 | /* FALLTHROUGH */ |
cc29b94d | 479 | case 8 : b+=((uint32_t)k[7])<<24; |
ad17b218 | 480 | /* FALLTHROUGH */ |
cc29b94d | 481 | case 7 : b+=((uint32_t)k[6])<<16; |
ad17b218 | 482 | /* FALLTHROUGH */ |
cc29b94d | 483 | case 6 : b+=((uint32_t)k[5])<<8; |
ad17b218 | 484 | /* FALLTHROUGH */ |
cc29b94d | 485 | case 5 : b+=k[4]; |
ad17b218 | 486 | /* FALLTHROUGH */ |
cc29b94d | 487 | case 4 : a+=((uint32_t)k[3])<<24; |
ad17b218 | 488 | /* FALLTHROUGH */ |
cc29b94d | 489 | case 3 : a+=((uint32_t)k[2])<<16; |
ad17b218 | 490 | /* FALLTHROUGH */ |
cc29b94d | 491 | case 2 : a+=((uint32_t)k[1])<<8; |
ad17b218 | 492 | /* FALLTHROUGH */ |
cc29b94d SM |
493 | case 1 : a+=k[0]; |
494 | break; | |
b012cde1 | 495 | case 0 : return NON_ZERO_32(c); |
cc29b94d SM |
496 | } |
497 | } | |
498 | ||
499 | final(a,b,c); | |
b012cde1 | 500 | return NON_ZERO_32(c); |
cc29b94d | 501 | } |
b012cde1 WD |
502 | |
503 | #if SIZEOF_INT64 >= 8 | |
504 | /* | |
505 | * hashlittle2: return 2 32-bit hash values joined into an int64. | |
506 | * | |
507 | * This is identical to hashlittle(), except it returns two 32-bit hash | |
508 | * values instead of just one. This is good enough for hash table | |
509 | * lookup with 2^^64 buckets, or if you want a second hash if you're not | |
510 | * happy with the first, or if you want a probably-unique 64-bit ID for | |
511 | * the key. *pc is better mixed than *pb, so use *pc first. If you want | |
512 | * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". | |
513 | */ | |
514 | int64 hashlittle2(const void *key, size_t length) | |
515 | { | |
516 | uint32_t a,b,c; /* internal state */ | |
517 | union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ | |
518 | ||
519 | /* Set up the internal state */ | |
520 | a = b = c = 0xdeadbeef + ((uint32_t)length); | |
521 | ||
522 | u.ptr = key; | |
523 | if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { | |
524 | const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ | |
525 | const uint8_t *k8; | |
526 | ||
527 | /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ | |
528 | while (length > 12) | |
529 | { | |
530 | a += k[0]; | |
531 | b += k[1]; | |
532 | c += k[2]; | |
533 | mix(a,b,c); | |
534 | length -= 12; | |
535 | k += 3; | |
536 | } | |
537 | ||
538 | /*----------------------------- handle the last (probably partial) block */ | |
539 | k8 = (const uint8_t *)k; | |
540 | switch(length) | |
541 | { | |
542 | case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |
543 | case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ | |
544 | case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ | |
545 | case 9 : c+=k8[8]; /* fall through */ | |
546 | case 8 : b+=k[1]; a+=k[0]; break; | |
547 | case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ | |
548 | case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ | |
549 | case 5 : b+=k8[4]; /* fall through */ | |
550 | case 4 : a+=k[0]; break; | |
551 | case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ | |
552 | case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ | |
553 | case 1 : a+=k8[0]; break; | |
554 | case 0 : return NON_ZERO_64(b, c); | |
555 | } | |
556 | } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { | |
557 | const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ | |
558 | const uint8_t *k8; | |
559 | ||
560 | /*--------------- all but last block: aligned reads and different mixing */ | |
561 | while (length > 12) | |
562 | { | |
563 | a += k[0] + (((uint32_t)k[1])<<16); | |
564 | b += k[2] + (((uint32_t)k[3])<<16); | |
565 | c += k[4] + (((uint32_t)k[5])<<16); | |
566 | mix(a,b,c); | |
567 | length -= 12; | |
568 | k += 6; | |
569 | } | |
570 | ||
571 | /*----------------------------- handle the last (probably partial) block */ | |
572 | k8 = (const uint8_t *)k; | |
573 | switch(length) | |
574 | { | |
575 | case 12: c+=k[4]+(((uint32_t)k[5])<<16); | |
576 | b+=k[2]+(((uint32_t)k[3])<<16); | |
577 | a+=k[0]+(((uint32_t)k[1])<<16); | |
578 | break; | |
579 | case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ | |
580 | case 10: c+=k[4]; | |
581 | b+=k[2]+(((uint32_t)k[3])<<16); | |
582 | a+=k[0]+(((uint32_t)k[1])<<16); | |
583 | break; | |
584 | case 9 : c+=k8[8]; /* fall through */ | |
585 | case 8 : b+=k[2]+(((uint32_t)k[3])<<16); | |
586 | a+=k[0]+(((uint32_t)k[1])<<16); | |
587 | break; | |
588 | case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ | |
589 | case 6 : b+=k[2]; | |
590 | a+=k[0]+(((uint32_t)k[1])<<16); | |
591 | break; | |
592 | case 5 : b+=k8[4]; /* fall through */ | |
593 | case 4 : a+=k[0]+(((uint32_t)k[1])<<16); | |
594 | break; | |
595 | case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ | |
596 | case 2 : a+=k[0]; | |
597 | break; | |
598 | case 1 : a+=k8[0]; | |
599 | break; | |
600 | case 0 : return NON_ZERO_64(b, c); /* zero length strings require no mixing */ | |
601 | } | |
602 | ||
603 | } else { /* need to read the key one byte at a time */ | |
604 | const uint8_t *k = (const uint8_t *)key; | |
605 | ||
606 | /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ | |
607 | while (length > 12) | |
608 | { | |
609 | a += k[0]; | |
610 | a += ((uint32_t)k[1])<<8; | |
611 | a += ((uint32_t)k[2])<<16; | |
612 | a += ((uint32_t)k[3])<<24; | |
613 | b += k[4]; | |
614 | b += ((uint32_t)k[5])<<8; | |
615 | b += ((uint32_t)k[6])<<16; | |
616 | b += ((uint32_t)k[7])<<24; | |
617 | c += k[8]; | |
618 | c += ((uint32_t)k[9])<<8; | |
619 | c += ((uint32_t)k[10])<<16; | |
620 | c += ((uint32_t)k[11])<<24; | |
621 | mix(a,b,c); | |
622 | length -= 12; | |
623 | k += 12; | |
624 | } | |
625 | ||
626 | /*-------------------------------- last block: affect all 32 bits of (c) */ | |
627 | switch(length) /* all the case statements fall through */ | |
628 | { | |
629 | case 12: c+=((uint32_t)k[11])<<24; | |
630 | /* FALLTHROUGH */ | |
631 | case 11: c+=((uint32_t)k[10])<<16; | |
632 | /* FALLTHROUGH */ | |
633 | case 10: c+=((uint32_t)k[9])<<8; | |
634 | /* FALLTHROUGH */ | |
635 | case 9 : c+=k[8]; | |
636 | /* FALLTHROUGH */ | |
637 | case 8 : b+=((uint32_t)k[7])<<24; | |
638 | /* FALLTHROUGH */ | |
639 | case 7 : b+=((uint32_t)k[6])<<16; | |
640 | /* FALLTHROUGH */ | |
641 | case 6 : b+=((uint32_t)k[5])<<8; | |
642 | /* FALLTHROUGH */ | |
643 | case 5 : b+=k[4]; | |
644 | /* FALLTHROUGH */ | |
645 | case 4 : a+=((uint32_t)k[3])<<24; | |
646 | /* FALLTHROUGH */ | |
647 | case 3 : a+=((uint32_t)k[2])<<16; | |
648 | /* FALLTHROUGH */ | |
649 | case 2 : a+=((uint32_t)k[1])<<8; | |
650 | /* FALLTHROUGH */ | |
651 | case 1 : a+=k[0]; | |
652 | break; | |
653 | case 0 : return NON_ZERO_64(b, c); | |
654 | } | |
655 | } | |
656 | ||
657 | final(a,b,c); | |
658 | return NON_ZERO_64(b, c); | |
659 | } | |
660 | #else | |
661 | #define hashlittle2(key, len) hashlittle(key, len) | |
662 | #endif |