1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /* Utilities for hashing. */
8
9 /*
10 * This file exports functions for hashing data down to a 32-bit value,
11 * including:
12 *
13 * - HashString Hash a char* or uint16_t/wchar_t* of known or unknown
14 * length.
15 *
16 * - HashBytes Hash a byte array of known length.
17 *
18 * - HashGeneric Hash one or more values. Currently, we support uint32_t,
19 * types which can be implicitly cast to uint32_t, data
20 * pointers, and function pointers.
21 *
22 * - AddToHash Add one or more values to the given hash. This supports the
23 * same list of types as HashGeneric.
24 *
25 *
26 * You can chain these functions together to hash complex objects. For example:
27 *
28 * class ComplexObject
29 * {
30 * char* mStr;
31 * uint32_t mUint1, mUint2;
32 * void (*mCallbackFn)();
33 *
34 * public:
35 * uint32_t hash()
36 * {
37 * uint32_t hash = HashString(mStr);
38 * hash = AddToHash(hash, mUint1, mUint2);
39 * return AddToHash(hash, mCallbackFn);
40 * }
41 * };
42 *
43 * If you want to hash an nsAString or nsACString, use the HashString functions
44 * in nsHashKeys.h.
45 */
46
47 #ifndef mozilla_HashFunctions_h
48 #define mozilla_HashFunctions_h
49
50 #include "mozilla/Assertions.h"
51 #include "mozilla/Attributes.h"
52 #include "mozilla/Char16.h"
53 #include "mozilla/MathAlgorithms.h"
54 #include "mozilla/Types.h"
55
56 #include <stdint.h>
57
58 #ifdef __cplusplus
59 namespace mozilla {
60
61 /**
62 * The golden ratio as a 32-bit fixed-point value.
63 */
64 static const uint32_t kGoldenRatioU32 = 0x9E3779B9U;
65
66 inline uint32_t
RotateBitsLeft32(uint32_t aValue,uint8_t aBits)67 RotateBitsLeft32(uint32_t aValue, uint8_t aBits)
68 {
69 MOZ_ASSERT(aBits < 32);
70 return (aValue << aBits) | (aValue >> (32 - aBits));
71 }
72
73 namespace detail {
74
75 inline uint32_t
AddU32ToHash(uint32_t aHash,uint32_t aValue)76 AddU32ToHash(uint32_t aHash, uint32_t aValue)
77 {
78 /*
79 * This is the meat of all our hash routines. This hash function is not
80 * particularly sophisticated, but it seems to work well for our mostly
81 * plain-text inputs. Implementation notes follow.
82 *
83 * Our use of the golden ratio here is arbitrary; we could pick almost any
84 * number which:
85 *
86 * * is odd (because otherwise, all our hash values will be even)
87 *
88 * * has a reasonably-even mix of 1's and 0's (consider the extreme case
89 * where we multiply by 0x3 or 0xeffffff -- this will not produce good
90 * mixing across all bits of the hash).
91 *
92 * The rotation length of 5 is also arbitrary, although an odd number is again
93 * preferable so our hash explores the whole universe of possible rotations.
94 *
95 * Finally, we multiply by the golden ratio *after* xor'ing, not before.
96 * Otherwise, if |aHash| is 0 (as it often is for the beginning of a
97 * message), the expression
98 *
99 * (kGoldenRatioU32 * RotateBitsLeft(aHash, 5)) |xor| aValue
100 *
101 * evaluates to |aValue|.
102 *
103 * (Number-theoretic aside: Because any odd number |m| is relatively prime to
104 * our modulus (2^32), the list
105 *
106 * [x * m (mod 2^32) for 0 <= x < 2^32]
107 *
108 * has no duplicate elements. This means that multiplying by |m| does not
109 * cause us to skip any possible hash values.
110 *
111 * It's also nice if |m| has large-ish order mod 2^32 -- that is, if the
112 * smallest k such that m^k == 1 (mod 2^32) is large -- so we can safely
113 * multiply our hash value by |m| a few times without negating the
114 * multiplicative effect. Our golden ratio constant has order 2^29, which is
115 * more than enough for our purposes.)
116 */
117 return kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue);
118 }
119
120 /**
121 * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
122 */
123 template<size_t PtrSize>
124 inline uint32_t
125 AddUintptrToHash(uint32_t aHash, uintptr_t aValue);
126
127 template<>
128 inline uint32_t
129 AddUintptrToHash<4>(uint32_t aHash, uintptr_t aValue)
130 {
131 return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
132 }
133
134 template<>
135 inline uint32_t
136 AddUintptrToHash<8>(uint32_t aHash, uintptr_t aValue)
137 {
138 /*
139 * The static cast to uint64_t below is necessary because this function
140 * sometimes gets compiled on 32-bit platforms (yes, even though it's a
141 * template and we never call this particular override in a 32-bit build). If
142 * we do aValue >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
143 * right 32 bits, and the compiler throws an error.
144 */
145 uint32_t v1 = static_cast<uint32_t>(aValue);
146 uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(aValue) >> 32);
147 return AddU32ToHash(AddU32ToHash(aHash, v1), v2);
148 }
149
150 } /* namespace detail */
151
152 /**
153 * AddToHash takes a hash and some values and returns a new hash based on the
154 * inputs.
155 *
156 * Currently, we support hashing uint32_t's, values which we can implicitly
157 * convert to uint32_t, data pointers, and function pointers.
158 */
159 template<typename A>
160 MOZ_WARN_UNUSED_RESULT inline uint32_t
AddToHash(uint32_t aHash,A aA)161 AddToHash(uint32_t aHash, A aA)
162 {
163 /*
164 * Try to convert |A| to uint32_t implicitly. If this works, great. If not,
165 * we'll error out.
166 */
167 return detail::AddU32ToHash(aHash, aA);
168 }
169
170 template<typename A>
171 MOZ_WARN_UNUSED_RESULT inline uint32_t
AddToHash(uint32_t aHash,A * aA)172 AddToHash(uint32_t aHash, A* aA)
173 {
174 /*
175 * You might think this function should just take a void*. But then we'd only
176 * catch data pointers and couldn't handle function pointers.
177 */
178
179 static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
180
181 return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
182 }
183
184 template<>
185 MOZ_WARN_UNUSED_RESULT inline uint32_t
AddToHash(uint32_t aHash,uintptr_t aA)186 AddToHash(uint32_t aHash, uintptr_t aA)
187 {
188 return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, aA);
189 }
190
191 template<typename A, typename... Args>
192 MOZ_WARN_UNUSED_RESULT uint32_t
AddToHash(uint32_t aHash,A aArg,Args...aArgs)193 AddToHash(uint32_t aHash, A aArg, Args... aArgs)
194 {
195 return AddToHash(AddToHash(aHash, aArg), aArgs...);
196 }
197
198 /**
199 * The HashGeneric class of functions let you hash one or more values.
200 *
201 * If you want to hash together two values x and y, calling HashGeneric(x, y) is
202 * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
203 * that x has already been hashed.
204 */
205 template<typename... Args>
206 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashGeneric(Args...aArgs)207 HashGeneric(Args... aArgs)
208 {
209 return AddToHash(0, aArgs...);
210 }
211
212 namespace detail {
213
214 template<typename T>
215 uint32_t
HashUntilZero(const T * aStr)216 HashUntilZero(const T* aStr)
217 {
218 uint32_t hash = 0;
219 for (T c; (c = *aStr); aStr++) {
220 hash = AddToHash(hash, c);
221 }
222 return hash;
223 }
224
225 template<typename T>
226 uint32_t
HashKnownLength(const T * aStr,size_t aLength)227 HashKnownLength(const T* aStr, size_t aLength)
228 {
229 uint32_t hash = 0;
230 for (size_t i = 0; i < aLength; i++) {
231 hash = AddToHash(hash, aStr[i]);
232 }
233 return hash;
234 }
235
236 } /* namespace detail */
237
238 /**
239 * The HashString overloads below do just what you'd expect.
240 *
241 * If you have the string's length, you might as well call the overload which
242 * includes the length. It may be marginally faster.
243 */
244 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const char * aStr)245 HashString(const char* aStr)
246 {
247 return detail::HashUntilZero(reinterpret_cast<const unsigned char*>(aStr));
248 }
249
250 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const char * aStr,size_t aLength)251 HashString(const char* aStr, size_t aLength)
252 {
253 return detail::HashKnownLength(reinterpret_cast<const unsigned char*>(aStr), aLength);
254 }
255
256 MOZ_WARN_UNUSED_RESULT
257 inline uint32_t
HashString(const unsigned char * aStr,size_t aLength)258 HashString(const unsigned char* aStr, size_t aLength)
259 {
260 return detail::HashKnownLength(aStr, aLength);
261 }
262
263 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const uint16_t * aStr)264 HashString(const uint16_t* aStr)
265 {
266 return detail::HashUntilZero(aStr);
267 }
268
269 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const uint16_t * aStr,size_t aLength)270 HashString(const uint16_t* aStr, size_t aLength)
271 {
272 return detail::HashKnownLength(aStr, aLength);
273 }
274
275 #ifdef MOZ_CHAR16_IS_NOT_WCHAR
276 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const char16_t * aStr)277 HashString(const char16_t* aStr)
278 {
279 return detail::HashUntilZero(aStr);
280 }
281
282 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const char16_t * aStr,size_t aLength)283 HashString(const char16_t* aStr, size_t aLength)
284 {
285 return detail::HashKnownLength(aStr, aLength);
286 }
287 #endif
288
289 /*
290 * On Windows, wchar_t (char16_t) is not the same as uint16_t, even though it's
291 * the same width!
292 */
293 #ifdef WIN32
294 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const wchar_t * aStr)295 HashString(const wchar_t* aStr)
296 {
297 return detail::HashUntilZero(aStr);
298 }
299
300 MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const wchar_t * aStr,size_t aLength)301 HashString(const wchar_t* aStr, size_t aLength)
302 {
303 return detail::HashKnownLength(aStr, aLength);
304 }
305 #endif
306
307 /**
308 * Hash some number of bytes.
309 *
310 * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
311 * same result out of HashBytes as you would out of HashString.
312 */
313 MOZ_WARN_UNUSED_RESULT extern MFBT_API uint32_t
314 HashBytes(const void* bytes, size_t aLength);
315
316 /**
317 * A pseudorandom function mapping 32-bit integers to 32-bit integers.
318 *
319 * This is for when you're feeding private data (like pointer values or credit
320 * card numbers) to a non-crypto hash function (like HashBytes) and then using
321 * the hash code for something that untrusted parties could observe (like a JS
322 * Map). Plug in a HashCodeScrambler before that last step to avoid leaking the
323 * private data.
324 *
325 * By itself, this does not prevent hash-flooding DoS attacks, because an
326 * attacker can still generate many values with exactly equal hash codes by
327 * attacking the non-crypto hash function alone. Equal hash codes will, of
328 * course, still be equal however much you scramble them.
329 *
330 * The algorithm is SipHash-1-3. See <https://131002.net/siphash/>.
331 */
332 class HashCodeScrambler
333 {
334 struct SipHasher;
335
336 uint64_t mK0, mK1;
337
338 public:
339 /** Creates a new scrambler with the given 128-bit key. */
HashCodeScrambler(uint64_t aK0,uint64_t aK1)340 HashCodeScrambler(uint64_t aK0, uint64_t aK1) : mK0(aK0), mK1(aK1) {}
341
342 /**
343 * Scramble a hash code. Always produces the same result for the same
344 * combination of key and hash code.
345 */
scramble(uint32_t aHashCode)346 uint32_t scramble(uint32_t aHashCode) const
347 {
348 SipHasher hasher(mK0, mK1);
349 return uint32_t(hasher.sipHash(aHashCode));
350 }
351
352 private:
353 struct SipHasher
354 {
SipHasherSipHasher355 SipHasher(uint64_t aK0, uint64_t aK1)
356 {
357 // 1. Initialization.
358 mV0 = aK0 ^ UINT64_C(0x736f6d6570736575);
359 mV1 = aK1 ^ UINT64_C(0x646f72616e646f6d);
360 mV2 = aK0 ^ UINT64_C(0x6c7967656e657261);
361 mV3 = aK1 ^ UINT64_C(0x7465646279746573);
362 }
363
sipHashSipHasher364 uint64_t sipHash(uint64_t aM)
365 {
366 // 2. Compression.
367 mV3 ^= aM;
368 sipRound();
369 mV0 ^= aM;
370
371 // 3. Finalization.
372 mV2 ^= 0xff;
373 for (int i = 0; i < 3; i++)
374 sipRound();
375 return mV0 ^ mV1 ^ mV2 ^ mV3;
376 }
377
sipRoundSipHasher378 void sipRound()
379 {
380 mV0 += mV1;
381 mV1 = RotateLeft(mV1, 13);
382 mV1 ^= mV0;
383 mV0 = RotateLeft(mV0, 32);
384 mV2 += mV3;
385 mV3 = RotateLeft(mV3, 16);
386 mV3 ^= mV2;
387 mV0 += mV3;
388 mV3 = RotateLeft(mV3, 21);
389 mV3 ^= mV0;
390 mV2 += mV1;
391 mV1 = RotateLeft(mV1, 17);
392 mV1 ^= mV2;
393 mV2 = RotateLeft(mV2, 32);
394 }
395
396 uint64_t mV0, mV1, mV2, mV3;
397 };
398 };
399
400 } /* namespace mozilla */
401 #endif /* __cplusplus */
402
403 #endif /* mozilla_HashFunctions_h */
404