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 /// 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 /// 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 /// 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 /// 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 /// 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 /// 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 /// 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     int64_t borrow = 0;
01590     for (unsigned i = 0; i < n; ++i) {
01591       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
01592       int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
01593       u[j+i] = (unsigned)subres;
01594       borrow = (p >> 32) - (subres >> 32);
01595       DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
01596                    << ", borrow = " << borrow << '\n');
01597     }
01598     bool isNeg = u[j+n] < borrow;
01599     u[j+n] -= (unsigned)borrow;
01600 
01601     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
01602     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01603     DEBUG(dbgs() << '\n');
01604 
01605     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
01606     // negative, go to step D6; otherwise go on to step D7.
01607     q[j] = (unsigned)qp;
01608     if (isNeg) {
01609       // D6. [Add back]. The probability that this step is necessary is very
01610       // small, on the order of only 2/b. Make sure that test data accounts for
01611       // this possibility. Decrease q[j] by 1
01612       q[j]--;
01613       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
01614       // A carry will occur to the left of u[j+n], and it should be ignored
01615       // since it cancels with the borrow that occurred in D4.
01616       bool carry = false;
01617       for (unsigned i = 0; i < n; i++) {
01618         unsigned limit = std::min(u[j+i],v[i]);
01619         u[j+i] += v[i] + carry;
01620         carry = u[j+i] < limit || (carry && u[j+i] == limit);
01621       }
01622       u[j+n] += carry;
01623     }
01624     DEBUG(dbgs() << "KnuthDiv: after correction:");
01625     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
01626     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
01627 
01628   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
01629   } while (--j >= 0);
01630 
01631   DEBUG(dbgs() << "KnuthDiv: quotient:");
01632   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
01633   DEBUG(dbgs() << '\n');
01634 
01635   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
01636   // remainder may be obtained by dividing u[...] by d. If r is non-null we
01637   // compute the remainder (urem uses this).
01638   if (r) {
01639     // The value d is expressed by the "shift" value above since we avoided
01640     // multiplication by d by using a shift left. So, all we have to do is
01641     // shift right here. In order to mak
01642     if (shift) {
01643       unsigned carry = 0;
01644       DEBUG(dbgs() << "KnuthDiv: remainder:");
01645       for (int i = n-1; i >= 0; i--) {
01646         r[i] = (u[i] >> shift) | carry;
01647         carry = u[i] << (32 - shift);
01648         DEBUG(dbgs() << " " << r[i]);
01649       }
01650     } else {
01651       for (int i = n-1; i >= 0; i--) {
01652         r[i] = u[i];
01653         DEBUG(dbgs() << " " << r[i]);
01654       }
01655     }
01656     DEBUG(dbgs() << '\n');
01657   }
01658   DEBUG(dbgs() << '\n');
01659 }
01660 
01661 void APInt::divide(const APInt LHS, unsigned lhsWords,
01662                    const APInt &RHS, unsigned rhsWords,
01663                    APInt *Quotient, APInt *Remainder)
01664 {
01665   assert(lhsWords >= rhsWords && "Fractional result");
01666 
01667   // First, compose the values into an array of 32-bit words instead of
01668   // 64-bit words. This is a necessity of both the "short division" algorithm
01669   // and the Knuth "classical algorithm" which requires there to be native
01670   // operations for +, -, and * on an m bit value with an m*2 bit result. We
01671   // can't use 64-bit operands here because we don't have native results of
01672   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
01673   // work on large-endian machines.
01674   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
01675   unsigned n = rhsWords * 2;
01676   unsigned m = (lhsWords * 2) - n;
01677 
01678   // Allocate space for the temporary values we need either on the stack, if
01679   // it will fit, or on the heap if it won't.
01680   unsigned SPACE[128];
01681   unsigned *U = nullptr;
01682   unsigned *V = nullptr;
01683   unsigned *Q = nullptr;
01684   unsigned *R = nullptr;
01685   if ((Remainder?4:3)*n+2*m+1 <= 128) {
01686     U = &SPACE[0];
01687     V = &SPACE[m+n+1];
01688     Q = &SPACE[(m+n+1) + n];
01689     if (Remainder)
01690       R = &SPACE[(m+n+1) + n + (m+n)];
01691   } else {
01692     U = new unsigned[m + n + 1];
01693     V = new unsigned[n];
01694     Q = new unsigned[m+n];
01695     if (Remainder)
01696       R = new unsigned[n];
01697   }
01698 
01699   // Initialize the dividend
01700   memset(U, 0, (m+n+1)*sizeof(unsigned));
01701   for (unsigned i = 0; i < lhsWords; ++i) {
01702     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
01703     U[i * 2] = (unsigned)(tmp & mask);
01704     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01705   }
01706   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
01707 
01708   // Initialize the divisor
01709   memset(V, 0, (n)*sizeof(unsigned));
01710   for (unsigned i = 0; i < rhsWords; ++i) {
01711     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
01712     V[i * 2] = (unsigned)(tmp & mask);
01713     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
01714   }
01715 
01716   // initialize the quotient and remainder
01717   memset(Q, 0, (m+n) * sizeof(unsigned));
01718   if (Remainder)
01719     memset(R, 0, n * sizeof(unsigned));
01720 
01721   // Now, adjust m and n for the Knuth division. n is the number of words in
01722   // the divisor. m is the number of words by which the dividend exceeds the
01723   // divisor (i.e. m+n is the length of the dividend). These sizes must not
01724   // contain any zero words or the Knuth algorithm fails.
01725   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
01726     n--;
01727     m++;
01728   }
01729   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
01730     m--;
01731 
01732   // If we're left with only a single word for the divisor, Knuth doesn't work
01733   // so we implement the short division algorithm here. This is much simpler
01734   // and faster because we are certain that we can divide a 64-bit quantity
01735   // by a 32-bit quantity at hardware speed and short division is simply a
01736   // series of such operations. This is just like doing short division but we
01737   // are using base 2^32 instead of base 10.
01738   assert(n != 0 && "Divide by zero?");
01739   if (n == 1) {
01740     unsigned divisor = V[0];
01741     unsigned remainder = 0;
01742     for (int i = m+n-1; i >= 0; i--) {
01743       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
01744       if (partial_dividend == 0) {
01745         Q[i] = 0;
01746         remainder = 0;
01747       } else if (partial_dividend < divisor) {
01748         Q[i] = 0;
01749         remainder = (unsigned)partial_dividend;
01750       } else if (partial_dividend == divisor) {
01751         Q[i] = 1;
01752         remainder = 0;
01753       } else {
01754         Q[i] = (unsigned)(partial_dividend / divisor);
01755         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
01756       }
01757     }
01758     if (R)
01759       R[0] = remainder;
01760   } else {
01761     // Now we're ready to invoke the Knuth classical divide algorithm. In this
01762     // case n > 1.
01763     KnuthDiv(U, V, Q, R, m, n);
01764   }
01765 
01766   // If the caller wants the quotient
01767   if (Quotient) {
01768     // Set up the Quotient value's memory.
01769     if (Quotient->BitWidth != LHS.BitWidth) {
01770       if (Quotient->isSingleWord())
01771         Quotient->VAL = 0;
01772       else
01773         delete [] Quotient->pVal;
01774       Quotient->BitWidth = LHS.BitWidth;
01775       if (!Quotient->isSingleWord())
01776         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
01777     } else
01778       Quotient->clearAllBits();
01779 
01780     // The quotient is in Q. Reconstitute the quotient into Quotient's low
01781     // order words.
01782     // This case is currently dead as all users of divide() handle trivial cases
01783     // earlier.
01784     if (lhsWords == 1) {
01785       uint64_t tmp =
01786         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
01787       if (Quotient->isSingleWord())
01788         Quotient->VAL = tmp;
01789       else
01790         Quotient->pVal[0] = tmp;
01791     } else {
01792       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
01793       for (unsigned i = 0; i < lhsWords; ++i)
01794         Quotient->pVal[i] =
01795           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01796     }
01797   }
01798 
01799   // If the caller wants the remainder
01800   if (Remainder) {
01801     // Set up the Remainder value's memory.
01802     if (Remainder->BitWidth != RHS.BitWidth) {
01803       if (Remainder->isSingleWord())
01804         Remainder->VAL = 0;
01805       else
01806         delete [] Remainder->pVal;
01807       Remainder->BitWidth = RHS.BitWidth;
01808       if (!Remainder->isSingleWord())
01809         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
01810     } else
01811       Remainder->clearAllBits();
01812 
01813     // The remainder is in R. Reconstitute the remainder into Remainder's low
01814     // order words.
01815     if (rhsWords == 1) {
01816       uint64_t tmp =
01817         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
01818       if (Remainder->isSingleWord())
01819         Remainder->VAL = tmp;
01820       else
01821         Remainder->pVal[0] = tmp;
01822     } else {
01823       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
01824       for (unsigned i = 0; i < rhsWords; ++i)
01825         Remainder->pVal[i] =
01826           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
01827     }
01828   }
01829 
01830   // Clean up the memory we allocated.
01831   if (U != &SPACE[0]) {
01832     delete [] U;
01833     delete [] V;
01834     delete [] Q;
01835     delete [] R;
01836   }
01837 }
01838 
01839 APInt APInt::udiv(const APInt& RHS) const {
01840   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01841 
01842   // First, deal with the easy case
01843   if (isSingleWord()) {
01844     assert(RHS.VAL != 0 && "Divide by zero?");
01845     return APInt(BitWidth, VAL / RHS.VAL);
01846   }
01847 
01848   // Get some facts about the LHS and RHS number of bits and words
01849   unsigned rhsBits = RHS.getActiveBits();
01850   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01851   assert(rhsWords && "Divided by zero???");
01852   unsigned lhsBits = this->getActiveBits();
01853   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01854 
01855   // Deal with some degenerate cases
01856   if (!lhsWords)
01857     // 0 / X ===> 0
01858     return APInt(BitWidth, 0);
01859   else if (lhsWords < rhsWords || this->ult(RHS)) {
01860     // X / Y ===> 0, iff X < Y
01861     return APInt(BitWidth, 0);
01862   } else if (*this == RHS) {
01863     // X / X ===> 1
01864     return APInt(BitWidth, 1);
01865   } else if (lhsWords == 1 && rhsWords == 1) {
01866     // All high words are zero, just use native divide
01867     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
01868   }
01869 
01870   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01871   APInt Quotient(1,0); // to hold result.
01872   divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
01873   return Quotient;
01874 }
01875 
01876 APInt APInt::sdiv(const APInt &RHS) const {
01877   if (isNegative()) {
01878     if (RHS.isNegative())
01879       return (-(*this)).udiv(-RHS);
01880     return -((-(*this)).udiv(RHS));
01881   }
01882   if (RHS.isNegative())
01883     return -(this->udiv(-RHS));
01884   return this->udiv(RHS);
01885 }
01886 
01887 APInt APInt::urem(const APInt& RHS) const {
01888   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
01889   if (isSingleWord()) {
01890     assert(RHS.VAL != 0 && "Remainder by zero?");
01891     return APInt(BitWidth, VAL % RHS.VAL);
01892   }
01893 
01894   // Get some facts about the LHS
01895   unsigned lhsBits = getActiveBits();
01896   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
01897 
01898   // Get some facts about the RHS
01899   unsigned rhsBits = RHS.getActiveBits();
01900   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01901   assert(rhsWords && "Performing remainder operation by zero ???");
01902 
01903   // Check the degenerate cases
01904   if (lhsWords == 0) {
01905     // 0 % Y ===> 0
01906     return APInt(BitWidth, 0);
01907   } else if (lhsWords < rhsWords || this->ult(RHS)) {
01908     // X % Y ===> X, iff X < Y
01909     return *this;
01910   } else if (*this == RHS) {
01911     // X % X == 0;
01912     return APInt(BitWidth, 0);
01913   } else if (lhsWords == 1) {
01914     // All high words are zero, just use native remainder
01915     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
01916   }
01917 
01918   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
01919   APInt Remainder(1,0);
01920   divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
01921   return Remainder;
01922 }
01923 
01924 APInt APInt::srem(const APInt &RHS) const {
01925   if (isNegative()) {
01926     if (RHS.isNegative())
01927       return -((-(*this)).urem(-RHS));
01928     return -((-(*this)).urem(RHS));
01929   }
01930   if (RHS.isNegative())
01931     return this->urem(-RHS);
01932   return this->urem(RHS);
01933 }
01934 
01935 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
01936                     APInt &Quotient, APInt &Remainder) {
01937   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
01938 
01939   // First, deal with the easy case
01940   if (LHS.isSingleWord()) {
01941     assert(RHS.VAL != 0 && "Divide by zero?");
01942     uint64_t QuotVal = LHS.VAL / RHS.VAL;
01943     uint64_t RemVal = LHS.VAL % RHS.VAL;
01944     Quotient = APInt(LHS.BitWidth, QuotVal);
01945     Remainder = APInt(LHS.BitWidth, RemVal);
01946     return;
01947   }
01948 
01949   // Get some size facts about the dividend and divisor
01950   unsigned lhsBits  = LHS.getActiveBits();
01951   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
01952   unsigned rhsBits  = RHS.getActiveBits();
01953   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
01954 
01955   // Check the degenerate cases
01956   if (lhsWords == 0) {
01957     Quotient = 0;                // 0 / Y ===> 0
01958     Remainder = 0;               // 0 % Y ===> 0
01959     return;
01960   }
01961 
01962   if (lhsWords < rhsWords || LHS.ult(RHS)) {
01963     Remainder = LHS;            // X % Y ===> X, iff X < Y
01964     Quotient = 0;               // X / Y ===> 0, iff X < Y
01965     return;
01966   }
01967 
01968   if (LHS == RHS) {
01969     Quotient  = 1;              // X / X ===> 1
01970     Remainder = 0;              // X % X ===> 0;
01971     return;
01972   }
01973 
01974   if (lhsWords == 1 && rhsWords == 1) {
01975     // There is only one word to consider so use the native versions.
01976     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
01977     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
01978     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
01979     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
01980     return;
01981   }
01982 
01983   // Okay, lets do it the long way
01984   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
01985 }
01986 
01987 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
01988                     APInt &Quotient, APInt &Remainder) {
01989   if (LHS.isNegative()) {
01990     if (RHS.isNegative())
01991       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
01992     else {
01993       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
01994       Quotient = -Quotient;
01995     }
01996     Remainder = -Remainder;
01997   } else if (RHS.isNegative()) {
01998     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
01999     Quotient = -Quotient;
02000   } else {
02001     APInt::udivrem(LHS, RHS, Quotient, Remainder);
02002   }
02003 }
02004 
02005 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
02006   APInt Res = *this+RHS;
02007   Overflow = isNonNegative() == RHS.isNonNegative() &&
02008              Res.isNonNegative() != isNonNegative();
02009   return Res;
02010 }
02011 
02012 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
02013   APInt Res = *this+RHS;
02014   Overflow = Res.ult(RHS);
02015   return Res;
02016 }
02017 
02018 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
02019   APInt Res = *this - RHS;
02020   Overflow = isNonNegative() != RHS.isNonNegative() &&
02021              Res.isNonNegative() != isNonNegative();
02022   return Res;
02023 }
02024 
02025 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
02026   APInt Res = *this-RHS;
02027   Overflow = Res.ugt(*this);
02028   return Res;
02029 }
02030 
02031 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
02032   // MININT/-1  -->  overflow.
02033   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
02034   return sdiv(RHS);
02035 }
02036 
02037 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
02038   APInt Res = *this * RHS;
02039   
02040   if (*this != 0 && RHS != 0)
02041     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
02042   else
02043     Overflow = false;
02044   return Res;
02045 }
02046 
02047 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
02048   APInt Res = *this * RHS;
02049 
02050   if (*this != 0 && RHS != 0)
02051     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
02052   else
02053     Overflow = false;
02054   return Res;
02055 }
02056 
02057 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
02058   Overflow = ShAmt.uge(getBitWidth());
02059   if (Overflow)
02060     return APInt(BitWidth, 0);
02061 
02062   if (isNonNegative()) // Don't allow sign change.
02063     Overflow = ShAmt.uge(countLeadingZeros());
02064   else
02065     Overflow = ShAmt.uge(countLeadingOnes());
02066   
02067   return *this << ShAmt;
02068 }
02069 
02070 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
02071   Overflow = ShAmt.uge(getBitWidth());
02072   if (Overflow)
02073     return APInt(BitWidth, 0);
02074 
02075   Overflow = ShAmt.ugt(countLeadingZeros());
02076 
02077   return *this << ShAmt;
02078 }
02079 
02080 
02081 
02082 
02083 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
02084   // Check our assumptions here
02085   assert(!str.empty() && "Invalid string length");
02086   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
02087           radix == 36) &&
02088          "Radix should be 2, 8, 10, 16, or 36!");
02089 
02090   StringRef::iterator p = str.begin();
02091   size_t slen = str.size();
02092   bool isNeg = *p == '-';
02093   if (*p == '-' || *p == '+') {
02094     p++;
02095     slen--;
02096     assert(slen && "String is only a sign, needs a value.");
02097   }
02098   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
02099   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
02100   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
02101   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
02102          "Insufficient bit width");
02103 
02104   // Allocate memory
02105   if (!isSingleWord())
02106     pVal = getClearedMemory(getNumWords());
02107 
02108   // Figure out if we can shift instead of multiply
02109   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
02110 
02111   // Set up an APInt for the digit to add outside the loop so we don't
02112   // constantly construct/destruct it.
02113   APInt apdigit(getBitWidth(), 0);
02114   APInt apradix(getBitWidth(), radix);
02115 
02116   // Enter digit traversal loop
02117   for (StringRef::iterator e = str.end(); p != e; ++p) {
02118     unsigned digit = getDigit(*p, radix);
02119     assert(digit < radix && "Invalid character in digit string");
02120 
02121     // Shift or multiply the value by the radix
02122     if (slen > 1) {
02123       if (shift)
02124         *this <<= shift;
02125       else
02126         *this *= apradix;
02127     }
02128 
02129     // Add in the digit we just interpreted
02130     if (apdigit.isSingleWord())
02131       apdigit.VAL = digit;
02132     else
02133       apdigit.pVal[0] = digit;
02134     *this += apdigit;
02135   }
02136   // If its negative, put it in two's complement form
02137   if (isNeg) {
02138     --(*this);
02139     this->flipAllBits();
02140   }
02141 }
02142 
02143 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
02144                      bool Signed, bool formatAsCLiteral) const {
02145   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 
02146           Radix == 36) &&
02147          "Radix should be 2, 8, 10, 16, or 36!");
02148 
02149   const char *Prefix = "";
02150   if (formatAsCLiteral) {
02151     switch (Radix) {
02152       case 2:
02153         // Binary literals are a non-standard extension added in gcc 4.3:
02154         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
02155         Prefix = "0b";
02156         break;
02157       case 8:
02158         Prefix = "0";
02159         break;
02160       case 10:
02161         break; // No prefix
02162       case 16:
02163         Prefix = "0x";
02164         break;
02165       default:
02166         llvm_unreachable("Invalid radix!");
02167     }
02168   }
02169 
02170   // First, check for a zero value and just short circuit the logic below.
02171   if (*this == 0) {
02172     while (*Prefix) {
02173       Str.push_back(*Prefix);
02174       ++Prefix;
02175     };
02176     Str.push_back('0');
02177     return;
02178   }
02179 
02180   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
02181 
02182   if (isSingleWord()) {
02183     char Buffer[65];
02184     char *BufPtr = Buffer+65;
02185 
02186     uint64_t N;
02187     if (!Signed) {
02188       N = getZExtValue();
02189     } else {
02190       int64_t I = getSExtValue();
02191       if (I >= 0) {
02192         N = I;
02193       } else {
02194         Str.push_back('-');
02195         N = -(uint64_t)I;
02196       }
02197     }
02198 
02199     while (*Prefix) {
02200       Str.push_back(*Prefix);
02201       ++Prefix;
02202     };
02203 
02204     while (N) {
02205       *--BufPtr = Digits[N % Radix];
02206       N /= Radix;
02207     }
02208     Str.append(BufPtr, Buffer+65);
02209     return;
02210   }
02211 
02212   APInt Tmp(*this);
02213 
02214   if (Signed && isNegative()) {
02215     // They want to print the signed version and it is a negative value
02216     // Flip the bits and add one to turn it into the equivalent positive
02217     // value and put a '-' in the result.
02218     Tmp.flipAllBits();
02219     ++Tmp;
02220     Str.push_back('-');
02221   }
02222 
02223   while (*Prefix) {
02224     Str.push_back(*Prefix);
02225     ++Prefix;
02226   };
02227 
02228   // We insert the digits backward, then reverse them to get the right order.
02229   unsigned StartDig = Str.size();
02230 
02231   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
02232   // because the number of bits per digit (1, 3 and 4 respectively) divides
02233   // equaly.  We just shift until the value is zero.
02234   if (Radix == 2 || Radix == 8 || Radix == 16) {
02235     // Just shift tmp right for each digit width until it becomes zero
02236     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
02237     unsigned MaskAmt = Radix - 1;
02238 
02239     while (Tmp != 0) {
02240       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
02241       Str.push_back(Digits[Digit]);
02242       Tmp = Tmp.lshr(ShiftAmt);
02243     }
02244   } else {
02245     APInt divisor(Radix == 10? 4 : 8, Radix);
02246     while (Tmp != 0) {
02247       APInt APdigit(1, 0);
02248       APInt tmp2(Tmp.getBitWidth(), 0);
02249       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
02250              &APdigit);
02251       unsigned Digit = (unsigned)APdigit.getZExtValue();
02252       assert(Digit < Radix && "divide failed");
02253       Str.push_back(Digits[Digit]);
02254       Tmp = tmp2;
02255     }
02256   }
02257 
02258   // Reverse the digits before returning.
02259   std::reverse(Str.begin()+StartDig, Str.end());
02260 }
02261 
02262 /// Returns the APInt as a std::string. Note that this is an inefficient method.
02263 /// It is better to pass in a SmallVector/SmallString to the methods above.
02264 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
02265   SmallString<40> S;
02266   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
02267   return S.str();
02268 }
02269 
02270 
02271 void APInt::dump() const {
02272   SmallString<40> S, U;
02273   this->toStringUnsigned(U);
02274   this->toStringSigned(S);
02275   dbgs() << "APInt(" << BitWidth << "b, "
02276          << U << "u " << S << "s)";
02277 }
02278 
02279 void APInt::print(raw_ostream &OS, bool isSigned) const {
02280   SmallString<40> S;
02281   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
02282   OS << S;
02283 }
02284 
02285 // This implements a variety of operations on a representation of
02286 // arbitrary precision, two's-complement, bignum integer values.
02287 
02288 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
02289 // and unrestricting assumption.
02290 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
02291 
02292 /* Some handy functions local to this file.  */
02293 namespace {
02294 
02295   /* Returns the integer part with the least significant BITS set.
02296      BITS cannot be zero.  */
02297   static inline integerPart
02298   lowBitMask(unsigned int bits)
02299   {
02300     assert(bits != 0 && bits <= integerPartWidth);
02301 
02302     return ~(integerPart) 0 >> (integerPartWidth - bits);
02303   }
02304 
02305   /* Returns the value of the lower half of PART.  */
02306   static inline integerPart
02307   lowHalf(integerPart part)
02308   {
02309     return part & lowBitMask(integerPartWidth / 2);
02310   }
02311 
02312   /* Returns the value of the upper half of PART.  */
02313   static inline integerPart
02314   highHalf(integerPart part)
02315   {
02316     return part >> (integerPartWidth / 2);
02317   }
02318 
02319   /* Returns the bit number of the most significant set bit of a part.
02320      If the input number has no bits set -1U is returned.  */
02321   static unsigned int
02322   partMSB(integerPart value)
02323   {
02324     return findLastSet(value, ZB_Max);
02325   }
02326 
02327   /* Returns the bit number of the least significant set bit of a
02328      part.  If the input number has no bits set -1U is returned.  */
02329   static unsigned int
02330   partLSB(integerPart value)
02331   {
02332     return findFirstSet(value, ZB_Max);
02333   }
02334 }
02335 
02336 /* Sets the least significant part of a bignum to the input value, and
02337    zeroes out higher parts.  */
02338 void
02339 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
02340 {
02341   unsigned int i;
02342 
02343   assert(parts > 0);
02344 
02345   dst[0] = part;
02346   for (i = 1; i < parts; i++)
02347     dst[i] = 0;
02348 }
02349 
02350 /* Assign one bignum to another.  */
02351 void
02352 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
02353 {
02354   unsigned int i;
02355 
02356   for (i = 0; i < parts; i++)
02357     dst[i] = src[i];
02358 }
02359 
02360 /* Returns true if a bignum is zero, false otherwise.  */
02361 bool
02362 APInt::tcIsZero(const integerPart *src, unsigned int parts)
02363 {
02364   unsigned int i;
02365 
02366   for (i = 0; i < parts; i++)
02367     if (src[i])
02368       return false;
02369 
02370   return true;
02371 }
02372 
02373 /* Extract the given bit of a bignum; returns 0 or 1.  */
02374 int
02375 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
02376 {
02377   return (parts[bit / integerPartWidth] &
02378           ((integerPart) 1 << bit % integerPartWidth)) != 0;
02379 }
02380 
02381 /* Set the given bit of a bignum. */
02382 void
02383 APInt::tcSetBit(integerPart *parts, unsigned int bit)
02384 {
02385   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
02386 }
02387 
02388 /* Clears the given bit of a bignum. */
02389 void
02390 APInt::tcClearBit(integerPart *parts, unsigned int bit)
02391 {
02392   parts[bit / integerPartWidth] &=
02393     ~((integerPart) 1 << (bit % integerPartWidth));
02394 }
02395 
02396 /* Returns the bit number of the least significant set bit of a
02397    number.  If the input number has no bits set -1U is returned.  */
02398 unsigned int
02399 APInt::tcLSB(const integerPart *parts, unsigned int n)
02400 {
02401   unsigned int i, lsb;
02402 
02403   for (i = 0; i < n; i++) {
02404       if (parts[i] != 0) {
02405           lsb = partLSB(parts[i]);
02406 
02407           return lsb + i * integerPartWidth;
02408       }
02409   }
02410 
02411   return -1U;
02412 }
02413 
02414 /* Returns the bit number of the most significant set bit of a number.
02415    If the input number has no bits set -1U is returned.  */
02416 unsigned int
02417 APInt::tcMSB(const integerPart *parts, unsigned int n)
02418 {
02419   unsigned int msb;
02420 
02421   do {
02422     --n;
02423 
02424     if (parts[n] != 0) {
02425       msb = partMSB(parts[n]);
02426 
02427       return msb + n * integerPartWidth;
02428     }
02429   } while (n);
02430 
02431   return -1U;
02432 }
02433 
02434 /* Copy the bit vector of width srcBITS from SRC, starting at bit
02435    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
02436    the least significant bit of DST.  All high bits above srcBITS in
02437    DST are zero-filled.  */
02438 void
02439 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
02440                  unsigned int srcBits, unsigned int srcLSB)
02441 {
02442   unsigned int firstSrcPart, dstParts, shift, n;
02443 
02444   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
02445   assert(dstParts <= dstCount);
02446 
02447   firstSrcPart = srcLSB / integerPartWidth;
02448   tcAssign (dst, src + firstSrcPart, dstParts);
02449 
02450   shift = srcLSB % integerPartWidth;
02451   tcShiftRight (dst, dstParts, shift);
02452 
02453   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
02454      in DST.  If this is less that srcBits, append the rest, else
02455      clear the high bits.  */
02456   n = dstParts * integerPartWidth - shift;
02457   if (n < srcBits) {
02458     integerPart mask = lowBitMask (srcBits - n);
02459     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
02460                           << n % integerPartWidth);
02461   } else if (n > srcBits) {
02462     if (srcBits % integerPartWidth)
02463       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
02464   }
02465 
02466   /* Clear high parts.  */
02467   while (dstParts < dstCount)
02468     dst[dstParts++] = 0;
02469 }
02470 
02471 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
02472 integerPart
02473 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
02474              integerPart c, unsigned int parts)
02475 {
02476   unsigned int i;
02477 
02478   assert(c <= 1);
02479 
02480   for (i = 0; i < parts; i++) {
02481     integerPart l;
02482 
02483     l = dst[i];
02484     if (c) {
02485       dst[i] += rhs[i] + 1;
02486       c = (dst[i] <= l);
02487     } else {
02488       dst[i] += rhs[i];
02489       c = (dst[i] < l);
02490     }
02491   }
02492 
02493   return c;
02494 }
02495 
02496 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
02497 integerPart
02498 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
02499                   integerPart c, unsigned int parts)
02500 {
02501   unsigned int i;
02502 
02503   assert(c <= 1);
02504 
02505   for (i = 0; i < parts; i++) {
02506     integerPart l;
02507 
02508     l = dst[i];
02509     if (c) {
02510       dst[i] -= rhs[i] + 1;
02511       c = (dst[i] >= l);
02512     } else {
02513       dst[i] -= rhs[i];
02514       c = (dst[i] > l);
02515     }
02516   }
02517 
02518   return c;
02519 }
02520 
02521 /* Negate a bignum in-place.  */
02522 void
02523 APInt::tcNegate(integerPart *dst, unsigned int parts)
02524 {
02525   tcComplement(dst, parts);
02526   tcIncrement(dst, parts);
02527 }
02528 
02529 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
02530     DST  = SRC * MULTIPLIER + CARRY   if add is false
02531 
02532     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
02533     they must start at the same point, i.e. DST == SRC.
02534 
02535     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
02536     returned.  Otherwise DST is filled with the least significant
02537     DSTPARTS parts of the result, and if all of the omitted higher
02538     parts were zero return zero, otherwise overflow occurred and
02539     return one.  */
02540 int
02541 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
02542                       integerPart multiplier, integerPart carry,
02543                       unsigned int srcParts, unsigned int dstParts,
02544                       bool add)
02545 {
02546   unsigned int i, n;
02547 
02548   /* Otherwise our writes of DST kill our later reads of SRC.  */
02549   assert(dst <= src || dst >= src + srcParts);
02550   assert(dstParts <= srcParts + 1);
02551 
02552   /* N loops; minimum of dstParts and srcParts.  */
02553   n = dstParts < srcParts ? dstParts: srcParts;
02554 
02555   for (i = 0; i < n; i++) {
02556     integerPart low, mid, high, srcPart;
02557 
02558       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
02559 
02560          This cannot overflow, because
02561 
02562          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
02563 
02564          which is less than n^2.  */
02565 
02566     srcPart = src[i];
02567 
02568     if (multiplier == 0 || srcPart == 0)        {
02569       low = carry;
02570       high = 0;
02571     } else {
02572       low = lowHalf(srcPart) * lowHalf(multiplier);
02573       high = highHalf(srcPart) * highHalf(multiplier);
02574 
02575       mid = lowHalf(srcPart) * highHalf(multiplier);
02576       high += highHalf(mid);
02577       mid <<= integerPartWidth / 2;
02578       if (low + mid < low)
02579         high++;
02580       low += mid;
02581 
02582       mid = highHalf(srcPart) * lowHalf(multiplier);
02583       high += highHalf(mid);
02584       mid <<= integerPartWidth / 2;
02585       if (low + mid < low)
02586         high++;
02587       low += mid;
02588 
02589       /* Now add carry.  */
02590       if (low + carry < low)
02591         high++;
02592       low += carry;
02593     }
02594 
02595     if (add) {
02596       /* And now DST[i], and store the new low part there.  */
02597       if (low + dst[i] < low)
02598         high++;
02599       dst[i] += low;
02600     } else
02601       dst[i] = low;
02602 
02603     carry = high;
02604   }
02605 
02606   if (i < dstParts) {
02607     /* Full multiplication, there is no overflow.  */
02608     assert(i + 1 == dstParts);
02609     dst[i] = carry;
02610     return 0;
02611   } else {
02612     /* We overflowed if there is carry.  */
02613     if (carry)
02614       return 1;
02615 
02616     /* We would overflow if any significant unwritten parts would be
02617        non-zero.  This is true if any remaining src parts are non-zero
02618        and the multiplier is non-zero.  */
02619     if (multiplier)
02620       for (; i < srcParts; i++)
02621         if (src[i])
02622           return 1;
02623 
02624     /* We fitted in the narrow destination.  */
02625     return 0;
02626   }
02627 }
02628 
02629 /* DST = LHS * RHS, where DST has the same width as the operands and
02630    is filled with the least significant parts of the result.  Returns
02631    one if overflow occurred, otherwise zero.  DST must be disjoint
02632    from both operands.  */
02633 int
02634 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
02635                   const integerPart *rhs, unsigned int parts)
02636 {
02637   unsigned int i;
02638   int overflow;
02639 
02640   assert(dst != lhs && dst != rhs);
02641 
02642   overflow = 0;
02643   tcSet(dst, 0, parts);
02644 
02645   for (i = 0; i < parts; i++)
02646     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
02647                                parts - i, true);
02648 
02649   return overflow;
02650 }
02651 
02652 /* DST = LHS * RHS, where DST has width the sum of the widths of the
02653    operands.  No overflow occurs.  DST must be disjoint from both
02654    operands.  Returns the number of parts required to hold the
02655    result.  */
02656 unsigned int
02657 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
02658                       const integerPart *rhs, unsigned int lhsParts,
02659                       unsigned int rhsParts)
02660 {
02661   /* Put the narrower number on the LHS for less loops below.  */
02662   if (lhsParts > rhsParts) {
02663     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
02664   } else {
02665     unsigned int n;
02666 
02667     assert(dst != lhs && dst != rhs);
02668 
02669     tcSet(dst, 0, rhsParts);
02670 
02671     for (n = 0; n < lhsParts; n++)
02672       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
02673 
02674     n = lhsParts + rhsParts;
02675 
02676     return n - (dst[n - 1] == 0);
02677   }
02678 }
02679 
02680 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
02681    Otherwise set LHS to LHS / RHS with the fractional part discarded,
02682    set REMAINDER to the remainder, return zero.  i.e.
02683 
02684    OLD_LHS = RHS * LHS + REMAINDER
02685 
02686    SCRATCH is a bignum of the same size as the operands and result for
02687    use by the routine; its contents need not be initialized and are
02688    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
02689 */
02690 int
02691 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
02692                 integerPart *remainder, integerPart *srhs,
02693                 unsigned int parts)
02694 {
02695   unsigned int n, shiftCount;
02696   integerPart mask;
02697 
02698   assert(lhs != remainder && lhs != srhs && remainder != srhs);
02699 
02700   shiftCount = tcMSB(rhs, parts) + 1;
02701   if (shiftCount == 0)
02702     return true;
02703 
02704   shiftCount = parts * integerPartWidth - shiftCount;
02705   n = shiftCount / integerPartWidth;
02706   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
02707 
02708   tcAssign(srhs, rhs, parts);
02709   tcShiftLeft(srhs, parts, shiftCount);
02710   tcAssign(remainder, lhs, parts);
02711   tcSet(lhs, 0, parts);
02712 
02713   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
02714      the total.  */
02715   for (;;) {
02716       int compare;
02717 
02718       compare = tcCompare(remainder, srhs, parts);
02719       if (compare >= 0) {
02720         tcSubtract(remainder, srhs, 0, parts);
02721         lhs[n] |= mask;
02722       }
02723 
02724       if (shiftCount == 0)
02725         break;
02726       shiftCount--;
02727       tcShiftRight(srhs, parts, 1);
02728       if ((mask >>= 1) == 0)
02729         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
02730   }
02731 
02732   return false;
02733 }
02734 
02735 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
02736    There are no restrictions on COUNT.  */
02737 void
02738 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
02739 {
02740   if (count) {
02741     unsigned int jump, shift;
02742 
02743     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02744     jump = count / integerPartWidth;
02745     shift = count % integerPartWidth;
02746 
02747     while (parts > jump) {
02748       integerPart part;
02749 
02750       parts--;
02751 
02752       /* dst[i] comes from the two parts src[i - jump] and, if we have
02753          an intra-part shift, src[i - jump - 1].  */
02754       part = dst[parts - jump];
02755       if (shift) {
02756         part <<= shift;
02757         if (parts >= jump + 1)
02758           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
02759       }
02760 
02761       dst[parts] = part;
02762     }
02763 
02764     while (parts > 0)
02765       dst[--parts] = 0;
02766   }
02767 }
02768 
02769 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
02770    zero.  There are no restrictions on COUNT.  */
02771 void
02772 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
02773 {
02774   if (count) {
02775     unsigned int i, jump, shift;
02776 
02777     /* Jump is the inter-part jump; shift is is intra-part shift.  */
02778     jump = count / integerPartWidth;
02779     shift = count % integerPartWidth;
02780 
02781     /* Perform the shift.  This leaves the most significant COUNT bits
02782        of the result at zero.  */
02783     for (i = 0; i < parts; i++) {
02784       integerPart part;
02785 
02786       if (i + jump >= parts) {
02787         part = 0;
02788       } else {
02789         part = dst[i + jump];
02790         if (shift) {
02791           part >>= shift;
02792           if (i + jump + 1 < parts)
02793             part |= dst[i + jump + 1] << (integerPartWidth - shift);
02794         }
02795       }
02796 
02797       dst[i] = part;
02798     }
02799   }
02800 }
02801 
02802 /* Bitwise and of two bignums.  */
02803 void
02804 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
02805 {
02806   unsigned int i;
02807 
02808   for (i = 0; i < parts; i++)
02809     dst[i] &= rhs[i];
02810 }
02811 
02812 /* Bitwise inclusive or of two bignums.  */
02813 void
02814 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
02815 {
02816   unsigned int i;
02817 
02818   for (i = 0; i < parts; i++)
02819     dst[i] |= rhs[i];
02820 }
02821 
02822 /* Bitwise exclusive or of two bignums.  */
02823 void
02824 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
02825 {
02826   unsigned int i;
02827 
02828   for (i = 0; i < parts; i++)
02829     dst[i] ^= rhs[i];
02830 }
02831 
02832 /* Complement a bignum in-place.  */
02833 void
02834 APInt::tcComplement(integerPart *dst, unsigned int parts)
02835 {
02836   unsigned int i;
02837 
02838   for (i = 0; i < parts; i++)
02839     dst[i] = ~dst[i];
02840 }
02841 
02842 /* Comparison (unsigned) of two bignums.  */
02843 int
02844 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
02845                  unsigned int parts)
02846 {
02847   while (parts) {
02848       parts--;
02849       if (lhs[parts] == rhs[parts])
02850         continue;
02851 
02852       if (lhs[parts] > rhs[parts])
02853         return 1;
02854       else
02855         return -1;
02856     }
02857 
02858   return 0;
02859 }
02860 
02861 /* Increment a bignum in-place, return the carry flag.  */
02862 integerPart
02863 APInt::tcIncrement(integerPart *dst, unsigned int parts)
02864 {
02865   unsigned int i;
02866 
02867   for (i = 0; i < parts; i++)
02868     if (++dst[i] != 0)
02869       break;
02870 
02871   return i == parts;
02872 }
02873 
02874 /* Decrement a bignum in-place, return the borrow flag.  */
02875 integerPart
02876 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
02877   for (unsigned int i = 0; i < parts; i++) {
02878     // If the current word is non-zero, then the decrement has no effect on the
02879     // higher-order words of the integer and no borrow can occur. Exit early.
02880     if (dst[i]--)
02881       return 0;
02882   }
02883   // If every word was zero, then there is a borrow.
02884   return 1;
02885 }
02886 
02887 
02888 /* Set the least significant BITS bits of a bignum, clear the
02889    rest.  */
02890 void
02891 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
02892                                  unsigned int bits)
02893 {
02894   unsigned int i;
02895 
02896   i = 0;
02897   while (bits > integerPartWidth) {
02898     dst[i++] = ~(integerPart) 0;
02899     bits -= integerPartWidth;
02900   }
02901 
02902   if (bits)
02903     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
02904 
02905   while (i < parts)
02906     dst[i++] = 0;
02907 }