#define DEBUG_TYPE "apint"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cmath>
#include <limits>
#include <cstring>
#include <cstdlib>
using namespace llvm;
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;
}
inline static uint64_t* getMemory(unsigned numWords) {
uint64_t * result = new uint64_t[numWords];
assert(result && "APInt memory allocation fails!");
return result;
}
inline static unsigned getDigit(char cdigit, uint8_t radix) {
unsigned r;
if (radix == 16 || radix == 36) {
r = cdigit - '0';
if (r <= 9)
return r;
r = cdigit - 'A';
if (r <= radix - 11U)
return r + 10;
r = cdigit - 'a';
if (r <= radix - 11U)
return r + 10;
radix = 10;
}
r = cdigit - '0';
if (r < radix)
return r;
return -1U;
}
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);
}
void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
assert(BitWidth && "Bitwidth too small");
assert(bigVal.data() && "Null pointer detected!");
if (isSingleWord())
VAL = bigVal[0];
else {
pVal = getClearedMemory(getNumWords());
unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
}
clearUnusedBits();
}
APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
: BitWidth(numBits), VAL(0) {
initFromArray(bigVal);
}
APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
: BitWidth(numBits), VAL(0) {
initFromArray(makeArrayRef(bigVal, numWords));
}
APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
: BitWidth(numbits), VAL(0) {
assert(BitWidth && "Bitwidth too small");
fromString(numbits, Str, radix);
}
APInt& APInt::AssignSlowCase(const APInt& RHS) {
if (this == &RHS)
return *this;
if (BitWidth == RHS.getBitWidth()) {
assert(!isSingleWord());
memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
return *this;
}
if (isSingleWord()) {
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();
}
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]);
}
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; else {
y = 0; break;
}
}
return y;
}
APInt& APInt::operator++() {
if (isSingleWord())
++VAL;
else
add_1(pVal, pVal, getNumWords(), 1);
return clearUnusedBits();
}
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; else {
y = 0; break; }
}
return bool(y);
}
APInt& APInt::operator--() {
if (isSingleWord())
--VAL;
else
sub_1(pVal, getNumWords(), 1);
return clearUnusedBits();
}
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]); dest[i] = x[i] + y[i] + carry;
carry = dest[i] < limit || (carry && dest[i] == limit);
}
return carry;
}
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();
}
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;
}
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();
}
static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
uint64_t carry = 0;
for (unsigned i = 0; i < len; ++i) {
uint64_t lx = x[i] & 0xffffffffULL;
uint64_t hx = x[i] >> 32;
uint8_t hasCarry = 0;
dest[i] = carry + lx * ly;
hasCarry = (dest[i] < carry) ? 1 : 0;
carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
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;
}
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;
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;
}
unsigned lhsBits = getActiveBits();
unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
if (!lhsWords)
return *this;
unsigned rhsBits = RHS.getActiveBits();
unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
if (!rhsWords) {
clearAllBits();
return *this;
}
unsigned destWords = rhsWords + lhsWords;
uint64_t *dest = getMemory(destWords);
mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
clearAllBits();
unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
clearUnusedBits();
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];
return APInt(val, getBitWidth()).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(*this);
Result *= RHS;
return Result;
}
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::EqualSlowCase(const APInt& RHS) const {
unsigned n1 = getActiveBits();
unsigned n2 = RHS.getActiveBits();
if (n1 != n2)
return false;
if (n1 <= APINT_BITS_PER_WORD)
return pVal[0] == RHS.pVal[0];
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;
unsigned n1 = getActiveBits();
unsigned n2 = RHS.getActiveBits();
if (n1 < n2)
return true;
if (n2 < n1)
return false;
if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
return pVal[0] < RHS.pVal[0];
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) {
lhs.flipAllBits();
lhs++;
}
if (rhsNeg) {
rhs.flipAllBits();
rhs++;
}
if (lhsNeg)
if (rhsNeg)
return lhs.ugt(rhs);
else
return true;
else if (rhsNeg)
return false;
else
return lhs.ult(rhs);
}
void APInt::setBit(unsigned bitPosition) {
if (isSingleWord())
VAL |= maskBit(bitPosition);
else
pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
}
void APInt::clearBit(unsigned bitPosition) {
if (isSingleWord())
VAL &= ~maskBit(bitPosition);
else
pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
}
void APInt::flipBit(unsigned bitPosition) {
assert(bitPosition < BitWidth && "Out of the bit-width range!");
if ((*this)[bitPosition]) clearBit(bitPosition);
else setBit(bitPosition);
}
unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
assert(!str.empty() && "Invalid string length");
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
radix == 36) &&
"Radix should be 2, 8, 10, 16, or 36!");
size_t slen = str.size();
StringRef::iterator p = str.begin();
unsigned isNegative = *p == '-';
if (*p == '-' || *p == '+') {
p++;
slen--;
assert(slen && "String is only a sign, needs a value.");
}
if (radix == 2)
return slen + isNegative;
if (radix == 8)
return slen * 3 + isNegative;
if (radix == 16)
return slen * 4 + isNegative;
unsigned sufficient
= radix == 10? (slen == 1 ? 4 : slen * 64/18)
: (slen == 1 ? 7 : slen * 16/3);
APInt tmp(sufficient, StringRef(p, slen), radix);
unsigned log = tmp.logBase2();
if (log == (unsigned)-1) {
return isNegative + 1;
} else {
return isNegative + log + 1;
}
}
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
#define mix(a,b,c) \
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
#define final(a,b,c) \
{ \
c ^= b; c -= rot(b,14); \
a ^= c; a -= rot(c,11); \
b ^= a; b -= rot(a,25); \
c ^= b; c -= rot(b,16); \
a ^= c; a -= rot(c,4); \
b ^= a; b -= rot(a,14); \
c ^= b; c -= rot(b,24); \
}
static inline uint32_t hashword(const uint64_t *k64, size_t length)
{
const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
uint32_t a,b,c;
a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
while (length > 3) {
a += k[0];
b += k[1];
c += k[2];
mix(a,b,c);
length -= 3;
k += 3;
}
switch (length) {
case 3 : c+=k[2];
case 2 : b+=k[1];
case 1 : a+=k[0];
final(a,b,c);
case 0:
break;
}
return c;
}
static inline uint32_t hashword8(const uint64_t k64)
{
uint32_t a,b,c;
a = b = c = 0xdeadbeef + 4;
b += k64 >> 32;
a += k64 & 0xffffffff;
final(a,b,c);
return c;
}
#undef final
#undef mix
#undef rot
uint64_t APInt::getHashValue() const {
uint64_t hash;
if (isSingleWord())
hash = hashword8(VAL);
else
hash = hashword(pVal, getNumWords()*2);
return hash;
}
APInt APInt::getHiBits(unsigned numBits) const {
return APIntOps::lshr(*this, BitWidth - numBits);
}
APInt APInt::getLoBits(unsigned numBits) const {
return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
BitWidth - numBits);
}
unsigned APInt::countLeadingZerosSlowCase() const {
unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
integerPart MSWMask;
if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
else {
MSWMask = ~integerPart(0);
BitsInMSW = APINT_BITS_PER_WORD;
}
unsigned i = getNumWords();
integerPart MSW = pVal[i-1] & MSWMask;
if (MSW)
return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
unsigned Count = BitsInMSW;
for (--i; i > 0u; --i) {
if (pVal[i-1] == 0)
Count += APINT_BITS_PER_WORD;
else {
Count += CountLeadingZeros_64(pVal[i-1]);
break;
}
}
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;
if (!highWordBits) {
highWordBits = APINT_BITS_PER_WORD;
shift = 0;
} else {
shift = 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]);
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;
}
static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
unsigned Shift) {
uint64_t Carry = 0;
for (int I = Words - 1; I >= 0; --I) {
uint64_t Tmp = Src[I];
Dst[I] = (Tmp >> Shift) | Carry;
Carry = Tmp << (64 - Shift);
}
}
APInt APInt::byteSwap() const {
assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
if (BitWidth == 16)
return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
if (BitWidth == 32)
return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
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);
}
if (BitWidth == 64)
return APInt(BitWidth, ByteSwap_64(VAL));
APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
for (unsigned I = 0, N = getNumWords(); I != N; ++I)
Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
if (Result.BitWidth != BitWidth) {
lshrNear(Result.pVal, Result.pVal, getNumWords(),
Result.BitWidth - BitWidth);
Result.BitWidth = BitWidth;
}
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;
bool isNeg = T.I >> 63;
int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
if (exp < 0)
return APInt(width, 0u);
uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
if (exp < 52)
return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
APInt(width, mantissa >> (52 - exp));
if (width <= exp - 52)
return APInt(width, 0);
APInt Tmp(width, mantissa);
Tmp = Tmp.shl((unsigned)exp - 52);
return isNeg ? -Tmp : Tmp;
}
double APInt::roundToDouble(bool isSigned) const {
if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
if (isSigned) {
int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
return double(sext);
} else
return double(getWord(0));
}
bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
APInt Tmp(isNeg ? -(*this) : (*this));
unsigned n = Tmp.getActiveBits();
uint64_t exp = n;
if (exp > 1023) {
if (!isSigned || !isNeg)
return std::numeric_limits<double>::infinity();
else
return -std::numeric_limits<double>::infinity();
}
exp += 1023;
uint64_t mantissa;
unsigned hiWord = whichWord(n-1);
if (hiWord == 0) {
mantissa = Tmp.pVal[0];
if (n > 52)
mantissa >>= n - 52; } 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;
}
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;
}
APInt APInt::trunc(unsigned width) const {
assert(width < BitWidth && "Invalid APInt Truncate request");
assert(width && "Can't truncate to 0 bits");
if (width <= APINT_BITS_PER_WORD)
return APInt(width, getRawData()[0]);
APInt Result(getMemory(getNumWords(width)), width);
unsigned i;
for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
Result.pVal[i] = pVal[i];
unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
if (bits != 0)
Result.pVal[i] = pVal[i] << bits >> bits;
return Result;
}
APInt APInt::sext(unsigned width) const {
assert(width > BitWidth && "Invalid APInt SignExtend request");
if (width <= APINT_BITS_PER_WORD) {
uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
val = (int64_t)val >> (width - BitWidth);
return APInt(width, val >> (APINT_BITS_PER_WORD - width));
}
APInt Result(getMemory(getNumWords(width)), width);
unsigned i;
uint64_t word = 0;
for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
word = getRawData()[i];
Result.pVal[i] = word;
}
unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
if (bits != 0)
word = (int64_t)getRawData()[i] << bits >> bits;
else
word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
for (; i != width / APINT_BITS_PER_WORD; i++) {
Result.pVal[i] = word;
word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
}
bits = (0 - width) % APINT_BITS_PER_WORD;
if (bits != 0)
Result.pVal[i] = word << bits >> bits;
return Result;
}
APInt APInt::zext(unsigned width) const {
assert(width > BitWidth && "Invalid APInt ZeroExtend request");
if (width <= APINT_BITS_PER_WORD)
return APInt(width, VAL);
APInt Result(getMemory(getNumWords(width)), width);
unsigned i;
for (i = 0; i != getNumWords(); i++)
Result.pVal[i] = getRawData()[i];
memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
return Result;
}
APInt APInt::zextOrTrunc(unsigned width) const {
if (BitWidth < width)
return zext(width);
if (BitWidth > width)
return trunc(width);
return *this;
}
APInt APInt::sextOrTrunc(unsigned width) const {
if (BitWidth < width)
return sext(width);
if (BitWidth > width)
return trunc(width);
return *this;
}
APInt APInt::zextOrSelf(unsigned width) const {
if (BitWidth < width)
return zext(width);
return *this;
}
APInt APInt::sextOrSelf(unsigned width) const {
if (BitWidth < width)
return sext(width);
return *this;
}
APInt APInt::ashr(const APInt &shiftAmt) const {
return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
}
APInt APInt::ashr(unsigned shiftAmt) const {
assert(shiftAmt <= BitWidth && "Invalid shift amount");
if (shiftAmt == 0)
return *this;
if (isSingleWord()) {
if (shiftAmt == BitWidth)
return APInt(BitWidth, 0); else {
unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
return APInt(BitWidth,
(((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
}
}
if (shiftAmt == BitWidth) {
if (isNegative())
return APInt(BitWidth, -1ULL, true);
else
return APInt(BitWidth, 0);
}
uint64_t * val = new uint64_t[getNumWords()];
unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; unsigned offset = shiftAmt / APINT_BITS_PER_WORD; unsigned breakWord = getNumWords() - 1 - offset; unsigned bitsInWord = whichBit(BitWidth); if (bitsInWord == 0)
bitsInWord = APINT_BITS_PER_WORD;
if (wordShift == 0) {
for (unsigned i = 0; i <= breakWord; ++i)
val[i] = pVal[i+offset];
if (isNegative())
if (bitsInWord < APINT_BITS_PER_WORD)
val[breakWord] |= ~0ULL << bitsInWord; } else {
for (unsigned i = 0; i < breakWord; ++i) {
val[i] = (pVal[i+offset] >> wordShift) |
(pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
}
val[breakWord] = pVal[breakWord+offset] >> wordShift;
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));
}
}
uint64_t fillValue = (isNegative() ? -1ULL : 0);
for (unsigned i = breakWord+1; i < getNumWords(); ++i)
val[i] = fillValue;
return APInt(val, BitWidth).clearUnusedBits();
}
APInt APInt::lshr(const APInt &shiftAmt) const {
return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
}
APInt APInt::lshr(unsigned shiftAmt) const {
if (isSingleWord()) {
if (shiftAmt >= BitWidth)
return APInt(BitWidth, 0);
else
return APInt(BitWidth, this->VAL >> shiftAmt);
}
if (shiftAmt == BitWidth)
return APInt(BitWidth, 0);
if (shiftAmt == 0)
return *this;
uint64_t * val = new uint64_t[getNumWords()];
if (shiftAmt < APINT_BITS_PER_WORD) {
lshrNear(val, pVal, getNumWords(), shiftAmt);
return APInt(val, BitWidth).clearUnusedBits();
}
unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
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();
}
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));
val[breakWord] = pVal[breakWord+offset] >> wordShift;
for (unsigned i = breakWord+1; i < getNumWords(); ++i)
val[i] = 0;
return APInt(val, BitWidth).clearUnusedBits();
}
APInt APInt::shl(const APInt &shiftAmt) const {
return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
}
APInt APInt::shlSlowCase(unsigned shiftAmt) const {
if (shiftAmt == BitWidth)
return APInt(BitWidth, 0);
if (shiftAmt == 0)
return *this;
uint64_t * val = new uint64_t[getNumWords()];
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();
}
unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
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();
}
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 {
rotateAmt %= BitWidth;
if (rotateAmt == 0)
return *this;
return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
}
APInt APInt::rotr(const APInt &rotateAmt) const {
return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
}
APInt APInt::rotr(unsigned rotateAmt) const {
rotateAmt %= BitWidth;
if (rotateAmt == 0)
return *this;
return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
}
APInt APInt::sqrt() const {
unsigned magnitude = getActiveBits();
if (magnitude <= 5) {
static const uint8_t results[32] = {
0,
1, 1,
2, 2, 2, 2,
3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6
};
return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
}
if (magnitude < 52) {
#if HAVE_ROUND
return APInt(BitWidth,
uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
#else
return APInt(BitWidth,
uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
#endif
}
unsigned nbits = BitWidth, i = 4;
APInt testy(BitWidth, 16);
APInt x_old(BitWidth, 1);
APInt x_new(BitWidth, 0);
APInt two(BitWidth, 2);
for (;; i += 2, testy = testy.shl(2))
if (i >= nbits || this->ule(testy)) {
x_old = x_old.shl(i / 2);
break;
}
for (;;) {
x_new = (this->udiv(x_old) + x_old).udiv(two);
if (x_old.ule(x_new))
break;
x_old = x_new;
}
APInt square(x_old * x_old);
APInt nextSquare((x_old + 1) * (x_old +1));
if (this->ult(square))
return x_old;
assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
APInt midpoint((nextSquare - square).udiv(two));
APInt offset(*this - square);
if (offset.ult(midpoint))
return x_old;
return x_old + 1;
}
APInt APInt::multiplicativeInverse(const APInt& modulo) const {
assert(ult(modulo) && "This APInt must be smaller than the modulo");
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) {
udivrem(r[i], r[i^1], q, r[i]);
t[i] -= t[i^1] * q;
}
if (r[i] != 1)
return APInt(BitWidth, 0);
return t[i].isNegative() ? t[i] + modulo : t[i];
}
APInt::ms APInt::magic() const {
const APInt& d = *this;
unsigned p;
APInt ad, anc, delta, q1, r1, q2, r2, t;
APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
struct ms mag;
ad = d.abs();
t = signedMin + (d.lshr(d.getBitWidth() - 1));
anc = t - 1 - t.urem(ad); p = d.getBitWidth() - 1; q1 = signedMin.udiv(anc); r1 = signedMin - q1*anc; q2 = signedMin.udiv(ad); r2 = signedMin - q2*ad; do {
p = p + 1;
q1 = q1<<1; r1 = r1<<1; if (r1.uge(anc)) { q1 = q1 + 1;
r1 = r1 - anc;
}
q2 = q2<<1; r2 = r2<<1; if (r2.uge(ad)) { q2 = q2 + 1;
r2 = r2 - ad;
}
delta = ad - r2;
} while (q1.ult(delta) || (q1 == delta && r1 == 0));
mag.m = q2 + 1;
if (d.isNegative()) mag.m = -mag.m; mag.s = p - d.getBitWidth(); return mag;
}
APInt::mu APInt::magicu(unsigned LeadingZeros) const {
const APInt& d = *this;
unsigned p;
APInt nc, delta, q1, r1, q2, r2;
struct mu magu;
magu.a = 0; APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
nc = allOnes - (-d).urem(d);
p = d.getBitWidth() - 1; q1 = signedMin.udiv(nc); r1 = signedMin - q1*nc; q2 = signedMax.udiv(d); r2 = signedMax - q2*d; do {
p = p + 1;
if (r1.uge(nc - r1)) {
q1 = q1 + q1 + 1; r1 = r1 + r1 - nc; }
else {
q1 = q1+q1; r1 = r1+r1; }
if ((r2 + 1).uge(d - r2)) {
if (q2.uge(signedMax)) magu.a = 1;
q2 = q2+q2 + 1; r2 = r2+r2 + 1 - d; }
else {
if (q2.uge(signedMin)) magu.a = 1;
q2 = q2+q2; r2 = r2+r2 + 1; }
delta = d - 1 - r2;
} while (p < d.getBitWidth()*2 &&
(q1.ult(delta) || (q1 == delta && r1 == 0)));
magu.m = q2 + 1; magu.s = p - d.getBitWidth(); return magu;
}
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");
uint64_t b = uint64_t(1) << 32;
#if 0
DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
DEBUG(dbgs() << "KnuthDiv: original:");
DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
DEBUG(dbgs() << " by");
DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
DEBUG(dbgs() << '\n');
#endif
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(dbgs() << "KnuthDiv: normal:");
DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
DEBUG(dbgs() << " by");
DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
DEBUG(dbgs() << '\n');
#endif
int j = m;
do {
DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
DEBUG(dbgs() << "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(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
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(dbgs() << "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)); u[k++] = (unsigned)(result >> 32); while (borrow && k <= m+n) { borrow = u[k] == 0;
u[k]--;
k++;
}
isNeg |= borrow;
DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
u[j+i+1] << '\n');
}
DEBUG(dbgs() << "KnuthDiv: after subtraction:");
DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
DEBUG(dbgs() << '\n');
if (isNeg) {
bool carry = true; for (unsigned i = 0; i <= m+n; ++i) {
u[i] = ~u[i] + carry; carry = carry && u[i] == 0;
}
}
DEBUG(dbgs() << "KnuthDiv: after complement:");
DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
DEBUG(dbgs() << '\n');
q[j] = (unsigned)qp;
if (isNeg) {
q[j]--;
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(dbgs() << "KnuthDiv: after correction:");
DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
} while (--j >= 0);
DEBUG(dbgs() << "KnuthDiv: quotient:");
DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
DEBUG(dbgs() << '\n');
if (r) {
if (shift) {
unsigned carry = 0;
DEBUG(dbgs() << "KnuthDiv: remainder:");
for (int i = n-1; i >= 0; i--) {
r[i] = (u[i] >> shift) | carry;
carry = u[i] << (32 - shift);
DEBUG(dbgs() << " " << r[i]);
}
} else {
for (int i = n-1; i >= 0; i--) {
r[i] = u[i];
DEBUG(dbgs() << " " << r[i]);
}
}
DEBUG(dbgs() << '\n');
}
#if 0
DEBUG(dbgs() << '\n');
#endif
}
void APInt::divide(const APInt LHS, unsigned lhsWords,
const APInt &RHS, unsigned rhsWords,
APInt *Quotient, APInt *Remainder)
{
assert(lhsWords >= rhsWords && "Fractional result");
uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
unsigned n = rhsWords * 2;
unsigned m = (lhsWords * 2) - n;
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];
}
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)*CHAR_BIT));
}
U[m+n] = 0;
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)*CHAR_BIT));
}
memset(Q, 0, (m+n) * sizeof(unsigned));
if (Remainder)
memset(R, 0, n * sizeof(unsigned));
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--;
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 {
KnuthDiv(U, V, Q, R, m, n);
}
if (Quotient) {
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->clearAllBits();
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 (Remainder) {
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->clearAllBits();
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));
}
}
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");
if (isSingleWord()) {
assert(RHS.VAL != 0 && "Divide by zero?");
return APInt(BitWidth, VAL / RHS.VAL);
}
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);
if (!lhsWords)
return APInt(BitWidth, 0);
else if (lhsWords < rhsWords || this->ult(RHS)) {
return APInt(BitWidth, 0);
} else if (*this == RHS) {
return APInt(BitWidth, 1);
} else if (lhsWords == 1 && rhsWords == 1) {
return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
}
APInt Quotient(1,0); 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);
}
unsigned lhsBits = getActiveBits();
unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
unsigned rhsBits = RHS.getActiveBits();
unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
assert(rhsWords && "Performing remainder operation by zero ???");
if (lhsWords == 0) {
return APInt(BitWidth, 0);
} else if (lhsWords < rhsWords || this->ult(RHS)) {
return *this;
} else if (*this == RHS) {
return APInt(BitWidth, 0);
} else if (lhsWords == 1) {
return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
}
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) {
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);
if (lhsWords == 0) {
Quotient = 0; Remainder = 0; return;
}
if (lhsWords < rhsWords || LHS.ult(RHS)) {
Remainder = LHS; Quotient = 0; return;
}
if (LHS == RHS) {
Quotient = 1; Remainder = 0; return;
}
if (lhsWords == 1 && rhsWords == 1) {
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;
}
divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
}
APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this+RHS;
Overflow = isNonNegative() == RHS.isNonNegative() &&
Res.isNonNegative() != isNonNegative();
return Res;
}
APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this+RHS;
Overflow = Res.ult(RHS);
return Res;
}
APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this - RHS;
Overflow = isNonNegative() != RHS.isNonNegative() &&
Res.isNonNegative() != isNonNegative();
return Res;
}
APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this-RHS;
Overflow = Res.ugt(*this);
return Res;
}
APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
Overflow = isMinSignedValue() && RHS.isAllOnesValue();
return sdiv(RHS);
}
APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this * RHS;
if (*this != 0 && RHS != 0)
Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
else
Overflow = false;
return Res;
}
APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this * RHS;
if (*this != 0 && RHS != 0)
Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
else
Overflow = false;
return Res;
}
APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
Overflow = ShAmt >= getBitWidth();
if (Overflow)
ShAmt = getBitWidth()-1;
if (isNonNegative()) Overflow = ShAmt >= countLeadingZeros();
else
Overflow = ShAmt >= countLeadingOnes();
return *this << ShAmt;
}
void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
assert(!str.empty() && "Invalid string length");
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
radix == 36) &&
"Radix should be 2, 8, 10, 16, or 36!");
StringRef::iterator p = str.begin();
size_t slen = str.size();
bool isNeg = *p == '-';
if (*p == '-' || *p == '+') {
p++;
slen--;
assert(slen && "String is only a sign, needs a value.");
}
assert((slen <= numbits || radix != 2) && "Insufficient bit width");
assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
"Insufficient bit width");
if (!isSingleWord())
pVal = getClearedMemory(getNumWords());
unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
APInt apdigit(getBitWidth(), 0);
APInt apradix(getBitWidth(), radix);
for (StringRef::iterator e = str.end(); p != e; ++p) {
unsigned digit = getDigit(*p, radix);
assert(digit < radix && "Invalid character in digit string");
if (slen > 1) {
if (shift)
*this <<= shift;
else
*this *= apradix;
}
if (apdigit.isSingleWord())
apdigit.VAL = digit;
else
apdigit.pVal[0] = digit;
*this += apdigit;
}
if (isNeg) {
(*this)--;
this->flipAllBits();
}
}
void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
bool Signed, bool formatAsCLiteral) const {
assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
Radix == 36) &&
"Radix should be 2, 8, 10, 16, or 36!");
const char *Prefix = "";
if (formatAsCLiteral) {
switch (Radix) {
case 2:
Prefix = "0b";
break;
case 8:
Prefix = "0";
break;
case 10:
break; case 16:
Prefix = "0x";
break;
default:
llvm_unreachable("Invalid radix!");
}
}
if (*this == 0) {
while (*Prefix) {
Str.push_back(*Prefix);
++Prefix;
};
Str.push_back('0');
return;
}
static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if (isSingleWord()) {
char Buffer[65];
char *BufPtr = Buffer+65;
uint64_t N;
if (!Signed) {
N = getZExtValue();
} else {
int64_t I = getSExtValue();
if (I >= 0) {
N = I;
} else {
Str.push_back('-');
N = -(uint64_t)I;
}
}
while (*Prefix) {
Str.push_back(*Prefix);
++Prefix;
};
while (N) {
*--BufPtr = Digits[N % Radix];
N /= Radix;
}
Str.append(BufPtr, Buffer+65);
return;
}
APInt Tmp(*this);
if (Signed && isNegative()) {
Tmp.flipAllBits();
Tmp++;
Str.push_back('-');
}
while (*Prefix) {
Str.push_back(*Prefix);
++Prefix;
};
unsigned StartDig = Str.size();
if (Radix == 2 || Radix == 8 || Radix == 16) {
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(Radix == 10? 4 : 8, Radix);
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;
}
}
std::reverse(Str.begin()+StartDig, Str.end());
}
std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
SmallString<40> S;
toString(S, Radix, Signed, false);
return S.str();
}
void APInt::dump() const {
SmallString<40> S, U;
this->toStringUnsigned(U);
this->toStringSigned(S);
dbgs() << "APInt(" << BitWidth << "b, "
<< U.str() << "u " << S.str() << "s)";
}
void APInt::print(raw_ostream &OS, bool isSigned) const {
SmallString<40> S;
this->toString(S, 10, isSigned, false);
OS << S.str();
}
#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
namespace {
static inline integerPart
lowBitMask(unsigned int bits)
{
assert(bits != 0 && bits <= integerPartWidth);
return ~(integerPart) 0 >> (integerPartWidth - bits);
}
static inline integerPart
lowHalf(integerPart part)
{
return part & lowBitMask(integerPartWidth / 2);
}
static inline integerPart
highHalf(integerPart part)
{
return part >> (integerPartWidth / 2);
}
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;
}
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;
}
}
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;
}
void
APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
{
unsigned int i;
for (i = 0; i < parts; i++)
dst[i] = src[i];
}
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;
}
int
APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
{
return (parts[bit / integerPartWidth] &
((integerPart) 1 << bit % integerPartWidth)) != 0;
}
void
APInt::tcSetBit(integerPart *parts, unsigned int bit)
{
parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
}
void
APInt::tcClearBit(integerPart *parts, unsigned int bit)
{
parts[bit / integerPartWidth] &=
~((integerPart) 1 << (bit % integerPartWidth));
}
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;
}
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;
}
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);
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);
}
while (dstParts < dstCount)
dst[dstParts++] = 0;
}
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;
}
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;
}
void
APInt::tcNegate(integerPart *dst, unsigned int parts)
{
tcComplement(dst, parts);
tcIncrement(dst, parts);
}
int
APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
integerPart multiplier, integerPart carry,
unsigned int srcParts, unsigned int dstParts,
bool add)
{
unsigned int i, n;
assert(dst <= src || dst >= src + srcParts);
assert(dstParts <= srcParts + 1);
n = dstParts < srcParts ? dstParts: srcParts;
for (i = 0; i < n; i++) {
integerPart low, mid, high, srcPart;
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;
if (low + carry < low)
high++;
low += carry;
}
if (add) {
if (low + dst[i] < low)
high++;
dst[i] += low;
} else
dst[i] = low;
carry = high;
}
if (i < dstParts) {
assert(i + 1 == dstParts);
dst[i] = carry;
return 0;
} else {
if (carry)
return 1;
if (multiplier)
for (; i < srcParts; i++)
if (src[i])
return 1;
return 0;
}
}
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;
}
unsigned int
APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
const integerPart *rhs, unsigned int lhsParts,
unsigned int rhsParts)
{
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);
}
}
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);
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;
}
void
APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
{
if (count) {
unsigned int jump, shift;
jump = count / integerPartWidth;
shift = count % integerPartWidth;
while (parts > jump) {
integerPart part;
parts--;
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;
}
}
void
APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
{
if (count) {
unsigned int i, jump, shift;
jump = count / integerPartWidth;
shift = count % integerPartWidth;
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;
}
}
}
void
APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
unsigned int i;
for (i = 0; i < parts; i++)
dst[i] &= rhs[i];
}
void
APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
unsigned int i;
for (i = 0; i < parts; i++)
dst[i] |= rhs[i];
}
void
APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
{
unsigned int i;
for (i = 0; i < parts; i++)
dst[i] ^= rhs[i];
}
void
APInt::tcComplement(integerPart *dst, unsigned int parts)
{
unsigned int i;
for (i = 0; i < parts; i++)
dst[i] = ~dst[i];
}
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;
}
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;
}
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;
}