Root/detail / charconv / detail / integer_search_trees.hpp
Prev Index Next

detail/charconv/detail/integer_search_trees.hpp

0.0% Lines (0/40) 0.0% Functions (0/1) 0.0% Branches (0/38)
detail/charconv/detail/integer_search_trees.hpp
Line Hits Source Code
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_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
6 #define BOOST_JSON_DETAIL_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/json/detail/charconv/detail/config.hpp>
12 #include <limits>
13 #include <array>
14 #include <cstdint>
15
16 namespace boost { namespace json { namespace detail { namespace charconv { namespace detail {
17
18 // Generic solution
19 template <typename T>
20 BOOST_JSON_CXX14_CONSTEXPR int num_digits(T x) noexcept
21 {
22 int digits = 0;
23
24 while (x)
25 {
26 x /= 10;
27 ++digits;
28 }
29
30 return digits;
31 }
32
33 template <>
34 BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint32_t x) noexcept
35 {
36 if (x >= UINT32_C(10000))
37 {
38 if (x >= UINT32_C(10000000))
39 {
40 if (x >= UINT32_C(100000000))
41 {
42 if (x >= UINT32_C(1000000000))
43 {
44 return 10;
45 }
46 return 9;
47 }
48 return 8;
49 }
50
51 else if (x >= UINT32_C(100000))
52 {
53 if (x >= UINT32_C(1000000))
54 {
55 return 7;
56 }
57 return 6;
58 }
59 return 5;
60 }
61 else if (x >= UINT32_C(100))
62 {
63 if (x >= UINT32_C(1000))
64 {
65 return 4;
66 }
67 return 3;
68 }
69 else if (x >= UINT32_C(10))
70 {
71 return 2;
72 }
73
74 return 1;
75 }
76
77 template <>
78 ✗ BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint64_t x) noexcept
79 {
80 ✗ if (x >= UINT64_C(10000000000))
81 {
82 ✗ if (x >= UINT64_C(100000000000000))
83 {
84 ✗ if (x >= UINT64_C(10000000000000000))
85 {
86 ✗ if (x >= UINT64_C(100000000000000000))
87 {
88 ✗ if (x >= UINT64_C(1000000000000000000))
89 {
90 ✗ if (x >= UINT64_C(10000000000000000000))
91 {
92 ✗ return 20;
93 }
94 ✗ return 19;
95 }
96 ✗ return 18;
97 }
98 ✗ return 17;
99 }
100 ✗ else if (x >= UINT64_C(1000000000000000))
101 {
102 ✗ return 16;
103 }
104 ✗ return 15;
105 }
106 ✗ if (x >= UINT64_C(1000000000000))
107 {
108 ✗ if (x >= UINT64_C(10000000000000))
109 {
110 ✗ return 14;
111 }
112 ✗ return 13;
113 }
114 ✗ if (x >= UINT64_C(100000000000))
115 {
116 ✗ return 12;
117 }
118 ✗ return 11;
119 }
120 ✗ else if (x >= UINT64_C(100000))
121 {
122 ✗ if (x >= UINT64_C(10000000))
123 {
124 ✗ if (x >= UINT64_C(100000000))
125 {
126 ✗ if (x >= UINT64_C(1000000000))
127 {
128 ✗ return 10;
129 }
130 ✗ return 9;
131 }
132 ✗ return 8;
133 }
134 ✗ if (x >= UINT64_C(1000000))
135 {
136 ✗ return 7;
137 }
138 ✗ return 6;
139 }
140 ✗ if (x >= UINT64_C(100))
141 {
142 ✗ if (x >= UINT64_C(1000))
143 {
144 ✗ if (x >= UINT64_C(10000))
145 {
146 ✗ return 5;
147 }
148 ✗ return 4;
149 }
150 ✗ return 3;
151 }
152 ✗ if (x >= UINT64_C(10))
153 {
154 ✗ return 2;
155 }
156 ✗ return 1;
157 }
158
159 #ifdef BOOST_HAS_INT128
160 static constexpr std::array<std::uint64_t, 20> powers_of_10 =
161 {{
162 UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000), UINT64_C(100000), UINT64_C(1000000),
163 UINT64_C(10000000), UINT64_C(100000000), UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000),
164 UINT64_C(1000000000000), UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000),
165 UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000), UINT64_C(10000000000000000000)
166 }};
167
168 // Assume that if someone is using 128 bit ints they are favoring the top end of the range
169 // Max value is 340,282,366,920,938,463,463,374,607,431,768,211,455 (39 digits)
170 BOOST_JSON_CXX14_CONSTEXPR int num_digits(boost::uint128_type x) noexcept
171 {
172 // There is not literal for boost::uint128_type so we need to calculate them using the max value of the
173 // std::uint64_t powers of 10
174 constexpr boost::uint128_type digits_39 = static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)) *
175 static_cast<boost::uint128_type>(UINT64_C(10000000000000000000));
176
177 constexpr boost::uint128_type digits_38 = digits_39 / 10;
178 constexpr boost::uint128_type digits_37 = digits_38 / 10;
179 constexpr boost::uint128_type digits_36 = digits_37 / 10;
180 constexpr boost::uint128_type digits_35 = digits_36 / 10;
181 constexpr boost::uint128_type digits_34 = digits_35 / 10;
182 constexpr boost::uint128_type digits_33 = digits_34 / 10;
183 constexpr boost::uint128_type digits_32 = digits_33 / 10;
184 constexpr boost::uint128_type digits_31 = digits_32 / 10;
185 constexpr boost::uint128_type digits_30 = digits_31 / 10;
186 constexpr boost::uint128_type digits_29 = digits_30 / 10;
187 constexpr boost::uint128_type digits_28 = digits_29 / 10;
188 constexpr boost::uint128_type digits_27 = digits_28 / 10;
189 constexpr boost::uint128_type digits_26 = digits_27 / 10;
190 constexpr boost::uint128_type digits_25 = digits_26 / 10;
191 constexpr boost::uint128_type digits_24 = digits_25 / 10;
192 constexpr boost::uint128_type digits_23 = digits_24 / 10;
193 constexpr boost::uint128_type digits_22 = digits_23 / 10;
194 constexpr boost::uint128_type digits_21 = digits_22 / 10;
195
196 return (x >= digits_39) ? 39 :
197 (x >= digits_38) ? 38 :
198 (x >= digits_37) ? 37 :
199 (x >= digits_36) ? 36 :
200 (x >= digits_35) ? 35 :
201 (x >= digits_34) ? 34 :
202 (x >= digits_33) ? 33 :
203 (x >= digits_32) ? 32 :
204 (x >= digits_31) ? 31 :
205 (x >= digits_30) ? 30 :
206 (x >= digits_29) ? 29 :
207 (x >= digits_28) ? 28 :
208 (x >= digits_27) ? 27 :
209 (x >= digits_26) ? 26 :
210 (x >= digits_25) ? 25 :
211 (x >= digits_24) ? 24 :
212 (x >= digits_23) ? 23 :
213 (x >= digits_22) ? 22 :
214 (x >= digits_21) ? 21 :
215 (x >= powers_of_10[19]) ? 20 :
216 (x >= powers_of_10[18]) ? 19 :
217 (x >= powers_of_10[17]) ? 18 :
218 (x >= powers_of_10[16]) ? 17 :
219 (x >= powers_of_10[15]) ? 16 :
220 (x >= powers_of_10[14]) ? 15 :
221 (x >= powers_of_10[13]) ? 14 :
222 (x >= powers_of_10[12]) ? 13 :
223 (x >= powers_of_10[11]) ? 12 :
224 (x >= powers_of_10[10]) ? 11 :
225 (x >= powers_of_10[9]) ? 10 :
226 (x >= powers_of_10[8]) ? 9 :
227 (x >= powers_of_10[7]) ? 8 :
228 (x >= powers_of_10[6]) ? 7 :
229 (x >= powers_of_10[5]) ? 6 :
230 (x >= powers_of_10[4]) ? 5 :
231 (x >= powers_of_10[3]) ? 4 :
232 (x >= powers_of_10[2]) ? 3 :
233 (x >= powers_of_10[1]) ? 2 :
234 (x >= powers_of_10[0]) ? 1 : 0;
235 }
236 #endif
237
238 }}}}} // Namespace boost::json::detail::charconv::detail
239
240 #endif // BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
241