lib/Support/APInt.cpp

//===-- APInt.cpp - Implement APInt class ---------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a class to represent arbitrary precision integer
// constant values and provide a variety of arithmetic operations on them.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "apint"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cmath>
#include <limits>
#include <cstring>
#include <cstdlib>
using namespace llvm;

/// A utility function for allocating memory, checking for allocation failures,
/// and ensuring the contents are zeroed.
inline static uint64_t* getClearedMemory(unsigned numWords) {
  uint64_t * result = new uint64_t[numWords];
  assert(result && "APInt memory allocation fails!");
  memset(result, 0, numWords * sizeof(uint64_t));
  return result;
}

/// A utility function for allocating memory and checking for allocation 
/// failure.  The content is not zeroed.
inline static uint64_t* getMemory(unsigned numWords) {
  uint64_t * result = new uint64_t[numWords];
  assert(result && "APInt memory allocation fails!");
  return result;
}

void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
  pVal = getClearedMemory(getNumWords());
  pVal[0] = val;
  if (isSigned && int64_t(val) < 0) 
    for (unsigned i = 1; i < getNumWords(); ++i)
      pVal[i] = -1ULL;
}

void APInt::initSlowCase(const APInt& that) {
  pVal = getMemory(getNumWords());
  memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
}


APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
  : BitWidth(numBits), VAL(0) {
  assert(BitWidth && "bitwidth too small");
  assert(bigVal && "Null pointer detected!");
  if (isSingleWord())
    VAL = bigVal[0];
  else {
    // Get memory, cleared to 0
    pVal = getClearedMemory(getNumWords());
    // Calculate the number of words to copy
    unsigned words = std::min<unsigned>(numWords, getNumWords());
    // Copy the words from bigVal to pVal
    memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
  }
  // Make sure unused high bits are cleared
  clearUnusedBits();
}

APInt::APInt(unsigned numbits, const char StrStart[], unsigned slen,
             uint8_t radix) 
  : BitWidth(numbits), VAL(0) {
  assert(BitWidth && "bitwidth too small");
  fromString(numbits, StrStart, slen, radix);
}

APInt& APInt::AssignSlowCase(const APInt& RHS) {
  // Don't do anything for X = X
  if (this == &RHS)
    return *this;

  if (BitWidth == RHS.getBitWidth()) {
    // assume same bit-width single-word case is already handled
    assert(!isSingleWord());
    memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
    return *this;
  }

  if (isSingleWord()) {
    // assume case where both are single words is already handled
    assert(!RHS.isSingleWord());
    VAL = 0;
    pVal = getMemory(RHS.getNumWords());
    memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
  } else if (getNumWords() == RHS.getNumWords()) 
    memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
  else if (RHS.isSingleWord()) {
    delete [] pVal;
    VAL = RHS.VAL;
  } else {
    delete [] pVal;
    pVal = getMemory(RHS.getNumWords());
    memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
  }
  BitWidth = RHS.BitWidth;
  return clearUnusedBits();
}

APInt& APInt::operator=(uint64_t RHS) {
  if (isSingleWord()) 
    VAL = RHS;
  else {
    pVal[0] = RHS;
    memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
  }
  return clearUnusedBits();
}

/// Profile - This method 'profiles' an APInt for use with FoldingSet.
void APInt::Profile(FoldingSetNodeID& ID) const {
  ID.AddInteger(BitWidth);
  
  if (isSingleWord()) {
    ID.AddInteger(VAL);
    return;
  }

  unsigned NumWords = getNumWords();
  for (unsigned i = 0; i < NumWords; ++i)
    ID.AddInteger(pVal[i]);
}

/// add_1 - This function adds a single "digit" integer, y, to the multiple 
/// "digit" integer array,  x[]. x[] is modified to reflect the addition and
/// 1 is returned if there is a carry out, otherwise 0 is returned.
/// @returns the carry of the addition.
static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
  for (unsigned i = 0; i < len; ++i) {
    dest[i] = y + x[i];
    if (dest[i] < y)
      y = 1; // Carry one to next digit.
    else {
      y = 0; // No need to carry so exit early
      break;
    }
  }
  return y;
}

/// @brief Prefix increment operator. Increments the APInt by one.
APInt& APInt::operator++() {
  if (isSingleWord()) 
    ++VAL;
  else
    add_1(pVal, pVal, getNumWords(), 1);
  return clearUnusedBits();
}

/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from 
/// the multi-digit integer array, x[], propagating the borrowed 1 value until 
/// no further borrowing is neeeded or it runs out of "digits" in x.  The result
/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
/// In other words, if y > x then this function returns 1, otherwise 0.
/// @returns the borrow out of the subtraction
static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
  for (unsigned i = 0; i < len; ++i) {
    uint64_t X = x[i];
    x[i] -= y;
    if (y > X) 
      y = 1;  // We have to "borrow 1" from next "digit"
    else {
      y = 0;  // No need to borrow
      break;  // Remaining digits are unchanged so exit early
    }
  }
  return bool(y);
}

/// @brief Prefix decrement operator. Decrements the APInt by one.
APInt& APInt::operator--() {
  if (isSingleWord()) 
    --VAL;
  else
    sub_1(pVal, getNumWords(), 1);
  return clearUnusedBits();
}

/// add - This function adds the integer array x to the integer array Y and
/// places the result in dest. 
/// @returns the carry out from the addition
/// @brief General addition of 64-bit integer arrays
static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, 
                unsigned len) {
  bool carry = false;
  for (unsigned i = 0; i< len; ++i) {
    uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
    dest[i] = x[i] + y[i] + carry;
    carry = dest[i] < limit || (carry && dest[i] == limit);
  }
  return carry;
}

/// Adds the RHS APint to this APInt.
/// @returns this, after addition of RHS.
/// @brief Addition assignment operator. 
APInt& APInt::operator+=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) 
    VAL += RHS.VAL;
  else {
    add(pVal, pVal, RHS.pVal, getNumWords());
  }
  return clearUnusedBits();
}

/// Subtracts the integer array y from the integer array x 
/// @returns returns the borrow out.
/// @brief Generalized subtraction of 64-bit integer arrays.
static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, 
                unsigned len) {
  bool borrow = false;
  for (unsigned i = 0; i < len; ++i) {
    uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
    borrow = y[i] > x_tmp || (borrow && x[i] == 0);
    dest[i] = x_tmp - y[i];
  }
  return borrow;
}

/// Subtracts the RHS APInt from this APInt
/// @returns this, after subtraction
/// @brief Subtraction assignment operator. 
APInt& APInt::operator-=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) 
    VAL -= RHS.VAL;
  else
    sub(pVal, pVal, RHS.pVal, getNumWords());
  return clearUnusedBits();
}

/// Multiplies an integer array, x by a a uint64_t integer and places the result
/// into dest. 
/// @returns the carry out of the multiplication.
/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
  // Split y into high 32-bit part (hy)  and low 32-bit part (ly)
  uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
  uint64_t carry = 0;

  // For each digit of x.
  for (unsigned i = 0; i < len; ++i) {
    // Split x into high and low words
    uint64_t lx = x[i] & 0xffffffffULL;
    uint64_t hx = x[i] >> 32;
    // hasCarry - A flag to indicate if there is a carry to the next digit.
    // hasCarry == 0, no carry
    // hasCarry == 1, has carry
    // hasCarry == 2, no carry and the calculation result == 0.
    uint8_t hasCarry = 0;
    dest[i] = carry + lx * ly;
    // Determine if the add above introduces carry.
    hasCarry = (dest[i] < carry) ? 1 : 0;
    carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
    // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 
    // (2^32 - 1) + 2^32 = 2^64.
    hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);

    carry += (lx * hy) & 0xffffffffULL;
    dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
    carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 
            (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
  }
  return carry;
}

/// Multiplies integer array x by integer array y and stores the result into 
/// the integer array dest. Note that dest's size must be >= xlen + ylen.
/// @brief Generalized multiplicate of integer arrays.
static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
                unsigned ylen) {
  dest[xlen] = mul_1(dest, x, xlen, y[0]);
  for (unsigned i = 1; i < ylen; ++i) {
    uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
    uint64_t carry = 0, lx = 0, hx = 0;
    for (unsigned j = 0; j < xlen; ++j) {
      lx = x[j] & 0xffffffffULL;
      hx = x[j] >> 32;
      // hasCarry - A flag to indicate if has carry.
      // hasCarry == 0, no carry
      // hasCarry == 1, has carry
      // hasCarry == 2, no carry and the calculation result == 0.
      uint8_t hasCarry = 0;
      uint64_t resul = carry + lx * ly;
      hasCarry = (resul < carry) ? 1 : 0;
      carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
      hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);

      carry += (lx * hy) & 0xffffffffULL;
      resul = (carry << 32) | (resul & 0xffffffffULL);
      dest[i+j] += resul;
      carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
              (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 
              ((lx * hy) >> 32) + hx * hy;
    }
    dest[i+xlen] = carry;
  }
}

APInt& APInt::operator*=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) {
    VAL *= RHS.VAL;
    clearUnusedBits();
    return *this;
  }

  // Get some bit facts about LHS and check for zero
  unsigned lhsBits = getActiveBits();
  unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
  if (!lhsWords) 
    // 0 * X ===> 0
    return *this;

  // Get some bit facts about RHS and check for zero
  unsigned rhsBits = RHS.getActiveBits();
  unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
  if (!rhsWords) {
    // X * 0 ===> 0
    clear();
    return *this;
  }

  // Allocate space for the result
  unsigned destWords = rhsWords + lhsWords;
  uint64_t *dest = getMemory(destWords);

  // Perform the long multiply
  mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);

  // Copy result back into *this
  clear();
  unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
  memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);

  // delete dest array and return
  delete[] dest;
  return *this;
}

APInt& APInt::operator&=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) {
    VAL &= RHS.VAL;
    return *this;
  }
  unsigned numWords = getNumWords();
  for (unsigned i = 0; i < numWords; ++i)
    pVal[i] &= RHS.pVal[i];
  return *this;
}

APInt& APInt::operator|=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) {
    VAL |= RHS.VAL;
    return *this;
  }
  unsigned numWords = getNumWords();
  for (unsigned i = 0; i < numWords; ++i)
    pVal[i] |= RHS.pVal[i];
  return *this;
}

APInt& APInt::operator^=(const APInt& RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) {
    VAL ^= RHS.VAL;
    this->clearUnusedBits();
    return *this;
  } 
  unsigned numWords = getNumWords();
  for (unsigned i = 0; i < numWords; ++i)
    pVal[i] ^= RHS.pVal[i];
  return clearUnusedBits();
}

APInt APInt::AndSlowCase(const APInt& RHS) const {
  unsigned numWords = getNumWords();
  uint64_t* val = getMemory(numWords);
  for (unsigned i = 0; i < numWords; ++i)
    val[i] = pVal[i] & RHS.pVal[i];
  return APInt(val, getBitWidth());
}

APInt APInt::OrSlowCase(const APInt& RHS) const {
  unsigned numWords = getNumWords();
  uint64_t *val = getMemory(numWords);
  for (unsigned i = 0; i < numWords; ++i)
    val[i] = pVal[i] | RHS.pVal[i];
  return APInt(val, getBitWidth());
}

APInt APInt::XorSlowCase(const APInt& RHS) const {
  unsigned numWords = getNumWords();
  uint64_t *val = getMemory(numWords);
  for (unsigned i = 0; i < numWords; ++i)
    val[i] = pVal[i] ^ RHS.pVal[i];

  // 0^0==1 so clear the high bits in case they got set.
  return APInt(val, getBitWidth()).clearUnusedBits();
}

bool APInt::operator !() const {
  if (isSingleWord())
    return !VAL;

  for (unsigned i = 0; i < getNumWords(); ++i)
    if (pVal[i]) 
      return false;
  return true;
}

APInt APInt::operator*(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord())
    return APInt(BitWidth, VAL * RHS.VAL);
  APInt Result(*this);
  Result *= RHS;
  return Result.clearUnusedBits();
}

APInt APInt::operator+(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord())
    return APInt(BitWidth, VAL + RHS.VAL);
  APInt Result(BitWidth, 0);
  add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
  return Result.clearUnusedBits();
}

APInt APInt::operator-(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord())
    return APInt(BitWidth, VAL - RHS.VAL);
  APInt Result(BitWidth, 0);
  sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
  return Result.clearUnusedBits();
}

bool APInt::operator[](unsigned bitPosition) const {
  return (maskBit(bitPosition) & 
          (isSingleWord() ?  VAL : pVal[whichWord(bitPosition)])) != 0;
}

bool APInt::EqualSlowCase(const APInt& RHS) const {
  // Get some facts about the number of bits used in the two operands.
  unsigned n1 = getActiveBits();
  unsigned n2 = RHS.getActiveBits();

  // If the number of bits isn't the same, they aren't equal
  if (n1 != n2) 
    return false;

  // If the number of bits fits in a word, we only need to compare the low word.
  if (n1 <= APINT_BITS_PER_WORD)
    return pVal[0] == RHS.pVal[0];

  // Otherwise, compare everything
  for (int i = whichWord(n1 - 1); i >= 0; --i)
    if (pVal[i] != RHS.pVal[i]) 
      return false;
  return true;
}

bool APInt::EqualSlowCase(uint64_t Val) const {
  unsigned n = getActiveBits();
  if (n <= APINT_BITS_PER_WORD)
    return pVal[0] == Val;
  else
    return false;
}

bool APInt::ult(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
  if (isSingleWord())
    return VAL < RHS.VAL;

  // Get active bit length of both operands
  unsigned n1 = getActiveBits();
  unsigned n2 = RHS.getActiveBits();

  // If magnitude of LHS is less than RHS, return true.
  if (n1 < n2)
    return true;

  // If magnitude of RHS is greather than LHS, return false.
  if (n2 < n1)
    return false;

  // If they bot fit in a word, just compare the low order word
  if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
    return pVal[0] < RHS.pVal[0];

  // Otherwise, compare all words
  unsigned topWord = whichWord(std::max(n1,n2)-1);
  for (int i = topWord; i >= 0; --i) {
    if (pVal[i] > RHS.pVal[i]) 
      return false;
    if (pVal[i] < RHS.pVal[i]) 
      return true;
  }
  return false;
}

bool APInt::slt(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
  if (isSingleWord()) {
    int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
    int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
    return lhsSext < rhsSext;
  }

  APInt lhs(*this);
  APInt rhs(RHS);
  bool lhsNeg = isNegative();
  bool rhsNeg = rhs.isNegative();
  if (lhsNeg) {
    // Sign bit is set so perform two's complement to make it positive
    lhs.flip();
    lhs++;
  }
  if (rhsNeg) {
    // Sign bit is set so perform two's complement to make it positive
    rhs.flip();
    rhs++;
  }

  // Now we have unsigned values to compare so do the comparison if necessary
  // based on the negativeness of the values.
  if (lhsNeg)
    if (rhsNeg)
      return lhs.ugt(rhs);
    else
      return true;
  else if (rhsNeg)
    return false;
  else 
    return lhs.ult(rhs);
}

APInt& APInt::set(unsigned bitPosition) {
  if (isSingleWord()) 
    VAL |= maskBit(bitPosition);
  else 
    pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
  return *this;
}

/// Set the given bit to 0 whose position is given as "bitPosition".
/// @brief Set a given bit to 0.
APInt& APInt::clear(unsigned bitPosition) {
  if (isSingleWord()) 
    VAL &= ~maskBit(bitPosition);
  else 
    pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
  return *this;
}

/// @brief Toggle every bit to its opposite value.

/// Toggle a given bit to its opposite value whose position is given 
/// as "bitPosition".
/// @brief Toggles a given bit to its opposite value.
APInt& APInt::flip(unsigned bitPosition) {
  assert(bitPosition < BitWidth && "Out of the bit-width range!");
  if ((*this)[bitPosition]) clear(bitPosition);
  else set(bitPosition);
  return *this;
}

unsigned APInt::getBitsNeeded(const char* str, unsigned slen, uint8_t radix) {
  assert(str != 0 && "Invalid value string");
  assert(slen > 0 && "Invalid string length");

  // Each computation below needs to know if its negative
  unsigned isNegative = str[0] == '-';
  if (isNegative) {
    slen--;
    str++;
  }
  // For radixes of power-of-two values, the bits required is accurately and
  // easily computed
  if (radix == 2)
    return slen + isNegative;
  if (radix == 8)
    return slen * 3 + isNegative;
  if (radix == 16)
    return slen * 4 + isNegative;

  // Otherwise it must be radix == 10, the hard case
  assert(radix == 10 && "Invalid radix");

  // This is grossly inefficient but accurate. We could probably do something
  // with a computation of roughly slen*64/20 and then adjust by the value of
  // the first few digits. But, I'm not sure how accurate that could be.

  // Compute a sufficient number of bits that is always large enough but might
  // be too large. This avoids the assertion in the constructor.
  unsigned sufficient = slen*64/18;

  // Convert to the actual binary value.
  APInt tmp(sufficient, str, slen, radix);

  // Compute how many bits are required.
  return isNegative + tmp.logBase2() + 1;
}

uint64_t APInt::getHashValue() const {
  // Put the bit width into the low order bits.
  uint64_t hash = BitWidth;

  // Add the sum of the words to the hash.
  if (isSingleWord())
    hash += VAL << 6; // clear separation of up to 64 bits
  else
    for (unsigned i = 0; i < getNumWords(); ++i)
      hash += pVal[i] << 6; // clear sepration of up to 64 bits
  return hash;
}

/// HiBits - This function returns the high "numBits" bits of this APInt.
APInt APInt::getHiBits(unsigned numBits) const {
  return APIntOps::lshr(*this, BitWidth - numBits);
}

/// LoBits - This function returns the low "numBits" bits of this APInt.
APInt APInt::getLoBits(unsigned numBits) const {
  return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), 
                        BitWidth - numBits);
}

bool APInt::isPowerOf2() const {
  return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
}

unsigned APInt::countLeadingZerosSlowCase() const {
  unsigned Count = 0;
  for (unsigned i = getNumWords(); i > 0u; --i) {
    if (pVal[i-1] == 0)
      Count += APINT_BITS_PER_WORD;
    else {
      Count += CountLeadingZeros_64(pVal[i-1]);
      break;
    }
  }
  unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
  if (remainder)
    Count -= APINT_BITS_PER_WORD - remainder;
  return std::min(Count, BitWidth);
}

static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
  unsigned Count = 0;
  if (skip)
    V <<= skip;
  while (V && (V & (1ULL << 63))) {
    Count++;
    V <<= 1;
  }
  return Count;
}

unsigned APInt::countLeadingOnes() const {
  if (isSingleWord())
    return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);

  unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
  unsigned shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
  int i = getNumWords() - 1;
  unsigned Count = countLeadingOnes_64(pVal[i], shift);
  if (Count == highWordBits) {
    for (i--; i >= 0; --i) {
      if (pVal[i] == -1ULL)
        Count += APINT_BITS_PER_WORD;
      else {
        Count += countLeadingOnes_64(pVal[i], 0);
        break;
      }
    }
  }
  return Count;
}

unsigned APInt::countTrailingZeros() const {
  if (isSingleWord())
    return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
  unsigned Count = 0;
  unsigned i = 0;
  for (; i < getNumWords() && pVal[i] == 0; ++i)
    Count += APINT_BITS_PER_WORD;
  if (i < getNumWords())
    Count += CountTrailingZeros_64(pVal[i]);
  return std::min(Count, BitWidth);
}

unsigned APInt::countTrailingOnesSlowCase() const {
  unsigned Count = 0;
  unsigned i = 0;
  for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
    Count += APINT_BITS_PER_WORD;
  if (i < getNumWords())
    Count += CountTrailingOnes_64(pVal[i]);
  return std::min(Count, BitWidth);
}

unsigned APInt::countPopulationSlowCase() const {
  unsigned Count = 0;
  for (unsigned i = 0; i < getNumWords(); ++i)
    Count += CountPopulation_64(pVal[i]);
  return Count;
}

APInt APInt::byteSwap() const {
  assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
  if (BitWidth == 16)
    return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
  else if (BitWidth == 32)
    return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
  else if (BitWidth == 48) {
    unsigned Tmp1 = unsigned(VAL >> 16);
    Tmp1 = ByteSwap_32(Tmp1);
    uint16_t Tmp2 = uint16_t(VAL);
    Tmp2 = ByteSwap_16(Tmp2);
    return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
  } else if (BitWidth == 64)
    return APInt(BitWidth, ByteSwap_64(VAL));
  else {
    APInt Result(BitWidth, 0);
    char *pByte = (char*)Result.pVal;
    for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
      char Tmp = pByte[i];
      pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
      pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
    }
    return Result;
  }
}

APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 
                                            const APInt& API2) {
  APInt A = API1, B = API2;
  while (!!B) {
    APInt T = B;
    B = APIntOps::urem(A, B);
    A = T;
  }
  return A;
}

APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
  union {
    double D;
    uint64_t I;
  } T;
  T.D = Double;

  // Get the sign bit from the highest order bit
  bool isNeg = T.I >> 63;

  // Get the 11-bit exponent and adjust for the 1023 bit bias
  int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;

  // If the exponent is negative, the value is < 0 so just return 0.
  if (exp < 0)
    return APInt(width, 0u);

  // Extract the mantissa by clearing the top 12 bits (sign + exponent).
  uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;

  // If the exponent doesn't shift all bits out of the mantissa
  if (exp < 52)
    return isNeg ? -APInt(width, mantissa >> (52 - exp)) : 
                    APInt(width, mantissa >> (52 - exp));

  // If the client didn't provide enough bits for us to shift the mantissa into
  // then the result is undefined, just return 0
  if (width <= exp - 52)
    return APInt(width, 0);

  // Otherwise, we have to shift the mantissa bits up to the right location
  APInt Tmp(width, mantissa);
  Tmp = Tmp.shl((unsigned)exp - 52);
  return isNeg ? -Tmp : Tmp;
}

/// RoundToDouble - This function convert this APInt to a double.
/// The layout for double is as following (IEEE Standard 754):
///  --------------------------------------
/// |  Sign    Exponent    Fraction    Bias |
/// |-------------------------------------- |
/// |  1[63]   11[62-52]   52[51-00]   1023 |
///  -------------------------------------- 
double APInt::roundToDouble(bool isSigned) const {

  // Handle the simple case where the value is contained in one uint64_t.
  if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
    if (isSigned) {
      int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
      return double(sext);
    } else
      return double(VAL);
  }

  // Determine if the value is negative.
  bool isNeg = isSigned ? (*this)[BitWidth-1] : false;

  // Construct the absolute value if we're negative.
  APInt Tmp(isNeg ? -(*this) : (*this));

  // Figure out how many bits we're using.
  unsigned n = Tmp.getActiveBits();

  // The exponent (without bias normalization) is just the number of bits
  // we are using. Note that the sign bit is gone since we constructed the
  // absolute value.
  uint64_t exp = n;

  // Return infinity for exponent overflow
  if (exp > 1023) {
    if (!isSigned || !isNeg)
      return std::numeric_limits<double>::infinity();
    else 
      return -std::numeric_limits<double>::infinity();
  }
  exp += 1023; // Increment for 1023 bias

  // Number of bits in mantissa is 52. To obtain the mantissa value, we must
  // extract the high 52 bits from the correct words in pVal.
  uint64_t mantissa;
  unsigned hiWord = whichWord(n-1);
  if (hiWord == 0) {
    mantissa = Tmp.pVal[0];
    if (n > 52)
      mantissa >>= n - 52; // shift down, we want the top 52 bits.
  } else {
    assert(hiWord > 0 && "huh?");
    uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
    uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
    mantissa = hibits | lobits;
  }

  // The leading bit of mantissa is implicit, so get rid of it.
  uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
  union {
    double D;
    uint64_t I;
  } T;
  T.I = sign | (exp << 52) | mantissa;
  return T.D;
}

// Truncate to new width.
APInt &APInt::trunc(unsigned width) {
  assert(width < BitWidth && "Invalid APInt Truncate request");
  assert(width && "Can't truncate to 0 bits");
  unsigned wordsBefore = getNumWords();
  BitWidth = width;
  unsigned wordsAfter = getNumWords();
  if (wordsBefore != wordsAfter) {
    if (wordsAfter == 1) {
      uint64_t *tmp = pVal;
      VAL = pVal[0];
      delete [] tmp;
    } else {
      uint64_t *newVal = getClearedMemory(wordsAfter);
      for (unsigned i = 0; i < wordsAfter; ++i)
        newVal[i] = pVal[i];
      delete [] pVal;
      pVal = newVal;
    }
  }
  return clearUnusedBits();
}

// Sign extend to a new width.
APInt &APInt::sext(unsigned width) {
  assert(width > BitWidth && "Invalid APInt SignExtend request");
  // If the sign bit isn't set, this is the same as zext.
  if (!isNegative()) {
    zext(width);
    return *this;
  }

  // The sign bit is set. First, get some facts
  unsigned wordsBefore = getNumWords();
  unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
  BitWidth = width;
  unsigned wordsAfter = getNumWords();

  // Mask the high order word appropriately
  if (wordsBefore == wordsAfter) {
    unsigned newWordBits = width % APINT_BITS_PER_WORD;
    // The extension is contained to the wordsBefore-1th word.
    uint64_t mask = ~0ULL;
    if (newWordBits)
      mask >>= APINT_BITS_PER_WORD - newWordBits;
    mask <<= wordBits;
    if (wordsBefore == 1)
      VAL |= mask;
    else
      pVal[wordsBefore-1] |= mask;
    return clearUnusedBits();
  }

  uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
  uint64_t *newVal = getMemory(wordsAfter);
  if (wordsBefore == 1)
    newVal[0] = VAL | mask;
  else {
    for (unsigned i = 0; i < wordsBefore; ++i)
      newVal[i] = pVal[i];
    newVal[wordsBefore-1] |= mask;
  }
  for (unsigned i = wordsBefore; i < wordsAfter; i++)
    newVal[i] = -1ULL;
  if (wordsBefore != 1)
    delete [] pVal;
  pVal = newVal;
  return clearUnusedBits();
}

//  Zero extend to a new width.
APInt &APInt::zext(unsigned width) {
  assert(width > BitWidth && "Invalid APInt ZeroExtend request");
  unsigned wordsBefore = getNumWords();
  BitWidth = width;
  unsigned wordsAfter = getNumWords();
  if (wordsBefore != wordsAfter) {
    uint64_t *newVal = getClearedMemory(wordsAfter);
    if (wordsBefore == 1)
      newVal[0] = VAL;
    else 
      for (unsigned i = 0; i < wordsBefore; ++i)
        newVal[i] = pVal[i];
    if (wordsBefore != 1)
      delete [] pVal;
    pVal = newVal;
  }
  return *this;
}

APInt &APInt::zextOrTrunc(unsigned width) {
  if (BitWidth < width)
    return zext(width);
  if (BitWidth > width)
    return trunc(width);
  return *this;
}

APInt &APInt::sextOrTrunc(unsigned width) {
  if (BitWidth < width)
    return sext(width);
  if (BitWidth > width)
    return trunc(width);
  return *this;
}

/// Arithmetic right-shift this APInt by shiftAmt.
/// @brief Arithmetic right-shift function.
APInt APInt::ashr(const APInt &shiftAmt) const {
  return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
}

/// Arithmetic right-shift this APInt by shiftAmt.
/// @brief Arithmetic right-shift function.
APInt APInt::ashr(unsigned shiftAmt) const {
  assert(shiftAmt <= BitWidth && "Invalid shift amount");
  // Handle a degenerate case
  if (shiftAmt == 0)
    return *this;

  // Handle single word shifts with built-in ashr
  if (isSingleWord()) {
    if (shiftAmt == BitWidth)
      return APInt(BitWidth, 0); // undefined
    else {
      unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
      return APInt(BitWidth, 
        (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
    }
  }

  // If all the bits were shifted out, the result is, technically, undefined.
  // We return -1 if it was negative, 0 otherwise. We check this early to avoid
  // issues in the algorithm below.
  if (shiftAmt == BitWidth) {
    if (isNegative())
      return APInt(BitWidth, -1ULL, true);
    else
      return APInt(BitWidth, 0);
  }

  // Create some space for the result.
  uint64_t * val = new uint64_t[getNumWords()];

  // Compute some values needed by the following shift algorithms
  unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
  unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
  unsigned breakWord = getNumWords() - 1 - offset; // last word affected
  unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
  if (bitsInWord == 0)
    bitsInWord = APINT_BITS_PER_WORD;

  // If we are shifting whole words, just move whole words
  if (wordShift == 0) {
    // Move the words containing significant bits
    for (unsigned i = 0; i <= breakWord; ++i)
      val[i] = pVal[i+offset]; // move whole word

    // Adjust the top significant word for sign bit fill, if negative
    if (isNegative())
      if (bitsInWord < APINT_BITS_PER_WORD)
        val[breakWord] |= ~0ULL << bitsInWord; // set high bits
  } else {
    // Shift the low order words 
    for (unsigned i = 0; i < breakWord; ++i) {
      // This combines the shifted corresponding word with the low bits from
      // the next word (shifted into this word's high bits).
      val[i] = (pVal[i+offset] >> wordShift) | 
               (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
    }

    // Shift the break word. In this case there are no bits from the next word
    // to include in this word.
    val[breakWord] = pVal[breakWord+offset] >> wordShift;

    // Deal with sign extenstion in the break word, and possibly the word before
    // it.
    if (isNegative()) {
      if (wordShift > bitsInWord) {
        if (breakWord > 0)
          val[breakWord-1] |= 
            ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
        val[breakWord] |= ~0ULL;
      } else 
        val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
    }
  }

  // Remaining words are 0 or -1, just assign them.
  uint64_t fillValue = (isNegative() ? -1ULL : 0);
  for (unsigned i = breakWord+1; i < getNumWords(); ++i)
    val[i] = fillValue;
  return APInt(val, BitWidth).clearUnusedBits();
}

/// Logical right-shift this APInt by shiftAmt.
/// @brief Logical right-shift function.
APInt APInt::lshr(const APInt &shiftAmt) const {
  return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
}

/// Logical right-shift this APInt by shiftAmt.
/// @brief Logical right-shift function.
APInt APInt::lshr(unsigned shiftAmt) const {
  if (isSingleWord()) {
    if (shiftAmt == BitWidth)
      return APInt(BitWidth, 0);
    else 
      return APInt(BitWidth, this->VAL >> shiftAmt);
  }

  // If all the bits were shifted out, the result is 0. This avoids issues
  // with shifting by the size of the integer type, which produces undefined
  // results. We define these "undefined results" to always be 0.
  if (shiftAmt == BitWidth)
    return APInt(BitWidth, 0);

  // If none of the bits are shifted out, the result is *this. This avoids
  // issues with shifting by the size of the integer type, which produces 
  // undefined results in the code below. This is also an optimization.
  if (shiftAmt == 0)
    return *this;

  // Create some space for the result.
  uint64_t * val = new uint64_t[getNumWords()];

  // If we are shifting less than a word, compute the shift with a simple carry
  if (shiftAmt < APINT_BITS_PER_WORD) {
    uint64_t carry = 0;
    for (int i = getNumWords()-1; i >= 0; --i) {
      val[i] = (pVal[i] >> shiftAmt) | carry;
      carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
    }
    return APInt(val, BitWidth).clearUnusedBits();
  }

  // Compute some values needed by the remaining shift algorithms
  unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
  unsigned offset = shiftAmt / APINT_BITS_PER_WORD;

  // If we are shifting whole words, just move whole words
  if (wordShift == 0) {
    for (unsigned i = 0; i < getNumWords() - offset; ++i)
      val[i] = pVal[i+offset];
    for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
      val[i] = 0;
    return APInt(val,BitWidth).clearUnusedBits();
  }

  // Shift the low order words 
  unsigned breakWord = getNumWords() - offset -1;
  for (unsigned i = 0; i < breakWord; ++i)
    val[i] = (pVal[i+offset] >> wordShift) |
             (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
  // Shift the break word.
  val[breakWord] = pVal[breakWord+offset] >> wordShift;

  // Remaining words are 0
  for (unsigned i = breakWord+1; i < getNumWords(); ++i)
    val[i] = 0;
  return APInt(val, BitWidth).clearUnusedBits();
}

/// Left-shift this APInt by shiftAmt.
/// @brief Left-shift function.
APInt APInt::shl(const APInt &shiftAmt) const {
  // It's undefined behavior in C to shift by BitWidth or greater.
  return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
}

APInt APInt::shlSlowCase(unsigned shiftAmt) const {
  // If all the bits were shifted out, the result is 0. This avoids issues
  // with shifting by the size of the integer type, which produces undefined
  // results. We define these "undefined results" to always be 0.
  if (shiftAmt == BitWidth)
    return APInt(BitWidth, 0);

  // If none of the bits are shifted out, the result is *this. This avoids a
  // lshr by the words size in the loop below which can produce incorrect
  // results. It also avoids the expensive computation below for a common case.
  if (shiftAmt == 0)
    return *this;

  // Create some space for the result.
  uint64_t * val = new uint64_t[getNumWords()];

  // If we are shifting less than a word, do it the easy way
  if (shiftAmt < APINT_BITS_PER_WORD) {
    uint64_t carry = 0;
    for (unsigned i = 0; i < getNumWords(); i++) {
      val[i] = pVal[i] << shiftAmt | carry;
      carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
    }
    return APInt(val, BitWidth).clearUnusedBits();
  }

  // Compute some values needed by the remaining shift algorithms
  unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
  unsigned offset = shiftAmt / APINT_BITS_PER_WORD;

  // If we are shifting whole words, just move whole words
  if (wordShift == 0) {
    for (unsigned i = 0; i < offset; i++)
      val[i] = 0;
    for (unsigned i = offset; i < getNumWords(); i++)
      val[i] = pVal[i-offset];
    return APInt(val,BitWidth).clearUnusedBits();
  }

  // Copy whole words from this to Result.
  unsigned i = getNumWords() - 1;
  for (; i > offset; --i)
    val[i] = pVal[i-offset] << wordShift |
             pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
  val[offset] = pVal[0] << wordShift;
  for (i = 0; i < offset; ++i)
    val[i] = 0;
  return APInt(val, BitWidth).clearUnusedBits();
}

APInt APInt::rotl(const APInt &rotateAmt) const {
  return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
}

APInt APInt::rotl(unsigned rotateAmt) const {
  if (rotateAmt == 0)
    return *this;
  // Don't get too fancy, just use existing shift/or facilities
  APInt hi(*this);
  APInt lo(*this);
  hi.shl(rotateAmt);
  lo.lshr(BitWidth - rotateAmt);
  return hi | lo;
}

APInt APInt::rotr(const APInt &rotateAmt) const {
  return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
}

APInt APInt::rotr(unsigned rotateAmt) const {
  if (rotateAmt == 0)
    return *this;
  // Don't get too fancy, just use existing shift/or facilities
  APInt hi(*this);
  APInt lo(*this);
  lo.lshr(rotateAmt);
  hi.shl(BitWidth - rotateAmt);
  return hi | lo;
}

// Square Root - this method computes and returns the square root of "this".
// Three mechanisms are used for computation. For small values (<= 5 bits),
// a table lookup is done. This gets some performance for common cases. For
// values using less than 52 bits, the value is converted to double and then
// the libc sqrt function is called. The result is rounded and then converted
// back to a uint64_t which is then used to construct the result. Finally,
// the Babylonian method for computing square roots is used. 
APInt APInt::sqrt() const {

  // Determine the magnitude of the value.
  unsigned magnitude = getActiveBits();

  // Use a fast table for some small values. This also gets rid of some
  // rounding errors in libc sqrt for small values.
  if (magnitude <= 5) {
    static const uint8_t results[32] = {
      /*     0 */ 0,
      /*  1- 2 */ 1, 1,
      /*  3- 6 */ 2, 2, 2, 2, 
      /*  7-12 */ 3, 3, 3, 3, 3, 3,
      /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
      /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
      /*    31 */ 6
    };
    return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
  }

  // If the magnitude of the value fits in less than 52 bits (the precision of
  // an IEEE double precision floating point value), then we can use the
  // libc sqrt function which will probably use a hardware sqrt computation.
  // This should be faster than the algorithm below.
  if (magnitude < 52) {
#ifdef _MSC_VER
    // Amazingly, VC++ doesn't have round().
    return APInt(BitWidth, 
                 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
#else
    return APInt(BitWidth, 
                 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
#endif
  }

  // Okay, all the short cuts are exhausted. We must compute it. The following
  // is a classical Babylonian method for computing the square root. This code
  // was adapted to APINt from a wikipedia article on such computations.
  // See http://www.wikipedia.org/ and go to the page named
  // Calculate_an_integer_square_root. 
  unsigned nbits = BitWidth, i = 4;
  APInt testy(BitWidth, 16);
  APInt x_old(BitWidth, 1);
  APInt x_new(BitWidth, 0);
  APInt two(BitWidth, 2);

  // Select a good starting value using binary logarithms.
  for (;; i += 2, testy = testy.shl(2)) 
    if (i >= nbits || this->ule(testy)) {
      x_old = x_old.shl(i / 2);
      break;
    }

  // Use the Babylonian method to arrive at the integer square root: 
  for (;;) {
    x_new = (this->udiv(x_old) + x_old).udiv(two);
    if (x_old.ule(x_new))
      break;
    x_old = x_new;
  }

  // Make sure we return the closest approximation
  // NOTE: The rounding calculation below is correct. It will produce an 
  // off-by-one discrepancy with results from pari/gp. That discrepancy has been
  // determined to be a rounding issue with pari/gp as it begins to use a 
  // floating point representation after 192 bits. There are no discrepancies
  // between this algorithm and pari/gp for bit widths < 192 bits.
  APInt square(x_old * x_old);
  APInt nextSquare((x_old + 1) * (x_old +1));
  if (this->ult(square))
    return x_old;
  else if (this->ule(nextSquare)) {
    APInt midpoint((nextSquare - square).udiv(two));
    APInt offset(*this - square);
    if (offset.ult(midpoint))
      return x_old;
    else
      return x_old + 1;
  } else
    assert(0 && "Error in APInt::sqrt computation");
  return x_old + 1;
}

/// Computes the multiplicative inverse of this APInt for a given modulo. The
/// iterative extended Euclidean algorithm is used to solve for this value,
/// however we simplify it to speed up calculating only the inverse, and take
/// advantage of div+rem calculations. We also use some tricks to avoid copying
/// (potentially large) APInts around.
APInt APInt::multiplicativeInverse(const APInt& modulo) const {
  assert(ult(modulo) && "This APInt must be smaller than the modulo");

  // Using the properties listed at the following web page (accessed 06/21/08):
  //   http://www.numbertheory.org/php/euclid.html
  // (especially the properties numbered 3, 4 and 9) it can be proved that
  // BitWidth bits suffice for all the computations in the algorithm implemented
  // below. More precisely, this number of bits suffice if the multiplicative
  // inverse exists, but may not suffice for the general extended Euclidean
  // algorithm.

  APInt r[2] = { modulo, *this };
  APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
  APInt q(BitWidth, 0);
  
  unsigned i;
  for (i = 0; r[i^1] != 0; i ^= 1) {
    // An overview of the math without the confusing bit-flipping:
    // q = r[i-2] / r[i-1]
    // r[i] = r[i-2] % r[i-1]
    // t[i] = t[i-2] - t[i-1] * q
    udivrem(r[i], r[i^1], q, r[i]);
    t[i] -= t[i^1] * q;
  }

  // If this APInt and the modulo are not coprime, there is no multiplicative
  // inverse, so return 0. We check this by looking at the next-to-last
  // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
  // algorithm.
  if (r[i] != 1)
    return APInt(BitWidth, 0);

  // The next-to-last t is the multiplicative inverse.  However, we are
  // interested in a positive inverse. Calcuate a positive one from a negative
  // one if necessary. A simple addition of the modulo suffices because
  // abs(t[i]) is known to be less than *this/2 (see the link above).
  return t[i].isNegative() ? t[i] + modulo : t[i];
}

/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
/// variables here have the same names as in the algorithm. Comments explain
/// the algorithm and any deviation from it.
static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
                     unsigned m, unsigned n) {
  assert(u && "Must provide dividend");
  assert(v && "Must provide divisor");
  assert(q && "Must provide quotient");
  assert(u != v && u != q && v != q && "Must us different memory");
  assert(n>1 && "n must be > 1");

  // Knuth uses the value b as the base of the number system. In our case b
  // is 2^31 so we just set it to -1u.
  uint64_t b = uint64_t(1) << 32;

#if 0
  DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
  DEBUG(cerr << "KnuthDiv: original:");
  DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
  DEBUG(cerr << " by");
  DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
  DEBUG(cerr << '\n');
#endif
  // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 
  // u and v by d. Note that we have taken Knuth's advice here to use a power 
  // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 
  // 2 allows us to shift instead of multiply and it is easy to determine the 
  // shift amount from the leading zeros.  We are basically normalizing the u
  // and v so that its high bits are shifted to the top of v's range without
  // overflow. Note that this can require an extra word in u so that u must
  // be of length m+n+1.
  unsigned shift = CountLeadingZeros_32(v[n-1]);
  unsigned v_carry = 0;
  unsigned u_carry = 0;
  if (shift) {
    for (unsigned i = 0; i < m+n; ++i) {
      unsigned u_tmp = u[i] >> (32 - shift);
      u[i] = (u[i] << shift) | u_carry;
      u_carry = u_tmp;
    }
    for (unsigned i = 0; i < n; ++i) {
      unsigned v_tmp = v[i] >> (32 - shift);
      v[i] = (v[i] << shift) | v_carry;
      v_carry = v_tmp;
    }
  }
  u[m+n] = u_carry;
#if 0
  DEBUG(cerr << "KnuthDiv:   normal:");
  DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
  DEBUG(cerr << " by");
  DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
  DEBUG(cerr << '\n');
#endif

  // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
  int j = m;
  do {
    DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
    // D3. [Calculate q'.]. 
    //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
    //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
    // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
    // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
    // on v[n-2] determines at high speed most of the cases in which the trial
    // value qp is one too large, and it eliminates all cases where qp is two 
    // too large. 
    uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
    DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
    uint64_t qp = dividend / v[n-1];
    uint64_t rp = dividend % v[n-1];
    if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
      qp--;
      rp += v[n-1];
      if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
        qp--;
    }
    DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');

    // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
    // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
    // consists of a simple multiplication by a one-place number, combined with
    // a subtraction. 
    bool isNeg = false;
    for (unsigned i = 0; i < n; ++i) {
      uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
      uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
      bool borrow = subtrahend > u_tmp;
      DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp 
                 << ", subtrahend == " << subtrahend
                 << ", borrow = " << borrow << '\n');

      uint64_t result = u_tmp - subtrahend;
      unsigned k = j + i;
      u[k++] = (unsigned)(result & (b-1)); // subtract low word
      u[k++] = (unsigned)(result >> 32);   // subtract high word
      while (borrow && k <= m+n) { // deal with borrow to the left
        borrow = u[k] == 0;
        u[k]--;
        k++;
      }
      isNeg |= borrow;
      DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " << 
                    u[j+i+1] << '\n'); 
    }
    DEBUG(cerr << "KnuthDiv: after subtraction:");
    DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
    DEBUG(cerr << '\n');
    // The digits (u[j+n]...u[j]) should be kept positive; if the result of 
    // this step is actually negative, (u[j+n]...u[j]) should be left as the 
    // true value plus b**(n+1), namely as the b's complement of
    // the true value, and a "borrow" to the left should be remembered.
    //
    if (isNeg) {
      bool carry = true;  // true because b's complement is "complement + 1"
      for (unsigned i = 0; i <= m+n; ++i) {
        u[i] = ~u[i] + carry; // b's complement
        carry = carry && u[i] == 0;
      }
    }
    DEBUG(cerr << "KnuthDiv: after complement:");
    DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
    DEBUG(cerr << '\n');

    // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 
    // negative, go to step D6; otherwise go on to step D7.
    q[j] = (unsigned)qp;
    if (isNeg) {
      // D6. [Add back]. The probability that this step is necessary is very 
      // small, on the order of only 2/b. Make sure that test data accounts for
      // this possibility. Decrease q[j] by 1 
      q[j]--;
      // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 
      // A carry will occur to the left of u[j+n], and it should be ignored 
      // since it cancels with the borrow that occurred in D4.
      bool carry = false;
      for (unsigned i = 0; i < n; i++) {
        unsigned limit = std::min(u[j+i],v[i]);
        u[j+i] += v[i] + carry;
        carry = u[j+i] < limit || (carry && u[j+i] == limit);
      }
      u[j+n] += carry;
    }
    DEBUG(cerr << "KnuthDiv: after correction:");
    DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
    DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');

  // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
  } while (--j >= 0);

  DEBUG(cerr << "KnuthDiv: quotient:");
  DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
  DEBUG(cerr << '\n');

  // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
  // remainder may be obtained by dividing u[...] by d. If r is non-null we
  // compute the remainder (urem uses this).
  if (r) {
    // The value d is expressed by the "shift" value above since we avoided
    // multiplication by d by using a shift left. So, all we have to do is
    // shift right here. In order to mak
    if (shift) {
      unsigned carry = 0;
      DEBUG(cerr << "KnuthDiv: remainder:");
      for (int i = n-1; i >= 0; i--) {
        r[i] = (u[i] >> shift) | carry;
        carry = u[i] << (32 - shift);
        DEBUG(cerr << " " << r[i]);
      }
    } else {
      for (int i = n-1; i >= 0; i--) {
        r[i] = u[i];
        DEBUG(cerr << " " << r[i]);
      }
    }
    DEBUG(cerr << '\n');
  }
#if 0
  DEBUG(cerr << std::setbase(10) << '\n');
#endif
}

void APInt::divide(const APInt LHS, unsigned lhsWords,
                   const APInt &RHS, unsigned rhsWords,
                   APInt *Quotient, APInt *Remainder)
{
  assert(lhsWords >= rhsWords && "Fractional result");

  // First, compose the values into an array of 32-bit words instead of 
  // 64-bit words. This is a necessity of both the "short division" algorithm
  // and the the Knuth "classical algorithm" which requires there to be native 
  // operations for +, -, and * on an m bit value with an m*2 bit result. We 
  // can't use 64-bit operands here because we don't have native results of 
  // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't 
  // work on large-endian machines.
  uint64_t mask = ~0ull >> (sizeof(unsigned)*8);
  unsigned n = rhsWords * 2;
  unsigned m = (lhsWords * 2) - n;

  // Allocate space for the temporary values we need either on the stack, if
  // it will fit, or on the heap if it won't.
  unsigned SPACE[128];
  unsigned *U = 0;
  unsigned *V = 0;
  unsigned *Q = 0;
  unsigned *R = 0;
  if ((Remainder?4:3)*n+2*m+1 <= 128) {
    U = &SPACE[0];
    V = &SPACE[m+n+1];
    Q = &SPACE[(m+n+1) + n];
    if (Remainder)
      R = &SPACE[(m+n+1) + n + (m+n)];
  } else {
    U = new unsigned[m + n + 1];
    V = new unsigned[n];
    Q = new unsigned[m+n];
    if (Remainder)
      R = new unsigned[n];
  }

  // Initialize the dividend
  memset(U, 0, (m+n+1)*sizeof(unsigned));
  for (unsigned i = 0; i < lhsWords; ++i) {
    uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
    U[i * 2] = (unsigned)(tmp & mask);
    U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8));
  }
  U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.

  // Initialize the divisor
  memset(V, 0, (n)*sizeof(unsigned));
  for (unsigned i = 0; i < rhsWords; ++i) {
    uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
    V[i * 2] = (unsigned)(tmp & mask);
    V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8));
  }

  // initialize the quotient and remainder
  memset(Q, 0, (m+n) * sizeof(unsigned));
  if (Remainder)
    memset(R, 0, n * sizeof(unsigned));

  // Now, adjust m and n for the Knuth division. n is the number of words in 
  // the divisor. m is the number of words by which the dividend exceeds the
  // divisor (i.e. m+n is the length of the dividend). These sizes must not 
  // contain any zero words or the Knuth algorithm fails.
  for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
    n--;
    m++;
  }
  for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
    m--;

  // If we're left with only a single word for the divisor, Knuth doesn't work
  // so we implement the short division algorithm here. This is much simpler
  // and faster because we are certain that we can divide a 64-bit quantity
  // by a 32-bit quantity at hardware speed and short division is simply a
  // series of such operations. This is just like doing short division but we
  // are using base 2^32 instead of base 10.
  assert(n != 0 && "Divide by zero?");
  if (n == 1) {
    unsigned divisor = V[0];
    unsigned remainder = 0;
    for (int i = m+n-1; i >= 0; i--) {
      uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
      if (partial_dividend == 0) {
        Q[i] = 0;
        remainder = 0;
      } else if (partial_dividend < divisor) {
        Q[i] = 0;
        remainder = (unsigned)partial_dividend;
      } else if (partial_dividend == divisor) {
        Q[i] = 1;
        remainder = 0;
      } else {
        Q[i] = (unsigned)(partial_dividend / divisor);
        remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
      }
    }
    if (R)
      R[0] = remainder;
  } else {
    // Now we're ready to invoke the Knuth classical divide algorithm. In this
    // case n > 1.
    KnuthDiv(U, V, Q, R, m, n);
  }

  // If the caller wants the quotient
  if (Quotient) {
    // Set up the Quotient value's memory.
    if (Quotient->BitWidth != LHS.BitWidth) {
      if (Quotient->isSingleWord())
        Quotient->VAL = 0;
      else
        delete [] Quotient->pVal;
      Quotient->BitWidth = LHS.BitWidth;
      if (!Quotient->isSingleWord())
        Quotient->pVal = getClearedMemory(Quotient->getNumWords());
    } else
      Quotient->clear();

    // The quotient is in Q. Reconstitute the quotient into Quotient's low 
    // order words.
    if (lhsWords == 1) {
      uint64_t tmp = 
        uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
      if (Quotient->isSingleWord())
        Quotient->VAL = tmp;
      else
        Quotient->pVal[0] = tmp;
    } else {
      assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
      for (unsigned i = 0; i < lhsWords; ++i)
        Quotient->pVal[i] = 
          uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
    }
  }

  // If the caller wants the remainder
  if (Remainder) {
    // Set up the Remainder value's memory.
    if (Remainder->BitWidth != RHS.BitWidth) {
      if (Remainder->isSingleWord())
        Remainder->VAL = 0;
      else
        delete [] Remainder->pVal;
      Remainder->BitWidth = RHS.BitWidth;
      if (!Remainder->isSingleWord())
        Remainder->pVal = getClearedMemory(Remainder->getNumWords());
    } else
      Remainder->clear();

    // The remainder is in R. Reconstitute the remainder into Remainder's low
    // order words.
    if (rhsWords == 1) {
      uint64_t tmp = 
        uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
      if (Remainder->isSingleWord())
        Remainder->VAL = tmp;
      else
        Remainder->pVal[0] = tmp;
    } else {
      assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
      for (unsigned i = 0; i < rhsWords; ++i)
        Remainder->pVal[i] = 
          uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
    }
  }

  // Clean up the memory we allocated.
  if (U != &SPACE[0]) {
    delete [] U;
    delete [] V;
    delete [] Q;
    delete [] R;
  }
}

APInt APInt::udiv(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

  // First, deal with the easy case
  if (isSingleWord()) {
    assert(RHS.VAL != 0 && "Divide by zero?");
    return APInt(BitWidth, VAL / RHS.VAL);
  }

  // Get some facts about the LHS and RHS number of bits and words
  unsigned rhsBits = RHS.getActiveBits();
  unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
  assert(rhsWords && "Divided by zero???");
  unsigned lhsBits = this->getActiveBits();
  unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);

  // Deal with some degenerate cases
  if (!lhsWords) 
    // 0 / X ===> 0
    return APInt(BitWidth, 0); 
  else if (lhsWords < rhsWords || this->ult(RHS)) {
    // X / Y ===> 0, iff X < Y
    return APInt(BitWidth, 0);
  } else if (*this == RHS) {
    // X / X ===> 1
    return APInt(BitWidth, 1);
  } else if (lhsWords == 1 && rhsWords == 1) {
    // All high words are zero, just use native divide
    return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
  }

  // We have to compute it the hard way. Invoke the Knuth divide algorithm.
  APInt Quotient(1,0); // to hold result.
  divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
  return Quotient;
}

APInt APInt::urem(const APInt& RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
  if (isSingleWord()) {
    assert(RHS.VAL != 0 && "Remainder by zero?");
    return APInt(BitWidth, VAL % RHS.VAL);
  }

  // Get some facts about the LHS
  unsigned lhsBits = getActiveBits();
  unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);

  // Get some facts about the RHS
  unsigned rhsBits = RHS.getActiveBits();
  unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
  assert(rhsWords && "Performing remainder operation by zero ???");

  // Check the degenerate cases
  if (lhsWords == 0) {
    // 0 % Y ===> 0
    return APInt(BitWidth, 0);
  } else if (lhsWords < rhsWords || this->ult(RHS)) {
    // X % Y ===> X, iff X < Y
    return *this;
  } else if (*this == RHS) {
    // X % X == 0;
    return APInt(BitWidth, 0);
  } else if (lhsWords == 1) {
    // All high words are zero, just use native remainder
    return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
  }

  // We have to compute it the hard way. Invoke the Knuth divide algorithm.
  APInt Remainder(1,0);
  divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
  return Remainder;
}

void APInt::udivrem(const APInt &LHS, const APInt &RHS, 
                    APInt &Quotient, APInt &Remainder) {
  // Get some size facts about the dividend and divisor
  unsigned lhsBits  = LHS.getActiveBits();
  unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
  unsigned rhsBits  = RHS.getActiveBits();
  unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);

  // Check the degenerate cases
  if (lhsWords == 0) {              
    Quotient = 0;                // 0 / Y ===> 0
    Remainder = 0;               // 0 % Y ===> 0
    return;
  } 
  
  if (lhsWords < rhsWords || LHS.ult(RHS)) { 
    Quotient = 0;               // X / Y ===> 0, iff X < Y
    Remainder = LHS;            // X % Y ===> X, iff X < Y
    return;
  } 
  
  if (LHS == RHS) {
    Quotient  = 1;              // X / X ===> 1
    Remainder = 0;              // X % X ===> 0;
    return;
  } 
  
  if (lhsWords == 1 && rhsWords == 1) {
    // There is only one word to consider so use the native versions.
    uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
    uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
    Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
    Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
    return;
  }

  // Okay, lets do it the long way
  divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
}

void APInt::fromString(unsigned numbits, const char *str, unsigned slen,
                       uint8_t radix) {
  // Check our assumptions here
  assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
         "Radix should be 2, 8, 10, or 16!");
  assert(str && "String is null?");
  bool isNeg = str[0] == '-';
  if (isNeg)
    str++, slen--;
  assert((slen <= numbits || radix != 2) && "Insufficient bit width");
  assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
  assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
  assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");

  // Allocate memory
  if (!isSingleWord())
    pVal = getClearedMemory(getNumWords());

  // Figure out if we can shift instead of multiply
  unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);

  // Set up an APInt for the digit to add outside the loop so we don't
  // constantly construct/destruct it.
  APInt apdigit(getBitWidth(), 0);
  APInt apradix(getBitWidth(), radix);

  // Enter digit traversal loop
  for (unsigned i = 0; i < slen; i++) {
    // Get a digit
    unsigned digit = 0;
    char cdigit = str[i];
    if (radix == 16) {
      if (!isxdigit(cdigit))
        assert(0 && "Invalid hex digit in string");
      if (isdigit(cdigit))
        digit = cdigit - '0';
      else if (cdigit >= 'a')
        digit = cdigit - 'a' + 10;
      else if (cdigit >= 'A')
        digit = cdigit - 'A' + 10;
      else
        assert(0 && "huh? we shouldn't get here");
    } else if (isdigit(cdigit)) {
      digit = cdigit - '0';
      assert((radix == 10 ||
              (radix == 8 && digit != 8 && digit != 9) ||
              (radix == 2 && (digit == 0 || digit == 1))) &&
             "Invalid digit in string for given radix");
    } else {
      assert(0 && "Invalid character in digit string");
    }

    // Shift or multiply the value by the radix
    if (shift)
      *this <<= shift;
    else
      *this *= apradix;

    // Add in the digit we just interpreted
    if (apdigit.isSingleWord())
      apdigit.VAL = digit;
    else
      apdigit.pVal[0] = digit;
    *this += apdigit;
  }
  // If its negative, put it in two's complement form
  if (isNeg) {
    (*this)--;
    this->flip();
  }
}

void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
                     bool Signed) const {
  assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
         "Radix should be 2, 8, 10, or 16!");
  
  // First, check for a zero value and just short circuit the logic below.
  if (*this == 0) {
    Str.push_back('0');
    return;
  }
  
  static const char Digits[] = "0123456789ABCDEF";
  
  if (isSingleWord()) {
    char Buffer[65];
    char *BufPtr = Buffer+65;
    
    uint64_t N;
    if (Signed) {
      int64_t I = getSExtValue();
      if (I < 0) {
        Str.push_back('-');
        I = -I;
      }
      N = I;
    } else {
      N = getZExtValue();
    }
    
    while (N) {
      *--BufPtr = Digits[N % Radix];
      N /= Radix;
    }
    Str.append(BufPtr, Buffer+65);
    return;
  }

  APInt Tmp(*this);
  
  if (Signed && isNegative()) {
    // They want to print the signed version and it is a negative value
    // Flip the bits and add one to turn it into the equivalent positive
    // value and put a '-' in the result.
    Tmp.flip();
    Tmp++;
    Str.push_back('-');
  }
  
  // We insert the digits backward, then reverse them to get the right order.
  unsigned StartDig = Str.size();
  
  // For the 2, 8 and 16 bit cases, we can just shift instead of divide 
  // because the number of bits per digit (1, 3 and 4 respectively) divides 
  // equaly.  We just shift until the value is zero.
  if (Radix != 10) {
    // Just shift tmp right for each digit width until it becomes zero
    unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
    unsigned MaskAmt = Radix - 1;
    
    while (Tmp != 0) {
      unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
      Str.push_back(Digits[Digit]);
      Tmp = Tmp.lshr(ShiftAmt);
    }
  } else {
    APInt divisor(4, 10);
    while (Tmp != 0) {
      APInt APdigit(1, 0);
      APInt tmp2(Tmp.getBitWidth(), 0);
      divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 
             &APdigit);
      unsigned Digit = (unsigned)APdigit.getZExtValue();
      assert(Digit < Radix && "divide failed");
      Str.push_back(Digits[Digit]);
      Tmp = tmp2;
    }
  }
  
  // Reverse the digits before returning.
  std::reverse(Str.begin()+StartDig, Str.end());
}

/// toString - This returns the APInt as a std::string.  Note that this is an
/// inefficient method.  It is better to pass in a SmallVector/SmallString
/// to the methods above.
std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
  SmallString<40> S;
  toString(S, Radix, Signed);
  return S.c_str();
}


void APInt::dump() const {
  SmallString<40> S, U;
  this->toStringUnsigned(U);
  this->toStringSigned(S);
  fprintf(stderr, "APInt(%db, %su %ss)", BitWidth, U.c_str(), S.c_str());
}

void APInt::print(raw_ostream &OS, bool isSigned) const {
  SmallString<40> S;
  this->toString(S, 10, isSigned);
  OS << S.c_str();
}

// This implements a variety of operations on a representation of
// arbitrary precision, two's-complement, bignum integer values.

/* Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
   and unrestricting assumption.  */
#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);

/* Some handy functions local to this file.  */
namespace {

  /* Returns the integer part with the least significant BITS set.
     BITS cannot be zero.  */
  static inline integerPart
  lowBitMask(unsigned int bits)
  {
    assert (bits != 0 && bits <= integerPartWidth);

    return ~(integerPart) 0 >> (integerPartWidth - bits);
  }

  /* Returns the value of the lower half of PART.  */
  static inline integerPart
  lowHalf(integerPart part)
  {
    return part & lowBitMask(integerPartWidth / 2);
  }

  /* Returns the value of the upper half of PART.  */
  static inline integerPart
  highHalf(integerPart part)
  {
    return part >> (integerPartWidth / 2);
  }

  /* Returns the bit number of the most significant set bit of a part.
     If the input number has no bits set -1U is returned.  */
  static unsigned int
  partMSB(integerPart value)
  {
    unsigned int n, msb;

    if (value == 0)
      return -1U;

    n = integerPartWidth / 2;

    msb = 0;
    do {
      if (value >> n) {
        value >>= n;
        msb += n;
      }

      n >>= 1;
    } while (n);

    return msb;
  }

  /* Returns the bit number of the least significant set bit of a
     part.  If the input number has no bits set -1U is returned.  */
  static unsigned int
  partLSB(integerPart value)
  {
    unsigned int n, lsb;

    if (value == 0)
      return -1U;

    lsb = integerPartWidth - 1;
    n = integerPartWidth / 2;

    do {
      if (value << n) {
        value <<= n;
        lsb -= n;
      }

      n >>= 1;
    } while (n);

    return lsb;
  }
}

/* Sets the least significant part of a bignum to the input value, and
   zeroes out higher parts.  */
void
APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
{
  unsigned int i;

  assert (parts > 0);

  dst[0] = part;
  for(i = 1; i < parts; i++)
    dst[i] = 0;
}

/* Assign one bignum to another.  */
void
APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    dst[i] = src[i];
}

/* Returns true if a bignum is zero, false otherwise.  */
bool
APInt::tcIsZero(const integerPart *src, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    if (src[i])
      return false;

  return true;
}

/* Extract the given bit of a bignum; returns 0 or 1.  */
int
APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
{
  return(parts[bit / integerPartWidth]
         & ((integerPart) 1 << bit % integerPartWidth)) != 0;
}

/* Set the given bit of a bignum.  */
void
APInt::tcSetBit(integerPart *parts, unsigned int bit)
{
  parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
}

/* Returns the bit number of the least significant set bit of a
   number.  If the input number has no bits set -1U is returned.  */
unsigned int
APInt::tcLSB(const integerPart *parts, unsigned int n)
{
  unsigned int i, lsb;

  for(i = 0; i < n; i++) {
      if (parts[i] != 0) {
          lsb = partLSB(parts[i]);

          return lsb + i * integerPartWidth;
      }
  }

  return -1U;
}

/* Returns the bit number of the most significant set bit of a number.
   If the input number has no bits set -1U is returned.  */
unsigned int
APInt::tcMSB(const integerPart *parts, unsigned int n)
{
  unsigned int msb;

  do {
      --n;

      if (parts[n] != 0) {
          msb = partMSB(parts[n]);

          return msb + n * integerPartWidth;
      }
  } while (n);

  return -1U;
}

/* Copy the bit vector of width srcBITS from SRC, starting at bit
   srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
   the least significant bit of DST.  All high bits above srcBITS in
   DST are zero-filled.  */
void
APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
                 unsigned int srcBits, unsigned int srcLSB)
{
  unsigned int firstSrcPart, dstParts, shift, n;

  dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
  assert (dstParts <= dstCount);

  firstSrcPart = srcLSB / integerPartWidth;
  tcAssign (dst, src + firstSrcPart, dstParts);

  shift = srcLSB % integerPartWidth;
  tcShiftRight (dst, dstParts, shift);

  /* We now have (dstParts * integerPartWidth - shift) bits from SRC
     in DST.  If this is less that srcBits, append the rest, else
     clear the high bits.  */
  n = dstParts * integerPartWidth - shift;
  if (n < srcBits) {
    integerPart mask = lowBitMask (srcBits - n);
    dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
                          << n % integerPartWidth);
  } else if (n > srcBits) {
    if (srcBits % integerPartWidth)
      dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
  }

  /* Clear high parts.  */
  while (dstParts < dstCount)
    dst[dstParts++] = 0;
}

/* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
integerPart
APInt::tcAdd(integerPart *dst, const integerPart *rhs,
             integerPart c, unsigned int parts)
{
  unsigned int i;

  assert(c <= 1);

  for(i = 0; i < parts; i++) {
    integerPart l;

    l = dst[i];
    if (c) {
      dst[i] += rhs[i] + 1;
      c = (dst[i] <= l);
    } else {
      dst[i] += rhs[i];
      c = (dst[i] < l);
    }
  }

  return c;
}

/* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
integerPart
APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
                  integerPart c, unsigned int parts)
{
  unsigned int i;

  assert(c <= 1);

  for(i = 0; i < parts; i++) {
    integerPart l;

    l = dst[i];
    if (c) {
      dst[i] -= rhs[i] + 1;
      c = (dst[i] >= l);
    } else {
      dst[i] -= rhs[i];
      c = (dst[i] > l);
    }
  }

  return c;
}

/* Negate a bignum in-place.  */
void
APInt::tcNegate(integerPart *dst, unsigned int parts)
{
  tcComplement(dst, parts);
  tcIncrement(dst, parts);
}

/*  DST += SRC * MULTIPLIER + CARRY   if add is true
    DST  = SRC * MULTIPLIER + CARRY   if add is false

    Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
    they must start at the same point, i.e. DST == SRC.

    If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
    returned.  Otherwise DST is filled with the least significant
    DSTPARTS parts of the result, and if all of the omitted higher
    parts were zero return zero, otherwise overflow occurred and
    return one.  */
int
APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
                      integerPart multiplier, integerPart carry,
                      unsigned int srcParts, unsigned int dstParts,
                      bool add)
{
  unsigned int i, n;

  /* Otherwise our writes of DST kill our later reads of SRC.  */
  assert(dst <= src || dst >= src + srcParts);
  assert(dstParts <= srcParts + 1);

  /* N loops; minimum of dstParts and srcParts.  */
  n = dstParts < srcParts ? dstParts: srcParts;

  for(i = 0; i < n; i++) {
    integerPart low, mid, high, srcPart;

      /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.

         This cannot overflow, because

         (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)

         which is less than n^2.  */

    srcPart = src[i];

    if (multiplier == 0 || srcPart == 0)        {
      low = carry;
      high = 0;
    } else {
      low = lowHalf(srcPart) * lowHalf(multiplier);
      high = highHalf(srcPart) * highHalf(multiplier);

      mid = lowHalf(srcPart) * highHalf(multiplier);
      high += highHalf(mid);
      mid <<= integerPartWidth / 2;
      if (low + mid < low)
        high++;
      low += mid;

      mid = highHalf(srcPart) * lowHalf(multiplier);
      high += highHalf(mid);
      mid <<= integerPartWidth / 2;
      if (low + mid < low)
        high++;
      low += mid;

      /* Now add carry.  */
      if (low + carry < low)
        high++;
      low += carry;
    }

    if (add) {
      /* And now DST[i], and store the new low part there.  */
      if (low + dst[i] < low)
        high++;
      dst[i] += low;
    } else
      dst[i] = low;

    carry = high;
  }

  if (i < dstParts) {
    /* Full multiplication, there is no overflow.  */
    assert(i + 1 == dstParts);
    dst[i] = carry;
    return 0;
  } else {
    /* We overflowed if there is carry.  */
    if (carry)
      return 1;

    /* We would overflow if any significant unwritten parts would be
       non-zero.  This is true if any remaining src parts are non-zero
       and the multiplier is non-zero.  */
    if (multiplier)
      for(; i < srcParts; i++)
        if (src[i])
          return 1;

    /* We fitted in the narrow destination.  */
    return 0;
  }
}

/* DST = LHS * RHS, where DST has the same width as the operands and
   is filled with the least significant parts of the result.  Returns
   one if overflow occurred, otherwise zero.  DST must be disjoint
   from both operands.  */
int
APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
                  const integerPart *rhs, unsigned int parts)
{
  unsigned int i;
  int overflow;

  assert(dst != lhs && dst != rhs);

  overflow = 0;
  tcSet(dst, 0, parts);

  for(i = 0; i < parts; i++)
    overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
                               parts - i, true);

  return overflow;
}

/* DST = LHS * RHS, where DST has width the sum of the widths of the
   operands.  No overflow occurs.  DST must be disjoint from both
   operands.  Returns the number of parts required to hold the
   result.  */
unsigned int
APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
                      const integerPart *rhs, unsigned int lhsParts,
                      unsigned int rhsParts)
{
  /* Put the narrower number on the LHS for less loops below.  */
  if (lhsParts > rhsParts) {
    return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
  } else {
    unsigned int n;

    assert(dst != lhs && dst != rhs);

    tcSet(dst, 0, rhsParts);

    for(n = 0; n < lhsParts; n++)
      tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);

    n = lhsParts + rhsParts;

    return n - (dst[n - 1] == 0);
  }
}

/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
   Otherwise set LHS to LHS / RHS with the fractional part discarded,
   set REMAINDER to the remainder, return zero.  i.e.

   OLD_LHS = RHS * LHS + REMAINDER

   SCRATCH is a bignum of the same size as the operands and result for
   use by the routine; its contents need not be initialized and are
   destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
*/
int
APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
                integerPart *remainder, integerPart *srhs,
                unsigned int parts)
{
  unsigned int n, shiftCount;
  integerPart mask;

  assert(lhs != remainder && lhs != srhs && remainder != srhs);

  shiftCount = tcMSB(rhs, parts) + 1;
  if (shiftCount == 0)
    return true;

  shiftCount = parts * integerPartWidth - shiftCount;
  n = shiftCount / integerPartWidth;
  mask = (integerPart) 1 << (shiftCount % integerPartWidth);

  tcAssign(srhs, rhs, parts);
  tcShiftLeft(srhs, parts, shiftCount);
  tcAssign(remainder, lhs, parts);
  tcSet(lhs, 0, parts);

  /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
     the total.  */
  for(;;) {
      int compare;

      compare = tcCompare(remainder, srhs, parts);
      if (compare >= 0) {
        tcSubtract(remainder, srhs, 0, parts);
        lhs[n] |= mask;
      }

      if (shiftCount == 0)
        break;
      shiftCount--;
      tcShiftRight(srhs, parts, 1);
      if ((mask >>= 1) == 0)
        mask = (integerPart) 1 << (integerPartWidth - 1), n--;
  }

  return false;
}

/* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
   There are no restrictions on COUNT.  */
void
APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
{
  if (count) {
    unsigned int jump, shift;

    /* Jump is the inter-part jump; shift is is intra-part shift.  */
    jump = count / integerPartWidth;
    shift = count % integerPartWidth;

    while (parts > jump) {
      integerPart part;

      parts--;

      /* dst[i] comes from the two parts src[i - jump] and, if we have
         an intra-part shift, src[i - jump - 1].  */
      part = dst[parts - jump];
      if (shift) {
        part <<= shift;
        if (parts >= jump + 1)
          part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
      }

      dst[parts] = part;
    }

    while (parts > 0)
      dst[--parts] = 0;
  }
}

/* Shift a bignum right COUNT bits in-place.  Shifted in bits are
   zero.  There are no restrictions on COUNT.  */
void
APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
{
  if (count) {
    unsigned int i, jump, shift;

    /* Jump is the inter-part jump; shift is is intra-part shift.  */
    jump = count / integerPartWidth;
    shift = count % integerPartWidth;

    /* Perform the shift.  This leaves the most significant COUNT bits
       of the result at zero.  */
    for(i = 0; i < parts; i++) {
      integerPart part;

      if (i + jump >= parts) {
        part = 0;
      } else {
        part = dst[i + jump];
        if (shift) {
          part >>= shift;
          if (i + jump + 1 < parts)
            part |= dst[i + jump + 1] << (integerPartWidth - shift);
        }
      }

      dst[i] = part;
    }
  }
}

/* Bitwise and of two bignums.  */
void
APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    dst[i] &= rhs[i];
}

/* Bitwise inclusive or of two bignums.  */
void
APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    dst[i] |= rhs[i];
}

/* Bitwise exclusive or of two bignums.  */
void
APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    dst[i] ^= rhs[i];
}

/* Complement a bignum in-place.  */
void
APInt::tcComplement(integerPart *dst, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    dst[i] = ~dst[i];
}

/* Comparison (unsigned) of two bignums.  */
int
APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
                 unsigned int parts)
{
  while (parts) {
      parts--;
      if (lhs[parts] == rhs[parts])
        continue;

      if (lhs[parts] > rhs[parts])
        return 1;
      else
        return -1;
    }

  return 0;
}

/* Increment a bignum in-place, return the carry flag.  */
integerPart
APInt::tcIncrement(integerPart *dst, unsigned int parts)
{
  unsigned int i;

  for(i = 0; i < parts; i++)
    if (++dst[i] != 0)
      break;

  return i == parts;
}

/* Set the least significant BITS bits of a bignum, clear the
   rest.  */
void
APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
                                 unsigned int bits)
{
  unsigned int i;

  i = 0;
  while (bits > integerPartWidth) {
    dst[i++] = ~(integerPart) 0;
    bits -= integerPartWidth;
  }

  if (bits)
    dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);

  while (i < parts)
    dst[i++] = 0;
}