diff options
Diffstat (limited to 'third_party/base/numerics/safe_math_impl.h')
| -rw-r--r-- | third_party/base/numerics/safe_math_impl.h | 863 |
1 files changed, 482 insertions, 381 deletions
diff --git a/third_party/base/numerics/safe_math_impl.h b/third_party/base/numerics/safe_math_impl.h index f950f5d517..5ad79ce192 100644 --- a/third_party/base/numerics/safe_math_impl.h +++ b/third_party/base/numerics/safe_math_impl.h @@ -14,7 +14,6 @@ #include <limits> #include <type_traits> -#include "third_party/base/macros.h" #include "third_party/base/numerics/safe_conversions.h" namespace pdfium { @@ -25,355 +24,486 @@ namespace internal { // 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; -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; -}; - -// WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to -// support 128-bit math, then the ArithmeticPromotion template below will need -// to be updated (or more likely replaced with a decltype expression). - -template <typename Integer> -struct UnsignedIntegerForSize { - typedef typename std::enable_if< - std::numeric_limits<Integer>::is_integer, - typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type; -}; - -template <typename Integer> -struct SignedIntegerForSize { - typedef typename std::enable_if< - std::numeric_limits<Integer>::is_integer, - typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type; -}; - -template <typename Integer> -struct TwiceWiderInteger { - typedef typename std::enable_if< - std::numeric_limits<Integer>::is_integer, - typename IntegerForSizeAndSign< - sizeof(Integer) * 2, - std::numeric_limits<Integer>::is_signed>::type>::type type; -}; - -template <typename Integer> -struct PositionOfSignBit { - static const typename std::enable_if<std::numeric_limits<Integer>::is_integer, - size_t>::type value = - CHAR_BIT * sizeof(Integer) - 1; -}; - // This is used for UnsignedAbs, where we need to support floating-point // template instantiations even though we don't actually support the operations. -// However, there is no corresponding implementation of e.g. CheckedUnsignedAbs, +// However, there is no corresponding implementation of e.g. SafeUnsignedAbs, // so the float versions will not compile. template <typename Numeric, - bool IsInteger = std::numeric_limits<Numeric>::is_integer, - bool IsFloat = std::numeric_limits<Numeric>::is_iec559> + bool IsInteger = std::is_integral<Numeric>::value, + bool IsFloat = std::is_floating_point<Numeric>::value> struct UnsignedOrFloatForSize; template <typename Numeric> struct UnsignedOrFloatForSize<Numeric, true, false> { - typedef typename UnsignedIntegerForSize<Numeric>::type type; + using type = typename std::make_unsigned<Numeric>::type; }; template <typename Numeric> struct UnsignedOrFloatForSize<Numeric, false, true> { - typedef Numeric type; + 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 UnsignedIntegerForSize<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); -} - -// 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. +// 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> -typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type -CheckedAdd(T x, T y, RangeConstraint* validity) { +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. - typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; + 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. - if (std::numeric_limits<T>::is_signed) { - if (HasSignBit(BinaryComplement( - static_cast<UnsignedDst>((uresult ^ ux) & (uresult ^ uy))))) { - *validity = RANGE_VALID; - } else { // Direction of wrap is inverse of result sign. - *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; + 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 bool Do(T x, U y, V* result) { +#if USE_OVERFLOW_BUILTINS + return !__builtin_add_overflow(x, y, result); +#else + using Promotion = typename BigEnoughPromotion<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. + bool is_valid = IsValueInRangeForNumericType<Promotion>(x) && + IsValueInRangeForNumericType<Promotion>(y); + + 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); } - } else { // Unsigned is either valid or overflow. - *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW; + *result = static_cast<V>(presult); + return is_valid && IsValueInRangeForNumericType<V>(presult); +#endif } - return static_cast<T>(uresult); -} +}; template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type -CheckedSub(T x, T y, RangeConstraint* validity) { +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. - typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; + 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. - if (std::numeric_limits<T>::is_signed) { - if (HasSignBit(BinaryComplement( - static_cast<UnsignedDst>((uresult ^ ux) & (ux ^ uy))))) { - *validity = RANGE_VALID; - } else { // Direction of wrap is inverse of result sign. - *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; + 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 bool Do(T x, U y, V* result) { +#if USE_OVERFLOW_BUILTINS + return !__builtin_sub_overflow(x, y, result); +#else + using Promotion = typename BigEnoughPromotion<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. + bool is_valid = IsValueInRangeForNumericType<Promotion>(x) && + IsValueInRangeForNumericType<Promotion>(y); + + 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); } - } else { // Unsigned is either valid or underflow. - *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW; + *result = static_cast<V>(presult); + return is_valid && IsValueInRangeForNumericType<V>(presult); +#endif } - 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 std::enable_if<std::numeric_limits<T>::is_integer && - sizeof(T) * 2 <= sizeof(uintmax_t), - T>::type -CheckedMul(T x, T y, RangeConstraint* validity) { - typedef typename TwiceWiderInteger<T>::type IntermediateType; - IntermediateType tmp = - static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y); - *validity = DstRangeRelationToSrcRange<T>(tmp); - return static_cast<T>(tmp); +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 std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed && - (sizeof(T) * 2 > sizeof(uintmax_t)), - T>::type -CheckedMul(T x, T y, RangeConstraint* validity) { - // If either side is zero then the result will be zero. - if (!x || !y) { - *validity = RANGE_VALID; - return static_cast<T>(0); - } - if (x > 0) { - if (y > 0) { - *validity = - x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW; +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 bool Do(T x, U y, V* result) { +#if USE_OVERFLOW_BUILTINS +#if defined(__clang__) + // TODO(jschuh): Get the Clang runtime library issues sorted out so we can + // support full-width, mixed-sign multiply builtins. + // https://crbug.com/613003 + static const bool kUseMaxInt = + // Narrower type than uintptr_t is always safe. + std::numeric_limits<__typeof__(x * y)>::digits < + std::numeric_limits<intptr_t>::digits || + // Safe for intptr_t and uintptr_t if the sign matches. + (IntegerBitsPlusSign<__typeof__(x * y)>::value == + IntegerBitsPlusSign<intptr_t>::value && + std::is_signed<T>::value == std::is_signed<U>::value); +#else + static const bool kUseMaxInt = true; +#endif + if (kUseMaxInt) + return !__builtin_mul_overflow(x, y, result); +#endif + using Promotion = typename FastIntegerArithmeticPromotion<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. + bool is_valid = IsValueInRangeForNumericType<Promotion>(x) && + IsValueInRangeForNumericType<Promotion>(y); + + if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { + presult = static_cast<Promotion>(x) * static_cast<Promotion>(y); } else { - *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID - : RANGE_UNDERFLOW; - } - } else { - if (y > 0) { - *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID - : RANGE_UNDERFLOW; - } else { - *validity = - y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW; + is_valid &= CheckedMulImpl(static_cast<Promotion>(x), + static_cast<Promotion>(y), &presult); } + *result = static_cast<V>(presult); + return is_valid && IsValueInRangeForNumericType<V>(presult); } - return static_cast<T>(*validity == RANGE_VALID ? x * y : 0); -} +}; -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed && - (sizeof(T) * 2 > sizeof(uintmax_t)), - T>::type -CheckedMul(T x, T y, RangeConstraint* validity) { - *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y) - ? RANGE_VALID - : RANGE_OVERFLOW; - return static_cast<T>(*validity == RANGE_VALID ? x * y : 0); -} +// Avoid poluting the namespace once we're done with the macro. +#undef USE_OVERFLOW_BUILTINS // Division just requires a check for a zero denominator or an invalid negation // on signed min/-1. template <typename T> -T CheckedDiv(T x, - T y, - RangeConstraint* validity, - typename std::enable_if<std::numeric_limits<T>::is_integer, - int>::type = 0) { - if (y == 0) { - *validity = RANGE_INVALID; - return static_cast<T>(0); - } - if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() && - y == static_cast<T>(-1)) { - *validity = RANGE_OVERFLOW; - return std::numeric_limits<T>::min(); +bool CheckedDivImpl(T x, T y, T* result) { + static_assert(std::is_integral<T>::value, "Type must be integral"); + if (y && (!std::is_signed<T>::value || + x != std::numeric_limits<T>::lowest() || y != static_cast<T>(-1))) { + *result = x / y; + return true; } - - *validity = RANGE_VALID; - return static_cast<T>(x / y); + return false; } -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, - T>::type -CheckedMod(T x, T y, RangeConstraint* validity) { - *validity = y > 0 ? RANGE_VALID : RANGE_INVALID; - return static_cast<T>(*validity == RANGE_VALID ? x % y : 0); -} +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 bool Do(T x, U y, V* result) { + using Promotion = typename BigEnoughPromotion<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. + 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, - T>::type -CheckedMod(T x, T y, RangeConstraint* validity) { - *validity = y != 0 ? RANGE_VALID : RANGE_INVALID; - return static_cast<T>(*validity == RANGE_VALID ? x % y : 0); +bool CheckedModImpl(T x, T y, T* result) { + static_assert(std::is_integral<T>::value, "Type must be integral"); + if (y > 0) { + *result = static_cast<T>(x % y); + return true; + } + return false; } -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, - T>::type -CheckedNeg(T value, RangeConstraint* validity) { - *validity = - value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; - // The negation of signed min is min, so catch that one. - return static_cast<T>(*validity == RANGE_VALID ? -value : 0); -} +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 bool Do(T x, U y, V* result) { + using Promotion = typename BigEnoughPromotion<T, U>::type; + Promotion presult; + bool is_valid = CheckedModImpl(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, - T>::type -CheckedNeg(T value, RangeConstraint* validity) { - // The only legal unsigned negation is zero. - *validity = value ? RANGE_UNDERFLOW : RANGE_VALID; - return static_cast<T>( - *validity == RANGE_VALID - ? -static_cast<typename SignedIntegerForSize<T>::type>(value) - : 0); -} +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 bool Do(T x, U shift, V* result) { + using ShiftType = typename std::make_unsigned<T>::type; + static const ShiftType kBitWidth = IntegerBitsPlusSign<T>::value; + const ShiftType real_shift = static_cast<ShiftType>(shift); + // Signed shift is not legal on negative values. + if (!IsValueNegative(x) && real_shift < kBitWidth) { + // Just use a multiplication because it's easy. + // TODO(jschuh): This could probably be made more efficient. + if (!std::is_signed<T>::value || real_shift != kBitWidth - 1) + return CheckedMulOp<T, T>::Do(x, static_cast<T>(1) << shift, result); + return !x; // Special case zero for a full width signed shift. + } + return false; + } +}; -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, - T>::type -CheckedAbs(T value, RangeConstraint* validity) { - *validity = - value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; - return static_cast<T>(*validity == RANGE_VALID ? std::abs(value) : 0); -} +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 = result_type> + static bool Do(T x, U shift, V* result) { + // Use the type conversion push negative values out of range. + using ShiftType = typename std::make_unsigned<T>::type; + if (static_cast<ShiftType>(shift) < IntegerBitsPlusSign<T>::value) { + T tmp = x >> shift; + *result = static_cast<V>(tmp); + return IsValueInRangeForNumericType<V>(tmp); + } + return false; + } +}; -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, - T>::type -CheckedAbs(T value, RangeConstraint* validity) { - // T is unsigned, so |value| must already be positive. - *validity = RANGE_VALID; - return value; -} +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 = result_type> + static 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 std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, - typename UnsignedIntegerForSize<T>::type>::type -CheckedUnsignedAbs(T value) { - typedef typename UnsignedIntegerForSize<T>::type UnsignedT; - return value == std::numeric_limits<T>::min() - ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1 - : static_cast<UnsignedT>(std::abs(value)); -} +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 = result_type> + static 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 std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, - T>::type -CheckedUnsignedAbs(T value) { - // T is unsigned, so |value| must already be positive. - return static_cast<T>(value); -} +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 = result_type> + static 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); + } +}; -// 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 std::enable_if<std::numeric_limits<T>::is_iec559, T>::type \ - Checked##NAME(T, T, RangeConstraint*) { \ - NOTREACHED(); \ - return static_cast<T>(0); \ +// 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 = result_type> + static bool Do(T x, U y, V* result) { + *result = IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x) + : static_cast<result_type>(y); + return true; } +}; -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) +// 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 = result_type> + static bool Do(T x, U y, V* result) { + *result = IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x) + : static_cast<result_type>(y); + return true; + } +}; -#undef BASE_FLOAT_ARITHMETIC_STUBS +// 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) { \ + 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 + +// Wrap the unary operations to allow SFINAE when instantiating integrals versus +// floating points. These don't perform any overflow checking. Rather, they +// exhibit well-defined overflow semantics and rely on the caller to detect +// if an overflow occured. + +template <typename T, + typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> +constexpr T NegateWrapper(T value) { + using UnsignedT = typename std::make_unsigned<T>::type; + // This will compile to a NEG on Intel, and is normal negation on ARM. + return static_cast<T>(UnsignedT(0) - static_cast<UnsignedT>(value)); +} -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg( - T value, - RangeConstraint*) { - return static_cast<T>(-value); +template < + typename T, + typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr> +constexpr T NegateWrapper(T value) { + return -value; } -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs( - T value, - RangeConstraint*) { - return static_cast<T>(std::abs(value)); +template <typename T, + typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> +constexpr typename std::make_unsigned<T>::type InvertWrapper(T value) { + return ~value; +} + +template <typename T, + typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> +constexpr T AbsWrapper(T value) { + return static_cast<T>(SafeUnsignedAbs(value)); +} + +template < + typename T, + typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr> +constexpr T AbsWrapper(T value) { + return value < 0 ? -value : value; } // Floats carry around their validity state with them, but integers do not. So, @@ -388,10 +518,10 @@ enum NumericRepresentation { template <typename NumericType> struct GetNumericRepresentation { static const NumericRepresentation value = - std::numeric_limits<NumericType>::is_integer + std::is_integral<NumericType>::value ? NUMERIC_INTEGER - : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING - : NUMERIC_UNKNOWN); + : (std::is_floating_point<NumericType>::value ? NUMERIC_FLOATING + : NUMERIC_UNKNOWN); }; template <typename T, NumericRepresentation type = @@ -402,41 +532,48 @@ class CheckedNumericState {}; template <typename T> class CheckedNumericState<T, NUMERIC_INTEGER> { private: + // 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_; - RangeConstraint validity_ : CHAR_BIT; // Actually requires only two bits. + + // 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; - CheckedNumericState() : value_(0), validity_(RANGE_VALID) {} + constexpr CheckedNumericState() : is_valid_(true), value_(0) {} template <typename Src> - CheckedNumericState(Src value, RangeConstraint validity) - : value_(static_cast<T>(value)), - validity_(GetRangeConstraint(validity | - DstRangeRelationToSrcRange<T>(value))) { - static_assert(std::numeric_limits<Src>::is_specialized, - "Argument must be numeric."); + 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> - CheckedNumericState(const CheckedNumericState<Src>& rhs) - : value_(static_cast<T>(rhs.value())), - validity_(GetRangeConstraint( - rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {} + constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs) + : is_valid_(rhs.IsValid()), + value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {} template <typename Src> - explicit CheckedNumericState( - Src value, - typename std::enable_if<std::numeric_limits<Src>::is_specialized, - int>::type = 0) - : value_(static_cast<T>(value)), - validity_(DstRangeRelationToSrcRange<T>(value)) {} - - RangeConstraint validity() const { return validity_; } - T value() const { return value_; } + 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. @@ -445,94 +582,58 @@ 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; - CheckedNumericState() : value_(0.0) {} + constexpr CheckedNumericState() : value_(0.0) {} template <typename Src> - CheckedNumericState( - Src value, - RangeConstraint validity, - typename std::enable_if<std::numeric_limits<Src>::is_integer, int>::type = - 0) { - switch (DstRangeRelationToSrcRange<T>(value)) { - case RANGE_VALID: - value_ = static_cast<T>(value); - break; - - case RANGE_UNDERFLOW: - value_ = -std::numeric_limits<T>::infinity(); - break; - - case RANGE_OVERFLOW: - value_ = std::numeric_limits<T>::infinity(); - break; - - case RANGE_INVALID: - value_ = std::numeric_limits<T>::quiet_NaN(); - break; - - default: - NOTREACHED(); - } - } + constexpr CheckedNumericState(Src value, bool is_valid) + : value_(WellDefinedConversionOrNaN(value, is_valid)) {} template <typename Src> - explicit CheckedNumericState( - Src value, - typename std::enable_if<std::numeric_limits<Src>::is_specialized, - int>::type = 0) - : value_(static_cast<T>(value)) {} + constexpr explicit CheckedNumericState(Src value) + : value_(WellDefinedConversionOrNaN( + value, + IsValueInRangeForNumericType<T>(value))) {} // Copy constructor. template <typename Src> - CheckedNumericState(const CheckedNumericState<Src>& rhs) - : value_(static_cast<T>(rhs.value())) {} - - RangeConstraint validity() const { - return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(), - value_ >= -std::numeric_limits<T>::max()); + 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. + // TODO(jschuh): Fix this if the libraries ever get fixed. + return value_ <= std::numeric_limits<T>::max() && + value_ >= std::numeric_limits<T>::lowest(); } - T value() const { return value_; } -}; - -// For integers less than 128-bit and floats 32-bit or larger, we have the type -// with the larger maximum exponent take precedence. -enum ArithmeticPromotionCategory { LEFT_PROMOTION, RIGHT_PROMOTION }; - -template <typename Lhs, - typename Rhs = Lhs, - ArithmeticPromotionCategory Promotion = - (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) - ? LEFT_PROMOTION - : RIGHT_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; + constexpr T value() const { return value_; } }; -// 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)); +template <template <typename, typename, typename> class M, + typename L, + typename R> +struct MathWrapper { + using math = M<typename UnderlyingType<L>::type, + typename UnderlyingType<R>::type, + void>; + using type = typename math::result_type; }; } // namespace internal |