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