X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=38b379005af0f77a910b5ba3accc4b82f37555f4;hb=ebb5a971d903aa4479bb2a21472597319a9b0086;hp=267aaf81d449bf8dd0cb186a3ed0eaf66d442547;hpb=20a4c23bcc958cbc3ce9775b440d205ac0944db8;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 267aaf81d44..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,19 +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) { @@ -46,8 +53,8 @@ inline static uint64_t* getMemory(uint32_t numWords) { 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 { @@ -60,10 +67,10 @@ APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned) 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]; @@ -82,23 +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 >= 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"); 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(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 >= 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 = that.VAL; else { @@ -158,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. @@ -747,7 +768,7 @@ uint32_t APInt::countLeadingZeros() const { uint32_t 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) { @@ -784,14 +805,26 @@ uint32_t APInt::countLeadingOnes() const { 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 { @@ -872,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; } @@ -945,7 +978,7 @@ double APInt::roundToDouble(bool isSigned) const { // Truncate to new 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(); @@ -968,7 +1001,7 @@ APInt &APInt::trunc(uint32_t width) { // Sign extend to a new 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); @@ -1016,7 +1049,7 @@ APInt &APInt::sext(uint32_t width) { // Zero extend to a new 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(); @@ -1050,6 +1083,12 @@ APInt &APInt::sextOrTrunc(uint32_t 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 { @@ -1074,7 +1113,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); } @@ -1133,6 +1172,12 @@ APInt APInt::ashr(uint32_t shiftAmt) const { 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 { @@ -1195,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 { @@ -1254,6 +1306,10 @@ 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; @@ -1265,6 +1321,10 @@ APInt APInt::rotl(uint32_t rotateAmt) const { 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; @@ -1457,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]--; @@ -1489,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 @@ -1585,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. @@ -1594,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 @@ -1631,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) @@ -1880,6 +1940,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"); } @@ -1907,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; @@ -1927,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; @@ -1962,7 +2026,8 @@ std::string APInt::toString(uint8_t radix, bool wantSigned) const { uint64_t mask = radix - 1; APInt zero(tmp.getBitWidth(), 0); while (tmp.ne(zero)) { - unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask; + unsigned digit = + (unsigned)((tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask); result.insert(insert_at, digits[digit]); tmp = tmp.lshr(shift); } @@ -1983,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; @@ -1999,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); @@ -2008,7 +2072,642 @@ void APInt::dump() const else for (unsigned i = getNumWords(); i > 0; i--) { cerr << pVal[i-1] << " "; } - cerr << " U(" << this->toString(10) << ") S(" << this->toStringSigned(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