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 bool APInt::operator !() const {
464 for (unsigned i = 0; i < getNumWords(); ++i)
470 APInt APInt::operator*(const APInt& RHS) const {
471 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
473 return APInt(BitWidth, VAL * RHS.VAL);
479 APInt APInt::operator+(const APInt& RHS) const {
480 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
482 return APInt(BitWidth, VAL + RHS.VAL);
483 APInt Result(BitWidth, 0);
484 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
485 return Result.clearUnusedBits();
488 APInt APInt::operator-(const APInt& RHS) const {
489 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
491 return APInt(BitWidth, VAL - RHS.VAL);
492 APInt Result(BitWidth, 0);
493 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
494 return Result.clearUnusedBits();
497 bool APInt::operator[](unsigned bitPosition) const {
498 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
499 return (maskBit(bitPosition) &
500 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
503 bool APInt::EqualSlowCase(const APInt& RHS) const {
504 // Get some facts about the number of bits used in the two operands.
505 unsigned n1 = getActiveBits();
506 unsigned n2 = RHS.getActiveBits();
508 // If the number of bits isn't the same, they aren't equal
512 // If the number of bits fits in a word, we only need to compare the low word.
513 if (n1 <= APINT_BITS_PER_WORD)
514 return pVal[0] == RHS.pVal[0];
516 // Otherwise, compare everything
517 for (int i = whichWord(n1 - 1); i >= 0; --i)
518 if (pVal[i] != RHS.pVal[i])
523 bool APInt::EqualSlowCase(uint64_t Val) const {
524 unsigned n = getActiveBits();
525 if (n <= APINT_BITS_PER_WORD)
526 return pVal[0] == Val;
531 bool APInt::ult(const APInt& RHS) const {
532 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
534 return VAL < RHS.VAL;
536 // Get active bit length of both operands
537 unsigned n1 = getActiveBits();
538 unsigned n2 = RHS.getActiveBits();
540 // If magnitude of LHS is less than RHS, return true.
544 // If magnitude of RHS is greather than LHS, return false.
548 // If they bot fit in a word, just compare the low order word
549 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
550 return pVal[0] < RHS.pVal[0];
552 // Otherwise, compare all words
553 unsigned topWord = whichWord(std::max(n1,n2)-1);
554 for (int i = topWord; i >= 0; --i) {
555 if (pVal[i] > RHS.pVal[i])
557 if (pVal[i] < RHS.pVal[i])
563 bool APInt::slt(const APInt& RHS) const {
564 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
565 if (isSingleWord()) {
566 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
567 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
568 return lhsSext < rhsSext;
573 bool lhsNeg = isNegative();
574 bool rhsNeg = rhs.isNegative();
576 // Sign bit is set so perform two's complement to make it positive
581 // Sign bit is set so perform two's complement to make it positive
586 // Now we have unsigned values to compare so do the comparison if necessary
587 // based on the negativeness of the values.
599 void APInt::setBit(unsigned bitPosition) {
601 VAL |= maskBit(bitPosition);
603 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
606 /// Set the given bit to 0 whose position is given as "bitPosition".
607 /// @brief Set a given bit to 0.
608 void APInt::clearBit(unsigned bitPosition) {
610 VAL &= ~maskBit(bitPosition);
612 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
615 /// @brief Toggle every bit to its opposite value.
617 /// Toggle a given bit to its opposite value whose position is given
618 /// as "bitPosition".
619 /// @brief Toggles a given bit to its opposite value.
620 void APInt::flipBit(unsigned bitPosition) {
621 assert(bitPosition < BitWidth && "Out of the bit-width range!");
622 if ((*this)[bitPosition]) clearBit(bitPosition);
623 else setBit(bitPosition);
626 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
627 assert(!str.empty() && "Invalid string length");
628 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
630 "Radix should be 2, 8, 10, 16, or 36!");
632 size_t slen = str.size();
634 // Each computation below needs to know if it's negative.
635 StringRef::iterator p = str.begin();
636 unsigned isNegative = *p == '-';
637 if (*p == '-' || *p == '+') {
640 assert(slen && "String is only a sign, needs a value.");
643 // For radixes of power-of-two values, the bits required is accurately and
646 return slen + isNegative;
648 return slen * 3 + isNegative;
650 return slen * 4 + isNegative;
654 // This is grossly inefficient but accurate. We could probably do something
655 // with a computation of roughly slen*64/20 and then adjust by the value of
656 // the first few digits. But, I'm not sure how accurate that could be.
658 // Compute a sufficient number of bits that is always large enough but might
659 // be too large. This avoids the assertion in the constructor. This
660 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
661 // bits in that case.
663 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
664 : (slen == 1 ? 7 : slen * 16/3);
666 // Convert to the actual binary value.
667 APInt tmp(sufficient, StringRef(p, slen), radix);
669 // Compute how many bits are required. If the log is infinite, assume we need
671 unsigned log = tmp.logBase2();
672 if (log == (unsigned)-1) {
673 return isNegative + 1;
675 return isNegative + log + 1;
679 hash_code llvm::hash_value(const APInt &Arg) {
680 if (Arg.isSingleWord())
681 return hash_combine(Arg.VAL);
683 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
686 /// HiBits - This function returns the high "numBits" bits of this APInt.
687 APInt APInt::getHiBits(unsigned numBits) const {
688 return APIntOps::lshr(*this, BitWidth - numBits);
691 /// LoBits - This function returns the low "numBits" bits of this APInt.
692 APInt APInt::getLoBits(unsigned numBits) const {
693 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
697 unsigned APInt::countLeadingZerosSlowCase() const {
698 // Treat the most significand word differently because it might have
699 // meaningless bits set beyond the precision.
700 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
702 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
704 MSWMask = ~integerPart(0);
705 BitsInMSW = APINT_BITS_PER_WORD;
708 unsigned i = getNumWords();
709 integerPart MSW = pVal[i-1] & MSWMask;
711 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
713 unsigned Count = BitsInMSW;
714 for (--i; i > 0u; --i) {
716 Count += APINT_BITS_PER_WORD;
718 Count += CountLeadingZeros_64(pVal[i-1]);
725 unsigned APInt::countLeadingOnes() const {
727 return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
729 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
732 highWordBits = APINT_BITS_PER_WORD;
735 shift = APINT_BITS_PER_WORD - highWordBits;
737 int i = getNumWords() - 1;
738 unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
739 if (Count == highWordBits) {
740 for (i--; i >= 0; --i) {
741 if (pVal[i] == -1ULL)
742 Count += APINT_BITS_PER_WORD;
744 Count += CountLeadingOnes_64(pVal[i]);
752 unsigned APInt::countTrailingZeros() const {
754 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
757 for (; i < getNumWords() && pVal[i] == 0; ++i)
758 Count += APINT_BITS_PER_WORD;
759 if (i < getNumWords())
760 Count += CountTrailingZeros_64(pVal[i]);
761 return std::min(Count, BitWidth);
764 unsigned APInt::countTrailingOnesSlowCase() const {
767 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
768 Count += APINT_BITS_PER_WORD;
769 if (i < getNumWords())
770 Count += CountTrailingOnes_64(pVal[i]);
771 return std::min(Count, BitWidth);
774 unsigned APInt::countPopulationSlowCase() const {
776 for (unsigned i = 0; i < getNumWords(); ++i)
777 Count += CountPopulation_64(pVal[i]);
781 /// Perform a logical right-shift from Src to Dst, which must be equal or
782 /// non-overlapping, of Words words, by Shift, which must be less than 64.
783 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
786 for (int I = Words - 1; I >= 0; --I) {
787 uint64_t Tmp = Src[I];
788 Dst[I] = (Tmp >> Shift) | Carry;
789 Carry = Tmp << (64 - Shift);
793 APInt APInt::byteSwap() const {
794 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
796 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
798 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
799 if (BitWidth == 48) {
800 unsigned Tmp1 = unsigned(VAL >> 16);
801 Tmp1 = ByteSwap_32(Tmp1);
802 uint16_t Tmp2 = uint16_t(VAL);
803 Tmp2 = ByteSwap_16(Tmp2);
804 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
807 return APInt(BitWidth, ByteSwap_64(VAL));
809 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
810 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
811 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
812 if (Result.BitWidth != BitWidth) {
813 lshrNear(Result.pVal, Result.pVal, getNumWords(),
814 Result.BitWidth - BitWidth);
815 Result.BitWidth = BitWidth;
820 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
822 APInt A = API1, B = API2;
825 B = APIntOps::urem(A, B);
831 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
838 // Get the sign bit from the highest order bit
839 bool isNeg = T.I >> 63;
841 // Get the 11-bit exponent and adjust for the 1023 bit bias
842 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
844 // If the exponent is negative, the value is < 0 so just return 0.
846 return APInt(width, 0u);
848 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
849 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
851 // If the exponent doesn't shift all bits out of the mantissa
853 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
854 APInt(width, mantissa >> (52 - exp));
856 // If the client didn't provide enough bits for us to shift the mantissa into
857 // then the result is undefined, just return 0
858 if (width <= exp - 52)
859 return APInt(width, 0);
861 // Otherwise, we have to shift the mantissa bits up to the right location
862 APInt Tmp(width, mantissa);
863 Tmp = Tmp.shl((unsigned)exp - 52);
864 return isNeg ? -Tmp : Tmp;
867 /// RoundToDouble - This function converts this APInt to a double.
868 /// The layout for double is as following (IEEE Standard 754):
869 /// --------------------------------------
870 /// | Sign Exponent Fraction Bias |
871 /// |-------------------------------------- |
872 /// | 1[63] 11[62-52] 52[51-00] 1023 |
873 /// --------------------------------------
874 double APInt::roundToDouble(bool isSigned) const {
876 // Handle the simple case where the value is contained in one uint64_t.
877 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
878 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
880 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
883 return double(getWord(0));
886 // Determine if the value is negative.
887 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
889 // Construct the absolute value if we're negative.
890 APInt Tmp(isNeg ? -(*this) : (*this));
892 // Figure out how many bits we're using.
893 unsigned n = Tmp.getActiveBits();
895 // The exponent (without bias normalization) is just the number of bits
896 // we are using. Note that the sign bit is gone since we constructed the
900 // Return infinity for exponent overflow
902 if (!isSigned || !isNeg)
903 return std::numeric_limits<double>::infinity();
905 return -std::numeric_limits<double>::infinity();
907 exp += 1023; // Increment for 1023 bias
909 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
910 // extract the high 52 bits from the correct words in pVal.
912 unsigned hiWord = whichWord(n-1);
914 mantissa = Tmp.pVal[0];
916 mantissa >>= n - 52; // shift down, we want the top 52 bits.
918 assert(hiWord > 0 && "huh?");
919 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
920 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
921 mantissa = hibits | lobits;
924 // The leading bit of mantissa is implicit, so get rid of it.
925 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
930 T.I = sign | (exp << 52) | mantissa;
934 // Truncate to new width.
935 APInt APInt::trunc(unsigned width) const {
936 assert(width < BitWidth && "Invalid APInt Truncate request");
937 assert(width && "Can't truncate to 0 bits");
939 if (width <= APINT_BITS_PER_WORD)
940 return APInt(width, getRawData()[0]);
942 APInt Result(getMemory(getNumWords(width)), width);
946 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
947 Result.pVal[i] = pVal[i];
949 // Truncate and copy any partial word.
950 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
952 Result.pVal[i] = pVal[i] << bits >> bits;
957 // Sign extend to a new width.
958 APInt APInt::sext(unsigned width) const {
959 assert(width > BitWidth && "Invalid APInt SignExtend request");
961 if (width <= APINT_BITS_PER_WORD) {
962 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
963 val = (int64_t)val >> (width - BitWidth);
964 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
967 APInt Result(getMemory(getNumWords(width)), width);
972 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
973 word = getRawData()[i];
974 Result.pVal[i] = word;
977 // Read and sign-extend any partial word.
978 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
980 word = (int64_t)getRawData()[i] << bits >> bits;
982 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
984 // Write remaining full words.
985 for (; i != width / APINT_BITS_PER_WORD; i++) {
986 Result.pVal[i] = word;
987 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
990 // Write any partial word.
991 bits = (0 - width) % APINT_BITS_PER_WORD;
993 Result.pVal[i] = word << bits >> bits;
998 // Zero extend to a new width.
999 APInt APInt::zext(unsigned width) const {
1000 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1002 if (width <= APINT_BITS_PER_WORD)
1003 return APInt(width, VAL);
1005 APInt Result(getMemory(getNumWords(width)), width);
1009 for (i = 0; i != getNumWords(); i++)
1010 Result.pVal[i] = getRawData()[i];
1012 // Zero remaining words.
1013 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1018 APInt APInt::zextOrTrunc(unsigned width) const {
1019 if (BitWidth < width)
1021 if (BitWidth > width)
1022 return trunc(width);
1026 APInt APInt::sextOrTrunc(unsigned width) const {
1027 if (BitWidth < width)
1029 if (BitWidth > width)
1030 return trunc(width);
1034 APInt APInt::zextOrSelf(unsigned width) const {
1035 if (BitWidth < width)
1040 APInt APInt::sextOrSelf(unsigned width) const {
1041 if (BitWidth < width)
1046 /// Arithmetic right-shift this APInt by shiftAmt.
1047 /// @brief Arithmetic right-shift function.
1048 APInt APInt::ashr(const APInt &shiftAmt) const {
1049 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1052 /// Arithmetic right-shift this APInt by shiftAmt.
1053 /// @brief Arithmetic right-shift function.
1054 APInt APInt::ashr(unsigned shiftAmt) const {
1055 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1056 // Handle a degenerate case
1060 // Handle single word shifts with built-in ashr
1061 if (isSingleWord()) {
1062 if (shiftAmt == BitWidth)
1063 return APInt(BitWidth, 0); // undefined
1065 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1066 return APInt(BitWidth,
1067 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1071 // If all the bits were shifted out, the result is, technically, undefined.
1072 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1073 // issues in the algorithm below.
1074 if (shiftAmt == BitWidth) {
1076 return APInt(BitWidth, -1ULL, true);
1078 return APInt(BitWidth, 0);
1081 // Create some space for the result.
1082 uint64_t * val = new uint64_t[getNumWords()];
1084 // Compute some values needed by the following shift algorithms
1085 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1086 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1087 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1088 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1089 if (bitsInWord == 0)
1090 bitsInWord = APINT_BITS_PER_WORD;
1092 // If we are shifting whole words, just move whole words
1093 if (wordShift == 0) {
1094 // Move the words containing significant bits
1095 for (unsigned i = 0; i <= breakWord; ++i)
1096 val[i] = pVal[i+offset]; // move whole word
1098 // Adjust the top significant word for sign bit fill, if negative
1100 if (bitsInWord < APINT_BITS_PER_WORD)
1101 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1103 // Shift the low order words
1104 for (unsigned i = 0; i < breakWord; ++i) {
1105 // This combines the shifted corresponding word with the low bits from
1106 // the next word (shifted into this word's high bits).
1107 val[i] = (pVal[i+offset] >> wordShift) |
1108 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1111 // Shift the break word. In this case there are no bits from the next word
1112 // to include in this word.
1113 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1115 // Deal with sign extenstion in the break word, and possibly the word before
1118 if (wordShift > bitsInWord) {
1121 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1122 val[breakWord] |= ~0ULL;
1124 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1128 // Remaining words are 0 or -1, just assign them.
1129 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1130 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1132 return APInt(val, BitWidth).clearUnusedBits();
1135 /// Logical right-shift this APInt by shiftAmt.
1136 /// @brief Logical right-shift function.
1137 APInt APInt::lshr(const APInt &shiftAmt) const {
1138 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1141 /// Logical right-shift this APInt by shiftAmt.
1142 /// @brief Logical right-shift function.
1143 APInt APInt::lshr(unsigned shiftAmt) const {
1144 if (isSingleWord()) {
1145 if (shiftAmt >= BitWidth)
1146 return APInt(BitWidth, 0);
1148 return APInt(BitWidth, this->VAL >> shiftAmt);
1151 // If all the bits were shifted out, the result is 0. This avoids issues
1152 // with shifting by the size of the integer type, which produces undefined
1153 // results. We define these "undefined results" to always be 0.
1154 if (shiftAmt == BitWidth)
1155 return APInt(BitWidth, 0);
1157 // If none of the bits are shifted out, the result is *this. This avoids
1158 // issues with shifting by the size of the integer type, which produces
1159 // undefined results in the code below. This is also an optimization.
1163 // Create some space for the result.
1164 uint64_t * val = new uint64_t[getNumWords()];
1166 // If we are shifting less than a word, compute the shift with a simple carry
1167 if (shiftAmt < APINT_BITS_PER_WORD) {
1168 lshrNear(val, pVal, getNumWords(), shiftAmt);
1169 return APInt(val, BitWidth).clearUnusedBits();
1172 // Compute some values needed by the remaining shift algorithms
1173 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1174 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1176 // If we are shifting whole words, just move whole words
1177 if (wordShift == 0) {
1178 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1179 val[i] = pVal[i+offset];
1180 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1182 return APInt(val,BitWidth).clearUnusedBits();
1185 // Shift the low order words
1186 unsigned breakWord = getNumWords() - offset -1;
1187 for (unsigned i = 0; i < breakWord; ++i)
1188 val[i] = (pVal[i+offset] >> wordShift) |
1189 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1190 // Shift the break word.
1191 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1193 // Remaining words are 0
1194 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1196 return APInt(val, BitWidth).clearUnusedBits();
1199 /// Left-shift this APInt by shiftAmt.
1200 /// @brief Left-shift function.
1201 APInt APInt::shl(const APInt &shiftAmt) const {
1202 // It's undefined behavior in C to shift by BitWidth or greater.
1203 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1206 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1207 // If all the bits were shifted out, the result is 0. This avoids issues
1208 // with shifting by the size of the integer type, which produces undefined
1209 // results. We define these "undefined results" to always be 0.
1210 if (shiftAmt == BitWidth)
1211 return APInt(BitWidth, 0);
1213 // If none of the bits are shifted out, the result is *this. This avoids a
1214 // lshr by the words size in the loop below which can produce incorrect
1215 // results. It also avoids the expensive computation below for a common case.
1219 // Create some space for the result.
1220 uint64_t * val = new uint64_t[getNumWords()];
1222 // If we are shifting less than a word, do it the easy way
1223 if (shiftAmt < APINT_BITS_PER_WORD) {
1225 for (unsigned i = 0; i < getNumWords(); i++) {
1226 val[i] = pVal[i] << shiftAmt | carry;
1227 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1229 return APInt(val, BitWidth).clearUnusedBits();
1232 // Compute some values needed by the remaining shift algorithms
1233 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1234 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1236 // If we are shifting whole words, just move whole words
1237 if (wordShift == 0) {
1238 for (unsigned i = 0; i < offset; i++)
1240 for (unsigned i = offset; i < getNumWords(); i++)
1241 val[i] = pVal[i-offset];
1242 return APInt(val,BitWidth).clearUnusedBits();
1245 // Copy whole words from this to Result.
1246 unsigned i = getNumWords() - 1;
1247 for (; i > offset; --i)
1248 val[i] = pVal[i-offset] << wordShift |
1249 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1250 val[offset] = pVal[0] << wordShift;
1251 for (i = 0; i < offset; ++i)
1253 return APInt(val, BitWidth).clearUnusedBits();
1256 APInt APInt::rotl(const APInt &rotateAmt) const {
1257 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1260 APInt APInt::rotl(unsigned rotateAmt) const {
1261 rotateAmt %= BitWidth;
1264 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1267 APInt APInt::rotr(const APInt &rotateAmt) const {
1268 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1271 APInt APInt::rotr(unsigned rotateAmt) const {
1272 rotateAmt %= BitWidth;
1275 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1278 // Square Root - this method computes and returns the square root of "this".
1279 // Three mechanisms are used for computation. For small values (<= 5 bits),
1280 // a table lookup is done. This gets some performance for common cases. For
1281 // values using less than 52 bits, the value is converted to double and then
1282 // the libc sqrt function is called. The result is rounded and then converted
1283 // back to a uint64_t which is then used to construct the result. Finally,
1284 // the Babylonian method for computing square roots is used.
1285 APInt APInt::sqrt() const {
1287 // Determine the magnitude of the value.
1288 unsigned magnitude = getActiveBits();
1290 // Use a fast table for some small values. This also gets rid of some
1291 // rounding errors in libc sqrt for small values.
1292 if (magnitude <= 5) {
1293 static const uint8_t results[32] = {
1296 /* 3- 6 */ 2, 2, 2, 2,
1297 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1298 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1299 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1302 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1305 // If the magnitude of the value fits in less than 52 bits (the precision of
1306 // an IEEE double precision floating point value), then we can use the
1307 // libc sqrt function which will probably use a hardware sqrt computation.
1308 // This should be faster than the algorithm below.
1309 if (magnitude < 52) {
1311 return APInt(BitWidth,
1312 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1314 return APInt(BitWidth,
1315 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1319 // Okay, all the short cuts are exhausted. We must compute it. The following
1320 // is a classical Babylonian method for computing the square root. This code
1321 // was adapted to APINt from a wikipedia article on such computations.
1322 // See http://www.wikipedia.org/ and go to the page named
1323 // Calculate_an_integer_square_root.
1324 unsigned nbits = BitWidth, i = 4;
1325 APInt testy(BitWidth, 16);
1326 APInt x_old(BitWidth, 1);
1327 APInt x_new(BitWidth, 0);
1328 APInt two(BitWidth, 2);
1330 // Select a good starting value using binary logarithms.
1331 for (;; i += 2, testy = testy.shl(2))
1332 if (i >= nbits || this->ule(testy)) {
1333 x_old = x_old.shl(i / 2);
1337 // Use the Babylonian method to arrive at the integer square root:
1339 x_new = (this->udiv(x_old) + x_old).udiv(two);
1340 if (x_old.ule(x_new))
1345 // Make sure we return the closest approximation
1346 // NOTE: The rounding calculation below is correct. It will produce an
1347 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1348 // determined to be a rounding issue with pari/gp as it begins to use a
1349 // floating point representation after 192 bits. There are no discrepancies
1350 // between this algorithm and pari/gp for bit widths < 192 bits.
1351 APInt square(x_old * x_old);
1352 APInt nextSquare((x_old + 1) * (x_old +1));
1353 if (this->ult(square))
1355 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1356 APInt midpoint((nextSquare - square).udiv(two));
1357 APInt offset(*this - square);
1358 if (offset.ult(midpoint))
1363 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1364 /// iterative extended Euclidean algorithm is used to solve for this value,
1365 /// however we simplify it to speed up calculating only the inverse, and take
1366 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1367 /// (potentially large) APInts around.
1368 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1369 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1371 // Using the properties listed at the following web page (accessed 06/21/08):
1372 // http://www.numbertheory.org/php/euclid.html
1373 // (especially the properties numbered 3, 4 and 9) it can be proved that
1374 // BitWidth bits suffice for all the computations in the algorithm implemented
1375 // below. More precisely, this number of bits suffice if the multiplicative
1376 // inverse exists, but may not suffice for the general extended Euclidean
1379 APInt r[2] = { modulo, *this };
1380 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1381 APInt q(BitWidth, 0);
1384 for (i = 0; r[i^1] != 0; i ^= 1) {
1385 // An overview of the math without the confusing bit-flipping:
1386 // q = r[i-2] / r[i-1]
1387 // r[i] = r[i-2] % r[i-1]
1388 // t[i] = t[i-2] - t[i-1] * q
1389 udivrem(r[i], r[i^1], q, r[i]);
1393 // If this APInt and the modulo are not coprime, there is no multiplicative
1394 // inverse, so return 0. We check this by looking at the next-to-last
1395 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1398 return APInt(BitWidth, 0);
1400 // The next-to-last t is the multiplicative inverse. However, we are
1401 // interested in a positive inverse. Calcuate a positive one from a negative
1402 // one if necessary. A simple addition of the modulo suffices because
1403 // abs(t[i]) is known to be less than *this/2 (see the link above).
1404 return t[i].isNegative() ? t[i] + modulo : t[i];
1407 /// Calculate the magic numbers required to implement a signed integer division
1408 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1409 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1410 /// Warren, Jr., chapter 10.
1411 APInt::ms APInt::magic() const {
1412 const APInt& d = *this;
1414 APInt ad, anc, delta, q1, r1, q2, r2, t;
1415 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1419 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1420 anc = t - 1 - t.urem(ad); // absolute value of nc
1421 p = d.getBitWidth() - 1; // initialize p
1422 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1423 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1424 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1425 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1428 q1 = q1<<1; // update q1 = 2p/abs(nc)
1429 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1430 if (r1.uge(anc)) { // must be unsigned comparison
1434 q2 = q2<<1; // update q2 = 2p/abs(d)
1435 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1436 if (r2.uge(ad)) { // must be unsigned comparison
1441 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1444 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1445 mag.s = p - d.getBitWidth(); // resulting shift
1449 /// Calculate the magic numbers required to implement an unsigned integer
1450 /// division by a constant as a sequence of multiplies, adds and shifts.
1451 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1452 /// S. Warren, Jr., chapter 10.
1453 /// LeadingZeros can be used to simplify the calculation if the upper bits
1454 /// of the divided value are known zero.
1455 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1456 const APInt& d = *this;
1458 APInt nc, delta, q1, r1, q2, r2;
1460 magu.a = 0; // initialize "add" indicator
1461 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1462 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1463 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1465 nc = allOnes - (-d).urem(d);
1466 p = d.getBitWidth() - 1; // initialize p
1467 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1468 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1469 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1470 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1473 if (r1.uge(nc - r1)) {
1474 q1 = q1 + q1 + 1; // update q1
1475 r1 = r1 + r1 - nc; // update r1
1478 q1 = q1+q1; // update q1
1479 r1 = r1+r1; // update r1
1481 if ((r2 + 1).uge(d - r2)) {
1482 if (q2.uge(signedMax)) magu.a = 1;
1483 q2 = q2+q2 + 1; // update q2
1484 r2 = r2+r2 + 1 - d; // update r2
1487 if (q2.uge(signedMin)) magu.a = 1;
1488 q2 = q2+q2; // update q2
1489 r2 = r2+r2 + 1; // update r2
1492 } while (p < d.getBitWidth()*2 &&
1493 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1494 magu.m = q2 + 1; // resulting magic number
1495 magu.s = p - d.getBitWidth(); // resulting shift
1499 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1500 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1501 /// variables here have the same names as in the algorithm. Comments explain
1502 /// the algorithm and any deviation from it.
1503 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1504 unsigned m, unsigned n) {
1505 assert(u && "Must provide dividend");
1506 assert(v && "Must provide divisor");
1507 assert(q && "Must provide quotient");
1508 assert(u != v && u != q && v != q && "Must us different memory");
1509 assert(n>1 && "n must be > 1");
1511 // Knuth uses the value b as the base of the number system. In our case b
1512 // is 2^31 so we just set it to -1u.
1513 uint64_t b = uint64_t(1) << 32;
1516 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1517 DEBUG(dbgs() << "KnuthDiv: original:");
1518 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1519 DEBUG(dbgs() << " by");
1520 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1521 DEBUG(dbgs() << '\n');
1523 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1524 // u and v by d. Note that we have taken Knuth's advice here to use a power
1525 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1526 // 2 allows us to shift instead of multiply and it is easy to determine the
1527 // shift amount from the leading zeros. We are basically normalizing the u
1528 // and v so that its high bits are shifted to the top of v's range without
1529 // overflow. Note that this can require an extra word in u so that u must
1530 // be of length m+n+1.
1531 unsigned shift = CountLeadingZeros_32(v[n-1]);
1532 unsigned v_carry = 0;
1533 unsigned u_carry = 0;
1535 for (unsigned i = 0; i < m+n; ++i) {
1536 unsigned u_tmp = u[i] >> (32 - shift);
1537 u[i] = (u[i] << shift) | u_carry;
1540 for (unsigned i = 0; i < n; ++i) {
1541 unsigned v_tmp = v[i] >> (32 - shift);
1542 v[i] = (v[i] << shift) | v_carry;
1548 DEBUG(dbgs() << "KnuthDiv: normal:");
1549 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1550 DEBUG(dbgs() << " by");
1551 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1552 DEBUG(dbgs() << '\n');
1555 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1558 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1559 // D3. [Calculate q'.].
1560 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1561 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1562 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1563 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1564 // on v[n-2] determines at high speed most of the cases in which the trial
1565 // value qp is one too large, and it eliminates all cases where qp is two
1567 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1568 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1569 uint64_t qp = dividend / v[n-1];
1570 uint64_t rp = dividend % v[n-1];
1571 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1574 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1577 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1579 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1580 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1581 // consists of a simple multiplication by a one-place number, combined with
1584 for (unsigned i = 0; i < n; ++i) {
1585 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1586 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1587 bool borrow = subtrahend > u_tmp;
1588 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1589 << ", subtrahend == " << subtrahend
1590 << ", borrow = " << borrow << '\n');
1592 uint64_t result = u_tmp - subtrahend;
1594 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1595 u[k++] = (unsigned)(result >> 32); // subtract high word
1596 while (borrow && k <= m+n) { // deal with borrow to the left
1602 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1605 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1606 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1607 DEBUG(dbgs() << '\n');
1608 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1609 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1610 // true value plus b**(n+1), namely as the b's complement of
1611 // the true value, and a "borrow" to the left should be remembered.
1614 bool carry = true; // true because b's complement is "complement + 1"
1615 for (unsigned i = 0; i <= m+n; ++i) {
1616 u[i] = ~u[i] + carry; // b's complement
1617 carry = carry && u[i] == 0;
1620 DEBUG(dbgs() << "KnuthDiv: after complement:");
1621 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1622 DEBUG(dbgs() << '\n');
1624 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1625 // negative, go to step D6; otherwise go on to step D7.
1626 q[j] = (unsigned)qp;
1628 // D6. [Add back]. The probability that this step is necessary is very
1629 // small, on the order of only 2/b. Make sure that test data accounts for
1630 // this possibility. Decrease q[j] by 1
1632 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1633 // A carry will occur to the left of u[j+n], and it should be ignored
1634 // since it cancels with the borrow that occurred in D4.
1636 for (unsigned i = 0; i < n; i++) {
1637 unsigned limit = std::min(u[j+i],v[i]);
1638 u[j+i] += v[i] + carry;
1639 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1643 DEBUG(dbgs() << "KnuthDiv: after correction:");
1644 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1645 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1647 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1650 DEBUG(dbgs() << "KnuthDiv: quotient:");
1651 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1652 DEBUG(dbgs() << '\n');
1654 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1655 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1656 // compute the remainder (urem uses this).
1658 // The value d is expressed by the "shift" value above since we avoided
1659 // multiplication by d by using a shift left. So, all we have to do is
1660 // shift right here. In order to mak
1663 DEBUG(dbgs() << "KnuthDiv: remainder:");
1664 for (int i = n-1; i >= 0; i--) {
1665 r[i] = (u[i] >> shift) | carry;
1666 carry = u[i] << (32 - shift);
1667 DEBUG(dbgs() << " " << r[i]);
1670 for (int i = n-1; i >= 0; i--) {
1672 DEBUG(dbgs() << " " << r[i]);
1675 DEBUG(dbgs() << '\n');
1678 DEBUG(dbgs() << '\n');
1682 void APInt::divide(const APInt LHS, unsigned lhsWords,
1683 const APInt &RHS, unsigned rhsWords,
1684 APInt *Quotient, APInt *Remainder)
1686 assert(lhsWords >= rhsWords && "Fractional result");
1688 // First, compose the values into an array of 32-bit words instead of
1689 // 64-bit words. This is a necessity of both the "short division" algorithm
1690 // and the Knuth "classical algorithm" which requires there to be native
1691 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1692 // can't use 64-bit operands here because we don't have native results of
1693 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1694 // work on large-endian machines.
1695 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1696 unsigned n = rhsWords * 2;
1697 unsigned m = (lhsWords * 2) - n;
1699 // Allocate space for the temporary values we need either on the stack, if
1700 // it will fit, or on the heap if it won't.
1701 unsigned SPACE[128];
1706 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1709 Q = &SPACE[(m+n+1) + n];
1711 R = &SPACE[(m+n+1) + n + (m+n)];
1713 U = new unsigned[m + n + 1];
1714 V = new unsigned[n];
1715 Q = new unsigned[m+n];
1717 R = new unsigned[n];
1720 // Initialize the dividend
1721 memset(U, 0, (m+n+1)*sizeof(unsigned));
1722 for (unsigned i = 0; i < lhsWords; ++i) {
1723 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1724 U[i * 2] = (unsigned)(tmp & mask);
1725 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1727 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1729 // Initialize the divisor
1730 memset(V, 0, (n)*sizeof(unsigned));
1731 for (unsigned i = 0; i < rhsWords; ++i) {
1732 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1733 V[i * 2] = (unsigned)(tmp & mask);
1734 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1737 // initialize the quotient and remainder
1738 memset(Q, 0, (m+n) * sizeof(unsigned));
1740 memset(R, 0, n * sizeof(unsigned));
1742 // Now, adjust m and n for the Knuth division. n is the number of words in
1743 // the divisor. m is the number of words by which the dividend exceeds the
1744 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1745 // contain any zero words or the Knuth algorithm fails.
1746 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1750 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1753 // If we're left with only a single word for the divisor, Knuth doesn't work
1754 // so we implement the short division algorithm here. This is much simpler
1755 // and faster because we are certain that we can divide a 64-bit quantity
1756 // by a 32-bit quantity at hardware speed and short division is simply a
1757 // series of such operations. This is just like doing short division but we
1758 // are using base 2^32 instead of base 10.
1759 assert(n != 0 && "Divide by zero?");
1761 unsigned divisor = V[0];
1762 unsigned remainder = 0;
1763 for (int i = m+n-1; i >= 0; i--) {
1764 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1765 if (partial_dividend == 0) {
1768 } else if (partial_dividend < divisor) {
1770 remainder = (unsigned)partial_dividend;
1771 } else if (partial_dividend == divisor) {
1775 Q[i] = (unsigned)(partial_dividend / divisor);
1776 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1782 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1784 KnuthDiv(U, V, Q, R, m, n);
1787 // If the caller wants the quotient
1789 // Set up the Quotient value's memory.
1790 if (Quotient->BitWidth != LHS.BitWidth) {
1791 if (Quotient->isSingleWord())
1794 delete [] Quotient->pVal;
1795 Quotient->BitWidth = LHS.BitWidth;
1796 if (!Quotient->isSingleWord())
1797 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1799 Quotient->clearAllBits();
1801 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1803 if (lhsWords == 1) {
1805 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1806 if (Quotient->isSingleWord())
1807 Quotient->VAL = tmp;
1809 Quotient->pVal[0] = tmp;
1811 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1812 for (unsigned i = 0; i < lhsWords; ++i)
1814 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1818 // If the caller wants the remainder
1820 // Set up the Remainder value's memory.
1821 if (Remainder->BitWidth != RHS.BitWidth) {
1822 if (Remainder->isSingleWord())
1825 delete [] Remainder->pVal;
1826 Remainder->BitWidth = RHS.BitWidth;
1827 if (!Remainder->isSingleWord())
1828 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1830 Remainder->clearAllBits();
1832 // The remainder is in R. Reconstitute the remainder into Remainder's low
1834 if (rhsWords == 1) {
1836 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1837 if (Remainder->isSingleWord())
1838 Remainder->VAL = tmp;
1840 Remainder->pVal[0] = tmp;
1842 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1843 for (unsigned i = 0; i < rhsWords; ++i)
1844 Remainder->pVal[i] =
1845 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1849 // Clean up the memory we allocated.
1850 if (U != &SPACE[0]) {
1858 APInt APInt::udiv(const APInt& RHS) const {
1859 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1861 // First, deal with the easy case
1862 if (isSingleWord()) {
1863 assert(RHS.VAL != 0 && "Divide by zero?");
1864 return APInt(BitWidth, VAL / RHS.VAL);
1867 // Get some facts about the LHS and RHS number of bits and words
1868 unsigned rhsBits = RHS.getActiveBits();
1869 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1870 assert(rhsWords && "Divided by zero???");
1871 unsigned lhsBits = this->getActiveBits();
1872 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1874 // Deal with some degenerate cases
1877 return APInt(BitWidth, 0);
1878 else if (lhsWords < rhsWords || this->ult(RHS)) {
1879 // X / Y ===> 0, iff X < Y
1880 return APInt(BitWidth, 0);
1881 } else if (*this == RHS) {
1883 return APInt(BitWidth, 1);
1884 } else if (lhsWords == 1 && rhsWords == 1) {
1885 // All high words are zero, just use native divide
1886 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1889 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1890 APInt Quotient(1,0); // to hold result.
1891 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1895 APInt APInt::urem(const APInt& RHS) const {
1896 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1897 if (isSingleWord()) {
1898 assert(RHS.VAL != 0 && "Remainder by zero?");
1899 return APInt(BitWidth, VAL % RHS.VAL);
1902 // Get some facts about the LHS
1903 unsigned lhsBits = getActiveBits();
1904 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1906 // Get some facts about the RHS
1907 unsigned rhsBits = RHS.getActiveBits();
1908 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1909 assert(rhsWords && "Performing remainder operation by zero ???");
1911 // Check the degenerate cases
1912 if (lhsWords == 0) {
1914 return APInt(BitWidth, 0);
1915 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1916 // X % Y ===> X, iff X < Y
1918 } else if (*this == RHS) {
1920 return APInt(BitWidth, 0);
1921 } else if (lhsWords == 1) {
1922 // All high words are zero, just use native remainder
1923 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1926 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1927 APInt Remainder(1,0);
1928 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1932 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1933 APInt &Quotient, APInt &Remainder) {
1934 // Get some size facts about the dividend and divisor
1935 unsigned lhsBits = LHS.getActiveBits();
1936 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1937 unsigned rhsBits = RHS.getActiveBits();
1938 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1940 // Check the degenerate cases
1941 if (lhsWords == 0) {
1942 Quotient = 0; // 0 / Y ===> 0
1943 Remainder = 0; // 0 % Y ===> 0
1947 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1948 Remainder = LHS; // X % Y ===> X, iff X < Y
1949 Quotient = 0; // X / Y ===> 0, iff X < Y
1954 Quotient = 1; // X / X ===> 1
1955 Remainder = 0; // X % X ===> 0;
1959 if (lhsWords == 1 && rhsWords == 1) {
1960 // There is only one word to consider so use the native versions.
1961 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1962 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1963 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1964 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1968 // Okay, lets do it the long way
1969 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1972 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1973 APInt Res = *this+RHS;
1974 Overflow = isNonNegative() == RHS.isNonNegative() &&
1975 Res.isNonNegative() != isNonNegative();
1979 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1980 APInt Res = *this+RHS;
1981 Overflow = Res.ult(RHS);
1985 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1986 APInt Res = *this - RHS;
1987 Overflow = isNonNegative() != RHS.isNonNegative() &&
1988 Res.isNonNegative() != isNonNegative();
1992 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1993 APInt Res = *this-RHS;
1994 Overflow = Res.ugt(*this);
1998 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1999 // MININT/-1 --> overflow.
2000 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2004 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2005 APInt Res = *this * RHS;
2007 if (*this != 0 && RHS != 0)
2008 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2014 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2015 APInt Res = *this * RHS;
2017 if (*this != 0 && RHS != 0)
2018 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2024 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2025 Overflow = ShAmt >= getBitWidth();
2027 ShAmt = getBitWidth()-1;
2029 if (isNonNegative()) // Don't allow sign change.
2030 Overflow = ShAmt >= countLeadingZeros();
2032 Overflow = ShAmt >= countLeadingOnes();
2034 return *this << ShAmt;
2040 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2041 // Check our assumptions here
2042 assert(!str.empty() && "Invalid string length");
2043 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2045 "Radix should be 2, 8, 10, 16, or 36!");
2047 StringRef::iterator p = str.begin();
2048 size_t slen = str.size();
2049 bool isNeg = *p == '-';
2050 if (*p == '-' || *p == '+') {
2053 assert(slen && "String is only a sign, needs a value.");
2055 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2056 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2057 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2058 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2059 "Insufficient bit width");
2062 if (!isSingleWord())
2063 pVal = getClearedMemory(getNumWords());
2065 // Figure out if we can shift instead of multiply
2066 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2068 // Set up an APInt for the digit to add outside the loop so we don't
2069 // constantly construct/destruct it.
2070 APInt apdigit(getBitWidth(), 0);
2071 APInt apradix(getBitWidth(), radix);
2073 // Enter digit traversal loop
2074 for (StringRef::iterator e = str.end(); p != e; ++p) {
2075 unsigned digit = getDigit(*p, radix);
2076 assert(digit < radix && "Invalid character in digit string");
2078 // Shift or multiply the value by the radix
2086 // Add in the digit we just interpreted
2087 if (apdigit.isSingleWord())
2088 apdigit.VAL = digit;
2090 apdigit.pVal[0] = digit;
2093 // If its negative, put it in two's complement form
2096 this->flipAllBits();
2100 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2101 bool Signed, bool formatAsCLiteral) const {
2102 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2104 "Radix should be 2, 8, 10, 16, or 36!");
2106 const char *Prefix = "";
2107 if (formatAsCLiteral) {
2110 // Binary literals are a non-standard extension added in gcc 4.3:
2111 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2123 llvm_unreachable("Invalid radix!");
2127 // First, check for a zero value and just short circuit the logic below.
2130 Str.push_back(*Prefix);
2137 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2139 if (isSingleWord()) {
2141 char *BufPtr = Buffer+65;
2147 int64_t I = getSExtValue();
2157 Str.push_back(*Prefix);
2162 *--BufPtr = Digits[N % Radix];
2165 Str.append(BufPtr, Buffer+65);
2171 if (Signed && isNegative()) {
2172 // They want to print the signed version and it is a negative value
2173 // Flip the bits and add one to turn it into the equivalent positive
2174 // value and put a '-' in the result.
2181 Str.push_back(*Prefix);
2185 // We insert the digits backward, then reverse them to get the right order.
2186 unsigned StartDig = Str.size();
2188 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2189 // because the number of bits per digit (1, 3 and 4 respectively) divides
2190 // equaly. We just shift until the value is zero.
2191 if (Radix == 2 || Radix == 8 || Radix == 16) {
2192 // Just shift tmp right for each digit width until it becomes zero
2193 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2194 unsigned MaskAmt = Radix - 1;
2197 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2198 Str.push_back(Digits[Digit]);
2199 Tmp = Tmp.lshr(ShiftAmt);
2202 APInt divisor(Radix == 10? 4 : 8, Radix);
2204 APInt APdigit(1, 0);
2205 APInt tmp2(Tmp.getBitWidth(), 0);
2206 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2208 unsigned Digit = (unsigned)APdigit.getZExtValue();
2209 assert(Digit < Radix && "divide failed");
2210 Str.push_back(Digits[Digit]);
2215 // Reverse the digits before returning.
2216 std::reverse(Str.begin()+StartDig, Str.end());
2219 /// toString - This returns the APInt as a std::string. Note that this is an
2220 /// inefficient method. It is better to pass in a SmallVector/SmallString
2221 /// to the methods above.
2222 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2224 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2229 void APInt::dump() const {
2230 SmallString<40> S, U;
2231 this->toStringUnsigned(U);
2232 this->toStringSigned(S);
2233 dbgs() << "APInt(" << BitWidth << "b, "
2234 << U.str() << "u " << S.str() << "s)";
2237 void APInt::print(raw_ostream &OS, bool isSigned) const {
2239 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2243 // This implements a variety of operations on a representation of
2244 // arbitrary precision, two's-complement, bignum integer values.
2246 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2247 // and unrestricting assumption.
2248 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2249 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2251 /* Some handy functions local to this file. */
2254 /* Returns the integer part with the least significant BITS set.
2255 BITS cannot be zero. */
2256 static inline integerPart
2257 lowBitMask(unsigned int bits)
2259 assert(bits != 0 && bits <= integerPartWidth);
2261 return ~(integerPart) 0 >> (integerPartWidth - bits);
2264 /* Returns the value of the lower half of PART. */
2265 static inline integerPart
2266 lowHalf(integerPart part)
2268 return part & lowBitMask(integerPartWidth / 2);
2271 /* Returns the value of the upper half of PART. */
2272 static inline integerPart
2273 highHalf(integerPart part)
2275 return part >> (integerPartWidth / 2);
2278 /* Returns the bit number of the most significant set bit of a part.
2279 If the input number has no bits set -1U is returned. */
2281 partMSB(integerPart value)
2283 unsigned int n, msb;
2288 n = integerPartWidth / 2;
2303 /* Returns the bit number of the least significant set bit of a
2304 part. If the input number has no bits set -1U is returned. */
2306 partLSB(integerPart value)
2308 unsigned int n, lsb;
2313 lsb = integerPartWidth - 1;
2314 n = integerPartWidth / 2;
2329 /* Sets the least significant part of a bignum to the input value, and
2330 zeroes out higher parts. */
2332 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2339 for (i = 1; i < parts; i++)
2343 /* Assign one bignum to another. */
2345 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2349 for (i = 0; i < parts; i++)
2353 /* Returns true if a bignum is zero, false otherwise. */
2355 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2359 for (i = 0; i < parts; i++)
2366 /* Extract the given bit of a bignum; returns 0 or 1. */
2368 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2370 return (parts[bit / integerPartWidth] &
2371 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2374 /* Set the given bit of a bignum. */
2376 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2378 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2381 /* Clears the given bit of a bignum. */
2383 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2385 parts[bit / integerPartWidth] &=
2386 ~((integerPart) 1 << (bit % integerPartWidth));
2389 /* Returns the bit number of the least significant set bit of a
2390 number. If the input number has no bits set -1U is returned. */
2392 APInt::tcLSB(const integerPart *parts, unsigned int n)
2394 unsigned int i, lsb;
2396 for (i = 0; i < n; i++) {
2397 if (parts[i] != 0) {
2398 lsb = partLSB(parts[i]);
2400 return lsb + i * integerPartWidth;
2407 /* Returns the bit number of the most significant set bit of a number.
2408 If the input number has no bits set -1U is returned. */
2410 APInt::tcMSB(const integerPart *parts, unsigned int n)
2417 if (parts[n] != 0) {
2418 msb = partMSB(parts[n]);
2420 return msb + n * integerPartWidth;
2427 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2428 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2429 the least significant bit of DST. All high bits above srcBITS in
2430 DST are zero-filled. */
2432 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2433 unsigned int srcBits, unsigned int srcLSB)
2435 unsigned int firstSrcPart, dstParts, shift, n;
2437 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2438 assert(dstParts <= dstCount);
2440 firstSrcPart = srcLSB / integerPartWidth;
2441 tcAssign (dst, src + firstSrcPart, dstParts);
2443 shift = srcLSB % integerPartWidth;
2444 tcShiftRight (dst, dstParts, shift);
2446 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2447 in DST. If this is less that srcBits, append the rest, else
2448 clear the high bits. */
2449 n = dstParts * integerPartWidth - shift;
2451 integerPart mask = lowBitMask (srcBits - n);
2452 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2453 << n % integerPartWidth);
2454 } else if (n > srcBits) {
2455 if (srcBits % integerPartWidth)
2456 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2459 /* Clear high parts. */
2460 while (dstParts < dstCount)
2461 dst[dstParts++] = 0;
2464 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2466 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2467 integerPart c, unsigned int parts)
2473 for (i = 0; i < parts; i++) {
2478 dst[i] += rhs[i] + 1;
2489 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2491 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2492 integerPart c, unsigned int parts)
2498 for (i = 0; i < parts; i++) {
2503 dst[i] -= rhs[i] + 1;
2514 /* Negate a bignum in-place. */
2516 APInt::tcNegate(integerPart *dst, unsigned int parts)
2518 tcComplement(dst, parts);
2519 tcIncrement(dst, parts);
2522 /* DST += SRC * MULTIPLIER + CARRY if add is true
2523 DST = SRC * MULTIPLIER + CARRY if add is false
2525 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2526 they must start at the same point, i.e. DST == SRC.
2528 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2529 returned. Otherwise DST is filled with the least significant
2530 DSTPARTS parts of the result, and if all of the omitted higher
2531 parts were zero return zero, otherwise overflow occurred and
2534 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2535 integerPart multiplier, integerPart carry,
2536 unsigned int srcParts, unsigned int dstParts,
2541 /* Otherwise our writes of DST kill our later reads of SRC. */
2542 assert(dst <= src || dst >= src + srcParts);
2543 assert(dstParts <= srcParts + 1);
2545 /* N loops; minimum of dstParts and srcParts. */
2546 n = dstParts < srcParts ? dstParts: srcParts;
2548 for (i = 0; i < n; i++) {
2549 integerPart low, mid, high, srcPart;
2551 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2553 This cannot overflow, because
2555 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2557 which is less than n^2. */
2561 if (multiplier == 0 || srcPart == 0) {
2565 low = lowHalf(srcPart) * lowHalf(multiplier);
2566 high = highHalf(srcPart) * highHalf(multiplier);
2568 mid = lowHalf(srcPart) * highHalf(multiplier);
2569 high += highHalf(mid);
2570 mid <<= integerPartWidth / 2;
2571 if (low + mid < low)
2575 mid = highHalf(srcPart) * lowHalf(multiplier);
2576 high += highHalf(mid);
2577 mid <<= integerPartWidth / 2;
2578 if (low + mid < low)
2582 /* Now add carry. */
2583 if (low + carry < low)
2589 /* And now DST[i], and store the new low part there. */
2590 if (low + dst[i] < low)
2600 /* Full multiplication, there is no overflow. */
2601 assert(i + 1 == dstParts);
2605 /* We overflowed if there is carry. */
2609 /* We would overflow if any significant unwritten parts would be
2610 non-zero. This is true if any remaining src parts are non-zero
2611 and the multiplier is non-zero. */
2613 for (; i < srcParts; i++)
2617 /* We fitted in the narrow destination. */
2622 /* DST = LHS * RHS, where DST has the same width as the operands and
2623 is filled with the least significant parts of the result. Returns
2624 one if overflow occurred, otherwise zero. DST must be disjoint
2625 from both operands. */
2627 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2628 const integerPart *rhs, unsigned int parts)
2633 assert(dst != lhs && dst != rhs);
2636 tcSet(dst, 0, parts);
2638 for (i = 0; i < parts; i++)
2639 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2645 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2646 operands. No overflow occurs. DST must be disjoint from both
2647 operands. Returns the number of parts required to hold the
2650 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2651 const integerPart *rhs, unsigned int lhsParts,
2652 unsigned int rhsParts)
2654 /* Put the narrower number on the LHS for less loops below. */
2655 if (lhsParts > rhsParts) {
2656 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2660 assert(dst != lhs && dst != rhs);
2662 tcSet(dst, 0, rhsParts);
2664 for (n = 0; n < lhsParts; n++)
2665 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2667 n = lhsParts + rhsParts;
2669 return n - (dst[n - 1] == 0);
2673 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2674 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2675 set REMAINDER to the remainder, return zero. i.e.
2677 OLD_LHS = RHS * LHS + REMAINDER
2679 SCRATCH is a bignum of the same size as the operands and result for
2680 use by the routine; its contents need not be initialized and are
2681 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2684 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2685 integerPart *remainder, integerPart *srhs,
2688 unsigned int n, shiftCount;
2691 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2693 shiftCount = tcMSB(rhs, parts) + 1;
2694 if (shiftCount == 0)
2697 shiftCount = parts * integerPartWidth - shiftCount;
2698 n = shiftCount / integerPartWidth;
2699 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2701 tcAssign(srhs, rhs, parts);
2702 tcShiftLeft(srhs, parts, shiftCount);
2703 tcAssign(remainder, lhs, parts);
2704 tcSet(lhs, 0, parts);
2706 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2711 compare = tcCompare(remainder, srhs, parts);
2713 tcSubtract(remainder, srhs, 0, parts);
2717 if (shiftCount == 0)
2720 tcShiftRight(srhs, parts, 1);
2721 if ((mask >>= 1) == 0)
2722 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2728 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2729 There are no restrictions on COUNT. */
2731 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2734 unsigned int jump, shift;
2736 /* Jump is the inter-part jump; shift is is intra-part shift. */
2737 jump = count / integerPartWidth;
2738 shift = count % integerPartWidth;
2740 while (parts > jump) {
2745 /* dst[i] comes from the two parts src[i - jump] and, if we have
2746 an intra-part shift, src[i - jump - 1]. */
2747 part = dst[parts - jump];
2750 if (parts >= jump + 1)
2751 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2762 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2763 zero. There are no restrictions on COUNT. */
2765 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2768 unsigned int i, jump, shift;
2770 /* Jump is the inter-part jump; shift is is intra-part shift. */
2771 jump = count / integerPartWidth;
2772 shift = count % integerPartWidth;
2774 /* Perform the shift. This leaves the most significant COUNT bits
2775 of the result at zero. */
2776 for (i = 0; i < parts; i++) {
2779 if (i + jump >= parts) {
2782 part = dst[i + jump];
2785 if (i + jump + 1 < parts)
2786 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2795 /* Bitwise and of two bignums. */
2797 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2801 for (i = 0; i < parts; i++)
2805 /* Bitwise inclusive or of two bignums. */
2807 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2811 for (i = 0; i < parts; i++)
2815 /* Bitwise exclusive or of two bignums. */
2817 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2821 for (i = 0; i < parts; i++)
2825 /* Complement a bignum in-place. */
2827 APInt::tcComplement(integerPart *dst, unsigned int parts)
2831 for (i = 0; i < parts; i++)
2835 /* Comparison (unsigned) of two bignums. */
2837 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2842 if (lhs[parts] == rhs[parts])
2845 if (lhs[parts] > rhs[parts])
2854 /* Increment a bignum in-place, return the carry flag. */
2856 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2860 for (i = 0; i < parts; i++)
2867 /* Set the least significant BITS bits of a bignum, clear the
2870 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2876 while (bits > integerPartWidth) {
2877 dst[i++] = ~(integerPart) 0;
2878 bits -= integerPartWidth;
2882 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);