//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "apint"
#include "llvm/ADT/APInt.h"
-#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.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>
+#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) {
r = cdigit - 'a';
if (r <= radix - 11U)
return r + 10;
+
+ radix = 10;
}
r = cdigit - '0';
clearAllBits();
unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
+ clearUnusedBits();
// delete dest array and return
delete[] dest;
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();
+ return Result;
}
APInt APInt::operator+(const APInt& RHS) const {
return Result.clearUnusedBits();
}
-bool APInt::operator[](unsigned bitPosition) const {
- assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
- 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();
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
}
}
-// From http://www.burtleburtle.net, byBob Jenkins.
-// When targeting x86, both GCC and LLVM seem to recognize this as a
-// rotate instruction.
-#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
-
-// From http://www.burtleburtle.net, by Bob Jenkins.
-#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; \
- }
-
-// From http://www.burtleburtle.net, by Bob Jenkins.
-#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); \
- }
-
-// hashword() was adapted from http://www.burtleburtle.net, by Bob
-// Jenkins. k is a pointer to an array of uint32_t values; length is
-// the length of the key, in 32-bit chunks. This version only handles
-// keys that are a multiple of 32 bits in size.
-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;
-
- /* Set up the internal state */
- 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;
- }
-
- /*------------------------------------------- handle the last 3 uint32_t's */
- switch (length) { /* all the case statements fall through */
- case 3 : c+=k[2];
- case 2 : b+=k[1];
- case 1 : a+=k[0];
- final(a,b,c);
- case 0: /* case 0: nothing left to add */
- break;
- }
- /*------------------------------------------------------ report the result */
- return c;
-}
-
-// hashword8() was adapted from http://www.burtleburtle.net, by Bob
-// Jenkins. This computes a 32-bit hash from one 64-bit word. When
-// targeting x86 (32 or 64 bit), both LLVM and GCC compile this
-// function into about 35 instructions when inlined.
-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
+hash_code llvm::hash_value(const APInt &Arg) {
+ if (Arg.isSingleWord())
+ return hash_combine(Arg.VAL);
-uint64_t APInt::getHashValue() const {
- uint64_t hash;
- if (isSingleWord())
- hash = hashword8(VAL);
- else
- hash = hashword(pVal, getNumWords()*2);
- return hash;
+ return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
}
/// HiBits - This function returns the high "numBits" bits of this APInt.
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;
}
}
return Count;
}
-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);
+ return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
unsigned shift;
shift = APINT_BITS_PER_WORD - highWordBits;
}
int i = getNumWords() - 1;
- unsigned Count = countLeadingOnes_64(pVal[i], shift);
+ 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);
+ Count += CountLeadingOnes_64(pVal[i]);
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);
}
return Count;
}
+/// Perform a logical right-shift from Src to Dst, which must be equal or
+/// non-overlapping, of Words words, by Shift, which must be less than 64.
+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)));
- else if (BitWidth == 32)
+ if (BitWidth == 32)
return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
- else if (BitWidth == 48) {
+ 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)
+ }
+ 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 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,
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;
+}
+
/// Arithmetic right-shift this APInt by shiftAmt.
/// @brief Arithmetic right-shift function.
APInt APInt::ashr(const APInt &shiftAmt) const {
// 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) {
/// @brief Logical right-shift function.
APInt APInt::lshr(unsigned shiftAmt) const {
if (isSingleWord()) {
- if (shiftAmt == BitWidth)
+ 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)
+ if (shiftAmt >= BitWidth)
return APInt(BitWidth, 0);
// If none of the bits are shifted out, the result is *this. This avoids
// 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);
- }
+ lshrNear(val, pVal, getNumWords(), shiftAmt);
return APInt(val, BitWidth).clearUnusedBits();
}
}
APInt APInt::rotl(unsigned rotateAmt) const {
+ rotateAmt %= BitWidth;
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;
+ return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
}
APInt APInt::rotr(const APInt &rotateAmt) const {
}
APInt APInt::rotr(unsigned rotateAmt) const {
+ rotateAmt %= BitWidth;
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;
+ return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
}
// Square Root - this method computes and returns the square root of "this".
// 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.
+ // 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 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
- llvm_unreachable("Error in APInt::sqrt computation");
+ 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 signedMin = APInt::getSignedMinValue(d.getBitWidth());
APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
- nc = allOnes - (-d).urem(d);
+ nc = allOnes - (allOnes - d).urem(d);
p = d.getBitWidth() - 1; // initialize p
q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
// 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];
// 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()) {
// 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
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();
}
}
bool Signed, bool formatAsCLiteral) const {
assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
Radix == 36) &&
- "Radix should be 2, 8, 10, or 16!");
+ "Radix should be 2, 8, 10, 16, or 36!");
const char *Prefix = "";
if (formatAsCLiteral) {
case 8:
Prefix = "0";
break;
+ case 10:
+ break; // No prefix
case 16:
Prefix = "0x";
break;
+ default:
+ llvm_unreachable("Invalid radix!");
}
}
// 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
projects / oota-llvm.git / blobdiff