[libc] add options to printf decimal floats

[michaelrj]

Summary

This patch adds three options for printf decimal long doubles, and these
can also apply to doubles.

1. Use a giant table which is fast and accurate, but takes up ~5MB).
2. Use dyadic floats for approximations, which only gives ~50 digits of accuracy but is very fast.
3. Use large integers for approximations, which is accurate but very slow.

[michaelrj]

Currently ryu_long_double_constants is empty, this is because it's 12 megabytes and arcanist complains when I try to upload it. I can add it for testing purposes, or you can generate it yourself with ryu_tablegen.py. It writes to the console so pipe it to a file. You'll also need to set POW10_ADDITIONAL_BITS_TABLE to 120, IDX_SIZE to 128, and MID_INT_SIZE to 320 in ryu_long_double_constants.h.

This patch isn't quite done yet, I still need to add an interface for the compile flags, but I wanted to get it out so that other people can review the math and overall design.

[lntue]

libc/src/__support/float_to_string.h

171

You could also mention that 50 digits is more than enough for the round trip long double -> decimal string -> long double to be correct, even when long double is quad precision (i.e. float128).

193

You can add a mul_pow_2 method that simply adds the exponent field in-place for a DyadicFloat.

[michaelrj]

cleanup for all three modes after some testing.

[lntue]

libc/src/__support/float_to_string.h

531–536

Are those still relevant?

554–559

Are those still relevant?

585

The definitions of shift_amount are the same in all branches?

628

The definitions of shift_amount are the same in all branches?

[michaelrj]

libc/src/__support/float_to_string.h

585

not quite, the table mode shift_amount uses POW10_ADDITIONAL_BITS_TABLE instead of POW10_ADDITIONAL_BITS_CALC. I'm going to rename those variables to avoid this confusion.

[michaelrj]

updates and cleanup

[lntue]

libc/src/__support/FPUtil/dyadic_float.h

128

Use in-place <<= or add it to UInt if missing.

130

Use in-place >>= or add it to UInt if missing.

libc/src/__support/float_to_string.h

144

I'm just curious, will changing from 1000000000 * 2^(...) to 1953125 * 2^(... + 9) has any affect, like performance or accuracy? Same with other instances below.

326

Use val.div_uint32_times_pow_2(1000000000, 0) to speed up?

[michaelrj]

address comments, still need to mess with the is_lowest_block and zero_blocks_after_point functions. They aren't strictly necessary, but they do provide significant speed improvements.

libc/src/__support/float_to_string.h

144

This number is constexpr, so there should be no change.

554–559

I need to see if I can fix their calculations to make them work, but they should speed up the int mode.

[sivachandra]

Just minor comments but LGTM.

libc/src/__support/float_to_string.h

21

s/LIBC_COPT_FLOAT_TO_STR_USE_MEGA_TABLE/LIBC_COPT_FLOAT_TO_STR_USE_LARGE_LONG_DOUBLE_TABLE

409

Add commentary about how the options here compare.

libc/utils/mathtools/ryu_tablegen.py

2

Add comments about usage of this script.

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

304 ↗

(On Diff #525852)

Either remove or add comments about why this is commented out.

[michaelrj]

add comments explaining compile flags in float_to_string.h and the constants in ryu_tablegen.py

libc/src/__support/float_to_string.h

21

I like the name MEGA_TABLE since the table is several megabytes in size. Additionally, when the mega table is enabled it's used for both doubles and long doubles.

409

I've added it to the top of the file.

[sivachandra]

libc/src/__support/float_to_string.h

21

You can choose to keep MEGA in there but the name should reflect that it is about long doubles. So, I suggest to make it: ..._USE_MEGA_LONG_DOUBLE_TABLE.

[michaelrj]

rename to LIBC_COPT_FLOAT_TO_STR_USE_MEGA_LONG_DOUBLE_TABLE

libc/src/__support/FPUtil/dyadic_float.h

template <size_t Bits> struct DyadicFloat {
   DyadicFloat(T x) {
     FPBits<T> x_bits(x);
     sign = x_bits.get_sign();
     exponent = x_bits.get_exponent() - FloatProperties<T>::MANTISSA_WIDTH;
     mantissa = MantissaType(x_bits.get_explicit_mantissa());
     normalize();
   }
 
-  DyadicFloat(bool s, int e, MantissaType m)
+  constexpr DyadicFloat(bool s, int e, MantissaType m)
       : sign(s), exponent(e), mantissa(m) {
     normalize();
   }
 
   // Normalizing the mantissa, bringing the leading 1 bit to the most
   // significant bit.
-  DyadicFloat &normalize() {
+  constexpr DyadicFloat &normalize() {
     if (!mantissa.is_zero()) {
       int shift_length = static_cast<int>(mantissa.clz());
       exponent -= shift_length;
       mantissa.shift_left(static_cast<size_t>(shift_length));
     }
     return *this;
   }
 
explicit operator T() const {
     auto d_lo = FPBits<T>::create_value(sign,
                                         exponent + (Bits - PRECISION - 2) +
                                             FloatProperties<T>::EXPONENT_BIAS,
                                         output_bits_t(0));
 
     // Still correct without FMA instructions if `d_lo` is not underflow.
     return multiply_add(d_lo.get_val(), T(round_and_sticky), d_hi.get_val());
   }
+
+  explicit operator MantissaType() const {
+    if (mantissa.is_zero())
+      return 0;
+
+    MantissaType new_mant = mantissa;
+    if (exponent > 0) {
+      new_mant = new_mant << exponent;
+    } else {
+      new_mant = new_mant >> (-exponent);
+    }
+
+    if (sign) {
+      new_mant = (~new_mant) + 1;
+    }
+
+    return new_mant;
+  }
 };
 
 // Quick add - Add 2 dyadic floats with rounding toward 0 and then normalize the
 // output:
 //   - Align the exponents so that:
 //     new a.exponent = new b.exponent = max(a.exponent, b.exponent)
 //   - Add or subtract the mantissas depending on the signs.
 //   - Normalize the result.
if (result.mantissa.val[DyadicFloat<Bits>::MantissaType::WORDCOUNT - 1] >>
         0)
       result.shift_left(1);
   } else {
     result.mantissa = (typename DyadicFloat<Bits>::MantissaType)(0);
   }
   return result;
 }
 
+// simple exponentiation implementation for testing. Only handles positive
+// exponents, since division isn't implemented.
+template <size_t Bits>
+constexpr DyadicFloat<Bits> pow_n(DyadicFloat<Bits> a, uint32_t power) {
+  DyadicFloat<Bits> result = 1.0;
+  DyadicFloat<Bits> cur_power = a;
+
+  while (power > 0) {
+    if ((power % 2) > 0) {
+      result = quick_mul(result, cur_power);
+    }
+    power = power >> 1;
+    cur_power = quick_mul(cur_power, cur_power);
+  }
+  return result;
+}
+
 } // namespace __llvm_libc::fputil
 
 #endif // LLVM_LIBC_SRC_SUPPORT_FPUTIL_DYADIC_FLOAT_H

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/FPUtil/dyadic_float.h"
 #include "src/__support/UInt.h"
 #include "src/__support/common.h"
 #include "src/__support/libc_assert.h"
+
+#ifdef LIBC_COPT_FLOAT_TO_STR_USE_GIANT_TABLE
+#include "src/__support/ryu_long_double_constants.h"
+#elif !defined(LIBC_COPT_FLOAT_TO_STR_NO_TABLE)
 #include "src/__support/ryu_constants.h"
+#else
+constexpr size_t IDX_SIZE = 1;
+constexpr size_t MID_INT_SIZE = 192;
+#endif
 
 // 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).

 
 namespace __llvm_libc {
 
 using BlockInt = uint32_t;
 constexpr size_t BLOCK_SIZE = 9;
 
 using MantissaInt = fputil::FPBits<long double>::UIntType;
 
+// Larger numbers prefer a slightly larger constant than is used for the smaller
+// numbers.
 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 &&
+// Returns floor(log_10(2^e)); requires 0 <= e <= 42039.
+LIBC_INLINE constexpr uint32_t log10_pow2(const uint64_t e) {
+  LIBC_ASSERT(e >= 0 && e <= 42039 &&
               "Incorrect exponent to perform log10_pow2 approximation.");
-  return (e * 78913) >> 18;
+  // This approximation is based on the float value for log_10(2). It first
+  // gives an incorrect result for our purposes at 42039 (well beyond the 16383
+  // maximum for long doubles).
+
+  // To get these constants I first evaluated log_10(2) to get an approximation
+  // of 0.301029996. Next I passed that value through a string to double
+  // conversion to get an explicit mantissa of 0x13441350fbd738 and an exponent
+  // of -2 (which becomes -54 when we shift the mantissa to be a non-fractional
+  // number). Next I shifted the mantissa right 12 bits to create more space for
+  // the multiplication result, adding 12 to the exponent to compensate. To
+  // check that this approximation works for our purposes I used the following
+  // python code:
+  // for i in range(16384):
+  //   if(len(str(2**i)) != (((i*0x13441350fbd)>>42)+1)):
+  //     print(i)
+  // The reason we add 1 is because this evaluation truncates the result, giving
+  // us the floor, whereas counting the digits of the power of 2 gives us the
+  // ceiling. With a similar loop I checked the maximum valid value and found
+  // 42039.
+  return (e * 0x13441350fbdll) >> 42;
+}
+
+// Same as above, but with different constants.
+LIBC_INLINE constexpr uint32_t log2_pow5(const uint64_t e) {
+  return (e * 0x12934f0979bll) >> 39;
 }
 
 // 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) +
+  return (ceil_log10_pow2(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) {
+LIBC_INLINE constexpr cpp::UInt<MID_INT_SIZE> get_table_positive(int exponent,
+                                                                 size_t i) {
   // 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);
+  const int shift_amount = exponent + POW10_ADDITIONAL_BITS_CALC - (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 cpp::UInt<INT_SIZE> MOD_SIZE =
+      (cpp::UInt<INT_SIZE>(1000000000)
+       << (POW10_ADDITIONAL_BITS_CALC + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
+
   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) {
+    // TODO: optimize division, that's clearly the bottleneck here.
     num = num % MOD_SIZE;
   }
   return num;
 }
 
+template <size_t INT_SIZE>
+LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_positive_df(int exponent,
+                                                          size_t i) {
+  static_assert(INT_SIZE == 256,
+                "Only 256 is supported as an int size right now.");
+  // This version uses dyadic floats with 256 bit mantissas to perform the same
+  // calculation as above. Due to floating point imprecision it is only accurate
+  // for the first 50 digits, but it's much faster. This is ideal for embedded
+  // situations that want to avoid the table altogether, and are willing to
+  // sacrifice some accuracy. It should primarily be used with the "%e"
+  // conversion.
+  const int shift_amount = exponent + POW10_ADDITIONAL_BITS_CALC - (9 * i);
+  if (shift_amount < 0) {
+    return 1;
+  }
+  fputil::DyadicFloat<INT_SIZE> num(false, shift_amount, 1);
+  constexpr cpp::UInt<INT_SIZE> MOD_SIZE =
+      (cpp::UInt<INT_SIZE>(1000000000)
+       << (POW10_ADDITIONAL_BITS_CALC + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
+
+  constexpr cpp::UInt<INT_SIZE> FIVE_EXP_MINUS_NINE_MANT{
+      {0xf387295d242602a7, 0xfdd7645e011abac9, 0x31680a88f8953030,
+       0x89705f4136b4a597}};
+
+  static const fputil::DyadicFloat<INT_SIZE> FIVE_EXP_MINUS_NINE(
+      false, -276, FIVE_EXP_MINUS_NINE_MANT);
+
+  if (i > 0) {
+    fputil::DyadicFloat<INT_SIZE> fives = fputil::pow_n(FIVE_EXP_MINUS_NINE, i);
+    num = fputil::quick_mul(num, fives);
+  }
+  cpp::UInt<INT_SIZE> int_num = static_cast<cpp::UInt<INT_SIZE>>(num) + 1;
+  if (int_num > MOD_SIZE) {
+    int_num = int_num % MOD_SIZE;
+  }
+
+  cpp::UInt<MID_INT_SIZE> result = int_num;
+
+  return result;
+}
+
 // 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;
+template <size_t INT_SIZE>
+LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_negative(int exponent, size_t i) {
+  int shift_amount = POW10_ADDITIONAL_BITS_CALC - exponent;
   cpp::UInt<INT_SIZE> num(1);
-  // const cpp::UInt<INT_SIZE> MOD_SIZE =
-  //     (cpp::UInt<INT_SIZE>(1) << constant) * 1000000000;
+  constexpr cpp::UInt<INT_SIZE> MOD_SIZE =
+      (cpp::UInt<INT_SIZE>(1000000000)
+       << (POW10_ADDITIONAL_BITS_CALC + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
 
   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;
+    int block_shifts = (-shift_amount) / BLOCK_SIZE;
     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);
+      shift_amount = shift_amount + (block_shifts * BLOCK_SIZE);
     } else {
       ten_blocks = 0;
       five_blocks = i;
-      shift_amount = shift_amount + (i * 9);
+      shift_amount = shift_amount + (i * BLOCK_SIZE);
     }
   }
 
   if (five_blocks > 0) {
     cpp::UInt<INT_SIZE> fives(FIVE_EXP_NINE);
     fives.pow_n(five_blocks);
-    num *= fives;
+    num = fives;
   }
   if (ten_blocks > 0) {
     cpp::UInt<INT_SIZE> tens(TEN_EXP_NINE);
     tens.pow_n(ten_blocks);
+    if (five_blocks <= 0) {
+      num = tens;
+    } else {
       num *= tens;
     }
+  }
 
   if (shift_amount > 0) {
     num = num << shift_amount;
   } else {
     num = num >> (-shift_amount);
   }
-  // if (num > MOD_SIZE) {
-  //   num = num % MOD_SIZE;
-  // }
+  if (num > MOD_SIZE) {
+    num = num % MOD_SIZE;
+  }
   return num;
 }
 
+template <size_t INT_SIZE>
+LIBC_INLINE cpp::UInt<MID_INT_SIZE> get_table_negative_df(int exponent,
+                                                          size_t i) {
+  static_assert(INT_SIZE == 256,
+                "Only 256 is supported as an int size right now.");
+  // This version uses dyadic floats with 256 bit mantissas to perform the same
+  // calculation as above. Due to floating point imprecision it is only accurate
+  // for the first 50 digits, but it's much faster. This is ideal for embedded
+  // situations that want to avoid the table altogether, and are willing to
+  // sacrifice some accuracy. It should primarily be used with the "%e"
+  // conversion.
+
+  int shift_amount = POW10_ADDITIONAL_BITS_CALC - exponent;
+
+  fputil::DyadicFloat<INT_SIZE> num(false, shift_amount, 1);
+  constexpr cpp::UInt<INT_SIZE> MOD_SIZE =
+      (cpp::UInt<INT_SIZE>(1000000000)
+       << (POW10_ADDITIONAL_BITS_CALC + (IDX_SIZE > 1 ? IDX_SIZE : 0)));
+
+  constexpr cpp::UInt<INT_SIZE> TEN_EXP_NINE_MANT(1000000000);
+
+  static const fputil::DyadicFloat<INT_SIZE> TEN_EXP_NINE(false, 0,
+                                                          TEN_EXP_NINE_MANT);
+
+  if (i > 0) {
+    fputil::DyadicFloat<INT_SIZE> tens = fputil::pow_n(TEN_EXP_NINE, i);
+    num = fputil::quick_mul(num, tens);
+  }
+
+  cpp::UInt<INT_SIZE> int_num = static_cast<cpp::UInt<INT_SIZE>>(num);
+  if (int_num > MOD_SIZE) {
+    int_num = int_num % MOD_SIZE;
+  }
+
+  cpp::UInt<MID_INT_SIZE> result = int_num;
+
+  return result;
+}
+
 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);
+
+  return (val % 1000000000)[0];
+  // 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
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) {
public:
   // 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;
+          exponent < 0
+              ? 0
+              : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
 
-      uint32_t temp_shift_amount =
-          POW10_ADDITIONAL_BITS_TABLE + (16 * idx) - exponent;
-      const uint32_t shift_amount = temp_shift_amount;
+      const uint32_t shift_amount =
+          POW10_ADDITIONAL_BITS_TABLE + (IDX_SIZE * idx) - exponent;
       // 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];
 
+#if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
+      // ----------------------- DYADIC FLOAT CALC MODE ------------------------
+      val = internal::get_table_positive_df<256>(pos_exp, block_index);
+#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
+
+      // ---------------------------- INT CALC MODE ----------------------------
+      const uint64_t MAX_POW_2_SIZE =
+          exponent + POW10_ADDITIONAL_BITS_CALC - (BLOCK_SIZE * block_index);
+      const uint64_t MAX_POW_5_SIZE =
+          internal::log2_pow5(BLOCK_SIZE * block_index);
+      const uint64_t MAX_INT_SIZE =
+          (MAX_POW_2_SIZE > MAX_POW_5_SIZE) ? MAX_POW_2_SIZE : MAX_POW_5_SIZE;
+
+      if (MAX_INT_SIZE < 1024) {
+        val = internal::get_table_positive<1024>(pos_exp, block_index);
+      } else if (MAX_INT_SIZE < 4096) {
+        val = internal::get_table_positive<4096>(pos_exp, block_index);
+      } else if (MAX_INT_SIZE < 8192) {
+        val = internal::get_table_positive<8192>(pos_exp, block_index);
+      } else {
+        val = internal::get_table_positive<16384>(pos_exp, block_index);
+      }
+#else
+      // ----------------------------- TABLE MODE ------------------------------
+      val = POW10_SPLIT[POW10_OFFSET[idx] + i];
+#endif
       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;
+      const int32_t idx = -exponent / IDX_SIZE;
       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);
+          POW10_ADDITIONAL_BITS_TABLE + (-exponent - IDX_SIZE * idx);
+
+      cpp::UInt<MID_INT_SIZE> val;
+#if defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT)
+      // ----------------------- DYADIC FLOAT CALC MODE ------------------------
+      val =
+          internal::get_table_negative_df<256>(idx * IDX_SIZE, block_index + 1);
+#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC)
+
+      // ---------------------------- INT CALC MODE ----------------------------
+      const int calc_shift_amount =
+          POW10_ADDITIONAL_BITS_CALC - (IDX_SIZE * idx);
+      const uint64_t TEN_BLOCKS = block_index + 1;
+      const uint64_t MAX_INT_SIZE =
+          internal::log2_pow5(TEN_BLOCKS) - TEN_BLOCKS;
+
+      if (MAX_INT_SIZE < 1024) {
+        val =
+            internal::get_table_negative<1024>(idx * IDX_SIZE, block_index + 1);
+      } else if (MAX_INT_SIZE < 4096) {
+        val =
+            internal::get_table_negative<4096>(idx * IDX_SIZE, block_index + 1);
+      } else if (MAX_INT_SIZE < 8192) {
+        val =
+            internal::get_table_negative<8192>(idx * IDX_SIZE, block_index + 1);
+      } else if (MAX_INT_SIZE < 16384) {
+        val = internal::get_table_negative<16384>(idx * IDX_SIZE,
+                                                  block_index + 1);
+      } else {
+        val = internal::get_table_negative<32768>(idx * IDX_SIZE,
+                                                  block_index + 1);
+      }
+#else
+      // ----------------------------- TABLE MODE ------------------------------
       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);
+      val = POW10_SPLIT_2[p];
+#endif
       uint32_t digits =
-          internal::mul_shift_mod_1e9(mantissa, table_val, shift_amount);
+          internal::mul_shift_mod_1e9(mantissa, 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);
+          exponent < 0
+              ? 0
+              : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
+      const uint32_t len = internal::length_for_num(idx * IDX_SIZE, 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 int32_t idx = -exponent / IDX_SIZE;
     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];
+    return MIN_BLOCK_2[-exponent / IDX_SIZE];
   }
 };
 
-// template <> constexpr void FloatToString<float>::init_convert() { ; }
+#ifndef LONG_DOUBLE_IS_DOUBLE
+// --------------------------- LONG DOUBLE FUNCTIONS ---------------------------
 
-// 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>::get_positive_blocks() {
+  if (exponent >= -MANT_WIDTH) {
+    const uint32_t idx =
+        exponent < 0
+            ? 0
+            : static_cast<uint32_t>(exponent + (IDX_SIZE - 1)) / IDX_SIZE;
+    const uint32_t len = internal::length_for_num(idx * IDX_SIZE, MANT_WIDTH);
+    return len;
+  } else {
+    return 0;
+  }
+}
 
 template <>
 LIBC_INLINE constexpr size_t
 FloatToString<long double>::zero_blocks_after_point() {
+  const int idx = -exponent / IDX_SIZE;
+  if (idx < 5) {
     return 0;
   }
+  return static_cast<size_t>(idx - 5) / 2;
+}
 
 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
+    // 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 + (IDX_SIZE - 1)) / IDX_SIZE;
+    const uint32_t pos_exp = idx * IDX_SIZE;
 
-    int32_t i = block_index;
+    // shift_amount = -(c0 - exponent) = c_0 + 16 * ceil(exponent/16) - exponent
+    const uint32_t shift_amount =
+        POW10_ADDITIONAL_BITS_CALC + pos_exp - exponent;
     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);
+#ifdef LIBC_COPT_FLOAT_TO_STR_USE_GIANT_TABLE
+    // ------------------------------ TABLE MODE -------------------------------
+    val = POW10_SPLIT[POW10_OFFSET[idx] + block_index];
+
+#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT) ||                      \
+    defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD)
+    // ------------------------ DYADIC FLOAT CALC MODE -------------------------
+    val = internal::get_table_positive_df<256>(pos_exp, block_index);
+#else
+    // ----------------------------- INT CALC MODE -----------------------------
+    const uint64_t MAX_POW_2_SIZE =
+        exponent + POW10_ADDITIONAL_BITS_CALC - (BLOCK_SIZE * block_index);
+    const uint64_t MAX_POW_5_SIZE =
+        internal::log2_pow5(BLOCK_SIZE * block_index);
+    const uint64_t MAX_INT_SIZE =
+        (MAX_POW_2_SIZE > MAX_POW_5_SIZE) ? MAX_POW_2_SIZE : MAX_POW_5_SIZE;
+
+    if (MAX_INT_SIZE < 1024) {
+      val = internal::get_table_positive<1024>(pos_exp, block_index);
+    } else if (MAX_INT_SIZE < 4096) {
+      val = internal::get_table_positive<4096>(pos_exp, block_index);
+    } else if (MAX_INT_SIZE < 8192) {
+      val = internal::get_table_positive<8192>(pos_exp, block_index);
     } else {
-      val = internal::get_table_positive<16384>(pos_exp, i,
-                                                POW10_ADDITIONAL_BITS_CALC);
+      val = internal::get_table_positive<16384>(pos_exp, block_index);
     }
+#endif
 
     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;
+    const int32_t idx = -exponent / IDX_SIZE;
+
+    const int32_t shift_amount =
+        POW10_ADDITIONAL_BITS_CALC + (-exponent - IDX_SIZE * idx);
+
+    cpp::UInt<MID_INT_SIZE> val;
+#ifdef LIBC_COPT_FLOAT_TO_STR_USE_GIANT_TABLE
+    // ------------------------------ TABLE MODE -------------------------------
     // 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];
+    const uint32_t p = POW10_OFFSET_2[idx] + block_index - 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);
+    val = POW10_SPLIT_2[p];
+#elif defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT) ||                      \
+    defined(LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD)
+    // ------------------------ DYADIC FLOAT CALC MODE -------------------------
+    val = internal::get_table_negative_df<256>(idx * IDX_SIZE, block_index + 1);
+#else // table mode
+    // ----------------------------- INT CALC MODE -----------------------------
+    const int calc_shift_amount = POW10_ADDITIONAL_BITS_CALC - (IDX_SIZE * idx);
+    const uint64_t TEN_BLOCKS = (block_index + 1) * BLOCK_SIZE;
+    const uint64_t MAX_INT_SIZE = internal::log2_pow5(TEN_BLOCKS);
+
+    if (MAX_INT_SIZE < 1024) {
+      val = internal::get_table_negative<1024>(idx * IDX_SIZE, block_index + 1);
+    } else if (MAX_INT_SIZE < 4096) {
+      val = internal::get_table_negative<4096>(idx * IDX_SIZE, block_index + 1);
+    } else if (MAX_INT_SIZE < 8192) {
+      val = internal::get_table_negative<8192>(idx * IDX_SIZE, block_index + 1);
+    } else if (MAX_INT_SIZE < 16384) {
+      val =
+          internal::get_table_negative<16384>(idx * IDX_SIZE, block_index + 1);
+    } else {
+      val =
+          internal::get_table_negative<16384+8192>(idx * IDX_SIZE, block_index + 1);
+    }
+#endif
+    BlockInt digits = internal::mul_shift_mod_1e9(mantissa, val, shift_amount);
     return digits;
   } else {
     return 0;
   }
 }
 
+#endif // LONG_DOUBLE_IS_DOUBLE
+
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_FLOAT_TO_STRING_H

libc/src/__support/ryu_constants.h

 //===-- Ryu Constants for float conversion ----------------------*- 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_RYU_CONSTANTS_H
 #define LLVM_LIBC_SRC_SUPPORT_RYU_CONSTANTS_H
 
 #include <stddef.h>
 #include <stdint.h>
 
+constexpr size_t POW10_ADDITIONAL_BITS_TABLE = 120;
+constexpr size_t IDX_SIZE = 16;
+
+constexpr size_t MID_INT_SIZE = 192;
+
 static const uint16_t POW10_OFFSET[64] = {
     0,   2,   5,   8,   12,  16,  21,   26,   32,   39,   46,   54,  62,
     71,  80,  90,  100, 111, 122, 134,  146,  159,  173,  187,  202, 217,
     233, 249, 266, 283, 301, 319, 338,  357,  377,  397,  418,  440, 462,
     485, 508, 532, 556, 581, 606, 632,  658,  685,  712,  740,  769, 798,
     828, 858, 889, 920, 952, 984, 1017, 1050, 1084, 1118, 1153, 1188};
 
 static const uint64_t POW10_SPLIT[1224][3] = {

libc/src/stdio/printf_core/converter.cpp

 
 namespace __llvm_libc {
 namespace printf_core {
 
 int convert(Writer *writer, const FormatSection &to_conv) {
   if (!to_conv.has_conv)
     return writer->write(to_conv.raw_string);
 
-#ifndef LIBC_COPT_PRINTF_DISABLE_FLOAT
-  // TODO(michaelrj): Undo this once decimal long double support is done.
+#if !defined(LIBC_COPT_PRINTF_DISABLE_FLOAT) &&                                \
+    defined(LIBC_COPT_PRINTF_HEX_LONG_DOUBLE)
   if (to_conv.length_modifier == LengthModifier::L) {
     switch (to_conv.conv_name) {
     case 'f':
     case 'F':
     case 'e':
     case 'E':
     case 'g':
     case 'G':

libc/src/stdio/printf_core/printf_config.h

 // type of that index. As an example, if the format string has 20 indexes, and
 // the index array is 10, then when the 20th index is requested the first 10
 // types can be found immediately, and then the format string must be parsed 10
 // times to find the types of the next 10 arguments.
 #ifndef LIBC_COPT_PRINTF_INDEX_ARR_LEN
 #define LIBC_COPT_PRINTF_INDEX_ARR_LEN 128
 #endif
 
+// TODO(michaelrj): Provide a proper interface for these options.
+// LIBC_COPT_FLOAT_TO_STR_USE_GIANT_TABLE
+// LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT
+// LIBC_COPT_FLOAT_TO_STR_USE_DYADIC_FLOAT_LD
+// LIBC_COPT_FLOAT_TO_STR_USE_INT_CALC
+// LIBC_COPT_FLOAT_TO_STR_NO_TABLE
+// LIBC_COPT_PRINTF_HEX_LONG_DOUBLE
+
 // TODO(michaelrj): Move the other printf configuration options into this file.
 
 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_PRINTF_CONFIG_H

libc/test/src/__support/high_precision_decimal_test.cpp

TEST(LlvmLibcHighPrecisionDecimalTest, RoundingTest) {
   // 1267650600228229401496703205376 = 2^100
   hpd = __llvm_libc::internal::HighPrecisionDecimal(
       "1267650600228229401496703205376");
 
   UInt128 result = UInt128(1) << 100;
 
   EXPECT_EQ(hpd.round_to_integer_type<UInt128>(), result);
 }
+
+// TODO: REMOVE THIS BEFORE COMMIT
+
+constexpr uint8_t POWERS_OF_TWO[19] = {
+    0, 3, 6, 9, 13, 16, 19, 23, 26, 29, 33, 36, 39, 43, 46, 49, 53, 56, 59,
+};
+constexpr int32_t NUM_POWERS_OF_TWO =
+    sizeof(POWERS_OF_TWO) / sizeof(POWERS_OF_TWO[0]);
+
+TEST(LlvmLibcHighPrecisionDecimalTest, ConstantCalc) {
+  __llvm_libc::internal::HighPrecisionDecimal hpd =
+      __llvm_libc::internal::HighPrecisionDecimal("0.000000001");
+
+  hpd.shift(9);
+
+  int exp2 = 0;
+
+  // Right shift until the number is smaller than 1.
+  while (hpd.get_decimal_point() > 0) {
+    int32_t shift_amount = 0;
+    if (hpd.get_decimal_point() >= NUM_POWERS_OF_TWO) {
+      shift_amount = 60;
+    } else {
+      shift_amount = POWERS_OF_TWO[hpd.get_decimal_point()];
+    }
+    exp2 += shift_amount;
+    hpd.shift(-shift_amount);
+  }
+
+  // Left shift until the number is between 1/2 and 1
+  while (hpd.get_decimal_point() < 0 ||
+         (hpd.get_decimal_point() == 0 && hpd.get_digits()[0] < 5)) {
+    int32_t shift_amount = 0;
+
+    if (-hpd.get_decimal_point() >= NUM_POWERS_OF_TWO) {
+      shift_amount = 60;
+    } else if (hpd.get_decimal_point() != 0) {
+      shift_amount = POWERS_OF_TWO[-hpd.get_decimal_point()];
+    } else { // This handles the case of the number being between .1 and .5
+      shift_amount = 1;
+    }
+    exp2 -= shift_amount;
+    hpd.shift(shift_amount);
+  }
+
+  // Left shift once so that the number is between 1 and 2
+  --exp2;
+  hpd.shift(1);
+
+  // Shift left to fill the mantissa
+  hpd.shift(256);
+  __llvm_libc::cpp::UInt<256+64> final_mantissa =
+      hpd.round_to_integer_type<__llvm_libc::cpp::UInt<256+64>>();
+
+  EXPECT_EQ(final_mantissa, __llvm_libc::cpp::UInt<256+64>(0));
+  EXPECT_EQ(exp2, 0);
+}

libc/test/src/stdio/sprintf_test.cpp

TEST_F(LlvmLibcSPrintfTest, FloatDecimalConv) {
 
   written = __llvm_libc::sprintf(buff, "%F", -nan);
   ASSERT_STREQ_LEN(written, buff, "-NAN");
 
   // Length Modifier Tests.
 
   // TODO: Fix long doubles (needs bigger table or alternate algorithm.)
   // Currently the table values are generated, which is very slow.
-  /*
+
+  written = __llvm_libc::sprintf(buff, "%Lf", 1.0L);
+  ASSERT_STREQ_LEN(written, buff, "1.000000");
+
   written = __llvm_libc::sprintf(buff, "%Lf", 1e100L);
   ASSERT_STREQ_LEN(written, buff,
                    "99999999999999999996693535322073426194986990198284960792713"
                    "91541752018669482644324418977840117055488.000000");
 
-  written = __llvm_libc::sprintf(buff, "%Lf", 1.0L);
-  ASSERT_STREQ_LEN(written, buff, "1.000000");
-
   char big_buff[10000];
+
+  // written = __llvm_libc::sprintf(big_buff, "%Lf", 0x1p16383L);
+
   written = __llvm_libc::sprintf(big_buff, "%Lf", 1e1000L);
   ASSERT_STREQ_LEN(
       written, big_buff,
       "999999999999999999973107317669562353428234857594552594925899449376328728"
       "202461036775511405481186963193066642191664822065529414252060696836533522"
       "387143501724276282079456797058697369889056407118642873669166717313763499"
       "277025985141177344925615052465165938514140943010597323750202561187880136"
       "174810574553749194614479541820148407958204853833697063267336294787191005"
ASSERT_STREQ_LEN(
       "462337569019001580859906425911782967213265389744605395555069797947978230"
       "708108432086217134763779632408473684293543722127232658767439906910370146"
       "716836295909075482355827087389127370874842532825987593970846704144140471"
       "956027276735614286138656432085771988513977140957180090146798065497158947"
       "229765733489703157617307078835099906185890777007500964162371428641176460"
       "739074789794941408428328217107759915202650066155868439585510978709442590"
       "231934194956788626761834746430104077432547436359522462253411168467463134"
       "24896.000000");
-*/
+
+
+  written = __llvm_libc::sprintf(big_buff, "%.10Lf", 1e-10L);
+  ASSERT_STREQ_LEN(
+      written, big_buff, "0.0000000001");
+
+  written = __llvm_libc::sprintf(big_buff, "%.7500Lf", 1e-4900L);
+  ASSERT_STREQ_LEN(
+      written, big_buff,
+      "0."
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000099999999999999999996962764452956071352139203248614920751610856665084"
+      "549214352477698417183862158583009348897567779527408501588132175167211539"
+      "462139941448204886585901454195352527238724272760638086779284030512649793"
+      "039219351187928723378036480041948464946018272171365770411701020666925613"
+      "422460317465324758217878522666789603627480490870456508256359180089236338"
+      "765625231186929290294207420828927406735690318849109129700396907705735097"
+      "663944722727287361650042373203763784830198232253311807069225650324196304"
+      "532045014970637489181357566354288111205943347410488298480279857453705249"
+      "232862728556860184412369114663536200895729846877559808001004454634804626"
+      "541455540260282018142615835686583304903486353937549394736905011798466731"
+      "536563240053860118551127061960208467764243724656897127545613968909523389"
+      "577188368809623987105800147797280462974804046545425080530020901531407223"
+      "191237123282274818236437397994019915368657474589800678444589412286037789"
+      "891525464936023205313685584525510094270344601331453730179416773626565262"
+      "480345858564672442896904520146956686863172737711483866766404977719744767"
+      "834324844875237277613991088218774564658513875732403456058414595576806383"
+      "115554713240005982141397577420073082470139244845624915873825746771661332"
+      "098677966580506186966978746832443976821987300902957597498388211921362869"
+      "017846215557612829071692275292036211064515305528052919611691470945774714"
+      "135516559501572279732350629089770249554808690411603894492333360300589658"
+      "470898965370892774715815089075170720164713889237058574941489766701880158"
+      "060081295483989540170337129032188818293132770882381428397119039835946745"
+      "549356649433406617266370644136291924838857814675939156677910783740103207"
+      "523299367093130816446415259371931925208362367989095199399211644084543790"
+      "110432339056231037520216864358899218874658268610955002763260912337688947"
+      "822453100821038299301092582962825965939081817836419126254832772002214908"
+      "085575905761843610944187009818156363893015929300295112598059949496854566"
+      "638748010633726861510500653821408135845840123073754133549077708843800674"
+      "328440913743105608636458354618912183716456158809545183074062249922212944"
+      "249667793845728355381309084891765979111348980470647082269921872595470473"
+      "719354467594516320911964549508538492057120740224559944452120552719041944"
+      "961475548547884309626382512432626380881023756568143060204097921571153170"
+      "723817845809196253498326358439807445210362177680590181657555380795450462"
+      "223805222580359379367452693270553602179122419370586308101820559214330382"
+      "570449525088342437216896462077260223998756027453411520977536701491759878"
+      "422771447006016890777855573925295187921971811871399320142563330377888532"
+      "179817332113");
+
   /*
     written = __llvm_libc::sprintf(buff, "%La", 0.1L);
   #if defined(SPECIAL_X86_LONG_DOUBLE)
     ASSERT_STREQ_LEN(written, buff, "0xc.ccccccccccccccdp-7");
   #elif defined(LONG_DOUBLE_IS_DOUBLE)
     ASSERT_STREQ_LEN(written, buff, "0x1.999999999999ap-4");
   #else // 128 bit long double
     ASSERT_STREQ_LEN(written, buff, "0x1.999999999999999999999999999ap-4");

libc/utils/mathtools/ryu_tablegen.py

+BLOCK_SIZE = 9
+
+
+# Values for double
+# CONSTANT = 120
+# IDX_SIZE = 16
+# MANT_WIDTH = 52
+# EXP_WIDTH = 11
+# MID_INT_SIZE = 192
+
+# Values for 128 bit float
+CONSTANT = 120
+IDX_SIZE = 128
+MANT_WIDTH = 112
+EXP_WIDTH = 15
+MID_INT_SIZE = 256 + 64
+
+MAX_EXP = 2 ** (EXP_WIDTH - 1)
+POSITIVE_ARR_SIZE = MAX_EXP // IDX_SIZE
+NEGATIVE_ARR_SIZE = (MAX_EXP // IDX_SIZE) + ((MANT_WIDTH + (IDX_SIZE - 1)) // IDX_SIZE)
+MOD_SIZE = (10**BLOCK_SIZE) << (CONSTANT + (IDX_SIZE if IDX_SIZE > 1 else 0))
+
+# floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)
+def get_table_positive(exponent, i):
+    pow_of_two = 1 << (exponent + CONSTANT - (BLOCK_SIZE * i))
+    pow_of_five = 5 ** (BLOCK_SIZE * i)
+    result = (pow_of_two // pow_of_five) + 1
+    return result % MOD_SIZE
+
+
+# floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
+def get_table_negative(exponent, i):
+    result = 1
+    pow_of_ten = 10 ** (BLOCK_SIZE * i)
+    shift_amount = CONSTANT - exponent
+    if shift_amount < 0:
+        result = pow_of_ten >> (-shift_amount)
+    else:
+        result = pow_of_ten << (shift_amount)
+    return result % MOD_SIZE
+
+
+# Returns floor(log_10(2^e)); requires 0 <= e <= 42039.
+def ceil_log10_pow2(e):
+    return ((e * 0x13441350FBD) >> 42) + 1
+
+
+def length_for_num(idx, index_size=IDX_SIZE):
+    return (
+        ceil_log10_pow2(idx * index_size) + ceil_log10_pow2(MANT_WIDTH) + BLOCK_SIZE - 1
+    ) // BLOCK_SIZE
+
+
+def get_64bit_window(num, index):
+    return (num >> (index * 64)) % (2**64)
+
+
+def mid_int_to_str(num):
+    outstr = "    {"
+    outstr += str(get_64bit_window(num, 0)) + "u"
+    for i in range(1, MID_INT_SIZE // 64):
+        outstr += ", " + str(get_64bit_window(num, i)) + "u"
+    outstr += "},"
+    return outstr
+
+
+def print_positive_table_for_idx(idx):
+    positive_blocks = length_for_num(idx)
+    for i in range(positive_blocks):
+        table_val = get_table_positive(idx * IDX_SIZE, i)
+        # print(hex(table_val))
+        print(mid_int_to_str(table_val))
+    return positive_blocks
+
+
+def print_negative_table_for_idx(idx):
+    i = 0
+    min_block = -1
+    table_val = 0
+    MIN_USEFUL_VAL = 2 ** (CONSTANT - (MANT_WIDTH + 2))
+    # Iterate through the zero blocks
+    while table_val < MIN_USEFUL_VAL:
+        i += 1
+        table_val = get_table_negative((idx) * IDX_SIZE, i)
+    else:
+        i -= 1
+
+    min_block = i
+
+    # Iterate until another zero block is found
+    while table_val >= MIN_USEFUL_VAL:
+        table_val = get_table_negative((idx) * IDX_SIZE, i + 1)
+        if table_val >= MIN_USEFUL_VAL:
+            print(mid_int_to_str(table_val))
+            i += 1
+    return i - min_block, min_block
+
+
+positive_size_arr = [0] * (POSITIVE_ARR_SIZE + 1)
+
+negative_size_arr = [0] * (NEGATIVE_ARR_SIZE + 1)
+min_block_arr = [0] * (NEGATIVE_ARR_SIZE + 1)
+acc = 0
+
+if MOD_SIZE > (2**MID_INT_SIZE):
+    print(
+        "Mod size is too big for current MID_INT_SIZE by a factor of",
+        MOD_SIZE // (2**MID_INT_SIZE),
+    )
+else:
+    print("static const uint64_t POW10_SPLIT[][" + str(MID_INT_SIZE // 64) + "] = {")
+    for idx in range(0, POSITIVE_ARR_SIZE):
+        num_size = print_positive_table_for_idx(idx)
+        acc += num_size
+        positive_size_arr[idx + 1] = acc
+    print("};")
+
+    print(
+        "static const uint32_t POW10_OFFSET_2[" + str(len(positive_size_arr)) + "] = {",
+        str(positive_size_arr)[1:-2],
+        "};",
+    )
+
+    print("static const uint64_t POW10_SPLIT_2[][" + str(MID_INT_SIZE // 64) + "] = {")
+    for idx in range(0, NEGATIVE_ARR_SIZE):
+        num_size, min_block = print_negative_table_for_idx(idx)
+        acc += num_size
+        negative_size_arr[idx + 1] = acc
+        min_block_arr[idx] = min_block
+    print("};")
+    print(
+        "static const uint32_t POW10_OFFSET_2[" + str(len(negative_size_arr)) + "] = {",
+        str(negative_size_arr)[1:-2],
+        "};",
+    )
+    print(
+        "static const uint16_t MIN_BLOCK_2[" + str(len(min_block_arr)) + "] = {",
+        str(min_block_arr)[1:-2],
+        "};",
+    )