LLVM API Documentation

APInt.cpp
Go to the documentation of this file.
00001 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a class to represent arbitrary precision integer
00011 // constant values and provide a variety of arithmetic operations on them.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "apint"
00016 #include "llvm/ADT/APInt.h"
00017 #include "llvm/ADT/FoldingSet.h"
00018 #include "llvm/ADT/Hashing.h"
00019 #include "llvm/ADT/SmallString.h"
00020 #include "llvm/ADT/StringRef.h"
00021 #include "llvm/Support/Debug.h"
00022 #include "llvm/Support/ErrorHandling.h"
00023 #include "llvm/Support/MathExtras.h"
00024 #include "llvm/Support/raw_ostream.h"
00025 #include <cmath>
00026 #include <cstdlib>
00027 #include <cstring>
00028 #include <limits>
00029 using namespace llvm;
00030 
00031 /// A utility function for allocating memory, checking for allocation failures,
00032 /// and ensuring the contents are zeroed.
00033 inline static uint64_t* getClearedMemory(unsigned numWords) {
00034   uint64_t * result = new uint64_t[numWords];
00035   assert(result && "APInt memory allocation fails!");
00036   memset(result, 0, numWords * sizeof(uint64_t));
00037   return result;
00038 }
00039 
00040 /// A utility function for allocating memory and checking for allocation
00041 /// failure.  The content is not zeroed.
00042 inline static uint64_t* getMemory(unsigned numWords) {
00043   uint64_t * result = new uint64_t[numWords];
00044   assert(result && "APInt memory allocation fails!");
00045   return result;
00046 }
00047 
00048 /// A utility function that converts a character to a digit.
00049 inline static unsigned getDigit(char cdigit, uint8_t radix) {
00050   unsigned r;
00051 
00052   if (radix == 16 || radix == 36) {
00053     r = cdigit - '0';
00054     if (r <= 9)
00055       return r;
00056 
00057     r = cdigit - 'A';
00058     if (r <= radix - 11U)
00059       return r + 10;
00060 
00061     r = cdigit - 'a';
00062     if (r <= radix - 11U)
00063       return r + 10;
00064     
00065     radix = 10;
00066   }
00067 
00068   r = cdigit - '0';
00069   if (r < radix)
00070     return r;
00071 
00072   return -1U;
00073 }
00074 
00075 
00076 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
00077   pVal = getClearedMemory(getNumWords());
00078   pVal[0] = val;
00079   if (isSigned && int64_t(val) < 0)
00080     for (unsigned i = 1; i < getNumWords(); ++i)
00081       pVal[i] = -1ULL;
00082 }
00083 
00084 void APInt::initSlowCase(const APInt& that) {
00085   pVal = getMemory(getNumWords());
00086   memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
00087 }
00088 
00089 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
00090   assert(BitWidth && "Bitwidth too small");
00091   assert(bigVal.data() && "Null pointer detected!");
00092   if (isSingleWord())
00093     VAL = bigVal[0];
00094   else {
00095     // Get memory, cleared to 0
00096     pVal = getClearedMemory(getNumWords());
00097     // Calculate the number of words to copy
00098     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
00099     // Copy the words from bigVal to pVal
00100     memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
00101   }
00102   // Make sure unused high bits are cleared
00103   clearUnusedBits();
00104 }
00105 
00106 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
00107   : BitWidth(numBits), VAL(0) {
00108   initFromArray(bigVal);
00109 }
00110 
00111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
00112   : BitWidth(numBits), VAL(0) {
00113   initFromArray(makeArrayRef(bigVal, numWords));
00114 }
00115 
00116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
00117   : BitWidth(numbits), VAL(0) {
00118   assert(BitWidth && "Bitwidth too small");
00119   fromString(numbits, Str, radix);
00120 }
00121 
00122 APInt& APInt::AssignSlowCase(const APInt& RHS) {
00123   // Don't do anything for X = X
00124   if (this == &RHS)
00125     return *this;
00126 
00127   if (BitWidth == RHS.getBitWidth()) {
00128     // assume same bit-width single-word case is already handled
00129     assert(!isSingleWord());
00130     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
00131     return *this;
00132   }
00133 
00134   if (isSingleWord()) {
00135     // assume case where both are single words is already handled
00136     assert(!RHS.isSingleWord());
00137     VAL = 0;
00138     pVal = getMemory(RHS.getNumWords());
00139     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
00140   } else if (getNumWords() == RHS.getNumWords())
00141     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
00142   else if (RHS.isSingleWord()) {
00143     delete [] pVal;
00144     VAL = RHS.VAL;
00145   } else {
00146     delete [] pVal;
00147     pVal = getMemory(RHS.getNumWords());
00148     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
00149   }
00150   BitWidth = RHS.BitWidth;
00151   return clearUnusedBits();
00152 }
00153 
00154 APInt& APInt::operator=(uint64_t RHS) {
00155   if (isSingleWord())
00156     VAL = RHS;
00157   else {
00158     pVal[0] = RHS;
00159     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
00160   }
00161   return clearUnusedBits();
00162 }
00163 
00164 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
00165 void APInt::Profile(FoldingSetNodeID& ID) const {
00166   ID.AddInteger(BitWidth);
00167 
00168   if (isSingleWord()) {
00169     ID.AddInteger(VAL);
00170     return;
00171   }
00172 
00173   unsigned NumWords = getNumWords();
00174   for (unsigned i = 0; i < NumWords; ++i)
00175     ID.AddInteger(pVal[i]);
00176 }
00177 
00178 /// add_1 - This function adds a single "digit" integer, y, to the multiple
00179 /// "digit" integer array,  x[]. x[] is modified to reflect the addition and
00180 /// 1 is returned if there is a carry out, otherwise 0 is returned.
00181 /// @returns the carry of the addition.
00182 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
00183   for (unsigned i = 0; i < len; ++i) {
00184     dest[i] = y + x[i];
00185     if (dest[i] < y)
00186       y = 1; // Carry one to next digit.
00187     else {
00188       y = 0; // No need to carry so exit early
00189       break;
00190     }
00191   }
00192   return y;
00193 }
00194 
00195 /// @brief Prefix increment operator. Increments the APInt by one.
00196 APInt& APInt::operator++() {
00197   if (isSingleWord())
00198     ++VAL;
00199   else
00200     add_1(pVal, pVal, getNumWords(), 1);
00201   return clearUnusedBits();
00202 }
00203 
00204 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
00205 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
00206 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
00207 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
00208 /// In other words, if y > x then this function returns 1, otherwise 0.
00209 /// @returns the borrow out of the subtraction
00210 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
00211   for (unsigned i = 0; i < len; ++i) {
00212     uint64_t X = x[i];
00213     x[i] -= y;
00214     if (y > X)
00215       y = 1;  // We have to "borrow 1" from next "digit"
00216     else {
00217       y = 0;  // No need to borrow
00218       break;  // Remaining digits are unchanged so exit early
00219     }
00220   }
00221   return bool(y);
00222 }
00223 
00224 /// @brief Prefix decrement operator. Decrements the APInt by one.
00225 APInt& APInt::operator--() {
00226   if (isSingleWord())
00227     --VAL;
00228   else
00229     sub_1(pVal, getNumWords(), 1);
00230   return clearUnusedBits();
00231 }
00232 
00233 /// add - This function adds the integer array x to the integer array Y and
00234 /// places the result in dest.
00235 /// @returns the carry out from the addition
00236 /// @brief General addition of 64-bit integer arrays
00237 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
00238                 unsigned len) {
00239   bool carry = false;
00240   for (unsigned i = 0; i< len; ++i) {
00241     uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
00242     dest[i] = x[i] + y[i] + carry;
00243     carry = dest[i] < limit || (carry && dest[i] == limit);
00244   }
00245   return carry;
00246 }
00247 
00248 /// Adds the RHS APint to this APInt.
00249 /// @returns this, after addition of RHS.
00250 /// @brief Addition assignment operator.
00251 APInt& APInt::operator+=(const APInt& RHS) {
00252   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00253   if (isSingleWord())
00254     VAL += RHS.VAL;
00255   else {
00256     add(pVal, pVal, RHS.pVal, getNumWords());
00257   }
00258   return clearUnusedBits();
00259 }
00260 
00261 /// Subtracts the integer array y from the integer array x
00262 /// @returns returns the borrow out.
00263 /// @brief Generalized subtraction of 64-bit integer arrays.
00264 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
00265                 unsigned len) {
00266   bool borrow = false;
00267   for (unsigned i = 0; i < len; ++i) {
00268     uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
00269     borrow = y[i] > x_tmp || (borrow && x[i] == 0);
00270     dest[i] = x_tmp - y[i];
00271   }
00272   return borrow;
00273 }
00274 
00275 /// Subtracts the RHS APInt from this APInt
00276 /// @returns this, after subtraction
00277 /// @brief Subtraction assignment operator.
00278 APInt& APInt::operator-=(const APInt& RHS) {
00279   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00280   if (isSingleWord())
00281     VAL -= RHS.VAL;
00282   else
00283     sub(pVal, pVal, RHS.pVal, getNumWords());
00284   return clearUnusedBits();
00285 }
00286 
00287 /// Multiplies an integer array, x, by a uint64_t integer and places the result
00288 /// into dest.
00289 /// @returns the carry out of the multiplication.
00290 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
00291 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
00292   // Split y into high 32-bit part (hy)  and low 32-bit part (ly)
00293   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
00294   uint64_t carry = 0;
00295 
00296   // For each digit of x.
00297   for (unsigned i = 0; i < len; ++i) {
00298     // Split x into high and low words
00299     uint64_t lx = x[i] & 0xffffffffULL;
00300     uint64_t hx = x[i] >> 32;
00301     // hasCarry - A flag to indicate if there is a carry to the next digit.
00302     // hasCarry == 0, no carry
00303     // hasCarry == 1, has carry
00304     // hasCarry == 2, no carry and the calculation result == 0.
00305     uint8_t hasCarry = 0;
00306     dest[i] = carry + lx * ly;
00307     // Determine if the add above introduces carry.
00308     hasCarry = (dest[i] < carry) ? 1 : 0;
00309     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
00310     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
00311     // (2^32 - 1) + 2^32 = 2^64.
00312     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
00313 
00314     carry += (lx * hy) & 0xffffffffULL;
00315     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
00316     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
00317             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
00318   }
00319   return carry;
00320 }
00321 
00322 /// Multiplies integer array x by integer array y and stores the result into
00323 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
00324 /// @brief Generalized multiplicate of integer arrays.
00325 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
00326                 unsigned ylen) {
00327   dest[xlen] = mul_1(dest, x, xlen, y[0]);
00328   for (unsigned i = 1; i < ylen; ++i) {
00329     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
00330     uint64_t carry = 0, lx = 0, hx = 0;
00331     for (unsigned j = 0; j < xlen; ++j) {
00332       lx = x[j] & 0xffffffffULL;
00333       hx = x[j] >> 32;
00334       // hasCarry - A flag to indicate if has carry.
00335       // hasCarry == 0, no carry
00336       // hasCarry == 1, has carry
00337       // hasCarry == 2, no carry and the calculation result == 0.
00338       uint8_t hasCarry = 0;
00339       uint64_t resul = carry + lx * ly;
00340       hasCarry = (resul < carry) ? 1 : 0;
00341       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
00342       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
00343 
00344       carry += (lx * hy) & 0xffffffffULL;
00345       resul = (carry << 32) | (resul & 0xffffffffULL);
00346       dest[i+j] += resul;
00347       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
00348               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
00349               ((lx * hy) >> 32) + hx * hy;
00350     }
00351     dest[i+xlen] = carry;
00352   }
00353 }
00354 
00355 APInt& APInt::operator*=(const APInt& RHS) {
00356   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00357   if (isSingleWord()) {
00358     VAL *= RHS.VAL;
00359     clearUnusedBits();
00360     return *this;
00361   }
00362 
00363   // Get some bit facts about LHS and check for zero
00364   unsigned lhsBits = getActiveBits();
00365   unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
00366   if (!lhsWords)
00367     // 0 * X ===> 0
00368     return *this;
00369 
00370   // Get some bit facts about RHS and check for zero
00371   unsigned rhsBits = RHS.getActiveBits();
00372   unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
00373   if (!rhsWords) {
00374     // X * 0 ===> 0
00375     clearAllBits();
00376     return *this;
00377   }
00378 
00379   // Allocate space for the result
00380   unsigned destWords = rhsWords + lhsWords;
00381   uint64_t *dest = getMemory(destWords);
00382 
00383   // Perform the long multiply
00384   mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
00385 
00386   // Copy result back into *this
00387   clearAllBits();
00388   unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
00389   memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
00390   clearUnusedBits();
00391 
00392   // delete dest array and return
00393   delete[] dest;
00394   return *this;
00395 }
00396 
00397 APInt& APInt::operator&=(const APInt& RHS) {
00398   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00399   if (isSingleWord()) {
00400     VAL &= RHS.VAL;
00401     return *this;
00402   }
00403   unsigned numWords = getNumWords();
00404   for (unsigned i = 0; i < numWords; ++i)
00405     pVal[i] &= RHS.pVal[i];
00406   return *this;
00407 }
00408 
00409 APInt& APInt::operator|=(const APInt& RHS) {
00410   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00411   if (isSingleWord()) {
00412     VAL |= RHS.VAL;
00413     return *this;
00414   }
00415   unsigned numWords = getNumWords();
00416   for (unsigned i = 0; i < numWords; ++i)
00417     pVal[i] |= RHS.pVal[i];
00418   return *this;
00419 }
00420 
00421 APInt& APInt::operator^=(const APInt& RHS) {
00422   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00423   if (isSingleWord()) {
00424     VAL ^= RHS.VAL;
00425     this->clearUnusedBits();
00426     return *this;
00427   }
00428   unsigned numWords = getNumWords();
00429   for (unsigned i = 0; i < numWords; ++i)
00430     pVal[i] ^= RHS.pVal[i];
00431   return clearUnusedBits();
00432 }
00433 
00434 APInt APInt::AndSlowCase(const APInt& RHS) const {
00435   unsigned numWords = getNumWords();
00436   uint64_t* val = getMemory(numWords);
00437   for (unsigned i = 0; i < numWords; ++i)
00438     val[i] = pVal[i] & RHS.pVal[i];
00439   return APInt(val, getBitWidth());
00440 }
00441 
00442 APInt APInt::OrSlowCase(const APInt& RHS) const {
00443   unsigned numWords = getNumWords();
00444   uint64_t *val = getMemory(numWords);
00445   for (unsigned i = 0; i < numWords; ++i)
00446     val[i] = pVal[i] | RHS.pVal[i];
00447   return APInt(val, getBitWidth());
00448 }
00449 
00450 APInt APInt::XorSlowCase(const APInt& RHS) const {
00451   unsigned numWords = getNumWords();
00452   uint64_t *val = getMemory(numWords);
00453   for (unsigned i = 0; i < numWords; ++i)
00454     val[i] = pVal[i] ^ RHS.pVal[i];
00455 
00456   // 0^0==1 so clear the high bits in case they got set.
00457   return APInt(val, getBitWidth()).clearUnusedBits();
00458 }
00459 
00460 APInt APInt::operator*(const APInt& RHS) const {
00461   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00462   if (isSingleWord())
00463     return APInt(BitWidth, VAL * RHS.VAL);
00464   APInt Result(*this);
00465   Result *= RHS;
00466   return Result;
00467 }
00468 
00469 APInt APInt::operator+(const APInt& RHS) const {
00470   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00471   if (isSingleWord())
00472     return APInt(BitWidth, VAL + RHS.VAL);
00473   APInt Result(BitWidth, 0);
00474   add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
00475   return Result.clearUnusedBits();
00476 }
00477 
00478 APInt APInt::operator-(const APInt& RHS) const {
00479   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
00480   if (isSingleWord())
00481     return APInt(BitWidth, VAL - RHS.VAL);
00482   APInt Result(BitWidth, 0);
00483   sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
00484   return Result.clearUnusedBits();
00485 }
00486 
00487 bool APInt::EqualSlowCase(const APInt& RHS) const {
00488   // Get some facts about the number of bits used in the two operands.
00489   unsigned n1 = getActiveBits();
00490   unsigned n2 = RHS.getActiveBits();
00491 
00492   // If the number of bits isn't the same, they aren't equal
00493   if (n1 != n2)
00494     return false;
00495 
00496   // If the number of bits fits in a word, we only need to compare the low word.
00497   if (n1 <= APINT_BITS_PER_WORD)
00498     return pVal[0] == RHS.pVal[0];
00499 
00500   // Otherwise, compare everything
00501   for (int i = whichWord(n1 - 1); i >= 0; --i)
00502     if (pVal[i] != RHS.pVal[i])
00503       return false;
00504   return true;
00505 }
00506 
00507 bool APInt::EqualSlowCase(uint64_t Val) const {
00508   unsigned n = getActiveBits();
00509   if (n <= APINT_BITS_PER_WORD)
00510     return pVal[0] == Val;
00511   else
00512     return false;
00513 }
00514 
00515 bool APInt::ult(const APInt& RHS) const {
00516   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
00517   if (isSingleWord())
00518     return VAL < RHS.VAL;
00519 
00520   // Get active bit length of both operands
00521   unsigned n1 = getActiveBits();
00522   unsigned n2 = RHS.getActiveBits();
00523 
00524   // If magnitude of LHS is less than RHS, return true.
00525   if (n1 < n2)
00526     return true;
00527 
00528   // If magnitude of RHS is greather than LHS, return false.
00529   if (n2 < n1)
00530     return false;
00531 
00532   // If they bot fit in a word, just compare the low order word
00533   if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
00534     return pVal[0] < RHS.pVal[0];
00535 
00536   // Otherwise, compare all words
00537   unsigned topWord = whichWord(std::max(n1,n2)-1);
00538   for (int i = topWord; i >= 0; --i) {
00539     if (pVal[i] > RHS.pVal[i])
00540       return false;
00541     if (pVal[i] < RHS.pVal[i])
00542       return true;
00543   }
00544   return false;
00545 }
00546 
00547 bool APInt::slt(const APInt& RHS) const {
00548   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
00549   if (isSingleWord()) {
00550     int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
00551     int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
00552     return lhsSext < rhsSext;
00553   }
00554 
00555   APInt lhs(*this);
00556   APInt rhs(RHS);
00557   bool lhsNeg = isNegative();
00558   bool rhsNeg = rhs.isNegative();
00559   if (lhsNeg) {
00560     // Sign bit is set so perform two's complement to make it positive
00561     lhs.flipAllBits();
00562     ++lhs;
00563   }
00564   if (rhsNeg) {
00565     // Sign bit is set so perform two's complement to make it positive
00566     rhs.flipAllBits();
00567     ++rhs;
00568   }
00569 
00570   // Now we have unsigned values to compare so do the comparison if necessary
00571   // based on the negativeness of the values.
00572   if (lhsNeg)
00573     if (rhsNeg)
00574       return lhs.ugt(rhs);
00575     else
00576       return true;
00577   else if (rhsNeg)
00578     return false;
00579   else
00580     return lhs.ult(rhs);
00581 }
00582 
00583 void APInt::setBit(unsigned bitPosition) {
00584   if (isSingleWord())
00585     VAL |= maskBit(bitPosition);
00586   else
00587     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
00588 }
00589 
00590 /// Set the given bit to 0 whose position is given as "bitPosition".
00591 /// @brief Set a given bit to 0.
00592 void APInt::clearBit(unsigned bitPosition) {
00593   if (isSingleWord())
00594     VAL &= ~maskBit(bitPosition);
00595   else
00596     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
00597 }
00598 
00599 /// @brief Toggle every bit to its opposite value.
00600 
00601 /// Toggle a given bit to its opposite value whose position is given
00602 /// as "bitPosition".
00603 /// @brief Toggles a given bit to its opposite value.
00604 void APInt::flipBit(unsigned bitPosition) {
00605   assert(bitPosition < BitWidth && "Out of the bit-width range!");
00606   if ((*this)[bitPosition]) clearBit(bitPosition);
00607   else setBit(bitPosition);
00608 }
00609 
00610 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
00611   assert(!str.empty() && "Invalid string length");
00612   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
00613           radix == 36) &&
00614          "Radix should be 2, 8, 10, 16, or 36!");
00615 
00616   size_t slen = str.size();
00617 
00618   // Each computation below needs to know if it's negative.
00619   StringRef::iterator p = str.begin();
00620   unsigned isNegative = *p == '-';
00621   if (*p == '-' || *p == '+') {
00622     p++;
00623     slen--;
00624     assert(slen && "String is only a sign, needs a value.");
00625   }
00626 
00627   // For radixes of power-of-two values, the bits required is accurately and
00628   // easily computed
00629   if (radix == 2)
00630     return slen + isNegative;
00631   if (radix == 8)
00632     return slen * 3 + isNegative;
00633   if (radix == 16)
00634     return slen * 4 + isNegative;
00635 
00636   // FIXME: base 36
00637   
00638   // This is grossly inefficient but accurate. We could probably do something
00639   // with a computation of roughly slen*64/20 and then adjust by the value of
00640   // the first few digits. But, I'm not sure how accurate that could be.
00641 
00642   // Compute a sufficient number of bits that is always large enough but might
00643   // be too large. This avoids the assertion in the constructor. This
00644   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
00645   // bits in that case.
00646   unsigned sufficient 
00647     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
00648                  : (slen == 1 ? 7 : slen * 16/3);
00649 
00650   // Convert to the actual binary value.
00651   APInt tmp(sufficient, StringRef(p, slen), radix);
00652 
00653   // Compute how many bits are required. If the log is infinite, assume we need
00654   // just bit.
00655   unsigned log = tmp.logBase2();
00656   if (log == (unsigned)-1) {
00657     return isNegative + 1;
00658   } else {
00659     return isNegative + log + 1;
00660   }
00661 }
00662 
00663 hash_code llvm::hash_value(const APInt &Arg) {
00664   if (Arg.isSingleWord())
00665     return hash_combine(Arg.VAL);
00666 
00667   return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
00668 }
00669 
00670 /// HiBits - This function returns the high "numBits" bits of this APInt.
00671 APInt APInt::getHiBits(unsigned numBits) const {
00672   return APIntOps::lshr(*this, BitWidth - numBits);
00673 }
00674 
00675 /// LoBits - This function returns the low "numBits" bits of this APInt.
00676 APInt APInt::getLoBits(unsigned numBits) const {
00677   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
00678                         BitWidth - numBits);
00679 }
00680 
00681 unsigned APInt::countLeadingZerosSlowCase() const {
00682   // Treat the most significand word differently because it might have
00683   // meaningless bits set beyond the precision.
00684   unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
00685   integerPart MSWMask;
00686   if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
00687   else {
00688     MSWMask = ~integerPart(0);
00689     BitsInMSW = APINT_BITS_PER_WORD;
00690   }
00691 
00692   unsigned i = getNumWords();
00693   integerPart MSW = pVal[i-1] & MSWMask;
00694   if (MSW)
00695     return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
00696 
00697   unsigned Count = BitsInMSW;
00698   for (--i; i > 0u; --i) {
00699     if (pVal[i-1] == 0)
00700       Count += APINT_BITS_PER_WORD;
00701     else {
00702       Count += llvm::countLeadingZeros(pVal[i-1]);
00703       break;
00704     }
00705   }
00706   return Count;
00707 }
00708 
00709 unsigned APInt::countLeadingOnes() const {
00710   if (isSingleWord())
00711     return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
00712 
00713   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
00714   unsigned shift;
00715   if (!highWordBits) {
00716     highWordBits = APINT_BITS_PER_WORD;
00717     shift = 0;
00718   } else {
00719     shift = APINT_BITS_PER_WORD - highWordBits;
00720   }
00721   int i = getNumWords() - 1;
00722   unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
00723   if (Count == highWordBits) {
00724     for (i--; i >= 0; --i) {
00725       if (pVal[i] == -1ULL)
00726         Count += APINT_BITS_PER_WORD;
00727       else {
00728         Count += CountLeadingOnes_64(pVal[i]);
00729         break;
00730       }
00731     }
00732   }
00733   return Count;
00734 }
00735 
00736 unsigned APInt::countTrailingZeros() const {
00737   if (isSingleWord())
00738     return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
00739   unsigned Count = 0;
00740   unsigned i = 0;
00741   for (; i < getNumWords() && pVal[i] == 0; ++i)
00742     Count += APINT_BITS_PER_WORD;
00743   if (i < getNumWords())
00744     Count += llvm::countTrailingZeros(pVal[i]);
00745   return std::min(Count, BitWidth);
00746 }
00747 
00748 unsigned APInt::countTrailingOnesSlowCase() const {
00749   unsigned Count = 0;
00750   unsigned i = 0;
00751   for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
00752     Count += APINT_BITS_PER_WORD;
00753   if (i < getNumWords())
00754     Count += CountTrailingOnes_64(pVal[i]);
00755   return std::min(Count, BitWidth);
00756 }
00757 
00758 unsigned APInt::countPopulationSlowCase() const {
00759   unsigned Count = 0;
00760   for (unsigned i = 0; i < getNumWords(); ++i)
00761     Count += CountPopulation_64(pVal[i]);
00762   return Count;
00763 }
00764 
00765 /// Perform a logical right-shift from Src to Dst, which must be equal or
00766 /// non-overlapping, of Words words, by Shift, which must be less than 64.
00767 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
00768                      unsigned Shift) {
00769   uint64_t Carry = 0;
00770   for (int I = Words - 1; I >= 0; --I) {
00771     uint64_t Tmp = Src[I];
00772     Dst[I] = (Tmp >> Shift) | Carry;
00773     Carry = Tmp << (64 - Shift);
00774   }
00775 }
00776 
00777 APInt APInt::byteSwap() const {
00778   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
00779   if (BitWidth == 16)
00780     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
00781   if (BitWidth == 32)
00782     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
00783   if (BitWidth == 48) {
00784     unsigned Tmp1 = unsigned(VAL >> 16);
00785     Tmp1 = ByteSwap_32(Tmp1);
00786     uint16_t Tmp2 = uint16_t(VAL);
00787     Tmp2 = ByteSwap_16(Tmp2);
00788     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
00789   }
00790   if (BitWidth == 64)
00791     return APInt(BitWidth, ByteSwap_64(VAL));
00792 
00793   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
00794   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
00795     Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
00796   if (Result.BitWidth != BitWidth) {
00797     lshrNear(Result.pVal, Result.pVal, getNumWords(),
00798              Result.BitWidth - BitWidth);
00799     Result.BitWidth = BitWidth;
00800   }
00801   return Result;
00802 }
00803 
00804 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
00805                                             const APInt& API2) {
00806   APInt A = API1, B = API2;
00807   while (!!B) {
00808     APInt T = B;
00809     B = APIntOps::urem(A, B);
00810     A = T;
00811   }
00812   return A;
00813 }
00814 
00815 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
00816   union {
00817     double D;
00818     uint64_t I;
00819   } T;
00820   T.D = Double;
00821 
00822   // Get the sign bit from the highest order bit
00823   bool isNeg = T.I >> 63;
00824 
00825   // Get the 11-bit exponent and adjust for the 1023 bit bias
00826   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
00827 
00828   // If the exponent is negative, the value is < 0 so just return 0.
00829   if (exp < 0)
00830     return APInt(width, 0u);
00831 
00832   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
00833   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
00834 
00835   // If the exponent doesn't shift all bits out of the mantissa
00836   if (exp < 52)
00837     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
00838                     APInt(width, mantissa >> (52 - exp));
00839 
00840   // If the client didn't provide enough bits for us to shift the mantissa into
00841   // then the result is undefined, just return 0
00842   if (width <= exp - 52)
00843     return APInt(width, 0);
00844 
00845   // Otherwise, we have to shift the mantissa bits up to the right location
00846   APInt Tmp(width, mantissa);
00847   Tmp = Tmp.shl((unsigned)exp - 52);
00848   return isNeg ? -Tmp : Tmp;
00849 }
00850 
00851 /// RoundToDouble - This function converts this APInt to a double.
00852 /// The layout for double is as following (IEEE Standard 754):
00853 ///  --------------------------------------
00854 /// |  Sign    Exponent    Fraction    Bias |
00855 /// |-------------------------------------- |
00856 /// |  1[63]   11[62-52]   52[51-00]   1023 |
00857 ///  --------------------------------------
00858 double APInt::roundToDouble(bool isSigned) const {
00859 
00860   // Handle the simple case where the value is contained in one uint64_t.
00861   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
00862   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
00863     if (isSigned) {
00864       int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
00865       return double(sext);
00866     } else
00867       return double(getWord(0));
00868   }
00869 
00870   // Determine if the value is negative.
00871   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
00872 
00873   // Construct the absolute value if we're negative.
00874   APInt Tmp(isNeg ? -(*this) : (*this));
00875 
00876   // Figure out how many bits we're using.
00877   unsigned n = Tmp.getActiveBits();
00878 
00879   // The exponent (without bias normalization) is just the number of bits
00880   // we are using. Note that the sign bit is gone since we constructed the
00881   // absolute value.
00882   uint64_t exp = n;
00883 
00884   // Return infinity for exponent overflow
00885   if (exp > 1023) {
00886     if (!isSigned || !isNeg)
00887       return std::numeric_limits<double>::infinity();
00888     else
00889       return -std::numeric_limits<double>::infinity();
00890   }
00891   exp += 1023; // Increment for 1023 bias
00892 
00893   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
00894   // extract the high 52 bits from the correct words in pVal.
00895   uint64_t mantissa;
00896   unsigned hiWord = whichWord(n-1);
00897   if (hiWord == 0) {
00898     mantissa = Tmp.pVal[0];
00899     if (n > 52)
00900       mantissa >>= n - 52; // shift down, we want the top 52 bits.
00901   } else {
00902     assert(hiWord > 0 && "huh?");
00903     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
00904     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
00905     mantissa = hibits | lobits;
00906   }
00907 
00908   // The leading bit of mantissa is implicit, so get rid of it.
00909   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
00910   union {
00911     double D;
00912     uint64_t I;
00913   } T;
00914   T.I = sign | (exp << 52) | mantissa;
00915   return T.D;
00916 }
00917 
00918 // Truncate to new width.
00919 APInt APInt::trunc(unsigned width) const {
00920   assert(width < BitWidth && "Invalid APInt Truncate request");
00921   assert(width && "Can't truncate to 0 bits");
00922 
00923   if (width <= APINT_BITS_PER_WORD)
00924     return APInt(width, getRawData()[0]);
00925 
00926   APInt Result(getMemory(getNumWords(width)), width);
00927 
00928   // Copy full words.
00929   unsigned i;
00930   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
00931     Result.pVal[i] = pVal[i];
00932 
00933   // Truncate and copy any partial word.
00934   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
00935   if (bits != 0)
00936     Result.pVal[i] = pVal[i] << bits >> bits;
00937 
00938   return Result;
00939 }
00940 
00941 // Sign extend to a new width.
00942 APInt APInt::sext(unsigned width) const {
00943   assert(width > BitWidth && "Invalid APInt SignExtend request");
00944 
00945   if (width <= APINT_BITS_PER_WORD) {
00946     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
00947     val = (int64_t)val >> (width - BitWidth);
00948     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
00949   }
00950 
00951   APInt Result(getMemory(getNumWords(width)), width);
00952 
00953   // Copy full words.
00954   unsigned i;
00955   uint64_t word = 0;
00956   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
00957     word = getRawData()[i];
00958     Result.pVal[i] = word;
00959   }
00960 
00961   // Read and sign-extend any partial word.
00962   unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
00963   if (bits != 0)
00964     word = (int64_t)getRawData()[i] << bits >> bits;
00965   else
00966     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
00967 
00968   // Write remaining full words.
00969   for (; i != width / APINT_BITS_PER_WORD; i++) {
00970     Result.pVal[i] = word;
00971     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
00972   }
00973 
00974   // Write any partial word.
00975   bits = (0 - width) % APINT_BITS_PER_WORD;
00976   if (bits != 0)
00977     Result.pVal[i] = word << bits >> bits;
00978 
00979   return Result;
00980 }
00981 
00982 //  Zero extend to a new width.
00983 APInt APInt::zext(unsigned width) const {
00984   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
00985 
00986   if (width <= APINT_BITS_PER_WORD)
00987     return APInt(width, VAL);
00988 
00989   APInt Result(getMemory(getNumWords(width)), width);
00990 
00991   // Copy words.
00992   unsigned i;
00993   for (i = 0; i != getNumWords(); i++)
00994     Result.pVal[i] = getRawData()[i];
00995 
00996   // Zero remaining words.
00997   memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
00998 
00999   return Result;
01000 }
01001 
01002 APInt APInt::zextOrTrunc(unsigned width) const {
01003   if (BitWidth < width)
01004     return zext(width);
01005   if (BitWidth > width)
01006     return trunc(width);
01007   return *this;
01008 }
01009 
01010 APInt APInt::sextOrTrunc(unsigned width) const {
01011   if (BitWidth < width)
01012     return sext(width);
01013   if (BitWidth > width)
01014     return trunc(width);
01015   return *this;
01016 }
01017 
01018 APInt APInt::zextOrSelf(unsigned width) const {
01019   if (BitWidth < width)
01020     return zext(width);
01021   return *this;
01022 }
01023 
01024 APInt APInt::sextOrSelf(unsigned width) const {
01025   if (BitWidth < width)
01026     return sext(width);
01027   return *this;
01028 }
01029 
01030 /// Arithmetic right-shift this APInt by shiftAmt.
01031 /// @brief Arithmetic right-shift function.
01032 APInt APInt::ashr(const APInt &shiftAmt) const {
01033   return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
01034 }
01035 
01036 /// Arithmetic right-shift this APInt by shiftAmt.
01037 /// @brief Arithmetic right-shift function.
01038 APInt APInt::ashr(unsigned shiftAmt) const {
01039   assert(shiftAmt <= BitWidth && "Invalid shift amount");
01040   // Handle a degenerate case
01041   if (shiftAmt == 0)
01042     return *this;
01043 
01044   // Handle single word shifts with built-in ashr
01045   if (isSingleWord()) {
01046     if (shiftAmt == BitWidth)
01047       return APInt(BitWidth, 0); // undefined
01048     else {
01049       unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
01050       return APInt(BitWidth,
01051         (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
01052     }
01053   }
01054 
01055   // If all the bits were shifted out, the result is, technically, undefined.
01056   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
01057   // issues in the algorithm below.
01058   if (shiftAmt == BitWidth) {
01059     if (isNegative())
01060       return APInt(BitWidth, -1ULL, true);
01061     else
01062       return APInt(BitWidth, 0);
01063   }
01064 
01065   // Create some space for the result.
01066   uint64_t * val = new uint64_t[getNumWords()];
01067 
01068   // Compute some values needed by the following shift algorithms
01069   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
01070   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
01071   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
01072   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
01073   if (bitsInWord == 0)
01074     bitsInWord = APINT_BITS_PER_WORD;
01075 
01076   // If we are shifting whole words, just move whole words
01077   if (wordShift == 0) {
01078     // Move the words containing significant bits
01079     for (unsigned i = 0; i <= breakWord; ++i)
01080       val[i] = pVal[i+offset]; // move whole word
01081 
01082     // Adjust the top significant word for sign bit fill, if negative
01083     if (isNegative())
01084       if (bitsInWord < APINT_BITS_PER_WORD)
01085         val[breakWord] |= ~0ULL << bitsInWord; // set high bits
01086   } else {
01087     // Shift the low order words
01088     for (unsigned i = 0; i < breakWord; ++i) {
01089       // This combines the shifted corresponding word with the low bits from
01090       // the next word (shifted into this word's high bits).
01091       val[i] = (pVal[i+offset] >> wordShift) |
01092                (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
01093     }
01094 
01095     // Shift the break word. In this case there are no bits from the next word
01096     // to include in this word.
01097     val[breakWord] = pVal[breakWord+offset] >> wordShift;
01098 
01099     // Deal with sign extension in the break word, and possibly the word before
01100     // it.
01101     if (isNegative()) {
01102       if (wordShift > bitsInWord) {
01103         if (breakWord > 0)
01104           val[breakWord-1] |=
01105             ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
01106         val[breakWord] |= ~0ULL;
01107       } else
01108         val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
01109     }
01110   }
01111 
01112   // Remaining words are 0 or -1, just assign them.
01113   uint64_t fillValue = (isNegative() ? -1ULL : 0);
01114   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
01115     val[i] = fillValue;
01116   return APInt(val, BitWidth).clearUnusedBits();
01117 }
01118 
01119 /// Logical right-shift this APInt by shiftAmt.
01120 /// @brief Logical right-shift function.
01121 APInt APInt::lshr(const APInt &shiftAmt) const {
01122   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
01123 }
01124 
01125 /// Logical right-shift this APInt by shiftAmt.
01126 /// @brief Logical right-shift function.
01127 APInt APInt::lshr(unsigned shiftAmt) const {
01128   if (isSingleWord()) {
01129     if (shiftAmt >= BitWidth)
01130       return APInt(BitWidth, 0);
01131     else
01132       return APInt(BitWidth, this->VAL >> shiftAmt);
01133   }
01134 
01135   // If all the bits were shifted out, the result is 0. This avoids issues
01136   // with shifting by the size of the integer type, which produces undefined
01137   // results. We define these "undefined results" to always be 0.
01138   if (shiftAmt >= BitWidth)
01139     return APInt(BitWidth, 0);
01140 
01141   // If none of the bits are shifted out, the result is *this. This avoids
01142   // issues with shifting by the size of the integer type, which produces
01143   // undefined results in the code below. This is also an optimization.
01144   if (shiftAmt == 0)
01145     return *this;
01146 
01147   // Create some space for the result.
01148   uint64_t * val = new uint64_t[getNumWords()];
01149 
01150   // If we are shifting less than a word, compute the shift with a simple carry
01151   if (shiftAmt < APINT_BITS_PER_WORD) {
01152     lshrNear(val, pVal, getNumWords(), shiftAmt);
01153     return APInt(val, BitWidth).clearUnusedBits();
01154   }
01155 
01156   // Compute some values needed by the remaining shift algorithms
01157   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
01158   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
01159 
01160   // If we are shifting whole words, just move whole words
01161   if (wordShift == 0) {
01162     for (unsigned i = 0; i < getNumWords() - offset; ++i)
01163       val[i] = pVal[i+offset];
01164     for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
01165       val[i] = 0;
01166     return APInt(val,BitWidth).clearUnusedBits();
01167   }
01168 
01169   // Shift the low order words
01170   unsigned breakWord = getNumWords() - offset -1;
01171   for (unsigned i = 0; i < breakWord; ++i)
01172     val[i] = (pVal[i+offset] >> wordShift) |
01173              (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
01174   // Shift the break word.
01175   val[breakWord] = pVal[breakWord+offset] >> wordShift;
01176 
01177   // Remaining words are 0
01178   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
01179     val[i] = 0;
01180   return APInt(val, BitWidth).clearUnusedBits();
01181 }
01182 
01183 /// Left-shift this APInt by shiftAmt.
01184 /// @brief Left-shift function.
01185 APInt APInt::shl(const APInt &shiftAmt) const {
01186   // It's undefined behavior in C to shift by BitWidth or greater.
01187   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
01188 }
01189 
01190 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
01191   // If all the bits were shifted out, the result is 0. This avoids issues
01192   // with shifting by the size of the integer type, which produces undefined
01193   // results. We define these "undefined results" to always be 0.
01194   if (shiftAmt == BitWidth)
01195     return APInt(BitWidth, 0);
01196 
01197   // If none of the bits are shifted out, the result is *this. This avoids a
01198   // lshr by the words size in the loop below which can produce incorrect
01199   // results. It also avoids the expensive computation below for a common case.
01200   if (shiftAmt == 0)
01201     return *this;
01202 
01203   // Create some space for the result.
01204   uint64_t * val = new uint64_t[getNumWords()];
01205 
01206   // If we are shifting less than a word, do it the easy way
01207   if (shiftAmt < APINT_BITS_PER_WORD) {
01208     uint64_t carry = 0;
01209     for (unsigned i = 0; i < getNumWords(); i++) {
01210       val[i] = pVal[i] << shiftAmt | carry;
01211       carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
01212     }
01213     return APInt(val, BitWidth).clearUnusedBits();
01214   }
01215 
01216   // Compute some values needed by the remaining shift algorithms
01217   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
01218   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
01219 
01220   // If we are shifting whole words, just move whole words
01221   if (wordShift == 0) {
01222     for (unsigned i = 0; i < offset; i++)
01223       val[i] = 0;
01224     for (unsigned i = offset; i < getNumWords(); i++)
01225       val[i] = pVal[i-offset];
01226     return APInt(val,BitWidth).clearUnusedBits();
01227   }
01228 
01229   // Copy whole words from this to Result.
01230   unsigned i = getNumWords() - 1;
01231   for (; i > offset; --i)
01232     val[i] = pVal[i-offset] << wordShift |
01233              pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
01234   val[offset] = pVal[0] << wordShift;
01235   for (i = 0; i < offset; ++i)
01236     val[i] = 0;
01237   return APInt(val, BitWidth).clearUnusedBits();
01238 }
01239 
01240 APInt APInt::rotl(const APInt &rotateAmt) const {
01241   return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
01242 }
01243 
01244 APInt APInt::rotl(unsigned rotateAmt) const {
01245   rotateAmt %= BitWidth;
01246   if (rotateAmt == 0)
01247     return *this;
01248   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
01249 }
01250 
01251 APInt APInt::rotr(const APInt &rotateAmt) const {
01252   return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
01253 }
01254 
01255 APInt APInt::rotr(unsigned rotateAmt) const {
01256   rotateAmt %= BitWidth;
01257   if (rotateAmt == 0)
01258     return *this;
01259   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
01260 }
01261 
01262 // Square Root - this method computes and returns the square root of "this".
01263 // Three mechanisms are used for computation. For small values (<= 5 bits),
01264 // a table lookup is done. This gets some performance for common cases. For
01265 // values using less than 52 bits, the value is converted to double and then
01266 // the libc sqrt function is called. The result is rounded and then converted
01267 // back to a uint64_t which is then used to construct the result. Finally,
01268 // the Babylonian method for computing square roots is used.
01269 APInt APInt::sqrt() const {
01270 
01271   // Determine the magnitude of the value.
01272   unsigned magnitude = getActiveBits();
01273 
01274   // Use a fast table for some small values. This also gets rid of some
01275   // rounding errors in libc sqrt for small values.
01276   if (magnitude <= 5) {
01277     static const uint8_t results[32] = {
01278       /*     0 */ 0,
01279       /*  1- 2 */ 1, 1,
01280       /*  3- 6 */ 2, 2, 2, 2,
01281       /*  7-12 */ 3, 3, 3, 3, 3, 3,
01282       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
01283       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
01284       /*    31 */ 6
01285     };
01286     return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
01287   }
01288 
01289   // If the magnitude of the value fits in less than 52 bits (the precision of
01290   // an IEEE double precision floating point value), then we can use the
01291   // libc sqrt function which will probably use a hardware sqrt computation.
01292   // This should be faster than the algorithm below.
01293   if (magnitude < 52) {
01294 #if HAVE_ROUND
01295     return APInt(BitWidth,
01296                  uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
01297 #else
01298     return APInt(BitWidth,
01299                  uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
01300 #endif
01301   }
01302 
01303   // Okay, all the short cuts are exhausted. We must compute it. The following
01304   // is a classical Babylonian method for computing the square root. This code
01305   // was adapted to APINt from a wikipedia article on such computations.
01306   // See http://www.wikipedia.org/ and go to the page named
01307   // Calculate_an_integer_square_root.
01308   unsigned nbits = BitWidth, i = 4;
01309   APInt testy(BitWidth, 16);
01310   APInt x_old(BitWidth, 1);
01311   APInt x_new(BitWidth, 0);
01312   APInt two(BitWidth, 2);
01313 
01314   // Select a good starting value using binary logarithms.
01315   for (;; i += 2, testy = testy.shl(2))
01316     if (i >= nbits || this->ule(testy)) {
01317       x_old = x_old.shl(i / 2);
01318       break;
01319     }
01320 
01321   // Use the Babylonian method to arrive at the integer square root:
01322   for (;;) {
01323     x_new = (this->udiv(x_old) + x_old).udiv(two);
01324     if (x_old.ule(x_new))
01325       break;
01326     x_old = x_new;
01327   }
01328 
01329   // Make sure we return the closest approximation
01330   // NOTE: The rounding calculation below is correct. It will produce an
01331   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
01332   // determined to be a rounding issue with pari/gp as it begins to use a
01333   // floating point representation after 192 bits. There are no discrepancies
01334   // between this algorithm and pari/gp for bit widths < 192 bits.
01335   APInt square(x_old * x_old);
01336   APInt nextSquare((x_old + 1) * (x_old +1));
01337   if (this->ult(square))
01338     return x_old;
01339   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
01340   APInt midpoint((nextSquare - square).udiv(two));
01341   APInt offset(*this - square);
01342   if (offset.ult(midpoint))
01343     return x_old;
01344   return x_old + 1;
01345 }
01346 
01347 /// Computes the multiplicative inverse of this APInt for a given modulo. The
01348 /// iterative extended Euclidean algorithm is used to solve for this value,
01349 /// however we simplify it to speed up calculating only the inverse, and take
01350 /// advantage of div+rem calculations. We also use some tricks to avoid copying
01351 /// (potentially large) APInts around.
01352 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
01353   assert(ult(modulo) && "This APInt must be smaller than the modulo");
01354 
01355   // Using the properties listed at the following web page (accessed 06/21/08):
01356   //   http://www.numbertheory.org/php/euclid.html
01357   // (especially the properties numbered 3, 4 and 9) it can be proved that
01358   // BitWidth bits suffice for all the computations in the algorithm implemented
01359   // below. More precisely, this number of bits suffice if the multiplicative
01360   // inverse exists, but may not suffice for the general extended Euclidean
01361   // algorithm.
01362 
01363   APInt r[2] = { modulo, *this };
01364   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
01365   APInt q(BitWidth, 0);
01366 
01367   unsigned i;
01368   for (i = 0; r[i^1] != 0; i ^= 1) {
01369     // An overview of the math without the confusing bit-flipping:
01370     // q = r[i-2] / r[i-1]
01371     // r[i] = r[i-2] % r[i-1]
01372     // t[i] = t[i-2] - t[i-1] * q
01373     udivrem(r[i], r[i^1], q, r[i]);
01374     t[i] -= t[i^1] * q;
01375   }
01376 
01377   // If this APInt and the modulo are not coprime, there is no multiplicative
01378   // inverse, so return 0. We check this by looking at the next-to-last
01379   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
01380   // algorithm.
01381   if (r[i] != 1)
01382     return APInt(BitWidth, 0);
01383 
01384   // The next-to-last t is the multiplicative inverse.  However, we are
01385   // interested in a positive inverse. Calcuate a positive one from a negative
01386   // one if necessary. A simple addition of the modulo suffices because
01387   // abs(t[i]) is known to be less than *this/2 (see the link above).
01388   return t[i].isNegative() ? t[i] + modulo : t[i];
01389 }
01390 
01391 /// Calculate the magic numbers required to implement a signed integer division
01392 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
01393 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
01394 /// Warren, Jr., chapter 10.
01395 APInt::ms APInt::magic() const {
01396   const APInt& d = *this;
01397   unsigned p;
01398   APInt ad, anc, delta, q1, r1, q2, r2, t;
01399   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
01400   struct ms mag;
01401 
01402   ad = d.abs();
01403   t = signedMin + (d.lshr(d.getBitWidth() - 1));
01404   anc = t - 1 - t.urem(ad);   // absolute value of nc
01405   p = d.getBitWidth() - 1;    // initialize p
01406   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
01407   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
01408   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
01409   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
01410   do {
01411     p = p + 1;
01412     q1 = q1<<1;          // update q1 = 2p/abs(nc)
01413     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
01414     if (r1.uge(anc)) {  // must be unsigned comparison
01415       q1 = q1 + 1;
01416       r1 = r1 - anc;
01417     }
01418     q2 = q2<<1;          // update q2 = 2p/abs(d)
01419     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
01420     if (r2.uge(ad)) {   // must be unsigned comparison
01421       q2 = q2 + 1;
01422       r2 = r2 - ad;
01423     }
01424     delta = ad - r2;
01425   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
01426 
01427   mag.m = q2 + 1;
01428   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
01429   mag.s = p - d.getBitWidth();          // resulting shift
01430   return mag;
01431 }
01432 
01433 /// Calculate the magic numbers required to implement an unsigned integer
01434 /// division by a constant as a sequence of multiplies, adds and shifts.
01435 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
01436 /// S. Warren, Jr., chapter 10.
01437 /// LeadingZeros can be used to simplify the calculation if the upper bits
01438 /// of the divided value are known zero.
01439 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
01440   const APInt& d = *this;
01441   unsigned p;
01442   APInt nc, delta, q1, r1, q2, r2;
01443   struct mu magu;
01444   magu.a = 0;               // initialize "add" indicator
01445   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
01446   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
01447   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
01448 
01449   nc = allOnes - (allOnes - d).urem(d);
01450   p = d.getBitWidth() - 1;  // initialize p
01451   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
01452   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
01453   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
01454   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
01455   do {
01456     p = p + 1;
01457     if (r1.uge(nc - r1)) {
01458       q1 = q1 + q1 + 1;  // update q1
01459       r1 = r1 + r1 - nc; // update r1
01460     }
01461     else {
01462       q1 = q1+q1; // update q1
01463       r1 = r1+r1; // update r1
01464     }
01465     if ((r2 + 1).uge(d - r2)) {
01466       if (q2.uge(signedMax)) magu.a = 1;
01467       q2 = q2+q2 + 1;     // update q2
01468       r2 = r2+r2 + 1 - d; // update r2
01469     }
01470     else {
01471       if (q2.uge(signedMin)) magu.a = 1;
01472       q2 = q2+q2;     // update q2
01473       r2 = r2+r2 + 1; // update r2
01474     }
01475     delta = d - 1 - r2;
01476   } while (p < d.getBitWidth()*2 &&
01477            (q1.ult(delta) || (q1 == delta && r1 == 0)));
01478   magu.m = q2 + 1; // resulting magic number
01479   magu.s = p - d.getBitWidth();  // resulting shift
01480   return magu;
01481 }
01482 
01483 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
01484 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
01485 /// variables here have the same names as in the algorithm. Comments explain
01486 /// the algorithm and any deviation from it.
01487 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
01488                      unsigned m, unsigned n) {
01489   assert(u && "Must provide dividend");
01490   assert(v && "Must provide divisor");
01491   assert(q && "Must provide quotient");
01492   assert(u != v && u != q && v != q && "Must us different memory");
01493   assert(n>1 && "n must be > 1");
01494 
01495   // Knuth uses the value b as the base of the number system. In our case b
01496   // is 2^31 so we just set it to -1u.
01497   uint64_t b = uint64_t(1) << 32;
01498 
01499 #if 0
01500   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
01501   DEBUG(dbgs() << "KnuthDiv: original:");
01502   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01503   DEBUG(dbgs() << " by");
01504   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
01505   DEBUG(dbgs() << '\n');
01506 #endif
01507   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
01508   // u and v by d. Note that we have taken Knuth's advice here to use a power
01509   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
01510   // 2 allows us to shift instead of multiply and it is easy to determine the
01511   // shift amount from the leading zeros.  We are basically normalizing the u
01512   // and v so that its high bits are shifted to the top of v's range without
01513   // overflow. Note that this can require an extra word in u so that u must
01514   // be of length m+n+1.
01515   unsigned shift = countLeadingZeros(v[n-1]);
01516   unsigned v_carry = 0;
01517   unsigned u_carry = 0;
01518   if (shift) {
01519     for (unsigned i = 0; i < m+n; ++i) {
01520       unsigned u_tmp = u[i] >> (32 - shift);
01521       u[i] = (u[i] << shift) | u_carry;
01522       u_carry = u_tmp;
01523     }
01524     for (unsigned i = 0; i < n; ++i) {
01525       unsigned v_tmp = v[i] >> (32 - shift);
01526       v[i] = (v[i] << shift) | v_carry;
01527       v_carry = v_tmp;
01528     }
01529   }
01530   u[m+n] = u_carry;
01531 #if 0
01532   DEBUG(dbgs() << "KnuthDiv:   normal:");
01533   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01534   DEBUG(dbgs() << " by");
01535   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
01536   DEBUG(dbgs() << '\n');
01537 #endif
01538 
01539   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
01540   int j = m;
01541   do {
01542     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
01543     // D3. [Calculate q'.].
01544     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
01545     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
01546     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
01547     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
01548     // on v[n-2] determines at high speed most of the cases in which the trial
01549     // value qp is one too large, and it eliminates all cases where qp is two
01550     // too large.
01551     uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
01552     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
01553     uint64_t qp = dividend / v[n-1];
01554     uint64_t rp = dividend % v[n-1];
01555     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
01556       qp--;
01557       rp += v[n-1];
01558       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
01559         qp--;
01560     }
01561     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
01562 
01563     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
01564     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
01565     // consists of a simple multiplication by a one-place number, combined with
01566     // a subtraction.
01567     bool isNeg = false;
01568     for (unsigned i = 0; i < n; ++i) {
01569       uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
01570       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
01571       bool borrow = subtrahend > u_tmp;
01572       DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
01573                    << ", subtrahend == " << subtrahend
01574                    << ", borrow = " << borrow << '\n');
01575 
01576       uint64_t result = u_tmp - subtrahend;
01577       unsigned k = j + i;
01578       u[k++] = (unsigned)(result & (b-1)); // subtract low word
01579       u[k++] = (unsigned)(result >> 32);   // subtract high word
01580       while (borrow && k <= m+n) { // deal with borrow to the left
01581         borrow = u[k] == 0;
01582         u[k]--;
01583         k++;
01584       }
01585       isNeg |= borrow;
01586       DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " <<
01587                     u[j+i+1] << '\n');
01588     }
01589     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
01590     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01591     DEBUG(dbgs() << '\n');
01592     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
01593     // this step is actually negative, (u[j+n]...u[j]) should be left as the
01594     // true value plus b**(n+1), namely as the b's complement of
01595     // the true value, and a "borrow" to the left should be remembered.
01596     //
01597     if (isNeg) {
01598       bool carry = true;  // true because b's complement is "complement + 1"
01599       for (unsigned i = 0; i <= m+n; ++i) {
01600         u[i] = ~u[i] + carry; // b's complement
01601         carry = carry && u[i] == 0;
01602       }
01603     }
01604     DEBUG(dbgs() << "KnuthDiv: after complement:");
01605     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01606     DEBUG(dbgs() << '\n');
01607 
01608     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
01609     // negative, go to step D6; otherwise go on to step D7.
01610     q[j] = (unsigned)qp;
01611     if (isNeg) {
01612       // D6. [Add back]. The probability that this step is necessary is very
01613       // small, on the order of only 2/b. Make sure that test data accounts for
01614       // this possibility. Decrease q[j] by 1
01615       q[j]--;
01616       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
01617       // A carry will occur to the left of u[j+n], and it should be ignored
01618       // since it cancels with the borrow that occurred in D4.
01619       bool carry = false;
01620       for (unsigned i = 0; i < n; i++) {
01621         unsigned limit = std::min(u[j+i],v[i]);
01622         u[j+i] += v[i] + carry;
01623         carry = u[j+i] < limit || (carry && u[j+i] == limit);
01624       }
01625       u[j+n] += carry;
01626     }
01627     DEBUG(dbgs() << "KnuthDiv: after correction:");
01628     DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
01629     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
01630 
01631   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
01632   } while (--j >= 0);
01633 
01634   DEBUG(dbgs() << "KnuthDiv: quotient:");
01635   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
01636   DEBUG(dbgs() << '\n');
01637 
01638   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
01639   // remainder may be obtained by dividing u[...] by d. If r is non-null we
01640   // compute the remainder (urem uses this).
01641   if (r) {
01642     // The value d is expressed by the "shift" value above since we avoided
01643     // multiplication by d by using a shift left. So, all we have to do is
01644     // shift right here. In order to mak
01645     if (shift) {
01646       unsigned carry = 0;
01647       DEBUG(dbgs() << "KnuthDiv: remainder:");
01648       for (int i = n-1; i >= 0; i--) {
01649         r[i] = (u[i] >> shift) | carry;
01650         carry = u[i] << (32 - shift);
01651         DEBUG(dbgs() << " " << r[i]);
01652       }
01653     } else {
01654       for (int i = n-1; i >= 0; i--) {
01655         r[i] = u[i];
01656         DEBUG(dbgs() << " " << r[i]);
01657       }
01658     }
01659     DEBUG(dbgs() << '\n');
01660   }
01661 #if 0
01662   DEBUG(dbgs() << '\n');
01663 #endif
01664 }
01665 
01666 void APInt::divide(const APInt LHS, unsigned lhsWords,
01667                    const APInt &RHS, unsigned rhsWords,
01668                    APInt *Quotient, APInt *Remainder)
01669 {
01670   assert(lhsWords >= rhsWords && "Fractional result");
01671 
01672   // First, compose the values into an array of 32-bit words instead of
01673   // 64-bit words. This is a necessity of both the "short division" algorithm
01674   // and the Knuth "classical algorithm" which requires there to be native
01675   // operations for +, -, and * on an m bit value with an m*2 bit result. We
01676   // can't use 64-bit operands here because we don't have native results of
01677   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
01678   // work on large-endian machines.
01679   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
01680   unsigned n = rhsWords * 2;
01681   unsigned m = (lhsWords * 2) - n;
01682 
01683   // Allocate space for the temporary values we need either on the stack, if
01684   // it will fit, or on the heap if it won't.
01685   unsigned SPACE[128];
01686   unsigned *U = nullptr;
01687   unsigned *V = nullptr;
01688   unsigned *Q = nullptr;
01689   unsigned *R = nullptr;
01690   if ((Remainder?4:3)*n+2*m+1 <= 128) {
01691     U = &SPACE[0];
01692     V = &SPACE[m+n+1];
01693     Q = &SPACE[(m+n+1) + n];
01694     if (Remainder)
01695       R = &SPACE[(m+n+1) + n + (m+n)];
01696   } else {
01697     U = new unsigned[m + n + 1];
01698     V = new unsigned[n];
01699     Q = new unsigned[m+n];
01700     if (Remainder)
01701       R = new unsigned[n];
01702   }
01703 
01704   // Initialize the dividend
01705   memset(U, 0, (m+n+1)*sizeof(unsigned));
01706   for (unsigned i = 0; i < lhsWords; ++i) {
01707     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
01708     U[i * 2] = (unsigned)(tmp & mask);
01709     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01710   }
01711   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
01712 
01713   // Initialize the divisor
01714   memset(V, 0, (n)*sizeof(unsigned));
01715   for (unsigned i = 0; i < rhsWords; ++i) {
01716     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
01717     V[i * 2] = (unsigned)(tmp & mask);
01718     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01719   }
01720 
01721   // initialize the quotient and remainder
01722   memset(Q, 0, (m+n) * sizeof(unsigned));
01723   if (Remainder)
01724     memset(R, 0, n * sizeof(unsigned));
01725 
01726   // Now, adjust m and n for the Knuth division. n is the number of words in
01727   // the divisor. m is the number of words by which the dividend exceeds the
01728   // divisor (i.e. m+n is the length of the dividend). These sizes must not
01729   // contain any zero words or the Knuth algorithm fails.
01730   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
01731     n--;
01732     m++;
01733   }
01734   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
01735     m--;
01736 
01737   // If we're left with only a single word for the divisor, Knuth doesn't work
01738   // so we implement the short division algorithm here. This is much simpler
01739   // and faster because we are certain that we can divide a 64-bit quantity
01740   // by a 32-bit quantity at hardware speed and short division is simply a
01741   // series of such operations. This is just like doing short division but we
01742   // are using base 2^32 instead of base 10.
01743   assert(n != 0 && "Divide by zero?");
01744   if (n == 1) {
01745     unsigned divisor = V[0];
01746     unsigned remainder = 0;
01747     for (int i = m+n-1; i >= 0; i--) {
01748       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
01749       if (partial_dividend == 0) {
01750         Q[i] = 0;
01751         remainder = 0;
01752       } else if (partial_dividend < divisor) {
01753         Q[i] = 0;
01754         remainder = (unsigned)partial_dividend;
01755       } else if (partial_dividend == divisor) {
01756         Q[i] = 1;
01757         remainder = 0;
01758       } else {
01759         Q[i] = (unsigned)(partial_dividend / divisor);
01760         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
01761       }
01762     }
01763     if (R)
01764       R[0] = remainder;
01765   } else {
01766     // Now we're ready to invoke the Knuth classical divide algorithm. In this
01767     // case n > 1.
01768     KnuthDiv(U, V, Q, R, m, n);
01769   }
01770 
01771   // If the caller wants the quotient
01772   if (Quotient) {
01773     // Set up the Quotient value's memory.
01774     if (Quotient->BitWidth != LHS.BitWidth) {
01775       if (Quotient->isSingleWord())
01776         Quotient->VAL = 0;
01777       else
01778         delete [] Quotient->pVal;
01779       Quotient->BitWidth = LHS.BitWidth;
01780       if (!Quotient->isSingleWord())
01781         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
01782     } else
01783       Quotient->clearAllBits();
01784 
01785     // The quotient is in Q. Reconstitute the quotient into Quotient's low
01786     // order words.
01787     if (lhsWords == 1) {
01788       uint64_t tmp =
01789         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
01790       if (Quotient->isSingleWord())
01791         Quotient->VAL = tmp;
01792       else
01793         Quotient->pVal[0] = tmp;
01794     } else {
01795       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
01796       for (unsigned i = 0; i < lhsWords; ++i)
01797         Quotient->pVal[i] =
01798           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01799     }
01800   }
01801 
01802   // If the caller wants the remainder
01803   if (Remainder) {
01804     // Set up the Remainder value's memory.
01805     if (Remainder->BitWidth != RHS.BitWidth) {
01806       if (Remainder->isSingleWord())
01807         Remainder->VAL = 0;
01808       else
01809         delete [] Remainder->pVal;
01810       Remainder->BitWidth = RHS.BitWidth;
01811       if (!Remainder->isSingleWord())
01812         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
01813     } else
01814       Remainder->clearAllBits();
01815 
01816     // The remainder is in R. Reconstitute the remainder into Remainder's low
01817     // order words.
01818     if (rhsWords == 1) {
01819       uint64_t tmp =
01820         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
01821       if (Remainder->isSingleWord())
01822         Remainder->VAL = tmp;
01823       else
01824         Remainder->pVal[0] = tmp;
01825     } else {
01826       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
01827       for (unsigned i = 0; i < rhsWords; ++i)
01828         Remainder->pVal[i] =
01829           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01830     }
01831   }
01832 
01833   // Clean up the memory we allocated.
01834   if (U != &SPACE[0]) {
01835     delete [] U;
01836     delete [] V;
01837     delete [] Q;
01838     delete [] R;
01839   }
01840 }
01841 
01842 APInt APInt::udiv(const APInt& RHS) const {
01843   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01844 
01845   // First, deal with the easy case
01846   if (isSingleWord()) {
01847     assert(RHS.VAL != 0 && "Divide by zero?");
01848     return APInt(BitWidth, VAL / RHS.VAL);
01849   }
01850 
01851   // Get some facts about the LHS and RHS number of bits and words
01852   unsigned rhsBits = RHS.getActiveBits();
01853   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01854   assert(rhsWords && "Divided by zero???");
01855   unsigned lhsBits = this->getActiveBits();
01856   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01857 
01858   // Deal with some degenerate cases
01859   if (!lhsWords)
01860     // 0 / X ===> 0
01861     return APInt(BitWidth, 0);
01862   else if (lhsWords < rhsWords || this->ult(RHS)) {
01863     // X / Y ===> 0, iff X < Y
01864     return APInt(BitWidth, 0);
01865   } else if (*this == RHS) {
01866     // X / X ===> 1
01867     return APInt(BitWidth, 1);
01868   } else if (lhsWords == 1 && rhsWords == 1) {
01869     // All high words are zero, just use native divide
01870     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
01871   }
01872 
01873   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01874   APInt Quotient(1,0); // to hold result.
01875   divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
01876   return Quotient;
01877 }
01878 
01879 APInt APInt::sdiv(const APInt &RHS) const {
01880   if (isNegative()) {
01881     if (RHS.isNegative())
01882       return (-(*this)).udiv(-RHS);
01883     return -((-(*this)).udiv(RHS));
01884   }
01885   if (RHS.isNegative())
01886     return -(this->udiv(-RHS));
01887   return this->udiv(RHS);
01888 }
01889 
01890 APInt APInt::urem(const APInt& RHS) const {
01891   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01892   if (isSingleWord()) {
01893     assert(RHS.VAL != 0 && "Remainder by zero?");
01894     return APInt(BitWidth, VAL % RHS.VAL);
01895   }
01896 
01897   // Get some facts about the LHS
01898   unsigned lhsBits = getActiveBits();
01899   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
01900 
01901   // Get some facts about the RHS
01902   unsigned rhsBits = RHS.getActiveBits();
01903   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01904   assert(rhsWords && "Performing remainder operation by zero ???");
01905 
01906   // Check the degenerate cases
01907   if (lhsWords == 0) {
01908     // 0 % Y ===> 0
01909     return APInt(BitWidth, 0);
01910   } else if (lhsWords < rhsWords || this->ult(RHS)) {
01911     // X % Y ===> X, iff X < Y
01912     return *this;
01913   } else if (*this == RHS) {
01914     // X % X == 0;
01915     return APInt(BitWidth, 0);
01916   } else if (lhsWords == 1) {
01917     // All high words are zero, just use native remainder
01918     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
01919   }
01920 
01921   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01922   APInt Remainder(1,0);
01923   divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
01924   return Remainder;
01925 }
01926 
01927 APInt APInt::srem(const APInt &RHS) const {
01928   if (isNegative()) {
01929     if (RHS.isNegative())
01930       return -((-(*this)).urem(-RHS));
01931     return -((-(*this)).urem(RHS));
01932   }
01933   if (RHS.isNegative())
01934     return this->urem(-RHS);
01935   return this->urem(RHS);
01936 }
01937 
01938 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
01939                     APInt &Quotient, APInt &Remainder) {
01940   // Get some size facts about the dividend and divisor
01941   unsigned lhsBits  = LHS.getActiveBits();
01942   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01943   unsigned rhsBits  = RHS.getActiveBits();
01944   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01945 
01946   // Check the degenerate cases
01947   if (lhsWords == 0) {
01948     Quotient = 0;                // 0 / Y ===> 0
01949     Remainder = 0;               // 0 % Y ===> 0
01950     return;
01951   }
01952 
01953   if (lhsWords < rhsWords || LHS.ult(RHS)) {
01954     Remainder = LHS;            // X % Y ===> X, iff X < Y
01955     Quotient = 0;               // X / Y ===> 0, iff X < Y
01956     return;
01957   }
01958 
01959   if (LHS == RHS) {
01960     Quotient  = 1;              // X / X ===> 1
01961     Remainder = 0;              // X % X ===> 0;
01962     return;
01963   }
01964 
01965   if (lhsWords == 1 && rhsWords == 1) {
01966     // There is only one word to consider so use the native versions.
01967     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
01968     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
01969     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
01970     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
01971     return;
01972   }
01973 
01974   // Okay, lets do it the long way
01975   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
01976 }
01977 
01978 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
01979                     APInt &Quotient, APInt &Remainder) {
01980   if (LHS.isNegative()) {
01981     if (RHS.isNegative())
01982       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
01983     else {
01984       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
01985       Quotient = -Quotient;
01986     }
01987     Remainder = -Remainder;
01988   } else if (RHS.isNegative()) {
01989     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
01990     Quotient = -Quotient;
01991   } else {
01992     APInt::udivrem(LHS, RHS, Quotient, Remainder);
01993   }
01994 }
01995 
01996 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
01997   APInt Res = *this+RHS;
01998   Overflow = isNonNegative() == RHS.isNonNegative() &&
01999              Res.isNonNegative() != isNonNegative();
02000   return Res;
02001 }
02002 
02003 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
02004   APInt Res = *this+RHS;
02005   Overflow = Res.ult(RHS);
02006   return Res;
02007 }
02008 
02009 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
02010   APInt Res = *this - RHS;
02011   Overflow = isNonNegative() != RHS.isNonNegative() &&
02012              Res.isNonNegative() != isNonNegative();
02013   return Res;
02014 }
02015 
02016 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
02017   APInt Res = *this-RHS;
02018   Overflow = Res.ugt(*this);
02019   return Res;
02020 }
02021 
02022 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
02023   // MININT/-1  -->  overflow.
02024   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
02025   return sdiv(RHS);
02026 }
02027 
02028 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
02029   APInt Res = *this * RHS;
02030   
02031   if (*this != 0 && RHS != 0)
02032     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
02033   else
02034     Overflow = false;
02035   return Res;
02036 }
02037 
02038 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
02039   APInt Res = *this * RHS;
02040 
02041   if (*this != 0 && RHS != 0)
02042     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
02043   else
02044     Overflow = false;
02045   return Res;
02046 }
02047 
02048 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
02049   Overflow = ShAmt >= getBitWidth();
02050   if (Overflow)
02051     ShAmt = getBitWidth()-1;
02052 
02053   if (isNonNegative()) // Don't allow sign change.
02054     Overflow = ShAmt >= countLeadingZeros();
02055   else
02056     Overflow = ShAmt >= countLeadingOnes();
02057   
02058   return *this << ShAmt;
02059 }
02060 
02061 
02062 
02063 
02064 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
02065   // Check our assumptions here
02066   assert(!str.empty() && "Invalid string length");
02067   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
02068           radix == 36) &&
02069          "Radix should be 2, 8, 10, 16, or 36!");
02070 
02071   StringRef::iterator p = str.begin();
02072   size_t slen = str.size();
02073   bool isNeg = *p == '-';
02074   if (*p == '-' || *p == '+') {
02075     p++;
02076     slen--;
02077     assert(slen && "String is only a sign, needs a value.");
02078   }
02079   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
02080   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
02081   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
02082   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
02083          "Insufficient bit width");
02084 
02085   // Allocate memory
02086   if (!isSingleWord())
02087     pVal = getClearedMemory(getNumWords());
02088 
02089   // Figure out if we can shift instead of multiply
02090   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
02091 
02092   // Set up an APInt for the digit to add outside the loop so we don't
02093   // constantly construct/destruct it.
02094   APInt apdigit(getBitWidth(), 0);
02095   APInt apradix(getBitWidth(), radix);
02096 
02097   // Enter digit traversal loop
02098   for (StringRef::iterator e = str.end(); p != e; ++p) {
02099     unsigned digit = getDigit(*p, radix);
02100     assert(digit < radix && "Invalid character in digit string");
02101 
02102     // Shift or multiply the value by the radix
02103     if (slen > 1) {
02104       if (shift)
02105         *this <<= shift;
02106       else
02107         *this *= apradix;
02108     }
02109 
02110     // Add in the digit we just interpreted
02111     if (apdigit.isSingleWord())
02112       apdigit.VAL = digit;
02113     else
02114       apdigit.pVal[0] = digit;
02115     *this += apdigit;
02116   }
02117   // If its negative, put it in two's complement form
02118   if (isNeg) {
02119     --(*this);
02120     this->flipAllBits();
02121   }
02122 }
02123 
02124 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
02125                      bool Signed, bool formatAsCLiteral) const {
02126   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 
02127           Radix == 36) &&
02128          "Radix should be 2, 8, 10, 16, or 36!");
02129 
02130   const char *Prefix = "";
02131   if (formatAsCLiteral) {
02132     switch (Radix) {
02133       case 2:
02134         // Binary literals are a non-standard extension added in gcc 4.3:
02135         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
02136         Prefix = "0b";
02137         break;
02138       case 8:
02139         Prefix = "0";
02140         break;
02141       case 10:
02142         break; // No prefix
02143       case 16:
02144         Prefix = "0x";
02145         break;
02146       default:
02147         llvm_unreachable("Invalid radix!");
02148     }
02149   }
02150 
02151   // First, check for a zero value and just short circuit the logic below.
02152   if (*this == 0) {
02153     while (*Prefix) {
02154       Str.push_back(*Prefix);
02155       ++Prefix;
02156     };
02157     Str.push_back('0');
02158     return;
02159   }
02160 
02161   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
02162 
02163   if (isSingleWord()) {
02164     char Buffer[65];
02165     char *BufPtr = Buffer+65;
02166 
02167     uint64_t N;
02168     if (!Signed) {
02169       N = getZExtValue();
02170     } else {
02171       int64_t I = getSExtValue();
02172       if (I >= 0) {
02173         N = I;
02174       } else {
02175         Str.push_back('-');
02176         N = -(uint64_t)I;
02177       }
02178     }
02179 
02180     while (*Prefix) {
02181       Str.push_back(*Prefix);
02182       ++Prefix;
02183     };
02184 
02185     while (N) {
02186       *--BufPtr = Digits[N % Radix];
02187       N /= Radix;
02188     }
02189     Str.append(BufPtr, Buffer+65);
02190     return;
02191   }
02192 
02193   APInt Tmp(*this);
02194 
02195   if (Signed && isNegative()) {
02196     // They want to print the signed version and it is a negative value
02197     // Flip the bits and add one to turn it into the equivalent positive
02198     // value and put a '-' in the result.
02199     Tmp.flipAllBits();
02200     ++Tmp;
02201     Str.push_back('-');
02202   }
02203 
02204   while (*Prefix) {
02205     Str.push_back(*Prefix);
02206     ++Prefix;
02207   };
02208 
02209   // We insert the digits backward, then reverse them to get the right order.
02210   unsigned StartDig = Str.size();
02211 
02212   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
02213   // because the number of bits per digit (1, 3 and 4 respectively) divides
02214   // equaly.  We just shift until the value is zero.
02215   if (Radix == 2 || Radix == 8 || Radix == 16) {
02216     // Just shift tmp right for each digit width until it becomes zero
02217     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
02218     unsigned MaskAmt = Radix - 1;
02219 
02220     while (Tmp != 0) {
02221       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
02222       Str.push_back(Digits[Digit]);
02223       Tmp = Tmp.lshr(ShiftAmt);
02224     }
02225   } else {
02226     APInt divisor(Radix == 10? 4 : 8, Radix);
02227     while (Tmp != 0) {
02228       APInt APdigit(1, 0);
02229       APInt tmp2(Tmp.getBitWidth(), 0);
02230       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
02231              &APdigit);
02232       unsigned Digit = (unsigned)APdigit.getZExtValue();
02233       assert(Digit < Radix && "divide failed");
02234       Str.push_back(Digits[Digit]);
02235       Tmp = tmp2;
02236     }
02237   }
02238 
02239   // Reverse the digits before returning.
02240   std::reverse(Str.begin()+StartDig, Str.end());
02241 }
02242 
02243 /// toString - This returns the APInt as a std::string.  Note that this is an
02244 /// inefficient method.  It is better to pass in a SmallVector/SmallString
02245 /// to the methods above.
02246 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
02247   SmallString<40> S;
02248   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
02249   return S.str();
02250 }
02251 
02252 
02253 void APInt::dump() const {
02254   SmallString<40> S, U;
02255   this->toStringUnsigned(U);
02256   this->toStringSigned(S);
02257   dbgs() << "APInt(" << BitWidth << "b, "
02258          << U.str() << "u " << S.str() << "s)";
02259 }
02260 
02261 void APInt::print(raw_ostream &OS, bool isSigned) const {
02262   SmallString<40> S;
02263   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
02264   OS << S.str();
02265 }
02266 
02267 // This implements a variety of operations on a representation of
02268 // arbitrary precision, two's-complement, bignum integer values.
02269 
02270 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
02271 // and unrestricting assumption.
02272 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
02273 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
02274 
02275 /* Some handy functions local to this file.  */
02276 namespace {
02277 
02278   /* Returns the integer part with the least significant BITS set.
02279      BITS cannot be zero.  */
02280   static inline integerPart
02281   lowBitMask(unsigned int bits)
02282   {
02283     assert(bits != 0 && bits <= integerPartWidth);
02284 
02285     return ~(integerPart) 0 >> (integerPartWidth - bits);
02286   }
02287 
02288   /* Returns the value of the lower half of PART.  */
02289   static inline integerPart
02290   lowHalf(integerPart part)
02291   {
02292     return part & lowBitMask(integerPartWidth / 2);
02293   }
02294 
02295   /* Returns the value of the upper half of PART.  */
02296   static inline integerPart
02297   highHalf(integerPart part)
02298   {
02299     return part >> (integerPartWidth / 2);
02300   }
02301 
02302   /* Returns the bit number of the most significant set bit of a part.
02303      If the input number has no bits set -1U is returned.  */
02304   static unsigned int
02305   partMSB(integerPart value)
02306   {
02307     return findLastSet(value, ZB_Max);
02308   }
02309 
02310   /* Returns the bit number of the least significant set bit of a
02311      part.  If the input number has no bits set -1U is returned.  */
02312   static unsigned int
02313   partLSB(integerPart value)
02314   {
02315     return findFirstSet(value, ZB_Max);
02316   }
02317 }
02318 
02319 /* Sets the least significant part of a bignum to the input value, and
02320    zeroes out higher parts.  */
02321 void
02322 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
02323 {
02324   unsigned int i;
02325 
02326   assert(parts > 0);
02327 
02328   dst[0] = part;
02329   for (i = 1; i < parts; i++)
02330     dst[i] = 0;
02331 }
02332 
02333 /* Assign one bignum to another.  */
02334 void
02335 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
02336 {
02337   unsigned int i;
02338 
02339   for (i = 0; i < parts; i++)
02340     dst[i] = src[i];
02341 }
02342 
02343 /* Returns true if a bignum is zero, false otherwise.  */
02344 bool
02345 APInt::tcIsZero(const integerPart *src, unsigned int parts)
02346 {
02347   unsigned int i;
02348 
02349   for (i = 0; i < parts; i++)
02350     if (src[i])
02351       return false;
02352 
02353   return true;
02354 }
02355 
02356 /* Extract the given bit of a bignum; returns 0 or 1.  */
02357 int
02358 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
02359 {
02360   return (parts[bit / integerPartWidth] &
02361           ((integerPart) 1 << bit % integerPartWidth)) != 0;
02362 }
02363 
02364 /* Set the given bit of a bignum. */
02365 void
02366 APInt::tcSetBit(integerPart *parts, unsigned int bit)
02367 {
02368   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
02369 }
02370 
02371 /* Clears the given bit of a bignum. */
02372 void
02373 APInt::tcClearBit(integerPart *parts, unsigned int bit)
02374 {
02375   parts[bit / integerPartWidth] &=
02376     ~((integerPart) 1 << (bit % integerPartWidth));
02377 }
02378 
02379 /* Returns the bit number of the least significant set bit of a
02380    number.  If the input number has no bits set -1U is returned.  */
02381 unsigned int
02382 APInt::tcLSB(const integerPart *parts, unsigned int n)
02383 {
02384   unsigned int i, lsb;
02385 
02386   for (i = 0; i < n; i++) {
02387       if (parts[i] != 0) {
02388           lsb = partLSB(parts[i]);
02389 
02390           return lsb + i * integerPartWidth;
02391       }
02392   }
02393 
02394   return -1U;
02395 }
02396 
02397 /* Returns the bit number of the most significant set bit of a number.
02398    If the input number has no bits set -1U is returned.  */
02399 unsigned int
02400 APInt::tcMSB(const integerPart *parts, unsigned int n)
02401 {
02402   unsigned int msb;
02403 
02404   do {
02405     --n;
02406 
02407     if (parts[n] != 0) {
02408       msb = partMSB(parts[n]);
02409 
02410       return msb + n * integerPartWidth;
02411     }
02412   } while (n);
02413 
02414   return -1U;
02415 }
02416 
02417 /* Copy the bit vector of width srcBITS from SRC, starting at bit
02418    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
02419    the least significant bit of DST.  All high bits above srcBITS in
02420    DST are zero-filled.  */
02421 void
02422 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
02423                  unsigned int srcBits, unsigned int srcLSB)
02424 {
02425   unsigned int firstSrcPart, dstParts, shift, n;
02426 
02427   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
02428   assert(dstParts <= dstCount);
02429 
02430   firstSrcPart = srcLSB / integerPartWidth;
02431   tcAssign (dst, src + firstSrcPart, dstParts);
02432 
02433   shift = srcLSB % integerPartWidth;
02434   tcShiftRight (dst, dstParts, shift);
02435 
02436   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
02437      in DST.  If this is less that srcBits, append the rest, else
02438      clear the high bits.  */
02439   n = dstParts * integerPartWidth - shift;
02440   if (n < srcBits) {
02441     integerPart mask = lowBitMask (srcBits - n);
02442     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
02443                           << n % integerPartWidth);
02444   } else if (n > srcBits) {
02445     if (srcBits % integerPartWidth)
02446       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
02447   }
02448 
02449   /* Clear high parts.  */
02450   while (dstParts < dstCount)
02451     dst[dstParts++] = 0;
02452 }
02453 
02454 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
02455 integerPart
02456 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
02457              integerPart c, unsigned int parts)
02458 {
02459   unsigned int i;
02460 
02461   assert(c <= 1);
02462 
02463   for (i = 0; i < parts; i++) {
02464     integerPart l;
02465 
02466     l = dst[i];
02467     if (c) {
02468       dst[i] += rhs[i] + 1;
02469       c = (dst[i] <= l);
02470     } else {
02471       dst[i] += rhs[i];
02472       c = (dst[i] < l);
02473     }
02474   }
02475 
02476   return c;
02477 }
02478 
02479 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
02480 integerPart
02481 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
02482                   integerPart c, unsigned int parts)
02483 {
02484   unsigned int i;
02485 
02486   assert(c <= 1);
02487 
02488   for (i = 0; i < parts; i++) {
02489     integerPart l;
02490 
02491     l = dst[i];
02492     if (c) {
02493       dst[i] -= rhs[i] + 1;
02494       c = (dst[i] >= l);
02495     } else {
02496       dst[i] -= rhs[i];
02497       c = (dst[i] > l);
02498     }
02499   }
02500 
02501   return c;
02502 }
02503 
02504 /* Negate a bignum in-place.  */
02505 void
02506 APInt::tcNegate(integerPart *dst, unsigned int parts)
02507 {
02508   tcComplement(dst, parts);
02509   tcIncrement(dst, parts);
02510 }
02511 
02512 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
02513     DST  = SRC * MULTIPLIER + CARRY   if add is false
02514 
02515     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
02516     they must start at the same point, i.e. DST == SRC.
02517 
02518     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
02519     returned.  Otherwise DST is filled with the least significant
02520     DSTPARTS parts of the result, and if all of the omitted higher
02521     parts were zero return zero, otherwise overflow occurred and
02522     return one.  */
02523 int
02524 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
02525                       integerPart multiplier, integerPart carry,
02526                       unsigned int srcParts, unsigned int dstParts,
02527                       bool add)
02528 {
02529   unsigned int i, n;
02530 
02531   /* Otherwise our writes of DST kill our later reads of SRC.  */
02532   assert(dst <= src || dst >= src + srcParts);
02533   assert(dstParts <= srcParts + 1);
02534 
02535   /* N loops; minimum of dstParts and srcParts.  */
02536   n = dstParts < srcParts ? dstParts: srcParts;
02537 
02538   for (i = 0; i < n; i++) {
02539     integerPart low, mid, high, srcPart;
02540 
02541       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
02542 
02543          This cannot overflow, because
02544 
02545          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
02546 
02547          which is less than n^2.  */
02548 
02549     srcPart = src[i];
02550 
02551     if (multiplier == 0 || srcPart == 0)        {
02552       low = carry;
02553       high = 0;
02554     } else {
02555       low = lowHalf(srcPart) * lowHalf(multiplier);
02556       high = highHalf(srcPart) * highHalf(multiplier);
02557 
02558       mid = lowHalf(srcPart) * highHalf(multiplier);
02559       high += highHalf(mid);
02560       mid <<= integerPartWidth / 2;
02561       if (low + mid < low)
02562         high++;
02563       low += mid;
02564 
02565       mid = highHalf(srcPart) * lowHalf(multiplier);
02566       high += highHalf(mid);
02567       mid <<= integerPartWidth / 2;
02568       if (low + mid < low)
02569         high++;
02570       low += mid;
02571 
02572       /* Now add carry.  */
02573       if (low + carry < low)
02574         high++;
02575       low += carry;
02576     }
02577 
02578     if (add) {
02579       /* And now DST[i], and store the new low part there.  */
02580       if (low + dst[i] < low)
02581         high++;
02582       dst[i] += low;
02583     } else
02584       dst[i] = low;
02585 
02586     carry = high;
02587   }
02588 
02589   if (i < dstParts) {
02590     /* Full multiplication, there is no overflow.  */
02591     assert(i + 1 == dstParts);
02592     dst[i] = carry;
02593     return 0;
02594   } else {
02595     /* We overflowed if there is carry.  */
02596     if (carry)
02597       return 1;
02598 
02599     /* We would overflow if any significant unwritten parts would be
02600        non-zero.  This is true if any remaining src parts are non-zero
02601        and the multiplier is non-zero.  */
02602     if (multiplier)
02603       for (; i < srcParts; i++)
02604         if (src[i])
02605           return 1;
02606 
02607     /* We fitted in the narrow destination.  */
02608     return 0;
02609   }
02610 }
02611 
02612 /* DST = LHS * RHS, where DST has the same width as the operands and
02613    is filled with the least significant parts of the result.  Returns
02614    one if overflow occurred, otherwise zero.  DST must be disjoint
02615    from both operands.  */
02616 int
02617 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
02618                   const integerPart *rhs, unsigned int parts)
02619 {
02620   unsigned int i;
02621   int overflow;
02622 
02623   assert(dst != lhs && dst != rhs);
02624 
02625   overflow = 0;
02626   tcSet(dst, 0, parts);
02627 
02628   for (i = 0; i < parts; i++)
02629     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
02630                                parts - i, true);
02631 
02632   return overflow;
02633 }
02634 
02635 /* DST = LHS * RHS, where DST has width the sum of the widths of the
02636    operands.  No overflow occurs.  DST must be disjoint from both
02637    operands.  Returns the number of parts required to hold the
02638    result.  */
02639 unsigned int
02640 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
02641                       const integerPart *rhs, unsigned int lhsParts,
02642                       unsigned int rhsParts)
02643 {
02644   /* Put the narrower number on the LHS for less loops below.  */
02645   if (lhsParts > rhsParts) {
02646     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
02647   } else {
02648     unsigned int n;
02649 
02650     assert(dst != lhs && dst != rhs);
02651 
02652     tcSet(dst, 0, rhsParts);
02653 
02654     for (n = 0; n < lhsParts; n++)
02655       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
02656 
02657     n = lhsParts + rhsParts;
02658 
02659     return n - (dst[n - 1] == 0);
02660   }
02661 }
02662 
02663 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
02664    Otherwise set LHS to LHS / RHS with the fractional part discarded,
02665    set REMAINDER to the remainder, return zero.  i.e.
02666 
02667    OLD_LHS = RHS * LHS + REMAINDER
02668 
02669    SCRATCH is a bignum of the same size as the operands and result for
02670    use by the routine; its contents need not be initialized and are
02671    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
02672 */
02673 int
02674 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
02675                 integerPart *remainder, integerPart *srhs,
02676                 unsigned int parts)
02677 {
02678   unsigned int n, shiftCount;
02679   integerPart mask;
02680 
02681   assert(lhs != remainder && lhs != srhs && remainder != srhs);
02682 
02683   shiftCount = tcMSB(rhs, parts) + 1;
02684   if (shiftCount == 0)
02685     return true;
02686 
02687   shiftCount = parts * integerPartWidth - shiftCount;
02688   n = shiftCount / integerPartWidth;
02689   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
02690 
02691   tcAssign(srhs, rhs, parts);
02692   tcShiftLeft(srhs, parts, shiftCount);
02693   tcAssign(remainder, lhs, parts);
02694   tcSet(lhs, 0, parts);
02695 
02696   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
02697      the total.  */
02698   for (;;) {
02699       int compare;
02700 
02701       compare = tcCompare(remainder, srhs, parts);
02702       if (compare >= 0) {
02703         tcSubtract(remainder, srhs, 0, parts);
02704         lhs[n] |= mask;
02705       }
02706 
02707       if (shiftCount == 0)
02708         break;
02709       shiftCount--;
02710       tcShiftRight(srhs, parts, 1);
02711       if ((mask >>= 1) == 0)
02712         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
02713   }
02714 
02715   return false;
02716 }
02717 
02718 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
02719    There are no restrictions on COUNT.  */
02720 void
02721 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
02722 {
02723   if (count) {
02724     unsigned int jump, shift;
02725 
02726     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02727     jump = count / integerPartWidth;
02728     shift = count % integerPartWidth;
02729 
02730     while (parts > jump) {
02731       integerPart part;
02732 
02733       parts--;
02734 
02735       /* dst[i] comes from the two parts src[i - jump] and, if we have
02736          an intra-part shift, src[i - jump - 1].  */
02737       part = dst[parts - jump];
02738       if (shift) {
02739         part <<= shift;
02740         if (parts >= jump + 1)
02741           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
02742       }
02743 
02744       dst[parts] = part;
02745     }
02746 
02747     while (parts > 0)
02748       dst[--parts] = 0;
02749   }
02750 }
02751 
02752 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
02753    zero.  There are no restrictions on COUNT.  */
02754 void
02755 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
02756 {
02757   if (count) {
02758     unsigned int i, jump, shift;
02759 
02760     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02761     jump = count / integerPartWidth;
02762     shift = count % integerPartWidth;
02763 
02764     /* Perform the shift.  This leaves the most significant COUNT bits
02765        of the result at zero.  */
02766     for (i = 0; i < parts; i++) {
02767       integerPart part;
02768 
02769       if (i + jump >= parts) {
02770         part = 0;
02771       } else {
02772         part = dst[i + jump];
02773         if (shift) {
02774           part >>= shift;
02775           if (i + jump + 1 < parts)
02776             part |= dst[i + jump + 1] << (integerPartWidth - shift);
02777         }
02778       }
02779 
02780       dst[i] = part;
02781     }
02782   }
02783 }
02784 
02785 /* Bitwise and of two bignums.  */
02786 void
02787 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
02788 {
02789   unsigned int i;
02790 
02791   for (i = 0; i < parts; i++)
02792     dst[i] &= rhs[i];
02793 }
02794 
02795 /* Bitwise inclusive or of two bignums.  */
02796 void
02797 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
02798 {
02799   unsigned int i;
02800 
02801   for (i = 0; i < parts; i++)
02802     dst[i] |= rhs[i];
02803 }
02804 
02805 /* Bitwise exclusive or of two bignums.  */
02806 void
02807 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
02808 {
02809   unsigned int i;
02810 
02811   for (i = 0; i < parts; i++)
02812     dst[i] ^= rhs[i];
02813 }
02814 
02815 /* Complement a bignum in-place.  */
02816 void
02817 APInt::tcComplement(integerPart *dst, unsigned int parts)
02818 {
02819   unsigned int i;
02820 
02821   for (i = 0; i < parts; i++)
02822     dst[i] = ~dst[i];
02823 }
02824 
02825 /* Comparison (unsigned) of two bignums.  */
02826 int
02827 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
02828                  unsigned int parts)
02829 {
02830   while (parts) {
02831       parts--;
02832       if (lhs[parts] == rhs[parts])
02833         continue;
02834 
02835       if (lhs[parts] > rhs[parts])
02836         return 1;
02837       else
02838         return -1;
02839     }
02840 
02841   return 0;
02842 }
02843 
02844 /* Increment a bignum in-place, return the carry flag.  */
02845 integerPart
02846 APInt::tcIncrement(integerPart *dst, unsigned int parts)
02847 {
02848   unsigned int i;
02849 
02850   for (i = 0; i < parts; i++)
02851     if (++dst[i] != 0)
02852       break;
02853 
02854   return i == parts;
02855 }
02856 
02857 /* Decrement a bignum in-place, return the borrow flag.  */
02858 integerPart
02859 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
02860   for (unsigned int i = 0; i < parts; i++) {
02861     // If the current word is non-zero, then the decrement has no effect on the
02862     // higher-order words of the integer and no borrow can occur. Exit early.
02863     if (dst[i]--)
02864       return 0;
02865   }
02866   // If every word was zero, then there is a borrow.
02867   return 1;
02868 }
02869 
02870 
02871 /* Set the least significant BITS bits of a bignum, clear the
02872    rest.  */
02873 void
02874 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
02875                                  unsigned int bits)
02876 {
02877   unsigned int i;
02878 
02879   i = 0;
02880   while (bits > integerPartWidth) {
02881     dst[i++] = ~(integerPart) 0;
02882     bits -= integerPartWidth;
02883   }
02884 
02885   if (bits)
02886     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
02887 
02888   while (i < parts)
02889     dst[i++] = 0;
02890 }