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 APInt& APInt::set(unsigned bitPosition) {
589 VAL |= maskBit(bitPosition);
591 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
595 /// Set the given bit to 0 whose position is given as "bitPosition".
596 /// @brief Set a given bit to 0.
597 APInt& APInt::clear(unsigned bitPosition) {
599 VAL &= ~maskBit(bitPosition);
601 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
605 /// @brief Toggle every bit to its opposite value.
607 /// Toggle a given bit to its opposite value whose position is given
608 /// as "bitPosition".
609 /// @brief Toggles a given bit to its opposite value.
610 APInt& APInt::flip(unsigned bitPosition) {
611 assert(bitPosition < BitWidth && "Out of the bit-width range!");
612 if ((*this)[bitPosition]) clear(bitPosition);
613 else set(bitPosition);
617 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
618 assert(!str.empty() && "Invalid string length");
619 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
620 "Radix should be 2, 8, 10, or 16!");
622 size_t slen = str.size();
624 // Each computation below needs to know if it's negative.
625 StringRef::iterator p = str.begin();
626 unsigned isNegative = *p == '-';
627 if (*p == '-' || *p == '+') {
630 assert(slen && "String is only a sign, needs a value.");
633 // For radixes of power-of-two values, the bits required is accurately and
636 return slen + isNegative;
638 return slen * 3 + isNegative;
640 return slen * 4 + isNegative;
642 // This is grossly inefficient but accurate. We could probably do something
643 // with a computation of roughly slen*64/20 and then adjust by the value of
644 // the first few digits. But, I'm not sure how accurate that could be.
646 // Compute a sufficient number of bits that is always large enough but might
647 // be too large. This avoids the assertion in the constructor. This
648 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
649 // bits in that case.
650 unsigned sufficient = slen == 1 ? 4 : slen * 64/18;
652 // Convert to the actual binary value.
653 APInt tmp(sufficient, StringRef(p, slen), radix);
655 // Compute how many bits are required. If the log is infinite, assume we need
657 unsigned log = tmp.logBase2();
658 if (log == (unsigned)-1) {
659 return isNegative + 1;
661 return isNegative + log + 1;
665 // From http://www.burtleburtle.net, byBob Jenkins.
666 // When targeting x86, both GCC and LLVM seem to recognize this as a
667 // rotate instruction.
668 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
670 // From http://www.burtleburtle.net, by Bob Jenkins.
673 a -= c; a ^= rot(c, 4); c += b; \
674 b -= a; b ^= rot(a, 6); a += c; \
675 c -= b; c ^= rot(b, 8); b += a; \
676 a -= c; a ^= rot(c,16); c += b; \
677 b -= a; b ^= rot(a,19); a += c; \
678 c -= b; c ^= rot(b, 4); b += a; \
681 // From http://www.burtleburtle.net, by Bob Jenkins.
682 #define final(a,b,c) \
684 c ^= b; c -= rot(b,14); \
685 a ^= c; a -= rot(c,11); \
686 b ^= a; b -= rot(a,25); \
687 c ^= b; c -= rot(b,16); \
688 a ^= c; a -= rot(c,4); \
689 b ^= a; b -= rot(a,14); \
690 c ^= b; c -= rot(b,24); \
693 // hashword() was adapted from http://www.burtleburtle.net, by Bob
694 // Jenkins. k is a pointer to an array of uint32_t values; length is
695 // the length of the key, in 32-bit chunks. This version only handles
696 // keys that are a multiple of 32 bits in size.
697 static inline uint32_t hashword(const uint64_t *k64, size_t length)
699 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
702 /* Set up the internal state */
703 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
705 /*------------------------------------------------- handle most of the key */
715 /*------------------------------------------- handle the last 3 uint32_t's */
716 switch (length) { /* all the case statements fall through */
721 case 0: /* case 0: nothing left to add */
724 /*------------------------------------------------------ report the result */
728 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
729 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
730 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
731 // function into about 35 instructions when inlined.
732 static inline uint32_t hashword8(const uint64_t k64)
735 a = b = c = 0xdeadbeef + 4;
737 a += k64 & 0xffffffff;
745 uint64_t APInt::getHashValue() const {
748 hash = hashword8(VAL);
750 hash = hashword(pVal, getNumWords()*2);
754 /// HiBits - This function returns the high "numBits" bits of this APInt.
755 APInt APInt::getHiBits(unsigned numBits) const {
756 return APIntOps::lshr(*this, BitWidth - numBits);
759 /// LoBits - This function returns the low "numBits" bits of this APInt.
760 APInt APInt::getLoBits(unsigned numBits) const {
761 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
765 bool APInt::isPowerOf2() const {
766 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
769 unsigned APInt::countLeadingZerosSlowCase() const {
770 // Treat the most significand word differently because it might have
771 // meaningless bits set beyond the precision.
772 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
774 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
776 MSWMask = ~integerPart(0);
777 BitsInMSW = APINT_BITS_PER_WORD;
780 unsigned i = getNumWords();
781 integerPart MSW = pVal[i-1] & MSWMask;
783 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
785 unsigned Count = BitsInMSW;
786 for (--i; i > 0u; --i) {
788 Count += APINT_BITS_PER_WORD;
790 Count += CountLeadingZeros_64(pVal[i-1]);
797 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
801 while (V && (V & (1ULL << 63))) {
808 unsigned APInt::countLeadingOnes() const {
810 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
812 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
815 highWordBits = APINT_BITS_PER_WORD;
818 shift = APINT_BITS_PER_WORD - highWordBits;
820 int i = getNumWords() - 1;
821 unsigned Count = countLeadingOnes_64(pVal[i], shift);
822 if (Count == highWordBits) {
823 for (i--; i >= 0; --i) {
824 if (pVal[i] == -1ULL)
825 Count += APINT_BITS_PER_WORD;
827 Count += countLeadingOnes_64(pVal[i], 0);
835 unsigned APInt::countTrailingZeros() const {
837 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
840 for (; i < getNumWords() && pVal[i] == 0; ++i)
841 Count += APINT_BITS_PER_WORD;
842 if (i < getNumWords())
843 Count += CountTrailingZeros_64(pVal[i]);
844 return std::min(Count, BitWidth);
847 unsigned APInt::countTrailingOnesSlowCase() const {
850 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
851 Count += APINT_BITS_PER_WORD;
852 if (i < getNumWords())
853 Count += CountTrailingOnes_64(pVal[i]);
854 return std::min(Count, BitWidth);
857 unsigned APInt::countPopulationSlowCase() const {
859 for (unsigned i = 0; i < getNumWords(); ++i)
860 Count += CountPopulation_64(pVal[i]);
864 APInt APInt::byteSwap() const {
865 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
867 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
868 else if (BitWidth == 32)
869 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
870 else if (BitWidth == 48) {
871 unsigned Tmp1 = unsigned(VAL >> 16);
872 Tmp1 = ByteSwap_32(Tmp1);
873 uint16_t Tmp2 = uint16_t(VAL);
874 Tmp2 = ByteSwap_16(Tmp2);
875 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
876 } else if (BitWidth == 64)
877 return APInt(BitWidth, ByteSwap_64(VAL));
879 APInt Result(BitWidth, 0);
880 char *pByte = (char*)Result.pVal;
881 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
883 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
884 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
890 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
892 APInt A = API1, B = API2;
895 B = APIntOps::urem(A, B);
901 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
908 // Get the sign bit from the highest order bit
909 bool isNeg = T.I >> 63;
911 // Get the 11-bit exponent and adjust for the 1023 bit bias
912 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
914 // If the exponent is negative, the value is < 0 so just return 0.
916 return APInt(width, 0u);
918 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
919 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
921 // If the exponent doesn't shift all bits out of the mantissa
923 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
924 APInt(width, mantissa >> (52 - exp));
926 // If the client didn't provide enough bits for us to shift the mantissa into
927 // then the result is undefined, just return 0
928 if (width <= exp - 52)
929 return APInt(width, 0);
931 // Otherwise, we have to shift the mantissa bits up to the right location
932 APInt Tmp(width, mantissa);
933 Tmp = Tmp.shl((unsigned)exp - 52);
934 return isNeg ? -Tmp : Tmp;
937 /// RoundToDouble - This function converts this APInt to a double.
938 /// The layout for double is as following (IEEE Standard 754):
939 /// --------------------------------------
940 /// | Sign Exponent Fraction Bias |
941 /// |-------------------------------------- |
942 /// | 1[63] 11[62-52] 52[51-00] 1023 |
943 /// --------------------------------------
944 double APInt::roundToDouble(bool isSigned) const {
946 // Handle the simple case where the value is contained in one uint64_t.
947 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
948 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
950 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
953 return double(getWord(0));
956 // Determine if the value is negative.
957 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
959 // Construct the absolute value if we're negative.
960 APInt Tmp(isNeg ? -(*this) : (*this));
962 // Figure out how many bits we're using.
963 unsigned n = Tmp.getActiveBits();
965 // The exponent (without bias normalization) is just the number of bits
966 // we are using. Note that the sign bit is gone since we constructed the
970 // Return infinity for exponent overflow
972 if (!isSigned || !isNeg)
973 return std::numeric_limits<double>::infinity();
975 return -std::numeric_limits<double>::infinity();
977 exp += 1023; // Increment for 1023 bias
979 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
980 // extract the high 52 bits from the correct words in pVal.
982 unsigned hiWord = whichWord(n-1);
984 mantissa = Tmp.pVal[0];
986 mantissa >>= n - 52; // shift down, we want the top 52 bits.
988 assert(hiWord > 0 && "huh?");
989 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
990 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
991 mantissa = hibits | lobits;
994 // The leading bit of mantissa is implicit, so get rid of it.
995 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
1000 T.I = sign | (exp << 52) | mantissa;
1004 // Truncate to new width.
1005 APInt &APInt::trunc(unsigned width) {
1006 assert(width < BitWidth && "Invalid APInt Truncate request");
1007 assert(width && "Can't truncate to 0 bits");
1008 unsigned wordsBefore = getNumWords();
1010 unsigned wordsAfter = getNumWords();
1011 if (wordsBefore != wordsAfter) {
1012 if (wordsAfter == 1) {
1013 uint64_t *tmp = pVal;
1017 uint64_t *newVal = getClearedMemory(wordsAfter);
1018 for (unsigned i = 0; i < wordsAfter; ++i)
1019 newVal[i] = pVal[i];
1024 return clearUnusedBits();
1027 // Sign extend to a new width.
1028 APInt &APInt::sext(unsigned width) {
1029 assert(width > BitWidth && "Invalid APInt SignExtend request");
1030 // If the sign bit isn't set, this is the same as zext.
1031 if (!isNegative()) {
1036 // The sign bit is set. First, get some facts
1037 unsigned wordsBefore = getNumWords();
1038 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
1040 unsigned wordsAfter = getNumWords();
1042 // Mask the high order word appropriately
1043 if (wordsBefore == wordsAfter) {
1044 unsigned newWordBits = width % APINT_BITS_PER_WORD;
1045 // The extension is contained to the wordsBefore-1th word.
1046 uint64_t mask = ~0ULL;
1048 mask >>= APINT_BITS_PER_WORD - newWordBits;
1050 if (wordsBefore == 1)
1053 pVal[wordsBefore-1] |= mask;
1054 return clearUnusedBits();
1057 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1058 uint64_t *newVal = getMemory(wordsAfter);
1059 if (wordsBefore == 1)
1060 newVal[0] = VAL | mask;
1062 for (unsigned i = 0; i < wordsBefore; ++i)
1063 newVal[i] = pVal[i];
1064 newVal[wordsBefore-1] |= mask;
1066 for (unsigned i = wordsBefore; i < wordsAfter; i++)
1068 if (wordsBefore != 1)
1071 return clearUnusedBits();
1074 // Zero extend to a new width.
1075 APInt &APInt::zext(unsigned width) {
1076 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1077 unsigned wordsBefore = getNumWords();
1079 unsigned wordsAfter = getNumWords();
1080 if (wordsBefore != wordsAfter) {
1081 uint64_t *newVal = getClearedMemory(wordsAfter);
1082 if (wordsBefore == 1)
1085 for (unsigned i = 0; i < wordsBefore; ++i)
1086 newVal[i] = pVal[i];
1087 if (wordsBefore != 1)
1094 APInt &APInt::zextOrTrunc(unsigned width) {
1095 if (BitWidth < width)
1097 if (BitWidth > width)
1098 return trunc(width);
1102 APInt &APInt::sextOrTrunc(unsigned width) {
1103 if (BitWidth < width)
1105 if (BitWidth > width)
1106 return trunc(width);
1110 /// Arithmetic right-shift this APInt by shiftAmt.
1111 /// @brief Arithmetic right-shift function.
1112 APInt APInt::ashr(const APInt &shiftAmt) const {
1113 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1116 /// Arithmetic right-shift this APInt by shiftAmt.
1117 /// @brief Arithmetic right-shift function.
1118 APInt APInt::ashr(unsigned shiftAmt) const {
1119 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1120 // Handle a degenerate case
1124 // Handle single word shifts with built-in ashr
1125 if (isSingleWord()) {
1126 if (shiftAmt == BitWidth)
1127 return APInt(BitWidth, 0); // undefined
1129 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1130 return APInt(BitWidth,
1131 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1135 // If all the bits were shifted out, the result is, technically, undefined.
1136 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1137 // issues in the algorithm below.
1138 if (shiftAmt == BitWidth) {
1140 return APInt(BitWidth, -1ULL, true);
1142 return APInt(BitWidth, 0);
1145 // Create some space for the result.
1146 uint64_t * val = new uint64_t[getNumWords()];
1148 // Compute some values needed by the following shift algorithms
1149 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1150 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1151 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1152 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1153 if (bitsInWord == 0)
1154 bitsInWord = APINT_BITS_PER_WORD;
1156 // If we are shifting whole words, just move whole words
1157 if (wordShift == 0) {
1158 // Move the words containing significant bits
1159 for (unsigned i = 0; i <= breakWord; ++i)
1160 val[i] = pVal[i+offset]; // move whole word
1162 // Adjust the top significant word for sign bit fill, if negative
1164 if (bitsInWord < APINT_BITS_PER_WORD)
1165 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1167 // Shift the low order words
1168 for (unsigned i = 0; i < breakWord; ++i) {
1169 // This combines the shifted corresponding word with the low bits from
1170 // the next word (shifted into this word's high bits).
1171 val[i] = (pVal[i+offset] >> wordShift) |
1172 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1175 // Shift the break word. In this case there are no bits from the next word
1176 // to include in this word.
1177 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1179 // Deal with sign extenstion in the break word, and possibly the word before
1182 if (wordShift > bitsInWord) {
1185 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1186 val[breakWord] |= ~0ULL;
1188 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1192 // Remaining words are 0 or -1, just assign them.
1193 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1194 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1196 return APInt(val, BitWidth).clearUnusedBits();
1199 /// Logical right-shift this APInt by shiftAmt.
1200 /// @brief Logical right-shift function.
1201 APInt APInt::lshr(const APInt &shiftAmt) const {
1202 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1205 /// Logical right-shift this APInt by shiftAmt.
1206 /// @brief Logical right-shift function.
1207 APInt APInt::lshr(unsigned shiftAmt) const {
1208 if (isSingleWord()) {
1209 if (shiftAmt == BitWidth)
1210 return APInt(BitWidth, 0);
1212 return APInt(BitWidth, this->VAL >> shiftAmt);
1215 // If all the bits were shifted out, the result is 0. This avoids issues
1216 // with shifting by the size of the integer type, which produces undefined
1217 // results. We define these "undefined results" to always be 0.
1218 if (shiftAmt == BitWidth)
1219 return APInt(BitWidth, 0);
1221 // If none of the bits are shifted out, the result is *this. This avoids
1222 // issues with shifting by the size of the integer type, which produces
1223 // undefined results in the code below. This is also an optimization.
1227 // Create some space for the result.
1228 uint64_t * val = new uint64_t[getNumWords()];
1230 // If we are shifting less than a word, compute the shift with a simple carry
1231 if (shiftAmt < APINT_BITS_PER_WORD) {
1233 for (int i = getNumWords()-1; i >= 0; --i) {
1234 val[i] = (pVal[i] >> shiftAmt) | carry;
1235 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1237 return APInt(val, BitWidth).clearUnusedBits();
1240 // Compute some values needed by the remaining shift algorithms
1241 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1242 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1244 // If we are shifting whole words, just move whole words
1245 if (wordShift == 0) {
1246 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1247 val[i] = pVal[i+offset];
1248 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1250 return APInt(val,BitWidth).clearUnusedBits();
1253 // Shift the low order words
1254 unsigned breakWord = getNumWords() - offset -1;
1255 for (unsigned i = 0; i < breakWord; ++i)
1256 val[i] = (pVal[i+offset] >> wordShift) |
1257 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1258 // Shift the break word.
1259 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1261 // Remaining words are 0
1262 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1264 return APInt(val, BitWidth).clearUnusedBits();
1267 /// Left-shift this APInt by shiftAmt.
1268 /// @brief Left-shift function.
1269 APInt APInt::shl(const APInt &shiftAmt) const {
1270 // It's undefined behavior in C to shift by BitWidth or greater.
1271 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1274 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1275 // If all the bits were shifted out, the result is 0. This avoids issues
1276 // with shifting by the size of the integer type, which produces undefined
1277 // results. We define these "undefined results" to always be 0.
1278 if (shiftAmt == BitWidth)
1279 return APInt(BitWidth, 0);
1281 // If none of the bits are shifted out, the result is *this. This avoids a
1282 // lshr by the words size in the loop below which can produce incorrect
1283 // results. It also avoids the expensive computation below for a common case.
1287 // Create some space for the result.
1288 uint64_t * val = new uint64_t[getNumWords()];
1290 // If we are shifting less than a word, do it the easy way
1291 if (shiftAmt < APINT_BITS_PER_WORD) {
1293 for (unsigned i = 0; i < getNumWords(); i++) {
1294 val[i] = pVal[i] << shiftAmt | carry;
1295 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1297 return APInt(val, BitWidth).clearUnusedBits();
1300 // Compute some values needed by the remaining shift algorithms
1301 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1302 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1304 // If we are shifting whole words, just move whole words
1305 if (wordShift == 0) {
1306 for (unsigned i = 0; i < offset; i++)
1308 for (unsigned i = offset; i < getNumWords(); i++)
1309 val[i] = pVal[i-offset];
1310 return APInt(val,BitWidth).clearUnusedBits();
1313 // Copy whole words from this to Result.
1314 unsigned i = getNumWords() - 1;
1315 for (; i > offset; --i)
1316 val[i] = pVal[i-offset] << wordShift |
1317 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1318 val[offset] = pVal[0] << wordShift;
1319 for (i = 0; i < offset; ++i)
1321 return APInt(val, BitWidth).clearUnusedBits();
1324 APInt APInt::rotl(const APInt &rotateAmt) const {
1325 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1328 APInt APInt::rotl(unsigned rotateAmt) const {
1331 // Don't get too fancy, just use existing shift/or facilities
1335 lo.lshr(BitWidth - rotateAmt);
1339 APInt APInt::rotr(const APInt &rotateAmt) const {
1340 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1343 APInt APInt::rotr(unsigned rotateAmt) const {
1346 // Don't get too fancy, just use existing shift/or facilities
1350 hi.shl(BitWidth - rotateAmt);
1354 // Square Root - this method computes and returns the square root of "this".
1355 // Three mechanisms are used for computation. For small values (<= 5 bits),
1356 // a table lookup is done. This gets some performance for common cases. For
1357 // values using less than 52 bits, the value is converted to double and then
1358 // the libc sqrt function is called. The result is rounded and then converted
1359 // back to a uint64_t which is then used to construct the result. Finally,
1360 // the Babylonian method for computing square roots is used.
1361 APInt APInt::sqrt() const {
1363 // Determine the magnitude of the value.
1364 unsigned magnitude = getActiveBits();
1366 // Use a fast table for some small values. This also gets rid of some
1367 // rounding errors in libc sqrt for small values.
1368 if (magnitude <= 5) {
1369 static const uint8_t results[32] = {
1372 /* 3- 6 */ 2, 2, 2, 2,
1373 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1374 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1375 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1378 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1381 // If the magnitude of the value fits in less than 52 bits (the precision of
1382 // an IEEE double precision floating point value), then we can use the
1383 // libc sqrt function which will probably use a hardware sqrt computation.
1384 // This should be faster than the algorithm below.
1385 if (magnitude < 52) {
1387 return APInt(BitWidth,
1388 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1390 return APInt(BitWidth,
1391 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1395 // Okay, all the short cuts are exhausted. We must compute it. The following
1396 // is a classical Babylonian method for computing the square root. This code
1397 // was adapted to APINt from a wikipedia article on such computations.
1398 // See http://www.wikipedia.org/ and go to the page named
1399 // Calculate_an_integer_square_root.
1400 unsigned nbits = BitWidth, i = 4;
1401 APInt testy(BitWidth, 16);
1402 APInt x_old(BitWidth, 1);
1403 APInt x_new(BitWidth, 0);
1404 APInt two(BitWidth, 2);
1406 // Select a good starting value using binary logarithms.
1407 for (;; i += 2, testy = testy.shl(2))
1408 if (i >= nbits || this->ule(testy)) {
1409 x_old = x_old.shl(i / 2);
1413 // Use the Babylonian method to arrive at the integer square root:
1415 x_new = (this->udiv(x_old) + x_old).udiv(two);
1416 if (x_old.ule(x_new))
1421 // Make sure we return the closest approximation
1422 // NOTE: The rounding calculation below is correct. It will produce an
1423 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1424 // determined to be a rounding issue with pari/gp as it begins to use a
1425 // floating point representation after 192 bits. There are no discrepancies
1426 // between this algorithm and pari/gp for bit widths < 192 bits.
1427 APInt square(x_old * x_old);
1428 APInt nextSquare((x_old + 1) * (x_old +1));
1429 if (this->ult(square))
1431 else if (this->ule(nextSquare)) {
1432 APInt midpoint((nextSquare - square).udiv(two));
1433 APInt offset(*this - square);
1434 if (offset.ult(midpoint))
1439 llvm_unreachable("Error in APInt::sqrt computation");
1443 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1444 /// iterative extended Euclidean algorithm is used to solve for this value,
1445 /// however we simplify it to speed up calculating only the inverse, and take
1446 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1447 /// (potentially large) APInts around.
1448 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1449 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1451 // Using the properties listed at the following web page (accessed 06/21/08):
1452 // http://www.numbertheory.org/php/euclid.html
1453 // (especially the properties numbered 3, 4 and 9) it can be proved that
1454 // BitWidth bits suffice for all the computations in the algorithm implemented
1455 // below. More precisely, this number of bits suffice if the multiplicative
1456 // inverse exists, but may not suffice for the general extended Euclidean
1459 APInt r[2] = { modulo, *this };
1460 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1461 APInt q(BitWidth, 0);
1464 for (i = 0; r[i^1] != 0; i ^= 1) {
1465 // An overview of the math without the confusing bit-flipping:
1466 // q = r[i-2] / r[i-1]
1467 // r[i] = r[i-2] % r[i-1]
1468 // t[i] = t[i-2] - t[i-1] * q
1469 udivrem(r[i], r[i^1], q, r[i]);
1473 // If this APInt and the modulo are not coprime, there is no multiplicative
1474 // inverse, so return 0. We check this by looking at the next-to-last
1475 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1478 return APInt(BitWidth, 0);
1480 // The next-to-last t is the multiplicative inverse. However, we are
1481 // interested in a positive inverse. Calcuate a positive one from a negative
1482 // one if necessary. A simple addition of the modulo suffices because
1483 // abs(t[i]) is known to be less than *this/2 (see the link above).
1484 return t[i].isNegative() ? t[i] + modulo : t[i];
1487 /// Calculate the magic numbers required to implement a signed integer division
1488 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1489 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1490 /// Warren, Jr., chapter 10.
1491 APInt::ms APInt::magic() const {
1492 const APInt& d = *this;
1494 APInt ad, anc, delta, q1, r1, q2, r2, t;
1495 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1499 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1500 anc = t - 1 - t.urem(ad); // absolute value of nc
1501 p = d.getBitWidth() - 1; // initialize p
1502 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1503 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1504 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1505 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1508 q1 = q1<<1; // update q1 = 2p/abs(nc)
1509 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1510 if (r1.uge(anc)) { // must be unsigned comparison
1514 q2 = q2<<1; // update q2 = 2p/abs(d)
1515 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1516 if (r2.uge(ad)) { // must be unsigned comparison
1521 } while (q1.ule(delta) || (q1 == delta && r1 == 0));
1524 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1525 mag.s = p - d.getBitWidth(); // resulting shift
1529 /// Calculate the magic numbers required to implement an unsigned integer
1530 /// division by a constant as a sequence of multiplies, adds and shifts.
1531 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1532 /// S. Warren, Jr., chapter 10.
1533 APInt::mu APInt::magicu() const {
1534 const APInt& d = *this;
1536 APInt nc, delta, q1, r1, q2, r2;
1538 magu.a = 0; // initialize "add" indicator
1539 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1540 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1541 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1543 nc = allOnes - (-d).urem(d);
1544 p = d.getBitWidth() - 1; // initialize p
1545 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1546 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1547 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1548 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1551 if (r1.uge(nc - r1)) {
1552 q1 = q1 + q1 + 1; // update q1
1553 r1 = r1 + r1 - nc; // update r1
1556 q1 = q1+q1; // update q1
1557 r1 = r1+r1; // update r1
1559 if ((r2 + 1).uge(d - r2)) {
1560 if (q2.uge(signedMax)) magu.a = 1;
1561 q2 = q2+q2 + 1; // update q2
1562 r2 = r2+r2 + 1 - d; // update r2
1565 if (q2.uge(signedMin)) magu.a = 1;
1566 q2 = q2+q2; // update q2
1567 r2 = r2+r2 + 1; // update r2
1570 } while (p < d.getBitWidth()*2 &&
1571 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1572 magu.m = q2 + 1; // resulting magic number
1573 magu.s = p - d.getBitWidth(); // resulting shift
1577 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1578 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1579 /// variables here have the same names as in the algorithm. Comments explain
1580 /// the algorithm and any deviation from it.
1581 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1582 unsigned m, unsigned n) {
1583 assert(u && "Must provide dividend");
1584 assert(v && "Must provide divisor");
1585 assert(q && "Must provide quotient");
1586 assert(u != v && u != q && v != q && "Must us different memory");
1587 assert(n>1 && "n must be > 1");
1589 // Knuth uses the value b as the base of the number system. In our case b
1590 // is 2^31 so we just set it to -1u.
1591 uint64_t b = uint64_t(1) << 32;
1594 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1595 DEBUG(dbgs() << "KnuthDiv: original:");
1596 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1597 DEBUG(dbgs() << " by");
1598 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1599 DEBUG(dbgs() << '\n');
1601 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1602 // u and v by d. Note that we have taken Knuth's advice here to use a power
1603 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1604 // 2 allows us to shift instead of multiply and it is easy to determine the
1605 // shift amount from the leading zeros. We are basically normalizing the u
1606 // and v so that its high bits are shifted to the top of v's range without
1607 // overflow. Note that this can require an extra word in u so that u must
1608 // be of length m+n+1.
1609 unsigned shift = CountLeadingZeros_32(v[n-1]);
1610 unsigned v_carry = 0;
1611 unsigned u_carry = 0;
1613 for (unsigned i = 0; i < m+n; ++i) {
1614 unsigned u_tmp = u[i] >> (32 - shift);
1615 u[i] = (u[i] << shift) | u_carry;
1618 for (unsigned i = 0; i < n; ++i) {
1619 unsigned v_tmp = v[i] >> (32 - shift);
1620 v[i] = (v[i] << shift) | v_carry;
1626 DEBUG(dbgs() << "KnuthDiv: normal:");
1627 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1628 DEBUG(dbgs() << " by");
1629 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1630 DEBUG(dbgs() << '\n');
1633 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1636 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1637 // D3. [Calculate q'.].
1638 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1639 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1640 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1641 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1642 // on v[n-2] determines at high speed most of the cases in which the trial
1643 // value qp is one too large, and it eliminates all cases where qp is two
1645 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1646 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1647 uint64_t qp = dividend / v[n-1];
1648 uint64_t rp = dividend % v[n-1];
1649 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1652 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1655 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1657 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1658 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1659 // consists of a simple multiplication by a one-place number, combined with
1662 for (unsigned i = 0; i < n; ++i) {
1663 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1664 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1665 bool borrow = subtrahend > u_tmp;
1666 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1667 << ", subtrahend == " << subtrahend
1668 << ", borrow = " << borrow << '\n');
1670 uint64_t result = u_tmp - subtrahend;
1672 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1673 u[k++] = (unsigned)(result >> 32); // subtract high word
1674 while (borrow && k <= m+n) { // deal with borrow to the left
1680 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1683 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1684 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1685 DEBUG(dbgs() << '\n');
1686 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1687 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1688 // true value plus b**(n+1), namely as the b's complement of
1689 // the true value, and a "borrow" to the left should be remembered.
1692 bool carry = true; // true because b's complement is "complement + 1"
1693 for (unsigned i = 0; i <= m+n; ++i) {
1694 u[i] = ~u[i] + carry; // b's complement
1695 carry = carry && u[i] == 0;
1698 DEBUG(dbgs() << "KnuthDiv: after complement:");
1699 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1700 DEBUG(dbgs() << '\n');
1702 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1703 // negative, go to step D6; otherwise go on to step D7.
1704 q[j] = (unsigned)qp;
1706 // D6. [Add back]. The probability that this step is necessary is very
1707 // small, on the order of only 2/b. Make sure that test data accounts for
1708 // this possibility. Decrease q[j] by 1
1710 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1711 // A carry will occur to the left of u[j+n], and it should be ignored
1712 // since it cancels with the borrow that occurred in D4.
1714 for (unsigned i = 0; i < n; i++) {
1715 unsigned limit = std::min(u[j+i],v[i]);
1716 u[j+i] += v[i] + carry;
1717 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1721 DEBUG(dbgs() << "KnuthDiv: after correction:");
1722 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1723 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1725 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1728 DEBUG(dbgs() << "KnuthDiv: quotient:");
1729 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1730 DEBUG(dbgs() << '\n');
1732 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1733 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1734 // compute the remainder (urem uses this).
1736 // The value d is expressed by the "shift" value above since we avoided
1737 // multiplication by d by using a shift left. So, all we have to do is
1738 // shift right here. In order to mak
1741 DEBUG(dbgs() << "KnuthDiv: remainder:");
1742 for (int i = n-1; i >= 0; i--) {
1743 r[i] = (u[i] >> shift) | carry;
1744 carry = u[i] << (32 - shift);
1745 DEBUG(dbgs() << " " << r[i]);
1748 for (int i = n-1; i >= 0; i--) {
1750 DEBUG(dbgs() << " " << r[i]);
1753 DEBUG(dbgs() << '\n');
1756 DEBUG(dbgs() << '\n');
1760 void APInt::divide(const APInt LHS, unsigned lhsWords,
1761 const APInt &RHS, unsigned rhsWords,
1762 APInt *Quotient, APInt *Remainder)
1764 assert(lhsWords >= rhsWords && "Fractional result");
1766 // First, compose the values into an array of 32-bit words instead of
1767 // 64-bit words. This is a necessity of both the "short division" algorithm
1768 // and the Knuth "classical algorithm" which requires there to be native
1769 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1770 // can't use 64-bit operands here because we don't have native results of
1771 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1772 // work on large-endian machines.
1773 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1774 unsigned n = rhsWords * 2;
1775 unsigned m = (lhsWords * 2) - n;
1777 // Allocate space for the temporary values we need either on the stack, if
1778 // it will fit, or on the heap if it won't.
1779 unsigned SPACE[128];
1784 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1787 Q = &SPACE[(m+n+1) + n];
1789 R = &SPACE[(m+n+1) + n + (m+n)];
1791 U = new unsigned[m + n + 1];
1792 V = new unsigned[n];
1793 Q = new unsigned[m+n];
1795 R = new unsigned[n];
1798 // Initialize the dividend
1799 memset(U, 0, (m+n+1)*sizeof(unsigned));
1800 for (unsigned i = 0; i < lhsWords; ++i) {
1801 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1802 U[i * 2] = (unsigned)(tmp & mask);
1803 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1805 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1807 // Initialize the divisor
1808 memset(V, 0, (n)*sizeof(unsigned));
1809 for (unsigned i = 0; i < rhsWords; ++i) {
1810 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1811 V[i * 2] = (unsigned)(tmp & mask);
1812 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1815 // initialize the quotient and remainder
1816 memset(Q, 0, (m+n) * sizeof(unsigned));
1818 memset(R, 0, n * sizeof(unsigned));
1820 // Now, adjust m and n for the Knuth division. n is the number of words in
1821 // the divisor. m is the number of words by which the dividend exceeds the
1822 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1823 // contain any zero words or the Knuth algorithm fails.
1824 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1828 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1831 // If we're left with only a single word for the divisor, Knuth doesn't work
1832 // so we implement the short division algorithm here. This is much simpler
1833 // and faster because we are certain that we can divide a 64-bit quantity
1834 // by a 32-bit quantity at hardware speed and short division is simply a
1835 // series of such operations. This is just like doing short division but we
1836 // are using base 2^32 instead of base 10.
1837 assert(n != 0 && "Divide by zero?");
1839 unsigned divisor = V[0];
1840 unsigned remainder = 0;
1841 for (int i = m+n-1; i >= 0; i--) {
1842 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1843 if (partial_dividend == 0) {
1846 } else if (partial_dividend < divisor) {
1848 remainder = (unsigned)partial_dividend;
1849 } else if (partial_dividend == divisor) {
1853 Q[i] = (unsigned)(partial_dividend / divisor);
1854 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1860 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1862 KnuthDiv(U, V, Q, R, m, n);
1865 // If the caller wants the quotient
1867 // Set up the Quotient value's memory.
1868 if (Quotient->BitWidth != LHS.BitWidth) {
1869 if (Quotient->isSingleWord())
1872 delete [] Quotient->pVal;
1873 Quotient->BitWidth = LHS.BitWidth;
1874 if (!Quotient->isSingleWord())
1875 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1879 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1881 if (lhsWords == 1) {
1883 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1884 if (Quotient->isSingleWord())
1885 Quotient->VAL = tmp;
1887 Quotient->pVal[0] = tmp;
1889 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1890 for (unsigned i = 0; i < lhsWords; ++i)
1892 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1896 // If the caller wants the remainder
1898 // Set up the Remainder value's memory.
1899 if (Remainder->BitWidth != RHS.BitWidth) {
1900 if (Remainder->isSingleWord())
1903 delete [] Remainder->pVal;
1904 Remainder->BitWidth = RHS.BitWidth;
1905 if (!Remainder->isSingleWord())
1906 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1910 // The remainder is in R. Reconstitute the remainder into Remainder's low
1912 if (rhsWords == 1) {
1914 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1915 if (Remainder->isSingleWord())
1916 Remainder->VAL = tmp;
1918 Remainder->pVal[0] = tmp;
1920 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1921 for (unsigned i = 0; i < rhsWords; ++i)
1922 Remainder->pVal[i] =
1923 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1927 // Clean up the memory we allocated.
1928 if (U != &SPACE[0]) {
1936 APInt APInt::udiv(const APInt& RHS) const {
1937 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1939 // First, deal with the easy case
1940 if (isSingleWord()) {
1941 assert(RHS.VAL != 0 && "Divide by zero?");
1942 return APInt(BitWidth, VAL / RHS.VAL);
1945 // Get some facts about the LHS and RHS number of bits and words
1946 unsigned rhsBits = RHS.getActiveBits();
1947 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1948 assert(rhsWords && "Divided by zero???");
1949 unsigned lhsBits = this->getActiveBits();
1950 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1952 // Deal with some degenerate cases
1955 return APInt(BitWidth, 0);
1956 else if (lhsWords < rhsWords || this->ult(RHS)) {
1957 // X / Y ===> 0, iff X < Y
1958 return APInt(BitWidth, 0);
1959 } else if (*this == RHS) {
1961 return APInt(BitWidth, 1);
1962 } else if (lhsWords == 1 && rhsWords == 1) {
1963 // All high words are zero, just use native divide
1964 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1967 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1968 APInt Quotient(1,0); // to hold result.
1969 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1973 APInt APInt::urem(const APInt& RHS) const {
1974 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1975 if (isSingleWord()) {
1976 assert(RHS.VAL != 0 && "Remainder by zero?");
1977 return APInt(BitWidth, VAL % RHS.VAL);
1980 // Get some facts about the LHS
1981 unsigned lhsBits = getActiveBits();
1982 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1984 // Get some facts about the RHS
1985 unsigned rhsBits = RHS.getActiveBits();
1986 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1987 assert(rhsWords && "Performing remainder operation by zero ???");
1989 // Check the degenerate cases
1990 if (lhsWords == 0) {
1992 return APInt(BitWidth, 0);
1993 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1994 // X % Y ===> X, iff X < Y
1996 } else if (*this == RHS) {
1998 return APInt(BitWidth, 0);
1999 } else if (lhsWords == 1) {
2000 // All high words are zero, just use native remainder
2001 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
2004 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2005 APInt Remainder(1,0);
2006 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2010 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2011 APInt &Quotient, APInt &Remainder) {
2012 // Get some size facts about the dividend and divisor
2013 unsigned lhsBits = LHS.getActiveBits();
2014 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2015 unsigned rhsBits = RHS.getActiveBits();
2016 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2018 // Check the degenerate cases
2019 if (lhsWords == 0) {
2020 Quotient = 0; // 0 / Y ===> 0
2021 Remainder = 0; // 0 % Y ===> 0
2025 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2026 Remainder = LHS; // X % Y ===> X, iff X < Y
2027 Quotient = 0; // X / Y ===> 0, iff X < Y
2032 Quotient = 1; // X / X ===> 1
2033 Remainder = 0; // X % X ===> 0;
2037 if (lhsWords == 1 && rhsWords == 1) {
2038 // There is only one word to consider so use the native versions.
2039 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2040 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2041 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2042 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2046 // Okay, lets do it the long way
2047 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2050 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2051 APInt Res = *this+RHS;
2052 Overflow = isNonNegative() == RHS.isNonNegative() &&
2053 Res.isNonNegative() != isNonNegative();
2057 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2058 APInt Res = *this+RHS;
2059 Overflow = Res.ult(RHS);
2063 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2064 APInt Res = *this - RHS;
2065 Overflow = isNonNegative() != RHS.isNonNegative() &&
2066 Res.isNonNegative() != isNonNegative();
2070 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2071 APInt Res = *this-RHS;
2072 Overflow = Res.ugt(*this);
2076 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2077 // MININT/-1 --> overflow.
2078 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2082 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2083 APInt Res = *this * RHS;
2085 if (*this != 0 && RHS != 0)
2086 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2092 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2093 Overflow = ShAmt >= getBitWidth();
2095 ShAmt = getBitWidth()-1;
2097 if (isNonNegative()) // Don't allow sign change.
2098 Overflow = ShAmt >= countLeadingZeros();
2100 Overflow = ShAmt >= countLeadingOnes();
2102 return *this << ShAmt;
2108 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2109 // Check our assumptions here
2110 assert(!str.empty() && "Invalid string length");
2111 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2112 "Radix should be 2, 8, 10, or 16!");
2114 StringRef::iterator p = str.begin();
2115 size_t slen = str.size();
2116 bool isNeg = *p == '-';
2117 if (*p == '-' || *p == '+') {
2120 assert(slen && "String is only a sign, needs a value.");
2122 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2123 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2124 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2125 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2126 "Insufficient bit width");
2129 if (!isSingleWord())
2130 pVal = getClearedMemory(getNumWords());
2132 // Figure out if we can shift instead of multiply
2133 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2135 // Set up an APInt for the digit to add outside the loop so we don't
2136 // constantly construct/destruct it.
2137 APInt apdigit(getBitWidth(), 0);
2138 APInt apradix(getBitWidth(), radix);
2140 // Enter digit traversal loop
2141 for (StringRef::iterator e = str.end(); p != e; ++p) {
2142 unsigned digit = getDigit(*p, radix);
2143 assert(digit < radix && "Invalid character in digit string");
2145 // Shift or multiply the value by the radix
2153 // Add in the digit we just interpreted
2154 if (apdigit.isSingleWord())
2155 apdigit.VAL = digit;
2157 apdigit.pVal[0] = digit;
2160 // If its negative, put it in two's complement form
2167 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2168 bool Signed) const {
2169 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2170 "Radix should be 2, 8, 10, or 16!");
2172 // First, check for a zero value and just short circuit the logic below.
2178 static const char Digits[] = "0123456789ABCDEF";
2180 if (isSingleWord()) {
2182 char *BufPtr = Buffer+65;
2188 int64_t I = getSExtValue();
2198 *--BufPtr = Digits[N % Radix];
2201 Str.append(BufPtr, Buffer+65);
2207 if (Signed && isNegative()) {
2208 // They want to print the signed version and it is a negative value
2209 // Flip the bits and add one to turn it into the equivalent positive
2210 // value and put a '-' in the result.
2216 // We insert the digits backward, then reverse them to get the right order.
2217 unsigned StartDig = Str.size();
2219 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2220 // because the number of bits per digit (1, 3 and 4 respectively) divides
2221 // equaly. We just shift until the value is zero.
2223 // Just shift tmp right for each digit width until it becomes zero
2224 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2225 unsigned MaskAmt = Radix - 1;
2228 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2229 Str.push_back(Digits[Digit]);
2230 Tmp = Tmp.lshr(ShiftAmt);
2233 APInt divisor(4, 10);
2235 APInt APdigit(1, 0);
2236 APInt tmp2(Tmp.getBitWidth(), 0);
2237 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2239 unsigned Digit = (unsigned)APdigit.getZExtValue();
2240 assert(Digit < Radix && "divide failed");
2241 Str.push_back(Digits[Digit]);
2246 // Reverse the digits before returning.
2247 std::reverse(Str.begin()+StartDig, Str.end());
2250 /// toString - This returns the APInt as a std::string. Note that this is an
2251 /// inefficient method. It is better to pass in a SmallVector/SmallString
2252 /// to the methods above.
2253 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2255 toString(S, Radix, Signed);
2260 void APInt::dump() const {
2261 SmallString<40> S, U;
2262 this->toStringUnsigned(U);
2263 this->toStringSigned(S);
2264 dbgs() << "APInt(" << BitWidth << "b, "
2265 << U.str() << "u " << S.str() << "s)";
2268 void APInt::print(raw_ostream &OS, bool isSigned) const {
2270 this->toString(S, 10, isSigned);
2274 // This implements a variety of operations on a representation of
2275 // arbitrary precision, two's-complement, bignum integer values.
2277 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2278 // and unrestricting assumption.
2279 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2280 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2282 /* Some handy functions local to this file. */
2285 /* Returns the integer part with the least significant BITS set.
2286 BITS cannot be zero. */
2287 static inline integerPart
2288 lowBitMask(unsigned int bits)
2290 assert(bits != 0 && bits <= integerPartWidth);
2292 return ~(integerPart) 0 >> (integerPartWidth - bits);
2295 /* Returns the value of the lower half of PART. */
2296 static inline integerPart
2297 lowHalf(integerPart part)
2299 return part & lowBitMask(integerPartWidth / 2);
2302 /* Returns the value of the upper half of PART. */
2303 static inline integerPart
2304 highHalf(integerPart part)
2306 return part >> (integerPartWidth / 2);
2309 /* Returns the bit number of the most significant set bit of a part.
2310 If the input number has no bits set -1U is returned. */
2312 partMSB(integerPart value)
2314 unsigned int n, msb;
2319 n = integerPartWidth / 2;
2334 /* Returns the bit number of the least significant set bit of a
2335 part. If the input number has no bits set -1U is returned. */
2337 partLSB(integerPart value)
2339 unsigned int n, lsb;
2344 lsb = integerPartWidth - 1;
2345 n = integerPartWidth / 2;
2360 /* Sets the least significant part of a bignum to the input value, and
2361 zeroes out higher parts. */
2363 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2370 for (i = 1; i < parts; i++)
2374 /* Assign one bignum to another. */
2376 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2380 for (i = 0; i < parts; i++)
2384 /* Returns true if a bignum is zero, false otherwise. */
2386 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2390 for (i = 0; i < parts; i++)
2397 /* Extract the given bit of a bignum; returns 0 or 1. */
2399 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2401 return (parts[bit / integerPartWidth] &
2402 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2405 /* Set the given bit of a bignum. */
2407 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2409 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2412 /* Clears the given bit of a bignum. */
2414 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2416 parts[bit / integerPartWidth] &=
2417 ~((integerPart) 1 << (bit % integerPartWidth));
2420 /* Returns the bit number of the least significant set bit of a
2421 number. If the input number has no bits set -1U is returned. */
2423 APInt::tcLSB(const integerPart *parts, unsigned int n)
2425 unsigned int i, lsb;
2427 for (i = 0; i < n; i++) {
2428 if (parts[i] != 0) {
2429 lsb = partLSB(parts[i]);
2431 return lsb + i * integerPartWidth;
2438 /* Returns the bit number of the most significant set bit of a number.
2439 If the input number has no bits set -1U is returned. */
2441 APInt::tcMSB(const integerPart *parts, unsigned int n)
2448 if (parts[n] != 0) {
2449 msb = partMSB(parts[n]);
2451 return msb + n * integerPartWidth;
2458 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2459 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2460 the least significant bit of DST. All high bits above srcBITS in
2461 DST are zero-filled. */
2463 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2464 unsigned int srcBits, unsigned int srcLSB)
2466 unsigned int firstSrcPart, dstParts, shift, n;
2468 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2469 assert(dstParts <= dstCount);
2471 firstSrcPart = srcLSB / integerPartWidth;
2472 tcAssign (dst, src + firstSrcPart, dstParts);
2474 shift = srcLSB % integerPartWidth;
2475 tcShiftRight (dst, dstParts, shift);
2477 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2478 in DST. If this is less that srcBits, append the rest, else
2479 clear the high bits. */
2480 n = dstParts * integerPartWidth - shift;
2482 integerPart mask = lowBitMask (srcBits - n);
2483 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2484 << n % integerPartWidth);
2485 } else if (n > srcBits) {
2486 if (srcBits % integerPartWidth)
2487 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2490 /* Clear high parts. */
2491 while (dstParts < dstCount)
2492 dst[dstParts++] = 0;
2495 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2497 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2498 integerPart c, unsigned int parts)
2504 for (i = 0; i < parts; i++) {
2509 dst[i] += rhs[i] + 1;
2520 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2522 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2523 integerPart c, unsigned int parts)
2529 for (i = 0; i < parts; i++) {
2534 dst[i] -= rhs[i] + 1;
2545 /* Negate a bignum in-place. */
2547 APInt::tcNegate(integerPart *dst, unsigned int parts)
2549 tcComplement(dst, parts);
2550 tcIncrement(dst, parts);
2553 /* DST += SRC * MULTIPLIER + CARRY if add is true
2554 DST = SRC * MULTIPLIER + CARRY if add is false
2556 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2557 they must start at the same point, i.e. DST == SRC.
2559 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2560 returned. Otherwise DST is filled with the least significant
2561 DSTPARTS parts of the result, and if all of the omitted higher
2562 parts were zero return zero, otherwise overflow occurred and
2565 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2566 integerPart multiplier, integerPart carry,
2567 unsigned int srcParts, unsigned int dstParts,
2572 /* Otherwise our writes of DST kill our later reads of SRC. */
2573 assert(dst <= src || dst >= src + srcParts);
2574 assert(dstParts <= srcParts + 1);
2576 /* N loops; minimum of dstParts and srcParts. */
2577 n = dstParts < srcParts ? dstParts: srcParts;
2579 for (i = 0; i < n; i++) {
2580 integerPart low, mid, high, srcPart;
2582 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2584 This cannot overflow, because
2586 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2588 which is less than n^2. */
2592 if (multiplier == 0 || srcPart == 0) {
2596 low = lowHalf(srcPart) * lowHalf(multiplier);
2597 high = highHalf(srcPart) * highHalf(multiplier);
2599 mid = lowHalf(srcPart) * highHalf(multiplier);
2600 high += highHalf(mid);
2601 mid <<= integerPartWidth / 2;
2602 if (low + mid < low)
2606 mid = highHalf(srcPart) * lowHalf(multiplier);
2607 high += highHalf(mid);
2608 mid <<= integerPartWidth / 2;
2609 if (low + mid < low)
2613 /* Now add carry. */
2614 if (low + carry < low)
2620 /* And now DST[i], and store the new low part there. */
2621 if (low + dst[i] < low)
2631 /* Full multiplication, there is no overflow. */
2632 assert(i + 1 == dstParts);
2636 /* We overflowed if there is carry. */
2640 /* We would overflow if any significant unwritten parts would be
2641 non-zero. This is true if any remaining src parts are non-zero
2642 and the multiplier is non-zero. */
2644 for (; i < srcParts; i++)
2648 /* We fitted in the narrow destination. */
2653 /* DST = LHS * RHS, where DST has the same width as the operands and
2654 is filled with the least significant parts of the result. Returns
2655 one if overflow occurred, otherwise zero. DST must be disjoint
2656 from both operands. */
2658 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2659 const integerPart *rhs, unsigned int parts)
2664 assert(dst != lhs && dst != rhs);
2667 tcSet(dst, 0, parts);
2669 for (i = 0; i < parts; i++)
2670 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2676 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2677 operands. No overflow occurs. DST must be disjoint from both
2678 operands. Returns the number of parts required to hold the
2681 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2682 const integerPart *rhs, unsigned int lhsParts,
2683 unsigned int rhsParts)
2685 /* Put the narrower number on the LHS for less loops below. */
2686 if (lhsParts > rhsParts) {
2687 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2691 assert(dst != lhs && dst != rhs);
2693 tcSet(dst, 0, rhsParts);
2695 for (n = 0; n < lhsParts; n++)
2696 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2698 n = lhsParts + rhsParts;
2700 return n - (dst[n - 1] == 0);
2704 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2705 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2706 set REMAINDER to the remainder, return zero. i.e.
2708 OLD_LHS = RHS * LHS + REMAINDER
2710 SCRATCH is a bignum of the same size as the operands and result for
2711 use by the routine; its contents need not be initialized and are
2712 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2715 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2716 integerPart *remainder, integerPart *srhs,
2719 unsigned int n, shiftCount;
2722 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2724 shiftCount = tcMSB(rhs, parts) + 1;
2725 if (shiftCount == 0)
2728 shiftCount = parts * integerPartWidth - shiftCount;
2729 n = shiftCount / integerPartWidth;
2730 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2732 tcAssign(srhs, rhs, parts);
2733 tcShiftLeft(srhs, parts, shiftCount);
2734 tcAssign(remainder, lhs, parts);
2735 tcSet(lhs, 0, parts);
2737 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2742 compare = tcCompare(remainder, srhs, parts);
2744 tcSubtract(remainder, srhs, 0, parts);
2748 if (shiftCount == 0)
2751 tcShiftRight(srhs, parts, 1);
2752 if ((mask >>= 1) == 0)
2753 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2759 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2760 There are no restrictions on COUNT. */
2762 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2765 unsigned int jump, shift;
2767 /* Jump is the inter-part jump; shift is is intra-part shift. */
2768 jump = count / integerPartWidth;
2769 shift = count % integerPartWidth;
2771 while (parts > jump) {
2776 /* dst[i] comes from the two parts src[i - jump] and, if we have
2777 an intra-part shift, src[i - jump - 1]. */
2778 part = dst[parts - jump];
2781 if (parts >= jump + 1)
2782 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2793 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2794 zero. There are no restrictions on COUNT. */
2796 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2799 unsigned int i, jump, shift;
2801 /* Jump is the inter-part jump; shift is is intra-part shift. */
2802 jump = count / integerPartWidth;
2803 shift = count % integerPartWidth;
2805 /* Perform the shift. This leaves the most significant COUNT bits
2806 of the result at zero. */
2807 for (i = 0; i < parts; i++) {
2810 if (i + jump >= parts) {
2813 part = dst[i + jump];
2816 if (i + jump + 1 < parts)
2817 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2826 /* Bitwise and of two bignums. */
2828 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2832 for (i = 0; i < parts; i++)
2836 /* Bitwise inclusive or of two bignums. */
2838 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2842 for (i = 0; i < parts; i++)
2846 /* Bitwise exclusive or of two bignums. */
2848 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2852 for (i = 0; i < parts; i++)
2856 /* Complement a bignum in-place. */
2858 APInt::tcComplement(integerPart *dst, unsigned int parts)
2862 for (i = 0; i < parts; i++)
2866 /* Comparison (unsigned) of two bignums. */
2868 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2873 if (lhs[parts] == rhs[parts])
2876 if (lhs[parts] > rhs[parts])
2885 /* Increment a bignum in-place, return the carry flag. */
2887 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2891 for (i = 0; i < parts; i++)
2898 /* Set the least significant BITS bits of a bignum, clear the
2901 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2907 while (bits > integerPartWidth) {
2908 dst[i++] = ~(integerPart) 0;
2909 bits -= integerPartWidth;
2913 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);