base/numerics/safe_math_impl.h

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