diff options
Diffstat (limited to 'gfx/angle/checkout/src/common/third_party/base/anglebase/numerics/checked_math_impl.h')
| -rw-r--r-- | gfx/angle/checkout/src/common/third_party/base/anglebase/numerics/checked_math_impl.h | 641 |
1 files changed, 641 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/common/third_party/base/anglebase/numerics/checked_math_impl.h b/gfx/angle/checkout/src/common/third_party/base/anglebase/numerics/checked_math_impl.h new file mode 100644 index 0000000000..e4b6082770 --- /dev/null +++ b/gfx/angle/checkout/src/common/third_party/base/anglebase/numerics/checked_math_impl.h @@ -0,0 +1,641 @@ +// 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 "anglebase/numerics/safe_conversions.h" +#include "anglebase/numerics/safe_math_shared_impl.h" + +namespace angle +{ +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; + const UnsignedDst ux = static_cast<UnsignedDst>(x); + const UnsignedDst uy = static_cast<UnsignedDst>(y); + const UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy); + // Addition is valid if the sign of (x + y) is equal to either that of x or + // that of y. + if (std::is_signed<T>::value ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) < 0 + : uresult < uy) // Unsigned is either valid or underflow. + return false; + *result = static_cast<T>(uresult); + return true; +} + +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) + { + if constexpr (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 constexpr (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); + } + if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) + return false; + *result = static_cast<V>(presult); + return true; + } +}; + +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; + const UnsignedDst ux = static_cast<UnsignedDst>(x); + const UnsignedDst uy = static_cast<UnsignedDst>(y); + const UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy); + // Subtraction is valid if either x and y have same sign, or (x-y) and x have + // the same sign. + if (std::is_signed<T>::value ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) < 0 : x < y) + return false; + *result = static_cast<T>(uresult); + return true; +} + +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) + { + if constexpr (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 constexpr (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); + } + if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) + return false; + *result = static_cast<V>(presult); + return true; + } +}; + +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); + const UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy); + const bool is_negative = std::is_signed<T>::value && static_cast<SignedDst>(x ^ y) < 0; + // 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. + if (uy > UnsignedDst(!std::is_signed<T>::value || is_negative) && + ux > (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy) + return false; + *result = is_negative ? 0 - uresult : uresult; + return true; +} + +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) + { + if constexpr (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 constexpr (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); + } + if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) + return false; + *result = static_cast<V>(presult); + return true; + } +}; + +// 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; + } + + const Promotion presult = Promotion(x) / Promotion(y); + if (!IsValueInRangeForNumericType<V>(presult)) + return false; + *result = static_cast<V>(presult); + return true; + } +}; + +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) + { + if (BASE_NUMERICS_UNLIKELY(!y)) + return false; + + 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)))) + { + *result = 0; + return true; + } + + const Promotion presult = static_cast<Promotion>(x) % static_cast<Promotion>(y); + if (!IsValueInRangeForNumericType<V>(presult)) + return false; + *result = static_cast<Promotion>(presult); + return true; + } +}; + +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. + if (!std::is_signed<T>::value || x || + as_unsigned(shift) != as_unsigned(std::numeric_limits<T>::digits)) + return false; + *result = 0; + return true; + } +}; + +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 sign conversion to push negative values out of range. + if (BASE_NUMERICS_UNLIKELY(as_unsigned(shift) >= IntegerBitsPlusSign<T>::value)) + { + return false; + } + + const T tmp = x >> shift; + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +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) + { + const result_type tmp = static_cast<result_type>(x) & static_cast<result_type>(y); + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +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) + { + const result_type tmp = static_cast<result_type>(x) | static_cast<result_type>(y); + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +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) + { + const result_type tmp = static_cast<result_type>(x) ^ static_cast<result_type>(y); + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +// 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) + { + const result_type tmp = + IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x) : static_cast<result_type>(y); + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +// 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) + { + const result_type tmp = + IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x) : static_cast<result_type>(y); + if (!IsValueInRangeForNumericType<V>(tmp)) + return false; + *result = static_cast<V>(tmp); + return true; + } +}; + +// 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; \ + const Promotion presult = x OP y; \ + if (!IsValueInRangeForNumericType<V>(presult)) \ + return false; \ + *result = static_cast<V>(presult); \ + return true; \ + } \ + }; + +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> +{ + public: + template <typename Src = int> + constexpr explicit CheckedNumericState(Src value = 0, bool is_valid = true) + : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)), + value_(WellDefinedConversionOrZero(value, is_valid_)) + { + static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric."); + } + + template <typename Src> + constexpr CheckedNumericState(const CheckedNumericState<Src> &rhs) + : CheckedNumericState(rhs.value(), rhs.is_valid()) + {} + + constexpr bool is_valid() const { return is_valid_; } + + constexpr T value() const { return value_; } + + private: + // Ensures that a type conversion does not trigger undefined behavior. + template <typename Src> + static constexpr T WellDefinedConversionOrZero(Src value, bool is_valid) + { + using SrcType = typename internal::UnderlyingType<Src>::type; + return (std::is_integral<SrcType>::value || is_valid) ? static_cast<T>(value) : 0; + } + + // is_valid_ precedes value_ because member intializers in the constructors + // are evaluated in field order, and is_valid_ must be read when initializing + // value_. + bool is_valid_; + T value_; +}; + +// Floating points maintain their own validity, but need translation wrappers. +template <typename T> +class CheckedNumericState<T, NUMERIC_FLOATING> +{ + public: + template <typename Src = double> + constexpr explicit CheckedNumericState(Src value = 0.0, bool is_valid = true) + : value_( + WellDefinedConversionOrNaN(value, is_valid && IsValueInRangeForNumericType<T>(value))) + {} + + template <typename Src> + constexpr CheckedNumericState(const CheckedNumericState<Src> &rhs) + : CheckedNumericState(rhs.value(), rhs.is_valid()) + {} + + 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_; } + + private: + // Ensures that a type conversion does not trigger undefined behavior. + template <typename Src> + static constexpr T WellDefinedConversionOrNaN(Src value, 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(); + } + + T value_; +}; + +} // namespace internal +} // namespace base +} // namespace angle + +#endif // BASE_NUMERICS_CHECKED_MATH_IMPL_H_ |