Index: base/numerics/safe_math_impl.h |
diff --git a/base/numerics/safe_math_impl.h b/base/numerics/safe_math_impl.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..637eda7f3db7dab1f002a1a412e5c500e3d3ffef |
--- /dev/null |
+++ b/base/numerics/safe_math_impl.h |
@@ -0,0 +1,481 @@ |
+// 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 SAFE_MATH_IMPL_H_ |
+#define SAFE_MATH_IMPL_H_ |
+ |
+#include <stdint.h> |
+ |
+#include <cmath> |
+#include <cstdlib> |
+#include <limits> |
+ |
+#include "base/compiler_specific.h" |
+#include "base/macros.h" |
+#include "base/template_util.h" |
+ |
+namespace base { |
+namespace internal { |
+ |
+using std::numeric_limits; |
+ |
+// Everything from here up to the floating point operations is portable C++, |
+// but it may not be fast. This code could be split based on |
+// platform/architecture and replaced with potentially faster implementations. |
+ |
+// Integer promotion templates used by the portable checked integer arithmetic. |
+template <size_t Size, bool IsSigned> |
+struct IntegerForSizeAndSign {}; |
awong
2014/02/11 20:14:12
Here and elsewhere, don't provide a definition for
jschuh
2014/02/21 19:22:28
Done.
|
+template <> |
+struct IntegerForSizeAndSign<1, true> { |
+ typedef int8_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<1, false> { |
+ typedef uint8_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<2, true> { |
+ typedef int16_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<2, false> { |
+ typedef uint16_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<4, true> { |
+ typedef int32_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<4, false> { |
+ typedef uint32_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<8, true> { |
+ typedef int64_t type; |
+}; |
+template <> |
+struct IntegerForSizeAndSign<8, false> { |
+ typedef uint64_t type; |
+}; |
+// The ArithmeticPromotion template below will need to be updated (or more |
awong
2014/02/11 20:14:12
This looks like a TODO. Make it into a TODO?
Also
jschuh
2014/02/21 19:22:28
We don't support 128-bit math today, so it's a war
|
+// likely replaced with decltype) if we add support for 128-bit integers). |
+ |
+template <typename Integer> |
+struct UnsignedIntegerForSize { |
+ typedef typename enable_if< |
awong
2014/02/11 20:14:12
Why do we need an enable_if here? Normally you use
jschuh
2014/02/21 19:22:28
I'm preventing this:
UnsignedIntegerForSize<flo
|
+ numeric_limits<Integer>::is_integer, |
+ typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type; |
+}; |
+ |
+template <typename Integer> |
+struct SignedIntegerForSize { |
+ typedef typename enable_if< |
+ numeric_limits<Integer>::is_integer, |
+ typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type; |
+}; |
+ |
+template <typename Integer> |
+struct TwiceWiderInteger { |
+ typedef typename enable_if< |
+ numeric_limits<Integer>::is_integer, |
+ typename IntegerForSizeAndSign< |
+ sizeof(Integer) * 2, |
+ numeric_limits<Integer>::is_signed>::type>::type type; |
+}; |
+ |
+template <typename Integer> |
+struct PositionOfSignBit { |
+ static const typename enable_if<numeric_limits<Integer>::is_integer, |
+ size_t>::type value = 8 * sizeof(Integer) - 1; |
+}; |
+ |
+// Helper templates for integer manipulations. |
+ |
+template <typename T> |
+bool HasSignBit(T x) { |
+ // Cast to unsigned since right shift on signed is undefined. |
+ return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >> |
+ PositionOfSignBit<T>::value); |
+} |
+ |
+// This wrapper undoes the standard integer promotions. |
+template <typename T> |
+T BinaryComplement(T x) { |
+ return ~x; |
+} |
+ |
+// Here are the actual portable checked integer implementations. |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer, T>::type |
+CheckedAdd(T x, T y, RangeCheckId* validity) { |
+ // 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; |
+ UnsignedDst ux = static_cast<UnsignedDst>(x); |
+ UnsignedDst uy = static_cast<UnsignedDst>(y); |
+ UnsignedDst uresult = ux + uy; |
+ // Addition is valid if the sign of (x + y) is equal to either that of x or |
+ // that of y. |
+ if (numeric_limits<T>::is_signed) { |
+ if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy)))) |
+ *validity = TYPE_VALID; |
+ else // Direction of wrap is inverse of result sign. |
+ *validity = HasSignBit(uresult) ? TYPE_OVERFLOW : TYPE_UNDERFLOW; |
+ |
+ } else { // Unsigned is either valid or overflow. |
+ *validity = BinaryComplement(x) >= y ? TYPE_VALID : TYPE_OVERFLOW; |
+ } |
+ return static_cast<T>(uresult); |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer, T>::type |
+CheckedSub(T x, T y, RangeCheckId* validity) { |
+ // 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; |
+ UnsignedDst ux = static_cast<UnsignedDst>(x); |
+ UnsignedDst uy = static_cast<UnsignedDst>(y); |
+ UnsignedDst uresult = ux - uy; |
+ // Subtraction is valid if either x and y have same sign, or (x-y) and x have |
+ // the same sign. |
+ if (numeric_limits<T>::is_signed) { |
+ if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy)))) |
+ *validity = TYPE_VALID; |
+ else // Direction of wrap is inverse of result sign. |
+ *validity = HasSignBit(uresult) ? TYPE_OVERFLOW : TYPE_UNDERFLOW; |
+ |
+ } else { // Unsigned is either valid or underflow. |
+ *validity = x >= y ? TYPE_VALID : TYPE_UNDERFLOW; |
+ } |
+ return static_cast<T>(uresult); |
+} |
+ |
+// 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 enable_if< |
+ numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t), |
+ T>::type |
+CheckedMul(T x, T y, RangeCheckId* validity) { |
+ typedef typename TwiceWiderInteger<T>::type IntermediateType; |
+ IntermediateType tmp = |
+ static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y); |
+ *validity = RangeCheck<T>(tmp); |
+ return static_cast<T>(tmp); |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer&& numeric_limits< |
awong
2014/02/11 20:14:12
Yes...it's looking like you're using enable_if to
jschuh
2014/02/21 19:22:28
This is breaking out the specializations. Based on
|
+ T>::is_signed&&(sizeof(T) * 2 > sizeof(uintmax_t)), |
+ T>::type |
+CheckedMul(T x, T y, RangeCheckId* validity) { |
+ // if either side is zero then the result will be zero. |
+ if (!(x || y)) { |
+ return TYPE_VALID; |
+ |
+ } else if (x > 0) { |
+ if (y > 0) |
+ *validity = |
+ x <= numeric_limits<T>::max() / y ? TYPE_VALID : TYPE_OVERFLOW; |
+ else |
+ *validity = |
+ y >= numeric_limits<T>::min() / x ? TYPE_VALID : TYPE_UNDERFLOW; |
+ |
+ } else { |
+ if (y > 0) |
+ *validity = |
+ x >= numeric_limits<T>::min() / y ? TYPE_VALID : TYPE_UNDERFLOW; |
+ else |
+ *validity = |
+ y >= numeric_limits<T>::max() / x ? TYPE_VALID : TYPE_OVERFLOW; |
+ } |
+ |
+ return x * y; |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer && |
+ !numeric_limits<T>::is_signed && |
+ (sizeof(T) * 2 > sizeof(uintmax_t)), |
+ T>::type |
+CheckedMul(T x, T y, RangeCheckId* validity) { |
+ *validity = (y == 0 || x <= numeric_limits<T>::max() / y) ? TYPE_VALID |
+ : TYPE_OVERFLOW; |
+ return x * y; |
+} |
+ |
+// Division just requires a check for an invalid negation on signed min/-1. |
+template <typename T> |
+T CheckedDiv(T x, |
+ T y, |
+ RangeCheckId* validity, |
+ typename enable_if<numeric_limits<T>::is_integer, int>::type = 0) { |
+ if (numeric_limits<T>::is_signed && x == numeric_limits<T>::min() && |
+ y == static_cast<T>(-1)) { |
+ *validity = TYPE_OVERFLOW; |
+ return numeric_limits<T>::min(); |
+ } |
+ |
+ *validity = TYPE_VALID; |
+ return x / y; |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer&& numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedMod(T x, T y, RangeCheckId* validity) { |
+ *validity = y > 0 ? TYPE_VALID : TYPE_INVALID; |
+ return x % y; |
+} |
+ |
+template <typename T> |
+typename enable_if< |
+ numeric_limits<T>::is_integer && !numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedMod(T x, T y, RangeCheckId* validity) { |
+ *validity = TYPE_VALID; |
+ return x % y; |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer&& numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedNeg(T value, RangeCheckId* validity) { |
+ *validity = value != numeric_limits<T>::min() ? TYPE_VALID : TYPE_OVERFLOW; |
+ // The negation of signed min is min, so catch that one. |
+ return -value; |
+} |
+ |
+template <typename T> |
+typename enable_if< |
+ numeric_limits<T>::is_integer && !numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedNeg(T value, RangeCheckId* validity) { |
+ // The only legal unsigned negation is zero. |
+ *validity = value ? TYPE_UNDERFLOW : TYPE_VALID; |
+ return static_cast<T>( |
+ -static_cast<typename SignedIntegerForSize<T>::type>(value)); |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_integer&& numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedAbs(T value, RangeCheckId* validity) { |
+ *validity = value != numeric_limits<T>::min() ? TYPE_VALID : TYPE_OVERFLOW; |
+ return std::abs(value); |
+} |
+ |
+template <typename T> |
+typename enable_if< |
+ numeric_limits<T>::is_integer && !numeric_limits<T>::is_signed, |
+ T>::type |
+CheckedAbs(T value, RangeCheckId* validity) { |
+ // Absolute value of a positive is just its identiy. |
+ *validity = TYPE_VALID; |
+ return value; |
+} |
+ |
+// These are the floating point stubs that the compiler needs to see. Only the |
+// negation operation is ever called. |
+#define BASE_FLOAT_ARITHMETIC_STUBS(NAME) \ |
+ template <typename T> \ |
+ typename enable_if<numeric_limits<T>::is_iec559, T>::type Checked##NAME( \ |
+ T, T, RangeCheckId*) { \ |
+ NOTREACHED(); \ |
+ return 0; \ |
+ } |
+ |
+BASE_FLOAT_ARITHMETIC_STUBS(Add) |
+BASE_FLOAT_ARITHMETIC_STUBS(Sub) |
+BASE_FLOAT_ARITHMETIC_STUBS(Mul) |
+BASE_FLOAT_ARITHMETIC_STUBS(Div) |
+BASE_FLOAT_ARITHMETIC_STUBS(Mod) |
+ |
+#undef BASE_FLOAT_ARITHMETIC_STUBS |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_iec559, T>::type CheckedNeg( |
+ T value, |
+ RangeCheckId*) { |
+ return -value; |
+} |
+ |
+template <typename T> |
+typename enable_if<numeric_limits<T>::is_iec559, T>::type CheckedAbs( |
+ T value, |
+ RangeCheckId*) { |
+ return std::abs(value); |
+} |
+ |
+// Floats carry around their validity state with them, but integers do not. So, |
+// we wrap the underlying value in a specialization in order to hide that detail |
+// and expose an interface via accessors. |
+enum NumericTypeId { NUMERIC_INTEGER, NUMERIC_FLOATING, NUMERIC_UNKNOWN }; |
+ |
+template <typename NumericType> |
+struct GetNumericTypeId { |
+ static const NumericTypeId value = |
+ numeric_limits<NumericType>::is_integer |
+ ? NUMERIC_INTEGER |
+ : (numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING |
+ : NUMERIC_UNKNOWN); |
+}; |
+ |
+template <typename T, NumericTypeId type = GetNumericTypeId<T>::value> |
+class CheckedNumericState {}; |
+ |
+// Integrals require quite a bit of additional housekeeping to manage state. |
+template <typename T> |
+class CheckedNumericState<T, NUMERIC_INTEGER> { |
+ private: |
+ T value_; |
+ RangeCheckId validity_; |
+ |
+ public: |
+ template <typename Src, NumericTypeId type> |
+ friend class CheckedNumericState; |
+ |
+ CheckedNumericState() : value_(0), validity_(TYPE_VALID) {} |
+ |
+ template <typename Src> |
+ CheckedNumericState(Src value, RangeCheckId validity) |
+ : value_(value), |
+ validity_(static_cast<RangeCheckId>(validity | RangeCheck<T>(value))) { |
+ COMPILE_ASSERT(numeric_limits<Src>::is_specialized, |
+ argument_must_be_numeric); |
+ } |
+ |
+ // Copy constructor. |
+ template <typename Src> |
+ CheckedNumericState(const CheckedNumericState<Src>& rhs) |
+ : value_(static_cast<T>(rhs.value())), |
+ validity_(static_cast<RangeCheckId>(rhs.validity() | |
+ RangeCheck<T>(rhs.value()))) {} |
+ |
+ template <typename Src> |
+ explicit CheckedNumericState( |
+ Src value, |
+ typename enable_if<numeric_limits<Src>::is_specialized, int>::type = 0) |
+ : value_(static_cast<T>(value)), validity_(RangeCheck<T>(value)) {} |
+ |
+ RangeCheckId validity() const { return validity_; } |
+ T value() const { return value_; } |
+}; |
+ |
+// Floating points maintain their own validity, but need translation wrappers. |
+template <typename T> |
+class CheckedNumericState<T, NUMERIC_FLOATING> { |
+ private: |
+ T value_; |
+ |
+ public: |
+ template <typename Src, NumericTypeId type> |
+ friend class CheckedNumericState; |
+ |
+ CheckedNumericState() : value_(0.0) {} |
+ |
+ template <typename Src> |
+ CheckedNumericState( |
+ Src value, |
+ RangeCheckId validity, |
+ typename enable_if<numeric_limits<Src>::is_integer, int>::type = 0) { |
+ switch (RangeCheck<T>(value)) { |
+ case TYPE_VALID: |
+ value_ = static_cast<T>(value); |
+ break; |
+ |
+ case TYPE_UNDERFLOW: |
+ value_ = -numeric_limits<T>::infinity(); |
+ break; |
+ |
+ case TYPE_OVERFLOW: |
+ value_ = numeric_limits<T>::infinity(); |
+ break; |
+ |
+ case TYPE_INVALID: |
+ value_ = numeric_limits<T>::quiet_NaN(); |
+ break; |
+ |
+ default: |
+ NOTREACHED(); |
+ } |
+ } |
+ |
+ template <typename Src> |
+ explicit CheckedNumericState( |
+ Src value, |
+ typename enable_if<numeric_limits<Src>::is_specialized, int>::type = 0) |
+ : value_(static_cast<T>(value)) {} |
+ |
+ // Copy constructor. |
+ template <typename Src> |
+ CheckedNumericState(const CheckedNumericState<Src>& rhs) |
+ : value_(static_cast<T>(rhs.value())) {} |
+ |
+ RangeCheckId validity() const { |
+ return BASE_NUMERIC_RANGE_CHECK_RESULT(value_ <= numeric_limits<T>::max(), |
+ value_ >= -numeric_limits<T>::max()); |
+ } |
+ T value() const { return value_; } |
+}; |
+ |
+// For integers less than 128-bit and floats 32-bit or larger, we can distil |
+// C/C++ arithmetic promotions down to two simple rules: |
+// 1. The type with the larger maximum exponent always takes precedence. |
+// 2. The resulting type must be promoted to at least an int. |
+// The following template specializations implement that promotion logic. |
+enum ArithmeticPromotionId { |
+ LEFT_PROMOTION, |
+ RIGHT_PROMOTION, |
+ DEFAULT_PROMOTION |
+}; |
+ |
+template <typename Lhs, |
+ typename Rhs = Lhs, |
+ ArithmeticPromotionId Promotion = |
+ (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) |
+ ? (MaxExponent<Lhs>::value > MaxExponent<int>::value |
+ ? LEFT_PROMOTION |
+ : DEFAULT_PROMOTION) |
+ : (MaxExponent<Rhs>::value > MaxExponent<int>::value |
+ ? RIGHT_PROMOTION |
+ : DEFAULT_PROMOTION) > struct ArithmeticPromotion {}; |
+ |
+template <typename Lhs, typename Rhs> |
+struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> { |
+ typedef Lhs type; |
+}; |
+ |
+template <typename Lhs, typename Rhs> |
+struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> { |
+ typedef Rhs type; |
+}; |
+ |
+template <typename Lhs, typename Rhs> |
+struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> { |
+ typedef int type; |
+}; |
+ |
+// 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 = !numeric_limits<T>::is_iec559 && |
+ StaticRangeCheck<T, Lhs>::value == CONTAINS_RANGE && |
+ sizeof(T) >= (2 * sizeof(Lhs)) && |
+ StaticRangeCheck<T, Rhs>::value != CONTAINS_RANGE && |
+ sizeof(T) >= (2 * sizeof(Rhs)); |
+}; |
+ |
+} // namespace internal |
+} // namespace base |
+ |
+#endif // SAFE_MATH_IMPL_H_ |