1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
///////////////////////////////////////////////////////////////
// Copyright 2015 John Maddock. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
#ifndef BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
#define BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
namespace boost {
namespace multiprecision {
namespace detail {
template <class Backend, class Unsigned>
void assign_bits(Backend& val, Unsigned bits, unsigned bit_location, unsigned chunk_bits, const mpl::false_& tag)
{
unsigned limb = bit_location / (sizeof(limb_type) * CHAR_BIT);
unsigned shift = bit_location % (sizeof(limb_type) * CHAR_BIT);
limb_type mask = chunk_bits >= sizeof(limb_type) * CHAR_BIT ? ~static_cast<limb_type>(0u) : (static_cast<limb_type>(1u) << chunk_bits) - 1;
limb_type value = static_cast<limb_type>(bits & mask) << shift;
if(value)
{
if(val.size() == limb)
{
val.resize(limb + 1, limb + 1);
if(val.size() > limb)
val.limbs()[limb] = value;
}
else if(val.size() > limb)
val.limbs()[limb] |= value;
}
if(chunk_bits > sizeof(limb_type) * CHAR_BIT - shift)
{
shift = sizeof(limb_type) * CHAR_BIT - shift;
chunk_bits -= shift;
bit_location += shift;
bits >>= shift;
if(bits)
assign_bits(val, bits, bit_location, chunk_bits, tag);
}
}
template <class Backend, class Unsigned>
void assign_bits(Backend& val, Unsigned bits, unsigned bit_location, unsigned chunk_bits, const mpl::true_&)
{
typedef typename Backend::local_limb_type local_limb_type;
//
// Check for possible overflow, this may trigger an exception, or have no effect
// depending on whether this is a checked integer or not:
//
if((bit_location >= sizeof(local_limb_type) * CHAR_BIT) && bits)
val.resize(2, 2);
else
{
local_limb_type mask = chunk_bits >= sizeof(local_limb_type) * CHAR_BIT ? ~static_cast<local_limb_type>(0u) : (static_cast<local_limb_type>(1u) << chunk_bits) - 1;
local_limb_type value = (static_cast<local_limb_type>(bits) & mask) << bit_location;
*val.limbs() |= value;
//
// Check for overflow bits:
//
bit_location = sizeof(local_limb_type) * CHAR_BIT - bit_location;
bits >>= bit_location;
if(bits)
val.resize(2, 2); // May throw!
}
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, unsigned bits, const mpl::false_&)
{
unsigned limb_count = static_cast<unsigned>(bits / (sizeof(limb_type) * CHAR_BIT));
if(bits % (sizeof(limb_type) * CHAR_BIT))
++limb_count;
static const unsigned max_limbs = MaxBits ? MaxBits / (CHAR_BIT * sizeof(limb_type)) + ((MaxBits % (CHAR_BIT * sizeof(limb_type))) ? 1 : 0) : (std::numeric_limits<unsigned>::max)();
if(limb_count > max_limbs)
limb_count = max_limbs;
newval.resize(limb_count, limb_count);
std::memset(newval.limbs(), 0, newval.size() * sizeof(limb_type));
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, unsigned, const mpl::true_&)
{
*newval.limbs() = 0;
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
import_bits_generic(
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, unsigned chunk_size = 0, bool msv_first = true)
{
typename number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>::backend_type newval;
typedef typename std::iterator_traits<Iterator>::value_type value_type;
typedef typename boost::make_unsigned<value_type>::type unsigned_value_type;
typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
typedef typename boost::make_unsigned<difference_type>::type size_type;
typedef typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag tag_type;
if(!chunk_size)
chunk_size = std::numeric_limits<value_type>::digits;
size_type limbs = std::distance(i, j);
size_type bits = limbs * chunk_size;
detail::resize_to_bit_size(newval, static_cast<unsigned>(bits), tag_type());
difference_type bit_location = msv_first ? bits - chunk_size : 0;
difference_type bit_location_change = msv_first ? -static_cast<difference_type>(chunk_size) : chunk_size;
while(i != j)
{
detail::assign_bits(newval, static_cast<unsigned_value_type>(*i), static_cast<unsigned>(bit_location), chunk_size, tag_type());
++i;
bit_location += bit_location_change;
}
newval.normalize();
val.backend().swap(newval);
return val;
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
inline typename boost::disable_if_c<boost::multiprecision::backends::is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value, number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&>::type
import_bits_fast(
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0)
{
std::size_t byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
std::size_t limb_len = byte_len / sizeof(limb_type);
if(byte_len % sizeof(limb_type))
++limb_len;
cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result = val.backend();
result.resize(static_cast<unsigned>(limb_len), static_cast<unsigned>(limb_len)); // checked types may throw here if they're not large enough to hold the data!
result.limbs()[result.size() - 1] = 0u;
std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(limb_type)));
result.normalize(); // In case data has leading zeros.
return val;
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
inline typename boost::enable_if_c<boost::multiprecision::backends::is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value, number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&>::type
import_bits_fast(
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0)
{
cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result = val.backend();
std::size_t byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
std::size_t limb_len = byte_len / sizeof(result.limbs()[0]);
if(byte_len % sizeof(result.limbs()[0]))
++limb_len;
result.limbs()[0] = 0u;
result.resize(static_cast<unsigned>(limb_len), static_cast<unsigned>(limb_len)); // checked types may throw here if they're not large enough to hold the data!
std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(result.limbs()[0])));
result.normalize(); // In case data has leading zeros.
return val;
}
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
import_bits(
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, unsigned chunk_size = 0, bool msv_first = true)
{
return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
import_bits(
number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0, bool msv_first = true)
{
#ifdef BOOST_LITTLE_ENDIAN
if(((chunk_size % CHAR_BIT) == 0) && !msv_first)
return detail::import_bits_fast(val, i, j, chunk_size);
#endif
return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
}
namespace detail {
template <class Backend>
boost::uintmax_t extract_bits(const Backend& val, unsigned location, unsigned count, const mpl::false_& tag)
{
unsigned limb = location / (sizeof(limb_type) * CHAR_BIT);
unsigned shift = location % (sizeof(limb_type) * CHAR_BIT);
boost::uintmax_t result = 0;
boost::uintmax_t mask = count == std::numeric_limits<boost::uintmax_t>::digits ? ~static_cast<boost::uintmax_t>(0) : (static_cast<boost::uintmax_t>(1u) << count) - 1;
if(count > (sizeof(limb_type) * CHAR_BIT - shift))
{
result = extract_bits(val, location + sizeof(limb_type) * CHAR_BIT - shift, count - sizeof(limb_type) * CHAR_BIT + shift, tag);
result <<= sizeof(limb_type) * CHAR_BIT - shift;
}
if(limb < val.size())
result |= (val.limbs()[limb] >> shift) & mask;
return result;
}
template <class Backend>
inline boost::uintmax_t extract_bits(const Backend& val, unsigned location, unsigned count, const mpl::true_&)
{
typename Backend::local_limb_type result = *val.limbs();
typename Backend::local_limb_type mask = count >= std::numeric_limits<typename Backend::local_limb_type>::digits ? ~static_cast<typename Backend::local_limb_type>(0) : (static_cast<typename Backend::local_limb_type>(1u) << count) - 1;
return (result >> location) & mask;
}
}
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class OutputIterator>
OutputIterator export_bits(
const number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, OutputIterator out, unsigned chunk_size, bool msv_first = true)
{
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4244)
#endif
typedef typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag tag_type;
if(!val)
{
*out = 0;
++out;
return out;
}
unsigned bitcount = boost::multiprecision::backends::eval_msb_imp(val.backend()) + 1;
unsigned chunks = bitcount / chunk_size;
if(bitcount % chunk_size)
++chunks;
int bit_location = msv_first ? bitcount - chunk_size : 0;
int bit_step = msv_first ? -static_cast<int>(chunk_size) : chunk_size;
while(bit_location % bit_step) ++bit_location;
do
{
*out = detail::extract_bits(val.backend(), bit_location, chunk_size, tag_type());
++out;
bit_location += bit_step;
} while((bit_location >= 0) && (bit_location < (int)bitcount));
return out;
#ifdef _MSC_VER
#pragma warning(pop)
#endif
}
}
}
#endif // BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
|
