[libc] Fix printf %e and %g bugs

[michaelrj]

Summary

Fuzzing revealed bugs in the %e and %g conversions. Since these are very
similar, they are grouped together. Again, most of the bugs were related
to rounding. As an example, previously the code to check if the number
was truncated only worked for digits below the decimal point, due to it
being originally designed for %f. This patch adds a mechanism to check
the digits above the decimal point for both %e and %g.

[michaelrj]

add explanatory comments

[sivachandra]

libc/test/src/stdio/sprintf_test.cpp

2563–2575

If categories are important, you choose to leave this note but find a better category name. "Base 10 rounding tests" ?

[michaelrj]

adjust test comments

libc/test/src/stdio/sprintf_test.cpp

2563–2575

These are already in the "Precision Tests" category, which is focused on testing the precision mechanism that also covers rounding.

libc/src/stdio/printf_core/float_dec_converter.h

char end_buff[BLOCK_SIZE];
 
       // 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 WRITE_OK;
       }
     }
     // 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. It's written via the buffer so that if
     // this is also the first block, the decimal point will be placed correctly.
 
     // TODO: Replace with memcpy
     for (size_t count = 0; count < block_digits; ++count) {
       block_buffer[count] = end_buff[count];
     }
LIBC_INLINE int convert_float_dec_exp_typed(Writer *writer,
 
   size_t last_block_size = BLOCK_SIZE;
 
   // if the last block is also the first block, then ignore leading zeroes.
   if (digits_written == 0) {
     last_block_size = IntegerToString<intmax_t>(digits).size();
   }
 
+  // This tracks if the number is truncated, that meaning that the digits after
+  // last_digit are non-zero.
+  bool truncated = false;
+
   // This is the last block.
   const size_t maximum = precision + 1 - digits_written;
   uint32_t last_digit = 0;
   for (uint32_t k = 0; k < last_block_size - maximum; ++k) {
+    if (last_digit > 0)
+      truncated = true;
+
     last_digit = digits % 10;
     digits /= 10;
   }
 
   // If the last block we read doesn't have the digit after the end of what
   // we'll print, then we need to read the next block to get that digit.
   if (maximum == last_block_size) {
-    BlockInt extra_block = float_converter.get_block(cur_block - 1);
+    --cur_block;
+    BlockInt extra_block = float_converter.get_block(cur_block);
     last_digit = extra_block / ((MAX_BLOCK / 10) + 1);
+    if (extra_block % ((MAX_BLOCK / 10) + 1) > 0) {
+      truncated = true;
+    }
   }
 
   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;
-    }
+
+  // If we've already seen a truncated digit, then we don't need to check any
+  // more.
+  if (!truncated) {
+    // Check the blocks above the decimal point
+    if (cur_block >= 0) {
+      // Check every block until the decimal point for non-zero digits.
+      for (int cur_extra_block = cur_block - 1; cur_extra_block >= 0;
+           --cur_extra_block) {
+        BlockInt extra_block = float_converter.get_block(cur_extra_block);
+        if (extra_block > 0) {
+          truncated = true;
           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;
     }
+    // If it's still not truncated and there are digits below the decimal point
+    if (!truncated && exponent - MANT_WIDTH < 0) {
+      // Use the formula from %f.
+      truncated =
+          !zero_after_digits(exponent - MANT_WIDTH, precision - final_exponent,
+                             float_bits.get_explicit_mantissa());
+    }
+  }
+  round = get_round_direction(last_digit, truncated, is_negative);
+
   RET_IF_RESULT_NEGATIVE(float_writer.write_last_block_exp(
       digits, maximum, round, final_exponent, a + 'E' - 'A'));
 
   RET_IF_RESULT_NEGATIVE(float_writer.right_pad());
   return WRITE_OK;
 }
 
 template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
if (int_to_str[i] == '9') {
       ++trailing_zeroes;
       trailing_nines = 0;
     } else {
       trailing_nines = 0;
       trailing_zeroes = 0;
     }
   }
 
+  bool truncated = false;
+
   // Find the digit after the lowest digit that we'll actually print to
   // determine the rounding.
   const uint32_t maximum =
       exp_precision + 1 - static_cast<uint32_t>(digits_checked);
   uint32_t last_digit = 0;
   for (uint32_t k = 0; k < last_block_size - maximum; ++k) {
+    if (last_digit > 0)
+      truncated = true;
+
     last_digit = digits % 10;
     digits /= 10;
   }
 
   // If the last block we read doesn't have the digit after the end of what
   // we'll print, then we need to read the next block to get that digit.
   if (maximum == last_block_size) {
-    BlockInt extra_block = float_converter.get_block(cur_block - 1);
+    --cur_block;
+    BlockInt extra_block = float_converter.get_block(cur_block);
     last_digit = extra_block / ((MAX_BLOCK / 10) + 1);
+
+    if (extra_block % ((MAX_BLOCK / 10) + 1) > 0)
+      truncated = true;
   }
 
   // TODO: unify this code across the three float conversions.
   RoundDirection round;
-  // Is m * 10^(additionalDigits + 1) / 2^(-exponent) integer?
-  const int32_t requiredTwos =
-      -(exponent - MANT_WIDTH) - static_cast<int32_t>(exp_precision) - 1;
-  // TODO: rename this variable to remove confusion with trailing_zeroes
-  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;
-    }
+
+  // If we've already seen a truncated digit, then we don't need to check any
+  // more.
+  if (!truncated) {
+    // Check the blocks above the decimal point
+    if (cur_block >= 0) {
+      // Check every block until the decimal point for non-zero digits.
+      for (int cur_extra_block = cur_block - 1; cur_extra_block >= 0;
+           --cur_extra_block) {
+        BlockInt extra_block = float_converter.get_block(cur_extra_block);
+        if (extra_block > 0) {
+          truncated = true;
           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;
     }
+    // If it's still not truncated and there are digits below the decimal point
+    if (!truncated && exponent - MANT_WIDTH < 0) {
+      // Use the formula from %f.
+      truncated =
+          !zero_after_digits(exponent - MANT_WIDTH, exp_precision - base_10_exp,
+                             float_bits.get_explicit_mantissa());
+    }
+  }
+
+  round = get_round_direction(last_digit, truncated, is_negative);
 
   bool round_up;
   if (round == RoundDirection::Up) {
     round_up = true;
   } else if (round == RoundDirection::Down) {
     round_up = false;
   } else {
-    // RoundDirection is even, so check the extra digit.
-    uint32_t low_digit = digits % 10;
+    // RoundDirection is even, so check the lowest digit that will be printed.
+    uint32_t low_digit;
+
+    // maximum is the number of digits that will remain in digits after getting
+    // last_digit. If it's greater than zero, we can just check the lowest digit
+    // in digits.
+    if (maximum > 0) {
+      low_digit = digits % 10;
+    } else {
+      // Else if there are trailing nines, then the low digit is a nine, same
+      // with zeroes.
+      if (trailing_nines > 0) {
+        low_digit = 9;
+      } else if (trailing_zeroes > 0) {
+        low_digit = 0;
+      } else {
+        // If there are no trailing zeroes or nines, then the round direction
+        // doesn't actually matter here. Since this conversion passes off the
+        // value to another one for final conversion, rounding only matters to
+        // determine if the exponent is higher than expected (with an all nine
+        // number) or to determine the trailing zeroes to trim. In this case
+        // low_digit is set to 0, but it could be set to any number.
+
+        low_digit = 0;
+      }
+    }
     round_up = (low_digit % 2) != 0;
   }
 
   digits_checked += digits_requested;
   LIBC_ASSERT(digits_checked == init_precision);
   // At this point we should have checked all the digits requested by the
   // precision. We may increment this number 1 more if we round up all of the
   // digits, but at this point in the code digits_checked should always equal

libc/test/src/stdio/sprintf_test.cpp

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];
+  char big_buff[10000]; // Used for long doubles and other extremely wide
+                        // numbers.
 
   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);
TEST_F(LlvmLibcSPrintfTest, FloatExponentConv) {
   written = __llvm_libc::sprintf(buff, "%e", nan);
   ASSERT_STREQ_LEN(written, buff, "nan");
 
   written = __llvm_libc::sprintf(buff, "%E", -nan);
   ASSERT_STREQ_LEN(written, buff, "-NAN");
 
   // Length Modifier Tests.
 
+#if defined(SPECIAL_X86_LONG_DOUBLE)
+  written = __llvm_libc::sprintf(buff, "%.9Le", 1000000000500000000.1L);
+  ASSERT_STREQ_LEN(written, buff, "1.000000001e+18");
+
+  written = __llvm_libc::sprintf(buff, "%.9Le", 1000000000500000000.0L);
+  ASSERT_STREQ_LEN(written, buff, "1.000000000e+18");
+#endif
+
   // 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", 1e100L);
   ASSERT_STREQ_LEN(written, buff,
                    "99999999999999999996693535322073426194986990198284960792713"
                    "91541752018669482644324418977840117055488.000000");
 
*/
   ASSERT_STREQ_LEN(written, buff, "0.00000e+00");
 
   written = __llvm_libc::sprintf(buff, "%.5e", 1.008);
   ASSERT_STREQ_LEN(written, buff, "1.00800e+00");
 
   written = __llvm_libc::sprintf(buff, "%.5e", 1.008e3);
   ASSERT_STREQ_LEN(written, buff, "1.00800e+03");
 
+  // These tests also focus on rounding. Almost all of them have a 5 right after
+  // the printed string (e.g. 9.5 with precision 0 prints 0 digits after the
+  // decimal point). This is again because rounding a number with a 5 after the
+  // printed section means that more digits have to be checked to determine if
+  // this should be rounded up (if there are non-zero digits after the 5) or to
+  // even (if the 5 is the last non-zero digit). Additionally, the algorithm for
+  // checking if a number is all 0s after the decimal point may not work since
+  // the decimal point moves in this representation.
+  written = __llvm_libc::sprintf(buff, "%.0e", 2.5812229360061737E+200);
+  ASSERT_STREQ_LEN(written, buff, "3e+200");
+
+  written = __llvm_libc::sprintf(buff, "%.1e", 9.059E+200);
+  ASSERT_STREQ_LEN(written, buff, "9.1e+200");
+
+  written = __llvm_libc::sprintf(buff, "%.0e", 9.059E+200);
+  ASSERT_STREQ_LEN(written, buff, "9e+200");
+
+  written = __llvm_libc::sprintf(buff, "%.166e", 1.131959884853339E-72);
+  ASSERT_STREQ_LEN(written, buff,
+                   "1."
+                   "13195988485333904593863991136097397258531639976739227369782"
+                   "68612419376648241056393424414314951197624317440549121097287"
+                   "069853416091591569170304865110665559768676757812e-72");
+
+  written = __llvm_libc::sprintf(buff, "%.0e", 9.5);
+  ASSERT_STREQ_LEN(written, buff, "1e+01");
+
+  written = __llvm_libc::sprintf(buff, "%.10e", 1.9999999999890936);
+  ASSERT_STREQ_LEN(written, buff, "2.0000000000e+00");
+
+  written = __llvm_libc::sprintf(buff, "%.1e", 745362143563.03894);
+  ASSERT_STREQ_LEN(written, buff, "7.5e+11");
+
+  written = __llvm_libc::sprintf(buff, "%.0e", 45181042688.0);
+  ASSERT_STREQ_LEN(written, buff, "5e+10");
+
+  written = __llvm_libc::sprintf(buff, "%.35e", 1.3752441369139243);
+  ASSERT_STREQ_LEN(written, buff, "1.37524413691392433101157166674965993e+00");
+
   // Subnormal Precision Tests
 
   written = __llvm_libc::sprintf(buff, "%.310e", 0x1.0p-1022);
   ASSERT_STREQ_LEN(
       written, buff,
       "2."
       "225073858507201383090232717332404064219215980462331830553327416887204434"
       "813918195854283159012511020564067339731035811005152434161553460108856012"
*/
 
   written = __llvm_libc::sprintf(buff, "%.3g", 1256.0);
   ASSERT_STREQ_LEN(written, buff, "1.26e+03");
 
   // Found through large scale testing.
   written = __llvm_libc::sprintf(buff, "%.15g", 22.25);
   ASSERT_STREQ_LEN(written, buff, "22.25");
 
-  // Subnormal Precision Tests
+  // These tests also focus on rounding, but only in how it relates to the base
+  // 10 exponent. The %g conversion selects between being a %f or %e conversion
+  // based on what the exponent would be if it was %e. If we call the precision
+  // P (equal to 6 if the precision is not set, 0 if the provided precision is
+  // 0, and provided precision - 1 otherwise) and the exponent X, then the style
+  // is %f with an effective precision of P - X + 1 if P > X >= -4, else the
+  // style is %e with effective precision P - 1. Additionally, it attempts to
+  // trim zeros that would be displayed after the decimal point.
+  written = __llvm_libc::sprintf(buff, "%.1g", 9.059E+200);
+  ASSERT_STREQ_LEN(written, buff, "9e+200");
+
+  written = __llvm_libc::sprintf(buff, "%.2g", 9.059E+200);
+  ASSERT_STREQ_LEN(written, buff, "9.1e+200");
 
+  // For this test, P = 0 and X = 1, so P > X >= -4 is false, giving a %e style.
+  written = __llvm_libc::sprintf(buff, "%.0g", 9.5);
+  ASSERT_STREQ_LEN(written, buff, "1e+01");
+
+  // Subnormal Precision Tests
   written = __llvm_libc::sprintf(buff, "%.310g", 0x1.0p-1022);
   ASSERT_STREQ_LEN(
       written, buff,
       "2."
       "225073858507201383090232717332404064219215980462331830553327416887204434"
       "813918195854283159012511020564067339731035811005152434161553460108856012"
       "385377718821130777993532002330479610147442583636071921565046942503734208"
       "375250806650616658158948720491179968591639648500635908770118304874799780"