#include <cassert>
#include <string>
+#define HOST_CHAR_BIT 8
+#define compileTimeAssert(cond) extern int CTAssert[(cond) ? 1 : -1]
+#define integerPartWidth (HOST_CHAR_BIT * sizeof(llvm::integerPart))
+
namespace llvm {
+ /* An unsigned host type used as a single part of a multi-part
+ bignum. */
+ typedef uint64_t integerPart;
+
//===----------------------------------------------------------------------===//
// APInt Class
//===----------------------------------------------------------------------===//
/// @param numBits the bit width of the constructed APInt
/// @param strStart the start of the string to be interpreted
/// @param slen the maximum number of characters to interpret
+ /// @param radix the radix to use for the conversion
/// @brief Construct an APInt from a string representation.
APInt(uint32_t numBits, const char strStart[], uint32_t slen, uint8_t radix);
/// @returns true if the argument APInt value is a power of two > 0.
bool isPowerOf2() const;
- /// This converts the APInt to a boolean valy as a test against zero.
+ /// isSignBit - Return true if this is the value returned by getSignBit.
+ bool isSignBit() const { return isMinSignedValue(); }
+
+ /// This converts the APInt to a boolean value as a test against zero.
/// @brief Boolean conversion function.
inline bool getBoolValue() const {
- return countLeadingZeros() != BitWidth;
+ return *this != 0;
+ }
+
+ /// getLimitedValue - If this value is smaller than the specified limit,
+ /// return it, otherwise return the limit value. This causes the value
+ /// to saturate to the limit.
+ uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const {
+ return (getActiveBits() > 64 || getZExtValue() > Limit) ?
+ Limit : getZExtValue();
}
/// @}
// Handle a degenerate case, to avoid shifting by word size
if (loBitsSet == 0)
return APInt(numBits, 0);
- uint32_t shiftAmt = numBits - loBitsSet;
+ if (loBitsSet == APINT_BITS_PER_WORD)
+ return APInt(numBits, -1ULL);
// For small values, return quickly
- if (numBits <= APINT_BITS_PER_WORD)
- return APInt(numBits, ~0ULL >> shiftAmt);
- return (~APInt(numBits, 0)).lshr(shiftAmt);
+ if (numBits < APINT_BITS_PER_WORD)
+ return APInt(numBits, (1ULL << loBitsSet) - 1);
+ return (~APInt(numBits, 0)).lshr(numBits - loBitsSet);
}
/// The hash value is computed as the sum of the words and the bit width.
return &pVal[0];
}
- /// @brief Set a sepcific word in the value to a new value.
- inline void setWordToValue(uint32_t idx, uint64_t Val) {
- assert(idx < getNumWords() && "Invalid word array index");
- if (isSingleWord())
- VAL = Val;
- else
- pVal[idx] = Val;
- }
-
/// @}
/// @name Unary Operators
/// @{
APInt operator-(uint64_t RHS) const {
return (*this) - APInt(BitWidth, RHS);
}
+
+ APInt operator<<(unsigned Bits) const {
+ return shl(Bits);
+ }
/// Arithmetic right-shift this APInt by shiftAmt.
/// @brief Arithmetic right-shift function.
/// @brief Left-shift function.
APInt shl(uint32_t shiftAmt) const;
+ /// @brief Rotate left by rotateAmt.
+ APInt rotl(uint32_t rotateAmt) const;
+
+ /// @brief Rotate right by rotateAmt.
+ APInt rotr(uint32_t rotateAmt) const;
+
/// Perform an unsigned divide operation on this APInt by RHS. Both this and
/// RHS are treated as unsigned quantities for purposes of this division.
/// @returns a new APInt value containing the division result
return this->urem(RHS);
}
+ /// Sometimes it is convenient to divide two APInt values and obtain both
+ /// the quotient and remainder. This function does both operations in the
+ /// same computation making it a little more efficient.
+ /// @brief Dual division/remainder interface.
+ static void udivrem(const APInt &LHS, const APInt &RHS,
+ APInt &Quotient, APInt &Remainder);
+
+ static void 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);
+ }
+ }
+
/// @returns the bit value at bitPosition
/// @brief Array-indexing support.
bool operator[](uint32_t bitPosition) const;
/// @brief Zero extend or truncate to width
APInt &zextOrTrunc(uint32_t width);
- /// This is a help function for convenience. If the given \p width equals to
- /// this APInt's BitWidth, just return this APInt, otherwise, just zero
- /// extend it.
- inline APInt &zextOrCopy(uint32_t width) {
- if (width == BitWidth)
- return *this;
- return zext(width);
- }
-
/// @}
/// @name Bit Manipulation Operators
/// @{
assert(getActiveBits() <= 64 && "Too many bits for int64_t");
return int64_t(pVal[0]);
}
+
+ /// This method determines how many bits are required to hold the APInt
+ /// equivalent of the string given by \p str of length \p slen.
+ /// @brief Get bits required for string value.
+ static uint32_t getBitsNeeded(const char* str, uint32_t slen, uint8_t radix);
+
/// countLeadingZeros - This function is an APInt version of the
/// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number
/// of zeros from the most significant bit to the first one bit.
return BitWidth - 1 - countLeadingZeros();
}
+ /// @returns the log base 2 of this APInt if its an exact power of two, -1
+ /// otherwise
+ inline int32_t exactLogBase2() const {
+ if (!isPowerOf2())
+ return -1;
+ return logBase2();
+ }
+
/// @brief Compute the square root
APInt sqrt() const;
return -(*this);
return *this;
}
+
+ /// @}
+
+ /// @}
+ /// @name Building-block Operations for APInt and APFloat
+ /// @{
+
+ // These building block operations operate on a representation of
+ // arbitrary precision, two's-complement, bignum integer values.
+ // They should be sufficient to implement APInt and APFloat bignum
+ // requirements. Inputs are generally a pointer to the base of an
+ // array of integer parts, representing an unsigned bignum, and a
+ // count of how many parts there are.
+
+ /// Sets the least significant part of a bignum to the input value,
+ /// and zeroes out higher parts. */
+ static void tcSet(integerPart *, integerPart, unsigned int);
+
+ /// Assign one bignum to another.
+ static void tcAssign(integerPart *, const integerPart *, unsigned int);
+
+ /// Returns true if a bignum is zero, false otherwise.
+ static bool tcIsZero(const integerPart *, unsigned int);
+
+ /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
+ static int tcExtractBit(const integerPart *, unsigned int bit);
+
+ /// Set the given bit of a bignum. Zero-based.
+ static void tcSetBit(integerPart *, unsigned int bit);
+
+ /// Returns the bit number of the least or most significant set bit
+ /// of a number. If the input number has no bits set -1U is
+ /// returned.
+ static unsigned int tcLSB(const integerPart *, unsigned int);
+ static unsigned int tcMSB(const integerPart *, unsigned int);
+
+ /// Negate a bignum in-place.
+ static void tcNegate(integerPart *, unsigned int);
+
+ /// DST += RHS + CARRY where CARRY is zero or one. Returns the
+ /// carry flag.
+ static integerPart tcAdd(integerPart *, const integerPart *,
+ integerPart carry, unsigned);
+
+ /// DST -= RHS + CARRY where CARRY is zero or one. Returns the
+ /// carry flag.
+ static integerPart tcSubtract(integerPart *, const integerPart *,
+ integerPart carry, unsigned);
+
+ /// DST += SRC * MULTIPLIER + PART if add is true
+ /// DST = SRC * MULTIPLIER + PART if add is false
+ ///
+ /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
+ /// they must start at the same point, i.e. DST == SRC.
+ ///
+ /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is
+ /// returned. Otherwise DST is filled with the least significant
+ /// DSTPARTS parts of the result, and if all of the omitted higher
+ /// parts were zero return zero, otherwise overflow occurred and
+ /// return one.
+ static int tcMultiplyPart(integerPart *dst, const integerPart *src,
+ integerPart multiplier, integerPart carry,
+ unsigned int srcParts, unsigned int dstParts,
+ bool add);
+
+ /// DST = LHS * RHS, where DST has the same width as the operands
+ /// and is filled with the least significant parts of the result.
+ /// Returns one if overflow occurred, otherwise zero. DST must be
+ /// disjoint from both operands.
+ static int tcMultiply(integerPart *, const integerPart *,
+ const integerPart *, unsigned);
+
+ /// DST = LHS * RHS, where DST has twice the width as the operands.
+ /// No overflow occurs. DST must be disjoint from both operands.
+ static void tcFullMultiply(integerPart *, const integerPart *,
+ const integerPart *, unsigned);
+
+ /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
+ /// Otherwise set LHS to LHS / RHS with the fractional part
+ /// discarded, set REMAINDER to the remainder, return zero. i.e.
+ ///
+ /// OLD_LHS = RHS * LHS + REMAINDER
+ ///
+ /// SCRATCH is a bignum of the same size as the operands and result
+ /// for use by the routine; its contents need not be initialized
+ /// and are destroyed. LHS, REMAINDER and SCRATCH must be
+ /// distinct.
+ static int tcDivide(integerPart *lhs, const integerPart *rhs,
+ integerPart *remainder, integerPart *scratch,
+ unsigned int parts);
+
+ /// Shift a bignum left COUNT bits. Shifted in bits are zero.
+ /// There are no restrictions on COUNT.
+ static void tcShiftLeft(integerPart *, unsigned int parts,
+ unsigned int count);
+
+ /// Shift a bignum right COUNT bits. Shifted in bits are zero.
+ /// There are no restrictions on COUNT.
+ static void tcShiftRight(integerPart *, unsigned int parts,
+ unsigned int count);
+
+ /// The obvious AND, OR and XOR and complement operations.
+ static void tcAnd(integerPart *, const integerPart *, unsigned int);
+ static void tcOr(integerPart *, const integerPart *, unsigned int);
+ static void tcXor(integerPart *, const integerPart *, unsigned int);
+ static void tcComplement(integerPart *, unsigned int);
+
+ /// Comparison (unsigned) of two bignums.
+ static int tcCompare(const integerPart *, const integerPart *,
+ unsigned int);
+
+ /// Increment a bignum in-place. Return the carry flag.
+ static integerPart tcIncrement(integerPart *, unsigned int);
+
+ /// Set the least significant BITS and clear the rest.
+ static void tcSetLeastSignificantBits(integerPart *, unsigned int,
+ unsigned int bits);
+
/// @}
};
/// @returns true if the argument APInt value is a sequence of ones
/// starting at the least significant bit with the remainder zero.
-inline const bool isMask(uint32_t numBits, const APInt& APIVal) {
+inline bool isMask(uint32_t numBits, const APInt& APIVal) {
return APIVal.getBoolValue() && ((APIVal + APInt(numBits,1)) & APIVal) == 0;
}
/// @returns true if the argument APInt value contains a sequence of ones
/// with the remainder zero.
-inline const bool isShiftedMask(uint32_t numBits, const APInt& APIVal) {
+inline bool isShiftedMask(uint32_t numBits, const APInt& APIVal) {
return isMask(numBits, (APIVal - APInt(numBits,1)) | APIVal);
}