Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/multiprecision/cpp_int.hpp @ 16:2665513ce2d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add boost headers
author Chris Cannam
date Tue, 05 Aug 2014 11:11:38 +0100
parents
children c530137014c0
comparison
equal deleted inserted replaced
15:663ca0da4350 16:2665513ce2d3
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 #ifndef BOOST_MP_CPP_INT_HPP
7 #define BOOST_MP_CPP_INT_HPP
8
9 #include <iostream>
10 #include <iomanip>
11 #include <boost/cstdint.hpp>
12 #include <boost/multiprecision/number.hpp>
13 #include <boost/multiprecision/detail/integer_ops.hpp>
14 #include <boost/array.hpp>
15 #include <boost/type_traits/is_integral.hpp>
16 #include <boost/type_traits/is_floating_point.hpp>
17 #include <boost/multiprecision/cpp_int/cpp_int_config.hpp>
18 #include <boost/multiprecision/rational_adaptor.hpp>
19 #include <boost/detail/endian.hpp>
20 #include <boost/integer/static_min_max.hpp>
21 #include <boost/type_traits/common_type.hpp>
22 #include <boost/type_traits/make_signed.hpp>
23 #include <boost/multiprecision/cpp_int/checked.hpp>
24 #ifdef BOOST_MP_USER_DEFINED_LITERALS
25 #include <boost/multiprecision/cpp_int/value_pack.hpp>
26 #endif
27
28 namespace boost{
29 namespace multiprecision{
30 namespace backends{
31
32 using boost::enable_if;
33
34
35 #ifdef BOOST_MSVC
36 // warning C4127: conditional expression is constant
37 #pragma warning(push)
38 #pragma warning(disable:4127 4351 4293 4996 4307 4702)
39 #endif
40
41 template <unsigned MinBits = 0, unsigned MaxBits = 0, cpp_integer_type SignType = signed_magnitude, cpp_int_check_type Checked = unchecked, class Allocator = typename mpl::if_c<MinBits && (MinBits == MaxBits), void, std::allocator<limb_type> >::type >
42 struct cpp_int_backend;
43
44 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, bool trivial = false>
45 struct cpp_int_base;
46 //
47 // Traits class determines the maximum and minimum precision values:
48 //
49 template <class T> struct max_precision;
50
51 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
52 struct max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
53 {
54 static const unsigned value = is_void<Allocator>::value ?
55 static_unsigned_max<MinBits, MaxBits>::value
56 : (((MaxBits >= MinBits) && MaxBits) ? MaxBits : UINT_MAX);
57 };
58
59 template <class T> struct min_precision;
60
61 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
62 struct min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
63 {
64 static const unsigned value = (is_void<Allocator>::value ? static_unsigned_max<MinBits, MaxBits>::value : MinBits);
65 };
66 //
67 // Traits class determines whether the number of bits precision requested could fit in a native type,
68 // we call this a "trivial" cpp_int:
69 //
70 template <class T>
71 struct is_trivial_cpp_int
72 {
73 static const bool value = false;
74 };
75
76 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
77 struct is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
78 {
79 typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> self;
80 static const bool value = is_void<Allocator>::value && (max_precision<self>::value <= (sizeof(double_limb_type) * CHAR_BIT) - (SignType == signed_packed ? 1 : 0));
81 };
82
83 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
84 struct is_trivial_cpp_int<cpp_int_base<MinBits, MaxBits, SignType, Checked, Allocator, true> >
85 {
86 static const bool value = true;
87 };
88
89 } // namespace backends
90 //
91 // Traits class to determine whether a cpp_int_backend is signed or not:
92 //
93 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
94 struct is_unsigned_number<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
95 : public mpl::bool_<(SignType == unsigned_magnitude) || (SignType == unsigned_packed)>{};
96
97 namespace backends{
98 //
99 // Traits class determines whether T should be implicitly convertible to U, or
100 // whether the constructor should be made explicit. The latter happens if we
101 // are losing the sign, or have fewer digits precision in the target type:
102 //
103 template <class T, class U>
104 struct is_implicit_cpp_int_conversion;
105
106 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
107 struct is_implicit_cpp_int_conversion<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >
108 {
109 typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t1;
110 typedef cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t2;
111 static const bool value =
112 (is_signed_number<t2>::value || !is_signed_number<t1>::value)
113 && (max_precision<t1>::value <= max_precision<t2>::value);
114 };
115
116 //
117 // Traits class to determine whether operations on a cpp_int may throw:
118 //
119 template <class T>
120 struct is_non_throwing_cpp_int : public mpl::false_{};
121 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType>
122 struct is_non_throwing_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, unchecked, void> > : public mpl::true_ {};
123
124 //
125 // Traits class, determines whether the cpp_int is fixed precision or not:
126 //
127 template <class T>
128 struct is_fixed_precision;
129 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
130 struct is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
131 : public mpl::bool_<max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value != UINT_MAX> {};
132
133 namespace detail{
134
135 inline void verify_new_size(unsigned new_size, unsigned min_size, const mpl::int_<checked>&)
136 {
137 if(new_size < min_size)
138 BOOST_THROW_EXCEPTION(std::overflow_error("Unable to allocate sufficient storage for the value of the result: value overflows the maximum allowable magnitude."));
139 }
140 inline void verify_new_size(unsigned /*new_size*/, unsigned /*min_size*/, const mpl::int_<unchecked>&){}
141
142 template <class U>
143 inline void verify_limb_mask(bool b, U limb, U mask, const mpl::int_<checked>&)
144 {
145 // When we mask out "limb" with "mask", do we loose bits? If so it's an overflow error:
146 if(b && (limb & ~mask))
147 BOOST_THROW_EXCEPTION(std::overflow_error("Overflow in cpp_int arithmetic: there is insufficient precision in the target type to hold all of the bits of the result."));
148 }
149 template <class U>
150 inline void verify_limb_mask(bool /*b*/, U /*limb*/, U /*mask*/, const mpl::int_<unchecked>&){}
151
152 }
153
154 //
155 // Now define the various data layouts that are possible as partial specializations of the base class,
156 // starting with the default arbitrary precision signed integer type:
157 //
158 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
159 struct cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false> : private Allocator::template rebind<limb_type>::other
160 {
161 typedef typename Allocator::template rebind<limb_type>::other allocator_type;
162 typedef typename allocator_type::pointer limb_pointer;
163 typedef typename allocator_type::const_pointer const_limb_pointer;
164 typedef mpl::int_<Checked> checked_type;
165
166 //
167 // Interface invariants:
168 //
169 BOOST_STATIC_ASSERT(!is_void<Allocator>::value);
170
171 private:
172 struct limb_data
173 {
174 unsigned capacity;
175 limb_pointer data;
176 };
177
178 public:
179 BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
180 BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
181 BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
182 BOOST_STATIC_CONSTANT(unsigned, internal_limb_count =
183 MinBits
184 ? MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0)
185 : sizeof(limb_data) / sizeof(limb_type));
186 BOOST_STATIC_CONSTANT(bool, variable = true);
187
188 private:
189 union data_type
190 {
191 limb_data ld;
192 limb_type la[internal_limb_count];
193 limb_type first;
194 double_limb_type double_first;
195
196 BOOST_CONSTEXPR data_type() : first(0) {}
197 BOOST_CONSTEXPR data_type(limb_type i) : first(i) {}
198 BOOST_CONSTEXPR data_type(signed_limb_type i) : first(i < 0 ? -i : i) {}
199 #ifdef BOOST_LITTLE_ENDIAN
200 BOOST_CONSTEXPR data_type(double_limb_type i) : double_first(i) {}
201 BOOST_CONSTEXPR data_type(signed_double_limb_type i) : double_first(i < 0 ? -i : i) {}
202 #endif
203 };
204
205 data_type m_data;
206 unsigned m_limbs;
207 bool m_sign, m_internal;
208
209 public:
210 //
211 // Direct construction:
212 //
213 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
214 : m_data(i), m_limbs(1), m_sign(false), m_internal(true) { }
215 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT
216 : m_data(i), m_limbs(1), m_sign(i < 0), m_internal(true) { }
217 #if defined(BOOST_LITTLE_ENDIAN)
218 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
219 : m_data(i), m_limbs(i > max_limb_value ? 2 : 1), m_sign(false), m_internal(true) { }
220 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT
221 : m_data(i), m_limbs(i < 0 ? (static_cast<double_limb_type>(-i) > static_cast<double_limb_type>(max_limb_value) ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
222 m_sign(i < 0), m_internal(true) { }
223 #endif
224 //
225 // Helper functions for getting at our internal data, and manipulating storage:
226 //
227 BOOST_MP_FORCEINLINE allocator_type& allocator() BOOST_NOEXCEPT { return *this; }
228 BOOST_MP_FORCEINLINE const allocator_type& allocator()const BOOST_NOEXCEPT { return *this; }
229 BOOST_MP_FORCEINLINE unsigned size()const BOOST_NOEXCEPT { return m_limbs; }
230 BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
231 BOOST_MP_FORCEINLINE const_limb_pointer limbs()const BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
232 BOOST_MP_FORCEINLINE unsigned capacity()const BOOST_NOEXCEPT { return m_internal ? internal_limb_count : m_data.ld.capacity; }
233 BOOST_MP_FORCEINLINE bool sign()const BOOST_NOEXCEPT { return m_sign; }
234 void sign(bool b) BOOST_NOEXCEPT
235 {
236 m_sign = b;
237 // Check for zero value:
238 if(m_sign && (m_limbs == 1))
239 {
240 if(limbs()[0] == 0)
241 m_sign = false;
242 }
243 }
244 void resize(unsigned new_size, unsigned min_size)
245 {
246 static const unsigned max_limbs = MaxBits / (CHAR_BIT * sizeof(limb_type)) + (MaxBits % (CHAR_BIT * sizeof(limb_type)) ? 1 : 0);
247 // We never resize beyond MaxSize:
248 if(new_size > max_limbs)
249 new_size = max_limbs;
250 detail::verify_new_size(new_size, min_size, checked_type());
251 // See if we have enough capacity already:
252 unsigned cap = capacity();
253 if(new_size > cap)
254 {
255 // Allocate a new buffer and copy everything over:
256 cap = (std::min)((std::max)(cap * 4, new_size), max_limbs);
257 limb_pointer pl = allocator().allocate(cap);
258 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
259 std::copy(limbs(), limbs() + size(), stdext::checked_array_iterator<limb_pointer>(pl, cap));
260 #else
261 std::copy(limbs(), limbs() + size(), pl);
262 #endif
263 if(!m_internal)
264 allocator().deallocate(limbs(), capacity());
265 else
266 m_internal = false;
267 m_limbs = new_size;
268 m_data.ld.capacity = cap;
269 m_data.ld.data = pl;
270 }
271 else
272 {
273 m_limbs = new_size;
274 }
275 }
276 BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT
277 {
278 limb_pointer p = limbs();
279 while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
280 }
281 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_data(), m_limbs(1), m_sign(false), m_internal(true) {}
282 BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) : allocator_type(o), m_limbs(0), m_internal(true)
283 {
284 resize(o.size(), o.size());
285 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
286 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
287 #else
288 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
289 #endif
290 m_sign = o.m_sign;
291 }
292 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
293 cpp_int_base(cpp_int_base&& o)
294 : allocator_type(static_cast<Allocator&&>(o)), m_limbs(o.m_limbs), m_sign(o.m_sign), m_internal(o.m_internal)
295 {
296 if(m_internal)
297 {
298 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
299 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
300 #else
301 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
302 #endif
303 }
304 else
305 {
306 m_data.ld = o.m_data.ld;
307 o.m_limbs = 0;
308 o.m_internal = true;
309 }
310 }
311 cpp_int_base& operator = (cpp_int_base&& o) BOOST_NOEXCEPT
312 {
313 if(!m_internal)
314 allocator().deallocate(m_data.ld.data, m_data.ld.capacity);
315 *static_cast<Allocator*>(this) = static_cast<Allocator&&>(o);
316 m_limbs = o.m_limbs;
317 m_sign = o.m_sign;
318 m_internal = o.m_internal;
319 if(m_internal)
320 {
321 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
322 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
323 #else
324 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
325 #endif
326 }
327 else
328 {
329 m_data.ld = o.m_data.ld;
330 o.m_limbs = 0;
331 o.m_internal = true;
332 }
333 return *this;
334 }
335 #endif
336 BOOST_MP_FORCEINLINE ~cpp_int_base() BOOST_NOEXCEPT
337 {
338 if(!m_internal)
339 allocator().deallocate(limbs(), capacity());
340 }
341 void assign(const cpp_int_base& o)
342 {
343 if(this != &o)
344 {
345 static_cast<allocator_type&>(*this) = static_cast<const allocator_type&>(o);
346 m_limbs = 0;
347 resize(o.size(), o.size());
348 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
349 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
350 #else
351 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
352 #endif
353 m_sign = o.m_sign;
354 }
355 }
356 BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
357 {
358 m_sign = !m_sign;
359 // Check for zero value:
360 if(m_sign && (m_limbs == 1))
361 {
362 if(limbs()[0] == 0)
363 m_sign = false;
364 }
365 }
366 BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
367 {
368 return m_sign;
369 }
370 BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
371 {
372 std::swap(m_data, o.m_data);
373 std::swap(m_sign, o.m_sign);
374 std::swap(m_internal, o.m_internal);
375 std::swap(m_limbs, o.m_limbs);
376 }
377 };
378
379 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
380
381 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
382 const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::limb_bits;
383 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
384 const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::max_limb_value;
385 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
386 const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::sign_bit_mask;
387 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
388 const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::internal_limb_count;
389 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
390 const bool cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::variable;
391
392 #endif
393
394 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
395 struct cpp_int_base<MinBits, MaxBits, unsigned_magnitude, Checked, Allocator, false> : private Allocator::template rebind<limb_type>::other
396 {
397 //
398 // There is currently no support for unsigned arbitrary precision arithmetic, largely
399 // because it's not clear what subtraction should do:
400 //
401 BOOST_STATIC_ASSERT_MSG(((sizeof(Allocator) == 0) && !is_void<Allocator>::value), "There is curently no support for unsigned arbitrary precision integers.");
402 };
403 //
404 // Fixed precision (i.e. no allocator), signed-magnitude type with limb-usage count:
405 //
406 template <unsigned MinBits, cpp_int_check_type Checked>
407 struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>
408 {
409 typedef limb_type* limb_pointer;
410 typedef const limb_type* const_limb_pointer;
411 typedef mpl::int_<Checked> checked_type;
412
413 //
414 // Interface invariants:
415 //
416 BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
417
418 public:
419 BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
420 BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
421 BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
422 BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0));
423 BOOST_STATIC_CONSTANT(bool, variable = false);
424 BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = MinBits % limb_bits ? (limb_type(1) << (MinBits % limb_bits)) -1 : (~limb_type(0)));
425 BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
426
427 private:
428 union data_type{
429 limb_type m_data[internal_limb_count];
430 limb_type m_first_limb;
431 double_limb_type m_double_first_limb;
432
433 BOOST_CONSTEXPR data_type() : m_first_limb(0) {}
434 BOOST_CONSTEXPR data_type(limb_type i) : m_first_limb(i) {}
435 BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i) {}
436 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
437 template <limb_type...VALUES>
438 BOOST_CONSTEXPR data_type(literals::detail::value_pack<VALUES...>) : m_data{ VALUES... } {}
439 #endif
440 } m_wrapper;
441 boost::uint16_t m_limbs;
442 bool m_sign;
443
444 public:
445 //
446 // Direct construction:
447 //
448 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
449 : m_wrapper(i), m_limbs(1), m_sign(false) {}
450 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT
451 : m_wrapper(limb_type(i < 0 ? -i : i)), m_limbs(1), m_sign(i < 0) {}
452 #if defined(BOOST_LITTLE_ENDIAN)
453 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
454 : m_wrapper(i), m_limbs(i > max_limb_value ? 2 : 1), m_sign(false) {}
455 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT
456 : m_wrapper(double_limb_type(i < 0 ? -i : i)),
457 m_limbs(i < 0 ? (static_cast<double_limb_type>(-i) > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
458 m_sign(i < 0) {}
459 #endif
460 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
461 template <limb_type...VALUES>
462 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<VALUES...> i)
463 : m_wrapper(i), m_limbs(sizeof...(VALUES)), m_sign(false) {}
464 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<> i)
465 : m_wrapper(i), m_limbs(1), m_sign(false) {}
466 BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&)
467 : m_wrapper(a.m_wrapper), m_limbs(a.m_limbs), m_sign((a.m_limbs == 1) && (*a.limbs() == 0) ? false : !a.m_sign) {}
468 #endif
469 //
470 // Helper functions for getting at our internal data, and manipulating storage:
471 //
472 BOOST_MP_FORCEINLINE unsigned size()const BOOST_NOEXCEPT { return m_limbs; }
473 BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
474 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs()const BOOST_NOEXCEPT { return m_wrapper.m_data; }
475 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign()const BOOST_NOEXCEPT { return m_sign; }
476 BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT
477 {
478 m_sign = b;
479 // Check for zero value:
480 if(m_sign && (m_limbs == 1))
481 {
482 if(limbs()[0] == 0)
483 m_sign = false;
484 }
485 }
486 BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size) BOOST_NOEXCEPT_IF((Checked == unchecked))
487 {
488 m_limbs = static_cast<boost::uint16_t>((std::min)(new_size, internal_limb_count));
489 detail::verify_new_size(m_limbs, min_size, checked_type());
490 }
491 BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
492 {
493 limb_pointer p = limbs();
494 detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count-1], upper_limb_mask, checked_type());
495 p[internal_limb_count-1] &= upper_limb_mask;
496 while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
497 if((m_limbs == 1) && (!*p)) m_sign = false; // zero is always unsigned
498 }
499
500 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_wrapper(limb_type(0u)), m_limbs(1), m_sign(false) {}
501 // Defaulted functions:
502 //BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& i)BOOST_NOEXCEPT;
503 //~cpp_int_base() BOOST_NOEXCEPT {}
504
505 void assign(const cpp_int_base& o) BOOST_NOEXCEPT
506 {
507 if(this != &o)
508 {
509 resize(o.size(), o.size());
510 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
511 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
512 #else
513 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
514 #endif
515 m_sign = o.m_sign;
516 }
517 }
518 BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
519 {
520 m_sign = !m_sign;
521 // Check for zero value:
522 if(m_sign && (m_limbs == 1))
523 {
524 if(limbs()[0] == 0)
525 m_sign = false;
526 }
527 }
528 BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
529 {
530 return m_sign;
531 }
532 BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
533 {
534 for(unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
535 std::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
536 std::swap(m_sign, o.m_sign);
537 std::swap(m_limbs, o.m_limbs);
538 }
539 };
540 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
541
542 template <unsigned MinBits, cpp_int_check_type Checked>
543 const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::limb_bits;
544 template <unsigned MinBits, cpp_int_check_type Checked>
545 const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::max_limb_value;
546 template <unsigned MinBits, cpp_int_check_type Checked>
547 const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::sign_bit_mask;
548 template <unsigned MinBits, cpp_int_check_type Checked>
549 const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::internal_limb_count;
550 template <unsigned MinBits, cpp_int_check_type Checked>
551 const bool cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::variable;
552
553 #endif
554 //
555 // Fixed precision (i.e. no allocator), unsigned type with limb-usage count:
556 //
557 template <unsigned MinBits, cpp_int_check_type Checked>
558 struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>
559 {
560 typedef limb_type* limb_pointer;
561 typedef const limb_type* const_limb_pointer;
562 typedef mpl::int_<Checked> checked_type;
563
564 //
565 // Interface invariants:
566 //
567 BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
568
569 public:
570 BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
571 BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
572 BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
573 BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0));
574 BOOST_STATIC_CONSTANT(bool, variable = false);
575 BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = MinBits % limb_bits ? (limb_type(1) << (MinBits % limb_bits)) -1 : (~limb_type(0)));
576 BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
577
578 private:
579 union data_type{
580 limb_type m_data[internal_limb_count];
581 limb_type m_first_limb;
582 double_limb_type m_double_first_limb;
583
584 BOOST_CONSTEXPR data_type() : m_first_limb(0) {}
585 BOOST_CONSTEXPR data_type(limb_type i) : m_first_limb(i) {}
586 BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i) {}
587 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
588 template <limb_type...VALUES>
589 BOOST_CONSTEXPR data_type(literals::detail::value_pack<VALUES...>) : m_data{ VALUES... } {}
590 #endif
591 } m_wrapper;
592 limb_type m_limbs;
593
594 public:
595 //
596 // Direct construction:
597 //
598 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
599 : m_wrapper(i), m_limbs(1) {}
600 BOOST_MP_FORCEINLINE cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT_IF((Checked == unchecked))
601 : m_wrapper(limb_type(i < 0 ? -i : i)), m_limbs(1) { if(i < 0) negate(); }
602 #ifdef BOOST_LITTLE_ENDIAN
603 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
604 : m_wrapper(i), m_limbs(i > max_limb_value ? 2 : 1) {}
605 BOOST_MP_FORCEINLINE cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT_IF((Checked == unchecked))
606 : m_wrapper(double_limb_type(i < 0 ? -i : i)), m_limbs(i < 0 ? (-i > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)) { if(i < 0) negate(); }
607 #endif
608 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
609 template <limb_type...VALUES>
610 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<VALUES...> i)
611 : m_wrapper(i), m_limbs(sizeof...(VALUES)) {}
612 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>)
613 : m_wrapper(static_cast<limb_type>(0u)), m_limbs(1) {}
614 #endif
615 //
616 // Helper functions for getting at our internal data, and manipulating storage:
617 //
618 BOOST_MP_FORCEINLINE unsigned size()const BOOST_NOEXCEPT { return m_limbs; }
619 BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
620 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs()const BOOST_NOEXCEPT { return m_wrapper.m_data; }
621 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign()const BOOST_NOEXCEPT { return false; }
622 BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT_IF((Checked == unchecked)) { if(b) negate(); }
623 BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size) BOOST_NOEXCEPT_IF((Checked == unchecked))
624 {
625 m_limbs = (std::min)(new_size, internal_limb_count);
626 detail::verify_new_size(m_limbs, min_size, checked_type());
627 }
628 BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
629 {
630 limb_pointer p = limbs();
631 detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count-1], upper_limb_mask, checked_type());
632 p[internal_limb_count-1] &= upper_limb_mask;
633 while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
634 }
635
636 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT
637 : m_wrapper(limb_type(0u)), m_limbs(1) {}
638 // Defaulted functions:
639 //BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT;
640 //~cpp_int_base() BOOST_NOEXCEPT {}
641
642 BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
643 {
644 if(this != &o)
645 {
646 resize(o.size(), o.size());
647 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
648 std::copy(o.limbs(), o.limbs() + o.size(), stdext::checked_array_iterator<limb_pointer>(limbs(), size()));
649 #else
650 std::copy(o.limbs(), o.limbs() + o.size(), limbs());
651 #endif
652 }
653 }
654 private:
655 void check_negate(const mpl::int_<checked>&)
656 {
657 BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned number."));
658 }
659 void check_negate(const mpl::int_<unchecked>&){}
660 public:
661 void negate() BOOST_NOEXCEPT_IF((Checked == unchecked))
662 {
663 // Not so much a negate as a complement - this gets called when subtraction
664 // would result in a "negative" number:
665 unsigned i;
666 if((m_limbs == 1) && (m_wrapper.m_data[0] == 0))
667 return; // negating zero is always zero, and always OK.
668 check_negate(checked_type());
669 for(i = m_limbs; i < internal_limb_count; ++i)
670 m_wrapper.m_data[i] = 0;
671 m_limbs = internal_limb_count;
672 for(i = 0; i < internal_limb_count; ++i)
673 m_wrapper.m_data[i] = ~m_wrapper.m_data[i];
674 normalize();
675 eval_increment(static_cast<cpp_int_backend<MinBits, MinBits, unsigned_magnitude, Checked, void>& >(*this));
676 }
677 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg()const BOOST_NOEXCEPT
678 {
679 return false;
680 }
681 BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
682 {
683 for(unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
684 std::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
685 std::swap(m_limbs, o.m_limbs);
686 }
687 };
688 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
689
690 template <unsigned MinBits, cpp_int_check_type Checked>
691 const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::limb_bits;
692 template <unsigned MinBits, cpp_int_check_type Checked>
693 const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::max_limb_value;
694 template <unsigned MinBits, cpp_int_check_type Checked>
695 const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::sign_bit_mask;
696 template <unsigned MinBits, cpp_int_check_type Checked>
697 const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::internal_limb_count;
698 template <unsigned MinBits, cpp_int_check_type Checked>
699 const bool cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::variable;
700
701 #endif
702 //
703 // Traits classes to figure out a native type with N bits, these vary from boost::uint_t<N> only
704 // because some platforms have native integer types longer than long long, "really long long" anyone??
705 //
706 template <unsigned N, bool s>
707 struct trivial_limb_type_imp
708 {
709 typedef double_limb_type type;
710 };
711
712 template <unsigned N>
713 struct trivial_limb_type_imp<N, true>
714 {
715 typedef typename boost::uint_t<N>::least type;
716 };
717
718 template <unsigned N>
719 struct trivial_limb_type : public trivial_limb_type_imp<N, N <= sizeof(long long) * CHAR_BIT> {};
720 //
721 // Backend for fixed precision signed-magnitude type which will fit entirely inside a "double_limb_type":
722 //
723 template <unsigned MinBits, cpp_int_check_type Checked>
724 struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, true>
725 {
726 typedef typename trivial_limb_type<MinBits>::type local_limb_type;
727 typedef local_limb_type* limb_pointer;
728 typedef const local_limb_type* const_limb_pointer;
729 typedef mpl::int_<Checked> checked_type;
730 protected:
731 BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
732 BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = (MinBits < limb_bits) ? local_limb_type((local_limb_type(~local_limb_type(0))) >> (limb_bits - MinBits)) : local_limb_type(~local_limb_type(0)));
733 private:
734 local_limb_type m_data;
735 bool m_sign;
736
737 //
738 // Interface invariants:
739 //
740 BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
741 protected:
742 template <class T>
743 typename boost::disable_if_c<std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits)>::type
744 check_in_range(T val, const mpl::int_<checked>&)
745 {
746 BOOST_MP_USING_ABS
747 typedef typename common_type<T, local_limb_type>::type common_type;
748
749 if(static_cast<common_type>(abs(val)) > static_cast<common_type>(limb_mask))
750 BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
751 }
752 template <class T, int C>
753 void check_in_range(T, const mpl::int_<C>&){}
754
755 template <class T>
756 void check_in_range(T val)
757 {
758 check_in_range(val, checked_type());
759 }
760
761 public:
762 //
763 // Direct construction:
764 //
765 template <class SI>
766 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
767 : m_data(i < 0 ? static_cast<local_limb_type>(static_cast<typename make_unsigned<SI>::type>(-i)) & limb_mask : static_cast<local_limb_type>(i) & limb_mask), m_sign(i < 0) {}
768 template <class SI>
769 BOOST_MP_FORCEINLINE cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
770 : m_data(i < 0 ? static_cast<local_limb_type>(static_cast<typename make_unsigned<SI>::type>(-i) & limb_mask) : static_cast<local_limb_type>(i) & limb_mask), m_sign(i < 0) { check_in_range(i); }
771 template <class UI>
772 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
773 : m_data(static_cast<local_limb_type>(i) & limb_mask), m_sign(false) {}
774 template <class UI>
775 BOOST_MP_FORCEINLINE cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == checked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
776 : m_data(static_cast<local_limb_type>(i) & limb_mask), m_sign(false) { check_in_range(i); }
777 template <class F>
778 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(F i, typename boost::enable_if_c<is_floating_point<F>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
779 : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask), m_sign(i < 0) {}
780 template <class F>
781 BOOST_MP_FORCEINLINE cpp_int_base(F i, typename boost::enable_if_c<is_floating_point<F>::value && (Checked == checked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
782 : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask), m_sign(i < 0) { check_in_range(i); }
783 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
784 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>)
785 : m_data(static_cast<local_limb_type>(0u)), m_sign(false) {}
786 template <limb_type a>
787 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a>)
788 : m_data(static_cast<local_limb_type>(a)), m_sign(false) {}
789 template <limb_type a, limb_type b>
790 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a, b>)
791 : m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)), m_sign(false) {}
792 BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&)
793 : m_data(a.m_data), m_sign(a.m_data ? !a.m_sign : false) {}
794 #endif
795 //
796 // Helper functions for getting at our internal data, and manipulating storage:
797 //
798 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size()const BOOST_NOEXCEPT { return 1; }
799 BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
800 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs()const BOOST_NOEXCEPT { return &m_data; }
801 BOOST_MP_FORCEINLINE bool sign()const BOOST_NOEXCEPT { return m_sign; }
802 BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT
803 {
804 m_sign = b;
805 // Check for zero value:
806 if(m_sign && !m_data)
807 {
808 m_sign = false;
809 }
810 }
811 BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size)
812 {
813 detail::verify_new_size(2, min_size, checked_type());
814 }
815 BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
816 {
817 if(!m_data)
818 m_sign = false; // zero is always unsigned
819 detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
820 m_data &= limb_mask;
821 }
822
823 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_data(0), m_sign(false) {}
824 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
825 : m_data(o.m_data), m_sign(o.m_sign) {}
826 //~cpp_int_base() BOOST_NOEXCEPT {}
827 BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
828 {
829 m_data = o.m_data;
830 m_sign = o.m_sign;
831 }
832 BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
833 {
834 m_sign = !m_sign;
835 // Check for zero value:
836 if(m_data == 0)
837 {
838 m_sign = false;
839 }
840 }
841 BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
842 {
843 return m_sign;
844 }
845 BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
846 {
847 std::swap(m_sign, o.m_sign);
848 std::swap(m_data, o.m_data);
849 }
850 };
851 //
852 // Backend for unsigned fixed precision (i.e. no allocator) type which will fit entirely inside a "double_limb_type":
853 //
854 template <unsigned MinBits, cpp_int_check_type Checked>
855 struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, true>
856 {
857 typedef typename trivial_limb_type<MinBits>::type local_limb_type;
858 typedef local_limb_type* limb_pointer;
859 typedef const local_limb_type* const_limb_pointer;
860 private:
861 BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
862 BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = limb_bits != MinBits ?
863 static_cast<local_limb_type>(static_cast<local_limb_type>(~local_limb_type(0)) >> (limb_bits - MinBits))
864 : static_cast<local_limb_type>(~local_limb_type(0)));
865
866 local_limb_type m_data;
867
868 typedef mpl::int_<Checked> checked_type;
869
870 //
871 // Interface invariants:
872 //
873 BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
874 protected:
875 template <class T>
876 typename boost::disable_if_c<std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits)>::type
877 check_in_range(T val, const mpl::int_<checked>&, const mpl::false_&)
878 {
879 typedef typename common_type<T, local_limb_type>::type common_type;
880
881 if(static_cast<common_type>(val) > limb_mask)
882 BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
883 }
884 template <class T>
885 void check_in_range(T val, const mpl::int_<checked>&, const mpl::true_&)
886 {
887 typedef typename common_type<T, local_limb_type>::type common_type;
888
889 if(static_cast<common_type>(val) > limb_mask)
890 BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
891 if(val < 0)
892 BOOST_THROW_EXCEPTION(std::range_error("The argument to an unsigned cpp_int constructor was negative."));
893 }
894 template <class T, int C, bool B>
895 BOOST_MP_FORCEINLINE void check_in_range(T, const mpl::int_<C>&, const mpl::bool_<B>&){}
896
897 template <class T>
898 BOOST_MP_FORCEINLINE void check_in_range(T val)
899 {
900 check_in_range(val, checked_type(), is_signed<T>());
901 }
902
903 public:
904 //
905 // Direct construction:
906 //
907 template <class SI>
908 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
909 : m_data(i < 0 ? (1 + ~static_cast<local_limb_type>(-i)) & limb_mask : static_cast<local_limb_type>(i) & limb_mask) {}
910 template <class SI>
911 BOOST_MP_FORCEINLINE cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
912 : m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)) { check_in_range(i); }
913 template <class UI>
914 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
915 : m_data(static_cast<local_limb_type>(i) & limb_mask) {}
916 template <class UI>
917 BOOST_MP_FORCEINLINE cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
918 : m_data(static_cast<local_limb_type>(i)) { check_in_range(i); }
919 template <class F>
920 BOOST_MP_FORCEINLINE cpp_int_base(F i, typename boost::enable_if<is_floating_point<F> >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
921 : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask)
922 {
923 check_in_range(i);
924 if(i < 0)
925 negate();
926 }
927 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
928 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>)
929 : m_data(static_cast<local_limb_type>(0u)) {}
930 template <limb_type a>
931 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a>)
932 : m_data(static_cast<local_limb_type>(a)) {}
933 template <limb_type a, limb_type b>
934 BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a, b>)
935 : m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)) {}
936 #endif
937 //
938 // Helper functions for getting at our internal data, and manipulating storage:
939 //
940 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size()const BOOST_NOEXCEPT { return 1; }
941 BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
942 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs()const BOOST_NOEXCEPT { return &m_data; }
943 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign()const BOOST_NOEXCEPT { return false; }
944 BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT_IF((Checked == unchecked))
945 {
946 if(b)
947 negate();
948 }
949 BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size)
950 {
951 detail::verify_new_size(2, min_size, checked_type());
952 }
953 BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
954 {
955 detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
956 m_data &= limb_mask;
957 }
958
959 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_data(0) {}
960 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
961 : m_data(o.m_data) {}
962 //~cpp_int_base() BOOST_NOEXCEPT {}
963 BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
964 {
965 m_data = o.m_data;
966 }
967 BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT_IF((Checked == unchecked))
968 {
969 if(Checked == checked)
970 {
971 BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned type."));
972 }
973 m_data = ~m_data;
974 ++m_data;
975 }
976 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg()const BOOST_NOEXCEPT
977 {
978 return false;
979 }
980 BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
981 {
982 std::swap(m_data, o.m_data);
983 }
984 };
985 //
986 // Traits class, lets us know whether type T can be directly converted to the base type,
987 // used to enable/disable constructors etc:
988 //
989 template <class Arg, class Base>
990 struct is_allowed_cpp_int_base_conversion : public mpl::if_c<
991 is_same<Arg, limb_type>::value || is_same<Arg, signed_limb_type>::value
992 #ifdef BOOST_LITTLE_ENDIAN
993 || is_same<Arg, double_limb_type>::value || is_same<Arg, signed_double_limb_type>::value
994 #endif
995 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
996 || literals::detail::is_value_pack<Arg>::value
997 #endif
998 || (is_trivial_cpp_int<Base>::value && is_arithmetic<Arg>::value),
999 mpl::true_,
1000 mpl::false_
1001 >::type
1002 {};
1003 //
1004 // Now the actual backend, normalising parameters passed to the base class:
1005 //
1006 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
1007 struct cpp_int_backend
1008 : public cpp_int_base<
1009 min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1010 max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1011 SignType,
1012 Checked,
1013 Allocator,
1014 is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>
1015 {
1016 typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> self_type;
1017 typedef cpp_int_base<
1018 min_precision<self_type>::value,
1019 max_precision<self_type>::value,
1020 SignType,
1021 Checked,
1022 Allocator,
1023 is_trivial_cpp_int<self_type>::value> base_type;
1024 typedef mpl::bool_<is_trivial_cpp_int<self_type>::value> trivial_tag;
1025 public:
1026 typedef typename mpl::if_<
1027 trivial_tag,
1028 mpl::list<
1029 signed char, short, int, long,
1030 long long, signed_double_limb_type>,
1031 mpl::list<signed_limb_type, signed_double_limb_type>
1032 >::type signed_types;
1033 typedef typename mpl::if_<
1034 trivial_tag,
1035 mpl::list<unsigned char, unsigned short, unsigned,
1036 unsigned long long, double_limb_type>,
1037 mpl::list<limb_type, double_limb_type>
1038 >::type unsigned_types;
1039 typedef typename mpl::if_<
1040 trivial_tag,
1041 mpl::list<float, double, long double>,
1042 mpl::list<long double>
1043 >::type float_types;
1044 typedef mpl::int_<Checked> checked_type;
1045
1046 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend() BOOST_NOEXCEPT{}
1047 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(const cpp_int_backend& o) BOOST_NOEXCEPT_IF(boost::is_void<Allocator>::value) : base_type(o) {}
1048 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1049 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(cpp_int_backend&& o) BOOST_NOEXCEPT
1050 : base_type(static_cast<base_type&&>(o)) {}
1051 #endif
1052 //
1053 // Direct construction from arithmetic type:
1054 //
1055 template <class Arg>
1056 BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(Arg i, typename boost::enable_if_c<is_allowed_cpp_int_base_conversion<Arg, base_type>::value >::type const* = 0)BOOST_NOEXCEPT_IF((Checked == unchecked) && boost::is_void<Allocator>::value)
1057 : base_type(i) {}
1058
1059 private:
1060 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1061 void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::true_ const &)
1062 {
1063 // Assigning trivial type to trivial type:
1064 this->check_in_range(*other.limbs());
1065 *this->limbs() = static_cast<typename self_type::local_limb_type>(*other.limbs());
1066 this->sign(other.sign());
1067 this->normalize();
1068 }
1069 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1070 void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::false_ const &)
1071 {
1072 // non-trivial to trivial narrowing conversion:
1073 double_limb_type v = *other.limbs();
1074 if(other.size() > 1)
1075 {
1076 v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
1077 if((Checked == checked) && (other.size() > 2))
1078 {
1079 BOOST_THROW_EXCEPTION(std::range_error("Assignment of a cpp_int that is out of range for the target type."));
1080 }
1081 }
1082 *this = v;
1083 this->sign(other.sign());
1084 this->normalize();
1085 }
1086 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1087 void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::true_ const &)
1088 {
1089 // trivial to non-trivial, treat the trivial argument as if it were an unsigned arithmetic type, then set the sign afterwards:
1090 *this = static_cast<
1091 typename boost::multiprecision::detail::canonical<
1092 typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type,
1093 cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>
1094 >::type
1095 >(*other.limbs());
1096 this->sign(other.sign());
1097 }
1098 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1099 void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::false_ const &)
1100 {
1101 // regular non-trivial to non-trivial assign:
1102 this->resize(other.size(), other.size());
1103 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1600)
1104 std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), stdext::checked_array_iterator<limb_pointer>(this->limbs(), this->size()));
1105 #else
1106 std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), this->limbs());
1107 #endif
1108 this->sign(other.sign());
1109 this->normalize();
1110 }
1111 public:
1112 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1113 cpp_int_backend(
1114 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1115 typename boost::enable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
1116 : base_type()
1117 {
1118 do_assign(
1119 other,
1120 mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1121 mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1122 }
1123 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1124 explicit cpp_int_backend(
1125 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1126 typename boost::disable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
1127 : base_type()
1128 {
1129 do_assign(
1130 other,
1131 mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1132 mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1133 }
1134 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1135 cpp_int_backend& operator=(
1136 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other)
1137 {
1138 do_assign(
1139 other,
1140 mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1141 mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1142 return *this;
1143 }
1144 #ifdef BOOST_MP_USER_DEFINED_LITERALS
1145 BOOST_CONSTEXPR cpp_int_backend(const cpp_int_backend& a, const literals::detail::negate_tag& tag)
1146 : base_type(static_cast<const base_type&>(a), tag){}
1147 #endif
1148
1149 BOOST_MP_FORCEINLINE cpp_int_backend& operator = (const cpp_int_backend& o) BOOST_NOEXCEPT_IF((Checked == unchecked) && boost::is_void<Allocator>::value)
1150 {
1151 this->assign(o);
1152 return *this;
1153 }
1154 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1155 BOOST_MP_FORCEINLINE cpp_int_backend& operator = (cpp_int_backend&& o) BOOST_NOEXCEPT_IF(boost::is_void<Allocator>::value)
1156 {
1157 *static_cast<base_type*>(this) = static_cast<base_type&&>(o);
1158 return *this;
1159 }
1160 #endif
1161 private:
1162 template <class A>
1163 typename boost::enable_if<is_unsigned<A> >::type do_assign_arithmetic(A val, const mpl::true_&)
1164 {
1165 this->check_in_range(val);
1166 *this->limbs() = static_cast<typename self_type::local_limb_type>(val);
1167 this->normalize();
1168 }
1169 template <class A>
1170 typename boost::disable_if<is_unsigned<A> >::type do_assign_arithmetic(A val, const mpl::true_&)
1171 {
1172 typedef typename make_signed<typename self_type::local_limb_type>::type signed_limb_type;
1173 this->check_in_range(val);
1174 *this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(-static_cast<signed_limb_type>(val)) : static_cast<typename self_type::local_limb_type>(val);
1175 this->sign(val < 0);
1176 this->normalize();
1177 }
1178 BOOST_MP_FORCEINLINE void do_assign_arithmetic(limb_type i, const mpl::false_&) BOOST_NOEXCEPT
1179 {
1180 this->resize(1, 1);
1181 *this->limbs() = i;
1182 this->sign(false);
1183 }
1184 BOOST_MP_FORCEINLINE void do_assign_arithmetic(signed_limb_type i, const mpl::false_&) BOOST_NOEXCEPT_IF((Checked == unchecked))
1185 {
1186 this->resize(1, 1);
1187 *this->limbs() = static_cast<limb_type>(std::abs(i));
1188 this->sign(i < 0);
1189 }
1190 void do_assign_arithmetic(double_limb_type i, const mpl::false_&)
1191 {
1192 BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
1193 BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
1194 typename base_type::limb_pointer p = this->limbs();
1195 *p = static_cast<limb_type>(i);
1196 p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
1197 this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1198 this->sign(false);
1199 }
1200 void do_assign_arithmetic(signed_double_limb_type i, const mpl::false_&)
1201 {
1202 BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
1203 BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
1204 bool s = false;
1205 if(i < 0)
1206 {
1207 s = true;
1208 i = -i;
1209 }
1210 else
1211 this->sign(false);
1212 typename base_type::limb_pointer p = this->limbs();
1213 *p = static_cast<limb_type>(i);
1214 p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
1215 this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1216 this->sign(s);
1217 }
1218
1219 void do_assign_arithmetic(long double a, const mpl::false_&)
1220 {
1221 using default_ops::eval_add;
1222 using default_ops::eval_subtract;
1223 using std::frexp;
1224 using std::ldexp;
1225 using std::floor;
1226
1227 if (a == 0) {
1228 *this = static_cast<limb_type>(0u);
1229 }
1230
1231 if (a == 1) {
1232 *this = static_cast<limb_type>(1u);
1233 }
1234
1235 BOOST_ASSERT(!(boost::math::isinf)(a));
1236 BOOST_ASSERT(!(boost::math::isnan)(a));
1237
1238 int e;
1239 long double f, term;
1240 *this = static_cast<limb_type>(0u);
1241
1242 f = frexp(a, &e);
1243
1244 static const limb_type shift = std::numeric_limits<limb_type>::digits;
1245
1246 while(f)
1247 {
1248 // extract int sized bits from f:
1249 f = ldexp(f, shift);
1250 term = floor(f);
1251 e -= shift;
1252 eval_left_shift(*this, shift);
1253 if(term > 0)
1254 eval_add(*this, static_cast<limb_type>(term));
1255 else
1256 eval_subtract(*this, static_cast<limb_type>(-term));
1257 f -= term;
1258 }
1259 if(e > 0)
1260 eval_left_shift(*this, e);
1261 else if(e < 0)
1262 eval_right_shift(*this, -e);
1263 }
1264 public:
1265 template <class Arithmetic>
1266 BOOST_MP_FORCEINLINE cpp_int_backend& operator = (Arithmetic val)
1267 {
1268 do_assign_arithmetic(val, trivial_tag());
1269 return *this;
1270 }
1271 private:
1272 void do_assign_string(const char* s, const mpl::true_&)
1273 {
1274 std::size_t n = s ? std::strlen(s) : 0;
1275 *this->limbs() = 0;
1276 unsigned radix = 10;
1277 bool isneg = false;
1278 if(n && (*s == '-'))
1279 {
1280 --n;
1281 ++s;
1282 isneg = true;
1283 }
1284 if(n && (*s == '0'))
1285 {
1286 if((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1287 {
1288 radix = 16;
1289 s +=2;
1290 n -= 2;
1291 }
1292 else
1293 {
1294 radix = 8;
1295 n -= 1;
1296 }
1297 }
1298 if(n)
1299 {
1300 unsigned val;
1301 while(*s)
1302 {
1303 if(*s >= '0' && *s <= '9')
1304 val = *s - '0';
1305 else if(*s >= 'a' && *s <= 'f')
1306 val = 10 + *s - 'a';
1307 else if(*s >= 'A' && *s <= 'F')
1308 val = 10 + *s - 'A';
1309 else
1310 val = radix + 1;
1311 if(val >= radix)
1312 {
1313 BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1314 }
1315 *this->limbs() = detail::checked_multiply(*this->limbs(), static_cast<typename base_type::local_limb_type>(radix), checked_type());
1316 *this->limbs() = detail::checked_add(*this->limbs(), static_cast<typename base_type::local_limb_type>(val), checked_type());
1317 ++s;
1318 }
1319 }
1320 if(isneg)
1321 this->negate();
1322 }
1323 void do_assign_string(const char* s, const mpl::false_&)
1324 {
1325 using default_ops::eval_multiply;
1326 using default_ops::eval_add;
1327 std::size_t n = s ? std::strlen(s) : 0;
1328 *this = static_cast<limb_type>(0u);
1329 unsigned radix = 10;
1330 bool isneg = false;
1331 if(n && (*s == '-'))
1332 {
1333 --n;
1334 ++s;
1335 isneg = true;
1336 }
1337 if(n && (*s == '0'))
1338 {
1339 if((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1340 {
1341 radix = 16;
1342 s +=2;
1343 n -= 2;
1344 }
1345 else
1346 {
1347 radix = 8;
1348 n -= 1;
1349 }
1350 }
1351 if(n)
1352 {
1353 if(radix == 8 || radix == 16)
1354 {
1355 unsigned shift = radix == 8 ? 3 : 4;
1356 unsigned block_count = base_type::limb_bits / shift;
1357 unsigned block_shift = shift * block_count;
1358 limb_type val, block;
1359 while(*s)
1360 {
1361 block = 0;
1362 for(unsigned i = 0; (i < block_count); ++i)
1363 {
1364 if(*s >= '0' && *s <= '9')
1365 val = *s - '0';
1366 else if(*s >= 'a' && *s <= 'f')
1367 val = 10 + *s - 'a';
1368 else if(*s >= 'A' && *s <= 'F')
1369 val = 10 + *s - 'A';
1370 else
1371 val = base_type::max_limb_value;
1372 if(val >= radix)
1373 {
1374 BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1375 }
1376 block <<= shift;
1377 block |= val;
1378 if(!*++s)
1379 {
1380 // final shift is different:
1381 block_shift = (i + 1) * shift;
1382 break;
1383 }
1384 }
1385 eval_left_shift(*this, block_shift);
1386 this->limbs()[0] |= block;
1387 }
1388 }
1389 else
1390 {
1391 // Base 10, we extract blocks of size 10^9 at a time, that way
1392 // the number of multiplications is kept to a minimum:
1393 limb_type block_mult = max_block_10;
1394 while(*s)
1395 {
1396 limb_type block = 0;
1397 for(unsigned i = 0; i < digits_per_block_10; ++i)
1398 {
1399 limb_type val;
1400 if(*s >= '0' && *s <= '9')
1401 val = *s - '0';
1402 else
1403 BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input."));
1404 block *= 10;
1405 block += val;
1406 if(!*++s)
1407 {
1408 block_mult = block_multiplier(i);
1409 break;
1410 }
1411 }
1412 eval_multiply(*this, block_mult);
1413 eval_add(*this, block);
1414 }
1415 }
1416 }
1417 if(isneg)
1418 this->negate();
1419 }
1420 public:
1421 cpp_int_backend& operator = (const char* s)
1422 {
1423 do_assign_string(s, trivial_tag());
1424 return *this;
1425 }
1426 BOOST_MP_FORCEINLINE void swap(cpp_int_backend& o) BOOST_NOEXCEPT
1427 {
1428 this->do_swap(o);
1429 }
1430 private:
1431 std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::false_&)const
1432 {
1433 typedef typename mpl::if_c<sizeof(*this->limbs()) == 1, unsigned, typename base_type::local_limb_type>::type io_type;
1434 if(this->sign() && (((f & std::ios_base::hex) == std::ios_base::hex) || ((f & std::ios_base::oct) == std::ios_base::oct)))
1435 BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1436 std::stringstream ss;
1437 ss.flags(f & ~std::ios_base::showpos);
1438 ss << static_cast<io_type>(*this->limbs());
1439 std::string result;
1440 if(this->sign())
1441 result += '-';
1442 else if(f & std::ios_base::showpos)
1443 result += '+';
1444 result += ss.str();
1445 return result;
1446 }
1447 std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::true_&)const
1448 {
1449 // Even though we have only one limb, we can't do IO on it :-(
1450 int base = 10;
1451 if((f & std::ios_base::oct) == std::ios_base::oct)
1452 base = 8;
1453 else if((f & std::ios_base::hex) == std::ios_base::hex)
1454 base = 16;
1455 std::string result;
1456
1457 unsigned Bits = sizeof(typename base_type::local_limb_type) * CHAR_BIT;
1458
1459 if(base == 8 || base == 16)
1460 {
1461 if(this->sign())
1462 BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1463 limb_type shift = base == 8 ? 3 : 4;
1464 limb_type mask = static_cast<limb_type>((1u << shift) - 1);
1465 typename base_type::local_limb_type v = *this->limbs();
1466 result.assign(Bits / shift + (Bits % shift ? 1 : 0), '0');
1467 std::string::difference_type pos = result.size() - 1;
1468 for(unsigned i = 0; i < Bits / shift; ++i)
1469 {
1470 char c = '0' + static_cast<char>(v & mask);
1471 if(c > '9')
1472 c += 'A' - '9' - 1;
1473 result[pos--] = c;
1474 v >>= shift;
1475 }
1476 if(Bits % shift)
1477 {
1478 mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
1479 char c = '0' + static_cast<char>(v & mask);
1480 if(c > '9')
1481 c += 'A' - '9';
1482 result[pos] = c;
1483 }
1484 //
1485 // Get rid of leading zeros:
1486 //
1487 std::string::size_type n = result.find_first_not_of('0');
1488 if(!result.empty() && (n == std::string::npos))
1489 n = result.size() - 1;
1490 result.erase(0, n);
1491 if(f & std::ios_base::showbase)
1492 {
1493 const char* pp = base == 8 ? "0" : "0x";
1494 result.insert(0, pp);
1495 }
1496 }
1497 else
1498 {
1499 result.assign(Bits / 3 + 1, '0');
1500 std::string::difference_type pos = result.size() - 1;
1501 typename base_type::local_limb_type v(*this->limbs());
1502 bool neg = false;
1503 if(this->sign())
1504 {
1505 neg = true;
1506 }
1507 while(v)
1508 {
1509 result[pos] = (v % 10) + '0';
1510 --pos;
1511 v /= 10;
1512 }
1513 std::string::size_type n = result.find_first_not_of('0');
1514 result.erase(0, n);
1515 if(result.empty())
1516 result = "0";
1517 if(neg)
1518 result.insert(0, 1, '-');
1519 else if(f & std::ios_base::showpos)
1520 result.insert(0, 1, '+');
1521 }
1522 return result;
1523 }
1524 std::string do_get_string(std::ios_base::fmtflags f, const mpl::true_&)const
1525 {
1526 #ifdef BOOST_MP_NO_DOUBLE_LIMB_TYPE_IO
1527 return do_get_trivial_string(f, mpl::bool_<is_same<typename base_type::local_limb_type, double_limb_type>::value>());
1528 #else
1529 return do_get_trivial_string(f, mpl::bool_<false>());
1530 #endif
1531 }
1532 std::string do_get_string(std::ios_base::fmtflags f, const mpl::false_&)const
1533 {
1534 using default_ops::eval_get_sign;
1535 int base = 10;
1536 if((f & std::ios_base::oct) == std::ios_base::oct)
1537 base = 8;
1538 else if((f & std::ios_base::hex) == std::ios_base::hex)
1539 base = 16;
1540 std::string result;
1541
1542 unsigned Bits = this->size() * base_type::limb_bits;
1543
1544 if(base == 8 || base == 16)
1545 {
1546 if(this->sign())
1547 BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1548 limb_type shift = base == 8 ? 3 : 4;
1549 limb_type mask = static_cast<limb_type>((1u << shift) - 1);
1550 cpp_int_backend t(*this);
1551 result.assign(Bits / shift + (Bits % shift ? 1 : 0), '0');
1552 std::string::difference_type pos = result.size() - 1;
1553 for(unsigned i = 0; i < Bits / shift; ++i)
1554 {
1555 char c = '0' + static_cast<char>(t.limbs()[0] & mask);
1556 if(c > '9')
1557 c += 'A' - '9' - 1;
1558 result[pos--] = c;
1559 eval_right_shift(t, shift);
1560 }
1561 if(Bits % shift)
1562 {
1563 mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
1564 char c = '0' + static_cast<char>(t.limbs()[0] & mask);
1565 if(c > '9')
1566 c += 'A' - '9';
1567 result[pos] = c;
1568 }
1569 //
1570 // Get rid of leading zeros:
1571 //
1572 std::string::size_type n = result.find_first_not_of('0');
1573 if(!result.empty() && (n == std::string::npos))
1574 n = result.size() - 1;
1575 result.erase(0, n);
1576 if(f & std::ios_base::showbase)
1577 {
1578 const char* pp = base == 8 ? "0" : "0x";
1579 result.insert(0, pp);
1580 }
1581 }
1582 else
1583 {
1584 result.assign(Bits / 3 + 1, '0');
1585 std::string::difference_type pos = result.size() - 1;
1586 cpp_int_backend t(*this);
1587 cpp_int_backend r;
1588 bool neg = false;
1589 if(t.sign())
1590 {
1591 t.negate();
1592 neg = true;
1593 }
1594 if(this->size() == 1)
1595 {
1596 result = boost::lexical_cast<std::string>(t.limbs()[0]);
1597 }
1598 else
1599 {
1600 cpp_int_backend block10;
1601 block10 = max_block_10;
1602 while(eval_get_sign(t) != 0)
1603 {
1604 cpp_int_backend t2;
1605 divide_unsigned_helper(&t2, t, block10, r);
1606 t = t2;
1607 limb_type v = r.limbs()[0];
1608 for(unsigned i = 0; i < digits_per_block_10; ++i)
1609 {
1610 char c = '0' + v % 10;
1611 v /= 10;
1612 result[pos] = c;
1613 if(pos-- == 0)
1614 break;
1615 }
1616 }
1617 }
1618 std::string::size_type n = result.find_first_not_of('0');
1619 result.erase(0, n);
1620 if(result.empty())
1621 result = "0";
1622 if(neg)
1623 result.insert(0, 1, '-');
1624 else if(f & std::ios_base::showpos)
1625 result.insert(0, 1, '+');
1626 }
1627 return result;
1628 }
1629 public:
1630 std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f)const
1631 {
1632 return do_get_string(f, trivial_tag());
1633 }
1634 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1635 int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::false_&)const BOOST_NOEXCEPT
1636 {
1637 if(this->sign() != o.sign())
1638 return this->sign() ? -1 : 1;
1639
1640 // Only do the compare if the same sign:
1641 int result = compare_unsigned(o);
1642
1643 if(this->sign())
1644 result = -result;
1645 return result;
1646 }
1647 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1648 int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::false_&)const
1649 {
1650 cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t(*this);
1651 return t.compare(o);
1652 }
1653 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1654 int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::true_&)const
1655 {
1656 cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t(o);
1657 return compare(t);
1658 }
1659 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1660 int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::true_&)const BOOST_NOEXCEPT
1661 {
1662 if(this->sign())
1663 {
1664 if(o.sign())
1665 {
1666 return *this->limbs() < *o.limbs() ? 1 : (*this->limbs() > *o.limbs() ? -1 : 0);
1667 }
1668 else
1669 return -1;
1670 }
1671 else
1672 {
1673 if(o.sign())
1674 return 1;
1675 return *this->limbs() < *o.limbs() ? -1 : (*this->limbs() > *o.limbs() ? 1 : 0);
1676 }
1677 }
1678 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1679 int compare(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o)const BOOST_NOEXCEPT
1680 {
1681 typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value> t1;
1682 typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value> t2;
1683 return compare_imp(o, t1(), t2());
1684 }
1685 template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1686 int compare_unsigned(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o)const BOOST_NOEXCEPT
1687 {
1688 if(this->size() != o.size())
1689 {
1690 return this->size() > o.size() ? 1 : -1;
1691 }
1692 typename base_type::const_limb_pointer pa = this->limbs();
1693 typename base_type::const_limb_pointer pb = o.limbs();
1694 for(int i = this->size() - 1; i >= 0; --i)
1695 {
1696 if(pa[i] != pb[i])
1697 return pa[i] > pb[i] ? 1 : -1;
1698 }
1699 return 0;
1700 }
1701 template <class Arithmetic>
1702 BOOST_MP_FORCEINLINE typename boost::enable_if<is_arithmetic<Arithmetic>, int>::type compare(Arithmetic i)const
1703 {
1704 // braindead version:
1705 cpp_int_backend t;
1706 t = i;
1707 return compare(t);
1708 }
1709 };
1710
1711 } // namespace backends
1712
1713 namespace default_ops{
1714
1715 template <class Backend>
1716 struct double_precision_type;
1717
1718 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
1719 struct double_precision_type<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
1720 {
1721 typedef typename mpl::if_c<
1722 backends::is_fixed_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1723 backends::cpp_int_backend<
1724 (is_void<Allocator>::value ?
1725 2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value
1726 : MinBits),
1727 2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1728 SignType,
1729 Checked,
1730 Allocator>,
1731 backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>
1732 >::type type;
1733 };
1734
1735
1736 }
1737
1738 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked>
1739 struct expression_template_default<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, void> >
1740 {
1741 static const expression_template_option value = et_off;
1742 };
1743
1744 using boost::multiprecision::backends::cpp_int_backend;
1745
1746 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
1747 struct number_category<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public mpl::int_<number_kind_integer>{};
1748
1749 typedef number<cpp_int_backend<> > cpp_int;
1750 typedef rational_adaptor<cpp_int_backend<> > cpp_rational_backend;
1751 typedef number<cpp_rational_backend> cpp_rational;
1752
1753 // Fixed precision unsigned types:
1754 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> > uint128_t;
1755 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> > uint256_t;
1756 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> > uint512_t;
1757 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;
1758
1759 // Fixed precision signed types:
1760 typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> > int128_t;
1761 typedef number<cpp_int_backend<256, 256, signed_magnitude, unchecked, void> > int256_t;
1762 typedef number<cpp_int_backend<512, 512, signed_magnitude, unchecked, void> > int512_t;
1763 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, unchecked, void> > int1024_t;
1764
1765 // Over again, but with checking enabled this time:
1766 typedef number<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_int;
1767 typedef rational_adaptor<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_rational_backend;
1768 typedef number<cpp_rational_backend> checked_cpp_rational;
1769 // Fixed precision unsigned types:
1770 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, checked, void> > checked_uint128_t;
1771 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, checked, void> > checked_uint256_t;
1772 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, checked, void> > checked_uint512_t;
1773 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, checked, void> > checked_uint1024_t;
1774
1775 // Fixed precision signed types:
1776 typedef number<cpp_int_backend<128, 128, signed_magnitude, checked, void> > checked_int128_t;
1777 typedef number<cpp_int_backend<256, 256, signed_magnitude, checked, void> > checked_int256_t;
1778 typedef number<cpp_int_backend<512, 512, signed_magnitude, checked, void> > checked_int512_t;
1779 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, checked, void> > checked_int1024_t;
1780
1781 #ifdef BOOST_NO_SFINAE_EXPR
1782
1783 namespace detail{
1784
1785 template<unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1786 struct is_explicitly_convertible<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > : public mpl::true_ {};
1787
1788 }
1789 #endif
1790
1791 }} // namespaces
1792
1793 //
1794 // Last of all we include the implementations of all the eval_* non member functions:
1795 //
1796 #include <boost/multiprecision/cpp_int/comparison.hpp>
1797 #include <boost/multiprecision/cpp_int/add.hpp>
1798 #include <boost/multiprecision/cpp_int/multiply.hpp>
1799 #include <boost/multiprecision/cpp_int/divide.hpp>
1800 #include <boost/multiprecision/cpp_int/bitwise.hpp>
1801 #include <boost/multiprecision/cpp_int/misc.hpp>
1802 #include <boost/multiprecision/cpp_int/limits.hpp>
1803 #ifdef BOOST_MP_USER_DEFINED_LITERALS
1804 #include <boost/multiprecision/cpp_int/literals.hpp>
1805 #endif
1806 #include <boost/multiprecision/cpp_int/serialize.hpp>
1807
1808 #endif