GCC Code Coverage Report

Directory: libs/json/include/boost/json/
File: detail/dragonbox/dragonbox.hpp
Date: 2025-12-23 16:57:39
Exec Total Coverage
Lines: 172 216 79.6%
Functions: 38 43 88.4%
Branches: 39 88 44.3%
Line Branch Exec Source
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 // Copyright 2023 Matt Borland
19 // Distributed under the Boost Software License, Version 1.0.
20 // https://www.boost.org/LICENSE_1_0.txt
21
22 #ifndef BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_HPP
23 #define BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_HPP
24
25 #include <boost/json/detail/charconv/detail/config.hpp>
26 #include <boost/json/detail/dragonbox/dragonbox_common.hpp>
27 #include <boost/core/bit.hpp>
28 #include <type_traits>
29 #include <limits>
30 #include <cstdint>
31 #include <cstring>
32
33 #ifdef BOOST_MSVC
34 # pragma warning(push)
35 # pragma warning(disable: 4127) // Conditional expression is constant (e.g. BOOST_IF_CONSTEXPR statements)
36 # pragma warning(disable: 4307) // Integral constant overflow (Only MSVC-14.1 issued this warning)
37 #endif
38
39 namespace boost {
40 namespace json {
41 namespace detail {
42
43 // A floating-point traits class defines ways to interpret a bit pattern of given size as an
44 // encoding of floating-point number. This is a default implementation of such a traits class,
45 // supporting ways to interpret 32-bits into a binary32-encoded floating-point number and to
46 // interpret 64-bits into a binary64-encoded floating-point number. Users might specialize this
47 // class to change the default behavior for certain types.
48
49 template <typename T>
50 struct dragonbox_float_traits
51 {
52 // I don't know if there is a truly reliable way of detecting
53 // IEEE-754 binary32/binary64 formats; I just did my best here.
54 static_assert(std::numeric_limits<T>::is_iec559 && std::numeric_limits<T>::radix == 2 &&
55 (physical_bits<T>::value == 32 || physical_bits<T>::value == 64),
56 "default_ieee754_traits only works for 32-bits or 64-bits types "
57 "supporting binary32 or binary64 formats!");
58
59 // The type that is being viewed.
60 using type = T;
61
62 // Refers to the format specification class.
63 using format = typename std::conditional<physical_bits<T>::value == 32, ieee754_binary32, ieee754_binary64>::type;
64
65 // Defines an unsigned integer type that is large enough to carry a variable of type T.
66 // Most of the operations will be done on this integer type.
67 using carrier_uint =
68 typename std::conditional<physical_bits<T>::value == 32, std::uint32_t, std::uint64_t>::type;
69
70 static_assert(sizeof(carrier_uint) == sizeof(T), "Type T must have a unsigned type with the same number of bits");
71
72 // Number of bits in the above unsigned integer type.
73 static constexpr int carrier_bits = static_cast<int>(physical_bits<carrier_uint>::value);
74
75 // Convert from carrier_uint into the original type.
76 // Depending on the floating-point encoding format, this operation might not be possible for
77 // some specific bit patterns. However, the contract is that u always denotes a
78 // valid bit pattern, so this function must be assumed to be noexcept.
79 static T carrier_to_float(carrier_uint u) noexcept
80 {
81 T x;
82 std::memcpy(&x, &u, sizeof(carrier_uint));
83 return x;
84 }
85
86 // Same as above.
87 510 static carrier_uint float_to_carrier(T x) noexcept
88 {
89 carrier_uint u;
90 510 std::memcpy(&u, &x, sizeof(carrier_uint));
91 510 return u;
92 }
93
94 // Extract exponent bits from a bit pattern.
95 // The result must be aligned to the LSB so that there is no additional zero paddings
96 // on the right. This function does not do bias adjustment.
97 510 static constexpr unsigned extract_exponent_bits(carrier_uint u) noexcept
98 {
99 510 return static_cast<unsigned>(u >> format::significand_bits) & ((static_cast<unsigned int>(1) << format::exponent_bits) - 1);
100 }
101
102 // Extract significand bits from a bit pattern.
103 // The result must be aligned to the LSB so that there is no additional zero paddings
104 // on the right. The result does not contain the implicit bit.
105 static constexpr carrier_uint extract_significand_bits(carrier_uint u) noexcept
106 {
107 return carrier_uint(u & carrier_uint((carrier_uint(1) << format::significand_bits) - 1));
108 }
109
110 // Remove the exponent bits and extract significand bits together with the sign bit.
111 510 static constexpr carrier_uint remove_exponent_bits(carrier_uint u, unsigned int exponent_bits) noexcept
112 {
113 510 return u ^ (carrier_uint(exponent_bits) << format::significand_bits);
114 }
115
116 // Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
117 444 static constexpr carrier_uint remove_sign_bit_and_shift(carrier_uint u) noexcept {
118 444 return carrier_uint(carrier_uint(u) << 1);
119 }
120
121 // The actual value of exponent is obtained by adding this value to the extracted exponent
122 // bits.
123 static constexpr int exponent_bias = 1 - (1 << (carrier_bits - format::significand_bits - 2));
124
125 // Obtain the actual value of the binary exponent from the extracted exponent bits.
126 static constexpr int binary_exponent(unsigned exponent_bits) noexcept
127 {
128 return static_cast<int>(exponent_bits == 0 ? format::min_exponent : int(exponent_bits) + format::exponent_bias);
129 }
130
131 // Obtain the actual value of the binary exponent from the extracted significand bits and
132 // exponent bits.
133 static constexpr carrier_uint binary_significand(carrier_uint significand_bits, unsigned exponent_bits) noexcept
134 {
135 return exponent_bits == 0 ? significand_bits : significand_bits | (carrier_uint(1) << format::significand_bits);
136 }
137
138 /* Various boolean observer functions */
139
140 495 static constexpr bool is_nonzero(carrier_uint u) noexcept
141 {
142 495 return (u << 1) != 0;
143 }
144
145 949 static constexpr bool is_positive(carrier_uint u) noexcept
146 {
147 949 return u < (carrier_uint(1) << (format::significand_bits + format::exponent_bits));
148 }
149
150 949 static constexpr bool is_negative(carrier_uint u) noexcept
151 {
152 949 return !is_positive(u);
153 }
154
155 510 static constexpr bool is_finite(unsigned exponent_bits) noexcept
156 {
157 510 return exponent_bits != ((1u << format::exponent_bits) - 1);
158 }
159
160 15 static constexpr bool has_all_zero_significand_bits(carrier_uint u) noexcept
161 {
162 15 return (u << 1) == 0;
163 }
164
165 306 static constexpr bool has_even_significand_bits(carrier_uint u) noexcept
166 {
167 306 return u % 2 == 0;
168 }
169 };
170
171 // Convenient wrappers for floating-point traits classes.
172 // In order to reduce the argument passing overhead, these classes should be as simple as
173 // possible (e.g., no inheritance, no private non-static data member, etc.; this is an
174 // unfortunate fact about common ABI convention).
175
176 template <typename T, typename Traits = dragonbox_float_traits<T>>
177 struct dragonbox_float_bits;
178
179 template <typename T, typename Traits = dragonbox_float_traits<T>>
180 struct dragonbox_signed_significand_bits;
181
182 template <typename T, typename Traits>
183 struct dragonbox_float_bits
184 {
185 using type = T;
186 using traits_type = Traits;
187 using carrier_uint = typename traits_type::carrier_uint;
188
189 carrier_uint u;
190
191 dragonbox_float_bits() = default;
192 constexpr explicit dragonbox_float_bits(carrier_uint bit_pattern) noexcept : u{bit_pattern} {}
193 510 constexpr explicit dragonbox_float_bits(T float_value) noexcept
194 510 : u{traits_type::float_to_carrier(float_value)} {}
195
196 T to_float() const noexcept
197 {
198 return traits_type::carrier_to_float(u);
199 }
200
201 // Extract exponent bits from a bit pattern.
202 // The result must be aligned to the LSB so that there is no additional zero paddings
203 // on the right. This function does not do bias adjustment.
204 510 constexpr unsigned int extract_exponent_bits() const noexcept
205 {
206 510 return traits_type::extract_exponent_bits(u);
207 }
208
209 // Extract significand bits from a bit pattern.
210 // The result must be aligned to the LSB so that there is no additional zero paddings
211 // on the right. The result does not contain the implicit bit.
212 constexpr carrier_uint extract_significand_bits() const noexcept
213 {
214 return traits_type::extract_significand_bits(u);
215 }
216
217 // Remove the exponent bits and extract significand bits together with the sign bit.
218 510 constexpr auto remove_exponent_bits(unsigned int exponent_bits) const noexcept -> dragonbox_signed_significand_bits<type, traits_type>
219 {
220 510 return dragonbox_signed_significand_bits<type, traits_type>(traits_type::remove_exponent_bits(u, exponent_bits));
221 }
222
223 // Obtain the actual value of the binary exponent from the extracted exponent bits.
224 static constexpr int binary_exponent(unsigned exponent_bits) noexcept
225 {
226 return traits_type::binary_exponent(exponent_bits);
227 }
228
229 constexpr int binary_exponent() const noexcept
230 {
231 return binary_exponent(extract_exponent_bits());
232 }
233
234 // Obtain the actual value of the binary exponent from the extracted significand bits and
235 // exponent bits.
236 static constexpr carrier_uint binary_significand(carrier_uint significand_bits, unsigned exponent_bits) noexcept
237 {
238 return traits_type::binary_significand(significand_bits, exponent_bits);
239 }
240
241 constexpr carrier_uint binary_significand() const noexcept
242 {
243 return binary_significand(extract_significand_bits(), extract_exponent_bits());
244 }
245
246 495 constexpr bool is_nonzero() const noexcept
247 {
248 495 return traits_type::is_nonzero(u);
249 }
250
251 constexpr bool is_positive() const noexcept
252 {
253 return traits_type::is_positive(u);
254 }
255
256 constexpr bool is_negative() const noexcept
257 {
258 return traits_type::is_negative(u);
259 }
260
261 510 constexpr bool is_finite(unsigned exponent_bits) const noexcept
262 {
263 510 return traits_type::is_finite(exponent_bits);
264 }
265
266 constexpr bool is_finite() const noexcept
267 {
268 return traits_type::is_finite(extract_exponent_bits());
269 }
270
271 constexpr bool has_even_significand_bits() const noexcept
272 {
273 return traits_type::has_even_significand_bits(u);
274 }
275 };
276
277 template <typename T, typename Traits>
278 struct dragonbox_signed_significand_bits
279 {
280 using type = T;
281 using traits_type = Traits;
282 using carrier_uint = typename traits_type::carrier_uint;
283
284 carrier_uint u;
285
286 dragonbox_signed_significand_bits() = default;
287 510 constexpr explicit dragonbox_signed_significand_bits(carrier_uint bit_pattern) noexcept
288 510 : u{bit_pattern} {}
289
290 // Shift the obtained signed significand bits to the left by 1 to remove the sign bit.
291 444 constexpr carrier_uint remove_sign_bit_and_shift() const noexcept
292 {
293 444 return traits_type::remove_sign_bit_and_shift(u);
294 }
295
296 constexpr bool is_positive() const noexcept
297 {
298 return traits_type::is_positive(u);
299 }
300
301 949 constexpr bool is_negative() const noexcept
302 {
303 949 return traits_type::is_negative(u);
304 }
305
306 15 constexpr bool has_all_zero_significand_bits() const noexcept
307 {
308 15 return traits_type::has_all_zero_significand_bits(u);
309 }
310
311 306 constexpr bool has_even_significand_bits() const noexcept
312 {
313 306 return traits_type::has_even_significand_bits(u);
314 }
315 };
316
317 ////////////////////////////////////////////////////////////////////////////////////////
318 // Utilities for fast divisibility tests.
319 ////////////////////////////////////////////////////////////////////////////////////////
320
321 namespace div {
322 // Replace n by floor(n / 10^N).
323 // Returns true if and only if n is divisible by 10^N.
324 // Precondition: n <= 10^(N+1)
325 // !!It takes an in-out parameter!!
326 template <int N>
327 struct divide_by_pow10_info;
328
329 template <>
330 struct divide_by_pow10_info<1>
331 {
332 static constexpr std::uint32_t magic_number = 6554;
333 static constexpr int shift_amount = 16;
334 };
335
336 template <>
337 struct divide_by_pow10_info<2>
338 {
339 static constexpr std::uint32_t magic_number = 656;
340 static constexpr int shift_amount = 16;
341 };
342
343 template <int N>
344 1 BOOST_CXX14_CONSTEXPR bool check_divisibility_and_divide_by_pow10(std::uint32_t& n) noexcept
345 {
346 // Make sure the computation for max_n does not overflow.
347 // static_assert(N + 1 <= log::floor_log10_pow2(31));
348
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 BOOST_ASSERT(n <= compute_power(UINT32_C(10), N + 1));
349
350 using info = divide_by_pow10_info<N>;
351 1 n *= info::magic_number;
352
353 1 constexpr auto mask = std::uint32_t(std::uint32_t(1) << info::shift_amount) - 1;
354 1 bool result = ((n & mask) < info::magic_number);
355
356 1 n >>= info::shift_amount;
357 1 return result;
358 }
359
360 // Compute floor(n / 10^N) for small n and N.
361 // Precondition: n <= 10^(N+1)
362 template <int N>
363 BOOST_CXX14_CONSTEXPR std::uint32_t small_division_by_pow10(std::uint32_t n) noexcept
364 {
365 // Make sure the computation for max_n does not overflow.
366 // static_assert(N + 1 <= log::floor_log10_pow2(31));
367 BOOST_ASSERT(n <= compute_power(UINT32_C(10), N + 1));
368
369 return (n * divide_by_pow10_info<N>::magic_number) >> divide_by_pow10_info<N>::shift_amount;
370 }
371
372 // Compute floor(n / 10^N) for small N.
373 // Precondition: n <= n_max
374 template <unsigned N, typename UInt, UInt n_max>
375 BOOST_CXX14_CONSTEXPR UInt divide_by_pow10(UInt n) noexcept
376 {
377
378 // Specialize for 32-bit division by 100.
379 // Compiler is supposed to generate the identical code for just writing
380 // "n / 100", but for some reason MSVC generates an inefficient code
381 // (mul + mov for no apparent reason, instead of single imul),
382 // so we does this manually.
383 BOOST_IF_CONSTEXPR (std::is_same<UInt, std::uint32_t>::value && N == 2)
384 {
385 return static_cast<UInt>(umul64(static_cast<std::uint32_t>(n), UINT32_C(1374389535)) >> 37);
386 }
387 // Specialize for 64-bit division by 1000.
388 // Ensure that the correctness condition is met.
389 else BOOST_IF_CONSTEXPR (std::is_same<UInt, std::uint64_t>::value && N == 3 && n_max <= UINT64_C(15534100272597517998))
390 {
391 return static_cast<UInt>(umul128_upper64(n, UINT64_C(2361183241434822607)) >> 7);
392 }
393 else
394 {
395 BOOST_CXX14_CONSTEXPR auto divisor = compute_power(static_cast<UInt>(10), N);
396 return n / divisor;
397 }
398 }
399
400 #ifdef BOOST_MSVC
401 # pragma warning(push)
402 # pragma warning(disable: 4100) // MSVC 14.0 does not have BOOST_ATTRIBUTE_UNUSED so we disable the warning
403 #endif
404
405 template <typename UInt>
406 306 BOOST_CXX14_CONSTEXPR UInt divide_by_pow10(unsigned N, BOOST_ATTRIBUTE_UNUSED UInt n_max, UInt n) noexcept
407 {
408 BOOST_IF_CONSTEXPR (std::is_same<UInt, std::uint32_t>::value && N == 2)
409 {
410 return static_cast<UInt>(umul64(static_cast<std::uint32_t>(n), static_cast<std::uint32_t>(1374389535)) >> UINT32_C(37));
411 }
412 // Specialize for 64-bit division by 1000.
413 // Ensure that the correctness condition is met.
414
2/4
✓ Branch 0 taken 306 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 306 times.
✗ Branch 3 not taken.
 306 else BOOST_IF_CONSTEXPR (std::is_same<UInt, std::uint64_t>::value && N == 3 && n_max <= UINT64_C(15534100272597517998))
415 {
416 306 return static_cast<UInt>(umul128_upper64(n, UINT64_C(2361183241434822607)) >> 7);
417 }
418 else
419 {
420 ✗ auto divisor = compute_power(static_cast<UInt>(10), N);
421 ✗ return n / divisor;
422 }
423 }
424
425 #ifdef BOOST_MSVC
426 # pragma warning(pop)
427 #endif
428 }
429
430 ////////////////////////////////////////////////////////////////////////////////////////
431 // Return types for the main interface function.
432 ////////////////////////////////////////////////////////////////////////////////////////
433
434 template <typename UInt, bool is_signed, bool trailing_zero_flag>
435 struct decimal_fp;
436
437 template <typename UInt>
438 struct decimal_fp<UInt, false, false>
439 {
440 using carrier_uint = UInt;
441
442 carrier_uint significand;
443 int exponent;
444 };
445
446 template <typename UInt>
447 struct decimal_fp<UInt, true, false>
448 {
449 using carrier_uint = UInt;
450
451 carrier_uint significand;
452 int exponent;
453 bool is_negative;
454 };
455
456 template <typename UInt>
457 struct decimal_fp<UInt, false, true>
458 {
459 using carrier_uint = UInt;
460
461 carrier_uint significand;
462 int exponent;
463 bool may_have_trailing_zeros;
464 };
465
466 template <typename UInt>
467 struct decimal_fp<UInt, true, true>
468 {
469 using carrier_uint = UInt;
470
471 carrier_uint significand;
472 int exponent;
473 bool is_negative;
474 bool may_have_trailing_zeros;
475 };
476
477 template <typename UInt>
478 using unsigned_decimal_fp = decimal_fp<UInt, false, false>;
479
480 template <typename UInt>
481 using signed_decimal_fp = decimal_fp<UInt, true, false>;
482
483 ////////////////////////////////////////////////////////////////////////////////////////
484 // Computed cache entries.
485 ////////////////////////////////////////////////////////////////////////////////////////
486
487 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
488 template <bool b>
489 struct cache_holder_ieee754_binary32_impl
490 #else
491 struct cache_holder_ieee754_binary32
492 #endif
493 {
494 using cache_entry_type = std::uint64_t;
495 static constexpr int cache_bits = 64;
496 static constexpr int min_k = -31;
497 static constexpr int max_k = 46;
498 static constexpr cache_entry_type cache[] = {
499 0x81ceb32c4b43fcf5, 0xa2425ff75e14fc32, 0xcad2f7f5359a3b3f, 0xfd87b5f28300ca0e,
500 0x9e74d1b791e07e49, 0xc612062576589ddb, 0xf79687aed3eec552, 0x9abe14cd44753b53,
501 0xc16d9a0095928a28, 0xf1c90080baf72cb2, 0x971da05074da7bef, 0xbce5086492111aeb,
502 0xec1e4a7db69561a6, 0x9392ee8e921d5d08, 0xb877aa3236a4b44a, 0xe69594bec44de15c,
503 0x901d7cf73ab0acda, 0xb424dc35095cd810, 0xe12e13424bb40e14, 0x8cbccc096f5088cc,
504 0xafebff0bcb24aaff, 0xdbe6fecebdedd5bf, 0x89705f4136b4a598, 0xabcc77118461cefd,
505 0xd6bf94d5e57a42bd, 0x8637bd05af6c69b6, 0xa7c5ac471b478424, 0xd1b71758e219652c,
506 0x83126e978d4fdf3c, 0xa3d70a3d70a3d70b, 0xcccccccccccccccd, 0x8000000000000000,
507 0xa000000000000000, 0xc800000000000000, 0xfa00000000000000, 0x9c40000000000000,
508 0xc350000000000000, 0xf424000000000000, 0x9896800000000000, 0xbebc200000000000,
509 0xee6b280000000000, 0x9502f90000000000, 0xba43b74000000000, 0xe8d4a51000000000,
510 0x9184e72a00000000, 0xb5e620f480000000, 0xe35fa931a0000000, 0x8e1bc9bf04000000,
511 0xb1a2bc2ec5000000, 0xde0b6b3a76400000, 0x8ac7230489e80000, 0xad78ebc5ac620000,
512 0xd8d726b7177a8000, 0x878678326eac9000, 0xa968163f0a57b400, 0xd3c21bcecceda100,
513 0x84595161401484a0, 0xa56fa5b99019a5c8, 0xcecb8f27f4200f3a, 0x813f3978f8940985,
514 0xa18f07d736b90be6, 0xc9f2c9cd04674edf, 0xfc6f7c4045812297, 0x9dc5ada82b70b59e,
515 0xc5371912364ce306, 0xf684df56c3e01bc7, 0x9a130b963a6c115d, 0xc097ce7bc90715b4,
516 0xf0bdc21abb48db21, 0x96769950b50d88f5, 0xbc143fa4e250eb32, 0xeb194f8e1ae525fe,
517 0x92efd1b8d0cf37bf, 0xb7abc627050305ae, 0xe596b7b0c643c71a, 0x8f7e32ce7bea5c70,
518 0xb35dbf821ae4f38c, 0xe0352f62a19e306f};
519 };
520
521 #if defined(BOOST_NO_CXX17_INLINE_VARIABLES) && (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
522
523 template <bool b> constexpr int cache_holder_ieee754_binary32_impl<b>::cache_bits;
524 template <bool b> constexpr int cache_holder_ieee754_binary32_impl<b>::min_k;
525 template <bool b> constexpr int cache_holder_ieee754_binary32_impl<b>::max_k;
526 template <bool b> constexpr typename cache_holder_ieee754_binary32_impl<b>::cache_entry_type cache_holder_ieee754_binary32_impl<b>::cache[];
527
528 #endif
529
530 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
531 using cache_holder_ieee754_binary32 = cache_holder_ieee754_binary32_impl<true>;
532 #endif
533
534 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
535 template <bool b>
536 struct cache_holder_ieee754_binary64_impl
537 #else
538 struct cache_holder_ieee754_binary64
539 #endif
540 {
541 using cache_entry_type = uint128;
542 static constexpr int cache_bits = 128;
543 static constexpr int min_k = -292;
544 static constexpr int max_k = 326;
545 static constexpr cache_entry_type cache[] = {
546 {0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7b}, {0x9faacf3df73609b1, 0x77b191618c54e9ad},
547 {0xc795830d75038c1d, 0xd59df5b9ef6a2418}, {0xf97ae3d0d2446f25, 0x4b0573286b44ad1e},
548 {0x9becce62836ac577, 0x4ee367f9430aec33}, {0xc2e801fb244576d5, 0x229c41f793cda740},
549 {0xf3a20279ed56d48a, 0x6b43527578c11110}, {0x9845418c345644d6, 0x830a13896b78aaaa},
550 {0xbe5691ef416bd60c, 0x23cc986bc656d554}, {0xedec366b11c6cb8f, 0x2cbfbe86b7ec8aa9},
551 {0x94b3a202eb1c3f39, 0x7bf7d71432f3d6aa}, {0xb9e08a83a5e34f07, 0xdaf5ccd93fb0cc54},
552 {0xe858ad248f5c22c9, 0xd1b3400f8f9cff69}, {0x91376c36d99995be, 0x23100809b9c21fa2},
553 {0xb58547448ffffb2d, 0xabd40a0c2832a78b}, {0xe2e69915b3fff9f9, 0x16c90c8f323f516d},
554 {0x8dd01fad907ffc3b, 0xae3da7d97f6792e4}, {0xb1442798f49ffb4a, 0x99cd11cfdf41779d},
555 {0xdd95317f31c7fa1d, 0x40405643d711d584}, {0x8a7d3eef7f1cfc52, 0x482835ea666b2573},
556 {0xad1c8eab5ee43b66, 0xda3243650005eed0}, {0xd863b256369d4a40, 0x90bed43e40076a83},
557 {0x873e4f75e2224e68, 0x5a7744a6e804a292}, {0xa90de3535aaae202, 0x711515d0a205cb37},
558 {0xd3515c2831559a83, 0x0d5a5b44ca873e04}, {0x8412d9991ed58091, 0xe858790afe9486c3},
559 {0xa5178fff668ae0b6, 0x626e974dbe39a873}, {0xce5d73ff402d98e3, 0xfb0a3d212dc81290},
560 {0x80fa687f881c7f8e, 0x7ce66634bc9d0b9a}, {0xa139029f6a239f72, 0x1c1fffc1ebc44e81},
561 {0xc987434744ac874e, 0xa327ffb266b56221}, {0xfbe9141915d7a922, 0x4bf1ff9f0062baa9},
562 {0x9d71ac8fada6c9b5, 0x6f773fc3603db4aa}, {0xc4ce17b399107c22, 0xcb550fb4384d21d4},
563 {0xf6019da07f549b2b, 0x7e2a53a146606a49}, {0x99c102844f94e0fb, 0x2eda7444cbfc426e},
564 {0xc0314325637a1939, 0xfa911155fefb5309}, {0xf03d93eebc589f88, 0x793555ab7eba27cb},
565 {0x96267c7535b763b5, 0x4bc1558b2f3458df}, {0xbbb01b9283253ca2, 0x9eb1aaedfb016f17},
566 {0xea9c227723ee8bcb, 0x465e15a979c1cadd}, {0x92a1958a7675175f, 0x0bfacd89ec191eca},
567 {0xb749faed14125d36, 0xcef980ec671f667c}, {0xe51c79a85916f484, 0x82b7e12780e7401b},
568 {0x8f31cc0937ae58d2, 0xd1b2ecb8b0908811}, {0xb2fe3f0b8599ef07, 0x861fa7e6dcb4aa16},
569 {0xdfbdcece67006ac9, 0x67a791e093e1d49b}, {0x8bd6a141006042bd, 0xe0c8bb2c5c6d24e1},
570 {0xaecc49914078536d, 0x58fae9f773886e19}, {0xda7f5bf590966848, 0xaf39a475506a899f},
571 {0x888f99797a5e012d, 0x6d8406c952429604}, {0xaab37fd7d8f58178, 0xc8e5087ba6d33b84},
572 {0xd5605fcdcf32e1d6, 0xfb1e4a9a90880a65}, {0x855c3be0a17fcd26, 0x5cf2eea09a550680},
573 {0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481f}, {0xd0601d8efc57b08b, 0xf13b94daf124da27},
574 {0x823c12795db6ce57, 0x76c53d08d6b70859}, {0xa2cb1717b52481ed, 0x54768c4b0c64ca6f},
575 {0xcb7ddcdda26da268, 0xa9942f5dcf7dfd0a}, {0xfe5d54150b090b02, 0xd3f93b35435d7c4d},
576 {0x9efa548d26e5a6e1, 0xc47bc5014a1a6db0}, {0xc6b8e9b0709f109a, 0x359ab6419ca1091c},
577 {0xf867241c8cc6d4c0, 0xc30163d203c94b63}, {0x9b407691d7fc44f8, 0x79e0de63425dcf1e},
578 {0xc21094364dfb5636, 0x985915fc12f542e5}, {0xf294b943e17a2bc4, 0x3e6f5b7b17b2939e},
579 {0x979cf3ca6cec5b5a, 0xa705992ceecf9c43}, {0xbd8430bd08277231, 0x50c6ff782a838354},
580 {0xece53cec4a314ebd, 0xa4f8bf5635246429}, {0x940f4613ae5ed136, 0x871b7795e136be9a},
581 {0xb913179899f68584, 0x28e2557b59846e40}, {0xe757dd7ec07426e5, 0x331aeada2fe589d0},
582 {0x9096ea6f3848984f, 0x3ff0d2c85def7622}, {0xb4bca50b065abe63, 0x0fed077a756b53aa},
583 {0xe1ebce4dc7f16dfb, 0xd3e8495912c62895}, {0x8d3360f09cf6e4bd, 0x64712dd7abbbd95d},
584 {0xb080392cc4349dec, 0xbd8d794d96aacfb4}, {0xdca04777f541c567, 0xecf0d7a0fc5583a1},
585 {0x89e42caaf9491b60, 0xf41686c49db57245}, {0xac5d37d5b79b6239, 0x311c2875c522ced6},
586 {0xd77485cb25823ac7, 0x7d633293366b828c}, {0x86a8d39ef77164bc, 0xae5dff9c02033198},
587 {0xa8530886b54dbdeb, 0xd9f57f830283fdfd}, {0xd267caa862a12d66, 0xd072df63c324fd7c},
588 {0x8380dea93da4bc60, 0x4247cb9e59f71e6e}, {0xa46116538d0deb78, 0x52d9be85f074e609},
589 {0xcd795be870516656, 0x67902e276c921f8c}, {0x806bd9714632dff6, 0x00ba1cd8a3db53b7},
590 {0xa086cfcd97bf97f3, 0x80e8a40eccd228a5}, {0xc8a883c0fdaf7df0, 0x6122cd128006b2ce},
591 {0xfad2a4b13d1b5d6c, 0x796b805720085f82}, {0x9cc3a6eec6311a63, 0xcbe3303674053bb1},
592 {0xc3f490aa77bd60fc, 0xbedbfc4411068a9d}, {0xf4f1b4d515acb93b, 0xee92fb5515482d45},
593 {0x991711052d8bf3c5, 0x751bdd152d4d1c4b}, {0xbf5cd54678eef0b6, 0xd262d45a78a0635e},
594 {0xef340a98172aace4, 0x86fb897116c87c35}, {0x9580869f0e7aac0e, 0xd45d35e6ae3d4da1},
595 {0xbae0a846d2195712, 0x8974836059cca10a}, {0xe998d258869facd7, 0x2bd1a438703fc94c},
596 {0x91ff83775423cc06, 0x7b6306a34627ddd0}, {0xb67f6455292cbf08, 0x1a3bc84c17b1d543},
597 {0xe41f3d6a7377eeca, 0x20caba5f1d9e4a94}, {0x8e938662882af53e, 0x547eb47b7282ee9d},
598 {0xb23867fb2a35b28d, 0xe99e619a4f23aa44}, {0xdec681f9f4c31f31, 0x6405fa00e2ec94d5},
599 {0x8b3c113c38f9f37e, 0xde83bc408dd3dd05}, {0xae0b158b4738705e, 0x9624ab50b148d446},
600 {0xd98ddaee19068c76, 0x3badd624dd9b0958}, {0x87f8a8d4cfa417c9, 0xe54ca5d70a80e5d7},
601 {0xa9f6d30a038d1dbc, 0x5e9fcf4ccd211f4d}, {0xd47487cc8470652b, 0x7647c32000696720},
602 {0x84c8d4dfd2c63f3b, 0x29ecd9f40041e074}, {0xa5fb0a17c777cf09, 0xf468107100525891},
603 {0xcf79cc9db955c2cc, 0x7182148d4066eeb5}, {0x81ac1fe293d599bf, 0xc6f14cd848405531},
604 {0xa21727db38cb002f, 0xb8ada00e5a506a7d}, {0xca9cf1d206fdc03b, 0xa6d90811f0e4851d},
605 {0xfd442e4688bd304a, 0x908f4a166d1da664}, {0x9e4a9cec15763e2e, 0x9a598e4e043287ff},
606 {0xc5dd44271ad3cdba, 0x40eff1e1853f29fe}, {0xf7549530e188c128, 0xd12bee59e68ef47d},
607 {0x9a94dd3e8cf578b9, 0x82bb74f8301958cf}, {0xc13a148e3032d6e7, 0xe36a52363c1faf02},
608 {0xf18899b1bc3f8ca1, 0xdc44e6c3cb279ac2}, {0x96f5600f15a7b7e5, 0x29ab103a5ef8c0ba},
609 {0xbcb2b812db11a5de, 0x7415d448f6b6f0e8}, {0xebdf661791d60f56, 0x111b495b3464ad22},
610 {0x936b9fcebb25c995, 0xcab10dd900beec35}, {0xb84687c269ef3bfb, 0x3d5d514f40eea743},
611 {0xe65829b3046b0afa, 0x0cb4a5a3112a5113}, {0x8ff71a0fe2c2e6dc, 0x47f0e785eaba72ac},
612 {0xb3f4e093db73a093, 0x59ed216765690f57}, {0xe0f218b8d25088b8, 0x306869c13ec3532d},
613 {0x8c974f7383725573, 0x1e414218c73a13fc}, {0xafbd2350644eeacf, 0xe5d1929ef90898fb},
614 {0xdbac6c247d62a583, 0xdf45f746b74abf3a}, {0x894bc396ce5da772, 0x6b8bba8c328eb784},
615 {0xab9eb47c81f5114f, 0x066ea92f3f326565}, {0xd686619ba27255a2, 0xc80a537b0efefebe},
616 {0x8613fd0145877585, 0xbd06742ce95f5f37}, {0xa798fc4196e952e7, 0x2c48113823b73705},
617 {0xd17f3b51fca3a7a0, 0xf75a15862ca504c6}, {0x82ef85133de648c4, 0x9a984d73dbe722fc},
618 {0xa3ab66580d5fdaf5, 0xc13e60d0d2e0ebbb}, {0xcc963fee10b7d1b3, 0x318df905079926a9},
619 {0xffbbcfe994e5c61f, 0xfdf17746497f7053}, {0x9fd561f1fd0f9bd3, 0xfeb6ea8bedefa634},
620 {0xc7caba6e7c5382c8, 0xfe64a52ee96b8fc1}, {0xf9bd690a1b68637b, 0x3dfdce7aa3c673b1},
621 {0x9c1661a651213e2d, 0x06bea10ca65c084f}, {0xc31bfa0fe5698db8, 0x486e494fcff30a63},
622 {0xf3e2f893dec3f126, 0x5a89dba3c3efccfb}, {0x986ddb5c6b3a76b7, 0xf89629465a75e01d},
623 {0xbe89523386091465, 0xf6bbb397f1135824}, {0xee2ba6c0678b597f, 0x746aa07ded582e2d},
624 {0x94db483840b717ef, 0xa8c2a44eb4571cdd}, {0xba121a4650e4ddeb, 0x92f34d62616ce414},
625 {0xe896a0d7e51e1566, 0x77b020baf9c81d18}, {0x915e2486ef32cd60, 0x0ace1474dc1d122f},
626 {0xb5b5ada8aaff80b8, 0x0d819992132456bb}, {0xe3231912d5bf60e6, 0x10e1fff697ed6c6a},
627 {0x8df5efabc5979c8f, 0xca8d3ffa1ef463c2}, {0xb1736b96b6fd83b3, 0xbd308ff8a6b17cb3},
628 {0xddd0467c64bce4a0, 0xac7cb3f6d05ddbdf}, {0x8aa22c0dbef60ee4, 0x6bcdf07a423aa96c},
629 {0xad4ab7112eb3929d, 0x86c16c98d2c953c7}, {0xd89d64d57a607744, 0xe871c7bf077ba8b8},
630 {0x87625f056c7c4a8b, 0x11471cd764ad4973}, {0xa93af6c6c79b5d2d, 0xd598e40d3dd89bd0},
631 {0xd389b47879823479, 0x4aff1d108d4ec2c4}, {0x843610cb4bf160cb, 0xcedf722a585139bb},
632 {0xa54394fe1eedb8fe, 0xc2974eb4ee658829}, {0xce947a3da6a9273e, 0x733d226229feea33},
633 {0x811ccc668829b887, 0x0806357d5a3f5260}, {0xa163ff802a3426a8, 0xca07c2dcb0cf26f8},
634 {0xc9bcff6034c13052, 0xfc89b393dd02f0b6}, {0xfc2c3f3841f17c67, 0xbbac2078d443ace3},
635 {0x9d9ba7832936edc0, 0xd54b944b84aa4c0e}, {0xc5029163f384a931, 0x0a9e795e65d4df12},
636 {0xf64335bcf065d37d, 0x4d4617b5ff4a16d6}, {0x99ea0196163fa42e, 0x504bced1bf8e4e46},
637 {0xc06481fb9bcf8d39, 0xe45ec2862f71e1d7}, {0xf07da27a82c37088, 0x5d767327bb4e5a4d},
638 {0x964e858c91ba2655, 0x3a6a07f8d510f870}, {0xbbe226efb628afea, 0x890489f70a55368c},
639 {0xeadab0aba3b2dbe5, 0x2b45ac74ccea842f}, {0x92c8ae6b464fc96f, 0x3b0b8bc90012929e},
640 {0xb77ada0617e3bbcb, 0x09ce6ebb40173745}, {0xe55990879ddcaabd, 0xcc420a6a101d0516},
641 {0x8f57fa54c2a9eab6, 0x9fa946824a12232e}, {0xb32df8e9f3546564, 0x47939822dc96abfa},
642 {0xdff9772470297ebd, 0x59787e2b93bc56f8}, {0x8bfbea76c619ef36, 0x57eb4edb3c55b65b},
643 {0xaefae51477a06b03, 0xede622920b6b23f2}, {0xdab99e59958885c4, 0xe95fab368e45ecee},
644 {0x88b402f7fd75539b, 0x11dbcb0218ebb415}, {0xaae103b5fcd2a881, 0xd652bdc29f26a11a},
645 {0xd59944a37c0752a2, 0x4be76d3346f04960}, {0x857fcae62d8493a5, 0x6f70a4400c562ddc},
646 {0xa6dfbd9fb8e5b88e, 0xcb4ccd500f6bb953}, {0xd097ad07a71f26b2, 0x7e2000a41346a7a8},
647 {0x825ecc24c873782f, 0x8ed400668c0c28c9}, {0xa2f67f2dfa90563b, 0x728900802f0f32fb},
648 {0xcbb41ef979346bca, 0x4f2b40a03ad2ffba}, {0xfea126b7d78186bc, 0xe2f610c84987bfa9},
649 {0x9f24b832e6b0f436, 0x0dd9ca7d2df4d7ca}, {0xc6ede63fa05d3143, 0x91503d1c79720dbc},
650 {0xf8a95fcf88747d94, 0x75a44c6397ce912b}, {0x9b69dbe1b548ce7c, 0xc986afbe3ee11abb},
651 {0xc24452da229b021b, 0xfbe85badce996169}, {0xf2d56790ab41c2a2, 0xfae27299423fb9c4},
652 {0x97c560ba6b0919a5, 0xdccd879fc967d41b}, {0xbdb6b8e905cb600f, 0x5400e987bbc1c921},
653 {0xed246723473e3813, 0x290123e9aab23b69}, {0x9436c0760c86e30b, 0xf9a0b6720aaf6522},
654 {0xb94470938fa89bce, 0xf808e40e8d5b3e6a}, {0xe7958cb87392c2c2, 0xb60b1d1230b20e05},
655 {0x90bd77f3483bb9b9, 0xb1c6f22b5e6f48c3}, {0xb4ecd5f01a4aa828, 0x1e38aeb6360b1af4},
656 {0xe2280b6c20dd5232, 0x25c6da63c38de1b1}, {0x8d590723948a535f, 0x579c487e5a38ad0f},
657 {0xb0af48ec79ace837, 0x2d835a9df0c6d852}, {0xdcdb1b2798182244, 0xf8e431456cf88e66},
658 {0x8a08f0f8bf0f156b, 0x1b8e9ecb641b5900}, {0xac8b2d36eed2dac5, 0xe272467e3d222f40},
659 {0xd7adf884aa879177, 0x5b0ed81dcc6abb10}, {0x86ccbb52ea94baea, 0x98e947129fc2b4ea},
660 {0xa87fea27a539e9a5, 0x3f2398d747b36225}, {0xd29fe4b18e88640e, 0x8eec7f0d19a03aae},
661 {0x83a3eeeef9153e89, 0x1953cf68300424ad}, {0xa48ceaaab75a8e2b, 0x5fa8c3423c052dd8},
662 {0xcdb02555653131b6, 0x3792f412cb06794e}, {0x808e17555f3ebf11, 0xe2bbd88bbee40bd1},
663 {0xa0b19d2ab70e6ed6, 0x5b6aceaeae9d0ec5}, {0xc8de047564d20a8b, 0xf245825a5a445276},
664 {0xfb158592be068d2e, 0xeed6e2f0f0d56713}, {0x9ced737bb6c4183d, 0x55464dd69685606c},
665 {0xc428d05aa4751e4c, 0xaa97e14c3c26b887}, {0xf53304714d9265df, 0xd53dd99f4b3066a9},
666 {0x993fe2c6d07b7fab, 0xe546a8038efe402a}, {0xbf8fdb78849a5f96, 0xde98520472bdd034},
667 {0xef73d256a5c0f77c, 0x963e66858f6d4441}, {0x95a8637627989aad, 0xdde7001379a44aa9},
668 {0xbb127c53b17ec159, 0x5560c018580d5d53}, {0xe9d71b689dde71af, 0xaab8f01e6e10b4a7},
669 {0x9226712162ab070d, 0xcab3961304ca70e9}, {0xb6b00d69bb55c8d1, 0x3d607b97c5fd0d23},
670 {0xe45c10c42a2b3b05, 0x8cb89a7db77c506b}, {0x8eb98a7a9a5b04e3, 0x77f3608e92adb243},
671 {0xb267ed1940f1c61c, 0x55f038b237591ed4}, {0xdf01e85f912e37a3, 0x6b6c46dec52f6689},
672 {0x8b61313bbabce2c6, 0x2323ac4b3b3da016}, {0xae397d8aa96c1b77, 0xabec975e0a0d081b},
673 {0xd9c7dced53c72255, 0x96e7bd358c904a22}, {0x881cea14545c7575, 0x7e50d64177da2e55},
674 {0xaa242499697392d2, 0xdde50bd1d5d0b9ea}, {0xd4ad2dbfc3d07787, 0x955e4ec64b44e865},
675 {0x84ec3c97da624ab4, 0xbd5af13bef0b113f}, {0xa6274bbdd0fadd61, 0xecb1ad8aeacdd58f},
676 {0xcfb11ead453994ba, 0x67de18eda5814af3}, {0x81ceb32c4b43fcf4, 0x80eacf948770ced8},
677 {0xa2425ff75e14fc31, 0xa1258379a94d028e}, {0xcad2f7f5359a3b3e, 0x096ee45813a04331},
678 {0xfd87b5f28300ca0d, 0x8bca9d6e188853fd}, {0x9e74d1b791e07e48, 0x775ea264cf55347e},
679 {0xc612062576589dda, 0x95364afe032a819e}, {0xf79687aed3eec551, 0x3a83ddbd83f52205},
680 {0x9abe14cd44753b52, 0xc4926a9672793543}, {0xc16d9a0095928a27, 0x75b7053c0f178294},
681 {0xf1c90080baf72cb1, 0x5324c68b12dd6339}, {0x971da05074da7bee, 0xd3f6fc16ebca5e04},
682 {0xbce5086492111aea, 0x88f4bb1ca6bcf585}, {0xec1e4a7db69561a5, 0x2b31e9e3d06c32e6},
683 {0x9392ee8e921d5d07, 0x3aff322e62439fd0}, {0xb877aa3236a4b449, 0x09befeb9fad487c3},
684 {0xe69594bec44de15b, 0x4c2ebe687989a9b4}, {0x901d7cf73ab0acd9, 0x0f9d37014bf60a11},
685 {0xb424dc35095cd80f, 0x538484c19ef38c95}, {0xe12e13424bb40e13, 0x2865a5f206b06fba},
686 {0x8cbccc096f5088cb, 0xf93f87b7442e45d4}, {0xafebff0bcb24aafe, 0xf78f69a51539d749},
687 {0xdbe6fecebdedd5be, 0xb573440e5a884d1c}, {0x89705f4136b4a597, 0x31680a88f8953031},
688 {0xabcc77118461cefc, 0xfdc20d2b36ba7c3e}, {0xd6bf94d5e57a42bc, 0x3d32907604691b4d},
689 {0x8637bd05af6c69b5, 0xa63f9a49c2c1b110}, {0xa7c5ac471b478423, 0x0fcf80dc33721d54},
690 {0xd1b71758e219652b, 0xd3c36113404ea4a9}, {0x83126e978d4fdf3b, 0x645a1cac083126ea},
691 {0xa3d70a3d70a3d70a, 0x3d70a3d70a3d70a4}, {0xcccccccccccccccc, 0xcccccccccccccccd},
692 {0x8000000000000000, 0x0000000000000000}, {0xa000000000000000, 0x0000000000000000},
693 {0xc800000000000000, 0x0000000000000000}, {0xfa00000000000000, 0x0000000000000000},
694 {0x9c40000000000000, 0x0000000000000000}, {0xc350000000000000, 0x0000000000000000},
695 {0xf424000000000000, 0x0000000000000000}, {0x9896800000000000, 0x0000000000000000},
696 {0xbebc200000000000, 0x0000000000000000}, {0xee6b280000000000, 0x0000000000000000},
697 {0x9502f90000000000, 0x0000000000000000}, {0xba43b74000000000, 0x0000000000000000},
698 {0xe8d4a51000000000, 0x0000000000000000}, {0x9184e72a00000000, 0x0000000000000000},
699 {0xb5e620f480000000, 0x0000000000000000}, {0xe35fa931a0000000, 0x0000000000000000},
700 {0x8e1bc9bf04000000, 0x0000000000000000}, {0xb1a2bc2ec5000000, 0x0000000000000000},
701 {0xde0b6b3a76400000, 0x0000000000000000}, {0x8ac7230489e80000, 0x0000000000000000},
702 {0xad78ebc5ac620000, 0x0000000000000000}, {0xd8d726b7177a8000, 0x0000000000000000},
703 {0x878678326eac9000, 0x0000000000000000}, {0xa968163f0a57b400, 0x0000000000000000},
704 {0xd3c21bcecceda100, 0x0000000000000000}, {0x84595161401484a0, 0x0000000000000000},
705 {0xa56fa5b99019a5c8, 0x0000000000000000}, {0xcecb8f27f4200f3a, 0x0000000000000000},
706 {0x813f3978f8940984, 0x4000000000000000}, {0xa18f07d736b90be5, 0x5000000000000000},
707 {0xc9f2c9cd04674ede, 0xa400000000000000}, {0xfc6f7c4045812296, 0x4d00000000000000},
708 {0x9dc5ada82b70b59d, 0xf020000000000000}, {0xc5371912364ce305, 0x6c28000000000000},
709 {0xf684df56c3e01bc6, 0xc732000000000000}, {0x9a130b963a6c115c, 0x3c7f400000000000},
710 {0xc097ce7bc90715b3, 0x4b9f100000000000}, {0xf0bdc21abb48db20, 0x1e86d40000000000},
711 {0x96769950b50d88f4, 0x1314448000000000}, {0xbc143fa4e250eb31, 0x17d955a000000000},
712 {0xeb194f8e1ae525fd, 0x5dcfab0800000000}, {0x92efd1b8d0cf37be, 0x5aa1cae500000000},
713 {0xb7abc627050305ad, 0xf14a3d9e40000000}, {0xe596b7b0c643c719, 0x6d9ccd05d0000000},
714 {0x8f7e32ce7bea5c6f, 0xe4820023a2000000}, {0xb35dbf821ae4f38b, 0xdda2802c8a800000},
715 {0xe0352f62a19e306e, 0xd50b2037ad200000}, {0x8c213d9da502de45, 0x4526f422cc340000},
716 {0xaf298d050e4395d6, 0x9670b12b7f410000}, {0xdaf3f04651d47b4c, 0x3c0cdd765f114000},
717 {0x88d8762bf324cd0f, 0xa5880a69fb6ac800}, {0xab0e93b6efee0053, 0x8eea0d047a457a00},
718 {0xd5d238a4abe98068, 0x72a4904598d6d880}, {0x85a36366eb71f041, 0x47a6da2b7f864750},
719 {0xa70c3c40a64e6c51, 0x999090b65f67d924}, {0xd0cf4b50cfe20765, 0xfff4b4e3f741cf6d},
720 {0x82818f1281ed449f, 0xbff8f10e7a8921a5}, {0xa321f2d7226895c7, 0xaff72d52192b6a0e},
721 {0xcbea6f8ceb02bb39, 0x9bf4f8a69f764491}, {0xfee50b7025c36a08, 0x02f236d04753d5b5},
722 {0x9f4f2726179a2245, 0x01d762422c946591}, {0xc722f0ef9d80aad6, 0x424d3ad2b7b97ef6},
723 {0xf8ebad2b84e0d58b, 0xd2e0898765a7deb3}, {0x9b934c3b330c8577, 0x63cc55f49f88eb30},
724 {0xc2781f49ffcfa6d5, 0x3cbf6b71c76b25fc}, {0xf316271c7fc3908a, 0x8bef464e3945ef7b},
725 {0x97edd871cfda3a56, 0x97758bf0e3cbb5ad}, {0xbde94e8e43d0c8ec, 0x3d52eeed1cbea318},
726 {0xed63a231d4c4fb27, 0x4ca7aaa863ee4bde}, {0x945e455f24fb1cf8, 0x8fe8caa93e74ef6b},
727 {0xb975d6b6ee39e436, 0xb3e2fd538e122b45}, {0xe7d34c64a9c85d44, 0x60dbbca87196b617},
728 {0x90e40fbeea1d3a4a, 0xbc8955e946fe31ce}, {0xb51d13aea4a488dd, 0x6babab6398bdbe42},
729 {0xe264589a4dcdab14, 0xc696963c7eed2dd2}, {0x8d7eb76070a08aec, 0xfc1e1de5cf543ca3},
730 {0xb0de65388cc8ada8, 0x3b25a55f43294bcc}, {0xdd15fe86affad912, 0x49ef0eb713f39ebf},
731 {0x8a2dbf142dfcc7ab, 0x6e3569326c784338}, {0xacb92ed9397bf996, 0x49c2c37f07965405},
732 {0xd7e77a8f87daf7fb, 0xdc33745ec97be907}, {0x86f0ac99b4e8dafd, 0x69a028bb3ded71a4},
733 {0xa8acd7c0222311bc, 0xc40832ea0d68ce0d}, {0xd2d80db02aabd62b, 0xf50a3fa490c30191},
734 {0x83c7088e1aab65db, 0x792667c6da79e0fb}, {0xa4b8cab1a1563f52, 0x577001b891185939},
735 {0xcde6fd5e09abcf26, 0xed4c0226b55e6f87}, {0x80b05e5ac60b6178, 0x544f8158315b05b5},
736 {0xa0dc75f1778e39d6, 0x696361ae3db1c722}, {0xc913936dd571c84c, 0x03bc3a19cd1e38ea},
737 {0xfb5878494ace3a5f, 0x04ab48a04065c724}, {0x9d174b2dcec0e47b, 0x62eb0d64283f9c77},
738 {0xc45d1df942711d9a, 0x3ba5d0bd324f8395}, {0xf5746577930d6500, 0xca8f44ec7ee3647a},
739 {0x9968bf6abbe85f20, 0x7e998b13cf4e1ecc}, {0xbfc2ef456ae276e8, 0x9e3fedd8c321a67f},
740 {0xefb3ab16c59b14a2, 0xc5cfe94ef3ea101f}, {0x95d04aee3b80ece5, 0xbba1f1d158724a13},
741 {0xbb445da9ca61281f, 0x2a8a6e45ae8edc98}, {0xea1575143cf97226, 0xf52d09d71a3293be},
742 {0x924d692ca61be758, 0x593c2626705f9c57}, {0xb6e0c377cfa2e12e, 0x6f8b2fb00c77836d},
743 {0xe498f455c38b997a, 0x0b6dfb9c0f956448}, {0x8edf98b59a373fec, 0x4724bd4189bd5ead},
744 {0xb2977ee300c50fe7, 0x58edec91ec2cb658}, {0xdf3d5e9bc0f653e1, 0x2f2967b66737e3ee},
745 {0x8b865b215899f46c, 0xbd79e0d20082ee75}, {0xae67f1e9aec07187, 0xecd8590680a3aa12},
746 {0xda01ee641a708de9, 0xe80e6f4820cc9496}, {0x884134fe908658b2, 0x3109058d147fdcde},
747 {0xaa51823e34a7eede, 0xbd4b46f0599fd416}, {0xd4e5e2cdc1d1ea96, 0x6c9e18ac7007c91b},
748 {0x850fadc09923329e, 0x03e2cf6bc604ddb1}, {0xa6539930bf6bff45, 0x84db8346b786151d},
749 {0xcfe87f7cef46ff16, 0xe612641865679a64}, {0x81f14fae158c5f6e, 0x4fcb7e8f3f60c07f},
750 {0xa26da3999aef7749, 0xe3be5e330f38f09e}, {0xcb090c8001ab551c, 0x5cadf5bfd3072cc6},
751 {0xfdcb4fa002162a63, 0x73d9732fc7c8f7f7}, {0x9e9f11c4014dda7e, 0x2867e7fddcdd9afb},
752 {0xc646d63501a1511d, 0xb281e1fd541501b9}, {0xf7d88bc24209a565, 0x1f225a7ca91a4227},
753 {0x9ae757596946075f, 0x3375788de9b06959}, {0xc1a12d2fc3978937, 0x0052d6b1641c83af},
754 {0xf209787bb47d6b84, 0xc0678c5dbd23a49b}, {0x9745eb4d50ce6332, 0xf840b7ba963646e1},
755 {0xbd176620a501fbff, 0xb650e5a93bc3d899}, {0xec5d3fa8ce427aff, 0xa3e51f138ab4cebf},
756 {0x93ba47c980e98cdf, 0xc66f336c36b10138}, {0xb8a8d9bbe123f017, 0xb80b0047445d4185},
757 {0xe6d3102ad96cec1d, 0xa60dc059157491e6}, {0x9043ea1ac7e41392, 0x87c89837ad68db30},
758 {0xb454e4a179dd1877, 0x29babe4598c311fc}, {0xe16a1dc9d8545e94, 0xf4296dd6fef3d67b},
759 {0x8ce2529e2734bb1d, 0x1899e4a65f58660d}, {0xb01ae745b101e9e4, 0x5ec05dcff72e7f90},
760 {0xdc21a1171d42645d, 0x76707543f4fa1f74}, {0x899504ae72497eba, 0x6a06494a791c53a9},
761 {0xabfa45da0edbde69, 0x0487db9d17636893}, {0xd6f8d7509292d603, 0x45a9d2845d3c42b7},
762 {0x865b86925b9bc5c2, 0x0b8a2392ba45a9b3}, {0xa7f26836f282b732, 0x8e6cac7768d7141f},
763 {0xd1ef0244af2364ff, 0x3207d795430cd927}, {0x8335616aed761f1f, 0x7f44e6bd49e807b9},
764 {0xa402b9c5a8d3a6e7, 0x5f16206c9c6209a7}, {0xcd036837130890a1, 0x36dba887c37a8c10},
765 {0x802221226be55a64, 0xc2494954da2c978a}, {0xa02aa96b06deb0fd, 0xf2db9baa10b7bd6d},
766 {0xc83553c5c8965d3d, 0x6f92829494e5acc8}, {0xfa42a8b73abbf48c, 0xcb772339ba1f17fa},
767 {0x9c69a97284b578d7, 0xff2a760414536efc}, {0xc38413cf25e2d70d, 0xfef5138519684abb},
768 {0xf46518c2ef5b8cd1, 0x7eb258665fc25d6a}, {0x98bf2f79d5993802, 0xef2f773ffbd97a62},
769 {0xbeeefb584aff8603, 0xaafb550ffacfd8fb}, {0xeeaaba2e5dbf6784, 0x95ba2a53f983cf39},
770 {0x952ab45cfa97a0b2, 0xdd945a747bf26184}, {0xba756174393d88df, 0x94f971119aeef9e5},
771 {0xe912b9d1478ceb17, 0x7a37cd5601aab85e}, {0x91abb422ccb812ee, 0xac62e055c10ab33b},
772 {0xb616a12b7fe617aa, 0x577b986b314d600a}, {0xe39c49765fdf9d94, 0xed5a7e85fda0b80c},
773 {0x8e41ade9fbebc27d, 0x14588f13be847308}, {0xb1d219647ae6b31c, 0x596eb2d8ae258fc9},
774 {0xde469fbd99a05fe3, 0x6fca5f8ed9aef3bc}, {0x8aec23d680043bee, 0x25de7bb9480d5855},
775 {0xada72ccc20054ae9, 0xaf561aa79a10ae6b}, {0xd910f7ff28069da4, 0x1b2ba1518094da05},
776 {0x87aa9aff79042286, 0x90fb44d2f05d0843}, {0xa99541bf57452b28, 0x353a1607ac744a54},
777 {0xd3fa922f2d1675f2, 0x42889b8997915ce9}, {0x847c9b5d7c2e09b7, 0x69956135febada12},
778 {0xa59bc234db398c25, 0x43fab9837e699096}, {0xcf02b2c21207ef2e, 0x94f967e45e03f4bc},
779 {0x8161afb94b44f57d, 0x1d1be0eebac278f6}, {0xa1ba1ba79e1632dc, 0x6462d92a69731733},
780 {0xca28a291859bbf93, 0x7d7b8f7503cfdcff}, {0xfcb2cb35e702af78, 0x5cda735244c3d43f},
781 {0x9defbf01b061adab, 0x3a0888136afa64a8}, {0xc56baec21c7a1916, 0x088aaa1845b8fdd1},
782 {0xf6c69a72a3989f5b, 0x8aad549e57273d46}, {0x9a3c2087a63f6399, 0x36ac54e2f678864c},
783 {0xc0cb28a98fcf3c7f, 0x84576a1bb416a7de}, {0xf0fdf2d3f3c30b9f, 0x656d44a2a11c51d6},
784 {0x969eb7c47859e743, 0x9f644ae5a4b1b326}, {0xbc4665b596706114, 0x873d5d9f0dde1fef},
785 {0xeb57ff22fc0c7959, 0xa90cb506d155a7eb}, {0x9316ff75dd87cbd8, 0x09a7f12442d588f3},
786 {0xb7dcbf5354e9bece, 0x0c11ed6d538aeb30}, {0xe5d3ef282a242e81, 0x8f1668c8a86da5fb},
787 {0x8fa475791a569d10, 0xf96e017d694487bd}, {0xb38d92d760ec4455, 0x37c981dcc395a9ad},
788 {0xe070f78d3927556a, 0x85bbe253f47b1418}, {0x8c469ab843b89562, 0x93956d7478ccec8f},
789 {0xaf58416654a6babb, 0x387ac8d1970027b3}, {0xdb2e51bfe9d0696a, 0x06997b05fcc0319f},
790 {0x88fcf317f22241e2, 0x441fece3bdf81f04}, {0xab3c2fddeeaad25a, 0xd527e81cad7626c4},
791 {0xd60b3bd56a5586f1, 0x8a71e223d8d3b075}, {0x85c7056562757456, 0xf6872d5667844e4a},
792 {0xa738c6bebb12d16c, 0xb428f8ac016561dc}, {0xd106f86e69d785c7, 0xe13336d701beba53},
793 {0x82a45b450226b39c, 0xecc0024661173474}, {0xa34d721642b06084, 0x27f002d7f95d0191},
794 {0xcc20ce9bd35c78a5, 0x31ec038df7b441f5}, {0xff290242c83396ce, 0x7e67047175a15272},
795 {0x9f79a169bd203e41, 0x0f0062c6e984d387}, {0xc75809c42c684dd1, 0x52c07b78a3e60869},
796 {0xf92e0c3537826145, 0xa7709a56ccdf8a83}, {0x9bbcc7a142b17ccb, 0x88a66076400bb692},
797 {0xc2abf989935ddbfe, 0x6acff893d00ea436}, {0xf356f7ebf83552fe, 0x0583f6b8c4124d44},
798 {0x98165af37b2153de, 0xc3727a337a8b704b}, {0xbe1bf1b059e9a8d6, 0x744f18c0592e4c5d},
799 {0xeda2ee1c7064130c, 0x1162def06f79df74}, {0x9485d4d1c63e8be7, 0x8addcb5645ac2ba9},
800 {0xb9a74a0637ce2ee1, 0x6d953e2bd7173693}, {0xe8111c87c5c1ba99, 0xc8fa8db6ccdd0438},
801 {0x910ab1d4db9914a0, 0x1d9c9892400a22a3}, {0xb54d5e4a127f59c8, 0x2503beb6d00cab4c},
802 {0xe2a0b5dc971f303a, 0x2e44ae64840fd61e}, {0x8da471a9de737e24, 0x5ceaecfed289e5d3},
803 {0xb10d8e1456105dad, 0x7425a83e872c5f48}, {0xdd50f1996b947518, 0xd12f124e28f7771a},
804 {0x8a5296ffe33cc92f, 0x82bd6b70d99aaa70}, {0xace73cbfdc0bfb7b, 0x636cc64d1001550c},
805 {0xd8210befd30efa5a, 0x3c47f7e05401aa4f}, {0x8714a775e3e95c78, 0x65acfaec34810a72},
806 {0xa8d9d1535ce3b396, 0x7f1839a741a14d0e}, {0xd31045a8341ca07c, 0x1ede48111209a051},
807 {0x83ea2b892091e44d, 0x934aed0aab460433}, {0xa4e4b66b68b65d60, 0xf81da84d56178540},
808 {0xce1de40642e3f4b9, 0x36251260ab9d668f}, {0x80d2ae83e9ce78f3, 0xc1d72b7c6b42601a},
809 {0xa1075a24e4421730, 0xb24cf65b8612f820}, {0xc94930ae1d529cfc, 0xdee033f26797b628},
810 {0xfb9b7cd9a4a7443c, 0x169840ef017da3b2}, {0x9d412e0806e88aa5, 0x8e1f289560ee864f},
811 {0xc491798a08a2ad4e, 0xf1a6f2bab92a27e3}, {0xf5b5d7ec8acb58a2, 0xae10af696774b1dc},
812 {0x9991a6f3d6bf1765, 0xacca6da1e0a8ef2a}, {0xbff610b0cc6edd3f, 0x17fd090a58d32af4},
813 {0xeff394dcff8a948e, 0xddfc4b4cef07f5b1}, {0x95f83d0a1fb69cd9, 0x4abdaf101564f98f},
814 {0xbb764c4ca7a4440f, 0x9d6d1ad41abe37f2}, {0xea53df5fd18d5513, 0x84c86189216dc5ee},
815 {0x92746b9be2f8552c, 0x32fd3cf5b4e49bb5}, {0xb7118682dbb66a77, 0x3fbc8c33221dc2a2},
816 {0xe4d5e82392a40515, 0x0fabaf3feaa5334b}, {0x8f05b1163ba6832d, 0x29cb4d87f2a7400f},
817 {0xb2c71d5bca9023f8, 0x743e20e9ef511013}, {0xdf78e4b2bd342cf6, 0x914da9246b255417},
818 {0x8bab8eefb6409c1a, 0x1ad089b6c2f7548f}, {0xae9672aba3d0c320, 0xa184ac2473b529b2},
819 {0xda3c0f568cc4f3e8, 0xc9e5d72d90a2741f}, {0x8865899617fb1871, 0x7e2fa67c7a658893},
820 {0xaa7eebfb9df9de8d, 0xddbb901b98feeab8}, {0xd51ea6fa85785631, 0x552a74227f3ea566},
821 {0x8533285c936b35de, 0xd53a88958f872760}, {0xa67ff273b8460356, 0x8a892abaf368f138},
822 {0xd01fef10a657842c, 0x2d2b7569b0432d86}, {0x8213f56a67f6b29b, 0x9c3b29620e29fc74},
823 {0xa298f2c501f45f42, 0x8349f3ba91b47b90}, {0xcb3f2f7642717713, 0x241c70a936219a74},
824 {0xfe0efb53d30dd4d7, 0xed238cd383aa0111}, {0x9ec95d1463e8a506, 0xf4363804324a40ab},
825 {0xc67bb4597ce2ce48, 0xb143c6053edcd0d6}, {0xf81aa16fdc1b81da, 0xdd94b7868e94050b},
826 {0x9b10a4e5e9913128, 0xca7cf2b4191c8327}, {0xc1d4ce1f63f57d72, 0xfd1c2f611f63a3f1},
827 {0xf24a01a73cf2dccf, 0xbc633b39673c8ced}, {0x976e41088617ca01, 0xd5be0503e085d814},
828 {0xbd49d14aa79dbc82, 0x4b2d8644d8a74e19}, {0xec9c459d51852ba2, 0xddf8e7d60ed1219f},
829 {0x93e1ab8252f33b45, 0xcabb90e5c942b504}, {0xb8da1662e7b00a17, 0x3d6a751f3b936244},
830 {0xe7109bfba19c0c9d, 0x0cc512670a783ad5}, {0x906a617d450187e2, 0x27fb2b80668b24c6},
831 {0xb484f9dc9641e9da, 0xb1f9f660802dedf7}, {0xe1a63853bbd26451, 0x5e7873f8a0396974},
832 {0x8d07e33455637eb2, 0xdb0b487b6423e1e9}, {0xb049dc016abc5e5f, 0x91ce1a9a3d2cda63},
833 {0xdc5c5301c56b75f7, 0x7641a140cc7810fc}, {0x89b9b3e11b6329ba, 0xa9e904c87fcb0a9e},
834 {0xac2820d9623bf429, 0x546345fa9fbdcd45}, {0xd732290fbacaf133, 0xa97c177947ad4096},
835 {0x867f59a9d4bed6c0, 0x49ed8eabcccc485e}, {0xa81f301449ee8c70, 0x5c68f256bfff5a75},
836 {0xd226fc195c6a2f8c, 0x73832eec6fff3112}, {0x83585d8fd9c25db7, 0xc831fd53c5ff7eac},
837 {0xa42e74f3d032f525, 0xba3e7ca8b77f5e56}, {0xcd3a1230c43fb26f, 0x28ce1bd2e55f35ec},
838 {0x80444b5e7aa7cf85, 0x7980d163cf5b81b4}, {0xa0555e361951c366, 0xd7e105bcc3326220},
839 {0xc86ab5c39fa63440, 0x8dd9472bf3fefaa8}, {0xfa856334878fc150, 0xb14f98f6f0feb952},
840 {0x9c935e00d4b9d8d2, 0x6ed1bf9a569f33d4}, {0xc3b8358109e84f07, 0x0a862f80ec4700c9},
841 {0xf4a642e14c6262c8, 0xcd27bb612758c0fb}, {0x98e7e9cccfbd7dbd, 0x8038d51cb897789d},
842 {0xbf21e44003acdd2c, 0xe0470a63e6bd56c4}, {0xeeea5d5004981478, 0x1858ccfce06cac75},
843 {0x95527a5202df0ccb, 0x0f37801e0c43ebc9}, {0xbaa718e68396cffd, 0xd30560258f54e6bb},
844 {0xe950df20247c83fd, 0x47c6b82ef32a206a}, {0x91d28b7416cdd27e, 0x4cdc331d57fa5442},
845 {0xb6472e511c81471d, 0xe0133fe4adf8e953}, {0xe3d8f9e563a198e5, 0x58180fddd97723a7},
846 {0x8e679c2f5e44ff8f, 0x570f09eaa7ea7649}, {0xb201833b35d63f73, 0x2cd2cc6551e513db},
847 {0xde81e40a034bcf4f, 0xf8077f7ea65e58d2}, {0x8b112e86420f6191, 0xfb04afaf27faf783},
848 {0xadd57a27d29339f6, 0x79c5db9af1f9b564}, {0xd94ad8b1c7380874, 0x18375281ae7822bd},
849 {0x87cec76f1c830548, 0x8f2293910d0b15b6}, {0xa9c2794ae3a3c69a, 0xb2eb3875504ddb23},
850 {0xd433179d9c8cb841, 0x5fa60692a46151ec}, {0x849feec281d7f328, 0xdbc7c41ba6bcd334},
851 {0xa5c7ea73224deff3, 0x12b9b522906c0801}, {0xcf39e50feae16bef, 0xd768226b34870a01},
852 {0x81842f29f2cce375, 0xe6a1158300d46641}, {0xa1e53af46f801c53, 0x60495ae3c1097fd1},
853 {0xca5e89b18b602368, 0x385bb19cb14bdfc5}, {0xfcf62c1dee382c42, 0x46729e03dd9ed7b6},
854 {0x9e19db92b4e31ba9, 0x6c07a2c26a8346d2}, {0xc5a05277621be293, 0xc7098b7305241886},
855 {0xf70867153aa2db38, 0xb8cbee4fc66d1ea8}};
856 };
857
858 #if defined(BOOST_NO_CXX17_INLINE_VARIABLES) && (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
859
860 template <bool b> constexpr int cache_holder_ieee754_binary64_impl<b>::cache_bits;
861 template <bool b> constexpr int cache_holder_ieee754_binary64_impl<b>::min_k;
862 template <bool b> constexpr int cache_holder_ieee754_binary64_impl<b>::max_k;
863 template <bool b> constexpr typename cache_holder_ieee754_binary64_impl<b>::cache_entry_type cache_holder_ieee754_binary64_impl<b>::cache[];
864
865 #endif
866
867 #if (!defined(BOOST_MSVC) || BOOST_MSVC != 1900)
868 using cache_holder_ieee754_binary64 = cache_holder_ieee754_binary64_impl<true>;
869 #endif
870
871 ////////////////////////////////////////////////////////////////////////////////////////
872 // Policies.
873 ////////////////////////////////////////////////////////////////////////////////////////
874
875 // Forward declare the implementation class.
876 template <typename Float, typename FloatTraits = dragonbox_float_traits<Float>>
877 struct impl;
878
879 namespace policy_impl {
880 // Sign policies.
881 namespace sign {
882 struct base {};
883
884 struct ignore : base
885 {
886 using sign_policy = ignore;
887 static constexpr bool return_has_sign = false;
888
889 template <typename SignedSignificandBits, typename ReturnType>
890 static BOOST_CXX14_CONSTEXPR void handle_sign(SignedSignificandBits, ReturnType&) noexcept {}
891 };
892
893 struct return_sign : base
894 {
895 using sign_policy = return_sign;
896 static constexpr bool return_has_sign = true;
897
898 template <typename SignedSignificandBits, typename ReturnType>
899 444 static BOOST_CXX14_CONSTEXPR void handle_sign(SignedSignificandBits s, ReturnType& r) noexcept
900 {
901 444 r.is_negative = s.is_negative();
902 444 }
903 };
904 }
905
906 // Trailing zero policies.
907 namespace trailing_zero {
908 struct base {};
909
910 struct ignore : base
911 {
912 using trailing_zero_policy = ignore;
913 static constexpr bool report_trailing_zeros = false;
914
915 template <typename Impl, typename ReturnType>
916 static BOOST_CXX14_CONSTEXPR void on_trailing_zeros(ReturnType&) noexcept {}
917
918 template <typename Impl, typename ReturnType>
919 static BOOST_CXX14_CONSTEXPR void no_trailing_zeros(ReturnType&) noexcept {}
920 };
921
922 struct remove : base
923 {
924 using trailing_zero_policy = remove;
925 static constexpr bool report_trailing_zeros = false;
926
927 template <typename Impl, typename ReturnType>
928 BOOST_FORCEINLINE static void on_trailing_zeros(ReturnType& r) noexcept
929 {
930 886 r.exponent += Impl::remove_trailing_zeros(r.significand);
931 443 }
932
933 template <typename Impl, typename ReturnType>
934 1 static BOOST_CXX14_CONSTEXPR void no_trailing_zeros(ReturnType&) noexcept {}
935 };
936
937 struct report : base
938 {
939 using trailing_zero_policy = report;
940 static constexpr bool report_trailing_zeros = true;
941
942 template <typename Impl, typename ReturnType>
943 static BOOST_CXX14_CONSTEXPR void on_trailing_zeros(ReturnType& r) noexcept
944 {
945 r.may_have_trailing_zeros = true;
946 }
947
948 template <typename Impl, typename ReturnType>
949 static BOOST_CXX14_CONSTEXPR void no_trailing_zeros(ReturnType& r) noexcept
950 {
951 r.may_have_trailing_zeros = false;
952 }
953 };
954 }
955
956 // Decimal-to-binary rounding mode policies.
957 namespace decimal_to_binary_rounding {
958 struct base {};
959
960 enum class tag_t
961 {
962 to_nearest,
963 left_closed_directed,
964 right_closed_directed
965 };
966
967 namespace interval_type {
968 struct symmetric_boundary
969 {
970 static constexpr bool is_symmetric = true;
971 bool is_closed;
972 ✗ constexpr bool include_left_endpoint() const noexcept { return is_closed; }
973 9 constexpr bool include_right_endpoint() const noexcept { return is_closed; }
974 };
975
976 struct asymmetric_boundary
977 {
978 static constexpr bool is_symmetric = false;
979 bool is_left_closed;
980 constexpr bool include_left_endpoint() const noexcept { return is_left_closed; }
981 constexpr bool include_right_endpoint() const noexcept { return !is_left_closed; }
982 };
983
984 struct closed
985 {
986 static constexpr bool is_symmetric = true;
987 138 static constexpr bool include_left_endpoint() noexcept { return true; }
988 138 static constexpr bool include_right_endpoint() noexcept { return true; }
989 };
990
991 struct open
992 {
993 static constexpr bool is_symmetric = true;
994 static constexpr bool include_left_endpoint() noexcept { return false; }
995 static constexpr bool include_right_endpoint() noexcept { return false; }
996 };
997
998 struct left_closed_right_open
999 {
1000 static constexpr bool is_symmetric = false;
1001 static constexpr bool include_left_endpoint() noexcept { return true; }
1002 static constexpr bool include_right_endpoint() noexcept { return false; }
1003 };
1004
1005 struct right_closed_left_open
1006 {
1007 static constexpr bool is_symmetric = false;
1008 static constexpr bool include_left_endpoint() noexcept { return false; }
1009 static constexpr bool include_right_endpoint() noexcept { return true; }
1010 };
1011 }
1012
1013 template <typename T>
1014 struct return_type : return_type<decltype(&T::operator())>
1015 {};
1016
1017 struct nearest_to_even : base
1018 {
1019 using decimal_to_binary_rounding_policy = nearest_to_even;
1020 static constexpr auto tag = tag_t::to_nearest;
1021 using normal_interval_type = interval_type::symmetric_boundary;
1022 using shorter_interval_type = interval_type::closed;
1023
1024 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1025 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func f) noexcept
1026 {
1027 444 return f(nearest_to_even{});
1028 }
1029
1030 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1031 BOOST_FORCEINLINE static constexpr ReturnType
1032 invoke_normal_interval_case(SignedSignificandBits s, Func&& f) noexcept
1033 {
1034 306 return f(s.has_even_significand_bits());
1035 }
1036
1037 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1038 BOOST_FORCEINLINE static constexpr ReturnType
1039 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1040 {
1041 138 return f();
1042 }
1043 };
1044
1045 struct nearest_to_odd : base
1046 {
1047 using decimal_to_binary_rounding_policy = nearest_to_odd;
1048 static constexpr auto tag = tag_t::to_nearest;
1049 using normal_interval_type = interval_type::symmetric_boundary;
1050 using shorter_interval_type = interval_type::open;
1051
1052 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1053 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1054 {
1055 return f(nearest_to_odd{});
1056 }
1057
1058 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1059 BOOST_FORCEINLINE static constexpr ReturnType
1060 invoke_normal_interval_case(SignedSignificandBits s, Func&& f) noexcept
1061 {
1062 return f(!s.has_even_significand_bits());
1063 }
1064
1065 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1066 BOOST_FORCEINLINE static constexpr ReturnType
1067 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1068 {
1069 return f();
1070 }
1071 };
1072
1073 struct nearest_toward_plus_infinity : base
1074 {
1075 using decimal_to_binary_rounding_policy = nearest_toward_plus_infinity;
1076 static constexpr auto tag = tag_t::to_nearest;
1077 using normal_interval_type = interval_type::asymmetric_boundary;
1078 using shorter_interval_type = interval_type::asymmetric_boundary;
1079
1080 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1081 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1082 {
1083 return f(nearest_toward_plus_infinity{});
1084 }
1085
1086 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1087 BOOST_FORCEINLINE static constexpr ReturnType
1088 invoke_normal_interval_case(SignedSignificandBits s, Func&& f) noexcept
1089 {
1090 return f(!s.is_negative());
1091 }
1092
1093 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1094 BOOST_FORCEINLINE static constexpr ReturnType
1095 invoke_shorter_interval_case(SignedSignificandBits s, Func&& f) noexcept
1096 {
1097 return f(!s.is_negative());
1098 }
1099 };
1100
1101 struct nearest_toward_minus_infinity : base
1102 {
1103 using decimal_to_binary_rounding_policy = nearest_toward_minus_infinity;
1104 static constexpr auto tag = tag_t::to_nearest;
1105 using normal_interval_type = interval_type::asymmetric_boundary;
1106 using shorter_interval_type = interval_type::asymmetric_boundary;
1107
1108 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1109 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1110 {
1111 return f(nearest_toward_minus_infinity{});
1112 }
1113
1114 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1115 BOOST_FORCEINLINE static constexpr ReturnType
1116 invoke_normal_interval_case(SignedSignificandBits s, Func&& f) noexcept
1117 {
1118 return f(s.is_negative());
1119 }
1120
1121 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1122 BOOST_FORCEINLINE static constexpr ReturnType
1123 invoke_shorter_interval_case(SignedSignificandBits s, Func&& f) noexcept
1124 {
1125 return f(s.is_negative());
1126 }
1127 };
1128
1129 struct nearest_toward_zero : base
1130 {
1131 using decimal_to_binary_rounding_policy = nearest_toward_zero;
1132 static constexpr auto tag = tag_t::to_nearest;
1133 using normal_interval_type = interval_type::right_closed_left_open;
1134 using shorter_interval_type = interval_type::right_closed_left_open;
1135
1136 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1137 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1138 {
1139 return f(nearest_toward_zero{});
1140 }
1141
1142 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1143 BOOST_FORCEINLINE static constexpr ReturnType
1144 invoke_normal_interval_case(SignedSignificandBits, Func&& f) noexcept
1145 {
1146 return f();
1147 }
1148
1149 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1150 BOOST_FORCEINLINE static constexpr ReturnType
1151 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1152 {
1153 return f();
1154 }
1155 };
1156
1157 struct nearest_away_from_zero : base
1158 {
1159 using decimal_to_binary_rounding_policy = nearest_away_from_zero;
1160 static constexpr auto tag = tag_t::to_nearest;
1161 using normal_interval_type = interval_type::left_closed_right_open;
1162 using shorter_interval_type = interval_type::left_closed_right_open;
1163
1164 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1165 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1166 {
1167 return f(nearest_away_from_zero{});
1168 }
1169
1170 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1171 BOOST_FORCEINLINE static constexpr ReturnType
1172 invoke_normal_interval_case(SignedSignificandBits, Func&& f) noexcept
1173 {
1174 return f();
1175 }
1176
1177 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1178 BOOST_FORCEINLINE static constexpr ReturnType
1179 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1180 {
1181 return f();
1182 }
1183 };
1184
1185 struct nearest_always_closed
1186 {
1187 static constexpr auto tag = tag_t::to_nearest;
1188 using normal_interval_type = interval_type::closed;
1189 using shorter_interval_type = interval_type::closed;
1190
1191 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1192 BOOST_FORCEINLINE static constexpr ReturnType
1193 invoke_normal_interval_case(SignedSignificandBits, Func&& f) noexcept
1194 {
1195 return f();
1196 }
1197
1198 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1199 BOOST_FORCEINLINE static constexpr ReturnType
1200 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1201 {
1202 return f();
1203 }
1204 };
1205
1206 struct nearest_always_open
1207 {
1208 static constexpr auto tag = tag_t::to_nearest;
1209 using normal_interval_type = interval_type::open;
1210 using shorter_interval_type = interval_type::open;
1211
1212 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1213 BOOST_FORCEINLINE static constexpr ReturnType
1214 invoke_normal_interval_case(SignedSignificandBits, Func&& f) noexcept
1215 {
1216 return f();
1217 }
1218
1219 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1220 BOOST_FORCEINLINE static constexpr ReturnType
1221 invoke_shorter_interval_case(SignedSignificandBits, Func&& f) noexcept
1222 {
1223 return f();
1224 }
1225 };
1226
1227 struct nearest_to_even_static_boundary : base
1228 {
1229 using decimal_to_binary_rounding_policy = nearest_to_even_static_boundary;
1230
1231 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1232 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1233 {
1234 if (s.has_even_significand_bits())
1235 {
1236 return f(nearest_always_closed{});
1237 }
1238 else
1239 {
1240 return f(nearest_always_open{});
1241 }
1242 }
1243 };
1244
1245 struct nearest_to_odd_static_boundary : base
1246 {
1247 using decimal_to_binary_rounding_policy = nearest_to_odd_static_boundary;
1248
1249 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1250 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1251 {
1252 if (s.has_even_significand_bits())
1253 {
1254 return f(nearest_always_open{});
1255 }
1256 else
1257 {
1258 return f(nearest_always_closed{});
1259 }
1260 }
1261 };
1262 struct nearest_toward_plus_infinity_static_boundary : base
1263 {
1264 using decimal_to_binary_rounding_policy = nearest_toward_plus_infinity_static_boundary;
1265
1266 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1267 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1268 {
1269 if (s.is_negative())
1270 {
1271 return f(nearest_toward_zero{});
1272 }
1273 else
1274 {
1275 return f(nearest_away_from_zero{});
1276 }
1277 }
1278 };
1279
1280 struct nearest_toward_minus_infinity_static_boundary : base
1281 {
1282 using decimal_to_binary_rounding_policy = nearest_toward_minus_infinity_static_boundary;
1283
1284 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1285 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1286 {
1287 if (s.is_negative())
1288 {
1289 return f(nearest_away_from_zero{});
1290 }
1291 else
1292 {
1293 return f(nearest_toward_zero{});
1294 }
1295 }
1296 };
1297
1298 struct left_closed_directed
1299 {
1300 static constexpr auto tag = tag_t::left_closed_directed;
1301 };
1302 struct right_closed_directed
1303 {
1304 static constexpr auto tag = tag_t::right_closed_directed;
1305 };
1306
1307 struct toward_plus_infinity : base
1308 {
1309 using decimal_to_binary_rounding_policy = toward_plus_infinity;
1310
1311 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1312 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1313 {
1314 if (s.is_negative())
1315 {
1316 return f(left_closed_directed{});
1317 }
1318 else
1319 {
1320 return f(right_closed_directed{});
1321 }
1322 }
1323 };
1324
1325 struct toward_minus_infinity : base
1326 {
1327 using decimal_to_binary_rounding_policy = toward_minus_infinity;
1328
1329 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1330 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits s, Func&& f) noexcept
1331 {
1332 if (s.is_negative())
1333 {
1334 return f(right_closed_directed{});
1335 }
1336 else
1337 {
1338 return f(left_closed_directed{});
1339 }
1340 }
1341 };
1342
1343 struct toward_zero : base
1344 {
1345 using decimal_to_binary_rounding_policy = toward_zero;
1346
1347 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1348 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1349 {
1350 return f(left_closed_directed{});
1351 }
1352 };
1353
1354 struct away_from_zero : base
1355 {
1356 using decimal_to_binary_rounding_policy = away_from_zero;
1357
1358 template <typename ReturnType, typename SignedSignificandBits, typename Func>
1359 BOOST_FORCEINLINE static ReturnType delegate(SignedSignificandBits, Func&& f) noexcept
1360 {
1361 return f(right_closed_directed{});
1362 }
1363 };
1364 }
1365
1366 // Binary-to-decimal rounding policies.
1367 // (Always assumes nearest rounding modes.)
1368 namespace binary_to_decimal_rounding {
1369 struct base {};
1370
1371 enum class tag_t
1372 {
1373 do_not_care,
1374 to_even,
1375 to_odd,
1376 away_from_zero,
1377 toward_zero
1378 };
1379
1380 struct do_not_care : base
1381 {
1382 using binary_to_decimal_rounding_policy = do_not_care;
1383 static constexpr auto tag = tag_t::do_not_care;
1384
1385 template <typename ReturnType>
1386 static constexpr bool prefer_round_down(ReturnType const&) noexcept
1387 {
1388 return false;
1389 }
1390 };
1391
1392 struct to_even : base
1393 {
1394 using binary_to_decimal_rounding_policy = to_even;
1395 static constexpr auto tag = tag_t::to_even;
1396
1397 template <typename ReturnType>
1398 ✗ static constexpr bool prefer_round_down(ReturnType const& r) noexcept
1399 {
1400 ✗ return r.significand % 2 != 0;
1401 }
1402 };
1403
1404 struct to_odd : base
1405 {
1406 using binary_to_decimal_rounding_policy = to_odd;
1407 static constexpr auto tag = tag_t::to_odd;
1408
1409 template <typename ReturnType>
1410 static constexpr bool prefer_round_down(ReturnType const& r) noexcept
1411 {
1412 return r.significand % 2 == 0;
1413 }
1414 };
1415
1416 struct away_from_zero : base
1417 {
1418 using binary_to_decimal_rounding_policy = away_from_zero;
1419 static constexpr auto tag = tag_t::away_from_zero;
1420
1421 template <typename ReturnType>
1422 static constexpr bool prefer_round_down(ReturnType const&) noexcept
1423 {
1424 return false;
1425 }
1426 };
1427
1428 struct toward_zero : base
1429 {
1430 using binary_to_decimal_rounding_policy = toward_zero;
1431 static constexpr auto tag = tag_t::toward_zero;
1432
1433 template <typename ReturnType>
1434 static constexpr bool prefer_round_down(ReturnType const&) noexcept
1435 {
1436 return true;
1437 }
1438 };
1439 }
1440
1441 // Cache policies.
1442 namespace cache {
1443 struct base {};
1444
1445 struct full : base
1446 {
1447 using cache_policy = full;
1448
1449 template <typename FloatFormat, typename cache_format = typename std::conditional<std::is_same<FloatFormat, ieee754_binary32>::value,
1450 cache_holder_ieee754_binary32,
1451 cache_holder_ieee754_binary64>::type>
1452 444 static constexpr typename cache_format::cache_entry_type get_cache(int k) noexcept
1453 {
1454 444 return cache_format::cache[std::size_t(k - cache_format::min_k)];
1455 }
1456 };
1457 }
1458 }
1459
1460 namespace policy {
1461 namespace sign {
1462 BOOST_INLINE_VARIABLE constexpr auto ignore = detail::policy_impl::sign::ignore{};
1463 BOOST_INLINE_VARIABLE constexpr auto return_sign = detail::policy_impl::sign::return_sign{};
1464 }
1465
1466 namespace trailing_zero {
1467 BOOST_INLINE_VARIABLE constexpr auto ignore = detail::policy_impl::trailing_zero::ignore{};
1468 BOOST_INLINE_VARIABLE constexpr auto remove = detail::policy_impl::trailing_zero::remove{};
1469 BOOST_INLINE_VARIABLE constexpr auto report = detail::policy_impl::trailing_zero::report{};
1470 }
1471
1472 namespace decimal_to_binary_rounding {
1473 BOOST_INLINE_VARIABLE constexpr auto nearest_to_even =
1474 detail::policy_impl::decimal_to_binary_rounding::nearest_to_even{};
1475 BOOST_INLINE_VARIABLE constexpr auto nearest_to_odd =
1476 detail::policy_impl::decimal_to_binary_rounding::nearest_to_odd{};
1477 BOOST_INLINE_VARIABLE constexpr auto nearest_toward_plus_infinity =
1478 detail::policy_impl::decimal_to_binary_rounding::nearest_toward_plus_infinity{};
1479 BOOST_INLINE_VARIABLE constexpr auto nearest_toward_minus_infinity =
1480 detail::policy_impl::decimal_to_binary_rounding::nearest_toward_minus_infinity{};
1481 BOOST_INLINE_VARIABLE constexpr auto nearest_toward_zero =
1482 detail::policy_impl::decimal_to_binary_rounding::nearest_toward_zero{};
1483 BOOST_INLINE_VARIABLE constexpr auto nearest_away_from_zero =
1484 detail::policy_impl::decimal_to_binary_rounding::nearest_away_from_zero{};
1485
1486 BOOST_INLINE_VARIABLE constexpr auto nearest_to_even_static_boundary =
1487 detail::policy_impl::decimal_to_binary_rounding::nearest_to_even_static_boundary{};
1488 BOOST_INLINE_VARIABLE constexpr auto nearest_to_odd_static_boundary =
1489 detail::policy_impl::decimal_to_binary_rounding::nearest_to_odd_static_boundary{};
1490 BOOST_INLINE_VARIABLE constexpr auto nearest_toward_plus_infinity_static_boundary =
1491 detail::policy_impl::decimal_to_binary_rounding::
1492 nearest_toward_plus_infinity_static_boundary{};
1493 BOOST_INLINE_VARIABLE constexpr auto nearest_toward_minus_infinity_static_boundary =
1494 detail::policy_impl::decimal_to_binary_rounding::
1495 nearest_toward_minus_infinity_static_boundary{};
1496
1497 BOOST_INLINE_VARIABLE constexpr auto toward_plus_infinity =
1498 detail::policy_impl::decimal_to_binary_rounding::toward_plus_infinity{};
1499 BOOST_INLINE_VARIABLE constexpr auto toward_minus_infinity =
1500 detail::policy_impl::decimal_to_binary_rounding::toward_minus_infinity{};
1501 BOOST_INLINE_VARIABLE constexpr auto toward_zero =
1502 detail::policy_impl::decimal_to_binary_rounding::toward_zero{};
1503 BOOST_INLINE_VARIABLE constexpr auto away_from_zero =
1504 detail::policy_impl::decimal_to_binary_rounding::away_from_zero{};
1505 }
1506
1507 namespace binary_to_decimal_rounding {
1508 BOOST_INLINE_VARIABLE constexpr auto do_not_care =
1509 detail::policy_impl::binary_to_decimal_rounding::do_not_care{};
1510 BOOST_INLINE_VARIABLE constexpr auto to_even =
1511 detail::policy_impl::binary_to_decimal_rounding::to_even{};
1512 BOOST_INLINE_VARIABLE constexpr auto to_odd =
1513 detail::policy_impl::binary_to_decimal_rounding::to_odd{};
1514 BOOST_INLINE_VARIABLE constexpr auto away_from_zero =
1515 detail::policy_impl::binary_to_decimal_rounding::away_from_zero{};
1516 BOOST_INLINE_VARIABLE constexpr auto toward_zero =
1517 detail::policy_impl::binary_to_decimal_rounding::toward_zero{};
1518 }
1519
1520 namespace cache {
1521 BOOST_INLINE_VARIABLE constexpr auto full = detail::policy_impl::cache::full{};
1522 }
1523 } // Namespace Policy
1524
1525 ////////////////////////////////////////////////////////////////////////////////////////
1526 // The main algorithm.
1527 ////////////////////////////////////////////////////////////////////////////////////////
1528
1529 template <typename Float, typename FloatTraits>
1530 struct impl : private FloatTraits, private FloatTraits::format
1531 {
1532 using format = typename FloatTraits::format;
1533 using carrier_uint = typename FloatTraits::carrier_uint;
1534
1535 using FloatTraits::carrier_bits;
1536 using format::significand_bits;
1537 using format::min_exponent;
1538 using format::max_exponent;
1539 using format::exponent_bias;
1540 using format::decimal_digits;
1541
1542 static constexpr int kappa = std::is_same<format, ieee754_binary32>::value ? 1 : 2;
1543 static_assert(kappa >= 1, "Kappa must be >= 1");
1544 // static_assert(carrier_bits >= significand_bits + 2 + log::floor_log2_pow10(kappa + 1));
1545
1546 static constexpr int min_k_a = -log::floor_log10_pow2_minus_log10_4_over_3(int(max_exponent - significand_bits));
1547 static constexpr int min_k_b = -log::floor_log10_pow2(int(max_exponent - significand_bits)) + kappa;
1548 static constexpr int min_k = min_k_a < min_k_b ? min_k_a : min_k_b;
1549 // static_assert(min_k >= cache_holder<format>::min_k, "Min k is not in the cache");
1550
1551 static constexpr int max_k_a = -log::floor_log10_pow2_minus_log10_4_over_3(int(min_exponent - significand_bits /*+ 1*/));
1552 static constexpr int max_k_b = -log::floor_log10_pow2(int(min_exponent - significand_bits)) + kappa;
1553 static constexpr int max_k = max_k_a > max_k_b ? max_k_a : max_k_b;
1554
1555 using cache_format = typename std::conditional<std::is_same<format, ieee754_binary32>::value,
1556 cache_holder_ieee754_binary32,
1557 cache_holder_ieee754_binary64>::type;
1558 using cache_entry_type = typename cache_format::cache_entry_type;
1559 static constexpr auto cache_bits = cache_format::cache_bits;
1560
1561 static constexpr int case_shorter_interval_left_endpoint_lower_threshold = 2;
1562 static BOOST_CXX14_CONSTEXPR const int case_shorter_interval_left_endpoint_upper_threshold = 3;
1563 //2 + log::floor_log2(compute_power(10, count_factors<5>((carrier_uint(1) << (significand_bits + 2)) - 1) + 1) / 3);
1564
1565 static constexpr int case_shorter_interval_right_endpoint_lower_threshold = 0;
1566 static BOOST_CXX14_CONSTEXPR const int case_shorter_interval_right_endpoint_upper_threshold = 3;
1567 //2 + log::floor_log2(compute_power(10, count_factors<5>((carrier_uint(1) << (significand_bits + 1)) + 1) + 1) / 3);
1568
1569 static constexpr int shorter_interval_tie_lower_threshold =
1570 -log::floor_log5_pow2_minus_log5_3(significand_bits + 4) - 2 - significand_bits;
1571 static constexpr int shorter_interval_tie_upper_threshold =
1572 -log::floor_log5_pow2(significand_bits + 2) - 2 - significand_bits;
1573
1574 struct compute_mul_result
1575 {
1576 carrier_uint result;
1577 bool is_integer;
1578 };
1579
1580 struct compute_mul_parity_result
1581 {
1582 bool parity;
1583 bool is_integer;
1584 };
1585
1586 //// The main algorithm assumes the input is a normal/subnormal finite number
1587
1588 #if defined(__GNUC__) && (__GNUC__ < 5) && !defined(__clang__)
1589 # pragma GCC diagnostic push
1590 # pragma GCC diagnostic ignored "-Wmissing-field-initializers"
1591 #endif
1592
1593 template <typename ReturnType, typename IntervalType, typename TrailingZeroPolicy,
1594 typename BinaryToDecimalRoundingPolicy, typename CachePolicy, typename... AdditionalArgs>
1595 306 BOOST_JSON_SAFEBUFFERS static ReturnType compute_nearest_normal(carrier_uint const two_fc, const int exponent,
1596 AdditionalArgs... additional_args) noexcept
1597 {
1598 //////////////////////////////////////////////////////////////////////
1599 // Step 1: Schubfach multiplier calculation
1600 //////////////////////////////////////////////////////////////////////
1601
1602 306 ReturnType ret_value = {};
1603 306 IntervalType interval_type{additional_args...};
1604
1605 // Compute k and beta.
1606 306 const int minus_k = log::floor_log10_pow2(exponent) - kappa;
1607 306 const auto cache = CachePolicy::template get_cache<format>(-minus_k);
1608 306 const int beta = exponent + log::floor_log2_pow10(-minus_k);
1609
1610 // Compute zi and deltai.
1611 // 10^kappa <= deltai < 10^(kappa + 1)
1612 306 const auto deltai = compute_delta(cache, beta);
1613 // For the case of binary32, the result of integer check is not correct for
1614 // 29711844 * 2^-82
1615 // = 6.1442653300000000008655037797566933477355632930994033813476... * 10^-18
1616 // and 29711844 * 2^-81
1617 // = 1.2288530660000000001731007559513386695471126586198806762695... * 10^-17,
1618 // and they are the unique counterexamples. However, since 29711844 is even,
1619 // this does not cause any problem for the endpoints calculations; it can only
1620 // cause a problem when we need to perform integer check for the center.
1621 // Fortunately, with these inputs, that branch is never executed, so we are fine.
1622 //const auto [zi, is_z_integer] = compute_mul((two_fc | 1) << beta, cache);
1623 306 const auto z_res = compute_mul((two_fc | 1) << beta, cache);
1624 306 const auto zi = z_res.result;
1625 306 const auto is_z_integer = z_res.is_integer;
1626
1627 //////////////////////////////////////////////////////////////////////
1628 // Step 2: Try larger divisor; remove trailing zeros if necessary
1629 //////////////////////////////////////////////////////////////////////
1630
1631 306 BOOST_CXX14_CONSTEXPR auto big_divisor = compute_power(std::uint32_t(10), kappa + 1);
1632 306 BOOST_CXX14_CONSTEXPR auto small_divisor = compute_power(std::uint32_t(10), kappa);
1633
1634 // Using an upper bound on zi, we might be able to optimize the division
1635 // better than the compiler; we are computing zi / big_divisor here.
1636 #ifdef BOOST_NO_CXX14_CONSTEXPR
1637 306 ret_value.significand = div::divide_by_pow10<carrier_uint>(kappa + 1, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1, zi);
1638 #else
1639 ret_value.significand = div::divide_by_pow10<kappa + 1, carrier_uint, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1>(zi);
1640 #endif
1641
1642 306 auto r = std::uint32_t(zi - big_divisor * ret_value.significand);
1643
1644
2/2
✓ Branch 0 taken 305 times.
✓ Branch 1 taken 1 times.
 306 if (r < deltai)
1645 {
1646 // Exclude the right endpoint if necessary.
1647
4/6
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 296 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 305 times.
 305 if (r == 0 && (is_z_integer & !interval_type.include_right_endpoint()))
1648 {
1649 BOOST_IF_CONSTEXPR (BinaryToDecimalRoundingPolicy::tag == policy_impl::binary_to_decimal_rounding::tag_t::do_not_care)
1650 {
1651 ret_value.significand *= 10;
1652 ret_value.exponent = minus_k + kappa;
1653 --ret_value.significand;
1654 TrailingZeroPolicy::template no_trailing_zeros<impl>(ret_value);
1655
1656 return ret_value;
1657 }
1658 else
1659 {
1660 ✗ --ret_value.significand;
1661 ✗ r = big_divisor;
1662
1663 ✗ goto small_divisor_case_label;
1664 }
1665 }
1666 }
1667
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 else if (r > deltai)
1668 {
1669 1 goto small_divisor_case_label;
1670 }
1671 else
1672 {
1673 // r == deltai; compare fractional parts.
1674 // const auto [xi_parity, x_is_integer] =
1675 // compute_mul_parity(two_fc - 1, cache, beta);
1676 ✗ const auto x_res = compute_mul_parity(two_fc - 1, cache, beta);
1677 ✗ const auto xi_parity = x_res.parity;
1678 ✗ const auto x_is_integer = x_res.is_integer;
1679
1680 ✗ if (!(xi_parity | (x_is_integer & interval_type.include_left_endpoint())))
1681 {
1682 ✗ goto small_divisor_case_label;
1683 }
1684 }
1685 305 ret_value.exponent = minus_k + kappa + 1;
1686
1687 // We may need to remove trailing zeros.
1688 TrailingZeroPolicy::template on_trailing_zeros<impl>(ret_value);
1689 305 return ret_value;
1690
1691
1692 //////////////////////////////////////////////////////////////////////
1693 // Step 3: Find the significand with the smaller divisor
1694 //////////////////////////////////////////////////////////////////////
1695
1696 1 small_divisor_case_label:
1697 1 TrailingZeroPolicy::template no_trailing_zeros<impl>(ret_value);
1698 1 ret_value.significand *= 10;
1699 1 ret_value.exponent = minus_k + kappa;
1700
1701 BOOST_IF_CONSTEXPR (BinaryToDecimalRoundingPolicy::tag == policy_impl::binary_to_decimal_rounding::tag_t::do_not_care)
1702 {
1703 // Normally, we want to compute
1704 // ret_value.significand += r / small_divisor
1705 // and return, but we need to take care of the case that the resulting
1706 // value is exactly the right endpoint, while that is not included in the
1707 // interval.
1708 if (!interval_type.include_right_endpoint())
1709 {
1710 // Is r divisible by 10^kappa?
1711 if (is_z_integer && div::check_divisibility_and_divide_by_pow10<kappa>(r))
1712 {
1713 // This should be in the interval.
1714 ret_value.significand += r - 1;
1715 }
1716 else
1717 {
1718 ret_value.significand += r;
1719 }
1720 }
1721 else
1722 {
1723 ret_value.significand += div::small_division_by_pow10<kappa>(r);
1724 }
1725 }
1726 else
1727 {
1728 1 auto dist = r - (deltai / 2) + (small_divisor / 2);
1729 1 const bool approx_y_parity = ((dist ^ (small_divisor / 2)) & 1) != 0;
1730
1731 // Is dist divisible by 10^kappa?
1732 1 const bool divisible_by_small_divisor = div::check_divisibility_and_divide_by_pow10<kappa>(dist);
1733
1734 // Add dist / 10^kappa to the significand.
1735 1 ret_value.significand += dist;
1736
1737
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (divisible_by_small_divisor)
1738 {
1739 // Check z^(f) >= epsilon^(f).
1740 // We have either yi == zi - epsiloni or yi == (zi - epsiloni) - 1,
1741 // where yi == zi - epsiloni if and only if z^(f) >= epsilon^(f).
1742 // Since there are only 2 possibilities, we only need to care about the
1743 // parity. Also, zi and r should have the same parity since the divisor is
1744 // an even number.
1745 //const auto [yi_parity, is_y_integer] =
1746 // compute_mul_parity(two_fc, cache, beta);
1747 ✗ const auto y_res = compute_mul_parity(two_fc, cache, beta);
1748 ✗ const auto yi_parity = y_res.parity;
1749 ✗ const auto is_y_integer = y_res.is_integer;
1750
1751 ✗ if (yi_parity != approx_y_parity)
1752 {
1753 ✗ --ret_value.significand;
1754 }
1755 else
1756 {
1757 // If z^(f) >= epsilon^(f), we might have a tie
1758 // when z^(f) == epsilon^(f), or equivalently, when y is an integer.
1759 // For tie-to-up case, we can just choose the upper one.
1760 ✗ if (BinaryToDecimalRoundingPolicy::prefer_round_down(ret_value) & is_y_integer)
1761 {
1762 ✗ --ret_value.significand;
1763 }
1764 }
1765 }
1766 }
1767
1768 1 return ret_value;
1769 }
1770
1771 template <typename ReturnType, typename IntervalType, typename TrailingZeroPolicy,
1772 typename BinaryToDecimalRoundingPolicy, typename CachePolicy, typename... AdditionalArgs>
1773 138 BOOST_JSON_SAFEBUFFERS static ReturnType compute_nearest_shorter(const int exponent, AdditionalArgs... additional_args) noexcept
1774 {
1775 138 ReturnType ret_value = {};
1776 IntervalType interval_type{additional_args...};
1777
1778 // Compute k and beta.
1779 138 const int minus_k = log::floor_log10_pow2_minus_log10_4_over_3(exponent);
1780 138 const int beta = exponent + log::floor_log2_pow10(-minus_k);
1781
1782 // Compute xi and zi.
1783 138 const auto cache = CachePolicy::template get_cache<format>(-minus_k);
1784
1785 138 auto xi = compute_left_endpoint_for_shorter_interval_case(cache, beta);
1786 138 auto zi = compute_right_endpoint_for_shorter_interval_case(cache, beta);
1787
1788 // If we don't accept the right endpoint and
1789 // if the right endpoint is an integer, decrease it.
1790
2/6
✗ Branch 1 not taken.
✓ Branch 2 taken 138 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 138 times.
 138 if (!interval_type.include_right_endpoint() && is_right_endpoint_integer_shorter_interval(exponent))
1791 {
1792 ✗ --zi;
1793 }
1794 // If we don't accept the left endpoint or
1795 // if the left endpoint is not an integer, increase it.
1796
3/6
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 138 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 138 times.
✗ Branch 7 not taken.
 138 if (!interval_type.include_left_endpoint() || !is_left_endpoint_integer_shorter_interval(exponent))
1797 {
1798 138 ++xi;
1799 }
1800
1801 // Try bigger divisor.
1802 138 ret_value.significand = zi / 10;
1803
1804 // If succeed, remove trailing zeros if necessary and return.
1805
1/2
✓ Branch 0 taken 138 times.
✗ Branch 1 not taken.
 138 if (ret_value.significand * 10 >= xi)
1806 {
1807 138 ret_value.exponent = minus_k + 1;
1808 TrailingZeroPolicy::template on_trailing_zeros<impl>(ret_value);
1809 138 return ret_value;
1810 }
1811
1812 // Otherwise, compute the round-up of y.
1813 ✗ TrailingZeroPolicy::template no_trailing_zeros<impl>(ret_value);
1814 ✗ ret_value.significand = compute_round_up_for_shorter_interval_case(cache, beta);
1815 ✗ ret_value.exponent = minus_k;
1816
1817 // When tie occurs, choose one of them according to the rule.
1818 ✗ if (BinaryToDecimalRoundingPolicy::prefer_round_down(ret_value) &&
1819 ✗ exponent >= shorter_interval_tie_lower_threshold &&
1820 exponent <= shorter_interval_tie_upper_threshold)
1821 {
1822 ✗ --ret_value.significand;
1823 }
1824 ✗ else if (ret_value.significand < xi)
1825 {
1826 ✗ ++ret_value.significand;
1827 }
1828
1829 ✗ return ret_value;
1830 }
1831
1832 #if defined(__GNUC__) && (__GNUC__ < 5) && !defined(__clang__)
1833 # pragma GCC diagnostic pop
1834 #endif
1835
1836 template <class ReturnType, class TrailingZeroPolicy, class CachePolicy>
1837 BOOST_JSON_SAFEBUFFERS static ReturnType compute_left_closed_directed(carrier_uint const two_fc, int exponent) noexcept
1838 {
1839 //////////////////////////////////////////////////////////////////////
1840 // Step 1: Schubfach multiplier calculation
1841 //////////////////////////////////////////////////////////////////////
1842
1843 ReturnType ret_value;
1844
1845 // Compute k and beta.
1846 const int minus_k = log::floor_log10_pow2(exponent) - kappa;
1847 const auto cache = CachePolicy::template get_cache<format>(-minus_k);
1848 const int beta = exponent + log::floor_log2_pow10(-minus_k);
1849
1850 // Compute xi and deltai.
1851 // 10^kappa <= deltai < 10^(kappa + 1)
1852 const auto deltai = compute_delta(cache, beta);
1853 //auto [xi, is_x_integer] = compute_mul(two_fc << beta, cache);
1854 const auto x_res = compute_mul(two_fc << beta, cache);
1855 auto xi = x_res.result;
1856 auto is_x_integer = x_res.is_integer;
1857
1858 // Deal with the unique exceptional cases
1859 // 29711844 * 2^-82
1860 // = 6.1442653300000000008655037797566933477355632930994033813476... * 10^-18
1861 // and 29711844 * 2^-81
1862 // = 1.2288530660000000001731007559513386695471126586198806762695... * 10^-17
1863 // for binary32.
1864 BOOST_IF_CONSTEXPR (std::is_same<format, ieee754_binary32>::value)
1865 {
1866 if (exponent <= -80)
1867 {
1868 is_x_integer = false;
1869 }
1870 }
1871
1872 if (!is_x_integer)
1873 {
1874 ++xi;
1875 }
1876
1877 //////////////////////////////////////////////////////////////////////
1878 // Step 2: Try larger divisor; remove trailing zeros if necessary
1879 //////////////////////////////////////////////////////////////////////
1880
1881 BOOST_CXX14_CONSTEXPR auto big_divisor = compute_power(std::uint32_t(10), kappa + 1);
1882
1883 // Using an upper bound on xi, we might be able to optimize the division
1884 // better than the compiler; we are computing xi / big_divisor here.
1885
1886 #ifdef BOOST_NO_CXX14_CONSTEXPR
1887 ret_value.significand = div::divide_by_pow10<carrier_uint>(kappa + 1, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1, xi);
1888 #else
1889 ret_value.significand = div::divide_by_pow10<kappa + 1, carrier_uint, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1>(xi);
1890 #endif
1891
1892 auto r = std::uint32_t(xi - big_divisor * ret_value.significand);
1893
1894 if (r != 0)
1895 {
1896 ++ret_value.significand;
1897 r = big_divisor - r;
1898 }
1899
1900 if (r > deltai)
1901 {
1902 goto small_divisor_case_label;
1903 }
1904 else if (r == deltai)
1905 {
1906 // Compare the fractional parts.
1907 // This branch is never taken for the exceptional cases
1908 // 2f_c = 29711482, e = -81
1909 // (6.1442649164096937243516663440523473127541365101933479309082... * 10^-18)
1910 // and 2f_c = 29711482, e = -80
1911 // (1.2288529832819387448703332688104694625508273020386695861816... * 10^-17).
1912 //const auto [zi_parity, is_z_integer] =
1913 // compute_mul_parity(two_fc + 2, cache, beta);
1914 const auto z_res = compute_mul_parity(two_fc + 2, cache, beta);
1915 if (z_res.parity || z_res.is_integer)
1916 {
1917 goto small_divisor_case_label;
1918 }
1919 }
1920
1921 // The ceiling is inside, so we are done.
1922 ret_value.exponent = minus_k + kappa + 1;
1923 TrailingZeroPolicy::template on_trailing_zeros<impl>(ret_value);
1924 return ret_value;
1925
1926
1927 //////////////////////////////////////////////////////////////////////
1928 // Step 3: Find the significand with the smaller divisor
1929 //////////////////////////////////////////////////////////////////////
1930
1931 small_divisor_case_label:
1932 ret_value.significand *= 10;
1933 ret_value.significand -= div::small_division_by_pow10<kappa>(r);
1934 ret_value.exponent = minus_k + kappa;
1935 TrailingZeroPolicy::template no_trailing_zeros<impl>(ret_value);
1936 return ret_value;
1937 }
1938
1939 template <typename ReturnType, typename TrailingZeroPolicy, typename CachePolicy>
1940 BOOST_JSON_SAFEBUFFERS static ReturnType compute_right_closed_directed(carrier_uint const two_fc, const int exponent, bool shorter_interval) noexcept
1941 {
1942 //////////////////////////////////////////////////////////////////////
1943 // Step 1: Schubfach multiplier calculation
1944 //////////////////////////////////////////////////////////////////////
1945
1946 ReturnType ret_value;
1947
1948 // Compute k and beta.
1949 const int minus_k = log::floor_log10_pow2(exponent - (shorter_interval ? 1 : 0)) - kappa;
1950 const auto cache = CachePolicy::template get_cache<format>(-minus_k);
1951 const int beta = exponent + log::floor_log2_pow10(-minus_k);
1952
1953 // Compute zi and deltai.
1954 // 10^kappa <= deltai < 10^(kappa + 1)
1955 const auto deltai = shorter_interval ? compute_delta(cache, beta - 1) : compute_delta(cache, beta);
1956 carrier_uint const zi = compute_mul(two_fc << beta, cache).result;
1957
1958
1959 //////////////////////////////////////////////////////////////////////
1960 // Step 2: Try larger divisor; remove trailing zeros if necessary
1961 //////////////////////////////////////////////////////////////////////
1962
1963 BOOST_CXX14_CONSTEXPR auto big_divisor = compute_power(std::uint32_t(10), kappa + 1);
1964
1965 // Using an upper bound on zi, we might be able to optimize the division better than
1966 // the compiler; we are computing zi / big_divisor here.
1967 #ifdef BOOST_NO_CXX14_CONSTEXPR
1968 ret_value.significand = div::divide_by_pow10<carrier_uint>(kappa + 1, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1, zi);
1969 #else
1970 ret_value.significand = div::divide_by_pow10<kappa + 1, carrier_uint, (carrier_uint(1) << (significand_bits + 1)) * big_divisor - 1>(zi);
1971 #endif
1972
1973 const auto r = std::uint32_t(zi - big_divisor * ret_value.significand);
1974
1975 if (r > deltai)
1976 {
1977 goto small_divisor_case_label;
1978 }
1979 else if (r == deltai)
1980 {
1981 // Compare the fractional parts.
1982 if (!compute_mul_parity(two_fc - (shorter_interval ? 1 : 2), cache, beta).parity)
1983 {
1984 goto small_divisor_case_label;
1985 }
1986 }
1987
1988 // The floor is inside, so we are done.
1989 ret_value.exponent = minus_k + kappa + 1;
1990 TrailingZeroPolicy::template on_trailing_zeros<impl>(ret_value);
1991 return ret_value;
1992
1993
1994 //////////////////////////////////////////////////////////////////////
1995 // Step 3: Find the significand with the small divisor
1996 //////////////////////////////////////////////////////////////////////
1997
1998 small_divisor_case_label:
1999 ret_value.significand *= 10;
2000 ret_value.significand += div::small_division_by_pow10<kappa>(r);
2001 ret_value.exponent = minus_k + kappa;
2002 TrailingZeroPolicy::template no_trailing_zeros<impl>(ret_value);
2003
2004 return ret_value;
2005 }
2006
2007 // Remove trailing zeros from n and return the number of zeros removed.
2008 BOOST_FORCEINLINE static int remove_trailing_zeros(carrier_uint& n) noexcept
2009 {
2010
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 305 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 138 times.
 443 if (n == 0)
2011 {
2012 ✗ return 0;
2013 }
2014
2015 BOOST_IF_CONSTEXPR (std::is_same<format, ieee754_binary32>::value)
2016 {
2017 constexpr auto mod_inv_5 = UINT32_C(0xcccccccd);
2018 constexpr auto mod_inv_25 = mod_inv_5 * mod_inv_5;
2019
2020 int s = 0;
2021 while (true)
2022 {
2023 auto q = boost::core::rotr(n * mod_inv_25, 2);
2024 if (q <= (std::numeric_limits<std::uint32_t>::max)() / 100)
2025 {
2026 n = q;
2027 s += 2;
2028 }
2029 else
2030 {
2031 break;
2032 }
2033 }
2034 auto q = boost::core::rotr(n * mod_inv_5, 1);
2035 if (q <= (std::numeric_limits<std::uint32_t>::max)() / 10)
2036 {
2037 n = q;
2038 s |= 1;
2039 }
2040
2041 return s;
2042 }
2043 else
2044 {
2045 // Static assertion does not work unless if constexpr is supported
2046 // static_assert(std::is_same<format, ieee754_binary64>::value, "Must be a double type");
2047
2048 // Divide by 10^8 and reduce to 32-bits if divisible.
2049 // Since ret_value.significand <= (2^53 * 1000 - 1) / 1000 < 10^16,
2050 // n is at most of 16 digits.
2051
2052 // This magic number is ceil(2^90 / 10^8).
2053 443 constexpr auto magic_number = UINT64_C(12379400392853802749);
2054 443 auto nm = umul128(n, magic_number);
2055
2056 // Is n is divisible by 10^8?
2057
3/4
✓ Branch 0 taken 302 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 138 times.
✗ Branch 3 not taken.
 443 if ((nm.high & ((std::uint64_t(1) << (90 - 64)) - 1)) == 0 &&
2058
2/4
✓ Branch 0 taken 302 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 138 times.
✗ Branch 3 not taken.
 440 nm.low < magic_number) {
2059 // If yes, work with the quotient.
2060 440 auto n32 = static_cast<std::uint32_t>(nm.high >> (90 - 64));
2061
2062 440 constexpr auto mod_inv_5 = UINT32_C(0xcccccccd);
2063 440 constexpr auto mod_inv_25 = mod_inv_5 * mod_inv_5;
2064
2065 440 int s = 8;
2066 1306 while (true)
2067 {
2068 1746 auto q = boost::core::rotr(n32 * mod_inv_25, 2);
2069
4/4
✓ Branch 1 taken 892 times.
✓ Branch 2 taken 302 times.
✓ Branch 4 taken 414 times.
✓ Branch 5 taken 138 times.
 1746 if (q <= (std::numeric_limits<std::uint32_t>::max)() / 100)
2070 {
2071 1306 n32 = q;
2072 1306 s += 2;
2073 }
2074 else
2075 {
2076 440 break;
2077 }
2078 }
2079
2080 440 auto q = boost::core::rotr(n32 * mod_inv_5, 1);
2081
4/4
✓ Branch 1 taken 263 times.
✓ Branch 2 taken 39 times.
✓ Branch 4 taken 137 times.
✓ Branch 5 taken 1 times.
 440 if (q <= (std::numeric_limits<std::uint32_t>::max)() / 10)
2082 {
2083 400 n32 = q;
2084 400 s |= 1;
2085 }
2086
2087 440 n = n32;
2088 440 return s;
2089 }
2090
2091 // If n is not divisible by 10^8, work with n itself.
2092 3 constexpr auto mod_inv_5 = UINT64_C(0xcccccccccccccccd);
2093 3 constexpr auto mod_inv_25 = mod_inv_5 * mod_inv_5;
2094
2095 3 int s = 0;
2096 ✗ while (true)
2097 {
2098 3 auto q = static_cast<carrier_uint>(boost::core::rotr(n * mod_inv_25, 2));
2099
1/4
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 3 if (q <= (std::numeric_limits<std::uint64_t>::max)() / 100)
2100 {
2101 ✗ n = q;
2102 ✗ s += 2;
2103 }
2104 else
2105 {
2106 3 break;
2107 }
2108 }
2109
2110 3 auto q = static_cast<carrier_uint>(boost::core::rotr(n * mod_inv_5, 1));
2111
1/4
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 3 if (q <= (std::numeric_limits<std::uint64_t>::max)() / 10)
2112 {
2113 ✗ n = q;
2114 ✗ s |= 1;
2115 }
2116
2117 3 return s;
2118 }
2119 }
2120
2121 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2122 static compute_mul_result compute_mul(carrier_uint u, cache_entry_type const& cache) noexcept
2123 {
2124 auto r = umul96_upper64(u, cache);
2125 return {carrier_uint(r >> 32), carrier_uint(r) == 0};
2126 }
2127
2128 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2129 306 static compute_mul_result compute_mul(carrier_uint u, cache_entry_type const& cache) noexcept
2130 {
2131 306 auto r = umul192_upper128(u, cache);
2132 306 return {r.high, r.low == 0};
2133 }
2134
2135 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2136 static constexpr std::uint32_t compute_delta(cache_entry_type const& cache,
2137 int beta) noexcept
2138 {
2139 return std::uint32_t(cache >> (cache_bits - 1 - beta));
2140 }
2141
2142 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2143 306 static constexpr std::uint32_t compute_delta(cache_entry_type const& cache,
2144 int beta) noexcept
2145 {
2146 306 return std::uint32_t(cache.high >> (carrier_bits - 1 - beta));
2147 }
2148
2149 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2150 static compute_mul_parity_result compute_mul_parity(carrier_uint two_f,
2151 cache_entry_type const& cache,
2152 int beta) noexcept
2153 {
2154 auto r = umul96_lower64(two_f, cache);
2155 return {((r >> (64 - beta)) & 1) != 0, std::uint32_t(r >> (32 - beta)) == 0};
2156 }
2157
2158 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2159 ✗ static compute_mul_parity_result compute_mul_parity(carrier_uint two_f,
2160 cache_entry_type const& cache,
2161 int beta) noexcept
2162 {
2163 ✗ auto r = umul192_lower128(two_f, cache);
2164 ✗ return {((r.high >> (64 - beta)) & 1) != 0, ((r.high << beta) | (r.low >> (64 - beta))) == 0};
2165 }
2166
2167 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2168 static constexpr carrier_uint compute_left_endpoint_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2169 {
2170 return carrier_uint((cache - (cache >> (significand_bits + 2))) >> (cache_bits - significand_bits - 1 - beta));
2171 }
2172
2173 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2174 138 static constexpr carrier_uint compute_left_endpoint_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2175 {
2176 138 return (cache.high - (cache.high >> (significand_bits + 2))) >> (carrier_bits - significand_bits - 1 - beta);
2177 }
2178
2179 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2180 static constexpr carrier_uint compute_right_endpoint_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2181 {
2182 return carrier_uint((cache + (cache >> (significand_bits + 1))) >> (cache_bits - significand_bits - 1 - beta));
2183 }
2184
2185 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2186 138 static constexpr carrier_uint compute_right_endpoint_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2187 {
2188 138 return (cache.high + (cache.high >> (significand_bits + 1))) >> (carrier_bits - significand_bits - 1 - beta);
2189 }
2190
2191 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary32>::value, bool>::type = true>
2192 static constexpr carrier_uint compute_round_up_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2193 {
2194 return (carrier_uint(cache >> (cache_bits - significand_bits - 2 - beta)) + 1) / 2;
2195 }
2196
2197 template <typename local_format = format, typename std::enable_if<std::is_same<local_format, ieee754_binary64>::value, bool>::type = true>
2198 ✗ static constexpr carrier_uint compute_round_up_for_shorter_interval_case(cache_entry_type const& cache, int beta) noexcept
2199 {
2200 ✗ return ((cache.high >> (carrier_bits - significand_bits - 2 - beta)) + 1) / 2;
2201 }
2202
2203 ✗ static constexpr bool is_right_endpoint_integer_shorter_interval(int exponent) noexcept
2204 {
2205 ✗ return exponent >= case_shorter_interval_right_endpoint_lower_threshold &&
2206 ✗ exponent <= case_shorter_interval_right_endpoint_upper_threshold;
2207 }
2208
2209 138 static constexpr bool is_left_endpoint_integer_shorter_interval(int exponent) noexcept
2210 {
2211
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 138 return exponent >= case_shorter_interval_left_endpoint_lower_threshold &&
2212 138 exponent <= case_shorter_interval_left_endpoint_upper_threshold;
2213 }
2214 };
2215
2216
2217 ////////////////////////////////////////////////////////////////////////////////////////
2218 // Policy holder.
2219 ////////////////////////////////////////////////////////////////////////////////////////
2220
2221 namespace policy_impl {
2222 template <typename... Policies>
2223 struct policy_holder : Policies... {};
2224 }
2225
2226 ////////////////////////////////////////////////////////////////////////////////////////
2227 // The interface function.
2228 ////////////////////////////////////////////////////////////////////////////////////////
2229
2230 #ifdef BOOST_MSVC
2231 # pragma warning(push)
2232 # pragma warning(disable: 4100) // Unreferenced formal parameter (interval_type_provider)
2233 # pragma warning(disable: 4189) // Local variable is initializaed but unused (tag)
2234 #endif
2235
2236 template <typename Float, typename FloatTraits = dragonbox_float_traits<Float>>
2237 BOOST_FORCEINLINE BOOST_JSON_SAFEBUFFERS auto
2238 to_decimal(dragonbox_signed_significand_bits<Float, FloatTraits> dragonbox_signed_significand_bits,
2239 unsigned int exponent_bits) noexcept
2240 -> decimal_fp<typename FloatTraits::carrier_uint, true, false>
2241 {
2242 // Build policy holder type.
2243 using namespace policy_impl;
2244
2245 using policy_holder = policy_holder<decimal_to_binary_rounding::nearest_to_even, binary_to_decimal_rounding::to_even, cache::full, sign::return_sign, trailing_zero::remove>;
2246
2247 using return_type = decimal_fp<typename FloatTraits::carrier_uint, policy_holder::return_has_sign, policy_holder::report_trailing_zeros>;
2248
2249 444 return_type ret = policy_holder::template delegate<return_type>(dragonbox_signed_significand_bits,
2250 444 [exponent_bits, dragonbox_signed_significand_bits](policy_impl::decimal_to_binary_rounding::nearest_to_even interval_type_provider) {
2251 using format = typename FloatTraits::format;
2252 444 constexpr auto tag = decltype(interval_type_provider)::tag;
2253
2254 444 auto two_fc = dragonbox_signed_significand_bits.remove_sign_bit_and_shift();
2255 444 auto exponent = int(exponent_bits);
2256
2257 BOOST_IF_CONSTEXPR (tag == decimal_to_binary_rounding::tag_t::to_nearest) { // NOLINT: if constexpr not always false
2258 // Is the input a normal number?
2259
2/2
✓ Branch 0 taken 433 times.
✓ Branch 1 taken 11 times.
 444 if (exponent != 0) {
2260 433 exponent += format::exponent_bias - format::significand_bits;
2261
2262 // Shorter interval case; proceed like Schubfach.
2263 // One might think this condition is wrong, since when exponent_bits == 1
2264 // and two_fc == 0, the interval is actually regular. However, it turns out
2265 // that this seemingly wrong condition is actually fine, because the end
2266 // result is anyway the same.
2267 //
2268 // [binary32]
2269 // (fc-1/2) * 2^e = 1.175'494'28... * 10^-38
2270 // (fc-1/4) * 2^e = 1.175'494'31... * 10^-38
2271 // fc * 2^e = 1.175'494'35... * 10^-38
2272 // (fc+1/2) * 2^e = 1.175'494'42... * 10^-38
2273 //
2274 // Hence, shorter_interval_case will return 1.175'494'4 * 10^-38.
2275 // 1.175'494'3 * 10^-38 is also a correct shortest representation that will
2276 // be rejected if we assume shorter interval, but 1.175'494'4 * 10^-38 is
2277 // closer to the true value so it doesn't matter.
2278 //
2279 // [binary64]
2280 // (fc-1/2) * 2^e = 2.225'073'858'507'201'13... * 10^-308
2281 // (fc-1/4) * 2^e = 2.225'073'858'507'201'25... * 10^-308
2282 // fc * 2^e = 2.225'073'858'507'201'38... * 10^-308
2283 // (fc+1/2) * 2^e = 2.225'073'858'507'201'63... * 10^-308
2284 //
2285 // Hence, shorter_interval_case will return 2.225'073'858'507'201'4 *
2286 // 10^-308. This is indeed of the shortest length, and it is the unique one
2287 // closest to the true value among valid representations of the same length.
2288 static_assert(std::is_same<format, ieee754_binary32>::value ||
2289 std::is_same<format, ieee754_binary64>::value, "Format must be IEEE754 binary 32 or 64");
2290
2291
2/2
✓ Branch 0 taken 138 times.
✓ Branch 1 taken 295 times.
 433 if (two_fc == 0) {
2292 138 return decltype(interval_type_provider)::template invoke_shorter_interval_case<return_type>(
2293 276 dragonbox_signed_significand_bits, [exponent]() {
2294 return detail::impl<Float, FloatTraits>::
2295 template compute_nearest_shorter<
2296 return_type,
2297 typename decltype(interval_type_provider)::
2298 shorter_interval_type,
2299 typename policy_holder::trailing_zero_policy,
2300 typename policy_holder::
2301 binary_to_decimal_rounding_policy,
2302 138 typename policy_holder::cache_policy>(
2303 138 exponent);
2304 138 });
2305 }
2306
2307 295 two_fc |= (decltype(two_fc)(1) << (format::significand_bits + 1));
2308 }
2309 // Is the input a subnormal number?
2310 else {
2311 11 exponent = format::min_exponent - format::significand_bits;
2312 }
2313
2314 306 return decltype(interval_type_provider)::template invoke_normal_interval_case<return_type>(
2315 612 dragonbox_signed_significand_bits, [two_fc, exponent](bool additional_args) {
2316 return detail::impl<Float, FloatTraits>::
2317 template compute_nearest_normal<
2318 return_type,
2319 typename decltype(interval_type_provider)::normal_interval_type,
2320 typename policy_holder::trailing_zero_policy,
2321 typename policy_holder::binary_to_decimal_rounding_policy,
2322 306 typename policy_holder::cache_policy>(two_fc, exponent, additional_args);
2323 306 });
2324 }
2325 else BOOST_IF_CONSTEXPR (tag == decimal_to_binary_rounding::tag_t::left_closed_directed) // NOLINT: if constexpr not always false
2326 {
2327 // Is the input a normal number?
2328 if (exponent != 0) {
2329 exponent += format::exponent_bias - format::significand_bits;
2330 two_fc |= (decltype(two_fc)(1) << (format::significand_bits + 1));
2331 }
2332 // Is the input a subnormal number?
2333 else {
2334 exponent = format::min_exponent - format::significand_bits;
2335 }
2336
2337 return detail::impl<Float>::template compute_left_closed_directed<
2338 return_type, typename policy_holder::trailing_zero_policy,
2339 typename policy_holder::cache_policy>(two_fc, exponent);
2340 }
2341 else
2342 {
2343 // Assertion does not work unless if constexpr is defined
2344 // static_assert(tag == decimal_to_binary_rounding::tag_t::right_closed_directed, "Tag should be right_closed_direction");
2345
2346 bool shorter_interval = false;
2347
2348 // Is the input a normal number?
2349 if (exponent != 0) {
2350 if (two_fc == 0 && exponent != 1) {
2351 shorter_interval = true;
2352 }
2353 exponent += format::exponent_bias - format::significand_bits;
2354 two_fc |= (decltype(two_fc)(1) << (format::significand_bits + 1));
2355 }
2356 // Is the input a subnormal number?
2357 else {
2358 exponent = format::min_exponent - format::significand_bits;
2359 }
2360
2361 return detail::impl<Float>::template compute_right_closed_directed<
2362 return_type, typename policy_holder::trailing_zero_policy,
2363 typename policy_holder::cache_policy>(two_fc, exponent, shorter_interval);
2364 }
2365 });
2366
2367 444 policy_holder::handle_sign(dragonbox_signed_significand_bits, ret);
2368 444 return ret;
2369 }
2370
2371 #ifdef BOOST_MSVC
2372 # pragma warning(pop)
2373 #endif
2374
2375 namespace to_chars_detail {
2376
2377 std::size_t dragon_box_print_chars(
2378 dragonbox_float_traits<double>::carrier_uint significand,
2379 int exponent,
2380 char* first,
2381 char* last) noexcept;
2382
2383 }
2384
2385 } // namespace detail
2386 } // namespace json
2387 } // namespace boost
2388
2389 #ifdef BOOST_MSVC
2390 # pragma warning(pop)
2391
2392 #endif
2393
2394 #endif // BOOST_JSON_DETAIL_DRAGONBOX_DRAGONBOX_HPP
2395