From d9713f05fdcecab8428d39034c6b84cd0bbd2920 Mon Sep 17 00:00:00 2001 From: Chris Palmer Date: Fri, 20 Jun 2014 16:30:49 -0700 Subject: Import Chromium base/numerics to resolve integer overflow. We'll use this for integer overflows going forward. BUG=382606 R=bo_xu@foxitsoftware.com, jschuh@chromium.org Review URL: https://codereview.chromium.org/341533007 --- third_party/numerics/safe_math_impl.h | 502 ++++++++++++++++++++++++++++++++++ 1 file changed, 502 insertions(+) create mode 100644 third_party/numerics/safe_math_impl.h (limited to 'third_party/numerics/safe_math_impl.h') diff --git a/third_party/numerics/safe_math_impl.h b/third_party/numerics/safe_math_impl.h new file mode 100644 index 0000000000..4bf59e64e0 --- /dev/null +++ b/third_party/numerics/safe_math_impl.h @@ -0,0 +1,502 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef SAFE_MATH_IMPL_H_ +#define SAFE_MATH_IMPL_H_ + +#include + +#include +#include +#include + +#include "../macros.h" +#include "../template_util.h" +#include "safe_conversions.h" + +namespace base { +namespace internal { + +// Everything from here up to the floating point operations is portable C++, +// 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 +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 +struct UnsignedIntegerForSize { + typedef typename enable_if< + std::numeric_limits::is_integer, + typename IntegerForSizeAndSign::type>::type type; +}; + +template +struct SignedIntegerForSize { + typedef typename enable_if< + std::numeric_limits::is_integer, + typename IntegerForSizeAndSign::type>::type type; +}; + +template +struct TwiceWiderInteger { + typedef typename enable_if< + std::numeric_limits::is_integer, + typename IntegerForSizeAndSign< + sizeof(Integer) * 2, + std::numeric_limits::is_signed>::type>::type type; +}; + +template +struct PositionOfSignBit { + static const typename enable_if::is_integer, + size_t>::type value = 8 * sizeof(Integer) - 1; +}; + +// Helper templates for integer manipulations. + +template +bool HasSignBit(T x) { + // Cast to unsigned since right shift on signed is undefined. + return !!(static_cast::type>(x) >> + PositionOfSignBit::value); +} + +// This wrapper undoes the standard integer promotions. +template +T BinaryComplement(T x) { + return ~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. + +template +typename enable_if::is_integer, T>::type +CheckedAdd(T x, T y, RangeConstraint* validity) { + // 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::type UnsignedDst; + UnsignedDst ux = static_cast(x); + UnsignedDst uy = static_cast(y); + UnsignedDst uresult = ux + uy; + // Addition is valid if the sign of (x + y) is equal to either that of x or + // that of y. + if (std::numeric_limits::is_signed) { + if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy)))) + *validity = RANGE_VALID; + else // Direction of wrap is inverse of result sign. + *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; + + } else { // Unsigned is either valid or overflow. + *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW; + } + return static_cast(uresult); +} + +template +typename enable_if::is_integer, T>::type +CheckedSub(T x, T y, RangeConstraint* validity) { + // 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::type UnsignedDst; + UnsignedDst ux = static_cast(x); + UnsignedDst uy = static_cast(y); + UnsignedDst uresult = ux - uy; + // Subtraction is valid if either x and y have same sign, or (x-y) and x have + // the same sign. + if (std::numeric_limits::is_signed) { + if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy)))) + *validity = RANGE_VALID; + else // Direction of wrap is inverse of result sign. + *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; + + } else { // Unsigned is either valid or underflow. + *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW; + } + return static_cast(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 enable_if< + std::numeric_limits::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t), + T>::type +CheckedMul(T x, T y, RangeConstraint* validity) { + typedef typename TwiceWiderInteger::type IntermediateType; + IntermediateType tmp = + static_cast(x) * static_cast(y); + *validity = DstRangeRelationToSrcRange(tmp); + return static_cast(tmp); +} + +template +typename enable_if::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)) { + return RANGE_VALID; + + } else if (x > 0) { + if (y > 0) + *validity = + x <= std::numeric_limits::max() / y ? RANGE_VALID : RANGE_OVERFLOW; + else + *validity = y >= std::numeric_limits::min() / x ? RANGE_VALID + : RANGE_UNDERFLOW; + + } else { + if (y > 0) + *validity = x >= std::numeric_limits::min() / y ? RANGE_VALID + : RANGE_UNDERFLOW; + else + *validity = + y >= std::numeric_limits::max() / x ? RANGE_VALID : RANGE_OVERFLOW; + } + + return x * y; +} + +template +typename enable_if::is_integer && + !std::numeric_limits::is_signed && + (sizeof(T) * 2 > sizeof(uintmax_t)), + T>::type +CheckedMul(T x, T y, RangeConstraint* validity) { + *validity = (y == 0 || x <= std::numeric_limits::max() / y) + ? RANGE_VALID + : RANGE_OVERFLOW; + return x * y; +} + +// Division just requires a check for an invalid negation on signed min/-1. +template +T CheckedDiv( + T x, + T y, + RangeConstraint* validity, + typename enable_if::is_integer, int>::type = 0) { + if (std::numeric_limits::is_signed && x == std::numeric_limits::min() && + y == static_cast(-1)) { + *validity = RANGE_OVERFLOW; + return std::numeric_limits::min(); + } + + *validity = RANGE_VALID; + return x / y; +} + +template +typename enable_if< + std::numeric_limits::is_integer&& std::numeric_limits::is_signed, + T>::type +CheckedMod(T x, T y, RangeConstraint* validity) { + *validity = y > 0 ? RANGE_VALID : RANGE_INVALID; + return x % y; +} + +template +typename enable_if< + std::numeric_limits::is_integer && !std::numeric_limits::is_signed, + T>::type +CheckedMod(T x, T y, RangeConstraint* validity) { + *validity = RANGE_VALID; + return x % y; +} + +template +typename enable_if< + std::numeric_limits::is_integer&& std::numeric_limits::is_signed, + T>::type +CheckedNeg(T value, RangeConstraint* validity) { + *validity = + value != std::numeric_limits::min() ? RANGE_VALID : RANGE_OVERFLOW; + // The negation of signed min is min, so catch that one. + return -value; +} + +template +typename enable_if< + std::numeric_limits::is_integer && !std::numeric_limits::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( + -static_cast::type>(value)); +} + +template +typename enable_if< + std::numeric_limits::is_integer&& std::numeric_limits::is_signed, + T>::type +CheckedAbs(T value, RangeConstraint* validity) { + *validity = + value != std::numeric_limits::min() ? RANGE_VALID : RANGE_OVERFLOW; + return std::abs(value); +} + +template +typename enable_if< + std::numeric_limits::is_integer && !std::numeric_limits::is_signed, + T>::type +CheckedAbs(T value, RangeConstraint* validity) { + // Absolute value of a positive is just its identiy. + *validity = RANGE_VALID; + return value; +} + +// 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 enable_if::is_iec559, T>::type \ + Checked##NAME(T, T, RangeConstraint*) { \ + NOTREACHED(); \ + return 0; \ + } + +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) + +#undef BASE_FLOAT_ARITHMETIC_STUBS + +template +typename enable_if::is_iec559, T>::type CheckedNeg( + T value, + RangeConstraint*) { + return -value; +} + +template +typename enable_if::is_iec559, T>::type CheckedAbs( + T value, + RangeConstraint*) { + return std::abs(value); +} + +// Floats carry around their validity state with them, but integers do not. So, +// we wrap the underlying value in a specialization in order to hide that detail +// and expose an interface via accessors. +enum NumericRepresentation { + NUMERIC_INTEGER, + NUMERIC_FLOATING, + NUMERIC_UNKNOWN +}; + +template +struct GetNumericRepresentation { + static const NumericRepresentation value = + std::numeric_limits::is_integer + ? NUMERIC_INTEGER + : (std::numeric_limits::is_iec559 ? NUMERIC_FLOATING + : NUMERIC_UNKNOWN); +}; + +template ::value> +class CheckedNumericState {}; + +// Integrals require quite a bit of additional housekeeping to manage state. +template +class CheckedNumericState { + private: + T value_; + RangeConstraint validity_; + + public: + template + friend class CheckedNumericState; + + CheckedNumericState() : value_(0), validity_(RANGE_VALID) {} + + template + CheckedNumericState(Src value, RangeConstraint validity) + : value_(value), + validity_(GetRangeConstraint(validity | + DstRangeRelationToSrcRange(value))) { + COMPILE_ASSERT(std::numeric_limits::is_specialized, + argument_must_be_numeric); + } + + // Copy constructor. + template + CheckedNumericState(const CheckedNumericState& rhs) + : value_(static_cast(rhs.value())), + validity_(GetRangeConstraint( + rhs.validity() | DstRangeRelationToSrcRange(rhs.value()))) {} + + template + explicit CheckedNumericState( + Src value, + typename enable_if::is_specialized, int>::type = + 0) + : value_(static_cast(value)), + validity_(DstRangeRelationToSrcRange(value)) {} + + RangeConstraint validity() const { return validity_; } + T value() const { return value_; } +}; + +// Floating points maintain their own validity, but need translation wrappers. +template +class CheckedNumericState { + private: + T value_; + + public: + template + friend class CheckedNumericState; + + CheckedNumericState() : value_(0.0) {} + + template + CheckedNumericState( + Src value, + RangeConstraint validity, + typename enable_if::is_integer, int>::type = 0) { + switch (DstRangeRelationToSrcRange(value)) { + case RANGE_VALID: + value_ = static_cast(value); + break; + + case RANGE_UNDERFLOW: + value_ = -std::numeric_limits::infinity(); + break; + + case RANGE_OVERFLOW: + value_ = std::numeric_limits::infinity(); + break; + + case RANGE_INVALID: + value_ = std::numeric_limits::quiet_NaN(); + break; + + default: + NOTREACHED(); + } + } + + template + explicit CheckedNumericState( + Src value, + typename enable_if::is_specialized, int>::type = + 0) + : value_(static_cast(value)) {} + + // Copy constructor. + template + CheckedNumericState(const CheckedNumericState& rhs) + : value_(static_cast(rhs.value())) {} + + RangeConstraint validity() const { + return GetRangeConstraint(value_ <= std::numeric_limits::max(), + value_ >= -std::numeric_limits::max()); + } + T value() const { return value_; } +}; + +// For integers less than 128-bit and floats 32-bit or larger, we can distil +// C/C++ arithmetic promotions down to two simple rules: +// 1. The type with the larger maximum exponent always takes precedence. +// 2. The resulting type must be promoted to at least an int. +// The following template specializations implement that promotion logic. +enum ArithmeticPromotionCategory { + LEFT_PROMOTION, + RIGHT_PROMOTION, + DEFAULT_PROMOTION +}; + +template ::value > MaxExponent::value) + ? (MaxExponent::value > MaxExponent::value + ? LEFT_PROMOTION + : DEFAULT_PROMOTION) + : (MaxExponent::value > MaxExponent::value + ? RIGHT_PROMOTION + : DEFAULT_PROMOTION) > +struct ArithmeticPromotion; + +template +struct ArithmeticPromotion { + typedef Lhs type; +}; + +template +struct ArithmeticPromotion { + typedef Rhs type; +}; + +template +struct ArithmeticPromotion { + typedef int type; +}; + +// We can statically check if operations on the provided types can wrap, so we +// can skip the checked operations if they're not needed. So, for an integer we +// care if the destination type preserves the sign and is twice the width of +// the source. +template +struct IsIntegerArithmeticSafe { + static const bool value = !std::numeric_limits::is_iec559 && + StaticDstRangeRelationToSrcRange::value == + NUMERIC_RANGE_CONTAINED && + sizeof(T) >= (2 * sizeof(Lhs)) && + StaticDstRangeRelationToSrcRange::value != + NUMERIC_RANGE_CONTAINED && + sizeof(T) >= (2 * sizeof(Rhs)); +}; + +} // namespace internal +} // namespace base + +#endif // SAFE_MATH_IMPL_H_ -- cgit v1.2.3