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