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 <cstring>
  19 #include <cstdlib>
  20 using namespace llvm;
  21
  22 // A utility function for allocating memory, checking for allocation failures,
  23 // and ensuring the contents is zeroed.
  24 inline static uint64_t* getClearedMemory(uint32_t numWords) {
  25   uint64_t * result = new uint64_t[numWords];
  26   assert(result && "APInt memory allocation fails!");
  27   memset(result, 0, numWords * sizeof(uint64_t));
  28   return result;
  29 }
  30
  31 // A utility function for allocating memory and checking for allocation failure.
  32 inline static uint64_t* getMemory(uint32_t numWords) {
  33   uint64_t * result = new uint64_t[numWords];
  34   assert(result && "APInt memory allocation fails!");
  35   return result;
  36 }
  37
  38 APInt::APInt(uint32_t numBits, uint64_t val)
  39   : BitWidth(numBits), pVal(0) {
  40   assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
  41   assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
  42   if (isSingleWord())
  43     VAL = val & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitWidth));
  44   else {
  45     pVal = getClearedMemory(getNumWords());
  46     pVal[0] = val;
  47   }
  48 }
  49
  50 APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[])
  51   : BitWidth(numBits), pVal(0)  {
  52   assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
  53   assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
  54   assert(bigVal && "Null pointer detected!");
  55   if (isSingleWord())
  56     VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitWidth));
  57   else {
  58     pVal = getMemory(getNumWords());
  59     // Calculate the actual length of bigVal[].
  60     uint32_t maxN = std::max<uint32_t>(numWords, getNumWords());
  61     uint32_t minN = std::min<uint32_t>(numWords, getNumWords());
  62     memcpy(pVal, bigVal, (minN - 1) * APINT_WORD_SIZE);
  63     pVal[minN-1] = bigVal[minN-1] &
  64                     (~uint64_t(0ULL) >>
  65                      (APINT_BITS_PER_WORD - BitWidth % APINT_BITS_PER_WORD));
  66     if (maxN == getNumWords())
  67       memset(pVal+numWords, 0, (getNumWords() - numWords) * APINT_WORD_SIZE);
  68   }
  69 }
  70
  71 /// @brief Create a new APInt by translating the char array represented
  72 /// integer value.
  73 APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
  74              uint8_t radix)
  75   : BitWidth(numbits), pVal(0) {
  76   fromString(numbits, StrStart, slen, radix);
  77 }
  78
  79 /// @brief Create a new APInt by translating the string represented
  80 /// integer value.
  81 APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix)
  82   : BitWidth(numbits), pVal(0) {
  83   assert(!Val.empty() && "String empty?");
  84   fromString(numbits, Val.c_str(), Val.size(), radix);
  85 }
  86
  87 /// @brief Copy constructor
  88 APInt::APInt(const APInt& APIVal)
  89   : BitWidth(APIVal.BitWidth), pVal(0) {
  90   if (isSingleWord())
  91     VAL = APIVal.VAL;
  92   else {
  93     pVal = getMemory(getNumWords());
  94     memcpy(pVal, APIVal.pVal, getNumWords() * APINT_WORD_SIZE);
  95   }
  96 }
  97
  98 APInt::~APInt() {
  99   if (!isSingleWord() && pVal)
 100     delete[] pVal;
 101 }
 102
 103 /// @brief Copy assignment operator. Create a new object from the given
 104 /// APInt one by initialization.
 105 APInt& APInt::operator=(const APInt& RHS) {
 106   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 107   if (isSingleWord())
 108     VAL = RHS.VAL;
 109   else
 110     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
 111   return *this;
 112 }
 113
 114 /// @brief Assignment operator. Assigns a common case integer value to
 115 /// the APInt.
 116 APInt& APInt::operator=(uint64_t RHS) {
 117   if (isSingleWord())
 118     VAL = RHS;
 119   else {
 120     pVal[0] = RHS;
 121     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
 122   }
 123   return *this;
 124 }
 125
 126 /// add_1 - This function adds a single "digit" integer, y, to the multiple
 127 /// "digit" integer array,  x[]. x[] is modified to reflect the addition and
 128 /// 1 is returned if there is a carry out, otherwise 0 is returned.
 129 /// @returns the carry of the addition.
 130 static uint64_t add_1(uint64_t dest[],
 131                              uint64_t x[], uint32_t len,
 132                              uint64_t y) {
 133   for (uint32_t i = 0; i < len; ++i) {
 134     dest[i] = y + x[i];
 135     if (dest[i] < y)
 136       y = 1;
 137     else {
 138       y = 0;
 139       break;
 140     }
 141   }
 142   return y;
 143 }
 144
 145 /// @brief Prefix increment operator. Increments the APInt by one.
 146 APInt& APInt::operator++() {
 147   if (isSingleWord())
 148     ++VAL;
 149   else
 150     add_1(pVal, pVal, getNumWords(), 1);
 151   clearUnusedBits();
 152   return *this;
 153 }
 154
 155 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
 156 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
 157 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
 158 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
 159 /// In other words, if y > x then this function returns 1, otherwise 0.
 160 static uint64_t sub_1(uint64_t x[], uint32_t len,
 161                              uint64_t y) {
 162   for (uint32_t i = 0; i < len; ++i) {
 163     uint64_t X = x[i];
 164     x[i] -= y;
 165     if (y > X)
 166       y = 1;  // We have to "borrow 1" from next "digit"
 167     else {
 168       y = 0;  // No need to borrow
 169       break;  // Remaining digits are unchanged so exit early
 170     }
 171   }
 172   return y;
 173 }
 174
 175 /// @brief Prefix decrement operator. Decrements the APInt by one.
 176 APInt& APInt::operator--() {
 177   if (isSingleWord())
 178     --VAL;
 179   else
 180     sub_1(pVal, getNumWords(), 1);
 181   clearUnusedBits();
 182   return *this;
 183 }
 184
 185 /// add - This function adds the integer array x[] by integer array
 186 /// y[] and returns the carry.
 187 static uint64_t add(uint64_t dest[], uint64_t x[],
 188                            uint64_t y[], uint32_t len) {
 189   uint32_t carry = 0;
 190   for (uint32_t i = 0; i< len; ++i) {
 191     carry += x[i];
 192     dest[i] = carry + y[i];
 193     carry = carry < x[i] ? 1 : (dest[i] < carry ? 1 : 0);
 194   }
 195   return carry;
 196 }
 197
 198 /// @brief Addition assignment operator. Adds this APInt by the given APInt&
 199 /// RHS and assigns the result to this APInt.
 200 APInt& APInt::operator+=(const APInt& RHS) {
 201   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 202   if (isSingleWord()) VAL += RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 203   else {
 204     if (RHS.isSingleWord()) add_1(pVal, pVal, getNumWords(), RHS.VAL);
 205     else {
 206       if (getNumWords() <= RHS.getNumWords())
 207         add(pVal, pVal, RHS.pVal, getNumWords());
 208       else {
 209         uint64_t carry = add(pVal, pVal, RHS.pVal, RHS.getNumWords());
 210         add_1(pVal + RHS.getNumWords(), pVal + RHS.getNumWords(),
 211               getNumWords() - RHS.getNumWords(), carry);
 212       }
 213     }
 214   }
 215   clearUnusedBits();
 216   return *this;
 217 }
 218
 219 /// sub - This function subtracts the integer array x[] by
 220 /// integer array y[], and returns the borrow-out carry.
 221 static uint64_t sub(uint64_t dest[], uint64_t x[],
 222                            uint64_t y[], uint32_t len) {
 223   // Carry indicator.
 224   uint64_t cy = 0;
 225
 226   for (uint32_t i = 0; i < len; ++i) {
 227     uint64_t Y = y[i], X = x[i];
 228     Y += cy;
 229
 230     cy = Y < cy ? 1 : 0;
 231     Y = X - Y;
 232     cy += Y > X ? 1 : 0;
 233     dest[i] = Y;
 234   }
 235   return cy;
 236 }
 237
 238 /// @brief Subtraction assignment operator. Subtracts this APInt by the given
 239 /// APInt &RHS and assigns the result to this APInt.
 240 APInt& APInt::operator-=(const APInt& RHS) {
 241   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 242   if (isSingleWord())
 243     VAL -= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 244   else {
 245     if (RHS.isSingleWord())
 246       sub_1(pVal, getNumWords(), RHS.VAL);
 247     else {
 248       if (RHS.getNumWords() < getNumWords()) {
 249         uint64_t carry = sub(pVal, pVal, RHS.pVal, RHS.getNumWords());
 250         sub_1(pVal + RHS.getNumWords(), getNumWords() - RHS.getNumWords(),
 251               carry);
 252       }
 253       else
 254         sub(pVal, pVal, RHS.pVal, getNumWords());
 255     }
 256   }
 257   clearUnusedBits();
 258   return *this;
 259 }
 260
 261 /// mul_1 - This function performs the multiplication operation on a
 262 /// large integer (represented as an integer array) and a uint64_t integer.
 263 /// @returns the carry of the multiplication.
 264 static uint64_t mul_1(uint64_t dest[],
 265                              uint64_t x[], uint32_t len,
 266                              uint64_t y) {
 267   // Split y into high 32-bit part and low 32-bit part.
 268   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
 269   uint64_t carry = 0, lx, hx;
 270   for (uint32_t i = 0; i < len; ++i) {
 271     lx = x[i] & 0xffffffffULL;
 272     hx = x[i] >> 32;
 273     // hasCarry - A flag to indicate if has carry.
 274     // hasCarry == 0, no carry
 275     // hasCarry == 1, has carry
 276     // hasCarry == 2, no carry and the calculation result == 0.
 277     uint8_t hasCarry = 0;
 278     dest[i] = carry + lx * ly;
 279     // Determine if the add above introduces carry.
 280     hasCarry = (dest[i] < carry) ? 1 : 0;
 281     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
 282     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
 283     // (2^32 - 1) + 2^32 = 2^64.
 284     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
 285
 286     carry += (lx * hy) & 0xffffffffULL;
 287     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
 288     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
 289             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
 290   }
 291
 292   return carry;
 293 }
 294
 295 /// mul - This function multiplies integer array x[] by integer array y[] and
 296 /// stores the result into integer array dest[].
 297 /// Note the array dest[]'s size should no less than xlen + ylen.
 298 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen,
 299                 uint64_t y[], uint32_t ylen) {
 300   dest[xlen] = mul_1(dest, x, xlen, y[0]);
 301
 302   for (uint32_t i = 1; i < ylen; ++i) {
 303     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
 304     uint64_t carry = 0, lx, hx;
 305     for (uint32_t j = 0; j < xlen; ++j) {
 306       lx = x[j] & 0xffffffffULL;
 307       hx = x[j] >> 32;
 308       // hasCarry - A flag to indicate if has carry.
 309       // hasCarry == 0, no carry
 310       // hasCarry == 1, has carry
 311       // hasCarry == 2, no carry and the calculation result == 0.
 312       uint8_t hasCarry = 0;
 313       uint64_t resul = carry + lx * ly;
 314       hasCarry = (resul < carry) ? 1 : 0;
 315       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
 316       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
 317
 318       carry += (lx * hy) & 0xffffffffULL;
 319       resul = (carry << 32) | (resul & 0xffffffffULL);
 320       dest[i+j] += resul;
 321       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
 322               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
 323               ((lx * hy) >> 32) + hx * hy;
 324     }
 325     dest[i+xlen] = carry;
 326   }
 327 }
 328
 329 /// @brief Multiplication assignment operator. Multiplies this APInt by the
 330 /// given APInt& RHS and assigns the result to this APInt.
 331 APInt& APInt::operator*=(const APInt& RHS) {
 332   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 333   if (isSingleWord()) VAL *= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
 334   else {
 335     // one-based first non-zero bit position.
 336     uint32_t first = getActiveBits();
 337     uint32_t xlen = !first ? 0 : whichWord(first - 1) + 1;
 338     if (!xlen)
 339       return *this;
 340     else if (RHS.isSingleWord())
 341       mul_1(pVal, pVal, xlen, RHS.VAL);
 342     else {
 343       first = RHS.getActiveBits();
 344       uint32_t ylen = !first ? 0 : whichWord(first - 1) + 1;
 345       if (!ylen) {
 346         memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
 347         return *this;
 348       }
 349       uint64_t *dest = getMemory(xlen+ylen);
 350       mul(dest, pVal, xlen, RHS.pVal, ylen);
 351       memcpy(pVal, dest, ((xlen + ylen >= getNumWords()) ?
 352                          getNumWords() : xlen + ylen) * APINT_WORD_SIZE);
 353       delete[] dest;
 354     }
 355   }
 356   clearUnusedBits();
 357   return *this;
 358 }
 359
 360 /// @brief Bitwise AND assignment operator. Performs bitwise AND operation on
 361 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 362 APInt& APInt::operator&=(const APInt& RHS) {
 363   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 364   if (isSingleWord()) {
 365     VAL &= RHS.VAL;
 366     return *this;
 367   }
 368   uint32_t numWords = getNumWords();
 369   for (uint32_t i = 0; i < numWords; ++i)
 370     pVal[i] &= RHS.pVal[i];
 371   return *this;
 372 }
 373
 374 /// @brief Bitwise OR assignment operator. Performs bitwise OR operation on
 375 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 376 APInt& APInt::operator|=(const APInt& RHS) {
 377   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 378   if (isSingleWord()) {
 379     VAL |= RHS.VAL;
 380     return *this;
 381   }
 382   uint32_t numWords = getNumWords();
 383   for (uint32_t i = 0; i < numWords; ++i)
 384     pVal[i] |= RHS.pVal[i];
 385   return *this;
 386 }
 387
 388 /// @brief Bitwise XOR assignment operator. Performs bitwise XOR operation on
 389 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
 390 APInt& APInt::operator^=(const APInt& RHS) {
 391   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 392   if (isSingleWord()) {
 393     VAL ^= RHS.VAL;
 394     return *this;
 395   }
 396   uint32_t numWords = getNumWords();
 397   for (uint32_t i = 0; i < numWords; ++i)
 398     pVal[i] ^= RHS.pVal[i];
 399   return *this;
 400 }
 401
 402 /// @brief Bitwise AND operator. Performs bitwise AND operation on this APInt
 403 /// and the given APInt& RHS.
 404 APInt APInt::operator&(const APInt& RHS) const {
 405   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 406   if (isSingleWord())
 407     return APInt(getBitWidth(), VAL & RHS.VAL);
 408
 409   APInt Result(*this);
 410   uint32_t numWords = getNumWords();
 411   for (uint32_t i = 0; i < numWords; ++i)
 412     Result.pVal[i] &= RHS.pVal[i];
 413   return Result;
 414 }
 415
 416 /// @brief Bitwise OR operator. Performs bitwise OR operation on this APInt
 417 /// and the given APInt& RHS.
 418 APInt APInt::operator|(const APInt& RHS) const {
 419   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 420   if (isSingleWord())
 421     return APInt(getBitWidth(), VAL | RHS.VAL);
 422   APInt Result(*this);
 423   uint32_t numWords = getNumWords();
 424   for (uint32_t i = 0; i < numWords; ++i)
 425     Result.pVal[i] |= RHS.pVal[i];
 426   return Result;
 427 }
 428
 429 /// @brief Bitwise XOR operator. Performs bitwise XOR operation on this APInt
 430 /// and the given APInt& RHS.
 431 APInt APInt::operator^(const APInt& RHS) const {
 432   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 433   if (isSingleWord())
 434     return APInt(getBitWidth(), VAL ^ RHS.VAL);
 435   APInt Result(*this);
 436   uint32_t numWords = getNumWords();
 437   for (uint32_t i = 0; i < numWords; ++i)
 438     Result.pVal[i] ^= RHS.pVal[i];
 439   return Result;
 440 }
 441
 442 /// @brief Logical negation operator. Performs logical negation operation on
 443 /// this APInt.
 444 bool APInt::operator !() const {
 445   if (isSingleWord())
 446     return !VAL;
 447
 448   for (uint32_t i = 0; i < getNumWords(); ++i)
 449     if (pVal[i])
 450       return false;
 451   return true;
 452 }
 453
 454 /// @brief Multiplication operator. Multiplies this APInt by the given APInt&
 455 /// RHS.
 456 APInt APInt::operator*(const APInt& RHS) const {
 457   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 458   APInt API(RHS);
 459   API *= *this;
 460   API.clearUnusedBits();
 461   return API;
 462 }
 463
 464 /// @brief Addition operator. Adds this APInt by the given APInt& RHS.
 465 APInt APInt::operator+(const APInt& RHS) const {
 466   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 467   APInt API(*this);
 468   API += RHS;
 469   API.clearUnusedBits();
 470   return API;
 471 }
 472
 473 /// @brief Subtraction operator. Subtracts this APInt by the given APInt& RHS
 474 APInt APInt::operator-(const APInt& RHS) const {
 475   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 476   APInt API(*this);
 477   API -= RHS;
 478   return API;
 479 }
 480
 481 /// @brief Array-indexing support.
 482 bool APInt::operator[](uint32_t bitPosition) const {
 483   return (maskBit(bitPosition) & (isSingleWord() ?
 484           VAL : pVal[whichWord(bitPosition)])) != 0;
 485 }
 486
 487 /// @brief Equality operator. Compare this APInt with the given APInt& RHS
 488 /// for the validity of the equality relationship.
 489 bool APInt::operator==(const APInt& RHS) const {
 490   uint32_t n1 = getActiveBits();
 491   uint32_t n2 = RHS.getActiveBits();
 492   if (n1 != n2) return false;
 493   else if (isSingleWord())
 494     return VAL == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 495   else {
 496     if (n1 <= APINT_BITS_PER_WORD)
 497       return pVal[0] == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
 498     for (int i = whichWord(n1 - 1); i >= 0; --i)
 499       if (pVal[i] != RHS.pVal[i]) return false;
 500   }
 501   return true;
 502 }
 503
 504 /// @brief Equality operator. Compare this APInt with the given uint64_t value
 505 /// for the validity of the equality relationship.
 506 bool APInt::operator==(uint64_t Val) const {
 507   if (isSingleWord())
 508     return VAL == Val;
 509   else {
 510     uint32_t n = getActiveBits();
 511     if (n <= APINT_BITS_PER_WORD)
 512       return pVal[0] == Val;
 513     else
 514       return false;
 515   }
 516 }
 517
 518 /// @brief Unsigned less than comparison
 519 bool APInt::ult(const APInt& RHS) const {
 520   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
 521   if (isSingleWord())
 522     return VAL < RHS.VAL;
 523   else {
 524     uint32_t n1 = getActiveBits();
 525     uint32_t n2 = RHS.getActiveBits();
 526     if (n1 < n2)
 527       return true;
 528     else if (n2 < n1)
 529       return false;
 530     else if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
 531       return pVal[0] < RHS.pVal[0];
 532     for (int i = whichWord(n1 - 1); i >= 0; --i) {
 533       if (pVal[i] > RHS.pVal[i]) return false;
 534       else if (pVal[i] < RHS.pVal[i]) return true;
 535     }
 536   }
 537   return false;
 538 }
 539
 540 /// @brief Signed less than comparison
 541 bool APInt::slt(const APInt& RHS) const {
 542   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
 543   if (isSingleWord()) {
 544     int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
 545     int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
 546     return lhsSext < rhsSext;
 547   }
 548
 549   APInt lhs(*this);
 550   APInt rhs(*this);
 551   bool lhsNegative = false;
 552   bool rhsNegative = false;
 553   if (lhs[BitWidth-1]) {
 554     lhsNegative = true;
 555     lhs.flip();
 556     lhs++;
 557   }
 558   if (rhs[BitWidth-1]) {
 559     rhsNegative = true;
 560     rhs.flip();
 561     rhs++;
 562   }
 563   if (lhsNegative)
 564     if (rhsNegative)
 565       return !lhs.ult(rhs);
 566     else
 567       return true;
 568   else if (rhsNegative)
 569     return false;
 570   else
 571     return lhs.ult(rhs);
 572 }
 573
 574 /// Set the given bit to 1 whose poition is given as "bitPosition".
 575 /// @brief Set a given bit to 1.
 576 APInt& APInt::set(uint32_t bitPosition) {
 577   if (isSingleWord()) VAL |= maskBit(bitPosition);
 578   else pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
 579   return *this;
 580 }
 581
 582 /// @brief Set every bit to 1.
 583 APInt& APInt::set() {
 584   if (isSingleWord())
 585     VAL = ~0ULL >> (APINT_BITS_PER_WORD - BitWidth);
 586   else {
 587     for (uint32_t i = 0; i < getNumWords() - 1; ++i)
 588       pVal[i] = -1ULL;
 589     pVal[getNumWords() - 1] = ~0ULL >>
 590       (APINT_BITS_PER_WORD - BitWidth % APINT_BITS_PER_WORD);
 591   }
 592   return *this;
 593 }
 594
 595 /// Set the given bit to 0 whose position is given as "bitPosition".
 596 /// @brief Set a given bit to 0.
 597 APInt& APInt::clear(uint32_t bitPosition) {
 598   if (isSingleWord())
 599     VAL &= ~maskBit(bitPosition);
 600   else
 601     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
 602   return *this;
 603 }
 604
 605 /// @brief Set every bit to 0.
 606 APInt& APInt::clear() {
 607   if (isSingleWord())
 608     VAL = 0;
 609   else
 610     memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
 611   return *this;
 612 }
 613
 614 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
 615 /// this APInt.
 616 APInt APInt::operator~() const {
 617   APInt API(*this);
 618   API.flip();
 619   return API;
 620 }
 621
 622 /// @brief Toggle every bit to its opposite value.
 623 APInt& APInt::flip() {
 624   if (isSingleWord()) VAL = (~(VAL <<
 625         (APINT_BITS_PER_WORD - BitWidth))) >> (APINT_BITS_PER_WORD - BitWidth);
 626   else {
 627     uint32_t i = 0;
 628     for (; i < getNumWords() - 1; ++i)
 629       pVal[i] = ~pVal[i];
 630     uint32_t offset =
 631       APINT_BITS_PER_WORD - (BitWidth - APINT_BITS_PER_WORD * (i - 1));
 632     pVal[i] = (~(pVal[i] << offset)) >> offset;
 633   }
 634   return *this;
 635 }
 636
 637 /// Toggle a given bit to its opposite value whose position is given
 638 /// as "bitPosition".
 639 /// @brief Toggles a given bit to its opposite value.
 640 APInt& APInt::flip(uint32_t bitPosition) {
 641   assert(bitPosition < BitWidth && "Out of the bit-width range!");
 642   if ((*this)[bitPosition]) clear(bitPosition);
 643   else set(bitPosition);
 644   return *this;
 645 }
 646
 647 /// getMaxValue - This function returns the largest value
 648 /// for an APInt of the specified bit-width and if isSign == true,
 649 /// it should be largest signed value, otherwise unsigned value.
 650 APInt APInt::getMaxValue(uint32_t numBits, bool isSign) {
 651   APInt Result(numBits, 0);
 652   Result.set();
 653   if (isSign)
 654     Result.clear(numBits - 1);
 655   return Result;
 656 }
 657
 658 /// getMinValue - This function returns the smallest value for
 659 /// an APInt of the given bit-width and if isSign == true,
 660 /// it should be smallest signed value, otherwise zero.
 661 APInt APInt::getMinValue(uint32_t numBits, bool isSign) {
 662   APInt Result(numBits, 0);
 663   if (isSign)
 664     Result.set(numBits - 1);
 665   return Result;
 666 }
 667
 668 /// getAllOnesValue - This function returns an all-ones value for
 669 /// an APInt of the specified bit-width.
 670 APInt APInt::getAllOnesValue(uint32_t numBits) {
 671   return getMaxValue(numBits, false);
 672 }
 673
 674 /// getNullValue - This function creates an '0' value for an
 675 /// APInt of the specified bit-width.
 676 APInt APInt::getNullValue(uint32_t numBits) {
 677   return getMinValue(numBits, false);
 678 }
 679
 680 /// HiBits - This function returns the high "numBits" bits of this APInt.
 681 APInt APInt::getHiBits(uint32_t numBits) const {
 682   return APIntOps::lshr(*this, BitWidth - numBits);
 683 }
 684
 685 /// LoBits - This function returns the low "numBits" bits of this APInt.
 686 APInt APInt::getLoBits(uint32_t numBits) const {
 687   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
 688                         BitWidth - numBits);
 689 }
 690
 691 bool APInt::isPowerOf2() const {
 692   return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
 693 }
 694
 695 /// countLeadingZeros - This function is a APInt version corresponding to
 696 /// llvm/include/llvm/Support/MathExtras.h's function
 697 /// countLeadingZeros_{32, 64}. It performs platform optimal form of counting
 698 /// the number of zeros from the most significant bit to the first one bit.
 699 /// @returns numWord() * 64 if the value is zero.
 700 uint32_t APInt::countLeadingZeros() const {
 701   if (isSingleWord())
 702     return CountLeadingZeros_64(VAL) - (APINT_BITS_PER_WORD - BitWidth);
 703   uint32_t Count = 0;
 704   for (uint32_t i = getNumWords(); i > 0u; --i) {
 705     uint32_t tmp = CountLeadingZeros_64(pVal[i-1]);
 706     Count += tmp;
 707     if (tmp != APINT_BITS_PER_WORD)
 708       if (i == getNumWords())
 709         Count -= (APINT_BITS_PER_WORD - whichBit(BitWidth));
 710       break;
 711   }
 712   return Count;
 713 }
 714
 715 /// countTrailingZeros - This function is a APInt version corresponding to
 716 /// llvm/include/llvm/Support/MathExtras.h's function
 717 /// countTrailingZeros_{32, 64}. It performs platform optimal form of counting
 718 /// the number of zeros from the least significant bit to the first one bit.
 719 /// @returns numWord() * 64 if the value is zero.
 720 uint32_t APInt::countTrailingZeros() const {
 721   if (isSingleWord())
 722     return CountTrailingZeros_64(VAL);
 723   APInt Tmp( ~(*this) & ((*this) - APInt(BitWidth,1)) );
 724   return getNumWords() * APINT_BITS_PER_WORD - Tmp.countLeadingZeros();
 725 }
 726
 727 /// countPopulation - This function is a APInt version corresponding to
 728 /// llvm/include/llvm/Support/MathExtras.h's function
 729 /// countPopulation_{32, 64}. It counts the number of set bits in a value.
 730 /// @returns 0 if the value is zero.
 731 uint32_t APInt::countPopulation() const {
 732   if (isSingleWord())
 733     return CountPopulation_64(VAL);
 734   uint32_t Count = 0;
 735   for (uint32_t i = 0; i < getNumWords(); ++i)
 736     Count += CountPopulation_64(pVal[i]);
 737   return Count;
 738 }
 739
 740
 741 /// byteSwap - This function returns a byte-swapped representation of the
 742 /// this APInt.
 743 APInt APInt::byteSwap() const {
 744   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
 745   if (BitWidth == 16)
 746     return APInt(BitWidth, ByteSwap_16(VAL));
 747   else if (BitWidth == 32)
 748     return APInt(BitWidth, ByteSwap_32(VAL));
 749   else if (BitWidth == 48) {
 750     uint64_t Tmp1 = ((VAL >> 32) << 16) | (VAL & 0xFFFF);
 751     Tmp1 = ByteSwap_32(Tmp1);
 752     uint64_t Tmp2 = (VAL >> 16) & 0xFFFF;
 753     Tmp2 = ByteSwap_16(Tmp2);
 754     return
 755       APInt(BitWidth,
 756             (Tmp1 & 0xff) | ((Tmp1<<16) & 0xffff00000000ULL) | (Tmp2 << 16));
 757   } else if (BitWidth == 64)
 758     return APInt(BitWidth, ByteSwap_64(VAL));
 759   else {
 760     APInt Result(BitWidth, 0);
 761     char *pByte = (char*)Result.pVal;
 762     for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
 763       char Tmp = pByte[i];
 764       pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
 765       pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
 766     }
 767     return Result;
 768   }
 769 }
 770
 771 /// GreatestCommonDivisor - This function returns the greatest common
 772 /// divisor of the two APInt values using Enclid's algorithm.
 773 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
 774                                             const APInt& API2) {
 775   APInt A = API1, B = API2;
 776   while (!!B) {
 777     APInt T = B;
 778     B = APIntOps::urem(A, B);
 779     A = T;
 780   }
 781   return A;
 782 }
 783
 784 /// DoubleRoundToAPInt - This function convert a double value to
 785 /// a APInt value.
 786 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double) {
 787   union {
 788     double D;
 789     uint64_t I;
 790   } T;
 791   T.D = Double;
 792   bool isNeg = T.I >> 63;
 793   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
 794   if (exp < 0)
 795     return APInt(64ull, 0u);
 796   uint64_t mantissa = ((T.I << 12) >> 12) | (1ULL << 52);
 797   if (exp < 52)
 798     return isNeg ? -APInt(64u, mantissa >> (52 - exp)) :
 799                     APInt(64u, mantissa >> (52 - exp));
 800   APInt Tmp(exp + 1, mantissa);
 801   Tmp = Tmp.shl(exp - 52);
 802   return isNeg ? -Tmp : Tmp;
 803 }
 804
 805 /// RoundToDouble - This function convert this APInt to a double.
 806 /// The layout for double is as following (IEEE Standard 754):
 807 ///  --------------------------------------
 808 /// |  Sign    Exponent    Fraction    Bias |
 809 /// |-------------------------------------- |
 810 /// |  1[63]   11[62-52]   52[51-00]   1023 |
 811 ///  --------------------------------------
 812 double APInt::roundToDouble(bool isSigned) const {
 813
 814   // Handle the simple case where the value is contained in one uint64_t.
 815   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
 816     if (isSigned) {
 817       int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
 818       return double(sext);
 819     } else
 820       return double(VAL);
 821   }
 822
 823   // Determine if the value is negative.
 824   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
 825
 826   // Construct the absolute value if we're negative.
 827   APInt Tmp(isNeg ? -(*this) : (*this));
 828
 829   // Figure out how many bits we're using.
 830   uint32_t n = Tmp.getActiveBits();
 831
 832   // The exponent (without bias normalization) is just the number of bits
 833   // we are using. Note that the sign bit is gone since we constructed the
 834   // absolute value.
 835   uint64_t exp = n;
 836
 837   // Return infinity for exponent overflow
 838   if (exp > 1023) {
 839     if (!isSigned || !isNeg)
 840       return double(0x0.0p2047L); // positive infinity
 841     else
 842       return double(-0x0.0p2047L); // negative infinity
 843   }
 844   exp += 1023; // Increment for 1023 bias
 845
 846   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
 847   // extract the high 52 bits from the correct words in pVal.
 848   uint64_t mantissa;
 849   unsigned hiWord = whichWord(n-1);
 850   if (hiWord == 0) {
 851     mantissa = Tmp.pVal[0];
 852     if (n > 52)
 853       mantissa >>= n - 52; // shift down, we want the top 52 bits.
 854   } else {
 855     assert(hiWord > 0 && "huh?");
 856     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
 857     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
 858     mantissa = hibits | lobits;
 859   }
 860
 861   // The leading bit of mantissa is implicit, so get rid of it.
 862   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
 863   union {
 864     double D;
 865     uint64_t I;
 866   } T;
 867   T.I = sign | (exp << 52) | mantissa;
 868   return T.D;
 869 }
 870
 871 // Truncate to new width.
 872 void APInt::trunc(uint32_t width) {
 873   assert(width < BitWidth && "Invalid APInt Truncate request");
 874 }
 875
 876 // Sign extend to a new width.
 877 void APInt::sext(uint32_t width) {
 878   assert(width > BitWidth && "Invalid APInt SignExtend request");
 879 }
 880
 881 //  Zero extend to a new width.
 882 void APInt::zext(uint32_t width) {
 883   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
 884 }
 885
 886 /// Arithmetic right-shift this APInt by shiftAmt.
 887 /// @brief Arithmetic right-shift function.
 888 APInt APInt::ashr(uint32_t shiftAmt) const {
 889   APInt API(*this);
 890   if (API.isSingleWord())
 891     API.VAL =
 892       (((int64_t(API.VAL) << (APINT_BITS_PER_WORD - API.BitWidth)) >>
 893           (APINT_BITS_PER_WORD - API.BitWidth)) >> shiftAmt) &
 894       (~uint64_t(0UL) >> (APINT_BITS_PER_WORD - API.BitWidth));
 895   else {
 896     if (shiftAmt >= API.BitWidth) {
 897       memset(API.pVal, API[API.BitWidth-1] ? 1 : 0,
 898              (API.getNumWords()-1) * APINT_WORD_SIZE);
 899       API.pVal[API.getNumWords() - 1] =
 900         ~uint64_t(0UL) >>
 901           (APINT_BITS_PER_WORD - API.BitWidth % APINT_BITS_PER_WORD);
 902     } else {
 903       uint32_t i = 0;
 904       for (; i < API.BitWidth - shiftAmt; ++i)
 905         if (API[i+shiftAmt])
 906           API.set(i);
 907         else
 908           API.clear(i);
 909       for (; i < API.BitWidth; ++i)
 910         if (API[API.BitWidth-1])
 911           API.set(i);
 912         else API.clear(i);
 913     }
 914   }
 915   return API;
 916 }
 917
 918 /// Logical right-shift this APInt by shiftAmt.
 919 /// @brief Logical right-shift function.
 920 APInt APInt::lshr(uint32_t shiftAmt) const {
 921   APInt API(*this);
 922   if (API.isSingleWord())
 923     API.VAL >>= shiftAmt;
 924   else {
 925     if (shiftAmt >= API.BitWidth)
 926       memset(API.pVal, 0, API.getNumWords() * APINT_WORD_SIZE);
 927     uint32_t i = 0;
 928     for (i = 0; i < API.BitWidth - shiftAmt; ++i)
 929       if (API[i+shiftAmt]) API.set(i);
 930       else API.clear(i);
 931     for (; i < API.BitWidth; ++i)
 932       API.clear(i);
 933   }
 934   return API;
 935 }
 936
 937 /// Left-shift this APInt by shiftAmt.
 938 /// @brief Left-shift function.
 939 APInt APInt::shl(uint32_t shiftAmt) const {
 940   APInt API(*this);
 941   if (API.isSingleWord())
 942     API.VAL <<= shiftAmt;
 943   else if (shiftAmt >= API.BitWidth)
 944     memset(API.pVal, 0, API.getNumWords() * APINT_WORD_SIZE);
 945   else {
 946     if (uint32_t offset = shiftAmt / APINT_BITS_PER_WORD) {
 947       for (uint32_t i = API.getNumWords() - 1; i > offset - 1; --i)
 948         API.pVal[i] = API.pVal[i-offset];
 949       memset(API.pVal, 0, offset * APINT_WORD_SIZE);
 950     }
 951     shiftAmt %= APINT_BITS_PER_WORD;
 952     uint32_t i;
 953     for (i = API.getNumWords() - 1; i > 0; --i)
 954       API.pVal[i] = (API.pVal[i] << shiftAmt) |
 955                     (API.pVal[i-1] >> (APINT_BITS_PER_WORD - shiftAmt));
 956     API.pVal[i] <<= shiftAmt;
 957   }
 958   API.clearUnusedBits();
 959   return API;
 960 }
 961
 962 #if 0
 963 /// subMul - This function substracts x[len-1:0] * y from
 964 /// dest[offset+len-1:offset], and returns the most significant
 965 /// word of the product, minus the borrow-out from the subtraction.
 966 static uint32_t subMul(uint32_t dest[], uint32_t offset,
 967                         uint32_t x[], uint32_t len, uint32_t y) {
 968   uint64_t yl = (uint64_t) y & 0xffffffffL;
 969   uint32_t carry = 0;
 970   uint32_t j = 0;
 971   do {
 972     uint64_t prod = ((uint64_t) x[j] & 0xffffffffUL) * yl;
 973     uint32_t prod_low = (uint32_t) prod;
 974     uint32_t prod_high = (uint32_t) (prod >> 32);
 975     prod_low += carry;
 976     carry = (prod_low < carry ? 1 : 0) + prod_high;
 977     uint32_t x_j = dest[offset+j];
 978     prod_low = x_j - prod_low;
 979     if (prod_low > x_j) ++carry;
 980     dest[offset+j] = prod_low;
 981   } while (++j < len);
 982   return carry;
 983 }
 984
 985 /// unitDiv - This function divides N by D,
 986 /// and returns (remainder << 32) | quotient.
 987 /// Assumes (N >> 32) < D.
 988 static uint64_t unitDiv(uint64_t N, uint32_t D) {
 989   uint64_t q, r;                   // q: quotient, r: remainder.
 990   uint64_t a1 = N >> 32;           // a1: high 32-bit part of N.
 991   uint64_t a0 = N & 0xffffffffL;   // a0: low 32-bit part of N
 992   if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL)) {
 993       q = N / D;
 994       r = N % D;
 995   }
 996   else {
 997     // Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d
 998     uint64_t c = N - ((uint64_t) D << 31);
 999     // Divide (c1*2^32 + c0) by d
1000     q = c / D;
1001     r = c % D;
1002     // Add 2^31 to quotient
1003     q += 1 << 31;
1004   }
1005
1006   return (r << 32) | (q & 0xFFFFFFFFl);
1007 }
1008
1009 #endif
1010
1011 /// div - This is basically Knuth's formulation of the classical algorithm.
1012 /// Correspondance with Knuth's notation:
1013 /// Knuth's u[0:m+n] == zds[nx:0].
1014 /// Knuth's v[1:n] == y[ny-1:0]
1015 /// Knuth's n == ny.
1016 /// Knuth's m == nx-ny.
1017 /// Our nx == Knuth's m+n.
1018 /// Could be re-implemented using gmp's mpn_divrem:
1019 /// zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny).
1020
1021 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1022 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1023 /// variables here have the same names as in the algorithm. Comments explain
1024 /// the algorithm and any deviation from it.
1025 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1026                      uint32_t m, uint32_t n) {
1027   assert(u && "Must provide dividend");
1028   assert(v && "Must provide divisor");
1029   assert(q && "Must provide quotient");
1030   assert(n>1 && "n must be > 1");
1031
1032   // Knuth uses the value b as the base of the number system. In our case b
1033   // is 2^31 so we just set it to -1u.
1034   uint64_t b = uint64_t(1) << 32;
1035
1036   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1037   // u and v by d. Note that we have taken Knuth's advice here to use a power
1038   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1039   // 2 allows us to shift instead of multiply and it is easy to determine the
1040   // shift amount from the leading zeros.  We are basically normalizing the u
1041   // and v so that its high bits are shifted to the top of v's range without
1042   // overflow. Note that this can require an extra word in u so that u must
1043   // be of length m+n+1.
1044   uint32_t shift = CountLeadingZeros_32(v[n-1]);
1045   uint32_t v_carry = 0;
1046   uint32_t u_carry = 0;
1047   if (shift) {
1048     for (uint32_t i = 0; i < m+n; ++i) {
1049       uint32_t u_tmp = u[i] >> (32 - shift);
1050       u[i] = (u[i] << shift) | u_carry;
1051       u_carry = u_tmp;
1052     }
1053     for (uint32_t i = 0; i < n; ++i) {
1054       uint32_t v_tmp = v[i] >> (32 - shift);
1055       v[i] = (v[i] << shift) | v_carry;
1056       v_carry = v_tmp;
1057     }
1058   }
1059   u[m+n] = u_carry;
1060
1061   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
1062   int j = m;
1063   do {
1064     // D3. [Calculate q'.].
1065     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1066     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1067     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1068     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1069     // on v[n-2] determines at high speed most of the cases in which the trial
1070     // value qp is one too large, and it eliminates all cases where qp is two
1071     // too large.
1072     uint64_t qp = ((uint64_t(u[j+n]) << 32) | uint64_t(u[j+n-1])) / v[n-1];
1073     uint64_t rp = ((uint64_t(u[j+n]) << 32) | uint64_t(u[j+n-1])) % v[n-1];
1074     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1075       qp--;
1076       rp += v[n-1];
1077     }
1078     if (rp < b)
1079       if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1080         qp--;
1081         rp += v[n-1];
1082       }
1083
1084     // D4. [Multiply and subtract.] Replace u with u - q*v (for each word).
1085     uint32_t borrow = 0;
1086     for (uint32_t i = 0; i < n; i++) {
1087       uint32_t save = u[j+i];
1088       u[j+i] = uint64_t(u[j+i]) - (qp * v[i]) - borrow;
1089       if (u[j+i] > save) {
1090         borrow = 1;
1091         u[j+i+1] += b;
1092       } else {
1093         borrow = 0;
1094       }
1095     }
1096     if (borrow)
1097       u[j+n] += 1;
1098
1099     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1100     // negative, go to step D6; otherwise go on to step D7.
1101     q[j] = qp;
1102     if (borrow) {
1103       // D6. [Add back]. The probability that this step is necessary is very
1104       // small, on the order of only 2/b. Make sure that test data accounts for
1105       // this possibility. Decreate qj by 1 and add v[...] to u[...]. A carry
1106       // will occur to the left of u[j+n], and it should be ignored since it
1107       // cancels with the borrow that occurred in D4.
1108       uint32_t carry = 0;
1109       for (uint32_t i = 0; i < n; i++) {
1110         uint32_t save = u[j+i];
1111         u[j+i] += v[i] + carry;
1112         carry = u[j+i] < save;
1113       }
1114     }
1115
1116     // D7. [Loop on j.]  Decreate j by one. Now if j >= 0, go back to D3.
1117     j--;
1118   } while (j >= 0);
1119
1120   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1121   // remainder may be obtained by dividing u[...] by d. If r is non-null we
1122   // compute the remainder (urem uses this).
1123   if (r) {
1124     // The value d is expressed by the "shift" value above since we avoided
1125     // multiplication by d by using a shift left. So, all we have to do is
1126     // shift right here. In order to mak
1127     uint32_t mask = ~0u >> (32 - shift);
1128     uint32_t carry = 0;
1129     for (int i = n-1; i >= 0; i--) {
1130       uint32_t save = u[i] & mask;
1131       r[i] = (u[i] >> shift) | carry;
1132       carry = save;
1133     }
1134   }
1135 }
1136
1137 // This function makes calling KnuthDiv a little more convenient. It uses
1138 // APInt parameters instead of uint32_t* parameters. It can also divide APInt
1139 // values of different widths.
1140 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1141                    const APInt &RHS, uint32_t rhsWords,
1142                    APInt *Quotient, APInt *Remainder)
1143 {
1144   assert(lhsWords >= rhsWords && "Fractional result");
1145
1146   // First, compose the values into an array of 32-bit words instead of
1147   // 64-bit words. This is a necessity of both the "short division" algorithm
1148   // and the the Knuth "classical algorithm" which requires there to be native
1149   // operations for +, -, and * on an m bit value with an m*2 bit result. We
1150   // can't use 64-bit operands here because we don't have native results of
1151   // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1152   // work on large-endian machines.
1153   uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1154   uint32_t n = rhsWords * 2;
1155   uint32_t m = (lhsWords * 2) - n;
1156   // FIXME: allocate space on stack if m and n are sufficiently small.
1157   uint32_t *U = new uint32_t[m + n + 1];
1158   memset(U, 0, (m+n+1)*sizeof(uint32_t));
1159   for (unsigned i = 0; i < lhsWords; ++i) {
1160     uint64_t tmp = (lhsWords == 1 ? LHS.VAL : LHS.pVal[i]);
1161     U[i * 2] = tmp & mask;
1162     U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1163   }
1164   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1165
1166   uint32_t *V = new uint32_t[n];
1167   memset(V, 0, (n)*sizeof(uint32_t));
1168   for (unsigned i = 0; i < rhsWords; ++i) {
1169     uint64_t tmp = (rhsWords == 1 ? RHS.VAL : RHS.pVal[i]);
1170     V[i * 2] = tmp & mask;
1171     V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1172   }
1173
1174   // Set up the quotient and remainder
1175   uint32_t *Q = new uint32_t[m+n];
1176   memset(Q, 0, (m+n) * sizeof(uint32_t));
1177   uint32_t *R = 0;
1178   if (Remainder) {
1179     R = new uint32_t[n];
1180     memset(R, 0, n * sizeof(uint32_t));
1181   }
1182
1183   // Now, adjust m and n for the Knuth division. n is the number of words in
1184   // the divisor. m is the number of words by which the dividend exceeds the
1185   // divisor (i.e. m+n is the length of the dividend). These sizes must not
1186   // contain any zero words or the Knuth algorithm fails.
1187   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1188     n--;
1189     m++;
1190   }
1191   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1192     m--;
1193
1194   // If we're left with only a single word for the divisor, Knuth doesn't work
1195   // so we implement the short division algorithm here. This is much simpler
1196   // and faster because we are certain that we can divide a 64-bit quantity
1197   // by a 32-bit quantity at hardware speed and short division is simply a
1198   // series of such operations. This is just like doing short division but we
1199   // are using base 2^32 instead of base 10.
1200   assert(n != 0 && "Divide by zero?");
1201   if (n == 1) {
1202     uint32_t divisor = V[0];
1203     uint32_t remainder = 0;
1204     for (int i = m+n-1; i >= 0; i--) {
1205       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1206       if (partial_dividend == 0) {
1207         Q[i] = 0;
1208         remainder = 0;
1209       } else if (partial_dividend < divisor) {
1210         Q[i] = 0;
1211         remainder = partial_dividend;
1212       } else if (partial_dividend == divisor) {
1213         Q[i] = 1;
1214         remainder = 0;
1215       } else {
1216         Q[i] = partial_dividend / divisor;
1217         remainder = partial_dividend - (Q[i] * divisor);
1218       }
1219     }
1220     if (R)
1221       R[0] = remainder;
1222   } else {
1223     // Now we're ready to invoke the Knuth classical divide algorithm. In this
1224     // case n > 1.
1225     KnuthDiv(U, V, Q, R, m, n);
1226   }
1227
1228   // If the caller wants the quotient
1229   if (Quotient) {
1230     // Set up the Quotient value's memory.
1231     if (Quotient->BitWidth != LHS.BitWidth) {
1232       if (Quotient->isSingleWord())
1233         Quotient->VAL = 0;
1234       else
1235         delete Quotient->pVal;
1236       Quotient->BitWidth = LHS.BitWidth;
1237       if (!Quotient->isSingleWord())
1238         Quotient->pVal = getClearedMemory(lhsWords);
1239     } else
1240       Quotient->clear();
1241
1242     // The quotient is in Q. Reconstitute the quotient into Quotient's low
1243     // order words.
1244     if (lhsWords == 1) {
1245       uint64_t tmp =
1246         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1247       if (Quotient->isSingleWord())
1248         Quotient->VAL = tmp;
1249       else
1250         Quotient->pVal[0] = tmp;
1251     } else {
1252       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1253       for (unsigned i = 0; i < lhsWords; ++i)
1254         Quotient->pVal[i] =
1255           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1256     }
1257   }
1258
1259   // If the caller wants the remainder
1260   if (Remainder) {
1261     // Set up the Remainder value's memory.
1262     if (Remainder->BitWidth != RHS.BitWidth) {
1263       if (Remainder->isSingleWord())
1264         Remainder->VAL = 0;
1265       else
1266         delete Remainder->pVal;
1267       Remainder->BitWidth = RHS.BitWidth;
1268       if (!Remainder->isSingleWord())
1269         Remainder->pVal = getClearedMemory(rhsWords);
1270     } else
1271       Remainder->clear();
1272
1273     // The remainder is in R. Reconstitute the remainder into Remainder's low
1274     // order words.
1275     if (rhsWords == 1) {
1276       uint64_t tmp =
1277         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1278       if (Remainder->isSingleWord())
1279         Remainder->VAL = tmp;
1280       else
1281         Remainder->pVal[0] = tmp;
1282     } else {
1283       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1284       for (unsigned i = 0; i < rhsWords; ++i)
1285         Remainder->pVal[i] =
1286           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1287     }
1288   }
1289
1290   // Clean up the memory we allocated.
1291   delete [] U;
1292   delete [] V;
1293   delete [] Q;
1294   delete [] R;
1295 }
1296
1297 /// Unsigned divide this APInt by APInt RHS.
1298 /// @brief Unsigned division function for APInt.
1299 APInt APInt::udiv(const APInt& RHS) const {
1300   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1301
1302   // First, deal with the easy case
1303   if (isSingleWord()) {
1304     assert(RHS.VAL != 0 && "Divide by zero?");
1305     return APInt(BitWidth, VAL / RHS.VAL);
1306   }
1307
1308   // Get some facts about the LHS and RHS number of bits and words
1309   uint32_t rhsBits = RHS.getActiveBits();
1310   uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1311   assert(rhsWords && "Divided by zero???");
1312   uint32_t lhsBits = this->getActiveBits();
1313   uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1314
1315   // Make a temporary to hold the result
1316   APInt Result(*this);
1317
1318   // Deal with some degenerate cases
1319   if (!lhsWords)
1320     return Result; // 0 / X == 0
1321   else if (lhsWords < rhsWords || Result.ult(RHS)) {
1322     // X / Y with X < Y == 0
1323     memset(Result.pVal, 0, Result.getNumWords() * APINT_WORD_SIZE);
1324     return Result;
1325   } else if (Result == RHS) {
1326     // X / X == 1
1327     memset(Result.pVal, 0, Result.getNumWords() * APINT_WORD_SIZE);
1328     Result.pVal[0] = 1;
1329     return Result;
1330   } else if (lhsWords == 1 && rhsWords == 1) {
1331     // All high words are zero, just use native divide
1332     Result.pVal[0] /= RHS.pVal[0];
1333     return Result;
1334   }
1335
1336   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1337   APInt Quotient(1,0); // to hold result.
1338   divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1339   return Quotient;
1340 }
1341
1342 /// Unsigned remainder operation on APInt.
1343 /// @brief Function for unsigned remainder operation.
1344 APInt APInt::urem(const APInt& RHS) const {
1345   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1346   if (isSingleWord()) {
1347     assert(RHS.VAL != 0 && "Remainder by zero?");
1348     return APInt(BitWidth, VAL % RHS.VAL);
1349   }
1350
1351   // Make a temporary to hold the result
1352   APInt Result(*this);
1353
1354   // Get some facts about the RHS
1355   uint32_t rhsBits = RHS.getActiveBits();
1356   uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1357   assert(rhsWords && "Performing remainder operation by zero ???");
1358
1359   // Get some facts about the LHS
1360   uint32_t lhsBits = Result.getActiveBits();
1361   uint32_t lhsWords = !lhsBits ? 0 : (Result.whichWord(lhsBits - 1) + 1);
1362
1363   // Check the degenerate cases
1364   if (lhsWords == 0) {
1365     // 0 % Y == 0
1366     memset(Result.pVal, 0, Result.getNumWords() * APINT_WORD_SIZE);
1367     return Result;
1368   } else if (lhsWords < rhsWords || Result.ult(RHS)) {
1369     // X % Y == X iff X < Y
1370     return Result;
1371   } else if (Result == RHS) {
1372     // X % X == 0;
1373     memset(Result.pVal, 0, Result.getNumWords() * APINT_WORD_SIZE);
1374     return Result;
1375   } else if (lhsWords == 1) {
1376     // All high words are zero, just use native remainder
1377     Result.pVal[0] %=  RHS.pVal[0];
1378     return Result;
1379   }
1380
1381   // We have to compute it the hard way. Invoke the Knute divide algorithm.
1382   APInt Remainder(1,0);
1383   divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1384   return Remainder;
1385 }
1386
1387 /// @brief Converts a char array into an integer.
1388 void APInt::fromString(uint32_t numbits, const char *StrStart, uint32_t slen,
1389                        uint8_t radix) {
1390   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1391          "Radix should be 2, 8, 10, or 16!");
1392   assert(StrStart && "String is null?");
1393   uint32_t size = 0;
1394   // If the radix is a power of 2, read the input
1395   // from most significant to least significant.
1396   if ((radix & (radix - 1)) == 0) {
1397     uint32_t nextBitPos = 0;
1398     uint32_t bits_per_digit = radix / 8 + 2;
1399     uint64_t resDigit = 0;
1400     BitWidth = slen * bits_per_digit;
1401     if (getNumWords() > 1)
1402       pVal = getMemory(getNumWords());
1403     for (int i = slen - 1; i >= 0; --i) {
1404       uint64_t digit = StrStart[i] - '0';
1405       resDigit |= digit << nextBitPos;
1406       nextBitPos += bits_per_digit;
1407       if (nextBitPos >= APINT_BITS_PER_WORD) {
1408         if (isSingleWord()) {
1409           VAL = resDigit;
1410            break;
1411         }
1412         pVal[size++] = resDigit;
1413         nextBitPos -= APINT_BITS_PER_WORD;
1414         resDigit = digit >> (bits_per_digit - nextBitPos);
1415       }
1416     }
1417     if (!isSingleWord() && size <= getNumWords())
1418       pVal[size] = resDigit;
1419   } else {   // General case.  The radix is not a power of 2.
1420     // For 10-radix, the max value of 64-bit integer is 18446744073709551615,
1421     // and its digits number is 20.
1422     const uint32_t chars_per_word = 20;
1423     if (slen < chars_per_word ||
1424         (slen == chars_per_word &&             // In case the value <= 2^64 - 1
1425          strcmp(StrStart, "18446744073709551615") <= 0)) {
1426       BitWidth = APINT_BITS_PER_WORD;
1427       VAL = strtoull(StrStart, 0, 10);
1428     } else { // In case the value > 2^64 - 1
1429       BitWidth = (slen / chars_per_word + 1) * APINT_BITS_PER_WORD;
1430       pVal = getClearedMemory(getNumWords());
1431       uint32_t str_pos = 0;
1432       while (str_pos < slen) {
1433         uint32_t chunk = slen - str_pos;
1434         if (chunk > chars_per_word - 1)
1435           chunk = chars_per_word - 1;
1436         uint64_t resDigit = StrStart[str_pos++] - '0';
1437         uint64_t big_base = radix;
1438         while (--chunk > 0) {
1439           resDigit = resDigit * radix + StrStart[str_pos++] - '0';
1440           big_base *= radix;
1441         }
1442
1443         uint64_t carry;
1444         if (!size)
1445           carry = resDigit;
1446         else {
1447           carry = mul_1(pVal, pVal, size, big_base);
1448           carry += add_1(pVal, pVal, size, resDigit);
1449         }
1450
1451         if (carry) pVal[size++] = carry;
1452       }
1453     }
1454   }
1455 }
1456
1457 /// to_string - This function translates the APInt into a string.
1458 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1459   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1460          "Radix should be 2, 8, 10, or 16!");
1461   static const char *digits[] = {
1462     "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1463   };
1464   std::string result;
1465   uint32_t bits_used = getActiveBits();
1466   if (isSingleWord()) {
1467     char buf[65];
1468     const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1469        (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1470     if (format) {
1471       if (wantSigned) {
1472         int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1473                            (APINT_BITS_PER_WORD-BitWidth);
1474         sprintf(buf, format, sextVal);
1475       } else
1476         sprintf(buf, format, VAL);
1477     } else {
1478       memset(buf, 0, 65);
1479       uint64_t v = VAL;
1480       while (bits_used) {
1481         uint32_t bit = v & 1;
1482         bits_used--;
1483         buf[bits_used] = digits[bit][0];
1484         v >>=1;
1485       }
1486     }
1487     result = buf;
1488     return result;
1489   }
1490
1491   if (radix != 10) {
1492     uint64_t mask = radix - 1;
1493     uint32_t shift = (radix == 16 ? 4 : radix  == 8 ? 3 : 1);
1494     uint32_t nibbles = APINT_BITS_PER_WORD / shift;
1495     for (uint32_t i = 0; i < getNumWords(); ++i) {
1496       uint64_t value = pVal[i];
1497       for (uint32_t j = 0; j < nibbles; ++j) {
1498         result.insert(0, digits[ value & mask ]);
1499         value >>= shift;
1500       }
1501     }
1502     return result;
1503   }
1504
1505   APInt tmp(*this);
1506   APInt divisor(4, radix);
1507   APInt zero(tmp.getBitWidth(), 0);
1508   size_t insert_at = 0;
1509   if (wantSigned && tmp[BitWidth-1]) {
1510     // They want to print the signed version and it is a negative value
1511     // Flip the bits and add one to turn it into the equivalent positive
1512     // value and put a '-' in the result.
1513     tmp.flip();
1514     tmp++;
1515     result = "-";
1516     insert_at = 1;
1517   }
1518   if (tmp == 0)
1519     result = "0";
1520   else while (tmp.ne(zero)) {
1521     APInt APdigit(1,0);
1522     divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), 0, &APdigit);
1523     uint32_t digit = APdigit.getValue();
1524     assert(digit < radix && "urem failed");
1525     result.insert(insert_at,digits[digit]);
1526     APInt tmp2(tmp.getBitWidth(), 0);
1527     divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 0);
1528     tmp = tmp2;
1529   }
1530
1531   return result;
1532 }
1533