X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=267aaf81d449bf8dd0cb186a3ed0eaf66d442547;hb=ba6801e6e72a9f4de1e116ea81b370456eb7ecd3;hp=acc9de295b40bd5864a75c4d1d3bf4ffa8b0a644;hpb=66ed1099ff3591c61e008198bb5a30862e778fc0;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index acc9de295b4..267aaf81d44 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -17,6 +17,8 @@ #include "llvm/DerivedTypes.h" #include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" +#include +#include #include #include #ifndef NDEBUG @@ -42,7 +44,7 @@ inline static uint64_t* getMemory(uint32_t numWords) { return result; } -APInt::APInt(uint32_t numBits, uint64_t val) +APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned) : BitWidth(numBits), VAL(0) { assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small"); assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); @@ -51,6 +53,9 @@ APInt::APInt(uint32_t numBits, uint64_t val) else { pVal = getClearedMemory(getNumWords()); pVal[0] = val; + if (isSigned && int64_t(val) < 0) + for (unsigned i = 1; i < getNumWords(); ++i) + pVal[i] = -1ULL; } clearUnusedBits(); } @@ -77,17 +82,23 @@ APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]) APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen, uint8_t radix) : BitWidth(numbits), VAL(0) { + assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small"); + assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); fromString(numbits, StrStart, slen, radix); } APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix) : BitWidth(numbits), VAL(0) { + assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small"); + assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); assert(!Val.empty() && "String empty?"); fromString(numbits, Val.c_str(), Val.size(), radix); } APInt::APInt(const APInt& that) : BitWidth(that.BitWidth), VAL(0) { + assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small"); + assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); if (isSingleWord()) VAL = that.VAL; else { @@ -600,7 +611,7 @@ APInt& APInt::set() { } // Set all the bits in all the words. - for (uint32_t i = 0; i < getNumWords() - 1; ++i) + for (uint32_t i = 0; i < getNumWords(); ++i) pVal[i] = -1ULL; // Clear the unused ones return clearUnusedBits(); @@ -654,6 +665,43 @@ APInt& APInt::flip(uint32_t bitPosition) { return *this; } +uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) { + assert(str != 0 && "Invalid value string"); + assert(slen > 0 && "Invalid string length"); + + // Each computation below needs to know if its negative + uint32_t isNegative = str[0] == '-'; + if (isNegative) { + slen--; + str++; + } + // For radixes of power-of-two values, the bits required is accurately and + // easily computed + if (radix == 2) + return slen + isNegative; + if (radix == 8) + return slen * 3 + isNegative; + if (radix == 16) + return slen * 4 + isNegative; + + // Otherwise it must be radix == 10, the hard case + assert(radix == 10 && "Invalid radix"); + + // This is grossly inefficient but accurate. We could probably do something + // with a computation of roughly slen*64/20 and then adjust by the value of + // the first few digits. But, I'm not sure how accurate that could be. + + // Compute a sufficient number of bits that is always large enough but might + // be too large. This avoids the assertion in the constructor. + uint32_t sufficient = slen*64/18; + + // Convert to the actual binary value. + APInt tmp(sufficient, str, slen, radix); + + // Compute how many bits are required. + return isNegative + tmp.logBase2() + 1; +} + uint64_t APInt::getHashValue() const { // Put the bit width into the low order bits. uint64_t hash = BitWidth; @@ -702,6 +750,38 @@ uint32_t APInt::countLeadingZeros() const { return Count; } +static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) { + uint32_t Count = 0; + if (skip) + V <<= skip; + while (V && (V & (1ULL << 63))) { + Count++; + V <<= 1; + } + return Count; +} + +uint32_t APInt::countLeadingOnes() const { + if (isSingleWord()) + return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth); + + uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD; + uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits); + int i = getNumWords() - 1; + uint32_t Count = countLeadingOnes_64(pVal[i], shift); + if (Count == highWordBits) { + for (i--; i >= 0; --i) { + if (pVal[i] == -1ULL) + Count += APINT_BITS_PER_WORD; + else { + Count += countLeadingOnes_64(pVal[i], 0); + break; + } + } + } + return Count; +} + uint32_t APInt::countTrailingZeros() const { if (isSingleWord()) return CountTrailingZeros_64(VAL); @@ -726,17 +806,15 @@ uint32_t APInt::countPopulation() const { APInt APInt::byteSwap() const { assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); if (BitWidth == 16) - return APInt(BitWidth, ByteSwap_16(VAL)); + return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); else if (BitWidth == 32) - return APInt(BitWidth, ByteSwap_32(VAL)); + return APInt(BitWidth, ByteSwap_32(uint32_t(VAL))); else if (BitWidth == 48) { - uint64_t Tmp1 = ((VAL >> 32) << 16) | (VAL & 0xFFFF); + uint32_t Tmp1 = uint32_t(VAL >> 16); Tmp1 = ByteSwap_32(Tmp1); - uint64_t Tmp2 = (VAL >> 16) & 0xFFFF; + uint16_t Tmp2 = uint16_t(VAL); Tmp2 = ByteSwap_16(Tmp2); - return - APInt(BitWidth, - (Tmp1 & 0xff) | ((Tmp1<<16) & 0xffff00000000ULL) | (Tmp2 << 16)); + return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); } else if (BitWidth == 64) return APInt(BitWidth, ByteSwap_64(VAL)); else { @@ -777,7 +855,7 @@ APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) { // If the exponent is negative, the value is < 0 so just return 0. if (exp < 0) - return APInt(64u, 0u); + return APInt(width, 0u); // Extract the mantissa by clearing the top 12 bits (sign + exponent). uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; @@ -833,9 +911,9 @@ double APInt::roundToDouble(bool isSigned) const { // Return infinity for exponent overflow if (exp > 1023) { if (!isSigned || !isNeg) - return double(1.0E300 * 1.0E300); // positive infinity + return std::numeric_limits::infinity(); else - return double(-1.0E300 * 1.0E300); // negative infinity + return -std::numeric_limits::infinity(); } exp += 1023; // Increment for 1023 bias @@ -865,7 +943,7 @@ double APInt::roundToDouble(bool isSigned) const { } // Truncate to new width. -void APInt::trunc(uint32_t width) { +APInt &APInt::trunc(uint32_t width) { assert(width < BitWidth && "Invalid APInt Truncate request"); assert(width >= IntegerType::MIN_INT_BITS && "Can't truncate to 0 bits"); uint32_t wordsBefore = getNumWords(); @@ -884,17 +962,17 @@ void APInt::trunc(uint32_t width) { pVal = newVal; } } - clearUnusedBits(); + return clearUnusedBits(); } // Sign extend to a new width. -void APInt::sext(uint32_t width) { +APInt &APInt::sext(uint32_t width) { assert(width > BitWidth && "Invalid APInt SignExtend request"); assert(width <= IntegerType::MAX_INT_BITS && "Too many bits"); // If the sign bit isn't set, this is the same as zext. if (!isNegative()) { zext(width); - return; + return *this; } // The sign bit is set. First, get some facts @@ -907,13 +985,15 @@ void APInt::sext(uint32_t width) { if (wordsBefore == wordsAfter) { uint32_t newWordBits = width % APINT_BITS_PER_WORD; // The extension is contained to the wordsBefore-1th word. - uint64_t mask = (~0ULL >> (APINT_BITS_PER_WORD - newWordBits)) << wordBits; + uint64_t mask = ~0ULL; + if (newWordBits) + mask >>= APINT_BITS_PER_WORD - newWordBits; + mask <<= wordBits; if (wordsBefore == 1) VAL |= mask; else pVal[wordsBefore-1] |= mask; - clearUnusedBits(); - return; + return clearUnusedBits(); } uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits; @@ -930,11 +1010,11 @@ void APInt::sext(uint32_t width) { if (wordsBefore != 1) delete [] pVal; pVal = newVal; - clearUnusedBits(); + return clearUnusedBits(); } // Zero extend to a new width. -void APInt::zext(uint32_t width) { +APInt &APInt::zext(uint32_t width) { assert(width > BitWidth && "Invalid APInt ZeroExtend request"); assert(width <= IntegerType::MAX_INT_BITS && "Too many bits"); uint32_t wordsBefore = getNumWords(); @@ -951,12 +1031,34 @@ void APInt::zext(uint32_t width) { delete [] pVal; pVal = newVal; } + return *this; +} + +APInt &APInt::zextOrTrunc(uint32_t width) { + if (BitWidth < width) + return zext(width); + if (BitWidth > width) + return trunc(width); + return *this; +} + +APInt &APInt::sextOrTrunc(uint32_t width) { + if (BitWidth < width) + return sext(width); + if (BitWidth > width) + return trunc(width); + return *this; } /// Arithmetic right-shift this APInt by shiftAmt. /// @brief Arithmetic right-shift function. APInt APInt::ashr(uint32_t shiftAmt) const { assert(shiftAmt <= BitWidth && "Invalid shift amount"); + // Handle a degenerate case + if (shiftAmt == 0) + return *this; + + // Handle single word shifts with built-in ashr if (isSingleWord()) { if (shiftAmt == BitWidth) return APInt(BitWidth, 0); // undefined @@ -967,65 +1069,79 @@ APInt APInt::ashr(uint32_t shiftAmt) const { } } - // If all the bits were shifted out, the result is 0 or -1. This avoids issues - // with shifting by the size of the integer type, which produces undefined - // results. - if (shiftAmt == BitWidth) + // If all the bits were shifted out, the result is, technically, undefined. + // We return -1 if it was negative, 0 otherwise. We check this early to avoid + // issues in the algorithm below. + if (shiftAmt == BitWidth) { if (isNegative()) return APInt(BitWidth, -1ULL); else return APInt(BitWidth, 0); + } // Create some space for the result. uint64_t * val = new uint64_t[getNumWords()]; - // If we are shifting less than a word, compute the shift with a simple carry - if (shiftAmt < APINT_BITS_PER_WORD) { - uint64_t carry = 0; - for (int i = getNumWords()-1; i >= 0; --i) { - val[i] = pVal[i] >> shiftAmt | carry; - carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); - } - return APInt(val, BitWidth).clearUnusedBits(); - } - - // Compute some values needed by the remaining shift algorithms - uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; - uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; + // Compute some values needed by the following shift algorithms + uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word + uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift + uint32_t breakWord = getNumWords() - 1 - offset; // last word affected + uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word? + if (bitsInWord == 0) + bitsInWord = APINT_BITS_PER_WORD; // If we are shifting whole words, just move whole words if (wordShift == 0) { - for (uint32_t i = 0; i < getNumWords() - offset; ++i) - val[i] = pVal[i+offset]; - for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++) - val[i] = (isNegative() ? -1ULL : 0); - return APInt(val,BitWidth).clearUnusedBits(); - } + // Move the words containing significant bits + for (uint32_t i = 0; i <= breakWord; ++i) + val[i] = pVal[i+offset]; // move whole word - // Shift the low order words - uint32_t breakWord = getNumWords() - offset -1; - for (uint32_t i = 0; i < breakWord; ++i) - val[i] = pVal[i+offset] >> wordShift | - pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift); - // Shift the break word. - uint32_t SignBit = APINT_BITS_PER_WORD - (BitWidth % APINT_BITS_PER_WORD); - val[breakWord] = uint64_t( - (((int64_t(pVal[breakWord+offset]) << SignBit) >> SignBit) >> wordShift)); + // Adjust the top significant word for sign bit fill, if negative + if (isNegative()) + if (bitsInWord < APINT_BITS_PER_WORD) + val[breakWord] |= ~0ULL << bitsInWord; // set high bits + } else { + // Shift the low order words + for (uint32_t i = 0; i < breakWord; ++i) { + // This combines the shifted corresponding word with the low bits from + // the next word (shifted into this word's high bits). + val[i] = (pVal[i+offset] >> wordShift) | + (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); + } + + // Shift the break word. In this case there are no bits from the next word + // to include in this word. + val[breakWord] = pVal[breakWord+offset] >> wordShift; + + // Deal with sign extenstion in the break word, and possibly the word before + // it. + if (isNegative()) { + if (wordShift > bitsInWord) { + if (breakWord > 0) + val[breakWord-1] |= + ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); + val[breakWord] |= ~0ULL; + } else + val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); + } + } - // Remaining words are 0 or -1 + // Remaining words are 0 or -1, just assign them. + uint64_t fillValue = (isNegative() ? -1ULL : 0); for (uint32_t i = breakWord+1; i < getNumWords(); ++i) - val[i] = (isNegative() ? -1ULL : 0); + val[i] = fillValue; return APInt(val, BitWidth).clearUnusedBits(); } /// Logical right-shift this APInt by shiftAmt. /// @brief Logical right-shift function. APInt APInt::lshr(uint32_t shiftAmt) const { - if (isSingleWord()) + if (isSingleWord()) { if (shiftAmt == BitWidth) return APInt(BitWidth, 0); else return APInt(BitWidth, this->VAL >> shiftAmt); + } // If all the bits were shifted out, the result is 0. This avoids issues // with shifting by the size of the integer type, which produces undefined @@ -1033,6 +1149,12 @@ APInt APInt::lshr(uint32_t shiftAmt) const { if (shiftAmt == BitWidth) return APInt(BitWidth, 0); + // If none of the bits are shifted out, the result is *this. This avoids + // issues with shifting byt he size of the integer type, which produces + // undefined results in the code below. This is also an optimization. + if (shiftAmt == 0) + return *this; + // Create some space for the result. uint64_t * val = new uint64_t[getNumWords()]; @@ -1040,7 +1162,7 @@ APInt APInt::lshr(uint32_t shiftAmt) const { if (shiftAmt < APINT_BITS_PER_WORD) { uint64_t carry = 0; for (int i = getNumWords()-1; i >= 0; --i) { - val[i] = pVal[i] >> shiftAmt | carry; + val[i] = (pVal[i] >> shiftAmt) | carry; carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); } return APInt(val, BitWidth).clearUnusedBits(); @@ -1062,8 +1184,8 @@ APInt APInt::lshr(uint32_t shiftAmt) const { // Shift the low order words uint32_t breakWord = getNumWords() - offset -1; for (uint32_t i = 0; i < breakWord; ++i) - val[i] = pVal[i+offset] >> wordShift | - pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift); + val[i] = (pVal[i+offset] >> wordShift) | + (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); // Shift the break word. val[breakWord] = pVal[breakWord+offset] >> wordShift; @@ -1089,6 +1211,12 @@ APInt APInt::shl(uint32_t shiftAmt) const { if (shiftAmt == BitWidth) return APInt(BitWidth, 0); + // If none of the bits are shifted out, the result is *this. This avoids a + // lshr by the words size in the loop below which can produce incorrect + // results. It also avoids the expensive computation below for a common case. + if (shiftAmt == 0) + return *this; + // Create some space for the result. uint64_t * val = new uint64_t[getNumWords()]; @@ -1126,6 +1254,118 @@ APInt APInt::shl(uint32_t shiftAmt) const { return APInt(val, BitWidth).clearUnusedBits(); } +APInt APInt::rotl(uint32_t rotateAmt) const { + if (rotateAmt == 0) + return *this; + // Don't get too fancy, just use existing shift/or facilities + APInt hi(*this); + APInt lo(*this); + hi.shl(rotateAmt); + lo.lshr(BitWidth - rotateAmt); + return hi | lo; +} + +APInt APInt::rotr(uint32_t rotateAmt) const { + if (rotateAmt == 0) + return *this; + // Don't get too fancy, just use existing shift/or facilities + APInt hi(*this); + APInt lo(*this); + lo.lshr(rotateAmt); + hi.shl(BitWidth - rotateAmt); + return hi | lo; +} + +// Square Root - this method computes and returns the square root of "this". +// Three mechanisms are used for computation. For small values (<= 5 bits), +// a table lookup is done. This gets some performance for common cases. For +// values using less than 52 bits, the value is converted to double and then +// the libc sqrt function is called. The result is rounded and then converted +// back to a uint64_t which is then used to construct the result. Finally, +// the Babylonian method for computing square roots is used. +APInt APInt::sqrt() const { + + // Determine the magnitude of the value. + uint32_t magnitude = getActiveBits(); + + // Use a fast table for some small values. This also gets rid of some + // rounding errors in libc sqrt for small values. + if (magnitude <= 5) { + static const uint8_t results[32] = { + /* 0 */ 0, + /* 1- 2 */ 1, 1, + /* 3- 6 */ 2, 2, 2, 2, + /* 7-12 */ 3, 3, 3, 3, 3, 3, + /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, + /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + /* 31 */ 6 + }; + return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); + } + + // If the magnitude of the value fits in less than 52 bits (the precision of + // an IEEE double precision floating point value), then we can use the + // libc sqrt function which will probably use a hardware sqrt computation. + // This should be faster than the algorithm below. + if (magnitude < 52) { +#ifdef _MSC_VER + // Amazingly, VC++ doesn't have round(). + return APInt(BitWidth, + uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5); +#else + return APInt(BitWidth, + uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); +#endif + } + + // Okay, all the short cuts are exhausted. We must compute it. The following + // is a classical Babylonian method for computing the square root. This code + // was adapted to APINt from a wikipedia article on such computations. + // See http://www.wikipedia.org/ and go to the page named + // Calculate_an_integer_square_root. + uint32_t nbits = BitWidth, i = 4; + APInt testy(BitWidth, 16); + APInt x_old(BitWidth, 1); + APInt x_new(BitWidth, 0); + APInt two(BitWidth, 2); + + // Select a good starting value using binary logarithms. + for (;; i += 2, testy = testy.shl(2)) + if (i >= nbits || this->ule(testy)) { + x_old = x_old.shl(i / 2); + break; + } + + // Use the Babylonian method to arrive at the integer square root: + for (;;) { + x_new = (this->udiv(x_old) + x_old).udiv(two); + if (x_old.ule(x_new)) + break; + x_old = x_new; + } + + // Make sure we return the closest approximation + // NOTE: The rounding calculation below is correct. It will produce an + // off-by-one discrepancy with results from pari/gp. That discrepancy has been + // determined to be a rounding issue with pari/gp as it begins to use a + // floating point representation after 192 bits. There are no discrepancies + // between this algorithm and pari/gp for bit widths < 192 bits. + APInt square(x_old * x_old); + APInt nextSquare((x_old + 1) * (x_old +1)); + if (this->ult(square)) + return x_old; + else if (this->ule(nextSquare)) { + APInt midpoint((nextSquare - square).udiv(two)); + APInt offset(*this - square); + if (offset.ult(midpoint)) + return x_old; + else + return x_old + 1; + } else + assert(0 && "Error in APInt::sqrt computation"); + return x_old + 1; +} + /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The /// variables here have the same names as in the algorithm. Comments explain @@ -1547,12 +1787,55 @@ APInt APInt::urem(const APInt& RHS) const { return APInt(BitWidth, pVal[0] % RHS.pVal[0]); } - // We have to compute it the hard way. Invoke the Knute divide algorithm. + // We have to compute it the hard way. Invoke the Knuth divide algorithm. APInt Remainder(1,0); divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); return Remainder; } +void APInt::udivrem(const APInt &LHS, const APInt &RHS, + APInt &Quotient, APInt &Remainder) { + // Get some size facts about the dividend and divisor + uint32_t lhsBits = LHS.getActiveBits(); + uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); + uint32_t rhsBits = RHS.getActiveBits(); + uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); + + // Check the degenerate cases + if (lhsWords == 0) { + Quotient = 0; // 0 / Y ===> 0 + Remainder = 0; // 0 % Y ===> 0 + return; + } + + if (lhsWords < rhsWords || LHS.ult(RHS)) { + Quotient = 0; // X / Y ===> 0, iff X < Y + Remainder = LHS; // X % Y ===> X, iff X < Y + return; + } + + if (LHS == RHS) { + Quotient = 1; // X / X ===> 1 + Remainder = 0; // X % X ===> 0; + return; + } + + if (lhsWords == 1 && rhsWords == 1) { + // There is only one word to consider so use the native versions. + if (LHS.isSingleWord()) { + Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL); + Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL); + } else { + Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]); + Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]); + } + return; + } + + // Okay, lets do it the long way + divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); +} + void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, uint8_t radix) { // Check our assumptions here @@ -1562,10 +1845,10 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, bool isNeg = str[0] == '-'; if (isNeg) str++, slen--; - assert(slen <= numbits || radix != 2 && "Insufficient bit width"); - assert(slen*3 <= numbits || radix != 8 && "Insufficient bit width"); - assert(slen*4 <= numbits || radix != 16 && "Insufficient bit width"); - assert((slen*64)/20 <= numbits || radix != 10 && "Insufficient bit width"); + assert((slen <= numbits || radix != 2) && "Insufficient bit width"); + assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width"); + assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width"); + assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width"); // Allocate memory if (!isSingleWord()) @@ -1584,21 +1867,26 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, // Get a digit uint32_t digit = 0; char cdigit = str[i]; - if (isdigit(cdigit)) - digit = cdigit - '0'; - else if (isxdigit(cdigit)) - if (cdigit >= 'a') + if (radix == 16) { + if (!isxdigit(cdigit)) + assert(0 && "Invalid hex digit in string"); + if (isdigit(cdigit)) + digit = cdigit - '0'; + else if (cdigit >= 'a') digit = cdigit - 'a' + 10; else if (cdigit >= 'A') digit = cdigit - 'A' + 10; else - assert(0 && "huh?"); - else + assert(0 && "huh? we shouldn't get here"); + } else if (isdigit(cdigit)) { + digit = cdigit - '0'; + } else { assert(0 && "Invalid character in digit string"); + } - // Shift or multiple the value by the radix + // Shift or multiply the value by the radix if (shift) - this->shl(shift); + *this <<= shift; else *this *= apradix; @@ -1650,14 +1938,33 @@ std::string APInt::toString(uint8_t radix, bool wantSigned) const { } if (radix != 10) { - uint64_t mask = radix - 1; - uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : 1); - uint32_t nibbles = APINT_BITS_PER_WORD / shift; - for (uint32_t i = 0; i < getNumWords(); ++i) { - uint64_t value = pVal[i]; - for (uint32_t j = 0; j < nibbles; ++j) { - result.insert(0, digits[ value & mask ]); - value >>= shift; + // For the 2, 8 and 16 bit cases, we can just shift instead of divide + // because the number of bits per digit (1,3 and 4 respectively) divides + // equaly. We just shift until there value is zero. + + // First, check for a zero value and just short circuit the logic below. + if (*this == 0) + result = "0"; + else { + APInt tmp(*this); + size_t insert_at = 0; + if (wantSigned && this->isNegative()) { + // They want to print the signed version and it is a negative value + // Flip the bits and add one to turn it into the equivalent positive + // value and put a '-' in the result. + tmp.flip(); + tmp++; + result = "-"; + insert_at = 1; + } + // Just shift tmp right for each digit width until it becomes zero + uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1)); + uint64_t mask = radix - 1; + APInt zero(tmp.getBitWidth(), 0); + while (tmp.ne(zero)) { + unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask; + result.insert(insert_at, digits[digit]); + tmp = tmp.lshr(shift); } } return result; @@ -1701,6 +2008,7 @@ void APInt::dump() const else for (unsigned i = getNumWords(); i > 0; i--) { cerr << pVal[i-1] << " "; } - cerr << " (" << this->toString(10) << ")\n" << std::setbase(10); + cerr << " U(" << this->toString(10) << ") S(" << this->toStringSigned(10) + << ")\n" << std::setbase(10); } #endif