//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "apint"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cmath>
-#include <limits>
-#include <cstring>
#include <cstdlib>
+#include <cstring>
+#include <limits>
using namespace llvm;
+#define DEBUG_TYPE "apint"
+
/// A utility function for allocating memory, checking for allocation failures,
/// and ensuring the contents are zeroed.
inline static uint64_t* getClearedMemory(unsigned numWords) {
if (lhsNeg) {
// Sign bit is set so perform two's complement to make it positive
lhs.flipAllBits();
- lhs++;
+ ++lhs;
}
if (rhsNeg) {
// Sign bit is set so perform two's complement to make it positive
rhs.flipAllBits();
- rhs++;
+ ++rhs;
}
// Now we have unsigned values to compare so do the comparison if necessary
unsigned i = getNumWords();
integerPart MSW = pVal[i-1] & MSWMask;
if (MSW)
- return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
+ return llvm::countLeadingZeros(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]);
+ Count += llvm::countLeadingZeros(pVal[i-1]);
break;
}
}
unsigned APInt::countTrailingZeros() const {
if (isSingleWord())
- return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
+ return std::min(unsigned(llvm::countTrailingZeros(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]);
+ Count += llvm::countTrailingZeros(pVal[i]);
return std::min(Count, BitWidth);
}
// to include in this word.
val[breakWord] = pVal[breakWord+offset] >> wordShift;
- // Deal with sign extenstion in the break word, and possibly the word before
+ // Deal with sign extension in the break word, and possibly the word before
// it.
if (isNegative()) {
if (wordShift > bitsInWord) {
// 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 shift = countLeadingZeros(v[n-1]);
unsigned v_carry = 0;
unsigned u_carry = 0;
if (shift) {
// 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;
+ unsigned *U = nullptr;
+ unsigned *V = nullptr;
+ unsigned *Q = nullptr;
+ unsigned *R = nullptr;
if ((Remainder?4:3)*n+2*m+1 <= 128) {
U = &SPACE[0];
V = &SPACE[m+n+1];
// 0 / X ===> 0
return APInt(BitWidth, 0);
else if (lhsWords < rhsWords || this->ult(RHS)) {
- // X / Y ===> 0, if X < Y
+ // X / Y ===> 0, iff X < Y
return APInt(BitWidth, 0);
} else if (*this == RHS) {
// X / X ===> 1
// 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);
+ divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
return Quotient;
}
+APInt APInt::sdiv(const APInt &RHS) const {
+ if (isNegative()) {
+ if (RHS.isNegative())
+ return (-(*this)).udiv(-RHS);
+ return -((-(*this)).udiv(RHS));
+ }
+ if (RHS.isNegative())
+ return -(this->udiv(-RHS));
+ return this->udiv(RHS);
+}
+
APInt APInt::urem(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
if (isSingleWord()) {
// 0 % Y ===> 0
return APInt(BitWidth, 0);
} else if (lhsWords < rhsWords || this->ult(RHS)) {
- // X % Y ===> X, if X < Y
+ // X % Y ===> X, iff X < Y
return *this;
} else if (*this == RHS) {
// X % X == 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);
+ divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
return Remainder;
}
+APInt APInt::srem(const APInt &RHS) const {
+ if (isNegative()) {
+ if (RHS.isNegative())
+ return -((-(*this)).urem(-RHS));
+ return -((-(*this)).urem(RHS));
+ }
+ if (RHS.isNegative())
+ return this->urem(-RHS);
+ return this->urem(RHS);
+}
+
void APInt::udivrem(const APInt &LHS, const APInt &RHS,
APInt &Quotient, APInt &Remainder) {
// Get some size facts about the dividend and divisor
}
if (lhsWords < rhsWords || LHS.ult(RHS)) {
- Remainder = LHS; // X % Y ===> X, if X < Y
- Quotient = 0; // X / Y ===> 0, if X < Y
+ Remainder = LHS; // X % Y ===> X, iff X < Y
+ Quotient = 0; // X / Y ===> 0, iff X < Y
return;
}
divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
}
+void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
+ APInt &Quotient, APInt &Remainder) {
+ if (LHS.isNegative()) {
+ if (RHS.isNegative())
+ APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
+ else {
+ APInt::udivrem(-LHS, RHS, Quotient, Remainder);
+ Quotient = -Quotient;
+ }
+ Remainder = -Remainder;
+ } else if (RHS.isNegative()) {
+ APInt::udivrem(LHS, -RHS, Quotient, Remainder);
+ Quotient = -Quotient;
+ } else {
+ APInt::udivrem(LHS, RHS, Quotient, Remainder);
+ }
+}
+
APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this+RHS;
Overflow = isNonNegative() == RHS.isNonNegative() &&
}
// If its negative, put it in two's complement form
if (isNeg) {
- (*this)--;
+ --(*this);
this->flipAllBits();
}
}
// Flip the bits and add one to turn it into the equivalent positive
// value and put a '-' in the result.
Tmp.flipAllBits();
- Tmp++;
+ ++Tmp;
Str.push_back('-');
}
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;
+ return findLastSet(value, ZB_Max);
}
/* Returns the bit number of the least significant set bit of a
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;
+ return findFirstSet(value, ZB_Max);
}
}
return i == parts;
}
+/* Decrement a bignum in-place, return the borrow flag. */
+integerPart
+APInt::tcDecrement(integerPart *dst, unsigned int parts) {
+ for (unsigned int i = 0; i < parts; i++) {
+ // If the current word is non-zero, then the decrement has no effect on the
+ // higher-order words of the integer and no borrow can occur. Exit early.
+ if (dst[i]--)
+ return 0;
+ }
+ // If every word was zero, then there is a borrow.
+ return 1;
+}
+
+
/* Set the least significant BITS bits of a bignum, clear the
rest. */
void