lib/Support/APInt.cpp

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