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 <cstdint>
47#include <cstddef>
48
49#include "include/ryu/common.h"
50#include "include/ryu/d2fixed.h"
51#include "include/ryu/d2s_intrinsics.h"
52#include "include/ryu/digit_table.h"
53#include "include/ryu/f2s.h"
54#include "include/ryu/ryu.h"
55
56_LIBCPP_BEGIN_NAMESPACE_STD
57
58inline constexpr int __FLOAT_MANTISSA_BITS = 23;
59inline constexpr int __FLOAT_EXPONENT_BITS = 8;
60inline constexpr int __FLOAT_BIAS = 127;
61
62inline constexpr int __FLOAT_POW5_INV_BITCOUNT = 59;
63inline constexpr uint64_t __FLOAT_POW5_INV_SPLIT[31] = {
64 576460752303423489u, 461168601842738791u, 368934881474191033u, 295147905179352826u,
65 472236648286964522u, 377789318629571618u, 302231454903657294u, 483570327845851670u,
66 386856262276681336u, 309485009821345069u, 495176015714152110u, 396140812571321688u,
67 316912650057057351u, 507060240091291761u, 405648192073033409u, 324518553658426727u,
68 519229685853482763u, 415383748682786211u, 332306998946228969u, 531691198313966350u,
69 425352958651173080u, 340282366920938464u, 544451787073501542u, 435561429658801234u,
70 348449143727040987u, 557518629963265579u, 446014903970612463u, 356811923176489971u,
71 570899077082383953u, 456719261665907162u, 365375409332725730u
72};
73inline constexpr int __FLOAT_POW5_BITCOUNT = 61;
74inline constexpr uint64_t __FLOAT_POW5_SPLIT[47] = {
75 1152921504606846976u, 1441151880758558720u, 1801439850948198400u, 2251799813685248000u,
76 1407374883553280000u, 1759218604441600000u, 2199023255552000000u, 1374389534720000000u,
77 1717986918400000000u, 2147483648000000000u, 1342177280000000000u, 1677721600000000000u,
78 2097152000000000000u, 1310720000000000000u, 1638400000000000000u, 2048000000000000000u,
79 1280000000000000000u, 1600000000000000000u, 2000000000000000000u, 1250000000000000000u,
80 1562500000000000000u, 1953125000000000000u, 1220703125000000000u, 1525878906250000000u,
81 1907348632812500000u, 1192092895507812500u, 1490116119384765625u, 1862645149230957031u,
82 1164153218269348144u, 1455191522836685180u, 1818989403545856475u, 2273736754432320594u,
83 1421085471520200371u, 1776356839400250464u, 2220446049250313080u, 1387778780781445675u,
84 1734723475976807094u, 2168404344971008868u, 1355252715606880542u, 1694065894508600678u,
85 2117582368135750847u, 1323488980084844279u, 1654361225106055349u, 2067951531382569187u,
86 1292469707114105741u, 1615587133892632177u, 2019483917365790221u
87};
88
89[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __pow5Factor(uint32_t __value) {
90 uint32_t __count = 0;
91 for (;;) {
92 _LIBCPP_ASSERT_INTERNAL(__value != 0, "");
93 const uint32_t __q = __value / 5;
94 const uint32_t __r = __value % 5;
95 if (__r != 0) {
96 break;
97 }
98 __value = __q;
99 ++__count;
100 }
101 return __count;
102}
103
104// Returns true if __value is divisible by 5^__p.
105[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __multipleOfPowerOf5(const uint32_t __value, const uint32_t __p) {
106 return __pow5Factor(__value) >= __p;
107}
108
109// Returns true if __value is divisible by 2^__p.
110[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __multipleOfPowerOf2(const uint32_t __value, const uint32_t __p) {
111 _LIBCPP_ASSERT_INTERNAL(__value != 0, "");
112 _LIBCPP_ASSERT_INTERNAL(__p < 32, "");
113 // __builtin_ctz doesn't appear to be faster here.
114 return (__value & ((1u << __p) - 1)) == 0;
115}
116
117[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulShift(const uint32_t __m, const uint64_t __factor, const int32_t __shift) {
118 _LIBCPP_ASSERT_INTERNAL(__shift > 32, "");
119
120 // The casts here help MSVC to avoid calls to the __allmul library
121 // function.
122 const uint32_t __factorLo = static_cast<uint32_t>(__factor);
123 const uint32_t __factorHi = static_cast<uint32_t>(__factor >> 32);
124 const uint64_t __bits0 = static_cast<uint64_t>(__m) * __factorLo;
125 const uint64_t __bits1 = static_cast<uint64_t>(__m) * __factorHi;
126
127#ifndef _LIBCPP_64_BIT
128 // On 32-bit platforms we can avoid a 64-bit shift-right since we only
129 // need the upper 32 bits of the result and the shift value is > 32.
130 const uint32_t __bits0Hi = static_cast<uint32_t>(__bits0 >> 32);
131 uint32_t __bits1Lo = static_cast<uint32_t>(__bits1);
132 uint32_t __bits1Hi = static_cast<uint32_t>(__bits1 >> 32);
133 __bits1Lo += __bits0Hi;
134 __bits1Hi += (__bits1Lo < __bits0Hi);
135 const int32_t __s = __shift - 32;
136 return (__bits1Hi << (32 - __s)) | (__bits1Lo >> __s);
137#else // ^^^ 32-bit ^^^ / vvv 64-bit vvv
138 const uint64_t __sum = (__bits0 >> 32) + __bits1;
139 const uint64_t __shiftedSum = __sum >> (__shift - 32);
140 _LIBCPP_ASSERT_INTERNAL(__shiftedSum <= UINT32_MAX, "");
141 return static_cast<uint32_t>(__shiftedSum);
142#endif // ^^^ 64-bit ^^^
143}
144
145[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulPow5InvDivPow2(const uint32_t __m, const uint32_t __q, const int32_t __j) {
146 return __mulShift(__m, factor: __FLOAT_POW5_INV_SPLIT[__q], shift: __j);
147}
148
149[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulPow5divPow2(const uint32_t __m, const uint32_t __i, const int32_t __j) {
150 return __mulShift(__m, factor: __FLOAT_POW5_SPLIT[__i], shift: __j);
151}
152
153// A floating decimal representing m * 10^e.
154struct __floating_decimal_32 {
155 uint32_t __mantissa;
156 int32_t __exponent;
157};
158
159[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline __floating_decimal_32 __f2d(const uint32_t __ieeeMantissa, const uint32_t __ieeeExponent) {
160 int32_t __e2;
161 uint32_t __m2;
162 if (__ieeeExponent == 0) {
163 // We subtract 2 so that the bounds computation has 2 additional bits.
164 __e2 = 1 - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS - 2;
165 __m2 = __ieeeMantissa;
166 } else {
167 __e2 = static_cast<int32_t>(__ieeeExponent) - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS - 2;
168 __m2 = (1u << __FLOAT_MANTISSA_BITS) | __ieeeMantissa;
169 }
170 const bool __even = (__m2 & 1) == 0;
171 const bool __acceptBounds = __even;
172
173 // Step 2: Determine the interval of valid decimal representations.
174 const uint32_t __mv = 4 * __m2;
175 const uint32_t __mp = 4 * __m2 + 2;
176 // Implicit bool -> int conversion. True is 1, false is 0.
177 const uint32_t __mmShift = __ieeeMantissa != 0 || __ieeeExponent <= 1;
178 const uint32_t __mm = 4 * __m2 - 1 - __mmShift;
179
180 // Step 3: Convert to a decimal power base using 64-bit arithmetic.
181 uint32_t __vr, __vp, __vm;
182 int32_t __e10;
183 bool __vmIsTrailingZeros = false;
184 bool __vrIsTrailingZeros = false;
185 uint8_t __lastRemovedDigit = 0;
186 if (__e2 >= 0) {
187 const uint32_t __q = __log10Pow2(e: __e2);
188 __e10 = static_cast<int32_t>(__q);
189 const int32_t __k = __FLOAT_POW5_INV_BITCOUNT + __pow5bits(e: static_cast<int32_t>(__q)) - 1;
190 const int32_t __i = -__e2 + static_cast<int32_t>(__q) + __k;
191 __vr = __mulPow5InvDivPow2(m: __mv, __q, j: __i);
192 __vp = __mulPow5InvDivPow2(m: __mp, __q, j: __i);
193 __vm = __mulPow5InvDivPow2(m: __mm, __q, j: __i);
194 if (__q != 0 && (__vp - 1) / 10 <= __vm / 10) {
195 // We need to know one removed digit even if we are not going to loop below. We could use
196 // __q = X - 1 above, except that would require 33 bits for the result, and we've found that
197 // 32-bit arithmetic is faster even on 64-bit machines.
198 const int32_t __l = __FLOAT_POW5_INV_BITCOUNT + __pow5bits(e: static_cast<int32_t>(__q - 1)) - 1;
199 __lastRemovedDigit = static_cast<uint8_t>(__mulPow5InvDivPow2(m: __mv, q: __q - 1,
200 j: -__e2 + static_cast<int32_t>(__q) - 1 + __l) % 10);
201 }
202 if (__q <= 9) {
203 // The largest power of 5 that fits in 24 bits is 5^10, but __q <= 9 seems to be safe as well.
204 // Only one of __mp, __mv, and __mm can be a multiple of 5, if any.
205 if (__mv % 5 == 0) {
206 __vrIsTrailingZeros = __multipleOfPowerOf5(value: __mv, p: __q);
207 } else if (__acceptBounds) {
208 __vmIsTrailingZeros = __multipleOfPowerOf5(value: __mm, p: __q);
209 } else {
210 __vp -= __multipleOfPowerOf5(value: __mp, p: __q);
211 }
212 }
213 } else {
214 const uint32_t __q = __log10Pow5(e: -__e2);
215 __e10 = static_cast<int32_t>(__q) + __e2;
216 const int32_t __i = -__e2 - static_cast<int32_t>(__q);
217 const int32_t __k = __pow5bits(e: __i) - __FLOAT_POW5_BITCOUNT;
218 int32_t __j = static_cast<int32_t>(__q) - __k;
219 __vr = __mulPow5divPow2(m: __mv, i: static_cast<uint32_t>(__i), __j);
220 __vp = __mulPow5divPow2(m: __mp, i: static_cast<uint32_t>(__i), __j);
221 __vm = __mulPow5divPow2(m: __mm, i: static_cast<uint32_t>(__i), __j);
222 if (__q != 0 && (__vp - 1) / 10 <= __vm / 10) {
223 __j = static_cast<int32_t>(__q) - 1 - (__pow5bits(e: __i + 1) - __FLOAT_POW5_BITCOUNT);
224 __lastRemovedDigit = static_cast<uint8_t>(__mulPow5divPow2(m: __mv, i: static_cast<uint32_t>(__i + 1), __j) % 10);
225 }
226 if (__q <= 1) {
227 // {__vr,__vp,__vm} is trailing zeros if {__mv,__mp,__mm} has at least __q trailing 0 bits.
228 // __mv = 4 * __m2, so it always has at least two trailing 0 bits.
229 __vrIsTrailingZeros = true;
230 if (__acceptBounds) {
231 // __mm = __mv - 1 - __mmShift, so it has 1 trailing 0 bit iff __mmShift == 1.
232 __vmIsTrailingZeros = __mmShift == 1;
233 } else {
234 // __mp = __mv + 2, so it always has at least one trailing 0 bit.
235 --__vp;
236 }
237 } else if (__q < 31) { // TRANSITION(ulfjack): Use a tighter bound here.
238 __vrIsTrailingZeros = __multipleOfPowerOf2(value: __mv, p: __q - 1);
239 }
240 }
241
242 // Step 4: Find the shortest decimal representation in the interval of valid representations.
243 int32_t __removed = 0;
244 uint32_t _Output;
245 if (__vmIsTrailingZeros || __vrIsTrailingZeros) {
246 // General case, which happens rarely (~4.0%).
247 while (__vp / 10 > __vm / 10) {
248#ifdef __clang__ // TRANSITION, LLVM-23106
249 __vmIsTrailingZeros &= __vm - (__vm / 10) * 10 == 0;
250#else
251 __vmIsTrailingZeros &= __vm % 10 == 0;
252#endif
253 __vrIsTrailingZeros &= __lastRemovedDigit == 0;
254 __lastRemovedDigit = static_cast<uint8_t>(__vr % 10);
255 __vr /= 10;
256 __vp /= 10;
257 __vm /= 10;
258 ++__removed;
259 }
260 if (__vmIsTrailingZeros) {
261 while (__vm % 10 == 0) {
262 __vrIsTrailingZeros &= __lastRemovedDigit == 0;
263 __lastRemovedDigit = static_cast<uint8_t>(__vr % 10);
264 __vr /= 10;
265 __vp /= 10;
266 __vm /= 10;
267 ++__removed;
268 }
269 }
270 if (__vrIsTrailingZeros && __lastRemovedDigit == 5 && __vr % 2 == 0) {
271 // Round even if the exact number is .....50..0.
272 __lastRemovedDigit = 4;
273 }
274 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.
275 _Output = __vr + ((__vr == __vm && (!__acceptBounds || !__vmIsTrailingZeros)) || __lastRemovedDigit >= 5);
276 } else {
277 // Specialized for the common case (~96.0%). Percentages below are relative to this.
278 // Loop iterations below (approximately):
279 // 0: 13.6%, 1: 70.7%, 2: 14.1%, 3: 1.39%, 4: 0.14%, 5+: 0.01%
280 while (__vp / 10 > __vm / 10) {
281 __lastRemovedDigit = static_cast<uint8_t>(__vr % 10);
282 __vr /= 10;
283 __vp /= 10;
284 __vm /= 10;
285 ++__removed;
286 }
287 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.
288 _Output = __vr + (__vr == __vm || __lastRemovedDigit >= 5);
289 }
290 const int32_t __exp = __e10 + __removed;
291
292 __floating_decimal_32 __fd;
293 __fd.__exponent = __exp;
294 __fd.__mantissa = _Output;
295 return __fd;
296}
297
298[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result _Large_integer_to_chars(char* const _First, char* const _Last,
299 const uint32_t _Mantissa2, const int32_t _Exponent2) {
300
301 // Print the integer _Mantissa2 * 2^_Exponent2 exactly.
302
303 // For nonzero integers, _Exponent2 >= -23. (The minimum value occurs when _Mantissa2 * 2^_Exponent2 is 1.
304 // In that case, _Mantissa2 is the implicit 1 bit followed by 23 zeros, so _Exponent2 is -23 to shift away
305 // the zeros.) The dense range of exactly representable integers has negative or zero exponents
306 // (as positive exponents make the range non-dense). For that dense range, Ryu will always be used:
307 // every digit is necessary to uniquely identify the value, so Ryu must print them all.
308
309 // Positive exponents are the non-dense range of exactly representable integers.
310 // This contains all of the values for which Ryu can't be used (and a few Ryu-friendly values).
311
312 // Performance note: Long division appears to be faster than losslessly widening float to double and calling
313 // __d2fixed_buffered_n(). If __f2fixed_buffered_n() is implemented, it might be faster than long division.
314
315 _LIBCPP_ASSERT_INTERNAL(_Exponent2 > 0, "");
316 _LIBCPP_ASSERT_INTERNAL(_Exponent2 <= 104, ""); // because __ieeeExponent <= 254
317
318 // Manually represent _Mantissa2 * 2^_Exponent2 as a large integer. _Mantissa2 is always 24 bits
319 // (due to the implicit bit), while _Exponent2 indicates a shift of at most 104 bits.
320 // 24 + 104 equals 128 equals 4 * 32, so we need exactly 4 32-bit elements.
321 // We use a little-endian representation, visualized like this:
322
323 // << left shift <<
324 // most significant
325 // _Data[3] _Data[2] _Data[1] _Data[0]
326 // least significant
327 // >> right shift >>
328
329 constexpr uint32_t _Data_size = 4;
330 uint32_t _Data[_Data_size]{};
331
332 // _Maxidx is the index of the most significant nonzero element.
333 uint32_t _Maxidx = ((24 + static_cast<uint32_t>(_Exponent2) + 31) / 32) - 1;
334 _LIBCPP_ASSERT_INTERNAL(_Maxidx < _Data_size, "");
335
336 const uint32_t _Bit_shift = static_cast<uint32_t>(_Exponent2) % 32;
337 if (_Bit_shift <= 8) { // _Mantissa2's 24 bits don't cross an element boundary
338 _Data[_Maxidx] = _Mantissa2 << _Bit_shift;
339 } else { // _Mantissa2's 24 bits cross an element boundary
340 _Data[_Maxidx - 1] = _Mantissa2 << _Bit_shift;
341 _Data[_Maxidx] = _Mantissa2 >> (32 - _Bit_shift);
342 }
343
344 // If Ryu hasn't determined the total output length, we need to buffer the digits generated from right to left
345 // by long division. The largest possible float is: 340'282346638'528859811'704183484'516925440
346 uint32_t _Blocks[4];
347 int32_t _Filled_blocks = 0;
348 // From left to right, we're going to print:
349 // _Data[0] will be [1, 10] digits.
350 // Then if _Filled_blocks > 0:
351 // _Blocks[_Filled_blocks - 1], ..., _Blocks[0] will be 0-filled 9-digit blocks.
352
353 if (_Maxidx != 0) { // If the integer is actually large, perform long division.
354 // Otherwise, skip to printing _Data[0].
355 for (;;) {
356 // Loop invariant: _Maxidx != 0 (i.e. the integer is actually large)
357
358 const uint32_t _Most_significant_elem = _Data[_Maxidx];
359 const uint32_t _Initial_remainder = _Most_significant_elem % 1000000000;
360 const uint32_t _Initial_quotient = _Most_significant_elem / 1000000000;
361 _Data[_Maxidx] = _Initial_quotient;
362 uint64_t _Remainder = _Initial_remainder;
363
364 // Process less significant elements.
365 uint32_t _Idx = _Maxidx;
366 do {
367 --_Idx; // Initially, _Remainder is at most 10^9 - 1.
368
369 // Now, _Remainder is at most (10^9 - 1) * 2^32 + 2^32 - 1, simplified to 10^9 * 2^32 - 1.
370 _Remainder = (_Remainder << 32) | _Data[_Idx];
371
372 // floor((10^9 * 2^32 - 1) / 10^9) == 2^32 - 1, so uint32_t _Quotient is lossless.
373 const uint32_t _Quotient = static_cast<uint32_t>(__div1e9(x: _Remainder));
374
375 // _Remainder is at most 10^9 - 1 again.
376 // For uint32_t truncation, see the __mod1e9() comment in d2s_intrinsics.h.
377 _Remainder = static_cast<uint32_t>(_Remainder) - 1000000000u * _Quotient;
378
379 _Data[_Idx] = _Quotient;
380 } while (_Idx != 0);
381
382 // Store a 0-filled 9-digit block.
383 _Blocks[_Filled_blocks++] = static_cast<uint32_t>(_Remainder);
384
385 if (_Initial_quotient == 0) { // Is the large integer shrinking?
386 --_Maxidx; // log2(10^9) is 29.9, so we can't shrink by more than one element.
387 if (_Maxidx == 0) {
388 break; // We've finished long division. Now we need to print _Data[0].
389 }
390 }
391 }
392 }
393
394 _LIBCPP_ASSERT_INTERNAL(_Data[0] != 0, "");
395 for (uint32_t _Idx = 1; _Idx < _Data_size; ++_Idx) {
396 _LIBCPP_ASSERT_INTERNAL(_Data[_Idx] == 0, "");
397 }
398
399 const uint32_t _Data_olength = _Data[0] >= 1000000000 ? 10 : __decimalLength9(v: _Data[0]);
400 const uint32_t _Total_fixed_length = _Data_olength + 9 * _Filled_blocks;
401
402 if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) {
403 return { .ptr: _Last, .ec: errc::value_too_large };
404 }
405
406 char* _Result = _First;
407
408 // Print _Data[0]. While it's up to 10 digits,
409 // which is more than Ryu generates, the code below can handle this.
410 __append_n_digits(olength: _Data_olength, digits: _Data[0], result: _Result);
411 _Result += _Data_olength;
412
413 // Print 0-filled 9-digit blocks.
414 for (int32_t _Idx = _Filled_blocks - 1; _Idx >= 0; --_Idx) {
415 __append_nine_digits(digits: _Blocks[_Idx], result: _Result);
416 _Result += 9;
417 }
418
419 return { .ptr: _Result, .ec: errc{} };
420}
421
422[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result __to_chars(char* const _First, char* const _Last, const __floating_decimal_32 __v,
423 chars_format _Fmt, const uint32_t __ieeeMantissa, const uint32_t __ieeeExponent) {
424 // Step 5: Print the decimal representation.
425 uint32_t _Output = __v.__mantissa;
426 int32_t _Ryu_exponent = __v.__exponent;
427 const uint32_t __olength = __decimalLength9(v: _Output);
428 int32_t _Scientific_exponent = _Ryu_exponent + static_cast<int32_t>(__olength) - 1;
429
430 if (_Fmt == chars_format{}) {
431 int32_t _Lower;
432 int32_t _Upper;
433
434 if (__olength == 1) {
435 // Value | Fixed | Scientific
436 // 1e-3 | "0.001" | "1e-03"
437 // 1e4 | "10000" | "1e+04"
438 _Lower = -3;
439 _Upper = 4;
440 } else {
441 // Value | Fixed | Scientific
442 // 1234e-7 | "0.0001234" | "1.234e-04"
443 // 1234e5 | "123400000" | "1.234e+08"
444 _Lower = -static_cast<int32_t>(__olength + 3);
445 _Upper = 5;
446 }
447
448 if (_Lower <= _Ryu_exponent && _Ryu_exponent <= _Upper) {
449 _Fmt = chars_format::fixed;
450 } else {
451 _Fmt = chars_format::scientific;
452 }
453 } else if (_Fmt == chars_format::general) {
454 // C11 7.21.6.1 "The fprintf function"/8:
455 // "Let P equal [...] 6 if the precision is omitted [...].
456 // Then, if a conversion with style E would have an exponent of X:
457 // - if P > X >= -4, the conversion is with style f [...].
458 // - otherwise, the conversion is with style e [...]."
459 if (-4 <= _Scientific_exponent && _Scientific_exponent < 6) {
460 _Fmt = chars_format::fixed;
461 } else {
462 _Fmt = chars_format::scientific;
463 }
464 }
465
466 if (_Fmt == chars_format::fixed) {
467 // Example: _Output == 1729, __olength == 4
468
469 // _Ryu_exponent | Printed | _Whole_digits | _Total_fixed_length | Notes
470 // --------------|----------|---------------|----------------------|---------------------------------------
471 // 2 | 172900 | 6 | _Whole_digits | Ryu can't be used for printing
472 // 1 | 17290 | 5 | (sometimes adjusted) | when the trimmed digits are nonzero.
473 // --------------|----------|---------------|----------------------|---------------------------------------
474 // 0 | 1729 | 4 | _Whole_digits | Unified length cases.
475 // --------------|----------|---------------|----------------------|---------------------------------------
476 // -1 | 172.9 | 3 | __olength + 1 | This case can't happen for
477 // -2 | 17.29 | 2 | | __olength == 1, but no additional
478 // -3 | 1.729 | 1 | | code is needed to avoid it.
479 // --------------|----------|---------------|----------------------|---------------------------------------
480 // -4 | 0.1729 | 0 | 2 - _Ryu_exponent | C11 7.21.6.1 "The fprintf function"/8:
481 // -5 | 0.01729 | -1 | | "If a decimal-point character appears,
482 // -6 | 0.001729 | -2 | | at least one digit appears before it."
483
484 const int32_t _Whole_digits = static_cast<int32_t>(__olength) + _Ryu_exponent;
485
486 uint32_t _Total_fixed_length;
487 if (_Ryu_exponent >= 0) { // cases "172900" and "1729"
488 _Total_fixed_length = static_cast<uint32_t>(_Whole_digits);
489 if (_Output == 1) {
490 // Rounding can affect the number of digits.
491 // For example, 1e11f is exactly "99999997952" which is 11 digits instead of 12.
492 // We can use a lookup table to detect this and adjust the total length.
493 static constexpr uint8_t _Adjustment[39] = {
494 0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,1 };
495 _Total_fixed_length -= _Adjustment[_Ryu_exponent];
496 // _Whole_digits doesn't need to be adjusted because these cases won't refer to it later.
497 }
498 } else if (_Whole_digits > 0) { // case "17.29"
499 _Total_fixed_length = __olength + 1;
500 } else { // case "0.001729"
501 _Total_fixed_length = static_cast<uint32_t>(2 - _Ryu_exponent);
502 }
503
504 if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) {
505 return { .ptr: _Last, .ec: errc::value_too_large };
506 }
507
508 char* _Mid;
509 if (_Ryu_exponent > 0) { // case "172900"
510 bool _Can_use_ryu;
511
512 if (_Ryu_exponent > 10) { // 10^10 is the largest power of 10 that's exactly representable as a float.
513 _Can_use_ryu = false;
514 } else {
515 // Ryu generated X: __v.__mantissa * 10^_Ryu_exponent
516 // __v.__mantissa == 2^_Trailing_zero_bits * (__v.__mantissa >> _Trailing_zero_bits)
517 // 10^_Ryu_exponent == 2^_Ryu_exponent * 5^_Ryu_exponent
518
519 // _Trailing_zero_bits is [0, 29] (aside: because 2^29 is the largest power of 2
520 // with 9 decimal digits, which is float's round-trip limit.)
521 // _Ryu_exponent is [1, 10].
522 // Normalization adds [2, 23] (aside: at least 2 because the pre-normalized mantissa is at least 5).
523 // This adds up to [3, 62], which is well below float's maximum binary exponent 127.
524
525 // Therefore, we just need to consider (__v.__mantissa >> _Trailing_zero_bits) * 5^_Ryu_exponent.
526
527 // If that product would exceed 24 bits, then X can't be exactly represented as a float.
528 // (That's not a problem for round-tripping, because X is close enough to the original float,
529 // but X isn't mathematically equal to the original float.) This requires a high-precision fallback.
530
531 // If the product is 24 bits or smaller, then X can be exactly represented as a float (and we don't
532 // need to re-synthesize it; the original float must have been X, because Ryu wouldn't produce the
533 // same output for two different floats X and Y). This allows Ryu's output to be used (zero-filled).
534
535 // (2^24 - 1) / 5^0 (for indexing), (2^24 - 1) / 5^1, ..., (2^24 - 1) / 5^10
536 static constexpr uint32_t _Max_shifted_mantissa[11] = {
537 16777215, 3355443, 671088, 134217, 26843, 5368, 1073, 214, 42, 8, 1 };
538
539 unsigned long _Trailing_zero_bits = std::countr_zero(t: __v.__mantissa); // __v.__mantissa is guaranteed nonzero
540 const uint32_t _Shifted_mantissa = __v.__mantissa >> _Trailing_zero_bits;
541 _Can_use_ryu = _Shifted_mantissa <= _Max_shifted_mantissa[_Ryu_exponent];
542 }
543
544 if (!_Can_use_ryu) {
545 const uint32_t _Mantissa2 = __ieeeMantissa | (1u << __FLOAT_MANTISSA_BITS); // restore implicit bit
546 const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent)
547 - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS; // bias and normalization
548
549 // Performance note: We've already called Ryu, so this will redundantly perform buffering and bounds checking.
550 return _Large_integer_to_chars(_First, _Last, _Mantissa2, _Exponent2);
551 }
552
553 // _Can_use_ryu
554 // Print the decimal digits, left-aligned within [_First, _First + _Total_fixed_length).
555 _Mid = _First + __olength;
556 } else { // cases "1729", "17.29", and "0.001729"
557 // Print the decimal digits, right-aligned within [_First, _First + _Total_fixed_length).
558 _Mid = _First + _Total_fixed_length;
559 }
560
561 while (_Output >= 10000) {
562#ifdef __clang__ // TRANSITION, LLVM-38217
563 const uint32_t __c = _Output - 10000 * (_Output / 10000);
564#else
565 const uint32_t __c = _Output % 10000;
566#endif
567 _Output /= 10000;
568 const uint32_t __c0 = (__c % 100) << 1;
569 const uint32_t __c1 = (__c / 100) << 1;
570 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c0, n: 2);
571 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c1, n: 2);
572 }
573 if (_Output >= 100) {
574 const uint32_t __c = (_Output % 100) << 1;
575 _Output /= 100;
576 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c, n: 2);
577 }
578 if (_Output >= 10) {
579 const uint32_t __c = _Output << 1;
580 std::memcpy(dest: _Mid -= 2, src: __DIGIT_TABLE + __c, n: 2);
581 } else {
582 *--_Mid = static_cast<char>('0' + _Output);
583 }
584
585 if (_Ryu_exponent > 0) { // case "172900" with _Can_use_ryu
586 // Performance note: it might be more efficient to do this immediately after setting _Mid.
587 std::memset(s: _First + __olength, c: '0', n: static_cast<size_t>(_Ryu_exponent));
588 } else if (_Ryu_exponent == 0) { // case "1729"
589 // Done!
590 } else if (_Whole_digits > 0) { // case "17.29"
591 // Performance note: moving digits might not be optimal.
592 std::memmove(dest: _First, src: _First + 1, n: static_cast<size_t>(_Whole_digits));
593 _First[_Whole_digits] = '.';
594 } else { // case "0.001729"
595 // Performance note: a larger memset() followed by overwriting '.' might be more efficient.
596 _First[0] = '0';
597 _First[1] = '.';
598 std::memset(s: _First + 2, c: '0', n: static_cast<size_t>(-_Whole_digits));
599 }
600
601 return { .ptr: _First + _Total_fixed_length, .ec: errc{} };
602 }
603
604 const uint32_t _Total_scientific_length =
605 __olength + (__olength > 1) + 4; // digits + possible decimal point + scientific exponent
606 if (_Last - _First < static_cast<ptrdiff_t>(_Total_scientific_length)) {
607 return { .ptr: _Last, .ec: errc::value_too_large };
608 }
609 char* const __result = _First;
610
611 // Print the decimal digits.
612 uint32_t __i = 0;
613 while (_Output >= 10000) {
614#ifdef __clang__ // TRANSITION, LLVM-38217
615 const uint32_t __c = _Output - 10000 * (_Output / 10000);
616#else
617 const uint32_t __c = _Output % 10000;
618#endif
619 _Output /= 10000;
620 const uint32_t __c0 = (__c % 100) << 1;
621 const uint32_t __c1 = (__c / 100) << 1;
622 std::memcpy(dest: __result + __olength - __i - 1, src: __DIGIT_TABLE + __c0, n: 2);
623 std::memcpy(dest: __result + __olength - __i - 3, src: __DIGIT_TABLE + __c1, n: 2);
624 __i += 4;
625 }
626 if (_Output >= 100) {
627 const uint32_t __c = (_Output % 100) << 1;
628 _Output /= 100;
629 std::memcpy(dest: __result + __olength - __i - 1, src: __DIGIT_TABLE + __c, n: 2);
630 __i += 2;
631 }
632 if (_Output >= 10) {
633 const uint32_t __c = _Output << 1;
634 // We can't use memcpy here: the decimal dot goes between these two digits.
635 __result[2] = __DIGIT_TABLE[__c + 1];
636 __result[0] = __DIGIT_TABLE[__c];
637 } else {
638 __result[0] = static_cast<char>('0' + _Output);
639 }
640
641 // Print decimal point if needed.
642 uint32_t __index;
643 if (__olength > 1) {
644 __result[1] = '.';
645 __index = __olength + 1;
646 } else {
647 __index = 1;
648 }
649
650 // Print the exponent.
651 __result[__index++] = 'e';
652 if (_Scientific_exponent < 0) {
653 __result[__index++] = '-';
654 _Scientific_exponent = -_Scientific_exponent;
655 } else {
656 __result[__index++] = '+';
657 }
658
659 std::memcpy(dest: __result + __index, src: __DIGIT_TABLE + 2 * _Scientific_exponent, n: 2);
660 __index += 2;
661
662 return { .ptr: _First + _Total_scientific_length, .ec: errc{} };
663}
664
665[[nodiscard]] to_chars_result __f2s_buffered_n(char* const _First, char* const _Last, const float __f,
666 const chars_format _Fmt) {
667
668 // Step 1: Decode the floating-point number, and unify normalized and subnormal cases.
669 const uint32_t __bits = __float_to_bits(__f);
670
671 // Case distinction; exit early for the easy cases.
672 if (__bits == 0) {
673 if (_Fmt == chars_format::scientific) {
674 if (_Last - _First < 5) {
675 return { .ptr: _Last, .ec: errc::value_too_large };
676 }
677
678 std::memcpy(dest: _First, src: "0e+00", n: 5);
679
680 return { .ptr: _First + 5, .ec: errc{} };
681 }
682
683 // Print "0" for chars_format::fixed, chars_format::general, and chars_format{}.
684 if (_First == _Last) {
685 return { .ptr: _Last, .ec: errc::value_too_large };
686 }
687
688 *_First = '0';
689
690 return { .ptr: _First + 1, .ec: errc{} };
691 }
692
693 // Decode __bits into mantissa and exponent.
694 const uint32_t __ieeeMantissa = __bits & ((1u << __FLOAT_MANTISSA_BITS) - 1);
695 const uint32_t __ieeeExponent = __bits >> __FLOAT_MANTISSA_BITS;
696
697 // When _Fmt == chars_format::fixed and the floating-point number is a large integer,
698 // it's faster to skip Ryu and immediately print the integer exactly.
699 if (_Fmt == chars_format::fixed) {
700 const uint32_t _Mantissa2 = __ieeeMantissa | (1u << __FLOAT_MANTISSA_BITS); // restore implicit bit
701 const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent)
702 - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS; // bias and normalization
703
704 // Normal values are equal to _Mantissa2 * 2^_Exponent2.
705 // (Subnormals are different, but they'll be rejected by the _Exponent2 test here, so they can be ignored.)
706
707 if (_Exponent2 > 0) {
708 return _Large_integer_to_chars(_First, _Last, _Mantissa2, _Exponent2);
709 }
710 }
711
712 const __floating_decimal_32 __v = __f2d(__ieeeMantissa, __ieeeExponent);
713 return __to_chars(_First, _Last, __v, _Fmt, __ieeeMantissa, __ieeeExponent);
714}
715
716_LIBCPP_END_NAMESPACE_STD
717
718// clang-format on
719