Line data Source code
1 : // Copyright 2020-2022 Junekey Jeon
2 : //
3 : // The contents of this file may be used under the terms of
4 : // the Apache License v2.0 with LLVM Exceptions.
5 : //
6 : // (See accompanying file LICENSE-Apache or copy at
7 : // https://llvm.org/foundation/relicensing/LICENSE.txt)
8 : //
9 : // Alternatively, the contents of this file may be used under the terms of
10 : // the Boost Software License, Version 1.0.
11 : // (See accompanying file LICENSE-Boost or copy at
12 : // https://www.boost.org/LICENSE_1_0.txt)
13 : //
14 : // Unless required by applicable law or agreed to in writing, this software
15 : // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 : // KIND, either express or implied.
17 : //
18 : // Some parts are copied from Dragonbox project.
19 : //
20 : // Copyright 2023 Matt Borland
21 : // Distributed under the Boost Software License, Version 1.0.
22 : // https://www.boost.org/LICENSE_1_0.txt
23 :
24 : #ifndef BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_COMMON_HPP
25 : #define BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_COMMON_HPP
26 :
27 : #include <boost/json/detail/charconv/detail/config.hpp>
28 : #include <boost/json/detail/dragonbox/bit_layouts.hpp>
29 : #include <boost/json/detail/dragonbox/emulated128.hpp>
30 : #include <boost/core/bit.hpp>
31 : #include <type_traits>
32 : #include <limits>
33 : #include <cstdint>
34 : #include <cstring>
35 : #include <cstddef>
36 : #include <climits>
37 :
38 : namespace boost {
39 : namespace json {
40 : namespace detail {
41 :
42 : template <typename T>
43 : struct physical_bits
44 : {
45 : static constexpr std::size_t value = sizeof(T) * CHAR_BIT;
46 : };
47 :
48 : template <typename T>
49 : struct value_bits
50 : {
51 : static constexpr std::size_t value = std::numeric_limits<typename std::enable_if<std::is_unsigned<T>::value, T>::type>::digits;
52 : };
53 :
54 : #ifdef BOOST_NO_CXX17_INLINE_VARIABLES
55 :
56 : template <typename T> constexpr std::size_t physical_bits<T>::value;
57 : template <typename T> constexpr std::size_t value_bits<T>::value;
58 :
59 : #endif
60 :
61 : // A floating-point traits class defines ways to interpret a bit pattern of given size as an
62 : // encoding of floating-point number. This is a default implementation of such a traits class,
63 : // supporting ways to interpret 32-bits into a binary32-encoded floating-point number and to
64 : // interpret 64-bits into a binary64-encoded floating-point number. Users might specialize this
65 : // class to change the default behavior for certain types.
66 : template <typename T>
67 : struct default_float_traits
68 : {
69 : // I don't know if there is a truly reliable way of detecting
70 : // IEEE-754 binary32/binary64 formats; I just did my best here.
71 : static_assert(std::numeric_limits<T>::is_iec559 && std::numeric_limits<T>::radix == 2 &&
72 : (detail::physical_bits<T>::value == 32 || detail::physical_bits<T>::value == 64),
73 : "default_ieee754_traits only works for 32-bits or 64-bits types "
74 : "supporting binary32 or binary64 formats!");
75 :
76 : // The type that is being viewed.
77 : using type = T;
78 :
79 : // Refers to the format specification class.
80 : using format =
81 : typename std::conditional<detail::physical_bits<T>::value == 32, detail::ieee754_binary32, detail::ieee754_binary64>::type;
82 :
83 : // Defines an unsignedeger type that is large enough to carry a variable of type T.
84 : // Most of the operations will be done on this integer type.
85 : using carrier_uint = typename std::conditional<detail::physical_bits<T>::value == 32, std::uint32_t, std::uint64_t>::type;
86 :
87 : static_assert(sizeof(carrier_uint) == sizeof(T), "carrier_uint must be T");
88 :
89 : // Number of bits in the above unsignedeger type.
90 : static constexpr int carrier_bits = static_cast<int>(detail::physical_bits<carrier_uint>::value);
91 :
92 : // Convert from carrier_uint into the original type.
93 : // Depending on the floating-point encoding format, this operation might not be possible for
94 : // some specific bit patterns. However, the contract is that u always denotes a
95 : // valid bit pattern, so this function must be assumed to be noexcept.
96 : static T carrier_to_float(carrier_uint u) noexcept
97 : {
98 : T x;
99 : std::memcpy(&x, &u, sizeof(carrier_uint));
100 : return x;
101 : }
102 :
103 : // Same as above.
104 : static carrier_uint float_to_carrier(T x) noexcept
105 : {
106 : carrier_uint u;
107 : std::memcpy(&u, &x, sizeof(carrier_uint));
108 : return u;
109 : }
110 :
111 : // Extract exponent bits from a bit pattern.
112 : // The result must be aligned to the LSB so that there is no additional zero paddings
113 : // on the right. This function does not do bias adjustment.
114 : static constexpr unsigned extract_exponent_bits(carrier_uint u) noexcept
115 : {
116 : return static_cast<unsigned>(u >> format::exponent_bits) & static_cast<unsigned>((1U << format::exponent_bits) - 1);
117 : }
118 :
119 : // Extract significand bits from a bit pattern.
120 : // The result must be aligned to the LSB so that there is no additional zero paddings
121 : // on the right. The result does not contain the implicit bit.
122 : static constexpr carrier_uint extract_significand_bits(carrier_uint u) noexcept
123 : {
124 : return static_cast<carrier_uint>(u & static_cast<carrier_uint>((static_cast<carrier_uint>(1) << format::significand_bits) - 1));
125 : }
126 :
127 : // Remove the exponent bits and extract significand bits together with the sign bit.
128 : static constexpr carrier_uint remove_exponent_bits(carrier_uint u, unsigned exponent_bits) noexcept
129 : {
130 : return u ^ (static_cast<carrier_uint>(exponent_bits) << format::significand_bits);
131 : }
132 :
133 : // Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
134 : static constexpr carrier_uint remove_sign_bit_and_shift(carrier_uint u) noexcept
135 : {
136 : return static_cast<carrier_uint>(static_cast<carrier_uint>(u) << 1);
137 : }
138 :
139 : // The actual value of exponent is obtained by adding this value to the extracted exponent bits
140 : static constexpr int exponent_bias = 1 - (1 << (carrier_bits - format::significand_bits - 2));
141 :
142 : // Obtain the actual value of the binary exponent from the extracted exponent bits.
143 : static constexpr int binary_exponent(unsigned exponent_bits) noexcept
144 : {
145 : return exponent_bits == 0 ? format::min_exponent : static_cast<int>(exponent_bits) + format::exponent_bias;
146 : }
147 :
148 : // Obtain the actual value of the binary exponent from the extracted significand bits and
149 : // exponent bits.
150 : static constexpr carrier_uint binary_significand(carrier_uint significand_bits, unsigned exponent_bits) noexcept
151 : {
152 : return exponent_bits == 0 ? significand_bits : (significand_bits | (static_cast<carrier_uint>(1) << format::significand_bits));
153 : }
154 :
155 :
156 : // Various boolean observer functions
157 :
158 : static constexpr bool is_nonzero(carrier_uint u) noexcept { return (u << 1) != 0; }
159 :
160 : static constexpr bool is_positive(carrier_uint u) noexcept
161 : {
162 : return u < static_cast<carrier_uint>(1) << (format::significand_bits + format::exponent_bits);
163 : }
164 :
165 : static constexpr bool is_negative(carrier_uint u) noexcept { return !is_positive(u); }
166 :
167 : static constexpr bool is_finite(unsigned exponent_bits) noexcept
168 : {
169 : //constexpr unsigned exponent_bits_all_set = (1u << format::exponent_bits) - 1;
170 : return exponent_bits != (1u << format::exponent_bits) - 1;
171 : }
172 :
173 : static constexpr bool has_all_zero_significand_bits(carrier_uint u) noexcept
174 : {
175 : return (u << 1) == 0;
176 : }
177 :
178 : static constexpr bool has_even_significand_bits(carrier_uint u) noexcept
179 : {
180 : return u % 2 == 0;
181 : }
182 : };
183 :
184 : // Convenient wrappers for floating-point traits classes.
185 : // In order to reduce the argument passing overhead, these classes should be as simple as
186 : // possible (e.g., no inheritance, no private non-static data member, etc.; this is an
187 : // unfortunate fact about common ABI convention).
188 :
189 : template <typename T, typename Traits = default_float_traits<T>>
190 : struct float_bits;
191 :
192 : template <typename T, typename Traits = default_float_traits<T>>
193 : struct signed_significand_bits;
194 :
195 : template <typename T, typename Traits>
196 : struct float_bits
197 : {
198 : using type = T;
199 : using traits_type = Traits;
200 : using carrier_uint = typename traits_type::carrier_uint;
201 :
202 : carrier_uint u;
203 :
204 : float_bits() = default;
205 : constexpr explicit float_bits(carrier_uint bit_pattern) noexcept : u{bit_pattern} {}
206 : constexpr explicit float_bits(T float_value) noexcept : u{traits_type::float_to_carrier(float_value)} {}
207 :
208 : constexpr T to_float() const noexcept { return traits_type::carrier_to_float(u); }
209 :
210 : // Extract exponent bits from a bit pattern.
211 : // The result must be aligned to the LSB so that there is no additional zero paddings
212 : // on the right. This function does not do bias adjustment.
213 : constexpr unsigned extract_exponent_bits() const noexcept
214 : {
215 : return traits_type::extract_exponent_bits(u);
216 : }
217 :
218 : // Extract significand bits from a bit pattern.
219 : // The result must be aligned to the LSB so that there is no additional zero paddings
220 : // on the right. The result does not contain the implicit bit.
221 : constexpr carrier_uint extract_significand_bits() const noexcept
222 : {
223 : return traits_type::extract_significand_bits(u);
224 : }
225 :
226 : // Remove the exponent bits and extract significand bits together with the sign bit.
227 : constexpr signed_significand_bits<type, traits_type> remove_exponent_bits(unsigned exponent_bits) const noexcept
228 : {
229 : return signed_significand_bits<type, traits_type>(traits_type::remove_exponent_bits(u, exponent_bits));
230 : }
231 :
232 : // Obtain the actual value of the binary exponent from the extracted exponent bits.
233 : static constexpr int binary_exponent(unsigned exponent_bits) noexcept
234 : {
235 : return traits_type::binary_exponent(exponent_bits);
236 : }
237 :
238 : constexpr int binary_exponent() const noexcept
239 : {
240 : return binary_exponent(extract_exponent_bits());
241 : }
242 :
243 : // Obtain the actual value of the binary exponent from the extracted significand bits and
244 : // exponent bits.
245 : static constexpr carrier_uint binary_significand(carrier_uint significand_bits, unsigned exponent_bits) noexcept
246 : {
247 : return traits_type::binary_significand(significand_bits, exponent_bits);
248 : }
249 :
250 : constexpr carrier_uint binary_significand() const noexcept
251 : {
252 : return binary_significand(extract_significand_bits(), extract_exponent_bits());
253 : }
254 :
255 : constexpr bool is_nonzero() const noexcept { return traits_type::is_nonzero(u); }
256 :
257 : constexpr bool is_positive() const noexcept { return traits_type::is_positive(u); }
258 :
259 : constexpr bool is_negative() const noexcept { return traits_type::is_negative(u); }
260 :
261 : constexpr bool is_finite(unsigned exponent_bits) const noexcept { return traits_type::is_finite(exponent_bits); }
262 :
263 : constexpr bool is_finite() const noexcept { return traits_type::is_finite(extract_exponent_bits()); }
264 :
265 : constexpr bool has_even_significand_bits() const noexcept { return traits_type::has_even_significand_bits(u); }
266 : };
267 :
268 : template <typename T, typename Traits>
269 : struct signed_significand_bits
270 : {
271 : using type = T;
272 : using traits_type = Traits;
273 : using carrier_uint = typename traits_type::carrier_uint;
274 :
275 : carrier_uint u;
276 :
277 : signed_significand_bits() = default;
278 : constexpr explicit signed_significand_bits(carrier_uint bit_pattern) noexcept
279 : : u{bit_pattern} {}
280 :
281 : // Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
282 : constexpr carrier_uint remove_sign_bit_and_shift() const noexcept
283 : {
284 : return traits_type::remove_sign_bit_and_shift(u);
285 : }
286 :
287 : constexpr bool is_positive() const noexcept { return traits_type::is_positive(u); }
288 :
289 : constexpr bool is_negative() const noexcept { return traits_type::is_negative(u); }
290 :
291 : constexpr bool has_all_zero_significand_bits() const noexcept
292 : {
293 : return traits_type::has_all_zero_significand_bits(u);
294 : }
295 :
296 : constexpr bool has_even_significand_bits() const noexcept
297 : {
298 : return traits_type::has_even_significand_bits(u);
299 : }
300 : };
301 :
302 : ////////////////////////////////////////////////////////////////////////////////////////
303 : // Some simple utilities for constexpr computation.
304 : ////////////////////////////////////////////////////////////////////////////////////////
305 :
306 : template <class Int, class Int2>
307 613 : BOOST_JSON_CXX14_CONSTEXPR Int compute_power(Int a, Int2 exp) noexcept
308 : {
309 613 : BOOST_ASSERT(exp >= 0);
310 :
311 613 : Int res = 1;
312 1839 : while (exp > 0)
313 : {
314 1226 : if (exp % 2 != 0)
315 : {
316 920 : res *= a;
317 : }
318 :
319 1226 : a *= a;
320 1226 : exp >>= 1;
321 : }
322 613 : return res;
323 : }
324 :
325 : static constexpr std::uint64_t power_of_10[] = {
326 : UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000),
327 : UINT64_C(100000), UINT64_C(1000000), UINT64_C(10000000), UINT64_C(100000000),
328 : UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000), UINT64_C(1000000000000),
329 : UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000),
330 : UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000),
331 : UINT64_C(10000000000000000000)
332 : };
333 :
334 : static_assert(sizeof(power_of_10) == 20 * sizeof(std::uint64_t), "There should be the first 20 powers of 10");
335 :
336 :
337 : template <unsigned a, typename UInt>
338 : BOOST_JSON_CXX14_CONSTEXPR int count_factors(UInt n) noexcept
339 : {
340 : int c = 0;
341 :
342 : while (n % a == 0)
343 : {
344 : n /= a;
345 : ++c;
346 : }
347 : return c;
348 : }
349 :
350 : ////////////////////////////////////////////////////////////////////////////////////////
351 : // Utilities for fast/constexpr log computation.
352 : ////////////////////////////////////////////////////////////////////////////////////////
353 :
354 : namespace log {
355 : static_assert((-1 >> 1) == -1, "right-shift for signed integers must be arithmetic");
356 :
357 : // Compute floor(e * c - s).
358 : enum class multiply : std::uint32_t {};
359 : enum class subtract : std::uint32_t {};
360 : enum class shift : std::size_t {};
361 : enum class min_exponent : std::int32_t {};
362 : enum class max_exponent : std::int32_t {};
363 :
364 : template <multiply m, subtract f, shift k, min_exponent e_min, max_exponent e_max>
365 888 : constexpr int compute(int e) noexcept
366 : {
367 888 : return static_cast<int>((std::int32_t(e) * std::int32_t(m) - std::int32_t(f)) >> std::size_t(k));
368 : }
369 :
370 : // For constexpr computation.
371 : // Returns -1 when n = 0.
372 : template <class UInt>
373 : BOOST_JSON_CXX14_CONSTEXPR int floor_log2(UInt n) noexcept
374 : {
375 : int count = -1;
376 : while (n != 0)
377 : {
378 : ++count;
379 : n >>= 1;
380 : }
381 :
382 : return count;
383 : }
384 :
385 : static constexpr int floor_log10_pow2_min_exponent = -2620;
386 :
387 : static constexpr int floor_log10_pow2_max_exponent = 2620;
388 :
389 306 : constexpr int floor_log10_pow2(int e) noexcept
390 : {
391 : using namespace log;
392 : return compute<multiply(315653), subtract(0), shift(20),
393 : min_exponent(floor_log10_pow2_min_exponent),
394 306 : max_exponent(floor_log10_pow2_max_exponent)>(e);
395 : }
396 :
397 : static constexpr int floor_log2_pow10_min_exponent = -1233;
398 :
399 : static constexpr int floor_log2_pow10_max_exponent = 1233;
400 :
401 444 : constexpr int floor_log2_pow10(int e) noexcept
402 : {
403 : using namespace log;
404 : return compute<multiply(1741647), subtract(0), shift(19),
405 : min_exponent(floor_log2_pow10_min_exponent),
406 444 : max_exponent(floor_log2_pow10_max_exponent)>(e);
407 : }
408 :
409 : static constexpr int floor_log10_pow2_minus_log10_4_over_3_min_exponent = -2985;
410 :
411 : static constexpr int floor_log10_pow2_minus_log10_4_over_3_max_exponent = 2936;
412 :
413 138 : constexpr int floor_log10_pow2_minus_log10_4_over_3(int e) noexcept
414 : {
415 : using namespace log;
416 : return compute<multiply(631305), subtract(261663), shift(21),
417 : min_exponent(floor_log10_pow2_minus_log10_4_over_3_min_exponent),
418 138 : max_exponent(floor_log10_pow2_minus_log10_4_over_3_max_exponent)>(e);
419 : }
420 :
421 : static constexpr int floor_log5_pow2_min_exponent = -1831;
422 :
423 : static constexpr int floor_log5_pow2_max_exponent = 1831;
424 :
425 : constexpr int floor_log5_pow2(int e) noexcept
426 : {
427 : using namespace log;
428 : return compute<multiply(225799), subtract(0), shift(19),
429 : min_exponent(floor_log5_pow2_min_exponent),
430 : max_exponent(floor_log5_pow2_max_exponent)>(e);
431 : }
432 :
433 : static constexpr int floor_log5_pow2_minus_log5_3_min_exponent = -3543;
434 :
435 : static constexpr int floor_log5_pow2_minus_log5_3_max_exponent = 2427;
436 :
437 : constexpr int floor_log5_pow2_minus_log5_3(int e) noexcept
438 : {
439 : using namespace log;
440 : return compute<multiply(451597), subtract(715764), shift(20),
441 : min_exponent(floor_log5_pow2_minus_log5_3_min_exponent),
442 : max_exponent(floor_log5_pow2_minus_log5_3_max_exponent)>(e);
443 : }
444 : } // Namespace log
445 :
446 : } // namespace detail
447 : } // namespace json
448 : } // namespace boost
449 :
450 : #endif // BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_COMMON_HPP
|
