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

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2012-20 John Maddock.
   3 //  Copyright 2019-20 Christopher Kormanyos.
   4 //  Copyright 2019-20 Madhur Chauhan.
   5 //  Distributed under the Boost Software License, Version 1.0.
   6 //  (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   7 //
   8 // Comparison operators for cpp_int_backend:
   9 //
  10 #ifndef BOOST_MP_CPP_INT_MUL_HPP
  11 #define BOOST_MP_CPP_INT_MUL_HPP
  12
  13 #include <limits>
  14 #include <boost/multiprecision/detail/standalone_config.hpp>
  15 #include <boost/multiprecision/detail/endian.hpp>
  16 #include <boost/multiprecision/detail/assert.hpp>
  17 #include <boost/multiprecision/integer.hpp>
  18
  19 namespace boost { namespace multiprecision { namespace backends {
  20
  21 #ifdef BOOST_MSVC
  22 #pragma warning(push)
  23 #pragma warning(disable : 4127) // conditional expression is constant
  24 #endif
  25 //
  26 // Multiplication by a single limb:
  27 //
  28 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>
  29 inline 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
  30 eval_multiply(
  31     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
  32     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
  33     const limb_type&                                                            val) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
  34 {
  35    if (!val)
  36    {
  37       result = static_cast<limb_type>(0);
  38       return;
  39    }
  40    if ((void*)&a != (void*)&result)
  41       result.resize(a.size(), a.size());
  42    double_limb_type                                                                                  carry = 0;
  43    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer       p     = result.limbs();
  44    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer       pe    = result.limbs() + result.size();
  45    typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa    = a.limbs();
  46    while (p != pe)
  47    {
  48       carry += static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(val);
  49 #ifdef __MSVC_RUNTIME_CHECKS
  50       *p = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
  51 #else
  52       *p = static_cast<limb_type>(carry);
  53 #endif
  54       carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
  55       ++p, ++pa;
  56    }
  57    if (carry)
  58    {
  59       std::size_t i = result.size();
  60       result.resize(i + 1, i + 1);
  61       if (result.size() > i)
  62          result.limbs()[i] = static_cast<limb_type>(carry);
  63    }
  64    result.sign(a.sign());
  65    if (is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
  66       result.normalize();
  67 }
  68
  69 //
  70 // resize_for_carry forces a resize of the underlying buffer only if a previous request
  71 // for "required" elements could possibly have failed, *and* we have checking enabled.
  72 // This will cause an overflow error inside resize():
  73 //
  74 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
  75 inline BOOST_MP_CXX14_CONSTEXPR void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& /*result*/, std::size_t /*required*/) {}
  76
  77 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, class Allocator1>
  78 inline BOOST_MP_CXX14_CONSTEXPR void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, checked, Allocator1>& result, std::size_t required)
  79 {
  80    if (result.size() < required)
  81       result.resize(required, required);
  82 }
  83 //
  84 // Minimum number of limbs required for Karatsuba to be worthwhile:
  85 //
  86 #ifdef BOOST_MP_KARATSUBA_CUTOFF
  87 const size_t karatsuba_cutoff = BOOST_MP_KARATSUBA_CUTOFF;
  88 #else
  89 const size_t karatsuba_cutoff = 40;
  90 #endif
  91 //
  92 // Core (recursive) Karatsuba multiplication, all the storage required is allocated upfront and
  93 // passed down the stack in this routine.  Note that all the cpp_int_backend's must be the same type
  94 // and full variable precision.  Karatsuba really doesn't play nice with fixed-size integers.  If necessary
  95 // fixed precision integers will get aliased as variable-precision types before this is called.
  96 //
  97 template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
  98 inline void multiply_karatsuba(
  99     cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>&       result,
 100     const cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>& a,
 101     const cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>& b,
 102     typename cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>::scoped_shared_storage& storage)
 103 {
 104    using cpp_int_type = cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>;
 105
 106    std::size_t as = a.size();
 107    std::size_t bs = b.size();
 108    //
 109    // Termination condition: if either argument is smaller than karatsuba_cutoff
 110    // then schoolboy multiplication will be faster:
 111    //
 112    if ((as < karatsuba_cutoff) || (bs < karatsuba_cutoff))
 113    {
 114       eval_multiply(result, a, b);
 115       return;
 116    }
 117    //
 118    // Partitioning size: split the larger of a and b into 2 halves
 119    //
 120    std::size_t n  = (as > bs ? as : bs) / 2 + 1;
 121    //
 122    // Partition a and b into high and low parts.
 123    // ie write a, b as a = a_h * 2^n + a_l, b = b_h * 2^n + b_l
 124    //
 125    // We could copy the high and low parts into new variables, but we'll
 126    // use aliasing to reference the internal limbs of a and b.  There is one wart here:
 127    // if a and b are mismatched in size, then n may be larger than the smaller
 128    // of a and b.  In that situation the high part is zero, and we have no limbs
 129    // to alias, so instead alias a local variable.
 130    // This raises 2 questions:
 131    // * Is this the best way to partition a and b?
 132    // * Since we have one high part zero, the arithmetic simplifies considerably,
 133    //   so should we have a special routine for this?
 134    //
 135    std::size_t          sz = (std::min)(as, n);
 136    const cpp_int_type a_l(a.limbs(), 0, sz);
 137
 138    sz = (std::min)(bs, n);
 139    const cpp_int_type b_l(b.limbs(), 0, sz);
 140
 141    limb_type          zero = 0;
 142    const cpp_int_type a_h(as > n ? a.limbs() + n : &zero, 0, as > n ? as - n : 1);
 143    const cpp_int_type b_h(bs > n ? b.limbs() + n : &zero, 0, bs > n ? bs - n : 1);
 144    //
 145    // The basis for the Karatsuba algorithm is as follows:
 146    //
 147    // let                x = a_h * b_ h
 148    //                    y = a_l * b_l
 149    //                    z = (a_h + a_l)*(b_h + b_l) - x - y
 150    // and therefore  a * b = x * (2 ^ (2 * n))+ z * (2 ^ n) + y
 151    //
 152    // Begin by allocating our temporaries, these alias the memory already allocated in the shared storage:
 153    //
 154    cpp_int_type t1(storage, 2 * n + 2);
 155    cpp_int_type t2(storage, n + 1);
 156    cpp_int_type t3(storage, n + 1);
 157    //
 158    // Now we want:
 159    //
 160    // result = | a_h*b_h  | a_l*b_l |
 161    // (bits)              <-- 2*n -->
 162    //
 163    // We create aliases for the low and high parts of result, and multiply directly into them:
 164    //
 165    cpp_int_type result_low(result.limbs(), 0, 2 * n);
 166    cpp_int_type result_high(result.limbs(), 2 * n, result.size() - 2 * n);
 167    //
 168    // low part of result is a_l * b_l:
 169    //
 170    multiply_karatsuba(result_low, a_l, b_l, storage);
 171    //
 172    // We haven't zeroed out memory in result, so set to zero any unused limbs,
 173    // if a_l and b_l have mostly random bits then nothing happens here, but if
 174    // one is zero or nearly so, then a memset might be faster... it's not clear
 175    // that it's worth the extra logic though (and is darn hard to measure
 176    // what the "average" case is).
 177    //
 178    for (std::size_t i = result_low.size(); i < 2 * n; ++i)
 179       result.limbs()[i] = 0;
 180    //
 181    // Set the high part of result to a_h * b_h:
 182    //
 183    multiply_karatsuba(result_high, a_h, b_h, storage);
 184    for (std::size_t i = result_high.size() + 2 * n; i < result.size(); ++i)
 185       result.limbs()[i] = 0;
 186    //
 187    // Now calculate (a_h+a_l)*(b_h+b_l):
 188    //
 189    add_unsigned(t2, a_l, a_h);
 190    add_unsigned(t3, b_l, b_h);
 191    multiply_karatsuba(t1, t2, t3, storage); // t1 = (a_h+a_l)*(b_h+b_l)
 192    //
 193    // There is now a slight deviation from Karatsuba, we want to subtract
 194    // a_l*b_l + a_h*b_h from t1, but rather than use an addition and a subtraction
 195    // plus one temporary, we'll use 2 subtractions.  On the minus side, a subtraction
 196    // is on average slightly slower than an addition, but we save a temporary (ie memory)
 197    // and also hammer the same piece of memory over and over rather than 2 disparate
 198    // memory regions.  Overall it seems to be a slight win.
 199    //
 200    subtract_unsigned(t1, t1, result_high);
 201    subtract_unsigned(t1, t1, result_low);
 202    //
 203    // The final step is to left shift t1 by n bits and add to the result.
 204    // Rather than do an actual left shift, we can simply alias the result
 205    // and add to the alias:
 206    //
 207    cpp_int_type result_alias(result.limbs(), n, result.size() - n);
 208    add_unsigned(result_alias, result_alias, t1);
 209    //
 210    // Free up storage for use by sister branches to this one:
 211    //
 212    storage.deallocate(t1.capacity() + t2.capacity() + t3.capacity());
 213
 214    result.normalize();
 215 }
 216
 217 inline std::size_t karatsuba_storage_size(std::size_t s)
 218 {
 219    //
 220    // This estimates how much memory we will need based on
 221    // s-limb multiplication.  In an ideal world the number of limbs
 222    // would halve with each recursion, and our storage requirements
 223    // would be 4s in the limit, and rather less in practice since
 224    // we bail out long before we reach one limb.  In the real world
 225    // we don't quite halve s in each recursion, so this is an heuristic
 226    // which over-estimates how much we need.  We could compute an exact
 227    // value, but it would be rather time consuming.
 228    //
 229    return 5 * s;
 230 }
 231 //
 232 // There are 2 entry point routines for Karatsuba multiplication:
 233 // one for variable precision types, and one for fixed precision types.
 234 // These are responsible for allocating all the storage required for the recursive
 235 // routines above, and are always at the outermost level.
 236 //
 237 // Normal variable precision case comes first:
 238 //
 239 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
 240 inline typename std::enable_if<!is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>::type
 241 setup_karatsuba(
 242    cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result,
 243    const cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& a,
 244    const cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& b)
 245 {
 246    std::size_t as = a.size();
 247    std::size_t bs = b.size();
 248    std::size_t s = as > bs ? as : bs;
 249    std::size_t storage_size = karatsuba_storage_size(s);
 250    if (storage_size < 300)
 251    {
 252       //
 253       // Special case: if we don't need too much memory, we can use stack based storage
 254       // and save a call to the allocator, this allows us to use Karatsuba multiply
 255       // at lower limb counts than would otherwise be possible:
 256       //
 257       limb_type limbs[300];
 258       typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::scoped_shared_storage storage(limbs, storage_size);
 259       multiply_karatsuba(result, a, b, storage);
 260    }
 261    else
 262    {
 263       typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::scoped_shared_storage storage(result.allocator(), storage_size);
 264       multiply_karatsuba(result, a, b, storage);
 265    }
 266 }
 267
 268 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>
 269 inline typename std::enable_if<is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_fixed_precision<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value || is_fixed_precision<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
 270 setup_karatsuba(
 271     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 272     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 273     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
 274 {
 275    //
 276    // Now comes the fixed precision case.
 277    // In fact Karatsuba doesn't really work with fixed precision since the logic
 278    // requires that we calculate all the bits of the result (especially in the
 279    // temporaries used internally).  So... we'll convert all the arguments
 280    // to variable precision types by aliasing them, this also
 281    // reduce the number of template instantations:
 282    //
 283    using variable_precision_type = cpp_int_backend<0, 0, signed_magnitude, unchecked, std::allocator<limb_type> >;
 284    variable_precision_type a_t(a.limbs(), 0, a.size()), b_t(b.limbs(), 0, b.size());
 285    std::size_t as = a.size();
 286    std::size_t bs = b.size();
 287    std::size_t s = as > bs ? as : bs;
 288    std::size_t sz = as + bs;
 289    std::size_t storage_size = karatsuba_storage_size(s);
 290
 291    if (!is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || (sz * sizeof(limb_type) * CHAR_BIT <= MaxBits1))
 292    {
 293       // Result is large enough for all the bits of the result, so we can use aliasing:
 294       result.resize(sz, sz);
 295       variable_precision_type t(result.limbs(), 0, result.size());
 296       typename variable_precision_type::scoped_shared_storage storage(t.allocator(), storage_size);
 297       multiply_karatsuba(t, a_t, b_t, storage);
 298       result.resize(t.size(), t.size());
 299    }
 300    else
 301    {
 302       //
 303       // Not enough bit in result for the answer, so we must use a temporary
 304       // and then truncate (ie modular arithmetic):
 305       //
 306       typename variable_precision_type::scoped_shared_storage storage(variable_precision_type::allocator_type(), sz + storage_size);
 307       variable_precision_type t(storage, sz);
 308       multiply_karatsuba(t, a_t, b_t, storage);
 309       //
 310       // If there is truncation, and result is a checked type then this will throw:
 311       //
 312       result = t;
 313    }
 314 }
 315 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>
 316 inline typename std::enable_if<!is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_fixed_precision<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_fixed_precision<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
 317 setup_karatsuba(
 318    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 319    const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 320    const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
 321 {
 322    //
 323    // Variable precision, mixed arguments, just alias and forward:
 324    //
 325    using variable_precision_type = cpp_int_backend<0, 0, signed_magnitude, unchecked, std::allocator<limb_type> >;
 326    variable_precision_type a_t(a.limbs(), 0, a.size()), b_t(b.limbs(), 0, b.size());
 327    std::size_t as = a.size();
 328    std::size_t bs = b.size();
 329    std::size_t s = as > bs ? as : bs;
 330    std::size_t sz = as + bs;
 331    std::size_t storage_size = karatsuba_storage_size(s);
 332
 333    result.resize(sz, sz);
 334    variable_precision_type t(result.limbs(), 0, result.size());
 335    typename variable_precision_type::scoped_shared_storage storage(t.allocator(), storage_size);
 336    multiply_karatsuba(t, a_t, b_t, storage);
 337 }
 338
 339 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>
 340 inline BOOST_MP_CXX14_CONSTEXPR void
 341 eval_multiply_comba(
 342     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 343     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 344     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 345 {
 346    //
 347    // see PR #182
 348    // Comba Multiplier - based on Paul Comba's
 349    // Exponentiation cryptosystems on the IBM PC, 1990
 350    //
 351    std::ptrdiff_t as                                                                                         = a.size(),
 352        bs                                                                                         = b.size(),
 353        rs                                                                                         = result.size();
 354    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
 355
 356    double_limb_type carry    = 0,
 357                     temp     = 0;
 358    limb_type      overflow   = 0;
 359    const std::size_t limb_bits  = sizeof(limb_type) * CHAR_BIT;
 360    const bool     must_throw = rs < as + bs - 1;
 361    for (std::ptrdiff_t r = 0, lim = (std::min)(rs, as + bs - 1); r < lim; ++r, overflow = 0)
 362    {
 363       std::ptrdiff_t i = r >= as ? as - 1 : r,
 364           j = r - i,
 365           k = i < bs - j ? i + 1 : bs - j; // min(i+1, bs-j);
 366
 367       typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs() + i;
 368       typename cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>::const_limb_pointer pb = b.limbs() + j;
 369
 370       temp = carry;
 371       carry += static_cast<double_limb_type>(*(pa)) * (*(pb));
 372       overflow += carry < temp;
 373       for (--k; k; k--)
 374       {
 375          temp = carry;
 376          carry += static_cast<double_limb_type>(*(--pa)) * (*(++pb));
 377          overflow += carry < temp;
 378       }
 379       *(pr++) = static_cast<limb_type>(carry);
 380       carry   = (static_cast<double_limb_type>(overflow) << limb_bits) | (carry >> limb_bits);
 381    }
 382    if (carry || must_throw)
 383    {
 384       resize_for_carry(result, as + bs);
 385       if (static_cast<int>(result.size()) >= as + bs)
 386          *pr = static_cast<limb_type>(carry);
 387    }
 388 }
 389 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>
 390 inline 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
 391 eval_multiply(
 392     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 393     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 394     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
 395    noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
 396       && (karatsuba_cutoff * sizeof(limb_type) * CHAR_BIT > MaxBits1)
 397       && (karatsuba_cutoff * sizeof(limb_type)* CHAR_BIT > MaxBits2)
 398       && (karatsuba_cutoff * sizeof(limb_type)* CHAR_BIT > MaxBits3)))
 399 {
 400    // Uses simple (O(n^2)) multiplication when the limbs are less
 401    // otherwise switches to karatsuba algorithm based on experimental value (~40 limbs)
 402    //
 403    // Trivial cases first:
 404    //
 405    std::size_t                                                                                          as = a.size();
 406    std::size_t                                                                                          bs = b.size();
 407    typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs();
 408    typename cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>::const_limb_pointer pb = b.limbs();
 409    if (as == 1)
 410    {
 411       bool s = b.sign() != a.sign();
 412       if (bs == 1)
 413       {
 414          result = static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(*pb);
 415       }
 416       else
 417       {
 418          limb_type l = *pa;
 419          eval_multiply(result, b, l);
 420       }
 421       result.sign(s);
 422       return;
 423    }
 424    if (bs == 1)
 425    {
 426       bool      s = b.sign() != a.sign();
 427       limb_type l = *pb;
 428       eval_multiply(result, a, l);
 429       result.sign(s);
 430       return;
 431    }
 432
 433    if ((void*)&result == (void*)&a)
 434    {
 435       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(a);
 436       eval_multiply(result, t, b);
 437       return;
 438    }
 439    if ((void*)&result == (void*)&b)
 440    {
 441       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(b);
 442       eval_multiply(result, a, t);
 443       return;
 444    }
 445
 446    constexpr const double_limb_type limb_max = ~static_cast<limb_type>(0u);
 447    constexpr const double_limb_type double_limb_max = ~static_cast<double_limb_type>(0u);
 448
 449    result.resize(as + bs, as + bs - 1);
 450 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 451    if (!BOOST_MP_IS_CONST_EVALUATED(as) && (as >= karatsuba_cutoff && bs >= karatsuba_cutoff))
 452 #else
 453    if (as >= karatsuba_cutoff && bs >= karatsuba_cutoff)
 454 #endif
 455    {
 456       setup_karatsuba(result, a, b);
 457       //
 458       // Set the sign of the result:
 459       //
 460       result.sign(a.sign() != b.sign());
 461       return;
 462    }
 463    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
 464    static_assert(double_limb_max - 2 * limb_max >= limb_max * limb_max, "failed limb size sanity check");
 465
 466 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 467    if (BOOST_MP_IS_CONST_EVALUATED(as))
 468    {
 469       for (std::size_t i = 0; i < result.size(); ++i)
 470          pr[i] = 0;
 471    }
 472    else
 473 #endif
 474    std::memset(pr, 0, result.size() * sizeof(limb_type));
 475
 476 #if defined(BOOST_MP_COMBA)
 477        //
 478        // Comba Multiplier might not be efficient because of less efficient assembly
 479        // by the compiler as of 09/01/2020 (DD/MM/YY). See PR #182
 480        // Till then this will lay dormant :(
 481        //
 482        eval_multiply_comba(result, a, b);
 483 #else
 484
 485    double_limb_type carry = 0;
 486    for (std::size_t i = 0; i < as; ++i)
 487    {
 488       BOOST_MP_ASSERT(result.size() > i);
 489       std::size_t inner_limit = !is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value ? bs : (std::min)(result.size() - i, bs);
 490       std::size_t j           = 0;
 491       for (; j < inner_limit; ++j)
 492       {
 493          BOOST_MP_ASSERT(i + j < result.size());
 494 #if (!defined(__GLIBCXX__) && !defined(__GLIBCPP__)) || !BOOST_WORKAROUND(BOOST_GCC_VERSION, <= 50100)
 495          BOOST_MP_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized || ((std::numeric_limits<double_limb_type>::max)() - carry >
 496                                                                                  static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value) * static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value)));
 497 #endif
 498          carry += static_cast<double_limb_type>(pa[i]) * static_cast<double_limb_type>(pb[j]);
 499          BOOST_MP_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized || ((std::numeric_limits<double_limb_type>::max)() - carry >= pr[i + j]));
 500          carry += pr[i + j];
 501 #ifdef __MSVC_RUNTIME_CHECKS
 502          pr[i + j] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 503 #else
 504          pr[i + j] = static_cast<limb_type>(carry);
 505 #endif
 506          carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 507          BOOST_MP_ASSERT(carry <= (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value));
 508       }
 509       if (carry)
 510       {
 511          resize_for_carry(result, i + j + 1); // May throw if checking is enabled
 512          if (i + j < result.size())
 513 #ifdef __MSVC_RUNTIME_CHECKS
 514             pr[i + j] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 515 #else
 516             pr[i + j] = static_cast<limb_type>(carry);
 517 #endif
 518       }
 519       carry = 0;
 520    }
 521 #endif // ifdef(BOOST_MP_COMBA) ends
 522
 523    result.normalize();
 524    //
 525    // Set the sign of the result:
 526    //
 527    result.sign(a.sign() != b.sign());
 528 }
 529
 530 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>
 531 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
 532 eval_multiply(
 533     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 534     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a)
 535    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>()))))
 536 {
 537    eval_multiply(result, result, a);
 538 }
 539
 540 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 541 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
 542 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const limb_type& val)
 543    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>()))))
 544 {
 545    eval_multiply(result, result, val);
 546 }
 547
 548 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>
 549 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
 550 eval_multiply(
 551     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 552     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 553     const double_limb_type&                                                     val)
 554    noexcept(
 555       (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>())))
 556       && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
 557    )
 558 {
 559    if (val <= (std::numeric_limits<limb_type>::max)())
 560    {
 561       eval_multiply(result, a, static_cast<limb_type>(val));
 562    }
 563    else
 564    {
 565 #if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
 566       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
 567 #else
 568       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
 569       t = val;
 570 #endif
 571       eval_multiply(result, a, t);
 572    }
 573 }
 574
 575 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 576 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
 577 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const double_limb_type& val)
 578    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const double_limb_type&>()))))
 579 {
 580    eval_multiply(result, result, val);
 581 }
 582
 583 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>
 584 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
 585 eval_multiply(
 586     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 587     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 588     const signed_limb_type&                                                     val)
 589    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>()))))
 590 {
 591    if (val > 0)
 592       eval_multiply(result, a, static_cast<limb_type>(val));
 593    else
 594    {
 595       eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
 596       result.negate();
 597    }
 598 }
 599
 600 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 601 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
 602 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_limb_type& val)
 603    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>()))))
 604 {
 605    eval_multiply(result, result, val);
 606 }
 607
 608 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>
 609 inline 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
 610 eval_multiply(
 611     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 612     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
 613     const signed_double_limb_type&                                              val)
 614    noexcept(
 615    (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>())))
 616       && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
 617    )
 618 {
 619    if (val > 0)
 620    {
 621       if (val <= (std::numeric_limits<limb_type>::max)())
 622       {
 623          eval_multiply(result, a, static_cast<limb_type>(val));
 624          return;
 625       }
 626    }
 627    else if (val >= -static_cast<signed_double_limb_type>((std::numeric_limits<limb_type>::max)()))
 628    {
 629       eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
 630       result.negate();
 631       return;
 632    }
 633 #if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
 634    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
 635 #else
 636    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
 637    t = val;
 638 #endif
 639    eval_multiply(result, a, t);
 640 }
 641
 642 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 643 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
 644 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_double_limb_type& val)
 645    noexcept(
 646    (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>())))
 647    && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
 648    )
 649 {
 650    eval_multiply(result, result, val);
 651 }
 652
 653 //
 654 // Now over again for trivial cpp_int's:
 655 //
 656 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 657 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 658     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
 659 eval_multiply(
 660     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 661     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 662 {
 663    *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 664    result.sign(result.sign() != o.sign());
 665    result.normalize();
 666 }
 667
 668 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 669 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 670     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>::type
 671 eval_multiply(
 672     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 673     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 674 {
 675    *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 676    result.normalize();
 677 }
 678
 679 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 680 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 681     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
 682 eval_multiply(
 683     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 684     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 685     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 686 {
 687    *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 688    result.sign(a.sign() != b.sign());
 689    result.normalize();
 690 }
 691
 692 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 693 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 694     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>::type
 695 eval_multiply(
 696     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 697     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 698     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 699 {
 700    *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 701    result.normalize();
 702 }
 703
 704 //
 705 // Special routines for multiplying two integers to obtain a multiprecision result:
 706 //
 707 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 708 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 709     !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 710 eval_multiply(
 711     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 712     signed_double_limb_type a, signed_double_limb_type b)
 713 {
 714    constexpr const signed_double_limb_type mask = ~static_cast<limb_type>(0);
 715    constexpr const std::size_t limb_bits = sizeof(limb_type) * CHAR_BIT;
 716
 717    bool s = false;
 718    if (a < 0)
 719    {
 720       a = -a;
 721       s = true;
 722    }
 723    if (b < 0)
 724    {
 725       b = -b;
 726       s = !s;
 727    }
 728    double_limb_type w = a & mask;
 729    double_limb_type x = a >> limb_bits;
 730    double_limb_type y = b & mask;
 731    double_limb_type z = b >> limb_bits;
 732
 733    result.resize(4, 4);
 734    limb_type* pr = result.limbs();
 735
 736    double_limb_type carry = w * y;
 737 #ifdef __MSVC_RUNTIME_CHECKS
 738    pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 739    carry >>= limb_bits;
 740    carry += w * z + x * y;
 741    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 742    carry >>= limb_bits;
 743    carry += x * z;
 744    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 745    pr[3] = static_cast<limb_type>(carry >> limb_bits);
 746 #else
 747    pr[0] = static_cast<limb_type>(carry);
 748    carry >>= limb_bits;
 749    carry += w * z + x * y;
 750    pr[1] = static_cast<limb_type>(carry);
 751    carry >>= limb_bits;
 752    carry += x * z;
 753    pr[2] = static_cast<limb_type>(carry);
 754    pr[3] = static_cast<limb_type>(carry >> limb_bits);
 755 #endif
 756    result.sign(s);
 757    result.normalize();
 758 }
 759
 760 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 761 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 762     !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 763 eval_multiply(
 764     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 765     double_limb_type a, double_limb_type b)
 766 {
 767    constexpr const signed_double_limb_type mask = ~static_cast<limb_type>(0);
 768    constexpr const std::size_t limb_bits = sizeof(limb_type) * CHAR_BIT;
 769
 770    double_limb_type w = a & mask;
 771    double_limb_type x = a >> limb_bits;
 772    double_limb_type y = b & mask;
 773    double_limb_type z = b >> limb_bits;
 774
 775    result.resize(4, 4);
 776    limb_type* pr = result.limbs();
 777
 778    double_limb_type carry = w * y;
 779 #ifdef __MSVC_RUNTIME_CHECKS
 780    pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 781    carry >>= limb_bits;
 782    carry += w * z;
 783    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 784    carry >>= limb_bits;
 785    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 786    carry = x * y + pr[1];
 787    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 788    carry >>= limb_bits;
 789    carry += pr[2] + x * z;
 790    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
 791    pr[3] = static_cast<limb_type>(carry >> limb_bits);
 792 #else
 793    pr[0] = static_cast<limb_type>(carry);
 794    carry >>= limb_bits;
 795    carry += w * z;
 796    pr[1] = static_cast<limb_type>(carry);
 797    carry >>= limb_bits;
 798    pr[2] = static_cast<limb_type>(carry);
 799    carry = x * y + pr[1];
 800    pr[1] = static_cast<limb_type>(carry);
 801    carry >>= limb_bits;
 802    carry += pr[2] + x * z;
 803    pr[2] = static_cast<limb_type>(carry);
 804    pr[3] = static_cast<limb_type>(carry >> limb_bits);
 805 #endif
 806    result.sign(false);
 807    result.normalize();
 808 }
 809
 810 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1,
 811           std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 812 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
 813     !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<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
 814 eval_multiply(
 815     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
 816     cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& a,
 817     cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& b)
 818 {
 819    using canonical_type = typename boost::multiprecision::detail::canonical<typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type, cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::type;
 820    eval_multiply(result, static_cast<canonical_type>(*a.limbs()), static_cast<canonical_type>(*b.limbs()));
 821    result.sign(a.sign() != b.sign());
 822 }
 823
 824 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class SI>
 825 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (sizeof(SI) <= sizeof(signed_double_limb_type) / 2)>::type
 826 eval_multiply(
 827     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 828     SI a, SI b)
 829 {
 830    result = static_cast<signed_double_limb_type>(a) * static_cast<signed_double_limb_type>(b);
 831 }
 832
 833 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class UI>
 834 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (sizeof(UI) <= sizeof(signed_double_limb_type) / 2)>::type
 835 eval_multiply(
 836     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 837     UI a, UI b)
 838 {
 839    result = static_cast<double_limb_type>(a) * static_cast<double_limb_type>(b);
 840 }
 841
 842 #ifdef BOOST_MSVC
 843 #pragma warning(pop)
 844 #endif
 845
 846 }}} // namespace boost::multiprecision::backends
 847
 848 #endif