charconv/detail/integer_search_trees.hpp

0001 // Copyright 2023 Matt Borland
0002 // Distributed under the Boost Software License, Version 1.0.
0003 // https://www.boost.org/LICENSE_1_0.txt
0004
0005 #ifndef BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
0006 #define BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
0007
0008 // https://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer?page=1&tab=scoredesc#tab-top
0009 // https://graphics.stanford.edu/~seander/bithacks.html
0010
0011 #include <boost/charconv/detail/config.hpp>
0012 #include <boost/charconv/detail/emulated128.hpp>
0013 #include <limits>
0014 #include <array>
0015 #include <cstdint>
0016
0017 namespace boost { namespace charconv { namespace detail {
0018
0019 // Generic solution
0020 template <typename T>
0021 BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(T x) noexcept
0022 {
0023     int digits = 0;
0024
0025     while (x)
0026     {
0027         x /= 10;
0028         ++digits;
0029     }
0030
0031     return digits;
0032 }
0033
0034 template <>
0035 BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(std::uint32_t x) noexcept
0036 {
0037     if (x >= UINT32_C(10000))
0038     {
0039         if (x >= UINT32_C(10000000))
0040         {
0041             if (x >= UINT32_C(100000000))
0042             {
0043                 if (x >= UINT32_C(1000000000))
0044                 {
0045                     return 10;
0046                 }
0047                 return 9;
0048             }
0049             return 8;
0050         }
0051
0052         else if (x >= UINT32_C(100000))
0053         {
0054             if (x >= UINT32_C(1000000))
0055             {
0056                 return 7;
0057             }
0058             return 6;
0059         }
0060         return 5;
0061     }
0062     else if (x >= UINT32_C(100))
0063     {
0064         if (x >= UINT32_C(1000))
0065         {
0066             return 4;
0067         }
0068         return 3;
0069     }
0070     else if (x >= UINT32_C(10))
0071     {
0072         return 2;
0073     }
0074
0075     return 1;
0076 }
0077
0078 template <>
0079 BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(std::uint64_t x) noexcept
0080 {
0081     if (x >= UINT64_C(10000000000))
0082     {
0083         if (x >= UINT64_C(100000000000000))
0084         {
0085             if (x >= UINT64_C(10000000000000000))
0086             {
0087                 if (x >= UINT64_C(100000000000000000))
0088                 {
0089                     if (x >= UINT64_C(1000000000000000000))
0090                     {
0091                         if (x >= UINT64_C(10000000000000000000))
0092                         {
0093                             return 20;
0094                         }
0095                         return 19;
0096                     }
0097                     return 18;
0098                 }
0099                 return 17;
0100             }
0101             else if (x >= UINT64_C(1000000000000000))
0102             {
0103                 return 16;
0104             }
0105             return 15;
0106         }
0107         if (x >= UINT64_C(1000000000000))
0108         {
0109             if (x >= UINT64_C(10000000000000))
0110             {
0111                 return 14;
0112             }
0113             return 13;
0114         }
0115         if (x >= UINT64_C(100000000000))
0116         {
0117             return 12;
0118         }
0119         return 11;
0120     }
0121     else if (x >= UINT64_C(100000))
0122     {
0123         if (x >= UINT64_C(10000000))
0124         {
0125             if (x >= UINT64_C(100000000))
0126             {
0127                 if (x >= UINT64_C(1000000000))
0128                 {
0129                     return 10;
0130                 }
0131                 return 9;
0132             }
0133             return 8;
0134         }
0135         if (x >= UINT64_C(1000000))
0136         {
0137             return 7;
0138         }
0139         return 6;
0140     }
0141     if (x >= UINT64_C(100))
0142     {
0143         if (x >= UINT64_C(1000))
0144         {
0145             if (x >= UINT64_C(10000))
0146             {
0147                 return 5;
0148             }
0149             return 4;
0150         }
0151         return 3;
0152     }
0153     if (x >= UINT64_C(10))
0154     {
0155         return 2;
0156     }
0157     return 1;
0158 }
0159
0160 #ifdef BOOST_MSVC
0161 # pragma warning(push)
0162 # pragma warning(disable: 4307) // MSVC 14.1 warns of intergral constant overflow
0163 #endif
0164
0165 BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(uint128 x) noexcept
0166 {
0167     if (x.high == 0)
0168     {
0169         return num_digits(x.low);
0170     }
0171
0172     BOOST_CHARCONV_CXX14_CONSTEXPR_NO_INLINE uint128 digits_39 = static_cast<uint128>(UINT64_C(10000000000000000000)) *
0173                                                                  static_cast<uint128>(UINT64_C(10000000000000000000));
0174     uint128 current_power_of_10 = digits_39;
0175
0176     for (int i = 39; i > 0; --i)
0177     {
0178         if (x >= current_power_of_10)
0179         {
0180             return i;
0181         }
0182
0183         current_power_of_10 /= 10U;
0184     }
0185
0186     return 1;
0187 }
0188
0189 #ifdef BOOST_MSVC
0190 # pragma warning(pop)
0191 #endif
0192
0193 #ifdef BOOST_CHARCONV_HAS_INT128
0194 static constexpr std::array<std::uint64_t, 20> powers_of_10 =
0195 {{
0196     UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000), UINT64_C(100000), UINT64_C(1000000),
0197     UINT64_C(10000000), UINT64_C(100000000), UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000),
0198     UINT64_C(1000000000000), UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000),
0199     UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000), UINT64_C(10000000000000000000)
0200 }};
0201
0202 // Assume that if someone is using 128 bit ints they are favoring the top end of the range
0203 // Max value is 340,282,366,920,938,463,463,374,607,431,768,211,455 (39 digits)
0204 BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(boost::uint128_type x) noexcept
0205 {
0206     // There is no literal for boost::uint128_type, so we need to calculate them using the max value of the
0207     // std::uint64_t powers of 10
0208     constexpr boost::uint128_type digits_39 = static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)) *
0209                                               static_cast<boost::uint128_type>(UINT64_C(10000000000000000000));
0210
0211     constexpr boost::uint128_type digits_38 = digits_39 / 10;
0212     constexpr boost::uint128_type digits_37 = digits_38 / 10;
0213     constexpr boost::uint128_type digits_36 = digits_37 / 10;
0214     constexpr boost::uint128_type digits_35 = digits_36 / 10;
0215     constexpr boost::uint128_type digits_34 = digits_35 / 10;
0216     constexpr boost::uint128_type digits_33 = digits_34 / 10;
0217     constexpr boost::uint128_type digits_32 = digits_33 / 10;
0218     constexpr boost::uint128_type digits_31 = digits_32 / 10;
0219     constexpr boost::uint128_type digits_30 = digits_31 / 10;
0220     constexpr boost::uint128_type digits_29 = digits_30 / 10;
0221     constexpr boost::uint128_type digits_28 = digits_29 / 10;
0222     constexpr boost::uint128_type digits_27 = digits_28 / 10;
0223     constexpr boost::uint128_type digits_26 = digits_27 / 10;
0224     constexpr boost::uint128_type digits_25 = digits_26 / 10;
0225     constexpr boost::uint128_type digits_24 = digits_25 / 10;
0226     constexpr boost::uint128_type digits_23 = digits_24 / 10;
0227     constexpr boost::uint128_type digits_22 = digits_23 / 10;
0228     constexpr boost::uint128_type digits_21 = digits_22 / 10;
0229
0230     return (x >= digits_39) ? 39 :
0231            (x >= digits_38) ? 38 :
0232            (x >= digits_37) ? 37 :
0233            (x >= digits_36) ? 36 :
0234            (x >= digits_35) ? 35 :
0235            (x >= digits_34) ? 34 :
0236            (x >= digits_33) ? 33 :
0237            (x >= digits_32) ? 32 :
0238            (x >= digits_31) ? 31 :
0239            (x >= digits_30) ? 30 :
0240            (x >= digits_29) ? 29 :
0241            (x >= digits_28) ? 28 :
0242            (x >= digits_27) ? 27 :
0243            (x >= digits_26) ? 26 :
0244            (x >= digits_25) ? 25 :
0245            (x >= digits_24) ? 24 :
0246            (x >= digits_23) ? 23 :
0247            (x >= digits_22) ? 22 :
0248            (x >= digits_21) ? 21 :
0249            (x >= powers_of_10[19]) ? 20 :
0250            (x >= powers_of_10[18]) ? 19 :
0251            (x >= powers_of_10[17]) ? 18 :
0252            (x >= powers_of_10[16]) ? 17 :
0253            (x >= powers_of_10[15]) ? 16 :
0254            (x >= powers_of_10[14]) ? 15 :
0255            (x >= powers_of_10[13]) ? 14 :
0256            (x >= powers_of_10[12]) ? 13 :
0257            (x >= powers_of_10[11]) ? 12 :
0258            (x >= powers_of_10[10]) ? 11 :
0259            (x >= powers_of_10[9])  ? 10 :
0260            (x >= powers_of_10[8])  ?  9 :
0261            (x >= powers_of_10[7])  ?  8 :
0262            (x >= powers_of_10[6])  ?  7 :
0263            (x >= powers_of_10[5])  ?  6 :
0264            (x >= powers_of_10[4])  ?  5 :
0265            (x >= powers_of_10[3])  ?  4 :
0266            (x >= powers_of_10[2])  ?  3 :
0267            (x >= powers_of_10[1])  ?  2 :
0268            (x >= powers_of_10[0])  ?  1 : 0;
0269 }
0270 #endif
0271
0272 }}} // Namespace boost::charconv::detail
0273
0274 #endif // BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP