xref: /llvm-project/libc/src/__support/float_to_string.h (revision 7302c8dbe71b7c03b73a35a21fa4b415fa1f4505)
107c0a41bSMichael Jones //===-- Utilities to convert floating point values to string ----*- C++ -*-===//
207c0a41bSMichael Jones //
307c0a41bSMichael Jones // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
407c0a41bSMichael Jones // See https://llvm.org/LICENSE.txt for license information.
507c0a41bSMichael Jones // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
607c0a41bSMichael Jones //
707c0a41bSMichael Jones //===----------------------------------------------------------------------===//
807c0a41bSMichael Jones 
9270547f3SGuillaume Chatelet #ifndef LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H
10270547f3SGuillaume Chatelet #define LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H
1107c0a41bSMichael Jones 
1207c0a41bSMichael Jones #include <stdint.h>
1307c0a41bSMichael Jones 
14a621198aSmichaelrj-google #include "src/__support/CPP/limits.h"
1507c0a41bSMichael Jones #include "src/__support/CPP/type_traits.h"
1607c0a41bSMichael Jones #include "src/__support/FPUtil/FPBits.h"
17688b9730SMichael Jones #include "src/__support/FPUtil/dyadic_float.h"
1809efe848SGuillaume Chatelet #include "src/__support/big_int.h"
1959c809cdSSiva Chandra Reddy #include "src/__support/common.h"
2058a75c6aSSiva Chandra Reddy #include "src/__support/libc_assert.h"
21a621198aSmichaelrj-google #include "src/__support/macros/attributes.h"
225ff3ff33SPetr Hosek #include "src/__support/macros/config.h"
23e1d64b76SMichael Jones #include "src/__support/sign.h"
24688b9730SMichael Jones 
25688b9730SMichael Jones // This file has 5 compile-time flags to allow the user to configure the float
26a621198aSmichaelrj-google // to string behavior. These were used to explore tradeoffs during the design
27a621198aSmichaelrj-google // phase, and can still be used to gain specific properties. Unless you
28a621198aSmichaelrj-google // specifically know what you're doing, you should leave all these flags off.
29a621198aSmichaelrj-google 
30a621198aSmichaelrj-google // LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD
31a621198aSmichaelrj-google //  This flag disables the separate long double conversion implementation. It is
32a621198aSmichaelrj-google //  not based on the Ryu algorithm, instead generating the digits by
33a621198aSmichaelrj-google //  multiplying/dividing the written-out number by 10^9 to get blocks. It's
34a621198aSmichaelrj-google //  significantly faster than INT_CALC, only about 10x slower than MEGA_TABLE,
35a621198aSmichaelrj-google //  and is small in binary size. Its downside is that it always calculates all
36a621198aSmichaelrj-google //  of the digits above the decimal point, making it inefficient for %e calls
37a621198aSmichaelrj-google //  with large exponents. This specialization overrides other flags, so this
38a621198aSmichaelrj-google //  flag must be set for other flags to effect the long double behavior.
39688b9730SMichael Jones 
40688b9730SMichael Jones // LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
41688b9730SMichael Jones //  The Mega Table is ~5 megabytes when compiled. It lists the constants needed
42688b9730SMichael Jones //  to perform the Ryu Printf algorithm (described below) for all long double
43688b9730SMichael Jones //  values. This makes it extremely fast for both doubles and long doubles, in
44688b9730SMichael Jones //  exchange for large binary size.
45688b9730SMichael Jones 
46688b9730SMichael Jones // LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT
47688b9730SMichael Jones //  Dyadic floats are software floating point numbers, and their accuracy can be
48688b9730SMichael Jones //  as high as necessary. This option uses 256 bit dyadic floats to calculate
49688b9730SMichael Jones //  the table values that Ryu Printf needs. This is reasonably fast and very
50688b9730SMichael Jones //  small compared to the Mega Table, but the 256 bit floats only give accurate
51688b9730SMichael Jones //  results for the first ~50 digits of the output. In practice this shouldn't
52688b9730SMichael Jones //  be a problem since long doubles are only accurate for ~35 digits, but the
53a621198aSmichaelrj-google //  trailing values all being 0s may cause brittle tests to fail.
54688b9730SMichael Jones 
55688b9730SMichael Jones // LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC
56688b9730SMichael Jones //  Integer Calculation uses wide integers to do the calculations for the Ryu
57688b9730SMichael Jones //  Printf table, which is just as accurate as the Mega Table without requiring
58688b9730SMichael Jones //  as much code size. These integers can be very large (~32KB at max, though
59688b9730SMichael Jones //  always on the stack) to handle the edges of the long double range. They are
60688b9730SMichael Jones //  also very slow, taking multiple seconds on a powerful CPU to calculate the
61688b9730SMichael Jones //  values at the end of the range. If no flag is set, this is used for long
62688b9730SMichael Jones //  doubles, the flag only changes the double behavior.
63688b9730SMichael Jones 
64688b9730SMichael Jones // LIBC_COPT_FLOAT_TO_STR_NO_TABLE
65688b9730SMichael Jones //  This flag doesn't change the actual calculation method, instead it is used
66688b9730SMichael Jones //  to disable the normal Ryu Printf table for configurations that don't use any
67688b9730SMichael Jones //  table at all.
68688b9730SMichael Jones 
69688b9730SMichael Jones // Default Config:
70688b9730SMichael Jones //  If no flags are set, doubles use the normal (and much more reasonably sized)
71a621198aSmichaelrj-google //  Ryu Printf table and long doubles use their specialized implementation. This
72a621198aSmichaelrj-google //  provides good performance and binary size.
73688b9730SMichael Jones 
74688b9730SMichael Jones #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
75688b9730SMichael Jones #include "src/__support/ryu_long_double_constants.h"
76688b9730SMichael Jones #elif !defined(LIBC_COPT_FLOAT_TO_STR_NO_TABLE)
7707c0a41bSMichael Jones #include "src/__support/ryu_constants.h"
78688b9730SMichael Jones #else
79688b9730SMichael Jones constexpr size_t IDX_SIZE = 1;
80688b9730SMichael Jones constexpr size_t MID_INT_SIZE = 192;
81688b9730SMichael Jones #endif
8207c0a41bSMichael Jones 
8307c0a41bSMichael Jones // This implementation is based on the Ryu Printf algorithm by Ulf Adams:
8407c0a41bSMichael Jones // Ulf Adams. 2019. Ryū revisited: printf floating point conversion.
8507c0a41bSMichael Jones // Proc. ACM Program. Lang. 3, OOPSLA, Article 169 (October 2019), 23 pages.
8607c0a41bSMichael Jones // https://doi.org/10.1145/3360595
8707c0a41bSMichael Jones 
8807c0a41bSMichael Jones // This version is modified to require significantly less memory (it doesn't use
8907c0a41bSMichael Jones // a large buffer to store the result).
9007c0a41bSMichael Jones 
9107c0a41bSMichael Jones // The general concept of this algorithm is as follows:
9207c0a41bSMichael Jones // We want to calculate a 9 digit segment of a floating point number using this
9307c0a41bSMichael Jones // formula: floor((mantissa * 2^exponent)/10^i) % 10^9.
9407c0a41bSMichael Jones // To do so normally would involve large integers (~1000 bits for doubles), so
9507c0a41bSMichael Jones // we use a shortcut. We can avoid calculating 2^exponent / 10^i by using a
9607c0a41bSMichael Jones // lookup table. The resulting intermediate value needs to be about 192 bits to
9707c0a41bSMichael Jones // store the result with enough precision. Since this is all being done with
9807c0a41bSMichael Jones // integers for appropriate precision, we would run into a problem if
9907c0a41bSMichael Jones // i > exponent since then 2^exponent / 10^i would be less than 1. To correct
10007c0a41bSMichael Jones // for this, the actual calculation done is 2^(exponent + c) / 10^i, and then
10107c0a41bSMichael Jones // when multiplying by the mantissa we reverse this by dividing by 2^c, like so:
10207c0a41bSMichael Jones // floor((mantissa * table[exponent][i])/(2^c)) % 10^9.
10307c0a41bSMichael Jones // This gives a 9 digit value, which is small enough to fit in a 32 bit integer,
10407c0a41bSMichael Jones // and that integer is converted into a string as normal, and called a block. In
10507c0a41bSMichael Jones // this implementation, the most recent block is buffered, so that if rounding
10607c0a41bSMichael Jones // is necessary the block can be adjusted before being written to the output.
10707c0a41bSMichael Jones // Any block that is all 9s adds one to the max block counter and doesn't clear
10807c0a41bSMichael Jones // the buffer because they can cause the block above them to be rounded up.
10907c0a41bSMichael Jones 
1105ff3ff33SPetr Hosek namespace LIBC_NAMESPACE_DECL {
11107c0a41bSMichael Jones 
11207c0a41bSMichael Jones using BlockInt = uint32_t;
113ab65c9c3Smichaelrj-google constexpr uint32_t BLOCK_SIZE = 9;
114a621198aSmichaelrj-google constexpr uint64_t EXP5_9 = 1953125;
115a621198aSmichaelrj-google constexpr uint64_t EXP10_9 = 1000000000;
11607c0a41bSMichael Jones 
117c09e6905SGuillaume Chatelet using FPBits = fputil::FPBits<long double>;
11807c0a41bSMichael Jones 
119688b9730SMichael Jones // Larger numbers prefer a slightly larger constant than is used for the smaller
120688b9730SMichael Jones // numbers.
121688b9730SMichael Jones constexpr size_t CALC_SHIFT_CONST = 128;
12207c0a41bSMichael Jones 
12307c0a41bSMichael Jones namespace internal {
12407c0a41bSMichael Jones 
125688b9730SMichael Jones // Returns floor(log_10(2^e)); requires 0 <= e <= 42039.
126a621198aSmichaelrj-google LIBC_INLINE constexpr uint32_t log10_pow2(uint64_t e) {
1278fc87f54SMikhail R. Gadelha   LIBC_ASSERT(e <= 42039 &&
12858a75c6aSSiva Chandra Reddy               "Incorrect exponent to perform log10_pow2 approximation.");
129688b9730SMichael Jones   // This approximation is based on the float value for log_10(2). It first
130688b9730SMichael Jones   // gives an incorrect result for our purposes at 42039 (well beyond the 16383
131688b9730SMichael Jones   // maximum for long doubles).
132688b9730SMichael Jones 
133688b9730SMichael Jones   // To get these constants I first evaluated log_10(2) to get an approximation
134688b9730SMichael Jones   // of 0.301029996. Next I passed that value through a string to double
135688b9730SMichael Jones   // conversion to get an explicit mantissa of 0x13441350fbd738 and an exponent
136688b9730SMichael Jones   // of -2 (which becomes -54 when we shift the mantissa to be a non-fractional
137688b9730SMichael Jones   // number). Next I shifted the mantissa right 12 bits to create more space for
138688b9730SMichael Jones   // the multiplication result, adding 12 to the exponent to compensate. To
139688b9730SMichael Jones   // check that this approximation works for our purposes I used the following
140688b9730SMichael Jones   // python code:
141688b9730SMichael Jones   // for i in range(16384):
142688b9730SMichael Jones   //   if(len(str(2**i)) != (((i*0x13441350fbd)>>42)+1)):
143688b9730SMichael Jones   //     print(i)
144688b9730SMichael Jones   // The reason we add 1 is because this evaluation truncates the result, giving
145688b9730SMichael Jones   // us the floor, whereas counting the digits of the power of 2 gives us the
146688b9730SMichael Jones   // ceiling. With a similar loop I checked the maximum valid value and found
147688b9730SMichael Jones   // 42039.
148ab65c9c3Smichaelrj-google   return static_cast<uint32_t>((e * 0x13441350fbdll) >> 42);
149688b9730SMichael Jones }
150688b9730SMichael Jones 
151688b9730SMichael Jones // Same as above, but with different constants.
152a621198aSmichaelrj-google LIBC_INLINE constexpr uint32_t log2_pow5(uint64_t e) {
153ab65c9c3Smichaelrj-google   return static_cast<uint32_t>((e * 0x12934f0979bll) >> 39);
15407c0a41bSMichael Jones }
15507c0a41bSMichael Jones 
15607c0a41bSMichael Jones // Returns 1 + floor(log_10(2^e). This could technically be off by 1 if any
15707c0a41bSMichael Jones // power of 2 was also a power of 10, but since that doesn't exist this is
15807c0a41bSMichael Jones // always accurate. This is used to calculate the maximum number of base-10
15907c0a41bSMichael Jones // digits a given e-bit number could have.
160a621198aSmichaelrj-google LIBC_INLINE constexpr uint32_t ceil_log10_pow2(uint32_t e) {
16107c0a41bSMichael Jones   return log10_pow2(e) + 1;
16207c0a41bSMichael Jones }
16307c0a41bSMichael Jones 
164a621198aSmichaelrj-google LIBC_INLINE constexpr uint32_t div_ceil(uint32_t num, uint32_t denom) {
165a621198aSmichaelrj-google   return (num + (denom - 1)) / denom;
166a621198aSmichaelrj-google }
167a621198aSmichaelrj-google 
16807c0a41bSMichael Jones // Returns the maximum number of 9 digit blocks a number described by the given
16907c0a41bSMichael Jones // index (which is ceil(exponent/16)) and mantissa width could need.
170a621198aSmichaelrj-google LIBC_INLINE constexpr uint32_t length_for_num(uint32_t idx,
171a621198aSmichaelrj-google                                               uint32_t mantissa_width) {
172a621198aSmichaelrj-google   return div_ceil(ceil_log10_pow2(idx) + ceil_log10_pow2(mantissa_width + 1),
173a621198aSmichaelrj-google                   BLOCK_SIZE);
17407c0a41bSMichael Jones }
17507c0a41bSMichael Jones 
17607c0a41bSMichael Jones // The formula for the table when i is positive (or zero) is as follows:
17707c0a41bSMichael Jones // floor(10^(-9i) * 2^(e + c_1) + 1) % (10^9 * 2^c_1)
17807c0a41bSMichael Jones // Rewritten slightly we get:
17907c0a41bSMichael Jones // floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)
18007c0a41bSMichael Jones 
181173d5023SMichael Jones // TODO: Fix long doubles (needs bigger table or alternate algorithm.)
182173d5023SMichael Jones // Currently the table values are generated, which is very slow.
18307c0a41bSMichael Jones template <size_t INT_SIZE>
1846a8e6c9aSGuillaume Chatelet LIBC_INLINE constexpr UInt<MID_INT_SIZE> get_table_positive(int exponent,
185688b9730SMichael Jones                                                             size_t i) {
18607c0a41bSMichael Jones   // INT_SIZE is the size of int that is used for the internal calculations of
18707c0a41bSMichael Jones   // this function. It should be large enough to hold 2^(exponent+constant), so
18807c0a41bSMichael Jones   // ~1000 for double and ~16000 for long double. Be warned that the time
18907c0a41bSMichael Jones   // complexity of exponentiation is O(n^2 * log_2(m)) where n is the number of
19007c0a41bSMichael Jones   // bits in the number being exponentiated and m is the exponent.
191e9bdf4afSMichael Jones   const int shift_amount =
192e9bdf4afSMichael Jones       static_cast<int>(exponent + CALC_SHIFT_CONST - (BLOCK_SIZE * i));
19307c0a41bSMichael Jones   if (shift_amount < 0) {
19407c0a41bSMichael Jones     return 1;
19507c0a41bSMichael Jones   }
1966a8e6c9aSGuillaume Chatelet   UInt<INT_SIZE> num(0);
19707c0a41bSMichael Jones   // MOD_SIZE is one of the limiting factors for how big the constant argument
19807c0a41bSMichael Jones   // can get, since it needs to be small enough to fit in the result UInt,
19907c0a41bSMichael Jones   // otherwise we'll get truncation on return.
2006a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> MOD_SIZE =
2016a8e6c9aSGuillaume Chatelet       (UInt<INT_SIZE>(EXP10_9)
202688b9730SMichael Jones        << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
203688b9730SMichael Jones 
2046a8e6c9aSGuillaume Chatelet   num = UInt<INT_SIZE>(1) << (shift_amount);
20507c0a41bSMichael Jones   if (i > 0) {
2066a8e6c9aSGuillaume Chatelet     UInt<INT_SIZE> fives(EXP5_9);
20707c0a41bSMichael Jones     fives.pow_n(i);
20807c0a41bSMichael Jones     num = num / fives;
20907c0a41bSMichael Jones   }
21007c0a41bSMichael Jones 
21107c0a41bSMichael Jones   num = num + 1;
21207c0a41bSMichael Jones   if (num > MOD_SIZE) {
2134e005515Slntue     auto rem = num.div_uint_half_times_pow_2(
214a621198aSmichaelrj-google                       EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
215688b9730SMichael Jones                    .value();
216688b9730SMichael Jones     num = rem;
21707c0a41bSMichael Jones   }
21807c0a41bSMichael Jones   return num;
21907c0a41bSMichael Jones }
22007c0a41bSMichael Jones 
221688b9730SMichael Jones template <size_t INT_SIZE>
2226a8e6c9aSGuillaume Chatelet LIBC_INLINE UInt<MID_INT_SIZE> get_table_positive_df(int exponent, size_t i) {
223688b9730SMichael Jones   static_assert(INT_SIZE == 256,
224688b9730SMichael Jones                 "Only 256 is supported as an int size right now.");
225688b9730SMichael Jones   // This version uses dyadic floats with 256 bit mantissas to perform the same
226688b9730SMichael Jones   // calculation as above. Due to floating point imprecision it is only accurate
227688b9730SMichael Jones   // for the first 50 digits, but it's much faster. Since even 128 bit long
228688b9730SMichael Jones   // doubles are only accurate to ~35 digits, the 50 digits of accuracy are
229688b9730SMichael Jones   // enough for these floats to be converted back and forth safely. This is
230688b9730SMichael Jones   // ideal for avoiding the size of the long double table.
231e9bdf4afSMichael Jones   const int shift_amount =
232e9bdf4afSMichael Jones       static_cast<int>(exponent + CALC_SHIFT_CONST - (9 * i));
233688b9730SMichael Jones   if (shift_amount < 0) {
234688b9730SMichael Jones     return 1;
235688b9730SMichael Jones   }
236e1d64b76SMichael Jones   fputil::DyadicFloat<INT_SIZE> num(Sign::POS, 0, 1);
2376a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> MOD_SIZE =
2386a8e6c9aSGuillaume Chatelet       (UInt<INT_SIZE>(EXP10_9)
239688b9730SMichael Jones        << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
240688b9730SMichael Jones 
2416a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> FIVE_EXP_MINUS_NINE_MANT{
242688b9730SMichael Jones       {0xf387295d242602a7, 0xfdd7645e011abac9, 0x31680a88f8953030,
243688b9730SMichael Jones        0x89705f4136b4a597}};
244688b9730SMichael Jones 
245688b9730SMichael Jones   static const fputil::DyadicFloat<INT_SIZE> FIVE_EXP_MINUS_NINE(
246e1d64b76SMichael Jones       Sign::POS, -276, FIVE_EXP_MINUS_NINE_MANT);
247688b9730SMichael Jones 
248688b9730SMichael Jones   if (i > 0) {
249e1d64b76SMichael Jones     fputil::DyadicFloat<INT_SIZE> fives =
250e1d64b76SMichael Jones         fputil::pow_n(FIVE_EXP_MINUS_NINE, static_cast<uint32_t>(i));
251688b9730SMichael Jones     num = fives;
252688b9730SMichael Jones   }
253688b9730SMichael Jones   num = mul_pow_2(num, shift_amount);
254688b9730SMichael Jones 
255688b9730SMichael Jones   // Adding one is part of the formula.
256e1d64b76SMichael Jones   UInt<INT_SIZE> int_num = num.as_mantissa_type() + 1;
257688b9730SMichael Jones   if (int_num > MOD_SIZE) {
258688b9730SMichael Jones     auto rem =
259688b9730SMichael Jones         int_num
2604e005515Slntue             .div_uint_half_times_pow_2(
2614e005515Slntue                 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
262688b9730SMichael Jones             .value();
263688b9730SMichael Jones     int_num = rem;
264688b9730SMichael Jones   }
265688b9730SMichael Jones 
2666a8e6c9aSGuillaume Chatelet   UInt<MID_INT_SIZE> result = int_num;
267688b9730SMichael Jones 
268688b9730SMichael Jones   return result;
269688b9730SMichael Jones }
270688b9730SMichael Jones 
27107c0a41bSMichael Jones // The formula for the table when i is negative (or zero) is as follows:
27207c0a41bSMichael Jones // floor(10^(-9i) * 2^(c_0 - e)) % (10^9 * 2^c_0)
27307c0a41bSMichael Jones // Since we know i is always negative, we just take it as unsigned and treat it
27407c0a41bSMichael Jones // as negative. We do the same with exponent, while they're both always negative
27507c0a41bSMichael Jones // in theory, in practice they're converted to positive for simpler
27607c0a41bSMichael Jones // calculations.
27707c0a41bSMichael Jones // The formula being used looks more like this:
27807c0a41bSMichael Jones // floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
279688b9730SMichael Jones template <size_t INT_SIZE>
2806a8e6c9aSGuillaume Chatelet LIBC_INLINE UInt<MID_INT_SIZE> get_table_negative(int exponent, size_t i) {
281688b9730SMichael Jones   int shift_amount = CALC_SHIFT_CONST - exponent;
2826a8e6c9aSGuillaume Chatelet   UInt<INT_SIZE> num(1);
2836a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> MOD_SIZE =
2846a8e6c9aSGuillaume Chatelet       (UInt<INT_SIZE>(EXP10_9)
285688b9730SMichael Jones        << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
28607c0a41bSMichael Jones 
28707c0a41bSMichael Jones   size_t ten_blocks = i;
28807c0a41bSMichael Jones   size_t five_blocks = 0;
28907c0a41bSMichael Jones   if (shift_amount < 0) {
290688b9730SMichael Jones     int block_shifts = (-shift_amount) / BLOCK_SIZE;
29107c0a41bSMichael Jones     if (block_shifts < static_cast<int>(ten_blocks)) {
29207c0a41bSMichael Jones       ten_blocks = ten_blocks - block_shifts;
29307c0a41bSMichael Jones       five_blocks = block_shifts;
294688b9730SMichael Jones       shift_amount = shift_amount + (block_shifts * BLOCK_SIZE);
29507c0a41bSMichael Jones     } else {
29607c0a41bSMichael Jones       ten_blocks = 0;
29707c0a41bSMichael Jones       five_blocks = i;
298ab65c9c3Smichaelrj-google       shift_amount = shift_amount + (static_cast<int>(i) * BLOCK_SIZE);
29907c0a41bSMichael Jones     }
30007c0a41bSMichael Jones   }
30107c0a41bSMichael Jones 
30207c0a41bSMichael Jones   if (five_blocks > 0) {
3036a8e6c9aSGuillaume Chatelet     UInt<INT_SIZE> fives(EXP5_9);
30407c0a41bSMichael Jones     fives.pow_n(five_blocks);
305688b9730SMichael Jones     num = fives;
30607c0a41bSMichael Jones   }
30707c0a41bSMichael Jones   if (ten_blocks > 0) {
3086a8e6c9aSGuillaume Chatelet     UInt<INT_SIZE> tens(EXP10_9);
30907c0a41bSMichael Jones     tens.pow_n(ten_blocks);
310688b9730SMichael Jones     if (five_blocks <= 0) {
311688b9730SMichael Jones       num = tens;
312688b9730SMichael Jones     } else {
31307c0a41bSMichael Jones       num *= tens;
31407c0a41bSMichael Jones     }
315688b9730SMichael Jones   }
31607c0a41bSMichael Jones 
31707c0a41bSMichael Jones   if (shift_amount > 0) {
31807c0a41bSMichael Jones     num = num << shift_amount;
31907c0a41bSMichael Jones   } else {
32007c0a41bSMichael Jones     num = num >> (-shift_amount);
32107c0a41bSMichael Jones   }
322688b9730SMichael Jones   if (num > MOD_SIZE) {
3234e005515Slntue     auto rem = num.div_uint_half_times_pow_2(
324a621198aSmichaelrj-google                       EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
325688b9730SMichael Jones                    .value();
326688b9730SMichael Jones     num = rem;
327688b9730SMichael Jones   }
32807c0a41bSMichael Jones   return num;
32907c0a41bSMichael Jones }
33007c0a41bSMichael Jones 
331688b9730SMichael Jones template <size_t INT_SIZE>
3326a8e6c9aSGuillaume Chatelet LIBC_INLINE UInt<MID_INT_SIZE> get_table_negative_df(int exponent, size_t i) {
333688b9730SMichael Jones   static_assert(INT_SIZE == 256,
334688b9730SMichael Jones                 "Only 256 is supported as an int size right now.");
335688b9730SMichael Jones   // This version uses dyadic floats with 256 bit mantissas to perform the same
336688b9730SMichael Jones   // calculation as above. Due to floating point imprecision it is only accurate
337688b9730SMichael Jones   // for the first 50 digits, but it's much faster. Since even 128 bit long
338688b9730SMichael Jones   // doubles are only accurate to ~35 digits, the 50 digits of accuracy are
339688b9730SMichael Jones   // enough for these floats to be converted back and forth safely. This is
340688b9730SMichael Jones   // ideal for avoiding the size of the long double table.
341688b9730SMichael Jones 
342688b9730SMichael Jones   int shift_amount = CALC_SHIFT_CONST - exponent;
343688b9730SMichael Jones 
344e1d64b76SMichael Jones   fputil::DyadicFloat<INT_SIZE> num(Sign::POS, 0, 1);
3456a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> MOD_SIZE =
3466a8e6c9aSGuillaume Chatelet       (UInt<INT_SIZE>(EXP10_9)
347688b9730SMichael Jones        << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
348688b9730SMichael Jones 
3496a8e6c9aSGuillaume Chatelet   constexpr UInt<INT_SIZE> TEN_EXP_NINE_MANT(EXP10_9);
350688b9730SMichael Jones 
351e1d64b76SMichael Jones   static const fputil::DyadicFloat<INT_SIZE> TEN_EXP_NINE(Sign::POS, 0,
352688b9730SMichael Jones                                                           TEN_EXP_NINE_MANT);
353688b9730SMichael Jones 
354688b9730SMichael Jones   if (i > 0) {
355e1d64b76SMichael Jones     fputil::DyadicFloat<INT_SIZE> tens =
356e1d64b76SMichael Jones         fputil::pow_n(TEN_EXP_NINE, static_cast<uint32_t>(i));
357688b9730SMichael Jones     num = tens;
358688b9730SMichael Jones   }
359688b9730SMichael Jones   num = mul_pow_2(num, shift_amount);
360688b9730SMichael Jones 
361e1d64b76SMichael Jones   UInt<INT_SIZE> int_num = num.as_mantissa_type();
362688b9730SMichael Jones   if (int_num > MOD_SIZE) {
363688b9730SMichael Jones     auto rem =
364688b9730SMichael Jones         int_num
3654e005515Slntue             .div_uint_half_times_pow_2(
3664e005515Slntue                 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
367688b9730SMichael Jones             .value();
368688b9730SMichael Jones     int_num = rem;
369688b9730SMichael Jones   }
370688b9730SMichael Jones 
3716a8e6c9aSGuillaume Chatelet   UInt<MID_INT_SIZE> result = int_num;
372688b9730SMichael Jones 
373688b9730SMichael Jones   return result;
374688b9730SMichael Jones }
375688b9730SMichael Jones 
376c09e6905SGuillaume Chatelet LIBC_INLINE uint32_t mul_shift_mod_1e9(const FPBits::StorageType mantissa,
3776a8e6c9aSGuillaume Chatelet                                        const UInt<MID_INT_SIZE> &large,
37807c0a41bSMichael Jones                                        const int32_t shift_amount) {
379*7302c8dbSNick Desaulniers   // make sure the number of bits is always divisible by 64
380*7302c8dbSNick Desaulniers   UInt<internal::div_ceil(MID_INT_SIZE + FPBits::STORAGE_LEN, 64) * 64> val(
381*7302c8dbSNick Desaulniers       large);
38244bf4c89SMikhail R. Gadelha   val = (val * mantissa) >> shift_amount;
3834e005515Slntue   return static_cast<uint32_t>(
3844e005515Slntue       val.div_uint_half_times_pow_2(static_cast<uint32_t>(EXP10_9), 0).value());
38507c0a41bSMichael Jones }
38607c0a41bSMichael Jones 
38707c0a41bSMichael Jones } // namespace internal
38807c0a41bSMichael Jones 
38907c0a41bSMichael Jones // Convert floating point values to their string representation.
39007c0a41bSMichael Jones // Because the result may not fit in a reasonably sized array, the caller must
39107c0a41bSMichael Jones // request blocks of digits and convert them from integers to strings themself.
39207c0a41bSMichael Jones // Blocks contain the most digits that can be stored in an BlockInt. This is 9
39307c0a41bSMichael Jones // digits for a 32 bit int and 18 digits for a 64 bit int.
39407c0a41bSMichael Jones // The intended use pattern is to create a FloatToString object of the
39507c0a41bSMichael Jones // appropriate type, then call get_positive_blocks to get an approximate number
39607c0a41bSMichael Jones // of blocks there are before the decimal point. Now the client code can start
39707c0a41bSMichael Jones // calling get_positive_block in a loop from the number of positive blocks to
39807c0a41bSMichael Jones // zero. This will give all digits before the decimal point. Then the user can
39907c0a41bSMichael Jones // start calling get_negative_block in a loop from 0 until the number of digits
40007c0a41bSMichael Jones // they need is reached. As an optimization, the client can use
40107c0a41bSMichael Jones // zero_blocks_after_point to find the number of blocks that are guaranteed to
40207c0a41bSMichael Jones // be zero after the decimal point and before the non-zero digits. Additionally,
40307c0a41bSMichael Jones // is_lowest_block will return if the current block is the lowest non-zero
40407c0a41bSMichael Jones // block.
40507c0a41bSMichael Jones template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
40607c0a41bSMichael Jones class FloatToString {
40707c0a41bSMichael Jones   fputil::FPBits<T> float_bits;
40807c0a41bSMichael Jones   int exponent;
409c09e6905SGuillaume Chatelet   FPBits::StorageType mantissa;
41007c0a41bSMichael Jones 
4113546f4daSGuillaume Chatelet   static constexpr int FRACTION_LEN = fputil::FPBits<T>::FRACTION_LEN;
4123546f4daSGuillaume Chatelet   static constexpr int EXP_BIAS = fputil::FPBits<T>::EXP_BIAS;
41307c0a41bSMichael Jones 
41407c0a41bSMichael Jones public:
415494734b0SSiva Chandra Reddy   LIBC_INLINE constexpr FloatToString(T init_float) : float_bits(init_float) {
416455d6780SMichael Jones     exponent = float_bits.get_explicit_exponent();
41707c0a41bSMichael Jones     mantissa = float_bits.get_explicit_mantissa();
41807c0a41bSMichael Jones 
41907c0a41bSMichael Jones     // Adjust for the width of the mantissa.
4203546f4daSGuillaume Chatelet     exponent -= FRACTION_LEN;
42107c0a41bSMichael Jones   }
42207c0a41bSMichael Jones 
423494734b0SSiva Chandra Reddy   LIBC_INLINE constexpr bool is_nan() { return float_bits.is_nan(); }
424494734b0SSiva Chandra Reddy   LIBC_INLINE constexpr bool is_inf() { return float_bits.is_inf(); }
425494734b0SSiva Chandra Reddy   LIBC_INLINE constexpr bool is_inf_or_nan() {
426494734b0SSiva Chandra Reddy     return float_bits.is_inf_or_nan();
427494734b0SSiva Chandra Reddy   }
42807c0a41bSMichael Jones 
42907c0a41bSMichael Jones   // get_block returns an integer that represents the digits in the requested
43007c0a41bSMichael Jones   // block.
431494734b0SSiva Chandra Reddy   LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {
4323546f4daSGuillaume Chatelet     if (exponent >= -FRACTION_LEN) {
43307c0a41bSMichael Jones       // idx is ceil(exponent/16) or 0 if exponent is negative. This is used to
43407c0a41bSMichael Jones       // find the coarse section of the POW10_SPLIT table that will be used to
43507c0a41bSMichael Jones       // calculate the 9 digit window, as well as some other related values.
43607c0a41bSMichael Jones       const uint32_t idx =
437688b9730SMichael Jones           exponent < 0
438688b9730SMichael Jones               ? 0
439688b9730SMichael Jones               : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
44007c0a41bSMichael Jones 
44107c0a41bSMichael Jones       // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
44207c0a41bSMichael Jones       // exponent
44307c0a41bSMichael Jones 
444a621198aSmichaelrj-google       const uint32_t pos_exp = idx * IDX_SIZE;
445a621198aSmichaelrj-google 
4466a8e6c9aSGuillaume Chatelet       UInt<MID_INT_SIZE> val;
44707c0a41bSMichael Jones 
448688b9730SMichael Jones #if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
449688b9730SMichael Jones       // ----------------------- DYADIC FLOAT CALC MODE ------------------------
450688b9730SMichael Jones       const int32_t SHIFT_CONST = CALC_SHIFT_CONST;
451688b9730SMichael Jones       val = internal::get_table_positive_df<256>(IDX_SIZE * idx, block_index);
452688b9730SMichael Jones #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
453688b9730SMichael Jones 
454688b9730SMichael Jones       // ---------------------------- INT CALC MODE ----------------------------
455688b9730SMichael Jones       const int32_t SHIFT_CONST = CALC_SHIFT_CONST;
456688b9730SMichael Jones       const uint64_t MAX_POW_2_SIZE =
4575bd34e0aSmichaelrj-google           pos_exp + CALC_SHIFT_CONST - (BLOCK_SIZE * block_index);
458688b9730SMichael Jones       const uint64_t MAX_POW_5_SIZE =
459688b9730SMichael Jones           internal::log2_pow5(BLOCK_SIZE * block_index);
460688b9730SMichael Jones       const uint64_t MAX_INT_SIZE =
461688b9730SMichael Jones           (MAX_POW_2_SIZE > MAX_POW_5_SIZE) ? MAX_POW_2_SIZE : MAX_POW_5_SIZE;
462688b9730SMichael Jones 
463688b9730SMichael Jones       if (MAX_INT_SIZE < 1024) {
464688b9730SMichael Jones         val = internal::get_table_positive<1024>(pos_exp, block_index);
465688b9730SMichael Jones       } else if (MAX_INT_SIZE < 2048) {
466688b9730SMichael Jones         val = internal::get_table_positive<2048>(pos_exp, block_index);
467688b9730SMichael Jones       } else if (MAX_INT_SIZE < 4096) {
468688b9730SMichael Jones         val = internal::get_table_positive<4096>(pos_exp, block_index);
469688b9730SMichael Jones       } else if (MAX_INT_SIZE < 8192) {
470688b9730SMichael Jones         val = internal::get_table_positive<8192>(pos_exp, block_index);
4715bd34e0aSmichaelrj-google       } else if (MAX_INT_SIZE < 16384) {
472688b9730SMichael Jones         val = internal::get_table_positive<16384>(pos_exp, block_index);
4735bd34e0aSmichaelrj-google       } else {
4745bd34e0aSmichaelrj-google         val = internal::get_table_positive<16384 + 128>(pos_exp, block_index);
47507c0a41bSMichael Jones       }
476a621198aSmichaelrj-google #else
477a621198aSmichaelrj-google       // ----------------------------- TABLE MODE ------------------------------
478a621198aSmichaelrj-google       const int32_t SHIFT_CONST = TABLE_SHIFT_CONST;
479a621198aSmichaelrj-google 
480a621198aSmichaelrj-google       val = POW10_SPLIT[POW10_OFFSET[idx] + block_index];
481688b9730SMichael Jones #endif
482688b9730SMichael Jones       const uint32_t shift_amount = SHIFT_CONST + pos_exp - exponent;
48307c0a41bSMichael Jones 
48407c0a41bSMichael Jones       const BlockInt digits =
48507c0a41bSMichael Jones           internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));
48607c0a41bSMichael Jones       return digits;
48707c0a41bSMichael Jones     } else {
48807c0a41bSMichael Jones       return 0;
48907c0a41bSMichael Jones     }
49007c0a41bSMichael Jones   }
49107c0a41bSMichael Jones 
492a621198aSmichaelrj-google   LIBC_INLINE constexpr BlockInt get_negative_block(int block_index) {
49307c0a41bSMichael Jones     if (exponent < 0) {
494688b9730SMichael Jones       const int32_t idx = -exponent / IDX_SIZE;
495688b9730SMichael Jones 
4966a8e6c9aSGuillaume Chatelet       UInt<MID_INT_SIZE> val;
497688b9730SMichael Jones 
4988a0ff194Smichaelrj-google       const uint32_t pos_exp = static_cast<uint32_t>(idx * IDX_SIZE);
499a621198aSmichaelrj-google 
500a621198aSmichaelrj-google #if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
501a621198aSmichaelrj-google       // ----------------------- DYADIC FLOAT CALC MODE ------------------------
502a621198aSmichaelrj-google       const int32_t SHIFT_CONST = CALC_SHIFT_CONST;
503a621198aSmichaelrj-google       val = internal::get_table_negative_df<256>(pos_exp, block_index + 1);
504a621198aSmichaelrj-google #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
505a621198aSmichaelrj-google       // ---------------------------- INT CALC MODE ----------------------------
506a621198aSmichaelrj-google       const int32_t SHIFT_CONST = CALC_SHIFT_CONST;
507a621198aSmichaelrj-google 
508a621198aSmichaelrj-google       const uint64_t NUM_FIVES = (block_index + 1) * BLOCK_SIZE;
509a621198aSmichaelrj-google       // Round MAX_INT_SIZE up to the nearest 64 (adding 1 because log2_pow5
510a621198aSmichaelrj-google       // implicitly rounds down).
511a621198aSmichaelrj-google       const uint64_t MAX_INT_SIZE =
512a621198aSmichaelrj-google           ((internal::log2_pow5(NUM_FIVES) / 64) + 1) * 64;
513a621198aSmichaelrj-google 
514a621198aSmichaelrj-google       if (MAX_INT_SIZE < 1024) {
515a621198aSmichaelrj-google         val = internal::get_table_negative<1024>(pos_exp, block_index + 1);
516a621198aSmichaelrj-google       } else if (MAX_INT_SIZE < 2048) {
517a621198aSmichaelrj-google         val = internal::get_table_negative<2048>(pos_exp, block_index + 1);
518a621198aSmichaelrj-google       } else if (MAX_INT_SIZE < 4096) {
519a621198aSmichaelrj-google         val = internal::get_table_negative<4096>(pos_exp, block_index + 1);
520a621198aSmichaelrj-google       } else if (MAX_INT_SIZE < 8192) {
521a621198aSmichaelrj-google         val = internal::get_table_negative<8192>(pos_exp, block_index + 1);
522a621198aSmichaelrj-google       } else if (MAX_INT_SIZE < 16384) {
523a621198aSmichaelrj-google         val = internal::get_table_negative<16384>(pos_exp, block_index + 1);
524a621198aSmichaelrj-google       } else {
525a621198aSmichaelrj-google         val = internal::get_table_negative<16384 + 8192>(pos_exp,
526a621198aSmichaelrj-google                                                          block_index + 1);
527a621198aSmichaelrj-google       }
528a621198aSmichaelrj-google #else
529a621198aSmichaelrj-google       // ----------------------------- TABLE MODE ------------------------------
53007c0a41bSMichael Jones       // if the requested block is zero
531a621198aSmichaelrj-google       const int32_t SHIFT_CONST = TABLE_SHIFT_CONST;
532bfcfc2a6Smichaelrj-google       if (block_index < MIN_BLOCK_2[idx]) {
53307c0a41bSMichael Jones         return 0;
53407c0a41bSMichael Jones       }
535688b9730SMichael Jones       const uint32_t p = POW10_OFFSET_2[idx] + block_index - MIN_BLOCK_2[idx];
53607c0a41bSMichael Jones       // If every digit after the requested block is zero.
53707c0a41bSMichael Jones       if (p >= POW10_OFFSET_2[idx + 1]) {
53807c0a41bSMichael Jones         return 0;
53907c0a41bSMichael Jones       }
540a621198aSmichaelrj-google 
541688b9730SMichael Jones       val = POW10_SPLIT_2[p];
542688b9730SMichael Jones #endif
543ab65c9c3Smichaelrj-google       const int32_t shift_amount =
544a621198aSmichaelrj-google           SHIFT_CONST + (-exponent - static_cast<int32_t>(pos_exp));
545a621198aSmichaelrj-google       BlockInt digits =
546a621198aSmichaelrj-google           internal::mul_shift_mod_1e9(mantissa, val, shift_amount);
54707c0a41bSMichael Jones       return digits;
54807c0a41bSMichael Jones     } else {
54907c0a41bSMichael Jones       return 0;
55007c0a41bSMichael Jones     }
55107c0a41bSMichael Jones   }
55207c0a41bSMichael Jones 
553a621198aSmichaelrj-google   LIBC_INLINE constexpr BlockInt get_block(int block_index) {
554a621198aSmichaelrj-google     if (block_index >= 0) {
555a621198aSmichaelrj-google       return get_positive_block(block_index);
556a621198aSmichaelrj-google     } else {
557a621198aSmichaelrj-google       return get_negative_block(-1 - block_index);
558a621198aSmichaelrj-google     }
559a621198aSmichaelrj-google   }
560a621198aSmichaelrj-google 
561a621198aSmichaelrj-google   LIBC_INLINE constexpr size_t get_positive_blocks() {
562a621198aSmichaelrj-google     if (exponent < -FRACTION_LEN)
563a621198aSmichaelrj-google       return 0;
564a621198aSmichaelrj-google     const uint32_t idx =
565a621198aSmichaelrj-google         exponent < 0
566a621198aSmichaelrj-google             ? 0
567a621198aSmichaelrj-google             : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
568a621198aSmichaelrj-google     return internal::length_for_num(idx * IDX_SIZE, FRACTION_LEN);
569a621198aSmichaelrj-google   }
570a621198aSmichaelrj-google 
571a621198aSmichaelrj-google   // This takes the index of a block after the decimal point (a negative block)
572a621198aSmichaelrj-google   // and return if it's sure that all of the digits after it are zero.
573a621198aSmichaelrj-google   LIBC_INLINE constexpr bool is_lowest_block(size_t negative_block_index) {
574a621198aSmichaelrj-google #ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE
575a621198aSmichaelrj-google     // The decimal representation of 2**(-i) will have exactly i digits after
576a621198aSmichaelrj-google     // the decimal point.
577a621198aSmichaelrj-google     int num_requested_digits =
578a621198aSmichaelrj-google         static_cast<int>((negative_block_index + 1) * BLOCK_SIZE);
579a621198aSmichaelrj-google 
580a621198aSmichaelrj-google     return num_requested_digits > -exponent;
581a621198aSmichaelrj-google #else
582a621198aSmichaelrj-google     const int32_t idx = -exponent / IDX_SIZE;
583a621198aSmichaelrj-google     const size_t p =
584a621198aSmichaelrj-google         POW10_OFFSET_2[idx] + negative_block_index - MIN_BLOCK_2[idx];
585a621198aSmichaelrj-google     // If the remaining digits are all 0, then this is the lowest block.
586a621198aSmichaelrj-google     return p >= POW10_OFFSET_2[idx + 1];
587a621198aSmichaelrj-google #endif
588a621198aSmichaelrj-google   }
589a621198aSmichaelrj-google 
590a621198aSmichaelrj-google   LIBC_INLINE constexpr size_t zero_blocks_after_point() {
591a621198aSmichaelrj-google #ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE
592a621198aSmichaelrj-google     if (exponent < -FRACTION_LEN) {
593a621198aSmichaelrj-google       const int pos_exp = -exponent - 1;
594a621198aSmichaelrj-google       const uint32_t pos_idx =
595a621198aSmichaelrj-google           static_cast<uint32_t>(pos_exp + (IDX_SIZE - 1)) / IDX_SIZE;
596a621198aSmichaelrj-google       const int32_t pos_len = ((internal::ceil_log10_pow2(pos_idx * IDX_SIZE) -
597a621198aSmichaelrj-google                                 internal::ceil_log10_pow2(FRACTION_LEN + 1)) /
598a621198aSmichaelrj-google                                BLOCK_SIZE) -
599a621198aSmichaelrj-google                               1;
600a621198aSmichaelrj-google       return static_cast<uint32_t>(pos_len > 0 ? pos_len : 0);
601a621198aSmichaelrj-google     }
602a621198aSmichaelrj-google     return 0;
603a621198aSmichaelrj-google #else
604a621198aSmichaelrj-google     return MIN_BLOCK_2[-exponent / IDX_SIZE];
605a621198aSmichaelrj-google #endif
606a621198aSmichaelrj-google   }
607a621198aSmichaelrj-google };
608a621198aSmichaelrj-google 
609f7d4236aSGuillaume Chatelet #if !defined(LIBC_TYPES_LONG_DOUBLE_IS_FLOAT64) &&                             \
610a621198aSmichaelrj-google     !defined(LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD)
611a621198aSmichaelrj-google // --------------------------- LONG DOUBLE FUNCTIONS ---------------------------
612a621198aSmichaelrj-google 
613a621198aSmichaelrj-google // this algorithm will work exactly the same for 80 bit and 128 bit long
614a621198aSmichaelrj-google // doubles. They have the same max exponent, but even if they didn't the
615a621198aSmichaelrj-google // constants should be calculated to be correct for any provided floating point
616a621198aSmichaelrj-google // type.
617a621198aSmichaelrj-google 
618a621198aSmichaelrj-google template <> class FloatToString<long double> {
619a621198aSmichaelrj-google   fputil::FPBits<long double> float_bits;
620a621198aSmichaelrj-google   bool is_negative = 0;
621a621198aSmichaelrj-google   int exponent = 0;
622a621198aSmichaelrj-google   FPBits::StorageType mantissa = 0;
623a621198aSmichaelrj-google 
624a621198aSmichaelrj-google   static constexpr int FRACTION_LEN = fputil::FPBits<long double>::FRACTION_LEN;
625a621198aSmichaelrj-google   static constexpr int EXP_BIAS = fputil::FPBits<long double>::EXP_BIAS;
626a621198aSmichaelrj-google   static constexpr size_t UINT_WORD_SIZE = 64;
627a621198aSmichaelrj-google 
628a621198aSmichaelrj-google   static constexpr size_t FLOAT_AS_INT_WIDTH =
629a621198aSmichaelrj-google       internal::div_ceil(fputil::FPBits<long double>::MAX_BIASED_EXPONENT -
630a621198aSmichaelrj-google                              FPBits::EXP_BIAS,
631a621198aSmichaelrj-google                          UINT_WORD_SIZE) *
632a621198aSmichaelrj-google       UINT_WORD_SIZE;
633a621198aSmichaelrj-google   static constexpr size_t EXTRA_INT_WIDTH =
634a621198aSmichaelrj-google       internal::div_ceil(sizeof(long double) * CHAR_BIT, UINT_WORD_SIZE) *
635a621198aSmichaelrj-google       UINT_WORD_SIZE;
636a621198aSmichaelrj-google 
6376a8e6c9aSGuillaume Chatelet   using wide_int = UInt<FLOAT_AS_INT_WIDTH + EXTRA_INT_WIDTH>;
638a621198aSmichaelrj-google 
639a621198aSmichaelrj-google   // float_as_fixed represents the floating point number as a fixed point number
640a621198aSmichaelrj-google   // with the point EXTRA_INT_WIDTH bits from the left of the number. This can
641a621198aSmichaelrj-google   // store any number with a negative exponent.
642a621198aSmichaelrj-google   wide_int float_as_fixed = 0;
643a621198aSmichaelrj-google   int int_block_index = 0;
644a621198aSmichaelrj-google 
645a621198aSmichaelrj-google   static constexpr size_t BLOCK_BUFFER_LEN =
6466812bc40Smichaelrj-google       internal::div_ceil(internal::log10_pow2(FLOAT_AS_INT_WIDTH), BLOCK_SIZE) +
6476812bc40Smichaelrj-google       1;
648a621198aSmichaelrj-google   BlockInt block_buffer[BLOCK_BUFFER_LEN] = {0};
649a621198aSmichaelrj-google   size_t block_buffer_valid = 0;
650a621198aSmichaelrj-google 
651a621198aSmichaelrj-google   template <size_t Bits>
6526a8e6c9aSGuillaume Chatelet   LIBC_INLINE static constexpr BlockInt grab_digits(UInt<Bits> &int_num) {
6534e005515Slntue     auto wide_result = int_num.div_uint_half_times_pow_2(EXP5_9, 9);
654a621198aSmichaelrj-google     // the optional only comes into effect when dividing by 0, which will
655a621198aSmichaelrj-google     // never happen here. Thus, we just assert that it has value.
656a621198aSmichaelrj-google     LIBC_ASSERT(wide_result.has_value());
657a621198aSmichaelrj-google     return static_cast<BlockInt>(wide_result.value());
658a621198aSmichaelrj-google   }
659a621198aSmichaelrj-google 
660a621198aSmichaelrj-google   LIBC_INLINE static constexpr void zero_leading_digits(wide_int &int_num) {
661a621198aSmichaelrj-google     // WORD_SIZE is the width of the numbers used to internally represent the
662a621198aSmichaelrj-google     // UInt
663a621198aSmichaelrj-google     for (size_t i = 0; i < EXTRA_INT_WIDTH / wide_int::WORD_SIZE; ++i)
664a621198aSmichaelrj-google       int_num[i + (FLOAT_AS_INT_WIDTH / wide_int::WORD_SIZE)] = 0;
665a621198aSmichaelrj-google   }
666a621198aSmichaelrj-google 
667a621198aSmichaelrj-google   // init_convert initializes float_as_int, cur_block, and block_buffer based on
668a621198aSmichaelrj-google   // the mantissa and exponent of the initial number. Calling it will always
669a621198aSmichaelrj-google   // return the class to the starting state.
670a621198aSmichaelrj-google   LIBC_INLINE constexpr void init_convert() {
671a621198aSmichaelrj-google     // No calculation necessary for the 0 case.
672a621198aSmichaelrj-google     if (mantissa == 0 && exponent == 0)
673a621198aSmichaelrj-google       return;
674a621198aSmichaelrj-google 
675a621198aSmichaelrj-google     if (exponent > 0) {
676a621198aSmichaelrj-google       // if the exponent is positive, then the number is fully above the decimal
677a621198aSmichaelrj-google       // point. In this case we represent the float as an integer, then divide
678a621198aSmichaelrj-google       // by 10^BLOCK_SIZE and take the remainder as our next block. This
679a621198aSmichaelrj-google       // generates the digits from right to left, but the digits will be written
680a621198aSmichaelrj-google       // from left to right, so it caches the results so they can be read in
681a621198aSmichaelrj-google       // reverse order.
682a621198aSmichaelrj-google 
683a621198aSmichaelrj-google       wide_int float_as_int = mantissa;
684a621198aSmichaelrj-google 
68571c3f5d6SGuillaume Chatelet       float_as_int <<= exponent;
686a621198aSmichaelrj-google       int_block_index = 0;
687a621198aSmichaelrj-google 
688a621198aSmichaelrj-google       while (float_as_int > 0) {
6896812bc40Smichaelrj-google         LIBC_ASSERT(int_block_index < static_cast<int>(BLOCK_BUFFER_LEN));
6904e005515Slntue         block_buffer[int_block_index] =
6914e005515Slntue             grab_digits<FLOAT_AS_INT_WIDTH + EXTRA_INT_WIDTH>(float_as_int);
692a621198aSmichaelrj-google         ++int_block_index;
693a621198aSmichaelrj-google       }
694a621198aSmichaelrj-google       block_buffer_valid = int_block_index;
695a621198aSmichaelrj-google 
696a621198aSmichaelrj-google     } else {
697a621198aSmichaelrj-google       // if the exponent is not positive, then the number is at least partially
698a621198aSmichaelrj-google       // below the decimal point. In this case we represent the float as a fixed
699a621198aSmichaelrj-google       // point number with the decimal point after the top EXTRA_INT_WIDTH bits.
700a621198aSmichaelrj-google       float_as_fixed = mantissa;
701a621198aSmichaelrj-google 
702a621198aSmichaelrj-google       const int SHIFT_AMOUNT = FLOAT_AS_INT_WIDTH + exponent;
703a621198aSmichaelrj-google       static_assert(EXTRA_INT_WIDTH >= sizeof(long double) * 8);
70471c3f5d6SGuillaume Chatelet       float_as_fixed <<= SHIFT_AMOUNT;
705a621198aSmichaelrj-google 
706a621198aSmichaelrj-google       // If there are still digits above the decimal point, handle those.
70771c3f5d6SGuillaume Chatelet       if (cpp::countl_zero(float_as_fixed) <
70871c3f5d6SGuillaume Chatelet           static_cast<int>(EXTRA_INT_WIDTH)) {
7096a8e6c9aSGuillaume Chatelet         UInt<EXTRA_INT_WIDTH> above_decimal_point =
710a621198aSmichaelrj-google             float_as_fixed >> FLOAT_AS_INT_WIDTH;
711a621198aSmichaelrj-google 
712a621198aSmichaelrj-google         size_t positive_int_block_index = 0;
713a621198aSmichaelrj-google         while (above_decimal_point > 0) {
714a621198aSmichaelrj-google           block_buffer[positive_int_block_index] =
7154e005515Slntue               grab_digits<EXTRA_INT_WIDTH>(above_decimal_point);
716a621198aSmichaelrj-google           ++positive_int_block_index;
717a621198aSmichaelrj-google         }
718a621198aSmichaelrj-google         block_buffer_valid = positive_int_block_index;
719a621198aSmichaelrj-google 
720a621198aSmichaelrj-google         // Zero all digits above the decimal point.
721a621198aSmichaelrj-google         zero_leading_digits(float_as_fixed);
722a621198aSmichaelrj-google         int_block_index = 0;
723a621198aSmichaelrj-google       }
724a621198aSmichaelrj-google     }
725a621198aSmichaelrj-google   }
726a621198aSmichaelrj-google 
727a621198aSmichaelrj-google public:
728a621198aSmichaelrj-google   LIBC_INLINE constexpr FloatToString(long double init_float)
729a621198aSmichaelrj-google       : float_bits(init_float) {
730a621198aSmichaelrj-google     is_negative = float_bits.is_neg();
731a621198aSmichaelrj-google     exponent = float_bits.get_explicit_exponent();
732a621198aSmichaelrj-google     mantissa = float_bits.get_explicit_mantissa();
733a621198aSmichaelrj-google 
734a621198aSmichaelrj-google     // Adjust for the width of the mantissa.
735a621198aSmichaelrj-google     exponent -= FRACTION_LEN;
736a621198aSmichaelrj-google 
737a621198aSmichaelrj-google     this->init_convert();
738a621198aSmichaelrj-google   }
739a621198aSmichaelrj-google 
740a621198aSmichaelrj-google   LIBC_INLINE constexpr size_t get_positive_blocks() {
741a621198aSmichaelrj-google     if (exponent < -FRACTION_LEN)
742a621198aSmichaelrj-google       return 0;
743a621198aSmichaelrj-google 
744a621198aSmichaelrj-google     const uint32_t idx =
745a621198aSmichaelrj-google         exponent < 0
746a621198aSmichaelrj-google             ? 0
747a621198aSmichaelrj-google             : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
748a621198aSmichaelrj-google     return internal::length_for_num(idx * IDX_SIZE, FRACTION_LEN);
749a621198aSmichaelrj-google   }
750a621198aSmichaelrj-google 
751a621198aSmichaelrj-google   LIBC_INLINE constexpr size_t zero_blocks_after_point() {
752a621198aSmichaelrj-google #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
753a621198aSmichaelrj-google     return MIN_BLOCK_2[-exponent / IDX_SIZE];
754a621198aSmichaelrj-google #else
755a621198aSmichaelrj-google     if (exponent >= -FRACTION_LEN)
756a621198aSmichaelrj-google       return 0;
757a621198aSmichaelrj-google 
758a621198aSmichaelrj-google     const int pos_exp = -exponent - 1;
759a621198aSmichaelrj-google     const uint32_t pos_idx =
760a621198aSmichaelrj-google         static_cast<uint32_t>(pos_exp + (IDX_SIZE - 1)) / IDX_SIZE;
761a621198aSmichaelrj-google     const int32_t pos_len = ((internal::ceil_log10_pow2(pos_idx * IDX_SIZE) -
762a621198aSmichaelrj-google                               internal::ceil_log10_pow2(FRACTION_LEN + 1)) /
763a621198aSmichaelrj-google                              BLOCK_SIZE) -
764a621198aSmichaelrj-google                             1;
765a621198aSmichaelrj-google     return static_cast<uint32_t>(pos_len > 0 ? pos_len : 0);
766a621198aSmichaelrj-google #endif
767a621198aSmichaelrj-google   }
768a621198aSmichaelrj-google 
769a621198aSmichaelrj-google   LIBC_INLINE constexpr bool is_lowest_block(size_t negative_block_index) {
770a621198aSmichaelrj-google     // The decimal representation of 2**(-i) will have exactly i digits after
771a621198aSmichaelrj-google     // the decimal point.
772a621198aSmichaelrj-google     const int num_requested_digits =
773a621198aSmichaelrj-google         static_cast<int>((negative_block_index + 1) * BLOCK_SIZE);
774a621198aSmichaelrj-google 
775a621198aSmichaelrj-google     return num_requested_digits > -exponent;
776a621198aSmichaelrj-google   }
777a621198aSmichaelrj-google 
778a621198aSmichaelrj-google   LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {
779a621198aSmichaelrj-google     if (exponent < -FRACTION_LEN)
780a621198aSmichaelrj-google       return 0;
781a621198aSmichaelrj-google     if (block_index > static_cast<int>(block_buffer_valid) || block_index < 0)
782a621198aSmichaelrj-google       return 0;
783a621198aSmichaelrj-google 
7846812bc40Smichaelrj-google     LIBC_ASSERT(block_index < static_cast<int>(BLOCK_BUFFER_LEN));
7856812bc40Smichaelrj-google 
786a621198aSmichaelrj-google     return block_buffer[block_index];
787a621198aSmichaelrj-google   }
788a621198aSmichaelrj-google 
789a621198aSmichaelrj-google   LIBC_INLINE constexpr BlockInt get_negative_block(int negative_block_index) {
790a621198aSmichaelrj-google     if (exponent >= 0)
791a621198aSmichaelrj-google       return 0;
792a621198aSmichaelrj-google 
793a621198aSmichaelrj-google     // negative_block_index starts at 0 with the first block after the decimal
794a621198aSmichaelrj-google     // point, and 1 with the second and so on. This converts to the same
795a621198aSmichaelrj-google     // block_index used everywhere else.
796a621198aSmichaelrj-google 
797a621198aSmichaelrj-google     const int block_index = -1 - negative_block_index;
798a621198aSmichaelrj-google 
799a621198aSmichaelrj-google     // If we're currently after the requested block (remember these are
800a621198aSmichaelrj-google     // negative indices) we reset the number to the start. This is only
801a621198aSmichaelrj-google     // likely to happen in %g calls. This will also reset int_block_index.
802a621198aSmichaelrj-google     // if (block_index > int_block_index) {
803a621198aSmichaelrj-google     //   init_convert();
804a621198aSmichaelrj-google     // }
805a621198aSmichaelrj-google 
806a621198aSmichaelrj-google     // Printf is the only existing user of this code and it will only ever move
807a621198aSmichaelrj-google     // downwards, except for %g but that currently creates a second
808a621198aSmichaelrj-google     // float_to_string object so this assertion still holds. If a new user needs
809a621198aSmichaelrj-google     // the ability to step backwards, uncomment the code above.
810a621198aSmichaelrj-google     LIBC_ASSERT(block_index <= int_block_index);
811a621198aSmichaelrj-google 
812a621198aSmichaelrj-google     // If we are currently before the requested block. Step until we reach the
813a621198aSmichaelrj-google     // requested block. This is likely to only be one step.
814a621198aSmichaelrj-google     while (block_index < int_block_index) {
815a621198aSmichaelrj-google       zero_leading_digits(float_as_fixed);
816a621198aSmichaelrj-google       float_as_fixed.mul(EXP10_9);
817a621198aSmichaelrj-google       --int_block_index;
818a621198aSmichaelrj-google     }
819a621198aSmichaelrj-google 
820a621198aSmichaelrj-google     // We're now on the requested block, return the current block.
821a621198aSmichaelrj-google     return static_cast<BlockInt>(float_as_fixed >> FLOAT_AS_INT_WIDTH);
822a621198aSmichaelrj-google   }
823a621198aSmichaelrj-google 
824a621198aSmichaelrj-google   LIBC_INLINE constexpr BlockInt get_block(int block_index) {
825a621198aSmichaelrj-google     if (block_index >= 0)
826a621198aSmichaelrj-google       return get_positive_block(block_index);
827a621198aSmichaelrj-google 
828a621198aSmichaelrj-google     return get_negative_block(-1 - block_index);
829a621198aSmichaelrj-google   }
830a621198aSmichaelrj-google };
831a621198aSmichaelrj-google 
832f7d4236aSGuillaume Chatelet #endif // !LIBC_TYPES_LONG_DOUBLE_IS_FLOAT64 &&
833a621198aSmichaelrj-google        // !LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD
834688b9730SMichael Jones 
8355ff3ff33SPetr Hosek } // namespace LIBC_NAMESPACE_DECL
83607c0a41bSMichael Jones 
837270547f3SGuillaume Chatelet #endif // LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H
838