src/OpenFOAM/primitives/hashes/Hasher/Hasher.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright held by original author
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software; you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by the
  13     Free Software Foundation; either version 2 of the License, or (at your
  14     option) any later version.
  15
  16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with OpenFOAM; if not, write to the Free Software Foundation,
  23     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  24
  25 Description
  26     Hashing functions, mostly from Bob Jenkins
  27 \*---------------------------------------------------------------------------*/
  28
  29 #include "Hasher.H"
  30 #include "HasherInt.H"
  31
  32 #if defined (__GLIBC__)
  33 #  include <endian.h>
  34 #endif
  35
  36 // Left-rotate a 32-bit value and carry by nBits
  37 #define bitRotateLeft(x, nBits)  (((x) << (nBits)) | ((x) >> (32 - (nBits))))
  38
  39
  40 // ----------------------------------------------------------------------------
  41 // lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  42 //
  43 // These are functions for producing 32-bit hashes for hash table lookup.
  44 // hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  45 // are externally useful functions.  Routines to test the hash are included
  46 // if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  47 // the public domain.  It has no warranty.
  48 //
  49 // You probably want to use hashlittle().  hashlittle() and hashbig()
  50 // hash byte arrays.  hashlittle() is is faster than hashbig() on
  51 // little-endian machines.  Intel and AMD are little-endian machines.
  52 // On second thought, you probably want hashlittle2(), which is identical to
  53 // hashlittle() except it returns two 32-bit hashes for the price of one.
  54 // You could implement hashbig2() if you wanted but I haven't bothered here.
  55 //
  56 // If you want to find a hash of, say, exactly 7 integers, do
  57 //   a = i1;  b = i2;  c = i3;
  58 //   mix(a,b,c);
  59 //   a += i4; b += i5; c += i6;
  60 //   mix(a,b,c);
  61 //   a += i7;
  62 //   final(a,b,c);
  63 // then use c as the hash value.  If you have a variable length array of
  64 // 4-byte integers to hash, use hashword().  If you have a byte array (like
  65 // a character string), use hashlittle().  If you have several byte arrays, or
  66 // a mix of things, see the comments above hashlittle().
  67 //
  68 // Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
  69 // then mix those integers.  This is fast (you can do a lot more thorough
  70 // mixing with 12*3 instructions on 3 integers than you can with 3 instructions
  71 // on 1 byte), but shoehorning those bytes into integers efficiently is messy.
  72 // ----------------------------------------------------------------------------
  73
  74 // ----------------------------------------------------------------------------
  75 // mix -- mix 3 32-bit values reversibly.
  76 //
  77 // This is reversible, so any information in (a,b,c) before mix_hash() is
  78 // still in (a,b,c) after mix_hash().
  79 //
  80 // If four pairs of (a,b,c) inputs are run through mix_hash(), or through
  81 // mix_hash() in reverse, there are at least 32 bits of the output that
  82 // are sometimes the same for one pair and different for another pair.
  83 // This was tested for:
  84 // * pairs that differed by one bit, by two bits, in any combination
  85 //   of top bits of (a,b,c), or in any combination of bottom bits of
  86 //   (a,b,c).
  87 // * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  88 //   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  89 //   is commonly produced by subtraction) look like a single 1-bit
  90 //   difference.
  91 // * the base values were pseudorandom, all zero but one bit set, or
  92 //   all zero plus a counter that starts at zero.
  93 //
  94 // Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
  95 // satisfy this are
  96 //     4  6  8 16 19  4
  97 //     9 15  3 18 27 15
  98 //    14  9  3  7 17  3
  99 // Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 100 // for "differ" defined as + with a one-bit base and a two-bit delta.  I
 101 // used http://burtleburtle.net/bob/hash/avalanche.html to choose
 102 // the operations, constants, and arrangements of the variables.
 103 //
 104 // This does not achieve avalanche.  There are input bits of (a,b,c)
 105 // that fail to affect some output bits of (a,b,c), especially of a.  The
 106 // most thoroughly mixed value is c, but it doesn't really even achieve
 107 // avalanche in c.
 108 //
 109 // This allows some parallelism.  Read-after-writes are good at doubling
 110 // the number of bits affected, so the goal of mixing pulls in the opposite
 111 // direction as the goal of parallelism.  I did what I could.  Rotates
 112 // seem to cost as much as shifts on every machine I could lay my hands
 113 // on, and rotates are much kinder to the top and bottom bits, so I used
 114 // rotates.
 115 // ----------------------------------------------------------------------------
 116
 117 #define bitMixer(a, b, c)                                                     \
 118     {                                                                         \
 119         a -= c; a ^= bitRotateLeft(c, 4); c += b;                             \
 120         b -= a; b ^= bitRotateLeft(a, 6); a += c;                             \
 121         c -= b; c ^= bitRotateLeft(b, 8); b += a;                             \
 122         a -= c; a ^= bitRotateLeft(c,16); c += b;                             \
 123         b -= a; b ^= bitRotateLeft(a,19); a += c;                             \
 124         c -= b; c ^= bitRotateLeft(b, 4); b += a;                             \
 125     }
 126
 127
 128 // ----------------------------------------------------------------------------
 129 // final -- final mixing of 3 32-bit values (a,b,c) into c
 130 //
 131 // Pairs of (a,b,c) values differing in only a few bits will usually
 132 // produce values of c that look totally different.  This was tested for
 133 // * pairs that differed by one bit, by two bits, in any combination
 134 //   of top bits of (a,b,c), or in any combination of bottom bits of
 135 //   (a,b,c).
 136 // * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 137 //   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 138 //   is commonly produced by subtraction) look like a single 1-bit
 139 //   difference.
 140 // * the base values were pseudorandom, all zero but one bit set, or
 141 //   all zero plus a counter that starts at zero.
 142 //
 143 // These constants passed:
 144 //  14 11 25 16 4 14 24
 145 //  12 14 25 16 4 14 24
 146 // and these came close:
 147 //   4  8 15 26 3 22 24
 148 //  10  8 15 26 3 22 24
 149 //  11  8 15 26 3 22 24
 150 // ----------------------------------------------------------------------------
 151
 152 #define bitMixerFinal(a, b, c)                                                \
 153     {                                                                         \
 154         c ^= b; c -= bitRotateLeft(b, 14);                                    \
 155         a ^= c; a -= bitRotateLeft(c, 11);                                    \
 156         b ^= a; b -= bitRotateLeft(a, 25);                                    \
 157         c ^= b; c -= bitRotateLeft(b, 16);                                    \
 158         a ^= c; a -= bitRotateLeft(c, 4);                                     \
 159         b ^= a; b -= bitRotateLeft(a, 14);                                    \
 160         c ^= b; c -= bitRotateLeft(b, 24);                                    \
 161     }
 162
 163
 164 // * * * * * * * * * * * * * * Static Functions  * * * * * * * * * * * * * * //
 165
 166 // ----------------------------------------------------------------------------
 167 // hashlittle() -- hash a variable-length key into a 32-bit value
 168 //   k       : the key (the unaligned variable-length array of bytes)
 169 //   length  : the length of the key, counting by bytes
 170 //   initval : can be any 4-byte value
 171 // Returns a 32-bit value.  Every bit of the key affects every bit of
 172 // the return value.  Two keys differing by one or two bits will have
 173 // totally different hash values.
 174 //
 175 // The best hash table sizes are powers of 2.  There is no need to do
 176 // mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 177 // use a bitmask.  For example, if you need only 10 bits, do
 178 //   h = (h & hashmask(10));
 179 // In which case, the hash table should have hashsize(10) elements.
 180 //
 181 // If you are hashing n strings (uint8_t **)k, do it like this:
 182 //   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
 183 //
 184 // By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 185 // code any way you wish, private, educational, or commercial.  It's free.
 186 //
 187 // Use for hash table lookup, or anything where one collision in 2^^32 is
 188 // acceptable.  Do NOT use for cryptographic purposes.
 189 // ----------------------------------------------------------------------------
 190
 191 //- specialized little-endian code
 192 #if !defined (__BYTE_ORDER) || (__BYTE_ORDER == __LITTLE_ENDIAN)
 193 static unsigned jenkins_hashlittle
 194 (
 195     const void *key,
 196     size_t length,
 197     unsigned initval
 198 )
 199 {
 200     uint32_t a, b, c;
 201     union { const void *ptr; size_t i; } u; // to cast key to (size_t) happily
 202
 203     // Set up the internal state
 204     a = b = c = 0xdeadbeef + static_cast<uint32_t>(length) + initval;
 205
 206     u.ptr = key;
 207     if ((u.i & 0x3) == 0)
 208     {
 209         // 32-bit chunks
 210         const uint32_t *k = reinterpret_cast<const uint32_t*>(key);
 211
 212         // all but last block: aligned reads and affect 32 bits of (a,b,c)
 213         while (length > 12)
 214         {
 215             a += k[0];
 216             b += k[1];
 217             c += k[2];
 218             bitMixer(a,b,c);
 219             length -= 12;
 220             k += 3;
 221         }
 222
 223         // handle the last (probably partial) block byte-wise
 224         const uint8_t *k8 = reinterpret_cast<const uint8_t*>(k);
 225         switch (length)
 226         {
 227             case 12: c += k[2]; b += k[1]; a += k[0]; break;
 228             case 11: c += static_cast<uint32_t>(k8[10]) << 16; // fall through
 229             case 10: c += static_cast<uint32_t>(k8[9])  << 8;  // fall through
 230             case 9 : c += k8[8];                               // fall through
 231             case 8 : b += k[1]; a += k[0]; break;
 232             case 7 : b += static_cast<uint32_t>(k8[6]) << 16;  // fall through
 233             case 6 : b += static_cast<uint32_t>(k8[5]) << 8;   // fall through
 234             case 5 : b += k8[4];                               // fall through
 235             case 4 : a += k[0]; break;
 236             case 3 : a += static_cast<uint32_t>(k8[2]) << 16;  // fall through
 237             case 2 : a += static_cast<uint32_t>(k8[1]) << 8;   // fall through
 238             case 1 : a += k8[0]; break;
 239             case 0 : return c;  // zero-length requires no mixing
 240         }
 241     }
 242     else if ((u.i & 0x1) == 0)
 243     {
 244         // 16-bit chunks
 245         const uint16_t *k = reinterpret_cast<const uint16_t*>(key);
 246
 247         // all but last block: aligned reads and different mixing
 248         while (length > 12)
 249         {
 250             a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 251             b += k[2] + (static_cast<uint32_t>(k[3]) << 16);
 252             c += k[4] + (static_cast<uint32_t>(k[5]) << 16);
 253             bitMixer(a,b,c);
 254             length -= 12;
 255             k += 6;
 256         }
 257
 258         // handle the last (probably partial) block
 259         const uint8_t *k8 = reinterpret_cast<const uint8_t*>(k);
 260         switch (length)
 261         {
 262             case 12:
 263                 c += k[4] + (static_cast<uint32_t>(k[5]) << 16);
 264                 b += k[2] + (static_cast<uint32_t>(k[3]) << 16);
 265                 a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 266                 break;
 267             case 11:
 268                 c += static_cast<uint32_t>(k8[10]) << 16;
 269                 // fall through
 270             case 10:
 271                 c += k[4];
 272                 b += k[2] + (static_cast<uint32_t>(k[3]) << 16);
 273                 a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 274                 break;
 275             case 9 :
 276                 c += k8[8];
 277                 // fall through
 278             case 8 :
 279                 b += k[2] + (static_cast<uint32_t>(k[3]) << 16);
 280                 a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 281                 break;
 282             case 7 :
 283                 b += static_cast<uint32_t>(k8[6]) << 16;
 284                 // fall through
 285             case 6 :
 286                 b += k[2];
 287                 a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 288                 break;
 289             case 5 :
 290                 b += k8[4];
 291                 // fall through
 292             case 4 :
 293                 a += k[0] + (static_cast<uint32_t>(k[1]) << 16);
 294                 break;
 295             case 3 :
 296                 a += static_cast<uint32_t>(k8[2]) << 16;
 297                 // fall through
 298             case 2 :
 299                 a += k[0];
 300                 break;
 301             case 1 :
 302                 a += k8[0];
 303                 break;
 304             case 0 : return c;     // zero-length requires no mixing
 305         }
 306     }
 307     else
 308     {
 309         const uint8_t *k = reinterpret_cast<const uint8_t*>(key);
 310
 311         // all but the last block: affect some 32 bits of (a,b,c)
 312         while (length > 12)
 313         {
 314             a += k[0];
 315             a += static_cast<uint32_t>(k[1]) << 8;
 316             a += static_cast<uint32_t>(k[2]) << 16;
 317             a += static_cast<uint32_t>(k[3]) << 24;
 318             b += k[4];
 319             b += static_cast<uint32_t>(k[5]) << 8;
 320             b += static_cast<uint32_t>(k[6]) << 16;
 321             b += static_cast<uint32_t>(k[7]) << 24;
 322             c += k[8];
 323             c += static_cast<uint32_t>(k[9])  << 8;
 324             c += static_cast<uint32_t>(k[10]) << 16;
 325             c += static_cast<uint32_t>(k[11]) << 24;
 326
 327             bitMixer(a,b,c);
 328             length -= 12;
 329             k += 12;
 330         }
 331
 332         // last block: affect all 32 bits of (c)
 333         switch (length) // most case statements fall through
 334         {
 335             case 12: c += static_cast<uint32_t>(k[11]) << 24;
 336             case 11: c += static_cast<uint32_t>(k[10]) << 16;
 337             case 10: c += static_cast<uint32_t>(k[9]) << 8;
 338             case 9 : c += k[8];
 339
 340             case 8 : b += static_cast<uint32_t>(k[7]) << 24;
 341             case 7 : b += static_cast<uint32_t>(k[6]) << 16;
 342             case 6 : b += static_cast<uint32_t>(k[5]) << 8;
 343             case 5 : b += k[4];
 344
 345             case 4 : a += static_cast<uint32_t>(k[3]) << 24;
 346             case 3 : a += static_cast<uint32_t>(k[2]) << 16;
 347             case 2 : a += static_cast<uint32_t>(k[1]) << 8;
 348             case 1 : a += k[0];
 349                 break;
 350
 351             case 0 : return c;
 352         }
 353     }
 354
 355     bitMixerFinal(a,b,c);
 356     return c;
 357 }
 358 #endif
 359
 360
 361
 362
 363 // ----------------------------------------------------------------------------
 364 // hashbig():
 365 // This is the same as hashword() on big-endian machines.  It is different
 366 // from hashlittle() on all machines.  hashbig() takes advantage of
 367 // big-endian byte ordering.
 368 // ----------------------------------------------------------------------------
 369 // specialized big-endian code
 370 #if !defined (__BYTE_ORDER) || (__BYTE_ORDER == __BIG_ENDIAN)
 371 static unsigned jenkins_hashbig
 372 (
 373     const void *key,
 374     size_t length,
 375     unsigned initval
 376 )
 377 {
 378     uint32_t a, b, c;
 379     union { const void *ptr; size_t i; } u; // to cast key to (size_t) happily
 380
 381     // Set up the internal state
 382     a = b = c = 0xdeadbeef + static_cast<uint32_t>(length) + initval;
 383
 384     u.ptr = key;
 385     if ((u.i & 0x3) == 0)
 386     {
 387         // 32-bit chunks
 388         const uint32_t *k = reinterpret_cast<const uint32_t*>(key);
 389
 390         // all but last block: aligned reads and affect 32 bits of (a,b,c)
 391         while (length > 12)
 392         {
 393             a += k[0];
 394             b += k[1];
 395             c += k[2];
 396             bitMixer(a,b,c);
 397             length -= 12;
 398             k += 3;
 399         }
 400
 401         // handle the last (probably partial) block byte-wise
 402         const uint8_t *k8 = reinterpret_cast<const uint8_t*>(k);
 403
 404         switch (length) // most the case statements fall through
 405         {
 406             case 12: c += k[2]; b += k[1]; a += k[0]; break;
 407             case 11: c += static_cast<uint32_t>(k8[10]) << 8; // fall through
 408             case 10: c += static_cast<uint32_t>(k8[9]) << 16; // fall through
 409             case 9 : c += static_cast<uint32_t>(k8[8]) << 24; // fall through
 410             case 8 : b += k[1]; a += k[0]; break;
 411             case 7 : b += static_cast<uint32_t>(k8[6]) << 8;  // fall through
 412             case 6 : b += static_cast<uint32_t>(k8[5]) << 16; // fall through
 413             case 5 : b += static_cast<uint32_t>(k8[4]) << 24; // fall through
 414             case 4 : a += k[0]; break;
 415             case 3 : a += static_cast<uint32_t>(k8[2]) << 8;  // fall through
 416             case 2 : a += static_cast<uint32_t>(k8[1]) << 16; // fall through
 417             case 1 : a += static_cast<uint32_t>(k8[0]) << 24; break;
 418             case 0 : return c;
 419         }
 420     }
 421     else
 422     {
 423         // need to read the key one byte at a time
 424         const uint8_t *k = reinterpret_cast<const uint8_t*>(key);
 425
 426         // all but the last block: affect some 32 bits of (a,b,c)
 427         while (length > 12)
 428         {
 429             a += static_cast<uint32_t>(k[0]) << 24;
 430             a += static_cast<uint32_t>(k[1]) << 16;
 431             a += static_cast<uint32_t>(k[2]) << 8;
 432             a += static_cast<uint32_t>(k[3]);
 433             b += static_cast<uint32_t>(k[4]) << 24;
 434             b += static_cast<uint32_t>(k[5]) << 16;
 435             b += static_cast<uint32_t>(k[6]) << 8;
 436             b += static_cast<uint32_t>(k[7]);
 437             c += static_cast<uint32_t>(k[8]) << 24;
 438             c += static_cast<uint32_t>(k[9]) << 16;
 439             c += static_cast<uint32_t>(k[10]) << 8;
 440             c += static_cast<uint32_t>(k[11]);
 441
 442             bitMixer(a,b,c);
 443             length -= 12;
 444             k += 12;
 445         }
 446
 447         // last block: affect all 32 bits of (c)
 448         switch (length) // the case statements fall through
 449         {
 450             case 12: c += k[11];
 451             case 11: c += static_cast<uint32_t>(k[10]) << 8;
 452             case 10: c += static_cast<uint32_t>(k[9]) << 16;
 453             case 9 : c += static_cast<uint32_t>(k[8]) << 24;
 454             case 8 : b += k[7];
 455             case 7 : b += static_cast<uint32_t>(k[6]) << 8;
 456             case 6 : b += static_cast<uint32_t>(k[5]) << 16;
 457             case 5 : b += static_cast<uint32_t>(k[4]) << 24;
 458             case 4 : a += k[3];
 459             case 3 : a += static_cast<uint32_t>(k[2]) << 8;
 460             case 2 : a += static_cast<uint32_t>(k[1]) << 16;
 461             case 1 : a += static_cast<uint32_t>(k[0]) << 24;
 462                 break;
 463             case 0 : return c;
 464         }
 465     }
 466
 467     bitMixerFinal(a,b,c);
 468     return c;
 469 }
 470 #endif
 471
 472
 473 // * * * * * * * * * * * * * * * Global Functions  * * * * * * * * * * * * * //
 474
 475
 476 unsigned Foam::Hasher
 477 (
 478     const void *key,
 479     size_t length,
 480     unsigned initval
 481 )
 482 {
 483 #ifdef __BYTE_ORDER
 484 # if (__BYTE_ORDER == __BIG_ENDIAN)
 485     return jenkins_hashbig(key, length, initval);
 486 # else
 487     return jenkins_hashlittle(key, length, initval);
 488 # endif
 489 #else
 490     // endian-ness not known at compile-time: runtime endian test
 491     const short endianTest = 0x0100;
 492
 493     // yields 0x01 for big endian
 494     if (*(reinterpret_cast<const char *>(&endianTest)))
 495     {
 496         return jenkins_hashbig(key, length, initval);
 497     }
 498     else
 499     {
 500         return jenkins_hashlittle(key, length, initval);
 501     }
 502 #endif
 503 }
 504
 505
 506 // ----------------------------------------------------------------------------
 507 //  This works on all machines.  To be useful, it requires
 508 //  -- that the key be an array of uint32_t's, and
 509 //  -- that the length be the number of uint32_t's in the key
 510 //
 511 //  The function hashword() is identical to hashlittle() on little-endian
 512 //  machines, and identical to hashbig() on big-endian machines,
 513 //  except that the length has to be measured in uint32_ts rather than in
 514 //  bytes.  hashlittle() is more complicated than hashword() only because
 515 //  hashlittle() has to dance around fitting the key bytes into registers.
 516 // ----------------------------------------------------------------------------
 517 unsigned Foam::HasherInt
 518 (
 519     const uint32_t *k,
 520     size_t length,
 521     unsigned seed
 522 )
 523 {
 524     uint32_t a, b, c;
 525
 526     // Set up the internal state
 527     a = b = c = 0xdeadbeef + (static_cast<uint32_t>(length) << 2) + seed;
 528
 529     // handle most of the key
 530     while (length > 3)
 531     {
 532         a += k[0];
 533         b += k[1];
 534         c += k[2];
 535         bitMixer(a,b,c);
 536         length -= 3;
 537         k += 3;
 538     }
 539
 540     // handle the last 3 uint32_t's
 541     switch (length)  // all case statements fall through
 542     {
 543         case 3 : c += k[2];
 544         case 2 : b += k[1];
 545         case 1 : a += k[0];
 546             bitMixerFinal(a,b,c);
 547         case 0 :  // case 0: nothing left to add
 548             break;
 549     }
 550
 551     return c;
 552 }
 553
 554
 555 // ----------------------------------------------------------------------------
 556 // hashword2() -- same as hashword(), but take two seeds and return two
 557 // 32-bit values.  pc and pb must both be non-null, and *pc and *pb must
 558 // both be initialized with seeds.  If you pass in (*pb)==0, the output
 559 // (*pc) will be the same as the return value from hashword().
 560 // ----------------------------------------------------------------------------
 561 unsigned Foam::HasherDual
 562 (
 563     const uint32_t *k,
 564     size_t length,
 565     unsigned& hash1,  // IN: seed OUT: primary hash value
 566     unsigned& hash2   // IN: more seed OUT: secondary hash value
 567 )
 568 {
 569     uint32_t a, b, c;
 570
 571     // Set up the internal state
 572     a = b = c = 0xdeadbeef + (static_cast<uint32_t>(length) << 2) + hash1;
 573     c += hash2;
 574
 575     // handle most of the key
 576     while (length > 3)
 577     {
 578         a += k[0];
 579         b += k[1];
 580         c += k[2];
 581         bitMixer(a,b,c);
 582         length -= 3;
 583         k += 3;
 584     }
 585
 586     // handle the last 3 uint32_t's
 587     switch (length)  // all case statements fall through
 588     {
 589         case 3 : c += k[2];
 590         case 2 : b += k[1];
 591         case 1 : a += k[0];
 592             bitMixerFinal(a,b,c);
 593         case 0 :  // case 0: nothing left to add
 594             break;
 595     }
 596
 597     // report the result
 598     hash1 = c;
 599     hash2 = b;
 600
 601     // return primary hash value
 602     return c;
 603 }
 604
 605
 606 // ************************************************************************* //