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 + 
BOOST_JSON_CXX14_CONSTEXPR Int compute_power(Int a, Int2 exp) noexcept
 
308 + 
{
 
309 + 
    BOOST_ASSERT(exp >= 0);
 
310 +
 
311 + 
    Int res = 1;
 
312 + 
    while (exp > 0)
 
313 + 
    {
 
314 + 
        if (exp % 2 != 0)
 
315 + 
        {
 
316 + 
            res *= a;
 
317 + 
        }
 
318 +
 
319 + 
        a *= a;
 
320 + 
        exp >>= 1;
 
321 + 
    }
 
322 + 
    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 + 
constexpr int compute(int e) noexcept
 
366 + 
{
 
367 + 
    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 + 
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 + 
                    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 + 
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 + 
                    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 + 
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 + 
                    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