+/// Logical right-shift this APInt by shiftAmt.
+/// @brief Logical right-shift function.
+APInt APInt::lshr(const APInt &shiftAmt) const {
+ return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
+}
+
+/// Logical right-shift this APInt by shiftAmt.
+/// @brief Logical right-shift function.
+APInt APInt::lshr(unsigned shiftAmt) const {
+ if (isSingleWord()) {
+ 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)
+ return APInt(BitWidth, 0);
+
+ // If none of the bits are shifted out, the result is *this. This avoids
+ // issues with shifting by the size of the integer type, which produces
+ // undefined results in the code below. This is also an optimization.
+ if (shiftAmt == 0)
+ return *this;
+
+ // Create some space for the result.
+ uint64_t * val = new uint64_t[getNumWords()];
+
+ // If we are shifting less than a word, compute the shift with a simple carry
+ if (shiftAmt < APINT_BITS_PER_WORD) {
+ lshrNear(val, pVal, getNumWords(), shiftAmt);
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+ }
+
+ // Compute some values needed by the remaining shift algorithms
+ unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
+ unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
+
+ // If we are shifting whole words, just move whole words
+ 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;
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+ }
+
+ // Shift the low order words
+ 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));
+ // Shift the break word.
+ val[breakWord] = pVal[breakWord+offset] >> wordShift;
+
+ // Remaining words are 0
+ for (unsigned i = breakWord+1; i < getNumWords(); ++i)
+ val[i] = 0;
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+}
+
+/// Left-shift this APInt by shiftAmt.
+/// @brief Left-shift function.
+APInt APInt::shl(const APInt &shiftAmt) const {
+ // It's undefined behavior in C to shift by BitWidth or greater.
+ return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
+}
+
+APInt APInt::shlSlowCase(unsigned shiftAmt) const {
+ // 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)
+ return APInt(BitWidth, 0);
+
+ // If none of the bits are shifted out, the result is *this. This avoids a
+ // lshr by the words size in the loop below which can produce incorrect
+ // results. It also avoids the expensive computation below for a common case.
+ if (shiftAmt == 0)
+ return *this;
+
+ // Create some space for the result.
+ uint64_t * val = new uint64_t[getNumWords()];
+
+ // If we are shifting less than a word, do it the easy way
+ 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);
+ }
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+ }
+
+ // Compute some values needed by the remaining shift algorithms
+ unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
+ unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
+
+ // If we are shifting whole words, just move whole words
+ 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];
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+ }
+
+ // Copy whole words from this to Result.
+ 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;
+ APInt Result(val, BitWidth);
+ Result.clearUnusedBits();
+ return Result;
+}
+
+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);
+}
+
+// Square Root - this method computes and returns the square root of "this".
+// Three mechanisms are used for computation. For small values (<= 5 bits),
+// a table lookup is done. This gets some performance for common cases. For
+// values using less than 52 bits, the value is converted to double and then
+// the libc sqrt function is called. The result is rounded and then converted
+// back to a uint64_t which is then used to construct the result. Finally,
+// the Babylonian method for computing square roots is used.
+APInt APInt::sqrt() const {
+
+ // Determine the magnitude of the value.
+ unsigned magnitude = getActiveBits();
+
+ // Use a fast table for some small values. This also gets rid of some
+ // rounding errors in libc sqrt for small values.
+ if (magnitude <= 5) {
+ static const uint8_t results[32] = {
+ /* 0 */ 0,
+ /* 1- 2 */ 1, 1,
+ /* 3- 6 */ 2, 2, 2, 2,
+ /* 7-12 */ 3, 3, 3, 3, 3, 3,
+ /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
+ /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ /* 31 */ 6
+ };
+ return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
+ }
+
+ // If the magnitude of the value fits in less than 52 bits (the precision of
+ // an IEEE double precision floating point value), then we can use the
+ // libc sqrt function which will probably use a hardware sqrt computation.
+ // This should be faster than the algorithm below.
+ if (magnitude < 52) {
+ return APInt(BitWidth,
+ uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
+ }
+
+ // 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.
+ // See http://www.wikipedia.org/ and go to the page named
+ // Calculate_an_integer_square_root.
+ unsigned nbits = BitWidth, i = 4;
+ APInt testy(BitWidth, 16);
+ APInt x_old(BitWidth, 1);
+ APInt x_new(BitWidth, 0);
+ APInt two(BitWidth, 2);
+
+ // Select a good starting value using binary logarithms.
+ for (;; i += 2, testy = testy.shl(2))
+ if (i >= nbits || this->ule(testy)) {
+ x_old = x_old.shl(i / 2);
+ break;
+ }
+
+ // Use the Babylonian method to arrive at the integer square root:
+ for (;;) {
+ x_new = (this->udiv(x_old) + x_old).udiv(two);
+ if (x_old.ule(x_new))
+ break;
+ x_old = x_new;
+ }
+
+ // Make sure we return the closest approximation
+ // NOTE: The rounding calculation below is correct. It will produce an
+ // off-by-one discrepancy with results from pari/gp. That discrepancy has been
+ // determined to be a rounding issue with pari/gp as it begins to use a
+ // floating point representation after 192 bits. There are no discrepancies
+ // between this algorithm and pari/gp for bit widths < 192 bits.
+ 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;
+}
+
+/// Computes the multiplicative inverse of this APInt for a given modulo. The
+/// iterative extended Euclidean algorithm is used to solve for this value,
+/// however we simplify it to speed up calculating only the inverse, and take
+/// advantage of div+rem calculations. We also use some tricks to avoid copying
+/// (potentially large) APInts around.
+APInt APInt::multiplicativeInverse(const APInt& modulo) const {
+ assert(ult(modulo) && "This APInt must be smaller than the modulo");
+
+ // Using the properties listed at the following web page (accessed 06/21/08):
+ // http://www.numbertheory.org/php/euclid.html
+ // (especially the properties numbered 3, 4 and 9) it can be proved that
+ // BitWidth bits suffice for all the computations in the algorithm implemented
+ // below. More precisely, this number of bits suffice if the multiplicative
+ // inverse exists, but may not suffice for the general extended Euclidean
+ // algorithm.
+
+ 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) {
+ // An overview of the math without the confusing bit-flipping:
+ // q = r[i-2] / r[i-1]
+ // r[i] = r[i-2] % r[i-1]
+ // t[i] = t[i-2] - t[i-1] * q
+ udivrem(r[i], r[i^1], q, r[i]);
+ t[i] -= t[i^1] * q;
+ }
+
+ // If this APInt and the modulo are not coprime, there is no multiplicative
+ // inverse, so return 0. We check this by looking at the next-to-last
+ // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
+ // algorithm.
+ if (r[i] != 1)
+ return APInt(BitWidth, 0);
+
+ // The next-to-last t is the multiplicative inverse. However, we are
+ // interested in a positive inverse. Calcuate a positive one from a negative
+ // one if necessary. A simple addition of the modulo suffices because
+ // abs(t[i]) is known to be less than *this/2 (see the link above).
+ return t[i].isNegative() ? t[i] + modulo : t[i];
+}
+
+/// Calculate the magic numbers required to implement a signed integer division
+/// by a constant as a sequence of multiplies, adds and shifts. Requires that
+/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
+/// Warren, Jr., chapter 10.
+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); // absolute value of nc
+ p = d.getBitWidth() - 1; // initialize p
+ q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
+ r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
+ q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
+ r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
+ do {
+ p = p + 1;
+ q1 = q1<<1; // update q1 = 2p/abs(nc)
+ r1 = r1<<1; // update r1 = rem(2p/abs(nc))
+ if (r1.uge(anc)) { // must be unsigned comparison
+ q1 = q1 + 1;
+ r1 = r1 - anc;
+ }
+ q2 = q2<<1; // update q2 = 2p/abs(d)
+ r2 = r2<<1; // update r2 = rem(2p/abs(d))
+ if (r2.uge(ad)) { // must be unsigned comparison
+ 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; // resulting magic number
+ mag.s = p - d.getBitWidth(); // resulting shift
+ return mag;
+}
+
+/// Calculate the magic numbers required to implement an unsigned integer
+/// division by a constant as a sequence of multiplies, adds and shifts.
+/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
+/// S. Warren, Jr., chapter 10.
+/// LeadingZeros can be used to simplify the calculation if the upper bits
+/// of the divided value are known zero.
+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; // initialize "add" indicator
+ APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
+ APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
+ APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
+
+ 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)
+ q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
+ r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
+ do {
+ p = p + 1;
+ if (r1.uge(nc - r1)) {
+ q1 = q1 + q1 + 1; // update q1
+ r1 = r1 + r1 - nc; // update r1
+ }
+ else {
+ q1 = q1+q1; // update q1
+ r1 = r1+r1; // update r1
+ }
+ if ((r2 + 1).uge(d - r2)) {
+ if (q2.uge(signedMax)) magu.a = 1;
+ q2 = q2+q2 + 1; // update q2
+ r2 = r2+r2 + 1 - d; // update r2
+ }
+ else {
+ if (q2.uge(signedMin)) magu.a = 1;
+ q2 = q2+q2; // update q2
+ r2 = r2+r2 + 1; // update r2
+ }
+ delta = d - 1 - r2;
+ } while (p < d.getBitWidth()*2 &&
+ (q1.ult(delta) || (q1 == delta && r1 == 0)));
+ magu.m = q2 + 1; // resulting magic number
+ magu.s = p - d.getBitWidth(); // resulting shift
+ return magu;
+}
+
+/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
+/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
+/// variables here have the same names as in the algorithm. Comments explain