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