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