boost/multiprecision/cpp_int/import_export.hpp

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