LLVM  mainline
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 bool APInt::isSplat(unsigned SplatSizeInBits) const {
00676   assert(getBitWidth() % SplatSizeInBits == 0 &&
00677          "SplatSizeInBits must divide width!");
00678   // We can check that all parts of an integer are equal by making use of a
00679   // little trick: rotate and check if it's still the same value.
00680   return *this == rotl(SplatSizeInBits);
00681 }
00682 
00683 /// HiBits - This function returns the high "numBits" bits of this APInt.
00684 APInt APInt::getHiBits(unsigned numBits) const {
00685   return APIntOps::lshr(*this, BitWidth - numBits);
00686 }
00687 
00688 /// LoBits - This function returns the low "numBits" bits of this APInt.
00689 APInt APInt::getLoBits(unsigned numBits) const {
00690   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
00691                         BitWidth - numBits);
00692 }
00693 
00694 unsigned APInt::countLeadingZerosSlowCase() const {
00695   // Treat the most significand word differently because it might have
00696   // meaningless bits set beyond the precision.
00697   unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
00698   integerPart MSWMask;
00699   if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
00700   else {
00701     MSWMask = ~integerPart(0);
00702     BitsInMSW = APINT_BITS_PER_WORD;
00703   }
00704 
00705   unsigned i = getNumWords();
00706   integerPart MSW = pVal[i-1] & MSWMask;
00707   if (MSW)
00708     return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
00709 
00710   unsigned Count = BitsInMSW;
00711   for (--i; i > 0u; --i) {
00712     if (pVal[i-1] == 0)
00713       Count += APINT_BITS_PER_WORD;
00714     else {
00715       Count += llvm::countLeadingZeros(pVal[i-1]);
00716       break;
00717     }
00718   }
00719   return Count;
00720 }
00721 
00722 unsigned APInt::countLeadingOnes() const {
00723   if (isSingleWord())
00724     return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
00725 
00726   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
00727   unsigned shift;
00728   if (!highWordBits) {
00729     highWordBits = APINT_BITS_PER_WORD;
00730     shift = 0;
00731   } else {
00732     shift = APINT_BITS_PER_WORD - highWordBits;
00733   }
00734   int i = getNumWords() - 1;
00735   unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
00736   if (Count == highWordBits) {
00737     for (i--; i >= 0; --i) {
00738       if (pVal[i] == -1ULL)
00739         Count += APINT_BITS_PER_WORD;
00740       else {
00741         Count += llvm::countLeadingOnes(pVal[i]);
00742         break;
00743       }
00744     }
00745   }
00746   return Count;
00747 }
00748 
00749 unsigned APInt::countTrailingZeros() const {
00750   if (isSingleWord())
00751     return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
00752   unsigned Count = 0;
00753   unsigned i = 0;
00754   for (; i < getNumWords() && pVal[i] == 0; ++i)
00755     Count += APINT_BITS_PER_WORD;
00756   if (i < getNumWords())
00757     Count += llvm::countTrailingZeros(pVal[i]);
00758   return std::min(Count, BitWidth);
00759 }
00760 
00761 unsigned APInt::countTrailingOnesSlowCase() const {
00762   unsigned Count = 0;
00763   unsigned i = 0;
00764   for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
00765     Count += APINT_BITS_PER_WORD;
00766   if (i < getNumWords())
00767     Count += llvm::countTrailingOnes(pVal[i]);
00768   return std::min(Count, BitWidth);
00769 }
00770 
00771 unsigned APInt::countPopulationSlowCase() const {
00772   unsigned Count = 0;
00773   for (unsigned i = 0; i < getNumWords(); ++i)
00774     Count += llvm::countPopulation(pVal[i]);
00775   return Count;
00776 }
00777 
00778 /// Perform a logical right-shift from Src to Dst, which must be equal or
00779 /// non-overlapping, of Words words, by Shift, which must be less than 64.
00780 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
00781                      unsigned Shift) {
00782   uint64_t Carry = 0;
00783   for (int I = Words - 1; I >= 0; --I) {
00784     uint64_t Tmp = Src[I];
00785     Dst[I] = (Tmp >> Shift) | Carry;
00786     Carry = Tmp << (64 - Shift);
00787   }
00788 }
00789 
00790 APInt APInt::byteSwap() const {
00791   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
00792   if (BitWidth == 16)
00793     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
00794   if (BitWidth == 32)
00795     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
00796   if (BitWidth == 48) {
00797     unsigned Tmp1 = unsigned(VAL >> 16);
00798     Tmp1 = ByteSwap_32(Tmp1);
00799     uint16_t Tmp2 = uint16_t(VAL);
00800     Tmp2 = ByteSwap_16(Tmp2);
00801     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
00802   }
00803   if (BitWidth == 64)
00804     return APInt(BitWidth, ByteSwap_64(VAL));
00805 
00806   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
00807   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
00808     Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
00809   if (Result.BitWidth != BitWidth) {
00810     lshrNear(Result.pVal, Result.pVal, getNumWords(),
00811              Result.BitWidth - BitWidth);
00812     Result.BitWidth = BitWidth;
00813   }
00814   return Result;
00815 }
00816 
00817 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
00818                                             const APInt& API2) {
00819   APInt A = API1, B = API2;
00820   while (!!B) {
00821     APInt T = B;
00822     B = APIntOps::urem(A, B);
00823     A = T;
00824   }
00825   return A;
00826 }
00827 
00828 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
00829   union {
00830     double D;
00831     uint64_t I;
00832   } T;
00833   T.D = Double;
00834 
00835   // Get the sign bit from the highest order bit
00836   bool isNeg = T.I >> 63;
00837 
00838   // Get the 11-bit exponent and adjust for the 1023 bit bias
00839   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
00840 
00841   // If the exponent is negative, the value is < 0 so just return 0.
00842   if (exp < 0)
00843     return APInt(width, 0u);
00844 
00845   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
00846   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
00847 
00848   // If the exponent doesn't shift all bits out of the mantissa
00849   if (exp < 52)
00850     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
00851                     APInt(width, mantissa >> (52 - exp));
00852 
00853   // If the client didn't provide enough bits for us to shift the mantissa into
00854   // then the result is undefined, just return 0
00855   if (width <= exp - 52)
00856     return APInt(width, 0);
00857 
00858   // Otherwise, we have to shift the mantissa bits up to the right location
00859   APInt Tmp(width, mantissa);
00860   Tmp = Tmp.shl((unsigned)exp - 52);
00861   return isNeg ? -Tmp : Tmp;
00862 }
00863 
00864 /// RoundToDouble - This function converts this APInt to a double.
00865 /// The layout for double is as following (IEEE Standard 754):
00866 ///  --------------------------------------
00867 /// |  Sign    Exponent    Fraction    Bias |
00868 /// |-------------------------------------- |
00869 /// |  1[63]   11[62-52]   52[51-00]   1023 |
00870 ///  --------------------------------------
00871 double APInt::roundToDouble(bool isSigned) const {
00872 
00873   // Handle the simple case where the value is contained in one uint64_t.
00874   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
00875   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
00876     if (isSigned) {
00877       int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
00878       return double(sext);
00879     } else
00880       return double(getWord(0));
00881   }
00882 
00883   // Determine if the value is negative.
00884   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
00885 
00886   // Construct the absolute value if we're negative.
00887   APInt Tmp(isNeg ? -(*this) : (*this));
00888 
00889   // Figure out how many bits we're using.
00890   unsigned n = Tmp.getActiveBits();
00891 
00892   // The exponent (without bias normalization) is just the number of bits
00893   // we are using. Note that the sign bit is gone since we constructed the
00894   // absolute value.
00895   uint64_t exp = n;
00896 
00897   // Return infinity for exponent overflow
00898   if (exp > 1023) {
00899     if (!isSigned || !isNeg)
00900       return std::numeric_limits<double>::infinity();
00901     else
00902       return -std::numeric_limits<double>::infinity();
00903   }
00904   exp += 1023; // Increment for 1023 bias
00905 
00906   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
00907   // extract the high 52 bits from the correct words in pVal.
00908   uint64_t mantissa;
00909   unsigned hiWord = whichWord(n-1);
00910   if (hiWord == 0) {
00911     mantissa = Tmp.pVal[0];
00912     if (n > 52)
00913       mantissa >>= n - 52; // shift down, we want the top 52 bits.
00914   } else {
00915     assert(hiWord > 0 && "huh?");
00916     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
00917     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
00918     mantissa = hibits | lobits;
00919   }
00920 
00921   // The leading bit of mantissa is implicit, so get rid of it.
00922   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
00923   union {
00924     double D;
00925     uint64_t I;
00926   } T;
00927   T.I = sign | (exp << 52) | mantissa;
00928   return T.D;
00929 }
00930 
00931 // Truncate to new width.
00932 APInt APInt::trunc(unsigned width) const {
00933   assert(width < BitWidth && "Invalid APInt Truncate request");
00934   assert(width && "Can't truncate to 0 bits");
00935 
00936   if (width <= APINT_BITS_PER_WORD)
00937     return APInt(width, getRawData()[0]);
00938 
00939   APInt Result(getMemory(getNumWords(width)), width);
00940 
00941   // Copy full words.
00942   unsigned i;
00943   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
00944     Result.pVal[i] = pVal[i];
00945 
00946   // Truncate and copy any partial word.
00947   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
00948   if (bits != 0)
00949     Result.pVal[i] = pVal[i] << bits >> bits;
00950 
00951   return Result;
00952 }
00953 
00954 // Sign extend to a new width.
00955 APInt APInt::sext(unsigned width) const {
00956   assert(width > BitWidth && "Invalid APInt SignExtend request");
00957 
00958   if (width <= APINT_BITS_PER_WORD) {
00959     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
00960     val = (int64_t)val >> (width - BitWidth);
00961     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
00962   }
00963 
00964   APInt Result(getMemory(getNumWords(width)), width);
00965 
00966   // Copy full words.
00967   unsigned i;
00968   uint64_t word = 0;
00969   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
00970     word = getRawData()[i];
00971     Result.pVal[i] = word;
00972   }
00973 
00974   // Read and sign-extend any partial word.
00975   unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
00976   if (bits != 0)
00977     word = (int64_t)getRawData()[i] << bits >> bits;
00978   else
00979     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
00980 
00981   // Write remaining full words.
00982   for (; i != width / APINT_BITS_PER_WORD; i++) {
00983     Result.pVal[i] = word;
00984     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
00985   }
00986 
00987   // Write any partial word.
00988   bits = (0 - width) % APINT_BITS_PER_WORD;
00989   if (bits != 0)
00990     Result.pVal[i] = word << bits >> bits;
00991 
00992   return Result;
00993 }
00994 
00995 //  Zero extend to a new width.
00996 APInt APInt::zext(unsigned width) const {
00997   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
00998 
00999   if (width <= APINT_BITS_PER_WORD)
01000     return APInt(width, VAL);
01001 
01002   APInt Result(getMemory(getNumWords(width)), width);
01003 
01004   // Copy words.
01005   unsigned i;
01006   for (i = 0; i != getNumWords(); i++)
01007     Result.pVal[i] = getRawData()[i];
01008 
01009   // Zero remaining words.
01010   memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
01011 
01012   return Result;
01013 }
01014 
01015 APInt APInt::zextOrTrunc(unsigned width) const {
01016   if (BitWidth < width)
01017     return zext(width);
01018   if (BitWidth > width)
01019     return trunc(width);
01020   return *this;
01021 }
01022 
01023 APInt APInt::sextOrTrunc(unsigned width) const {
01024   if (BitWidth < width)
01025     return sext(width);
01026   if (BitWidth > width)
01027     return trunc(width);
01028   return *this;
01029 }
01030 
01031 APInt APInt::zextOrSelf(unsigned width) const {
01032   if (BitWidth < width)
01033     return zext(width);
01034   return *this;
01035 }
01036 
01037 APInt APInt::sextOrSelf(unsigned width) const {
01038   if (BitWidth < width)
01039     return sext(width);
01040   return *this;
01041 }
01042 
01043 /// Arithmetic right-shift this APInt by shiftAmt.
01044 /// @brief Arithmetic right-shift function.
01045 APInt APInt::ashr(const APInt &shiftAmt) const {
01046   return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
01047 }
01048 
01049 /// Arithmetic right-shift this APInt by shiftAmt.
01050 /// @brief Arithmetic right-shift function.
01051 APInt APInt::ashr(unsigned shiftAmt) const {
01052   assert(shiftAmt <= BitWidth && "Invalid shift amount");
01053   // Handle a degenerate case
01054   if (shiftAmt == 0)
01055     return *this;
01056 
01057   // Handle single word shifts with built-in ashr
01058   if (isSingleWord()) {
01059     if (shiftAmt == BitWidth)
01060       return APInt(BitWidth, 0); // undefined
01061     else {
01062       unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
01063       return APInt(BitWidth,
01064         (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
01065     }
01066   }
01067 
01068   // If all the bits were shifted out, the result is, technically, undefined.
01069   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
01070   // issues in the algorithm below.
01071   if (shiftAmt == BitWidth) {
01072     if (isNegative())
01073       return APInt(BitWidth, -1ULL, true);
01074     else
01075       return APInt(BitWidth, 0);
01076   }
01077 
01078   // Create some space for the result.
01079   uint64_t * val = new uint64_t[getNumWords()];
01080 
01081   // Compute some values needed by the following shift algorithms
01082   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
01083   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
01084   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
01085   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
01086   if (bitsInWord == 0)
01087     bitsInWord = APINT_BITS_PER_WORD;
01088 
01089   // If we are shifting whole words, just move whole words
01090   if (wordShift == 0) {
01091     // Move the words containing significant bits
01092     for (unsigned i = 0; i <= breakWord; ++i)
01093       val[i] = pVal[i+offset]; // move whole word
01094 
01095     // Adjust the top significant word for sign bit fill, if negative
01096     if (isNegative())
01097       if (bitsInWord < APINT_BITS_PER_WORD)
01098         val[breakWord] |= ~0ULL << bitsInWord; // set high bits
01099   } else {
01100     // Shift the low order words
01101     for (unsigned i = 0; i < breakWord; ++i) {
01102       // This combines the shifted corresponding word with the low bits from
01103       // the next word (shifted into this word's high bits).
01104       val[i] = (pVal[i+offset] >> wordShift) |
01105                (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
01106     }
01107 
01108     // Shift the break word. In this case there are no bits from the next word
01109     // to include in this word.
01110     val[breakWord] = pVal[breakWord+offset] >> wordShift;
01111 
01112     // Deal with sign extension in the break word, and possibly the word before
01113     // it.
01114     if (isNegative()) {
01115       if (wordShift > bitsInWord) {
01116         if (breakWord > 0)
01117           val[breakWord-1] |=
01118             ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
01119         val[breakWord] |= ~0ULL;
01120       } else
01121         val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
01122     }
01123   }
01124 
01125   // Remaining words are 0 or -1, just assign them.
01126   uint64_t fillValue = (isNegative() ? -1ULL : 0);
01127   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
01128     val[i] = fillValue;
01129   APInt Result(val, BitWidth);
01130   Result.clearUnusedBits();
01131   return Result;
01132 }
01133 
01134 /// Logical right-shift this APInt by shiftAmt.
01135 /// @brief Logical right-shift function.
01136 APInt APInt::lshr(const APInt &shiftAmt) const {
01137   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
01138 }
01139 
01140 /// Logical right-shift this APInt by shiftAmt.
01141 /// @brief Logical right-shift function.
01142 APInt APInt::lshr(unsigned shiftAmt) const {
01143   if (isSingleWord()) {
01144     if (shiftAmt >= BitWidth)
01145       return APInt(BitWidth, 0);
01146     else
01147       return APInt(BitWidth, this->VAL >> shiftAmt);
01148   }
01149 
01150   // If all the bits were shifted out, the result is 0. This avoids issues
01151   // with shifting by the size of the integer type, which produces undefined
01152   // results. We define these "undefined results" to always be 0.
01153   if (shiftAmt >= BitWidth)
01154     return APInt(BitWidth, 0);
01155 
01156   // If none of the bits are shifted out, the result is *this. This avoids
01157   // issues with shifting by the size of the integer type, which produces
01158   // undefined results in the code below. This is also an optimization.
01159   if (shiftAmt == 0)
01160     return *this;
01161 
01162   // Create some space for the result.
01163   uint64_t * val = new uint64_t[getNumWords()];
01164 
01165   // If we are shifting less than a word, compute the shift with a simple carry
01166   if (shiftAmt < APINT_BITS_PER_WORD) {
01167     lshrNear(val, pVal, getNumWords(), shiftAmt);
01168     APInt Result(val, BitWidth);
01169     Result.clearUnusedBits();
01170     return Result;
01171   }
01172 
01173   // Compute some values needed by the remaining shift algorithms
01174   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
01175   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
01176 
01177   // If we are shifting whole words, just move whole words
01178   if (wordShift == 0) {
01179     for (unsigned i = 0; i < getNumWords() - offset; ++i)
01180       val[i] = pVal[i+offset];
01181     for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
01182       val[i] = 0;
01183     APInt Result(val, BitWidth);
01184     Result.clearUnusedBits();
01185     return Result;
01186   }
01187 
01188   // Shift the low order words
01189   unsigned breakWord = getNumWords() - offset -1;
01190   for (unsigned i = 0; i < breakWord; ++i)
01191     val[i] = (pVal[i+offset] >> wordShift) |
01192              (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
01193   // Shift the break word.
01194   val[breakWord] = pVal[breakWord+offset] >> wordShift;
01195 
01196   // Remaining words are 0
01197   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
01198     val[i] = 0;
01199   APInt Result(val, BitWidth);
01200   Result.clearUnusedBits();
01201   return Result;
01202 }
01203 
01204 /// Left-shift this APInt by shiftAmt.
01205 /// @brief Left-shift function.
01206 APInt APInt::shl(const APInt &shiftAmt) const {
01207   // It's undefined behavior in C to shift by BitWidth or greater.
01208   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
01209 }
01210 
01211 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
01212   // If all the bits were shifted out, the result is 0. This avoids issues
01213   // with shifting by the size of the integer type, which produces undefined
01214   // results. We define these "undefined results" to always be 0.
01215   if (shiftAmt == BitWidth)
01216     return APInt(BitWidth, 0);
01217 
01218   // If none of the bits are shifted out, the result is *this. This avoids a
01219   // lshr by the words size in the loop below which can produce incorrect
01220   // results. It also avoids the expensive computation below for a common case.
01221   if (shiftAmt == 0)
01222     return *this;
01223 
01224   // Create some space for the result.
01225   uint64_t * val = new uint64_t[getNumWords()];
01226 
01227   // If we are shifting less than a word, do it the easy way
01228   if (shiftAmt < APINT_BITS_PER_WORD) {
01229     uint64_t carry = 0;
01230     for (unsigned i = 0; i < getNumWords(); i++) {
01231       val[i] = pVal[i] << shiftAmt | carry;
01232       carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
01233     }
01234     APInt Result(val, BitWidth);
01235     Result.clearUnusedBits();
01236     return Result;
01237   }
01238 
01239   // Compute some values needed by the remaining shift algorithms
01240   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
01241   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
01242 
01243   // If we are shifting whole words, just move whole words
01244   if (wordShift == 0) {
01245     for (unsigned i = 0; i < offset; i++)
01246       val[i] = 0;
01247     for (unsigned i = offset; i < getNumWords(); i++)
01248       val[i] = pVal[i-offset];
01249     APInt Result(val, BitWidth);
01250     Result.clearUnusedBits();
01251     return Result;
01252   }
01253 
01254   // Copy whole words from this to Result.
01255   unsigned i = getNumWords() - 1;
01256   for (; i > offset; --i)
01257     val[i] = pVal[i-offset] << wordShift |
01258              pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
01259   val[offset] = pVal[0] << wordShift;
01260   for (i = 0; i < offset; ++i)
01261     val[i] = 0;
01262   APInt Result(val, BitWidth);
01263   Result.clearUnusedBits();
01264   return Result;
01265 }
01266 
01267 APInt APInt::rotl(const APInt &rotateAmt) const {
01268   return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
01269 }
01270 
01271 APInt APInt::rotl(unsigned rotateAmt) const {
01272   rotateAmt %= BitWidth;
01273   if (rotateAmt == 0)
01274     return *this;
01275   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
01276 }
01277 
01278 APInt APInt::rotr(const APInt &rotateAmt) const {
01279   return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
01280 }
01281 
01282 APInt APInt::rotr(unsigned rotateAmt) const {
01283   rotateAmt %= BitWidth;
01284   if (rotateAmt == 0)
01285     return *this;
01286   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
01287 }
01288 
01289 // Square Root - this method computes and returns the square root of "this".
01290 // Three mechanisms are used for computation. For small values (<= 5 bits),
01291 // a table lookup is done. This gets some performance for common cases. For
01292 // values using less than 52 bits, the value is converted to double and then
01293 // the libc sqrt function is called. The result is rounded and then converted
01294 // back to a uint64_t which is then used to construct the result. Finally,
01295 // the Babylonian method for computing square roots is used.
01296 APInt APInt::sqrt() const {
01297 
01298   // Determine the magnitude of the value.
01299   unsigned magnitude = getActiveBits();
01300 
01301   // Use a fast table for some small values. This also gets rid of some
01302   // rounding errors in libc sqrt for small values.
01303   if (magnitude <= 5) {
01304     static const uint8_t results[32] = {
01305       /*     0 */ 0,
01306       /*  1- 2 */ 1, 1,
01307       /*  3- 6 */ 2, 2, 2, 2,
01308       /*  7-12 */ 3, 3, 3, 3, 3, 3,
01309       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
01310       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
01311       /*    31 */ 6
01312     };
01313     return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
01314   }
01315 
01316   // If the magnitude of the value fits in less than 52 bits (the precision of
01317   // an IEEE double precision floating point value), then we can use the
01318   // libc sqrt function which will probably use a hardware sqrt computation.
01319   // This should be faster than the algorithm below.
01320   if (magnitude < 52) {
01321     return APInt(BitWidth,
01322                  uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
01323   }
01324 
01325   // Okay, all the short cuts are exhausted. We must compute it. The following
01326   // is a classical Babylonian method for computing the square root. This code
01327   // was adapted to APInt from a wikipedia article on such computations.
01328   // See http://www.wikipedia.org/ and go to the page named
01329   // Calculate_an_integer_square_root.
01330   unsigned nbits = BitWidth, i = 4;
01331   APInt testy(BitWidth, 16);
01332   APInt x_old(BitWidth, 1);
01333   APInt x_new(BitWidth, 0);
01334   APInt two(BitWidth, 2);
01335 
01336   // Select a good starting value using binary logarithms.
01337   for (;; i += 2, testy = testy.shl(2))
01338     if (i >= nbits || this->ule(testy)) {
01339       x_old = x_old.shl(i / 2);
01340       break;
01341     }
01342 
01343   // Use the Babylonian method to arrive at the integer square root:
01344   for (;;) {
01345     x_new = (this->udiv(x_old) + x_old).udiv(two);
01346     if (x_old.ule(x_new))
01347       break;
01348     x_old = x_new;
01349   }
01350 
01351   // Make sure we return the closest approximation
01352   // NOTE: The rounding calculation below is correct. It will produce an
01353   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
01354   // determined to be a rounding issue with pari/gp as it begins to use a
01355   // floating point representation after 192 bits. There are no discrepancies
01356   // between this algorithm and pari/gp for bit widths < 192 bits.
01357   APInt square(x_old * x_old);
01358   APInt nextSquare((x_old + 1) * (x_old +1));
01359   if (this->ult(square))
01360     return x_old;
01361   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
01362   APInt midpoint((nextSquare - square).udiv(two));
01363   APInt offset(*this - square);
01364   if (offset.ult(midpoint))
01365     return x_old;
01366   return x_old + 1;
01367 }
01368 
01369 /// Computes the multiplicative inverse of this APInt for a given modulo. The
01370 /// iterative extended Euclidean algorithm is used to solve for this value,
01371 /// however we simplify it to speed up calculating only the inverse, and take
01372 /// advantage of div+rem calculations. We also use some tricks to avoid copying
01373 /// (potentially large) APInts around.
01374 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
01375   assert(ult(modulo) && "This APInt must be smaller than the modulo");
01376 
01377   // Using the properties listed at the following web page (accessed 06/21/08):
01378   //   http://www.numbertheory.org/php/euclid.html
01379   // (especially the properties numbered 3, 4 and 9) it can be proved that
01380   // BitWidth bits suffice for all the computations in the algorithm implemented
01381   // below. More precisely, this number of bits suffice if the multiplicative
01382   // inverse exists, but may not suffice for the general extended Euclidean
01383   // algorithm.
01384 
01385   APInt r[2] = { modulo, *this };
01386   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
01387   APInt q(BitWidth, 0);
01388 
01389   unsigned i;
01390   for (i = 0; r[i^1] != 0; i ^= 1) {
01391     // An overview of the math without the confusing bit-flipping:
01392     // q = r[i-2] / r[i-1]
01393     // r[i] = r[i-2] % r[i-1]
01394     // t[i] = t[i-2] - t[i-1] * q
01395     udivrem(r[i], r[i^1], q, r[i]);
01396     t[i] -= t[i^1] * q;
01397   }
01398 
01399   // If this APInt and the modulo are not coprime, there is no multiplicative
01400   // inverse, so return 0. We check this by looking at the next-to-last
01401   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
01402   // algorithm.
01403   if (r[i] != 1)
01404     return APInt(BitWidth, 0);
01405 
01406   // The next-to-last t is the multiplicative inverse.  However, we are
01407   // interested in a positive inverse. Calcuate a positive one from a negative
01408   // one if necessary. A simple addition of the modulo suffices because
01409   // abs(t[i]) is known to be less than *this/2 (see the link above).
01410   return t[i].isNegative() ? t[i] + modulo : t[i];
01411 }
01412 
01413 /// Calculate the magic numbers required to implement a signed integer division
01414 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
01415 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
01416 /// Warren, Jr., chapter 10.
01417 APInt::ms APInt::magic() const {
01418   const APInt& d = *this;
01419   unsigned p;
01420   APInt ad, anc, delta, q1, r1, q2, r2, t;
01421   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
01422   struct ms mag;
01423 
01424   ad = d.abs();
01425   t = signedMin + (d.lshr(d.getBitWidth() - 1));
01426   anc = t - 1 - t.urem(ad);   // absolute value of nc
01427   p = d.getBitWidth() - 1;    // initialize p
01428   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
01429   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
01430   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
01431   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
01432   do {
01433     p = p + 1;
01434     q1 = q1<<1;          // update q1 = 2p/abs(nc)
01435     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
01436     if (r1.uge(anc)) {  // must be unsigned comparison
01437       q1 = q1 + 1;
01438       r1 = r1 - anc;
01439     }
01440     q2 = q2<<1;          // update q2 = 2p/abs(d)
01441     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
01442     if (r2.uge(ad)) {   // must be unsigned comparison
01443       q2 = q2 + 1;
01444       r2 = r2 - ad;
01445     }
01446     delta = ad - r2;
01447   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
01448 
01449   mag.m = q2 + 1;
01450   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
01451   mag.s = p - d.getBitWidth();          // resulting shift
01452   return mag;
01453 }
01454 
01455 /// Calculate the magic numbers required to implement an unsigned integer
01456 /// division by a constant as a sequence of multiplies, adds and shifts.
01457 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
01458 /// S. Warren, Jr., chapter 10.
01459 /// LeadingZeros can be used to simplify the calculation if the upper bits
01460 /// of the divided value are known zero.
01461 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
01462   const APInt& d = *this;
01463   unsigned p;
01464   APInt nc, delta, q1, r1, q2, r2;
01465   struct mu magu;
01466   magu.a = 0;               // initialize "add" indicator
01467   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
01468   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
01469   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
01470 
01471   nc = allOnes - (allOnes - d).urem(d);
01472   p = d.getBitWidth() - 1;  // initialize p
01473   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
01474   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
01475   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
01476   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
01477   do {
01478     p = p + 1;
01479     if (r1.uge(nc - r1)) {
01480       q1 = q1 + q1 + 1;  // update q1
01481       r1 = r1 + r1 - nc; // update r1
01482     }
01483     else {
01484       q1 = q1+q1; // update q1
01485       r1 = r1+r1; // update r1
01486     }
01487     if ((r2 + 1).uge(d - r2)) {
01488       if (q2.uge(signedMax)) magu.a = 1;
01489       q2 = q2+q2 + 1;     // update q2
01490       r2 = r2+r2 + 1 - d; // update r2
01491     }
01492     else {
01493       if (q2.uge(signedMin)) magu.a = 1;
01494       q2 = q2+q2;     // update q2
01495       r2 = r2+r2 + 1; // update r2
01496     }
01497     delta = d - 1 - r2;
01498   } while (p < d.getBitWidth()*2 &&
01499            (q1.ult(delta) || (q1 == delta && r1 == 0)));
01500   magu.m = q2 + 1; // resulting magic number
01501   magu.s = p - d.getBitWidth();  // resulting shift
01502   return magu;
01503 }
01504 
01505 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
01506 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
01507 /// variables here have the same names as in the algorithm. Comments explain
01508 /// the algorithm and any deviation from it.
01509 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
01510                      unsigned m, unsigned n) {
01511   assert(u && "Must provide dividend");
01512   assert(v && "Must provide divisor");
01513   assert(q && "Must provide quotient");
01514   assert(u != v && u != q && v != q && "Must use different memory");
01515   assert(n>1 && "n must be > 1");
01516 
01517   // b denotes the base of the number system. In our case b is 2^32.
01518   LLVM_CONSTEXPR uint64_t b = uint64_t(1) << 32;
01519 
01520   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
01521   DEBUG(dbgs() << "KnuthDiv: original:");
01522   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01523   DEBUG(dbgs() << " by");
01524   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
01525   DEBUG(dbgs() << '\n');
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 
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 
01557   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
01558   int j = m;
01559   do {
01560     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
01561     // D3. [Calculate q'.].
01562     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
01563     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
01564     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
01565     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
01566     // on v[n-2] determines at high speed most of the cases in which the trial
01567     // value qp is one too large, and it eliminates all cases where qp is two
01568     // too large.
01569     uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
01570     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
01571     uint64_t qp = dividend / v[n-1];
01572     uint64_t rp = dividend % v[n-1];
01573     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
01574       qp--;
01575       rp += v[n-1];
01576       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
01577         qp--;
01578     }
01579     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
01580 
01581     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
01582     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
01583     // consists of a simple multiplication by a one-place number, combined with
01584     // a subtraction.
01585     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
01586     // this step is actually negative, (u[j+n]...u[j]) should be left as the
01587     // true value plus b**(n+1), namely as the b's complement of
01588     // the true value, and a "borrow" to the left should be remembered.
01589     bool isNeg = false;
01590     for (unsigned i = 0; i < n; ++i) {
01591       uint64_t u_tmp = (uint64_t(u[j+i+1]) << 32) | uint64_t(u[j+i]);
01592       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
01593       bool borrow = subtrahend > u_tmp;
01594       DEBUG(dbgs() << "KnuthDiv: u_tmp = " << u_tmp
01595                    << ", subtrahend = " << subtrahend
01596                    << ", borrow = " << borrow << '\n');
01597 
01598       uint64_t result = u_tmp - subtrahend;
01599       unsigned k = j + i;
01600       u[k++] = (unsigned)result;         // subtraction low word
01601       u[k++] = (unsigned)(result >> 32); // subtraction high word
01602       while (borrow && k <= m+n) {       // deal with borrow to the left
01603         borrow = u[k] == 0;
01604         u[k]--;
01605         k++;
01606       }
01607       isNeg |= borrow;
01608       DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i] 
01609                    << ", u[j+i+1] = " << u[j+i+1] << '\n');
01610     }
01611     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
01612     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01613     DEBUG(dbgs() << '\n');
01614 
01615     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
01616     // negative, go to step D6; otherwise go on to step D7.
01617     q[j] = (unsigned)qp;
01618     if (isNeg) {
01619       // D6. [Add back]. The probability that this step is necessary is very
01620       // small, on the order of only 2/b. Make sure that test data accounts for
01621       // this possibility. Decrease q[j] by 1
01622       q[j]--;
01623       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
01624       // A carry will occur to the left of u[j+n], and it should be ignored
01625       // since it cancels with the borrow that occurred in D4.
01626       bool carry = false;
01627       for (unsigned i = 0; i < n; i++) {
01628         unsigned limit = std::min(u[j+i],v[i]);
01629         u[j+i] += v[i] + carry;
01630         carry = u[j+i] < limit || (carry && u[j+i] == limit);
01631       }
01632       u[j+n] += carry;
01633     }
01634     DEBUG(dbgs() << "KnuthDiv: after correction:");
01635     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01636     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
01637 
01638   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
01639   } while (--j >= 0);
01640 
01641   DEBUG(dbgs() << "KnuthDiv: quotient:");
01642   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
01643   DEBUG(dbgs() << '\n');
01644 
01645   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
01646   // remainder may be obtained by dividing u[...] by d. If r is non-null we
01647   // compute the remainder (urem uses this).
01648   if (r) {
01649     // The value d is expressed by the "shift" value above since we avoided
01650     // multiplication by d by using a shift left. So, all we have to do is
01651     // shift right here. In order to mak
01652     if (shift) {
01653       unsigned carry = 0;
01654       DEBUG(dbgs() << "KnuthDiv: remainder:");
01655       for (int i = n-1; i >= 0; i--) {
01656         r[i] = (u[i] >> shift) | carry;
01657         carry = u[i] << (32 - shift);
01658         DEBUG(dbgs() << " " << r[i]);
01659       }
01660     } else {
01661       for (int i = n-1; i >= 0; i--) {
01662         r[i] = u[i];
01663         DEBUG(dbgs() << " " << r[i]);
01664       }
01665     }
01666     DEBUG(dbgs() << '\n');
01667   }
01668   DEBUG(dbgs() << '\n');
01669 }
01670 
01671 void APInt::divide(const APInt LHS, unsigned lhsWords,
01672                    const APInt &RHS, unsigned rhsWords,
01673                    APInt *Quotient, APInt *Remainder)
01674 {
01675   assert(lhsWords >= rhsWords && "Fractional result");
01676 
01677   // First, compose the values into an array of 32-bit words instead of
01678   // 64-bit words. This is a necessity of both the "short division" algorithm
01679   // and the Knuth "classical algorithm" which requires there to be native
01680   // operations for +, -, and * on an m bit value with an m*2 bit result. We
01681   // can't use 64-bit operands here because we don't have native results of
01682   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
01683   // work on large-endian machines.
01684   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
01685   unsigned n = rhsWords * 2;
01686   unsigned m = (lhsWords * 2) - n;
01687 
01688   // Allocate space for the temporary values we need either on the stack, if
01689   // it will fit, or on the heap if it won't.
01690   unsigned SPACE[128];
01691   unsigned *U = nullptr;
01692   unsigned *V = nullptr;
01693   unsigned *Q = nullptr;
01694   unsigned *R = nullptr;
01695   if ((Remainder?4:3)*n+2*m+1 <= 128) {
01696     U = &SPACE[0];
01697     V = &SPACE[m+n+1];
01698     Q = &SPACE[(m+n+1) + n];
01699     if (Remainder)
01700       R = &SPACE[(m+n+1) + n + (m+n)];
01701   } else {
01702     U = new unsigned[m + n + 1];
01703     V = new unsigned[n];
01704     Q = new unsigned[m+n];
01705     if (Remainder)
01706       R = new unsigned[n];
01707   }
01708 
01709   // Initialize the dividend
01710   memset(U, 0, (m+n+1)*sizeof(unsigned));
01711   for (unsigned i = 0; i < lhsWords; ++i) {
01712     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
01713     U[i * 2] = (unsigned)(tmp & mask);
01714     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01715   }
01716   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
01717 
01718   // Initialize the divisor
01719   memset(V, 0, (n)*sizeof(unsigned));
01720   for (unsigned i = 0; i < rhsWords; ++i) {
01721     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
01722     V[i * 2] = (unsigned)(tmp & mask);
01723     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01724   }
01725 
01726   // initialize the quotient and remainder
01727   memset(Q, 0, (m+n) * sizeof(unsigned));
01728   if (Remainder)
01729     memset(R, 0, n * sizeof(unsigned));
01730 
01731   // Now, adjust m and n for the Knuth division. n is the number of words in
01732   // the divisor. m is the number of words by which the dividend exceeds the
01733   // divisor (i.e. m+n is the length of the dividend). These sizes must not
01734   // contain any zero words or the Knuth algorithm fails.
01735   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
01736     n--;
01737     m++;
01738   }
01739   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
01740     m--;
01741 
01742   // If we're left with only a single word for the divisor, Knuth doesn't work
01743   // so we implement the short division algorithm here. This is much simpler
01744   // and faster because we are certain that we can divide a 64-bit quantity
01745   // by a 32-bit quantity at hardware speed and short division is simply a
01746   // series of such operations. This is just like doing short division but we
01747   // are using base 2^32 instead of base 10.
01748   assert(n != 0 && "Divide by zero?");
01749   if (n == 1) {
01750     unsigned divisor = V[0];
01751     unsigned remainder = 0;
01752     for (int i = m+n-1; i >= 0; i--) {
01753       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
01754       if (partial_dividend == 0) {
01755         Q[i] = 0;
01756         remainder = 0;
01757       } else if (partial_dividend < divisor) {
01758         Q[i] = 0;
01759         remainder = (unsigned)partial_dividend;
01760       } else if (partial_dividend == divisor) {
01761         Q[i] = 1;
01762         remainder = 0;
01763       } else {
01764         Q[i] = (unsigned)(partial_dividend / divisor);
01765         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
01766       }
01767     }
01768     if (R)
01769       R[0] = remainder;
01770   } else {
01771     // Now we're ready to invoke the Knuth classical divide algorithm. In this
01772     // case n > 1.
01773     KnuthDiv(U, V, Q, R, m, n);
01774   }
01775 
01776   // If the caller wants the quotient
01777   if (Quotient) {
01778     // Set up the Quotient value's memory.
01779     if (Quotient->BitWidth != LHS.BitWidth) {
01780       if (Quotient->isSingleWord())
01781         Quotient->VAL = 0;
01782       else
01783         delete [] Quotient->pVal;
01784       Quotient->BitWidth = LHS.BitWidth;
01785       if (!Quotient->isSingleWord())
01786         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
01787     } else
01788       Quotient->clearAllBits();
01789 
01790     // The quotient is in Q. Reconstitute the quotient into Quotient's low
01791     // order words.
01792     // This case is currently dead as all users of divide() handle trivial cases
01793     // earlier.
01794     if (lhsWords == 1) {
01795       uint64_t tmp =
01796         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
01797       if (Quotient->isSingleWord())
01798         Quotient->VAL = tmp;
01799       else
01800         Quotient->pVal[0] = tmp;
01801     } else {
01802       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
01803       for (unsigned i = 0; i < lhsWords; ++i)
01804         Quotient->pVal[i] =
01805           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01806     }
01807   }
01808 
01809   // If the caller wants the remainder
01810   if (Remainder) {
01811     // Set up the Remainder value's memory.
01812     if (Remainder->BitWidth != RHS.BitWidth) {
01813       if (Remainder->isSingleWord())
01814         Remainder->VAL = 0;
01815       else
01816         delete [] Remainder->pVal;
01817       Remainder->BitWidth = RHS.BitWidth;
01818       if (!Remainder->isSingleWord())
01819         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
01820     } else
01821       Remainder->clearAllBits();
01822 
01823     // The remainder is in R. Reconstitute the remainder into Remainder's low
01824     // order words.
01825     if (rhsWords == 1) {
01826       uint64_t tmp =
01827         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
01828       if (Remainder->isSingleWord())
01829         Remainder->VAL = tmp;
01830       else
01831         Remainder->pVal[0] = tmp;
01832     } else {
01833       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
01834       for (unsigned i = 0; i < rhsWords; ++i)
01835         Remainder->pVal[i] =
01836           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01837     }
01838   }
01839 
01840   // Clean up the memory we allocated.
01841   if (U != &SPACE[0]) {
01842     delete [] U;
01843     delete [] V;
01844     delete [] Q;
01845     delete [] R;
01846   }
01847 }
01848 
01849 APInt APInt::udiv(const APInt& RHS) const {
01850   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01851 
01852   // First, deal with the easy case
01853   if (isSingleWord()) {
01854     assert(RHS.VAL != 0 && "Divide by zero?");
01855     return APInt(BitWidth, VAL / RHS.VAL);
01856   }
01857 
01858   // Get some facts about the LHS and RHS number of bits and words
01859   unsigned rhsBits = RHS.getActiveBits();
01860   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01861   assert(rhsWords && "Divided by zero???");
01862   unsigned lhsBits = this->getActiveBits();
01863   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01864 
01865   // Deal with some degenerate cases
01866   if (!lhsWords)
01867     // 0 / X ===> 0
01868     return APInt(BitWidth, 0);
01869   else if (lhsWords < rhsWords || this->ult(RHS)) {
01870     // X / Y ===> 0, iff X < Y
01871     return APInt(BitWidth, 0);
01872   } else if (*this == RHS) {
01873     // X / X ===> 1
01874     return APInt(BitWidth, 1);
01875   } else if (lhsWords == 1 && rhsWords == 1) {
01876     // All high words are zero, just use native divide
01877     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
01878   }
01879 
01880   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01881   APInt Quotient(1,0); // to hold result.
01882   divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
01883   return Quotient;
01884 }
01885 
01886 APInt APInt::sdiv(const APInt &RHS) const {
01887   if (isNegative()) {
01888     if (RHS.isNegative())
01889       return (-(*this)).udiv(-RHS);
01890     return -((-(*this)).udiv(RHS));
01891   }
01892   if (RHS.isNegative())
01893     return -(this->udiv(-RHS));
01894   return this->udiv(RHS);
01895 }
01896 
01897 APInt APInt::urem(const APInt& RHS) const {
01898   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01899   if (isSingleWord()) {
01900     assert(RHS.VAL != 0 && "Remainder by zero?");
01901     return APInt(BitWidth, VAL % RHS.VAL);
01902   }
01903 
01904   // Get some facts about the LHS
01905   unsigned lhsBits = getActiveBits();
01906   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
01907 
01908   // Get some facts about the RHS
01909   unsigned rhsBits = RHS.getActiveBits();
01910   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01911   assert(rhsWords && "Performing remainder operation by zero ???");
01912 
01913   // Check the degenerate cases
01914   if (lhsWords == 0) {
01915     // 0 % Y ===> 0
01916     return APInt(BitWidth, 0);
01917   } else if (lhsWords < rhsWords || this->ult(RHS)) {
01918     // X % Y ===> X, iff X < Y
01919     return *this;
01920   } else if (*this == RHS) {
01921     // X % X == 0;
01922     return APInt(BitWidth, 0);
01923   } else if (lhsWords == 1) {
01924     // All high words are zero, just use native remainder
01925     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
01926   }
01927 
01928   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01929   APInt Remainder(1,0);
01930   divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
01931   return Remainder;
01932 }
01933 
01934 APInt APInt::srem(const APInt &RHS) const {
01935   if (isNegative()) {
01936     if (RHS.isNegative())
01937       return -((-(*this)).urem(-RHS));
01938     return -((-(*this)).urem(RHS));
01939   }
01940   if (RHS.isNegative())
01941     return this->urem(-RHS);
01942   return this->urem(RHS);
01943 }
01944 
01945 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
01946                     APInt &Quotient, APInt &Remainder) {
01947   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
01948 
01949   // First, deal with the easy case
01950   if (LHS.isSingleWord()) {
01951     assert(RHS.VAL != 0 && "Divide by zero?");
01952     uint64_t QuotVal = LHS.VAL / RHS.VAL;
01953     uint64_t RemVal = LHS.VAL % RHS.VAL;
01954     Quotient = APInt(LHS.BitWidth, QuotVal);
01955     Remainder = APInt(LHS.BitWidth, RemVal);
01956     return;
01957   }
01958 
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 << "u " << S << "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;
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 }