1// Copyright 2023 Matt Borland
2// Distributed under the Boost Software License, Version 1.0.
3// https://www.boost.org/LICENSE_1_0.txt
4
5#ifndef BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
6#define BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
7
8// https://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer?page=1&tab=scoredesc#tab-top
9// https://graphics.stanford.edu/~seander/bithacks.html
10
11#include <boost/charconv/detail/config.hpp>
12#include <boost/charconv/detail/emulated128.hpp>
13#include <limits>
14#include <array>
15#include <cstdint>
16
17namespace boost { namespace charconv { namespace detail {
18
19// Generic solution
20template <typename T>
21BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(T x) noexcept
22{
23 int digits = 0;
24
25 while (x)
26 {
27 x /= 10;
28 ++digits;
29 }
30
31 return digits;
32}
33
34template <>
35BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(std::uint32_t x) noexcept
36{
37 if (x >= UINT32_C(10000))
38 {
39 if (x >= UINT32_C(10000000))
40 {
41 if (x >= UINT32_C(100000000))
42 {
43 if (x >= UINT32_C(1000000000))
44 {
45 return 10;
46 }
47 return 9;
48 }
49 return 8;
50 }
51
52 else if (x >= UINT32_C(100000))
53 {
54 if (x >= UINT32_C(1000000))
55 {
56 return 7;
57 }
58 return 6;
59 }
60 return 5;
61 }
62 else if (x >= UINT32_C(100))
63 {
64 if (x >= UINT32_C(1000))
65 {
66 return 4;
67 }
68 return 3;
69 }
70 else if (x >= UINT32_C(10))
71 {
72 return 2;
73 }
74
75 return 1;
76}
77
78template <>
79BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(std::uint64_t x) noexcept
80{
81 if (x >= UINT64_C(10000000000))
82 {
83 if (x >= UINT64_C(100000000000000))
84 {
85 if (x >= UINT64_C(10000000000000000))
86 {
87 if (x >= UINT64_C(100000000000000000))
88 {
89 if (x >= UINT64_C(1000000000000000000))
90 {
91 if (x >= UINT64_C(10000000000000000000))
92 {
93 return 20;
94 }
95 return 19;
96 }
97 return 18;
98 }
99 return 17;
100 }
101 else if (x >= UINT64_C(1000000000000000))
102 {
103 return 16;
104 }
105 return 15;
106 }
107 if (x >= UINT64_C(1000000000000))
108 {
109 if (x >= UINT64_C(10000000000000))
110 {
111 return 14;
112 }
113 return 13;
114 }
115 if (x >= UINT64_C(100000000000))
116 {
117 return 12;
118 }
119 return 11;
120 }
121 else if (x >= UINT64_C(100000))
122 {
123 if (x >= UINT64_C(10000000))
124 {
125 if (x >= UINT64_C(100000000))
126 {
127 if (x >= UINT64_C(1000000000))
128 {
129 return 10;
130 }
131 return 9;
132 }
133 return 8;
134 }
135 if (x >= UINT64_C(1000000))
136 {
137 return 7;
138 }
139 return 6;
140 }
141 if (x >= UINT64_C(100))
142 {
143 if (x >= UINT64_C(1000))
144 {
145 if (x >= UINT64_C(10000))
146 {
147 return 5;
148 }
149 return 4;
150 }
151 return 3;
152 }
153 if (x >= UINT64_C(10))
154 {
155 return 2;
156 }
157 return 1;
158}
159
160#ifdef BOOST_MSVC
161# pragma warning(push)
162# pragma warning(disable: 4307) // MSVC 14.1 warns of intergral constant overflow
163#endif
164
165BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(uint128 x) noexcept
166{
167 if (x.high == 0)
168 {
169 return num_digits(x: x.low);
170 }
171
172 BOOST_CHARCONV_CXX14_CONSTEXPR_NO_INLINE uint128 digits_39 = static_cast<uint128>(UINT64_C(10000000000000000000)) *
173 static_cast<uint128>(UINT64_C(10000000000000000000));
174 uint128 current_power_of_10 = digits_39;
175
176 for (int i = 39; i > 0; --i)
177 {
178 if (x >= current_power_of_10)
179 {
180 return i;
181 }
182
183 current_power_of_10 /= 10U;
184 }
185
186 return 1;
187}
188
189#ifdef BOOST_MSVC
190# pragma warning(pop)
191#endif
192
193#ifdef BOOST_CHARCONV_HAS_INT128
194static constexpr std::array<std::uint64_t, 20> powers_of_10 =
195{._M_elems: {
196 UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000), UINT64_C(100000), UINT64_C(1000000),
197 UINT64_C(10000000), UINT64_C(100000000), UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000),
198 UINT64_C(1000000000000), UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000),
199 UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000), UINT64_C(10000000000000000000)
200}};
201
202// Assume that if someone is using 128 bit ints they are favoring the top end of the range
203// Max value is 340,282,366,920,938,463,463,374,607,431,768,211,455 (39 digits)
204BOOST_CHARCONV_CXX14_CONSTEXPR int num_digits(boost::uint128_type x) noexcept
205{
206 // There is no literal for boost::uint128_type, so we need to calculate them using the max value of the
207 // std::uint64_t powers of 10
208 constexpr boost::uint128_type digits_39 = static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)) *
209 static_cast<boost::uint128_type>(UINT64_C(10000000000000000000));
210
211 constexpr boost::uint128_type digits_38 = digits_39 / 10;
212 constexpr boost::uint128_type digits_37 = digits_38 / 10;
213 constexpr boost::uint128_type digits_36 = digits_37 / 10;
214 constexpr boost::uint128_type digits_35 = digits_36 / 10;
215 constexpr boost::uint128_type digits_34 = digits_35 / 10;
216 constexpr boost::uint128_type digits_33 = digits_34 / 10;
217 constexpr boost::uint128_type digits_32 = digits_33 / 10;
218 constexpr boost::uint128_type digits_31 = digits_32 / 10;
219 constexpr boost::uint128_type digits_30 = digits_31 / 10;
220 constexpr boost::uint128_type digits_29 = digits_30 / 10;
221 constexpr boost::uint128_type digits_28 = digits_29 / 10;
222 constexpr boost::uint128_type digits_27 = digits_28 / 10;
223 constexpr boost::uint128_type digits_26 = digits_27 / 10;
224 constexpr boost::uint128_type digits_25 = digits_26 / 10;
225 constexpr boost::uint128_type digits_24 = digits_25 / 10;
226 constexpr boost::uint128_type digits_23 = digits_24 / 10;
227 constexpr boost::uint128_type digits_22 = digits_23 / 10;
228 constexpr boost::uint128_type digits_21 = digits_22 / 10;
229
230 return (x >= digits_39) ? 39 :
231 (x >= digits_38) ? 38 :
232 (x >= digits_37) ? 37 :
233 (x >= digits_36) ? 36 :
234 (x >= digits_35) ? 35 :
235 (x >= digits_34) ? 34 :
236 (x >= digits_33) ? 33 :
237 (x >= digits_32) ? 32 :
238 (x >= digits_31) ? 31 :
239 (x >= digits_30) ? 30 :
240 (x >= digits_29) ? 29 :
241 (x >= digits_28) ? 28 :
242 (x >= digits_27) ? 27 :
243 (x >= digits_26) ? 26 :
244 (x >= digits_25) ? 25 :
245 (x >= digits_24) ? 24 :
246 (x >= digits_23) ? 23 :
247 (x >= digits_22) ? 22 :
248 (x >= digits_21) ? 21 :
249 (x >= powers_of_10[19]) ? 20 :
250 (x >= powers_of_10[18]) ? 19 :
251 (x >= powers_of_10[17]) ? 18 :
252 (x >= powers_of_10[16]) ? 17 :
253 (x >= powers_of_10[15]) ? 16 :
254 (x >= powers_of_10[14]) ? 15 :
255 (x >= powers_of_10[13]) ? 14 :
256 (x >= powers_of_10[12]) ? 13 :
257 (x >= powers_of_10[11]) ? 12 :
258 (x >= powers_of_10[10]) ? 11 :
259 (x >= powers_of_10[9]) ? 10 :
260 (x >= powers_of_10[8]) ? 9 :
261 (x >= powers_of_10[7]) ? 8 :
262 (x >= powers_of_10[6]) ? 7 :
263 (x >= powers_of_10[5]) ? 6 :
264 (x >= powers_of_10[4]) ? 5 :
265 (x >= powers_of_10[3]) ? 4 :
266 (x >= powers_of_10[2]) ? 3 :
267 (x >= powers_of_10[1]) ? 2 :
268 (x >= powers_of_10[0]) ? 1 : 0;
269}
270#endif
271
272}}} // Namespace boost::charconv::detail
273
274#endif // BOOST_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
275

source code of boost/libs/charconv/include/boost/charconv/detail/integer_search_trees.hpp