Chris@16: ///////////////////////////////////////////////////////////////
Chris@16: //  Copyright 2012 John Maddock. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
Chris@16: //
Chris@16: // Comparison operators for cpp_int_backend:
Chris@16: //
Chris@16: #ifndef BOOST_MP_CPP_INT_BIT_HPP
Chris@16: #define BOOST_MP_CPP_INT_BIT_HPP
Chris@16: 
Chris@16: namespace boost{ namespace multiprecision{ namespace backends{
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: void is_valid_bitwise_op(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::int_<checked>&)
Chris@16: {
Chris@16:    if(result.sign() || o.sign())
Chris@16:       BOOST_THROW_EXCEPTION(std::range_error("Bitwise operations on negative values results in undefined behavior."));
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: void is_valid_bitwise_op(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& , const mpl::int_<unchecked>&){}
Chris@16: 
Chris@16: template <class CppInt1, class CppInt2, class Op>
Chris@16: void bitwise_op(
Chris@16:    CppInt1& result,
Chris@16:    const CppInt2& o,
Chris@101:    Op op, const mpl::true_&) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<CppInt1>::value))
Chris@16: {
Chris@16:    //
Chris@16:    // There are 4 cases:
Chris@16:    // * Both positive.
Chris@16:    // * result negative, o positive.
Chris@16:    // * o negative, result positive.
Chris@16:    // * Both negative.
Chris@16:    //
Chris@16:    // When one arg is negative we convert to 2's complement form "on the fly",
Chris@16:    // and then convert back to signed-magnitude form at the end.
Chris@16:    //
Chris@16:    // Note however, that if the type is checked, then bitwise ops on negative values
Chris@16:    // are not permitted and an exception will result.
Chris@16:    //
Chris@16:    is_valid_bitwise_op(result, o, typename CppInt1::checked_type());
Chris@16:    //
Chris@16:    // First figure out how big the result needs to be and set up some data:
Chris@16:    //
Chris@16:    unsigned rs = result.size();
Chris@16:    unsigned os = o.size();
Chris@16:    unsigned m, x;
Chris@16:    minmax(rs, os, m, x);
Chris@16:    result.resize(x, x);
Chris@16:    typename CppInt1::limb_pointer pr = result.limbs();
Chris@16:    typename CppInt2::const_limb_pointer po = o.limbs();
Chris@16:    for(unsigned i = rs; i < x; ++i)
Chris@16:       pr[i] = 0;
Chris@16: 
Chris@16:    limb_type next_limb = 0;
Chris@16: 
Chris@16:    if(!result.sign())
Chris@16:    {
Chris@16:       if(!o.sign())
Chris@16:       {
Chris@16:          for(unsigned i = 0; i < os; ++i)
Chris@16:             pr[i] = op(pr[i], po[i]);
Chris@16:          for(unsigned i = os; i < x; ++i)
Chris@16:             pr[i] = op(pr[i], limb_type(0));
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          // "o" is negative:
Chris@16:          double_limb_type carry = 1;
Chris@16:          for(unsigned i = 0; i < os; ++i)
Chris@16:          {
Chris@16:             carry += static_cast<double_limb_type>(~po[i]);
Chris@16:             pr[i] = op(pr[i], static_cast<limb_type>(carry));
Chris@16:             carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          for(unsigned i = os; i < x; ++i)
Chris@16:          {
Chris@16:             carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:             pr[i] = op(pr[i], static_cast<limb_type>(carry));
Chris@16:             carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          // Set the overflow into the "extra" limb:
Chris@16:          carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:          next_limb = op(limb_type(0), static_cast<limb_type>(carry));
Chris@16:       }
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       if(!o.sign())
Chris@16:       {
Chris@16:          // "result" is negative:
Chris@16:          double_limb_type carry = 1;
Chris@16:          for(unsigned i = 0; i < os; ++i)
Chris@16:          {
Chris@16:             carry += static_cast<double_limb_type>(~pr[i]);
Chris@16:             pr[i] = op(static_cast<limb_type>(carry), po[i]);
Chris@16:             carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          for(unsigned i = os; i < x; ++i)
Chris@16:          {
Chris@16:             carry += static_cast<double_limb_type>(~pr[i]);
Chris@16:             pr[i] = op(static_cast<limb_type>(carry), limb_type(0));
Chris@16:             carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          // Set the overflow into the "extra" limb:
Chris@16:          carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:          next_limb = op(static_cast<limb_type>(carry), limb_type(0));
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          // both are negative:
Chris@16:          double_limb_type r_carry = 1;
Chris@16:          double_limb_type o_carry = 1;
Chris@16:          for(unsigned i = 0; i < os; ++i)
Chris@16:          {
Chris@16:             r_carry += static_cast<double_limb_type>(~pr[i]);
Chris@16:             o_carry += static_cast<double_limb_type>(~po[i]);
Chris@16:             pr[i] = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
Chris@16:             r_carry >>= CppInt1::limb_bits;
Chris@16:             o_carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          for(unsigned i = os; i < x; ++i)
Chris@16:          {
Chris@16:             r_carry += static_cast<double_limb_type>(~pr[i]);
Chris@16:             o_carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:             pr[i] = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
Chris@16:             r_carry >>= CppInt1::limb_bits;
Chris@16:             o_carry >>= CppInt1::limb_bits;
Chris@16:          }
Chris@16:          // Set the overflow into the "extra" limb:
Chris@16:          r_carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:          o_carry += static_cast<double_limb_type>(~limb_type(0));
Chris@16:          next_limb = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
Chris@16:       }
Chris@16:    }
Chris@16:    //
Chris@16:    // See if the result is negative or not:
Chris@16:    //
Chris@16:    if(static_cast<signed_limb_type>(next_limb) < 0)
Chris@16:    {
Chris@16:       result.sign(true);
Chris@16:       double_limb_type carry = 1;
Chris@16:       for(unsigned i = 0; i < x; ++i)
Chris@16:       {
Chris@16:          carry += static_cast<double_limb_type>(~pr[i]);
Chris@16:          pr[i] = static_cast<limb_type>(carry);
Chris@16:          carry >>= CppInt1::limb_bits;
Chris@16:       }
Chris@16:    }
Chris@16:    else
Chris@16:       result.sign(false);
Chris@16: 
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@101: template <class CppInt1, class CppInt2, class Op>
Chris@101: void bitwise_op(
Chris@101:    CppInt1& result,
Chris@101:    const CppInt2& o,
Chris@101:    Op op, const mpl::false_&) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<CppInt1>::value))
Chris@101: {
Chris@101:    //
Chris@101:    // Both arguments are unsigned types, very simple case handled as a special case.
Chris@101:    //
Chris@101:    // First figure out how big the result needs to be and set up some data:
Chris@101:    //
Chris@101:    unsigned rs = result.size();
Chris@101:    unsigned os = o.size();
Chris@101:    unsigned m, x;
Chris@101:    minmax(rs, os, m, x);
Chris@101:    result.resize(x, x);
Chris@101:    typename CppInt1::limb_pointer pr = result.limbs();
Chris@101:    typename CppInt2::const_limb_pointer po = o.limbs();
Chris@101:    for(unsigned i = rs; i < x; ++i)
Chris@101:       pr[i] = 0;
Chris@101: 
Chris@101:    for(unsigned i = 0; i < os; ++i)
Chris@101:       pr[i] = op(pr[i], po[i]);
Chris@101:    for(unsigned i = os; i < x; ++i)
Chris@101:       pr[i] = op(pr[i], limb_type(0));
Chris@101: 
Chris@101:    result.normalize();
Chris@101: }
Chris@101: 
Chris@16: struct bit_and{ limb_type operator()(limb_type a, limb_type b)const BOOST_NOEXCEPT { return a & b; } };
Chris@16: struct bit_or { limb_type operator()(limb_type a, limb_type b)const BOOST_NOEXCEPT { return a | b; } };
Chris@16: struct bit_xor{ limb_type operator()(limb_type a, limb_type b)const BOOST_NOEXCEPT { return a ^ b; } };
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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
Chris@16:    eval_bitwise_and(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@101:    bitwise_op(result, o, bit_and(), 
Chris@101:       mpl::bool_<std::numeric_limits<number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::is_signed || std::numeric_limits<number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > >::is_signed>());
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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
Chris@16:    eval_bitwise_or(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@101:    bitwise_op(result, o, bit_or(),
Chris@101:       mpl::bool_<std::numeric_limits<number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::is_signed || std::numeric_limits<number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > >::is_signed>());
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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
Chris@16:    eval_bitwise_xor(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@101:    bitwise_op(result, o, bit_xor(),
Chris@101:       mpl::bool_<std::numeric_limits<number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::is_signed || std::numeric_limits<number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > >::is_signed>());
Chris@101: }
Chris@101: //
Chris@101: // Again for operands which are single limbs:
Chris@101: //
Chris@101: template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
Chris@101: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
Chris@101:    eval_bitwise_and(
Chris@101:       cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
Chris@101:       limb_type l) BOOST_NOEXCEPT
Chris@101: {
Chris@101:    result.limbs()[0] &= l;
Chris@101:    result.resize(1, 1);
Chris@101: }
Chris@101: 
Chris@101: template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
Chris@101: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
Chris@101:    eval_bitwise_or(
Chris@101:       cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
Chris@101:       limb_type l) BOOST_NOEXCEPT
Chris@101: {
Chris@101:    result.limbs()[0] |= l;
Chris@101: }
Chris@101: 
Chris@101: template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
Chris@101: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
Chris@101:    eval_bitwise_xor(
Chris@101:       cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
Chris@101:       limb_type l) BOOST_NOEXCEPT
Chris@101: {
Chris@101:    result.limbs()[0] ^= l;
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !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
Chris@16:    eval_complement(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    BOOST_STATIC_ASSERT_MSG(((Checked1 != checked) || (Checked2 != checked)), "Attempt to take the complement of a signed type results in undefined behavior.");
Chris@16:    // Increment and negate:
Chris@16:    result = o;
Chris@16:    eval_increment(result);
Chris@16:    result.negate();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value >::type
Chris@16:    eval_complement(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    unsigned os = o.size();
Chris@16:    result.resize(UINT_MAX, os);
Chris@16:    for(unsigned i = 0; i < os; ++i)
Chris@16:       result.limbs()[i] = ~o.limbs()[i];
Chris@16:    for(unsigned i = os; i < result.size(); ++i)
Chris@16:       result.limbs()[i] = ~static_cast<limb_type>(0);
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
Chris@16:    eval_left_shift(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       double_limb_type s) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    if(!s)
Chris@16:       return;
Chris@16: 
Chris@16:    limb_type offset = static_cast<limb_type>(s / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits);
Chris@16:    limb_type shift  = static_cast<limb_type>(s % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits);
Chris@16: 
Chris@16:    unsigned ors = result.size();
Chris@16:    if((ors == 1) && (!*result.limbs()))
Chris@16:       return; // shifting zero yields zero.
Chris@16:    unsigned rs = ors;
Chris@16:    if(shift && (result.limbs()[ors - 1] >> (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - shift)))
Chris@16:       ++rs; // Most significant limb will overflow when shifted
Chris@16:    rs += offset;
Chris@16:    result.resize(rs, rs);
Chris@16:    bool truncated = result.size() != rs;
Chris@16: 
Chris@16:    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
Chris@16: 
Chris@16:    if(offset > rs)
Chris@16:    {
Chris@16:       // The result is shifted past the end of the result:
Chris@16:       result = static_cast<limb_type>(0);
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    unsigned i = rs - result.size();
Chris@16:    if(shift)
Chris@16:    {
Chris@16:       // This code only works when shift is non-zero, otherwise we invoke undefined behaviour!
Chris@16:       if(!truncated)
Chris@16:       {
Chris@16:          if(rs > ors + offset)
Chris@16:          {
Chris@16:             pr[rs - 1 - i] = pr[ors - 1 - i] >> (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - shift);
Chris@16:             --rs;
Chris@16:          }
Chris@16:          else
Chris@16:          {
Chris@16:             pr[rs - 1 - i] = pr[ors - 1 - i] << shift;
Chris@16:             if(ors > 1)
Chris@16:                pr[rs - 1 - i] |= pr[ors - 2 - i] >> (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - shift);
Chris@16:             ++i;
Chris@16:          }
Chris@16:       }
Chris@16:       for(; ors > 1 + i; ++i)
Chris@16:       {
Chris@16:          pr[rs - 1 - i] = pr[ors - 1 - i] << shift;
Chris@16:          pr[rs - 1 - i] |= pr[ors - 2 - i] >> (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - shift);
Chris@16:       }
Chris@16:       if(ors >= 1 + i)
Chris@16:       {
Chris@16:          pr[rs - 1 - i] = pr[ors - 1 - i] << shift;
Chris@16:          ++i;
Chris@16:       }
Chris@16:       for(; i < rs; ++i)
Chris@16:          pr[rs - 1 - i] = 0;
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       for(; i < ors; ++i)
Chris@16:          pr[rs - 1 - i] = pr[ors - 1 - i];
Chris@16:       for(; i < rs; ++i)
Chris@16:          pr[rs - 1 - i] = 0;
Chris@16:    }
Chris@16:    //
Chris@16:    // We may have shifted off the end and have leading zeros:
Chris@16:    //
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
Chris@16:    eval_right_shift(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       double_limb_type s) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    if(!s)
Chris@16:       return;
Chris@16: 
Chris@16:    limb_type offset = static_cast<limb_type>(s / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits);
Chris@16:    limb_type shift  = static_cast<limb_type>(s % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits);
Chris@16:    unsigned ors = result.size();
Chris@16:    unsigned rs = ors;
Chris@16:    if(offset >= rs)
Chris@16:    {
Chris@16:       result = limb_type(0);
Chris@16:       return;
Chris@16:    }
Chris@16:    rs -= offset;
Chris@16:    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
Chris@16:    if((pr[ors - 1] >> shift) == 0)
Chris@16:       --rs;
Chris@16:    if(rs == 0)
Chris@16:    {
Chris@16:       result = limb_type(0);
Chris@16:       return;
Chris@16:    }
Chris@16:    unsigned i = 0;
Chris@16:    if(shift)
Chris@16:    {
Chris@16:       // This code only works for non-zero shift, otherwise we invoke undefined behaviour!
Chris@16:       for(; i + offset + 1 < ors; ++i)
Chris@16:       {
Chris@16:          pr[i] = pr[i + offset] >> shift;
Chris@16:          pr[i] |= pr[i + offset + 1] << (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - shift);
Chris@16:       }
Chris@16:       pr[i] = pr[i + offset] >> shift;
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       for(; i < rs; ++i)
Chris@16:          pr[i] = pr[i + offset];
Chris@16:    }
Chris@16:    result.resize(rs, rs);
Chris@16: }
Chris@16: 
Chris@16: //
Chris@16: // Over again for trivial cpp_int's:
Chris@16: //
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class T>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::type
Chris@16:    eval_left_shift(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, T s) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    *result.limbs() = detail::checked_left_shift(*result.limbs(), s, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class T>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::type
Chris@16:    eval_right_shift(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, T s) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    // Nothing to check here... just make sure we don't invoke undefined behavior:
Chris@16:    *result.limbs() = (static_cast<unsigned>(s) >= sizeof(*result.limbs()) * CHAR_BIT) ? 0 : *result.limbs() >> s;
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)
Chris@16:          >::type
Chris@16:    eval_bitwise_and(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
Chris@16: 
Chris@16:    using default_ops::eval_bit_test;
Chris@16:    using default_ops::eval_increment;
Chris@16: 
Chris@16:    if(result.sign() || o.sign())
Chris@16:    {
Chris@16:       static const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
Chris@16:       eval_bitwise_and(t1, t2);
Chris@16:       bool s = eval_bit_test(t1, m + 1);
Chris@16:       if(s)
Chris@16:       {
Chris@16:          eval_complement(t1, t1);
Chris@16:          eval_increment(t1);
Chris@16:       }
Chris@16:       result = t1;
Chris@16:       result.sign(s);
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       *result.limbs() &= *o.limbs();
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          >::type
Chris@16:    eval_bitwise_and(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    *result.limbs() &= *o.limbs();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)
Chris@16:          >::type
Chris@16:    eval_bitwise_or(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
Chris@16: 
Chris@16:    using default_ops::eval_bit_test;
Chris@16:    using default_ops::eval_increment;
Chris@16: 
Chris@16:    if(result.sign() || o.sign())
Chris@16:    {
Chris@16:       static const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
Chris@16:       eval_bitwise_or(t1, t2);
Chris@16:       bool s = eval_bit_test(t1, m + 1);
Chris@16:       if(s)
Chris@16:       {
Chris@16:          eval_complement(t1, t1);
Chris@16:          eval_increment(t1);
Chris@16:       }
Chris@16:       result = t1;
Chris@16:       result.sign(s);
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       *result.limbs() |= *o.limbs();
Chris@16:       result.normalize();
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          >::type
Chris@16:    eval_bitwise_or(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    *result.limbs() |= *o.limbs();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)
Chris@16:          >::type
Chris@16:    eval_bitwise_xor(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
Chris@16: 
Chris@16:    using default_ops::eval_bit_test;
Chris@16:    using default_ops::eval_increment;
Chris@16: 
Chris@16:    if(result.sign() || o.sign())
Chris@16:    {
Chris@16:       static const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
Chris@16:       cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
Chris@16:       eval_bitwise_xor(t1, t2);
Chris@16:       bool s = eval_bit_test(t1, m + 1);
Chris@16:       if(s)
Chris@16:       {
Chris@16:          eval_complement(t1, t1);
Chris@16:          eval_increment(t1);
Chris@16:       }
Chris@16:       result = t1;
Chris@16:       result.sign(s);
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       *result.limbs() ^= *o.limbs();
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          >::type
Chris@16:    eval_bitwise_xor(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    *result.limbs() ^= *o.limbs();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)
Chris@16:          >::type
Chris@16:    eval_complement(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    BOOST_STATIC_ASSERT_MSG(((Checked1 != checked) || (Checked2 != checked)), "Attempt to take the complement of a signed type results in undefined behavior.");
Chris@16:    //
Chris@16:    // If we're not checked then emulate 2's complement behavior:
Chris@16:    //
Chris@16:    if(o.sign())
Chris@16:    {
Chris@16:       *result.limbs() = *o.limbs() - 1;
Chris@16:       result.sign(false);
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       *result.limbs() = 1 + *o.limbs();
Chris@16:       result.sign(true);
Chris@16:    }
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: inline typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
Chris@16:          >::type
Chris@16:    eval_complement(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
Chris@16: {
Chris@16:    *result.limbs() = ~*o.limbs();
Chris@16:    result.normalize();
Chris@16: }
Chris@16: 
Chris@16: }}} // namespaces
Chris@16: 
Chris@16: #endif