1// Modified by Russ Cox to add "namespace re2".
2// Also threw away all but hashword and hashword2.
3// http://burtleburtle.net/bob/c/lookup3.c
4
5/*
6-------------------------------------------------------------------------------
7lookup3.c, by Bob Jenkins, May 2006, Public Domain.
8
9These are functions for producing 32-bit hashes for hash table lookup.
10hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
11are externally useful functions.  Routines to test the hash are included
12if SELF_TEST is defined.  You can use this free for any purpose.  It's in
13the public domain.  It has no warranty.
14
15You probably want to use hashlittle().  hashlittle() and hashbig()
16hash byte arrays.  hashlittle() is is faster than hashbig() on
17little-endian machines.  Intel and AMD are little-endian machines.
18On second thought, you probably want hashlittle2(), which is identical to
19hashlittle() except it returns two 32-bit hashes for the price of one.
20You could implement hashbig2() if you wanted but I haven't bothered here.
21
22If you want to find a hash of, say, exactly 7 integers, do
23  a = i1;  b = i2;  c = i3;
24  mix(a,b,c);
25  a += i4; b += i5; c += i6;
26  mix(a,b,c);
27  a += i7;
28  final(a,b,c);
29then use c as the hash value.  If you have a variable length array of
304-byte integers to hash, use hashword().  If you have a byte array (like
31a character string), use hashlittle().  If you have several byte arrays, or
32a mix of things, see the comments above hashlittle().
33
34Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
35then mix those integers.  This is fast (you can do a lot more thorough
36mixing with 12*3 instructions on 3 integers than you can with 3 instructions
37on 1 byte), but shoehorning those bytes into integers efficiently is messy.
38-------------------------------------------------------------------------------
39*/
40
41#include "util/util.h"
42
43#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
44
45/*
46-------------------------------------------------------------------------------
47mix -- mix 3 32-bit values reversibly.
48
49This is reversible, so any information in (a,b,c) before mix() is
50still in (a,b,c) after mix().
51
52If four pairs of (a,b,c) inputs are run through mix(), or through
53mix() in reverse, there are at least 32 bits of the output that
54are sometimes the same for one pair and different for another pair.
55This was tested for:
56* pairs that differed by one bit, by two bits, in any combination
57  of top bits of (a,b,c), or in any combination of bottom bits of
58  (a,b,c).
59* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
60  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
61  is commonly produced by subtraction) look like a single 1-bit
62  difference.
63* the base values were pseudorandom, all zero but one bit set, or
64  all zero plus a counter that starts at zero.
65
66Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
67satisfy this are
68    4  6  8 16 19  4
69    9 15  3 18 27 15
70   14  9  3  7 17  3
71Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
72for "differ" defined as + with a one-bit base and a two-bit delta.  I
73used http://burtleburtle.net/bob/hash/avalanche.html to choose
74the operations, constants, and arrangements of the variables.
75
76This does not achieve avalanche.  There are input bits of (a,b,c)
77that fail to affect some output bits of (a,b,c), especially of a.  The
78most thoroughly mixed value is c, but it doesn't really even achieve
79avalanche in c.
80
81This allows some parallelism.  Read-after-writes are good at doubling
82the number of bits affected, so the goal of mixing pulls in the opposite
83direction as the goal of parallelism.  I did what I could.  Rotates
84seem to cost as much as shifts on every machine I could lay my hands
85on, and rotates are much kinder to the top and bottom bits, so I used
86rotates.
87-------------------------------------------------------------------------------
88*/
89#define mix(a,b,c) \
90{ \
91  a -= c;  a ^= rot(c, 4);  c += b; \
92  b -= a;  b ^= rot(a, 6);  a += c; \
93  c -= b;  c ^= rot(b, 8);  b += a; \
94  a -= c;  a ^= rot(c,16);  c += b; \
95  b -= a;  b ^= rot(a,19);  a += c; \
96  c -= b;  c ^= rot(b, 4);  b += a; \
97}
98
99/*
100-------------------------------------------------------------------------------
101final -- final mixing of 3 32-bit values (a,b,c) into c
102
103Pairs of (a,b,c) values differing in only a few bits will usually
104produce values of c that look totally different.  This was tested for
105* pairs that differed by one bit, by two bits, in any combination
106  of top bits of (a,b,c), or in any combination of bottom bits of
107  (a,b,c).
108* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
109  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
110  is commonly produced by subtraction) look like a single 1-bit
111  difference.
112* the base values were pseudorandom, all zero but one bit set, or
113  all zero plus a counter that starts at zero.
114
115These constants passed:
116 14 11 25 16 4 14 24
117 12 14 25 16 4 14 24
118and these came close:
119  4  8 15 26 3 22 24
120 10  8 15 26 3 22 24
121 11  8 15 26 3 22 24
122-------------------------------------------------------------------------------
123*/
124#define final(a,b,c) \
125{ \
126  c ^= b; c -= rot(b,14); \
127  a ^= c; a -= rot(c,11); \
128  b ^= a; b -= rot(a,25); \
129  c ^= b; c -= rot(b,16); \
130  a ^= c; a -= rot(c,4);  \
131  b ^= a; b -= rot(a,14); \
132  c ^= b; c -= rot(b,24); \
133}
134
135namespace re2 {
136
137/*
138--------------------------------------------------------------------
139 This works on all machines.  To be useful, it requires
140 -- that the key be an array of uint32_t's, and
141 -- that the length be the number of uint32_t's in the key
142
143 The function hashword() is identical to hashlittle() on little-endian
144 machines, and identical to hashbig() on big-endian machines,
145 except that the length has to be measured in uint32_ts rather than in
146 bytes.  hashlittle() is more complicated than hashword() only because
147 hashlittle() has to dance around fitting the key bytes into registers.
148--------------------------------------------------------------------
149*/
150uint32 hashword(
151const uint32 *k,                   /* the key, an array of uint32_t values */
152size_t          length,               /* the length of the key, in uint32_ts */
153uint32        initval)         /* the previous hash, or an arbitrary value */
154{
155  uint32_t a,b,c;
156
157  /* Set up the internal state */
158  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
159
160  /*------------------------------------------------- handle most of the key */
161  while (length > 3)
162  {
163    a += k[0];
164    b += k[1];
165    c += k[2];
166    mix(a,b,c);
167    length -= 3;
168    k += 3;
169  }
170
171  /*------------------------------------------- handle the last 3 uint32_t's */
172  switch(length)                     /* all the case statements fall through */
173  {
174  case 3 : c+=k[2];
175  case 2 : b+=k[1];
176  case 1 : a+=k[0];
177    final(a,b,c);
178  case 0:     /* case 0: nothing left to add */
179    break;
180  }
181  /*------------------------------------------------------ report the result */
182  return c;
183}
184
185
186/*
187--------------------------------------------------------------------
188hashword2() -- same as hashword(), but take two seeds and return two
18932-bit values.  pc and pb must both be nonnull, and *pc and *pb must
190both be initialized with seeds.  If you pass in (*pb)==0, the output
191(*pc) will be the same as the return value from hashword().
192--------------------------------------------------------------------
193*/
194void hashword2 (
195const uint32 *k,                   /* the key, an array of uint32_t values */
196size_t          length,               /* the length of the key, in uint32_ts */
197uint32       *pc,                      /* IN: seed OUT: primary hash value */
198uint32       *pb)               /* IN: more seed OUT: secondary hash value */
199{
200  uint32_t a,b,c;
201
202  /* Set up the internal state */
203  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
204  c += *pb;
205
206  /*------------------------------------------------- handle most of the key */
207  while (length > 3)
208  {
209    a += k[0];
210    b += k[1];
211    c += k[2];
212    mix(a,b,c);
213    length -= 3;
214    k += 3;
215  }
216
217  /*------------------------------------------- handle the last 3 uint32_t's */
218  switch(length)                     /* all the case statements fall through */
219  {
220  case 3 : c+=k[2];
221  case 2 : b+=k[1];
222  case 1 : a+=k[0];
223    final(a,b,c);
224  case 0:     /* case 0: nothing left to add */
225    break;
226  }
227  /*------------------------------------------------------ report the result */
228  *pc=c; *pb=b;
229}
230
231}  // namespace re2
232