[libc][NFC] Move aligned access implementations to separate header
[llvm-project.git] / libc / src / __support / float_to_string.h
bloba3d1b08f3964f444e0cb50160418fce93bc865e8
1 //===-- Utilities to convert floating point values to string ----*- C++ -*-===//
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 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
10 #define LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
12 #include <stdint.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
59 // table at all.
61 // Default Config:
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
65 // for doubles.
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"
71 #else
72 constexpr size_t IDX_SIZE = 1;
73 constexpr size_t MID_INT_SIZE = 192;
74 #endif
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
111 // numbers.
112 constexpr size_t CALC_SHIFT_CONST = 128;
114 namespace internal {
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
131 // python code:
132 // for i in range(16384):
133 // if(len(str(2**i)) != (((i*0x13441350fbd)>>42)+1)):
134 // print(i)
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
138 // 42039.
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) +
161 (BLOCK_SIZE - 1)) /
162 BLOCK_SIZE;
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,
175 size_t i) {
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) {
183 return 1;
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);
196 if (i > 0) {
197 cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
198 fives.pow_n(i);
199 num = num / fives;
202 num = num + 1;
203 if (num > MOD_SIZE) {
204 auto rem =
205 num.div_uint32_times_pow_2(
206 1000000000, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
207 .value();
208 num = rem;
210 return num;
213 template <size_t INT_SIZE>
214 LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_positive_df(int exponent,
215 size_t i) {
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) {
226 return 1;
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);
240 if (i > 0) {
241 fputil::DyadicFloat<INT_SIZE> fives = fputil::pow_n(FIVE_EXP_MINUS_NINE, i);
242 num = fives;
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) {
249 auto rem =
250 int_num
251 .div_uint32_times_pow_2(
252 1000000000, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
253 .value();
254 int_num = rem;
257 cpp::UInt<MID_INT_SIZE> result = int_num;
259 return result;
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
267 // calculations.
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);
288 } else {
289 ten_blocks = 0;
290 five_blocks = i;
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);
298 num = fives;
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) {
304 num = tens;
305 } else {
306 num *= tens;
310 if (shift_amount > 0) {
311 num = num << shift_amount;
312 } else {
313 num = num >> (-shift_amount);
315 if (num > MOD_SIZE) {
316 auto rem =
317 num.div_uint32_times_pow_2(
318 1000000000, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
319 .value();
320 num = rem;
322 return num;
325 template <size_t INT_SIZE>
326 LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_negative_df(int exponent,
327 size_t i) {
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,
347 TEN_EXP_NINE_MANT);
349 if (i > 0) {
350 fputil::DyadicFloat<INT_SIZE> tens = fputil::pow_n(TEN_EXP_NINE, i);
351 num = tens;
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) {
357 auto rem =
358 int_num
359 .div_uint32_times_pow_2(
360 1000000000, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))
361 .value();
362 int_num = rem;
365 cpp::UInt<MID_INT_SIZE> result = int_num;
367 return result;
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
414 // block.
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;
418 bool is_negative;
419 int exponent;
420 MantissaInt mantissa;
422 static constexpr int MANT_WIDTH = fputil::MantissaWidth<T>::VALUE;
423 static constexpr int EXP_BIAS = fputil::FPBits<T>::EXPONENT_BIAS;
425 public:
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
434 ++exponent;
435 } else { // Zeroes
436 exponent = 0;
440 // Adjust for the width of the mantissa.
441 exponent -= MANT_WIDTH;
443 // init_convert();
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
453 // block.
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.
459 const uint32_t idx =
460 exponent < 0
462 : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
464 // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
465 // exponent
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);
493 } else {
494 val = internal::get_table_positive<16384>(IDX_SIZE * idx, block_index);
496 #else
497 // ----------------------------- TABLE MODE ------------------------------
498 const int32_t SHIFT_CONST = TABLE_SHIFT_CONST;
500 val = POW10_SPLIT[POW10_OFFSET[idx] + block_index];
501 #endif
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));
505 return digits;
506 } else {
507 return 0;
511 LIBC_INLINE constexpr BlockInt get_negative_block(int block_index) {
512 if (exponent < 0) {
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;
520 val =
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) {
529 val =
530 internal::get_table_negative<1024>(idx * IDX_SIZE, block_index + 1);
531 } else if (MAX_INT_SIZE < 2048) {
532 val =
533 internal::get_table_negative<2048>(idx * IDX_SIZE, block_index + 1);
534 } else if (MAX_INT_SIZE < 4096) {
535 val =
536 internal::get_table_negative<4096>(idx * IDX_SIZE, block_index + 1);
537 } else if (MAX_INT_SIZE < 8192) {
538 val =
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,
542 block_index + 1);
543 } else {
544 val = internal::get_table_negative<32768>(idx * IDX_SIZE,
545 block_index + 1);
547 #else
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]) {
552 return 0;
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]) {
557 return 0;
560 val = POW10_SPLIT_2[p];
561 #endif
562 const int32_t shift_amount = SHIFT_CONST + (-exponent - IDX_SIZE * idx);
563 uint32_t digits =
564 internal::mul_shift_mod_1e9(mantissa, val, shift_amount);
565 return digits;
566 } else {
567 return 0;
571 LIBC_INLINE constexpr BlockInt get_block(int block_index) {
572 if (block_index >= 0) {
573 return get_positive_block(block_index);
574 } else {
575 return get_negative_block(-1 - block_index);
579 LIBC_INLINE constexpr size_t get_positive_blocks() {
580 if (exponent >= -MANT_WIDTH) {
581 const uint32_t idx =
582 exponent < 0
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);
586 return len;
587 } else {
588 return 0;
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
596 return false;
597 #else
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];
602 #endif
605 LIBC_INLINE constexpr size_t zero_blocks_after_point() {
606 #ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE
607 return 0;
608 // TODO (michaelrj): Find a good algorithm for this that doesn't use a
609 // table.
610 #else
611 return MIN_BLOCK_2[-exponent / IDX_SIZE];
612 #endif
616 #ifndef LONG_DOUBLE_IS_DOUBLE
617 // --------------------------- LONG DOUBLE FUNCTIONS ---------------------------
619 template <>
620 LIBC_INLINE constexpr size_t FloatToString<long double>::get_positive_blocks() {
621 if (exponent >= -MANT_WIDTH) {
622 const uint32_t idx =
623 exponent < 0
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);
627 return len;
628 } else {
629 return 0;
633 template <>
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];
638 #else
639 return 0;
640 // TODO (michaelrj): Find a good algorithm for this that doesn't use a table.
641 #endif
644 template <>
645 LIBC_INLINE constexpr bool FloatToString<long double>::is_lowest_block(size_t) {
646 return false;
649 template <>
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.
657 const uint32_t idx =
658 exponent < 0
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);
676 #else
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);
694 } else {
695 val = internal::get_table_positive<16384>(pos_exp, block_index);
697 #endif
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));
702 return digits;
703 } else {
704 return 0;
708 template <>
709 LIBC_INLINE constexpr BlockInt
710 FloatToString<long double>::get_negative_block(int block_index) {
711 if (exponent < 0) {
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]) {
721 return 0;
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]) {
726 return 0;
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);
735 #else // table mode
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) {
751 val =
752 internal::get_table_negative<16384>(idx * IDX_SIZE, block_index + 1);
753 } else {
754 val = internal::get_table_negative<16384 + 8192>(idx * IDX_SIZE,
755 block_index + 1);
757 #endif
758 const int32_t shift_amount = SHIFT_CONST + (-exponent - IDX_SIZE * idx);
759 BlockInt digits = internal::mul_shift_mod_1e9(mantissa, val, shift_amount);
760 return digits;
761 } else {
762 return 0;
766 #endif // LONG_DOUBLE_IS_DOUBLE
768 } // namespace __llvm_libc
770 #endif // LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H