DTS Application Library  0.2.3
Application library containing referenced objects and interfaces to common libraries
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Files | Macros | Functions
Burtle Bob hash algorythim.
Distrotech Application Library

lookup3.c, by Bob Jenkins, May 2006, Public Domain (Original Documentation) More...

Files

file  lookup3.c
 by Bob Jenkins, May 2006, Public Domain.
 

Macros

#define JHASH_INITVAL   0xdeadbeef
 Default init value for hash functioneaster egg copied from <linux/jhash.h> More...
 
#define jenhash(key, length, initval)   hashlittle(key, length, (initval) ? initval : JHASH_INITVAL);
 Define jenhash as hashlittle on big endian it should be hashbig. More...
 
#define HASH_LITTLE_ENDIAN   0
 
#define HASH_BIG_ENDIAN   0
 
#define hashsize(n)   ((uint32_t)1<<(n))
 
#define hashmask(n)   (hashsize(n)-1)
 
#define rot(x, k)   (((x)<<(k)) | ((x)>>(32-(k))))
 
#define mix(a, b, c)
 mix 3 32-bit values reversibly More...
 
#define final(a, b, c)
 final mixing of 3 32-bit values (a,b,c) into c More...
 

Functions

uint32_t hashword (const uint32_t *k, size_t length, uint32_t initval)
 hash a variable-length key into a 32-bit value (Big Endian) More...
 
void hashword2 (const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb)
 same as hashword(), but take two seeds and return two 32-bit values More...
 
uint32_t hashlittle (const void *key, size_t length, uint32_t initval)
 hash a variable-length key into a 32-bit value (Little Endian) More...
 
void hashlittle2 (const void *key, size_t length, uint32_t *pc, uint32_t *pb)
 return 2 32-bit hash values. More...
 
uint32_t hashbig (const void *key, size_t length, uint32_t initval)
 This is the same as hashword() on big-endian machines. More...
 

Detailed Description

lookup3.c, by Bob Jenkins, May 2006, Public Domain (Original Documentation) 

-------------------------------------------------------------------------------
lookup3.c, by Bob Jenkins, May 2006, Public Domain.

These are functions for producing 32-bit hashes for hash table lookup.
hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
are externally useful functions.  Routines to test the hash are included
if SELF_TEST is defined.  You can use this free for any purpose.  It's in
the public domain.  It has no warranty.

You probably want to use hashlittle().  hashlittle() and hashbig()
hash byte arrays.  hashlittle() is is faster than hashbig() on
little-endian machines.  Intel and AMD are little-endian machines.
On second thought, you probably want hashlittle2(), which is identical to
hashlittle() except it returns two 32-bit hashes for the price of one.
You could implement hashbig2() if you wanted but I haven't bothered here.

If you want to find a hash of, say, exactly 7 integers, do
  a = i1;  b = i2;  c = i3;
  mix(a,b,c);
  a += i4; b += i5; c += i6;
  mix(a,b,c);
  a += i7;
  final(a,b,c);
then use c as the hash value.  If you have a variable length array of
4-byte integers to hash, use hashword().  If you have a byte array (like
a character string), use hashlittle().  If you have several byte arrays, or
a mix of things, see the comments above hashlittle().

Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
then mix those integers.  This is fast (you can do a lot more thorough
mixing with 12*3 instructions on 3 integers than you can with 3 instructions
on 1 byte), but shoehorning those bytes into integers efficiently is messy.
-------------------------------------------------------------------------------

Macro Definition Documentation

#define final (   a,
  b,
  c 
)
Value:
{ \
c ^= b; c -= rot(b,14); \
a ^= c; a -= rot(c,11); \
b ^= a; b -= rot(a,25); \
c ^= b; c -= rot(b,16); \
a ^= c; a -= rot(c,4); \
b ^= a; b -= rot(a,14); \
c ^= b; c -= rot(b,24); \
}
rot
#define rot(x, k)
Definition: lookup3.c:75

final mixing of 3 32-bit values (a,b,c) into c 

-------------------------------------------------------------------------------
final -- final mixing of 3 32-bit values (a,b,c) into c

Pairs of (a,b,c) values differing in only a few bits will usually
produce values of c that look totally different.  This was tested for
* pairs that differed by one bit, by two bits, in any combination
  of top bits of (a,b,c), or in any combination of bottom bits of
  (a,b,c).
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  is commonly produced by subtraction) look like a single 1-bit
  difference.
* the base values were pseudorandom, all zero but one bit set, or
  all zero plus a counter that starts at zero.

These constants passed:
 14 11 25 16 4 14 24
 12 14 25 16 4 14 24
and these came close:
  4  8 15 26 3 22 24
 10  8 15 26 3 22 24
 11  8 15 26 3 22 24
-------------------------------------------------------------------------------

Definition at line 158 of file lookup3.c.

#define HASH_BIG_ENDIAN   0

Definition at line 70 of file lookup3.c.

Referenced by hashbig().

#define HASH_LITTLE_ENDIAN   0

Definition at line 69 of file lookup3.c.

Referenced by hashlittle(), and hashlittle2().

#define hashmask (   n)    (hashsize(n)-1)

Definition at line 74 of file lookup3.c.

#define hashsize (   n)    ((uint32_t)1<<(n))

Definition at line 73 of file lookup3.c.

#define jenhash (   key,
  length,
  initval 
)    hashlittle(key, length, (initval) ? initval : JHASH_INITVAL);

Define jenhash as hashlittle on big endian it should be hashbig.

Definition at line 914 of file dtsapp.h.

#define JHASH_INITVAL   0xdeadbeef

Default init value for hash functioneaster egg copied from <linux/jhash.h>

Definition at line 909 of file dtsapp.h.

#define mix (   a,
  b,
  c 
)
Value:
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
rot
#define rot(x, k)
Definition: lookup3.c:75

mix 3 32-bit values reversibly 

-------------------------------------------------------------------------------
mix -- mix 3 32-bit values reversibly.

This is reversible, so any information in (a,b,c) before mix() is
still in (a,b,c) after mix().

If four pairs of (a,b,c) inputs are run through mix(), or through
mix() in reverse, there are at least 32 bits of the output that
are sometimes the same for one pair and different for another pair.
This was tested for:
* pairs that differed by one bit, by two bits, in any combination
  of top bits of (a,b,c), or in any combination of bottom bits of
  (a,b,c).
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  is commonly produced by subtraction) look like a single 1-bit
  difference.
* the base values were pseudorandom, all zero but one bit set, or
  all zero plus a counter that starts at zero.

Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
satisfy this are
    4  6  8 16 19  4
    9 15  3 18 27 15
   14  9  3  7 17  3
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
for "differ" defined as + with a one-bit base and a two-bit delta.  I
used http://burtleburtle.net/bob/hash/avalanche.html to choose
the operations, constants, and arrangements of the variables.

This does not achieve avalanche.  There are input bits of (a,b,c)
that fail to affect some output bits of (a,b,c), especially of a.  The
most thoroughly mixed value is c, but it doesn't really even achieve
avalanche in c.

This allows some parallelism.  Read-after-writes are good at doubling
the number of bits affected, so the goal of mixing pulls in the opposite
direction as the goal of parallelism.  I did what I could.  Rotates
seem to cost as much as shifts on every machine I could lay my hands
on, and rotates are much kinder to the top and bottom bits, so I used
rotates.
-------------------------------------------------------------------------------

Definition at line 122 of file lookup3.c.

Referenced by hashbig(), hashlittle(), hashlittle2(), hashword(), and hashword2().

#define rot (   x,
  k 
)    (((x)<<(k)) | ((x)>>(32-(k))))

Definition at line 75 of file lookup3.c.

Function Documentation

uint32_t hashbig ( const void *  key,
size_t  length,
uint32_t  initval 
)

This is the same as hashword() on big-endian machines. 

 * hashbig():
 * This is the same as hashword() on big-endian machines.  It is different
 * from hashlittle() on all machines.  hashbig() takes advantage of
 * big-endian byte ordering.

Definition at line 862 of file lookup3.c.

References HASH_BIG_ENDIAN, and mix.

862  {
863  uint32_t a,b,c;
864  union {
865  const void *ptr;
866  size_t i;
867  } u; /* to cast key to (size_t) happily */
868 
869  /* Set up the internal state */
870  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
871 
872  u.ptr = key;
873  if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
874  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
875 #ifdef VALGRIND
876  const uint8_t *k8;
877 #endif
878  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
879  while (length > 12) {
880  a += k[0];
881  b += k[1];
882  c += k[2];
883  mix(a,b,c);
884  length -= 12;
885  k += 3;
886  }
887 
888  /*----------------------------- handle the last (probably partial) block */
889  /*
890  * "k[2]<<8" actually reads beyond the end of the string, but
891  * then shifts out the part it's not allowed to read. Because the
892  * string is aligned, the illegal read is in the same word as the
893  * rest of the string. Every machine with memory protection I've seen
894  * does it on word boundaries, so is OK with this. But VALGRIND will
895  * still catch it and complain. The masking trick does make the hash
896  * noticably faster for short strings (like English words).
897  */
898 #ifndef VALGRIND
899 
900  switch(length) {
901  case 12:
902  c+=k[2];
903  b+=k[1];
904  a+=k[0];
905  break;
906  case 11:
907  c+=k[2]&0xffffff00;
908  b+=k[1];
909  a+=k[0];
910  break;
911  case 10:
912  c+=k[2]&0xffff0000;
913  b+=k[1];
914  a+=k[0];
915  break;
916  case 9 :
917  c+=k[2]&0xff000000;
918  b+=k[1];
919  a+=k[0];
920  break;
921  case 8 :
922  b+=k[1];
923  a+=k[0];
924  break;
925  case 7 :
926  b+=k[1]&0xffffff00;
927  a+=k[0];
928  break;
929  case 6 :
930  b+=k[1]&0xffff0000;
931  a+=k[0];
932  break;
933  case 5 :
934  b+=k[1]&0xff000000;
935  a+=k[0];
936  break;
937  case 4 :
938  a+=k[0];
939  break;
940  case 3 :
941  a+=k[0]&0xffffff00;
942  break;
943  case 2 :
944  a+=k[0]&0xffff0000;
945  break;
946  case 1 :
947  a+=k[0]&0xff000000;
948  break;
949  case 0 :
950  return (c); /* zero length strings require no mixing */
951  }
952 
953 #else /* make valgrind happy */
954 
955  k8 = (const uint8_t *)k;
956  switch(length) { /* all the case statements fall through */
957  case 12:
958  c+=k[2];
959  b+=k[1];
960  a+=k[0];
961  break;
962  case 11:
963  c+=((uint32_t)k8[10])<<8; /* fall through */
964  case 10:
965  c+=((uint32_t)k8[9])<<16; /* fall through */
966  case 9 :
967  c+=((uint32_t)k8[8])<<24; /* fall through */
968  case 8 :
969  b+=k[1];
970  a+=k[0];
971  break;
972  case 7 :
973  b+=((uint32_t)k8[6])<<8; /* fall through */
974  case 6 :
975  b+=((uint32_t)k8[5])<<16; /* fall through */
976  case 5 :
977  b+=((uint32_t)k8[4])<<24; /* fall through */
978  case 4 :
979  a+=k[0];
980  break;
981  case 3 :
982  a+=((uint32_t)k8[2])<<8; /* fall through */
983  case 2 :
984  a+=((uint32_t)k8[1])<<16; /* fall through */
985  case 1 :
986  a+=((uint32_t)k8[0])<<24;
987  break;
988  case 0 :
989  return c;
990  }
991 
992 #endif /* !VALGRIND */
993 
994  } else { /* need to read the key one byte at a time */
995  const uint8_t *k = (const uint8_t *)key;
996 
997  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
998  while (length > 12) {
999  a += ((uint32_t)k[0])<<24;
1000  a += ((uint32_t)k[1])<<16;
1001  a += ((uint32_t)k[2])<<8;
1002  a += ((uint32_t)k[3]);
1003  b += ((uint32_t)k[4])<<24;
1004  b += ((uint32_t)k[5])<<16;
1005  b += ((uint32_t)k[6])<<8;
1006  b += ((uint32_t)k[7]);
1007  c += ((uint32_t)k[8])<<24;
1008  c += ((uint32_t)k[9])<<16;
1009  c += ((uint32_t)k[10])<<8;
1010  c += ((uint32_t)k[11]);
1011  mix(a,b,c);
1012  length -= 12;
1013  k += 12;
1014  }
1015 
1016  /*-------------------------------- last block: affect all 32 bits of (c) */
1017  switch(length) { /* all the case statements fall through */
1018  case 12:
1019  c+=k[11];
1020  /* no break */
1021  case 11:
1022  c+=((uint32_t)k[10])<<8;
1023  /* no break */
1024  case 10:
1025  c+=((uint32_t)k[9])<<16;
1026  /* no break */
1027  case 9 :
1028  c+=((uint32_t)k[8])<<24;
1029  /* no break */
1030  case 8 :
1031  b+=k[7];
1032  /* no break */
1033  case 7 :
1034  b+=((uint32_t)k[6])<<8;
1035  /* no break */
1036  case 6 :
1037  b+=((uint32_t)k[5])<<16;
1038  /* no break */
1039  case 5 :
1040  b+=((uint32_t)k[4])<<24;
1041  /* no break */
1042  case 4 :
1043  a+=k[3];
1044  /* no break */
1045  case 3 :
1046  a+=((uint32_t)k[2])<<8;
1047  /* no break */
1048  case 2 :
1049  a+=((uint32_t)k[1])<<16;
1050  /* no break */
1051  case 1 :
1052  a+=((uint32_t)k[0])<<24;
1053  break;
1054  case 0 :
1055  return (c);
1056  }
1057  }
1058 
1059  final(a,b,c);
1060  return (c);
1061 }
HASH_BIG_ENDIAN
#define HASH_BIG_ENDIAN
Definition: lookup3.c:70
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122
uint32_t hashlittle ( const void *  key,
size_t  length,
uint32_t  initval 
)

hash a variable-length key into a 32-bit value (Little Endian) 

-------------------------------------------------------------------------------
hashlittle() -- hash a variable-length key into a 32-bit value
  k       : the key (the unaligned variable-length array of bytes)
  length  : the length of the key, counting by bytes
  initval : can be any 4-byte value
Returns a 32-bit value.  Every bit of the key affects every bit of
the return value.  Two keys differing by one or two bits will have
totally different hash values.

The best hash table sizes are powers of 2.  There is no need to do
mod a prime (mod is sooo slow!).  If you need less than 32 bits,
use a bitmask.  For example, if you need only 10 bits, do
  h = (h & hashmask(10));
In which case, the hash table should have hashsize(10) elements.

If you are hashing n strings (uint8_t **)k, do it like this:
  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);

By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
code any way you wish, private, educational, or commercial.  It's free.

Use for hash table lookup, or anything where one collision in 2^^32 is
acceptable.  Do NOT use for cryptographic purposes.
-------------------------------------------------------------------------------

Definition at line 298 of file lookup3.c.

References HASH_LITTLE_ENDIAN, and mix.

298  {
299  uint32_t a,b,c; /* internal state */
300  union {
301  const void *ptr;
302  size_t i;
303  } u; /* needed for Mac Powerbook G4 */
304 
305  /* Set up the internal state */
306  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
307 
308  u.ptr = key;
309  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
310  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
311 #ifdef VALGRIND
312  const uint8_t *k8;
313 #endif
314  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
315  while (length > 12) {
316  a += k[0];
317  b += k[1];
318  c += k[2];
319  mix(a,b,c);
320  length -= 12;
321  k += 3;
322  }
323 
324  /*----------------------------- handle the last (probably partial) block */
325  /*
326  * "k[2]&0xffffff" actually reads beyond the end of the string, but
327  * then masks off the part it's not allowed to read. Because the
328  * string is aligned, the masked-off tail is in the same word as the
329  * rest of the string. Every machine with memory protection I've seen
330  * does it on word boundaries, so is OK with this. But VALGRIND will
331  * still catch it and complain. The masking trick does make the hash
332  * noticably faster for short strings (like English words).
333  */
334 #ifndef VALGRIND
335 
336  switch(length) {
337  case 12:
338  c+=k[2];
339  b+=k[1];
340  a+=k[0];
341  break;
342  case 11:
343  c+=k[2]&0xffffff;
344  b+=k[1];
345  a+=k[0];
346  break;
347  case 10:
348  c+=k[2]&0xffff;
349  b+=k[1];
350  a+=k[0];
351  break;
352  case 9 :
353  c+=k[2]&0xff;
354  b+=k[1];
355  a+=k[0];
356  break;
357  case 8 :
358  b+=k[1];
359  a+=k[0];
360  break;
361  case 7 :
362  b+=k[1]&0xffffff;
363  a+=k[0];
364  break;
365  case 6 :
366  b+=k[1]&0xffff;
367  a+=k[0];
368  break;
369  case 5 :
370  b+=k[1]&0xff;
371  a+=k[0];
372  break;
373  case 4 :
374  a+=k[0];
375  break;
376  case 3 :
377  a+=k[0]&0xffffff;
378  break;
379  case 2 :
380  a+=k[0]&0xffff;
381  break;
382  case 1 :
383  a+=k[0]&0xff;
384  break;
385  case 0 :
386  return (c); /* zero length strings require no mixing */
387  }
388 
389 #else /* make valgrind happy */
390 
391  k8 = (const uint8_t *)k;
392  switch(length) {
393  case 12:
394  c+=k[2];
395  b+=k[1];
396  a+=k[0];
397  break;
398  case 11:
399  c+=((uint32_t)k8[10])<<16; /* fall through */
400  case 10:
401  c+=((uint32_t)k8[9])<<8; /* fall through */
402  case 9 :
403  c+=k8[8]; /* fall through */
404  case 8 :
405  b+=k[1];
406  a+=k[0];
407  break;
408  case 7 :
409  b+=((uint32_t)k8[6])<<16; /* fall through */
410  case 6 :
411  b+=((uint32_t)k8[5])<<8; /* fall through */
412  case 5 :
413  b+=k8[4]; /* fall through */
414  case 4 :
415  a+=k[0];
416  break;
417  case 3 :
418  a+=((uint32_t)k8[2])<<16; /* fall through */
419  case 2 :
420  a+=((uint32_t)k8[1])<<8; /* fall through */
421  case 1 :
422  a+=k8[0];
423  break;
424  case 0 :
425  return c;
426  }
427 
428 #endif /* !valgrind */
429 
430  } else
431  if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
432  const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
433  const uint8_t *k8;
434 
435  /*--------------- all but last block: aligned reads and different mixing */
436  while (length > 12) {
437  a += k[0] + (((uint32_t)k[1])<<16);
438  b += k[2] + (((uint32_t)k[3])<<16);
439  c += k[4] + (((uint32_t)k[5])<<16);
440  mix(a,b,c);
441  length -= 12;
442  k += 6;
443  }
444 
445  /*----------------------------- handle the last (probably partial) block */
446  k8 = (const uint8_t *)k;
447  switch(length) {
448  case 12:
449  c+=k[4]+(((uint32_t)k[5])<<16);
450  b+=k[2]+(((uint32_t)k[3])<<16);
451  a+=k[0]+(((uint32_t)k[1])<<16);
452  break;
453  case 11:
454  c+=((uint32_t)k8[10])<<16; /* fall through */
455  /* no break */
456  case 10:
457  c+=k[4];
458  b+=k[2]+(((uint32_t)k[3])<<16);
459  a+=k[0]+(((uint32_t)k[1])<<16);
460  break;
461  case 9 :
462  c+=k8[8]; /* fall through */
463  /* no break */
464  case 8 :
465  b+=k[2]+(((uint32_t)k[3])<<16);
466  a+=k[0]+(((uint32_t)k[1])<<16);
467  break;
468  case 7 :
469  b+=((uint32_t)k8[6])<<16; /* fall through */
470  /* no break */
471  case 6 :
472  b+=k[2];
473  a+=k[0]+(((uint32_t)k[1])<<16);
474  break;
475  case 5 :
476  b+=k8[4]; /* fall through */
477  /* no break */
478  case 4 :
479  a+=k[0]+(((uint32_t)k[1])<<16);
480  break;
481  case 3 :
482  a+=((uint32_t)k8[2])<<16; /* fall through */
483  /* no break */
484  case 2 :
485  a+=k[0];
486  break;
487  case 1 :
488  a+=k8[0];
489  break;
490  case 0 :
491  return (c); /* zero length requires no mixing */
492  }
493 
494  } else { /* need to read the key one byte at a time */
495  const uint8_t *k = (const uint8_t *)key;
496 
497  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
498  while (length > 12) {
499  a += k[0];
500  a += ((uint32_t)k[1])<<8;
501  a += ((uint32_t)k[2])<<16;
502  a += ((uint32_t)k[3])<<24;
503  b += k[4];
504  b += ((uint32_t)k[5])<<8;
505  b += ((uint32_t)k[6])<<16;
506  b += ((uint32_t)k[7])<<24;
507  c += k[8];
508  c += ((uint32_t)k[9])<<8;
509  c += ((uint32_t)k[10])<<16;
510  c += ((uint32_t)k[11])<<24;
511  mix(a,b,c);
512  length -= 12;
513  k += 12;
514  }
515 
516  /*-------------------------------- last block: affect all 32 bits of (c) */
517  switch(length) { /* all the case statements fall through */
518  case 12:
519  c+=((uint32_t)k[11])<<24;
520  /* no break */
521  case 11:
522  c+=((uint32_t)k[10])<<16;
523  /* no break */
524  case 10:
525  c+=((uint32_t)k[9])<<8;
526  /* no break */
527  case 9 :
528  c+=k[8];
529  /* no break */
530  case 8 :
531  b+=((uint32_t)k[7])<<24;
532  /* no break */
533  case 7 :
534  b+=((uint32_t)k[6])<<16;
535  /* no break */
536  case 6 :
537  b+=((uint32_t)k[5])<<8;
538  /* no break */
539  case 5 :
540  b+=k[4];
541  /* no break */
542  case 4 :
543  a+=((uint32_t)k[3])<<24;
544  /* no break */
545  case 3 :
546  a+=((uint32_t)k[2])<<16;
547  /* no break */
548  case 2 :
549  a+=((uint32_t)k[1])<<8;
550  /* no break */
551  case 1 :
552  a+=k[0];
553  break;
554  case 0 :
555  return (c);
556  }
557  }
558 
559  final(a,b,c);
560  return (c);
561 }
HASH_LITTLE_ENDIAN
#define HASH_LITTLE_ENDIAN
Definition: lookup3.c:69
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122
void hashlittle2 ( const void *  key,
size_t  length,
uint32_t *  pc,
uint32_t *  pb 
)

return 2 32-bit hash values. 

 * hashlittle2: return 2 32-bit hash values
 *
 * This is identical to hashlittle(), except it returns two 32-bit hash
 * values instead of just one.  This is good enough for hash table
 * lookup with 2^^64 buckets, or if you want a second hash if you're not
 * happy with the first, or if you want a probably-unique 64-bit ID for
 * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".

Definition at line 574 of file lookup3.c.

References HASH_LITTLE_ENDIAN, and mix.

578  { /* IN: secondary initval, OUT: secondary hash */
579  uint32_t a,b,c; /* internal state */
580  union {
581  const void *ptr;
582  size_t i;
583  } u; /* needed for Mac Powerbook G4 */
584 
585  /* Set up the internal state */
586  a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
587  c += *pb;
588 
589  u.ptr = key;
590  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
591  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
592 #ifdef VALGRIND
593  const uint8_t *k8;
594 #endif
595 
596  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
597  while (length > 12) {
598  a += k[0];
599  b += k[1];
600  c += k[2];
601  mix(a,b,c);
602  length -= 12;
603  k += 3;
604  }
605 
606  /*----------------------------- handle the last (probably partial) block */
607  /*
608  * "k[2]&0xffffff" actually reads beyond the end of the string, but
609  * then masks off the part it's not allowed to read. Because the
610  * string is aligned, the masked-off tail is in the same word as the
611  * rest of the string. Every machine with memory protection I've seen
612  * does it on word boundaries, so is OK with this. But VALGRIND will
613  * still catch it and complain. The masking trick does make the hash
614  * noticably faster for short strings (like English words).
615  */
616 #ifndef VALGRIND
617 
618  switch(length) {
619  case 12:
620  c+=k[2];
621  b+=k[1];
622  a+=k[0];
623  break;
624  case 11:
625  c+=k[2]&0xffffff;
626  b+=k[1];
627  a+=k[0];
628  break;
629  case 10:
630  c+=k[2]&0xffff;
631  b+=k[1];
632  a+=k[0];
633  break;
634  case 9 :
635  c+=k[2]&0xff;
636  b+=k[1];
637  a+=k[0];
638  break;
639  case 8 :
640  b+=k[1];
641  a+=k[0];
642  break;
643  case 7 :
644  b+=k[1]&0xffffff;
645  a+=k[0];
646  break;
647  case 6 :
648  b+=k[1]&0xffff;
649  a+=k[0];
650  break;
651  case 5 :
652  b+=k[1]&0xff;
653  a+=k[0];
654  break;
655  case 4 :
656  a+=k[0];
657  break;
658  case 3 :
659  a+=k[0]&0xffffff;
660  break;
661  case 2 :
662  a+=k[0]&0xffff;
663  break;
664  case 1 :
665  a+=k[0]&0xff;
666  break;
667  case 0 :
668  *pc=c;
669  *pb=b;
670  return; /* zero length strings require no mixing */
671  }
672 
673 #else /* make valgrind happy */
674 
675  k8 = (const uint8_t *)k;
676  switch(length) {
677  case 12:
678  c+=k[2];
679  b+=k[1];
680  a+=k[0];
681  break;
682  case 11:
683  c+=((uint32_t)k8[10])<<16; /* fall through */
684  case 10:
685  c+=((uint32_t)k8[9])<<8; /* fall through */
686  case 9 :
687  c+=k8[8]; /* fall through */
688  case 8 :
689  b+=k[1];
690  a+=k[0];
691  break;
692  case 7 :
693  b+=((uint32_t)k8[6])<<16; /* fall through */
694  case 6 :
695  b+=((uint32_t)k8[5])<<8; /* fall through */
696  case 5 :
697  b+=k8[4]; /* fall through */
698  case 4 :
699  a+=k[0];
700  break;
701  case 3 :
702  a+=((uint32_t)k8[2])<<16; /* fall through */
703  case 2 :
704  a+=((uint32_t)k8[1])<<8; /* fall through */
705  case 1 :
706  a+=k8[0];
707  break;
708  case 0 :
709  *pc=c;
710  *pb=b;
711  return; /* zero length strings require no mixing */
712  }
713 
714 #endif /* !valgrind */
715 
716  } else
717  if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
718  const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
719  const uint8_t *k8;
720 
721  /*--------------- all but last block: aligned reads and different mixing */
722  while (length > 12) {
723  a += k[0] + (((uint32_t)k[1])<<16);
724  b += k[2] + (((uint32_t)k[3])<<16);
725  c += k[4] + (((uint32_t)k[5])<<16);
726  mix(a,b,c);
727  length -= 12;
728  k += 6;
729  }
730 
731  /*----------------------------- handle the last (probably partial) block */
732  k8 = (const uint8_t *)k;
733  switch(length) {
734  case 12:
735  c+=k[4]+(((uint32_t)k[5])<<16);
736  b+=k[2]+(((uint32_t)k[3])<<16);
737  a+=k[0]+(((uint32_t)k[1])<<16);
738  break;
739  case 11:
740  c+=((uint32_t)k8[10])<<16; /* fall through */
741  /* no break */
742  case 10:
743  c+=k[4];
744  b+=k[2]+(((uint32_t)k[3])<<16);
745  a+=k[0]+(((uint32_t)k[1])<<16);
746  break;
747  case 9 :
748  c+=k8[8]; /* fall through */
749  /* no break */
750  case 8 :
751  b+=k[2]+(((uint32_t)k[3])<<16);
752  a+=k[0]+(((uint32_t)k[1])<<16);
753  break;
754  case 7 :
755  b+=((uint32_t)k8[6])<<16; /* fall through */
756  /* no break */
757  case 6 :
758  b+=k[2];
759  a+=k[0]+(((uint32_t)k[1])<<16);
760  break;
761  case 5 :
762  b+=k8[4]; /* fall through */
763  /* no break */
764  case 4 :
765  a+=k[0]+(((uint32_t)k[1])<<16);
766  break;
767  case 3 :
768  a+=((uint32_t)k8[2])<<16; /* fall through */
769  /* no break */
770  case 2 :
771  a+=k[0];
772  break;
773  case 1 :
774  a+=k8[0];
775  break;
776  case 0 :
777  *pc=c;
778  *pb=b;
779  return; /* zero length strings require no mixing */
780  }
781 
782  } else { /* need to read the key one byte at a time */
783  const uint8_t *k = (const uint8_t *)key;
784 
785  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
786  while (length > 12) {
787  a += k[0];
788  a += ((uint32_t)k[1])<<8;
789  a += ((uint32_t)k[2])<<16;
790  a += ((uint32_t)k[3])<<24;
791  b += k[4];
792  b += ((uint32_t)k[5])<<8;
793  b += ((uint32_t)k[6])<<16;
794  b += ((uint32_t)k[7])<<24;
795  c += k[8];
796  c += ((uint32_t)k[9])<<8;
797  c += ((uint32_t)k[10])<<16;
798  c += ((uint32_t)k[11])<<24;
799  mix(a,b,c);
800  length -= 12;
801  k += 12;
802  }
803 
804  /*-------------------------------- last block: affect all 32 bits of (c) */
805  switch(length) { /* all the case statements fall through */
806  case 12:
807  c+=((uint32_t)k[11])<<24;
808  /* no break */
809  case 11:
810  c+=((uint32_t)k[10])<<16;
811  /* no break */
812  case 10:
813  c+=((uint32_t)k[9])<<8;
814  /* no break */
815  case 9 :
816  c+=k[8];
817  /* no break */
818  case 8 :
819  b+=((uint32_t)k[7])<<24;
820  /* no break */
821  case 7 :
822  b+=((uint32_t)k[6])<<16;
823  /* no break */
824  case 6 :
825  b+=((uint32_t)k[5])<<8;
826  /* no break */
827  case 5 :
828  b+=k[4];
829  /* no break */
830  case 4 :
831  a+=((uint32_t)k[3])<<24;
832  /* no break */
833  case 3 :
834  a+=((uint32_t)k[2])<<16;
835  /* no break */
836  case 2 :
837  a+=((uint32_t)k[1])<<8;
838  /* no break */
839  case 1 :
840  a+=k[0];
841  break;
842  case 0 :
843  *pc=c;
844  *pb=b;
845  return; /* zero length strings require no mixing */
846  }
847  }
848 
849  final(a,b,c);
850  *pc=c;
851  *pb=b;
852 }
HASH_LITTLE_ENDIAN
#define HASH_LITTLE_ENDIAN
Definition: lookup3.c:69
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122
uint32_t hashword ( const uint32_t *  k,
size_t  length,
uint32_t  initval 
)

hash a variable-length key into a 32-bit value (Big Endian) 

--------------------------------------------------------------------
 This works on all machines.  To be useful, it requires
 -- that the key be an array of uint32_t's, and
 -- that the length be the number of uint32_t's in the key

 The function hashword() is identical to hashlittle() on little-endian
 machines, and identical to hashbig() on big-endian machines,
 except that the length has to be measured in uint32_ts rather than in
 bytes.  hashlittle() is more complicated than hashword() only because
 hashlittle() has to dance around fitting the key bytes into registers.
--------------------------------------------------------------------

Definition at line 182 of file lookup3.c.

References mix.

185  { /* the previous hash, or an arbitrary value */
186  uint32_t a,b,c;
187 
188  /* Set up the internal state */
189  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
190 
191  /*------------------------------------------------- handle most of the key */
192  while (length > 3) {
193  a += k[0];
194  b += k[1];
195  c += k[2];
196  mix(a,b,c);
197  length -= 3;
198  k += 3;
199  }
200 
201  /*------------------------------------------- handle the last 3 uint32_t's */
202  switch(length) { /* all the case statements fall through */
203  case 3 :
204  c+=k[2];
205  /* no break */
206  case 2 :
207  b+=k[1];
208  /* no break */
209  case 1 :
210  a+=k[0];
211  final(a,b,c);
212  /* no break */
213  case 0: /* case 0: nothing left to add */
214  break;
215  }
216  /*------------------------------------------------------ report the result */
217  return (c);
218 }
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122
void hashword2 ( const uint32_t *  k,
size_t  length,
uint32_t *  pc,
uint32_t *  pb 
)

same as hashword(), but take two seeds and return two 32-bit values 

--------------------------------------------------------------------
hashword2() -- same as hashword(), but take two seeds and return two
32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
both be initialized with seeds.  If you pass in (*pb)==0, the output
(*pc) will be the same as the return value from hashword().
--------------------------------------------------------------------

Definition at line 229 of file lookup3.c.

References mix.

233  { /* IN: more seed OUT: secondary hash value */
234  uint32_t a,b,c;
235 
236  /* Set up the internal state */
237  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
238  c += *pb;
239 
240  /*------------------------------------------------- handle most of the key */
241  while (length > 3) {
242  a += k[0];
243  b += k[1];
244  c += k[2];
245  mix(a,b,c);
246  length -= 3;
247  k += 3;
248  }
249 
250  /*------------------------------------------- handle the last 3 uint32_t's */
251  switch(length) { /* all the case statements fall through */
252  case 3 :
253  c+=k[2];
254  /* no break */
255  case 2 :
256  b+=k[1];
257  /* no break */
258  case 1 :
259  a+=k[0];
260  final(a,b,c);
261  /* no break */
262  case 0: /* case 0: nothing left to add */
263  break;
264  }
265  /*------------------------------------------------------ report the result */
266  *pc=c;
267  *pb=b;
268 }
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122