X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=3d38a0c6066617683e78b28cd55613f534d4b5ea;hb=0001e56f15215ae4bc5fffb82eec5c4828b888f0;hp=0bfc95bde3f746c31e53a36b30e94904b4171125;hpb=09dfd8e19dc4bb0e53966a0531880d42182a1f9f;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 0bfc95bde3f..3d38a0c6066 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Sheng Zhou and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -14,22 +14,20 @@ #define DEBUG_TYPE "apint" #include "llvm/ADT/APInt.h" -#include "llvm/DerivedTypes.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/SmallString.h" #include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" -#include +#include "llvm/Support/raw_ostream.h" +#include #include #include #include -#ifndef NDEBUG -#include -#endif - using namespace llvm; /// A utility function for allocating memory, checking for allocation failures, /// and ensuring the contents are zeroed. -inline static uint64_t* getClearedMemory(uint32_t numWords) { +inline static uint64_t* getClearedMemory(unsigned numWords) { uint64_t * result = new uint64_t[numWords]; assert(result && "APInt memory allocation fails!"); memset(result, 0, numWords * sizeof(uint64_t)); @@ -38,32 +36,29 @@ inline static uint64_t* getClearedMemory(uint32_t numWords) { /// A utility function for allocating memory and checking for allocation /// failure. The content is not zeroed. -inline static uint64_t* getMemory(uint32_t numWords) { +inline static uint64_t* getMemory(unsigned numWords) { uint64_t * result = new uint64_t[numWords]; assert(result && "APInt memory allocation fails!"); return result; } -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"); - if (isSingleWord()) - VAL = 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(); +void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) { + pVal = getClearedMemory(getNumWords()); + pVal[0] = val; + if (isSigned && int64_t(val) < 0) + for (unsigned i = 1; i < getNumWords(); ++i) + pVal[i] = -1ULL; +} + +void APInt::initSlowCase(const APInt& that) { + pVal = getMemory(getNumWords()); + memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); } -APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]) - : BitWidth(numBits), VAL(0) { - assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small"); - assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); + +APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) + : BitWidth(numBits), VAL(0) { + assert(BitWidth && "bitwidth too small"); assert(bigVal && "Null pointer detected!"); if (isSingleWord()) VAL = bigVal[0]; @@ -71,7 +66,7 @@ APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]) // Get memory, cleared to 0 pVal = getClearedMemory(getNumWords()); // Calculate the number of words to copy - uint32_t words = std::min(numWords, getNumWords()); + unsigned words = std::min(numWords, getNumWords()); // Copy the words from bigVal to pVal memcpy(pVal, bigVal, words * APINT_WORD_SIZE); } @@ -79,56 +74,32 @@ APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]) clearUnusedBits(); } -APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen, +APInt::APInt(unsigned numbits, const char StrStart[], unsigned slen, uint8_t radix) : BitWidth(numbits), VAL(0) { + assert(BitWidth && "bitwidth too small"); fromString(numbits, StrStart, slen, radix); } -APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix) - : BitWidth(numbits), VAL(0) { - assert(!Val.empty() && "String empty?"); - fromString(numbits, Val.c_str(), Val.size(), radix); -} - -APInt::APInt(const APInt& that) - : BitWidth(that.BitWidth), VAL(0) { - if (isSingleWord()) - VAL = that.VAL; - else { - pVal = getMemory(getNumWords()); - memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); - } -} - -APInt::~APInt() { - if (!isSingleWord() && pVal) - delete [] pVal; -} - -APInt& APInt::operator=(const APInt& RHS) { +APInt& APInt::AssignSlowCase(const APInt& RHS) { // Don't do anything for X = X if (this == &RHS) return *this; - // If the bitwidths are the same, we can avoid mucking with memory if (BitWidth == RHS.getBitWidth()) { - if (isSingleWord()) - VAL = RHS.VAL; - else - memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); + // assume same bit-width single-word case is already handled + assert(!isSingleWord()); + memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); return *this; } - if (isSingleWord()) - if (RHS.isSingleWord()) - VAL = RHS.VAL; - else { - VAL = 0; - pVal = getMemory(RHS.getNumWords()); - memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); - } - else if (getNumWords() == RHS.getNumWords()) + if (isSingleWord()) { + // assume case where both are single words is already handled + assert(!RHS.isSingleWord()); + VAL = 0; + pVal = getMemory(RHS.getNumWords()); + memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); + } else if (getNumWords() == RHS.getNumWords()) memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); else if (RHS.isSingleWord()) { delete [] pVal; @@ -152,12 +123,26 @@ APInt& APInt::operator=(uint64_t RHS) { return clearUnusedBits(); } +/// Profile - This method 'profiles' an APInt for use with FoldingSet. +void APInt::Profile(FoldingSetNodeID& ID) const { + ID.AddInteger(BitWidth); + + if (isSingleWord()) { + ID.AddInteger(VAL); + return; + } + + unsigned NumWords = getNumWords(); + for (unsigned i = 0; i < NumWords; ++i) + ID.AddInteger(pVal[i]); +} + /// add_1 - This function adds a single "digit" integer, y, to the multiple /// "digit" integer array, x[]. x[] is modified to reflect the addition and /// 1 is returned if there is a carry out, otherwise 0 is returned. /// @returns the carry of the addition. -static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { - for (uint32_t i = 0; i < len; ++i) { +static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { + for (unsigned i = 0; i < len; ++i) { dest[i] = y + x[i]; if (dest[i] < y) y = 1; // Carry one to next digit. @@ -184,8 +169,8 @@ APInt& APInt::operator++() { /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. /// In other words, if y > x then this function returns 1, otherwise 0. /// @returns the borrow out of the subtraction -static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) { - for (uint32_t i = 0; i < len; ++i) { +static bool sub_1(uint64_t x[], unsigned len, uint64_t y) { + for (unsigned i = 0; i < len; ++i) { uint64_t X = x[i]; x[i] -= y; if (y > X) @@ -212,9 +197,9 @@ APInt& APInt::operator--() { /// @returns the carry out from the addition /// @brief General addition of 64-bit integer arrays static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, - uint32_t len) { + unsigned len) { bool carry = false; - for (uint32_t i = 0; i< len; ++i) { + for (unsigned i = 0; i< len; ++i) { uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x dest[i] = x[i] + y[i] + carry; carry = dest[i] < limit || (carry && dest[i] == limit); @@ -239,9 +224,9 @@ APInt& APInt::operator+=(const APInt& RHS) { /// @returns returns the borrow out. /// @brief Generalized subtraction of 64-bit integer arrays. static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, - uint32_t len) { + unsigned len) { bool borrow = false; - for (uint32_t i = 0; i < len; ++i) { + for (unsigned i = 0; i < len; ++i) { uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; borrow = y[i] > x_tmp || (borrow && x[i] == 0); dest[i] = x_tmp - y[i]; @@ -265,13 +250,13 @@ APInt& APInt::operator-=(const APInt& RHS) { /// into dest. /// @returns the carry out of the multiplication. /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. -static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { +static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { // Split y into high 32-bit part (hy) and low 32-bit part (ly) uint64_t ly = y & 0xffffffffULL, hy = y >> 32; uint64_t carry = 0; // For each digit of x. - for (uint32_t i = 0; i < len; ++i) { + for (unsigned i = 0; i < len; ++i) { // Split x into high and low words uint64_t lx = x[i] & 0xffffffffULL; uint64_t hx = x[i] >> 32; @@ -299,13 +284,13 @@ static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { /// Multiplies integer array x by integer array y and stores the result into /// the integer array dest. Note that dest's size must be >= xlen + ylen. /// @brief Generalized multiplicate of integer arrays. -static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[], - uint32_t ylen) { +static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], + unsigned ylen) { dest[xlen] = mul_1(dest, x, xlen, y[0]); - for (uint32_t i = 1; i < ylen; ++i) { + for (unsigned i = 1; i < ylen; ++i) { uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; uint64_t carry = 0, lx = 0, hx = 0; - for (uint32_t j = 0; j < xlen; ++j) { + for (unsigned j = 0; j < xlen; ++j) { lx = x[j] & 0xffffffffULL; hx = x[j] >> 32; // hasCarry - A flag to indicate if has carry. @@ -338,15 +323,15 @@ APInt& APInt::operator*=(const APInt& RHS) { } // Get some bit facts about LHS and check for zero - uint32_t lhsBits = getActiveBits(); - uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; + unsigned lhsBits = getActiveBits(); + unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; if (!lhsWords) // 0 * X ===> 0 return *this; // Get some bit facts about RHS and check for zero - uint32_t rhsBits = RHS.getActiveBits(); - uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; + unsigned rhsBits = RHS.getActiveBits(); + unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; if (!rhsWords) { // X * 0 ===> 0 clear(); @@ -354,7 +339,7 @@ APInt& APInt::operator*=(const APInt& RHS) { } // Allocate space for the result - uint32_t destWords = rhsWords + lhsWords; + unsigned destWords = rhsWords + lhsWords; uint64_t *dest = getMemory(destWords); // Perform the long multiply @@ -362,7 +347,7 @@ APInt& APInt::operator*=(const APInt& RHS) { // Copy result back into *this clear(); - uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; + unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); // delete dest array and return @@ -376,8 +361,8 @@ APInt& APInt::operator&=(const APInt& RHS) { VAL &= RHS.VAL; return *this; } - uint32_t numWords = getNumWords(); - for (uint32_t i = 0; i < numWords; ++i) + unsigned numWords = getNumWords(); + for (unsigned i = 0; i < numWords; ++i) pVal[i] &= RHS.pVal[i]; return *this; } @@ -388,8 +373,8 @@ APInt& APInt::operator|=(const APInt& RHS) { VAL |= RHS.VAL; return *this; } - uint32_t numWords = getNumWords(); - for (uint32_t i = 0; i < numWords; ++i) + unsigned numWords = getNumWords(); + for (unsigned i = 0; i < numWords; ++i) pVal[i] |= RHS.pVal[i]; return *this; } @@ -401,44 +386,32 @@ APInt& APInt::operator^=(const APInt& RHS) { this->clearUnusedBits(); return *this; } - uint32_t numWords = getNumWords(); - for (uint32_t i = 0; i < numWords; ++i) + unsigned numWords = getNumWords(); + for (unsigned i = 0; i < numWords; ++i) pVal[i] ^= RHS.pVal[i]; return clearUnusedBits(); } -APInt APInt::operator&(const APInt& RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL & RHS.VAL); - - uint32_t numWords = getNumWords(); +APInt APInt::AndSlowCase(const APInt& RHS) const { + unsigned numWords = getNumWords(); uint64_t* val = getMemory(numWords); - for (uint32_t i = 0; i < numWords; ++i) + for (unsigned i = 0; i < numWords; ++i) val[i] = pVal[i] & RHS.pVal[i]; return APInt(val, getBitWidth()); } -APInt APInt::operator|(const APInt& RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL | RHS.VAL); - - uint32_t numWords = getNumWords(); +APInt APInt::OrSlowCase(const APInt& RHS) const { + unsigned numWords = getNumWords(); uint64_t *val = getMemory(numWords); - for (uint32_t i = 0; i < numWords; ++i) + for (unsigned i = 0; i < numWords; ++i) val[i] = pVal[i] | RHS.pVal[i]; return APInt(val, getBitWidth()); } -APInt APInt::operator^(const APInt& RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(BitWidth, VAL ^ RHS.VAL); - - uint32_t numWords = getNumWords(); +APInt APInt::XorSlowCase(const APInt& RHS) const { + unsigned numWords = getNumWords(); uint64_t *val = getMemory(numWords); - for (uint32_t i = 0; i < numWords; ++i) + for (unsigned i = 0; i < numWords; ++i) val[i] = pVal[i] ^ RHS.pVal[i]; // 0^0==1 so clear the high bits in case they got set. @@ -449,7 +422,7 @@ bool APInt::operator !() const { if (isSingleWord()) return !VAL; - for (uint32_t i = 0; i < getNumWords(); ++i) + for (unsigned i = 0; i < getNumWords(); ++i) if (pVal[i]) return false; return true; @@ -482,19 +455,15 @@ APInt APInt::operator-(const APInt& RHS) const { return Result.clearUnusedBits(); } -bool APInt::operator[](uint32_t bitPosition) const { +bool APInt::operator[](unsigned bitPosition) const { return (maskBit(bitPosition) & (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; } -bool APInt::operator==(const APInt& RHS) const { - assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); - if (isSingleWord()) - return VAL == RHS.VAL; - +bool APInt::EqualSlowCase(const APInt& RHS) const { // Get some facts about the number of bits used in the two operands. - uint32_t n1 = getActiveBits(); - uint32_t n2 = RHS.getActiveBits(); + unsigned n1 = getActiveBits(); + unsigned n2 = RHS.getActiveBits(); // If the number of bits isn't the same, they aren't equal if (n1 != n2) @@ -511,11 +480,8 @@ bool APInt::operator==(const APInt& RHS) const { return true; } -bool APInt::operator==(uint64_t Val) const { - if (isSingleWord()) - return VAL == Val; - - uint32_t n = getActiveBits(); +bool APInt::EqualSlowCase(uint64_t Val) const { + unsigned n = getActiveBits(); if (n <= APINT_BITS_PER_WORD) return pVal[0] == Val; else @@ -528,8 +494,8 @@ bool APInt::ult(const APInt& RHS) const { return VAL < RHS.VAL; // Get active bit length of both operands - uint32_t n1 = getActiveBits(); - uint32_t n2 = RHS.getActiveBits(); + unsigned n1 = getActiveBits(); + unsigned n2 = RHS.getActiveBits(); // If magnitude of LHS is less than RHS, return true. if (n1 < n2) @@ -544,7 +510,7 @@ bool APInt::ult(const APInt& RHS) const { return pVal[0] < RHS.pVal[0]; // Otherwise, compare all words - uint32_t topWord = whichWord(std::max(n1,n2)-1); + unsigned topWord = whichWord(std::max(n1,n2)-1); for (int i = topWord; i >= 0; --i) { if (pVal[i] > RHS.pVal[i]) return false; @@ -590,7 +556,7 @@ bool APInt::slt(const APInt& RHS) const { return lhs.ult(rhs); } -APInt& APInt::set(uint32_t bitPosition) { +APInt& APInt::set(unsigned bitPosition) { if (isSingleWord()) VAL |= maskBit(bitPosition); else @@ -598,22 +564,9 @@ APInt& APInt::set(uint32_t bitPosition) { return *this; } -APInt& APInt::set() { - if (isSingleWord()) { - VAL = -1ULL; - return clearUnusedBits(); - } - - // Set all the bits in all the words. - for (uint32_t i = 0; i < getNumWords() - 1; ++i) - pVal[i] = -1ULL; - // Clear the unused ones - return clearUnusedBits(); -} - /// Set the given bit to 0 whose position is given as "bitPosition". /// @brief Set a given bit to 0. -APInt& APInt::clear(uint32_t bitPosition) { +APInt& APInt::clear(unsigned bitPosition) { if (isSingleWord()) VAL &= ~maskBit(bitPosition); else @@ -621,44 +574,55 @@ APInt& APInt::clear(uint32_t bitPosition) { return *this; } -/// @brief Set every bit to 0. -APInt& APInt::clear() { - if (isSingleWord()) - VAL = 0; - else - memset(pVal, 0, getNumWords() * APINT_WORD_SIZE); - return *this; -} - -/// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on -/// this APInt. -APInt APInt::operator~() const { - APInt Result(*this); - Result.flip(); - return Result; -} - /// @brief Toggle every bit to its opposite value. -APInt& APInt::flip() { - if (isSingleWord()) { - VAL ^= -1ULL; - return clearUnusedBits(); - } - for (uint32_t i = 0; i < getNumWords(); ++i) - pVal[i] ^= -1ULL; - return clearUnusedBits(); -} /// Toggle a given bit to its opposite value whose position is given /// as "bitPosition". /// @brief Toggles a given bit to its opposite value. -APInt& APInt::flip(uint32_t bitPosition) { +APInt& APInt::flip(unsigned bitPosition) { assert(bitPosition < BitWidth && "Out of the bit-width range!"); if ((*this)[bitPosition]) clear(bitPosition); else set(bitPosition); return *this; } +unsigned APInt::getBitsNeeded(const char* str, unsigned 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 + unsigned 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. + unsigned 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; @@ -667,18 +631,18 @@ uint64_t APInt::getHashValue() const { if (isSingleWord()) hash += VAL << 6; // clear separation of up to 64 bits else - for (uint32_t i = 0; i < getNumWords(); ++i) + for (unsigned i = 0; i < getNumWords(); ++i) hash += pVal[i] << 6; // clear sepration of up to 64 bits return hash; } /// HiBits - This function returns the high "numBits" bits of this APInt. -APInt APInt::getHiBits(uint32_t numBits) const { +APInt APInt::getHiBits(unsigned numBits) const { return APIntOps::lshr(*this, BitWidth - numBits); } /// LoBits - This function returns the low "numBits" bits of this APInt. -APInt APInt::getLoBits(uint32_t numBits) const { +APInt APInt::getLoBits(unsigned numBits) const { return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), BitWidth - numBits); } @@ -687,28 +651,24 @@ bool APInt::isPowerOf2() const { return (!!*this) && !(*this & (*this - APInt(BitWidth,1))); } -uint32_t APInt::countLeadingZeros() const { - uint32_t Count = 0; - if (isSingleWord()) - Count = CountLeadingZeros_64(VAL); - else { - for (uint32_t i = getNumWords(); i > 0u; --i) { - if (pVal[i-1] == 0) - Count += APINT_BITS_PER_WORD; - else { - Count += CountLeadingZeros_64(pVal[i-1]); - break; - } +unsigned APInt::countLeadingZerosSlowCase() const { + unsigned Count = 0; + for (unsigned i = getNumWords(); i > 0u; --i) { + if (pVal[i-1] == 0) + Count += APINT_BITS_PER_WORD; + else { + Count += CountLeadingZeros_64(pVal[i-1]); + break; } } - uint32_t remainder = BitWidth % APINT_BITS_PER_WORD; + unsigned remainder = BitWidth % APINT_BITS_PER_WORD; if (remainder) Count -= APINT_BITS_PER_WORD - remainder; - return Count; + return std::min(Count, BitWidth); } -static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) { - uint32_t Count = 0; +static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) { + unsigned Count = 0; if (skip) V <<= skip; while (V && (V & (1ULL << 63))) { @@ -718,14 +678,20 @@ static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) { return Count; } -uint32_t APInt::countLeadingOnes() const { +unsigned 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); + unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; + unsigned shift; + if (!highWordBits) { + highWordBits = APINT_BITS_PER_WORD; + shift = 0; + } else { + shift = APINT_BITS_PER_WORD - highWordBits; + } int i = getNumWords() - 1; - uint32_t Count = countLeadingOnes_64(pVal[i], shift); + unsigned Count = countLeadingOnes_64(pVal[i], shift); if (Count == highWordBits) { for (i--; i >= 0; --i) { if (pVal[i] == -1ULL) @@ -739,23 +705,31 @@ uint32_t APInt::countLeadingOnes() const { return Count; } -uint32_t APInt::countTrailingZeros() const { +unsigned APInt::countTrailingZeros() const { if (isSingleWord()) - return CountTrailingZeros_64(VAL); - uint32_t Count = 0; - uint32_t i = 0; + return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth); + unsigned Count = 0; + unsigned i = 0; for (; i < getNumWords() && pVal[i] == 0; ++i) Count += APINT_BITS_PER_WORD; if (i < getNumWords()) Count += CountTrailingZeros_64(pVal[i]); - return Count; + return std::min(Count, BitWidth); } -uint32_t APInt::countPopulation() const { - if (isSingleWord()) - return CountPopulation_64(VAL); - uint32_t Count = 0; - for (uint32_t i = 0; i < getNumWords(); ++i) +unsigned APInt::countTrailingOnesSlowCase() const { + unsigned Count = 0; + unsigned i = 0; + for (; i < getNumWords() && pVal[i] == -1ULL; ++i) + Count += APINT_BITS_PER_WORD; + if (i < getNumWords()) + Count += CountTrailingOnes_64(pVal[i]); + return std::min(Count, BitWidth); +} + +unsigned APInt::countPopulationSlowCase() const { + unsigned Count = 0; + for (unsigned i = 0; i < getNumWords(); ++i) Count += CountPopulation_64(pVal[i]); return Count; } @@ -765,9 +739,9 @@ APInt APInt::byteSwap() const { if (BitWidth == 16) return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); else if (BitWidth == 32) - return APInt(BitWidth, ByteSwap_32(uint32_t(VAL))); + return APInt(BitWidth, ByteSwap_32(unsigned(VAL))); else if (BitWidth == 48) { - uint32_t Tmp1 = uint32_t(VAL >> 16); + unsigned Tmp1 = unsigned(VAL >> 16); Tmp1 = ByteSwap_32(Tmp1); uint16_t Tmp2 = uint16_t(VAL); Tmp2 = ByteSwap_16(Tmp2); @@ -777,7 +751,7 @@ APInt APInt::byteSwap() const { else { APInt Result(BitWidth, 0); char *pByte = (char*)Result.pVal; - for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { + for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { char Tmp = pByte[i]; pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i]; pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp; @@ -797,7 +771,7 @@ APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, return A; } -APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) { +APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { union { double D; uint64_t I; @@ -829,7 +803,7 @@ APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) { // Otherwise, we have to shift the mantissa bits up to the right location APInt Tmp(width, mantissa); - Tmp = Tmp.shl(exp - 52); + Tmp = Tmp.shl((unsigned)exp - 52); return isNeg ? -Tmp : Tmp; } @@ -858,7 +832,7 @@ double APInt::roundToDouble(bool isSigned) const { APInt Tmp(isNeg ? -(*this) : (*this)); // Figure out how many bits we're using. - uint32_t n = Tmp.getActiveBits(); + unsigned n = Tmp.getActiveBits(); // The exponent (without bias normalization) is just the number of bits // we are using. Note that the sign bit is gone since we constructed the @@ -900,12 +874,12 @@ double APInt::roundToDouble(bool isSigned) const { } // Truncate to new width. -APInt &APInt::trunc(uint32_t width) { +APInt &APInt::trunc(unsigned width) { assert(width < BitWidth && "Invalid APInt Truncate request"); - assert(width >= IntegerType::MIN_INT_BITS && "Can't truncate to 0 bits"); - uint32_t wordsBefore = getNumWords(); + assert(width && "Can't truncate to 0 bits"); + unsigned wordsBefore = getNumWords(); BitWidth = width; - uint32_t wordsAfter = getNumWords(); + unsigned wordsAfter = getNumWords(); if (wordsBefore != wordsAfter) { if (wordsAfter == 1) { uint64_t *tmp = pVal; @@ -913,7 +887,7 @@ APInt &APInt::trunc(uint32_t width) { delete [] tmp; } else { uint64_t *newVal = getClearedMemory(wordsAfter); - for (uint32_t i = 0; i < wordsAfter; ++i) + for (unsigned i = 0; i < wordsAfter; ++i) newVal[i] = pVal[i]; delete [] pVal; pVal = newVal; @@ -923,9 +897,8 @@ APInt &APInt::trunc(uint32_t width) { } // Sign extend to a new width. -APInt &APInt::sext(uint32_t width) { +APInt &APInt::sext(unsigned 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); @@ -933,14 +906,14 @@ APInt &APInt::sext(uint32_t width) { } // The sign bit is set. First, get some facts - uint32_t wordsBefore = getNumWords(); - uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD; + unsigned wordsBefore = getNumWords(); + unsigned wordBits = BitWidth % APINT_BITS_PER_WORD; BitWidth = width; - uint32_t wordsAfter = getNumWords(); + unsigned wordsAfter = getNumWords(); // Mask the high order word appropriately if (wordsBefore == wordsAfter) { - uint32_t newWordBits = width % APINT_BITS_PER_WORD; + unsigned newWordBits = width % APINT_BITS_PER_WORD; // The extension is contained to the wordsBefore-1th word. uint64_t mask = ~0ULL; if (newWordBits) @@ -958,11 +931,11 @@ APInt &APInt::sext(uint32_t width) { if (wordsBefore == 1) newVal[0] = VAL | mask; else { - for (uint32_t i = 0; i < wordsBefore; ++i) + for (unsigned i = 0; i < wordsBefore; ++i) newVal[i] = pVal[i]; newVal[wordsBefore-1] |= mask; } - for (uint32_t i = wordsBefore; i < wordsAfter; i++) + for (unsigned i = wordsBefore; i < wordsAfter; i++) newVal[i] = -1ULL; if (wordsBefore != 1) delete [] pVal; @@ -971,18 +944,17 @@ APInt &APInt::sext(uint32_t width) { } // Zero extend to a new width. -APInt &APInt::zext(uint32_t width) { +APInt &APInt::zext(unsigned width) { assert(width > BitWidth && "Invalid APInt ZeroExtend request"); - assert(width <= IntegerType::MAX_INT_BITS && "Too many bits"); - uint32_t wordsBefore = getNumWords(); + unsigned wordsBefore = getNumWords(); BitWidth = width; - uint32_t wordsAfter = getNumWords(); + unsigned wordsAfter = getNumWords(); if (wordsBefore != wordsAfter) { uint64_t *newVal = getClearedMemory(wordsAfter); if (wordsBefore == 1) newVal[0] = VAL; else - for (uint32_t i = 0; i < wordsBefore; ++i) + for (unsigned i = 0; i < wordsBefore; ++i) newVal[i] = pVal[i]; if (wordsBefore != 1) delete [] pVal; @@ -991,7 +963,7 @@ APInt &APInt::zext(uint32_t width) { return *this; } -APInt &APInt::zextOrTrunc(uint32_t width) { +APInt &APInt::zextOrTrunc(unsigned width) { if (BitWidth < width) return zext(width); if (BitWidth > width) @@ -999,7 +971,7 @@ APInt &APInt::zextOrTrunc(uint32_t width) { return *this; } -APInt &APInt::sextOrTrunc(uint32_t width) { +APInt &APInt::sextOrTrunc(unsigned width) { if (BitWidth < width) return sext(width); if (BitWidth > width) @@ -1009,7 +981,13 @@ APInt &APInt::sextOrTrunc(uint32_t width) { /// Arithmetic right-shift this APInt by shiftAmt. /// @brief Arithmetic right-shift function. -APInt APInt::ashr(uint32_t shiftAmt) const { +APInt APInt::ashr(const APInt &shiftAmt) const { + return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth)); +} + +/// Arithmetic right-shift this APInt by shiftAmt. +/// @brief Arithmetic right-shift function. +APInt APInt::ashr(unsigned shiftAmt) const { assert(shiftAmt <= BitWidth && "Invalid shift amount"); // Handle a degenerate case if (shiftAmt == 0) @@ -1020,7 +998,7 @@ APInt APInt::ashr(uint32_t shiftAmt) const { if (shiftAmt == BitWidth) return APInt(BitWidth, 0); // undefined else { - uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth; + unsigned SignBit = APINT_BITS_PER_WORD - BitWidth; return APInt(BitWidth, (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); } @@ -1029,27 +1007,28 @@ APInt APInt::ashr(uint32_t shiftAmt) const { // 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 (shiftAmt == BitWidth) { if (isNegative()) - return APInt(BitWidth, -1ULL); + return APInt(BitWidth, -1ULL, true); else return APInt(BitWidth, 0); + } // Create some space for the result. uint64_t * val = new uint64_t[getNumWords()]; // 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? + unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word + unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift + unsigned breakWord = getNumWords() - 1 - offset; // last word affected + unsigned 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) { // Move the words containing significant bits - for (uint32_t i = 0; i <= breakWord; ++i) + for (unsigned i = 0; i <= breakWord; ++i) val[i] = pVal[i+offset]; // move whole word // Adjust the top significant word for sign bit fill, if negative @@ -1058,7 +1037,7 @@ APInt APInt::ashr(uint32_t shiftAmt) const { val[breakWord] |= ~0ULL << bitsInWord; // set high bits } else { // Shift the low order words - for (uint32_t i = 0; i < breakWord; ++i) { + for (unsigned 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) | @@ -1071,7 +1050,7 @@ APInt APInt::ashr(uint32_t shiftAmt) const { // Deal with sign extenstion in the break word, and possibly the word before // it. - if (isNegative()) + if (isNegative()) { if (wordShift > bitsInWord) { if (breakWord > 0) val[breakWord-1] |= @@ -1079,23 +1058,31 @@ APInt APInt::ashr(uint32_t shiftAmt) const { val[breakWord] |= ~0ULL; } else val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); + } } // Remaining words are 0 or -1, just assign them. uint64_t fillValue = (isNegative() ? -1ULL : 0); - for (uint32_t i = breakWord+1; i < getNumWords(); ++i) + for (unsigned i = breakWord+1; i < getNumWords(); ++i) 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()) +APInt APInt::lshr(const APInt &shiftAmt) const { + return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); +} + +/// Logical right-shift this APInt by shiftAmt. +/// @brief Logical right-shift function. +APInt APInt::lshr(unsigned shiftAmt) const { + 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 @@ -1103,6 +1090,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 by the 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()]; @@ -1117,55 +1110,59 @@ APInt APInt::lshr(uint32_t shiftAmt) const { } // 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; + unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; + unsigned offset = shiftAmt / 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) + for (unsigned i = 0; i < getNumWords() - offset; ++i) val[i] = pVal[i+offset]; - for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++) + for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) val[i] = 0; return APInt(val,BitWidth).clearUnusedBits(); } // Shift the low order words - uint32_t breakWord = getNumWords() - offset -1; - for (uint32_t i = 0; i < breakWord; ++i) + unsigned breakWord = getNumWords() - offset -1; + for (unsigned i = 0; i < breakWord; ++i) 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; // Remaining words are 0 - for (uint32_t i = breakWord+1; i < getNumWords(); ++i) + for (unsigned i = breakWord+1; i < getNumWords(); ++i) val[i] = 0; return APInt(val, BitWidth).clearUnusedBits(); } /// Left-shift this APInt by shiftAmt. /// @brief Left-shift function. -APInt APInt::shl(uint32_t shiftAmt) const { - assert(shiftAmt <= BitWidth && "Invalid shift amount"); - if (isSingleWord()) { - if (shiftAmt == BitWidth) - return APInt(BitWidth, 0); // avoid undefined shift results - return APInt(BitWidth, VAL << shiftAmt); - } +APInt APInt::shl(const APInt &shiftAmt) const { + // It's undefined behavior in C to shift by BitWidth or greater. + return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); +} +APInt APInt::shlSlowCase(unsigned shiftAmt) const { // 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 // results. We define these "undefined results" to always be 0. 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()]; // If we are shifting less than a word, do it the easy way if (shiftAmt < APINT_BITS_PER_WORD) { uint64_t carry = 0; - for (uint32_t i = 0; i < getNumWords(); i++) { + for (unsigned i = 0; i < getNumWords(); i++) { val[i] = pVal[i] << shiftAmt | carry; carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); } @@ -1173,20 +1170,20 @@ APInt APInt::shl(uint32_t shiftAmt) const { } // 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; + unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; + unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // If we are shifting whole words, just move whole words if (wordShift == 0) { - for (uint32_t i = 0; i < offset; i++) + for (unsigned i = 0; i < offset; i++) val[i] = 0; - for (uint32_t i = offset; i < getNumWords(); i++) + for (unsigned i = offset; i < getNumWords(); i++) val[i] = pVal[i-offset]; return APInt(val,BitWidth).clearUnusedBits(); } // Copy whole words from this to Result. - uint32_t i = getNumWords() - 1; + unsigned i = getNumWords() - 1; for (; i > offset; --i) val[i] = pVal[i-offset] << wordShift | pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); @@ -1196,6 +1193,35 @@ APInt APInt::shl(uint32_t shiftAmt) const { return APInt(val, BitWidth).clearUnusedBits(); } +APInt APInt::rotl(const APInt &rotateAmt) const { + return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth)); +} + +APInt APInt::rotl(unsigned 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(const APInt &rotateAmt) const { + return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth)); +} + +APInt APInt::rotr(unsigned 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), @@ -1207,7 +1233,7 @@ APInt APInt::shl(uint32_t shiftAmt) const { APInt APInt::sqrt() const { // Determine the magnitude of the value. - uint32_t magnitude = getActiveBits(); + unsigned magnitude = getActiveBits(); // Use a fast table for some small values. This also gets rid of some // rounding errors in libc sqrt for small values. @@ -1244,7 +1270,7 @@ APInt APInt::sqrt() const { // 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; + unsigned nbits = BitWidth, i = 4; APInt testy(BitWidth, 16); APInt x_old(BitWidth, 1); APInt x_new(BitWidth, 0); @@ -1287,12 +1313,56 @@ APInt APInt::sqrt() const { return x_old + 1; } +/// Computes the multiplicative inverse of this APInt for a given modulo. The +/// iterative extended Euclidean algorithm is used to solve for this value, +/// however we simplify it to speed up calculating only the inverse, and take +/// advantage of div+rem calculations. We also use some tricks to avoid copying +/// (potentially large) APInts around. +APInt APInt::multiplicativeInverse(const APInt& modulo) const { + assert(ult(modulo) && "This APInt must be smaller than the modulo"); + + // Using the properties listed at the following web page (accessed 06/21/08): + // http://www.numbertheory.org/php/euclid.html + // (especially the properties numbered 3, 4 and 9) it can be proved that + // BitWidth bits suffice for all the computations in the algorithm implemented + // below. More precisely, this number of bits suffice if the multiplicative + // inverse exists, but may not suffice for the general extended Euclidean + // algorithm. + + APInt r[2] = { modulo, *this }; + APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; + APInt q(BitWidth, 0); + + unsigned i; + for (i = 0; r[i^1] != 0; i ^= 1) { + // An overview of the math without the confusing bit-flipping: + // q = r[i-2] / r[i-1] + // r[i] = r[i-2] % r[i-1] + // t[i] = t[i-2] - t[i-1] * q + udivrem(r[i], r[i^1], q, r[i]); + t[i] -= t[i^1] * q; + } + + // If this APInt and the modulo are not coprime, there is no multiplicative + // inverse, so return 0. We check this by looking at the next-to-last + // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean + // algorithm. + if (r[i] != 1) + return APInt(BitWidth, 0); + + // The next-to-last t is the multiplicative inverse. However, we are + // interested in a positive inverse. Calcuate a positive one from a negative + // one if necessary. A simple addition of the modulo suffices because + // abs(t[i]) is known to be less than *this/2 (see the link above). + return t[i].isNegative() ? t[i] + modulo : t[i]; +} + /// 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 /// the algorithm and any deviation from it. -static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, - uint32_t m, uint32_t n) { +static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, + unsigned m, unsigned n) { assert(u && "Must provide dividend"); assert(v && "Must provide divisor"); assert(q && "Must provide quotient"); @@ -1303,12 +1373,14 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // is 2^31 so we just set it to -1u. uint64_t b = uint64_t(1) << 32; +#if 0 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n'); DEBUG(cerr << "KnuthDiv: original:"); DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); DEBUG(cerr << " by"); DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); DEBUG(cerr << '\n'); +#endif // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of // u and v by d. Note that we have taken Knuth's advice here to use a power // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of @@ -1317,27 +1389,29 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // and v so that its high bits are shifted to the top of v's range without // overflow. Note that this can require an extra word in u so that u must // be of length m+n+1. - uint32_t shift = CountLeadingZeros_32(v[n-1]); - uint32_t v_carry = 0; - uint32_t u_carry = 0; + unsigned shift = CountLeadingZeros_32(v[n-1]); + unsigned v_carry = 0; + unsigned u_carry = 0; if (shift) { - for (uint32_t i = 0; i < m+n; ++i) { - uint32_t u_tmp = u[i] >> (32 - shift); + for (unsigned i = 0; i < m+n; ++i) { + unsigned u_tmp = u[i] >> (32 - shift); u[i] = (u[i] << shift) | u_carry; u_carry = u_tmp; } - for (uint32_t i = 0; i < n; ++i) { - uint32_t v_tmp = v[i] >> (32 - shift); + for (unsigned i = 0; i < n; ++i) { + unsigned v_tmp = v[i] >> (32 - shift); v[i] = (v[i] << shift) | v_carry; v_carry = v_tmp; } } u[m+n] = u_carry; +#if 0 DEBUG(cerr << "KnuthDiv: normal:"); DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); DEBUG(cerr << " by"); DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); DEBUG(cerr << '\n'); +#endif // D2. [Initialize j.] Set j to m. This is the loop counter over the places. int j = m; @@ -1368,7 +1442,7 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // consists of a simple multiplication by a one-place number, combined with // a subtraction. bool isNeg = false; - for (uint32_t i = 0; i < n; ++i) { + for (unsigned i = 0; i < n; ++i) { uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); bool borrow = subtrahend > u_tmp; @@ -1377,9 +1451,9 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, << ", borrow = " << borrow << '\n'); uint64_t result = u_tmp - subtrahend; - uint32_t k = j + i; - u[k++] = result & (b-1); // subtract low word - u[k++] = result >> 32; // subtract high word + unsigned k = j + i; + u[k++] = (unsigned)(result & (b-1)); // subtract low word + u[k++] = (unsigned)(result >> 32); // subtract high word while (borrow && k <= m+n) { // deal with borrow to the left borrow = u[k] == 0; u[k]--; @@ -1399,7 +1473,7 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // if (isNeg) { bool carry = true; // true because b's complement is "complement + 1" - for (uint32_t i = 0; i <= m+n; ++i) { + for (unsigned i = 0; i <= m+n; ++i) { u[i] = ~u[i] + carry; // b's complement carry = carry && u[i] == 0; } @@ -1410,7 +1484,7 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was // negative, go to step D6; otherwise go on to step D7. - q[j] = qp; + q[j] = (unsigned)qp; if (isNeg) { // D6. [Add back]. The probability that this step is necessary is very // small, on the order of only 2/b. Make sure that test data accounts for @@ -1420,8 +1494,8 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // A carry will occur to the left of u[j+n], and it should be ignored // since it cancels with the borrow that occurred in D4. bool carry = false; - for (uint32_t i = 0; i < n; i++) { - uint32_t limit = std::min(u[j+i],v[i]); + for (unsigned i = 0; i < n; i++) { + unsigned limit = std::min(u[j+i],v[i]); u[j+i] += v[i] + carry; carry = u[j+i] < limit || (carry && u[j+i] == limit); } @@ -1446,7 +1520,7 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, // multiplication by d by using a shift left. So, all we have to do is // shift right here. In order to mak if (shift) { - uint32_t carry = 0; + unsigned carry = 0; DEBUG(cerr << "KnuthDiv: remainder:"); for (int i = n-1; i >= 0; i--) { r[i] = (u[i] >> shift) | carry; @@ -1461,11 +1535,13 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, } DEBUG(cerr << '\n'); } +#if 0 DEBUG(cerr << std::setbase(10) << '\n'); +#endif } -void APInt::divide(const APInt LHS, uint32_t lhsWords, - const APInt &RHS, uint32_t rhsWords, +void APInt::divide(const APInt LHS, unsigned lhsWords, + const APInt &RHS, unsigned rhsWords, APInt *Quotient, APInt *Remainder) { assert(lhsWords >= rhsWords && "Fractional result"); @@ -1477,17 +1553,17 @@ void APInt::divide(const APInt LHS, uint32_t lhsWords, // can't use 64-bit operands here because we don't have native results of // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't // work on large-endian machines. - uint64_t mask = ~0ull >> (sizeof(uint32_t)*8); - uint32_t n = rhsWords * 2; - uint32_t m = (lhsWords * 2) - n; + uint64_t mask = ~0ull >> (sizeof(unsigned)*8); + unsigned n = rhsWords * 2; + unsigned m = (lhsWords * 2) - n; // Allocate space for the temporary values we need either on the stack, if // it will fit, or on the heap if it won't. - uint32_t SPACE[128]; - uint32_t *U = 0; - uint32_t *V = 0; - uint32_t *Q = 0; - uint32_t *R = 0; + unsigned SPACE[128]; + unsigned *U = 0; + unsigned *V = 0; + unsigned *Q = 0; + unsigned *R = 0; if ((Remainder?4:3)*n+2*m+1 <= 128) { U = &SPACE[0]; V = &SPACE[m+n+1]; @@ -1495,34 +1571,34 @@ void APInt::divide(const APInt LHS, uint32_t lhsWords, if (Remainder) R = &SPACE[(m+n+1) + n + (m+n)]; } else { - U = new uint32_t[m + n + 1]; - V = new uint32_t[n]; - Q = new uint32_t[m+n]; + U = new unsigned[m + n + 1]; + V = new unsigned[n]; + Q = new unsigned[m+n]; if (Remainder) - R = new uint32_t[n]; + R = new unsigned[n]; } // Initialize the dividend - memset(U, 0, (m+n+1)*sizeof(uint32_t)); + memset(U, 0, (m+n+1)*sizeof(unsigned)); for (unsigned i = 0; i < lhsWords; ++i) { uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); - U[i * 2] = tmp & mask; - U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8); + U[i * 2] = (unsigned)(tmp & mask); + U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8)); } U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. // Initialize the divisor - memset(V, 0, (n)*sizeof(uint32_t)); + memset(V, 0, (n)*sizeof(unsigned)); for (unsigned i = 0; i < rhsWords; ++i) { uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); - V[i * 2] = tmp & mask; - V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8); + V[i * 2] = (unsigned)(tmp & mask); + V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8)); } // initialize the quotient and remainder - memset(Q, 0, (m+n) * sizeof(uint32_t)); + memset(Q, 0, (m+n) * sizeof(unsigned)); if (Remainder) - memset(R, 0, n * sizeof(uint32_t)); + memset(R, 0, n * sizeof(unsigned)); // Now, adjust m and n for the Knuth division. n is the number of words in // the divisor. m is the number of words by which the dividend exceeds the @@ -1543,8 +1619,8 @@ void APInt::divide(const APInt LHS, uint32_t lhsWords, // are using base 2^32 instead of base 10. assert(n != 0 && "Divide by zero?"); if (n == 1) { - uint32_t divisor = V[0]; - uint32_t remainder = 0; + unsigned divisor = V[0]; + unsigned remainder = 0; for (int i = m+n-1; i >= 0; i--) { uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; if (partial_dividend == 0) { @@ -1552,13 +1628,13 @@ void APInt::divide(const APInt LHS, uint32_t lhsWords, remainder = 0; } else if (partial_dividend < divisor) { Q[i] = 0; - remainder = partial_dividend; + remainder = (unsigned)partial_dividend; } else if (partial_dividend == divisor) { Q[i] = 1; remainder = 0; } else { - Q[i] = partial_dividend / divisor; - remainder = partial_dividend - (Q[i] * divisor); + Q[i] = (unsigned)(partial_dividend / divisor); + remainder = (unsigned)(partial_dividend - (Q[i] * divisor)); } } if (R) @@ -1650,11 +1726,11 @@ APInt APInt::udiv(const APInt& RHS) const { } // Get some facts about the LHS and RHS number of bits and words - uint32_t rhsBits = RHS.getActiveBits(); - uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); + unsigned rhsBits = RHS.getActiveBits(); + unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); assert(rhsWords && "Divided by zero???"); - uint32_t lhsBits = this->getActiveBits(); - uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); + unsigned lhsBits = this->getActiveBits(); + unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); // Deal with some degenerate cases if (!lhsWords) @@ -1685,12 +1761,12 @@ APInt APInt::urem(const APInt& RHS) const { } // Get some facts about the LHS - uint32_t lhsBits = getActiveBits(); - uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); + unsigned lhsBits = getActiveBits(); + unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); // Get some facts about the RHS - uint32_t rhsBits = RHS.getActiveBits(); - uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); + unsigned rhsBits = RHS.getActiveBits(); + unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); assert(rhsWords && "Performing remainder operation by zero ???"); // Check the degenerate cases @@ -1708,13 +1784,53 @@ 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::fromString(uint32_t numbits, const char *str, uint32_t slen, +void APInt::udivrem(const APInt &LHS, const APInt &RHS, + APInt &Quotient, APInt &Remainder) { + // Get some size facts about the dividend and divisor + unsigned lhsBits = LHS.getActiveBits(); + unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); + unsigned rhsBits = RHS.getActiveBits(); + unsigned 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. + uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0]; + uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; + Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue); + Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue); + return; + } + + // Okay, lets do it the long way + divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); +} + +void APInt::fromString(unsigned numbits, const char *str, unsigned slen, uint8_t radix) { // Check our assumptions here assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && @@ -1723,17 +1839,17 @@ 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()) pVal = getClearedMemory(getNumWords()); // Figure out if we can shift instead of multiply - uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); + unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); // Set up an APInt for the digit to add outside the loop so we don't // constantly construct/destruct it. @@ -1743,23 +1859,32 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, // Enter digit traversal loop for (unsigned i = 0; i < slen; i++) { // Get a digit - uint32_t digit = 0; + unsigned 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'; + assert((radix == 10 || + (radix == 8 && digit != 8 && digit != 9) || + (radix == 2 && (digit == 0 || digit == 1))) && + "Invalid digit in string for given radix"); + } 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; @@ -1777,92 +1902,744 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, } } -std::string APInt::toString(uint8_t radix, bool wantSigned) const { - assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && +void APInt::toString(SmallVectorImpl &Str, unsigned Radix, + bool Signed) const { + assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) && "Radix should be 2, 8, 10, or 16!"); - static const char *digits[] = { - "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F" - }; - std::string result; - uint32_t bits_used = getActiveBits(); + + // First, check for a zero value and just short circuit the logic below. + if (*this == 0) { + Str.push_back('0'); + return; + } + + static const char Digits[] = "0123456789ABCDEF"; + if (isSingleWord()) { - char buf[65]; - const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") : - (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0))); - if (format) { - if (wantSigned) { - int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >> - (APINT_BITS_PER_WORD-BitWidth); - sprintf(buf, format, sextVal); - } else - sprintf(buf, format, VAL); - } else { - memset(buf, 0, 65); - uint64_t v = VAL; - while (bits_used) { - uint32_t bit = v & 1; - bits_used--; - buf[bits_used] = digits[bit][0]; - v >>=1; + char Buffer[65]; + char *BufPtr = Buffer+65; + + uint64_t N; + if (Signed) { + int64_t I = getSExtValue(); + if (I < 0) { + Str.push_back('-'); + I = -I; } + N = I; + } else { + N = getZExtValue(); } - result = buf; - return result; - } - - 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; - } + + while (N) { + *--BufPtr = Digits[N % Radix]; + N /= Radix; } - return result; + Str.append(BufPtr, Buffer+65); + return; } - APInt tmp(*this); - APInt divisor(4, radix); - APInt zero(tmp.getBitWidth(), 0); - size_t insert_at = 0; - if (wantSigned && tmp[BitWidth-1]) { + APInt Tmp(*this); + + if (Signed && 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; - } - if (tmp == APInt(tmp.getBitWidth(), 0)) - result = "0"; - else while (tmp.ne(zero)) { - APInt APdigit(1,0); - APInt tmp2(tmp.getBitWidth(), 0); - divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, - &APdigit); - uint32_t digit = APdigit.getZExtValue(); - assert(digit < radix && "divide failed"); - result.insert(insert_at,digits[digit]); - tmp = tmp2; + Tmp.flip(); + Tmp++; + Str.push_back('-'); + } + + // We insert the digits backward, then reverse them to get the right order. + unsigned StartDig = Str.size(); + + // 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 the value is zero. + if (Radix != 10) { + // Just shift tmp right for each digit width until it becomes zero + unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1)); + unsigned MaskAmt = Radix - 1; + + while (Tmp != 0) { + unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; + Str.push_back(Digits[Digit]); + Tmp = Tmp.lshr(ShiftAmt); + } + } else { + APInt divisor(4, 10); + while (Tmp != 0) { + APInt APdigit(1, 0); + APInt tmp2(Tmp.getBitWidth(), 0); + divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, + &APdigit); + unsigned Digit = (unsigned)APdigit.getZExtValue(); + assert(Digit < Radix && "divide failed"); + Str.push_back(Digits[Digit]); + Tmp = tmp2; + } } + + // Reverse the digits before returning. + std::reverse(Str.begin()+StartDig, Str.end()); +} - return result; +/// toString - This returns the APInt as a std::string. Note that this is an +/// inefficient method. It is better to pass in a SmallVector/SmallString +/// to the methods above. +std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { + SmallString<40> S; + toString(S, Radix, Signed); + return S.c_str(); +} + + +void APInt::dump() const { + SmallString<40> S, U; + this->toStringUnsigned(U); + this->toStringSigned(S); + fprintf(stderr, "APInt(%db, %su %ss)", BitWidth, U.c_str(), S.c_str()); +} + +void APInt::print(raw_ostream &OS, bool isSigned) const { + SmallString<40> S; + this->toString(S, 10, isSigned); + OS << S.c_str(); +} + +// This implements a variety of operations on a representation of +// arbitrary precision, two's-complement, bignum integer values. + +/* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe + and unrestricting assumption. */ +#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] +COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); + +/* Some handy functions local to this file. */ +namespace { + + /* Returns the integer part with the least significant BITS set. + BITS cannot be zero. */ + static inline integerPart + lowBitMask(unsigned int bits) + { + assert (bits != 0 && bits <= integerPartWidth); + + return ~(integerPart) 0 >> (integerPartWidth - bits); + } + + /* Returns the value of the lower half of PART. */ + static inline integerPart + lowHalf(integerPart part) + { + return part & lowBitMask(integerPartWidth / 2); + } + + /* Returns the value of the upper half of PART. */ + static inline integerPart + highHalf(integerPart part) + { + return part >> (integerPartWidth / 2); + } + + /* Returns the bit number of the most significant set bit of a part. + If the input number has no bits set -1U is returned. */ + static unsigned int + partMSB(integerPart value) + { + unsigned int n, msb; + + if (value == 0) + return -1U; + + n = integerPartWidth / 2; + + msb = 0; + do { + if (value >> n) { + value >>= n; + msb += n; + } + + n >>= 1; + } while (n); + + return msb; + } + + /* Returns the bit number of the least significant set bit of a + part. If the input number has no bits set -1U is returned. */ + static unsigned int + partLSB(integerPart value) + { + unsigned int n, lsb; + + if (value == 0) + return -1U; + + lsb = integerPartWidth - 1; + n = integerPartWidth / 2; + + do { + if (value << n) { + value <<= n; + lsb -= n; + } + + n >>= 1; + } while (n); + + return lsb; + } } -#ifndef NDEBUG -void APInt::dump() const +/* Sets the least significant part of a bignum to the input value, and + zeroes out higher parts. */ +void +APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) { - cerr << "APInt(" << BitWidth << ")=" << std::setbase(16); - if (isSingleWord()) - cerr << VAL; - else for (unsigned i = getNumWords(); i > 0; i--) { - cerr << pVal[i-1] << " "; + unsigned int i; + + assert (parts > 0); + + dst[0] = part; + for(i = 1; i < parts; i++) + dst[i] = 0; +} + +/* Assign one bignum to another. */ +void +APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + dst[i] = src[i]; +} + +/* Returns true if a bignum is zero, false otherwise. */ +bool +APInt::tcIsZero(const integerPart *src, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + if (src[i]) + return false; + + return true; +} + +/* Extract the given bit of a bignum; returns 0 or 1. */ +int +APInt::tcExtractBit(const integerPart *parts, unsigned int bit) +{ + return(parts[bit / integerPartWidth] + & ((integerPart) 1 << bit % integerPartWidth)) != 0; +} + +/* Set the given bit of a bignum. */ +void +APInt::tcSetBit(integerPart *parts, unsigned int bit) +{ + parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); +} + +/* Returns the bit number of the least significant set bit of a + number. If the input number has no bits set -1U is returned. */ +unsigned int +APInt::tcLSB(const integerPart *parts, unsigned int n) +{ + unsigned int i, lsb; + + for(i = 0; i < n; i++) { + if (parts[i] != 0) { + lsb = partLSB(parts[i]); + + return lsb + i * integerPartWidth; + } } - cerr << " U(" << this->toString(10) << ") S(" << this->toStringSigned(10) - << ")\n" << std::setbase(10); + + return -1U; +} + +/* Returns the bit number of the most significant set bit of a number. + If the input number has no bits set -1U is returned. */ +unsigned int +APInt::tcMSB(const integerPart *parts, unsigned int n) +{ + unsigned int msb; + + do { + --n; + + if (parts[n] != 0) { + msb = partMSB(parts[n]); + + return msb + n * integerPartWidth; + } + } while (n); + + return -1U; +} + +/* Copy the bit vector of width srcBITS from SRC, starting at bit + srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes + the least significant bit of DST. All high bits above srcBITS in + DST are zero-filled. */ +void +APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src, + unsigned int srcBits, unsigned int srcLSB) +{ + unsigned int firstSrcPart, dstParts, shift, n; + + dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; + assert (dstParts <= dstCount); + + firstSrcPart = srcLSB / integerPartWidth; + tcAssign (dst, src + firstSrcPart, dstParts); + + shift = srcLSB % integerPartWidth; + tcShiftRight (dst, dstParts, shift); + + /* We now have (dstParts * integerPartWidth - shift) bits from SRC + in DST. If this is less that srcBits, append the rest, else + clear the high bits. */ + n = dstParts * integerPartWidth - shift; + if (n < srcBits) { + integerPart mask = lowBitMask (srcBits - n); + dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) + << n % integerPartWidth); + } else if (n > srcBits) { + if (srcBits % integerPartWidth) + dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); + } + + /* Clear high parts. */ + while (dstParts < dstCount) + dst[dstParts++] = 0; +} + +/* DST += RHS + C where C is zero or one. Returns the carry flag. */ +integerPart +APInt::tcAdd(integerPart *dst, const integerPart *rhs, + integerPart c, unsigned int parts) +{ + unsigned int i; + + assert(c <= 1); + + for(i = 0; i < parts; i++) { + integerPart l; + + l = dst[i]; + if (c) { + dst[i] += rhs[i] + 1; + c = (dst[i] <= l); + } else { + dst[i] += rhs[i]; + c = (dst[i] < l); + } + } + + return c; +} + +/* DST -= RHS + C where C is zero or one. Returns the carry flag. */ +integerPart +APInt::tcSubtract(integerPart *dst, const integerPart *rhs, + integerPart c, unsigned int parts) +{ + unsigned int i; + + assert(c <= 1); + + for(i = 0; i < parts; i++) { + integerPart l; + + l = dst[i]; + if (c) { + dst[i] -= rhs[i] + 1; + c = (dst[i] >= l); + } else { + dst[i] -= rhs[i]; + c = (dst[i] > l); + } + } + + return c; +} + +/* Negate a bignum in-place. */ +void +APInt::tcNegate(integerPart *dst, unsigned int parts) +{ + tcComplement(dst, parts); + tcIncrement(dst, parts); +} + +/* DST += SRC * MULTIPLIER + CARRY if add is true + DST = SRC * MULTIPLIER + CARRY if add is false + + Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC + they must start at the same point, i.e. DST == SRC. + + If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is + returned. Otherwise DST is filled with the least significant + DSTPARTS parts of the result, and if all of the omitted higher + parts were zero return zero, otherwise overflow occurred and + return one. */ +int +APInt::tcMultiplyPart(integerPart *dst, const integerPart *src, + integerPart multiplier, integerPart carry, + unsigned int srcParts, unsigned int dstParts, + bool add) +{ + unsigned int i, n; + + /* Otherwise our writes of DST kill our later reads of SRC. */ + assert(dst <= src || dst >= src + srcParts); + assert(dstParts <= srcParts + 1); + + /* N loops; minimum of dstParts and srcParts. */ + n = dstParts < srcParts ? dstParts: srcParts; + + for(i = 0; i < n; i++) { + integerPart low, mid, high, srcPart; + + /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. + + This cannot overflow, because + + (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) + + which is less than n^2. */ + + srcPart = src[i]; + + if (multiplier == 0 || srcPart == 0) { + low = carry; + high = 0; + } else { + low = lowHalf(srcPart) * lowHalf(multiplier); + high = highHalf(srcPart) * highHalf(multiplier); + + mid = lowHalf(srcPart) * highHalf(multiplier); + high += highHalf(mid); + mid <<= integerPartWidth / 2; + if (low + mid < low) + high++; + low += mid; + + mid = highHalf(srcPart) * lowHalf(multiplier); + high += highHalf(mid); + mid <<= integerPartWidth / 2; + if (low + mid < low) + high++; + low += mid; + + /* Now add carry. */ + if (low + carry < low) + high++; + low += carry; + } + + if (add) { + /* And now DST[i], and store the new low part there. */ + if (low + dst[i] < low) + high++; + dst[i] += low; + } else + dst[i] = low; + + carry = high; + } + + if (i < dstParts) { + /* Full multiplication, there is no overflow. */ + assert(i + 1 == dstParts); + dst[i] = carry; + return 0; + } else { + /* We overflowed if there is carry. */ + if (carry) + return 1; + + /* We would overflow if any significant unwritten parts would be + non-zero. This is true if any remaining src parts are non-zero + and the multiplier is non-zero. */ + if (multiplier) + for(; i < srcParts; i++) + if (src[i]) + return 1; + + /* We fitted in the narrow destination. */ + return 0; + } +} + +/* DST = LHS * RHS, where DST has the same width as the operands and + is filled with the least significant parts of the result. Returns + one if overflow occurred, otherwise zero. DST must be disjoint + from both operands. */ +int +APInt::tcMultiply(integerPart *dst, const integerPart *lhs, + const integerPart *rhs, unsigned int parts) +{ + unsigned int i; + int overflow; + + assert(dst != lhs && dst != rhs); + + overflow = 0; + tcSet(dst, 0, parts); + + for(i = 0; i < parts; i++) + overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, + parts - i, true); + + return overflow; +} + +/* DST = LHS * RHS, where DST has width the sum of the widths of the + operands. No overflow occurs. DST must be disjoint from both + operands. Returns the number of parts required to hold the + result. */ +unsigned int +APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, + const integerPart *rhs, unsigned int lhsParts, + unsigned int rhsParts) +{ + /* Put the narrower number on the LHS for less loops below. */ + if (lhsParts > rhsParts) { + return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); + } else { + unsigned int n; + + assert(dst != lhs && dst != rhs); + + tcSet(dst, 0, rhsParts); + + for(n = 0; n < lhsParts; n++) + tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); + + n = lhsParts + rhsParts; + + return n - (dst[n - 1] == 0); + } +} + +/* If RHS is zero LHS and REMAINDER are left unchanged, return one. + Otherwise set LHS to LHS / RHS with the fractional part discarded, + set REMAINDER to the remainder, return zero. i.e. + + OLD_LHS = RHS * LHS + REMAINDER + + SCRATCH is a bignum of the same size as the operands and result for + use by the routine; its contents need not be initialized and are + destroyed. LHS, REMAINDER and SCRATCH must be distinct. +*/ +int +APInt::tcDivide(integerPart *lhs, const integerPart *rhs, + integerPart *remainder, integerPart *srhs, + unsigned int parts) +{ + unsigned int n, shiftCount; + integerPart mask; + + assert(lhs != remainder && lhs != srhs && remainder != srhs); + + shiftCount = tcMSB(rhs, parts) + 1; + if (shiftCount == 0) + return true; + + shiftCount = parts * integerPartWidth - shiftCount; + n = shiftCount / integerPartWidth; + mask = (integerPart) 1 << (shiftCount % integerPartWidth); + + tcAssign(srhs, rhs, parts); + tcShiftLeft(srhs, parts, shiftCount); + tcAssign(remainder, lhs, parts); + tcSet(lhs, 0, parts); + + /* Loop, subtracting SRHS if REMAINDER is greater and adding that to + the total. */ + for(;;) { + int compare; + + compare = tcCompare(remainder, srhs, parts); + if (compare >= 0) { + tcSubtract(remainder, srhs, 0, parts); + lhs[n] |= mask; + } + + if (shiftCount == 0) + break; + shiftCount--; + tcShiftRight(srhs, parts, 1); + if ((mask >>= 1) == 0) + mask = (integerPart) 1 << (integerPartWidth - 1), n--; + } + + return false; +} + +/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. + There are no restrictions on COUNT. */ +void +APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) +{ + if (count) { + unsigned int jump, shift; + + /* Jump is the inter-part jump; shift is is intra-part shift. */ + jump = count / integerPartWidth; + shift = count % integerPartWidth; + + while (parts > jump) { + integerPart part; + + parts--; + + /* dst[i] comes from the two parts src[i - jump] and, if we have + an intra-part shift, src[i - jump - 1]. */ + part = dst[parts - jump]; + if (shift) { + part <<= shift; + if (parts >= jump + 1) + part |= dst[parts - jump - 1] >> (integerPartWidth - shift); + } + + dst[parts] = part; + } + + while (parts > 0) + dst[--parts] = 0; + } +} + +/* Shift a bignum right COUNT bits in-place. Shifted in bits are + zero. There are no restrictions on COUNT. */ +void +APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) +{ + if (count) { + unsigned int i, jump, shift; + + /* Jump is the inter-part jump; shift is is intra-part shift. */ + jump = count / integerPartWidth; + shift = count % integerPartWidth; + + /* Perform the shift. This leaves the most significant COUNT bits + of the result at zero. */ + for(i = 0; i < parts; i++) { + integerPart part; + + if (i + jump >= parts) { + part = 0; + } else { + part = dst[i + jump]; + if (shift) { + part >>= shift; + if (i + jump + 1 < parts) + part |= dst[i + jump + 1] << (integerPartWidth - shift); + } + } + + dst[i] = part; + } + } +} + +/* Bitwise and of two bignums. */ +void +APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + dst[i] &= rhs[i]; +} + +/* Bitwise inclusive or of two bignums. */ +void +APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + dst[i] |= rhs[i]; +} + +/* Bitwise exclusive or of two bignums. */ +void +APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + dst[i] ^= rhs[i]; +} + +/* Complement a bignum in-place. */ +void +APInt::tcComplement(integerPart *dst, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + dst[i] = ~dst[i]; +} + +/* Comparison (unsigned) of two bignums. */ +int +APInt::tcCompare(const integerPart *lhs, const integerPart *rhs, + unsigned int parts) +{ + while (parts) { + parts--; + if (lhs[parts] == rhs[parts]) + continue; + + if (lhs[parts] > rhs[parts]) + return 1; + else + return -1; + } + + return 0; +} + +/* Increment a bignum in-place, return the carry flag. */ +integerPart +APInt::tcIncrement(integerPart *dst, unsigned int parts) +{ + unsigned int i; + + for(i = 0; i < parts; i++) + if (++dst[i] != 0) + break; + + return i == parts; +} + +/* Set the least significant BITS bits of a bignum, clear the + rest. */ +void +APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, + unsigned int bits) +{ + unsigned int i; + + i = 0; + while (bits > integerPartWidth) { + dst[i++] = ~(integerPart) 0; + bits -= integerPartWidth; + } + + if (bits) + dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); + + while (i < parts) + dst[i++] = 0; } -#endif