| //===-- 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 "src/__support/str_to_integer.h" |
| #include <stdint.h> |
| |
| namespace __llvm_libc { |
| namespace internal { |
| |
| struct LShiftTableEntry { |
| uint32_t newDigits; |
| char const *powerOfFive; |
| }; |
| |
| // 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 |
| class HighPrecisionDecimal { |
| |
| // This precomputed table speeds up left shifts by having the number of new |
| // digits that will be added by multiplying 5^i by 2^i. If the number is less |
| // than 5^i then it will add one fewer digit. There are only 60 entries since |
| // that's the max shift amount. |
| // This table was generated by the script at |
| // libc/utils/mathtools/GenerateHPDConstants.py |
| static constexpr LShiftTableEntry LEFT_SHIFT_DIGIT_TABLE[] = { |
| {0, ""}, |
| {1, "5"}, |
| {1, "25"}, |
| {1, "125"}, |
| {2, "625"}, |
| {2, "3125"}, |
| {2, "15625"}, |
| {3, "78125"}, |
| {3, "390625"}, |
| {3, "1953125"}, |
| {4, "9765625"}, |
| {4, "48828125"}, |
| {4, "244140625"}, |
| {4, "1220703125"}, |
| {5, "6103515625"}, |
| {5, "30517578125"}, |
| {5, "152587890625"}, |
| {6, "762939453125"}, |
| {6, "3814697265625"}, |
| {6, "19073486328125"}, |
| {7, "95367431640625"}, |
| {7, "476837158203125"}, |
| {7, "2384185791015625"}, |
| {7, "11920928955078125"}, |
| {8, "59604644775390625"}, |
| {8, "298023223876953125"}, |
| {8, "1490116119384765625"}, |
| {9, "7450580596923828125"}, |
| {9, "37252902984619140625"}, |
| {9, "186264514923095703125"}, |
| {10, "931322574615478515625"}, |
| {10, "4656612873077392578125"}, |
| {10, "23283064365386962890625"}, |
| {10, "116415321826934814453125"}, |
| {11, "582076609134674072265625"}, |
| {11, "2910383045673370361328125"}, |
| {11, "14551915228366851806640625"}, |
| {12, "72759576141834259033203125"}, |
| {12, "363797880709171295166015625"}, |
| {12, "1818989403545856475830078125"}, |
| {13, "9094947017729282379150390625"}, |
| {13, "45474735088646411895751953125"}, |
| {13, "227373675443232059478759765625"}, |
| {13, "1136868377216160297393798828125"}, |
| {14, "5684341886080801486968994140625"}, |
| {14, "28421709430404007434844970703125"}, |
| {14, "142108547152020037174224853515625"}, |
| {15, "710542735760100185871124267578125"}, |
| {15, "3552713678800500929355621337890625"}, |
| {15, "17763568394002504646778106689453125"}, |
| {16, "88817841970012523233890533447265625"}, |
| {16, "444089209850062616169452667236328125"}, |
| {16, "2220446049250313080847263336181640625"}, |
| {16, "11102230246251565404236316680908203125"}, |
| {17, "55511151231257827021181583404541015625"}, |
| {17, "277555756156289135105907917022705078125"}, |
| {17, "1387778780781445675529539585113525390625"}, |
| {18, "6938893903907228377647697925567626953125"}, |
| {18, "34694469519536141888238489627838134765625"}, |
| {18, "173472347597680709441192448139190673828125"}, |
| {19, "867361737988403547205962240695953369140625"}, |
| }; |
| |
| // The maximum amount we can shift is the number of bits used in the |
| // accumulator, minus the number of bits needed to represent the base (in this |
| // case 4). |
| static constexpr uint32_t MAX_SHIFT_AMOUNT = sizeof(uint64_t) - 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 we're right in the middle and there are no extra digits |
| if (this->digits[roundToDigit] == 5 && |
| roundToDigit + 1 == this->numDigits) { |
| |
| // Round up if we've truncated (since that means the result is slightly |
| // higher than what's represented.) |
| if (this->truncated) { |
| return true; |
| } |
| |
| // If this exactly halfway, round to even. |
| return this->digits[roundToDigit - 1] % 2 != 0; |
| } |
| // If there are digits after roundToDigit, they must be non-zero since we |
| // trim trailing zeroes after all operations that change digits. |
| return this->digits[roundToDigit] >= 5; |
| } |
| |
| // Takes an amount to left shift and returns the number of new digits needed |
| // to store the result based on LEFT_SHIFT_DIGIT_TABLE. |
| uint32_t getNumNewDigits(uint32_t lShiftAmount) { |
| const char *powerOfFive = LEFT_SHIFT_DIGIT_TABLE[lShiftAmount].powerOfFive; |
| uint32_t newDigits = LEFT_SHIFT_DIGIT_TABLE[lShiftAmount].newDigits; |
| uint32_t digitIndex = 0; |
| while (powerOfFive[digitIndex] != 0) { |
| if (digitIndex >= this->numDigits) { |
| return newDigits - 1; |
| } |
| if (this->digits[digitIndex] != powerOfFive[digitIndex] - '0') { |
| return newDigits - |
| ((this->digits[digitIndex] < powerOfFive[digitIndex] - '0') ? 1 |
| : 0); |
| } |
| ++digitIndex; |
| } |
| return newDigits; |
| } |
| |
| // Trim all trailing 0s |
| void trimTrailingZeroes() { |
| 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; |
| |
| const uint64_t shiftMask = (uint64_t(1) << shiftAmount) - 1; |
| |
| // Warm Up phase: we don't have enough digits to start writing, so just |
| // read them into the accumulator. |
| while (accumulator >> shiftAmount == 0) { |
| uint64_t readDigit = 0; |
| // If there are still digits to read, read the next one, else the digit is |
| // assumed to be 0. |
| if (readIndex < this->numDigits) { |
| readDigit = this->digits[readIndex]; |
| } |
| accumulator = accumulator * 10 + readDigit; |
| ++readIndex; |
| } |
| |
| // Shift the decimal point by the number of digits it took to fill the |
| // accumulator. |
| this->decimalPoint -= readIndex - 1; |
| |
| // Middle phase: we have enough digits to write, as well as more digits to |
| // read. Keep reading until we run out of digits. |
| while (readIndex < this->numDigits) { |
| uint64_t readDigit = this->digits[readIndex]; |
| uint64_t writeDigit = accumulator >> shiftAmount; |
| accumulator &= shiftMask; |
| this->digits[writeIndex] = static_cast<uint8_t>(writeDigit); |
| accumulator = accumulator * 10 + readDigit; |
| ++readIndex; |
| ++writeIndex; |
| } |
| |
| // Cool Down phase: All of the readable digits have been read, so just write |
| // the remainder, while treating any more digits as 0. |
| while (accumulator > 0) { |
| uint64_t writeDigit = accumulator >> shiftAmount; |
| accumulator &= shiftMask; |
| 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->trimTrailingZeroes(); |
| } |
| |
| // 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) { |
| uint32_t newDigits = this->getNumNewDigits(shiftAmount); |
| |
| int32_t readIndex = this->numDigits - 1; |
| uint32_t writeIndex = this->numDigits + newDigits; |
| |
| 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 nextAccumulator = accumulator / 10; |
| uint64_t writeDigit = accumulator - (10 * nextAccumulator); |
| --writeIndex; |
| if (writeIndex < MAX_NUM_DIGITS) { |
| this->digits[writeIndex] = static_cast<uint8_t>(writeDigit); |
| } else if (writeDigit != 0) { |
| this->truncated = true; |
| } |
| accumulator = nextAccumulator; |
| --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 nextAccumulator = accumulator / 10; |
| uint64_t writeDigit = accumulator - (10 * nextAccumulator); |
| --writeIndex; |
| if (writeIndex < MAX_NUM_DIGITS) { |
| this->digits[writeIndex] = static_cast<uint8_t>(writeDigit); |
| } else if (writeDigit != 0) { |
| this->truncated = true; |
| } |
| accumulator = nextAccumulator; |
| } |
| |
| this->numDigits += newDigits; |
| if (this->numDigits > MAX_NUM_DIGITS) { |
| this->numDigits = MAX_NUM_DIGITS; |
| } |
| this->decimalPoint += newDigits; |
| this->trimTrailingZeroes(); |
| } |
| |
| public: |
| // numString is assumed to be a string of numeric characters. It doesn't |
| // handle leading spaces. |
| HighPrecisionDecimal(const char *__restrict numString) { |
| bool sawDot = false; |
| while (isdigit(*numString) || *numString == '.') { |
| if (*numString == '.') { |
| if (sawDot) { |
| break; |
| } |
| this->decimalPoint = this->numDigits; |
| sawDot = true; |
| } else { |
| if (*numString == '0' && this->numDigits == 0) { |
| --this->decimalPoint; |
| ++numString; |
| continue; |
| } |
| if (this->numDigits < MAX_NUM_DIGITS) { |
| this->digits[this->numDigits] = *numString - '0'; |
| ++this->numDigits; |
| } else if (*numString != '0') { |
| this->truncated = true; |
| } |
| } |
| ++numString; |
| } |
| |
| if (!sawDot) { |
| this->decimalPoint = this->numDigits; |
| } |
| |
| if ((*numString | 32) == 'e') { |
| ++numString; |
| if (isdigit(*numString) || *numString == '+' || *numString == '-') { |
| int32_t addToExp = strtointeger<int32_t>(numString, nullptr, 10); |
| if (addToExp > 100000) { |
| addToExp = 100000; |
| } else if (addToExp < -100000) { |
| addToExp = -100000; |
| } |
| this->decimalPoint += addToExp; |
| } |
| } |
| |
| this->trimTrailingZeroes(); |
| } |
| |
| // 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 |
