LLVM API Documentation

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