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 llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
697 unsigned Count = BitsInMSW;
698 for (--i; i > 0u; --i) {
700 Count += APINT_BITS_PER_WORD;
702 Count += llvm::countLeadingZeros(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(llvm::countTrailingZeros(VAL)), BitWidth);
741 for (; i < getNumWords() && pVal[i] == 0; ++i)
742 Count += APINT_BITS_PER_WORD;
743 if (i < getNumWords())
744 Count += llvm::countTrailingZeros(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(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::sdiv(const APInt &RHS) const {
1881 if (RHS.isNegative())
1882 return (-(*this)).udiv(-RHS);
1883 return -((-(*this)).udiv(RHS));
1885 if (RHS.isNegative())
1886 return -(this->udiv(-RHS));
1887 return this->udiv(RHS);
1890 APInt APInt::urem(const APInt& RHS) const {
1891 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1892 if (isSingleWord()) {
1893 assert(RHS.VAL != 0 && "Remainder by zero?");
1894 return APInt(BitWidth, VAL % RHS.VAL);
1897 // Get some facts about the LHS
1898 unsigned lhsBits = getActiveBits();
1899 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1901 // Get some facts about the RHS
1902 unsigned rhsBits = RHS.getActiveBits();
1903 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1904 assert(rhsWords && "Performing remainder operation by zero ???");
1906 // Check the degenerate cases
1907 if (lhsWords == 0) {
1909 return APInt(BitWidth, 0);
1910 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1911 // X % Y ===> X, iff X < Y
1913 } else if (*this == RHS) {
1915 return APInt(BitWidth, 0);
1916 } else if (lhsWords == 1) {
1917 // All high words are zero, just use native remainder
1918 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1921 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1922 APInt Remainder(1,0);
1923 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1927 APInt APInt::srem(const APInt &RHS) const {
1929 if (RHS.isNegative())
1930 return -((-(*this)).urem(-RHS));
1931 return -((-(*this)).urem(RHS));
1933 if (RHS.isNegative())
1934 return this->urem(-RHS);
1935 return this->urem(RHS);
1938 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1939 APInt &Quotient, APInt &Remainder) {
1940 // Get some size facts about the dividend and divisor
1941 unsigned lhsBits = LHS.getActiveBits();
1942 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1943 unsigned rhsBits = RHS.getActiveBits();
1944 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1946 // Check the degenerate cases
1947 if (lhsWords == 0) {
1948 Quotient = 0; // 0 / Y ===> 0
1949 Remainder = 0; // 0 % Y ===> 0
1953 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1954 Remainder = LHS; // X % Y ===> X, iff X < Y
1955 Quotient = 0; // X / Y ===> 0, iff X < Y
1960 Quotient = 1; // X / X ===> 1
1961 Remainder = 0; // X % X ===> 0;
1965 if (lhsWords == 1 && rhsWords == 1) {
1966 // There is only one word to consider so use the native versions.
1967 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1968 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1969 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1970 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1974 // Okay, lets do it the long way
1975 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1978 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1979 APInt &Quotient, APInt &Remainder) {
1980 if (LHS.isNegative()) {
1981 if (RHS.isNegative())
1982 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1984 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1985 Quotient = -Quotient;
1987 Remainder = -Remainder;
1988 } else if (RHS.isNegative()) {
1989 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1990 Quotient = -Quotient;
1992 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1996 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1997 APInt Res = *this+RHS;
1998 Overflow = isNonNegative() == RHS.isNonNegative() &&
1999 Res.isNonNegative() != isNonNegative();
2003 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2004 APInt Res = *this+RHS;
2005 Overflow = Res.ult(RHS);
2009 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2010 APInt Res = *this - RHS;
2011 Overflow = isNonNegative() != RHS.isNonNegative() &&
2012 Res.isNonNegative() != isNonNegative();
2016 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2017 APInt Res = *this-RHS;
2018 Overflow = Res.ugt(*this);
2022 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2023 // MININT/-1 --> overflow.
2024 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2028 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2029 APInt Res = *this * RHS;
2031 if (*this != 0 && RHS != 0)
2032 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2038 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2039 APInt Res = *this * RHS;
2041 if (*this != 0 && RHS != 0)
2042 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2048 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2049 Overflow = ShAmt >= getBitWidth();
2051 ShAmt = getBitWidth()-1;
2053 if (isNonNegative()) // Don't allow sign change.
2054 Overflow = ShAmt >= countLeadingZeros();
2056 Overflow = ShAmt >= countLeadingOnes();
2058 return *this << ShAmt;
2064 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2065 // Check our assumptions here
2066 assert(!str.empty() && "Invalid string length");
2067 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2069 "Radix should be 2, 8, 10, 16, or 36!");
2071 StringRef::iterator p = str.begin();
2072 size_t slen = str.size();
2073 bool isNeg = *p == '-';
2074 if (*p == '-' || *p == '+') {
2077 assert(slen && "String is only a sign, needs a value.");
2079 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2080 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2081 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2082 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2083 "Insufficient bit width");
2086 if (!isSingleWord())
2087 pVal = getClearedMemory(getNumWords());
2089 // Figure out if we can shift instead of multiply
2090 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2092 // Set up an APInt for the digit to add outside the loop so we don't
2093 // constantly construct/destruct it.
2094 APInt apdigit(getBitWidth(), 0);
2095 APInt apradix(getBitWidth(), radix);
2097 // Enter digit traversal loop
2098 for (StringRef::iterator e = str.end(); p != e; ++p) {
2099 unsigned digit = getDigit(*p, radix);
2100 assert(digit < radix && "Invalid character in digit string");
2102 // Shift or multiply the value by the radix
2110 // Add in the digit we just interpreted
2111 if (apdigit.isSingleWord())
2112 apdigit.VAL = digit;
2114 apdigit.pVal[0] = digit;
2117 // If its negative, put it in two's complement form
2120 this->flipAllBits();
2124 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2125 bool Signed, bool formatAsCLiteral) const {
2126 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2128 "Radix should be 2, 8, 10, 16, or 36!");
2130 const char *Prefix = "";
2131 if (formatAsCLiteral) {
2134 // Binary literals are a non-standard extension added in gcc 4.3:
2135 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2147 llvm_unreachable("Invalid radix!");
2151 // First, check for a zero value and just short circuit the logic below.
2154 Str.push_back(*Prefix);
2161 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2163 if (isSingleWord()) {
2165 char *BufPtr = Buffer+65;
2171 int64_t I = getSExtValue();
2181 Str.push_back(*Prefix);
2186 *--BufPtr = Digits[N % Radix];
2189 Str.append(BufPtr, Buffer+65);
2195 if (Signed && isNegative()) {
2196 // They want to print the signed version and it is a negative value
2197 // Flip the bits and add one to turn it into the equivalent positive
2198 // value and put a '-' in the result.
2205 Str.push_back(*Prefix);
2209 // We insert the digits backward, then reverse them to get the right order.
2210 unsigned StartDig = Str.size();
2212 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2213 // because the number of bits per digit (1, 3 and 4 respectively) divides
2214 // equaly. We just shift until the value is zero.
2215 if (Radix == 2 || Radix == 8 || Radix == 16) {
2216 // Just shift tmp right for each digit width until it becomes zero
2217 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2218 unsigned MaskAmt = Radix - 1;
2221 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2222 Str.push_back(Digits[Digit]);
2223 Tmp = Tmp.lshr(ShiftAmt);
2226 APInt divisor(Radix == 10? 4 : 8, Radix);
2228 APInt APdigit(1, 0);
2229 APInt tmp2(Tmp.getBitWidth(), 0);
2230 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2232 unsigned Digit = (unsigned)APdigit.getZExtValue();
2233 assert(Digit < Radix && "divide failed");
2234 Str.push_back(Digits[Digit]);
2239 // Reverse the digits before returning.
2240 std::reverse(Str.begin()+StartDig, Str.end());
2243 /// toString - This returns the APInt as a std::string. Note that this is an
2244 /// inefficient method. It is better to pass in a SmallVector/SmallString
2245 /// to the methods above.
2246 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2248 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2253 void APInt::dump() const {
2254 SmallString<40> S, U;
2255 this->toStringUnsigned(U);
2256 this->toStringSigned(S);
2257 dbgs() << "APInt(" << BitWidth << "b, "
2258 << U.str() << "u " << S.str() << "s)";
2261 void APInt::print(raw_ostream &OS, bool isSigned) const {
2263 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2267 // This implements a variety of operations on a representation of
2268 // arbitrary precision, two's-complement, bignum integer values.
2270 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2271 // and unrestricting assumption.
2272 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2273 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2275 /* Some handy functions local to this file. */
2278 /* Returns the integer part with the least significant BITS set.
2279 BITS cannot be zero. */
2280 static inline integerPart
2281 lowBitMask(unsigned int bits)
2283 assert(bits != 0 && bits <= integerPartWidth);
2285 return ~(integerPart) 0 >> (integerPartWidth - bits);
2288 /* Returns the value of the lower half of PART. */
2289 static inline integerPart
2290 lowHalf(integerPart part)
2292 return part & lowBitMask(integerPartWidth / 2);
2295 /* Returns the value of the upper half of PART. */
2296 static inline integerPart
2297 highHalf(integerPart part)
2299 return part >> (integerPartWidth / 2);
2302 /* Returns the bit number of the most significant set bit of a part.
2303 If the input number has no bits set -1U is returned. */
2305 partMSB(integerPart value)
2307 return findLastSet(value, ZB_Max);
2310 /* Returns the bit number of the least significant set bit of a
2311 part. If the input number has no bits set -1U is returned. */
2313 partLSB(integerPart value)
2315 return findFirstSet(value, ZB_Max);
2319 /* Sets the least significant part of a bignum to the input value, and
2320 zeroes out higher parts. */
2322 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2329 for (i = 1; i < parts; i++)
2333 /* Assign one bignum to another. */
2335 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2339 for (i = 0; i < parts; i++)
2343 /* Returns true if a bignum is zero, false otherwise. */
2345 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2349 for (i = 0; i < parts; i++)
2356 /* Extract the given bit of a bignum; returns 0 or 1. */
2358 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2360 return (parts[bit / integerPartWidth] &
2361 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2364 /* Set the given bit of a bignum. */
2366 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2368 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2371 /* Clears the given bit of a bignum. */
2373 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2375 parts[bit / integerPartWidth] &=
2376 ~((integerPart) 1 << (bit % integerPartWidth));
2379 /* Returns the bit number of the least significant set bit of a
2380 number. If the input number has no bits set -1U is returned. */
2382 APInt::tcLSB(const integerPart *parts, unsigned int n)
2384 unsigned int i, lsb;
2386 for (i = 0; i < n; i++) {
2387 if (parts[i] != 0) {
2388 lsb = partLSB(parts[i]);
2390 return lsb + i * integerPartWidth;
2397 /* Returns the bit number of the most significant set bit of a number.
2398 If the input number has no bits set -1U is returned. */
2400 APInt::tcMSB(const integerPart *parts, unsigned int n)
2407 if (parts[n] != 0) {
2408 msb = partMSB(parts[n]);
2410 return msb + n * integerPartWidth;
2417 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2418 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2419 the least significant bit of DST. All high bits above srcBITS in
2420 DST are zero-filled. */
2422 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2423 unsigned int srcBits, unsigned int srcLSB)
2425 unsigned int firstSrcPart, dstParts, shift, n;
2427 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2428 assert(dstParts <= dstCount);
2430 firstSrcPart = srcLSB / integerPartWidth;
2431 tcAssign (dst, src + firstSrcPart, dstParts);
2433 shift = srcLSB % integerPartWidth;
2434 tcShiftRight (dst, dstParts, shift);
2436 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2437 in DST. If this is less that srcBits, append the rest, else
2438 clear the high bits. */
2439 n = dstParts * integerPartWidth - shift;
2441 integerPart mask = lowBitMask (srcBits - n);
2442 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2443 << n % integerPartWidth);
2444 } else if (n > srcBits) {
2445 if (srcBits % integerPartWidth)
2446 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2449 /* Clear high parts. */
2450 while (dstParts < dstCount)
2451 dst[dstParts++] = 0;
2454 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2456 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2457 integerPart c, unsigned int parts)
2463 for (i = 0; i < parts; i++) {
2468 dst[i] += rhs[i] + 1;
2479 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2481 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2482 integerPart c, unsigned int parts)
2488 for (i = 0; i < parts; i++) {
2493 dst[i] -= rhs[i] + 1;
2504 /* Negate a bignum in-place. */
2506 APInt::tcNegate(integerPart *dst, unsigned int parts)
2508 tcComplement(dst, parts);
2509 tcIncrement(dst, parts);
2512 /* DST += SRC * MULTIPLIER + CARRY if add is true
2513 DST = SRC * MULTIPLIER + CARRY if add is false
2515 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2516 they must start at the same point, i.e. DST == SRC.
2518 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2519 returned. Otherwise DST is filled with the least significant
2520 DSTPARTS parts of the result, and if all of the omitted higher
2521 parts were zero return zero, otherwise overflow occurred and
2524 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2525 integerPart multiplier, integerPart carry,
2526 unsigned int srcParts, unsigned int dstParts,
2531 /* Otherwise our writes of DST kill our later reads of SRC. */
2532 assert(dst <= src || dst >= src + srcParts);
2533 assert(dstParts <= srcParts + 1);
2535 /* N loops; minimum of dstParts and srcParts. */
2536 n = dstParts < srcParts ? dstParts: srcParts;
2538 for (i = 0; i < n; i++) {
2539 integerPart low, mid, high, srcPart;
2541 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2543 This cannot overflow, because
2545 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2547 which is less than n^2. */
2551 if (multiplier == 0 || srcPart == 0) {
2555 low = lowHalf(srcPart) * lowHalf(multiplier);
2556 high = highHalf(srcPart) * highHalf(multiplier);
2558 mid = lowHalf(srcPart) * highHalf(multiplier);
2559 high += highHalf(mid);
2560 mid <<= integerPartWidth / 2;
2561 if (low + mid < low)
2565 mid = highHalf(srcPart) * lowHalf(multiplier);
2566 high += highHalf(mid);
2567 mid <<= integerPartWidth / 2;
2568 if (low + mid < low)
2572 /* Now add carry. */
2573 if (low + carry < low)
2579 /* And now DST[i], and store the new low part there. */
2580 if (low + dst[i] < low)
2590 /* Full multiplication, there is no overflow. */
2591 assert(i + 1 == dstParts);
2595 /* We overflowed if there is carry. */
2599 /* We would overflow if any significant unwritten parts would be
2600 non-zero. This is true if any remaining src parts are non-zero
2601 and the multiplier is non-zero. */
2603 for (; i < srcParts; i++)
2607 /* We fitted in the narrow destination. */
2612 /* DST = LHS * RHS, where DST has the same width as the operands and
2613 is filled with the least significant parts of the result. Returns
2614 one if overflow occurred, otherwise zero. DST must be disjoint
2615 from both operands. */
2617 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2618 const integerPart *rhs, unsigned int parts)
2623 assert(dst != lhs && dst != rhs);
2626 tcSet(dst, 0, parts);
2628 for (i = 0; i < parts; i++)
2629 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2635 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2636 operands. No overflow occurs. DST must be disjoint from both
2637 operands. Returns the number of parts required to hold the
2640 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2641 const integerPart *rhs, unsigned int lhsParts,
2642 unsigned int rhsParts)
2644 /* Put the narrower number on the LHS for less loops below. */
2645 if (lhsParts > rhsParts) {
2646 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2650 assert(dst != lhs && dst != rhs);
2652 tcSet(dst, 0, rhsParts);
2654 for (n = 0; n < lhsParts; n++)
2655 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2657 n = lhsParts + rhsParts;
2659 return n - (dst[n - 1] == 0);
2663 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2664 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2665 set REMAINDER to the remainder, return zero. i.e.
2667 OLD_LHS = RHS * LHS + REMAINDER
2669 SCRATCH is a bignum of the same size as the operands and result for
2670 use by the routine; its contents need not be initialized and are
2671 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2674 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2675 integerPart *remainder, integerPart *srhs,
2678 unsigned int n, shiftCount;
2681 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2683 shiftCount = tcMSB(rhs, parts) + 1;
2684 if (shiftCount == 0)
2687 shiftCount = parts * integerPartWidth - shiftCount;
2688 n = shiftCount / integerPartWidth;
2689 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2691 tcAssign(srhs, rhs, parts);
2692 tcShiftLeft(srhs, parts, shiftCount);
2693 tcAssign(remainder, lhs, parts);
2694 tcSet(lhs, 0, parts);
2696 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2701 compare = tcCompare(remainder, srhs, parts);
2703 tcSubtract(remainder, srhs, 0, parts);
2707 if (shiftCount == 0)
2710 tcShiftRight(srhs, parts, 1);
2711 if ((mask >>= 1) == 0)
2712 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2718 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2719 There are no restrictions on COUNT. */
2721 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2724 unsigned int jump, shift;
2726 /* Jump is the inter-part jump; shift is is intra-part shift. */
2727 jump = count / integerPartWidth;
2728 shift = count % integerPartWidth;
2730 while (parts > jump) {
2735 /* dst[i] comes from the two parts src[i - jump] and, if we have
2736 an intra-part shift, src[i - jump - 1]. */
2737 part = dst[parts - jump];
2740 if (parts >= jump + 1)
2741 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2752 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2753 zero. There are no restrictions on COUNT. */
2755 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2758 unsigned int i, jump, shift;
2760 /* Jump is the inter-part jump; shift is is intra-part shift. */
2761 jump = count / integerPartWidth;
2762 shift = count % integerPartWidth;
2764 /* Perform the shift. This leaves the most significant COUNT bits
2765 of the result at zero. */
2766 for (i = 0; i < parts; i++) {
2769 if (i + jump >= parts) {
2772 part = dst[i + jump];
2775 if (i + jump + 1 < parts)
2776 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2785 /* Bitwise and of two bignums. */
2787 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2791 for (i = 0; i < parts; i++)
2795 /* Bitwise inclusive or of two bignums. */
2797 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2801 for (i = 0; i < parts; i++)
2805 /* Bitwise exclusive or of two bignums. */
2807 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2811 for (i = 0; i < parts; i++)
2815 /* Complement a bignum in-place. */
2817 APInt::tcComplement(integerPart *dst, unsigned int parts)
2821 for (i = 0; i < parts; i++)
2825 /* Comparison (unsigned) of two bignums. */
2827 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2832 if (lhs[parts] == rhs[parts])
2835 if (lhs[parts] > rhs[parts])
2844 /* Increment a bignum in-place, return the carry flag. */
2846 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2850 for (i = 0; i < parts; i++)
2857 /* Decrement a bignum in-place, return the borrow flag. */
2859 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2860 for (unsigned int i = 0; i < parts; i++) {
2861 // If the current word is non-zero, then the decrement has no effect on the
2862 // higher-order words of the integer and no borrow can occur. Exit early.
2866 // If every word was zero, then there is a borrow.
2871 /* Set the least significant BITS bits of a bignum, clear the
2874 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2880 while (bits > integerPartWidth) {
2881 dst[i++] = ~(integerPart) 0;
2882 bits -= integerPartWidth;
2886 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);