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