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