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