ceph/src/boost/boost/multiprecision/cpp_int/divide.hpp

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2012 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   5 //
   6 // Comparison operators for cpp_int_backend:
   7 //
   8 #ifndef BOOST_MP_CPP_INT_DIV_HPP
   9 #define BOOST_MP_CPP_INT_DIV_HPP
  10
  11 #include <boost/multiprecision/detail/no_exceptions_support.hpp>
  12 #include <boost/multiprecision/detail/assert.hpp>
  13
  14 namespace boost { namespace multiprecision { namespace backends {
  15
  16 template <class CppInt1, class CppInt2, class CppInt3>
  17 BOOST_MP_CXX14_CONSTEXPR void divide_unsigned_helper(
  18     CppInt1*       result,
  19     const CppInt2& x,
  20     const CppInt3& y,
  21     CppInt1&       r)
  22 {
  23    if (((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
  24    {
  25       CppInt2 t(x);
  26       divide_unsigned_helper(result, t, y, r);
  27       return;
  28    }
  29    if (((void*)result == (void*)&y) || ((void*)&r == (void*)&y))
  30    {
  31       CppInt3 t(y);
  32       divide_unsigned_helper(result, x, t, r);
  33       return;
  34    }
  35
  36    /*
  37     Very simple, fairly braindead long division.
  38     Start by setting the remainder equal to x, and the
  39     result equal to 0.  Then in each loop we calculate our
  40     "best guess" for how many times y divides into r,
  41     add our guess to the result, and subtract guess*y
  42     from the remainder r.  One wrinkle is that the remainder
  43     may go negative, in which case we subtract the current guess
  44     from the result rather than adding.  The value of the guess
  45     is determined by dividing the most-significant-limb of the
  46     current remainder by the most-significant-limb of y.
  47
  48     Note that there are more efficient algorithms than this
  49     available, in particular see Knuth Vol 2.  However for small
  50     numbers of limbs this generally outperforms the alternatives
  51     and avoids the normalisation step which would require extra storage.
  52     */
  53
  54    using default_ops::eval_subtract;
  55
  56    if (result == &r)
  57    {
  58       CppInt1 rem;
  59       divide_unsigned_helper(result, x, y, rem);
  60       r = rem;
  61       return;
  62    }
  63
  64    //
  65    // Find the most significant words of numerator and denominator.
  66    //
  67    std::size_t y_order = y.size() - 1;
  68
  69    if (y_order == 0)
  70    {
  71       //
  72       // Only a single non-zero limb in the denominator, in this case
  73       // we can use a specialized divide-by-single-limb routine which is
  74       // much faster.  This also handles division by zero:
  75       //
  76       divide_unsigned_helper(result, x, y.limbs()[y_order], r);
  77       return;
  78    }
  79
  80    typename CppInt2::const_limb_pointer px = x.limbs();
  81    typename CppInt3::const_limb_pointer py = y.limbs();
  82
  83    std::size_t r_order = x.size() - 1;
  84    if ((r_order == 0) && (*px == 0))
  85    {
  86       // x is zero, so is the result:
  87       r = x;
  88       if (result)
  89          *result = x;
  90       return;
  91    }
  92
  93    r = x;
  94    r.sign(false);
  95    if (result)
  96       *result = static_cast<limb_type>(0u);
  97    //
  98    // Check if the remainder is already less than the divisor, if so
  99    // we already have the result.  Note we try and avoid a full compare
 100    // if we can:
 101    //
 102    if (r_order <= y_order)
 103    {
 104       if ((r_order < y_order) || (r.compare_unsigned(y) < 0))
 105       {
 106          return;
 107       }
 108    }
 109
 110    CppInt1 t;
 111    bool    r_neg = false;
 112
 113    //
 114    // See if we can short-circuit long division, and use basic arithmetic instead:
 115    //
 116    if (r_order == 0)
 117    {
 118       if (result)
 119       {
 120          *result = px[0] / py[0];
 121       }
 122       r = px[0] % py[0];
 123       return;
 124    }
 125    else if (r_order == 1)
 126    {
 127       double_limb_type a = (static_cast<double_limb_type>(px[1]) << CppInt1::limb_bits) | px[0];
 128       double_limb_type b = y_order ? (static_cast<double_limb_type>(py[1]) << CppInt1::limb_bits) | py[0]
 129                                    : py[0];
 130       if (result)
 131       {
 132          *result = a / b;
 133       }
 134       r = a % b;
 135       return;
 136    }
 137    //
 138    // prepare result:
 139    //
 140    if (result)
 141       result->resize(1 + r_order - y_order, 1 + r_order - y_order);
 142    typename CppInt1::const_limb_pointer prem = r.limbs();
 143    // This is initialised just to keep the compiler from emitting useless warnings later on:
 144    typename CppInt1::limb_pointer pr = typename CppInt1::limb_pointer();
 145    if (result)
 146    {
 147       pr = result->limbs();
 148       for (std::size_t i = 1; i < 1 + r_order - y_order; ++i)
 149          pr[i] = 0;
 150    }
 151    bool first_pass = true;
 152
 153    do
 154    {
 155       //
 156       // Calculate our best guess for how many times y divides into r:
 157       //
 158       limb_type guess = 1;
 159       if ((prem[r_order] <= py[y_order]) && (r_order > 0))
 160       {
 161          double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
 162          double_limb_type b = py[y_order];
 163          double_limb_type v = a / b;
 164          if (v <= CppInt1::max_limb_value)
 165          {
 166             guess = static_cast<limb_type>(v);
 167             --r_order;
 168          }
 169       }
 170       else if (r_order == 0)
 171       {
 172          guess = prem[0] / py[y_order];
 173       }
 174       else
 175       {
 176          double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
 177          double_limb_type b = (y_order > 0) ? (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits) | py[y_order - 1] : (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits);
 178          BOOST_MP_ASSERT(b);
 179          double_limb_type v = a / b;
 180          guess              = static_cast<limb_type>(v);
 181       }
 182       BOOST_MP_ASSERT(guess); // If the guess ever gets to zero we go on forever....
 183       //
 184       // Update result:
 185       //
 186       std::size_t shift = r_order - y_order;
 187       if (result)
 188       {
 189          if (r_neg)
 190          {
 191             if (pr[shift] > guess)
 192                pr[shift] -= guess;
 193             else
 194             {
 195                t.resize(shift + 1, shift + 1);
 196                t.limbs()[shift] = guess;
 197                for (std::size_t i = 0; i < shift; ++i)
 198                   t.limbs()[i] = 0;
 199                eval_subtract(*result, t);
 200             }
 201          }
 202          else if (CppInt1::max_limb_value - pr[shift] > guess)
 203             pr[shift] += guess;
 204          else
 205          {
 206             t.resize(shift + 1, shift + 1);
 207             t.limbs()[shift] = guess;
 208             for (std::size_t i = 0; i < shift; ++i)
 209                t.limbs()[i] = 0;
 210             eval_add(*result, t);
 211          }
 212       }
 213       //
 214       // Calculate guess * y, we use a fused mutiply-shift O(N) for this
 215       // rather than a full O(N^2) multiply:
 216       //
 217       double_limb_type carry = 0;
 218       t.resize(y.size() + shift + 1, y.size() + shift);
 219       bool                           truncated_t = (t.size() != y.size() + shift + 1);
 220       typename CppInt1::limb_pointer pt          = t.limbs();
 221       for (std::size_t i = 0; i < shift; ++i)
 222          pt[i] = 0;
 223       for (std::size_t i = 0; i < y.size(); ++i)
 224       {
 225          carry += static_cast<double_limb_type>(py[i]) * static_cast<double_limb_type>(guess);
 226 #ifdef __MSVC_RUNTIME_CHECKS
 227          pt[i + shift] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 228 #else
 229          pt[i + shift]    = static_cast<limb_type>(carry);
 230 #endif
 231          carry >>= CppInt1::limb_bits;
 232       }
 233       if (carry && !truncated_t)
 234       {
 235 #ifdef __MSVC_RUNTIME_CHECKS
 236          pt[t.size() - 1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 237 #else
 238          pt[t.size() - 1] = static_cast<limb_type>(carry);
 239 #endif
 240       }
 241       else if (!truncated_t)
 242       {
 243          t.resize(t.size() - 1, t.size() - 1);
 244       }
 245       //
 246       // Update r in a way that won't actually produce a negative result
 247       // in case the argument types are unsigned:
 248       //
 249       if (truncated_t && carry)
 250       {
 251          // We need to calculate 2^n + t - r
 252          // where n is the number of bits in this type.
 253          // Simplest way is to get 2^n - r by complementing
 254          // r, then add t to it.  Note that we can't call eval_complement
 255          // in case this is a signed checked type:
 256          for (std::size_t i = 0; i <= r_order; ++i)
 257             r.limbs()[i] = ~prem[i];
 258          r.normalize();
 259          eval_increment(r);
 260          eval_add(r, t);
 261          r_neg = !r_neg;
 262       }
 263       else if (r.compare(t) > 0)
 264       {
 265          eval_subtract(r, t);
 266       }
 267       else
 268       {
 269          r.swap(t);
 270          eval_subtract(r, t);
 271          prem  = r.limbs();
 272          r_neg = !r_neg;
 273       }
 274       //
 275       // First time through we need to strip any leading zero, otherwise
 276       // the termination condition goes belly-up:
 277       //
 278       if (result && first_pass)
 279       {
 280          first_pass = false;
 281          while (pr[result->size() - 1] == 0)
 282             result->resize(result->size() - 1, result->size() - 1);
 283       }
 284       //
 285       // Update r_order:
 286       //
 287       r_order = r.size() - 1;
 288       if (r_order < y_order)
 289          break;
 290    }
 291    // Termination condition is really just a check that r > y, but with a common
 292    // short-circuit case handled first:
 293    while ((r_order > y_order) || (r.compare_unsigned(y) >= 0));
 294
 295    //
 296    // We now just have to normalise the result:
 297    //
 298    if (r_neg && eval_get_sign(r))
 299    {
 300       // We have one too many in the result:
 301       if (result)
 302          eval_decrement(*result);
 303       if (y.sign())
 304       {
 305          r.negate();
 306          eval_subtract(r, y);
 307       }
 308       else
 309          eval_subtract(r, y, r);
 310    }
 311
 312    BOOST_MP_ASSERT(r.compare_unsigned(y) < 0); // remainder must be less than the divisor or our code has failed
 313 }
 314
 315 template <class CppInt1, class CppInt2>
 316 BOOST_MP_CXX14_CONSTEXPR void divide_unsigned_helper(
 317     CppInt1*       result,
 318     const CppInt2& x,
 319     limb_type      y,
 320     CppInt1&       r)
 321 {
 322    if (((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
 323    {
 324       CppInt2 t(x);
 325       divide_unsigned_helper(result, t, y, r);
 326       return;
 327    }
 328
 329    if (result == &r)
 330    {
 331       CppInt1 rem;
 332       divide_unsigned_helper(result, x, y, rem);
 333       r = rem;
 334       return;
 335    }
 336
 337    // As above, but simplified for integer divisor:
 338
 339    using default_ops::eval_subtract;
 340
 341    if (y == 0)
 342    {
 343       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Integer Division by zero."));
 344    }
 345    //
 346    // Find the most significant word of numerator.
 347    //
 348    std::size_t r_order = x.size() - 1;
 349
 350    //
 351    // Set remainder and result to their initial values:
 352    //
 353    r = x;
 354    r.sign(false);
 355    typename CppInt1::limb_pointer pr = r.limbs();
 356
 357    //
 358    // check for x < y, try to do this without actually having to
 359    // do a full comparison:
 360    //
 361    if ((r_order == 0) && (*pr < y))
 362    {
 363       if (result)
 364          *result = static_cast<limb_type>(0u);
 365       return;
 366    }
 367
 368    //
 369    // See if we can short-circuit long division, and use basic arithmetic instead:
 370    //
 371    if (r_order == 0)
 372    {
 373       if (result)
 374       {
 375          *result = *pr / y;
 376          result->sign(x.sign());
 377       }
 378       *pr %= y;
 379       r.sign(x.sign());
 380       return;
 381    }
 382    else if (r_order == 1)
 383    {
 384       double_limb_type a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[0];
 385       if (result)
 386       {
 387          *result = a / y;
 388          result->sign(x.sign());
 389       }
 390       r = a % y;
 391       r.sign(x.sign());
 392       return;
 393    }
 394
 395    // This is initialised just to keep the compiler from emitting useless warnings later on:
 396    typename CppInt1::limb_pointer pres = typename CppInt1::limb_pointer();
 397    if (result)
 398    {
 399       result->resize(r_order + 1, r_order + 1);
 400       pres = result->limbs();
 401       if (result->size() > r_order)
 402          pres[r_order] = 0; // just in case we don't set the most significant limb below.
 403    }
 404
 405    do
 406    {
 407       //
 408       // Calculate our best guess for how many times y divides into r:
 409       //
 410       if ((pr[r_order] < y) && r_order)
 411       {
 412          double_limb_type a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[r_order - 1];
 413          double_limb_type b = a % y;
 414          r.resize(r.size() - 1, r.size() - 1);
 415          --r_order;
 416          pr[r_order] = static_cast<limb_type>(b);
 417          if (result)
 418             pres[r_order] = static_cast<limb_type>(a / y);
 419          if (r_order && pr[r_order] == 0)
 420          {
 421             --r_order; // No remainder, division was exact.
 422             r.resize(r.size() - 1, r.size() - 1);
 423             if (result)
 424                pres[r_order] = static_cast<limb_type>(0u);
 425          }
 426       }
 427       else
 428       {
 429          if (result)
 430             pres[r_order] = pr[r_order] / y;
 431          pr[r_order] %= y;
 432          if (r_order && pr[r_order] == 0)
 433          {
 434             --r_order; // No remainder, division was exact.
 435             r.resize(r.size() - 1, r.size() - 1);
 436             if (result)
 437                pres[r_order] = static_cast<limb_type>(0u);
 438          }
 439       }
 440    }
 441    // Termination condition is really just a check that r >= y, but with two common
 442    // short-circuit cases handled first:
 443    while (r_order || (pr[r_order] >= y));
 444
 445    if (result)
 446    {
 447       result->normalize();
 448       result->sign(x.sign());
 449    }
 450    r.normalize();
 451    r.sign(x.sign());
 452
 453    BOOST_MP_ASSERT(r.compare(y) < 0); // remainder must be less than the divisor or our code has failed
 454 }
 455
 456 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
 457 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
 458 eval_divide(
 459     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 460     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 461     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
 462 {
 463    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
 464    bool                                                                 s = a.sign() != b.sign();
 465    divide_unsigned_helper(&result, a, b, r);
 466    result.sign(s);
 467 }
 468
 469 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 470 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 471 eval_divide(
 472     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 473     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 474     limb_type&                                                                  b)
 475 {
 476    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
 477    bool                                                                 s = a.sign();
 478    divide_unsigned_helper(&result, a, b, r);
 479    result.sign(s);
 480 }
 481
 482 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 483 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 484 eval_divide(
 485     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 486     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 487     signed_limb_type&                                                           b)
 488 {
 489    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
 490    bool                                                                 s = a.sign() != (b < 0);
 491    divide_unsigned_helper(&result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(b)), r);
 492    result.sign(s);
 493 }
 494
 495 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 496 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 497 eval_divide(
 498     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 499     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
 500 {
 501    // There is no in place divide:
 502    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
 503    eval_divide(result, a, b);
 504 }
 505
 506 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 507 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 508 eval_divide(
 509     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 510     limb_type                                                             b)
 511 {
 512    // There is no in place divide:
 513    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
 514    eval_divide(result, a, b);
 515 }
 516
 517 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 518 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 519 eval_divide(
 520     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 521     signed_limb_type                                                      b)
 522 {
 523    // There is no in place divide:
 524    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
 525    eval_divide(result, a, b);
 526 }
 527
 528 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
 529 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
 530 eval_modulus(
 531     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 532     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 533     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
 534 {
 535    bool s = a.sign();
 536    if (b.size() == 1)
 537       eval_modulus(result, a, *b.limbs());
 538    else
 539       divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>*>(0), a, b, result);
 540    result.sign(s);
 541 }
 542
 543 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 544 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 545 eval_modulus(
 546     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 547     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 548     const limb_type                                                             mod)
 549 {
 550    const std::ptrdiff_t n = a.size();
 551    const double_limb_type two_n_mod = static_cast<limb_type>(1u) + (~static_cast<limb_type>(0u) - mod) % mod;
 552    limb_type              res       = a.limbs()[n - 1] % mod;
 553
 554    for (std::ptrdiff_t i = n - 2; i >= 0; --i)
 555       res = (res * two_n_mod + a.limbs()[i]) % mod;
 556    //
 557    // We must not modify result until here in case
 558    // result and a are the same object:
 559    //
 560    result.resize(1, 1);
 561    *result.limbs() = res;
 562    result.sign(a.sign());
 563 }
 564
 565 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 566 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 567 eval_modulus(
 568    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 569    const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 570    signed_limb_type                                                            b)
 571 {
 572    const limb_type t = b < 0 ? -b : b;
 573    eval_modulus(result, a, t);
 574    result.sign(a.sign());
 575 }
 576
 577 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 578 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 579 eval_modulus(
 580     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 581     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
 582 {
 583    // There is no in place divide:
 584    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
 585    eval_modulus(result, a, b);
 586 }
 587
 588 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 589 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 590 eval_modulus(
 591     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 592     limb_type                                                             b)
 593 {
 594    // Single limb modulus is in place:
 595    eval_modulus(result, result, b);
 596 }
 597
 598 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 599 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 600 eval_modulus(
 601     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 602     signed_limb_type                                                      b)
 603 {
 604    // Single limb modulus is in place:
 605    eval_modulus(result, result, b);
 606 }
 607
 608 //
 609 // Over again for trivial cpp_int's:
 610 //
 611 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 612 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 613     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)>::type
 614 eval_divide(
 615     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 616     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
 617 {
 618    if (!*o.limbs())
 619       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Division by zero."));
 620    *result.limbs() /= *o.limbs();
 621    result.sign(result.sign() != o.sign());
 622 }
 623
 624 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 625 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 626     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 627 eval_divide(
 628     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 629     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
 630 {
 631    if (!*o.limbs())
 632       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Division by zero."));
 633    *result.limbs() /= *o.limbs();
 634 }
 635
 636 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 637 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 638     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 639 eval_modulus(
 640     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 641     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
 642 {
 643    if (!*o.limbs())
 644       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Division by zero."));
 645    *result.limbs() %= *o.limbs();
 646    result.sign(result.sign());
 647 }
 648
 649 }}} // namespace boost::multiprecision::backends
 650
 651 #endif