diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -12,12 +12,20 @@ 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 diff --git a/libc/src/__support/high_precision_decimal.h b/libc/src/__support/high_precision_decimal.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/high_precision_decimal.h @@ -0,0 +1,369 @@ +//===-- 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 + +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(this->digits[readIndex]); + ++readIndex; + } + + this->decimalPoint -= readIndex - 1; + + const uint64_t mask = + (uint64_t(1) << static_cast(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(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(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(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(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(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(shiftAmount) > MAX_SHIFT_AMOUNT) { + this->leftShift(MAX_SHIFT_AMOUNT); + shiftAmount -= MAX_SHIFT_AMOUNT; + } + this->leftShift(shiftAmount); + } + // Right + else { + while (static_cast(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 T roundToIntegerType() { + T result = 0; + uint32_t curDigit = 0; + + while (static_cast(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(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 diff --git a/libc/src/__support/str_conv_utils.h b/libc/src/__support/str_conv_utils.h --- a/libc/src/__support/str_conv_utils.h +++ b/libc/src/__support/str_conv_utils.h @@ -10,6 +10,7 @@ #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 #include diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -9,3 +9,13 @@ 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 +) diff --git a/libc/test/src/__support/high_precision_decimal_test.cpp b/libc/test/src/__support/high_precision_decimal_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/high_precision_decimal_test.cpp @@ -0,0 +1,369 @@ +//===-- 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(1)); + EXPECT_EQ(hpd.roundToIntegerType(), 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(2)); + EXPECT_EQ(hpd.roundToIntegerType(), 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(5)); + EXPECT_EQ(hpd.roundToIntegerType(), 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(2)); + EXPECT_EQ(hpd.roundToIntegerType(), 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(3)); + EXPECT_EQ(hpd.roundToIntegerType(), 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(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); +}