iOS/Pods/Realm/include/core/realm/util/safe_int_ops.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2016 Realm Inc.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  **************************************************************************/
  18
  19 #ifndef REALM_UTIL_SAFE_INT_OPS_HPP
  20 #define REALM_UTIL_SAFE_INT_OPS_HPP
  21
  22 #ifdef _WIN32
  23 #undef max // collides with numeric_limits::max called later in this header file
  24 #undef min // collides with numeric_limits::min called later in this header file
  25 #endif
  26
  27 #include <limits>
  28
  29 #include <realm/util/features.h>
  30 #include <realm/util/assert.hpp>
  31 #include <realm/util/type_traits.hpp>
  32
  33 namespace realm {
  34 namespace util {
  35
  36
  37 /// Perform integral or floating-point promotion on the argument. This
  38 /// is useful for example when printing a number of arbitrary numeric
  39 /// type to 'stdout', since it will convert values of character-like
  40 /// types to regular integer types, which will then be printed as
  41 /// numbers rather characters.
  42 template <class T>
  43 typename Promote<T>::type promote(T value) noexcept;
  44
  45
  46 /// This function allows you to test for a negative value in any
  47 /// numeric type, even when the type is unsigned. Normally, when the
  48 /// type is unsigned, such a test will produce a compiler warning.
  49 template <class T>
  50 bool is_negative(T value) noexcept;
  51
  52
  53 /// Cast the specified value to the specified unsigned type reducing
  54 /// the value (or in case of negative values, the two's complement
  55 /// representation) modulo `2**N` where `N` is the number of value
  56 /// bits (or digits) in the unsigned target type. This is usefull in
  57 /// cases where the target type may be `bool`, but need not be `bool`.
  58 template <class To, class From>
  59 To cast_to_unsigned(From) noexcept;
  60
  61
  62 //@{
  63
  64 /// Compare two integers of the same, or of different type, and
  65 /// produce the expected result according to the natural
  66 /// interpretation of the operation.
  67 ///
  68 /// Note that in general a standard comparison between a signed and an
  69 /// unsigned integer type is unsafe, and it often generates a compiler
  70 /// warning. An example is a 'less than' comparison between a negative
  71 /// value of type 'int' and a small positive value of type
  72 /// 'unsigned'. In this case the negative value will be converted to
  73 /// 'unsigned' producing a large positive value which, in turn, will
  74 /// lead to the counter intuitive result of 'false'.
  75 ///
  76 /// Please note that these operation incur absolutely no overhead when
  77 /// the two types have the same signedness.
  78 ///
  79 /// These functions check at compile time that both types have valid
  80 /// specializations of std::numeric_limits<> and that both are indeed
  81 /// integers.
  82 ///
  83 /// These functions make absolutely no assumptions about the platform
  84 /// except that it complies with at least C++03.
  85
  86 template <class A, class B>
  87 inline bool int_equal_to(A, B) noexcept;
  88 template <class A, class B>
  89 inline bool int_not_equal_to(A, B) noexcept;
  90 template <class A, class B>
  91 inline bool int_less_than(A, B) noexcept;
  92 template <class A, class B>
  93 inline bool int_less_than_or_equal(A, B) noexcept;
  94 template <class A, class B>
  95 inline bool int_greater_than(A, B) noexcept;
  96 template <class A, class B>
  97 inline bool int_greater_than_or_equal(A, B) noexcept;
  98
  99 //@}
 100
 101
 102 //@{
 103
 104 /// Check for overflow in integer variable `lval` while adding integer
 105 /// `rval` to it, or while subtracting integer `rval` from it. Returns
 106 /// true on positive or negative overflow.
 107 ///
 108 /// Both `lval` and `rval` must be of an integer type for which a
 109 /// specialization of std::numeric_limits<> exists. The two types need
 110 /// not be the same, in particular, one can be signed and the other
 111 /// one can be unsigned.
 112 ///
 113 /// These functions are especially well suited for cases where \a rval
 114 /// is a compile-time constant.
 115 ///
 116 /// These functions check at compile time that both types have valid
 117 /// specializations of std::numeric_limits<> and that both are indeed
 118 /// integers.
 119 ///
 120 /// These functions make absolutely no assumptions about the platform
 121 /// except that it complies with at least C++03.
 122
 123 template <class L, class R>
 124 inline bool int_add_with_overflow_detect(L& lval, R rval) noexcept;
 125
 126 template <class L, class R>
 127 inline bool int_subtract_with_overflow_detect(L& lval, R rval) noexcept;
 128
 129 //@}
 130
 131
 132 /// Check for positive overflow when multiplying two positive integers
 133 /// of the same, or of different type. Returns true on overflow.
 134 ///
 135 /// \param lval Must not be negative. Both signed and unsigned types
 136 /// can be used.
 137 ///
 138 /// \param rval Must be stricly greater than zero. Both signed and
 139 /// unsigned types can be used.
 140 ///
 141 /// This function is especially well suited for cases where \a rval is
 142 /// a compile-time constant.
 143 ///
 144 /// This function checks at compile time that both types have valid
 145 /// specializations of std::numeric_limits<> and that both are indeed
 146 /// integers.
 147 ///
 148 /// This function makes absolutely no assumptions about the platform
 149 /// except that it complies with at least C++03.
 150 template <class L, class R>
 151 inline bool int_multiply_with_overflow_detect(L& lval, R rval) noexcept;
 152
 153
 154 /// Checks for positive overflow when performing a bitwise shift to
 155 /// the left on a non-negative value of arbitrary integer
 156 /// type. Returns true on overflow.
 157 ///
 158 /// \param lval Must not be negative. Both signed and unsigned types
 159 /// can be used.
 160 ///
 161 /// \param i Must be non-negative and such that <tt>L(1)>>i</tt> has a
 162 /// value that is defined by the C++03 standard. In particular, the
 163 /// value of i must not exceed the number of bits of storage type T as
 164 /// shifting by this amount is not defined by the standard.
 165 ///
 166 /// This function makes absolutely no assumptions about the platform
 167 /// except that it complies with at least C++03.
 168 template <class T>
 169 inline bool int_shift_left_with_overflow_detect(T& lval, int i) noexcept;
 170
 171
 172 //@{
 173
 174 /// Check for overflow when casting an integer value from one type to
 175 /// another. While the first function is a mere check, the second one
 176 /// also carries out the cast, but only when there is no
 177 /// overflow. Both return true on overflow.
 178 ///
 179 /// These functions check at compile time that both types have valid
 180 /// specializations of std::numeric_limits<> and that both are indeed
 181 /// integers.
 182 ///
 183 /// These functions make absolutely no assumptions about the platform
 184 /// except that it complies with at least C++03.
 185
 186 template <class To, class From>
 187 bool int_cast_has_overflow(From from) noexcept;
 188
 189 template <class To, class From>
 190 bool int_cast_with_overflow_detect(From from, To& to) noexcept;
 191
 192 //@}
 193
 194
 195 /// Convert negative values from two's complement representation to the
 196 /// platforms native representation.
 197 ///
 198 /// If `To` is an unsigned type, this function does nothing beyond casting the
 199 /// specified value to `To`. Otherwise, `To` is a signed type, and negative
 200 /// values will be converted from two's complement representation in unsigned
 201 /// `From` to the platforms native representation in `To`.
 202 ///
 203 /// For signed `To` the result is well-defined if, and only if the value with
 204 /// the specified two's complement representation is representable in the
 205 /// specified signed type. While this is generally the case when using
 206 /// corresponding signed/unsigned type pairs, it is not guaranteed by the
 207 /// standard. However, if you know that the signed type has at least as many
 208 /// value bits as the unsigned type, then the result is always
 209 /// well-defined. Note that a 'value bit' in this context is the same as a
 210 /// 'digit' from the point of view of `std::numeric_limits`.
 211 ///
 212 /// On platforms that use two's complement representation of negative values,
 213 /// this function is expected to be completely optimized away. This has been
 214 /// observed to be true with both GCC 4.8 and Clang 3.2.
 215 ///
 216 /// Note that the **opposite** direction (from the platforms native
 217 /// representation to two's complement) is trivially handled by casting the
 218 /// signed value to a value of a sufficiently wide unsigned integer type. An
 219 /// unsigned type will be sufficiently wide if it has at least one more value
 220 /// bit than the signed type.
 221 ///
 222 /// Interestingly, the C++ language offers no direct way of doing what this
 223 /// function does, yet, this function is implemented in a way that makes no
 224 /// assumption about the underlying platform except what is guaranteed by C++11.
 225 ///
 226 /// \tparam From The unsigned type used to store the two's complement
 227 /// representation.
 228 ///
 229 /// \tparam To A signed or unsigned integer type.
 230 template <class To, class From>
 231 To from_twos_compl(From twos_compl) noexcept;
 232
 233
 234 // Implementation:
 235
 236 template <class T>
 237 inline typename Promote<T>::type promote(T value) noexcept
 238 {
 239     typedef typename Promote<T>::type promoted_type;
 240     promoted_type value_2 = promoted_type(value);
 241     return value_2;
 242 }
 243
 244 } // namespace util
 245
 246 namespace _impl {
 247
 248 template <class T, bool is_signed>
 249 struct IsNegative {
 250     static bool test(T value) noexcept
 251     {
 252         return value < 0;
 253     }
 254 };
 255 template <class T>
 256 struct IsNegative<T, false> {
 257     static bool test(T) noexcept
 258     {
 259         return false;
 260     }
 261 };
 262
 263 template <class To>
 264 struct CastToUnsigned {
 265     template <class From>
 266     static To cast(From value) noexcept
 267     {
 268         return To(value);
 269     }
 270 };
 271 template <>
 272 struct CastToUnsigned<bool> {
 273     template <class From>
 274     static bool cast(From value) noexcept
 275     {
 276         return bool(unsigned(value) & 1);
 277     }
 278 };
 279
 280 template <class L, class R, bool l_signed, bool r_signed>
 281 struct SafeIntBinopsImpl {
 282 };
 283
 284 // (unsigned, unsigned) (all size combinations)
 285 //
 286 // This implementation utilizes the fact that overflow in unsigned
 287 // arithmetic is guaranteed to be handled by reduction modulo 2**N
 288 // where N is the number of bits in the unsigned type. The purpose of
 289 // the bitwise 'and' with lim_l::max() is to make a cast to bool
 290 // behave the same way as casts to other unsigned integer types.
 291 // Finally, this implementation uses the fact that if modular addition
 292 // overflows, then the result must be a value that is less than both
 293 // operands. Also, if modular subtraction overflows, then the result
 294 // must be a value that is greater than the first operand.
 295 template <class L, class R>
 296 struct SafeIntBinopsImpl<L, R, false, false> {
 297     typedef std::numeric_limits<L> lim_l;
 298     typedef std::numeric_limits<R> lim_r;
 299     static const int needed_bits_l = lim_l::digits;
 300     static const int needed_bits_r = lim_r::digits;
 301     static const int needed_bits = needed_bits_l >= needed_bits_r ? needed_bits_l : needed_bits_r;
 302     typedef typename util::FastestUnsigned<needed_bits>::type common_unsigned;
 303     static bool equal(L l, R r) noexcept
 304     {
 305         return common_unsigned(l) == common_unsigned(r);
 306     }
 307     static bool less(L l, R r) noexcept
 308     {
 309         return common_unsigned(l) < common_unsigned(r);
 310     }
 311     static bool add(L& lval, R rval) noexcept
 312     {
 313         L lval_2 = util::cast_to_unsigned<L>(lval + rval);
 314         bool overflow = common_unsigned(lval_2) < common_unsigned(rval);
 315         if (REALM_UNLIKELY(overflow))
 316             return true;
 317         lval = lval_2;
 318         return false;
 319     }
 320     static bool sub(L& lval, R rval) noexcept
 321     {
 322         common_unsigned lval_2 = common_unsigned(lval) - common_unsigned(rval);
 323         bool overflow = lval_2 > common_unsigned(lval);
 324         if (REALM_UNLIKELY(overflow))
 325             return true;
 326         lval = util::cast_to_unsigned<L>(lval_2);
 327         return false;
 328     }
 329 };
 330
 331 // (unsigned, signed) (all size combinations)
 332 template <class L, class R>
 333 struct SafeIntBinopsImpl<L, R, false, true> {
 334     typedef std::numeric_limits<L> lim_l;
 335     typedef std::numeric_limits<R> lim_r;
 336     static const int needed_bits_l = lim_l::digits;
 337     static const int needed_bits_r = lim_r::digits + 1;
 338     static const int needed_bits = needed_bits_l >= needed_bits_r ? needed_bits_l : needed_bits_r;
 339     typedef typename util::FastestUnsigned<needed_bits>::type common_unsigned;
 340     typedef std::numeric_limits<common_unsigned> lim_cu;
 341     static bool equal(L l, R r) noexcept
 342     {
 343         return (lim_l::digits > lim_r::digits) ? r >= 0 && l == util::cast_to_unsigned<L>(r) : R(l) == r;
 344     }
 345     static bool less(L l, R r) noexcept
 346     {
 347         return (lim_l::digits > lim_r::digits) ? r >= 0 && l < util::cast_to_unsigned<L>(r) : R(l) < r;
 348     }
 349     static bool add(L& lval, R rval) noexcept
 350     {
 351         common_unsigned lval_2 = lval + common_unsigned(rval);
 352         bool overflow;
 353         if (lim_l::digits < lim_cu::digits) {
 354             overflow = common_unsigned(lval_2) > common_unsigned(lim_l::max());
 355         }
 356         else {
 357             overflow = (lval_2 < common_unsigned(lval)) == (rval >= 0);
 358         }
 359         if (REALM_UNLIKELY(overflow))
 360             return true;
 361         lval = util::cast_to_unsigned<L>(lval_2);
 362         return false;
 363     }
 364     static bool sub(L& lval, R rval) noexcept
 365     {
 366         common_unsigned lval_2 = lval - common_unsigned(rval);
 367         bool overflow;
 368         if (lim_l::digits < lim_cu::digits) {
 369             overflow = common_unsigned(lval_2) > common_unsigned(lim_l::max());
 370         }
 371         else {
 372             overflow = (common_unsigned(lval_2) > common_unsigned(lval)) == (rval >= 0);
 373         }
 374         if (REALM_UNLIKELY(overflow))
 375             return true;
 376         lval = util::cast_to_unsigned<L>(lval_2);
 377         return false;
 378     }
 379 };
 380
 381 // (signed, unsigned) (all size combinations)
 382 template <class L, class R>
 383 struct SafeIntBinopsImpl<L, R, true, false> {
 384     typedef std::numeric_limits<L> lim_l;
 385     typedef std::numeric_limits<R> lim_r;
 386     static const int needed_bits_l = lim_l::digits + 1;
 387     static const int needed_bits_r = lim_r::digits;
 388     static const int needed_bits = needed_bits_l >= needed_bits_r ? needed_bits_l : needed_bits_r;
 389     typedef typename util::FastestUnsigned<needed_bits>::type common_unsigned;
 390     static bool equal(L l, R r) noexcept
 391     {
 392         return (lim_l::digits < lim_r::digits) ? l >= 0 && util::cast_to_unsigned<R>(l) == r : l == L(r);
 393     }
 394     static bool less(L l, R r) noexcept
 395     {
 396         return (lim_l::digits < lim_r::digits) ? l < 0 || util::cast_to_unsigned<R>(l) < r : l < L(r);
 397     }
 398     static bool add(L& lval, R rval) noexcept
 399     {
 400         common_unsigned max_add = common_unsigned(lim_l::max()) - common_unsigned(lval);
 401         bool overflow = common_unsigned(rval) > max_add;
 402         if (REALM_UNLIKELY(overflow))
 403             return true;
 404         lval = util::from_twos_compl<L>(common_unsigned(lval) + rval);
 405         return false;
 406     }
 407     static bool sub(L& lval, R rval) noexcept
 408     {
 409         common_unsigned max_sub = common_unsigned(lval) - common_unsigned(lim_l::min());
 410         bool overflow = common_unsigned(rval) > max_sub;
 411         if (REALM_UNLIKELY(overflow))
 412             return true;
 413         lval = util::from_twos_compl<L>(common_unsigned(lval) - rval);
 414         return false;
 415     }
 416 };
 417
 418 // (signed, signed) (all size combinations)
 419 template <class L, class R>
 420 struct SafeIntBinopsImpl<L, R, true, true> {
 421     typedef std::numeric_limits<L> lim_l;
 422     static bool equal(L l, R r) noexcept
 423     {
 424         return l == r;
 425     }
 426     static bool less(L l, R r) noexcept
 427     {
 428         return l < r;
 429     }
 430     static bool add(L& lval, R rval) noexcept
 431     {
 432         // Note that both subtractions below occur in a signed type
 433         // that is at least as wide as both of the two types. Note
 434         // also that any signed type guarantees that there is no
 435         // overflow when subtracting two negative values or two
 436         // non-negative value. See C99 (adopted as subset of C++11)
 437         // section 6.2.6.2 "Integer types" paragraph 2.
 438         if (rval < 0) {
 439             if (REALM_UNLIKELY(lval < lim_l::min() - rval))
 440                 return true;
 441         }
 442         else {
 443             if (REALM_UNLIKELY(lval > lim_l::max() - rval))
 444                 return true;
 445         }
 446         // The following statement has exactly the same effect as
 447         // `lval += rval`.
 448         lval = L(lval + rval);
 449         return false;
 450     }
 451     static bool sub(L& lval, R rval) noexcept
 452     {
 453         // Note that both subtractions below occur in a signed type
 454         // that is at least as wide as both of the two types. Note
 455         // also that there can be no overflow when adding a negative
 456         // value to a non-negative value, or when adding a
 457         // non-negative value to a negative one.
 458         if (rval < 0) {
 459             if (REALM_UNLIKELY(lval > lim_l::max() + rval))
 460                 return true;
 461         }
 462         else {
 463             if (REALM_UNLIKELY(lval < lim_l::min() + rval))
 464                 return true;
 465         }
 466         // The following statement has exactly the same effect as
 467         // `lval += rval`.
 468         lval = L(lval - rval);
 469         return false;
 470     }
 471 };
 472
 473 template <class L, class R>
 474 struct SafeIntBinops : SafeIntBinopsImpl<L, R, std::numeric_limits<L>::is_signed, std::numeric_limits<R>::is_signed> {
 475     typedef std::numeric_limits<L> lim_l;
 476     typedef std::numeric_limits<R> lim_r;
 477     static_assert(lim_l::is_specialized && lim_r::is_specialized,
 478                   "std::numeric_limits<> must be specialized for both types");
 479     static_assert(lim_l::is_integer && lim_r::is_integer, "Both types must be integers");
 480 };
 481
 482 } // namespace _impl
 483
 484 namespace util {
 485
 486 template <class T>
 487 inline bool is_negative(T value) noexcept
 488 {
 489     return _impl::IsNegative<T, std::numeric_limits<T>::is_signed>::test(value);
 490 }
 491
 492 template <class To, class From>
 493 inline To cast_to_unsigned(From value) noexcept
 494 {
 495     return _impl::CastToUnsigned<To>::cast(value);
 496 }
 497
 498 template <class A, class B>
 499 inline bool int_equal_to(A a, B b) noexcept
 500 {
 501     return _impl::SafeIntBinops<A, B>::equal(a, b);
 502 }
 503
 504 template <class A, class B>
 505 inline bool int_not_equal_to(A a, B b) noexcept
 506 {
 507     return !_impl::SafeIntBinops<A, B>::equal(a, b);
 508 }
 509
 510 template <class A, class B>
 511 inline bool int_less_than(A a, B b) noexcept
 512 {
 513     return _impl::SafeIntBinops<A, B>::less(a, b);
 514 }
 515
 516 template <class A, class B>
 517 inline bool int_less_than_or_equal(A a, B b) noexcept
 518 {
 519     return !_impl::SafeIntBinops<B, A>::less(b, a); // Not greater than
 520 }
 521
 522 template <class A, class B>
 523 inline bool int_greater_than(A a, B b) noexcept
 524 {
 525     return _impl::SafeIntBinops<B, A>::less(b, a);
 526 }
 527
 528 template <class A, class B>
 529 inline bool int_greater_than_or_equal(A a, B b) noexcept
 530 {
 531     return !_impl::SafeIntBinops<A, B>::less(a, b); // Not less than
 532 }
 533
 534 template <class L, class R>
 535 inline bool int_add_with_overflow_detect(L& lval, R rval) noexcept
 536 {
 537     return _impl::SafeIntBinops<L, R>::add(lval, rval);
 538 }
 539
 540 template <class L, class R>
 541 inline bool int_subtract_with_overflow_detect(L& lval, R rval) noexcept
 542 {
 543     return _impl::SafeIntBinops<L, R>::sub(lval, rval);
 544 }
 545
 546 template <class L, class R>
 547 inline bool int_multiply_with_overflow_detect(L& lval, R rval) noexcept
 548 {
 549     // FIXME: Check if the following optimizes better (if it works at all):
 550     // L lval_2 = L(lval * rval);
 551     // bool overflow  =  rval != 0  &&  (lval_2 / rval) != lval;
 552     typedef std::numeric_limits<L> lim_l;
 553     typedef std::numeric_limits<R> lim_r;
 554     static_assert(lim_l::is_specialized && lim_r::is_specialized,
 555                   "std::numeric_limits<> must be specialized for both types");
 556     static_assert(lim_l::is_integer && lim_r::is_integer, "Both types must be integers");
 557     REALM_ASSERT(int_greater_than_or_equal(lval, 0));
 558     REALM_ASSERT(int_greater_than(rval, 0));
 559     if (int_less_than(lim_l::max() / rval, lval))
 560         return true;
 561     lval = L(lval * rval);
 562     return false;
 563 }
 564
 565 template <class T>
 566 inline bool int_shift_left_with_overflow_detect(T& lval, int i) noexcept
 567 {
 568     typedef std::numeric_limits<T> lim;
 569     static_assert(lim::is_specialized, "std::numeric_limits<> must be specialized for T");
 570     static_assert(lim::is_integer, "T must be an integer type");
 571     REALM_ASSERT(int_greater_than_or_equal(lval, 0));
 572     if ((lim::max() >> i) < lval)
 573         return true;
 574     lval <<= i;
 575     return false;
 576 }
 577
 578 template <class To, class From>
 579 inline bool int_cast_has_overflow(From from) noexcept
 580 {
 581     typedef std::numeric_limits<To> lim_to;
 582     return int_less_than(from, lim_to::min()) || int_less_than(lim_to::max(), from);
 583 }
 584
 585 template <class To, class From>
 586 inline bool int_cast_with_overflow_detect(From from, To& to) noexcept
 587 {
 588     if (REALM_LIKELY(!int_cast_has_overflow<To>(from))) {
 589         to = To(from);
 590         return false;
 591     }
 592     return true;
 593 }
 594
 595 template <class To, class From>
 596 inline To from_twos_compl(From twos_compl) noexcept
 597 {
 598     typedef std::numeric_limits<From> lim_f;
 599     typedef std::numeric_limits<To> lim_t;
 600     static_assert(lim_f::is_specialized && lim_t::is_specialized,
 601                   "std::numeric_limits<> must be specialized for both types");
 602     static_assert(lim_f::is_integer && lim_t::is_integer, "Both types must be integers");
 603     static_assert(!lim_f::is_signed, "`From` must be unsigned");
 604     To native;
 605     int sign_bit_pos = lim_f::digits - 1;
 606     From sign_bit = From(1) << sign_bit_pos;
 607     bool non_negative = !lim_t::is_signed || (twos_compl & sign_bit) == 0;
 608     if (non_negative) {
 609         // Non-negative value
 610         native = To(twos_compl);
 611     }
 612     else {
 613         // Negative value
 614         native = To(-1 - To(From(-1) - twos_compl));
 615     }
 616     return native;
 617 }
 618
 619
 620 } // namespace util
 621 } // namespace realm
 622
 623 #endif // REALM_UTIL_SAFE_INT_OPS_HPP