Performance optimizations for base/numerics absolute value and multiply

base/numerics/safe_math_impl.h

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_NUMERICS_SAFE_MATH_IMPL_H_
 #define BASE_NUMERICS_SAFE_MATH_IMPL_H_
 
 #include <stddef.h>
 #include <stdint.h>
 
@@ skipping 24 matching lines @@
 template <typename Numeric>
 struct UnsignedOrFloatForSize<Numeric, true, false> {
   using type = typename std::make_unsigned<Numeric>::type;
 };
 
 template <typename Numeric>
 struct UnsignedOrFloatForSize<Numeric, false, true> {
   using type = Numeric;
 };
 
-// Helper templates for integer manipulations.
-
-template <typename T>
-constexpr bool HasSignBit(T x) {
-  // Cast to unsigned since right shift on signed is undefined.
-  return !!(static_cast<typename std::make_unsigned<T>::type>(x) >>
-            PositionOfSignBit<T>::value);
-}
-
-// This wrapper undoes the standard integer promotions.
-template <typename T>
-constexpr T BinaryComplement(T x) {
-  return static_cast<T>(~x);
-}
-
 // Probe for builtin math overflow support on Clang and version check on GCC.
 #if defined(__has_builtin)
 #define USE_OVERFLOW_BUILTINS (__has_builtin(__builtin_add_overflow))
 #elif defined(__GNUC__)
 #define USE_OVERFLOW_BUILTINS (__GNUC__ >= 5)
 #else
 #define USE_OVERFLOW_BUILTINS (0)
 #endif
 
 template <typename T,
@@ skipping 115 matching lines @@
   *result = static_cast<T>(tmp);
   return DstRangeRelationToSrcRange<T>(tmp) == RANGE_VALID;
 }
 
 template <typename T,
           typename std::enable_if<
               std::is_integral<T>::value && std::is_signed<T>::value &&
               ((IntegerBitsPlusSign<T>::value * 2) >
                IntegerBitsPlusSign<intmax_t>::value)>::type* = nullptr>
 bool CheckedMulImpl(T x, T y, T* result) {
-  if (x && y) {
-    if (x > 0) {
-      if (y > 0) {
-        if (x > std::numeric_limits<T>::max() / y)
-          return false;
-      } else {
-        if (y < std::numeric_limits<T>::lowest() / x)
-          return false;
-      }
-    } else {
-      if (y > 0) {
-        if (x < std::numeric_limits<T>::lowest() / y)
-          return false;
-      } else {
-        if (y < std::numeric_limits<T>::max() / x)
-          return false;
-      }
-    }
-  }
-  *result = x * y;
-  return true;
+  // Since the value of x*y is potentially undefined if we have a signed type,
+  // we compute it using the unsigned type of the same size.
+  using UnsignedDst = typename std::make_unsigned<T>::type;
+  const T is_negative = HasSignBit(x) ^ HasSignBit(y);
+  const UnsignedDst ux = SafeUnsignedAbs(x);
+  const UnsignedDst uy = SafeUnsignedAbs(y);
+  UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy);
+  // This is a non-branching conditional negation.
+  *result = static_cast<T>((uresult ^ -is_negative) + is_negative);

[scottmg, 2016/12/10 01:01:31]

I would have moved that before this line instead, if anywhere, since that's
where it's used.

+  // This uses the unsigned overflow check on the absolute value, with a +1
+  // bound for a negative result.
+  return (uy == 0 ||
+          ux <= (static_cast<UnsignedDst>(std::numeric_limits<T>::max()) +
+                 is_negative) /
+                    uy);
 }
 
 template <typename T,
           typename std::enable_if<
               std::is_integral<T>::value && !std::is_signed<T>::value &&
               ((IntegerBitsPlusSign<T>::value * 2) >
                IntegerBitsPlusSign<uintmax_t>::value)>::type* = nullptr>
 bool CheckedMulImpl(T x, T y, T* result) {
   *result = x * y;
   return (y == 0 || x <= std::numeric_limits<T>::max() / y);
@@ skipping 296 matching lines @@
                                   !std::is_signed<T>::value>::type* = nullptr>
 bool CheckedInv(T value, T* result) {
   *result = ~value;
   return true;
 }
 
 template <typename T,
           typename std::enable_if<std::is_integral<T>::value &&
                                   std::is_signed<T>::value>::type* = nullptr>
 bool CheckedAbs(T value, T* result) {
-  if (value != std::numeric_limits<T>::lowest()) {
-    *result = std::abs(value);
-    return true;
-  }
-  return false;
+  *result = static_cast<T>(SafeUnsignedAbs(value));
+  return *result != std::numeric_limits<T>::lowest();
 }
 
 template <typename T,
           typename std::enable_if<std::is_integral<T>::value &&
                                   !std::is_signed<T>::value>::type* = nullptr>
 bool CheckedAbs(T value, T* result) {
   // T is unsigned, so |value| must already be positive.
   *result = value;
   return true;
 }
 
-template <typename T,
-          typename std::enable_if<std::is_integral<T>::value &&
-                                  std::is_signed<T>::value>::type* = nullptr>
-constexpr typename std::make_unsigned<T>::type SafeUnsignedAbs(T value) {
-  using UnsignedT = typename std::make_unsigned<T>::type;
-  return value == std::numeric_limits<T>::lowest()
-             ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1
-             : static_cast<UnsignedT>(std::abs(value));
-}
-
-template <typename T,
-          typename std::enable_if<std::is_integral<T>::value &&
-                                  !std::is_signed<T>::value>::type* = nullptr>
-constexpr T SafeUnsignedAbs(T value) {
-  // T is unsigned, so |value| must already be positive.
-  return static_cast<T>(value);
-}
-
 // This is just boilerplate that wraps the standard floating point arithmetic.
 // A macro isn't the nicest solution, but it beats rewriting these repeatedly.
 #define BASE_FLOAT_ARITHMETIC_OPS(NAME, OP)                                    \
   template <typename T, typename U>                                            \
   struct Checked##NAME##Op<                                                    \
       T, U, typename std::enable_if<std::is_floating_point<T>::value ||        \
                                     std::is_floating_point<U>::value>::type> { \
     using result_type = typename MaxExponentPromotion<T, U>::type;             \
     template <typename V>                                                      \
     static bool Do(T x, U y, V* result) {                                      \
@@ skipping 154 matching lines @@
   using math = M<typename UnderlyingType<L>::type,
                  typename UnderlyingType<R>::type,
                  void>;
   using type = typename math::result_type;
 };
 
 }  // namespace internal
 }  // namespace base
 
 #endif  // BASE_NUMERICS_SAFE_MATH_IMPL_H_