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);
390 // delete dest array and return
395 APInt& APInt::operator&=(const APInt& RHS) {
396 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
397 if (isSingleWord()) {
401 unsigned numWords = getNumWords();
402 for (unsigned i = 0; i < numWords; ++i)
403 pVal[i] &= RHS.pVal[i];
407 APInt& APInt::operator|=(const APInt& RHS) {
408 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
409 if (isSingleWord()) {
413 unsigned numWords = getNumWords();
414 for (unsigned i = 0; i < numWords; ++i)
415 pVal[i] |= RHS.pVal[i];
419 APInt& APInt::operator^=(const APInt& RHS) {
420 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
421 if (isSingleWord()) {
423 this->clearUnusedBits();
426 unsigned numWords = getNumWords();
427 for (unsigned i = 0; i < numWords; ++i)
428 pVal[i] ^= RHS.pVal[i];
429 return clearUnusedBits();
432 APInt APInt::AndSlowCase(const APInt& RHS) const {
433 unsigned numWords = getNumWords();
434 uint64_t* val = getMemory(numWords);
435 for (unsigned i = 0; i < numWords; ++i)
436 val[i] = pVal[i] & RHS.pVal[i];
437 return APInt(val, getBitWidth());
440 APInt APInt::OrSlowCase(const APInt& RHS) const {
441 unsigned numWords = getNumWords();
442 uint64_t *val = getMemory(numWords);
443 for (unsigned i = 0; i < numWords; ++i)
444 val[i] = pVal[i] | RHS.pVal[i];
445 return APInt(val, getBitWidth());
448 APInt APInt::XorSlowCase(const APInt& RHS) const {
449 unsigned numWords = getNumWords();
450 uint64_t *val = getMemory(numWords);
451 for (unsigned i = 0; i < numWords; ++i)
452 val[i] = pVal[i] ^ RHS.pVal[i];
454 // 0^0==1 so clear the high bits in case they got set.
455 return APInt(val, getBitWidth()).clearUnusedBits();
458 bool APInt::operator !() const {
462 for (unsigned i = 0; i < getNumWords(); ++i)
468 APInt APInt::operator*(const APInt& RHS) const {
469 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
471 return APInt(BitWidth, VAL * RHS.VAL);
474 return Result.clearUnusedBits();
477 APInt APInt::operator+(const APInt& RHS) const {
478 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
480 return APInt(BitWidth, VAL + RHS.VAL);
481 APInt Result(BitWidth, 0);
482 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
483 return Result.clearUnusedBits();
486 APInt APInt::operator-(const APInt& RHS) const {
487 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
489 return APInt(BitWidth, VAL - RHS.VAL);
490 APInt Result(BitWidth, 0);
491 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
492 return Result.clearUnusedBits();
495 bool APInt::operator[](unsigned bitPosition) const {
496 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
497 return (maskBit(bitPosition) &
498 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
501 bool APInt::EqualSlowCase(const APInt& RHS) const {
502 // Get some facts about the number of bits used in the two operands.
503 unsigned n1 = getActiveBits();
504 unsigned n2 = RHS.getActiveBits();
506 // If the number of bits isn't the same, they aren't equal
510 // If the number of bits fits in a word, we only need to compare the low word.
511 if (n1 <= APINT_BITS_PER_WORD)
512 return pVal[0] == RHS.pVal[0];
514 // Otherwise, compare everything
515 for (int i = whichWord(n1 - 1); i >= 0; --i)
516 if (pVal[i] != RHS.pVal[i])
521 bool APInt::EqualSlowCase(uint64_t Val) const {
522 unsigned n = getActiveBits();
523 if (n <= APINT_BITS_PER_WORD)
524 return pVal[0] == Val;
529 bool APInt::ult(const APInt& RHS) const {
530 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
532 return VAL < RHS.VAL;
534 // Get active bit length of both operands
535 unsigned n1 = getActiveBits();
536 unsigned n2 = RHS.getActiveBits();
538 // If magnitude of LHS is less than RHS, return true.
542 // If magnitude of RHS is greather than LHS, return false.
546 // If they bot fit in a word, just compare the low order word
547 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
548 return pVal[0] < RHS.pVal[0];
550 // Otherwise, compare all words
551 unsigned topWord = whichWord(std::max(n1,n2)-1);
552 for (int i = topWord; i >= 0; --i) {
553 if (pVal[i] > RHS.pVal[i])
555 if (pVal[i] < RHS.pVal[i])
561 bool APInt::slt(const APInt& RHS) const {
562 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
563 if (isSingleWord()) {
564 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
565 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
566 return lhsSext < rhsSext;
571 bool lhsNeg = isNegative();
572 bool rhsNeg = rhs.isNegative();
574 // Sign bit is set so perform two's complement to make it positive
579 // Sign bit is set so perform two's complement to make it positive
584 // Now we have unsigned values to compare so do the comparison if necessary
585 // based on the negativeness of the values.
597 void APInt::setBit(unsigned bitPosition) {
599 VAL |= maskBit(bitPosition);
601 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
604 /// Set the given bit to 0 whose position is given as "bitPosition".
605 /// @brief Set a given bit to 0.
606 void APInt::clearBit(unsigned bitPosition) {
608 VAL &= ~maskBit(bitPosition);
610 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
613 /// @brief Toggle every bit to its opposite value.
615 /// Toggle a given bit to its opposite value whose position is given
616 /// as "bitPosition".
617 /// @brief Toggles a given bit to its opposite value.
618 void APInt::flipBit(unsigned bitPosition) {
619 assert(bitPosition < BitWidth && "Out of the bit-width range!");
620 if ((*this)[bitPosition]) clearBit(bitPosition);
621 else setBit(bitPosition);
624 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
625 assert(!str.empty() && "Invalid string length");
626 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
628 "Radix should be 2, 8, 10, 16, or 36!");
630 size_t slen = str.size();
632 // Each computation below needs to know if it's negative.
633 StringRef::iterator p = str.begin();
634 unsigned isNegative = *p == '-';
635 if (*p == '-' || *p == '+') {
638 assert(slen && "String is only a sign, needs a value.");
641 // For radixes of power-of-two values, the bits required is accurately and
644 return slen + isNegative;
646 return slen * 3 + isNegative;
648 return slen * 4 + isNegative;
652 // This is grossly inefficient but accurate. We could probably do something
653 // with a computation of roughly slen*64/20 and then adjust by the value of
654 // the first few digits. But, I'm not sure how accurate that could be.
656 // Compute a sufficient number of bits that is always large enough but might
657 // be too large. This avoids the assertion in the constructor. This
658 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
659 // bits in that case.
661 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
662 : (slen == 1 ? 7 : slen * 16/3);
664 // Convert to the actual binary value.
665 APInt tmp(sufficient, StringRef(p, slen), radix);
667 // Compute how many bits are required. If the log is infinite, assume we need
669 unsigned log = tmp.logBase2();
670 if (log == (unsigned)-1) {
671 return isNegative + 1;
673 return isNegative + log + 1;
677 // From http://www.burtleburtle.net, byBob Jenkins.
678 // When targeting x86, both GCC and LLVM seem to recognize this as a
679 // rotate instruction.
680 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
682 // From http://www.burtleburtle.net, by Bob Jenkins.
685 a -= c; a ^= rot(c, 4); c += b; \
686 b -= a; b ^= rot(a, 6); a += c; \
687 c -= b; c ^= rot(b, 8); b += a; \
688 a -= c; a ^= rot(c,16); c += b; \
689 b -= a; b ^= rot(a,19); a += c; \
690 c -= b; c ^= rot(b, 4); b += a; \
693 // From http://www.burtleburtle.net, by Bob Jenkins.
694 #define final(a,b,c) \
696 c ^= b; c -= rot(b,14); \
697 a ^= c; a -= rot(c,11); \
698 b ^= a; b -= rot(a,25); \
699 c ^= b; c -= rot(b,16); \
700 a ^= c; a -= rot(c,4); \
701 b ^= a; b -= rot(a,14); \
702 c ^= b; c -= rot(b,24); \
705 // hashword() was adapted from http://www.burtleburtle.net, by Bob
706 // Jenkins. k is a pointer to an array of uint32_t values; length is
707 // the length of the key, in 32-bit chunks. This version only handles
708 // keys that are a multiple of 32 bits in size.
709 static inline uint32_t hashword(const uint64_t *k64, size_t length)
711 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
714 /* Set up the internal state */
715 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
717 /*------------------------------------------------- handle most of the key */
727 /*------------------------------------------- handle the last 3 uint32_t's */
728 switch (length) { /* all the case statements fall through */
733 case 0: /* case 0: nothing left to add */
736 /*------------------------------------------------------ report the result */
740 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
741 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
742 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
743 // function into about 35 instructions when inlined.
744 static inline uint32_t hashword8(const uint64_t k64)
747 a = b = c = 0xdeadbeef + 4;
749 a += k64 & 0xffffffff;
757 uint64_t APInt::getHashValue() const {
760 hash = hashword8(VAL);
762 hash = hashword(pVal, getNumWords()*2);
766 /// HiBits - This function returns the high "numBits" bits of this APInt.
767 APInt APInt::getHiBits(unsigned numBits) const {
768 return APIntOps::lshr(*this, BitWidth - numBits);
771 /// LoBits - This function returns the low "numBits" bits of this APInt.
772 APInt APInt::getLoBits(unsigned numBits) const {
773 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
777 unsigned APInt::countLeadingZerosSlowCase() const {
778 // Treat the most significand word differently because it might have
779 // meaningless bits set beyond the precision.
780 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
782 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
784 MSWMask = ~integerPart(0);
785 BitsInMSW = APINT_BITS_PER_WORD;
788 unsigned i = getNumWords();
789 integerPart MSW = pVal[i-1] & MSWMask;
791 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
793 unsigned Count = BitsInMSW;
794 for (--i; i > 0u; --i) {
796 Count += APINT_BITS_PER_WORD;
798 Count += CountLeadingZeros_64(pVal[i-1]);
805 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
809 while (V && (V & (1ULL << 63))) {
816 unsigned APInt::countLeadingOnes() const {
818 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
820 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
823 highWordBits = APINT_BITS_PER_WORD;
826 shift = APINT_BITS_PER_WORD - highWordBits;
828 int i = getNumWords() - 1;
829 unsigned Count = countLeadingOnes_64(pVal[i], shift);
830 if (Count == highWordBits) {
831 for (i--; i >= 0; --i) {
832 if (pVal[i] == -1ULL)
833 Count += APINT_BITS_PER_WORD;
835 Count += countLeadingOnes_64(pVal[i], 0);
843 unsigned APInt::countTrailingZeros() const {
845 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
848 for (; i < getNumWords() && pVal[i] == 0; ++i)
849 Count += APINT_BITS_PER_WORD;
850 if (i < getNumWords())
851 Count += CountTrailingZeros_64(pVal[i]);
852 return std::min(Count, BitWidth);
855 unsigned APInt::countTrailingOnesSlowCase() const {
858 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
859 Count += APINT_BITS_PER_WORD;
860 if (i < getNumWords())
861 Count += CountTrailingOnes_64(pVal[i]);
862 return std::min(Count, BitWidth);
865 unsigned APInt::countPopulationSlowCase() const {
867 for (unsigned i = 0; i < getNumWords(); ++i)
868 Count += CountPopulation_64(pVal[i]);
872 APInt APInt::byteSwap() const {
873 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
875 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
876 else if (BitWidth == 32)
877 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
878 else if (BitWidth == 48) {
879 unsigned Tmp1 = unsigned(VAL >> 16);
880 Tmp1 = ByteSwap_32(Tmp1);
881 uint16_t Tmp2 = uint16_t(VAL);
882 Tmp2 = ByteSwap_16(Tmp2);
883 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
884 } else if (BitWidth == 64)
885 return APInt(BitWidth, ByteSwap_64(VAL));
887 APInt Result(BitWidth, 0);
888 char *pByte = (char*)Result.pVal;
889 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
891 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
892 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
898 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
900 APInt A = API1, B = API2;
903 B = APIntOps::urem(A, B);
909 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
916 // Get the sign bit from the highest order bit
917 bool isNeg = T.I >> 63;
919 // Get the 11-bit exponent and adjust for the 1023 bit bias
920 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
922 // If the exponent is negative, the value is < 0 so just return 0.
924 return APInt(width, 0u);
926 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
927 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
929 // If the exponent doesn't shift all bits out of the mantissa
931 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
932 APInt(width, mantissa >> (52 - exp));
934 // If the client didn't provide enough bits for us to shift the mantissa into
935 // then the result is undefined, just return 0
936 if (width <= exp - 52)
937 return APInt(width, 0);
939 // Otherwise, we have to shift the mantissa bits up to the right location
940 APInt Tmp(width, mantissa);
941 Tmp = Tmp.shl((unsigned)exp - 52);
942 return isNeg ? -Tmp : Tmp;
945 /// RoundToDouble - This function converts this APInt to a double.
946 /// The layout for double is as following (IEEE Standard 754):
947 /// --------------------------------------
948 /// | Sign Exponent Fraction Bias |
949 /// |-------------------------------------- |
950 /// | 1[63] 11[62-52] 52[51-00] 1023 |
951 /// --------------------------------------
952 double APInt::roundToDouble(bool isSigned) const {
954 // Handle the simple case where the value is contained in one uint64_t.
955 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
956 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
958 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
961 return double(getWord(0));
964 // Determine if the value is negative.
965 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
967 // Construct the absolute value if we're negative.
968 APInt Tmp(isNeg ? -(*this) : (*this));
970 // Figure out how many bits we're using.
971 unsigned n = Tmp.getActiveBits();
973 // The exponent (without bias normalization) is just the number of bits
974 // we are using. Note that the sign bit is gone since we constructed the
978 // Return infinity for exponent overflow
980 if (!isSigned || !isNeg)
981 return std::numeric_limits<double>::infinity();
983 return -std::numeric_limits<double>::infinity();
985 exp += 1023; // Increment for 1023 bias
987 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
988 // extract the high 52 bits from the correct words in pVal.
990 unsigned hiWord = whichWord(n-1);
992 mantissa = Tmp.pVal[0];
994 mantissa >>= n - 52; // shift down, we want the top 52 bits.
996 assert(hiWord > 0 && "huh?");
997 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
998 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
999 mantissa = hibits | lobits;
1002 // The leading bit of mantissa is implicit, so get rid of it.
1003 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
1008 T.I = sign | (exp << 52) | mantissa;
1012 // Truncate to new width.
1013 APInt APInt::trunc(unsigned width) const {
1014 assert(width < BitWidth && "Invalid APInt Truncate request");
1015 assert(width && "Can't truncate to 0 bits");
1017 if (width <= APINT_BITS_PER_WORD)
1018 return APInt(width, getRawData()[0]);
1020 APInt Result(getMemory(getNumWords(width)), width);
1024 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
1025 Result.pVal[i] = pVal[i];
1027 // Truncate and copy any partial word.
1028 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
1030 Result.pVal[i] = pVal[i] << bits >> bits;
1035 // Sign extend to a new width.
1036 APInt APInt::sext(unsigned width) const {
1037 assert(width > BitWidth && "Invalid APInt SignExtend request");
1039 if (width <= APINT_BITS_PER_WORD) {
1040 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
1041 val = (int64_t)val >> (width - BitWidth);
1042 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
1045 APInt Result(getMemory(getNumWords(width)), width);
1050 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
1051 word = getRawData()[i];
1052 Result.pVal[i] = word;
1055 // Read and sign-extend any partial word.
1056 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
1058 word = (int64_t)getRawData()[i] << bits >> bits;
1060 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1062 // Write remaining full words.
1063 for (; i != width / APINT_BITS_PER_WORD; i++) {
1064 Result.pVal[i] = word;
1065 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1068 // Write any partial word.
1069 bits = (0 - width) % APINT_BITS_PER_WORD;
1071 Result.pVal[i] = word << bits >> bits;
1076 // Zero extend to a new width.
1077 APInt APInt::zext(unsigned width) const {
1078 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1080 if (width <= APINT_BITS_PER_WORD)
1081 return APInt(width, VAL);
1083 APInt Result(getMemory(getNumWords(width)), width);
1087 for (i = 0; i != getNumWords(); i++)
1088 Result.pVal[i] = getRawData()[i];
1090 // Zero remaining words.
1091 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1096 APInt APInt::zextOrTrunc(unsigned width) const {
1097 if (BitWidth < width)
1099 if (BitWidth > width)
1100 return trunc(width);
1104 APInt APInt::sextOrTrunc(unsigned width) const {
1105 if (BitWidth < width)
1107 if (BitWidth > width)
1108 return trunc(width);
1112 /// Arithmetic right-shift this APInt by shiftAmt.
1113 /// @brief Arithmetic right-shift function.
1114 APInt APInt::ashr(const APInt &shiftAmt) const {
1115 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1118 /// Arithmetic right-shift this APInt by shiftAmt.
1119 /// @brief Arithmetic right-shift function.
1120 APInt APInt::ashr(unsigned shiftAmt) const {
1121 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1122 // Handle a degenerate case
1126 // Handle single word shifts with built-in ashr
1127 if (isSingleWord()) {
1128 if (shiftAmt == BitWidth)
1129 return APInt(BitWidth, 0); // undefined
1131 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1132 return APInt(BitWidth,
1133 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1137 // If all the bits were shifted out, the result is, technically, undefined.
1138 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1139 // issues in the algorithm below.
1140 if (shiftAmt == BitWidth) {
1142 return APInt(BitWidth, -1ULL, true);
1144 return APInt(BitWidth, 0);
1147 // Create some space for the result.
1148 uint64_t * val = new uint64_t[getNumWords()];
1150 // Compute some values needed by the following shift algorithms
1151 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1152 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1153 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1154 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1155 if (bitsInWord == 0)
1156 bitsInWord = APINT_BITS_PER_WORD;
1158 // If we are shifting whole words, just move whole words
1159 if (wordShift == 0) {
1160 // Move the words containing significant bits
1161 for (unsigned i = 0; i <= breakWord; ++i)
1162 val[i] = pVal[i+offset]; // move whole word
1164 // Adjust the top significant word for sign bit fill, if negative
1166 if (bitsInWord < APINT_BITS_PER_WORD)
1167 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1169 // Shift the low order words
1170 for (unsigned i = 0; i < breakWord; ++i) {
1171 // This combines the shifted corresponding word with the low bits from
1172 // the next word (shifted into this word's high bits).
1173 val[i] = (pVal[i+offset] >> wordShift) |
1174 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1177 // Shift the break word. In this case there are no bits from the next word
1178 // to include in this word.
1179 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1181 // Deal with sign extenstion in the break word, and possibly the word before
1184 if (wordShift > bitsInWord) {
1187 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1188 val[breakWord] |= ~0ULL;
1190 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1194 // Remaining words are 0 or -1, just assign them.
1195 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1196 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1198 return APInt(val, BitWidth).clearUnusedBits();
1201 /// Logical right-shift this APInt by shiftAmt.
1202 /// @brief Logical right-shift function.
1203 APInt APInt::lshr(const APInt &shiftAmt) const {
1204 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1207 /// Logical right-shift this APInt by shiftAmt.
1208 /// @brief Logical right-shift function.
1209 APInt APInt::lshr(unsigned shiftAmt) const {
1210 if (isSingleWord()) {
1211 if (shiftAmt == BitWidth)
1212 return APInt(BitWidth, 0);
1214 return APInt(BitWidth, this->VAL >> shiftAmt);
1217 // If all the bits were shifted out, the result is 0. This avoids issues
1218 // with shifting by the size of the integer type, which produces undefined
1219 // results. We define these "undefined results" to always be 0.
1220 if (shiftAmt == BitWidth)
1221 return APInt(BitWidth, 0);
1223 // If none of the bits are shifted out, the result is *this. This avoids
1224 // issues with shifting by the size of the integer type, which produces
1225 // undefined results in the code below. This is also an optimization.
1229 // Create some space for the result.
1230 uint64_t * val = new uint64_t[getNumWords()];
1232 // If we are shifting less than a word, compute the shift with a simple carry
1233 if (shiftAmt < APINT_BITS_PER_WORD) {
1235 for (int i = getNumWords()-1; i >= 0; --i) {
1236 val[i] = (pVal[i] >> shiftAmt) | carry;
1237 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1239 return APInt(val, BitWidth).clearUnusedBits();
1242 // Compute some values needed by the remaining shift algorithms
1243 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1244 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1246 // If we are shifting whole words, just move whole words
1247 if (wordShift == 0) {
1248 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1249 val[i] = pVal[i+offset];
1250 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1252 return APInt(val,BitWidth).clearUnusedBits();
1255 // Shift the low order words
1256 unsigned breakWord = getNumWords() - offset -1;
1257 for (unsigned i = 0; i < breakWord; ++i)
1258 val[i] = (pVal[i+offset] >> wordShift) |
1259 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1260 // Shift the break word.
1261 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1263 // Remaining words are 0
1264 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1266 return APInt(val, BitWidth).clearUnusedBits();
1269 /// Left-shift this APInt by shiftAmt.
1270 /// @brief Left-shift function.
1271 APInt APInt::shl(const APInt &shiftAmt) const {
1272 // It's undefined behavior in C to shift by BitWidth or greater.
1273 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1276 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1277 // If all the bits were shifted out, the result is 0. This avoids issues
1278 // with shifting by the size of the integer type, which produces undefined
1279 // results. We define these "undefined results" to always be 0.
1280 if (shiftAmt == BitWidth)
1281 return APInt(BitWidth, 0);
1283 // If none of the bits are shifted out, the result is *this. This avoids a
1284 // lshr by the words size in the loop below which can produce incorrect
1285 // results. It also avoids the expensive computation below for a common case.
1289 // Create some space for the result.
1290 uint64_t * val = new uint64_t[getNumWords()];
1292 // If we are shifting less than a word, do it the easy way
1293 if (shiftAmt < APINT_BITS_PER_WORD) {
1295 for (unsigned i = 0; i < getNumWords(); i++) {
1296 val[i] = pVal[i] << shiftAmt | carry;
1297 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1299 return APInt(val, BitWidth).clearUnusedBits();
1302 // Compute some values needed by the remaining shift algorithms
1303 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1304 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1306 // If we are shifting whole words, just move whole words
1307 if (wordShift == 0) {
1308 for (unsigned i = 0; i < offset; i++)
1310 for (unsigned i = offset; i < getNumWords(); i++)
1311 val[i] = pVal[i-offset];
1312 return APInt(val,BitWidth).clearUnusedBits();
1315 // Copy whole words from this to Result.
1316 unsigned i = getNumWords() - 1;
1317 for (; i > offset; --i)
1318 val[i] = pVal[i-offset] << wordShift |
1319 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1320 val[offset] = pVal[0] << wordShift;
1321 for (i = 0; i < offset; ++i)
1323 return APInt(val, BitWidth).clearUnusedBits();
1326 APInt APInt::rotl(const APInt &rotateAmt) const {
1327 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1330 APInt APInt::rotl(unsigned rotateAmt) const {
1333 // Don't get too fancy, just use existing shift/or facilities
1337 lo.lshr(BitWidth - rotateAmt);
1341 APInt APInt::rotr(const APInt &rotateAmt) const {
1342 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1345 APInt APInt::rotr(unsigned rotateAmt) const {
1348 // Don't get too fancy, just use existing shift/or facilities
1352 hi.shl(BitWidth - rotateAmt);
1356 // Square Root - this method computes and returns the square root of "this".
1357 // Three mechanisms are used for computation. For small values (<= 5 bits),
1358 // a table lookup is done. This gets some performance for common cases. For
1359 // values using less than 52 bits, the value is converted to double and then
1360 // the libc sqrt function is called. The result is rounded and then converted
1361 // back to a uint64_t which is then used to construct the result. Finally,
1362 // the Babylonian method for computing square roots is used.
1363 APInt APInt::sqrt() const {
1365 // Determine the magnitude of the value.
1366 unsigned magnitude = getActiveBits();
1368 // Use a fast table for some small values. This also gets rid of some
1369 // rounding errors in libc sqrt for small values.
1370 if (magnitude <= 5) {
1371 static const uint8_t results[32] = {
1374 /* 3- 6 */ 2, 2, 2, 2,
1375 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1376 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1377 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1380 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1383 // If the magnitude of the value fits in less than 52 bits (the precision of
1384 // an IEEE double precision floating point value), then we can use the
1385 // libc sqrt function which will probably use a hardware sqrt computation.
1386 // This should be faster than the algorithm below.
1387 if (magnitude < 52) {
1389 return APInt(BitWidth,
1390 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1392 return APInt(BitWidth,
1393 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1397 // Okay, all the short cuts are exhausted. We must compute it. The following
1398 // is a classical Babylonian method for computing the square root. This code
1399 // was adapted to APINt from a wikipedia article on such computations.
1400 // See http://www.wikipedia.org/ and go to the page named
1401 // Calculate_an_integer_square_root.
1402 unsigned nbits = BitWidth, i = 4;
1403 APInt testy(BitWidth, 16);
1404 APInt x_old(BitWidth, 1);
1405 APInt x_new(BitWidth, 0);
1406 APInt two(BitWidth, 2);
1408 // Select a good starting value using binary logarithms.
1409 for (;; i += 2, testy = testy.shl(2))
1410 if (i >= nbits || this->ule(testy)) {
1411 x_old = x_old.shl(i / 2);
1415 // Use the Babylonian method to arrive at the integer square root:
1417 x_new = (this->udiv(x_old) + x_old).udiv(two);
1418 if (x_old.ule(x_new))
1423 // Make sure we return the closest approximation
1424 // NOTE: The rounding calculation below is correct. It will produce an
1425 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1426 // determined to be a rounding issue with pari/gp as it begins to use a
1427 // floating point representation after 192 bits. There are no discrepancies
1428 // between this algorithm and pari/gp for bit widths < 192 bits.
1429 APInt square(x_old * x_old);
1430 APInt nextSquare((x_old + 1) * (x_old +1));
1431 if (this->ult(square))
1433 else if (this->ule(nextSquare)) {
1434 APInt midpoint((nextSquare - square).udiv(two));
1435 APInt offset(*this - square);
1436 if (offset.ult(midpoint))
1441 llvm_unreachable("Error in APInt::sqrt computation");
1445 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1446 /// iterative extended Euclidean algorithm is used to solve for this value,
1447 /// however we simplify it to speed up calculating only the inverse, and take
1448 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1449 /// (potentially large) APInts around.
1450 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1451 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1453 // Using the properties listed at the following web page (accessed 06/21/08):
1454 // http://www.numbertheory.org/php/euclid.html
1455 // (especially the properties numbered 3, 4 and 9) it can be proved that
1456 // BitWidth bits suffice for all the computations in the algorithm implemented
1457 // below. More precisely, this number of bits suffice if the multiplicative
1458 // inverse exists, but may not suffice for the general extended Euclidean
1461 APInt r[2] = { modulo, *this };
1462 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1463 APInt q(BitWidth, 0);
1466 for (i = 0; r[i^1] != 0; i ^= 1) {
1467 // An overview of the math without the confusing bit-flipping:
1468 // q = r[i-2] / r[i-1]
1469 // r[i] = r[i-2] % r[i-1]
1470 // t[i] = t[i-2] - t[i-1] * q
1471 udivrem(r[i], r[i^1], q, r[i]);
1475 // If this APInt and the modulo are not coprime, there is no multiplicative
1476 // inverse, so return 0. We check this by looking at the next-to-last
1477 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1480 return APInt(BitWidth, 0);
1482 // The next-to-last t is the multiplicative inverse. However, we are
1483 // interested in a positive inverse. Calcuate a positive one from a negative
1484 // one if necessary. A simple addition of the modulo suffices because
1485 // abs(t[i]) is known to be less than *this/2 (see the link above).
1486 return t[i].isNegative() ? t[i] + modulo : t[i];
1489 /// Calculate the magic numbers required to implement a signed integer division
1490 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1491 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1492 /// Warren, Jr., chapter 10.
1493 APInt::ms APInt::magic() const {
1494 const APInt& d = *this;
1496 APInt ad, anc, delta, q1, r1, q2, r2, t;
1497 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1501 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1502 anc = t - 1 - t.urem(ad); // absolute value of nc
1503 p = d.getBitWidth() - 1; // initialize p
1504 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1505 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1506 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1507 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1510 q1 = q1<<1; // update q1 = 2p/abs(nc)
1511 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1512 if (r1.uge(anc)) { // must be unsigned comparison
1516 q2 = q2<<1; // update q2 = 2p/abs(d)
1517 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1518 if (r2.uge(ad)) { // must be unsigned comparison
1523 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1526 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1527 mag.s = p - d.getBitWidth(); // resulting shift
1531 /// Calculate the magic numbers required to implement an unsigned integer
1532 /// division by a constant as a sequence of multiplies, adds and shifts.
1533 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1534 /// S. Warren, Jr., chapter 10.
1535 /// LeadingZeros can be used to simplify the calculation if the upper bits
1536 /// of the divided value are known zero.
1537 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1538 const APInt& d = *this;
1540 APInt nc, delta, q1, r1, q2, r2;
1542 magu.a = 0; // initialize "add" indicator
1543 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1544 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1545 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1547 nc = allOnes - (-d).urem(d);
1548 p = d.getBitWidth() - 1; // initialize p
1549 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1550 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1551 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1552 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1555 if (r1.uge(nc - r1)) {
1556 q1 = q1 + q1 + 1; // update q1
1557 r1 = r1 + r1 - nc; // update r1
1560 q1 = q1+q1; // update q1
1561 r1 = r1+r1; // update r1
1563 if ((r2 + 1).uge(d - r2)) {
1564 if (q2.uge(signedMax)) magu.a = 1;
1565 q2 = q2+q2 + 1; // update q2
1566 r2 = r2+r2 + 1 - d; // update r2
1569 if (q2.uge(signedMin)) magu.a = 1;
1570 q2 = q2+q2; // update q2
1571 r2 = r2+r2 + 1; // update r2
1574 } while (p < d.getBitWidth()*2 &&
1575 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1576 magu.m = q2 + 1; // resulting magic number
1577 magu.s = p - d.getBitWidth(); // resulting shift
1581 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1582 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1583 /// variables here have the same names as in the algorithm. Comments explain
1584 /// the algorithm and any deviation from it.
1585 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1586 unsigned m, unsigned n) {
1587 assert(u && "Must provide dividend");
1588 assert(v && "Must provide divisor");
1589 assert(q && "Must provide quotient");
1590 assert(u != v && u != q && v != q && "Must us different memory");
1591 assert(n>1 && "n must be > 1");
1593 // Knuth uses the value b as the base of the number system. In our case b
1594 // is 2^31 so we just set it to -1u.
1595 uint64_t b = uint64_t(1) << 32;
1598 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1599 DEBUG(dbgs() << "KnuthDiv: original:");
1600 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1601 DEBUG(dbgs() << " by");
1602 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1603 DEBUG(dbgs() << '\n');
1605 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1606 // u and v by d. Note that we have taken Knuth's advice here to use a power
1607 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1608 // 2 allows us to shift instead of multiply and it is easy to determine the
1609 // shift amount from the leading zeros. We are basically normalizing the u
1610 // and v so that its high bits are shifted to the top of v's range without
1611 // overflow. Note that this can require an extra word in u so that u must
1612 // be of length m+n+1.
1613 unsigned shift = CountLeadingZeros_32(v[n-1]);
1614 unsigned v_carry = 0;
1615 unsigned u_carry = 0;
1617 for (unsigned i = 0; i < m+n; ++i) {
1618 unsigned u_tmp = u[i] >> (32 - shift);
1619 u[i] = (u[i] << shift) | u_carry;
1622 for (unsigned i = 0; i < n; ++i) {
1623 unsigned v_tmp = v[i] >> (32 - shift);
1624 v[i] = (v[i] << shift) | v_carry;
1630 DEBUG(dbgs() << "KnuthDiv: normal:");
1631 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1632 DEBUG(dbgs() << " by");
1633 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1634 DEBUG(dbgs() << '\n');
1637 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1640 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1641 // D3. [Calculate q'.].
1642 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1643 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1644 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1645 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1646 // on v[n-2] determines at high speed most of the cases in which the trial
1647 // value qp is one too large, and it eliminates all cases where qp is two
1649 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1650 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1651 uint64_t qp = dividend / v[n-1];
1652 uint64_t rp = dividend % v[n-1];
1653 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1656 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1659 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1661 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1662 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1663 // consists of a simple multiplication by a one-place number, combined with
1666 for (unsigned i = 0; i < n; ++i) {
1667 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1668 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1669 bool borrow = subtrahend > u_tmp;
1670 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1671 << ", subtrahend == " << subtrahend
1672 << ", borrow = " << borrow << '\n');
1674 uint64_t result = u_tmp - subtrahend;
1676 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1677 u[k++] = (unsigned)(result >> 32); // subtract high word
1678 while (borrow && k <= m+n) { // deal with borrow to the left
1684 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1687 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1688 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1689 DEBUG(dbgs() << '\n');
1690 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1691 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1692 // true value plus b**(n+1), namely as the b's complement of
1693 // the true value, and a "borrow" to the left should be remembered.
1696 bool carry = true; // true because b's complement is "complement + 1"
1697 for (unsigned i = 0; i <= m+n; ++i) {
1698 u[i] = ~u[i] + carry; // b's complement
1699 carry = carry && u[i] == 0;
1702 DEBUG(dbgs() << "KnuthDiv: after complement:");
1703 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1704 DEBUG(dbgs() << '\n');
1706 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1707 // negative, go to step D6; otherwise go on to step D7.
1708 q[j] = (unsigned)qp;
1710 // D6. [Add back]. The probability that this step is necessary is very
1711 // small, on the order of only 2/b. Make sure that test data accounts for
1712 // this possibility. Decrease q[j] by 1
1714 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1715 // A carry will occur to the left of u[j+n], and it should be ignored
1716 // since it cancels with the borrow that occurred in D4.
1718 for (unsigned i = 0; i < n; i++) {
1719 unsigned limit = std::min(u[j+i],v[i]);
1720 u[j+i] += v[i] + carry;
1721 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1725 DEBUG(dbgs() << "KnuthDiv: after correction:");
1726 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1727 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1729 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1732 DEBUG(dbgs() << "KnuthDiv: quotient:");
1733 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1734 DEBUG(dbgs() << '\n');
1736 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1737 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1738 // compute the remainder (urem uses this).
1740 // The value d is expressed by the "shift" value above since we avoided
1741 // multiplication by d by using a shift left. So, all we have to do is
1742 // shift right here. In order to mak
1745 DEBUG(dbgs() << "KnuthDiv: remainder:");
1746 for (int i = n-1; i >= 0; i--) {
1747 r[i] = (u[i] >> shift) | carry;
1748 carry = u[i] << (32 - shift);
1749 DEBUG(dbgs() << " " << r[i]);
1752 for (int i = n-1; i >= 0; i--) {
1754 DEBUG(dbgs() << " " << r[i]);
1757 DEBUG(dbgs() << '\n');
1760 DEBUG(dbgs() << '\n');
1764 void APInt::divide(const APInt LHS, unsigned lhsWords,
1765 const APInt &RHS, unsigned rhsWords,
1766 APInt *Quotient, APInt *Remainder)
1768 assert(lhsWords >= rhsWords && "Fractional result");
1770 // First, compose the values into an array of 32-bit words instead of
1771 // 64-bit words. This is a necessity of both the "short division" algorithm
1772 // and the Knuth "classical algorithm" which requires there to be native
1773 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1774 // can't use 64-bit operands here because we don't have native results of
1775 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1776 // work on large-endian machines.
1777 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1778 unsigned n = rhsWords * 2;
1779 unsigned m = (lhsWords * 2) - n;
1781 // Allocate space for the temporary values we need either on the stack, if
1782 // it will fit, or on the heap if it won't.
1783 unsigned SPACE[128];
1788 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1791 Q = &SPACE[(m+n+1) + n];
1793 R = &SPACE[(m+n+1) + n + (m+n)];
1795 U = new unsigned[m + n + 1];
1796 V = new unsigned[n];
1797 Q = new unsigned[m+n];
1799 R = new unsigned[n];
1802 // Initialize the dividend
1803 memset(U, 0, (m+n+1)*sizeof(unsigned));
1804 for (unsigned i = 0; i < lhsWords; ++i) {
1805 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1806 U[i * 2] = (unsigned)(tmp & mask);
1807 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1809 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1811 // Initialize the divisor
1812 memset(V, 0, (n)*sizeof(unsigned));
1813 for (unsigned i = 0; i < rhsWords; ++i) {
1814 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1815 V[i * 2] = (unsigned)(tmp & mask);
1816 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1819 // initialize the quotient and remainder
1820 memset(Q, 0, (m+n) * sizeof(unsigned));
1822 memset(R, 0, n * sizeof(unsigned));
1824 // Now, adjust m and n for the Knuth division. n is the number of words in
1825 // the divisor. m is the number of words by which the dividend exceeds the
1826 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1827 // contain any zero words or the Knuth algorithm fails.
1828 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1832 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1835 // If we're left with only a single word for the divisor, Knuth doesn't work
1836 // so we implement the short division algorithm here. This is much simpler
1837 // and faster because we are certain that we can divide a 64-bit quantity
1838 // by a 32-bit quantity at hardware speed and short division is simply a
1839 // series of such operations. This is just like doing short division but we
1840 // are using base 2^32 instead of base 10.
1841 assert(n != 0 && "Divide by zero?");
1843 unsigned divisor = V[0];
1844 unsigned remainder = 0;
1845 for (int i = m+n-1; i >= 0; i--) {
1846 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1847 if (partial_dividend == 0) {
1850 } else if (partial_dividend < divisor) {
1852 remainder = (unsigned)partial_dividend;
1853 } else if (partial_dividend == divisor) {
1857 Q[i] = (unsigned)(partial_dividend / divisor);
1858 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1864 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1866 KnuthDiv(U, V, Q, R, m, n);
1869 // If the caller wants the quotient
1871 // Set up the Quotient value's memory.
1872 if (Quotient->BitWidth != LHS.BitWidth) {
1873 if (Quotient->isSingleWord())
1876 delete [] Quotient->pVal;
1877 Quotient->BitWidth = LHS.BitWidth;
1878 if (!Quotient->isSingleWord())
1879 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1881 Quotient->clearAllBits();
1883 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1885 if (lhsWords == 1) {
1887 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1888 if (Quotient->isSingleWord())
1889 Quotient->VAL = tmp;
1891 Quotient->pVal[0] = tmp;
1893 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1894 for (unsigned i = 0; i < lhsWords; ++i)
1896 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1900 // If the caller wants the remainder
1902 // Set up the Remainder value's memory.
1903 if (Remainder->BitWidth != RHS.BitWidth) {
1904 if (Remainder->isSingleWord())
1907 delete [] Remainder->pVal;
1908 Remainder->BitWidth = RHS.BitWidth;
1909 if (!Remainder->isSingleWord())
1910 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1912 Remainder->clearAllBits();
1914 // The remainder is in R. Reconstitute the remainder into Remainder's low
1916 if (rhsWords == 1) {
1918 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1919 if (Remainder->isSingleWord())
1920 Remainder->VAL = tmp;
1922 Remainder->pVal[0] = tmp;
1924 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1925 for (unsigned i = 0; i < rhsWords; ++i)
1926 Remainder->pVal[i] =
1927 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1931 // Clean up the memory we allocated.
1932 if (U != &SPACE[0]) {
1940 APInt APInt::udiv(const APInt& RHS) const {
1941 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1943 // First, deal with the easy case
1944 if (isSingleWord()) {
1945 assert(RHS.VAL != 0 && "Divide by zero?");
1946 return APInt(BitWidth, VAL / RHS.VAL);
1949 // Get some facts about the LHS and RHS number of bits and words
1950 unsigned rhsBits = RHS.getActiveBits();
1951 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1952 assert(rhsWords && "Divided by zero???");
1953 unsigned lhsBits = this->getActiveBits();
1954 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1956 // Deal with some degenerate cases
1959 return APInt(BitWidth, 0);
1960 else if (lhsWords < rhsWords || this->ult(RHS)) {
1961 // X / Y ===> 0, iff X < Y
1962 return APInt(BitWidth, 0);
1963 } else if (*this == RHS) {
1965 return APInt(BitWidth, 1);
1966 } else if (lhsWords == 1 && rhsWords == 1) {
1967 // All high words are zero, just use native divide
1968 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1971 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1972 APInt Quotient(1,0); // to hold result.
1973 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1977 APInt APInt::urem(const APInt& RHS) const {
1978 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1979 if (isSingleWord()) {
1980 assert(RHS.VAL != 0 && "Remainder by zero?");
1981 return APInt(BitWidth, VAL % RHS.VAL);
1984 // Get some facts about the LHS
1985 unsigned lhsBits = getActiveBits();
1986 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1988 // Get some facts about the RHS
1989 unsigned rhsBits = RHS.getActiveBits();
1990 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1991 assert(rhsWords && "Performing remainder operation by zero ???");
1993 // Check the degenerate cases
1994 if (lhsWords == 0) {
1996 return APInt(BitWidth, 0);
1997 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1998 // X % Y ===> X, iff X < Y
2000 } else if (*this == RHS) {
2002 return APInt(BitWidth, 0);
2003 } else if (lhsWords == 1) {
2004 // All high words are zero, just use native remainder
2005 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
2008 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2009 APInt Remainder(1,0);
2010 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2014 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2015 APInt &Quotient, APInt &Remainder) {
2016 // Get some size facts about the dividend and divisor
2017 unsigned lhsBits = LHS.getActiveBits();
2018 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2019 unsigned rhsBits = RHS.getActiveBits();
2020 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2022 // Check the degenerate cases
2023 if (lhsWords == 0) {
2024 Quotient = 0; // 0 / Y ===> 0
2025 Remainder = 0; // 0 % Y ===> 0
2029 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2030 Remainder = LHS; // X % Y ===> X, iff X < Y
2031 Quotient = 0; // X / Y ===> 0, iff X < Y
2036 Quotient = 1; // X / X ===> 1
2037 Remainder = 0; // X % X ===> 0;
2041 if (lhsWords == 1 && rhsWords == 1) {
2042 // There is only one word to consider so use the native versions.
2043 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2044 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2045 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2046 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2050 // Okay, lets do it the long way
2051 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2054 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2055 APInt Res = *this+RHS;
2056 Overflow = isNonNegative() == RHS.isNonNegative() &&
2057 Res.isNonNegative() != isNonNegative();
2061 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2062 APInt Res = *this+RHS;
2063 Overflow = Res.ult(RHS);
2067 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2068 APInt Res = *this - RHS;
2069 Overflow = isNonNegative() != RHS.isNonNegative() &&
2070 Res.isNonNegative() != isNonNegative();
2074 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2075 APInt Res = *this-RHS;
2076 Overflow = Res.ugt(*this);
2080 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2081 // MININT/-1 --> overflow.
2082 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2086 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2087 APInt Res = *this * RHS;
2089 if (*this != 0 && RHS != 0)
2090 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2096 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2097 APInt Res = *this * RHS;
2099 if (*this != 0 && RHS != 0)
2100 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2106 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2107 Overflow = ShAmt >= getBitWidth();
2109 ShAmt = getBitWidth()-1;
2111 if (isNonNegative()) // Don't allow sign change.
2112 Overflow = ShAmt >= countLeadingZeros();
2114 Overflow = ShAmt >= countLeadingOnes();
2116 return *this << ShAmt;
2122 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2123 // Check our assumptions here
2124 assert(!str.empty() && "Invalid string length");
2125 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2127 "Radix should be 2, 8, 10, 16, or 36!");
2129 StringRef::iterator p = str.begin();
2130 size_t slen = str.size();
2131 bool isNeg = *p == '-';
2132 if (*p == '-' || *p == '+') {
2135 assert(slen && "String is only a sign, needs a value.");
2137 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2138 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2139 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2140 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2141 "Insufficient bit width");
2144 if (!isSingleWord())
2145 pVal = getClearedMemory(getNumWords());
2147 // Figure out if we can shift instead of multiply
2148 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2150 // Set up an APInt for the digit to add outside the loop so we don't
2151 // constantly construct/destruct it.
2152 APInt apdigit(getBitWidth(), 0);
2153 APInt apradix(getBitWidth(), radix);
2155 // Enter digit traversal loop
2156 for (StringRef::iterator e = str.end(); p != e; ++p) {
2157 unsigned digit = getDigit(*p, radix);
2158 assert(digit < radix && "Invalid character in digit string");
2160 // Shift or multiply the value by the radix
2168 // Add in the digit we just interpreted
2169 if (apdigit.isSingleWord())
2170 apdigit.VAL = digit;
2172 apdigit.pVal[0] = digit;
2175 // If its negative, put it in two's complement form
2178 this->flipAllBits();
2182 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2183 bool Signed, bool formatAsCLiteral) const {
2184 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2186 "Radix should be 2, 8, 10, or 16!");
2188 const char *Prefix = "";
2189 if (formatAsCLiteral) {
2192 // Binary literals are a non-standard extension added in gcc 4.3:
2193 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2205 // First, check for a zero value and just short circuit the logic below.
2208 Str.push_back(*Prefix);
2215 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2217 if (isSingleWord()) {
2219 char *BufPtr = Buffer+65;
2225 int64_t I = getSExtValue();
2235 Str.push_back(*Prefix);
2240 *--BufPtr = Digits[N % Radix];
2243 Str.append(BufPtr, Buffer+65);
2249 if (Signed && isNegative()) {
2250 // They want to print the signed version and it is a negative value
2251 // Flip the bits and add one to turn it into the equivalent positive
2252 // value and put a '-' in the result.
2259 Str.push_back(*Prefix);
2263 // We insert the digits backward, then reverse them to get the right order.
2264 unsigned StartDig = Str.size();
2266 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2267 // because the number of bits per digit (1, 3 and 4 respectively) divides
2268 // equaly. We just shift until the value is zero.
2269 if (Radix == 2 || Radix == 8 || Radix == 16) {
2270 // Just shift tmp right for each digit width until it becomes zero
2271 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2272 unsigned MaskAmt = Radix - 1;
2275 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2276 Str.push_back(Digits[Digit]);
2277 Tmp = Tmp.lshr(ShiftAmt);
2280 APInt divisor(Radix == 10? 4 : 8, Radix);
2282 APInt APdigit(1, 0);
2283 APInt tmp2(Tmp.getBitWidth(), 0);
2284 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2286 unsigned Digit = (unsigned)APdigit.getZExtValue();
2287 assert(Digit < Radix && "divide failed");
2288 Str.push_back(Digits[Digit]);
2293 // Reverse the digits before returning.
2294 std::reverse(Str.begin()+StartDig, Str.end());
2297 /// toString - This returns the APInt as a std::string. Note that this is an
2298 /// inefficient method. It is better to pass in a SmallVector/SmallString
2299 /// to the methods above.
2300 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2302 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2307 void APInt::dump() const {
2308 SmallString<40> S, U;
2309 this->toStringUnsigned(U);
2310 this->toStringSigned(S);
2311 dbgs() << "APInt(" << BitWidth << "b, "
2312 << U.str() << "u " << S.str() << "s)";
2315 void APInt::print(raw_ostream &OS, bool isSigned) const {
2317 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2321 // This implements a variety of operations on a representation of
2322 // arbitrary precision, two's-complement, bignum integer values.
2324 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2325 // and unrestricting assumption.
2326 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2327 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2329 /* Some handy functions local to this file. */
2332 /* Returns the integer part with the least significant BITS set.
2333 BITS cannot be zero. */
2334 static inline integerPart
2335 lowBitMask(unsigned int bits)
2337 assert(bits != 0 && bits <= integerPartWidth);
2339 return ~(integerPart) 0 >> (integerPartWidth - bits);
2342 /* Returns the value of the lower half of PART. */
2343 static inline integerPart
2344 lowHalf(integerPart part)
2346 return part & lowBitMask(integerPartWidth / 2);
2349 /* Returns the value of the upper half of PART. */
2350 static inline integerPart
2351 highHalf(integerPart part)
2353 return part >> (integerPartWidth / 2);
2356 /* Returns the bit number of the most significant set bit of a part.
2357 If the input number has no bits set -1U is returned. */
2359 partMSB(integerPart value)
2361 unsigned int n, msb;
2366 n = integerPartWidth / 2;
2381 /* Returns the bit number of the least significant set bit of a
2382 part. If the input number has no bits set -1U is returned. */
2384 partLSB(integerPart value)
2386 unsigned int n, lsb;
2391 lsb = integerPartWidth - 1;
2392 n = integerPartWidth / 2;
2407 /* Sets the least significant part of a bignum to the input value, and
2408 zeroes out higher parts. */
2410 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2417 for (i = 1; i < parts; i++)
2421 /* Assign one bignum to another. */
2423 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2427 for (i = 0; i < parts; i++)
2431 /* Returns true if a bignum is zero, false otherwise. */
2433 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2437 for (i = 0; i < parts; i++)
2444 /* Extract the given bit of a bignum; returns 0 or 1. */
2446 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2448 return (parts[bit / integerPartWidth] &
2449 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2452 /* Set the given bit of a bignum. */
2454 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2456 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2459 /* Clears the given bit of a bignum. */
2461 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2463 parts[bit / integerPartWidth] &=
2464 ~((integerPart) 1 << (bit % integerPartWidth));
2467 /* Returns the bit number of the least significant set bit of a
2468 number. If the input number has no bits set -1U is returned. */
2470 APInt::tcLSB(const integerPart *parts, unsigned int n)
2472 unsigned int i, lsb;
2474 for (i = 0; i < n; i++) {
2475 if (parts[i] != 0) {
2476 lsb = partLSB(parts[i]);
2478 return lsb + i * integerPartWidth;
2485 /* Returns the bit number of the most significant set bit of a number.
2486 If the input number has no bits set -1U is returned. */
2488 APInt::tcMSB(const integerPart *parts, unsigned int n)
2495 if (parts[n] != 0) {
2496 msb = partMSB(parts[n]);
2498 return msb + n * integerPartWidth;
2505 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2506 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2507 the least significant bit of DST. All high bits above srcBITS in
2508 DST are zero-filled. */
2510 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2511 unsigned int srcBits, unsigned int srcLSB)
2513 unsigned int firstSrcPart, dstParts, shift, n;
2515 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2516 assert(dstParts <= dstCount);
2518 firstSrcPart = srcLSB / integerPartWidth;
2519 tcAssign (dst, src + firstSrcPart, dstParts);
2521 shift = srcLSB % integerPartWidth;
2522 tcShiftRight (dst, dstParts, shift);
2524 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2525 in DST. If this is less that srcBits, append the rest, else
2526 clear the high bits. */
2527 n = dstParts * integerPartWidth - shift;
2529 integerPart mask = lowBitMask (srcBits - n);
2530 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2531 << n % integerPartWidth);
2532 } else if (n > srcBits) {
2533 if (srcBits % integerPartWidth)
2534 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2537 /* Clear high parts. */
2538 while (dstParts < dstCount)
2539 dst[dstParts++] = 0;
2542 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2544 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2545 integerPart c, unsigned int parts)
2551 for (i = 0; i < parts; i++) {
2556 dst[i] += rhs[i] + 1;
2567 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2569 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2570 integerPart c, unsigned int parts)
2576 for (i = 0; i < parts; i++) {
2581 dst[i] -= rhs[i] + 1;
2592 /* Negate a bignum in-place. */
2594 APInt::tcNegate(integerPart *dst, unsigned int parts)
2596 tcComplement(dst, parts);
2597 tcIncrement(dst, parts);
2600 /* DST += SRC * MULTIPLIER + CARRY if add is true
2601 DST = SRC * MULTIPLIER + CARRY if add is false
2603 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2604 they must start at the same point, i.e. DST == SRC.
2606 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2607 returned. Otherwise DST is filled with the least significant
2608 DSTPARTS parts of the result, and if all of the omitted higher
2609 parts were zero return zero, otherwise overflow occurred and
2612 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2613 integerPart multiplier, integerPart carry,
2614 unsigned int srcParts, unsigned int dstParts,
2619 /* Otherwise our writes of DST kill our later reads of SRC. */
2620 assert(dst <= src || dst >= src + srcParts);
2621 assert(dstParts <= srcParts + 1);
2623 /* N loops; minimum of dstParts and srcParts. */
2624 n = dstParts < srcParts ? dstParts: srcParts;
2626 for (i = 0; i < n; i++) {
2627 integerPart low, mid, high, srcPart;
2629 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2631 This cannot overflow, because
2633 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2635 which is less than n^2. */
2639 if (multiplier == 0 || srcPart == 0) {
2643 low = lowHalf(srcPart) * lowHalf(multiplier);
2644 high = highHalf(srcPart) * highHalf(multiplier);
2646 mid = lowHalf(srcPart) * highHalf(multiplier);
2647 high += highHalf(mid);
2648 mid <<= integerPartWidth / 2;
2649 if (low + mid < low)
2653 mid = highHalf(srcPart) * lowHalf(multiplier);
2654 high += highHalf(mid);
2655 mid <<= integerPartWidth / 2;
2656 if (low + mid < low)
2660 /* Now add carry. */
2661 if (low + carry < low)
2667 /* And now DST[i], and store the new low part there. */
2668 if (low + dst[i] < low)
2678 /* Full multiplication, there is no overflow. */
2679 assert(i + 1 == dstParts);
2683 /* We overflowed if there is carry. */
2687 /* We would overflow if any significant unwritten parts would be
2688 non-zero. This is true if any remaining src parts are non-zero
2689 and the multiplier is non-zero. */
2691 for (; i < srcParts; i++)
2695 /* We fitted in the narrow destination. */
2700 /* DST = LHS * RHS, where DST has the same width as the operands and
2701 is filled with the least significant parts of the result. Returns
2702 one if overflow occurred, otherwise zero. DST must be disjoint
2703 from both operands. */
2705 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2706 const integerPart *rhs, unsigned int parts)
2711 assert(dst != lhs && dst != rhs);
2714 tcSet(dst, 0, parts);
2716 for (i = 0; i < parts; i++)
2717 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2723 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2724 operands. No overflow occurs. DST must be disjoint from both
2725 operands. Returns the number of parts required to hold the
2728 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2729 const integerPart *rhs, unsigned int lhsParts,
2730 unsigned int rhsParts)
2732 /* Put the narrower number on the LHS for less loops below. */
2733 if (lhsParts > rhsParts) {
2734 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2738 assert(dst != lhs && dst != rhs);
2740 tcSet(dst, 0, rhsParts);
2742 for (n = 0; n < lhsParts; n++)
2743 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2745 n = lhsParts + rhsParts;
2747 return n - (dst[n - 1] == 0);
2751 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2752 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2753 set REMAINDER to the remainder, return zero. i.e.
2755 OLD_LHS = RHS * LHS + REMAINDER
2757 SCRATCH is a bignum of the same size as the operands and result for
2758 use by the routine; its contents need not be initialized and are
2759 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2762 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2763 integerPart *remainder, integerPart *srhs,
2766 unsigned int n, shiftCount;
2769 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2771 shiftCount = tcMSB(rhs, parts) + 1;
2772 if (shiftCount == 0)
2775 shiftCount = parts * integerPartWidth - shiftCount;
2776 n = shiftCount / integerPartWidth;
2777 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2779 tcAssign(srhs, rhs, parts);
2780 tcShiftLeft(srhs, parts, shiftCount);
2781 tcAssign(remainder, lhs, parts);
2782 tcSet(lhs, 0, parts);
2784 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2789 compare = tcCompare(remainder, srhs, parts);
2791 tcSubtract(remainder, srhs, 0, parts);
2795 if (shiftCount == 0)
2798 tcShiftRight(srhs, parts, 1);
2799 if ((mask >>= 1) == 0)
2800 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2806 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2807 There are no restrictions on COUNT. */
2809 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2812 unsigned int jump, shift;
2814 /* Jump is the inter-part jump; shift is is intra-part shift. */
2815 jump = count / integerPartWidth;
2816 shift = count % integerPartWidth;
2818 while (parts > jump) {
2823 /* dst[i] comes from the two parts src[i - jump] and, if we have
2824 an intra-part shift, src[i - jump - 1]. */
2825 part = dst[parts - jump];
2828 if (parts >= jump + 1)
2829 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2840 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2841 zero. There are no restrictions on COUNT. */
2843 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2846 unsigned int i, jump, shift;
2848 /* Jump is the inter-part jump; shift is is intra-part shift. */
2849 jump = count / integerPartWidth;
2850 shift = count % integerPartWidth;
2852 /* Perform the shift. This leaves the most significant COUNT bits
2853 of the result at zero. */
2854 for (i = 0; i < parts; i++) {
2857 if (i + jump >= parts) {
2860 part = dst[i + jump];
2863 if (i + jump + 1 < parts)
2864 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2873 /* Bitwise and of two bignums. */
2875 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2879 for (i = 0; i < parts; i++)
2883 /* Bitwise inclusive or of two bignums. */
2885 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2889 for (i = 0; i < parts; i++)
2893 /* Bitwise exclusive or of two bignums. */
2895 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2899 for (i = 0; i < parts; i++)
2903 /* Complement a bignum in-place. */
2905 APInt::tcComplement(integerPart *dst, unsigned int parts)
2909 for (i = 0; i < parts; i++)
2913 /* Comparison (unsigned) of two bignums. */
2915 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2920 if (lhs[parts] == rhs[parts])
2923 if (lhs[parts] > rhs[parts])
2932 /* Increment a bignum in-place, return the carry flag. */
2934 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2938 for (i = 0; i < parts; i++)
2945 /* Set the least significant BITS bits of a bignum, clear the
2948 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2954 while (bits > integerPartWidth) {
2955 dst[i++] = ~(integerPart) 0;
2956 bits -= integerPartWidth;
2960 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);