clearUnusedBits();
}
-APInt::APInt(unsigned numbits, const StringRef& Str, uint8_t radix)
+APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
: BitWidth(numbits), VAL(0) {
assert(BitWidth && "Bitwidth too small");
fromString(numbits, Str, radix);
return clearUnusedBits();
}
-/// Multiplies an integer array, x by a a uint64_t integer and places the result
+/// Multiplies an integer array, x, by 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.
unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
if (!rhsWords) {
// X * 0 ===> 0
- clear();
+ clearAllBits();
return *this;
}
mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
// Copy result back into *this
- clear();
+ clearAllBits();
unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
}
bool APInt::operator[](unsigned bitPosition) const {
+ assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
return (maskBit(bitPosition) &
(isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
}
bool rhsNeg = rhs.isNegative();
if (lhsNeg) {
// Sign bit is set so perform two's complement to make it positive
- lhs.flip();
+ lhs.flipAllBits();
lhs++;
}
if (rhsNeg) {
// Sign bit is set so perform two's complement to make it positive
- rhs.flip();
+ rhs.flipAllBits();
rhs++;
}
return lhs.ult(rhs);
}
-APInt& APInt::set(unsigned bitPosition) {
+void APInt::setBit(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) {
+void APInt::clearBit(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) {
+void APInt::flipBit(unsigned bitPosition) {
assert(bitPosition < BitWidth && "Out of the bit-width range!");
- if ((*this)[bitPosition]) clear(bitPosition);
- else set(bitPosition);
- return *this;
+ if ((*this)[bitPosition]) clearBit(bitPosition);
+ else setBit(bitPosition);
}
-unsigned APInt::getBitsNeeded(const StringRef& str, uint8_t radix) {
+unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
assert(!str.empty() && "Invalid string length");
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
"Radix should be 2, 8, 10, or 16!");
a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
/*------------------------------------------------- handle most of the key */
- while (length > 3)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 3;
- k += 3;
- }
+ while (length > 3) {
+ a += k[0];
+ b += k[1];
+ c += k[2];
+ mix(a,b,c);
+ length -= 3;
+ k += 3;
+ }
/*------------------------------------------- handle the last 3 uint32_t's */
switch (length) { /* all the case statements fall through */
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) {
+ // Treat the most significand word differently because it might have
+ // meaningless bits set beyond the precision.
+ 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 {
break;
}
}
- unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
- if (remainder)
- Count -= APINT_BITS_PER_WORD - remainder;
- return std::min(Count, BitWidth);
+ return Count;
}
static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
}
// Truncate to new width.
-APInt &APInt::trunc(unsigned width) {
+APInt APInt::trunc(unsigned width) const {
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();
+
+ if (width <= APINT_BITS_PER_WORD)
+ return APInt(width, getRawData()[0]);
+
+ APInt Result(getMemory(getNumWords(width)), width);
+
+ // Copy full words.
+ unsigned i;
+ for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
+ Result.pVal[i] = pVal[i];
+
+ // Truncate and copy any partial word.
+ unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
+ if (bits != 0)
+ Result.pVal[i] = pVal[i] << bits >> bits;
+
+ return Result;
}
// Sign extend to a new width.
-APInt &APInt::sext(unsigned width) {
+APInt APInt::sext(unsigned width) const {
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;
+
+ 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));
}
- // 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();
+ APInt Result(getMemory(getNumWords(width)), width);
+
+ // Copy full words.
+ unsigned i;
+ uint64_t word = 0;
+ for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
+ word = getRawData()[i];
+ Result.pVal[i] = word;
}
- 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;
+ // Read and sign-extend any partial 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);
+
+ // Write remaining full words.
+ for (; i != width / APINT_BITS_PER_WORD; i++) {
+ Result.pVal[i] = word;
+ word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
}
- for (unsigned i = wordsBefore; i < wordsAfter; i++)
- newVal[i] = -1ULL;
- if (wordsBefore != 1)
- delete [] pVal;
- pVal = newVal;
- return clearUnusedBits();
+
+ // Write any partial word.
+ bits = (0 - width) % APINT_BITS_PER_WORD;
+ if (bits != 0)
+ Result.pVal[i] = word << bits >> bits;
+
+ return Result;
}
// Zero extend to a new width.
-APInt &APInt::zext(unsigned width) {
+APInt APInt::zext(unsigned width) const {
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;
+
+ if (width <= APINT_BITS_PER_WORD)
+ return APInt(width, VAL);
+
+ APInt Result(getMemory(getNumWords(width)), width);
+
+ // Copy words.
+ unsigned i;
+ for (i = 0; i != getNumWords(); i++)
+ Result.pVal[i] = getRawData()[i];
+
+ // Zero remaining words.
+ memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
+
+ return Result;
}
-APInt &APInt::zextOrTrunc(unsigned width) {
+APInt APInt::zextOrTrunc(unsigned width) const {
if (BitWidth < width)
return zext(width);
if (BitWidth > width)
return *this;
}
-APInt &APInt::sextOrTrunc(unsigned width) {
+APInt APInt::sextOrTrunc(unsigned width) const {
if (BitWidth < width)
return sext(width);
if (BitWidth > width)
// 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().
+#if HAVE_ROUND
return APInt(BitWidth,
- uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
+ uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
#else
return APInt(BitWidth,
- uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
+ uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
#endif
}
// 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
+ // and 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. Furthermore, casting the 64-bit values to 32-bit values won't
if (!Quotient->isSingleWord())
Quotient->pVal = getClearedMemory(Quotient->getNumWords());
} else
- Quotient->clear();
+ Quotient->clearAllBits();
// The quotient is in Q. Reconstitute the quotient into Quotient's low
// order words.
if (!Remainder->isSingleWord())
Remainder->pVal = getClearedMemory(Remainder->getNumWords());
} else
- Remainder->clear();
+ Remainder->clearAllBits();
// The remainder is in R. Reconstitute the remainder into Remainder's low
// order words.
divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
}
-void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) {
+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 {
+ // MININT/-1 --> overflow.
+ 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::sshl_ov(unsigned ShAmt, bool &Overflow) const {
+ Overflow = ShAmt >= getBitWidth();
+ if (Overflow)
+ ShAmt = getBitWidth()-1;
+
+ if (isNonNegative()) // Don't allow sign change.
+ Overflow = ShAmt >= countLeadingZeros();
+ else
+ Overflow = ShAmt >= countLeadingOnes();
+
+ return *this << ShAmt;
+}
+
+
+
+
+void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
// Check our assumptions here
assert(!str.empty() && "Invalid string length");
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
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");
+ assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
+ "Insufficient bit width");
// Allocate memory
if (!isSingleWord())
// If its negative, put it in two's complement form
if (isNeg) {
(*this)--;
- this->flip();
+ this->flipAllBits();
}
}
char *BufPtr = Buffer+65;
uint64_t N;
- if (Signed) {
+ if (!Signed) {
+ N = getZExtValue();
+ } else {
int64_t I = getSExtValue();
- if (I < 0) {
+ if (I >= 0) {
+ N = I;
+ } else {
Str.push_back('-');
- I = -I;
+ N = -(uint64_t)I;
}
- N = I;
- } else {
- N = getZExtValue();
}
while (N) {
// 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.flipAllBits();
Tmp++;
Str.push_back('-');
}
static inline integerPart
lowBitMask(unsigned int bits)
{
- assert (bits != 0 && bits <= integerPartWidth);
+ assert(bits != 0 && bits <= integerPartWidth);
return ~(integerPart) 0 >> (integerPartWidth - bits);
}
{
unsigned int i;
- assert (parts > 0);
+ assert(parts > 0);
dst[0] = part;
- for(i = 1; i < parts; i++)
+ for (i = 1; i < parts; i++)
dst[i] = 0;
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
dst[i] = src[i];
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
if (src[i])
return false;
int
APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
{
- return(parts[bit / integerPartWidth]
- & ((integerPart) 1 << bit % integerPartWidth)) != 0;
+ return (parts[bit / integerPartWidth] &
+ ((integerPart) 1 << bit % integerPartWidth)) != 0;
}
-/* Set the given bit of a bignum. */
+/* Set the given bit of a bignum. */
void
APInt::tcSetBit(integerPart *parts, unsigned int bit)
{
parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
}
+/* Clears the given bit of a bignum. */
+void
+APInt::tcClearBit(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
{
unsigned int i, lsb;
- for(i = 0; i < n; i++) {
+ for (i = 0; i < n; i++) {
if (parts[i] != 0) {
lsb = partLSB(parts[i]);
unsigned int msb;
do {
- --n;
+ --n;
- if (parts[n] != 0) {
- msb = partMSB(parts[n]);
+ if (parts[n] != 0) {
+ msb = partMSB(parts[n]);
- return msb + n * integerPartWidth;
- }
+ return msb + n * integerPartWidth;
+ }
} while (n);
return -1U;
unsigned int firstSrcPart, dstParts, shift, n;
dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
- assert (dstParts <= dstCount);
+ assert(dstParts <= dstCount);
firstSrcPart = srcLSB / integerPartWidth;
tcAssign (dst, src + firstSrcPart, dstParts);
assert(c <= 1);
- for(i = 0; i < parts; i++) {
+ for (i = 0; i < parts; i++) {
integerPart l;
l = dst[i];
assert(c <= 1);
- for(i = 0; i < parts; i++) {
+ for (i = 0; i < parts; i++) {
integerPart l;
l = dst[i];
/* N loops; minimum of dstParts and srcParts. */
n = dstParts < srcParts ? dstParts: srcParts;
- for(i = 0; i < n; i++) {
+ for (i = 0; i < n; i++) {
integerPart low, mid, high, srcPart;
/* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
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++)
+ for (; i < srcParts; i++)
if (src[i])
return 1;
overflow = 0;
tcSet(dst, 0, parts);
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
parts - i, true);
tcSet(dst, 0, rhsParts);
- for(n = 0; n < lhsParts; n++)
+ for (n = 0; n < lhsParts; n++)
tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
n = lhsParts + rhsParts;
/* Loop, subtracting SRHS if REMAINDER is greater and adding that to
the total. */
- for(;;) {
+ for (;;) {
int compare;
compare = tcCompare(remainder, srhs, parts);
/* Perform the shift. This leaves the most significant COUNT bits
of the result at zero. */
- for(i = 0; i < parts; i++) {
+ for (i = 0; i < parts; i++) {
integerPart part;
if (i + jump >= parts) {
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
dst[i] &= rhs[i];
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
dst[i] |= rhs[i];
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
dst[i] ^= rhs[i];
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
dst[i] = ~dst[i];
}
{
unsigned int i;
- for(i = 0; i < parts; i++)
+ for (i = 0; i < parts; i++)
if (++dst[i] != 0)
break;