// Copyright 2014 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ #define BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ #include #include #include #if defined(__GNUC__) || defined(__clang__) #define BASE_NUMERICS_LIKELY(x) __builtin_expect(!!(x), 1) #define BASE_NUMERICS_UNLIKELY(x) __builtin_expect(!!(x), 0) #else #define BASE_NUMERICS_LIKELY(x) (x) #define BASE_NUMERICS_UNLIKELY(x) (x) #endif namespace base { namespace internal { // The std library doesn't provide a binary max_exponent for integers, however // we can compute an analog using std::numeric_limits<>::digits. template struct MaxExponent { static const int value = std::is_floating_point::value ? std::numeric_limits::max_exponent : std::numeric_limits::digits + 1; }; // The number of bits (including the sign) in an integer. Eliminates sizeof // hacks. template struct IntegerBitsPlusSign { static const int value = std::numeric_limits::digits + std::is_signed::value; }; // Helper templates for integer manipulations. template struct PositionOfSignBit { static const size_t value = IntegerBitsPlusSign::value - 1; }; // Determines if a numeric value is negative without throwing compiler // warnings on: unsigned(value) < 0. template ::value>::type* = nullptr> constexpr bool IsValueNegative(T value) { static_assert(std::is_arithmetic::value, "Argument must be numeric."); return value < 0; } template ::value>::type* = nullptr> constexpr bool IsValueNegative(T) { static_assert(std::is_arithmetic::value, "Argument must be numeric."); return false; } // This performs a fast negation, returning a signed value. It works on unsigned // arguments, but probably doesn't do what you want for any unsigned value // larger than max / 2 + 1 (i.e. signed min cast to unsigned). template constexpr typename std::make_signed::type ConditionalNegate( T x, bool is_negative) { static_assert(std::is_integral::value, "Type must be integral"); using SignedT = typename std::make_signed::type; using UnsignedT = typename std::make_unsigned::type; return static_cast((static_cast(x) ^ static_cast(-SignedT(is_negative))) + is_negative); } // This performs a safe, absolute value via unsigned overflow. template constexpr typename std::make_unsigned::type SafeUnsignedAbs(T value) { static_assert(std::is_integral::value, "Type must be integral"); using UnsignedT = typename std::make_unsigned::type; return IsValueNegative(value) ? static_cast(0u - static_cast(value)) : static_cast(value); } // TODO(jschuh): Switch to std::is_constant_evaluated() once C++20 is supported. // Alternately, the usage could be restructured for "consteval if" in C++23. #define IsConstantEvaluated() (__builtin_is_constant_evaluated()) // TODO(jschuh): Debug builds don't reliably propagate constants, so we restrict // some accelerated runtime paths to release builds until this can be forced // with consteval support in C++20 or C++23. #if defined(NDEBUG) constexpr bool kEnableAsmCode = true; #else constexpr bool kEnableAsmCode = false; #endif // Forces a crash, like a CHECK(false). Used for numeric boundary errors. // Also used in a constexpr template to trigger a compilation failure on // an error condition. struct CheckOnFailure { template static T HandleFailure() { #if defined(_MSC_VER) __debugbreak(); #elif defined(__GNUC__) || defined(__clang__) __builtin_trap(); #else ((void)(*(volatile char*)0 = 0)); #endif return T(); } }; enum IntegerRepresentation { INTEGER_REPRESENTATION_UNSIGNED, INTEGER_REPRESENTATION_SIGNED }; // A range for a given nunmeric Src type is contained for a given numeric Dst // type if both numeric_limits::max() <= numeric_limits::max() and // numeric_limits::lowest() >= numeric_limits::lowest() are true. // We implement this as template specializations rather than simple static // comparisons to ensure type correctness in our comparisons. enum NumericRangeRepresentation { NUMERIC_RANGE_NOT_CONTAINED, NUMERIC_RANGE_CONTAINED }; // Helper templates to statically determine if our destination type can contain // maximum and minimum values represented by the source type. template ::value ? INTEGER_REPRESENTATION_SIGNED : INTEGER_REPRESENTATION_UNSIGNED, IntegerRepresentation SrcSign = std::is_signed::value ? INTEGER_REPRESENTATION_SIGNED : INTEGER_REPRESENTATION_UNSIGNED> struct StaticDstRangeRelationToSrcRange; // Same sign: Dst is guaranteed to contain Src only if its range is equal or // larger. template struct StaticDstRangeRelationToSrcRange { static const NumericRangeRepresentation value = MaxExponent::value >= MaxExponent::value ? NUMERIC_RANGE_CONTAINED : NUMERIC_RANGE_NOT_CONTAINED; }; // Unsigned to signed: Dst is guaranteed to contain source only if its range is // larger. template struct StaticDstRangeRelationToSrcRange { static const NumericRangeRepresentation value = MaxExponent::value > MaxExponent::value ? NUMERIC_RANGE_CONTAINED : NUMERIC_RANGE_NOT_CONTAINED; }; // Signed to unsigned: Dst cannot be statically determined to contain Src. template struct StaticDstRangeRelationToSrcRange { static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED; }; // This class wraps the range constraints as separate booleans so the compiler // can identify constants and eliminate unused code paths. class RangeCheck { public: constexpr RangeCheck(bool is_in_lower_bound, bool is_in_upper_bound) : is_underflow_(!is_in_lower_bound), is_overflow_(!is_in_upper_bound) {} constexpr RangeCheck() : is_underflow_(false), is_overflow_(false) {} constexpr bool IsValid() const { return !is_overflow_ && !is_underflow_; } constexpr bool IsInvalid() const { return is_overflow_ && is_underflow_; } constexpr bool IsOverflow() const { return is_overflow_ && !is_underflow_; } constexpr bool IsUnderflow() const { return !is_overflow_ && is_underflow_; } constexpr bool IsOverflowFlagSet() const { return is_overflow_; } constexpr bool IsUnderflowFlagSet() const { return is_underflow_; } constexpr bool operator==(const RangeCheck rhs) const { return is_underflow_ == rhs.is_underflow_ && is_overflow_ == rhs.is_overflow_; } constexpr bool operator!=(const RangeCheck rhs) const { return !(*this == rhs); } private: // Do not change the order of these member variables. The integral conversion // optimization depends on this exact order. const bool is_underflow_; const bool is_overflow_; }; // The following helper template addresses a corner case in range checks for // conversion from a floating-point type to an integral type of smaller range // but larger precision (e.g. float -> unsigned). The problem is as follows: // 1. Integral maximum is always one less than a power of two, so it must be // truncated to fit the mantissa of the floating point. The direction of // rounding is implementation defined, but by default it's always IEEE // floats, which round to nearest and thus result in a value of larger // magnitude than the integral value. // Example: float f = UINT_MAX; // f is 4294967296f but UINT_MAX // // is 4294967295u. // 2. If the floating point value is equal to the promoted integral maximum // value, a range check will erroneously pass. // Example: (4294967296f <= 4294967295u) // This is true due to a precision // // loss in rounding up to float. // 3. When the floating point value is then converted to an integral, the // resulting value is out of range for the target integral type and // thus is implementation defined. // Example: unsigned u = (float)INT_MAX; // u will typically overflow to 0. // To fix this bug we manually truncate the maximum value when the destination // type is an integral of larger precision than the source floating-point type, // such that the resulting maximum is represented exactly as a floating point. template class Bounds> struct NarrowingRange { using SrcLimits = std::numeric_limits; using DstLimits = typename std::numeric_limits; // Computes the mask required to make an accurate comparison between types. static const int kShift = (MaxExponent::value > MaxExponent::value && SrcLimits::digits < DstLimits::digits) ? (DstLimits::digits - SrcLimits::digits) : 0; template < typename T, typename std::enable_if::value>::type* = nullptr> // Masks out the integer bits that are beyond the precision of the // intermediate type used for comparison. static constexpr T Adjust(T value) { static_assert(std::is_same::value, ""); static_assert(kShift < DstLimits::digits, ""); using UnsignedDst = typename std::make_unsigned_t; return static_cast(ConditionalNegate( SafeUnsignedAbs(value) & ~((UnsignedDst{1} << kShift) - UnsignedDst{1}), IsValueNegative(value))); } template ::value>::type* = nullptr> static constexpr T Adjust(T value) { static_assert(std::is_same::value, ""); static_assert(kShift == 0, ""); return value; } static constexpr Dst max() { return Adjust(Bounds::max()); } static constexpr Dst lowest() { return Adjust(Bounds::lowest()); } }; template class Bounds, IntegerRepresentation DstSign = std::is_signed::value ? INTEGER_REPRESENTATION_SIGNED : INTEGER_REPRESENTATION_UNSIGNED, IntegerRepresentation SrcSign = std::is_signed::value ? INTEGER_REPRESENTATION_SIGNED : INTEGER_REPRESENTATION_UNSIGNED, NumericRangeRepresentation DstRange = StaticDstRangeRelationToSrcRange::value> struct DstRangeRelationToSrcRangeImpl; // The following templates are for ranges that must be verified at runtime. We // split it into checks based on signedness to avoid confusing casts and // compiler warnings on signed an unsigned comparisons. // Same sign narrowing: The range is contained for normal limits. template class Bounds, IntegerRepresentation DstSign, IntegerRepresentation SrcSign> struct DstRangeRelationToSrcRangeImpl { static constexpr RangeCheck Check(Src value) { using SrcLimits = std::numeric_limits; using DstLimits = NarrowingRange; return RangeCheck( static_cast(SrcLimits::lowest()) >= DstLimits::lowest() || static_cast(value) >= DstLimits::lowest(), static_cast(SrcLimits::max()) <= DstLimits::max() || static_cast(value) <= DstLimits::max()); } }; // Signed to signed narrowing: Both the upper and lower boundaries may be // exceeded for standard limits. template class Bounds> struct DstRangeRelationToSrcRangeImpl { static constexpr RangeCheck Check(Src value) { using DstLimits = NarrowingRange; return RangeCheck(value >= DstLimits::lowest(), value <= DstLimits::max()); } }; // Unsigned to unsigned narrowing: Only the upper bound can be exceeded for // standard limits. template class Bounds> struct DstRangeRelationToSrcRangeImpl { static constexpr RangeCheck Check(Src value) { using DstLimits = NarrowingRange; return RangeCheck( DstLimits::lowest() == Dst(0) || value >= DstLimits::lowest(), value <= DstLimits::max()); } }; // Unsigned to signed: Only the upper bound can be exceeded for standard limits. template class Bounds> struct DstRangeRelationToSrcRangeImpl { static constexpr RangeCheck Check(Src value) { using DstLimits = NarrowingRange; using Promotion = decltype(Src() + Dst()); return RangeCheck(DstLimits::lowest() <= Dst(0) || static_cast(value) >= static_cast(DstLimits::lowest()), static_cast(value) <= static_cast(DstLimits::max())); } }; // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst, // and any negative value exceeds the lower boundary for standard limits. template class Bounds> struct DstRangeRelationToSrcRangeImpl { static constexpr RangeCheck Check(Src value) { using SrcLimits = std::numeric_limits; using DstLimits = NarrowingRange; using Promotion = decltype(Src() + Dst()); bool ge_zero = false; // Converting floating-point to integer will discard fractional part, so // values in (-1.0, -0.0) will truncate to 0 and fit in Dst. if (std::is_floating_point::value) { ge_zero = value > Src(-1); } else { ge_zero = value >= Src(0); } return RangeCheck( ge_zero && (DstLimits::lowest() == 0 || static_cast(value) >= DstLimits::lowest()), static_cast(SrcLimits::max()) <= static_cast(DstLimits::max()) || static_cast(value) <= static_cast(DstLimits::max())); } }; // Simple wrapper for statically checking if a type's range is contained. template struct IsTypeInRangeForNumericType { static const bool value = StaticDstRangeRelationToSrcRange::value == NUMERIC_RANGE_CONTAINED; }; template class Bounds = std::numeric_limits, typename Src> constexpr RangeCheck DstRangeRelationToSrcRange(Src value) { static_assert(std::is_arithmetic::value, "Argument must be numeric."); static_assert(std::is_arithmetic::value, "Result must be numeric."); static_assert(Bounds::lowest() < Bounds::max(), ""); return DstRangeRelationToSrcRangeImpl::Check(value); } // Integer promotion templates used by the portable checked integer arithmetic. template struct IntegerForDigitsAndSign; #define INTEGER_FOR_DIGITS_AND_SIGN(I) \ template <> \ struct IntegerForDigitsAndSign::value, \ std::is_signed::value> { \ using type = I; \ } INTEGER_FOR_DIGITS_AND_SIGN(int8_t); INTEGER_FOR_DIGITS_AND_SIGN(uint8_t); INTEGER_FOR_DIGITS_AND_SIGN(int16_t); INTEGER_FOR_DIGITS_AND_SIGN(uint16_t); INTEGER_FOR_DIGITS_AND_SIGN(int32_t); INTEGER_FOR_DIGITS_AND_SIGN(uint32_t); INTEGER_FOR_DIGITS_AND_SIGN(int64_t); INTEGER_FOR_DIGITS_AND_SIGN(uint64_t); #undef INTEGER_FOR_DIGITS_AND_SIGN // 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). static_assert(IntegerBitsPlusSign::value == 64, "Max integer size not supported for this toolchain."); template ::value> struct TwiceWiderInteger { using type = typename IntegerForDigitsAndSign::value * 2, IsSigned>::type; }; enum ArithmeticPromotionCategory { LEFT_PROMOTION, // Use the type of the left-hand argument. RIGHT_PROMOTION // Use the type of the right-hand argument. }; // Determines the type that can represent the largest positive value. template ::value > MaxExponent::value) ? LEFT_PROMOTION : RIGHT_PROMOTION> struct MaxExponentPromotion; template struct MaxExponentPromotion { using type = Lhs; }; template struct MaxExponentPromotion { using type = Rhs; }; // Determines the type that can represent the lowest arithmetic value. template ::value ? (std::is_signed::value ? (MaxExponent::value > MaxExponent::value ? LEFT_PROMOTION : RIGHT_PROMOTION) : LEFT_PROMOTION) : (std::is_signed::value ? RIGHT_PROMOTION : (MaxExponent::value < MaxExponent::value ? LEFT_PROMOTION : RIGHT_PROMOTION))> struct LowestValuePromotion; template struct LowestValuePromotion { using type = Lhs; }; template struct LowestValuePromotion { using type = Rhs; }; // Determines the type that is best able to represent an arithmetic result. template < typename Lhs, typename Rhs = Lhs, bool is_intmax_type = std::is_integral::type>::value&& IntegerBitsPlusSign::type>:: value == IntegerBitsPlusSign::value, bool is_max_exponent = StaticDstRangeRelationToSrcRange< typename MaxExponentPromotion::type, Lhs>::value == NUMERIC_RANGE_CONTAINED&& StaticDstRangeRelationToSrcRange< typename MaxExponentPromotion::type, Rhs>::value == NUMERIC_RANGE_CONTAINED> struct BigEnoughPromotion; // The side with the max exponent is big enough. template struct BigEnoughPromotion { using type = typename MaxExponentPromotion::type; static const bool is_contained = true; }; // We can use a twice wider type to fit. template struct BigEnoughPromotion { using type = typename TwiceWiderInteger::type, std::is_signed::value || std::is_signed::value>::type; static const bool is_contained = true; }; // No type is large enough. template struct BigEnoughPromotion { using type = typename MaxExponentPromotion::type; static const bool is_contained = false; }; // 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 struct IsIntegerArithmeticSafe { static const bool value = !std::is_floating_point::value && !std::is_floating_point::value && !std::is_floating_point::value && std::is_signed::value >= std::is_signed::value && IntegerBitsPlusSign::value >= (2 * IntegerBitsPlusSign::value) && std::is_signed::value >= std::is_signed::value && IntegerBitsPlusSign::value >= (2 * IntegerBitsPlusSign::value); }; // Promotes to a type that can represent any possible result of a binary // arithmetic operation with the source types. template ::value || std::is_signed::value, intmax_t, uintmax_t>::type, typename MaxExponentPromotion::type>::value> struct FastIntegerArithmeticPromotion; template struct FastIntegerArithmeticPromotion { using type = typename TwiceWiderInteger::type, std::is_signed::value || std::is_signed::value>::type; static_assert(IsIntegerArithmeticSafe::value, ""); static const bool is_contained = true; }; template struct FastIntegerArithmeticPromotion { using type = typename BigEnoughPromotion::type; static const bool is_contained = false; }; // Extracts the underlying type from an enum. template ::value> struct ArithmeticOrUnderlyingEnum; template struct ArithmeticOrUnderlyingEnum { using type = typename std::underlying_type::type; static const bool value = std::is_arithmetic::value; }; template struct ArithmeticOrUnderlyingEnum { using type = T; static const bool value = std::is_arithmetic::value; }; // The following are helper templates used in the CheckedNumeric class. template class CheckedNumeric; template class ClampedNumeric; template class StrictNumeric; // Used to treat CheckedNumeric and arithmetic underlying types the same. template struct UnderlyingType { using type = typename ArithmeticOrUnderlyingEnum::type; static const bool is_numeric = std::is_arithmetic::value; static const bool is_checked = false; static const bool is_clamped = false; static const bool is_strict = false; }; template struct UnderlyingType> { using type = T; static const bool is_numeric = true; static const bool is_checked = true; static const bool is_clamped = false; static const bool is_strict = false; }; template struct UnderlyingType> { using type = T; static const bool is_numeric = true; static const bool is_checked = false; static const bool is_clamped = true; static const bool is_strict = false; }; template struct UnderlyingType> { using type = T; static const bool is_numeric = true; static const bool is_checked = false; static const bool is_clamped = false; static const bool is_strict = true; }; template struct IsCheckedOp { static const bool value = UnderlyingType::is_numeric && UnderlyingType::is_numeric && (UnderlyingType::is_checked || UnderlyingType::is_checked); }; template struct IsClampedOp { static const bool value = UnderlyingType::is_numeric && UnderlyingType::is_numeric && (UnderlyingType::is_clamped || UnderlyingType::is_clamped) && !(UnderlyingType::is_checked || UnderlyingType::is_checked); }; template struct IsStrictOp { static const bool value = UnderlyingType::is_numeric && UnderlyingType::is_numeric && (UnderlyingType::is_strict || UnderlyingType::is_strict) && !(UnderlyingType::is_checked || UnderlyingType::is_checked) && !(UnderlyingType::is_clamped || UnderlyingType::is_clamped); }; // as_signed<> returns the supplied integral value (or integral castable // Numeric template) cast as a signed integral of equivalent precision. // I.e. it's mostly an alias for: static_cast::type>(t) template constexpr typename std::make_signed< typename base::internal::UnderlyingType::type>::type as_signed(const Src value) { static_assert(std::is_integral::value, "Argument must be a signed or unsigned integer type."); return static_cast(value); } // as_unsigned<> returns the supplied integral value (or integral castable // Numeric template) cast as an unsigned integral of equivalent precision. // I.e. it's mostly an alias for: static_cast::type>(t) template constexpr typename std::make_unsigned< typename base::internal::UnderlyingType::type>::type as_unsigned(const Src value) { static_assert(std::is_integral::value, "Argument must be a signed or unsigned integer type."); return static_cast(value); } template constexpr bool IsLessImpl(const L lhs, const R rhs, const RangeCheck l_range, const RangeCheck r_range) { return l_range.IsUnderflow() || r_range.IsOverflow() || (l_range == r_range && static_cast(lhs) < static_cast(rhs)); } template struct IsLess { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return IsLessImpl(lhs, rhs, DstRangeRelationToSrcRange(lhs), DstRangeRelationToSrcRange(rhs)); } }; template constexpr bool IsLessOrEqualImpl(const L lhs, const R rhs, const RangeCheck l_range, const RangeCheck r_range) { return l_range.IsUnderflow() || r_range.IsOverflow() || (l_range == r_range && static_cast(lhs) <= static_cast(rhs)); } template struct IsLessOrEqual { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return IsLessOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange(lhs), DstRangeRelationToSrcRange(rhs)); } }; template constexpr bool IsGreaterImpl(const L lhs, const R rhs, const RangeCheck l_range, const RangeCheck r_range) { return l_range.IsOverflow() || r_range.IsUnderflow() || (l_range == r_range && static_cast(lhs) > static_cast(rhs)); } template struct IsGreater { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return IsGreaterImpl(lhs, rhs, DstRangeRelationToSrcRange(lhs), DstRangeRelationToSrcRange(rhs)); } }; template constexpr bool IsGreaterOrEqualImpl(const L lhs, const R rhs, const RangeCheck l_range, const RangeCheck r_range) { return l_range.IsOverflow() || r_range.IsUnderflow() || (l_range == r_range && static_cast(lhs) >= static_cast(rhs)); } template struct IsGreaterOrEqual { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return IsGreaterOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange(lhs), DstRangeRelationToSrcRange(rhs)); } }; template struct IsEqual { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return DstRangeRelationToSrcRange(lhs) == DstRangeRelationToSrcRange(rhs) && static_cast(lhs) == static_cast(rhs); } }; template struct IsNotEqual { static_assert(std::is_arithmetic::value && std::is_arithmetic::value, "Types must be numeric."); static constexpr bool Test(const L lhs, const R rhs) { return DstRangeRelationToSrcRange(lhs) != DstRangeRelationToSrcRange(rhs) || static_cast(lhs) != static_cast(rhs); } }; // These perform the actual math operations on the CheckedNumerics. // Binary arithmetic operations. template