Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
31 namespace { // anonymous
32 
33 inline uint32_t rotl32 ( uint32_t x, int8_t r )
34 {
35  return (x << r) | (x >> (32 - r));
36 }
37 
38 inline 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 
91 namespace Tpetra {
92 namespace Details {
93 
94 void 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 
151 void 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 
257 void 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