1	////////////////////////////////////////////////////////////////
2	// Copyright 2012 - 2022 John Maddock.
3	// Copyright 2022 Christopher Kormanyos.
4	// Distributed under the Boost Software License,
5	// Version 1.0. (See accompanying file LICENSE_1_0.txt
6	// or copy at https://www.boost.org/LICENSE_1_0.txt)
7
8	#ifndef BOOST_MP_CPP_INT_HPP
9	#define BOOST_MP_CPP_INT_HPP
10
11	#include <cstdint>
12	#include <cstring>
13	#include <iostream>
14	#include <iomanip>
15	#include <type_traits>
16	#include <string>
17	#include <boost/multiprecision/detail/standalone_config.hpp>
18	#include <boost/multiprecision/detail/endian.hpp>
19	#include <boost/multiprecision/number.hpp>
20	#include <boost/multiprecision/detail/integer_ops.hpp>
21	#include <boost/multiprecision/detail/rebind.hpp>
22	#include <boost/multiprecision/cpp_int/cpp_int_config.hpp>
23	#include <boost/multiprecision/rational_adaptor.hpp>
24	#include <boost/multiprecision/traits/is_byte_container.hpp>
25	#include <boost/multiprecision/cpp_int/checked.hpp>
26	#include <boost/multiprecision/detail/constexpr.hpp>
27	#include <boost/multiprecision/detail/float128_functions.hpp>
28	#include <boost/multiprecision/cpp_int/value_pack.hpp>
29	#include <boost/multiprecision/detail/empty_value.hpp>
30	#include <boost/multiprecision/detail/no_exceptions_support.hpp>
31	#include <boost/multiprecision/detail/assert.hpp>
32	#include <boost/multiprecision/detail/fpclassify.hpp>
33
34	namespace boost {
35	namespace multiprecision {
36
37	#ifdef BOOST_MSVC
38	#pragma warning(push)
39	#pragma warning(disable : 4307) // integral constant overflow (oveflow is in a branch not taken when it would overflow)
40	#pragma warning(disable : 4127) // conditional expression is constant
41	#pragma warning(disable : 4702) // Unreachable code (reachability depends on template params)
42	#endif
43	#if defined(__GNUC__) && !defined(__clang__)
44	// see https://github.com/boostorg/multiprecision/issues/413
45	// and https://github.com/boostorg/multiprecision/issues/431
46	#pragma GCC diagnostic push
47	#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
48	#endif
49
50	namespace detail {
51
52	template <std::size_t MinBits, std::size_t MaxBits, boost::multiprecision::cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
53	struct is_byte_container<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public std::false_type
54	{};
55
56	} // namespace detail
57
58	namespace backends {
59
60	namespace detail {
61	template <std::size_t Value1, std::size_t Value2>
62	struct static_unsigned_max
63	{
64	static constexpr std::size_t value = (Value1 > Value2) ? Value1 : Value2;
65	};
66	} // Namespace detail
67
68	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, bool trivial = false>
69	struct cpp_int_base;
70	//
71	// Traits class determines the maximum and minimum precision values:
72	//
73	template <class T>
74	struct max_precision;
75
76	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
77	struct max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
78	{
79	static constexpr std::size_t value = std::is_void<Allocator>::value ? detail::static_unsigned_max<MinBits, MaxBits>::value
80	: (((MaxBits >= MinBits) && MaxBits) ? MaxBits : SIZE_MAX);
81	};
82
83	template <class T>
84	struct min_precision;
85
86	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
87	struct min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
88	{
89	static constexpr std::size_t value = (std::is_void<Allocator>::value ? detail::static_unsigned_max<MinBits, MaxBits>::value : MinBits);
90	};
91	//
92	// Traits class determines whether the number of bits precision requested could fit in a native type,
93	// we call this a "trivial" cpp_int:
94	//
95	template <class T>
96	struct is_trivial_cpp_int
97	{
98	static constexpr bool value = false;
99	};
100
101	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
102	struct is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
103	{
104	using self = cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>;
105	static constexpr bool value = std::is_void<Allocator>::value && (max_precision<self>::value <= (sizeof(double_limb_type) * CHAR_BIT) - (SignType == signed_packed ? 1 : 0));
106	};
107
108	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
109	struct is_trivial_cpp_int<cpp_int_base<MinBits, MaxBits, SignType, Checked, Allocator, true> >
110	{
111	static constexpr bool value = true;
112	};
113
114	} // namespace backends
115	//
116	// Traits class to determine whether a cpp_int_backend is signed or not:
117	//
118	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
119	struct is_unsigned_number<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
120	: public std::integral_constant<bool, (SignType == unsigned_magnitude) || (SignType == unsigned_packed)>
121	{};
122
123	namespace backends {
124	//
125	// Traits class determines whether T should be implicitly convertible to U, or
126	// whether the constructor should be made explicit. The latter happens if we
127	// are losing the sign, or have fewer digits precision in the target type:
128	//
129	template <class T, class U>
130	struct is_implicit_cpp_int_conversion;
131
132	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
133	struct is_implicit_cpp_int_conversion<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >
134	{
135	using t1 = cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>;
136	using t2 = cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>;
137	static constexpr bool value =
138	(is_signed_number<t2>::value || !is_signed_number<t1>::value) && (max_precision<t1>::value <= max_precision<t2>::value);
139	};
140
141	//
142	// Traits class to determine whether operations on a cpp_int may throw:
143	//
144	template <class T>
145	struct is_non_throwing_cpp_int : public std::integral_constant<bool, false>
146	{};
147	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType>
148	struct is_non_throwing_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, unchecked, void> > : public std::integral_constant<bool, true>
149	{};
150
151	//
152	// Traits class, determines whether the cpp_int is fixed precision or not:
153	//
154	template <class T>
155	struct is_fixed_precision;
156	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
157	struct is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
158	: public std::integral_constant<bool, max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value != SIZE_MAX>
159	{};
160
161	namespace detail {
162
163	inline BOOST_MP_CXX14_CONSTEXPR void verify_new_size(std::size_t new_size, std::size_t min_size, const std::integral_constant<int, checked>&)
164	{
165	if (new_size < min_size)
166	BOOST_MP_THROW_EXCEPTION(std::overflow_error("Unable to allocate sufficient storage for the value of the result: value overflows the maximum allowable magnitude."));
167	}
168	inline BOOST_MP_CXX14_CONSTEXPR void verify_new_size(std::size_t /*new_size*/, std::size_t /*min_size*/, const std::integral_constant<int, unchecked>&) {}
169
170	template <class U>
171	inline BOOST_MP_CXX14_CONSTEXPR void verify_limb_mask(bool b, U limb, U mask, const std::integral_constant<int, checked>&)
172	{
173	// When we mask out "limb" with "mask", do we loose bits? If so it's an overflow error:
174	if (b && (limb & ~mask))
175	BOOST_MP_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."));
176	}
177	template <class U>
178	inline BOOST_MP_CXX14_CONSTEXPR void verify_limb_mask(bool /*b*/, U /*limb*/, U /*mask*/, const std::integral_constant<int, unchecked>&) {}
179
180	} // namespace detail
181
182	//
183	// Now define the various data layouts that are possible as partial specializations of the base class,
184	// starting with the default arbitrary precision signed integer type:
185	//
186	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
187	struct cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>
188	: private boost::multiprecision::detail::empty_value<typename detail::rebind<limb_type, Allocator>::type>
189	{
190	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, bool trivial2>
191	friend struct cpp_int_base;
192
193	using allocator_type = typename detail::rebind<limb_type, Allocator>::type;
194	using limb_pointer = typename std::allocator_traits<allocator_type>::pointer ;
195	using const_limb_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
196	using checked_type = std::integral_constant<int, Checked>;
197
198	//
199	// Interface invariants:
200	//
201	static_assert(!std::is_void<Allocator>::value, "Allocator must not be void here");
202
203	using base_type = boost::multiprecision::detail::empty_value<allocator_type>;
204
205	private:
206	struct limb_data
207	{
208	std::size_t capacity;
209	limb_pointer data;
210	};
211
212	public:
213	static constexpr std::size_t limb_bits = sizeof(limb_type) * CHAR_BIT;
214	static constexpr limb_type max_limb_value = ~static_cast<limb_type>(0u);
215	static constexpr limb_type sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1);
216	static constexpr std::size_t internal_limb_count =
217	MinBits
218	? (MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0))
219	: (sizeof(limb_data) / sizeof(limb_type)) > 1 ? (sizeof(limb_data) / sizeof(limb_type)) : 2;
220	private:
221	union data_type
222	{
223	limb_data ld;
224	limb_type la[internal_limb_count];
225	limb_type first;
226	double_limb_type double_first;
227
228	constexpr data_type() noexcept : first(0) {}
229	constexpr data_type(limb_type i) noexcept : first(i) {}
230	constexpr data_type(signed_limb_type i) noexcept : first(static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(t: i))) {}
231	#if BOOST_MP_ENDIAN_LITTLE_BYTE
232	constexpr data_type(double_limb_type i) noexcept : double_first(i)
233	{}
234	constexpr data_type(signed_double_limb_type i) noexcept : double_first(static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i))) {}
235	#endif
236	#if !defined(BOOST_NO_CXX11_UNIFIED_INITIALIZATION_SYNTAX) && !(defined(BOOST_MSVC) && (BOOST_MSVC < 1900))
237	constexpr data_type(limb_type* limbs, std::size_t len) noexcept : ld{ len, limbs }
238	{}
239	#else
240	constexpr data_type(limb_type* limbs, std::size_t len) noexcept
241	{
242	ld.capacity = len;
243	ld.data = limbs;
244	}
245	#endif
246	};
247
248	data_type m_data;
249	std::size_t m_limbs;
250	bool m_sign, m_internal, m_alias;
251
252	public:
253	//
254	// Direct construction:
255	//
256	BOOST_MP_FORCEINLINE constexpr cpp_int_base(limb_type i) noexcept
257	: m_data(i),
258	m_limbs(1),
259	m_sign(false),
260	m_internal(true),
261	m_alias(false) {}
262	BOOST_MP_FORCEINLINE constexpr cpp_int_base(signed_limb_type i) noexcept
263	: m_data(i),
264	m_limbs(1),
265	m_sign(i < 0),
266	m_internal(true),
267	m_alias(false) {}
268	#if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
269	BOOST_MP_FORCEINLINE constexpr cpp_int_base(double_limb_type i) noexcept
270	: m_data(i),
271	m_limbs(i > max_limb_value ? 2 : 1),
272	m_sign(false),
273	m_internal(true),
274	m_alias(false)
275	{}
276	BOOST_MP_FORCEINLINE constexpr cpp_int_base(signed_double_limb_type i) noexcept
277	: m_data(i),
278	m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i)) > static_cast<double_limb_type>(max_limb_value) ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
279	m_sign(i < 0),
280	m_internal(true),
281	m_alias(false) {}
282	#endif
283	//
284	// Aliasing constructor aliases data:
285	//
286	struct scoped_shared_storage : private boost::multiprecision::detail::empty_value<allocator_type>
287	{
288	private:
289	limb_type* data;
290	std::size_t capacity;
291	std::size_t allocated;
292	bool is_alias;
293	allocator_type& allocator() noexcept { return boost::multiprecision::detail::empty_value<allocator_type>::get(); }
294
295	public:
296	scoped_shared_storage(const allocator_type& a, std::size_t len)
297	: boost::multiprecision::detail::empty_value<allocator_type>(boost::multiprecision::detail::empty_init_t(), a), capacity(len), allocated(0), is_alias(false)
298	{
299	data = allocator().allocate(len);
300	}
301	scoped_shared_storage(const cpp_int_base& i, std::size_t len)
302	: boost::multiprecision::detail::empty_value<allocator_type>(boost::multiprecision::detail::empty_init_t(), i.allocator()), capacity(len), allocated(0), is_alias(false)
303	{
304	data = allocator().allocate(len);
305	}
306	scoped_shared_storage(limb_type* limbs, std::size_t n) : data(limbs), capacity(n), allocated(0), is_alias(true) {}
307	~scoped_shared_storage()
308	{
309	if(!is_alias)
310	allocator().deallocate(data, capacity);
311	}
312	limb_type* allocate(std::size_t n) noexcept
313	{
314	limb_type* result = data + allocated;
315	allocated += n;
316	BOOST_MP_ASSERT(allocated <= capacity);
317	return result;
318	}
319	void deallocate(std::size_t n)
320	{
321	BOOST_MP_ASSERT(n <= allocated);
322	allocated -= n;
323	}
324	};
325	explicit constexpr cpp_int_base(limb_type* data, std::size_t offset, std::size_t len) noexcept
326	: m_data(data + offset, len),
327	m_limbs(len),
328	m_sign(false),
329	m_internal(false),
330	m_alias(true) {}
331	// This next constructor is for constructing const objects from const limb_type*'s only.
332	// Unfortunately we appear to have no way to assert that within the language, and the const_cast
333	// is a side effect of that :(
334	explicit constexpr cpp_int_base(const limb_type* data, std::size_t offset, std::size_t len) noexcept
335	: m_data(const_cast<limb_type*>(data) + offset, len),
336	m_limbs(len),
337	m_sign(false),
338	m_internal(false),
339	m_alias(true) {}
340	explicit cpp_int_base(scoped_shared_storage& data, std::size_t len) noexcept
341	: m_data(data.allocate(len), len),
342	m_limbs(len),
343	m_sign(false),
344	m_internal(false),
345	m_alias(true) {}
346	//
347	// Helper functions for getting at our internal data, and manipulating storage:
348	//
349	BOOST_MP_FORCEINLINE allocator_type& allocator() noexcept { return base_type::get(); }
350	BOOST_MP_FORCEINLINE const allocator_type& allocator() const noexcept { return base_type::get(); }
351	BOOST_MP_FORCEINLINE std::size_t size() const noexcept { return m_limbs; }
352	BOOST_MP_FORCEINLINE limb_pointer limbs() noexcept { return m_internal ? m_data.la : m_data.ld.data; }
353	BOOST_MP_FORCEINLINE const_limb_pointer limbs() const noexcept { return m_internal ? m_data.la : m_data.ld.data; }
354	BOOST_MP_FORCEINLINE std::size_t capacity() const noexcept { return m_internal ? internal_limb_count : m_data.ld.capacity; }
355	BOOST_MP_FORCEINLINE bool sign() const noexcept { return m_sign; }
356	void sign(bool b) noexcept
357	{
358	m_sign = b;
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	void resize(std::size_t new_size, std::size_t min_size)
367	{
368	constexpr std::size_t max_limbs = MaxBits / (CHAR_BIT * sizeof(limb_type)) + ((MaxBits % (CHAR_BIT * sizeof(limb_type))) ? 1 : 0);
369	// We never resize beyond MaxSize:
370	if (new_size > max_limbs)
371	new_size = max_limbs;
372	detail::verify_new_size(new_size, min_size, checked_type());
373	// See if we have enough capacity already:
374	std::size_t cap = capacity();
375	if (new_size > cap)
376	{
377	// We must not be an alias, memory allocation here defeats the whole point of aliasing:
378	BOOST_MP_ASSERT(!m_alias);
379	// Allocate a new buffer and copy everything over:
380	cap = (std::min)(a: (std::max)(a: cap * 4, b: new_size), b: max_limbs);
381	limb_pointer pl = allocator().allocate(cap);
382	std::memcpy(dest: pl, src: limbs(), n: size() * sizeof(limbs()[0]));
383	if (!m_internal && !m_alias)
384	allocator().deallocate(limbs(), capacity());
385	else
386	m_internal = false;
387	m_limbs = new_size;
388	m_data.ld.capacity = cap;
389	m_data.ld.data = pl;
390	}
391	else
392	{
393	m_limbs = new_size;
394	}
395	}
396	BOOST_MP_FORCEINLINE void normalize() noexcept
397	{
398	limb_pointer p = limbs();
399	while ((m_limbs - 1) && !p[m_limbs - 1])
400	--m_limbs;
401	}
402	BOOST_MP_FORCEINLINE constexpr cpp_int_base() noexcept : m_data(), m_limbs(1), m_sign(false), m_internal(true), m_alias(false){}
403	BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) : base_type(o), m_limbs(o.m_alias ? o.m_limbs : 0), m_sign(o.m_sign), m_internal(o.m_alias ? false : true), m_alias(o.m_alias)
404	{
405	if (m_alias)
406	{
407	m_data.ld = o.m_data.ld;
408	}
409	else
410	{
411	resize(new_size: o.size(), min_size: o.size());
412	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(limbs()[0]));
413	}
414	}
415	// rvalue copy:
416	cpp_int_base(cpp_int_base&& o)
417	: base_type(static_cast<base_type&&>(o)), m_limbs(o.m_limbs), m_sign(o.m_sign), m_internal(o.m_internal), m_alias(o.m_alias)
418	{
419	if (m_internal)
420	{
421	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(limbs()[0]));
422	}
423	else
424	{
425	m_data.ld = o.m_data.ld;
426	o.m_limbs = 0;
427	o.m_internal = true;
428	}
429	}
430	cpp_int_base& operator=(cpp_int_base&& o) noexcept
431	{
432	if (!m_internal && !m_alias)
433	allocator().deallocate(m_data.ld.data, m_data.ld.capacity);
434	*static_cast<base_type*>(this) = static_cast<base_type&&>(o);
435	m_limbs = o.m_limbs;
436	m_sign = o.m_sign;
437	m_internal = o.m_internal;
438	m_alias = o.m_alias;
439	if (m_internal)
440	{
441	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(limbs()[0]));
442	}
443	else
444	{
445	m_data.ld = o.m_data.ld;
446	o.m_limbs = 0;
447	o.m_internal = true;
448	}
449	return *this;
450	}
451	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_int_check_type Checked2>
452	cpp_int_base& operator=(cpp_int_base<MinBits2, MaxBits2, signed_magnitude, Checked2, Allocator>&& o) noexcept
453	{
454	if(o.m_internal)
455	{
456	m_sign = o.m_sign;
457	this->resize(o.size(), o.size());
458	std::memcpy(dest: this->limbs(), src: o.limbs(), n: o.size() * sizeof(*(o.limbs())));
459	return *this;
460	}
461	if (!m_internal && !m_alias)
462	allocator().deallocate(m_data.ld.data, m_data.ld.capacity);
463	*static_cast<base_type*>(this) = static_cast<typename cpp_int_base<MinBits2, MaxBits2, signed_magnitude, Checked2, Allocator>::base_type&&>(o);
464	m_limbs = o.m_limbs;
465	m_sign = o.m_sign;
466	m_internal = o.m_internal;
467	m_alias = o.m_alias;
468	m_data.ld.capacity = o.m_data.ld.capacity;
469	m_data.ld.data = o.limbs();
470	o.m_limbs = 0;
471	o.m_internal = true;
472	return *this;
473	}
474	BOOST_MP_FORCEINLINE ~cpp_int_base() noexcept
475	{
476	if (!m_internal && !m_alias)
477	allocator().deallocate(limbs(), capacity());
478	}
479	void assign(const cpp_int_base& o)
480	{
481	if (this != &o)
482	{
483	static_cast<base_type&>(*this) = static_cast<const base_type&>(o);
484	m_limbs = 0;
485	resize(new_size: o.size(), min_size: o.size());
486	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(limbs()[0]));
487	m_sign = o.m_sign;
488	}
489	}
490	BOOST_MP_FORCEINLINE void negate() noexcept
491	{
492	m_sign = !m_sign;
493	// Check for zero value:
494	if (m_sign && (m_limbs == 1))
495	{
496	if (limbs()[0] == 0)
497	m_sign = false;
498	}
499	}
500	BOOST_MP_FORCEINLINE bool isneg() const noexcept
501	{
502	return m_sign;
503	}
504	BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) noexcept
505	{
506	std::swap(m_data, o.m_data);
507	std::swap(m_sign, o.m_sign);
508	std::swap(m_internal, o.m_internal);
509	std::swap(m_limbs, o.m_limbs);
510	std::swap(m_alias, o.m_alias);
511	}
512
513	protected:
514	template <class A>
515	void check_in_range(const A&) noexcept {}
516	};
517
518	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
519	constexpr std::size_t cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::limb_bits;
520	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
521	constexpr limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::max_limb_value;
522	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
523	constexpr limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::sign_bit_mask;
524	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
525	constexpr std::size_t cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::internal_limb_count;
526
527	template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
528	struct cpp_int_base<MinBits, MaxBits, unsigned_magnitude, Checked, Allocator, false>
529	: private boost::multiprecision::detail::empty_value<typename detail::rebind<limb_type, Allocator>::type>
530	{
531	//
532	// There is currently no support for unsigned arbitrary precision arithmetic, largely
533	// because it's not clear what subtraction should do:
534	//
535	static_assert(((sizeof(Allocator) == 0) && !std::is_void<Allocator>::value), "There is curently no support for unsigned arbitrary precision integers.");
536	};
537	//
538	// Fixed precision (i.e. no allocator), signed-magnitude type with limb-usage count:
539	//
540	template <std::size_t MinBits, cpp_int_check_type Checked>
541	struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>
542	{
543	using limb_pointer = limb_type* ;
544	using const_limb_pointer = const limb_type* ;
545	using checked_type = std::integral_constant<int, Checked>;
546
547	struct scoped_shared_storage
548	{
549	BOOST_MP_CXX14_CONSTEXPR scoped_shared_storage(const cpp_int_base&, std::size_t) {}
550	BOOST_MP_CXX14_CONSTEXPR void deallocate(std::size_t) {}
551	};
552
553	//
554	// Interface invariants:
555	//
556	static_assert(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?");
557
558	public:
559	static constexpr std::size_t limb_bits = sizeof(limb_type) * CHAR_BIT;
560	static constexpr limb_type max_limb_value = ~static_cast<limb_type>(0u);
561	static constexpr limb_type sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1);
562	static constexpr std::size_t internal_limb_count = MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0);
563	static constexpr limb_type upper_limb_mask = (MinBits % limb_bits) ? (limb_type(1) << (MinBits % limb_bits)) - 1 : (~limb_type(0));
564	static_assert(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
565
566	private:
567	union data_type
568	{
569	limb_type m_data[internal_limb_count];
570	limb_type m_first_limb;
571	double_limb_type m_double_first_limb;
572
573	constexpr data_type()
574	: m_data{0}
575	{}
576	constexpr data_type(limb_type i)
577	: m_data{i}
578	{}
579	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
580	constexpr data_type(limb_type i, limb_type j) : m_data{i, j}
581	{}
582	#endif
583	constexpr data_type(double_limb_type i) : m_double_first_limb(i)
584	{
585	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
586	if (BOOST_MP_IS_CONST_EVALUATED(m_double_first_limb))
587	{
588	data_type t(static_cast<limb_type>(i & max_limb_value), static_cast<limb_type>(i >> limb_bits));
589	*this = t;
590	}
591	#endif
592	}
593	template <limb_type... VALUES>
594	constexpr data_type(literals::detail::value_pack<VALUES...>) : m_data{VALUES...}
595	{}
596	} m_wrapper;
597	std::uint16_t m_limbs;
598	bool m_sign;
599
600	public:
601	//
602	// Direct construction:
603	//
604	BOOST_MP_FORCEINLINE constexpr cpp_int_base(limb_type i) noexcept
605	: m_wrapper(i),
606	m_limbs(1),
607	m_sign(false) {}
608	BOOST_MP_FORCEINLINE constexpr cpp_int_base(signed_limb_type i) noexcept
609	: m_wrapper(limb_type(i < 0 ? static_cast<limb_type>(-static_cast<signed_double_limb_type>(i)) : i)),
610	m_limbs(1),
611	m_sign(i < 0) {}
612	#if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
613	BOOST_MP_FORCEINLINE constexpr cpp_int_base(double_limb_type i) noexcept
614	: m_wrapper(i),
615	m_limbs(i > max_limb_value ? 2 : 1),
616	m_sign(false)
617	{}
618	BOOST_MP_FORCEINLINE constexpr cpp_int_base(signed_double_limb_type i) noexcept
619	: m_wrapper(double_limb_type(i < 0 ? static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i)) : i)),
620	m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i)) > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
621	m_sign(i < 0) {}
622	#endif
623	template <limb_type... VALUES>
624	constexpr cpp_int_base(literals::detail::value_pack<VALUES...> i)
625	: m_wrapper(i), m_limbs(sizeof...(VALUES)), m_sign(false)
626	{}
627	constexpr cpp_int_base(literals::detail::value_pack<> i)
628	: m_wrapper(i), m_limbs(1), m_sign(false) {}
629	constexpr cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&)
630	: m_wrapper(a.m_wrapper), m_limbs(a.m_limbs), m_sign((a.m_limbs == 1) && (*a.limbs() == 0) ? false : !a.m_sign) {}
631	explicit constexpr cpp_int_base(scoped_shared_storage&, std::size_t) noexcept : m_wrapper(), m_limbs(0), m_sign(false)
632	{}
633	//
634	// These are deprecated in C++20 unless we make them explicit:
635	//
636	BOOST_MP_CXX14_CONSTEXPR cpp_int_base& operator=(const cpp_int_base&) = default;
637	//
638	// Helper functions for getting at our internal data, and manipulating storage:
639	//
640	BOOST_MP_FORCEINLINE constexpr std::size_t size() const noexcept { return m_limbs; }
641	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() noexcept { return m_wrapper.m_data; }
642	BOOST_MP_FORCEINLINE constexpr const_limb_pointer limbs() const noexcept { return m_wrapper.m_data; }
643	BOOST_MP_FORCEINLINE constexpr bool sign() const noexcept { return m_sign; }
644	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) noexcept
645	{
646	m_sign = b;
647	// Check for zero value:
648	if (m_sign && (m_limbs == 1))
649	{
650	if (limbs()[0] == 0)
651	m_sign = false;
652	}
653	}
654	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(std::size_t new_size, std::size_t min_size) noexcept((Checked == unchecked))
655	{
656	m_limbs = static_cast<std::uint16_t>((std::min)(a: new_size, b: internal_limb_count));
657	detail::verify_new_size(m_limbs, min_size, checked_type());
658	}
659	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() noexcept((Checked == unchecked))
660	{
661	limb_pointer p = limbs();
662	detail::verify_limb_mask(m_limbs == internal_limb_count, p[m_limbs - 1], upper_limb_mask, checked_type());
663	p[internal_limb_count - 1] &= upper_limb_mask;
664	while ((m_limbs - 1) && !p[m_limbs - 1])
665	--m_limbs;
666	if ((m_limbs == 1) && (!*p))
667	m_sign = false; // zero is always unsigned
668	}
669
670	BOOST_MP_FORCEINLINE constexpr cpp_int_base() noexcept : m_wrapper(limb_type(0u)), m_limbs(1), m_sign(false) {}
671	// Not defaulted, it breaks constexpr support in the Intel compiler for some reason:
672	BOOST_MP_FORCEINLINE constexpr cpp_int_base(const cpp_int_base& o) noexcept
673	: m_wrapper(o.m_wrapper),
674	m_limbs(o.m_limbs),
675	m_sign(o.m_sign) {}
676	// Defaulted functions:
677	//~cpp_int_base() noexcept {}
678
679	void BOOST_MP_CXX14_CONSTEXPR assign(const cpp_int_base& o) noexcept
680	{
681	if (this != &o)
682	{
683	m_limbs = o.m_limbs;
684	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
685	if (BOOST_MP_IS_CONST_EVALUATED(m_limbs))
686	{
687	for (std::size_t i = 0; i < m_limbs; ++i)
688	limbs()[i] = o.limbs()[i];
689	}
690	else
691	#endif
692	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(o.limbs()[0]));
693	m_sign = o.m_sign;
694	}
695	}
696	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate() noexcept
697	{
698	m_sign = !m_sign;
699	// Check for zero value:
700	if (m_sign && (m_limbs == 1))
701	{
702	if (limbs()[0] == 0)
703	m_sign = false;
704	}
705	}
706	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool isneg() const noexcept
707	{
708	return m_sign;
709	}
710	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) noexcept
711	{
712	for (std::size_t i = 0; i < (std::max)(size(), o.size()); ++i)
713	std_constexpr::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
714	std_constexpr::swap(m_sign, o.m_sign);
715	std_constexpr::swap(m_limbs, o.m_limbs);
716	}
717
718	protected:
719	template <class A>
720	BOOST_MP_CXX14_CONSTEXPR void check_in_range(const A&) noexcept {}
721	};
722
723	template <std::size_t MinBits, cpp_int_check_type Checked>
724	constexpr std::size_t cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::limb_bits;
725	template <std::size_t MinBits, cpp_int_check_type Checked>
726	constexpr limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::max_limb_value;
727	template <std::size_t MinBits, cpp_int_check_type Checked>
728	constexpr limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::sign_bit_mask;
729	template <std::size_t MinBits, cpp_int_check_type Checked>
730	constexpr std::size_t cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::internal_limb_count;
731	//
732	// Fixed precision (i.e. no allocator), unsigned type with limb-usage count:
733	//
734	template <std::size_t MinBits, cpp_int_check_type Checked>
735	struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>
736	{
737	using limb_pointer = limb_type* ;
738	using const_limb_pointer = const limb_type* ;
739	using checked_type = std::integral_constant<int, Checked>;
740
741	struct scoped_shared_storage
742	{
743	BOOST_MP_CXX14_CONSTEXPR scoped_shared_storage(const cpp_int_base&, std::size_t) {}
744	BOOST_MP_CXX14_CONSTEXPR void deallocate(std::size_t) {}
745	};
746	//
747	// Interface invariants:
748	//
749	static_assert(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?");
750
751	public:
752	static constexpr std::size_t limb_bits = sizeof(limb_type) * CHAR_BIT;
753	static constexpr limb_type max_limb_value = ~static_cast<limb_type>(0u);
754	static constexpr limb_type sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1);
755	static constexpr std::size_t internal_limb_count = MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0);
756	static constexpr limb_type upper_limb_mask = (MinBits % limb_bits) ? (limb_type(1) << (MinBits % limb_bits)) - 1 : (~limb_type(0));
757	static_assert(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
758
759	private:
760	union data_type
761	{
762	limb_type m_data[internal_limb_count];
763	limb_type m_first_limb;
764	double_limb_type m_double_first_limb;
765
766	constexpr data_type()
767	: m_data{0}
768	{}
769	constexpr data_type(limb_type i)
770	: m_data{i}
771	{}
772	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
773	constexpr data_type(limb_type i, limb_type j) : m_data{i, j}
774	{}
775	#endif
776	constexpr data_type(double_limb_type i) : m_double_first_limb(i)
777	{
778	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
779	if (BOOST_MP_IS_CONST_EVALUATED(m_double_first_limb))
780	{
781	data_type t(static_cast<limb_type>(i & max_limb_value), static_cast<limb_type>(i >> limb_bits));
782	*this = t;
783	}
784	#endif
785	}
786	template <limb_type... VALUES>
787	constexpr data_type(literals::detail::value_pack<VALUES...>) : m_data{VALUES...}
788	{}
789	} m_wrapper;
790	std::size_t m_limbs;
791
792	public:
793	//
794	// Direct construction:
795	//
796	BOOST_MP_FORCEINLINE constexpr cpp_int_base(limb_type i) noexcept
797	: m_wrapper(i),
798	m_limbs(1) {}
799	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(signed_limb_type i) noexcept((Checked == unchecked))
800	: m_wrapper(static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(t: i))),
801	m_limbs(1)
802	{
803	if (i < 0)
804	negate();
805	}
806	#if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
807	BOOST_MP_FORCEINLINE constexpr cpp_int_base(double_limb_type i) noexcept
808	: m_wrapper(i),
809	m_limbs(i > max_limb_value ? 2 : 1)
810	{}
811	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(signed_double_limb_type i) noexcept((Checked == unchecked))
812	: m_wrapper(double_limb_type(i < 0 ? static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i)) : i)),
813	m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(t: i)) > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1))
814	{
815	if (i < 0)
816	negate();
817	}
818	#endif
819	template <limb_type... VALUES>
820	constexpr cpp_int_base(literals::detail::value_pack<VALUES...> i)
821	: m_wrapper(i), m_limbs(sizeof...(VALUES))
822	{}
823	constexpr cpp_int_base(literals::detail::value_pack<>)
824	: m_wrapper(static_cast<limb_type>(0u)), m_limbs(1) {}
825	explicit constexpr cpp_int_base(scoped_shared_storage&, std::size_t) noexcept : m_wrapper(), m_limbs(1)
826	{}
827	//
828	// Helper functions for getting at our internal data, and manipulating storage:
829	//
830	BOOST_MP_FORCEINLINE constexpr std::size_t size() const noexcept { return m_limbs; }
831	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() noexcept { return m_wrapper.m_data; }
832	BOOST_MP_FORCEINLINE constexpr const_limb_pointer limbs() const noexcept { return m_wrapper.m_data; }
833	BOOST_MP_FORCEINLINE constexpr bool sign() const noexcept { return false; }
834	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) noexcept((Checked == unchecked))
835	{
836	if (b)
837	negate();
838	}
839	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(std::size_t new_size, std::size_t min_size) noexcept((Checked == unchecked))
840	{
841	m_limbs = (std::min)(a: new_size, b: internal_limb_count);
842	detail::verify_new_size(m_limbs, min_size, checked_type());
843	}
844	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() noexcept((Checked == unchecked))
845	{
846	limb_pointer p = limbs();
847	detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count - 1], upper_limb_mask, checked_type());
848	p[internal_limb_count - 1] &= upper_limb_mask;
849	while ((m_limbs - 1) && !p[m_limbs - 1])
850	--m_limbs;
851	}
852
853	BOOST_MP_FORCEINLINE constexpr cpp_int_base() noexcept
854	: m_wrapper(limb_type(0u)),
855	m_limbs(1) {}
856	BOOST_MP_FORCEINLINE constexpr cpp_int_base(const cpp_int_base& o) noexcept
857	: m_wrapper(o.m_wrapper),
858	m_limbs(o.m_limbs) {}
859	// Defaulted functions:
860	//~cpp_int_base() noexcept {}
861	//
862	// These are deprecated in C++20 unless we make them explicit:
863	//
864	BOOST_MP_CXX14_CONSTEXPR cpp_int_base& operator=(const cpp_int_base&) = default;
865
866	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) noexcept
867	{
868	if (this != &o)
869	{
870	m_limbs = o.m_limbs;
871	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
872	if (BOOST_MP_IS_CONST_EVALUATED(m_limbs))
873	{
874	for (std::size_t i = 0; i < m_limbs; ++i)
875	limbs()[i] = o.limbs()[i];
876	}
877	else
878	#endif
879	std::memcpy(dest: limbs(), src: o.limbs(), n: o.size() * sizeof(limbs()[0]));
880	}
881	}
882
883	private:
884	void check_negate(const std::integral_constant<int, checked>&)
885	{
886	BOOST_MP_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned number."));
887	}
888	BOOST_MP_CXX14_CONSTEXPR void check_negate(const std::integral_constant<int, unchecked>&) {}
889
890	public:
891	BOOST_MP_CXX14_CONSTEXPR void negate() noexcept((Checked == unchecked))
892	{
893	// Not so much a negate as a complement - this gets called when subtraction
894	// would result in a "negative" number:
895	if ((m_limbs == 1) && (m_wrapper.m_data[0] == 0))
896	return; // negating zero is always zero, and always OK.
897	check_negate(checked_type());
898	std::size_t i = m_limbs;
899	for (; i < internal_limb_count; ++i)
900	m_wrapper.m_data[i] = 0;
901	m_limbs = internal_limb_count;
902	for (i = 0; i < internal_limb_count; ++i)
903	m_wrapper.m_data[i] = ~m_wrapper.m_data[i];
904	normalize();
905	eval_increment(static_cast<cpp_int_backend<MinBits, MinBits, unsigned_magnitude, Checked, void>&>(*this));
906	}
907	BOOST_MP_FORCEINLINE constexpr bool isneg() const noexcept
908	{
909	return false;
910	}
911	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) noexcept
912	{
913	for (std::size_t i = 0; i < (std::max)(size(), o.size()); ++i)
914	std_constexpr::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
915	std_constexpr::swap(m_limbs, o.m_limbs);
916	}
917
918	protected:
919	template <class A>
920	BOOST_MP_CXX14_CONSTEXPR void check_in_range(const A&) noexcept {}
921	};
922
923	template <std::size_t MinBits, cpp_int_check_type Checked>
924	constexpr std::size_t cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::limb_bits;
925	template <std::size_t MinBits, cpp_int_check_type Checked>
926	constexpr limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::max_limb_value;
927	template <std::size_t MinBits, cpp_int_check_type Checked>
928	constexpr limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::sign_bit_mask;
929	template <std::size_t MinBits, cpp_int_check_type Checked>
930	constexpr std::size_t cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::internal_limb_count;
931	//
932	// Traits classes to figure out a native type with N bits, these vary from boost::uint_t<N> only
933	// because some platforms have native integer types longer than long long, "really long long" anyone??
934	//
935	template <unsigned N, bool s>
936	struct trivial_limb_type_imp
937	{
938	using type = double_limb_type;
939	};
940
941	template <unsigned N>
942	struct trivial_limb_type_imp<N, true>
943	{
944	using type = typename boost::multiprecision::detail::uint_t<N>::least;
945	};
946
947	template <unsigned N>
948	struct trivial_limb_type : public trivial_limb_type_imp<N, N <= sizeof(long long) * CHAR_BIT>
949	{};
950	//
951	// Backend for fixed precision signed-magnitude type which will fit entirely inside a "double_limb_type":
952	//
953	template <std::size_t MinBits, cpp_int_check_type Checked>
954	struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, true>
955	{
956	using local_limb_type = typename trivial_limb_type<static_cast<unsigned>(MinBits)>::type;
957	using limb_pointer = local_limb_type*;
958	using const_limb_pointer = const local_limb_type*;
959	using checked_type = std::integral_constant<int, Checked>;
960
961	struct scoped_shared_storage
962	{
963	BOOST_MP_CXX14_CONSTEXPR scoped_shared_storage(const cpp_int_base&, std::size_t) {}
964	BOOST_MP_CXX14_CONSTEXPR void deallocate(std::size_t) {}
965	};
966
967	protected:
968	static constexpr std::size_t limb_bits = sizeof(local_limb_type) * CHAR_BIT;
969	static constexpr 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));
970
971	private:
972	local_limb_type m_data;
973	bool m_sign;
974
975	//
976	// Interface invariants:
977	//
978	static_assert(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?");
979
980	protected:
981	template <class T>
982	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!(!boost::multiprecision::detail::is_integral<T>::value || (std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= static_cast<int>(MinBits))))>::type
983	check_in_range(T val, const std::integral_constant<int, checked>&)
984	{
985	using common_type = typename std::common_type<typename boost::multiprecision::detail::make_unsigned<T>::type, local_limb_type>::type;
986
987	if (static_cast<common_type>(boost::multiprecision::detail::unsigned_abs(val)) > static_cast<common_type>(limb_mask))
988	BOOST_MP_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
989	}
990	template <class T>
991	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!(boost::multiprecision::detail::is_integral<T>::value || (std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= static_cast<int>(MinBits))))>::type
992	check_in_range(T val, const std::integral_constant<int, checked>&)
993	{
994	using std::abs;
995	using common_type = typename std::common_type<T, local_limb_type>::type;
996
997	if (static_cast<common_type>(abs(val)) > static_cast<common_type>(limb_mask))
998	BOOST_MP_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
999	}
1000	template <class T, int C>
1001	BOOST_MP_CXX14_CONSTEXPR void check_in_range(T, const std::integral_constant<int, C>&) noexcept {}
1002
1003	template <class T>
1004	BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<T>(), checked_type())))
1005	{
1006	check_in_range(val, checked_type());
1007	}
1008
1009	public:
1010	//
1011	// Direct construction:
1012	//
1013	template <class SI>
1014	BOOST_MP_FORCEINLINE constexpr cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1015	: m_data(i < 0 ? static_cast<local_limb_type>(static_cast<typename boost::multiprecision::detail::make_unsigned<SI>::type>(boost::multiprecision::detail::unsigned_abs(i)) & limb_mask) : static_cast<local_limb_type>(i & limb_mask)), m_sign(i < 0) {}
1016	template <class SI>
1017	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1018	: m_data(i < 0 ? (static_cast<local_limb_type>(static_cast<typename boost::multiprecision::detail::make_unsigned<SI>::type>(boost::multiprecision::detail::unsigned_abs(i)) & limb_mask)) : static_cast<local_limb_type>(i & limb_mask)), m_sign(i < 0)
1019	{
1020	check_in_range(i);
1021	}
1022	template <class UI>
1023	BOOST_MP_FORCEINLINE constexpr cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1024	: m_data(static_cast<local_limb_type>(i) & limb_mask),
1025	m_sign(false) {}
1026	template <class UI>
1027	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
1028	: m_data(static_cast<local_limb_type>(i) & limb_mask), m_sign(false) { check_in_range(i); }
1029	#if !(defined(__clang__) && defined(__MINGW32__))
1030	template <class F>
1031	BOOST_MP_FORCEINLINE constexpr cpp_int_base(F i, typename std::enable_if<std::is_floating_point<F>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1032	: m_data(static_cast<local_limb_type>(i < 0 ? -i : i) & limb_mask),
1033	m_sign(i < 0) {}
1034	template <class F>
1035	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(F i, typename std::enable_if<std::is_floating_point<F>::value && (Checked == checked)>::type const* = nullptr)
1036	: m_data(static_cast<local_limb_type>(i < 0 ? -i : i) & limb_mask), m_sign(i < 0) { check_in_range(i); }
1037	#else
1038	//
1039	// conversion from float to __int128 is broken on clang/mingw,
1040	// see: https://bugs.llvm.org/show_bug.cgi?id=48940
1041	// Since no floating point type has more than 64 bits of
1042	// precision, we can simply cast to an intermediate type to
1043	// solve the issue:
1044	//
1045	template <class F>
1046	BOOST_MP_FORCEINLINE constexpr cpp_int_base(F i, typename std::enable_if<std::is_floating_point<F>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1047	: m_data(static_cast<local_limb_type>(static_cast<std::uint64_t>(i < 0 ? -i : i)) & limb_mask),
1048	m_sign(i < 0) {}
1049	template <class F>
1050	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(F i, typename std::enable_if<std::is_floating_point<F>::value && (Checked == checked)>::type const* = nullptr)
1051	: m_data(static_cast<local_limb_type>(static_cast<std::uint64_t>(i < 0 ? -i : i)) & limb_mask), m_sign(i < 0) { check_in_range(i); }
1052	#endif
1053
1054	constexpr cpp_int_base(literals::detail::value_pack<>) noexcept
1055	: m_data(static_cast<local_limb_type>(0u)),
1056	m_sign(false)
1057	{}
1058	template <limb_type a>
1059	constexpr cpp_int_base(literals::detail::value_pack<a>) noexcept
1060	: m_data(static_cast<local_limb_type>(a)),
1061	m_sign(false) {}
1062	template <limb_type a, limb_type b>
1063	constexpr cpp_int_base(literals::detail::value_pack<a, b>) noexcept
1064	: m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)),
1065	m_sign(false) {}
1066	constexpr cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&) noexcept
1067	: m_data(a.m_data),
1068	m_sign(a.m_data ? !a.m_sign : false) {}
1069	//
1070	// These are deprecated in C++20 unless we make them explicit:
1071	//
1072	BOOST_MP_CXX14_CONSTEXPR cpp_int_base& operator=(const cpp_int_base&) = default;
1073
1074	explicit constexpr cpp_int_base(scoped_shared_storage&, std::size_t) noexcept : m_data(0), m_sign(false)
1075	{}
1076	//
1077	// Helper functions for getting at our internal data, and manipulating storage:
1078	//
1079	BOOST_MP_FORCEINLINE constexpr std::size_t size() const noexcept { return 1; }
1080	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() noexcept { return &m_data; }
1081	BOOST_MP_FORCEINLINE constexpr const_limb_pointer limbs() const noexcept { return &m_data; }
1082	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool sign() const noexcept { return m_sign; }
1083	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) noexcept
1084	{
1085	m_sign = b;
1086	// Check for zero value:
1087	if (m_sign && !m_data)
1088	{
1089	m_sign = false;
1090	}
1091	}
1092	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(std::size_t /* new_size */, std::size_t min_size)
1093	{
1094	detail::verify_new_size(2, min_size, checked_type());
1095	}
1096	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() noexcept((Checked == unchecked))
1097	{
1098	if (!m_data)
1099	m_sign = false; // zero is always unsigned
1100	detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
1101	m_data &= limb_mask;
1102	}
1103
1104	BOOST_MP_FORCEINLINE constexpr cpp_int_base() noexcept : m_data(0), m_sign(false) {}
1105	BOOST_MP_FORCEINLINE constexpr cpp_int_base(const cpp_int_base& o) noexcept
1106	: m_data(o.m_data),
1107	m_sign(o.m_sign) {}
1108	//~cpp_int_base() noexcept {}
1109	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) noexcept
1110	{
1111	m_data = o.m_data;
1112	m_sign = o.m_sign;
1113	}
1114	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate() noexcept
1115	{
1116	m_sign = !m_sign;
1117	// Check for zero value:
1118	if (m_data == 0)
1119	{
1120	m_sign = false;
1121	}
1122	}
1123	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool isneg() const noexcept
1124	{
1125	return m_sign;
1126	}
1127	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) noexcept
1128	{
1129	std_constexpr::swap(m_sign, o.m_sign);
1130	std_constexpr::swap(m_data, o.m_data);
1131	}
1132	};
1133	//
1134	// Backend for unsigned fixed precision (i.e. no allocator) type which will fit entirely inside a "double_limb_type":
1135	//
1136	template <std::size_t MinBits, cpp_int_check_type Checked>
1137	struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, true>
1138	{
1139	using local_limb_type = typename trivial_limb_type<static_cast<unsigned>(MinBits)>::type;
1140	using limb_pointer = local_limb_type* ;
1141	using const_limb_pointer = const local_limb_type* ;
1142
1143	struct scoped_shared_storage
1144	{
1145	BOOST_MP_CXX14_CONSTEXPR scoped_shared_storage(const cpp_int_base&, std::size_t) {}
1146	BOOST_MP_CXX14_CONSTEXPR void deallocate(std::size_t) {}
1147	};
1148
1149	private:
1150	static constexpr std::size_t limb_bits = sizeof(local_limb_type) * CHAR_BIT;
1151	static constexpr local_limb_type limb_mask = limb_bits != MinBits ? static_cast<local_limb_type>(static_cast<local_limb_type>(~local_limb_type(0)) >> (limb_bits - MinBits))
1152	: static_cast<local_limb_type>(~local_limb_type(0));
1153
1154	local_limb_type m_data;
1155
1156	using checked_type = std::integral_constant<int, Checked>;
1157
1158	//
1159	// Interface invariants:
1160	//
1161	static_assert(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?");
1162
1163	protected:
1164	template <class T>
1165	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if< !(std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= static_cast<int>(MinBits)))>::type
1166	check_in_range(T val, const std::integral_constant<int, checked>&, const std::integral_constant<bool, false>&)
1167	{
1168	using common_type = typename std::common_type<T, local_limb_type>::type;
1169
1170	if (static_cast<common_type>(val) > limb_mask)
1171	BOOST_MP_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
1172	}
1173	template <class T>
1174	BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val, const std::integral_constant<int, checked>&, const std::integral_constant<bool, true>&)
1175	{
1176	using common_type = typename std::common_type<T, local_limb_type>::type;
1177
1178	if (static_cast<common_type>(val) > static_cast<common_type>(limb_mask))
1179	BOOST_MP_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
1180	if (val < 0)
1181	BOOST_MP_THROW_EXCEPTION(std::range_error("The argument to an unsigned cpp_int constructor was negative."));
1182	}
1183	template <class T, int C, bool B>
1184	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void check_in_range(T, const std::integral_constant<int, C>&, const std::integral_constant<bool, B>&) noexcept {}
1185
1186	template <class T>
1187	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<T>(), checked_type(), boost::multiprecision::detail::is_signed<T>())))
1188	{
1189	check_in_range(val, checked_type(), boost::multiprecision::detail::is_signed<T>());
1190	}
1191
1192	public:
1193	//
1194	// Direct construction:
1195	//
1196	#ifdef __MSVC_RUNTIME_CHECKS
1197	template <class SI>
1198	BOOST_MP_FORCEINLINE constexpr cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1199	: m_data(i < 0 ? (1 + ~static_cast<local_limb_type>(-i & limb_mask)) & limb_mask : static_cast<local_limb_type>(i & limb_mask))
1200	{}
1201	template <class SI>
1202	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1203	: m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i & limb_mask) : static_cast<local_limb_type>(i & limb_mask)) { check_in_range(i); }
1204	template <class UI>
1205	BOOST_MP_FORCEINLINE constexpr cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1206	: m_data(static_cast<local_limb_type>(i& limb_mask)) {}
1207	template <class UI>
1208	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
1209	: m_data(static_cast<local_limb_type>(i & limb_mask)) { check_in_range(i); }
1210	#else
1211	template <class SI>
1212	BOOST_MP_FORCEINLINE constexpr cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1213	: m_data(i < 0 ? (1 + ~static_cast<local_limb_type>(-i)) & limb_mask : static_cast<local_limb_type>(i) & limb_mask)
1214	{}
1215	template <class SI>
1216	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1217	: m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)) { check_in_range(i); }
1218	template <class UI>
1219	BOOST_MP_FORCEINLINE constexpr cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == unchecked)>::type const* = nullptr) noexcept
1220	: m_data(static_cast<local_limb_type>(i) & limb_mask) {}
1221	template <class UI>
1222	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (Checked == checked)>::type const* = nullptr) noexcept(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
1223	: m_data(static_cast<local_limb_type>(i)) { check_in_range(i); }
1224	#endif
1225	template <class F>
1226	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(F i, typename std::enable_if<std::is_floating_point<F>::value >::type const* = nullptr) noexcept((Checked == unchecked))
1227	: m_data(static_cast<local_limb_type>(i < 0 ? -i : i) & limb_mask)
1228	{
1229	check_in_range(i);
1230	if (i < 0)
1231	negate();
1232	}
1233	constexpr cpp_int_base(literals::detail::value_pack<>) noexcept
1234	: m_data(static_cast<local_limb_type>(0u))
1235	{}
1236	template <limb_type a>
1237	constexpr cpp_int_base(literals::detail::value_pack<a>) noexcept
1238	: m_data(static_cast<local_limb_type>(a)) {}
1239	template <limb_type a, limb_type b>
1240	constexpr cpp_int_base(literals::detail::value_pack<a, b>) noexcept
1241	: m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)) {}
1242	//
1243	// These are deprecated in C++20 unless we make them explicit:
1244	//
1245	BOOST_MP_CXX14_CONSTEXPR cpp_int_base& operator=(const cpp_int_base&) = default;
1246
1247	explicit constexpr cpp_int_base(scoped_shared_storage&, std::size_t) noexcept : m_data(0)
1248	{}
1249	//
1250	// Helper functions for getting at our internal data, and manipulating storage:
1251	//
1252	BOOST_MP_FORCEINLINE constexpr std::size_t size() const noexcept { return 1; }
1253	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() noexcept { return &m_data; }
1254	BOOST_MP_FORCEINLINE constexpr const_limb_pointer limbs() const noexcept { return &m_data; }
1255	BOOST_MP_FORCEINLINE constexpr bool sign() const noexcept { return false; }
1256	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) noexcept((Checked == unchecked))
1257	{
1258	if (b)
1259	negate();
1260	}
1261	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(unsigned, std::size_t min_size)
1262	{
1263	detail::verify_new_size(2, min_size, checked_type());
1264	}
1265	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() noexcept((Checked == unchecked))
1266	{
1267	detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
1268	m_data &= limb_mask;
1269	}
1270
1271	BOOST_MP_FORCEINLINE constexpr cpp_int_base() noexcept : m_data(0) {}
1272	BOOST_MP_FORCEINLINE constexpr cpp_int_base(const cpp_int_base& o) noexcept
1273	: m_data(o.m_data) {}
1274	//~cpp_int_base() noexcept {}
1275	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) noexcept
1276	{
1277	m_data = o.m_data;
1278	}
1279	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate()
1280	#if !defined(BOOST_NO_CXX17_IF_CONSTEXPR)
1281	noexcept((Checked == unchecked))
1282	#endif
1283	{
1284	BOOST_IF_CONSTEXPR(Checked == checked)
1285	{
1286	BOOST_MP_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned type."));
1287	}
1288	m_data = ~m_data;
1289	++m_data;
1290	}
1291	BOOST_MP_FORCEINLINE constexpr bool isneg() const noexcept
1292	{
1293	return false;
1294	}
1295	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) noexcept
1296	{
1297	std_constexpr::swap(m_data, o.m_data);
1298	}
1299	};
1300	//
1301	// Traits class, lets us know whether type T can be directly converted to the base type,
1302	// used to enable/disable constructors etc:
1303	//
1304	template <class Arg, class Base>
1305	struct is_allowed_cpp_int_base_conversion : public std::conditional<
1306	std::is_same<Arg, limb_type>::value || std::is_same<Arg, signed_limb_type>::value
1307	#if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
1308	|| std::is_same<Arg, double_limb_type>::value || std::is_same<Arg, signed_double_limb_type>::value
1309	#endif
1310	|| literals::detail::is_value_pack<Arg>::value || (is_trivial_cpp_int<Base>::value && boost::multiprecision::detail::is_arithmetic<Arg>::value),
1311	std::integral_constant<bool, true>,
1312	std::integral_constant<bool, false>>::type
1313	{};
1314	//
1315	// Now the actual backend, normalising parameters passed to the base class:
1316	//
1317	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
1318	struct cpp_int_backend
1319	: public cpp_int_base<
1320	min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1321	max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1322	SignType,
1323	Checked,
1324	Allocator,
1325	is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>
1326	{
1327	using self_type = cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>;
1328	using base_type = cpp_int_base<
1329	min_precision<self_type>::value,
1330	max_precision<self_type>::value,
1331	SignType,
1332	Checked,
1333	Allocator,
1334	is_trivial_cpp_int<self_type>::value>;
1335	using trivial_tag = std::integral_constant<bool, is_trivial_cpp_int<self_type>::value>;
1336
1337	public:
1338	using signed_types = typename std::conditional<
1339	is_trivial_cpp_int<self_type>::value,
1340	std::tuple<
1341	signed char, short, int, long,
1342	long long, signed_double_limb_type>,
1343	std::tuple<signed_limb_type, signed_double_limb_type> >::type;
1344	using unsigned_types = typename std::conditional<
1345	is_trivial_cpp_int<self_type>::value,
1346	std::tuple<unsigned char, unsigned short, unsigned,
1347	unsigned long, unsigned long long, double_limb_type>,
1348	std::tuple<limb_type, double_limb_type> >::type;
1349	using float_types = typename std::conditional<
1350	is_trivial_cpp_int<self_type>::value,
1351	std::tuple<float, double, long double>,
1352	std::tuple<long double> >::type;
1353	using checked_type = std::integral_constant<int, Checked> ;
1354
1355	BOOST_MP_FORCEINLINE constexpr cpp_int_backend() noexcept {}
1356	BOOST_MP_FORCEINLINE constexpr cpp_int_backend(const cpp_int_backend& o) noexcept(std::is_void<Allocator>::value) : base_type(o) {}
1357	// rvalue copy:
1358	BOOST_MP_FORCEINLINE constexpr cpp_int_backend(cpp_int_backend&& o) noexcept
1359	: base_type(static_cast<base_type&&>(o))
1360	{}
1361	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2>
1362	BOOST_MP_FORCEINLINE BOOST_CXX14_CONSTEXPR cpp_int_backend(cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2>&& o, typename std::enable_if<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2>, self_type>::value>::type* = nullptr) noexcept
1363	{
1364	*this = static_cast<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2>&&>(o);
1365	}
1366	//
1367	// Direct construction from arithmetic type:
1368	//
1369	template <class Arg>
1370	BOOST_MP_FORCEINLINE constexpr cpp_int_backend(Arg i, typename std::enable_if<is_allowed_cpp_int_base_conversion<Arg, base_type>::value>::type const* = nullptr) noexcept(noexcept(base_type(std::declval<Arg>())))
1371	: base_type(i) {}
1372	//
1373	// Aliasing constructor: the result will alias the memory referenced, unless
1374	// we have fixed precision and storage, in which case we copy the memory:
1375	//
1376	explicit constexpr cpp_int_backend(limb_type* data, std::size_t offset, std::size_t len) noexcept
1377	: base_type(data, offset, len) {}
1378	explicit cpp_int_backend(const limb_type* data, std::size_t offset, std::size_t len) noexcept
1379	: base_type(data, offset, len) { this->normalize(); }
1380	explicit constexpr cpp_int_backend(typename base_type::scoped_shared_storage& data, std::size_t len) noexcept
1381	: base_type(data, len) {}
1382
1383	private:
1384	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1385	BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, std::true_type const&, std::true_type const&)
1386	{
1387	// Assigning trivial type to trivial type:
1388	this->check_in_range(*other.limbs());
1389	*this->limbs() = static_cast<typename self_type::local_limb_type>(*other.limbs());
1390	this->sign(other.sign());
1391	this->normalize();
1392	}
1393	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1394	BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, std::true_type const&, std::false_type const&)
1395	{
1396	// non-trivial to trivial narrowing conversion:
1397	double_limb_type v = *other.limbs();
1398	if (other.size() > 1)
1399	{
1400	v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
1401	BOOST_IF_CONSTEXPR(Checked == checked)
1402	{
1403	if (other.size() > 2)
1404	{
1405	BOOST_MP_THROW_EXCEPTION(std::range_error("Assignment of a cpp_int that is out of range for the target type."));
1406	}
1407	}
1408	}
1409	*this = v;
1410	this->sign(other.sign());
1411	this->normalize();
1412	}
1413	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1414	BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, std::false_type const&, std::true_type const&)
1415	{
1416	// trivial to non-trivial, treat the trivial argument as if it were an unsigned arithmetic type, then set the sign afterwards:
1417	*this = static_cast<
1418	typename boost::multiprecision::detail::canonical<
1419	typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type,
1420	cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::type>(*other.limbs());
1421	this->sign(other.sign());
1422	}
1423	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1424	BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, std::false_type const&, std::false_type const&)
1425	{
1426	// regular non-trivial to non-trivial assign:
1427	this->resize(other.size(), other.size());
1428
1429	#if !defined(BOOST_MP_HAS_IS_CONSTANT_EVALUATED) && !defined(BOOST_MP_HAS_BUILTIN_IS_CONSTANT_EVALUATED) && !defined(BOOST_NO_CXX14_CONSTEXPR)
1430	std::size_t count = (std::min)(other.size(), this->size());
1431	for (std::size_t i = 0; i < count; ++i)
1432	this->limbs()[i] = other.limbs()[i];
1433	#else
1434	#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
1435	if (BOOST_MP_IS_CONST_EVALUATED(other.size()))
1436	{
1437	std::size_t count = (std::min)(other.size(), this->size());
1438	for (std::size_t i = 0; i < count; ++i)
1439	this->limbs()[i] = other.limbs()[i];
1440	}
1441	else
1442	#endif
1443	{
1444	static_assert(sizeof(other.limbs()[0]) == sizeof(this->limbs()[0]), "This method requires equal limb sizes");
1445	std::memcpy(dest: this->limbs(), src: other.limbs(), n: (std::min)(other.size() * sizeof(other.limbs()[0]), this->size() * sizeof(this->limbs()[0])));
1446	}
1447	#endif
1448	this->sign(other.sign());
1449	this->normalize();
1450	}
1451
1452	public:
1453	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1454	BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(
1455	const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1456	typename std::enable_if<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = nullptr)
1457	: base_type()
1458	{
1459	do_assign(
1460	other,
1461	std::integral_constant<bool, is_trivial_cpp_int<self_type>::value>(),
1462	std::integral_constant<bool, is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1463	}
1464	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1465	explicit BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(
1466	const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1467	typename std::enable_if< !(is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value)>::type* = nullptr)
1468	: base_type()
1469	{
1470	do_assign(
1471	other,
1472	std::integral_constant<bool, is_trivial_cpp_int<self_type>::value>(),
1473	std::integral_constant<bool, is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1474	}
1475	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1476	BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(
1477	const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other)
1478	{
1479	do_assign(
1480	other,
1481	std::integral_constant<bool, is_trivial_cpp_int<self_type>::value>(),
1482	std::integral_constant<bool, is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1483	return *this;
1484	}
1485	constexpr cpp_int_backend(const cpp_int_backend& a, const literals::detail::negate_tag& tag)
1486	: base_type(static_cast<const base_type&>(a), tag)
1487	{}
1488
1489	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(const cpp_int_backend& o) noexcept(noexcept(std::declval<cpp_int_backend>().assign(std::declval<const cpp_int_backend&>())))
1490	{
1491	this->assign(o);
1492	return *this;
1493	}
1494	// rvalue copy:
1495	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(cpp_int_backend&& o) noexcept(noexcept(std::declval<base_type&>() = std::declval<base_type>()))
1496	{
1497	*static_cast<base_type*>(this) = static_cast<base_type&&>(o);
1498	return *this;
1499	}
1500	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2>
1501	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<((MaxBits2 <= MaxBits) || (MaxBits == 0)) && !std::is_void<Allocator>::value, cpp_int_backend&>::type operator=(cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator>&& o) noexcept
1502	{
1503	*static_cast<base_type*>(this) = static_cast<typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2>::base_type&&>(o);
1504	return *this;
1505	}
1506
1507	template <class A>
1508	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
1509	boost::multiprecision::detail::is_unsigned<A>::value
1510	&& trivial_tag::value, cpp_int_backend&>::type
1511	operator=(const A& val)
1512	noexcept(noexcept(std::declval<cpp_int_backend>().check_in_range(std::declval<A>())))
1513	{
1514	this->check_in_range(val);
1515	*this->limbs() = static_cast<typename self_type::local_limb_type>(val);
1516	this->sign(false);
1517	this->normalize();
1518	return *this;
1519	}
1520	template <class A>
1521	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
1522	!(boost::multiprecision::detail::is_unsigned<A>::value || !boost::multiprecision::detail::is_integral<A>::value)
1523	&& trivial_tag::value, cpp_int_backend&>::type
1524	operator=(const A& val)
1525	noexcept(noexcept(std::declval<cpp_int_backend>().check_in_range(std::declval<A>())) && noexcept(std::declval<cpp_int_backend>().sign(true)))
1526	{
1527	this->check_in_range(val);
1528	*this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(boost::multiprecision::detail::unsigned_abs(val)) : static_cast<typename self_type::local_limb_type>(val);
1529	this->sign(val < 0);
1530	this->normalize();
1531	return *this;
1532	}
1533	template <class A>
1534	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
1535	std::is_convertible<A, limb_type>::value
1536	&& !boost::multiprecision::detail::is_integral<A>::value
1537	&& trivial_tag::value, cpp_int_backend&>::type
1538	operator=(const A& val)
1539	{
1540	this->check_in_range(val);
1541	*this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(boost::multiprecision::detail::abs(val)) : static_cast<typename self_type::local_limb_type>(val);
1542	this->sign(val < 0);
1543	this->normalize();
1544	return *this;
1545	}
1546	template <class A>
1547	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
1548	std::is_same<A, limb_type>::value && !trivial_tag::value, cpp_int_backend&>::type
1549	operator=(A i) noexcept
1550	{
1551	this->resize(1, 1);
1552	*this->limbs() = i;
1553	this->sign(false);
1554	return *this;
1555	}
1556	template <class A>
1557	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if <
1558	std::is_same<A, signed_limb_type>::value && !trivial_tag::value, cpp_int_backend&>::type
1559	operator=(A i) noexcept(noexcept(std::declval<cpp_int_backend>().sign(true)))
1560	{
1561	this->resize(1, 1);
1562	*this->limbs() = static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(i));
1563	this->sign(i < 0);
1564	return *this;
1565	}
1566	template <class A>
1567	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if <
1568	std::is_same<A, double_limb_type>::value && !trivial_tag::value, cpp_int_backend&>::type
1569	operator=(A i) noexcept
1570	{
1571	static_assert(sizeof(i) == 2 * sizeof(limb_type), "Failed integer size check");
1572	static_assert(base_type::internal_limb_count >= 2, "Failed internal limb count");
1573	typename base_type::limb_pointer p = this->limbs();
1574	#ifdef __MSVC_RUNTIME_CHECKS
1575	*p = static_cast<limb_type>(i & ~static_cast<limb_type>(0));
1576	#else
1577	*p = static_cast<limb_type>(i);
1578	#endif
1579	p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
1580	this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1581	this->sign(false);
1582	return *this;
1583	}
1584	template <class A>
1585	BOOST_MP_CXX14_CONSTEXPR typename std::enable_if <
1586	std::is_same<A, signed_double_limb_type>::value && !trivial_tag::value, cpp_int_backend&>::type
1587	operator=(A i) noexcept(noexcept(std::declval<cpp_int_backend>().sign(true)))
1588	{
1589	static_assert(sizeof(i) == 2 * sizeof(limb_type), "double limb type size check failed");
1590	static_assert(base_type::internal_limb_count >= 2, "Failed internal limb count check");
1591	bool s = false;
1592	if (i < 0)
1593	s = true;
1594	double_limb_type ui = static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i));
1595	typename base_type::limb_pointer p = this->limbs();
1596	#ifdef __MSVC_RUNTIME_CHECKS
1597	*p = static_cast<limb_type>(ui & ~static_cast<limb_type>(0));
1598	#else
1599	*p = static_cast<limb_type>(ui);
1600	#endif
1601	p[1] = static_cast<limb_type>(ui >> base_type::limb_bits);
1602	this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1603	this->sign(s);
1604	return *this;
1605	}
1606	private:
1607	template <class F>
1608	BOOST_MP_CXX14_CONSTEXPR void do_assign_float(F a)
1609	{
1610	using default_ops::eval_add;
1611	using default_ops::eval_subtract;
1612	BOOST_MP_FLOAT128_USING using std::floor; using std::frexp; using std::ldexp;
1613
1614	if (a < 0)
1615	{
1616	do_assign_float(-a);
1617	this->sign(true);
1618	return;
1619	}
1620
1621	if (a == 0)
1622	{
1623	*this = static_cast<limb_type>(0u);
1624	}
1625
1626	if (a == 1)
1627	{
1628	*this = static_cast<limb_type>(1u);
1629	}
1630
1631	if (!BOOST_MP_ISFINITE(a))
1632	{
1633	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Cannot convert a non-finite number to an integer."));
1634	}
1635
1636	int e = 0;
1637	F f(0), term(0);
1638	*this = static_cast<limb_type>(0u);
1639
1640	f = frexp(a, &e);
1641
1642	#if !(defined(__clang__) && (__clang_major__ <= 7))
1643	constexpr limb_type shift = std::numeric_limits<limb_type>::digits;
1644	#else
1645	// clang 7 has an issue converting long double to unsigned long long in
1646	// release mode (bits get dropped, conversion appears to go via float)
1647	// Never extract more than double bits at a time:
1648	constexpr limb_type shift = std::numeric_limits<limb_type>::digits > std::numeric_limits<double>::digits
1649	? std::numeric_limits<double>::digits : std::numeric_limits<limb_type>::digits;
1650	#endif
1651
1652	while (f != static_cast<F>(0.0f))
1653	{
1654	// extract int sized bits from f:
1655	f = ldexp(f, shift);
1656	term = floor(f);
1657	e = e - static_cast<int>(shift);
1658	eval_left_shift(*this, shift);
1659	#if !(defined(__clang__) && (__clang_major__ <= 7))
1660	if (term > 0)
1661	eval_add(*this, static_cast<limb_type>(term));
1662	else
1663	eval_subtract(*this, static_cast<limb_type>(-term));
1664	#else
1665	// clang 7 requires extra cast to double to avoid buggy code generation:
1666	if (term > 0)
1667	eval_add(*this, static_cast<limb_type>(static_cast<double>(term)));
1668	else
1669	eval_subtract(*this, static_cast<limb_type>(static_cast<double>(-term)));
1670	#endif
1671	f -= term;
1672	}
1673	if (e > 0)
1674	eval_left_shift(*this, static_cast<unsigned int>(e));
1675	else if (e < 0)
1676	eval_right_shift(*this, static_cast<unsigned int>(-e));
1677	}
1678	public:
1679	template <class A>
1680	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if <
1681	std::is_floating_point<A>::value && !trivial_tag::value, cpp_int_backend&>::type
1682	operator=(A a)
1683	{
1684	do_assign_float(a);
1685	return *this;
1686	}
1687
1688	private:
1689	void do_assign_string(const char* s, const std::integral_constant<bool, true>&)
1690	{
1691	std::size_t n = s ? std::strlen(s: s) : 0;
1692	*this = 0;
1693	unsigned radix = 10;
1694	bool isneg = false;
1695	if (n && (*s == '-'))
1696	{
1697	--n;
1698	++s;
1699	isneg = true;
1700	}
1701	if (n && (*s == '0'))
1702	{
1703	if ((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1704	{
1705	radix = 16;
1706	s += 2;
1707	n -= 2;
1708	}
1709	else
1710	{
1711	radix = 8;
1712	n -= 1;
1713	}
1714	}
1715	if (n)
1716	{
1717	unsigned val;
1718	while (*s)
1719	{
1720	if (*s >= '0' && *s <= '9')
1721	val = static_cast<unsigned>(*s - '0');
1722	else if (*s >= 'a' && *s <= 'f')
1723	val = 10u + static_cast<unsigned>(*s - 'a');
1724	else if (*s >= 'A' && *s <= 'F')
1725	val = 10u + static_cast<unsigned>(*s - 'A');
1726	else
1727	val = radix + 1u;
1728	if (val >= radix)
1729	{
1730	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1731	}
1732	*this->limbs() = detail::checked_multiply(*this->limbs(), static_cast<typename base_type::local_limb_type>(radix), checked_type());
1733	*this->limbs() = detail::checked_add(*this->limbs(), static_cast<typename base_type::local_limb_type>(val), checked_type());
1734	++s;
1735	}
1736	}
1737	if (isneg)
1738	this->negate();
1739	}
1740	void do_assign_string(const char* s, const std::integral_constant<bool, false>&)
1741	{
1742	using default_ops::eval_add;
1743	using default_ops::eval_multiply;
1744	std::size_t n = s ? std::strlen(s: s) : 0;
1745	*this = static_cast<limb_type>(0u);
1746	unsigned radix = 10;
1747	bool isneg = false;
1748	if (n && (*s == '-'))
1749	{
1750	--n;
1751	++s;
1752	isneg = true;
1753	}
1754	if (n && (*s == '0'))
1755	{
1756	if ((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1757	{
1758	radix = 16;
1759	s += 2;
1760	n -= 2;
1761	}
1762	else
1763	{
1764	radix = 8;
1765	n -= 1;
1766	}
1767	}
1768	//
1769	// Exception guarantee: create the result in stack variable "result"
1770	// then do a swap at the end. In the event of a throw, *this will
1771	// be left unchanged.
1772	//
1773	cpp_int_backend result;
1774	if (n)
1775	{
1776	if (radix == 16)
1777	{
1778	while (*s == '0')
1779	++s;
1780	std::size_t bitcount = 4 * std::strlen(s: s);
1781	limb_type val;
1782	std::size_t limb, shift;
1783	if (bitcount > 4)
1784	bitcount -= 4;
1785	else
1786	bitcount = 0;
1787	std::size_t newsize = bitcount / (sizeof(limb_type) * CHAR_BIT) + 1;
1788	result.resize(static_cast<unsigned>(newsize), static_cast<unsigned>(newsize)); // will throw if this is a checked integer that cannot be resized
1789	std::memset(s: result.limbs(), c: 0, n: result.size() * sizeof(limb_type));
1790	while (*s)
1791	{
1792	if (*s >= '0' && *s <= '9')
1793	val = static_cast<unsigned>(*s - '0');
1794	else if (*s >= 'a' && *s <= 'f')
1795	val = 10u + static_cast<unsigned>(*s - 'a');
1796	else if (*s >= 'A' && *s <= 'F')
1797	val = 10u + static_cast<unsigned>(*s - 'A');
1798	else
1799	{
1800	#if defined(BOOST_NO_EXCEPTIONS)
1801	val = static_cast<unsigned>('0');
1802	#endif
1803
1804	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1805	}
1806	limb = bitcount / (sizeof(limb_type) * CHAR_BIT);
1807	shift = bitcount % (sizeof(limb_type) * CHAR_BIT);
1808	val <<= shift;
1809	if (result.size() > limb)
1810	{
1811	result.limbs()[limb] |= val;
1812	}
1813	++s;
1814	bitcount -= 4;
1815	}
1816	result.normalize();
1817	}
1818	else if (radix == 8)
1819	{
1820	while (*s == '0')
1821	++s;
1822	std::size_t bitcount = 3 * std::strlen(s: s);
1823	limb_type val;
1824	std::size_t limb, shift;
1825	if (bitcount > 3)
1826	bitcount -= 3;
1827	else
1828	bitcount = 0;
1829	std::size_t newsize = bitcount / (sizeof(limb_type) * CHAR_BIT) + 1;
1830	result.resize(static_cast<unsigned>(newsize), static_cast<unsigned>(newsize)); // will throw if this is a checked integer that cannot be resized
1831	std::memset(s: result.limbs(), c: 0, n: result.size() * sizeof(limb_type));
1832	while (*s)
1833	{
1834	if (*s >= '0' && *s <= '7')
1835	val = static_cast<unsigned>(*s - '0');
1836	else
1837	{
1838	#if defined(BOOST_NO_EXCEPTIONS)
1839	val = static_cast<unsigned>('0');
1840	#endif
1841
1842	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1843	}
1844	limb = bitcount / (sizeof(limb_type) * CHAR_BIT);
1845	shift = bitcount % (sizeof(limb_type) * CHAR_BIT);
1846	if (result.size() > limb)
1847	{
1848	result.limbs()[limb] |= (val << shift);
1849	if (shift > sizeof(limb_type) * CHAR_BIT - 3)
1850	{
1851	// Deal with the bits in val that overflow into the next limb:
1852	val >>= (sizeof(limb_type) * CHAR_BIT - shift);
1853	if (val)
1854	{
1855	// If this is the most-significant-limb, we may need to allocate an extra one for the overflow:
1856	if (limb + 1 == newsize)
1857	{
1858	result.resize(static_cast<unsigned>(newsize + 1), static_cast<unsigned>(newsize + 1));
1859	result.limbs()[limb + 1] = 0;
1860	}
1861	if (result.size() > limb + 1)
1862	{
1863	result.limbs()[limb + 1] |= val;
1864	}
1865	}
1866	}
1867	}
1868	++s;
1869	bitcount -= 3;
1870	}
1871	result.normalize();
1872	}
1873	else
1874	{
1875	// Base 10, we extract blocks of size 10^9 at a time, that way
1876	// the number of multiplications is kept to a minimum:
1877	limb_type block_mult = max_block_10;
1878	while (*s)
1879	{
1880	limb_type block = 0;
1881	for (unsigned i = 0; i < digits_per_block_10; ++i)
1882	{
1883	limb_type val;
1884	if (*s >= '0' && *s <= '9')
1885	val = static_cast<limb_type>(*s - '0');
1886	else
1887	{
1888	#if defined(BOOST_NO_EXCEPTIONS)
1889	val = static_cast<unsigned>('0');
1890	#endif
1891
1892	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input."));
1893	}
1894	block *= 10;
1895	block += val;
1896	if (!*++s)
1897	{
1898	block_mult = block_multiplier(count: i);
1899	break;
1900	}
1901	}
1902	eval_multiply(result, block_mult);
1903	eval_add(result, block);
1904	}
1905	}
1906	}
1907	if (isneg)
1908	result.negate();
1909	result.swap(*this);
1910	}
1911
1912	public:
1913	cpp_int_backend& operator=(const char* s)
1914	{
1915	do_assign_string(s, trivial_tag());
1916	return *this;
1917	}
1918	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void swap(cpp_int_backend& o) noexcept
1919	{
1920	this->do_swap(o);
1921	}
1922
1923	private:
1924	std::string do_get_trivial_string(std::ios_base::fmtflags f, const std::integral_constant<bool, false>&) const
1925	{
1926	using io_type = typename std::conditional<sizeof(typename base_type::local_limb_type) == 1, unsigned, typename base_type::local_limb_type>::type;
1927	if (this->sign() && (((f & std::ios_base::hex) == std::ios_base::hex) || ((f & std::ios_base::oct) == std::ios_base::oct)))
1928	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1929	std::stringstream ss;
1930	ss.flags(fmtfl: f & ~std::ios_base::showpos);
1931	ss << static_cast<io_type>(*this->limbs());
1932	std::string result;
1933	if (this->sign())
1934	result += '-';
1935	else if (f & std::ios_base::showpos)
1936	result += '+';
1937	result += ss.str();
1938	return result;
1939	}
1940	std::string do_get_trivial_string(std::ios_base::fmtflags f, const std::integral_constant<bool, true>&) const
1941	{
1942	// Even though we have only one limb, we can't do IO on it :-(
1943	int base = 10;
1944	if ((f & std::ios_base::oct) == std::ios_base::oct)
1945	base = 8;
1946	else if ((f & std::ios_base::hex) == std::ios_base::hex)
1947	base = 16;
1948	std::string result;
1949
1950	std::size_t Bits = sizeof(typename base_type::local_limb_type) * CHAR_BIT;
1951
1952	if (base == 8 || base == 16)
1953	{
1954	if (this->sign())
1955	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1956	limb_type shift = base == 8 ? 3 : 4;
1957	limb_type mask = static_cast<limb_type>((1u << shift) - 1);
1958	typename base_type::local_limb_type v = *this->limbs();
1959	result.assign(n: Bits / shift + (Bits % shift ? 1 : 0), c: '0');
1960	std::string::difference_type pos = static_cast<std::string::difference_type>(result.size() - 1u);
1961	char letter_a = f & std::ios_base::uppercase ? 'A' : 'a';
1962	for (std::size_t i = 0; i < Bits / shift; ++i)
1963	{
1964	char c = static_cast<char>('0' + static_cast<char>(v & mask));
1965	if (c > '9')
1966	c = static_cast<char>(c + letter_a - '9' - 1);
1967	result[static_cast<std::size_t>(pos)] = c;
1968	--pos;
1969	v >>= shift;
1970	}
1971	if (Bits % shift)
1972	{
1973	mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
1974	char c = static_cast<char>('0' + static_cast<char>(v & mask));
1975	if (c > '9')
1976	c = static_cast<char>(c + letter_a - '9');
1977	result[static_cast<std::size_t>(pos)] = c;
1978	}
1979	//
1980	// Get rid of leading zeros:
1981	//
1982	std::string::size_type n = result.find_first_not_of(c: '0');
1983	if (!result.empty() && (n == std::string::npos))
1984	n = result.size() - 1;
1985	result.erase(pos: 0, n: n);
1986	if (f & std::ios_base::showbase)
1987	{
1988	const char* pp = base == 8 ? "0" : (f & std::ios_base::uppercase) ? "0X" : "0x";
1989	result.insert(pos: static_cast<std::string::size_type>(0), s: pp);
1990	}
1991	}
1992	else
1993	{
1994	result.assign(n: Bits / 3 + 1, c: '0');
1995	std::string::difference_type pos = static_cast<std::string::difference_type>(result.size() - 1u);
1996	typename base_type::local_limb_type v(*this->limbs());
1997	bool neg = false;
1998	if (this->sign())
1999	{
2000	neg = true;
2001	}
2002	while (v)
2003	{
2004	result[static_cast<std::string::size_type>(pos)] = static_cast<char>(static_cast<char>(v % 10) + '0');
2005	--pos;
2006	v /= 10;
2007	}
2008	std::string::size_type n = result.find_first_not_of(c: '0');
2009	result.erase(pos: 0, n: n);
2010	if (result.empty())
2011	result = "0";
2012	if (neg)
2013	result.insert(pos: static_cast<std::string::size_type>(0), n: 1, c: '-');
2014	else if (f & std::ios_base::showpos)
2015	result.insert(pos: static_cast<std::string::size_type>(0), n: 1, c: '+');
2016	}
2017	return result;
2018	}
2019	std::string do_get_string(std::ios_base::fmtflags f, const std::integral_constant<bool, true>&) const
2020	{
2021	#ifdef BOOST_MP_NO_DOUBLE_LIMB_TYPE_IO
2022	return do_get_trivial_string(f, std::integral_constant<bool, std::is_same<typename base_type::local_limb_type, double_limb_type>::value>());
2023	#else
2024	return do_get_trivial_string(f, std::integral_constant<bool, false>());
2025	#endif
2026	}
2027	std::string do_get_string(std::ios_base::fmtflags f, const std::integral_constant<bool, false>&) const
2028	{
2029	using default_ops::eval_get_sign;
2030	int base = 10;
2031	if ((f & std::ios_base::oct) == std::ios_base::oct)
2032	base = 8;
2033	else if ((f & std::ios_base::hex) == std::ios_base::hex)
2034	base = 16;
2035	std::string result;
2036
2037	std::size_t Bits = this->size() * base_type::limb_bits;
2038
2039	if (base == 8 || base == 16)
2040	{
2041	if (this->sign())
2042	BOOST_MP_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
2043	limb_type shift = base == 8 ? 3 : 4;
2044	limb_type mask = static_cast<limb_type>((1u << shift) - 1);
2045	cpp_int_backend t(*this);
2046	result.assign(n: Bits / shift + ((Bits % shift) ? 1 : 0), c: '0');
2047	std::string::difference_type pos = static_cast<std::string::difference_type>(result.size() - 1u);
2048	char letter_a = f & std::ios_base::uppercase ? 'A' : 'a';
2049	for (std::size_t i = 0; i < Bits / shift; ++i)
2050	{
2051	char c = static_cast<char>('0' + static_cast<char>(t.limbs()[0] & mask));
2052	if (c > '9')
2053	c = static_cast<char>(c + letter_a - '9' - 1);
2054	result[static_cast<std::size_t>(pos)] = c;
2055	--pos;
2056	eval_right_shift(t, shift);
2057	}
2058	if (Bits % shift)
2059	{
2060	mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
2061	char c = static_cast<char>('0' + static_cast<char>(t.limbs()[0] & mask));
2062	if (c > '9')
2063	c = static_cast<char>(c + letter_a - '9');
2064	result[static_cast<std::size_t>(pos)] = c;
2065	}
2066	//
2067	// Get rid of leading zeros:
2068	//
2069	std::string::size_type n = result.find_first_not_of(c: '0');
2070	if (!result.empty() && (n == std::string::npos))
2071	n = result.size() - 1;
2072	result.erase(pos: 0, n: n);
2073	if (f & std::ios_base::showbase)
2074	{
2075	const char* pp = base == 8 ? "0" : (f & std::ios_base::uppercase) ? "0X" : "0x";
2076	result.insert(pos: static_cast<std::string::size_type>(0), s: pp);
2077	}
2078	}
2079	else
2080	{
2081	result.assign(n: Bits / 3 + 1, c: '0');
2082	std::string::difference_type pos = static_cast<std::string::difference_type>(result.size() - 1u);
2083	cpp_int_backend t(*this);
2084	cpp_int_backend r;
2085	bool neg = false;
2086	if (t.sign())
2087	{
2088	t.negate();
2089	neg = true;
2090	}
2091	if (this->size() == 1)
2092	{
2093	result = std::to_string(t.limbs()[0]);
2094	}
2095	else
2096	{
2097	cpp_int_backend block10;
2098	block10 = max_block_10;
2099	while (eval_get_sign(t) != 0)
2100	{
2101	cpp_int_backend t2;
2102	divide_unsigned_helper(&t2, t, block10, r);
2103	t = t2;
2104	limb_type v = r.limbs()[0];
2105	for (std::size_t i = 0; i < digits_per_block_10; ++i)
2106	{
2107	char c = static_cast<char>('0' + static_cast<char>(v % 10));
2108	v /= 10;
2109	result[static_cast<std::size_t>(pos)] = c;
2110	if (pos-- == 0u)
2111	break;
2112	}
2113	}
2114	}
2115	std::string::size_type n = result.find_first_not_of(c: '0');
2116	result.erase(pos: 0, n: n);
2117	if (result.empty())
2118	result = std::string(static_cast<std::size_t>(1u), '0');
2119	if (neg)
2120	result.insert(pos: static_cast<std::string::size_type>(0), n: 1, c: '-');
2121	else if (f & std::ios_base::showpos)
2122	result.insert(pos: static_cast<std::string::size_type>(0), n: 1, c: '+');
2123	}
2124	return result;
2125	}
2126
2127	public:
2128	std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f) const
2129	{
2130	return do_get_string(f, trivial_tag());
2131	}
2132
2133	private:
2134	template <class Container>
2135	void construct_from_container(const Container& c, const std::integral_constant<bool, false>&)
2136	{
2137	//
2138	// We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
2139	//
2140	std::size_t newsize = static_cast<unsigned>(c.size() / sizeof(limb_type));
2141	if (c.size() % sizeof(limb_type))
2142	{
2143	++newsize;
2144	}
2145	if (newsize)
2146	{
2147	this->resize(newsize, newsize); // May throw
2148	std::memset(s: this->limbs(), c: 0, n: this->size());
2149	typename Container::const_iterator i(c.begin()), j(c.end());
2150	std::size_t byte_location = static_cast<unsigned>(c.size() - 1);
2151	while (i != j)
2152	{
2153	std::size_t limb = byte_location / sizeof(limb_type);
2154	std::size_t shift = (byte_location % sizeof(limb_type)) * CHAR_BIT;
2155	if (this->size() > limb)
2156	this->limbs()[limb] |= static_cast<limb_type>(static_cast<unsigned char>(*i)) << shift;
2157	++i;
2158	--byte_location;
2159	}
2160	}
2161	}
2162	template <class Container>
2163	BOOST_MP_CXX14_CONSTEXPR void construct_from_container(const Container& c, const std::integral_constant<bool, true>&)
2164	{
2165	//
2166	// We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
2167	//
2168	using local_limb_type = typename base_type::local_limb_type;
2169	*this->limbs() = 0;
2170	if (c.size())
2171	{
2172	typename Container::const_iterator i(c.begin()), j(c.end());
2173	std::size_t byte_location = static_cast<unsigned>(c.size() - 1);
2174	while (i != j)
2175	{
2176	std::size_t limb = byte_location / sizeof(local_limb_type);
2177	std::size_t shift = (byte_location % sizeof(local_limb_type)) * CHAR_BIT;
2178	if (limb == 0)
2179	this->limbs()[0] |= static_cast<limb_type>(static_cast<unsigned char>(*i)) << shift;
2180	++i;
2181	--byte_location;
2182	}
2183	}
2184	}
2185
2186	public:
2187	template <class Container>
2188	BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(const Container& c, typename std::enable_if<boost::multiprecision::detail::is_byte_container<Container>::value>::type const* = nullptr)
2189	{
2190	//
2191	// We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
2192	//
2193	construct_from_container(c, trivial_tag());
2194	}
2195	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2196	BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const std::integral_constant<bool, false>&, const std::integral_constant<bool, false>&) const noexcept
2197	{
2198	if (this->sign() != o.sign())
2199	return this->sign() ? -1 : 1;
2200
2201	// Only do the compare if the same sign:
2202	int result = compare_unsigned(o);
2203
2204	if (this->sign())
2205	result = -result;
2206	return result;
2207	}
2208	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2209	BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const std::integral_constant<bool, true>&, const std::integral_constant<bool, false>&) const
2210	{
2211	cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t(*this);
2212	return t.compare(o);
2213	}
2214	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2215	BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const std::integral_constant<bool, false>&, const std::integral_constant<bool, true>&) const
2216	{
2217	cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t(o);
2218	return compare(t);
2219	}
2220	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2221	BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const std::integral_constant<bool, true>&, const std::integral_constant<bool, true>&) const noexcept
2222	{
2223	if (this->sign())
2224	{
2225	if (o.sign())
2226	{
2227	return *this->limbs() < *o.limbs() ? 1 : (*this->limbs() > *o.limbs() ? -1 : 0);
2228	}
2229	else
2230	return -1;
2231	}
2232	else
2233	{
2234	if (o.sign())
2235	return 1;
2236	return *this->limbs() < *o.limbs() ? -1 : (*this->limbs() > *o.limbs() ? 1 : 0);
2237	}
2238	}
2239	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2240	BOOST_MP_CXX14_CONSTEXPR int compare(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) const noexcept
2241	{
2242	using t1 = std::integral_constant<bool, is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value> ;
2243	using t2 = std::integral_constant<bool, is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>;
2244	return compare_imp(o, t1(), t2());
2245	}
2246	template <std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2247	BOOST_MP_CXX14_CONSTEXPR int compare_unsigned(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) const noexcept
2248	{
2249	if (this->size() != o.size())
2250	{
2251	return this->size() > o.size() ? 1 : -1;
2252	}
2253	typename base_type::const_limb_pointer pa = this->limbs();
2254	typename base_type::const_limb_pointer pb = o.limbs();
2255	for (std::ptrdiff_t i = static_cast<std::ptrdiff_t>(static_cast<std::ptrdiff_t>(this->size()) - 1); i >= 0; --i)
2256	{
2257	if (pa[i] != pb[i])
2258	return pa[i] > pb[i] ? 1 : -1;
2259	}
2260	return 0;
2261	}
2262	template <class Arithmetic>
2263	BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<boost::multiprecision::detail::is_arithmetic<Arithmetic>::value, int>::type compare(Arithmetic i) const
2264	{
2265	// braindead version:
2266	cpp_int_backend t;
2267	t = i;
2268	return compare(t);
2269	}
2270	};
2271
2272	} // namespace backends
2273
2274	namespace default_ops {
2275
2276	template <class Backend>
2277	struct double_precision_type;
2278
2279	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2280	struct double_precision_type<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
2281	{
2282	using type = typename std::conditional<
2283	backends::is_fixed_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
2284	backends::cpp_int_backend<
2285	(std::is_void<Allocator>::value ? 2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value
2286	: MinBits),
2287	2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
2288	SignType,
2289	Checked,
2290	Allocator>,
2291	backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::type;
2292	};
2293
2294	} // namespace default_ops
2295
2296	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2297	struct is_equivalent_number_type<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, backends::cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >
2298	: public std::integral_constant<bool, std::numeric_limits<number<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, et_on> >::digits == std::numeric_limits<number<backends::cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, et_on> >::digits>{};
2299
2300	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2301	struct number_category<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public std::integral_constant<int, number_kind_integer>
2302	{};
2303
2304	#ifdef BOOST_HAS_INT128
2305
2306	namespace detail {
2307
2308	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2309	struct is_convertible_arithmetic<int128_type, backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
2310	{
2311	static constexpr bool value = true;
2312	};
2313	template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2314	struct is_convertible_arithmetic<uint128_type, backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
2315	{
2316	static constexpr bool value = true;
2317	};
2318
2319	}
2320
2321	#endif
2322
2323	#if defined(__GNUC__) && !defined(__clang__)
2324	// see https://github.com/boostorg/multiprecision/issues/413
2325	// and https://github.com/boostorg/multiprecision/issues/431
2326	#pragma GCC diagnostic pop
2327	#endif
2328	#ifdef BOOST_MSVC
2329	#pragma warning(pop)
2330	#endif
2331
2332	}} // namespace boost::multiprecision
2333
2334	//
2335	// Last of all we include the implementations of all the eval_* non member functions:
2336	//
2337	#include <boost/multiprecision/cpp_int/limits.hpp>
2338	#include <boost/multiprecision/cpp_int/comparison.hpp>
2339	#include <boost/multiprecision/cpp_int/add.hpp>
2340	#include <boost/multiprecision/cpp_int/multiply.hpp>
2341	#include <boost/multiprecision/cpp_int/divide.hpp>
2342	#include <boost/multiprecision/cpp_int/bitwise.hpp>
2343	#include <boost/multiprecision/cpp_int/misc.hpp>
2344	#include <boost/multiprecision/cpp_int/literals.hpp>
2345	#include <boost/multiprecision/cpp_int/serialize.hpp>
2346	#include <boost/multiprecision/cpp_int/import_export.hpp>
2347
2348	#endif
2349