/Users/deen/code/yugabyte-db/src/yb/gutil/hash/city.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2010 Google Inc. All Rights Reserved. |
2 | | // Authors: gpike@google.com (Geoff Pike), jyrki@google.com (Jyrki Alakuijala) |
3 | | // |
4 | | // This file provides CityHash64() and related functions. |
5 | | // |
6 | | // The externally visible functions follow the naming conventions of |
7 | | // hash.h, where the size of the output is part of the name. For |
8 | | // example, CityHash64 returns a 64-bit hash. The internal helpers do |
9 | | // not have the return type in their name, but instead have names like |
10 | | // HashLenXX or HashLenXXtoYY, where XX and YY are input string lengths. |
11 | | // |
12 | | // Most of the constants and tricks here were copied from murmur.cc or |
13 | | // hash.h, or discovered by trial and error. It's probably possible to further |
14 | | // optimize the code here by writing a program that systematically explores |
15 | | // more of the space of possible hash functions, or by using SIMD instructions. |
16 | | |
17 | | // |
18 | | // The following only applies to changes made to this file as part of YugaByte development. |
19 | | // |
20 | | // Portions Copyright (c) YugaByte, Inc. |
21 | | // |
22 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
23 | | // in compliance with the License. You may obtain a copy of the License at |
24 | | // |
25 | | // http://www.apache.org/licenses/LICENSE-2.0 |
26 | | // |
27 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
28 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
29 | | // or implied. See the License for the specific language governing permissions and limitations |
30 | | // under the License. |
31 | | // |
32 | | |
33 | | #include "yb/gutil/hash/city.h" |
34 | | |
35 | | #include <sys/types.h> |
36 | | |
37 | | #include <glog/logging.h> |
38 | | |
39 | | #include "yb/gutil/endian.h" |
40 | | #include "yb/gutil/hash/hash128to64.h" |
41 | | |
42 | | using std::copy; |
43 | | using std::max; |
44 | | using std::min; |
45 | | using std::swap; |
46 | | using std::make_pair; |
47 | | using std::pair; |
48 | | |
49 | | namespace util_hash { |
50 | | |
51 | | // Some primes between 2^63 and 2^64 for various uses. |
52 | | static const uint64 k0 = 0xa5b85c5e198ed849ULL; |
53 | | static const uint64 k1 = 0x8d58ac26afe12e47ULL; |
54 | | static const uint64 k2 = 0xc47b6e9e3a970ed3ULL; |
55 | | static const uint64 k3 = 0xc70f6907e782aa0bULL; |
56 | | |
57 | | // Bitwise right rotate. Normally this will compile to a single |
58 | | // instruction, especially if the shift is a manifest constant. |
59 | 11 | static uint64 Rotate(uint64 val, int shift) { |
60 | 11 | DCHECK_GE(shift, 0); |
61 | 11 | DCHECK_LE(shift, 63); |
62 | | // Avoid shifting by 64: doing so yields an undefined result. |
63 | 11 | return shift == 0 ? val : ((val >> shift) | (val << (64 - shift))); |
64 | 11 | } |
65 | | |
66 | | // Equivalent to Rotate(), but requires the second arg to be non-zero. |
67 | | // On x86-64, and probably others, it's possible for this to compile |
68 | | // to a single instruction if both args are already in registers. |
69 | 0 | static uint64 RotateByAtLeast1(uint64 val, size_t shift) { |
70 | 0 | DCHECK_GE(shift, 1); |
71 | 0 | DCHECK_LE(shift, 63); |
72 | 0 | return (val >> shift) | (val << (64 - shift)); |
73 | 0 | } |
74 | | |
75 | 1 | static uint64 ShiftMix(uint64 val) { |
76 | 1 | return val ^ (val >> 47); |
77 | 1 | } |
78 | | |
79 | 104k | static uint64 HashLen16(uint64 u, uint64 v) { |
80 | 104k | return Hash128to64(uint128(u, v)); |
81 | 104k | } |
82 | | |
83 | 104k | static uint64 HashLen0to16(const char *s, size_t len) { |
84 | 104k | DCHECK_GE(len, 0); |
85 | 104k | DCHECK_LE(len, 16); |
86 | 104k | if (len > 8) { |
87 | 0 | uint64 a = LittleEndian::Load64(s); |
88 | 0 | uint64 b = LittleEndian::Load64(s + len - 8); |
89 | 0 | return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b; |
90 | 0 | } |
91 | 104k | if (len >= 4) { |
92 | 104k | uint64 a = LittleEndian::Load32(s); |
93 | 104k | return HashLen16(len + (a << 3), LittleEndian::Load32(s + len - 4)); |
94 | 104k | } |
95 | 0 | if (len > 0) { |
96 | 0 | uint8 a = s[0]; |
97 | 0 | uint8 b = s[len >> 1]; |
98 | 0 | uint8 c = s[len - 1]; |
99 | 0 | uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8); |
100 | 0 | uint32 z = static_cast<uint32>(len) + (static_cast<uint32>(c) << 2); |
101 | 0 | return ShiftMix(y * k2 ^ z * k3) * k2; |
102 | 0 | } |
103 | 0 | return k2; |
104 | 0 | } |
105 | | |
106 | | // This probably works well for 16-byte strings as well, but it may be overkill |
107 | | // in that case. |
108 | 0 | static uint64 HashLen17to32(const char *s, size_t len) { |
109 | 0 | DCHECK_GE(len, 17); |
110 | 0 | DCHECK_LE(len, 32); |
111 | 0 | uint64 a = LittleEndian::Load64(s) * k1; |
112 | 0 | uint64 b = LittleEndian::Load64(s + 8); |
113 | 0 | uint64 c = LittleEndian::Load64(s + len - 8) * k2; |
114 | 0 | uint64 d = LittleEndian::Load64(s + len - 16) * k0; |
115 | 0 | return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d, |
116 | 0 | a + Rotate(b ^ k3, 20) - c + len); |
117 | 0 | } |
118 | | |
119 | | // Return a 16-byte hash for 48 bytes. Quick and dirty. |
120 | | // Callers do best to use "random-looking" values for a and b. |
121 | | // (For more, see the code review discussion of CL 18799087.) |
122 | | static pair<uint64, uint64> WeakHashLen32WithSeeds( |
123 | 4 | uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) { |
124 | 4 | a += w; |
125 | 4 | b = Rotate(b + a + z, 51); |
126 | 4 | uint64 c = a; |
127 | 4 | a += x; |
128 | 4 | a += y; |
129 | 4 | b += Rotate(a, 23); |
130 | 4 | return make_pair(a + z, b + c); |
131 | 4 | } |
132 | | |
133 | | // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. |
134 | | static pair<uint64, uint64> WeakHashLen32WithSeeds( |
135 | 4 | const char* s, uint64 a, uint64 b) { |
136 | 4 | return WeakHashLen32WithSeeds(LittleEndian::Load64(s), |
137 | 4 | LittleEndian::Load64(s + 8), |
138 | 4 | LittleEndian::Load64(s + 16), |
139 | 4 | LittleEndian::Load64(s + 24), |
140 | 4 | a, |
141 | 4 | b); |
142 | 4 | } |
143 | | |
144 | | // Return an 8-byte hash for 33 to 64 bytes. |
145 | 0 | static uint64 HashLen33to64(const char *s, size_t len) { |
146 | 0 | uint64 z = LittleEndian::Load64(s + 24); |
147 | 0 | uint64 a = LittleEndian::Load64(s) + |
148 | 0 | (len + LittleEndian::Load64(s + len - 16)) * k0; |
149 | 0 | uint64 b = Rotate(a + z, 52); |
150 | 0 | uint64 c = Rotate(a, 37); |
151 | 0 | a += LittleEndian::Load64(s + 8); |
152 | 0 | c += Rotate(a, 7); |
153 | 0 | a += LittleEndian::Load64(s + 16); |
154 | 0 | uint64 vf = a + z; |
155 | 0 | uint64 vs = b + Rotate(a, 31) + c; |
156 | 0 | a = LittleEndian::Load64(s + 16) + LittleEndian::Load64(s + len - 32); |
157 | 0 | z += LittleEndian::Load64(s + len - 8); |
158 | 0 | b = Rotate(a + z, 52); |
159 | 0 | c = Rotate(a, 37); |
160 | 0 | a += LittleEndian::Load64(s + len - 24); |
161 | 0 | c += Rotate(a, 7); |
162 | 0 | a += LittleEndian::Load64(s + len - 16); |
163 | 0 | uint64 wf = a + z; |
164 | 0 | uint64 ws = b + Rotate(a, 31) + c; |
165 | 0 | uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0); |
166 | 0 | return ShiftMix(r * k0 + vs) * k2; |
167 | 0 | } |
168 | | |
169 | 104k | uint64 CityHash64(const char *s, size_t len) { |
170 | 104k | if (len <= 32) { |
171 | 104k | if (len <= 16) { |
172 | 104k | return HashLen0to16(s, len); |
173 | 0 | } else { |
174 | 0 | return HashLen17to32(s, len); |
175 | 0 | } |
176 | 1 | } else if (len <= 64) { |
177 | 0 | return HashLen33to64(s, len); |
178 | 0 | } |
179 | | |
180 | | // For strings over 64 bytes we hash the end first, and then as we |
181 | | // loop we keep 56 bytes of state: v, w, x, y, and z. |
182 | 1 | uint64 x = LittleEndian::Load64(s + len - 40); |
183 | 1 | uint64 y = LittleEndian::Load64(s + len - 16) + |
184 | 1 | LittleEndian::Load64(s + len - 56); |
185 | 1 | uint64 z = HashLen16(LittleEndian::Load64(s + len - 48) + len, |
186 | 1 | LittleEndian::Load64(s + len - 24)); |
187 | 1 | pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, z); |
188 | 1 | pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, y + k1, x); |
189 | 1 | x = x * k1 + LittleEndian::Load64(s); |
190 | | |
191 | | // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. |
192 | 1 | len = (len - 1) & ~static_cast<size_t>(63); |
193 | 1 | DCHECK_GT(len, 0); |
194 | 1 | DCHECK_EQ(len, len / 64 * 64); |
195 | 1 | do { |
196 | 1 | x = Rotate(x + y + v.first + LittleEndian::Load64(s + 8), 37) * k1; |
197 | 1 | y = Rotate(y + v.second + LittleEndian::Load64(s + 48), 42) * k1; |
198 | 1 | x ^= w.second; |
199 | 1 | y += v.first + LittleEndian::Load64(s + 40); |
200 | 1 | z = Rotate(z + w.first, 33) * k1; |
201 | 1 | v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); |
202 | 1 | w = WeakHashLen32WithSeeds(s + 32, z + w.second, |
203 | 1 | y + LittleEndian::Load64(s + 16)); |
204 | 1 | std::swap(z, x); |
205 | 1 | s += 64; |
206 | 1 | len -= 64; |
207 | 1 | } while (len != 0); |
208 | 1 | return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z, |
209 | 1 | HashLen16(v.second, w.second) + x); |
210 | 1 | } |
211 | | |
212 | 0 | uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) { |
213 | 0 | return CityHash64WithSeeds(s, len, k2, seed); |
214 | 0 | } |
215 | | |
216 | | uint64 CityHash64WithSeeds(const char *s, size_t len, |
217 | 0 | uint64 seed0, uint64 seed1) { |
218 | 0 | return HashLen16(CityHash64(s, len) - seed0, seed1); |
219 | 0 | } |
220 | | |
221 | | // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings |
222 | | // of any length representable in ssize_t. Based on City and Murmur128. |
223 | 0 | static uint128 CityMurmur(const char *s, size_t len, uint128 seed) { |
224 | 0 | uint64 a = Uint128Low64(seed); |
225 | 0 | uint64 b = Uint128High64(seed); |
226 | 0 | uint64 c = 0; |
227 | 0 | uint64 d = 0; |
228 | 0 | ssize_t l = len - 16; |
229 | 0 | if (l <= 0) { // len <= 16 |
230 | 0 | c = b * k1 + HashLen0to16(s, len); |
231 | 0 | d = Rotate(a + (len >= 8 ? LittleEndian::Load64(s) : c), 32); |
232 | 0 | } else { // len > 16 |
233 | 0 | c = HashLen16(LittleEndian::Load64(s + len - 8) + k1, a); |
234 | 0 | d = HashLen16(b + len, c + LittleEndian::Load64(s + len - 16)); |
235 | 0 | a += d; |
236 | 0 | do { |
237 | 0 | a ^= ShiftMix(LittleEndian::Load64(s) * k1) * k1; |
238 | 0 | a *= k1; |
239 | 0 | b ^= a; |
240 | 0 | c ^= ShiftMix(LittleEndian::Load64(s + 8) * k1) * k1; |
241 | 0 | c *= k1; |
242 | 0 | d ^= c; |
243 | 0 | s += 16; |
244 | 0 | l -= 16; |
245 | 0 | } while (l > 0); |
246 | 0 | } |
247 | 0 | a = HashLen16(a, c); |
248 | 0 | b = HashLen16(d, b); |
249 | 0 | return uint128(a ^ b, HashLen16(b, a)); |
250 | 0 | } |
251 | | |
252 | 0 | uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) { |
253 | | // TODO(user): As of February 2011, there's a beta of Murmur3 that would |
254 | | // most likely be useful here. E.g., if (len < 900) return Murmur3(...) |
255 | 0 | if (len < 128) { |
256 | 0 | return CityMurmur(s, len, seed); |
257 | 0 | } |
258 | | |
259 | | // We expect len >= 128 to be the common case. Keep 56 bytes of state: |
260 | | // v, w, x, y, and z. |
261 | 0 | pair<uint64, uint64> v, w; |
262 | 0 | uint64 x = Uint128Low64(seed); |
263 | 0 | uint64 y = Uint128High64(seed); |
264 | 0 | uint64 z = len * k1; |
265 | 0 | v.first = Rotate(y ^ k1, 49) * k1 + LittleEndian::Load64(s); |
266 | 0 | v.second = Rotate(v.first, 42) * k1 + LittleEndian::Load64(s + 8); |
267 | 0 | w.first = Rotate(y + z, 35) * k1 + x; |
268 | 0 | w.second = Rotate(x + LittleEndian::Load64(s + 88), 53) * k1; |
269 | | |
270 | | // This is similar to the inner loop of CityHash64(), manually unrolled. |
271 | 0 | do { |
272 | 0 | x = Rotate(x + y + v.first + LittleEndian::Load64(s + 16), 37) * k1; |
273 | 0 | y = Rotate(y + v.second + LittleEndian::Load64(s + 48), 42) * k1; |
274 | 0 | x ^= w.second; |
275 | 0 | y ^= v.first; |
276 | 0 | z = Rotate(z ^ w.first, 33); |
277 | 0 | v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); |
278 | 0 | w = WeakHashLen32WithSeeds(s + 32, z + w.second, y); |
279 | 0 | std::swap(z, x); |
280 | 0 | s += 64; |
281 | 0 | x = Rotate(x + y + v.first + LittleEndian::Load64(s + 16), 37) * k1; |
282 | 0 | y = Rotate(y + v.second + LittleEndian::Load64(s + 48), 42) * k1; |
283 | 0 | x ^= w.second; |
284 | 0 | y ^= v.first; |
285 | 0 | z = Rotate(z ^ w.first, 33); |
286 | 0 | v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); |
287 | 0 | w = WeakHashLen32WithSeeds(s + 32, z + w.second, y); |
288 | 0 | std::swap(z, x); |
289 | 0 | s += 64; |
290 | 0 | len -= 128; |
291 | 0 | } while (PREDICT_TRUE(len >= 128)); |
292 | 0 | y += Rotate(w.first, 37) * k0 + z; |
293 | 0 | x += Rotate(v.first + z, 49) * k0; |
294 | | // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s. |
295 | 0 | for (size_t tail_done = 0; tail_done < len; ) { |
296 | 0 | tail_done += 32; |
297 | 0 | y = Rotate(y - x, 42) * k0 + v.second; |
298 | 0 | w.first += LittleEndian::Load64(s + len - tail_done + 16); |
299 | 0 | x = Rotate(x, 49) * k0 + w.first; |
300 | 0 | w.first += v.first; |
301 | 0 | v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second); |
302 | 0 | } |
303 | | // At this point our 48 bytes of state should contain more than |
304 | | // enough information for a strong 128-bit hash. We use two |
305 | | // different 48-byte-to-8-byte hashes to get a 16-byte final result. |
306 | 0 | x = HashLen16(x, v.first); |
307 | 0 | y = HashLen16(y, w.first); |
308 | 0 | return uint128(HashLen16(x + v.second, w.second) + y, |
309 | 0 | HashLen16(x + w.second, y + v.second)); |
310 | 0 | } |
311 | | |
312 | 0 | uint128 CityHash128(const char *s, size_t len) { |
313 | 0 | if (len >= 16) { |
314 | 0 | return CityHash128WithSeed(s + 16, |
315 | 0 | len - 16, |
316 | 0 | uint128(LittleEndian::Load64(s) ^ k3, |
317 | 0 | LittleEndian::Load64(s + 8))); |
318 | 0 | } else if (len >= 8) { |
319 | 0 | return CityHash128WithSeed(nullptr, |
320 | 0 | 0, |
321 | 0 | uint128(LittleEndian::Load64(s) ^ (len * k0), |
322 | 0 | LittleEndian::Load64(s + len - 8) ^ k1)); |
323 | 0 | } else { |
324 | 0 | return CityHash128WithSeed(s, len, uint128(k0, k1)); |
325 | 0 | } |
326 | 0 | } |
327 | | |
328 | | } // namespace util_hash |