1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/ADT/FoldingSet.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/raw_ostream.h"
30 /// A utility function for allocating memory, checking for allocation failures,
31 /// and ensuring the contents are zeroed.
32 inline static uint64_t* getClearedMemory(unsigned numWords) {
33 uint64_t * result = new uint64_t[numWords];
34 assert(result && "APInt memory allocation fails!");
35 memset(result, 0, numWords * sizeof(uint64_t));
39 /// A utility function for allocating memory and checking for allocation
40 /// failure. The content is not zeroed.
41 inline static uint64_t* getMemory(unsigned numWords) {
42 uint64_t * result = new uint64_t[numWords];
43 assert(result && "APInt memory allocation fails!");
47 /// A utility function that converts a character to a digit.
48 inline static unsigned getDigit(char cdigit, uint8_t radix) {
51 if (radix == 16 || radix == 36) {
73 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
74 pVal = getClearedMemory(getNumWords());
76 if (isSigned && int64_t(val) < 0)
77 for (unsigned i = 1; i < getNumWords(); ++i)
81 void APInt::initSlowCase(const APInt& that) {
82 pVal = getMemory(getNumWords());
83 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
86 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
87 assert(BitWidth && "Bitwidth too small");
88 assert(bigVal.data() && "Null pointer detected!");
92 // Get memory, cleared to 0
93 pVal = getClearedMemory(getNumWords());
94 // Calculate the number of words to copy
95 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
96 // Copy the words from bigVal to pVal
97 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
99 // Make sure unused high bits are cleared
103 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
104 : BitWidth(numBits), VAL(0) {
105 initFromArray(bigVal);
108 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
109 : BitWidth(numBits), VAL(0) {
110 initFromArray(makeArrayRef(bigVal, numWords));
113 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
114 : BitWidth(numbits), VAL(0) {
115 assert(BitWidth && "Bitwidth too small");
116 fromString(numbits, Str, radix);
119 APInt& APInt::AssignSlowCase(const APInt& RHS) {
120 // Don't do anything for X = X
124 if (BitWidth == RHS.getBitWidth()) {
125 // assume same bit-width single-word case is already handled
126 assert(!isSingleWord());
127 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
131 if (isSingleWord()) {
132 // assume case where both are single words is already handled
133 assert(!RHS.isSingleWord());
135 pVal = getMemory(RHS.getNumWords());
136 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
137 } else if (getNumWords() == RHS.getNumWords())
138 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
139 else if (RHS.isSingleWord()) {
144 pVal = getMemory(RHS.getNumWords());
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
147 BitWidth = RHS.BitWidth;
148 return clearUnusedBits();
151 APInt& APInt::operator=(uint64_t RHS) {
156 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
158 return clearUnusedBits();
161 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
162 void APInt::Profile(FoldingSetNodeID& ID) const {
163 ID.AddInteger(BitWidth);
165 if (isSingleWord()) {
170 unsigned NumWords = getNumWords();
171 for (unsigned i = 0; i < NumWords; ++i)
172 ID.AddInteger(pVal[i]);
175 /// add_1 - This function adds a single "digit" integer, y, to the multiple
176 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
177 /// 1 is returned if there is a carry out, otherwise 0 is returned.
178 /// @returns the carry of the addition.
179 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
180 for (unsigned i = 0; i < len; ++i) {
183 y = 1; // Carry one to next digit.
185 y = 0; // No need to carry so exit early
192 /// @brief Prefix increment operator. Increments the APInt by one.
193 APInt& APInt::operator++() {
197 add_1(pVal, pVal, getNumWords(), 1);
198 return clearUnusedBits();
201 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
202 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
203 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
204 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
205 /// In other words, if y > x then this function returns 1, otherwise 0.
206 /// @returns the borrow out of the subtraction
207 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
208 for (unsigned i = 0; i < len; ++i) {
212 y = 1; // We have to "borrow 1" from next "digit"
214 y = 0; // No need to borrow
215 break; // Remaining digits are unchanged so exit early
221 /// @brief Prefix decrement operator. Decrements the APInt by one.
222 APInt& APInt::operator--() {
226 sub_1(pVal, getNumWords(), 1);
227 return clearUnusedBits();
230 /// add - This function adds the integer array x to the integer array Y and
231 /// places the result in dest.
232 /// @returns the carry out from the addition
233 /// @brief General addition of 64-bit integer arrays
234 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
237 for (unsigned i = 0; i< len; ++i) {
238 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
239 dest[i] = x[i] + y[i] + carry;
240 carry = dest[i] < limit || (carry && dest[i] == limit);
245 /// Adds the RHS APint to this APInt.
246 /// @returns this, after addition of RHS.
247 /// @brief Addition assignment operator.
248 APInt& APInt::operator+=(const APInt& RHS) {
249 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
253 add(pVal, pVal, RHS.pVal, getNumWords());
255 return clearUnusedBits();
258 /// Subtracts the integer array y from the integer array x
259 /// @returns returns the borrow out.
260 /// @brief Generalized subtraction of 64-bit integer arrays.
261 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
264 for (unsigned i = 0; i < len; ++i) {
265 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
266 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
267 dest[i] = x_tmp - y[i];
272 /// Subtracts the RHS APInt from this APInt
273 /// @returns this, after subtraction
274 /// @brief Subtraction assignment operator.
275 APInt& APInt::operator-=(const APInt& RHS) {
276 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
280 sub(pVal, pVal, RHS.pVal, getNumWords());
281 return clearUnusedBits();
284 /// Multiplies an integer array, x, by a uint64_t integer and places the result
286 /// @returns the carry out of the multiplication.
287 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
288 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
289 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
290 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
293 // For each digit of x.
294 for (unsigned i = 0; i < len; ++i) {
295 // Split x into high and low words
296 uint64_t lx = x[i] & 0xffffffffULL;
297 uint64_t hx = x[i] >> 32;
298 // hasCarry - A flag to indicate if there is a carry to the next digit.
299 // hasCarry == 0, no carry
300 // hasCarry == 1, has carry
301 // hasCarry == 2, no carry and the calculation result == 0.
302 uint8_t hasCarry = 0;
303 dest[i] = carry + lx * ly;
304 // Determine if the add above introduces carry.
305 hasCarry = (dest[i] < carry) ? 1 : 0;
306 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
307 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
308 // (2^32 - 1) + 2^32 = 2^64.
309 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
311 carry += (lx * hy) & 0xffffffffULL;
312 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
313 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
314 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
319 /// Multiplies integer array x by integer array y and stores the result into
320 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
321 /// @brief Generalized multiplicate of integer arrays.
322 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
324 dest[xlen] = mul_1(dest, x, xlen, y[0]);
325 for (unsigned i = 1; i < ylen; ++i) {
326 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
327 uint64_t carry = 0, lx = 0, hx = 0;
328 for (unsigned j = 0; j < xlen; ++j) {
329 lx = x[j] & 0xffffffffULL;
331 // hasCarry - A flag to indicate if has carry.
332 // hasCarry == 0, no carry
333 // hasCarry == 1, has carry
334 // hasCarry == 2, no carry and the calculation result == 0.
335 uint8_t hasCarry = 0;
336 uint64_t resul = carry + lx * ly;
337 hasCarry = (resul < carry) ? 1 : 0;
338 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
339 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
341 carry += (lx * hy) & 0xffffffffULL;
342 resul = (carry << 32) | (resul & 0xffffffffULL);
344 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
345 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
346 ((lx * hy) >> 32) + hx * hy;
348 dest[i+xlen] = carry;
352 APInt& APInt::operator*=(const APInt& RHS) {
353 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
354 if (isSingleWord()) {
360 // Get some bit facts about LHS and check for zero
361 unsigned lhsBits = getActiveBits();
362 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
367 // Get some bit facts about RHS and check for zero
368 unsigned rhsBits = RHS.getActiveBits();
369 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
376 // Allocate space for the result
377 unsigned destWords = rhsWords + lhsWords;
378 uint64_t *dest = getMemory(destWords);
380 // Perform the long multiply
381 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
383 // Copy result back into *this
385 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
386 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
388 // delete dest array and return
393 APInt& APInt::operator&=(const APInt& RHS) {
394 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
395 if (isSingleWord()) {
399 unsigned numWords = getNumWords();
400 for (unsigned i = 0; i < numWords; ++i)
401 pVal[i] &= RHS.pVal[i];
405 APInt& APInt::operator|=(const APInt& RHS) {
406 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
407 if (isSingleWord()) {
411 unsigned numWords = getNumWords();
412 for (unsigned i = 0; i < numWords; ++i)
413 pVal[i] |= RHS.pVal[i];
417 APInt& APInt::operator^=(const APInt& RHS) {
418 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
419 if (isSingleWord()) {
421 this->clearUnusedBits();
424 unsigned numWords = getNumWords();
425 for (unsigned i = 0; i < numWords; ++i)
426 pVal[i] ^= RHS.pVal[i];
427 return clearUnusedBits();
430 APInt APInt::AndSlowCase(const APInt& RHS) const {
431 unsigned numWords = getNumWords();
432 uint64_t* val = getMemory(numWords);
433 for (unsigned i = 0; i < numWords; ++i)
434 val[i] = pVal[i] & RHS.pVal[i];
435 return APInt(val, getBitWidth());
438 APInt APInt::OrSlowCase(const APInt& RHS) const {
439 unsigned numWords = getNumWords();
440 uint64_t *val = getMemory(numWords);
441 for (unsigned i = 0; i < numWords; ++i)
442 val[i] = pVal[i] | RHS.pVal[i];
443 return APInt(val, getBitWidth());
446 APInt APInt::XorSlowCase(const APInt& RHS) const {
447 unsigned numWords = getNumWords();
448 uint64_t *val = getMemory(numWords);
449 for (unsigned i = 0; i < numWords; ++i)
450 val[i] = pVal[i] ^ RHS.pVal[i];
452 // 0^0==1 so clear the high bits in case they got set.
453 return APInt(val, getBitWidth()).clearUnusedBits();
456 bool APInt::operator !() const {
460 for (unsigned i = 0; i < getNumWords(); ++i)
466 APInt APInt::operator*(const APInt& RHS) const {
467 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
469 return APInt(BitWidth, VAL * RHS.VAL);
472 return Result.clearUnusedBits();
475 APInt APInt::operator+(const APInt& RHS) const {
476 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
478 return APInt(BitWidth, VAL + RHS.VAL);
479 APInt Result(BitWidth, 0);
480 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
481 return Result.clearUnusedBits();
484 APInt APInt::operator-(const APInt& RHS) const {
485 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
487 return APInt(BitWidth, VAL - RHS.VAL);
488 APInt Result(BitWidth, 0);
489 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
490 return Result.clearUnusedBits();
493 bool APInt::operator[](unsigned bitPosition) const {
494 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
495 return (maskBit(bitPosition) &
496 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
499 bool APInt::EqualSlowCase(const APInt& RHS) const {
500 // Get some facts about the number of bits used in the two operands.
501 unsigned n1 = getActiveBits();
502 unsigned n2 = RHS.getActiveBits();
504 // If the number of bits isn't the same, they aren't equal
508 // If the number of bits fits in a word, we only need to compare the low word.
509 if (n1 <= APINT_BITS_PER_WORD)
510 return pVal[0] == RHS.pVal[0];
512 // Otherwise, compare everything
513 for (int i = whichWord(n1 - 1); i >= 0; --i)
514 if (pVal[i] != RHS.pVal[i])
519 bool APInt::EqualSlowCase(uint64_t Val) const {
520 unsigned n = getActiveBits();
521 if (n <= APINT_BITS_PER_WORD)
522 return pVal[0] == Val;
527 bool APInt::ult(const APInt& RHS) const {
528 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
530 return VAL < RHS.VAL;
532 // Get active bit length of both operands
533 unsigned n1 = getActiveBits();
534 unsigned n2 = RHS.getActiveBits();
536 // If magnitude of LHS is less than RHS, return true.
540 // If magnitude of RHS is greather than LHS, return false.
544 // If they bot fit in a word, just compare the low order word
545 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
546 return pVal[0] < RHS.pVal[0];
548 // Otherwise, compare all words
549 unsigned topWord = whichWord(std::max(n1,n2)-1);
550 for (int i = topWord; i >= 0; --i) {
551 if (pVal[i] > RHS.pVal[i])
553 if (pVal[i] < RHS.pVal[i])
559 bool APInt::slt(const APInt& RHS) const {
560 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
561 if (isSingleWord()) {
562 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
563 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
564 return lhsSext < rhsSext;
569 bool lhsNeg = isNegative();
570 bool rhsNeg = rhs.isNegative();
572 // Sign bit is set so perform two's complement to make it positive
577 // Sign bit is set so perform two's complement to make it positive
582 // Now we have unsigned values to compare so do the comparison if necessary
583 // based on the negativeness of the values.
595 void APInt::setBit(unsigned bitPosition) {
597 VAL |= maskBit(bitPosition);
599 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
602 /// Set the given bit to 0 whose position is given as "bitPosition".
603 /// @brief Set a given bit to 0.
604 void APInt::clearBit(unsigned bitPosition) {
606 VAL &= ~maskBit(bitPosition);
608 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
611 /// @brief Toggle every bit to its opposite value.
613 /// Toggle a given bit to its opposite value whose position is given
614 /// as "bitPosition".
615 /// @brief Toggles a given bit to its opposite value.
616 void APInt::flipBit(unsigned bitPosition) {
617 assert(bitPosition < BitWidth && "Out of the bit-width range!");
618 if ((*this)[bitPosition]) clearBit(bitPosition);
619 else setBit(bitPosition);
622 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
623 assert(!str.empty() && "Invalid string length");
624 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
626 "Radix should be 2, 8, 10, 16, or 36!");
628 size_t slen = str.size();
630 // Each computation below needs to know if it's negative.
631 StringRef::iterator p = str.begin();
632 unsigned isNegative = *p == '-';
633 if (*p == '-' || *p == '+') {
636 assert(slen && "String is only a sign, needs a value.");
639 // For radixes of power-of-two values, the bits required is accurately and
642 return slen + isNegative;
644 return slen * 3 + isNegative;
646 return slen * 4 + isNegative;
650 // This is grossly inefficient but accurate. We could probably do something
651 // with a computation of roughly slen*64/20 and then adjust by the value of
652 // the first few digits. But, I'm not sure how accurate that could be.
654 // Compute a sufficient number of bits that is always large enough but might
655 // be too large. This avoids the assertion in the constructor. This
656 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
657 // bits in that case.
659 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
660 : (slen == 1 ? 7 : slen * 16/3);
662 // Convert to the actual binary value.
663 APInt tmp(sufficient, StringRef(p, slen), radix);
665 // Compute how many bits are required. If the log is infinite, assume we need
667 unsigned log = tmp.logBase2();
668 if (log == (unsigned)-1) {
669 return isNegative + 1;
671 return isNegative + log + 1;
675 // From http://www.burtleburtle.net, byBob Jenkins.
676 // When targeting x86, both GCC and LLVM seem to recognize this as a
677 // rotate instruction.
678 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
680 // From http://www.burtleburtle.net, by Bob Jenkins.
683 a -= c; a ^= rot(c, 4); c += b; \
684 b -= a; b ^= rot(a, 6); a += c; \
685 c -= b; c ^= rot(b, 8); b += a; \
686 a -= c; a ^= rot(c,16); c += b; \
687 b -= a; b ^= rot(a,19); a += c; \
688 c -= b; c ^= rot(b, 4); b += a; \
691 // From http://www.burtleburtle.net, by Bob Jenkins.
692 #define final(a,b,c) \
694 c ^= b; c -= rot(b,14); \
695 a ^= c; a -= rot(c,11); \
696 b ^= a; b -= rot(a,25); \
697 c ^= b; c -= rot(b,16); \
698 a ^= c; a -= rot(c,4); \
699 b ^= a; b -= rot(a,14); \
700 c ^= b; c -= rot(b,24); \
703 // hashword() was adapted from http://www.burtleburtle.net, by Bob
704 // Jenkins. k is a pointer to an array of uint32_t values; length is
705 // the length of the key, in 32-bit chunks. This version only handles
706 // keys that are a multiple of 32 bits in size.
707 static inline uint32_t hashword(const uint64_t *k64, size_t length)
709 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
712 /* Set up the internal state */
713 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
715 /*------------------------------------------------- handle most of the key */
725 /*------------------------------------------- handle the last 3 uint32_t's */
726 switch (length) { /* all the case statements fall through */
731 case 0: /* case 0: nothing left to add */
734 /*------------------------------------------------------ report the result */
738 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
739 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
740 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
741 // function into about 35 instructions when inlined.
742 static inline uint32_t hashword8(const uint64_t k64)
745 a = b = c = 0xdeadbeef + 4;
747 a += k64 & 0xffffffff;
755 uint64_t APInt::getHashValue() const {
758 hash = hashword8(VAL);
760 hash = hashword(pVal, getNumWords()*2);
764 /// HiBits - This function returns the high "numBits" bits of this APInt.
765 APInt APInt::getHiBits(unsigned numBits) const {
766 return APIntOps::lshr(*this, BitWidth - numBits);
769 /// LoBits - This function returns the low "numBits" bits of this APInt.
770 APInt APInt::getLoBits(unsigned numBits) const {
771 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
775 unsigned APInt::countLeadingZerosSlowCase() const {
776 // Treat the most significand word differently because it might have
777 // meaningless bits set beyond the precision.
778 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
780 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
782 MSWMask = ~integerPart(0);
783 BitsInMSW = APINT_BITS_PER_WORD;
786 unsigned i = getNumWords();
787 integerPart MSW = pVal[i-1] & MSWMask;
789 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
791 unsigned Count = BitsInMSW;
792 for (--i; i > 0u; --i) {
794 Count += APINT_BITS_PER_WORD;
796 Count += CountLeadingZeros_64(pVal[i-1]);
803 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
807 while (V && (V & (1ULL << 63))) {
814 unsigned APInt::countLeadingOnes() const {
816 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
818 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
821 highWordBits = APINT_BITS_PER_WORD;
824 shift = APINT_BITS_PER_WORD - highWordBits;
826 int i = getNumWords() - 1;
827 unsigned Count = countLeadingOnes_64(pVal[i], shift);
828 if (Count == highWordBits) {
829 for (i--; i >= 0; --i) {
830 if (pVal[i] == -1ULL)
831 Count += APINT_BITS_PER_WORD;
833 Count += countLeadingOnes_64(pVal[i], 0);
841 unsigned APInt::countTrailingZeros() const {
843 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
846 for (; i < getNumWords() && pVal[i] == 0; ++i)
847 Count += APINT_BITS_PER_WORD;
848 if (i < getNumWords())
849 Count += CountTrailingZeros_64(pVal[i]);
850 return std::min(Count, BitWidth);
853 unsigned APInt::countTrailingOnesSlowCase() const {
856 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
857 Count += APINT_BITS_PER_WORD;
858 if (i < getNumWords())
859 Count += CountTrailingOnes_64(pVal[i]);
860 return std::min(Count, BitWidth);
863 unsigned APInt::countPopulationSlowCase() const {
865 for (unsigned i = 0; i < getNumWords(); ++i)
866 Count += CountPopulation_64(pVal[i]);
870 APInt APInt::byteSwap() const {
871 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
873 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
874 else if (BitWidth == 32)
875 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
876 else if (BitWidth == 48) {
877 unsigned Tmp1 = unsigned(VAL >> 16);
878 Tmp1 = ByteSwap_32(Tmp1);
879 uint16_t Tmp2 = uint16_t(VAL);
880 Tmp2 = ByteSwap_16(Tmp2);
881 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
882 } else if (BitWidth == 64)
883 return APInt(BitWidth, ByteSwap_64(VAL));
885 APInt Result(BitWidth, 0);
886 char *pByte = (char*)Result.pVal;
887 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
889 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
890 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
896 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
898 APInt A = API1, B = API2;
901 B = APIntOps::urem(A, B);
907 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
914 // Get the sign bit from the highest order bit
915 bool isNeg = T.I >> 63;
917 // Get the 11-bit exponent and adjust for the 1023 bit bias
918 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
920 // If the exponent is negative, the value is < 0 so just return 0.
922 return APInt(width, 0u);
924 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
925 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
927 // If the exponent doesn't shift all bits out of the mantissa
929 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
930 APInt(width, mantissa >> (52 - exp));
932 // If the client didn't provide enough bits for us to shift the mantissa into
933 // then the result is undefined, just return 0
934 if (width <= exp - 52)
935 return APInt(width, 0);
937 // Otherwise, we have to shift the mantissa bits up to the right location
938 APInt Tmp(width, mantissa);
939 Tmp = Tmp.shl((unsigned)exp - 52);
940 return isNeg ? -Tmp : Tmp;
943 /// RoundToDouble - This function converts this APInt to a double.
944 /// The layout for double is as following (IEEE Standard 754):
945 /// --------------------------------------
946 /// | Sign Exponent Fraction Bias |
947 /// |-------------------------------------- |
948 /// | 1[63] 11[62-52] 52[51-00] 1023 |
949 /// --------------------------------------
950 double APInt::roundToDouble(bool isSigned) const {
952 // Handle the simple case where the value is contained in one uint64_t.
953 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
954 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
956 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
959 return double(getWord(0));
962 // Determine if the value is negative.
963 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
965 // Construct the absolute value if we're negative.
966 APInt Tmp(isNeg ? -(*this) : (*this));
968 // Figure out how many bits we're using.
969 unsigned n = Tmp.getActiveBits();
971 // The exponent (without bias normalization) is just the number of bits
972 // we are using. Note that the sign bit is gone since we constructed the
976 // Return infinity for exponent overflow
978 if (!isSigned || !isNeg)
979 return std::numeric_limits<double>::infinity();
981 return -std::numeric_limits<double>::infinity();
983 exp += 1023; // Increment for 1023 bias
985 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
986 // extract the high 52 bits from the correct words in pVal.
988 unsigned hiWord = whichWord(n-1);
990 mantissa = Tmp.pVal[0];
992 mantissa >>= n - 52; // shift down, we want the top 52 bits.
994 assert(hiWord > 0 && "huh?");
995 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
996 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
997 mantissa = hibits | lobits;
1000 // The leading bit of mantissa is implicit, so get rid of it.
1001 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
1006 T.I = sign | (exp << 52) | mantissa;
1010 // Truncate to new width.
1011 APInt APInt::trunc(unsigned width) const {
1012 assert(width < BitWidth && "Invalid APInt Truncate request");
1013 assert(width && "Can't truncate to 0 bits");
1015 if (width <= APINT_BITS_PER_WORD)
1016 return APInt(width, getRawData()[0]);
1018 APInt Result(getMemory(getNumWords(width)), width);
1022 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
1023 Result.pVal[i] = pVal[i];
1025 // Truncate and copy any partial word.
1026 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
1028 Result.pVal[i] = pVal[i] << bits >> bits;
1033 // Sign extend to a new width.
1034 APInt APInt::sext(unsigned width) const {
1035 assert(width > BitWidth && "Invalid APInt SignExtend request");
1037 if (width <= APINT_BITS_PER_WORD) {
1038 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
1039 val = (int64_t)val >> (width - BitWidth);
1040 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
1043 APInt Result(getMemory(getNumWords(width)), width);
1048 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
1049 word = getRawData()[i];
1050 Result.pVal[i] = word;
1053 // Read and sign-extend any partial word.
1054 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
1056 word = (int64_t)getRawData()[i] << bits >> bits;
1058 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1060 // Write remaining full words.
1061 for (; i != width / APINT_BITS_PER_WORD; i++) {
1062 Result.pVal[i] = word;
1063 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1066 // Write any partial word.
1067 bits = (0 - width) % APINT_BITS_PER_WORD;
1069 Result.pVal[i] = word << bits >> bits;
1074 // Zero extend to a new width.
1075 APInt APInt::zext(unsigned width) const {
1076 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1078 if (width <= APINT_BITS_PER_WORD)
1079 return APInt(width, VAL);
1081 APInt Result(getMemory(getNumWords(width)), width);
1085 for (i = 0; i != getNumWords(); i++)
1086 Result.pVal[i] = getRawData()[i];
1088 // Zero remaining words.
1089 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1094 APInt APInt::zextOrTrunc(unsigned width) const {
1095 if (BitWidth < width)
1097 if (BitWidth > width)
1098 return trunc(width);
1102 APInt APInt::sextOrTrunc(unsigned width) const {
1103 if (BitWidth < width)
1105 if (BitWidth > width)
1106 return trunc(width);
1110 /// Arithmetic right-shift this APInt by shiftAmt.
1111 /// @brief Arithmetic right-shift function.
1112 APInt APInt::ashr(const APInt &shiftAmt) const {
1113 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1116 /// Arithmetic right-shift this APInt by shiftAmt.
1117 /// @brief Arithmetic right-shift function.
1118 APInt APInt::ashr(unsigned shiftAmt) const {
1119 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1120 // Handle a degenerate case
1124 // Handle single word shifts with built-in ashr
1125 if (isSingleWord()) {
1126 if (shiftAmt == BitWidth)
1127 return APInt(BitWidth, 0); // undefined
1129 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1130 return APInt(BitWidth,
1131 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1135 // If all the bits were shifted out, the result is, technically, undefined.
1136 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1137 // issues in the algorithm below.
1138 if (shiftAmt == BitWidth) {
1140 return APInt(BitWidth, -1ULL, true);
1142 return APInt(BitWidth, 0);
1145 // Create some space for the result.
1146 uint64_t * val = new uint64_t[getNumWords()];
1148 // Compute some values needed by the following shift algorithms
1149 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1150 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1151 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1152 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1153 if (bitsInWord == 0)
1154 bitsInWord = APINT_BITS_PER_WORD;
1156 // If we are shifting whole words, just move whole words
1157 if (wordShift == 0) {
1158 // Move the words containing significant bits
1159 for (unsigned i = 0; i <= breakWord; ++i)
1160 val[i] = pVal[i+offset]; // move whole word
1162 // Adjust the top significant word for sign bit fill, if negative
1164 if (bitsInWord < APINT_BITS_PER_WORD)
1165 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1167 // Shift the low order words
1168 for (unsigned i = 0; i < breakWord; ++i) {
1169 // This combines the shifted corresponding word with the low bits from
1170 // the next word (shifted into this word's high bits).
1171 val[i] = (pVal[i+offset] >> wordShift) |
1172 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1175 // Shift the break word. In this case there are no bits from the next word
1176 // to include in this word.
1177 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1179 // Deal with sign extenstion in the break word, and possibly the word before
1182 if (wordShift > bitsInWord) {
1185 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1186 val[breakWord] |= ~0ULL;
1188 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1192 // Remaining words are 0 or -1, just assign them.
1193 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1194 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1196 return APInt(val, BitWidth).clearUnusedBits();
1199 /// Logical right-shift this APInt by shiftAmt.
1200 /// @brief Logical right-shift function.
1201 APInt APInt::lshr(const APInt &shiftAmt) const {
1202 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1205 /// Logical right-shift this APInt by shiftAmt.
1206 /// @brief Logical right-shift function.
1207 APInt APInt::lshr(unsigned shiftAmt) const {
1208 if (isSingleWord()) {
1209 if (shiftAmt == BitWidth)
1210 return APInt(BitWidth, 0);
1212 return APInt(BitWidth, this->VAL >> shiftAmt);
1215 // If all the bits were shifted out, the result is 0. This avoids issues
1216 // with shifting by the size of the integer type, which produces undefined
1217 // results. We define these "undefined results" to always be 0.
1218 if (shiftAmt == BitWidth)
1219 return APInt(BitWidth, 0);
1221 // If none of the bits are shifted out, the result is *this. This avoids
1222 // issues with shifting by the size of the integer type, which produces
1223 // undefined results in the code below. This is also an optimization.
1227 // Create some space for the result.
1228 uint64_t * val = new uint64_t[getNumWords()];
1230 // If we are shifting less than a word, compute the shift with a simple carry
1231 if (shiftAmt < APINT_BITS_PER_WORD) {
1233 for (int i = getNumWords()-1; i >= 0; --i) {
1234 val[i] = (pVal[i] >> shiftAmt) | carry;
1235 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1237 return APInt(val, BitWidth).clearUnusedBits();
1240 // Compute some values needed by the remaining shift algorithms
1241 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1242 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1244 // If we are shifting whole words, just move whole words
1245 if (wordShift == 0) {
1246 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1247 val[i] = pVal[i+offset];
1248 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1250 return APInt(val,BitWidth).clearUnusedBits();
1253 // Shift the low order words
1254 unsigned breakWord = getNumWords() - offset -1;
1255 for (unsigned i = 0; i < breakWord; ++i)
1256 val[i] = (pVal[i+offset] >> wordShift) |
1257 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1258 // Shift the break word.
1259 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1261 // Remaining words are 0
1262 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1264 return APInt(val, BitWidth).clearUnusedBits();
1267 /// Left-shift this APInt by shiftAmt.
1268 /// @brief Left-shift function.
1269 APInt APInt::shl(const APInt &shiftAmt) const {
1270 // It's undefined behavior in C to shift by BitWidth or greater.
1271 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1274 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1275 // If all the bits were shifted out, the result is 0. This avoids issues
1276 // with shifting by the size of the integer type, which produces undefined
1277 // results. We define these "undefined results" to always be 0.
1278 if (shiftAmt == BitWidth)
1279 return APInt(BitWidth, 0);
1281 // If none of the bits are shifted out, the result is *this. This avoids a
1282 // lshr by the words size in the loop below which can produce incorrect
1283 // results. It also avoids the expensive computation below for a common case.
1287 // Create some space for the result.
1288 uint64_t * val = new uint64_t[getNumWords()];
1290 // If we are shifting less than a word, do it the easy way
1291 if (shiftAmt < APINT_BITS_PER_WORD) {
1293 for (unsigned i = 0; i < getNumWords(); i++) {
1294 val[i] = pVal[i] << shiftAmt | carry;
1295 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1297 return APInt(val, BitWidth).clearUnusedBits();
1300 // Compute some values needed by the remaining shift algorithms
1301 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1302 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1304 // If we are shifting whole words, just move whole words
1305 if (wordShift == 0) {
1306 for (unsigned i = 0; i < offset; i++)
1308 for (unsigned i = offset; i < getNumWords(); i++)
1309 val[i] = pVal[i-offset];
1310 return APInt(val,BitWidth).clearUnusedBits();
1313 // Copy whole words from this to Result.
1314 unsigned i = getNumWords() - 1;
1315 for (; i > offset; --i)
1316 val[i] = pVal[i-offset] << wordShift |
1317 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1318 val[offset] = pVal[0] << wordShift;
1319 for (i = 0; i < offset; ++i)
1321 return APInt(val, BitWidth).clearUnusedBits();
1324 APInt APInt::rotl(const APInt &rotateAmt) const {
1325 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1328 APInt APInt::rotl(unsigned rotateAmt) const {
1331 // Don't get too fancy, just use existing shift/or facilities
1335 lo.lshr(BitWidth - rotateAmt);
1339 APInt APInt::rotr(const APInt &rotateAmt) const {
1340 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1343 APInt APInt::rotr(unsigned rotateAmt) const {
1346 // Don't get too fancy, just use existing shift/or facilities
1350 hi.shl(BitWidth - rotateAmt);
1354 // Square Root - this method computes and returns the square root of "this".
1355 // Three mechanisms are used for computation. For small values (<= 5 bits),
1356 // a table lookup is done. This gets some performance for common cases. For
1357 // values using less than 52 bits, the value is converted to double and then
1358 // the libc sqrt function is called. The result is rounded and then converted
1359 // back to a uint64_t which is then used to construct the result. Finally,
1360 // the Babylonian method for computing square roots is used.
1361 APInt APInt::sqrt() const {
1363 // Determine the magnitude of the value.
1364 unsigned magnitude = getActiveBits();
1366 // Use a fast table for some small values. This also gets rid of some
1367 // rounding errors in libc sqrt for small values.
1368 if (magnitude <= 5) {
1369 static const uint8_t results[32] = {
1372 /* 3- 6 */ 2, 2, 2, 2,
1373 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1374 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1375 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1378 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1381 // If the magnitude of the value fits in less than 52 bits (the precision of
1382 // an IEEE double precision floating point value), then we can use the
1383 // libc sqrt function which will probably use a hardware sqrt computation.
1384 // This should be faster than the algorithm below.
1385 if (magnitude < 52) {
1387 return APInt(BitWidth,
1388 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1390 return APInt(BitWidth,
1391 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1395 // Okay, all the short cuts are exhausted. We must compute it. The following
1396 // is a classical Babylonian method for computing the square root. This code
1397 // was adapted to APINt from a wikipedia article on such computations.
1398 // See http://www.wikipedia.org/ and go to the page named
1399 // Calculate_an_integer_square_root.
1400 unsigned nbits = BitWidth, i = 4;
1401 APInt testy(BitWidth, 16);
1402 APInt x_old(BitWidth, 1);
1403 APInt x_new(BitWidth, 0);
1404 APInt two(BitWidth, 2);
1406 // Select a good starting value using binary logarithms.
1407 for (;; i += 2, testy = testy.shl(2))
1408 if (i >= nbits || this->ule(testy)) {
1409 x_old = x_old.shl(i / 2);
1413 // Use the Babylonian method to arrive at the integer square root:
1415 x_new = (this->udiv(x_old) + x_old).udiv(two);
1416 if (x_old.ule(x_new))
1421 // Make sure we return the closest approximation
1422 // NOTE: The rounding calculation below is correct. It will produce an
1423 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1424 // determined to be a rounding issue with pari/gp as it begins to use a
1425 // floating point representation after 192 bits. There are no discrepancies
1426 // between this algorithm and pari/gp for bit widths < 192 bits.
1427 APInt square(x_old * x_old);
1428 APInt nextSquare((x_old + 1) * (x_old +1));
1429 if (this->ult(square))
1431 else if (this->ule(nextSquare)) {
1432 APInt midpoint((nextSquare - square).udiv(two));
1433 APInt offset(*this - square);
1434 if (offset.ult(midpoint))
1439 llvm_unreachable("Error in APInt::sqrt computation");
1443 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1444 /// iterative extended Euclidean algorithm is used to solve for this value,
1445 /// however we simplify it to speed up calculating only the inverse, and take
1446 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1447 /// (potentially large) APInts around.
1448 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1449 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1451 // Using the properties listed at the following web page (accessed 06/21/08):
1452 // http://www.numbertheory.org/php/euclid.html
1453 // (especially the properties numbered 3, 4 and 9) it can be proved that
1454 // BitWidth bits suffice for all the computations in the algorithm implemented
1455 // below. More precisely, this number of bits suffice if the multiplicative
1456 // inverse exists, but may not suffice for the general extended Euclidean
1459 APInt r[2] = { modulo, *this };
1460 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1461 APInt q(BitWidth, 0);
1464 for (i = 0; r[i^1] != 0; i ^= 1) {
1465 // An overview of the math without the confusing bit-flipping:
1466 // q = r[i-2] / r[i-1]
1467 // r[i] = r[i-2] % r[i-1]
1468 // t[i] = t[i-2] - t[i-1] * q
1469 udivrem(r[i], r[i^1], q, r[i]);
1473 // If this APInt and the modulo are not coprime, there is no multiplicative
1474 // inverse, so return 0. We check this by looking at the next-to-last
1475 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1478 return APInt(BitWidth, 0);
1480 // The next-to-last t is the multiplicative inverse. However, we are
1481 // interested in a positive inverse. Calcuate a positive one from a negative
1482 // one if necessary. A simple addition of the modulo suffices because
1483 // abs(t[i]) is known to be less than *this/2 (see the link above).
1484 return t[i].isNegative() ? t[i] + modulo : t[i];
1487 /// Calculate the magic numbers required to implement a signed integer division
1488 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1489 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1490 /// Warren, Jr., chapter 10.
1491 APInt::ms APInt::magic() const {
1492 const APInt& d = *this;
1494 APInt ad, anc, delta, q1, r1, q2, r2, t;
1495 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1499 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1500 anc = t - 1 - t.urem(ad); // absolute value of nc
1501 p = d.getBitWidth() - 1; // initialize p
1502 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1503 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1504 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1505 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1508 q1 = q1<<1; // update q1 = 2p/abs(nc)
1509 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1510 if (r1.uge(anc)) { // must be unsigned comparison
1514 q2 = q2<<1; // update q2 = 2p/abs(d)
1515 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1516 if (r2.uge(ad)) { // must be unsigned comparison
1521 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1524 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1525 mag.s = p - d.getBitWidth(); // resulting shift
1529 /// Calculate the magic numbers required to implement an unsigned integer
1530 /// division by a constant as a sequence of multiplies, adds and shifts.
1531 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1532 /// S. Warren, Jr., chapter 10.
1533 /// LeadingZeros can be used to simplify the calculation if the upper bits
1534 /// of the divided value are known zero.
1535 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1536 const APInt& d = *this;
1538 APInt nc, delta, q1, r1, q2, r2;
1540 magu.a = 0; // initialize "add" indicator
1541 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1542 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1543 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1545 nc = allOnes - (-d).urem(d);
1546 p = d.getBitWidth() - 1; // initialize p
1547 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1548 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1549 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1550 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1553 if (r1.uge(nc - r1)) {
1554 q1 = q1 + q1 + 1; // update q1
1555 r1 = r1 + r1 - nc; // update r1
1558 q1 = q1+q1; // update q1
1559 r1 = r1+r1; // update r1
1561 if ((r2 + 1).uge(d - r2)) {
1562 if (q2.uge(signedMax)) magu.a = 1;
1563 q2 = q2+q2 + 1; // update q2
1564 r2 = r2+r2 + 1 - d; // update r2
1567 if (q2.uge(signedMin)) magu.a = 1;
1568 q2 = q2+q2; // update q2
1569 r2 = r2+r2 + 1; // update r2
1572 } while (p < d.getBitWidth()*2 &&
1573 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1574 magu.m = q2 + 1; // resulting magic number
1575 magu.s = p - d.getBitWidth(); // resulting shift
1579 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1580 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1581 /// variables here have the same names as in the algorithm. Comments explain
1582 /// the algorithm and any deviation from it.
1583 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1584 unsigned m, unsigned n) {
1585 assert(u && "Must provide dividend");
1586 assert(v && "Must provide divisor");
1587 assert(q && "Must provide quotient");
1588 assert(u != v && u != q && v != q && "Must us different memory");
1589 assert(n>1 && "n must be > 1");
1591 // Knuth uses the value b as the base of the number system. In our case b
1592 // is 2^31 so we just set it to -1u.
1593 uint64_t b = uint64_t(1) << 32;
1596 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1597 DEBUG(dbgs() << "KnuthDiv: original:");
1598 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1599 DEBUG(dbgs() << " by");
1600 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1601 DEBUG(dbgs() << '\n');
1603 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1604 // u and v by d. Note that we have taken Knuth's advice here to use a power
1605 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1606 // 2 allows us to shift instead of multiply and it is easy to determine the
1607 // shift amount from the leading zeros. We are basically normalizing the u
1608 // and v so that its high bits are shifted to the top of v's range without
1609 // overflow. Note that this can require an extra word in u so that u must
1610 // be of length m+n+1.
1611 unsigned shift = CountLeadingZeros_32(v[n-1]);
1612 unsigned v_carry = 0;
1613 unsigned u_carry = 0;
1615 for (unsigned i = 0; i < m+n; ++i) {
1616 unsigned u_tmp = u[i] >> (32 - shift);
1617 u[i] = (u[i] << shift) | u_carry;
1620 for (unsigned i = 0; i < n; ++i) {
1621 unsigned v_tmp = v[i] >> (32 - shift);
1622 v[i] = (v[i] << shift) | v_carry;
1628 DEBUG(dbgs() << "KnuthDiv: normal:");
1629 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1630 DEBUG(dbgs() << " by");
1631 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1632 DEBUG(dbgs() << '\n');
1635 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1638 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1639 // D3. [Calculate q'.].
1640 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1641 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1642 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1643 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1644 // on v[n-2] determines at high speed most of the cases in which the trial
1645 // value qp is one too large, and it eliminates all cases where qp is two
1647 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1648 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1649 uint64_t qp = dividend / v[n-1];
1650 uint64_t rp = dividend % v[n-1];
1651 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1654 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1657 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1659 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1660 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1661 // consists of a simple multiplication by a one-place number, combined with
1664 for (unsigned i = 0; i < n; ++i) {
1665 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1666 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1667 bool borrow = subtrahend > u_tmp;
1668 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1669 << ", subtrahend == " << subtrahend
1670 << ", borrow = " << borrow << '\n');
1672 uint64_t result = u_tmp - subtrahend;
1674 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1675 u[k++] = (unsigned)(result >> 32); // subtract high word
1676 while (borrow && k <= m+n) { // deal with borrow to the left
1682 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1685 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1686 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1687 DEBUG(dbgs() << '\n');
1688 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1689 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1690 // true value plus b**(n+1), namely as the b's complement of
1691 // the true value, and a "borrow" to the left should be remembered.
1694 bool carry = true; // true because b's complement is "complement + 1"
1695 for (unsigned i = 0; i <= m+n; ++i) {
1696 u[i] = ~u[i] + carry; // b's complement
1697 carry = carry && u[i] == 0;
1700 DEBUG(dbgs() << "KnuthDiv: after complement:");
1701 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1702 DEBUG(dbgs() << '\n');
1704 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1705 // negative, go to step D6; otherwise go on to step D7.
1706 q[j] = (unsigned)qp;
1708 // D6. [Add back]. The probability that this step is necessary is very
1709 // small, on the order of only 2/b. Make sure that test data accounts for
1710 // this possibility. Decrease q[j] by 1
1712 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1713 // A carry will occur to the left of u[j+n], and it should be ignored
1714 // since it cancels with the borrow that occurred in D4.
1716 for (unsigned i = 0; i < n; i++) {
1717 unsigned limit = std::min(u[j+i],v[i]);
1718 u[j+i] += v[i] + carry;
1719 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1723 DEBUG(dbgs() << "KnuthDiv: after correction:");
1724 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1725 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1727 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1730 DEBUG(dbgs() << "KnuthDiv: quotient:");
1731 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1732 DEBUG(dbgs() << '\n');
1734 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1735 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1736 // compute the remainder (urem uses this).
1738 // The value d is expressed by the "shift" value above since we avoided
1739 // multiplication by d by using a shift left. So, all we have to do is
1740 // shift right here. In order to mak
1743 DEBUG(dbgs() << "KnuthDiv: remainder:");
1744 for (int i = n-1; i >= 0; i--) {
1745 r[i] = (u[i] >> shift) | carry;
1746 carry = u[i] << (32 - shift);
1747 DEBUG(dbgs() << " " << r[i]);
1750 for (int i = n-1; i >= 0; i--) {
1752 DEBUG(dbgs() << " " << r[i]);
1755 DEBUG(dbgs() << '\n');
1758 DEBUG(dbgs() << '\n');
1762 void APInt::divide(const APInt LHS, unsigned lhsWords,
1763 const APInt &RHS, unsigned rhsWords,
1764 APInt *Quotient, APInt *Remainder)
1766 assert(lhsWords >= rhsWords && "Fractional result");
1768 // First, compose the values into an array of 32-bit words instead of
1769 // 64-bit words. This is a necessity of both the "short division" algorithm
1770 // and the Knuth "classical algorithm" which requires there to be native
1771 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1772 // can't use 64-bit operands here because we don't have native results of
1773 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1774 // work on large-endian machines.
1775 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1776 unsigned n = rhsWords * 2;
1777 unsigned m = (lhsWords * 2) - n;
1779 // Allocate space for the temporary values we need either on the stack, if
1780 // it will fit, or on the heap if it won't.
1781 unsigned SPACE[128];
1786 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1789 Q = &SPACE[(m+n+1) + n];
1791 R = &SPACE[(m+n+1) + n + (m+n)];
1793 U = new unsigned[m + n + 1];
1794 V = new unsigned[n];
1795 Q = new unsigned[m+n];
1797 R = new unsigned[n];
1800 // Initialize the dividend
1801 memset(U, 0, (m+n+1)*sizeof(unsigned));
1802 for (unsigned i = 0; i < lhsWords; ++i) {
1803 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1804 U[i * 2] = (unsigned)(tmp & mask);
1805 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1807 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1809 // Initialize the divisor
1810 memset(V, 0, (n)*sizeof(unsigned));
1811 for (unsigned i = 0; i < rhsWords; ++i) {
1812 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1813 V[i * 2] = (unsigned)(tmp & mask);
1814 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1817 // initialize the quotient and remainder
1818 memset(Q, 0, (m+n) * sizeof(unsigned));
1820 memset(R, 0, n * sizeof(unsigned));
1822 // Now, adjust m and n for the Knuth division. n is the number of words in
1823 // the divisor. m is the number of words by which the dividend exceeds the
1824 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1825 // contain any zero words or the Knuth algorithm fails.
1826 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1830 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1833 // If we're left with only a single word for the divisor, Knuth doesn't work
1834 // so we implement the short division algorithm here. This is much simpler
1835 // and faster because we are certain that we can divide a 64-bit quantity
1836 // by a 32-bit quantity at hardware speed and short division is simply a
1837 // series of such operations. This is just like doing short division but we
1838 // are using base 2^32 instead of base 10.
1839 assert(n != 0 && "Divide by zero?");
1841 unsigned divisor = V[0];
1842 unsigned remainder = 0;
1843 for (int i = m+n-1; i >= 0; i--) {
1844 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1845 if (partial_dividend == 0) {
1848 } else if (partial_dividend < divisor) {
1850 remainder = (unsigned)partial_dividend;
1851 } else if (partial_dividend == divisor) {
1855 Q[i] = (unsigned)(partial_dividend / divisor);
1856 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1862 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1864 KnuthDiv(U, V, Q, R, m, n);
1867 // If the caller wants the quotient
1869 // Set up the Quotient value's memory.
1870 if (Quotient->BitWidth != LHS.BitWidth) {
1871 if (Quotient->isSingleWord())
1874 delete [] Quotient->pVal;
1875 Quotient->BitWidth = LHS.BitWidth;
1876 if (!Quotient->isSingleWord())
1877 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1879 Quotient->clearAllBits();
1881 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1883 if (lhsWords == 1) {
1885 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1886 if (Quotient->isSingleWord())
1887 Quotient->VAL = tmp;
1889 Quotient->pVal[0] = tmp;
1891 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1892 for (unsigned i = 0; i < lhsWords; ++i)
1894 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1898 // If the caller wants the remainder
1900 // Set up the Remainder value's memory.
1901 if (Remainder->BitWidth != RHS.BitWidth) {
1902 if (Remainder->isSingleWord())
1905 delete [] Remainder->pVal;
1906 Remainder->BitWidth = RHS.BitWidth;
1907 if (!Remainder->isSingleWord())
1908 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1910 Remainder->clearAllBits();
1912 // The remainder is in R. Reconstitute the remainder into Remainder's low
1914 if (rhsWords == 1) {
1916 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1917 if (Remainder->isSingleWord())
1918 Remainder->VAL = tmp;
1920 Remainder->pVal[0] = tmp;
1922 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1923 for (unsigned i = 0; i < rhsWords; ++i)
1924 Remainder->pVal[i] =
1925 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1929 // Clean up the memory we allocated.
1930 if (U != &SPACE[0]) {
1938 APInt APInt::udiv(const APInt& RHS) const {
1939 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1941 // First, deal with the easy case
1942 if (isSingleWord()) {
1943 assert(RHS.VAL != 0 && "Divide by zero?");
1944 return APInt(BitWidth, VAL / RHS.VAL);
1947 // Get some facts about the LHS and RHS number of bits and words
1948 unsigned rhsBits = RHS.getActiveBits();
1949 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1950 assert(rhsWords && "Divided by zero???");
1951 unsigned lhsBits = this->getActiveBits();
1952 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1954 // Deal with some degenerate cases
1957 return APInt(BitWidth, 0);
1958 else if (lhsWords < rhsWords || this->ult(RHS)) {
1959 // X / Y ===> 0, iff X < Y
1960 return APInt(BitWidth, 0);
1961 } else if (*this == RHS) {
1963 return APInt(BitWidth, 1);
1964 } else if (lhsWords == 1 && rhsWords == 1) {
1965 // All high words are zero, just use native divide
1966 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1969 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1970 APInt Quotient(1,0); // to hold result.
1971 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1975 APInt APInt::urem(const APInt& RHS) const {
1976 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1977 if (isSingleWord()) {
1978 assert(RHS.VAL != 0 && "Remainder by zero?");
1979 return APInt(BitWidth, VAL % RHS.VAL);
1982 // Get some facts about the LHS
1983 unsigned lhsBits = getActiveBits();
1984 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1986 // Get some facts about the RHS
1987 unsigned rhsBits = RHS.getActiveBits();
1988 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1989 assert(rhsWords && "Performing remainder operation by zero ???");
1991 // Check the degenerate cases
1992 if (lhsWords == 0) {
1994 return APInt(BitWidth, 0);
1995 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1996 // X % Y ===> X, iff X < Y
1998 } else if (*this == RHS) {
2000 return APInt(BitWidth, 0);
2001 } else if (lhsWords == 1) {
2002 // All high words are zero, just use native remainder
2003 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
2006 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2007 APInt Remainder(1,0);
2008 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2012 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2013 APInt &Quotient, APInt &Remainder) {
2014 // Get some size facts about the dividend and divisor
2015 unsigned lhsBits = LHS.getActiveBits();
2016 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2017 unsigned rhsBits = RHS.getActiveBits();
2018 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2020 // Check the degenerate cases
2021 if (lhsWords == 0) {
2022 Quotient = 0; // 0 / Y ===> 0
2023 Remainder = 0; // 0 % Y ===> 0
2027 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2028 Remainder = LHS; // X % Y ===> X, iff X < Y
2029 Quotient = 0; // X / Y ===> 0, iff X < Y
2034 Quotient = 1; // X / X ===> 1
2035 Remainder = 0; // X % X ===> 0;
2039 if (lhsWords == 1 && rhsWords == 1) {
2040 // There is only one word to consider so use the native versions.
2041 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2042 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2043 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2044 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2048 // Okay, lets do it the long way
2049 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2052 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2053 APInt Res = *this+RHS;
2054 Overflow = isNonNegative() == RHS.isNonNegative() &&
2055 Res.isNonNegative() != isNonNegative();
2059 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2060 APInt Res = *this+RHS;
2061 Overflow = Res.ult(RHS);
2065 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2066 APInt Res = *this - RHS;
2067 Overflow = isNonNegative() != RHS.isNonNegative() &&
2068 Res.isNonNegative() != isNonNegative();
2072 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2073 APInt Res = *this-RHS;
2074 Overflow = Res.ugt(*this);
2078 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2079 // MININT/-1 --> overflow.
2080 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2084 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2085 APInt Res = *this * RHS;
2087 if (*this != 0 && RHS != 0)
2088 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2094 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2095 APInt Res = *this * RHS;
2097 if (*this != 0 && RHS != 0)
2098 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2104 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2105 Overflow = ShAmt >= getBitWidth();
2107 ShAmt = getBitWidth()-1;
2109 if (isNonNegative()) // Don't allow sign change.
2110 Overflow = ShAmt >= countLeadingZeros();
2112 Overflow = ShAmt >= countLeadingOnes();
2114 return *this << ShAmt;
2120 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2121 // Check our assumptions here
2122 assert(!str.empty() && "Invalid string length");
2123 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2125 "Radix should be 2, 8, 10, 16, or 36!");
2127 StringRef::iterator p = str.begin();
2128 size_t slen = str.size();
2129 bool isNeg = *p == '-';
2130 if (*p == '-' || *p == '+') {
2133 assert(slen && "String is only a sign, needs a value.");
2135 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2136 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2137 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2138 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2139 "Insufficient bit width");
2142 if (!isSingleWord())
2143 pVal = getClearedMemory(getNumWords());
2145 // Figure out if we can shift instead of multiply
2146 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2148 // Set up an APInt for the digit to add outside the loop so we don't
2149 // constantly construct/destruct it.
2150 APInt apdigit(getBitWidth(), 0);
2151 APInt apradix(getBitWidth(), radix);
2153 // Enter digit traversal loop
2154 for (StringRef::iterator e = str.end(); p != e; ++p) {
2155 unsigned digit = getDigit(*p, radix);
2156 assert(digit < radix && "Invalid character in digit string");
2158 // Shift or multiply the value by the radix
2166 // Add in the digit we just interpreted
2167 if (apdigit.isSingleWord())
2168 apdigit.VAL = digit;
2170 apdigit.pVal[0] = digit;
2173 // If its negative, put it in two's complement form
2176 this->flipAllBits();
2180 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2181 bool Signed, bool formatAsCLiteral) const {
2182 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2184 "Radix should be 2, 8, 10, or 16!");
2186 const char *Prefix = "";
2187 if (formatAsCLiteral) {
2190 // Binary literals are a non-standard extension added in gcc 4.3:
2191 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2203 // First, check for a zero value and just short circuit the logic below.
2206 Str.push_back(*Prefix);
2213 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2215 if (isSingleWord()) {
2217 char *BufPtr = Buffer+65;
2223 int64_t I = getSExtValue();
2233 Str.push_back(*Prefix);
2238 *--BufPtr = Digits[N % Radix];
2241 Str.append(BufPtr, Buffer+65);
2247 if (Signed && isNegative()) {
2248 // They want to print the signed version and it is a negative value
2249 // Flip the bits and add one to turn it into the equivalent positive
2250 // value and put a '-' in the result.
2257 Str.push_back(*Prefix);
2261 // We insert the digits backward, then reverse them to get the right order.
2262 unsigned StartDig = Str.size();
2264 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2265 // because the number of bits per digit (1, 3 and 4 respectively) divides
2266 // equaly. We just shift until the value is zero.
2267 if (Radix == 2 || Radix == 8 || Radix == 16) {
2268 // Just shift tmp right for each digit width until it becomes zero
2269 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2270 unsigned MaskAmt = Radix - 1;
2273 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2274 Str.push_back(Digits[Digit]);
2275 Tmp = Tmp.lshr(ShiftAmt);
2278 APInt divisor(Radix == 10? 4 : 8, Radix);
2280 APInt APdigit(1, 0);
2281 APInt tmp2(Tmp.getBitWidth(), 0);
2282 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2284 unsigned Digit = (unsigned)APdigit.getZExtValue();
2285 assert(Digit < Radix && "divide failed");
2286 Str.push_back(Digits[Digit]);
2291 // Reverse the digits before returning.
2292 std::reverse(Str.begin()+StartDig, Str.end());
2295 /// toString - This returns the APInt as a std::string. Note that this is an
2296 /// inefficient method. It is better to pass in a SmallVector/SmallString
2297 /// to the methods above.
2298 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2300 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2305 void APInt::dump() const {
2306 SmallString<40> S, U;
2307 this->toStringUnsigned(U);
2308 this->toStringSigned(S);
2309 dbgs() << "APInt(" << BitWidth << "b, "
2310 << U.str() << "u " << S.str() << "s)";
2313 void APInt::print(raw_ostream &OS, bool isSigned) const {
2315 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2319 // This implements a variety of operations on a representation of
2320 // arbitrary precision, two's-complement, bignum integer values.
2322 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2323 // and unrestricting assumption.
2324 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2325 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2327 /* Some handy functions local to this file. */
2330 /* Returns the integer part with the least significant BITS set.
2331 BITS cannot be zero. */
2332 static inline integerPart
2333 lowBitMask(unsigned int bits)
2335 assert(bits != 0 && bits <= integerPartWidth);
2337 return ~(integerPart) 0 >> (integerPartWidth - bits);
2340 /* Returns the value of the lower half of PART. */
2341 static inline integerPart
2342 lowHalf(integerPart part)
2344 return part & lowBitMask(integerPartWidth / 2);
2347 /* Returns the value of the upper half of PART. */
2348 static inline integerPart
2349 highHalf(integerPart part)
2351 return part >> (integerPartWidth / 2);
2354 /* Returns the bit number of the most significant set bit of a part.
2355 If the input number has no bits set -1U is returned. */
2357 partMSB(integerPart value)
2359 unsigned int n, msb;
2364 n = integerPartWidth / 2;
2379 /* Returns the bit number of the least significant set bit of a
2380 part. If the input number has no bits set -1U is returned. */
2382 partLSB(integerPart value)
2384 unsigned int n, lsb;
2389 lsb = integerPartWidth - 1;
2390 n = integerPartWidth / 2;
2405 /* Sets the least significant part of a bignum to the input value, and
2406 zeroes out higher parts. */
2408 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2415 for (i = 1; i < parts; i++)
2419 /* Assign one bignum to another. */
2421 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2425 for (i = 0; i < parts; i++)
2429 /* Returns true if a bignum is zero, false otherwise. */
2431 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2435 for (i = 0; i < parts; i++)
2442 /* Extract the given bit of a bignum; returns 0 or 1. */
2444 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2446 return (parts[bit / integerPartWidth] &
2447 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2450 /* Set the given bit of a bignum. */
2452 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2454 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2457 /* Clears the given bit of a bignum. */
2459 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2461 parts[bit / integerPartWidth] &=
2462 ~((integerPart) 1 << (bit % integerPartWidth));
2465 /* Returns the bit number of the least significant set bit of a
2466 number. If the input number has no bits set -1U is returned. */
2468 APInt::tcLSB(const integerPart *parts, unsigned int n)
2470 unsigned int i, lsb;
2472 for (i = 0; i < n; i++) {
2473 if (parts[i] != 0) {
2474 lsb = partLSB(parts[i]);
2476 return lsb + i * integerPartWidth;
2483 /* Returns the bit number of the most significant set bit of a number.
2484 If the input number has no bits set -1U is returned. */
2486 APInt::tcMSB(const integerPart *parts, unsigned int n)
2493 if (parts[n] != 0) {
2494 msb = partMSB(parts[n]);
2496 return msb + n * integerPartWidth;
2503 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2504 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2505 the least significant bit of DST. All high bits above srcBITS in
2506 DST are zero-filled. */
2508 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2509 unsigned int srcBits, unsigned int srcLSB)
2511 unsigned int firstSrcPart, dstParts, shift, n;
2513 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2514 assert(dstParts <= dstCount);
2516 firstSrcPart = srcLSB / integerPartWidth;
2517 tcAssign (dst, src + firstSrcPart, dstParts);
2519 shift = srcLSB % integerPartWidth;
2520 tcShiftRight (dst, dstParts, shift);
2522 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2523 in DST. If this is less that srcBits, append the rest, else
2524 clear the high bits. */
2525 n = dstParts * integerPartWidth - shift;
2527 integerPart mask = lowBitMask (srcBits - n);
2528 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2529 << n % integerPartWidth);
2530 } else if (n > srcBits) {
2531 if (srcBits % integerPartWidth)
2532 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2535 /* Clear high parts. */
2536 while (dstParts < dstCount)
2537 dst[dstParts++] = 0;
2540 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2542 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2543 integerPart c, unsigned int parts)
2549 for (i = 0; i < parts; i++) {
2554 dst[i] += rhs[i] + 1;
2565 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2567 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2568 integerPart c, unsigned int parts)
2574 for (i = 0; i < parts; i++) {
2579 dst[i] -= rhs[i] + 1;
2590 /* Negate a bignum in-place. */
2592 APInt::tcNegate(integerPart *dst, unsigned int parts)
2594 tcComplement(dst, parts);
2595 tcIncrement(dst, parts);
2598 /* DST += SRC * MULTIPLIER + CARRY if add is true
2599 DST = SRC * MULTIPLIER + CARRY if add is false
2601 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2602 they must start at the same point, i.e. DST == SRC.
2604 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2605 returned. Otherwise DST is filled with the least significant
2606 DSTPARTS parts of the result, and if all of the omitted higher
2607 parts were zero return zero, otherwise overflow occurred and
2610 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2611 integerPart multiplier, integerPart carry,
2612 unsigned int srcParts, unsigned int dstParts,
2617 /* Otherwise our writes of DST kill our later reads of SRC. */
2618 assert(dst <= src || dst >= src + srcParts);
2619 assert(dstParts <= srcParts + 1);
2621 /* N loops; minimum of dstParts and srcParts. */
2622 n = dstParts < srcParts ? dstParts: srcParts;
2624 for (i = 0; i < n; i++) {
2625 integerPart low, mid, high, srcPart;
2627 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2629 This cannot overflow, because
2631 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2633 which is less than n^2. */
2637 if (multiplier == 0 || srcPart == 0) {
2641 low = lowHalf(srcPart) * lowHalf(multiplier);
2642 high = highHalf(srcPart) * highHalf(multiplier);
2644 mid = lowHalf(srcPart) * highHalf(multiplier);
2645 high += highHalf(mid);
2646 mid <<= integerPartWidth / 2;
2647 if (low + mid < low)
2651 mid = highHalf(srcPart) * lowHalf(multiplier);
2652 high += highHalf(mid);
2653 mid <<= integerPartWidth / 2;
2654 if (low + mid < low)
2658 /* Now add carry. */
2659 if (low + carry < low)
2665 /* And now DST[i], and store the new low part there. */
2666 if (low + dst[i] < low)
2676 /* Full multiplication, there is no overflow. */
2677 assert(i + 1 == dstParts);
2681 /* We overflowed if there is carry. */
2685 /* We would overflow if any significant unwritten parts would be
2686 non-zero. This is true if any remaining src parts are non-zero
2687 and the multiplier is non-zero. */
2689 for (; i < srcParts; i++)
2693 /* We fitted in the narrow destination. */
2698 /* DST = LHS * RHS, where DST has the same width as the operands and
2699 is filled with the least significant parts of the result. Returns
2700 one if overflow occurred, otherwise zero. DST must be disjoint
2701 from both operands. */
2703 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2704 const integerPart *rhs, unsigned int parts)
2709 assert(dst != lhs && dst != rhs);
2712 tcSet(dst, 0, parts);
2714 for (i = 0; i < parts; i++)
2715 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2721 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2722 operands. No overflow occurs. DST must be disjoint from both
2723 operands. Returns the number of parts required to hold the
2726 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2727 const integerPart *rhs, unsigned int lhsParts,
2728 unsigned int rhsParts)
2730 /* Put the narrower number on the LHS for less loops below. */
2731 if (lhsParts > rhsParts) {
2732 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2736 assert(dst != lhs && dst != rhs);
2738 tcSet(dst, 0, rhsParts);
2740 for (n = 0; n < lhsParts; n++)
2741 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2743 n = lhsParts + rhsParts;
2745 return n - (dst[n - 1] == 0);
2749 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2750 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2751 set REMAINDER to the remainder, return zero. i.e.
2753 OLD_LHS = RHS * LHS + REMAINDER
2755 SCRATCH is a bignum of the same size as the operands and result for
2756 use by the routine; its contents need not be initialized and are
2757 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2760 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2761 integerPart *remainder, integerPart *srhs,
2764 unsigned int n, shiftCount;
2767 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2769 shiftCount = tcMSB(rhs, parts) + 1;
2770 if (shiftCount == 0)
2773 shiftCount = parts * integerPartWidth - shiftCount;
2774 n = shiftCount / integerPartWidth;
2775 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2777 tcAssign(srhs, rhs, parts);
2778 tcShiftLeft(srhs, parts, shiftCount);
2779 tcAssign(remainder, lhs, parts);
2780 tcSet(lhs, 0, parts);
2782 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2787 compare = tcCompare(remainder, srhs, parts);
2789 tcSubtract(remainder, srhs, 0, parts);
2793 if (shiftCount == 0)
2796 tcShiftRight(srhs, parts, 1);
2797 if ((mask >>= 1) == 0)
2798 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2804 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2805 There are no restrictions on COUNT. */
2807 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2810 unsigned int jump, shift;
2812 /* Jump is the inter-part jump; shift is is intra-part shift. */
2813 jump = count / integerPartWidth;
2814 shift = count % integerPartWidth;
2816 while (parts > jump) {
2821 /* dst[i] comes from the two parts src[i - jump] and, if we have
2822 an intra-part shift, src[i - jump - 1]. */
2823 part = dst[parts - jump];
2826 if (parts >= jump + 1)
2827 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2838 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2839 zero. There are no restrictions on COUNT. */
2841 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2844 unsigned int i, jump, shift;
2846 /* Jump is the inter-part jump; shift is is intra-part shift. */
2847 jump = count / integerPartWidth;
2848 shift = count % integerPartWidth;
2850 /* Perform the shift. This leaves the most significant COUNT bits
2851 of the result at zero. */
2852 for (i = 0; i < parts; i++) {
2855 if (i + jump >= parts) {
2858 part = dst[i + jump];
2861 if (i + jump + 1 < parts)
2862 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2871 /* Bitwise and of two bignums. */
2873 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2877 for (i = 0; i < parts; i++)
2881 /* Bitwise inclusive or of two bignums. */
2883 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2887 for (i = 0; i < parts; i++)
2891 /* Bitwise exclusive or of two bignums. */
2893 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2897 for (i = 0; i < parts; i++)
2901 /* Complement a bignum in-place. */
2903 APInt::tcComplement(integerPart *dst, unsigned int parts)
2907 for (i = 0; i < parts; i++)
2911 /* Comparison (unsigned) of two bignums. */
2913 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2918 if (lhs[parts] == rhs[parts])
2921 if (lhs[parts] > rhs[parts])
2930 /* Increment a bignum in-place, return the carry flag. */
2932 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2936 for (i = 0; i < parts; i++)
2943 /* Set the least significant BITS bits of a bignum, clear the
2946 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2952 while (bits > integerPartWidth) {
2953 dst[i++] = ~(integerPart) 0;
2954 bits -= integerPartWidth;
2958 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);