OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ | 5 #ifndef BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ |
6 #define BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ | 6 #define BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ |
7 | 7 |
8 #include <limits.h> | 8 #include <limits.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
11 #include <climits> | 11 #include <climits> |
12 #include <limits> | 12 #include <limits> |
13 #include <type_traits> | 13 #include <type_traits> |
14 | 14 |
15 namespace base { | 15 namespace base { |
16 namespace internal { | 16 namespace internal { |
17 | 17 |
18 // The std library doesn't provide a binary max_exponent for integers, however | 18 // The std library doesn't provide a binary max_exponent for integers, however |
19 // we can compute one by adding one to the number of non-sign bits. This allows | 19 // we can compute one by adding one to the number of non-sign bits. This allows |
20 // for accurate range comparisons between floating point and integer types. | 20 // for accurate range comparisons between floating point and integer types. |
21 template <typename NumericType> | 21 template <typename NumericType> |
22 struct MaxExponent { | 22 struct MaxExponent { |
23 static_assert(std::is_arithmetic<NumericType>::value, | |
24 "Argument must be numeric."); | |
25 static const int value = std::numeric_limits<NumericType>::is_iec559 | 23 static const int value = std::numeric_limits<NumericType>::is_iec559 |
26 ? std::numeric_limits<NumericType>::max_exponent | 24 ? std::numeric_limits<NumericType>::max_exponent |
27 : (sizeof(NumericType) * CHAR_BIT + 1 - | 25 : (sizeof(NumericType) * CHAR_BIT + 1 - |
28 std::numeric_limits<NumericType>::is_signed); | 26 std::numeric_limits<NumericType>::is_signed); |
29 }; | 27 }; |
30 | 28 |
31 enum IntegerRepresentation { | 29 enum IntegerRepresentation { |
32 INTEGER_REPRESENTATION_UNSIGNED, | 30 INTEGER_REPRESENTATION_UNSIGNED, |
33 INTEGER_REPRESENTATION_SIGNED | 31 INTEGER_REPRESENTATION_SIGNED |
34 }; | 32 }; |
(...skipping 218 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
253 | 251 |
254 template <typename Dst, typename Src> | 252 template <typename Dst, typename Src> |
255 constexpr RangeConstraint DstRangeRelationToSrcRange(Src value) { | 253 constexpr RangeConstraint DstRangeRelationToSrcRange(Src value) { |
256 static_assert(std::numeric_limits<Src>::is_specialized, | 254 static_assert(std::numeric_limits<Src>::is_specialized, |
257 "Argument must be numeric."); | 255 "Argument must be numeric."); |
258 static_assert(std::numeric_limits<Dst>::is_specialized, | 256 static_assert(std::numeric_limits<Dst>::is_specialized, |
259 "Result must be numeric."); | 257 "Result must be numeric."); |
260 return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value); | 258 return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value); |
261 } | 259 } |
262 | 260 |
| 261 // Integer promotion templates used by the portable checked integer arithmetic. |
| 262 template <size_t Size, bool IsSigned> |
| 263 struct IntegerForSizeAndSign; |
| 264 template <> |
| 265 struct IntegerForSizeAndSign<1, true> { |
| 266 typedef int8_t type; |
| 267 }; |
| 268 template <> |
| 269 struct IntegerForSizeAndSign<1, false> { |
| 270 typedef uint8_t type; |
| 271 }; |
| 272 template <> |
| 273 struct IntegerForSizeAndSign<2, true> { |
| 274 typedef int16_t type; |
| 275 }; |
| 276 template <> |
| 277 struct IntegerForSizeAndSign<2, false> { |
| 278 typedef uint16_t type; |
| 279 }; |
| 280 template <> |
| 281 struct IntegerForSizeAndSign<4, true> { |
| 282 typedef int32_t type; |
| 283 }; |
| 284 template <> |
| 285 struct IntegerForSizeAndSign<4, false> { |
| 286 typedef uint32_t type; |
| 287 }; |
| 288 template <> |
| 289 struct IntegerForSizeAndSign<8, true> { |
| 290 typedef int64_t type; |
| 291 }; |
| 292 template <> |
| 293 struct IntegerForSizeAndSign<8, false> { |
| 294 typedef uint64_t type; |
| 295 static_assert(sizeof(uintmax_t) == 8, |
| 296 "Max integer size not supported for this toolchain."); |
| 297 }; |
| 298 |
| 299 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to |
| 300 // support 128-bit math, then the ArithmeticPromotion template below will need |
| 301 // to be updated (or more likely replaced with a decltype expression). |
| 302 |
| 303 template <typename Integer> |
| 304 struct UnsignedIntegerForSize { |
| 305 typedef typename std::enable_if< |
| 306 std::numeric_limits<Integer>::is_integer, |
| 307 typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type; |
| 308 }; |
| 309 |
| 310 template <typename Integer> |
| 311 struct SignedIntegerForSize { |
| 312 typedef typename std::enable_if< |
| 313 std::numeric_limits<Integer>::is_integer, |
| 314 typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type; |
| 315 }; |
| 316 |
| 317 template <typename Integer> |
| 318 struct TwiceWiderInteger { |
| 319 typedef typename std::enable_if< |
| 320 std::numeric_limits<Integer>::is_integer, |
| 321 typename IntegerForSizeAndSign< |
| 322 sizeof(Integer) * 2, |
| 323 std::numeric_limits<Integer>::is_signed>::type>::type type; |
| 324 }; |
| 325 |
| 326 template <typename Integer> |
| 327 struct PositionOfSignBit { |
| 328 static const typename std::enable_if<std::numeric_limits<Integer>::is_integer, |
| 329 size_t>::type value = |
| 330 CHAR_BIT * sizeof(Integer) - 1; |
| 331 }; |
| 332 |
| 333 enum ArithmeticPromotionCategory { |
| 334 LEFT_PROMOTION, // Use the type of the left-hand argument. |
| 335 RIGHT_PROMOTION, // Use the type of the right-hand argument. |
| 336 MAX_EXPONENT_PROMOTION, // Use the type supporting the largest exponent. |
| 337 BIG_ENOUGH_PROMOTION // Attempt to find a big enough type. |
| 338 }; |
| 339 |
| 340 template <ArithmeticPromotionCategory Promotion, |
| 341 typename Lhs, |
| 342 typename Rhs = Lhs> |
| 343 struct ArithmeticPromotion; |
| 344 |
| 345 template <typename Lhs, |
| 346 typename Rhs, |
| 347 ArithmeticPromotionCategory Promotion = |
| 348 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) |
| 349 ? LEFT_PROMOTION |
| 350 : RIGHT_PROMOTION> |
| 351 struct MaxExponentPromotion; |
| 352 |
| 353 template <typename Lhs, typename Rhs> |
| 354 struct MaxExponentPromotion<Lhs, Rhs, LEFT_PROMOTION> { |
| 355 using type = Lhs; |
| 356 }; |
| 357 |
| 358 template <typename Lhs, typename Rhs> |
| 359 struct MaxExponentPromotion<Lhs, Rhs, RIGHT_PROMOTION> { |
| 360 using type = Rhs; |
| 361 }; |
| 362 |
| 363 template <typename Lhs, |
| 364 typename Rhs = Lhs, |
| 365 bool is_intmax_type = |
| 366 std::is_integral< |
| 367 typename MaxExponentPromotion<Lhs, Rhs>::type>::value && |
| 368 sizeof(typename MaxExponentPromotion<Lhs, Rhs>::type) == |
| 369 sizeof(intmax_t), |
| 370 bool is_max_exponent = |
| 371 StaticDstRangeRelationToSrcRange< |
| 372 typename MaxExponentPromotion<Lhs, Rhs>::type, |
| 373 Lhs>::value == |
| 374 NUMERIC_RANGE_CONTAINED&& StaticDstRangeRelationToSrcRange< |
| 375 typename MaxExponentPromotion<Lhs, Rhs>::type, |
| 376 Rhs>::value == NUMERIC_RANGE_CONTAINED> |
| 377 struct BigEnoughPromotion; |
| 378 |
| 379 // The side with the max exponent is big enough. |
| 380 template <typename Lhs, typename Rhs, bool is_intmax_type> |
| 381 struct BigEnoughPromotion<Lhs, Rhs, is_intmax_type, true> { |
| 382 using type = typename MaxExponentPromotion<Lhs, Rhs>::type; |
| 383 static const bool is_contained = true; |
| 384 }; |
| 385 |
| 386 // We can use a twice wider type to fit. |
| 387 template <typename Lhs, typename Rhs> |
| 388 struct BigEnoughPromotion<Lhs, Rhs, false, false> { |
| 389 using type = typename IntegerForSizeAndSign< |
| 390 sizeof(typename MaxExponentPromotion<Lhs, Rhs>::type) * 2, |
| 391 std::is_signed<Lhs>::value || std::is_signed<Rhs>::value>::type; |
| 392 static const bool is_contained = true; |
| 393 }; |
| 394 |
| 395 // No type is large enough. |
| 396 template <typename Lhs, typename Rhs> |
| 397 struct BigEnoughPromotion<Lhs, Rhs, true, false> { |
| 398 using type = typename MaxExponentPromotion<Lhs, Rhs>::type; |
| 399 static const bool is_contained = false; |
| 400 }; |
| 401 |
| 402 // These are the supported promotion types. |
| 403 |
| 404 // Use the type supporting the largest exponent. |
| 405 template <typename Lhs, typename Rhs> |
| 406 struct ArithmeticPromotion<MAX_EXPONENT_PROMOTION, Lhs, Rhs> { |
| 407 using type = typename MaxExponentPromotion<Lhs, Rhs>::type; |
| 408 static const bool is_contained = true; |
| 409 }; |
| 410 |
| 411 // Attempt to find a big enough type. |
| 412 template <typename Lhs, typename Rhs> |
| 413 struct ArithmeticPromotion<BIG_ENOUGH_PROMOTION, Lhs, Rhs> { |
| 414 using type = typename BigEnoughPromotion<Lhs, Rhs>::type; |
| 415 static const bool is_contained = BigEnoughPromotion<Lhs, Rhs>::is_contained; |
| 416 }; |
| 417 |
| 418 // We can statically check if operations on the provided types can wrap, so we |
| 419 // can skip the checked operations if they're not needed. So, for an integer we |
| 420 // care if the destination type preserves the sign and is twice the width of |
| 421 // the source. |
| 422 template <typename T, typename Lhs, typename Rhs> |
| 423 struct IsIntegerArithmeticSafe { |
| 424 static const bool value = !std::numeric_limits<T>::is_iec559 && |
| 425 StaticDstRangeRelationToSrcRange<T, Lhs>::value == |
| 426 NUMERIC_RANGE_CONTAINED && |
| 427 sizeof(T) >= (2 * sizeof(Lhs)) && |
| 428 StaticDstRangeRelationToSrcRange<T, Rhs>::value != |
| 429 NUMERIC_RANGE_CONTAINED && |
| 430 sizeof(T) >= (2 * sizeof(Rhs)); |
| 431 }; |
| 432 |
| 433 // This hacks around libstdc++ 4.6 missing stuff in type_traits. |
| 434 #if defined(__GLIBCXX__) |
| 435 #define PRIV_GLIBCXX_4_7_0 20120322 |
| 436 #define PRIV_GLIBCXX_4_5_4 20120702 |
| 437 #define PRIV_GLIBCXX_4_6_4 20121127 |
| 438 #if (__GLIBCXX__ < PRIV_GLIBCXX_4_7_0 || __GLIBCXX__ == PRIV_GLIBCXX_4_5_4 || \ |
| 439 __GLIBCXX__ == PRIV_GLIBCXX_4_6_4) |
| 440 #define PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX |
| 441 #undef PRIV_GLIBCXX_4_7_0 |
| 442 #undef PRIV_GLIBCXX_4_5_4 |
| 443 #undef PRIV_GLIBCXX_4_6_4 |
| 444 #endif |
| 445 #endif |
| 446 |
| 447 // Extracts the underlying type from an enum. |
| 448 template <typename T, bool is_enum = std::is_enum<T>::value> |
| 449 struct ArithmeticOrUnderlyingEnum; |
| 450 |
| 451 template <typename T> |
| 452 struct ArithmeticOrUnderlyingEnum<T, true> { |
| 453 #if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) |
| 454 using type = __underlying_type(T); |
| 455 #else |
| 456 using type = typename std::underlying_type<T>::type; |
| 457 #endif |
| 458 static const bool value = std::is_arithmetic<type>::value; |
| 459 }; |
| 460 |
| 461 #if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX) |
| 462 #undef PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX |
| 463 #endif |
| 464 |
| 465 template <typename T> |
| 466 struct ArithmeticOrUnderlyingEnum<T, false> { |
| 467 using type = T; |
| 468 static const bool value = std::is_arithmetic<type>::value; |
| 469 }; |
| 470 |
| 471 // The following are helper templates used in the CheckedNumeric class. |
| 472 template <typename T> |
| 473 class CheckedNumeric; |
| 474 |
| 475 template <typename T> |
| 476 class StrictNumeric; |
| 477 |
| 478 // Used to treat CheckedNumeric and arithmetic underlying types the same. |
| 479 template <typename T> |
| 480 struct UnderlyingType { |
| 481 using type = typename ArithmeticOrUnderlyingEnum<T>::type; |
| 482 static const bool is_numeric = std::is_arithmetic<type>::value; |
| 483 static const bool is_checked = false; |
| 484 static const bool is_strict = false; |
| 485 }; |
| 486 |
| 487 template <typename T> |
| 488 struct UnderlyingType<CheckedNumeric<T>> { |
| 489 using type = T; |
| 490 static const bool is_numeric = true; |
| 491 static const bool is_checked = true; |
| 492 static const bool is_strict = false; |
| 493 }; |
| 494 |
| 495 template <typename T> |
| 496 struct UnderlyingType<StrictNumeric<T>> { |
| 497 using type = T; |
| 498 static const bool is_numeric = true; |
| 499 static const bool is_checked = false; |
| 500 static const bool is_strict = true; |
| 501 }; |
| 502 |
| 503 template <typename L, typename R> |
| 504 struct IsCheckedOp { |
| 505 static const bool value = |
| 506 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric && |
| 507 (UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked); |
| 508 }; |
| 509 |
| 510 template <typename L, typename R> |
| 511 struct IsStrictOp { |
| 512 static const bool value = |
| 513 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric && |
| 514 (UnderlyingType<L>::is_strict || UnderlyingType<R>::is_strict); |
| 515 }; |
| 516 |
| 517 template <typename L, typename R> |
| 518 constexpr bool IsLessImpl(const L lhs, |
| 519 const R rhs, |
| 520 const RangeConstraint l_range, |
| 521 const RangeConstraint r_range) { |
| 522 return l_range == RANGE_UNDERFLOW || r_range == RANGE_OVERFLOW || |
| 523 (l_range == r_range && |
| 524 static_cast<decltype(lhs + rhs)>(lhs) < |
| 525 static_cast<decltype(lhs + rhs)>(rhs)); |
| 526 } |
| 527 |
| 528 template <typename L, typename R> |
| 529 struct IsLess { |
| 530 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 531 "Types must be numeric."); |
| 532 static constexpr bool Test(const L lhs, const R rhs) { |
| 533 return IsLessImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), |
| 534 DstRangeRelationToSrcRange<L>(rhs)); |
| 535 } |
| 536 }; |
| 537 |
| 538 template <typename L, typename R> |
| 539 constexpr bool IsLessOrEqualImpl(const L lhs, |
| 540 const R rhs, |
| 541 const RangeConstraint l_range, |
| 542 const RangeConstraint r_range) { |
| 543 return l_range == RANGE_UNDERFLOW || r_range == RANGE_OVERFLOW || |
| 544 (l_range == r_range && |
| 545 static_cast<decltype(lhs + rhs)>(lhs) <= |
| 546 static_cast<decltype(lhs + rhs)>(rhs)); |
| 547 } |
| 548 |
| 549 template <typename L, typename R> |
| 550 struct IsLessOrEqual { |
| 551 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 552 "Types must be numeric."); |
| 553 static constexpr bool Test(const L lhs, const R rhs) { |
| 554 return IsLessOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), |
| 555 DstRangeRelationToSrcRange<L>(rhs)); |
| 556 } |
| 557 }; |
| 558 |
| 559 template <typename L, typename R> |
| 560 constexpr bool IsGreaterImpl(const L lhs, |
| 561 const R rhs, |
| 562 const RangeConstraint l_range, |
| 563 const RangeConstraint r_range) { |
| 564 return l_range == RANGE_OVERFLOW || r_range == RANGE_UNDERFLOW || |
| 565 (l_range == r_range && |
| 566 static_cast<decltype(lhs + rhs)>(lhs) > |
| 567 static_cast<decltype(lhs + rhs)>(rhs)); |
| 568 } |
| 569 |
| 570 template <typename L, typename R> |
| 571 struct IsGreater { |
| 572 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 573 "Types must be numeric."); |
| 574 static constexpr bool Test(const L lhs, const R rhs) { |
| 575 return IsGreaterImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), |
| 576 DstRangeRelationToSrcRange<L>(rhs)); |
| 577 } |
| 578 }; |
| 579 |
| 580 template <typename L, typename R> |
| 581 constexpr bool IsGreaterOrEqualImpl(const L lhs, |
| 582 const R rhs, |
| 583 const RangeConstraint l_range, |
| 584 const RangeConstraint r_range) { |
| 585 return l_range == RANGE_OVERFLOW || r_range == RANGE_UNDERFLOW || |
| 586 (l_range == r_range && |
| 587 static_cast<decltype(lhs + rhs)>(lhs) >= |
| 588 static_cast<decltype(lhs + rhs)>(rhs)); |
| 589 } |
| 590 |
| 591 template <typename L, typename R> |
| 592 struct IsGreaterOrEqual { |
| 593 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 594 "Types must be numeric."); |
| 595 static constexpr bool Test(const L lhs, const R rhs) { |
| 596 return IsGreaterOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs), |
| 597 DstRangeRelationToSrcRange<L>(rhs)); |
| 598 } |
| 599 }; |
| 600 |
| 601 template <typename L, typename R> |
| 602 struct IsEqual { |
| 603 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 604 "Types must be numeric."); |
| 605 static constexpr bool Test(const L lhs, const R rhs) { |
| 606 return DstRangeRelationToSrcRange<R>(lhs) == |
| 607 DstRangeRelationToSrcRange<L>(rhs) && |
| 608 static_cast<decltype(lhs + rhs)>(lhs) == |
| 609 static_cast<decltype(lhs + rhs)>(rhs); |
| 610 } |
| 611 }; |
| 612 |
| 613 template <typename L, typename R> |
| 614 struct IsNotEqual { |
| 615 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 616 "Types must be numeric."); |
| 617 static constexpr bool Test(const L lhs, const R rhs) { |
| 618 return DstRangeRelationToSrcRange<R>(lhs) != |
| 619 DstRangeRelationToSrcRange<L>(rhs) || |
| 620 static_cast<decltype(lhs + rhs)>(lhs) != |
| 621 static_cast<decltype(lhs + rhs)>(rhs); |
| 622 } |
| 623 }; |
| 624 |
| 625 // These perform the actual math operations on the CheckedNumerics. |
| 626 // Binary arithmetic operations. |
| 627 template <template <typename, typename> class C, typename L, typename R> |
| 628 constexpr bool SafeCompare(const L lhs, const R rhs) { |
| 629 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value, |
| 630 "Types must be numeric."); |
| 631 using Promotion = ArithmeticPromotion<BIG_ENOUGH_PROMOTION, L, R>; |
| 632 using BigType = typename Promotion::type; |
| 633 return Promotion::is_contained |
| 634 // Force to a larger type for speed if both are contained. |
| 635 ? C<BigType, BigType>::Test( |
| 636 static_cast<BigType>(static_cast<L>(lhs)), |
| 637 static_cast<BigType>(static_cast<R>(rhs))) |
| 638 // Let the template functions figure it out for mixed types. |
| 639 : C<L, R>::Test(lhs, rhs); |
| 640 }; |
| 641 |
263 } // namespace internal | 642 } // namespace internal |
264 } // namespace base | 643 } // namespace base |
265 | 644 |
266 #endif // BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ | 645 #endif // BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ |
OLD | NEW |