| blob | fb3ad3396b111316fe2995c0440a1a39620f7431 |
1 /*---------------------------------------------------------------------------*\
2 ========= |
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4 \\ / O peration |
5 \\ / A nd | Copyright (C) 2011 OpenFOAM Foundation
6 \\/ M anipulation |
7 -------------------------------------------------------------------------------
8 License
9 This file is part of OpenFOAM.
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.
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.
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/>.
24 Description
25 Hashing functions, mostly from Bob Jenkins
26 \*---------------------------------------------------------------------------*/
28 #include "Hasher.H"
29 #include "HasherInt.H"
31 #if defined (__GLIBC__)
32 # include <endian.h>
33 #endif
35 // Left-rotate a 32-bit value and carry by nBits
36 #define bitRotateLeft(x, nBits) (((x) << (nBits)) | ((x) >> (32 - (nBits))))
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 // ----------------------------------------------------------------------------
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 // ----------------------------------------------------------------------------
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 }
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 // ----------------------------------------------------------------------------
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 }
163 // * * * * * * * * * * * * * * Static Functions * * * * * * * * * * * * * * //
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 // ----------------------------------------------------------------------------
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
202 // Set up the internal state
203 a = b = c = 0xdeadbeef + static_cast<uint32_t>(length) + initval;
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);
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 }
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);
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 }
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);
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;
326 bitMixer(a,b,c);
327 length -= 12;
328 k += 12;
329 }
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];
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];
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;
350 case 0 : return c;
351 }
352 }
354 bitMixerFinal(a,b,c);
355 return c;
356 }
357 #endif
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
380 // Set up the internal state
381 a = b = c = 0xdeadbeef + static_cast<uint32_t>(length) + initval;
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);
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 }
400 // handle the last (probably partial) block byte-wise
401 const uint8_t *k8 = reinterpret_cast<const uint8_t*>(k);
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);
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]);
441 bitMixer(a,b,c);
442 length -= 12;
443 k += 12;
444 }
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 }
466 bitMixerFinal(a,b,c);
467 return c;
468 }
469 #endif
472 // * * * * * * * * * * * * * * * Global Functions * * * * * * * * * * * * * //
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;
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 }
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;
525 // Set up the internal state
526 a = b = c = 0xdeadbeef + (static_cast<uint32_t>(length) << 2) + seed;
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 }
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 }
550 return c;
551 }
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;
570 // Set up the internal state
571 a = b = c = 0xdeadbeef + (static_cast<uint32_t>(length) << 2) + hash1;
572 c += hash2;
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 }
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 }
596 // report the result
597 hash1 = c;
598 hash2 = b;
600 // return primary hash value
601 return c;
602 }
605 // ************************************************************************* //