Performance optimizations for Checked(Add|Sub|Mul|Div)

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 208 matching lines @@
   static const bool is_contained = true;
 };
 
 // Attempt to find a big enough type.
 template <typename Lhs, typename Rhs>
 struct ArithmeticPromotion<BIG_ENOUGH_PROMOTION, Lhs, Rhs> {
   using type = typename BigEnoughPromotion<Lhs, Rhs>::type;
   static const bool is_contained = BigEnoughPromotion<Lhs, Rhs>::is_contained;
 };
 
+// We can statically check if operations on the provided types can wrap, so we
+// can skip the checked operations if they're not needed. So, for an integer we
+// care if the destination type preserves the sign and is twice the width of
+// the source.
+template <typename T, typename Lhs, typename Rhs>
+struct IsIntegerArithmeticSafe {
+  static const bool value = !std::numeric_limits<T>::is_iec559 &&
+                            StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
+                                NUMERIC_RANGE_CONTAINED &&
+                            sizeof(T) >= (2 * sizeof(Lhs)) &&
+                            StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
+                                NUMERIC_RANGE_CONTAINED &&
+                            sizeof(T) >= (2 * sizeof(Rhs));
+};
+
 // Here are the actual portable checked integer math implementations.
 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
 // way to coalesce things into the CheckedNumericState specializations below.
 
 template <typename T>
 typename std::enable_if<std::numeric_limits<T>::is_integer, bool>::type
 CheckedAddImpl(T x, T y, T* result) {
   // Since the value of x+y is undefined if we have a signed type, we compute
   // it using the unsigned type of the same size.
   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
@@ skipping 11 matching lines @@
 }
 
 template <typename T, typename U, typename V>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
                             std::numeric_limits<U>::is_integer &&
                             std::numeric_limits<V>::is_integer,
                         bool>::type
 CheckedAdd(T x, U y, V* result) {
   using Promotion =
       typename ArithmeticPromotion<BIG_ENOUGH_PROMOTION, T, U>::type;
+  Promotion presult;
   // Fail if either operand is out of range for the promoted type.
   // TODO(jschuh): This could be made to work for a broader range of values.
-  if (!IsValueInRangeForNumericType<Promotion>(x) ||
-      !IsValueInRangeForNumericType<Promotion>(y)) {
-    return false;
+  bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
+                  IsValueInRangeForNumericType<Promotion>(y);
+
+  if (IsIntegerArithmeticSafe<Promotion, U, V>::value) {
+    presult = static_cast<Promotion>(x) + static_cast<Promotion>(y);
+  } else {
+    is_valid &= CheckedAddImpl(static_cast<Promotion>(x),

[Tom Sepez, 2016/11/16 21:16:08]

Do we maybe perform an operation here that we would have skipped in the old
code, and is it safe to do so without spewing UBSAN warninging.

[jschuh, 2016/11/16 21:22:28]

The Impl functions should all be safe from undefined behavior. I went through
and cleaned them up a few months ago. If it hits any, file a bug and I'll fix
it.

+                               static_cast<Promotion>(y), &presult);
   }
-
-  Promotion presult;
-  bool is_valid = CheckedAddImpl(static_cast<Promotion>(x),
-                                 static_cast<Promotion>(y), &presult);
   *result = static_cast<V>(presult);
   return is_valid && IsValueInRangeForNumericType<V>(presult);
 }
 
 template <typename T>
 typename std::enable_if<std::numeric_limits<T>::is_integer, bool>::type
 CheckedSubImpl(T x, T y, T* result) {
   // Since the value of x+y is undefined if we have a signed type, we compute
   // it using the unsigned type of the same size.
   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
@@ skipping 10 matching lines @@
 }
 
 template <typename T, typename U, typename V>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
                             std::numeric_limits<U>::is_integer &&
                             std::numeric_limits<V>::is_integer,
                         bool>::type
 CheckedSub(T x, U y, V* result) {
   using Promotion =
       typename ArithmeticPromotion<BIG_ENOUGH_PROMOTION, T, U>::type;
+  Promotion presult;
   // Fail if either operand is out of range for the promoted type.
   // TODO(jschuh): This could be made to work for a broader range of values.
-  if (!IsValueInRangeForNumericType<Promotion>(x) ||
-      !IsValueInRangeForNumericType<Promotion>(y)) {
-    return false;
+  bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
+                  IsValueInRangeForNumericType<Promotion>(y);
+
+  if (IsIntegerArithmeticSafe<Promotion, U, V>::value) {
+    presult = static_cast<Promotion>(x) - static_cast<Promotion>(y);
+  } else {
+    is_valid &= CheckedSubImpl(static_cast<Promotion>(x),
+                               static_cast<Promotion>(y), &presult);
   }
-
-  Promotion presult;
-  bool is_valid = CheckedSubImpl(static_cast<Promotion>(x),
-                                 static_cast<Promotion>(y), &presult);
   *result = static_cast<V>(presult);
   return is_valid && IsValueInRangeForNumericType<V>(presult);
 }
 
 // Integer multiplication is a bit complicated. In the fast case we just
 // we just promote to a twice wider type, and range check the result. In the
 // slow case we need to manually check that the result won't be truncated by
 // checking with division against the appropriate bound.
 template <typename T>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
@@ skipping 47 matching lines @@
 }
 
 template <typename T, typename U, typename V>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
                             std::numeric_limits<U>::is_integer &&
                             std::numeric_limits<V>::is_integer,
                         bool>::type
 CheckedMul(T x, U y, V* result) {
   using Promotion =
       typename ArithmeticPromotion<BIG_ENOUGH_PROMOTION, T, U>::type;
+  Promotion presult;
   // Fail if either operand is out of range for the promoted type.
   // TODO(jschuh): This could be made to work for a broader range of values.
-  if (!IsValueInRangeForNumericType<Promotion>(x) ||
-      !IsValueInRangeForNumericType<Promotion>(y)) {
-    return false;
+  bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
+                  IsValueInRangeForNumericType<Promotion>(y);
+
+  if (IsIntegerArithmeticSafe<Promotion, U, V>::value) {
+    presult = static_cast<Promotion>(x) * static_cast<Promotion>(y);
+  } else {
+    is_valid &= CheckedMulImpl(static_cast<Promotion>(x),
+                               static_cast<Promotion>(y), &presult);
   }
-
-  Promotion presult;
-  bool is_valid = CheckedMulImpl(static_cast<Promotion>(x),
-                                 static_cast<Promotion>(y), &presult);
   *result = static_cast<V>(presult);
   return is_valid && IsValueInRangeForNumericType<V>(presult);
 }
 
 // Division just requires a check for a zero denominator or an invalid negation
 // on signed min/-1.
 template <typename T>
 typename std::enable_if<std::numeric_limits<T>::is_integer, bool>::type
 CheckedDivImpl(T x, T y, T* result) {
   if (y && (!std::numeric_limits<T>::is_signed ||
             x != std::numeric_limits<T>::min() || y != static_cast<T>(-1))) {
     *result = x / y;
     return true;
   }
   return false;
 }
 
 template <typename T, typename U, typename V>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
                             std::numeric_limits<U>::is_integer &&
                             std::numeric_limits<V>::is_integer,
                         bool>::type
 CheckedDiv(T x, U y, V* result) {
   using Promotion =
       typename ArithmeticPromotion<BIG_ENOUGH_PROMOTION, T, U>::type;
+  Promotion presult;
   // Fail if either operand is out of range for the promoted type.
   // TODO(jschuh): This could be made to work for a broader range of values.
-  if (!IsValueInRangeForNumericType<Promotion>(x) ||
-      !IsValueInRangeForNumericType<Promotion>(y)) {
-    return false;
-  }
-
-  Promotion presult;
-  bool is_valid = CheckedDivImpl(static_cast<Promotion>(x),
-                                 static_cast<Promotion>(y), &presult);
+  bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
+                  IsValueInRangeForNumericType<Promotion>(y);
+  is_valid &= CheckedDivImpl(static_cast<Promotion>(x),
+                             static_cast<Promotion>(y), &presult);
   *result = static_cast<V>(presult);
   return is_valid && IsValueInRangeForNumericType<V>(presult);
 }
 
 template <typename T>
 typename std::enable_if<std::numeric_limits<T>::is_integer &&
                             std::numeric_limits<T>::is_signed,
                         bool>::type
 CheckedModImpl(T x, T y, T* result) {
   if (y > 0) {
@@ skipping 243 matching lines @@
       : value_(static_cast<T>(rhs.value())) {}
 
   bool is_valid() const { return std::isfinite(value_); }
   T value() const { return value_; }
 };
 
 }  // namespace internal
 }  // namespace base
 
 #endif  // BASE_NUMERICS_SAFE_MATH_IMPL_H_