Lines Matching +full:a +full:- +full:c
2 * Taken from http://burtleburtle.net/bob/c/lookup3.c
9 -------------------------------------------------------------------------------
10 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
12 These are functions for producing 32-bit hashes for hash table lookup.
20 little-endian machines. Intel and AMD are little-endian machines.
22 hashlittle() except it returns two 32-bit hashes for the price of one.
25 If you want to find a hash of, say, exactly 7 integers, do
26 a = i1; b = i2; c = i3;
27 mix(a,b,c);
28 a += i4; b += i5; c += i6;
29 mix(a,b,c);
30 a += i7;
31 final(a,b,c);
32 then use c as the hash value. If you have a variable length array of
33 4-byte integers to hash, use hashword(). If you have a byte array (like
34 a character string), use hashlittle(). If you have several byte arrays, or
35 a mix of things, see the comments above hashlittle().
37 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
38 then mix those integers. This is fast (you can do a lot more thorough
41 -------------------------------------------------------------------------------
44 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
47 -------------------------------------------------------------------------------
48 mix -- mix 3 32-bit values reversibly.
50 This is reversible, so any information in (a,b,c) before mix() is
51 still in (a,b,c) after mix().
53 If four pairs of (a,b,c) inputs are run through mix(), or through
58 of top bits of (a,b,c), or in any combination of bottom bits of
59 (a,b,c).
60 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
61 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
62 is commonly produced by subtraction) look like a single 1-bit
65 all zero plus a counter that starts at zero.
67 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
73 for "differ" defined as + with a one-bit base and a two-bit delta. I
77 This does not achieve avalanche. There are input bits of (a,b,c)
78 that fail to affect some output bits of (a,b,c), especially of a. The
79 most thoroughly mixed value is c, but it doesn't really even achieve
80 avalanche in c.
82 This allows some parallelism. Read-after-writes are good at doubling
88 -------------------------------------------------------------------------------
90 #define mix(a,b,c) \ argument
92 a -= c; a ^= rot(c, 4); c += b; \
93 b -= a; b ^= rot(a, 6); a += c; \
94 c -= b; c ^= rot(b, 8); b += a; \
95 a -= c; a ^= rot(c,16); c += b; \
96 b -= a; b ^= rot(a,19); a += c; \
97 c -= b; c ^= rot(b, 4); b += a; \
101 -------------------------------------------------------------------------------
102 final -- final mixing of 3 32-bit values (a,b,c) into c
104 Pairs of (a,b,c) values differing in only a few bits will usually
105 produce values of c that look totally different. This was tested for
107 of top bits of (a,b,c), or in any combination of bottom bits of
108 (a,b,c).
109 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
110 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
111 is commonly produced by subtraction) look like a single 1-bit
114 all zero plus a counter that starts at zero.
123 -------------------------------------------------------------------------------
125 #define final(a,b,c) \ argument
127 c ^= b; c -= rot(b,14); \
128 a ^= c; a -= rot(c,11); \
129 b ^= a; b -= rot(a,25); \
130 c ^= b; c -= rot(b,16); \
131 a ^= c; a -= rot(c,4); \
132 b ^= a; b -= rot(a,14); \
133 c ^= b; c -= rot(b,24); \
137 --------------------------------------------------------------------
139 -- that the key be an array of uint32_t's, and
140 -- that the length be the number of uint32_t's in the key
142 The function hashword() is identical to hashlittle() on little-endian
143 machines, and identical to hashbig() on big-endian machines,
147 --------------------------------------------------------------------
154 uint32_t a,b,c; in jenkins_hash32() local
157 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; in jenkins_hash32()
159 /*------------------------------------------------- handle most of the key */ in jenkins_hash32()
162 a += k[0]; in jenkins_hash32()
164 c += k[2]; in jenkins_hash32()
165 mix(a,b,c); in jenkins_hash32()
166 length -= 3; in jenkins_hash32()
170 /*------------------------------------------- handle the last 3 uint32_t's */ in jenkins_hash32()
173 case 3 : c+=k[2]; in jenkins_hash32()
175 case 1 : a+=k[0]; in jenkins_hash32()
176 final(a,b,c); in jenkins_hash32()
180 /*------------------------------------------------------ report the result */ in jenkins_hash32()
181 return c; in jenkins_hash32()
186 -------------------------------------------------------------------------------
187 hashlittle() -- hash a variable-length key into a 32-bit value
188 k : the key (the unaligned variable-length array of bytes)
190 initval : can be any 4-byte value
191 Returns a 32-bit value. Every bit of the key affects every bit of
196 mod a prime (mod is sooo slow!). If you need less than 32 bits,
197 use a bitmask. For example, if you need only 10 bits, do
209 -------------------------------------------------------------------------------
214 uint32_t a,b,c; /* internal state */ in jenkins_hash() local
218 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; in jenkins_hash()
222 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ in jenkins_hash()
224 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ in jenkins_hash()
227 a += k[0]; in jenkins_hash()
229 c += k[2]; in jenkins_hash()
230 mix(a,b,c); in jenkins_hash()
231 length -= 12; in jenkins_hash()
235 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
239 * string is aligned, the masked-off tail is in the same word as the in jenkins_hash()
248 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; in jenkins_hash()
249 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; in jenkins_hash()
250 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; in jenkins_hash()
251 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; in jenkins_hash()
252 case 8 : b+=k[1]; a+=k[0]; break; in jenkins_hash()
253 case 7 : b+=k[1]&0xffffff; a+=k[0]; break; in jenkins_hash()
254 case 6 : b+=k[1]&0xffff; a+=k[0]; break; in jenkins_hash()
255 case 5 : b+=k[1]&0xff; a+=k[0]; break; in jenkins_hash()
256 case 4 : a+=k[0]; break; in jenkins_hash()
257 case 3 : a+=k[0]&0xffffff; break; in jenkins_hash()
258 case 2 : a+=k[0]&0xffff; break; in jenkins_hash()
259 case 1 : a+=k[0]&0xff; break; in jenkins_hash()
260 case 0 : return c; /* zero length strings require no mixing */ in jenkins_hash()
264 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ in jenkins_hash()
267 /*--------------- all but last block: aligned reads and different mixing */ in jenkins_hash()
270 a += k[0] + (((uint32_t)k[1])<<16); in jenkins_hash()
272 c += k[4] + (((uint32_t)k[5])<<16); in jenkins_hash()
273 mix(a,b,c); in jenkins_hash()
274 length -= 12; in jenkins_hash()
278 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
282 case 12: c+=k[4]+(((uint32_t)k[5])<<16); in jenkins_hash()
284 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
286 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ in jenkins_hash()
287 case 10: c+=k[4]; in jenkins_hash()
289 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
291 case 9 : c+=k8[8]; /* fall through */ in jenkins_hash()
293 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
297 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
300 case 4 : a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
302 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ in jenkins_hash()
303 case 2 : a+=k[0]; in jenkins_hash()
305 case 1 : a+=k8[0]; in jenkins_hash()
307 case 0 : return c; /* zero length requires no mixing */ in jenkins_hash()
310 } else { /* need to read the key one byte at a time */ in jenkins_hash()
313 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ in jenkins_hash()
316 a += k[0]; in jenkins_hash()
317 a += ((uint32_t)k[1])<<8; in jenkins_hash()
318 a += ((uint32_t)k[2])<<16; in jenkins_hash()
319 a += ((uint32_t)k[3])<<24; in jenkins_hash()
324 c += k[8]; in jenkins_hash()
325 c += ((uint32_t)k[9])<<8; in jenkins_hash()
326 c += ((uint32_t)k[10])<<16; in jenkins_hash()
327 c += ((uint32_t)k[11])<<24; in jenkins_hash()
328 mix(a,b,c); in jenkins_hash()
329 length -= 12; in jenkins_hash()
333 /*-------------------------------- last block: affect all 32 bits of (c) */ in jenkins_hash()
336 case 12: c+=((uint32_t)k[11])<<24; in jenkins_hash()
337 case 11: c+=((uint32_t)k[10])<<16; in jenkins_hash()
338 case 10: c+=((uint32_t)k[9])<<8; in jenkins_hash()
339 case 9 : c+=k[8]; in jenkins_hash()
344 case 4 : a+=((uint32_t)k[3])<<24; in jenkins_hash()
345 case 3 : a+=((uint32_t)k[2])<<16; in jenkins_hash()
346 case 2 : a+=((uint32_t)k[1])<<8; in jenkins_hash()
347 case 1 : a+=k[0]; in jenkins_hash()
349 case 0 : return c; in jenkins_hash()
353 final(a,b,c); in jenkins_hash()
354 return c; in jenkins_hash()
361 * This is the same as hashword() on big-endian machines. It is different
363 * big-endian byte ordering.
367 uint32_t a,b,c; in jenkins_hash() local
371 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; in jenkins_hash()
375 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ in jenkins_hash()
377 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ in jenkins_hash()
380 a += k[0]; in jenkins_hash()
382 c += k[2]; in jenkins_hash()
383 mix(a,b,c); in jenkins_hash()
384 length -= 12; in jenkins_hash()
388 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
401 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; in jenkins_hash()
402 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; in jenkins_hash()
403 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; in jenkins_hash()
404 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; in jenkins_hash()
405 case 8 : b+=k[1]; a+=k[0]; break; in jenkins_hash()
406 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; in jenkins_hash()
407 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; in jenkins_hash()
408 case 5 : b+=k[1]&0xff000000; a+=k[0]; break; in jenkins_hash()
409 case 4 : a+=k[0]; break; in jenkins_hash()
410 case 3 : a+=k[0]&0xffffff00; break; in jenkins_hash()
411 case 2 : a+=k[0]&0xffff0000; break; in jenkins_hash()
412 case 1 : a+=k[0]&0xff000000; break; in jenkins_hash()
413 case 0 : return c; /* zero length strings require no mixing */ in jenkins_hash()
416 } else { /* need to read the key one byte at a time */ in jenkins_hash()
419 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ in jenkins_hash()
422 a += ((uint32_t)k[0])<<24; in jenkins_hash()
423 a += ((uint32_t)k[1])<<16; in jenkins_hash()
424 a += ((uint32_t)k[2])<<8; in jenkins_hash()
425 a += ((uint32_t)k[3]); in jenkins_hash()
430 c += ((uint32_t)k[8])<<24; in jenkins_hash()
431 c += ((uint32_t)k[9])<<16; in jenkins_hash()
432 c += ((uint32_t)k[10])<<8; in jenkins_hash()
433 c += ((uint32_t)k[11]); in jenkins_hash()
434 mix(a,b,c); in jenkins_hash()
435 length -= 12; in jenkins_hash()
439 /*-------------------------------- last block: affect all 32 bits of (c) */ in jenkins_hash()
442 case 12: c+=k[11]; in jenkins_hash()
443 case 11: c+=((uint32_t)k[10])<<8; in jenkins_hash()
444 case 10: c+=((uint32_t)k[9])<<16; in jenkins_hash()
445 case 9 : c+=((uint32_t)k[8])<<24; in jenkins_hash()
450 case 4 : a+=k[3]; in jenkins_hash()
451 case 3 : a+=((uint32_t)k[2])<<8; in jenkins_hash()
452 case 2 : a+=((uint32_t)k[1])<<16; in jenkins_hash()
453 case 1 : a+=((uint32_t)k[0])<<24; in jenkins_hash()
455 case 0 : return c; in jenkins_hash()
459 final(a,b,c); in jenkins_hash()
460 return c; in jenkins_hash()