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