Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
MurmurHash3.cpp
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.hpp"
11
12//-----------------------------------------------------------------------------
13// Platform-specific functions and macros
14
15// Microsoft Visual Studio
16#if defined(_MSC_VER)
17
18#define FORCE_INLINE __forceinline
19
20#include <stdlib.h>
21
22#define ROTL32(x,y) _rotl(x,y)
23#define ROTL64(x,y) _rotl64(x,y)
24
25#define BIG_CONSTANT(x) (x)
26
27// Other compilers
28
29#else // not defined(_MSC_VER)
30
31namespace { // anonymous
32
33inline uint32_t rotl32 ( uint32_t x, int8_t r )
34{
35 return (x << r) | (x >> (32 - r));
36}
37
38inline uint64_t rotl64 ( uint64_t x, int8_t r )
39{
40 return (x << r) | (x >> (64 - r));
41}
42
43} // namespace (anonymous)
44
45#define ROTL32(x,y) rotl32(x,y)
46#define ROTL64(x,y) rotl64(x,y)
47
48#define BIG_CONSTANT(x) (x##LLU)
49
50#endif // !defined(_MSC_VER)
51
52//-----------------------------------------------------------------------------
53// Block read - if your platform needs to do endian-swapping or can only
54// handle aligned reads, do the conversion here
55
56#define GETBLOCK(lhs, p, i ) \
57{ \
58 lhs = p[(i)];\
59} \
60
61
62//-----------------------------------------------------------------------------
63// Finalization mix - force all bits of a hash block to avalanche
64
65#define FMIX_32( h ) \
66{ \
67 uint32_t t_h = (h); \
68 t_h ^= t_h >> 16; \
69 t_h *= 0x85ebca6b; \
70 t_h ^= t_h >> 13; \
71 t_h *= 0xc2b2ae35; \
72 t_h ^= t_h >> 16; \
73 h = t_h; \
74} \
75
76//----------
77
78#define FMIX_64( k )\
79{\
80 uint64_t t_k = (k);\
81 t_k ^= t_k >> 33;\
82 t_k *= BIG_CONSTANT(0xff51afd7ed558ccd);\
83 t_k ^= t_k >> 33;\
84 t_k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);\
85 t_k ^= t_k >> 33;\
86 k = t_k;\
87}\
88
89//-----------------------------------------------------------------------------
90
91namespace Tpetra {
92namespace Details {
93
94void MurmurHash3_x86_32 ( const void * key, int len,
95 uint32_t seed, void * out )
96{
97 const uint8_t * data = (const uint8_t*)key;
98 const int nblocks = len / 4;
99
100 uint32_t h1 = seed;
101
102 const uint32_t c1 = 0xcc9e2d51;
103 const uint32_t c2 = 0x1b873593;
104
105 //----------
106 // body
107
108 const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
109
110 for(int i = -nblocks; i; i++)
111 {
112 uint32_t k1;
113 GETBLOCK(k1, blocks,i);
114
115 k1 *= c1;
116 k1 = ROTL32(k1,15);
117 k1 *= c2;
118
119 h1 ^= k1;
120 h1 = ROTL32(h1,13);
121 h1 = h1*5+0xe6546b64;
122 }
123
124 //----------
125 // tail
126
127 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
128
129 uint32_t k1 = 0;
130
131 switch(len & 3)
132 {
133 case 3: k1 ^= tail[2] << 16;
134 case 2: k1 ^= tail[1] << 8;
135 case 1: k1 ^= tail[0];
136 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
137 };
138
139 //----------
140 // finalization
141
142 h1 ^= len;
143
144 FMIX_32(h1);
145
146 *(uint32_t*)out = h1;
147}
148
149//-----------------------------------------------------------------------------
150
151void MurmurHash3_x86_128 ( const void * key, const int len,
152 uint32_t seed, void * out )
153{
154 const uint8_t * data = (const uint8_t*)key;
155 const int nblocks = len / 16;
156
157 uint32_t h1 = seed;
158 uint32_t h2 = seed;
159 uint32_t h3 = seed;
160 uint32_t h4 = seed;
161
162 const uint32_t c1 = 0x239b961b;
163 const uint32_t c2 = 0xab0e9789;
164 const uint32_t c3 = 0x38b34ae5;
165 const uint32_t c4 = 0xa1e38b93;
166
167 //----------
168 // body
169
170 const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
171
172 for(int i = -nblocks; i; i++)
173 {
174 uint32_t k1, k2, k3, k4;
175 GETBLOCK(k1, blocks,i*4+0);
176 GETBLOCK(k2, blocks,i*4+1);
177 GETBLOCK(k3, blocks,i*4+2);
178 GETBLOCK(k4, 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 FMIX_32(h1);
242 FMIX_32(h2);
243 FMIX_32(h3);
244 FMIX_32(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, k2;
277 GETBLOCK(k1, blocks,i*2+0);
278 GETBLOCK(k2, blocks,i*2+1);
279
280 k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
281
282 h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
283
284 k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
285
286 h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
287 }
288
289 //----------
290 // tail
291
292 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
293
294 uint64_t k1 = 0;
295 uint64_t k2 = 0;
296
297 switch(len & 15)
298 {
299 case 15: k2 ^= uint64_t(tail[14]) << 48;
300 case 14: k2 ^= uint64_t(tail[13]) << 40;
301 case 13: k2 ^= uint64_t(tail[12]) << 32;
302 case 12: k2 ^= uint64_t(tail[11]) << 24;
303 case 11: k2 ^= uint64_t(tail[10]) << 16;
304 case 10: k2 ^= uint64_t(tail[ 9]) << 8;
305 case 9: k2 ^= uint64_t(tail[ 8]) << 0;
306 k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
307
308 case 8: k1 ^= uint64_t(tail[ 7]) << 56;
309 case 7: k1 ^= uint64_t(tail[ 6]) << 48;
310 case 6: k1 ^= uint64_t(tail[ 5]) << 40;
311 case 5: k1 ^= uint64_t(tail[ 4]) << 32;
312 case 4: k1 ^= uint64_t(tail[ 3]) << 24;
313 case 3: k1 ^= uint64_t(tail[ 2]) << 16;
314 case 2: k1 ^= uint64_t(tail[ 1]) << 8;
315 case 1: k1 ^= uint64_t(tail[ 0]) << 0;
316 k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
317 };
318
319 //----------
320 // finalization
321
322 h1 ^= len; h2 ^= len;
323
324 h1 += h2;
325 h2 += h1;
326
327 FMIX_64(h1);
328 FMIX_64(h2);
329
330 h1 += h2;
331 h2 += h1;
332
333 ((uint64_t*)out)[0] = h1;
334 ((uint64_t*)out)[1] = h2;
335}
336
337} // namespace Details
338} // namespace Tpetra
339
340//-----------------------------------------------------------------------------
341
Implementation details of Tpetra.
Namespace Tpetra contains the class and methods constituting the Tpetra library.