From 4022f87eb8716155291543efaaf289e51d7cbf43 Mon Sep 17 00:00:00 2001 From: tsepez Date: Mon, 23 Jan 2017 14:36:20 -0800 Subject: Update safe numerics package to get bitwise ops Fix callers conventions to avoid ambiguity. Fix bad bounds check unmasked by change. Directly include headers no longer pulled in by numerics itself. Review-Url: https://codereview.chromium.org/2640143003 --- third_party/base/numerics/safe_conversions.h | 270 ++++++- third_party/base/numerics/safe_conversions_impl.h | 694 ++++++++++++++--- third_party/base/numerics/safe_math.h | 602 ++++++++++----- third_party/base/numerics/safe_math_impl.h | 863 ++++++++++++---------- 4 files changed, 1745 insertions(+), 684 deletions(-) (limited to 'third_party/base/numerics') diff --git a/third_party/base/numerics/safe_conversions.h b/third_party/base/numerics/safe_conversions.h index dd0d1e47dc..dc61d9c9cc 100644 --- a/third_party/base/numerics/safe_conversions.h +++ b/third_party/base/numerics/safe_conversions.h @@ -2,65 +2,271 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#ifndef PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_H_ -#define PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_H_ +#ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_H_ +#define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_H_ + +#include #include +#include +#include -#include "safe_conversions_impl.h" -#include "third_party/base/logging.h" +#include "third_party/base/numerics/safe_conversions_impl.h" namespace pdfium { namespace base { +// The following are helper constexpr template functions and classes for safely +// performing a range of conversions, assignments, and tests: +// +// checked_cast<> - Analogous to static_cast<> for numeric types, except +// that it CHECKs that the specified numeric conversion will not overflow +// or underflow. NaN source will always trigger a CHECK. +// The default CHECK triggers a crash, but the handler can be overriden. +// saturated_cast<> - Analogous to static_cast<> for numeric types, except +// that it returns a saturated result when the specified numeric conversion +// would otherwise overflow or underflow. An NaN source returns 0 by +// default, but can be overridden to return a different result. +// strict_cast<> - Analogous to static_cast<> for numeric types, except that +// it will cause a compile failure if the destination type is not large +// enough to contain any value in the source type. It performs no runtime +// checking and thus introduces no runtime overhead. +// IsValueInRangeForNumericType<>() - A convenience function that returns true +// if the type supplied to the template parameter can represent the value +// passed as an argument to the function. +// IsValueNegative<>() - A convenience function that will accept any arithmetic +// type as an argument and will return whether the value is less than zero. +// Unsigned types always return false. +// SafeUnsignedAbs() - Returns the absolute value of the supplied integer +// parameter as an unsigned result (thus avoiding an overflow if the value +// is the signed, two's complement minimum). +// StrictNumeric<> - A wrapper type that performs assignments and copies via +// the strict_cast<> template, and can perform valid arithmetic comparisons +// across any range of arithmetic types. StrictNumeric is the return type +// for values extracted from a CheckedNumeric class instance. The raw +// arithmetic value is extracted via static_cast to the underlying type. +// MakeStrictNum() - Creates a new StrictNumeric from the underlying type of +// the supplied arithmetic or StrictNumeric type. + // Convenience function that returns true if the supplied value is in range // for the destination type. template -inline bool IsValueInRangeForNumericType(Src value) { - return internal::DstRangeRelationToSrcRange(value) == - internal::RANGE_VALID; +constexpr bool IsValueInRangeForNumericType(Src value) { + return internal::DstRangeRelationToSrcRange(value).IsValid(); } +// Forces a crash, like a CHECK(false). Used for numeric boundary errors. +struct CheckOnFailure { + template + static T HandleFailure() { +#if defined(__GNUC__) || defined(__clang__) + __builtin_trap(); +#else + ((void)(*(volatile char*)0 = 0)); +#endif + return T(); + } +}; + // checked_cast<> is analogous to static_cast<> for numeric types, // except that it CHECKs that the specified numeric conversion will not // overflow or underflow. NaN source will always trigger a CHECK. -template -inline Dst checked_cast(Src value) { - CHECK(IsValueInRangeForNumericType(value)); - return static_cast(value); +template +constexpr Dst checked_cast(Src value) { + // This throws a compile-time error on evaluating the constexpr if it can be + // determined at compile-time as failing, otherwise it will CHECK at runtime. + using SrcType = typename internal::UnderlyingType::type; + return IsValueInRangeForNumericType(value) + ? static_cast(static_cast(value)) + : CheckHandler::template HandleFailure(); +} + +// Default boundaries for integral/float: max/infinity, lowest/-infinity, 0/NaN. +template +struct SaturationDefaultHandler { + static constexpr T NaN() { + return std::numeric_limits::has_quiet_NaN + ? std::numeric_limits::quiet_NaN() + : T(); + } + static constexpr T max() { return std::numeric_limits::max(); } + static constexpr T Overflow() { + return std::numeric_limits::has_infinity + ? std::numeric_limits::infinity() + : std::numeric_limits::max(); + } + static constexpr T lowest() { return std::numeric_limits::lowest(); } + static constexpr T Underflow() { + return std::numeric_limits::has_infinity + ? std::numeric_limits::infinity() * -1 + : std::numeric_limits::lowest(); + } +}; + +namespace internal { + +template class S, typename Src> +constexpr Dst saturated_cast_impl(Src value, RangeCheck constraint) { + // For some reason clang generates much better code when the branch is + // structured exactly this way, rather than a sequence of checks. + return !constraint.IsOverflowFlagSet() + ? (!constraint.IsUnderflowFlagSet() ? static_cast(value) + : S::Underflow()) + // Skip this check for integral Src, which cannot be NaN. + : (std::is_integral::value || !constraint.IsUnderflowFlagSet() + ? S::Overflow() + : S::NaN()); } // saturated_cast<> is analogous to static_cast<> for numeric types, except -// that the specified numeric conversion will saturate rather than overflow or -// underflow. NaN assignment to an integral will trigger a CHECK condition. +// that the specified numeric conversion will saturate by default rather than +// overflow or underflow, and NaN assignment to an integral will return 0. +// All boundary condition behaviors can be overriden with a custom handler. +template + class SaturationHandler = SaturationDefaultHandler, + typename Src> +constexpr Dst saturated_cast(Src value) { + using SrcType = typename UnderlyingType::type; + return saturated_cast_impl( + value, + DstRangeRelationToSrcRange(value)); +} + +// strict_cast<> is analogous to static_cast<> for numeric types, except that +// it will cause a compile failure if the destination type is not large enough +// to contain any value in the source type. It performs no runtime checking. template -inline Dst saturated_cast(Src value) { - // Optimization for floating point values, which already saturate. - if (std::numeric_limits::is_iec559) - return static_cast(value); +constexpr Dst strict_cast(Src value) { + using SrcType = typename UnderlyingType::type; + static_assert(UnderlyingType::is_numeric, "Argument must be numeric."); + static_assert(std::is_arithmetic::value, "Result must be numeric."); - switch (internal::DstRangeRelationToSrcRange(value)) { - case internal::RANGE_VALID: - return static_cast(value); + // If you got here from a compiler error, it's because you tried to assign + // from a source type to a destination type that has insufficient range. + // The solution may be to change the destination type you're assigning to, + // and use one large enough to represent the source. + // Alternatively, you may be better served with the checked_cast<> or + // saturated_cast<> template functions for your particular use case. + static_assert(StaticDstRangeRelationToSrcRange::value == + NUMERIC_RANGE_CONTAINED, + "The source type is out of range for the destination type. " + "Please see strict_cast<> comments for more information."); - case internal::RANGE_UNDERFLOW: - return std::numeric_limits::min(); + return static_cast(static_cast(value)); +} - case internal::RANGE_OVERFLOW: - return std::numeric_limits::max(); +// Some wrappers to statically check that a type is in range. +template +struct IsNumericRangeContained { + static const bool value = false; +}; - // Should fail only on attempting to assign NaN to a saturated integer. - case internal::RANGE_INVALID: - CHECK(false); - return std::numeric_limits::max(); +template +struct IsNumericRangeContained< + Dst, + Src, + typename std::enable_if::value && + ArithmeticOrUnderlyingEnum::value>::type> { + static const bool value = StaticDstRangeRelationToSrcRange::value == + NUMERIC_RANGE_CONTAINED; +}; + +// StrictNumeric implements compile time range checking between numeric types by +// wrapping assignment operations in a strict_cast. This class is intended to be +// used for function arguments and return types, to ensure the destination type +// can always contain the source type. This is essentially the same as enforcing +// -Wconversion in gcc and C4302 warnings on MSVC, but it can be applied +// incrementally at API boundaries, making it easier to convert code so that it +// compiles cleanly with truncation warnings enabled. +// This template should introduce no runtime overhead, but it also provides no +// runtime checking of any of the associated mathematical operations. Use +// CheckedNumeric for runtime range checks of the actual value being assigned. +template +class StrictNumeric { + public: + using type = T; + + constexpr StrictNumeric() : value_(0) {} + + // Copy constructor. + template + constexpr StrictNumeric(const StrictNumeric& rhs) + : value_(strict_cast(rhs.value_)) {} + + // This is not an explicit constructor because we implicitly upgrade regular + // numerics to StrictNumerics to make them easier to use. + template + constexpr StrictNumeric(Src value) // NOLINT(runtime/explicit) + : value_(strict_cast(value)) {} + + // If you got here from a compiler error, it's because you tried to assign + // from a source type to a destination type that has insufficient range. + // The solution may be to change the destination type you're assigning to, + // and use one large enough to represent the source. + // If you're assigning from a CheckedNumeric<> class, you may be able to use + // the AssignIfValid() member function, specify a narrower destination type to + // the member value functions (e.g. val.template ValueOrDie()), use one + // of the value helper functions (e.g. ValueOrDieForType(val)). + // If you've encountered an _ambiguous overload_ you can use a static_cast<> + // to explicitly cast the result to the destination type. + // If none of that works, you may be better served with the checked_cast<> or + // saturated_cast<> template functions for your particular use case. + template ::value>::type* = nullptr> + constexpr operator Dst() const { + return static_cast::type>(value_); } - NOTREACHED(); - return static_cast(value); + private: + const T value_; +}; + +// Convience wrapper returns a StrictNumeric from the provided arithmetic type. +template +constexpr StrictNumeric::type> MakeStrictNum( + const T value) { + return value; +} + +// Overload the ostream output operator to make logging work nicely. +template +std::ostream& operator<<(std::ostream& os, const StrictNumeric& value) { + os << static_cast(value); + return os; } +#define STRICT_COMPARISON_OP(NAME, OP) \ + template ::value>::type* = nullptr> \ + constexpr bool operator OP(const L lhs, const R rhs) { \ + return SafeCompare::type, \ + typename UnderlyingType::type>(lhs, rhs); \ + } + +STRICT_COMPARISON_OP(IsLess, <); +STRICT_COMPARISON_OP(IsLessOrEqual, <=); +STRICT_COMPARISON_OP(IsGreater, >); +STRICT_COMPARISON_OP(IsGreaterOrEqual, >=); +STRICT_COMPARISON_OP(IsEqual, ==); +STRICT_COMPARISON_OP(IsNotEqual, !=); + +#undef STRICT_COMPARISON_OP +}; + +using internal::strict_cast; +using internal::saturated_cast; +using internal::SafeUnsignedAbs; +using internal::StrictNumeric; +using internal::MakeStrictNum; +using internal::IsValueNegative; + +// Explicitly make a shorter size_t alias for convenience. +using SizeT = StrictNumeric; + } // namespace base } // namespace pdfium -#endif // PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_H_ - +#endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_H_ diff --git a/third_party/base/numerics/safe_conversions_impl.h b/third_party/base/numerics/safe_conversions_impl.h index e1c4c3b756..2a7ce146e3 100644 --- a/third_party/base/numerics/safe_conversions_impl.h +++ b/third_party/base/numerics/safe_conversions_impl.h @@ -2,29 +2,81 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#ifndef PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_IMPL_H_ -#define PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_IMPL_H_ +#ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ +#define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ -#include -#include +#include -#include "third_party/base/macros.h" +#include +#include namespace pdfium { namespace base { namespace internal { // The std library doesn't provide a binary max_exponent for integers, however -// we can compute one by adding one to the number of non-sign bits. This allows -// for accurate range comparisons between floating point and integer types. +// we can compute an analog using std::numeric_limits<>::digits. template struct MaxExponent { - static const int value = std::numeric_limits::is_iec559 + static const int value = std::is_floating_point::value ? std::numeric_limits::max_exponent - : (sizeof(NumericType) * 8 + 1 - - std::numeric_limits::is_signed); + : 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) ^ -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) ? 0 - static_cast(value) + : static_cast(value); +} + enum IntegerRepresentation { INTEGER_REPRESENTATION_UNSIGNED, INTEGER_REPRESENTATION_SIGNED @@ -32,7 +84,7 @@ enum IntegerRepresentation { // 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::min() >= numeric_limits::min() are true. +// 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 { @@ -43,16 +95,14 @@ enum NumericRangeRepresentation { // Helper templates to statically determine if our destination type can contain // maximum and minimum values represented by the source type. -template < - typename Dst, - typename Src, - IntegerRepresentation DstSign = std::numeric_limits::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - IntegerRepresentation SrcSign = - std::numeric_limits::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED > +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 @@ -87,132 +137,598 @@ struct StaticDstRangeRelationToSrcRange= RANGE_VALID && - integer_range_constraint <= RANGE_INVALID); - return static_cast(integer_range_constraint); -} +// 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; -// This function creates a RangeConstraint from an upper and lower bound -// check by taking advantage of the fact that only NaN can be out of range in -// both directions at once. -inline RangeConstraint GetRangeConstraint(bool is_in_upper_bound, - bool is_in_lower_bound) { - return GetRangeConstraint((is_in_upper_bound ? 0 : RANGE_OVERFLOW) | - (is_in_lower_bound ? 0 : RANGE_UNDERFLOW)); -} + // 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> -template < - typename Dst, - typename Src, - IntegerRepresentation DstSign = std::numeric_limits::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - IntegerRepresentation SrcSign = std::numeric_limits::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - NumericRangeRepresentation DstRange = - StaticDstRangeRelationToSrcRange::value > + // 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, ""); + return static_cast( + ConditionalNegate(SafeUnsignedAbs(value) & ~((T(1) << kShift) - T(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. -// Dst range is statically determined to contain Src: Nothing to check. +// Same sign narrowing: The range is contained for normal limits. template class Bounds, IntegerRepresentation DstSign, IntegerRepresentation SrcSign> struct DstRangeRelationToSrcRangeImpl { - static RangeConstraint Check(Src value) { return RANGE_VALID; } + 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. -template +// exceeded for standard limits. +template class Bounds> struct DstRangeRelationToSrcRangeImpl { - static RangeConstraint Check(Src value) { - return std::numeric_limits::is_iec559 - ? GetRangeConstraint(value <= std::numeric_limits::max(), - value >= -std::numeric_limits::max()) - : GetRangeConstraint(value <= std::numeric_limits::max(), - value >= std::numeric_limits::min()); + static constexpr RangeCheck Check(Src value) { + using DstLimits = NarrowingRange; + return RangeCheck(value >= DstLimits::lowest(), value <= DstLimits::max()); } }; -// Unsigned to unsigned narrowing: Only the upper boundary can be exceeded. -template +// Unsigned to unsigned narrowing: Only the upper bound can be exceeded for +// standard limits. +template class Bounds> struct DstRangeRelationToSrcRangeImpl { - static RangeConstraint Check(Src value) { - return GetRangeConstraint(value <= std::numeric_limits::max(), true); + static constexpr RangeCheck Check(Src value) { + using DstLimits = NarrowingRange; + return RangeCheck( + DstLimits::lowest() == Dst(0) || value >= DstLimits::lowest(), + value <= DstLimits::max()); } }; -// Unsigned to signed: The upper boundary may be exceeded. -template +// Unsigned to signed: Only the upper bound can be exceeded for standard limits. +template class Bounds> struct DstRangeRelationToSrcRangeImpl { - static RangeConstraint Check(Src value) { - return sizeof(Dst) > sizeof(Src) - ? RANGE_VALID - : GetRangeConstraint( - value <= static_cast(std::numeric_limits::max()), - true); + 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. -template +// and any negative value exceeds the lower boundary for standard limits. +template class Bounds> struct DstRangeRelationToSrcRangeImpl { - static RangeConstraint Check(Src value) { - return (MaxExponent::value >= MaxExponent::value) - ? GetRangeConstraint(true, value >= static_cast(0)) - : GetRangeConstraint( - value <= static_cast(std::numeric_limits::max()), - value >= static_cast(0)); + static constexpr RangeCheck Check(Src value) { + using SrcLimits = std::numeric_limits; + using DstLimits = NarrowingRange; + using Promotion = decltype(Src() + Dst()); + return RangeCheck( + value >= Src(0) && (DstLimits::lowest() == 0 || + static_cast(value) >= DstLimits::lowest()), + static_cast(SrcLimits::max()) <= + static_cast(DstLimits::max()) || + static_cast(value) <= + static_cast(DstLimits::max())); } }; -template -inline RangeConstraint DstRangeRelationToSrcRange(Src value) { - COMPILE_ASSERT(std::numeric_limits::is_specialized, - argument_must_be_numeric); - COMPILE_ASSERT(std::numeric_limits::is_specialized, - result_must_be_numeric); - return DstRangeRelationToSrcRangeImpl::Check(value); +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; +}; + +// This hacks around libstdc++ 4.6 missing stuff in type_traits. +#if defined(__GLIBCXX__) +#define PRIV_GLIBCXX_4_7_0 20120322 +#define PRIV_GLIBCXX_4_5_4 20120702 +#define PRIV_GLIBCXX_4_6_4 20121127 +#if (__GLIBCXX__ < PRIV_GLIBCXX_4_7_0 || __GLIBCXX__ == PRIV_GLIBCXX_4_5_4 || \ + __GLIBCXX__ == PRIV_GLIBCXX_4_6_4) +#define PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX +#undef PRIV_GLIBCXX_4_7_0 +#undef PRIV_GLIBCXX_4_5_4 +#undef PRIV_GLIBCXX_4_6_4 +#endif +#endif + +// Extracts the underlying type from an enum. +template ::value> +struct ArithmeticOrUnderlyingEnum; + +template +struct ArithmeticOrUnderlyingEnum { +#if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) + using type = __underlying_type(T); +#else + using type = typename std::underlying_type::type; +#endif + static const bool value = std::is_arithmetic::value; +}; + +#if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) +#undef PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX +#endif + +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 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_strict = false; +}; + +template +struct UnderlyingType> { + using type = T; + static const bool is_numeric = true; + static const bool is_checked = 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_strict = true; +}; + +template +struct IsCheckedOp { + static const bool value = + UnderlyingType::is_numeric && UnderlyingType::is_numeric && + (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); +}; + +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