1
/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
5
* The hash function used here is by Bob Jenkins, 1996:
6
* <http://burtleburtle.net/bob/hash/doobs.html>
7
* "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net.
8
* You may use this code any way you wish, private, educational,
9
* or commercial. It's free."
12
#include "memcached.h"
15
* Since the hash function does bit manipulation, it needs to know
16
* whether it's big or little-endian. ENDIAN_LITTLE and ENDIAN_BIG
17
* are set in the configure script.
19
#if defined(ENDIAN_BIG) && ENDIAN_BIG == 1
20
# define HASH_LITTLE_ENDIAN 0
21
# define HASH_BIG_ENDIAN 1
23
# if defined(ENDIAN_LITTLE) && ENDIAN_LITTLE == 1
24
# define HASH_LITTLE_ENDIAN 1
25
# define HASH_BIG_ENDIAN 0
27
# define HASH_LITTLE_ENDIAN 0
28
# define HASH_BIG_ENDIAN 0
32
#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
35
-------------------------------------------------------------------------------
36
mix -- mix 3 32-bit values reversibly.
38
This is reversible, so any information in (a,b,c) before mix() is
39
still in (a,b,c) after mix().
41
If four pairs of (a,b,c) inputs are run through mix(), or through
42
mix() in reverse, there are at least 32 bits of the output that
43
are sometimes the same for one pair and different for another pair.
45
* pairs that differed by one bit, by two bits, in any combination
46
of top bits of (a,b,c), or in any combination of bottom bits of
48
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
49
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
50
is commonly produced by subtraction) look like a single 1-bit
52
* the base values were pseudorandom, all zero but one bit set, or
53
all zero plus a counter that starts at zero.
55
Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
60
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
61
for "differ" defined as + with a one-bit base and a two-bit delta. I
62
used http://burtleburtle.net/bob/hash/avalanche.html to choose
63
the operations, constants, and arrangements of the variables.
65
This does not achieve avalanche. There are input bits of (a,b,c)
66
that fail to affect some output bits of (a,b,c), especially of a. The
67
most thoroughly mixed value is c, but it doesn't really even achieve
70
This allows some parallelism. Read-after-writes are good at doubling
71
the number of bits affected, so the goal of mixing pulls in the opposite
72
direction as the goal of parallelism. I did what I could. Rotates
73
seem to cost as much as shifts on every machine I could lay my hands
74
on, and rotates are much kinder to the top and bottom bits, so I used
76
-------------------------------------------------------------------------------
80
a -= c; a ^= rot(c, 4); c += b; \
81
b -= a; b ^= rot(a, 6); a += c; \
82
c -= b; c ^= rot(b, 8); b += a; \
83
a -= c; a ^= rot(c,16); c += b; \
84
b -= a; b ^= rot(a,19); a += c; \
85
c -= b; c ^= rot(b, 4); b += a; \
89
-------------------------------------------------------------------------------
90
final -- final mixing of 3 32-bit values (a,b,c) into c
92
Pairs of (a,b,c) values differing in only a few bits will usually
93
produce values of c that look totally different. This was tested for
94
* pairs that differed by one bit, by two bits, in any combination
95
of top bits of (a,b,c), or in any combination of bottom bits of
97
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
98
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
99
is commonly produced by subtraction) look like a single 1-bit
101
* the base values were pseudorandom, all zero but one bit set, or
102
all zero plus a counter that starts at zero.
104
These constants passed:
107
and these came close:
111
-------------------------------------------------------------------------------
113
#define final(a,b,c) \
115
c ^= b; c -= rot(b,14); \
116
a ^= c; a -= rot(c,11); \
117
b ^= a; b -= rot(a,25); \
118
c ^= b; c -= rot(b,16); \
119
a ^= c; a -= rot(c,4); \
120
b ^= a; b -= rot(a,14); \
121
c ^= b; c -= rot(b,24); \
124
#if HASH_LITTLE_ENDIAN == 1
126
const void *key, /* the key to hash */
127
size_t length, /* length of the key */
128
const uint32_t initval) /* initval */
130
uint32_t a,b,c; /* internal state */
131
union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
133
/* Set up the internal state */
134
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
137
if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
138
const uint32_t *k = key; /* read 32-bit chunks */
141
#endif /* ifdef VALGRIND */
143
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
154
/*----------------------------- handle the last (probably partial) block */
156
* "k[2]&0xffffff" actually reads beyond the end of the string, but
157
* then masks off the part it's not allowed to read. Because the
158
* string is aligned, the masked-off tail is in the same word as the
159
* rest of the string. Every machine with memory protection I've seen
160
* does it on word boundaries, so is OK with this. But VALGRIND will
161
* still catch it and complain. The masking trick does make the hash
162
* noticably faster for short strings (like English words).
168
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
169
case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
170
case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
171
case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
172
case 8 : b+=k[1]; a+=k[0]; break;
173
case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
174
case 6 : b+=k[1]&0xffff; a+=k[0]; break;
175
case 5 : b+=k[1]&0xff; a+=k[0]; break;
176
case 4 : a+=k[0]; break;
177
case 3 : a+=k[0]&0xffffff; break;
178
case 2 : a+=k[0]&0xffff; break;
179
case 1 : a+=k[0]&0xff; break;
180
case 0 : return c; /* zero length strings require no mixing */
185
#else /* make valgrind happy */
187
k8 = (const uint8_t *)k;
190
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
191
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
192
case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
193
case 9 : c+=k8[8]; /* fall through */
194
case 8 : b+=k[1]; a+=k[0]; break;
195
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
196
case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
197
case 5 : b+=k8[4]; /* fall through */
198
case 4 : a+=k[0]; break;
199
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
200
case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
201
case 1 : a+=k8[0]; break;
202
case 0 : return c; /* zero length strings require no mixing */
205
#endif /* !valgrind */
207
} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
208
const uint16_t *k = key; /* read 16-bit chunks */
211
/*--------------- all but last block: aligned reads and different mixing */
214
a += k[0] + (((uint32_t)k[1])<<16);
215
b += k[2] + (((uint32_t)k[3])<<16);
216
c += k[4] + (((uint32_t)k[5])<<16);
222
/*----------------------------- handle the last (probably partial) block */
223
k8 = (const uint8_t *)k;
226
case 12: c+=k[4]+(((uint32_t)k[5])<<16);
227
b+=k[2]+(((uint32_t)k[3])<<16);
228
a+=k[0]+(((uint32_t)k[1])<<16);
230
case 11: c+=((uint32_t)k8[10])<<16; /* @fallthrough */
231
case 10: c+=k[4]; /* @fallthrough@ */
232
b+=k[2]+(((uint32_t)k[3])<<16);
233
a+=k[0]+(((uint32_t)k[1])<<16);
235
case 9 : c+=k8[8]; /* @fallthrough */
236
case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
237
a+=k[0]+(((uint32_t)k[1])<<16);
239
case 7 : b+=((uint32_t)k8[6])<<16; /* @fallthrough */
241
a+=k[0]+(((uint32_t)k[1])<<16);
243
case 5 : b+=k8[4]; /* @fallthrough */
244
case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
246
case 3 : a+=((uint32_t)k8[2])<<16; /* @fallthrough */
251
case 0 : return c; /* zero length strings require no mixing */
256
} else { /* need to read the key one byte at a time */
257
const uint8_t *k = key;
259
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
263
a += ((uint32_t)k[1])<<8;
264
a += ((uint32_t)k[2])<<16;
265
a += ((uint32_t)k[3])<<24;
267
b += ((uint32_t)k[5])<<8;
268
b += ((uint32_t)k[6])<<16;
269
b += ((uint32_t)k[7])<<24;
271
c += ((uint32_t)k[9])<<8;
272
c += ((uint32_t)k[10])<<16;
273
c += ((uint32_t)k[11])<<24;
279
/*-------------------------------- last block: affect all 32 bits of (c) */
280
switch(length) /* all the case statements fall through */
282
case 12: c+=((uint32_t)k[11])<<24;
283
case 11: c+=((uint32_t)k[10])<<16;
284
case 10: c+=((uint32_t)k[9])<<8;
286
case 8 : b+=((uint32_t)k[7])<<24;
287
case 7 : b+=((uint32_t)k[6])<<16;
288
case 6 : b+=((uint32_t)k[5])<<8;
290
case 4 : a+=((uint32_t)k[3])<<24;
291
case 3 : a+=((uint32_t)k[2])<<16;
292
case 2 : a+=((uint32_t)k[1])<<8;
295
case 0 : return c; /* zero length strings require no mixing */
302
return c; /* zero length strings require no mixing */
305
#elif HASH_BIG_ENDIAN == 1
308
* This is the same as hashword() on big-endian machines. It is different
309
* from hashlittle() on all machines. hashbig() takes advantage of
310
* big-endian byte ordering.
312
uint32_t hash( const void *key, size_t length, const uint32_t initval)
315
union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
317
/* Set up the internal state */
318
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
321
if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
322
const uint32_t *k = key; /* read 32-bit chunks */
325
#endif /* ifdef VALGRIND */
327
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
338
/*----------------------------- handle the last (probably partial) block */
340
* "k[2]<<8" actually reads beyond the end of the string, but
341
* then shifts out the part it's not allowed to read. Because the
342
* string is aligned, the illegal read is in the same word as the
343
* rest of the string. Every machine with memory protection I've seen
344
* does it on word boundaries, so is OK with this. But VALGRIND will
345
* still catch it and complain. The masking trick does make the hash
346
* noticably faster for short strings (like English words).
352
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
353
case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
354
case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
355
case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
356
case 8 : b+=k[1]; a+=k[0]; break;
357
case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
358
case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
359
case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
360
case 4 : a+=k[0]; break;
361
case 3 : a+=k[0]&0xffffff00; break;
362
case 2 : a+=k[0]&0xffff0000; break;
363
case 1 : a+=k[0]&0xff000000; break;
364
case 0 : return c; /* zero length strings require no mixing */
367
#else /* make valgrind happy */
369
k8 = (const uint8_t *)k;
370
switch(length) /* all the case statements fall through */
372
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
373
case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
374
case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
375
case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
376
case 8 : b+=k[1]; a+=k[0]; break;
377
case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
378
case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
379
case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
380
case 4 : a+=k[0]; break;
381
case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
382
case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
383
case 1 : a+=((uint32_t)k8[0])<<24; break;
387
#endif /* !VALGRIND */
389
} else { /* need to read the key one byte at a time */
390
const uint8_t *k = key;
392
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
395
a += ((uint32_t)k[0])<<24;
396
a += ((uint32_t)k[1])<<16;
397
a += ((uint32_t)k[2])<<8;
398
a += ((uint32_t)k[3]);
399
b += ((uint32_t)k[4])<<24;
400
b += ((uint32_t)k[5])<<16;
401
b += ((uint32_t)k[6])<<8;
402
b += ((uint32_t)k[7]);
403
c += ((uint32_t)k[8])<<24;
404
c += ((uint32_t)k[9])<<16;
405
c += ((uint32_t)k[10])<<8;
406
c += ((uint32_t)k[11]);
412
/*-------------------------------- last block: affect all 32 bits of (c) */
413
switch(length) /* all the case statements fall through */
416
case 11: c+=((uint32_t)k[10])<<8;
417
case 10: c+=((uint32_t)k[9])<<16;
418
case 9 : c+=((uint32_t)k[8])<<24;
420
case 7 : b+=((uint32_t)k[6])<<8;
421
case 6 : b+=((uint32_t)k[5])<<16;
422
case 5 : b+=((uint32_t)k[4])<<24;
424
case 3 : a+=((uint32_t)k[2])<<8;
425
case 2 : a+=((uint32_t)k[1])<<16;
426
case 1 : a+=((uint32_t)k[0])<<24;
435
#else /* HASH_XXX_ENDIAN == 1 */
436
#error Must define HASH_BIG_ENDIAN or HASH_LITTLE_ENDIAN
437
#endif /* HASH_XXX_ENDIAN == 1 */
added
removed
memcached/hash.c
