mfbt/HashFunctions.h

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