/src/jansson-2.14/src/lookup3.h

Source
// clang-format off
/*
-------------------------------------------------------------------------------
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.
-------------------------------------------------------------------------------
*/

#include <stdlib.h>

#ifdef HAVE_CONFIG_H
#include <jansson_private_config.h>
#endif

#ifdef HAVE_STDINT_H
#include <stdint.h>     /* defines uint32_t etc */
#endif

#ifdef HAVE_SYS_PARAM_H
#include <sys/param.h>  /* attempt to define endianness */
#endif

#ifdef HAVE_ENDIAN_H
# include <endian.h>    /* attempt to define endianness */
#endif

/*
 * My best guess at if you are big-endian or little-endian.  This may
 * need adjustment.
 */
#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
     __BYTE_ORDER == __LITTLE_ENDIAN) || \
    (defined(i386) || defined(__i386__) || defined(__i486__) || \
     defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
# define HASH_LITTLE_ENDIAN 1
# define HASH_BIG_ENDIAN 0
#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
       __BYTE_ORDER == __BIG_ENDIAN) || \
      (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
# define HASH_LITTLE_ENDIAN 0
# define HASH_BIG_ENDIAN 1
#else
# define HASH_LITTLE_ENDIAN 0
# define HASH_BIG_ENDIAN 0
#endif

#define hashsize(n) ((size_t)1<<(n))
#define hashmask(n) (hashsize(n)-1)
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

/*
-------------------------------------------------------------------------------
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.
-------------------------------------------------------------------------------
*/
#define mix(a,b,c) \
{ \
  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; \
}

/*
-------------------------------------------------------------------------------
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
-------------------------------------------------------------------------------
*/
#define final(a,b,c) \
{ \
  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); \
}

/*
-------------------------------------------------------------------------------
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.
-------------------------------------------------------------------------------
*/

static uint32_t hashlittle(const void *key, size_t length, uint32_t initval)
{
  uint32_t a,b,c;                                          /* internal state */
  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */

  /* Set up the internal state */
  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;

  u.ptr = key;
  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */

/* Detect Valgrind or AddressSanitizer */
#ifdef VALGRIND
# define NO_MASKING_TRICK 1
#else
# if defined(__has_feature)  /* Clang */
#  if __has_feature(address_sanitizer)  /* is ASAN enabled? */
#   define NO_MASKING_TRICK 1
#  endif
# else
#  if defined(__SANITIZE_ADDRESS__)  /* GCC 4.8.x, is ASAN enabled? */
#   define NO_MASKING_TRICK 1
#  endif
# endif
#endif

#ifdef NO_MASKING_TRICK
    const uint8_t  *k8;
#endif

    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    while (length > 12)
    {
      a += k[0];
      b += k[1];
      c += k[2];
      mix(a,b,c);
      length -= 12;
      k += 3;
    }

    /*----------------------------- handle the last (probably partial) block */
    /* 
     * "k[2]&0xffffff" actually reads beyond the end of the string, but
     * then masks off the part it's not allowed to read.  Because the
     * string is aligned, the masked-off tail is in the same word as the
     * rest of the string.  Every machine with memory protection I've seen
     * does it on word boundaries, so is OK with this.  But VALGRIND will
     * still catch it and complain.  The masking trick does make the hash
     * noticeably faster for short strings (like English words).
     */
#ifndef NO_MASKING_TRICK

    switch(length)
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
    case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
    case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
    case 6 : b+=k[1]&0xffff; a+=k[0]; break;
    case 5 : b+=k[1]&0xff; a+=k[0]; break;
    case 4 : a+=k[0]; break;
    case 3 : a+=k[0]&0xffffff; break;
    case 2 : a+=k[0]&0xffff; break;
    case 1 : a+=k[0]&0xff; break;
    case 0 : return c;              /* zero length strings require no mixing */
    }

#else /* make valgrind happy */

    k8 = (const uint8_t *)k;
    switch(length)
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
    case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
    case 9 : c+=k8[8];                   /* fall through */
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
    case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
    case 5 : b+=k8[4];                   /* fall through */
    case 4 : a+=k[0]; break;
    case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
    case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
    case 1 : a+=k8[0]; break;
    case 0 : return c;
    }

#endif /* !valgrind */

  } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
    const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
    const uint8_t  *k8;

    /*--------------- all but last block: aligned reads and different mixing */
    while (length > 12)
    {
      a += k[0] + (((uint32_t)k[1])<<16);
      b += k[2] + (((uint32_t)k[3])<<16);
      c += k[4] + (((uint32_t)k[5])<<16);
      mix(a,b,c);
      length -= 12;
      k += 6;
    }

    /*----------------------------- handle the last (probably partial) block */
    k8 = (const uint8_t *)k;
    switch(length)
    {
    case 12: c+=k[4]+(((uint32_t)k[5])<<16);
             b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
    case 10: c+=k[4];
             b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 9 : c+=k8[8];                      /* fall through */
    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
    case 6 : b+=k[2];
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 5 : b+=k8[4];                      /* fall through */
    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
    case 2 : a+=k[0];
             break;
    case 1 : a+=k8[0];
             break;
    case 0 : return c;                     /* zero length requires no mixing */
    }

  } else {                        /* need to read the key one byte at a time */
    const uint8_t *k = (const uint8_t *)key;

    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    while (length > 12)
    {
      a += k[0];
      a += ((uint32_t)k[1])<<8;
      a += ((uint32_t)k[2])<<16;
      a += ((uint32_t)k[3])<<24;
      b += k[4];
      b += ((uint32_t)k[5])<<8;
      b += ((uint32_t)k[6])<<16;
      b += ((uint32_t)k[7])<<24;
      c += k[8];
      c += ((uint32_t)k[9])<<8;
      c += ((uint32_t)k[10])<<16;
      c += ((uint32_t)k[11])<<24;
      mix(a,b,c);
      length -= 12;
      k += 12;
    }

    /*-------------------------------- last block: affect all 32 bits of (c) */
    switch(length)                   /* all the case statements fall through */
    {
    case 12: c+=((uint32_t)k[11])<<24; /* fall through */
    case 11: c+=((uint32_t)k[10])<<16; /* fall through */
    case 10: c+=((uint32_t)k[9])<<8; /* fall through */
    case 9 : c+=k[8]; /* fall through */
    case 8 : b+=((uint32_t)k[7])<<24; /* fall through */
    case 7 : b+=((uint32_t)k[6])<<16; /* fall through */
    case 6 : b+=((uint32_t)k[5])<<8; /* fall through */
    case 5 : b+=k[4]; /* fall through */
    case 4 : a+=((uint32_t)k[3])<<24; /* fall through */
    case 3 : a+=((uint32_t)k[2])<<16; /* fall through */
    case 2 : a+=((uint32_t)k[1])<<8; /* fall through */
    case 1 : a+=k[0];
             break;
    case 0 : return c;
    }
  }

  final(a,b,c);
  return c;
}

Coverage Report

Created: 2026-02-14 06:42

Line	Count	Source
1		// clang-format off
2		/*
3		-------------------------------------------------------------------------------
4		lookup3.c, by Bob Jenkins, May 2006, Public Domain.
5
6		These are functions for producing 32-bit hashes for hash table lookup.
7		hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
8		are externally useful functions. Routines to test the hash are included
9		if SELF_TEST is defined. You can use this free for any purpose. It's in
10		the public domain. It has no warranty.
11
12		You probably want to use hashlittle(). hashlittle() and hashbig()
13		hash byte arrays. hashlittle() is is faster than hashbig() on
14		little-endian machines. Intel and AMD are little-endian machines.
15		On second thought, you probably want hashlittle2(), which is identical to
16		hashlittle() except it returns two 32-bit hashes for the price of one.
17		You could implement hashbig2() if you wanted but I haven't bothered here.
18
19		If you want to find a hash of, say, exactly 7 integers, do
20		a = i1; b = i2; c = i3;
21		mix(a,b,c);
22		a += i4; b += i5; c += i6;
23		mix(a,b,c);
24		a += i7;
25		final(a,b,c);
26		then use c as the hash value. If you have a variable length array of
27		4-byte integers to hash, use hashword(). If you have a byte array (like
28		a character string), use hashlittle(). If you have several byte arrays, or
29		a mix of things, see the comments above hashlittle().
30
31		Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
32		then mix those integers. This is fast (you can do a lot more thorough
33		mixing with 12*3 instructions on 3 integers than you can with 3 instructions
34		on 1 byte), but shoehorning those bytes into integers efficiently is messy.
35		-------------------------------------------------------------------------------
36		*/
37
38		#include <stdlib.h>
39
40		#ifdef HAVE_CONFIG_H
41		#include <jansson_private_config.h>
42		#endif
43
44		#ifdef HAVE_STDINT_H
45		#include <stdint.h> /* defines uint32_t etc */
46		#endif
47
48		#ifdef HAVE_SYS_PARAM_H
49		#include <sys/param.h> /* attempt to define endianness */
50		#endif
51
52		#ifdef HAVE_ENDIAN_H
53		# include <endian.h> /* attempt to define endianness */
54		#endif
55
56		/*
57		* My best guess at if you are big-endian or little-endian. This may
58		* need adjustment.
59		*/
60		#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
61		__BYTE_ORDER == __LITTLE_ENDIAN) \|\| \
62		(defined(i386) \|\| defined(__i386__) \|\| defined(__i486__) \|\| \
63		defined(__i586__) \|\| defined(__i686__) \|\| defined(vax) \|\| defined(MIPSEL))
64	0	# define HASH_LITTLE_ENDIAN 1
65		# define HASH_BIG_ENDIAN 0
66		#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
67		__BYTE_ORDER == __BIG_ENDIAN) \|\| \
68		(defined(sparc) \|\| defined(POWERPC) \|\| defined(mc68000) \|\| defined(sel))
69		# define HASH_LITTLE_ENDIAN 0
70		# define HASH_BIG_ENDIAN 1
71		#else
72		# define HASH_LITTLE_ENDIAN 0
73		# define HASH_BIG_ENDIAN 0
74		#endif
75
76	0	#define hashsize(n) ((size_t)1<<(n))
77	0	#define hashmask(n) (hashsize(n)-1)
78	0	#define rot(x,k) (((x)<<(k)) \| ((x)>>(32-(k))))
79
80		/*
81		-------------------------------------------------------------------------------
82		mix -- mix 3 32-bit values reversibly.
83
84		This is reversible, so any information in (a,b,c) before mix() is
85		still in (a,b,c) after mix().
86
87		If four pairs of (a,b,c) inputs are run through mix(), or through
88		mix() in reverse, there are at least 32 bits of the output that
89		are sometimes the same for one pair and different for another pair.
90		This was tested for:
91		* pairs that differed by one bit, by two bits, in any combination
92		of top bits of (a,b,c), or in any combination of bottom bits of
93		(a,b,c).
94		* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
95		the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
96		is commonly produced by subtraction) look like a single 1-bit
97		difference.
98		* the base values were pseudorandom, all zero but one bit set, or
99		all zero plus a counter that starts at zero.
100
101		Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
102		satisfy this are
103		4 6 8 16 19 4
104		9 15 3 18 27 15
105		14 9 3 7 17 3
106		Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
107		for "differ" defined as + with a one-bit base and a two-bit delta. I
108		used http://burtleburtle.net/bob/hash/avalanche.html to choose
109		the operations, constants, and arrangements of the variables.
110
111		This does not achieve avalanche. There are input bits of (a,b,c)
112		that fail to affect some output bits of (a,b,c), especially of a. The
113		most thoroughly mixed value is c, but it doesn't really even achieve
114		avalanche in c.
115
116		This allows some parallelism. Read-after-writes are good at doubling
117		the number of bits affected, so the goal of mixing pulls in the opposite
118		direction as the goal of parallelism. I did what I could. Rotates
119		seem to cost as much as shifts on every machine I could lay my hands
120		on, and rotates are much kinder to the top and bottom bits, so I used
121		rotates.
122		-------------------------------------------------------------------------------
123		*/
124	0	#define mix(a,b,c) \
125	0	{ \
126	0	a -= c; a ^= rot(c, 4); c += b; \
127	0	b -= a; b ^= rot(a, 6); a += c; \
128	0	c -= b; c ^= rot(b, 8); b += a; \
129	0	a -= c; a ^= rot(c,16); c += b; \
130	0	b -= a; b ^= rot(a,19); a += c; \
131	0	c -= b; c ^= rot(b, 4); b += a; \
132	0	}
133
134		/*
135		-------------------------------------------------------------------------------
136		final -- final mixing of 3 32-bit values (a,b,c) into c
137
138		Pairs of (a,b,c) values differing in only a few bits will usually
139		produce values of c that look totally different. This was tested for
140		* pairs that differed by one bit, by two bits, in any combination
141		of top bits of (a,b,c), or in any combination of bottom bits of
142		(a,b,c).
143		* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
144		the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
145		is commonly produced by subtraction) look like a single 1-bit
146		difference.
147		* the base values were pseudorandom, all zero but one bit set, or
148		all zero plus a counter that starts at zero.
149
150		These constants passed:
151		14 11 25 16 4 14 24
152		12 14 25 16 4 14 24
153		and these came close:
154		4 8 15 26 3 22 24
155		10 8 15 26 3 22 24
156		11 8 15 26 3 22 24
157		-------------------------------------------------------------------------------
158		*/
159	0	#define final(a,b,c) \
160	0	{ \
161	0	c ^= b; c -= rot(b,14); \
162	0	a ^= c; a -= rot(c,11); \
163	0	b ^= a; b -= rot(a,25); \
164	0	c ^= b; c -= rot(b,16); \
165	0	a ^= c; a -= rot(c,4); \
166	0	b ^= a; b -= rot(a,14); \
167	0	c ^= b; c -= rot(b,24); \
168	0	}
169
170		/*
171		-------------------------------------------------------------------------------
172		hashlittle() -- hash a variable-length key into a 32-bit value
173		k : the key (the unaligned variable-length array of bytes)
174		length : the length of the key, counting by bytes
175		initval : can be any 4-byte value
176		Returns a 32-bit value. Every bit of the key affects every bit of
177		the return value. Two keys differing by one or two bits will have
178		totally different hash values.
179
180		The best hash table sizes are powers of 2. There is no need to do
181		mod a prime (mod is sooo slow!). If you need less than 32 bits,
182		use a bitmask. For example, if you need only 10 bits, do
183		h = (h & hashmask(10));
184		In which case, the hash table should have hashsize(10) elements.
185
186		If you are hashing n strings (uint8_t **)k, do it like this:
187		for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
188
189		By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
190		code any way you wish, private, educational, or commercial. It's free.
191
192		Use for hash table lookup, or anything where one collision in 2^^32 is
193		acceptable. Do NOT use for cryptographic purposes.
194		-------------------------------------------------------------------------------
195		*/
196
197		static uint32_t hashlittle(const void *key, size_t length, uint32_t initval)
198	0	{
199	0	uint32_t a,b,c; /* internal state */
200	0	union { const void ptr; size_t i; } u; / needed for Mac Powerbook G4 */
201
202		/* Set up the internal state */
203	0	a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
204
205	0	u.ptr = key;
206	0	if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
207	0	const uint32_t k = (const uint32_t )key; /* read 32-bit chunks */
208
209		/* Detect Valgrind or AddressSanitizer */
210		#ifdef VALGRIND
211		# define NO_MASKING_TRICK 1
212		#else
213	0	# if defined(__has_feature) /* Clang */
214		# if __has_feature(address_sanitizer) /* is ASAN enabled? */
215		# define NO_MASKING_TRICK 1
216		# endif
217		# else
218		# if defined(__SANITIZE_ADDRESS__) /* GCC 4.8.x, is ASAN enabled? */
219		# define NO_MASKING_TRICK 1
220		# endif
221		# endif
222	0	#endif
223
224		#ifdef NO_MASKING_TRICK
225		const uint8_t *k8;
226		#endif
227
228		/------ all but last block: aligned reads and affect 32 bits of (a,b,c) /
229	0	while (length > 12)
230	0	{
231	0	a += k[0];
232	0	b += k[1];
233	0	c += k[2];
234	0	mix(a,b,c);
235	0	length -= 12;
236	0	k += 3;
237	0	}
238
239		/----------------------------- handle the last (probably partial) block /
240		/*
241		* "k[2]&0xffffff" actually reads beyond the end of the string, but
242		* then masks off the part it's not allowed to read. Because the
243		* string is aligned, the masked-off tail is in the same word as the
244		* rest of the string. Every machine with memory protection I've seen
245		* does it on word boundaries, so is OK with this. But VALGRIND will
246		* still catch it and complain. The masking trick does make the hash
247		* noticeably faster for short strings (like English words).
248		*/
249	0	#ifndef NO_MASKING_TRICK
250
251	0	switch(length)
252	0	{
253	0	case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
254	0	case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
255	0	case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
256	0	case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
257	0	case 8 : b+=k[1]; a+=k[0]; break;
258	0	case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
259	0	case 6 : b+=k[1]&0xffff; a+=k[0]; break;
260	0	case 5 : b+=k[1]&0xff; a+=k[0]; break;
261	0	case 4 : a+=k[0]; break;
262	0	case 3 : a+=k[0]&0xffffff; break;
263	0	case 2 : a+=k[0]&0xffff; break;
264	0	case 1 : a+=k[0]&0xff; break;
265	0	case 0 : return c; /* zero length strings require no mixing */
266	0	}
267
268		#else /* make valgrind happy */
269
270		k8 = (const uint8_t *)k;
271		switch(length)
272		{
273		case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
274		case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
275		case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
276		case 9 : c+=k8[8]; /* fall through */
277		case 8 : b+=k[1]; a+=k[0]; break;
278		case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
279		case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
280		case 5 : b+=k8[4]; /* fall through */
281		case 4 : a+=k[0]; break;
282		case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
283		case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
284		case 1 : a+=k8[0]; break;
285		case 0 : return c;
286		}
287
288		#endif /* !valgrind */
289
290	0	} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
291	0	const uint16_t k = (const uint16_t )key; /* read 16-bit chunks */
292	0	const uint8_t *k8;
293
294		/--------------- all but last block: aligned reads and different mixing /
295	0	while (length > 12)
296	0	{
297	0	a += k[0] + (((uint32_t)k[1])<<16);
298	0	b += k[2] + (((uint32_t)k[3])<<16);
299	0	c += k[4] + (((uint32_t)k[5])<<16);
300	0	mix(a,b,c);
301	0	length -= 12;
302	0	k += 6;
303	0	}
304
305		/----------------------------- handle the last (probably partial) block /
306	0	k8 = (const uint8_t *)k;
307	0	switch(length)
308	0	{
309	0	case 12: c+=k[4]+(((uint32_t)k[5])<<16);
310	0	b+=k[2]+(((uint32_t)k[3])<<16);
311	0	a+=k[0]+(((uint32_t)k[1])<<16);
312	0	break;
313	0	case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
314	0	case 10: c+=k[4];
315	0	b+=k[2]+(((uint32_t)k[3])<<16);
316	0	a+=k[0]+(((uint32_t)k[1])<<16);
317	0	break;
318	0	case 9 : c+=k8[8]; /* fall through */
319	0	case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
320	0	a+=k[0]+(((uint32_t)k[1])<<16);
321	0	break;
322	0	case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
323	0	case 6 : b+=k[2];
324	0	a+=k[0]+(((uint32_t)k[1])<<16);
325	0	break;
326	0	case 5 : b+=k8[4]; /* fall through */
327	0	case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
328	0	break;
329	0	case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
330	0	case 2 : a+=k[0];
331	0	break;
332	0	case 1 : a+=k8[0];
333	0	break;
334	0	case 0 : return c; /* zero length requires no mixing */
335	0	}
336
337	0	} else { /* need to read the key one byte at a time */
338	0	const uint8_t k = (const uint8_t )key;
339
340		/--------------- all but the last block: affect some 32 bits of (a,b,c) /
341	0	while (length > 12)
342	0	{
343	0	a += k[0];
344	0	a += ((uint32_t)k[1])<<8;
345	0	a += ((uint32_t)k[2])<<16;
346	0	a += ((uint32_t)k[3])<<24;
347	0	b += k[4];
348	0	b += ((uint32_t)k[5])<<8;
349	0	b += ((uint32_t)k[6])<<16;
350	0	b += ((uint32_t)k[7])<<24;
351	0	c += k[8];
352	0	c += ((uint32_t)k[9])<<8;
353	0	c += ((uint32_t)k[10])<<16;
354	0	c += ((uint32_t)k[11])<<24;
355	0	mix(a,b,c);
356	0	length -= 12;
357	0	k += 12;
358	0	}
359
360		/-------------------------------- last block: affect all 32 bits of (c) /
361	0	switch(length) /* all the case statements fall through */
362	0	{
363	0	case 12: c+=((uint32_t)k[11])<<24; /* fall through */
364	0	case 11: c+=((uint32_t)k[10])<<16; /* fall through */
365	0	case 10: c+=((uint32_t)k[9])<<8; /* fall through */
366	0	case 9 : c+=k[8]; /* fall through */
367	0	case 8 : b+=((uint32_t)k[7])<<24; /* fall through */
368	0	case 7 : b+=((uint32_t)k[6])<<16; /* fall through */
369	0	case 6 : b+=((uint32_t)k[5])<<8; /* fall through */
370	0	case 5 : b+=k[4]; /* fall through */
371	0	case 4 : a+=((uint32_t)k[3])<<24; /* fall through */
372	0	case 3 : a+=((uint32_t)k[2])<<16; /* fall through */
373	0	case 2 : a+=((uint32_t)k[1])<<8; /* fall through */
374	0	case 1 : a+=k[0];
375	0	break;
376	0	case 0 : return c;
377	0	}
378	0	}
379
380	0	final(a,b,c);
381	0	return c;
382	0	}