Coverage Report

Created: 2022-07-16 07:03

/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