[libc] Fix printf %f bugs

[michaelrj]

Summary

Fuzzing revealed several bugs in the %f float conversion. This patch
fixes them. Most of these bugs are related to rounding, such as
1.999...999 being rounded to 2.999...999 instead of 2.000...000 due to
rounding up not properly changing the nines to zeros. Additionally, much
of the rounding infrastructure has been refactored out so it can be
shared with the other conversions.

[sivachandra]

libc/test/src/stdio/sprintf_test.cpp

1286

Remove.

1288

Add a comment describing the "why" of the expected result. In a way it is obvious I think, but will help people who do not remember what the %.9f means.

Same for the tests below.

[michaelrj]

add comments explaining more about the tests

libc/test/src/stdio/sprintf_test.cpp

1286

same as previous, this is a category.

[sivachandra]

libc/test/src/stdio/sprintf_test.cpp

1286

You can choose to leave the note about fuzzing, but the category I think is "Rounding behavior tests".

1303

Nit: Add a comment explaining why there are digits beyond the 3339 even though the literal above does not.

[michaelrj]

adjust test comments

libc/test/src/stdio/sprintf_test.cpp

1286

that category is "precision tests" which these are already in, see line 1217 (might be adjusted by the previous patch).

[sivachandra]

LGTM but I have left a question on a comment in the test.

libc/test/src/stdio/sprintf_test.cpp

1297

I am confused with this wording. My knowledge says that if you write down a literal, then is already an exact value (of course, might not correspond exactly to an encoded value). Likewise, if a floating number is encoded as single/double/quad precision number, then that is also an exact number.

1303

Isn't the reason that the closest number that can be represented as a double precision number to that literal?

[michaelrj]

simplify test comment

libc/test/src/stdio/sprintf_test.cpp

1297

The literal you write down maps to a value, but it's usually not exact. As an example, when you write 0.1 the "actual" value as a double is 0.1000000000000000055511151231257827021181583404541015625. That's the value you get if you actually calculate 1.mantissa * 2^exponent, but when converting to and from a string that's not the only valid value. The number only has ~17 significant figures, so if you change the digits after that point you'll still get the same result. In this case the first non-significant digit happens to be the first 5. You can set that digit and any digits after to any value you want and it'll still give you the same result. As long as you stay within that range (0.1000...000, 0.1000...001), the number is equivalent. That's what I meant by floating point numbers representing a range.

1303

This is a simpler way to explain it. I've adjusted the comment.

libc/src/stdio/printf_core/float_dec_converter.h

 
 // constexpr size_t BLOCK_SIZE = 18;
 // constexpr uint32_t MAX_BLOCK = 999999999999999999;
 constexpr char DECIMAL_POINT = '.';
 
 // This is used to represent which direction the number should be rounded.
 enum class RoundDirection { Up, Down, Even };
 
+LIBC_INLINE RoundDirection get_round_direction(int last_digit, bool truncated,
+                                               bool is_negative) {
+  switch (fputil::quick_get_round()) {
+  case FE_TONEAREST:
+    // Round to nearest, if it's exactly halfway then round to even.
+    if (last_digit != 5) {
+      return last_digit > 5 ? RoundDirection::Up : RoundDirection::Down;
+    } else {
+      return !truncated ? RoundDirection::Even : RoundDirection::Up;
+    }
+  case FE_DOWNWARD:
+    if (is_negative && (truncated || last_digit > 0)) {
+      return RoundDirection::Up;
+    } else {
+      return RoundDirection::Down;
+    }
+  case FE_UPWARD:
+    if (!is_negative && (truncated || last_digit > 0)) {
+      return RoundDirection::Up;
+    } else {
+      return RoundDirection::Down;
+    }
+    return is_negative ? RoundDirection::Down : RoundDirection::Up;
+  case FE_TOWARDZERO:
+    return RoundDirection::Down;
+  default:
+    return RoundDirection::Down;
+  }
+}
+
+template <typename T>
+LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_integral_v<T>, bool>
+zero_after_digits(int32_t base_2_exp, int32_t digits_after_point, T mantissa) {
+  const int32_t required_twos = -base_2_exp - digits_after_point - 1;
+  const bool has_trailing_zeros =
+      required_twos <= 0 ||
+      (required_twos < 60 &&
+       multiple_of_power_of_2(mantissa, static_cast<uint32_t>(required_twos)));
+  return has_trailing_zeros;
+}
+
 class PaddingWriter {
   bool left_justified = false;
   bool leading_zeroes = false;
   char sign_char = 0;
   size_t min_width = 0;
 
 public:
   PaddingWriter() {}
class FloatWriter {
   size_t max_block_count = 0; // The # of blocks of all 9s currently buffered.
   size_t total_digits = 0;    // The number of digits that will be output.
   size_t digits_before_decimal = 0; // The # of digits to write before the '.'
   size_t total_digits_written = 0;  // The # of digits that have been output.
   bool has_decimal_point;           // True if the number has a decimal point.
   Writer *writer;                   // Writes to the final output.
   PaddingWriter padding_writer; // Handles prefixes/padding, uses total_digits.
 
-  int flush_buffer() {
+  int flush_buffer(bool round_up_max_blocks = false) {
+    const char MAX_BLOCK_DIGIT = (round_up_max_blocks ? '0' : '9');
+
     // Write the most recent buffered block, and mark has_written
     if (!has_written) {
       has_written = true;
       RET_IF_RESULT_NEGATIVE(
           padding_writer.write_left_padding(writer, total_digits));
     }
 
     // if the decimal point is the next character, or is in the range covered
int flush_buffer(bool round_up_max_blocks = false) {
     // if the decimal point is the next character, or is in the range covered
     // by the max blocks, write the appropriate digits and the decimal point.
     if (total_digits_written < digits_before_decimal &&
         total_digits_written + BLOCK_SIZE * max_block_count >=
             digits_before_decimal &&
         has_decimal_point) {
       size_t digits_to_write = digits_before_decimal - total_digits_written;
       if (digits_to_write > 0) {
-        RET_IF_RESULT_NEGATIVE(writer->write('9', digits_to_write));
+        RET_IF_RESULT_NEGATIVE(writer->write(MAX_BLOCK_DIGIT, digits_to_write));
       }
       RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT));
       if ((BLOCK_SIZE * max_block_count) - digits_to_write > 0) {
         RET_IF_RESULT_NEGATIVE(writer->write(
-            '9', (BLOCK_SIZE * max_block_count) - digits_to_write));
+            MAX_BLOCK_DIGIT, (BLOCK_SIZE * max_block_count) - digits_to_write));
       }
       // add 1 for the decimal point
       total_digits_written += BLOCK_SIZE * max_block_count + 1;
       // clear the buffer of max blocks
       max_block_count = 0;
     }
 
     // Clear the buffer of max blocks
     if (max_block_count > 0) {
-      RET_IF_RESULT_NEGATIVE(writer->write('9', max_block_count * BLOCK_SIZE));
+      RET_IF_RESULT_NEGATIVE(
+          writer->write(MAX_BLOCK_DIGIT, max_block_count * BLOCK_SIZE));
       total_digits_written += max_block_count * BLOCK_SIZE;
       max_block_count = 0;
     }
     return 0;
   }
 
   // -exponent will never overflow because all long double types we support
   // have at most 15 bits of mantissa and the C standard defines an int as
int write_last_block_dec(BlockInt block, size_t block_digits,
     const cpp::string_view int_to_str = buf.view();
 
     // copy the last block_digits characters into the start of end_buff.
     // TODO: Replace with memcpy
     for (size_t count = 0; count < block_digits; ++count) {
       end_buff[count] = int_to_str[count + 1 + (BLOCK_SIZE - block_digits)];
     }
 
-    char low_digit;
+    char low_digit = '0';
     if (block_digits > 0) {
       low_digit = end_buff[block_digits - 1];
     } else if (max_block_count > 0) {
       low_digit = '9';
-    } else {
+    } else if (buffered_digits > 0) {
       low_digit = block_buffer[buffered_digits - 1];
     }
 
+    bool round_up_max_blocks = false;
+
     // Round up
     if (round == RoundDirection::Up ||
         (round == RoundDirection::Even && low_digit % 2 != 0)) {
       bool has_carry = true;
+      round_up_max_blocks = true; // if we're rounding up, we might need to
+                                  // round up the max blocks that are buffered.
       // handle the low block that we're adding
       for (int count = static_cast<int>(block_digits) - 1;
            count >= 0 && has_carry; --count) {
         if (end_buff[count] == '9') {
           end_buff[count] = '0';
         } else {
           end_buff[count] += 1;
           has_carry = false;
+          round_up_max_blocks = false; // If the low block isn't all nines, then
+                                       // the max blocks aren't rounded up.
         }
       }
       // handle the high block that's buffered
       for (int count = static_cast<int>(buffered_digits) - 1;
            count >= 0 && has_carry; --count) {
         if (block_buffer[count] == '9') {
           block_buffer[count] = '0';
         } else {
if (round == RoundDirection::Up ||
         }
         total_digits_written = total_digits;
         return 0;
       }
     }
     // Either we intend to round down, or the rounding up is complete. Flush the
     // buffers.
 
-    RET_IF_RESULT_NEGATIVE(flush_buffer());
+    RET_IF_RESULT_NEGATIVE(flush_buffer(round_up_max_blocks));
 
     // And then write the final block.
     RET_IF_RESULT_NEGATIVE(writer->write({end_buff, block_digits}));
     total_digits_written += block_digits;
     return 0;
   }
 
   int write_last_block_exp(uint32_t block, size_t block_digits,
for (; i < blocks; ++i) {
 
         const uint32_t maximum = precision - BLOCK_SIZE * i;
         uint32_t last_digit = 0;
         for (uint32_t k = 0; k < BLOCK_SIZE - maximum; ++k) {
           last_digit = digits % 10;
           digits /= 10;
         }
         RoundDirection round;
-        // Is m * 10^(additionalDigits + 1) / 2^(-exponent) integer?
-        const int32_t requiredTwos =
-            -(exponent - MANT_WIDTH) - static_cast<int32_t>(precision) - 1;
-        const bool trailingZeros =
-            requiredTwos <= 0 ||
-            (requiredTwos < 60 &&
-             multiple_of_power_of_2(float_bits.get_explicit_mantissa(),
-                                    static_cast<uint32_t>(requiredTwos)));
-        switch (fputil::quick_get_round()) {
-        case FE_TONEAREST:
-          // Round to nearest, if it's exactly halfway then round to even.
-          if (last_digit != 5) {
-            round = last_digit > 5 ? RoundDirection::Up : RoundDirection::Down;
-          } else {
-            round = trailingZeros ? RoundDirection::Even : RoundDirection::Up;
-          }
-          break;
-        case FE_DOWNWARD:
-          if (is_negative && (!trailingZeros || last_digit > 0)) {
-            round = RoundDirection::Up;
-          } else {
-            round = RoundDirection::Down;
-          }
-          break;
-        case FE_UPWARD:
-          if (!is_negative && (!trailingZeros || last_digit > 0)) {
-            round = RoundDirection::Up;
-          } else {
-            round = RoundDirection::Down;
-          }
-          round = is_negative ? RoundDirection::Down : RoundDirection::Up;
-          break;
-        case FE_TOWARDZERO:
-          round = RoundDirection::Down;
-          break;
-        }
+        const bool truncated =
+            !zero_after_digits(exponent - MANT_WIDTH, precision,
+                               float_bits.get_explicit_mantissa());
+        round = get_round_direction(last_digit, truncated, is_negative);
+
         RET_IF_RESULT_NEGATIVE(
             float_writer.write_last_block_dec(digits, maximum, round));
         break;
       }
     }
   } else {
     RET_IF_RESULT_NEGATIVE(float_writer.write_zeroes(precision));
   }

libc/test/src/stdio/sprintf_test.cpp

 //===-- Unittests for sprintf ---------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "src/stdio/sprintf.h"
 
 #include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/FPUtil/PlatformDefs.h"
 #include "test/UnitTest/RoundingModeUtils.h"
 #include "test/UnitTest/Test.h"
 
+// TODO: Add a comment here explaining the printf format string.
+
 // #include <stdio.h>
 // namespace __llvm_libc {
 // using ::sprintf;
 // }
 
 class LlvmLibcSPrintfTest : public __llvm_libc::testing::Test {
 protected:
   char buff[1000];
ASSERT_STREQ_LEN(
       " 0x1.00000000000000000000000000000000000000000000000000p+0");
 }
 
 TEST_F(LlvmLibcSPrintfTest, FloatDecimalConv) {
   ForceRoundingMode r(RoundingMode::Nearest);
   double inf = __llvm_libc::fputil::FPBits<double>::inf().get_val();
   double nan = __llvm_libc::fputil::FPBits<double>::build_nan(1);
 
+  char big_buff[10000];
+
   written = __llvm_libc::sprintf(buff, "%f", 1.0);
   ASSERT_STREQ_LEN(written, buff, "1.000000");
 
   written = __llvm_libc::sprintf(buff, "%F", -1.0);
   ASSERT_STREQ_LEN(written, buff, "-1.000000");
 
   written = __llvm_libc::sprintf(buff, "%f", -1.234567);
   ASSERT_STREQ_LEN(written, buff, "-1.234567");

 
 #if defined(SPECIAL_X86_LONG_DOUBLE)
 
   written = __llvm_libc::sprintf(buff, "%Lf", 1e100L);
   ASSERT_STREQ_LEN(written, buff,
                    "99999999999999999996693535322073426194986990198284960792713"
                    "91541752018669482644324418977840117055488.000000");
 
-  char big_buff[10000];
-
   written = __llvm_libc::sprintf(big_buff, "%Lf", 1e1000L);
   ASSERT_STREQ_LEN(
       written, big_buff,
       "999999999999999999973107317669562353428234857594552594925899449376328728"
       "202461036775511405481186963193066642191664822065529414252060696836533522"
       "387143501724276282079456797058697369889056407118642873669166717313763499"
       "277025985141177344925615052465165938514140943010597323750202561187880136"
       "174810574553749194614479541820148407958204853833697063267336294787191005"
#endif // SPECIAL_X86_LONG_DOUBLE
 
   // Found with the help of Fred Tydeman's tbin2dec test.
   written = __llvm_libc::sprintf(buff, "%.1f", 0x1.1000000000006p+3);
   ASSERT_STREQ_LEN(written, buff, "8.5");
 
   written = __llvm_libc::sprintf(buff, "%.0f", 0x1.1000000000006p+3);
   ASSERT_STREQ_LEN(written, buff, "9");
 
+  // Most of these tests are checking rounding behavior when the precision is
+  // set. As an example, %.9f has a precision of 9, meaning it should be rounded
+  // to 9 digits after the decimal point. In this case, that means that it
+  // should be rounded up. Many of these tests have precisions divisible by 9
+  // since when printing the floating point numbers are broken up into "blocks"
+  // of 9 digits. They often also have a 5 after the end of what's printed,
+  // since in round to nearest mode, that requires checking additional digits.
+  written = __llvm_libc::sprintf(buff, "%.9f", 1.9999999999999514);
+  ASSERT_STREQ_LEN(written, buff, "2.000000000");
+
+  // The number continues after the literal because floating point numbers can't
+  // represent every value. The printed value is the closest value a double can
+  // represent, rounded to the requested precision.
+  written = __llvm_libc::sprintf(buff, "%.238f", 1.131959884853339E-72);
+  ASSERT_STREQ_LEN(
+      written, buff,
+      "0."
+      "000000000000000000000000000000000000000000000000000000000000000000000001"
+      "131959884853339045938639911360973972585316399767392273697826861241937664"
+      "824105639342441431495119762431744054912109728706985341609159156917030486"
+      "5110665559768676757812");
+
+  written = __llvm_libc::sprintf(buff, "%.36f", 9.9e-77);
+  ASSERT_STREQ_LEN(written, buff, "0.000000000000000000000000000000000000");
+
+  written = __llvm_libc::sprintf(big_buff, "%.1071f", 2.0226568751604562E-314);
+  ASSERT_STREQ_LEN(
+      written, big_buff,
+      "0."
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000000000000000000000000000000000000000000000000000"
+      "000000000000000000000000020226568751604561683387695750739190248658016786"
+      "876938365740768295004457513021760887468117675879956193821375945376632621"
+      "367998639317487303530427946024002091961988296562516210434394107910027236"
+      "308233439098296717697919471698168200340836487924061502604112643734560622"
+      "258525943451473162532620033398739382796482175564084902819878893430369431"
+      "907237673154867595954110791891883281880339550955455702452422857027182100"
+      "606009588295886640782228837851739241290179512817803196347460636150182981"
+      "085084829941917048152725177119574542042352896161225179181967347829576272"
+      "242480201291872969114441104973910102402751449901108484914924879541248714"
+      "939096548775588293353689592872854495101242645279589976452453829724479805"
+      "750016448075109469332839157162950982637994457036256790161132812");
+
+  // If no precision is specified it defaults to 6 for %f.
+  written = __llvm_libc::sprintf(buff, "%f", 2325885.4901960781);
+  ASSERT_STREQ_LEN(written, buff, "2325885.490196");
+
   // Subnormal Precision Tests
 
   written = __llvm_libc::sprintf(buff, "%.310f", 0x1.0p-1022);
   ASSERT_STREQ_LEN(
       written, buff,
       "0."
       "000000000000000000000000000000000000000000000000000000000000000000000000"
       "000000000000000000000000000000000000000000000000000000000000000000000000"