ceph/src/boost/libs/multiprecision/include/boost/multiprecision/cpp_int/misc.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 http://www.boost.org/LICENSE_1_
   5 //
   6 // Comparison operators for cpp_int_backend:
   7 //
   8 #ifndef BOOST_MP_CPP_INT_MISC_HPP
   9 #define BOOST_MP_CPP_INT_MISC_HPP
  10
  11 #include <boost/multiprecision/detail/bitscan.hpp> // lsb etc
  12 #include <boost/integer/common_factor_rt.hpp> // gcd/lcm
  13 #include <boost/functional/hash_fwd.hpp>
  14
  15 #ifdef BOOST_MSVC
  16 #pragma warning(push)
  17 #pragma warning(disable:4702)
  18 #pragma warning(disable:4127) // conditional expression is constant
  19 #pragma warning(disable:4146) // unary minus operator applied to unsigned type, result still unsigned
  20 #endif
  21
  22
  23 namespace boost{ namespace multiprecision{ namespace backends{
  24
  25 template <class R, class CppInt>
  26 void check_in_range(const CppInt& val, const mpl::int_<checked>&)
  27 {
  28    typedef typename boost::multiprecision::detail::canonical<R, CppInt>::type cast_type;
  29    if(val.sign())
  30    {
  31       if(val.compare(static_cast<cast_type>((std::numeric_limits<R>::min)())) < 0)
  32          BOOST_THROW_EXCEPTION(std::overflow_error("Could not convert to the target type - -value is out of range."));
  33    }
  34    else
  35    {
  36       if(val.compare(static_cast<cast_type>((std::numeric_limits<R>::max)())) > 0)
  37          BOOST_THROW_EXCEPTION(std::overflow_error("Could not convert to the target type - -value is out of range."));
  38    }
  39 }
  40 template <class R, class CppInt>
  41 inline void check_in_range(const CppInt& /*val*/, const mpl::int_<unchecked>&) BOOST_NOEXCEPT {}
  42
  43 inline void check_is_negative(const mpl::true_&) BOOST_NOEXCEPT {}
  44 inline void check_is_negative(const mpl::false_&)
  45 {
  46    BOOST_THROW_EXCEPTION(std::range_error("Attempt to assign a negative value to an unsigned type."));
  47 }
  48
  49 template <class Integer>
  50 inline Integer negate_integer(Integer i, const mpl::true_&) BOOST_NOEXCEPT
  51 {
  52    return -i;
  53 }
  54 template <class Integer>
  55 inline Integer negate_integer(Integer i, const mpl::false_&) BOOST_NOEXCEPT
  56 {
  57    return ~(i-1);
  58 }
  59
  60 template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
  61 inline typename enable_if_c<is_integral<R>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, void>::type
  62    eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& backend) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
  63 {
  64    typedef mpl::int_<Checked1> checked_type;
  65    check_in_range<R>(backend, checked_type());
  66
  67    *result = static_cast<R>(backend.limbs()[0]);
  68    unsigned shift = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
  69    for(unsigned i = 1; (i < backend.size()) && (shift < static_cast<unsigned>(std::numeric_limits<R>::digits)); ++i)
  70    {
  71       *result += static_cast<R>(backend.limbs()[i]) << shift;
  72       shift += cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
  73    }
  74    if(backend.sign())
  75    {
  76       check_is_negative(boost::is_signed<R>());
  77       *result = negate_integer(*result, boost::is_signed<R>());
  78    }
  79 }
  80
  81 template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
  82 inline typename enable_if_c<is_floating_point<R>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, void>::type
  83    eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& backend) BOOST_MP_NOEXCEPT_IF(is_arithmetic<R>::value)
  84 {
  85    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::const_limb_pointer p = backend.limbs();
  86    unsigned shift = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
  87    *result = static_cast<R>(*p);
  88    for(unsigned i = 1; i < backend.size(); ++i)
  89    {
  90       *result += static_cast<R>(std::ldexp(static_cast<long double>(p[i]), shift));
  91       shift += cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
  92    }
  93    if(backend.sign())
  94       *result = -*result;
  95 }
  96
  97 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
  98 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, bool>::type
  99    eval_is_zero(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT
 100 {
 101    return (val.size() == 1) && (val.limbs()[0] == 0);
 102 }
 103 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 104 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, int>::type
 105    eval_get_sign(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT
 106 {
 107    return eval_is_zero(val) ? 0 : val.sign() ? -1 : 1;
 108 }
 109 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 110 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 111    eval_abs(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 112 {
 113    result = val;
 114    result.sign(false);
 115 }
 116
 117 //
 118 // Get the location of the least-significant-bit:
 119 //
 120 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 121 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 122    eval_lsb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 123 {
 124    using default_ops::eval_get_sign;
 125    if(eval_get_sign(a) == 0)
 126    {
 127       BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
 128    }
 129    if(a.sign())
 130    {
 131       BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
 132    }
 133
 134    //
 135    // Find the index of the least significant limb that is non-zero:
 136    //
 137    unsigned index = 0;
 138    while(!a.limbs()[index] && (index < a.size()))
 139       ++index;
 140    //
 141    // Find the index of the least significant bit within that limb:
 142    //
 143    unsigned result = boost::multiprecision::detail::find_lsb(a.limbs()[index]);
 144
 145    return result + index * cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 146 }
 147
 148 //
 149 // Get the location of the most-significant-bit:
 150 //
 151 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 152 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 153 eval_msb_imp(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 154 {
 155    //
 156    // Find the index of the most significant bit that is non-zero:
 157    //
 158    return (a.size() - 1) * cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits + boost::multiprecision::detail::find_msb(a.limbs()[a.size() - 1]);
 159 }
 160
 161 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 162 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 163    eval_msb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 164 {
 165    using default_ops::eval_get_sign;
 166    if(eval_get_sign(a) == 0)
 167    {
 168       BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
 169    }
 170    if(a.sign())
 171    {
 172       BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
 173    }
 174    return eval_msb_imp(a);
 175 }
 176
 177 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 178 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, bool>::type
 179    eval_bit_test(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) BOOST_NOEXCEPT
 180 {
 181    unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 182    unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 183    limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u);
 184    if(offset >= val.size())
 185       return false;
 186    return val.limbs()[offset] & mask ? true : false;
 187 }
 188
 189 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 190 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 191    eval_bit_set(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index)
 192 {
 193    unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 194    unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 195    limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u);
 196    if(offset >= val.size())
 197    {
 198       unsigned os = val.size();
 199       val.resize(offset + 1, offset + 1);
 200       if(offset >= val.size())
 201          return;  // fixed precision overflow
 202       for(unsigned i = os; i <= offset; ++i)
 203          val.limbs()[i] = 0;
 204    }
 205    val.limbs()[offset] |= mask;
 206 }
 207
 208 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 209 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 210    eval_bit_unset(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) BOOST_NOEXCEPT
 211 {
 212    unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 213    unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 214    limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u);
 215    if(offset >= val.size())
 216       return;
 217    val.limbs()[offset] &= ~mask;
 218    val.normalize();
 219 }
 220
 221 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 222 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 223    eval_bit_flip(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index)
 224 {
 225    unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 226    unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
 227    limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u);
 228    if(offset >= val.size())
 229    {
 230       unsigned os = val.size();
 231       val.resize(offset + 1, offset + 1);
 232       if(offset >= val.size())
 233          return;  // fixed precision overflow
 234       for(unsigned i = os; i <= offset; ++i)
 235          val.limbs()[i] = 0;
 236    }
 237    val.limbs()[offset] ^= mask;
 238    val.normalize();
 239 }
 240
 241 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 242 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 243    eval_qr(
 244       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x,
 245       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& y,
 246       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q,
 247       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 248 {
 249    divide_unsigned_helper(&q, x, y, r);
 250    q.sign(x.sign() != y.sign());
 251    r.sign(x.sign());
 252 }
 253
 254 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 255 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 256    eval_qr(
 257       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x,
 258       limb_type y,
 259       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q,
 260       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 261 {
 262    divide_unsigned_helper(&q, x, y, r);
 263    q.sign(x.sign());
 264    r.sign(x.sign());
 265 }
 266
 267 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class U>
 268 inline typename enable_if_c<is_integral<U>::value>::type eval_qr(
 269       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x,
 270       U y,
 271       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q,
 272       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 273 {
 274    using default_ops::eval_qr;
 275    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
 276    t = y;
 277    eval_qr(x, t, q, r);
 278 }
 279
 280 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer>
 281 inline typename enable_if_c<is_unsigned<Integer>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, Integer>::type
 282    eval_integer_modulus(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, Integer val)
 283 {
 284    if((sizeof(Integer) <= sizeof(limb_type)) || (val <= (std::numeric_limits<limb_type>::max)()))
 285    {
 286       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> d;
 287       divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>*>(0), x, static_cast<limb_type>(val), d);
 288       return d.limbs()[0];
 289    }
 290    else
 291    {
 292       return default_ops::eval_integer_modulus(x, val);
 293    }
 294 }
 295
 296 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer>
 297 BOOST_MP_FORCEINLINE typename enable_if_c<is_signed<Integer>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, Integer>::type
 298    eval_integer_modulus(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, Integer val)
 299 {
 300    return eval_integer_modulus(x, boost::multiprecision::detail::unsigned_abs(val));
 301 }
 302
 303 inline limb_type integer_gcd_reduce(limb_type u, limb_type v)
 304 {
 305    do
 306    {
 307       if(u > v)
 308          std::swap(u, v);
 309       if(u == v)
 310          break;
 311       v -= u;
 312       v >>= boost::multiprecision::detail::find_lsb(v);
 313    } while(true);
 314    return u;
 315 }
 316
 317 inline double_limb_type integer_gcd_reduce(double_limb_type u, double_limb_type v)
 318 {
 319    do
 320    {
 321       if(u > v)
 322          std::swap(u, v);
 323       if(u == v)
 324          break;
 325       if(v <= ~static_cast<limb_type>(0))
 326       {
 327          u = integer_gcd_reduce(static_cast<limb_type>(v), static_cast<limb_type>(u));
 328          break;
 329       }
 330       v -= u;
 331 #ifdef __MSVC_RUNTIME_CHECKS
 332       while((v & 1u) == 0)
 333 #else
 334       while((static_cast<unsigned>(v) & 1u) == 0)
 335 #endif
 336          v >>= 1;
 337    } while(true);
 338    return u;
 339 }
 340
 341 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 342 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 343    eval_gcd(
 344       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 345       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 346       limb_type v)
 347 {
 348    using default_ops::eval_lsb;
 349    using default_ops::eval_is_zero;
 350    using default_ops::eval_get_sign;
 351
 352    int shift;
 353
 354    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> u(a);
 355
 356    int s = eval_get_sign(u);
 357
 358    /* GCD(0,x) := x */
 359    if(s < 0)
 360    {
 361       u.negate();
 362    }
 363    else if(s == 0)
 364    {
 365       result = v;
 366       return;
 367    }
 368    if(v == 0)
 369    {
 370       result = u;
 371       return;
 372    }
 373
 374    /* Let shift := lg K, where K is the greatest power of 2
 375    dividing both u and v. */
 376
 377    unsigned us = eval_lsb(u);
 378    unsigned vs = boost::multiprecision::detail::find_lsb(v);
 379    shift = (std::min)(us, vs);
 380    eval_right_shift(u, us);
 381    if(vs)
 382       v >>= vs;
 383
 384    do
 385    {
 386       /* Now u and v are both odd, so diff(u, v) is even.
 387       Let u = min(u, v), v = diff(u, v)/2. */
 388       if(u.size() <= 2)
 389       {
 390          if(u.size() == 1)
 391             v = integer_gcd_reduce(*u.limbs(), v);
 392          else
 393          {
 394             double_limb_type i;
 395             i = u.limbs()[0] | (static_cast<double_limb_type>(u.limbs()[1]) << sizeof(limb_type) * CHAR_BIT);
 396             v = static_cast<limb_type>(integer_gcd_reduce(i, static_cast<double_limb_type>(v)));
 397          }
 398          break;
 399       }
 400       eval_subtract(u, v);
 401       us = eval_lsb(u);
 402       eval_right_shift(u, us);
 403    }
 404    while(true);
 405
 406    result = v;
 407    eval_left_shift(result, shift);
 408 }
 409 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer>
 410 inline typename enable_if_c<is_unsigned<Integer>::value && (sizeof(Integer) <= sizeof(limb_type)) && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 411    eval_gcd(
 412       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 413       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 414       const Integer& v)
 415 {
 416    eval_gcd(result, a, static_cast<limb_type>(v));
 417 }
 418 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer>
 419 inline typename enable_if_c<is_signed<Integer>::value && (sizeof(Integer) <= sizeof(limb_type)) && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 420    eval_gcd(
 421       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 422       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 423       const Integer& v)
 424 {
 425    eval_gcd(result, a, static_cast<limb_type>(v < 0 ? -v : v));
 426 }
 427
 428 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 429 inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 430    eval_gcd(
 431       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
 432       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
 433       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b)
 434 {
 435    using default_ops::eval_lsb;
 436    using default_ops::eval_is_zero;
 437    using default_ops::eval_get_sign;
 438
 439    if(a.size() == 1)
 440    {
 441       eval_gcd(result, b, *a.limbs());
 442       return;
 443    }
 444    if(b.size() == 1)
 445    {
 446       eval_gcd(result, a, *b.limbs());
 447       return;
 448    }
 449
 450    int shift;
 451
 452    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> u(a), v(b);
 453
 454    int s = eval_get_sign(u);
 455
 456    /* GCD(0,x) := x */
 457    if(s < 0)
 458    {
 459       u.negate();
 460    }
 461    else if(s == 0)
 462    {
 463       result = v;
 464       return;
 465    }
 466    s = eval_get_sign(v);
 467    if(s < 0)
 468    {
 469       v.negate();
 470    }
 471    else if(s == 0)
 472    {
 473       result = u;
 474       return;
 475    }
 476
 477    /* Let shift := lg K, where K is the greatest power of 2
 478    dividing both u and v. */
 479
 480    unsigned us = eval_lsb(u);
 481    unsigned vs = eval_lsb(v);
 482    shift = (std::min)(us, vs);
 483    eval_right_shift(u, us);
 484    eval_right_shift(v, vs);
 485
 486    do
 487    {
 488       /* Now u and v are both odd, so diff(u, v) is even.
 489       Let u = min(u, v), v = diff(u, v)/2. */
 490       s = u.compare(v);
 491       if(s > 0)
 492          u.swap(v);
 493       if(s == 0)
 494          break;
 495       if(v.size() <= 2)
 496       {
 497          if(v.size() == 1)
 498             u = integer_gcd_reduce(*v.limbs(), *u.limbs());
 499          else
 500          {
 501             double_limb_type i, j;
 502             i = v.limbs()[0] | (static_cast<double_limb_type>(v.limbs()[1]) << sizeof(limb_type) * CHAR_BIT);
 503             j = (u.size() == 1) ? *u.limbs() : u.limbs()[0] | (static_cast<double_limb_type>(u.limbs()[1]) << sizeof(limb_type) * CHAR_BIT);
 504             u = integer_gcd_reduce(i, j);
 505          }
 506          break;
 507       }
 508       eval_subtract(v, u);
 509       vs = eval_lsb(v);
 510       eval_right_shift(v, vs);
 511    }
 512    while(true);
 513
 514    result = u;
 515    eval_left_shift(result, shift);
 516 }
 517 //
 518 // Now again for trivial backends:
 519 //
 520 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 521 BOOST_MP_FORCEINLINE typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
 522    eval_gcd(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_NOEXCEPT
 523 {
 524    *result.limbs() = boost::integer::gcd(*a.limbs(), *b.limbs());
 525 }
 526 // This one is only enabled for unchecked cpp_int's, for checked int's we need the checking in the default version:
 527 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 528 BOOST_MP_FORCEINLINE typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && (Checked1 == unchecked)>::type
 529    eval_lcm(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
 530 {
 531    *result.limbs() = boost::integer::lcm(*a.limbs(), *b.limbs());
 532    result.normalize(); // result may overflow the specified number of bits
 533 }
 534
 535 inline void conversion_overflow(const mpl::int_<checked>&)
 536 {
 537    BOOST_THROW_EXCEPTION(std::overflow_error("Overflow in conversion to narrower type"));
 538 }
 539 inline void conversion_overflow(const mpl::int_<unchecked>&){}
 540
 541 template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 542 inline typename enable_if_c<
 543             is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
 544             && is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
 545             && boost::is_convertible<typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type, R>::value
 546          >::type
 547    eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val)
 548 {
 549    typedef typename common_type<R, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type>::type common_type;
 550    if(std::numeric_limits<R>::is_specialized && (static_cast<common_type>(*val.limbs()) > static_cast<common_type>((std::numeric_limits<R>::max)())))
 551    {
 552       if(val.isneg())
 553       {
 554          if(static_cast<common_type>(*val.limbs()) > -static_cast<common_type>((std::numeric_limits<R>::min)()))
 555             conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 556          *result = (std::numeric_limits<R>::min)();
 557       }
 558       else
 559       {
 560          conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 561          *result = (std::numeric_limits<R>::max)();
 562       }
 563    }
 564    else
 565    {
 566       *result = static_cast<R>(*val.limbs());
 567       if(val.isneg())
 568       {
 569          check_is_negative(mpl::bool_<is_signed_number<R>::value || (number_category<R>::value == number_kind_floating_point)>());
 570          *result = negate_integer(*result, mpl::bool_<is_signed_number<R>::value || (number_category<R>::value == number_kind_floating_point)>());
 571       }
 572    }
 573 }
 574
 575 template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 576 inline typename enable_if_c<
 577             is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
 578             && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
 579             && boost::is_convertible<typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type, R>::value
 580          >::type
 581    eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val)
 582 {
 583    typedef typename common_type<R, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type>::type common_type;
 584    if(std::numeric_limits<R>::is_specialized && (static_cast<common_type>(*val.limbs()) > static_cast<common_type>((std::numeric_limits<R>::max)())))
 585    {
 586       conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
 587       *result = (std::numeric_limits<R>::max)();
 588    }
 589    else
 590       *result = static_cast<R>(*val.limbs());
 591 }
 592
 593 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 594 inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 595    eval_lsb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 596 {
 597    using default_ops::eval_get_sign;
 598    if(eval_get_sign(a) == 0)
 599    {
 600       BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
 601    }
 602    if(a.sign())
 603    {
 604       BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
 605    }
 606    //
 607    // Find the index of the least significant bit within that limb:
 608    //
 609    return boost::multiprecision::detail::find_lsb(*a.limbs());
 610 }
 611
 612 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 613 inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 614 eval_msb_imp(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 615 {
 616    //
 617    // Find the index of the least significant bit within that limb:
 618    //
 619    return boost::multiprecision::detail::find_msb(*a.limbs());
 620 }
 621
 622 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 623 inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type
 624    eval_msb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a)
 625 {
 626    using default_ops::eval_get_sign;
 627    if(eval_get_sign(a) == 0)
 628    {
 629       BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
 630    }
 631    if(a.sign())
 632    {
 633       BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
 634    }
 635    return eval_msb_imp(a);
 636 }
 637
 638 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
 639 inline std::size_t hash_value(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT
 640 {
 641    std::size_t result = 0;
 642    for(unsigned i = 0; i < val.size(); ++i)
 643    {
 644       boost::hash_combine(result, val.limbs()[i]);
 645    }
 646    boost::hash_combine(result, val.sign());
 647    return result;
 648 }
 649
 650 #ifdef BOOST_MSVC
 651 #pragma warning(pop)
 652 #endif
 653
 654 }}} // namespaces
 655
 656 #endif