mfbt/HashFunctions.h

   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 uint32_t (a.k.a.
  11  * mozilla::HashNumber), including:
  12  *
  13  *  - HashString    Hash a char* or char16_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  *    HashNumber hash()
  36  *    {
  37  *      HashNumber 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 #include "mozilla/WrappingOperations.h"
  56
  57 #include <stdint.h>
  58 #include <type_traits>
  59
  60 namespace mozilla {
  61
  62 using HashNumber = uint32_t;
  63 static const uint32_t kHashNumberBits = 32;
  64
  65 /**
  66  * The golden ratio as a 32-bit fixed-point value.
  67  */
  68 static const HashNumber kGoldenRatioU32 = 0x9E3779B9U;
  69
  70 /*
  71  * Given a raw hash code, h, return a number that can be used to select a hash
  72  * bucket.
  73  *
  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.
  78  *
  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.
  82  *
  83  * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
  84  */
  85 constexpr HashNumber ScrambleHashCode(HashNumber h) {
  86   /*
  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
  91    * bits.)
  92    *
  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.
  95    *
  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
  99    * for details.
 100    */
 101   return mozilla::WrappingMultiply(h, kGoldenRatioU32);
 102 }
 103
 104 namespace detail {
 105
 106 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
 107 constexpr HashNumber RotateLeft5(HashNumber aValue) {
 108   return (aValue << 5) | (aValue >> 27);
 109 }
 110
 111 constexpr HashNumber AddU32ToHash(HashNumber aHash, uint32_t aValue) {
 112   /*
 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.
 116    *
 117    * Our use of the golden ratio here is arbitrary; we could pick almost any
 118    * number which:
 119    *
 120    *  * is odd (because otherwise, all our hash values will be even)
 121    *
 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).
 125    *
 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.
 128    *
 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
 132    *
 133    *   mozilla::WrappingMultiply(kGoldenRatioU32, RotateLeft5(aHash))
 134    *   |xor|
 135    *   aValue
 136    *
 137    * evaluates to |aValue|.
 138    *
 139    * (Number-theoretic aside: Because any odd number |m| is relatively prime to
 140    * our modulus (2**32), the list
 141    *
 142    *    [x * m (mod 2**32) for 0 <= x < 2**32]
 143    *
 144    * has no duplicate elements.  This means that multiplying by |m| does not
 145    * cause us to skip any possible hash values.
 146    *
 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.)
 152    */
 153   return mozilla::WrappingMultiply(kGoldenRatioU32,
 154                                    RotateLeft5(aHash) ^ aValue);
 155 }
 156
 157 /**
 158  * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
 159  */
 160 template <size_t PtrSize>
 161 constexpr HashNumber AddUintptrToHash(HashNumber aHash, uintptr_t aValue) {
 162   return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
 163 }
 164
 165 template <>
 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);
 170 }
 171
 172 } /* namespace detail */
 173
 174 /**
 175  * AddToHash takes a hash and some values and returns a new hash based on the
 176  * inputs.
 177  *
 178  * Currently, we support hashing uint32_t's, values which we can implicitly
 179  * convert to uint32_t, data pointers, and function pointers.
 180  */
 181 template <typename T, bool TypeIsNotIntegral = !std::is_integral_v<T>,
 182           bool TypeIsNotEnum = !std::is_enum_v<T>,
 183           std::enable_if_t<TypeIsNotIntegral && TypeIsNotEnum, int> = 0>
 184 MOZ_MUST_USE inline HashNumber AddToHash(HashNumber aHash, T aA) {
 185   /*
 186    * Try to convert |A| to uint32_t implicitly.  If this works, great.  If not,
 187    * we'll error out.
 188    */
 189   return detail::AddU32ToHash(aHash, aA);
 190 }
 191
 192 template <typename A>
 193 MOZ_MUST_USE inline HashNumber AddToHash(HashNumber aHash, A* aA) {
 194   /*
 195    * You might think this function should just take a void*.  But then we'd only
 196    * catch data pointers and couldn't handle function pointers.
 197    */
 198
 199   static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
 200
 201   return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
 202 }
 203
 204 // We use AddUintptrToHash() for hashing all integral types.  8-byte integral
 205 // types are treated the same as 64-bit pointers, and smaller integral types are
 206 // first implicitly converted to 32 bits and then passed to AddUintptrToHash()
 207 // to be hashed.
 208 template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
 209 MOZ_MUST_USE constexpr HashNumber AddToHash(HashNumber aHash, T aA) {
 210   return detail::AddUintptrToHash<sizeof(T)>(aHash, aA);
 211 }
 212
 213 template <typename T, std::enable_if_t<std::is_enum_v<T>, int> = 0>
 214 MOZ_MUST_USE constexpr HashNumber AddToHash(HashNumber aHash, T aA) {
 215   // Hash using AddUintptrToHash with the underlying type of the enum type
 216   using UnderlyingType = typename std::underlying_type<T>::type;
 217   return detail::AddUintptrToHash<sizeof(UnderlyingType)>(
 218       aHash, static_cast<UnderlyingType>(aA));
 219 }
 220
 221 template <typename A, typename... Args>
 222 MOZ_MUST_USE HashNumber AddToHash(HashNumber aHash, A aArg, Args... aArgs) {
 223   return AddToHash(AddToHash(aHash, aArg), aArgs...);
 224 }
 225
 226 /**
 227  * The HashGeneric class of functions let you hash one or more values.
 228  *
 229  * If you want to hash together two values x and y, calling HashGeneric(x, y) is
 230  * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
 231  * that x has already been hashed.
 232  */
 233 template <typename... Args>
 234 MOZ_MUST_USE inline HashNumber HashGeneric(Args... aArgs) {
 235   return AddToHash(0, aArgs...);
 236 }
 237
 238 /**
 239  * Hash successive |*aIter| until |!*aIter|, i.e. til null-termination.
 240  *
 241  * This function is *not* named HashString like the non-template overloads
 242  * below.  Some users define HashString overloads and pass inexactly-matching
 243  * values to them -- but an inexactly-matching value would match this overload
 244  * instead!  We follow the general rule and don't mix and match template and
 245  * regular overloads to avoid this.
 246  *
 247  * If you have the string's length, call HashStringKnownLength: it may be
 248  * marginally faster.
 249  */
 250 template <typename Iterator>
 251 MOZ_MUST_USE constexpr HashNumber HashStringUntilZero(Iterator aIter) {
 252   HashNumber hash = 0;
 253   for (; auto c = *aIter; ++aIter) {
 254     hash = AddToHash(hash, c);
 255   }
 256   return hash;
 257 }
 258
 259 /**
 260  * Hash successive |aIter[i]| up to |i == aLength|.
 261  */
 262 template <typename Iterator>
 263 MOZ_MUST_USE constexpr HashNumber HashStringKnownLength(Iterator aIter,
 264                                                         size_t aLength) {
 265   HashNumber hash = 0;
 266   for (size_t i = 0; i < aLength; i++) {
 267     hash = AddToHash(hash, aIter[i]);
 268   }
 269   return hash;
 270 }
 271
 272 /**
 273  * The HashString overloads below do just what you'd expect.
 274  *
 275  * These functions are non-template functions so that users can 1) overload them
 276  * with their own types 2) in a way that allows implicit conversions to happen.
 277  */
 278 MOZ_MUST_USE inline HashNumber HashString(const char* aStr) {
 279   // Use the |const unsigned char*| version of the above so that all ordinary
 280   // character data hashes identically.
 281   return HashStringUntilZero(reinterpret_cast<const unsigned char*>(aStr));
 282 }
 283
 284 MOZ_MUST_USE inline HashNumber HashString(const char* aStr, size_t aLength) {
 285   // Delegate to the |const unsigned char*| version of the above to share
 286   // template instantiations.
 287   return HashStringKnownLength(reinterpret_cast<const unsigned char*>(aStr),
 288                                aLength);
 289 }
 290
 291 MOZ_MUST_USE
 292 inline HashNumber HashString(const unsigned char* aStr, size_t aLength) {
 293   return HashStringKnownLength(aStr, aLength);
 294 }
 295
 296 MOZ_MUST_USE constexpr HashNumber HashString(const char16_t* aStr) {
 297   return HashStringUntilZero(aStr);
 298 }
 299
 300 MOZ_MUST_USE inline HashNumber HashString(const char16_t* aStr,
 301                                           size_t aLength) {
 302   return HashStringKnownLength(aStr, aLength);
 303 }
 304
 305 /**
 306  * HashString overloads for |wchar_t| on platforms where it isn't |char16_t|.
 307  */
 308 template <typename WCharT, typename = typename std::enable_if<
 309                                std::is_same<WCharT, wchar_t>::value &&
 310                                !std::is_same<wchar_t, char16_t>::value>::type>
 311 MOZ_MUST_USE inline HashNumber HashString(const WCharT* aStr) {
 312   return HashStringUntilZero(aStr);
 313 }
 314
 315 template <typename WCharT, typename = typename std::enable_if<
 316                                std::is_same<WCharT, wchar_t>::value &&
 317                                !std::is_same<wchar_t, char16_t>::value>::type>
 318 MOZ_MUST_USE inline HashNumber HashString(const WCharT* aStr, size_t aLength) {
 319   return HashStringKnownLength(aStr, aLength);
 320 }
 321
 322 /**
 323  * Hash some number of bytes.
 324  *
 325  * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
 326  * same result out of HashBytes as you would out of HashString.
 327  */
 328 MOZ_MUST_USE extern MFBT_API HashNumber HashBytes(const void* bytes,
 329                                                   size_t aLength);
 330
 331 /**
 332  * A pseudorandom function mapping 32-bit integers to 32-bit integers.
 333  *
 334  * This is for when you're feeding private data (like pointer values or credit
 335  * card numbers) to a non-crypto hash function (like HashBytes) and then using
 336  * the hash code for something that untrusted parties could observe (like a JS
 337  * Map). Plug in a HashCodeScrambler before that last step to avoid leaking the
 338  * private data.
 339  *
 340  * By itself, this does not prevent hash-flooding DoS attacks, because an
 341  * attacker can still generate many values with exactly equal hash codes by
 342  * attacking the non-crypto hash function alone. Equal hash codes will, of
 343  * course, still be equal however much you scramble them.
 344  *
 345  * The algorithm is SipHash-1-3. See <https://131002.net/siphash/>.
 346  */
 347 class HashCodeScrambler {
 348   struct SipHasher;
 349
 350   uint64_t mK0, mK1;
 351
 352  public:
 353   /** Creates a new scrambler with the given 128-bit key. */
 354   constexpr HashCodeScrambler(uint64_t aK0, uint64_t aK1)
 355       : mK0(aK0), mK1(aK1) {}
 356
 357   /**
 358    * Scramble a hash code. Always produces the same result for the same
 359    * combination of key and hash code.
 360    */
 361   HashNumber scramble(HashNumber aHashCode) const {
 362     SipHasher hasher(mK0, mK1);
 363     return HashNumber(hasher.sipHash(aHashCode));
 364   }
 365
 366  private:
 367   struct SipHasher {
 368     SipHasher(uint64_t aK0, uint64_t aK1) {
 369       // 1. Initialization.
 370       mV0 = aK0 ^ UINT64_C(0x736f6d6570736575);
 371       mV1 = aK1 ^ UINT64_C(0x646f72616e646f6d);
 372       mV2 = aK0 ^ UINT64_C(0x6c7967656e657261);
 373       mV3 = aK1 ^ UINT64_C(0x7465646279746573);
 374     }
 375
 376     uint64_t sipHash(uint64_t aM) {
 377       // 2. Compression.
 378       mV3 ^= aM;
 379       sipRound();
 380       mV0 ^= aM;
 381
 382       // 3. Finalization.
 383       mV2 ^= 0xff;
 384       for (int i = 0; i < 3; i++) sipRound();
 385       return mV0 ^ mV1 ^ mV2 ^ mV3;
 386     }
 387
 388     void sipRound() {
 389       mV0 = WrappingAdd(mV0, mV1);
 390       mV1 = RotateLeft(mV1, 13);
 391       mV1 ^= mV0;
 392       mV0 = RotateLeft(mV0, 32);
 393       mV2 = WrappingAdd(mV2, mV3);
 394       mV3 = RotateLeft(mV3, 16);
 395       mV3 ^= mV2;
 396       mV0 = WrappingAdd(mV0, mV3);
 397       mV3 = RotateLeft(mV3, 21);
 398       mV3 ^= mV0;
 399       mV2 = WrappingAdd(mV2, mV1);
 400       mV1 = RotateLeft(mV1, 17);
 401       mV1 ^= mV2;
 402       mV2 = RotateLeft(mV2, 32);
 403     }
 404
 405     uint64_t mV0, mV1, mV2, mV3;
 406   };
 407 };
 408
 409 } /* namespace mozilla */
 410
 411 #endif /* mozilla_HashFunctions_h */