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