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