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/ArrayRef.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/MathExtras.h"
24 #include "llvm/Support/raw_ostream.h"
31 #define DEBUG_TYPE "apint"
33 /// A utility function for allocating memory, checking for allocation failures,
34 /// and ensuring the contents are zeroed.
35 inline static uint64_t* getClearedMemory(unsigned numWords) {
36 uint64_t * result = new uint64_t[numWords];
37 assert(result && "APInt memory allocation fails!");
38 memset(result, 0, numWords * sizeof(uint64_t));
42 /// A utility function for allocating memory and checking for allocation
43 /// failure. The content is not zeroed.
44 inline static uint64_t* getMemory(unsigned numWords) {
45 uint64_t * result = new uint64_t[numWords];
46 assert(result && "APInt memory allocation fails!");
50 /// A utility function that converts a character to a digit.
51 inline static unsigned getDigit(char cdigit, uint8_t radix) {
54 if (radix == 16 || radix == 36) {
78 void APInt::initSlowCase(uint64_t val, bool isSigned) {
79 pVal = getClearedMemory(getNumWords());
81 if (isSigned && int64_t(val) < 0)
82 for (unsigned i = 1; i < getNumWords(); ++i)
86 void APInt::initSlowCase(const APInt& that) {
87 pVal = getMemory(getNumWords());
88 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
91 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
92 assert(BitWidth && "Bitwidth too small");
93 assert(bigVal.data() && "Null pointer detected!");
97 // Get memory, cleared to 0
98 pVal = getClearedMemory(getNumWords());
99 // Calculate the number of words to copy
100 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
101 // Copy the words from bigVal to pVal
102 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
104 // Make sure unused high bits are cleared
108 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
109 : BitWidth(numBits), VAL(0) {
110 initFromArray(bigVal);
113 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
114 : BitWidth(numBits), VAL(0) {
115 initFromArray(makeArrayRef(bigVal, numWords));
118 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
119 : BitWidth(numbits), VAL(0) {
120 assert(BitWidth && "Bitwidth too small");
121 fromString(numbits, Str, radix);
124 APInt& APInt::AssignSlowCase(const APInt& RHS) {
125 // Don't do anything for X = X
129 if (BitWidth == RHS.getBitWidth()) {
130 // assume same bit-width single-word case is already handled
131 assert(!isSingleWord());
132 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
136 if (isSingleWord()) {
137 // assume case where both are single words is already handled
138 assert(!RHS.isSingleWord());
140 pVal = getMemory(RHS.getNumWords());
141 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
142 } else if (getNumWords() == RHS.getNumWords())
143 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
144 else if (RHS.isSingleWord()) {
149 pVal = getMemory(RHS.getNumWords());
150 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
152 BitWidth = RHS.BitWidth;
153 return clearUnusedBits();
156 APInt& APInt::operator=(uint64_t RHS) {
161 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
163 return clearUnusedBits();
166 /// This method 'profiles' an APInt for use with FoldingSet.
167 void APInt::Profile(FoldingSetNodeID& ID) const {
168 ID.AddInteger(BitWidth);
170 if (isSingleWord()) {
175 unsigned NumWords = getNumWords();
176 for (unsigned i = 0; i < NumWords; ++i)
177 ID.AddInteger(pVal[i]);
180 /// This function adds a single "digit" integer, y, to the multiple
181 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
182 /// 1 is returned if there is a carry out, otherwise 0 is returned.
183 /// @returns the carry of the addition.
184 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
185 for (unsigned i = 0; i < len; ++i) {
188 y = 1; // Carry one to next digit.
190 y = 0; // No need to carry so exit early
197 /// @brief Prefix increment operator. Increments the APInt by one.
198 APInt& APInt::operator++() {
202 add_1(pVal, pVal, getNumWords(), 1);
203 return clearUnusedBits();
206 /// This function subtracts a single "digit" (64-bit word), y, from
207 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
208 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
209 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
210 /// In other words, if y > x then this function returns 1, otherwise 0.
211 /// @returns the borrow out of the subtraction
212 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
213 for (unsigned i = 0; i < len; ++i) {
217 y = 1; // We have to "borrow 1" from next "digit"
219 y = 0; // No need to borrow
220 break; // Remaining digits are unchanged so exit early
226 /// @brief Prefix decrement operator. Decrements the APInt by one.
227 APInt& APInt::operator--() {
231 sub_1(pVal, getNumWords(), 1);
232 return clearUnusedBits();
235 /// This function adds the integer array x to the integer array Y and
236 /// places the result in dest.
237 /// @returns the carry out from the addition
238 /// @brief General addition of 64-bit integer arrays
239 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
242 for (unsigned i = 0; i< len; ++i) {
243 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
244 dest[i] = x[i] + y[i] + carry;
245 carry = dest[i] < limit || (carry && dest[i] == limit);
250 /// Adds the RHS APint to this APInt.
251 /// @returns this, after addition of RHS.
252 /// @brief Addition assignment operator.
253 APInt& APInt::operator+=(const APInt& RHS) {
254 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
258 add(pVal, pVal, RHS.pVal, getNumWords());
260 return clearUnusedBits();
263 /// Subtracts the integer array y from the integer array x
264 /// @returns returns the borrow out.
265 /// @brief Generalized subtraction of 64-bit integer arrays.
266 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
269 for (unsigned i = 0; i < len; ++i) {
270 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
271 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
272 dest[i] = x_tmp - y[i];
277 /// Subtracts the RHS APInt from this APInt
278 /// @returns this, after subtraction
279 /// @brief Subtraction assignment operator.
280 APInt& APInt::operator-=(const APInt& RHS) {
281 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
285 sub(pVal, pVal, RHS.pVal, getNumWords());
286 return clearUnusedBits();
289 /// Multiplies an integer array, x, by a uint64_t integer and places the result
291 /// @returns the carry out of the multiplication.
292 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
293 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
294 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
295 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
298 // For each digit of x.
299 for (unsigned i = 0; i < len; ++i) {
300 // Split x into high and low words
301 uint64_t lx = x[i] & 0xffffffffULL;
302 uint64_t hx = x[i] >> 32;
303 // hasCarry - A flag to indicate if there is a carry to the next digit.
304 // hasCarry == 0, no carry
305 // hasCarry == 1, has carry
306 // hasCarry == 2, no carry and the calculation result == 0.
307 uint8_t hasCarry = 0;
308 dest[i] = carry + lx * ly;
309 // Determine if the add above introduces carry.
310 hasCarry = (dest[i] < carry) ? 1 : 0;
311 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
312 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
313 // (2^32 - 1) + 2^32 = 2^64.
314 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
316 carry += (lx * hy) & 0xffffffffULL;
317 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
318 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
319 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
324 /// Multiplies integer array x by integer array y and stores the result into
325 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
326 /// @brief Generalized multiplicate of integer arrays.
327 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
329 dest[xlen] = mul_1(dest, x, xlen, y[0]);
330 for (unsigned i = 1; i < ylen; ++i) {
331 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
332 uint64_t carry = 0, lx = 0, hx = 0;
333 for (unsigned j = 0; j < xlen; ++j) {
334 lx = x[j] & 0xffffffffULL;
336 // hasCarry - A flag to indicate if has carry.
337 // hasCarry == 0, no carry
338 // hasCarry == 1, has carry
339 // hasCarry == 2, no carry and the calculation result == 0.
340 uint8_t hasCarry = 0;
341 uint64_t resul = carry + lx * ly;
342 hasCarry = (resul < carry) ? 1 : 0;
343 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
344 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
346 carry += (lx * hy) & 0xffffffffULL;
347 resul = (carry << 32) | (resul & 0xffffffffULL);
349 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
350 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
351 ((lx * hy) >> 32) + hx * hy;
353 dest[i+xlen] = carry;
357 APInt& APInt::operator*=(const APInt& RHS) {
358 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
359 if (isSingleWord()) {
365 // Get some bit facts about LHS and check for zero
366 unsigned lhsBits = getActiveBits();
367 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
372 // Get some bit facts about RHS and check for zero
373 unsigned rhsBits = RHS.getActiveBits();
374 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
381 // Allocate space for the result
382 unsigned destWords = rhsWords + lhsWords;
383 uint64_t *dest = getMemory(destWords);
385 // Perform the long multiply
386 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
388 // Copy result back into *this
390 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
391 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
394 // delete dest array and return
399 APInt& APInt::operator&=(const APInt& RHS) {
400 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
401 if (isSingleWord()) {
405 unsigned numWords = getNumWords();
406 for (unsigned i = 0; i < numWords; ++i)
407 pVal[i] &= RHS.pVal[i];
411 APInt& APInt::operator|=(const APInt& RHS) {
412 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
413 if (isSingleWord()) {
417 unsigned numWords = getNumWords();
418 for (unsigned i = 0; i < numWords; ++i)
419 pVal[i] |= RHS.pVal[i];
423 APInt& APInt::operator^=(const APInt& RHS) {
424 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
425 if (isSingleWord()) {
427 this->clearUnusedBits();
430 unsigned numWords = getNumWords();
431 for (unsigned i = 0; i < numWords; ++i)
432 pVal[i] ^= RHS.pVal[i];
433 return clearUnusedBits();
436 APInt APInt::AndSlowCase(const APInt& RHS) const {
437 unsigned numWords = getNumWords();
438 uint64_t* val = getMemory(numWords);
439 for (unsigned i = 0; i < numWords; ++i)
440 val[i] = pVal[i] & RHS.pVal[i];
441 return APInt(val, getBitWidth());
444 APInt APInt::OrSlowCase(const APInt& RHS) const {
445 unsigned numWords = getNumWords();
446 uint64_t *val = getMemory(numWords);
447 for (unsigned i = 0; i < numWords; ++i)
448 val[i] = pVal[i] | RHS.pVal[i];
449 return APInt(val, getBitWidth());
452 APInt APInt::XorSlowCase(const APInt& RHS) const {
453 unsigned numWords = getNumWords();
454 uint64_t *val = getMemory(numWords);
455 for (unsigned i = 0; i < numWords; ++i)
456 val[i] = pVal[i] ^ RHS.pVal[i];
458 APInt Result(val, getBitWidth());
459 // 0^0==1 so clear the high bits in case they got set.
460 Result.clearUnusedBits();
464 APInt APInt::operator*(const APInt& RHS) const {
465 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
467 return APInt(BitWidth, VAL * RHS.VAL);
473 APInt APInt::operator+(const APInt& RHS) const {
474 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
476 return APInt(BitWidth, VAL + RHS.VAL);
477 APInt Result(BitWidth, 0);
478 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
479 Result.clearUnusedBits();
483 APInt APInt::operator+(uint64_t RHS) const {
485 return APInt(BitWidth, VAL + RHS);
487 add_1(Result.pVal, Result.pVal, getNumWords(), RHS);
488 Result.clearUnusedBits();
492 APInt APInt::operator-(const APInt& RHS) const {
493 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
495 return APInt(BitWidth, VAL - RHS.VAL);
496 APInt Result(BitWidth, 0);
497 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
498 Result.clearUnusedBits();
502 APInt APInt::operator-(uint64_t RHS) const {
504 return APInt(BitWidth, VAL - RHS);
506 sub_1(Result.pVal, getNumWords(), RHS);
507 Result.clearUnusedBits();
511 bool APInt::EqualSlowCase(const APInt& RHS) const {
512 return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
515 bool APInt::EqualSlowCase(uint64_t Val) const {
516 unsigned n = getActiveBits();
517 if (n <= APINT_BITS_PER_WORD)
518 return pVal[0] == Val;
523 bool APInt::ult(const APInt& RHS) const {
524 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
526 return VAL < RHS.VAL;
528 // Get active bit length of both operands
529 unsigned n1 = getActiveBits();
530 unsigned n2 = RHS.getActiveBits();
532 // If magnitude of LHS is less than RHS, return true.
536 // If magnitude of RHS is greather than LHS, return false.
540 // If they bot fit in a word, just compare the low order word
541 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
542 return pVal[0] < RHS.pVal[0];
544 // Otherwise, compare all words
545 unsigned topWord = whichWord(std::max(n1,n2)-1);
546 for (int i = topWord; i >= 0; --i) {
547 if (pVal[i] > RHS.pVal[i])
549 if (pVal[i] < RHS.pVal[i])
555 bool APInt::slt(const APInt& RHS) const {
556 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
557 if (isSingleWord()) {
558 int64_t lhsSext = SignExtend64(VAL, BitWidth);
559 int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
560 return lhsSext < rhsSext;
563 bool lhsNeg = isNegative();
564 bool rhsNeg = RHS.isNegative();
566 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
567 if (lhsNeg != rhsNeg)
570 // Otherwise we can just use an unsigned comparision, because even negative
571 // numbers compare correctly this way if both have the same signed-ness.
575 void APInt::setBit(unsigned bitPosition) {
577 VAL |= maskBit(bitPosition);
579 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
582 /// Set the given bit to 0 whose position is given as "bitPosition".
583 /// @brief Set a given bit to 0.
584 void APInt::clearBit(unsigned bitPosition) {
586 VAL &= ~maskBit(bitPosition);
588 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
591 /// @brief Toggle every bit to its opposite value.
593 /// Toggle a given bit to its opposite value whose position is given
594 /// as "bitPosition".
595 /// @brief Toggles a given bit to its opposite value.
596 void APInt::flipBit(unsigned bitPosition) {
597 assert(bitPosition < BitWidth && "Out of the bit-width range!");
598 if ((*this)[bitPosition]) clearBit(bitPosition);
599 else setBit(bitPosition);
602 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
603 assert(!str.empty() && "Invalid string length");
604 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
606 "Radix should be 2, 8, 10, 16, or 36!");
608 size_t slen = str.size();
610 // Each computation below needs to know if it's negative.
611 StringRef::iterator p = str.begin();
612 unsigned isNegative = *p == '-';
613 if (*p == '-' || *p == '+') {
616 assert(slen && "String is only a sign, needs a value.");
619 // For radixes of power-of-two values, the bits required is accurately and
622 return slen + isNegative;
624 return slen * 3 + isNegative;
626 return slen * 4 + isNegative;
630 // This is grossly inefficient but accurate. We could probably do something
631 // with a computation of roughly slen*64/20 and then adjust by the value of
632 // the first few digits. But, I'm not sure how accurate that could be.
634 // Compute a sufficient number of bits that is always large enough but might
635 // be too large. This avoids the assertion in the constructor. This
636 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
637 // bits in that case.
639 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
640 : (slen == 1 ? 7 : slen * 16/3);
642 // Convert to the actual binary value.
643 APInt tmp(sufficient, StringRef(p, slen), radix);
645 // Compute how many bits are required. If the log is infinite, assume we need
647 unsigned log = tmp.logBase2();
648 if (log == (unsigned)-1) {
649 return isNegative + 1;
651 return isNegative + log + 1;
655 hash_code llvm::hash_value(const APInt &Arg) {
656 if (Arg.isSingleWord())
657 return hash_combine(Arg.VAL);
659 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
662 bool APInt::isSplat(unsigned SplatSizeInBits) const {
663 assert(getBitWidth() % SplatSizeInBits == 0 &&
664 "SplatSizeInBits must divide width!");
665 // We can check that all parts of an integer are equal by making use of a
666 // little trick: rotate and check if it's still the same value.
667 return *this == rotl(SplatSizeInBits);
670 /// This function returns the high "numBits" bits of this APInt.
671 APInt APInt::getHiBits(unsigned numBits) const {
672 return APIntOps::lshr(*this, BitWidth - numBits);
675 /// This function returns the low "numBits" bits of this APInt.
676 APInt APInt::getLoBits(unsigned numBits) const {
677 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
681 unsigned APInt::countLeadingZerosSlowCase() const {
683 for (int i = getNumWords()-1; i >= 0; --i) {
684 integerPart V = pVal[i];
686 Count += APINT_BITS_PER_WORD;
688 Count += llvm::countLeadingZeros(V);
692 // Adjust for unused bits in the most significant word (they are zero).
693 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
694 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
698 unsigned APInt::countLeadingOnes() const {
700 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
702 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
705 highWordBits = APINT_BITS_PER_WORD;
708 shift = APINT_BITS_PER_WORD - highWordBits;
710 int i = getNumWords() - 1;
711 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
712 if (Count == highWordBits) {
713 for (i--; i >= 0; --i) {
714 if (pVal[i] == -1ULL)
715 Count += APINT_BITS_PER_WORD;
717 Count += llvm::countLeadingOnes(pVal[i]);
725 unsigned APInt::countTrailingZeros() const {
727 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
730 for (; i < getNumWords() && pVal[i] == 0; ++i)
731 Count += APINT_BITS_PER_WORD;
732 if (i < getNumWords())
733 Count += llvm::countTrailingZeros(pVal[i]);
734 return std::min(Count, BitWidth);
737 unsigned APInt::countTrailingOnesSlowCase() const {
740 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
741 Count += APINT_BITS_PER_WORD;
742 if (i < getNumWords())
743 Count += llvm::countTrailingOnes(pVal[i]);
744 return std::min(Count, BitWidth);
747 unsigned APInt::countPopulationSlowCase() const {
749 for (unsigned i = 0; i < getNumWords(); ++i)
750 Count += llvm::countPopulation(pVal[i]);
754 /// Perform a logical right-shift from Src to Dst, which must be equal or
755 /// non-overlapping, of Words words, by Shift, which must be less than 64.
756 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
759 for (int I = Words - 1; I >= 0; --I) {
760 uint64_t Tmp = Src[I];
761 Dst[I] = (Tmp >> Shift) | Carry;
762 Carry = Tmp << (64 - Shift);
766 APInt APInt::byteSwap() const {
767 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
769 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
771 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
772 if (BitWidth == 48) {
773 unsigned Tmp1 = unsigned(VAL >> 16);
774 Tmp1 = ByteSwap_32(Tmp1);
775 uint16_t Tmp2 = uint16_t(VAL);
776 Tmp2 = ByteSwap_16(Tmp2);
777 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
780 return APInt(BitWidth, ByteSwap_64(VAL));
782 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
783 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
784 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
785 if (Result.BitWidth != BitWidth) {
786 lshrNear(Result.pVal, Result.pVal, getNumWords(),
787 Result.BitWidth - BitWidth);
788 Result.BitWidth = BitWidth;
793 APInt APInt::reverseBits() const {
796 return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
798 return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
800 return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
802 return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
808 APInt Reversed(*this);
809 int S = BitWidth - 1;
811 const APInt One(BitWidth, 1);
813 for ((Val = Val.lshr(1)); Val != 0; (Val = Val.lshr(1))) {
815 Reversed |= (Val & One);
823 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
825 APInt A = API1, B = API2;
828 B = APIntOps::urem(A, B);
834 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
841 // Get the sign bit from the highest order bit
842 bool isNeg = T.I >> 63;
844 // Get the 11-bit exponent and adjust for the 1023 bit bias
845 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
847 // If the exponent is negative, the value is < 0 so just return 0.
849 return APInt(width, 0u);
851 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
852 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
854 // If the exponent doesn't shift all bits out of the mantissa
856 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
857 APInt(width, mantissa >> (52 - exp));
859 // If the client didn't provide enough bits for us to shift the mantissa into
860 // then the result is undefined, just return 0
861 if (width <= exp - 52)
862 return APInt(width, 0);
864 // Otherwise, we have to shift the mantissa bits up to the right location
865 APInt Tmp(width, mantissa);
866 Tmp = Tmp.shl((unsigned)exp - 52);
867 return isNeg ? -Tmp : Tmp;
870 /// This function converts this APInt to a double.
871 /// The layout for double is as following (IEEE Standard 754):
872 /// --------------------------------------
873 /// | Sign Exponent Fraction Bias |
874 /// |-------------------------------------- |
875 /// | 1[63] 11[62-52] 52[51-00] 1023 |
876 /// --------------------------------------
877 double APInt::roundToDouble(bool isSigned) const {
879 // Handle the simple case where the value is contained in one uint64_t.
880 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
881 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
883 int64_t sext = SignExtend64(getWord(0), BitWidth);
886 return double(getWord(0));
889 // Determine if the value is negative.
890 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
892 // Construct the absolute value if we're negative.
893 APInt Tmp(isNeg ? -(*this) : (*this));
895 // Figure out how many bits we're using.
896 unsigned n = Tmp.getActiveBits();
898 // The exponent (without bias normalization) is just the number of bits
899 // we are using. Note that the sign bit is gone since we constructed the
903 // Return infinity for exponent overflow
905 if (!isSigned || !isNeg)
906 return std::numeric_limits<double>::infinity();
908 return -std::numeric_limits<double>::infinity();
910 exp += 1023; // Increment for 1023 bias
912 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
913 // extract the high 52 bits from the correct words in pVal.
915 unsigned hiWord = whichWord(n-1);
917 mantissa = Tmp.pVal[0];
919 mantissa >>= n - 52; // shift down, we want the top 52 bits.
921 assert(hiWord > 0 && "huh?");
922 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
923 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
924 mantissa = hibits | lobits;
927 // The leading bit of mantissa is implicit, so get rid of it.
928 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
933 T.I = sign | (exp << 52) | mantissa;
937 // Truncate to new width.
938 APInt APInt::trunc(unsigned width) const {
939 assert(width < BitWidth && "Invalid APInt Truncate request");
940 assert(width && "Can't truncate to 0 bits");
942 if (width <= APINT_BITS_PER_WORD)
943 return APInt(width, getRawData()[0]);
945 APInt Result(getMemory(getNumWords(width)), width);
949 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
950 Result.pVal[i] = pVal[i];
952 // Truncate and copy any partial word.
953 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
955 Result.pVal[i] = pVal[i] << bits >> bits;
960 // Sign extend to a new width.
961 APInt APInt::sext(unsigned width) const {
962 assert(width > BitWidth && "Invalid APInt SignExtend request");
964 if (width <= APINT_BITS_PER_WORD) {
965 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
966 val = (int64_t)val >> (width - BitWidth);
967 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
970 APInt Result(getMemory(getNumWords(width)), width);
975 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
976 word = getRawData()[i];
977 Result.pVal[i] = word;
980 // Read and sign-extend any partial word.
981 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
983 word = (int64_t)getRawData()[i] << bits >> bits;
985 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
987 // Write remaining full words.
988 for (; i != width / APINT_BITS_PER_WORD; i++) {
989 Result.pVal[i] = word;
990 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
993 // Write any partial word.
994 bits = (0 - width) % APINT_BITS_PER_WORD;
996 Result.pVal[i] = word << bits >> bits;
1001 // Zero extend to a new width.
1002 APInt APInt::zext(unsigned width) const {
1003 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1005 if (width <= APINT_BITS_PER_WORD)
1006 return APInt(width, VAL);
1008 APInt Result(getMemory(getNumWords(width)), width);
1012 for (i = 0; i != getNumWords(); i++)
1013 Result.pVal[i] = getRawData()[i];
1015 // Zero remaining words.
1016 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1021 APInt APInt::zextOrTrunc(unsigned width) const {
1022 if (BitWidth < width)
1024 if (BitWidth > width)
1025 return trunc(width);
1029 APInt APInt::sextOrTrunc(unsigned width) const {
1030 if (BitWidth < width)
1032 if (BitWidth > width)
1033 return trunc(width);
1037 APInt APInt::zextOrSelf(unsigned width) const {
1038 if (BitWidth < width)
1043 APInt APInt::sextOrSelf(unsigned width) const {
1044 if (BitWidth < width)
1049 /// Arithmetic right-shift this APInt by shiftAmt.
1050 /// @brief Arithmetic right-shift function.
1051 APInt APInt::ashr(const APInt &shiftAmt) const {
1052 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1055 /// Arithmetic right-shift this APInt by shiftAmt.
1056 /// @brief Arithmetic right-shift function.
1057 APInt APInt::ashr(unsigned shiftAmt) const {
1058 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1059 // Handle a degenerate case
1063 // Handle single word shifts with built-in ashr
1064 if (isSingleWord()) {
1065 if (shiftAmt == BitWidth)
1066 return APInt(BitWidth, 0); // undefined
1068 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1069 return APInt(BitWidth,
1070 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1074 // If all the bits were shifted out, the result is, technically, undefined.
1075 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1076 // issues in the algorithm below.
1077 if (shiftAmt == BitWidth) {
1079 return APInt(BitWidth, -1ULL, true);
1081 return APInt(BitWidth, 0);
1084 // Create some space for the result.
1085 uint64_t * val = new uint64_t[getNumWords()];
1087 // Compute some values needed by the following shift algorithms
1088 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1089 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1090 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1091 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1092 if (bitsInWord == 0)
1093 bitsInWord = APINT_BITS_PER_WORD;
1095 // If we are shifting whole words, just move whole words
1096 if (wordShift == 0) {
1097 // Move the words containing significant bits
1098 for (unsigned i = 0; i <= breakWord; ++i)
1099 val[i] = pVal[i+offset]; // move whole word
1101 // Adjust the top significant word for sign bit fill, if negative
1103 if (bitsInWord < APINT_BITS_PER_WORD)
1104 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1106 // Shift the low order words
1107 for (unsigned i = 0; i < breakWord; ++i) {
1108 // This combines the shifted corresponding word with the low bits from
1109 // the next word (shifted into this word's high bits).
1110 val[i] = (pVal[i+offset] >> wordShift) |
1111 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1114 // Shift the break word. In this case there are no bits from the next word
1115 // to include in this word.
1116 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1118 // Deal with sign extension in the break word, and possibly the word before
1121 if (wordShift > bitsInWord) {
1124 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1125 val[breakWord] |= ~0ULL;
1127 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1131 // Remaining words are 0 or -1, just assign them.
1132 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1133 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1135 APInt Result(val, BitWidth);
1136 Result.clearUnusedBits();
1140 /// Logical right-shift this APInt by shiftAmt.
1141 /// @brief Logical right-shift function.
1142 APInt APInt::lshr(const APInt &shiftAmt) const {
1143 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1146 /// Logical right-shift this APInt by shiftAmt.
1147 /// @brief Logical right-shift function.
1148 APInt APInt::lshr(unsigned shiftAmt) const {
1149 if (isSingleWord()) {
1150 if (shiftAmt >= BitWidth)
1151 return APInt(BitWidth, 0);
1153 return APInt(BitWidth, this->VAL >> shiftAmt);
1156 // If all the bits were shifted out, the result is 0. This avoids issues
1157 // with shifting by the size of the integer type, which produces undefined
1158 // results. We define these "undefined results" to always be 0.
1159 if (shiftAmt >= BitWidth)
1160 return APInt(BitWidth, 0);
1162 // If none of the bits are shifted out, the result is *this. This avoids
1163 // issues with shifting by the size of the integer type, which produces
1164 // undefined results in the code below. This is also an optimization.
1168 // Create some space for the result.
1169 uint64_t * val = new uint64_t[getNumWords()];
1171 // If we are shifting less than a word, compute the shift with a simple carry
1172 if (shiftAmt < APINT_BITS_PER_WORD) {
1173 lshrNear(val, pVal, getNumWords(), shiftAmt);
1174 APInt Result(val, BitWidth);
1175 Result.clearUnusedBits();
1179 // Compute some values needed by the remaining shift algorithms
1180 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1181 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1183 // If we are shifting whole words, just move whole words
1184 if (wordShift == 0) {
1185 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1186 val[i] = pVal[i+offset];
1187 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1189 APInt Result(val, BitWidth);
1190 Result.clearUnusedBits();
1194 // Shift the low order words
1195 unsigned breakWord = getNumWords() - offset -1;
1196 for (unsigned i = 0; i < breakWord; ++i)
1197 val[i] = (pVal[i+offset] >> wordShift) |
1198 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1199 // Shift the break word.
1200 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1202 // Remaining words are 0
1203 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1205 APInt Result(val, BitWidth);
1206 Result.clearUnusedBits();
1210 /// Left-shift this APInt by shiftAmt.
1211 /// @brief Left-shift function.
1212 APInt APInt::shl(const APInt &shiftAmt) const {
1213 // It's undefined behavior in C to shift by BitWidth or greater.
1214 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1217 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1218 // If all the bits were shifted out, the result is 0. This avoids issues
1219 // with shifting by the size of the integer type, which produces undefined
1220 // results. We define these "undefined results" to always be 0.
1221 if (shiftAmt == BitWidth)
1222 return APInt(BitWidth, 0);
1224 // If none of the bits are shifted out, the result is *this. This avoids a
1225 // lshr by the words size in the loop below which can produce incorrect
1226 // results. It also avoids the expensive computation below for a common case.
1230 // Create some space for the result.
1231 uint64_t * val = new uint64_t[getNumWords()];
1233 // If we are shifting less than a word, do it the easy way
1234 if (shiftAmt < APINT_BITS_PER_WORD) {
1236 for (unsigned i = 0; i < getNumWords(); i++) {
1237 val[i] = pVal[i] << shiftAmt | carry;
1238 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1240 APInt Result(val, BitWidth);
1241 Result.clearUnusedBits();
1245 // Compute some values needed by the remaining shift algorithms
1246 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1247 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1249 // If we are shifting whole words, just move whole words
1250 if (wordShift == 0) {
1251 for (unsigned i = 0; i < offset; i++)
1253 for (unsigned i = offset; i < getNumWords(); i++)
1254 val[i] = pVal[i-offset];
1255 APInt Result(val, BitWidth);
1256 Result.clearUnusedBits();
1260 // Copy whole words from this to Result.
1261 unsigned i = getNumWords() - 1;
1262 for (; i > offset; --i)
1263 val[i] = pVal[i-offset] << wordShift |
1264 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1265 val[offset] = pVal[0] << wordShift;
1266 for (i = 0; i < offset; ++i)
1268 APInt Result(val, BitWidth);
1269 Result.clearUnusedBits();
1273 APInt APInt::rotl(const APInt &rotateAmt) const {
1274 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1277 APInt APInt::rotl(unsigned rotateAmt) const {
1278 rotateAmt %= BitWidth;
1281 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1284 APInt APInt::rotr(const APInt &rotateAmt) const {
1285 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1288 APInt APInt::rotr(unsigned rotateAmt) const {
1289 rotateAmt %= BitWidth;
1292 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1295 // Square Root - this method computes and returns the square root of "this".
1296 // Three mechanisms are used for computation. For small values (<= 5 bits),
1297 // a table lookup is done. This gets some performance for common cases. For
1298 // values using less than 52 bits, the value is converted to double and then
1299 // the libc sqrt function is called. The result is rounded and then converted
1300 // back to a uint64_t which is then used to construct the result. Finally,
1301 // the Babylonian method for computing square roots is used.
1302 APInt APInt::sqrt() const {
1304 // Determine the magnitude of the value.
1305 unsigned magnitude = getActiveBits();
1307 // Use a fast table for some small values. This also gets rid of some
1308 // rounding errors in libc sqrt for small values.
1309 if (magnitude <= 5) {
1310 static const uint8_t results[32] = {
1313 /* 3- 6 */ 2, 2, 2, 2,
1314 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1315 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1316 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1319 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1322 // If the magnitude of the value fits in less than 52 bits (the precision of
1323 // an IEEE double precision floating point value), then we can use the
1324 // libc sqrt function which will probably use a hardware sqrt computation.
1325 // This should be faster than the algorithm below.
1326 if (magnitude < 52) {
1327 return APInt(BitWidth,
1328 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1331 // Okay, all the short cuts are exhausted. We must compute it. The following
1332 // is a classical Babylonian method for computing the square root. This code
1333 // was adapted to APInt from a wikipedia article on such computations.
1334 // See http://www.wikipedia.org/ and go to the page named
1335 // Calculate_an_integer_square_root.
1336 unsigned nbits = BitWidth, i = 4;
1337 APInt testy(BitWidth, 16);
1338 APInt x_old(BitWidth, 1);
1339 APInt x_new(BitWidth, 0);
1340 APInt two(BitWidth, 2);
1342 // Select a good starting value using binary logarithms.
1343 for (;; i += 2, testy = testy.shl(2))
1344 if (i >= nbits || this->ule(testy)) {
1345 x_old = x_old.shl(i / 2);
1349 // Use the Babylonian method to arrive at the integer square root:
1351 x_new = (this->udiv(x_old) + x_old).udiv(two);
1352 if (x_old.ule(x_new))
1357 // Make sure we return the closest approximation
1358 // NOTE: The rounding calculation below is correct. It will produce an
1359 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1360 // determined to be a rounding issue with pari/gp as it begins to use a
1361 // floating point representation after 192 bits. There are no discrepancies
1362 // between this algorithm and pari/gp for bit widths < 192 bits.
1363 APInt square(x_old * x_old);
1364 APInt nextSquare((x_old + 1) * (x_old +1));
1365 if (this->ult(square))
1367 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1368 APInt midpoint((nextSquare - square).udiv(two));
1369 APInt offset(*this - square);
1370 if (offset.ult(midpoint))
1375 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1376 /// iterative extended Euclidean algorithm is used to solve for this value,
1377 /// however we simplify it to speed up calculating only the inverse, and take
1378 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1379 /// (potentially large) APInts around.
1380 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1381 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1383 // Using the properties listed at the following web page (accessed 06/21/08):
1384 // http://www.numbertheory.org/php/euclid.html
1385 // (especially the properties numbered 3, 4 and 9) it can be proved that
1386 // BitWidth bits suffice for all the computations in the algorithm implemented
1387 // below. More precisely, this number of bits suffice if the multiplicative
1388 // inverse exists, but may not suffice for the general extended Euclidean
1391 APInt r[2] = { modulo, *this };
1392 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1393 APInt q(BitWidth, 0);
1396 for (i = 0; r[i^1] != 0; i ^= 1) {
1397 // An overview of the math without the confusing bit-flipping:
1398 // q = r[i-2] / r[i-1]
1399 // r[i] = r[i-2] % r[i-1]
1400 // t[i] = t[i-2] - t[i-1] * q
1401 udivrem(r[i], r[i^1], q, r[i]);
1405 // If this APInt and the modulo are not coprime, there is no multiplicative
1406 // inverse, so return 0. We check this by looking at the next-to-last
1407 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1410 return APInt(BitWidth, 0);
1412 // The next-to-last t is the multiplicative inverse. However, we are
1413 // interested in a positive inverse. Calcuate a positive one from a negative
1414 // one if necessary. A simple addition of the modulo suffices because
1415 // abs(t[i]) is known to be less than *this/2 (see the link above).
1416 return t[i].isNegative() ? t[i] + modulo : t[i];
1419 /// Calculate the magic numbers required to implement a signed integer division
1420 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1421 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1422 /// Warren, Jr., chapter 10.
1423 APInt::ms APInt::magic() const {
1424 const APInt& d = *this;
1426 APInt ad, anc, delta, q1, r1, q2, r2, t;
1427 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1431 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1432 anc = t - 1 - t.urem(ad); // absolute value of nc
1433 p = d.getBitWidth() - 1; // initialize p
1434 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1435 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1436 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1437 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1440 q1 = q1<<1; // update q1 = 2p/abs(nc)
1441 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1442 if (r1.uge(anc)) { // must be unsigned comparison
1446 q2 = q2<<1; // update q2 = 2p/abs(d)
1447 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1448 if (r2.uge(ad)) { // must be unsigned comparison
1453 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1456 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1457 mag.s = p - d.getBitWidth(); // resulting shift
1461 /// Calculate the magic numbers required to implement an unsigned integer
1462 /// division by a constant as a sequence of multiplies, adds and shifts.
1463 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1464 /// S. Warren, Jr., chapter 10.
1465 /// LeadingZeros can be used to simplify the calculation if the upper bits
1466 /// of the divided value are known zero.
1467 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1468 const APInt& d = *this;
1470 APInt nc, delta, q1, r1, q2, r2;
1472 magu.a = 0; // initialize "add" indicator
1473 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1474 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1475 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1477 nc = allOnes - (allOnes - d).urem(d);
1478 p = d.getBitWidth() - 1; // initialize p
1479 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1480 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1481 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1482 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1485 if (r1.uge(nc - r1)) {
1486 q1 = q1 + q1 + 1; // update q1
1487 r1 = r1 + r1 - nc; // update r1
1490 q1 = q1+q1; // update q1
1491 r1 = r1+r1; // update r1
1493 if ((r2 + 1).uge(d - r2)) {
1494 if (q2.uge(signedMax)) magu.a = 1;
1495 q2 = q2+q2 + 1; // update q2
1496 r2 = r2+r2 + 1 - d; // update r2
1499 if (q2.uge(signedMin)) magu.a = 1;
1500 q2 = q2+q2; // update q2
1501 r2 = r2+r2 + 1; // update r2
1504 } while (p < d.getBitWidth()*2 &&
1505 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1506 magu.m = q2 + 1; // resulting magic number
1507 magu.s = p - d.getBitWidth(); // resulting shift
1511 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1512 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1513 /// variables here have the same names as in the algorithm. Comments explain
1514 /// the algorithm and any deviation from it.
1515 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1516 unsigned m, unsigned n) {
1517 assert(u && "Must provide dividend");
1518 assert(v && "Must provide divisor");
1519 assert(q && "Must provide quotient");
1520 assert(u != v && u != q && v != q && "Must use different memory");
1521 assert(n>1 && "n must be > 1");
1523 // b denotes the base of the number system. In our case b is 2^32.
1524 LLVM_CONSTEXPR uint64_t b = uint64_t(1) << 32;
1526 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1527 DEBUG(dbgs() << "KnuthDiv: original:");
1528 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1529 DEBUG(dbgs() << " by");
1530 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1531 DEBUG(dbgs() << '\n');
1532 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1533 // u and v by d. Note that we have taken Knuth's advice here to use a power
1534 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1535 // 2 allows us to shift instead of multiply and it is easy to determine the
1536 // shift amount from the leading zeros. We are basically normalizing the u
1537 // and v so that its high bits are shifted to the top of v's range without
1538 // overflow. Note that this can require an extra word in u so that u must
1539 // be of length m+n+1.
1540 unsigned shift = countLeadingZeros(v[n-1]);
1541 unsigned v_carry = 0;
1542 unsigned u_carry = 0;
1544 for (unsigned i = 0; i < m+n; ++i) {
1545 unsigned u_tmp = u[i] >> (32 - shift);
1546 u[i] = (u[i] << shift) | u_carry;
1549 for (unsigned i = 0; i < n; ++i) {
1550 unsigned v_tmp = v[i] >> (32 - shift);
1551 v[i] = (v[i] << shift) | v_carry;
1557 DEBUG(dbgs() << "KnuthDiv: normal:");
1558 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1559 DEBUG(dbgs() << " by");
1560 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1561 DEBUG(dbgs() << '\n');
1563 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1566 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1567 // D3. [Calculate q'.].
1568 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1569 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1570 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1571 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1572 // on v[n-2] determines at high speed most of the cases in which the trial
1573 // value qp is one too large, and it eliminates all cases where qp is two
1575 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1576 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1577 uint64_t qp = dividend / v[n-1];
1578 uint64_t rp = dividend % v[n-1];
1579 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1582 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1585 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1587 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1588 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1589 // consists of a simple multiplication by a one-place number, combined with
1591 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1592 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1593 // true value plus b**(n+1), namely as the b's complement of
1594 // the true value, and a "borrow" to the left should be remembered.
1596 for (unsigned i = 0; i < n; ++i) {
1597 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1598 int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
1599 u[j+i] = (unsigned)subres;
1600 borrow = (p >> 32) - (subres >> 32);
1601 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
1602 << ", borrow = " << borrow << '\n');
1604 bool isNeg = u[j+n] < borrow;
1605 u[j+n] -= (unsigned)borrow;
1607 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1608 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1609 DEBUG(dbgs() << '\n');
1611 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1612 // negative, go to step D6; otherwise go on to step D7.
1613 q[j] = (unsigned)qp;
1615 // D6. [Add back]. The probability that this step is necessary is very
1616 // small, on the order of only 2/b. Make sure that test data accounts for
1617 // this possibility. Decrease q[j] by 1
1619 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1620 // A carry will occur to the left of u[j+n], and it should be ignored
1621 // since it cancels with the borrow that occurred in D4.
1623 for (unsigned i = 0; i < n; i++) {
1624 unsigned limit = std::min(u[j+i],v[i]);
1625 u[j+i] += v[i] + carry;
1626 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1630 DEBUG(dbgs() << "KnuthDiv: after correction:");
1631 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1632 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1634 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1637 DEBUG(dbgs() << "KnuthDiv: quotient:");
1638 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1639 DEBUG(dbgs() << '\n');
1641 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1642 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1643 // compute the remainder (urem uses this).
1645 // The value d is expressed by the "shift" value above since we avoided
1646 // multiplication by d by using a shift left. So, all we have to do is
1647 // shift right here. In order to mak
1650 DEBUG(dbgs() << "KnuthDiv: remainder:");
1651 for (int i = n-1; i >= 0; i--) {
1652 r[i] = (u[i] >> shift) | carry;
1653 carry = u[i] << (32 - shift);
1654 DEBUG(dbgs() << " " << r[i]);
1657 for (int i = n-1; i >= 0; i--) {
1659 DEBUG(dbgs() << " " << r[i]);
1662 DEBUG(dbgs() << '\n');
1664 DEBUG(dbgs() << '\n');
1667 void APInt::divide(const APInt &LHS, unsigned lhsWords, const APInt &RHS,
1668 unsigned rhsWords, APInt *Quotient, APInt *Remainder) {
1669 assert(lhsWords >= rhsWords && "Fractional result");
1671 // First, compose the values into an array of 32-bit words instead of
1672 // 64-bit words. This is a necessity of both the "short division" algorithm
1673 // and the Knuth "classical algorithm" which requires there to be native
1674 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1675 // can't use 64-bit operands here because we don't have native results of
1676 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1677 // work on large-endian machines.
1678 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1679 unsigned n = rhsWords * 2;
1680 unsigned m = (lhsWords * 2) - n;
1682 // Allocate space for the temporary values we need either on the stack, if
1683 // it will fit, or on the heap if it won't.
1684 unsigned SPACE[128];
1685 unsigned *U = nullptr;
1686 unsigned *V = nullptr;
1687 unsigned *Q = nullptr;
1688 unsigned *R = nullptr;
1689 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1692 Q = &SPACE[(m+n+1) + n];
1694 R = &SPACE[(m+n+1) + n + (m+n)];
1696 U = new unsigned[m + n + 1];
1697 V = new unsigned[n];
1698 Q = new unsigned[m+n];
1700 R = new unsigned[n];
1703 // Initialize the dividend
1704 memset(U, 0, (m+n+1)*sizeof(unsigned));
1705 for (unsigned i = 0; i < lhsWords; ++i) {
1706 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1707 U[i * 2] = (unsigned)(tmp & mask);
1708 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1710 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1712 // Initialize the divisor
1713 memset(V, 0, (n)*sizeof(unsigned));
1714 for (unsigned i = 0; i < rhsWords; ++i) {
1715 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1716 V[i * 2] = (unsigned)(tmp & mask);
1717 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1720 // initialize the quotient and remainder
1721 memset(Q, 0, (m+n) * sizeof(unsigned));
1723 memset(R, 0, n * sizeof(unsigned));
1725 // Now, adjust m and n for the Knuth division. n is the number of words in
1726 // the divisor. m is the number of words by which the dividend exceeds the
1727 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1728 // contain any zero words or the Knuth algorithm fails.
1729 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1733 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1736 // If we're left with only a single word for the divisor, Knuth doesn't work
1737 // so we implement the short division algorithm here. This is much simpler
1738 // and faster because we are certain that we can divide a 64-bit quantity
1739 // by a 32-bit quantity at hardware speed and short division is simply a
1740 // series of such operations. This is just like doing short division but we
1741 // are using base 2^32 instead of base 10.
1742 assert(n != 0 && "Divide by zero?");
1744 unsigned divisor = V[0];
1745 unsigned remainder = 0;
1746 for (int i = m+n-1; i >= 0; i--) {
1747 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1748 if (partial_dividend == 0) {
1751 } else if (partial_dividend < divisor) {
1753 remainder = (unsigned)partial_dividend;
1754 } else if (partial_dividend == divisor) {
1758 Q[i] = (unsigned)(partial_dividend / divisor);
1759 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1765 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1767 KnuthDiv(U, V, Q, R, m, n);
1770 // If the caller wants the quotient
1772 // Set up the Quotient value's memory.
1773 if (Quotient->BitWidth != LHS.BitWidth) {
1774 if (Quotient->isSingleWord())
1777 delete [] Quotient->pVal;
1778 Quotient->BitWidth = LHS.BitWidth;
1779 if (!Quotient->isSingleWord())
1780 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1782 Quotient->clearAllBits();
1784 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1786 // This case is currently dead as all users of divide() handle trivial cases
1788 if (lhsWords == 1) {
1790 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1791 if (Quotient->isSingleWord())
1792 Quotient->VAL = tmp;
1794 Quotient->pVal[0] = tmp;
1796 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1797 for (unsigned i = 0; i < lhsWords; ++i)
1799 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1803 // If the caller wants the remainder
1805 // Set up the Remainder value's memory.
1806 if (Remainder->BitWidth != RHS.BitWidth) {
1807 if (Remainder->isSingleWord())
1810 delete [] Remainder->pVal;
1811 Remainder->BitWidth = RHS.BitWidth;
1812 if (!Remainder->isSingleWord())
1813 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1815 Remainder->clearAllBits();
1817 // The remainder is in R. Reconstitute the remainder into Remainder's low
1819 if (rhsWords == 1) {
1821 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1822 if (Remainder->isSingleWord())
1823 Remainder->VAL = tmp;
1825 Remainder->pVal[0] = tmp;
1827 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1828 for (unsigned i = 0; i < rhsWords; ++i)
1829 Remainder->pVal[i] =
1830 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1834 // Clean up the memory we allocated.
1835 if (U != &SPACE[0]) {
1843 APInt APInt::udiv(const APInt& RHS) const {
1844 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1846 // First, deal with the easy case
1847 if (isSingleWord()) {
1848 assert(RHS.VAL != 0 && "Divide by zero?");
1849 return APInt(BitWidth, VAL / RHS.VAL);
1852 // Get some facts about the LHS and RHS number of bits and words
1853 unsigned rhsBits = RHS.getActiveBits();
1854 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1855 assert(rhsWords && "Divided by zero???");
1856 unsigned lhsBits = this->getActiveBits();
1857 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1859 // Deal with some degenerate cases
1862 return APInt(BitWidth, 0);
1863 else if (lhsWords < rhsWords || this->ult(RHS)) {
1864 // X / Y ===> 0, iff X < Y
1865 return APInt(BitWidth, 0);
1866 } else if (*this == RHS) {
1868 return APInt(BitWidth, 1);
1869 } else if (lhsWords == 1 && rhsWords == 1) {
1870 // All high words are zero, just use native divide
1871 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1874 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1875 APInt Quotient(1,0); // to hold result.
1876 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
1880 APInt APInt::sdiv(const APInt &RHS) const {
1882 if (RHS.isNegative())
1883 return (-(*this)).udiv(-RHS);
1884 return -((-(*this)).udiv(RHS));
1886 if (RHS.isNegative())
1887 return -(this->udiv(-RHS));
1888 return this->udiv(RHS);
1891 APInt APInt::urem(const APInt& RHS) const {
1892 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1893 if (isSingleWord()) {
1894 assert(RHS.VAL != 0 && "Remainder by zero?");
1895 return APInt(BitWidth, VAL % RHS.VAL);
1898 // Get some facts about the LHS
1899 unsigned lhsBits = getActiveBits();
1900 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1902 // Get some facts about the RHS
1903 unsigned rhsBits = RHS.getActiveBits();
1904 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1905 assert(rhsWords && "Performing remainder operation by zero ???");
1907 // Check the degenerate cases
1908 if (lhsWords == 0) {
1910 return APInt(BitWidth, 0);
1911 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1912 // X % Y ===> X, iff X < Y
1914 } else if (*this == RHS) {
1916 return APInt(BitWidth, 0);
1917 } else if (lhsWords == 1) {
1918 // All high words are zero, just use native remainder
1919 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1922 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1923 APInt Remainder(1,0);
1924 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
1928 APInt APInt::srem(const APInt &RHS) const {
1930 if (RHS.isNegative())
1931 return -((-(*this)).urem(-RHS));
1932 return -((-(*this)).urem(RHS));
1934 if (RHS.isNegative())
1935 return this->urem(-RHS);
1936 return this->urem(RHS);
1939 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1940 APInt &Quotient, APInt &Remainder) {
1941 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1943 // First, deal with the easy case
1944 if (LHS.isSingleWord()) {
1945 assert(RHS.VAL != 0 && "Divide by zero?");
1946 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1947 uint64_t RemVal = LHS.VAL % RHS.VAL;
1948 Quotient = APInt(LHS.BitWidth, QuotVal);
1949 Remainder = APInt(LHS.BitWidth, RemVal);
1953 // Get some size facts about the dividend and divisor
1954 unsigned lhsBits = LHS.getActiveBits();
1955 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1956 unsigned rhsBits = RHS.getActiveBits();
1957 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1959 // Check the degenerate cases
1960 if (lhsWords == 0) {
1961 Quotient = 0; // 0 / Y ===> 0
1962 Remainder = 0; // 0 % Y ===> 0
1966 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1967 Remainder = LHS; // X % Y ===> X, iff X < Y
1968 Quotient = 0; // X / Y ===> 0, iff X < Y
1973 Quotient = 1; // X / X ===> 1
1974 Remainder = 0; // X % X ===> 0;
1978 if (lhsWords == 1 && rhsWords == 1) {
1979 // There is only one word to consider so use the native versions.
1980 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1981 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1982 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1983 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1987 // Okay, lets do it the long way
1988 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1991 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1992 APInt &Quotient, APInt &Remainder) {
1993 if (LHS.isNegative()) {
1994 if (RHS.isNegative())
1995 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1997 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1998 Quotient = -Quotient;
2000 Remainder = -Remainder;
2001 } else if (RHS.isNegative()) {
2002 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
2003 Quotient = -Quotient;
2005 APInt::udivrem(LHS, RHS, Quotient, Remainder);
2009 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2010 APInt Res = *this+RHS;
2011 Overflow = isNonNegative() == RHS.isNonNegative() &&
2012 Res.isNonNegative() != isNonNegative();
2016 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2017 APInt Res = *this+RHS;
2018 Overflow = Res.ult(RHS);
2022 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2023 APInt Res = *this - RHS;
2024 Overflow = isNonNegative() != RHS.isNonNegative() &&
2025 Res.isNonNegative() != isNonNegative();
2029 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2030 APInt Res = *this-RHS;
2031 Overflow = Res.ugt(*this);
2035 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2036 // MININT/-1 --> overflow.
2037 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2041 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2042 APInt Res = *this * RHS;
2044 if (*this != 0 && RHS != 0)
2045 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2051 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2052 APInt Res = *this * RHS;
2054 if (*this != 0 && RHS != 0)
2055 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2061 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
2062 Overflow = ShAmt.uge(getBitWidth());
2064 return APInt(BitWidth, 0);
2066 if (isNonNegative()) // Don't allow sign change.
2067 Overflow = ShAmt.uge(countLeadingZeros());
2069 Overflow = ShAmt.uge(countLeadingOnes());
2071 return *this << ShAmt;
2074 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
2075 Overflow = ShAmt.uge(getBitWidth());
2077 return APInt(BitWidth, 0);
2079 Overflow = ShAmt.ugt(countLeadingZeros());
2081 return *this << ShAmt;
2087 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2088 // Check our assumptions here
2089 assert(!str.empty() && "Invalid string length");
2090 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2092 "Radix should be 2, 8, 10, 16, or 36!");
2094 StringRef::iterator p = str.begin();
2095 size_t slen = str.size();
2096 bool isNeg = *p == '-';
2097 if (*p == '-' || *p == '+') {
2100 assert(slen && "String is only a sign, needs a value.");
2102 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2103 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2104 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2105 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2106 "Insufficient bit width");
2109 if (!isSingleWord())
2110 pVal = getClearedMemory(getNumWords());
2112 // Figure out if we can shift instead of multiply
2113 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2115 // Set up an APInt for the digit to add outside the loop so we don't
2116 // constantly construct/destruct it.
2117 APInt apdigit(getBitWidth(), 0);
2118 APInt apradix(getBitWidth(), radix);
2120 // Enter digit traversal loop
2121 for (StringRef::iterator e = str.end(); p != e; ++p) {
2122 unsigned digit = getDigit(*p, radix);
2123 assert(digit < radix && "Invalid character in digit string");
2125 // Shift or multiply the value by the radix
2133 // Add in the digit we just interpreted
2134 if (apdigit.isSingleWord())
2135 apdigit.VAL = digit;
2137 apdigit.pVal[0] = digit;
2140 // If its negative, put it in two's complement form
2143 this->flipAllBits();
2147 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2148 bool Signed, bool formatAsCLiteral) const {
2149 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2151 "Radix should be 2, 8, 10, 16, or 36!");
2153 const char *Prefix = "";
2154 if (formatAsCLiteral) {
2157 // Binary literals are a non-standard extension added in gcc 4.3:
2158 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2170 llvm_unreachable("Invalid radix!");
2174 // First, check for a zero value and just short circuit the logic below.
2177 Str.push_back(*Prefix);
2184 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2186 if (isSingleWord()) {
2188 char *BufPtr = Buffer+65;
2194 int64_t I = getSExtValue();
2204 Str.push_back(*Prefix);
2209 *--BufPtr = Digits[N % Radix];
2212 Str.append(BufPtr, Buffer+65);
2218 if (Signed && isNegative()) {
2219 // They want to print the signed version and it is a negative value
2220 // Flip the bits and add one to turn it into the equivalent positive
2221 // value and put a '-' in the result.
2228 Str.push_back(*Prefix);
2232 // We insert the digits backward, then reverse them to get the right order.
2233 unsigned StartDig = Str.size();
2235 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2236 // because the number of bits per digit (1, 3 and 4 respectively) divides
2237 // equaly. We just shift until the value is zero.
2238 if (Radix == 2 || Radix == 8 || Radix == 16) {
2239 // Just shift tmp right for each digit width until it becomes zero
2240 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2241 unsigned MaskAmt = Radix - 1;
2244 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2245 Str.push_back(Digits[Digit]);
2246 Tmp = Tmp.lshr(ShiftAmt);
2249 APInt divisor(Radix == 10? 4 : 8, Radix);
2251 APInt APdigit(1, 0);
2252 APInt tmp2(Tmp.getBitWidth(), 0);
2253 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2255 unsigned Digit = (unsigned)APdigit.getZExtValue();
2256 assert(Digit < Radix && "divide failed");
2257 Str.push_back(Digits[Digit]);
2262 // Reverse the digits before returning.
2263 std::reverse(Str.begin()+StartDig, Str.end());
2266 /// Returns the APInt as a std::string. Note that this is an inefficient method.
2267 /// It is better to pass in a SmallVector/SmallString to the methods above.
2268 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2270 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2275 LLVM_DUMP_METHOD void APInt::dump() const {
2276 SmallString<40> S, U;
2277 this->toStringUnsigned(U);
2278 this->toStringSigned(S);
2279 dbgs() << "APInt(" << BitWidth << "b, "
2280 << U << "u " << S << "s)";
2283 void APInt::print(raw_ostream &OS, bool isSigned) const {
2285 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2289 // This implements a variety of operations on a representation of
2290 // arbitrary precision, two's-complement, bignum integer values.
2292 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2293 // and unrestricting assumption.
2294 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
2296 /* Some handy functions local to this file. */
2299 /* Returns the integer part with the least significant BITS set.
2300 BITS cannot be zero. */
2301 static inline integerPart
2302 lowBitMask(unsigned int bits)
2304 assert(bits != 0 && bits <= integerPartWidth);
2306 return ~(integerPart) 0 >> (integerPartWidth - bits);
2309 /* Returns the value of the lower half of PART. */
2310 static inline integerPart
2311 lowHalf(integerPart part)
2313 return part & lowBitMask(integerPartWidth / 2);
2316 /* Returns the value of the upper half of PART. */
2317 static inline integerPart
2318 highHalf(integerPart part)
2320 return part >> (integerPartWidth / 2);
2323 /* Returns the bit number of the most significant set bit of a part.
2324 If the input number has no bits set -1U is returned. */
2326 partMSB(integerPart value)
2328 return findLastSet(value, ZB_Max);
2331 /* Returns the bit number of the least significant set bit of a
2332 part. If the input number has no bits set -1U is returned. */
2334 partLSB(integerPart value)
2336 return findFirstSet(value, ZB_Max);
2340 /* Sets the least significant part of a bignum to the input value, and
2341 zeroes out higher parts. */
2343 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2350 for (i = 1; i < parts; i++)
2354 /* Assign one bignum to another. */
2356 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2360 for (i = 0; i < parts; i++)
2364 /* Returns true if a bignum is zero, false otherwise. */
2366 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2370 for (i = 0; i < parts; i++)
2377 /* Extract the given bit of a bignum; returns 0 or 1. */
2379 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2381 return (parts[bit / integerPartWidth] &
2382 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2385 /* Set the given bit of a bignum. */
2387 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2389 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2392 /* Clears the given bit of a bignum. */
2394 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2396 parts[bit / integerPartWidth] &=
2397 ~((integerPart) 1 << (bit % integerPartWidth));
2400 /* Returns the bit number of the least significant set bit of a
2401 number. If the input number has no bits set -1U is returned. */
2403 APInt::tcLSB(const integerPart *parts, unsigned int n)
2405 unsigned int i, lsb;
2407 for (i = 0; i < n; i++) {
2408 if (parts[i] != 0) {
2409 lsb = partLSB(parts[i]);
2411 return lsb + i * integerPartWidth;
2418 /* Returns the bit number of the most significant set bit of a number.
2419 If the input number has no bits set -1U is returned. */
2421 APInt::tcMSB(const integerPart *parts, unsigned int n)
2428 if (parts[n] != 0) {
2429 msb = partMSB(parts[n]);
2431 return msb + n * integerPartWidth;
2438 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2439 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2440 the least significant bit of DST. All high bits above srcBITS in
2441 DST are zero-filled. */
2443 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2444 unsigned int srcBits, unsigned int srcLSB)
2446 unsigned int firstSrcPart, dstParts, shift, n;
2448 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2449 assert(dstParts <= dstCount);
2451 firstSrcPart = srcLSB / integerPartWidth;
2452 tcAssign (dst, src + firstSrcPart, dstParts);
2454 shift = srcLSB % integerPartWidth;
2455 tcShiftRight (dst, dstParts, shift);
2457 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2458 in DST. If this is less that srcBits, append the rest, else
2459 clear the high bits. */
2460 n = dstParts * integerPartWidth - shift;
2462 integerPart mask = lowBitMask (srcBits - n);
2463 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2464 << n % integerPartWidth);
2465 } else if (n > srcBits) {
2466 if (srcBits % integerPartWidth)
2467 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2470 /* Clear high parts. */
2471 while (dstParts < dstCount)
2472 dst[dstParts++] = 0;
2475 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2477 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2478 integerPart c, unsigned int parts)
2484 for (i = 0; i < parts; i++) {
2489 dst[i] += rhs[i] + 1;
2500 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2502 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2503 integerPart c, unsigned int parts)
2509 for (i = 0; i < parts; i++) {
2514 dst[i] -= rhs[i] + 1;
2525 /* Negate a bignum in-place. */
2527 APInt::tcNegate(integerPart *dst, unsigned int parts)
2529 tcComplement(dst, parts);
2530 tcIncrement(dst, parts);
2533 /* DST += SRC * MULTIPLIER + CARRY if add is true
2534 DST = SRC * MULTIPLIER + CARRY if add is false
2536 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2537 they must start at the same point, i.e. DST == SRC.
2539 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2540 returned. Otherwise DST is filled with the least significant
2541 DSTPARTS parts of the result, and if all of the omitted higher
2542 parts were zero return zero, otherwise overflow occurred and
2545 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2546 integerPart multiplier, integerPart carry,
2547 unsigned int srcParts, unsigned int dstParts,
2552 /* Otherwise our writes of DST kill our later reads of SRC. */
2553 assert(dst <= src || dst >= src + srcParts);
2554 assert(dstParts <= srcParts + 1);
2556 /* N loops; minimum of dstParts and srcParts. */
2557 n = dstParts < srcParts ? dstParts: srcParts;
2559 for (i = 0; i < n; i++) {
2560 integerPart low, mid, high, srcPart;
2562 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2564 This cannot overflow, because
2566 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2568 which is less than n^2. */
2572 if (multiplier == 0 || srcPart == 0) {
2576 low = lowHalf(srcPart) * lowHalf(multiplier);
2577 high = highHalf(srcPart) * highHalf(multiplier);
2579 mid = lowHalf(srcPart) * highHalf(multiplier);
2580 high += highHalf(mid);
2581 mid <<= integerPartWidth / 2;
2582 if (low + mid < low)
2586 mid = highHalf(srcPart) * lowHalf(multiplier);
2587 high += highHalf(mid);
2588 mid <<= integerPartWidth / 2;
2589 if (low + mid < low)
2593 /* Now add carry. */
2594 if (low + carry < low)
2600 /* And now DST[i], and store the new low part there. */
2601 if (low + dst[i] < low)
2611 /* Full multiplication, there is no overflow. */
2612 assert(i + 1 == dstParts);
2616 /* We overflowed if there is carry. */
2620 /* We would overflow if any significant unwritten parts would be
2621 non-zero. This is true if any remaining src parts are non-zero
2622 and the multiplier is non-zero. */
2624 for (; i < srcParts; i++)
2628 /* We fitted in the narrow destination. */
2633 /* DST = LHS * RHS, where DST has the same width as the operands and
2634 is filled with the least significant parts of the result. Returns
2635 one if overflow occurred, otherwise zero. DST must be disjoint
2636 from both operands. */
2638 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2639 const integerPart *rhs, unsigned int parts)
2644 assert(dst != lhs && dst != rhs);
2647 tcSet(dst, 0, parts);
2649 for (i = 0; i < parts; i++)
2650 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2656 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2657 operands. No overflow occurs. DST must be disjoint from both
2658 operands. Returns the number of parts required to hold the
2661 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2662 const integerPart *rhs, unsigned int lhsParts,
2663 unsigned int rhsParts)
2665 /* Put the narrower number on the LHS for less loops below. */
2666 if (lhsParts > rhsParts) {
2667 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2671 assert(dst != lhs && dst != rhs);
2673 tcSet(dst, 0, rhsParts);
2675 for (n = 0; n < lhsParts; n++)
2676 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2678 n = lhsParts + rhsParts;
2680 return n - (dst[n - 1] == 0);
2684 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2685 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2686 set REMAINDER to the remainder, return zero. i.e.
2688 OLD_LHS = RHS * LHS + REMAINDER
2690 SCRATCH is a bignum of the same size as the operands and result for
2691 use by the routine; its contents need not be initialized and are
2692 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2695 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2696 integerPart *remainder, integerPart *srhs,
2699 unsigned int n, shiftCount;
2702 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2704 shiftCount = tcMSB(rhs, parts) + 1;
2705 if (shiftCount == 0)
2708 shiftCount = parts * integerPartWidth - shiftCount;
2709 n = shiftCount / integerPartWidth;
2710 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2712 tcAssign(srhs, rhs, parts);
2713 tcShiftLeft(srhs, parts, shiftCount);
2714 tcAssign(remainder, lhs, parts);
2715 tcSet(lhs, 0, parts);
2717 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2722 compare = tcCompare(remainder, srhs, parts);
2724 tcSubtract(remainder, srhs, 0, parts);
2728 if (shiftCount == 0)
2731 tcShiftRight(srhs, parts, 1);
2732 if ((mask >>= 1) == 0) {
2733 mask = (integerPart) 1 << (integerPartWidth - 1);
2741 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2742 There are no restrictions on COUNT. */
2744 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2747 unsigned int jump, shift;
2749 /* Jump is the inter-part jump; shift is is intra-part shift. */
2750 jump = count / integerPartWidth;
2751 shift = count % integerPartWidth;
2753 while (parts > jump) {
2758 /* dst[i] comes from the two parts src[i - jump] and, if we have
2759 an intra-part shift, src[i - jump - 1]. */
2760 part = dst[parts - jump];
2763 if (parts >= jump + 1)
2764 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2775 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2776 zero. There are no restrictions on COUNT. */
2778 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2781 unsigned int i, jump, shift;
2783 /* Jump is the inter-part jump; shift is is intra-part shift. */
2784 jump = count / integerPartWidth;
2785 shift = count % integerPartWidth;
2787 /* Perform the shift. This leaves the most significant COUNT bits
2788 of the result at zero. */
2789 for (i = 0; i < parts; i++) {
2792 if (i + jump >= parts) {
2795 part = dst[i + jump];
2798 if (i + jump + 1 < parts)
2799 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2808 /* Bitwise and of two bignums. */
2810 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2814 for (i = 0; i < parts; i++)
2818 /* Bitwise inclusive or of two bignums. */
2820 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2824 for (i = 0; i < parts; i++)
2828 /* Bitwise exclusive or of two bignums. */
2830 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2834 for (i = 0; i < parts; i++)
2838 /* Complement a bignum in-place. */
2840 APInt::tcComplement(integerPart *dst, unsigned int parts)
2844 for (i = 0; i < parts; i++)
2848 /* Comparison (unsigned) of two bignums. */
2850 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2855 if (lhs[parts] == rhs[parts])
2858 if (lhs[parts] > rhs[parts])
2867 /* Increment a bignum in-place, return the carry flag. */
2869 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2873 for (i = 0; i < parts; i++)
2880 /* Decrement a bignum in-place, return the borrow flag. */
2882 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2883 for (unsigned int i = 0; i < parts; i++) {
2884 // If the current word is non-zero, then the decrement has no effect on the
2885 // higher-order words of the integer and no borrow can occur. Exit early.
2889 // If every word was zero, then there is a borrow.
2894 /* Set the least significant BITS bits of a bignum, clear the
2897 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2903 while (bits > integerPartWidth) {
2904 dst[i++] = ~(integerPart) 0;
2905 bits -= integerPartWidth;
2909 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);