hash.h revision e6b7aa4a609d4b514d772ee4a1340778a195f6f7 
1/*
2 * The following hash function is based on MurmurHash3, placed into the public
3 * domain by Austin Appleby.  See http://code.google.com/p/smhasher/ for
4 * details.
5 */
6/******************************************************************************/
7#ifdef JEMALLOC_H_TYPES
8
9#endif /* JEMALLOC_H_TYPES */
10/******************************************************************************/
11#ifdef JEMALLOC_H_STRUCTS
12
13#endif /* JEMALLOC_H_STRUCTS */
14/******************************************************************************/
15#ifdef JEMALLOC_H_EXTERNS
16
17#endif /* JEMALLOC_H_EXTERNS */
18/******************************************************************************/
19#ifdef JEMALLOC_H_INLINES
20
21#ifndef JEMALLOC_ENABLE_INLINE
22void	hash(const void *key, size_t len, const uint32_t seed,
23    size_t r_hash[2]);
24#endif
25
26#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_))
27/******************************************************************************/
28/* Internal implementation. */
29JEMALLOC_INLINE uint32_t
30hash_rotl_32(uint32_t x, int8_t r)
31{
32
33	return (x << r) | (x >> (32 - r));
34}
35
36JEMALLOC_INLINE uint64_t
37hash_rotl_64(uint64_t x, int8_t r)
38{
39	return (x << r) | (x >> (64 - r));
40}
41
42JEMALLOC_INLINE uint32_t
43hash_get_block_32(const uint32_t *p, int i)
44{
45
46	return (p[i]);
47}
48
49JEMALLOC_INLINE uint64_t
50hash_get_block_64(const uint64_t *p, int i)
51{
52
53	return (p[i]);
54}
55
56JEMALLOC_INLINE uint32_t
57hash_fmix_32(uint32_t h)
58{
59
60	h ^= h >> 16;
61	h *= 0x85ebca6b;
62	h ^= h >> 13;
63	h *= 0xc2b2ae35;
64	h ^= h >> 16;
65
66	return (h);
67}
68
69JEMALLOC_INLINE uint64_t
70hash_fmix_64(uint64_t k)
71{
72
73	k ^= k >> 33;
74	k *= QU(0xff51afd7ed558ccdLLU);
75	k ^= k >> 33;
76	k *= QU(0xc4ceb9fe1a85ec53LLU);
77	k ^= k >> 33;
78
79	return (k);
80}
81
82JEMALLOC_INLINE uint32_t
83hash_x86_32(const void *key, int len, uint32_t seed)
84{
85	const uint8_t *data = (const uint8_t *) key;
86	const int nblocks = len / 4;
87
88	uint32_t h1 = seed;
89
90	const uint32_t c1 = 0xcc9e2d51;
91	const uint32_t c2 = 0x1b873593;
92
93	/* body */
94	{
95		const uint32_t *blocks = (const uint32_t *) (data + nblocks*4);
96		int i;
97
98		for (i = -nblocks; i; i++) {
99			uint32_t k1 = hash_get_block_32(blocks, i);
100
101			k1 *= c1;
102			k1 = hash_rotl_32(k1, 15);
103			k1 *= c2;
104
105			h1 ^= k1;
106			h1 = hash_rotl_32(h1, 13);
107			h1 = h1*5 + 0xe6546b64;
108		}
109	}
110
111	/* tail */
112	{
113		const uint8_t *tail = (const uint8_t *) (data + nblocks*4);
114
115		uint32_t k1 = 0;
116
117		switch (len & 3) {
118		case 3: k1 ^= tail[2] << 16;
119		case 2: k1 ^= tail[1] << 8;
120		case 1: k1 ^= tail[0]; k1 *= c1; k1 = hash_rotl_32(k1, 15);
121			k1 *= c2; h1 ^= k1;
122		}
123	}
124
125	/* finalization */
126	h1 ^= len;
127
128	h1 = hash_fmix_32(h1);
129
130	return (h1);
131}
132
133UNUSED JEMALLOC_INLINE void
134hash_x86_128(const void *key, const int len, uint32_t seed,
135  uint64_t r_out[2])
136{
137	const uint8_t * data = (const uint8_t *) key;
138	const int nblocks = len / 16;
139
140	uint32_t h1 = seed;
141	uint32_t h2 = seed;
142	uint32_t h3 = seed;
143	uint32_t h4 = seed;
144
145	const uint32_t c1 = 0x239b961b;
146	const uint32_t c2 = 0xab0e9789;
147	const uint32_t c3 = 0x38b34ae5;
148	const uint32_t c4 = 0xa1e38b93;
149
150	/* body */
151	{
152		const uint32_t *blocks = (const uint32_t *) (data + nblocks*16);
153		int i;
154
155		for (i = -nblocks; i; i++) {
156			uint32_t k1 = hash_get_block_32(blocks, i*4 + 0);
157			uint32_t k2 = hash_get_block_32(blocks, i*4 + 1);
158			uint32_t k3 = hash_get_block_32(blocks, i*4 + 2);
159			uint32_t k4 = hash_get_block_32(blocks, i*4 + 3);
160
161			k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1;
162
163			h1 = hash_rotl_32(h1, 19); h1 += h2;
164			h1 = h1*5 + 0x561ccd1b;
165
166			k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2;
167
168			h2 = hash_rotl_32(h2, 17); h2 += h3;
169			h2 = h2*5 + 0x0bcaa747;
170
171			k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3;
172
173			h3 = hash_rotl_32(h3, 15); h3 += h4;
174			h3 = h3*5 + 0x96cd1c35;
175
176			k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4;
177
178			h4 = hash_rotl_32(h4, 13); h4 += h1;
179			h4 = h4*5 + 0x32ac3b17;
180		}
181	}
182
183	/* tail */
184	{
185		const uint8_t *tail = (const uint8_t *) (data + nblocks*16);
186		uint32_t k1 = 0;
187		uint32_t k2 = 0;
188		uint32_t k3 = 0;
189		uint32_t k4 = 0;
190
191		switch (len & 15) {
192		case 15: k4 ^= tail[14] << 16;
193		case 14: k4 ^= tail[13] << 8;
194		case 13: k4 ^= tail[12] << 0;
195			k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4;
196
197		case 12: k3 ^= tail[11] << 24;
198		case 11: k3 ^= tail[10] << 16;
199		case 10: k3 ^= tail[ 9] << 8;
200		case  9: k3 ^= tail[ 8] << 0;
201		     k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3;
202
203		case  8: k2 ^= tail[ 7] << 24;
204		case  7: k2 ^= tail[ 6] << 16;
205		case  6: k2 ^= tail[ 5] << 8;
206		case  5: k2 ^= tail[ 4] << 0;
207			k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2;
208
209		case  4: k1 ^= tail[ 3] << 24;
210		case  3: k1 ^= tail[ 2] << 16;
211		case  2: k1 ^= tail[ 1] << 8;
212		case  1: k1 ^= tail[ 0] << 0;
213			k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1;
214		}
215	}
216
217	/* finalization */
218	h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
219
220	h1 += h2; h1 += h3; h1 += h4;
221	h2 += h1; h3 += h1; h4 += h1;
222
223	h1 = hash_fmix_32(h1);
224	h2 = hash_fmix_32(h2);
225	h3 = hash_fmix_32(h3);
226	h4 = hash_fmix_32(h4);
227
228	h1 += h2; h1 += h3; h1 += h4;
229	h2 += h1; h3 += h1; h4 += h1;
230
231	r_out[0] = (((uint64_t) h2) << 32) | h1;
232	r_out[1] = (((uint64_t) h4) << 32) | h3;
233}
234
235UNUSED JEMALLOC_INLINE void
236hash_x64_128(const void *key, const int len, const uint32_t seed,
237  uint64_t r_out[2])
238{
239	const uint8_t *data = (const uint8_t *) key;
240	const int nblocks = len / 16;
241
242	uint64_t h1 = seed;
243	uint64_t h2 = seed;
244
245	const uint64_t c1 = QU(0x87c37b91114253d5LLU);
246	const uint64_t c2 = QU(0x4cf5ad432745937fLLU);
247
248	/* body */
249	{
250		const uint64_t *blocks = (const uint64_t *) (data);
251		int i;
252
253		for (i = 0; i < nblocks; i++) {
254			uint64_t k1 = hash_get_block_64(blocks, i*2 + 0);
255			uint64_t k2 = hash_get_block_64(blocks, i*2 + 1);
256
257			k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1;
258
259			h1 = hash_rotl_64(h1, 27); h1 += h2;
260			h1 = h1*5 + 0x52dce729;
261
262			k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2;
263
264			h2 = hash_rotl_64(h2, 31); h2 += h1;
265			h2 = h2*5 + 0x38495ab5;
266		}
267	}
268
269	/* tail */
270	{
271		const uint8_t *tail = (const uint8_t*)(data + nblocks*16);
272		uint64_t k1 = 0;
273		uint64_t k2 = 0;
274
275		switch (len & 15) {
276		case 15: k2 ^= ((uint64_t)(tail[14])) << 48;
277		case 14: k2 ^= ((uint64_t)(tail[13])) << 40;
278		case 13: k2 ^= ((uint64_t)(tail[12])) << 32;
279		case 12: k2 ^= ((uint64_t)(tail[11])) << 24;
280		case 11: k2 ^= ((uint64_t)(tail[10])) << 16;
281		case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8;
282		case  9: k2 ^= ((uint64_t)(tail[ 8])) << 0;
283			k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2;
284
285		case  8: k1 ^= ((uint64_t)(tail[ 7])) << 56;
286		case  7: k1 ^= ((uint64_t)(tail[ 6])) << 48;
287		case  6: k1 ^= ((uint64_t)(tail[ 5])) << 40;
288		case  5: k1 ^= ((uint64_t)(tail[ 4])) << 32;
289		case  4: k1 ^= ((uint64_t)(tail[ 3])) << 24;
290		case  3: k1 ^= ((uint64_t)(tail[ 2])) << 16;
291		case  2: k1 ^= ((uint64_t)(tail[ 1])) << 8;
292		case  1: k1 ^= ((uint64_t)(tail[ 0])) << 0;
293			k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1;
294		}
295	}
296
297	/* finalization */
298	h1 ^= len; h2 ^= len;
299
300	h1 += h2;
301	h2 += h1;
302
303	h1 = hash_fmix_64(h1);
304	h2 = hash_fmix_64(h2);
305
306	h1 += h2;
307	h2 += h1;
308
309	r_out[0] = h1;
310	r_out[1] = h2;
311}
312
313/******************************************************************************/
314/* API. */
315JEMALLOC_INLINE void
316hash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2])
317{
318#if (LG_SIZEOF_PTR == 3)
319	hash_x64_128(key, len, seed, (uint64_t *)r_hash);
320#else
321	uint64_t hashes[2];
322	hash_x86_128(key, len, seed, hashes);
323	r_hash[0] = (size_t)hashes[0];
324	r_hash[1] = (size_t)hashes[1];
325#endif
326}
327#endif
328
329#endif /* JEMALLOC_H_INLINES */
330/******************************************************************************/
331