Bug 1432646 - Implement mozilla::WrapToSigned. r=froydnj
authorJeff Walden <jwalden@mit.edu>
Thu, 25 Jan 2018 14:48:01 -0800
changeset 401022 e266383ee349457626c646694a374d9d3ef7bc19
parent 401021 816c9ead4b0c87ae9d9d6138a8de35d8c1436928
child 401023 6518882d84718cbc4ce789bf229c618d6bc67f58
push id99283
push userjwalden@mit.edu
push dateSat, 27 Jan 2018 07:54:29 +0000
treeherdermozilla-inbound@c50cbf6e8176 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1432646
milestone60.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 1432646 - Implement mozilla::WrapToSigned. r=froydnj
js/public/Conversions.h
mfbt/MathAlgorithms.h
mfbt/tests/TestMathAlgorithms.cpp
--- a/js/public/Conversions.h
+++ b/js/public/Conversions.h
@@ -6,16 +6,17 @@
 
 /* ECMAScript conversion operations. */
 
 #ifndef js_Conversions_h
 #define js_Conversions_h
 
 #include "mozilla/Casting.h"
 #include "mozilla/FloatingPoint.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/TypeTraits.h"
 
 #include <math.h>
 
 #include "jspubtd.h"
 
 #include "js/RootingAPI.h"
 #include "js/Value.h"
@@ -379,47 +380,20 @@ ToUintWidth(double d)
 
 template<typename ResultType>
 inline ResultType
 ToIntWidth(double d)
 {
     static_assert(mozilla::IsSigned<ResultType>::value,
                   "ResultType must be a signed type");
 
-    constexpr ResultType MaxValue = (1ULL << (CHAR_BIT * sizeof(ResultType) - 1)) - 1;
-    constexpr ResultType MinValue = -MaxValue - 1;
-
     using UnsignedResult = typename mozilla::MakeUnsigned<ResultType>::Type;
     UnsignedResult u = ToUintWidth<UnsignedResult>(d);
 
-    // The algorithm below 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 (u <= UnsignedResult(MaxValue))
-        return static_cast<ResultType>(u);
-
-    // 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 static_cast<ResultType>(u - UnsignedResult(MinValue)) + MinValue;
+    return mozilla::WrapToSigned(u);
 }
 
 } // namespace detail
 
 /* ES5 9.5 ToInt32 (specialized for doubles). */
 inline int32_t
 ToInt32(double d)
 {
--- a/mfbt/MathAlgorithms.h
+++ b/mfbt/MathAlgorithms.h
@@ -537,11 +537,76 @@ Clamp(const T aValue, const T aMin, cons
 
     if (aValue <= aMin)
         return aMin;
     if (aValue >= aMax)
         return aMax;
     return aValue;
 }
 
+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);
+
+  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 mozilla */
 
 #endif /* mozilla_MathAlgorithms_h */
--- a/mfbt/tests/TestMathAlgorithms.cpp
+++ b/mfbt/tests/TestMathAlgorithms.cpp
@@ -1,18 +1,21 @@
 /* -*- 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/. */
 
 #include "mozilla/MathAlgorithms.h"
 
+#include <stdint.h>
+
 using mozilla::Clamp;
 using mozilla::IsPowerOfTwo;
+using mozilla::WrapToSigned;
 
 static void
 TestClamp()
 {
   MOZ_RELEASE_ASSERT(Clamp(0, 0, 0) == 0);
   MOZ_RELEASE_ASSERT(Clamp(1, 0, 0) == 0);
   MOZ_RELEASE_ASSERT(Clamp(-1, 0, 0) == 0);
 
@@ -72,16 +75,55 @@ TestIsPowerOfTwo()
 
   static_assert(!IsPowerOfTwo(uint64_t(UINT64_MAX/2)), "0x7fffffffffffffff isn't a power of two");
   static_assert(IsPowerOfTwo(uint64_t(UINT64_MAX/2 + 1)), "0x8000000000000000 is a power of two");
   static_assert(!IsPowerOfTwo(uint64_t(UINT64_MAX/2 + 2)), "0x8000000000000001 isn't a power of two");
   static_assert(!IsPowerOfTwo(uint64_t(UINT64_MAX - 1)), "0xfffffffffffffffe isn't a power of two");
   static_assert(!IsPowerOfTwo(uint64_t(UINT64_MAX)), "0xffffffffffffffff isn't a power of two");
 }
 
+static_assert(WrapToSigned(uint8_t(17)) == 17,
+              "no wraparound should work, 8-bit");
+static_assert(WrapToSigned(uint8_t(128)) == -128,
+              "works for 8-bit numbers, wraparound low end");
+static_assert(WrapToSigned(uint8_t(128 + 7)) == -128 + 7,
+              "works for 8-bit numbers, wraparound mid");
+static_assert(WrapToSigned(uint8_t(128 + 127)) == -128 + 127,
+              "works for 8-bit numbers, wraparound high end");
+
+static_assert(WrapToSigned(uint16_t(12345)) == 12345,
+              "no wraparound should work, 16-bit");
+static_assert(WrapToSigned(uint16_t(32768)) == -32768,
+              "works for 16-bit numbers, wraparound low end");
+static_assert(WrapToSigned(uint16_t(32768 + 42)) == -32768 + 42,
+              "works for 16-bit numbers, wraparound mid");
+static_assert(WrapToSigned(uint16_t(32768 + 32767)) == -32768 + 32767,
+              "works for 16-bit numbers, wraparound high end");
+
+static_assert(WrapToSigned(uint32_t(8675309)) == 8675309,
+              "no wraparound should work, 32-bit");
+static_assert(WrapToSigned(uint32_t(2147483648)) == -2147483648,
+              "works for 32-bit numbers, wraparound low end");
+static_assert(WrapToSigned(uint32_t(2147483648 + 42)) == -2147483648 + 42,
+              "works for 32-bit numbers, wraparound mid");
+static_assert(WrapToSigned(uint32_t(2147483648 + 2147483647)) ==
+                -2147483648 + 2147483647,
+              "works for 32-bit numbers, wraparound high end");
+
+static_assert(WrapToSigned(uint64_t(4152739164)) == 4152739164,
+              "no wraparound should work, 64-bit");
+static_assert(WrapToSigned(uint64_t(9223372036854775808ULL)) == -9223372036854775807LL - 1,
+              "works for 64-bit numbers, wraparound low end");
+static_assert(WrapToSigned(uint64_t(9223372036854775808ULL + 8005552368LL)) ==
+                -9223372036854775807LL - 1 + 8005552368LL,
+              "works for 64-bit numbers, wraparound mid");
+static_assert(WrapToSigned(uint64_t(9223372036854775808ULL + 9223372036854775807ULL)) ==
+                -9223372036854775807LL - 1 + 9223372036854775807LL,
+              "works for 64-bit numbers, wraparound high end");
+
 int
 main()
 {
   TestIsPowerOfTwo();
   TestClamp();
 
   return 0;
 }