/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ /* vim: set ts=8 sts=2 et sw=2 tw=80: */ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/* Utilities for hashing. */
/* * This file exports functions for hashing data down to a uint32_t (a.k.a. * mozilla::HashNumber), including: * * - HashString Hash a char* or char16_t/wchar_t* of known or unknown * length. * * - HashBytes Hash a byte array of known length. * * - HashGeneric Hash one or more values. Currently, we support uint32_t, * types which can be implicitly cast to uint32_t, data * pointers, and function pointers. * * - AddToHash Add one or more values to the given hash. This supports the * same list of types as HashGeneric. * * * You can chain these functions together to hash complex objects. For example: * * class ComplexObject * { * char* mStr; * uint32_t mUint1, mUint2; * void (*mCallbackFn)(); * * public: * HashNumber hash() * { * HashNumber hash = HashString(mStr); * hash = AddToHash(hash, mUint1, mUint2); * return AddToHash(hash, mCallbackFn); * } * }; * * If you want to hash an nsAString or nsACString, use the HashString functions * in nsHashKeys.h.
*/
using HashNumber = uint32_t; staticconst uint32_t kHashNumberBits = 32;
/** * The golden ratio as a 32-bit fixed-point value.
*/ staticconst HashNumber kGoldenRatioU32 = 0x9E3779B9U;
/* * Given a raw hash code, h, return a number that can be used to select a hash * bucket. * * This function aims to produce as uniform an output distribution as possible, * especially in the most significant (leftmost) bits, even though the input * distribution may be highly nonrandom, given the constraints that this must * be deterministic and quick to compute. * * Since the leftmost bits of the result are best, the hash bucket index is * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
*/
constexpr HashNumber ScrambleHashCode(HashNumber h) { /* * Simply returning h would not cause any hash tables to produce wrong * answers. But it can produce pathologically bad performance: The caller * right-shifts the result, keeping only the highest bits. The high bits of * hash codes are very often completely entropy-free. (So are the lowest * bits.) * * So we use Fibonacci hashing, as described in Knuth, The Art of Computer * Programming, 6.4. This mixes all the bits of the input hash code h. * * The value of goldenRatio is taken from the hex expansion of the golden * ratio, which starts 1.9E3779B9.... This value is especially good if * values with consecutive hash codes are stored in a hash table; see Knuth * for details.
*/ return mozilla::WrappingMultiply(h, kGoldenRatioU32);
}
constexpr HashNumber AddU32ToHash(HashNumber aHash, uint32_t aValue) { /* * This is the meat of all our hash routines. This hash function is not * particularly sophisticated, but it seems to work well for our mostly * plain-text inputs. Implementation notes follow. * * Our use of the golden ratio here is arbitrary; we could pick almost any * number which: * * * is odd (because otherwise, all our hash values will be even) * * * has a reasonably-even mix of 1's and 0's (consider the extreme case * where we multiply by 0x3 or 0xeffffff -- this will not produce good * mixing across all bits of the hash). * * The rotation length of 5 is also arbitrary, although an odd number is again * preferable so our hash explores the whole universe of possible rotations. * * Finally, we multiply by the golden ratio *after* xor'ing, not before. * Otherwise, if |aHash| is 0 (as it often is for the beginning of a * message), the expression * * mozilla::WrappingMultiply(kGoldenRatioU32, RotateLeft5(aHash)) * |xor| * aValue * * evaluates to |aValue|. * * (Number-theoretic aside: Because any odd number |m| is relatively prime to * our modulus (2**32), the list * * [x * m (mod 2**32) for 0 <= x < 2**32] * * has no duplicate elements. This means that multiplying by |m| does not * cause us to skip any possible hash values. * * It's also nice if |m| has large-ish order mod 2**32 -- that is, if the * smallest k such that m**k == 1 (mod 2**32) is large -- so we can safely * multiply our hash value by |m| a few times without negating the * multiplicative effect. Our golden ratio constant has order 2**29, which is * more than enough for our purposes.)
*/ return mozilla::WrappingMultiply(kGoldenRatioU32,
RotateLeft5(aHash) ^ aValue);
}
/** * AddUintNToHash takes sizeof(int_type) as a template parameter. * Changes to these functions need to be propagated to * MacroAssembler::prepareHashNonGCThing, which inlines them manually for * the JIT.
*/ template <size_t Size>
constexpr HashNumber AddUintNToHash(HashNumber aHash, uint64_t aValue) { return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
}
/** * AddToHash takes a hash and some values and returns a new hash based on the * inputs. * * Currently, we support hashing uint32_t's, values which we can implicitly * convert to uint32_t, data pointers, and function pointers.
*/ template <typename T, bool TypeIsNotIntegral = !std::is_integral_v<T>, bool TypeIsNotEnum = !std::is_enum_v<T>,
std::enable_if_t<TypeIsNotIntegral && TypeIsNotEnum, int> = 0>
[[nodiscard]] inline HashNumber AddToHash(HashNumber aHash, T aA) { /* * Try to convert |A| to uint32_t implicitly. If this works, great. If not, * we'll error out.
*/ return detail::AddU32ToHash(aHash, aA);
}
template <typename A>
[[nodiscard]] inline HashNumber AddToHash(HashNumber aHash, A* aA) { /* * You might think this function should just take a void*. But then we'd only * catch data pointers and couldn't handle function pointers.
*/
// We use AddUintNToHash() for hashing all integral types. 8-byte integral // types are treated the same as 64-bit pointers, and smaller integral types are // first implicitly converted to 32 bits and then passed to AddUintNToHash() // to be hashed. template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
[[nodiscard]] constexpr HashNumber AddToHash(HashNumber aHash, T aA) { return detail::AddUintNToHash<sizeof(T)>(aHash, aA);
}
template <typename T, std::enable_if_t<std::is_enum_v<T>, int> = 0>
[[nodiscard]] constexpr HashNumber AddToHash(HashNumber aHash, T aA) { // Hash using AddUintNToHash with the underlying type of the enum type using UnderlyingType = typename std::underlying_type<T>::type; return detail::AddUintNToHash<sizeof(UnderlyingType)>(
aHash, static_cast<UnderlyingType>(aA));
}
template <typename A, typename... Args>
[[nodiscard]] HashNumber AddToHash(HashNumber aHash, A aArg, Args... aArgs) { return AddToHash(AddToHash(aHash, aArg), aArgs...);
}
/** * The HashGeneric class of functions let you hash one or more values. * * If you want to hash together two values x and y, calling HashGeneric(x, y) is * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes * that x has already been hashed.
*/ template <typename... Args>
[[nodiscard]] inline HashNumber HashGeneric(Args... aArgs) { return AddToHash(0, aArgs...);
}
/** * Hash successive |*aIter| until |!*aIter|, i.e. til null-termination. * * This function is *not* named HashString like the non-template overloads * below. Some users define HashString overloads and pass inexactly-matching * values to them -- but an inexactly-matching value would match this overload * instead! We follow the general rule and don't mix and match template and * regular overloads to avoid this. * * If you have the string's length, call HashStringKnownLength: it may be * marginally faster.
*/ template <typename Iterator>
[[nodiscard]] constexpr HashNumber HashStringUntilZero(Iterator aIter) {
HashNumber hash = 0; for (; auto c = *aIter; ++aIter) {
hash = AddToHash(hash, c);
} return hash;
}
/** * Hash successive |aIter[i]| up to |i == aLength|.
*/ template <typename Iterator>
[[nodiscard]] constexpr HashNumber HashStringKnownLength(Iterator aIter,
size_t aLength) {
HashNumber hash = 0; for (size_t i = 0; i < aLength; i++) {
hash = AddToHash(hash, aIter[i]);
} return hash;
}
/** * The HashString overloads below do just what you'd expect. * * These functions are non-template functions so that users can 1) overload them * with their own types 2) in a way that allows implicit conversions to happen.
*/
[[nodiscard]] inline HashNumber HashString(constchar* aStr) { // Use the |const unsigned char*| version of the above so that all ordinary // character data hashes identically. return HashStringUntilZero(reinterpret_cast<constunsignedchar*>(aStr));
}
[[nodiscard]] inline HashNumber HashString(constchar* aStr, size_t aLength) { // Delegate to the |const unsigned char*| version of the above to share // template instantiations. return HashStringKnownLength(reinterpret_cast<constunsignedchar*>(aStr),
aLength);
}
/** * Hash some number of bytes. * * This hash walks word-by-word, rather than byte-by-byte, so you won't get the * same result out of HashBytes as you would out of HashString.
*/
[[nodiscard]] extern MFBT_API HashNumber HashBytes(constvoid* bytes,
size_t aLength);
/** * A pseudorandom function mapping 32-bit integers to 32-bit integers. * * This is for when you're feeding private data (like pointer values or credit * card numbers) to a non-crypto hash function (like HashBytes) and then using * the hash code for something that untrusted parties could observe (like a JS * Map). Plug in a HashCodeScrambler before that last step to avoid leaking the * private data. * * By itself, this does not prevent hash-flooding DoS attacks, because an * attacker can still generate many values with exactly equal hash codes by * attacking the non-crypto hash function alone. Equal hash codes will, of * course, still be equal however much you scramble them. * * The algorithm is SipHash-1-3. See <https://131002.net/siphash/>.
*/ class HashCodeScrambler { struct SipHasher;
uint64_t mK0, mK1;
public: /** Creates a new scrambler with the given 128-bit key. */
constexpr HashCodeScrambler(uint64_t aK0, uint64_t aK1)
: mK0(aK0), mK1(aK1) {}
/** * Scramble a hash code. Always produces the same result for the same * combination of key and hash code.
*/
HashNumber scramble(HashNumber aHashCode) const {
SipHasher hasher(mK0, mK1); return HashNumber(hasher.sipHash(aHashCode));
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
