checked_math_impl.h (22009B)
1 // Copyright 2017 The Chromium Authors 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_CHECKED_MATH_IMPL_H_ 6 #define BASE_NUMERICS_CHECKED_MATH_IMPL_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include <climits> 12 #include <cmath> 13 #include <cstdlib> 14 #include <limits> 15 #include <type_traits> 16 17 #include "base/numerics/safe_conversions.h" 18 #include "base/numerics/safe_math_shared_impl.h" 19 20 namespace base { 21 namespace internal { 22 23 template <typename T> 24 constexpr bool CheckedAddImpl(T x, T y, T* result) { 25 static_assert(std::is_integral_v<T>, "Type must be integral"); 26 // Since the value of x+y is undefined if we have a signed type, we compute 27 // it using the unsigned type of the same size. 28 using UnsignedDst = typename std::make_unsigned<T>::type; 29 using SignedDst = typename std::make_signed<T>::type; 30 const UnsignedDst ux = static_cast<UnsignedDst>(x); 31 const UnsignedDst uy = static_cast<UnsignedDst>(y); 32 const UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy); 33 // Addition is valid if the sign of (x + y) is equal to either that of x or 34 // that of y. 35 if (std::is_signed_v<T> 36 ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) < 0 37 : uresult < uy) { // Unsigned is either valid or underflow. 38 return false; 39 } 40 *result = static_cast<T>(uresult); 41 return true; 42 } 43 44 template <typename T, typename U, class Enable = void> 45 struct CheckedAddOp {}; 46 47 template <typename T, typename U> 48 struct CheckedAddOp< 49 T, 50 U, 51 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 52 using result_type = typename MaxExponentPromotion<T, U>::type; 53 template <typename V> 54 static constexpr bool Do(T x, U y, V* result) { 55 if constexpr (CheckedAddFastOp<T, U>::is_supported) 56 return CheckedAddFastOp<T, U>::Do(x, y, result); 57 58 // Double the underlying type up to a full machine word. 59 using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type; 60 using Promotion = 61 typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value > 62 IntegerBitsPlusSign<intptr_t>::value), 63 typename BigEnoughPromotion<T, U>::type, 64 FastPromotion>::type; 65 // Fail if either operand is out of range for the promoted type. 66 // TODO(jschuh): This could be made to work for a broader range of values. 67 if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) || 68 !IsValueInRangeForNumericType<Promotion>(y))) { 69 return false; 70 } 71 72 Promotion presult = {}; 73 bool is_valid = true; 74 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { 75 presult = static_cast<Promotion>(x) + static_cast<Promotion>(y); 76 } else { 77 is_valid = CheckedAddImpl(static_cast<Promotion>(x), 78 static_cast<Promotion>(y), &presult); 79 } 80 if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) 81 return false; 82 *result = static_cast<V>(presult); 83 return true; 84 } 85 }; 86 87 template <typename T> 88 constexpr bool CheckedSubImpl(T x, T y, T* result) { 89 static_assert(std::is_integral_v<T>, "Type must be integral"); 90 // Since the value of x+y is undefined if we have a signed type, we compute 91 // it using the unsigned type of the same size. 92 using UnsignedDst = typename std::make_unsigned<T>::type; 93 using SignedDst = typename std::make_signed<T>::type; 94 const UnsignedDst ux = static_cast<UnsignedDst>(x); 95 const UnsignedDst uy = static_cast<UnsignedDst>(y); 96 const UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy); 97 // Subtraction is valid if either x and y have same sign, or (x-y) and x have 98 // the same sign. 99 if (std::is_signed_v<T> 100 ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) < 0 101 : x < y) { 102 return false; 103 } 104 *result = static_cast<T>(uresult); 105 return true; 106 } 107 108 template <typename T, typename U, class Enable = void> 109 struct CheckedSubOp {}; 110 111 template <typename T, typename U> 112 struct CheckedSubOp< 113 T, 114 U, 115 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 116 using result_type = typename MaxExponentPromotion<T, U>::type; 117 template <typename V> 118 static constexpr bool Do(T x, U y, V* result) { 119 if constexpr (CheckedSubFastOp<T, U>::is_supported) 120 return CheckedSubFastOp<T, U>::Do(x, y, result); 121 122 // Double the underlying type up to a full machine word. 123 using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type; 124 using Promotion = 125 typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value > 126 IntegerBitsPlusSign<intptr_t>::value), 127 typename BigEnoughPromotion<T, U>::type, 128 FastPromotion>::type; 129 // Fail if either operand is out of range for the promoted type. 130 // TODO(jschuh): This could be made to work for a broader range of values. 131 if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) || 132 !IsValueInRangeForNumericType<Promotion>(y))) { 133 return false; 134 } 135 136 Promotion presult = {}; 137 bool is_valid = true; 138 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { 139 presult = static_cast<Promotion>(x) - static_cast<Promotion>(y); 140 } else { 141 is_valid = CheckedSubImpl(static_cast<Promotion>(x), 142 static_cast<Promotion>(y), &presult); 143 } 144 if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) 145 return false; 146 *result = static_cast<V>(presult); 147 return true; 148 } 149 }; 150 151 template <typename T> 152 constexpr bool CheckedMulImpl(T x, T y, T* result) { 153 static_assert(std::is_integral_v<T>, "Type must be integral"); 154 // Since the value of x*y is potentially undefined if we have a signed type, 155 // we compute it using the unsigned type of the same size. 156 using UnsignedDst = typename std::make_unsigned<T>::type; 157 using SignedDst = typename std::make_signed<T>::type; 158 const UnsignedDst ux = SafeUnsignedAbs(x); 159 const UnsignedDst uy = SafeUnsignedAbs(y); 160 const UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy); 161 const bool is_negative = 162 std::is_signed_v<T> && static_cast<SignedDst>(x ^ y) < 0; 163 // We have a fast out for unsigned identity or zero on the second operand. 164 // After that it's an unsigned overflow check on the absolute value, with 165 // a +1 bound for a negative result. 166 if (uy > UnsignedDst(!std::is_signed_v<T> || is_negative) && 167 ux > (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy) { 168 return false; 169 } 170 *result = static_cast<T>(is_negative ? 0 - uresult : uresult); 171 return true; 172 } 173 174 template <typename T, typename U, class Enable = void> 175 struct CheckedMulOp {}; 176 177 template <typename T, typename U> 178 struct CheckedMulOp< 179 T, 180 U, 181 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 182 using result_type = typename MaxExponentPromotion<T, U>::type; 183 template <typename V> 184 static constexpr bool Do(T x, U y, V* result) { 185 if constexpr (CheckedMulFastOp<T, U>::is_supported) 186 return CheckedMulFastOp<T, U>::Do(x, y, result); 187 188 using Promotion = typename FastIntegerArithmeticPromotion<T, U>::type; 189 // Verify the destination type can hold the result (always true for 0). 190 if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) || 191 !IsValueInRangeForNumericType<Promotion>(y)) && 192 x && y)) { 193 return false; 194 } 195 196 Promotion presult = {}; 197 bool is_valid = true; 198 if (CheckedMulFastOp<Promotion, Promotion>::is_supported) { 199 // The fast op may be available with the promoted type. 200 // The casts here are safe because of the "value in range" conditional 201 // above. 202 is_valid = CheckedMulFastOp<Promotion, Promotion>::Do( 203 static_cast<Promotion>(x), static_cast<Promotion>(y), &presult); 204 } else if (IsIntegerArithmeticSafe<Promotion, T, U>::value) { 205 presult = static_cast<Promotion>(x) * static_cast<Promotion>(y); 206 } else { 207 is_valid = CheckedMulImpl(static_cast<Promotion>(x), 208 static_cast<Promotion>(y), &presult); 209 } 210 if (!is_valid || !IsValueInRangeForNumericType<V>(presult)) 211 return false; 212 *result = static_cast<V>(presult); 213 return true; 214 } 215 }; 216 217 // Division just requires a check for a zero denominator or an invalid negation 218 // on signed min/-1. 219 template <typename T, typename U, class Enable = void> 220 struct CheckedDivOp {}; 221 222 template <typename T, typename U> 223 struct CheckedDivOp< 224 T, 225 U, 226 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 227 using result_type = typename MaxExponentPromotion<T, U>::type; 228 template <typename V> 229 static constexpr bool Do(T x, U y, V* result) { 230 if (BASE_NUMERICS_UNLIKELY(!y)) 231 return false; 232 233 // The overflow check can be compiled away if we don't have the exact 234 // combination of types needed to trigger this case. 235 using Promotion = typename BigEnoughPromotion<T, U>::type; 236 if (BASE_NUMERICS_UNLIKELY( 237 (std::is_signed_v<T> && std::is_signed_v<U> && 238 IsTypeInRangeForNumericType<T, Promotion>::value && 239 static_cast<Promotion>(x) == 240 std::numeric_limits<Promotion>::lowest() && 241 y == static_cast<U>(-1)))) { 242 return false; 243 } 244 245 // This branch always compiles away if the above branch wasn't removed. 246 if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) || 247 !IsValueInRangeForNumericType<Promotion>(y)) && 248 x)) { 249 return false; 250 } 251 252 const Promotion presult = Promotion(x) / Promotion(y); 253 if (!IsValueInRangeForNumericType<V>(presult)) 254 return false; 255 *result = static_cast<V>(presult); 256 return true; 257 } 258 }; 259 260 template <typename T, typename U, class Enable = void> 261 struct CheckedModOp {}; 262 263 template <typename T, typename U> 264 struct CheckedModOp< 265 T, 266 U, 267 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 268 using result_type = typename MaxExponentPromotion<T, U>::type; 269 template <typename V> 270 static constexpr bool Do(T x, U y, V* result) { 271 if (BASE_NUMERICS_UNLIKELY(!y)) 272 return false; 273 274 using Promotion = typename BigEnoughPromotion<T, U>::type; 275 if (BASE_NUMERICS_UNLIKELY( 276 (std::is_signed_v<T> && std::is_signed_v<U> && 277 IsTypeInRangeForNumericType<T, Promotion>::value && 278 static_cast<Promotion>(x) == 279 std::numeric_limits<Promotion>::lowest() && 280 y == static_cast<U>(-1)))) { 281 *result = 0; 282 return true; 283 } 284 285 const Promotion presult = 286 static_cast<Promotion>(x) % static_cast<Promotion>(y); 287 if (!IsValueInRangeForNumericType<V>(presult)) 288 return false; 289 *result = static_cast<Promotion>(presult); 290 return true; 291 } 292 }; 293 294 template <typename T, typename U, class Enable = void> 295 struct CheckedLshOp {}; 296 297 // Left shift. Shifts less than 0 or greater than or equal to the number 298 // of bits in the promoted type are undefined. Shifts of negative values 299 // are undefined. Otherwise it is defined when the result fits. 300 template <typename T, typename U> 301 struct CheckedLshOp< 302 T, 303 U, 304 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 305 using result_type = T; 306 template <typename V> 307 static constexpr bool Do(T x, U shift, V* result) { 308 // Disallow negative numbers and verify the shift is in bounds. 309 if (BASE_NUMERICS_LIKELY(!IsValueNegative(x) && 310 as_unsigned(shift) < 311 as_unsigned(std::numeric_limits<T>::digits))) { 312 // Shift as unsigned to avoid undefined behavior. 313 *result = static_cast<V>(as_unsigned(x) << shift); 314 // If the shift can be reversed, we know it was valid. 315 return *result >> shift == x; 316 } 317 318 // Handle the legal corner-case of a full-width signed shift of zero. 319 if (!std::is_signed_v<T> || x || 320 as_unsigned(shift) != as_unsigned(std::numeric_limits<T>::digits)) { 321 return false; 322 } 323 *result = 0; 324 return true; 325 } 326 }; 327 328 template <typename T, typename U, class Enable = void> 329 struct CheckedRshOp {}; 330 331 // Right shift. Shifts less than 0 or greater than or equal to the number 332 // of bits in the promoted type are undefined. Otherwise, it is always defined, 333 // but a right shift of a negative value is implementation-dependent. 334 template <typename T, typename U> 335 struct CheckedRshOp< 336 T, 337 U, 338 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 339 using result_type = T; 340 template <typename V> 341 static constexpr bool Do(T x, U shift, V* result) { 342 // Use sign conversion to push negative values out of range. 343 if (BASE_NUMERICS_UNLIKELY(as_unsigned(shift) >= 344 IntegerBitsPlusSign<T>::value)) { 345 return false; 346 } 347 348 const T tmp = x >> shift; 349 if (!IsValueInRangeForNumericType<V>(tmp)) 350 return false; 351 *result = static_cast<V>(tmp); 352 return true; 353 } 354 }; 355 356 template <typename T, typename U, class Enable = void> 357 struct CheckedAndOp {}; 358 359 // For simplicity we support only unsigned integer results. 360 template <typename T, typename U> 361 struct CheckedAndOp< 362 T, 363 U, 364 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 365 using result_type = typename std::make_unsigned< 366 typename MaxExponentPromotion<T, U>::type>::type; 367 template <typename V> 368 static constexpr bool Do(T x, U y, V* result) { 369 const result_type tmp = 370 static_cast<result_type>(x) & static_cast<result_type>(y); 371 if (!IsValueInRangeForNumericType<V>(tmp)) 372 return false; 373 *result = static_cast<V>(tmp); 374 return true; 375 } 376 }; 377 378 template <typename T, typename U, class Enable = void> 379 struct CheckedOrOp {}; 380 381 // For simplicity we support only unsigned integers. 382 template <typename T, typename U> 383 struct CheckedOrOp< 384 T, 385 U, 386 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 387 using result_type = typename std::make_unsigned< 388 typename MaxExponentPromotion<T, U>::type>::type; 389 template <typename V> 390 static constexpr bool Do(T x, U y, V* result) { 391 const result_type tmp = 392 static_cast<result_type>(x) | static_cast<result_type>(y); 393 if (!IsValueInRangeForNumericType<V>(tmp)) 394 return false; 395 *result = static_cast<V>(tmp); 396 return true; 397 } 398 }; 399 400 template <typename T, typename U, class Enable = void> 401 struct CheckedXorOp {}; 402 403 // For simplicity we support only unsigned integers. 404 template <typename T, typename U> 405 struct CheckedXorOp< 406 T, 407 U, 408 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>> { 409 using result_type = typename std::make_unsigned< 410 typename MaxExponentPromotion<T, U>::type>::type; 411 template <typename V> 412 static constexpr bool Do(T x, U y, V* result) { 413 const result_type tmp = 414 static_cast<result_type>(x) ^ static_cast<result_type>(y); 415 if (!IsValueInRangeForNumericType<V>(tmp)) 416 return false; 417 *result = static_cast<V>(tmp); 418 return true; 419 } 420 }; 421 422 // Max doesn't really need to be implemented this way because it can't fail, 423 // but it makes the code much cleaner to use the MathOp wrappers. 424 template <typename T, typename U, class Enable = void> 425 struct CheckedMaxOp {}; 426 427 template <typename T, typename U> 428 struct CheckedMaxOp< 429 T, 430 U, 431 std::enable_if_t<std::is_arithmetic_v<T> && std::is_arithmetic_v<U>>> { 432 using result_type = typename MaxExponentPromotion<T, U>::type; 433 template <typename V> 434 static constexpr bool Do(T x, U y, V* result) { 435 const result_type tmp = IsGreater<T, U>::Test(x, y) 436 ? static_cast<result_type>(x) 437 : static_cast<result_type>(y); 438 if (!IsValueInRangeForNumericType<V>(tmp)) 439 return false; 440 *result = static_cast<V>(tmp); 441 return true; 442 } 443 }; 444 445 // Min doesn't really need to be implemented this way because it can't fail, 446 // but it makes the code much cleaner to use the MathOp wrappers. 447 template <typename T, typename U, class Enable = void> 448 struct CheckedMinOp {}; 449 450 template <typename T, typename U> 451 struct CheckedMinOp< 452 T, 453 U, 454 std::enable_if_t<std::is_arithmetic_v<T> && std::is_arithmetic_v<U>>> { 455 using result_type = typename LowestValuePromotion<T, U>::type; 456 template <typename V> 457 static constexpr bool Do(T x, U y, V* result) { 458 const result_type tmp = IsLess<T, U>::Test(x, y) 459 ? static_cast<result_type>(x) 460 : static_cast<result_type>(y); 461 if (!IsValueInRangeForNumericType<V>(tmp)) 462 return false; 463 *result = static_cast<V>(tmp); 464 return true; 465 } 466 }; 467 468 // This is just boilerplate that wraps the standard floating point arithmetic. 469 // A macro isn't the nicest solution, but it beats rewriting these repeatedly. 470 #define BASE_FLOAT_ARITHMETIC_OPS(NAME, OP) \ 471 template <typename T, typename U> \ 472 struct Checked##NAME##Op<T, U, \ 473 std::enable_if_t<std::is_floating_point_v<T> || \ 474 std::is_floating_point_v<U>>> { \ 475 using result_type = typename MaxExponentPromotion<T, U>::type; \ 476 template <typename V> \ 477 static constexpr bool Do(T x, U y, V* result) { \ 478 using Promotion = typename MaxExponentPromotion<T, U>::type; \ 479 const Promotion presult = x OP y; \ 480 if (!IsValueInRangeForNumericType<V>(presult)) \ 481 return false; \ 482 *result = static_cast<V>(presult); \ 483 return true; \ 484 } \ 485 }; 486 487 BASE_FLOAT_ARITHMETIC_OPS(Add, +) 488 BASE_FLOAT_ARITHMETIC_OPS(Sub, -) 489 BASE_FLOAT_ARITHMETIC_OPS(Mul, *) 490 BASE_FLOAT_ARITHMETIC_OPS(Div, /) 491 492 #undef BASE_FLOAT_ARITHMETIC_OPS 493 494 // Floats carry around their validity state with them, but integers do not. So, 495 // we wrap the underlying value in a specialization in order to hide that detail 496 // and expose an interface via accessors. 497 enum NumericRepresentation { 498 NUMERIC_INTEGER, 499 NUMERIC_FLOATING, 500 NUMERIC_UNKNOWN 501 }; 502 503 template <typename NumericType> 504 struct GetNumericRepresentation { 505 static const NumericRepresentation value = 506 std::is_integral_v<NumericType> 507 ? NUMERIC_INTEGER 508 : (std::is_floating_point_v<NumericType> ? NUMERIC_FLOATING 509 : NUMERIC_UNKNOWN); 510 }; 511 512 template <typename T, 513 NumericRepresentation type = GetNumericRepresentation<T>::value> 514 class CheckedNumericState {}; 515 516 // Integrals require quite a bit of additional housekeeping to manage state. 517 template <typename T> 518 class CheckedNumericState<T, NUMERIC_INTEGER> { 519 public: 520 template <typename Src = int> 521 constexpr explicit CheckedNumericState(Src value = 0, bool is_valid = true) 522 : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)), 523 value_(WellDefinedConversionOrZero(value, is_valid_)) { 524 static_assert(std::is_arithmetic_v<Src>, "Argument must be numeric."); 525 } 526 527 template <typename Src> 528 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs) 529 : CheckedNumericState(rhs.value(), rhs.is_valid()) {} 530 531 constexpr bool is_valid() const { return is_valid_; } 532 533 constexpr T value() const { return value_; } 534 535 private: 536 // Ensures that a type conversion does not trigger undefined behavior. 537 template <typename Src> 538 static constexpr T WellDefinedConversionOrZero(Src value, bool is_valid) { 539 using SrcType = typename internal::UnderlyingType<Src>::type; 540 return (std::is_integral_v<SrcType> || is_valid) ? static_cast<T>(value) 541 : 0; 542 } 543 544 // is_valid_ precedes value_ because member initializers in the constructors 545 // are evaluated in field order, and is_valid_ must be read when initializing 546 // value_. 547 bool is_valid_; 548 T value_; 549 }; 550 551 // Floating points maintain their own validity, but need translation wrappers. 552 template <typename T> 553 class CheckedNumericState<T, NUMERIC_FLOATING> { 554 public: 555 template <typename Src = double> 556 constexpr explicit CheckedNumericState(Src value = 0.0, bool is_valid = true) 557 : value_(WellDefinedConversionOrNaN( 558 value, 559 is_valid && IsValueInRangeForNumericType<T>(value))) {} 560 561 template <typename Src> 562 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs) 563 : CheckedNumericState(rhs.value(), rhs.is_valid()) {} 564 565 constexpr bool is_valid() const { 566 // Written this way because std::isfinite is not reliably constexpr. 567 return IsConstantEvaluated() 568 ? value_ <= std::numeric_limits<T>::max() && 569 value_ >= std::numeric_limits<T>::lowest() 570 : std::isfinite(value_); 571 } 572 573 constexpr T value() const { return value_; } 574 575 private: 576 // Ensures that a type conversion does not trigger undefined behavior. 577 template <typename Src> 578 static constexpr T WellDefinedConversionOrNaN(Src value, bool is_valid) { 579 using SrcType = typename internal::UnderlyingType<Src>::type; 580 return (StaticDstRangeRelationToSrcRange<T, SrcType>::value == 581 NUMERIC_RANGE_CONTAINED || 582 is_valid) 583 ? static_cast<T>(value) 584 : std::numeric_limits<T>::quiet_NaN(); 585 } 586 587 T value_; 588 }; 589 590 } // namespace internal 591 } // namespace base 592 593 #endif // BASE_NUMERICS_CHECKED_MATH_IMPL_H_