1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef LIBTEXTCLASSIFIER_UTILS_HASH_FARMHASH_H_
18 #define LIBTEXTCLASSIFIER_UTILS_HASH_FARMHASH_H_
19
20 #include <assert.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h> // for memcpy and memset
24 #include <utility>
25
26 #ifndef NAMESPACE_FOR_HASH_FUNCTIONS
27 #define NAMESPACE_FOR_HASH_FUNCTIONS tc3farmhash
28 #endif
29
30 namespace NAMESPACE_FOR_HASH_FUNCTIONS {
31
32 #if defined(FARMHASH_UINT128_T_DEFINED)
Uint128Low64(const uint128_t x)33 inline uint64_t Uint128Low64(const uint128_t x) {
34 return static_cast<uint64_t>(x);
35 }
Uint128High64(const uint128_t x)36 inline uint64_t Uint128High64(const uint128_t x) {
37 return static_cast<uint64_t>(x >> 64);
38 }
Uint128(uint64_t lo,uint64_t hi)39 inline uint128_t Uint128(uint64_t lo, uint64_t hi) {
40 return lo + (((uint128_t)hi) << 64);
41 }
42 #else
43 typedef std::pair<uint64_t, uint64_t> uint128_t;
44 inline uint64_t Uint128Low64(const uint128_t x) { return x.first; }
45 inline uint64_t Uint128High64(const uint128_t x) { return x.second; }
46 inline uint128_t Uint128(uint64_t lo, uint64_t hi) { return uint128_t(lo, hi); }
47 #endif
48
49
50 // BASIC STRING HASHING
51
52 // Hash function for a byte array.
53 // May change from time to time, may differ on different platforms, may differ
54 // depending on NDEBUG.
55 size_t Hash(const char* s, size_t len);
56
57 // Hash function for a byte array. Most useful in 32-bit binaries.
58 // May change from time to time, may differ on different platforms, may differ
59 // depending on NDEBUG.
60 uint32_t Hash32(const char* s, size_t len);
61
62 // Hash function for a byte array. For convenience, a 32-bit seed is also
63 // hashed into the result.
64 // May change from time to time, may differ on different platforms, may differ
65 // depending on NDEBUG.
66 uint32_t Hash32WithSeed(const char* s, size_t len, uint32_t seed);
67
68 // Hash 128 input bits down to 64 bits of output.
69 // Hash function for a byte array.
70 // May change from time to time, may differ on different platforms, may differ
71 // depending on NDEBUG.
72 uint64_t Hash64(const char* s, size_t len);
73
74 // Hash function for a byte array. For convenience, a 64-bit seed is also
75 // hashed into the result.
76 // May change from time to time, may differ on different platforms, may differ
77 // depending on NDEBUG.
78 uint64_t Hash64WithSeed(const char* s, size_t len, uint64_t seed);
79
80 // Hash function for a byte array. For convenience, two seeds are also
81 // hashed into the result.
82 // May change from time to time, may differ on different platforms, may differ
83 // depending on NDEBUG.
84 uint64_t Hash64WithSeeds(const char* s, size_t len,
85 uint64_t seed0, uint64_t seed1);
86
87 // Hash function for a byte array.
88 // May change from time to time, may differ on different platforms, may differ
89 // depending on NDEBUG.
90 uint128_t Hash128(const char* s, size_t len);
91
92 // Hash function for a byte array. For convenience, a 128-bit seed is also
93 // hashed into the result.
94 // May change from time to time, may differ on different platforms, may differ
95 // depending on NDEBUG.
96 uint128_t Hash128WithSeed(const char* s, size_t len, uint128_t seed);
97
98 // BASIC NON-STRING HASHING
99
100 // This is intended to be a reasonably good hash function.
101 // May change from time to time, may differ on different platforms, may differ
102 // depending on NDEBUG.
Hash128to64(uint128_t x)103 inline uint64_t Hash128to64(uint128_t x) {
104 // Murmur-inspired hashing.
105 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
106 uint64_t a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
107 a ^= (a >> 47);
108 uint64_t b = (Uint128High64(x) ^ a) * kMul;
109 b ^= (b >> 47);
110 b *= kMul;
111 return b;
112 }
113
114 // FINGERPRINTING (i.e., good, portable, forever-fixed hash functions)
115
116 // Fingerprint function for a byte array. Most useful in 32-bit binaries.
117 uint32_t Fingerprint32(const char* s, size_t len);
118
119 // Fingerprint function for a byte array.
120 uint64_t Fingerprint64(const char* s, size_t len);
121
122 // Fingerprint function for a byte array.
123 uint128_t Fingerprint128(const char* s, size_t len);
124
125 // This is intended to be a good fingerprinting primitive.
126 // See below for more overloads.
Fingerprint(uint128_t x)127 inline uint64_t Fingerprint(uint128_t x) {
128 // Murmur-inspired hashing.
129 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
130 uint64_t a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
131 a ^= (a >> 47);
132 uint64_t b = (Uint128High64(x) ^ a) * kMul;
133 b ^= (b >> 44);
134 b *= kMul;
135 b ^= (b >> 41);
136 b *= kMul;
137 return b;
138 }
139
140 // This is intended to be a good fingerprinting primitive.
Fingerprint(uint64_t x)141 inline uint64_t Fingerprint(uint64_t x) {
142 // Murmur-inspired hashing.
143 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
144 uint64_t b = x * kMul;
145 b ^= (b >> 44);
146 b *= kMul;
147 b ^= (b >> 41);
148 b *= kMul;
149 return b;
150 }
151
152 #ifndef FARMHASH_NO_CXX_STRING
153
154 // Convenience functions to hash or fingerprint C++ strings.
155 // These require that Str::data() return a pointer to the first char
156 // (as a const char*) and that Str::length() return the string's length;
157 // they work with std::string, for example.
158
159 // Hash function for a byte array. Most useful in 32-bit binaries.
160 // May change from time to time, may differ on different platforms, may differ
161 // depending on NDEBUG.
162 template <typename Str>
Hash(const Str & s)163 inline size_t Hash(const Str& s) {
164 assert(sizeof(s[0]) == 1);
165 return Hash(s.data(), s.length());
166 }
167
168 // Hash function for a byte array. Most useful in 32-bit binaries.
169 // May change from time to time, may differ on different platforms, may differ
170 // depending on NDEBUG.
171 template <typename Str>
Hash32(const Str & s)172 inline uint32_t Hash32(const Str& s) {
173 assert(sizeof(s[0]) == 1);
174 return Hash32(s.data(), s.length());
175 }
176
177 // Hash function for a byte array. For convenience, a 32-bit seed is also
178 // hashed into the result.
179 // May change from time to time, may differ on different platforms, may differ
180 // depending on NDEBUG.
181 template <typename Str>
Hash32WithSeed(const Str & s,uint32_t seed)182 inline uint32_t Hash32WithSeed(const Str& s, uint32_t seed) {
183 assert(sizeof(s[0]) == 1);
184 return Hash32WithSeed(s.data(), s.length(), seed);
185 }
186
187 // Hash 128 input bits down to 64 bits of output.
188 // Hash function for a byte array.
189 // May change from time to time, may differ on different platforms, may differ
190 // depending on NDEBUG.
191 template <typename Str>
Hash64(const Str & s)192 inline uint64_t Hash64(const Str& s) {
193 assert(sizeof(s[0]) == 1);
194 return Hash64(s.data(), s.length());
195 }
196
197 // Hash function for a byte array. For convenience, a 64-bit seed is also
198 // hashed into the result.
199 // May change from time to time, may differ on different platforms, may differ
200 // depending on NDEBUG.
201 template <typename Str>
Hash64WithSeed(const Str & s,uint64_t seed)202 inline uint64_t Hash64WithSeed(const Str& s, uint64_t seed) {
203 assert(sizeof(s[0]) == 1);
204 return Hash64WithSeed(s.data(), s.length(), seed);
205 }
206
207 // Hash function for a byte array. For convenience, two seeds are also
208 // hashed into the result.
209 // May change from time to time, may differ on different platforms, may differ
210 // depending on NDEBUG.
211 template <typename Str>
Hash64WithSeeds(const Str & s,uint64_t seed0,uint64_t seed1)212 inline uint64_t Hash64WithSeeds(const Str& s, uint64_t seed0, uint64_t seed1) {
213 assert(sizeof(s[0]) == 1);
214 return Hash64WithSeeds(s.data(), s.length(), seed0, seed1);
215 }
216
217 // Hash function for a byte array.
218 // May change from time to time, may differ on different platforms, may differ
219 // depending on NDEBUG.
220 template <typename Str>
Hash128(const Str & s)221 inline uint128_t Hash128(const Str& s) {
222 assert(sizeof(s[0]) == 1);
223 return Hash128(s.data(), s.length());
224 }
225
226 // Hash function for a byte array. For convenience, a 128-bit seed is also
227 // hashed into the result.
228 // May change from time to time, may differ on different platforms, may differ
229 // depending on NDEBUG.
230 template <typename Str>
Hash128WithSeed(const Str & s,uint128_t seed)231 inline uint128_t Hash128WithSeed(const Str& s, uint128_t seed) {
232 assert(sizeof(s[0]) == 1);
233 return Hash128(s.data(), s.length(), seed);
234 }
235
236 // FINGERPRINTING (i.e., good, portable, forever-fixed hash functions)
237
238 // Fingerprint function for a byte array. Most useful in 32-bit binaries.
239 template <typename Str>
Fingerprint32(const Str & s)240 inline uint32_t Fingerprint32(const Str& s) {
241 assert(sizeof(s[0]) == 1);
242 return Fingerprint32(s.data(), s.length());
243 }
244
245 // Fingerprint 128 input bits down to 64 bits of output.
246 // Fingerprint function for a byte array.
247 template <typename Str>
Fingerprint64(const Str & s)248 inline uint64_t Fingerprint64(const Str& s) {
249 assert(sizeof(s[0]) == 1);
250 return Fingerprint64(s.data(), s.length());
251 }
252
253 // Fingerprint function for a byte array.
254 template <typename Str>
Fingerprint128(const Str & s)255 inline uint128_t Fingerprint128(const Str& s) {
256 assert(sizeof(s[0]) == 1);
257 return Fingerprint128(s.data(), s.length());
258 }
259
260 #endif
261
262 } // namespace NAMESPACE_FOR_HASH_FUNCTIONS
263
264 #endif // LIBTEXTCLASSIFIER_UTILS_HASH_FARMHASH_H_
265