1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/MathExtras.h"
24 #include "llvm/Support/raw_ostream.h"
31 #define DEBUG_TYPE "apint"
33 /// A utility function for allocating memory, checking for allocation failures,
34 /// and ensuring the contents are zeroed.
35 inline static uint64_t* getClearedMemory(unsigned numWords) {
36 uint64_t * result = new uint64_t[numWords];
37 assert(result && "APInt memory allocation fails!");
38 memset(result, 0, numWords * sizeof(uint64_t));
42 /// A utility function for allocating memory and checking for allocation
43 /// failure. The content is not zeroed.
44 inline static uint64_t* getMemory(unsigned numWords) {
45 uint64_t * result = new uint64_t[numWords];
46 assert(result && "APInt memory allocation fails!");
50 /// A utility function that converts a character to a digit.
51 inline static unsigned getDigit(char cdigit, uint8_t radix) {
54 if (radix == 16 || radix == 36) {
78 void APInt::initSlowCase(uint64_t val, bool isSigned) {
79 pVal = getClearedMemory(getNumWords());
81 if (isSigned && int64_t(val) < 0)
82 for (unsigned i = 1; i < getNumWords(); ++i)
86 void APInt::initSlowCase(const APInt& that) {
87 pVal = getMemory(getNumWords());
88 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
91 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
92 assert(BitWidth && "Bitwidth too small");
93 assert(bigVal.data() && "Null pointer detected!");
97 // Get memory, cleared to 0
98 pVal = getClearedMemory(getNumWords());
99 // Calculate the number of words to copy
100 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
101 // Copy the words from bigVal to pVal
102 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
104 // Make sure unused high bits are cleared
108 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
109 : BitWidth(numBits), VAL(0) {
110 initFromArray(bigVal);
113 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
114 : BitWidth(numBits), VAL(0) {
115 initFromArray(makeArrayRef(bigVal, numWords));
118 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
119 : BitWidth(numbits), VAL(0) {
120 assert(BitWidth && "Bitwidth too small");
121 fromString(numbits, Str, radix);
124 APInt& APInt::AssignSlowCase(const APInt& RHS) {
125 // Don't do anything for X = X
129 if (BitWidth == RHS.getBitWidth()) {
130 // assume same bit-width single-word case is already handled
131 assert(!isSingleWord());
132 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
136 if (isSingleWord()) {
137 // assume case where both are single words is already handled
138 assert(!RHS.isSingleWord());
140 pVal = getMemory(RHS.getNumWords());
141 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
142 } else if (getNumWords() == RHS.getNumWords())
143 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
144 else if (RHS.isSingleWord()) {
149 pVal = getMemory(RHS.getNumWords());
150 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
152 BitWidth = RHS.BitWidth;
153 return clearUnusedBits();
156 APInt& APInt::operator=(uint64_t RHS) {
161 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
163 return clearUnusedBits();
166 /// This method 'profiles' an APInt for use with FoldingSet.
167 void APInt::Profile(FoldingSetNodeID& ID) const {
168 ID.AddInteger(BitWidth);
170 if (isSingleWord()) {
175 unsigned NumWords = getNumWords();
176 for (unsigned i = 0; i < NumWords; ++i)
177 ID.AddInteger(pVal[i]);
180 /// This function adds a single "digit" integer, y, to the multiple
181 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
182 /// 1 is returned if there is a carry out, otherwise 0 is returned.
183 /// @returns the carry of the addition.
184 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
185 for (unsigned i = 0; i < len; ++i) {
188 y = 1; // Carry one to next digit.
190 y = 0; // No need to carry so exit early
197 /// @brief Prefix increment operator. Increments the APInt by one.
198 APInt& APInt::operator++() {
202 add_1(pVal, pVal, getNumWords(), 1);
203 return clearUnusedBits();
206 /// This function subtracts a single "digit" (64-bit word), y, from
207 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
208 /// no further borrowing is needed or it runs out of "digits" in x. The result
209 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
210 /// In other words, if y > x then this function returns 1, otherwise 0.
211 /// @returns the borrow out of the subtraction
212 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
213 for (unsigned i = 0; i < len; ++i) {
217 y = 1; // We have to "borrow 1" from next "digit"
219 y = 0; // No need to borrow
220 break; // Remaining digits are unchanged so exit early
226 /// @brief Prefix decrement operator. Decrements the APInt by one.
227 APInt& APInt::operator--() {
231 sub_1(pVal, getNumWords(), 1);
232 return clearUnusedBits();
235 /// This function adds the integer array x to the integer array Y and
236 /// places the result in dest.
237 /// @returns the carry out from the addition
238 /// @brief General addition of 64-bit integer arrays
239 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
242 for (unsigned i = 0; i< len; ++i) {
243 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
244 dest[i] = x[i] + y[i] + carry;
245 carry = dest[i] < limit || (carry && dest[i] == limit);
250 /// Adds the RHS APint to this APInt.
251 /// @returns this, after addition of RHS.
252 /// @brief Addition assignment operator.
253 APInt& APInt::operator+=(const APInt& RHS) {
254 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
258 add(pVal, pVal, RHS.pVal, getNumWords());
260 return clearUnusedBits();
263 APInt& APInt::operator+=(uint64_t RHS) {
267 add_1(pVal, pVal, getNumWords(), RHS);
268 return clearUnusedBits();
271 /// Subtracts the integer array y from the integer array x
272 /// @returns returns the borrow out.
273 /// @brief Generalized subtraction of 64-bit integer arrays.
274 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
277 for (unsigned i = 0; i < len; ++i) {
278 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
279 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
280 dest[i] = x_tmp - y[i];
285 /// Subtracts the RHS APInt from this APInt
286 /// @returns this, after subtraction
287 /// @brief Subtraction assignment operator.
288 APInt& APInt::operator-=(const APInt& RHS) {
289 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
293 sub(pVal, pVal, RHS.pVal, getNumWords());
294 return clearUnusedBits();
297 APInt& APInt::operator-=(uint64_t RHS) {
301 sub_1(pVal, getNumWords(), RHS);
302 return clearUnusedBits();
305 /// Multiplies an integer array, x, by a uint64_t integer and places the result
307 /// @returns the carry out of the multiplication.
308 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
309 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
310 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
311 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
314 // For each digit of x.
315 for (unsigned i = 0; i < len; ++i) {
316 // Split x into high and low words
317 uint64_t lx = x[i] & 0xffffffffULL;
318 uint64_t hx = x[i] >> 32;
319 // hasCarry - A flag to indicate if there is a carry to the next digit.
320 // hasCarry == 0, no carry
321 // hasCarry == 1, has carry
322 // hasCarry == 2, no carry and the calculation result == 0.
323 uint8_t hasCarry = 0;
324 dest[i] = carry + lx * ly;
325 // Determine if the add above introduces carry.
326 hasCarry = (dest[i] < carry) ? 1 : 0;
327 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
328 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
329 // (2^32 - 1) + 2^32 = 2^64.
330 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
332 carry += (lx * hy) & 0xffffffffULL;
333 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
334 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
335 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
340 /// Multiplies integer array x by integer array y and stores the result into
341 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
342 /// @brief Generalized multiplicate of integer arrays.
343 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
345 dest[xlen] = mul_1(dest, x, xlen, y[0]);
346 for (unsigned i = 1; i < ylen; ++i) {
347 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
348 uint64_t carry = 0, lx = 0, hx = 0;
349 for (unsigned j = 0; j < xlen; ++j) {
350 lx = x[j] & 0xffffffffULL;
352 // hasCarry - A flag to indicate if has carry.
353 // hasCarry == 0, no carry
354 // hasCarry == 1, has carry
355 // hasCarry == 2, no carry and the calculation result == 0.
356 uint8_t hasCarry = 0;
357 uint64_t resul = carry + lx * ly;
358 hasCarry = (resul < carry) ? 1 : 0;
359 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
360 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
362 carry += (lx * hy) & 0xffffffffULL;
363 resul = (carry << 32) | (resul & 0xffffffffULL);
365 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
366 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
367 ((lx * hy) >> 32) + hx * hy;
369 dest[i+xlen] = carry;
373 APInt& APInt::operator*=(const APInt& RHS) {
374 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
375 if (isSingleWord()) {
381 // Get some bit facts about LHS and check for zero
382 unsigned lhsBits = getActiveBits();
383 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
388 // Get some bit facts about RHS and check for zero
389 unsigned rhsBits = RHS.getActiveBits();
390 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
397 // Allocate space for the result
398 unsigned destWords = rhsWords + lhsWords;
399 uint64_t *dest = getMemory(destWords);
401 // Perform the long multiply
402 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
404 // Copy result back into *this
406 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
407 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
410 // delete dest array and return
415 APInt& APInt::operator&=(const APInt& RHS) {
416 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
417 if (isSingleWord()) {
421 unsigned numWords = getNumWords();
422 for (unsigned i = 0; i < numWords; ++i)
423 pVal[i] &= RHS.pVal[i];
427 APInt& APInt::operator|=(const APInt& RHS) {
428 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
429 if (isSingleWord()) {
433 unsigned numWords = getNumWords();
434 for (unsigned i = 0; i < numWords; ++i)
435 pVal[i] |= RHS.pVal[i];
439 APInt& APInt::operator^=(const APInt& RHS) {
440 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
441 if (isSingleWord()) {
443 this->clearUnusedBits();
446 unsigned numWords = getNumWords();
447 for (unsigned i = 0; i < numWords; ++i)
448 pVal[i] ^= RHS.pVal[i];
449 return clearUnusedBits();
452 APInt APInt::AndSlowCase(const APInt& RHS) const {
453 unsigned numWords = getNumWords();
454 uint64_t* val = getMemory(numWords);
455 for (unsigned i = 0; i < numWords; ++i)
456 val[i] = pVal[i] & RHS.pVal[i];
457 return APInt(val, getBitWidth());
460 APInt APInt::OrSlowCase(const APInt& RHS) const {
461 unsigned numWords = getNumWords();
462 uint64_t *val = getMemory(numWords);
463 for (unsigned i = 0; i < numWords; ++i)
464 val[i] = pVal[i] | RHS.pVal[i];
465 return APInt(val, getBitWidth());
468 APInt APInt::XorSlowCase(const APInt& RHS) const {
469 unsigned numWords = getNumWords();
470 uint64_t *val = getMemory(numWords);
471 for (unsigned i = 0; i < numWords; ++i)
472 val[i] = pVal[i] ^ RHS.pVal[i];
474 APInt Result(val, getBitWidth());
475 // 0^0==1 so clear the high bits in case they got set.
476 Result.clearUnusedBits();
480 APInt APInt::operator*(const APInt& RHS) const {
481 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
483 return APInt(BitWidth, VAL * RHS.VAL);
489 bool APInt::EqualSlowCase(const APInt& RHS) const {
490 return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
493 bool APInt::EqualSlowCase(uint64_t Val) const {
494 unsigned n = getActiveBits();
495 if (n <= APINT_BITS_PER_WORD)
496 return pVal[0] == Val;
501 bool APInt::ult(const APInt& RHS) const {
502 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
504 return VAL < RHS.VAL;
506 // Get active bit length of both operands
507 unsigned n1 = getActiveBits();
508 unsigned n2 = RHS.getActiveBits();
510 // If magnitude of LHS is less than RHS, return true.
514 // If magnitude of RHS is greather than LHS, return false.
518 // If they bot fit in a word, just compare the low order word
519 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
520 return pVal[0] < RHS.pVal[0];
522 // Otherwise, compare all words
523 unsigned topWord = whichWord(std::max(n1,n2)-1);
524 for (int i = topWord; i >= 0; --i) {
525 if (pVal[i] > RHS.pVal[i])
527 if (pVal[i] < RHS.pVal[i])
533 bool APInt::slt(const APInt& RHS) const {
534 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
535 if (isSingleWord()) {
536 int64_t lhsSext = SignExtend64(VAL, BitWidth);
537 int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
538 return lhsSext < rhsSext;
541 bool lhsNeg = isNegative();
542 bool rhsNeg = RHS.isNegative();
544 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
545 if (lhsNeg != rhsNeg)
548 // Otherwise we can just use an unsigned comparision, because even negative
549 // numbers compare correctly this way if both have the same signed-ness.
553 void APInt::setBit(unsigned bitPosition) {
555 VAL |= maskBit(bitPosition);
557 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
560 /// Set the given bit to 0 whose position is given as "bitPosition".
561 /// @brief Set a given bit to 0.
562 void APInt::clearBit(unsigned bitPosition) {
564 VAL &= ~maskBit(bitPosition);
566 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
569 /// @brief Toggle every bit to its opposite value.
571 /// Toggle a given bit to its opposite value whose position is given
572 /// as "bitPosition".
573 /// @brief Toggles a given bit to its opposite value.
574 void APInt::flipBit(unsigned bitPosition) {
575 assert(bitPosition < BitWidth && "Out of the bit-width range!");
576 if ((*this)[bitPosition]) clearBit(bitPosition);
577 else setBit(bitPosition);
580 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
581 assert(!str.empty() && "Invalid string length");
582 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
584 "Radix should be 2, 8, 10, 16, or 36!");
586 size_t slen = str.size();
588 // Each computation below needs to know if it's negative.
589 StringRef::iterator p = str.begin();
590 unsigned isNegative = *p == '-';
591 if (*p == '-' || *p == '+') {
594 assert(slen && "String is only a sign, needs a value.");
597 // For radixes of power-of-two values, the bits required is accurately and
600 return slen + isNegative;
602 return slen * 3 + isNegative;
604 return slen * 4 + isNegative;
608 // This is grossly inefficient but accurate. We could probably do something
609 // with a computation of roughly slen*64/20 and then adjust by the value of
610 // the first few digits. But, I'm not sure how accurate that could be.
612 // Compute a sufficient number of bits that is always large enough but might
613 // be too large. This avoids the assertion in the constructor. This
614 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
615 // bits in that case.
617 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
618 : (slen == 1 ? 7 : slen * 16/3);
620 // Convert to the actual binary value.
621 APInt tmp(sufficient, StringRef(p, slen), radix);
623 // Compute how many bits are required. If the log is infinite, assume we need
625 unsigned log = tmp.logBase2();
626 if (log == (unsigned)-1) {
627 return isNegative + 1;
629 return isNegative + log + 1;
633 hash_code llvm::hash_value(const APInt &Arg) {
634 if (Arg.isSingleWord())
635 return hash_combine(Arg.VAL);
637 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
640 bool APInt::isSplat(unsigned SplatSizeInBits) const {
641 assert(getBitWidth() % SplatSizeInBits == 0 &&
642 "SplatSizeInBits must divide width!");
643 // We can check that all parts of an integer are equal by making use of a
644 // little trick: rotate and check if it's still the same value.
645 return *this == rotl(SplatSizeInBits);
648 /// This function returns the high "numBits" bits of this APInt.
649 APInt APInt::getHiBits(unsigned numBits) const {
650 return APIntOps::lshr(*this, BitWidth - numBits);
653 /// This function returns the low "numBits" bits of this APInt.
654 APInt APInt::getLoBits(unsigned numBits) const {
655 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
659 unsigned APInt::countLeadingZerosSlowCase() const {
661 for (int i = getNumWords()-1; i >= 0; --i) {
662 integerPart V = pVal[i];
664 Count += APINT_BITS_PER_WORD;
666 Count += llvm::countLeadingZeros(V);
670 // Adjust for unused bits in the most significant word (they are zero).
671 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
672 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
676 unsigned APInt::countLeadingOnes() const {
678 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
680 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
683 highWordBits = APINT_BITS_PER_WORD;
686 shift = APINT_BITS_PER_WORD - highWordBits;
688 int i = getNumWords() - 1;
689 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
690 if (Count == highWordBits) {
691 for (i--; i >= 0; --i) {
692 if (pVal[i] == -1ULL)
693 Count += APINT_BITS_PER_WORD;
695 Count += llvm::countLeadingOnes(pVal[i]);
703 unsigned APInt::countTrailingZeros() const {
705 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
708 for (; i < getNumWords() && pVal[i] == 0; ++i)
709 Count += APINT_BITS_PER_WORD;
710 if (i < getNumWords())
711 Count += llvm::countTrailingZeros(pVal[i]);
712 return std::min(Count, BitWidth);
715 unsigned APInt::countTrailingOnesSlowCase() const {
718 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
719 Count += APINT_BITS_PER_WORD;
720 if (i < getNumWords())
721 Count += llvm::countTrailingOnes(pVal[i]);
722 return std::min(Count, BitWidth);
725 unsigned APInt::countPopulationSlowCase() const {
727 for (unsigned i = 0; i < getNumWords(); ++i)
728 Count += llvm::countPopulation(pVal[i]);
732 /// Perform a logical right-shift from Src to Dst, which must be equal or
733 /// non-overlapping, of Words words, by Shift, which must be less than 64.
734 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
737 for (int I = Words - 1; I >= 0; --I) {
738 uint64_t Tmp = Src[I];
739 Dst[I] = (Tmp >> Shift) | Carry;
740 Carry = Tmp << (64 - Shift);
744 APInt APInt::byteSwap() const {
745 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
747 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
749 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
750 if (BitWidth == 48) {
751 unsigned Tmp1 = unsigned(VAL >> 16);
752 Tmp1 = ByteSwap_32(Tmp1);
753 uint16_t Tmp2 = uint16_t(VAL);
754 Tmp2 = ByteSwap_16(Tmp2);
755 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
758 return APInt(BitWidth, ByteSwap_64(VAL));
760 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
761 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
762 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
763 if (Result.BitWidth != BitWidth) {
764 lshrNear(Result.pVal, Result.pVal, getNumWords(),
765 Result.BitWidth - BitWidth);
766 Result.BitWidth = BitWidth;
771 APInt APInt::reverseBits() const {
774 return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
776 return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
778 return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
780 return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
786 APInt Reversed(*this);
787 int S = BitWidth - 1;
789 const APInt One(BitWidth, 1);
791 for ((Val = Val.lshr(1)); Val != 0; (Val = Val.lshr(1))) {
793 Reversed |= (Val & One);
801 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
803 APInt A = API1, B = API2;
806 B = APIntOps::urem(A, B);
812 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
819 // Get the sign bit from the highest order bit
820 bool isNeg = T.I >> 63;
822 // Get the 11-bit exponent and adjust for the 1023 bit bias
823 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
825 // If the exponent is negative, the value is < 0 so just return 0.
827 return APInt(width, 0u);
829 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
830 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
832 // If the exponent doesn't shift all bits out of the mantissa
834 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
835 APInt(width, mantissa >> (52 - exp));
837 // If the client didn't provide enough bits for us to shift the mantissa into
838 // then the result is undefined, just return 0
839 if (width <= exp - 52)
840 return APInt(width, 0);
842 // Otherwise, we have to shift the mantissa bits up to the right location
843 APInt Tmp(width, mantissa);
844 Tmp = Tmp.shl((unsigned)exp - 52);
845 return isNeg ? -Tmp : Tmp;
848 /// This function converts this APInt to a double.
849 /// The layout for double is as following (IEEE Standard 754):
850 /// --------------------------------------
851 /// | Sign Exponent Fraction Bias |
852 /// |-------------------------------------- |
853 /// | 1[63] 11[62-52] 52[51-00] 1023 |
854 /// --------------------------------------
855 double APInt::roundToDouble(bool isSigned) const {
857 // Handle the simple case where the value is contained in one uint64_t.
858 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
859 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
861 int64_t sext = SignExtend64(getWord(0), BitWidth);
864 return double(getWord(0));
867 // Determine if the value is negative.
868 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
870 // Construct the absolute value if we're negative.
871 APInt Tmp(isNeg ? -(*this) : (*this));
873 // Figure out how many bits we're using.
874 unsigned n = Tmp.getActiveBits();
876 // The exponent (without bias normalization) is just the number of bits
877 // we are using. Note that the sign bit is gone since we constructed the
881 // Return infinity for exponent overflow
883 if (!isSigned || !isNeg)
884 return std::numeric_limits<double>::infinity();
886 return -std::numeric_limits<double>::infinity();
888 exp += 1023; // Increment for 1023 bias
890 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
891 // extract the high 52 bits from the correct words in pVal.
893 unsigned hiWord = whichWord(n-1);
895 mantissa = Tmp.pVal[0];
897 mantissa >>= n - 52; // shift down, we want the top 52 bits.
899 assert(hiWord > 0 && "huh?");
900 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
901 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
902 mantissa = hibits | lobits;
905 // The leading bit of mantissa is implicit, so get rid of it.
906 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
911 T.I = sign | (exp << 52) | mantissa;
915 // Truncate to new width.
916 APInt APInt::trunc(unsigned width) const {
917 assert(width < BitWidth && "Invalid APInt Truncate request");
918 assert(width && "Can't truncate to 0 bits");
920 if (width <= APINT_BITS_PER_WORD)
921 return APInt(width, getRawData()[0]);
923 APInt Result(getMemory(getNumWords(width)), width);
927 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
928 Result.pVal[i] = pVal[i];
930 // Truncate and copy any partial word.
931 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
933 Result.pVal[i] = pVal[i] << bits >> bits;
938 // Sign extend to a new width.
939 APInt APInt::sext(unsigned width) const {
940 assert(width > BitWidth && "Invalid APInt SignExtend request");
942 if (width <= APINT_BITS_PER_WORD) {
943 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
944 val = (int64_t)val >> (width - BitWidth);
945 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
948 APInt Result(getMemory(getNumWords(width)), width);
953 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
954 word = getRawData()[i];
955 Result.pVal[i] = word;
958 // Read and sign-extend any partial word.
959 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
961 word = (int64_t)getRawData()[i] << bits >> bits;
963 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
965 // Write remaining full words.
966 for (; i != width / APINT_BITS_PER_WORD; i++) {
967 Result.pVal[i] = word;
968 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
971 // Write any partial word.
972 bits = (0 - width) % APINT_BITS_PER_WORD;
974 Result.pVal[i] = word << bits >> bits;
979 // Zero extend to a new width.
980 APInt APInt::zext(unsigned width) const {
981 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
983 if (width <= APINT_BITS_PER_WORD)
984 return APInt(width, VAL);
986 APInt Result(getMemory(getNumWords(width)), width);
990 for (i = 0; i != getNumWords(); i++)
991 Result.pVal[i] = getRawData()[i];
993 // Zero remaining words.
994 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
999 APInt APInt::zextOrTrunc(unsigned width) const {
1000 if (BitWidth < width)
1002 if (BitWidth > width)
1003 return trunc(width);
1007 APInt APInt::sextOrTrunc(unsigned width) const {
1008 if (BitWidth < width)
1010 if (BitWidth > width)
1011 return trunc(width);
1015 APInt APInt::zextOrSelf(unsigned width) const {
1016 if (BitWidth < width)
1021 APInt APInt::sextOrSelf(unsigned width) const {
1022 if (BitWidth < width)
1027 /// Arithmetic right-shift this APInt by shiftAmt.
1028 /// @brief Arithmetic right-shift function.
1029 APInt APInt::ashr(const APInt &shiftAmt) const {
1030 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1033 /// Arithmetic right-shift this APInt by shiftAmt.
1034 /// @brief Arithmetic right-shift function.
1035 APInt APInt::ashr(unsigned shiftAmt) const {
1036 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1037 // Handle a degenerate case
1041 // Handle single word shifts with built-in ashr
1042 if (isSingleWord()) {
1043 if (shiftAmt == BitWidth)
1044 return APInt(BitWidth, 0); // undefined
1045 return APInt(BitWidth, SignExtend64(VAL, BitWidth) >> shiftAmt);
1048 // If all the bits were shifted out, the result is, technically, undefined.
1049 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1050 // issues in the algorithm below.
1051 if (shiftAmt == BitWidth) {
1053 return APInt(BitWidth, -1ULL, true);
1055 return APInt(BitWidth, 0);
1058 // Create some space for the result.
1059 uint64_t * val = new uint64_t[getNumWords()];
1061 // Compute some values needed by the following shift algorithms
1062 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1063 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1064 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1065 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1066 if (bitsInWord == 0)
1067 bitsInWord = APINT_BITS_PER_WORD;
1069 // If we are shifting whole words, just move whole words
1070 if (wordShift == 0) {
1071 // Move the words containing significant bits
1072 for (unsigned i = 0; i <= breakWord; ++i)
1073 val[i] = pVal[i+offset]; // move whole word
1075 // Adjust the top significant word for sign bit fill, if negative
1077 if (bitsInWord < APINT_BITS_PER_WORD)
1078 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1080 // Shift the low order words
1081 for (unsigned i = 0; i < breakWord; ++i) {
1082 // This combines the shifted corresponding word with the low bits from
1083 // the next word (shifted into this word's high bits).
1084 val[i] = (pVal[i+offset] >> wordShift) |
1085 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1088 // Shift the break word. In this case there are no bits from the next word
1089 // to include in this word.
1090 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1092 // Deal with sign extension in the break word, and possibly the word before
1095 if (wordShift > bitsInWord) {
1098 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1099 val[breakWord] |= ~0ULL;
1101 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1105 // Remaining words are 0 or -1, just assign them.
1106 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1107 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1109 APInt Result(val, BitWidth);
1110 Result.clearUnusedBits();
1114 /// Logical right-shift this APInt by shiftAmt.
1115 /// @brief Logical right-shift function.
1116 APInt APInt::lshr(const APInt &shiftAmt) const {
1117 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1120 /// Logical right-shift this APInt by shiftAmt.
1121 /// @brief Logical right-shift function.
1122 APInt APInt::lshr(unsigned shiftAmt) const {
1123 if (isSingleWord()) {
1124 if (shiftAmt >= BitWidth)
1125 return APInt(BitWidth, 0);
1127 return APInt(BitWidth, this->VAL >> shiftAmt);
1130 // If all the bits were shifted out, the result is 0. This avoids issues
1131 // with shifting by the size of the integer type, which produces undefined
1132 // results. We define these "undefined results" to always be 0.
1133 if (shiftAmt >= BitWidth)
1134 return APInt(BitWidth, 0);
1136 // If none of the bits are shifted out, the result is *this. This avoids
1137 // issues with shifting by the size of the integer type, which produces
1138 // undefined results in the code below. This is also an optimization.
1142 // Create some space for the result.
1143 uint64_t * val = new uint64_t[getNumWords()];
1145 // If we are shifting less than a word, compute the shift with a simple carry
1146 if (shiftAmt < APINT_BITS_PER_WORD) {
1147 lshrNear(val, pVal, getNumWords(), shiftAmt);
1148 APInt Result(val, BitWidth);
1149 Result.clearUnusedBits();
1153 // Compute some values needed by the remaining shift algorithms
1154 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1155 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1157 // If we are shifting whole words, just move whole words
1158 if (wordShift == 0) {
1159 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1160 val[i] = pVal[i+offset];
1161 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1163 APInt Result(val, BitWidth);
1164 Result.clearUnusedBits();
1168 // Shift the low order words
1169 unsigned breakWord = getNumWords() - offset -1;
1170 for (unsigned i = 0; i < breakWord; ++i)
1171 val[i] = (pVal[i+offset] >> wordShift) |
1172 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1173 // Shift the break word.
1174 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1176 // Remaining words are 0
1177 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1179 APInt Result(val, BitWidth);
1180 Result.clearUnusedBits();
1184 /// Left-shift this APInt by shiftAmt.
1185 /// @brief Left-shift function.
1186 APInt APInt::shl(const APInt &shiftAmt) const {
1187 // It's undefined behavior in C to shift by BitWidth or greater.
1188 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1191 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1192 // If all the bits were shifted out, the result is 0. This avoids issues
1193 // with shifting by the size of the integer type, which produces undefined
1194 // results. We define these "undefined results" to always be 0.
1195 if (shiftAmt == BitWidth)
1196 return APInt(BitWidth, 0);
1198 // If none of the bits are shifted out, the result is *this. This avoids a
1199 // lshr by the words size in the loop below which can produce incorrect
1200 // results. It also avoids the expensive computation below for a common case.
1204 // Create some space for the result.
1205 uint64_t * val = new uint64_t[getNumWords()];
1207 // If we are shifting less than a word, do it the easy way
1208 if (shiftAmt < APINT_BITS_PER_WORD) {
1210 for (unsigned i = 0; i < getNumWords(); i++) {
1211 val[i] = pVal[i] << shiftAmt | carry;
1212 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1214 APInt Result(val, BitWidth);
1215 Result.clearUnusedBits();
1219 // Compute some values needed by the remaining shift algorithms
1220 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1221 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1223 // If we are shifting whole words, just move whole words
1224 if (wordShift == 0) {
1225 for (unsigned i = 0; i < offset; i++)
1227 for (unsigned i = offset; i < getNumWords(); i++)
1228 val[i] = pVal[i-offset];
1229 APInt Result(val, BitWidth);
1230 Result.clearUnusedBits();
1234 // Copy whole words from this to Result.
1235 unsigned i = getNumWords() - 1;
1236 for (; i > offset; --i)
1237 val[i] = pVal[i-offset] << wordShift |
1238 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1239 val[offset] = pVal[0] << wordShift;
1240 for (i = 0; i < offset; ++i)
1242 APInt Result(val, BitWidth);
1243 Result.clearUnusedBits();
1247 APInt APInt::rotl(const APInt &rotateAmt) const {
1248 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1251 APInt APInt::rotl(unsigned rotateAmt) const {
1252 rotateAmt %= BitWidth;
1255 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1258 APInt APInt::rotr(const APInt &rotateAmt) const {
1259 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1262 APInt APInt::rotr(unsigned rotateAmt) const {
1263 rotateAmt %= BitWidth;
1266 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1269 // Square Root - this method computes and returns the square root of "this".
1270 // Three mechanisms are used for computation. For small values (<= 5 bits),
1271 // a table lookup is done. This gets some performance for common cases. For
1272 // values using less than 52 bits, the value is converted to double and then
1273 // the libc sqrt function is called. The result is rounded and then converted
1274 // back to a uint64_t which is then used to construct the result. Finally,
1275 // the Babylonian method for computing square roots is used.
1276 APInt APInt::sqrt() const {
1278 // Determine the magnitude of the value.
1279 unsigned magnitude = getActiveBits();
1281 // Use a fast table for some small values. This also gets rid of some
1282 // rounding errors in libc sqrt for small values.
1283 if (magnitude <= 5) {
1284 static const uint8_t results[32] = {
1287 /* 3- 6 */ 2, 2, 2, 2,
1288 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1289 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1290 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1293 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1296 // If the magnitude of the value fits in less than 52 bits (the precision of
1297 // an IEEE double precision floating point value), then we can use the
1298 // libc sqrt function which will probably use a hardware sqrt computation.
1299 // This should be faster than the algorithm below.
1300 if (magnitude < 52) {
1301 return APInt(BitWidth,
1302 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1305 // Okay, all the short cuts are exhausted. We must compute it. The following
1306 // is a classical Babylonian method for computing the square root. This code
1307 // was adapted to APInt from a wikipedia article on such computations.
1308 // See http://www.wikipedia.org/ and go to the page named
1309 // Calculate_an_integer_square_root.
1310 unsigned nbits = BitWidth, i = 4;
1311 APInt testy(BitWidth, 16);
1312 APInt x_old(BitWidth, 1);
1313 APInt x_new(BitWidth, 0);
1314 APInt two(BitWidth, 2);
1316 // Select a good starting value using binary logarithms.
1317 for (;; i += 2, testy = testy.shl(2))
1318 if (i >= nbits || this->ule(testy)) {
1319 x_old = x_old.shl(i / 2);
1323 // Use the Babylonian method to arrive at the integer square root:
1325 x_new = (this->udiv(x_old) + x_old).udiv(two);
1326 if (x_old.ule(x_new))
1331 // Make sure we return the closest approximation
1332 // NOTE: The rounding calculation below is correct. It will produce an
1333 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1334 // determined to be a rounding issue with pari/gp as it begins to use a
1335 // floating point representation after 192 bits. There are no discrepancies
1336 // between this algorithm and pari/gp for bit widths < 192 bits.
1337 APInt square(x_old * x_old);
1338 APInt nextSquare((x_old + 1) * (x_old +1));
1339 if (this->ult(square))
1341 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1342 APInt midpoint((nextSquare - square).udiv(two));
1343 APInt offset(*this - square);
1344 if (offset.ult(midpoint))
1349 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1350 /// iterative extended Euclidean algorithm is used to solve for this value,
1351 /// however we simplify it to speed up calculating only the inverse, and take
1352 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1353 /// (potentially large) APInts around.
1354 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1355 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1357 // Using the properties listed at the following web page (accessed 06/21/08):
1358 // http://www.numbertheory.org/php/euclid.html
1359 // (especially the properties numbered 3, 4 and 9) it can be proved that
1360 // BitWidth bits suffice for all the computations in the algorithm implemented
1361 // below. More precisely, this number of bits suffice if the multiplicative
1362 // inverse exists, but may not suffice for the general extended Euclidean
1365 APInt r[2] = { modulo, *this };
1366 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1367 APInt q(BitWidth, 0);
1370 for (i = 0; r[i^1] != 0; i ^= 1) {
1371 // An overview of the math without the confusing bit-flipping:
1372 // q = r[i-2] / r[i-1]
1373 // r[i] = r[i-2] % r[i-1]
1374 // t[i] = t[i-2] - t[i-1] * q
1375 udivrem(r[i], r[i^1], q, r[i]);
1379 // If this APInt and the modulo are not coprime, there is no multiplicative
1380 // inverse, so return 0. We check this by looking at the next-to-last
1381 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1384 return APInt(BitWidth, 0);
1386 // The next-to-last t is the multiplicative inverse. However, we are
1387 // interested in a positive inverse. Calcuate a positive one from a negative
1388 // one if necessary. A simple addition of the modulo suffices because
1389 // abs(t[i]) is known to be less than *this/2 (see the link above).
1390 return t[i].isNegative() ? t[i] + modulo : t[i];
1393 /// Calculate the magic numbers required to implement a signed integer division
1394 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1395 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1396 /// Warren, Jr., chapter 10.
1397 APInt::ms APInt::magic() const {
1398 const APInt& d = *this;
1400 APInt ad, anc, delta, q1, r1, q2, r2, t;
1401 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1405 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1406 anc = t - 1 - t.urem(ad); // absolute value of nc
1407 p = d.getBitWidth() - 1; // initialize p
1408 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1409 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1410 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1411 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1414 q1 = q1<<1; // update q1 = 2p/abs(nc)
1415 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1416 if (r1.uge(anc)) { // must be unsigned comparison
1420 q2 = q2<<1; // update q2 = 2p/abs(d)
1421 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1422 if (r2.uge(ad)) { // must be unsigned comparison
1427 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1430 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1431 mag.s = p - d.getBitWidth(); // resulting shift
1435 /// Calculate the magic numbers required to implement an unsigned integer
1436 /// division by a constant as a sequence of multiplies, adds and shifts.
1437 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1438 /// S. Warren, Jr., chapter 10.
1439 /// LeadingZeros can be used to simplify the calculation if the upper bits
1440 /// of the divided value are known zero.
1441 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1442 const APInt& d = *this;
1444 APInt nc, delta, q1, r1, q2, r2;
1446 magu.a = 0; // initialize "add" indicator
1447 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1448 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1449 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1451 nc = allOnes - (allOnes - d).urem(d);
1452 p = d.getBitWidth() - 1; // initialize p
1453 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1454 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1455 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1456 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1459 if (r1.uge(nc - r1)) {
1460 q1 = q1 + q1 + 1; // update q1
1461 r1 = r1 + r1 - nc; // update r1
1464 q1 = q1+q1; // update q1
1465 r1 = r1+r1; // update r1
1467 if ((r2 + 1).uge(d - r2)) {
1468 if (q2.uge(signedMax)) magu.a = 1;
1469 q2 = q2+q2 + 1; // update q2
1470 r2 = r2+r2 + 1 - d; // update r2
1473 if (q2.uge(signedMin)) magu.a = 1;
1474 q2 = q2+q2; // update q2
1475 r2 = r2+r2 + 1; // update r2
1478 } while (p < d.getBitWidth()*2 &&
1479 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1480 magu.m = q2 + 1; // resulting magic number
1481 magu.s = p - d.getBitWidth(); // resulting shift
1485 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1486 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1487 /// variables here have the same names as in the algorithm. Comments explain
1488 /// the algorithm and any deviation from it.
1489 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1490 unsigned m, unsigned n) {
1491 assert(u && "Must provide dividend");
1492 assert(v && "Must provide divisor");
1493 assert(q && "Must provide quotient");
1494 assert(u != v && u != q && v != q && "Must use different memory");
1495 assert(n>1 && "n must be > 1");
1497 // b denotes the base of the number system. In our case b is 2^32.
1498 const uint64_t b = uint64_t(1) << 32;
1500 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1501 DEBUG(dbgs() << "KnuthDiv: original:");
1502 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1503 DEBUG(dbgs() << " by");
1504 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1505 DEBUG(dbgs() << '\n');
1506 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1507 // u and v by d. Note that we have taken Knuth's advice here to use a power
1508 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1509 // 2 allows us to shift instead of multiply and it is easy to determine the
1510 // shift amount from the leading zeros. We are basically normalizing the u
1511 // and v so that its high bits are shifted to the top of v's range without
1512 // overflow. Note that this can require an extra word in u so that u must
1513 // be of length m+n+1.
1514 unsigned shift = countLeadingZeros(v[n-1]);
1515 unsigned v_carry = 0;
1516 unsigned u_carry = 0;
1518 for (unsigned i = 0; i < m+n; ++i) {
1519 unsigned u_tmp = u[i] >> (32 - shift);
1520 u[i] = (u[i] << shift) | u_carry;
1523 for (unsigned i = 0; i < n; ++i) {
1524 unsigned v_tmp = v[i] >> (32 - shift);
1525 v[i] = (v[i] << shift) | v_carry;
1531 DEBUG(dbgs() << "KnuthDiv: normal:");
1532 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1533 DEBUG(dbgs() << " by");
1534 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1535 DEBUG(dbgs() << '\n');
1537 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1540 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1541 // D3. [Calculate q'.].
1542 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1543 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1544 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1545 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1546 // on v[n-2] determines at high speed most of the cases in which the trial
1547 // value qp is one too large, and it eliminates all cases where qp is two
1549 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1550 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1551 uint64_t qp = dividend / v[n-1];
1552 uint64_t rp = dividend % v[n-1];
1553 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1556 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1559 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1561 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1562 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1563 // consists of a simple multiplication by a one-place number, combined with
1565 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1566 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1567 // true value plus b**(n+1), namely as the b's complement of
1568 // the true value, and a "borrow" to the left should be remembered.
1570 for (unsigned i = 0; i < n; ++i) {
1571 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1572 int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
1573 u[j+i] = (unsigned)subres;
1574 borrow = (p >> 32) - (subres >> 32);
1575 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
1576 << ", borrow = " << borrow << '\n');
1578 bool isNeg = u[j+n] < borrow;
1579 u[j+n] -= (unsigned)borrow;
1581 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1582 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1583 DEBUG(dbgs() << '\n');
1585 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1586 // negative, go to step D6; otherwise go on to step D7.
1587 q[j] = (unsigned)qp;
1589 // D6. [Add back]. The probability that this step is necessary is very
1590 // small, on the order of only 2/b. Make sure that test data accounts for
1591 // this possibility. Decrease q[j] by 1
1593 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1594 // A carry will occur to the left of u[j+n], and it should be ignored
1595 // since it cancels with the borrow that occurred in D4.
1597 for (unsigned i = 0; i < n; i++) {
1598 unsigned limit = std::min(u[j+i],v[i]);
1599 u[j+i] += v[i] + carry;
1600 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1604 DEBUG(dbgs() << "KnuthDiv: after correction:");
1605 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1606 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1608 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1611 DEBUG(dbgs() << "KnuthDiv: quotient:");
1612 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1613 DEBUG(dbgs() << '\n');
1615 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1616 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1617 // compute the remainder (urem uses this).
1619 // The value d is expressed by the "shift" value above since we avoided
1620 // multiplication by d by using a shift left. So, all we have to do is
1621 // shift right here. In order to mak
1624 DEBUG(dbgs() << "KnuthDiv: remainder:");
1625 for (int i = n-1; i >= 0; i--) {
1626 r[i] = (u[i] >> shift) | carry;
1627 carry = u[i] << (32 - shift);
1628 DEBUG(dbgs() << " " << r[i]);
1631 for (int i = n-1; i >= 0; i--) {
1633 DEBUG(dbgs() << " " << r[i]);
1636 DEBUG(dbgs() << '\n');
1638 DEBUG(dbgs() << '\n');
1641 void APInt::divide(const APInt &LHS, unsigned lhsWords, const APInt &RHS,
1642 unsigned rhsWords, APInt *Quotient, APInt *Remainder) {
1643 assert(lhsWords >= rhsWords && "Fractional result");
1645 // First, compose the values into an array of 32-bit words instead of
1646 // 64-bit words. This is a necessity of both the "short division" algorithm
1647 // and the Knuth "classical algorithm" which requires there to be native
1648 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1649 // can't use 64-bit operands here because we don't have native results of
1650 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1651 // work on large-endian machines.
1652 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1653 unsigned n = rhsWords * 2;
1654 unsigned m = (lhsWords * 2) - n;
1656 // Allocate space for the temporary values we need either on the stack, if
1657 // it will fit, or on the heap if it won't.
1658 unsigned SPACE[128];
1659 unsigned *U = nullptr;
1660 unsigned *V = nullptr;
1661 unsigned *Q = nullptr;
1662 unsigned *R = nullptr;
1663 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1666 Q = &SPACE[(m+n+1) + n];
1668 R = &SPACE[(m+n+1) + n + (m+n)];
1670 U = new unsigned[m + n + 1];
1671 V = new unsigned[n];
1672 Q = new unsigned[m+n];
1674 R = new unsigned[n];
1677 // Initialize the dividend
1678 memset(U, 0, (m+n+1)*sizeof(unsigned));
1679 for (unsigned i = 0; i < lhsWords; ++i) {
1680 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1681 U[i * 2] = (unsigned)(tmp & mask);
1682 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1684 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1686 // Initialize the divisor
1687 memset(V, 0, (n)*sizeof(unsigned));
1688 for (unsigned i = 0; i < rhsWords; ++i) {
1689 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1690 V[i * 2] = (unsigned)(tmp & mask);
1691 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1694 // initialize the quotient and remainder
1695 memset(Q, 0, (m+n) * sizeof(unsigned));
1697 memset(R, 0, n * sizeof(unsigned));
1699 // Now, adjust m and n for the Knuth division. n is the number of words in
1700 // the divisor. m is the number of words by which the dividend exceeds the
1701 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1702 // contain any zero words or the Knuth algorithm fails.
1703 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1707 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1710 // If we're left with only a single word for the divisor, Knuth doesn't work
1711 // so we implement the short division algorithm here. This is much simpler
1712 // and faster because we are certain that we can divide a 64-bit quantity
1713 // by a 32-bit quantity at hardware speed and short division is simply a
1714 // series of such operations. This is just like doing short division but we
1715 // are using base 2^32 instead of base 10.
1716 assert(n != 0 && "Divide by zero?");
1718 unsigned divisor = V[0];
1719 unsigned remainder = 0;
1720 for (int i = m+n-1; i >= 0; i--) {
1721 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1722 if (partial_dividend == 0) {
1725 } else if (partial_dividend < divisor) {
1727 remainder = (unsigned)partial_dividend;
1728 } else if (partial_dividend == divisor) {
1732 Q[i] = (unsigned)(partial_dividend / divisor);
1733 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1739 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1741 KnuthDiv(U, V, Q, R, m, n);
1744 // If the caller wants the quotient
1746 // Set up the Quotient value's memory.
1747 if (Quotient->BitWidth != LHS.BitWidth) {
1748 if (Quotient->isSingleWord())
1751 delete [] Quotient->pVal;
1752 Quotient->BitWidth = LHS.BitWidth;
1753 if (!Quotient->isSingleWord())
1754 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1756 Quotient->clearAllBits();
1758 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1760 // This case is currently dead as all users of divide() handle trivial cases
1762 if (lhsWords == 1) {
1764 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1765 if (Quotient->isSingleWord())
1766 Quotient->VAL = tmp;
1768 Quotient->pVal[0] = tmp;
1770 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1771 for (unsigned i = 0; i < lhsWords; ++i)
1773 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1777 // If the caller wants the remainder
1779 // Set up the Remainder value's memory.
1780 if (Remainder->BitWidth != RHS.BitWidth) {
1781 if (Remainder->isSingleWord())
1784 delete [] Remainder->pVal;
1785 Remainder->BitWidth = RHS.BitWidth;
1786 if (!Remainder->isSingleWord())
1787 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1789 Remainder->clearAllBits();
1791 // The remainder is in R. Reconstitute the remainder into Remainder's low
1793 if (rhsWords == 1) {
1795 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1796 if (Remainder->isSingleWord())
1797 Remainder->VAL = tmp;
1799 Remainder->pVal[0] = tmp;
1801 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1802 for (unsigned i = 0; i < rhsWords; ++i)
1803 Remainder->pVal[i] =
1804 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1808 // Clean up the memory we allocated.
1809 if (U != &SPACE[0]) {
1817 APInt APInt::udiv(const APInt& RHS) const {
1818 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1820 // First, deal with the easy case
1821 if (isSingleWord()) {
1822 assert(RHS.VAL != 0 && "Divide by zero?");
1823 return APInt(BitWidth, VAL / RHS.VAL);
1826 // Get some facts about the LHS and RHS number of bits and words
1827 unsigned rhsBits = RHS.getActiveBits();
1828 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1829 assert(rhsWords && "Divided by zero???");
1830 unsigned lhsBits = this->getActiveBits();
1831 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1833 // Deal with some degenerate cases
1836 return APInt(BitWidth, 0);
1837 else if (lhsWords < rhsWords || this->ult(RHS)) {
1838 // X / Y ===> 0, iff X < Y
1839 return APInt(BitWidth, 0);
1840 } else if (*this == RHS) {
1842 return APInt(BitWidth, 1);
1843 } else if (lhsWords == 1 && rhsWords == 1) {
1844 // All high words are zero, just use native divide
1845 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1848 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1849 APInt Quotient(1,0); // to hold result.
1850 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
1854 APInt APInt::sdiv(const APInt &RHS) const {
1856 if (RHS.isNegative())
1857 return (-(*this)).udiv(-RHS);
1858 return -((-(*this)).udiv(RHS));
1860 if (RHS.isNegative())
1861 return -(this->udiv(-RHS));
1862 return this->udiv(RHS);
1865 APInt APInt::urem(const APInt& RHS) const {
1866 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1867 if (isSingleWord()) {
1868 assert(RHS.VAL != 0 && "Remainder by zero?");
1869 return APInt(BitWidth, VAL % RHS.VAL);
1872 // Get some facts about the LHS
1873 unsigned lhsBits = getActiveBits();
1874 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1876 // Get some facts about the RHS
1877 unsigned rhsBits = RHS.getActiveBits();
1878 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1879 assert(rhsWords && "Performing remainder operation by zero ???");
1881 // Check the degenerate cases
1882 if (lhsWords == 0) {
1884 return APInt(BitWidth, 0);
1885 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1886 // X % Y ===> X, iff X < Y
1888 } else if (*this == RHS) {
1890 return APInt(BitWidth, 0);
1891 } else if (lhsWords == 1) {
1892 // All high words are zero, just use native remainder
1893 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1896 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1897 APInt Remainder(1,0);
1898 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
1902 APInt APInt::srem(const APInt &RHS) const {
1904 if (RHS.isNegative())
1905 return -((-(*this)).urem(-RHS));
1906 return -((-(*this)).urem(RHS));
1908 if (RHS.isNegative())
1909 return this->urem(-RHS);
1910 return this->urem(RHS);
1913 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1914 APInt &Quotient, APInt &Remainder) {
1915 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1917 // First, deal with the easy case
1918 if (LHS.isSingleWord()) {
1919 assert(RHS.VAL != 0 && "Divide by zero?");
1920 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1921 uint64_t RemVal = LHS.VAL % RHS.VAL;
1922 Quotient = APInt(LHS.BitWidth, QuotVal);
1923 Remainder = APInt(LHS.BitWidth, RemVal);
1927 // Get some size facts about the dividend and divisor
1928 unsigned lhsBits = LHS.getActiveBits();
1929 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1930 unsigned rhsBits = RHS.getActiveBits();
1931 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1933 // Check the degenerate cases
1934 if (lhsWords == 0) {
1935 Quotient = 0; // 0 / Y ===> 0
1936 Remainder = 0; // 0 % Y ===> 0
1940 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1941 Remainder = LHS; // X % Y ===> X, iff X < Y
1942 Quotient = 0; // X / Y ===> 0, iff X < Y
1947 Quotient = 1; // X / X ===> 1
1948 Remainder = 0; // X % X ===> 0;
1952 if (lhsWords == 1 && rhsWords == 1) {
1953 // There is only one word to consider so use the native versions.
1954 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1955 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1956 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1957 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1961 // Okay, lets do it the long way
1962 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1965 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1966 APInt &Quotient, APInt &Remainder) {
1967 if (LHS.isNegative()) {
1968 if (RHS.isNegative())
1969 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1971 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1972 Quotient = -Quotient;
1974 Remainder = -Remainder;
1975 } else if (RHS.isNegative()) {
1976 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1977 Quotient = -Quotient;
1979 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1983 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1984 APInt Res = *this+RHS;
1985 Overflow = isNonNegative() == RHS.isNonNegative() &&
1986 Res.isNonNegative() != isNonNegative();
1990 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1991 APInt Res = *this+RHS;
1992 Overflow = Res.ult(RHS);
1996 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1997 APInt Res = *this - RHS;
1998 Overflow = isNonNegative() != RHS.isNonNegative() &&
1999 Res.isNonNegative() != isNonNegative();
2003 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2004 APInt Res = *this-RHS;
2005 Overflow = Res.ugt(*this);
2009 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2010 // MININT/-1 --> overflow.
2011 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2015 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2016 APInt Res = *this * RHS;
2018 if (*this != 0 && RHS != 0)
2019 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2025 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2026 APInt Res = *this * RHS;
2028 if (*this != 0 && RHS != 0)
2029 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2035 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
2036 Overflow = ShAmt.uge(getBitWidth());
2038 return APInt(BitWidth, 0);
2040 if (isNonNegative()) // Don't allow sign change.
2041 Overflow = ShAmt.uge(countLeadingZeros());
2043 Overflow = ShAmt.uge(countLeadingOnes());
2045 return *this << ShAmt;
2048 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
2049 Overflow = ShAmt.uge(getBitWidth());
2051 return APInt(BitWidth, 0);
2053 Overflow = ShAmt.ugt(countLeadingZeros());
2055 return *this << ShAmt;
2061 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2062 // Check our assumptions here
2063 assert(!str.empty() && "Invalid string length");
2064 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2066 "Radix should be 2, 8, 10, 16, or 36!");
2068 StringRef::iterator p = str.begin();
2069 size_t slen = str.size();
2070 bool isNeg = *p == '-';
2071 if (*p == '-' || *p == '+') {
2074 assert(slen && "String is only a sign, needs a value.");
2076 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2077 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2078 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2079 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2080 "Insufficient bit width");
2083 if (!isSingleWord())
2084 pVal = getClearedMemory(getNumWords());
2086 // Figure out if we can shift instead of multiply
2087 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2089 // Set up an APInt for the digit to add outside the loop so we don't
2090 // constantly construct/destruct it.
2091 APInt apdigit(getBitWidth(), 0);
2092 APInt apradix(getBitWidth(), radix);
2094 // Enter digit traversal loop
2095 for (StringRef::iterator e = str.end(); p != e; ++p) {
2096 unsigned digit = getDigit(*p, radix);
2097 assert(digit < radix && "Invalid character in digit string");
2099 // Shift or multiply the value by the radix
2107 // Add in the digit we just interpreted
2108 if (apdigit.isSingleWord())
2109 apdigit.VAL = digit;
2111 apdigit.pVal[0] = digit;
2114 // If its negative, put it in two's complement form
2117 this->flipAllBits();
2121 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2122 bool Signed, bool formatAsCLiteral) const {
2123 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2125 "Radix should be 2, 8, 10, 16, or 36!");
2127 const char *Prefix = "";
2128 if (formatAsCLiteral) {
2131 // Binary literals are a non-standard extension added in gcc 4.3:
2132 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2144 llvm_unreachable("Invalid radix!");
2148 // First, check for a zero value and just short circuit the logic below.
2151 Str.push_back(*Prefix);
2158 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2160 if (isSingleWord()) {
2162 char *BufPtr = Buffer+65;
2168 int64_t I = getSExtValue();
2178 Str.push_back(*Prefix);
2183 *--BufPtr = Digits[N % Radix];
2186 Str.append(BufPtr, Buffer+65);
2192 if (Signed && isNegative()) {
2193 // They want to print the signed version and it is a negative value
2194 // Flip the bits and add one to turn it into the equivalent positive
2195 // value and put a '-' in the result.
2202 Str.push_back(*Prefix);
2206 // We insert the digits backward, then reverse them to get the right order.
2207 unsigned StartDig = Str.size();
2209 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2210 // because the number of bits per digit (1, 3 and 4 respectively) divides
2211 // equaly. We just shift until the value is zero.
2212 if (Radix == 2 || Radix == 8 || Radix == 16) {
2213 // Just shift tmp right for each digit width until it becomes zero
2214 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2215 unsigned MaskAmt = Radix - 1;
2218 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2219 Str.push_back(Digits[Digit]);
2220 Tmp = Tmp.lshr(ShiftAmt);
2223 APInt divisor(Radix == 10? 4 : 8, Radix);
2225 APInt APdigit(1, 0);
2226 APInt tmp2(Tmp.getBitWidth(), 0);
2227 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2229 unsigned Digit = (unsigned)APdigit.getZExtValue();
2230 assert(Digit < Radix && "divide failed");
2231 Str.push_back(Digits[Digit]);
2236 // Reverse the digits before returning.
2237 std::reverse(Str.begin()+StartDig, Str.end());
2240 /// Returns the APInt as a std::string. Note that this is an inefficient method.
2241 /// It is better to pass in a SmallVector/SmallString to the methods above.
2242 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2244 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2249 LLVM_DUMP_METHOD void APInt::dump() const {
2250 SmallString<40> S, U;
2251 this->toStringUnsigned(U);
2252 this->toStringSigned(S);
2253 dbgs() << "APInt(" << BitWidth << "b, "
2254 << U << "u " << S << "s)";
2257 void APInt::print(raw_ostream &OS, bool isSigned) const {
2259 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2263 // This implements a variety of operations on a representation of
2264 // arbitrary precision, two's-complement, bignum integer values.
2266 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2267 // and unrestricting assumption.
2268 static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");
2270 /* Some handy functions local to this file. */
2273 /* Returns the integer part with the least significant BITS set.
2274 BITS cannot be zero. */
2275 static inline integerPart
2276 lowBitMask(unsigned int bits)
2278 assert(bits != 0 && bits <= integerPartWidth);
2280 return ~(integerPart) 0 >> (integerPartWidth - bits);
2283 /* Returns the value of the lower half of PART. */
2284 static inline integerPart
2285 lowHalf(integerPart part)
2287 return part & lowBitMask(integerPartWidth / 2);
2290 /* Returns the value of the upper half of PART. */
2291 static inline integerPart
2292 highHalf(integerPart part)
2294 return part >> (integerPartWidth / 2);
2297 /* Returns the bit number of the most significant set bit of a part.
2298 If the input number has no bits set -1U is returned. */
2300 partMSB(integerPart value)
2302 return findLastSet(value, ZB_Max);
2305 /* Returns the bit number of the least significant set bit of a
2306 part. If the input number has no bits set -1U is returned. */
2308 partLSB(integerPart value)
2310 return findFirstSet(value, ZB_Max);
2314 /* Sets the least significant part of a bignum to the input value, and
2315 zeroes out higher parts. */
2317 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2324 for (i = 1; i < parts; i++)
2328 /* Assign one bignum to another. */
2330 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2334 for (i = 0; i < parts; i++)
2338 /* Returns true if a bignum is zero, false otherwise. */
2340 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2344 for (i = 0; i < parts; i++)
2351 /* Extract the given bit of a bignum; returns 0 or 1. */
2353 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2355 return (parts[bit / integerPartWidth] &
2356 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2359 /* Set the given bit of a bignum. */
2361 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2363 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2366 /* Clears the given bit of a bignum. */
2368 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2370 parts[bit / integerPartWidth] &=
2371 ~((integerPart) 1 << (bit % integerPartWidth));
2374 /* Returns the bit number of the least significant set bit of a
2375 number. If the input number has no bits set -1U is returned. */
2377 APInt::tcLSB(const integerPart *parts, unsigned int n)
2379 unsigned int i, lsb;
2381 for (i = 0; i < n; i++) {
2382 if (parts[i] != 0) {
2383 lsb = partLSB(parts[i]);
2385 return lsb + i * integerPartWidth;
2392 /* Returns the bit number of the most significant set bit of a number.
2393 If the input number has no bits set -1U is returned. */
2395 APInt::tcMSB(const integerPart *parts, unsigned int n)
2402 if (parts[n] != 0) {
2403 msb = partMSB(parts[n]);
2405 return msb + n * integerPartWidth;
2412 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2413 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2414 the least significant bit of DST. All high bits above srcBITS in
2415 DST are zero-filled. */
2417 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2418 unsigned int srcBits, unsigned int srcLSB)
2420 unsigned int firstSrcPart, dstParts, shift, n;
2422 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2423 assert(dstParts <= dstCount);
2425 firstSrcPart = srcLSB / integerPartWidth;
2426 tcAssign (dst, src + firstSrcPart, dstParts);
2428 shift = srcLSB % integerPartWidth;
2429 tcShiftRight (dst, dstParts, shift);
2431 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2432 in DST. If this is less that srcBits, append the rest, else
2433 clear the high bits. */
2434 n = dstParts * integerPartWidth - shift;
2436 integerPart mask = lowBitMask (srcBits - n);
2437 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2438 << n % integerPartWidth);
2439 } else if (n > srcBits) {
2440 if (srcBits % integerPartWidth)
2441 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2444 /* Clear high parts. */
2445 while (dstParts < dstCount)
2446 dst[dstParts++] = 0;
2449 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2451 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2452 integerPart c, unsigned int parts)
2458 for (i = 0; i < parts; i++) {
2463 dst[i] += rhs[i] + 1;
2474 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2476 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2477 integerPart c, unsigned int parts)
2483 for (i = 0; i < parts; i++) {
2488 dst[i] -= rhs[i] + 1;
2499 /* Negate a bignum in-place. */
2501 APInt::tcNegate(integerPart *dst, unsigned int parts)
2503 tcComplement(dst, parts);
2504 tcIncrement(dst, parts);
2507 /* DST += SRC * MULTIPLIER + CARRY if add is true
2508 DST = SRC * MULTIPLIER + CARRY if add is false
2510 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2511 they must start at the same point, i.e. DST == SRC.
2513 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2514 returned. Otherwise DST is filled with the least significant
2515 DSTPARTS parts of the result, and if all of the omitted higher
2516 parts were zero return zero, otherwise overflow occurred and
2519 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2520 integerPart multiplier, integerPart carry,
2521 unsigned int srcParts, unsigned int dstParts,
2526 /* Otherwise our writes of DST kill our later reads of SRC. */
2527 assert(dst <= src || dst >= src + srcParts);
2528 assert(dstParts <= srcParts + 1);
2530 /* N loops; minimum of dstParts and srcParts. */
2531 n = dstParts < srcParts ? dstParts: srcParts;
2533 for (i = 0; i < n; i++) {
2534 integerPart low, mid, high, srcPart;
2536 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2538 This cannot overflow, because
2540 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2542 which is less than n^2. */
2546 if (multiplier == 0 || srcPart == 0) {
2550 low = lowHalf(srcPart) * lowHalf(multiplier);
2551 high = highHalf(srcPart) * highHalf(multiplier);
2553 mid = lowHalf(srcPart) * highHalf(multiplier);
2554 high += highHalf(mid);
2555 mid <<= integerPartWidth / 2;
2556 if (low + mid < low)
2560 mid = highHalf(srcPart) * lowHalf(multiplier);
2561 high += highHalf(mid);
2562 mid <<= integerPartWidth / 2;
2563 if (low + mid < low)
2567 /* Now add carry. */
2568 if (low + carry < low)
2574 /* And now DST[i], and store the new low part there. */
2575 if (low + dst[i] < low)
2585 /* Full multiplication, there is no overflow. */
2586 assert(i + 1 == dstParts);
2590 /* We overflowed if there is carry. */
2594 /* We would overflow if any significant unwritten parts would be
2595 non-zero. This is true if any remaining src parts are non-zero
2596 and the multiplier is non-zero. */
2598 for (; i < srcParts; i++)
2602 /* We fitted in the narrow destination. */
2607 /* DST = LHS * RHS, where DST has the same width as the operands and
2608 is filled with the least significant parts of the result. Returns
2609 one if overflow occurred, otherwise zero. DST must be disjoint
2610 from both operands. */
2612 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2613 const integerPart *rhs, unsigned int parts)
2618 assert(dst != lhs && dst != rhs);
2621 tcSet(dst, 0, parts);
2623 for (i = 0; i < parts; i++)
2624 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2630 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2631 operands. No overflow occurs. DST must be disjoint from both
2632 operands. Returns the number of parts required to hold the
2635 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2636 const integerPart *rhs, unsigned int lhsParts,
2637 unsigned int rhsParts)
2639 /* Put the narrower number on the LHS for less loops below. */
2640 if (lhsParts > rhsParts) {
2641 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2645 assert(dst != lhs && dst != rhs);
2647 tcSet(dst, 0, rhsParts);
2649 for (n = 0; n < lhsParts; n++)
2650 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2652 n = lhsParts + rhsParts;
2654 return n - (dst[n - 1] == 0);
2658 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2659 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2660 set REMAINDER to the remainder, return zero. i.e.
2662 OLD_LHS = RHS * LHS + REMAINDER
2664 SCRATCH is a bignum of the same size as the operands and result for
2665 use by the routine; its contents need not be initialized and are
2666 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2669 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2670 integerPart *remainder, integerPart *srhs,
2673 unsigned int n, shiftCount;
2676 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2678 shiftCount = tcMSB(rhs, parts) + 1;
2679 if (shiftCount == 0)
2682 shiftCount = parts * integerPartWidth - shiftCount;
2683 n = shiftCount / integerPartWidth;
2684 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2686 tcAssign(srhs, rhs, parts);
2687 tcShiftLeft(srhs, parts, shiftCount);
2688 tcAssign(remainder, lhs, parts);
2689 tcSet(lhs, 0, parts);
2691 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2696 compare = tcCompare(remainder, srhs, parts);
2698 tcSubtract(remainder, srhs, 0, parts);
2702 if (shiftCount == 0)
2705 tcShiftRight(srhs, parts, 1);
2706 if ((mask >>= 1) == 0) {
2707 mask = (integerPart) 1 << (integerPartWidth - 1);
2715 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2716 There are no restrictions on COUNT. */
2718 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2721 unsigned int jump, shift;
2723 /* Jump is the inter-part jump; shift is is intra-part shift. */
2724 jump = count / integerPartWidth;
2725 shift = count % integerPartWidth;
2727 while (parts > jump) {
2732 /* dst[i] comes from the two parts src[i - jump] and, if we have
2733 an intra-part shift, src[i - jump - 1]. */
2734 part = dst[parts - jump];
2737 if (parts >= jump + 1)
2738 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2749 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2750 zero. There are no restrictions on COUNT. */
2752 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2755 unsigned int i, jump, shift;
2757 /* Jump is the inter-part jump; shift is is intra-part shift. */
2758 jump = count / integerPartWidth;
2759 shift = count % integerPartWidth;
2761 /* Perform the shift. This leaves the most significant COUNT bits
2762 of the result at zero. */
2763 for (i = 0; i < parts; i++) {
2766 if (i + jump >= parts) {
2769 part = dst[i + jump];
2772 if (i + jump + 1 < parts)
2773 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2782 /* Bitwise and of two bignums. */
2784 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2788 for (i = 0; i < parts; i++)
2792 /* Bitwise inclusive or of two bignums. */
2794 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2798 for (i = 0; i < parts; i++)
2802 /* Bitwise exclusive or of two bignums. */
2804 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2808 for (i = 0; i < parts; i++)
2812 /* Complement a bignum in-place. */
2814 APInt::tcComplement(integerPart *dst, unsigned int parts)
2818 for (i = 0; i < parts; i++)
2822 /* Comparison (unsigned) of two bignums. */
2824 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2829 if (lhs[parts] == rhs[parts])
2832 if (lhs[parts] > rhs[parts])
2841 /* Increment a bignum in-place, return the carry flag. */
2843 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2847 for (i = 0; i < parts; i++)
2854 /* Decrement a bignum in-place, return the borrow flag. */
2856 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2857 for (unsigned int i = 0; i < parts; i++) {
2858 // If the current word is non-zero, then the decrement has no effect on the
2859 // higher-order words of the integer and no borrow can occur. Exit early.
2863 // If every word was zero, then there is a borrow.
2868 /* Set the least significant BITS bits of a bignum, clear the
2871 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2877 while (bits > integerPartWidth) {
2878 dst[i++] = ~(integerPart) 0;
2879 bits -= integerPartWidth;
2883 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);