multiprecision/cpp_int/import_export.hpp

0001 ///////////////////////////////////////////////////////////////
0002 //  Copyright 2015 John Maddock. Distributed under the Boost
0003 //  Software License, Version 1.0. (See accompanying file
0004 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
0005
0006 #ifndef BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
0007 #define BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
0008
0009 #include <climits>
0010 #include <cstring>
0011 #include <boost/multiprecision/detail/endian.hpp>
0012
0013 namespace boost {
0014 namespace multiprecision {
0015
0016 namespace detail {
0017
0018 template <class Backend, class Unsigned>
0019 void assign_bits(Backend& val, Unsigned bits, std::size_t bit_location, std::size_t chunk_bits, const std::integral_constant<bool, false>& tag)
0020 {
0021    std::size_t limb  = bit_location / (sizeof(limb_type) * CHAR_BIT);
0022    std::size_t shift = bit_location % (sizeof(limb_type) * CHAR_BIT);
0023
0024    limb_type mask = chunk_bits >= sizeof(limb_type) * CHAR_BIT ? ~static_cast<limb_type>(0u) : (static_cast<limb_type>(1u) << chunk_bits) - 1;
0025
0026    limb_type value = static_cast<limb_type>(bits & mask) << shift;
0027    if (value)
0028    {
0029       if (val.size() == limb)
0030       {
0031          val.resize(limb + 1, limb + 1);
0032          if (val.size() > limb)
0033             val.limbs()[limb] = value;
0034       }
0035       else if (val.size() > limb)
0036          val.limbs()[limb] |= value;
0037    }
0038    if (chunk_bits > sizeof(limb_type) * CHAR_BIT - shift)
0039    {
0040       shift = sizeof(limb_type) * CHAR_BIT - shift;
0041       chunk_bits -= shift;
0042       bit_location += shift;
0043       bits >>= shift;
0044       if (bits)
0045          assign_bits(val, bits, bit_location, chunk_bits, tag);
0046    }
0047 }
0048 template <class Backend, class Unsigned>
0049 void assign_bits(Backend& val, Unsigned bits, std::size_t bit_location, std::size_t chunk_bits, const std::integral_constant<bool, true>&)
0050 {
0051    using local_limb_type = typename Backend::local_limb_type;
0052    //
0053    // Check for possible overflow, this may trigger an exception, or have no effect
0054    // depending on whether this is a checked integer or not:
0055    //
0056    if ((bit_location >= sizeof(local_limb_type) * CHAR_BIT) && bits)
0057       val.resize(2, 2);
0058    else
0059    {
0060       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;
0061       local_limb_type value = (static_cast<local_limb_type>(bits) & mask) << bit_location;
0062       *val.limbs() |= value;
0063       //
0064       // Check for overflow bits:
0065       //
0066       bit_location = sizeof(local_limb_type) * CHAR_BIT - bit_location;
0067       if ((bit_location < sizeof(bits) * CHAR_BIT) && (bits >>= bit_location))
0068          val.resize(2, 2); // May throw!
0069    }
0070 }
0071
0072 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
0073 inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, std::size_t bits, const std::integral_constant<bool, false>&)
0074 {
0075    std::size_t limb_count = static_cast<unsigned>(bits / (sizeof(limb_type) * CHAR_BIT));
0076    if (bits % (sizeof(limb_type) * CHAR_BIT))
0077       ++limb_count;
0078    constexpr std::size_t max_limbs = MaxBits ? MaxBits / (CHAR_BIT * sizeof(limb_type)) + ((MaxBits % (CHAR_BIT * sizeof(limb_type))) ? 1 : 0) : (std::numeric_limits<unsigned>::max)();
0079    if (limb_count > max_limbs)
0080       limb_count = max_limbs;
0081    newval.resize(limb_count, limb_count);
0082    std::memset(newval.limbs(), 0, newval.size() * sizeof(limb_type));
0083 }
0084 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
0085 inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, unsigned, const std::integral_constant<bool, true>&)
0086 {
0087    *newval.limbs() = 0;
0088 }
0089
0090 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
0091 number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
0092 import_bits_generic(
0093     number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, std::size_t chunk_size = 0, bool msv_first = true)
0094 {
0095    typename number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>::backend_type newval;
0096
0097    using value_type = typename std::iterator_traits<Iterator>::value_type                                  ;
0098    using unsigned_value_type = typename boost::multiprecision::detail::make_unsigned<value_type>::type                                        ;
0099    using difference_type = typename std::iterator_traits<Iterator>::difference_type                             ;
0100    using size_type = typename boost::multiprecision::detail::make_unsigned<difference_type>::type                                   ;
0101    using tag_type = typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag;
0102
0103    if (!chunk_size)
0104       chunk_size = std::numeric_limits<value_type>::digits;
0105
0106    size_type limbs = std::distance(i, j);
0107    size_type bits  = limbs * chunk_size;
0108
0109    detail::resize_to_bit_size(newval, static_cast<unsigned>(bits), tag_type());
0110
0111    difference_type bit_location        = msv_first ? bits - chunk_size : 0;
0112    difference_type bit_location_change = msv_first ? -static_cast<difference_type>(chunk_size) : chunk_size;
0113
0114    while (i != j)
0115    {
0116       detail::assign_bits(newval, static_cast<unsigned_value_type>(*i), static_cast<std::size_t>(bit_location), chunk_size, tag_type());
0117       ++i;
0118       bit_location += bit_location_change;
0119    }
0120
0121    newval.normalize();
0122
0123    val.backend().swap(newval);
0124    return val;
0125 }
0126
0127 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
0128 inline typename std::enable_if< !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
0129 import_bits_fast(
0130     number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, std::size_t chunk_size = 0)
0131 {
0132    std::size_t byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
0133    std::size_t limb_len = byte_len / sizeof(limb_type);
0134    if (byte_len % sizeof(limb_type))
0135       ++limb_len;
0136    cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result = val.backend();
0137    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!
0138    result.limbs()[result.size() - 1] = 0u;
0139    std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(limb_type)));
0140    result.normalize(); // In case data has leading zeros.
0141    return val;
0142 }
0143 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
0144 inline typename std::enable_if<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
0145 import_bits_fast(
0146     number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, std::size_t chunk_size = 0)
0147 {
0148    cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result   = val.backend();
0149    std::size_t                                                      byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
0150    std::size_t                                                      limb_len = byte_len / sizeof(result.limbs()[0]);
0151    if (byte_len % sizeof(result.limbs()[0]))
0152       ++limb_len;
0153    result.limbs()[0] = 0u;
0154    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!
0155    std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(result.limbs()[0])));
0156    result.normalize(); // In case data has leading zeros.
0157    return val;
0158 }
0159 } // namespace detail
0160
0161 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
0162 inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
0163 import_bits(
0164     number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, std::size_t chunk_size = 0, bool msv_first = true)
0165 {
0166    return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
0167 }
0168
0169 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
0170 inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
0171 import_bits(
0172     number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, std::size_t chunk_size = 0, bool msv_first = true)
0173 {
0174 #if BOOST_MP_ENDIAN_LITTLE_BYTE
0175    if (((chunk_size % CHAR_BIT) == 0) && !msv_first && (sizeof(*i) * CHAR_BIT == chunk_size))
0176       return detail::import_bits_fast(val, i, j, chunk_size);
0177 #endif
0178    return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
0179 }
0180
0181 namespace detail {
0182
0183 template <class Backend>
0184 std::uintmax_t extract_bits(const Backend& val, std::size_t location, std::size_t count, const std::integral_constant<bool, false>& tag)
0185 {
0186    std::size_t         limb   = location / (sizeof(limb_type) * CHAR_BIT);
0187    std::size_t         shift  = location % (sizeof(limb_type) * CHAR_BIT);
0188    std::uintmax_t result = 0;
0189    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;
0190    if (count > (sizeof(limb_type) * CHAR_BIT - shift))
0191    {
0192       result = extract_bits(val, location + sizeof(limb_type) * CHAR_BIT - shift, count - sizeof(limb_type) * CHAR_BIT + shift, tag);
0193       result <<= sizeof(limb_type) * CHAR_BIT - shift;
0194    }
0195    if (limb < val.size())
0196       result |= (val.limbs()[limb] >> shift) & mask;
0197    return result;
0198 }
0199
0200 template <class Backend>
0201 inline std::uintmax_t extract_bits(const Backend& val, std::size_t location, std::size_t count, const std::integral_constant<bool, true>&)
0202 {
0203    typename Backend::local_limb_type result = *val.limbs();
0204    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;
0205    return (result >> location) & mask;
0206 }
0207
0208 } // namespace detail
0209
0210 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class OutputIterator>
0211 OutputIterator export_bits(
0212     const number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, OutputIterator out, std::size_t chunk_size, bool msv_first = true)
0213 {
0214 #ifdef BOOST_MSVC
0215 #pragma warning(push)
0216 #pragma warning(disable : 4244)
0217 #endif
0218    using tag_type = typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag;
0219    if (!val)
0220    {
0221       *out = 0;
0222       ++out;
0223       return out;
0224    }
0225    std::size_t bitcount = boost::multiprecision::backends::eval_msb_imp(val.backend()) + 1;
0226
0227          std::ptrdiff_t bit_location = msv_first ? static_cast<std::ptrdiff_t>(bitcount - chunk_size) : 0;
0228    const std::ptrdiff_t bit_step     = msv_first ? static_cast<std::ptrdiff_t>(-static_cast<std::ptrdiff_t>(chunk_size)) : static_cast<std::ptrdiff_t>(chunk_size);
0229    while (bit_location % bit_step)
0230       ++bit_location;
0231
0232    do
0233    {
0234       *out = detail::extract_bits(val.backend(), bit_location, chunk_size, tag_type());
0235       ++out;
0236       bit_location += bit_step;
0237    } while ((bit_location >= 0) && (bit_location < static_cast<int>(bitcount)));
0238
0239    return out;
0240 #ifdef BOOST_MSVC
0241 #pragma warning(pop)
0242 #endif
0243 }
0244
0245 }
0246 } // namespace boost::multiprecision
0247
0248 #endif // BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP