Line data Source code
1 : //-----------------------------------------------------------------------------
2 : // MurmurHash3 was written by Austin Appleby, and is placed in the public
3 : // domain. The author hereby disclaims copyright to this source code.
4 :
5 : // Note - The x86 and x64 versions do _not_ produce the same results, as the
6 : // algorithms are optimized for their respective platforms. You can still
7 : // compile and run any of them on any platform, but your performance with the
8 : // non-native version will be less than optimal.
9 :
10 : #include "murmur3.h"
11 :
12 : //-----------------------------------------------------------------------------
13 : // Platform-specific functions and macros
14 :
15 : #ifdef __GNUC__
16 : #define FORCE_INLINE __attribute__((always_inline)) inline
17 : #else
18 : #define FORCE_INLINE inline
19 : #endif
20 :
21 : static FORCE_INLINE uint32_t rotl32(uint32_t x, int8_t r) {
22 24967060 : return (x << r) | (x >> (32 - r));
23 : }
24 :
25 : static FORCE_INLINE uint64_t rotl64(uint64_t x, int8_t r) {
26 22831539 : return (x << r) | (x >> (64 - r));
27 : }
28 :
29 : #define ROTL32(x, y) rotl32(x, y)
30 : #define ROTL64(x, y) rotl64(x, y)
31 :
32 : #define BIG_CONSTANT(x) (x##LLU)
33 :
34 : //-----------------------------------------------------------------------------
35 : // Block read - if your platform needs to do endian-swapping or can only
36 : // handle aligned reads, do the conversion here
37 :
38 : #define getblock(p, i) (p[i])
39 :
40 : //-----------------------------------------------------------------------------
41 : // Finalization mix - force all bits of a hash block to avalanche
42 :
43 : static FORCE_INLINE uint32_t fmix32(uint32_t h) {
44 77896 : h ^= h >> 16;
45 77896 : h *= 0x85ebca6b;
46 77896 : h ^= h >> 13;
47 77896 : h *= 0xc2b2ae35;
48 77896 : h ^= h >> 16;
49 :
50 77896 : return h;
51 : }
52 :
53 : //----------
54 :
55 : static FORCE_INLINE uint64_t fmix64(uint64_t k) {
56 136450 : k ^= k >> 33;
57 136450 : k *= BIG_CONSTANT(0xff51afd7ed558ccd);
58 136450 : k ^= k >> 33;
59 136450 : k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
60 136450 : k ^= k >> 33;
61 :
62 136450 : return k;
63 : }
64 :
65 : //-----------------------------------------------------------------------------
66 :
67 0 : void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out) {
68 0 : const uint8_t *data = (const uint8_t *)key;
69 0 : const int nblocks = len / 4;
70 : int i;
71 :
72 0 : uint32_t h1 = seed;
73 :
74 0 : uint32_t c1 = 0xcc9e2d51;
75 0 : uint32_t c2 = 0x1b873593;
76 :
77 : //----------
78 : // body
79 :
80 0 : const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
81 :
82 0 : for(i = -nblocks; i; i++) {
83 0 : uint32_t k1 = getblock(blocks, i);
84 :
85 0 : k1 *= c1;
86 0 : k1 = ROTL32(k1, 15);
87 0 : k1 *= c2;
88 :
89 0 : h1 ^= k1;
90 0 : h1 = ROTL32(h1, 13);
91 0 : h1 = h1 * 5 + 0xe6546b64;
92 : }
93 :
94 : //----------
95 : // tail
96 :
97 0 : const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
98 :
99 0 : uint32_t k1 = 0;
100 :
101 0 : switch(len & 3) {
102 : case 3:
103 0 : k1 ^= tail[2] << 16;
104 : case 2:
105 0 : k1 ^= tail[1] << 8;
106 : case 1:
107 0 : k1 ^= tail[0];
108 0 : k1 *= c1;
109 0 : k1 = ROTL32(k1, 15);
110 0 : k1 *= c2;
111 0 : h1 ^= k1;
112 : };
113 :
114 : //----------
115 : // finalization
116 :
117 0 : h1 ^= len;
118 :
119 0 : h1 = fmix32(h1);
120 :
121 0 : *(uint32_t *)out = h1;
122 0 : }
123 :
124 : //-----------------------------------------------------------------------------
125 :
126 19474 : void MurmurHash3_x86_128(const void *key, const int len, uint32_t seed, void *out) {
127 19474 : const uint8_t *data = (const uint8_t *)key;
128 19474 : const int nblocks = len / 16;
129 : int i;
130 :
131 19474 : uint32_t h1 = seed;
132 19474 : uint32_t h2 = seed;
133 19474 : uint32_t h3 = seed;
134 19474 : uint32_t h4 = seed;
135 :
136 19474 : uint32_t c1 = 0x239b961b;
137 19474 : uint32_t c2 = 0xab0e9789;
138 19474 : uint32_t c3 = 0x38b34ae5;
139 19474 : uint32_t c4 = 0xa1e38b93;
140 :
141 : //----------
142 : // body
143 :
144 19474 : const uint32_t *blocks = (const uint32_t *)(data + nblocks * 16);
145 :
146 3138431 : for(i = -nblocks; i; i++) {
147 3118957 : uint32_t k1 = getblock(blocks, i * 4 + 0);
148 3118957 : uint32_t k2 = getblock(blocks, i * 4 + 1);
149 3118957 : uint32_t k3 = getblock(blocks, i * 4 + 2);
150 3118957 : uint32_t k4 = getblock(blocks, i * 4 + 3);
151 :
152 3118957 : k1 *= c1;
153 3118957 : k1 = ROTL32(k1, 15);
154 3118957 : k1 *= c2;
155 3118957 : h1 ^= k1;
156 :
157 3118957 : h1 = ROTL32(h1, 19);
158 3118957 : h1 += h2;
159 3118957 : h1 = h1 * 5 + 0x561ccd1b;
160 :
161 3118957 : k2 *= c2;
162 3118957 : k2 = ROTL32(k2, 16);
163 3118957 : k2 *= c3;
164 3118957 : h2 ^= k2;
165 :
166 3118957 : h2 = ROTL32(h2, 17);
167 3118957 : h2 += h3;
168 3118957 : h2 = h2 * 5 + 0x0bcaa747;
169 :
170 3118957 : k3 *= c3;
171 3118957 : k3 = ROTL32(k3, 17);
172 3118957 : k3 *= c4;
173 3118957 : h3 ^= k3;
174 :
175 3118957 : h3 = ROTL32(h3, 15);
176 3118957 : h3 += h4;
177 3118957 : h3 = h3 * 5 + 0x96cd1c35;
178 :
179 3118957 : k4 *= c4;
180 3118957 : k4 = ROTL32(k4, 18);
181 3118957 : k4 *= c1;
182 3118957 : h4 ^= k4;
183 :
184 3118957 : h4 = ROTL32(h4, 13);
185 3118957 : h4 += h1;
186 3118957 : h4 = h4 * 5 + 0x32ac3b17;
187 : }
188 :
189 : //----------
190 : // tail
191 :
192 19474 : const uint8_t *tail = (const uint8_t *)(data + nblocks * 16);
193 :
194 19474 : uint32_t k1 = 0;
195 19474 : uint32_t k2 = 0;
196 19474 : uint32_t k3 = 0;
197 19474 : uint32_t k4 = 0;
198 :
199 19474 : switch(len & 15) {
200 : case 15:
201 0 : k4 ^= tail[14] << 16;
202 : case 14:
203 0 : k4 ^= tail[13] << 8;
204 : case 13:
205 0 : k4 ^= tail[12] << 0;
206 0 : k4 *= c4;
207 0 : k4 = ROTL32(k4, 18);
208 0 : k4 *= c1;
209 0 : h4 ^= k4;
210 :
211 : case 12:
212 0 : k3 ^= tail[11] << 24;
213 : case 11:
214 0 : k3 ^= tail[10] << 16;
215 : case 10:
216 12 : k3 ^= tail[9] << 8;
217 : case 9:
218 12 : k3 ^= tail[8] << 0;
219 12 : k3 *= c3;
220 12 : k3 = ROTL32(k3, 17);
221 12 : k3 *= c4;
222 12 : h3 ^= k3;
223 :
224 : case 8:
225 28 : k2 ^= tail[7] << 24;
226 : case 7:
227 28 : k2 ^= tail[6] << 16;
228 : case 6:
229 28 : k2 ^= tail[5] << 8;
230 : case 5:
231 28 : k2 ^= tail[4] << 0;
232 28 : k2 *= c2;
233 28 : k2 = ROTL32(k2, 16);
234 28 : k2 *= c3;
235 28 : h2 ^= k2;
236 :
237 : case 4:
238 4629 : k1 ^= tail[3] << 24;
239 : case 3:
240 15202 : k1 ^= tail[2] << 16;
241 : case 2:
242 15201 : k1 ^= tail[1] << 8;
243 : case 1:
244 15364 : k1 ^= tail[0] << 0;
245 15364 : k1 *= c1;
246 15364 : k1 = ROTL32(k1, 15);
247 15364 : k1 *= c2;
248 15364 : h1 ^= k1;
249 : };
250 :
251 : //----------
252 : // finalization
253 :
254 19474 : h1 ^= len;
255 19474 : h2 ^= len;
256 19474 : h3 ^= len;
257 19474 : h4 ^= len;
258 :
259 19474 : h1 += h2;
260 19474 : h1 += h3;
261 19474 : h1 += h4;
262 19474 : h2 += h1;
263 19474 : h3 += h1;
264 19474 : h4 += h1;
265 :
266 19474 : h1 = fmix32(h1);
267 19474 : h2 = fmix32(h2);
268 19474 : h3 = fmix32(h3);
269 19474 : h4 = fmix32(h4);
270 :
271 19474 : h1 += h2;
272 19474 : h1 += h3;
273 19474 : h1 += h4;
274 19474 : h2 += h1;
275 19474 : h3 += h1;
276 19474 : h4 += h1;
277 :
278 19474 : ((uint32_t *)out)[0] = h1;
279 19474 : ((uint32_t *)out)[1] = h2;
280 19474 : ((uint32_t *)out)[2] = h3;
281 19474 : ((uint32_t *)out)[3] = h4;
282 19474 : }
283 :
284 : //-----------------------------------------------------------------------------
285 :
286 68225 : void MurmurHash3_x64_128(const void *key, const int len, const uint32_t seed, void *out) {
287 68225 : const uint8_t *data = (const uint8_t *)key;
288 68225 : const int nblocks = len / 16;
289 : int i;
290 :
291 68225 : uint64_t h1 = seed;
292 68225 : uint64_t h2 = seed;
293 :
294 68225 : uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
295 68225 : uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
296 :
297 : //----------
298 : // body
299 :
300 68225 : const uint64_t *blocks = (const uint64_t *)(data);
301 :
302 5762633 : for(i = 0; i < nblocks; i++) {
303 5694408 : uint64_t k1 = getblock(blocks, i * 2 + 0);
304 5694408 : uint64_t k2 = getblock(blocks, i * 2 + 1);
305 :
306 5694408 : k1 *= c1;
307 5694408 : k1 = ROTL64(k1, 31);
308 5694408 : k1 *= c2;
309 5694408 : h1 ^= k1;
310 :
311 5694408 : h1 = ROTL64(h1, 27);
312 5694408 : h1 += h2;
313 5694408 : h1 = h1 * 5 + 0x52dce729;
314 :
315 5694408 : k2 *= c2;
316 5694408 : k2 = ROTL64(k2, 33);
317 5694408 : k2 *= c1;
318 5694408 : h2 ^= k2;
319 :
320 5694408 : h2 = ROTL64(h2, 31);
321 5694408 : h2 += h1;
322 5694408 : h2 = h2 * 5 + 0x38495ab5;
323 : }
324 :
325 : //----------
326 : // tail
327 :
328 68225 : const uint8_t *tail = (const uint8_t *)(data + nblocks * 16);
329 :
330 68225 : uint64_t k1 = 0;
331 68225 : uint64_t k2 = 0;
332 :
333 68225 : switch(len & 15) {
334 : case 15:
335 0 : k2 ^= (uint64_t)(tail[14]) << 48;
336 : case 14:
337 0 : k2 ^= (uint64_t)(tail[13]) << 40;
338 : case 13:
339 0 : k2 ^= (uint64_t)(tail[12]) << 32;
340 : case 12:
341 0 : k2 ^= (uint64_t)(tail[11]) << 24;
342 : case 11:
343 0 : k2 ^= (uint64_t)(tail[10]) << 16;
344 : case 10:
345 49 : k2 ^= (uint64_t)(tail[9]) << 8;
346 : case 9:
347 49 : k2 ^= (uint64_t)(tail[8]) << 0;
348 49 : k2 *= c2;
349 49 : k2 = ROTL64(k2, 33);
350 49 : k2 *= c1;
351 49 : h2 ^= k2;
352 :
353 : case 8:
354 105 : k1 ^= (uint64_t)(tail[7]) << 56;
355 : case 7:
356 105 : k1 ^= (uint64_t)(tail[6]) << 48;
357 : case 6:
358 105 : k1 ^= (uint64_t)(tail[5]) << 40;
359 : case 5:
360 105 : k1 ^= (uint64_t)(tail[4]) << 32;
361 : case 4:
362 16207 : k1 ^= (uint64_t)(tail[3]) << 24;
363 : case 3:
364 53272 : k1 ^= (uint64_t)(tail[2]) << 16;
365 : case 2:
366 53283 : k1 ^= (uint64_t)(tail[1]) << 8;
367 : case 1:
368 53858 : k1 ^= (uint64_t)(tail[0]) << 0;
369 53858 : k1 *= c1;
370 53858 : k1 = ROTL64(k1, 31);
371 53858 : k1 *= c2;
372 53858 : h1 ^= k1;
373 : };
374 :
375 : //----------
376 : // finalization
377 :
378 68225 : h1 ^= len;
379 68225 : h2 ^= len;
380 :
381 68225 : h1 += h2;
382 68225 : h2 += h1;
383 :
384 68225 : h1 = fmix64(h1);
385 68225 : h2 = fmix64(h2);
386 :
387 68225 : h1 += h2;
388 68225 : h2 += h1;
389 :
390 68225 : ((uint64_t *)out)[0] = h1;
391 68225 : ((uint64_t *)out)[1] = h2;
392 68225 : }
393 :
394 : //-----------------------------------------------------------------------------
|
