diff options
Diffstat (limited to 'third_party')
| -rw-r--r-- | third_party/agg23/agg_rasterizer_scanline_aa.cpp | 8 | ||||
| -rw-r--r-- | third_party/base/numerics/safe_conversions.h | 270 | ||||
| -rw-r--r-- | third_party/base/numerics/safe_conversions_impl.h | 694 | ||||
| -rw-r--r-- | third_party/base/numerics/safe_math.h | 602 | ||||
| -rw-r--r-- | third_party/base/numerics/safe_math_impl.h | 863 |
5 files changed, 1749 insertions, 688 deletions
diff --git a/third_party/agg23/agg_rasterizer_scanline_aa.cpp b/third_party/agg23/agg_rasterizer_scanline_aa.cpp index c6b3f013a0..af6dd58fe3 100644 --- a/third_party/agg23/agg_rasterizer_scanline_aa.cpp +++ b/third_party/agg23/agg_rasterizer_scanline_aa.cpp @@ -283,8 +283,8 @@ void outline_aa::render_line(int x1, int y1, int x2, int y2) incr = -1; dy = -dy; } - delta = safeP.ValueOrDie() / dy; - mod = safeP.ValueOrDie() % dy; + delta = (safeP / dy).ValueOrDie(); + mod = (safeP % dy).ValueOrDie(); if(mod < 0) { delta--; mod += dy; @@ -298,8 +298,8 @@ void outline_aa::render_line(int x1, int y1, int x2, int y2) safeP *= dx; if (!safeP.IsValid()) return; - lift = safeP.ValueOrDie() / dy; - rem = safeP.ValueOrDie() % dy; + lift = (safeP / dy).ValueOrDie(); + rem = (safeP % dy).ValueOrDie(); if (rem < 0) { lift--; rem += dy; 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 <stddef.h> #include <limits> +#include <ostream> +#include <type_traits> -#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 <typename Dst, typename Src> -inline bool IsValueInRangeForNumericType(Src value) { - return internal::DstRangeRelationToSrcRange<Dst>(value) == - internal::RANGE_VALID; +constexpr bool IsValueInRangeForNumericType(Src value) { + return internal::DstRangeRelationToSrcRange<Dst>(value).IsValid(); } +// Forces a crash, like a CHECK(false). Used for numeric boundary errors. +struct CheckOnFailure { + template <typename T> + 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 <typename Dst, typename Src> -inline Dst checked_cast(Src value) { - CHECK(IsValueInRangeForNumericType<Dst>(value)); - return static_cast<Dst>(value); +template <typename Dst, class CheckHandler = CheckOnFailure, typename Src> +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<Src>::type; + return IsValueInRangeForNumericType<Dst, SrcType>(value) + ? static_cast<Dst>(static_cast<SrcType>(value)) + : CheckHandler::template HandleFailure<Dst>(); +} + +// Default boundaries for integral/float: max/infinity, lowest/-infinity, 0/NaN. +template <typename T> +struct SaturationDefaultHandler { + static constexpr T NaN() { + return std::numeric_limits<T>::has_quiet_NaN + ? std::numeric_limits<T>::quiet_NaN() + : T(); + } + static constexpr T max() { return std::numeric_limits<T>::max(); } + static constexpr T Overflow() { + return std::numeric_limits<T>::has_infinity + ? std::numeric_limits<T>::infinity() + : std::numeric_limits<T>::max(); + } + static constexpr T lowest() { return std::numeric_limits<T>::lowest(); } + static constexpr T Underflow() { + return std::numeric_limits<T>::has_infinity + ? std::numeric_limits<T>::infinity() * -1 + : std::numeric_limits<T>::lowest(); + } +}; + +namespace internal { + +template <typename Dst, template <typename> 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<Dst>(value) + : S<Dst>::Underflow()) + // Skip this check for integral Src, which cannot be NaN. + : (std::is_integral<Src>::value || !constraint.IsUnderflowFlagSet() + ? S<Dst>::Overflow() + : S<Dst>::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 <typename Dst, + template <typename> + class SaturationHandler = SaturationDefaultHandler, + typename Src> +constexpr Dst saturated_cast(Src value) { + using SrcType = typename UnderlyingType<Src>::type; + return saturated_cast_impl<Dst, SaturationHandler, SrcType>( + value, + DstRangeRelationToSrcRange<Dst, SaturationHandler, SrcType>(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 <typename Dst, typename Src> -inline Dst saturated_cast(Src value) { - // Optimization for floating point values, which already saturate. - if (std::numeric_limits<Dst>::is_iec559) - return static_cast<Dst>(value); +constexpr Dst strict_cast(Src value) { + using SrcType = typename UnderlyingType<Src>::type; + static_assert(UnderlyingType<Src>::is_numeric, "Argument must be numeric."); + static_assert(std::is_arithmetic<Dst>::value, "Result must be numeric."); - switch (internal::DstRangeRelationToSrcRange<Dst>(value)) { - case internal::RANGE_VALID: - return static_cast<Dst>(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<Dst, SrcType>::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<Dst>::min(); + return static_cast<Dst>(static_cast<SrcType>(value)); +} - case internal::RANGE_OVERFLOW: - return std::numeric_limits<Dst>::max(); +// Some wrappers to statically check that a type is in range. +template <typename Dst, typename Src, class Enable = void> +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<Dst>::max(); +template <typename Dst, typename Src> +struct IsNumericRangeContained< + Dst, + Src, + typename std::enable_if<ArithmeticOrUnderlyingEnum<Dst>::value && + ArithmeticOrUnderlyingEnum<Src>::value>::type> { + static const bool value = StaticDstRangeRelationToSrcRange<Dst, Src>::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 <typename T> +class StrictNumeric { + public: + using type = T; + + constexpr StrictNumeric() : value_(0) {} + + // Copy constructor. + template <typename Src> + constexpr StrictNumeric(const StrictNumeric<Src>& rhs) + : value_(strict_cast<T>(rhs.value_)) {} + + // This is not an explicit constructor because we implicitly upgrade regular + // numerics to StrictNumerics to make them easier to use. + template <typename Src> + constexpr StrictNumeric(Src value) // NOLINT(runtime/explicit) + : value_(strict_cast<T>(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<Dst>()), use one + // of the value helper functions (e.g. ValueOrDieForType<Dst>(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 <typename Dst, + typename std::enable_if< + IsNumericRangeContained<Dst, T>::value>::type* = nullptr> + constexpr operator Dst() const { + return static_cast<typename ArithmeticOrUnderlyingEnum<Dst>::type>(value_); } - NOTREACHED(); - return static_cast<Dst>(value); + private: + const T value_; +}; + +// Convience wrapper returns a StrictNumeric from the provided arithmetic type. +template <typename T> +constexpr StrictNumeric<typename UnderlyingType<T>::type> MakeStrictNum( + const T value) { + return value; +} + +// Overload the ostream output operator to make logging work nicely. +template <typename T> +std::ostream& operator<<(std::ostream& os, const StrictNumeric<T>& value) { + os << static_cast<T>(value); + return os; } +#define STRICT_COMPARISON_OP(NAME, OP) \ + template <typename L, typename R, \ + typename std::enable_if< \ + internal::IsStrictOp<L, R>::value>::type* = nullptr> \ + constexpr bool operator OP(const L lhs, const R rhs) { \ + return SafeCompare<NAME, typename UnderlyingType<L>::type, \ + typename UnderlyingType<R>::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<size_t>; + } // 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 <assert.h> -#include <limits> +#include <stdint.h> -#include "third_party/base/macros.h" +#include <limits> +#include <type_traits> 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 <typename NumericType> struct MaxExponent { - static const int value = std::numeric_limits<NumericType>::is_iec559 + static const int value = std::is_floating_point<NumericType>::value ? std::numeric_limits<NumericType>::max_exponent - : (sizeof(NumericType) * 8 + 1 - - std::numeric_limits<NumericType>::is_signed); + : std::numeric_limits<NumericType>::digits + 1; +}; + +// The number of bits (including the sign) in an integer. Eliminates sizeof +// hacks. +template <typename NumericType> +struct IntegerBitsPlusSign { + static const int value = std::numeric_limits<NumericType>::digits + + std::is_signed<NumericType>::value; +}; + +// Helper templates for integer manipulations. + +template <typename Integer> +struct PositionOfSignBit { + static const size_t value = IntegerBitsPlusSign<Integer>::value - 1; }; +// Determines if a numeric value is negative without throwing compiler +// warnings on: unsigned(value) < 0. +template <typename T, + typename std::enable_if<std::is_signed<T>::value>::type* = nullptr> +constexpr bool IsValueNegative(T value) { + static_assert(std::is_arithmetic<T>::value, "Argument must be numeric."); + return value < 0; +} + +template <typename T, + typename std::enable_if<!std::is_signed<T>::value>::type* = nullptr> +constexpr bool IsValueNegative(T) { + static_assert(std::is_arithmetic<T>::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 <typename T> +constexpr typename std::make_signed<T>::type ConditionalNegate( + T x, + bool is_negative) { + static_assert(std::is_integral<T>::value, "Type must be integral"); + using SignedT = typename std::make_signed<T>::type; + using UnsignedT = typename std::make_unsigned<T>::type; + return static_cast<SignedT>( + (static_cast<UnsignedT>(x) ^ -SignedT(is_negative)) + is_negative); +} + +// This performs a safe, absolute value via unsigned overflow. +template <typename T> +constexpr typename std::make_unsigned<T>::type SafeUnsignedAbs(T value) { + static_assert(std::is_integral<T>::value, "Type must be integral"); + using UnsignedT = typename std::make_unsigned<T>::type; + return IsValueNegative(value) ? 0 - static_cast<UnsignedT>(value) + : static_cast<UnsignedT>(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<Src>::max() <= numeric_limits<Dst>::max() and -// numeric_limits<Src>::min() >= numeric_limits<Dst>::min() are true. +// numeric_limits<Src>::lowest() >= numeric_limits<Dst>::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<Dst>::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - IntegerRepresentation SrcSign = - std::numeric_limits<Src>::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED > +template <typename Dst, + typename Src, + IntegerRepresentation DstSign = std::is_signed<Dst>::value + ? INTEGER_REPRESENTATION_SIGNED + : INTEGER_REPRESENTATION_UNSIGNED, + IntegerRepresentation SrcSign = std::is_signed<Src>::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<Dst, static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED; }; -enum RangeConstraint { - RANGE_VALID = 0x0, // Value can be represented by the destination type. - RANGE_UNDERFLOW = 0x1, // Value would overflow. - RANGE_OVERFLOW = 0x2, // Value would underflow. - RANGE_INVALID = RANGE_UNDERFLOW | RANGE_OVERFLOW // Invalid (i.e. NaN). +// 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_(0), is_overflow_(0) {} + 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_; }; -// Helper function for coercing an int back to a RangeContraint. -inline RangeConstraint GetRangeConstraint(int integer_range_constraint) { - assert(integer_range_constraint >= RANGE_VALID && - integer_range_constraint <= RANGE_INVALID); - return static_cast<RangeConstraint>(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 <typename Dst, typename Src, template <typename> class Bounds> +struct NarrowingRange { + using SrcLimits = std::numeric_limits<Src>; + using DstLimits = typename std::numeric_limits<Dst>; -// 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<Src>::value > MaxExponent<Dst>::value && + SrcLimits::digits < DstLimits::digits) + ? (DstLimits::digits - SrcLimits::digits) + : 0; + template < + typename T, + typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> -template < - typename Dst, - typename Src, - IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - IntegerRepresentation SrcSign = std::numeric_limits<Src>::is_signed - ? INTEGER_REPRESENTATION_SIGNED - : INTEGER_REPRESENTATION_UNSIGNED, - NumericRangeRepresentation DstRange = - StaticDstRangeRelationToSrcRange<Dst, Src>::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<T, Dst>::value, ""); + static_assert(kShift < DstLimits::digits, ""); + return static_cast<T>( + ConditionalNegate(SafeUnsignedAbs(value) & ~((T(1) << kShift) - T(1)), + IsValueNegative(value))); + } + + template <typename T, + typename std::enable_if<std::is_floating_point<T>::value>::type* = + nullptr> + static constexpr T Adjust(T value) { + static_assert(std::is_same<T, Dst>::value, ""); + static_assert(kShift == 0, ""); + return value; + } + + static constexpr Dst max() { return Adjust(Bounds<Dst>::max()); } + static constexpr Dst lowest() { return Adjust(Bounds<Dst>::lowest()); } +}; + +template <typename Dst, + typename Src, + template <typename> class Bounds, + IntegerRepresentation DstSign = std::is_signed<Dst>::value + ? INTEGER_REPRESENTATION_SIGNED + : INTEGER_REPRESENTATION_UNSIGNED, + IntegerRepresentation SrcSign = std::is_signed<Src>::value + ? INTEGER_REPRESENTATION_SIGNED + : INTEGER_REPRESENTATION_UNSIGNED, + NumericRangeRepresentation DstRange = + StaticDstRangeRelationToSrcRange<Dst, Src>::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 <typename Dst, typename Src, + template <typename> class Bounds, IntegerRepresentation DstSign, IntegerRepresentation SrcSign> struct DstRangeRelationToSrcRangeImpl<Dst, Src, + Bounds, DstSign, SrcSign, NUMERIC_RANGE_CONTAINED> { - static RangeConstraint Check(Src value) { return RANGE_VALID; } + static constexpr RangeCheck Check(Src value) { + using SrcLimits = std::numeric_limits<Src>; + using DstLimits = NarrowingRange<Dst, Src, Bounds>; + return RangeCheck( + static_cast<Dst>(SrcLimits::lowest()) >= DstLimits::lowest() || + static_cast<Dst>(value) >= DstLimits::lowest(), + static_cast<Dst>(SrcLimits::max()) <= DstLimits::max() || + static_cast<Dst>(value) <= DstLimits::max()); + } }; // Signed to signed narrowing: Both the upper and lower boundaries may be -// exceeded. -template <typename Dst, typename Src> +// exceeded for standard limits. +template <typename Dst, typename Src, template <typename> class Bounds> struct DstRangeRelationToSrcRangeImpl<Dst, Src, + Bounds, INTEGER_REPRESENTATION_SIGNED, INTEGER_REPRESENTATION_SIGNED, NUMERIC_RANGE_NOT_CONTAINED> { - static RangeConstraint Check(Src value) { - return std::numeric_limits<Dst>::is_iec559 - ? GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), - value >= -std::numeric_limits<Dst>::max()) - : GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), - value >= std::numeric_limits<Dst>::min()); + static constexpr RangeCheck Check(Src value) { + using DstLimits = NarrowingRange<Dst, Src, Bounds>; + return RangeCheck(value >= DstLimits::lowest(), value <= DstLimits::max()); } }; -// Unsigned to unsigned narrowing: Only the upper boundary can be exceeded. -template <typename Dst, typename Src> +// Unsigned to unsigned narrowing: Only the upper bound can be exceeded for +// standard limits. +template <typename Dst, typename Src, template <typename> class Bounds> struct DstRangeRelationToSrcRangeImpl<Dst, Src, + Bounds, INTEGER_REPRESENTATION_UNSIGNED, INTEGER_REPRESENTATION_UNSIGNED, NUMERIC_RANGE_NOT_CONTAINED> { - static RangeConstraint Check(Src value) { - return GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), true); + static constexpr RangeCheck Check(Src value) { + using DstLimits = NarrowingRange<Dst, Src, Bounds>; + return RangeCheck( + DstLimits::lowest() == Dst(0) || value >= DstLimits::lowest(), + value <= DstLimits::max()); } }; -// Unsigned to signed: The upper boundary may be exceeded. -template <typename Dst, typename Src> +// Unsigned to signed: Only the upper bound can be exceeded for standard limits. +template <typename Dst, typename Src, template <typename> class Bounds> struct DstRangeRelationToSrcRangeImpl<Dst, Src, + Bounds, INTEGER_REPRESENTATION_SIGNED, INTEGER_REPRESENTATION_UNSIGNED, NUMERIC_RANGE_NOT_CONTAINED> { - static RangeConstraint Check(Src value) { - return sizeof(Dst) > sizeof(Src) - ? RANGE_VALID - : GetRangeConstraint( - value <= static_cast<Src>(std::numeric_limits<Dst>::max()), - true); + static constexpr RangeCheck Check(Src value) { + using DstLimits = NarrowingRange<Dst, Src, Bounds>; + using Promotion = decltype(Src() + Dst()); + return RangeCheck(DstLimits::lowest() <= Dst(0) || + static_cast<Promotion>(value) >= + static_cast<Promotion>(DstLimits::lowest()), + static_cast<Promotion>(value) <= + static_cast<Promotion>(DstLimits::max())); } }; // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst, -// and any negative value exceeds the lower boundary. -template <typename Dst, typename Src> +// and any negative value exceeds the lower boundary for standard limits. +template <typename Dst, typename Src, template <typename> class Bounds> struct DstRangeRelationToSrcRangeImpl<Dst, Src, + Bounds, INTEGER_REPRESENTATION_UNSIGNED, INTEGER_REPRESENTATION_SIGNED, NUMERIC_RANGE_NOT_CONTAINED> { - static RangeConstraint Check(Src value) { - return (MaxExponent<Dst>::value >= MaxExponent<Src>::value) - ? GetRangeConstraint(true, value >= static_cast<Src>(0)) - : GetRangeConstraint( - value <= static_cast<Src>(std::numeric_limits<Dst>::max()), - value >= static_cast<Src>(0)); + static constexpr RangeCheck Check(Src value) { + using SrcLimits = std::numeric_limits<Src>; + using DstLimits = NarrowingRange<Dst, Src, Bounds>; + using Promotion = decltype(Src() + Dst()); + return RangeCheck( + value >= Src(0) && (DstLimits::lowest() == 0 || + static_cast<Dst>(value) >= DstLimits::lowest()), + static_cast<Promotion>(SrcLimits::max()) <= + static_cast<Promotion>(DstLimits::max()) || + static_cast<Promotion>(value) <= + static_cast<Promotion>(DstLimits::max())); } }; -template <typename Dst, typename Src> -inline RangeConstraint DstRangeRelationToSrcRange(Src value) { - COMPILE_ASSERT(std::numeric_limits<Src>::is_specialized, - argument_must_be_numeric); - COMPILE_ASSERT(std::numeric_limits<Dst>::is_specialized, - result_must_be_numeric); - return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value); +template <typename Dst, + template <typename> class Bounds = std::numeric_limits, + typename Src> +constexpr RangeCheck DstRangeRelationToSrcRange(Src value) { + static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric."); + static_assert(std::is_arithmetic<Dst>::value, "Result must be numeric."); + static_assert(Bounds<Dst>::lowest() < Bounds<Dst>::max(), ""); + return DstRangeRelationToSrcRangeImpl<Dst, Src, Bounds>::Check(value); } +// Integer promotion templates used by the portable checked integer arithmetic. +template <size_t Size, bool IsSigned> +struct IntegerForDigitsAndSign; + +#define INTEGER_FOR_DIGITS_AND_SIGN(I) \ + template <> \ + struct IntegerForDigitsAndSign<IntegerBitsPlusSign<I>::value, \ + std::is_signed<I>::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<intmax_t>::value == 64, + "Max integer size not supported for this toolchain."); + +template <typename Integer, bool IsSigned = std::is_signed<Integer>::value> +struct TwiceWiderInteger { + using type = + typename IntegerForDigitsAndSign<IntegerBitsPlusSign<Integer>::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 <typename Lhs, + typename Rhs, + ArithmeticPromotionCategory Promotion = + (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) + ? LEFT_PROMOTION + : RIGHT_PROMOTION> +struct MaxExponentPromotion; + +template <typename Lhs, typename Rhs> +struct MaxExponentPromotion<Lhs, Rhs, LEFT_PROMOTION> { + using type = Lhs; +}; + +template <typename Lhs, typename Rhs> +struct MaxExponentPromotion<Lhs, Rhs, RIGHT_PROMOTION> { + using type = Rhs; +}; + +// Determines the type that can represent the lowest arithmetic value. +template <typename Lhs, + typename Rhs, + ArithmeticPromotionCategory Promotion = + std::is_signed<Lhs>::value + ? (std::is_signed<Rhs>::value + ? (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value + ? LEFT_PROMOTION + : RIGHT_PROMOTION) + : LEFT_PROMOTION) + : (std::is_signed<Rhs>::value + ? RIGHT_PROMOTION + : (MaxExponent<Lhs>::value < MaxExponent<Rhs>::value + ? LEFT_PROMOTION + : RIGHT_PROMOTION))> +struct LowestValuePromotion; + +template <typename Lhs, typename Rhs> +struct LowestValuePromotion<Lhs, Rhs, LEFT_PROMOTION> { + using type = Lhs; +}; + +template <typename Lhs, typename Rhs> +struct LowestValuePromotion<Lhs, Rhs, RIGHT_PROMOTION> { + 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<typename MaxExponentPromotion<Lhs, Rhs>::type>::value&& + IntegerBitsPlusSign<typename MaxExponentPromotion<Lhs, Rhs>::type>:: + value == IntegerBitsPlusSign<intmax_t>::value, + bool is_max_exponent = + StaticDstRangeRelationToSrcRange< + typename MaxExponentPromotion<Lhs, Rhs>::type, + Lhs>::value == + NUMERIC_RANGE_CONTAINED&& StaticDstRangeRelationToSrcRange< + typename MaxExponentPromotion<Lhs, Rhs>::type, + Rhs>::value == NUMERIC_RANGE_CONTAINED> +struct BigEnoughPromotion; + +// The side with the max exponent is big enough. +template <typename Lhs, typename Rhs, bool is_intmax_type> +struct BigEnoughPromotion<Lhs, Rhs, is_intmax_type, true> { + using type = typename MaxExponentPromotion<Lhs, Rhs>::type; + static const bool is_contained = true; +}; + +// We can use a twice wider type to fit. +template <typename Lhs, typename Rhs> +struct BigEnoughPromotion<Lhs, Rhs, false, false> { + using type = + typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type, + std::is_signed<Lhs>::value || + std::is_signed<Rhs>::value>::type; + static const bool is_contained = true; +}; + +// No type is large enough. +template <typename Lhs, typename Rhs> +struct BigEnoughPromotion<Lhs, Rhs, true, false> { + using type = typename MaxExponentPromotion<Lhs, Rhs>::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 <typename T, typename Lhs, typename Rhs = Lhs> +struct IsIntegerArithmeticSafe { + static const bool value = + !std::is_floating_point<T>::value && + !std::is_floating_point<Lhs>::value && + !std::is_floating_point<Rhs>::value && + std::is_signed<T>::value >= std::is_signed<Lhs>::value && + IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Lhs>::value) && + std::is_signed<T>::value >= std::is_signed<Rhs>::value && + IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Rhs>::value); +}; + +// Promotes to a type that can represent any possible result of a binary +// arithmetic operation with the source types. +template <typename Lhs, + typename Rhs, + bool is_promotion_possible = IsIntegerArithmeticSafe< + typename std::conditional<std::is_signed<Lhs>::value || + std::is_signed<Rhs>::value, + intmax_t, + uintmax_t>::type, + typename MaxExponentPromotion<Lhs, Rhs>::type>::value> +struct FastIntegerArithmeticPromotion; + +template <typename Lhs, typename Rhs> +struct FastIntegerArithmeticPromotion<Lhs, Rhs, true> { + using type = + typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type, + std::is_signed<Lhs>::value || + std::is_signed<Rhs>::value>::type; + static_assert(IsIntegerArithmeticSafe<type, Lhs, Rhs>::value, ""); + static const bool is_contained = true; +}; + +template <typename Lhs, typename Rhs> +struct FastIntegerArithmeticPromotion<Lhs, Rhs, false> { + using type = typename BigEnoughPromotion<Lhs, Rhs>::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 <typename T, bool is_enum = std::is_enum<T>::value> +struct ArithmeticOrUnderlyingEnum; + +template <typename T> +struct ArithmeticOrUnderlyingEnum<T, true> { +#if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) + using type = __underlying_type(T); +#else + using type = typename std::underlying_type<T>::type; +#endif + static const bool value = std::is_arithmetic<type>::value; +}; + +#if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) +#undef PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX +#endif + +template <typename T> +struct ArithmeticOrUnderlyingEnum<T, false> { + using type = T; + static const bool value = std::is_arithmetic<type>::value; +}; + +// The following are helper templates used in the CheckedNumeric class. +template <typename T> +class CheckedNumeric; + +template <typename T> +class StrictNumeric; + +// Used to treat CheckedNumeric and arithmetic underlying types the same. +template <typename T> +struct UnderlyingType { + using type = typename ArithmeticOrUnderlyingEnum<T>::type; + static const bool is_numeric = std::is_arithmetic<type>::value; + static const bool is_checked = false; + static const bool is_strict = false; +}; + +template <typename T> +struct UnderlyingType<CheckedNumeric<T>> { + using type = T; + static const bool is_numeric = true; + static const bool is_checked = true; + static const bool is_strict = false; +}; + +template <typename T> +struct UnderlyingType<StrictNumeric<T>> { + using type = T; + static const bool is_numeric = true; + static const bool is_checked = false; + static const bool is_strict = true; +}; + +template <typename L, typename R> +struct IsCheckedOp { + static const bool value = + UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric && + (UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked); +}; + +template <typename L, typename R> +struct IsStrictOp { + static const bool value = + UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric && + (UnderlyingType<L>::is_strict || UnderlyingType<R>::is_strict); +}; + +template <typename L, typename R> +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<decltype(lhs + rhs)>(lhs) < + static_cast<decltype(lhs + rhs)>(rhs)); +} + +template <typename L, typename R> +struct IsLess { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return IsLessImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), + DstRangeRelationToSrcRange<L>(rhs)); + } +}; + +template <typename L, typename R> +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<decltype(lhs + rhs)>(lhs) <= + static_cast<decltype(lhs + rhs)>(rhs)); +} + +template <typename L, typename R> +struct IsLessOrEqual { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return IsLessOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), + DstRangeRelationToSrcRange<L>(rhs)); + } +}; + +template <typename L, typename R> +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<decltype(lhs + rhs)>(lhs) > + static_cast<decltype(lhs + rhs)>(rhs)); +} + +template <typename L, typename R> +struct IsGreater { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return IsGreaterImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), + DstRangeRelationToSrcRange<L>(rhs)); + } +}; + +template <typename L, typename R> +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<decltype(lhs + rhs)>(lhs) >= + static_cast<decltype(lhs + rhs)>(rhs)); +} + +template <typename L, typename R> +struct IsGreaterOrEqual { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return IsGreaterOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), + DstRangeRelationToSrcRange<L>(rhs)); + } +}; + +template <typename L, typename R> +struct IsEqual { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return DstRangeRelationToSrcRange<R>(lhs) == + DstRangeRelationToSrcRange<L>(rhs) && + static_cast<decltype(lhs + rhs)>(lhs) == + static_cast<decltype(lhs + rhs)>(rhs); + } +}; + +template <typename L, typename R> +struct IsNotEqual { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + static constexpr bool Test(const L lhs, const R rhs) { + return DstRangeRelationToSrcRange<R>(lhs) != + DstRangeRelationToSrcRange<L>(rhs) || + static_cast<decltype(lhs + rhs)>(lhs) != + static_cast<decltype(lhs + rhs)>(rhs); + } +}; + +// These perform the actual math operations on the CheckedNumerics. +// Binary arithmetic operations. +template <template <typename, typename> class C, typename L, typename R> +constexpr bool SafeCompare(const L lhs, const R rhs) { + static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, + "Types must be numeric."); + using Promotion = BigEnoughPromotion<L, R>; + using BigType = typename Promotion::type; + return Promotion::is_contained + // Force to a larger type for speed if both are contained. + ? C<BigType, BigType>::Test( + static_cast<BigType>(static_cast<L>(lhs)), + static_cast<BigType>(static_cast<R>(rhs))) + // Let the template functions figure it out for mixed types. + : C<L, R>::Test(lhs, rhs); +}; + } // namespace internal } // namespace base } // namespace pdfium -#endif // PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_IMPL_H_ +#endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ diff --git a/third_party/base/numerics/safe_math.h b/third_party/base/numerics/safe_math.h index 013af1eb60..a0c41a467b 100644 --- a/third_party/base/numerics/safe_math.h +++ b/third_party/base/numerics/safe_math.h @@ -2,140 +2,268 @@ // 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_MATH_H_ -#define PDFIUM_THIRD_PARTY_BASE_SAFE_MATH_H_ +#ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_ +#define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_ -#include "safe_math_impl.h" +#include <stddef.h> + +#include <limits> +#include <type_traits> + +#include "third_party/base/numerics/safe_math_impl.h" namespace pdfium { namespace base { namespace internal { -// CheckedNumeric implements all the logic and operators for detecting integer +// CheckedNumeric<> implements all the logic and operators for detecting integer // boundary conditions such as overflow, underflow, and invalid conversions. // The CheckedNumeric type implicitly converts from floating point and integer // data types, and contains overloads for basic arithmetic operations (i.e.: +, -// -, *, /, %). +// -, *, / for all types and %, <<, >>, &, |, ^ for integers). Type promotions +// are a slightly modified version of the standard C arithmetic rules with the +// two differences being that there is no default promotion to int and bitwise +// logical operations always return an unsigned of the wider type. +// +// You may also use one of the variadic convenience functions, which accept +// standard arithmetic or CheckedNumeric types, perform arithmetic operations, +// and return a CheckedNumeric result. The supported functions are: +// CheckAdd() - Addition. +// CheckSub() - Subtraction. +// CheckMul() - Multiplication. +// CheckDiv() - Division. +// CheckMod() - Modulous (integer only). +// CheckLsh() - Left integer shift (integer only). +// CheckRsh() - Right integer shift (integer only). +// CheckAnd() - Bitwise AND (integer only with unsigned result). +// CheckOr() - Bitwise OR (integer only with unsigned result). +// CheckXor() - Bitwise XOR (integer only with unsigned result). +// CheckMax() - Maximum of supplied arguments. +// CheckMin() - Minimum of supplied arguments. +// +// The unary negation, increment, and decrement operators are supported, along +// with the following unary arithmetic methods, which return a new +// CheckedNumeric as a result of the operation: +// Abs() - Absolute value. +// UnsignedAbs() - Absolute value as an equal-width unsigned underlying type +// (valid for only integral types). +// Max() - Returns whichever is greater of the current instance or argument. +// The underlying return type is whichever has the greatest magnitude. +// Min() - Returns whichever is lowest of the current instance or argument. +// The underlying return type is whichever has can represent the lowest +// number in the smallest width (e.g. int8_t over unsigned, int over +// int8_t, and float over int). // // The following methods convert from CheckedNumeric to standard numeric values: -// IsValid() - Returns true if the underlying numeric value is valid (i.e. has -// has not wrapped and is not the result of an invalid conversion). -// ValueOrDie() - Returns the underlying value. If the state is not valid this -// call will crash on a CHECK. -// ValueOrDefault() - Returns the current value, or the supplied default if the -// state is not valid. -// ValueFloating() - Returns the underlying floating point value (valid only -// only for floating point CheckedNumeric types). +// AssignIfValid() - Assigns the underlying value to the supplied destination +// pointer if the value is currently valid and within the range +// supported by the destination type. Returns true on success. +// **************************************************************************** +// * WARNING: All of the following functions return a StrictNumeric, which * +// * is valid for comparison and assignment operations, but will trigger a * +// * compile failure on attempts to assign to a type of insufficient range. * +// **************************************************************************** +// IsValid() - Returns true if the underlying numeric value is valid (i.e. has +// has not wrapped and is not the result of an invalid conversion). +// ValueOrDie() - Returns the underlying value. If the state is not valid this +// call will crash on a CHECK. +// ValueOrDefault() - Returns the current value, or the supplied default if the +// state is not valid (will not trigger a CHECK). // -// Bitwise operations are explicitly not supported, because correct -// handling of some cases (e.g. sign manipulation) is ambiguous. Comparison -// operations are explicitly not supported because they could result in a crash -// on a CHECK condition. You should use patterns like the following for these -// operations: -// Bitwise operation: -// CheckedNumeric<int> checked_int = untrusted_input_value; -// int x = checked_int.ValueOrDefault(0) | kFlagValues; -// Comparison: -// CheckedNumeric<size_t> checked_size; -// CheckedNumeric<int> checked_size = untrusted_input_value; -// checked_size = checked_size + HEADER LENGTH; +// The following wrapper functions can be used to avoid the template +// disambiguator syntax when converting a destination type. +// IsValidForType<>() in place of: a.template IsValid<Dst>() +// ValueOrDieForType<>() in place of: a.template ValueOrDie() +// ValueOrDefaultForType<>() in place of: a.template ValueOrDefault(default) +// +// The following are general utility methods that are useful for converting +// between arithmetic types and CheckedNumeric types: +// CheckedNumeric::Cast<Dst>() - Instance method returning a CheckedNumeric +// derived from casting the current instance to a CheckedNumeric of +// the supplied destination type. +// MakeCheckedNum() - Creates a new CheckedNumeric from the underlying type of +// the supplied arithmetic, CheckedNumeric, or StrictNumeric type. +// +// Comparison operations are explicitly not supported because they could result +// in a crash on an unexpected CHECK condition. You should use patterns like the +// following for comparisons: +// CheckedNumeric<size_t> checked_size = untrusted_input_value; +// checked_size += HEADER LENGTH; // if (checked_size.IsValid() && checked_size.ValueOrDie() < buffer_size) // Do stuff... + template <typename T> class CheckedNumeric { + static_assert(std::is_arithmetic<T>::value, + "CheckedNumeric<T>: T must be a numeric type."); + public: - typedef T type; + using type = T; - CheckedNumeric() {} + constexpr CheckedNumeric() {} // Copy constructor. template <typename Src> - CheckedNumeric(const CheckedNumeric<Src>& rhs) - : state_(rhs.ValueUnsafe(), rhs.validity()) {} + constexpr CheckedNumeric(const CheckedNumeric<Src>& rhs) + : state_(rhs.state_.value(), rhs.IsValid()) {} template <typename Src> - CheckedNumeric(Src value, RangeConstraint validity) - : state_(value, validity) {} + friend class CheckedNumeric; // This is not an explicit constructor because we implicitly upgrade regular // numerics to CheckedNumerics to make them easier to use. template <typename Src> - CheckedNumeric(Src value) + constexpr CheckedNumeric(Src value) // NOLINT(runtime/explicit) : state_(value) { - COMPILE_ASSERT(std::numeric_limits<Src>::is_specialized, - argument_must_be_numeric); + static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric."); + } + + // This is not an explicit constructor because we want a seamless conversion + // from StrictNumeric types. + template <typename Src> + constexpr CheckedNumeric( + StrictNumeric<Src> value) // NOLINT(runtime/explicit) + : state_(static_cast<Src>(value)) {} + + // IsValid() - The public API to test if a CheckedNumeric is currently valid. + // A range checked destination type can be supplied using the Dst template + // parameter. + template <typename Dst = T> + constexpr bool IsValid() const { + return state_.is_valid() && + IsValueInRangeForNumericType<Dst>(state_.value()); } - // IsValid() is the public API to test if a CheckedNumeric is currently valid. - bool IsValid() const { return validity() == RANGE_VALID; } + // AssignIfValid(Dst) - Assigns the underlying value if it is currently valid + // and is within the range supported by the destination type. Returns true if + // successful and false otherwise. + template <typename Dst> + constexpr bool AssignIfValid(Dst* result) const { + return IsValid<Dst>() ? ((*result = static_cast<Dst>(state_.value())), true) + : false; + } - // ValueOrDie() The primary accessor for the underlying value. If the current - // state is not valid it will CHECK and crash. - T ValueOrDie() const { - CHECK(IsValid()); - return state_.value(); + // ValueOrDie() - The primary accessor for the underlying value. If the + // current state is not valid it will CHECK and crash. + // A range checked destination type can be supplied using the Dst template + // parameter, which will trigger a CHECK if the value is not in bounds for + // the destination. + // The CHECK behavior can be overridden by supplying a handler as a + // template parameter, for test code, etc. However, the handler cannot access + // the underlying value, and it is not available through other means. + template <typename Dst = T, class CheckHandler = CheckOnFailure> + constexpr StrictNumeric<Dst> ValueOrDie() const { + return IsValid<Dst>() ? static_cast<Dst>(state_.value()) + : CheckHandler::template HandleFailure<Dst>(); } - // ValueOrDefault(T default_value) A convenience method that returns the + // ValueOrDefault(T default_value) - A convenience method that returns the // current value if the state is valid, and the supplied default_value for // any other state. - T ValueOrDefault(T default_value) const { - return IsValid() ? state_.value() : default_value; + // A range checked destination type can be supplied using the Dst template + // parameter. WARNING: This function may fail to compile or CHECK at runtime + // if the supplied default_value is not within range of the destination type. + template <typename Dst = T, typename Src> + constexpr StrictNumeric<Dst> ValueOrDefault(const Src default_value) const { + return IsValid<Dst>() ? static_cast<Dst>(state_.value()) + : checked_cast<Dst>(default_value); } - // ValueFloating() - Since floating point values include their validity state, - // we provide an easy method for extracting them directly, without a risk of - // crashing on a CHECK. - T ValueFloating() const { - COMPILE_ASSERT(std::numeric_limits<T>::is_iec559, argument_must_be_float); - return CheckedNumeric<T>::cast(*this).ValueUnsafe(); + // Returns a checked numeric of the specified type, cast from the current + // CheckedNumeric. If the current state is invalid or the destination cannot + // represent the result then the returned CheckedNumeric will be invalid. + template <typename Dst> + constexpr CheckedNumeric<typename UnderlyingType<Dst>::type> Cast() const { + return *this; } - // validity() - DO NOT USE THIS IN EXTERNAL CODE - It is public right now for - // tests and to avoid a big matrix of friend operator overloads. But the - // values it returns are likely to change in the future. - // Returns: current validity state (i.e. valid, overflow, underflow, nan). - // TODO(jschuh): crbug.com/332611 Figure out and implement semantics for - // saturation/wrapping so we can expose this state consistently and implement - // saturated arithmetic. - RangeConstraint validity() const { return state_.validity(); } - - // ValueUnsafe() - DO NOT USE THIS IN EXTERNAL CODE - It is public right now - // for tests and to avoid a big matrix of friend operator overloads. But the - // values it returns are likely to change in the future. - // Returns: the raw numeric value, regardless of the current state. - // TODO(jschuh): crbug.com/332611 Figure out and implement semantics for - // saturation/wrapping so we can expose this state consistently and implement - // saturated arithmetic. - T ValueUnsafe() const { return state_.value(); } + // This friend method is available solely for providing more detailed logging + // in the the tests. Do not implement it in production code, because the + // underlying values may change at any time. + template <typename U> + friend U GetNumericValueForTest(const CheckedNumeric<U>& src); // Prototypes for the supported arithmetic operator overloads. - template <typename Src> CheckedNumeric& operator+=(Src rhs); - template <typename Src> CheckedNumeric& operator-=(Src rhs); - template <typename Src> CheckedNumeric& operator*=(Src rhs); - template <typename Src> CheckedNumeric& operator/=(Src rhs); - template <typename Src> CheckedNumeric& operator%=(Src rhs); - - CheckedNumeric operator-() const { - RangeConstraint validity; - T value = CheckedNeg(state_.value(), &validity); - // Negation is always valid for floating point. - if (std::numeric_limits<T>::is_iec559) - return CheckedNumeric<T>(value); - - validity = GetRangeConstraint(state_.validity() | validity); - return CheckedNumeric<T>(value, validity); + template <typename Src> + CheckedNumeric& operator+=(const Src rhs); + template <typename Src> + CheckedNumeric& operator-=(const Src rhs); + template <typename Src> + CheckedNumeric& operator*=(const Src rhs); + template <typename Src> + CheckedNumeric& operator/=(const Src rhs); + template <typename Src> + CheckedNumeric& operator%=(const Src rhs); + template <typename Src> + CheckedNumeric& operator<<=(const Src rhs); + template <typename Src> + CheckedNumeric& operator>>=(const Src rhs); + template <typename Src> + CheckedNumeric& operator&=(const Src rhs); + template <typename Src> + CheckedNumeric& operator|=(const Src rhs); + template <typename Src> + CheckedNumeric& operator^=(const Src rhs); + + constexpr CheckedNumeric operator-() const { + return CheckedNumeric<T>( + NegateWrapper(state_.value()), + IsValid() && + (!std::is_signed<T>::value || std::is_floating_point<T>::value || + NegateWrapper(state_.value()) != + std::numeric_limits<T>::lowest())); + } + + constexpr CheckedNumeric operator~() const { + return CheckedNumeric<decltype(InvertWrapper(T()))>( + InvertWrapper(state_.value()), IsValid()); } - CheckedNumeric Abs() const { - RangeConstraint validity; - T value = CheckedAbs(state_.value(), &validity); - // Absolute value is always valid for floating point. - if (std::numeric_limits<T>::is_iec559) - return CheckedNumeric<T>(value); + constexpr CheckedNumeric Abs() const { + return CheckedNumeric<T>( + AbsWrapper(state_.value()), + IsValid() && + (!std::is_signed<T>::value || std::is_floating_point<T>::value || + AbsWrapper(state_.value()) != std::numeric_limits<T>::lowest())); + } + + template <typename U> + constexpr CheckedNumeric<typename MathWrapper<CheckedMaxOp, T, U>::type> Max( + const U rhs) const { + using R = typename UnderlyingType<U>::type; + using result_type = typename MathWrapper<CheckedMaxOp, T, U>::type; + // TODO(jschuh): This can be converted to the MathOp version and remain + // constexpr once we have C++14 support. + return CheckedNumeric<result_type>( + static_cast<result_type>( + IsGreater<T, R>::Test(state_.value(), Wrapper<U>::value(rhs)) + ? state_.value() + : Wrapper<U>::value(rhs)), + state_.is_valid() && Wrapper<U>::is_valid(rhs)); + } - validity = GetRangeConstraint(state_.validity() | validity); - return CheckedNumeric<T>(value, validity); + template <typename U> + constexpr CheckedNumeric<typename MathWrapper<CheckedMinOp, T, U>::type> Min( + const U rhs) const { + using R = typename UnderlyingType<U>::type; + using result_type = typename MathWrapper<CheckedMinOp, T, U>::type; + // TODO(jschuh): This can be converted to the MathOp version and remain + // constexpr once we have C++14 support. + return CheckedNumeric<result_type>( + static_cast<result_type>( + IsLess<T, R>::Test(state_.value(), Wrapper<U>::value(rhs)) + ? state_.value() + : Wrapper<U>::value(rhs)), + state_.is_valid() && Wrapper<U>::is_valid(rhs)); + } + + // This function is available only for integral types. It returns an unsigned + // integer of the same width as the source type, containing the absolute value + // of the source, and properly handling signed min. + constexpr CheckedNumeric<typename UnsignedOrFloatForSize<T>::type> + UnsignedAbs() const { + return CheckedNumeric<typename UnsignedOrFloatForSize<T>::type>( + SafeUnsignedAbs(state_.value()), state_.is_valid()); } CheckedNumeric& operator++() { @@ -160,113 +288,223 @@ class CheckedNumeric { return value; } - // These static methods behave like a convenience cast operator targeting - // the desired CheckedNumeric type. As an optimization, a reference is - // returned when Src is the same type as T. + // These perform the actual math operations on the CheckedNumerics. + // Binary arithmetic operations. + template <template <typename, typename, typename> class M, + typename L, + typename R> + static CheckedNumeric MathOp(const L lhs, const R rhs) { + using Math = typename MathWrapper<M, L, R>::math; + T result = 0; + bool is_valid = + Wrapper<L>::is_valid(lhs) && Wrapper<R>::is_valid(rhs) && + Math::Do(Wrapper<L>::value(lhs), Wrapper<R>::value(rhs), &result); + return CheckedNumeric<T>(result, is_valid); + }; + + // Assignment arithmetic operations. + template <template <typename, typename, typename> class M, typename R> + CheckedNumeric& MathOp(const R rhs) { + using Math = typename MathWrapper<M, T, R>::math; + T result = 0; // Using T as the destination saves a range check. + bool is_valid = state_.is_valid() && Wrapper<R>::is_valid(rhs) && + Math::Do(state_.value(), Wrapper<R>::value(rhs), &result); + *this = CheckedNumeric<T>(result, is_valid); + return *this; + }; + + private: + CheckedNumericState<T> state_; + template <typename Src> - static CheckedNumeric<T> cast( - Src u, - typename std::enable_if<std::numeric_limits<Src>::is_specialized, - int>::type = 0) { - return u; - } + constexpr CheckedNumeric(Src value, bool is_valid) + : state_(value, is_valid) {} + // These wrappers allow us to handle state the same way for both + // CheckedNumeric and POD arithmetic types. template <typename Src> - static CheckedNumeric<T> cast( - const CheckedNumeric<Src>& u, - typename std::enable_if<!std::is_same<Src, T>::value, int>::type = 0) { - return u; - } + struct Wrapper { + static constexpr bool is_valid(Src) { return true; } + static constexpr Src value(Src value) { return value; } + }; - static const CheckedNumeric<T>& cast(const CheckedNumeric<T>& u) { return u; } + template <typename Src> + struct Wrapper<CheckedNumeric<Src>> { + static constexpr bool is_valid(const CheckedNumeric<Src> v) { + return v.IsValid(); + } + static constexpr Src value(const CheckedNumeric<Src> v) { + return v.state_.value(); + } + }; - private: - CheckedNumericState<T> state_; + template <typename Src> + struct Wrapper<StrictNumeric<Src>> { + static constexpr bool is_valid(const StrictNumeric<Src>) { return true; } + static constexpr Src value(const StrictNumeric<Src> v) { + return static_cast<Src>(v); + } + }; }; -// This is the boilerplate for the standard arithmetic operator overloads. A -// macro isn't the prettiest solution, but it beats rewriting these five times. -// Some details worth noting are: -// * We apply the standard arithmetic promotions. -// * We skip range checks for floating points. -// * We skip range checks for destination integers with sufficient range. -// TODO(jschuh): extract these out into templates. -#define BASE_NUMERIC_ARITHMETIC_OPERATORS(NAME, OP, COMPOUND_OP) \ - /* Binary arithmetic operator for CheckedNumerics of the same type. */ \ - template <typename T> \ - CheckedNumeric<typename ArithmeticPromotion<T>::type> operator OP( \ - const CheckedNumeric<T>& lhs, const CheckedNumeric<T>& rhs) { \ - typedef typename ArithmeticPromotion<T>::type Promotion; \ - /* Floating point always takes the fast path */ \ - if (std::numeric_limits<T>::is_iec559) \ - return CheckedNumeric<T>(lhs.ValueUnsafe() OP rhs.ValueUnsafe()); \ - if (IsIntegerArithmeticSafe<Promotion, T, T>::value) \ - return CheckedNumeric<Promotion>( \ - lhs.ValueUnsafe() OP rhs.ValueUnsafe(), \ - GetRangeConstraint(rhs.validity() | lhs.validity())); \ - RangeConstraint validity = RANGE_VALID; \ - T result = Checked##NAME(static_cast<Promotion>(lhs.ValueUnsafe()), \ - static_cast<Promotion>(rhs.ValueUnsafe()), \ - &validity); \ - return CheckedNumeric<Promotion>( \ - result, \ - GetRangeConstraint(validity | lhs.validity() | rhs.validity())); \ - } \ - /* Assignment arithmetic operator implementation from CheckedNumeric. */ \ - template <typename T> \ - template <typename Src> \ - CheckedNumeric<T>& CheckedNumeric<T>::operator COMPOUND_OP(Src rhs) { \ - *this = CheckedNumeric<T>::cast(*this) OP CheckedNumeric<Src>::cast(rhs); \ - return *this; \ - } \ - /* Binary arithmetic operator for CheckedNumeric of different type. */ \ - template <typename T, typename Src> \ - CheckedNumeric<typename ArithmeticPromotion<T, Src>::type> operator OP( \ - const CheckedNumeric<Src>& lhs, const CheckedNumeric<T>& rhs) { \ - typedef typename ArithmeticPromotion<T, Src>::type Promotion; \ - if (IsIntegerArithmeticSafe<Promotion, T, Src>::value) \ - return CheckedNumeric<Promotion>( \ - lhs.ValueUnsafe() OP rhs.ValueUnsafe(), \ - GetRangeConstraint(rhs.validity() | lhs.validity())); \ - return CheckedNumeric<Promotion>::cast(lhs) \ - OP CheckedNumeric<Promotion>::cast(rhs); \ - } \ - /* Binary arithmetic operator for left CheckedNumeric and right numeric. */ \ - template <typename T, typename Src> \ - CheckedNumeric<typename ArithmeticPromotion<T, Src>::type> operator OP( \ - const CheckedNumeric<T>& lhs, Src rhs) { \ - typedef typename ArithmeticPromotion<T, Src>::type Promotion; \ - if (IsIntegerArithmeticSafe<Promotion, T, Src>::value) \ - return CheckedNumeric<Promotion>(lhs.ValueUnsafe() OP rhs, \ - lhs.validity()); \ - return CheckedNumeric<Promotion>::cast(lhs) \ - OP CheckedNumeric<Promotion>::cast(rhs); \ - } \ - /* Binary arithmetic operator for right numeric and left CheckedNumeric. */ \ - template <typename T, typename Src> \ - CheckedNumeric<typename ArithmeticPromotion<T, Src>::type> operator OP( \ - Src lhs, const CheckedNumeric<T>& rhs) { \ - typedef typename ArithmeticPromotion<T, Src>::type Promotion; \ - if (IsIntegerArithmeticSafe<Promotion, T, Src>::value) \ - return CheckedNumeric<Promotion>(lhs OP rhs.ValueUnsafe(), \ - rhs.validity()); \ - return CheckedNumeric<Promotion>::cast(lhs) \ - OP CheckedNumeric<Promotion>::cast(rhs); \ - } +// Convenience functions to avoid the ugly template disambiguator syntax. +template <typename Dst, typename Src> +constexpr bool IsValidForType(const CheckedNumeric<Src> value) { + return value.template IsValid<Dst>(); +} + +template <typename Dst, typename Src> +constexpr StrictNumeric<Dst> ValueOrDieForType( + const CheckedNumeric<Src> value) { + return value.template ValueOrDie<Dst>(); +} + +template <typename Dst, typename Src, typename Default> +constexpr StrictNumeric<Dst> ValueOrDefaultForType( + const CheckedNumeric<Src> value, + const Default default_value) { + return value.template ValueOrDefault<Dst>(default_value); +} + +// These variadic templates work out the return types. +// TODO(jschuh): Rip all this out once we have C++14 non-trailing auto support. +template <template <typename, typename, typename> class M, + typename L, + typename R, + typename... Args> +struct ResultType; + +template <template <typename, typename, typename> class M, + typename L, + typename R> +struct ResultType<M, L, R> { + using type = typename MathWrapper<M, L, R>::type; +}; + +template <template <typename, typename, typename> class M, + typename L, + typename R, + typename... Args> +struct ResultType { + using type = + typename ResultType<M, typename ResultType<M, L, R>::type, Args...>::type; +}; + +// Convience wrapper to return a new CheckedNumeric from the provided arithmetic +// or CheckedNumericType. +template <typename T> +constexpr CheckedNumeric<typename UnderlyingType<T>::type> MakeCheckedNum( + const T value) { + return value; +} + +// These implement the variadic wrapper for the math operations. +template <template <typename, typename, typename> class M, + typename L, + typename R> +CheckedNumeric<typename MathWrapper<M, L, R>::type> ChkMathOp(const L lhs, + const R rhs) { + using Math = typename MathWrapper<M, L, R>::math; + return CheckedNumeric<typename Math::result_type>::template MathOp<M>(lhs, + rhs); +} + +// General purpose wrapper template for arithmetic operations. +template <template <typename, typename, typename> class M, + typename L, + typename R, + typename... Args> +CheckedNumeric<typename ResultType<M, L, R, Args...>::type> +ChkMathOp(const L lhs, const R rhs, const Args... args) { + auto tmp = ChkMathOp<M>(lhs, rhs); + return tmp.IsValid() ? ChkMathOp<M>(tmp, args...) + : decltype(ChkMathOp<M>(tmp, args...))(tmp); +}; -BASE_NUMERIC_ARITHMETIC_OPERATORS(Add, +, += ) -BASE_NUMERIC_ARITHMETIC_OPERATORS(Sub, -, -= ) -BASE_NUMERIC_ARITHMETIC_OPERATORS(Mul, *, *= ) -BASE_NUMERIC_ARITHMETIC_OPERATORS(Div, /, /= ) -BASE_NUMERIC_ARITHMETIC_OPERATORS(Mod, %, %= ) +// The following macros are just boilerplate for the standard arithmetic +// operator overloads and variadic function templates. A macro isn't the nicest +// solution, but it beats rewriting these over and over again. +#define BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME) \ + template <typename L, typename R, typename... Args> \ + CheckedNumeric<typename ResultType<Checked##NAME##Op, L, R, Args...>::type> \ + Check##NAME(const L lhs, const R rhs, const Args... args) { \ + return ChkMathOp<Checked##NAME##Op, L, R, Args...>(lhs, rhs, args...); \ + } +#define BASE_NUMERIC_ARITHMETIC_OPERATORS(NAME, OP, COMPOUND_OP) \ + /* Binary arithmetic operator for all CheckedNumeric operations. */ \ + template <typename L, typename R, \ + typename std::enable_if<IsCheckedOp<L, R>::value>::type* = \ + nullptr> \ + CheckedNumeric<typename MathWrapper<Checked##NAME##Op, L, R>::type> \ + operator OP(const L lhs, const R rhs) { \ + return decltype(lhs OP rhs)::template MathOp<Checked##NAME##Op>(lhs, rhs); \ + } \ + /* Assignment arithmetic operator implementation from CheckedNumeric. */ \ + template <typename L> \ + template <typename R> \ + CheckedNumeric<L>& CheckedNumeric<L>::operator COMPOUND_OP(const R rhs) { \ + return MathOp<Checked##NAME##Op>(rhs); \ + } \ + /* Variadic arithmetic functions that return CheckedNumeric. */ \ + BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME) + +BASE_NUMERIC_ARITHMETIC_OPERATORS(Add, +, +=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Sub, -, -=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Mul, *, *=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Div, /, /=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Mod, %, %=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Lsh, <<, <<=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Rsh, >>, >>=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(And, &, &=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Or, |, |=) +BASE_NUMERIC_ARITHMETIC_OPERATORS(Xor, ^, ^=) +BASE_NUMERIC_ARITHMETIC_VARIADIC(Max) +BASE_NUMERIC_ARITHMETIC_VARIADIC(Min) + +#undef BASE_NUMERIC_ARITHMETIC_VARIADIC #undef BASE_NUMERIC_ARITHMETIC_OPERATORS +// These are some extra StrictNumeric operators to support simple pointer +// arithmetic with our result types. Since wrapping on a pointer is always +// bad, we trigger the CHECK condition here. +template <typename L, typename R> +L* operator+(L* lhs, const StrictNumeric<R> rhs) { + uintptr_t result = CheckAdd(reinterpret_cast<uintptr_t>(lhs), + CheckMul(sizeof(L), static_cast<R>(rhs))) + .template ValueOrDie<uintptr_t>(); + return reinterpret_cast<L*>(result); +} + +template <typename L, typename R> +L* operator-(L* lhs, const StrictNumeric<R> rhs) { + uintptr_t result = CheckSub(reinterpret_cast<uintptr_t>(lhs), + CheckMul(sizeof(L), static_cast<R>(rhs))) + .template ValueOrDie<uintptr_t>(); + return reinterpret_cast<L*>(result); +} + } // namespace internal using internal::CheckedNumeric; +using internal::IsValidForType; +using internal::ValueOrDieForType; +using internal::ValueOrDefaultForType; +using internal::MakeCheckedNum; +using internal::CheckMax; +using internal::CheckMin; +using internal::CheckAdd; +using internal::CheckSub; +using internal::CheckMul; +using internal::CheckDiv; +using internal::CheckMod; +using internal::CheckLsh; +using internal::CheckRsh; +using internal::CheckAnd; +using internal::CheckOr; +using internal::CheckXor; } // namespace base } // namespace pdfium -#endif // PDFIUM_THIRD_PARTY_BASE_SAFE_MATH_H_ +#endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_ 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 |