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   // Get some size facts about the dividend and divisor
01960   unsigned lhsBits  = LHS.getActiveBits();
01961   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01962   unsigned rhsBits  = RHS.getActiveBits();
01963   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01964 
01965   // Check the degenerate cases
01966   if (lhsWords == 0) {
01967     Quotient = 0;                // 0 / Y ===> 0
01968     Remainder = 0;               // 0 % Y ===> 0
01969     return;
01970   }
01971 
01972   if (lhsWords < rhsWords || LHS.ult(RHS)) {
01973     Remainder = LHS;            // X % Y ===> X, iff X < Y
01974     Quotient = 0;               // X / Y ===> 0, iff X < Y
01975     return;
01976   }
01977 
01978   if (LHS == RHS) {
01979     Quotient  = 1;              // X / X ===> 1
01980     Remainder = 0;              // X % X ===> 0;
01981     return;
01982   }
01983 
01984   if (lhsWords == 1 && rhsWords == 1) {
01985     // There is only one word to consider so use the native versions.
01986     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
01987     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
01988     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
01989     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
01990     return;
01991   }
01992 
01993   // Okay, lets do it the long way
01994   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
01995 }
01996 
01997 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
01998                     APInt &Quotient, APInt &Remainder) {
01999   if (LHS.isNegative()) {
02000     if (RHS.isNegative())
02001       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
02002     else {
02003       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
02004       Quotient = -Quotient;
02005     }
02006     Remainder = -Remainder;
02007   } else if (RHS.isNegative()) {
02008     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
02009     Quotient = -Quotient;
02010   } else {
02011     APInt::udivrem(LHS, RHS, Quotient, Remainder);
02012   }
02013 }
02014 
02015 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
02016   APInt Res = *this+RHS;
02017   Overflow = isNonNegative() == RHS.isNonNegative() &&
02018              Res.isNonNegative() != isNonNegative();
02019   return Res;
02020 }
02021 
02022 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
02023   APInt Res = *this+RHS;
02024   Overflow = Res.ult(RHS);
02025   return Res;
02026 }
02027 
02028 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
02029   APInt Res = *this - RHS;
02030   Overflow = isNonNegative() != RHS.isNonNegative() &&
02031              Res.isNonNegative() != isNonNegative();
02032   return Res;
02033 }
02034 
02035 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
02036   APInt Res = *this-RHS;
02037   Overflow = Res.ugt(*this);
02038   return Res;
02039 }
02040 
02041 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
02042   // MININT/-1  -->  overflow.
02043   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
02044   return sdiv(RHS);
02045 }
02046 
02047 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
02048   APInt Res = *this * RHS;
02049   
02050   if (*this != 0 && RHS != 0)
02051     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
02052   else
02053     Overflow = false;
02054   return Res;
02055 }
02056 
02057 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
02058   APInt Res = *this * RHS;
02059 
02060   if (*this != 0 && RHS != 0)
02061     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
02062   else
02063     Overflow = false;
02064   return Res;
02065 }
02066 
02067 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
02068   Overflow = ShAmt.uge(getBitWidth());
02069   if (Overflow)
02070     return APInt(BitWidth, 0);
02071 
02072   if (isNonNegative()) // Don't allow sign change.
02073     Overflow = ShAmt.uge(countLeadingZeros());
02074   else
02075     Overflow = ShAmt.uge(countLeadingOnes());
02076   
02077   return *this << ShAmt;
02078 }
02079 
02080 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
02081   Overflow = ShAmt.uge(getBitWidth());
02082   if (Overflow)
02083     return APInt(BitWidth, 0);
02084 
02085   Overflow = ShAmt.ugt(countLeadingZeros());
02086 
02087   return *this << ShAmt;
02088 }
02089 
02090 
02091 
02092 
02093 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
02094   // Check our assumptions here
02095   assert(!str.empty() && "Invalid string length");
02096   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
02097           radix == 36) &&
02098          "Radix should be 2, 8, 10, 16, or 36!");
02099 
02100   StringRef::iterator p = str.begin();
02101   size_t slen = str.size();
02102   bool isNeg = *p == '-';
02103   if (*p == '-' || *p == '+') {
02104     p++;
02105     slen--;
02106     assert(slen && "String is only a sign, needs a value.");
02107   }
02108   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
02109   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
02110   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
02111   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
02112          "Insufficient bit width");
02113 
02114   // Allocate memory
02115   if (!isSingleWord())
02116     pVal = getClearedMemory(getNumWords());
02117 
02118   // Figure out if we can shift instead of multiply
02119   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
02120 
02121   // Set up an APInt for the digit to add outside the loop so we don't
02122   // constantly construct/destruct it.
02123   APInt apdigit(getBitWidth(), 0);
02124   APInt apradix(getBitWidth(), radix);
02125 
02126   // Enter digit traversal loop
02127   for (StringRef::iterator e = str.end(); p != e; ++p) {
02128     unsigned digit = getDigit(*p, radix);
02129     assert(digit < radix && "Invalid character in digit string");
02130 
02131     // Shift or multiply the value by the radix
02132     if (slen > 1) {
02133       if (shift)
02134         *this <<= shift;
02135       else
02136         *this *= apradix;
02137     }
02138 
02139     // Add in the digit we just interpreted
02140     if (apdigit.isSingleWord())
02141       apdigit.VAL = digit;
02142     else
02143       apdigit.pVal[0] = digit;
02144     *this += apdigit;
02145   }
02146   // If its negative, put it in two's complement form
02147   if (isNeg) {
02148     --(*this);
02149     this->flipAllBits();
02150   }
02151 }
02152 
02153 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
02154                      bool Signed, bool formatAsCLiteral) const {
02155   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 
02156           Radix == 36) &&
02157          "Radix should be 2, 8, 10, 16, or 36!");
02158 
02159   const char *Prefix = "";
02160   if (formatAsCLiteral) {
02161     switch (Radix) {
02162       case 2:
02163         // Binary literals are a non-standard extension added in gcc 4.3:
02164         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
02165         Prefix = "0b";
02166         break;
02167       case 8:
02168         Prefix = "0";
02169         break;
02170       case 10:
02171         break; // No prefix
02172       case 16:
02173         Prefix = "0x";
02174         break;
02175       default:
02176         llvm_unreachable("Invalid radix!");
02177     }
02178   }
02179 
02180   // First, check for a zero value and just short circuit the logic below.
02181   if (*this == 0) {
02182     while (*Prefix) {
02183       Str.push_back(*Prefix);
02184       ++Prefix;
02185     };
02186     Str.push_back('0');
02187     return;
02188   }
02189 
02190   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
02191 
02192   if (isSingleWord()) {
02193     char Buffer[65];
02194     char *BufPtr = Buffer+65;
02195 
02196     uint64_t N;
02197     if (!Signed) {
02198       N = getZExtValue();
02199     } else {
02200       int64_t I = getSExtValue();
02201       if (I >= 0) {
02202         N = I;
02203       } else {
02204         Str.push_back('-');
02205         N = -(uint64_t)I;
02206       }
02207     }
02208 
02209     while (*Prefix) {
02210       Str.push_back(*Prefix);
02211       ++Prefix;
02212     };
02213 
02214     while (N) {
02215       *--BufPtr = Digits[N % Radix];
02216       N /= Radix;
02217     }
02218     Str.append(BufPtr, Buffer+65);
02219     return;
02220   }
02221 
02222   APInt Tmp(*this);
02223 
02224   if (Signed && isNegative()) {
02225     // They want to print the signed version and it is a negative value
02226     // Flip the bits and add one to turn it into the equivalent positive
02227     // value and put a '-' in the result.
02228     Tmp.flipAllBits();
02229     ++Tmp;
02230     Str.push_back('-');
02231   }
02232 
02233   while (*Prefix) {
02234     Str.push_back(*Prefix);
02235     ++Prefix;
02236   };
02237 
02238   // We insert the digits backward, then reverse them to get the right order.
02239   unsigned StartDig = Str.size();
02240 
02241   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
02242   // because the number of bits per digit (1, 3 and 4 respectively) divides
02243   // equaly.  We just shift until the value is zero.
02244   if (Radix == 2 || Radix == 8 || Radix == 16) {
02245     // Just shift tmp right for each digit width until it becomes zero
02246     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
02247     unsigned MaskAmt = Radix - 1;
02248 
02249     while (Tmp != 0) {
02250       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
02251       Str.push_back(Digits[Digit]);
02252       Tmp = Tmp.lshr(ShiftAmt);
02253     }
02254   } else {
02255     APInt divisor(Radix == 10? 4 : 8, Radix);
02256     while (Tmp != 0) {
02257       APInt APdigit(1, 0);
02258       APInt tmp2(Tmp.getBitWidth(), 0);
02259       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
02260              &APdigit);
02261       unsigned Digit = (unsigned)APdigit.getZExtValue();
02262       assert(Digit < Radix && "divide failed");
02263       Str.push_back(Digits[Digit]);
02264       Tmp = tmp2;
02265     }
02266   }
02267 
02268   // Reverse the digits before returning.
02269   std::reverse(Str.begin()+StartDig, Str.end());
02270 }
02271 
02272 /// toString - This returns the APInt as a std::string.  Note that this is an
02273 /// inefficient method.  It is better to pass in a SmallVector/SmallString
02274 /// to the methods above.
02275 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
02276   SmallString<40> S;
02277   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
02278   return S.str();
02279 }
02280 
02281 
02282 void APInt::dump() const {
02283   SmallString<40> S, U;
02284   this->toStringUnsigned(U);
02285   this->toStringSigned(S);
02286   dbgs() << "APInt(" << BitWidth << "b, "
02287          << U.str() << "u " << S.str() << "s)";
02288 }
02289 
02290 void APInt::print(raw_ostream &OS, bool isSigned) const {
02291   SmallString<40> S;
02292   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
02293   OS << S.str();
02294 }
02295 
02296 // This implements a variety of operations on a representation of
02297 // arbitrary precision, two's-complement, bignum integer values.
02298 
02299 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
02300 // and unrestricting assumption.
02301 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
02302 
02303 /* Some handy functions local to this file.  */
02304 namespace {
02305 
02306   /* Returns the integer part with the least significant BITS set.
02307      BITS cannot be zero.  */
02308   static inline integerPart
02309   lowBitMask(unsigned int bits)
02310   {
02311     assert(bits != 0 && bits <= integerPartWidth);
02312 
02313     return ~(integerPart) 0 >> (integerPartWidth - bits);
02314   }
02315 
02316   /* Returns the value of the lower half of PART.  */
02317   static inline integerPart
02318   lowHalf(integerPart part)
02319   {
02320     return part & lowBitMask(integerPartWidth / 2);
02321   }
02322 
02323   /* Returns the value of the upper half of PART.  */
02324   static inline integerPart
02325   highHalf(integerPart part)
02326   {
02327     return part >> (integerPartWidth / 2);
02328   }
02329 
02330   /* Returns the bit number of the most significant set bit of a part.
02331      If the input number has no bits set -1U is returned.  */
02332   static unsigned int
02333   partMSB(integerPart value)
02334   {
02335     return findLastSet(value, ZB_Max);
02336   }
02337 
02338   /* Returns the bit number of the least significant set bit of a
02339      part.  If the input number has no bits set -1U is returned.  */
02340   static unsigned int
02341   partLSB(integerPart value)
02342   {
02343     return findFirstSet(value, ZB_Max);
02344   }
02345 }
02346 
02347 /* Sets the least significant part of a bignum to the input value, and
02348    zeroes out higher parts.  */
02349 void
02350 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
02351 {
02352   unsigned int i;
02353 
02354   assert(parts > 0);
02355 
02356   dst[0] = part;
02357   for (i = 1; i < parts; i++)
02358     dst[i] = 0;
02359 }
02360 
02361 /* Assign one bignum to another.  */
02362 void
02363 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
02364 {
02365   unsigned int i;
02366 
02367   for (i = 0; i < parts; i++)
02368     dst[i] = src[i];
02369 }
02370 
02371 /* Returns true if a bignum is zero, false otherwise.  */
02372 bool
02373 APInt::tcIsZero(const integerPart *src, unsigned int parts)
02374 {
02375   unsigned int i;
02376 
02377   for (i = 0; i < parts; i++)
02378     if (src[i])
02379       return false;
02380 
02381   return true;
02382 }
02383 
02384 /* Extract the given bit of a bignum; returns 0 or 1.  */
02385 int
02386 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
02387 {
02388   return (parts[bit / integerPartWidth] &
02389           ((integerPart) 1 << bit % integerPartWidth)) != 0;
02390 }
02391 
02392 /* Set the given bit of a bignum. */
02393 void
02394 APInt::tcSetBit(integerPart *parts, unsigned int bit)
02395 {
02396   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
02397 }
02398 
02399 /* Clears the given bit of a bignum. */
02400 void
02401 APInt::tcClearBit(integerPart *parts, unsigned int bit)
02402 {
02403   parts[bit / integerPartWidth] &=
02404     ~((integerPart) 1 << (bit % integerPartWidth));
02405 }
02406 
02407 /* Returns the bit number of the least significant set bit of a
02408    number.  If the input number has no bits set -1U is returned.  */
02409 unsigned int
02410 APInt::tcLSB(const integerPart *parts, unsigned int n)
02411 {
02412   unsigned int i, lsb;
02413 
02414   for (i = 0; i < n; i++) {
02415       if (parts[i] != 0) {
02416           lsb = partLSB(parts[i]);
02417 
02418           return lsb + i * integerPartWidth;
02419       }
02420   }
02421 
02422   return -1U;
02423 }
02424 
02425 /* Returns the bit number of the most significant set bit of a number.
02426    If the input number has no bits set -1U is returned.  */
02427 unsigned int
02428 APInt::tcMSB(const integerPart *parts, unsigned int n)
02429 {
02430   unsigned int msb;
02431 
02432   do {
02433     --n;
02434 
02435     if (parts[n] != 0) {
02436       msb = partMSB(parts[n]);
02437 
02438       return msb + n * integerPartWidth;
02439     }
02440   } while (n);
02441 
02442   return -1U;
02443 }
02444 
02445 /* Copy the bit vector of width srcBITS from SRC, starting at bit
02446    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
02447    the least significant bit of DST.  All high bits above srcBITS in
02448    DST are zero-filled.  */
02449 void
02450 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
02451                  unsigned int srcBits, unsigned int srcLSB)
02452 {
02453   unsigned int firstSrcPart, dstParts, shift, n;
02454 
02455   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
02456   assert(dstParts <= dstCount);
02457 
02458   firstSrcPart = srcLSB / integerPartWidth;
02459   tcAssign (dst, src + firstSrcPart, dstParts);
02460 
02461   shift = srcLSB % integerPartWidth;
02462   tcShiftRight (dst, dstParts, shift);
02463 
02464   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
02465      in DST.  If this is less that srcBits, append the rest, else
02466      clear the high bits.  */
02467   n = dstParts * integerPartWidth - shift;
02468   if (n < srcBits) {
02469     integerPart mask = lowBitMask (srcBits - n);
02470     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
02471                           << n % integerPartWidth);
02472   } else if (n > srcBits) {
02473     if (srcBits % integerPartWidth)
02474       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
02475   }
02476 
02477   /* Clear high parts.  */
02478   while (dstParts < dstCount)
02479     dst[dstParts++] = 0;
02480 }
02481 
02482 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
02483 integerPart
02484 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
02485              integerPart c, unsigned int parts)
02486 {
02487   unsigned int i;
02488 
02489   assert(c <= 1);
02490 
02491   for (i = 0; i < parts; i++) {
02492     integerPart l;
02493 
02494     l = dst[i];
02495     if (c) {
02496       dst[i] += rhs[i] + 1;
02497       c = (dst[i] <= l);
02498     } else {
02499       dst[i] += rhs[i];
02500       c = (dst[i] < l);
02501     }
02502   }
02503 
02504   return c;
02505 }
02506 
02507 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
02508 integerPart
02509 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
02510                   integerPart c, unsigned int parts)
02511 {
02512   unsigned int i;
02513 
02514   assert(c <= 1);
02515 
02516   for (i = 0; i < parts; i++) {
02517     integerPart l;
02518 
02519     l = dst[i];
02520     if (c) {
02521       dst[i] -= rhs[i] + 1;
02522       c = (dst[i] >= l);
02523     } else {
02524       dst[i] -= rhs[i];
02525       c = (dst[i] > l);
02526     }
02527   }
02528 
02529   return c;
02530 }
02531 
02532 /* Negate a bignum in-place.  */
02533 void
02534 APInt::tcNegate(integerPart *dst, unsigned int parts)
02535 {
02536   tcComplement(dst, parts);
02537   tcIncrement(dst, parts);
02538 }
02539 
02540 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
02541     DST  = SRC * MULTIPLIER + CARRY   if add is false
02542 
02543     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
02544     they must start at the same point, i.e. DST == SRC.
02545 
02546     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
02547     returned.  Otherwise DST is filled with the least significant
02548     DSTPARTS parts of the result, and if all of the omitted higher
02549     parts were zero return zero, otherwise overflow occurred and
02550     return one.  */
02551 int
02552 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
02553                       integerPart multiplier, integerPart carry,
02554                       unsigned int srcParts, unsigned int dstParts,
02555                       bool add)
02556 {
02557   unsigned int i, n;
02558 
02559   /* Otherwise our writes of DST kill our later reads of SRC.  */
02560   assert(dst <= src || dst >= src + srcParts);
02561   assert(dstParts <= srcParts + 1);
02562 
02563   /* N loops; minimum of dstParts and srcParts.  */
02564   n = dstParts < srcParts ? dstParts: srcParts;
02565 
02566   for (i = 0; i < n; i++) {
02567     integerPart low, mid, high, srcPart;
02568 
02569       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
02570 
02571          This cannot overflow, because
02572 
02573          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
02574 
02575          which is less than n^2.  */
02576 
02577     srcPart = src[i];
02578 
02579     if (multiplier == 0 || srcPart == 0)        {
02580       low = carry;
02581       high = 0;
02582     } else {
02583       low = lowHalf(srcPart) * lowHalf(multiplier);
02584       high = highHalf(srcPart) * highHalf(multiplier);
02585 
02586       mid = lowHalf(srcPart) * highHalf(multiplier);
02587       high += highHalf(mid);
02588       mid <<= integerPartWidth / 2;
02589       if (low + mid < low)
02590         high++;
02591       low += mid;
02592 
02593       mid = highHalf(srcPart) * lowHalf(multiplier);
02594       high += highHalf(mid);
02595       mid <<= integerPartWidth / 2;
02596       if (low + mid < low)
02597         high++;
02598       low += mid;
02599 
02600       /* Now add carry.  */
02601       if (low + carry < low)
02602         high++;
02603       low += carry;
02604     }
02605 
02606     if (add) {
02607       /* And now DST[i], and store the new low part there.  */
02608       if (low + dst[i] < low)
02609         high++;
02610       dst[i] += low;
02611     } else
02612       dst[i] = low;
02613 
02614     carry = high;
02615   }
02616 
02617   if (i < dstParts) {
02618     /* Full multiplication, there is no overflow.  */
02619     assert(i + 1 == dstParts);
02620     dst[i] = carry;
02621     return 0;
02622   } else {
02623     /* We overflowed if there is carry.  */
02624     if (carry)
02625       return 1;
02626 
02627     /* We would overflow if any significant unwritten parts would be
02628        non-zero.  This is true if any remaining src parts are non-zero
02629        and the multiplier is non-zero.  */
02630     if (multiplier)
02631       for (; i < srcParts; i++)
02632         if (src[i])
02633           return 1;
02634 
02635     /* We fitted in the narrow destination.  */
02636     return 0;
02637   }
02638 }
02639 
02640 /* DST = LHS * RHS, where DST has the same width as the operands and
02641    is filled with the least significant parts of the result.  Returns
02642    one if overflow occurred, otherwise zero.  DST must be disjoint
02643    from both operands.  */
02644 int
02645 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
02646                   const integerPart *rhs, unsigned int parts)
02647 {
02648   unsigned int i;
02649   int overflow;
02650 
02651   assert(dst != lhs && dst != rhs);
02652 
02653   overflow = 0;
02654   tcSet(dst, 0, parts);
02655 
02656   for (i = 0; i < parts; i++)
02657     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
02658                                parts - i, true);
02659 
02660   return overflow;
02661 }
02662 
02663 /* DST = LHS * RHS, where DST has width the sum of the widths of the
02664    operands.  No overflow occurs.  DST must be disjoint from both
02665    operands.  Returns the number of parts required to hold the
02666    result.  */
02667 unsigned int
02668 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
02669                       const integerPart *rhs, unsigned int lhsParts,
02670                       unsigned int rhsParts)
02671 {
02672   /* Put the narrower number on the LHS for less loops below.  */
02673   if (lhsParts > rhsParts) {
02674     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
02675   } else {
02676     unsigned int n;
02677 
02678     assert(dst != lhs && dst != rhs);
02679 
02680     tcSet(dst, 0, rhsParts);
02681 
02682     for (n = 0; n < lhsParts; n++)
02683       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
02684 
02685     n = lhsParts + rhsParts;
02686 
02687     return n - (dst[n - 1] == 0);
02688   }
02689 }
02690 
02691 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
02692    Otherwise set LHS to LHS / RHS with the fractional part discarded,
02693    set REMAINDER to the remainder, return zero.  i.e.
02694 
02695    OLD_LHS = RHS * LHS + REMAINDER
02696 
02697    SCRATCH is a bignum of the same size as the operands and result for
02698    use by the routine; its contents need not be initialized and are
02699    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
02700 */
02701 int
02702 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
02703                 integerPart *remainder, integerPart *srhs,
02704                 unsigned int parts)
02705 {
02706   unsigned int n, shiftCount;
02707   integerPart mask;
02708 
02709   assert(lhs != remainder && lhs != srhs && remainder != srhs);
02710 
02711   shiftCount = tcMSB(rhs, parts) + 1;
02712   if (shiftCount == 0)
02713     return true;
02714 
02715   shiftCount = parts * integerPartWidth - shiftCount;
02716   n = shiftCount / integerPartWidth;
02717   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
02718 
02719   tcAssign(srhs, rhs, parts);
02720   tcShiftLeft(srhs, parts, shiftCount);
02721   tcAssign(remainder, lhs, parts);
02722   tcSet(lhs, 0, parts);
02723 
02724   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
02725      the total.  */
02726   for (;;) {
02727       int compare;
02728 
02729       compare = tcCompare(remainder, srhs, parts);
02730       if (compare >= 0) {
02731         tcSubtract(remainder, srhs, 0, parts);
02732         lhs[n] |= mask;
02733       }
02734 
02735       if (shiftCount == 0)
02736         break;
02737       shiftCount--;
02738       tcShiftRight(srhs, parts, 1);
02739       if ((mask >>= 1) == 0)
02740         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
02741   }
02742 
02743   return false;
02744 }
02745 
02746 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
02747    There are no restrictions on COUNT.  */
02748 void
02749 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
02750 {
02751   if (count) {
02752     unsigned int jump, shift;
02753 
02754     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02755     jump = count / integerPartWidth;
02756     shift = count % integerPartWidth;
02757 
02758     while (parts > jump) {
02759       integerPart part;
02760 
02761       parts--;
02762 
02763       /* dst[i] comes from the two parts src[i - jump] and, if we have
02764          an intra-part shift, src[i - jump - 1].  */
02765       part = dst[parts - jump];
02766       if (shift) {
02767         part <<= shift;
02768         if (parts >= jump + 1)
02769           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
02770       }
02771 
02772       dst[parts] = part;
02773     }
02774 
02775     while (parts > 0)
02776       dst[--parts] = 0;
02777   }
02778 }
02779 
02780 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
02781    zero.  There are no restrictions on COUNT.  */
02782 void
02783 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
02784 {
02785   if (count) {
02786     unsigned int i, jump, shift;
02787 
02788     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02789     jump = count / integerPartWidth;
02790     shift = count % integerPartWidth;
02791 
02792     /* Perform the shift.  This leaves the most significant COUNT bits
02793        of the result at zero.  */
02794     for (i = 0; i < parts; i++) {
02795       integerPart part;
02796 
02797       if (i + jump >= parts) {
02798         part = 0;
02799       } else {
02800         part = dst[i + jump];
02801         if (shift) {
02802           part >>= shift;
02803           if (i + jump + 1 < parts)
02804             part |= dst[i + jump + 1] << (integerPartWidth - shift);
02805         }
02806       }
02807 
02808       dst[i] = part;
02809     }
02810   }
02811 }
02812 
02813 /* Bitwise and of two bignums.  */
02814 void
02815 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
02816 {
02817   unsigned int i;
02818 
02819   for (i = 0; i < parts; i++)
02820     dst[i] &= rhs[i];
02821 }
02822 
02823 /* Bitwise inclusive or of two bignums.  */
02824 void
02825 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
02826 {
02827   unsigned int i;
02828 
02829   for (i = 0; i < parts; i++)
02830     dst[i] |= rhs[i];
02831 }
02832 
02833 /* Bitwise exclusive or of two bignums.  */
02834 void
02835 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
02836 {
02837   unsigned int i;
02838 
02839   for (i = 0; i < parts; i++)
02840     dst[i] ^= rhs[i];
02841 }
02842 
02843 /* Complement a bignum in-place.  */
02844 void
02845 APInt::tcComplement(integerPart *dst, unsigned int parts)
02846 {
02847   unsigned int i;
02848 
02849   for (i = 0; i < parts; i++)
02850     dst[i] = ~dst[i];
02851 }
02852 
02853 /* Comparison (unsigned) of two bignums.  */
02854 int
02855 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
02856                  unsigned int parts)
02857 {
02858   while (parts) {
02859       parts--;
02860       if (lhs[parts] == rhs[parts])
02861         continue;
02862 
02863       if (lhs[parts] > rhs[parts])
02864         return 1;
02865       else
02866         return -1;
02867     }
02868 
02869   return 0;
02870 }
02871 
02872 /* Increment a bignum in-place, return the carry flag.  */
02873 integerPart
02874 APInt::tcIncrement(integerPart *dst, unsigned int parts)
02875 {
02876   unsigned int i;
02877 
02878   for (i = 0; i < parts; i++)
02879     if (++dst[i] != 0)
02880       break;
02881 
02882   return i == parts;
02883 }
02884 
02885 /* Decrement a bignum in-place, return the borrow flag.  */
02886 integerPart
02887 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
02888   for (unsigned int i = 0; i < parts; i++) {
02889     // If the current word is non-zero, then the decrement has no effect on the
02890     // higher-order words of the integer and no borrow can occur. Exit early.
02891     if (dst[i]--)
02892       return 0;
02893   }
02894   // If every word was zero, then there is a borrow.
02895   return 1;
02896 }
02897 
02898 
02899 /* Set the least significant BITS bits of a bignum, clear the
02900    rest.  */
02901 void
02902 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
02903                                  unsigned int bits)
02904 {
02905   unsigned int i;
02906 
02907   i = 0;
02908   while (bits > integerPartWidth) {
02909     dst[i++] = ~(integerPart) 0;
02910     bits -= integerPartWidth;
02911   }
02912 
02913   if (bits)
02914     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
02915 
02916   while (i < parts)
02917     dst[i++] = 0;
02918 }