/Users/deen/code/yugabyte-db/src/yb/gutil/hash/hash.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2011 Google Inc. All Rights Reserved. |
2 | | // |
3 | | // The following only applies to changes made to this file as part of YugaByte development. |
4 | | // |
5 | | // Portions Copyright (c) YugaByte, Inc. |
6 | | // |
7 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
8 | | // in compliance with the License. You may obtain a copy of the License at |
9 | | // |
10 | | // http://www.apache.org/licenses/LICENSE-2.0 |
11 | | // |
12 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
13 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
14 | | // or implied. See the License for the specific language governing permissions and limitations |
15 | | // under the License. |
16 | | // |
17 | | // This is the legacy unified hash library implementation. Its components are |
18 | | // being split up into smaller, dedicated libraries. What remains here are |
19 | | // things still being migrated. |
20 | | // |
21 | | // To find the implementation of the core Bob Jenkins lookup2 hash, look in |
22 | | // jenkins.cc. |
23 | | |
24 | | #include "yb/gutil/hash/hash.h" |
25 | | |
26 | | #include "yb/gutil/integral_types.h" |
27 | | #include <glog/logging.h> |
28 | | #include "yb/gutil/hash/jenkins.h" |
29 | | #include "yb/gutil/hash/jenkins_lookup2.h" |
30 | | #include "yb/gutil/macros.h" |
31 | | |
32 | | // For components that ship code externally (notably the Google Search |
33 | | // Appliance) we want to change the fingerprint function so that |
34 | | // attackers cannot mount offline attacks to find collisions with |
35 | | // google.com internal fingerprints (most importantly, for URL |
36 | | // fingerprints). |
37 | | #ifdef GOOGLECLIENT |
38 | | #error Do not compile this into binaries that we deliver to users! |
39 | | #error Instead, use |
40 | | #endif |
41 | | #ifdef EXTERNAL_FP |
42 | | static const uint32 kFingerprintSeed0 = 0xabc; |
43 | | static const uint32 kFingerprintSeed1 = 0xdef; |
44 | | #else |
45 | | static const uint32 kFingerprintSeed0 = 0; |
46 | | static const uint32 kFingerprintSeed1 = 102072; |
47 | | #endif |
48 | | |
49 | 0 | static inline uint32 char2unsigned(char c) { |
50 | 0 | return static_cast<uint32>(static_cast<unsigned char>(c)); |
51 | 0 | } |
52 | | |
53 | 0 | uint64 FingerprintReferenceImplementation(const char *s, uint32 len) { |
54 | 0 | uint32 hi = Hash32StringWithSeed(s, len, kFingerprintSeed0); |
55 | 0 | uint32 lo = Hash32StringWithSeed(s, len, kFingerprintSeed1); |
56 | 0 | return CombineFingerprintHalves(hi, lo); |
57 | 0 | } |
58 | | |
59 | | // This is a faster version of FingerprintReferenceImplementation(), |
60 | | // making use of the fact that we're hashing the same string twice. |
61 | | // The code is tedious to read, but it's just two interleaved copies of |
62 | | // Hash32StringWithSeed(). |
63 | 0 | uint64 FingerprintInterleavedImplementation(const char *s, uint32 len) { |
64 | 0 | uint32 a, b, c = kFingerprintSeed0, d, e, f = kFingerprintSeed1; |
65 | 0 | uint32 keylen; |
66 | |
|
67 | 0 | a = b = d = e = 0x9e3779b9UL; // the golden ratio; an arbitrary value |
68 | |
|
69 | 0 | keylen = len; |
70 | 0 | if (keylen >= 4 * sizeof(a)) { |
71 | 0 | uint32 word32AtOffset0 = Google1At(s); |
72 | 0 | do { |
73 | 0 | a += word32AtOffset0; |
74 | 0 | d += word32AtOffset0; |
75 | 0 | b += Google1At(s + sizeof(a)); |
76 | 0 | e += Google1At(s + sizeof(a)); |
77 | 0 | c += Google1At(s + sizeof(a) * 2); |
78 | 0 | f += Google1At(s + sizeof(a) * 2); |
79 | 0 | s += 3 * sizeof(a); |
80 | 0 | word32AtOffset0 = Google1At(s); |
81 | 0 | mix(a, b, c); |
82 | 0 | mix(d, e, f); |
83 | 0 | keylen -= 3 * static_cast<uint32>(sizeof(a)); |
84 | 0 | } while (keylen >= 4 * sizeof(a)); |
85 | 0 | if (keylen >= 3 * sizeof(a)) { |
86 | 0 | a += word32AtOffset0; |
87 | 0 | d += word32AtOffset0; |
88 | 0 | b += Google1At(s + sizeof(a)); |
89 | 0 | e += Google1At(s + sizeof(a)); |
90 | 0 | c += Google1At(s + sizeof(a) * 2); |
91 | 0 | f += Google1At(s + sizeof(a) * 2); |
92 | 0 | s += 3 * sizeof(a); |
93 | 0 | mix(a, b, c); |
94 | 0 | mix(d, e, f); |
95 | 0 | keylen -= 3 * static_cast<uint32>(sizeof(a)); |
96 | 0 | DCHECK_LT(keylen, sizeof(a)); |
97 | 0 | c += len; |
98 | 0 | f += len; |
99 | 0 | switch ( keylen ) { // deal with rest. Cases fall through |
100 | 0 | case 3 : |
101 | 0 | a += char2unsigned(s[2]) << 16; |
102 | 0 | d += char2unsigned(s[2]) << 16; |
103 | 0 | FALLTHROUGH_INTENDED; |
104 | 0 | case 2 : |
105 | 0 | a += char2unsigned(s[1]) << 8; |
106 | 0 | d += char2unsigned(s[1]) << 8; |
107 | 0 | FALLTHROUGH_INTENDED; |
108 | 0 | case 1 : |
109 | 0 | a += char2unsigned(s[0]); |
110 | 0 | d += char2unsigned(s[0]); |
111 | 0 | } |
112 | 0 | } else { |
113 | 0 | DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a)); |
114 | 0 | c += len; |
115 | 0 | f += len; |
116 | 0 | switch ( keylen ) { // deal with rest. Cases fall through |
117 | 0 | case 11: |
118 | 0 | c += char2unsigned(s[10]) << 24; |
119 | 0 | f += char2unsigned(s[10]) << 24; |
120 | 0 | FALLTHROUGH_INTENDED; |
121 | 0 | case 10: |
122 | 0 | c += char2unsigned(s[9]) << 16; |
123 | 0 | f += char2unsigned(s[9]) << 16; |
124 | 0 | FALLTHROUGH_INTENDED; |
125 | 0 | case 9 : |
126 | 0 | c += char2unsigned(s[8]) << 8; |
127 | 0 | f += char2unsigned(s[8]) << 8; |
128 | 0 | FALLTHROUGH_INTENDED; |
129 | 0 | case 8 : |
130 | 0 | b += Google1At(s+4); a += word32AtOffset0; |
131 | 0 | e += Google1At(s+4); d += word32AtOffset0; |
132 | 0 | break; |
133 | 0 | case 7 : |
134 | 0 | b += char2unsigned(s[6]) << 16; |
135 | 0 | e += char2unsigned(s[6]) << 16; |
136 | 0 | FALLTHROUGH_INTENDED; |
137 | 0 | case 6 : |
138 | 0 | b += char2unsigned(s[5]) << 8; |
139 | 0 | e += char2unsigned(s[5]) << 8; |
140 | 0 | FALLTHROUGH_INTENDED; |
141 | 0 | case 5 : |
142 | 0 | b += char2unsigned(s[4]); |
143 | 0 | e += char2unsigned(s[4]); |
144 | 0 | FALLTHROUGH_INTENDED; |
145 | 0 | case 4 : |
146 | 0 | a += word32AtOffset0; |
147 | 0 | d += word32AtOffset0; |
148 | 0 | } |
149 | 0 | } |
150 | 0 | } else { |
151 | 0 | if (keylen >= 3 * sizeof(a)) { |
152 | 0 | a += Google1At(s); |
153 | 0 | d += Google1At(s); |
154 | 0 | b += Google1At(s + sizeof(a)); |
155 | 0 | e += Google1At(s + sizeof(a)); |
156 | 0 | c += Google1At(s + sizeof(a) * 2); |
157 | 0 | f += Google1At(s + sizeof(a) * 2); |
158 | 0 | s += 3 * sizeof(a); |
159 | 0 | mix(a, b, c); |
160 | 0 | mix(d, e, f); |
161 | 0 | keylen -= 3 * static_cast<uint32>(sizeof(a)); |
162 | 0 | } |
163 | 0 | c += len; |
164 | 0 | f += len; |
165 | 0 | switch ( keylen ) { // deal with rest. Cases fall through |
166 | 0 | case 11: |
167 | 0 | c += char2unsigned(s[10]) << 24; |
168 | 0 | f += char2unsigned(s[10]) << 24; |
169 | 0 | FALLTHROUGH_INTENDED; |
170 | 0 | case 10: |
171 | 0 | c += char2unsigned(s[9]) << 16; |
172 | 0 | f += char2unsigned(s[9]) << 16; |
173 | 0 | FALLTHROUGH_INTENDED; |
174 | 0 | case 9 : |
175 | 0 | c += char2unsigned(s[8]) << 8; |
176 | 0 | f += char2unsigned(s[8]) << 8; |
177 | 0 | FALLTHROUGH_INTENDED; |
178 | 0 | case 8 : |
179 | 0 | b += Google1At(s+4); a += Google1At(s); |
180 | 0 | e += Google1At(s+4); d += Google1At(s); |
181 | 0 | break; |
182 | 0 | case 7 : |
183 | 0 | b += char2unsigned(s[6]) << 16; |
184 | 0 | e += char2unsigned(s[6]) << 16; |
185 | 0 | FALLTHROUGH_INTENDED; |
186 | 0 | case 6 : |
187 | 0 | b += char2unsigned(s[5]) << 8; |
188 | 0 | e += char2unsigned(s[5]) << 8; |
189 | 0 | FALLTHROUGH_INTENDED; |
190 | 0 | case 5 : |
191 | 0 | b += char2unsigned(s[4]); |
192 | 0 | e += char2unsigned(s[4]); |
193 | 0 | FALLTHROUGH_INTENDED; |
194 | 0 | case 4 : |
195 | 0 | a += Google1At(s); |
196 | 0 | d += Google1At(s); |
197 | 0 | break; |
198 | 0 | case 3 : |
199 | 0 | a += char2unsigned(s[2]) << 16; |
200 | 0 | d += char2unsigned(s[2]) << 16; |
201 | 0 | FALLTHROUGH_INTENDED; |
202 | 0 | case 2 : |
203 | 0 | a += char2unsigned(s[1]) << 8; |
204 | 0 | d += char2unsigned(s[1]) << 8; |
205 | 0 | FALLTHROUGH_INTENDED; |
206 | 0 | case 1 : |
207 | 0 | a += char2unsigned(s[0]); |
208 | 0 | d += char2unsigned(s[0]); |
209 | 0 | } |
210 | 0 | } |
211 | 0 | mix(a, b, c); |
212 | 0 | mix(d, e, f); |
213 | 0 | return CombineFingerprintHalves(c, f); |
214 | 0 | } |
215 | | |
216 | | // Extern template definitions. |