]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | // |
6 | /* | |
7 | Murmurhash from http://sites.google.com/site/murmurhash/ | |
8 | ||
11fdf7f2 TL |
9 | All code is released to the public domain. For business purposes, Murmurhash |
10 | is under the MIT license. | |
7c673cae FG |
11 | */ |
12 | #include "murmurhash.h" | |
20effc67 | 13 | #include "port/lang.h" |
7c673cae FG |
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 | ||
11fdf7f2 TL |
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 | |
7c673cae FG |
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 | { | |
11fdf7f2 TL |
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; | |
7c673cae FG |
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 | ||
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 | { | |
11fdf7f2 TL |
124 | case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED; |
125 | case 2: h ^= data[1] << 8; FALLTHROUGH_INTENDED; | |
7c673cae FG |
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 | ||
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 | { | |
11fdf7f2 TL |
178 | case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED; |
179 | case 2: h ^= data[1] << 8; FALLTHROUGH_INTENDED; | |
7c673cae FG |
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 |