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