1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 /*
7 Murmurhash from http://sites.google.com/site/murmurhash/
8
9 All code is released to the public domain. For business purposes, Murmurhash
10 is under the MIT license.
11 */
12 #include "murmurhash.h"
13 #include "util/util.h"
14
15 #if defined(__x86_64__)
16
17 // -------------------------------------------------------------------
18 //
19 // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
20 // and endian-ness issues if used across multiple platforms.
21 //
22 // 64-bit hash for 64-bit platforms
23
24 #ifdef ROCKSDB_UBSAN_RUN
25 #if defined(__clang__)
26 __attribute__((__no_sanitize__("alignment")))
27 #elif defined(__GNUC__)
28 __attribute__((__no_sanitize_undefined__))
29 #endif
30 #endif
MurmurHash64A(const void * key,int len,unsigned int seed)31 uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )
32 {
33 const uint64_t m = 0xc6a4a7935bd1e995;
34 const int r = 47;
35
36 uint64_t h = seed ^ (len * m);
37
38 const uint64_t * data = (const uint64_t *)key;
39 const uint64_t * end = data + (len/8);
40
41 while(data != end)
42 {
43 uint64_t k = *data++;
44
45 k *= m;
46 k ^= k >> r;
47 k *= m;
48
49 h ^= k;
50 h *= m;
51 }
52
53 const unsigned char * data2 = (const unsigned char*)data;
54
55 switch(len & 7)
56 {
57 case 7: h ^= ((uint64_t)data2[6]) << 48; FALLTHROUGH_INTENDED;
58 case 6: h ^= ((uint64_t)data2[5]) << 40; FALLTHROUGH_INTENDED;
59 case 5: h ^= ((uint64_t)data2[4]) << 32; FALLTHROUGH_INTENDED;
60 case 4: h ^= ((uint64_t)data2[3]) << 24; FALLTHROUGH_INTENDED;
61 case 3: h ^= ((uint64_t)data2[2]) << 16; FALLTHROUGH_INTENDED;
62 case 2: h ^= ((uint64_t)data2[1]) << 8; FALLTHROUGH_INTENDED;
63 case 1: h ^= ((uint64_t)data2[0]);
64 h *= m;
65 };
66
67 h ^= h >> r;
68 h *= m;
69 h ^= h >> r;
70
71 return h;
72 }
73
74 #elif defined(__i386__)
75
76 // -------------------------------------------------------------------
77 //
78 // Note - This code makes a few assumptions about how your machine behaves -
79 //
80 // 1. We can read a 4-byte value from any address without crashing
81 // 2. sizeof(int) == 4
82 //
83 // And it has a few limitations -
84 //
85 // 1. It will not work incrementally.
86 // 2. It will not produce the same results on little-endian and big-endian
87 // machines.
88
MurmurHash2(const void * key,int len,unsigned int seed)89 unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
90 {
91 // 'm' and 'r' are mixing constants generated offline.
92 // They're not really 'magic', they just happen to work well.
93
94 const unsigned int m = 0x5bd1e995;
95 const int r = 24;
96
97 // Initialize the hash to a 'random' value
98
99 unsigned int h = seed ^ len;
100
101 // Mix 4 bytes at a time into the hash
102
103 const unsigned char * data = (const unsigned char *)key;
104
105 while(len >= 4)
106 {
107 unsigned int k = *(unsigned int *)data;
108
109 k *= m;
110 k ^= k >> r;
111 k *= m;
112
113 h *= m;
114 h ^= k;
115
116 data += 4;
117 len -= 4;
118 }
119
120 // Handle the last few bytes of the input array
121
122 switch(len)
123 {
124 case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED;
125 case 2: h ^= data[1] << 8; FALLTHROUGH_INTENDED;
126 case 1: h ^= data[0];
127 h *= m;
128 };
129
130 // Do a few final mixes of the hash to ensure the last few
131 // bytes are well-incorporated.
132
133 h ^= h >> 13;
134 h *= m;
135 h ^= h >> 15;
136
137 return h;
138 }
139
140 #else
141
142 // -------------------------------------------------------------------
143 //
144 // Same as MurmurHash2, but endian- and alignment-neutral.
145 // Half the speed though, alas.
146
MurmurHashNeutral2(const void * key,int len,unsigned int seed)147 unsigned int MurmurHashNeutral2 ( const void * key, int len, unsigned int seed )
148 {
149 const unsigned int m = 0x5bd1e995;
150 const int r = 24;
151
152 unsigned int h = seed ^ len;
153
154 const unsigned char * data = (const unsigned char *)key;
155
156 while(len >= 4)
157 {
158 unsigned int k;
159
160 k = data[0];
161 k |= data[1] << 8;
162 k |= data[2] << 16;
163 k |= data[3] << 24;
164
165 k *= m;
166 k ^= k >> r;
167 k *= m;
168
169 h *= m;
170 h ^= k;
171
172 data += 4;
173 len -= 4;
174 }
175
176 switch(len)
177 {
178 case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED;
179 case 2: h ^= data[1] << 8; FALLTHROUGH_INTENDED;
180 case 1: h ^= data[0];
181 h *= m;
182 };
183
184 h ^= h >> 13;
185 h *= m;
186 h ^= h >> 15;
187
188 return h;
189 }
190
191 #endif
192