Bug 1443706 - Introduce ConstExprHashString(const char16_t*). r=jwalden
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 08 Mar 2018 10:27:14 +1100
changeset 461993 545fb6e48c79d2704b5e5506a667b72d97a3d949
parent 461992 83dffebb15369683ef0426c43d68c593f5d2b618
child 461994 dbae3228e48227093d181e84e79331433f3d5562
push id9165
push userasasaki@mozilla.com
push dateThu, 26 Apr 2018 21:04:54 +0000
treeherdermozilla-beta@064c3804de2e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjwalden
bugs1443706, 1443342, 1411469
milestone61.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1443706 - Introduce ConstExprHashString(const char16_t*). r=jwalden This is a `constexpr` alternative to HashString(const char16_t*). We can't make HashString(const char16_t*) itself `constexpr` because HashUntilZero(const T*) isn't in a form that older compilers (like GCC 4.9) allow to be made `constexpr`. (The trick to satisfying those compilers is to use recursion instead of iteration, to get the function into a single `return` statement.) This requires making a bunch of other functions `constexpr` as well. It also requires adding MOZ_{PUSH,POP}_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING macros to avoid some MSVC weirdness. The introduction of RotateLeft5() partly undoes one of the patches from bug 1443342, but that's unavoidable. This change will help with static allocation of static atoms (bug 1411469). MozReview-Commit-ID: 7r3PnrQXb29
mfbt/HashFunctions.h
mfbt/WrappingOperations.h
--- a/mfbt/HashFunctions.h
+++ b/mfbt/HashFunctions.h
@@ -60,17 +60,24 @@ namespace mozilla {
 
 /**
  * The golden ratio as a 32-bit fixed-point value.
  */
 static const uint32_t kGoldenRatioU32 = 0x9E3779B9U;
 
 namespace detail {
 
-inline uint32_t
+MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
+constexpr uint32_t
+RotateLeft5(uint32_t aValue)
+{
+  return (aValue << 5) | (aValue >> 27);
+}
+
+constexpr uint32_t
 AddU32ToHash(uint32_t aHash, uint32_t aValue)
 {
   /*
    * This is the meat of all our hash routines.  This hash function is not
    * particularly sophisticated, but it seems to work well for our mostly
    * plain-text inputs.  Implementation notes follow.
    *
    * Our use of the golden ratio here is arbitrary; we could pick almost any
@@ -84,17 +91,17 @@ AddU32ToHash(uint32_t aHash, uint32_t aV
    *
    * The rotation length of 5 is also arbitrary, although an odd number is again
    * preferable so our hash explores the whole universe of possible rotations.
    *
    * Finally, we multiply by the golden ratio *after* xor'ing, not before.
    * Otherwise, if |aHash| is 0 (as it often is for the beginning of a
    * message), the expression
    *
-   *   mozilla::WrappingMultiply(kGoldenRatioU32, RotateBitsLeft(aHash, 5))
+   *   mozilla::WrappingMultiply(kGoldenRatioU32, RotateLeft5(aHash))
    *   |xor|
    *   aValue
    *
    * evaluates to |aValue|.
    *
    * (Number-theoretic aside: Because any odd number |m| is relatively prime to
    * our modulus (2**32), the list
    *
@@ -105,24 +112,24 @@ AddU32ToHash(uint32_t aHash, uint32_t aV
    *
    * It's also nice if |m| has large-ish order mod 2**32 -- that is, if the
    * smallest k such that m**k == 1 (mod 2**32) is large -- so we can safely
    * multiply our hash value by |m| a few times without negating the
    * multiplicative effect.  Our golden ratio constant has order 2**29, which is
    * more than enough for our purposes.)
    */
   return mozilla::WrappingMultiply(kGoldenRatioU32,
-                                   RotateLeft(aHash, 5) ^ aValue);
+                                   RotateLeft5(aHash) ^ aValue);
 }
 
 /**
  * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
  */
 template<size_t PtrSize>
-inline uint32_t
+constexpr uint32_t
 AddUintptrToHash(uint32_t aHash, uintptr_t aValue)
 {
   return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
 }
 
 template<>
 inline uint32_t
 AddUintptrToHash<8>(uint32_t aHash, uintptr_t aValue)
@@ -168,17 +175,17 @@ AddToHash(uint32_t aHash, A* aA)
   return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
 }
 
 // We use AddUintptrToHash() for hashing all integral types.  8-byte integral types
 // are treated the same as 64-bit pointers, and smaller integral types are first
 // implicitly converted to 32 bits and then passed to AddUintptrToHash() to be hashed.
 template<typename T,
          typename U = typename mozilla::EnableIf<mozilla::IsIntegral<T>::value>::Type>
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE constexpr uint32_t
 AddToHash(uint32_t aHash, T aA)
 {
   return detail::AddUintptrToHash<sizeof(T)>(aHash, aA);
 }
 
 template<typename A, typename... Args>
 MOZ_MUST_USE uint32_t
 AddToHash(uint32_t aHash, A aArg, Args... aArgs)
@@ -208,16 +215,29 @@ HashUntilZero(const T* aStr)
 {
   uint32_t hash = 0;
   for (T c; (c = *aStr); aStr++) {
     hash = AddToHash(hash, c);
   }
   return hash;
 }
 
+// This is a `constexpr` alternative to HashUntilZero(const T*). It should
+// only be used for compile-time computation because it uses recursion.
+// XXX: once support for GCC 4.9 is dropped, this function should be removed
+// and HashUntilZero(const T*) should be made `constexpr`.
+template<typename T>
+constexpr uint32_t
+ConstExprHashUntilZero(const T* aStr, uint32_t aHash)
+{
+  return !*aStr
+       ? aHash
+       : ConstExprHashUntilZero(aStr + 1, AddToHash(aHash, *aStr));
+}
+
 template<typename T>
 uint32_t
 HashKnownLength(const T* aStr, size_t aLength)
 {
   uint32_t hash = 0;
   for (size_t i = 0; i < aLength; i++) {
     hash = AddToHash(hash, aStr[i]);
   }
@@ -252,16 +272,31 @@ HashString(const unsigned char* aStr, si
 }
 
 MOZ_MUST_USE inline uint32_t
 HashString(const char16_t* aStr)
 {
   return detail::HashUntilZero(aStr);
 }
 
+// This is a `constexpr` alternative to HashString(const char16_t*). It should
+// only be used for compile-time computation because it uses recursion.
+//
+// You may need to use the
+// MOZ_{PUSH,POP}_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING macros if you use
+// this function. See the comment on those macros' definitions for more detail.
+//
+// XXX: once support for GCC 4.9 is dropped, this function should be removed
+// and HashString(const char16_t*) should be made `constexpr`.
+MOZ_MUST_USE constexpr uint32_t
+ConstExprHashString(const char16_t* aStr)
+{
+  return detail::ConstExprHashUntilZero(aStr, 0);
+}
+
 MOZ_MUST_USE inline uint32_t
 HashString(const char16_t* aStr, size_t aLength)
 {
   return detail::HashKnownLength(aStr, aLength);
 }
 
 /*
  * On Windows, wchar_t is not the same as char16_t, even though it's
--- a/mfbt/WrappingOperations.h
+++ b/mfbt/WrappingOperations.h
@@ -89,55 +89,42 @@ struct WrapToSignedHelper
 /**
  * Convert an unsigned value to signed, if necessary wrapping around.
  *
  * This is the behavior normal C++ casting will perform in most implementations
  * these days -- but this function makes explicit that such conversion is
  * happening.
  */
 template<typename UnsignedType>
-inline constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
+constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
 WrapToSigned(UnsignedType aValue)
 {
   return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
 }
 
-// The |mozilla::Wrapping*| functions aren't constexpr because MSVC warns about
-// well-defined unsigned integer overflows that may occur within the constexpr
-// math.  If/when MSVC fix this bug, we should make them all constexpr.
-//
-//   https://msdn.microsoft.com/en-us/library/4kze989h.aspx (C4307)
-//   https://developercommunity.visualstudio.com/content/problem/211134/unsigned-integer-overflows-in-constexpr-functionsa.html (bug report)
-//
-// For now there's no practical, readable way to avoid such overflows in pure
-// C++.  And we can't add narrow #pragmas where overflow can occur to disable
-// the warnings, because constexpr apparently causes the warning to be emitted
-// at the outermost call *sites* (so every user of |mozilla::Wrapping*| would
-// have to add them).
-
 namespace detail {
 
 template<typename T>
-inline constexpr T
+constexpr T
 ToResult(typename MakeUnsigned<T>::Type aUnsigned)
 {
   // We could *always* return WrapToSigned and rely on unsigned conversion to
   // undo the wrapping when |T| is unsigned, but this seems clearer.
   return IsSigned<T>::value ? WrapToSigned(aUnsigned) : aUnsigned;
 }
 
 template<typename T>
 struct WrappingAddHelper
 {
 private:
   using UnsignedT = typename MakeUnsigned<T>::Type;
 
 public:
   MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
-  static T compute(T aX, T aY)
+  static constexpr T compute(T aX, T aY)
   {
     return ToResult<T>(static_cast<UnsignedT>(aX) + static_cast<UnsignedT>(aY));
   }
 };
 
 } // namespace detail
 
 /**
@@ -160,33 +147,33 @@ public:
  *   WrappingAdd(int32_t(-42), int32_t(-17)) is -59 ((8589934533 mod 2**32) - 2**32).
  *
  * There's no equivalent to this operation in C++, as C++ signed addition that
  * overflows has undefined behavior.  But it's how such addition *tends* to
  * behave with most compilers, unless an optimization or similar -- quite
  * permissibly -- triggers different behavior.
  */
 template<typename T>
-inline T
+constexpr T
 WrappingAdd(T aX, T aY)
 {
   return detail::WrappingAddHelper<T>::compute(aX, aY);
 }
 
 namespace detail {
 
 template<typename T>
 struct WrappingSubtractHelper
 {
 private:
   using UnsignedT = typename MakeUnsigned<T>::Type;
 
 public:
   MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
-  static T compute(T aX, T aY)
+  static constexpr T compute(T aX, T aY)
   {
     return ToResult<T>(static_cast<UnsignedT>(aX) - static_cast<UnsignedT>(aY));
   }
 };
 
 } // namespace detail
 
 /**
@@ -210,33 +197,33 @@ public:
  *   WrappingSubtract(int32_t(-17), int32_t(-42)) is 25 (25 mod 2**32).
  *
  * There's no equivalent to this operation in C++, as C++ signed subtraction
  * that overflows has undefined behavior.  But it's how such subtraction *tends*
  * to behave with most compilers, unless an optimization or similar -- quite
  * permissibly -- triggers different behavior.
  */
 template<typename T>
-inline T
+constexpr T
 WrappingSubtract(T aX, T aY)
 {
   return detail::WrappingSubtractHelper<T>::compute(aX, aY);
 }
 
 namespace detail {
 
 template<typename T>
 struct WrappingMultiplyHelper
 {
 private:
   using UnsignedT = typename MakeUnsigned<T>::Type;
 
 public:
   MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
-  static T compute(T aX, T aY)
+  static constexpr T compute(T aX, T aY)
   {
     // Begin with |1U| to ensure the overall operation chain is never promoted
     // to signed integer operations that might have *signed* integer overflow.
     return ToResult<T>(static_cast<UnsignedT>(1U *
                                               static_cast<UnsignedT>(aX) *
                                               static_cast<UnsignedT>(aY)));
   }
 };
@@ -272,17 +259,41 @@ public:
  *   WrappingMultiply(int8_t(16), int8_t(255)) is -16 ((4080 mod 2**8) - 2**8).
  *
  * There's no equivalent to this operation in C++, as C++ signed
  * multiplication that overflows has undefined behavior.  But it's how such
  * multiplication *tends* to behave with most compilers, unless an optimization
  * or similar -- quite permissibly -- triggers different behavior.
  */
 template<typename T>
-inline T
+constexpr T
 WrappingMultiply(T aX, T aY)
 {
   return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
 }
 
+// The |mozilla::Wrapping*| functions are constexpr. Unfortunately, MSVC warns
+// about well-defined unsigned integer overflows that may occur within the
+// constexpr math.
+//
+//   https://msdn.microsoft.com/en-us/library/4kze989h.aspx (C4307)
+//   https://developercommunity.visualstudio.com/content/problem/211134/unsigned-integer-overflows-in-constexpr-functionsa.html (bug report)
+//
+// So we need a way to suppress these warnings. Unfortunately, the warnings are
+// issued at the very top of the `constexpr` chain, which is often some
+// distance from the triggering Wrapping*() operation. So we can't suppress
+// them within this file. Instead, callers have to do it with these macros.
+//
+// If/when MSVC fix this bug, we should remove these macros.
+#ifdef _MSC_VER
+#define MOZ_PUSH_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING \
+  __pragma(warning(push)) \
+  __pragma(warning(disable:4307))
+#define MOZ_POP_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING \
+  __pragma(warning(pop))
+#else
+#define MOZ_PUSH_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING
+#define MOZ_POP_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING
+#endif
+
 } /* namespace mozilla */
 
 #endif /* mozilla_WrappingOperations_h */