ScaledNumber.cpp revision c6a4f5e819217e1e12c458aed8e7b122e23a3a58
1c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines//==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- C++ -*-===// 2c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 3c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// The LLVM Compiler Infrastructure 4c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 5c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// This file is distributed under the University of Illinois Open Source 6c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// License. See LICENSE.TXT for details. 7c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 8c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines//===----------------------------------------------------------------------===// 9c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 10c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// Implementation of some scaled number algorithms. 11c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 12c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines//===----------------------------------------------------------------------===// 13c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 14c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines#include "llvm/Support/ScaledNumber.h" 15c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 16c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines#include "llvm/ADT/APFloat.h" 17c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines#include "llvm/Support/Debug.h" 18c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 19c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesusing namespace llvm; 20c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesusing namespace llvm::ScaledNumbers; 21c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 22c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstd::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS, 23c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t RHS) { 24c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Separate into two 32-bit digits (U.L). 25c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines auto getU = [](uint64_t N) { return N >> 32; }; 26c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines auto getL = [](uint64_t N) { return N & UINT32_MAX; }; 27c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t UL = getU(LHS), LL = getL(LHS), UR = getU(RHS), LR = getL(RHS); 28c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 29c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Compute cross products. 30c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR; 31c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 32c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Sum into two 64-bit digits. 33c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Upper = P1, Lower = P4; 34c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines auto addWithCarry = [&](uint64_t N) { 35c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t NewLower = Lower + (getL(N) << 32); 36c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Upper += getU(N) + (NewLower < Lower); 37c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Lower = NewLower; 38c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines }; 39c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines addWithCarry(P2); 40c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines addWithCarry(P3); 41c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 42c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Check whether the upper digit is empty. 43c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!Upper) 44c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return std::make_pair(Lower, 0); 45c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 46c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Shift as little as possible to maximize precision. 47c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned LeadingZeros = countLeadingZeros(Upper); 48c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int Shift = 64 - LeadingZeros; 49c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (LeadingZeros) 50c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Upper = Upper << LeadingZeros | Lower >> Shift; 51c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return getRounded(Upper, Shift, 52c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Shift && (Lower & UINT64_C(1) << (Shift - 1))); 53c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 54c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 55c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); } 56c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 57c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstd::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend, 58c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint32_t Divisor) { 59c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Dividend && "expected non-zero dividend"); 60c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Divisor && "expected non-zero divisor"); 61c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 62c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Use 64-bit math and canonicalize the dividend to gain precision. 63c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Dividend64 = Dividend; 64c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int Shift = 0; 65c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (int Zeros = countLeadingZeros(Dividend64)) { 66c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Shift -= Zeros; 67c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Dividend64 <<= Zeros; 68c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 69c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Quotient = Dividend64 / Divisor; 70c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Remainder = Dividend64 % Divisor; 71c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 72c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // If Quotient needs to be shifted, leave the rounding to getAdjusted(). 73c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Quotient > UINT32_MAX) 74c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return getAdjusted<uint32_t>(Quotient, Shift); 75c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 76c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Round based on the value of the next bit. 77c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor)); 78c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 79c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 80c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstd::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend, 81c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Divisor) { 82c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Dividend && "expected non-zero dividend"); 83c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Divisor && "expected non-zero divisor"); 84c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 85c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Minimize size of divisor. 86c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int Shift = 0; 87c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (int Zeros = countTrailingZeros(Divisor)) { 88c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Shift -= Zeros; 89c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Divisor >>= Zeros; 90c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 91c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 92c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Check for powers of two. 93c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Divisor == 1) 94c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return std::make_pair(Dividend, Shift); 95c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 96c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Maximize size of dividend. 97c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (int Zeros = countLeadingZeros(Dividend)) { 98c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Shift -= Zeros; 99c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Dividend <<= Zeros; 100c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 101c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 102c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Start with the result of a divide. 103c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Quotient = Dividend / Divisor; 104c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Dividend %= Divisor; 105c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 106c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Continue building the quotient with long division. 107c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines while (!(Quotient >> 63) && Dividend) { 108c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Shift Dividend and check for overflow. 109c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines bool IsOverflow = Dividend >> 63; 110c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Dividend <<= 1; 111c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines --Shift; 112c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 113c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Get the next bit of Quotient. 114c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Quotient <<= 1; 115c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (IsOverflow || Divisor <= Dividend) { 116c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Quotient |= 1; 117c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Dividend -= Divisor; 118c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 119c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 120c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 121c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor)); 122c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 123c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 124c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesint ScaledNumbers::compareImpl(uint64_t L, uint64_t R, int ScaleDiff) { 125c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(ScaleDiff >= 0 && "wrong argument order"); 126c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(ScaleDiff < 64 && "numbers too far apart"); 127c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 128c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t L_adjusted = L >> ScaleDiff; 129c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (L_adjusted < R) 130c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return -1; 131c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (L_adjusted > R) 132c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return 1; 133c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 134c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return L > L_adjusted << ScaleDiff ? 1 : 0; 135c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 136c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 137c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic void appendDigit(std::string &Str, unsigned D) { 138c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(D < 10); 139c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Str += '0' + D % 10; 140c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 141c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 142c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic void appendNumber(std::string &Str, uint64_t N) { 143c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines while (N) { 144c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines appendDigit(Str, N % 10); 145c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines N /= 10; 146c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 147c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 148c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 149c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic bool doesRoundUp(char Digit) { 150c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines switch (Digit) { 151c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines case '5': 152c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines case '6': 153c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines case '7': 154c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines case '8': 155c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines case '9': 156c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return true; 157c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines default: 158c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return false; 159c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 160c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 161c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 162c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic std::string toStringAPFloat(uint64_t D, int E, unsigned Precision) { 163c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(E >= ScaledNumbers::MinScale); 164c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(E <= ScaledNumbers::MaxScale); 165c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 166c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Find a new E, but don't let it increase past MaxScale. 167c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int LeadingZeros = ScaledNumberBase::countLeadingZeros64(D); 168c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int NewE = std::min(ScaledNumbers::MaxScale, E + 63 - LeadingZeros); 169c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int Shift = 63 - (NewE - E); 170c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Shift <= LeadingZeros); 171c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(Shift == LeadingZeros || NewE == ScaledNumbers::MaxScale); 172c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines D <<= Shift; 173c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines E = NewE; 174c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 175c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Check for a denormal. 176c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned AdjustedE = E + 16383; 177c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!(D >> 63)) { 178c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(E == ScaledNumbers::MaxScale); 179c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines AdjustedE = 0; 180c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 181c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 182c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Build the float and print it. 183c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t RawBits[2] = {D, AdjustedE}; 184c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines APFloat Float(APFloat::x87DoubleExtended, APInt(80, RawBits)); 185c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines SmallVector<char, 24> Chars; 186c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Float.toString(Chars, Precision, 0); 187c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return std::string(Chars.begin(), Chars.end()); 188c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 189c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 190c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic std::string stripTrailingZeros(const std::string &Float) { 191c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines size_t NonZero = Float.find_last_not_of('0'); 192c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(NonZero != std::string::npos && "no . in floating point string"); 193c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 194c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Float[NonZero] == '.') 195c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ++NonZero; 196c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 197c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return Float.substr(0, NonZero + 1); 198c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 199c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 200c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstd::string ScaledNumberBase::toString(uint64_t D, int16_t E, int Width, 201c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned Precision) { 202c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!D) 203c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return "0.0"; 204c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 205c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Canonicalize exponent and digits. 206c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Above0 = 0; 207c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Below0 = 0; 208c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Extra = 0; 209c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int ExtraShift = 0; 210c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (E == 0) { 211c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Above0 = D; 212c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } else if (E > 0) { 213c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (int Shift = std::min(int16_t(countLeadingZeros64(D)), E)) { 214c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines D <<= Shift; 215c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines E -= Shift; 216c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 217c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!E) 218c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Above0 = D; 219c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 220c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } else if (E > -64) { 221c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Above0 = D >> -E; 222c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 = D << (64 + E); 223c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } else if (E > -120) { 224c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 = D >> (-E - 64); 225c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Extra = D << (128 + E); 226c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ExtraShift = -64 - E; 227c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 228c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 229c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Fall back on APFloat for very small and very large numbers. 230c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!Above0 && !Below0) 231c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return toStringAPFloat(D, E, Precision); 232c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 233c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Append the digits before the decimal. 234c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines std::string Str; 235c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines size_t DigitsOut = 0; 236c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Above0) { 237c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines appendNumber(Str, Above0); 238c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines DigitsOut = Str.size(); 239c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } else 240c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines appendDigit(Str, 0); 241c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines std::reverse(Str.begin(), Str.end()); 242c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 243c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Return early if there's nothing after the decimal. 244c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!Below0) 245c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return Str + ".0"; 246c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 247c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Append the decimal and beyond. 248c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Str += '.'; 249c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines uint64_t Error = UINT64_C(1) << (64 - Width); 250c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 251c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // We need to shift Below0 to the right to make space for calculating 252c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // digits. Save the precision we're losing in Extra. 253c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Extra = (Below0 & 0xf) << 56 | (Extra >> 8); 254c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 >>= 4; 255c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines size_t SinceDot = 0; 256c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines size_t AfterDot = Str.size(); 257c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines do { 258c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (ExtraShift) { 259c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines --ExtraShift; 260c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Error *= 5; 261c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } else 262c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Error *= 10; 263c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 264c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 *= 10; 265c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Extra *= 10; 266c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 += (Extra >> 60); 267c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Extra = Extra & (UINT64_MAX >> 4); 268c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines appendDigit(Str, Below0 >> 60); 269c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Below0 = Below0 & (UINT64_MAX >> 4); 270c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (DigitsOut || Str.back() != '0') 271c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ++DigitsOut; 272c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ++SinceDot; 273c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } while (Error && (Below0 << 4 | Extra >> 60) >= Error / 2 && 274c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines (!Precision || DigitsOut <= Precision || SinceDot < 2)); 275c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 276c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Return early for maximum precision. 277c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!Precision || DigitsOut <= Precision) 278c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return stripTrailingZeros(Str); 279c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 280c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Find where to truncate. 281c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines size_t Truncate = 282c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines std::max(Str.size() - (DigitsOut - Precision), AfterDot + 1); 283c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 284c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Check if there's anything to truncate. 285c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Truncate >= Str.size()) 286c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return stripTrailingZeros(Str); 287c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 288c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines bool Carry = doesRoundUp(Str[Truncate]); 289c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!Carry) 290c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return stripTrailingZeros(Str.substr(0, Truncate)); 291c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 292c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Round with the first truncated digit. 293c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (std::string::reverse_iterator I(Str.begin() + Truncate), E = Str.rend(); 294c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines I != E; ++I) { 295c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (*I == '.') 296c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines continue; 297c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (*I == '9') { 298c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines *I = '0'; 299c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines continue; 300c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 301c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 302c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines ++*I; 303c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Carry = false; 304c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines break; 305c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 306c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 307c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Add "1" in front if we still need to carry. 308c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return stripTrailingZeros(std::string(Carry, '1') + Str.substr(0, Truncate)); 309c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 310c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 311c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesraw_ostream &ScaledNumberBase::print(raw_ostream &OS, uint64_t D, int16_t E, 312c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines int Width, unsigned Precision) { 313c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return OS << toString(D, E, Width, Precision); 314c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 315c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 316c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesvoid ScaledNumberBase::dump(uint64_t D, int16_t E, int Width) { 317c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines print(dbgs(), D, E, Width, 0) << "[" << Width << ":" << D << "*2^" << E 318c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines << "]"; 319c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 320