X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=1cabe0f03e7136044646f70fad34637a7a00dc7a;hb=de551f91d8816632a76a065084caab9fab6aacff;hp=277a0b0c113c35b187b971b63b3bec286a2db164;hpb=9132a2b81842b0e2b77703fab3e6fe7467f859bb;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 277a0b0c113..1cabe0f03e7 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,62 +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 >= IntegerType::MIN_INT_BITS && "bitwidth too small"); - assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); + 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(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 { - 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; @@ -158,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. @@ -190,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) @@ -218,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); @@ -245,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]; @@ -271,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; @@ -305,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. @@ -344,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(); @@ -360,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 @@ -368,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 @@ -382,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; } @@ -394,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; } @@ -407,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. @@ -455,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; @@ -488,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) @@ -517,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 @@ -534,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) @@ -550,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; @@ -596,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 @@ -604,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(); ++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 @@ -627,50 +574,24 @@ 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; } -uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) { +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 - uint32_t isNegative = str[0] == '-'; + unsigned isNegative = str[0] == '-'; if (isNegative) { slen--; str++; @@ -693,7 +614,7 @@ uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) { // 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; + unsigned sufficient = slen*64/18; // Convert to the actual binary value. APInt tmp(sufficient, str, slen, radix); @@ -702,26 +623,104 @@ uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) { return isNegative + tmp.logBase2() + 1; } -uint64_t APInt::getHashValue() const { - // Put the bit width into the low order bits. - uint64_t hash = BitWidth; +// From http://www.burtleburtle.net, byBob Jenkins. +// When targeting x86, both GCC and LLVM seem to recognize this as a +// rotate instruction. +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +// From http://www.burtleburtle.net, by Bob Jenkins. +#define mix(a,b,c) \ + { \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ + } + +// From http://www.burtleburtle.net, by Bob Jenkins. +#define final(a,b,c) \ + { \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ + } + +// hashword() was adapted from http://www.burtleburtle.net, by Bob +// Jenkins. k is a pointer to an array of uint32_t values; length is +// the length of the key, in 32-bit chunks. This version only handles +// keys that are a multiple of 32 bits in size. +static inline uint32_t hashword(const uint64_t *k64, size_t length) +{ + const uint32_t *k = reinterpret_cast(k64); + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length)<<2); + + /*------------------------------------------------- handle most of the key */ + while (length > 3) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch(length) /* all the case statements fall through */ + { + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} - // Add the sum of the words to the hash. +// hashword8() was adapted from http://www.burtleburtle.net, by Bob +// Jenkins. This computes a 32-bit hash from one 64-bit word. When +// targeting x86 (32 or 64 bit), both LLVM and GCC compile this +// function into about 35 instructions when inlined. +static inline uint32_t hashword8(const uint64_t k64) +{ + uint32_t a,b,c; + a = b = c = 0xdeadbeef + 4; + b += k64 >> 32; + a += k64 & 0xffffffff; + final(a,b,c); + return c; +} +#undef final +#undef mix +#undef rot + +uint64_t APInt::getHashValue() const { + uint64_t hash; if (isSingleWord()) - hash += VAL << 6; // clear separation of up to 64 bits + hash = hashword8(VAL); else - for (uint32_t i = 0; i < getNumWords(); ++i) - hash += pVal[i] << 6; // clear sepration of up to 64 bits + hash = hashword(pVal, getNumWords()*2); 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); } @@ -730,28 +729,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))) { @@ -761,14 +756,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) @@ -782,23 +783,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; } @@ -808,9 +817,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); @@ -820,7 +829,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; @@ -840,7 +849,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; @@ -872,7 +881,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; } @@ -901,7 +910,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 @@ -943,12 +952,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; @@ -956,7 +965,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; @@ -966,9 +975,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); @@ -976,14 +984,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) @@ -1001,11 +1009,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; @@ -1014,18 +1022,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; @@ -1034,7 +1041,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) @@ -1042,7 +1049,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) @@ -1052,7 +1059,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) @@ -1063,7 +1076,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)); } @@ -1074,7 +1087,7 @@ APInt APInt::ashr(uint32_t shiftAmt) const { // issues in the algorithm below. if (shiftAmt == BitWidth) { if (isNegative()) - return APInt(BitWidth, -1ULL); + return APInt(BitWidth, -1ULL, true); else return APInt(BitWidth, 0); } @@ -1083,17 +1096,17 @@ APInt APInt::ashr(uint32_t shiftAmt) const { 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 @@ -1102,7 +1115,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) | @@ -1128,14 +1141,20 @@ APInt APInt::ashr(uint32_t shiftAmt) const { // 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 { +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); @@ -1150,7 +1169,7 @@ APInt APInt::lshr(uint32_t shiftAmt) const { 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 + // 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; @@ -1169,42 +1188,40 @@ 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. @@ -1223,7 +1240,7 @@ APInt APInt::shl(uint32_t shiftAmt) const { // 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); } @@ -1231,20 +1248,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); @@ -1254,7 +1271,11 @@ APInt APInt::shl(uint32_t shiftAmt) const { return APInt(val, BitWidth).clearUnusedBits(); } -APInt APInt::rotl(uint32_t rotateAmt) const { +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 @@ -1265,7 +1286,11 @@ APInt APInt::rotl(uint32_t rotateAmt) const { return hi | lo; } -APInt APInt::rotr(uint32_t rotateAmt) const { +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 @@ -1286,7 +1311,7 @@ APInt APInt::rotr(uint32_t rotateAmt) 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. @@ -1323,7 +1348,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); @@ -1366,12 +1391,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"); @@ -1382,12 +1451,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 @@ -1396,27 +1467,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; @@ -1447,7 +1520,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; @@ -1456,9 +1529,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]--; @@ -1478,7 +1551,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; } @@ -1489,7 +1562,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 @@ -1499,8 +1572,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); } @@ -1525,7 +1598,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; @@ -1540,11 +1613,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"); @@ -1554,19 +1629,19 @@ void APInt::divide(const APInt LHS, uint32_t lhsWords, // and the the Knuth "classical algorithm" which requires there to be native // operations for +, -, and * on an m bit value with an m*2 bit result. We // 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 + // 128-bits. Furthermore, 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)*CHAR_BIT); + 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]; @@ -1574,34 +1649,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)*CHAR_BIT)); } 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)*CHAR_BIT)); } // 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 @@ -1622,8 +1697,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) { @@ -1631,13 +1706,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) @@ -1729,11 +1804,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) @@ -1764,12 +1839,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 @@ -1796,10 +1871,10 @@ APInt APInt::urem(const APInt& RHS) const { 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); + 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) { @@ -1822,13 +1897,10 @@ void APInt::udivrem(const APInt &LHS, const APInt &RHS, 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]); - } + 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; } @@ -1836,7 +1908,7 @@ void APInt::udivrem(const APInt &LHS, const APInt &RHS, divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); } -void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, +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) && @@ -1855,7 +1927,7 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, 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. @@ -1865,7 +1937,7 @@ 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 (radix == 16) { if (!isxdigit(cdigit)) @@ -1880,6 +1952,10 @@ void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, 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"); } @@ -1904,120 +1980,117 @@ 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) { - // 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); - } + + 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(); } -#ifndef NDEBUG -void APInt::dump() const -{ - cerr << "APInt(" << BitWidth << ")=" << std::setbase(16); - if (isSingleWord()) - cerr << VAL; - else for (unsigned i = getNumWords(); i > 0; i--) { - cerr << pVal[i-1] << " "; - } - cerr << " U(" << this->toStringUnsigned(10) << ") S(" - << this->toStringSigned(10) << ")\n" << std::setbase(10); + +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(); } -#endif // 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. */ @@ -2025,7 +2098,7 @@ namespace { /* Returns the integer part with the least significant BITS set. BITS cannot be zero. */ - inline integerPart + static inline integerPart lowBitMask(unsigned int bits) { assert (bits != 0 && bits <= integerPartWidth); @@ -2033,23 +2106,23 @@ namespace { return ~(integerPart) 0 >> (integerPartWidth - bits); } - /* Returns the value of the lower nibble of PART. */ - inline integerPart + /* 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 nibble of PART. */ - inline integerPart + /* 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 bit of a part. If - the input number has no bits set -1U is returned. */ - unsigned int + /* 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; @@ -2072,9 +2145,9 @@ namespace { return msb; } - /* Returns the bit number of the least significant bit of a part. - If the input number has no bits set -1U is returned. */ - unsigned int + /* 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; @@ -2105,6 +2178,8 @@ APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) { unsigned int i; + assert (parts > 0); + dst[0] = part; for(i = 1; i < parts; i++) dst[i] = 0; @@ -2148,8 +2223,8 @@ APInt::tcSetBit(integerPart *parts, unsigned int bit) parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); } -/* Returns the bit number of the least significant bit of a number. - If the input number has no bits set -1U is returned. */ +/* 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) { @@ -2166,8 +2241,8 @@ APInt::tcLSB(const integerPart *parts, unsigned int n) return -1U; } -/* Returns the bit number of the most significant bit of a number. If - the input number has no bits set -1U is returned. */ +/* 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) { @@ -2186,6 +2261,43 @@ APInt::tcMSB(const integerPart *parts, unsigned int 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, @@ -2244,8 +2356,8 @@ APInt::tcNegate(integerPart *dst, unsigned int parts) tcIncrement(dst, parts); } -/* DST += SRC * MULTIPLIER + PART if add is true - DST = SRC * MULTIPLIER + PART if add is false +/* 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. @@ -2367,25 +2479,32 @@ APInt::tcMultiply(integerPart *dst, const integerPart *lhs, return overflow; } -/* DST = LHS * RHS, where DST has twice the width as the operands. No - overflow occurs. DST must be disjoint from both operands. */ -void +/* 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 parts) + const integerPart *rhs, unsigned int lhsParts, + unsigned int rhsParts) { - unsigned int i; - int overflow; + /* 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); + assert(dst != lhs && dst != rhs); - overflow = 0; - tcSet(dst, 0, parts); + tcSet(dst, 0, rhsParts); - for(i = 0; i < parts; i++) - overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, - parts + 1, true); + for(n = 0; n < lhsParts; n++) + tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); + + n = lhsParts + rhsParts; - assert(!overflow); + return n - (dst[n - 1] == 0); + } } /* If RHS is zero LHS and REMAINDER are left unchanged, return one. @@ -2448,31 +2567,33 @@ APInt::tcDivide(integerPart *lhs, const integerPart *rhs, void APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) { - unsigned int jump, shift; + if (count) { + unsigned int jump, shift; - /* Jump is the inter-part jump; shift is is intra-part shift. */ - jump = count / integerPartWidth; - shift = count % integerPartWidth; + /* Jump is the inter-part jump; shift is is intra-part shift. */ + jump = count / integerPartWidth; + shift = count % integerPartWidth; - while (parts > jump) { - integerPart part; + while (parts > jump) { + integerPart part; - parts--; + 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; + /* 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; - } + dst[parts] = part; + } - while (parts > 0) - dst[--parts] = 0; + while (parts > 0) + dst[--parts] = 0; + } } /* Shift a bignum right COUNT bits in-place. Shifted in bits are @@ -2480,29 +2601,31 @@ APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) void APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) { - unsigned int i, jump, shift; + 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; + /* 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; + /* 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); + 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; + dst[i] = part; + } } }