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
  59 namespace mozilla {
  60
  61 using HashNumber = uint32_t;
  62 static const uint32_t kHashNumberBits = 32;
  63
  64 /**
  65  * The golden ratio as a 32-bit fixed-point value.
  66  */
  67 static const HashNumber kGoldenRatioU32 = 0x9E3779B9U;
  68
  69 /*
  70  * Given a raw hash code, h, return a number that can be used to select a hash
  71  * bucket.
  72  *
  73  * This function aims to produce as uniform an output distribution as possible,
  74  * especially in the most significant (leftmost) bits, even though the input
  75  * distribution may be highly nonrandom, given the constraints that this must
  76  * be deterministic and quick to compute.
  77  *
  78  * Since the leftmost bits of the result are best, the hash bucket index is
  79  * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
  80  * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
  81  *
  82  * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
  83  */
  84 constexpr HashNumber
  85 ScrambleHashCode(HashNumber h)
  86 {
  87   /*
  88    * Simply returning h would not cause any hash tables to produce wrong
  89    * answers. But it can produce pathologically bad performance: The caller
  90    * right-shifts the result, keeping only the highest bits. The high bits of
  91    * hash codes are very often completely entropy-free. (So are the lowest
  92    * bits.)
  93    *
  94    * So we use Fibonacci hashing, as described in Knuth, The Art of Computer
  95    * Programming, 6.4. This mixes all the bits of the input hash code h.
  96    *
  97    * The value of goldenRatio is taken from the hex expansion of the golden
  98    * ratio, which starts 1.9E3779B9.... This value is especially good if
  99    * values with consecutive hash codes are stored in a hash table; see Knuth
 100    * for details.
 101    */
 102   return mozilla::WrappingMultiply(h, kGoldenRatioU32);
 103 }
 104
 105 namespace detail {
 106
 107 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
 108 constexpr HashNumber
 109 RotateLeft5(HashNumber aValue)
 110 {
 111   return (aValue << 5) | (aValue >> 27);
 112 }
 113
 114 constexpr HashNumber
 115 AddU32ToHash(HashNumber aHash, uint32_t aValue)
 116 {
 117   /*
 118    * This is the meat of all our hash routines.  This hash function is not
 119    * particularly sophisticated, but it seems to work well for our mostly
 120    * plain-text inputs.  Implementation notes follow.
 121    *
 122    * Our use of the golden ratio here is arbitrary; we could pick almost any
 123    * number which:
 124    *
 125    *  * is odd (because otherwise, all our hash values will be even)
 126    *
 127    *  * has a reasonably-even mix of 1's and 0's (consider the extreme case
 128    *    where we multiply by 0x3 or 0xeffffff -- this will not produce good
 129    *    mixing across all bits of the hash).
 130    *
 131    * The rotation length of 5 is also arbitrary, although an odd number is again
 132    * preferable so our hash explores the whole universe of possible rotations.
 133    *
 134    * Finally, we multiply by the golden ratio *after* xor'ing, not before.
 135    * Otherwise, if |aHash| is 0 (as it often is for the beginning of a
 136    * message), the expression
 137    *
 138    *   mozilla::WrappingMultiply(kGoldenRatioU32, RotateLeft5(aHash))
 139    *   |xor|
 140    *   aValue
 141    *
 142    * evaluates to |aValue|.
 143    *
 144    * (Number-theoretic aside: Because any odd number |m| is relatively prime to
 145    * our modulus (2**32), the list
 146    *
 147    *    [x * m (mod 2**32) for 0 <= x < 2**32]
 148    *
 149    * has no duplicate elements.  This means that multiplying by |m| does not
 150    * cause us to skip any possible hash values.
 151    *
 152    * It's also nice if |m| has large-ish order mod 2**32 -- that is, if the
 153    * smallest k such that m**k == 1 (mod 2**32) is large -- so we can safely
 154    * multiply our hash value by |m| a few times without negating the
 155    * multiplicative effect.  Our golden ratio constant has order 2**29, which is
 156    * more than enough for our purposes.)
 157    */
 158   return mozilla::WrappingMultiply(kGoldenRatioU32,
 159                                    RotateLeft5(aHash) ^ aValue);
 160 }
 161
 162 /**
 163  * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
 164  */
 165 template<size_t PtrSize>
 166 constexpr HashNumber
 167 AddUintptrToHash(HashNumber aHash, uintptr_t aValue)
 168 {
 169   return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
 170 }
 171
 172 template<>
 173 inline HashNumber
 174 AddUintptrToHash<8>(HashNumber aHash, uintptr_t aValue)
 175 {
 176   uint32_t v1 = static_cast<uint32_t>(aValue);
 177   uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(aValue) >> 32);
 178   return AddU32ToHash(AddU32ToHash(aHash, v1), v2);
 179 }
 180
 181 } /* namespace detail */
 182
 183 /**
 184  * AddToHash takes a hash and some values and returns a new hash based on the
 185  * inputs.
 186  *
 187  * Currently, we support hashing uint32_t's, values which we can implicitly
 188  * convert to uint32_t, data pointers, and function pointers.
 189  */
 190 template<typename T,
 191          bool TypeIsNotIntegral = !mozilla::IsIntegral<T>::value,
 192          typename U = typename mozilla::EnableIf<TypeIsNotIntegral>::Type>
 193 MOZ_MUST_USE inline HashNumber
 194 AddToHash(HashNumber aHash, T aA)
 195 {
 196   /*
 197    * Try to convert |A| to uint32_t implicitly.  If this works, great.  If not,
 198    * we'll error out.
 199    */
 200   return detail::AddU32ToHash(aHash, aA);
 201 }
 202
 203 template<typename A>
 204 MOZ_MUST_USE inline HashNumber
 205 AddToHash(HashNumber aHash, A* aA)
 206 {
 207   /*
 208    * You might think this function should just take a void*.  But then we'd only
 209    * catch data pointers and couldn't handle function pointers.
 210    */
 211
 212   static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
 213
 214   return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
 215 }
 216
 217 // We use AddUintptrToHash() for hashing all integral types.  8-byte integral types
 218 // are treated the same as 64-bit pointers, and smaller integral types are first
 219 // implicitly converted to 32 bits and then passed to AddUintptrToHash() to be hashed.
 220 template<typename T,
 221          typename U = typename mozilla::EnableIf<mozilla::IsIntegral<T>::value>::Type>
 222 MOZ_MUST_USE constexpr HashNumber
 223 AddToHash(HashNumber aHash, T aA)
 224 {
 225   return detail::AddUintptrToHash<sizeof(T)>(aHash, aA);
 226 }
 227
 228 template<typename A, typename... Args>
 229 MOZ_MUST_USE HashNumber
 230 AddToHash(HashNumber aHash, A aArg, Args... aArgs)
 231 {
 232   return AddToHash(AddToHash(aHash, aArg), aArgs...);
 233 }
 234
 235 /**
 236  * The HashGeneric class of functions let you hash one or more values.
 237  *
 238  * If you want to hash together two values x and y, calling HashGeneric(x, y) is
 239  * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
 240  * that x has already been hashed.
 241  */
 242 template<typename... Args>
 243 MOZ_MUST_USE inline HashNumber
 244 HashGeneric(Args... aArgs)
 245 {
 246   return AddToHash(0, aArgs...);
 247 }
 248
 249 namespace detail {
 250
 251 template<typename T>
 252 constexpr HashNumber
 253 HashUntilZero(const T* aStr)
 254 {
 255   HashNumber hash = 0;
 256   for (; T c = *aStr; aStr++) {
 257     hash = AddToHash(hash, c);
 258   }
 259   return hash;
 260 }
 261
 262 template<typename T>
 263 HashNumber
 264 HashKnownLength(const T* aStr, size_t aLength)
 265 {
 266   HashNumber hash = 0;
 267   for (size_t i = 0; i < aLength; i++) {
 268     hash = AddToHash(hash, aStr[i]);
 269   }
 270   return hash;
 271 }
 272
 273 } /* namespace detail */
 274
 275 /**
 276  * The HashString overloads below do just what you'd expect.
 277  *
 278  * If you have the string's length, you might as well call the overload which
 279  * includes the length.  It may be marginally faster.
 280  */
 281 MOZ_MUST_USE inline HashNumber
 282 HashString(const char* aStr)
 283 {
 284   return detail::HashUntilZero(reinterpret_cast<const unsigned char*>(aStr));
 285 }
 286
 287 MOZ_MUST_USE inline HashNumber
 288 HashString(const char* aStr, size_t aLength)
 289 {
 290   return detail::HashKnownLength(reinterpret_cast<const unsigned char*>(aStr), aLength);
 291 }
 292
 293 MOZ_MUST_USE
 294 inline HashNumber
 295 HashString(const unsigned char* aStr, size_t aLength)
 296 {
 297   return detail::HashKnownLength(aStr, aLength);
 298 }
 299
 300 // You may need to use the
 301 // MOZ_{PUSH,POP}_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING macros if you use
 302 // this function. See the comment on those macros' definitions for more detail.
 303 MOZ_MUST_USE constexpr HashNumber
 304 HashString(const char16_t* aStr)
 305 {
 306   return detail::HashUntilZero(aStr);
 307 }
 308
 309 MOZ_MUST_USE inline HashNumber
 310 HashString(const char16_t* aStr, size_t aLength)
 311 {
 312   return detail::HashKnownLength(aStr, aLength);
 313 }
 314
 315 /*
 316  * On Windows, wchar_t is not the same as char16_t, even though it's
 317  * the same width!
 318  */
 319 #ifdef WIN32
 320 MOZ_MUST_USE inline HashNumber
 321 HashString(const wchar_t* aStr)
 322 {
 323   return detail::HashUntilZero(aStr);
 324 }
 325
 326 MOZ_MUST_USE inline HashNumber
 327 HashString(const wchar_t* aStr, size_t aLength)
 328 {
 329   return detail::HashKnownLength(aStr, aLength);
 330 }
 331 #endif
 332
 333 /**
 334  * Hash some number of bytes.
 335  *
 336  * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
 337  * same result out of HashBytes as you would out of HashString.
 338  */
 339 MOZ_MUST_USE extern MFBT_API HashNumber
 340 HashBytes(const void* bytes, size_t aLength);
 341
 342 /**
 343  * A pseudorandom function mapping 32-bit integers to 32-bit integers.
 344  *
 345  * This is for when you're feeding private data (like pointer values or credit
 346  * card numbers) to a non-crypto hash function (like HashBytes) and then using
 347  * the hash code for something that untrusted parties could observe (like a JS
 348  * Map). Plug in a HashCodeScrambler before that last step to avoid leaking the
 349  * private data.
 350  *
 351  * By itself, this does not prevent hash-flooding DoS attacks, because an
 352  * attacker can still generate many values with exactly equal hash codes by
 353  * attacking the non-crypto hash function alone. Equal hash codes will, of
 354  * course, still be equal however much you scramble them.
 355  *
 356  * The algorithm is SipHash-1-3. See <https://131002.net/siphash/>.
 357  */
 358 class HashCodeScrambler
 359 {
 360   struct SipHasher;
 361
 362   uint64_t mK0, mK1;
 363
 364 public:
 365   /** Creates a new scrambler with the given 128-bit key. */
 366   constexpr HashCodeScrambler(uint64_t aK0, uint64_t aK1) : mK0(aK0), mK1(aK1) {}
 367
 368   /**
 369    * Scramble a hash code. Always produces the same result for the same
 370    * combination of key and hash code.
 371    */
 372   HashNumber scramble(HashNumber aHashCode) const
 373   {
 374     SipHasher hasher(mK0, mK1);
 375     return HashNumber(hasher.sipHash(aHashCode));
 376   }
 377
 378 private:
 379   struct SipHasher
 380   {
 381     SipHasher(uint64_t aK0, uint64_t aK1)
 382     {
 383       // 1. Initialization.
 384       mV0 = aK0 ^ UINT64_C(0x736f6d6570736575);
 385       mV1 = aK1 ^ UINT64_C(0x646f72616e646f6d);
 386       mV2 = aK0 ^ UINT64_C(0x6c7967656e657261);
 387       mV3 = aK1 ^ UINT64_C(0x7465646279746573);
 388     }
 389
 390     uint64_t sipHash(uint64_t aM)
 391     {
 392       // 2. Compression.
 393       mV3 ^= aM;
 394       sipRound();
 395       mV0 ^= aM;
 396
 397       // 3. Finalization.
 398       mV2 ^= 0xff;
 399       for (int i = 0; i < 3; i++)
 400         sipRound();
 401       return mV0 ^ mV1 ^ mV2 ^ mV3;
 402     }
 403
 404     void sipRound()
 405     {
 406       mV0 = WrappingAdd(mV0, mV1);
 407       mV1 = RotateLeft(mV1, 13);
 408       mV1 ^= mV0;
 409       mV0 = RotateLeft(mV0, 32);
 410       mV2 = WrappingAdd(mV2, mV3);
 411       mV3 = RotateLeft(mV3, 16);
 412       mV3 ^= mV2;
 413       mV0 = WrappingAdd(mV0, mV3);
 414       mV3 = RotateLeft(mV3, 21);
 415       mV3 ^= mV0;
 416       mV2 = WrappingAdd(mV2, mV1);
 417       mV1 = RotateLeft(mV1, 17);
 418       mV1 ^= mV2;
 419       mV2 = RotateLeft(mV2, 32);
 420     }
 421
 422     uint64_t mV0, mV1, mV2, mV3;
 423   };
 424 };
 425
 426 } /* namespace mozilla */
 427
 428 #endif /* mozilla_HashFunctions_h */