[libc][NFC] Add supporting class for atof implementation

[michaelrj]

Summary

This change adds the High Precision Decimal described here:
https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html
It will be used for the atof implementation later, but is complete and
tested now.

The code is inspired by the golang implmentation of the HPD class, which
can be found here: https://github.com/golang/go/blob/release-branch.go1.16/src/strconv/decimal.go

[michaelrj]

parse the decimal point out of the string. This meant I needed to change the imports so I could use strtointeger for the integer parsing.

[michaelrj]

update the comments and add a file to generate the constant table

[sivachandra]

libc/src/__support/GenerateHPDConstants.py

1 ↗

(On Diff #376349)

This file should go in https://github.com/llvm/llvm-project/tree/main/libc/utils/mathtools.

Also, please add a detailed doc comment about what this script is for.

libc/src/__support/high_precision_decimal.h

33

Add a note here that these constants were generated using the <link/to/the/script/in/utils/mathtools/>.

[michaelrj]

move the constant generation script and add an explanation of what it is and how it works.

libc/src/__support/GenerateHPDConstants.py

1 ↗

(On Diff #376349)

I may have gone a bit overboard with this one, but I wanted to have a clear explanation of how and why this trick works. I can make it a bit shorter if you want.

libc/src/__support/CMakeLists.txt

 add_header_library(
   common
   HDRS
     common.h
     endian.h
     sanitizer.h
 )
 
 add_header_library(
   ctype_utils
   HDRS
     ctype_utils.h
 )
 
 add_header_library(
+  high_precision_decimal
+  HDRS
+    high_precision_decimal.h
+
+)
+
+add_header_library(
   str_conv_utils
   HDRS
     str_conv_utils.h
   DEPENDS
     .ctype_utils
+    .high_precision_decimal
     libc.include.errno
     libc.src.errno.__errno_location
     libc.utils.CPP.standalone_cpp
 )
 
 add_header_library(
   integer_operations
   HDRS
     integer_operations.h
 )
 
 add_subdirectory(FPUtil)

libc/src/__support/high_precision_decimal.h

+//===-- High Precision Decimal ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See httpss//llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBC_SRC_SUPPORT_HIGH_PRECISION_DECIMAL_H
+#define LIBC_SRC_SUPPORT_HIGH_PRECISION_DECIMAL_H
+
+#include "src/__support/ctype_utils.h"
+#include <stdint.h>
+
+namespace __llvm_libc {
+namespace internal {
+
+struct LeftCheat {
+  int delta;
+  char const *string;
+};
+
+// This is based on the HPD data structure described as part of the Simple
+// Decimal Conversion algorithm by Nigel Tao, described at this link:
+// https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html
+// And the golang implmentation, also by Nigel Tao:
+// https://github.com/golang/go/blob/release-branch.go1.16/src/strconv/decimal.go
+class HighPrecsisionDecimal {
+
+  // This cheat sheet speeds up left shifts.
+  // Indexed by shift count, it contains the number of new digits that will be
+  // introduced by that shift.
+  //
+  // For example, LEFT_SHIFT_CHEAT_SHEET[4] = {2, "625"}.  That means that
+  // if we are shifting by 4 (multiplying by 16), it will add 2 digits
+  // when the string prefix is "625" through "999", and one fewer digit
+  // if the string prefix is "000" through "624".
+  //
+  // Credit for this trick goes to Ken Thompson.
+  static constexpr LeftCheat LEFT_SHIFT_CHEAT_SHEET[] = {
+      {0, ""},
+      {1, "5"},                                          // * 2
+      {1, "25"},                                         // * 4
+      {1, "125"},                                        // * 8
+      {2, "625"},                                        // * 16
+      {2, "3125"},                                       // * 32
+      {2, "15625"},                                      // * 64
+      {3, "78125"},                                      // * 128
+      {3, "390625"},                                     // * 256
+      {3, "1953125"},                                    // * 512
+      {4, "9765625"},                                    // * 1024
+      {4, "48828125"},                                   // * 2048
+      {4, "244140625"},                                  // * 4096
+      {4, "1220703125"},                                 // * 8192
+      {5, "6103515625"},                                 // * 16384
+      {5, "30517578125"},                                // * 32768
+      {5, "152587890625"},                               // * 65536
+      {6, "762939453125"},                               // * 131072
+      {6, "3814697265625"},                              // * 262144
+      {6, "19073486328125"},                             // * 524288
+      {7, "95367431640625"},                             // * 1048576
+      {7, "476837158203125"},                            // * 2097152
+      {7, "2384185791015625"},                           // * 4194304
+      {7, "11920928955078125"},                          // * 8388608
+      {8, "59604644775390625"},                          // * 16777216
+      {8, "298023223876953125"},                         // * 33554432
+      {8, "1490116119384765625"},                        // * 67108864
+      {9, "7450580596923828125"},                        // * 134217728
+      {9, "37252902984619140625"},                       // * 268435456
+      {9, "186264514923095703125"},                      // * 536870912
+      {10, "931322574615478515625"},                     // * 1073741824
+      {10, "4656612873077392578125"},                    // * 2147483648
+      {10, "23283064365386962890625"},                   // * 4294967296
+      {10, "116415321826934814453125"},                  // * 8589934592
+      {11, "582076609134674072265625"},                  // * 17179869184
+      {11, "2910383045673370361328125"},                 // * 34359738368
+      {11, "14551915228366851806640625"},                // * 68719476736
+      {12, "72759576141834259033203125"},                // * 137438953472
+      {12, "363797880709171295166015625"},               // * 274877906944
+      {12, "1818989403545856475830078125"},              // * 549755813888
+      {13, "9094947017729282379150390625"},              // * 1099511627776
+      {13, "45474735088646411895751953125"},             // * 2199023255552
+      {13, "227373675443232059478759765625"},            // * 4398046511104
+      {13, "1136868377216160297393798828125"},           // * 8796093022208
+      {14, "5684341886080801486968994140625"},           // * 17592186044416
+      {14, "28421709430404007434844970703125"},          // * 35184372088832
+      {14, "142108547152020037174224853515625"},         // * 70368744177664
+      {15, "710542735760100185871124267578125"},         // * 140737488355328
+      {15, "3552713678800500929355621337890625"},        // * 281474976710656
+      {15, "17763568394002504646778106689453125"},       // * 562949953421312
+      {16, "88817841970012523233890533447265625"},       // * 1125899906842624
+      {16, "444089209850062616169452667236328125"},      // * 2251799813685248
+      {16, "2220446049250313080847263336181640625"},     // * 4503599627370496
+      {16, "11102230246251565404236316680908203125"},    // * 9007199254740992
+      {17, "55511151231257827021181583404541015625"},    // * 18014398509481984
+      {17, "277555756156289135105907917022705078125"},   // * 36028797018963968
+      {17, "1387778780781445675529539585113525390625"},  // * 72057594037927936
+      {18, "6938893903907228377647697925567626953125"},  // * 144115188075855872
+      {18, "34694469519536141888238489627838134765625"}, // * 288230376151711744
+      {18,
+       "173472347597680709441192448139190673828125"}, // * 576460752303423488
+      {19,
+       "867361737988403547205962240695953369140625"}, // * 1152921504606846976
+  };
+
+  static constexpr uint32_t MAX_SHIFT_AMOUNT = 64 - 4;
+
+  // 800 is an arbitrary number of digits, but should be
+  // large enough for any practical number.
+  static constexpr uint32_t MAX_NUM_DIGITS = 800;
+
+  uint32_t numDigits = 0;
+  int32_t decimalPoint = 0;
+  bool truncated = false;
+  uint8_t digits[MAX_NUM_DIGITS];
+
+private:
+  bool shouldRoundUp(uint32_t roundToDigit) {
+    if (roundToDigit < 0 || roundToDigit >= this->numDigits) {
+      return false;
+    }
+    if (this->digits[roundToDigit] == 5 &&
+        roundToDigit + 1 == this->numDigits) {
+      // This exactly halfway, so round to even.
+
+      // if we've truncated, then round up.
+      if (this->truncated) {
+        return true;
+      }
+
+      // Extra condition to prevent underflow
+      return roundToDigit > 0 && (this->digits[roundToDigit - 1] % 2 != 0);
+    }
+    return this->digits[roundToDigit] >= 5;
+  }
+
+  // check if the leading prefix of digits[] is lexographically less than char*
+  // other
+  bool prefixIsLessThan(char const *other) {
+    uint32_t digitIndex = 0;
+    while (other[digitIndex] != 0) {
+      if (digitIndex >= this->numDigits) {
+        return true;
+      }
+      if (this->digits[digitIndex] != other[digitIndex] - '0') {
+        return this->digits[digitIndex] < other[digitIndex] - '0';
+      }
+    }
+    return false;
+  }
+
+  // Trim all trailing 0s
+  void trim() {
+    while (this->numDigits > 0 && this->digits[this->numDigits - 1] == 0) {
+      --this->numDigits;
+    }
+    if (this->numDigits == 0) {
+      this->decimalPoint = 0;
+    }
+  }
+
+  // Perform a digitwise binary non-rounding right shift on this value by
+  // shiftAmount. The shiftAmount can't be more than MAX_SHIFT_AMOUNT to prevent
+  // overflow.
+  void rightShift(uint32_t shiftAmount) {
+    uint32_t readIndex = 0;
+    uint32_t writeIndex = 0;
+
+    uint64_t accumulator = 0;
+
+    // Warm Up phase: we don't have enough digits to start writing, so just
+    // read
+    while (accumulator >> shiftAmount == 0) {
+      if (readIndex >= this->numDigits) {
+        if (accumulator == 0) {
+          // This should only happen when trying to shift a 0, which should
+          // never happen, but it's easier to include a case.
+          this->numDigits = 0;
+          return;
+        }
+        // Since there are no more defined digits, all remaining digits are
+        // assumed to be 0.
+        while (accumulator >> shiftAmount == 0) {
+          accumulator *= 10;
+          ++readIndex;
+        }
+        break;
+      }
+      accumulator =
+          accumulator * 10 + static_cast<uint64_t>(this->digits[readIndex]);
+      ++readIndex;
+    }
+
+    this->decimalPoint -= readIndex - 1;
+
+    const uint64_t mask =
+        (uint64_t(1) << static_cast<uint64_t>(shiftAmount)) - uint64_t(1);
+
+    // Middle phase: we have enough digits to write, as well as more digits to
+    // read
+    while (readIndex < this->numDigits) {
+      uint64_t readDigit = this->digits[readIndex];
+      uint64_t writeDigit = accumulator >> shiftAmount;
+      accumulator &= mask;
+      this->digits[writeIndex] = static_cast<uint8_t>(writeDigit);
+      ++writeIndex;
+      accumulator = accumulator * 10 + readDigit;
+      ++readIndex;
+    }
+
+    // Cool Down phase: All of the readable digits have been read, so just write
+    // the remainder.
+    while (accumulator > 0) {
+      uint64_t writeDigit = accumulator >> shiftAmount;
+      accumulator &= mask;
+      if (writeIndex < MAX_NUM_DIGITS) {
+        this->digits[writeIndex] = static_cast<uint8_t>(writeDigit);
+        ++writeIndex;
+      } else if (writeDigit > 0) {
+        this->truncated = true;
+      }
+      accumulator = accumulator * 10;
+    }
+    this->numDigits = writeIndex;
+    this->trim();
+  }
+
+  // Perform a digitwise binary non-rounding left shift on this value by
+  // shiftAmount. The shiftAmount can't be more than MAX_SHIFT_AMOUNT to prevent
+  // overflow.
+  void leftShift(uint32_t shiftAmount) {
+    int delta = LEFT_SHIFT_CHEAT_SHEET[shiftAmount].delta;
+    if (prefixIsLessThan(LEFT_SHIFT_CHEAT_SHEET[shiftAmount].string)) {
+      --delta;
+    }
+
+    int32_t readIndex = this->numDigits - 1;
+    uint32_t writeIndex = this->numDigits + delta;
+
+    uint64_t accumulator = 0;
+
+    // No Warm Up phase. Since we're putting digits in at the top and taking
+    // digits from the bottom we don't have to wait for the accumulator to fill.
+
+    // Middle phase: while we have more digits to read, keep reading as well as
+    // writing.
+    while (readIndex >= 0) {
+      accumulator += static_cast<uint64_t>(this->digits[readIndex])
+                     << shiftAmount;
+      uint64_t quotient = accumulator / 10;
+      uint64_t remainder = accumulator - (10 * quotient);
+      --writeIndex;
+      if (writeIndex < MAX_NUM_DIGITS) {
+        this->digits[writeIndex] = static_cast<uint8_t>(remainder);
+      } else if (remainder != 0) {
+        this->truncated = true;
+      }
+      accumulator = quotient;
+      --readIndex;
+    }
+
+    // Cool Down phase: there are no more digits to read, so just write the
+    // remaining digits in the accumulator.
+    while (accumulator > 0) {
+      uint64_t quotient = accumulator / 10;
+      uint64_t remainder = accumulator - (10 * quotient);
+      --writeIndex;
+      if (writeIndex < MAX_NUM_DIGITS) {
+        this->digits[writeIndex] = static_cast<uint8_t>(remainder);
+      } else if (remainder != 0) {
+        this->truncated = true;
+      }
+      accumulator = quotient;
+    }
+
+    this->numDigits += delta;
+    if (this->numDigits >= MAX_NUM_DIGITS) {
+      this->numDigits = MAX_NUM_DIGITS;
+    }
+    this->decimalPoint += delta;
+    this->trim();
+  }
+
+public:
+  // numString is assumed to be a string of numeric characters. It doesn't
+  // handle leading spaces. Decimal point is set based on the provided exp10,
+  // not the actual string.
+  HighPrecsisionDecimal(const char *__restrict numString,
+                        int32_t decimalPoint) {
+    bool sawDot = false;
+    bool sawDigit = false;
+    while (isdigit(*numString) || *numString == '.') {
+      if (*numString == '.') {
+        if (sawDot) {
+          break;
+        }
+        sawDot = true;
+      } else {
+        sawDigit = true;
+        if (this->numDigits < MAX_NUM_DIGITS) {
+          this->digits[this->numDigits] = *numString - '0';
+          ++this->numDigits;
+        } else if (*numString != '0') {
+          this->truncated = true;
+        }
+      }
+      ++numString;
+    }
+    this->decimalPoint = decimalPoint;
+  }
+
+  // Binary shift left (shiftAmount > 0) or right (shiftAmount < 0)
+  void shift(int shiftAmount) {
+    if (shiftAmount == 0) {
+      return;
+    }
+    // Left
+    else if (shiftAmount > 0) {
+      while (static_cast<uint32_t>(shiftAmount) > MAX_SHIFT_AMOUNT) {
+        this->leftShift(MAX_SHIFT_AMOUNT);
+        shiftAmount -= MAX_SHIFT_AMOUNT;
+      }
+      this->leftShift(shiftAmount);
+    }
+    // Right
+    else {
+      while (static_cast<uint32_t>(shiftAmount) < -MAX_SHIFT_AMOUNT) {
+        this->rightShift(MAX_SHIFT_AMOUNT);
+        shiftAmount += MAX_SHIFT_AMOUNT;
+      }
+      this->rightShift(-shiftAmount);
+    }
+  }
+
+  // Round the number represented to the closest value of unsigned int type T.
+  // This is done ignoring overflow.
+  template <class T> T roundToIntegerType() {
+    T result = 0;
+    uint32_t curDigit = 0;
+
+    while (static_cast<int32_t>(curDigit) < this->decimalPoint &&
+           curDigit < this->numDigits) {
+      result = result * 10 + (this->digits[curDigit]);
+      ++curDigit;
+    }
+
+    // If there are implicit 0s at the end of the number, include those.
+    while (static_cast<int32_t>(curDigit) < this->decimalPoint) {
+      result *= 10;
+      ++curDigit;
+    }
+    if (this->shouldRoundUp(this->decimalPoint)) {
+      ++result;
+    }
+    return result;
+  }
+
+  // Extra functions for testing.
+
+  uint8_t *getDigits() { return this->digits; }
+  uint32_t getNumDigits() { return this->numDigits; }
+  int32_t getDecimalPoint() { return this->decimalPoint; }
+  void setTruncated(bool trunc) { this->truncated = trunc; }
+};
+
+} // namespace internal
+} // namespace __llvm_libc
+
+#endif // LIBC_SRC_SUPPORT_HIGH_PRECISION_DECIMAL_H

libc/src/__support/str_conv_utils.h

 //===-- Stdlib utils --------------------------------------------*- 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 LIBC_SRC_STDLIB_STDLIB_UTILS_H
 #define LIBC_SRC_STDLIB_STDLIB_UTILS_H
 
 #include "src/__support/ctype_utils.h"
+#include "src/__support/high_precision_decimal.h"
 #include "utils/CPP/Limits.h"
 #include <errno.h>
 #include <limits.h>
 
 namespace __llvm_libc {
 namespace internal {
 
 // Returns a pointer to the first character in src that is not a whitespace

libc/test/src/__support/CMakeLists.txt

 add_libc_testsuite(libc_support_unittests)
 
 add_libc_unittest(
   endian_test
   SUITE
     libc_support_unittests
   SRCS
     endian_test.cpp
   DEPENDS
     libc.src.__support.common
 )
+
+add_libc_unittest(
+  high_precision_decimal_test
+  SUITE
+    libc_support_unittests
+  SRCS
+  high_precision_decimal_test.cpp
+  DEPENDS
+    libc.src.__support.high_precision_decimal
+)

libc/test/src/__support/high_precision_decimal_test.cpp

+//===-- Unittests for high_precision_decimal ------------------------------===//
+//
+// 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/__support/high_precision_decimal.h"
+
+#include "utils/UnitTest/Test.h"
+
+TEST(LlvmLibcHighPrecisionDecimalTest, BasicInit) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal("1.2345", 1);
+  uint8_t *digits = hpd.getDigits();
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(2));
+  EXPECT_EQ(digits[2], uint8_t(3));
+  EXPECT_EQ(digits[3], uint8_t(4));
+  EXPECT_EQ(digits[4], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 5u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 1);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, SmallShift) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal("1.2345", 1);
+  uint8_t *digits = hpd.getDigits();
+
+  hpd.shift(-1); // shift right one, equal to dividing by 2
+  // result should be 0.61725
+
+  EXPECT_EQ(digits[0], uint8_t(6));
+  EXPECT_EQ(digits[1], uint8_t(1));
+  EXPECT_EQ(digits[2], uint8_t(7));
+  EXPECT_EQ(digits[3], uint8_t(2));
+  EXPECT_EQ(digits[4], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 5u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 0);
+
+  hpd.shift(1); // shift left one, equal to multiplying by 2
+  // result should be 1.2345 again
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(2));
+  EXPECT_EQ(digits[2], uint8_t(3));
+  EXPECT_EQ(digits[3], uint8_t(4));
+  EXPECT_EQ(digits[4], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 5u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 1);
+
+  hpd.shift(1); // shift left one again
+  // result should be 2.469
+
+  EXPECT_EQ(digits[0], uint8_t(2));
+  EXPECT_EQ(digits[1], uint8_t(4));
+  EXPECT_EQ(digits[2], uint8_t(6));
+  EXPECT_EQ(digits[3], uint8_t(9));
+  EXPECT_EQ(hpd.getNumDigits(), 4u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 1);
+
+  hpd.shift(-1); // shift right one again
+  // result should be 1.2345 again
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(2));
+  EXPECT_EQ(digits[2], uint8_t(3));
+  EXPECT_EQ(digits[3], uint8_t(4));
+  EXPECT_EQ(digits[4], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 5u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 1);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, MediumShift) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal(".299792458", 0);
+  uint8_t *digits = hpd.getDigits();
+
+  hpd.shift(-3); // shift right three, equal to dividing by 8
+  // result should be 0.03747405725
+
+  EXPECT_EQ(digits[0], uint8_t(3));
+  EXPECT_EQ(digits[1], uint8_t(7));
+  EXPECT_EQ(digits[2], uint8_t(4));
+  EXPECT_EQ(digits[3], uint8_t(7));
+  EXPECT_EQ(digits[4], uint8_t(4));
+  EXPECT_EQ(digits[5], uint8_t(0));
+  EXPECT_EQ(digits[6], uint8_t(5));
+  EXPECT_EQ(digits[7], uint8_t(7));
+  EXPECT_EQ(digits[8], uint8_t(2));
+  EXPECT_EQ(digits[9], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 10u);
+  EXPECT_EQ(hpd.getDecimalPoint(), -1);
+
+  hpd.shift(3); // shift left three, equal to multiplying by 8
+  // result should be 0.299792458 again
+
+  EXPECT_EQ(digits[0], uint8_t(2));
+  EXPECT_EQ(digits[1], uint8_t(9));
+  EXPECT_EQ(digits[2], uint8_t(9));
+  EXPECT_EQ(digits[3], uint8_t(7));
+  EXPECT_EQ(digits[4], uint8_t(9));
+  EXPECT_EQ(digits[5], uint8_t(2));
+  EXPECT_EQ(digits[6], uint8_t(4));
+  EXPECT_EQ(digits[7], uint8_t(5));
+  EXPECT_EQ(digits[8], uint8_t(8));
+  EXPECT_EQ(hpd.getNumDigits(), 9u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 0);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, BigShift) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal(".299792458", 0);
+  uint8_t *digits = hpd.getDigits();
+
+  hpd.shift(-29); // shift right 29, equal to dividing by 536,870,912
+  // result should be 0.0000000005584069676697254180908203125
+
+  EXPECT_EQ(digits[0], uint8_t(5));
+  EXPECT_EQ(digits[1], uint8_t(5));
+  EXPECT_EQ(digits[2], uint8_t(8));
+  EXPECT_EQ(digits[3], uint8_t(4));
+  EXPECT_EQ(digits[4], uint8_t(0));
+  EXPECT_EQ(digits[5], uint8_t(6));
+  EXPECT_EQ(digits[6], uint8_t(9));
+  EXPECT_EQ(digits[7], uint8_t(6));
+  EXPECT_EQ(digits[8], uint8_t(7));
+  EXPECT_EQ(digits[9], uint8_t(6));
+  EXPECT_EQ(digits[10], uint8_t(6));
+  EXPECT_EQ(digits[11], uint8_t(9));
+  EXPECT_EQ(digits[12], uint8_t(7));
+  EXPECT_EQ(digits[13], uint8_t(2));
+  EXPECT_EQ(digits[14], uint8_t(5));
+  EXPECT_EQ(digits[15], uint8_t(4));
+  EXPECT_EQ(digits[16], uint8_t(1));
+  EXPECT_EQ(digits[17], uint8_t(8));
+  EXPECT_EQ(digits[18], uint8_t(0));
+  EXPECT_EQ(digits[19], uint8_t(9));
+  EXPECT_EQ(digits[20], uint8_t(0));
+  EXPECT_EQ(digits[21], uint8_t(8));
+  EXPECT_EQ(digits[22], uint8_t(2));
+  EXPECT_EQ(digits[23], uint8_t(0));
+  EXPECT_EQ(digits[24], uint8_t(3));
+  EXPECT_EQ(digits[25], uint8_t(1));
+  EXPECT_EQ(digits[26], uint8_t(2));
+  EXPECT_EQ(digits[27], uint8_t(5));
+  EXPECT_EQ(hpd.getNumDigits(), 28u);
+  EXPECT_EQ(hpd.getDecimalPoint(), -9);
+
+  hpd.shift(29); // shift left 29, equal to multiplying by 536,870,912
+  // result should be 0.299792458 again
+
+  EXPECT_EQ(digits[0], uint8_t(2));
+  EXPECT_EQ(digits[1], uint8_t(9));
+  EXPECT_EQ(digits[2], uint8_t(9));
+  EXPECT_EQ(digits[3], uint8_t(7));
+  EXPECT_EQ(digits[4], uint8_t(9));
+  EXPECT_EQ(digits[5], uint8_t(2));
+  EXPECT_EQ(digits[6], uint8_t(4));
+  EXPECT_EQ(digits[7], uint8_t(5));
+  EXPECT_EQ(digits[8], uint8_t(8));
+  EXPECT_EQ(hpd.getNumDigits(), 9u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 0);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, BigShiftInSteps) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal("1", 1);
+  uint8_t *digits = hpd.getDigits();
+
+  hpd.shift(60); // shift left 60, equal to multiplying by
+                 // 1152921504606846976.
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(1));
+  EXPECT_EQ(digits[2], uint8_t(5));
+  EXPECT_EQ(digits[3], uint8_t(2));
+  EXPECT_EQ(digits[4], uint8_t(9));
+  EXPECT_EQ(digits[5], uint8_t(2));
+  EXPECT_EQ(digits[6], uint8_t(1));
+  EXPECT_EQ(digits[7], uint8_t(5));
+  EXPECT_EQ(digits[8], uint8_t(0));
+  EXPECT_EQ(digits[9], uint8_t(4));
+  EXPECT_EQ(digits[10], uint8_t(6));
+  EXPECT_EQ(digits[11], uint8_t(0));
+  EXPECT_EQ(digits[12], uint8_t(6));
+  EXPECT_EQ(digits[13], uint8_t(8));
+  EXPECT_EQ(digits[14], uint8_t(4));
+  EXPECT_EQ(digits[15], uint8_t(6));
+  EXPECT_EQ(digits[16], uint8_t(9));
+  EXPECT_EQ(digits[17], uint8_t(7));
+  EXPECT_EQ(digits[18], uint8_t(6));
+  EXPECT_EQ(hpd.getNumDigits(), 19u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 19);
+
+  hpd.shift(40); // shift left 40, equal to multiplying by
+                 // 1099511627776. Result should be 2^100
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(2));
+  EXPECT_EQ(digits[2], uint8_t(6));
+  EXPECT_EQ(digits[3], uint8_t(7));
+  EXPECT_EQ(digits[4], uint8_t(6));
+  EXPECT_EQ(digits[5], uint8_t(5));
+  EXPECT_EQ(digits[6], uint8_t(0));
+  EXPECT_EQ(digits[7], uint8_t(6));
+  EXPECT_EQ(digits[8], uint8_t(0));
+  EXPECT_EQ(digits[9], uint8_t(0));
+  EXPECT_EQ(digits[10], uint8_t(2));
+  EXPECT_EQ(digits[11], uint8_t(2));
+  EXPECT_EQ(digits[12], uint8_t(8));
+  EXPECT_EQ(digits[13], uint8_t(2));
+  EXPECT_EQ(digits[14], uint8_t(2));
+  EXPECT_EQ(digits[15], uint8_t(9));
+  EXPECT_EQ(digits[16], uint8_t(4));
+  EXPECT_EQ(digits[17], uint8_t(0));
+  EXPECT_EQ(digits[18], uint8_t(1));
+  EXPECT_EQ(digits[19], uint8_t(4));
+  EXPECT_EQ(digits[20], uint8_t(9));
+  EXPECT_EQ(digits[21], uint8_t(6));
+  EXPECT_EQ(digits[22], uint8_t(7));
+  EXPECT_EQ(digits[23], uint8_t(0));
+  EXPECT_EQ(digits[24], uint8_t(3));
+  EXPECT_EQ(digits[25], uint8_t(2));
+  EXPECT_EQ(digits[26], uint8_t(0));
+  EXPECT_EQ(digits[27], uint8_t(5));
+  EXPECT_EQ(digits[28], uint8_t(3));
+  EXPECT_EQ(digits[29], uint8_t(7));
+  EXPECT_EQ(digits[30], uint8_t(6));
+
+  EXPECT_EQ(hpd.getNumDigits(), 31u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 31);
+
+  hpd.shift(-60); // shift right 60, equal to dividing by
+                  // 1152921504606846976. Result should be 2^40
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(0));
+  EXPECT_EQ(digits[2], uint8_t(9));
+  EXPECT_EQ(digits[3], uint8_t(9));
+  EXPECT_EQ(digits[4], uint8_t(5));
+  EXPECT_EQ(digits[5], uint8_t(1));
+  EXPECT_EQ(digits[6], uint8_t(1));
+  EXPECT_EQ(digits[7], uint8_t(6));
+  EXPECT_EQ(digits[8], uint8_t(2));
+  EXPECT_EQ(digits[9], uint8_t(7));
+  EXPECT_EQ(digits[10], uint8_t(7));
+  EXPECT_EQ(digits[11], uint8_t(7));
+  EXPECT_EQ(digits[12], uint8_t(6));
+
+  EXPECT_EQ(hpd.getNumDigits(), 13u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 13);
+
+  hpd.shift(-40); // shift right 40, equal to dividing by
+                  // 1099511627776. Result should be 1
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+
+  EXPECT_EQ(hpd.getNumDigits(), 1u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 1);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, VeryBigShift) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal("1", -10);
+  uint8_t *digits = hpd.getDigits();
+
+  hpd.shift(100); // shift left 100, equal to multiplying by
+                  // 1267650600228229401496703205376.
+  // result should be 2^100
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(digits[1], uint8_t(2));
+  EXPECT_EQ(digits[2], uint8_t(6));
+  EXPECT_EQ(digits[3], uint8_t(7));
+  EXPECT_EQ(digits[4], uint8_t(6));
+  EXPECT_EQ(digits[5], uint8_t(5));
+  EXPECT_EQ(digits[6], uint8_t(0));
+  EXPECT_EQ(digits[7], uint8_t(6));
+  EXPECT_EQ(digits[8], uint8_t(0));
+  EXPECT_EQ(digits[9], uint8_t(0));
+  EXPECT_EQ(digits[10], uint8_t(2));
+  EXPECT_EQ(digits[11], uint8_t(2));
+  EXPECT_EQ(digits[12], uint8_t(8));
+  EXPECT_EQ(digits[13], uint8_t(2));
+  EXPECT_EQ(digits[14], uint8_t(2));
+  EXPECT_EQ(digits[15], uint8_t(9));
+  EXPECT_EQ(digits[16], uint8_t(4));
+  EXPECT_EQ(digits[17], uint8_t(0));
+  EXPECT_EQ(digits[18], uint8_t(1));
+  EXPECT_EQ(digits[19], uint8_t(4));
+  EXPECT_EQ(digits[20], uint8_t(9));
+  EXPECT_EQ(digits[21], uint8_t(6));
+  EXPECT_EQ(digits[22], uint8_t(7));
+  EXPECT_EQ(digits[23], uint8_t(0));
+  EXPECT_EQ(digits[24], uint8_t(3));
+  EXPECT_EQ(digits[25], uint8_t(2));
+  EXPECT_EQ(digits[26], uint8_t(0));
+  EXPECT_EQ(digits[27], uint8_t(5));
+  EXPECT_EQ(digits[28], uint8_t(3));
+  EXPECT_EQ(digits[29], uint8_t(7));
+  EXPECT_EQ(digits[30], uint8_t(6));
+
+  EXPECT_EQ(hpd.getNumDigits(), 31u);
+  EXPECT_EQ(hpd.getDecimalPoint(), 20);
+
+  hpd.shift(-100); // shift right 100, equal to dividing by
+                   // 1267650600228229401496703205376.
+  // result should be 1
+
+  EXPECT_EQ(digits[0], uint8_t(1));
+  EXPECT_EQ(hpd.getNumDigits(), 1u);
+  EXPECT_EQ(hpd.getDecimalPoint(), -10);
+}
+
+TEST(LlvmLibcHighPrecisionDecimalTest, RoundingTest) {
+  __llvm_libc::internal::HighPrecsisionDecimal hpd =
+      __llvm_libc::internal::HighPrecsisionDecimal("1.2345", 1);
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint32_t>(), uint32_t(1));
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(1));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(1));
+
+  hpd.shift(1); // shift left 1 to get 2.469 (rounds to 2)
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint32_t>(), uint32_t(2));
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(2));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(2));
+
+  hpd.shift(1); // shift left 1 to get 4.938 (rounds to 5)
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint32_t>(), uint32_t(5));
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(5));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(5));
+
+  // 2.5 is right between two integers, so we round to even (2)
+  hpd = __llvm_libc::internal::HighPrecsisionDecimal("2.5", 1);
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint32_t>(), uint32_t(2));
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(2));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(2));
+
+  // unless it's marked as having truncated, which means it's actually slightly
+  // higher, forcing a round up (3)
+  hpd.setTruncated(true);
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint32_t>(), uint32_t(3));
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(3));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(3));
+
+  // Check that the larger int types are being handled properly (overflow is not
+  // handled, so int types that are too small are ignored for this test.)
+
+  // 1099511627776 = 2^40
+  hpd = __llvm_libc::internal::HighPrecsisionDecimal("1099511627776", 13);
+
+  EXPECT_EQ(hpd.roundToIntegerType<uint64_t>(), uint64_t(1099511627776));
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), __uint128_t(1099511627776));
+
+  // 1267650600228229401496703205376 = 2^100
+  hpd = __llvm_libc::internal::HighPrecsisionDecimal(
+      "1267650600228229401496703205376", 31);
+
+  __uint128_t result = __uint128_t(1) << 100;
+
+  EXPECT_EQ(hpd.roundToIntegerType<__uint128_t>(), result);
+}