LCOV - code coverage report
Current view: top level - src/base - safe_math_impl.h (source / functions) Hit Total Coverage
Test: app.info Lines: 16 27 59.3 %
Date: 2019-03-21 Functions: 1 1 100.0 %

          Line data    Source code
       1             : // Copyright 2014 The Chromium Authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : // Slightly adapted for inclusion in V8.
       6             : // Copyright 2014 the V8 project authors. All rights reserved.
       7             : 
       8             : #ifndef V8_BASE_SAFE_MATH_IMPL_H_
       9             : #define V8_BASE_SAFE_MATH_IMPL_H_
      10             : 
      11             : #include <stdint.h>
      12             : 
      13             : #include <cmath>
      14             : #include <cstdlib>
      15             : #include <limits>
      16             : 
      17             : #include "src/base/macros.h"
      18             : #include "src/base/safe_conversions.h"
      19             : 
      20             : namespace v8 {
      21             : namespace base {
      22             : namespace internal {
      23             : 
      24             : 
      25             : // From Chromium's base/template_util.h:
      26             : 
      27             : template<class T, T v>
      28             : struct integral_constant {
      29             :   static const T value = v;
      30             :   typedef T value_type;
      31             :   typedef integral_constant<T, v> type;
      32             : };
      33             : 
      34             : template <class T, T v> const T integral_constant<T, v>::value;
      35             : 
      36             : typedef integral_constant<bool, true> true_type;
      37             : typedef integral_constant<bool, false> false_type;
      38             : 
      39             : template <class T, class U> struct is_same : public false_type {};
      40             : template <class T> struct is_same<T, T> : true_type {};
      41             : 
      42             : template<bool B, class T = void>
      43             : struct enable_if {};
      44             : 
      45             : template<class T>
      46             : struct enable_if<true, T> { typedef T type; };
      47             : 
      48             : // </template_util.h>
      49             : 
      50             : 
      51             : // Everything from here up to the floating point operations is portable C++,
      52             : // but it may not be fast. This code could be split based on
      53             : // platform/architecture and replaced with potentially faster implementations.
      54             : 
      55             : // Integer promotion templates used by the portable checked integer arithmetic.
      56             : template <size_t Size, bool IsSigned>
      57             : struct IntegerForSizeAndSign;
      58             : template <>
      59             : struct IntegerForSizeAndSign<1, true> {
      60             :   typedef int8_t type;
      61             : };
      62             : template <>
      63             : struct IntegerForSizeAndSign<1, false> {
      64             :   typedef uint8_t type;
      65             : };
      66             : template <>
      67             : struct IntegerForSizeAndSign<2, true> {
      68             :   typedef int16_t type;
      69             : };
      70             : template <>
      71             : struct IntegerForSizeAndSign<2, false> {
      72             :   typedef uint16_t type;
      73             : };
      74             : template <>
      75             : struct IntegerForSizeAndSign<4, true> {
      76             :   typedef int32_t type;
      77             : };
      78             : template <>
      79             : struct IntegerForSizeAndSign<4, false> {
      80             :   typedef uint32_t type;
      81             : };
      82             : template <>
      83             : struct IntegerForSizeAndSign<8, true> {
      84             :   typedef int64_t type;
      85             : };
      86             : template <>
      87             : struct IntegerForSizeAndSign<8, false> {
      88             :   typedef uint64_t type;
      89             : };
      90             : 
      91             : // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
      92             : // support 128-bit math, then the ArithmeticPromotion template below will need
      93             : // to be updated (or more likely replaced with a decltype expression).
      94             : 
      95             : template <typename Integer>
      96             : struct UnsignedIntegerForSize {
      97             :   typedef typename enable_if<
      98             :       std::numeric_limits<Integer>::is_integer,
      99             :       typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
     100             : };
     101             : 
     102             : template <typename Integer>
     103             : struct SignedIntegerForSize {
     104             :   typedef typename enable_if<
     105             :       std::numeric_limits<Integer>::is_integer,
     106             :       typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
     107             : };
     108             : 
     109             : template <typename Integer>
     110             : struct TwiceWiderInteger {
     111             :   typedef typename enable_if<
     112             :       std::numeric_limits<Integer>::is_integer,
     113             :       typename IntegerForSizeAndSign<
     114             :           sizeof(Integer) * 2,
     115             :           std::numeric_limits<Integer>::is_signed>::type>::type type;
     116             : };
     117             : 
     118             : template <typename Integer>
     119             : struct PositionOfSignBit {
     120             :   static const typename enable_if<std::numeric_limits<Integer>::is_integer,
     121             :                                   size_t>::type value = 8 * sizeof(Integer) - 1;
     122             : };
     123             : 
     124             : // Helper templates for integer manipulations.
     125             : 
     126             : template <typename T>
     127             : bool HasSignBit(T x) {
     128             :   // Cast to unsigned since right shift on signed is undefined.
     129    45619154 :   return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
     130             :             PositionOfSignBit<T>::value);
     131             : }
     132             : 
     133             : // This wrapper undoes the standard integer promotions.
     134             : template <typename T>
     135             : T BinaryComplement(T x) {
     136    45619154 :   return ~x;
     137             : }
     138             : 
     139             : // Here are the actual portable checked integer math implementations.
     140             : // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
     141             : // way to coalesce things into the CheckedNumericState specializations below.
     142             : 
     143             : template <typename T>
     144             : typename enable_if<std::numeric_limits<T>::is_integer, T>::type
     145             : CheckedAdd(T x, T y, RangeConstraint* validity) {
     146             :   // Since the value of x+y is undefined if we have a signed type, we compute
     147             :   // it using the unsigned type of the same size.
     148             :   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
     149    45619154 :   UnsignedDst ux = static_cast<UnsignedDst>(x);
     150    45619154 :   UnsignedDst uy = static_cast<UnsignedDst>(y);
     151    45619154 :   UnsignedDst uresult = ux + uy;
     152             :   // Addition is valid if the sign of (x + y) is equal to either that of x or
     153             :   // that of y.
     154             :   if (std::numeric_limits<T>::is_signed) {
     155    91238308 :     if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
     156             :       *validity = RANGE_VALID;
     157             :     else  // Direction of wrap is inverse of result sign.
     158           0 :       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
     159             : 
     160             :   } else {  // Unsigned is either valid or overflow.
     161             :     *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
     162             :   }
     163    45619154 :   return static_cast<T>(uresult);
     164             : }
     165             : 
     166             : template <typename T>
     167             : typename enable_if<std::numeric_limits<T>::is_integer, T>::type
     168             : CheckedSub(T x, T y, RangeConstraint* validity) {
     169             :   // Since the value of x+y is undefined if we have a signed type, we compute
     170             :   // it using the unsigned type of the same size.
     171             :   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
     172           0 :   UnsignedDst ux = static_cast<UnsignedDst>(x);
     173           0 :   UnsignedDst uy = static_cast<UnsignedDst>(y);
     174           0 :   UnsignedDst uresult = ux - uy;
     175             :   // Subtraction is valid if either x and y have same sign, or (x-y) and x have
     176             :   // the same sign.
     177             :   if (std::numeric_limits<T>::is_signed) {
     178           0 :     if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
     179             :       *validity = RANGE_VALID;
     180             :     else  // Direction of wrap is inverse of result sign.
     181           0 :       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
     182             : 
     183             :   } else {  // Unsigned is either valid or underflow.
     184             :     *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
     185             :   }
     186           0 :   return static_cast<T>(uresult);
     187             : }
     188             : 
     189             : // Integer multiplication is a bit complicated. In the fast case we just
     190             : // we just promote to a twice wider type, and range check the result. In the
     191             : // slow case we need to manually check that the result won't be truncated by
     192             : // checking with division against the appropriate bound.
     193             : template <typename T>
     194             : typename enable_if<
     195             :     std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
     196             :     T>::type
     197             : CheckedMul(T x, T y, RangeConstraint* validity) {
     198             :   typedef typename TwiceWiderInteger<T>::type IntermediateType;
     199             :   IntermediateType tmp =
     200       97590 :       static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
     201             :   *validity = DstRangeRelationToSrcRange<T>(tmp);
     202       97590 :   return static_cast<T>(tmp);
     203             : }
     204             : 
     205             : template <typename T>
     206             : typename enable_if<std::numeric_limits<T>::is_integer &&
     207             :                        std::numeric_limits<T>::is_signed &&
     208             :                        (sizeof(T) * 2 > sizeof(uintmax_t)),
     209             :                    T>::type
     210    45477804 : CheckedMul(T x, T y, RangeConstraint* validity) {
     211             :   // If either side is zero then the result will be zero.
     212    45477804 :   if (!x || !y) {
     213             :     return RANGE_VALID;
     214             : 
     215    45475804 :   } else if (x > 0) {
     216    45475804 :     if (y > 0)
     217    45475804 :       *validity =
     218             :           x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
     219             :     else
     220           0 :       *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
     221             :                                                          : RANGE_UNDERFLOW;
     222             : 
     223             :   } else {
     224           0 :     if (y > 0)
     225           0 :       *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
     226             :                                                          : RANGE_UNDERFLOW;
     227             :     else
     228           0 :       *validity =
     229             :           y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
     230             :   }
     231             : 
     232    45475804 :   return x * y;
     233             : }
     234             : 
     235             : template <typename T>
     236             : typename enable_if<std::numeric_limits<T>::is_integer &&
     237             :                        !std::numeric_limits<T>::is_signed &&
     238             :                        (sizeof(T) * 2 > sizeof(uintmax_t)),
     239             :                    T>::type
     240             : CheckedMul(T x, T y, RangeConstraint* validity) {
     241             :   *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
     242             :                   ? RANGE_VALID
     243             :                   : RANGE_OVERFLOW;
     244             :   return x * y;
     245             : }
     246             : 
     247             : // Division just requires a check for an invalid negation on signed min/-1.
     248             : template <typename T>
     249             : T CheckedDiv(
     250             :     T x,
     251             :     T y,
     252             :     RangeConstraint* validity,
     253             :     typename enable_if<std::numeric_limits<T>::is_integer, int>::type = 0) {
     254             :   if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() &&
     255             :       y == static_cast<T>(-1)) {
     256             :     *validity = RANGE_OVERFLOW;
     257             :     return std::numeric_limits<T>::min();
     258             :   }
     259             : 
     260             :   *validity = RANGE_VALID;
     261             :   return x / y;
     262             : }
     263             : 
     264             : template <typename T>
     265             : typename enable_if<
     266             :     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
     267             :     T>::type
     268             : CheckedMod(T x, T y, RangeConstraint* validity) {
     269             :   *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
     270             :   return x % y;
     271             : }
     272             : 
     273             : template <typename T>
     274             : typename enable_if<
     275             :     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
     276             :     T>::type
     277             : CheckedMod(T x, T y, RangeConstraint* validity) {
     278             :   *validity = RANGE_VALID;
     279             :   return x % y;
     280             : }
     281             : 
     282             : template <typename T>
     283             : typename enable_if<
     284             :     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
     285             :     T>::type
     286             : CheckedNeg(T value, RangeConstraint* validity) {
     287             :   *validity =
     288             :       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
     289             :   // The negation of signed min is min, so catch that one.
     290             :   return -value;
     291             : }
     292             : 
     293             : template <typename T>
     294             : typename enable_if<
     295             :     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
     296             :     T>::type
     297             : CheckedNeg(T value, RangeConstraint* validity) {
     298             :   // The only legal unsigned negation is zero.
     299             :   *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
     300             :   return static_cast<T>(
     301             :       -static_cast<typename SignedIntegerForSize<T>::type>(value));
     302             : }
     303             : 
     304             : template <typename T>
     305             : typename enable_if<
     306             :     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
     307             :     T>::type
     308             : CheckedAbs(T value, RangeConstraint* validity) {
     309             :   *validity =
     310             :       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
     311             :   return std::abs(value);
     312             : }
     313             : 
     314             : template <typename T>
     315             : typename enable_if<
     316             :     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
     317             :     T>::type
     318             : CheckedAbs(T value, RangeConstraint* validity) {
     319             :   // Absolute value of a positive is just its identiy.
     320             :   *validity = RANGE_VALID;
     321             :   return value;
     322             : }
     323             : 
     324             : // These are the floating point stubs that the compiler needs to see. Only the
     325             : // negation operation is ever called.
     326             : #define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                        \
     327             :   template <typename T>                                          \
     328             :   typename enable_if<std::numeric_limits<T>::is_iec559, T>::type \
     329             :   Checked##NAME(T, T, RangeConstraint*) {                        \
     330             :     UNREACHABLE();                                               \
     331             :     return 0;                                                    \
     332             :   }
     333             : 
     334             : BASE_FLOAT_ARITHMETIC_STUBS(Add)
     335             : BASE_FLOAT_ARITHMETIC_STUBS(Sub)
     336             : BASE_FLOAT_ARITHMETIC_STUBS(Mul)
     337             : BASE_FLOAT_ARITHMETIC_STUBS(Div)
     338             : BASE_FLOAT_ARITHMETIC_STUBS(Mod)
     339             : 
     340             : #undef BASE_FLOAT_ARITHMETIC_STUBS
     341             : 
     342             : template <typename T>
     343             : typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
     344             :     T value,
     345             :     RangeConstraint*) {
     346             :   return -value;
     347             : }
     348             : 
     349             : template <typename T>
     350             : typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
     351             :     T value,
     352             :     RangeConstraint*) {
     353             :   return std::abs(value);
     354             : }
     355             : 
     356             : // Floats carry around their validity state with them, but integers do not. So,
     357             : // we wrap the underlying value in a specialization in order to hide that detail
     358             : // and expose an interface via accessors.
     359             : enum NumericRepresentation {
     360             :   NUMERIC_INTEGER,
     361             :   NUMERIC_FLOATING,
     362             :   NUMERIC_UNKNOWN
     363             : };
     364             : 
     365             : template <typename NumericType>
     366             : struct GetNumericRepresentation {
     367             :   static const NumericRepresentation value =
     368             :       std::numeric_limits<NumericType>::is_integer
     369             :           ? NUMERIC_INTEGER
     370             :           : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
     371             :                                                          : NUMERIC_UNKNOWN);
     372             : };
     373             : 
     374             : template <typename T, NumericRepresentation type =
     375             :                           GetNumericRepresentation<T>::value>
     376             : class CheckedNumericState {};
     377             : 
     378             : // Integrals require quite a bit of additional housekeeping to manage state.
     379             : template <typename T>
     380             : class CheckedNumericState<T, NUMERIC_INTEGER> {
     381             :  private:
     382             :   T value_;
     383             :   RangeConstraint validity_;
     384             : 
     385             :  public:
     386             :   template <typename Src, NumericRepresentation type>
     387             :   friend class CheckedNumericState;
     388             : 
     389             :   CheckedNumericState() : value_(0), validity_(RANGE_VALID) {}
     390             : 
     391             :   template <typename Src>
     392             :   CheckedNumericState(Src value, RangeConstraint validity)
     393             :       : value_(value),
     394             :         validity_(GetRangeConstraint(validity |
     395             :                                      DstRangeRelationToSrcRange<T>(value))) {
     396             :     // Argument must be numeric.
     397             :     STATIC_ASSERT(std::numeric_limits<Src>::is_specialized);
     398             :   }
     399             : 
     400             :   // Copy constructor.
     401             :   template <typename Src>
     402             :   CheckedNumericState(const CheckedNumericState<Src>& rhs)
     403             :       : value_(static_cast<T>(rhs.value())),
     404             :         validity_(GetRangeConstraint(
     405             :             rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}
     406             : 
     407             :   template <typename Src>
     408             :   explicit CheckedNumericState(
     409             :       Src value,
     410             :       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
     411             :           0)
     412             :       : value_(static_cast<T>(value)),
     413    45479992 :         validity_(DstRangeRelationToSrcRange<T>(value)) {}
     414             : 
     415             :   RangeConstraint validity() const { return validity_; }
     416             :   T value() const { return value_; }
     417             : };
     418             : 
     419             : // Floating points maintain their own validity, but need translation wrappers.
     420             : template <typename T>
     421             : class CheckedNumericState<T, NUMERIC_FLOATING> {
     422             :  private:
     423             :   T value_;
     424             : 
     425             :  public:
     426             :   template <typename Src, NumericRepresentation type>
     427             :   friend class CheckedNumericState;
     428             : 
     429             :   CheckedNumericState() : value_(0.0) {}
     430             : 
     431             :   template <typename Src>
     432             :   CheckedNumericState(
     433             :       Src value,
     434             :       RangeConstraint validity,
     435             :       typename enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0) {
     436             :     switch (DstRangeRelationToSrcRange<T>(value)) {
     437             :       case RANGE_VALID:
     438             :         value_ = static_cast<T>(value);
     439             :         break;
     440             : 
     441             :       case RANGE_UNDERFLOW:
     442             :         value_ = -std::numeric_limits<T>::infinity();
     443             :         break;
     444             : 
     445             :       case RANGE_OVERFLOW:
     446             :         value_ = std::numeric_limits<T>::infinity();
     447             :         break;
     448             : 
     449             :       case RANGE_INVALID:
     450             :         value_ = std::numeric_limits<T>::quiet_NaN();
     451             :         break;
     452             :     }
     453             :   }
     454             : 
     455             :   template <typename Src>
     456             :   explicit CheckedNumericState(
     457             :       Src value,
     458             :       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
     459             :           0)
     460             :       : value_(static_cast<T>(value)) {}
     461             : 
     462             :   // Copy constructor.
     463             :   template <typename Src>
     464             :   CheckedNumericState(const CheckedNumericState<Src>& rhs)
     465             :       : value_(static_cast<T>(rhs.value())) {}
     466             : 
     467             :   RangeConstraint validity() const {
     468             :     return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
     469             :                               value_ >= -std::numeric_limits<T>::max());
     470             :   }
     471             :   T value() const { return value_; }
     472             : };
     473             : 
     474             : // For integers less than 128-bit and floats 32-bit or larger, we can distil
     475             : // C/C++ arithmetic promotions down to two simple rules:
     476             : // 1. The type with the larger maximum exponent always takes precedence.
     477             : // 2. The resulting type must be promoted to at least an int.
     478             : // The following template specializations implement that promotion logic.
     479             : enum ArithmeticPromotionCategory {
     480             :   LEFT_PROMOTION,
     481             :   RIGHT_PROMOTION,
     482             :   DEFAULT_PROMOTION
     483             : };
     484             : 
     485             : template <typename Lhs,
     486             :           typename Rhs = Lhs,
     487             :           ArithmeticPromotionCategory Promotion =
     488             :               (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
     489             :                   ? (MaxExponent<Lhs>::value > MaxExponent<int>::value
     490             :                          ? LEFT_PROMOTION
     491             :                          : DEFAULT_PROMOTION)
     492             :                   : (MaxExponent<Rhs>::value > MaxExponent<int>::value
     493             :                          ? RIGHT_PROMOTION
     494             :                          : DEFAULT_PROMOTION) >
     495             : struct ArithmeticPromotion;
     496             : 
     497             : template <typename Lhs, typename Rhs>
     498             : struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
     499             :   typedef Lhs type;
     500             : };
     501             : 
     502             : template <typename Lhs, typename Rhs>
     503             : struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
     504             :   typedef Rhs type;
     505             : };
     506             : 
     507             : template <typename Lhs, typename Rhs>
     508             : struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> {
     509             :   typedef int type;
     510             : };
     511             : 
     512             : // We can statically check if operations on the provided types can wrap, so we
     513             : // can skip the checked operations if they're not needed. So, for an integer we
     514             : // care if the destination type preserves the sign and is twice the width of
     515             : // the source.
     516             : template <typename T, typename Lhs, typename Rhs>
     517             : struct IsIntegerArithmeticSafe {
     518             :   static const bool value = !std::numeric_limits<T>::is_iec559 &&
     519             :                             StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
     520             :                                 NUMERIC_RANGE_CONTAINED &&
     521             :                             sizeof(T) >= (2 * sizeof(Lhs)) &&
     522             :                             StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
     523             :                                 NUMERIC_RANGE_CONTAINED &&
     524             :                             sizeof(T) >= (2 * sizeof(Rhs));
     525             : };
     526             : 
     527             : }  // namespace internal
     528             : }  // namespace base
     529             : }  // namespace v8
     530             : 
     531             : #endif  // V8_BASE_SAFE_MATH_IMPL_H_

Generated by: LCOV version 1.10