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) {
80 pVal = getClearedMemory(getNumWords());
82 if (isSigned && int64_t(val) < 0)
83 for (unsigned i = 1; i < getNumWords(); ++i)
88 void APInt::initSlowCase(const APInt& that) {
90 pVal = getMemory(getNumWords());
91 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
94 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
95 assert(BitWidth && "Bitwidth too small");
96 assert(bigVal.data() && "Null pointer detected!");
100 // Get memory, cleared to 0
102 pVal = getClearedMemory(getNumWords());
103 // Calculate the number of words to copy
104 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
105 // Copy the words from bigVal to pVal
106 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
108 // Make sure unused high bits are cleared
112 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
113 : BitWidth(numBits) {
114 initFromArray(bigVal);
117 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
118 : BitWidth(numBits) {
119 initFromArray(makeArrayRef(bigVal, numWords));
122 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
123 : VAL(0), BitWidth(numbits) {
124 assert(BitWidth && "Bitwidth too small");
125 fromString(numbits, Str, radix);
128 APInt& APInt::AssignSlowCase(const APInt& RHS) {
129 // Don't do anything for X = X
133 if (BitWidth == RHS.getBitWidth()) {
134 // assume same bit-width single-word case is already handled
135 assert(!isSingleWord());
136 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
140 if (isSingleWord()) {
141 // assume case where both are single words is already handled
142 assert(!RHS.isSingleWord());
144 pVal = getMemory(RHS.getNumWords());
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
146 } else if (getNumWords() == RHS.getNumWords())
147 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
148 else if (RHS.isSingleWord()) {
153 pVal = getMemory(RHS.getNumWords());
154 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
156 BitWidth = RHS.BitWidth;
157 return clearUnusedBits();
160 /// This method 'profiles' an APInt for use with FoldingSet.
161 void APInt::Profile(FoldingSetNodeID& ID) const {
162 ID.AddInteger(BitWidth);
164 if (isSingleWord()) {
169 unsigned NumWords = getNumWords();
170 for (unsigned i = 0; i < NumWords; ++i)
171 ID.AddInteger(pVal[i]);
174 /// @brief Prefix increment operator. Increments the APInt by one.
175 APInt& APInt::operator++() {
179 tcIncrement(pVal, getNumWords());
180 return clearUnusedBits();
183 /// @brief Prefix decrement operator. Decrements the APInt by one.
184 APInt& APInt::operator--() {
188 tcDecrement(pVal, getNumWords());
189 return clearUnusedBits();
192 /// Adds the RHS APint to this APInt.
193 /// @returns this, after addition of RHS.
194 /// @brief Addition assignment operator.
195 APInt& APInt::operator+=(const APInt& RHS) {
196 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
200 tcAdd(pVal, RHS.pVal, 0, getNumWords());
201 return clearUnusedBits();
204 APInt& APInt::operator+=(uint64_t RHS) {
208 tcAddPart(pVal, RHS, getNumWords());
209 return clearUnusedBits();
212 /// Subtracts the RHS APInt from this APInt
213 /// @returns this, after subtraction
214 /// @brief Subtraction assignment operator.
215 APInt& APInt::operator-=(const APInt& RHS) {
216 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
220 tcSubtract(pVal, RHS.pVal, 0, getNumWords());
221 return clearUnusedBits();
224 APInt& APInt::operator-=(uint64_t RHS) {
228 tcSubtractPart(pVal, RHS, getNumWords());
229 return clearUnusedBits();
232 /// Multiplies an integer array, x, by a uint64_t integer and places the result
234 /// @returns the carry out of the multiplication.
235 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
236 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
237 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
238 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
241 // For each digit of x.
242 for (unsigned i = 0; i < len; ++i) {
243 // Split x into high and low words
244 uint64_t lx = x[i] & 0xffffffffULL;
245 uint64_t hx = x[i] >> 32;
246 // hasCarry - A flag to indicate if there is a carry to the next digit.
247 // hasCarry == 0, no carry
248 // hasCarry == 1, has carry
249 // hasCarry == 2, no carry and the calculation result == 0.
250 uint8_t hasCarry = 0;
251 dest[i] = carry + lx * ly;
252 // Determine if the add above introduces carry.
253 hasCarry = (dest[i] < carry) ? 1 : 0;
254 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
255 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
256 // (2^32 - 1) + 2^32 = 2^64.
257 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
259 carry += (lx * hy) & 0xffffffffULL;
260 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
261 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
262 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
267 /// Multiplies integer array x by integer array y and stores the result into
268 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
269 /// @brief Generalized multiplication of integer arrays.
270 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
272 dest[xlen] = mul_1(dest, x, xlen, y[0]);
273 for (unsigned i = 1; i < ylen; ++i) {
274 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
275 uint64_t carry = 0, lx = 0, hx = 0;
276 for (unsigned j = 0; j < xlen; ++j) {
277 lx = x[j] & 0xffffffffULL;
279 // hasCarry - A flag to indicate if has carry.
280 // hasCarry == 0, no carry
281 // hasCarry == 1, has carry
282 // hasCarry == 2, no carry and the calculation result == 0.
283 uint8_t hasCarry = 0;
284 uint64_t resul = carry + lx * ly;
285 hasCarry = (resul < carry) ? 1 : 0;
286 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
287 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
289 carry += (lx * hy) & 0xffffffffULL;
290 resul = (carry << 32) | (resul & 0xffffffffULL);
292 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
293 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
294 ((lx * hy) >> 32) + hx * hy;
296 dest[i+xlen] = carry;
300 APInt& APInt::operator*=(const APInt& RHS) {
301 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
302 if (isSingleWord()) {
308 // Get some bit facts about LHS and check for zero
309 unsigned lhsBits = getActiveBits();
310 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
315 // Get some bit facts about RHS and check for zero
316 unsigned rhsBits = RHS.getActiveBits();
317 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
324 // Allocate space for the result
325 unsigned destWords = rhsWords + lhsWords;
326 uint64_t *dest = getMemory(destWords);
328 // Perform the long multiply
329 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
331 // Copy result back into *this
333 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
334 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
337 // delete dest array and return
342 APInt& APInt::AndAssignSlowCase(const APInt& RHS) {
343 tcAnd(pVal, RHS.pVal, getNumWords());
347 APInt& APInt::OrAssignSlowCase(const APInt& RHS) {
348 tcOr(pVal, RHS.pVal, getNumWords());
352 APInt& APInt::XorAssignSlowCase(const APInt& RHS) {
353 tcXor(pVal, RHS.pVal, getNumWords());
357 APInt APInt::operator*(const APInt& RHS) const {
358 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
360 return APInt(BitWidth, VAL * RHS.VAL);
366 bool APInt::EqualSlowCase(const APInt& RHS) const {
367 return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
370 bool APInt::EqualSlowCase(uint64_t Val) const {
371 unsigned n = getActiveBits();
372 if (n <= APINT_BITS_PER_WORD)
373 return pVal[0] == Val;
378 bool APInt::ult(const APInt& RHS) const {
379 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
381 return VAL < RHS.VAL;
383 // Get active bit length of both operands
384 unsigned n1 = getActiveBits();
385 unsigned n2 = RHS.getActiveBits();
387 // If magnitude of LHS is less than RHS, return true.
391 // If magnitude of RHS is greater than LHS, return false.
395 // If they both fit in a word, just compare the low order word
396 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
397 return pVal[0] < RHS.pVal[0];
399 // Otherwise, compare all words
400 unsigned topWord = whichWord(std::max(n1,n2)-1);
401 for (int i = topWord; i >= 0; --i) {
402 if (pVal[i] > RHS.pVal[i])
404 if (pVal[i] < RHS.pVal[i])
410 bool APInt::slt(const APInt& RHS) const {
411 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
412 if (isSingleWord()) {
413 int64_t lhsSext = SignExtend64(VAL, BitWidth);
414 int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
415 return lhsSext < rhsSext;
418 bool lhsNeg = isNegative();
419 bool rhsNeg = RHS.isNegative();
421 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
422 if (lhsNeg != rhsNeg)
425 // Otherwise we can just use an unsigned comparison, because even negative
426 // numbers compare correctly this way if both have the same signed-ness.
430 void APInt::setBit(unsigned bitPosition) {
432 VAL |= maskBit(bitPosition);
434 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
437 void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
438 unsigned loWord = whichWord(loBit);
439 unsigned hiWord = whichWord(hiBit);
441 // Create an initial mask for the low word with zeros below loBit.
442 uint64_t loMask = UINT64_MAX << whichBit(loBit);
444 // If hiBit is not aligned, we need a high mask.
445 unsigned hiShiftAmt = whichBit(hiBit);
446 if (hiShiftAmt != 0) {
447 // Create a high mask with zeros above hiBit.
448 uint64_t hiMask = UINT64_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
449 // If loWord and hiWord are equal, then we combine the masks. Otherwise,
450 // set the bits in hiWord.
451 if (hiWord == loWord)
454 pVal[hiWord] |= hiMask;
456 // Apply the mask to the low word.
457 pVal[loWord] |= loMask;
459 // Fill any words between loWord and hiWord with all ones.
460 for (unsigned word = loWord + 1; word < hiWord; ++word)
461 pVal[word] = UINT64_MAX;
464 /// Set the given bit to 0 whose position is given as "bitPosition".
465 /// @brief Set a given bit to 0.
466 void APInt::clearBit(unsigned bitPosition) {
468 VAL &= ~maskBit(bitPosition);
470 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
473 /// @brief Toggle every bit to its opposite value.
474 void APInt::flipAllBitsSlowCase() {
475 tcComplement(pVal, getNumWords());
479 /// Toggle a given bit to its opposite value whose position is given
480 /// as "bitPosition".
481 /// @brief Toggles a given bit to its opposite value.
482 void APInt::flipBit(unsigned bitPosition) {
483 assert(bitPosition < BitWidth && "Out of the bit-width range!");
484 if ((*this)[bitPosition]) clearBit(bitPosition);
485 else setBit(bitPosition);
488 void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
489 unsigned subBitWidth = subBits.getBitWidth();
490 assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
491 "Illegal bit insertion");
493 // Insertion is a direct copy.
494 if (subBitWidth == BitWidth) {
499 // Single word result can be done as a direct bitmask.
500 if (isSingleWord()) {
501 uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
502 VAL &= ~(mask << bitPosition);
503 VAL |= (subBits.VAL << bitPosition);
507 unsigned loBit = whichBit(bitPosition);
508 unsigned loWord = whichWord(bitPosition);
509 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
511 // Insertion within a single word can be done as a direct bitmask.
512 if (loWord == hi1Word) {
513 uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
514 pVal[loWord] &= ~(mask << loBit);
515 pVal[loWord] |= (subBits.VAL << loBit);
519 // Insert on word boundaries.
521 // Direct copy whole words.
522 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
523 memcpy(pVal + loWord, subBits.getRawData(),
524 numWholeSubWords * APINT_WORD_SIZE);
526 // Mask+insert remaining bits.
527 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
528 if (remainingBits != 0) {
529 uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - remainingBits);
530 pVal[hi1Word] &= ~mask;
531 pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
536 // General case - set/clear individual bits in dst based on src.
537 // TODO - there is scope for optimization here, but at the moment this code
538 // path is barely used so prefer readability over performance.
539 for (unsigned i = 0; i != subBitWidth; ++i) {
541 setBit(bitPosition + i);
543 clearBit(bitPosition + i);
547 APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
548 assert(numBits > 0 && "Can't extract zero bits");
549 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
550 "Illegal bit extraction");
553 return APInt(numBits, VAL >> bitPosition);
555 unsigned loBit = whichBit(bitPosition);
556 unsigned loWord = whichWord(bitPosition);
557 unsigned hiWord = whichWord(bitPosition + numBits - 1);
559 // Single word result extracting bits from a single word source.
560 if (loWord == hiWord)
561 return APInt(numBits, pVal[loWord] >> loBit);
563 // Extracting bits that start on a source word boundary can be done
564 // as a fast memory copy.
566 return APInt(numBits, makeArrayRef(pVal + loWord, 1 + hiWord - loWord));
568 // General case - shift + copy source words directly into place.
569 APInt Result(numBits, 0);
570 unsigned NumSrcWords = getNumWords();
571 unsigned NumDstWords = Result.getNumWords();
573 for (unsigned word = 0; word < NumDstWords; ++word) {
574 uint64_t w0 = pVal[loWord + word];
576 (loWord + word + 1) < NumSrcWords ? pVal[loWord + word + 1] : 0;
577 Result.pVal[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
580 return Result.clearUnusedBits();
583 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
584 assert(!str.empty() && "Invalid string length");
585 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
587 "Radix should be 2, 8, 10, 16, or 36!");
589 size_t slen = str.size();
591 // Each computation below needs to know if it's negative.
592 StringRef::iterator p = str.begin();
593 unsigned isNegative = *p == '-';
594 if (*p == '-' || *p == '+') {
597 assert(slen && "String is only a sign, needs a value.");
600 // For radixes of power-of-two values, the bits required is accurately and
603 return slen + isNegative;
605 return slen * 3 + isNegative;
607 return slen * 4 + isNegative;
611 // This is grossly inefficient but accurate. We could probably do something
612 // with a computation of roughly slen*64/20 and then adjust by the value of
613 // the first few digits. But, I'm not sure how accurate that could be.
615 // Compute a sufficient number of bits that is always large enough but might
616 // be too large. This avoids the assertion in the constructor. This
617 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
618 // bits in that case.
620 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
621 : (slen == 1 ? 7 : slen * 16/3);
623 // Convert to the actual binary value.
624 APInt tmp(sufficient, StringRef(p, slen), radix);
626 // Compute how many bits are required. If the log is infinite, assume we need
628 unsigned log = tmp.logBase2();
629 if (log == (unsigned)-1) {
630 return isNegative + 1;
632 return isNegative + log + 1;
636 hash_code llvm::hash_value(const APInt &Arg) {
637 if (Arg.isSingleWord())
638 return hash_combine(Arg.VAL);
640 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
643 bool APInt::isSplat(unsigned SplatSizeInBits) const {
644 assert(getBitWidth() % SplatSizeInBits == 0 &&
645 "SplatSizeInBits must divide width!");
646 // We can check that all parts of an integer are equal by making use of a
647 // little trick: rotate and check if it's still the same value.
648 return *this == rotl(SplatSizeInBits);
651 /// This function returns the high "numBits" bits of this APInt.
652 APInt APInt::getHiBits(unsigned numBits) const {
653 return this->lshr(BitWidth - numBits);
656 /// This function returns the low "numBits" bits of this APInt.
657 APInt APInt::getLoBits(unsigned numBits) const {
658 APInt Result(getLowBitsSet(BitWidth, numBits));
663 unsigned APInt::countLeadingZerosSlowCase() const {
665 for (int i = getNumWords()-1; i >= 0; --i) {
666 uint64_t V = pVal[i];
668 Count += APINT_BITS_PER_WORD;
670 Count += llvm::countLeadingZeros(V);
674 // Adjust for unused bits in the most significant word (they are zero).
675 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
676 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
680 unsigned APInt::countLeadingOnes() const {
682 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
684 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
687 highWordBits = APINT_BITS_PER_WORD;
690 shift = APINT_BITS_PER_WORD - highWordBits;
692 int i = getNumWords() - 1;
693 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
694 if (Count == highWordBits) {
695 for (i--; i >= 0; --i) {
696 if (pVal[i] == -1ULL)
697 Count += APINT_BITS_PER_WORD;
699 Count += llvm::countLeadingOnes(pVal[i]);
707 unsigned APInt::countTrailingZeros() const {
709 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
712 for (; i < getNumWords() && pVal[i] == 0; ++i)
713 Count += APINT_BITS_PER_WORD;
714 if (i < getNumWords())
715 Count += llvm::countTrailingZeros(pVal[i]);
716 return std::min(Count, BitWidth);
719 unsigned APInt::countTrailingOnesSlowCase() const {
722 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
723 Count += APINT_BITS_PER_WORD;
724 if (i < getNumWords())
725 Count += llvm::countTrailingOnes(pVal[i]);
726 return std::min(Count, BitWidth);
729 unsigned APInt::countPopulationSlowCase() const {
731 for (unsigned i = 0; i < getNumWords(); ++i)
732 Count += llvm::countPopulation(pVal[i]);
736 APInt APInt::byteSwap() const {
737 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
739 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
741 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
742 if (BitWidth == 48) {
743 unsigned Tmp1 = unsigned(VAL >> 16);
744 Tmp1 = ByteSwap_32(Tmp1);
745 uint16_t Tmp2 = uint16_t(VAL);
746 Tmp2 = ByteSwap_16(Tmp2);
747 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
750 return APInt(BitWidth, ByteSwap_64(VAL));
752 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
753 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
754 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
755 if (Result.BitWidth != BitWidth) {
756 Result.lshrInPlace(Result.BitWidth - BitWidth);
757 Result.BitWidth = BitWidth;
762 APInt APInt::reverseBits() const {
765 return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
767 return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
769 return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
771 return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
777 APInt Reversed(*this);
778 int S = BitWidth - 1;
780 const APInt One(BitWidth, 1);
782 for ((Val = Val.lshr(1)); Val != 0; (Val = Val.lshr(1))) {
784 Reversed |= (Val & One);
792 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
793 // Fast-path a common case.
794 if (A == B) return A;
796 // Corner cases: if either operand is zero, the other is the gcd.
800 // Count common powers of 2 and remove all other powers of 2.
803 unsigned Pow2_A = A.countTrailingZeros();
804 unsigned Pow2_B = B.countTrailingZeros();
805 if (Pow2_A > Pow2_B) {
806 A.lshrInPlace(Pow2_A - Pow2_B);
808 } else if (Pow2_B > Pow2_A) {
809 B.lshrInPlace(Pow2_B - Pow2_A);
816 // Both operands are odd multiples of 2^Pow_2:
818 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
820 // This is a modified version of Stein's algorithm, taking advantage of
821 // efficient countTrailingZeros().
825 A.lshrInPlace(A.countTrailingZeros() - Pow2);
828 B.lshrInPlace(B.countTrailingZeros() - Pow2);
835 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
842 // Get the sign bit from the highest order bit
843 bool isNeg = T.I >> 63;
845 // Get the 11-bit exponent and adjust for the 1023 bit bias
846 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
848 // If the exponent is negative, the value is < 0 so just return 0.
850 return APInt(width, 0u);
852 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
853 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
855 // If the exponent doesn't shift all bits out of the mantissa
857 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
858 APInt(width, mantissa >> (52 - exp));
860 // If the client didn't provide enough bits for us to shift the mantissa into
861 // then the result is undefined, just return 0
862 if (width <= exp - 52)
863 return APInt(width, 0);
865 // Otherwise, we have to shift the mantissa bits up to the right location
866 APInt Tmp(width, mantissa);
867 Tmp = Tmp.shl((unsigned)exp - 52);
868 return isNeg ? -Tmp : Tmp;
871 /// This function converts this APInt to a double.
872 /// The layout for double is as following (IEEE Standard 754):
873 /// --------------------------------------
874 /// | Sign Exponent Fraction Bias |
875 /// |-------------------------------------- |
876 /// | 1[63] 11[62-52] 52[51-00] 1023 |
877 /// --------------------------------------
878 double APInt::roundToDouble(bool isSigned) const {
880 // Handle the simple case where the value is contained in one uint64_t.
881 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
882 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
884 int64_t sext = SignExtend64(getWord(0), BitWidth);
887 return double(getWord(0));
890 // Determine if the value is negative.
891 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
893 // Construct the absolute value if we're negative.
894 APInt Tmp(isNeg ? -(*this) : (*this));
896 // Figure out how many bits we're using.
897 unsigned n = Tmp.getActiveBits();
899 // The exponent (without bias normalization) is just the number of bits
900 // we are using. Note that the sign bit is gone since we constructed the
904 // Return infinity for exponent overflow
906 if (!isSigned || !isNeg)
907 return std::numeric_limits<double>::infinity();
909 return -std::numeric_limits<double>::infinity();
911 exp += 1023; // Increment for 1023 bias
913 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
914 // extract the high 52 bits from the correct words in pVal.
916 unsigned hiWord = whichWord(n-1);
918 mantissa = Tmp.pVal[0];
920 mantissa >>= n - 52; // shift down, we want the top 52 bits.
922 assert(hiWord > 0 && "huh?");
923 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
924 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
925 mantissa = hibits | lobits;
928 // The leading bit of mantissa is implicit, so get rid of it.
929 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
934 T.I = sign | (exp << 52) | mantissa;
938 // Truncate to new width.
939 APInt APInt::trunc(unsigned width) const {
940 assert(width < BitWidth && "Invalid APInt Truncate request");
941 assert(width && "Can't truncate to 0 bits");
943 if (width <= APINT_BITS_PER_WORD)
944 return APInt(width, getRawData()[0]);
946 APInt Result(getMemory(getNumWords(width)), width);
950 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
951 Result.pVal[i] = pVal[i];
953 // Truncate and copy any partial word.
954 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
956 Result.pVal[i] = pVal[i] << bits >> bits;
961 // Sign extend to a new width.
962 APInt APInt::sext(unsigned width) const {
963 assert(width > BitWidth && "Invalid APInt SignExtend request");
965 if (width <= APINT_BITS_PER_WORD) {
966 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
967 val = (int64_t)val >> (width - BitWidth);
968 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
971 APInt Result(getMemory(getNumWords(width)), width);
976 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
977 word = getRawData()[i];
978 Result.pVal[i] = word;
981 // Read and sign-extend any partial word.
982 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
984 word = (int64_t)getRawData()[i] << bits >> bits;
986 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
988 // Write remaining full words.
989 for (; i != width / APINT_BITS_PER_WORD; i++) {
990 Result.pVal[i] = word;
991 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
994 // Write any partial word.
995 bits = (0 - width) % APINT_BITS_PER_WORD;
997 Result.pVal[i] = word << bits >> bits;
1002 // Zero extend to a new width.
1003 APInt APInt::zext(unsigned width) const {
1004 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1006 if (width <= APINT_BITS_PER_WORD)
1007 return APInt(width, VAL);
1009 APInt Result(getMemory(getNumWords(width)), width);
1013 for (i = 0; i != getNumWords(); i++)
1014 Result.pVal[i] = getRawData()[i];
1016 // Zero remaining words.
1017 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1022 APInt APInt::zextOrTrunc(unsigned width) const {
1023 if (BitWidth < width)
1025 if (BitWidth > width)
1026 return trunc(width);
1030 APInt APInt::sextOrTrunc(unsigned width) const {
1031 if (BitWidth < width)
1033 if (BitWidth > width)
1034 return trunc(width);
1038 APInt APInt::zextOrSelf(unsigned width) const {
1039 if (BitWidth < width)
1044 APInt APInt::sextOrSelf(unsigned width) const {
1045 if (BitWidth < width)
1050 /// Arithmetic right-shift this APInt by shiftAmt.
1051 /// @brief Arithmetic right-shift function.
1052 APInt APInt::ashr(const APInt &shiftAmt) const {
1053 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1056 /// Arithmetic right-shift this APInt by shiftAmt.
1057 /// @brief Arithmetic right-shift function.
1058 APInt APInt::ashr(unsigned shiftAmt) const {
1059 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1060 // Handle a degenerate case
1064 // Handle single word shifts with built-in ashr
1065 if (isSingleWord()) {
1066 if (shiftAmt == BitWidth)
1067 return APInt(BitWidth, 0); // undefined
1068 return APInt(BitWidth, SignExtend64(VAL, BitWidth) >> shiftAmt);
1071 // If all the bits were shifted out, the result is, technically, undefined.
1072 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1073 // issues in the algorithm below.
1074 if (shiftAmt == BitWidth) {
1076 return APInt(BitWidth, -1ULL, true);
1078 return APInt(BitWidth, 0);
1081 // Create some space for the result.
1082 uint64_t * val = new uint64_t[getNumWords()];
1084 // Compute some values needed by the following shift algorithms
1085 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1086 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1087 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1088 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1089 if (bitsInWord == 0)
1090 bitsInWord = APINT_BITS_PER_WORD;
1092 // If we are shifting whole words, just move whole words
1093 if (wordShift == 0) {
1094 // Move the words containing significant bits
1095 for (unsigned i = 0; i <= breakWord; ++i)
1096 val[i] = pVal[i+offset]; // move whole word
1098 // Adjust the top significant word for sign bit fill, if negative
1100 if (bitsInWord < APINT_BITS_PER_WORD)
1101 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1103 // Shift the low order words
1104 for (unsigned i = 0; i < breakWord; ++i) {
1105 // This combines the shifted corresponding word with the low bits from
1106 // the next word (shifted into this word's high bits).
1107 val[i] = (pVal[i+offset] >> wordShift) |
1108 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1111 // Shift the break word. In this case there are no bits from the next word
1112 // to include in this word.
1113 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1115 // Deal with sign extension in the break word, and possibly the word before
1118 if (wordShift > bitsInWord) {
1121 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1122 val[breakWord] |= ~0ULL;
1124 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1128 // Remaining words are 0 or -1, just assign them.
1129 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1130 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1132 APInt Result(val, BitWidth);
1133 Result.clearUnusedBits();
1137 /// Logical right-shift this APInt by shiftAmt.
1138 /// @brief Logical right-shift function.
1139 APInt APInt::lshr(const APInt &shiftAmt) const {
1140 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1143 /// Perform a logical right-shift from Src to Dst of Words words, by Shift,
1144 /// which must be less than 64. If the source and destination ranges overlap,
1145 /// we require that Src >= Dst (put another way, we require that the overall
1146 /// operation is a right shift on the combined range).
1147 static void lshrWords(APInt::WordType *Dst, APInt::WordType *Src,
1148 unsigned Words, unsigned Shift) {
1149 assert(Shift < APInt::APINT_BITS_PER_WORD);
1155 std::memmove(Dst, Src, Words * APInt::APINT_WORD_SIZE);
1159 uint64_t Low = Src[0];
1160 for (unsigned I = 1; I != Words; ++I) {
1161 uint64_t High = Src[I];
1163 (Low >> Shift) | (High << (APInt::APINT_BITS_PER_WORD - Shift));
1166 Dst[Words - 1] = Low >> Shift;
1169 /// Logical right-shift this APInt by shiftAmt.
1170 /// @brief Logical right-shift function.
1171 void APInt::lshrInPlace(unsigned shiftAmt) {
1172 if (isSingleWord()) {
1173 if (shiftAmt >= BitWidth)
1180 // Don't bother performing a no-op shift.
1184 // Find number of complete words being shifted out and zeroed.
1185 const unsigned Words = getNumWords();
1186 const unsigned ShiftFullWords =
1187 std::min(shiftAmt / APINT_BITS_PER_WORD, Words);
1189 // Fill in first Words - ShiftFullWords by shifting.
1190 lshrWords(pVal, pVal + ShiftFullWords, Words - ShiftFullWords,
1191 shiftAmt % APINT_BITS_PER_WORD);
1193 // The remaining high words are all zero.
1194 for (unsigned I = Words - ShiftFullWords; I != Words; ++I)
1198 /// Left-shift this APInt by shiftAmt.
1199 /// @brief Left-shift function.
1200 APInt APInt::shl(const APInt &shiftAmt) const {
1201 // It's undefined behavior in C to shift by BitWidth or greater.
1202 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1205 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1206 // If all the bits were shifted out, the result is 0. This avoids issues
1207 // with shifting by the size of the integer type, which produces undefined
1208 // results. We define these "undefined results" to always be 0.
1209 if (shiftAmt == BitWidth)
1210 return APInt(BitWidth, 0);
1212 // If none of the bits are shifted out, the result is *this. This avoids a
1213 // lshr by the words size in the loop below which can produce incorrect
1214 // results. It also avoids the expensive computation below for a common case.
1218 // Create some space for the result.
1219 uint64_t * val = new uint64_t[getNumWords()];
1221 // If we are shifting less than a word, do it the easy way
1222 if (shiftAmt < APINT_BITS_PER_WORD) {
1224 for (unsigned i = 0; i < getNumWords(); i++) {
1225 val[i] = pVal[i] << shiftAmt | carry;
1226 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1228 APInt Result(val, BitWidth);
1229 Result.clearUnusedBits();
1233 // Compute some values needed by the remaining shift algorithms
1234 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1235 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1237 // If we are shifting whole words, just move whole words
1238 if (wordShift == 0) {
1239 for (unsigned i = 0; i < offset; i++)
1241 for (unsigned i = offset; i < getNumWords(); i++)
1242 val[i] = pVal[i-offset];
1243 APInt Result(val, BitWidth);
1244 Result.clearUnusedBits();
1248 // Copy whole words from this to Result.
1249 unsigned i = getNumWords() - 1;
1250 for (; i > offset; --i)
1251 val[i] = pVal[i-offset] << wordShift |
1252 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1253 val[offset] = pVal[0] << wordShift;
1254 for (i = 0; i < offset; ++i)
1256 APInt Result(val, BitWidth);
1257 Result.clearUnusedBits();
1261 // Calculate the rotate amount modulo the bit width.
1262 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
1263 unsigned rotBitWidth = rotateAmt.getBitWidth();
1264 APInt rot = rotateAmt;
1265 if (rotBitWidth < BitWidth) {
1266 // Extend the rotate APInt, so that the urem doesn't divide by 0.
1267 // e.g. APInt(1, 32) would give APInt(1, 0).
1268 rot = rotateAmt.zext(BitWidth);
1270 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
1271 return rot.getLimitedValue(BitWidth);
1274 APInt APInt::rotl(const APInt &rotateAmt) const {
1275 return rotl(rotateModulo(BitWidth, rotateAmt));
1278 APInt APInt::rotl(unsigned rotateAmt) const {
1279 rotateAmt %= BitWidth;
1282 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1285 APInt APInt::rotr(const APInt &rotateAmt) const {
1286 return rotr(rotateModulo(BitWidth, rotateAmt));
1289 APInt APInt::rotr(unsigned rotateAmt) const {
1290 rotateAmt %= BitWidth;
1293 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1296 // Square Root - this method computes and returns the square root of "this".
1297 // Three mechanisms are used for computation. For small values (<= 5 bits),
1298 // a table lookup is done. This gets some performance for common cases. For
1299 // values using less than 52 bits, the value is converted to double and then
1300 // the libc sqrt function is called. The result is rounded and then converted
1301 // back to a uint64_t which is then used to construct the result. Finally,
1302 // the Babylonian method for computing square roots is used.
1303 APInt APInt::sqrt() const {
1305 // Determine the magnitude of the value.
1306 unsigned magnitude = getActiveBits();
1308 // Use a fast table for some small values. This also gets rid of some
1309 // rounding errors in libc sqrt for small values.
1310 if (magnitude <= 5) {
1311 static const uint8_t results[32] = {
1314 /* 3- 6 */ 2, 2, 2, 2,
1315 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1316 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1317 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1320 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1323 // If the magnitude of the value fits in less than 52 bits (the precision of
1324 // an IEEE double precision floating point value), then we can use the
1325 // libc sqrt function which will probably use a hardware sqrt computation.
1326 // This should be faster than the algorithm below.
1327 if (magnitude < 52) {
1328 return APInt(BitWidth,
1329 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1332 // Okay, all the short cuts are exhausted. We must compute it. The following
1333 // is a classical Babylonian method for computing the square root. This code
1334 // was adapted to APInt from a wikipedia article on such computations.
1335 // See http://www.wikipedia.org/ and go to the page named
1336 // Calculate_an_integer_square_root.
1337 unsigned nbits = BitWidth, i = 4;
1338 APInt testy(BitWidth, 16);
1339 APInt x_old(BitWidth, 1);
1340 APInt x_new(BitWidth, 0);
1341 APInt two(BitWidth, 2);
1343 // Select a good starting value using binary logarithms.
1344 for (;; i += 2, testy = testy.shl(2))
1345 if (i >= nbits || this->ule(testy)) {
1346 x_old = x_old.shl(i / 2);
1350 // Use the Babylonian method to arrive at the integer square root:
1352 x_new = (this->udiv(x_old) + x_old).udiv(two);
1353 if (x_old.ule(x_new))
1358 // Make sure we return the closest approximation
1359 // NOTE: The rounding calculation below is correct. It will produce an
1360 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1361 // determined to be a rounding issue with pari/gp as it begins to use a
1362 // floating point representation after 192 bits. There are no discrepancies
1363 // between this algorithm and pari/gp for bit widths < 192 bits.
1364 APInt square(x_old * x_old);
1365 APInt nextSquare((x_old + 1) * (x_old +1));
1366 if (this->ult(square))
1368 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1369 APInt midpoint((nextSquare - square).udiv(two));
1370 APInt offset(*this - square);
1371 if (offset.ult(midpoint))
1376 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1377 /// iterative extended Euclidean algorithm is used to solve for this value,
1378 /// however we simplify it to speed up calculating only the inverse, and take
1379 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1380 /// (potentially large) APInts around.
1381 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1382 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1384 // Using the properties listed at the following web page (accessed 06/21/08):
1385 // http://www.numbertheory.org/php/euclid.html
1386 // (especially the properties numbered 3, 4 and 9) it can be proved that
1387 // BitWidth bits suffice for all the computations in the algorithm implemented
1388 // below. More precisely, this number of bits suffice if the multiplicative
1389 // inverse exists, but may not suffice for the general extended Euclidean
1392 APInt r[2] = { modulo, *this };
1393 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1394 APInt q(BitWidth, 0);
1397 for (i = 0; r[i^1] != 0; i ^= 1) {
1398 // An overview of the math without the confusing bit-flipping:
1399 // q = r[i-2] / r[i-1]
1400 // r[i] = r[i-2] % r[i-1]
1401 // t[i] = t[i-2] - t[i-1] * q
1402 udivrem(r[i], r[i^1], q, r[i]);
1406 // If this APInt and the modulo are not coprime, there is no multiplicative
1407 // inverse, so return 0. We check this by looking at the next-to-last
1408 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1411 return APInt(BitWidth, 0);
1413 // The next-to-last t is the multiplicative inverse. However, we are
1414 // interested in a positive inverse. Calcuate a positive one from a negative
1415 // one if necessary. A simple addition of the modulo suffices because
1416 // abs(t[i]) is known to be less than *this/2 (see the link above).
1417 return t[i].isNegative() ? t[i] + modulo : t[i];
1420 /// Calculate the magic numbers required to implement a signed integer division
1421 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1422 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1423 /// Warren, Jr., chapter 10.
1424 APInt::ms APInt::magic() const {
1425 const APInt& d = *this;
1427 APInt ad, anc, delta, q1, r1, q2, r2, t;
1428 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1432 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1433 anc = t - 1 - t.urem(ad); // absolute value of nc
1434 p = d.getBitWidth() - 1; // initialize p
1435 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1436 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1437 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1438 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1441 q1 = q1<<1; // update q1 = 2p/abs(nc)
1442 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1443 if (r1.uge(anc)) { // must be unsigned comparison
1447 q2 = q2<<1; // update q2 = 2p/abs(d)
1448 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1449 if (r2.uge(ad)) { // must be unsigned comparison
1454 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1457 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1458 mag.s = p - d.getBitWidth(); // resulting shift
1462 /// Calculate the magic numbers required to implement an unsigned integer
1463 /// division by a constant as a sequence of multiplies, adds and shifts.
1464 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1465 /// S. Warren, Jr., chapter 10.
1466 /// LeadingZeros can be used to simplify the calculation if the upper bits
1467 /// of the divided value are known zero.
1468 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1469 const APInt& d = *this;
1471 APInt nc, delta, q1, r1, q2, r2;
1473 magu.a = 0; // initialize "add" indicator
1474 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1475 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1476 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1478 nc = allOnes - (allOnes - d).urem(d);
1479 p = d.getBitWidth() - 1; // initialize p
1480 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1481 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1482 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1483 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1486 if (r1.uge(nc - r1)) {
1487 q1 = q1 + q1 + 1; // update q1
1488 r1 = r1 + r1 - nc; // update r1
1491 q1 = q1+q1; // update q1
1492 r1 = r1+r1; // update r1
1494 if ((r2 + 1).uge(d - r2)) {
1495 if (q2.uge(signedMax)) magu.a = 1;
1496 q2 = q2+q2 + 1; // update q2
1497 r2 = r2+r2 + 1 - d; // update r2
1500 if (q2.uge(signedMin)) magu.a = 1;
1501 q2 = q2+q2; // update q2
1502 r2 = r2+r2 + 1; // update r2
1505 } while (p < d.getBitWidth()*2 &&
1506 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1507 magu.m = q2 + 1; // resulting magic number
1508 magu.s = p - d.getBitWidth(); // resulting shift
1512 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1513 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1514 /// variables here have the same names as in the algorithm. Comments explain
1515 /// the algorithm and any deviation from it.
1516 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1517 unsigned m, unsigned n) {
1518 assert(u && "Must provide dividend");
1519 assert(v && "Must provide divisor");
1520 assert(q && "Must provide quotient");
1521 assert(u != v && u != q && v != q && "Must use different memory");
1522 assert(n>1 && "n must be > 1");
1524 // b denotes the base of the number system. In our case b is 2^32.
1525 const uint64_t b = uint64_t(1) << 32;
1527 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1528 DEBUG(dbgs() << "KnuthDiv: original:");
1529 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1530 DEBUG(dbgs() << " by");
1531 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1532 DEBUG(dbgs() << '\n');
1533 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1534 // u and v by d. Note that we have taken Knuth's advice here to use a power
1535 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1536 // 2 allows us to shift instead of multiply and it is easy to determine the
1537 // shift amount from the leading zeros. We are basically normalizing the u
1538 // and v so that its high bits are shifted to the top of v's range without
1539 // overflow. Note that this can require an extra word in u so that u must
1540 // be of length m+n+1.
1541 unsigned shift = countLeadingZeros(v[n-1]);
1542 unsigned v_carry = 0;
1543 unsigned u_carry = 0;
1545 for (unsigned i = 0; i < m+n; ++i) {
1546 unsigned u_tmp = u[i] >> (32 - shift);
1547 u[i] = (u[i] << shift) | u_carry;
1550 for (unsigned i = 0; i < n; ++i) {
1551 unsigned v_tmp = v[i] >> (32 - shift);
1552 v[i] = (v[i] << shift) | v_carry;
1558 DEBUG(dbgs() << "KnuthDiv: normal:");
1559 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1560 DEBUG(dbgs() << " by");
1561 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1562 DEBUG(dbgs() << '\n');
1564 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1567 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1568 // D3. [Calculate q'.].
1569 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1570 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1571 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1572 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1573 // on v[n-2] determines at high speed most of the cases in which the trial
1574 // value qp is one too large, and it eliminates all cases where qp is two
1576 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1577 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1578 uint64_t qp = dividend / v[n-1];
1579 uint64_t rp = dividend % v[n-1];
1580 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1583 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1586 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1588 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1589 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1590 // consists of a simple multiplication by a one-place number, combined with
1592 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1593 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1594 // true value plus b**(n+1), namely as the b's complement of
1595 // the true value, and a "borrow" to the left should be remembered.
1597 for (unsigned i = 0; i < n; ++i) {
1598 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1599 int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
1600 u[j+i] = (unsigned)subres;
1601 borrow = (p >> 32) - (subres >> 32);
1602 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
1603 << ", borrow = " << borrow << '\n');
1605 bool isNeg = u[j+n] < borrow;
1606 u[j+n] -= (unsigned)borrow;
1608 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1609 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1610 DEBUG(dbgs() << '\n');
1612 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1613 // negative, go to step D6; otherwise go on to step D7.
1614 q[j] = (unsigned)qp;
1616 // D6. [Add back]. The probability that this step is necessary is very
1617 // small, on the order of only 2/b. Make sure that test data accounts for
1618 // this possibility. Decrease q[j] by 1
1620 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1621 // A carry will occur to the left of u[j+n], and it should be ignored
1622 // since it cancels with the borrow that occurred in D4.
1624 for (unsigned i = 0; i < n; i++) {
1625 unsigned limit = std::min(u[j+i],v[i]);
1626 u[j+i] += v[i] + carry;
1627 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1631 DEBUG(dbgs() << "KnuthDiv: after correction:");
1632 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1633 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1635 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1638 DEBUG(dbgs() << "KnuthDiv: quotient:");
1639 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1640 DEBUG(dbgs() << '\n');
1642 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1643 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1644 // compute the remainder (urem uses this).
1646 // The value d is expressed by the "shift" value above since we avoided
1647 // multiplication by d by using a shift left. So, all we have to do is
1648 // shift right here.
1651 DEBUG(dbgs() << "KnuthDiv: remainder:");
1652 for (int i = n-1; i >= 0; i--) {
1653 r[i] = (u[i] >> shift) | carry;
1654 carry = u[i] << (32 - shift);
1655 DEBUG(dbgs() << " " << r[i]);
1658 for (int i = n-1; i >= 0; i--) {
1660 DEBUG(dbgs() << " " << r[i]);
1663 DEBUG(dbgs() << '\n');
1665 DEBUG(dbgs() << '\n');
1668 void APInt::divide(const APInt &LHS, unsigned lhsWords, const APInt &RHS,
1669 unsigned rhsWords, APInt *Quotient, APInt *Remainder) {
1670 assert(lhsWords >= rhsWords && "Fractional result");
1672 // First, compose the values into an array of 32-bit words instead of
1673 // 64-bit words. This is a necessity of both the "short division" algorithm
1674 // and the Knuth "classical algorithm" which requires there to be native
1675 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1676 // can't use 64-bit operands here because we don't have native results of
1677 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1678 // work on large-endian machines.
1679 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1680 unsigned n = rhsWords * 2;
1681 unsigned m = (lhsWords * 2) - n;
1683 // Allocate space for the temporary values we need either on the stack, if
1684 // it will fit, or on the heap if it won't.
1685 unsigned SPACE[128];
1686 unsigned *U = nullptr;
1687 unsigned *V = nullptr;
1688 unsigned *Q = nullptr;
1689 unsigned *R = nullptr;
1690 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1693 Q = &SPACE[(m+n+1) + n];
1695 R = &SPACE[(m+n+1) + n + (m+n)];
1697 U = new unsigned[m + n + 1];
1698 V = new unsigned[n];
1699 Q = new unsigned[m+n];
1701 R = new unsigned[n];
1704 // Initialize the dividend
1705 memset(U, 0, (m+n+1)*sizeof(unsigned));
1706 for (unsigned i = 0; i < lhsWords; ++i) {
1707 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1708 U[i * 2] = (unsigned)(tmp & mask);
1709 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1711 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1713 // Initialize the divisor
1714 memset(V, 0, (n)*sizeof(unsigned));
1715 for (unsigned i = 0; i < rhsWords; ++i) {
1716 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1717 V[i * 2] = (unsigned)(tmp & mask);
1718 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1721 // initialize the quotient and remainder
1722 memset(Q, 0, (m+n) * sizeof(unsigned));
1724 memset(R, 0, n * sizeof(unsigned));
1726 // Now, adjust m and n for the Knuth division. n is the number of words in
1727 // the divisor. m is the number of words by which the dividend exceeds the
1728 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1729 // contain any zero words or the Knuth algorithm fails.
1730 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1734 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1737 // If we're left with only a single word for the divisor, Knuth doesn't work
1738 // so we implement the short division algorithm here. This is much simpler
1739 // and faster because we are certain that we can divide a 64-bit quantity
1740 // by a 32-bit quantity at hardware speed and short division is simply a
1741 // series of such operations. This is just like doing short division but we
1742 // are using base 2^32 instead of base 10.
1743 assert(n != 0 && "Divide by zero?");
1745 unsigned divisor = V[0];
1746 unsigned remainder = 0;
1747 for (int i = m+n-1; i >= 0; i--) {
1748 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1749 if (partial_dividend == 0) {
1752 } else if (partial_dividend < divisor) {
1754 remainder = (unsigned)partial_dividend;
1755 } else if (partial_dividend == divisor) {
1759 Q[i] = (unsigned)(partial_dividend / divisor);
1760 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1766 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1768 KnuthDiv(U, V, Q, R, m, n);
1771 // If the caller wants the quotient
1773 // Set up the Quotient value's memory.
1774 if (Quotient->BitWidth != LHS.BitWidth) {
1775 if (Quotient->isSingleWord())
1778 delete [] Quotient->pVal;
1779 Quotient->BitWidth = LHS.BitWidth;
1780 if (!Quotient->isSingleWord())
1781 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1783 Quotient->clearAllBits();
1785 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1787 // This case is currently dead as all users of divide() handle trivial cases
1789 if (lhsWords == 1) {
1791 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1792 if (Quotient->isSingleWord())
1793 Quotient->VAL = tmp;
1795 Quotient->pVal[0] = tmp;
1797 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1798 for (unsigned i = 0; i < lhsWords; ++i)
1800 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1804 // If the caller wants the remainder
1806 // Set up the Remainder value's memory.
1807 if (Remainder->BitWidth != RHS.BitWidth) {
1808 if (Remainder->isSingleWord())
1811 delete [] Remainder->pVal;
1812 Remainder->BitWidth = RHS.BitWidth;
1813 if (!Remainder->isSingleWord())
1814 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1816 Remainder->clearAllBits();
1818 // The remainder is in R. Reconstitute the remainder into Remainder's low
1820 if (rhsWords == 1) {
1822 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1823 if (Remainder->isSingleWord())
1824 Remainder->VAL = tmp;
1826 Remainder->pVal[0] = tmp;
1828 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1829 for (unsigned i = 0; i < rhsWords; ++i)
1830 Remainder->pVal[i] =
1831 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1835 // Clean up the memory we allocated.
1836 if (U != &SPACE[0]) {
1844 APInt APInt::udiv(const APInt& RHS) const {
1845 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1847 // First, deal with the easy case
1848 if (isSingleWord()) {
1849 assert(RHS.VAL != 0 && "Divide by zero?");
1850 return APInt(BitWidth, VAL / RHS.VAL);
1853 // Get some facts about the LHS and RHS number of bits and words
1854 unsigned rhsBits = RHS.getActiveBits();
1855 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1856 assert(rhsWords && "Divided by zero???");
1857 unsigned lhsBits = this->getActiveBits();
1858 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1860 // Deal with some degenerate cases
1863 return APInt(BitWidth, 0);
1864 else if (lhsWords < rhsWords || this->ult(RHS)) {
1865 // X / Y ===> 0, iff X < Y
1866 return APInt(BitWidth, 0);
1867 } else if (*this == RHS) {
1869 return APInt(BitWidth, 1);
1870 } else if (lhsWords == 1 && rhsWords == 1) {
1871 // All high words are zero, just use native divide
1872 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1875 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1876 APInt Quotient(1,0); // to hold result.
1877 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
1881 APInt APInt::sdiv(const APInt &RHS) const {
1883 if (RHS.isNegative())
1884 return (-(*this)).udiv(-RHS);
1885 return -((-(*this)).udiv(RHS));
1887 if (RHS.isNegative())
1888 return -(this->udiv(-RHS));
1889 return this->udiv(RHS);
1892 APInt APInt::urem(const APInt& RHS) const {
1893 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1894 if (isSingleWord()) {
1895 assert(RHS.VAL != 0 && "Remainder by zero?");
1896 return APInt(BitWidth, VAL % RHS.VAL);
1899 // Get some facts about the LHS
1900 unsigned lhsBits = getActiveBits();
1901 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1903 // Get some facts about the RHS
1904 unsigned rhsBits = RHS.getActiveBits();
1905 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1906 assert(rhsWords && "Performing remainder operation by zero ???");
1908 // Check the degenerate cases
1909 if (lhsWords == 0) {
1911 return APInt(BitWidth, 0);
1912 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1913 // X % Y ===> X, iff X < Y
1915 } else if (*this == RHS) {
1917 return APInt(BitWidth, 0);
1918 } else if (lhsWords == 1) {
1919 // All high words are zero, just use native remainder
1920 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1923 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1924 APInt Remainder(1,0);
1925 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
1929 APInt APInt::srem(const APInt &RHS) const {
1931 if (RHS.isNegative())
1932 return -((-(*this)).urem(-RHS));
1933 return -((-(*this)).urem(RHS));
1935 if (RHS.isNegative())
1936 return this->urem(-RHS);
1937 return this->urem(RHS);
1940 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1941 APInt &Quotient, APInt &Remainder) {
1942 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1944 // First, deal with the easy case
1945 if (LHS.isSingleWord()) {
1946 assert(RHS.VAL != 0 && "Divide by zero?");
1947 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1948 uint64_t RemVal = LHS.VAL % RHS.VAL;
1949 Quotient = APInt(LHS.BitWidth, QuotVal);
1950 Remainder = APInt(LHS.BitWidth, RemVal);
1954 // Get some size facts about the dividend and divisor
1955 unsigned lhsBits = LHS.getActiveBits();
1956 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1957 unsigned rhsBits = RHS.getActiveBits();
1958 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1960 // Check the degenerate cases
1961 if (lhsWords == 0) {
1962 Quotient = 0; // 0 / Y ===> 0
1963 Remainder = 0; // 0 % Y ===> 0
1967 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1968 Remainder = LHS; // X % Y ===> X, iff X < Y
1969 Quotient = 0; // X / Y ===> 0, iff X < Y
1974 Quotient = 1; // X / X ===> 1
1975 Remainder = 0; // X % X ===> 0;
1979 if (lhsWords == 1 && rhsWords == 1) {
1980 // There is only one word to consider so use the native versions.
1981 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1982 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1983 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1984 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1988 // Okay, lets do it the long way
1989 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1992 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1993 APInt &Quotient, APInt &Remainder) {
1994 if (LHS.isNegative()) {
1995 if (RHS.isNegative())
1996 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1998 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1999 Quotient = -Quotient;
2001 Remainder = -Remainder;
2002 } else if (RHS.isNegative()) {
2003 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
2004 Quotient = -Quotient;
2006 APInt::udivrem(LHS, RHS, Quotient, Remainder);
2010 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2011 APInt Res = *this+RHS;
2012 Overflow = isNonNegative() == RHS.isNonNegative() &&
2013 Res.isNonNegative() != isNonNegative();
2017 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2018 APInt Res = *this+RHS;
2019 Overflow = Res.ult(RHS);
2023 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2024 APInt Res = *this - RHS;
2025 Overflow = isNonNegative() != RHS.isNonNegative() &&
2026 Res.isNonNegative() != isNonNegative();
2030 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2031 APInt Res = *this-RHS;
2032 Overflow = Res.ugt(*this);
2036 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2037 // MININT/-1 --> overflow.
2038 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2042 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2043 APInt Res = *this * RHS;
2045 if (*this != 0 && RHS != 0)
2046 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2052 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2053 APInt Res = *this * RHS;
2055 if (*this != 0 && RHS != 0)
2056 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2062 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
2063 Overflow = ShAmt.uge(getBitWidth());
2065 return APInt(BitWidth, 0);
2067 if (isNonNegative()) // Don't allow sign change.
2068 Overflow = ShAmt.uge(countLeadingZeros());
2070 Overflow = ShAmt.uge(countLeadingOnes());
2072 return *this << ShAmt;
2075 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
2076 Overflow = ShAmt.uge(getBitWidth());
2078 return APInt(BitWidth, 0);
2080 Overflow = ShAmt.ugt(countLeadingZeros());
2082 return *this << ShAmt;
2088 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2089 // Check our assumptions here
2090 assert(!str.empty() && "Invalid string length");
2091 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2093 "Radix should be 2, 8, 10, 16, or 36!");
2095 StringRef::iterator p = str.begin();
2096 size_t slen = str.size();
2097 bool isNeg = *p == '-';
2098 if (*p == '-' || *p == '+') {
2101 assert(slen && "String is only a sign, needs a value.");
2103 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2104 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2105 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2106 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2107 "Insufficient bit width");
2110 if (!isSingleWord())
2111 pVal = getClearedMemory(getNumWords());
2113 // Figure out if we can shift instead of multiply
2114 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2116 // Set up an APInt for the radix multiplier outside the loop so we don't
2117 // constantly construct/destruct it.
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
2136 // If its negative, put it in two's complement form
2139 this->flipAllBits();
2143 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2144 bool Signed, bool formatAsCLiteral) const {
2145 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2147 "Radix should be 2, 8, 10, 16, or 36!");
2149 const char *Prefix = "";
2150 if (formatAsCLiteral) {
2153 // Binary literals are a non-standard extension added in gcc 4.3:
2154 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2166 llvm_unreachable("Invalid radix!");
2170 // First, check for a zero value and just short circuit the logic below.
2173 Str.push_back(*Prefix);
2180 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2182 if (isSingleWord()) {
2184 char *BufPtr = Buffer+65;
2190 int64_t I = getSExtValue();
2200 Str.push_back(*Prefix);
2205 *--BufPtr = Digits[N % Radix];
2208 Str.append(BufPtr, Buffer+65);
2214 if (Signed && isNegative()) {
2215 // They want to print the signed version and it is a negative value
2216 // Flip the bits and add one to turn it into the equivalent positive
2217 // value and put a '-' in the result.
2224 Str.push_back(*Prefix);
2228 // We insert the digits backward, then reverse them to get the right order.
2229 unsigned StartDig = Str.size();
2231 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2232 // because the number of bits per digit (1, 3 and 4 respectively) divides
2233 // equally. We just shift until the value is zero.
2234 if (Radix == 2 || Radix == 8 || Radix == 16) {
2235 // Just shift tmp right for each digit width until it becomes zero
2236 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2237 unsigned MaskAmt = Radix - 1;
2240 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2241 Str.push_back(Digits[Digit]);
2242 Tmp = Tmp.lshr(ShiftAmt);
2245 APInt divisor(Radix == 10? 4 : 8, Radix);
2247 APInt APdigit(1, 0);
2248 APInt tmp2(Tmp.getBitWidth(), 0);
2249 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2251 unsigned Digit = (unsigned)APdigit.getZExtValue();
2252 assert(Digit < Radix && "divide failed");
2253 Str.push_back(Digits[Digit]);
2258 // Reverse the digits before returning.
2259 std::reverse(Str.begin()+StartDig, Str.end());
2262 /// Returns the APInt as a std::string. Note that this is an inefficient method.
2263 /// It is better to pass in a SmallVector/SmallString to the methods above.
2264 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2266 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2270 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2271 LLVM_DUMP_METHOD void APInt::dump() const {
2272 SmallString<40> S, U;
2273 this->toStringUnsigned(U);
2274 this->toStringSigned(S);
2275 dbgs() << "APInt(" << BitWidth << "b, "
2276 << U << "u " << S << "s)\n";
2280 void APInt::print(raw_ostream &OS, bool isSigned) const {
2282 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2286 // This implements a variety of operations on a representation of
2287 // arbitrary precision, two's-complement, bignum integer values.
2289 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2290 // and unrestricting assumption.
2291 static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2292 "Part width must be divisible by 2!");
2294 /* Some handy functions local to this file. */
2296 /* Returns the integer part with the least significant BITS set.
2297 BITS cannot be zero. */
2298 static inline APInt::WordType lowBitMask(unsigned bits) {
2299 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
2301 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2304 /* Returns the value of the lower half of PART. */
2305 static inline APInt::WordType lowHalf(APInt::WordType part) {
2306 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2309 /* Returns the value of the upper half of PART. */
2310 static inline APInt::WordType highHalf(APInt::WordType part) {
2311 return part >> (APInt::APINT_BITS_PER_WORD / 2);
2314 /* Returns the bit number of the most significant set bit of a part.
2315 If the input number has no bits set -1U is returned. */
2316 static unsigned partMSB(APInt::WordType value) {
2317 return findLastSet(value, ZB_Max);
2320 /* Returns the bit number of the least significant set bit of a
2321 part. If the input number has no bits set -1U is returned. */
2322 static unsigned partLSB(APInt::WordType value) {
2323 return findFirstSet(value, ZB_Max);
2326 /* Sets the least significant part of a bignum to the input value, and
2327 zeroes out higher parts. */
2328 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
2332 for (unsigned i = 1; i < parts; i++)
2336 /* Assign one bignum to another. */
2337 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
2338 for (unsigned i = 0; i < parts; i++)
2342 /* Returns true if a bignum is zero, false otherwise. */
2343 bool APInt::tcIsZero(const WordType *src, unsigned parts) {
2344 for (unsigned i = 0; i < parts; i++)
2351 /* Extract the given bit of a bignum; returns 0 or 1. */
2352 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
2353 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2356 /* Set the given bit of a bignum. */
2357 void APInt::tcSetBit(WordType *parts, unsigned bit) {
2358 parts[whichWord(bit)] |= maskBit(bit);
2361 /* Clears the given bit of a bignum. */
2362 void APInt::tcClearBit(WordType *parts, unsigned bit) {
2363 parts[whichWord(bit)] &= ~maskBit(bit);
2366 /* Returns the bit number of the least significant set bit of a
2367 number. If the input number has no bits set -1U is returned. */
2368 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
2369 for (unsigned i = 0; i < n; i++) {
2370 if (parts[i] != 0) {
2371 unsigned lsb = partLSB(parts[i]);
2373 return lsb + i * APINT_BITS_PER_WORD;
2380 /* Returns the bit number of the most significant set bit of a number.
2381 If the input number has no bits set -1U is returned. */
2382 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
2386 if (parts[n] != 0) {
2387 unsigned msb = partMSB(parts[n]);
2389 return msb + n * APINT_BITS_PER_WORD;
2396 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2397 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2398 the least significant bit of DST. All high bits above srcBITS in
2399 DST are zero-filled. */
2401 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
2402 unsigned srcBits, unsigned srcLSB) {
2403 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
2404 assert(dstParts <= dstCount);
2406 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
2407 tcAssign (dst, src + firstSrcPart, dstParts);
2409 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
2410 tcShiftRight (dst, dstParts, shift);
2412 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
2413 in DST. If this is less that srcBits, append the rest, else
2414 clear the high bits. */
2415 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
2417 WordType mask = lowBitMask (srcBits - n);
2418 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2419 << n % APINT_BITS_PER_WORD);
2420 } else if (n > srcBits) {
2421 if (srcBits % APINT_BITS_PER_WORD)
2422 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
2425 /* Clear high parts. */
2426 while (dstParts < dstCount)
2427 dst[dstParts++] = 0;
2430 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2431 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2432 WordType c, unsigned parts) {
2435 for (unsigned i = 0; i < parts; i++) {
2436 WordType l = dst[i];
2438 dst[i] += rhs[i] + 1;
2449 /// This function adds a single "word" integer, src, to the multiple
2450 /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2451 /// 1 is returned if there is a carry out, otherwise 0 is returned.
2452 /// @returns the carry of the addition.
2453 APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2455 for (unsigned i = 0; i < parts; ++i) {
2458 return 0; // No need to carry so exit early.
2459 src = 1; // Carry one to next digit.
2465 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2466 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2467 WordType c, unsigned parts) {
2470 for (unsigned i = 0; i < parts; i++) {
2471 WordType l = dst[i];
2473 dst[i] -= rhs[i] + 1;
2484 /// This function subtracts a single "word" (64-bit word), src, from
2485 /// the multi-word integer array, dst[], propagating the borrowed 1 value until
2486 /// no further borrowing is needed or it runs out of "words" in dst. The result
2487 /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2488 /// exhausted. In other words, if src > dst then this function returns 1,
2490 /// @returns the borrow out of the subtraction
2491 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2493 for (unsigned i = 0; i < parts; ++i) {
2494 WordType Dst = dst[i];
2497 return 0; // No need to borrow so exit early.
2498 src = 1; // We have to "borrow 1" from next "word"
2504 /* Negate a bignum in-place. */
2505 void APInt::tcNegate(WordType *dst, unsigned parts) {
2506 tcComplement(dst, parts);
2507 tcIncrement(dst, parts);
2510 /* DST += SRC * MULTIPLIER + CARRY if add is true
2511 DST = SRC * MULTIPLIER + CARRY if add is false
2513 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2514 they must start at the same point, i.e. DST == SRC.
2516 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2517 returned. Otherwise DST is filled with the least significant
2518 DSTPARTS parts of the result, and if all of the omitted higher
2519 parts were zero return zero, otherwise overflow occurred and
2521 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2522 WordType multiplier, WordType carry,
2523 unsigned srcParts, unsigned dstParts,
2525 /* Otherwise our writes of DST kill our later reads of SRC. */
2526 assert(dst <= src || dst >= src + srcParts);
2527 assert(dstParts <= srcParts + 1);
2529 /* N loops; minimum of dstParts and srcParts. */
2530 unsigned n = dstParts < srcParts ? dstParts: srcParts;
2533 for (i = 0; i < n; i++) {
2534 WordType low, mid, high, srcPart;
2536 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2538 This cannot overflow, because
2540 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2542 which is less than n^2. */
2546 if (multiplier == 0 || srcPart == 0) {
2550 low = lowHalf(srcPart) * lowHalf(multiplier);
2551 high = highHalf(srcPart) * highHalf(multiplier);
2553 mid = lowHalf(srcPart) * highHalf(multiplier);
2554 high += highHalf(mid);
2555 mid <<= APINT_BITS_PER_WORD / 2;
2556 if (low + mid < low)
2560 mid = highHalf(srcPart) * lowHalf(multiplier);
2561 high += highHalf(mid);
2562 mid <<= APINT_BITS_PER_WORD / 2;
2563 if (low + mid < low)
2567 /* Now add carry. */
2568 if (low + carry < low)
2574 /* And now DST[i], and store the new low part there. */
2575 if (low + dst[i] < low)
2585 /* Full multiplication, there is no overflow. */
2586 assert(i + 1 == dstParts);
2590 /* We overflowed if there is carry. */
2594 /* We would overflow if any significant unwritten parts would be
2595 non-zero. This is true if any remaining src parts are non-zero
2596 and the multiplier is non-zero. */
2598 for (; i < srcParts; i++)
2602 /* We fitted in the narrow destination. */
2607 /* DST = LHS * RHS, where DST has the same width as the operands and
2608 is filled with the least significant parts of the result. Returns
2609 one if overflow occurred, otherwise zero. DST must be disjoint
2610 from both operands. */
2611 int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2612 const WordType *rhs, unsigned parts) {
2613 assert(dst != lhs && dst != rhs);
2616 tcSet(dst, 0, parts);
2618 for (unsigned i = 0; i < parts; i++)
2619 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2625 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2626 operands. No overflow occurs. DST must be disjoint from both
2627 operands. Returns the number of parts required to hold the
2629 unsigned APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2630 const WordType *rhs, unsigned lhsParts,
2631 unsigned rhsParts) {
2632 /* Put the narrower number on the LHS for less loops below. */
2633 if (lhsParts > rhsParts) {
2634 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2636 assert(dst != lhs && dst != rhs);
2638 tcSet(dst, 0, rhsParts);
2640 for (unsigned i = 0; i < lhsParts; i++)
2641 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2643 unsigned n = lhsParts + rhsParts;
2645 return n - (dst[n - 1] == 0);
2649 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2650 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2651 set REMAINDER to the remainder, return zero. i.e.
2653 OLD_LHS = RHS * LHS + REMAINDER
2655 SCRATCH is a bignum of the same size as the operands and result for
2656 use by the routine; its contents need not be initialized and are
2657 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2659 int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2660 WordType *remainder, WordType *srhs,
2662 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2664 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2665 if (shiftCount == 0)
2668 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2669 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2670 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
2672 tcAssign(srhs, rhs, parts);
2673 tcShiftLeft(srhs, parts, shiftCount);
2674 tcAssign(remainder, lhs, parts);
2675 tcSet(lhs, 0, parts);
2677 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2682 compare = tcCompare(remainder, srhs, parts);
2684 tcSubtract(remainder, srhs, 0, parts);
2688 if (shiftCount == 0)
2691 tcShiftRight(srhs, parts, 1);
2692 if ((mask >>= 1) == 0) {
2693 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
2701 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2702 There are no restrictions on COUNT. */
2703 void APInt::tcShiftLeft(WordType *dst, unsigned parts, unsigned count) {
2705 /* Jump is the inter-part jump; shift is is intra-part shift. */
2706 unsigned jump = count / APINT_BITS_PER_WORD;
2707 unsigned shift = count % APINT_BITS_PER_WORD;
2709 while (parts > jump) {
2714 /* dst[i] comes from the two parts src[i - jump] and, if we have
2715 an intra-part shift, src[i - jump - 1]. */
2716 part = dst[parts - jump];
2719 if (parts >= jump + 1)
2720 part |= dst[parts - jump - 1] >> (APINT_BITS_PER_WORD - shift);
2731 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2732 zero. There are no restrictions on COUNT. */
2733 void APInt::tcShiftRight(WordType *dst, unsigned parts, unsigned count) {
2735 /* Jump is the inter-part jump; shift is is intra-part shift. */
2736 unsigned jump = count / APINT_BITS_PER_WORD;
2737 unsigned shift = count % APINT_BITS_PER_WORD;
2739 /* Perform the shift. This leaves the most significant COUNT bits
2740 of the result at zero. */
2741 for (unsigned i = 0; i < parts; i++) {
2744 if (i + jump >= parts) {
2747 part = dst[i + jump];
2750 if (i + jump + 1 < parts)
2751 part |= dst[i + jump + 1] << (APINT_BITS_PER_WORD - shift);
2760 /* Bitwise and of two bignums. */
2761 void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
2762 for (unsigned i = 0; i < parts; i++)
2766 /* Bitwise inclusive or of two bignums. */
2767 void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
2768 for (unsigned i = 0; i < parts; i++)
2772 /* Bitwise exclusive or of two bignums. */
2773 void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
2774 for (unsigned i = 0; i < parts; i++)
2778 /* Complement a bignum in-place. */
2779 void APInt::tcComplement(WordType *dst, unsigned parts) {
2780 for (unsigned i = 0; i < parts; i++)
2784 /* Comparison (unsigned) of two bignums. */
2785 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
2789 if (lhs[parts] == rhs[parts])
2792 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2798 /* Set the least significant BITS bits of a bignum, clear the
2800 void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
2803 while (bits > APINT_BITS_PER_WORD) {
2804 dst[i++] = ~(WordType) 0;
2805 bits -= APINT_BITS_PER_WORD;
2809 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);