michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* Utilities for hashing. */
michael@0: 
michael@0: /*
michael@0:  * This file exports functions for hashing data down to a 32-bit value,
michael@0:  * including:
michael@0:  *
michael@0:  *  - HashString    Hash a char* or uint16_t/wchar_t* of known or unknown
michael@0:  *                  length.
michael@0:  *
michael@0:  *  - HashBytes     Hash a byte array of known length.
michael@0:  *
michael@0:  *  - HashGeneric   Hash one or more values.  Currently, we support uint32_t,
michael@0:  *                  types which can be implicitly cast to uint32_t, data
michael@0:  *                  pointers, and function pointers.
michael@0:  *
michael@0:  *  - AddToHash     Add one or more values to the given hash.  This supports the
michael@0:  *                  same list of types as HashGeneric.
michael@0:  *
michael@0:  *
michael@0:  * You can chain these functions together to hash complex objects.  For example:
michael@0:  *
michael@0:  *  class ComplexObject
michael@0:  *  {
michael@0:  *      char* str;
michael@0:  *      uint32_t uint1, uint2;
michael@0:  *      void (*callbackFn)();
michael@0:  *
michael@0:  *    public:
michael@0:  *      uint32_t hash() {
michael@0:  *        uint32_t hash = HashString(str);
michael@0:  *        hash = AddToHash(hash, uint1, uint2);
michael@0:  *        return AddToHash(hash, callbackFn);
michael@0:  *      }
michael@0:  *  };
michael@0:  *
michael@0:  * If you want to hash an nsAString or nsACString, use the HashString functions
michael@0:  * in nsHashKeys.h.
michael@0:  */
michael@0: 
michael@0: #ifndef mozilla_HashFunctions_h
michael@0: #define mozilla_HashFunctions_h
michael@0: 
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "mozilla/Char16.h"
michael@0: #include "mozilla/Types.h"
michael@0: 
michael@0: #include <stdint.h>
michael@0: 
michael@0: #ifdef __cplusplus
michael@0: namespace mozilla {
michael@0: 
michael@0: /**
michael@0:  * The golden ratio as a 32-bit fixed-point value.
michael@0:  */
michael@0: static const uint32_t GoldenRatioU32 = 0x9E3779B9U;
michael@0: 
michael@0: inline uint32_t
michael@0: RotateBitsLeft32(uint32_t value, uint8_t bits)
michael@0: {
michael@0:   MOZ_ASSERT(bits < 32);
michael@0:   return (value << bits) | (value >> (32 - bits));
michael@0: }
michael@0: 
michael@0: namespace detail {
michael@0: 
michael@0: inline uint32_t
michael@0: AddU32ToHash(uint32_t hash, uint32_t value)
michael@0: {
michael@0:   /*
michael@0:    * This is the meat of all our hash routines.  This hash function is not
michael@0:    * particularly sophisticated, but it seems to work well for our mostly
michael@0:    * plain-text inputs.  Implementation notes follow.
michael@0:    *
michael@0:    * Our use of the golden ratio here is arbitrary; we could pick almost any
michael@0:    * number which:
michael@0:    *
michael@0:    *  * is odd (because otherwise, all our hash values will be even)
michael@0:    *
michael@0:    *  * has a reasonably-even mix of 1's and 0's (consider the extreme case
michael@0:    *    where we multiply by 0x3 or 0xeffffff -- this will not produce good
michael@0:    *    mixing across all bits of the hash).
michael@0:    *
michael@0:    * The rotation length of 5 is also arbitrary, although an odd number is again
michael@0:    * preferable so our hash explores the whole universe of possible rotations.
michael@0:    *
michael@0:    * Finally, we multiply by the golden ratio *after* xor'ing, not before.
michael@0:    * Otherwise, if |hash| is 0 (as it often is for the beginning of a message),
michael@0:    * the expression
michael@0:    *
michael@0:    *   (GoldenRatioU32 * RotateBitsLeft(hash, 5)) |xor| value
michael@0:    *
michael@0:    * evaluates to |value|.
michael@0:    *
michael@0:    * (Number-theoretic aside: Because any odd number |m| is relatively prime to
michael@0:    * our modulus (2^32), the list
michael@0:    *
michael@0:    *    [x * m (mod 2^32) for 0 <= x < 2^32]
michael@0:    *
michael@0:    * has no duplicate elements.  This means that multiplying by |m| does not
michael@0:    * cause us to skip any possible hash values.
michael@0:    *
michael@0:    * It's also nice if |m| has large-ish order mod 2^32 -- that is, if the
michael@0:    * smallest k such that m^k == 1 (mod 2^32) is large -- so we can safely
michael@0:    * multiply our hash value by |m| a few times without negating the
michael@0:    * multiplicative effect.  Our golden ratio constant has order 2^29, which is
michael@0:    * more than enough for our purposes.)
michael@0:    */
michael@0:   return GoldenRatioU32 * (RotateBitsLeft32(hash, 5) ^ value);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
michael@0:  */
michael@0: template<size_t PtrSize>
michael@0: inline uint32_t
michael@0: AddUintptrToHash(uint32_t hash, uintptr_t value);
michael@0: 
michael@0: template<>
michael@0: inline uint32_t
michael@0: AddUintptrToHash<4>(uint32_t hash, uintptr_t value)
michael@0: {
michael@0:   return AddU32ToHash(hash, static_cast<uint32_t>(value));
michael@0: }
michael@0: 
michael@0: template<>
michael@0: inline uint32_t
michael@0: AddUintptrToHash<8>(uint32_t hash, uintptr_t value)
michael@0: {
michael@0:   /*
michael@0:    * The static cast to uint64_t below is necessary because this function
michael@0:    * sometimes gets compiled on 32-bit platforms (yes, even though it's a
michael@0:    * template and we never call this particular override in a 32-bit build).  If
michael@0:    * we do value >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
michael@0:    * right 32 bits, and the compiler throws an error.
michael@0:    */
michael@0:   uint32_t v1 = static_cast<uint32_t>(value);
michael@0:   uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(value) >> 32);
michael@0:   return AddU32ToHash(AddU32ToHash(hash, v1), v2);
michael@0: }
michael@0: 
michael@0: } /* namespace detail */
michael@0: 
michael@0: /**
michael@0:  * AddToHash takes a hash and some values and returns a new hash based on the
michael@0:  * inputs.
michael@0:  *
michael@0:  * Currently, we support hashing uint32_t's, values which we can implicitly
michael@0:  * convert to uint32_t, data pointers, and function pointers.
michael@0:  */
michael@0: template<typename A>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: AddToHash(uint32_t hash, A a)
michael@0: {
michael@0:   /*
michael@0:    * Try to convert |A| to uint32_t implicitly.  If this works, great.  If not,
michael@0:    * we'll error out.
michael@0:    */
michael@0:   return detail::AddU32ToHash(hash, a);
michael@0: }
michael@0: 
michael@0: template<typename A>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: AddToHash(uint32_t hash, A* a)
michael@0: {
michael@0:   /*
michael@0:    * You might think this function should just take a void*.  But then we'd only
michael@0:    * catch data pointers and couldn't handle function pointers.
michael@0:    */
michael@0: 
michael@0:   static_assert(sizeof(a) == sizeof(uintptr_t),
michael@0:                 "Strange pointer!");
michael@0: 
michael@0:   return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, uintptr_t(a));
michael@0: }
michael@0: 
michael@0: template<>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: AddToHash(uint32_t hash, uintptr_t a)
michael@0: {
michael@0:   return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, a);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: uint32_t
michael@0: AddToHash(uint32_t hash, A a, B b)
michael@0: {
michael@0:   return AddToHash(AddToHash(hash, a), b);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: uint32_t
michael@0: AddToHash(uint32_t hash, A a, B b, C c)
michael@0: {
michael@0:   return AddToHash(AddToHash(hash, a, b), c);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C, typename D>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: uint32_t
michael@0: AddToHash(uint32_t hash, A a, B b, C c, D d)
michael@0: {
michael@0:   return AddToHash(AddToHash(hash, a, b, c), d);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C, typename D, typename E>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: uint32_t
michael@0: AddToHash(uint32_t hash, A a, B b, C c, D d, E e)
michael@0: {
michael@0:   return AddToHash(AddToHash(hash, a, b, c, d), e);
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * The HashGeneric class of functions let you hash one or more values.
michael@0:  *
michael@0:  * If you want to hash together two values x and y, calling HashGeneric(x, y) is
michael@0:  * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
michael@0:  * that x has already been hashed.
michael@0:  */
michael@0: template<typename A>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashGeneric(A a)
michael@0: {
michael@0:   return AddToHash(0, a);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashGeneric(A a, B b)
michael@0: {
michael@0:   return AddToHash(0, a, b);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashGeneric(A a, B b, C c)
michael@0: {
michael@0:   return AddToHash(0, a, b, c);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C, typename D>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashGeneric(A a, B b, C c, D d)
michael@0: {
michael@0:   return AddToHash(0, a, b, c, d);
michael@0: }
michael@0: 
michael@0: template<typename A, typename B, typename C, typename D, typename E>
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashGeneric(A a, B b, C c, D d, E e)
michael@0: {
michael@0:   return AddToHash(0, a, b, c, d, e);
michael@0: }
michael@0: 
michael@0: namespace detail {
michael@0: 
michael@0: template<typename T>
michael@0: uint32_t
michael@0: HashUntilZero(const T* str)
michael@0: {
michael@0:   uint32_t hash = 0;
michael@0:   for (T c; (c = *str); str++)
michael@0:     hash = AddToHash(hash, c);
michael@0:   return hash;
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: uint32_t
michael@0: HashKnownLength(const T* str, size_t length)
michael@0: {
michael@0:   uint32_t hash = 0;
michael@0:   for (size_t i = 0; i < length; i++)
michael@0:     hash = AddToHash(hash, str[i]);
michael@0:   return hash;
michael@0: }
michael@0: 
michael@0: } /* namespace detail */
michael@0: 
michael@0: /**
michael@0:  * The HashString overloads below do just what you'd expect.
michael@0:  *
michael@0:  * If you have the string's length, you might as well call the overload which
michael@0:  * includes the length.  It may be marginally faster.
michael@0:  */
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const char* str)
michael@0: {
michael@0:   return detail::HashUntilZero(str);
michael@0: }
michael@0: 
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const char* str, size_t length)
michael@0: {
michael@0:   return detail::HashKnownLength(str, length);
michael@0: }
michael@0: 
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const uint16_t* str)
michael@0: {
michael@0:   return detail::HashUntilZero(str);
michael@0: }
michael@0: 
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const uint16_t* str, size_t length)
michael@0: {
michael@0:   return detail::HashKnownLength(str, length);
michael@0: }
michael@0: 
michael@0: #ifdef MOZ_CHAR16_IS_NOT_WCHAR
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const char16_t* str)
michael@0: {
michael@0:   return detail::HashUntilZero(str);
michael@0: }
michael@0: 
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const char16_t* str, size_t length)
michael@0: {
michael@0:   return detail::HashKnownLength(str, length);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  * On Windows, wchar_t (char16_t) is not the same as uint16_t, even though it's
michael@0:  * the same width!
michael@0:  */
michael@0: #ifdef WIN32
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const wchar_t* str)
michael@0: {
michael@0:   return detail::HashUntilZero(str);
michael@0: }
michael@0: 
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: inline uint32_t
michael@0: HashString(const wchar_t* str, size_t length)
michael@0: {
michael@0:   return detail::HashKnownLength(str, length);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: /**
michael@0:  * Hash some number of bytes.
michael@0:  *
michael@0:  * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
michael@0:  * same result out of HashBytes as you would out of HashString.
michael@0:  */
michael@0: MOZ_WARN_UNUSED_RESULT
michael@0: extern MFBT_API uint32_t
michael@0: HashBytes(const void* bytes, size_t length);
michael@0: 
michael@0: } /* namespace mozilla */
michael@0: #endif /* __cplusplus */
michael@0: 
michael@0: #endif /* mozilla_HashFunctions_h */