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