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