src/__support/float_to_string.h - llvm-project/libc - Git at Google

 //===-- Utilities to convert floating point values to string ----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #ifndef LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
 #define LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H

 #include <stdint.h>

 #include "src/__support/CPP/type_traits.h"
 #include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/UInt.h"
 #include "src/__support/common.h"
 #include "src/__support/libc_assert.h"
 #include "src/__support/ryu_constants.h"

 // This implementation is based on the Ryu Printf algorithm by Ulf Adams:
 // Ulf Adams. 2019. Ryū revisited: printf floating point conversion.
 // Proc. ACM Program. Lang. 3, OOPSLA, Article 169 (October 2019), 23 pages.
 // https://doi.org/10.1145/3360595

 // This version is modified to require significantly less memory (it doesn't use
 // a large buffer to store the result).

 // The general concept of this algorithm is as follows:
 // We want to calculate a 9 digit segment of a floating point number using this
 // formula: floor((mantissa * 2^exponent)/10^i) % 10^9.
 // To do so normally would involve large integers (~1000 bits for doubles), so
 // we use a shortcut. We can avoid calculating 2^exponent / 10^i by using a
 // lookup table. The resulting intermediate value needs to be about 192 bits to
 // store the result with enough precision. Since this is all being done with
 // integers for appropriate precision, we would run into a problem if
 // i > exponent since then 2^exponent / 10^i would be less than 1. To correct
 // for this, the actual calculation done is 2^(exponent + c) / 10^i, and then
 // when multiplying by the mantissa we reverse this by dividing by 2^c, like so:
 // floor((mantissa * table[exponent][i])/(2^c)) % 10^9.
 // This gives a 9 digit value, which is small enough to fit in a 32 bit integer,
 // and that integer is converted into a string as normal, and called a block. In
 // this implementation, the most recent block is buffered, so that if rounding
 // is necessary the block can be adjusted before being written to the output.
 // Any block that is all 9s adds one to the max block counter and doesn't clear
 // the buffer because they can cause the block above them to be rounded up.

 namespace __llvm_libc {

 using BlockInt = uint32_t;
 constexpr size_t BLOCK_SIZE = 9;

 using MantissaInt = fputil::FPBits<long double>::UIntType;

 constexpr size_t POW10_ADDITIONAL_BITS_CALC = 128;
 constexpr size_t POW10_ADDITIONAL_BITS_TABLE = 120;

 constexpr size_t MID_INT_SIZE = 192;

 namespace internal {

 // Returns floor(log_10(2^e)); requires 0 <= e <= 1650.
 LIBC_INLINE constexpr uint32_t log10_pow2(const uint32_t e) {
   // The first value this approximation fails for is 2^1651 which is just
   // greater than 10^297.
   LIBC_ASSERT(e >= 0 && e <= 1650 &&
               "Incorrect exponent to perform log10_pow2 approximation.");
   return (e * 78913) >> 18;
 }

 // Returns 1 + floor(log_10(2^e). This could technically be off by 1 if any
 // power of 2 was also a power of 10, but since that doesn't exist this is
 // always accurate. This is used to calculate the maximum number of base-10
 // digits a given e-bit number could have.
 LIBC_INLINE constexpr uint32_t ceil_log10_pow2(const uint32_t e) {
   return log10_pow2(e) + 1;
 }

 // Returns the maximum number of 9 digit blocks a number described by the given
 // index (which is ceil(exponent/16)) and mantissa width could need.
 LIBC_INLINE constexpr uint32_t length_for_num(const uint32_t idx,
                                               const uint32_t mantissa_width) {
   //+8 to round up when dividing by 9
   return (ceil_log10_pow2(16 * idx) + ceil_log10_pow2(mantissa_width) +
           (BLOCK_SIZE - 1)) /
          BLOCK_SIZE;
   // return (ceil_log10_pow2(16 * idx + mantissa_width) + 8) / 9;
 }

 // The formula for the table when i is positive (or zero) is as follows:
 // floor(10^(-9i) * 2^(e + c_1) + 1) % (10^9 * 2^c_1)
 // Rewritten slightly we get:
 // floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)

 // TODO: Fix long doubles (needs bigger table or alternate algorithm.)
 // Currently the table values are generated, which is very slow.
 template <size_t INT_SIZE>
 LIBC_INLINE constexpr cpp::UInt<MID_INT_SIZE>
 get_table_positive(int exponent, size_t i, const size_t constant) {
   // INT_SIZE is the size of int that is used for the internal calculations of
   // this function. It should be large enough to hold 2^(exponent+constant), so
   // ~1000 for double and ~16000 for long double. Be warned that the time
   // complexity of exponentiation is O(n^2 * log_2(m)) where n is the number of
   // bits in the number being exponentiated and m is the exponent.
   int shift_amount = exponent + constant - (9 * i);
   if (shift_amount < 0) {
     return 1;
   }
   cpp::UInt<INT_SIZE> num(0);
   // MOD_SIZE is one of the limiting factors for how big the constant argument
   // can get, since it needs to be small enough to fit in the result UInt,
   // otherwise we'll get truncation on return.
   const cpp::UInt<INT_SIZE> MOD_SIZE =
       (cpp::UInt<INT_SIZE>(1) << constant) * 1000000000;
   constexpr uint64_t FIVE_EXP_NINE = 1953125;

   num = cpp::UInt<INT_SIZE>(1) << (shift_amount);
   if (i > 0) {
     cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
     fives.pow_n(i);
     num = num / fives;
   }

   num = num + 1;
   if (num > MOD_SIZE) {
     num = num % MOD_SIZE;
   }
   return num;
 }

 // The formula for the table when i is negative (or zero) is as follows:
 // floor(10^(-9i) * 2^(c_0 - e)) % (10^9 * 2^c_0)
 // Since we know i is always negative, we just take it as unsigned and treat it
 // as negative. We do the same with exponent, while they're both always negative
 // in theory, in practice they're converted to positive for simpler
 // calculations.
 // The formula being used looks more like this:
 // floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
 LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_negative(int exponent, size_t i,
                                                        const size_t constant) {
   constexpr size_t INT_SIZE = 1024;
   int shift_amount = constant - exponent;
   cpp::UInt<INT_SIZE> num(1);
   // const cpp::UInt<INT_SIZE> MOD_SIZE =
   //     (cpp::UInt<INT_SIZE>(1) << constant) * 1000000000;

   constexpr uint64_t TEN_EXP_NINE = 1000000000;
   constexpr uint64_t FIVE_EXP_NINE = 1953125;
   size_t ten_blocks = i;
   size_t five_blocks = 0;
   if (shift_amount < 0) {
     int block_shifts = (-shift_amount) / 9;
     if (block_shifts < static_cast<int>(ten_blocks)) {
       ten_blocks = ten_blocks - block_shifts;
       five_blocks = block_shifts;
       shift_amount = shift_amount + (block_shifts * 9);
     } else {
       ten_blocks = 0;
       five_blocks = i;
       shift_amount = shift_amount + (i * 9);
     }
   }

   if (five_blocks > 0) {
     cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
     fives.pow_n(five_blocks);
     num *= fives;
   }
   if (ten_blocks > 0) {
     cpp::UInt<INT_SIZE> tens(TEN_EXP_NINE);
     tens.pow_n(ten_blocks);
     num *= tens;
   }

   if (shift_amount > 0) {
     num = num << shift_amount;
   } else {
     num = num >> (-shift_amount);
   }
   // if (num > MOD_SIZE) {
   //   num = num % MOD_SIZE;
   // }
   return num;
 }

 LIBC_INLINE uint32_t fast_uint_mod_1e9(const cpp::UInt<MID_INT_SIZE> &val) {
   // The formula for mult_const is:
   //  1 + floor((2^(bits in target integer size + log_2(divider))) / divider)
   // Where divider is 10^9 and target integer size is 128.
   const cpp::UInt<MID_INT_SIZE> mult_const(
       {0x31680A88F8953031u, 0x89705F4136B4A597u, 0});
   const auto middle = (mult_const * val);
   const uint64_t result = static_cast<uint64_t>(middle[2]);
   const uint32_t shifted = result >> 29;
   return static_cast<uint32_t>(val) - (1000000000 * shifted);
 }

 LIBC_INLINE uint32_t mul_shift_mod_1e9(const MantissaInt mantissa,
                                        const cpp::UInt<MID_INT_SIZE> &large,
                                        const int32_t shift_amount) {
   constexpr size_t MANT_INT_SIZE = sizeof(MantissaInt) * 8;
   cpp::UInt<MID_INT_SIZE + MANT_INT_SIZE> val(large);
   // TODO: Find a better way to force __uint128_t to be UInt<128>
   cpp::UInt<MANT_INT_SIZE> wide_mant(0);
   wide_mant[0] = mantissa & (uint64_t(-1));
   wide_mant[1] = mantissa >> 64;
   val = (val * wide_mant) >> shift_amount;
   return fast_uint_mod_1e9(val);
 }

 } // namespace internal

 // Convert floating point values to their string representation.
 // Because the result may not fit in a reasonably sized array, the caller must
 // request blocks of digits and convert them from integers to strings themself.
 // Blocks contain the most digits that can be stored in an BlockInt. This is 9
 // digits for a 32 bit int and 18 digits for a 64 bit int.
 // The intended use pattern is to create a FloatToString object of the
 // appropriate type, then call get_positive_blocks to get an approximate number
 // of blocks there are before the decimal point. Now the client code can start
 // calling get_positive_block in a loop from the number of positive blocks to
 // zero. This will give all digits before the decimal point. Then the user can
 // start calling get_negative_block in a loop from 0 until the number of digits
 // they need is reached. As an optimization, the client can use
 // zero_blocks_after_point to find the number of blocks that are guaranteed to
 // be zero after the decimal point and before the non-zero digits. Additionally,
 // is_lowest_block will return if the current block is the lowest non-zero
 // block.
 template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
 class FloatToString {
   fputil::FPBits<T> float_bits;
   bool is_negative;
   int exponent;
   MantissaInt mantissa;

   static constexpr int MANT_WIDTH = fputil::MantissaWidth<T>::VALUE;
   static constexpr int EXP_BIAS = fputil::FPBits<T>::EXPONENT_BIAS;

   // constexpr void init_convert();

 public:
   LIBC_INLINE constexpr FloatToString(T init_float) : float_bits(init_float) {
     is_negative = float_bits.get_sign();
     exponent = float_bits.get_exponent();
     mantissa = float_bits.get_explicit_mantissa();

     // Handle the exponent for numbers with a 0 exponent.
     if (exponent == -EXP_BIAS) {
       if (mantissa > 0) { // Subnormals
         ++exponent;
       } else { // Zeroes
         exponent = 0;
       }
     }

     // Adjust for the width of the mantissa.
     exponent -= MANT_WIDTH;

     // init_convert();
   }

   LIBC_INLINE constexpr bool is_nan() { return float_bits.is_nan(); }
   LIBC_INLINE constexpr bool is_inf() { return float_bits.is_inf(); }
   LIBC_INLINE constexpr bool is_inf_or_nan() {
     return float_bits.is_inf_or_nan();
   }

   // get_block returns an integer that represents the digits in the requested
   // block.
   LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {
     if (exponent >= -MANT_WIDTH) {
       // idx is ceil(exponent/16) or 0 if exponent is negative. This is used to
       // find the coarse section of the POW10_SPLIT table that will be used to
       // calculate the 9 digit window, as well as some other related values.
       const uint32_t idx =
           exponent < 0 ? 0 : static_cast<uint32_t>(exponent + 15) / 16;

       uint32_t temp_shift_amount =
           POW10_ADDITIONAL_BITS_TABLE + (16 * idx) - exponent;
       const uint32_t shift_amount = temp_shift_amount;
       // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
       // exponent

       int32_t i = block_index;
       cpp::UInt<MID_INT_SIZE> val;
       val = POW10_SPLIT[POW10_OFFSET[idx] + i];

       const uint32_t digits =
           internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));
       return digits;
     } else {
       return 0;
     }
   }

   LIBC_INLINE constexpr BlockInt get_negative_block(int block_index) {
     if (exponent < 0) {
       const int32_t idx = -exponent / 16;
       uint32_t i = block_index;
       // if the requested block is zero
       if (i < MIN_BLOCK_2[idx]) {
         return 0;
       }
       const int32_t shift_amount =
           POW10_ADDITIONAL_BITS_TABLE + (-exponent - 16 * idx);
       const uint32_t p = POW10_OFFSET_2[idx] + i - MIN_BLOCK_2[idx];
       // If every digit after the requested block is zero.
       if (p >= POW10_OFFSET_2[idx + 1]) {
         return 0;
       }

       cpp::UInt<MID_INT_SIZE> table_val = POW10_SPLIT_2[p];
       // cpp::UInt<MID_INT_SIZE> calculated_val =
       //     get_table_negative(idx * 16, i + 1, POW10_ADDITIONAL_BITS_CALC);
       uint32_t digits =
           internal::mul_shift_mod_1e9(mantissa, table_val, shift_amount);
       return digits;
     } else {
       return 0;
     }
   }

   LIBC_INLINE constexpr BlockInt get_block(int block_index) {
     if (block_index >= 0) {
       return get_positive_block(block_index);
     } else {
       return get_negative_block(-1 - block_index);
     }
   }

   LIBC_INLINE constexpr size_t get_positive_blocks() {
     if (exponent >= -MANT_WIDTH) {
       const uint32_t idx =
           exponent < 0 ? 0 : static_cast<uint32_t>(exponent + 15) / 16;
       const uint32_t len = internal::length_for_num(idx, MANT_WIDTH);
       return len;
     } else {
       return 0;
     }
   }

   // This takes the index of a block after the decimal point (a negative block)
   // and return if it's sure that all of the digits after it are zero.
   LIBC_INLINE constexpr bool is_lowest_block(size_t block_index) {
     const int32_t idx = -exponent / 16;
     const uint32_t p = POW10_OFFSET_2[idx] + block_index - MIN_BLOCK_2[idx];
     // If the remaining digits are all 0, then this is the lowest block.
     return p >= POW10_OFFSET_2[idx + 1];
   }

   LIBC_INLINE constexpr size_t zero_blocks_after_point() {
     return MIN_BLOCK_2[-exponent / 16];
   }
 };

 // template <> constexpr void FloatToString<float>::init_convert() { ; }

 // template <> constexpr void FloatToString<double>::init_convert() { ; }

 // template <> constexpr void FloatToString<long double>::init_convert() {
 //   // TODO: More here.
 //   ;
 // }

 template <>
 LIBC_INLINE constexpr size_t
 FloatToString<long double>::zero_blocks_after_point() {
   return 0;
 }

 template <>
 LIBC_INLINE constexpr bool FloatToString<long double>::is_lowest_block(size_t) {
   return false;
 }

 template <>
 LIBC_INLINE constexpr BlockInt
 FloatToString<long double>::get_positive_block(int block_index) {
   if (exponent >= -MANT_WIDTH) {
     const uint32_t pos_exp = (exponent < 0 ? 0 : exponent);

     uint32_t temp_shift_amount =
         POW10_ADDITIONAL_BITS_CALC + pos_exp - exponent;
     const uint32_t shift_amount = temp_shift_amount;
     // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
     // exponent

     int32_t i = block_index;
     cpp::UInt<MID_INT_SIZE> val;
     if (exponent + POW10_ADDITIONAL_BITS_CALC < 1024) {
       val = internal::get_table_positive<1024>(pos_exp, i,
                                                POW10_ADDITIONAL_BITS_CALC);
     } else if (exponent + POW10_ADDITIONAL_BITS_CALC < 4096) {
       val = internal::get_table_positive<4096>(pos_exp, i,
                                                POW10_ADDITIONAL_BITS_CALC);
     } else if (exponent + POW10_ADDITIONAL_BITS_CALC < 8192) {
       val = internal::get_table_positive<8192>(pos_exp, i,
                                                POW10_ADDITIONAL_BITS_CALC);
     } else {
       val = internal::get_table_positive<16384>(pos_exp, i,
                                                 POW10_ADDITIONAL_BITS_CALC);
     }

     const BlockInt digits =
         internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));
     return digits;
   } else {
     return 0;
   }
 }

 template <>
 LIBC_INLINE constexpr BlockInt
 FloatToString<long double>::get_negative_block(int block_index) {
   if (exponent < 0) {
     const int32_t idx = -exponent / 16;
     uint32_t i = -1 - block_index;
     // if the requested block is zero
     if (i <= MIN_BLOCK_2[idx]) {
       return 0;
     }
     const int32_t shift_amount =
         POW10_ADDITIONAL_BITS_CALC + (-exponent - 16 * idx);
     const uint32_t p = POW10_OFFSET_2[idx] + i - MIN_BLOCK_2[idx];
     // If every digit after the requested block is zero.
     if (p >= POW10_OFFSET_2[idx + 1]) {
       return 0;
     }

     // cpp::UInt<MID_INT_SIZE> table_val = POW10_SPLIT_2[p];
     cpp::UInt<MID_INT_SIZE> calculated_val = internal::get_table_negative(
         idx * 16, i + 1, POW10_ADDITIONAL_BITS_CALC);
     BlockInt digits =
         internal::mul_shift_mod_1e9(mantissa, calculated_val, shift_amount);
     return digits;
   } else {
     return 0;
   }
 }

 } // namespace __llvm_libc

 #endif // LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
	//===-- Utilities to convert floating point values to string ----- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#ifndef LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H
	#define LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H

	#include <stdint.h>

	#include "src/__support/CPP/type_traits.h"
	#include "src/__support/FPUtil/FPBits.h"
	#include "src/__support/UInt.h"
	#include "src/__support/common.h"
	#include "src/__support/libc_assert.h"
	#include "src/__support/ryu_constants.h"

	// This implementation is based on the Ryu Printf algorithm by Ulf Adams:
	// Ulf Adams. 2019. Ryū revisited: printf floating point conversion.
	// Proc. ACM Program. Lang. 3, OOPSLA, Article 169 (October 2019), 23 pages.
	// https://doi.org/10.1145/3360595

	// This version is modified to require significantly less memory (it doesn't use
	// a large buffer to store the result).

	// The general concept of this algorithm is as follows:
	// We want to calculate a 9 digit segment of a floating point number using this
	// formula: floor((mantissa * 2^exponent)/10^i) % 10^9.
	// To do so normally would involve large integers (~1000 bits for doubles), so
	// we use a shortcut. We can avoid calculating 2^exponent / 10^i by using a
	// lookup table. The resulting intermediate value needs to be about 192 bits to
	// store the result with enough precision. Since this is all being done with
	// integers for appropriate precision, we would run into a problem if
	// i > exponent since then 2^exponent / 10^i would be less than 1. To correct
	// for this, the actual calculation done is 2^(exponent + c) / 10^i, and then
	// when multiplying by the mantissa we reverse this by dividing by 2^c, like so:
	// floor((mantissa * table[exponent][i])/(2^c)) % 10^9.
	// This gives a 9 digit value, which is small enough to fit in a 32 bit integer,
	// and that integer is converted into a string as normal, and called a block. In
	// this implementation, the most recent block is buffered, so that if rounding
	// is necessary the block can be adjusted before being written to the output.
	// Any block that is all 9s adds one to the max block counter and doesn't clear
	// the buffer because they can cause the block above them to be rounded up.

	namespace __llvm_libc {

	using BlockInt = uint32_t;
	constexpr size_t BLOCK_SIZE = 9;

	using MantissaInt = fputil::FPBits<long double>::UIntType;

	constexpr size_t POW10_ADDITIONAL_BITS_CALC = 128;
	constexpr size_t POW10_ADDITIONAL_BITS_TABLE = 120;

	constexpr size_t MID_INT_SIZE = 192;

	namespace internal {

	// Returns floor(log_10(2^e)); requires 0 <= e <= 1650.
	LIBC_INLINE constexpr uint32_t log10_pow2(const uint32_t e) {
	// The first value this approximation fails for is 2^1651 which is just
	// greater than 10^297.
	LIBC_ASSERT(e >= 0 && e <= 1650 &&
	"Incorrect exponent to perform log10_pow2 approximation.");
	return (e * 78913) >> 18;
	}

	// Returns 1 + floor(log_10(2^e). This could technically be off by 1 if any
	// power of 2 was also a power of 10, but since that doesn't exist this is
	// always accurate. This is used to calculate the maximum number of base-10
	// digits a given e-bit number could have.
	LIBC_INLINE constexpr uint32_t ceil_log10_pow2(const uint32_t e) {
	return log10_pow2(e) + 1;
	}

	// Returns the maximum number of 9 digit blocks a number described by the given
	// index (which is ceil(exponent/16)) and mantissa width could need.
	LIBC_INLINE constexpr uint32_t length_for_num(const uint32_t idx,
	const uint32_t mantissa_width) {
	//+8 to round up when dividing by 9
	return (ceil_log10_pow2(16 * idx) + ceil_log10_pow2(mantissa_width) +
	(BLOCK_SIZE - 1)) /
	BLOCK_SIZE;
	// return (ceil_log10_pow2(16 * idx + mantissa_width) + 8) / 9;
	}

	// The formula for the table when i is positive (or zero) is as follows:
	// floor(10^(-9i) * 2^(e + c_1) + 1) % (10^9 * 2^c_1)
	// Rewritten slightly we get:
	// floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)

	// TODO: Fix long doubles (needs bigger table or alternate algorithm.)
	// Currently the table values are generated, which is very slow.
	template <size_t INT_SIZE>
	LIBC_INLINE constexpr cpp::UInt<MID_INT_SIZE>
	get_table_positive(int exponent, size_t i, const size_t constant) {
	// INT_SIZE is the size of int that is used for the internal calculations of
	// this function. It should be large enough to hold 2^(exponent+constant), so
	// ~1000 for double and ~16000 for long double. Be warned that the time
	// complexity of exponentiation is O(n^2 * log_2(m)) where n is the number of
	// bits in the number being exponentiated and m is the exponent.
	int shift_amount = exponent + constant - (9 * i);
	if (shift_amount < 0) {
	return 1;
	}
	cpp::UInt<INT_SIZE> num(0);
	// MOD_SIZE is one of the limiting factors for how big the constant argument
	// can get, since it needs to be small enough to fit in the result UInt,
	// otherwise we'll get truncation on return.
	const cpp::UInt<INT_SIZE> MOD_SIZE =
	(cpp::UInt<INT_SIZE>(1) << constant) * 1000000000;
	constexpr uint64_t FIVE_EXP_NINE = 1953125;

	num = cpp::UInt<INT_SIZE>(1) << (shift_amount);
	if (i > 0) {
	cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
	fives.pow_n(i);
	num = num / fives;
	}

	num = num + 1;
	if (num > MOD_SIZE) {
	num = num % MOD_SIZE;
	}
	return num;
	}

	// The formula for the table when i is negative (or zero) is as follows:
	// floor(10^(-9i) * 2^(c_0 - e)) % (10^9 * 2^c_0)
	// Since we know i is always negative, we just take it as unsigned and treat it
	// as negative. We do the same with exponent, while they're both always negative
	// in theory, in practice they're converted to positive for simpler
	// calculations.
	// The formula being used looks more like this:
	// floor(10^(9(-i)) 2^(c_0 + (-e))) % (10^9 * 2^c_0)
	LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_negative(int exponent, size_t i,
	const size_t constant) {
	constexpr size_t INT_SIZE = 1024;
	int shift_amount = constant - exponent;
	cpp::UInt<INT_SIZE> num(1);
	// const cpp::UInt<INT_SIZE> MOD_SIZE =
	// (cpp::UInt<INT_SIZE>(1) << constant) * 1000000000;

	constexpr uint64_t TEN_EXP_NINE = 1000000000;
	constexpr uint64_t FIVE_EXP_NINE = 1953125;
	size_t ten_blocks = i;
	size_t five_blocks = 0;
	if (shift_amount < 0) {
	int block_shifts = (-shift_amount) / 9;
	if (block_shifts < static_cast<int>(ten_blocks)) {
	ten_blocks = ten_blocks - block_shifts;
	five_blocks = block_shifts;
	shift_amount = shift_amount + (block_shifts * 9);
	} else {
	ten_blocks = 0;
	five_blocks = i;
	shift_amount = shift_amount + (i * 9);
	}
	}

	if (five_blocks > 0) {
	cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
	fives.pow_n(five_blocks);
	num *= fives;
	}
	if (ten_blocks > 0) {
	cpp::UInt<INT_SIZE> tens(TEN_EXP_NINE);
	tens.pow_n(ten_blocks);
	num *= tens;
	}

	if (shift_amount > 0) {
	num = num << shift_amount;
	} else {
	num = num >> (-shift_amount);
	}
	// if (num > MOD_SIZE) {
	// num = num % MOD_SIZE;
	// }
	return num;
	}

	LIBC_INLINE uint32_t fast_uint_mod_1e9(const cpp::UInt<MID_INT_SIZE> &val) {
	// The formula for mult_const is:
	// 1 + floor((2^(bits in target integer size + log_2(divider))) / divider)
	// Where divider is 10^9 and target integer size is 128.
	const cpp::UInt<MID_INT_SIZE> mult_const(
	{0x31680A88F8953031u, 0x89705F4136B4A597u, 0});
	const auto middle = (mult_const * val);
	const uint64_t result = static_cast<uint64_t>(middle[2]);
	const uint32_t shifted = result >> 29;
	return static_cast<uint32_t>(val) - (1000000000 * shifted);
	}

	LIBC_INLINE uint32_t mul_shift_mod_1e9(const MantissaInt mantissa,
	const cpp::UInt<MID_INT_SIZE> &large,
	const int32_t shift_amount) {
	constexpr size_t MANT_INT_SIZE = sizeof(MantissaInt) * 8;
	cpp::UInt<MID_INT_SIZE + MANT_INT_SIZE> val(large);
	// TODO: Find a better way to force __uint128_t to be UInt<128>
	cpp::UInt<MANT_INT_SIZE> wide_mant(0);
	wide_mant[0] = mantissa & (uint64_t(-1));
	wide_mant[1] = mantissa >> 64;
	val = (val * wide_mant) >> shift_amount;
	return fast_uint_mod_1e9(val);
	}

	} // namespace internal

	// Convert floating point values to their string representation.
	// Because the result may not fit in a reasonably sized array, the caller must
	// request blocks of digits and convert them from integers to strings themself.
	// Blocks contain the most digits that can be stored in an BlockInt. This is 9
	// digits for a 32 bit int and 18 digits for a 64 bit int.
	// The intended use pattern is to create a FloatToString object of the
	// appropriate type, then call get_positive_blocks to get an approximate number
	// of blocks there are before the decimal point. Now the client code can start
	// calling get_positive_block in a loop from the number of positive blocks to
	// zero. This will give all digits before the decimal point. Then the user can
	// start calling get_negative_block in a loop from 0 until the number of digits
	// they need is reached. As an optimization, the client can use
	// zero_blocks_after_point to find the number of blocks that are guaranteed to
	// be zero after the decimal point and before the non-zero digits. Additionally,
	// is_lowest_block will return if the current block is the lowest non-zero
	// block.
	template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
	class FloatToString {
	fputil::FPBits<T> float_bits;
	bool is_negative;
	int exponent;
	MantissaInt mantissa;

	static constexpr int MANT_WIDTH = fputil::MantissaWidth<T>::VALUE;
	static constexpr int EXP_BIAS = fputil::FPBits<T>::EXPONENT_BIAS;

	// constexpr void init_convert();

	public:
	LIBC_INLINE constexpr FloatToString(T init_float) : float_bits(init_float) {
	is_negative = float_bits.get_sign();
	exponent = float_bits.get_exponent();
	mantissa = float_bits.get_explicit_mantissa();

	// Handle the exponent for numbers with a 0 exponent.
	if (exponent == -EXP_BIAS) {
	if (mantissa > 0) { // Subnormals
	++exponent;
	} else { // Zeroes
	exponent = 0;
	}
	}

	// Adjust for the width of the mantissa.
	exponent -= MANT_WIDTH;

	// init_convert();
	}

	LIBC_INLINE constexpr bool is_nan() { return float_bits.is_nan(); }
	LIBC_INLINE constexpr bool is_inf() { return float_bits.is_inf(); }
	LIBC_INLINE constexpr bool is_inf_or_nan() {
	return float_bits.is_inf_or_nan();
	}

	// get_block returns an integer that represents the digits in the requested
	// block.
	LIBC_INLINE constexpr BlockInt get_positive_block(int block_index) {
	if (exponent >= -MANT_WIDTH) {
	// idx is ceil(exponent/16) or 0 if exponent is negative. This is used to
	// find the coarse section of the POW10_SPLIT table that will be used to
	// calculate the 9 digit window, as well as some other related values.
	const uint32_t idx =
	exponent < 0 ? 0 : static_cast<uint32_t>(exponent + 15) / 16;

	uint32_t temp_shift_amount =
	POW10_ADDITIONAL_BITS_TABLE + (16 * idx) - exponent;
	const uint32_t shift_amount = temp_shift_amount;
	// shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
	// exponent

	int32_t i = block_index;
	cpp::UInt<MID_INT_SIZE> val;
	val = POW10_SPLIT[POW10_OFFSET[idx] + i];

	const uint32_t digits =
	internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));
	return digits;
	} else {
	return 0;
	}
	}

	LIBC_INLINE constexpr BlockInt get_negative_block(int block_index) {
	if (exponent < 0) {
	const int32_t idx = -exponent / 16;
	uint32_t i = block_index;
	// if the requested block is zero
	if (i < MIN_BLOCK_2[idx]) {
	return 0;
	}
	const int32_t shift_amount =
	POW10_ADDITIONAL_BITS_TABLE + (-exponent - 16 * idx);
	const uint32_t p = POW10_OFFSET_2[idx] + i - MIN_BLOCK_2[idx];
	// If every digit after the requested block is zero.
	if (p >= POW10_OFFSET_2[idx + 1]) {
	return 0;
	}

	cpp::UInt<MID_INT_SIZE> table_val = POW10_SPLIT_2[p];
	// cpp::UInt<MID_INT_SIZE> calculated_val =
	// get_table_negative(idx * 16, i + 1, POW10_ADDITIONAL_BITS_CALC);
	uint32_t digits =
	internal::mul_shift_mod_1e9(mantissa, table_val, shift_amount);
	return digits;
	} else {
	return 0;
	}
	}

	LIBC_INLINE constexpr BlockInt get_block(int block_index) {
	if (block_index >= 0) {
	return get_positive_block(block_index);
	} else {
	return get_negative_block(-1 - block_index);
	}
	}

	LIBC_INLINE constexpr size_t get_positive_blocks() {
	if (exponent >= -MANT_WIDTH) {
	const uint32_t idx =
	exponent < 0 ? 0 : static_cast<uint32_t>(exponent + 15) / 16;
	const uint32_t len = internal::length_for_num(idx, MANT_WIDTH);
	return len;
	} else {
	return 0;
	}
	}

	// This takes the index of a block after the decimal point (a negative block)
	// and return if it's sure that all of the digits after it are zero.
	LIBC_INLINE constexpr bool is_lowest_block(size_t block_index) {
	const int32_t idx = -exponent / 16;
	const uint32_t p = POW10_OFFSET_2[idx] + block_index - MIN_BLOCK_2[idx];
	// If the remaining digits are all 0, then this is the lowest block.
	return p >= POW10_OFFSET_2[idx + 1];
	}

	LIBC_INLINE constexpr size_t zero_blocks_after_point() {
	return MIN_BLOCK_2[-exponent / 16];
	}
	};

	// template <> constexpr void FloatToString<float>::init_convert() { ; }

	// template <> constexpr void FloatToString<double>::init_convert() { ; }

	// template <> constexpr void FloatToString<long double>::init_convert() {
	// // TODO: More here.
	// ;
	// }

	template <>
	LIBC_INLINE constexpr size_t
	FloatToString<long double>::zero_blocks_after_point() {
	return 0;
	}

	template <>
	LIBC_INLINE constexpr bool FloatToString<long double>::is_lowest_block(size_t) {
	return false;
	}

	template <>
	LIBC_INLINE constexpr BlockInt
	FloatToString<long double>::get_positive_block(int block_index) {
	if (exponent >= -MANT_WIDTH) {
	const uint32_t pos_exp = (exponent < 0 ? 0 : exponent);

	uint32_t temp_shift_amount =
	POW10_ADDITIONAL_BITS_CALC + pos_exp - exponent;
	const uint32_t shift_amount = temp_shift_amount;
	// shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) -
	// exponent

	int32_t i = block_index;
	cpp::UInt<MID_INT_SIZE> val;
	if (exponent + POW10_ADDITIONAL_BITS_CALC < 1024) {
	val = internal::get_table_positive<1024>(pos_exp, i,
	POW10_ADDITIONAL_BITS_CALC);
	} else if (exponent + POW10_ADDITIONAL_BITS_CALC < 4096) {
	val = internal::get_table_positive<4096>(pos_exp, i,
	POW10_ADDITIONAL_BITS_CALC);
	} else if (exponent + POW10_ADDITIONAL_BITS_CALC < 8192) {
	val = internal::get_table_positive<8192>(pos_exp, i,
	POW10_ADDITIONAL_BITS_CALC);
	} else {
	val = internal::get_table_positive<16384>(pos_exp, i,
	POW10_ADDITIONAL_BITS_CALC);
	}

	const BlockInt digits =
	internal::mul_shift_mod_1e9(mantissa, val, (int32_t)(shift_amount));
	return digits;
	} else {
	return 0;
	}
	}

	template <>
	LIBC_INLINE constexpr BlockInt
	FloatToString<long double>::get_negative_block(int block_index) {
	if (exponent < 0) {
	const int32_t idx = -exponent / 16;
	uint32_t i = -1 - block_index;
	// if the requested block is zero
	if (i <= MIN_BLOCK_2[idx]) {
	return 0;
	}
	const int32_t shift_amount =
	POW10_ADDITIONAL_BITS_CALC + (-exponent - 16 * idx);
	const uint32_t p = POW10_OFFSET_2[idx] + i - MIN_BLOCK_2[idx];
	// If every digit after the requested block is zero.
	if (p >= POW10_OFFSET_2[idx + 1]) {
	return 0;
	}

	// cpp::UInt<MID_INT_SIZE> table_val = POW10_SPLIT_2[p];
	cpp::UInt<MID_INT_SIZE> calculated_val = internal::get_table_negative(
	idx * 16, i + 1, POW10_ADDITIONAL_BITS_CALC);
	BlockInt digits =
	internal::mul_shift_mod_1e9(mantissa, calculated_val, shift_amount);
	return digits;
	} else {
	return 0;
	}
	}

	} // namespace __llvm_libc

	#endif // LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H