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