hashtable.c

   1 /*
   2  * Routines to provide a memory-efficient hashtable.
   3  *
   4  * Copyright (C) 2007-2022 Wayne Davison
   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 {
  26         int req = size;
  27         struct hashtable *tbl;
  28         int node_size = key64 ? sizeof (struct ht_int64_node)
  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) {
  33                 size = 16;
  34                 while (size < req)
  35                         size *= 2;
  36         }
  37
  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;
  44
  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
  55         return tbl;
  56 }
  57
  58 void hashtable_destroy(struct hashtable *tbl)
  59 {
  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         }
  64         free(tbl->nodes);
  65         free(tbl);
  66 }
  67
  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)
  81 {
  82         int key64 = tbl->key64;
  83         struct ht_int32_node *node;
  84         uint32 ndx;
  85
  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
  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;
  95
  96                 tbl->nodes = new_array0(char, size * tbl->node_size);
  97                 tbl->size = size;
  98                 tbl->entries = 0;
  99
 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
 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;
 115                         }
 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
 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);
 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))))
 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;
 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) {
 170                         if (!data_when_new)
 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
 181                 node->key = (int32)key;
 182         node->data = data_when_new;
 183         tbl->entries++;
 184         return node;
 185 }
 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
 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)
 355
 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;
 396     case 0 : return NON_ZERO_32(c);
 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;
 442     case 0 : return NON_ZERO_32(c);         /* zero length requires no mixing */
 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;
 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);
 496     }
 497   }
 498
 499   final(a,b,c);
 500   return NON_ZERO_32(c);
 501 }
 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