1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/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 /// A utility function for allocating memory, checking for allocation failures,
32 /// and ensuring the contents are zeroed.
33 inline static uint64_t* getClearedMemory(unsigned numWords) {
34 uint64_t * result = new uint64_t[numWords];
35 assert(result && "APInt memory allocation fails!");
36 memset(result, 0, numWords * sizeof(uint64_t));
40 /// A utility function for allocating memory and checking for allocation
41 /// failure. The content is not zeroed.
42 inline static uint64_t* getMemory(unsigned numWords) {
43 uint64_t * result = new uint64_t[numWords];
44 assert(result && "APInt memory allocation fails!");
48 /// A utility function that converts a character to a digit.
49 inline static unsigned getDigit(char cdigit, uint8_t radix) {
52 if (radix == 16 || radix == 36) {
76 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
77 pVal = getClearedMemory(getNumWords());
79 if (isSigned && int64_t(val) < 0)
80 for (unsigned i = 1; i < getNumWords(); ++i)
84 void APInt::initSlowCase(const APInt& that) {
85 pVal = getMemory(getNumWords());
86 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
89 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
90 assert(BitWidth && "Bitwidth too small");
91 assert(bigVal.data() && "Null pointer detected!");
95 // Get memory, cleared to 0
96 pVal = getClearedMemory(getNumWords());
97 // Calculate the number of words to copy
98 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
99 // Copy the words from bigVal to pVal
100 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
102 // Make sure unused high bits are cleared
106 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
107 : BitWidth(numBits), VAL(0) {
108 initFromArray(bigVal);
111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
112 : BitWidth(numBits), VAL(0) {
113 initFromArray(makeArrayRef(bigVal, numWords));
116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
117 : BitWidth(numbits), VAL(0) {
118 assert(BitWidth && "Bitwidth too small");
119 fromString(numbits, Str, radix);
122 APInt& APInt::AssignSlowCase(const APInt& RHS) {
123 // Don't do anything for X = X
127 if (BitWidth == RHS.getBitWidth()) {
128 // assume same bit-width single-word case is already handled
129 assert(!isSingleWord());
130 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
134 if (isSingleWord()) {
135 // assume case where both are single words is already handled
136 assert(!RHS.isSingleWord());
138 pVal = getMemory(RHS.getNumWords());
139 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
140 } else if (getNumWords() == RHS.getNumWords())
141 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
142 else if (RHS.isSingleWord()) {
147 pVal = getMemory(RHS.getNumWords());
148 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
150 BitWidth = RHS.BitWidth;
151 return clearUnusedBits();
154 APInt& APInt::operator=(uint64_t RHS) {
159 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
161 return clearUnusedBits();
164 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
165 void APInt::Profile(FoldingSetNodeID& ID) const {
166 ID.AddInteger(BitWidth);
168 if (isSingleWord()) {
173 unsigned NumWords = getNumWords();
174 for (unsigned i = 0; i < NumWords; ++i)
175 ID.AddInteger(pVal[i]);
178 /// add_1 - This function adds a single "digit" integer, y, to the multiple
179 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
180 /// 1 is returned if there is a carry out, otherwise 0 is returned.
181 /// @returns the carry of the addition.
182 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
183 for (unsigned i = 0; i < len; ++i) {
186 y = 1; // Carry one to next digit.
188 y = 0; // No need to carry so exit early
195 /// @brief Prefix increment operator. Increments the APInt by one.
196 APInt& APInt::operator++() {
200 add_1(pVal, pVal, getNumWords(), 1);
201 return clearUnusedBits();
204 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
205 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
206 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
207 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
208 /// In other words, if y > x then this function returns 1, otherwise 0.
209 /// @returns the borrow out of the subtraction
210 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
211 for (unsigned i = 0; i < len; ++i) {
215 y = 1; // We have to "borrow 1" from next "digit"
217 y = 0; // No need to borrow
218 break; // Remaining digits are unchanged so exit early
224 /// @brief Prefix decrement operator. Decrements the APInt by one.
225 APInt& APInt::operator--() {
229 sub_1(pVal, getNumWords(), 1);
230 return clearUnusedBits();
233 /// add - This function adds the integer array x to the integer array Y and
234 /// places the result in dest.
235 /// @returns the carry out from the addition
236 /// @brief General addition of 64-bit integer arrays
237 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
240 for (unsigned i = 0; i< len; ++i) {
241 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
242 dest[i] = x[i] + y[i] + carry;
243 carry = dest[i] < limit || (carry && dest[i] == limit);
248 /// Adds the RHS APint to this APInt.
249 /// @returns this, after addition of RHS.
250 /// @brief Addition assignment operator.
251 APInt& APInt::operator+=(const APInt& RHS) {
252 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
256 add(pVal, pVal, RHS.pVal, getNumWords());
258 return clearUnusedBits();
261 /// Subtracts the integer array y from the integer array x
262 /// @returns returns the borrow out.
263 /// @brief Generalized subtraction of 64-bit integer arrays.
264 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
267 for (unsigned i = 0; i < len; ++i) {
268 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
269 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
270 dest[i] = x_tmp - y[i];
275 /// Subtracts the RHS APInt from this APInt
276 /// @returns this, after subtraction
277 /// @brief Subtraction assignment operator.
278 APInt& APInt::operator-=(const APInt& RHS) {
279 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
283 sub(pVal, pVal, RHS.pVal, getNumWords());
284 return clearUnusedBits();
287 /// Multiplies an integer array, x, by a uint64_t integer and places the result
289 /// @returns the carry out of the multiplication.
290 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
291 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
292 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
293 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
296 // For each digit of x.
297 for (unsigned i = 0; i < len; ++i) {
298 // Split x into high and low words
299 uint64_t lx = x[i] & 0xffffffffULL;
300 uint64_t hx = x[i] >> 32;
301 // hasCarry - A flag to indicate if there is a carry to the next digit.
302 // hasCarry == 0, no carry
303 // hasCarry == 1, has carry
304 // hasCarry == 2, no carry and the calculation result == 0.
305 uint8_t hasCarry = 0;
306 dest[i] = carry + lx * ly;
307 // Determine if the add above introduces carry.
308 hasCarry = (dest[i] < carry) ? 1 : 0;
309 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
310 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
311 // (2^32 - 1) + 2^32 = 2^64.
312 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
314 carry += (lx * hy) & 0xffffffffULL;
315 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
316 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
317 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
322 /// Multiplies integer array x by integer array y and stores the result into
323 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
324 /// @brief Generalized multiplicate of integer arrays.
325 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
327 dest[xlen] = mul_1(dest, x, xlen, y[0]);
328 for (unsigned i = 1; i < ylen; ++i) {
329 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
330 uint64_t carry = 0, lx = 0, hx = 0;
331 for (unsigned j = 0; j < xlen; ++j) {
332 lx = x[j] & 0xffffffffULL;
334 // hasCarry - A flag to indicate if has carry.
335 // hasCarry == 0, no carry
336 // hasCarry == 1, has carry
337 // hasCarry == 2, no carry and the calculation result == 0.
338 uint8_t hasCarry = 0;
339 uint64_t resul = carry + lx * ly;
340 hasCarry = (resul < carry) ? 1 : 0;
341 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
342 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
344 carry += (lx * hy) & 0xffffffffULL;
345 resul = (carry << 32) | (resul & 0xffffffffULL);
347 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
348 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
349 ((lx * hy) >> 32) + hx * hy;
351 dest[i+xlen] = carry;
355 APInt& APInt::operator*=(const APInt& RHS) {
356 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
357 if (isSingleWord()) {
363 // Get some bit facts about LHS and check for zero
364 unsigned lhsBits = getActiveBits();
365 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
370 // Get some bit facts about RHS and check for zero
371 unsigned rhsBits = RHS.getActiveBits();
372 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
379 // Allocate space for the result
380 unsigned destWords = rhsWords + lhsWords;
381 uint64_t *dest = getMemory(destWords);
383 // Perform the long multiply
384 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
386 // Copy result back into *this
388 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
389 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
392 // delete dest array and return
397 APInt& APInt::operator&=(const APInt& RHS) {
398 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
399 if (isSingleWord()) {
403 unsigned numWords = getNumWords();
404 for (unsigned i = 0; i < numWords; ++i)
405 pVal[i] &= RHS.pVal[i];
409 APInt& APInt::operator|=(const APInt& RHS) {
410 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
411 if (isSingleWord()) {
415 unsigned numWords = getNumWords();
416 for (unsigned i = 0; i < numWords; ++i)
417 pVal[i] |= RHS.pVal[i];
421 APInt& APInt::operator^=(const APInt& RHS) {
422 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
423 if (isSingleWord()) {
425 this->clearUnusedBits();
428 unsigned numWords = getNumWords();
429 for (unsigned i = 0; i < numWords; ++i)
430 pVal[i] ^= RHS.pVal[i];
431 return clearUnusedBits();
434 APInt APInt::AndSlowCase(const APInt& RHS) const {
435 unsigned numWords = getNumWords();
436 uint64_t* val = getMemory(numWords);
437 for (unsigned i = 0; i < numWords; ++i)
438 val[i] = pVal[i] & RHS.pVal[i];
439 return APInt(val, getBitWidth());
442 APInt APInt::OrSlowCase(const APInt& RHS) const {
443 unsigned numWords = getNumWords();
444 uint64_t *val = getMemory(numWords);
445 for (unsigned i = 0; i < numWords; ++i)
446 val[i] = pVal[i] | RHS.pVal[i];
447 return APInt(val, getBitWidth());
450 APInt APInt::XorSlowCase(const APInt& RHS) const {
451 unsigned numWords = getNumWords();
452 uint64_t *val = getMemory(numWords);
453 for (unsigned i = 0; i < numWords; ++i)
454 val[i] = pVal[i] ^ RHS.pVal[i];
456 // 0^0==1 so clear the high bits in case they got set.
457 return APInt(val, getBitWidth()).clearUnusedBits();
460 APInt APInt::operator*(const APInt& RHS) const {
461 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
463 return APInt(BitWidth, VAL * RHS.VAL);
469 APInt APInt::operator+(const APInt& RHS) const {
470 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
472 return APInt(BitWidth, VAL + RHS.VAL);
473 APInt Result(BitWidth, 0);
474 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
475 return Result.clearUnusedBits();
478 APInt APInt::operator-(const APInt& RHS) const {
479 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
481 return APInt(BitWidth, VAL - RHS.VAL);
482 APInt Result(BitWidth, 0);
483 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
484 return Result.clearUnusedBits();
487 bool APInt::EqualSlowCase(const APInt& RHS) const {
488 // Get some facts about the number of bits used in the two operands.
489 unsigned n1 = getActiveBits();
490 unsigned n2 = RHS.getActiveBits();
492 // If the number of bits isn't the same, they aren't equal
496 // If the number of bits fits in a word, we only need to compare the low word.
497 if (n1 <= APINT_BITS_PER_WORD)
498 return pVal[0] == RHS.pVal[0];
500 // Otherwise, compare everything
501 for (int i = whichWord(n1 - 1); i >= 0; --i)
502 if (pVal[i] != RHS.pVal[i])
507 bool APInt::EqualSlowCase(uint64_t Val) const {
508 unsigned n = getActiveBits();
509 if (n <= APINT_BITS_PER_WORD)
510 return pVal[0] == Val;
515 bool APInt::ult(const APInt& RHS) const {
516 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
518 return VAL < RHS.VAL;
520 // Get active bit length of both operands
521 unsigned n1 = getActiveBits();
522 unsigned n2 = RHS.getActiveBits();
524 // If magnitude of LHS is less than RHS, return true.
528 // If magnitude of RHS is greather than LHS, return false.
532 // If they bot fit in a word, just compare the low order word
533 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
534 return pVal[0] < RHS.pVal[0];
536 // Otherwise, compare all words
537 unsigned topWord = whichWord(std::max(n1,n2)-1);
538 for (int i = topWord; i >= 0; --i) {
539 if (pVal[i] > RHS.pVal[i])
541 if (pVal[i] < RHS.pVal[i])
547 bool APInt::slt(const APInt& RHS) const {
548 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
549 if (isSingleWord()) {
550 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
551 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
552 return lhsSext < rhsSext;
557 bool lhsNeg = isNegative();
558 bool rhsNeg = rhs.isNegative();
560 // Sign bit is set so perform two's complement to make it positive
565 // Sign bit is set so perform two's complement to make it positive
570 // Now we have unsigned values to compare so do the comparison if necessary
571 // based on the negativeness of the values.
583 void APInt::setBit(unsigned bitPosition) {
585 VAL |= maskBit(bitPosition);
587 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
590 /// Set the given bit to 0 whose position is given as "bitPosition".
591 /// @brief Set a given bit to 0.
592 void APInt::clearBit(unsigned bitPosition) {
594 VAL &= ~maskBit(bitPosition);
596 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
599 /// @brief Toggle every bit to its opposite value.
601 /// Toggle a given bit to its opposite value whose position is given
602 /// as "bitPosition".
603 /// @brief Toggles a given bit to its opposite value.
604 void APInt::flipBit(unsigned bitPosition) {
605 assert(bitPosition < BitWidth && "Out of the bit-width range!");
606 if ((*this)[bitPosition]) clearBit(bitPosition);
607 else setBit(bitPosition);
610 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
611 assert(!str.empty() && "Invalid string length");
612 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
614 "Radix should be 2, 8, 10, 16, or 36!");
616 size_t slen = str.size();
618 // Each computation below needs to know if it's negative.
619 StringRef::iterator p = str.begin();
620 unsigned isNegative = *p == '-';
621 if (*p == '-' || *p == '+') {
624 assert(slen && "String is only a sign, needs a value.");
627 // For radixes of power-of-two values, the bits required is accurately and
630 return slen + isNegative;
632 return slen * 3 + isNegative;
634 return slen * 4 + isNegative;
638 // This is grossly inefficient but accurate. We could probably do something
639 // with a computation of roughly slen*64/20 and then adjust by the value of
640 // the first few digits. But, I'm not sure how accurate that could be.
642 // Compute a sufficient number of bits that is always large enough but might
643 // be too large. This avoids the assertion in the constructor. This
644 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
645 // bits in that case.
647 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
648 : (slen == 1 ? 7 : slen * 16/3);
650 // Convert to the actual binary value.
651 APInt tmp(sufficient, StringRef(p, slen), radix);
653 // Compute how many bits are required. If the log is infinite, assume we need
655 unsigned log = tmp.logBase2();
656 if (log == (unsigned)-1) {
657 return isNegative + 1;
659 return isNegative + log + 1;
663 hash_code llvm::hash_value(const APInt &Arg) {
664 if (Arg.isSingleWord())
665 return hash_combine(Arg.VAL);
667 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
670 /// HiBits - 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 /// LoBits - 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 {
682 // Treat the most significand word differently because it might have
683 // meaningless bits set beyond the precision.
684 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
686 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
688 MSWMask = ~integerPart(0);
689 BitsInMSW = APINT_BITS_PER_WORD;
692 unsigned i = getNumWords();
693 integerPart MSW = pVal[i-1] & MSWMask;
695 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
697 unsigned Count = BitsInMSW;
698 for (--i; i > 0u; --i) {
700 Count += APINT_BITS_PER_WORD;
702 Count += CountLeadingZeros_64(pVal[i-1]);
709 unsigned APInt::countLeadingOnes() const {
711 return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
713 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
716 highWordBits = APINT_BITS_PER_WORD;
719 shift = APINT_BITS_PER_WORD - highWordBits;
721 int i = getNumWords() - 1;
722 unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
723 if (Count == highWordBits) {
724 for (i--; i >= 0; --i) {
725 if (pVal[i] == -1ULL)
726 Count += APINT_BITS_PER_WORD;
728 Count += CountLeadingOnes_64(pVal[i]);
736 unsigned APInt::countTrailingZeros() const {
738 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
741 for (; i < getNumWords() && pVal[i] == 0; ++i)
742 Count += APINT_BITS_PER_WORD;
743 if (i < getNumWords())
744 Count += CountTrailingZeros_64(pVal[i]);
745 return std::min(Count, BitWidth);
748 unsigned APInt::countTrailingOnesSlowCase() const {
751 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
752 Count += APINT_BITS_PER_WORD;
753 if (i < getNumWords())
754 Count += CountTrailingOnes_64(pVal[i]);
755 return std::min(Count, BitWidth);
758 unsigned APInt::countPopulationSlowCase() const {
760 for (unsigned i = 0; i < getNumWords(); ++i)
761 Count += CountPopulation_64(pVal[i]);
765 /// Perform a logical right-shift from Src to Dst, which must be equal or
766 /// non-overlapping, of Words words, by Shift, which must be less than 64.
767 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
770 for (int I = Words - 1; I >= 0; --I) {
771 uint64_t Tmp = Src[I];
772 Dst[I] = (Tmp >> Shift) | Carry;
773 Carry = Tmp << (64 - Shift);
777 APInt APInt::byteSwap() const {
778 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
780 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
782 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
783 if (BitWidth == 48) {
784 unsigned Tmp1 = unsigned(VAL >> 16);
785 Tmp1 = ByteSwap_32(Tmp1);
786 uint16_t Tmp2 = uint16_t(VAL);
787 Tmp2 = ByteSwap_16(Tmp2);
788 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
791 return APInt(BitWidth, ByteSwap_64(VAL));
793 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
794 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
795 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
796 if (Result.BitWidth != BitWidth) {
797 lshrNear(Result.pVal, Result.pVal, getNumWords(),
798 Result.BitWidth - BitWidth);
799 Result.BitWidth = BitWidth;
804 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
806 APInt A = API1, B = API2;
809 B = APIntOps::urem(A, B);
815 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
822 // Get the sign bit from the highest order bit
823 bool isNeg = T.I >> 63;
825 // Get the 11-bit exponent and adjust for the 1023 bit bias
826 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
828 // If the exponent is negative, the value is < 0 so just return 0.
830 return APInt(width, 0u);
832 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
833 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
835 // If the exponent doesn't shift all bits out of the mantissa
837 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
838 APInt(width, mantissa >> (52 - exp));
840 // If the client didn't provide enough bits for us to shift the mantissa into
841 // then the result is undefined, just return 0
842 if (width <= exp - 52)
843 return APInt(width, 0);
845 // Otherwise, we have to shift the mantissa bits up to the right location
846 APInt Tmp(width, mantissa);
847 Tmp = Tmp.shl((unsigned)exp - 52);
848 return isNeg ? -Tmp : Tmp;
851 /// RoundToDouble - This function converts this APInt to a double.
852 /// The layout for double is as following (IEEE Standard 754):
853 /// --------------------------------------
854 /// | Sign Exponent Fraction Bias |
855 /// |-------------------------------------- |
856 /// | 1[63] 11[62-52] 52[51-00] 1023 |
857 /// --------------------------------------
858 double APInt::roundToDouble(bool isSigned) const {
860 // Handle the simple case where the value is contained in one uint64_t.
861 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
862 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
864 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
867 return double(getWord(0));
870 // Determine if the value is negative.
871 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
873 // Construct the absolute value if we're negative.
874 APInt Tmp(isNeg ? -(*this) : (*this));
876 // Figure out how many bits we're using.
877 unsigned n = Tmp.getActiveBits();
879 // The exponent (without bias normalization) is just the number of bits
880 // we are using. Note that the sign bit is gone since we constructed the
884 // Return infinity for exponent overflow
886 if (!isSigned || !isNeg)
887 return std::numeric_limits<double>::infinity();
889 return -std::numeric_limits<double>::infinity();
891 exp += 1023; // Increment for 1023 bias
893 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
894 // extract the high 52 bits from the correct words in pVal.
896 unsigned hiWord = whichWord(n-1);
898 mantissa = Tmp.pVal[0];
900 mantissa >>= n - 52; // shift down, we want the top 52 bits.
902 assert(hiWord > 0 && "huh?");
903 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
904 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
905 mantissa = hibits | lobits;
908 // The leading bit of mantissa is implicit, so get rid of it.
909 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
914 T.I = sign | (exp << 52) | mantissa;
918 // Truncate to new width.
919 APInt APInt::trunc(unsigned width) const {
920 assert(width < BitWidth && "Invalid APInt Truncate request");
921 assert(width && "Can't truncate to 0 bits");
923 if (width <= APINT_BITS_PER_WORD)
924 return APInt(width, getRawData()[0]);
926 APInt Result(getMemory(getNumWords(width)), width);
930 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
931 Result.pVal[i] = pVal[i];
933 // Truncate and copy any partial word.
934 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
936 Result.pVal[i] = pVal[i] << bits >> bits;
941 // Sign extend to a new width.
942 APInt APInt::sext(unsigned width) const {
943 assert(width > BitWidth && "Invalid APInt SignExtend request");
945 if (width <= APINT_BITS_PER_WORD) {
946 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
947 val = (int64_t)val >> (width - BitWidth);
948 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
951 APInt Result(getMemory(getNumWords(width)), width);
956 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
957 word = getRawData()[i];
958 Result.pVal[i] = word;
961 // Read and sign-extend any partial word.
962 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
964 word = (int64_t)getRawData()[i] << bits >> bits;
966 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
968 // Write remaining full words.
969 for (; i != width / APINT_BITS_PER_WORD; i++) {
970 Result.pVal[i] = word;
971 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
974 // Write any partial word.
975 bits = (0 - width) % APINT_BITS_PER_WORD;
977 Result.pVal[i] = word << bits >> bits;
982 // Zero extend to a new width.
983 APInt APInt::zext(unsigned width) const {
984 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
986 if (width <= APINT_BITS_PER_WORD)
987 return APInt(width, VAL);
989 APInt Result(getMemory(getNumWords(width)), width);
993 for (i = 0; i != getNumWords(); i++)
994 Result.pVal[i] = getRawData()[i];
996 // Zero remaining words.
997 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1002 APInt APInt::zextOrTrunc(unsigned width) const {
1003 if (BitWidth < width)
1005 if (BitWidth > width)
1006 return trunc(width);
1010 APInt APInt::sextOrTrunc(unsigned width) const {
1011 if (BitWidth < width)
1013 if (BitWidth > width)
1014 return trunc(width);
1018 APInt APInt::zextOrSelf(unsigned width) const {
1019 if (BitWidth < width)
1024 APInt APInt::sextOrSelf(unsigned width) const {
1025 if (BitWidth < width)
1030 /// Arithmetic right-shift this APInt by shiftAmt.
1031 /// @brief Arithmetic right-shift function.
1032 APInt APInt::ashr(const APInt &shiftAmt) const {
1033 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1036 /// Arithmetic right-shift this APInt by shiftAmt.
1037 /// @brief Arithmetic right-shift function.
1038 APInt APInt::ashr(unsigned shiftAmt) const {
1039 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1040 // Handle a degenerate case
1044 // Handle single word shifts with built-in ashr
1045 if (isSingleWord()) {
1046 if (shiftAmt == BitWidth)
1047 return APInt(BitWidth, 0); // undefined
1049 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1050 return APInt(BitWidth,
1051 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1055 // If all the bits were shifted out, the result is, technically, undefined.
1056 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1057 // issues in the algorithm below.
1058 if (shiftAmt == BitWidth) {
1060 return APInt(BitWidth, -1ULL, true);
1062 return APInt(BitWidth, 0);
1065 // Create some space for the result.
1066 uint64_t * val = new uint64_t[getNumWords()];
1068 // Compute some values needed by the following shift algorithms
1069 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1070 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1071 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1072 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1073 if (bitsInWord == 0)
1074 bitsInWord = APINT_BITS_PER_WORD;
1076 // If we are shifting whole words, just move whole words
1077 if (wordShift == 0) {
1078 // Move the words containing significant bits
1079 for (unsigned i = 0; i <= breakWord; ++i)
1080 val[i] = pVal[i+offset]; // move whole word
1082 // Adjust the top significant word for sign bit fill, if negative
1084 if (bitsInWord < APINT_BITS_PER_WORD)
1085 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1087 // Shift the low order words
1088 for (unsigned i = 0; i < breakWord; ++i) {
1089 // This combines the shifted corresponding word with the low bits from
1090 // the next word (shifted into this word's high bits).
1091 val[i] = (pVal[i+offset] >> wordShift) |
1092 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1095 // Shift the break word. In this case there are no bits from the next word
1096 // to include in this word.
1097 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1099 // Deal with sign extenstion in the break word, and possibly the word before
1102 if (wordShift > bitsInWord) {
1105 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1106 val[breakWord] |= ~0ULL;
1108 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1112 // Remaining words are 0 or -1, just assign them.
1113 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1114 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1116 return APInt(val, BitWidth).clearUnusedBits();
1119 /// Logical right-shift this APInt by shiftAmt.
1120 /// @brief Logical right-shift function.
1121 APInt APInt::lshr(const APInt &shiftAmt) const {
1122 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1125 /// Logical right-shift this APInt by shiftAmt.
1126 /// @brief Logical right-shift function.
1127 APInt APInt::lshr(unsigned shiftAmt) const {
1128 if (isSingleWord()) {
1129 if (shiftAmt >= BitWidth)
1130 return APInt(BitWidth, 0);
1132 return APInt(BitWidth, this->VAL >> shiftAmt);
1135 // If all the bits were shifted out, the result is 0. This avoids issues
1136 // with shifting by the size of the integer type, which produces undefined
1137 // results. We define these "undefined results" to always be 0.
1138 if (shiftAmt >= BitWidth)
1139 return APInt(BitWidth, 0);
1141 // If none of the bits are shifted out, the result is *this. This avoids
1142 // issues with shifting by the size of the integer type, which produces
1143 // undefined results in the code below. This is also an optimization.
1147 // Create some space for the result.
1148 uint64_t * val = new uint64_t[getNumWords()];
1150 // If we are shifting less than a word, compute the shift with a simple carry
1151 if (shiftAmt < APINT_BITS_PER_WORD) {
1152 lshrNear(val, pVal, getNumWords(), shiftAmt);
1153 return APInt(val, BitWidth).clearUnusedBits();
1156 // Compute some values needed by the remaining shift algorithms
1157 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1158 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1160 // If we are shifting whole words, just move whole words
1161 if (wordShift == 0) {
1162 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1163 val[i] = pVal[i+offset];
1164 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1166 return APInt(val,BitWidth).clearUnusedBits();
1169 // Shift the low order words
1170 unsigned breakWord = getNumWords() - offset -1;
1171 for (unsigned i = 0; i < breakWord; ++i)
1172 val[i] = (pVal[i+offset] >> wordShift) |
1173 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1174 // Shift the break word.
1175 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1177 // Remaining words are 0
1178 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1180 return APInt(val, BitWidth).clearUnusedBits();
1183 /// Left-shift this APInt by shiftAmt.
1184 /// @brief Left-shift function.
1185 APInt APInt::shl(const APInt &shiftAmt) const {
1186 // It's undefined behavior in C to shift by BitWidth or greater.
1187 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1190 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1191 // If all the bits were shifted out, the result is 0. This avoids issues
1192 // with shifting by the size of the integer type, which produces undefined
1193 // results. We define these "undefined results" to always be 0.
1194 if (shiftAmt == BitWidth)
1195 return APInt(BitWidth, 0);
1197 // If none of the bits are shifted out, the result is *this. This avoids a
1198 // lshr by the words size in the loop below which can produce incorrect
1199 // results. It also avoids the expensive computation below for a common case.
1203 // Create some space for the result.
1204 uint64_t * val = new uint64_t[getNumWords()];
1206 // If we are shifting less than a word, do it the easy way
1207 if (shiftAmt < APINT_BITS_PER_WORD) {
1209 for (unsigned i = 0; i < getNumWords(); i++) {
1210 val[i] = pVal[i] << shiftAmt | carry;
1211 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1213 return APInt(val, BitWidth).clearUnusedBits();
1216 // Compute some values needed by the remaining shift algorithms
1217 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1218 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1220 // If we are shifting whole words, just move whole words
1221 if (wordShift == 0) {
1222 for (unsigned i = 0; i < offset; i++)
1224 for (unsigned i = offset; i < getNumWords(); i++)
1225 val[i] = pVal[i-offset];
1226 return APInt(val,BitWidth).clearUnusedBits();
1229 // Copy whole words from this to Result.
1230 unsigned i = getNumWords() - 1;
1231 for (; i > offset; --i)
1232 val[i] = pVal[i-offset] << wordShift |
1233 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1234 val[offset] = pVal[0] << wordShift;
1235 for (i = 0; i < offset; ++i)
1237 return APInt(val, BitWidth).clearUnusedBits();
1240 APInt APInt::rotl(const APInt &rotateAmt) const {
1241 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1244 APInt APInt::rotl(unsigned rotateAmt) const {
1245 rotateAmt %= BitWidth;
1248 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1251 APInt APInt::rotr(const APInt &rotateAmt) const {
1252 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1255 APInt APInt::rotr(unsigned rotateAmt) const {
1256 rotateAmt %= BitWidth;
1259 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1262 // Square Root - this method computes and returns the square root of "this".
1263 // Three mechanisms are used for computation. For small values (<= 5 bits),
1264 // a table lookup is done. This gets some performance for common cases. For
1265 // values using less than 52 bits, the value is converted to double and then
1266 // the libc sqrt function is called. The result is rounded and then converted
1267 // back to a uint64_t which is then used to construct the result. Finally,
1268 // the Babylonian method for computing square roots is used.
1269 APInt APInt::sqrt() const {
1271 // Determine the magnitude of the value.
1272 unsigned magnitude = getActiveBits();
1274 // Use a fast table for some small values. This also gets rid of some
1275 // rounding errors in libc sqrt for small values.
1276 if (magnitude <= 5) {
1277 static const uint8_t results[32] = {
1280 /* 3- 6 */ 2, 2, 2, 2,
1281 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1282 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1283 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1286 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1289 // If the magnitude of the value fits in less than 52 bits (the precision of
1290 // an IEEE double precision floating point value), then we can use the
1291 // libc sqrt function which will probably use a hardware sqrt computation.
1292 // This should be faster than the algorithm below.
1293 if (magnitude < 52) {
1295 return APInt(BitWidth,
1296 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1298 return APInt(BitWidth,
1299 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1303 // Okay, all the short cuts are exhausted. We must compute it. The following
1304 // is a classical Babylonian method for computing the square root. This code
1305 // was adapted to APINt from a wikipedia article on such computations.
1306 // See http://www.wikipedia.org/ and go to the page named
1307 // Calculate_an_integer_square_root.
1308 unsigned nbits = BitWidth, i = 4;
1309 APInt testy(BitWidth, 16);
1310 APInt x_old(BitWidth, 1);
1311 APInt x_new(BitWidth, 0);
1312 APInt two(BitWidth, 2);
1314 // Select a good starting value using binary logarithms.
1315 for (;; i += 2, testy = testy.shl(2))
1316 if (i >= nbits || this->ule(testy)) {
1317 x_old = x_old.shl(i / 2);
1321 // Use the Babylonian method to arrive at the integer square root:
1323 x_new = (this->udiv(x_old) + x_old).udiv(two);
1324 if (x_old.ule(x_new))
1329 // Make sure we return the closest approximation
1330 // NOTE: The rounding calculation below is correct. It will produce an
1331 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1332 // determined to be a rounding issue with pari/gp as it begins to use a
1333 // floating point representation after 192 bits. There are no discrepancies
1334 // between this algorithm and pari/gp for bit widths < 192 bits.
1335 APInt square(x_old * x_old);
1336 APInt nextSquare((x_old + 1) * (x_old +1));
1337 if (this->ult(square))
1339 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1340 APInt midpoint((nextSquare - square).udiv(two));
1341 APInt offset(*this - square);
1342 if (offset.ult(midpoint))
1347 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1348 /// iterative extended Euclidean algorithm is used to solve for this value,
1349 /// however we simplify it to speed up calculating only the inverse, and take
1350 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1351 /// (potentially large) APInts around.
1352 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1353 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1355 // Using the properties listed at the following web page (accessed 06/21/08):
1356 // http://www.numbertheory.org/php/euclid.html
1357 // (especially the properties numbered 3, 4 and 9) it can be proved that
1358 // BitWidth bits suffice for all the computations in the algorithm implemented
1359 // below. More precisely, this number of bits suffice if the multiplicative
1360 // inverse exists, but may not suffice for the general extended Euclidean
1363 APInt r[2] = { modulo, *this };
1364 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1365 APInt q(BitWidth, 0);
1368 for (i = 0; r[i^1] != 0; i ^= 1) {
1369 // An overview of the math without the confusing bit-flipping:
1370 // q = r[i-2] / r[i-1]
1371 // r[i] = r[i-2] % r[i-1]
1372 // t[i] = t[i-2] - t[i-1] * q
1373 udivrem(r[i], r[i^1], q, r[i]);
1377 // If this APInt and the modulo are not coprime, there is no multiplicative
1378 // inverse, so return 0. We check this by looking at the next-to-last
1379 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1382 return APInt(BitWidth, 0);
1384 // The next-to-last t is the multiplicative inverse. However, we are
1385 // interested in a positive inverse. Calcuate a positive one from a negative
1386 // one if necessary. A simple addition of the modulo suffices because
1387 // abs(t[i]) is known to be less than *this/2 (see the link above).
1388 return t[i].isNegative() ? t[i] + modulo : t[i];
1391 /// Calculate the magic numbers required to implement a signed integer division
1392 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1393 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1394 /// Warren, Jr., chapter 10.
1395 APInt::ms APInt::magic() const {
1396 const APInt& d = *this;
1398 APInt ad, anc, delta, q1, r1, q2, r2, t;
1399 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1403 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1404 anc = t - 1 - t.urem(ad); // absolute value of nc
1405 p = d.getBitWidth() - 1; // initialize p
1406 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1407 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1408 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1409 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1412 q1 = q1<<1; // update q1 = 2p/abs(nc)
1413 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1414 if (r1.uge(anc)) { // must be unsigned comparison
1418 q2 = q2<<1; // update q2 = 2p/abs(d)
1419 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1420 if (r2.uge(ad)) { // must be unsigned comparison
1425 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1428 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1429 mag.s = p - d.getBitWidth(); // resulting shift
1433 /// Calculate the magic numbers required to implement an unsigned integer
1434 /// division by a constant as a sequence of multiplies, adds and shifts.
1435 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1436 /// S. Warren, Jr., chapter 10.
1437 /// LeadingZeros can be used to simplify the calculation if the upper bits
1438 /// of the divided value are known zero.
1439 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1440 const APInt& d = *this;
1442 APInt nc, delta, q1, r1, q2, r2;
1444 magu.a = 0; // initialize "add" indicator
1445 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1446 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1447 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1449 nc = allOnes - (allOnes - d).urem(d);
1450 p = d.getBitWidth() - 1; // initialize p
1451 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1452 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1453 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1454 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1457 if (r1.uge(nc - r1)) {
1458 q1 = q1 + q1 + 1; // update q1
1459 r1 = r1 + r1 - nc; // update r1
1462 q1 = q1+q1; // update q1
1463 r1 = r1+r1; // update r1
1465 if ((r2 + 1).uge(d - r2)) {
1466 if (q2.uge(signedMax)) magu.a = 1;
1467 q2 = q2+q2 + 1; // update q2
1468 r2 = r2+r2 + 1 - d; // update r2
1471 if (q2.uge(signedMin)) magu.a = 1;
1472 q2 = q2+q2; // update q2
1473 r2 = r2+r2 + 1; // update r2
1476 } while (p < d.getBitWidth()*2 &&
1477 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1478 magu.m = q2 + 1; // resulting magic number
1479 magu.s = p - d.getBitWidth(); // resulting shift
1483 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1484 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1485 /// variables here have the same names as in the algorithm. Comments explain
1486 /// the algorithm and any deviation from it.
1487 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1488 unsigned m, unsigned n) {
1489 assert(u && "Must provide dividend");
1490 assert(v && "Must provide divisor");
1491 assert(q && "Must provide quotient");
1492 assert(u != v && u != q && v != q && "Must us different memory");
1493 assert(n>1 && "n must be > 1");
1495 // Knuth uses the value b as the base of the number system. In our case b
1496 // is 2^31 so we just set it to -1u.
1497 uint64_t b = uint64_t(1) << 32;
1500 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1501 DEBUG(dbgs() << "KnuthDiv: original:");
1502 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1503 DEBUG(dbgs() << " by");
1504 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1505 DEBUG(dbgs() << '\n');
1507 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1508 // u and v by d. Note that we have taken Knuth's advice here to use a power
1509 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1510 // 2 allows us to shift instead of multiply and it is easy to determine the
1511 // shift amount from the leading zeros. We are basically normalizing the u
1512 // and v so that its high bits are shifted to the top of v's range without
1513 // overflow. Note that this can require an extra word in u so that u must
1514 // be of length m+n+1.
1515 unsigned shift = CountLeadingZeros_32(v[n-1]);
1516 unsigned v_carry = 0;
1517 unsigned u_carry = 0;
1519 for (unsigned i = 0; i < m+n; ++i) {
1520 unsigned u_tmp = u[i] >> (32 - shift);
1521 u[i] = (u[i] << shift) | u_carry;
1524 for (unsigned i = 0; i < n; ++i) {
1525 unsigned v_tmp = v[i] >> (32 - shift);
1526 v[i] = (v[i] << shift) | v_carry;
1532 DEBUG(dbgs() << "KnuthDiv: normal:");
1533 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1534 DEBUG(dbgs() << " by");
1535 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1536 DEBUG(dbgs() << '\n');
1539 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1542 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1543 // D3. [Calculate q'.].
1544 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1545 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1546 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1547 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1548 // on v[n-2] determines at high speed most of the cases in which the trial
1549 // value qp is one too large, and it eliminates all cases where qp is two
1551 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1552 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1553 uint64_t qp = dividend / v[n-1];
1554 uint64_t rp = dividend % v[n-1];
1555 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1558 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1561 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1563 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1564 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1565 // consists of a simple multiplication by a one-place number, combined with
1568 for (unsigned i = 0; i < n; ++i) {
1569 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1570 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1571 bool borrow = subtrahend > u_tmp;
1572 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1573 << ", subtrahend == " << subtrahend
1574 << ", borrow = " << borrow << '\n');
1576 uint64_t result = u_tmp - subtrahend;
1578 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1579 u[k++] = (unsigned)(result >> 32); // subtract high word
1580 while (borrow && k <= m+n) { // deal with borrow to the left
1586 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1589 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1590 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1591 DEBUG(dbgs() << '\n');
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.
1598 bool carry = true; // true because b's complement is "complement + 1"
1599 for (unsigned i = 0; i <= m+n; ++i) {
1600 u[i] = ~u[i] + carry; // b's complement
1601 carry = carry && u[i] == 0;
1604 DEBUG(dbgs() << "KnuthDiv: after complement:");
1605 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1606 DEBUG(dbgs() << '\n');
1608 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1609 // negative, go to step D6; otherwise go on to step D7.
1610 q[j] = (unsigned)qp;
1612 // D6. [Add back]. The probability that this step is necessary is very
1613 // small, on the order of only 2/b. Make sure that test data accounts for
1614 // this possibility. Decrease q[j] by 1
1616 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1617 // A carry will occur to the left of u[j+n], and it should be ignored
1618 // since it cancels with the borrow that occurred in D4.
1620 for (unsigned i = 0; i < n; i++) {
1621 unsigned limit = std::min(u[j+i],v[i]);
1622 u[j+i] += v[i] + carry;
1623 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1627 DEBUG(dbgs() << "KnuthDiv: after correction:");
1628 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1629 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1631 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1634 DEBUG(dbgs() << "KnuthDiv: quotient:");
1635 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1636 DEBUG(dbgs() << '\n');
1638 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1639 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1640 // compute the remainder (urem uses this).
1642 // The value d is expressed by the "shift" value above since we avoided
1643 // multiplication by d by using a shift left. So, all we have to do is
1644 // shift right here. In order to mak
1647 DEBUG(dbgs() << "KnuthDiv: remainder:");
1648 for (int i = n-1; i >= 0; i--) {
1649 r[i] = (u[i] >> shift) | carry;
1650 carry = u[i] << (32 - shift);
1651 DEBUG(dbgs() << " " << r[i]);
1654 for (int i = n-1; i >= 0; i--) {
1656 DEBUG(dbgs() << " " << r[i]);
1659 DEBUG(dbgs() << '\n');
1662 DEBUG(dbgs() << '\n');
1666 void APInt::divide(const APInt LHS, unsigned lhsWords,
1667 const APInt &RHS, unsigned rhsWords,
1668 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];
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 if (lhsWords == 1) {
1789 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1790 if (Quotient->isSingleWord())
1791 Quotient->VAL = tmp;
1793 Quotient->pVal[0] = tmp;
1795 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1796 for (unsigned i = 0; i < lhsWords; ++i)
1798 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1802 // If the caller wants the remainder
1804 // Set up the Remainder value's memory.
1805 if (Remainder->BitWidth != RHS.BitWidth) {
1806 if (Remainder->isSingleWord())
1809 delete [] Remainder->pVal;
1810 Remainder->BitWidth = RHS.BitWidth;
1811 if (!Remainder->isSingleWord())
1812 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1814 Remainder->clearAllBits();
1816 // The remainder is in R. Reconstitute the remainder into Remainder's low
1818 if (rhsWords == 1) {
1820 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1821 if (Remainder->isSingleWord())
1822 Remainder->VAL = tmp;
1824 Remainder->pVal[0] = tmp;
1826 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1827 for (unsigned i = 0; i < rhsWords; ++i)
1828 Remainder->pVal[i] =
1829 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1833 // Clean up the memory we allocated.
1834 if (U != &SPACE[0]) {
1842 APInt APInt::udiv(const APInt& RHS) const {
1843 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1845 // First, deal with the easy case
1846 if (isSingleWord()) {
1847 assert(RHS.VAL != 0 && "Divide by zero?");
1848 return APInt(BitWidth, VAL / RHS.VAL);
1851 // Get some facts about the LHS and RHS number of bits and words
1852 unsigned rhsBits = RHS.getActiveBits();
1853 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1854 assert(rhsWords && "Divided by zero???");
1855 unsigned lhsBits = this->getActiveBits();
1856 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1858 // Deal with some degenerate cases
1861 return APInt(BitWidth, 0);
1862 else if (lhsWords < rhsWords || this->ult(RHS)) {
1863 // X / Y ===> 0, iff X < Y
1864 return APInt(BitWidth, 0);
1865 } else if (*this == RHS) {
1867 return APInt(BitWidth, 1);
1868 } else if (lhsWords == 1 && rhsWords == 1) {
1869 // All high words are zero, just use native divide
1870 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1873 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1874 APInt Quotient(1,0); // to hold result.
1875 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1879 APInt APInt::urem(const APInt& RHS) const {
1880 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1881 if (isSingleWord()) {
1882 assert(RHS.VAL != 0 && "Remainder by zero?");
1883 return APInt(BitWidth, VAL % RHS.VAL);
1886 // Get some facts about the LHS
1887 unsigned lhsBits = getActiveBits();
1888 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1890 // Get some facts about the RHS
1891 unsigned rhsBits = RHS.getActiveBits();
1892 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1893 assert(rhsWords && "Performing remainder operation by zero ???");
1895 // Check the degenerate cases
1896 if (lhsWords == 0) {
1898 return APInt(BitWidth, 0);
1899 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1900 // X % Y ===> X, iff X < Y
1902 } else if (*this == RHS) {
1904 return APInt(BitWidth, 0);
1905 } else if (lhsWords == 1) {
1906 // All high words are zero, just use native remainder
1907 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1910 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1911 APInt Remainder(1,0);
1912 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1916 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1917 APInt &Quotient, APInt &Remainder) {
1918 // Get some size facts about the dividend and divisor
1919 unsigned lhsBits = LHS.getActiveBits();
1920 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1921 unsigned rhsBits = RHS.getActiveBits();
1922 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1924 // Check the degenerate cases
1925 if (lhsWords == 0) {
1926 Quotient = 0; // 0 / Y ===> 0
1927 Remainder = 0; // 0 % Y ===> 0
1931 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1932 Remainder = LHS; // X % Y ===> X, iff X < Y
1933 Quotient = 0; // X / Y ===> 0, iff X < Y
1938 Quotient = 1; // X / X ===> 1
1939 Remainder = 0; // X % X ===> 0;
1943 if (lhsWords == 1 && rhsWords == 1) {
1944 // There is only one word to consider so use the native versions.
1945 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1946 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1947 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1948 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1952 // Okay, lets do it the long way
1953 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1956 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1957 APInt Res = *this+RHS;
1958 Overflow = isNonNegative() == RHS.isNonNegative() &&
1959 Res.isNonNegative() != isNonNegative();
1963 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1964 APInt Res = *this+RHS;
1965 Overflow = Res.ult(RHS);
1969 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1970 APInt Res = *this - RHS;
1971 Overflow = isNonNegative() != RHS.isNonNegative() &&
1972 Res.isNonNegative() != isNonNegative();
1976 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1977 APInt Res = *this-RHS;
1978 Overflow = Res.ugt(*this);
1982 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1983 // MININT/-1 --> overflow.
1984 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1988 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1989 APInt Res = *this * RHS;
1991 if (*this != 0 && RHS != 0)
1992 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1998 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1999 APInt Res = *this * RHS;
2001 if (*this != 0 && RHS != 0)
2002 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2008 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2009 Overflow = ShAmt >= getBitWidth();
2011 ShAmt = getBitWidth()-1;
2013 if (isNonNegative()) // Don't allow sign change.
2014 Overflow = ShAmt >= countLeadingZeros();
2016 Overflow = ShAmt >= countLeadingOnes();
2018 return *this << ShAmt;
2024 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2025 // Check our assumptions here
2026 assert(!str.empty() && "Invalid string length");
2027 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2029 "Radix should be 2, 8, 10, 16, or 36!");
2031 StringRef::iterator p = str.begin();
2032 size_t slen = str.size();
2033 bool isNeg = *p == '-';
2034 if (*p == '-' || *p == '+') {
2037 assert(slen && "String is only a sign, needs a value.");
2039 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2040 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2041 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2042 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2043 "Insufficient bit width");
2046 if (!isSingleWord())
2047 pVal = getClearedMemory(getNumWords());
2049 // Figure out if we can shift instead of multiply
2050 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2052 // Set up an APInt for the digit to add outside the loop so we don't
2053 // constantly construct/destruct it.
2054 APInt apdigit(getBitWidth(), 0);
2055 APInt apradix(getBitWidth(), radix);
2057 // Enter digit traversal loop
2058 for (StringRef::iterator e = str.end(); p != e; ++p) {
2059 unsigned digit = getDigit(*p, radix);
2060 assert(digit < radix && "Invalid character in digit string");
2062 // Shift or multiply the value by the radix
2070 // Add in the digit we just interpreted
2071 if (apdigit.isSingleWord())
2072 apdigit.VAL = digit;
2074 apdigit.pVal[0] = digit;
2077 // If its negative, put it in two's complement form
2080 this->flipAllBits();
2084 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2085 bool Signed, bool formatAsCLiteral) const {
2086 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2088 "Radix should be 2, 8, 10, 16, or 36!");
2090 const char *Prefix = "";
2091 if (formatAsCLiteral) {
2094 // Binary literals are a non-standard extension added in gcc 4.3:
2095 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2107 llvm_unreachable("Invalid radix!");
2111 // First, check for a zero value and just short circuit the logic below.
2114 Str.push_back(*Prefix);
2121 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2123 if (isSingleWord()) {
2125 char *BufPtr = Buffer+65;
2131 int64_t I = getSExtValue();
2141 Str.push_back(*Prefix);
2146 *--BufPtr = Digits[N % Radix];
2149 Str.append(BufPtr, Buffer+65);
2155 if (Signed && isNegative()) {
2156 // They want to print the signed version and it is a negative value
2157 // Flip the bits and add one to turn it into the equivalent positive
2158 // value and put a '-' in the result.
2165 Str.push_back(*Prefix);
2169 // We insert the digits backward, then reverse them to get the right order.
2170 unsigned StartDig = Str.size();
2172 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2173 // because the number of bits per digit (1, 3 and 4 respectively) divides
2174 // equaly. We just shift until the value is zero.
2175 if (Radix == 2 || Radix == 8 || Radix == 16) {
2176 // Just shift tmp right for each digit width until it becomes zero
2177 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2178 unsigned MaskAmt = Radix - 1;
2181 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2182 Str.push_back(Digits[Digit]);
2183 Tmp = Tmp.lshr(ShiftAmt);
2186 APInt divisor(Radix == 10? 4 : 8, Radix);
2188 APInt APdigit(1, 0);
2189 APInt tmp2(Tmp.getBitWidth(), 0);
2190 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2192 unsigned Digit = (unsigned)APdigit.getZExtValue();
2193 assert(Digit < Radix && "divide failed");
2194 Str.push_back(Digits[Digit]);
2199 // Reverse the digits before returning.
2200 std::reverse(Str.begin()+StartDig, Str.end());
2203 /// toString - This returns the APInt as a std::string. Note that this is an
2204 /// inefficient method. It is better to pass in a SmallVector/SmallString
2205 /// to the methods above.
2206 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2208 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2213 void APInt::dump() const {
2214 SmallString<40> S, U;
2215 this->toStringUnsigned(U);
2216 this->toStringSigned(S);
2217 dbgs() << "APInt(" << BitWidth << "b, "
2218 << U.str() << "u " << S.str() << "s)";
2221 void APInt::print(raw_ostream &OS, bool isSigned) const {
2223 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2227 // This implements a variety of operations on a representation of
2228 // arbitrary precision, two's-complement, bignum integer values.
2230 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2231 // and unrestricting assumption.
2232 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2233 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2235 /* Some handy functions local to this file. */
2238 /* Returns the integer part with the least significant BITS set.
2239 BITS cannot be zero. */
2240 static inline integerPart
2241 lowBitMask(unsigned int bits)
2243 assert(bits != 0 && bits <= integerPartWidth);
2245 return ~(integerPart) 0 >> (integerPartWidth - bits);
2248 /* Returns the value of the lower half of PART. */
2249 static inline integerPart
2250 lowHalf(integerPart part)
2252 return part & lowBitMask(integerPartWidth / 2);
2255 /* Returns the value of the upper half of PART. */
2256 static inline integerPart
2257 highHalf(integerPart part)
2259 return part >> (integerPartWidth / 2);
2262 /* Returns the bit number of the most significant set bit of a part.
2263 If the input number has no bits set -1U is returned. */
2265 partMSB(integerPart value)
2267 unsigned int n, msb;
2272 n = integerPartWidth / 2;
2287 /* Returns the bit number of the least significant set bit of a
2288 part. If the input number has no bits set -1U is returned. */
2290 partLSB(integerPart value)
2292 unsigned int n, lsb;
2297 lsb = integerPartWidth - 1;
2298 n = integerPartWidth / 2;
2313 /* Sets the least significant part of a bignum to the input value, and
2314 zeroes out higher parts. */
2316 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2323 for (i = 1; i < parts; i++)
2327 /* Assign one bignum to another. */
2329 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2333 for (i = 0; i < parts; i++)
2337 /* Returns true if a bignum is zero, false otherwise. */
2339 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2343 for (i = 0; i < parts; i++)
2350 /* Extract the given bit of a bignum; returns 0 or 1. */
2352 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2354 return (parts[bit / integerPartWidth] &
2355 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2358 /* Set the given bit of a bignum. */
2360 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2362 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2365 /* Clears the given bit of a bignum. */
2367 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2369 parts[bit / integerPartWidth] &=
2370 ~((integerPart) 1 << (bit % integerPartWidth));
2373 /* Returns the bit number of the least significant set bit of a
2374 number. If the input number has no bits set -1U is returned. */
2376 APInt::tcLSB(const integerPart *parts, unsigned int n)
2378 unsigned int i, lsb;
2380 for (i = 0; i < n; i++) {
2381 if (parts[i] != 0) {
2382 lsb = partLSB(parts[i]);
2384 return lsb + i * integerPartWidth;
2391 /* Returns the bit number of the most significant set bit of a number.
2392 If the input number has no bits set -1U is returned. */
2394 APInt::tcMSB(const integerPart *parts, unsigned int n)
2401 if (parts[n] != 0) {
2402 msb = partMSB(parts[n]);
2404 return msb + n * integerPartWidth;
2411 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2412 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2413 the least significant bit of DST. All high bits above srcBITS in
2414 DST are zero-filled. */
2416 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2417 unsigned int srcBits, unsigned int srcLSB)
2419 unsigned int firstSrcPart, dstParts, shift, n;
2421 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2422 assert(dstParts <= dstCount);
2424 firstSrcPart = srcLSB / integerPartWidth;
2425 tcAssign (dst, src + firstSrcPart, dstParts);
2427 shift = srcLSB % integerPartWidth;
2428 tcShiftRight (dst, dstParts, shift);
2430 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2431 in DST. If this is less that srcBits, append the rest, else
2432 clear the high bits. */
2433 n = dstParts * integerPartWidth - shift;
2435 integerPart mask = lowBitMask (srcBits - n);
2436 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2437 << n % integerPartWidth);
2438 } else if (n > srcBits) {
2439 if (srcBits % integerPartWidth)
2440 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2443 /* Clear high parts. */
2444 while (dstParts < dstCount)
2445 dst[dstParts++] = 0;
2448 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2450 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2451 integerPart c, unsigned int parts)
2457 for (i = 0; i < parts; i++) {
2462 dst[i] += rhs[i] + 1;
2473 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2475 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2476 integerPart c, unsigned int parts)
2482 for (i = 0; i < parts; i++) {
2487 dst[i] -= rhs[i] + 1;
2498 /* Negate a bignum in-place. */
2500 APInt::tcNegate(integerPart *dst, unsigned int parts)
2502 tcComplement(dst, parts);
2503 tcIncrement(dst, parts);
2506 /* DST += SRC * MULTIPLIER + CARRY if add is true
2507 DST = SRC * MULTIPLIER + CARRY if add is false
2509 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2510 they must start at the same point, i.e. DST == SRC.
2512 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2513 returned. Otherwise DST is filled with the least significant
2514 DSTPARTS parts of the result, and if all of the omitted higher
2515 parts were zero return zero, otherwise overflow occurred and
2518 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2519 integerPart multiplier, integerPart carry,
2520 unsigned int srcParts, unsigned int 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 n = dstParts < srcParts ? dstParts: srcParts;
2532 for (i = 0; i < n; i++) {
2533 integerPart low, mid, high, srcPart;
2535 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2537 This cannot overflow, because
2539 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2541 which is less than n^2. */
2545 if (multiplier == 0 || srcPart == 0) {
2549 low = lowHalf(srcPart) * lowHalf(multiplier);
2550 high = highHalf(srcPart) * highHalf(multiplier);
2552 mid = lowHalf(srcPart) * highHalf(multiplier);
2553 high += highHalf(mid);
2554 mid <<= integerPartWidth / 2;
2555 if (low + mid < low)
2559 mid = highHalf(srcPart) * lowHalf(multiplier);
2560 high += highHalf(mid);
2561 mid <<= integerPartWidth / 2;
2562 if (low + mid < low)
2566 /* Now add carry. */
2567 if (low + carry < low)
2573 /* And now DST[i], and store the new low part there. */
2574 if (low + dst[i] < low)
2584 /* Full multiplication, there is no overflow. */
2585 assert(i + 1 == dstParts);
2589 /* We overflowed if there is carry. */
2593 /* We would overflow if any significant unwritten parts would be
2594 non-zero. This is true if any remaining src parts are non-zero
2595 and the multiplier is non-zero. */
2597 for (; i < srcParts; i++)
2601 /* We fitted in the narrow destination. */
2606 /* DST = LHS * RHS, where DST has the same width as the operands and
2607 is filled with the least significant parts of the result. Returns
2608 one if overflow occurred, otherwise zero. DST must be disjoint
2609 from both operands. */
2611 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2612 const integerPart *rhs, unsigned int parts)
2617 assert(dst != lhs && dst != rhs);
2620 tcSet(dst, 0, parts);
2622 for (i = 0; i < parts; i++)
2623 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2629 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2630 operands. No overflow occurs. DST must be disjoint from both
2631 operands. Returns the number of parts required to hold the
2634 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2635 const integerPart *rhs, unsigned int lhsParts,
2636 unsigned int rhsParts)
2638 /* Put the narrower number on the LHS for less loops below. */
2639 if (lhsParts > rhsParts) {
2640 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2644 assert(dst != lhs && dst != rhs);
2646 tcSet(dst, 0, rhsParts);
2648 for (n = 0; n < lhsParts; n++)
2649 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2651 n = lhsParts + rhsParts;
2653 return n - (dst[n - 1] == 0);
2657 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2658 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2659 set REMAINDER to the remainder, return zero. i.e.
2661 OLD_LHS = RHS * LHS + REMAINDER
2663 SCRATCH is a bignum of the same size as the operands and result for
2664 use by the routine; its contents need not be initialized and are
2665 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2668 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2669 integerPart *remainder, integerPart *srhs,
2672 unsigned int n, shiftCount;
2675 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2677 shiftCount = tcMSB(rhs, parts) + 1;
2678 if (shiftCount == 0)
2681 shiftCount = parts * integerPartWidth - shiftCount;
2682 n = shiftCount / integerPartWidth;
2683 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2685 tcAssign(srhs, rhs, parts);
2686 tcShiftLeft(srhs, parts, shiftCount);
2687 tcAssign(remainder, lhs, parts);
2688 tcSet(lhs, 0, parts);
2690 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2695 compare = tcCompare(remainder, srhs, parts);
2697 tcSubtract(remainder, srhs, 0, parts);
2701 if (shiftCount == 0)
2704 tcShiftRight(srhs, parts, 1);
2705 if ((mask >>= 1) == 0)
2706 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2712 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2713 There are no restrictions on COUNT. */
2715 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2718 unsigned int jump, shift;
2720 /* Jump is the inter-part jump; shift is is intra-part shift. */
2721 jump = count / integerPartWidth;
2722 shift = count % integerPartWidth;
2724 while (parts > jump) {
2729 /* dst[i] comes from the two parts src[i - jump] and, if we have
2730 an intra-part shift, src[i - jump - 1]. */
2731 part = dst[parts - jump];
2734 if (parts >= jump + 1)
2735 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2746 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2747 zero. There are no restrictions on COUNT. */
2749 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2752 unsigned int i, jump, shift;
2754 /* Jump is the inter-part jump; shift is is intra-part shift. */
2755 jump = count / integerPartWidth;
2756 shift = count % integerPartWidth;
2758 /* Perform the shift. This leaves the most significant COUNT bits
2759 of the result at zero. */
2760 for (i = 0; i < parts; i++) {
2763 if (i + jump >= parts) {
2766 part = dst[i + jump];
2769 if (i + jump + 1 < parts)
2770 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2779 /* Bitwise and of two bignums. */
2781 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2785 for (i = 0; i < parts; i++)
2789 /* Bitwise inclusive or of two bignums. */
2791 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2795 for (i = 0; i < parts; i++)
2799 /* Bitwise exclusive or of two bignums. */
2801 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2805 for (i = 0; i < parts; i++)
2809 /* Complement a bignum in-place. */
2811 APInt::tcComplement(integerPart *dst, unsigned int parts)
2815 for (i = 0; i < parts; i++)
2819 /* Comparison (unsigned) of two bignums. */
2821 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2826 if (lhs[parts] == rhs[parts])
2829 if (lhs[parts] > rhs[parts])
2838 /* Increment a bignum in-place, return the carry flag. */
2840 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2844 for (i = 0; i < parts; i++)
2851 /* Set the least significant BITS bits of a bignum, clear the
2854 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2860 while (bits > integerPartWidth) {
2861 dst[i++] = ~(integerPart) 0;
2862 bits -= integerPartWidth;
2866 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);