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 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/Types.h"
  54
  55 #include <stdint.h>
  56
  57 #ifdef __cplusplus
  58 namespace mozilla {
  59
  60 /**
  61  * The golden ratio as a 32-bit fixed-point value.
  62  */
  63 static const uint32_t kGoldenRatioU32 = 0x9E3779B9U;
  64
  65 inline uint32_t
  66 RotateBitsLeft32(uint32_t aValue, uint8_t aBits)
  67 {
  68   MOZ_ASSERT(aBits < 32);
  69   return (aValue << aBits) | (aValue >> (32 - aBits));
  70 }
  71
  72 namespace detail {
  73
  74 inline uint32_t
  75 AddU32ToHash(uint32_t aHash, uint32_t aValue)
  76 {
  77   /*
  78    * This is the meat of all our hash routines.  This hash function is not
  79    * particularly sophisticated, but it seems to work well for our mostly
  80    * plain-text inputs.  Implementation notes follow.
  81    *
  82    * Our use of the golden ratio here is arbitrary; we could pick almost any
  83    * number which:
  84    *
  85    *  * is odd (because otherwise, all our hash values will be even)
  86    *
  87    *  * has a reasonably-even mix of 1's and 0's (consider the extreme case
  88    *    where we multiply by 0x3 or 0xeffffff -- this will not produce good
  89    *    mixing across all bits of the hash).
  90    *
  91    * The rotation length of 5 is also arbitrary, although an odd number is again
  92    * preferable so our hash explores the whole universe of possible rotations.
  93    *
  94    * Finally, we multiply by the golden ratio *after* xor'ing, not before.
  95    * Otherwise, if |aHash| is 0 (as it often is for the beginning of a
  96    * message), the expression
  97    *
  98    *   (kGoldenRatioU32 * RotateBitsLeft(aHash, 5)) |xor| aValue
  99    *
 100    * evaluates to |aValue|.
 101    *
 102    * (Number-theoretic aside: Because any odd number |m| is relatively prime to
 103    * our modulus (2^32), the list
 104    *
 105    *    [x * m (mod 2^32) for 0 <= x < 2^32]
 106    *
 107    * has no duplicate elements.  This means that multiplying by |m| does not
 108    * cause us to skip any possible hash values.
 109    *
 110    * It's also nice if |m| has large-ish order mod 2^32 -- that is, if the
 111    * smallest k such that m^k == 1 (mod 2^32) is large -- so we can safely
 112    * multiply our hash value by |m| a few times without negating the
 113    * multiplicative effect.  Our golden ratio constant has order 2^29, which is
 114    * more than enough for our purposes.)
 115    */
 116   return kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue);
 117 }
 118
 119 /**
 120  * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
 121  */
 122 template<size_t PtrSize>
 123 inline uint32_t
 124 AddUintptrToHash(uint32_t aHash, uintptr_t aValue);
 125
 126 template<>
 127 inline uint32_t
 128 AddUintptrToHash<4>(uint32_t aHash, uintptr_t aValue)
 129 {
 130   return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
 131 }
 132
 133 template<>
 134 inline uint32_t
 135 AddUintptrToHash<8>(uint32_t aHash, uintptr_t aValue)
 136 {
 137   /*
 138    * The static cast to uint64_t below is necessary because this function
 139    * sometimes gets compiled on 32-bit platforms (yes, even though it's a
 140    * template and we never call this particular override in a 32-bit build).  If
 141    * we do aValue >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
 142    * right 32 bits, and the compiler throws an error.
 143    */
 144   uint32_t v1 = static_cast<uint32_t>(aValue);
 145   uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(aValue) >> 32);
 146   return AddU32ToHash(AddU32ToHash(aHash, v1), v2);
 147 }
 148
 149 } /* namespace detail */
 150
 151 /**
 152  * AddToHash takes a hash and some values and returns a new hash based on the
 153  * inputs.
 154  *
 155  * Currently, we support hashing uint32_t's, values which we can implicitly
 156  * convert to uint32_t, data pointers, and function pointers.
 157  */
 158 template<typename A>
 159 MOZ_WARN_UNUSED_RESULT inline uint32_t
 160 AddToHash(uint32_t aHash, A aA)
 161 {
 162   /*
 163    * Try to convert |A| to uint32_t implicitly.  If this works, great.  If not,
 164    * we'll error out.
 165    */
 166   return detail::AddU32ToHash(aHash, aA);
 167 }
 168
 169 template<typename A>
 170 MOZ_WARN_UNUSED_RESULT inline uint32_t
 171 AddToHash(uint32_t aHash, A* aA)
 172 {
 173   /*
 174    * You might think this function should just take a void*.  But then we'd only
 175    * catch data pointers and couldn't handle function pointers.
 176    */
 177
 178   static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
 179
 180   return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
 181 }
 182
 183 template<>
 184 MOZ_WARN_UNUSED_RESULT inline uint32_t
 185 AddToHash(uint32_t aHash, uintptr_t aA)
 186 {
 187   return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, aA);
 188 }
 189
 190 template<typename A, typename B>
 191 MOZ_WARN_UNUSED_RESULT uint32_t
 192 AddToHash(uint32_t aHash, A aA, B aB)
 193 {
 194   return AddToHash(AddToHash(aHash, aA), aB);
 195 }
 196
 197 template<typename A, typename B, typename C>
 198 MOZ_WARN_UNUSED_RESULT uint32_t
 199 AddToHash(uint32_t aHash, A aA, B aB, C aC)
 200 {
 201   return AddToHash(AddToHash(aHash, aA, aB), aC);
 202 }
 203
 204 template<typename A, typename B, typename C, typename D>
 205 MOZ_WARN_UNUSED_RESULT uint32_t
 206 AddToHash(uint32_t aHash, A aA, B aB, C aC, D aD)
 207 {
 208   return AddToHash(AddToHash(aHash, aA, aB, aC), aD);
 209 }
 210
 211 template<typename A, typename B, typename C, typename D, typename E>
 212 MOZ_WARN_UNUSED_RESULT uint32_t
 213 AddToHash(uint32_t aHash, A aA, B aB, C aC, D aD, E aE)
 214 {
 215   return AddToHash(AddToHash(aHash, aA, aB, aC, aD), aE);
 216 }
 217
 218 /**
 219  * The HashGeneric class of functions let you hash one or more values.
 220  *
 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.
 224  */
 225 template<typename A>
 226 MOZ_WARN_UNUSED_RESULT inline uint32_t
 227 HashGeneric(A aA)
 228 {
 229   return AddToHash(0, aA);
 230 }
 231
 232 template<typename A, typename B>
 233 MOZ_WARN_UNUSED_RESULT inline uint32_t
 234 HashGeneric(A aA, B aB)
 235 {
 236   return AddToHash(0, aA, aB);
 237 }
 238
 239 template<typename A, typename B, typename C>
 240 MOZ_WARN_UNUSED_RESULT inline uint32_t
 241 HashGeneric(A aA, B aB, C aC)
 242 {
 243   return AddToHash(0, aA, aB, aC);
 244 }
 245
 246 template<typename A, typename B, typename C, typename D>
 247 MOZ_WARN_UNUSED_RESULT inline uint32_t
 248 HashGeneric(A aA, B aB, C aC, D aD)
 249 {
 250   return AddToHash(0, aA, aB, aC, aD);
 251 }
 252
 253 template<typename A, typename B, typename C, typename D, typename E>
 254 MOZ_WARN_UNUSED_RESULT inline uint32_t
 255 HashGeneric(A aA, B aB, C aC, D aD, E aE)
 256 {
 257   return AddToHash(0, aA, aB, aC, aD, aE);
 258 }
 259
 260 namespace detail {
 261
 262 template<typename T>
 263 uint32_t
 264 HashUntilZero(const T* aStr)
 265 {
 266   uint32_t hash = 0;
 267   for (T c; (c = *aStr); aStr++) {
 268     hash = AddToHash(hash, c);
 269   }
 270   return hash;
 271 }
 272
 273 template<typename T>
 274 uint32_t
 275 HashKnownLength(const T* aStr, size_t aLength)
 276 {
 277   uint32_t hash = 0;
 278   for (size_t i = 0; i < aLength; i++) {
 279     hash = AddToHash(hash, aStr[i]);
 280   }
 281   return hash;
 282 }
 283
 284 } /* namespace detail */
 285
 286 /**
 287  * The HashString overloads below do just what you'd expect.
 288  *
 289  * If you have the string's length, you might as well call the overload which
 290  * includes the length.  It may be marginally faster.
 291  */
 292 MOZ_WARN_UNUSED_RESULT inline uint32_t
 293 HashString(const char* aStr)
 294 {
 295   return detail::HashUntilZero(reinterpret_cast<const unsigned char*>(aStr));
 296 }
 297
 298 MOZ_WARN_UNUSED_RESULT inline uint32_t
 299 HashString(const char* aStr, size_t aLength)
 300 {
 301   return detail::HashKnownLength(reinterpret_cast<const unsigned char*>(aStr), aLength);
 302 }
 303
 304 MOZ_WARN_UNUSED_RESULT
 305 inline uint32_t
 306 HashString(const unsigned char* aStr, size_t aLength)
 307 {
 308   return detail::HashKnownLength(aStr, aLength);
 309 }
 310
 311 MOZ_WARN_UNUSED_RESULT inline uint32_t
 312 HashString(const uint16_t* aStr)
 313 {
 314   return detail::HashUntilZero(aStr);
 315 }
 316
 317 MOZ_WARN_UNUSED_RESULT inline uint32_t
 318 HashString(const uint16_t* aStr, size_t aLength)
 319 {
 320   return detail::HashKnownLength(aStr, aLength);
 321 }
 322
 323 #ifdef MOZ_CHAR16_IS_NOT_WCHAR
 324 MOZ_WARN_UNUSED_RESULT inline uint32_t
 325 HashString(const char16_t* aStr)
 326 {
 327   return detail::HashUntilZero(aStr);
 328 }
 329
 330 MOZ_WARN_UNUSED_RESULT inline uint32_t
 331 HashString(const char16_t* aStr, size_t aLength)
 332 {
 333   return detail::HashKnownLength(aStr, aLength);
 334 }
 335 #endif
 336
 337 /*
 338  * On Windows, wchar_t (char16_t) is not the same as uint16_t, even though it's
 339  * the same width!
 340  */
 341 #ifdef WIN32
 342 MOZ_WARN_UNUSED_RESULT inline uint32_t
 343 HashString(const wchar_t* aStr)
 344 {
 345   return detail::HashUntilZero(aStr);
 346 }
 347
 348 MOZ_WARN_UNUSED_RESULT inline uint32_t
 349 HashString(const wchar_t* aStr, size_t aLength)
 350 {
 351   return detail::HashKnownLength(aStr, aLength);
 352 }
 353 #endif
 354
 355 /**
 356  * Hash some number of bytes.
 357  *
 358  * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
 359  * same result out of HashBytes as you would out of HashString.
 360  */
 361 MOZ_WARN_UNUSED_RESULT extern MFBT_API uint32_t
 362 HashBytes(const void* bytes, size_t aLength);
 363
 364 } /* namespace mozilla */
 365 #endif /* __cplusplus */
 366
 367 #endif /* mozilla_HashFunctions_h */