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