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 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/FoldingSet.h"
17 #include "llvm/ADT/Hashing.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/ADT/StringRef.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 #define DEBUG_TYPE "apint"
32 /// A utility function for allocating memory, checking for allocation failures,
33 /// and ensuring the contents are zeroed.
34 inline static uint64_t* getClearedMemory(unsigned numWords) {
35 uint64_t * result = new uint64_t[numWords];
36 assert(result && "APInt memory allocation fails!");
37 memset(result, 0, numWords * sizeof(uint64_t));
41 /// A utility function for allocating memory and checking for allocation
42 /// failure. The content is not zeroed.
43 inline static uint64_t* getMemory(unsigned numWords) {
44 uint64_t * result = new uint64_t[numWords];
45 assert(result && "APInt memory allocation fails!");
49 /// A utility function that converts a character to a digit.
50 inline static unsigned getDigit(char cdigit, uint8_t radix) {
53 if (radix == 16 || radix == 36) {
77 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
78 pVal = getClearedMemory(getNumWords());
80 if (isSigned && int64_t(val) < 0)
81 for (unsigned i = 1; i < getNumWords(); ++i)
85 void APInt::initSlowCase(const APInt& that) {
86 pVal = getMemory(getNumWords());
87 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
90 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
91 assert(BitWidth && "Bitwidth too small");
92 assert(bigVal.data() && "Null pointer detected!");
96 // Get memory, cleared to 0
97 pVal = getClearedMemory(getNumWords());
98 // Calculate the number of words to copy
99 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
100 // Copy the words from bigVal to pVal
101 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
103 // Make sure unused high bits are cleared
107 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
108 : BitWidth(numBits), VAL(0) {
109 initFromArray(bigVal);
112 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
113 : BitWidth(numBits), VAL(0) {
114 initFromArray(makeArrayRef(bigVal, numWords));
117 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
118 : BitWidth(numbits), VAL(0) {
119 assert(BitWidth && "Bitwidth too small");
120 fromString(numbits, Str, radix);
123 APInt& APInt::AssignSlowCase(const APInt& RHS) {
124 // Don't do anything for X = X
128 if (BitWidth == RHS.getBitWidth()) {
129 // assume same bit-width single-word case is already handled
130 assert(!isSingleWord());
131 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
135 if (isSingleWord()) {
136 // assume case where both are single words is already handled
137 assert(!RHS.isSingleWord());
139 pVal = getMemory(RHS.getNumWords());
140 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
141 } else if (getNumWords() == RHS.getNumWords())
142 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
143 else if (RHS.isSingleWord()) {
148 pVal = getMemory(RHS.getNumWords());
149 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
151 BitWidth = RHS.BitWidth;
152 return clearUnusedBits();
155 APInt& APInt::operator=(uint64_t RHS) {
160 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
162 return clearUnusedBits();
165 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
166 void APInt::Profile(FoldingSetNodeID& ID) const {
167 ID.AddInteger(BitWidth);
169 if (isSingleWord()) {
174 unsigned NumWords = getNumWords();
175 for (unsigned i = 0; i < NumWords; ++i)
176 ID.AddInteger(pVal[i]);
179 /// add_1 - This function adds a single "digit" integer, y, to the multiple
180 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
181 /// 1 is returned if there is a carry out, otherwise 0 is returned.
182 /// @returns the carry of the addition.
183 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
184 for (unsigned i = 0; i < len; ++i) {
187 y = 1; // Carry one to next digit.
189 y = 0; // No need to carry so exit early
196 /// @brief Prefix increment operator. Increments the APInt by one.
197 APInt& APInt::operator++() {
201 add_1(pVal, pVal, getNumWords(), 1);
202 return clearUnusedBits();
205 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
206 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
207 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
208 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
209 /// In other words, if y > x then this function returns 1, otherwise 0.
210 /// @returns the borrow out of the subtraction
211 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
212 for (unsigned i = 0; i < len; ++i) {
216 y = 1; // We have to "borrow 1" from next "digit"
218 y = 0; // No need to borrow
219 break; // Remaining digits are unchanged so exit early
225 /// @brief Prefix decrement operator. Decrements the APInt by one.
226 APInt& APInt::operator--() {
230 sub_1(pVal, getNumWords(), 1);
231 return clearUnusedBits();
234 /// add - This function adds the integer array x to the integer array Y and
235 /// places the result in dest.
236 /// @returns the carry out from the addition
237 /// @brief General addition of 64-bit integer arrays
238 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
241 for (unsigned i = 0; i< len; ++i) {
242 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
243 dest[i] = x[i] + y[i] + carry;
244 carry = dest[i] < limit || (carry && dest[i] == limit);
249 /// Adds the RHS APint to this APInt.
250 /// @returns this, after addition of RHS.
251 /// @brief Addition assignment operator.
252 APInt& APInt::operator+=(const APInt& RHS) {
253 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
257 add(pVal, pVal, RHS.pVal, getNumWords());
259 return clearUnusedBits();
262 /// Subtracts the integer array y from the integer array x
263 /// @returns returns the borrow out.
264 /// @brief Generalized subtraction of 64-bit integer arrays.
265 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
268 for (unsigned i = 0; i < len; ++i) {
269 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
270 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
271 dest[i] = x_tmp - y[i];
276 /// Subtracts the RHS APInt from this APInt
277 /// @returns this, after subtraction
278 /// @brief Subtraction assignment operator.
279 APInt& APInt::operator-=(const APInt& RHS) {
280 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
284 sub(pVal, pVal, RHS.pVal, getNumWords());
285 return clearUnusedBits();
288 /// Multiplies an integer array, x, by a uint64_t integer and places the result
290 /// @returns the carry out of the multiplication.
291 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
292 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
293 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
294 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
297 // For each digit of x.
298 for (unsigned i = 0; i < len; ++i) {
299 // Split x into high and low words
300 uint64_t lx = x[i] & 0xffffffffULL;
301 uint64_t hx = x[i] >> 32;
302 // hasCarry - A flag to indicate if there is a carry to the next digit.
303 // hasCarry == 0, no carry
304 // hasCarry == 1, has carry
305 // hasCarry == 2, no carry and the calculation result == 0.
306 uint8_t hasCarry = 0;
307 dest[i] = carry + lx * ly;
308 // Determine if the add above introduces carry.
309 hasCarry = (dest[i] < carry) ? 1 : 0;
310 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
311 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
312 // (2^32 - 1) + 2^32 = 2^64.
313 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
315 carry += (lx * hy) & 0xffffffffULL;
316 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
317 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
318 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
323 /// Multiplies integer array x by integer array y and stores the result into
324 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
325 /// @brief Generalized multiplicate of integer arrays.
326 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
328 dest[xlen] = mul_1(dest, x, xlen, y[0]);
329 for (unsigned i = 1; i < ylen; ++i) {
330 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
331 uint64_t carry = 0, lx = 0, hx = 0;
332 for (unsigned j = 0; j < xlen; ++j) {
333 lx = x[j] & 0xffffffffULL;
335 // hasCarry - A flag to indicate if has carry.
336 // hasCarry == 0, no carry
337 // hasCarry == 1, has carry
338 // hasCarry == 2, no carry and the calculation result == 0.
339 uint8_t hasCarry = 0;
340 uint64_t resul = carry + lx * ly;
341 hasCarry = (resul < carry) ? 1 : 0;
342 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
343 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
345 carry += (lx * hy) & 0xffffffffULL;
346 resul = (carry << 32) | (resul & 0xffffffffULL);
348 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
349 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
350 ((lx * hy) >> 32) + hx * hy;
352 dest[i+xlen] = carry;
356 APInt& APInt::operator*=(const APInt& RHS) {
357 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
358 if (isSingleWord()) {
364 // Get some bit facts about LHS and check for zero
365 unsigned lhsBits = getActiveBits();
366 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
371 // Get some bit facts about RHS and check for zero
372 unsigned rhsBits = RHS.getActiveBits();
373 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
380 // Allocate space for the result
381 unsigned destWords = rhsWords + lhsWords;
382 uint64_t *dest = getMemory(destWords);
384 // Perform the long multiply
385 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
387 // Copy result back into *this
389 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
390 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
393 // delete dest array and return
398 APInt& APInt::operator&=(const APInt& RHS) {
399 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
400 if (isSingleWord()) {
404 unsigned numWords = getNumWords();
405 for (unsigned i = 0; i < numWords; ++i)
406 pVal[i] &= RHS.pVal[i];
410 APInt& APInt::operator|=(const APInt& RHS) {
411 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
412 if (isSingleWord()) {
416 unsigned numWords = getNumWords();
417 for (unsigned i = 0; i < numWords; ++i)
418 pVal[i] |= RHS.pVal[i];
422 APInt& APInt::operator^=(const APInt& RHS) {
423 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
424 if (isSingleWord()) {
426 this->clearUnusedBits();
429 unsigned numWords = getNumWords();
430 for (unsigned i = 0; i < numWords; ++i)
431 pVal[i] ^= RHS.pVal[i];
432 return clearUnusedBits();
435 APInt APInt::AndSlowCase(const APInt& RHS) const {
436 unsigned numWords = getNumWords();
437 uint64_t* val = getMemory(numWords);
438 for (unsigned i = 0; i < numWords; ++i)
439 val[i] = pVal[i] & RHS.pVal[i];
440 return APInt(val, getBitWidth());
443 APInt APInt::OrSlowCase(const APInt& RHS) const {
444 unsigned numWords = getNumWords();
445 uint64_t *val = getMemory(numWords);
446 for (unsigned i = 0; i < numWords; ++i)
447 val[i] = pVal[i] | RHS.pVal[i];
448 return APInt(val, getBitWidth());
451 APInt APInt::XorSlowCase(const APInt& RHS) const {
452 unsigned numWords = getNumWords();
453 uint64_t *val = getMemory(numWords);
454 for (unsigned i = 0; i < numWords; ++i)
455 val[i] = pVal[i] ^ RHS.pVal[i];
457 APInt Result(val, getBitWidth());
458 // 0^0==1 so clear the high bits in case they got set.
459 Result.clearUnusedBits();
463 APInt APInt::operator*(const APInt& RHS) const {
464 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
466 return APInt(BitWidth, VAL * RHS.VAL);
472 APInt APInt::operator+(const APInt& RHS) const {
473 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
475 return APInt(BitWidth, VAL + RHS.VAL);
476 APInt Result(BitWidth, 0);
477 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
478 Result.clearUnusedBits();
482 APInt APInt::operator-(const APInt& RHS) const {
483 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
485 return APInt(BitWidth, VAL - RHS.VAL);
486 APInt Result(BitWidth, 0);
487 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
488 Result.clearUnusedBits();
492 bool APInt::EqualSlowCase(const APInt& RHS) const {
493 // Get some facts about the number of bits used in the two operands.
494 unsigned n1 = getActiveBits();
495 unsigned n2 = RHS.getActiveBits();
497 // If the number of bits isn't the same, they aren't equal
501 // If the number of bits fits in a word, we only need to compare the low word.
502 if (n1 <= APINT_BITS_PER_WORD)
503 return pVal[0] == RHS.pVal[0];
505 // Otherwise, compare everything
506 for (int i = whichWord(n1 - 1); i >= 0; --i)
507 if (pVal[i] != RHS.pVal[i])
512 bool APInt::EqualSlowCase(uint64_t Val) const {
513 unsigned n = getActiveBits();
514 if (n <= APINT_BITS_PER_WORD)
515 return pVal[0] == Val;
520 bool APInt::ult(const APInt& RHS) const {
521 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
523 return VAL < RHS.VAL;
525 // Get active bit length of both operands
526 unsigned n1 = getActiveBits();
527 unsigned n2 = RHS.getActiveBits();
529 // If magnitude of LHS is less than RHS, return true.
533 // If magnitude of RHS is greather than LHS, return false.
537 // If they bot fit in a word, just compare the low order word
538 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
539 return pVal[0] < RHS.pVal[0];
541 // Otherwise, compare all words
542 unsigned topWord = whichWord(std::max(n1,n2)-1);
543 for (int i = topWord; i >= 0; --i) {
544 if (pVal[i] > RHS.pVal[i])
546 if (pVal[i] < RHS.pVal[i])
552 bool APInt::slt(const APInt& RHS) const {
553 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
554 if (isSingleWord()) {
555 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
556 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
557 return lhsSext < rhsSext;
562 bool lhsNeg = isNegative();
563 bool rhsNeg = rhs.isNegative();
565 // Sign bit is set so perform two's complement to make it positive
570 // Sign bit is set so perform two's complement to make it positive
575 // Now we have unsigned values to compare so do the comparison if necessary
576 // based on the negativeness of the values.
588 void APInt::setBit(unsigned bitPosition) {
590 VAL |= maskBit(bitPosition);
592 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
595 /// Set the given bit to 0 whose position is given as "bitPosition".
596 /// @brief Set a given bit to 0.
597 void APInt::clearBit(unsigned bitPosition) {
599 VAL &= ~maskBit(bitPosition);
601 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
604 /// @brief Toggle every bit to its opposite value.
606 /// Toggle a given bit to its opposite value whose position is given
607 /// as "bitPosition".
608 /// @brief Toggles a given bit to its opposite value.
609 void APInt::flipBit(unsigned bitPosition) {
610 assert(bitPosition < BitWidth && "Out of the bit-width range!");
611 if ((*this)[bitPosition]) clearBit(bitPosition);
612 else setBit(bitPosition);
615 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
616 assert(!str.empty() && "Invalid string length");
617 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
619 "Radix should be 2, 8, 10, 16, or 36!");
621 size_t slen = str.size();
623 // Each computation below needs to know if it's negative.
624 StringRef::iterator p = str.begin();
625 unsigned isNegative = *p == '-';
626 if (*p == '-' || *p == '+') {
629 assert(slen && "String is only a sign, needs a value.");
632 // For radixes of power-of-two values, the bits required is accurately and
635 return slen + isNegative;
637 return slen * 3 + isNegative;
639 return slen * 4 + isNegative;
643 // This is grossly inefficient but accurate. We could probably do something
644 // with a computation of roughly slen*64/20 and then adjust by the value of
645 // the first few digits. But, I'm not sure how accurate that could be.
647 // Compute a sufficient number of bits that is always large enough but might
648 // be too large. This avoids the assertion in the constructor. This
649 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
650 // bits in that case.
652 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
653 : (slen == 1 ? 7 : slen * 16/3);
655 // Convert to the actual binary value.
656 APInt tmp(sufficient, StringRef(p, slen), radix);
658 // Compute how many bits are required. If the log is infinite, assume we need
660 unsigned log = tmp.logBase2();
661 if (log == (unsigned)-1) {
662 return isNegative + 1;
664 return isNegative + log + 1;
668 hash_code llvm::hash_value(const APInt &Arg) {
669 if (Arg.isSingleWord())
670 return hash_combine(Arg.VAL);
672 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
675 /// HiBits - This function returns the high "numBits" bits of this APInt.
676 APInt APInt::getHiBits(unsigned numBits) const {
677 return APIntOps::lshr(*this, BitWidth - numBits);
680 /// LoBits - This function returns the low "numBits" bits of this APInt.
681 APInt APInt::getLoBits(unsigned numBits) const {
682 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
686 unsigned APInt::countLeadingZerosSlowCase() const {
687 // Treat the most significand word differently because it might have
688 // meaningless bits set beyond the precision.
689 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
691 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
693 MSWMask = ~integerPart(0);
694 BitsInMSW = APINT_BITS_PER_WORD;
697 unsigned i = getNumWords();
698 integerPart MSW = pVal[i-1] & MSWMask;
700 return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
702 unsigned Count = BitsInMSW;
703 for (--i; i > 0u; --i) {
705 Count += APINT_BITS_PER_WORD;
707 Count += llvm::countLeadingZeros(pVal[i-1]);
714 unsigned APInt::countLeadingOnes() const {
716 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
718 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
721 highWordBits = APINT_BITS_PER_WORD;
724 shift = APINT_BITS_PER_WORD - highWordBits;
726 int i = getNumWords() - 1;
727 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
728 if (Count == highWordBits) {
729 for (i--; i >= 0; --i) {
730 if (pVal[i] == -1ULL)
731 Count += APINT_BITS_PER_WORD;
733 Count += llvm::countLeadingOnes(pVal[i]);
741 unsigned APInt::countTrailingZeros() const {
743 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
746 for (; i < getNumWords() && pVal[i] == 0; ++i)
747 Count += APINT_BITS_PER_WORD;
748 if (i < getNumWords())
749 Count += llvm::countTrailingZeros(pVal[i]);
750 return std::min(Count, BitWidth);
753 unsigned APInt::countTrailingOnesSlowCase() const {
756 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
757 Count += APINT_BITS_PER_WORD;
758 if (i < getNumWords())
759 Count += llvm::countTrailingOnes(pVal[i]);
760 return std::min(Count, BitWidth);
763 unsigned APInt::countPopulationSlowCase() const {
765 for (unsigned i = 0; i < getNumWords(); ++i)
766 Count += llvm::countPopulation(pVal[i]);
770 /// Perform a logical right-shift from Src to Dst, which must be equal or
771 /// non-overlapping, of Words words, by Shift, which must be less than 64.
772 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
775 for (int I = Words - 1; I >= 0; --I) {
776 uint64_t Tmp = Src[I];
777 Dst[I] = (Tmp >> Shift) | Carry;
778 Carry = Tmp << (64 - Shift);
782 APInt APInt::byteSwap() const {
783 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
785 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
787 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
788 if (BitWidth == 48) {
789 unsigned Tmp1 = unsigned(VAL >> 16);
790 Tmp1 = ByteSwap_32(Tmp1);
791 uint16_t Tmp2 = uint16_t(VAL);
792 Tmp2 = ByteSwap_16(Tmp2);
793 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
796 return APInt(BitWidth, ByteSwap_64(VAL));
798 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
799 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
800 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
801 if (Result.BitWidth != BitWidth) {
802 lshrNear(Result.pVal, Result.pVal, getNumWords(),
803 Result.BitWidth - BitWidth);
804 Result.BitWidth = BitWidth;
809 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
811 APInt A = API1, B = API2;
814 B = APIntOps::urem(A, B);
820 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
827 // Get the sign bit from the highest order bit
828 bool isNeg = T.I >> 63;
830 // Get the 11-bit exponent and adjust for the 1023 bit bias
831 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
833 // If the exponent is negative, the value is < 0 so just return 0.
835 return APInt(width, 0u);
837 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
838 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
840 // If the exponent doesn't shift all bits out of the mantissa
842 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
843 APInt(width, mantissa >> (52 - exp));
845 // If the client didn't provide enough bits for us to shift the mantissa into
846 // then the result is undefined, just return 0
847 if (width <= exp - 52)
848 return APInt(width, 0);
850 // Otherwise, we have to shift the mantissa bits up to the right location
851 APInt Tmp(width, mantissa);
852 Tmp = Tmp.shl((unsigned)exp - 52);
853 return isNeg ? -Tmp : Tmp;
856 /// RoundToDouble - This function converts this APInt to a double.
857 /// The layout for double is as following (IEEE Standard 754):
858 /// --------------------------------------
859 /// | Sign Exponent Fraction Bias |
860 /// |-------------------------------------- |
861 /// | 1[63] 11[62-52] 52[51-00] 1023 |
862 /// --------------------------------------
863 double APInt::roundToDouble(bool isSigned) const {
865 // Handle the simple case where the value is contained in one uint64_t.
866 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
867 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
869 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
872 return double(getWord(0));
875 // Determine if the value is negative.
876 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
878 // Construct the absolute value if we're negative.
879 APInt Tmp(isNeg ? -(*this) : (*this));
881 // Figure out how many bits we're using.
882 unsigned n = Tmp.getActiveBits();
884 // The exponent (without bias normalization) is just the number of bits
885 // we are using. Note that the sign bit is gone since we constructed the
889 // Return infinity for exponent overflow
891 if (!isSigned || !isNeg)
892 return std::numeric_limits<double>::infinity();
894 return -std::numeric_limits<double>::infinity();
896 exp += 1023; // Increment for 1023 bias
898 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
899 // extract the high 52 bits from the correct words in pVal.
901 unsigned hiWord = whichWord(n-1);
903 mantissa = Tmp.pVal[0];
905 mantissa >>= n - 52; // shift down, we want the top 52 bits.
907 assert(hiWord > 0 && "huh?");
908 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
909 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
910 mantissa = hibits | lobits;
913 // The leading bit of mantissa is implicit, so get rid of it.
914 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
919 T.I = sign | (exp << 52) | mantissa;
923 // Truncate to new width.
924 APInt APInt::trunc(unsigned width) const {
925 assert(width < BitWidth && "Invalid APInt Truncate request");
926 assert(width && "Can't truncate to 0 bits");
928 if (width <= APINT_BITS_PER_WORD)
929 return APInt(width, getRawData()[0]);
931 APInt Result(getMemory(getNumWords(width)), width);
935 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
936 Result.pVal[i] = pVal[i];
938 // Truncate and copy any partial word.
939 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
941 Result.pVal[i] = pVal[i] << bits >> bits;
946 // Sign extend to a new width.
947 APInt APInt::sext(unsigned width) const {
948 assert(width > BitWidth && "Invalid APInt SignExtend request");
950 if (width <= APINT_BITS_PER_WORD) {
951 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
952 val = (int64_t)val >> (width - BitWidth);
953 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
956 APInt Result(getMemory(getNumWords(width)), width);
961 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
962 word = getRawData()[i];
963 Result.pVal[i] = word;
966 // Read and sign-extend any partial word.
967 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
969 word = (int64_t)getRawData()[i] << bits >> bits;
971 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
973 // Write remaining full words.
974 for (; i != width / APINT_BITS_PER_WORD; i++) {
975 Result.pVal[i] = word;
976 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
979 // Write any partial word.
980 bits = (0 - width) % APINT_BITS_PER_WORD;
982 Result.pVal[i] = word << bits >> bits;
987 // Zero extend to a new width.
988 APInt APInt::zext(unsigned width) const {
989 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
991 if (width <= APINT_BITS_PER_WORD)
992 return APInt(width, VAL);
994 APInt Result(getMemory(getNumWords(width)), width);
998 for (i = 0; i != getNumWords(); i++)
999 Result.pVal[i] = getRawData()[i];
1001 // Zero remaining words.
1002 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1007 APInt APInt::zextOrTrunc(unsigned width) const {
1008 if (BitWidth < width)
1010 if (BitWidth > width)
1011 return trunc(width);
1015 APInt APInt::sextOrTrunc(unsigned width) const {
1016 if (BitWidth < width)
1018 if (BitWidth > width)
1019 return trunc(width);
1023 APInt APInt::zextOrSelf(unsigned width) const {
1024 if (BitWidth < width)
1029 APInt APInt::sextOrSelf(unsigned width) const {
1030 if (BitWidth < width)
1035 /// Arithmetic right-shift this APInt by shiftAmt.
1036 /// @brief Arithmetic right-shift function.
1037 APInt APInt::ashr(const APInt &shiftAmt) const {
1038 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1041 /// Arithmetic right-shift this APInt by shiftAmt.
1042 /// @brief Arithmetic right-shift function.
1043 APInt APInt::ashr(unsigned shiftAmt) const {
1044 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1045 // Handle a degenerate case
1049 // Handle single word shifts with built-in ashr
1050 if (isSingleWord()) {
1051 if (shiftAmt == BitWidth)
1052 return APInt(BitWidth, 0); // undefined
1054 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1055 return APInt(BitWidth,
1056 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1060 // If all the bits were shifted out, the result is, technically, undefined.
1061 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1062 // issues in the algorithm below.
1063 if (shiftAmt == BitWidth) {
1065 return APInt(BitWidth, -1ULL, true);
1067 return APInt(BitWidth, 0);
1070 // Create some space for the result.
1071 uint64_t * val = new uint64_t[getNumWords()];
1073 // Compute some values needed by the following shift algorithms
1074 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1075 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1076 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1077 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1078 if (bitsInWord == 0)
1079 bitsInWord = APINT_BITS_PER_WORD;
1081 // If we are shifting whole words, just move whole words
1082 if (wordShift == 0) {
1083 // Move the words containing significant bits
1084 for (unsigned i = 0; i <= breakWord; ++i)
1085 val[i] = pVal[i+offset]; // move whole word
1087 // Adjust the top significant word for sign bit fill, if negative
1089 if (bitsInWord < APINT_BITS_PER_WORD)
1090 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1092 // Shift the low order words
1093 for (unsigned i = 0; i < breakWord; ++i) {
1094 // This combines the shifted corresponding word with the low bits from
1095 // the next word (shifted into this word's high bits).
1096 val[i] = (pVal[i+offset] >> wordShift) |
1097 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1100 // Shift the break word. In this case there are no bits from the next word
1101 // to include in this word.
1102 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1104 // Deal with sign extension in the break word, and possibly the word before
1107 if (wordShift > bitsInWord) {
1110 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1111 val[breakWord] |= ~0ULL;
1113 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1117 // Remaining words are 0 or -1, just assign them.
1118 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1119 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1121 APInt Result(val, BitWidth);
1122 Result.clearUnusedBits();
1126 /// Logical right-shift this APInt by shiftAmt.
1127 /// @brief Logical right-shift function.
1128 APInt APInt::lshr(const APInt &shiftAmt) const {
1129 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1132 /// Logical right-shift this APInt by shiftAmt.
1133 /// @brief Logical right-shift function.
1134 APInt APInt::lshr(unsigned shiftAmt) const {
1135 if (isSingleWord()) {
1136 if (shiftAmt >= BitWidth)
1137 return APInt(BitWidth, 0);
1139 return APInt(BitWidth, this->VAL >> shiftAmt);
1142 // If all the bits were shifted out, the result is 0. This avoids issues
1143 // with shifting by the size of the integer type, which produces undefined
1144 // results. We define these "undefined results" to always be 0.
1145 if (shiftAmt >= BitWidth)
1146 return APInt(BitWidth, 0);
1148 // If none of the bits are shifted out, the result is *this. This avoids
1149 // issues with shifting by the size of the integer type, which produces
1150 // undefined results in the code below. This is also an optimization.
1154 // Create some space for the result.
1155 uint64_t * val = new uint64_t[getNumWords()];
1157 // If we are shifting less than a word, compute the shift with a simple carry
1158 if (shiftAmt < APINT_BITS_PER_WORD) {
1159 lshrNear(val, pVal, getNumWords(), shiftAmt);
1160 APInt Result(val, BitWidth);
1161 Result.clearUnusedBits();
1165 // Compute some values needed by the remaining shift algorithms
1166 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1167 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1169 // If we are shifting whole words, just move whole words
1170 if (wordShift == 0) {
1171 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1172 val[i] = pVal[i+offset];
1173 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1175 APInt Result(val, BitWidth);
1176 Result.clearUnusedBits();
1180 // Shift the low order words
1181 unsigned breakWord = getNumWords() - offset -1;
1182 for (unsigned i = 0; i < breakWord; ++i)
1183 val[i] = (pVal[i+offset] >> wordShift) |
1184 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1185 // Shift the break word.
1186 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1188 // Remaining words are 0
1189 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1191 APInt Result(val, BitWidth);
1192 Result.clearUnusedBits();
1196 /// Left-shift this APInt by shiftAmt.
1197 /// @brief Left-shift function.
1198 APInt APInt::shl(const APInt &shiftAmt) const {
1199 // It's undefined behavior in C to shift by BitWidth or greater.
1200 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1203 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1204 // If all the bits were shifted out, the result is 0. This avoids issues
1205 // with shifting by the size of the integer type, which produces undefined
1206 // results. We define these "undefined results" to always be 0.
1207 if (shiftAmt == BitWidth)
1208 return APInt(BitWidth, 0);
1210 // If none of the bits are shifted out, the result is *this. This avoids a
1211 // lshr by the words size in the loop below which can produce incorrect
1212 // results. It also avoids the expensive computation below for a common case.
1216 // Create some space for the result.
1217 uint64_t * val = new uint64_t[getNumWords()];
1219 // If we are shifting less than a word, do it the easy way
1220 if (shiftAmt < APINT_BITS_PER_WORD) {
1222 for (unsigned i = 0; i < getNumWords(); i++) {
1223 val[i] = pVal[i] << shiftAmt | carry;
1224 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1226 APInt Result(val, BitWidth);
1227 Result.clearUnusedBits();
1231 // Compute some values needed by the remaining shift algorithms
1232 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1233 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1235 // If we are shifting whole words, just move whole words
1236 if (wordShift == 0) {
1237 for (unsigned i = 0; i < offset; i++)
1239 for (unsigned i = offset; i < getNumWords(); i++)
1240 val[i] = pVal[i-offset];
1241 APInt Result(val, BitWidth);
1242 Result.clearUnusedBits();
1246 // Copy whole words from this to Result.
1247 unsigned i = getNumWords() - 1;
1248 for (; i > offset; --i)
1249 val[i] = pVal[i-offset] << wordShift |
1250 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1251 val[offset] = pVal[0] << wordShift;
1252 for (i = 0; i < offset; ++i)
1254 APInt Result(val, BitWidth);
1255 Result.clearUnusedBits();
1259 APInt APInt::rotl(const APInt &rotateAmt) const {
1260 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1263 APInt APInt::rotl(unsigned rotateAmt) const {
1264 rotateAmt %= BitWidth;
1267 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1270 APInt APInt::rotr(const APInt &rotateAmt) const {
1271 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1274 APInt APInt::rotr(unsigned rotateAmt) const {
1275 rotateAmt %= BitWidth;
1278 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1281 // Square Root - this method computes and returns the square root of "this".
1282 // Three mechanisms are used for computation. For small values (<= 5 bits),
1283 // a table lookup is done. This gets some performance for common cases. For
1284 // values using less than 52 bits, the value is converted to double and then
1285 // the libc sqrt function is called. The result is rounded and then converted
1286 // back to a uint64_t which is then used to construct the result. Finally,
1287 // the Babylonian method for computing square roots is used.
1288 APInt APInt::sqrt() const {
1290 // Determine the magnitude of the value.
1291 unsigned magnitude = getActiveBits();
1293 // Use a fast table for some small values. This also gets rid of some
1294 // rounding errors in libc sqrt for small values.
1295 if (magnitude <= 5) {
1296 static const uint8_t results[32] = {
1299 /* 3- 6 */ 2, 2, 2, 2,
1300 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1301 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1302 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1305 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1308 // If the magnitude of the value fits in less than 52 bits (the precision of
1309 // an IEEE double precision floating point value), then we can use the
1310 // libc sqrt function which will probably use a hardware sqrt computation.
1311 // This should be faster than the algorithm below.
1312 if (magnitude < 52) {
1313 return APInt(BitWidth,
1314 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1317 // Okay, all the short cuts are exhausted. We must compute it. The following
1318 // is a classical Babylonian method for computing the square root. This code
1319 // was adapted to APInt from a wikipedia article on such computations.
1320 // See http://www.wikipedia.org/ and go to the page named
1321 // Calculate_an_integer_square_root.
1322 unsigned nbits = BitWidth, i = 4;
1323 APInt testy(BitWidth, 16);
1324 APInt x_old(BitWidth, 1);
1325 APInt x_new(BitWidth, 0);
1326 APInt two(BitWidth, 2);
1328 // Select a good starting value using binary logarithms.
1329 for (;; i += 2, testy = testy.shl(2))
1330 if (i >= nbits || this->ule(testy)) {
1331 x_old = x_old.shl(i / 2);
1335 // Use the Babylonian method to arrive at the integer square root:
1337 x_new = (this->udiv(x_old) + x_old).udiv(two);
1338 if (x_old.ule(x_new))
1343 // Make sure we return the closest approximation
1344 // NOTE: The rounding calculation below is correct. It will produce an
1345 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1346 // determined to be a rounding issue with pari/gp as it begins to use a
1347 // floating point representation after 192 bits. There are no discrepancies
1348 // between this algorithm and pari/gp for bit widths < 192 bits.
1349 APInt square(x_old * x_old);
1350 APInt nextSquare((x_old + 1) * (x_old +1));
1351 if (this->ult(square))
1353 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1354 APInt midpoint((nextSquare - square).udiv(two));
1355 APInt offset(*this - square);
1356 if (offset.ult(midpoint))
1361 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1362 /// iterative extended Euclidean algorithm is used to solve for this value,
1363 /// however we simplify it to speed up calculating only the inverse, and take
1364 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1365 /// (potentially large) APInts around.
1366 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1367 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1369 // Using the properties listed at the following web page (accessed 06/21/08):
1370 // http://www.numbertheory.org/php/euclid.html
1371 // (especially the properties numbered 3, 4 and 9) it can be proved that
1372 // BitWidth bits suffice for all the computations in the algorithm implemented
1373 // below. More precisely, this number of bits suffice if the multiplicative
1374 // inverse exists, but may not suffice for the general extended Euclidean
1377 APInt r[2] = { modulo, *this };
1378 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1379 APInt q(BitWidth, 0);
1382 for (i = 0; r[i^1] != 0; i ^= 1) {
1383 // An overview of the math without the confusing bit-flipping:
1384 // q = r[i-2] / r[i-1]
1385 // r[i] = r[i-2] % r[i-1]
1386 // t[i] = t[i-2] - t[i-1] * q
1387 udivrem(r[i], r[i^1], q, r[i]);
1391 // If this APInt and the modulo are not coprime, there is no multiplicative
1392 // inverse, so return 0. We check this by looking at the next-to-last
1393 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1396 return APInt(BitWidth, 0);
1398 // The next-to-last t is the multiplicative inverse. However, we are
1399 // interested in a positive inverse. Calcuate a positive one from a negative
1400 // one if necessary. A simple addition of the modulo suffices because
1401 // abs(t[i]) is known to be less than *this/2 (see the link above).
1402 return t[i].isNegative() ? t[i] + modulo : t[i];
1405 /// Calculate the magic numbers required to implement a signed integer division
1406 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1407 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1408 /// Warren, Jr., chapter 10.
1409 APInt::ms APInt::magic() const {
1410 const APInt& d = *this;
1412 APInt ad, anc, delta, q1, r1, q2, r2, t;
1413 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1417 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1418 anc = t - 1 - t.urem(ad); // absolute value of nc
1419 p = d.getBitWidth() - 1; // initialize p
1420 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1421 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1422 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1423 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1426 q1 = q1<<1; // update q1 = 2p/abs(nc)
1427 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1428 if (r1.uge(anc)) { // must be unsigned comparison
1432 q2 = q2<<1; // update q2 = 2p/abs(d)
1433 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1434 if (r2.uge(ad)) { // must be unsigned comparison
1439 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1442 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1443 mag.s = p - d.getBitWidth(); // resulting shift
1447 /// Calculate the magic numbers required to implement an unsigned integer
1448 /// division by a constant as a sequence of multiplies, adds and shifts.
1449 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1450 /// S. Warren, Jr., chapter 10.
1451 /// LeadingZeros can be used to simplify the calculation if the upper bits
1452 /// of the divided value are known zero.
1453 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1454 const APInt& d = *this;
1456 APInt nc, delta, q1, r1, q2, r2;
1458 magu.a = 0; // initialize "add" indicator
1459 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1460 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1461 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1463 nc = allOnes - (allOnes - d).urem(d);
1464 p = d.getBitWidth() - 1; // initialize p
1465 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1466 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1467 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1468 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1471 if (r1.uge(nc - r1)) {
1472 q1 = q1 + q1 + 1; // update q1
1473 r1 = r1 + r1 - nc; // update r1
1476 q1 = q1+q1; // update q1
1477 r1 = r1+r1; // update r1
1479 if ((r2 + 1).uge(d - r2)) {
1480 if (q2.uge(signedMax)) magu.a = 1;
1481 q2 = q2+q2 + 1; // update q2
1482 r2 = r2+r2 + 1 - d; // update r2
1485 if (q2.uge(signedMin)) magu.a = 1;
1486 q2 = q2+q2; // update q2
1487 r2 = r2+r2 + 1; // update r2
1490 } while (p < d.getBitWidth()*2 &&
1491 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1492 magu.m = q2 + 1; // resulting magic number
1493 magu.s = p - d.getBitWidth(); // resulting shift
1497 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1498 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1499 /// variables here have the same names as in the algorithm. Comments explain
1500 /// the algorithm and any deviation from it.
1501 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1502 unsigned m, unsigned n) {
1503 assert(u && "Must provide dividend");
1504 assert(v && "Must provide divisor");
1505 assert(q && "Must provide quotient");
1506 assert(u != v && u != q && v != q && "Must us different memory");
1507 assert(n>1 && "n must be > 1");
1509 // Knuth uses the value b as the base of the number system. In our case b
1510 // is 2^31 so we just set it to -1u.
1511 uint64_t b = uint64_t(1) << 32;
1514 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1515 DEBUG(dbgs() << "KnuthDiv: original:");
1516 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1517 DEBUG(dbgs() << " by");
1518 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1519 DEBUG(dbgs() << '\n');
1521 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1522 // u and v by d. Note that we have taken Knuth's advice here to use a power
1523 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1524 // 2 allows us to shift instead of multiply and it is easy to determine the
1525 // shift amount from the leading zeros. We are basically normalizing the u
1526 // and v so that its high bits are shifted to the top of v's range without
1527 // overflow. Note that this can require an extra word in u so that u must
1528 // be of length m+n+1.
1529 unsigned shift = countLeadingZeros(v[n-1]);
1530 unsigned v_carry = 0;
1531 unsigned u_carry = 0;
1533 for (unsigned i = 0; i < m+n; ++i) {
1534 unsigned u_tmp = u[i] >> (32 - shift);
1535 u[i] = (u[i] << shift) | u_carry;
1538 for (unsigned i = 0; i < n; ++i) {
1539 unsigned v_tmp = v[i] >> (32 - shift);
1540 v[i] = (v[i] << shift) | v_carry;
1546 DEBUG(dbgs() << "KnuthDiv: normal:");
1547 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1548 DEBUG(dbgs() << " by");
1549 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1550 DEBUG(dbgs() << '\n');
1553 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1556 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1557 // D3. [Calculate q'.].
1558 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1559 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1560 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1561 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1562 // on v[n-2] determines at high speed most of the cases in which the trial
1563 // value qp is one too large, and it eliminates all cases where qp is two
1565 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1566 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1567 uint64_t qp = dividend / v[n-1];
1568 uint64_t rp = dividend % v[n-1];
1569 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1572 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1575 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1577 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1578 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1579 // consists of a simple multiplication by a one-place number, combined with
1582 for (unsigned i = 0; i < n; ++i) {
1583 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1584 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1585 bool borrow = subtrahend > u_tmp;
1586 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1587 << ", subtrahend == " << subtrahend
1588 << ", borrow = " << borrow << '\n');
1590 uint64_t result = u_tmp - subtrahend;
1592 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1593 u[k++] = (unsigned)(result >> 32); // subtract high word
1594 while (borrow && k <= m+n) { // deal with borrow to the left
1600 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1603 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1604 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1605 DEBUG(dbgs() << '\n');
1606 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1607 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1608 // true value plus b**(n+1), namely as the b's complement of
1609 // the true value, and a "borrow" to the left should be remembered.
1612 bool carry = true; // true because b's complement is "complement + 1"
1613 for (unsigned i = 0; i <= m+n; ++i) {
1614 u[i] = ~u[i] + carry; // b's complement
1615 carry = carry && u[i] == 0;
1618 DEBUG(dbgs() << "KnuthDiv: after complement:");
1619 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1620 DEBUG(dbgs() << '\n');
1622 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1623 // negative, go to step D6; otherwise go on to step D7.
1624 q[j] = (unsigned)qp;
1626 // D6. [Add back]. The probability that this step is necessary is very
1627 // small, on the order of only 2/b. Make sure that test data accounts for
1628 // this possibility. Decrease q[j] by 1
1630 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1631 // A carry will occur to the left of u[j+n], and it should be ignored
1632 // since it cancels with the borrow that occurred in D4.
1634 for (unsigned i = 0; i < n; i++) {
1635 unsigned limit = std::min(u[j+i],v[i]);
1636 u[j+i] += v[i] + carry;
1637 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1641 DEBUG(dbgs() << "KnuthDiv: after correction:");
1642 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1643 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1645 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1648 DEBUG(dbgs() << "KnuthDiv: quotient:");
1649 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1650 DEBUG(dbgs() << '\n');
1652 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1653 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1654 // compute the remainder (urem uses this).
1656 // The value d is expressed by the "shift" value above since we avoided
1657 // multiplication by d by using a shift left. So, all we have to do is
1658 // shift right here. In order to mak
1661 DEBUG(dbgs() << "KnuthDiv: remainder:");
1662 for (int i = n-1; i >= 0; i--) {
1663 r[i] = (u[i] >> shift) | carry;
1664 carry = u[i] << (32 - shift);
1665 DEBUG(dbgs() << " " << r[i]);
1668 for (int i = n-1; i >= 0; i--) {
1670 DEBUG(dbgs() << " " << r[i]);
1673 DEBUG(dbgs() << '\n');
1676 DEBUG(dbgs() << '\n');
1680 void APInt::divide(const APInt LHS, unsigned lhsWords,
1681 const APInt &RHS, unsigned rhsWords,
1682 APInt *Quotient, APInt *Remainder)
1684 assert(lhsWords >= rhsWords && "Fractional result");
1686 // First, compose the values into an array of 32-bit words instead of
1687 // 64-bit words. This is a necessity of both the "short division" algorithm
1688 // and the Knuth "classical algorithm" which requires there to be native
1689 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1690 // can't use 64-bit operands here because we don't have native results of
1691 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1692 // work on large-endian machines.
1693 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1694 unsigned n = rhsWords * 2;
1695 unsigned m = (lhsWords * 2) - n;
1697 // Allocate space for the temporary values we need either on the stack, if
1698 // it will fit, or on the heap if it won't.
1699 unsigned SPACE[128];
1700 unsigned *U = nullptr;
1701 unsigned *V = nullptr;
1702 unsigned *Q = nullptr;
1703 unsigned *R = nullptr;
1704 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1707 Q = &SPACE[(m+n+1) + n];
1709 R = &SPACE[(m+n+1) + n + (m+n)];
1711 U = new unsigned[m + n + 1];
1712 V = new unsigned[n];
1713 Q = new unsigned[m+n];
1715 R = new unsigned[n];
1718 // Initialize the dividend
1719 memset(U, 0, (m+n+1)*sizeof(unsigned));
1720 for (unsigned i = 0; i < lhsWords; ++i) {
1721 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1722 U[i * 2] = (unsigned)(tmp & mask);
1723 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1725 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1727 // Initialize the divisor
1728 memset(V, 0, (n)*sizeof(unsigned));
1729 for (unsigned i = 0; i < rhsWords; ++i) {
1730 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1731 V[i * 2] = (unsigned)(tmp & mask);
1732 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1735 // initialize the quotient and remainder
1736 memset(Q, 0, (m+n) * sizeof(unsigned));
1738 memset(R, 0, n * sizeof(unsigned));
1740 // Now, adjust m and n for the Knuth division. n is the number of words in
1741 // the divisor. m is the number of words by which the dividend exceeds the
1742 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1743 // contain any zero words or the Knuth algorithm fails.
1744 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1748 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1751 // If we're left with only a single word for the divisor, Knuth doesn't work
1752 // so we implement the short division algorithm here. This is much simpler
1753 // and faster because we are certain that we can divide a 64-bit quantity
1754 // by a 32-bit quantity at hardware speed and short division is simply a
1755 // series of such operations. This is just like doing short division but we
1756 // are using base 2^32 instead of base 10.
1757 assert(n != 0 && "Divide by zero?");
1759 unsigned divisor = V[0];
1760 unsigned remainder = 0;
1761 for (int i = m+n-1; i >= 0; i--) {
1762 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1763 if (partial_dividend == 0) {
1766 } else if (partial_dividend < divisor) {
1768 remainder = (unsigned)partial_dividend;
1769 } else if (partial_dividend == divisor) {
1773 Q[i] = (unsigned)(partial_dividend / divisor);
1774 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1780 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1782 KnuthDiv(U, V, Q, R, m, n);
1785 // If the caller wants the quotient
1787 // Set up the Quotient value's memory.
1788 if (Quotient->BitWidth != LHS.BitWidth) {
1789 if (Quotient->isSingleWord())
1792 delete [] Quotient->pVal;
1793 Quotient->BitWidth = LHS.BitWidth;
1794 if (!Quotient->isSingleWord())
1795 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1797 Quotient->clearAllBits();
1799 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1801 if (lhsWords == 1) {
1803 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1804 if (Quotient->isSingleWord())
1805 Quotient->VAL = tmp;
1807 Quotient->pVal[0] = tmp;
1809 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1810 for (unsigned i = 0; i < lhsWords; ++i)
1812 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1816 // If the caller wants the remainder
1818 // Set up the Remainder value's memory.
1819 if (Remainder->BitWidth != RHS.BitWidth) {
1820 if (Remainder->isSingleWord())
1823 delete [] Remainder->pVal;
1824 Remainder->BitWidth = RHS.BitWidth;
1825 if (!Remainder->isSingleWord())
1826 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1828 Remainder->clearAllBits();
1830 // The remainder is in R. Reconstitute the remainder into Remainder's low
1832 if (rhsWords == 1) {
1834 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1835 if (Remainder->isSingleWord())
1836 Remainder->VAL = tmp;
1838 Remainder->pVal[0] = tmp;
1840 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1841 for (unsigned i = 0; i < rhsWords; ++i)
1842 Remainder->pVal[i] =
1843 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1847 // Clean up the memory we allocated.
1848 if (U != &SPACE[0]) {
1856 APInt APInt::udiv(const APInt& RHS) const {
1857 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1859 // First, deal with the easy case
1860 if (isSingleWord()) {
1861 assert(RHS.VAL != 0 && "Divide by zero?");
1862 return APInt(BitWidth, VAL / RHS.VAL);
1865 // Get some facts about the LHS and RHS number of bits and words
1866 unsigned rhsBits = RHS.getActiveBits();
1867 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1868 assert(rhsWords && "Divided by zero???");
1869 unsigned lhsBits = this->getActiveBits();
1870 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1872 // Deal with some degenerate cases
1875 return APInt(BitWidth, 0);
1876 else if (lhsWords < rhsWords || this->ult(RHS)) {
1877 // X / Y ===> 0, iff X < Y
1878 return APInt(BitWidth, 0);
1879 } else if (*this == RHS) {
1881 return APInt(BitWidth, 1);
1882 } else if (lhsWords == 1 && rhsWords == 1) {
1883 // All high words are zero, just use native divide
1884 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1887 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1888 APInt Quotient(1,0); // to hold result.
1889 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
1893 APInt APInt::sdiv(const APInt &RHS) const {
1895 if (RHS.isNegative())
1896 return (-(*this)).udiv(-RHS);
1897 return -((-(*this)).udiv(RHS));
1899 if (RHS.isNegative())
1900 return -(this->udiv(-RHS));
1901 return this->udiv(RHS);
1904 APInt APInt::urem(const APInt& RHS) const {
1905 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1906 if (isSingleWord()) {
1907 assert(RHS.VAL != 0 && "Remainder by zero?");
1908 return APInt(BitWidth, VAL % RHS.VAL);
1911 // Get some facts about the LHS
1912 unsigned lhsBits = getActiveBits();
1913 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1915 // Get some facts about the RHS
1916 unsigned rhsBits = RHS.getActiveBits();
1917 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1918 assert(rhsWords && "Performing remainder operation by zero ???");
1920 // Check the degenerate cases
1921 if (lhsWords == 0) {
1923 return APInt(BitWidth, 0);
1924 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1925 // X % Y ===> X, iff X < Y
1927 } else if (*this == RHS) {
1929 return APInt(BitWidth, 0);
1930 } else if (lhsWords == 1) {
1931 // All high words are zero, just use native remainder
1932 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1935 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1936 APInt Remainder(1,0);
1937 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
1941 APInt APInt::srem(const APInt &RHS) const {
1943 if (RHS.isNegative())
1944 return -((-(*this)).urem(-RHS));
1945 return -((-(*this)).urem(RHS));
1947 if (RHS.isNegative())
1948 return this->urem(-RHS);
1949 return this->urem(RHS);
1952 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1953 APInt &Quotient, APInt &Remainder) {
1954 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1956 // First, deal with the easy case
1957 if (LHS.isSingleWord()) {
1958 assert(RHS.VAL != 0 && "Divide by zero?");
1959 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1960 uint64_t RemVal = LHS.VAL % RHS.VAL;
1961 Quotient = APInt(LHS.BitWidth, QuotVal);
1962 Remainder = APInt(LHS.BitWidth, RemVal);
1966 // Get some size facts about the dividend and divisor
1967 unsigned lhsBits = LHS.getActiveBits();
1968 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1969 unsigned rhsBits = RHS.getActiveBits();
1970 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1972 // Check the degenerate cases
1973 if (lhsWords == 0) {
1974 Quotient = 0; // 0 / Y ===> 0
1975 Remainder = 0; // 0 % Y ===> 0
1979 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1980 Remainder = LHS; // X % Y ===> X, iff X < Y
1981 Quotient = 0; // X / Y ===> 0, iff X < Y
1986 Quotient = 1; // X / X ===> 1
1987 Remainder = 0; // X % X ===> 0;
1991 if (lhsWords == 1 && rhsWords == 1) {
1992 // There is only one word to consider so use the native versions.
1993 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1994 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1995 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1996 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2000 // Okay, lets do it the long way
2001 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2004 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
2005 APInt &Quotient, APInt &Remainder) {
2006 if (LHS.isNegative()) {
2007 if (RHS.isNegative())
2008 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
2010 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
2011 Quotient = -Quotient;
2013 Remainder = -Remainder;
2014 } else if (RHS.isNegative()) {
2015 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
2016 Quotient = -Quotient;
2018 APInt::udivrem(LHS, RHS, Quotient, Remainder);
2022 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2023 APInt Res = *this+RHS;
2024 Overflow = isNonNegative() == RHS.isNonNegative() &&
2025 Res.isNonNegative() != isNonNegative();
2029 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2030 APInt Res = *this+RHS;
2031 Overflow = Res.ult(RHS);
2035 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2036 APInt Res = *this - RHS;
2037 Overflow = isNonNegative() != RHS.isNonNegative() &&
2038 Res.isNonNegative() != isNonNegative();
2042 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2043 APInt Res = *this-RHS;
2044 Overflow = Res.ugt(*this);
2048 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2049 // MININT/-1 --> overflow.
2050 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2054 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2055 APInt Res = *this * RHS;
2057 if (*this != 0 && RHS != 0)
2058 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2064 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2065 APInt Res = *this * RHS;
2067 if (*this != 0 && RHS != 0)
2068 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2074 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
2075 Overflow = ShAmt.uge(getBitWidth());
2077 return APInt(BitWidth, 0);
2079 if (isNonNegative()) // Don't allow sign change.
2080 Overflow = ShAmt.uge(countLeadingZeros());
2082 Overflow = ShAmt.uge(countLeadingOnes());
2084 return *this << ShAmt;
2087 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
2088 Overflow = ShAmt.uge(getBitWidth());
2090 return APInt(BitWidth, 0);
2092 Overflow = ShAmt.ugt(countLeadingZeros());
2094 return *this << ShAmt;
2100 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2101 // Check our assumptions here
2102 assert(!str.empty() && "Invalid string length");
2103 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2105 "Radix should be 2, 8, 10, 16, or 36!");
2107 StringRef::iterator p = str.begin();
2108 size_t slen = str.size();
2109 bool isNeg = *p == '-';
2110 if (*p == '-' || *p == '+') {
2113 assert(slen && "String is only a sign, needs a value.");
2115 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2116 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2117 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2118 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2119 "Insufficient bit width");
2122 if (!isSingleWord())
2123 pVal = getClearedMemory(getNumWords());
2125 // Figure out if we can shift instead of multiply
2126 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2128 // Set up an APInt for the digit to add outside the loop so we don't
2129 // constantly construct/destruct it.
2130 APInt apdigit(getBitWidth(), 0);
2131 APInt apradix(getBitWidth(), radix);
2133 // Enter digit traversal loop
2134 for (StringRef::iterator e = str.end(); p != e; ++p) {
2135 unsigned digit = getDigit(*p, radix);
2136 assert(digit < radix && "Invalid character in digit string");
2138 // Shift or multiply the value by the radix
2146 // Add in the digit we just interpreted
2147 if (apdigit.isSingleWord())
2148 apdigit.VAL = digit;
2150 apdigit.pVal[0] = digit;
2153 // If its negative, put it in two's complement form
2156 this->flipAllBits();
2160 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2161 bool Signed, bool formatAsCLiteral) const {
2162 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2164 "Radix should be 2, 8, 10, 16, or 36!");
2166 const char *Prefix = "";
2167 if (formatAsCLiteral) {
2170 // Binary literals are a non-standard extension added in gcc 4.3:
2171 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2183 llvm_unreachable("Invalid radix!");
2187 // First, check for a zero value and just short circuit the logic below.
2190 Str.push_back(*Prefix);
2197 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2199 if (isSingleWord()) {
2201 char *BufPtr = Buffer+65;
2207 int64_t I = getSExtValue();
2217 Str.push_back(*Prefix);
2222 *--BufPtr = Digits[N % Radix];
2225 Str.append(BufPtr, Buffer+65);
2231 if (Signed && isNegative()) {
2232 // They want to print the signed version and it is a negative value
2233 // Flip the bits and add one to turn it into the equivalent positive
2234 // value and put a '-' in the result.
2241 Str.push_back(*Prefix);
2245 // We insert the digits backward, then reverse them to get the right order.
2246 unsigned StartDig = Str.size();
2248 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2249 // because the number of bits per digit (1, 3 and 4 respectively) divides
2250 // equaly. We just shift until the value is zero.
2251 if (Radix == 2 || Radix == 8 || Radix == 16) {
2252 // Just shift tmp right for each digit width until it becomes zero
2253 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2254 unsigned MaskAmt = Radix - 1;
2257 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2258 Str.push_back(Digits[Digit]);
2259 Tmp = Tmp.lshr(ShiftAmt);
2262 APInt divisor(Radix == 10? 4 : 8, Radix);
2264 APInt APdigit(1, 0);
2265 APInt tmp2(Tmp.getBitWidth(), 0);
2266 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2268 unsigned Digit = (unsigned)APdigit.getZExtValue();
2269 assert(Digit < Radix && "divide failed");
2270 Str.push_back(Digits[Digit]);
2275 // Reverse the digits before returning.
2276 std::reverse(Str.begin()+StartDig, Str.end());
2279 /// toString - This returns the APInt as a std::string. Note that this is an
2280 /// inefficient method. It is better to pass in a SmallVector/SmallString
2281 /// to the methods above.
2282 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2284 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2289 void APInt::dump() const {
2290 SmallString<40> S, U;
2291 this->toStringUnsigned(U);
2292 this->toStringSigned(S);
2293 dbgs() << "APInt(" << BitWidth << "b, "
2294 << U << "u " << S << "s)";
2297 void APInt::print(raw_ostream &OS, bool isSigned) const {
2299 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2303 // This implements a variety of operations on a representation of
2304 // arbitrary precision, two's-complement, bignum integer values.
2306 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2307 // and unrestricting assumption.
2308 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
2310 /* Some handy functions local to this file. */
2313 /* Returns the integer part with the least significant BITS set.
2314 BITS cannot be zero. */
2315 static inline integerPart
2316 lowBitMask(unsigned int bits)
2318 assert(bits != 0 && bits <= integerPartWidth);
2320 return ~(integerPart) 0 >> (integerPartWidth - bits);
2323 /* Returns the value of the lower half of PART. */
2324 static inline integerPart
2325 lowHalf(integerPart part)
2327 return part & lowBitMask(integerPartWidth / 2);
2330 /* Returns the value of the upper half of PART. */
2331 static inline integerPart
2332 highHalf(integerPart part)
2334 return part >> (integerPartWidth / 2);
2337 /* Returns the bit number of the most significant set bit of a part.
2338 If the input number has no bits set -1U is returned. */
2340 partMSB(integerPart value)
2342 return findLastSet(value, ZB_Max);
2345 /* Returns the bit number of the least significant set bit of a
2346 part. If the input number has no bits set -1U is returned. */
2348 partLSB(integerPart value)
2350 return findFirstSet(value, ZB_Max);
2354 /* Sets the least significant part of a bignum to the input value, and
2355 zeroes out higher parts. */
2357 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2364 for (i = 1; i < parts; i++)
2368 /* Assign one bignum to another. */
2370 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2374 for (i = 0; i < parts; i++)
2378 /* Returns true if a bignum is zero, false otherwise. */
2380 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2384 for (i = 0; i < parts; i++)
2391 /* Extract the given bit of a bignum; returns 0 or 1. */
2393 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2395 return (parts[bit / integerPartWidth] &
2396 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2399 /* Set the given bit of a bignum. */
2401 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2403 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2406 /* Clears the given bit of a bignum. */
2408 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2410 parts[bit / integerPartWidth] &=
2411 ~((integerPart) 1 << (bit % integerPartWidth));
2414 /* Returns the bit number of the least significant set bit of a
2415 number. If the input number has no bits set -1U is returned. */
2417 APInt::tcLSB(const integerPart *parts, unsigned int n)
2419 unsigned int i, lsb;
2421 for (i = 0; i < n; i++) {
2422 if (parts[i] != 0) {
2423 lsb = partLSB(parts[i]);
2425 return lsb + i * integerPartWidth;
2432 /* Returns the bit number of the most significant set bit of a number.
2433 If the input number has no bits set -1U is returned. */
2435 APInt::tcMSB(const integerPart *parts, unsigned int n)
2442 if (parts[n] != 0) {
2443 msb = partMSB(parts[n]);
2445 return msb + n * integerPartWidth;
2452 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2453 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2454 the least significant bit of DST. All high bits above srcBITS in
2455 DST are zero-filled. */
2457 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2458 unsigned int srcBits, unsigned int srcLSB)
2460 unsigned int firstSrcPart, dstParts, shift, n;
2462 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2463 assert(dstParts <= dstCount);
2465 firstSrcPart = srcLSB / integerPartWidth;
2466 tcAssign (dst, src + firstSrcPart, dstParts);
2468 shift = srcLSB % integerPartWidth;
2469 tcShiftRight (dst, dstParts, shift);
2471 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2472 in DST. If this is less that srcBits, append the rest, else
2473 clear the high bits. */
2474 n = dstParts * integerPartWidth - shift;
2476 integerPart mask = lowBitMask (srcBits - n);
2477 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2478 << n % integerPartWidth);
2479 } else if (n > srcBits) {
2480 if (srcBits % integerPartWidth)
2481 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2484 /* Clear high parts. */
2485 while (dstParts < dstCount)
2486 dst[dstParts++] = 0;
2489 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2491 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2492 integerPart c, unsigned int parts)
2498 for (i = 0; i < parts; i++) {
2503 dst[i] += rhs[i] + 1;
2514 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2516 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2517 integerPart c, unsigned int parts)
2523 for (i = 0; i < parts; i++) {
2528 dst[i] -= rhs[i] + 1;
2539 /* Negate a bignum in-place. */
2541 APInt::tcNegate(integerPart *dst, unsigned int parts)
2543 tcComplement(dst, parts);
2544 tcIncrement(dst, parts);
2547 /* DST += SRC * MULTIPLIER + CARRY if add is true
2548 DST = SRC * MULTIPLIER + CARRY if add is false
2550 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2551 they must start at the same point, i.e. DST == SRC.
2553 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2554 returned. Otherwise DST is filled with the least significant
2555 DSTPARTS parts of the result, and if all of the omitted higher
2556 parts were zero return zero, otherwise overflow occurred and
2559 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2560 integerPart multiplier, integerPart carry,
2561 unsigned int srcParts, unsigned int dstParts,
2566 /* Otherwise our writes of DST kill our later reads of SRC. */
2567 assert(dst <= src || dst >= src + srcParts);
2568 assert(dstParts <= srcParts + 1);
2570 /* N loops; minimum of dstParts and srcParts. */
2571 n = dstParts < srcParts ? dstParts: srcParts;
2573 for (i = 0; i < n; i++) {
2574 integerPart low, mid, high, srcPart;
2576 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2578 This cannot overflow, because
2580 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2582 which is less than n^2. */
2586 if (multiplier == 0 || srcPart == 0) {
2590 low = lowHalf(srcPart) * lowHalf(multiplier);
2591 high = highHalf(srcPart) * highHalf(multiplier);
2593 mid = lowHalf(srcPart) * highHalf(multiplier);
2594 high += highHalf(mid);
2595 mid <<= integerPartWidth / 2;
2596 if (low + mid < low)
2600 mid = highHalf(srcPart) * lowHalf(multiplier);
2601 high += highHalf(mid);
2602 mid <<= integerPartWidth / 2;
2603 if (low + mid < low)
2607 /* Now add carry. */
2608 if (low + carry < low)
2614 /* And now DST[i], and store the new low part there. */
2615 if (low + dst[i] < low)
2625 /* Full multiplication, there is no overflow. */
2626 assert(i + 1 == dstParts);
2630 /* We overflowed if there is carry. */
2634 /* We would overflow if any significant unwritten parts would be
2635 non-zero. This is true if any remaining src parts are non-zero
2636 and the multiplier is non-zero. */
2638 for (; i < srcParts; i++)
2642 /* We fitted in the narrow destination. */
2647 /* DST = LHS * RHS, where DST has the same width as the operands and
2648 is filled with the least significant parts of the result. Returns
2649 one if overflow occurred, otherwise zero. DST must be disjoint
2650 from both operands. */
2652 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2653 const integerPart *rhs, unsigned int parts)
2658 assert(dst != lhs && dst != rhs);
2661 tcSet(dst, 0, parts);
2663 for (i = 0; i < parts; i++)
2664 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2670 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2671 operands. No overflow occurs. DST must be disjoint from both
2672 operands. Returns the number of parts required to hold the
2675 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2676 const integerPart *rhs, unsigned int lhsParts,
2677 unsigned int rhsParts)
2679 /* Put the narrower number on the LHS for less loops below. */
2680 if (lhsParts > rhsParts) {
2681 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2685 assert(dst != lhs && dst != rhs);
2687 tcSet(dst, 0, rhsParts);
2689 for (n = 0; n < lhsParts; n++)
2690 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2692 n = lhsParts + rhsParts;
2694 return n - (dst[n - 1] == 0);
2698 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2699 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2700 set REMAINDER to the remainder, return zero. i.e.
2702 OLD_LHS = RHS * LHS + REMAINDER
2704 SCRATCH is a bignum of the same size as the operands and result for
2705 use by the routine; its contents need not be initialized and are
2706 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2709 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2710 integerPart *remainder, integerPart *srhs,
2713 unsigned int n, shiftCount;
2716 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2718 shiftCount = tcMSB(rhs, parts) + 1;
2719 if (shiftCount == 0)
2722 shiftCount = parts * integerPartWidth - shiftCount;
2723 n = shiftCount / integerPartWidth;
2724 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2726 tcAssign(srhs, rhs, parts);
2727 tcShiftLeft(srhs, parts, shiftCount);
2728 tcAssign(remainder, lhs, parts);
2729 tcSet(lhs, 0, parts);
2731 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2736 compare = tcCompare(remainder, srhs, parts);
2738 tcSubtract(remainder, srhs, 0, parts);
2742 if (shiftCount == 0)
2745 tcShiftRight(srhs, parts, 1);
2746 if ((mask >>= 1) == 0)
2747 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2753 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2754 There are no restrictions on COUNT. */
2756 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2759 unsigned int jump, shift;
2761 /* Jump is the inter-part jump; shift is is intra-part shift. */
2762 jump = count / integerPartWidth;
2763 shift = count % integerPartWidth;
2765 while (parts > jump) {
2770 /* dst[i] comes from the two parts src[i - jump] and, if we have
2771 an intra-part shift, src[i - jump - 1]. */
2772 part = dst[parts - jump];
2775 if (parts >= jump + 1)
2776 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2787 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2788 zero. There are no restrictions on COUNT. */
2790 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2793 unsigned int i, jump, shift;
2795 /* Jump is the inter-part jump; shift is is intra-part shift. */
2796 jump = count / integerPartWidth;
2797 shift = count % integerPartWidth;
2799 /* Perform the shift. This leaves the most significant COUNT bits
2800 of the result at zero. */
2801 for (i = 0; i < parts; i++) {
2804 if (i + jump >= parts) {
2807 part = dst[i + jump];
2810 if (i + jump + 1 < parts)
2811 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2820 /* Bitwise and of two bignums. */
2822 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2826 for (i = 0; i < parts; i++)
2830 /* Bitwise inclusive or of two bignums. */
2832 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2836 for (i = 0; i < parts; i++)
2840 /* Bitwise exclusive or of two bignums. */
2842 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2846 for (i = 0; i < parts; i++)
2850 /* Complement a bignum in-place. */
2852 APInt::tcComplement(integerPart *dst, unsigned int parts)
2856 for (i = 0; i < parts; i++)
2860 /* Comparison (unsigned) of two bignums. */
2862 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2867 if (lhs[parts] == rhs[parts])
2870 if (lhs[parts] > rhs[parts])
2879 /* Increment a bignum in-place, return the carry flag. */
2881 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2885 for (i = 0; i < parts; i++)
2892 /* Decrement a bignum in-place, return the borrow flag. */
2894 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2895 for (unsigned int i = 0; i < parts; i++) {
2896 // If the current word is non-zero, then the decrement has no effect on the
2897 // higher-order words of the integer and no borrow can occur. Exit early.
2901 // If every word was zero, then there is a borrow.
2906 /* Set the least significant BITS bits of a bignum, clear the
2909 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2915 while (bits > integerPartWidth) {
2916 dst[i++] = ~(integerPart) 0;
2917 bits -= integerPartWidth;
2921 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);