1 //===-- Utilities to convert floating point values to string ----*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
10 #define LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
14 #include "src/__support/CPP/type_traits.h"
15 #include "src/__support/FPUtil/FPBits.h"
16 #include "src/__support/FPUtil/dyadic_float.h"
17 #include "src/__support/UInt.h"
18 #include "src/__support/common.h"
19 #include "src/__support/libc_assert.h"
21 // This file has 5 compile-time flags to allow the user to configure the float
22 // to string behavior. These allow the user to select which 2 of the 3 useful
23 // properties they want. The useful properties are:
24 // 1) Speed of Evaluation
25 // 2) Small Size of Binary
26 // 3) Centered Output Value
27 // These are explained below with the flags that are missing each one.
29 // LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
30 // The Mega Table is ~5 megabytes when compiled. It lists the constants needed
31 // to perform the Ryu Printf algorithm (described below) for all long double
32 // values. This makes it extremely fast for both doubles and long doubles, in
33 // exchange for large binary size.
35 // LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT
36 // LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD
37 // Dyadic floats are software floating point numbers, and their accuracy can be
38 // as high as necessary. This option uses 256 bit dyadic floats to calculate
39 // the table values that Ryu Printf needs. This is reasonably fast and very
40 // small compared to the Mega Table, but the 256 bit floats only give accurate
41 // results for the first ~50 digits of the output. In practice this shouldn't
42 // be a problem since long doubles are only accurate for ~35 digits, but the
43 // trailing values all being 0s may cause brittle tests to fail. The _LD
44 // version of this flag only effects the long double calculations, and the
45 // other version effects both long double and double.
47 // LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC
48 // Integer Calculation uses wide integers to do the calculations for the Ryu
49 // Printf table, which is just as accurate as the Mega Table without requiring
50 // as much code size. These integers can be very large (~32KB at max, though
51 // always on the stack) to handle the edges of the long double range. They are
52 // also very slow, taking multiple seconds on a powerful CPU to calculate the
53 // values at the end of the range. If no flag is set, this is used for long
54 // doubles, the flag only changes the double behavior.
56 // LIBC_COPT_FLOAT_TO_STR_NO_TABLE
57 // This flag doesn't change the actual calculation method, instead it is used
58 // to disable the normal Ryu Printf table for configurations that don't use any
62 // If no flags are set, doubles use the normal (and much more reasonably sized)
63 // Ryu Printf table and long doubles use Integer Calculation. This is because
64 // long doubles are rarely used and the normal Ryu Printf table is very fast
67 #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
68 #include "src/__support/ryu_long_double_constants.h"
69 #elif !defined(LIBC_COPT_FLOAT_TO_STR_NO_TABLE)
70 #include "src/__support/ryu_constants.h"
72 constexpr size_t IDX_SIZE
= 1;
73 constexpr size_t MID_INT_SIZE
= 192;
76 // This implementation is based on the Ryu Printf algorithm by Ulf Adams:
77 // Ulf Adams. 2019. Ryƫ revisited: printf floating point conversion.
78 // Proc. ACM Program. Lang. 3, OOPSLA, Article 169 (October 2019), 23 pages.
79 // https://doi.org/10.1145/3360595
81 // This version is modified to require significantly less memory (it doesn't use
82 // a large buffer to store the result).
84 // The general concept of this algorithm is as follows:
85 // We want to calculate a 9 digit segment of a floating point number using this
86 // formula: floor((mantissa * 2^exponent)/10^i) % 10^9.
87 // To do so normally would involve large integers (~1000 bits for doubles), so
88 // we use a shortcut. We can avoid calculating 2^exponent / 10^i by using a
89 // lookup table. The resulting intermediate value needs to be about 192 bits to
90 // store the result with enough precision. Since this is all being done with
91 // integers for appropriate precision, we would run into a problem if
92 // i > exponent since then 2^exponent / 10^i would be less than 1. To correct
93 // for this, the actual calculation done is 2^(exponent + c) / 10^i, and then
94 // when multiplying by the mantissa we reverse this by dividing by 2^c, like so:
95 // floor((mantissa * table[exponent][i])/(2^c)) % 10^9.
96 // This gives a 9 digit value, which is small enough to fit in a 32 bit integer,
97 // and that integer is converted into a string as normal, and called a block. In
98 // this implementation, the most recent block is buffered, so that if rounding
99 // is necessary the block can be adjusted before being written to the output.
100 // Any block that is all 9s adds one to the max block counter and doesn't clear
101 // the buffer because they can cause the block above them to be rounded up.
103 namespace __llvm_libc
{
105 using BlockInt
= uint32_t;
106 constexpr size_t BLOCK_SIZE
= 9;
108 using MantissaInt
= fputil::FPBits
<long double>::UIntType
;
110 // Larger numbers prefer a slightly larger constant than is used for the smaller
112 constexpr size_t CALC_SHIFT_CONST
= 128;
116 // Returns floor(log_10(2^e)); requires 0 <= e <= 42039.
117 LIBC_INLINE
constexpr uint32_t log10_pow2(const uint64_t e
) {
118 LIBC_ASSERT(e
>= 0 && e
<= 42039 &&
119 "Incorrect exponent to perform log10_pow2 approximation.");
120 // This approximation is based on the float value for log_10(2). It first
121 // gives an incorrect result for our purposes at 42039 (well beyond the 16383
122 // maximum for long doubles).
124 // To get these constants I first evaluated log_10(2) to get an approximation
125 // of 0.301029996. Next I passed that value through a string to double
126 // conversion to get an explicit mantissa of 0x13441350fbd738 and an exponent
127 // of -2 (which becomes -54 when we shift the mantissa to be a non-fractional
128 // number). Next I shifted the mantissa right 12 bits to create more space for
129 // the multiplication result, adding 12 to the exponent to compensate. To
130 // check that this approximation works for our purposes I used the following
132 // for i in range(16384):
133 // if(len(str(2**i)) != (((i*0x13441350fbd)>>42)+1)):
135 // The reason we add 1 is because this evaluation truncates the result, giving
136 // us the floor, whereas counting the digits of the power of 2 gives us the
137 // ceiling. With a similar loop I checked the maximum valid value and found
139 return (e
* 0x13441350fbdll
) >> 42;
142 // Same as above, but with different constants.
143 LIBC_INLINE
constexpr uint32_t log2_pow5(const uint64_t e
) {
144 return (e
* 0x12934f0979bll
) >> 39;
147 // Returns 1 + floor(log_10(2^e). This could technically be off by 1 if any
148 // power of 2 was also a power of 10, but since that doesn't exist this is
149 // always accurate. This is used to calculate the maximum number of base-10
150 // digits a given e-bit number could have.
151 LIBC_INLINE
constexpr uint32_t ceil_log10_pow2(const uint32_t e
) {
152 return log10_pow2(e
) + 1;
155 // Returns the maximum number of 9 digit blocks a number described by the given
156 // index (which is ceil(exponent/16)) and mantissa width could need.
157 LIBC_INLINE
constexpr uint32_t length_for_num(const uint32_t idx
,
158 const uint32_t mantissa_width
) {
159 //+8 to round up when dividing by 9
160 return (ceil_log10_pow2(idx
) + ceil_log10_pow2(mantissa_width
) +
163 // return (ceil_log10_pow2(16 * idx + mantissa_width) + 8) / 9;
166 // The formula for the table when i is positive (or zero) is as follows:
167 // floor(10^(-9i) * 2^(e + c_1) + 1) % (10^9 * 2^c_1)
168 // Rewritten slightly we get:
169 // floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)
171 // TODO: Fix long doubles (needs bigger table or alternate algorithm.)
172 // Currently the table values are generated, which is very slow.
173 template <size_t INT_SIZE
>
174 LIBC_INLINE
constexpr cpp::UInt
<MID_INT_SIZE
> get_table_positive(int exponent
,
176 // INT_SIZE is the size of int that is used for the internal calculations of
177 // this function. It should be large enough to hold 2^(exponent+constant), so
178 // ~1000 for double and ~16000 for long double. Be warned that the time
179 // complexity of exponentiation is O(n^2 * log_2(m)) where n is the number of
180 // bits in the number being exponentiated and m is the exponent.
181 const int shift_amount
= exponent
+ CALC_SHIFT_CONST
- (BLOCK_SIZE
* i
);
182 if (shift_amount
< 0) {
185 cpp::UInt
<INT_SIZE
> num(0);
186 // MOD_SIZE is one of the limiting factors for how big the constant argument
187 // can get, since it needs to be small enough to fit in the result UInt,
188 // otherwise we'll get truncation on return.
189 constexpr cpp::UInt
<INT_SIZE
> MOD_SIZE
=
190 (cpp::UInt
<INT_SIZE
>(1000000000)
191 << (CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0)));
193 constexpr uint64_t FIVE_EXP_NINE
= 1953125;
195 num
= cpp::UInt
<INT_SIZE
>(1) << (shift_amount
);
197 cpp::UInt
<INT_SIZE
> fives(FIVE_EXP_NINE
);
203 if (num
> MOD_SIZE
) {
205 num
.div_uint32_times_pow_2(
206 1000000000, CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0))
213 template <size_t INT_SIZE
>
214 LIBC_INLINE
cpp::UInt
<MID_INT_SIZE
> get_table_positive_df(int exponent
,
216 static_assert(INT_SIZE
== 256,
217 "Only 256 is supported as an int size right now.");
218 // This version uses dyadic floats with 256 bit mantissas to perform the same
219 // calculation as above. Due to floating point imprecision it is only accurate
220 // for the first 50 digits, but it's much faster. Since even 128 bit long
221 // doubles are only accurate to ~35 digits, the 50 digits of accuracy are
222 // enough for these floats to be converted back and forth safely. This is
223 // ideal for avoiding the size of the long double table.
224 const int shift_amount
= exponent
+ CALC_SHIFT_CONST
- (9 * i
);
225 if (shift_amount
< 0) {
228 fputil::DyadicFloat
<INT_SIZE
> num(false, 0, 1);
229 constexpr cpp::UInt
<INT_SIZE
> MOD_SIZE
=
230 (cpp::UInt
<INT_SIZE
>(1000000000)
231 << (CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0)));
233 constexpr cpp::UInt
<INT_SIZE
> FIVE_EXP_MINUS_NINE_MANT
{
234 {0xf387295d242602a7, 0xfdd7645e011abac9, 0x31680a88f8953030,
235 0x89705f4136b4a597}};
237 static const fputil::DyadicFloat
<INT_SIZE
> FIVE_EXP_MINUS_NINE(
238 false, -276, FIVE_EXP_MINUS_NINE_MANT
);
241 fputil::DyadicFloat
<INT_SIZE
> fives
= fputil::pow_n(FIVE_EXP_MINUS_NINE
, i
);
244 num
= mul_pow_2(num
, shift_amount
);
246 // Adding one is part of the formula.
247 cpp::UInt
<INT_SIZE
> int_num
= static_cast<cpp::UInt
<INT_SIZE
>>(num
) + 1;
248 if (int_num
> MOD_SIZE
) {
251 .div_uint32_times_pow_2(
252 1000000000, CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0))
257 cpp::UInt
<MID_INT_SIZE
> result
= int_num
;
262 // The formula for the table when i is negative (or zero) is as follows:
263 // floor(10^(-9i) * 2^(c_0 - e)) % (10^9 * 2^c_0)
264 // Since we know i is always negative, we just take it as unsigned and treat it
265 // as negative. We do the same with exponent, while they're both always negative
266 // in theory, in practice they're converted to positive for simpler
268 // The formula being used looks more like this:
269 // floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
270 template <size_t INT_SIZE
>
271 LIBC_INLINE
cpp::UInt
<MID_INT_SIZE
> get_table_negative(int exponent
, size_t i
) {
272 int shift_amount
= CALC_SHIFT_CONST
- exponent
;
273 cpp::UInt
<INT_SIZE
> num(1);
274 constexpr cpp::UInt
<INT_SIZE
> MOD_SIZE
=
275 (cpp::UInt
<INT_SIZE
>(1000000000)
276 << (CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0)));
278 constexpr uint64_t TEN_EXP_NINE
= 1000000000;
279 constexpr uint64_t FIVE_EXP_NINE
= 1953125;
280 size_t ten_blocks
= i
;
281 size_t five_blocks
= 0;
282 if (shift_amount
< 0) {
283 int block_shifts
= (-shift_amount
) / BLOCK_SIZE
;
284 if (block_shifts
< static_cast<int>(ten_blocks
)) {
285 ten_blocks
= ten_blocks
- block_shifts
;
286 five_blocks
= block_shifts
;
287 shift_amount
= shift_amount
+ (block_shifts
* BLOCK_SIZE
);
291 shift_amount
= shift_amount
+ (i
* BLOCK_SIZE
);
295 if (five_blocks
> 0) {
296 cpp::UInt
<INT_SIZE
> fives(FIVE_EXP_NINE
);
297 fives
.pow_n(five_blocks
);
300 if (ten_blocks
> 0) {
301 cpp::UInt
<INT_SIZE
> tens(TEN_EXP_NINE
);
302 tens
.pow_n(ten_blocks
);
303 if (five_blocks
<= 0) {
310 if (shift_amount
> 0) {
311 num
= num
<< shift_amount
;
313 num
= num
>> (-shift_amount
);
315 if (num
> MOD_SIZE
) {
317 num
.div_uint32_times_pow_2(
318 1000000000, CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0))
325 template <size_t INT_SIZE
>
326 LIBC_INLINE
cpp::UInt
<MID_INT_SIZE
> get_table_negative_df(int exponent
,
328 static_assert(INT_SIZE
== 256,
329 "Only 256 is supported as an int size right now.");
330 // This version uses dyadic floats with 256 bit mantissas to perform the same
331 // calculation as above. Due to floating point imprecision it is only accurate
332 // for the first 50 digits, but it's much faster. Since even 128 bit long
333 // doubles are only accurate to ~35 digits, the 50 digits of accuracy are
334 // enough for these floats to be converted back and forth safely. This is
335 // ideal for avoiding the size of the long double table.
337 int shift_amount
= CALC_SHIFT_CONST
- exponent
;
339 fputil::DyadicFloat
<INT_SIZE
> num(false, 0, 1);
340 constexpr cpp::UInt
<INT_SIZE
> MOD_SIZE
=
341 (cpp::UInt
<INT_SIZE
>(1000000000)
342 << (CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0)));
344 constexpr cpp::UInt
<INT_SIZE
> TEN_EXP_NINE_MANT(1000000000);
346 static const fputil::DyadicFloat
<INT_SIZE
> TEN_EXP_NINE(false, 0,
350 fputil::DyadicFloat
<INT_SIZE
> tens
= fputil::pow_n(TEN_EXP_NINE
, i
);
353 num
= mul_pow_2(num
, shift_amount
);
355 cpp::UInt
<INT_SIZE
> int_num
= static_cast<cpp::UInt
<INT_SIZE
>>(num
);
356 if (int_num
> MOD_SIZE
) {
359 .div_uint32_times_pow_2(
360 1000000000, CALC_SHIFT_CONST
+ (IDX_SIZE
> 1 ? IDX_SIZE
: 0))
365 cpp::UInt
<MID_INT_SIZE
> result
= int_num
;
370 LIBC_INLINE
uint32_t fast_uint_mod_1e9(const cpp::UInt
<MID_INT_SIZE
> &val
) {
371 // The formula for mult_const is:
372 // 1 + floor((2^(bits in target integer size + log_2(divider))) / divider)
373 // Where divider is 10^9 and target integer size is 128.
374 const cpp::UInt
<MID_INT_SIZE
> mult_const(
375 {0x31680A88F8953031u
, 0x89705F4136B4A597u
, 0});
376 const auto middle
= (mult_const
* val
);
377 const uint64_t result
= static_cast<uint64_t>(middle
[2]);
378 const uint32_t shifted
= result
>> 29;
379 return static_cast<uint32_t>(val
) - (1000000000 * shifted
);
382 LIBC_INLINE
uint32_t mul_shift_mod_1e9(const MantissaInt mantissa
,
383 const cpp::UInt
<MID_INT_SIZE
> &large
,
384 const int32_t shift_amount
) {
385 constexpr size_t MANT_INT_SIZE
= sizeof(MantissaInt
) * 8;
386 cpp::UInt
<MID_INT_SIZE
+ MANT_INT_SIZE
> val(large
);
387 // TODO: Find a better way to force __uint128_t to be UInt<128>
388 cpp::UInt
<MANT_INT_SIZE
> wide_mant(0);
389 wide_mant
[0] = static_cast<size_t>(mantissa
& (uint64_t(-1)));
390 wide_mant
[1] = static_cast<size_t>(mantissa
>> 64);
391 val
= (val
* wide_mant
) >> shift_amount
;
393 return val
.div_uint32_times_pow_2(1000000000, 0).value()[0];
394 // return fast_uint_mod_1e9(val);
397 } // namespace internal
399 // Convert floating point values to their string representation.
400 // Because the result may not fit in a reasonably sized array, the caller must
401 // request blocks of digits and convert them from integers to strings themself.
402 // Blocks contain the most digits that can be stored in an BlockInt. This is 9
403 // digits for a 32 bit int and 18 digits for a 64 bit int.
404 // The intended use pattern is to create a FloatToString object of the
405 // appropriate type, then call get_positive_blocks to get an approximate number
406 // of blocks there are before the decimal point. Now the client code can start
407 // calling get_positive_block in a loop from the number of positive blocks to
408 // zero. This will give all digits before the decimal point. Then the user can
409 // start calling get_negative_block in a loop from 0 until the number of digits
410 // they need is reached. As an optimization, the client can use
411 // zero_blocks_after_point to find the number of blocks that are guaranteed to
412 // be zero after the decimal point and before the non-zero digits. Additionally,
413 // is_lowest_block will return if the current block is the lowest non-zero
415 template <typename T
, cpp::enable_if_t
<cpp::is_floating_point_v
<T
>, int> = 0>
416 class FloatToString
{
417 fputil::FPBits
<T
> float_bits
;
420 MantissaInt mantissa
;
422 static constexpr int MANT_WIDTH
= fputil::MantissaWidth
<T
>::VALUE
;
423 static constexpr int EXP_BIAS
= fputil::FPBits
<T
>::EXPONENT_BIAS
;
426 LIBC_INLINE
constexpr FloatToString(T init_float
) : float_bits(init_float
) {
427 is_negative
= float_bits
.get_sign();
428 exponent
= float_bits
.get_exponent();
429 mantissa
= float_bits
.get_explicit_mantissa();
431 // Handle the exponent for numbers with a 0 exponent.
432 if (exponent
== -EXP_BIAS
) {
433 if (mantissa
> 0) { // Subnormals
440 // Adjust for the width of the mantissa.
441 exponent
-= MANT_WIDTH
;
446 LIBC_INLINE
constexpr bool is_nan() { return float_bits
.is_nan(); }
447 LIBC_INLINE
constexpr bool is_inf() { return float_bits
.is_inf(); }
448 LIBC_INLINE
constexpr bool is_inf_or_nan() {
449 return float_bits
.is_inf_or_nan();
452 // get_block returns an integer that represents the digits in the requested
454 LIBC_INLINE
constexpr BlockInt
get_positive_block(int block_index
) {
455 if (exponent
>= -MANT_WIDTH
) {
456 // idx is ceil(exponent/16) or 0 if exponent is negative. This is used to
457 // find the coarse section of the POW10_SPLIT table that will be used to
458 // calculate the 9 digit window, as well as some other related values.
462 : static_cast<uint32_t>(exponent
+ (IDX_SIZE
- 1)) / IDX_SIZE
;
464 // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
467 cpp::UInt
<MID_INT_SIZE
> val
;
469 #if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
470 // ----------------------- DYADIC FLOAT CALC MODE ------------------------
471 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
472 val
= internal::get_table_positive_df
<256>(IDX_SIZE
* idx
, block_index
);
473 #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
475 // ---------------------------- INT CALC MODE ----------------------------
476 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
478 const uint64_t MAX_POW_2_SIZE
=
479 exponent
+ CALC_SHIFT_CONST
- (BLOCK_SIZE
* block_index
);
480 const uint64_t MAX_POW_5_SIZE
=
481 internal::log2_pow5(BLOCK_SIZE
* block_index
);
482 const uint64_t MAX_INT_SIZE
=
483 (MAX_POW_2_SIZE
> MAX_POW_5_SIZE
) ? MAX_POW_2_SIZE
: MAX_POW_5_SIZE
;
485 if (MAX_INT_SIZE
< 1024) {
486 val
= internal::get_table_positive
<1024>(IDX_SIZE
* idx
, block_index
);
487 } else if (MAX_INT_SIZE
< 2048) {
488 val
= internal::get_table_positive
<2048>(IDX_SIZE
* idx
, block_index
);
489 } else if (MAX_INT_SIZE
< 4096) {
490 val
= internal::get_table_positive
<4096>(IDX_SIZE
* idx
, block_index
);
491 } else if (MAX_INT_SIZE
< 8192) {
492 val
= internal::get_table_positive
<8192>(IDX_SIZE
* idx
, block_index
);
494 val
= internal::get_table_positive
<16384>(IDX_SIZE
* idx
, block_index
);
497 // ----------------------------- TABLE MODE ------------------------------
498 const int32_t SHIFT_CONST
= TABLE_SHIFT_CONST
;
500 val
= POW10_SPLIT
[POW10_OFFSET
[idx
] + block_index
];
502 const uint32_t shift_amount
= SHIFT_CONST
+ (IDX_SIZE
* idx
) - exponent
;
503 const uint32_t digits
=
504 internal::mul_shift_mod_1e9(mantissa
, val
, (int32_t)(shift_amount
));
511 LIBC_INLINE
constexpr BlockInt
get_negative_block(int block_index
) {
513 const int32_t idx
= -exponent
/ IDX_SIZE
;
515 cpp::UInt
<MID_INT_SIZE
> val
;
517 #if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
518 // ----------------------- DYADIC FLOAT CALC MODE ------------------------
519 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
521 internal::get_table_negative_df
<256>(idx
* IDX_SIZE
, block_index
+ 1);
522 #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
523 // ---------------------------- INT CALC MODE ----------------------------
524 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
525 const uint64_t TEN_BLOCKS
= (block_index
+ 1) * BLOCK_SIZE
;
526 const uint64_t MAX_INT_SIZE
= internal::log2_pow5(TEN_BLOCKS
);
528 if (MAX_INT_SIZE
< 1024) {
530 internal::get_table_negative
<1024>(idx
* IDX_SIZE
, block_index
+ 1);
531 } else if (MAX_INT_SIZE
< 2048) {
533 internal::get_table_negative
<2048>(idx
* IDX_SIZE
, block_index
+ 1);
534 } else if (MAX_INT_SIZE
< 4096) {
536 internal::get_table_negative
<4096>(idx
* IDX_SIZE
, block_index
+ 1);
537 } else if (MAX_INT_SIZE
< 8192) {
539 internal::get_table_negative
<8192>(idx
* IDX_SIZE
, block_index
+ 1);
540 } else if (MAX_INT_SIZE
< 16384) {
541 val
= internal::get_table_negative
<16384>(idx
* IDX_SIZE
,
544 val
= internal::get_table_negative
<32768>(idx
* IDX_SIZE
,
548 // ----------------------------- TABLE MODE ------------------------------
549 // if the requested block is zero
550 const int32_t SHIFT_CONST
= TABLE_SHIFT_CONST
;
551 if (block_index
< MIN_BLOCK_2
[idx
]) {
554 const uint32_t p
= POW10_OFFSET_2
[idx
] + block_index
- MIN_BLOCK_2
[idx
];
555 // If every digit after the requested block is zero.
556 if (p
>= POW10_OFFSET_2
[idx
+ 1]) {
560 val
= POW10_SPLIT_2
[p
];
562 const int32_t shift_amount
= SHIFT_CONST
+ (-exponent
- IDX_SIZE
* idx
);
564 internal::mul_shift_mod_1e9(mantissa
, val
, shift_amount
);
571 LIBC_INLINE
constexpr BlockInt
get_block(int block_index
) {
572 if (block_index
>= 0) {
573 return get_positive_block(block_index
);
575 return get_negative_block(-1 - block_index
);
579 LIBC_INLINE
constexpr size_t get_positive_blocks() {
580 if (exponent
>= -MANT_WIDTH
) {
584 : static_cast<uint32_t>(exponent
+ (IDX_SIZE
- 1)) / IDX_SIZE
;
585 const uint32_t len
= internal::length_for_num(idx
* IDX_SIZE
, MANT_WIDTH
);
592 // This takes the index of a block after the decimal point (a negative block)
593 // and return if it's sure that all of the digits after it are zero.
594 LIBC_INLINE
constexpr bool is_lowest_block(size_t block_index
) {
595 #ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE
598 const int32_t idx
= -exponent
/ IDX_SIZE
;
599 const uint32_t p
= POW10_OFFSET_2
[idx
] + block_index
- MIN_BLOCK_2
[idx
];
600 // If the remaining digits are all 0, then this is the lowest block.
601 return p
>= POW10_OFFSET_2
[idx
+ 1];
605 LIBC_INLINE
constexpr size_t zero_blocks_after_point() {
606 #ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE
608 // TODO (michaelrj): Find a good algorithm for this that doesn't use a
611 return MIN_BLOCK_2
[-exponent
/ IDX_SIZE
];
616 #ifndef LONG_DOUBLE_IS_DOUBLE
617 // --------------------------- LONG DOUBLE FUNCTIONS ---------------------------
620 LIBC_INLINE
constexpr size_t FloatToString
<long double>::get_positive_blocks() {
621 if (exponent
>= -MANT_WIDTH
) {
625 : static_cast<uint32_t>(exponent
+ (IDX_SIZE
- 1)) / IDX_SIZE
;
626 const uint32_t len
= internal::length_for_num(idx
* IDX_SIZE
, MANT_WIDTH
);
634 LIBC_INLINE
constexpr size_t
635 FloatToString
<long double>::zero_blocks_after_point() {
636 #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
637 return MIN_BLOCK_2
[-exponent
/ IDX_SIZE
];
640 // TODO (michaelrj): Find a good algorithm for this that doesn't use a table.
645 LIBC_INLINE
constexpr bool FloatToString
<long double>::is_lowest_block(size_t) {
650 LIBC_INLINE
constexpr BlockInt
651 FloatToString
<long double>::get_positive_block(int block_index
) {
652 if (exponent
>= -MANT_WIDTH
) {
654 // idx is ceil(exponent/16) or 0 if exponent is negative. This is used to
655 // find the coarse section of the POW10_SPLIT table that will be used to
656 // calculate the 9 digit window, as well as some other related values.
660 : static_cast<uint32_t>(exponent
+ (IDX_SIZE
- 1)) / IDX_SIZE
;
661 const uint32_t pos_exp
= idx
* IDX_SIZE
;
663 // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) - exponent
665 cpp::UInt
<MID_INT_SIZE
> val
;
666 #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
667 // ------------------------------ TABLE MODE -------------------------------
668 const int32_t SHIFT_CONST
= TABLE_SHIFT_CONST
;
669 val
= POW10_SPLIT
[POW10_OFFSET
[idx
] + block_index
];
671 #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT) || \
672 defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD)
673 // ------------------------ DYADIC FLOAT CALC MODE -------------------------
674 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
675 val
= internal::get_table_positive_df
<256>(pos_exp
, block_index
);
677 // ----------------------------- INT CALC MODE -----------------------------
678 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
679 const uint64_t MAX_POW_2_SIZE
=
680 exponent
+ CALC_SHIFT_CONST
- (BLOCK_SIZE
* block_index
);
681 const uint64_t MAX_POW_5_SIZE
=
682 internal::log2_pow5(BLOCK_SIZE
* block_index
);
683 const uint64_t MAX_INT_SIZE
=
684 (MAX_POW_2_SIZE
> MAX_POW_5_SIZE
) ? MAX_POW_2_SIZE
: MAX_POW_5_SIZE
;
686 if (MAX_INT_SIZE
< 1024) {
687 val
= internal::get_table_positive
<1024>(pos_exp
, block_index
);
688 } else if (MAX_INT_SIZE
< 2048) {
689 val
= internal::get_table_positive
<2048>(pos_exp
, block_index
);
690 } else if (MAX_INT_SIZE
< 4096) {
691 val
= internal::get_table_positive
<4096>(pos_exp
, block_index
);
692 } else if (MAX_INT_SIZE
< 8192) {
693 val
= internal::get_table_positive
<8192>(pos_exp
, block_index
);
695 val
= internal::get_table_positive
<16384>(pos_exp
, block_index
);
698 const uint32_t shift_amount
= SHIFT_CONST
+ pos_exp
- exponent
;
700 const BlockInt digits
=
701 internal::mul_shift_mod_1e9(mantissa
, val
, (int32_t)(shift_amount
));
709 LIBC_INLINE
constexpr BlockInt
710 FloatToString
<long double>::get_negative_block(int block_index
) {
712 const int32_t idx
= -exponent
/ IDX_SIZE
;
714 cpp::UInt
<MID_INT_SIZE
> val
;
715 #ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE
716 // ------------------------------ TABLE MODE -------------------------------
717 const int32_t SHIFT_CONST
= TABLE_SHIFT_CONST
;
719 // if the requested block is zero
720 if (block_index
<= MIN_BLOCK_2
[idx
]) {
723 const uint32_t p
= POW10_OFFSET_2
[idx
] + block_index
- MIN_BLOCK_2
[idx
];
724 // If every digit after the requested block is zero.
725 if (p
>= POW10_OFFSET_2
[idx
+ 1]) {
728 val
= POW10_SPLIT_2
[p
];
729 #elif defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT) || \
730 defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD)
731 // ------------------------ DYADIC FLOAT CALC MODE -------------------------
732 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
734 val
= internal::get_table_negative_df
<256>(idx
* IDX_SIZE
, block_index
+ 1);
736 // ----------------------------- INT CALC MODE -----------------------------
737 const int32_t SHIFT_CONST
= CALC_SHIFT_CONST
;
739 const uint64_t TEN_BLOCKS
= (block_index
+ 1) * BLOCK_SIZE
;
740 const uint64_t MAX_INT_SIZE
= internal::log2_pow5(TEN_BLOCKS
);
742 if (MAX_INT_SIZE
< 1024) {
743 val
= internal::get_table_negative
<1024>(idx
* IDX_SIZE
, block_index
+ 1);
744 } else if (MAX_INT_SIZE
< 2048) {
745 val
= internal::get_table_negative
<2048>(idx
* IDX_SIZE
, block_index
+ 1);
746 } else if (MAX_INT_SIZE
< 4096) {
747 val
= internal::get_table_negative
<4096>(idx
* IDX_SIZE
, block_index
+ 1);
748 } else if (MAX_INT_SIZE
< 8192) {
749 val
= internal::get_table_negative
<8192>(idx
* IDX_SIZE
, block_index
+ 1);
750 } else if (MAX_INT_SIZE
< 16384) {
752 internal::get_table_negative
<16384>(idx
* IDX_SIZE
, block_index
+ 1);
754 val
= internal::get_table_negative
<16384 + 8192>(idx
* IDX_SIZE
,
758 const int32_t shift_amount
= SHIFT_CONST
+ (-exponent
- IDX_SIZE
* idx
);
759 BlockInt digits
= internal::mul_shift_mod_1e9(mantissa
, val
, shift_amount
);
766 #endif // LONG_DOUBLE_IS_DOUBLE
768 } // namespace __llvm_libc
770 #endif // LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H