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