Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:42:13 

0001 ///////////////////////////////////////////////////////////////
0002 //  Copyright 2020 Madhur Chauhan. 
0003 //  Copyright 2020 John Maddock. Distributed under the Boost
0004 //  Software License, Version 1.0. (See accompanying file
0005 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
0006 
0007 #ifndef BOOST_MP_ADD_UNSIGNED_HPP
0008 #define BOOST_MP_ADD_UNSIGNED_HPP
0009 
0010 #include <boost/multiprecision/cpp_int/intel_intrinsics.hpp>
0011 #include <boost/multiprecision/detail/assert.hpp>
0012 
0013 namespace boost { namespace multiprecision { namespace backends {
0014 
0015 template <class CppInt1, class CppInt2, class CppInt3>
0016 inline BOOST_MP_CXX14_CONSTEXPR void add_unsigned_constexpr(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0017 {
0018    using ::boost::multiprecision::std_constexpr::swap;
0019    //
0020    // This is the generic, C++ only version of addition.
0021    // It's also used for all constexpr branches, hence the name.
0022    // Nothing fancy, just let uintmax_t take the strain:
0023    //
0024    double_limb_type carry = 0;
0025    std::size_t         m(0), x(0);
0026    std::size_t         as = a.size();
0027    std::size_t         bs = b.size();
0028    minmax(as, bs, m, x);
0029    if (x == 1)
0030    {
0031       bool s = a.sign();
0032       result = static_cast<double_limb_type>(*a.limbs()) + static_cast<double_limb_type>(*b.limbs());
0033       result.sign(s);
0034       return;
0035    }
0036    result.resize(x, x);
0037    typename CppInt2::const_limb_pointer pa     = a.limbs();
0038    typename CppInt3::const_limb_pointer pb     = b.limbs();
0039    typename CppInt1::limb_pointer       pr     = result.limbs();
0040    typename CppInt1::limb_pointer       pr_end = pr + m;
0041 
0042    if (as < bs)
0043       swap(pa, pb);
0044 
0045    // First where a and b overlap:
0046    while (pr != pr_end)
0047    {
0048       carry += static_cast<double_limb_type>(*pa) + static_cast<double_limb_type>(*pb);
0049 #ifdef __MSVC_RUNTIME_CHECKS
0050       *pr = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0051 #else
0052       *pr = static_cast<limb_type>(carry);
0053 #endif
0054       carry >>= CppInt1::limb_bits;
0055       ++pr, ++pa, ++pb;
0056    }
0057    pr_end += x - m;
0058    // Now where only a has digits:
0059    while (pr != pr_end)
0060    {
0061       if (!carry)
0062       {
0063          if (pa != pr)
0064             std_constexpr::copy(pa, pa + (pr_end - pr), pr);
0065          break;
0066       }
0067       carry += static_cast<double_limb_type>(*pa);
0068 #ifdef __MSVC_RUNTIME_CHECKS
0069       *pr = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0070 #else
0071       *pr = static_cast<limb_type>(carry);
0072 #endif
0073       carry >>= CppInt1::limb_bits;
0074       ++pr, ++pa;
0075    }
0076    if (carry)
0077    {
0078       // We overflowed, need to add one more limb:
0079       result.resize(x + 1, x + 1);
0080       if (result.size() > x)
0081          result.limbs()[x] = static_cast<limb_type>(1u);
0082    }
0083    result.normalize();
0084    result.sign(a.sign());
0085 }
0086 //
0087 // Core subtraction routine for all non-trivial cpp_int's:
0088 //
0089 template <class CppInt1, class CppInt2, class CppInt3>
0090 inline BOOST_MP_CXX14_CONSTEXPR void subtract_unsigned_constexpr(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0091 {
0092    using ::boost::multiprecision::std_constexpr::swap;
0093    //
0094    // This is the generic, C++ only version of subtraction.
0095    // It's also used for all constexpr branches, hence the name.
0096    // Nothing fancy, just let uintmax_t take the strain:
0097    //
0098    double_limb_type borrow = 0;
0099    std::size_t         m(0), x(0);
0100    minmax(a.size(), b.size(), m, x);
0101    //
0102    // special cases for small limb counts:
0103    //
0104    if (x == 1)
0105    {
0106       bool      s  = a.sign();
0107       limb_type al = *a.limbs();
0108       limb_type bl = *b.limbs();
0109       if (bl > al)
0110       {
0111          ::boost::multiprecision::std_constexpr::swap(al, bl);
0112          s = !s;
0113       }
0114       result = al - bl;
0115       result.sign(s);
0116       return;
0117    }
0118    // This isn't used till later, but comparison has to occur before we resize the result,
0119    // as that may also resize a or b if this is an inplace operation:
0120    int c = a.compare_unsigned(b);
0121    // Set up the result vector:
0122    result.resize(x, x);
0123    // Now that a, b, and result are stable, get pointers to their limbs:
0124    typename CppInt2::const_limb_pointer pa      = a.limbs();
0125    typename CppInt3::const_limb_pointer pb      = b.limbs();
0126    typename CppInt1::limb_pointer       pr      = result.limbs();
0127    bool                                 swapped = false;
0128    if (c < 0)
0129    {
0130       swap(pa, pb);
0131       swapped = true;
0132    }
0133    else if (c == 0)
0134    {
0135       result = static_cast<limb_type>(0);
0136       return;
0137    }
0138 
0139    std::size_t i = 0;
0140    // First where a and b overlap:
0141    while (i < m)
0142    {
0143       borrow = static_cast<double_limb_type>(pa[i]) - static_cast<double_limb_type>(pb[i]) - borrow;
0144       pr[i]  = static_cast<limb_type>(borrow);
0145       borrow = (borrow >> CppInt1::limb_bits) & 1u;
0146       ++i;
0147    }
0148    // Now where only a has digits, only as long as we've borrowed:
0149    while (borrow && (i < x))
0150    {
0151       borrow = static_cast<double_limb_type>(pa[i]) - borrow;
0152       pr[i]  = static_cast<limb_type>(borrow);
0153       borrow = (borrow >> CppInt1::limb_bits) & 1u;
0154       ++i;
0155    }
0156    // Any remaining digits are the same as those in pa:
0157    if ((x != i) && (pa != pr))
0158       std_constexpr::copy(pa + i, pa + x, pr + i);
0159    BOOST_MP_ASSERT(0 == borrow);
0160 
0161    //
0162    // We may have lost digits, if so update limb usage count:
0163    //
0164    result.normalize();
0165    result.sign(a.sign());
0166    if (swapped)
0167       result.negate();
0168 }
0169 
0170 
0171 #ifdef BOOST_MP_HAS_IMMINTRIN_H
0172 //
0173 // This is the key addition routine where all the argument types are non-trivial cpp_int's:
0174 //
0175 //
0176 // This optimization is limited to: GCC, LLVM, ICC (Intel), MSVC for x86_64 and i386.
0177 // If your architecture and compiler supports ADC intrinsic, please file a bug
0178 //
0179 // As of May, 2020 major compilers don't recognize carry chain though adc
0180 // intrinsics are used to hint compilers to use ADC and still compilers don't
0181 // unroll the loop efficiently (except LLVM) so manual unrolling is done.
0182 //
0183 // Also note that these intrinsics were only introduced by Intel as part of the
0184 // ADX processor extensions, even though the addc instruction has been available
0185 // for basically all x86 processors.  That means gcc-9, clang-9, msvc-14.2 and up
0186 // are required to support these intrinsics.
0187 //
0188 template <class CppInt1, class CppInt2, class CppInt3>
0189 inline BOOST_MP_CXX14_CONSTEXPR void add_unsigned(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0190 {
0191 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0192    if (BOOST_MP_IS_CONST_EVALUATED(a.size()))
0193    {
0194       add_unsigned_constexpr(result, a, b);
0195    }
0196    else
0197 #endif
0198    {
0199       using std::swap;
0200 
0201       // Nothing fancy, just let uintmax_t take the strain:
0202       std::size_t m(0), x(0);
0203       std::size_t as = a.size();
0204       std::size_t bs = b.size();
0205       minmax(as, bs, m, x);
0206       if (x == 1)
0207       {
0208          bool s = a.sign();
0209          result = static_cast<double_limb_type>(*a.limbs()) + static_cast<double_limb_type>(*b.limbs());
0210          result.sign(s);
0211          return;
0212       }
0213       result.resize(x, x);
0214       typename CppInt2::const_limb_pointer pa = a.limbs();
0215       typename CppInt3::const_limb_pointer pb = b.limbs();
0216       typename CppInt1::limb_pointer       pr = result.limbs();
0217 
0218       if (as < bs)
0219          swap(pa, pb);
0220       // First where a and b overlap:
0221       std::size_t      i = 0;
0222       unsigned char carry = 0;
0223 #if defined(BOOST_MSVC) && !defined(BOOST_HAS_INT128) && defined(_M_X64)
0224       //
0225       // Special case for 32-bit limbs on 64-bit architecture - we can process
0226       // 2 limbs with each instruction.
0227       //
0228       for (; i + 8 <= m; i += 8)
0229       {
0230          carry = _addcarry_u64(carry, *(unsigned long long*)(pa + i + 0), *(unsigned long long*)(pb + i + 0), (unsigned long long*)(pr + i));
0231          carry = _addcarry_u64(carry, *(unsigned long long*)(pa + i + 2), *(unsigned long long*)(pb + i + 2), (unsigned long long*)(pr + i + 2));
0232          carry = _addcarry_u64(carry, *(unsigned long long*)(pa + i + 4), *(unsigned long long*)(pb + i + 4), (unsigned long long*)(pr + i + 4));
0233          carry = _addcarry_u64(carry, *(unsigned long long*)(pa + i + 6), *(unsigned long long*)(pb + i + 6), (unsigned long long*)(pr + i + 6));
0234       }
0235 #else
0236       for (; i + 4 <= m; i += 4)
0237       {
0238          carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i + 0], pb[i + 0], pr + i);
0239          carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i + 1], pb[i + 1], pr + i + 1);
0240          carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i + 2], pb[i + 2], pr + i + 2);
0241          carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i + 3], pb[i + 3], pr + i + 3);
0242       }
0243 #endif
0244       for (; i < m; ++i)
0245          carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i], pb[i], pr + i);
0246       for (; i < x && carry; ++i)
0247          // We know carry is 1, so we just need to increment pa[i] (ie add a literal 1) and capture the carry:
0248          carry = ::boost::multiprecision::detail::addcarry_limb(0, pa[i], 1, pr + i);
0249       if (i == x && carry)
0250       {
0251          // We overflowed, need to add one more limb:
0252          result.resize(x + 1, x + 1);
0253          if (result.size() > x)
0254             result.limbs()[x] = static_cast<limb_type>(1u);
0255       }
0256       else if ((x != i) && (pa != pr))
0257          // Copy remaining digits only if we need to:
0258          std_constexpr::copy(pa + i, pa + x, pr + i);
0259       result.normalize();
0260       result.sign(a.sign());
0261    }
0262 }
0263 
0264 template <class CppInt1, class CppInt2, class CppInt3>
0265 inline BOOST_MP_CXX14_CONSTEXPR void subtract_unsigned(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0266 {
0267 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0268    if (BOOST_MP_IS_CONST_EVALUATED(a.size()))
0269    {
0270       subtract_unsigned_constexpr(result, a, b);
0271    }
0272    else
0273 #endif
0274    {
0275       using std::swap;
0276 
0277       // Nothing fancy, just let uintmax_t take the strain:
0278       std::size_t         m(0), x(0);
0279       minmax(a.size(), b.size(), m, x);
0280       //
0281       // special cases for small limb counts:
0282       //
0283       if (x == 1)
0284       {
0285          bool      s = a.sign();
0286          limb_type al = *a.limbs();
0287          limb_type bl = *b.limbs();
0288          if (bl > al)
0289          {
0290             ::boost::multiprecision::std_constexpr::swap(al, bl);
0291             s = !s;
0292          }
0293          result = al - bl;
0294          result.sign(s);
0295          return;
0296       }
0297       // This isn't used till later, but comparison has to occur before we resize the result,
0298       // as that may also resize a or b if this is an inplace operation:
0299       int c = a.compare_unsigned(b);
0300       // Set up the result vector:
0301       result.resize(x, x);
0302       // Now that a, b, and result are stable, get pointers to their limbs:
0303       typename CppInt2::const_limb_pointer pa = a.limbs();
0304       typename CppInt3::const_limb_pointer pb = b.limbs();
0305       typename CppInt1::limb_pointer       pr = result.limbs();
0306       bool                                 swapped = false;
0307       if (c < 0)
0308       {
0309          swap(pa, pb);
0310          swapped = true;
0311       }
0312       else if (c == 0)
0313       {
0314          result = static_cast<limb_type>(0);
0315          return;
0316       }
0317 
0318       std::size_t i = 0;
0319       unsigned char borrow = 0;
0320       // First where a and b overlap:
0321 #if defined(BOOST_MSVC) && !defined(BOOST_HAS_INT128) && defined(_M_X64)
0322       //
0323       // Special case for 32-bit limbs on 64-bit architecture - we can process
0324       // 2 limbs with each instruction.
0325       //
0326       for (; i + 8 <= m; i += 8)
0327       {
0328          borrow = _subborrow_u64(borrow, *reinterpret_cast<const unsigned long long*>(pa + i), *reinterpret_cast<const unsigned long long*>(pb + i), reinterpret_cast<unsigned long long*>(pr + i));
0329          borrow = _subborrow_u64(borrow, *reinterpret_cast<const unsigned long long*>(pa + i + 2), *reinterpret_cast<const unsigned long long*>(pb + i + 2), reinterpret_cast<unsigned long long*>(pr + i + 2));
0330          borrow = _subborrow_u64(borrow, *reinterpret_cast<const unsigned long long*>(pa + i + 4), *reinterpret_cast<const unsigned long long*>(pb + i + 4), reinterpret_cast<unsigned long long*>(pr + i + 4));
0331          borrow = _subborrow_u64(borrow, *reinterpret_cast<const unsigned long long*>(pa + i + 6), *reinterpret_cast<const unsigned long long*>(pb + i + 6), reinterpret_cast<unsigned long long*>(pr + i + 6));
0332       }
0333 #else
0334       for(; i + 4 <= m; i += 4)
0335       {
0336          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i], pb[i], pr + i);
0337          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i + 1], pb[i + 1], pr + i + 1);
0338          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i + 2], pb[i + 2], pr + i + 2);
0339          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i + 3], pb[i + 3], pr + i + 3);
0340       }
0341 #endif
0342       for (; i < m; ++i)
0343          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i], pb[i], pr + i);
0344 
0345       // Now where only a has digits, only as long as we've borrowed:
0346       while (borrow && (i < x))
0347       {
0348          borrow = boost::multiprecision::detail::subborrow_limb(borrow, pa[i], 0, pr + i);
0349          ++i;
0350       }
0351       // Any remaining digits are the same as those in pa:
0352       if ((x != i) && (pa != pr))
0353          std_constexpr::copy(pa + i, pa + x, pr + i);
0354       BOOST_MP_ASSERT(0 == borrow);
0355 
0356       //
0357       // We may have lost digits, if so update limb usage count:
0358       //
0359       result.normalize();
0360       result.sign(a.sign());
0361       if (swapped)
0362          result.negate();
0363    }  // constepxr.
0364 }
0365 
0366 #else
0367 
0368 template <class CppInt1, class CppInt2, class CppInt3>
0369 inline BOOST_MP_CXX14_CONSTEXPR void add_unsigned(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0370 {
0371    add_unsigned_constexpr(result, a, b);
0372 }
0373 
0374 template <class CppInt1, class CppInt2, class CppInt3>
0375 inline BOOST_MP_CXX14_CONSTEXPR void subtract_unsigned(CppInt1& result, const CppInt2& a, const CppInt3& b) noexcept(is_non_throwing_cpp_int<CppInt1>::value)
0376 {
0377    subtract_unsigned_constexpr(result, a, b);
0378 }
0379 
0380 #endif
0381 
0382 } } }  // namespaces
0383 
0384 
0385 #endif
0386 
0387
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!