Branch data 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 : :
12 : : //-----------------------------------------------------------------------------
13 : : // Platform-specific functions and macros
14 : :
15 : : #define FORCE_INLINE inline __attribute__((always_inline))
16 : :
17 : 1136966 : static inline uint32_t rotl32 ( uint32_t x, int8_t r )
18 : : {
19 : 1136966 : return (x << r) | (x >> (32 - r));
20 : : }
21 : :
22 : 58720000 : static inline uint64_t rotl64 ( uint64_t x, int8_t r )
23 : : {
24 : 58720000 : return (x << r) | (x >> (64 - r));
25 : : }
26 : :
27 : : #define ROTL32(x,y) rotl32(x,y)
28 : : #define ROTL64(x,y) rotl64(x,y)
29 : :
30 : : #define BIG_CONSTANT(x) (x##LLU)
31 : :
32 : : //-----------------------------------------------------------------------------
33 : : // Finalization mix - force all bits of a hash block to avalanche
34 : :
35 : : FORCE_INLINE uint32_t fmix32 ( uint32_t h )
36 : : {
37 : 237564 : h ^= h >> 16;
38 : 237564 : h *= 0x85ebca6b;
39 : 237564 : h ^= h >> 13;
40 : 237564 : h *= 0xc2b2ae35;
41 : 237564 : h ^= h >> 16;
42 : :
43 : 237564 : return h;
44 : : }
45 : :
46 : : //----------
47 : :
48 : : FORCE_INLINE uint64_t fmix64 ( uint64_t k )
49 : : {
50 : 79480800 : k ^= k >> 33;
51 : 79480800 : k *= BIG_CONSTANT(0xff51afd7ed558ccd);
52 : 79480800 : k ^= k >> 33;
53 : 79480800 : k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
54 : 79480800 : k ^= k >> 33;
55 : :
56 : 79480800 : return k;
57 : : }
58 : :
59 : : //-----------------------------------------------------------------------------
60 : :
61 : 237564 : void MurmurHash3_x86_32 ( const void * key, int len,
62 : : uint32_t seed, void * out )
63 : : {
64 : 237564 : const uint8_t * data = (const uint8_t*)key;
65 : 237564 : const int nblocks = len / 4;
66 : :
67 : 237564 : uint32_t h1 = seed;
68 : :
69 : 237564 : uint32_t c1 = 0xcc9e2d51;
70 : 237564 : uint32_t c2 = 0x1b873593;
71 : :
72 : : //----------
73 : : // body
74 : :
75 : 237564 : const uint8_t * tail = data + nblocks*4;
76 : :
77 [ + + ]: 722034 : for(int i = -nblocks; i; i++)
78 : : {
79 : 484470 : uint32_t k1 = jl_load_unaligned_i32(tail + sizeof(uint32_t)*i);
80 : :
81 : 484470 : k1 *= c1;
82 : 484470 : k1 = ROTL32(k1,15);
83 : 484470 : k1 *= c2;
84 : :
85 : 484470 : h1 ^= k1;
86 : 484470 : h1 = ROTL32(h1,13);
87 : 484470 : h1 = h1*5+0xe6546b64;
88 : : }
89 : :
90 : : //----------
91 : : // tail
92 : :
93 : 237564 : uint32_t k1 = 0;
94 : :
95 [ + + + + ]: 237564 : switch(len & 3)
96 : : {
97 : 69570 : case 3: k1 ^= tail[2] << 16; JL_FALLTHROUGH;
98 : 120720 : case 2: k1 ^= tail[1] << 8; JL_FALLTHROUGH;
99 : 168026 : case 1: k1 ^= tail[0];
100 : 168026 : k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
101 : : };
102 : :
103 : : //----------
104 : : // finalization
105 : :
106 : 237564 : h1 ^= len;
107 : :
108 : 237564 : h1 = fmix32(h1);
109 : :
110 : 237564 : *(uint32_t*)out = h1;
111 : 237564 : }
112 : :
113 : : //-----------------------------------------------------------------------------
114 : :
115 : 0 : void MurmurHash3_x86_128 ( const void * key, const int len,
116 : : uint32_t seed, void * out )
117 : : {
118 : 0 : const uint8_t * data = (const uint8_t*)key;
119 : 0 : const int nblocks = len / 16;
120 : :
121 : 0 : uint32_t h1 = seed;
122 : 0 : uint32_t h2 = seed;
123 : 0 : uint32_t h3 = seed;
124 : 0 : uint32_t h4 = seed;
125 : :
126 : 0 : uint32_t c1 = 0x239b961b;
127 : 0 : uint32_t c2 = 0xab0e9789;
128 : 0 : uint32_t c3 = 0x38b34ae5;
129 : 0 : uint32_t c4 = 0xa1e38b93;
130 : :
131 : : //----------
132 : : // body
133 : :
134 : 0 : const uint8_t *tail = data + nblocks*16;
135 : :
136 [ # # ]: 0 : for(int i = -nblocks; i; i++)
137 : : {
138 : 0 : uint32_t k1 = jl_load_unaligned_i32(tail + sizeof(uint32_t)*(i*4 + 0));
139 : 0 : uint32_t k2 = jl_load_unaligned_i32(tail + sizeof(uint32_t)*(i*4 + 1));
140 : 0 : uint32_t k3 = jl_load_unaligned_i32(tail + sizeof(uint32_t)*(i*4 + 2));
141 : 0 : uint32_t k4 = jl_load_unaligned_i32(tail + sizeof(uint32_t)*(i*4 + 3));
142 : :
143 : 0 : k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
144 : :
145 : 0 : h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
146 : :
147 : 0 : k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
148 : :
149 : 0 : h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
150 : :
151 : 0 : k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
152 : :
153 : 0 : h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
154 : :
155 : 0 : k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
156 : :
157 : 0 : h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
158 : : }
159 : :
160 : : //----------
161 : : // tail
162 : :
163 : 0 : uint32_t k1 = 0;
164 : 0 : uint32_t k2 = 0;
165 : 0 : uint32_t k3 = 0;
166 : 0 : uint32_t k4 = 0;
167 : :
168 [ # # # # : 0 : switch(len & 15)
# # # # #
# # # # #
# # ]
169 : : {
170 : 0 : case 15: k4 ^= tail[14] << 16; JL_FALLTHROUGH;
171 : 0 : case 14: k4 ^= tail[13] << 8; JL_FALLTHROUGH;
172 : 0 : case 13: k4 ^= tail[12] << 0;
173 : 0 : k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
174 : : JL_FALLTHROUGH;
175 : :
176 : 0 : case 12: k3 ^= tail[11] << 24; JL_FALLTHROUGH;
177 : 0 : case 11: k3 ^= tail[10] << 16; JL_FALLTHROUGH;
178 : 0 : case 10: k3 ^= tail[ 9] << 8; JL_FALLTHROUGH;
179 : 0 : case 9: k3 ^= tail[ 8] << 0;
180 : 0 : k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
181 : : JL_FALLTHROUGH;
182 : :
183 : 0 : case 8: k2 ^= tail[ 7] << 24; JL_FALLTHROUGH;
184 : 0 : case 7: k2 ^= tail[ 6] << 16; JL_FALLTHROUGH;
185 : 0 : case 6: k2 ^= tail[ 5] << 8; JL_FALLTHROUGH;
186 : 0 : case 5: k2 ^= tail[ 4] << 0;
187 : 0 : k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
188 : : JL_FALLTHROUGH;
189 : :
190 : 0 : case 4: k1 ^= tail[ 3] << 24; JL_FALLTHROUGH;
191 : 0 : case 3: k1 ^= tail[ 2] << 16; JL_FALLTHROUGH;
192 : 0 : case 2: k1 ^= tail[ 1] << 8; JL_FALLTHROUGH;
193 : 0 : case 1: k1 ^= tail[ 0] << 0;
194 : 0 : k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
195 : : };
196 : :
197 : : //----------
198 : : // finalization
199 : :
200 : 0 : h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
201 : :
202 : 0 : h1 += h2; h1 += h3; h1 += h4;
203 : 0 : h2 += h1; h3 += h1; h4 += h1;
204 : :
205 : 0 : h1 = fmix32(h1);
206 : 0 : h2 = fmix32(h2);
207 : 0 : h3 = fmix32(h3);
208 : 0 : h4 = fmix32(h4);
209 : :
210 : 0 : h1 += h2; h1 += h3; h1 += h4;
211 : 0 : h2 += h1; h3 += h1; h4 += h1;
212 : :
213 : 0 : ((uint32_t*)out)[0] = h1;
214 : 0 : ((uint32_t*)out)[1] = h2;
215 : 0 : ((uint32_t*)out)[2] = h3;
216 : 0 : ((uint32_t*)out)[3] = h4;
217 : 0 : }
218 : :
219 : : //-----------------------------------------------------------------------------
220 : :
221 : 39740400 : void MurmurHash3_x64_128 ( const void * key, const int len,
222 : : const uint32_t seed, void * out )
223 : : {
224 : 39740400 : const uint8_t * data = (const uint8_t*)key;
225 : 39740400 : const int nblocks = len / 16;
226 : :
227 : 39740400 : uint64_t h1 = seed;
228 : 39740400 : uint64_t h2 = seed;
229 : :
230 : 39740400 : uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
231 : 39740400 : uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
232 : :
233 : : //----------
234 : : // body
235 : :
236 [ + + ]: 43545400 : for(int i = 0; i < nblocks; i++)
237 : : {
238 : 3804940 : uint64_t k1 = jl_load_unaligned_i64(data + sizeof(uint64_t)*(i*2 + 0));
239 : 3804940 : uint64_t k2 = jl_load_unaligned_i64(data + sizeof(uint64_t)*(i*2 + 1));
240 : :
241 : 3804940 : k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
242 : :
243 : 3804940 : h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
244 : :
245 : 3804940 : k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
246 : :
247 : 3804940 : h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
248 : : }
249 : :
250 : : //----------
251 : : // tail
252 : :
253 : 39740400 : const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
254 : :
255 : 39740400 : uint64_t k1 = 0;
256 : 39740400 : uint64_t k2 = 0;
257 : :
258 [ + + + + : 39740400 : switch(len & 15)
+ + + + +
+ + + + +
+ + ]
259 : : {
260 : 531276 : case 15: k2 ^= ((uint64_t)(tail[14])) << 48; JL_FALLTHROUGH;
261 : 919168 : case 14: k2 ^= ((uint64_t)(tail[13])) << 40; JL_FALLTHROUGH;
262 : 1323910 : case 13: k2 ^= ((uint64_t)(tail[12])) << 32; JL_FALLTHROUGH;
263 : 1741884 : case 12: k2 ^= ((uint64_t)(tail[11])) << 24; JL_FALLTHROUGH;
264 : 2398160 : case 11: k2 ^= ((uint64_t)(tail[10])) << 16; JL_FALLTHROUGH;
265 : 3828420 : case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; JL_FALLTHROUGH;
266 : 4654600 : case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0;
267 : 4654600 : k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
268 : : JL_FALLTHROUGH;
269 : :
270 : 7040820 : case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; JL_FALLTHROUGH;
271 : 8487960 : case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; JL_FALLTHROUGH;
272 : 13155760 : case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; JL_FALLTHROUGH;
273 : 17192920 : case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; JL_FALLTHROUGH;
274 : 28753000 : case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; JL_FALLTHROUGH;
275 : 31350200 : case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; JL_FALLTHROUGH;
276 : 33133800 : case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; JL_FALLTHROUGH;
277 : 38845600 : case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0;
278 : 38845600 : k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
279 : : };
280 : :
281 : : //----------
282 : : // finalization
283 : :
284 : 39740400 : h1 ^= len; h2 ^= len;
285 : :
286 : 39740400 : h1 += h2;
287 : 39740400 : h2 += h1;
288 : :
289 : 39740400 : h1 = fmix64(h1);
290 : 39740400 : h2 = fmix64(h2);
291 : :
292 : 39740400 : h1 += h2;
293 : 39740400 : h2 += h1;
294 : :
295 : 39740400 : ((uint64_t*)out)[0] = h1;
296 : 39740400 : ((uint64_t*)out)[1] = h2;
297 : 39740400 : }
298 : :
299 : : //-----------------------------------------------------------------------------
|
