Home | History | Annotate | Download | only in Support
      1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements a class to represent arbitrary precision integer
     11 // constant values and provide a variety of arithmetic operations on them.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #define DEBUG_TYPE "apint"
     16 #include "llvm/ADT/APInt.h"
     17 #include "llvm/ADT/FoldingSet.h"
     18 #include "llvm/ADT/Hashing.h"
     19 #include "llvm/ADT/SmallString.h"
     20 #include "llvm/ADT/StringRef.h"
     21 #include "llvm/Support/Debug.h"
     22 #include "llvm/Support/ErrorHandling.h"
     23 #include "llvm/Support/MathExtras.h"
     24 #include "llvm/Support/raw_ostream.h"
     25 #include <cmath>
     26 #include <cstdlib>
     27 #include <cstring>
     28 #include <limits>
     29 using namespace llvm;
     30 
     31 /// A utility function for allocating memory, checking for allocation failures,
     32 /// and ensuring the contents are zeroed.
     33 inline static uint64_t* getClearedMemory(unsigned numWords) {
     34   uint64_t * result = new uint64_t[numWords];
     35   assert(result && "APInt memory allocation fails!");
     36   memset(result, 0, numWords * sizeof(uint64_t));
     37   return result;
     38 }
     39 
     40 /// A utility function for allocating memory and checking for allocation
     41 /// failure.  The content is not zeroed.
     42 inline static uint64_t* getMemory(unsigned numWords) {
     43   uint64_t * result = new uint64_t[numWords];
     44   assert(result && "APInt memory allocation fails!");
     45   return result;
     46 }
     47 
     48 /// A utility function that converts a character to a digit.
     49 inline static unsigned getDigit(char cdigit, uint8_t radix) {
     50   unsigned r;
     51 
     52   if (radix == 16 || radix == 36) {
     53     r = cdigit - '0';
     54     if (r <= 9)
     55       return r;
     56 
     57     r = cdigit - 'A';
     58     if (r <= radix - 11U)
     59       return r + 10;
     60 
     61     r = cdigit - 'a';
     62     if (r <= radix - 11U)
     63       return r + 10;
     64 
     65     radix = 10;
     66   }
     67 
     68   r = cdigit - '0';
     69   if (r < radix)
     70     return r;
     71 
     72   return -1U;
     73 }
     74 
     75 
     76 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
     77   pVal = getClearedMemory(getNumWords());
     78   pVal[0] = val;
     79   if (isSigned && int64_t(val) < 0)
     80     for (unsigned i = 1; i < getNumWords(); ++i)
     81       pVal[i] = -1ULL;
     82 }
     83 
     84 void APInt::initSlowCase(const APInt& that) {
     85   pVal = getMemory(getNumWords());
     86   memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
     87 }
     88 
     89 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
     90   assert(BitWidth && "Bitwidth too small");
     91   assert(bigVal.data() && "Null pointer detected!");
     92   if (isSingleWord())
     93     VAL = bigVal[0];
     94   else {
     95     // Get memory, cleared to 0
     96     pVal = getClearedMemory(getNumWords());
     97     // Calculate the number of words to copy
     98     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     99     // Copy the words from bigVal to pVal
    100     memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
    101   }
    102   // Make sure unused high bits are cleared
    103   clearUnusedBits();
    104 }
    105 
    106 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
    107   : BitWidth(numBits), VAL(0) {
    108   initFromArray(bigVal);
    109 }
    110 
    111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
    112   : BitWidth(numBits), VAL(0) {
    113   initFromArray(makeArrayRef(bigVal, numWords));
    114 }
    115 
    116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
    117   : BitWidth(numbits), VAL(0) {
    118   assert(BitWidth && "Bitwidth too small");
    119   fromString(numbits, Str, radix);
    120 }
    121 
    122 APInt& APInt::AssignSlowCase(const APInt& RHS) {
    123   // Don't do anything for X = X
    124   if (this == &RHS)
    125     return *this;
    126 
    127   if (BitWidth == RHS.getBitWidth()) {
    128     // assume same bit-width single-word case is already handled
    129     assert(!isSingleWord());
    130     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
    131     return *this;
    132   }
    133 
    134   if (isSingleWord()) {
    135     // assume case where both are single words is already handled
    136     assert(!RHS.isSingleWord());
    137     VAL = 0;
    138     pVal = getMemory(RHS.getNumWords());
    139     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    140   } else if (getNumWords() == RHS.getNumWords())
    141     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    142   else if (RHS.isSingleWord()) {
    143     delete [] pVal;
    144     VAL = RHS.VAL;
    145   } else {
    146     delete [] pVal;
    147     pVal = getMemory(RHS.getNumWords());
    148     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    149   }
    150   BitWidth = RHS.BitWidth;
    151   return clearUnusedBits();
    152 }
    153 
    154 APInt& APInt::operator=(uint64_t RHS) {
    155   if (isSingleWord())
    156     VAL = RHS;
    157   else {
    158     pVal[0] = RHS;
    159     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
    160   }
    161   return clearUnusedBits();
    162 }
    163 
    164 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
    165 void APInt::Profile(FoldingSetNodeID& ID) const {
    166   ID.AddInteger(BitWidth);
    167 
    168   if (isSingleWord()) {
    169     ID.AddInteger(VAL);
    170     return;
    171   }
    172 
    173   unsigned NumWords = getNumWords();
    174   for (unsigned i = 0; i < NumWords; ++i)
    175     ID.AddInteger(pVal[i]);
    176 }
    177 
    178 /// add_1 - This function adds a single "digit" integer, y, to the multiple
    179 /// "digit" integer array,  x[]. x[] is modified to reflect the addition and
    180 /// 1 is returned if there is a carry out, otherwise 0 is returned.
    181 /// @returns the carry of the addition.
    182 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
    183   for (unsigned i = 0; i < len; ++i) {
    184     dest[i] = y + x[i];
    185     if (dest[i] < y)
    186       y = 1; // Carry one to next digit.
    187     else {
    188       y = 0; // No need to carry so exit early
    189       break;
    190     }
    191   }
    192   return y;
    193 }
    194 
    195 /// @brief Prefix increment operator. Increments the APInt by one.
    196 APInt& APInt::operator++() {
    197   if (isSingleWord())
    198     ++VAL;
    199   else
    200     add_1(pVal, pVal, getNumWords(), 1);
    201   return clearUnusedBits();
    202 }
    203 
    204 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
    205 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
    206 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
    207 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
    208 /// In other words, if y > x then this function returns 1, otherwise 0.
    209 /// @returns the borrow out of the subtraction
    210 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
    211   for (unsigned i = 0; i < len; ++i) {
    212     uint64_t X = x[i];
    213     x[i] -= y;
    214     if (y > X)
    215       y = 1;  // We have to "borrow 1" from next "digit"
    216     else {
    217       y = 0;  // No need to borrow
    218       break;  // Remaining digits are unchanged so exit early
    219     }
    220   }
    221   return bool(y);
    222 }
    223 
    224 /// @brief Prefix decrement operator. Decrements the APInt by one.
    225 APInt& APInt::operator--() {
    226   if (isSingleWord())
    227     --VAL;
    228   else
    229     sub_1(pVal, getNumWords(), 1);
    230   return clearUnusedBits();
    231 }
    232 
    233 /// add - This function adds the integer array x to the integer array Y and
    234 /// places the result in dest.
    235 /// @returns the carry out from the addition
    236 /// @brief General addition of 64-bit integer arrays
    237 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
    238                 unsigned len) {
    239   bool carry = false;
    240   for (unsigned i = 0; i< len; ++i) {
    241     uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
    242     dest[i] = x[i] + y[i] + carry;
    243     carry = dest[i] < limit || (carry && dest[i] == limit);
    244   }
    245   return carry;
    246 }
    247 
    248 /// Adds the RHS APint to this APInt.
    249 /// @returns this, after addition of RHS.
    250 /// @brief Addition assignment operator.
    251 APInt& APInt::operator+=(const APInt& RHS) {
    252   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    253   if (isSingleWord())
    254     VAL += RHS.VAL;
    255   else {
    256     add(pVal, pVal, RHS.pVal, getNumWords());
    257   }
    258   return clearUnusedBits();
    259 }
    260 
    261 /// Subtracts the integer array y from the integer array x
    262 /// @returns returns the borrow out.
    263 /// @brief Generalized subtraction of 64-bit integer arrays.
    264 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
    265                 unsigned len) {
    266   bool borrow = false;
    267   for (unsigned i = 0; i < len; ++i) {
    268     uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
    269     borrow = y[i] > x_tmp || (borrow && x[i] == 0);
    270     dest[i] = x_tmp - y[i];
    271   }
    272   return borrow;
    273 }
    274 
    275 /// Subtracts the RHS APInt from this APInt
    276 /// @returns this, after subtraction
    277 /// @brief Subtraction assignment operator.
    278 APInt& APInt::operator-=(const APInt& RHS) {
    279   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    280   if (isSingleWord())
    281     VAL -= RHS.VAL;
    282   else
    283     sub(pVal, pVal, RHS.pVal, getNumWords());
    284   return clearUnusedBits();
    285 }
    286 
    287 /// Multiplies an integer array, x, by a uint64_t integer and places the result
    288 /// into dest.
    289 /// @returns the carry out of the multiplication.
    290 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
    291 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
    292   // Split y into high 32-bit part (hy)  and low 32-bit part (ly)
    293   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
    294   uint64_t carry = 0;
    295 
    296   // For each digit of x.
    297   for (unsigned i = 0; i < len; ++i) {
    298     // Split x into high and low words
    299     uint64_t lx = x[i] & 0xffffffffULL;
    300     uint64_t hx = x[i] >> 32;
    301     // hasCarry - A flag to indicate if there is a carry to the next digit.
    302     // hasCarry == 0, no carry
    303     // hasCarry == 1, has carry
    304     // hasCarry == 2, no carry and the calculation result == 0.
    305     uint8_t hasCarry = 0;
    306     dest[i] = carry + lx * ly;
    307     // Determine if the add above introduces carry.
    308     hasCarry = (dest[i] < carry) ? 1 : 0;
    309     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
    310     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
    311     // (2^32 - 1) + 2^32 = 2^64.
    312     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
    313 
    314     carry += (lx * hy) & 0xffffffffULL;
    315     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
    316     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
    317             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
    318   }
    319   return carry;
    320 }
    321 
    322 /// Multiplies integer array x by integer array y and stores the result into
    323 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
    324 /// @brief Generalized multiplicate of integer arrays.
    325 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
    326                 unsigned ylen) {
    327   dest[xlen] = mul_1(dest, x, xlen, y[0]);
    328   for (unsigned i = 1; i < ylen; ++i) {
    329     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
    330     uint64_t carry = 0, lx = 0, hx = 0;
    331     for (unsigned j = 0; j < xlen; ++j) {
    332       lx = x[j] & 0xffffffffULL;
    333       hx = x[j] >> 32;
    334       // hasCarry - A flag to indicate if has carry.
    335       // hasCarry == 0, no carry
    336       // hasCarry == 1, has carry
    337       // hasCarry == 2, no carry and the calculation result == 0.
    338       uint8_t hasCarry = 0;
    339       uint64_t resul = carry + lx * ly;
    340       hasCarry = (resul < carry) ? 1 : 0;
    341       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
    342       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
    343 
    344       carry += (lx * hy) & 0xffffffffULL;
    345       resul = (carry << 32) | (resul & 0xffffffffULL);
    346       dest[i+j] += resul;
    347       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
    348               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
    349               ((lx * hy) >> 32) + hx * hy;
    350     }
    351     dest[i+xlen] = carry;
    352   }
    353 }
    354 
    355 APInt& APInt::operator*=(const APInt& RHS) {
    356   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    357   if (isSingleWord()) {
    358     VAL *= RHS.VAL;
    359     clearUnusedBits();
    360     return *this;
    361   }
    362 
    363   // Get some bit facts about LHS and check for zero
    364   unsigned lhsBits = getActiveBits();
    365   unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
    366   if (!lhsWords)
    367     // 0 * X ===> 0
    368     return *this;
    369 
    370   // Get some bit facts about RHS and check for zero
    371   unsigned rhsBits = RHS.getActiveBits();
    372   unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
    373   if (!rhsWords) {
    374     // X * 0 ===> 0
    375     clearAllBits();
    376     return *this;
    377   }
    378 
    379   // Allocate space for the result
    380   unsigned destWords = rhsWords + lhsWords;
    381   uint64_t *dest = getMemory(destWords);
    382 
    383   // Perform the long multiply
    384   mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
    385 
    386   // Copy result back into *this
    387   clearAllBits();
    388   unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
    389   memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
    390   clearUnusedBits();
    391 
    392   // delete dest array and return
    393   delete[] dest;
    394   return *this;
    395 }
    396 
    397 APInt& APInt::operator&=(const APInt& RHS) {
    398   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    399   if (isSingleWord()) {
    400     VAL &= RHS.VAL;
    401     return *this;
    402   }
    403   unsigned numWords = getNumWords();
    404   for (unsigned i = 0; i < numWords; ++i)
    405     pVal[i] &= RHS.pVal[i];
    406   return *this;
    407 }
    408 
    409 APInt& APInt::operator|=(const APInt& RHS) {
    410   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    411   if (isSingleWord()) {
    412     VAL |= RHS.VAL;
    413     return *this;
    414   }
    415   unsigned numWords = getNumWords();
    416   for (unsigned i = 0; i < numWords; ++i)
    417     pVal[i] |= RHS.pVal[i];
    418   return *this;
    419 }
    420 
    421 APInt& APInt::operator^=(const APInt& RHS) {
    422   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    423   if (isSingleWord()) {
    424     VAL ^= RHS.VAL;
    425     this->clearUnusedBits();
    426     return *this;
    427   }
    428   unsigned numWords = getNumWords();
    429   for (unsigned i = 0; i < numWords; ++i)
    430     pVal[i] ^= RHS.pVal[i];
    431   return clearUnusedBits();
    432 }
    433 
    434 APInt APInt::AndSlowCase(const APInt& RHS) const {
    435   unsigned numWords = getNumWords();
    436   uint64_t* val = getMemory(numWords);
    437   for (unsigned i = 0; i < numWords; ++i)
    438     val[i] = pVal[i] & RHS.pVal[i];
    439   return APInt(val, getBitWidth());
    440 }
    441 
    442 APInt APInt::OrSlowCase(const APInt& RHS) const {
    443   unsigned numWords = getNumWords();
    444   uint64_t *val = getMemory(numWords);
    445   for (unsigned i = 0; i < numWords; ++i)
    446     val[i] = pVal[i] | RHS.pVal[i];
    447   return APInt(val, getBitWidth());
    448 }
    449 
    450 APInt APInt::XorSlowCase(const APInt& RHS) const {
    451   unsigned numWords = getNumWords();
    452   uint64_t *val = getMemory(numWords);
    453   for (unsigned i = 0; i < numWords; ++i)
    454     val[i] = pVal[i] ^ RHS.pVal[i];
    455 
    456   // 0^0==1 so clear the high bits in case they got set.
    457   return APInt(val, getBitWidth()).clearUnusedBits();
    458 }
    459 
    460 APInt APInt::operator*(const APInt& RHS) const {
    461   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    462   if (isSingleWord())
    463     return APInt(BitWidth, VAL * RHS.VAL);
    464   APInt Result(*this);
    465   Result *= RHS;
    466   return Result;
    467 }
    468 
    469 APInt APInt::operator+(const APInt& RHS) const {
    470   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    471   if (isSingleWord())
    472     return APInt(BitWidth, VAL + RHS.VAL);
    473   APInt Result(BitWidth, 0);
    474   add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
    475   return Result.clearUnusedBits();
    476 }
    477 
    478 APInt APInt::operator-(const APInt& RHS) const {
    479   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    480   if (isSingleWord())
    481     return APInt(BitWidth, VAL - RHS.VAL);
    482   APInt Result(BitWidth, 0);
    483   sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
    484   return Result.clearUnusedBits();
    485 }
    486 
    487 bool APInt::EqualSlowCase(const APInt& RHS) const {
    488   // Get some facts about the number of bits used in the two operands.
    489   unsigned n1 = getActiveBits();
    490   unsigned n2 = RHS.getActiveBits();
    491 
    492   // If the number of bits isn't the same, they aren't equal
    493   if (n1 != n2)
    494     return false;
    495 
    496   // If the number of bits fits in a word, we only need to compare the low word.
    497   if (n1 <= APINT_BITS_PER_WORD)
    498     return pVal[0] == RHS.pVal[0];
    499 
    500   // Otherwise, compare everything
    501   for (int i = whichWord(n1 - 1); i >= 0; --i)
    502     if (pVal[i] != RHS.pVal[i])
    503       return false;
    504   return true;
    505 }
    506 
    507 bool APInt::EqualSlowCase(uint64_t Val) const {
    508   unsigned n = getActiveBits();
    509   if (n <= APINT_BITS_PER_WORD)
    510     return pVal[0] == Val;
    511   else
    512     return false;
    513 }
    514 
    515 bool APInt::ult(const APInt& RHS) const {
    516   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
    517   if (isSingleWord())
    518     return VAL < RHS.VAL;
    519 
    520   // Get active bit length of both operands
    521   unsigned n1 = getActiveBits();
    522   unsigned n2 = RHS.getActiveBits();
    523 
    524   // If magnitude of LHS is less than RHS, return true.
    525   if (n1 < n2)
    526     return true;
    527 
    528   // If magnitude of RHS is greather than LHS, return false.
    529   if (n2 < n1)
    530     return false;
    531 
    532   // If they bot fit in a word, just compare the low order word
    533   if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
    534     return pVal[0] < RHS.pVal[0];
    535 
    536   // Otherwise, compare all words
    537   unsigned topWord = whichWord(std::max(n1,n2)-1);
    538   for (int i = topWord; i >= 0; --i) {
    539     if (pVal[i] > RHS.pVal[i])
    540       return false;
    541     if (pVal[i] < RHS.pVal[i])
    542       return true;
    543   }
    544   return false;
    545 }
    546 
    547 bool APInt::slt(const APInt& RHS) const {
    548   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
    549   if (isSingleWord()) {
    550     int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
    551     int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
    552     return lhsSext < rhsSext;
    553   }
    554 
    555   APInt lhs(*this);
    556   APInt rhs(RHS);
    557   bool lhsNeg = isNegative();
    558   bool rhsNeg = rhs.isNegative();
    559   if (lhsNeg) {
    560     // Sign bit is set so perform two's complement to make it positive
    561     lhs.flipAllBits();
    562     ++lhs;
    563   }
    564   if (rhsNeg) {
    565     // Sign bit is set so perform two's complement to make it positive
    566     rhs.flipAllBits();
    567     ++rhs;
    568   }
    569 
    570   // Now we have unsigned values to compare so do the comparison if necessary
    571   // based on the negativeness of the values.
    572   if (lhsNeg)
    573     if (rhsNeg)
    574       return lhs.ugt(rhs);
    575     else
    576       return true;
    577   else if (rhsNeg)
    578     return false;
    579   else
    580     return lhs.ult(rhs);
    581 }
    582 
    583 void APInt::setBit(unsigned bitPosition) {
    584   if (isSingleWord())
    585     VAL |= maskBit(bitPosition);
    586   else
    587     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
    588 }
    589 
    590 /// Set the given bit to 0 whose position is given as "bitPosition".
    591 /// @brief Set a given bit to 0.
    592 void APInt::clearBit(unsigned bitPosition) {
    593   if (isSingleWord())
    594     VAL &= ~maskBit(bitPosition);
    595   else
    596     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
    597 }
    598 
    599 /// @brief Toggle every bit to its opposite value.
    600 
    601 /// Toggle a given bit to its opposite value whose position is given
    602 /// as "bitPosition".
    603 /// @brief Toggles a given bit to its opposite value.
    604 void APInt::flipBit(unsigned bitPosition) {
    605   assert(bitPosition < BitWidth && "Out of the bit-width range!");
    606   if ((*this)[bitPosition]) clearBit(bitPosition);
    607   else setBit(bitPosition);
    608 }
    609 
    610 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
    611   assert(!str.empty() && "Invalid string length");
    612   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
    613           radix == 36) &&
    614          "Radix should be 2, 8, 10, 16, or 36!");
    615 
    616   size_t slen = str.size();
    617 
    618   // Each computation below needs to know if it's negative.
    619   StringRef::iterator p = str.begin();
    620   unsigned isNegative = *p == '-';
    621   if (*p == '-' || *p == '+') {
    622     p++;
    623     slen--;
    624     assert(slen && "String is only a sign, needs a value.");
    625   }
    626 
    627   // For radixes of power-of-two values, the bits required is accurately and
    628   // easily computed
    629   if (radix == 2)
    630     return slen + isNegative;
    631   if (radix == 8)
    632     return slen * 3 + isNegative;
    633   if (radix == 16)
    634     return slen * 4 + isNegative;
    635 
    636   // FIXME: base 36
    637 
    638   // This is grossly inefficient but accurate. We could probably do something
    639   // with a computation of roughly slen*64/20 and then adjust by the value of
    640   // the first few digits. But, I'm not sure how accurate that could be.
    641 
    642   // Compute a sufficient number of bits that is always large enough but might
    643   // be too large. This avoids the assertion in the constructor. This
    644   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
    645   // bits in that case.
    646   unsigned sufficient
    647     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
    648                  : (slen == 1 ? 7 : slen * 16/3);
    649 
    650   // Convert to the actual binary value.
    651   APInt tmp(sufficient, StringRef(p, slen), radix);
    652 
    653   // Compute how many bits are required. If the log is infinite, assume we need
    654   // just bit.
    655   unsigned log = tmp.logBase2();
    656   if (log == (unsigned)-1) {
    657     return isNegative + 1;
    658   } else {
    659     return isNegative + log + 1;
    660   }
    661 }
    662 
    663 hash_code llvm::hash_value(const APInt &Arg) {
    664   if (Arg.isSingleWord())
    665     return hash_combine(Arg.VAL);
    666 
    667   return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
    668 }
    669 
    670 /// HiBits - This function returns the high "numBits" bits of this APInt.
    671 APInt APInt::getHiBits(unsigned numBits) const {
    672   return APIntOps::lshr(*this, BitWidth - numBits);
    673 }
    674 
    675 /// LoBits - This function returns the low "numBits" bits of this APInt.
    676 APInt APInt::getLoBits(unsigned numBits) const {
    677   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
    678                         BitWidth - numBits);
    679 }
    680 
    681 unsigned APInt::countLeadingZerosSlowCase() const {
    682   // Treat the most significand word differently because it might have
    683   // meaningless bits set beyond the precision.
    684   unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
    685   integerPart MSWMask;
    686   if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
    687   else {
    688     MSWMask = ~integerPart(0);
    689     BitsInMSW = APINT_BITS_PER_WORD;
    690   }
    691 
    692   unsigned i = getNumWords();
    693   integerPart MSW = pVal[i-1] & MSWMask;
    694   if (MSW)
    695     return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
    696 
    697   unsigned Count = BitsInMSW;
    698   for (--i; i > 0u; --i) {
    699     if (pVal[i-1] == 0)
    700       Count += APINT_BITS_PER_WORD;
    701     else {
    702       Count += llvm::countLeadingZeros(pVal[i-1]);
    703       break;
    704     }
    705   }
    706   return Count;
    707 }
    708 
    709 unsigned APInt::countLeadingOnes() const {
    710   if (isSingleWord())
    711     return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
    712 
    713   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
    714   unsigned shift;
    715   if (!highWordBits) {
    716     highWordBits = APINT_BITS_PER_WORD;
    717     shift = 0;
    718   } else {
    719     shift = APINT_BITS_PER_WORD - highWordBits;
    720   }
    721   int i = getNumWords() - 1;
    722   unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
    723   if (Count == highWordBits) {
    724     for (i--; i >= 0; --i) {
    725       if (pVal[i] == -1ULL)
    726         Count += APINT_BITS_PER_WORD;
    727       else {
    728         Count += CountLeadingOnes_64(pVal[i]);
    729         break;
    730       }
    731     }
    732   }
    733   return Count;
    734 }
    735 
    736 unsigned APInt::countTrailingZeros() const {
    737   if (isSingleWord())
    738     return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
    739   unsigned Count = 0;
    740   unsigned i = 0;
    741   for (; i < getNumWords() && pVal[i] == 0; ++i)
    742     Count += APINT_BITS_PER_WORD;
    743   if (i < getNumWords())
    744     Count += llvm::countTrailingZeros(pVal[i]);
    745   return std::min(Count, BitWidth);
    746 }
    747 
    748 unsigned APInt::countTrailingOnesSlowCase() const {
    749   unsigned Count = 0;
    750   unsigned i = 0;
    751   for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
    752     Count += APINT_BITS_PER_WORD;
    753   if (i < getNumWords())
    754     Count += CountTrailingOnes_64(pVal[i]);
    755   return std::min(Count, BitWidth);
    756 }
    757 
    758 unsigned APInt::countPopulationSlowCase() const {
    759   unsigned Count = 0;
    760   for (unsigned i = 0; i < getNumWords(); ++i)
    761     Count += CountPopulation_64(pVal[i]);
    762   return Count;
    763 }
    764 
    765 /// Perform a logical right-shift from Src to Dst, which must be equal or
    766 /// non-overlapping, of Words words, by Shift, which must be less than 64.
    767 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
    768                      unsigned Shift) {
    769   uint64_t Carry = 0;
    770   for (int I = Words - 1; I >= 0; --I) {
    771     uint64_t Tmp = Src[I];
    772     Dst[I] = (Tmp >> Shift) | Carry;
    773     Carry = Tmp << (64 - Shift);
    774   }
    775 }
    776 
    777 APInt APInt::byteSwap() const {
    778   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
    779   if (BitWidth == 16)
    780     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
    781   if (BitWidth == 32)
    782     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
    783   if (BitWidth == 48) {
    784     unsigned Tmp1 = unsigned(VAL >> 16);
    785     Tmp1 = ByteSwap_32(Tmp1);
    786     uint16_t Tmp2 = uint16_t(VAL);
    787     Tmp2 = ByteSwap_16(Tmp2);
    788     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
    789   }
    790   if (BitWidth == 64)
    791     return APInt(BitWidth, ByteSwap_64(VAL));
    792 
    793   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
    794   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
    795     Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
    796   if (Result.BitWidth != BitWidth) {
    797     lshrNear(Result.pVal, Result.pVal, getNumWords(),
    798              Result.BitWidth - BitWidth);
    799     Result.BitWidth = BitWidth;
    800   }
    801   return Result;
    802 }
    803 
    804 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
    805                                             const APInt& API2) {
    806   APInt A = API1, B = API2;
    807   while (!!B) {
    808     APInt T = B;
    809     B = APIntOps::urem(A, B);
    810     A = T;
    811   }
    812   return A;
    813 }
    814 
    815 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
    816   union {
    817     double D;
    818     uint64_t I;
    819   } T;
    820   T.D = Double;
    821 
    822   // Get the sign bit from the highest order bit
    823   bool isNeg = T.I >> 63;
    824 
    825   // Get the 11-bit exponent and adjust for the 1023 bit bias
    826   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
    827 
    828   // If the exponent is negative, the value is < 0 so just return 0.
    829   if (exp < 0)
    830     return APInt(width, 0u);
    831 
    832   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
    833   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
    834 
    835   // If the exponent doesn't shift all bits out of the mantissa
    836   if (exp < 52)
    837     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
    838                     APInt(width, mantissa >> (52 - exp));
    839 
    840   // If the client didn't provide enough bits for us to shift the mantissa into
    841   // then the result is undefined, just return 0
    842   if (width <= exp - 52)
    843     return APInt(width, 0);
    844 
    845   // Otherwise, we have to shift the mantissa bits up to the right location
    846   APInt Tmp(width, mantissa);
    847   Tmp = Tmp.shl((unsigned)exp - 52);
    848   return isNeg ? -Tmp : Tmp;
    849 }
    850 
    851 /// RoundToDouble - This function converts this APInt to a double.
    852 /// The layout for double is as following (IEEE Standard 754):
    853 ///  --------------------------------------
    854 /// |  Sign    Exponent    Fraction    Bias |
    855 /// |-------------------------------------- |
    856 /// |  1[63]   11[62-52]   52[51-00]   1023 |
    857 ///  --------------------------------------
    858 double APInt::roundToDouble(bool isSigned) const {
    859 
    860   // Handle the simple case where the value is contained in one uint64_t.
    861   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
    862   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
    863     if (isSigned) {
    864       int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
    865       return double(sext);
    866     } else
    867       return double(getWord(0));
    868   }
    869 
    870   // Determine if the value is negative.
    871   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
    872 
    873   // Construct the absolute value if we're negative.
    874   APInt Tmp(isNeg ? -(*this) : (*this));
    875 
    876   // Figure out how many bits we're using.
    877   unsigned n = Tmp.getActiveBits();
    878 
    879   // The exponent (without bias normalization) is just the number of bits
    880   // we are using. Note that the sign bit is gone since we constructed the
    881   // absolute value.
    882   uint64_t exp = n;
    883 
    884   // Return infinity for exponent overflow
    885   if (exp > 1023) {
    886     if (!isSigned || !isNeg)
    887       return std::numeric_limits<double>::infinity();
    888     else
    889       return -std::numeric_limits<double>::infinity();
    890   }
    891   exp += 1023; // Increment for 1023 bias
    892 
    893   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
    894   // extract the high 52 bits from the correct words in pVal.
    895   uint64_t mantissa;
    896   unsigned hiWord = whichWord(n-1);
    897   if (hiWord == 0) {
    898     mantissa = Tmp.pVal[0];
    899     if (n > 52)
    900       mantissa >>= n - 52; // shift down, we want the top 52 bits.
    901   } else {
    902     assert(hiWord > 0 && "huh?");
    903     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
    904     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
    905     mantissa = hibits | lobits;
    906   }
    907 
    908   // The leading bit of mantissa is implicit, so get rid of it.
    909   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
    910   union {
    911     double D;
    912     uint64_t I;
    913   } T;
    914   T.I = sign | (exp << 52) | mantissa;
    915   return T.D;
    916 }
    917 
    918 // Truncate to new width.
    919 APInt APInt::trunc(unsigned width) const {
    920   assert(width < BitWidth && "Invalid APInt Truncate request");
    921   assert(width && "Can't truncate to 0 bits");
    922 
    923   if (width <= APINT_BITS_PER_WORD)
    924     return APInt(width, getRawData()[0]);
    925 
    926   APInt Result(getMemory(getNumWords(width)), width);
    927 
    928   // Copy full words.
    929   unsigned i;
    930   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
    931     Result.pVal[i] = pVal[i];
    932 
    933   // Truncate and copy any partial word.
    934   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
    935   if (bits != 0)
    936     Result.pVal[i] = pVal[i] << bits >> bits;
    937 
    938   return Result;
    939 }
    940 
    941 // Sign extend to a new width.
    942 APInt APInt::sext(unsigned width) const {
    943   assert(width > BitWidth && "Invalid APInt SignExtend request");
    944 
    945   if (width <= APINT_BITS_PER_WORD) {
    946     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
    947     val = (int64_t)val >> (width - BitWidth);
    948     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
    949   }
    950 
    951   APInt Result(getMemory(getNumWords(width)), width);
    952 
    953   // Copy full words.
    954   unsigned i;
    955   uint64_t word = 0;
    956   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
    957     word = getRawData()[i];
    958     Result.pVal[i] = word;
    959   }
    960 
    961   // Read and sign-extend any partial word.
    962   unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
    963   if (bits != 0)
    964     word = (int64_t)getRawData()[i] << bits >> bits;
    965   else
    966     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
    967 
    968   // Write remaining full words.
    969   for (; i != width / APINT_BITS_PER_WORD; i++) {
    970     Result.pVal[i] = word;
    971     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
    972   }
    973 
    974   // Write any partial word.
    975   bits = (0 - width) % APINT_BITS_PER_WORD;
    976   if (bits != 0)
    977     Result.pVal[i] = word << bits >> bits;
    978 
    979   return Result;
    980 }
    981 
    982 //  Zero extend to a new width.
    983 APInt APInt::zext(unsigned width) const {
    984   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
    985 
    986   if (width <= APINT_BITS_PER_WORD)
    987     return APInt(width, VAL);
    988 
    989   APInt Result(getMemory(getNumWords(width)), width);
    990 
    991   // Copy words.
    992   unsigned i;
    993   for (i = 0; i != getNumWords(); i++)
    994     Result.pVal[i] = getRawData()[i];
    995 
    996   // Zero remaining words.
    997   memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
    998 
    999   return Result;
   1000 }
   1001 
   1002 APInt APInt::zextOrTrunc(unsigned width) const {
   1003   if (BitWidth < width)
   1004     return zext(width);
   1005   if (BitWidth > width)
   1006     return trunc(width);
   1007   return *this;
   1008 }
   1009 
   1010 APInt APInt::sextOrTrunc(unsigned width) const {
   1011   if (BitWidth < width)
   1012     return sext(width);
   1013   if (BitWidth > width)
   1014     return trunc(width);
   1015   return *this;
   1016 }
   1017 
   1018 APInt APInt::zextOrSelf(unsigned width) const {
   1019   if (BitWidth < width)
   1020     return zext(width);
   1021   return *this;
   1022 }
   1023 
   1024 APInt APInt::sextOrSelf(unsigned width) const {
   1025   if (BitWidth < width)
   1026     return sext(width);
   1027   return *this;
   1028 }
   1029 
   1030 /// Arithmetic right-shift this APInt by shiftAmt.
   1031 /// @brief Arithmetic right-shift function.
   1032 APInt APInt::ashr(const APInt &shiftAmt) const {
   1033   return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1034 }
   1035 
   1036 /// Arithmetic right-shift this APInt by shiftAmt.
   1037 /// @brief Arithmetic right-shift function.
   1038 APInt APInt::ashr(unsigned shiftAmt) const {
   1039   assert(shiftAmt <= BitWidth && "Invalid shift amount");
   1040   // Handle a degenerate case
   1041   if (shiftAmt == 0)
   1042     return *this;
   1043 
   1044   // Handle single word shifts with built-in ashr
   1045   if (isSingleWord()) {
   1046     if (shiftAmt == BitWidth)
   1047       return APInt(BitWidth, 0); // undefined
   1048     else {
   1049       unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
   1050       return APInt(BitWidth,
   1051         (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
   1052     }
   1053   }
   1054 
   1055   // If all the bits were shifted out, the result is, technically, undefined.
   1056   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
   1057   // issues in the algorithm below.
   1058   if (shiftAmt == BitWidth) {
   1059     if (isNegative())
   1060       return APInt(BitWidth, -1ULL, true);
   1061     else
   1062       return APInt(BitWidth, 0);
   1063   }
   1064 
   1065   // Create some space for the result.
   1066   uint64_t * val = new uint64_t[getNumWords()];
   1067 
   1068   // Compute some values needed by the following shift algorithms
   1069   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
   1070   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
   1071   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
   1072   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
   1073   if (bitsInWord == 0)
   1074     bitsInWord = APINT_BITS_PER_WORD;
   1075 
   1076   // If we are shifting whole words, just move whole words
   1077   if (wordShift == 0) {
   1078     // Move the words containing significant bits
   1079     for (unsigned i = 0; i <= breakWord; ++i)
   1080       val[i] = pVal[i+offset]; // move whole word
   1081 
   1082     // Adjust the top significant word for sign bit fill, if negative
   1083     if (isNegative())
   1084       if (bitsInWord < APINT_BITS_PER_WORD)
   1085         val[breakWord] |= ~0ULL << bitsInWord; // set high bits
   1086   } else {
   1087     // Shift the low order words
   1088     for (unsigned i = 0; i < breakWord; ++i) {
   1089       // This combines the shifted corresponding word with the low bits from
   1090       // the next word (shifted into this word's high bits).
   1091       val[i] = (pVal[i+offset] >> wordShift) |
   1092                (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
   1093     }
   1094 
   1095     // Shift the break word. In this case there are no bits from the next word
   1096     // to include in this word.
   1097     val[breakWord] = pVal[breakWord+offset] >> wordShift;
   1098 
   1099     // Deal with sign extenstion in the break word, and possibly the word before
   1100     // it.
   1101     if (isNegative()) {
   1102       if (wordShift > bitsInWord) {
   1103         if (breakWord > 0)
   1104           val[breakWord-1] |=
   1105             ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
   1106         val[breakWord] |= ~0ULL;
   1107       } else
   1108         val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
   1109     }
   1110   }
   1111 
   1112   // Remaining words are 0 or -1, just assign them.
   1113   uint64_t fillValue = (isNegative() ? -1ULL : 0);
   1114   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
   1115     val[i] = fillValue;
   1116   return APInt(val, BitWidth).clearUnusedBits();
   1117 }
   1118 
   1119 /// Logical right-shift this APInt by shiftAmt.
   1120 /// @brief Logical right-shift function.
   1121 APInt APInt::lshr(const APInt &shiftAmt) const {
   1122   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1123 }
   1124 
   1125 /// Logical right-shift this APInt by shiftAmt.
   1126 /// @brief Logical right-shift function.
   1127 APInt APInt::lshr(unsigned shiftAmt) const {
   1128   if (isSingleWord()) {
   1129     if (shiftAmt >= BitWidth)
   1130       return APInt(BitWidth, 0);
   1131     else
   1132       return APInt(BitWidth, this->VAL >> shiftAmt);
   1133   }
   1134 
   1135   // If all the bits were shifted out, the result is 0. This avoids issues
   1136   // with shifting by the size of the integer type, which produces undefined
   1137   // results. We define these "undefined results" to always be 0.
   1138   if (shiftAmt >= BitWidth)
   1139     return APInt(BitWidth, 0);
   1140 
   1141   // If none of the bits are shifted out, the result is *this. This avoids
   1142   // issues with shifting by the size of the integer type, which produces
   1143   // undefined results in the code below. This is also an optimization.
   1144   if (shiftAmt == 0)
   1145     return *this;
   1146 
   1147   // Create some space for the result.
   1148   uint64_t * val = new uint64_t[getNumWords()];
   1149 
   1150   // If we are shifting less than a word, compute the shift with a simple carry
   1151   if (shiftAmt < APINT_BITS_PER_WORD) {
   1152     lshrNear(val, pVal, getNumWords(), shiftAmt);
   1153     return APInt(val, BitWidth).clearUnusedBits();
   1154   }
   1155 
   1156   // Compute some values needed by the remaining shift algorithms
   1157   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
   1158   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
   1159 
   1160   // If we are shifting whole words, just move whole words
   1161   if (wordShift == 0) {
   1162     for (unsigned i = 0; i < getNumWords() - offset; ++i)
   1163       val[i] = pVal[i+offset];
   1164     for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
   1165       val[i] = 0;
   1166     return APInt(val,BitWidth).clearUnusedBits();
   1167   }
   1168 
   1169   // Shift the low order words
   1170   unsigned breakWord = getNumWords() - offset -1;
   1171   for (unsigned i = 0; i < breakWord; ++i)
   1172     val[i] = (pVal[i+offset] >> wordShift) |
   1173              (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
   1174   // Shift the break word.
   1175   val[breakWord] = pVal[breakWord+offset] >> wordShift;
   1176 
   1177   // Remaining words are 0
   1178   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
   1179     val[i] = 0;
   1180   return APInt(val, BitWidth).clearUnusedBits();
   1181 }
   1182 
   1183 /// Left-shift this APInt by shiftAmt.
   1184 /// @brief Left-shift function.
   1185 APInt APInt::shl(const APInt &shiftAmt) const {
   1186   // It's undefined behavior in C to shift by BitWidth or greater.
   1187   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1188 }
   1189 
   1190 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
   1191   // If all the bits were shifted out, the result is 0. This avoids issues
   1192   // with shifting by the size of the integer type, which produces undefined
   1193   // results. We define these "undefined results" to always be 0.
   1194   if (shiftAmt == BitWidth)
   1195     return APInt(BitWidth, 0);
   1196 
   1197   // If none of the bits are shifted out, the result is *this. This avoids a
   1198   // lshr by the words size in the loop below which can produce incorrect
   1199   // results. It also avoids the expensive computation below for a common case.
   1200   if (shiftAmt == 0)
   1201     return *this;
   1202 
   1203   // Create some space for the result.
   1204   uint64_t * val = new uint64_t[getNumWords()];
   1205 
   1206   // If we are shifting less than a word, do it the easy way
   1207   if (shiftAmt < APINT_BITS_PER_WORD) {
   1208     uint64_t carry = 0;
   1209     for (unsigned i = 0; i < getNumWords(); i++) {
   1210       val[i] = pVal[i] << shiftAmt | carry;
   1211       carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
   1212     }
   1213     return APInt(val, BitWidth).clearUnusedBits();
   1214   }
   1215 
   1216   // Compute some values needed by the remaining shift algorithms
   1217   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
   1218   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
   1219 
   1220   // If we are shifting whole words, just move whole words
   1221   if (wordShift == 0) {
   1222     for (unsigned i = 0; i < offset; i++)
   1223       val[i] = 0;
   1224     for (unsigned i = offset; i < getNumWords(); i++)
   1225       val[i] = pVal[i-offset];
   1226     return APInt(val,BitWidth).clearUnusedBits();
   1227   }
   1228 
   1229   // Copy whole words from this to Result.
   1230   unsigned i = getNumWords() - 1;
   1231   for (; i > offset; --i)
   1232     val[i] = pVal[i-offset] << wordShift |
   1233              pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
   1234   val[offset] = pVal[0] << wordShift;
   1235   for (i = 0; i < offset; ++i)
   1236     val[i] = 0;
   1237   return APInt(val, BitWidth).clearUnusedBits();
   1238 }
   1239 
   1240 APInt APInt::rotl(const APInt &rotateAmt) const {
   1241   return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
   1242 }
   1243 
   1244 APInt APInt::rotl(unsigned rotateAmt) const {
   1245   rotateAmt %= BitWidth;
   1246   if (rotateAmt == 0)
   1247     return *this;
   1248   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
   1249 }
   1250 
   1251 APInt APInt::rotr(const APInt &rotateAmt) const {
   1252   return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
   1253 }
   1254 
   1255 APInt APInt::rotr(unsigned rotateAmt) const {
   1256   rotateAmt %= BitWidth;
   1257   if (rotateAmt == 0)
   1258     return *this;
   1259   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
   1260 }
   1261 
   1262 // Square Root - this method computes and returns the square root of "this".
   1263 // Three mechanisms are used for computation. For small values (<= 5 bits),
   1264 // a table lookup is done. This gets some performance for common cases. For
   1265 // values using less than 52 bits, the value is converted to double and then
   1266 // the libc sqrt function is called. The result is rounded and then converted
   1267 // back to a uint64_t which is then used to construct the result. Finally,
   1268 // the Babylonian method for computing square roots is used.
   1269 APInt APInt::sqrt() const {
   1270 
   1271   // Determine the magnitude of the value.
   1272   unsigned magnitude = getActiveBits();
   1273 
   1274   // Use a fast table for some small values. This also gets rid of some
   1275   // rounding errors in libc sqrt for small values.
   1276   if (magnitude <= 5) {
   1277     static const uint8_t results[32] = {
   1278       /*     0 */ 0,
   1279       /*  1- 2 */ 1, 1,
   1280       /*  3- 6 */ 2, 2, 2, 2,
   1281       /*  7-12 */ 3, 3, 3, 3, 3, 3,
   1282       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
   1283       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
   1284       /*    31 */ 6
   1285     };
   1286     return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
   1287   }
   1288 
   1289   // If the magnitude of the value fits in less than 52 bits (the precision of
   1290   // an IEEE double precision floating point value), then we can use the
   1291   // libc sqrt function which will probably use a hardware sqrt computation.
   1292   // This should be faster than the algorithm below.
   1293   if (magnitude < 52) {
   1294 #if HAVE_ROUND
   1295     return APInt(BitWidth,
   1296                  uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
   1297 #else
   1298     return APInt(BitWidth,
   1299                  uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
   1300 #endif
   1301   }
   1302 
   1303   // Okay, all the short cuts are exhausted. We must compute it. The following
   1304   // is a classical Babylonian method for computing the square root. This code
   1305   // was adapted to APINt from a wikipedia article on such computations.
   1306   // See http://www.wikipedia.org/ and go to the page named
   1307   // Calculate_an_integer_square_root.
   1308   unsigned nbits = BitWidth, i = 4;
   1309   APInt testy(BitWidth, 16);
   1310   APInt x_old(BitWidth, 1);
   1311   APInt x_new(BitWidth, 0);
   1312   APInt two(BitWidth, 2);
   1313 
   1314   // Select a good starting value using binary logarithms.
   1315   for (;; i += 2, testy = testy.shl(2))
   1316     if (i >= nbits || this->ule(testy)) {
   1317       x_old = x_old.shl(i / 2);
   1318       break;
   1319     }
   1320 
   1321   // Use the Babylonian method to arrive at the integer square root:
   1322   for (;;) {
   1323     x_new = (this->udiv(x_old) + x_old).udiv(two);
   1324     if (x_old.ule(x_new))
   1325       break;
   1326     x_old = x_new;
   1327   }
   1328 
   1329   // Make sure we return the closest approximation
   1330   // NOTE: The rounding calculation below is correct. It will produce an
   1331   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
   1332   // determined to be a rounding issue with pari/gp as it begins to use a
   1333   // floating point representation after 192 bits. There are no discrepancies
   1334   // between this algorithm and pari/gp for bit widths < 192 bits.
   1335   APInt square(x_old * x_old);
   1336   APInt nextSquare((x_old + 1) * (x_old +1));
   1337   if (this->ult(square))
   1338     return x_old;
   1339   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
   1340   APInt midpoint((nextSquare - square).udiv(two));
   1341   APInt offset(*this - square);
   1342   if (offset.ult(midpoint))
   1343     return x_old;
   1344   return x_old + 1;
   1345 }
   1346 
   1347 /// Computes the multiplicative inverse of this APInt for a given modulo. The
   1348 /// iterative extended Euclidean algorithm is used to solve for this value,
   1349 /// however we simplify it to speed up calculating only the inverse, and take
   1350 /// advantage of div+rem calculations. We also use some tricks to avoid copying
   1351 /// (potentially large) APInts around.
   1352 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
   1353   assert(ult(modulo) && "This APInt must be smaller than the modulo");
   1354 
   1355   // Using the properties listed at the following web page (accessed 06/21/08):
   1356   //   http://www.numbertheory.org/php/euclid.html
   1357   // (especially the properties numbered 3, 4 and 9) it can be proved that
   1358   // BitWidth bits suffice for all the computations in the algorithm implemented
   1359   // below. More precisely, this number of bits suffice if the multiplicative
   1360   // inverse exists, but may not suffice for the general extended Euclidean
   1361   // algorithm.
   1362 
   1363   APInt r[2] = { modulo, *this };
   1364   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
   1365   APInt q(BitWidth, 0);
   1366 
   1367   unsigned i;
   1368   for (i = 0; r[i^1] != 0; i ^= 1) {
   1369     // An overview of the math without the confusing bit-flipping:
   1370     // q = r[i-2] / r[i-1]
   1371     // r[i] = r[i-2] % r[i-1]
   1372     // t[i] = t[i-2] - t[i-1] * q
   1373     udivrem(r[i], r[i^1], q, r[i]);
   1374     t[i] -= t[i^1] * q;
   1375   }
   1376 
   1377   // If this APInt and the modulo are not coprime, there is no multiplicative
   1378   // inverse, so return 0. We check this by looking at the next-to-last
   1379   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
   1380   // algorithm.
   1381   if (r[i] != 1)
   1382     return APInt(BitWidth, 0);
   1383 
   1384   // The next-to-last t is the multiplicative inverse.  However, we are
   1385   // interested in a positive inverse. Calcuate a positive one from a negative
   1386   // one if necessary. A simple addition of the modulo suffices because
   1387   // abs(t[i]) is known to be less than *this/2 (see the link above).
   1388   return t[i].isNegative() ? t[i] + modulo : t[i];
   1389 }
   1390 
   1391 /// Calculate the magic numbers required to implement a signed integer division
   1392 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
   1393 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
   1394 /// Warren, Jr., chapter 10.
   1395 APInt::ms APInt::magic() const {
   1396   const APInt& d = *this;
   1397   unsigned p;
   1398   APInt ad, anc, delta, q1, r1, q2, r2, t;
   1399   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
   1400   struct ms mag;
   1401 
   1402   ad = d.abs();
   1403   t = signedMin + (d.lshr(d.getBitWidth() - 1));
   1404   anc = t - 1 - t.urem(ad);   // absolute value of nc
   1405   p = d.getBitWidth() - 1;    // initialize p
   1406   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
   1407   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
   1408   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
   1409   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
   1410   do {
   1411     p = p + 1;
   1412     q1 = q1<<1;          // update q1 = 2p/abs(nc)
   1413     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
   1414     if (r1.uge(anc)) {  // must be unsigned comparison
   1415       q1 = q1 + 1;
   1416       r1 = r1 - anc;
   1417     }
   1418     q2 = q2<<1;          // update q2 = 2p/abs(d)
   1419     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
   1420     if (r2.uge(ad)) {   // must be unsigned comparison
   1421       q2 = q2 + 1;
   1422       r2 = r2 - ad;
   1423     }
   1424     delta = ad - r2;
   1425   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
   1426 
   1427   mag.m = q2 + 1;
   1428   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
   1429   mag.s = p - d.getBitWidth();          // resulting shift
   1430   return mag;
   1431 }
   1432 
   1433 /// Calculate the magic numbers required to implement an unsigned integer
   1434 /// division by a constant as a sequence of multiplies, adds and shifts.
   1435 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
   1436 /// S. Warren, Jr., chapter 10.
   1437 /// LeadingZeros can be used to simplify the calculation if the upper bits
   1438 /// of the divided value are known zero.
   1439 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
   1440   const APInt& d = *this;
   1441   unsigned p;
   1442   APInt nc, delta, q1, r1, q2, r2;
   1443   struct mu magu;
   1444   magu.a = 0;               // initialize "add" indicator
   1445   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
   1446   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
   1447   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
   1448 
   1449   nc = allOnes - (allOnes - d).urem(d);
   1450   p = d.getBitWidth() - 1;  // initialize p
   1451   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
   1452   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
   1453   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
   1454   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
   1455   do {
   1456     p = p + 1;
   1457     if (r1.uge(nc - r1)) {
   1458       q1 = q1 + q1 + 1;  // update q1
   1459       r1 = r1 + r1 - nc; // update r1
   1460     }
   1461     else {
   1462       q1 = q1+q1; // update q1
   1463       r1 = r1+r1; // update r1
   1464     }
   1465     if ((r2 + 1).uge(d - r2)) {
   1466       if (q2.uge(signedMax)) magu.a = 1;
   1467       q2 = q2+q2 + 1;     // update q2
   1468       r2 = r2+r2 + 1 - d; // update r2
   1469     }
   1470     else {
   1471       if (q2.uge(signedMin)) magu.a = 1;
   1472       q2 = q2+q2;     // update q2
   1473       r2 = r2+r2 + 1; // update r2
   1474     }
   1475     delta = d - 1 - r2;
   1476   } while (p < d.getBitWidth()*2 &&
   1477            (q1.ult(delta) || (q1 == delta && r1 == 0)));
   1478   magu.m = q2 + 1; // resulting magic number
   1479   magu.s = p - d.getBitWidth();  // resulting shift
   1480   return magu;
   1481 }
   1482 
   1483 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
   1484 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
   1485 /// variables here have the same names as in the algorithm. Comments explain
   1486 /// the algorithm and any deviation from it.
   1487 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
   1488                      unsigned m, unsigned n) {
   1489   assert(u && "Must provide dividend");
   1490   assert(v && "Must provide divisor");
   1491   assert(q && "Must provide quotient");
   1492   assert(u != v && u != q && v != q && "Must us different memory");
   1493   assert(n>1 && "n must be > 1");
   1494 
   1495   // Knuth uses the value b as the base of the number system. In our case b
   1496   // is 2^31 so we just set it to -1u.
   1497   uint64_t b = uint64_t(1) << 32;
   1498 
   1499 #if 0
   1500   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
   1501   DEBUG(dbgs() << "KnuthDiv: original:");
   1502   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1503   DEBUG(dbgs() << " by");
   1504   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   1505   DEBUG(dbgs() << '\n');
   1506 #endif
   1507   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
   1508   // u and v by d. Note that we have taken Knuth's advice here to use a power
   1509   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
   1510   // 2 allows us to shift instead of multiply and it is easy to determine the
   1511   // shift amount from the leading zeros.  We are basically normalizing the u
   1512   // and v so that its high bits are shifted to the top of v's range without
   1513   // overflow. Note that this can require an extra word in u so that u must
   1514   // be of length m+n+1.
   1515   unsigned shift = countLeadingZeros(v[n-1]);
   1516   unsigned v_carry = 0;
   1517   unsigned u_carry = 0;
   1518   if (shift) {
   1519     for (unsigned i = 0; i < m+n; ++i) {
   1520       unsigned u_tmp = u[i] >> (32 - shift);
   1521       u[i] = (u[i] << shift) | u_carry;
   1522       u_carry = u_tmp;
   1523     }
   1524     for (unsigned i = 0; i < n; ++i) {
   1525       unsigned v_tmp = v[i] >> (32 - shift);
   1526       v[i] = (v[i] << shift) | v_carry;
   1527       v_carry = v_tmp;
   1528     }
   1529   }
   1530   u[m+n] = u_carry;
   1531 #if 0
   1532   DEBUG(dbgs() << "KnuthDiv:   normal:");
   1533   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1534   DEBUG(dbgs() << " by");
   1535   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   1536   DEBUG(dbgs() << '\n');
   1537 #endif
   1538 
   1539   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
   1540   int j = m;
   1541   do {
   1542     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
   1543     // D3. [Calculate q'.].
   1544     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
   1545     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
   1546     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
   1547     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
   1548     // on v[n-2] determines at high speed most of the cases in which the trial
   1549     // value qp is one too large, and it eliminates all cases where qp is two
   1550     // too large.
   1551     uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
   1552     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
   1553     uint64_t qp = dividend / v[n-1];
   1554     uint64_t rp = dividend % v[n-1];
   1555     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
   1556       qp--;
   1557       rp += v[n-1];
   1558       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
   1559         qp--;
   1560     }
   1561     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
   1562 
   1563     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
   1564     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
   1565     // consists of a simple multiplication by a one-place number, combined with
   1566     // a subtraction.
   1567     bool isNeg = false;
   1568     for (unsigned i = 0; i < n; ++i) {
   1569       uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
   1570       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
   1571       bool borrow = subtrahend > u_tmp;
   1572       DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
   1573                    << ", subtrahend == " << subtrahend
   1574                    << ", borrow = " << borrow << '\n');
   1575 
   1576       uint64_t result = u_tmp - subtrahend;
   1577       unsigned k = j + i;
   1578       u[k++] = (unsigned)(result & (b-1)); // subtract low word
   1579       u[k++] = (unsigned)(result >> 32);   // subtract high word
   1580       while (borrow && k <= m+n) { // deal with borrow to the left
   1581         borrow = u[k] == 0;
   1582         u[k]--;
   1583         k++;
   1584       }
   1585       isNeg |= borrow;
   1586       DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " <<
   1587                     u[j+i+1] << '\n');
   1588     }
   1589     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
   1590     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1591     DEBUG(dbgs() << '\n');
   1592     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
   1593     // this step is actually negative, (u[j+n]...u[j]) should be left as the
   1594     // true value plus b**(n+1), namely as the b's complement of
   1595     // the true value, and a "borrow" to the left should be remembered.
   1596     //
   1597     if (isNeg) {
   1598       bool carry = true;  // true because b's complement is "complement + 1"
   1599       for (unsigned i = 0; i <= m+n; ++i) {
   1600         u[i] = ~u[i] + carry; // b's complement
   1601         carry = carry && u[i] == 0;
   1602       }
   1603     }
   1604     DEBUG(dbgs() << "KnuthDiv: after complement:");
   1605     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1606     DEBUG(dbgs() << '\n');
   1607 
   1608     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
   1609     // negative, go to step D6; otherwise go on to step D7.
   1610     q[j] = (unsigned)qp;
   1611     if (isNeg) {
   1612       // D6. [Add back]. The probability that this step is necessary is very
   1613       // small, on the order of only 2/b. Make sure that test data accounts for
   1614       // this possibility. Decrease q[j] by 1
   1615       q[j]--;
   1616       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
   1617       // A carry will occur to the left of u[j+n], and it should be ignored
   1618       // since it cancels with the borrow that occurred in D4.
   1619       bool carry = false;
   1620       for (unsigned i = 0; i < n; i++) {
   1621         unsigned limit = std::min(u[j+i],v[i]);
   1622         u[j+i] += v[i] + carry;
   1623         carry = u[j+i] < limit || (carry && u[j+i] == limit);
   1624       }
   1625       u[j+n] += carry;
   1626     }
   1627     DEBUG(dbgs() << "KnuthDiv: after correction:");
   1628     DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
   1629     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
   1630 
   1631   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
   1632   } while (--j >= 0);
   1633 
   1634   DEBUG(dbgs() << "KnuthDiv: quotient:");
   1635   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
   1636   DEBUG(dbgs() << '\n');
   1637 
   1638   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
   1639   // remainder may be obtained by dividing u[...] by d. If r is non-null we
   1640   // compute the remainder (urem uses this).
   1641   if (r) {
   1642     // The value d is expressed by the "shift" value above since we avoided
   1643     // multiplication by d by using a shift left. So, all we have to do is
   1644     // shift right here. In order to mak
   1645     if (shift) {
   1646       unsigned carry = 0;
   1647       DEBUG(dbgs() << "KnuthDiv: remainder:");
   1648       for (int i = n-1; i >= 0; i--) {
   1649         r[i] = (u[i] >> shift) | carry;
   1650         carry = u[i] << (32 - shift);
   1651         DEBUG(dbgs() << " " << r[i]);
   1652       }
   1653     } else {
   1654       for (int i = n-1; i >= 0; i--) {
   1655         r[i] = u[i];
   1656         DEBUG(dbgs() << " " << r[i]);
   1657       }
   1658     }
   1659     DEBUG(dbgs() << '\n');
   1660   }
   1661 #if 0
   1662   DEBUG(dbgs() << '\n');
   1663 #endif
   1664 }
   1665 
   1666 void APInt::divide(const APInt LHS, unsigned lhsWords,
   1667                    const APInt &RHS, unsigned rhsWords,
   1668                    APInt *Quotient, APInt *Remainder)
   1669 {
   1670   assert(lhsWords >= rhsWords && "Fractional result");
   1671 
   1672   // First, compose the values into an array of 32-bit words instead of
   1673   // 64-bit words. This is a necessity of both the "short division" algorithm
   1674   // and the Knuth "classical algorithm" which requires there to be native
   1675   // operations for +, -, and * on an m bit value with an m*2 bit result. We
   1676   // can't use 64-bit operands here because we don't have native results of
   1677   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
   1678   // work on large-endian machines.
   1679   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
   1680   unsigned n = rhsWords * 2;
   1681   unsigned m = (lhsWords * 2) - n;
   1682 
   1683   // Allocate space for the temporary values we need either on the stack, if
   1684   // it will fit, or on the heap if it won't.
   1685   unsigned SPACE[128];
   1686   unsigned *U = 0;
   1687   unsigned *V = 0;
   1688   unsigned *Q = 0;
   1689   unsigned *R = 0;
   1690   if ((Remainder?4:3)*n+2*m+1 <= 128) {
   1691     U = &SPACE[0];
   1692     V = &SPACE[m+n+1];
   1693     Q = &SPACE[(m+n+1) + n];
   1694     if (Remainder)
   1695       R = &SPACE[(m+n+1) + n + (m+n)];
   1696   } else {
   1697     U = new unsigned[m + n + 1];
   1698     V = new unsigned[n];
   1699     Q = new unsigned[m+n];
   1700     if (Remainder)
   1701       R = new unsigned[n];
   1702   }
   1703 
   1704   // Initialize the dividend
   1705   memset(U, 0, (m+n+1)*sizeof(unsigned));
   1706   for (unsigned i = 0; i < lhsWords; ++i) {
   1707     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
   1708     U[i * 2] = (unsigned)(tmp & mask);
   1709     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   1710   }
   1711   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
   1712 
   1713   // Initialize the divisor
   1714   memset(V, 0, (n)*sizeof(unsigned));
   1715   for (unsigned i = 0; i < rhsWords; ++i) {
   1716     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
   1717     V[i * 2] = (unsigned)(tmp & mask);
   1718     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   1719   }
   1720 
   1721   // initialize the quotient and remainder
   1722   memset(Q, 0, (m+n) * sizeof(unsigned));
   1723   if (Remainder)
   1724     memset(R, 0, n * sizeof(unsigned));
   1725 
   1726   // Now, adjust m and n for the Knuth division. n is the number of words in
   1727   // the divisor. m is the number of words by which the dividend exceeds the
   1728   // divisor (i.e. m+n is the length of the dividend). These sizes must not
   1729   // contain any zero words or the Knuth algorithm fails.
   1730   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
   1731     n--;
   1732     m++;
   1733   }
   1734   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
   1735     m--;
   1736 
   1737   // If we're left with only a single word for the divisor, Knuth doesn't work
   1738   // so we implement the short division algorithm here. This is much simpler
   1739   // and faster because we are certain that we can divide a 64-bit quantity
   1740   // by a 32-bit quantity at hardware speed and short division is simply a
   1741   // series of such operations. This is just like doing short division but we
   1742   // are using base 2^32 instead of base 10.
   1743   assert(n != 0 && "Divide by zero?");
   1744   if (n == 1) {
   1745     unsigned divisor = V[0];
   1746     unsigned remainder = 0;
   1747     for (int i = m+n-1; i >= 0; i--) {
   1748       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
   1749       if (partial_dividend == 0) {
   1750         Q[i] = 0;
   1751         remainder = 0;
   1752       } else if (partial_dividend < divisor) {
   1753         Q[i] = 0;
   1754         remainder = (unsigned)partial_dividend;
   1755       } else if (partial_dividend == divisor) {
   1756         Q[i] = 1;
   1757         remainder = 0;
   1758       } else {
   1759         Q[i] = (unsigned)(partial_dividend / divisor);
   1760         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
   1761       }
   1762     }
   1763     if (R)
   1764       R[0] = remainder;
   1765   } else {
   1766     // Now we're ready to invoke the Knuth classical divide algorithm. In this
   1767     // case n > 1.
   1768     KnuthDiv(U, V, Q, R, m, n);
   1769   }
   1770 
   1771   // If the caller wants the quotient
   1772   if (Quotient) {
   1773     // Set up the Quotient value's memory.
   1774     if (Quotient->BitWidth != LHS.BitWidth) {
   1775       if (Quotient->isSingleWord())
   1776         Quotient->VAL = 0;
   1777       else
   1778         delete [] Quotient->pVal;
   1779       Quotient->BitWidth = LHS.BitWidth;
   1780       if (!Quotient->isSingleWord())
   1781         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
   1782     } else
   1783       Quotient->clearAllBits();
   1784 
   1785     // The quotient is in Q. Reconstitute the quotient into Quotient's low
   1786     // order words.
   1787     if (lhsWords == 1) {
   1788       uint64_t tmp =
   1789         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
   1790       if (Quotient->isSingleWord())
   1791         Quotient->VAL = tmp;
   1792       else
   1793         Quotient->pVal[0] = tmp;
   1794     } else {
   1795       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
   1796       for (unsigned i = 0; i < lhsWords; ++i)
   1797         Quotient->pVal[i] =
   1798           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
   1799     }
   1800   }
   1801 
   1802   // If the caller wants the remainder
   1803   if (Remainder) {
   1804     // Set up the Remainder value's memory.
   1805     if (Remainder->BitWidth != RHS.BitWidth) {
   1806       if (Remainder->isSingleWord())
   1807         Remainder->VAL = 0;
   1808       else
   1809         delete [] Remainder->pVal;
   1810       Remainder->BitWidth = RHS.BitWidth;
   1811       if (!Remainder->isSingleWord())
   1812         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
   1813     } else
   1814       Remainder->clearAllBits();
   1815 
   1816     // The remainder is in R. Reconstitute the remainder into Remainder's low
   1817     // order words.
   1818     if (rhsWords == 1) {
   1819       uint64_t tmp =
   1820         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
   1821       if (Remainder->isSingleWord())
   1822         Remainder->VAL = tmp;
   1823       else
   1824         Remainder->pVal[0] = tmp;
   1825     } else {
   1826       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
   1827       for (unsigned i = 0; i < rhsWords; ++i)
   1828         Remainder->pVal[i] =
   1829           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
   1830     }
   1831   }
   1832 
   1833   // Clean up the memory we allocated.
   1834   if (U != &SPACE[0]) {
   1835     delete [] U;
   1836     delete [] V;
   1837     delete [] Q;
   1838     delete [] R;
   1839   }
   1840 }
   1841 
   1842 APInt APInt::udiv(const APInt& RHS) const {
   1843   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   1844 
   1845   // First, deal with the easy case
   1846   if (isSingleWord()) {
   1847     assert(RHS.VAL != 0 && "Divide by zero?");
   1848     return APInt(BitWidth, VAL / RHS.VAL);
   1849   }
   1850 
   1851   // Get some facts about the LHS and RHS number of bits and words
   1852   unsigned rhsBits = RHS.getActiveBits();
   1853   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1854   assert(rhsWords && "Divided by zero???");
   1855   unsigned lhsBits = this->getActiveBits();
   1856   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
   1857 
   1858   // Deal with some degenerate cases
   1859   if (!lhsWords)
   1860     // 0 / X ===> 0
   1861     return APInt(BitWidth, 0);
   1862   else if (lhsWords < rhsWords || this->ult(RHS)) {
   1863     // X / Y ===> 0, iff X < Y
   1864     return APInt(BitWidth, 0);
   1865   } else if (*this == RHS) {
   1866     // X / X ===> 1
   1867     return APInt(BitWidth, 1);
   1868   } else if (lhsWords == 1 && rhsWords == 1) {
   1869     // All high words are zero, just use native divide
   1870     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
   1871   }
   1872 
   1873   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
   1874   APInt Quotient(1,0); // to hold result.
   1875   divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
   1876   return Quotient;
   1877 }
   1878 
   1879 APInt APInt::sdiv(const APInt &RHS) const {
   1880   if (isNegative()) {
   1881     if (RHS.isNegative())
   1882       return (-(*this)).udiv(-RHS);
   1883     return -((-(*this)).udiv(RHS));
   1884   }
   1885   if (RHS.isNegative())
   1886     return -(this->udiv(-RHS));
   1887   return this->udiv(RHS);
   1888 }
   1889 
   1890 APInt APInt::urem(const APInt& RHS) const {
   1891   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   1892   if (isSingleWord()) {
   1893     assert(RHS.VAL != 0 && "Remainder by zero?");
   1894     return APInt(BitWidth, VAL % RHS.VAL);
   1895   }
   1896 
   1897   // Get some facts about the LHS
   1898   unsigned lhsBits = getActiveBits();
   1899   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
   1900 
   1901   // Get some facts about the RHS
   1902   unsigned rhsBits = RHS.getActiveBits();
   1903   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1904   assert(rhsWords && "Performing remainder operation by zero ???");
   1905 
   1906   // Check the degenerate cases
   1907   if (lhsWords == 0) {
   1908     // 0 % Y ===> 0
   1909     return APInt(BitWidth, 0);
   1910   } else if (lhsWords < rhsWords || this->ult(RHS)) {
   1911     // X % Y ===> X, iff X < Y
   1912     return *this;
   1913   } else if (*this == RHS) {
   1914     // X % X == 0;
   1915     return APInt(BitWidth, 0);
   1916   } else if (lhsWords == 1) {
   1917     // All high words are zero, just use native remainder
   1918     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
   1919   }
   1920 
   1921   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
   1922   APInt Remainder(1,0);
   1923   divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
   1924   return Remainder;
   1925 }
   1926 
   1927 APInt APInt::srem(const APInt &RHS) const {
   1928   if (isNegative()) {
   1929     if (RHS.isNegative())
   1930       return -((-(*this)).urem(-RHS));
   1931     return -((-(*this)).urem(RHS));
   1932   }
   1933   if (RHS.isNegative())
   1934     return this->urem(-RHS);
   1935   return this->urem(RHS);
   1936 }
   1937 
   1938 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
   1939                     APInt &Quotient, APInt &Remainder) {
   1940   // Get some size facts about the dividend and divisor
   1941   unsigned lhsBits  = LHS.getActiveBits();
   1942   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
   1943   unsigned rhsBits  = RHS.getActiveBits();
   1944   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1945 
   1946   // Check the degenerate cases
   1947   if (lhsWords == 0) {
   1948     Quotient = 0;                // 0 / Y ===> 0
   1949     Remainder = 0;               // 0 % Y ===> 0
   1950     return;
   1951   }
   1952 
   1953   if (lhsWords < rhsWords || LHS.ult(RHS)) {
   1954     Remainder = LHS;            // X % Y ===> X, iff X < Y
   1955     Quotient = 0;               // X / Y ===> 0, iff X < Y
   1956     return;
   1957   }
   1958 
   1959   if (LHS == RHS) {
   1960     Quotient  = 1;              // X / X ===> 1
   1961     Remainder = 0;              // X % X ===> 0;
   1962     return;
   1963   }
   1964 
   1965   if (lhsWords == 1 && rhsWords == 1) {
   1966     // There is only one word to consider so use the native versions.
   1967     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
   1968     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
   1969     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
   1970     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
   1971     return;
   1972   }
   1973 
   1974   // Okay, lets do it the long way
   1975   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
   1976 }
   1977 
   1978 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
   1979                     APInt &Quotient, APInt &Remainder) {
   1980   if (LHS.isNegative()) {
   1981     if (RHS.isNegative())
   1982       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
   1983     else {
   1984       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
   1985       Quotient = -Quotient;
   1986     }
   1987     Remainder = -Remainder;
   1988   } else if (RHS.isNegative()) {
   1989     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
   1990     Quotient = -Quotient;
   1991   } else {
   1992     APInt::udivrem(LHS, RHS, Quotient, Remainder);
   1993   }
   1994 }
   1995 
   1996 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
   1997   APInt Res = *this+RHS;
   1998   Overflow = isNonNegative() == RHS.isNonNegative() &&
   1999              Res.isNonNegative() != isNonNegative();
   2000   return Res;
   2001 }
   2002 
   2003 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
   2004   APInt Res = *this+RHS;
   2005   Overflow = Res.ult(RHS);
   2006   return Res;
   2007 }
   2008 
   2009 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
   2010   APInt Res = *this - RHS;
   2011   Overflow = isNonNegative() != RHS.isNonNegative() &&
   2012              Res.isNonNegative() != isNonNegative();
   2013   return Res;
   2014 }
   2015 
   2016 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
   2017   APInt Res = *this-RHS;
   2018   Overflow = Res.ugt(*this);
   2019   return Res;
   2020 }
   2021 
   2022 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
   2023   // MININT/-1  -->  overflow.
   2024   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
   2025   return sdiv(RHS);
   2026 }
   2027 
   2028 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
   2029   APInt Res = *this * RHS;
   2030 
   2031   if (*this != 0 && RHS != 0)
   2032     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
   2033   else
   2034     Overflow = false;
   2035   return Res;
   2036 }
   2037 
   2038 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
   2039   APInt Res = *this * RHS;
   2040 
   2041   if (*this != 0 && RHS != 0)
   2042     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
   2043   else
   2044     Overflow = false;
   2045   return Res;
   2046 }
   2047 
   2048 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
   2049   Overflow = ShAmt >= getBitWidth();
   2050   if (Overflow)
   2051     ShAmt = getBitWidth()-1;
   2052 
   2053   if (isNonNegative()) // Don't allow sign change.
   2054     Overflow = ShAmt >= countLeadingZeros();
   2055   else
   2056     Overflow = ShAmt >= countLeadingOnes();
   2057 
   2058   return *this << ShAmt;
   2059 }
   2060 
   2061 
   2062 
   2063 
   2064 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
   2065   // Check our assumptions here
   2066   assert(!str.empty() && "Invalid string length");
   2067   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
   2068           radix == 36) &&
   2069          "Radix should be 2, 8, 10, 16, or 36!");
   2070 
   2071   StringRef::iterator p = str.begin();
   2072   size_t slen = str.size();
   2073   bool isNeg = *p == '-';
   2074   if (*p == '-' || *p == '+') {
   2075     p++;
   2076     slen--;
   2077     assert(slen && "String is only a sign, needs a value.");
   2078   }
   2079   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
   2080   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
   2081   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
   2082   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
   2083          "Insufficient bit width");
   2084 
   2085   // Allocate memory
   2086   if (!isSingleWord())
   2087     pVal = getClearedMemory(getNumWords());
   2088 
   2089   // Figure out if we can shift instead of multiply
   2090   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
   2091 
   2092   // Set up an APInt for the digit to add outside the loop so we don't
   2093   // constantly construct/destruct it.
   2094   APInt apdigit(getBitWidth(), 0);
   2095   APInt apradix(getBitWidth(), radix);
   2096 
   2097   // Enter digit traversal loop
   2098   for (StringRef::iterator e = str.end(); p != e; ++p) {
   2099     unsigned digit = getDigit(*p, radix);
   2100     assert(digit < radix && "Invalid character in digit string");
   2101 
   2102     // Shift or multiply the value by the radix
   2103     if (slen > 1) {
   2104       if (shift)
   2105         *this <<= shift;
   2106       else
   2107         *this *= apradix;
   2108     }
   2109 
   2110     // Add in the digit we just interpreted
   2111     if (apdigit.isSingleWord())
   2112       apdigit.VAL = digit;
   2113     else
   2114       apdigit.pVal[0] = digit;
   2115     *this += apdigit;
   2116   }
   2117   // If its negative, put it in two's complement form
   2118   if (isNeg) {
   2119     --(*this);
   2120     this->flipAllBits();
   2121   }
   2122 }
   2123 
   2124 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
   2125                      bool Signed, bool formatAsCLiteral) const {
   2126   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
   2127           Radix == 36) &&
   2128          "Radix should be 2, 8, 10, 16, or 36!");
   2129 
   2130   const char *Prefix = "";
   2131   if (formatAsCLiteral) {
   2132     switch (Radix) {
   2133       case 2:
   2134         // Binary literals are a non-standard extension added in gcc 4.3:
   2135         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
   2136         Prefix = "0b";
   2137         break;
   2138       case 8:
   2139         Prefix = "0";
   2140         break;
   2141       case 10:
   2142         break; // No prefix
   2143       case 16:
   2144         Prefix = "0x";
   2145         break;
   2146       default:
   2147         llvm_unreachable("Invalid radix!");
   2148     }
   2149   }
   2150 
   2151   // First, check for a zero value and just short circuit the logic below.
   2152   if (*this == 0) {
   2153     while (*Prefix) {
   2154       Str.push_back(*Prefix);
   2155       ++Prefix;
   2156     };
   2157     Str.push_back('0');
   2158     return;
   2159   }
   2160 
   2161   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   2162 
   2163   if (isSingleWord()) {
   2164     char Buffer[65];
   2165     char *BufPtr = Buffer+65;
   2166 
   2167     uint64_t N;
   2168     if (!Signed) {
   2169       N = getZExtValue();
   2170     } else {
   2171       int64_t I = getSExtValue();
   2172       if (I >= 0) {
   2173         N = I;
   2174       } else {
   2175         Str.push_back('-');
   2176         N = -(uint64_t)I;
   2177       }
   2178     }
   2179 
   2180     while (*Prefix) {
   2181       Str.push_back(*Prefix);
   2182       ++Prefix;
   2183     };
   2184 
   2185     while (N) {
   2186       *--BufPtr = Digits[N % Radix];
   2187       N /= Radix;
   2188     }
   2189     Str.append(BufPtr, Buffer+65);
   2190     return;
   2191   }
   2192 
   2193   APInt Tmp(*this);
   2194 
   2195   if (Signed && isNegative()) {
   2196     // They want to print the signed version and it is a negative value
   2197     // Flip the bits and add one to turn it into the equivalent positive
   2198     // value and put a '-' in the result.
   2199     Tmp.flipAllBits();
   2200     ++Tmp;
   2201     Str.push_back('-');
   2202   }
   2203 
   2204   while (*Prefix) {
   2205     Str.push_back(*Prefix);
   2206     ++Prefix;
   2207   };
   2208 
   2209   // We insert the digits backward, then reverse them to get the right order.
   2210   unsigned StartDig = Str.size();
   2211 
   2212   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
   2213   // because the number of bits per digit (1, 3 and 4 respectively) divides
   2214   // equaly.  We just shift until the value is zero.
   2215   if (Radix == 2 || Radix == 8 || Radix == 16) {
   2216     // Just shift tmp right for each digit width until it becomes zero
   2217     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
   2218     unsigned MaskAmt = Radix - 1;
   2219 
   2220     while (Tmp != 0) {
   2221       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
   2222       Str.push_back(Digits[Digit]);
   2223       Tmp = Tmp.lshr(ShiftAmt);
   2224     }
   2225   } else {
   2226     APInt divisor(Radix == 10? 4 : 8, Radix);
   2227     while (Tmp != 0) {
   2228       APInt APdigit(1, 0);
   2229       APInt tmp2(Tmp.getBitWidth(), 0);
   2230       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
   2231              &APdigit);
   2232       unsigned Digit = (unsigned)APdigit.getZExtValue();
   2233       assert(Digit < Radix && "divide failed");
   2234       Str.push_back(Digits[Digit]);
   2235       Tmp = tmp2;
   2236     }
   2237   }
   2238 
   2239   // Reverse the digits before returning.
   2240   std::reverse(Str.begin()+StartDig, Str.end());
   2241 }
   2242 
   2243 /// toString - This returns the APInt as a std::string.  Note that this is an
   2244 /// inefficient method.  It is better to pass in a SmallVector/SmallString
   2245 /// to the methods above.
   2246 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
   2247   SmallString<40> S;
   2248   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
   2249   return S.str();
   2250 }
   2251 
   2252 
   2253 void APInt::dump() const {
   2254   SmallString<40> S, U;
   2255   this->toStringUnsigned(U);
   2256   this->toStringSigned(S);
   2257   dbgs() << "APInt(" << BitWidth << "b, "
   2258          << U.str() << "u " << S.str() << "s)";
   2259 }
   2260 
   2261 void APInt::print(raw_ostream &OS, bool isSigned) const {
   2262   SmallString<40> S;
   2263   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
   2264   OS << S.str();
   2265 }
   2266 
   2267 // This implements a variety of operations on a representation of
   2268 // arbitrary precision, two's-complement, bignum integer values.
   2269 
   2270 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
   2271 // and unrestricting assumption.
   2272 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
   2273 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
   2274 
   2275 /* Some handy functions local to this file.  */
   2276 namespace {
   2277 
   2278   /* Returns the integer part with the least significant BITS set.
   2279      BITS cannot be zero.  */
   2280   static inline integerPart
   2281   lowBitMask(unsigned int bits)
   2282   {
   2283     assert(bits != 0 && bits <= integerPartWidth);
   2284 
   2285     return ~(integerPart) 0 >> (integerPartWidth - bits);
   2286   }
   2287 
   2288   /* Returns the value of the lower half of PART.  */
   2289   static inline integerPart
   2290   lowHalf(integerPart part)
   2291   {
   2292     return part & lowBitMask(integerPartWidth / 2);
   2293   }
   2294 
   2295   /* Returns the value of the upper half of PART.  */
   2296   static inline integerPart
   2297   highHalf(integerPart part)
   2298   {
   2299     return part >> (integerPartWidth / 2);
   2300   }
   2301 
   2302   /* Returns the bit number of the most significant set bit of a part.
   2303      If the input number has no bits set -1U is returned.  */
   2304   static unsigned int
   2305   partMSB(integerPart value)
   2306   {
   2307     return findLastSet(value, ZB_Max);
   2308   }
   2309 
   2310   /* Returns the bit number of the least significant set bit of a
   2311      part.  If the input number has no bits set -1U is returned.  */
   2312   static unsigned int
   2313   partLSB(integerPart value)
   2314   {
   2315     return findFirstSet(value, ZB_Max);
   2316   }
   2317 }
   2318 
   2319 /* Sets the least significant part of a bignum to the input value, and
   2320    zeroes out higher parts.  */
   2321 void
   2322 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
   2323 {
   2324   unsigned int i;
   2325 
   2326   assert(parts > 0);
   2327 
   2328   dst[0] = part;
   2329   for (i = 1; i < parts; i++)
   2330     dst[i] = 0;
   2331 }
   2332 
   2333 /* Assign one bignum to another.  */
   2334 void
   2335 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
   2336 {
   2337   unsigned int i;
   2338 
   2339   for (i = 0; i < parts; i++)
   2340     dst[i] = src[i];
   2341 }
   2342 
   2343 /* Returns true if a bignum is zero, false otherwise.  */
   2344 bool
   2345 APInt::tcIsZero(const integerPart *src, unsigned int parts)
   2346 {
   2347   unsigned int i;
   2348 
   2349   for (i = 0; i < parts; i++)
   2350     if (src[i])
   2351       return false;
   2352 
   2353   return true;
   2354 }
   2355 
   2356 /* Extract the given bit of a bignum; returns 0 or 1.  */
   2357 int
   2358 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
   2359 {
   2360   return (parts[bit / integerPartWidth] &
   2361           ((integerPart) 1 << bit % integerPartWidth)) != 0;
   2362 }
   2363 
   2364 /* Set the given bit of a bignum. */
   2365 void
   2366 APInt::tcSetBit(integerPart *parts, unsigned int bit)
   2367 {
   2368   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
   2369 }
   2370 
   2371 /* Clears the given bit of a bignum. */
   2372 void
   2373 APInt::tcClearBit(integerPart *parts, unsigned int bit)
   2374 {
   2375   parts[bit / integerPartWidth] &=
   2376     ~((integerPart) 1 << (bit % integerPartWidth));
   2377 }
   2378 
   2379 /* Returns the bit number of the least significant set bit of a
   2380    number.  If the input number has no bits set -1U is returned.  */
   2381 unsigned int
   2382 APInt::tcLSB(const integerPart *parts, unsigned int n)
   2383 {
   2384   unsigned int i, lsb;
   2385 
   2386   for (i = 0; i < n; i++) {
   2387       if (parts[i] != 0) {
   2388           lsb = partLSB(parts[i]);
   2389 
   2390           return lsb + i * integerPartWidth;
   2391       }
   2392   }
   2393 
   2394   return -1U;
   2395 }
   2396 
   2397 /* Returns the bit number of the most significant set bit of a number.
   2398    If the input number has no bits set -1U is returned.  */
   2399 unsigned int
   2400 APInt::tcMSB(const integerPart *parts, unsigned int n)
   2401 {
   2402   unsigned int msb;
   2403 
   2404   do {
   2405     --n;
   2406 
   2407     if (parts[n] != 0) {
   2408       msb = partMSB(parts[n]);
   2409 
   2410       return msb + n * integerPartWidth;
   2411     }
   2412   } while (n);
   2413 
   2414   return -1U;
   2415 }
   2416 
   2417 /* Copy the bit vector of width srcBITS from SRC, starting at bit
   2418    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
   2419    the least significant bit of DST.  All high bits above srcBITS in
   2420    DST are zero-filled.  */
   2421 void
   2422 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
   2423                  unsigned int srcBits, unsigned int srcLSB)
   2424 {
   2425   unsigned int firstSrcPart, dstParts, shift, n;
   2426 
   2427   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
   2428   assert(dstParts <= dstCount);
   2429 
   2430   firstSrcPart = srcLSB / integerPartWidth;
   2431   tcAssign (dst, src + firstSrcPart, dstParts);
   2432 
   2433   shift = srcLSB % integerPartWidth;
   2434   tcShiftRight (dst, dstParts, shift);
   2435 
   2436   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
   2437      in DST.  If this is less that srcBits, append the rest, else
   2438      clear the high bits.  */
   2439   n = dstParts * integerPartWidth - shift;
   2440   if (n < srcBits) {
   2441     integerPart mask = lowBitMask (srcBits - n);
   2442     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
   2443                           << n % integerPartWidth);
   2444   } else if (n > srcBits) {
   2445     if (srcBits % integerPartWidth)
   2446       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
   2447   }
   2448 
   2449   /* Clear high parts.  */
   2450   while (dstParts < dstCount)
   2451     dst[dstParts++] = 0;
   2452 }
   2453 
   2454 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
   2455 integerPart
   2456 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
   2457              integerPart c, unsigned int parts)
   2458 {
   2459   unsigned int i;
   2460 
   2461   assert(c <= 1);
   2462 
   2463   for (i = 0; i < parts; i++) {
   2464     integerPart l;
   2465 
   2466     l = dst[i];
   2467     if (c) {
   2468       dst[i] += rhs[i] + 1;
   2469       c = (dst[i] <= l);
   2470     } else {
   2471       dst[i] += rhs[i];
   2472       c = (dst[i] < l);
   2473     }
   2474   }
   2475 
   2476   return c;
   2477 }
   2478 
   2479 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
   2480 integerPart
   2481 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
   2482                   integerPart c, unsigned int parts)
   2483 {
   2484   unsigned int i;
   2485 
   2486   assert(c <= 1);
   2487 
   2488   for (i = 0; i < parts; i++) {
   2489     integerPart l;
   2490 
   2491     l = dst[i];
   2492     if (c) {
   2493       dst[i] -= rhs[i] + 1;
   2494       c = (dst[i] >= l);
   2495     } else {
   2496       dst[i] -= rhs[i];
   2497       c = (dst[i] > l);
   2498     }
   2499   }
   2500 
   2501   return c;
   2502 }
   2503 
   2504 /* Negate a bignum in-place.  */
   2505 void
   2506 APInt::tcNegate(integerPart *dst, unsigned int parts)
   2507 {
   2508   tcComplement(dst, parts);
   2509   tcIncrement(dst, parts);
   2510 }
   2511 
   2512 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
   2513     DST  = SRC * MULTIPLIER + CARRY   if add is false
   2514 
   2515     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
   2516     they must start at the same point, i.e. DST == SRC.
   2517 
   2518     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
   2519     returned.  Otherwise DST is filled with the least significant
   2520     DSTPARTS parts of the result, and if all of the omitted higher
   2521     parts were zero return zero, otherwise overflow occurred and
   2522     return one.  */
   2523 int
   2524 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
   2525                       integerPart multiplier, integerPart carry,
   2526                       unsigned int srcParts, unsigned int dstParts,
   2527                       bool add)
   2528 {
   2529   unsigned int i, n;
   2530 
   2531   /* Otherwise our writes of DST kill our later reads of SRC.  */
   2532   assert(dst <= src || dst >= src + srcParts);
   2533   assert(dstParts <= srcParts + 1);
   2534 
   2535   /* N loops; minimum of dstParts and srcParts.  */
   2536   n = dstParts < srcParts ? dstParts: srcParts;
   2537 
   2538   for (i = 0; i < n; i++) {
   2539     integerPart low, mid, high, srcPart;
   2540 
   2541       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
   2542 
   2543          This cannot overflow, because
   2544 
   2545          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
   2546 
   2547          which is less than n^2.  */
   2548 
   2549     srcPart = src[i];
   2550 
   2551     if (multiplier == 0 || srcPart == 0)        {
   2552       low = carry;
   2553       high = 0;
   2554     } else {
   2555       low = lowHalf(srcPart) * lowHalf(multiplier);
   2556       high = highHalf(srcPart) * highHalf(multiplier);
   2557 
   2558       mid = lowHalf(srcPart) * highHalf(multiplier);
   2559       high += highHalf(mid);
   2560       mid <<= integerPartWidth / 2;
   2561       if (low + mid < low)
   2562         high++;
   2563       low += mid;
   2564 
   2565       mid = highHalf(srcPart) * lowHalf(multiplier);
   2566       high += highHalf(mid);
   2567       mid <<= integerPartWidth / 2;
   2568       if (low + mid < low)
   2569         high++;
   2570       low += mid;
   2571 
   2572       /* Now add carry.  */
   2573       if (low + carry < low)
   2574         high++;
   2575       low += carry;
   2576     }
   2577 
   2578     if (add) {
   2579       /* And now DST[i], and store the new low part there.  */
   2580       if (low + dst[i] < low)
   2581         high++;
   2582       dst[i] += low;
   2583     } else
   2584       dst[i] = low;
   2585 
   2586     carry = high;
   2587   }
   2588 
   2589   if (i < dstParts) {
   2590     /* Full multiplication, there is no overflow.  */
   2591     assert(i + 1 == dstParts);
   2592     dst[i] = carry;
   2593     return 0;
   2594   } else {
   2595     /* We overflowed if there is carry.  */
   2596     if (carry)
   2597       return 1;
   2598 
   2599     /* We would overflow if any significant unwritten parts would be
   2600        non-zero.  This is true if any remaining src parts are non-zero
   2601        and the multiplier is non-zero.  */
   2602     if (multiplier)
   2603       for (; i < srcParts; i++)
   2604         if (src[i])
   2605           return 1;
   2606 
   2607     /* We fitted in the narrow destination.  */
   2608     return 0;
   2609   }
   2610 }
   2611 
   2612 /* DST = LHS * RHS, where DST has the same width as the operands and
   2613    is filled with the least significant parts of the result.  Returns
   2614    one if overflow occurred, otherwise zero.  DST must be disjoint
   2615    from both operands.  */
   2616 int
   2617 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
   2618                   const integerPart *rhs, unsigned int parts)
   2619 {
   2620   unsigned int i;
   2621   int overflow;
   2622 
   2623   assert(dst != lhs && dst != rhs);
   2624 
   2625   overflow = 0;
   2626   tcSet(dst, 0, parts);
   2627 
   2628   for (i = 0; i < parts; i++)
   2629     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
   2630                                parts - i, true);
   2631 
   2632   return overflow;
   2633 }
   2634 
   2635 /* DST = LHS * RHS, where DST has width the sum of the widths of the
   2636    operands.  No overflow occurs.  DST must be disjoint from both
   2637    operands.  Returns the number of parts required to hold the
   2638    result.  */
   2639 unsigned int
   2640 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
   2641                       const integerPart *rhs, unsigned int lhsParts,
   2642                       unsigned int rhsParts)
   2643 {
   2644   /* Put the narrower number on the LHS for less loops below.  */
   2645   if (lhsParts > rhsParts) {
   2646     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
   2647   } else {
   2648     unsigned int n;
   2649 
   2650     assert(dst != lhs && dst != rhs);
   2651 
   2652     tcSet(dst, 0, rhsParts);
   2653 
   2654     for (n = 0; n < lhsParts; n++)
   2655       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
   2656 
   2657     n = lhsParts + rhsParts;
   2658 
   2659     return n - (dst[n - 1] == 0);
   2660   }
   2661 }
   2662 
   2663 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
   2664    Otherwise set LHS to LHS / RHS with the fractional part discarded,
   2665    set REMAINDER to the remainder, return zero.  i.e.
   2666 
   2667    OLD_LHS = RHS * LHS + REMAINDER
   2668 
   2669    SCRATCH is a bignum of the same size as the operands and result for
   2670    use by the routine; its contents need not be initialized and are
   2671    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
   2672 */
   2673 int
   2674 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
   2675                 integerPart *remainder, integerPart *srhs,
   2676                 unsigned int parts)
   2677 {
   2678   unsigned int n, shiftCount;
   2679   integerPart mask;
   2680 
   2681   assert(lhs != remainder && lhs != srhs && remainder != srhs);
   2682 
   2683   shiftCount = tcMSB(rhs, parts) + 1;
   2684   if (shiftCount == 0)
   2685     return true;
   2686 
   2687   shiftCount = parts * integerPartWidth - shiftCount;
   2688   n = shiftCount / integerPartWidth;
   2689   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
   2690 
   2691   tcAssign(srhs, rhs, parts);
   2692   tcShiftLeft(srhs, parts, shiftCount);
   2693   tcAssign(remainder, lhs, parts);
   2694   tcSet(lhs, 0, parts);
   2695 
   2696   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
   2697      the total.  */
   2698   for (;;) {
   2699       int compare;
   2700 
   2701       compare = tcCompare(remainder, srhs, parts);
   2702       if (compare >= 0) {
   2703         tcSubtract(remainder, srhs, 0, parts);
   2704         lhs[n] |= mask;
   2705       }
   2706 
   2707       if (shiftCount == 0)
   2708         break;
   2709       shiftCount--;
   2710       tcShiftRight(srhs, parts, 1);
   2711       if ((mask >>= 1) == 0)
   2712         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
   2713   }
   2714 
   2715   return false;
   2716 }
   2717 
   2718 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
   2719    There are no restrictions on COUNT.  */
   2720 void
   2721 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
   2722 {
   2723   if (count) {
   2724     unsigned int jump, shift;
   2725 
   2726     /* Jump is the inter-part jump; shift is is intra-part shift.  */
   2727     jump = count / integerPartWidth;
   2728     shift = count % integerPartWidth;
   2729 
   2730     while (parts > jump) {
   2731       integerPart part;
   2732 
   2733       parts--;
   2734 
   2735       /* dst[i] comes from the two parts src[i - jump] and, if we have
   2736          an intra-part shift, src[i - jump - 1].  */
   2737       part = dst[parts - jump];
   2738       if (shift) {
   2739         part <<= shift;
   2740         if (parts >= jump + 1)
   2741           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
   2742       }
   2743 
   2744       dst[parts] = part;
   2745     }
   2746 
   2747     while (parts > 0)
   2748       dst[--parts] = 0;
   2749   }
   2750 }
   2751 
   2752 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
   2753    zero.  There are no restrictions on COUNT.  */
   2754 void
   2755 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
   2756 {
   2757   if (count) {
   2758     unsigned int i, jump, shift;
   2759 
   2760     /* Jump is the inter-part jump; shift is is intra-part shift.  */
   2761     jump = count / integerPartWidth;
   2762     shift = count % integerPartWidth;
   2763 
   2764     /* Perform the shift.  This leaves the most significant COUNT bits
   2765        of the result at zero.  */
   2766     for (i = 0; i < parts; i++) {
   2767       integerPart part;
   2768 
   2769       if (i + jump >= parts) {
   2770         part = 0;
   2771       } else {
   2772         part = dst[i + jump];
   2773         if (shift) {
   2774           part >>= shift;
   2775           if (i + jump + 1 < parts)
   2776             part |= dst[i + jump + 1] << (integerPartWidth - shift);
   2777         }
   2778       }
   2779 
   2780       dst[i] = part;
   2781     }
   2782   }
   2783 }
   2784 
   2785 /* Bitwise and of two bignums.  */
   2786 void
   2787 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2788 {
   2789   unsigned int i;
   2790 
   2791   for (i = 0; i < parts; i++)
   2792     dst[i] &= rhs[i];
   2793 }
   2794 
   2795 /* Bitwise inclusive or of two bignums.  */
   2796 void
   2797 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2798 {
   2799   unsigned int i;
   2800 
   2801   for (i = 0; i < parts; i++)
   2802     dst[i] |= rhs[i];
   2803 }
   2804 
   2805 /* Bitwise exclusive or of two bignums.  */
   2806 void
   2807 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2808 {
   2809   unsigned int i;
   2810 
   2811   for (i = 0; i < parts; i++)
   2812     dst[i] ^= rhs[i];
   2813 }
   2814 
   2815 /* Complement a bignum in-place.  */
   2816 void
   2817 APInt::tcComplement(integerPart *dst, unsigned int parts)
   2818 {
   2819   unsigned int i;
   2820 
   2821   for (i = 0; i < parts; i++)
   2822     dst[i] = ~dst[i];
   2823 }
   2824 
   2825 /* Comparison (unsigned) of two bignums.  */
   2826 int
   2827 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
   2828                  unsigned int parts)
   2829 {
   2830   while (parts) {
   2831       parts--;
   2832       if (lhs[parts] == rhs[parts])
   2833         continue;
   2834 
   2835       if (lhs[parts] > rhs[parts])
   2836         return 1;
   2837       else
   2838         return -1;
   2839     }
   2840 
   2841   return 0;
   2842 }
   2843 
   2844 /* Increment a bignum in-place, return the carry flag.  */
   2845 integerPart
   2846 APInt::tcIncrement(integerPart *dst, unsigned int parts)
   2847 {
   2848   unsigned int i;
   2849 
   2850   for (i = 0; i < parts; i++)
   2851     if (++dst[i] != 0)
   2852       break;
   2853 
   2854   return i == parts;
   2855 }
   2856 
   2857 /* Decrement a bignum in-place, return the borrow flag.  */
   2858 integerPart
   2859 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
   2860   for (unsigned int i = 0; i < parts; i++) {
   2861     // If the current word is non-zero, then the decrement has no effect on the
   2862     // higher-order words of the integer and no borrow can occur. Exit early.
   2863     if (dst[i]--)
   2864       return 0;
   2865   }
   2866   // If every word was zero, then there is a borrow.
   2867   return 1;
   2868 }
   2869 
   2870 
   2871 /* Set the least significant BITS bits of a bignum, clear the
   2872    rest.  */
   2873 void
   2874 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
   2875                                  unsigned int bits)
   2876 {
   2877   unsigned int i;
   2878 
   2879   i = 0;
   2880   while (bits > integerPartWidth) {
   2881     dst[i++] = ~(integerPart) 0;
   2882     bits -= integerPartWidth;
   2883   }
   2884 
   2885   if (bits)
   2886     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
   2887 
   2888   while (i < parts)
   2889     dst[i++] = 0;
   2890 }
   2891