1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// Copyright (c) Microsoft Corporation.
10// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
11
12// Copyright 2018 Ulf Adams
13// Copyright (c) Microsoft Corporation. All rights reserved.
14
15// Boost Software License - Version 1.0 - August 17th, 2003
16
17// Permission is hereby granted, free of charge, to any person or organization
18// obtaining a copy of the software and accompanying documentation covered by
19// this license (the "Software") to use, reproduce, display, distribute,
20// execute, and transmit the Software, and to prepare derivative works of the
21// Software, and to permit third-parties to whom the Software is furnished to
22// do so, all subject to the following:
23
24// The copyright notices in the Software and this entire statement, including
25// the above license grant, this restriction and the following disclaimer,
26// must be included in all copies of the Software, in whole or in part, and
27// all derivative works of the Software, unless such copies or derivative
28// works are solely in the form of machine-executable object code generated by
29// a source language processor.
30
31// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
32// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
33// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
34// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
35// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
36// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
37// DEALINGS IN THE SOFTWARE.
38
39// Avoid formatting to keep the changes with the original code minimal.
40// clang-format off
41
42#include <__assert>
43#include <__config>
44#include <bit>
45#include <charconv>
46#include <cstddef>
47
48#include "include/ryu/common.h"
49#include "include/ryu/d2fixed.h"
50#include "include/ryu/d2s.h"
51#include "include/ryu/d2s_full_table.h"
52#include "include/ryu/d2s_intrinsics.h"
53#include "include/ryu/digit_table.h"
54#include "include/ryu/ryu.h"
55
56_LIBCPP_BEGIN_NAMESPACE_STD
57
58// We need a 64x128-bit multiplication and a subsequent 128-bit shift.
59// Multiplication:
60// The 64-bit factor is variable and passed in, the 128-bit factor comes
61// from a lookup table. We know that the 64-bit factor only has 55
62// significant bits (i.e., the 9 topmost bits are zeros). The 128-bit
63// factor only has 124 significant bits (i.e., the 4 topmost bits are
64// zeros).
65// Shift:
66// In principle, the multiplication result requires 55 + 124 = 179 bits to
67// represent. However, we then shift this value to the right by __j, which is
68// at least __j >= 115, so the result is guaranteed to fit into 179 - 115 = 64
69// bits. This means that we only need the topmost 64 significant bits of
70// the 64x128-bit multiplication.
71//
72// There are several ways to do this:
73// 1. Best case: the compiler exposes a 128-bit type.
74// We perform two 64x64-bit multiplications, add the higher 64 bits of the
75// lower result to the higher result, and shift by __j - 64 bits.
76//
77// We explicitly cast from 64-bit to 128-bit, so the compiler can tell
78// that these are only 64-bit inputs, and can map these to the best
79// possible sequence of assembly instructions.
80// x64 machines happen to have matching assembly instructions for
81// 64x64-bit multiplications and 128-bit shifts.
82//
83// 2. Second best case: the compiler exposes intrinsics for the x64 assembly
84// instructions mentioned in 1.
85//
86// 3. We only have 64x64 bit instructions that return the lower 64 bits of
87// the result, i.e., we have to use plain C.
88// Our inputs are less than the full width, so we have three options:
89// a. Ignore this fact and just implement the intrinsics manually.
90// b. Split both into 31-bit pieces, which guarantees no internal overflow,
91// but requires extra work upfront (unless we change the lookup table).
92// c. Split only the first factor into 31-bit pieces, which also guarantees
93// no internal overflow, but requires extra work since the intermediate
94// results are not perfectly aligned.
95#ifdef _LIBCPP_INTRINSIC128
96
97[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint64_t __mulShift(const uint64_t __m, const uint64_t* const __mul, const int32_t __j) {
98 // __m is maximum 55 bits
99 uint64_t __high1; // 128
100 const uint64_t __low1 = __ryu_umul128(a: __m, b: __mul[1], productHi: &__high1); // 64
101 uint64_t __high0; // 64
102 (void) __ryu_umul128(a: __m, b: __mul[0], productHi: &__high0); // 0
103 const uint64_t __sum = __high0 + __low1;
104 if (__sum < __high0) {
105 ++__high1; // overflow into __high1
106 }
107 return __ryu_shiftright128(lo: __sum, hi: __high1, dist: static_cast<uint32_t>(__j - 64));
108}
109
110[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint64_t __mulShiftAll(const uint64_t __m, const uint64_t* const __mul, const int32_t __j,
111 uint64_t* const __vp, uint64_t* const __vm, const uint32_t __mmShift) {
112 *__vp = __mulShift(m: 4 * __m + 2, __mul, __j);
113 *__vm = __mulShift(m: 4 * __m - 1 - __mmShift, __mul, __j);
114 return __mulShift(m: 4 * __m, __mul, __j);
115}
116
117#else // ^^^ intrinsics available ^^^ / vvv intrinsics unavailable vvv
118
119[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_ALWAYS_INLINE uint64_t __mulShiftAll(uint64_t __m, const uint64_t* const __mul, const int32_t __j,
120 uint64_t* const __vp, uint64_t* const __vm, const uint32_t __mmShift) { // TRANSITION, VSO-634761
121 __m <<= 1;
122 // __m is maximum 55 bits
123 uint64_t __tmp;
124 const uint64_t __lo = __ryu_umul128(__m, __mul[0], &__tmp);
125 uint64_t __hi;
126 const uint64_t __mid = __tmp + __ryu_umul128(__m, __mul[1], &__hi);
127 __hi += __mid < __tmp; // overflow into __hi
128
129 const uint64_t __lo2 = __lo + __mul[0];
130 const uint64_t __mid2 = __mid + __mul[1] + (__lo2 < __lo);
131 const uint64_t __hi2 = __hi + (__mid2 < __mid);
132 *__vp = __ryu_shiftright128(__mid2, __hi2, static_cast<uint32_t>(__j - 64 - 1));
133
134 if (__mmShift == 1) {
135 const uint64_t __lo3 = __lo - __mul[0];
136 const uint64_t __mid3 = __mid - __mul[1] - (__lo3 > __lo);
137 const uint64_t __hi3 = __hi - (__mid3 > __mid);
138 *__vm = __ryu_shiftright128(__mid3, __hi3, static_cast<uint32_t>(__j - 64 - 1));
139 } else {
140 const uint64_t __lo3 = __lo + __lo;
141 const uint64_t __mid3 = __mid + __mid + (__lo3 < __lo);
142 const uint64_t __hi3 = __hi + __hi + (__mid3 < __mid);
143 const uint64_t __lo4 = __lo3 - __mul[0];
144 const uint64_t __mid4 = __mid3 - __mul[1] - (__lo4 > __lo3);
145 const uint64_t __hi4 = __hi3 - (__mid4 > __mid3);
146 *__vm = __ryu_shiftright128(__mid4, __hi4, static_cast<uint32_t>(__j - 64));
147 }
148
149 return __ryu_shiftright128(__mid, __hi, static_cast<uint32_t>(__j - 64 - 1));
150}
151
152#endif // ^^^ intrinsics unavailable ^^^
153
154[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __decimalLength17(const uint64_t __v) {
155 // This is slightly faster than a loop.
156 // The average output length is 16.38 digits, so we check high-to-low.
157 // Function precondition: __v is not an 18, 19, or 20-digit number.
158 // (17 digits are sufficient for round-tripping.)
159 _LIBCPP_ASSERT_INTERNAL(__v < 100000000000000000u, "");
160 if (__v >= 10000000000000000u) { return 17; }
161 if (__v >= 1000000000000000u) { return 16; }
162 if (__v >= 100000000000000u) { return 15; }
163 if (__v >= 10000000000000u) { return 14; }
164 if (__v >= 1000000000000u) { return 13; }
165 if (__v >= 100000000000u) { return 12; }
166 if (__v >= 10000000000u) { return 11; }
167 if (__v >= 1000000000u) { return 10; }
168 if (__v >= 100000000u) { return 9; }
169 if (__v >= 10000000u) { return 8; }
170 if (__v >= 1000000u) { return 7; }
171 if (__v >= 100000u) { return 6; }
172 if (__v >= 10000u) { return 5; }
173 if (__v >= 1000u) { return 4; }
174 if (__v >= 100u) { return 3; }
175 if (__v >= 10u) { return 2; }
176 return 1;
177}
178
179// A floating decimal representing m * 10^e.
180struct __floating_decimal_64 {
181 uint64_t __mantissa;
182 int32_t __exponent;
183};
184
185[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline __floating_decimal_64 __d2d(const uint64_t __ieeeMantissa, const uint32_t __ieeeExponent) {
186 int32_t __e2;
187 uint64_t __m2;
188 if (__ieeeExponent == 0) {
189 // We subtract 2 so that the bounds computation has 2 additional bits.
190 __e2 = 1 - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS - 2;
191 __m2 = __ieeeMantissa;
192 } else {
193 __e2 = static_cast<int32_t>(__ieeeExponent) - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS - 2;
194 __m2 = (1ull << __DOUBLE_MANTISSA_BITS) | __ieeeMantissa;
195 }
196 const bool __even = (__m2 & 1) == 0;
197 const bool __acceptBounds = __even;
198
199 // Step 2: Determine the interval of valid decimal representations.
200 const uint64_t __mv = 4 * __m2;
201 // Implicit bool -> int conversion. True is 1, false is 0.
202 const uint32_t __mmShift = __ieeeMantissa != 0 || __ieeeExponent <= 1;
203 // We would compute __mp and __mm like this:
204 // uint64_t __mp = 4 * __m2 + 2;
205 // uint64_t __mm = __mv - 1 - __mmShift;
206
207 // Step 3: Convert to a decimal power base using 128-bit arithmetic.
208 uint64_t __vr, __vp, __vm;
209 int32_t __e10;
210 bool __vmIsTrailingZeros = false;
211 bool __vrIsTrailingZeros = false;
212 if (__e2 >= 0) {
213 // I tried special-casing __q == 0, but there was no effect on performance.
214 // This expression is slightly faster than max(0, __log10Pow2(__e2) - 1).
215 const uint32_t __q = __log10Pow2(e: __e2) - (__e2 > 3);
216 __e10 = static_cast<int32_t>(__q);
217 const int32_t __k = __DOUBLE_POW5_INV_BITCOUNT + __pow5bits(e: static_cast<int32_t>(__q)) - 1;
218 const int32_t __i = -__e2 + static_cast<int32_t>(__q) + __k;
219 __vr = __mulShiftAll(m: __m2, mul: __DOUBLE_POW5_INV_SPLIT[__q], j: __i, vp: &__vp, vm: &__vm, __mmShift);
220 if (__q <= 21) {
221 // This should use __q <= 22, but I think 21 is also safe. Smaller values
222 // may still be safe, but it's more difficult to reason about them.
223 // Only one of __mp, __mv, and __mm can be a multiple of 5, if any.
224 const uint32_t __mvMod5 = static_cast<uint32_t>(__mv) - 5 * static_cast<uint32_t>(__div5(x: __mv));
225 if (__mvMod5 == 0) {
226 __vrIsTrailingZeros = __multipleOfPowerOf5(value: __mv, p: __q);
227 } else if (__acceptBounds) {
228 // Same as min(__e2 + (~__mm & 1), __pow5Factor(__mm)) >= __q
229 // <=> __e2 + (~__mm & 1) >= __q && __pow5Factor(__mm) >= __q
230 // <=> true && __pow5Factor(__mm) >= __q, since __e2 >= __q.
231 __vmIsTrailingZeros = __multipleOfPowerOf5(value: __mv - 1 - __mmShift, p: __q);
232 } else {
233 // Same as min(__e2 + 1, __pow5Factor(__mp)) >= __q.
234 __vp -= __multipleOfPowerOf5(value: __mv + 2, p: __q);
235 }
236 }
237 } else {
238 // This expression is slightly faster than max(0, __log10Pow5(-__e2) - 1).
239 const uint32_t __q = __log10Pow5(e: -__e2) - (-__e2 > 1);
240 __e10 = static_cast<int32_t>(__q) + __e2;
241 const int32_t __i = -__e2 - static_cast<int32_t>(__q);
242 const int32_t __k = __pow5bits(e: __i) - __DOUBLE_POW5_BITCOUNT;
243 const int32_t __j = static_cast<int32_t>(__q) - __k;
244 __vr = __mulShiftAll(m: __m2, mul: __DOUBLE_POW5_SPLIT[__i], __j, vp: &__vp, vm: &__vm, __mmShift);
245 if (__q <= 1) {
246 // {__vr,__vp,__vm} is trailing zeros if {__mv,__mp,__mm} has at least __q trailing 0 bits.
247 // __mv = 4 * __m2, so it always has at least two trailing 0 bits.
248 __vrIsTrailingZeros = true;
249 if (__acceptBounds) {
250 // __mm = __mv - 1 - __mmShift, so it has 1 trailing 0 bit iff __mmShift == 1.
251 __vmIsTrailingZeros = __mmShift == 1;
252 } else {
253 // __mp = __mv + 2, so it always has at least one trailing 0 bit.
254 --__vp;
255 }
256 } else if (__q < 63) { // TRANSITION(ulfjack): Use a tighter bound here.
257 // We need to compute min(ntz(__mv), __pow5Factor(__mv) - __e2) >= __q - 1
258 // <=> ntz(__mv) >= __q - 1 && __pow5Factor(__mv) - __e2 >= __q - 1
259 // <=> ntz(__mv) >= __q - 1 (__e2 is negative and -__e2 >= __q)
260 // <=> (__mv & ((1 << (__q - 1)) - 1)) == 0
261 // We also need to make sure that the left shift does not overflow.
262 __vrIsTrailingZeros = __multipleOfPowerOf2(value: __mv, p: __q - 1);
263 }
264 }
265
266 // Step 4: Find the shortest decimal representation in the interval of valid representations.
267 int32_t __removed = 0;
268 uint8_t __lastRemovedDigit = 0;
269 uint64_t _Output;
270 // On average, we remove ~2 digits.
271 if (__vmIsTrailingZeros || __vrIsTrailingZeros) {
272 // General case, which happens rarely (~0.7%).
273 for (;;) {
274 const uint64_t __vpDiv10 = __div10(x: __vp);
275 const uint64_t __vmDiv10 = __div10(x: __vm);
276 if (__vpDiv10 <= __vmDiv10) {
277 break;
278 }
279 const uint32_t __vmMod10 = static_cast<uint32_t>(__vm) - 10 * static_cast<uint32_t>(__vmDiv10);
280 const uint64_t __vrDiv10 = __div10(x: __vr);
281 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);
282 __vmIsTrailingZeros &= __vmMod10 == 0;
283 __vrIsTrailingZeros &= __lastRemovedDigit == 0;
284 __lastRemovedDigit = static_cast<uint8_t>(__vrMod10);
285 __vr = __vrDiv10;
286 __vp = __vpDiv10;
287 __vm = __vmDiv10;
288 ++__removed;
289 }
290 if (__vmIsTrailingZeros) {
291 for (;;) {
292 const uint64_t __vmDiv10 = __div10(x: __vm);
293 const uint32_t __vmMod10 = static_cast<uint32_t>(__vm) - 10 * static_cast<uint32_t>(__vmDiv10);
294 if (__vmMod10 != 0) {
295 break;
296 }
297 const uint64_t __vpDiv10 = __div10(x: __vp);
298 const uint64_t __vrDiv10 = __div10(x: __vr);
299 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);
300 __vrIsTrailingZeros &= __lastRemovedDigit == 0;
301 __lastRemovedDigit = static_cast<uint8_t>(__vrMod10);
302 __vr = __vrDiv10;
303 __vp = __vpDiv10;
304 __vm = __vmDiv10;
305 ++__removed;
306 }
307 }
308 if (__vrIsTrailingZeros && __lastRemovedDigit == 5 && __vr % 2 == 0) {
309 // Round even if the exact number is .....50..0.
310 __lastRemovedDigit = 4;
311 }
312 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.
313 _Output = __vr + ((__vr == __vm && (!__acceptBounds || !__vmIsTrailingZeros)) || __lastRemovedDigit >= 5);
314 } else {
315 // Specialized for the common case (~99.3%). Percentages below are relative to this.
316 bool __roundUp = false;
317 const uint64_t __vpDiv100 = __div100(x: __vp);
318 const uint64_t __vmDiv100 = __div100(x: __vm);
319 if (__vpDiv100 > __vmDiv100) { // Optimization: remove two digits at a time (~86.2%).
320 const uint64_t __vrDiv100 = __div100(x: __vr);
321 const uint32_t __vrMod100 = static_cast<uint32_t>(__vr) - 100 * static_cast<uint32_t>(__vrDiv100);
322 __roundUp = __vrMod100 >= 50;
323 __vr = __vrDiv100;
324 __vp = __vpDiv100;
325 __vm = __vmDiv100;
326 __removed += 2;
327 }
328 // Loop iterations below (approximately), without optimization above:
329 // 0: 0.03%, 1: 13.8%, 2: 70.6%, 3: 14.0%, 4: 1.40%, 5: 0.14%, 6+: 0.02%
330 // Loop iterations below (approximately), with optimization above:
331 // 0: 70.6%, 1: 27.8%, 2: 1.40%, 3: 0.14%, 4+: 0.02%
332 for (;;) {
333 const uint64_t __vpDiv10 = __div10(x: __vp);
334 const uint64_t __vmDiv10 = __div10(x: __vm);
335 if (__vpDiv10 <= __vmDiv10) {
336 break;
337 }
338 const uint64_t __vrDiv10 = __div10(x: __vr);
339 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);
340 __roundUp = __vrMod10 >= 5;
341 __vr = __vrDiv10;
342 __vp = __vpDiv10;
343 __vm = __vmDiv10;
344 ++__removed;
345 }
346 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.
347 _Output = __vr + (__vr == __vm || __roundUp);
348 }
349 const int32_t __exp = __e10 + __removed;
350
351 __floating_decimal_64 __fd;
352 __fd.__exponent = __exp;
353 __fd.__mantissa = _Output;
354 return __fd;
355}
356
357[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result __to_chars(char* const _First, char* const _Last, const __floating_decimal_64 __v,
358 chars_format _Fmt, const double __f) {
359 // Step 5: Print the decimal representation.
360 uint64_t _Output = __v.__mantissa;
361 int32_t _Ryu_exponent = __v.__exponent;
362 const uint32_t __olength = __decimalLength17(v: _Output);
363 int32_t _Scientific_exponent = _Ryu_exponent + static_cast<int32_t>(__olength) - 1;
364
365 if (_Fmt == chars_format{}) {
366 int32_t _Lower;
367 int32_t _Upper;
368
369 if (__olength == 1) {
370 // Value | Fixed | Scientific
371 // 1e-3 | "0.001" | "1e-03"
372 // 1e4 | "10000" | "1e+04"
373 _Lower = -3;
374 _Upper = 4;
375 } else {
376 // Value | Fixed | Scientific
377 // 1234e-7 | "0.0001234" | "1.234e-04"
378 // 1234e5 | "123400000" | "1.234e+08"
379 _Lower = -static_cast<int32_t>(__olength + 3);
380 _Upper = 5;
381 }
382
383 if (_Lower <= _Ryu_exponent && _Ryu_exponent <= _Upper) {
384 _Fmt = chars_format::fixed;
385 } else {
386 _Fmt = chars_format::scientific;
387 }
388 } else if (_Fmt == chars_format::general) {
389 // C11 7.21.6.1 "The fprintf function"/8:
390 // "Let P equal [...] 6 if the precision is omitted [...].
391 // Then, if a conversion with style E would have an exponent of X:
392 // - if P > X >= -4, the conversion is with style f [...].
393 // - otherwise, the conversion is with style e [...]."
394 if (-4 <= _Scientific_exponent && _Scientific_exponent < 6) {
395 _Fmt = chars_format::fixed;
396 } else {
397 _Fmt = chars_format::scientific;
398 }
399 }
400
401 if (_Fmt == chars_format::fixed) {
402 // Example: _Output == 1729, __olength == 4
403
404 // _Ryu_exponent | Printed | _Whole_digits | _Total_fixed_length | Notes
405 // --------------|----------|---------------|----------------------|---------------------------------------
406 // 2 | 172900 | 6 | _Whole_digits | Ryu can't be used for printing
407 // 1 | 17290 | 5 | (sometimes adjusted) | when the trimmed digits are nonzero.
408 // --------------|----------|---------------|----------------------|---------------------------------------
409 // 0 | 1729 | 4 | _Whole_digits | Unified length cases.
410 // --------------|----------|---------------|----------------------|---------------------------------------
411 // -1 | 172.9 | 3 | __olength + 1 | This case can't happen for
412 // -2 | 17.29 | 2 | | __olength == 1, but no additional
413 // -3 | 1.729 | 1 | | code is needed to avoid it.
414 // --------------|----------|---------------|----------------------|---------------------------------------
415 // -4 | 0.1729 | 0 | 2 - _Ryu_exponent | C11 7.21.6.1 "The fprintf function"/8:
416 // -5 | 0.01729 | -1 | | "If a decimal-point character appears,
417 // -6 | 0.001729 | -2 | | at least one digit appears before it."
418
419 const int32_t _Whole_digits = static_cast<int32_t>(__olength) + _Ryu_exponent;
420
421 uint32_t _Total_fixed_length;
422 if (_Ryu_exponent >= 0) { // cases "172900" and "1729"
423 _Total_fixed_length = static_cast<uint32_t>(_Whole_digits);
424 if (_Output == 1) {
425 // Rounding can affect the number of digits.
426 // For example, 1e23 is exactly "99999999999999991611392" which is 23 digits instead of 24.
427 // We can use a lookup table to detect this and adjust the total length.
428 static constexpr uint8_t _Adjustment[309] = {
429 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,1,1,0,0,0,0,0,
430 1,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,1,0,1,1,0,0,0,0,1,1,1,
431 1,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,1,
432 1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,0,0,1,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,1,
433 0,1,0,1,0,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,0,1,
434 1,1,0,1,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0,0,1,1,0,
435 0,1,0,1,1,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,1,0 };
436 _Total_fixed_length -= _Adjustment[_Ryu_exponent];
437 // _Whole_digits doesn't need to be adjusted because these cases won't refer to it later.
438 }
439 } else if (_Whole_digits > 0) { // case "17.29"
440 _Total_fixed_length = __olength + 1;
441 } else { // case "0.001729"
442 _Total_fixed_length = static_cast<uint32_t>(2 - _Ryu_exponent);
443 }
444
445 if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) {
446 return { .ptr: _Last, .ec: errc::value_too_large };
447 }
448
449 char* _Mid;
450 if (_Ryu_exponent > 0) { // case "172900"
451 bool _Can_use_ryu;
452
453 if (_Ryu_exponent > 22) { // 10^22 is the largest power of 10 that's exactly representable as a double.
454 _Can_use_ryu = false;
455 } else {
456 // Ryu generated X: __v.__mantissa * 10^_Ryu_exponent
457 // __v.__mantissa == 2^_Trailing_zero_bits * (__v.__mantissa >> _Trailing_zero_bits)
458 // 10^_Ryu_exponent == 2^_Ryu_exponent * 5^_Ryu_exponent
459
460 // _Trailing_zero_bits is [0, 56] (aside: because 2^56 is the largest power of 2
461 // with 17 decimal digits, which is double's round-trip limit.)
462 // _Ryu_exponent is [1, 22].
463 // Normalization adds [2, 52] (aside: at least 2 because the pre-normalized mantissa is at least 5).
464 // This adds up to [3, 130], which is well below double's maximum binary exponent 1023.
465
466 // Therefore, we just need to consider (__v.__mantissa >> _Trailing_zero_bits) * 5^_Ryu_exponent.
467
468 // If that product would exceed 53 bits, then X can't be exactly represented as a double.
469 // (That's not a problem for round-tripping, because X is close enough to the original double,
470 // but X isn't mathematically equal to the original double.) This requires a high-precision fallback.
471
472 // If the product is 53 bits or smaller, then X can be exactly represented as a double (and we don't
473 // need to re-synthesize it; the original double must have been X, because Ryu wouldn't produce the
474 // same output for two different doubles X and Y). This allows Ryu's output to be used (zero-filled).
475
476 // (2^53 - 1) / 5^0 (for indexing), (2^53 - 1) / 5^1, ..., (2^53 - 1) / 5^22
477 static constexpr uint64_t _Max_shifted_mantissa[23] = {
478 9007199254740991u, 1801439850948198u, 360287970189639u, 72057594037927u, 14411518807585u,
479 2882303761517u, 576460752303u, 115292150460u, 23058430092u, 4611686018u, 922337203u, 184467440u,
480 36893488u, 7378697u, 1475739u, 295147u, 59029u, 11805u, 2361u, 472u, 94u, 18u, 3u };
481
482 unsigned long _Trailing_zero_bits = std::countr_zero(t: __v.__mantissa);
483 const uint64_t _Shifted_mantissa = __v.__mantissa >> _Trailing_zero_bits;
484 _Can_use_ryu = _Shifted_mantissa <= _Max_shifted_mantissa[_Ryu_exponent];
485 }
486
487 if (!_Can_use_ryu) {
488 // Print the integer exactly.
489 // Performance note: This will redundantly perform bounds checking.
490 // Performance note: This will redundantly decompose the IEEE representation.
491 return __d2fixed_buffered_n(_First, _Last, d: __f, precision: 0);
492 }
493
494 // _Can_use_ryu
495 // Print the decimal digits, left-aligned within [_First, _First + _Total_fixed_length).
496 _Mid = _First + __olength;
497 } else { // cases "1729", "17.29", and "0.001729"
498 // Print the decimal digits, right-aligned within [_First, _First + _Total_fixed_length).
499 _Mid = _First + _Total_fixed_length;
500 }
501
502 // We prefer 32-bit operations, even on 64-bit platforms.
503 // We have at most 17 digits, and uint32_t can store 9 digits.
504 // If _Output doesn't fit into uint32_t, we cut off 8 digits,
505 // so the rest will fit into uint32_t.
506 if ((_Output >> 32) != 0) {
507 // Expensive 64-bit division.
508 const uint64_t __q = __div1e8(x: _Output);
509 uint32_t __output2 = static_cast<uint32_t>(_Output - 100000000 * __q);
510 _Output = __q;
511
512 const uint32_t __c = __output2 % 10000;
513 __output2 /= 10000;
514 const uint32_t __d = __output2 % 10000;
515 const uint32_t __c0 = (__c % 100) << 1;
516 const uint32_t __c1 = (__c / 100) << 1;
517 const uint32_t __d0 = (__d % 100) << 1;
518 const uint32_t __d1 = (__d / 100) << 1;
519
520 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c0, n: 2);
521 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c1, n: 2);
522 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __d0, n: 2);
523 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __d1, n: 2);
524 }
525 uint32_t __output2 = static_cast<uint32_t>(_Output);
526 while (__output2 >= 10000) {
527#ifdef __clang__ // TRANSITION, LLVM-38217
528 const uint32_t __c = __output2 - 10000 * (__output2 / 10000);
529#else
530 const uint32_t __c = __output2 % 10000;
531#endif
532 __output2 /= 10000;
533 const uint32_t __c0 = (__c % 100) << 1;
534 const uint32_t __c1 = (__c / 100) << 1;
535 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c0, n: 2);
536 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c1, n: 2);
537 }
538 if (__output2 >= 100) {
539 const uint32_t __c = (__output2 % 100) << 1;
540 __output2 /= 100;
541 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c, n: 2);
542 }
543 if (__output2 >= 10) {
544 const uint32_t __c = __output2 << 1;
545 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c, n: 2);
546 } else {
547 *--_Mid = static_cast<char>('0' + __output2);
548 }
549
550 if (_Ryu_exponent > 0) { // case "172900" with _Can_use_ryu
551 // Performance note: it might be more efficient to do this immediately after setting _Mid.
552 std::memset(s: _First + __olength, c: '0', n: static_cast<size_t>(_Ryu_exponent));
553 } else if (_Ryu_exponent == 0) { // case "1729"
554 // Done!
555 } else if (_Whole_digits > 0) { // case "17.29"
556 // Performance note: moving digits might not be optimal.
557 std::memmove(dest: _First, src: _First + 1, n: static_cast<size_t>(_Whole_digits));
558 _First[_Whole_digits] = '.';
559 } else { // case "0.001729"
560 // Performance note: a larger memset() followed by overwriting '.' might be more efficient.
561 _First[0] = '0';
562 _First[1] = '.';
563 std::memset(s: _First + 2, c: '0', n: static_cast<size_t>(-_Whole_digits));
564 }
565
566 return { .ptr: _First + _Total_fixed_length, .ec: errc{} };
567 }
568
569 const uint32_t _Total_scientific_length = __olength + (__olength > 1) // digits + possible decimal point
570 + (-100 < _Scientific_exponent && _Scientific_exponent < 100 ? 4 : 5); // + scientific exponent
571 if (_Last - _First < static_cast<ptrdiff_t>(_Total_scientific_length)) {
572 return { .ptr: _Last, .ec: errc::value_too_large };
573 }
574 char* const __result = _First;
575
576 // Print the decimal digits.
577 uint32_t __i = 0;
578 // We prefer 32-bit operations, even on 64-bit platforms.
579 // We have at most 17 digits, and uint32_t can store 9 digits.
580 // If _Output doesn't fit into uint32_t, we cut off 8 digits,
581 // so the rest will fit into uint32_t.
582 if ((_Output >> 32) != 0) {
583 // Expensive 64-bit division.
584 const uint64_t __q = __div1e8(x: _Output);
585 uint32_t __output2 = static_cast<uint32_t>(_Output) - 100000000 * static_cast<uint32_t>(__q);
586 _Output = __q;
587
588 const uint32_t __c = __output2 % 10000;
589 __output2 /= 10000;
590 const uint32_t __d = __output2 % 10000;
591 const uint32_t __c0 = (__c % 100) << 1;
592 const uint32_t __c1 = (__c / 100) << 1;
593 const uint32_t __d0 = (__d % 100) << 1;
594 const uint32_t __d1 = (__d / 100) << 1;
595 std::memcpy(dest: __result + __olength - __i - 1, src: __DIGIT_TABLE + __c0, n: 2);
596 std::memcpy(dest: __result + __olength - __i - 3, src: __DIGIT_TABLE + __c1, n: 2);
597 std::memcpy(dest: __result + __olength - __i - 5, src: __DIGIT_TABLE + __d0, n: 2);
598 std::memcpy(dest: __result + __olength - __i - 7, src: __DIGIT_TABLE + __d1, n: 2);
599 __i += 8;
600 }
601 uint32_t __output2 = static_cast<uint32_t>(_Output);
602 while (__output2 >= 10000) {
603#ifdef __clang__ // TRANSITION, LLVM-38217
604 const uint32_t __c = __output2 - 10000 * (__output2 / 10000);
605#else
606 const uint32_t __c = __output2 % 10000;
607#endif
608 __output2 /= 10000;
609 const uint32_t __c0 = (__c % 100) << 1;
610 const uint32_t __c1 = (__c / 100) << 1;
611 std::memcpy(dest: __result + __olength - __i - 1, src: __DIGIT_TABLE + __c0, n: 2);
612 std::memcpy(dest: __result + __olength - __i - 3, src: __DIGIT_TABLE + __c1, n: 2);
613 __i += 4;
614 }
615 if (__output2 >= 100) {
616 const uint32_t __c = (__output2 % 100) << 1;
617 __output2 /= 100;
618 std::memcpy(dest: __result + __olength - __i - 1, src: __DIGIT_TABLE + __c, n: 2);
619 __i += 2;
620 }
621 if (__output2 >= 10) {
622 const uint32_t __c = __output2 << 1;
623 // We can't use memcpy here: the decimal dot goes between these two digits.
624 __result[2] = __DIGIT_TABLE[__c + 1];
625 __result[0] = __DIGIT_TABLE[__c];
626 } else {
627 __result[0] = static_cast<char>('0' + __output2);
628 }
629
630 // Print decimal point if needed.
631 uint32_t __index;
632 if (__olength > 1) {
633 __result[1] = '.';
634 __index = __olength + 1;
635 } else {
636 __index = 1;
637 }
638
639 // Print the exponent.
640 __result[__index++] = 'e';
641 if (_Scientific_exponent < 0) {
642 __result[__index++] = '-';
643 _Scientific_exponent = -_Scientific_exponent;
644 } else {
645 __result[__index++] = '+';
646 }
647
648 if (_Scientific_exponent >= 100) {
649 const int32_t __c = _Scientific_exponent % 10;
650 std::memcpy(dest: __result + __index, src: __DIGIT_TABLE + 2 * (_Scientific_exponent / 10), n: 2);
651 __result[__index + 2] = static_cast<char>('0' + __c);
652 __index += 3;
653 } else {
654 std::memcpy(dest: __result + __index, src: __DIGIT_TABLE + 2 * _Scientific_exponent, n: 2);
655 __index += 2;
656 }
657
658 return { .ptr: _First + _Total_scientific_length, .ec: errc{} };
659}
660
661[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __d2d_small_int(const uint64_t __ieeeMantissa, const uint32_t __ieeeExponent,
662 __floating_decimal_64* const __v) {
663 const uint64_t __m2 = (1ull << __DOUBLE_MANTISSA_BITS) | __ieeeMantissa;
664 const int32_t __e2 = static_cast<int32_t>(__ieeeExponent) - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS;
665
666 if (__e2 > 0) {
667 // f = __m2 * 2^__e2 >= 2^53 is an integer.
668 // Ignore this case for now.
669 return false;
670 }
671
672 if (__e2 < -52) {
673 // f < 1.
674 return false;
675 }
676
677 // Since 2^52 <= __m2 < 2^53 and 0 <= -__e2 <= 52: 1 <= f = __m2 / 2^-__e2 < 2^53.
678 // Test if the lower -__e2 bits of the significand are 0, i.e. whether the fraction is 0.
679 const uint64_t __mask = (1ull << -__e2) - 1;
680 const uint64_t __fraction = __m2 & __mask;
681 if (__fraction != 0) {
682 return false;
683 }
684
685 // f is an integer in the range [1, 2^53).
686 // Note: __mantissa might contain trailing (decimal) 0's.
687 // Note: since 2^53 < 10^16, there is no need to adjust __decimalLength17().
688 __v->__mantissa = __m2 >> -__e2;
689 __v->__exponent = 0;
690 return true;
691}
692
693[[nodiscard]] to_chars_result __d2s_buffered_n(char* const _First, char* const _Last, const double __f,
694 const chars_format _Fmt) {
695
696 // Step 1: Decode the floating-point number, and unify normalized and subnormal cases.
697 const uint64_t __bits = __double_to_bits(d: __f);
698
699 // Case distinction; exit early for the easy cases.
700 if (__bits == 0) {
701 if (_Fmt == chars_format::scientific) {
702 if (_Last - _First < 5) {
703 return { .ptr: _Last, .ec: errc::value_too_large };
704 }
705
706 std::memcpy(dest: _First, src: "0e+00", n: 5);
707
708 return { .ptr: _First + 5, .ec: errc{} };
709 }
710
711 // Print "0" for chars_format::fixed, chars_format::general, and chars_format{}.
712 if (_First == _Last) {
713 return { .ptr: _Last, .ec: errc::value_too_large };
714 }
715
716 *_First = '0';
717
718 return { .ptr: _First + 1, .ec: errc{} };
719 }
720
721 // Decode __bits into mantissa and exponent.
722 const uint64_t __ieeeMantissa = __bits & ((1ull << __DOUBLE_MANTISSA_BITS) - 1);
723 const uint32_t __ieeeExponent = static_cast<uint32_t>(__bits >> __DOUBLE_MANTISSA_BITS);
724
725 if (_Fmt == chars_format::fixed) {
726 // const uint64_t _Mantissa2 = __ieeeMantissa | (1ull << __DOUBLE_MANTISSA_BITS); // restore implicit bit
727 const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent)
728 - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS; // bias and normalization
729
730 // Normal values are equal to _Mantissa2 * 2^_Exponent2.
731 // (Subnormals are different, but they'll be rejected by the _Exponent2 test here, so they can be ignored.)
732
733 // For nonzero integers, _Exponent2 >= -52. (The minimum value occurs when _Mantissa2 * 2^_Exponent2 is 1.
734 // In that case, _Mantissa2 is the implicit 1 bit followed by 52 zeros, so _Exponent2 is -52 to shift away
735 // the zeros.) The dense range of exactly representable integers has negative or zero exponents
736 // (as positive exponents make the range non-dense). For that dense range, Ryu will always be used:
737 // every digit is necessary to uniquely identify the value, so Ryu must print them all.
738
739 // Positive exponents are the non-dense range of exactly representable integers. This contains all of the values
740 // for which Ryu can't be used (and a few Ryu-friendly values). We can save time by detecting positive
741 // exponents here and skipping Ryu. Calling __d2fixed_buffered_n() with precision 0 is valid for all integers
742 // (so it's okay if we call it with a Ryu-friendly value).
743 if (_Exponent2 > 0) {
744 return __d2fixed_buffered_n(_First, _Last, d: __f, precision: 0);
745 }
746 }
747
748 __floating_decimal_64 __v;
749 const bool __isSmallInt = __d2d_small_int(__ieeeMantissa, __ieeeExponent, v: &__v);
750 if (__isSmallInt) {
751 // For small integers in the range [1, 2^53), __v.__mantissa might contain trailing (decimal) zeros.
752 // For scientific notation we need to move these zeros into the exponent.
753 // (This is not needed for fixed-point notation, so it might be beneficial to trim
754 // trailing zeros in __to_chars only if needed - once fixed-point notation output is implemented.)
755 for (;;) {
756 const uint64_t __q = __div10(x: __v.__mantissa);
757 const uint32_t __r = static_cast<uint32_t>(__v.__mantissa) - 10 * static_cast<uint32_t>(__q);
758 if (__r != 0) {
759 break;
760 }
761 __v.__mantissa = __q;
762 ++__v.__exponent;
763 }
764 } else {
765 __v = __d2d(__ieeeMantissa, __ieeeExponent);
766 }
767
768 return __to_chars(_First, _Last, __v, _Fmt, __f);
769}
770
771_LIBCPP_END_NAMESPACE_STD
772
773// clang-format on
774