From 610fad85d2dcc1b65227f67ae3c86db1d921a4d0 Mon Sep 17 00:00:00 2001 From: Reid Spencer Date: Sat, 24 Feb 2007 10:01:42 +0000 Subject: [PATCH] 1. Fix last bug in KnuthDiv. All divide tests pass up to 1024 bits now. 2. Clean up comments, style, coding standards, etc. 3. Simplify a constructor. Extended testing revealed some additional bugs in shifting. I'll fix these tomorrow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34559 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/APInt.cpp | 118 +++++++++++++++++++++++--------------------------- 1 file changed, 55 insertions(+), 63 deletions(-) diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index c3b3d9d233f..63bc5f55b3e 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -2,8 +2,9 @@ // // 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 was developed by Sheng Zhou and Reid Spencer and is distributed +// under the // University of Illinois Open Source License. See LICENSE.TXT +// for details. // //===----------------------------------------------------------------------===// // @@ -20,14 +21,13 @@ #include #include #ifndef NDEBUG -#include #include #endif using namespace llvm; // A utility function for allocating memory, checking for allocation failures, -// and ensuring the contents is zeroed. +// and ensuring the contents are zeroed. inline static uint64_t* getClearedMemory(uint32_t numWords) { uint64_t * result = new uint64_t[numWords]; assert(result && "APInt memory allocation fails!"); @@ -36,6 +36,7 @@ inline static uint64_t* getClearedMemory(uint32_t numWords) { } // A utility function for allocating memory and checking for allocation failure. +// The content is not zero'd inline static uint64_t* getMemory(uint32_t numWords) { uint64_t * result = new uint64_t[numWords]; assert(result && "APInt memory allocation fails!"); @@ -60,38 +61,31 @@ APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]) assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large"); assert(bigVal && "Null pointer detected!"); if (isSingleWord()) - VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitWidth)); + VAL = bigVal[0]; else { - pVal = getMemory(getNumWords()); - // Calculate the actual length of bigVal[]. - uint32_t maxN = std::max(numWords, getNumWords()); - uint32_t minN = std::min(numWords, getNumWords()); - memcpy(pVal, bigVal, (minN - 1) * APINT_WORD_SIZE); - pVal[minN-1] = bigVal[minN-1] & - (~uint64_t(0ULL) >> - (APINT_BITS_PER_WORD - BitWidth % APINT_BITS_PER_WORD)); - if (maxN == getNumWords()) - memset(pVal+numWords, 0, (getNumWords() - numWords) * APINT_WORD_SIZE); + // Get memory, cleared to 0 + pVal = getClearedMemory(getNumWords()); + // Calculate the number of words to copy + uint32_t words = std::min(numWords, getNumWords()); + // Copy the words from bigVal to pVal + memcpy(pVal, bigVal, words * APINT_WORD_SIZE); } + // Make sure unused high bits are cleared + clearUnusedBits(); } -/// @brief Create a new APInt by translating the char array represented -/// integer value. APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen, uint8_t radix) : BitWidth(numbits), VAL(0) { fromString(numbits, StrStart, slen, radix); } -/// @brief Create a new APInt by translating the string represented -/// integer value. APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix) : BitWidth(numbits), VAL(0) { assert(!Val.empty() && "String empty?"); fromString(numbits, Val.c_str(), Val.size(), radix); } -/// @brief Copy constructor APInt::APInt(const APInt& that) : BitWidth(that.BitWidth), VAL(0) { if (isSingleWord()) @@ -107,8 +101,6 @@ APInt::~APInt() { delete[] pVal; } -/// @brief Copy assignment operator. Create a new object from the given -/// APInt one by initialization. APInt& APInt::operator=(const APInt& RHS) { assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); if (isSingleWord()) @@ -118,8 +110,6 @@ APInt& APInt::operator=(const APInt& RHS) { return *this; } -/// @brief Assignment operator. Assigns a common case integer value to -/// the APInt. APInt& APInt::operator=(uint64_t RHS) { if (isSingleWord()) VAL = RHS; @@ -134,15 +124,13 @@ APInt& APInt::operator=(uint64_t RHS) { /// "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 uint64_t add_1(uint64_t dest[], - uint64_t x[], uint32_t len, - uint64_t y) { +static uint64_t add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { for (uint32_t i = 0; i < len; ++i) { dest[i] = y + x[i]; if (dest[i] < y) - y = 1; + y = 1; // Carry one to next digit. else { - y = 0; + y = 0; // No need to carry so exit early break; } } @@ -216,7 +204,7 @@ APInt& APInt::operator+=(const APInt& RHS) { } /// sub - This function subtracts the integer array x[] by -/// integer array y[], and returns the borrow-out carry. +/// integer array y[], and returns the borrow-out. static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, uint32_t len) { bool borrow = false; @@ -243,10 +231,8 @@ APInt& APInt::operator-=(const APInt& RHS) { /// mul_1 - This function performs the multiplication operation on a /// large integer (represented as an integer array) and a uint64_t integer. /// @returns the carry of the multiplication. -static uint64_t mul_1(uint64_t dest[], - uint64_t x[], uint32_t len, - uint64_t y) { - // Split y into high 32-bit part and low 32-bit part. +static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t 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, lx, hx; for (uint32_t i = 0; i < len; ++i) { @@ -277,10 +263,9 @@ static uint64_t mul_1(uint64_t dest[], /// mul - This function multiplies integer array x[] by integer array y[] and /// stores the result into integer array dest[]. /// Note the array dest[]'s size should no less than xlen + ylen. -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[], uint32_t xlen, uint64_t y[], + uint32_t ylen) { dest[xlen] = mul_1(dest, x, xlen, y[0]); - for (uint32_t i = 1; i < ylen; ++i) { uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; uint64_t carry = 0, lx = 0, hx = 0; @@ -1053,43 +1038,50 @@ static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { qp--; rp += v[n-1]; - if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) { + if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) qp--; - //rp += v[n-1]; - } } DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation // consists of a simple multiplication by a one-place number, combined with - // a subtraction. The digits (u[j+n]...u[j]) should be kept positive; - bool borrow = false; + // a subtraction. + bool isNegative = false; for (uint32_t i = 0; i < n; ++i) { - uint64_t u_tmp = borrow ? uint64_t(u[j+i] - 1) : uint64_t(u[j+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; DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp - << ", subtrahend == " << subtrahend << '\n'); - - borrow = subtrahend > u_tmp || (borrow && u[j+i] == 0); - u[j+i] = u_tmp - subtrahend; - } - if (borrow) { - borrow = u[j+n] == 0; // Was result negative? - u[j+n]--; // handle the borrow + << ", subtrahend == " << subtrahend + << ", 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 + while (borrow && k <= m+n) { // deal with borrow to the left + borrow = u[k] == 0; + u[k]--; + k++; + } + isNegative |= borrow; + DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << + u[j+i+1] << '\n'); } DEBUG(cerr << "KnuthDiv: after subtraction:"); DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]); DEBUG(cerr << '\n'); - // if the result of this step is actually negative, (u[j+n]...u[j]) should - // be left as the true value plus b**(n+1), namely as the b's complement of + // The digits (u[j+n]...u[j]) should be kept positive; if the result of + // this step is actually negative, (u[j+n]...u[j]) should be left as the + // true value plus b**(n+1), namely as the b's complement of // the true value, and a "borrow" to the left should be remembered. // - if (borrow) { - bool carry = true; - for (uint32_t i = 0; i <= n; ++i) { - u[j+i] = ~u[j+i] + carry; // b's complement - carry = u[j+i] == 0; + if (isNegative) { + bool carry = true; // true because b's complement is "complement + 1" + for (uint32_t i = 0; i <= m+n; ++i) { + u[i] = ~u[i] + carry; // b's complement + carry = carry && u[i] == 0; } } DEBUG(cerr << "KnuthDiv: after complement:"); @@ -1099,7 +1091,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; - if (borrow) { + if (isNegative) { // 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 // this possibility. Decrease q[j] by 1 @@ -1516,12 +1508,12 @@ std::string APInt::toString(uint8_t radix, bool wantSigned) const { #ifndef NDEBUG void APInt::dump() const { - std::cerr << "APInt(" << BitWidth << ")=" << std::setbase(16); + cerr << "APInt(" << BitWidth << ")=" << std::setbase(16); if (isSingleWord()) - std::cerr << VAL; + cerr << VAL; else for (unsigned i = getNumWords(); i > 0; i--) { - std::cerr << pVal[i-1] << " "; + cerr << pVal[i-1] << " "; } - std::cerr << " (" << this->toString(10, false) << ")\n" << std::setbase(10); + cerr << " (" << this->toString(10, false) << ")\n" << std::setbase(10); } #endif -- 2.11.0