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