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