charconv/detail/to_chars_integer_impl.hpp

0001 // Copyright 2020-2023 Junekey Jeon
0002 // Copyright 2022 Peter Dimov
0003 // Copyright 2023 Matt Borland
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // https://www.boost.org/LICENSE_1_0.txt
0006
0007 #ifndef BOOST_CHARCONV_DETAIL_TO_CHARS_INTEGER_IMPL_HPP
0008 #define BOOST_CHARCONV_DETAIL_TO_CHARS_INTEGER_IMPL_HPP
0009
0010 #include <boost/charconv/detail/config.hpp>
0011 #include <boost/charconv/detail/memcpy.hpp>
0012 #include <boost/charconv/detail/to_chars_result.hpp>
0013 #include <boost/charconv/detail/integer_search_trees.hpp>
0014 #include <boost/charconv/detail/emulated128.hpp>
0015 #include <boost/charconv/detail/apply_sign.hpp>
0016 #include <limits>
0017 #include <system_error>
0018 #include <type_traits>
0019 #include <array>
0020 #include <limits>
0021 #include <utility>
0022 #include <cstring>
0023 #include <cstdio>
0024 #include <cerrno>
0025 #include <cstdint>
0026 #include <climits>
0027 #include <cmath>
0028
0029 namespace boost { namespace charconv { namespace detail {
0030
0031
0032 static constexpr char radix_table[] = {
0033         '0', '0', '0', '1', '0', '2', '0', '3', '0', '4',
0034         '0', '5', '0', '6', '0', '7', '0', '8', '0', '9',
0035         '1', '0', '1', '1', '1', '2', '1', '3', '1', '4',
0036         '1', '5', '1', '6', '1', '7', '1', '8', '1', '9',
0037         '2', '0', '2', '1', '2', '2', '2', '3', '2', '4',
0038         '2', '5', '2', '6', '2', '7', '2', '8', '2', '9',
0039         '3', '0', '3', '1', '3', '2', '3', '3', '3', '4',
0040         '3', '5', '3', '6', '3', '7', '3', '8', '3', '9',
0041         '4', '0', '4', '1', '4', '2', '4', '3', '4', '4',
0042         '4', '5', '4', '6', '4', '7', '4', '8', '4', '9',
0043         '5', '0', '5', '1', '5', '2', '5', '3', '5', '4',
0044         '5', '5', '5', '6', '5', '7', '5', '8', '5', '9',
0045         '6', '0', '6', '1', '6', '2', '6', '3', '6', '4',
0046         '6', '5', '6', '6', '6', '7', '6', '8', '6', '9',
0047         '7', '0', '7', '1', '7', '2', '7', '3', '7', '4',
0048         '7', '5', '7', '6', '7', '7', '7', '8', '7', '9',
0049         '8', '0', '8', '1', '8', '2', '8', '3', '8', '4',
0050         '8', '5', '8', '6', '8', '7', '8', '8', '8', '9',
0051         '9', '0', '9', '1', '9', '2', '9', '3', '9', '4',
0052         '9', '5', '9', '6', '9', '7', '9', '8', '9', '9'
0053 };
0054
0055 static constexpr char digit_table[] = {
0056         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
0057         'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
0058         'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
0059         'u', 'v', 'w', 'x', 'y', 'z'
0060 };
0061
0062 // See: https://jk-jeon.github.io/posts/2022/02/jeaiii-algorithm/
0063 // https://arxiv.org/abs/2101.11408
0064 BOOST_CHARCONV_CONSTEXPR char* decompose32(std::uint32_t value, char* buffer) noexcept
0065 {
0066     constexpr auto mask = (std::uint64_t(1) << 57) - 1;
0067     auto y = value * std::uint64_t(1441151881);
0068
0069     for (std::size_t i {}; i < 10; i += 2)
0070     {
0071         boost::charconv::detail::memcpy(buffer + i, radix_table + static_cast<std::size_t>(y >> 57) * 2, 2);
0072         y &= mask;
0073         y *= 100;
0074     }
0075
0076     return buffer + 10;
0077 }
0078
0079 #ifdef BOOST_MSVC
0080 # pragma warning(push)
0081 # pragma warning(disable: 4127 4146)
0082 #endif
0083
0084 template <typename Integer>
0085 BOOST_CHARCONV_CONSTEXPR to_chars_result to_chars_integer_impl(char* first, char* last, Integer value) noexcept
0086 {
0087     using Unsigned_Integer = typename std::make_unsigned<Integer>::type;
0088     Unsigned_Integer unsigned_value {};
0089
0090     char buffer[10] {};
0091     int converted_value_digits {};
0092     bool is_negative = false;
0093
0094     if (first > last)
0095     {
0096         return {last, std::errc::invalid_argument};
0097     }
0098
0099     // Strip the sign from the value and apply at the end after parsing if the type is signed
0100     BOOST_IF_CONSTEXPR (std::is_signed<Integer>::value)
0101     {
0102         if (value < 0)
0103         {
0104             is_negative = true;
0105             unsigned_value = apply_sign(value);
0106         }
0107         else
0108         {
0109             unsigned_value = static_cast<Unsigned_Integer>(value);
0110         }
0111     }
0112     else
0113     {
0114         unsigned_value = static_cast<Unsigned_Integer>(value);
0115     }
0116
0117     const std::ptrdiff_t user_buffer_size = last - first - static_cast<std::ptrdiff_t>(is_negative);
0118
0119     // If the type is less than 32 bits we can use this without change
0120     // If the type is greater than 32 bits we use a binary search tree to figure out how many digits
0121     // are present and then decompose the value into two (or more) std::uint32_t of known length so that we
0122     // don't have the issue of removing leading zeros from the least significant digits
0123
0124     // Yields: warning C4127: conditional expression is constant because first half of the expression is constant,
0125     // but we need to short circuit to avoid UB on the second half
0126     if (std::numeric_limits<Integer>::digits <= std::numeric_limits<std::uint32_t>::digits ||
0127         unsigned_value <= static_cast<Unsigned_Integer>((std::numeric_limits<std::uint32_t>::max)()))
0128     {
0129         const auto converted_value = static_cast<std::uint32_t>(unsigned_value);
0130         converted_value_digits = num_digits(converted_value);
0131
0132         if (converted_value_digits > user_buffer_size)
0133         {
0134             return {last, std::errc::value_too_large};
0135         }
0136
0137         decompose32(converted_value, buffer);
0138
0139         if (is_negative)
0140         {
0141             *first++ = '-';
0142         }
0143
0144         boost::charconv::detail::memcpy(first, buffer + (sizeof(buffer) - static_cast<unsigned>(converted_value_digits)),
0145                                         static_cast<std::size_t>(converted_value_digits));
0146     }
0147     else if (std::numeric_limits<Integer>::digits <= std::numeric_limits<std::uint64_t>::digits ||
0148              static_cast<std::uint64_t>(unsigned_value) <= (std::numeric_limits<std::uint64_t>::max)())
0149     {
0150         auto converted_value = static_cast<std::uint64_t>(unsigned_value);
0151         converted_value_digits = num_digits(converted_value);
0152
0153         if (converted_value_digits > user_buffer_size)
0154         {
0155             return {last, std::errc::value_too_large};
0156         }
0157
0158         if (is_negative)
0159         {
0160             *first++ = '-';
0161         }
0162
0163         // Only store 9 digits in each to avoid overflow
0164         if (num_digits(converted_value) <= 18)
0165         {
0166             const auto x = static_cast<std::uint32_t>(converted_value / UINT64_C(1000000000));
0167             const auto y = static_cast<std::uint32_t>(converted_value % UINT64_C(1000000000));
0168             const int first_value_chars = num_digits(x);
0169
0170             decompose32(x, buffer);
0171             boost::charconv::detail::memcpy(first, buffer + (sizeof(buffer) - static_cast<unsigned>(first_value_chars)),
0172                                             static_cast<std::size_t>(first_value_chars));
0173
0174             decompose32(y, buffer);
0175             boost::charconv::detail::memcpy(first + first_value_chars, buffer + 1, sizeof(buffer) - 1);
0176         }
0177         else
0178         {
0179             const auto x = static_cast<std::uint32_t>(converted_value / UINT64_C(100000000000));
0180             converted_value -= x * UINT64_C(100000000000);
0181             const auto y = static_cast<std::uint32_t>(converted_value / UINT64_C(100));
0182             const auto z = static_cast<std::uint32_t>(converted_value % UINT64_C(100));
0183
0184             if (converted_value_digits == 19)
0185             {
0186                 decompose32(x, buffer);
0187                 boost::charconv::detail::memcpy(first, buffer + 2, sizeof(buffer) - 2);
0188
0189                 decompose32(y, buffer);
0190                 boost::charconv::detail::memcpy(first + 8, buffer + 1, sizeof(buffer) - 1);
0191
0192                 // Always prints 2 digits last
0193                 boost::charconv::detail::memcpy(first + 17, radix_table + z * 2, 2);
0194             }
0195             else // 20
0196             {
0197                 decompose32(x, buffer);
0198                 boost::charconv::detail::memcpy(first, buffer + 1, sizeof(buffer) - 1);
0199
0200                 decompose32(y, buffer);
0201                 boost::charconv::detail::memcpy(first + 9, buffer + 1, sizeof(buffer) - 1);
0202
0203                 // Always prints 2 digits last
0204                 boost::charconv::detail::memcpy(first + 18, radix_table + z * 2, 2);
0205             }
0206         }
0207     }
0208
0209     return {first + converted_value_digits, std::errc()};
0210 }
0211
0212 // Prior to GCC 10.3 std::numeric_limits was not specialized for __int128 which breaks the above control flow
0213 // Here we find if the 128-bit type will fit into a 64-bit type and use the above, or we use string manipulation
0214 // to extract the digits
0215 //
0216 // See: https://quuxplusone.github.io/blog/2019/02/28/is-int128-integral/
0217 template <typename Integer>
0218 BOOST_CHARCONV_CONSTEXPR to_chars_result to_chars_128integer_impl(char* first, char* last, Integer value) noexcept
0219 {
0220     #ifdef BOOST_CHARCONV_HAS_INT128
0221     using Unsigned_Integer = boost::uint128_type;
0222     #else
0223     using Unsigned_Integer = uint128;
0224     #endif
0225
0226     Unsigned_Integer unsigned_value {};
0227
0228     const std::ptrdiff_t user_buffer_size = last - first;
0229     BOOST_ATTRIBUTE_UNUSED bool is_negative = false;
0230
0231     if (first > last)
0232     {
0233         return {last, std::errc::invalid_argument};
0234     }
0235
0236     // Strip the sign from the value and apply at the end after parsing if the type is signed
0237     #ifdef BOOST_CHARCONV_HAS_INT128
0238     BOOST_IF_CONSTEXPR (std::is_same<boost::int128_type, Integer>::value)
0239     {
0240         if (value < 0)
0241         {
0242             is_negative = true;
0243             unsigned_value = -(static_cast<Unsigned_Integer>(value));
0244         }
0245         else
0246         {
0247             unsigned_value = static_cast<Unsigned_Integer>(value);
0248         }
0249     }
0250     else
0251     #endif
0252     {
0253         unsigned_value = static_cast<Unsigned_Integer>(value);
0254     }
0255
0256     auto converted_value = static_cast<Unsigned_Integer>(unsigned_value);
0257
0258     const int converted_value_digits = num_digits(converted_value);
0259
0260     if (converted_value_digits > user_buffer_size)
0261     {
0262         return {last, std::errc::value_too_large};
0263     }
0264
0265     if (is_negative)
0266     {
0267         *first++ = '-';
0268     }
0269
0270     // If the value fits into 64 bits use the other method of processing
0271     if (converted_value < (std::numeric_limits<std::uint64_t>::max)())
0272     {
0273         return to_chars_integer_impl(first, last, static_cast<std::uint64_t>(value));
0274     }
0275
0276     constexpr std::uint32_t ten_9 = UINT32_C(1000000000);
0277     char buffer[5][10] {};
0278     int num_chars[5] {};
0279     int i = 0;
0280
0281     while (converted_value != 0)
0282     {
0283         auto digits = static_cast<std::uint32_t>(converted_value % ten_9);
0284         num_chars[i] = num_digits(digits);
0285         decompose32(digits, buffer[i]); // Always returns 10 digits (to include leading 0s) which we want
0286         converted_value = (converted_value - digits) / ten_9;
0287         ++i;
0288     }
0289
0290     --i;
0291     auto offset = static_cast<std::size_t>(num_chars[i]);
0292     boost::charconv::detail::memcpy(first, buffer[i] + 10 - offset, offset);
0293
0294     while (i > 0)
0295     {
0296         --i;
0297         boost::charconv::detail::memcpy(first + offset, buffer[i] + 1, 9);
0298         offset += 9;
0299     }
0300
0301     return {first + converted_value_digits, std::errc()};
0302 }
0303
0304 // Conversion warning from shift operators with unsigned char
0305 #if defined(__GNUC__) && __GNUC__ >= 5
0306 # pragma GCC diagnostic push
0307 # pragma GCC diagnostic ignored "-Wconversion"
0308 #elif defined(__clang__)
0309 # pragma clang diagnostic push
0310 # pragma clang diagnostic ignored "-Wconversion"
0311 #endif
0312
0313 // All other bases
0314 // Use a simple lookup table to put together the Integer in character form
0315 template <typename Integer, typename Unsigned_Integer>
0316 BOOST_CHARCONV_CONSTEXPR to_chars_result to_chars_integer_impl(char* first, char* last, Integer value, int base) noexcept
0317 {
0318     if (!((first <= last) && (base >= 2 && base <= 36)))
0319     {
0320         return {last, std::errc::invalid_argument};
0321     }
0322
0323     if (value == 0)
0324     {
0325         *first++ = '0';
0326         return {first, std::errc()};
0327     }
0328
0329     Unsigned_Integer unsigned_value {};
0330     const auto unsigned_base = static_cast<Unsigned_Integer>(base);
0331
0332     BOOST_IF_CONSTEXPR (std::is_signed<Integer>::value)
0333     {
0334         if (value < 0)
0335         {
0336             *first++ = '-';
0337             unsigned_value = static_cast<Unsigned_Integer>(detail::apply_sign(value));
0338         }
0339         else
0340         {
0341             unsigned_value = static_cast<Unsigned_Integer>(value);
0342         }
0343     }
0344     else
0345     {
0346         unsigned_value = static_cast<Unsigned_Integer>(value);
0347     }
0348
0349     const std::ptrdiff_t output_length = last - first;
0350
0351     constexpr Unsigned_Integer zero = 48U; // Char for '0'
0352     constexpr auto buffer_size = sizeof(Unsigned_Integer) * CHAR_BIT;
0353     char buffer[buffer_size] {};
0354     const char* buffer_end = buffer + buffer_size;
0355     char* end = buffer + buffer_size - 1;
0356
0357     // Work from LSB to MSB
0358     switch (base)
0359     {
0360         case 2:
0361             while (unsigned_value != 0)
0362             {
0363                 *end-- = static_cast<char>(zero + (unsigned_value & 1U)); // 1<<1 - 1
0364                 unsigned_value >>= static_cast<Unsigned_Integer>(1);
0365             }
0366             break;
0367
0368         case 4:
0369             while (unsigned_value != 0)
0370             {
0371                 *end-- = static_cast<char>(zero + (unsigned_value & 3U)); // 1<<2 - 1
0372                 unsigned_value >>= static_cast<Unsigned_Integer>(2);
0373             }
0374             break;
0375
0376         case 8:
0377             while (unsigned_value != 0)
0378             {
0379                 *end-- = static_cast<char>(zero + (unsigned_value & 7U)); // 1<<3 - 1
0380                 unsigned_value >>= static_cast<Unsigned_Integer>(3);
0381             }
0382             break;
0383
0384         case 16:
0385             while (unsigned_value != 0)
0386             {
0387                 *end-- = digit_table[unsigned_value & 15U]; // 1<<4 - 1
0388                 unsigned_value >>= static_cast<Unsigned_Integer>(4);
0389             }
0390             break;
0391
0392         case 32:
0393             while (unsigned_value != 0)
0394             {
0395                 *end-- = digit_table[unsigned_value & 31U]; // 1<<5 - 1
0396                 unsigned_value >>= static_cast<Unsigned_Integer>(5);
0397             }
0398             break;
0399
0400         default:
0401             while (unsigned_value != 0)
0402             {
0403                 *end-- = digit_table[unsigned_value % unsigned_base];
0404                 unsigned_value /= unsigned_base;
0405             }
0406             break;
0407     }
0408
0409     const std::ptrdiff_t num_chars = buffer_end - end - 1;
0410
0411     if (num_chars > output_length)
0412     {
0413         return {last, std::errc::value_too_large};
0414     }
0415
0416     boost::charconv::detail::memcpy(first, buffer + (buffer_size - static_cast<unsigned long>(num_chars)),
0417                                     static_cast<std::size_t>(num_chars));
0418
0419     return {first + num_chars, std::errc()};
0420 }
0421
0422 #if defined(__GNUC__) && __GNUC__ >= 5
0423 # pragma GCC diagnostic pop
0424 #elif defined(__clang__)
0425 # pragma clang diagnostic pop
0426 #endif
0427
0428 #ifdef BOOST_MSVC
0429 # pragma warning(pop)
0430 #endif
0431
0432 template <typename Integer>
0433 BOOST_CHARCONV_CONSTEXPR to_chars_result to_chars_int(char* first, char* last, Integer value, int base = 10) noexcept
0434 {
0435     using Unsigned_Integer = typename std::make_unsigned<Integer>::type;
0436     if (base == 10)
0437     {
0438         return to_chars_integer_impl(first, last, value);
0439     }
0440
0441     return to_chars_integer_impl<Integer, Unsigned_Integer>(first, last, value, base);
0442 }
0443
0444 #ifdef BOOST_CHARCONV_HAS_INT128
0445 template <typename Integer>
0446 BOOST_CHARCONV_CONSTEXPR to_chars_result to_chars128(char* first, char* last, Integer value, int base = 10) noexcept
0447 {
0448     if (base == 10)
0449     {
0450         return to_chars_128integer_impl(first, last, value);
0451     }
0452
0453     return to_chars_integer_impl<Integer, boost::uint128_type>(first, last, value, base);
0454 }
0455 #endif
0456
0457 }}} // Namespaces
0458
0459 #endif //BOOST_CHARCONV_DETAIL_TO_CHARS_INTEGER_IMPL_HPP