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