/Users/deen/code/yugabyte-db/src/yb/rocksdb/util/murmurhash.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | /* |
21 | | Murmurhash from http://sites.google.com/site/murmurhash/ |
22 | | |
23 | | All code is released to the public domain. For business purposes, Murmurhash is |
24 | | under the MIT license. |
25 | | */ |
26 | | |
27 | | #include "murmurhash.h" |
28 | | |
29 | | #if defined(__x86_64__) |
30 | | |
31 | | // ------------------------------------------------------------------- |
32 | | // |
33 | | // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment |
34 | | // and endian-ness issues if used across multiple platforms. |
35 | | // |
36 | | // 64-bit hash for 64-bit platforms |
37 | | |
38 | | uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ) |
39 | | { |
40 | | const uint64_t m = 0xc6a4a7935bd1e995; |
41 | | const int r = 47; |
42 | | |
43 | | uint64_t h = seed ^ (len * m); |
44 | | |
45 | | const uint64_t * data = (const uint64_t *)key; |
46 | | const uint64_t * end = data + (len/8); |
47 | | |
48 | | while(data != end) |
49 | | { |
50 | | uint64_t k = *data++; |
51 | | |
52 | | k *= m; |
53 | | k ^= k >> r; |
54 | | k *= m; |
55 | | |
56 | | h ^= k; |
57 | | h *= m; |
58 | | } |
59 | | |
60 | | const unsigned char * data2 = (const unsigned char*)data; |
61 | | |
62 | | switch(len & 7) |
63 | | { |
64 | | case 7: h ^= ((uint64_t)data2[6]) << 48; FALLTHROUGH_INTENDED; |
65 | | case 6: h ^= ((uint64_t)data2[5]) << 40; FALLTHROUGH_INTENDED; |
66 | | case 5: h ^= ((uint64_t)data2[4]) << 32; FALLTHROUGH_INTENDED; |
67 | | case 4: h ^= ((uint64_t)data2[3]) << 24; FALLTHROUGH_INTENDED; |
68 | | case 3: h ^= ((uint64_t)data2[2]) << 16; FALLTHROUGH_INTENDED; |
69 | | case 2: h ^= ((uint64_t)data2[1]) << 8; FALLTHROUGH_INTENDED; |
70 | | case 1: h ^= ((uint64_t)data2[0]); |
71 | | h *= m; |
72 | | }; |
73 | | |
74 | | h ^= h >> r; |
75 | | h *= m; |
76 | | h ^= h >> r; |
77 | | |
78 | | return h; |
79 | | } |
80 | | |
81 | | #elif defined(__i386__) |
82 | | |
83 | | // ------------------------------------------------------------------- |
84 | | // |
85 | | // Note - This code makes a few assumptions about how your machine behaves - |
86 | | // |
87 | | // 1. We can read a 4-byte value from any address without crashing |
88 | | // 2. sizeof(int) == 4 |
89 | | // |
90 | | // And it has a few limitations - |
91 | | // |
92 | | // 1. It will not work incrementally. |
93 | | // 2. It will not produce the same results on little-endian and big-endian |
94 | | // machines. |
95 | | |
96 | | unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed ) |
97 | | { |
98 | | // 'm' and 'r' are mixing constants generated offline. |
99 | | // They're not really 'magic', they just happen to work well. |
100 | | |
101 | | const unsigned int m = 0x5bd1e995; |
102 | | const int r = 24; |
103 | | |
104 | | // Initialize the hash to a 'random' value |
105 | | |
106 | | unsigned int h = seed ^ len; |
107 | | |
108 | | // Mix 4 bytes at a time into the hash |
109 | | |
110 | | const unsigned char * data = (const unsigned char *)key; |
111 | | |
112 | | while(len >= 4) |
113 | | { |
114 | | unsigned int k = *(unsigned int *)data; |
115 | | |
116 | | k *= m; |
117 | | k ^= k >> r; |
118 | | k *= m; |
119 | | |
120 | | h *= m; |
121 | | h ^= k; |
122 | | |
123 | | data += 4; |
124 | | len -= 4; |
125 | | } |
126 | | |
127 | | // Handle the last few bytes of the input array |
128 | | |
129 | | switch(len) |
130 | | { |
131 | | case 3: h ^= data[2] << 16; |
132 | | case 2: h ^= data[1] << 8; |
133 | | case 1: h ^= data[0]; |
134 | | h *= m; |
135 | | }; |
136 | | |
137 | | // Do a few final mixes of the hash to ensure the last few |
138 | | // bytes are well-incorporated. |
139 | | |
140 | | h ^= h >> 13; |
141 | | h *= m; |
142 | | h ^= h >> 15; |
143 | | |
144 | | return h; |
145 | | } |
146 | | |
147 | | #else |
148 | | |
149 | | // ------------------------------------------------------------------- |
150 | | // |
151 | | // Same as MurmurHash2, but endian- and alignment-neutral. |
152 | | // Half the speed though, alas. |
153 | | |
154 | | unsigned int MurmurHashNeutral2 ( const void * key, int len, unsigned int seed ) |
155 | 3.96M | { |
156 | 3.96M | const unsigned int m = 0x5bd1e995; |
157 | 3.96M | const int r = 24; |
158 | | |
159 | 3.96M | unsigned int h = seed ^ len; |
160 | | |
161 | 3.96M | const unsigned char * data = (const unsigned char *)key; |
162 | | |
163 | 7.57M | while(len >= 4) |
164 | 3.61M | { |
165 | 3.61M | unsigned int k; |
166 | | |
167 | 3.61M | k = data[0]; |
168 | 3.61M | k |= data[1] << 8; |
169 | 3.61M | k |= data[2] << 16; |
170 | 3.61M | k |= data[3] << 24; |
171 | | |
172 | 3.61M | k *= m; |
173 | 3.61M | k ^= k >> r; |
174 | 3.61M | k *= m; |
175 | | |
176 | 3.61M | h *= m; |
177 | 3.61M | h ^= k; |
178 | | |
179 | 3.61M | data += 4; |
180 | 3.61M | len -= 4; |
181 | 3.61M | } |
182 | | |
183 | 3.96M | switch(len) |
184 | 3.96M | { |
185 | 10.1k | case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED; |
186 | 1.01M | case 2: h ^= data[1] << 8; FALLTHROUGH_INTENDED; |
187 | 2.75M | case 1: h ^= data[0]; |
188 | 2.75M | h *= m; |
189 | 2.75M | FALLTHROUGH_INTENDED; |
190 | 3.96M | case 0:; |
191 | 3.96M | }; |
192 | | |
193 | 3.96M | h ^= h >> 13; |
194 | 3.96M | h *= m; |
195 | 3.96M | h ^= h >> 15; |
196 | | |
197 | 3.96M | return h; |
198 | 3.96M | } |
199 | | |
200 | | #endif |