Aluode/PerceptionLabPortable
0
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
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#if defined(GNUC) && ((GNUC > 4) || (GNUC == 4 && GNUC_MINOR >= 4))
33
34/* gcc version >= 4.4 4.1 = RHEL 5, 4.4 = RHEL 6.
35 * Don't inline for RHEL 5 gcc which is 4.1 */
36#define FORCE_INLINE attribute((always_inline))
37
38#else
39
40#define FORCE_INLINE
41
42#endif
43
44
45inline uint32_t rotl32 ( uint32_t x, int8_t r )
46{
47 return (x << r) | (x >> (32 - r));
48}
49
50inline uint64_t rotl64 ( uint64_t x, int8_t r )
51{
52 return (x << r) | (x >> (64 - r));
53}
54
55#define ROTL32(x,y) rotl32(x,y)
56#define ROTL64(x,y) rotl64(x,y)
57
58#define BIG_CONSTANT(x) (x##LLU)
59
60#endif // !defined(_MSC_VER)
61
62//-----------------------------------------------------------------------------
63// Block read - if your platform needs to do endian-swapping or can only
64// handle aligned reads, do the conversion here
65
66FORCE_INLINE uint32_t getblock ( const uint32_t * p, int i )
67{
68 return p[i];
69}
70
71FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )
72{
73 return p[i];
74}
75
76//-----------------------------------------------------------------------------
77// Finalization mix - force all bits of a hash block to avalanche
78
79FORCE_INLINE uint32_t fmix ( uint32_t h )
80{
81 h ^= h >> 16;
82 h *= 0x85ebca6b;
83 h ^= h >> 13;
84 h *= 0xc2b2ae35;
85 h ^= h >> 16;
86
87 return h;
88}
89
90//----------
91
92FORCE_INLINE uint64_t fmix ( uint64_t k )
93{
94 k ^= k >> 33;
95 k *= BIG_CONSTANT(0xff51afd7ed558ccd);
96 k ^= k >> 33;
97 k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
98 k ^= k >> 33;
99
100 return k;
101}
102
103//-----------------------------------------------------------------------------
104
105void MurmurHash3_x86_32 ( const void * key, int len,
106 uint32_t seed, void * out )
107{
108 const uint8_t * data = (const uint8_t*)key;
109 const int nblocks = len / 4;
110
111 uint32_t h1 = seed;
112
113 uint32_t c1 = 0xcc9e2d51;
114 uint32_t c2 = 0x1b873593;
115
116 //----------
117 // body
118
119 const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
120
121 for(int i = -nblocks; i; i++)
122 {
123 uint32_t k1 = getblock(blocks,i);
124
125 k1 *= c1;
126 k1 = ROTL32(k1,15);
127 k1 *= c2;
128
129 h1 ^= k1;
130 h1 = ROTL32(h1,13);
131 h1 = h1*5+0xe6546b64;
132 }
133
134 //----------
135 // tail
136
137 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
138
139 uint32_t k1 = 0;
140
141 switch(len & 3)
142 {
143 case 3: k1 ^= tail[2] << 16;
144 case 2: k1 ^= tail[1] << 8;
145 case 1: k1 ^= tail[0];
146 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
147 }
148
149 //----------
150 // finalization
151
152 h1 ^= len;
153
154 h1 = fmix(h1);
155
156 *(uint32_t*)out = h1;
157}
158
159//-----------------------------------------------------------------------------
160
161void MurmurHash3_x86_128 ( const void * key, const int len,
162 uint32_t seed, void * out )
163{
164 const uint8_t * data = (const uint8_t*)key;
165 const int nblocks = len / 16;
166
167 uint32_t h1 = seed;
168 uint32_t h2 = seed;
169 uint32_t h3 = seed;
170 uint32_t h4 = seed;
171
172 uint32_t c1 = 0x239b961b;
173 uint32_t c2 = 0xab0e9789;
174 uint32_t c3 = 0x38b34ae5;
175 uint32_t c4 = 0xa1e38b93;
176
177 //----------
178 // body
179
180 const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
181
182 for(int i = -nblocks; i; i++)
183 {
184 uint32_t k1 = getblock(blocks,i*4+0);
185 uint32_t k2 = getblock(blocks,i*4+1);
186 uint32_t k3 = getblock(blocks,i*4+2);
187 uint32_t k4 = getblock(blocks,i*4+3);
188
189 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
190
191 h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
192
193 k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
194
195 h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
196
197 k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
198
199 h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
200
201 k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
202
203 h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
204 }
205
206 //----------
207 // tail
208
209 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
210
211 uint32_t k1 = 0;
212 uint32_t k2 = 0;
213 uint32_t k3 = 0;
214 uint32_t k4 = 0;
215
216 switch(len & 15)
217 {
218 case 15: k4 ^= tail[14] << 16;
219 case 14: k4 ^= tail[13] << 8;
220 case 13: k4 ^= tail[12] << 0;
221 k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
222
223 case 12: k3 ^= tail[11] << 24;
224 case 11: k3 ^= tail[10] << 16;
225 case 10: k3 ^= tail[ 9] << 8;
226 case 9: k3 ^= tail[ 8] << 0;
227 k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
228
229 case 8: k2 ^= tail[ 7] << 24;
230 case 7: k2 ^= tail[ 6] << 16;
231 case 6: k2 ^= tail[ 5] << 8;
232 case 5: k2 ^= tail[ 4] << 0;
233 k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
234
235 case 4: k1 ^= tail[ 3] << 24;
236 case 3: k1 ^= tail[ 2] << 16;
237 case 2: k1 ^= tail[ 1] << 8;
238 case 1: k1 ^= tail[ 0] << 0;
239 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
240 }
241
242 //----------
243 // finalization
244
245 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
246
247 h1 += h2; h1 += h3; h1 += h4;
248 h2 += h1; h3 += h1; h4 += h1;
249
250 h1 = fmix(h1);
251 h2 = fmix(h2);
252 h3 = fmix(h3);
253 h4 = fmix(h4);
254
255 h1 += h2; h1 += h3; h1 += h4;
256 h2 += h1; h3 += h1; h4 += h1;
257
258 ((uint32_t*)out)[0] = h1;
259 ((uint32_t*)out)[1] = h2;
260 ((uint32_t*)out)[2] = h3;
261 ((uint32_t*)out)[3] = h4;
262}
263
264//-----------------------------------------------------------------------------
265
266void MurmurHash3_x64_128 ( const void * key, const int len,
267 const uint32_t seed, void * out )
268{
269 const uint8_t * data = (const uint8_t*)key;
270 const int nblocks = len / 16;
271
272 uint64_t h1 = seed;
273 uint64_t h2 = seed;
274
275 uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
276 uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
277
278 //----------
279 // body
280
281 const uint64_t * blocks = (const uint64_t *)(data);
282
283 for(int i = 0; i < nblocks; i++)
284 {
285 uint64_t k1 = getblock(blocks,i*2+0);
286 uint64_t k2 = getblock(blocks,i*2+1);
287
288 k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
289
290 h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
291
292 k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
293
294 h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
295 }
296
297 //----------
298 // tail
299
300 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
301
302 uint64_t k1 = 0;
303 uint64_t k2 = 0;
304
305 switch(len & 15)
306 {
307 case 15: k2 ^= uint64_t(tail[14]) << 48;
308 case 14: k2 ^= uint64_t(tail[13]) << 40;
309 case 13: k2 ^= uint64_t(tail[12]) << 32;
310 case 12: k2 ^= uint64_t(tail[11]) << 24;
311 case 11: k2 ^= uint64_t(tail[10]) << 16;
312 case 10: k2 ^= uint64_t(tail[ 9]) << 8;
313 case 9: k2 ^= uint64_t(tail[ 8]) << 0;
314 k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
315
316 case 8: k1 ^= uint64_t(tail[ 7]) << 56;
317 case 7: k1 ^= uint64_t(tail[ 6]) << 48;
318 case 6: k1 ^= uint64_t(tail[ 5]) << 40;
319 case 5: k1 ^= uint64_t(tail[ 4]) << 32;
320 case 4: k1 ^= uint64_t(tail[ 3]) << 24;
321 case 3: k1 ^= uint64_t(tail[ 2]) << 16;
322 case 2: k1 ^= uint64_t(tail[ 1]) << 8;
323 case 1: k1 ^= uint64_t(tail[ 0]) << 0;
324 k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
325 }
326
327 //----------
328 // finalization
329
330 h1 ^= len; h2 ^= len;
331
332 h1 += h2;
333 h2 += h1;
334
335 h1 = fmix(h1);
336 h2 = fmix(h2);
337
338 h1 += h2;
339 h2 += h1;
340
341 ((uint64_t*)out)[0] = h1;
342 ((uint64_t*)out)[1] = h2;
343}
344
345//-----------------------------------------------------------------------------
346