| // Copyright 2017 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_CHECKED_MATH_IMPL_H_ | |
| #define BASE_NUMERICS_CHECKED_MATH_IMPL_H_ | |
| #include <stddef.h> | |
| #include <stdint.h> | |
| #include <climits> | |
| #include <cmath> | |
| #include <cstdlib> | |
| #include <limits> | |
| #include <type_traits> | |
| #include "base/numerics/safe_conversions.h" | |
| #include "base/numerics/safe_math_shared_impl.h" | |
| namespace base { | |
| namespace internal { | |
| template <typename T> | |
| constexpr bool CheckedAddImpl(T x, T y, T* result) { | |
| static_assert(std::is_integral<T>::value, "Type must be integral"); | |
| // 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. | |
| using UnsignedDst = typename std::make_unsigned<T>::type; | |
| using SignedDst = typename std::make_signed<T>::type; | |
| UnsignedDst ux = static_cast<UnsignedDst>(x); | |
| UnsignedDst uy = static_cast<UnsignedDst>(y); | |
| UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy); | |
| *result = static_cast<T>(uresult); | |
| // Addition is valid if the sign of (x + y) is equal to either that of x or | |
| // that of y. | |
| return (std::is_signed<T>::value) | |
| ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) >= 0 | |
| : uresult >= uy; // Unsigned is either valid or underflow. | |
| } | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedAddOp {}; | |
| template <typename T, typename U> | |
| struct CheckedAddOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| // TODO(jschuh) Make this "constexpr if" once we're C++17. | |
| if (CheckedAddFastOp<T, U>::is_supported) | |
| return CheckedAddFastOp<T, U>::Do(x, y, result); | |
| // Double the underlying type up to a full machine word. | |
| using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type; | |
| using Promotion = | |
| typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value > | |
| IntegerBitsPlusSign<intptr_t>::value), | |
| typename BigEnoughPromotion<T, U>::type, | |
| FastPromotion>::type; | |
| // 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 (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) || | |
| !IsValueInRangeForNumericType<Promotion>(y))) { | |
| return false; | |
| } | |
| Promotion presult = {}; | |
| bool is_valid = true; | |
| if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { | |
| presult = static_cast<Promotion>(x) + static_cast<Promotion>(y); | |
| } else { | |
| 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> | |
| constexpr bool CheckedSubImpl(T x, T y, T* result) { | |
| static_assert(std::is_integral<T>::value, "Type must be integral"); | |
| // 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. | |
| using UnsignedDst = typename std::make_unsigned<T>::type; | |
| using SignedDst = typename std::make_signed<T>::type; | |
| UnsignedDst ux = static_cast<UnsignedDst>(x); | |
| UnsignedDst uy = static_cast<UnsignedDst>(y); | |
| UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy); | |
| *result = static_cast<T>(uresult); | |
| // Subtraction is valid if either x and y have same sign, or (x-y) and x have | |
| // the same sign. | |
| return (std::is_signed<T>::value) | |
| ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) >= 0 | |
| : x >= y; | |
| } | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedSubOp {}; | |
| template <typename T, typename U> | |
| struct CheckedSubOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| // TODO(jschuh) Make this "constexpr if" once we're C++17. | |
| if (CheckedSubFastOp<T, U>::is_supported) | |
| return CheckedSubFastOp<T, U>::Do(x, y, result); | |
| // Double the underlying type up to a full machine word. | |
| using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type; | |
| using Promotion = | |
| typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value > | |
| IntegerBitsPlusSign<intptr_t>::value), | |
| typename BigEnoughPromotion<T, U>::type, | |
| FastPromotion>::type; | |
| // 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 (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) || | |
| !IsValueInRangeForNumericType<Promotion>(y))) { | |
| return false; | |
| } | |
| Promotion presult = {}; | |
| bool is_valid = true; | |
| if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { | |
| presult = static_cast<Promotion>(x) - static_cast<Promotion>(y); | |
| } else { | |
| is_valid = CheckedSubImpl(static_cast<Promotion>(x), | |
| static_cast<Promotion>(y), &presult); | |
| } | |
| *result = static_cast<V>(presult); | |
| return is_valid && IsValueInRangeForNumericType<V>(presult); | |
| } | |
| }; | |
| template <typename T> | |
| constexpr bool CheckedMulImpl(T x, T y, T* result) { | |
| static_assert(std::is_integral<T>::value, "Type must be integral"); | |
| // 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; | |
| using SignedDst = typename std::make_signed<T>::type; | |
| const UnsignedDst ux = SafeUnsignedAbs(x); | |
| const UnsignedDst uy = SafeUnsignedAbs(y); | |
| UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy); | |
| const bool is_negative = | |
| std::is_signed<T>::value && static_cast<SignedDst>(x ^ y) < 0; | |
| *result = is_negative ? 0 - uresult : uresult; | |
| // We have a fast out for unsigned identity or zero on the second operand. | |
| // After that it's an unsigned overflow check on the absolute value, with | |
| // a +1 bound for a negative result. | |
| return uy <= UnsignedDst(!std::is_signed<T>::value || is_negative) || | |
| ux <= (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy; | |
| } | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedMulOp {}; | |
| template <typename T, typename U> | |
| struct CheckedMulOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| // TODO(jschuh) Make this "constexpr if" once we're C++17. | |
| if (CheckedMulFastOp<T, U>::is_supported) | |
| return CheckedMulFastOp<T, U>::Do(x, y, result); | |
| using Promotion = typename FastIntegerArithmeticPromotion<T, U>::type; | |
| // Verify the destination type can hold the result (always true for 0). | |
| if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) || | |
| !IsValueInRangeForNumericType<Promotion>(y)) && | |
| x && y)) { | |
| return false; | |
| } | |
| Promotion presult = {}; | |
| bool is_valid = true; | |
| if (CheckedMulFastOp<Promotion, Promotion>::is_supported) { | |
| // The fast op may be available with the promoted type. | |
| is_valid = CheckedMulFastOp<Promotion, Promotion>::Do(x, y, &presult); | |
| } else if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { | |
| presult = static_cast<Promotion>(x) * static_cast<Promotion>(y); | |
| } else { | |
| 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 U, class Enable = void> | |
| struct CheckedDivOp {}; | |
| template <typename T, typename U> | |
| struct CheckedDivOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| if (BASE_NUMERICS_UNLIKELY(!y)) | |
| return false; | |
| // The overflow check can be compiled away if we don't have the exact | |
| // combination of types needed to trigger this case. | |
| using Promotion = typename BigEnoughPromotion<T, U>::type; | |
| if (BASE_NUMERICS_UNLIKELY( | |
| (std::is_signed<T>::value && std::is_signed<U>::value && | |
| IsTypeInRangeForNumericType<T, Promotion>::value && | |
| static_cast<Promotion>(x) == | |
| std::numeric_limits<Promotion>::lowest() && | |
| y == static_cast<U>(-1)))) { | |
| return false; | |
| } | |
| // This branch always compiles away if the above branch wasn't removed. | |
| if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) || | |
| !IsValueInRangeForNumericType<Promotion>(y)) && | |
| x)) { | |
| return false; | |
| } | |
| Promotion presult = Promotion(x) / Promotion(y); | |
| *result = static_cast<V>(presult); | |
| return IsValueInRangeForNumericType<V>(presult); | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedModOp {}; | |
| template <typename T, typename U> | |
| struct CheckedModOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| using Promotion = typename BigEnoughPromotion<T, U>::type; | |
| if (BASE_NUMERICS_LIKELY(y)) { | |
| Promotion presult = static_cast<Promotion>(x) % static_cast<Promotion>(y); | |
| *result = static_cast<Promotion>(presult); | |
| return IsValueInRangeForNumericType<V>(presult); | |
| } | |
| return false; | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedLshOp {}; | |
| // Left shift. Shifts less than 0 or greater than or equal to the number | |
| // of bits in the promoted type are undefined. Shifts of negative values | |
| // are undefined. Otherwise it is defined when the result fits. | |
| template <typename T, typename U> | |
| struct CheckedLshOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = T; | |
| template <typename V> | |
| static constexpr bool Do(T x, U shift, V* result) { | |
| // Disallow negative numbers and verify the shift is in bounds. | |
| if (BASE_NUMERICS_LIKELY(!IsValueNegative(x) && | |
| as_unsigned(shift) < | |
| as_unsigned(std::numeric_limits<T>::digits))) { | |
| // Shift as unsigned to avoid undefined behavior. | |
| *result = static_cast<V>(as_unsigned(x) << shift); | |
| // If the shift can be reversed, we know it was valid. | |
| return *result >> shift == x; | |
| } | |
| // Handle the legal corner-case of a full-width signed shift of zero. | |
| return std::is_signed<T>::value && !x && | |
| as_unsigned(shift) == as_unsigned(std::numeric_limits<T>::digits); | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedRshOp {}; | |
| // Right shift. Shifts less than 0 or greater than or equal to the number | |
| // of bits in the promoted type are undefined. Otherwise, it is always defined, | |
| // but a right shift of a negative value is implementation-dependent. | |
| template <typename T, typename U> | |
| struct CheckedRshOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = T; | |
| template <typename V> | |
| static bool Do(T x, U shift, V* result) { | |
| // Use the type conversion push negative values out of range. | |
| if (BASE_NUMERICS_LIKELY(as_unsigned(shift) < | |
| IntegerBitsPlusSign<T>::value)) { | |
| T tmp = x >> shift; | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| return false; | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedAndOp {}; | |
| // For simplicity we support only unsigned integer results. | |
| template <typename T, typename U> | |
| struct CheckedAndOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename std::make_unsigned< | |
| typename MaxExponentPromotion<T, U>::type>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| result_type tmp = static_cast<result_type>(x) & static_cast<result_type>(y); | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedOrOp {}; | |
| // For simplicity we support only unsigned integers. | |
| template <typename T, typename U> | |
| struct CheckedOrOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename std::make_unsigned< | |
| typename MaxExponentPromotion<T, U>::type>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| result_type tmp = static_cast<result_type>(x) | static_cast<result_type>(y); | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| }; | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedXorOp {}; | |
| // For simplicity we support only unsigned integers. | |
| template <typename T, typename U> | |
| struct CheckedXorOp<T, | |
| U, | |
| typename std::enable_if<std::is_integral<T>::value && | |
| std::is_integral<U>::value>::type> { | |
| using result_type = typename std::make_unsigned< | |
| typename MaxExponentPromotion<T, U>::type>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| result_type tmp = static_cast<result_type>(x) ^ static_cast<result_type>(y); | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| }; | |
| // Max doesn't really need to be implemented this way because it can't fail, | |
| // but it makes the code much cleaner to use the MathOp wrappers. | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedMaxOp {}; | |
| template <typename T, typename U> | |
| struct CheckedMaxOp< | |
| T, | |
| U, | |
| typename std::enable_if<std::is_arithmetic<T>::value && | |
| std::is_arithmetic<U>::value>::type> { | |
| using result_type = typename MaxExponentPromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| result_type tmp = IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x) | |
| : static_cast<result_type>(y); | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| }; | |
| // Min doesn't really need to be implemented this way because it can't fail, | |
| // but it makes the code much cleaner to use the MathOp wrappers. | |
| template <typename T, typename U, class Enable = void> | |
| struct CheckedMinOp {}; | |
| template <typename T, typename U> | |
| struct CheckedMinOp< | |
| T, | |
| U, | |
| typename std::enable_if<std::is_arithmetic<T>::value && | |
| std::is_arithmetic<U>::value>::type> { | |
| using result_type = typename LowestValuePromotion<T, U>::type; | |
| template <typename V> | |
| static constexpr bool Do(T x, U y, V* result) { | |
| result_type tmp = IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x) | |
| : static_cast<result_type>(y); | |
| *result = static_cast<V>(tmp); | |
| return IsValueInRangeForNumericType<V>(tmp); | |
| } | |
| }; | |
| // 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 constexpr bool Do(T x, U y, V* result) { \ | |
| using Promotion = typename MaxExponentPromotion<T, U>::type; \ | |
| Promotion presult = x OP y; \ | |
| *result = static_cast<V>(presult); \ | |
| return IsValueInRangeForNumericType<V>(presult); \ | |
| } \ | |
| }; | |
| BASE_FLOAT_ARITHMETIC_OPS(Add, +) | |
| BASE_FLOAT_ARITHMETIC_OPS(Sub, -) | |
| BASE_FLOAT_ARITHMETIC_OPS(Mul, *) | |
| BASE_FLOAT_ARITHMETIC_OPS(Div, /) | |
| #undef BASE_FLOAT_ARITHMETIC_OPS | |
| // 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 NumericRepresentation { | |
| NUMERIC_INTEGER, | |
| NUMERIC_FLOATING, | |
| NUMERIC_UNKNOWN | |
| }; | |
| template <typename NumericType> | |
| struct GetNumericRepresentation { | |
| static const NumericRepresentation value = | |
| std::is_integral<NumericType>::value | |
| ? NUMERIC_INTEGER | |
| : (std::is_floating_point<NumericType>::value ? NUMERIC_FLOATING | |
| : NUMERIC_UNKNOWN); | |
| }; | |
| template <typename T, | |
| NumericRepresentation type = GetNumericRepresentation<T>::value> | |
| class CheckedNumericState {}; | |
| // Integrals require quite a bit of additional housekeeping to manage state. | |
| template <typename T> | |
| class CheckedNumericState<T, NUMERIC_INTEGER> { | |
| private: | |
| // is_valid_ precedes value_ because member initializers in the constructors | |
| // are evaluated in field order, and is_valid_ must be read when initializing | |
| // value_. | |
| bool is_valid_; | |
| T value_; | |
| // Ensures that a type conversion does not trigger undefined behavior. | |
| template <typename Src> | |
| static constexpr T WellDefinedConversionOrZero(const Src value, | |
| const bool is_valid) { | |
| using SrcType = typename internal::UnderlyingType<Src>::type; | |
| return (std::is_integral<SrcType>::value || is_valid) | |
| ? static_cast<T>(value) | |
| : static_cast<T>(0); | |
| } | |
| public: | |
| template <typename Src, NumericRepresentation type> | |
| friend class CheckedNumericState; | |
| constexpr CheckedNumericState() : is_valid_(true), value_(0) {} | |
| template <typename Src> | |
| constexpr CheckedNumericState(Src value, bool is_valid) | |
| : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)), | |
| value_(WellDefinedConversionOrZero(value, is_valid_)) { | |
| static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric."); | |
| } | |
| // Copy constructor. | |
| template <typename Src> | |
| constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs) | |
| : is_valid_(rhs.IsValid()), | |
| value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {} | |
| template <typename Src> | |
| constexpr explicit CheckedNumericState(Src value) | |
| : is_valid_(IsValueInRangeForNumericType<T>(value)), | |
| value_(WellDefinedConversionOrZero(value, is_valid_)) {} | |
| constexpr bool is_valid() const { return is_valid_; } | |
| constexpr 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_; | |
| // Ensures that a type conversion does not trigger undefined behavior. | |
| template <typename Src> | |
| static constexpr T WellDefinedConversionOrNaN(const Src value, | |
| const bool is_valid) { | |
| using SrcType = typename internal::UnderlyingType<Src>::type; | |
| return (StaticDstRangeRelationToSrcRange<T, SrcType>::value == | |
| NUMERIC_RANGE_CONTAINED || | |
| is_valid) | |
| ? static_cast<T>(value) | |
| : std::numeric_limits<T>::quiet_NaN(); | |
| } | |
| public: | |
| template <typename Src, NumericRepresentation type> | |
| friend class CheckedNumericState; | |
| constexpr CheckedNumericState() : value_(0.0) {} | |
| template <typename Src> | |
| constexpr CheckedNumericState(Src value, bool is_valid) | |
| : value_(WellDefinedConversionOrNaN(value, is_valid)) {} | |
| template <typename Src> | |
| constexpr explicit CheckedNumericState(Src value) | |
| : value_(WellDefinedConversionOrNaN( | |
| value, | |
| IsValueInRangeForNumericType<T>(value))) {} | |
| // Copy constructor. | |
| template <typename Src> | |
| constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs) | |
| : value_(WellDefinedConversionOrNaN( | |
| rhs.value(), | |
| rhs.is_valid() && IsValueInRangeForNumericType<T>(rhs.value()))) {} | |
| constexpr bool is_valid() const { | |
| // Written this way because std::isfinite is not reliably constexpr. | |
| return MustTreatAsConstexpr(value_) | |
| ? value_ <= std::numeric_limits<T>::max() && | |
| value_ >= std::numeric_limits<T>::lowest() | |
| : std::isfinite(value_); | |
| } | |
| constexpr T value() const { return value_; } | |
| }; | |
| } // namespace internal | |
| } // namespace base | |
| #endif // BASE_NUMERICS_CHECKED_MATH_IMPL_H_ |