1 #ifndef JEMALLOC_INTERNAL_HASH_INLINES_H
2 #define JEMALLOC_INTERNAL_HASH_INLINES_H
3
4 /*
5 * The following hash function is based on MurmurHash3, placed into the public
6 * domain by Austin Appleby. See https://github.com/aappleby/smhasher for
7 * details.
8 */
9
10 #ifndef JEMALLOC_ENABLE_INLINE
11 uint32_t hash_x86_32(const void *key, int len, uint32_t seed);
12 void hash_x86_128(const void *key, const int len, uint32_t seed,
13 uint64_t r_out[2]);
14 void hash_x64_128(const void *key, const int len, const uint32_t seed,
15 uint64_t r_out[2]);
16 void hash(const void *key, size_t len, const uint32_t seed,
17 size_t r_hash[2]);
18 #endif
19
20 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_))
21 /******************************************************************************/
22 /* Internal implementation. */
23 JEMALLOC_INLINE uint32_t
hash_rotl_32(uint32_t x,int8_t r)24 hash_rotl_32(uint32_t x, int8_t r)
25 {
26 return ((x << r) | (x >> (32 - r)));
27 }
28
29 JEMALLOC_INLINE uint64_t
hash_rotl_64(uint64_t x,int8_t r)30 hash_rotl_64(uint64_t x, int8_t r)
31 {
32 return ((x << r) | (x >> (64 - r)));
33 }
34
35 JEMALLOC_INLINE uint32_t
hash_get_block_32(const uint32_t * p,int i)36 hash_get_block_32(const uint32_t *p, int i)
37 {
38 /* Handle unaligned read. */
39 if (unlikely((uintptr_t)p & (sizeof(uint32_t)-1)) != 0) {
40 uint32_t ret;
41
42 memcpy(&ret, (uint8_t *)(p + i), sizeof(uint32_t));
43 return (ret);
44 }
45
46 return (p[i]);
47 }
48
49 JEMALLOC_INLINE uint64_t
hash_get_block_64(const uint64_t * p,int i)50 hash_get_block_64(const uint64_t *p, int i)
51 {
52 /* Handle unaligned read. */
53 if (unlikely((uintptr_t)p & (sizeof(uint64_t)-1)) != 0) {
54 uint64_t ret;
55
56 memcpy(&ret, (uint8_t *)(p + i), sizeof(uint64_t));
57 return (ret);
58 }
59
60 return (p[i]);
61 }
62
63 JEMALLOC_INLINE uint32_t
hash_fmix_32(uint32_t h)64 hash_fmix_32(uint32_t h)
65 {
66 h ^= h >> 16;
67 h *= 0x85ebca6b;
68 h ^= h >> 13;
69 h *= 0xc2b2ae35;
70 h ^= h >> 16;
71
72 return (h);
73 }
74
75 JEMALLOC_INLINE uint64_t
hash_fmix_64(uint64_t k)76 hash_fmix_64(uint64_t k)
77 {
78 k ^= k >> 33;
79 k *= KQU(0xff51afd7ed558ccd);
80 k ^= k >> 33;
81 k *= KQU(0xc4ceb9fe1a85ec53);
82 k ^= k >> 33;
83
84 return (k);
85 }
86
87 JEMALLOC_INLINE uint32_t
hash_x86_32(const void * key,int len,uint32_t seed)88 hash_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
138 UNUSED JEMALLOC_INLINE void
hash_x86_128(const void * key,const int len,uint32_t seed,uint64_t r_out[2])139 hash_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
240 UNUSED JEMALLOC_INLINE void
hash_x64_128(const void * key,const int len,const uint32_t seed,uint64_t r_out[2])241 hash_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 = KQU(0x87c37b91114253d5);
251 const uint64_t c2 = KQU(0x4cf5ad432745937f);
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. */
320 JEMALLOC_INLINE void
hash(const void * key,size_t len,const uint32_t seed,size_t r_hash[2])321 hash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2])
322 {
323 assert(len <= INT_MAX); /* Unfortunate implementation limitation. */
324
325 #if (LG_SIZEOF_PTR == 3 && !defined(JEMALLOC_BIG_ENDIAN))
326 hash_x64_128(key, (int)len, seed, (uint64_t *)r_hash);
327 #else
328 {
329 uint64_t hashes[2];
330 hash_x86_128(key, (int)len, seed, hashes);
331 r_hash[0] = (size_t)hashes[0];
332 r_hash[1] = (size_t)hashes[1];
333 }
334 #endif
335 }
336 #endif
337
338 #endif /* JEMALLOC_INTERNAL_HASH_INLINES_H */
339