From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- .../chromium/base/numerics/checked_math_impl.h | 567 +++++++++++++++++++++ 1 file changed, 567 insertions(+) create mode 100644 security/sandbox/chromium/base/numerics/checked_math_impl.h (limited to 'security/sandbox/chromium/base/numerics/checked_math_impl.h') diff --git a/security/sandbox/chromium/base/numerics/checked_math_impl.h b/security/sandbox/chromium/base/numerics/checked_math_impl.h new file mode 100644 index 0000000000..e083389ebf --- /dev/null +++ b/security/sandbox/chromium/base/numerics/checked_math_impl.h @@ -0,0 +1,567 @@ +// Copyright 2017 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef BASE_NUMERICS_CHECKED_MATH_IMPL_H_ +#define BASE_NUMERICS_CHECKED_MATH_IMPL_H_ + +#include +#include + +#include +#include +#include +#include +#include + +#include "base/numerics/safe_conversions.h" +#include "base/numerics/safe_math_shared_impl.h" + +namespace base { +namespace internal { + +template +constexpr bool CheckedAddImpl(T x, T y, T* result) { + static_assert(std::is_integral::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. + using UnsignedDst = typename std::make_unsigned::type; + using SignedDst = typename std::make_signed::type; + UnsignedDst ux = static_cast(x); + UnsignedDst uy = static_cast(y); + UnsignedDst uresult = static_cast(ux + uy); + *result = static_cast(uresult); + // Addition is valid if the sign of (x + y) is equal to either that of x or + // that of y. + return (std::is_signed::value) + ? static_cast((uresult ^ ux) & (uresult ^ uy)) >= 0 + : uresult >= uy; // Unsigned is either valid or underflow. +} + +template +struct CheckedAddOp {}; + +template +struct CheckedAddOp::value && + std::is_integral::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + // TODO(jschuh) Make this "constexpr if" once we're C++17. + if (CheckedAddFastOp::is_supported) + return CheckedAddFastOp::Do(x, y, result); + + // Double the underlying type up to a full machine word. + using FastPromotion = typename FastIntegerArithmeticPromotion::type; + using Promotion = + typename std::conditional<(IntegerBitsPlusSign::value > + IntegerBitsPlusSign::value), + typename BigEnoughPromotion::type, + FastPromotion>::type; + // 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. + if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType(x) || + !IsValueInRangeForNumericType(y))) { + return false; + } + + Promotion presult = {}; + bool is_valid = true; + if (IsIntegerArithmeticSafe::value) { + presult = static_cast(x) + static_cast(y); + } else { + is_valid = CheckedAddImpl(static_cast(x), + static_cast(y), &presult); + } + *result = static_cast(presult); + return is_valid && IsValueInRangeForNumericType(presult); + } +}; + +template +constexpr bool CheckedSubImpl(T x, T y, T* result) { + static_assert(std::is_integral::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. + using UnsignedDst = typename std::make_unsigned::type; + using SignedDst = typename std::make_signed::type; + UnsignedDst ux = static_cast(x); + UnsignedDst uy = static_cast(y); + UnsignedDst uresult = static_cast(ux - uy); + *result = static_cast(uresult); + // Subtraction is valid if either x and y have same sign, or (x-y) and x have + // the same sign. + return (std::is_signed::value) + ? static_cast((uresult ^ ux) & (ux ^ uy)) >= 0 + : x >= y; +} + +template +struct CheckedSubOp {}; + +template +struct CheckedSubOp::value && + std::is_integral::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + // TODO(jschuh) Make this "constexpr if" once we're C++17. + if (CheckedSubFastOp::is_supported) + return CheckedSubFastOp::Do(x, y, result); + + // Double the underlying type up to a full machine word. + using FastPromotion = typename FastIntegerArithmeticPromotion::type; + using Promotion = + typename std::conditional<(IntegerBitsPlusSign::value > + IntegerBitsPlusSign::value), + typename BigEnoughPromotion::type, + FastPromotion>::type; + // 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. + if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType(x) || + !IsValueInRangeForNumericType(y))) { + return false; + } + + Promotion presult = {}; + bool is_valid = true; + if (IsIntegerArithmeticSafe::value) { + presult = static_cast(x) - static_cast(y); + } else { + is_valid = CheckedSubImpl(static_cast(x), + static_cast(y), &presult); + } + *result = static_cast(presult); + return is_valid && IsValueInRangeForNumericType(presult); + } +}; + +template +constexpr bool CheckedMulImpl(T x, T y, T* result) { + static_assert(std::is_integral::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::type; + using SignedDst = typename std::make_signed::type; + const UnsignedDst ux = SafeUnsignedAbs(x); + const UnsignedDst uy = SafeUnsignedAbs(y); + UnsignedDst uresult = static_cast(ux * uy); + const bool is_negative = + std::is_signed::value && static_cast(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::value || is_negative) || + ux <= (std::numeric_limits::max() + UnsignedDst(is_negative)) / uy; +} + +template +struct CheckedMulOp {}; + +template +struct CheckedMulOp::value && + std::is_integral::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + // TODO(jschuh) Make this "constexpr if" once we're C++17. + if (CheckedMulFastOp::is_supported) + return CheckedMulFastOp::Do(x, y, result); + + using Promotion = typename FastIntegerArithmeticPromotion::type; + // Verify the destination type can hold the result (always true for 0). + if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType(x) || + !IsValueInRangeForNumericType(y)) && + x && y)) { + return false; + } + + Promotion presult = {}; + bool is_valid = true; + if (CheckedMulFastOp::is_supported) { + // The fast op may be available with the promoted type. + is_valid = CheckedMulFastOp::Do(x, y, &presult); + } else if (IsIntegerArithmeticSafe::value) { + presult = static_cast(x) * static_cast(y); + } else { + is_valid = CheckedMulImpl(static_cast(x), + static_cast(y), &presult); + } + *result = static_cast(presult); + return is_valid && IsValueInRangeForNumericType(presult); + } +}; + +// Division just requires a check for a zero denominator or an invalid negation +// on signed min/-1. +template +struct CheckedDivOp {}; + +template +struct CheckedDivOp::value && + std::is_integral::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + if (BASE_NUMERICS_UNLIKELY(!y)) + return false; + + // The overflow check can be compiled away if we don't have the exact + // combination of types needed to trigger this case. + using Promotion = typename BigEnoughPromotion::type; + if (BASE_NUMERICS_UNLIKELY( + (std::is_signed::value && std::is_signed::value && + IsTypeInRangeForNumericType::value && + static_cast(x) == + std::numeric_limits::lowest() && + y == static_cast(-1)))) { + return false; + } + + // This branch always compiles away if the above branch wasn't removed. + if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType(x) || + !IsValueInRangeForNumericType(y)) && + x)) { + return false; + } + + Promotion presult = Promotion(x) / Promotion(y); + *result = static_cast(presult); + return IsValueInRangeForNumericType(presult); + } +}; + +template +struct CheckedModOp {}; + +template +struct CheckedModOp::value && + std::is_integral::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + using Promotion = typename BigEnoughPromotion::type; + if (BASE_NUMERICS_LIKELY(y)) { + Promotion presult = static_cast(x) % static_cast(y); + *result = static_cast(presult); + return IsValueInRangeForNumericType(presult); + } + return false; + } +}; + +template +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 +struct CheckedLshOp::value && + std::is_integral::value>::type> { + using result_type = T; + template + static constexpr bool Do(T x, U shift, V* result) { + // Disallow negative numbers and verify the shift is in bounds. + if (BASE_NUMERICS_LIKELY(!IsValueNegative(x) && + as_unsigned(shift) < + as_unsigned(std::numeric_limits::digits))) { + // Shift as unsigned to avoid undefined behavior. + *result = static_cast(as_unsigned(x) << shift); + // If the shift can be reversed, we know it was valid. + return *result >> shift == x; + } + + // Handle the legal corner-case of a full-width signed shift of zero. + return std::is_signed::value && !x && + as_unsigned(shift) == as_unsigned(std::numeric_limits::digits); + } +}; + +template +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 +struct CheckedRshOp::value && + std::is_integral::value>::type> { + using result_type = T; + template + static bool Do(T x, U shift, V* result) { + // Use the type conversion push negative values out of range. + if (BASE_NUMERICS_LIKELY(as_unsigned(shift) < + IntegerBitsPlusSign::value)) { + T tmp = x >> shift; + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } + return false; + } +}; + +template +struct CheckedAndOp {}; + +// For simplicity we support only unsigned integer results. +template +struct CheckedAndOp::value && + std::is_integral::value>::type> { + using result_type = typename std::make_unsigned< + typename MaxExponentPromotion::type>::type; + template + static constexpr bool Do(T x, U y, V* result) { + result_type tmp = static_cast(x) & static_cast(y); + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } +}; + +template +struct CheckedOrOp {}; + +// For simplicity we support only unsigned integers. +template +struct CheckedOrOp::value && + std::is_integral::value>::type> { + using result_type = typename std::make_unsigned< + typename MaxExponentPromotion::type>::type; + template + static constexpr bool Do(T x, U y, V* result) { + result_type tmp = static_cast(x) | static_cast(y); + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } +}; + +template +struct CheckedXorOp {}; + +// For simplicity we support only unsigned integers. +template +struct CheckedXorOp::value && + std::is_integral::value>::type> { + using result_type = typename std::make_unsigned< + typename MaxExponentPromotion::type>::type; + template + static constexpr bool Do(T x, U y, V* result) { + result_type tmp = static_cast(x) ^ static_cast(y); + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } +}; + +// 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 +struct CheckedMaxOp {}; + +template +struct CheckedMaxOp< + T, + U, + typename std::enable_if::value && + std::is_arithmetic::value>::type> { + using result_type = typename MaxExponentPromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + result_type tmp = IsGreater::Test(x, y) ? static_cast(x) + : static_cast(y); + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } +}; + +// 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 +struct CheckedMinOp {}; + +template +struct CheckedMinOp< + T, + U, + typename std::enable_if::value && + std::is_arithmetic::value>::type> { + using result_type = typename LowestValuePromotion::type; + template + static constexpr bool Do(T x, U y, V* result) { + result_type tmp = IsLess::Test(x, y) ? static_cast(x) + : static_cast(y); + *result = static_cast(tmp); + return IsValueInRangeForNumericType(tmp); + } +}; + +// 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 \ + struct Checked##NAME##Op< \ + T, U, \ + typename std::enable_if::value || \ + std::is_floating_point::value>::type> { \ + using result_type = typename MaxExponentPromotion::type; \ + template \ + static constexpr bool Do(T x, U y, V* result) { \ + using Promotion = typename MaxExponentPromotion::type; \ + Promotion presult = x OP y; \ + *result = static_cast(presult); \ + return IsValueInRangeForNumericType(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 + +// 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::is_integral::value + ? NUMERIC_INTEGER + : (std::is_floating_point::value ? NUMERIC_FLOATING + : NUMERIC_UNKNOWN); +}; + +template ::value> +class CheckedNumericState {}; + +// Integrals require quite a bit of additional housekeeping to manage state. +template +class CheckedNumericState { + 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_; + + // Ensures that a type conversion does not trigger undefined behavior. + template + static constexpr T WellDefinedConversionOrZero(const Src value, + const bool is_valid) { + using SrcType = typename internal::UnderlyingType::type; + return (std::is_integral::value || is_valid) + ? static_cast(value) + : static_cast(0); + } + + public: + template + friend class CheckedNumericState; + + constexpr CheckedNumericState() : is_valid_(true), value_(0) {} + + template + constexpr CheckedNumericState(Src value, bool is_valid) + : is_valid_(is_valid && IsValueInRangeForNumericType(value)), + value_(WellDefinedConversionOrZero(value, is_valid_)) { + static_assert(std::is_arithmetic::value, "Argument must be numeric."); + } + + // Copy constructor. + template + constexpr CheckedNumericState(const CheckedNumericState& rhs) + : is_valid_(rhs.IsValid()), + value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {} + + template + constexpr explicit CheckedNumericState(Src value) + : is_valid_(IsValueInRangeForNumericType(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. +template +class CheckedNumericState { + private: + T value_; + + // Ensures that a type conversion does not trigger undefined behavior. + template + static constexpr T WellDefinedConversionOrNaN(const Src value, + const bool is_valid) { + using SrcType = typename internal::UnderlyingType::type; + return (StaticDstRangeRelationToSrcRange::value == + NUMERIC_RANGE_CONTAINED || + is_valid) + ? static_cast(value) + : std::numeric_limits::quiet_NaN(); + } + + public: + template + friend class CheckedNumericState; + + constexpr CheckedNumericState() : value_(0.0) {} + + template + constexpr CheckedNumericState(Src value, bool is_valid) + : value_(WellDefinedConversionOrNaN(value, is_valid)) {} + + template + constexpr explicit CheckedNumericState(Src value) + : value_(WellDefinedConversionOrNaN( + value, + IsValueInRangeForNumericType(value))) {} + + // Copy constructor. + template + constexpr CheckedNumericState(const CheckedNumericState& rhs) + : value_(WellDefinedConversionOrNaN( + rhs.value(), + rhs.is_valid() && IsValueInRangeForNumericType(rhs.value()))) {} + + constexpr bool is_valid() const { + // Written this way because std::isfinite is not reliably constexpr. + return MustTreatAsConstexpr(value_) + ? value_ <= std::numeric_limits::max() && + value_ >= std::numeric_limits::lowest() + : std::isfinite(value_); + } + constexpr T value() const { return value_; } +}; + +} // namespace internal +} // namespace base + +#endif // BASE_NUMERICS_CHECKED_MATH_IMPL_H_ -- cgit v1.2.3