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