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/. */
7 /* Utilities for hashing. */
10 * This file exports functions for hashing data down to a uint32_t (a.k.a.
11 * mozilla::HashNumber), including:
13 * - HashString Hash a char* or char16_t/wchar_t* of known or unknown
16 * - HashBytes Hash a byte array of known length.
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.
22 * - AddToHash Add one or more values to the given hash. This supports the
23 * same list of types as HashGeneric.
26 * You can chain these functions together to hash complex objects. For example:
31 * uint32_t mUint1, mUint2;
32 * void (*mCallbackFn)();
37 * HashNumber hash = HashString(mStr);
38 * hash = AddToHash(hash, mUint1, mUint2);
39 * return AddToHash(hash, mCallbackFn);
43 * If you want to hash an nsAString or nsACString, use the HashString functions
47 #ifndef mozilla_HashFunctions_h
48 #define mozilla_HashFunctions_h
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 #include "mozilla/WrappingOperations.h"
58 #include <type_traits>
62 using HashNumber
= uint32_t;
63 static const uint32_t kHashNumberBits
= 32;
66 * The golden ratio as a 32-bit fixed-point value.
68 static const HashNumber kGoldenRatioU32
= 0x9E3779B9U
;
71 * Given a raw hash code, h, return a number that can be used to select a hash
74 * This function aims to produce as uniform an output distribution as possible,
75 * especially in the most significant (leftmost) bits, even though the input
76 * distribution may be highly nonrandom, given the constraints that this must
77 * be deterministic and quick to compute.
79 * Since the leftmost bits of the result are best, the hash bucket index is
80 * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
81 * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
83 * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
85 constexpr HashNumber
ScrambleHashCode(HashNumber h
) {
87 * Simply returning h would not cause any hash tables to produce wrong
88 * answers. But it can produce pathologically bad performance: The caller
89 * right-shifts the result, keeping only the highest bits. The high bits of
90 * hash codes are very often completely entropy-free. (So are the lowest
93 * So we use Fibonacci hashing, as described in Knuth, The Art of Computer
94 * Programming, 6.4. This mixes all the bits of the input hash code h.
96 * The value of goldenRatio is taken from the hex expansion of the golden
97 * ratio, which starts 1.9E3779B9.... This value is especially good if
98 * values with consecutive hash codes are stored in a hash table; see Knuth
101 return mozilla::WrappingMultiply(h
, kGoldenRatioU32
);
106 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
107 constexpr HashNumber
RotateLeft5(HashNumber aValue
) {
108 return (aValue
<< 5) | (aValue
>> 27);
111 constexpr HashNumber
AddU32ToHash(HashNumber aHash
, uint32_t aValue
) {
113 * This is the meat of all our hash routines. This hash function is not
114 * particularly sophisticated, but it seems to work well for our mostly
115 * plain-text inputs. Implementation notes follow.
117 * Our use of the golden ratio here is arbitrary; we could pick almost any
120 * * is odd (because otherwise, all our hash values will be even)
122 * * has a reasonably-even mix of 1's and 0's (consider the extreme case
123 * where we multiply by 0x3 or 0xeffffff -- this will not produce good
124 * mixing across all bits of the hash).
126 * The rotation length of 5 is also arbitrary, although an odd number is again
127 * preferable so our hash explores the whole universe of possible rotations.
129 * Finally, we multiply by the golden ratio *after* xor'ing, not before.
130 * Otherwise, if |aHash| is 0 (as it often is for the beginning of a
131 * message), the expression
133 * mozilla::WrappingMultiply(kGoldenRatioU32, RotateLeft5(aHash))
137 * evaluates to |aValue|.
139 * (Number-theoretic aside: Because any odd number |m| is relatively prime to
140 * our modulus (2**32), the list
142 * [x * m (mod 2**32) for 0 <= x < 2**32]
144 * has no duplicate elements. This means that multiplying by |m| does not
145 * cause us to skip any possible hash values.
147 * It's also nice if |m| has large-ish order mod 2**32 -- that is, if the
148 * smallest k such that m**k == 1 (mod 2**32) is large -- so we can safely
149 * multiply our hash value by |m| a few times without negating the
150 * multiplicative effect. Our golden ratio constant has order 2**29, which is
151 * more than enough for our purposes.)
153 return mozilla::WrappingMultiply(kGoldenRatioU32
,
154 RotateLeft5(aHash
) ^ aValue
);
158 * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
160 template <size_t PtrSize
>
161 constexpr HashNumber
AddUintptrToHash(HashNumber aHash
, uintptr_t aValue
) {
162 return AddU32ToHash(aHash
, static_cast<uint32_t>(aValue
));
166 inline HashNumber AddUintptrToHash
<8>(HashNumber aHash
, uintptr_t aValue
) {
167 uint32_t v1
= static_cast<uint32_t>(aValue
);
168 uint32_t v2
= static_cast<uint32_t>(static_cast<uint64_t>(aValue
) >> 32);
169 return AddU32ToHash(AddU32ToHash(aHash
, v1
), v2
);
172 } /* namespace detail */
175 * AddToHash takes a hash and some values and returns a new hash based on the
178 * Currently, we support hashing uint32_t's, values which we can implicitly
179 * convert to uint32_t, data pointers, and function pointers.
181 template <typename T
, bool TypeIsNotIntegral
= !mozilla::IsIntegral
<T
>::value
,
182 typename U
= typename
mozilla::EnableIf
<TypeIsNotIntegral
>::Type
>
183 MOZ_MUST_USE
inline HashNumber
AddToHash(HashNumber aHash
, T aA
) {
185 * Try to convert |A| to uint32_t implicitly. If this works, great. If not,
188 return detail::AddU32ToHash(aHash
, aA
);
191 template <typename A
>
192 MOZ_MUST_USE
inline HashNumber
AddToHash(HashNumber aHash
, A
* aA
) {
194 * You might think this function should just take a void*. But then we'd only
195 * catch data pointers and couldn't handle function pointers.
198 static_assert(sizeof(aA
) == sizeof(uintptr_t), "Strange pointer!");
200 return detail::AddUintptrToHash
<sizeof(uintptr_t)>(aHash
, uintptr_t(aA
));
203 // We use AddUintptrToHash() for hashing all integral types. 8-byte integral
204 // types are treated the same as 64-bit pointers, and smaller integral types are
205 // first implicitly converted to 32 bits and then passed to AddUintptrToHash()
207 template <typename T
, typename U
= typename
mozilla::EnableIf
<
208 mozilla::IsIntegral
<T
>::value
>::Type
>
209 MOZ_MUST_USE
constexpr HashNumber
AddToHash(HashNumber aHash
, T aA
) {
210 return detail::AddUintptrToHash
<sizeof(T
)>(aHash
, aA
);
213 template <typename A
, typename
... Args
>
214 MOZ_MUST_USE HashNumber
AddToHash(HashNumber aHash
, A aArg
, Args
... aArgs
) {
215 return AddToHash(AddToHash(aHash
, aArg
), aArgs
...);
219 * The HashGeneric class of functions let you hash one or more values.
221 * If you want to hash together two values x and y, calling HashGeneric(x, y) is
222 * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
223 * that x has already been hashed.
225 template <typename
... Args
>
226 MOZ_MUST_USE
inline HashNumber
HashGeneric(Args
... aArgs
) {
227 return AddToHash(0, aArgs
...);
231 * Hash successive |*aIter| until |!*aIter|, i.e. til null-termination.
233 * This function is *not* named HashString like the non-template overloads
234 * below. Some users define HashString overloads and pass inexactly-matching
235 * values to them -- but an inexactly-matching value would match this overload
236 * instead! We follow the general rule and don't mix and match template and
237 * regular overloads to avoid this.
239 * If you have the string's length, call HashStringKnownLength: it may be
242 template <typename Iterator
>
243 MOZ_MUST_USE
constexpr HashNumber
HashStringUntilZero(Iterator aIter
) {
245 for (; auto c
= *aIter
; ++aIter
) {
246 hash
= AddToHash(hash
, c
);
252 * Hash successive |aIter[i]| up to |i == aLength|.
254 template <typename Iterator
>
255 MOZ_MUST_USE
constexpr HashNumber
HashStringKnownLength(Iterator aIter
,
258 for (size_t i
= 0; i
< aLength
; i
++) {
259 hash
= AddToHash(hash
, aIter
[i
]);
265 * The HashString overloads below do just what you'd expect.
267 * These functions are non-template functions so that users can 1) overload them
268 * with their own types 2) in a way that allows implicit conversions to happen.
270 MOZ_MUST_USE
inline HashNumber
HashString(const char* aStr
) {
271 // Use the |const unsigned char*| version of the above so that all ordinary
272 // character data hashes identically.
273 return HashStringUntilZero(reinterpret_cast<const unsigned char*>(aStr
));
276 MOZ_MUST_USE
inline HashNumber
HashString(const char* aStr
, size_t aLength
) {
277 // Delegate to the |const unsigned char*| version of the above to share
278 // template instantiations.
279 return HashStringKnownLength(reinterpret_cast<const unsigned char*>(aStr
),
284 inline HashNumber
HashString(const unsigned char* aStr
, size_t aLength
) {
285 return HashStringKnownLength(aStr
, aLength
);
288 // You may need to use the
289 // MOZ_{PUSH,POP}_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING macros if you use
290 // this function. See the comment on those macros' definitions for more detail.
291 MOZ_MUST_USE
constexpr HashNumber
HashString(const char16_t
* aStr
) {
292 return HashStringUntilZero(aStr
);
295 MOZ_MUST_USE
inline HashNumber
HashString(const char16_t
* aStr
,
297 return HashStringKnownLength(aStr
, aLength
);
301 * HashString overloads for |wchar_t| on platforms where it isn't |char16_t|.
303 template <typename WCharT
, typename
= typename
std::enable_if
<
304 std::is_same
<WCharT
, wchar_t>::value
&&
305 !std::is_same
<wchar_t, char16_t
>::value
>::type
>
306 MOZ_MUST_USE
inline HashNumber
HashString(const WCharT
* aStr
) {
307 return HashStringUntilZero(aStr
);
310 template <typename WCharT
, typename
= typename
std::enable_if
<
311 std::is_same
<WCharT
, wchar_t>::value
&&
312 !std::is_same
<wchar_t, char16_t
>::value
>::type
>
313 MOZ_MUST_USE
inline HashNumber
HashString(const WCharT
* aStr
, size_t aLength
) {
314 return HashStringKnownLength(aStr
, aLength
);
318 * Hash some number of bytes.
320 * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
321 * same result out of HashBytes as you would out of HashString.
323 MOZ_MUST_USE
extern MFBT_API HashNumber
HashBytes(const void* bytes
,
327 * A pseudorandom function mapping 32-bit integers to 32-bit integers.
329 * This is for when you're feeding private data (like pointer values or credit
330 * card numbers) to a non-crypto hash function (like HashBytes) and then using
331 * the hash code for something that untrusted parties could observe (like a JS
332 * Map). Plug in a HashCodeScrambler before that last step to avoid leaking the
335 * By itself, this does not prevent hash-flooding DoS attacks, because an
336 * attacker can still generate many values with exactly equal hash codes by
337 * attacking the non-crypto hash function alone. Equal hash codes will, of
338 * course, still be equal however much you scramble them.
340 * The algorithm is SipHash-1-3. See <https://131002.net/siphash/>.
342 class HashCodeScrambler
{
348 /** Creates a new scrambler with the given 128-bit key. */
349 constexpr HashCodeScrambler(uint64_t aK0
, uint64_t aK1
)
350 : mK0(aK0
), mK1(aK1
) {}
353 * Scramble a hash code. Always produces the same result for the same
354 * combination of key and hash code.
356 HashNumber
scramble(HashNumber aHashCode
) const {
357 SipHasher
hasher(mK0
, mK1
);
358 return HashNumber(hasher
.sipHash(aHashCode
));
363 SipHasher(uint64_t aK0
, uint64_t aK1
) {
364 // 1. Initialization.
365 mV0
= aK0
^ UINT64_C(0x736f6d6570736575);
366 mV1
= aK1
^ UINT64_C(0x646f72616e646f6d);
367 mV2
= aK0
^ UINT64_C(0x6c7967656e657261);
368 mV3
= aK1
^ UINT64_C(0x7465646279746573);
371 uint64_t sipHash(uint64_t aM
) {
379 for (int i
= 0; i
< 3; i
++) sipRound();
380 return mV0
^ mV1
^ mV2
^ mV3
;
384 mV0
= WrappingAdd(mV0
, mV1
);
385 mV1
= RotateLeft(mV1
, 13);
387 mV0
= RotateLeft(mV0
, 32);
388 mV2
= WrappingAdd(mV2
, mV3
);
389 mV3
= RotateLeft(mV3
, 16);
391 mV0
= WrappingAdd(mV0
, mV3
);
392 mV3
= RotateLeft(mV3
, 21);
394 mV2
= WrappingAdd(mV2
, mV1
);
395 mV1
= RotateLeft(mV1
, 17);
397 mV2
= RotateLeft(mV2
, 32);
400 uint64_t mV0
, mV1
, mV2
, mV3
;
404 } /* namespace mozilla */
406 #endif /* mozilla_HashFunctions_h */