1 ///////////////////////////////////////////////////////////////
2 // Copyright 2012 John Maddock. Distributed under the Boost
3 // Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
6 // Comparison operators for cpp_int_backend:
8 #ifndef BOOST_MP_CPP_INT_BIT_HPP
9 #define BOOST_MP_CPP_INT_BIT_HPP
13 #pragma warning(disable : 4319)
16 namespace boost { namespace multiprecision { namespace backends {
18 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>
19 BOOST_MP_CXX14_CONSTEXPR void is_valid_bitwise_op(
20 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
21 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::int_<checked>&)
23 if (result.sign() || o.sign())
24 BOOST_THROW_EXCEPTION(std::range_error("Bitwise operations on negative values results in undefined behavior."));
27 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>
28 BOOST_MP_CXX14_CONSTEXPR void is_valid_bitwise_op(
29 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&,
30 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&, const mpl::int_<unchecked>&) {}
32 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
33 BOOST_MP_CXX14_CONSTEXPR void is_valid_bitwise_op(
34 const cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>& result, const mpl::int_<checked>&)
37 BOOST_THROW_EXCEPTION(std::range_error("Bitwise operations on negative values results in undefined behavior."));
40 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
41 BOOST_MP_CXX14_CONSTEXPR void is_valid_bitwise_op(
42 const cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>&, const mpl::int_<checked>&) {}
44 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
45 BOOST_MP_CXX14_CONSTEXPR void is_valid_bitwise_op(
46 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&, const mpl::int_<unchecked>&) {}
48 template <class CppInt1, class CppInt2, class Op>
49 BOOST_MP_CXX14_CONSTEXPR void bitwise_op(
52 Op op, const mpl::true_&) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<CppInt1>::value))
57 // * result negative, o positive.
58 // * o negative, result positive.
61 // When one arg is negative we convert to 2's complement form "on the fly",
62 // and then convert back to signed-magnitude form at the end.
64 // Note however, that if the type is checked, then bitwise ops on negative values
65 // are not permitted and an exception will result.
67 is_valid_bitwise_op(result, o, typename CppInt1::checked_type());
69 // First figure out how big the result needs to be and set up some data:
71 unsigned rs = result.size();
72 unsigned os = o.size();
76 typename CppInt1::limb_pointer pr = result.limbs();
77 typename CppInt2::const_limb_pointer po = o.limbs();
78 for (unsigned i = rs; i < x; ++i)
81 limb_type next_limb = 0;
87 for (unsigned i = 0; i < os; ++i)
88 pr[i] = op(pr[i], po[i]);
89 for (unsigned i = os; i < x; ++i)
90 pr[i] = op(pr[i], limb_type(0));
95 double_limb_type carry = 1;
96 for (unsigned i = 0; i < os; ++i)
98 carry += static_cast<double_limb_type>(~po[i]);
99 pr[i] = op(pr[i], static_cast<limb_type>(carry));
100 carry >>= CppInt1::limb_bits;
102 for (unsigned i = os; i < x; ++i)
104 carry += static_cast<double_limb_type>(~limb_type(0));
105 pr[i] = op(pr[i], static_cast<limb_type>(carry));
106 carry >>= CppInt1::limb_bits;
108 // Set the overflow into the "extra" limb:
109 carry += static_cast<double_limb_type>(~limb_type(0));
110 next_limb = op(limb_type(0), static_cast<limb_type>(carry));
117 // "result" is negative:
118 double_limb_type carry = 1;
119 for (unsigned i = 0; i < os; ++i)
121 carry += static_cast<double_limb_type>(~pr[i]);
122 pr[i] = op(static_cast<limb_type>(carry), po[i]);
123 carry >>= CppInt1::limb_bits;
125 for (unsigned i = os; i < x; ++i)
127 carry += static_cast<double_limb_type>(~pr[i]);
128 pr[i] = op(static_cast<limb_type>(carry), limb_type(0));
129 carry >>= CppInt1::limb_bits;
131 // Set the overflow into the "extra" limb:
132 carry += static_cast<double_limb_type>(~limb_type(0));
133 next_limb = op(static_cast<limb_type>(carry), limb_type(0));
137 // both are negative:
138 double_limb_type r_carry = 1;
139 double_limb_type o_carry = 1;
140 for (unsigned i = 0; i < os; ++i)
142 r_carry += static_cast<double_limb_type>(~pr[i]);
143 o_carry += static_cast<double_limb_type>(~po[i]);
144 pr[i] = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
145 r_carry >>= CppInt1::limb_bits;
146 o_carry >>= CppInt1::limb_bits;
148 for (unsigned i = os; i < x; ++i)
150 r_carry += static_cast<double_limb_type>(~pr[i]);
151 o_carry += static_cast<double_limb_type>(~limb_type(0));
152 pr[i] = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
153 r_carry >>= CppInt1::limb_bits;
154 o_carry >>= CppInt1::limb_bits;
156 // Set the overflow into the "extra" limb:
157 r_carry += static_cast<double_limb_type>(~limb_type(0));
158 o_carry += static_cast<double_limb_type>(~limb_type(0));
159 next_limb = op(static_cast<limb_type>(r_carry), static_cast<limb_type>(o_carry));
163 // See if the result is negative or not:
165 if (static_cast<signed_limb_type>(next_limb) < 0)
167 double_limb_type carry = 1;
168 for (unsigned i = 0; i < x; ++i)
170 carry += static_cast<double_limb_type>(~pr[i]);
171 pr[i] = static_cast<limb_type>(carry);
172 carry >>= CppInt1::limb_bits;
176 result.resize(x + 1, x);
177 if (result.size() > x)
178 result.limbs()[x] = static_cast<limb_type>(carry);
188 template <class CppInt1, class CppInt2, class Op>
189 BOOST_MP_CXX14_CONSTEXPR void bitwise_op(
192 Op op, const mpl::false_&) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<CppInt1>::value))
195 // Both arguments are unsigned types, very simple case handled as a special case.
197 // First figure out how big the result needs to be and set up some data:
199 unsigned rs = result.size();
200 unsigned os = o.size();
202 minmax(rs, os, m, x);
204 typename CppInt1::limb_pointer pr = result.limbs();
205 typename CppInt2::const_limb_pointer po = o.limbs();
206 for (unsigned i = rs; i < x; ++i)
209 for (unsigned i = 0; i < os; ++i)
210 pr[i] = op(pr[i], po[i]);
211 for (unsigned i = os; i < x; ++i)
212 pr[i] = op(pr[i], limb_type(0));
219 BOOST_MP_CXX14_CONSTEXPR limb_type operator()(limb_type a, limb_type b) const BOOST_NOEXCEPT { return a & b; }
223 BOOST_MP_CXX14_CONSTEXPR limb_type operator()(limb_type a, limb_type b) const BOOST_NOEXCEPT { return a | b; }
227 BOOST_MP_CXX14_CONSTEXPR limb_type operator()(limb_type a, limb_type b) const BOOST_NOEXCEPT { return a ^ b; }
230 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>
231 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR 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
233 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
234 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
236 bitwise_op(result, o, bit_and(),
237 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 > ());
240 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>
241 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR 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
243 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
244 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
246 bitwise_op(result, o, bit_or(),
247 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 > ());
250 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>
251 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR 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
253 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
254 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
256 bitwise_op(result, o, bit_xor(),
257 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 > ());
260 // Again for operands which are single limbs:
262 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
263 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
265 cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
266 limb_type l) BOOST_NOEXCEPT
268 result.limbs()[0] &= l;
272 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
273 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
275 cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
276 limb_type l) BOOST_NOEXCEPT
278 result.limbs()[0] |= l;
281 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
282 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
284 cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
285 limb_type l) BOOST_NOEXCEPT
287 result.limbs()[0] ^= l;
290 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>
291 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR 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
293 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
294 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
296 BOOST_STATIC_ASSERT_MSG(((Checked1 != checked) || (Checked2 != checked)), "Attempt to take the complement of a signed type results in undefined behavior.");
297 // Increment and negate:
299 eval_increment(result);
303 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
304 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR 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
306 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
307 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
309 unsigned os = o.size();
310 result.resize(UINT_MAX, os);
311 for (unsigned i = 0; i < os; ++i)
312 result.limbs()[i] = ~o.limbs()[i];
313 for (unsigned i = os; i < result.size(); ++i)
314 result.limbs()[i] = ~static_cast<limb_type>(0);
319 inline BOOST_MP_CXX14_CONSTEXPR void left_shift_byte(Int& result, double_limb_type s)
321 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
322 limb_type shift = static_cast<limb_type>(s % Int::limb_bits);
323 unsigned ors = result.size();
324 if ((ors == 1) && (!*result.limbs()))
325 return; // shifting zero yields zero.
327 if (shift && (result.limbs()[ors - 1] >> (Int::limb_bits - shift)))
328 ++rs; // Most significant limb will overflow when shifted
330 result.resize(rs, rs);
333 typename Int::limb_pointer pr = result.limbs();
337 std::size_t bytes = static_cast<std::size_t>(s / CHAR_BIT);
338 std::size_t len = (std::min)(ors * sizeof(limb_type), rs * sizeof(limb_type) - bytes);
339 if (bytes >= rs * sizeof(limb_type))
340 result = static_cast<limb_type>(0u);
343 unsigned char* pc = reinterpret_cast<unsigned char*>(pr);
344 std::memmove(pc + bytes, pc, len);
345 std::memset(pc, 0, bytes);
350 inline BOOST_MP_CXX14_CONSTEXPR void left_shift_limb(Int& result, double_limb_type s)
352 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
353 limb_type shift = static_cast<limb_type>(s % Int::limb_bits);
355 unsigned ors = result.size();
356 if ((ors == 1) && (!*result.limbs()))
357 return; // shifting zero yields zero.
359 if (shift && (result.limbs()[ors - 1] >> (Int::limb_bits - shift)))
360 ++rs; // Most significant limb will overflow when shifted
362 result.resize(rs, rs);
364 typename Int::limb_pointer pr = result.limbs();
368 // The result is shifted past the end of the result:
369 result = static_cast<limb_type>(0);
373 unsigned i = rs - result.size();
375 pr[rs - 1 - i] = pr[ors - 1 - i];
381 inline BOOST_MP_CXX14_CONSTEXPR void left_shift_generic(Int& result, double_limb_type s)
383 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
384 limb_type shift = static_cast<limb_type>(s % Int::limb_bits);
386 unsigned ors = result.size();
387 if ((ors == 1) && (!*result.limbs()))
388 return; // shifting zero yields zero.
390 if (shift && (result.limbs()[ors - 1] >> (Int::limb_bits - shift)))
391 ++rs; // Most significant limb will overflow when shifted
393 result.resize(rs, rs);
394 bool truncated = result.size() != rs;
396 typename Int::limb_pointer pr = result.limbs();
400 // The result is shifted past the end of the result:
401 result = static_cast<limb_type>(0);
405 unsigned i = rs - result.size();
406 // This code only works when shift is non-zero, otherwise we invoke undefined behaviour!
410 if (rs > ors + offset)
412 pr[rs - 1 - i] = pr[ors - 1 - i] >> (Int::limb_bits - shift);
417 pr[rs - 1 - i] = pr[ors - 1 - i] << shift;
419 pr[rs - 1 - i] |= pr[ors - 2 - i] >> (Int::limb_bits - shift);
423 for (; rs - i >= 2 + offset; ++i)
425 pr[rs - 1 - i] = pr[rs - 1 - i - offset] << shift;
426 pr[rs - 1 - i] |= pr[rs - 2 - i - offset] >> (Int::limb_bits - shift);
428 if (rs - i >= 1 + offset)
430 pr[rs - 1 - i] = pr[rs - 1 - i - offset] << shift;
437 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
438 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
440 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
441 double_limb_type s) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
443 is_valid_bitwise_op(result, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
447 #if BOOST_ENDIAN_LITTLE_BYTE && defined(BOOST_MP_USE_LIMB_SHIFT)
448 #ifdef BOOST_NO_CXX14_CONSTEXPR
449 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - 1;
450 static const limb_type byte_shift_mask = CHAR_BIT - 1;
452 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - 1;
453 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
455 if ((s & limb_shift_mask) == 0)
457 left_shift_limb(result, s);
459 #ifdef BOOST_MP_NO_CONSTEXPR_DETECTION
460 else if ((s & byte_shift_mask) == 0)
462 else if (((s & byte_shift_mask) == 0) && !BOOST_MP_IS_CONST_EVALUATED(s))
465 left_shift_byte(result, s);
467 #elif BOOST_ENDIAN_LITTLE_BYTE
468 #ifdef BOOST_NO_CXX14_CONSTEXPR
469 static const limb_type byte_shift_mask = CHAR_BIT - 1;
471 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
473 #ifdef BOOST_MP_NO_CONSTEXPR_DETECTION
474 if ((s & byte_shift_mask) == 0)
476 constexpr limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - 1;
477 if (BOOST_MP_IS_CONST_EVALUATED(s) && ((s & limb_shift_mask) == 0))
478 left_shift_limb(result, s);
479 else if (((s & byte_shift_mask) == 0) && !BOOST_MP_IS_CONST_EVALUATED(s))
482 left_shift_byte(result, s);
485 #ifdef BOOST_NO_CXX14_CONSTEXPR
486 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - 1;
488 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits - 1;
490 if ((s & limb_shift_mask) == 0)
492 left_shift_limb(result, s);
497 left_shift_generic(result, s);
500 // We may have shifted off the end and have leading zeros:
506 inline BOOST_MP_CXX14_CONSTEXPR void right_shift_byte(Int& result, double_limb_type s)
508 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
509 BOOST_ASSERT((s % CHAR_BIT) == 0);
510 unsigned ors = result.size();
514 result = limb_type(0);
518 typename Int::limb_pointer pr = result.limbs();
519 unsigned char* pc = reinterpret_cast<unsigned char*>(pr);
520 limb_type shift = static_cast<limb_type>(s / CHAR_BIT);
521 std::memmove(pc, pc + shift, ors * sizeof(pr[0]) - shift);
522 shift = (sizeof(limb_type) - shift % sizeof(limb_type)) * CHAR_BIT;
523 if (shift < Int::limb_bits)
525 pr[ors - offset - 1] &= (static_cast<limb_type>(1u) << shift) - 1;
526 if (!pr[ors - offset - 1] && (rs > 1))
529 result.resize(rs, rs);
533 inline BOOST_MP_CXX14_CONSTEXPR void right_shift_limb(Int& result, double_limb_type s)
535 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
536 BOOST_ASSERT((s % Int::limb_bits) == 0);
537 unsigned ors = result.size();
541 result = limb_type(0);
545 typename Int::limb_pointer pr = result.limbs();
548 pr[i] = pr[i + offset];
549 result.resize(rs, rs);
553 inline BOOST_MP_CXX14_CONSTEXPR void right_shift_generic(Int& result, double_limb_type s)
555 limb_type offset = static_cast<limb_type>(s / Int::limb_bits);
556 limb_type shift = static_cast<limb_type>(s % Int::limb_bits);
557 unsigned ors = result.size();
561 result = limb_type(0);
565 typename Int::limb_pointer pr = result.limbs();
566 if ((pr[ors - 1] >> shift) == 0)
570 result = limb_type(0);
576 // This code only works for non-zero shift, otherwise we invoke undefined behaviour!
578 for (; i + offset + 1 < ors; ++i)
580 pr[i] = pr[i + offset] >> shift;
581 pr[i] |= pr[i + offset + 1] << (Int::limb_bits - shift);
583 pr[i] = pr[i + offset] >> shift;
584 result.resize(rs, rs);
587 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
588 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value>::type
590 cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>& result,
591 double_limb_type s) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1> >::value))
593 is_valid_bitwise_op(result, typename cpp_int_backend<MinBits1, MaxBits1, unsigned_magnitude, Checked1, Allocator1>::checked_type());
597 #if BOOST_ENDIAN_LITTLE_BYTE && defined(BOOST_MP_USE_LIMB_SHIFT)
598 #ifdef BOOST_NO_CXX14_CONSTEXPR
599 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
600 static const limb_type byte_shift_mask = CHAR_BIT - 1;
602 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
603 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
605 if ((s & limb_shift_mask) == 0)
606 right_shift_limb(result, s);
607 #ifdef BOOST_MP_NO_CONSTEXPR_DETECTION
608 else if ((s & byte_shift_mask) == 0)
610 else if (((s & byte_shift_mask) == 0) && !BOOST_MP_IS_CONST_EVALUATED(s))
612 right_shift_byte(result, s);
613 #elif BOOST_ENDIAN_LITTLE_BYTE
614 #ifdef BOOST_NO_CXX14_CONSTEXPR
615 static const limb_type byte_shift_mask = CHAR_BIT - 1;
617 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
619 #ifdef BOOST_MP_NO_CONSTEXPR_DETECTION
620 if ((s & byte_shift_mask) == 0)
622 constexpr limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
623 if (BOOST_MP_IS_CONST_EVALUATED(s) && ((s & limb_shift_mask) == 0))
624 right_shift_limb(result, s);
625 else if (((s & byte_shift_mask) == 0) && !BOOST_MP_IS_CONST_EVALUATED(s))
627 right_shift_byte(result, s);
629 #ifdef BOOST_NO_CXX14_CONSTEXPR
630 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
632 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
634 if ((s & limb_shift_mask) == 0)
635 right_shift_limb(result, s);
638 right_shift_generic(result, s);
640 template <unsigned MinBits1, unsigned MaxBits1, cpp_int_check_type Checked1, class Allocator1>
641 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1> >::value>::type
643 cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>& result,
644 double_limb_type s) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1> >::value))
646 is_valid_bitwise_op(result, typename cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::checked_type());
650 bool is_neg = result.sign();
652 eval_increment(result);
654 #if BOOST_ENDIAN_LITTLE_BYTE && defined(BOOST_MP_USE_LIMB_SHIFT)
655 #ifdef BOOST_NO_CXX14_CONSTEXPR
656 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
657 static const limb_type byte_shift_mask = CHAR_BIT - 1;
659 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
660 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
662 if ((s & limb_shift_mask) == 0)
663 right_shift_limb(result, s);
664 else if ((s & byte_shift_mask) == 0)
665 right_shift_byte(result, s);
666 #elif BOOST_ENDIAN_LITTLE_BYTE
667 #ifdef BOOST_NO_CXX14_CONSTEXPR
668 static const limb_type byte_shift_mask = CHAR_BIT - 1;
670 constexpr const limb_type byte_shift_mask = CHAR_BIT - 1;
672 if ((s & byte_shift_mask) == 0)
673 right_shift_byte(result, s);
675 #ifdef BOOST_NO_CXX14_CONSTEXPR
676 static const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
678 constexpr const limb_type limb_shift_mask = cpp_int_backend<MinBits1, MaxBits1, signed_magnitude, Checked1, Allocator1>::limb_bits - 1;
680 if ((s & limb_shift_mask) == 0)
681 right_shift_limb(result, s);
684 right_shift_generic(result, s);
686 eval_decrement(result);
690 // Over again for trivial cpp_int's:
692 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class T>
693 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename enable_if<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::type
694 eval_left_shift(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, T s) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
696 is_valid_bitwise_op(result, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
697 *result.limbs() = detail::checked_left_shift(*result.limbs(), s, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
701 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class T>
702 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename enable_if<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> > >::type
703 eval_right_shift(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, T s) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
705 // Nothing to check here... just make sure we don't invoke undefined behavior:
706 is_valid_bitwise_op(result, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
707 *result.limbs() = (static_cast<unsigned>(s) >= sizeof(*result.limbs()) * CHAR_BIT) ? 0 : (result.sign() ? ((--*result.limbs()) >> s) + 1 : *result.limbs() >> s);
708 if (result.sign() && (*result.limbs() == 0))
709 result = static_cast<signed_limb_type>(-1);
712 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>
713 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
714 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)>::type
716 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
717 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
719 BOOST_STATIC_ASSERT_MSG(((Checked1 != checked) || (Checked2 != checked)), "Attempt to take the complement of a signed type results in undefined behavior.");
721 // If we're not checked then emulate 2's complement behavior:
725 *result.limbs() = *o.limbs() - 1;
730 *result.limbs() = 1 + *o.limbs();
736 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>
737 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
738 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
740 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
741 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
743 *result.limbs() = ~*o.limbs();
747 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>
748 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
749 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
751 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
752 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
754 *result.limbs() &= *o.limbs();
757 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>
758 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
759 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)>::type
761 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
762 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
764 is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
766 using default_ops::eval_bit_test;
767 using default_ops::eval_increment;
769 if (result.sign() || o.sign())
771 #ifdef BOOST_NO_CXX14_CONSTEXPR
776 const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
777 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
778 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
779 eval_bitwise_and(t1, t2);
780 bool s = eval_bit_test(t1, m + 1);
783 eval_complement(t1, t1);
791 *result.limbs() &= *o.limbs();
795 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>
796 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
797 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
799 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
800 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
802 *result.limbs() |= *o.limbs();
805 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>
806 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
807 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)>::type
809 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
810 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
812 is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
814 using default_ops::eval_bit_test;
815 using default_ops::eval_increment;
817 if (result.sign() || o.sign())
819 #ifdef BOOST_NO_CXX14_CONSTEXPR
824 const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
825 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
826 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
827 eval_bitwise_or(t1, t2);
828 bool s = eval_bit_test(t1, m + 1);
831 eval_complement(t1, t1);
839 *result.limbs() |= *o.limbs();
844 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>
845 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
846 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
848 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
849 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
851 *result.limbs() ^= *o.limbs();
854 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>
855 inline BOOST_MP_CXX14_CONSTEXPR typename enable_if_c<
856 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value)>::type
858 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
859 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
861 is_valid_bitwise_op(result, o, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
863 using default_ops::eval_bit_test;
864 using default_ops::eval_increment;
866 if (result.sign() || o.sign())
868 #ifdef BOOST_NO_CXX14_CONSTEXPR
873 const unsigned m = static_unsigned_max<static_unsigned_max<MinBits1, MinBits2>::value, static_unsigned_max<MaxBits1, MaxBits2>::value>::value;
874 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t1(result);
875 cpp_int_backend<m + 1, m + 1, unsigned_magnitude, unchecked, void> t2(o);
876 eval_bitwise_xor(t1, t2);
877 bool s = eval_bit_test(t1, m + 1);
880 eval_complement(t1, t1);
888 *result.limbs() ^= *o.limbs();
892 }}} // namespace boost::multiprecision::backends