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