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::operator[](unsigned bitPosition) const {
488 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
489 return (maskBit(bitPosition) &
490 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
493 bool APInt::EqualSlowCase(const APInt& RHS) const {
494 // Get some facts about the number of bits used in the two operands.
495 unsigned n1 = getActiveBits();
496 unsigned n2 = RHS.getActiveBits();
498 // If the number of bits isn't the same, they aren't equal
502 // If the number of bits fits in a word, we only need to compare the low word.
503 if (n1 <= APINT_BITS_PER_WORD)
504 return pVal[0] == RHS.pVal[0];
506 // Otherwise, compare everything
507 for (int i = whichWord(n1 - 1); i >= 0; --i)
508 if (pVal[i] != RHS.pVal[i])
513 bool APInt::EqualSlowCase(uint64_t Val) const {
514 unsigned n = getActiveBits();
515 if (n <= APINT_BITS_PER_WORD)
516 return pVal[0] == Val;
521 bool APInt::ult(const APInt& RHS) const {
522 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
524 return VAL < RHS.VAL;
526 // Get active bit length of both operands
527 unsigned n1 = getActiveBits();
528 unsigned n2 = RHS.getActiveBits();
530 // If magnitude of LHS is less than RHS, return true.
534 // If magnitude of RHS is greather than LHS, return false.
538 // If they bot fit in a word, just compare the low order word
539 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
540 return pVal[0] < RHS.pVal[0];
542 // Otherwise, compare all words
543 unsigned topWord = whichWord(std::max(n1,n2)-1);
544 for (int i = topWord; i >= 0; --i) {
545 if (pVal[i] > RHS.pVal[i])
547 if (pVal[i] < RHS.pVal[i])
553 bool APInt::slt(const APInt& RHS) const {
554 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
555 if (isSingleWord()) {
556 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
557 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
558 return lhsSext < rhsSext;
563 bool lhsNeg = isNegative();
564 bool rhsNeg = rhs.isNegative();
566 // Sign bit is set so perform two's complement to make it positive
571 // Sign bit is set so perform two's complement to make it positive
576 // Now we have unsigned values to compare so do the comparison if necessary
577 // based on the negativeness of the values.
589 void APInt::setBit(unsigned bitPosition) {
591 VAL |= maskBit(bitPosition);
593 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
596 /// Set the given bit to 0 whose position is given as "bitPosition".
597 /// @brief Set a given bit to 0.
598 void APInt::clearBit(unsigned bitPosition) {
600 VAL &= ~maskBit(bitPosition);
602 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
605 /// @brief Toggle every bit to its opposite value.
607 /// Toggle a given bit to its opposite value whose position is given
608 /// as "bitPosition".
609 /// @brief Toggles a given bit to its opposite value.
610 void APInt::flipBit(unsigned bitPosition) {
611 assert(bitPosition < BitWidth && "Out of the bit-width range!");
612 if ((*this)[bitPosition]) clearBit(bitPosition);
613 else setBit(bitPosition);
616 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
617 assert(!str.empty() && "Invalid string length");
618 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
620 "Radix should be 2, 8, 10, 16, or 36!");
622 size_t slen = str.size();
624 // Each computation below needs to know if it's negative.
625 StringRef::iterator p = str.begin();
626 unsigned isNegative = *p == '-';
627 if (*p == '-' || *p == '+') {
630 assert(slen && "String is only a sign, needs a value.");
633 // For radixes of power-of-two values, the bits required is accurately and
636 return slen + isNegative;
638 return slen * 3 + isNegative;
640 return slen * 4 + isNegative;
644 // This is grossly inefficient but accurate. We could probably do something
645 // with a computation of roughly slen*64/20 and then adjust by the value of
646 // the first few digits. But, I'm not sure how accurate that could be.
648 // Compute a sufficient number of bits that is always large enough but might
649 // be too large. This avoids the assertion in the constructor. This
650 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
651 // bits in that case.
653 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
654 : (slen == 1 ? 7 : slen * 16/3);
656 // Convert to the actual binary value.
657 APInt tmp(sufficient, StringRef(p, slen), radix);
659 // Compute how many bits are required. If the log is infinite, assume we need
661 unsigned log = tmp.logBase2();
662 if (log == (unsigned)-1) {
663 return isNegative + 1;
665 return isNegative + log + 1;
669 hash_code llvm::hash_value(const APInt &Arg) {
670 if (Arg.isSingleWord())
671 return hash_combine(Arg.VAL);
673 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
676 /// HiBits - This function returns the high "numBits" bits of this APInt.
677 APInt APInt::getHiBits(unsigned numBits) const {
678 return APIntOps::lshr(*this, BitWidth - numBits);
681 /// LoBits - This function returns the low "numBits" bits of this APInt.
682 APInt APInt::getLoBits(unsigned numBits) const {
683 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
687 unsigned APInt::countLeadingZerosSlowCase() const {
688 // Treat the most significand word differently because it might have
689 // meaningless bits set beyond the precision.
690 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
692 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
694 MSWMask = ~integerPart(0);
695 BitsInMSW = APINT_BITS_PER_WORD;
698 unsigned i = getNumWords();
699 integerPart MSW = pVal[i-1] & MSWMask;
701 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
703 unsigned Count = BitsInMSW;
704 for (--i; i > 0u; --i) {
706 Count += APINT_BITS_PER_WORD;
708 Count += CountLeadingZeros_64(pVal[i-1]);
715 unsigned APInt::countLeadingOnes() const {
717 return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
719 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
722 highWordBits = APINT_BITS_PER_WORD;
725 shift = APINT_BITS_PER_WORD - highWordBits;
727 int i = getNumWords() - 1;
728 unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
729 if (Count == highWordBits) {
730 for (i--; i >= 0; --i) {
731 if (pVal[i] == -1ULL)
732 Count += APINT_BITS_PER_WORD;
734 Count += CountLeadingOnes_64(pVal[i]);
742 unsigned APInt::countTrailingZeros() const {
744 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
747 for (; i < getNumWords() && pVal[i] == 0; ++i)
748 Count += APINT_BITS_PER_WORD;
749 if (i < getNumWords())
750 Count += CountTrailingZeros_64(pVal[i]);
751 return std::min(Count, BitWidth);
754 unsigned APInt::countTrailingOnesSlowCase() const {
757 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
758 Count += APINT_BITS_PER_WORD;
759 if (i < getNumWords())
760 Count += CountTrailingOnes_64(pVal[i]);
761 return std::min(Count, BitWidth);
764 unsigned APInt::countPopulationSlowCase() const {
766 for (unsigned i = 0; i < getNumWords(); ++i)
767 Count += CountPopulation_64(pVal[i]);
771 /// Perform a logical right-shift from Src to Dst, which must be equal or
772 /// non-overlapping, of Words words, by Shift, which must be less than 64.
773 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
776 for (int I = Words - 1; I >= 0; --I) {
777 uint64_t Tmp = Src[I];
778 Dst[I] = (Tmp >> Shift) | Carry;
779 Carry = Tmp << (64 - Shift);
783 APInt APInt::byteSwap() const {
784 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
786 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
788 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
789 if (BitWidth == 48) {
790 unsigned Tmp1 = unsigned(VAL >> 16);
791 Tmp1 = ByteSwap_32(Tmp1);
792 uint16_t Tmp2 = uint16_t(VAL);
793 Tmp2 = ByteSwap_16(Tmp2);
794 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
797 return APInt(BitWidth, ByteSwap_64(VAL));
799 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
800 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
801 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
802 if (Result.BitWidth != BitWidth) {
803 lshrNear(Result.pVal, Result.pVal, getNumWords(),
804 Result.BitWidth - BitWidth);
805 Result.BitWidth = BitWidth;
810 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
812 APInt A = API1, B = API2;
815 B = APIntOps::urem(A, B);
821 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
828 // Get the sign bit from the highest order bit
829 bool isNeg = T.I >> 63;
831 // Get the 11-bit exponent and adjust for the 1023 bit bias
832 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
834 // If the exponent is negative, the value is < 0 so just return 0.
836 return APInt(width, 0u);
838 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
839 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
841 // If the exponent doesn't shift all bits out of the mantissa
843 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
844 APInt(width, mantissa >> (52 - exp));
846 // If the client didn't provide enough bits for us to shift the mantissa into
847 // then the result is undefined, just return 0
848 if (width <= exp - 52)
849 return APInt(width, 0);
851 // Otherwise, we have to shift the mantissa bits up to the right location
852 APInt Tmp(width, mantissa);
853 Tmp = Tmp.shl((unsigned)exp - 52);
854 return isNeg ? -Tmp : Tmp;
857 /// RoundToDouble - This function converts this APInt to a double.
858 /// The layout for double is as following (IEEE Standard 754):
859 /// --------------------------------------
860 /// | Sign Exponent Fraction Bias |
861 /// |-------------------------------------- |
862 /// | 1[63] 11[62-52] 52[51-00] 1023 |
863 /// --------------------------------------
864 double APInt::roundToDouble(bool isSigned) const {
866 // Handle the simple case where the value is contained in one uint64_t.
867 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
868 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
870 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
873 return double(getWord(0));
876 // Determine if the value is negative.
877 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
879 // Construct the absolute value if we're negative.
880 APInt Tmp(isNeg ? -(*this) : (*this));
882 // Figure out how many bits we're using.
883 unsigned n = Tmp.getActiveBits();
885 // The exponent (without bias normalization) is just the number of bits
886 // we are using. Note that the sign bit is gone since we constructed the
890 // Return infinity for exponent overflow
892 if (!isSigned || !isNeg)
893 return std::numeric_limits<double>::infinity();
895 return -std::numeric_limits<double>::infinity();
897 exp += 1023; // Increment for 1023 bias
899 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
900 // extract the high 52 bits from the correct words in pVal.
902 unsigned hiWord = whichWord(n-1);
904 mantissa = Tmp.pVal[0];
906 mantissa >>= n - 52; // shift down, we want the top 52 bits.
908 assert(hiWord > 0 && "huh?");
909 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
910 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
911 mantissa = hibits | lobits;
914 // The leading bit of mantissa is implicit, so get rid of it.
915 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
920 T.I = sign | (exp << 52) | mantissa;
924 // Truncate to new width.
925 APInt APInt::trunc(unsigned width) const {
926 assert(width < BitWidth && "Invalid APInt Truncate request");
927 assert(width && "Can't truncate to 0 bits");
929 if (width <= APINT_BITS_PER_WORD)
930 return APInt(width, getRawData()[0]);
932 APInt Result(getMemory(getNumWords(width)), width);
936 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
937 Result.pVal[i] = pVal[i];
939 // Truncate and copy any partial word.
940 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
942 Result.pVal[i] = pVal[i] << bits >> bits;
947 // Sign extend to a new width.
948 APInt APInt::sext(unsigned width) const {
949 assert(width > BitWidth && "Invalid APInt SignExtend request");
951 if (width <= APINT_BITS_PER_WORD) {
952 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
953 val = (int64_t)val >> (width - BitWidth);
954 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
957 APInt Result(getMemory(getNumWords(width)), width);
962 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
963 word = getRawData()[i];
964 Result.pVal[i] = word;
967 // Read and sign-extend any partial word.
968 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
970 word = (int64_t)getRawData()[i] << bits >> bits;
972 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
974 // Write remaining full words.
975 for (; i != width / APINT_BITS_PER_WORD; i++) {
976 Result.pVal[i] = word;
977 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
980 // Write any partial word.
981 bits = (0 - width) % APINT_BITS_PER_WORD;
983 Result.pVal[i] = word << bits >> bits;
988 // Zero extend to a new width.
989 APInt APInt::zext(unsigned width) const {
990 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
992 if (width <= APINT_BITS_PER_WORD)
993 return APInt(width, VAL);
995 APInt Result(getMemory(getNumWords(width)), width);
999 for (i = 0; i != getNumWords(); i++)
1000 Result.pVal[i] = getRawData()[i];
1002 // Zero remaining words.
1003 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1008 APInt APInt::zextOrTrunc(unsigned width) const {
1009 if (BitWidth < width)
1011 if (BitWidth > width)
1012 return trunc(width);
1016 APInt APInt::sextOrTrunc(unsigned width) const {
1017 if (BitWidth < width)
1019 if (BitWidth > width)
1020 return trunc(width);
1024 APInt APInt::zextOrSelf(unsigned width) const {
1025 if (BitWidth < width)
1030 APInt APInt::sextOrSelf(unsigned width) const {
1031 if (BitWidth < width)
1036 /// Arithmetic right-shift this APInt by shiftAmt.
1037 /// @brief Arithmetic right-shift function.
1038 APInt APInt::ashr(const APInt &shiftAmt) const {
1039 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1042 /// Arithmetic right-shift this APInt by shiftAmt.
1043 /// @brief Arithmetic right-shift function.
1044 APInt APInt::ashr(unsigned shiftAmt) const {
1045 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1046 // Handle a degenerate case
1050 // Handle single word shifts with built-in ashr
1051 if (isSingleWord()) {
1052 if (shiftAmt == BitWidth)
1053 return APInt(BitWidth, 0); // undefined
1055 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1056 return APInt(BitWidth,
1057 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1061 // If all the bits were shifted out, the result is, technically, undefined.
1062 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1063 // issues in the algorithm below.
1064 if (shiftAmt == BitWidth) {
1066 return APInt(BitWidth, -1ULL, true);
1068 return APInt(BitWidth, 0);
1071 // Create some space for the result.
1072 uint64_t * val = new uint64_t[getNumWords()];
1074 // Compute some values needed by the following shift algorithms
1075 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1076 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1077 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1078 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1079 if (bitsInWord == 0)
1080 bitsInWord = APINT_BITS_PER_WORD;
1082 // If we are shifting whole words, just move whole words
1083 if (wordShift == 0) {
1084 // Move the words containing significant bits
1085 for (unsigned i = 0; i <= breakWord; ++i)
1086 val[i] = pVal[i+offset]; // move whole word
1088 // Adjust the top significant word for sign bit fill, if negative
1090 if (bitsInWord < APINT_BITS_PER_WORD)
1091 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1093 // Shift the low order words
1094 for (unsigned i = 0; i < breakWord; ++i) {
1095 // This combines the shifted corresponding word with the low bits from
1096 // the next word (shifted into this word's high bits).
1097 val[i] = (pVal[i+offset] >> wordShift) |
1098 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1101 // Shift the break word. In this case there are no bits from the next word
1102 // to include in this word.
1103 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1105 // Deal with sign extenstion in the break word, and possibly the word before
1108 if (wordShift > bitsInWord) {
1111 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1112 val[breakWord] |= ~0ULL;
1114 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1118 // Remaining words are 0 or -1, just assign them.
1119 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1120 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1122 return APInt(val, BitWidth).clearUnusedBits();
1125 /// Logical right-shift this APInt by shiftAmt.
1126 /// @brief Logical right-shift function.
1127 APInt APInt::lshr(const APInt &shiftAmt) const {
1128 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1131 /// Logical right-shift this APInt by shiftAmt.
1132 /// @brief Logical right-shift function.
1133 APInt APInt::lshr(unsigned shiftAmt) const {
1134 if (isSingleWord()) {
1135 if (shiftAmt >= BitWidth)
1136 return APInt(BitWidth, 0);
1138 return APInt(BitWidth, this->VAL >> shiftAmt);
1141 // If all the bits were shifted out, the result is 0. This avoids issues
1142 // with shifting by the size of the integer type, which produces undefined
1143 // results. We define these "undefined results" to always be 0.
1144 if (shiftAmt == BitWidth)
1145 return APInt(BitWidth, 0);
1147 // If none of the bits are shifted out, the result is *this. This avoids
1148 // issues with shifting by the size of the integer type, which produces
1149 // undefined results in the code below. This is also an optimization.
1153 // Create some space for the result.
1154 uint64_t * val = new uint64_t[getNumWords()];
1156 // If we are shifting less than a word, compute the shift with a simple carry
1157 if (shiftAmt < APINT_BITS_PER_WORD) {
1158 lshrNear(val, pVal, getNumWords(), shiftAmt);
1159 return APInt(val, BitWidth).clearUnusedBits();
1162 // Compute some values needed by the remaining shift algorithms
1163 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1164 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1166 // If we are shifting whole words, just move whole words
1167 if (wordShift == 0) {
1168 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1169 val[i] = pVal[i+offset];
1170 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1172 return APInt(val,BitWidth).clearUnusedBits();
1175 // Shift the low order words
1176 unsigned breakWord = getNumWords() - offset -1;
1177 for (unsigned i = 0; i < breakWord; ++i)
1178 val[i] = (pVal[i+offset] >> wordShift) |
1179 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1180 // Shift the break word.
1181 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1183 // Remaining words are 0
1184 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1186 return APInt(val, BitWidth).clearUnusedBits();
1189 /// Left-shift this APInt by shiftAmt.
1190 /// @brief Left-shift function.
1191 APInt APInt::shl(const APInt &shiftAmt) const {
1192 // It's undefined behavior in C to shift by BitWidth or greater.
1193 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1196 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1197 // If all the bits were shifted out, the result is 0. This avoids issues
1198 // with shifting by the size of the integer type, which produces undefined
1199 // results. We define these "undefined results" to always be 0.
1200 if (shiftAmt == BitWidth)
1201 return APInt(BitWidth, 0);
1203 // If none of the bits are shifted out, the result is *this. This avoids a
1204 // lshr by the words size in the loop below which can produce incorrect
1205 // results. It also avoids the expensive computation below for a common case.
1209 // Create some space for the result.
1210 uint64_t * val = new uint64_t[getNumWords()];
1212 // If we are shifting less than a word, do it the easy way
1213 if (shiftAmt < APINT_BITS_PER_WORD) {
1215 for (unsigned i = 0; i < getNumWords(); i++) {
1216 val[i] = pVal[i] << shiftAmt | carry;
1217 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1219 return APInt(val, BitWidth).clearUnusedBits();
1222 // Compute some values needed by the remaining shift algorithms
1223 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1224 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1226 // If we are shifting whole words, just move whole words
1227 if (wordShift == 0) {
1228 for (unsigned i = 0; i < offset; i++)
1230 for (unsigned i = offset; i < getNumWords(); i++)
1231 val[i] = pVal[i-offset];
1232 return APInt(val,BitWidth).clearUnusedBits();
1235 // Copy whole words from this to Result.
1236 unsigned i = getNumWords() - 1;
1237 for (; i > offset; --i)
1238 val[i] = pVal[i-offset] << wordShift |
1239 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1240 val[offset] = pVal[0] << wordShift;
1241 for (i = 0; i < offset; ++i)
1243 return APInt(val, BitWidth).clearUnusedBits();
1246 APInt APInt::rotl(const APInt &rotateAmt) const {
1247 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1250 APInt APInt::rotl(unsigned rotateAmt) const {
1251 rotateAmt %= BitWidth;
1254 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1257 APInt APInt::rotr(const APInt &rotateAmt) const {
1258 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1261 APInt APInt::rotr(unsigned rotateAmt) const {
1262 rotateAmt %= BitWidth;
1265 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1268 // Square Root - this method computes and returns the square root of "this".
1269 // Three mechanisms are used for computation. For small values (<= 5 bits),
1270 // a table lookup is done. This gets some performance for common cases. For
1271 // values using less than 52 bits, the value is converted to double and then
1272 // the libc sqrt function is called. The result is rounded and then converted
1273 // back to a uint64_t which is then used to construct the result. Finally,
1274 // the Babylonian method for computing square roots is used.
1275 APInt APInt::sqrt() const {
1277 // Determine the magnitude of the value.
1278 unsigned magnitude = getActiveBits();
1280 // Use a fast table for some small values. This also gets rid of some
1281 // rounding errors in libc sqrt for small values.
1282 if (magnitude <= 5) {
1283 static const uint8_t results[32] = {
1286 /* 3- 6 */ 2, 2, 2, 2,
1287 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1288 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1289 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1292 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1295 // If the magnitude of the value fits in less than 52 bits (the precision of
1296 // an IEEE double precision floating point value), then we can use the
1297 // libc sqrt function which will probably use a hardware sqrt computation.
1298 // This should be faster than the algorithm below.
1299 if (magnitude < 52) {
1301 return APInt(BitWidth,
1302 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1304 return APInt(BitWidth,
1305 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1309 // Okay, all the short cuts are exhausted. We must compute it. The following
1310 // is a classical Babylonian method for computing the square root. This code
1311 // was adapted to APINt from a wikipedia article on such computations.
1312 // See http://www.wikipedia.org/ and go to the page named
1313 // Calculate_an_integer_square_root.
1314 unsigned nbits = BitWidth, i = 4;
1315 APInt testy(BitWidth, 16);
1316 APInt x_old(BitWidth, 1);
1317 APInt x_new(BitWidth, 0);
1318 APInt two(BitWidth, 2);
1320 // Select a good starting value using binary logarithms.
1321 for (;; i += 2, testy = testy.shl(2))
1322 if (i >= nbits || this->ule(testy)) {
1323 x_old = x_old.shl(i / 2);
1327 // Use the Babylonian method to arrive at the integer square root:
1329 x_new = (this->udiv(x_old) + x_old).udiv(two);
1330 if (x_old.ule(x_new))
1335 // Make sure we return the closest approximation
1336 // NOTE: The rounding calculation below is correct. It will produce an
1337 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1338 // determined to be a rounding issue with pari/gp as it begins to use a
1339 // floating point representation after 192 bits. There are no discrepancies
1340 // between this algorithm and pari/gp for bit widths < 192 bits.
1341 APInt square(x_old * x_old);
1342 APInt nextSquare((x_old + 1) * (x_old +1));
1343 if (this->ult(square))
1345 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1346 APInt midpoint((nextSquare - square).udiv(two));
1347 APInt offset(*this - square);
1348 if (offset.ult(midpoint))
1353 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1354 /// iterative extended Euclidean algorithm is used to solve for this value,
1355 /// however we simplify it to speed up calculating only the inverse, and take
1356 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1357 /// (potentially large) APInts around.
1358 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1359 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1361 // Using the properties listed at the following web page (accessed 06/21/08):
1362 // http://www.numbertheory.org/php/euclid.html
1363 // (especially the properties numbered 3, 4 and 9) it can be proved that
1364 // BitWidth bits suffice for all the computations in the algorithm implemented
1365 // below. More precisely, this number of bits suffice if the multiplicative
1366 // inverse exists, but may not suffice for the general extended Euclidean
1369 APInt r[2] = { modulo, *this };
1370 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1371 APInt q(BitWidth, 0);
1374 for (i = 0; r[i^1] != 0; i ^= 1) {
1375 // An overview of the math without the confusing bit-flipping:
1376 // q = r[i-2] / r[i-1]
1377 // r[i] = r[i-2] % r[i-1]
1378 // t[i] = t[i-2] - t[i-1] * q
1379 udivrem(r[i], r[i^1], q, r[i]);
1383 // If this APInt and the modulo are not coprime, there is no multiplicative
1384 // inverse, so return 0. We check this by looking at the next-to-last
1385 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1388 return APInt(BitWidth, 0);
1390 // The next-to-last t is the multiplicative inverse. However, we are
1391 // interested in a positive inverse. Calcuate a positive one from a negative
1392 // one if necessary. A simple addition of the modulo suffices because
1393 // abs(t[i]) is known to be less than *this/2 (see the link above).
1394 return t[i].isNegative() ? t[i] + modulo : t[i];
1397 /// Calculate the magic numbers required to implement a signed integer division
1398 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1399 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1400 /// Warren, Jr., chapter 10.
1401 APInt::ms APInt::magic() const {
1402 const APInt& d = *this;
1404 APInt ad, anc, delta, q1, r1, q2, r2, t;
1405 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1409 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1410 anc = t - 1 - t.urem(ad); // absolute value of nc
1411 p = d.getBitWidth() - 1; // initialize p
1412 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1413 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1414 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1415 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1418 q1 = q1<<1; // update q1 = 2p/abs(nc)
1419 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1420 if (r1.uge(anc)) { // must be unsigned comparison
1424 q2 = q2<<1; // update q2 = 2p/abs(d)
1425 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1426 if (r2.uge(ad)) { // must be unsigned comparison
1431 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1434 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1435 mag.s = p - d.getBitWidth(); // resulting shift
1439 /// Calculate the magic numbers required to implement an unsigned integer
1440 /// division by a constant as a sequence of multiplies, adds and shifts.
1441 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1442 /// S. Warren, Jr., chapter 10.
1443 /// LeadingZeros can be used to simplify the calculation if the upper bits
1444 /// of the divided value are known zero.
1445 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1446 const APInt& d = *this;
1448 APInt nc, delta, q1, r1, q2, r2;
1450 magu.a = 0; // initialize "add" indicator
1451 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1452 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1453 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1455 nc = allOnes - (-d).urem(d);
1456 p = d.getBitWidth() - 1; // initialize p
1457 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1458 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1459 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1460 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1463 if (r1.uge(nc - r1)) {
1464 q1 = q1 + q1 + 1; // update q1
1465 r1 = r1 + r1 - nc; // update r1
1468 q1 = q1+q1; // update q1
1469 r1 = r1+r1; // update r1
1471 if ((r2 + 1).uge(d - r2)) {
1472 if (q2.uge(signedMax)) magu.a = 1;
1473 q2 = q2+q2 + 1; // update q2
1474 r2 = r2+r2 + 1 - d; // update r2
1477 if (q2.uge(signedMin)) magu.a = 1;
1478 q2 = q2+q2; // update q2
1479 r2 = r2+r2 + 1; // update r2
1482 } while (p < d.getBitWidth()*2 &&
1483 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1484 magu.m = q2 + 1; // resulting magic number
1485 magu.s = p - d.getBitWidth(); // resulting shift
1489 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1490 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1491 /// variables here have the same names as in the algorithm. Comments explain
1492 /// the algorithm and any deviation from it.
1493 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1494 unsigned m, unsigned n) {
1495 assert(u && "Must provide dividend");
1496 assert(v && "Must provide divisor");
1497 assert(q && "Must provide quotient");
1498 assert(u != v && u != q && v != q && "Must us different memory");
1499 assert(n>1 && "n must be > 1");
1501 // Knuth uses the value b as the base of the number system. In our case b
1502 // is 2^31 so we just set it to -1u.
1503 uint64_t b = uint64_t(1) << 32;
1506 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1507 DEBUG(dbgs() << "KnuthDiv: original:");
1508 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1509 DEBUG(dbgs() << " by");
1510 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1511 DEBUG(dbgs() << '\n');
1513 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1514 // u and v by d. Note that we have taken Knuth's advice here to use a power
1515 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1516 // 2 allows us to shift instead of multiply and it is easy to determine the
1517 // shift amount from the leading zeros. We are basically normalizing the u
1518 // and v so that its high bits are shifted to the top of v's range without
1519 // overflow. Note that this can require an extra word in u so that u must
1520 // be of length m+n+1.
1521 unsigned shift = CountLeadingZeros_32(v[n-1]);
1522 unsigned v_carry = 0;
1523 unsigned u_carry = 0;
1525 for (unsigned i = 0; i < m+n; ++i) {
1526 unsigned u_tmp = u[i] >> (32 - shift);
1527 u[i] = (u[i] << shift) | u_carry;
1530 for (unsigned i = 0; i < n; ++i) {
1531 unsigned v_tmp = v[i] >> (32 - shift);
1532 v[i] = (v[i] << shift) | v_carry;
1538 DEBUG(dbgs() << "KnuthDiv: normal:");
1539 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1540 DEBUG(dbgs() << " by");
1541 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1542 DEBUG(dbgs() << '\n');
1545 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1548 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1549 // D3. [Calculate q'.].
1550 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1551 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1552 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1553 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1554 // on v[n-2] determines at high speed most of the cases in which the trial
1555 // value qp is one too large, and it eliminates all cases where qp is two
1557 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1558 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1559 uint64_t qp = dividend / v[n-1];
1560 uint64_t rp = dividend % v[n-1];
1561 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1564 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1567 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1569 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1570 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1571 // consists of a simple multiplication by a one-place number, combined with
1574 for (unsigned i = 0; i < n; ++i) {
1575 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1576 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1577 bool borrow = subtrahend > u_tmp;
1578 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1579 << ", subtrahend == " << subtrahend
1580 << ", borrow = " << borrow << '\n');
1582 uint64_t result = u_tmp - subtrahend;
1584 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1585 u[k++] = (unsigned)(result >> 32); // subtract high word
1586 while (borrow && k <= m+n) { // deal with borrow to the left
1592 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1595 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1596 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1597 DEBUG(dbgs() << '\n');
1598 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1599 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1600 // true value plus b**(n+1), namely as the b's complement of
1601 // the true value, and a "borrow" to the left should be remembered.
1604 bool carry = true; // true because b's complement is "complement + 1"
1605 for (unsigned i = 0; i <= m+n; ++i) {
1606 u[i] = ~u[i] + carry; // b's complement
1607 carry = carry && u[i] == 0;
1610 DEBUG(dbgs() << "KnuthDiv: after complement:");
1611 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1612 DEBUG(dbgs() << '\n');
1614 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1615 // negative, go to step D6; otherwise go on to step D7.
1616 q[j] = (unsigned)qp;
1618 // D6. [Add back]. The probability that this step is necessary is very
1619 // small, on the order of only 2/b. Make sure that test data accounts for
1620 // this possibility. Decrease q[j] by 1
1622 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1623 // A carry will occur to the left of u[j+n], and it should be ignored
1624 // since it cancels with the borrow that occurred in D4.
1626 for (unsigned i = 0; i < n; i++) {
1627 unsigned limit = std::min(u[j+i],v[i]);
1628 u[j+i] += v[i] + carry;
1629 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1633 DEBUG(dbgs() << "KnuthDiv: after correction:");
1634 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1635 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1637 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1640 DEBUG(dbgs() << "KnuthDiv: quotient:");
1641 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1642 DEBUG(dbgs() << '\n');
1644 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1645 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1646 // compute the remainder (urem uses this).
1648 // The value d is expressed by the "shift" value above since we avoided
1649 // multiplication by d by using a shift left. So, all we have to do is
1650 // shift right here. In order to mak
1653 DEBUG(dbgs() << "KnuthDiv: remainder:");
1654 for (int i = n-1; i >= 0; i--) {
1655 r[i] = (u[i] >> shift) | carry;
1656 carry = u[i] << (32 - shift);
1657 DEBUG(dbgs() << " " << r[i]);
1660 for (int i = n-1; i >= 0; i--) {
1662 DEBUG(dbgs() << " " << r[i]);
1665 DEBUG(dbgs() << '\n');
1668 DEBUG(dbgs() << '\n');
1672 void APInt::divide(const APInt LHS, unsigned lhsWords,
1673 const APInt &RHS, unsigned rhsWords,
1674 APInt *Quotient, APInt *Remainder)
1676 assert(lhsWords >= rhsWords && "Fractional result");
1678 // First, compose the values into an array of 32-bit words instead of
1679 // 64-bit words. This is a necessity of both the "short division" algorithm
1680 // and the Knuth "classical algorithm" which requires there to be native
1681 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1682 // can't use 64-bit operands here because we don't have native results of
1683 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1684 // work on large-endian machines.
1685 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1686 unsigned n = rhsWords * 2;
1687 unsigned m = (lhsWords * 2) - n;
1689 // Allocate space for the temporary values we need either on the stack, if
1690 // it will fit, or on the heap if it won't.
1691 unsigned SPACE[128];
1696 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1699 Q = &SPACE[(m+n+1) + n];
1701 R = &SPACE[(m+n+1) + n + (m+n)];
1703 U = new unsigned[m + n + 1];
1704 V = new unsigned[n];
1705 Q = new unsigned[m+n];
1707 R = new unsigned[n];
1710 // Initialize the dividend
1711 memset(U, 0, (m+n+1)*sizeof(unsigned));
1712 for (unsigned i = 0; i < lhsWords; ++i) {
1713 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1714 U[i * 2] = (unsigned)(tmp & mask);
1715 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1717 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1719 // Initialize the divisor
1720 memset(V, 0, (n)*sizeof(unsigned));
1721 for (unsigned i = 0; i < rhsWords; ++i) {
1722 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1723 V[i * 2] = (unsigned)(tmp & mask);
1724 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1727 // initialize the quotient and remainder
1728 memset(Q, 0, (m+n) * sizeof(unsigned));
1730 memset(R, 0, n * sizeof(unsigned));
1732 // Now, adjust m and n for the Knuth division. n is the number of words in
1733 // the divisor. m is the number of words by which the dividend exceeds the
1734 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1735 // contain any zero words or the Knuth algorithm fails.
1736 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1740 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1743 // If we're left with only a single word for the divisor, Knuth doesn't work
1744 // so we implement the short division algorithm here. This is much simpler
1745 // and faster because we are certain that we can divide a 64-bit quantity
1746 // by a 32-bit quantity at hardware speed and short division is simply a
1747 // series of such operations. This is just like doing short division but we
1748 // are using base 2^32 instead of base 10.
1749 assert(n != 0 && "Divide by zero?");
1751 unsigned divisor = V[0];
1752 unsigned remainder = 0;
1753 for (int i = m+n-1; i >= 0; i--) {
1754 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1755 if (partial_dividend == 0) {
1758 } else if (partial_dividend < divisor) {
1760 remainder = (unsigned)partial_dividend;
1761 } else if (partial_dividend == divisor) {
1765 Q[i] = (unsigned)(partial_dividend / divisor);
1766 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1772 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1774 KnuthDiv(U, V, Q, R, m, n);
1777 // If the caller wants the quotient
1779 // Set up the Quotient value's memory.
1780 if (Quotient->BitWidth != LHS.BitWidth) {
1781 if (Quotient->isSingleWord())
1784 delete [] Quotient->pVal;
1785 Quotient->BitWidth = LHS.BitWidth;
1786 if (!Quotient->isSingleWord())
1787 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1789 Quotient->clearAllBits();
1791 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1793 if (lhsWords == 1) {
1795 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1796 if (Quotient->isSingleWord())
1797 Quotient->VAL = tmp;
1799 Quotient->pVal[0] = tmp;
1801 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1802 for (unsigned i = 0; i < lhsWords; ++i)
1804 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1808 // If the caller wants the remainder
1810 // Set up the Remainder value's memory.
1811 if (Remainder->BitWidth != RHS.BitWidth) {
1812 if (Remainder->isSingleWord())
1815 delete [] Remainder->pVal;
1816 Remainder->BitWidth = RHS.BitWidth;
1817 if (!Remainder->isSingleWord())
1818 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1820 Remainder->clearAllBits();
1822 // The remainder is in R. Reconstitute the remainder into Remainder's low
1824 if (rhsWords == 1) {
1826 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1827 if (Remainder->isSingleWord())
1828 Remainder->VAL = tmp;
1830 Remainder->pVal[0] = tmp;
1832 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1833 for (unsigned i = 0; i < rhsWords; ++i)
1834 Remainder->pVal[i] =
1835 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1839 // Clean up the memory we allocated.
1840 if (U != &SPACE[0]) {
1848 APInt APInt::udiv(const APInt& RHS) const {
1849 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1851 // First, deal with the easy case
1852 if (isSingleWord()) {
1853 assert(RHS.VAL != 0 && "Divide by zero?");
1854 return APInt(BitWidth, VAL / RHS.VAL);
1857 // Get some facts about the LHS and RHS number of bits and words
1858 unsigned rhsBits = RHS.getActiveBits();
1859 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1860 assert(rhsWords && "Divided by zero???");
1861 unsigned lhsBits = this->getActiveBits();
1862 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1864 // Deal with some degenerate cases
1867 return APInt(BitWidth, 0);
1868 else if (lhsWords < rhsWords || this->ult(RHS)) {
1869 // X / Y ===> 0, iff X < Y
1870 return APInt(BitWidth, 0);
1871 } else if (*this == RHS) {
1873 return APInt(BitWidth, 1);
1874 } else if (lhsWords == 1 && rhsWords == 1) {
1875 // All high words are zero, just use native divide
1876 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1879 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1880 APInt Quotient(1,0); // to hold result.
1881 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1885 APInt APInt::urem(const APInt& RHS) const {
1886 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1887 if (isSingleWord()) {
1888 assert(RHS.VAL != 0 && "Remainder by zero?");
1889 return APInt(BitWidth, VAL % RHS.VAL);
1892 // Get some facts about the LHS
1893 unsigned lhsBits = getActiveBits();
1894 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1896 // Get some facts about the RHS
1897 unsigned rhsBits = RHS.getActiveBits();
1898 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1899 assert(rhsWords && "Performing remainder operation by zero ???");
1901 // Check the degenerate cases
1902 if (lhsWords == 0) {
1904 return APInt(BitWidth, 0);
1905 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1906 // X % Y ===> X, iff X < Y
1908 } else if (*this == RHS) {
1910 return APInt(BitWidth, 0);
1911 } else if (lhsWords == 1) {
1912 // All high words are zero, just use native remainder
1913 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1916 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1917 APInt Remainder(1,0);
1918 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1922 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1923 APInt &Quotient, APInt &Remainder) {
1924 // Get some size facts about the dividend and divisor
1925 unsigned lhsBits = LHS.getActiveBits();
1926 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1927 unsigned rhsBits = RHS.getActiveBits();
1928 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1930 // Check the degenerate cases
1931 if (lhsWords == 0) {
1932 Quotient = 0; // 0 / Y ===> 0
1933 Remainder = 0; // 0 % Y ===> 0
1937 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1938 Remainder = LHS; // X % Y ===> X, iff X < Y
1939 Quotient = 0; // X / Y ===> 0, iff X < Y
1944 Quotient = 1; // X / X ===> 1
1945 Remainder = 0; // X % X ===> 0;
1949 if (lhsWords == 1 && rhsWords == 1) {
1950 // There is only one word to consider so use the native versions.
1951 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1952 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1953 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1954 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1958 // Okay, lets do it the long way
1959 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1962 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1963 APInt Res = *this+RHS;
1964 Overflow = isNonNegative() == RHS.isNonNegative() &&
1965 Res.isNonNegative() != isNonNegative();
1969 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1970 APInt Res = *this+RHS;
1971 Overflow = Res.ult(RHS);
1975 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1976 APInt Res = *this - RHS;
1977 Overflow = isNonNegative() != RHS.isNonNegative() &&
1978 Res.isNonNegative() != isNonNegative();
1982 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1983 APInt Res = *this-RHS;
1984 Overflow = Res.ugt(*this);
1988 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1989 // MININT/-1 --> overflow.
1990 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1994 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1995 APInt Res = *this * RHS;
1997 if (*this != 0 && RHS != 0)
1998 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2004 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2005 APInt Res = *this * RHS;
2007 if (*this != 0 && RHS != 0)
2008 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2014 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2015 Overflow = ShAmt >= getBitWidth();
2017 ShAmt = getBitWidth()-1;
2019 if (isNonNegative()) // Don't allow sign change.
2020 Overflow = ShAmt >= countLeadingZeros();
2022 Overflow = ShAmt >= countLeadingOnes();
2024 return *this << ShAmt;
2030 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2031 // Check our assumptions here
2032 assert(!str.empty() && "Invalid string length");
2033 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2035 "Radix should be 2, 8, 10, 16, or 36!");
2037 StringRef::iterator p = str.begin();
2038 size_t slen = str.size();
2039 bool isNeg = *p == '-';
2040 if (*p == '-' || *p == '+') {
2043 assert(slen && "String is only a sign, needs a value.");
2045 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2046 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2047 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2048 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2049 "Insufficient bit width");
2052 if (!isSingleWord())
2053 pVal = getClearedMemory(getNumWords());
2055 // Figure out if we can shift instead of multiply
2056 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2058 // Set up an APInt for the digit to add outside the loop so we don't
2059 // constantly construct/destruct it.
2060 APInt apdigit(getBitWidth(), 0);
2061 APInt apradix(getBitWidth(), radix);
2063 // Enter digit traversal loop
2064 for (StringRef::iterator e = str.end(); p != e; ++p) {
2065 unsigned digit = getDigit(*p, radix);
2066 assert(digit < radix && "Invalid character in digit string");
2068 // Shift or multiply the value by the radix
2076 // Add in the digit we just interpreted
2077 if (apdigit.isSingleWord())
2078 apdigit.VAL = digit;
2080 apdigit.pVal[0] = digit;
2083 // If its negative, put it in two's complement form
2086 this->flipAllBits();
2090 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2091 bool Signed, bool formatAsCLiteral) const {
2092 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2094 "Radix should be 2, 8, 10, 16, or 36!");
2096 const char *Prefix = "";
2097 if (formatAsCLiteral) {
2100 // Binary literals are a non-standard extension added in gcc 4.3:
2101 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2113 llvm_unreachable("Invalid radix!");
2117 // First, check for a zero value and just short circuit the logic below.
2120 Str.push_back(*Prefix);
2127 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2129 if (isSingleWord()) {
2131 char *BufPtr = Buffer+65;
2137 int64_t I = getSExtValue();
2147 Str.push_back(*Prefix);
2152 *--BufPtr = Digits[N % Radix];
2155 Str.append(BufPtr, Buffer+65);
2161 if (Signed && isNegative()) {
2162 // They want to print the signed version and it is a negative value
2163 // Flip the bits and add one to turn it into the equivalent positive
2164 // value and put a '-' in the result.
2171 Str.push_back(*Prefix);
2175 // We insert the digits backward, then reverse them to get the right order.
2176 unsigned StartDig = Str.size();
2178 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2179 // because the number of bits per digit (1, 3 and 4 respectively) divides
2180 // equaly. We just shift until the value is zero.
2181 if (Radix == 2 || Radix == 8 || Radix == 16) {
2182 // Just shift tmp right for each digit width until it becomes zero
2183 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2184 unsigned MaskAmt = Radix - 1;
2187 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2188 Str.push_back(Digits[Digit]);
2189 Tmp = Tmp.lshr(ShiftAmt);
2192 APInt divisor(Radix == 10? 4 : 8, Radix);
2194 APInt APdigit(1, 0);
2195 APInt tmp2(Tmp.getBitWidth(), 0);
2196 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2198 unsigned Digit = (unsigned)APdigit.getZExtValue();
2199 assert(Digit < Radix && "divide failed");
2200 Str.push_back(Digits[Digit]);
2205 // Reverse the digits before returning.
2206 std::reverse(Str.begin()+StartDig, Str.end());
2209 /// toString - This returns the APInt as a std::string. Note that this is an
2210 /// inefficient method. It is better to pass in a SmallVector/SmallString
2211 /// to the methods above.
2212 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2214 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2219 void APInt::dump() const {
2220 SmallString<40> S, U;
2221 this->toStringUnsigned(U);
2222 this->toStringSigned(S);
2223 dbgs() << "APInt(" << BitWidth << "b, "
2224 << U.str() << "u " << S.str() << "s)";
2227 void APInt::print(raw_ostream &OS, bool isSigned) const {
2229 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2233 // This implements a variety of operations on a representation of
2234 // arbitrary precision, two's-complement, bignum integer values.
2236 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2237 // and unrestricting assumption.
2238 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2239 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2241 /* Some handy functions local to this file. */
2244 /* Returns the integer part with the least significant BITS set.
2245 BITS cannot be zero. */
2246 static inline integerPart
2247 lowBitMask(unsigned int bits)
2249 assert(bits != 0 && bits <= integerPartWidth);
2251 return ~(integerPart) 0 >> (integerPartWidth - bits);
2254 /* Returns the value of the lower half of PART. */
2255 static inline integerPart
2256 lowHalf(integerPart part)
2258 return part & lowBitMask(integerPartWidth / 2);
2261 /* Returns the value of the upper half of PART. */
2262 static inline integerPart
2263 highHalf(integerPart part)
2265 return part >> (integerPartWidth / 2);
2268 /* Returns the bit number of the most significant set bit of a part.
2269 If the input number has no bits set -1U is returned. */
2271 partMSB(integerPart value)
2273 unsigned int n, msb;
2278 n = integerPartWidth / 2;
2293 /* Returns the bit number of the least significant set bit of a
2294 part. If the input number has no bits set -1U is returned. */
2296 partLSB(integerPart value)
2298 unsigned int n, lsb;
2303 lsb = integerPartWidth - 1;
2304 n = integerPartWidth / 2;
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 /* Set the least significant BITS bits of a bignum, clear the
2860 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2866 while (bits > integerPartWidth) {
2867 dst[i++] = ~(integerPart) 0;
2868 bits -= integerPartWidth;
2872 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);