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