1 files changed, 188 insertions, 0 deletions
diff --git a/mfbt/WrappingOperations.h b/mfbt/WrappingOperations.h
new file mode 100644
index 0000000000..c93626f653
--- /dev/null
+++ b/mfbt/WrappingOperations.h
@@ -0,0 +1,188 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/*
+ * Math operations that implement wraparound semantics on overflow or underflow
+ * without performing C++ undefined behavior or tripping up compiler-based
+ * integer-overflow sanitizers.
+ */
+
+#ifndef mozilla_WrappingOperations_h
+#define mozilla_WrappingOperations_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/TypeTraits.h"
+
+#include <limits.h>
+
+namespace mozilla {
+
+namespace detail {
+
+template<typename UnsignedType>
+struct WrapToSignedHelper
+{
+  static_assert(mozilla::IsUnsigned<UnsignedType>::value,
+                "WrapToSigned must be passed an unsigned type");
+
+  using SignedType = typename mozilla::MakeSigned<UnsignedType>::Type;
+
+  static constexpr SignedType MaxValue =
+    (UnsignedType(1) << (CHAR_BIT * sizeof(SignedType) - 1)) - 1;
+  static constexpr SignedType MinValue = -MaxValue - 1;
+
+  static constexpr UnsignedType MinValueUnsigned =
+    static_cast<UnsignedType>(MinValue);
+  static constexpr UnsignedType MaxValueUnsigned =
+    static_cast<UnsignedType>(MaxValue);
+
+  // Overflow-correctness was proven in bug 1432646 and is explained in the
+  // comment below.  This function is very hot, both at compile time and
+  // runtime, so disable all overflow checking in it.
+  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW MOZ_NO_SANITIZE_SIGNED_OVERFLOW
+  static constexpr SignedType compute(UnsignedType aValue)
+  {
+    // This algorithm was originally provided here:
+    // https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior
+    //
+    // If the value is in the non-negative signed range, just cast.
+    //
+    // If the value will be negative, compute its delta from the first number
+    // past the max signed integer, then add that to the minimum signed value.
+    //
+    // At the low end: if |u| is the maximum signed value plus one, then it has
+    // the same mathematical value as |MinValue| cast to unsigned form.  The
+    // delta is zero, so the signed form of |u| is |MinValue| -- exactly the
+    // result of adding zero delta to |MinValue|.
+    //
+    // At the high end: if |u| is the maximum *unsigned* value, then it has all
+    // bits set.  |MinValue| cast to unsigned form is purely the high bit set.
+    // So the delta is all bits but high set -- exactly |MaxValue|.  And as
+    // |MinValue = -MaxValue - 1|, we have |MaxValue + (-MaxValue - 1)| to
+    // equal -1.
+    //
+    // Thus the delta below is in signed range, the corresponding cast is safe,
+    // and this computation produces values spanning [MinValue, 0): exactly the
+    // desired range of all negative signed integers.
+    return (aValue <= MaxValueUnsigned)
+           ? static_cast<SignedType>(aValue)
+           : static_cast<SignedType>(aValue - MinValueUnsigned) + MinValue;
+  }
+};
+
+} // namespace detail
+
+/**
+ * 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
+WrapToSigned(UnsignedType aValue)
+{
+  return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
+}
+
+namespace detail {
+
+template<typename T>
+struct WrappingMultiplyHelper
+{
+private:
+  using UnsignedT = typename MakeUnsigned<T>::Type;
+
+  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
+  static UnsignedT
+  multiply(UnsignedT aX, UnsignedT aY)
+  {
+  // |mozilla::WrappingMultiply| isn't constexpr because MSVC warns about well-
+  // defined unsigned integer overflows that may happen here.
+  // https://msdn.microsoft.com/en-us/library/4kze989h.aspx  And constexpr
+  // seems to cause the warning to be emitted at |WrappingMultiply| call *sites*
+  // instead of here, so these #pragmas are ineffective.
+  //
+  // https://stackoverflow.com/questions/37658794/integer-constant-overflow-warning-in-constexpr
+  //
+  // If/when MSVC fix this bug, we should make these functions constexpr.
+
+    // Begin with |1U| to ensure the overall operation chain is never promoted
+    // to signed integer operations that might have *signed* integer overflow.
+    return static_cast<UnsignedT>(1U * aX * aY);
+  }
+
+  static T
+  toResult(UnsignedT aX, UnsignedT aY)
+  {
+    // We could always return WrapToSigned and rely on unsigned conversion
+    // undoing the wrapping when |T| is unsigned, but this seems clearer.
+    return IsSigned<T>::value
+           ? WrapToSigned(multiply(aX, aY))
+           : multiply(aX, aY);
+  }
+
+public:
+  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
+  static T compute(T aX, T aY)
+  {
+    return toResult(static_cast<UnsignedT>(aX), static_cast<UnsignedT>(aY));
+  }
+};
+
+} // namespace detail
+
+/**
+ * Multiply two integers of the same type, and return the result converted to
+ * that type using wraparound semantics.  This function:
+ *
+ *   1) makes explicit the desire for and dependence upon wraparound semantics,
+ *   2) provides wraparound semantics *safely* with no signed integer overflow
+ *      that would have undefined behavior, and
+ *   3) won't trip up {,un}signed-integer overflow sanitizers (see
+ *      build/autoconf/sanitize.m4) at runtime.
+ *
+ * For N-bit unsigned integer types, this is equivalent to multiplying the two
+ * numbers, then taking the result mod 2**N:
+ *
+ *   WrappingMultiply(uint32_t(42), uint32_t(17)) is 714 (714 mod 2**32);
+ *   WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8);
+ *   WrappingMultiply(uint16_t(3), uint16_t(32768)) is 32768 (98304 mod 2*16).
+ *
+ * Use this function for any unsigned multiplication that can wrap (instead of
+ * normal C++ multiplication) to play nice with the sanitizers.  But it's
+ * especially important to use it for uint16_t multiplication: in most compilers
+ * for uint16_t*uint16_t some operand values will trigger signed integer
+ * overflow with undefined behavior!  http://kqueue.org/blog/2013/09/17/cltq/
+ * has the grody details.  Other than that one weird case, WrappingMultiply on
+ * unsigned types is the same as C++ multiplication.
+ *
+ * For N-bit signed integer types, this is equivalent to multiplying the two
+ * numbers wrapped to unsigned, taking the product mod 2**N, then wrapping that
+ * number to the signed range:
+ *
+ *   WrappingMultiply(int16_t(-456), int16_t(123)) is 9448 ((-56088 mod 2**16) + 2**16);
+ *   WrappingMultiply(int32_t(-7), int32_t(-9)) is 63 (63 mod 2**32);
+ *   WrappingMultiply(int8_t(16), int8_t(24)) is -128 ((384 mod 2**8) - 2**8);
+ *   WrappingMultiply(int8_t(16), int8_t(255)) is -16 ((4080 mod 2**8) - 2**8).
+ *
+ * There is no ready equivalent to this operation in C++, as applying C++
+ * multiplication to signed integer types in ways that trigger overflow has
+ * undefined behavior.  However, it's how multiplication *tends* to behave with
+ * most compilers in most situations, even though it's emphatically not required
+ * to do so.
+ */
+template<typename T>
+inline T
+WrappingMultiply(T aX, T aY)
+{
+  return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
+}
+
+} /* namespace mozilla */
+
+#endif /* mozilla_WrappingOperations_h */