841 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H10#define LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H11 12#include "hdr/stdint_proxy.h"13#include "src/__support/CPP/limits.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/big_int.h"18#include "src/__support/common.h"19#include "src/__support/libc_assert.h"20#include "src/__support/macros/attributes.h"21#include "src/__support/macros/config.h"22#include "src/__support/sign.h"23 24// This file has 5 compile-time flags to allow the user to configure the float25// to string behavior. These were used to explore tradeoffs during the design26// phase, and can still be used to gain specific properties. Unless you27// specifically know what you're doing, you should leave all these flags off.28 29// LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD30// This flag disables the separate long double conversion implementation. It is31// not based on the Ryu algorithm, instead generating the digits by32// multiplying/dividing the written-out number by 10^9 to get blocks. It's33// significantly faster than INT_CALC, only about 10x slower than MEGA_TABLE,34// and is small in binary size. Its downside is that it always calculates all35// of the digits above the decimal point, making it inefficient for %e calls36// with large exponents. This specialization overrides other flags, so this37// flag must be set for other flags to effect the long double behavior.38 39// LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE40// The Mega Table is ~5 megabytes when compiled. It lists the constants needed41// to perform the Ryu Printf algorithm (described below) for all long double42// values. This makes it extremely fast for both doubles and long doubles, in43// exchange for large binary size.44 45// LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT46// Dyadic floats are software floating point numbers, and their accuracy can be47// as high as necessary. This option uses 256 bit dyadic floats to calculate48// the table values that Ryu Printf needs. This is reasonably fast and very49// small compared to the Mega Table, but the 256 bit floats only give accurate50// results for the first ~50 digits of the output. In practice this shouldn't51// be a problem since long doubles are only accurate for ~35 digits, but the52// trailing values all being 0s may cause brittle tests to fail.53 54// LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC55// Integer Calculation uses wide integers to do the calculations for the Ryu56// Printf table, which is just as accurate as the Mega Table without requiring57// as much code size. These integers can be very large (~32KB at max, though58// always on the stack) to handle the edges of the long double range. They are59// also very slow, taking multiple seconds on a powerful CPU to calculate the60// values at the end of the range. If no flag is set, this is used for long61// doubles, the flag only changes the double behavior.62 63// LIBC_COPT_FLOAT_TO_STR_NO_TABLE64// This flag doesn't change the actual calculation method, instead it is used65// to disable the normal Ryu Printf table for configurations that don't use any66// table at all.67 68// Default Config:69// If no flags are set, doubles use the normal (and much more reasonably sized)70// Ryu Printf table and long doubles use their specialized implementation. This71// provides good performance and binary size.72 73#ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE74#include "src/__support/ryu_long_double_constants.h"75#elif !defined(LIBC_COPT_FLOAT_TO_STR_NO_TABLE)76#include "src/__support/ryu_constants.h"77#else78constexpr size_t IDX_SIZE = 1;79constexpr size_t MID_INT_SIZE = 192;80#endif81 82// This implementation is based on the Ryu Printf algorithm by Ulf Adams:83// Ulf Adams. 2019. Ryū revisited: printf floating point conversion.84// Proc. ACM Program. Lang. 3, OOPSLA, Article 169 (October 2019), 23 pages.85// https://doi.org/10.1145/336059586 87// This version is modified to require significantly less memory (it doesn't use88// a large buffer to store the result).89 90// The general concept of this algorithm is as follows:91// We want to calculate a 9 digit segment of a floating point number using this92// formula: floor((mantissa * 2^exponent)/10^i) % 10^9.93// To do so normally would involve large integers (~1000 bits for doubles), so94// we use a shortcut. We can avoid calculating 2^exponent / 10^i by using a95// lookup table. The resulting intermediate value needs to be about 192 bits to96// store the result with enough precision. Since this is all being done with97// integers for appropriate precision, we would run into a problem if98// i > exponent since then 2^exponent / 10^i would be less than 1. To correct99// for this, the actual calculation done is 2^(exponent + c) / 10^i, and then100// when multiplying by the mantissa we reverse this by dividing by 2^c, like so:101// floor((mantissa * table[exponent][i])/(2^c)) % 10^9.102// This gives a 9 digit value, which is small enough to fit in a 32 bit integer,103// and that integer is converted into a string as normal, and called a block. In104// this implementation, the most recent block is buffered, so that if rounding105// is necessary the block can be adjusted before being written to the output.106// Any block that is all 9s adds one to the max block counter and doesn't clear107// the buffer because they can cause the block above them to be rounded up.108 109namespace LIBC_NAMESPACE_DECL {110 111using BlockInt = uint32_t;112constexpr uint32_t BLOCK_SIZE = 9;113constexpr uint64_t EXP5_9 = 1953125;114constexpr uint64_t EXP10_9 = 1000000000;115 116using FPBits = fputil::FPBits<long double>;117 118// Larger numbers prefer a slightly larger constant than is used for the smaller119// numbers.120constexpr size_t CALC_SHIFT_CONST = 128;121 122namespace internal {123 124// Returns floor(log_10(2^e)); requires 0 <= e <= 42039.125LIBC_INLINE constexpr uint32_t log10_pow2(uint64_t e) {126 LIBC_ASSERT(e <= 42039 &&127 "Incorrect exponent to perform log10_pow2 approximation.");128 // This approximation is based on the float value for log_10(2). It first129 // gives an incorrect result for our purposes at 42039 (well beyond the 16383130 // maximum for long doubles).131 132 // To get these constants I first evaluated log_10(2) to get an approximation133 // of 0.301029996. Next I passed that value through a string to double134 // conversion to get an explicit mantissa of 0x13441350fbd738 and an exponent135 // of -2 (which becomes -54 when we shift the mantissa to be a non-fractional136 // number). Next I shifted the mantissa right 12 bits to create more space for137 // the multiplication result, adding 12 to the exponent to compensate. To138 // check that this approximation works for our purposes I used the following139 // python code:140 // for i in range(16384):141 // if(len(str(2**i)) != (((i*0x13441350fbd)>>42)+1)):142 // print(i)143 // The reason we add 1 is because this evaluation truncates the result, giving144 // us the floor, whereas counting the digits of the power of 2 gives us the145 // ceiling. With a similar loop I checked the maximum valid value and found146 // 42039.147 return static_cast<uint32_t>((e * 0x13441350fbdll) >> 42);148}149 150// Same as above, but with different constants.151LIBC_INLINE constexpr uint32_t log2_pow5(uint64_t e) {152 return static_cast<uint32_t>((e * 0x12934f0979bll) >> 39);153}154 155// Returns 1 + floor(log_10(2^e). This could technically be off by 1 if any156// power of 2 was also a power of 10, but since that doesn't exist this is157// always accurate. This is used to calculate the maximum number of base-10158// digits a given e-bit number could have.159LIBC_INLINE constexpr uint32_t ceil_log10_pow2(uint32_t e) {160 return log10_pow2(e) + 1;161}162 163LIBC_INLINE constexpr uint32_t div_ceil(uint32_t num, uint32_t denom) {164 return (num + (denom - 1)) / denom;165}166 167// Returns the maximum number of 9 digit blocks a number described by the given168// index (which is ceil(exponent/16)) and mantissa width could need.169LIBC_INLINE constexpr uint32_t length_for_num(uint32_t idx,170 uint32_t mantissa_width) {171 return div_ceil(ceil_log10_pow2(idx) + ceil_log10_pow2(mantissa_width + 1),172 BLOCK_SIZE);173}174 175// The formula for the table when i is positive (or zero) is as follows:176// floor(10^(-9i) * 2^(e + c_1) + 1) % (10^9 * 2^c_1)177// Rewritten slightly we get:178// floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)179 180// TODO: Fix long doubles (needs bigger table or alternate algorithm.)181// Currently the table values are generated, which is very slow.182template <size_t INT_SIZE>183LIBC_INLINE constexpr UInt<MID_INT_SIZE> get_table_positive(int exponent,184 size_t i) {185 // INT_SIZE is the size of int that is used for the internal calculations of186 // this function. It should be large enough to hold 2^(exponent+constant), so187 // ~1000 for double and ~16000 for long double. Be warned that the time188 // complexity of exponentiation is O(n^2 * log_2(m)) where n is the number of189 // bits in the number being exponentiated and m is the exponent.190 const int shift_amount =191 static_cast<int>(exponent + CALC_SHIFT_CONST - (BLOCK_SIZE * i));192 if (shift_amount < 0) {193 return 1;194 }195 UInt<INT_SIZE> num(0);196 // MOD_SIZE is one of the limiting factors for how big the constant argument197 // can get, since it needs to be small enough to fit in the result UInt,198 // otherwise we'll get truncation on return.199 constexpr UInt<INT_SIZE> MOD_SIZE =200 (UInt<INT_SIZE>(EXP10_9)201 << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));202 203 num = UInt<INT_SIZE>(1) << (shift_amount);204 if (i > 0) {205 UInt<INT_SIZE> fives(EXP5_9);206 fives.pow_n(i);207 num = num / fives;208 }209 210 num = num + 1;211 if (num > MOD_SIZE) {212 auto rem = num.div_uint_half_times_pow_2(213 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))214 .value();215 num = rem;216 }217 return num;218}219 220template <size_t INT_SIZE>221LIBC_INLINE UInt<MID_INT_SIZE> get_table_positive_df(int exponent, size_t i) {222 static_assert(INT_SIZE == 256,223 "Only 256 is supported as an int size right now.");224 // This version uses dyadic floats with 256 bit mantissas to perform the same225 // calculation as above. Due to floating point imprecision it is only accurate226 // for the first 50 digits, but it's much faster. Since even 128 bit long227 // doubles are only accurate to ~35 digits, the 50 digits of accuracy are228 // enough for these floats to be converted back and forth safely. This is229 // ideal for avoiding the size of the long double table.230 const int shift_amount =231 static_cast<int>(exponent + CALC_SHIFT_CONST - (9 * i));232 if (shift_amount < 0) {233 return 1;234 }235 fputil::DyadicFloat<INT_SIZE> num(Sign::POS, 0, 1);236 constexpr UInt<INT_SIZE> MOD_SIZE =237 (UInt<INT_SIZE>(EXP10_9)238 << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));239 240 constexpr UInt<INT_SIZE> FIVE_EXP_MINUS_NINE_MANT{241 {0xf387295d242602a7, 0xfdd7645e011abac9, 0x31680a88f8953030,242 0x89705f4136b4a597}};243 244 static const fputil::DyadicFloat<INT_SIZE> FIVE_EXP_MINUS_NINE(245 Sign::POS, -276, FIVE_EXP_MINUS_NINE_MANT);246 247 if (i > 0) {248 fputil::DyadicFloat<INT_SIZE> fives =249 fputil::pow_n(FIVE_EXP_MINUS_NINE, static_cast<uint32_t>(i));250 num = fives;251 }252 num = mul_pow_2(num, shift_amount);253 254 // Adding one is part of the formula.255 UInt<INT_SIZE> int_num = num.as_mantissa_type() + 1;256 if (int_num > MOD_SIZE) {257 auto rem =258 int_num259 .div_uint_half_times_pow_2(260 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))261 .value();262 int_num = rem;263 }264 265 UInt<MID_INT_SIZE> result = int_num;266 267 return result;268}269 270// The formula for the table when i is negative (or zero) is as follows:271// floor(10^(-9i) * 2^(c_0 - e)) % (10^9 * 2^c_0)272// Since we know i is always negative, we just take it as unsigned and treat it273// as negative. We do the same with exponent, while they're both always negative274// in theory, in practice they're converted to positive for simpler275// calculations.276// The formula being used looks more like this:277// floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)278template <size_t INT_SIZE>279LIBC_INLINE UInt<MID_INT_SIZE> get_table_negative(int exponent, size_t i) {280 int shift_amount = CALC_SHIFT_CONST - exponent;281 UInt<INT_SIZE> num(1);282 constexpr UInt<INT_SIZE> MOD_SIZE =283 (UInt<INT_SIZE>(EXP10_9)284 << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));285 286 size_t ten_blocks = i;287 size_t five_blocks = 0;288 if (shift_amount < 0) {289 int block_shifts = (-shift_amount) / static_cast<int>(BLOCK_SIZE);290 if (block_shifts < static_cast<int>(ten_blocks)) {291 ten_blocks = ten_blocks - block_shifts;292 five_blocks = block_shifts;293 shift_amount = shift_amount + (block_shifts * BLOCK_SIZE);294 } else {295 ten_blocks = 0;296 five_blocks = i;297 shift_amount = shift_amount + (static_cast<int>(i) * BLOCK_SIZE);298 }299 }300 301 if (five_blocks > 0) {302 UInt<INT_SIZE> fives(EXP5_9);303 fives.pow_n(five_blocks);304 num = fives;305 }306 if (ten_blocks > 0) {307 UInt<INT_SIZE> tens(EXP10_9);308 tens.pow_n(ten_blocks);309 if (five_blocks <= 0) {310 num = tens;311 } else {312 num *= tens;313 }314 }315 316 if (shift_amount > 0) {317 num = num << shift_amount;318 } else {319 num = num >> (-shift_amount);320 }321 if (num > MOD_SIZE) {322 auto rem = num.div_uint_half_times_pow_2(323 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))324 .value();325 num = rem;326 }327 return num;328}329 330template <size_t INT_SIZE>331LIBC_INLINE UInt<MID_INT_SIZE> get_table_negative_df(int exponent, size_t i) {332 static_assert(INT_SIZE == 256,333 "Only 256 is supported as an int size right now.");334 // This version uses dyadic floats with 256 bit mantissas to perform the same335 // calculation as above. Due to floating point imprecision it is only accurate336 // for the first 50 digits, but it's much faster. Since even 128 bit long337 // doubles are only accurate to ~35 digits, the 50 digits of accuracy are338 // enough for these floats to be converted back and forth safely. This is339 // ideal for avoiding the size of the long double table.340 341 int shift_amount = CALC_SHIFT_CONST - exponent;342 343 fputil::DyadicFloat<INT_SIZE> num(Sign::POS, 0, 1);344 constexpr UInt<INT_SIZE> MOD_SIZE =345 (UInt<INT_SIZE>(EXP10_9)346 << (CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0)));347 348 constexpr UInt<INT_SIZE> TEN_EXP_NINE_MANT(EXP10_9);349 350 static const fputil::DyadicFloat<INT_SIZE> TEN_EXP_NINE(Sign::POS, 0,351 TEN_EXP_NINE_MANT);352 353 if (i > 0) {354 fputil::DyadicFloat<INT_SIZE> tens =355 fputil::pow_n(TEN_EXP_NINE, static_cast<uint32_t>(i));356 num = tens;357 }358 num = mul_pow_2(num, shift_amount);359 360 UInt<INT_SIZE> int_num = num.as_mantissa_type();361 if (int_num > MOD_SIZE) {362 auto rem =363 int_num364 .div_uint_half_times_pow_2(365 EXP10_9, CALC_SHIFT_CONST + (IDX_SIZE > 1 ? IDX_SIZE : 0))366 .value();367 int_num = rem;368 }369 370 UInt<MID_INT_SIZE> result = int_num;371 372 return result;373}374 375LIBC_INLINE uint32_t mul_shift_mod_1e9(const FPBits::StorageType mantissa,376 const UInt<MID_INT_SIZE> &large,377 const int32_t shift_amount) {378 // make sure the number of bits is always divisible by 64379 UInt<internal::div_ceil(MID_INT_SIZE + FPBits::STORAGE_LEN, 64) * 64> val(380 large);381 val = (val * mantissa) >> shift_amount;382 return static_cast<uint32_t>(383 val.div_uint_half_times_pow_2(static_cast<uint32_t>(EXP10_9), 0).value());384}385 386} // namespace internal387 388// Convert floating point values to their string representation.389// Because the result may not fit in a reasonably sized array, the caller must390// request blocks of digits and convert them from integers to strings themself.391// Blocks contain the most digits that can be stored in an BlockInt. This is 9392// digits for a 32 bit int and 18 digits for a 64 bit int.393// The intended use pattern is to create a FloatToString object of the394// appropriate type, then call get_positive_blocks to get an approximate number395// of blocks there are before the decimal point. Now the client code can start396// calling get_positive_block in a loop from the number of positive blocks to397// zero. This will give all digits before the decimal point. Then the user can398// start calling get_negative_block in a loop from 0 until the number of digits399// they need is reached. As an optimization, the client can use400// zero_blocks_after_point to find the number of blocks that are guaranteed to401// be zero after the decimal point and before the non-zero digits. Additionally,402// is_lowest_block will return if the current block is the lowest non-zero403// block.404template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>405class FloatToString {406 fputil::FPBits<T> float_bits;407 int exponent;408 FPBits::StorageType mantissa;409 410 static constexpr int FRACTION_LEN = fputil::FPBits<T>::FRACTION_LEN;411 static constexpr int EXP_BIAS = fputil::FPBits<T>::EXP_BIAS;412 413public:414 LIBC_INLINE constexpr FloatToString(T init_float) : float_bits(init_float) {415 exponent = float_bits.get_explicit_exponent();416 mantissa = float_bits.get_explicit_mantissa();417 418 // Adjust for the width of the mantissa.419 exponent -= FRACTION_LEN;420 }421 422 LIBC_INLINE constexpr bool is_nan() { return float_bits.is_nan(); }423 LIBC_INLINE constexpr bool is_inf() { return float_bits.is_inf(); }424 LIBC_INLINE constexpr bool is_inf_or_nan() {425 return float_bits.is_inf_or_nan();426 }427 428 // get_block returns an integer that represents the digits in the requested429 // block.430 LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {431 if (exponent >= -FRACTION_LEN) {432 // idx is ceil(exponent/16) or 0 if exponent is negative. This is used to433 // find the coarse section of the POW10_SPLIT table that will be used to434 // calculate the 9 digit window, as well as some other related values.435 const uint32_t idx =436 exponent < 0437 ? 0438 : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;439 440 // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -441 // exponent442 443 const uint32_t pos_exp = idx * IDX_SIZE;444 445 UInt<MID_INT_SIZE> val;446 447#if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)448 // ----------------------- DYADIC FLOAT CALC MODE ------------------------449 const int32_t SHIFT_CONST = CALC_SHIFT_CONST;450 val = internal::get_table_positive_df<256>(IDX_SIZE * idx, block_index);451#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)452 453 // ---------------------------- INT CALC MODE ----------------------------454 const int32_t SHIFT_CONST = CALC_SHIFT_CONST;455 const uint64_t MAX_POW_2_SIZE =456 pos_exp + CALC_SHIFT_CONST - (BLOCK_SIZE * block_index);457 const uint64_t MAX_POW_5_SIZE =458 internal::log2_pow5(BLOCK_SIZE * block_index);459 const uint64_t MAX_INT_SIZE =460 (MAX_POW_2_SIZE > MAX_POW_5_SIZE) ? MAX_POW_2_SIZE : MAX_POW_5_SIZE;461 462 if (MAX_INT_SIZE < 1024) {463 val = internal::get_table_positive<1024>(pos_exp, block_index);464 } else if (MAX_INT_SIZE < 2048) {465 val = internal::get_table_positive<2048>(pos_exp, block_index);466 } else if (MAX_INT_SIZE < 4096) {467 val = internal::get_table_positive<4096>(pos_exp, block_index);468 } else if (MAX_INT_SIZE < 8192) {469 val = internal::get_table_positive<8192>(pos_exp, block_index);470 } else if (MAX_INT_SIZE < 16384) {471 val = internal::get_table_positive<16384>(pos_exp, block_index);472 } else {473 val = internal::get_table_positive<16384 + 128>(pos_exp, block_index);474 }475#else476 // ----------------------------- TABLE MODE ------------------------------477 const int32_t SHIFT_CONST = TABLE_SHIFT_CONST;478 479 val = POW10_SPLIT[POW10_OFFSET[idx] + block_index];480#endif481 const uint32_t shift_amount = SHIFT_CONST + pos_exp - exponent;482 483 const BlockInt digits =484 internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));485 return digits;486 } else {487 return 0;488 }489 }490 491 LIBC_INLINE constexpr BlockInt get_negative_block(int block_index) {492 if (exponent < 0) {493 const int32_t idx = -exponent / static_cast<int32_t>(IDX_SIZE);494 495 UInt<MID_INT_SIZE> val;496 497 const uint32_t pos_exp = static_cast<uint32_t>(idx * IDX_SIZE);498 499#if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)500 // ----------------------- DYADIC FLOAT CALC MODE ------------------------501 const int32_t SHIFT_CONST = CALC_SHIFT_CONST;502 val = internal::get_table_negative_df<256>(pos_exp, block_index + 1);503#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)504 // ---------------------------- INT CALC MODE ----------------------------505 const int32_t SHIFT_CONST = CALC_SHIFT_CONST;506 507 const uint64_t NUM_FIVES = (block_index + 1) * BLOCK_SIZE;508 // Round MAX_INT_SIZE up to the nearest 64 (adding 1 because log2_pow5509 // implicitly rounds down).510 const uint64_t MAX_INT_SIZE =511 ((internal::log2_pow5(NUM_FIVES) / 64) + 1) * 64;512 513 if (MAX_INT_SIZE < 1024) {514 val = internal::get_table_negative<1024>(pos_exp, block_index + 1);515 } else if (MAX_INT_SIZE < 2048) {516 val = internal::get_table_negative<2048>(pos_exp, block_index + 1);517 } else if (MAX_INT_SIZE < 4096) {518 val = internal::get_table_negative<4096>(pos_exp, block_index + 1);519 } else if (MAX_INT_SIZE < 8192) {520 val = internal::get_table_negative<8192>(pos_exp, block_index + 1);521 } else if (MAX_INT_SIZE < 16384) {522 val = internal::get_table_negative<16384>(pos_exp, block_index + 1);523 } else {524 val = internal::get_table_negative<16384 + 8192>(pos_exp,525 block_index + 1);526 }527#else528 // ----------------------------- TABLE MODE ------------------------------529 // if the requested block is zero530 const int32_t SHIFT_CONST = TABLE_SHIFT_CONST;531 if (block_index < MIN_BLOCK_2[idx]) {532 return 0;533 }534 const uint32_t p = POW10_OFFSET_2[idx] + block_index - MIN_BLOCK_2[idx];535 // If every digit after the requested block is zero.536 if (p >= POW10_OFFSET_2[idx + 1]) {537 return 0;538 }539 540 val = POW10_SPLIT_2[p];541#endif542 const int32_t shift_amount =543 SHIFT_CONST + (-exponent - static_cast<int32_t>(pos_exp));544 BlockInt digits =545 internal::mul_shift_mod_1e9(mantissa, val, shift_amount);546 return digits;547 } else {548 return 0;549 }550 }551 552 LIBC_INLINE constexpr BlockInt get_block(int block_index) {553 if (block_index >= 0) {554 return get_positive_block(block_index);555 } else {556 return get_negative_block(-1 - block_index);557 }558 }559 560 LIBC_INLINE constexpr size_t get_positive_blocks() {561 if (exponent < -FRACTION_LEN)562 return 0;563 const uint32_t idx =564 exponent < 0565 ? 0566 : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;567 return internal::length_for_num(idx * IDX_SIZE, FRACTION_LEN);568 }569 570 // This takes the index of a block after the decimal point (a negative block)571 // and return if it's sure that all of the digits after it are zero.572 LIBC_INLINE constexpr bool is_lowest_block(size_t negative_block_index) {573#ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE574 // The decimal representation of 2**(-i) will have exactly i digits after575 // the decimal point.576 int num_requested_digits =577 static_cast<int>((negative_block_index + 1) * BLOCK_SIZE);578 579 return num_requested_digits > -exponent;580#else581 const int32_t idx = -exponent / static_cast<int32_t>(IDX_SIZE);582 const size_t p =583 POW10_OFFSET_2[idx] + negative_block_index - MIN_BLOCK_2[idx];584 // If the remaining digits are all 0, then this is the lowest block.585 return p >= POW10_OFFSET_2[idx + 1];586#endif587 }588 589 LIBC_INLINE constexpr size_t zero_blocks_after_point() {590#ifdef LIBC_COPT_FLOAT_TO_STR_NO_TABLE591 if (exponent < -FRACTION_LEN) {592 const int pos_exp = -exponent - 1;593 const uint32_t pos_idx =594 static_cast<uint32_t>(pos_exp + (IDX_SIZE - 1)) / IDX_SIZE;595 const int32_t pos_len = ((internal::ceil_log10_pow2(pos_idx * IDX_SIZE) -596 internal::ceil_log10_pow2(FRACTION_LEN + 1)) /597 BLOCK_SIZE) -598 1;599 return static_cast<uint32_t>(pos_len > 0 ? pos_len : 0);600 }601 return 0;602#else603 return MIN_BLOCK_2[-exponent / static_cast<int32_t>(IDX_SIZE)];604#endif605 }606};607 608#if !defined(LIBC_TYPES_LONG_DOUBLE_IS_FLOAT64) && \609 !defined(LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD)610// --------------------------- LONG DOUBLE FUNCTIONS ---------------------------611 612// this algorithm will work exactly the same for 80 bit and 128 bit long613// doubles. They have the same max exponent, but even if they didn't the614// constants should be calculated to be correct for any provided floating point615// type.616 617template <> class FloatToString<long double> {618 fputil::FPBits<long double> float_bits;619 bool is_negative = 0;620 int exponent = 0;621 FPBits::StorageType mantissa = 0;622 623 static constexpr int FRACTION_LEN = fputil::FPBits<long double>::FRACTION_LEN;624 static constexpr int EXP_BIAS = fputil::FPBits<long double>::EXP_BIAS;625 static constexpr size_t UINT_WORD_SIZE = 64;626 627 static constexpr size_t FLOAT_AS_INT_WIDTH =628 internal::div_ceil(fputil::FPBits<long double>::MAX_BIASED_EXPONENT -629 FPBits::EXP_BIAS,630 UINT_WORD_SIZE) *631 UINT_WORD_SIZE;632 static constexpr size_t EXTRA_INT_WIDTH =633 internal::div_ceil(sizeof(long double) * CHAR_BIT, UINT_WORD_SIZE) *634 UINT_WORD_SIZE;635 636 using wide_int = UInt<FLOAT_AS_INT_WIDTH + EXTRA_INT_WIDTH>;637 638 // float_as_fixed represents the floating point number as a fixed point number639 // with the point EXTRA_INT_WIDTH bits from the left of the number. This can640 // store any number with a negative exponent.641 wide_int float_as_fixed = 0;642 int int_block_index = 0;643 644 static constexpr size_t BLOCK_BUFFER_LEN =645 internal::div_ceil(internal::log10_pow2(FLOAT_AS_INT_WIDTH), BLOCK_SIZE) +646 1;647 BlockInt block_buffer[BLOCK_BUFFER_LEN] = {0};648 size_t block_buffer_valid = 0;649 650 template <size_t Bits>651 LIBC_INLINE static constexpr BlockInt grab_digits(UInt<Bits> &int_num) {652 auto wide_result = int_num.div_uint_half_times_pow_2(EXP5_9, 9);653 // the optional only comes into effect when dividing by 0, which will654 // never happen here. Thus, we just assert that it has value.655 LIBC_ASSERT(wide_result.has_value());656 return static_cast<BlockInt>(wide_result.value());657 }658 659 LIBC_INLINE static constexpr void zero_leading_digits(wide_int &int_num) {660 // WORD_SIZE is the width of the numbers used to internally represent the661 // UInt662 for (size_t i = 0; i < EXTRA_INT_WIDTH / wide_int::WORD_SIZE; ++i)663 int_num[i + (FLOAT_AS_INT_WIDTH / wide_int::WORD_SIZE)] = 0;664 }665 666 // init_convert initializes float_as_int, cur_block, and block_buffer based on667 // the mantissa and exponent of the initial number. Calling it will always668 // return the class to the starting state.669 LIBC_INLINE constexpr void init_convert() {670 // No calculation necessary for the 0 case.671 if (mantissa == 0 && exponent == 0)672 return;673 674 if (exponent > 0) {675 // if the exponent is positive, then the number is fully above the decimal676 // point. In this case we represent the float as an integer, then divide677 // by 10^BLOCK_SIZE and take the remainder as our next block. This678 // generates the digits from right to left, but the digits will be written679 // from left to right, so it caches the results so they can be read in680 // reverse order.681 682 wide_int float_as_int = mantissa;683 684 float_as_int <<= exponent;685 int_block_index = 0;686 687 while (float_as_int > 0) {688 LIBC_ASSERT(int_block_index < static_cast<int>(BLOCK_BUFFER_LEN));689 block_buffer[int_block_index] =690 grab_digits<FLOAT_AS_INT_WIDTH + EXTRA_INT_WIDTH>(float_as_int);691 ++int_block_index;692 }693 block_buffer_valid = int_block_index;694 695 } else {696 // if the exponent is not positive, then the number is at least partially697 // below the decimal point. In this case we represent the float as a fixed698 // point number with the decimal point after the top EXTRA_INT_WIDTH bits.699 float_as_fixed = mantissa;700 701 const int SHIFT_AMOUNT = FLOAT_AS_INT_WIDTH + exponent;702 static_assert(EXTRA_INT_WIDTH >= sizeof(long double) * 8);703 if (SHIFT_AMOUNT > 0) {704 float_as_fixed <<= SHIFT_AMOUNT;705 } else {706 float_as_fixed >>= -SHIFT_AMOUNT;707 }708 709 // If there are still digits above the decimal point, handle those.710 if (cpp::countl_zero(float_as_fixed) <711 static_cast<int>(EXTRA_INT_WIDTH)) {712 UInt<EXTRA_INT_WIDTH> above_decimal_point =713 float_as_fixed >> FLOAT_AS_INT_WIDTH;714 715 size_t positive_int_block_index = 0;716 while (above_decimal_point > 0) {717 block_buffer[positive_int_block_index] =718 grab_digits<EXTRA_INT_WIDTH>(above_decimal_point);719 ++positive_int_block_index;720 }721 block_buffer_valid = positive_int_block_index;722 723 // Zero all digits above the decimal point.724 zero_leading_digits(float_as_fixed);725 int_block_index = 0;726 }727 }728 }729 730public:731 LIBC_INLINE constexpr FloatToString(long double init_float)732 : float_bits(init_float) {733 is_negative = float_bits.is_neg();734 exponent = float_bits.get_explicit_exponent();735 mantissa = float_bits.get_explicit_mantissa();736 737 // Adjust for the width of the mantissa.738 exponent -= FRACTION_LEN;739 740 this->init_convert();741 }742 743 LIBC_INLINE constexpr size_t get_positive_blocks() {744 if (exponent < -FRACTION_LEN)745 return 0;746 747 const uint32_t idx =748 exponent < 0749 ? 0750 : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;751 return internal::length_for_num(idx * IDX_SIZE, FRACTION_LEN);752 }753 754 LIBC_INLINE constexpr size_t zero_blocks_after_point() {755#ifdef LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE756 return MIN_BLOCK_2[-exponent / IDX_SIZE];757#else758 if (exponent >= -FRACTION_LEN)759 return 0;760 761 const int pos_exp = -exponent - 1;762 const uint32_t pos_idx =763 static_cast<uint32_t>(pos_exp + (IDX_SIZE - 1)) / IDX_SIZE;764 const int32_t pos_len = ((internal::ceil_log10_pow2(pos_idx * IDX_SIZE) -765 internal::ceil_log10_pow2(FRACTION_LEN + 1)) /766 BLOCK_SIZE) -767 1;768 return static_cast<uint32_t>(pos_len > 0 ? pos_len : 0);769#endif770 }771 772 LIBC_INLINE constexpr bool is_lowest_block(size_t negative_block_index) {773 // The decimal representation of 2**(-i) will have exactly i digits after774 // the decimal point.775 const int num_requested_digits =776 static_cast<int>(negative_block_index * BLOCK_SIZE);777 778 return num_requested_digits > -exponent;779 }780 781 LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {782 if (exponent < -FRACTION_LEN)783 return 0;784 if (block_index > static_cast<int>(block_buffer_valid) || block_index < 0)785 return 0;786 787 LIBC_ASSERT(block_index < static_cast<int>(BLOCK_BUFFER_LEN));788 789 return block_buffer[block_index];790 }791 792 LIBC_INLINE constexpr BlockInt get_negative_block(int negative_block_index) {793 if (exponent >= 0)794 return 0;795 796 // negative_block_index starts at 0 with the first block after the decimal797 // point, and 1 with the second and so on. This converts to the same798 // block_index used everywhere else.799 800 const int block_index = -1 - negative_block_index;801 802 // If we're currently after the requested block (remember these are803 // negative indices) we reset the number to the start. This is only804 // likely to happen in %g calls. This will also reset int_block_index.805 // if (block_index > int_block_index) {806 // init_convert();807 // }808 809 // Printf is the only existing user of this code and it will only ever move810 // downwards, except for %g but that currently creates a second811 // float_to_string object so this assertion still holds. If a new user needs812 // the ability to step backwards, uncomment the code above.813 LIBC_ASSERT(block_index <= int_block_index);814 815 // If we are currently before the requested block. Step until we reach the816 // requested block. This is likely to only be one step.817 while (block_index < int_block_index) {818 zero_leading_digits(float_as_fixed);819 float_as_fixed.mul(EXP10_9);820 --int_block_index;821 }822 823 // We're now on the requested block, return the current block.824 return static_cast<BlockInt>(float_as_fixed >> FLOAT_AS_INT_WIDTH);825 }826 827 LIBC_INLINE constexpr BlockInt get_block(int block_index) {828 if (block_index >= 0)829 return get_positive_block(block_index);830 831 return get_negative_block(-1 - block_index);832 }833};834 835#endif // !LIBC_TYPES_LONG_DOUBLE_IS_FLOAT64 &&836 // !LIBC_COPT_FLOAT_TO_STR_NO_SPECIALIZE_LD837 838} // namespace LIBC_NAMESPACE_DECL839 840#endif // LLVM_LIBC_SRC___SUPPORT_FLOAT_TO_STRING_H841