boost/multiprecision/tommath.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 //  Copyright 2011 John Maddock.
0003 //  Copyright 2021 Matt Borland. Distributed under the Boost
0004 //  Software License, Version 1.0. (See accompanying file
0005 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_MP_TOMMATH_HPP
0008 #define BOOST_MP_TOMMATH_HPP
0009
0010 #include <cctype>
0011 #include <climits>
0012 #include <cmath>
0013 #include <cstdint>
0014 #include <cstddef>
0015 #include <cstdlib>
0016 #include <limits>
0017 #include <memory>
0018 #include <string>
0019
0020 #include <tommath.h>
0021
0022 #include <boost/multiprecision/detail/standalone_config.hpp>
0023 #include <boost/multiprecision/detail/fpclassify.hpp>
0024 #include <boost/multiprecision/number.hpp>
0025 #include <boost/multiprecision/rational_adaptor.hpp>
0026 #include <boost/multiprecision/detail/integer_ops.hpp>
0027 #include <boost/multiprecision/detail/hash.hpp>
0028 #include <boost/multiprecision/detail/no_exceptions_support.hpp>
0029 #include <boost/multiprecision/detail/assert.hpp>
0030
0031 namespace boost {
0032 namespace multiprecision {
0033 namespace backends {
0034
0035 namespace detail {
0036
0037 template <class ErrType>
0038 inline void check_tommath_result(ErrType v)
0039 {
0040    if (v != MP_OKAY)
0041    {
0042       BOOST_MP_THROW_EXCEPTION(std::runtime_error(mp_error_to_string(v)));
0043    }
0044 }
0045
0046 } // namespace detail
0047
0048 void eval_multiply(tommath_int& t, const tommath_int& o);
0049 void eval_add(tommath_int& t, const tommath_int& o);
0050
0051 struct tommath_int
0052 {
0053    using signed_types = std::tuple<std::int32_t, long long>  ;
0054    using unsigned_types = std::tuple<std::uint32_t, unsigned long long>;
0055    using float_types = std::tuple<long double>                            ;
0056
0057    tommath_int()
0058    {
0059       detail::check_tommath_result(mp_init(&m_data));
0060    }
0061    tommath_int(const tommath_int& o)
0062    {
0063       detail::check_tommath_result(mp_init_copy(&m_data, const_cast< ::mp_int*>(&o.m_data)));
0064    }
0065    // rvalues:
0066    tommath_int(tommath_int&& o) noexcept
0067    {
0068       m_data      = o.m_data;
0069       o.m_data.dp = 0;
0070    }
0071    tommath_int& operator=(tommath_int&& o)
0072    {
0073       mp_exch(&m_data, &o.m_data);
0074       return *this;
0075    }
0076    tommath_int& operator=(const tommath_int& o)
0077    {
0078       if (m_data.dp == nullptr)
0079          detail::check_tommath_result(mp_init(&m_data));
0080       if (o.m_data.dp)
0081          detail::check_tommath_result(mp_copy(const_cast< ::mp_int*>(&o.m_data), &m_data));
0082       return *this;
0083    }
0084 #ifndef mp_get_u64
0085    // Pick off 32 bit chunks for mp_set_int:
0086    tommath_int& operator=(unsigned long long i)
0087    {
0088       if (m_data.dp == nullptr)
0089          detail::check_tommath_result(mp_init(&m_data));
0090       unsigned long long mask = ((1uLL << 32) - 1);
0091       unsigned shift = 0;
0092       ::mp_int t;
0093       detail::check_tommath_result(mp_init(&t));
0094       mp_zero(&m_data);
0095       while (i)
0096       {
0097          detail::check_tommath_result(mp_set_int(&t, static_cast<unsigned>(i & mask)));
0098          if (shift)
0099             detail::check_tommath_result(mp_mul_2d(&t, shift, &t));
0100          detail::check_tommath_result((mp_add(&m_data, &t, &m_data)));
0101          shift += 32;
0102          i >>= 32;
0103       }
0104       mp_clear(&t);
0105       return *this;
0106    }
0107 #elif !defined(ULLONG_MAX) || (ULLONG_MAX != 18446744073709551615uLL)
0108    // Pick off 64 bit chunks for mp_set_u64:
0109    tommath_int& operator=(unsigned long long i)
0110    {
0111       if (m_data.dp == nullptr)
0112          detail::check_tommath_result(mp_init(&m_data));
0113       if(sizeof(unsigned long long) * CHAR_BIT == 64)
0114       {
0115          mp_set_u64(&m_data, i);
0116          return *this;
0117       }
0118       unsigned long long mask = ((1uLL << 64) - 1);
0119       unsigned shift = 0;
0120       ::mp_int t;
0121       detail::check_tommath_result(mp_init(&t));
0122       mp_zero(&m_data);
0123       while (i)
0124       {
0125          detail::check_tommath_result(mp_set_u64(&t, static_cast<std::uint64_t>(i & mask)));
0126          if (shift)
0127             detail::check_tommath_result(mp_mul_2d(&t, shift, &t));
0128          detail::check_tommath_result((mp_add(&m_data, &t, &m_data)));
0129          shift += 64;
0130          i >>= 64;
0131       }
0132       mp_clear(&t);
0133       return *this;
0134    }
0135 #else
0136    tommath_int& operator=(unsigned long long i)
0137    {
0138       if (m_data.dp == nullptr)
0139          detail::check_tommath_result(mp_init(&m_data));
0140       mp_set_u64(&m_data, i);
0141       return *this;
0142    }
0143 #endif
0144    tommath_int& operator=(long long i)
0145    {
0146       if (m_data.dp == nullptr)
0147          detail::check_tommath_result(mp_init(&m_data));
0148       bool neg = i < 0;
0149       *this    = boost::multiprecision::detail::unsigned_abs(i);
0150       if (neg)
0151          detail::check_tommath_result(mp_neg(&m_data, &m_data));
0152       return *this;
0153    }
0154 #ifdef BOOST_HAS_INT128
0155    // Pick off 64 bit chunks for mp_set_u64:
0156    tommath_int& operator=(uint128_type i)
0157    {
0158       if (m_data.dp == nullptr)
0159          detail::check_tommath_result(mp_init(&m_data));
0160
0161       int128_type  mask  = ((static_cast<uint128_type>(1u) << 64) - 1);
0162       unsigned           shift = 0;
0163       ::mp_int           t;
0164       detail::check_tommath_result(mp_init(&t));
0165       mp_zero(&m_data);
0166       while (i)
0167       {
0168 #ifndef mp_get_u32
0169          detail::check_tommath_result(mp_set_long_long(&t, static_cast<std::uint64_t>(i & mask)));
0170 #else
0171          mp_set_u64(&t, static_cast<std::uint64_t>(i & mask));
0172 #endif
0173          if (shift)
0174             detail::check_tommath_result(mp_mul_2d(&t, shift, &t));
0175          detail::check_tommath_result((mp_add(&m_data, &t, &m_data)));
0176          shift += 64;
0177          i >>= 64;
0178       }
0179       mp_clear(&t);
0180       return *this;
0181    }
0182    tommath_int& operator=(int128_type i)
0183    {
0184       if (m_data.dp == nullptr)
0185          detail::check_tommath_result(mp_init(&m_data));
0186       bool neg = i < 0;
0187       *this    = boost::multiprecision::detail::unsigned_abs(i);
0188       if (neg)
0189          detail::check_tommath_result(mp_neg(&m_data, &m_data));
0190       return *this;
0191    }
0192 #endif
0193    //
0194    // Note that although mp_set_int takes an unsigned long as an argument
0195    // it only sets the first 32-bits to the result, and ignores the rest.
0196    // So use uint32_t as the largest type to pass to this function.
0197    //
0198    tommath_int& operator=(std::uint32_t i)
0199    {
0200       if (m_data.dp == nullptr)
0201          detail::check_tommath_result(mp_init(&m_data));
0202 #ifndef mp_get_u32
0203       detail::check_tommath_result((mp_set_int(&m_data, i)));
0204 #else
0205       mp_set_u32(&m_data, i);
0206 #endif
0207       return *this;
0208    }
0209    tommath_int& operator=(std::int32_t i)
0210    {
0211       if (m_data.dp == nullptr)
0212          detail::check_tommath_result(mp_init(&m_data));
0213       bool neg = i < 0;
0214       *this    = boost::multiprecision::detail::unsigned_abs(i);
0215       if (neg)
0216          detail::check_tommath_result(mp_neg(&m_data, &m_data));
0217       return *this;
0218    }
0219    template <class F>
0220    tommath_int& assign_float(F a)
0221    {
0222       BOOST_MP_FLOAT128_USING using std::floor; using std::frexp; using std::ldexp;
0223
0224       if (m_data.dp == nullptr)
0225          detail::check_tommath_result(mp_init(&m_data));
0226
0227       if (a == 0)
0228       {
0229 #ifndef mp_get_u32
0230          detail::check_tommath_result(mp_set_int(&m_data, 0));
0231 #else
0232          mp_set_i32(&m_data, 0);
0233 #endif
0234          return *this;
0235       }
0236
0237       if (a == 1)
0238       {
0239 #ifndef mp_get_u32
0240          detail::check_tommath_result(mp_set_int(&m_data, 1));
0241 #else
0242          mp_set_i32(&m_data, 1);
0243 #endif
0244          return *this;
0245       }
0246
0247       BOOST_MP_ASSERT(!BOOST_MP_ISINF(a));
0248       BOOST_MP_ASSERT(!BOOST_MP_ISNAN(a));
0249
0250       int         e;
0251       F f, term;
0252 #ifndef mp_get_u32
0253       detail::check_tommath_result(mp_set_int(&m_data, 0u));
0254 #else
0255       mp_set_i32(&m_data, 0);
0256 #endif
0257       ::mp_int t;
0258       detail::check_tommath_result(mp_init(&t));
0259
0260       f = frexp(a, &e);
0261
0262 #ifdef MP_DIGIT_BIT
0263       constexpr const int shift = std::numeric_limits<int>::digits - 1;
0264       using part_type = int     ;
0265 #else
0266       constexpr const int  shift = std::numeric_limits<std::int64_t>::digits - 1;
0267       using part_type = std::int64_t;
0268 #endif
0269
0270       while (f)
0271       {
0272          // extract int sized bits from f:
0273          f    = ldexp(f, shift);
0274          term = floor(f);
0275          e -= shift;
0276          detail::check_tommath_result(mp_mul_2d(&m_data, shift, &m_data));
0277          if (term > 0)
0278          {
0279 #ifndef mp_get_u64
0280             detail::check_tommath_result(mp_set_int(&t, static_cast<part_type>(term)));
0281 #else
0282             mp_set_i64(&t, static_cast<part_type>(term));
0283 #endif
0284             detail::check_tommath_result(mp_add(&m_data, &t, &m_data));
0285          }
0286          else
0287          {
0288 #ifndef mp_get_u64
0289             detail::check_tommath_result(mp_set_int(&t, static_cast<part_type>(-term)));
0290 #else
0291             mp_set_i64(&t, static_cast<part_type>(-term));
0292 #endif
0293             detail::check_tommath_result(mp_sub(&m_data, &t, &m_data));
0294          }
0295          f -= term;
0296       }
0297       if (e > 0)
0298          detail::check_tommath_result(mp_mul_2d(&m_data, e, &m_data));
0299       else if (e < 0)
0300       {
0301          tommath_int t2;
0302          detail::check_tommath_result(mp_div_2d(&m_data, -e, &m_data, &t2.data()));
0303       }
0304       mp_clear(&t);
0305       return *this;
0306    }
0307    tommath_int& operator=(long double a)
0308    {
0309       return assign_float(a);
0310    }
0311 #ifdef BOOST_HAS_FLOAT128
0312    tommath_int& operator= (float128_type a)
0313    {
0314       return assign_float(a);
0315    }
0316 #endif
0317    tommath_int& operator=(const char* s)
0318    {
0319       //
0320       // We don't use libtommath's own routine because it doesn't error check the input :-(
0321       //
0322       if (m_data.dp == nullptr)
0323          detail::check_tommath_result(mp_init(&m_data));
0324       std::size_t n  = s ? std::strlen(s) : 0;
0325       *this          = static_cast<std::uint32_t>(0u);
0326       unsigned radix = 10;
0327       bool     isneg = false;
0328       if (n && (*s == '-'))
0329       {
0330          --n;
0331          ++s;
0332          isneg = true;
0333       }
0334       if (n && (*s == '0'))
0335       {
0336          if ((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
0337          {
0338             radix = 16;
0339             s += 2;
0340             n -= 2;
0341          }
0342          else
0343          {
0344             radix = 8;
0345             n -= 1;
0346          }
0347       }
0348       if (n)
0349       {
0350          if (radix == 8 || radix == 16)
0351          {
0352             unsigned shift = radix == 8 ? 3 : 4;
0353 #ifndef MP_DIGIT_BIT
0354             unsigned block_count = DIGIT_BIT / shift;
0355 #else
0356             unsigned block_count = MP_DIGIT_BIT / shift;
0357 #endif
0358             unsigned               block_shift = shift * block_count;
0359             unsigned long long val, block;
0360             while (*s)
0361             {
0362                block = 0;
0363                for (unsigned i = 0; (i < block_count); ++i)
0364                {
0365                   if (*s >= '0' && *s <= '9')
0366                      val = *s - '0';
0367                   else if (*s >= 'a' && *s <= 'f')
0368                      val = 10 + *s - 'a';
0369                   else if (*s >= 'A' && *s <= 'F')
0370                      val = 10 + *s - 'A';
0371                   else
0372                      val = 400;
0373                   if (val > radix)
0374                   {
0375                      BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
0376                   }
0377                   block <<= shift;
0378                   block |= val;
0379                   if (!*++s)
0380                   {
0381                      // final shift is different:
0382                      block_shift = (i + 1) * shift;
0383                      break;
0384                   }
0385                }
0386                detail::check_tommath_result(mp_mul_2d(&data(), block_shift, &data()));
0387                if (data().used)
0388                   data().dp[0] |= block;
0389                else
0390                   *this = block;
0391             }
0392          }
0393          else
0394          {
0395             // Base 10, we extract blocks of size 10^9 at a time, that way
0396             // the number of multiplications is kept to a minimum:
0397             std::uint32_t block_mult = 1000000000;
0398             while (*s)
0399             {
0400                std::uint32_t block = 0;
0401                for (unsigned i = 0; i < 9; ++i)
0402                {
0403                   std::uint32_t val;
0404                   if (*s >= '0' && *s <= '9')
0405                      val = *s - '0';
0406                   else
0407                      BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input."));
0408                   block *= 10;
0409                   block += val;
0410                   if (!*++s)
0411                   {
0412                      constexpr const std::uint32_t block_multiplier[9] = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
0413                      block_mult                                       = block_multiplier[i];
0414                      break;
0415                   }
0416                }
0417                tommath_int t;
0418                t = block_mult;
0419                eval_multiply(*this, t);
0420                t = block;
0421                eval_add(*this, t);
0422             }
0423          }
0424       }
0425       if (isneg)
0426          this->negate();
0427       return *this;
0428    }
0429    std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f) const
0430    {
0431       BOOST_MP_ASSERT(m_data.dp);
0432       int base = 10;
0433       if ((f & std::ios_base::oct) == std::ios_base::oct)
0434          base = 8;
0435       else if ((f & std::ios_base::hex) == std::ios_base::hex)
0436          base = 16;
0437       //
0438       // sanity check, bases 8 and 16 are only available for positive numbers:
0439       //
0440       if ((base != 10) && m_data.sign)
0441          BOOST_MP_THROW_EXCEPTION(std::runtime_error("Formatted output in bases 8 or 16 is only available for positive numbers"));
0442
0443       // Check against known removed macro that was removed around the same time as type was changed
0444       #ifdef mp_tobinary
0445       int s;
0446       #else
0447       size_t s;
0448       #endif
0449       detail::check_tommath_result(mp_radix_size(const_cast< ::mp_int*>(&m_data), base, &s));
0450
0451       std::unique_ptr<char[]> a(new char[s + 1]);
0452 #ifndef mp_to_binary
0453       detail::check_tommath_result(mp_toradix_n(const_cast< ::mp_int*>(&m_data), a.get(), base, s + 1));
0454 #else
0455       std::size_t written;
0456       detail::check_tommath_result(mp_to_radix(&m_data, a.get(), s + 1, &written, base));
0457 #endif
0458       std::string result = a.get();
0459       if (f & std::ios_base::uppercase)
0460          for (size_t i = 0; i < result.length(); ++i)
0461             result[i] = std::toupper(result[i]);
0462       if ((base != 10) && (f & std::ios_base::showbase))
0463       {
0464          int         pos = result[0] == '-' ? 1 : 0;
0465          const char* pp  = base == 8 ? "0" : (f & std::ios_base::uppercase) ? "0X" : "0x";
0466          result.insert(static_cast<std::string::size_type>(pos), pp);
0467       }
0468       if ((f & std::ios_base::showpos) && (result[0] != '-'))
0469          result.insert(static_cast<std::string::size_type>(0), 1, '+');
0470       if (((f & std::ios_base::uppercase) == 0) && (base == 16))
0471       {
0472          for (std::size_t i = 0; i < result.size(); ++i)
0473             result[i] = std::tolower(result[i]);
0474       }
0475       return result;
0476    }
0477    ~tommath_int()
0478    {
0479       if (m_data.dp)
0480          mp_clear(&m_data);
0481    }
0482    void negate()
0483    {
0484       BOOST_MP_ASSERT(m_data.dp);
0485       detail::check_tommath_result(mp_neg(&m_data, &m_data));
0486    }
0487    int compare(const tommath_int& o) const
0488    {
0489       BOOST_MP_ASSERT(m_data.dp && o.m_data.dp);
0490       return mp_cmp(const_cast< ::mp_int*>(&m_data), const_cast< ::mp_int*>(&o.m_data));
0491    }
0492    template <class V>
0493    int compare(V v) const
0494    {
0495       tommath_int d;
0496       tommath_int t(*this);
0497       detail::check_tommath_result(mp_shrink(&t.data()));
0498       d = v;
0499       return t.compare(d);
0500    }
0501    ::mp_int& data()
0502    {
0503       BOOST_MP_ASSERT(m_data.dp);
0504       return m_data;
0505    }
0506    const ::mp_int& data() const
0507    {
0508       BOOST_MP_ASSERT(m_data.dp);
0509       return m_data;
0510    }
0511    void swap(tommath_int& o) noexcept
0512    {
0513       mp_exch(&m_data, &o.data());
0514    }
0515
0516  protected:
0517    ::mp_int m_data;
0518 };
0519
0520 #ifndef mp_isneg
0521 #define BOOST_MP_TOMMATH_BIT_OP_CHECK(x) \
0522    if (SIGN(&x.data()))                  \
0523    BOOST_MP_THROW_EXCEPTION(std::runtime_error("Bitwise operations on libtommath negative valued integers are disabled as they produce unpredictable results"))
0524 #else
0525 #define BOOST_MP_TOMMATH_BIT_OP_CHECK(x) \
0526    if (mp_isneg(&x.data()))              \
0527    BOOST_MP_THROW_EXCEPTION(std::runtime_error("Bitwise operations on libtommath negative valued integers are disabled as they produce unpredictable results"))
0528 #endif
0529
0530 int eval_get_sign(const tommath_int& val);
0531
0532 inline void eval_add(tommath_int& t, const tommath_int& o)
0533 {
0534    detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0535 }
0536 inline void eval_subtract(tommath_int& t, const tommath_int& o)
0537 {
0538    detail::check_tommath_result(mp_sub(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0539 }
0540 inline void eval_multiply(tommath_int& t, const tommath_int& o)
0541 {
0542    detail::check_tommath_result(mp_mul(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0543 }
0544 inline void eval_divide(tommath_int& t, const tommath_int& o)
0545 {
0546    using default_ops::eval_is_zero;
0547    tommath_int temp;
0548    if (eval_is_zero(o))
0549       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Integer division by zero"));
0550    detail::check_tommath_result(mp_div(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data(), &temp.data()));
0551 }
0552 inline void eval_modulus(tommath_int& t, const tommath_int& o)
0553 {
0554    using default_ops::eval_is_zero;
0555    if (eval_is_zero(o))
0556       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Integer division by zero"));
0557    bool neg  = eval_get_sign(t) < 0;
0558    bool neg2 = eval_get_sign(o) < 0;
0559    detail::check_tommath_result(mp_mod(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0560    if ((neg != neg2) && (eval_get_sign(t) != 0))
0561    {
0562       t.negate();
0563       detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0564       t.negate();
0565    }
0566    else if (neg && (t.compare(o) == 0))
0567    {
0568       mp_zero(&t.data());
0569    }
0570 }
0571 template <class UI>
0572 inline void eval_left_shift(tommath_int& t, UI i)
0573 {
0574    detail::check_tommath_result(mp_mul_2d(&t.data(), static_cast<unsigned>(i), &t.data()));
0575 }
0576 template <class UI>
0577 inline void eval_right_shift(tommath_int& t, UI i)
0578 {
0579    using default_ops::eval_decrement;
0580    using default_ops::eval_increment;
0581    bool        neg = eval_get_sign(t) < 0;
0582    tommath_int d;
0583    if (neg)
0584       eval_increment(t);
0585    detail::check_tommath_result(mp_div_2d(&t.data(), static_cast<unsigned>(i), &t.data(), &d.data()));
0586    if (neg)
0587       eval_decrement(t);
0588 }
0589 template <class UI>
0590 inline void eval_left_shift(tommath_int& t, const tommath_int& v, UI i)
0591 {
0592    detail::check_tommath_result(mp_mul_2d(const_cast< ::mp_int*>(&v.data()), static_cast<unsigned>(i), &t.data()));
0593 }
0594 /*
0595 template <class UI>
0596 inline void eval_right_shift(tommath_int& t, const tommath_int& v, UI i)
0597 {
0598    tommath_int d;
0599    detail::check_tommath_result(mp_div_2d(const_cast< ::mp_int*>(&v.data()), static_cast<unsigned long>(i), &t.data(), &d.data()));
0600 }
0601 */
0602 inline void eval_bitwise_and(tommath_int& result, const tommath_int& v)
0603 {
0604    BOOST_MP_TOMMATH_BIT_OP_CHECK(result);
0605    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0606    detail::check_tommath_result(mp_and(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data()));
0607 }
0608
0609 inline void eval_bitwise_or(tommath_int& result, const tommath_int& v)
0610 {
0611    BOOST_MP_TOMMATH_BIT_OP_CHECK(result);
0612    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0613    detail::check_tommath_result(mp_or(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data()));
0614 }
0615
0616 inline void eval_bitwise_xor(tommath_int& result, const tommath_int& v)
0617 {
0618    BOOST_MP_TOMMATH_BIT_OP_CHECK(result);
0619    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0620    detail::check_tommath_result(mp_xor(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data()));
0621 }
0622
0623 inline void eval_add(tommath_int& t, const tommath_int& p, const tommath_int& o)
0624 {
0625    detail::check_tommath_result(mp_add(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data()));
0626 }
0627 inline void eval_subtract(tommath_int& t, const tommath_int& p, const tommath_int& o)
0628 {
0629    detail::check_tommath_result(mp_sub(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data()));
0630 }
0631 inline void eval_multiply(tommath_int& t, const tommath_int& p, const tommath_int& o)
0632 {
0633    detail::check_tommath_result(mp_mul(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data()));
0634 }
0635 inline void eval_divide(tommath_int& t, const tommath_int& p, const tommath_int& o)
0636 {
0637    using default_ops::eval_is_zero;
0638    tommath_int d;
0639    if (eval_is_zero(o))
0640       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Integer division by zero"));
0641    detail::check_tommath_result(mp_div(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data(), &d.data()));
0642 }
0643 inline void eval_modulus(tommath_int& t, const tommath_int& p, const tommath_int& o)
0644 {
0645    using default_ops::eval_is_zero;
0646    if (eval_is_zero(o))
0647       BOOST_MP_THROW_EXCEPTION(std::overflow_error("Integer division by zero"));
0648    bool neg  = eval_get_sign(p) < 0;
0649    bool neg2 = eval_get_sign(o) < 0;
0650    detail::check_tommath_result(mp_mod(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data()));
0651    if ((neg != neg2) && (eval_get_sign(t) != 0))
0652    {
0653       t.negate();
0654       detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data()));
0655       t.negate();
0656    }
0657    else if (neg && (t.compare(o) == 0))
0658    {
0659       mp_zero(&t.data());
0660    }
0661 }
0662
0663 inline void eval_bitwise_and(tommath_int& result, const tommath_int& u, const tommath_int& v)
0664 {
0665    BOOST_MP_TOMMATH_BIT_OP_CHECK(u);
0666    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0667    detail::check_tommath_result(mp_and(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data()));
0668 }
0669
0670 inline void eval_bitwise_or(tommath_int& result, const tommath_int& u, const tommath_int& v)
0671 {
0672    BOOST_MP_TOMMATH_BIT_OP_CHECK(u);
0673    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0674    detail::check_tommath_result(mp_or(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data()));
0675 }
0676
0677 inline void eval_bitwise_xor(tommath_int& result, const tommath_int& u, const tommath_int& v)
0678 {
0679    BOOST_MP_TOMMATH_BIT_OP_CHECK(u);
0680    BOOST_MP_TOMMATH_BIT_OP_CHECK(v);
0681    detail::check_tommath_result(mp_xor(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data()));
0682 }
0683 /*
0684 inline void eval_complement(tommath_int& result, const tommath_int& u)
0685 {
0686    //
0687    // Although this code works, it doesn't really do what the user might expect....
0688    // and it's hard to see how it ever could.  Disabled for now:
0689    //
0690    result = u;
0691    for(int i = 0; i < result.data().used; ++i)
0692    {
0693       result.data().dp[i] = MP_MASK & ~(result.data().dp[i]);
0694    }
0695    //
0696    // We now need to pad out the left of the value with 1's to round up to a whole number of
0697    // CHAR_BIT * sizeof(mp_digit) units.  Otherwise we'll end up with a very strange number of
0698    // bits set!
0699    //
0700    unsigned shift = result.data().used * DIGIT_BIT;    // How many bits we're actually using
0701    // How many bits we actually need, reduced by one to account for a mythical sign bit:
0702    int padding = result.data().used * std::numeric_limits<mp_digit>::digits - shift - 1;
0703    while(padding >= std::numeric_limits<mp_digit>::digits)
0704       padding -= std::numeric_limits<mp_digit>::digits;
0705
0706    // Create a mask providing the extra bits we need and add to result:
0707    tommath_int mask;
0708    mask = static_cast<long long>((1u << padding) - 1);
0709    eval_left_shift(mask, shift);
0710    add(result, mask);
0711 }
0712 */
0713 inline bool eval_is_zero(const tommath_int& val)
0714 {
0715    return mp_iszero(&val.data());
0716 }
0717 inline int eval_get_sign(const tommath_int& val)
0718 {
0719 #ifndef mp_isneg
0720    return mp_iszero(&val.data()) ? 0 : SIGN(&val.data()) ? -1 : 1;
0721 #else
0722    return mp_iszero(&val.data()) ? 0 : mp_isneg(&val.data()) ? -1 : 1;
0723 #endif
0724 }
0725
0726 inline void eval_convert_to(unsigned long long* result, const tommath_int& val)
0727 {
0728    if (mp_isneg(&val.data()))
0729    {
0730       BOOST_MP_THROW_EXCEPTION(std::range_error("Converting negative arbitrary precision value to unsigned."));
0731    }
0732 #ifdef MP_DEPRECATED
0733    *result = mp_get_ull(&val.data());
0734 #else
0735    *result = mp_get_long_long(const_cast<mp_int*>(&val.data()));
0736 #endif
0737 }
0738
0739 inline void eval_convert_to(long long* result, const tommath_int& val)
0740 {
0741    if (!mp_iszero(&val.data()) && (mp_count_bits(const_cast<::mp_int*>(&val.data())) > std::numeric_limits<long long>::digits))
0742    {
0743       *result = mp_isneg(&val.data()) ? (std::numeric_limits<long long>::min)() : (std::numeric_limits<long long>::max)();
0744       return;
0745    }
0746 #ifdef MP_DEPRECATED
0747    unsigned long long r = mp_get_mag_ull(&val.data());
0748 #else
0749    unsigned long long r = mp_get_long_long(const_cast<mp_int*>(&val.data()));
0750 #endif
0751    if (mp_isneg(&val.data()))
0752       *result = -static_cast<long long>(r);
0753    else
0754       *result = r;
0755 }
0756
0757 #ifdef BOOST_HAS_INT128
0758 inline void eval_convert_to(uint128_type* result, const tommath_int& val)
0759 {
0760 #ifdef MP_DEPRECATED
0761    if (mp_ubin_size(&val.data()) > sizeof(uint128_type))
0762    {
0763       *result = ~static_cast<uint128_type>(0);
0764       return;
0765    }
0766    unsigned char buf[sizeof(uint128_type)];
0767    std::size_t   len;
0768    detail::check_tommath_result(mp_to_ubin(&val.data(), buf, sizeof(buf), &len));
0769    *result = 0;
0770    for (std::size_t i = 0; i < len; ++i)
0771    {
0772       *result <<= CHAR_BIT;
0773       *result |= buf[i];
0774    }
0775 #else
0776    std::size_t len = mp_unsigned_bin_size(const_cast<mp_int*>(&val.data()));
0777    if (len > sizeof(uint128_type))
0778    {
0779       *result = ~static_cast<uint128_type>(0);
0780       return;
0781    }
0782    unsigned char buf[sizeof(uint128_type)];
0783    detail::check_tommath_result(mp_to_unsigned_bin(const_cast<mp_int*>(&val.data()), buf));
0784    *result = 0;
0785    for (std::size_t i = 0; i < len; ++i)
0786    {
0787       *result <<= CHAR_BIT;
0788       *result |= buf[i];
0789    }
0790 #endif
0791 }
0792 inline void eval_convert_to(int128_type* result, const tommath_int& val)
0793 {
0794    uint128_type r;
0795    eval_convert_to(&r, val);
0796    if (mp_isneg(&val.data()))
0797       *result = -static_cast<int128_type>(r);
0798    else
0799       *result = r;
0800 }
0801 #endif
0802 #if defined(BOOST_HAS_FLOAT128)
0803 inline void eval_convert_to(float128_type* result, const tommath_int& val) noexcept
0804 {
0805    *result = float128_procs::strtoflt128(val.str(0, std::ios_base::scientific).c_str(), nullptr);
0806 }
0807 #endif
0808 inline void eval_convert_to(long double* result, const tommath_int& val) noexcept
0809 {
0810    *result = std::strtold(val.str(0, std::ios_base::scientific).c_str(), nullptr);
0811 }
0812 inline void eval_convert_to(double* result, const tommath_int& val) noexcept
0813 {
0814    *result = std::strtod(val.str(0, std::ios_base::scientific).c_str(), nullptr);
0815 }
0816 inline void eval_convert_to(float* result, const tommath_int& val) noexcept
0817 {
0818    *result = std::strtof(val.str(0, std::ios_base::scientific).c_str(), nullptr);
0819 }
0820
0821
0822 inline void eval_abs(tommath_int& result, const tommath_int& val)
0823 {
0824    detail::check_tommath_result(mp_abs(const_cast< ::mp_int*>(&val.data()), &result.data()));
0825 }
0826 inline void eval_gcd(tommath_int& result, const tommath_int& a, const tommath_int& b)
0827 {
0828    detail::check_tommath_result(mp_gcd(const_cast< ::mp_int*>(&a.data()), const_cast< ::mp_int*>(&b.data()), const_cast< ::mp_int*>(&result.data())));
0829 }
0830 inline void eval_lcm(tommath_int& result, const tommath_int& a, const tommath_int& b)
0831 {
0832    detail::check_tommath_result(mp_lcm(const_cast< ::mp_int*>(&a.data()), const_cast< ::mp_int*>(&b.data()), const_cast< ::mp_int*>(&result.data())));
0833 }
0834 inline void eval_powm(tommath_int& result, const tommath_int& base, const tommath_int& p, const tommath_int& m)
0835 {
0836    if (eval_get_sign(p) < 0)
0837    {
0838       BOOST_MP_THROW_EXCEPTION(std::runtime_error("powm requires a positive exponent."));
0839    }
0840    detail::check_tommath_result(mp_exptmod(const_cast< ::mp_int*>(&base.data()), const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&m.data()), &result.data()));
0841 }
0842
0843 inline void eval_qr(const tommath_int& x, const tommath_int& y,
0844                     tommath_int& q, tommath_int& r)
0845 {
0846    detail::check_tommath_result(mp_div(const_cast< ::mp_int*>(&x.data()), const_cast< ::mp_int*>(&y.data()), &q.data(), &r.data()));
0847 }
0848
0849 inline std::size_t eval_lsb(const tommath_int& val)
0850 {
0851    int c = eval_get_sign(val);
0852    if (c == 0)
0853    {
0854       BOOST_MP_THROW_EXCEPTION(std::domain_error("No bits were set in the operand."));
0855    }
0856    if (c < 0)
0857    {
0858       BOOST_MP_THROW_EXCEPTION(std::domain_error("Testing individual bits in negative values is not supported - results are undefined."));
0859    }
0860    return mp_cnt_lsb(const_cast< ::mp_int*>(&val.data()));
0861 }
0862
0863 inline std::size_t eval_msb(const tommath_int& val)
0864 {
0865    int c = eval_get_sign(val);
0866    if (c == 0)
0867    {
0868       BOOST_MP_THROW_EXCEPTION(std::domain_error("No bits were set in the operand."));
0869    }
0870    if (c < 0)
0871    {
0872       BOOST_MP_THROW_EXCEPTION(std::domain_error("Testing individual bits in negative values is not supported - results are undefined."));
0873    }
0874    return mp_count_bits(const_cast< ::mp_int*>(&val.data())) - 1;
0875 }
0876
0877 template <class Integer>
0878 inline typename std::enable_if<boost::multiprecision::detail::is_unsigned<Integer>::value, Integer>::type eval_integer_modulus(const tommath_int& x, Integer val)
0879 {
0880 #ifndef MP_DIGIT_BIT
0881    constexpr const mp_digit m = (static_cast<mp_digit>(1) << DIGIT_BIT) - 1;
0882 #else
0883    constexpr const mp_digit m = (static_cast<mp_digit>(1) << MP_DIGIT_BIT) - 1;
0884 #endif
0885    if (val <= m)
0886    {
0887       mp_digit d;
0888       detail::check_tommath_result(mp_mod_d(const_cast< ::mp_int*>(&x.data()), static_cast<mp_digit>(val), &d));
0889       return d;
0890    }
0891    else
0892    {
0893       return default_ops::eval_integer_modulus(x, val);
0894    }
0895 }
0896 template <class Integer>
0897 inline typename std::enable_if<boost::multiprecision::detail::is_signed<Integer>::value && boost::multiprecision::detail::is_integral<Integer>::value, Integer>::type eval_integer_modulus(const tommath_int& x, Integer val)
0898 {
0899    return eval_integer_modulus(x, boost::multiprecision::detail::unsigned_abs(val));
0900 }
0901
0902 inline std::size_t hash_value(const tommath_int& val)
0903 {
0904    std::size_t result = 0;
0905    std::size_t len    = val.data().used;
0906    for (std::size_t i = 0; i < len; ++i)
0907       boost::multiprecision::detail::hash_combine(result, val.data().dp[i]);
0908    boost::multiprecision::detail::hash_combine(result, val.data().sign);
0909    return result;
0910 }
0911
0912 } // namespace backends
0913
0914 template <>
0915 struct number_category<tommath_int> : public std::integral_constant<int, number_kind_integer>
0916 {};
0917
0918 }
0919 } // namespace boost::multiprecision
0920
0921 namespace std {
0922
0923 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0924 class numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >
0925 {
0926    using number_type = boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates>;
0927
0928  public:
0929    static constexpr bool is_specialized = true;
0930    //
0931    // Largest and smallest numbers are bounded only by available memory, set
0932    // to zero:
0933    //
0934    static number_type(min)()
0935    {
0936       return number_type();
0937    }
0938    static number_type(max)()
0939    {
0940       return number_type();
0941    }
0942    static number_type                        lowest() { return (min)(); }
0943    static constexpr int                digits       = INT_MAX;
0944    static constexpr int                digits10     = (INT_MAX / 1000) * 301L;
0945    static constexpr int                max_digits10 = digits10 + 3;
0946    static constexpr bool               is_signed    = true;
0947    static constexpr bool               is_integer   = true;
0948    static constexpr bool               is_exact     = true;
0949    static constexpr int                radix        = 2;
0950    static number_type                        epsilon() { return number_type(); }
0951    static number_type                        round_error() { return number_type(); }
0952    static constexpr int                min_exponent      = 0;
0953    static constexpr int                min_exponent10    = 0;
0954    static constexpr int                max_exponent      = 0;
0955    static constexpr int                max_exponent10    = 0;
0956    static constexpr bool               has_infinity      = false;
0957    static constexpr bool               has_quiet_NaN     = false;
0958    static constexpr bool               has_signaling_NaN = false;
0959 #ifdef _MSC_VER
0960 #pragma warning(push)
0961 #pragma warning(disable : 4996)
0962 #endif
0963    static constexpr float_denorm_style       has_denorm      = denorm_absent;
0964 #ifdef _MSC_VER
0965 #pragma warning(pop)
0966 #endif
0967    static constexpr bool                     has_denorm_loss = false;
0968    static number_type                        infinity() { return number_type(); }
0969    static number_type                        quiet_NaN() { return number_type(); }
0970    static number_type                        signaling_NaN() { return number_type(); }
0971    static number_type                        denorm_min() { return number_type(); }
0972    static constexpr bool               is_iec559       = false;
0973    static constexpr bool               is_bounded      = false;
0974    static constexpr bool               is_modulo       = false;
0975    static constexpr bool               traps           = false;
0976    static constexpr bool               tinyness_before = false;
0977    static constexpr float_round_style  round_style     = round_toward_zero;
0978 };
0979
0980 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0981 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::digits;
0982 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0983 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::digits10;
0984 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0985 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_digits10;
0986 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0987 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_signed;
0988 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0989 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_integer;
0990 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0991 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_exact;
0992 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0993 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::radix;
0994 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0995 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::min_exponent;
0996 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0997 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::min_exponent10;
0998 template <boost::multiprecision::expression_template_option ExpressionTemplates>
0999 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_exponent;
1000 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1001 constexpr int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_exponent10;
1002 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1003 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_infinity;
1004 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1005 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_quiet_NaN;
1006 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1007 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_signaling_NaN;
1008 #ifdef _MSC_VER
1009 #pragma warning(push)
1010 #pragma warning(disable : 4996)
1011 #endif
1012 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1013 constexpr float_denorm_style numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_denorm;
1014 #ifdef _MSC_VER
1015 #pragma warning(pop)
1016 #endif
1017 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1018 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_denorm_loss;
1019 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1020 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_iec559;
1021 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1022 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_bounded;
1023 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1024 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_modulo;
1025 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1026 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::traps;
1027 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1028 constexpr bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::tinyness_before;
1029 template <boost::multiprecision::expression_template_option ExpressionTemplates>
1030 constexpr float_round_style numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::round_style;
1031
1032 } // namespace std
1033
1034 #endif