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