diff options
author | tsepez <tsepez@chromium.org> | 2017-01-23 14:36:20 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2017-01-23 14:36:20 -0800 |
commit | 4022f87eb8716155291543efaaf289e51d7cbf43 (patch) | |
tree | 28e2a3b99367932ee84a92b1f6c913245e62afb1 /third_party | |
parent | b76f49b36baffea2b2ecb90d67c7b6bb734e7bb9 (diff) | |
download | pdfium-4022f87eb8716155291543efaaf289e51d7cbf43.tar.xz |
Update safe numerics package to get bitwise ops
Fix callers conventions to avoid ambiguity.
Fix bad bounds check unmasked by change.
Directly include headers no longer pulled in by numerics itself.
Review-Url: https://codereview.chromium.org/2640143003
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 |