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 bool APInt::isSplat(unsigned SplatSizeInBits) const {
676 assert(getBitWidth() % SplatSizeInBits == 0 &&
677 "SplatSizeInBits must divide width!");
678 // We can check that all parts of an integer are equal by making use of a
679 // little trick: rotate and check if it's still the same value.
680 return *this == rotl(SplatSizeInBits);
683 /// HiBits - This function returns the high "numBits" bits of this APInt.
684 APInt APInt::getHiBits(unsigned numBits) const {
685 return APIntOps::lshr(*this, BitWidth - numBits);
688 /// LoBits - This function returns the low "numBits" bits of this APInt.
689 APInt APInt::getLoBits(unsigned numBits) const {
690 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
694 unsigned APInt::countLeadingZerosSlowCase() const {
695 // Treat the most significand word differently because it might have
696 // meaningless bits set beyond the precision.
697 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
699 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
701 MSWMask = ~integerPart(0);
702 BitsInMSW = APINT_BITS_PER_WORD;
705 unsigned i = getNumWords();
706 integerPart MSW = pVal[i-1] & MSWMask;
708 return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
710 unsigned Count = BitsInMSW;
711 for (--i; i > 0u; --i) {
713 Count += APINT_BITS_PER_WORD;
715 Count += llvm::countLeadingZeros(pVal[i-1]);
722 unsigned APInt::countLeadingOnes() const {
724 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
726 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
729 highWordBits = APINT_BITS_PER_WORD;
732 shift = APINT_BITS_PER_WORD - highWordBits;
734 int i = getNumWords() - 1;
735 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
736 if (Count == highWordBits) {
737 for (i--; i >= 0; --i) {
738 if (pVal[i] == -1ULL)
739 Count += APINT_BITS_PER_WORD;
741 Count += llvm::countLeadingOnes(pVal[i]);
749 unsigned APInt::countTrailingZeros() const {
751 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
754 for (; i < getNumWords() && pVal[i] == 0; ++i)
755 Count += APINT_BITS_PER_WORD;
756 if (i < getNumWords())
757 Count += llvm::countTrailingZeros(pVal[i]);
758 return std::min(Count, BitWidth);
761 unsigned APInt::countTrailingOnesSlowCase() const {
764 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
765 Count += APINT_BITS_PER_WORD;
766 if (i < getNumWords())
767 Count += llvm::countTrailingOnes(pVal[i]);
768 return std::min(Count, BitWidth);
771 unsigned APInt::countPopulationSlowCase() const {
773 for (unsigned i = 0; i < getNumWords(); ++i)
774 Count += llvm::countPopulation(pVal[i]);
778 /// Perform a logical right-shift from Src to Dst, which must be equal or
779 /// non-overlapping, of Words words, by Shift, which must be less than 64.
780 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
783 for (int I = Words - 1; I >= 0; --I) {
784 uint64_t Tmp = Src[I];
785 Dst[I] = (Tmp >> Shift) | Carry;
786 Carry = Tmp << (64 - Shift);
790 APInt APInt::byteSwap() const {
791 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
793 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
795 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
796 if (BitWidth == 48) {
797 unsigned Tmp1 = unsigned(VAL >> 16);
798 Tmp1 = ByteSwap_32(Tmp1);
799 uint16_t Tmp2 = uint16_t(VAL);
800 Tmp2 = ByteSwap_16(Tmp2);
801 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
804 return APInt(BitWidth, ByteSwap_64(VAL));
806 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
807 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
808 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
809 if (Result.BitWidth != BitWidth) {
810 lshrNear(Result.pVal, Result.pVal, getNumWords(),
811 Result.BitWidth - BitWidth);
812 Result.BitWidth = BitWidth;
817 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
819 APInt A = API1, B = API2;
822 B = APIntOps::urem(A, B);
828 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
835 // Get the sign bit from the highest order bit
836 bool isNeg = T.I >> 63;
838 // Get the 11-bit exponent and adjust for the 1023 bit bias
839 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
841 // If the exponent is negative, the value is < 0 so just return 0.
843 return APInt(width, 0u);
845 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
846 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
848 // If the exponent doesn't shift all bits out of the mantissa
850 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
851 APInt(width, mantissa >> (52 - exp));
853 // If the client didn't provide enough bits for us to shift the mantissa into
854 // then the result is undefined, just return 0
855 if (width <= exp - 52)
856 return APInt(width, 0);
858 // Otherwise, we have to shift the mantissa bits up to the right location
859 APInt Tmp(width, mantissa);
860 Tmp = Tmp.shl((unsigned)exp - 52);
861 return isNeg ? -Tmp : Tmp;
864 /// RoundToDouble - This function converts this APInt to a double.
865 /// The layout for double is as following (IEEE Standard 754):
866 /// --------------------------------------
867 /// | Sign Exponent Fraction Bias |
868 /// |-------------------------------------- |
869 /// | 1[63] 11[62-52] 52[51-00] 1023 |
870 /// --------------------------------------
871 double APInt::roundToDouble(bool isSigned) const {
873 // Handle the simple case where the value is contained in one uint64_t.
874 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
875 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
877 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
880 return double(getWord(0));
883 // Determine if the value is negative.
884 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
886 // Construct the absolute value if we're negative.
887 APInt Tmp(isNeg ? -(*this) : (*this));
889 // Figure out how many bits we're using.
890 unsigned n = Tmp.getActiveBits();
892 // The exponent (without bias normalization) is just the number of bits
893 // we are using. Note that the sign bit is gone since we constructed the
897 // Return infinity for exponent overflow
899 if (!isSigned || !isNeg)
900 return std::numeric_limits<double>::infinity();
902 return -std::numeric_limits<double>::infinity();
904 exp += 1023; // Increment for 1023 bias
906 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
907 // extract the high 52 bits from the correct words in pVal.
909 unsigned hiWord = whichWord(n-1);
911 mantissa = Tmp.pVal[0];
913 mantissa >>= n - 52; // shift down, we want the top 52 bits.
915 assert(hiWord > 0 && "huh?");
916 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
917 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
918 mantissa = hibits | lobits;
921 // The leading bit of mantissa is implicit, so get rid of it.
922 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
927 T.I = sign | (exp << 52) | mantissa;
931 // Truncate to new width.
932 APInt APInt::trunc(unsigned width) const {
933 assert(width < BitWidth && "Invalid APInt Truncate request");
934 assert(width && "Can't truncate to 0 bits");
936 if (width <= APINT_BITS_PER_WORD)
937 return APInt(width, getRawData()[0]);
939 APInt Result(getMemory(getNumWords(width)), width);
943 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
944 Result.pVal[i] = pVal[i];
946 // Truncate and copy any partial word.
947 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
949 Result.pVal[i] = pVal[i] << bits >> bits;
954 // Sign extend to a new width.
955 APInt APInt::sext(unsigned width) const {
956 assert(width > BitWidth && "Invalid APInt SignExtend request");
958 if (width <= APINT_BITS_PER_WORD) {
959 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
960 val = (int64_t)val >> (width - BitWidth);
961 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
964 APInt Result(getMemory(getNumWords(width)), width);
969 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
970 word = getRawData()[i];
971 Result.pVal[i] = word;
974 // Read and sign-extend any partial word.
975 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
977 word = (int64_t)getRawData()[i] << bits >> bits;
979 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
981 // Write remaining full words.
982 for (; i != width / APINT_BITS_PER_WORD; i++) {
983 Result.pVal[i] = word;
984 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
987 // Write any partial word.
988 bits = (0 - width) % APINT_BITS_PER_WORD;
990 Result.pVal[i] = word << bits >> bits;
995 // Zero extend to a new width.
996 APInt APInt::zext(unsigned width) const {
997 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
999 if (width <= APINT_BITS_PER_WORD)
1000 return APInt(width, VAL);
1002 APInt Result(getMemory(getNumWords(width)), width);
1006 for (i = 0; i != getNumWords(); i++)
1007 Result.pVal[i] = getRawData()[i];
1009 // Zero remaining words.
1010 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1015 APInt APInt::zextOrTrunc(unsigned width) const {
1016 if (BitWidth < width)
1018 if (BitWidth > width)
1019 return trunc(width);
1023 APInt APInt::sextOrTrunc(unsigned width) const {
1024 if (BitWidth < width)
1026 if (BitWidth > width)
1027 return trunc(width);
1031 APInt APInt::zextOrSelf(unsigned width) const {
1032 if (BitWidth < width)
1037 APInt APInt::sextOrSelf(unsigned width) const {
1038 if (BitWidth < width)
1043 /// Arithmetic right-shift this APInt by shiftAmt.
1044 /// @brief Arithmetic right-shift function.
1045 APInt APInt::ashr(const APInt &shiftAmt) const {
1046 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1049 /// Arithmetic right-shift this APInt by shiftAmt.
1050 /// @brief Arithmetic right-shift function.
1051 APInt APInt::ashr(unsigned shiftAmt) const {
1052 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1053 // Handle a degenerate case
1057 // Handle single word shifts with built-in ashr
1058 if (isSingleWord()) {
1059 if (shiftAmt == BitWidth)
1060 return APInt(BitWidth, 0); // undefined
1062 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1063 return APInt(BitWidth,
1064 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1068 // If all the bits were shifted out, the result is, technically, undefined.
1069 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1070 // issues in the algorithm below.
1071 if (shiftAmt == BitWidth) {
1073 return APInt(BitWidth, -1ULL, true);
1075 return APInt(BitWidth, 0);
1078 // Create some space for the result.
1079 uint64_t * val = new uint64_t[getNumWords()];
1081 // Compute some values needed by the following shift algorithms
1082 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1083 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1084 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1085 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1086 if (bitsInWord == 0)
1087 bitsInWord = APINT_BITS_PER_WORD;
1089 // If we are shifting whole words, just move whole words
1090 if (wordShift == 0) {
1091 // Move the words containing significant bits
1092 for (unsigned i = 0; i <= breakWord; ++i)
1093 val[i] = pVal[i+offset]; // move whole word
1095 // Adjust the top significant word for sign bit fill, if negative
1097 if (bitsInWord < APINT_BITS_PER_WORD)
1098 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1100 // Shift the low order words
1101 for (unsigned i = 0; i < breakWord; ++i) {
1102 // This combines the shifted corresponding word with the low bits from
1103 // the next word (shifted into this word's high bits).
1104 val[i] = (pVal[i+offset] >> wordShift) |
1105 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1108 // Shift the break word. In this case there are no bits from the next word
1109 // to include in this word.
1110 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1112 // Deal with sign extension in the break word, and possibly the word before
1115 if (wordShift > bitsInWord) {
1118 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1119 val[breakWord] |= ~0ULL;
1121 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1125 // Remaining words are 0 or -1, just assign them.
1126 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1127 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1129 APInt Result(val, BitWidth);
1130 Result.clearUnusedBits();
1134 /// Logical right-shift this APInt by shiftAmt.
1135 /// @brief Logical right-shift function.
1136 APInt APInt::lshr(const APInt &shiftAmt) const {
1137 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1140 /// Logical right-shift this APInt by shiftAmt.
1141 /// @brief Logical right-shift function.
1142 APInt APInt::lshr(unsigned shiftAmt) const {
1143 if (isSingleWord()) {
1144 if (shiftAmt >= BitWidth)
1145 return APInt(BitWidth, 0);
1147 return APInt(BitWidth, this->VAL >> shiftAmt);
1150 // If all the bits were shifted out, the result is 0. This avoids issues
1151 // with shifting by the size of the integer type, which produces undefined
1152 // results. We define these "undefined results" to always be 0.
1153 if (shiftAmt >= BitWidth)
1154 return APInt(BitWidth, 0);
1156 // If none of the bits are shifted out, the result is *this. This avoids
1157 // issues with shifting by the size of the integer type, which produces
1158 // undefined results in the code below. This is also an optimization.
1162 // Create some space for the result.
1163 uint64_t * val = new uint64_t[getNumWords()];
1165 // If we are shifting less than a word, compute the shift with a simple carry
1166 if (shiftAmt < APINT_BITS_PER_WORD) {
1167 lshrNear(val, pVal, getNumWords(), shiftAmt);
1168 APInt Result(val, BitWidth);
1169 Result.clearUnusedBits();
1173 // Compute some values needed by the remaining shift algorithms
1174 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1175 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1177 // If we are shifting whole words, just move whole words
1178 if (wordShift == 0) {
1179 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1180 val[i] = pVal[i+offset];
1181 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1183 APInt Result(val, BitWidth);
1184 Result.clearUnusedBits();
1188 // Shift the low order words
1189 unsigned breakWord = getNumWords() - offset -1;
1190 for (unsigned i = 0; i < breakWord; ++i)
1191 val[i] = (pVal[i+offset] >> wordShift) |
1192 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1193 // Shift the break word.
1194 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1196 // Remaining words are 0
1197 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1199 APInt Result(val, BitWidth);
1200 Result.clearUnusedBits();
1204 /// Left-shift this APInt by shiftAmt.
1205 /// @brief Left-shift function.
1206 APInt APInt::shl(const APInt &shiftAmt) const {
1207 // It's undefined behavior in C to shift by BitWidth or greater.
1208 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1211 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1212 // If all the bits were shifted out, the result is 0. This avoids issues
1213 // with shifting by the size of the integer type, which produces undefined
1214 // results. We define these "undefined results" to always be 0.
1215 if (shiftAmt == BitWidth)
1216 return APInt(BitWidth, 0);
1218 // If none of the bits are shifted out, the result is *this. This avoids a
1219 // lshr by the words size in the loop below which can produce incorrect
1220 // results. It also avoids the expensive computation below for a common case.
1224 // Create some space for the result.
1225 uint64_t * val = new uint64_t[getNumWords()];
1227 // If we are shifting less than a word, do it the easy way
1228 if (shiftAmt < APINT_BITS_PER_WORD) {
1230 for (unsigned i = 0; i < getNumWords(); i++) {
1231 val[i] = pVal[i] << shiftAmt | carry;
1232 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1234 APInt Result(val, BitWidth);
1235 Result.clearUnusedBits();
1239 // Compute some values needed by the remaining shift algorithms
1240 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1241 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1243 // If we are shifting whole words, just move whole words
1244 if (wordShift == 0) {
1245 for (unsigned i = 0; i < offset; i++)
1247 for (unsigned i = offset; i < getNumWords(); i++)
1248 val[i] = pVal[i-offset];
1249 APInt Result(val, BitWidth);
1250 Result.clearUnusedBits();
1254 // Copy whole words from this to Result.
1255 unsigned i = getNumWords() - 1;
1256 for (; i > offset; --i)
1257 val[i] = pVal[i-offset] << wordShift |
1258 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1259 val[offset] = pVal[0] << wordShift;
1260 for (i = 0; i < offset; ++i)
1262 APInt Result(val, BitWidth);
1263 Result.clearUnusedBits();
1267 APInt APInt::rotl(const APInt &rotateAmt) const {
1268 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1271 APInt APInt::rotl(unsigned rotateAmt) const {
1272 rotateAmt %= BitWidth;
1275 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1278 APInt APInt::rotr(const APInt &rotateAmt) const {
1279 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1282 APInt APInt::rotr(unsigned rotateAmt) const {
1283 rotateAmt %= BitWidth;
1286 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1289 // Square Root - this method computes and returns the square root of "this".
1290 // Three mechanisms are used for computation. For small values (<= 5 bits),
1291 // a table lookup is done. This gets some performance for common cases. For
1292 // values using less than 52 bits, the value is converted to double and then
1293 // the libc sqrt function is called. The result is rounded and then converted
1294 // back to a uint64_t which is then used to construct the result. Finally,
1295 // the Babylonian method for computing square roots is used.
1296 APInt APInt::sqrt() const {
1298 // Determine the magnitude of the value.
1299 unsigned magnitude = getActiveBits();
1301 // Use a fast table for some small values. This also gets rid of some
1302 // rounding errors in libc sqrt for small values.
1303 if (magnitude <= 5) {
1304 static const uint8_t results[32] = {
1307 /* 3- 6 */ 2, 2, 2, 2,
1308 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1309 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1310 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1313 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1316 // If the magnitude of the value fits in less than 52 bits (the precision of
1317 // an IEEE double precision floating point value), then we can use the
1318 // libc sqrt function which will probably use a hardware sqrt computation.
1319 // This should be faster than the algorithm below.
1320 if (magnitude < 52) {
1321 return APInt(BitWidth,
1322 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1325 // Okay, all the short cuts are exhausted. We must compute it. The following
1326 // is a classical Babylonian method for computing the square root. This code
1327 // was adapted to APInt from a wikipedia article on such computations.
1328 // See http://www.wikipedia.org/ and go to the page named
1329 // Calculate_an_integer_square_root.
1330 unsigned nbits = BitWidth, i = 4;
1331 APInt testy(BitWidth, 16);
1332 APInt x_old(BitWidth, 1);
1333 APInt x_new(BitWidth, 0);
1334 APInt two(BitWidth, 2);
1336 // Select a good starting value using binary logarithms.
1337 for (;; i += 2, testy = testy.shl(2))
1338 if (i >= nbits || this->ule(testy)) {
1339 x_old = x_old.shl(i / 2);
1343 // Use the Babylonian method to arrive at the integer square root:
1345 x_new = (this->udiv(x_old) + x_old).udiv(two);
1346 if (x_old.ule(x_new))
1351 // Make sure we return the closest approximation
1352 // NOTE: The rounding calculation below is correct. It will produce an
1353 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1354 // determined to be a rounding issue with pari/gp as it begins to use a
1355 // floating point representation after 192 bits. There are no discrepancies
1356 // between this algorithm and pari/gp for bit widths < 192 bits.
1357 APInt square(x_old * x_old);
1358 APInt nextSquare((x_old + 1) * (x_old +1));
1359 if (this->ult(square))
1361 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1362 APInt midpoint((nextSquare - square).udiv(two));
1363 APInt offset(*this - square);
1364 if (offset.ult(midpoint))
1369 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1370 /// iterative extended Euclidean algorithm is used to solve for this value,
1371 /// however we simplify it to speed up calculating only the inverse, and take
1372 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1373 /// (potentially large) APInts around.
1374 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1375 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1377 // Using the properties listed at the following web page (accessed 06/21/08):
1378 // http://www.numbertheory.org/php/euclid.html
1379 // (especially the properties numbered 3, 4 and 9) it can be proved that
1380 // BitWidth bits suffice for all the computations in the algorithm implemented
1381 // below. More precisely, this number of bits suffice if the multiplicative
1382 // inverse exists, but may not suffice for the general extended Euclidean
1385 APInt r[2] = { modulo, *this };
1386 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1387 APInt q(BitWidth, 0);
1390 for (i = 0; r[i^1] != 0; i ^= 1) {
1391 // An overview of the math without the confusing bit-flipping:
1392 // q = r[i-2] / r[i-1]
1393 // r[i] = r[i-2] % r[i-1]
1394 // t[i] = t[i-2] - t[i-1] * q
1395 udivrem(r[i], r[i^1], q, r[i]);
1399 // If this APInt and the modulo are not coprime, there is no multiplicative
1400 // inverse, so return 0. We check this by looking at the next-to-last
1401 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1404 return APInt(BitWidth, 0);
1406 // The next-to-last t is the multiplicative inverse. However, we are
1407 // interested in a positive inverse. Calcuate a positive one from a negative
1408 // one if necessary. A simple addition of the modulo suffices because
1409 // abs(t[i]) is known to be less than *this/2 (see the link above).
1410 return t[i].isNegative() ? t[i] + modulo : t[i];
1413 /// Calculate the magic numbers required to implement a signed integer division
1414 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1415 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1416 /// Warren, Jr., chapter 10.
1417 APInt::ms APInt::magic() const {
1418 const APInt& d = *this;
1420 APInt ad, anc, delta, q1, r1, q2, r2, t;
1421 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1425 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1426 anc = t - 1 - t.urem(ad); // absolute value of nc
1427 p = d.getBitWidth() - 1; // initialize p
1428 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1429 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1430 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1431 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1434 q1 = q1<<1; // update q1 = 2p/abs(nc)
1435 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1436 if (r1.uge(anc)) { // must be unsigned comparison
1440 q2 = q2<<1; // update q2 = 2p/abs(d)
1441 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1442 if (r2.uge(ad)) { // must be unsigned comparison
1447 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1450 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1451 mag.s = p - d.getBitWidth(); // resulting shift
1455 /// Calculate the magic numbers required to implement an unsigned integer
1456 /// division by a constant as a sequence of multiplies, adds and shifts.
1457 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1458 /// S. Warren, Jr., chapter 10.
1459 /// LeadingZeros can be used to simplify the calculation if the upper bits
1460 /// of the divided value are known zero.
1461 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1462 const APInt& d = *this;
1464 APInt nc, delta, q1, r1, q2, r2;
1466 magu.a = 0; // initialize "add" indicator
1467 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1468 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1469 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1471 nc = allOnes - (allOnes - d).urem(d);
1472 p = d.getBitWidth() - 1; // initialize p
1473 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1474 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1475 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1476 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1479 if (r1.uge(nc - r1)) {
1480 q1 = q1 + q1 + 1; // update q1
1481 r1 = r1 + r1 - nc; // update r1
1484 q1 = q1+q1; // update q1
1485 r1 = r1+r1; // update r1
1487 if ((r2 + 1).uge(d - r2)) {
1488 if (q2.uge(signedMax)) magu.a = 1;
1489 q2 = q2+q2 + 1; // update q2
1490 r2 = r2+r2 + 1 - d; // update r2
1493 if (q2.uge(signedMin)) magu.a = 1;
1494 q2 = q2+q2; // update q2
1495 r2 = r2+r2 + 1; // update r2
1498 } while (p < d.getBitWidth()*2 &&
1499 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1500 magu.m = q2 + 1; // resulting magic number
1501 magu.s = p - d.getBitWidth(); // resulting shift
1505 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1506 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1507 /// variables here have the same names as in the algorithm. Comments explain
1508 /// the algorithm and any deviation from it.
1509 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1510 unsigned m, unsigned n) {
1511 assert(u && "Must provide dividend");
1512 assert(v && "Must provide divisor");
1513 assert(q && "Must provide quotient");
1514 assert(u != v && u != q && v != q && "Must us different memory");
1515 assert(n>1 && "n must be > 1");
1517 // Knuth uses the value b as the base of the number system. In our case b
1518 // is 2^31 so we just set it to -1u.
1519 uint64_t b = uint64_t(1) << 32;
1522 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1523 DEBUG(dbgs() << "KnuthDiv: original:");
1524 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1525 DEBUG(dbgs() << " by");
1526 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1527 DEBUG(dbgs() << '\n');
1529 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1530 // u and v by d. Note that we have taken Knuth's advice here to use a power
1531 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1532 // 2 allows us to shift instead of multiply and it is easy to determine the
1533 // shift amount from the leading zeros. We are basically normalizing the u
1534 // and v so that its high bits are shifted to the top of v's range without
1535 // overflow. Note that this can require an extra word in u so that u must
1536 // be of length m+n+1.
1537 unsigned shift = countLeadingZeros(v[n-1]);
1538 unsigned v_carry = 0;
1539 unsigned u_carry = 0;
1541 for (unsigned i = 0; i < m+n; ++i) {
1542 unsigned u_tmp = u[i] >> (32 - shift);
1543 u[i] = (u[i] << shift) | u_carry;
1546 for (unsigned i = 0; i < n; ++i) {
1547 unsigned v_tmp = v[i] >> (32 - shift);
1548 v[i] = (v[i] << shift) | v_carry;
1554 DEBUG(dbgs() << "KnuthDiv: normal:");
1555 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1556 DEBUG(dbgs() << " by");
1557 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1558 DEBUG(dbgs() << '\n');
1561 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1564 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1565 // D3. [Calculate q'.].
1566 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1567 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1568 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1569 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1570 // on v[n-2] determines at high speed most of the cases in which the trial
1571 // value qp is one too large, and it eliminates all cases where qp is two
1573 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1574 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1575 uint64_t qp = dividend / v[n-1];
1576 uint64_t rp = dividend % v[n-1];
1577 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1580 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1583 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1585 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1586 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1587 // consists of a simple multiplication by a one-place number, combined with
1590 for (unsigned i = 0; i < n; ++i) {
1591 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1592 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1593 bool borrow = subtrahend > u_tmp;
1594 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1595 << ", subtrahend == " << subtrahend
1596 << ", borrow = " << borrow << '\n');
1598 uint64_t result = u_tmp - subtrahend;
1600 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1601 u[k++] = (unsigned)(result >> 32); // subtract high word
1602 while (borrow && k <= m+n) { // deal with borrow to the left
1608 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1611 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1612 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1613 DEBUG(dbgs() << '\n');
1614 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1615 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1616 // true value plus b**(n+1), namely as the b's complement of
1617 // the true value, and a "borrow" to the left should be remembered.
1620 bool carry = true; // true because b's complement is "complement + 1"
1621 for (unsigned i = 0; i <= m+n; ++i) {
1622 u[i] = ~u[i] + carry; // b's complement
1623 carry = carry && u[i] == 0;
1626 DEBUG(dbgs() << "KnuthDiv: after complement:");
1627 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1628 DEBUG(dbgs() << '\n');
1630 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1631 // negative, go to step D6; otherwise go on to step D7.
1632 q[j] = (unsigned)qp;
1634 // D6. [Add back]. The probability that this step is necessary is very
1635 // small, on the order of only 2/b. Make sure that test data accounts for
1636 // this possibility. Decrease q[j] by 1
1638 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1639 // A carry will occur to the left of u[j+n], and it should be ignored
1640 // since it cancels with the borrow that occurred in D4.
1642 for (unsigned i = 0; i < n; i++) {
1643 unsigned limit = std::min(u[j+i],v[i]);
1644 u[j+i] += v[i] + carry;
1645 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1649 DEBUG(dbgs() << "KnuthDiv: after correction:");
1650 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1651 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1653 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1656 DEBUG(dbgs() << "KnuthDiv: quotient:");
1657 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1658 DEBUG(dbgs() << '\n');
1660 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1661 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1662 // compute the remainder (urem uses this).
1664 // The value d is expressed by the "shift" value above since we avoided
1665 // multiplication by d by using a shift left. So, all we have to do is
1666 // shift right here. In order to mak
1669 DEBUG(dbgs() << "KnuthDiv: remainder:");
1670 for (int i = n-1; i >= 0; i--) {
1671 r[i] = (u[i] >> shift) | carry;
1672 carry = u[i] << (32 - shift);
1673 DEBUG(dbgs() << " " << r[i]);
1676 for (int i = n-1; i >= 0; i--) {
1678 DEBUG(dbgs() << " " << r[i]);
1681 DEBUG(dbgs() << '\n');
1684 DEBUG(dbgs() << '\n');
1688 void APInt::divide(const APInt LHS, unsigned lhsWords,
1689 const APInt &RHS, unsigned rhsWords,
1690 APInt *Quotient, APInt *Remainder)
1692 assert(lhsWords >= rhsWords && "Fractional result");
1694 // First, compose the values into an array of 32-bit words instead of
1695 // 64-bit words. This is a necessity of both the "short division" algorithm
1696 // and the Knuth "classical algorithm" which requires there to be native
1697 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1698 // can't use 64-bit operands here because we don't have native results of
1699 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1700 // work on large-endian machines.
1701 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1702 unsigned n = rhsWords * 2;
1703 unsigned m = (lhsWords * 2) - n;
1705 // Allocate space for the temporary values we need either on the stack, if
1706 // it will fit, or on the heap if it won't.
1707 unsigned SPACE[128];
1708 unsigned *U = nullptr;
1709 unsigned *V = nullptr;
1710 unsigned *Q = nullptr;
1711 unsigned *R = nullptr;
1712 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1715 Q = &SPACE[(m+n+1) + n];
1717 R = &SPACE[(m+n+1) + n + (m+n)];
1719 U = new unsigned[m + n + 1];
1720 V = new unsigned[n];
1721 Q = new unsigned[m+n];
1723 R = new unsigned[n];
1726 // Initialize the dividend
1727 memset(U, 0, (m+n+1)*sizeof(unsigned));
1728 for (unsigned i = 0; i < lhsWords; ++i) {
1729 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1730 U[i * 2] = (unsigned)(tmp & mask);
1731 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1733 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1735 // Initialize the divisor
1736 memset(V, 0, (n)*sizeof(unsigned));
1737 for (unsigned i = 0; i < rhsWords; ++i) {
1738 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1739 V[i * 2] = (unsigned)(tmp & mask);
1740 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1743 // initialize the quotient and remainder
1744 memset(Q, 0, (m+n) * sizeof(unsigned));
1746 memset(R, 0, n * sizeof(unsigned));
1748 // Now, adjust m and n for the Knuth division. n is the number of words in
1749 // the divisor. m is the number of words by which the dividend exceeds the
1750 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1751 // contain any zero words or the Knuth algorithm fails.
1752 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1756 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1759 // If we're left with only a single word for the divisor, Knuth doesn't work
1760 // so we implement the short division algorithm here. This is much simpler
1761 // and faster because we are certain that we can divide a 64-bit quantity
1762 // by a 32-bit quantity at hardware speed and short division is simply a
1763 // series of such operations. This is just like doing short division but we
1764 // are using base 2^32 instead of base 10.
1765 assert(n != 0 && "Divide by zero?");
1767 unsigned divisor = V[0];
1768 unsigned remainder = 0;
1769 for (int i = m+n-1; i >= 0; i--) {
1770 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1771 if (partial_dividend == 0) {
1774 } else if (partial_dividend < divisor) {
1776 remainder = (unsigned)partial_dividend;
1777 } else if (partial_dividend == divisor) {
1781 Q[i] = (unsigned)(partial_dividend / divisor);
1782 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1788 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1790 KnuthDiv(U, V, Q, R, m, n);
1793 // If the caller wants the quotient
1795 // Set up the Quotient value's memory.
1796 if (Quotient->BitWidth != LHS.BitWidth) {
1797 if (Quotient->isSingleWord())
1800 delete [] Quotient->pVal;
1801 Quotient->BitWidth = LHS.BitWidth;
1802 if (!Quotient->isSingleWord())
1803 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1805 Quotient->clearAllBits();
1807 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1809 if (lhsWords == 1) {
1811 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1812 if (Quotient->isSingleWord())
1813 Quotient->VAL = tmp;
1815 Quotient->pVal[0] = tmp;
1817 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1818 for (unsigned i = 0; i < lhsWords; ++i)
1820 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1824 // If the caller wants the remainder
1826 // Set up the Remainder value's memory.
1827 if (Remainder->BitWidth != RHS.BitWidth) {
1828 if (Remainder->isSingleWord())
1831 delete [] Remainder->pVal;
1832 Remainder->BitWidth = RHS.BitWidth;
1833 if (!Remainder->isSingleWord())
1834 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1836 Remainder->clearAllBits();
1838 // The remainder is in R. Reconstitute the remainder into Remainder's low
1840 if (rhsWords == 1) {
1842 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1843 if (Remainder->isSingleWord())
1844 Remainder->VAL = tmp;
1846 Remainder->pVal[0] = tmp;
1848 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1849 for (unsigned i = 0; i < rhsWords; ++i)
1850 Remainder->pVal[i] =
1851 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1855 // Clean up the memory we allocated.
1856 if (U != &SPACE[0]) {
1864 APInt APInt::udiv(const APInt& RHS) const {
1865 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1867 // First, deal with the easy case
1868 if (isSingleWord()) {
1869 assert(RHS.VAL != 0 && "Divide by zero?");
1870 return APInt(BitWidth, VAL / RHS.VAL);
1873 // Get some facts about the LHS and RHS number of bits and words
1874 unsigned rhsBits = RHS.getActiveBits();
1875 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1876 assert(rhsWords && "Divided by zero???");
1877 unsigned lhsBits = this->getActiveBits();
1878 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1880 // Deal with some degenerate cases
1883 return APInt(BitWidth, 0);
1884 else if (lhsWords < rhsWords || this->ult(RHS)) {
1885 // X / Y ===> 0, iff X < Y
1886 return APInt(BitWidth, 0);
1887 } else if (*this == RHS) {
1889 return APInt(BitWidth, 1);
1890 } else if (lhsWords == 1 && rhsWords == 1) {
1891 // All high words are zero, just use native divide
1892 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1895 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1896 APInt Quotient(1,0); // to hold result.
1897 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
1901 APInt APInt::sdiv(const APInt &RHS) const {
1903 if (RHS.isNegative())
1904 return (-(*this)).udiv(-RHS);
1905 return -((-(*this)).udiv(RHS));
1907 if (RHS.isNegative())
1908 return -(this->udiv(-RHS));
1909 return this->udiv(RHS);
1912 APInt APInt::urem(const APInt& RHS) const {
1913 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1914 if (isSingleWord()) {
1915 assert(RHS.VAL != 0 && "Remainder by zero?");
1916 return APInt(BitWidth, VAL % RHS.VAL);
1919 // Get some facts about the LHS
1920 unsigned lhsBits = getActiveBits();
1921 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1923 // Get some facts about the RHS
1924 unsigned rhsBits = RHS.getActiveBits();
1925 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1926 assert(rhsWords && "Performing remainder operation by zero ???");
1928 // Check the degenerate cases
1929 if (lhsWords == 0) {
1931 return APInt(BitWidth, 0);
1932 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1933 // X % Y ===> X, iff X < Y
1935 } else if (*this == RHS) {
1937 return APInt(BitWidth, 0);
1938 } else if (lhsWords == 1) {
1939 // All high words are zero, just use native remainder
1940 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1943 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1944 APInt Remainder(1,0);
1945 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
1949 APInt APInt::srem(const APInt &RHS) const {
1951 if (RHS.isNegative())
1952 return -((-(*this)).urem(-RHS));
1953 return -((-(*this)).urem(RHS));
1955 if (RHS.isNegative())
1956 return this->urem(-RHS);
1957 return this->urem(RHS);
1960 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1961 APInt &Quotient, APInt &Remainder) {
1962 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1964 // First, deal with the easy case
1965 if (LHS.isSingleWord()) {
1966 assert(RHS.VAL != 0 && "Divide by zero?");
1967 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1968 uint64_t RemVal = LHS.VAL % RHS.VAL;
1969 Quotient = APInt(LHS.BitWidth, QuotVal);
1970 Remainder = APInt(LHS.BitWidth, RemVal);
1974 // Get some size facts about the dividend and divisor
1975 unsigned lhsBits = LHS.getActiveBits();
1976 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1977 unsigned rhsBits = RHS.getActiveBits();
1978 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1980 // Check the degenerate cases
1981 if (lhsWords == 0) {
1982 Quotient = 0; // 0 / Y ===> 0
1983 Remainder = 0; // 0 % Y ===> 0
1987 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1988 Remainder = LHS; // X % Y ===> X, iff X < Y
1989 Quotient = 0; // X / Y ===> 0, iff X < Y
1994 Quotient = 1; // X / X ===> 1
1995 Remainder = 0; // X % X ===> 0;
1999 if (lhsWords == 1 && rhsWords == 1) {
2000 // There is only one word to consider so use the native versions.
2001 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2002 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2003 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2004 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2008 // Okay, lets do it the long way
2009 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2012 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
2013 APInt &Quotient, APInt &Remainder) {
2014 if (LHS.isNegative()) {
2015 if (RHS.isNegative())
2016 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
2018 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
2019 Quotient = -Quotient;
2021 Remainder = -Remainder;
2022 } else if (RHS.isNegative()) {
2023 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
2024 Quotient = -Quotient;
2026 APInt::udivrem(LHS, RHS, Quotient, Remainder);
2030 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2031 APInt Res = *this+RHS;
2032 Overflow = isNonNegative() == RHS.isNonNegative() &&
2033 Res.isNonNegative() != isNonNegative();
2037 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2038 APInt Res = *this+RHS;
2039 Overflow = Res.ult(RHS);
2043 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2044 APInt Res = *this - RHS;
2045 Overflow = isNonNegative() != RHS.isNonNegative() &&
2046 Res.isNonNegative() != isNonNegative();
2050 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2051 APInt Res = *this-RHS;
2052 Overflow = Res.ugt(*this);
2056 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2057 // MININT/-1 --> overflow.
2058 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2062 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2063 APInt Res = *this * RHS;
2065 if (*this != 0 && RHS != 0)
2066 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2072 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2073 APInt Res = *this * RHS;
2075 if (*this != 0 && RHS != 0)
2076 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2082 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
2083 Overflow = ShAmt.uge(getBitWidth());
2085 return APInt(BitWidth, 0);
2087 if (isNonNegative()) // Don't allow sign change.
2088 Overflow = ShAmt.uge(countLeadingZeros());
2090 Overflow = ShAmt.uge(countLeadingOnes());
2092 return *this << ShAmt;
2095 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
2096 Overflow = ShAmt.uge(getBitWidth());
2098 return APInt(BitWidth, 0);
2100 Overflow = ShAmt.ugt(countLeadingZeros());
2102 return *this << ShAmt;
2108 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2109 // Check our assumptions here
2110 assert(!str.empty() && "Invalid string length");
2111 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2113 "Radix should be 2, 8, 10, 16, or 36!");
2115 StringRef::iterator p = str.begin();
2116 size_t slen = str.size();
2117 bool isNeg = *p == '-';
2118 if (*p == '-' || *p == '+') {
2121 assert(slen && "String is only a sign, needs a value.");
2123 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2124 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2125 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2126 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2127 "Insufficient bit width");
2130 if (!isSingleWord())
2131 pVal = getClearedMemory(getNumWords());
2133 // Figure out if we can shift instead of multiply
2134 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2136 // Set up an APInt for the digit to add outside the loop so we don't
2137 // constantly construct/destruct it.
2138 APInt apdigit(getBitWidth(), 0);
2139 APInt apradix(getBitWidth(), radix);
2141 // Enter digit traversal loop
2142 for (StringRef::iterator e = str.end(); p != e; ++p) {
2143 unsigned digit = getDigit(*p, radix);
2144 assert(digit < radix && "Invalid character in digit string");
2146 // Shift or multiply the value by the radix
2154 // Add in the digit we just interpreted
2155 if (apdigit.isSingleWord())
2156 apdigit.VAL = digit;
2158 apdigit.pVal[0] = digit;
2161 // If its negative, put it in two's complement form
2164 this->flipAllBits();
2168 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2169 bool Signed, bool formatAsCLiteral) const {
2170 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2172 "Radix should be 2, 8, 10, 16, or 36!");
2174 const char *Prefix = "";
2175 if (formatAsCLiteral) {
2178 // Binary literals are a non-standard extension added in gcc 4.3:
2179 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2191 llvm_unreachable("Invalid radix!");
2195 // First, check for a zero value and just short circuit the logic below.
2198 Str.push_back(*Prefix);
2205 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2207 if (isSingleWord()) {
2209 char *BufPtr = Buffer+65;
2215 int64_t I = getSExtValue();
2225 Str.push_back(*Prefix);
2230 *--BufPtr = Digits[N % Radix];
2233 Str.append(BufPtr, Buffer+65);
2239 if (Signed && isNegative()) {
2240 // They want to print the signed version and it is a negative value
2241 // Flip the bits and add one to turn it into the equivalent positive
2242 // value and put a '-' in the result.
2249 Str.push_back(*Prefix);
2253 // We insert the digits backward, then reverse them to get the right order.
2254 unsigned StartDig = Str.size();
2256 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2257 // because the number of bits per digit (1, 3 and 4 respectively) divides
2258 // equaly. We just shift until the value is zero.
2259 if (Radix == 2 || Radix == 8 || Radix == 16) {
2260 // Just shift tmp right for each digit width until it becomes zero
2261 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2262 unsigned MaskAmt = Radix - 1;
2265 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2266 Str.push_back(Digits[Digit]);
2267 Tmp = Tmp.lshr(ShiftAmt);
2270 APInt divisor(Radix == 10? 4 : 8, Radix);
2272 APInt APdigit(1, 0);
2273 APInt tmp2(Tmp.getBitWidth(), 0);
2274 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2276 unsigned Digit = (unsigned)APdigit.getZExtValue();
2277 assert(Digit < Radix && "divide failed");
2278 Str.push_back(Digits[Digit]);
2283 // Reverse the digits before returning.
2284 std::reverse(Str.begin()+StartDig, Str.end());
2287 /// toString - This returns the APInt as a std::string. Note that this is an
2288 /// inefficient method. It is better to pass in a SmallVector/SmallString
2289 /// to the methods above.
2290 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2292 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2297 void APInt::dump() const {
2298 SmallString<40> S, U;
2299 this->toStringUnsigned(U);
2300 this->toStringSigned(S);
2301 dbgs() << "APInt(" << BitWidth << "b, "
2302 << U << "u " << S << "s)";
2305 void APInt::print(raw_ostream &OS, bool isSigned) const {
2307 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2311 // This implements a variety of operations on a representation of
2312 // arbitrary precision, two's-complement, bignum integer values.
2314 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2315 // and unrestricting assumption.
2316 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
2318 /* Some handy functions local to this file. */
2321 /* Returns the integer part with the least significant BITS set.
2322 BITS cannot be zero. */
2323 static inline integerPart
2324 lowBitMask(unsigned int bits)
2326 assert(bits != 0 && bits <= integerPartWidth);
2328 return ~(integerPart) 0 >> (integerPartWidth - bits);
2331 /* Returns the value of the lower half of PART. */
2332 static inline integerPart
2333 lowHalf(integerPart part)
2335 return part & lowBitMask(integerPartWidth / 2);
2338 /* Returns the value of the upper half of PART. */
2339 static inline integerPart
2340 highHalf(integerPart part)
2342 return part >> (integerPartWidth / 2);
2345 /* Returns the bit number of the most significant set bit of a part.
2346 If the input number has no bits set -1U is returned. */
2348 partMSB(integerPart value)
2350 return findLastSet(value, ZB_Max);
2353 /* Returns the bit number of the least significant set bit of a
2354 part. If the input number has no bits set -1U is returned. */
2356 partLSB(integerPart value)
2358 return findFirstSet(value, ZB_Max);
2362 /* Sets the least significant part of a bignum to the input value, and
2363 zeroes out higher parts. */
2365 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2372 for (i = 1; i < parts; i++)
2376 /* Assign one bignum to another. */
2378 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2382 for (i = 0; i < parts; i++)
2386 /* Returns true if a bignum is zero, false otherwise. */
2388 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2392 for (i = 0; i < parts; i++)
2399 /* Extract the given bit of a bignum; returns 0 or 1. */
2401 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2403 return (parts[bit / integerPartWidth] &
2404 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2407 /* Set the given bit of a bignum. */
2409 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2411 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2414 /* Clears the given bit of a bignum. */
2416 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2418 parts[bit / integerPartWidth] &=
2419 ~((integerPart) 1 << (bit % integerPartWidth));
2422 /* Returns the bit number of the least significant set bit of a
2423 number. If the input number has no bits set -1U is returned. */
2425 APInt::tcLSB(const integerPart *parts, unsigned int n)
2427 unsigned int i, lsb;
2429 for (i = 0; i < n; i++) {
2430 if (parts[i] != 0) {
2431 lsb = partLSB(parts[i]);
2433 return lsb + i * integerPartWidth;
2440 /* Returns the bit number of the most significant set bit of a number.
2441 If the input number has no bits set -1U is returned. */
2443 APInt::tcMSB(const integerPart *parts, unsigned int n)
2450 if (parts[n] != 0) {
2451 msb = partMSB(parts[n]);
2453 return msb + n * integerPartWidth;
2460 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2461 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2462 the least significant bit of DST. All high bits above srcBITS in
2463 DST are zero-filled. */
2465 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2466 unsigned int srcBits, unsigned int srcLSB)
2468 unsigned int firstSrcPart, dstParts, shift, n;
2470 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2471 assert(dstParts <= dstCount);
2473 firstSrcPart = srcLSB / integerPartWidth;
2474 tcAssign (dst, src + firstSrcPart, dstParts);
2476 shift = srcLSB % integerPartWidth;
2477 tcShiftRight (dst, dstParts, shift);
2479 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2480 in DST. If this is less that srcBits, append the rest, else
2481 clear the high bits. */
2482 n = dstParts * integerPartWidth - shift;
2484 integerPart mask = lowBitMask (srcBits - n);
2485 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2486 << n % integerPartWidth);
2487 } else if (n > srcBits) {
2488 if (srcBits % integerPartWidth)
2489 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2492 /* Clear high parts. */
2493 while (dstParts < dstCount)
2494 dst[dstParts++] = 0;
2497 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2499 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2500 integerPart c, unsigned int parts)
2506 for (i = 0; i < parts; i++) {
2511 dst[i] += rhs[i] + 1;
2522 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2524 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2525 integerPart c, unsigned int parts)
2531 for (i = 0; i < parts; i++) {
2536 dst[i] -= rhs[i] + 1;
2547 /* Negate a bignum in-place. */
2549 APInt::tcNegate(integerPart *dst, unsigned int parts)
2551 tcComplement(dst, parts);
2552 tcIncrement(dst, parts);
2555 /* DST += SRC * MULTIPLIER + CARRY if add is true
2556 DST = SRC * MULTIPLIER + CARRY if add is false
2558 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2559 they must start at the same point, i.e. DST == SRC.
2561 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2562 returned. Otherwise DST is filled with the least significant
2563 DSTPARTS parts of the result, and if all of the omitted higher
2564 parts were zero return zero, otherwise overflow occurred and
2567 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2568 integerPart multiplier, integerPart carry,
2569 unsigned int srcParts, unsigned int dstParts,
2574 /* Otherwise our writes of DST kill our later reads of SRC. */
2575 assert(dst <= src || dst >= src + srcParts);
2576 assert(dstParts <= srcParts + 1);
2578 /* N loops; minimum of dstParts and srcParts. */
2579 n = dstParts < srcParts ? dstParts: srcParts;
2581 for (i = 0; i < n; i++) {
2582 integerPart low, mid, high, srcPart;
2584 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2586 This cannot overflow, because
2588 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2590 which is less than n^2. */
2594 if (multiplier == 0 || srcPart == 0) {
2598 low = lowHalf(srcPart) * lowHalf(multiplier);
2599 high = highHalf(srcPart) * highHalf(multiplier);
2601 mid = lowHalf(srcPart) * highHalf(multiplier);
2602 high += highHalf(mid);
2603 mid <<= integerPartWidth / 2;
2604 if (low + mid < low)
2608 mid = highHalf(srcPart) * lowHalf(multiplier);
2609 high += highHalf(mid);
2610 mid <<= integerPartWidth / 2;
2611 if (low + mid < low)
2615 /* Now add carry. */
2616 if (low + carry < low)
2622 /* And now DST[i], and store the new low part there. */
2623 if (low + dst[i] < low)
2633 /* Full multiplication, there is no overflow. */
2634 assert(i + 1 == dstParts);
2638 /* We overflowed if there is carry. */
2642 /* We would overflow if any significant unwritten parts would be
2643 non-zero. This is true if any remaining src parts are non-zero
2644 and the multiplier is non-zero. */
2646 for (; i < srcParts; i++)
2650 /* We fitted in the narrow destination. */
2655 /* DST = LHS * RHS, where DST has the same width as the operands and
2656 is filled with the least significant parts of the result. Returns
2657 one if overflow occurred, otherwise zero. DST must be disjoint
2658 from both operands. */
2660 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2661 const integerPart *rhs, unsigned int parts)
2666 assert(dst != lhs && dst != rhs);
2669 tcSet(dst, 0, parts);
2671 for (i = 0; i < parts; i++)
2672 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2678 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2679 operands. No overflow occurs. DST must be disjoint from both
2680 operands. Returns the number of parts required to hold the
2683 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2684 const integerPart *rhs, unsigned int lhsParts,
2685 unsigned int rhsParts)
2687 /* Put the narrower number on the LHS for less loops below. */
2688 if (lhsParts > rhsParts) {
2689 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2693 assert(dst != lhs && dst != rhs);
2695 tcSet(dst, 0, rhsParts);
2697 for (n = 0; n < lhsParts; n++)
2698 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2700 n = lhsParts + rhsParts;
2702 return n - (dst[n - 1] == 0);
2706 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2707 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2708 set REMAINDER to the remainder, return zero. i.e.
2710 OLD_LHS = RHS * LHS + REMAINDER
2712 SCRATCH is a bignum of the same size as the operands and result for
2713 use by the routine; its contents need not be initialized and are
2714 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2717 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2718 integerPart *remainder, integerPart *srhs,
2721 unsigned int n, shiftCount;
2724 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2726 shiftCount = tcMSB(rhs, parts) + 1;
2727 if (shiftCount == 0)
2730 shiftCount = parts * integerPartWidth - shiftCount;
2731 n = shiftCount / integerPartWidth;
2732 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2734 tcAssign(srhs, rhs, parts);
2735 tcShiftLeft(srhs, parts, shiftCount);
2736 tcAssign(remainder, lhs, parts);
2737 tcSet(lhs, 0, parts);
2739 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2744 compare = tcCompare(remainder, srhs, parts);
2746 tcSubtract(remainder, srhs, 0, parts);
2750 if (shiftCount == 0)
2753 tcShiftRight(srhs, parts, 1);
2754 if ((mask >>= 1) == 0)
2755 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2761 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2762 There are no restrictions on COUNT. */
2764 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2767 unsigned int jump, shift;
2769 /* Jump is the inter-part jump; shift is is intra-part shift. */
2770 jump = count / integerPartWidth;
2771 shift = count % integerPartWidth;
2773 while (parts > jump) {
2778 /* dst[i] comes from the two parts src[i - jump] and, if we have
2779 an intra-part shift, src[i - jump - 1]. */
2780 part = dst[parts - jump];
2783 if (parts >= jump + 1)
2784 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2795 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2796 zero. There are no restrictions on COUNT. */
2798 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2801 unsigned int i, jump, shift;
2803 /* Jump is the inter-part jump; shift is is intra-part shift. */
2804 jump = count / integerPartWidth;
2805 shift = count % integerPartWidth;
2807 /* Perform the shift. This leaves the most significant COUNT bits
2808 of the result at zero. */
2809 for (i = 0; i < parts; i++) {
2812 if (i + jump >= parts) {
2815 part = dst[i + jump];
2818 if (i + jump + 1 < parts)
2819 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2828 /* Bitwise and of two bignums. */
2830 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2834 for (i = 0; i < parts; i++)
2838 /* Bitwise inclusive or of two bignums. */
2840 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2844 for (i = 0; i < parts; i++)
2848 /* Bitwise exclusive or of two bignums. */
2850 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2854 for (i = 0; i < parts; i++)
2858 /* Complement a bignum in-place. */
2860 APInt::tcComplement(integerPart *dst, unsigned int parts)
2864 for (i = 0; i < parts; i++)
2868 /* Comparison (unsigned) of two bignums. */
2870 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2875 if (lhs[parts] == rhs[parts])
2878 if (lhs[parts] > rhs[parts])
2887 /* Increment a bignum in-place, return the carry flag. */
2889 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2893 for (i = 0; i < parts; i++)
2900 /* Decrement a bignum in-place, return the borrow flag. */
2902 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2903 for (unsigned int i = 0; i < parts; i++) {
2904 // If the current word is non-zero, then the decrement has no effect on the
2905 // higher-order words of the integer and no borrow can occur. Exit early.
2909 // If every word was zero, then there is a borrow.
2914 /* Set the least significant BITS bits of a bignum, clear the
2917 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2923 while (bits > integerPartWidth) {
2924 dst[i++] = ~(integerPart) 0;
2925 bits -= integerPartWidth;
2929 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);