Call `OpenSSL_add_all_algorithms()` on older openssl versions.
[rsync.git] / hashtable.c
blob2cc4e55047004d0541a7889531daffae8f7c90ca
1 /*
2 * Routines to provide a memory-efficient hashtable.
4 * Copyright (C) 2007-2022 Wayne Davison
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.
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.
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.
20 #include "rsync.h"
22 #define HASH_LOAD_LIMIT(size) ((size)*3/4)
24 struct hashtable *hashtable_create(int size, int key64)
26 int req = size;
27 struct hashtable *tbl;
28 int node_size = key64 ? sizeof (struct ht_int64_node)
29 : sizeof (struct ht_int32_node);
31 /* Pick a power of 2 that can hold the requested size. */
32 if (size & (size-1) || size < 16) {
33 size = 16;
34 while (size < req)
35 size *= 2;
38 tbl = new(struct hashtable);
39 tbl->nodes = new_array0(char, size * node_size);
40 tbl->size = size;
41 tbl->entries = 0;
42 tbl->node_size = node_size;
43 tbl->key64 = key64 ? 1 : 0;
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);
55 return tbl;
58 void hashtable_destroy(struct hashtable *tbl)
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);
64 free(tbl->nodes);
65 free(tbl);
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.
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.
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)
82 int key64 = tbl->key64;
83 struct ht_int32_node *node;
84 uint32 ndx;
86 if (key64 ? key == 0 : (int32)key == 0) {
87 rprintf(FERROR, "Internal hashtable error: illegal key supplied!\n");
88 exit_cleanup(RERR_MESSAGEIO);
91 if (data_when_new && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) {
92 void *old_nodes = tbl->nodes;
93 int size = tbl->size * 2;
94 int i;
96 tbl->nodes = new_array0(char, size * tbl->node_size);
97 tbl->size = size;
98 tbl->entries = 0;
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);
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;
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;
118 free(old_nodes);
121 if (!key64) {
122 /* Based on Jenkins One-at-a-time hash. */
123 uchar buf[4], *keyp = buf;
124 int i;
126 SIVALu(buf, 0, key);
127 for (ndx = 0, i = 0; i < 4; i++) {
128 ndx += keyp[i];
129 ndx += (ndx << 10);
130 ndx ^= (ndx >> 6);
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;
139 /* Set up the internal state */
140 a = b = c = 0xdeadbeef + (8 << 2);
142 #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
143 #if SIZEOF_INT64 >= 8
144 b += (uint32)(key >> 32);
145 #endif
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;
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;
163 ndx &= tbl->size - 1;
164 node = HT_NODE(tbl, tbl->nodes, ndx);
165 nkey = HT_KEY(node, key64);
167 if (nkey == key)
168 return node;
169 if (nkey == 0) {
170 if (!data_when_new)
171 return NULL;
172 break;
174 ndx++;
177 /* Take over this empty spot and then return the node. */
178 if (key64)
179 ((struct ht_int64_node*)node)->key = key;
180 else
181 node->key = (int32)key;
182 node->data = data_when_new;
183 tbl->entries++;
184 return node;
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
196 -------------------------------------------------------------------------------
197 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
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.
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.
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().
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.
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))))
235 -------------------------------------------------------------------------------
236 mix -- mix 3 32-bit values reversibly.
238 This is reversible, so any information in (a,b,c) before mix() is
239 still in (a,b,c) after mix().
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.
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.
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.
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 -------------------------------------------------------------------------------
278 #define mix(a,b,c) \
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; \
289 -------------------------------------------------------------------------------
290 final -- final mixing of 3 32-bit values (a,b,c) into c
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.
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 -------------------------------------------------------------------------------
313 #define final(a,b,c) \
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); \
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.
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.
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);
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.
348 Use for hash table lookup, or anything where one collision in 2^^32 is
349 acceptable. Do NOT use for cryptographic purposes.
350 -------------------------------------------------------------------------------
353 #define NON_ZERO_32(x) ((x) ? (x) : (uint32_t)1)
354 #define NON_ZERO_64(x, y) ((x) || (y) ? (y) | (int64)(x) << 32 | (y) : (int64)1)
356 uint32_t hashlittle(const void *key, size_t length)
358 uint32_t a,b,c; /* internal state */
359 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
361 /* Set up the internal state */
362 a = b = c = 0xdeadbeef + ((uint32_t)length);
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;
369 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
370 while (length > 12)
372 a += k[0];
373 b += k[1];
374 c += k[2];
375 mix(a,b,c);
376 length -= 12;
377 k += 3;
380 /*----------------------------- handle the last (probably partial) block */
381 k8 = (const uint8_t *)k;
382 switch(length)
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;
396 case 0 : return NON_ZERO_32(c);
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;
402 /*--------------- all but last block: aligned reads and different mixing */
403 while (length > 12)
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;
413 /*----------------------------- handle the last (probably partial) block */
414 k8 = (const uint8_t *)k;
415 switch(length)
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;
442 case 0 : return NON_ZERO_32(c); /* zero length requires no mixing */
445 } else { /* need to read the key one byte at a time */
446 const uint8_t *k = (const uint8_t *)key;
448 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
449 while (length > 12)
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;
468 /*-------------------------------- last block: affect all 32 bits of (c) */
469 switch(length) /* all the case statements fall through */
471 case 12: c+=((uint32_t)k[11])<<24;
472 /* FALLTHROUGH */
473 case 11: c+=((uint32_t)k[10])<<16;
474 /* FALLTHROUGH */
475 case 10: c+=((uint32_t)k[9])<<8;
476 /* FALLTHROUGH */
477 case 9 : c+=k[8];
478 /* FALLTHROUGH */
479 case 8 : b+=((uint32_t)k[7])<<24;
480 /* FALLTHROUGH */
481 case 7 : b+=((uint32_t)k[6])<<16;
482 /* FALLTHROUGH */
483 case 6 : b+=((uint32_t)k[5])<<8;
484 /* FALLTHROUGH */
485 case 5 : b+=k[4];
486 /* FALLTHROUGH */
487 case 4 : a+=((uint32_t)k[3])<<24;
488 /* FALLTHROUGH */
489 case 3 : a+=((uint32_t)k[2])<<16;
490 /* FALLTHROUGH */
491 case 2 : a+=((uint32_t)k[1])<<8;
492 /* FALLTHROUGH */
493 case 1 : a+=k[0];
494 break;
495 case 0 : return NON_ZERO_32(c);
499 final(a,b,c);
500 return NON_ZERO_32(c);
503 #if SIZEOF_INT64 >= 8
505 * hashlittle2: return 2 32-bit hash values joined into an int64.
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)".
514 int64 hashlittle2(const void *key, size_t length)
516 uint32_t a,b,c; /* internal state */
517 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
519 /* Set up the internal state */
520 a = b = c = 0xdeadbeef + ((uint32_t)length);
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;
527 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
528 while (length > 12)
530 a += k[0];
531 b += k[1];
532 c += k[2];
533 mix(a,b,c);
534 length -= 12;
535 k += 3;
538 /*----------------------------- handle the last (probably partial) block */
539 k8 = (const uint8_t *)k;
540 switch(length)
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);
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;
560 /*--------------- all but last block: aligned reads and different mixing */
561 while (length > 12)
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;
571 /*----------------------------- handle the last (probably partial) block */
572 k8 = (const uint8_t *)k;
573 switch(length)
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 */
603 } else { /* need to read the key one byte at a time */
604 const uint8_t *k = (const uint8_t *)key;
606 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
607 while (length > 12)
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;
626 /*-------------------------------- last block: affect all 32 bits of (c) */
627 switch(length) /* all the case statements fall through */
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);
657 final(a,b,c);
658 return NON_ZERO_64(b, c);
660 #else
661 #define hashlittle2(key, len) hashlittle(key, len)
662 #endif