OLD | NEW |
(Empty) | |
| 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/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_ |
OLD | NEW |