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