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