lib/Support/APInt.cpp

   1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Sheng Zhou and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a class to represent arbitrary precision integral
  11 // constant values.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/ADT/APInt.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/Support/MathExtras.h"
  18 #include <strings.h>
  19 #include <iostream>
  20 #include <sstream>
  21 #include <iomanip>
  22 #include <cstdlib>
  23 using namespace llvm;
  24
  25 APInt::APInt(uint64_t val, unsigned numBits, bool sign)
  26   : bitsnum(numBits), isSigned(sign) {
  27   assert(bitsnum >= IntegerType::MIN_INT_BITS && "bitwidth too small");
  28   assert(bitsnum <= IntegerType::MAX_INT_BITS && "bitwidth too large");
  29   if (isSingleWord())
  30     VAL = val & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - bitsnum));
  31   else {
  32     // Memory allocation and check if successful.
  33     assert((pVal = new uint64_t[numWords()]) &&
  34             "APInt memory allocation fails!");
  35     bzero(pVal, numWords() * 8);
  36     pVal[0] = val;
  37   }
  38 }
  39
  40 APInt::APInt(unsigned numBits, uint64_t bigVal[], bool sign)
  41   : bitsnum(numBits), isSigned(sign) {
  42   assert(bitsnum >= IntegerType::MIN_INT_BITS && "bitwidth too small");
  43   assert(bitsnum <= IntegerType::MAX_INT_BITS && "bitwidth too large");
  44   assert(bigVal && "Null pointer detected!");
  45   if (isSingleWord())
  46     VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - bitsnum));
  47   else {
  48     // Memory allocation and check if successful.
  49     assert((pVal = new uint64_t[numWords()]) &&
  50            "APInt memory allocation fails!");
  51     // Calculate the actual length of bigVal[].
  52     unsigned n = sizeof(*bigVal) / sizeof(bigVal[0]);
  53     unsigned maxN = std::max<unsigned>(n, numWords());
  54     unsigned minN = std::min<unsigned>(n, numWords());
  55     memcpy(pVal, bigVal, (minN - 1) * 8);
  56     pVal[minN-1] = bigVal[minN-1] & (~uint64_t(0ULL) >> (64 - bitsnum % 64));
  57     if (maxN == numWords())
  58       bzero(pVal+n, (numWords() - n) * 8);
  59   }
  60 }
  61
  62 APInt::APInt(std::string& Val, uint8_t radix, bool sign)
  63   : isSigned(sign) {
  64   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
  65          "Radix should be 2, 8, 10, or 16!");
  66   assert(!Val.empty() && "String empty?");
  67   unsigned slen = Val.size();
  68   unsigned size = 0;
  69   // If the radix is a power of 2, read the input
  70   // from most significant to least significant.
  71   if ((radix & (radix - 1)) == 0) {
  72     unsigned nextBitPos = 0, bits_per_digit = radix / 8 + 2;
  73     uint64_t resDigit = 0;
  74     bitsnum = slen * bits_per_digit;
  75     if (numWords() > 1)
  76       assert((pVal = new uint64_t[numWords()]) &&
  77              "APInt memory allocation fails!");
  78     for (int i = slen - 1; i >= 0; --i) {
  79       uint64_t digit = Val[i] - 48;             // '0' == 48.
  80       resDigit |= digit << nextBitPos;
  81       nextBitPos += bits_per_digit;
  82       if (nextBitPos >= 64) {
  83         if (isSingleWord()) {
  84           VAL = resDigit;
  85            break;
  86         }
  87         pVal[size++] = resDigit;
  88         nextBitPos -= 64;
  89         resDigit = digit >> (bits_per_digit - nextBitPos);
  90       }
  91     }
  92     if (!isSingleWord() && size <= numWords())
  93       pVal[size] = resDigit;
  94   } else {   // General case.  The radix is not a power of 2.
  95     // For 10-radix, the max value of 64-bit integer is 18446744073709551615,
  96     // and its digits number is 14.
  97     const unsigned chars_per_word = 20;
  98     if (slen < chars_per_word ||
  99         (Val <= "18446744073709551615" &&
 100          slen == chars_per_word)) { // In case Val <= 2^64 - 1
 101       bitsnum = 64;
 102       VAL = strtoull(Val.c_str(), 0, 10);
 103     } else { // In case Val > 2^64 - 1
 104       bitsnum = (slen / chars_per_word + 1) * 64;
 105       assert((pVal = new uint64_t[numWords()]) &&
 106              "APInt memory allocation fails!");
 107       bzero(pVal, numWords() * 8);
 108       unsigned str_pos = 0;
 109       while (str_pos < slen) {
 110         unsigned chunk = slen - str_pos;
 111         if (chunk > chars_per_word - 1)
 112           chunk = chars_per_word - 1;
 113         uint64_t resDigit = Val[str_pos++] - 48;  // 48 == '0'.
 114         uint64_t big_base = radix;
 115         while (--chunk > 0) {
 116           resDigit = resDigit * radix + Val[str_pos++] - 48;
 117           big_base *= radix;
 118         }
 119
 120         uint64_t carry;
 121         if (!size)
 122           carry = resDigit;
 123         else {
 124           carry = mul_1(pVal, pVal, size, big_base);
 125           carry += add_1(pVal, pVal, size, resDigit);
 126         }
 127
 128         if (carry) pVal[size++] = carry;
 129       }
 130     }
 131   }
 132 }
 133
 134 APInt::APInt(const APInt& APIVal)
 135   : bitsnum(APIVal.bitsnum), isSigned(APIVal.isSigned) {
 136   if (isSingleWord()) VAL = APIVal.VAL;
 137   else {
 138     // Memory allocation and check if successful.
 139     assert((pVal = new uint64_t[numWords()]) &&
 140            "APInt memory allocation fails!");
 141     memcpy(pVal, APIVal.pVal, numWords() * 8);
 142   }
 143 }
 144
 145 APInt::~APInt() {
 146   if (!isSingleWord() && pVal) delete[] pVal;
 147 }
 148
 149 /// whichByte - This function returns the word position
 150 /// for the specified bit position.
 151 inline unsigned APInt::whichByte(unsigned bitPosition)
 152 { return (bitPosition % APINT_BITS_PER_WORD) / 8; }
 153
 154 /// getWord - returns the corresponding word for the specified bit position.
 155 inline uint64_t& APInt::getWord(unsigned bitPosition)
 156 { return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; }
 157
 158 /// getWord - returns the corresponding word for the specified bit position.
 159 /// This is a constant version.
 160 inline uint64_t APInt::getWord(unsigned bitPosition) const
 161 { return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; }
 162
 163 /// mul_1 - This function multiplies the integer array x[] by a integer y and
 164 /// returns the carry.
 165 uint64_t APInt::mul_1(uint64_t dest[], uint64_t x[],
 166                      unsigned len, uint64_t y) {
 167   // Split y into high 32-bit part and low 32-bit part.
 168   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
 169   uint64_t carry = 0, lx, hx;
 170   for (unsigned i = 0; i < len; ++i) {
 171     lx = x[i] & 0xffffffffULL;
 172     hx = x[i] >> 32;
 173     // hasCarry - A flag to indicate if has carry.
 174     // hasCarry == 0, no carry
 175     // hasCarry == 1, has carry
 176     // hasCarry == 2, no carry and the calculation result == 0.
 177     uint8_t hasCarry = 0;
 178     dest[i] = carry + lx * ly;
 179     // Determine if the add above introduces carry.
 180     hasCarry = (dest[i] < carry) ? 1 : 0;
 181     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
 182     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
 183     // (2^32 - 1) + 2^32 = 2^64.
 184     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
 185
 186     carry += (lx * hy) & 0xffffffffULL;
 187     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
 188     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
 189             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
 190   }
 191
 192   return carry;
 193 }
 194
 195 /// mul - This function multiplies integer array x[] by integer array y[] and
 196 /// stores the result into integer array dest[].
 197 /// Note the array dest[]'s size should no less than xlen + ylen.
 198 void APInt::mul(uint64_t dest[], uint64_t x[], unsigned xlen,
 199                uint64_t y[], unsigned ylen) {
 200   dest[xlen] = mul_1(dest, x, xlen, y[0]);
 201
 202   for (unsigned i = 1; i < ylen; ++i) {
 203     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
 204     uint64_t carry = 0, lx, hx;
 205     for (unsigned j = 0; j < xlen; ++j) {
 206       lx = x[j] & 0xffffffffULL;
 207       hx = x[j] >> 32;
 208       // hasCarry - A flag to indicate if has carry.
 209       // hasCarry == 0, no carry
 210       // hasCarry == 1, has carry
 211       // hasCarry == 2, no carry and the calculation result == 0.
 212       uint8_t hasCarry = 0;
 213       uint64_t resul = carry + lx * ly;
 214       hasCarry = (resul < carry) ? 1 : 0;
 215       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
 216       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
 217
 218       carry += (lx * hy) & 0xffffffffULL;
 219       resul = (carry << 32) | (resul & 0xffffffffULL);
 220       dest[i+j] += resul;
 221       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
 222               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
 223               ((lx * hy) >> 32) + hx * hy;
 224     }
 225     dest[i+xlen] = carry;
 226   }
 227 }
 228
 229 /// add_1 - This function adds the integer array x[] by integer y and
 230 /// returns the carry.
 231 uint64_t APInt::add_1(uint64_t dest[], uint64_t x[],
 232                       unsigned len, uint64_t y) {
 233   uint64_t carry = y;
 234
 235   for (unsigned i = 0; i < len; ++i) {
 236     dest[i] = carry + x[i];
 237     carry = (dest[i] < carry) ? 1 : 0;
 238   }
 239   return carry;
 240 }
 241
 242 /// add - This function adds the integer array x[] by integer array
 243 /// y[] and returns the carry.
 244 uint64_t APInt::add(uint64_t dest[], uint64_t x[],
 245                     uint64_t y[], unsigned len) {
 246   unsigned carry = 0;
 247
 248   for (unsigned i = 0; i< len; ++i) {
 249     carry += x[i];
 250     dest[i] = carry + y[i];
 251     carry = carry < x[i] ? 1 : (dest[i] < carry ? 1 : 0);
 252   }
 253   return carry;
 254 }
 255
 256 /// sub_1 - This function subtracts the integer array x[] by
 257 /// integer y and returns the borrow-out carry.
 258 uint64_t APInt::sub_1(uint64_t x[], unsigned len, uint64_t y) {
 259   uint64_t cy = y;
 260
 261   for (unsigned i = 0; i < len; ++i) {
 262     uint64_t X = x[i];
 263     x[i] -= cy;
 264     if (cy > X)
 265       cy = 1;
 266     else {
 267       cy = 0;
 268       break;
 269     }
 270   }
 271
 272   return cy;
 273 }
 274
 275 /// sub - This function subtracts the integer array x[] by
 276 /// integer array y[], and returns the borrow-out carry.
 277 uint64_t APInt::sub(uint64_t dest[], uint64_t x[],
 278                     uint64_t y[], unsigned len) {
 279   // Carry indicator.
 280   uint64_t cy = 0;
 281
 282   for (unsigned i = 0; i < len; ++i) {
 283     uint64_t Y = y[i], X = x[i];
 284     Y += cy;
 285
 286     cy = Y < cy ? 1 : 0;
 287     Y = X - Y;
 288     cy += Y > X ? 1 : 0;
 289     dest[i] = Y;
 290   }
 291   return cy;
 292 }
 293
 294 /// UnitDiv - This function divides N by D,
 295 /// and returns (remainder << 32) | quotient.
 296 /// Assumes (N >> 32) < D.
 297 uint64_t APInt::unitDiv(uint64_t N, unsigned D) {
 298   uint64_t q, r;                   // q: quotient, r: remainder.
 299   uint64_t a1 = N >> 32;           // a1: high 32-bit part of N.
 300   uint64_t a0 = N & 0xffffffffL;   // a0: low 32-bit part of N
 301   if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL)) {
 302       q = N / D;
 303       r = N % D;
 304   }
 305   else {
 306     // Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d
 307     uint64_t c = N - ((uint64_t) D << 31);
 308     // Divide (c1*2^32 + c0) by d
 309     q = c / D;
 310     r = c % D;
 311     // Add 2^31 to quotient
 312     q += 1 << 31;
 313   }
 314
 315   return (r << 32) | (q & 0xFFFFFFFFl);
 316 }
 317
 318 /// subMul - This function substracts x[len-1:0] * y from
 319 /// dest[offset+len-1:offset], and returns the most significant
 320 /// word of the product, minus the borrow-out from the subtraction.
 321 unsigned APInt::subMul(unsigned dest[], unsigned offset,
 322                         unsigned x[], unsigned len, unsigned y) {
 323   uint64_t yl = (uint64_t) y & 0xffffffffL;
 324   unsigned carry = 0;
 325   unsigned j = 0;
 326   do {
 327     uint64_t prod = ((uint64_t) x[j] & 0xffffffffL) * yl;
 328     unsigned prod_low = (unsigned) prod;
 329     unsigned prod_high = (unsigned) (prod >> 32);
 330     prod_low += carry;
 331     carry = (prod_low < carry ? 1 : 0) + prod_high;
 332     unsigned x_j = dest[offset+j];
 333     prod_low = x_j - prod_low;
 334     if (prod_low > x_j) ++carry;
 335     dest[offset+j] = prod_low;
 336   } while (++j < len);
 337   return carry;
 338 }
 339
 340 /// div - This is basically Knuth's formulation of the classical algorithm.
 341 /// Correspondance with Knuth's notation:
 342 /// Knuth's u[0:m+n] == zds[nx:0].
 343 /// Knuth's v[1:n] == y[ny-1:0]
 344 /// Knuth's n == ny.
 345 /// Knuth's m == nx-ny.
 346 /// Our nx == Knuth's m+n.
 347 /// Could be re-implemented using gmp's mpn_divrem:
 348 /// zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny).
 349 void APInt::div(unsigned zds[], unsigned nx, unsigned y[], unsigned ny) {
 350   unsigned j = nx;
 351   do {                          // loop over digits of quotient
 352     // Knuth's j == our nx-j.
 353     // Knuth's u[j:j+n] == our zds[j:j-ny].
 354     unsigned qhat;  // treated as unsigned
 355     if (zds[j] == y[ny-1]) qhat = -1U;  // 0xffffffff
 356     else {
 357       uint64_t w = (((uint64_t)(zds[j])) << 32) +
 358                    ((uint64_t)zds[j-1] & 0xffffffffL);
 359       qhat = (unsigned) unitDiv(w, y[ny-1]);
 360     }
 361     if (qhat) {
 362       unsigned borrow = subMul(zds, j - ny, y, ny, qhat);
 363       unsigned save = zds[j];
 364       uint64_t num = ((uint64_t)save&0xffffffffL) -
 365                      ((uint64_t)borrow&0xffffffffL);
 366       while (num) {
 367         qhat--;
 368         uint64_t carry = 0;
 369         for (unsigned i = 0;  i < ny; i++) {
 370           carry += ((uint64_t) zds[j-ny+i] & 0xffffffffL)
 371             + ((uint64_t) y[i] & 0xffffffffL);
 372           zds[j-ny+i] = (unsigned) carry;
 373           carry >>= 32;
 374         }
 375         zds[j] += carry;
 376         num = carry - 1;
 377       }
 378     }
 379     zds[j] = qhat;
 380   } while (--j >= ny);
 381 }
 382
 383 /// lshift - This function shift x[0:len-1] left by shiftAmt bits, and
 384 /// store the len least significant words of the result in
 385 /// dest[d_offset:d_offset+len-1]. It returns the bits shifted out from
 386 /// the most significant digit.
 387 uint64_t APInt::lshift(uint64_t dest[], unsigned d_offset,
 388                        uint64_t x[], unsigned len, unsigned shiftAmt) {
 389   unsigned count = 64 - shiftAmt;
 390   int i = len - 1;
 391   uint64_t high_word = x[i], retVal = high_word >> count;
 392   ++d_offset;
 393   while (--i >= 0) {
 394     uint64_t low_word = x[i];
 395     dest[d_offset+i] = (high_word << shiftAmt) | (low_word >> count);
 396     high_word = low_word;
 397   }
 398   dest[d_offset+i] = high_word << shiftAmt;
 399   return retVal;
 400 }
 401
 402 /// @brief Copy assignment operator. Create a new object from the given
 403 /// APInt one by initialization.
 404 APInt& APInt::operator=(const APInt& RHS) {
 405   if (isSingleWord()) VAL = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 406   else {
 407     unsigned minN = std::min(numWords(), RHS.numWords());
 408     memcpy(pVal, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, minN * 8);
 409     if (numWords() != minN)
 410       bzero(pVal + minN, (numWords() - minN) * 8);
 411   }
 412   return *this;
 413 }
 414
 415 /// @brief Assignment operator. Assigns a common case integer value to
 416 /// the APInt.
 417 APInt& APInt::operator=(uint64_t RHS) {
 418   if (isSingleWord()) VAL = RHS;
 419   else {
 420     pVal[0] = RHS;
 421     bzero(pVal, (numWords() - 1) * 8);
 422   }
 423   return *this;
 424 }
 425
 426 /// @brief Postfix increment operator. Increments the APInt by one.
 427 const APInt APInt::operator++(int) {
 428   APInt API(*this);
 429   if (isSingleWord()) ++VAL;
 430   else
 431     add_1(pVal, pVal, numWords(), 1);
 432   API.TruncToBits();
 433   return API;
 434 }
 435
 436 /// @brief Prefix increment operator. Increments the APInt by one.
 437 APInt& APInt::operator++() {
 438   if (isSingleWord()) ++VAL;
 439   else
 440     add_1(pVal, pVal, numWords(), 1);
 441   TruncToBits();
 442   return *this;
 443 }
 444
 445 /// @brief Postfix decrement operator. Decrements the APInt by one.
 446 const APInt APInt::operator--(int) {
 447   APInt API(*this);
 448   if (isSingleWord()) --VAL;
 449   else
 450     sub_1(API.pVal, API.numWords(), 1);
 451   API.TruncToBits();
 452   return API;
 453 }
 454
 455 /// @brief Prefix decrement operator. Decrements the APInt by one.
 456 APInt& APInt::operator--() {
 457   if (isSingleWord()) --VAL;
 458   else
 459     sub_1(pVal, numWords(), 1);
 460   TruncToBits();
 461   return *this;
 462 }
 463
 464 /// @brief Addition assignment operator. Adds this APInt by the given APInt&
 465 /// RHS and assigns the result to this APInt.
 466 APInt& APInt::operator+=(const APInt& RHS) {
 467   if (isSingleWord()) VAL += RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 468   else {
 469     if (RHS.isSingleWord()) add_1(pVal, pVal, numWords(), RHS.VAL);
 470     else {
 471       if (numWords() <= RHS.numWords())
 472         add(pVal, pVal, RHS.pVal, numWords());
 473       else {
 474         uint64_t carry = add(pVal, pVal, RHS.pVal, RHS.numWords());
 475         add_1(pVal + RHS.numWords(), pVal + RHS.numWords(),
 476               numWords() - RHS.numWords(), carry);
 477       }
 478     }
 479   }
 480   TruncToBits();
 481   return *this;
 482 }
 483
 484 /// @brief Subtraction assignment operator. Subtracts this APInt by the given
 485 /// APInt &RHS and assigns the result to this APInt.
 486 APInt& APInt::operator-=(const APInt& RHS) {
 487   if (isSingleWord())
 488     VAL -= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 489   else {
 490     if (RHS.isSingleWord())
 491       sub_1(pVal, numWords(), RHS.VAL);
 492     else {
 493       if (RHS.numWords() < numWords()) {
 494         uint64_t carry = sub(pVal, pVal, RHS.pVal, RHS.numWords());
 495         sub_1(pVal + RHS.numWords(), numWords() - RHS.numWords(), carry);
 496       }
 497       else
 498         sub(pVal, pVal, RHS.pVal, numWords());
 499     }
 500   }
 501   TruncToBits();
 502   return *this;
 503 }
 504
 505 /// @brief Multiplication assignment operator. Multiplies this APInt by the
 506 /// given APInt& RHS and assigns the result to this APInt.
 507 APInt& APInt::operator*=(const APInt& RHS) {
 508   if (isSingleWord()) VAL *= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 509   else {
 510     // one-based first non-zero bit position.
 511     unsigned first = numWords() * APINT_BITS_PER_WORD - CountLeadingZeros();
 512     unsigned xlen = !first ? 0 : whichWord(first - 1) + 1;
 513     if (!xlen)
 514       return *this;
 515     else if (RHS.isSingleWord())
 516       mul_1(pVal, pVal, xlen, RHS.VAL);
 517     else {
 518       first = RHS.numWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros();
 519       unsigned ylen = !first ? 0 : whichWord(first - 1) + 1;
 520       if (!ylen) {
 521         bzero(pVal, numWords() * 8);
 522         return *this;
 523       }
 524       uint64_t *dest = new uint64_t[xlen+ylen];
 525       assert(dest && "Memory Allocation Failed!");
 526       mul(dest, pVal, xlen, RHS.pVal, ylen);
 527       memcpy(pVal, dest, ((xlen + ylen >= numWords()) ? numWords() : xlen + ylen) * 8);
 528       delete[] dest;
 529     }
 530   }
 531   TruncToBits();
 532   return *this;
 533 }
 534
 535 /// @brief Division assignment operator. Divides this APInt by the given APInt
 536 /// &RHS and assigns the result to this APInt.
 537 APInt& APInt::operator/=(const APInt& RHS) {
 538   unsigned first = RHS.numWords() * APINT_BITS_PER_WORD -
 539                    RHS.CountLeadingZeros();
 540   unsigned ylen = !first ? 0 : whichWord(first - 1) + 1;
 541   assert(ylen && "Divided by zero???");
 542   if (isSingleWord()) {
 543     if (isSigned && RHS.isSigned)
 544       VAL = RHS.isSingleWord() ? (int64_t(VAL) / int64_t(RHS.VAL)) :
 545             (ylen > 1 ? 0 : int64_t(VAL) / int64_t(RHS.pVal[0]));
 546     else
 547       VAL = RHS.isSingleWord() ? (VAL / RHS.VAL) :
 548           (ylen > 1 ? 0 : VAL / RHS.pVal[0]);
 549   } else {
 550     unsigned first2 = numWords() * APINT_BITS_PER_WORD - CountLeadingZeros();
 551     unsigned xlen = !first2 ? 0 : whichWord(first2 - 1) + 1;
 552     if (!xlen)
 553       return *this;
 554     else if ((*this) < RHS)
 555       bzero(pVal, numWords() * 8);
 556     else if ((*this) == RHS) {
 557       bzero(pVal, numWords() * 8);
 558       pVal[0] = 1;
 559     } else if (xlen == 1)
 560       pVal[0] /= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 561     else {
 562       uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen];
 563       assert(xwords && ywords && "Memory Allocation Failed!");
 564       memcpy(xwords, pVal, xlen * 8);
 565       xwords[xlen] = 0;
 566       memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8);
 567       if (unsigned nshift = 63 - (first - 1) % 64) {
 568         lshift(ywords, 0, ywords, ylen, nshift);
 569         unsigned xlentmp = xlen;
 570         xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift);
 571       }
 572       div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2);
 573       bzero(pVal, numWords() * 8);
 574       memcpy(pVal, xwords + ylen, (xlen - ylen) * 8);
 575       delete[] xwords;
 576       delete[] ywords;
 577     }
 578   }
 579   return *this;
 580 }
 581
 582 /// @brief Remainder assignment operator. Yields the remainder from the
 583 /// division of this APInt by the given APInt& RHS and assigns the remainder
 584 /// to this APInt.
 585 APInt& APInt::operator%=(const APInt& RHS) {
 586   unsigned first = RHS.numWords() * APINT_BITS_PER_WORD -
 587                    RHS.CountLeadingZeros();
 588   unsigned ylen = !first ? 0 : whichWord(first - 1) + 1;
 589   assert(ylen && "Performing remainder operation by zero ???");
 590   if (isSingleWord()) {
 591     if (isSigned && RHS.isSigned)
 592       VAL = RHS.isSingleWord() ? (int64_t(VAL) % int64_t(RHS.VAL)) :
 593             (ylen > 1 ? VAL : int64_t(VAL) % int64_t(RHS.pVal[0]));
 594     else
 595       VAL = RHS.isSingleWord() ? (VAL % RHS.VAL) :
 596           (ylen > 1 ? VAL : VAL % RHS.pVal[0]);
 597   } else {
 598     unsigned first2 = numWords() * APINT_BITS_PER_WORD - CountLeadingZeros();
 599     unsigned xlen = !first2 ? 0 : whichWord(first2 - 1) + 1;
 600     if (!xlen || (*this) < RHS)
 601       return *this;
 602     else if ((*this) == RHS)
 603       bzero(pVal, numWords() * 8);
 604     else if (xlen == 1)
 605       pVal[0] %= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 606     else {
 607       uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen];
 608       assert(xwords && ywords && "Memory Allocation Failed!");
 609       memcpy(xwords, pVal, xlen * 8);
 610       xwords[xlen] = 0;
 611       memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8);
 612       unsigned nshift = 63 - (first - 1) % 64;
 613       if (nshift) {
 614         lshift(ywords, 0, ywords, ylen, nshift);
 615         unsigned xlentmp = xlen;
 616         xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift);
 617       }
 618       div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2);
 619       bzero(pVal, numWords() * 8);
 620       for (unsigned i = 0; i < ylen-1; ++i)
 621         pVal[i] = (xwords[i] >> nshift) | (xwords[i+1] << (64 - nshift));
 622       pVal[ylen-1] = xwords[ylen-1] >> nshift;
 623       delete[] xwords;
 624       delete[] ywords;
 625     }
 626   }
 627   return *this;
 628 }
 629
 630 /// @brief Bitwise AND assignment operator. Performs bitwise AND operation on
 631 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 632 APInt& APInt::operator&=(const APInt& RHS) {
 633   if (isSingleWord()) {
 634     if (RHS.isSingleWord()) VAL &= RHS.VAL;
 635     else VAL &= RHS.pVal[0];
 636   } else {
 637     if (RHS.isSingleWord()) {
 638       bzero(pVal, (numWords() - 1) * 8);
 639       pVal[0] &= RHS.VAL;
 640     } else {
 641       unsigned minwords = numWords() < RHS.numWords() ? numWords() : RHS.numWords();
 642       for (unsigned i = 0; i < minwords; ++i)
 643         pVal[i] &= RHS.pVal[i];
 644       if (numWords() > minwords) bzero(pVal+minwords, (numWords() - minwords) * 8);
 645     }
 646   }
 647   return *this;
 648 }
 649
 650 /// @brief Bitwise OR assignment operator. Performs bitwise OR operation on
 651 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 652 APInt& APInt::operator|=(const APInt& RHS) {
 653   if (isSingleWord()) {
 654     if (RHS.isSingleWord()) VAL |= RHS.VAL;
 655     else VAL |= RHS.pVal[0];
 656   } else {
 657     if (RHS.isSingleWord()) {
 658       pVal[0] |= RHS.VAL;
 659     } else {
 660       unsigned minwords = numWords() < RHS.numWords() ? numWords() : RHS.numWords();
 661       for (unsigned i = 0; i < minwords; ++i)
 662         pVal[i] |= RHS.pVal[i];
 663     }
 664   }
 665   TruncToBits();
 666   return *this;
 667 }
 668
 669 /// @brief Bitwise XOR assignment operator. Performs bitwise XOR operation on
 670 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 671 APInt& APInt::operator^=(const APInt& RHS) {
 672   if (isSingleWord()) {
 673     if (RHS.isSingleWord()) VAL ^= RHS.VAL;
 674     else VAL ^= RHS.pVal[0];
 675   } else {
 676     if (RHS.isSingleWord()) {
 677       for (unsigned i = 0; i < numWords(); ++i)
 678         pVal[i] ^= RHS.VAL;
 679     } else {
 680       unsigned minwords = numWords() < RHS.numWords() ? numWords() : RHS.numWords();
 681       for (unsigned i = 0; i < minwords; ++i)
 682         pVal[i] ^= RHS.pVal[i];
 683       if (numWords() > minwords)
 684         for (unsigned i = minwords; i < numWords(); ++i)
 685           pVal[i] ^= 0;
 686     }
 687   }
 688   TruncToBits();
 689   return *this;
 690 }
 691
 692 /// @brief Bitwise AND operator. Performs bitwise AND operation on this APInt
 693 /// and the given APInt& RHS.
 694 APInt APInt::operator&(const APInt& RHS) const {
 695   APInt API(RHS);
 696   return API &= *this;
 697 }
 698
 699 /// @brief Bitwise OR operator. Performs bitwise OR operation on this APInt
 700 /// and the given APInt& RHS.
 701 APInt APInt::operator|(const APInt& RHS) const {
 702   APInt API(RHS);
 703   API |= *this;
 704   API.TruncToBits();
 705   return API;
 706 }
 707
 708 /// @brief Bitwise XOR operator. Performs bitwise XOR operation on this APInt
 709 /// and the given APInt& RHS.
 710 APInt APInt::operator^(const APInt& RHS) const {
 711   APInt API(RHS);
 712   API ^= *this;
 713   API.TruncToBits();
 714   return API;
 715 }
 716
 717 /// @brief Logical AND operator. Performs logical AND operation on this APInt
 718 /// and the given APInt& RHS.
 719 bool APInt::operator&&(const APInt& RHS) const {
 720   if (isSingleWord())
 721     return RHS.isSingleWord() ? VAL && RHS.VAL : VAL && RHS.pVal[0];
 722   else if (RHS.isSingleWord())
 723     return RHS.VAL && pVal[0];
 724   else {
 725     unsigned minN = std::min(numWords(), RHS.numWords());
 726     for (unsigned i = 0; i < minN; ++i)
 727       if (pVal[i] && RHS.pVal[i])
 728         return true;
 729   }
 730   return false;
 731 }
 732
 733 /// @brief Logical OR operator. Performs logical OR operation on this APInt
 734 /// and the given APInt& RHS.
 735 bool APInt::operator||(const APInt& RHS) const {
 736   if (isSingleWord())
 737     return RHS.isSingleWord() ? VAL || RHS.VAL : VAL || RHS.pVal[0];
 738   else if (RHS.isSingleWord())
 739     return RHS.VAL || pVal[0];
 740   else {
 741     unsigned minN = std::min(numWords(), RHS.numWords());
 742     for (unsigned i = 0; i < minN; ++i)
 743       if (pVal[i] || RHS.pVal[i])
 744         return true;
 745   }
 746   return false;
 747 }
 748
 749 /// @brief Logical negation operator. Performs logical negation operation on
 750 /// this APInt.
 751 bool APInt::operator !() const {
 752   if (isSingleWord())
 753     return !VAL;
 754   else
 755     for (unsigned i = 0; i < numWords(); ++i)
 756        if (pVal[i])
 757          return false;
 758   return true;
 759 }
 760
 761 /// @brief Multiplication operator. Multiplies this APInt by the given APInt&
 762 /// RHS.
 763 APInt APInt::operator*(const APInt& RHS) const {
 764   APInt API(RHS);
 765   API *= *this;
 766   API.TruncToBits();
 767   return API;
 768 }
 769
 770 /// @brief Division operator. Divides this APInt by the given APInt& RHS.
 771 APInt APInt::operator/(const APInt& RHS) const {
 772   APInt API(*this);
 773   return API /= RHS;
 774 }
 775
 776 /// @brief Remainder operator. Yields the remainder from the division of this
 777 /// APInt and the given APInt& RHS.
 778 APInt APInt::operator%(const APInt& RHS) const {
 779   APInt API(*this);
 780   return API %= RHS;
 781 }
 782
 783 /// @brief Addition operator. Adds this APInt by the given APInt& RHS.
 784 APInt APInt::operator+(const APInt& RHS) const {
 785   APInt API(*this);
 786   API += RHS;
 787   API.TruncToBits();
 788   return API;
 789 }
 790
 791 /// @brief Subtraction operator. Subtracts this APInt by the given APInt& RHS
 792 APInt APInt::operator-(const APInt& RHS) const {
 793   APInt API(*this);
 794   API -= RHS;
 795   API.TruncToBits();
 796   return API;
 797 }
 798
 799 /// @brief Array-indexing support.
 800 bool APInt::operator[](unsigned bitPosition) const {
 801   return maskBit(bitPosition) & (isSingleWord() ?
 802          VAL : pVal[whichWord(bitPosition)]) != 0;
 803 }
 804
 805 /// @brief Equality operator. Compare this APInt with the given APInt& RHS
 806 /// for the validity of the equality relationship.
 807 bool APInt::operator==(const APInt& RHS) const {
 808   unsigned n1 = numWords() * APINT_BITS_PER_WORD - CountLeadingZeros(),
 809            n2 = RHS.numWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros();
 810   if (n1 != n2) return false;
 811   else if (isSingleWord())
 812     return VAL == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 813   else {
 814     if (n1 <= 64)
 815       return pVal[0] == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 816     for (int i = whichWord(n1 - 1); i >= 0; --i)
 817       if (pVal[i] != RHS.pVal[i]) return false;
 818   }
 819   return true;
 820 }
 821
 822 /// @brief Inequality operator. Compare this APInt with the given APInt& RHS
 823 /// for the validity of the inequality relationship.
 824 bool APInt::operator!=(const APInt& RHS) const {
 825   return !((*this) == RHS);
 826 }
 827
 828 /// @brief Less-than operator. Compare this APInt with the given APInt& RHS
 829 /// for the validity of the less-than relationship.
 830 bool APInt::operator <(const APInt& RHS) const {
 831   if (isSigned && RHS.isSigned) {
 832     if ((*this)[bitsnum-1] > RHS[RHS.bitsnum-1])
 833       return false;
 834     else if ((*this)[bitsnum-1] < RHS[RHS.bitsnum-1])
 835       return true;
 836   }
 837   unsigned n1 = numWords() * 64 - CountLeadingZeros(),
 838            n2 = RHS.numWords() * 64 - RHS.CountLeadingZeros();
 839   if (n1 < n2) return true;
 840   else if (n1 > n2) return false;
 841   else if (isSingleWord())
 842     return VAL < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 843   else {
 844     if (n1 <= 64)
 845       return pVal[0] < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 846     for (int i = whichWord(n1 - 1); i >= 0; --i) {
 847       if (pVal[i] > RHS.pVal[i]) return false;
 848       else if (pVal[i] < RHS.pVal[i]) return true;
 849     }
 850   }
 851   return false;
 852 }
 853
 854 /// @brief Less-than-or-equal operator. Compare this APInt with the given
 855 /// APInt& RHS for the validity of the less-than-or-equal relationship.
 856 bool APInt::operator<=(const APInt& RHS) const {
 857   return (*this) == RHS || (*this) < RHS;
 858 }
 859
 860 /// @brief Greater-than operator. Compare this APInt with the given APInt& RHS
 861 /// for the validity of the greater-than relationship.
 862 bool APInt::operator >(const APInt& RHS) const {
 863   return !((*this) <= RHS);
 864 }
 865
 866 /// @brief Greater-than-or-equal operator. Compare this APInt with the given
 867 /// APInt& RHS for the validity of the greater-than-or-equal relationship.
 868 bool APInt::operator>=(const APInt& RHS) const {
 869   return !((*this) < RHS);
 870 }
 871
 872 /// Set the given bit to 1 whose poition is given as "bitPosition".
 873 /// @brief Set a given bit to 1.
 874 APInt& APInt::set(unsigned bitPosition) {
 875   if (isSingleWord()) VAL |= maskBit(bitPosition);
 876   else pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
 877   return *this;
 878 }
 879
 880 /// @brief Set every bit to 1.
 881 APInt& APInt::set() {
 882   if (isSingleWord()) VAL = -1ULL;
 883   else
 884     for (unsigned i = 0; i < numWords(); ++i)
 885       pVal[i] = -1ULL;
 886   return *this;
 887 }
 888
 889 /// Set the given bit to 0 whose position is given as "bitPosition".
 890 /// @brief Set a given bit to 0.
 891 APInt& APInt::clear(unsigned bitPosition) {
 892   if (isSingleWord()) VAL &= ~maskBit(bitPosition);
 893   else pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
 894   return *this;
 895 }
 896
 897 /// @brief Set every bit to 0.
 898 APInt& APInt::clear() {
 899   if (isSingleWord()) VAL = 0;
 900   else bzero(pVal, numWords() * 8);
 901   return *this;
 902 }
 903
 904 /// @brief Left-shift assignment operator. Left-shift the APInt by shiftAmt
 905 /// and assigns the result to this APInt.
 906 APInt& APInt::operator<<=(unsigned shiftAmt) {
 907   if (shiftAmt >= bitsnum) {
 908     if (isSingleWord()) VAL = 0;
 909     else bzero(pVal, numWords() * 8);
 910   } else {
 911     for (unsigned i = 0; i < shiftAmt; ++i) clear(i);
 912     for (unsigned i = shiftAmt; i < bitsnum; ++i) {
 913       if ((*this)[i-shiftAmt]) set(i);
 914       else clear(i);
 915     }
 916   }
 917   return *this;
 918 }
 919
 920 /// @brief Left-shift operator. Left-shift the APInt by shiftAmt.
 921 APInt APInt::operator<<(unsigned shiftAmt) const {
 922   APInt API(*this);
 923   API <<= shiftAmt;
 924   return API;
 925 }
 926
 927 /// @brief Right-shift assignment operator. Right-shift the APInt by shiftAmt
 928 /// and assigns the result to this APInt.
 929 APInt& APInt::operator>>=(unsigned shiftAmt) {
 930   bool isAShr = isSigned && (*this)[bitsnum-1];
 931   if (isSingleWord())
 932     VAL = isAShr ? (int64_t(VAL) >> shiftAmt) : (VAL >> shiftAmt);
 933   else {
 934     unsigned i = 0;
 935     for (i = 0; i < bitsnum - shiftAmt; ++i)
 936       if ((*this)[i+shiftAmt]) set(i);
 937       else clear(i);
 938     for (; i < bitsnum; ++i)
 939       isAShr ? set(i) : clear(i);
 940   }
 941   return *this;
 942 }
 943
 944 /// @brief Right-shift operator. Right-shift the APInt by shiftAmt.
 945 APInt APInt::operator>>(unsigned shiftAmt) const {
 946   APInt API(*this);
 947   API >>= shiftAmt;
 948   return API;
 949 }
 950
 951 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
 952 /// this APInt.
 953 APInt APInt::operator~() const {
 954   APInt API(*this);
 955   API.flip();
 956   return API;
 957 }
 958
 959 /// @brief Toggle every bit to its opposite value.
 960 APInt& APInt::flip() {
 961   if (isSingleWord()) VAL = (~(VAL << (64 - bitsnum))) >> (64 - bitsnum);
 962   else {
 963     unsigned i = 0;
 964     for (; i < numWords() - 1; ++i)
 965       pVal[i] = ~pVal[i];
 966     unsigned offset = 64 - (bitsnum - 64 * (i - 1));
 967     pVal[i] = (~(pVal[i] << offset)) >> offset;
 968   }
 969   return *this;
 970 }
 971
 972 /// Toggle a given bit to its opposite value whose position is given
 973 /// as "bitPosition".
 974 /// @brief Toggles a given bit to its opposite value.
 975 APInt& APInt::flip(unsigned bitPosition) {
 976   assert(bitPosition < bitsnum && "Out of the bit-width range!");
 977   if ((*this)[bitPosition]) clear(bitPosition);
 978   else set(bitPosition);
 979   return *this;
 980 }
 981
 982 /// to_string - This function translates the APInt into a string.
 983 std::string APInt::to_string(uint8_t radix) const {
 984   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
 985          "Radix should be 2, 8, 10, or 16!");
 986   std::ostringstream buf;
 987   buf << std::setbase(radix);
 988   // If the radix is a power of 2, set the format of ostringstream,
 989   // and output the value into buf.
 990   if ((radix & (radix - 1)) == 0) {
 991     if (isSingleWord()) buf << VAL;
 992     else {
 993       buf << pVal[numWords()-1];
 994       buf << std::setw(64 / (radix / 8 + 2)) << std::setfill('0');
 995       for (int i = numWords() - 2; i >= 0; --i)
 996         buf << pVal[i];
 997     }
 998   }
 999   else {  // If the radix = 10, need to translate the value into a
1000           // string.
1001     if (isSingleWord()) buf << VAL;
1002     else {
1003       // FIXME: To be supported.
1004     }
1005   }
1006   return buf.str();
1007 }
1008
1009 /// getMaxValue - This function returns the largest value
1010 /// for an APInt of the specified bit-width and if isSign == true,
1011 /// it should be largest signed value, otherwise unsigned value.
1012 APInt APInt::getMaxValue(unsigned numBits, bool isSign) {
1013   APInt APIVal(numBits, 1);
1014   APIVal.set();
1015   return isSign ? APIVal.clear(numBits) : APIVal;
1016 }
1017
1018 /// getMinValue - This function returns the smallest value for
1019 /// an APInt of the given bit-width and if isSign == true,
1020 /// it should be smallest signed value, otherwise zero.
1021 APInt APInt::getMinValue(unsigned numBits, bool isSign) {
1022   APInt APIVal(0, numBits);
1023   return isSign ? APIVal : APIVal.set(numBits);
1024 }
1025
1026 /// getAllOnesValue - This function returns an all-ones value for
1027 /// an APInt of the specified bit-width.
1028 APInt APInt::getAllOnesValue(unsigned numBits) {
1029   return getMaxValue(numBits, false);
1030 }
1031
1032 /// getNullValue - This function creates an '0' value for an
1033 /// APInt of the specified bit-width.
1034 APInt APInt::getNullValue(unsigned numBits) {
1035   return getMinValue(numBits, true);
1036 }
1037
1038 /// HiBits - This function returns the high "numBits" bits of this APInt.
1039 APInt APInt::HiBits(unsigned numBits) const {
1040   return (*this) >> (bitsnum - numBits);
1041 }
1042
1043 /// LoBits - This function returns the low "numBits" bits of this APInt.
1044 APInt APInt::LoBits(unsigned numBits) const {
1045   return ((*this) << (bitsnum - numBits)) >> (bitsnum - numBits);
1046 }
1047
1048 /// CountLeadingZeros - This function is a APInt version corresponding to
1049 /// llvm/include/llvm/Support/MathExtras.h's function
1050 /// CountLeadingZeros_{32, 64}. It performs platform optimal form of counting
1051 /// the number of zeros from the most significant bit to the first one bit.
1052 /// @returns numWord() * 64 if the value is zero.
1053 unsigned APInt::CountLeadingZeros() const {
1054   if (isSingleWord())
1055     return CountLeadingZeros_64(VAL);
1056   unsigned Count = 0;
1057   for (int i = numWords() - 1; i >= 0; --i) {
1058     unsigned tmp = CountLeadingZeros_64(pVal[i]);
1059     Count += tmp;
1060     if (tmp != 64)
1061       break;
1062   }
1063   return Count;
1064 }
1065
1066 /// CountTrailingZero - This function is a APInt version corresponding to
1067 /// llvm/include/llvm/Support/MathExtras.h's function
1068 /// CountTrailingZeros_{32, 64}. It performs platform optimal form of counting
1069 /// the number of zeros from the least significant bit to the first one bit.
1070 /// @returns numWord() * 64 if the value is zero.
1071 unsigned APInt::CountTrailingZeros() const {
1072   if (isSingleWord())
1073     return CountTrailingZeros_64(~VAL & (VAL - 1));
1074   APInt Tmp = ~(*this) & ((*this) - 1);
1075   return numWords() * 64 - Tmp.CountLeadingZeros();
1076 }
1077
1078 /// CountPopulation - This function is a APInt version corresponding to
1079 /// llvm/include/llvm/Support/MathExtras.h's function
1080 /// CountPopulation_{32, 64}. It counts the number of set bits in a value.
1081 /// @returns 0 if the value is zero.
1082 unsigned APInt::CountPopulation() const {
1083   if (isSingleWord())
1084     return CountPopulation_64(VAL);
1085   unsigned Count = 0;
1086   for (unsigned i = 0; i < numWords(); ++i)
1087     Count += CountPopulation_64(pVal[i]);
1088   return Count;
1089 }
1090
1091
1092 /// ByteSwap - This function returns a byte-swapped representation of the
1093 /// APInt argument, APIVal.
1094 APInt llvm::ByteSwap(const APInt& APIVal) {
1095   if (APIVal.bitsnum <= 32)
1096     return APInt(APIVal.bitsnum, ByteSwap_32(unsigned(APIVal.VAL)));
1097   else if (APIVal.bitsnum <= 64)
1098     return APInt(APIVal.bitsnum, ByteSwap_64(APIVal.VAL));
1099   else
1100     return APIVal;
1101 }
1102
1103 /// GreatestCommonDivisor - This function returns the greatest common
1104 /// divisor of the two APInt values using Enclid's algorithm.
1105 APInt llvm::GreatestCommonDivisor(const APInt& API1, const APInt& API2) {
1106   APInt A = API1, B = API2;
1107   while (!!B) {
1108     APInt T = B;
1109     B = A % B;
1110     A = T;
1111   }
1112   return A;
1113 }