Lines Matching +full:mix +full:- +full:26 +full:k
9 -------------------------------------------------------------------------------
12 These are functions for producing 32-bit hashes for hash table lookup.
13 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
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.
27 mix(a,b,c);
29 mix(a,b,c);
33 4-byte integers to hash, use hashword(). If you have a byte array (like
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)))) argument
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
54 mix() in reverse, there are at least 32 bits of the output that
60 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
62 is commonly produced by subtraction) look like a single 1-bit
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
82 This allows some parallelism. Read-after-writes are good at doubling
88 -------------------------------------------------------------------------------
90 #define mix(a,b,c) \ macro
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
109 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
111 is commonly produced by subtraction) look like a single 1-bit
120 4 8 15 26 3 22 24
121 10 8 15 26 3 22 24
122 11 8 15 26 3 22 24
123 -------------------------------------------------------------------------------
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 --------------------------------------------------------------------
150 const uint32_t *k, /* the key, an array of uint32_t values */ in jenkins_hash32() argument
159 /*------------------------------------------------- handle most of the key */ in jenkins_hash32()
162 a += k[0]; in jenkins_hash32()
163 b += k[1]; in jenkins_hash32()
164 c += k[2]; in jenkins_hash32()
165 mix(a,b,c); in jenkins_hash32()
166 length -= 3; in jenkins_hash32()
167 k += 3; in jenkins_hash32()
170 /*------------------------------------------- handle the last 3 uint32_t's */ in jenkins_hash32()
173 case 3 : c+=k[2]; in jenkins_hash32()
174 case 2 : b+=k[1]; in jenkins_hash32()
175 case 1 : a+=k[0]; in jenkins_hash32()
180 /*------------------------------------------------------ report the result */ 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
201 If you are hashing n strings (uint8_t **)k, do it like this:
202 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
209 -------------------------------------------------------------------------------
222 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ in jenkins_hash() local
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()
228 b += k[1]; in jenkins_hash()
229 c += k[2]; in jenkins_hash()
230 mix(a,b,c); in jenkins_hash()
231 length -= 12; in jenkins_hash()
232 k += 3; in jenkins_hash()
235 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
237 * "k[2]&0xffffff" actually reads beyond the end of the string, but 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()
264 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ in jenkins_hash() local
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()
271 b += k[2] + (((uint32_t)k[3])<<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()
275 k += 6; in jenkins_hash()
278 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
279 k8 = (const uint8_t *)k; in jenkins_hash()
282 case 12: c+=k[4]+(((uint32_t)k[5])<<16); in jenkins_hash()
283 b+=k[2]+(((uint32_t)k[3])<<16); in jenkins_hash()
284 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
287 case 10: c+=k[4]; in jenkins_hash()
288 b+=k[2]+(((uint32_t)k[3])<<16); in jenkins_hash()
289 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
292 case 8 : b+=k[2]+(((uint32_t)k[3])<<16); in jenkins_hash()
293 a+=k[0]+(((uint32_t)k[1])<<16); in jenkins_hash()
296 case 6 : b+=k[2]; 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()
303 case 2 : a+=k[0]; in jenkins_hash()
311 const uint8_t *k = (const uint8_t *)key; in jenkins_hash() local
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()
320 b += k[4]; in jenkins_hash()
321 b += ((uint32_t)k[5])<<8; in jenkins_hash()
322 b += ((uint32_t)k[6])<<16; in jenkins_hash()
323 b += ((uint32_t)k[7])<<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()
330 k += 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()
340 case 8 : b+=((uint32_t)k[7])<<24; in jenkins_hash()
341 case 7 : b+=((uint32_t)k[6])<<16; in jenkins_hash()
342 case 6 : b+=((uint32_t)k[5])<<8; in jenkins_hash()
343 case 5 : b+=k[4]; 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()
361 * This is the same as hashword() on big-endian machines. It is different
363 * big-endian byte ordering.
375 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ in jenkins_hash() local
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()
381 b += k[1]; in jenkins_hash()
382 c += k[2]; in jenkins_hash()
383 mix(a,b,c); in jenkins_hash()
384 length -= 12; in jenkins_hash()
385 k += 3; in jenkins_hash()
388 /*----------------------------- handle the last (probably partial) block */ in jenkins_hash()
390 * "k[2]<<8" actually reads beyond the end of the string, but 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()
417 const uint8_t *k = (const uint8_t *)key; in jenkins_hash() local
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()
426 b += ((uint32_t)k[4])<<24; in jenkins_hash()
427 b += ((uint32_t)k[5])<<16; in jenkins_hash()
428 b += ((uint32_t)k[6])<<8; in jenkins_hash()
429 b += ((uint32_t)k[7]); 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()
436 k += 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()
446 case 8 : b+=k[7]; in jenkins_hash()
447 case 7 : b+=((uint32_t)k[6])<<8; in jenkins_hash()
448 case 6 : b+=((uint32_t)k[5])<<16; in jenkins_hash()
449 case 5 : b+=((uint32_t)k[4])<<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()