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) {
51 if (radix == 16 || radix == 36) {
75 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
76 pVal = getClearedMemory(getNumWords());
78 if (isSigned && int64_t(val) < 0)
79 for (unsigned i = 1; i < getNumWords(); ++i)
83 void APInt::initSlowCase(const APInt& that) {
84 pVal = getMemory(getNumWords());
85 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
88 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
89 assert(BitWidth && "Bitwidth too small");
90 assert(bigVal.data() && "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>(bigVal.size(), getNumWords());
98 // Copy the words from bigVal to pVal
99 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
101 // Make sure unused high bits are cleared
105 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
106 : BitWidth(numBits), VAL(0) {
107 initFromArray(bigVal);
110 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
111 : BitWidth(numBits), VAL(0) {
112 initFromArray(makeArrayRef(bigVal, numWords));
115 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
116 : BitWidth(numbits), VAL(0) {
117 assert(BitWidth && "Bitwidth too small");
118 fromString(numbits, Str, radix);
121 APInt& APInt::AssignSlowCase(const APInt& RHS) {
122 // Don't do anything for X = X
126 if (BitWidth == RHS.getBitWidth()) {
127 // assume same bit-width single-word case is already handled
128 assert(!isSingleWord());
129 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
133 if (isSingleWord()) {
134 // assume case where both are single words is already handled
135 assert(!RHS.isSingleWord());
137 pVal = getMemory(RHS.getNumWords());
138 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
139 } else if (getNumWords() == RHS.getNumWords())
140 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
141 else if (RHS.isSingleWord()) {
146 pVal = getMemory(RHS.getNumWords());
147 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
149 BitWidth = RHS.BitWidth;
150 return clearUnusedBits();
153 APInt& APInt::operator=(uint64_t RHS) {
158 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
160 return clearUnusedBits();
163 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
164 void APInt::Profile(FoldingSetNodeID& ID) const {
165 ID.AddInteger(BitWidth);
167 if (isSingleWord()) {
172 unsigned NumWords = getNumWords();
173 for (unsigned i = 0; i < NumWords; ++i)
174 ID.AddInteger(pVal[i]);
177 /// add_1 - This function adds a single "digit" integer, y, to the multiple
178 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
179 /// 1 is returned if there is a carry out, otherwise 0 is returned.
180 /// @returns the carry of the addition.
181 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
182 for (unsigned i = 0; i < len; ++i) {
185 y = 1; // Carry one to next digit.
187 y = 0; // No need to carry so exit early
194 /// @brief Prefix increment operator. Increments the APInt by one.
195 APInt& APInt::operator++() {
199 add_1(pVal, pVal, getNumWords(), 1);
200 return clearUnusedBits();
203 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
204 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
205 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
206 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
207 /// In other words, if y > x then this function returns 1, otherwise 0.
208 /// @returns the borrow out of the subtraction
209 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
210 for (unsigned i = 0; i < len; ++i) {
214 y = 1; // We have to "borrow 1" from next "digit"
216 y = 0; // No need to borrow
217 break; // Remaining digits are unchanged so exit early
223 /// @brief Prefix decrement operator. Decrements the APInt by one.
224 APInt& APInt::operator--() {
228 sub_1(pVal, getNumWords(), 1);
229 return clearUnusedBits();
232 /// add - This function adds the integer array x to the integer array Y and
233 /// places the result in dest.
234 /// @returns the carry out from the addition
235 /// @brief General addition of 64-bit integer arrays
236 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
239 for (unsigned i = 0; i< len; ++i) {
240 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
241 dest[i] = x[i] + y[i] + carry;
242 carry = dest[i] < limit || (carry && dest[i] == limit);
247 /// Adds the RHS APint to this APInt.
248 /// @returns this, after addition of RHS.
249 /// @brief Addition assignment operator.
250 APInt& APInt::operator+=(const APInt& RHS) {
251 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
255 add(pVal, pVal, RHS.pVal, getNumWords());
257 return clearUnusedBits();
260 /// Subtracts the integer array y from the integer array x
261 /// @returns returns the borrow out.
262 /// @brief Generalized subtraction of 64-bit integer arrays.
263 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
266 for (unsigned i = 0; i < len; ++i) {
267 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
268 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
269 dest[i] = x_tmp - y[i];
274 /// Subtracts the RHS APInt from this APInt
275 /// @returns this, after subtraction
276 /// @brief Subtraction assignment operator.
277 APInt& APInt::operator-=(const APInt& RHS) {
278 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
282 sub(pVal, pVal, RHS.pVal, getNumWords());
283 return clearUnusedBits();
286 /// Multiplies an integer array, x, by a uint64_t integer and places the result
288 /// @returns the carry out of the multiplication.
289 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
290 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
291 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
292 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
295 // For each digit of x.
296 for (unsigned i = 0; i < len; ++i) {
297 // Split x into high and low words
298 uint64_t lx = x[i] & 0xffffffffULL;
299 uint64_t hx = x[i] >> 32;
300 // hasCarry - A flag to indicate if there is a carry to the next digit.
301 // hasCarry == 0, no carry
302 // hasCarry == 1, has carry
303 // hasCarry == 2, no carry and the calculation result == 0.
304 uint8_t hasCarry = 0;
305 dest[i] = carry + lx * ly;
306 // Determine if the add above introduces carry.
307 hasCarry = (dest[i] < carry) ? 1 : 0;
308 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
309 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
310 // (2^32 - 1) + 2^32 = 2^64.
311 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
313 carry += (lx * hy) & 0xffffffffULL;
314 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
315 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
316 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
321 /// Multiplies integer array x by integer array y and stores the result into
322 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
323 /// @brief Generalized multiplicate of integer arrays.
324 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
326 dest[xlen] = mul_1(dest, x, xlen, y[0]);
327 for (unsigned i = 1; i < ylen; ++i) {
328 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
329 uint64_t carry = 0, lx = 0, hx = 0;
330 for (unsigned j = 0; j < xlen; ++j) {
331 lx = x[j] & 0xffffffffULL;
333 // hasCarry - A flag to indicate if has carry.
334 // hasCarry == 0, no carry
335 // hasCarry == 1, has carry
336 // hasCarry == 2, no carry and the calculation result == 0.
337 uint8_t hasCarry = 0;
338 uint64_t resul = carry + lx * ly;
339 hasCarry = (resul < carry) ? 1 : 0;
340 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
341 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
343 carry += (lx * hy) & 0xffffffffULL;
344 resul = (carry << 32) | (resul & 0xffffffffULL);
346 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
347 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
348 ((lx * hy) >> 32) + hx * hy;
350 dest[i+xlen] = carry;
354 APInt& APInt::operator*=(const APInt& RHS) {
355 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
356 if (isSingleWord()) {
362 // Get some bit facts about LHS and check for zero
363 unsigned lhsBits = getActiveBits();
364 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
369 // Get some bit facts about RHS and check for zero
370 unsigned rhsBits = RHS.getActiveBits();
371 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
378 // Allocate space for the result
379 unsigned destWords = rhsWords + lhsWords;
380 uint64_t *dest = getMemory(destWords);
382 // Perform the long multiply
383 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
385 // Copy result back into *this
387 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
388 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
391 // delete dest array and return
396 APInt& APInt::operator&=(const APInt& RHS) {
397 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
398 if (isSingleWord()) {
402 unsigned numWords = getNumWords();
403 for (unsigned i = 0; i < numWords; ++i)
404 pVal[i] &= RHS.pVal[i];
408 APInt& APInt::operator|=(const APInt& RHS) {
409 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
410 if (isSingleWord()) {
414 unsigned numWords = getNumWords();
415 for (unsigned i = 0; i < numWords; ++i)
416 pVal[i] |= RHS.pVal[i];
420 APInt& APInt::operator^=(const APInt& RHS) {
421 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
422 if (isSingleWord()) {
424 this->clearUnusedBits();
427 unsigned numWords = getNumWords();
428 for (unsigned i = 0; i < numWords; ++i)
429 pVal[i] ^= RHS.pVal[i];
430 return clearUnusedBits();
433 APInt APInt::AndSlowCase(const APInt& RHS) const {
434 unsigned numWords = getNumWords();
435 uint64_t* val = getMemory(numWords);
436 for (unsigned i = 0; i < numWords; ++i)
437 val[i] = pVal[i] & RHS.pVal[i];
438 return APInt(val, getBitWidth());
441 APInt APInt::OrSlowCase(const APInt& RHS) const {
442 unsigned numWords = getNumWords();
443 uint64_t *val = getMemory(numWords);
444 for (unsigned i = 0; i < numWords; ++i)
445 val[i] = pVal[i] | RHS.pVal[i];
446 return APInt(val, getBitWidth());
449 APInt APInt::XorSlowCase(const APInt& RHS) const {
450 unsigned numWords = getNumWords();
451 uint64_t *val = getMemory(numWords);
452 for (unsigned i = 0; i < numWords; ++i)
453 val[i] = pVal[i] ^ RHS.pVal[i];
455 // 0^0==1 so clear the high bits in case they got set.
456 return APInt(val, getBitWidth()).clearUnusedBits();
459 bool APInt::operator !() const {
463 for (unsigned i = 0; i < getNumWords(); ++i)
469 APInt APInt::operator*(const APInt& RHS) const {
470 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
472 return APInt(BitWidth, VAL * RHS.VAL);
478 APInt APInt::operator+(const APInt& RHS) const {
479 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
481 return APInt(BitWidth, VAL + RHS.VAL);
482 APInt Result(BitWidth, 0);
483 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
484 return Result.clearUnusedBits();
487 APInt APInt::operator-(const APInt& RHS) const {
488 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
490 return APInt(BitWidth, VAL - RHS.VAL);
491 APInt Result(BitWidth, 0);
492 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
493 return Result.clearUnusedBits();
496 bool APInt::operator[](unsigned bitPosition) const {
497 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
498 return (maskBit(bitPosition) &
499 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
502 bool APInt::EqualSlowCase(const APInt& RHS) const {
503 // Get some facts about the number of bits used in the two operands.
504 unsigned n1 = getActiveBits();
505 unsigned n2 = RHS.getActiveBits();
507 // If the number of bits isn't the same, they aren't equal
511 // If the number of bits fits in a word, we only need to compare the low word.
512 if (n1 <= APINT_BITS_PER_WORD)
513 return pVal[0] == RHS.pVal[0];
515 // Otherwise, compare everything
516 for (int i = whichWord(n1 - 1); i >= 0; --i)
517 if (pVal[i] != RHS.pVal[i])
522 bool APInt::EqualSlowCase(uint64_t Val) const {
523 unsigned n = getActiveBits();
524 if (n <= APINT_BITS_PER_WORD)
525 return pVal[0] == Val;
530 bool APInt::ult(const APInt& RHS) const {
531 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
533 return VAL < RHS.VAL;
535 // Get active bit length of both operands
536 unsigned n1 = getActiveBits();
537 unsigned n2 = RHS.getActiveBits();
539 // If magnitude of LHS is less than RHS, return true.
543 // If magnitude of RHS is greather than LHS, return false.
547 // If they bot fit in a word, just compare the low order word
548 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
549 return pVal[0] < RHS.pVal[0];
551 // Otherwise, compare all words
552 unsigned topWord = whichWord(std::max(n1,n2)-1);
553 for (int i = topWord; i >= 0; --i) {
554 if (pVal[i] > RHS.pVal[i])
556 if (pVal[i] < RHS.pVal[i])
562 bool APInt::slt(const APInt& RHS) const {
563 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
564 if (isSingleWord()) {
565 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
566 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
567 return lhsSext < rhsSext;
572 bool lhsNeg = isNegative();
573 bool rhsNeg = rhs.isNegative();
575 // Sign bit is set so perform two's complement to make it positive
580 // Sign bit is set so perform two's complement to make it positive
585 // Now we have unsigned values to compare so do the comparison if necessary
586 // based on the negativeness of the values.
598 void APInt::setBit(unsigned bitPosition) {
600 VAL |= maskBit(bitPosition);
602 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
605 /// Set the given bit to 0 whose position is given as "bitPosition".
606 /// @brief Set a given bit to 0.
607 void APInt::clearBit(unsigned bitPosition) {
609 VAL &= ~maskBit(bitPosition);
611 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
614 /// @brief Toggle every bit to its opposite value.
616 /// Toggle a given bit to its opposite value whose position is given
617 /// as "bitPosition".
618 /// @brief Toggles a given bit to its opposite value.
619 void APInt::flipBit(unsigned bitPosition) {
620 assert(bitPosition < BitWidth && "Out of the bit-width range!");
621 if ((*this)[bitPosition]) clearBit(bitPosition);
622 else setBit(bitPosition);
625 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
626 assert(!str.empty() && "Invalid string length");
627 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
629 "Radix should be 2, 8, 10, 16, or 36!");
631 size_t slen = str.size();
633 // Each computation below needs to know if it's negative.
634 StringRef::iterator p = str.begin();
635 unsigned isNegative = *p == '-';
636 if (*p == '-' || *p == '+') {
639 assert(slen && "String is only a sign, needs a value.");
642 // For radixes of power-of-two values, the bits required is accurately and
645 return slen + isNegative;
647 return slen * 3 + isNegative;
649 return slen * 4 + isNegative;
653 // This is grossly inefficient but accurate. We could probably do something
654 // with a computation of roughly slen*64/20 and then adjust by the value of
655 // the first few digits. But, I'm not sure how accurate that could be.
657 // Compute a sufficient number of bits that is always large enough but might
658 // be too large. This avoids the assertion in the constructor. This
659 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
660 // bits in that case.
662 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
663 : (slen == 1 ? 7 : slen * 16/3);
665 // Convert to the actual binary value.
666 APInt tmp(sufficient, StringRef(p, slen), radix);
668 // Compute how many bits are required. If the log is infinite, assume we need
670 unsigned log = tmp.logBase2();
671 if (log == (unsigned)-1) {
672 return isNegative + 1;
674 return isNegative + log + 1;
678 // From http://www.burtleburtle.net, byBob Jenkins.
679 // When targeting x86, both GCC and LLVM seem to recognize this as a
680 // rotate instruction.
681 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
683 // From http://www.burtleburtle.net, by Bob Jenkins.
686 a -= c; a ^= rot(c, 4); c += b; \
687 b -= a; b ^= rot(a, 6); a += c; \
688 c -= b; c ^= rot(b, 8); b += a; \
689 a -= c; a ^= rot(c,16); c += b; \
690 b -= a; b ^= rot(a,19); a += c; \
691 c -= b; c ^= rot(b, 4); b += a; \
694 // From http://www.burtleburtle.net, by Bob Jenkins.
695 #define final(a,b,c) \
697 c ^= b; c -= rot(b,14); \
698 a ^= c; a -= rot(c,11); \
699 b ^= a; b -= rot(a,25); \
700 c ^= b; c -= rot(b,16); \
701 a ^= c; a -= rot(c,4); \
702 b ^= a; b -= rot(a,14); \
703 c ^= b; c -= rot(b,24); \
706 // hashword() was adapted from http://www.burtleburtle.net, by Bob
707 // Jenkins. k is a pointer to an array of uint32_t values; length is
708 // the length of the key, in 32-bit chunks. This version only handles
709 // keys that are a multiple of 32 bits in size.
710 static inline uint32_t hashword(const uint64_t *k64, size_t length)
712 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
715 /* Set up the internal state */
716 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
718 /*------------------------------------------------- handle most of the key */
728 /*------------------------------------------- handle the last 3 uint32_t's */
729 switch (length) { /* all the case statements fall through */
734 case 0: /* case 0: nothing left to add */
737 /*------------------------------------------------------ report the result */
741 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
742 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
743 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
744 // function into about 35 instructions when inlined.
745 static inline uint32_t hashword8(const uint64_t k64)
748 a = b = c = 0xdeadbeef + 4;
750 a += k64 & 0xffffffff;
758 uint64_t APInt::getHashValue() const {
761 hash = hashword8(VAL);
763 hash = hashword(pVal, getNumWords()*2);
767 /// HiBits - This function returns the high "numBits" bits of this APInt.
768 APInt APInt::getHiBits(unsigned numBits) const {
769 return APIntOps::lshr(*this, BitWidth - numBits);
772 /// LoBits - This function returns the low "numBits" bits of this APInt.
773 APInt APInt::getLoBits(unsigned numBits) const {
774 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
778 unsigned APInt::countLeadingZerosSlowCase() const {
779 // Treat the most significand word differently because it might have
780 // meaningless bits set beyond the precision.
781 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
783 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
785 MSWMask = ~integerPart(0);
786 BitsInMSW = APINT_BITS_PER_WORD;
789 unsigned i = getNumWords();
790 integerPart MSW = pVal[i-1] & MSWMask;
792 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
794 unsigned Count = BitsInMSW;
795 for (--i; i > 0u; --i) {
797 Count += APINT_BITS_PER_WORD;
799 Count += CountLeadingZeros_64(pVal[i-1]);
806 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
810 while (V && (V & (1ULL << 63))) {
817 unsigned APInt::countLeadingOnes() const {
819 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
821 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
824 highWordBits = APINT_BITS_PER_WORD;
827 shift = APINT_BITS_PER_WORD - highWordBits;
829 int i = getNumWords() - 1;
830 unsigned Count = countLeadingOnes_64(pVal[i], shift);
831 if (Count == highWordBits) {
832 for (i--; i >= 0; --i) {
833 if (pVal[i] == -1ULL)
834 Count += APINT_BITS_PER_WORD;
836 Count += countLeadingOnes_64(pVal[i], 0);
844 unsigned APInt::countTrailingZeros() const {
846 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
849 for (; i < getNumWords() && pVal[i] == 0; ++i)
850 Count += APINT_BITS_PER_WORD;
851 if (i < getNumWords())
852 Count += CountTrailingZeros_64(pVal[i]);
853 return std::min(Count, BitWidth);
856 unsigned APInt::countTrailingOnesSlowCase() const {
859 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
860 Count += APINT_BITS_PER_WORD;
861 if (i < getNumWords())
862 Count += CountTrailingOnes_64(pVal[i]);
863 return std::min(Count, BitWidth);
866 unsigned APInt::countPopulationSlowCase() const {
868 for (unsigned i = 0; i < getNumWords(); ++i)
869 Count += CountPopulation_64(pVal[i]);
873 /// Perform a logical right-shift from Src to Dst, which must be equal or
874 /// non-overlapping, of Words words, by Shift, which must be less than 64.
875 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
878 for (int I = Words - 1; I >= 0; --I) {
879 uint64_t Tmp = Src[I];
880 Dst[I] = (Tmp >> Shift) | Carry;
881 Carry = Tmp << (64 - Shift);
885 APInt APInt::byteSwap() const {
886 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
888 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
890 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
891 if (BitWidth == 48) {
892 unsigned Tmp1 = unsigned(VAL >> 16);
893 Tmp1 = ByteSwap_32(Tmp1);
894 uint16_t Tmp2 = uint16_t(VAL);
895 Tmp2 = ByteSwap_16(Tmp2);
896 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
899 return APInt(BitWidth, ByteSwap_64(VAL));
901 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
902 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
903 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
904 if (Result.BitWidth != BitWidth) {
905 lshrNear(Result.pVal, Result.pVal, getNumWords(),
906 Result.BitWidth - BitWidth);
907 Result.BitWidth = BitWidth;
912 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
914 APInt A = API1, B = API2;
917 B = APIntOps::urem(A, B);
923 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
930 // Get the sign bit from the highest order bit
931 bool isNeg = T.I >> 63;
933 // Get the 11-bit exponent and adjust for the 1023 bit bias
934 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
936 // If the exponent is negative, the value is < 0 so just return 0.
938 return APInt(width, 0u);
940 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
941 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
943 // If the exponent doesn't shift all bits out of the mantissa
945 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
946 APInt(width, mantissa >> (52 - exp));
948 // If the client didn't provide enough bits for us to shift the mantissa into
949 // then the result is undefined, just return 0
950 if (width <= exp - 52)
951 return APInt(width, 0);
953 // Otherwise, we have to shift the mantissa bits up to the right location
954 APInt Tmp(width, mantissa);
955 Tmp = Tmp.shl((unsigned)exp - 52);
956 return isNeg ? -Tmp : Tmp;
959 /// RoundToDouble - This function converts this APInt to a double.
960 /// The layout for double is as following (IEEE Standard 754):
961 /// --------------------------------------
962 /// | Sign Exponent Fraction Bias |
963 /// |-------------------------------------- |
964 /// | 1[63] 11[62-52] 52[51-00] 1023 |
965 /// --------------------------------------
966 double APInt::roundToDouble(bool isSigned) const {
968 // Handle the simple case where the value is contained in one uint64_t.
969 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
970 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
972 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
975 return double(getWord(0));
978 // Determine if the value is negative.
979 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
981 // Construct the absolute value if we're negative.
982 APInt Tmp(isNeg ? -(*this) : (*this));
984 // Figure out how many bits we're using.
985 unsigned n = Tmp.getActiveBits();
987 // The exponent (without bias normalization) is just the number of bits
988 // we are using. Note that the sign bit is gone since we constructed the
992 // Return infinity for exponent overflow
994 if (!isSigned || !isNeg)
995 return std::numeric_limits<double>::infinity();
997 return -std::numeric_limits<double>::infinity();
999 exp += 1023; // Increment for 1023 bias
1001 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
1002 // extract the high 52 bits from the correct words in pVal.
1004 unsigned hiWord = whichWord(n-1);
1006 mantissa = Tmp.pVal[0];
1008 mantissa >>= n - 52; // shift down, we want the top 52 bits.
1010 assert(hiWord > 0 && "huh?");
1011 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
1012 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
1013 mantissa = hibits | lobits;
1016 // The leading bit of mantissa is implicit, so get rid of it.
1017 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
1022 T.I = sign | (exp << 52) | mantissa;
1026 // Truncate to new width.
1027 APInt APInt::trunc(unsigned width) const {
1028 assert(width < BitWidth && "Invalid APInt Truncate request");
1029 assert(width && "Can't truncate to 0 bits");
1031 if (width <= APINT_BITS_PER_WORD)
1032 return APInt(width, getRawData()[0]);
1034 APInt Result(getMemory(getNumWords(width)), width);
1038 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
1039 Result.pVal[i] = pVal[i];
1041 // Truncate and copy any partial word.
1042 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
1044 Result.pVal[i] = pVal[i] << bits >> bits;
1049 // Sign extend to a new width.
1050 APInt APInt::sext(unsigned width) const {
1051 assert(width > BitWidth && "Invalid APInt SignExtend request");
1053 if (width <= APINT_BITS_PER_WORD) {
1054 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
1055 val = (int64_t)val >> (width - BitWidth);
1056 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
1059 APInt Result(getMemory(getNumWords(width)), width);
1064 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
1065 word = getRawData()[i];
1066 Result.pVal[i] = word;
1069 // Read and sign-extend any partial word.
1070 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
1072 word = (int64_t)getRawData()[i] << bits >> bits;
1074 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1076 // Write remaining full words.
1077 for (; i != width / APINT_BITS_PER_WORD; i++) {
1078 Result.pVal[i] = word;
1079 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1082 // Write any partial word.
1083 bits = (0 - width) % APINT_BITS_PER_WORD;
1085 Result.pVal[i] = word << bits >> bits;
1090 // Zero extend to a new width.
1091 APInt APInt::zext(unsigned width) const {
1092 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1094 if (width <= APINT_BITS_PER_WORD)
1095 return APInt(width, VAL);
1097 APInt Result(getMemory(getNumWords(width)), width);
1101 for (i = 0; i != getNumWords(); i++)
1102 Result.pVal[i] = getRawData()[i];
1104 // Zero remaining words.
1105 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1110 APInt APInt::zextOrTrunc(unsigned width) const {
1111 if (BitWidth < width)
1113 if (BitWidth > width)
1114 return trunc(width);
1118 APInt APInt::sextOrTrunc(unsigned width) const {
1119 if (BitWidth < width)
1121 if (BitWidth > width)
1122 return trunc(width);
1126 APInt APInt::zextOrSelf(unsigned width) const {
1127 if (BitWidth < width)
1132 APInt APInt::sextOrSelf(unsigned width) const {
1133 if (BitWidth < width)
1138 /// Arithmetic right-shift this APInt by shiftAmt.
1139 /// @brief Arithmetic right-shift function.
1140 APInt APInt::ashr(const APInt &shiftAmt) const {
1141 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1144 /// Arithmetic right-shift this APInt by shiftAmt.
1145 /// @brief Arithmetic right-shift function.
1146 APInt APInt::ashr(unsigned shiftAmt) const {
1147 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1148 // Handle a degenerate case
1152 // Handle single word shifts with built-in ashr
1153 if (isSingleWord()) {
1154 if (shiftAmt == BitWidth)
1155 return APInt(BitWidth, 0); // undefined
1157 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1158 return APInt(BitWidth,
1159 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1163 // If all the bits were shifted out, the result is, technically, undefined.
1164 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1165 // issues in the algorithm below.
1166 if (shiftAmt == BitWidth) {
1168 return APInt(BitWidth, -1ULL, true);
1170 return APInt(BitWidth, 0);
1173 // Create some space for the result.
1174 uint64_t * val = new uint64_t[getNumWords()];
1176 // Compute some values needed by the following shift algorithms
1177 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1178 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1179 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1180 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1181 if (bitsInWord == 0)
1182 bitsInWord = APINT_BITS_PER_WORD;
1184 // If we are shifting whole words, just move whole words
1185 if (wordShift == 0) {
1186 // Move the words containing significant bits
1187 for (unsigned i = 0; i <= breakWord; ++i)
1188 val[i] = pVal[i+offset]; // move whole word
1190 // Adjust the top significant word for sign bit fill, if negative
1192 if (bitsInWord < APINT_BITS_PER_WORD)
1193 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1195 // Shift the low order words
1196 for (unsigned i = 0; i < breakWord; ++i) {
1197 // This combines the shifted corresponding word with the low bits from
1198 // the next word (shifted into this word's high bits).
1199 val[i] = (pVal[i+offset] >> wordShift) |
1200 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1203 // Shift the break word. In this case there are no bits from the next word
1204 // to include in this word.
1205 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1207 // Deal with sign extenstion in the break word, and possibly the word before
1210 if (wordShift > bitsInWord) {
1213 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1214 val[breakWord] |= ~0ULL;
1216 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1220 // Remaining words are 0 or -1, just assign them.
1221 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1222 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1224 return APInt(val, BitWidth).clearUnusedBits();
1227 /// Logical right-shift this APInt by shiftAmt.
1228 /// @brief Logical right-shift function.
1229 APInt APInt::lshr(const APInt &shiftAmt) const {
1230 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1233 /// Logical right-shift this APInt by shiftAmt.
1234 /// @brief Logical right-shift function.
1235 APInt APInt::lshr(unsigned shiftAmt) const {
1236 if (isSingleWord()) {
1237 if (shiftAmt == BitWidth)
1238 return APInt(BitWidth, 0);
1240 return APInt(BitWidth, this->VAL >> shiftAmt);
1243 // If all the bits were shifted out, the result is 0. This avoids issues
1244 // with shifting by the size of the integer type, which produces undefined
1245 // results. We define these "undefined results" to always be 0.
1246 if (shiftAmt == BitWidth)
1247 return APInt(BitWidth, 0);
1249 // If none of the bits are shifted out, the result is *this. This avoids
1250 // issues with shifting by the size of the integer type, which produces
1251 // undefined results in the code below. This is also an optimization.
1255 // Create some space for the result.
1256 uint64_t * val = new uint64_t[getNumWords()];
1258 // If we are shifting less than a word, compute the shift with a simple carry
1259 if (shiftAmt < APINT_BITS_PER_WORD) {
1260 lshrNear(val, pVal, getNumWords(), shiftAmt);
1261 return APInt(val, BitWidth).clearUnusedBits();
1264 // Compute some values needed by the remaining shift algorithms
1265 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1266 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1268 // If we are shifting whole words, just move whole words
1269 if (wordShift == 0) {
1270 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1271 val[i] = pVal[i+offset];
1272 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1274 return APInt(val,BitWidth).clearUnusedBits();
1277 // Shift the low order words
1278 unsigned breakWord = getNumWords() - offset -1;
1279 for (unsigned i = 0; i < breakWord; ++i)
1280 val[i] = (pVal[i+offset] >> wordShift) |
1281 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1282 // Shift the break word.
1283 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1285 // Remaining words are 0
1286 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1288 return APInt(val, BitWidth).clearUnusedBits();
1291 /// Left-shift this APInt by shiftAmt.
1292 /// @brief Left-shift function.
1293 APInt APInt::shl(const APInt &shiftAmt) const {
1294 // It's undefined behavior in C to shift by BitWidth or greater.
1295 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1298 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1299 // If all the bits were shifted out, the result is 0. This avoids issues
1300 // with shifting by the size of the integer type, which produces undefined
1301 // results. We define these "undefined results" to always be 0.
1302 if (shiftAmt == BitWidth)
1303 return APInt(BitWidth, 0);
1305 // If none of the bits are shifted out, the result is *this. This avoids a
1306 // lshr by the words size in the loop below which can produce incorrect
1307 // results. It also avoids the expensive computation below for a common case.
1311 // Create some space for the result.
1312 uint64_t * val = new uint64_t[getNumWords()];
1314 // If we are shifting less than a word, do it the easy way
1315 if (shiftAmt < APINT_BITS_PER_WORD) {
1317 for (unsigned i = 0; i < getNumWords(); i++) {
1318 val[i] = pVal[i] << shiftAmt | carry;
1319 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1321 return APInt(val, BitWidth).clearUnusedBits();
1324 // Compute some values needed by the remaining shift algorithms
1325 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1326 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1328 // If we are shifting whole words, just move whole words
1329 if (wordShift == 0) {
1330 for (unsigned i = 0; i < offset; i++)
1332 for (unsigned i = offset; i < getNumWords(); i++)
1333 val[i] = pVal[i-offset];
1334 return APInt(val,BitWidth).clearUnusedBits();
1337 // Copy whole words from this to Result.
1338 unsigned i = getNumWords() - 1;
1339 for (; i > offset; --i)
1340 val[i] = pVal[i-offset] << wordShift |
1341 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1342 val[offset] = pVal[0] << wordShift;
1343 for (i = 0; i < offset; ++i)
1345 return APInt(val, BitWidth).clearUnusedBits();
1348 APInt APInt::rotl(const APInt &rotateAmt) const {
1349 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1352 APInt APInt::rotl(unsigned rotateAmt) const {
1353 rotateAmt %= BitWidth;
1356 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1359 APInt APInt::rotr(const APInt &rotateAmt) const {
1360 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1363 APInt APInt::rotr(unsigned rotateAmt) const {
1364 rotateAmt %= BitWidth;
1367 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1370 // Square Root - this method computes and returns the square root of "this".
1371 // Three mechanisms are used for computation. For small values (<= 5 bits),
1372 // a table lookup is done. This gets some performance for common cases. For
1373 // values using less than 52 bits, the value is converted to double and then
1374 // the libc sqrt function is called. The result is rounded and then converted
1375 // back to a uint64_t which is then used to construct the result. Finally,
1376 // the Babylonian method for computing square roots is used.
1377 APInt APInt::sqrt() const {
1379 // Determine the magnitude of the value.
1380 unsigned magnitude = getActiveBits();
1382 // Use a fast table for some small values. This also gets rid of some
1383 // rounding errors in libc sqrt for small values.
1384 if (magnitude <= 5) {
1385 static const uint8_t results[32] = {
1388 /* 3- 6 */ 2, 2, 2, 2,
1389 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1390 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1391 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1394 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1397 // If the magnitude of the value fits in less than 52 bits (the precision of
1398 // an IEEE double precision floating point value), then we can use the
1399 // libc sqrt function which will probably use a hardware sqrt computation.
1400 // This should be faster than the algorithm below.
1401 if (magnitude < 52) {
1403 return APInt(BitWidth,
1404 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1406 return APInt(BitWidth,
1407 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1411 // Okay, all the short cuts are exhausted. We must compute it. The following
1412 // is a classical Babylonian method for computing the square root. This code
1413 // was adapted to APINt from a wikipedia article on such computations.
1414 // See http://www.wikipedia.org/ and go to the page named
1415 // Calculate_an_integer_square_root.
1416 unsigned nbits = BitWidth, i = 4;
1417 APInt testy(BitWidth, 16);
1418 APInt x_old(BitWidth, 1);
1419 APInt x_new(BitWidth, 0);
1420 APInt two(BitWidth, 2);
1422 // Select a good starting value using binary logarithms.
1423 for (;; i += 2, testy = testy.shl(2))
1424 if (i >= nbits || this->ule(testy)) {
1425 x_old = x_old.shl(i / 2);
1429 // Use the Babylonian method to arrive at the integer square root:
1431 x_new = (this->udiv(x_old) + x_old).udiv(two);
1432 if (x_old.ule(x_new))
1437 // Make sure we return the closest approximation
1438 // NOTE: The rounding calculation below is correct. It will produce an
1439 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1440 // determined to be a rounding issue with pari/gp as it begins to use a
1441 // floating point representation after 192 bits. There are no discrepancies
1442 // between this algorithm and pari/gp for bit widths < 192 bits.
1443 APInt square(x_old * x_old);
1444 APInt nextSquare((x_old + 1) * (x_old +1));
1445 if (this->ult(square))
1447 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1448 APInt midpoint((nextSquare - square).udiv(two));
1449 APInt offset(*this - square);
1450 if (offset.ult(midpoint))
1455 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1456 /// iterative extended Euclidean algorithm is used to solve for this value,
1457 /// however we simplify it to speed up calculating only the inverse, and take
1458 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1459 /// (potentially large) APInts around.
1460 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1461 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1463 // Using the properties listed at the following web page (accessed 06/21/08):
1464 // http://www.numbertheory.org/php/euclid.html
1465 // (especially the properties numbered 3, 4 and 9) it can be proved that
1466 // BitWidth bits suffice for all the computations in the algorithm implemented
1467 // below. More precisely, this number of bits suffice if the multiplicative
1468 // inverse exists, but may not suffice for the general extended Euclidean
1471 APInt r[2] = { modulo, *this };
1472 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1473 APInt q(BitWidth, 0);
1476 for (i = 0; r[i^1] != 0; i ^= 1) {
1477 // An overview of the math without the confusing bit-flipping:
1478 // q = r[i-2] / r[i-1]
1479 // r[i] = r[i-2] % r[i-1]
1480 // t[i] = t[i-2] - t[i-1] * q
1481 udivrem(r[i], r[i^1], q, r[i]);
1485 // If this APInt and the modulo are not coprime, there is no multiplicative
1486 // inverse, so return 0. We check this by looking at the next-to-last
1487 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1490 return APInt(BitWidth, 0);
1492 // The next-to-last t is the multiplicative inverse. However, we are
1493 // interested in a positive inverse. Calcuate a positive one from a negative
1494 // one if necessary. A simple addition of the modulo suffices because
1495 // abs(t[i]) is known to be less than *this/2 (see the link above).
1496 return t[i].isNegative() ? t[i] + modulo : t[i];
1499 /// Calculate the magic numbers required to implement a signed integer division
1500 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1501 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1502 /// Warren, Jr., chapter 10.
1503 APInt::ms APInt::magic() const {
1504 const APInt& d = *this;
1506 APInt ad, anc, delta, q1, r1, q2, r2, t;
1507 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1511 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1512 anc = t - 1 - t.urem(ad); // absolute value of nc
1513 p = d.getBitWidth() - 1; // initialize p
1514 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1515 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1516 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1517 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1520 q1 = q1<<1; // update q1 = 2p/abs(nc)
1521 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1522 if (r1.uge(anc)) { // must be unsigned comparison
1526 q2 = q2<<1; // update q2 = 2p/abs(d)
1527 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1528 if (r2.uge(ad)) { // must be unsigned comparison
1533 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1536 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1537 mag.s = p - d.getBitWidth(); // resulting shift
1541 /// Calculate the magic numbers required to implement an unsigned integer
1542 /// division by a constant as a sequence of multiplies, adds and shifts.
1543 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1544 /// S. Warren, Jr., chapter 10.
1545 /// LeadingZeros can be used to simplify the calculation if the upper bits
1546 /// of the divided value are known zero.
1547 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1548 const APInt& d = *this;
1550 APInt nc, delta, q1, r1, q2, r2;
1552 magu.a = 0; // initialize "add" indicator
1553 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1554 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1555 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1557 nc = allOnes - (-d).urem(d);
1558 p = d.getBitWidth() - 1; // initialize p
1559 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1560 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1561 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1562 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1565 if (r1.uge(nc - r1)) {
1566 q1 = q1 + q1 + 1; // update q1
1567 r1 = r1 + r1 - nc; // update r1
1570 q1 = q1+q1; // update q1
1571 r1 = r1+r1; // update r1
1573 if ((r2 + 1).uge(d - r2)) {
1574 if (q2.uge(signedMax)) magu.a = 1;
1575 q2 = q2+q2 + 1; // update q2
1576 r2 = r2+r2 + 1 - d; // update r2
1579 if (q2.uge(signedMin)) magu.a = 1;
1580 q2 = q2+q2; // update q2
1581 r2 = r2+r2 + 1; // update r2
1584 } while (p < d.getBitWidth()*2 &&
1585 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1586 magu.m = q2 + 1; // resulting magic number
1587 magu.s = p - d.getBitWidth(); // resulting shift
1591 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1592 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1593 /// variables here have the same names as in the algorithm. Comments explain
1594 /// the algorithm and any deviation from it.
1595 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1596 unsigned m, unsigned n) {
1597 assert(u && "Must provide dividend");
1598 assert(v && "Must provide divisor");
1599 assert(q && "Must provide quotient");
1600 assert(u != v && u != q && v != q && "Must us different memory");
1601 assert(n>1 && "n must be > 1");
1603 // Knuth uses the value b as the base of the number system. In our case b
1604 // is 2^31 so we just set it to -1u.
1605 uint64_t b = uint64_t(1) << 32;
1608 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1609 DEBUG(dbgs() << "KnuthDiv: original:");
1610 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1611 DEBUG(dbgs() << " by");
1612 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1613 DEBUG(dbgs() << '\n');
1615 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1616 // u and v by d. Note that we have taken Knuth's advice here to use a power
1617 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1618 // 2 allows us to shift instead of multiply and it is easy to determine the
1619 // shift amount from the leading zeros. We are basically normalizing the u
1620 // and v so that its high bits are shifted to the top of v's range without
1621 // overflow. Note that this can require an extra word in u so that u must
1622 // be of length m+n+1.
1623 unsigned shift = CountLeadingZeros_32(v[n-1]);
1624 unsigned v_carry = 0;
1625 unsigned u_carry = 0;
1627 for (unsigned i = 0; i < m+n; ++i) {
1628 unsigned u_tmp = u[i] >> (32 - shift);
1629 u[i] = (u[i] << shift) | u_carry;
1632 for (unsigned i = 0; i < n; ++i) {
1633 unsigned v_tmp = v[i] >> (32 - shift);
1634 v[i] = (v[i] << shift) | v_carry;
1640 DEBUG(dbgs() << "KnuthDiv: normal:");
1641 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1642 DEBUG(dbgs() << " by");
1643 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1644 DEBUG(dbgs() << '\n');
1647 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1650 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1651 // D3. [Calculate q'.].
1652 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1653 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1654 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1655 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1656 // on v[n-2] determines at high speed most of the cases in which the trial
1657 // value qp is one too large, and it eliminates all cases where qp is two
1659 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1660 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1661 uint64_t qp = dividend / v[n-1];
1662 uint64_t rp = dividend % v[n-1];
1663 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1666 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1669 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1671 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1672 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1673 // consists of a simple multiplication by a one-place number, combined with
1676 for (unsigned i = 0; i < n; ++i) {
1677 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1678 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1679 bool borrow = subtrahend > u_tmp;
1680 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1681 << ", subtrahend == " << subtrahend
1682 << ", borrow = " << borrow << '\n');
1684 uint64_t result = u_tmp - subtrahend;
1686 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1687 u[k++] = (unsigned)(result >> 32); // subtract high word
1688 while (borrow && k <= m+n) { // deal with borrow to the left
1694 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1697 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1698 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1699 DEBUG(dbgs() << '\n');
1700 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1701 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1702 // true value plus b**(n+1), namely as the b's complement of
1703 // the true value, and a "borrow" to the left should be remembered.
1706 bool carry = true; // true because b's complement is "complement + 1"
1707 for (unsigned i = 0; i <= m+n; ++i) {
1708 u[i] = ~u[i] + carry; // b's complement
1709 carry = carry && u[i] == 0;
1712 DEBUG(dbgs() << "KnuthDiv: after complement:");
1713 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1714 DEBUG(dbgs() << '\n');
1716 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1717 // negative, go to step D6; otherwise go on to step D7.
1718 q[j] = (unsigned)qp;
1720 // D6. [Add back]. The probability that this step is necessary is very
1721 // small, on the order of only 2/b. Make sure that test data accounts for
1722 // this possibility. Decrease q[j] by 1
1724 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1725 // A carry will occur to the left of u[j+n], and it should be ignored
1726 // since it cancels with the borrow that occurred in D4.
1728 for (unsigned i = 0; i < n; i++) {
1729 unsigned limit = std::min(u[j+i],v[i]);
1730 u[j+i] += v[i] + carry;
1731 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1735 DEBUG(dbgs() << "KnuthDiv: after correction:");
1736 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1737 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1739 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1742 DEBUG(dbgs() << "KnuthDiv: quotient:");
1743 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1744 DEBUG(dbgs() << '\n');
1746 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1747 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1748 // compute the remainder (urem uses this).
1750 // The value d is expressed by the "shift" value above since we avoided
1751 // multiplication by d by using a shift left. So, all we have to do is
1752 // shift right here. In order to mak
1755 DEBUG(dbgs() << "KnuthDiv: remainder:");
1756 for (int i = n-1; i >= 0; i--) {
1757 r[i] = (u[i] >> shift) | carry;
1758 carry = u[i] << (32 - shift);
1759 DEBUG(dbgs() << " " << r[i]);
1762 for (int i = n-1; i >= 0; i--) {
1764 DEBUG(dbgs() << " " << r[i]);
1767 DEBUG(dbgs() << '\n');
1770 DEBUG(dbgs() << '\n');
1774 void APInt::divide(const APInt LHS, unsigned lhsWords,
1775 const APInt &RHS, unsigned rhsWords,
1776 APInt *Quotient, APInt *Remainder)
1778 assert(lhsWords >= rhsWords && "Fractional result");
1780 // First, compose the values into an array of 32-bit words instead of
1781 // 64-bit words. This is a necessity of both the "short division" algorithm
1782 // and the Knuth "classical algorithm" which requires there to be native
1783 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1784 // can't use 64-bit operands here because we don't have native results of
1785 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1786 // work on large-endian machines.
1787 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1788 unsigned n = rhsWords * 2;
1789 unsigned m = (lhsWords * 2) - n;
1791 // Allocate space for the temporary values we need either on the stack, if
1792 // it will fit, or on the heap if it won't.
1793 unsigned SPACE[128];
1798 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1801 Q = &SPACE[(m+n+1) + n];
1803 R = &SPACE[(m+n+1) + n + (m+n)];
1805 U = new unsigned[m + n + 1];
1806 V = new unsigned[n];
1807 Q = new unsigned[m+n];
1809 R = new unsigned[n];
1812 // Initialize the dividend
1813 memset(U, 0, (m+n+1)*sizeof(unsigned));
1814 for (unsigned i = 0; i < lhsWords; ++i) {
1815 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1816 U[i * 2] = (unsigned)(tmp & mask);
1817 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1819 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1821 // Initialize the divisor
1822 memset(V, 0, (n)*sizeof(unsigned));
1823 for (unsigned i = 0; i < rhsWords; ++i) {
1824 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1825 V[i * 2] = (unsigned)(tmp & mask);
1826 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1829 // initialize the quotient and remainder
1830 memset(Q, 0, (m+n) * sizeof(unsigned));
1832 memset(R, 0, n * sizeof(unsigned));
1834 // Now, adjust m and n for the Knuth division. n is the number of words in
1835 // the divisor. m is the number of words by which the dividend exceeds the
1836 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1837 // contain any zero words or the Knuth algorithm fails.
1838 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1842 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1845 // If we're left with only a single word for the divisor, Knuth doesn't work
1846 // so we implement the short division algorithm here. This is much simpler
1847 // and faster because we are certain that we can divide a 64-bit quantity
1848 // by a 32-bit quantity at hardware speed and short division is simply a
1849 // series of such operations. This is just like doing short division but we
1850 // are using base 2^32 instead of base 10.
1851 assert(n != 0 && "Divide by zero?");
1853 unsigned divisor = V[0];
1854 unsigned remainder = 0;
1855 for (int i = m+n-1; i >= 0; i--) {
1856 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1857 if (partial_dividend == 0) {
1860 } else if (partial_dividend < divisor) {
1862 remainder = (unsigned)partial_dividend;
1863 } else if (partial_dividend == divisor) {
1867 Q[i] = (unsigned)(partial_dividend / divisor);
1868 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1874 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1876 KnuthDiv(U, V, Q, R, m, n);
1879 // If the caller wants the quotient
1881 // Set up the Quotient value's memory.
1882 if (Quotient->BitWidth != LHS.BitWidth) {
1883 if (Quotient->isSingleWord())
1886 delete [] Quotient->pVal;
1887 Quotient->BitWidth = LHS.BitWidth;
1888 if (!Quotient->isSingleWord())
1889 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1891 Quotient->clearAllBits();
1893 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1895 if (lhsWords == 1) {
1897 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1898 if (Quotient->isSingleWord())
1899 Quotient->VAL = tmp;
1901 Quotient->pVal[0] = tmp;
1903 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1904 for (unsigned i = 0; i < lhsWords; ++i)
1906 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1910 // If the caller wants the remainder
1912 // Set up the Remainder value's memory.
1913 if (Remainder->BitWidth != RHS.BitWidth) {
1914 if (Remainder->isSingleWord())
1917 delete [] Remainder->pVal;
1918 Remainder->BitWidth = RHS.BitWidth;
1919 if (!Remainder->isSingleWord())
1920 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1922 Remainder->clearAllBits();
1924 // The remainder is in R. Reconstitute the remainder into Remainder's low
1926 if (rhsWords == 1) {
1928 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1929 if (Remainder->isSingleWord())
1930 Remainder->VAL = tmp;
1932 Remainder->pVal[0] = tmp;
1934 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1935 for (unsigned i = 0; i < rhsWords; ++i)
1936 Remainder->pVal[i] =
1937 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1941 // Clean up the memory we allocated.
1942 if (U != &SPACE[0]) {
1950 APInt APInt::udiv(const APInt& RHS) const {
1951 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1953 // First, deal with the easy case
1954 if (isSingleWord()) {
1955 assert(RHS.VAL != 0 && "Divide by zero?");
1956 return APInt(BitWidth, VAL / RHS.VAL);
1959 // Get some facts about the LHS and RHS number of bits and words
1960 unsigned rhsBits = RHS.getActiveBits();
1961 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1962 assert(rhsWords && "Divided by zero???");
1963 unsigned lhsBits = this->getActiveBits();
1964 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1966 // Deal with some degenerate cases
1969 return APInt(BitWidth, 0);
1970 else if (lhsWords < rhsWords || this->ult(RHS)) {
1971 // X / Y ===> 0, iff X < Y
1972 return APInt(BitWidth, 0);
1973 } else if (*this == RHS) {
1975 return APInt(BitWidth, 1);
1976 } else if (lhsWords == 1 && rhsWords == 1) {
1977 // All high words are zero, just use native divide
1978 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1981 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1982 APInt Quotient(1,0); // to hold result.
1983 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1987 APInt APInt::urem(const APInt& RHS) const {
1988 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1989 if (isSingleWord()) {
1990 assert(RHS.VAL != 0 && "Remainder by zero?");
1991 return APInt(BitWidth, VAL % RHS.VAL);
1994 // Get some facts about the LHS
1995 unsigned lhsBits = getActiveBits();
1996 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1998 // Get some facts about the RHS
1999 unsigned rhsBits = RHS.getActiveBits();
2000 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2001 assert(rhsWords && "Performing remainder operation by zero ???");
2003 // Check the degenerate cases
2004 if (lhsWords == 0) {
2006 return APInt(BitWidth, 0);
2007 } else if (lhsWords < rhsWords || this->ult(RHS)) {
2008 // X % Y ===> X, iff X < Y
2010 } else if (*this == RHS) {
2012 return APInt(BitWidth, 0);
2013 } else if (lhsWords == 1) {
2014 // All high words are zero, just use native remainder
2015 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
2018 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2019 APInt Remainder(1,0);
2020 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2024 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2025 APInt &Quotient, APInt &Remainder) {
2026 // Get some size facts about the dividend and divisor
2027 unsigned lhsBits = LHS.getActiveBits();
2028 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2029 unsigned rhsBits = RHS.getActiveBits();
2030 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2032 // Check the degenerate cases
2033 if (lhsWords == 0) {
2034 Quotient = 0; // 0 / Y ===> 0
2035 Remainder = 0; // 0 % Y ===> 0
2039 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2040 Remainder = LHS; // X % Y ===> X, iff X < Y
2041 Quotient = 0; // X / Y ===> 0, iff X < Y
2046 Quotient = 1; // X / X ===> 1
2047 Remainder = 0; // X % X ===> 0;
2051 if (lhsWords == 1 && rhsWords == 1) {
2052 // There is only one word to consider so use the native versions.
2053 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2054 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2055 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2056 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2060 // Okay, lets do it the long way
2061 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2064 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2065 APInt Res = *this+RHS;
2066 Overflow = isNonNegative() == RHS.isNonNegative() &&
2067 Res.isNonNegative() != isNonNegative();
2071 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2072 APInt Res = *this+RHS;
2073 Overflow = Res.ult(RHS);
2077 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2078 APInt Res = *this - RHS;
2079 Overflow = isNonNegative() != RHS.isNonNegative() &&
2080 Res.isNonNegative() != isNonNegative();
2084 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2085 APInt Res = *this-RHS;
2086 Overflow = Res.ugt(*this);
2090 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2091 // MININT/-1 --> overflow.
2092 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2096 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2097 APInt Res = *this * RHS;
2099 if (*this != 0 && RHS != 0)
2100 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2106 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2107 APInt Res = *this * RHS;
2109 if (*this != 0 && RHS != 0)
2110 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2116 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2117 Overflow = ShAmt >= getBitWidth();
2119 ShAmt = getBitWidth()-1;
2121 if (isNonNegative()) // Don't allow sign change.
2122 Overflow = ShAmt >= countLeadingZeros();
2124 Overflow = ShAmt >= countLeadingOnes();
2126 return *this << ShAmt;
2132 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2133 // Check our assumptions here
2134 assert(!str.empty() && "Invalid string length");
2135 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2137 "Radix should be 2, 8, 10, 16, or 36!");
2139 StringRef::iterator p = str.begin();
2140 size_t slen = str.size();
2141 bool isNeg = *p == '-';
2142 if (*p == '-' || *p == '+') {
2145 assert(slen && "String is only a sign, needs a value.");
2147 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2148 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2149 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2150 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2151 "Insufficient bit width");
2154 if (!isSingleWord())
2155 pVal = getClearedMemory(getNumWords());
2157 // Figure out if we can shift instead of multiply
2158 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2160 // Set up an APInt for the digit to add outside the loop so we don't
2161 // constantly construct/destruct it.
2162 APInt apdigit(getBitWidth(), 0);
2163 APInt apradix(getBitWidth(), radix);
2165 // Enter digit traversal loop
2166 for (StringRef::iterator e = str.end(); p != e; ++p) {
2167 unsigned digit = getDigit(*p, radix);
2168 assert(digit < radix && "Invalid character in digit string");
2170 // Shift or multiply the value by the radix
2178 // Add in the digit we just interpreted
2179 if (apdigit.isSingleWord())
2180 apdigit.VAL = digit;
2182 apdigit.pVal[0] = digit;
2185 // If its negative, put it in two's complement form
2188 this->flipAllBits();
2192 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2193 bool Signed, bool formatAsCLiteral) const {
2194 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2196 "Radix should be 2, 8, 10, 16, or 36!");
2198 const char *Prefix = "";
2199 if (formatAsCLiteral) {
2202 // Binary literals are a non-standard extension added in gcc 4.3:
2203 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2215 llvm_unreachable("Invalid radix!");
2219 // First, check for a zero value and just short circuit the logic below.
2222 Str.push_back(*Prefix);
2229 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2231 if (isSingleWord()) {
2233 char *BufPtr = Buffer+65;
2239 int64_t I = getSExtValue();
2249 Str.push_back(*Prefix);
2254 *--BufPtr = Digits[N % Radix];
2257 Str.append(BufPtr, Buffer+65);
2263 if (Signed && isNegative()) {
2264 // They want to print the signed version and it is a negative value
2265 // Flip the bits and add one to turn it into the equivalent positive
2266 // value and put a '-' in the result.
2273 Str.push_back(*Prefix);
2277 // We insert the digits backward, then reverse them to get the right order.
2278 unsigned StartDig = Str.size();
2280 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2281 // because the number of bits per digit (1, 3 and 4 respectively) divides
2282 // equaly. We just shift until the value is zero.
2283 if (Radix == 2 || Radix == 8 || Radix == 16) {
2284 // Just shift tmp right for each digit width until it becomes zero
2285 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2286 unsigned MaskAmt = Radix - 1;
2289 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2290 Str.push_back(Digits[Digit]);
2291 Tmp = Tmp.lshr(ShiftAmt);
2294 APInt divisor(Radix == 10? 4 : 8, Radix);
2296 APInt APdigit(1, 0);
2297 APInt tmp2(Tmp.getBitWidth(), 0);
2298 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2300 unsigned Digit = (unsigned)APdigit.getZExtValue();
2301 assert(Digit < Radix && "divide failed");
2302 Str.push_back(Digits[Digit]);
2307 // Reverse the digits before returning.
2308 std::reverse(Str.begin()+StartDig, Str.end());
2311 /// toString - This returns the APInt as a std::string. Note that this is an
2312 /// inefficient method. It is better to pass in a SmallVector/SmallString
2313 /// to the methods above.
2314 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2316 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2321 void APInt::dump() const {
2322 SmallString<40> S, U;
2323 this->toStringUnsigned(U);
2324 this->toStringSigned(S);
2325 dbgs() << "APInt(" << BitWidth << "b, "
2326 << U.str() << "u " << S.str() << "s)";
2329 void APInt::print(raw_ostream &OS, bool isSigned) const {
2331 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2335 // This implements a variety of operations on a representation of
2336 // arbitrary precision, two's-complement, bignum integer values.
2338 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2339 // and unrestricting assumption.
2340 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2341 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2343 /* Some handy functions local to this file. */
2346 /* Returns the integer part with the least significant BITS set.
2347 BITS cannot be zero. */
2348 static inline integerPart
2349 lowBitMask(unsigned int bits)
2351 assert(bits != 0 && bits <= integerPartWidth);
2353 return ~(integerPart) 0 >> (integerPartWidth - bits);
2356 /* Returns the value of the lower half of PART. */
2357 static inline integerPart
2358 lowHalf(integerPart part)
2360 return part & lowBitMask(integerPartWidth / 2);
2363 /* Returns the value of the upper half of PART. */
2364 static inline integerPart
2365 highHalf(integerPart part)
2367 return part >> (integerPartWidth / 2);
2370 /* Returns the bit number of the most significant set bit of a part.
2371 If the input number has no bits set -1U is returned. */
2373 partMSB(integerPart value)
2375 unsigned int n, msb;
2380 n = integerPartWidth / 2;
2395 /* Returns the bit number of the least significant set bit of a
2396 part. If the input number has no bits set -1U is returned. */
2398 partLSB(integerPart value)
2400 unsigned int n, lsb;
2405 lsb = integerPartWidth - 1;
2406 n = integerPartWidth / 2;
2421 /* Sets the least significant part of a bignum to the input value, and
2422 zeroes out higher parts. */
2424 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2431 for (i = 1; i < parts; i++)
2435 /* Assign one bignum to another. */
2437 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2441 for (i = 0; i < parts; i++)
2445 /* Returns true if a bignum is zero, false otherwise. */
2447 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2451 for (i = 0; i < parts; i++)
2458 /* Extract the given bit of a bignum; returns 0 or 1. */
2460 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2462 return (parts[bit / integerPartWidth] &
2463 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2466 /* Set the given bit of a bignum. */
2468 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2470 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2473 /* Clears the given bit of a bignum. */
2475 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2477 parts[bit / integerPartWidth] &=
2478 ~((integerPart) 1 << (bit % integerPartWidth));
2481 /* Returns the bit number of the least significant set bit of a
2482 number. If the input number has no bits set -1U is returned. */
2484 APInt::tcLSB(const integerPart *parts, unsigned int n)
2486 unsigned int i, lsb;
2488 for (i = 0; i < n; i++) {
2489 if (parts[i] != 0) {
2490 lsb = partLSB(parts[i]);
2492 return lsb + i * integerPartWidth;
2499 /* Returns the bit number of the most significant set bit of a number.
2500 If the input number has no bits set -1U is returned. */
2502 APInt::tcMSB(const integerPart *parts, unsigned int n)
2509 if (parts[n] != 0) {
2510 msb = partMSB(parts[n]);
2512 return msb + n * integerPartWidth;
2519 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2520 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2521 the least significant bit of DST. All high bits above srcBITS in
2522 DST are zero-filled. */
2524 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2525 unsigned int srcBits, unsigned int srcLSB)
2527 unsigned int firstSrcPart, dstParts, shift, n;
2529 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2530 assert(dstParts <= dstCount);
2532 firstSrcPart = srcLSB / integerPartWidth;
2533 tcAssign (dst, src + firstSrcPart, dstParts);
2535 shift = srcLSB % integerPartWidth;
2536 tcShiftRight (dst, dstParts, shift);
2538 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2539 in DST. If this is less that srcBits, append the rest, else
2540 clear the high bits. */
2541 n = dstParts * integerPartWidth - shift;
2543 integerPart mask = lowBitMask (srcBits - n);
2544 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2545 << n % integerPartWidth);
2546 } else if (n > srcBits) {
2547 if (srcBits % integerPartWidth)
2548 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2551 /* Clear high parts. */
2552 while (dstParts < dstCount)
2553 dst[dstParts++] = 0;
2556 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2558 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2559 integerPart c, unsigned int parts)
2565 for (i = 0; i < parts; i++) {
2570 dst[i] += rhs[i] + 1;
2581 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2583 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2584 integerPart c, unsigned int parts)
2590 for (i = 0; i < parts; i++) {
2595 dst[i] -= rhs[i] + 1;
2606 /* Negate a bignum in-place. */
2608 APInt::tcNegate(integerPart *dst, unsigned int parts)
2610 tcComplement(dst, parts);
2611 tcIncrement(dst, parts);
2614 /* DST += SRC * MULTIPLIER + CARRY if add is true
2615 DST = SRC * MULTIPLIER + CARRY if add is false
2617 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2618 they must start at the same point, i.e. DST == SRC.
2620 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2621 returned. Otherwise DST is filled with the least significant
2622 DSTPARTS parts of the result, and if all of the omitted higher
2623 parts were zero return zero, otherwise overflow occurred and
2626 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2627 integerPart multiplier, integerPart carry,
2628 unsigned int srcParts, unsigned int dstParts,
2633 /* Otherwise our writes of DST kill our later reads of SRC. */
2634 assert(dst <= src || dst >= src + srcParts);
2635 assert(dstParts <= srcParts + 1);
2637 /* N loops; minimum of dstParts and srcParts. */
2638 n = dstParts < srcParts ? dstParts: srcParts;
2640 for (i = 0; i < n; i++) {
2641 integerPart low, mid, high, srcPart;
2643 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2645 This cannot overflow, because
2647 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2649 which is less than n^2. */
2653 if (multiplier == 0 || srcPart == 0) {
2657 low = lowHalf(srcPart) * lowHalf(multiplier);
2658 high = highHalf(srcPart) * highHalf(multiplier);
2660 mid = lowHalf(srcPart) * highHalf(multiplier);
2661 high += highHalf(mid);
2662 mid <<= integerPartWidth / 2;
2663 if (low + mid < low)
2667 mid = highHalf(srcPart) * lowHalf(multiplier);
2668 high += highHalf(mid);
2669 mid <<= integerPartWidth / 2;
2670 if (low + mid < low)
2674 /* Now add carry. */
2675 if (low + carry < low)
2681 /* And now DST[i], and store the new low part there. */
2682 if (low + dst[i] < low)
2692 /* Full multiplication, there is no overflow. */
2693 assert(i + 1 == dstParts);
2697 /* We overflowed if there is carry. */
2701 /* We would overflow if any significant unwritten parts would be
2702 non-zero. This is true if any remaining src parts are non-zero
2703 and the multiplier is non-zero. */
2705 for (; i < srcParts; i++)
2709 /* We fitted in the narrow destination. */
2714 /* DST = LHS * RHS, where DST has the same width as the operands and
2715 is filled with the least significant parts of the result. Returns
2716 one if overflow occurred, otherwise zero. DST must be disjoint
2717 from both operands. */
2719 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2720 const integerPart *rhs, unsigned int parts)
2725 assert(dst != lhs && dst != rhs);
2728 tcSet(dst, 0, parts);
2730 for (i = 0; i < parts; i++)
2731 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2737 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2738 operands. No overflow occurs. DST must be disjoint from both
2739 operands. Returns the number of parts required to hold the
2742 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2743 const integerPart *rhs, unsigned int lhsParts,
2744 unsigned int rhsParts)
2746 /* Put the narrower number on the LHS for less loops below. */
2747 if (lhsParts > rhsParts) {
2748 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2752 assert(dst != lhs && dst != rhs);
2754 tcSet(dst, 0, rhsParts);
2756 for (n = 0; n < lhsParts; n++)
2757 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2759 n = lhsParts + rhsParts;
2761 return n - (dst[n - 1] == 0);
2765 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2766 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2767 set REMAINDER to the remainder, return zero. i.e.
2769 OLD_LHS = RHS * LHS + REMAINDER
2771 SCRATCH is a bignum of the same size as the operands and result for
2772 use by the routine; its contents need not be initialized and are
2773 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2776 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2777 integerPart *remainder, integerPart *srhs,
2780 unsigned int n, shiftCount;
2783 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2785 shiftCount = tcMSB(rhs, parts) + 1;
2786 if (shiftCount == 0)
2789 shiftCount = parts * integerPartWidth - shiftCount;
2790 n = shiftCount / integerPartWidth;
2791 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2793 tcAssign(srhs, rhs, parts);
2794 tcShiftLeft(srhs, parts, shiftCount);
2795 tcAssign(remainder, lhs, parts);
2796 tcSet(lhs, 0, parts);
2798 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2803 compare = tcCompare(remainder, srhs, parts);
2805 tcSubtract(remainder, srhs, 0, parts);
2809 if (shiftCount == 0)
2812 tcShiftRight(srhs, parts, 1);
2813 if ((mask >>= 1) == 0)
2814 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2820 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2821 There are no restrictions on COUNT. */
2823 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2826 unsigned int jump, shift;
2828 /* Jump is the inter-part jump; shift is is intra-part shift. */
2829 jump = count / integerPartWidth;
2830 shift = count % integerPartWidth;
2832 while (parts > jump) {
2837 /* dst[i] comes from the two parts src[i - jump] and, if we have
2838 an intra-part shift, src[i - jump - 1]. */
2839 part = dst[parts - jump];
2842 if (parts >= jump + 1)
2843 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2854 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2855 zero. There are no restrictions on COUNT. */
2857 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2860 unsigned int i, jump, shift;
2862 /* Jump is the inter-part jump; shift is is intra-part shift. */
2863 jump = count / integerPartWidth;
2864 shift = count % integerPartWidth;
2866 /* Perform the shift. This leaves the most significant COUNT bits
2867 of the result at zero. */
2868 for (i = 0; i < parts; i++) {
2871 if (i + jump >= parts) {
2874 part = dst[i + jump];
2877 if (i + jump + 1 < parts)
2878 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2887 /* Bitwise and of two bignums. */
2889 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2893 for (i = 0; i < parts; i++)
2897 /* Bitwise inclusive or of two bignums. */
2899 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2903 for (i = 0; i < parts; i++)
2907 /* Bitwise exclusive or of two bignums. */
2909 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2913 for (i = 0; i < parts; i++)
2917 /* Complement a bignum in-place. */
2919 APInt::tcComplement(integerPart *dst, unsigned int parts)
2923 for (i = 0; i < parts; i++)
2927 /* Comparison (unsigned) of two bignums. */
2929 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2934 if (lhs[parts] == rhs[parts])
2937 if (lhs[parts] > rhs[parts])
2946 /* Increment a bignum in-place, return the carry flag. */
2948 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2952 for (i = 0; i < parts; i++)
2959 /* Set the least significant BITS bits of a bignum, clear the
2962 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2968 while (bits > integerPartWidth) {
2969 dst[i++] = ~(integerPart) 0;
2970 bits -= integerPartWidth;
2974 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);