CernVM-FS  2.10.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
murmur.hxx
Go to the documentation of this file.
1 //-----------------------------------------------------------------------------
2 // MurmurHash2 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 - This code makes a few assumptions about how your machine behaves -
6 
7 // 1. We can read a 4-byte value from any address without crashing
8 // 2. sizeof(int) == 4
9 
10 // And it has a few limitations -
11 
12 // 1. It will not work incrementally.
13 // 2. It will not produce the same results on little-endian and big-endian
14 // machines.
15 
16 #ifndef CVMFS_MURMUR_H_
17 #define CVMFS_MURMUR_H_
18 
19 #include <stdint.h>
20 
21 #define BIG_CONSTANT(x) (x##LLU)
22 
23 inline uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
24 {
25  // 'm' and 'r' are mixing constants generated offline.
26  // They're not really 'magic', they just happen to work well.
27 
28  const uint32_t m = 0x5bd1e995;
29  const int r = 24;
30 
31  // Initialize the hash to a 'random' value
32 
33  uint32_t h = seed ^ len;
34 
35  // Mix 4 bytes at a time into the hash
36 
37  const unsigned char * data = (const unsigned char *)key;
38 
39  while(len >= 4)
40  {
41  uint32_t k = *(uint32_t*)data;
42 
43  k *= m;
44  k ^= k >> r;
45  k *= m;
46 
47  h *= m;
48  h ^= k;
49 
50  data += 4;
51  len -= 4;
52  }
53 
54  // Handle the last few bytes of the input array
55 
56  switch(len)
57  {
58  case 3: h ^= data[2] << 16;
59  case 2: h ^= data[1] << 8;
60  case 1: h ^= data[0];
61  h *= m;
62  };
63 
64  // Do a few final mixes of the hash to ensure the last few
65  // bytes are well-incorporated.
66 
67  h ^= h >> 13;
68  h *= m;
69  h ^= h >> 15;
70 
71  return h;
72 }
73 
74 
75 //-----------------------------------------------------------------------------
76 // MurmurHash2, 64-bit versions, by Austin Appleby
77 
78 // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
79 // and endian-ness issues if used across multiple platforms.
80 
81 // 64-bit hash for 64-bit platforms
82 
83 inline uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed )
84 {
85  const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
86  const int r = 47;
87 
88  uint64_t h = seed ^ (len * m);
89 
90  const uint64_t * data = (const uint64_t *)key;
91  const uint64_t * end = data + (len/8);
92 
93  while(data != end)
94  {
95  uint64_t k = *data++;
96 
97  k *= m;
98  k ^= k >> r;
99  k *= m;
100 
101  h ^= k;
102  h *= m;
103  }
104 
105  const unsigned char * data2 = (const unsigned char*)data;
106 
107  switch(len & 7)
108  {
109  case 7: h ^= uint64_t(data2[6]) << 48;
110  case 6: h ^= uint64_t(data2[5]) << 40;
111  case 5: h ^= uint64_t(data2[4]) << 32;
112  case 4: h ^= uint64_t(data2[3]) << 24;
113  case 3: h ^= uint64_t(data2[2]) << 16;
114  case 2: h ^= uint64_t(data2[1]) << 8;
115  case 1: h ^= uint64_t(data2[0]);
116  h *= m;
117  };
118 
119  h ^= h >> r;
120  h *= m;
121  h ^= h >> r;
122 
123  return h;
124 }
125 
126 #endif // CVMFS_MURMUR_H_
#define BIG_CONSTANT(x)
Definition: murmur.hxx:21
uint64_t MurmurHash64A(const void *key, int len, uint64_t seed)
Definition: murmur.hxx:83
uint32_t MurmurHash2(const void *key, int len, uint32_t seed)
Definition: murmur.hxx:23