ceph/src/boost/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 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>
  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>
  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                if((bit_location < sizeof(bits)*CHAR_BIT) && (bits >>= bit_location))
  65                   val.resize(2, 2); // May throw!
  66             }
  67          }
  68
  69          template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  70          inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, unsigned bits, const mpl::false_&)
  71          {
  72             unsigned limb_count = static_cast<unsigned>(bits / (sizeof(limb_type) * CHAR_BIT));
  73             if(bits % (sizeof(limb_type) * CHAR_BIT))
  74                ++limb_count;
  75             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)();
  76             if(limb_count > max_limbs)
  77                limb_count = max_limbs;
  78             newval.resize(limb_count, limb_count);
  79             std::memset(newval.limbs(), 0, newval.size() * sizeof(limb_type));
  80          }
  81          template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  82          inline void resize_to_bit_size(cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& newval, unsigned, const mpl::true_&)
  83          {
  84             *newval.limbs() = 0;
  85          }
  86
  87          template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
  88          number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
  89             import_bits_generic(
  90                number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, unsigned chunk_size = 0, bool msv_first = true)
  91          {
  92             typename number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>::backend_type newval;
  93
  94             typedef typename std::iterator_traits<Iterator>::value_type       value_type;
  95             typedef typename boost::make_unsigned<value_type>::type           unsigned_value_type;
  96             typedef typename std::iterator_traits<Iterator>::difference_type  difference_type;
  97             typedef typename boost::make_unsigned<difference_type>::type      size_type;
  98             typedef typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag tag_type;
  99
 100             if(!chunk_size)
 101                chunk_size = std::numeric_limits<value_type>::digits;
 102
 103             size_type limbs = std::distance(i, j);
 104             size_type bits = limbs * chunk_size;
 105
 106             detail::resize_to_bit_size(newval, static_cast<unsigned>(bits), tag_type());
 107
 108             difference_type bit_location = msv_first ? bits - chunk_size : 0;
 109             difference_type bit_location_change = msv_first ? -static_cast<difference_type>(chunk_size) : chunk_size;
 110
 111             while(i != j)
 112             {
 113                detail::assign_bits(newval, static_cast<unsigned_value_type>(*i), static_cast<unsigned>(bit_location), chunk_size, tag_type());
 114                ++i;
 115                bit_location += bit_location_change;
 116             }
 117
 118             newval.normalize();
 119
 120             val.backend().swap(newval);
 121             return val;
 122          }
 123
 124          template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
 125          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
 126             import_bits_fast(
 127                number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0)
 128          {
 129             std::size_t byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
 130             std::size_t limb_len = byte_len / sizeof(limb_type);
 131             if(byte_len % sizeof(limb_type))
 132                ++limb_len;
 133             cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result = val.backend();
 134             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!
 135             result.limbs()[result.size() - 1] = 0u;
 136             std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(limb_type)));
 137             result.normalize(); // In case data has leading zeros.
 138             return val;
 139          }
 140          template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
 141          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
 142             import_bits_fast(
 143                number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0)
 144          {
 145             cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result = val.backend();
 146             std::size_t byte_len = (j - i) * (chunk_size ? chunk_size / CHAR_BIT : sizeof(*i));
 147             std::size_t limb_len = byte_len / sizeof(result.limbs()[0]);
 148             if(byte_len % sizeof(result.limbs()[0]))
 149                ++limb_len;
 150             result.limbs()[0] = 0u;
 151             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!
 152             std::memcpy(result.limbs(), i, (std::min)(byte_len, result.size() * sizeof(result.limbs()[0])));
 153             result.normalize(); // In case data has leading zeros.
 154             return val;
 155          }
 156       }
 157
 158
 159       template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class Iterator>
 160       inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
 161          import_bits(
 162             number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, Iterator i, Iterator j, unsigned chunk_size = 0, bool msv_first = true)
 163       {
 164          return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
 165       }
 166
 167       template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class T>
 168       inline number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>&
 169          import_bits(
 170             number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, T* i, T* j, unsigned chunk_size = 0, bool msv_first = true)
 171       {
 172 #ifdef BOOST_LITTLE_ENDIAN
 173          if(((chunk_size % CHAR_BIT) == 0) && !msv_first)
 174             return detail::import_bits_fast(val, i, j, chunk_size);
 175 #endif
 176          return detail::import_bits_generic(val, i, j, chunk_size, msv_first);
 177       }
 178
 179       namespace detail {
 180
 181          template <class Backend>
 182          boost::uintmax_t extract_bits(const Backend& val, unsigned location, unsigned count, const mpl::false_& tag)
 183          {
 184             unsigned limb = location / (sizeof(limb_type) * CHAR_BIT);
 185             unsigned shift = location % (sizeof(limb_type) * CHAR_BIT);
 186             boost::uintmax_t result = 0;
 187             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;
 188             if(count > (sizeof(limb_type) * CHAR_BIT - shift))
 189             {
 190                result = extract_bits(val, location + sizeof(limb_type) * CHAR_BIT - shift, count - sizeof(limb_type) * CHAR_BIT + shift, tag);
 191                result <<= sizeof(limb_type) * CHAR_BIT - shift;
 192             }
 193             if(limb < val.size())
 194                result |= (val.limbs()[limb] >> shift) & mask;
 195             return result;
 196          }
 197
 198          template <class Backend>
 199          inline boost::uintmax_t extract_bits(const Backend& val, unsigned location, unsigned count, const mpl::true_&)
 200          {
 201             typename Backend::local_limb_type result = *val.limbs();
 202             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;
 203             return (result >> location) & mask;
 204          }
 205
 206       }
 207
 208       template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, expression_template_option ExpressionTemplates, class OutputIterator>
 209       OutputIterator export_bits(
 210          const number<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, ExpressionTemplates>& val, OutputIterator out, unsigned chunk_size, bool msv_first = true)
 211       {
 212 #ifdef _MSC_VER
 213 #pragma warning(push)
 214 #pragma warning(disable:4244)
 215 #endif
 216          typedef typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::trivial_tag tag_type;
 217          if(!val)
 218          {
 219             *out = 0;
 220             ++out;
 221             return out;
 222          }
 223          unsigned bitcount = boost::multiprecision::backends::eval_msb_imp(val.backend()) + 1;
 224          unsigned chunks = bitcount / chunk_size;
 225          if(bitcount % chunk_size)
 226             ++chunks;
 227
 228          int bit_location = msv_first ? bitcount - chunk_size : 0;
 229          int bit_step = msv_first ? -static_cast<int>(chunk_size) : chunk_size;
 230          while(bit_location % bit_step) ++bit_location;
 231
 232          do
 233          {
 234             *out = detail::extract_bits(val.backend(), bit_location, chunk_size, tag_type());
 235             ++out;
 236             bit_location += bit_step;
 237          } while((bit_location >= 0) && (bit_location < (int)bitcount));
 238
 239          return out;
 240 #ifdef _MSC_VER
 241 #pragma warning(pop)
 242 #endif
 243       }
 244
 245    }
 246 }
 247
 248
 249
 250 #endif // BOOST_MP_CPP_INT_IMPORT_EXPORT_HPP
 251