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/StringRef.h"
18 #include "llvm/ADT/FoldingSet.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/raw_ostream.h"
30 /// A utility function for allocating memory, checking for allocation failures,
31 /// and ensuring the contents are zeroed.
32 inline static uint64_t* getClearedMemory(unsigned numWords) {
33 uint64_t * result = new uint64_t[numWords];
34 assert(result && "APInt memory allocation fails!");
35 memset(result, 0, numWords * sizeof(uint64_t));
39 /// A utility function for allocating memory and checking for allocation
40 /// failure. The content is not zeroed.
41 inline static uint64_t* getMemory(unsigned numWords) {
42 uint64_t * result = new uint64_t[numWords];
43 assert(result && "APInt memory allocation fails!");
47 /// A utility function that converts a character to a digit.
48 inline static unsigned getDigit(char cdigit, uint8_t radix) {
73 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
74 pVal = getClearedMemory(getNumWords());
76 if (isSigned && int64_t(val) < 0)
77 for (unsigned i = 1; i < getNumWords(); ++i)
81 void APInt::initSlowCase(const APInt& that) {
82 pVal = getMemory(getNumWords());
83 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
87 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
88 : BitWidth(numBits), VAL(0) {
89 assert(BitWidth && "Bitwidth too small");
90 assert(bigVal && "Null pointer detected!");
94 // Get memory, cleared to 0
95 pVal = getClearedMemory(getNumWords());
96 // Calculate the number of words to copy
97 unsigned words = std::min<unsigned>(numWords, getNumWords());
98 // Copy the words from bigVal to pVal
99 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
101 // Make sure unused high bits are cleared
105 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
106 : BitWidth(numbits), VAL(0) {
107 assert(BitWidth && "Bitwidth too small");
108 fromString(numbits, Str, radix);
111 APInt& APInt::AssignSlowCase(const APInt& RHS) {
112 // Don't do anything for X = X
116 if (BitWidth == RHS.getBitWidth()) {
117 // assume same bit-width single-word case is already handled
118 assert(!isSingleWord());
119 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
123 if (isSingleWord()) {
124 // assume case where both are single words is already handled
125 assert(!RHS.isSingleWord());
127 pVal = getMemory(RHS.getNumWords());
128 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
129 } else if (getNumWords() == RHS.getNumWords())
130 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
131 else if (RHS.isSingleWord()) {
136 pVal = getMemory(RHS.getNumWords());
137 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
139 BitWidth = RHS.BitWidth;
140 return clearUnusedBits();
143 APInt& APInt::operator=(uint64_t RHS) {
148 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
150 return clearUnusedBits();
153 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
154 void APInt::Profile(FoldingSetNodeID& ID) const {
155 ID.AddInteger(BitWidth);
157 if (isSingleWord()) {
162 unsigned NumWords = getNumWords();
163 for (unsigned i = 0; i < NumWords; ++i)
164 ID.AddInteger(pVal[i]);
167 /// add_1 - This function adds a single "digit" integer, y, to the multiple
168 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
169 /// 1 is returned if there is a carry out, otherwise 0 is returned.
170 /// @returns the carry of the addition.
171 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
172 for (unsigned i = 0; i < len; ++i) {
175 y = 1; // Carry one to next digit.
177 y = 0; // No need to carry so exit early
184 /// @brief Prefix increment operator. Increments the APInt by one.
185 APInt& APInt::operator++() {
189 add_1(pVal, pVal, getNumWords(), 1);
190 return clearUnusedBits();
193 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
194 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
195 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
196 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
197 /// In other words, if y > x then this function returns 1, otherwise 0.
198 /// @returns the borrow out of the subtraction
199 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
200 for (unsigned i = 0; i < len; ++i) {
204 y = 1; // We have to "borrow 1" from next "digit"
206 y = 0; // No need to borrow
207 break; // Remaining digits are unchanged so exit early
213 /// @brief Prefix decrement operator. Decrements the APInt by one.
214 APInt& APInt::operator--() {
218 sub_1(pVal, getNumWords(), 1);
219 return clearUnusedBits();
222 /// add - This function adds the integer array x to the integer array Y and
223 /// places the result in dest.
224 /// @returns the carry out from the addition
225 /// @brief General addition of 64-bit integer arrays
226 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
229 for (unsigned i = 0; i< len; ++i) {
230 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
231 dest[i] = x[i] + y[i] + carry;
232 carry = dest[i] < limit || (carry && dest[i] == limit);
237 /// Adds the RHS APint to this APInt.
238 /// @returns this, after addition of RHS.
239 /// @brief Addition assignment operator.
240 APInt& APInt::operator+=(const APInt& RHS) {
241 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
245 add(pVal, pVal, RHS.pVal, getNumWords());
247 return clearUnusedBits();
250 /// Subtracts the integer array y from the integer array x
251 /// @returns returns the borrow out.
252 /// @brief Generalized subtraction of 64-bit integer arrays.
253 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
256 for (unsigned i = 0; i < len; ++i) {
257 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
258 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
259 dest[i] = x_tmp - y[i];
264 /// Subtracts the RHS APInt from this APInt
265 /// @returns this, after subtraction
266 /// @brief Subtraction assignment operator.
267 APInt& APInt::operator-=(const APInt& RHS) {
268 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
272 sub(pVal, pVal, RHS.pVal, getNumWords());
273 return clearUnusedBits();
276 /// Multiplies an integer array, x, by a uint64_t integer and places the result
278 /// @returns the carry out of the multiplication.
279 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
280 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
281 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
282 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
285 // For each digit of x.
286 for (unsigned i = 0; i < len; ++i) {
287 // Split x into high and low words
288 uint64_t lx = x[i] & 0xffffffffULL;
289 uint64_t hx = x[i] >> 32;
290 // hasCarry - A flag to indicate if there is a carry to the next digit.
291 // hasCarry == 0, no carry
292 // hasCarry == 1, has carry
293 // hasCarry == 2, no carry and the calculation result == 0.
294 uint8_t hasCarry = 0;
295 dest[i] = carry + lx * ly;
296 // Determine if the add above introduces carry.
297 hasCarry = (dest[i] < carry) ? 1 : 0;
298 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
299 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
300 // (2^32 - 1) + 2^32 = 2^64.
301 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
303 carry += (lx * hy) & 0xffffffffULL;
304 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
305 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
306 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
311 /// Multiplies integer array x by integer array y and stores the result into
312 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
313 /// @brief Generalized multiplicate of integer arrays.
314 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
316 dest[xlen] = mul_1(dest, x, xlen, y[0]);
317 for (unsigned i = 1; i < ylen; ++i) {
318 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
319 uint64_t carry = 0, lx = 0, hx = 0;
320 for (unsigned j = 0; j < xlen; ++j) {
321 lx = x[j] & 0xffffffffULL;
323 // hasCarry - A flag to indicate if has carry.
324 // hasCarry == 0, no carry
325 // hasCarry == 1, has carry
326 // hasCarry == 2, no carry and the calculation result == 0.
327 uint8_t hasCarry = 0;
328 uint64_t resul = carry + lx * ly;
329 hasCarry = (resul < carry) ? 1 : 0;
330 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
331 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
333 carry += (lx * hy) & 0xffffffffULL;
334 resul = (carry << 32) | (resul & 0xffffffffULL);
336 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
337 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
338 ((lx * hy) >> 32) + hx * hy;
340 dest[i+xlen] = carry;
344 APInt& APInt::operator*=(const APInt& RHS) {
345 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
346 if (isSingleWord()) {
352 // Get some bit facts about LHS and check for zero
353 unsigned lhsBits = getActiveBits();
354 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
359 // Get some bit facts about RHS and check for zero
360 unsigned rhsBits = RHS.getActiveBits();
361 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
368 // Allocate space for the result
369 unsigned destWords = rhsWords + lhsWords;
370 uint64_t *dest = getMemory(destWords);
372 // Perform the long multiply
373 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
375 // Copy result back into *this
377 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
378 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
380 // delete dest array and return
385 APInt& APInt::operator&=(const APInt& RHS) {
386 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
387 if (isSingleWord()) {
391 unsigned numWords = getNumWords();
392 for (unsigned i = 0; i < numWords; ++i)
393 pVal[i] &= RHS.pVal[i];
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()) {
413 this->clearUnusedBits();
416 unsigned numWords = getNumWords();
417 for (unsigned i = 0; i < numWords; ++i)
418 pVal[i] ^= RHS.pVal[i];
419 return clearUnusedBits();
422 APInt APInt::AndSlowCase(const APInt& RHS) const {
423 unsigned numWords = getNumWords();
424 uint64_t* val = getMemory(numWords);
425 for (unsigned i = 0; i < numWords; ++i)
426 val[i] = pVal[i] & RHS.pVal[i];
427 return APInt(val, getBitWidth());
430 APInt APInt::OrSlowCase(const APInt& RHS) const {
431 unsigned numWords = getNumWords();
432 uint64_t *val = getMemory(numWords);
433 for (unsigned i = 0; i < numWords; ++i)
434 val[i] = pVal[i] | RHS.pVal[i];
435 return APInt(val, getBitWidth());
438 APInt APInt::XorSlowCase(const APInt& RHS) const {
439 unsigned numWords = getNumWords();
440 uint64_t *val = getMemory(numWords);
441 for (unsigned i = 0; i < numWords; ++i)
442 val[i] = pVal[i] ^ RHS.pVal[i];
444 // 0^0==1 so clear the high bits in case they got set.
445 return APInt(val, getBitWidth()).clearUnusedBits();
448 bool APInt::operator !() const {
452 for (unsigned i = 0; i < getNumWords(); ++i)
458 APInt APInt::operator*(const APInt& RHS) const {
459 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
461 return APInt(BitWidth, VAL * RHS.VAL);
464 return Result.clearUnusedBits();
467 APInt APInt::operator+(const APInt& RHS) const {
468 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
470 return APInt(BitWidth, VAL + RHS.VAL);
471 APInt Result(BitWidth, 0);
472 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
473 return Result.clearUnusedBits();
476 APInt APInt::operator-(const APInt& RHS) const {
477 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
479 return APInt(BitWidth, VAL - RHS.VAL);
480 APInt Result(BitWidth, 0);
481 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
482 return Result.clearUnusedBits();
485 bool APInt::operator[](unsigned bitPosition) const {
486 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
487 return (maskBit(bitPosition) &
488 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
491 bool APInt::EqualSlowCase(const APInt& RHS) const {
492 // Get some facts about the number of bits used in the two operands.
493 unsigned n1 = getActiveBits();
494 unsigned n2 = RHS.getActiveBits();
496 // If the number of bits isn't the same, they aren't equal
500 // If the number of bits fits in a word, we only need to compare the low word.
501 if (n1 <= APINT_BITS_PER_WORD)
502 return pVal[0] == RHS.pVal[0];
504 // Otherwise, compare everything
505 for (int i = whichWord(n1 - 1); i >= 0; --i)
506 if (pVal[i] != RHS.pVal[i])
511 bool APInt::EqualSlowCase(uint64_t Val) const {
512 unsigned n = getActiveBits();
513 if (n <= APINT_BITS_PER_WORD)
514 return pVal[0] == Val;
519 bool APInt::ult(const APInt& RHS) const {
520 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
522 return VAL < RHS.VAL;
524 // Get active bit length of both operands
525 unsigned n1 = getActiveBits();
526 unsigned n2 = RHS.getActiveBits();
528 // If magnitude of LHS is less than RHS, return true.
532 // If magnitude of RHS is greather than LHS, return false.
536 // If they bot fit in a word, just compare the low order word
537 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
538 return pVal[0] < RHS.pVal[0];
540 // Otherwise, compare all words
541 unsigned topWord = whichWord(std::max(n1,n2)-1);
542 for (int i = topWord; i >= 0; --i) {
543 if (pVal[i] > RHS.pVal[i])
545 if (pVal[i] < RHS.pVal[i])
551 bool APInt::slt(const APInt& RHS) const {
552 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
553 if (isSingleWord()) {
554 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
555 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
556 return lhsSext < rhsSext;
561 bool lhsNeg = isNegative();
562 bool rhsNeg = rhs.isNegative();
564 // Sign bit is set so perform two's complement to make it positive
569 // Sign bit is set so perform two's complement to make it positive
574 // Now we have unsigned values to compare so do the comparison if necessary
575 // based on the negativeness of the values.
587 void APInt::set(unsigned bitPosition) {
589 VAL |= maskBit(bitPosition);
591 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
594 /// Set the given bit to 0 whose position is given as "bitPosition".
595 /// @brief Set a given bit to 0.
596 void APInt::clear(unsigned bitPosition) {
598 VAL &= ~maskBit(bitPosition);
600 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
603 /// @brief Toggle every bit to its opposite value.
605 /// Toggle a given bit to its opposite value whose position is given
606 /// as "bitPosition".
607 /// @brief Toggles a given bit to its opposite value.
608 void APInt::flip(unsigned bitPosition) {
609 assert(bitPosition < BitWidth && "Out of the bit-width range!");
610 if ((*this)[bitPosition]) clear(bitPosition);
611 else set(bitPosition);
614 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
615 assert(!str.empty() && "Invalid string length");
616 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
617 "Radix should be 2, 8, 10, or 16!");
619 size_t slen = str.size();
621 // Each computation below needs to know if it's negative.
622 StringRef::iterator p = str.begin();
623 unsigned isNegative = *p == '-';
624 if (*p == '-' || *p == '+') {
627 assert(slen && "String is only a sign, needs a value.");
630 // For radixes of power-of-two values, the bits required is accurately and
633 return slen + isNegative;
635 return slen * 3 + isNegative;
637 return slen * 4 + isNegative;
639 // This is grossly inefficient but accurate. We could probably do something
640 // with a computation of roughly slen*64/20 and then adjust by the value of
641 // the first few digits. But, I'm not sure how accurate that could be.
643 // Compute a sufficient number of bits that is always large enough but might
644 // be too large. This avoids the assertion in the constructor. This
645 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
646 // bits in that case.
647 unsigned sufficient = slen == 1 ? 4 : slen * 64/18;
649 // Convert to the actual binary value.
650 APInt tmp(sufficient, StringRef(p, slen), radix);
652 // Compute how many bits are required. If the log is infinite, assume we need
654 unsigned log = tmp.logBase2();
655 if (log == (unsigned)-1) {
656 return isNegative + 1;
658 return isNegative + log + 1;
662 // From http://www.burtleburtle.net, byBob Jenkins.
663 // When targeting x86, both GCC and LLVM seem to recognize this as a
664 // rotate instruction.
665 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
667 // From http://www.burtleburtle.net, by Bob Jenkins.
670 a -= c; a ^= rot(c, 4); c += b; \
671 b -= a; b ^= rot(a, 6); a += c; \
672 c -= b; c ^= rot(b, 8); b += a; \
673 a -= c; a ^= rot(c,16); c += b; \
674 b -= a; b ^= rot(a,19); a += c; \
675 c -= b; c ^= rot(b, 4); b += a; \
678 // From http://www.burtleburtle.net, by Bob Jenkins.
679 #define final(a,b,c) \
681 c ^= b; c -= rot(b,14); \
682 a ^= c; a -= rot(c,11); \
683 b ^= a; b -= rot(a,25); \
684 c ^= b; c -= rot(b,16); \
685 a ^= c; a -= rot(c,4); \
686 b ^= a; b -= rot(a,14); \
687 c ^= b; c -= rot(b,24); \
690 // hashword() was adapted from http://www.burtleburtle.net, by Bob
691 // Jenkins. k is a pointer to an array of uint32_t values; length is
692 // the length of the key, in 32-bit chunks. This version only handles
693 // keys that are a multiple of 32 bits in size.
694 static inline uint32_t hashword(const uint64_t *k64, size_t length)
696 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
699 /* Set up the internal state */
700 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
702 /*------------------------------------------------- handle most of the key */
712 /*------------------------------------------- handle the last 3 uint32_t's */
713 switch (length) { /* all the case statements fall through */
718 case 0: /* case 0: nothing left to add */
721 /*------------------------------------------------------ report the result */
725 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
726 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
727 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
728 // function into about 35 instructions when inlined.
729 static inline uint32_t hashword8(const uint64_t k64)
732 a = b = c = 0xdeadbeef + 4;
734 a += k64 & 0xffffffff;
742 uint64_t APInt::getHashValue() const {
745 hash = hashword8(VAL);
747 hash = hashword(pVal, getNumWords()*2);
751 /// HiBits - This function returns the high "numBits" bits of this APInt.
752 APInt APInt::getHiBits(unsigned numBits) const {
753 return APIntOps::lshr(*this, BitWidth - numBits);
756 /// LoBits - This function returns the low "numBits" bits of this APInt.
757 APInt APInt::getLoBits(unsigned numBits) const {
758 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
762 bool APInt::isPowerOf2() const {
763 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
766 unsigned APInt::countLeadingZerosSlowCase() const {
767 // Treat the most significand word differently because it might have
768 // meaningless bits set beyond the precision.
769 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
771 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
773 MSWMask = ~integerPart(0);
774 BitsInMSW = APINT_BITS_PER_WORD;
777 unsigned i = getNumWords();
778 integerPart MSW = pVal[i-1] & MSWMask;
780 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
782 unsigned Count = BitsInMSW;
783 for (--i; i > 0u; --i) {
785 Count += APINT_BITS_PER_WORD;
787 Count += CountLeadingZeros_64(pVal[i-1]);
794 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
798 while (V && (V & (1ULL << 63))) {
805 unsigned APInt::countLeadingOnes() const {
807 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
809 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
812 highWordBits = APINT_BITS_PER_WORD;
815 shift = APINT_BITS_PER_WORD - highWordBits;
817 int i = getNumWords() - 1;
818 unsigned Count = countLeadingOnes_64(pVal[i], shift);
819 if (Count == highWordBits) {
820 for (i--; i >= 0; --i) {
821 if (pVal[i] == -1ULL)
822 Count += APINT_BITS_PER_WORD;
824 Count += countLeadingOnes_64(pVal[i], 0);
832 unsigned APInt::countTrailingZeros() const {
834 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
837 for (; i < getNumWords() && pVal[i] == 0; ++i)
838 Count += APINT_BITS_PER_WORD;
839 if (i < getNumWords())
840 Count += CountTrailingZeros_64(pVal[i]);
841 return std::min(Count, BitWidth);
844 unsigned APInt::countTrailingOnesSlowCase() const {
847 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
848 Count += APINT_BITS_PER_WORD;
849 if (i < getNumWords())
850 Count += CountTrailingOnes_64(pVal[i]);
851 return std::min(Count, BitWidth);
854 unsigned APInt::countPopulationSlowCase() const {
856 for (unsigned i = 0; i < getNumWords(); ++i)
857 Count += CountPopulation_64(pVal[i]);
861 APInt APInt::byteSwap() const {
862 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
864 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
865 else if (BitWidth == 32)
866 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
867 else if (BitWidth == 48) {
868 unsigned Tmp1 = unsigned(VAL >> 16);
869 Tmp1 = ByteSwap_32(Tmp1);
870 uint16_t Tmp2 = uint16_t(VAL);
871 Tmp2 = ByteSwap_16(Tmp2);
872 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
873 } else if (BitWidth == 64)
874 return APInt(BitWidth, ByteSwap_64(VAL));
876 APInt Result(BitWidth, 0);
877 char *pByte = (char*)Result.pVal;
878 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
880 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
881 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
887 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
889 APInt A = API1, B = API2;
892 B = APIntOps::urem(A, B);
898 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
905 // Get the sign bit from the highest order bit
906 bool isNeg = T.I >> 63;
908 // Get the 11-bit exponent and adjust for the 1023 bit bias
909 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
911 // If the exponent is negative, the value is < 0 so just return 0.
913 return APInt(width, 0u);
915 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
916 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
918 // If the exponent doesn't shift all bits out of the mantissa
920 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
921 APInt(width, mantissa >> (52 - exp));
923 // If the client didn't provide enough bits for us to shift the mantissa into
924 // then the result is undefined, just return 0
925 if (width <= exp - 52)
926 return APInt(width, 0);
928 // Otherwise, we have to shift the mantissa bits up to the right location
929 APInt Tmp(width, mantissa);
930 Tmp = Tmp.shl((unsigned)exp - 52);
931 return isNeg ? -Tmp : Tmp;
934 /// RoundToDouble - This function converts this APInt to a double.
935 /// The layout for double is as following (IEEE Standard 754):
936 /// --------------------------------------
937 /// | Sign Exponent Fraction Bias |
938 /// |-------------------------------------- |
939 /// | 1[63] 11[62-52] 52[51-00] 1023 |
940 /// --------------------------------------
941 double APInt::roundToDouble(bool isSigned) const {
943 // Handle the simple case where the value is contained in one uint64_t.
944 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
945 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
947 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
950 return double(getWord(0));
953 // Determine if the value is negative.
954 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
956 // Construct the absolute value if we're negative.
957 APInt Tmp(isNeg ? -(*this) : (*this));
959 // Figure out how many bits we're using.
960 unsigned n = Tmp.getActiveBits();
962 // The exponent (without bias normalization) is just the number of bits
963 // we are using. Note that the sign bit is gone since we constructed the
967 // Return infinity for exponent overflow
969 if (!isSigned || !isNeg)
970 return std::numeric_limits<double>::infinity();
972 return -std::numeric_limits<double>::infinity();
974 exp += 1023; // Increment for 1023 bias
976 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
977 // extract the high 52 bits from the correct words in pVal.
979 unsigned hiWord = whichWord(n-1);
981 mantissa = Tmp.pVal[0];
983 mantissa >>= n - 52; // shift down, we want the top 52 bits.
985 assert(hiWord > 0 && "huh?");
986 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
987 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
988 mantissa = hibits | lobits;
991 // The leading bit of mantissa is implicit, so get rid of it.
992 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
997 T.I = sign | (exp << 52) | mantissa;
1001 // Truncate to new width.
1002 APInt &APInt::trunc(unsigned width) {
1003 assert(width < BitWidth && "Invalid APInt Truncate request");
1004 assert(width && "Can't truncate to 0 bits");
1005 unsigned wordsBefore = getNumWords();
1007 unsigned wordsAfter = getNumWords();
1008 if (wordsBefore != wordsAfter) {
1009 if (wordsAfter == 1) {
1010 uint64_t *tmp = pVal;
1014 uint64_t *newVal = getClearedMemory(wordsAfter);
1015 for (unsigned i = 0; i < wordsAfter; ++i)
1016 newVal[i] = pVal[i];
1021 return clearUnusedBits();
1024 // Sign extend to a new width.
1025 APInt &APInt::sext(unsigned width) {
1026 assert(width > BitWidth && "Invalid APInt SignExtend request");
1027 // If the sign bit isn't set, this is the same as zext.
1028 if (!isNegative()) {
1033 // The sign bit is set. First, get some facts
1034 unsigned wordsBefore = getNumWords();
1035 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
1037 unsigned wordsAfter = getNumWords();
1039 // Mask the high order word appropriately
1040 if (wordsBefore == wordsAfter) {
1041 unsigned newWordBits = width % APINT_BITS_PER_WORD;
1042 // The extension is contained to the wordsBefore-1th word.
1043 uint64_t mask = ~0ULL;
1045 mask >>= APINT_BITS_PER_WORD - newWordBits;
1047 if (wordsBefore == 1)
1050 pVal[wordsBefore-1] |= mask;
1051 return clearUnusedBits();
1054 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1055 uint64_t *newVal = getMemory(wordsAfter);
1056 if (wordsBefore == 1)
1057 newVal[0] = VAL | mask;
1059 for (unsigned i = 0; i < wordsBefore; ++i)
1060 newVal[i] = pVal[i];
1061 newVal[wordsBefore-1] |= mask;
1063 for (unsigned i = wordsBefore; i < wordsAfter; i++)
1065 if (wordsBefore != 1)
1068 return clearUnusedBits();
1071 // Zero extend to a new width.
1072 APInt &APInt::zext(unsigned width) {
1073 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1074 unsigned wordsBefore = getNumWords();
1076 unsigned wordsAfter = getNumWords();
1077 if (wordsBefore != wordsAfter) {
1078 uint64_t *newVal = getClearedMemory(wordsAfter);
1079 if (wordsBefore == 1)
1082 for (unsigned i = 0; i < wordsBefore; ++i)
1083 newVal[i] = pVal[i];
1084 if (wordsBefore != 1)
1091 APInt &APInt::zextOrTrunc(unsigned width) {
1092 if (BitWidth < width)
1094 if (BitWidth > width)
1095 return trunc(width);
1099 APInt &APInt::sextOrTrunc(unsigned width) {
1100 if (BitWidth < width)
1102 if (BitWidth > width)
1103 return trunc(width);
1107 /// Arithmetic right-shift this APInt by shiftAmt.
1108 /// @brief Arithmetic right-shift function.
1109 APInt APInt::ashr(const APInt &shiftAmt) const {
1110 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1113 /// Arithmetic right-shift this APInt by shiftAmt.
1114 /// @brief Arithmetic right-shift function.
1115 APInt APInt::ashr(unsigned shiftAmt) const {
1116 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1117 // Handle a degenerate case
1121 // Handle single word shifts with built-in ashr
1122 if (isSingleWord()) {
1123 if (shiftAmt == BitWidth)
1124 return APInt(BitWidth, 0); // undefined
1126 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1127 return APInt(BitWidth,
1128 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1132 // If all the bits were shifted out, the result is, technically, undefined.
1133 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1134 // issues in the algorithm below.
1135 if (shiftAmt == BitWidth) {
1137 return APInt(BitWidth, -1ULL, true);
1139 return APInt(BitWidth, 0);
1142 // Create some space for the result.
1143 uint64_t * val = new uint64_t[getNumWords()];
1145 // Compute some values needed by the following shift algorithms
1146 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1147 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1148 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1149 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1150 if (bitsInWord == 0)
1151 bitsInWord = APINT_BITS_PER_WORD;
1153 // If we are shifting whole words, just move whole words
1154 if (wordShift == 0) {
1155 // Move the words containing significant bits
1156 for (unsigned i = 0; i <= breakWord; ++i)
1157 val[i] = pVal[i+offset]; // move whole word
1159 // Adjust the top significant word for sign bit fill, if negative
1161 if (bitsInWord < APINT_BITS_PER_WORD)
1162 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1164 // Shift the low order words
1165 for (unsigned i = 0; i < breakWord; ++i) {
1166 // This combines the shifted corresponding word with the low bits from
1167 // the next word (shifted into this word's high bits).
1168 val[i] = (pVal[i+offset] >> wordShift) |
1169 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1172 // Shift the break word. In this case there are no bits from the next word
1173 // to include in this word.
1174 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1176 // Deal with sign extenstion in the break word, and possibly the word before
1179 if (wordShift > bitsInWord) {
1182 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1183 val[breakWord] |= ~0ULL;
1185 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1189 // Remaining words are 0 or -1, just assign them.
1190 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1191 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1193 return APInt(val, BitWidth).clearUnusedBits();
1196 /// Logical right-shift this APInt by shiftAmt.
1197 /// @brief Logical right-shift function.
1198 APInt APInt::lshr(const APInt &shiftAmt) const {
1199 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1202 /// Logical right-shift this APInt by shiftAmt.
1203 /// @brief Logical right-shift function.
1204 APInt APInt::lshr(unsigned shiftAmt) const {
1205 if (isSingleWord()) {
1206 if (shiftAmt == BitWidth)
1207 return APInt(BitWidth, 0);
1209 return APInt(BitWidth, this->VAL >> shiftAmt);
1212 // If all the bits were shifted out, the result is 0. This avoids issues
1213 // with shifting by the size of the integer type, which produces undefined
1214 // results. We define these "undefined results" to always be 0.
1215 if (shiftAmt == BitWidth)
1216 return APInt(BitWidth, 0);
1218 // If none of the bits are shifted out, the result is *this. This avoids
1219 // issues with shifting by the size of the integer type, which produces
1220 // undefined results in the code below. This is also an optimization.
1224 // Create some space for the result.
1225 uint64_t * val = new uint64_t[getNumWords()];
1227 // If we are shifting less than a word, compute the shift with a simple carry
1228 if (shiftAmt < APINT_BITS_PER_WORD) {
1230 for (int i = getNumWords()-1; i >= 0; --i) {
1231 val[i] = (pVal[i] >> shiftAmt) | carry;
1232 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1234 return APInt(val, BitWidth).clearUnusedBits();
1237 // Compute some values needed by the remaining shift algorithms
1238 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1239 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1241 // If we are shifting whole words, just move whole words
1242 if (wordShift == 0) {
1243 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1244 val[i] = pVal[i+offset];
1245 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1247 return APInt(val,BitWidth).clearUnusedBits();
1250 // Shift the low order words
1251 unsigned breakWord = getNumWords() - offset -1;
1252 for (unsigned i = 0; i < breakWord; ++i)
1253 val[i] = (pVal[i+offset] >> wordShift) |
1254 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1255 // Shift the break word.
1256 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1258 // Remaining words are 0
1259 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1261 return APInt(val, BitWidth).clearUnusedBits();
1264 /// Left-shift this APInt by shiftAmt.
1265 /// @brief Left-shift function.
1266 APInt APInt::shl(const APInt &shiftAmt) const {
1267 // It's undefined behavior in C to shift by BitWidth or greater.
1268 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1271 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1272 // If all the bits were shifted out, the result is 0. This avoids issues
1273 // with shifting by the size of the integer type, which produces undefined
1274 // results. We define these "undefined results" to always be 0.
1275 if (shiftAmt == BitWidth)
1276 return APInt(BitWidth, 0);
1278 // If none of the bits are shifted out, the result is *this. This avoids a
1279 // lshr by the words size in the loop below which can produce incorrect
1280 // results. It also avoids the expensive computation below for a common case.
1284 // Create some space for the result.
1285 uint64_t * val = new uint64_t[getNumWords()];
1287 // If we are shifting less than a word, do it the easy way
1288 if (shiftAmt < APINT_BITS_PER_WORD) {
1290 for (unsigned i = 0; i < getNumWords(); i++) {
1291 val[i] = pVal[i] << shiftAmt | carry;
1292 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1294 return APInt(val, BitWidth).clearUnusedBits();
1297 // Compute some values needed by the remaining shift algorithms
1298 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1299 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1301 // If we are shifting whole words, just move whole words
1302 if (wordShift == 0) {
1303 for (unsigned i = 0; i < offset; i++)
1305 for (unsigned i = offset; i < getNumWords(); i++)
1306 val[i] = pVal[i-offset];
1307 return APInt(val,BitWidth).clearUnusedBits();
1310 // Copy whole words from this to Result.
1311 unsigned i = getNumWords() - 1;
1312 for (; i > offset; --i)
1313 val[i] = pVal[i-offset] << wordShift |
1314 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1315 val[offset] = pVal[0] << wordShift;
1316 for (i = 0; i < offset; ++i)
1318 return APInt(val, BitWidth).clearUnusedBits();
1321 APInt APInt::rotl(const APInt &rotateAmt) const {
1322 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1325 APInt APInt::rotl(unsigned rotateAmt) const {
1328 // Don't get too fancy, just use existing shift/or facilities
1332 lo.lshr(BitWidth - rotateAmt);
1336 APInt APInt::rotr(const APInt &rotateAmt) const {
1337 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1340 APInt APInt::rotr(unsigned rotateAmt) const {
1343 // Don't get too fancy, just use existing shift/or facilities
1347 hi.shl(BitWidth - rotateAmt);
1351 // Square Root - this method computes and returns the square root of "this".
1352 // Three mechanisms are used for computation. For small values (<= 5 bits),
1353 // a table lookup is done. This gets some performance for common cases. For
1354 // values using less than 52 bits, the value is converted to double and then
1355 // the libc sqrt function is called. The result is rounded and then converted
1356 // back to a uint64_t which is then used to construct the result. Finally,
1357 // the Babylonian method for computing square roots is used.
1358 APInt APInt::sqrt() const {
1360 // Determine the magnitude of the value.
1361 unsigned magnitude = getActiveBits();
1363 // Use a fast table for some small values. This also gets rid of some
1364 // rounding errors in libc sqrt for small values.
1365 if (magnitude <= 5) {
1366 static const uint8_t results[32] = {
1369 /* 3- 6 */ 2, 2, 2, 2,
1370 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1371 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1372 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1375 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1378 // If the magnitude of the value fits in less than 52 bits (the precision of
1379 // an IEEE double precision floating point value), then we can use the
1380 // libc sqrt function which will probably use a hardware sqrt computation.
1381 // This should be faster than the algorithm below.
1382 if (magnitude < 52) {
1384 return APInt(BitWidth,
1385 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1387 return APInt(BitWidth,
1388 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1392 // Okay, all the short cuts are exhausted. We must compute it. The following
1393 // is a classical Babylonian method for computing the square root. This code
1394 // was adapted to APINt from a wikipedia article on such computations.
1395 // See http://www.wikipedia.org/ and go to the page named
1396 // Calculate_an_integer_square_root.
1397 unsigned nbits = BitWidth, i = 4;
1398 APInt testy(BitWidth, 16);
1399 APInt x_old(BitWidth, 1);
1400 APInt x_new(BitWidth, 0);
1401 APInt two(BitWidth, 2);
1403 // Select a good starting value using binary logarithms.
1404 for (;; i += 2, testy = testy.shl(2))
1405 if (i >= nbits || this->ule(testy)) {
1406 x_old = x_old.shl(i / 2);
1410 // Use the Babylonian method to arrive at the integer square root:
1412 x_new = (this->udiv(x_old) + x_old).udiv(two);
1413 if (x_old.ule(x_new))
1418 // Make sure we return the closest approximation
1419 // NOTE: The rounding calculation below is correct. It will produce an
1420 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1421 // determined to be a rounding issue with pari/gp as it begins to use a
1422 // floating point representation after 192 bits. There are no discrepancies
1423 // between this algorithm and pari/gp for bit widths < 192 bits.
1424 APInt square(x_old * x_old);
1425 APInt nextSquare((x_old + 1) * (x_old +1));
1426 if (this->ult(square))
1428 else if (this->ule(nextSquare)) {
1429 APInt midpoint((nextSquare - square).udiv(two));
1430 APInt offset(*this - square);
1431 if (offset.ult(midpoint))
1436 llvm_unreachable("Error in APInt::sqrt computation");
1440 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1441 /// iterative extended Euclidean algorithm is used to solve for this value,
1442 /// however we simplify it to speed up calculating only the inverse, and take
1443 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1444 /// (potentially large) APInts around.
1445 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1446 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1448 // Using the properties listed at the following web page (accessed 06/21/08):
1449 // http://www.numbertheory.org/php/euclid.html
1450 // (especially the properties numbered 3, 4 and 9) it can be proved that
1451 // BitWidth bits suffice for all the computations in the algorithm implemented
1452 // below. More precisely, this number of bits suffice if the multiplicative
1453 // inverse exists, but may not suffice for the general extended Euclidean
1456 APInt r[2] = { modulo, *this };
1457 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1458 APInt q(BitWidth, 0);
1461 for (i = 0; r[i^1] != 0; i ^= 1) {
1462 // An overview of the math without the confusing bit-flipping:
1463 // q = r[i-2] / r[i-1]
1464 // r[i] = r[i-2] % r[i-1]
1465 // t[i] = t[i-2] - t[i-1] * q
1466 udivrem(r[i], r[i^1], q, r[i]);
1470 // If this APInt and the modulo are not coprime, there is no multiplicative
1471 // inverse, so return 0. We check this by looking at the next-to-last
1472 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1475 return APInt(BitWidth, 0);
1477 // The next-to-last t is the multiplicative inverse. However, we are
1478 // interested in a positive inverse. Calcuate a positive one from a negative
1479 // one if necessary. A simple addition of the modulo suffices because
1480 // abs(t[i]) is known to be less than *this/2 (see the link above).
1481 return t[i].isNegative() ? t[i] + modulo : t[i];
1484 /// Calculate the magic numbers required to implement a signed integer division
1485 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1486 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1487 /// Warren, Jr., chapter 10.
1488 APInt::ms APInt::magic() const {
1489 const APInt& d = *this;
1491 APInt ad, anc, delta, q1, r1, q2, r2, t;
1492 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1496 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1497 anc = t - 1 - t.urem(ad); // absolute value of nc
1498 p = d.getBitWidth() - 1; // initialize p
1499 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1500 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1501 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1502 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1505 q1 = q1<<1; // update q1 = 2p/abs(nc)
1506 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1507 if (r1.uge(anc)) { // must be unsigned comparison
1511 q2 = q2<<1; // update q2 = 2p/abs(d)
1512 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1513 if (r2.uge(ad)) { // must be unsigned comparison
1518 } while (q1.ule(delta) || (q1 == delta && r1 == 0));
1521 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1522 mag.s = p - d.getBitWidth(); // resulting shift
1526 /// Calculate the magic numbers required to implement an unsigned integer
1527 /// division by a constant as a sequence of multiplies, adds and shifts.
1528 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1529 /// S. Warren, Jr., chapter 10.
1530 APInt::mu APInt::magicu() const {
1531 const APInt& d = *this;
1533 APInt nc, delta, q1, r1, q2, r2;
1535 magu.a = 0; // initialize "add" indicator
1536 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1537 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1538 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1540 nc = allOnes - (-d).urem(d);
1541 p = d.getBitWidth() - 1; // initialize p
1542 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1543 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1544 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1545 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1548 if (r1.uge(nc - r1)) {
1549 q1 = q1 + q1 + 1; // update q1
1550 r1 = r1 + r1 - nc; // update r1
1553 q1 = q1+q1; // update q1
1554 r1 = r1+r1; // update r1
1556 if ((r2 + 1).uge(d - r2)) {
1557 if (q2.uge(signedMax)) magu.a = 1;
1558 q2 = q2+q2 + 1; // update q2
1559 r2 = r2+r2 + 1 - d; // update r2
1562 if (q2.uge(signedMin)) magu.a = 1;
1563 q2 = q2+q2; // update q2
1564 r2 = r2+r2 + 1; // update r2
1567 } while (p < d.getBitWidth()*2 &&
1568 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1569 magu.m = q2 + 1; // resulting magic number
1570 magu.s = p - d.getBitWidth(); // resulting shift
1574 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1575 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1576 /// variables here have the same names as in the algorithm. Comments explain
1577 /// the algorithm and any deviation from it.
1578 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1579 unsigned m, unsigned n) {
1580 assert(u && "Must provide dividend");
1581 assert(v && "Must provide divisor");
1582 assert(q && "Must provide quotient");
1583 assert(u != v && u != q && v != q && "Must us different memory");
1584 assert(n>1 && "n must be > 1");
1586 // Knuth uses the value b as the base of the number system. In our case b
1587 // is 2^31 so we just set it to -1u.
1588 uint64_t b = uint64_t(1) << 32;
1591 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1592 DEBUG(dbgs() << "KnuthDiv: original:");
1593 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1594 DEBUG(dbgs() << " by");
1595 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1596 DEBUG(dbgs() << '\n');
1598 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1599 // u and v by d. Note that we have taken Knuth's advice here to use a power
1600 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1601 // 2 allows us to shift instead of multiply and it is easy to determine the
1602 // shift amount from the leading zeros. We are basically normalizing the u
1603 // and v so that its high bits are shifted to the top of v's range without
1604 // overflow. Note that this can require an extra word in u so that u must
1605 // be of length m+n+1.
1606 unsigned shift = CountLeadingZeros_32(v[n-1]);
1607 unsigned v_carry = 0;
1608 unsigned u_carry = 0;
1610 for (unsigned i = 0; i < m+n; ++i) {
1611 unsigned u_tmp = u[i] >> (32 - shift);
1612 u[i] = (u[i] << shift) | u_carry;
1615 for (unsigned i = 0; i < n; ++i) {
1616 unsigned v_tmp = v[i] >> (32 - shift);
1617 v[i] = (v[i] << shift) | v_carry;
1623 DEBUG(dbgs() << "KnuthDiv: normal:");
1624 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1625 DEBUG(dbgs() << " by");
1626 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1627 DEBUG(dbgs() << '\n');
1630 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1633 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1634 // D3. [Calculate q'.].
1635 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1636 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1637 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1638 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1639 // on v[n-2] determines at high speed most of the cases in which the trial
1640 // value qp is one too large, and it eliminates all cases where qp is two
1642 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1643 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1644 uint64_t qp = dividend / v[n-1];
1645 uint64_t rp = dividend % v[n-1];
1646 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1649 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1652 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1654 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1655 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1656 // consists of a simple multiplication by a one-place number, combined with
1659 for (unsigned i = 0; i < n; ++i) {
1660 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1661 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1662 bool borrow = subtrahend > u_tmp;
1663 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1664 << ", subtrahend == " << subtrahend
1665 << ", borrow = " << borrow << '\n');
1667 uint64_t result = u_tmp - subtrahend;
1669 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1670 u[k++] = (unsigned)(result >> 32); // subtract high word
1671 while (borrow && k <= m+n) { // deal with borrow to the left
1677 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1680 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1681 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1682 DEBUG(dbgs() << '\n');
1683 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1684 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1685 // true value plus b**(n+1), namely as the b's complement of
1686 // the true value, and a "borrow" to the left should be remembered.
1689 bool carry = true; // true because b's complement is "complement + 1"
1690 for (unsigned i = 0; i <= m+n; ++i) {
1691 u[i] = ~u[i] + carry; // b's complement
1692 carry = carry && u[i] == 0;
1695 DEBUG(dbgs() << "KnuthDiv: after complement:");
1696 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1697 DEBUG(dbgs() << '\n');
1699 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1700 // negative, go to step D6; otherwise go on to step D7.
1701 q[j] = (unsigned)qp;
1703 // D6. [Add back]. The probability that this step is necessary is very
1704 // small, on the order of only 2/b. Make sure that test data accounts for
1705 // this possibility. Decrease q[j] by 1
1707 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1708 // A carry will occur to the left of u[j+n], and it should be ignored
1709 // since it cancels with the borrow that occurred in D4.
1711 for (unsigned i = 0; i < n; i++) {
1712 unsigned limit = std::min(u[j+i],v[i]);
1713 u[j+i] += v[i] + carry;
1714 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1718 DEBUG(dbgs() << "KnuthDiv: after correction:");
1719 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1720 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1722 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1725 DEBUG(dbgs() << "KnuthDiv: quotient:");
1726 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1727 DEBUG(dbgs() << '\n');
1729 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1730 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1731 // compute the remainder (urem uses this).
1733 // The value d is expressed by the "shift" value above since we avoided
1734 // multiplication by d by using a shift left. So, all we have to do is
1735 // shift right here. In order to mak
1738 DEBUG(dbgs() << "KnuthDiv: remainder:");
1739 for (int i = n-1; i >= 0; i--) {
1740 r[i] = (u[i] >> shift) | carry;
1741 carry = u[i] << (32 - shift);
1742 DEBUG(dbgs() << " " << r[i]);
1745 for (int i = n-1; i >= 0; i--) {
1747 DEBUG(dbgs() << " " << r[i]);
1750 DEBUG(dbgs() << '\n');
1753 DEBUG(dbgs() << '\n');
1757 void APInt::divide(const APInt LHS, unsigned lhsWords,
1758 const APInt &RHS, unsigned rhsWords,
1759 APInt *Quotient, APInt *Remainder)
1761 assert(lhsWords >= rhsWords && "Fractional result");
1763 // First, compose the values into an array of 32-bit words instead of
1764 // 64-bit words. This is a necessity of both the "short division" algorithm
1765 // and the Knuth "classical algorithm" which requires there to be native
1766 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1767 // can't use 64-bit operands here because we don't have native results of
1768 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1769 // work on large-endian machines.
1770 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1771 unsigned n = rhsWords * 2;
1772 unsigned m = (lhsWords * 2) - n;
1774 // Allocate space for the temporary values we need either on the stack, if
1775 // it will fit, or on the heap if it won't.
1776 unsigned SPACE[128];
1781 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1784 Q = &SPACE[(m+n+1) + n];
1786 R = &SPACE[(m+n+1) + n + (m+n)];
1788 U = new unsigned[m + n + 1];
1789 V = new unsigned[n];
1790 Q = new unsigned[m+n];
1792 R = new unsigned[n];
1795 // Initialize the dividend
1796 memset(U, 0, (m+n+1)*sizeof(unsigned));
1797 for (unsigned i = 0; i < lhsWords; ++i) {
1798 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1799 U[i * 2] = (unsigned)(tmp & mask);
1800 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1802 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1804 // Initialize the divisor
1805 memset(V, 0, (n)*sizeof(unsigned));
1806 for (unsigned i = 0; i < rhsWords; ++i) {
1807 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1808 V[i * 2] = (unsigned)(tmp & mask);
1809 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1812 // initialize the quotient and remainder
1813 memset(Q, 0, (m+n) * sizeof(unsigned));
1815 memset(R, 0, n * sizeof(unsigned));
1817 // Now, adjust m and n for the Knuth division. n is the number of words in
1818 // the divisor. m is the number of words by which the dividend exceeds the
1819 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1820 // contain any zero words or the Knuth algorithm fails.
1821 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1825 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1828 // If we're left with only a single word for the divisor, Knuth doesn't work
1829 // so we implement the short division algorithm here. This is much simpler
1830 // and faster because we are certain that we can divide a 64-bit quantity
1831 // by a 32-bit quantity at hardware speed and short division is simply a
1832 // series of such operations. This is just like doing short division but we
1833 // are using base 2^32 instead of base 10.
1834 assert(n != 0 && "Divide by zero?");
1836 unsigned divisor = V[0];
1837 unsigned remainder = 0;
1838 for (int i = m+n-1; i >= 0; i--) {
1839 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1840 if (partial_dividend == 0) {
1843 } else if (partial_dividend < divisor) {
1845 remainder = (unsigned)partial_dividend;
1846 } else if (partial_dividend == divisor) {
1850 Q[i] = (unsigned)(partial_dividend / divisor);
1851 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1857 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1859 KnuthDiv(U, V, Q, R, m, n);
1862 // If the caller wants the quotient
1864 // Set up the Quotient value's memory.
1865 if (Quotient->BitWidth != LHS.BitWidth) {
1866 if (Quotient->isSingleWord())
1869 delete [] Quotient->pVal;
1870 Quotient->BitWidth = LHS.BitWidth;
1871 if (!Quotient->isSingleWord())
1872 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1876 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1878 if (lhsWords == 1) {
1880 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1881 if (Quotient->isSingleWord())
1882 Quotient->VAL = tmp;
1884 Quotient->pVal[0] = tmp;
1886 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1887 for (unsigned i = 0; i < lhsWords; ++i)
1889 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1893 // If the caller wants the remainder
1895 // Set up the Remainder value's memory.
1896 if (Remainder->BitWidth != RHS.BitWidth) {
1897 if (Remainder->isSingleWord())
1900 delete [] Remainder->pVal;
1901 Remainder->BitWidth = RHS.BitWidth;
1902 if (!Remainder->isSingleWord())
1903 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1907 // The remainder is in R. Reconstitute the remainder into Remainder's low
1909 if (rhsWords == 1) {
1911 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1912 if (Remainder->isSingleWord())
1913 Remainder->VAL = tmp;
1915 Remainder->pVal[0] = tmp;
1917 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1918 for (unsigned i = 0; i < rhsWords; ++i)
1919 Remainder->pVal[i] =
1920 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1924 // Clean up the memory we allocated.
1925 if (U != &SPACE[0]) {
1933 APInt APInt::udiv(const APInt& RHS) const {
1934 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1936 // First, deal with the easy case
1937 if (isSingleWord()) {
1938 assert(RHS.VAL != 0 && "Divide by zero?");
1939 return APInt(BitWidth, VAL / RHS.VAL);
1942 // Get some facts about the LHS and RHS number of bits and words
1943 unsigned rhsBits = RHS.getActiveBits();
1944 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1945 assert(rhsWords && "Divided by zero???");
1946 unsigned lhsBits = this->getActiveBits();
1947 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1949 // Deal with some degenerate cases
1952 return APInt(BitWidth, 0);
1953 else if (lhsWords < rhsWords || this->ult(RHS)) {
1954 // X / Y ===> 0, iff X < Y
1955 return APInt(BitWidth, 0);
1956 } else if (*this == RHS) {
1958 return APInt(BitWidth, 1);
1959 } else if (lhsWords == 1 && rhsWords == 1) {
1960 // All high words are zero, just use native divide
1961 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1964 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1965 APInt Quotient(1,0); // to hold result.
1966 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1970 APInt APInt::urem(const APInt& RHS) const {
1971 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1972 if (isSingleWord()) {
1973 assert(RHS.VAL != 0 && "Remainder by zero?");
1974 return APInt(BitWidth, VAL % RHS.VAL);
1977 // Get some facts about the LHS
1978 unsigned lhsBits = getActiveBits();
1979 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1981 // Get some facts about the RHS
1982 unsigned rhsBits = RHS.getActiveBits();
1983 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1984 assert(rhsWords && "Performing remainder operation by zero ???");
1986 // Check the degenerate cases
1987 if (lhsWords == 0) {
1989 return APInt(BitWidth, 0);
1990 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1991 // X % Y ===> X, iff X < Y
1993 } else if (*this == RHS) {
1995 return APInt(BitWidth, 0);
1996 } else if (lhsWords == 1) {
1997 // All high words are zero, just use native remainder
1998 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
2001 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2002 APInt Remainder(1,0);
2003 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2007 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2008 APInt &Quotient, APInt &Remainder) {
2009 // Get some size facts about the dividend and divisor
2010 unsigned lhsBits = LHS.getActiveBits();
2011 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2012 unsigned rhsBits = RHS.getActiveBits();
2013 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2015 // Check the degenerate cases
2016 if (lhsWords == 0) {
2017 Quotient = 0; // 0 / Y ===> 0
2018 Remainder = 0; // 0 % Y ===> 0
2022 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2023 Remainder = LHS; // X % Y ===> X, iff X < Y
2024 Quotient = 0; // X / Y ===> 0, iff X < Y
2029 Quotient = 1; // X / X ===> 1
2030 Remainder = 0; // X % X ===> 0;
2034 if (lhsWords == 1 && rhsWords == 1) {
2035 // There is only one word to consider so use the native versions.
2036 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2037 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2038 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2039 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2043 // Okay, lets do it the long way
2044 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2047 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2048 APInt Res = *this+RHS;
2049 Overflow = isNonNegative() == RHS.isNonNegative() &&
2050 Res.isNonNegative() != isNonNegative();
2054 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2055 APInt Res = *this+RHS;
2056 Overflow = Res.ult(RHS);
2060 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2061 APInt Res = *this - RHS;
2062 Overflow = isNonNegative() != RHS.isNonNegative() &&
2063 Res.isNonNegative() != isNonNegative();
2067 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2068 APInt Res = *this-RHS;
2069 Overflow = Res.ugt(*this);
2073 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2074 // MININT/-1 --> overflow.
2075 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2079 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2080 APInt Res = *this * RHS;
2082 if (*this != 0 && RHS != 0)
2083 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2089 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2090 Overflow = ShAmt >= getBitWidth();
2092 ShAmt = getBitWidth()-1;
2094 if (isNonNegative()) // Don't allow sign change.
2095 Overflow = ShAmt >= countLeadingZeros();
2097 Overflow = ShAmt >= countLeadingOnes();
2099 return *this << ShAmt;
2105 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2106 // Check our assumptions here
2107 assert(!str.empty() && "Invalid string length");
2108 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2109 "Radix should be 2, 8, 10, or 16!");
2111 StringRef::iterator p = str.begin();
2112 size_t slen = str.size();
2113 bool isNeg = *p == '-';
2114 if (*p == '-' || *p == '+') {
2117 assert(slen && "String is only a sign, needs a value.");
2119 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2120 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2121 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2122 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2123 "Insufficient bit width");
2126 if (!isSingleWord())
2127 pVal = getClearedMemory(getNumWords());
2129 // Figure out if we can shift instead of multiply
2130 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2132 // Set up an APInt for the digit to add outside the loop so we don't
2133 // constantly construct/destruct it.
2134 APInt apdigit(getBitWidth(), 0);
2135 APInt apradix(getBitWidth(), radix);
2137 // Enter digit traversal loop
2138 for (StringRef::iterator e = str.end(); p != e; ++p) {
2139 unsigned digit = getDigit(*p, radix);
2140 assert(digit < radix && "Invalid character in digit string");
2142 // Shift or multiply the value by the radix
2150 // Add in the digit we just interpreted
2151 if (apdigit.isSingleWord())
2152 apdigit.VAL = digit;
2154 apdigit.pVal[0] = digit;
2157 // If its negative, put it in two's complement form
2164 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2165 bool Signed) const {
2166 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2167 "Radix should be 2, 8, 10, or 16!");
2169 // First, check for a zero value and just short circuit the logic below.
2175 static const char Digits[] = "0123456789ABCDEF";
2177 if (isSingleWord()) {
2179 char *BufPtr = Buffer+65;
2185 int64_t I = getSExtValue();
2195 *--BufPtr = Digits[N % Radix];
2198 Str.append(BufPtr, Buffer+65);
2204 if (Signed && isNegative()) {
2205 // They want to print the signed version and it is a negative value
2206 // Flip the bits and add one to turn it into the equivalent positive
2207 // value and put a '-' in the result.
2213 // We insert the digits backward, then reverse them to get the right order.
2214 unsigned StartDig = Str.size();
2216 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2217 // because the number of bits per digit (1, 3 and 4 respectively) divides
2218 // equaly. We just shift until the value is zero.
2220 // Just shift tmp right for each digit width until it becomes zero
2221 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2222 unsigned MaskAmt = Radix - 1;
2225 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2226 Str.push_back(Digits[Digit]);
2227 Tmp = Tmp.lshr(ShiftAmt);
2230 APInt divisor(4, 10);
2232 APInt APdigit(1, 0);
2233 APInt tmp2(Tmp.getBitWidth(), 0);
2234 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2236 unsigned Digit = (unsigned)APdigit.getZExtValue();
2237 assert(Digit < Radix && "divide failed");
2238 Str.push_back(Digits[Digit]);
2243 // Reverse the digits before returning.
2244 std::reverse(Str.begin()+StartDig, Str.end());
2247 /// toString - This returns the APInt as a std::string. Note that this is an
2248 /// inefficient method. It is better to pass in a SmallVector/SmallString
2249 /// to the methods above.
2250 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2252 toString(S, Radix, Signed);
2257 void APInt::dump() const {
2258 SmallString<40> S, U;
2259 this->toStringUnsigned(U);
2260 this->toStringSigned(S);
2261 dbgs() << "APInt(" << BitWidth << "b, "
2262 << U.str() << "u " << S.str() << "s)";
2265 void APInt::print(raw_ostream &OS, bool isSigned) const {
2267 this->toString(S, 10, isSigned);
2271 // This implements a variety of operations on a representation of
2272 // arbitrary precision, two's-complement, bignum integer values.
2274 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2275 // and unrestricting assumption.
2276 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2277 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2279 /* Some handy functions local to this file. */
2282 /* Returns the integer part with the least significant BITS set.
2283 BITS cannot be zero. */
2284 static inline integerPart
2285 lowBitMask(unsigned int bits)
2287 assert(bits != 0 && bits <= integerPartWidth);
2289 return ~(integerPart) 0 >> (integerPartWidth - bits);
2292 /* Returns the value of the lower half of PART. */
2293 static inline integerPart
2294 lowHalf(integerPart part)
2296 return part & lowBitMask(integerPartWidth / 2);
2299 /* Returns the value of the upper half of PART. */
2300 static inline integerPart
2301 highHalf(integerPart part)
2303 return part >> (integerPartWidth / 2);
2306 /* Returns the bit number of the most significant set bit of a part.
2307 If the input number has no bits set -1U is returned. */
2309 partMSB(integerPart value)
2311 unsigned int n, msb;
2316 n = integerPartWidth / 2;
2331 /* Returns the bit number of the least significant set bit of a
2332 part. If the input number has no bits set -1U is returned. */
2334 partLSB(integerPart value)
2336 unsigned int n, lsb;
2341 lsb = integerPartWidth - 1;
2342 n = integerPartWidth / 2;
2357 /* Sets the least significant part of a bignum to the input value, and
2358 zeroes out higher parts. */
2360 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2367 for (i = 1; i < parts; i++)
2371 /* Assign one bignum to another. */
2373 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2377 for (i = 0; i < parts; i++)
2381 /* Returns true if a bignum is zero, false otherwise. */
2383 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2387 for (i = 0; i < parts; i++)
2394 /* Extract the given bit of a bignum; returns 0 or 1. */
2396 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2398 return (parts[bit / integerPartWidth] &
2399 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2402 /* Set the given bit of a bignum. */
2404 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2406 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2409 /* Clears the given bit of a bignum. */
2411 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2413 parts[bit / integerPartWidth] &=
2414 ~((integerPart) 1 << (bit % integerPartWidth));
2417 /* Returns the bit number of the least significant set bit of a
2418 number. If the input number has no bits set -1U is returned. */
2420 APInt::tcLSB(const integerPart *parts, unsigned int n)
2422 unsigned int i, lsb;
2424 for (i = 0; i < n; i++) {
2425 if (parts[i] != 0) {
2426 lsb = partLSB(parts[i]);
2428 return lsb + i * integerPartWidth;
2435 /* Returns the bit number of the most significant set bit of a number.
2436 If the input number has no bits set -1U is returned. */
2438 APInt::tcMSB(const integerPart *parts, unsigned int n)
2445 if (parts[n] != 0) {
2446 msb = partMSB(parts[n]);
2448 return msb + n * integerPartWidth;
2455 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2456 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2457 the least significant bit of DST. All high bits above srcBITS in
2458 DST are zero-filled. */
2460 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2461 unsigned int srcBits, unsigned int srcLSB)
2463 unsigned int firstSrcPart, dstParts, shift, n;
2465 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2466 assert(dstParts <= dstCount);
2468 firstSrcPart = srcLSB / integerPartWidth;
2469 tcAssign (dst, src + firstSrcPart, dstParts);
2471 shift = srcLSB % integerPartWidth;
2472 tcShiftRight (dst, dstParts, shift);
2474 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2475 in DST. If this is less that srcBits, append the rest, else
2476 clear the high bits. */
2477 n = dstParts * integerPartWidth - shift;
2479 integerPart mask = lowBitMask (srcBits - n);
2480 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2481 << n % integerPartWidth);
2482 } else if (n > srcBits) {
2483 if (srcBits % integerPartWidth)
2484 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2487 /* Clear high parts. */
2488 while (dstParts < dstCount)
2489 dst[dstParts++] = 0;
2492 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2494 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2495 integerPart c, unsigned int parts)
2501 for (i = 0; i < parts; i++) {
2506 dst[i] += rhs[i] + 1;
2517 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2519 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2520 integerPart c, unsigned int parts)
2526 for (i = 0; i < parts; i++) {
2531 dst[i] -= rhs[i] + 1;
2542 /* Negate a bignum in-place. */
2544 APInt::tcNegate(integerPart *dst, unsigned int parts)
2546 tcComplement(dst, parts);
2547 tcIncrement(dst, parts);
2550 /* DST += SRC * MULTIPLIER + CARRY if add is true
2551 DST = SRC * MULTIPLIER + CARRY if add is false
2553 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2554 they must start at the same point, i.e. DST == SRC.
2556 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2557 returned. Otherwise DST is filled with the least significant
2558 DSTPARTS parts of the result, and if all of the omitted higher
2559 parts were zero return zero, otherwise overflow occurred and
2562 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2563 integerPart multiplier, integerPart carry,
2564 unsigned int srcParts, unsigned int dstParts,
2569 /* Otherwise our writes of DST kill our later reads of SRC. */
2570 assert(dst <= src || dst >= src + srcParts);
2571 assert(dstParts <= srcParts + 1);
2573 /* N loops; minimum of dstParts and srcParts. */
2574 n = dstParts < srcParts ? dstParts: srcParts;
2576 for (i = 0; i < n; i++) {
2577 integerPart low, mid, high, srcPart;
2579 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2581 This cannot overflow, because
2583 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2585 which is less than n^2. */
2589 if (multiplier == 0 || srcPart == 0) {
2593 low = lowHalf(srcPart) * lowHalf(multiplier);
2594 high = highHalf(srcPart) * highHalf(multiplier);
2596 mid = lowHalf(srcPart) * highHalf(multiplier);
2597 high += highHalf(mid);
2598 mid <<= integerPartWidth / 2;
2599 if (low + mid < low)
2603 mid = highHalf(srcPart) * lowHalf(multiplier);
2604 high += highHalf(mid);
2605 mid <<= integerPartWidth / 2;
2606 if (low + mid < low)
2610 /* Now add carry. */
2611 if (low + carry < low)
2617 /* And now DST[i], and store the new low part there. */
2618 if (low + dst[i] < low)
2628 /* Full multiplication, there is no overflow. */
2629 assert(i + 1 == dstParts);
2633 /* We overflowed if there is carry. */
2637 /* We would overflow if any significant unwritten parts would be
2638 non-zero. This is true if any remaining src parts are non-zero
2639 and the multiplier is non-zero. */
2641 for (; i < srcParts; i++)
2645 /* We fitted in the narrow destination. */
2650 /* DST = LHS * RHS, where DST has the same width as the operands and
2651 is filled with the least significant parts of the result. Returns
2652 one if overflow occurred, otherwise zero. DST must be disjoint
2653 from both operands. */
2655 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2656 const integerPart *rhs, unsigned int parts)
2661 assert(dst != lhs && dst != rhs);
2664 tcSet(dst, 0, parts);
2666 for (i = 0; i < parts; i++)
2667 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2673 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2674 operands. No overflow occurs. DST must be disjoint from both
2675 operands. Returns the number of parts required to hold the
2678 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2679 const integerPart *rhs, unsigned int lhsParts,
2680 unsigned int rhsParts)
2682 /* Put the narrower number on the LHS for less loops below. */
2683 if (lhsParts > rhsParts) {
2684 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2688 assert(dst != lhs && dst != rhs);
2690 tcSet(dst, 0, rhsParts);
2692 for (n = 0; n < lhsParts; n++)
2693 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2695 n = lhsParts + rhsParts;
2697 return n - (dst[n - 1] == 0);
2701 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2702 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2703 set REMAINDER to the remainder, return zero. i.e.
2705 OLD_LHS = RHS * LHS + REMAINDER
2707 SCRATCH is a bignum of the same size as the operands and result for
2708 use by the routine; its contents need not be initialized and are
2709 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2712 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2713 integerPart *remainder, integerPart *srhs,
2716 unsigned int n, shiftCount;
2719 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2721 shiftCount = tcMSB(rhs, parts) + 1;
2722 if (shiftCount == 0)
2725 shiftCount = parts * integerPartWidth - shiftCount;
2726 n = shiftCount / integerPartWidth;
2727 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2729 tcAssign(srhs, rhs, parts);
2730 tcShiftLeft(srhs, parts, shiftCount);
2731 tcAssign(remainder, lhs, parts);
2732 tcSet(lhs, 0, parts);
2734 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2739 compare = tcCompare(remainder, srhs, parts);
2741 tcSubtract(remainder, srhs, 0, parts);
2745 if (shiftCount == 0)
2748 tcShiftRight(srhs, parts, 1);
2749 if ((mask >>= 1) == 0)
2750 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2756 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2757 There are no restrictions on COUNT. */
2759 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2762 unsigned int jump, shift;
2764 /* Jump is the inter-part jump; shift is is intra-part shift. */
2765 jump = count / integerPartWidth;
2766 shift = count % integerPartWidth;
2768 while (parts > jump) {
2773 /* dst[i] comes from the two parts src[i - jump] and, if we have
2774 an intra-part shift, src[i - jump - 1]. */
2775 part = dst[parts - jump];
2778 if (parts >= jump + 1)
2779 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2790 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2791 zero. There are no restrictions on COUNT. */
2793 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2796 unsigned int i, jump, shift;
2798 /* Jump is the inter-part jump; shift is is intra-part shift. */
2799 jump = count / integerPartWidth;
2800 shift = count % integerPartWidth;
2802 /* Perform the shift. This leaves the most significant COUNT bits
2803 of the result at zero. */
2804 for (i = 0; i < parts; i++) {
2807 if (i + jump >= parts) {
2810 part = dst[i + jump];
2813 if (i + jump + 1 < parts)
2814 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2823 /* Bitwise and of two bignums. */
2825 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2829 for (i = 0; i < parts; i++)
2833 /* Bitwise inclusive or of two bignums. */
2835 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2839 for (i = 0; i < parts; i++)
2843 /* Bitwise exclusive or of two bignums. */
2845 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2849 for (i = 0; i < parts; i++)
2853 /* Complement a bignum in-place. */
2855 APInt::tcComplement(integerPart *dst, unsigned int parts)
2859 for (i = 0; i < parts; i++)
2863 /* Comparison (unsigned) of two bignums. */
2865 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2870 if (lhs[parts] == rhs[parts])
2873 if (lhs[parts] > rhs[parts])
2882 /* Increment a bignum in-place, return the carry flag. */
2884 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2888 for (i = 0; i < parts; i++)
2895 /* Set the least significant BITS bits of a bignum, clear the
2898 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2904 while (bits > integerPartWidth) {
2905 dst[i++] = ~(integerPart) 0;
2906 bits -= integerPartWidth;
2910 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);