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 BASE_NUMERICS_SAFE_MATH_IMPL_H_
   6 #define BASE_NUMERICS_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 // This is used for UnsignedAbs, where we need to support floating-point
  94 // template instantiations even though we don't actually support the operations.
  95 // However, there is no corresponding implementation of e.g. CheckedUnsignedAbs,
  96 // so the float versions will not compile.
  97 template <typename Numeric,
  98           bool IsInteger = std::numeric_limits<Numeric>::is_integer,
  99           bool IsFloat = std::numeric_limits<Numeric>::is_iec559>
 100 struct UnsignedOrFloatForSize;
 101
 102 template <typename Numeric>
 103 struct UnsignedOrFloatForSize<Numeric, true, false> {
 104   typedef typename UnsignedIntegerForSize<Numeric>::type type;
 105 };
 106
 107 template <typename Numeric>
 108 struct UnsignedOrFloatForSize<Numeric, false, true> {
 109   typedef Numeric type;
 110 };
 111
 112 // Helper templates for integer manipulations.
 113
 114 template <typename T>
 115 bool HasSignBit(T x) {
 116   // Cast to unsigned since right shift on signed is undefined.
 117   return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
 118             PositionOfSignBit<T>::value);
 119 }
 120
 121 // This wrapper undoes the standard integer promotions.
 122 template <typename T>
 123 T BinaryComplement(T x) {
 124   return ~x;
 125 }
 126
 127 // Here are the actual portable checked integer math implementations.
 128 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
 129 // way to coalesce things into the CheckedNumericState specializations below.
 130
 131 template <typename T>
 132 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
 133 CheckedAdd(T x, T y, RangeConstraint* validity) {
 134   // Since the value of x+y is undefined if we have a signed type, we compute
 135   // it using the unsigned type of the same size.
 136   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
 137   UnsignedDst ux = static_cast<UnsignedDst>(x);
 138   UnsignedDst uy = static_cast<UnsignedDst>(y);
 139   UnsignedDst uresult = ux + uy;
 140   // Addition is valid if the sign of (x + y) is equal to either that of x or
 141   // that of y.
 142   if (std::numeric_limits<T>::is_signed) {
 143     if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
 144       *validity = RANGE_VALID;
 145     else  // Direction of wrap is inverse of result sign.
 146       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
 147
 148   } else {  // Unsigned is either valid or overflow.
 149     *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
 150   }
 151   return static_cast<T>(uresult);
 152 }
 153
 154 template <typename T>
 155 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
 156 CheckedSub(T x, T y, RangeConstraint* validity) {
 157   // Since the value of x+y is undefined if we have a signed type, we compute
 158   // it using the unsigned type of the same size.
 159   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
 160   UnsignedDst ux = static_cast<UnsignedDst>(x);
 161   UnsignedDst uy = static_cast<UnsignedDst>(y);
 162   UnsignedDst uresult = ux - uy;
 163   // Subtraction is valid if either x and y have same sign, or (x-y) and x have
 164   // the same sign.
 165   if (std::numeric_limits<T>::is_signed) {
 166     if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
 167       *validity = RANGE_VALID;
 168     else  // Direction of wrap is inverse of result sign.
 169       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
 170
 171   } else {  // Unsigned is either valid or underflow.
 172     *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
 173   }
 174   return static_cast<T>(uresult);
 175 }
 176
 177 // Integer multiplication is a bit complicated. In the fast case we just
 178 // we just promote to a twice wider type, and range check the result. In the
 179 // slow case we need to manually check that the result won't be truncated by
 180 // checking with division against the appropriate bound.
 181 template <typename T>
 182 typename enable_if<
 183     std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
 184     T>::type
 185 CheckedMul(T x, T y, RangeConstraint* validity) {
 186   typedef typename TwiceWiderInteger<T>::type IntermediateType;
 187   IntermediateType tmp =
 188       static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
 189   *validity = DstRangeRelationToSrcRange<T>(tmp);
 190   return static_cast<T>(tmp);
 191 }
 192
 193 template <typename T>
 194 typename enable_if<std::numeric_limits<T>::is_integer&& std::numeric_limits<
 195                        T>::is_signed&&(sizeof(T) * 2 > sizeof(uintmax_t)),
 196                    T>::type
 197 CheckedMul(T x, T y, RangeConstraint* validity) {
 198   // If either side is zero then the result will be zero.
 199   if (!x || !y) {
 200     return RANGE_VALID;
 201
 202   } else if (x > 0) {
 203     if (y > 0)
 204       *validity =
 205           x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
 206     else
 207       *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
 208                                                          : RANGE_UNDERFLOW;
 209
 210   } else {
 211     if (y > 0)
 212       *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
 213                                                          : RANGE_UNDERFLOW;
 214     else
 215       *validity =
 216           y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
 217   }
 218
 219   return x * y;
 220 }
 221
 222 template <typename T>
 223 typename enable_if<std::numeric_limits<T>::is_integer &&
 224                        !std::numeric_limits<T>::is_signed &&
 225                        (sizeof(T) * 2 > sizeof(uintmax_t)),
 226                    T>::type
 227 CheckedMul(T x, T y, RangeConstraint* validity) {
 228   *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
 229                   ? RANGE_VALID
 230                   : RANGE_OVERFLOW;
 231   return x * y;
 232 }
 233
 234 // Division just requires a check for an invalid negation on signed min/-1.
 235 template <typename T>
 236 T CheckedDiv(
 237     T x,
 238     T y,
 239     RangeConstraint* validity,
 240     typename enable_if<std::numeric_limits<T>::is_integer, int>::type = 0) {
 241   if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() &&
 242       y == static_cast<T>(-1)) {
 243     *validity = RANGE_OVERFLOW;
 244     return std::numeric_limits<T>::min();
 245   }
 246
 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 CheckedMod(T x, T y, RangeConstraint* validity) {
 256   *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
 257   return x % y;
 258 }
 259
 260 template <typename T>
 261 typename enable_if<
 262     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
 263     T>::type
 264 CheckedMod(T x, T y, RangeConstraint* validity) {
 265   *validity = RANGE_VALID;
 266   return x % y;
 267 }
 268
 269 template <typename T>
 270 typename enable_if<
 271     std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
 272     T>::type
 273 CheckedNeg(T value, RangeConstraint* validity) {
 274   *validity =
 275       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
 276   // The negation of signed min is min, so catch that one.
 277   return -value;
 278 }
 279
 280 template <typename T>
 281 typename enable_if<
 282     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
 283     T>::type
 284 CheckedNeg(T value, RangeConstraint* validity) {
 285   // The only legal unsigned negation is zero.
 286   *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
 287   return static_cast<T>(
 288       -static_cast<typename SignedIntegerForSize<T>::type>(value));
 289 }
 290
 291 template <typename T>
 292 typename enable_if<
 293     std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
 294     T>::type
 295 CheckedAbs(T value, RangeConstraint* validity) {
 296   *validity =
 297       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
 298   return static_cast<T>(std::abs(value));
 299 }
 300
 301 template <typename T>
 302 typename enable_if<
 303     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
 304     T>::type
 305 CheckedAbs(T value, RangeConstraint* validity) {
 306   // T is unsigned, so |value| must already be positive.
 307   *validity = RANGE_VALID;
 308   return value;
 309 }
 310
 311 template <typename T>
 312 typename enable_if<std::numeric_limits<T>::is_integer &&
 313                        std::numeric_limits<T>::is_signed,
 314                    typename UnsignedIntegerForSize<T>::type>::type
 315 CheckedUnsignedAbs(T value) {
 316   typedef typename UnsignedIntegerForSize<T>::type UnsignedT;
 317   return value == std::numeric_limits<T>::min()
 318              ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1
 319              : static_cast<UnsignedT>(std::abs(value));
 320 }
 321
 322 template <typename T>
 323 typename enable_if<std::numeric_limits<T>::is_integer &&
 324                        !std::numeric_limits<T>::is_signed,
 325                    T>::type
 326 CheckedUnsignedAbs(T value) {
 327   // T is unsigned, so |value| must already be positive.
 328   return value;
 329 }
 330
 331 // These are the floating point stubs that the compiler needs to see. Only the
 332 // negation operation is ever called.
 333 #define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                        \
 334   template <typename T>                                          \
 335   typename enable_if<std::numeric_limits<T>::is_iec559, T>::type \
 336   Checked##NAME(T, T, RangeConstraint*) {                        \
 337     NOTREACHED();                                                \
 338     return 0;                                                    \
 339   }
 340
 341 BASE_FLOAT_ARITHMETIC_STUBS(Add)
 342 BASE_FLOAT_ARITHMETIC_STUBS(Sub)
 343 BASE_FLOAT_ARITHMETIC_STUBS(Mul)
 344 BASE_FLOAT_ARITHMETIC_STUBS(Div)
 345 BASE_FLOAT_ARITHMETIC_STUBS(Mod)
 346
 347 #undef BASE_FLOAT_ARITHMETIC_STUBS
 348
 349 template <typename T>
 350 typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
 351     T value,
 352     RangeConstraint*) {
 353   return -value;
 354 }
 355
 356 template <typename T>
 357 typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
 358     T value,
 359     RangeConstraint*) {
 360   return std::abs(value);
 361 }
 362
 363 // Floats carry around their validity state with them, but integers do not. So,
 364 // we wrap the underlying value in a specialization in order to hide that detail
 365 // and expose an interface via accessors.
 366 enum NumericRepresentation {
 367   NUMERIC_INTEGER,
 368   NUMERIC_FLOATING,
 369   NUMERIC_UNKNOWN
 370 };
 371
 372 template <typename NumericType>
 373 struct GetNumericRepresentation {
 374   static const NumericRepresentation value =
 375       std::numeric_limits<NumericType>::is_integer
 376           ? NUMERIC_INTEGER
 377           : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
 378                                                          : NUMERIC_UNKNOWN);
 379 };
 380
 381 template <typename T, NumericRepresentation type =
 382                           GetNumericRepresentation<T>::value>
 383 class CheckedNumericState {};
 384
 385 // Integrals require quite a bit of additional housekeeping to manage state.
 386 template <typename T>
 387 class CheckedNumericState<T, NUMERIC_INTEGER> {
 388  private:
 389   T value_;
 390   RangeConstraint validity_;
 391
 392  public:
 393   template <typename Src, NumericRepresentation type>
 394   friend class CheckedNumericState;
 395
 396   CheckedNumericState() : value_(0), validity_(RANGE_VALID) {}
 397
 398   template <typename Src>
 399   CheckedNumericState(Src value, RangeConstraint validity)
 400       : value_(static_cast<T>(value)),
 401         validity_(GetRangeConstraint(validity |
 402                                      DstRangeRelationToSrcRange<T>(value))) {
 403     static_assert(std::numeric_limits<Src>::is_specialized,
 404                   "Argument must be numeric.");
 405   }
 406
 407   // Copy constructor.
 408   template <typename Src>
 409   CheckedNumericState(const CheckedNumericState<Src>& rhs)
 410       : value_(static_cast<T>(rhs.value())),
 411         validity_(GetRangeConstraint(
 412             rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}
 413
 414   template <typename Src>
 415   explicit CheckedNumericState(
 416       Src value,
 417       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
 418           0)
 419       : value_(static_cast<T>(value)),
 420         validity_(DstRangeRelationToSrcRange<T>(value)) {}
 421
 422   RangeConstraint validity() const { return validity_; }
 423   T value() const { return value_; }
 424 };
 425
 426 // Floating points maintain their own validity, but need translation wrappers.
 427 template <typename T>
 428 class CheckedNumericState<T, NUMERIC_FLOATING> {
 429  private:
 430   T value_;
 431
 432  public:
 433   template <typename Src, NumericRepresentation type>
 434   friend class CheckedNumericState;
 435
 436   CheckedNumericState() : value_(0.0) {}
 437
 438   template <typename Src>
 439   CheckedNumericState(
 440       Src value,
 441       RangeConstraint validity,
 442       typename enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0) {
 443     switch (DstRangeRelationToSrcRange<T>(value)) {
 444       case RANGE_VALID:
 445         value_ = static_cast<T>(value);
 446         break;
 447
 448       case RANGE_UNDERFLOW:
 449         value_ = -std::numeric_limits<T>::infinity();
 450         break;
 451
 452       case RANGE_OVERFLOW:
 453         value_ = std::numeric_limits<T>::infinity();
 454         break;
 455
 456       case RANGE_INVALID:
 457         value_ = std::numeric_limits<T>::quiet_NaN();
 458         break;
 459
 460       default:
 461         NOTREACHED();
 462     }
 463   }
 464
 465   template <typename Src>
 466   explicit CheckedNumericState(
 467       Src value,
 468       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
 469           0)
 470       : value_(static_cast<T>(value)) {}
 471
 472   // Copy constructor.
 473   template <typename Src>
 474   CheckedNumericState(const CheckedNumericState<Src>& rhs)
 475       : value_(static_cast<T>(rhs.value())) {}
 476
 477   RangeConstraint validity() const {
 478     return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
 479                               value_ >= -std::numeric_limits<T>::max());
 480   }
 481   T value() const { return value_; }
 482 };
 483
 484 // For integers less than 128-bit and floats 32-bit or larger, we can distil
 485 // C/C++ arithmetic promotions down to two simple rules:
 486 // 1. The type with the larger maximum exponent always takes precedence.
 487 // 2. The resulting type must be promoted to at least an int.
 488 // The following template specializations implement that promotion logic.
 489 enum ArithmeticPromotionCategory {
 490   LEFT_PROMOTION,
 491   RIGHT_PROMOTION,
 492   DEFAULT_PROMOTION
 493 };
 494
 495 template <typename Lhs,
 496           typename Rhs = Lhs,
 497           ArithmeticPromotionCategory Promotion =
 498               (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
 499                   ? (MaxExponent<Lhs>::value > MaxExponent<int>::value
 500                          ? LEFT_PROMOTION
 501                          : DEFAULT_PROMOTION)
 502                   : (MaxExponent<Rhs>::value > MaxExponent<int>::value
 503                          ? RIGHT_PROMOTION
 504                          : DEFAULT_PROMOTION) >
 505 struct ArithmeticPromotion;
 506
 507 template <typename Lhs, typename Rhs>
 508 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
 509   typedef Lhs type;
 510 };
 511
 512 template <typename Lhs, typename Rhs>
 513 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
 514   typedef Rhs type;
 515 };
 516
 517 template <typename Lhs, typename Rhs>
 518 struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> {
 519   typedef int type;
 520 };
 521
 522 // We can statically check if operations on the provided types can wrap, so we
 523 // can skip the checked operations if they're not needed. So, for an integer we
 524 // care if the destination type preserves the sign and is twice the width of
 525 // the source.
 526 template <typename T, typename Lhs, typename Rhs>
 527 struct IsIntegerArithmeticSafe {
 528   static const bool value = !std::numeric_limits<T>::is_iec559 &&
 529                             StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
 530                                 NUMERIC_RANGE_CONTAINED &&
 531                             sizeof(T) >= (2 * sizeof(Lhs)) &&
 532                             StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
 533                                 NUMERIC_RANGE_CONTAINED &&
 534                             sizeof(T) >= (2 * sizeof(Rhs));
 535 };
 536
 537 }  // namespace internal
 538 }  // namespace base
 539
 540 #endif  // BASE_NUMERICS_SAFE_MATH_IMPL_H_