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) {
52 if (!isxdigit(cdigit))
53 llvm_unreachable("Invalid hex digit in string");
56 else if (cdigit >= 'a')
57 digit = cdigit - 'a' + 10;
58 else if (cdigit >= 'A')
59 digit = cdigit - 'A' + 10;
61 llvm_unreachable("huh? we shouldn't get here");
62 } else if (isdigit(cdigit)) {
64 assert((radix == 10 ||
65 (radix == 8 && digit != 8 && digit != 9) ||
66 (radix == 2 && (digit == 0 || digit == 1))) &&
67 "Invalid digit in string for given radix");
69 llvm_unreachable("Invalid character in digit string");
76 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
77 pVal = getClearedMemory(getNumWords());
79 if (isSigned && int64_t(val) < 0)
80 for (unsigned i = 1; i < getNumWords(); ++i)
84 void APInt::initSlowCase(const APInt& that) {
85 pVal = getMemory(getNumWords());
86 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
90 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
91 : BitWidth(numBits), VAL(0) {
92 assert(BitWidth && "Bitwidth too small");
93 assert(bigVal && "Null pointer detected!");
97 // Get memory, cleared to 0
98 pVal = getClearedMemory(getNumWords());
99 // Calculate the number of words to copy
100 unsigned words = std::min<unsigned>(numWords, getNumWords());
101 // Copy the words from bigVal to pVal
102 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
104 // Make sure unused high bits are cleared
108 APInt::APInt(unsigned numbits, const StringRef& Str, uint8_t radix)
109 : BitWidth(numbits), VAL(0) {
110 assert(BitWidth && "Bitwidth too small");
111 fromString(numbits, Str, radix);
114 APInt& APInt::AssignSlowCase(const APInt& RHS) {
115 // Don't do anything for X = X
119 if (BitWidth == RHS.getBitWidth()) {
120 // assume same bit-width single-word case is already handled
121 assert(!isSingleWord());
122 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
126 if (isSingleWord()) {
127 // assume case where both are single words is already handled
128 assert(!RHS.isSingleWord());
130 pVal = getMemory(RHS.getNumWords());
131 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
132 } else if (getNumWords() == RHS.getNumWords())
133 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
134 else if (RHS.isSingleWord()) {
139 pVal = getMemory(RHS.getNumWords());
140 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
142 BitWidth = RHS.BitWidth;
143 return clearUnusedBits();
146 APInt& APInt::operator=(uint64_t RHS) {
151 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
153 return clearUnusedBits();
156 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
157 void APInt::Profile(FoldingSetNodeID& ID) const {
158 ID.AddInteger(BitWidth);
160 if (isSingleWord()) {
165 unsigned NumWords = getNumWords();
166 for (unsigned i = 0; i < NumWords; ++i)
167 ID.AddInteger(pVal[i]);
170 /// add_1 - This function adds a single "digit" integer, y, to the multiple
171 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
172 /// 1 is returned if there is a carry out, otherwise 0 is returned.
173 /// @returns the carry of the addition.
174 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
175 for (unsigned i = 0; i < len; ++i) {
178 y = 1; // Carry one to next digit.
180 y = 0; // No need to carry so exit early
187 /// @brief Prefix increment operator. Increments the APInt by one.
188 APInt& APInt::operator++() {
192 add_1(pVal, pVal, getNumWords(), 1);
193 return clearUnusedBits();
196 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
197 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
198 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
199 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
200 /// In other words, if y > x then this function returns 1, otherwise 0.
201 /// @returns the borrow out of the subtraction
202 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
203 for (unsigned i = 0; i < len; ++i) {
207 y = 1; // We have to "borrow 1" from next "digit"
209 y = 0; // No need to borrow
210 break; // Remaining digits are unchanged so exit early
216 /// @brief Prefix decrement operator. Decrements the APInt by one.
217 APInt& APInt::operator--() {
221 sub_1(pVal, getNumWords(), 1);
222 return clearUnusedBits();
225 /// add - This function adds the integer array x to the integer array Y and
226 /// places the result in dest.
227 /// @returns the carry out from the addition
228 /// @brief General addition of 64-bit integer arrays
229 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
232 for (unsigned i = 0; i< len; ++i) {
233 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
234 dest[i] = x[i] + y[i] + carry;
235 carry = dest[i] < limit || (carry && dest[i] == limit);
240 /// Adds the RHS APint to this APInt.
241 /// @returns this, after addition of RHS.
242 /// @brief Addition assignment operator.
243 APInt& APInt::operator+=(const APInt& RHS) {
244 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
248 add(pVal, pVal, RHS.pVal, getNumWords());
250 return clearUnusedBits();
253 /// Subtracts the integer array y from the integer array x
254 /// @returns returns the borrow out.
255 /// @brief Generalized subtraction of 64-bit integer arrays.
256 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
259 for (unsigned i = 0; i < len; ++i) {
260 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
261 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
262 dest[i] = x_tmp - y[i];
267 /// Subtracts the RHS APInt from this APInt
268 /// @returns this, after subtraction
269 /// @brief Subtraction assignment operator.
270 APInt& APInt::operator-=(const APInt& RHS) {
271 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
275 sub(pVal, pVal, RHS.pVal, getNumWords());
276 return clearUnusedBits();
279 /// Multiplies an integer array, x by a a uint64_t integer and places the result
281 /// @returns the carry out of the multiplication.
282 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
283 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
284 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
285 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
288 // For each digit of x.
289 for (unsigned i = 0; i < len; ++i) {
290 // Split x into high and low words
291 uint64_t lx = x[i] & 0xffffffffULL;
292 uint64_t hx = x[i] >> 32;
293 // hasCarry - A flag to indicate if there is a carry to the next digit.
294 // hasCarry == 0, no carry
295 // hasCarry == 1, has carry
296 // hasCarry == 2, no carry and the calculation result == 0.
297 uint8_t hasCarry = 0;
298 dest[i] = carry + lx * ly;
299 // Determine if the add above introduces carry.
300 hasCarry = (dest[i] < carry) ? 1 : 0;
301 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
302 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
303 // (2^32 - 1) + 2^32 = 2^64.
304 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
306 carry += (lx * hy) & 0xffffffffULL;
307 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
308 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
309 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
314 /// Multiplies integer array x by integer array y and stores the result into
315 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
316 /// @brief Generalized multiplicate of integer arrays.
317 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
319 dest[xlen] = mul_1(dest, x, xlen, y[0]);
320 for (unsigned i = 1; i < ylen; ++i) {
321 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
322 uint64_t carry = 0, lx = 0, hx = 0;
323 for (unsigned j = 0; j < xlen; ++j) {
324 lx = x[j] & 0xffffffffULL;
326 // hasCarry - A flag to indicate if has carry.
327 // hasCarry == 0, no carry
328 // hasCarry == 1, has carry
329 // hasCarry == 2, no carry and the calculation result == 0.
330 uint8_t hasCarry = 0;
331 uint64_t resul = carry + lx * ly;
332 hasCarry = (resul < carry) ? 1 : 0;
333 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
334 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
336 carry += (lx * hy) & 0xffffffffULL;
337 resul = (carry << 32) | (resul & 0xffffffffULL);
339 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
340 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
341 ((lx * hy) >> 32) + hx * hy;
343 dest[i+xlen] = carry;
347 APInt& APInt::operator*=(const APInt& RHS) {
348 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
349 if (isSingleWord()) {
355 // Get some bit facts about LHS and check for zero
356 unsigned lhsBits = getActiveBits();
357 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
362 // Get some bit facts about RHS and check for zero
363 unsigned rhsBits = RHS.getActiveBits();
364 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
371 // Allocate space for the result
372 unsigned destWords = rhsWords + lhsWords;
373 uint64_t *dest = getMemory(destWords);
375 // Perform the long multiply
376 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
378 // Copy result back into *this
380 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
381 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
383 // delete dest array and return
388 APInt& APInt::operator&=(const APInt& RHS) {
389 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
390 if (isSingleWord()) {
394 unsigned numWords = getNumWords();
395 for (unsigned i = 0; i < numWords; ++i)
396 pVal[i] &= RHS.pVal[i];
400 APInt& APInt::operator|=(const APInt& RHS) {
401 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
402 if (isSingleWord()) {
406 unsigned numWords = getNumWords();
407 for (unsigned i = 0; i < numWords; ++i)
408 pVal[i] |= RHS.pVal[i];
412 APInt& APInt::operator^=(const APInt& RHS) {
413 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
414 if (isSingleWord()) {
416 this->clearUnusedBits();
419 unsigned numWords = getNumWords();
420 for (unsigned i = 0; i < numWords; ++i)
421 pVal[i] ^= RHS.pVal[i];
422 return clearUnusedBits();
425 APInt APInt::AndSlowCase(const APInt& RHS) const {
426 unsigned numWords = getNumWords();
427 uint64_t* val = getMemory(numWords);
428 for (unsigned i = 0; i < numWords; ++i)
429 val[i] = pVal[i] & RHS.pVal[i];
430 return APInt(val, getBitWidth());
433 APInt APInt::OrSlowCase(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::XorSlowCase(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];
447 // 0^0==1 so clear the high bits in case they got set.
448 return APInt(val, getBitWidth()).clearUnusedBits();
451 bool APInt::operator !() const {
455 for (unsigned i = 0; i < getNumWords(); ++i)
461 APInt APInt::operator*(const APInt& RHS) const {
462 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
464 return APInt(BitWidth, VAL * RHS.VAL);
467 return Result.clearUnusedBits();
470 APInt APInt::operator+(const APInt& RHS) const {
471 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
473 return APInt(BitWidth, VAL + RHS.VAL);
474 APInt Result(BitWidth, 0);
475 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
476 return Result.clearUnusedBits();
479 APInt APInt::operator-(const APInt& RHS) const {
480 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
482 return APInt(BitWidth, VAL - RHS.VAL);
483 APInt Result(BitWidth, 0);
484 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
485 return Result.clearUnusedBits();
488 bool APInt::operator[](unsigned bitPosition) const {
489 return (maskBit(bitPosition) &
490 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
493 bool APInt::EqualSlowCase(const APInt& RHS) const {
494 // Get some facts about the number of bits used in the two operands.
495 unsigned n1 = getActiveBits();
496 unsigned n2 = RHS.getActiveBits();
498 // If the number of bits isn't the same, they aren't equal
502 // If the number of bits fits in a word, we only need to compare the low word.
503 if (n1 <= APINT_BITS_PER_WORD)
504 return pVal[0] == RHS.pVal[0];
506 // Otherwise, compare everything
507 for (int i = whichWord(n1 - 1); i >= 0; --i)
508 if (pVal[i] != RHS.pVal[i])
513 bool APInt::EqualSlowCase(uint64_t Val) const {
514 unsigned n = getActiveBits();
515 if (n <= APINT_BITS_PER_WORD)
516 return pVal[0] == Val;
521 bool APInt::ult(const APInt& RHS) const {
522 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
524 return VAL < RHS.VAL;
526 // Get active bit length of both operands
527 unsigned n1 = getActiveBits();
528 unsigned n2 = RHS.getActiveBits();
530 // If magnitude of LHS is less than RHS, return true.
534 // If magnitude of RHS is greather than LHS, return false.
538 // If they bot fit in a word, just compare the low order word
539 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
540 return pVal[0] < RHS.pVal[0];
542 // Otherwise, compare all words
543 unsigned topWord = whichWord(std::max(n1,n2)-1);
544 for (int i = topWord; i >= 0; --i) {
545 if (pVal[i] > RHS.pVal[i])
547 if (pVal[i] < RHS.pVal[i])
553 bool APInt::slt(const APInt& RHS) const {
554 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
555 if (isSingleWord()) {
556 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
557 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
558 return lhsSext < rhsSext;
563 bool lhsNeg = isNegative();
564 bool rhsNeg = rhs.isNegative();
566 // Sign bit is set so perform two's complement to make it positive
571 // Sign bit is set so perform two's complement to make it positive
576 // Now we have unsigned values to compare so do the comparison if necessary
577 // based on the negativeness of the values.
589 APInt& APInt::set(unsigned bitPosition) {
591 VAL |= maskBit(bitPosition);
593 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
597 /// Set the given bit to 0 whose position is given as "bitPosition".
598 /// @brief Set a given bit to 0.
599 APInt& APInt::clear(unsigned bitPosition) {
601 VAL &= ~maskBit(bitPosition);
603 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
607 /// @brief Toggle every bit to its opposite value.
609 /// Toggle a given bit to its opposite value whose position is given
610 /// as "bitPosition".
611 /// @brief Toggles a given bit to its opposite value.
612 APInt& APInt::flip(unsigned bitPosition) {
613 assert(bitPosition < BitWidth && "Out of the bit-width range!");
614 if ((*this)[bitPosition]) clear(bitPosition);
615 else set(bitPosition);
619 unsigned APInt::getBitsNeeded(const StringRef& str, uint8_t radix) {
620 assert(!str.empty() && "Invalid string length");
621 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
622 "Radix should be 2, 8, 10, or 16!");
624 size_t slen = str.size();
626 // Each computation below needs to know if its negative
627 StringRef::iterator p = str.begin();
628 unsigned isNegative = str.front() == '-';
629 if (*p == '-' || *p == '+') {
632 assert(slen && "string is only a minus!");
634 // For radixes of power-of-two values, the bits required is accurately and
637 return slen + isNegative;
639 return slen * 3 + isNegative;
641 return slen * 4 + isNegative;
643 // This is grossly inefficient but accurate. We could probably do something
644 // with a computation of roughly slen*64/20 and then adjust by the value of
645 // the first few digits. But, I'm not sure how accurate that could be.
647 // Compute a sufficient number of bits that is always large enough but might
648 // be too large. This avoids the assertion in the constructor. This
649 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
650 // bits in that case.
651 unsigned sufficient = slen == 1 ? 4 : slen * 64/18;
653 // Convert to the actual binary value.
654 APInt tmp(sufficient, StringRef(p, slen), radix);
656 // Compute how many bits are required. If the log is infinite, assume we need
658 unsigned log = tmp.logBase2();
659 if (log == (unsigned)-1) {
660 return isNegative + 1;
662 return isNegative + log + 1;
666 // From http://www.burtleburtle.net, byBob Jenkins.
667 // When targeting x86, both GCC and LLVM seem to recognize this as a
668 // rotate instruction.
669 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
671 // From http://www.burtleburtle.net, by Bob Jenkins.
674 a -= c; a ^= rot(c, 4); c += b; \
675 b -= a; b ^= rot(a, 6); a += c; \
676 c -= b; c ^= rot(b, 8); b += a; \
677 a -= c; a ^= rot(c,16); c += b; \
678 b -= a; b ^= rot(a,19); a += c; \
679 c -= b; c ^= rot(b, 4); b += a; \
682 // From http://www.burtleburtle.net, by Bob Jenkins.
683 #define final(a,b,c) \
685 c ^= b; c -= rot(b,14); \
686 a ^= c; a -= rot(c,11); \
687 b ^= a; b -= rot(a,25); \
688 c ^= b; c -= rot(b,16); \
689 a ^= c; a -= rot(c,4); \
690 b ^= a; b -= rot(a,14); \
691 c ^= b; c -= rot(b,24); \
694 // hashword() was adapted from http://www.burtleburtle.net, by Bob
695 // Jenkins. k is a pointer to an array of uint32_t values; length is
696 // the length of the key, in 32-bit chunks. This version only handles
697 // keys that are a multiple of 32 bits in size.
698 static inline uint32_t hashword(const uint64_t *k64, size_t length)
700 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
703 /* Set up the internal state */
704 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
706 /*------------------------------------------------- handle most of the key */
717 /*------------------------------------------- handle the last 3 uint32_t's */
718 switch (length) { /* all the case statements fall through */
723 case 0: /* case 0: nothing left to add */
726 /*------------------------------------------------------ report the result */
730 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
731 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
732 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
733 // function into about 35 instructions when inlined.
734 static inline uint32_t hashword8(const uint64_t k64)
737 a = b = c = 0xdeadbeef + 4;
739 a += k64 & 0xffffffff;
747 uint64_t APInt::getHashValue() const {
750 hash = hashword8(VAL);
752 hash = hashword(pVal, getNumWords()*2);
756 /// HiBits - This function returns the high "numBits" bits of this APInt.
757 APInt APInt::getHiBits(unsigned numBits) const {
758 return APIntOps::lshr(*this, BitWidth - numBits);
761 /// LoBits - This function returns the low "numBits" bits of this APInt.
762 APInt APInt::getLoBits(unsigned numBits) const {
763 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
767 bool APInt::isPowerOf2() const {
768 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
771 unsigned APInt::countLeadingZerosSlowCase() const {
773 for (unsigned i = getNumWords(); i > 0u; --i) {
775 Count += APINT_BITS_PER_WORD;
777 Count += CountLeadingZeros_64(pVal[i-1]);
781 unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
783 Count -= APINT_BITS_PER_WORD - remainder;
784 return std::min(Count, BitWidth);
787 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
791 while (V && (V & (1ULL << 63))) {
798 unsigned APInt::countLeadingOnes() const {
800 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
802 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
805 highWordBits = APINT_BITS_PER_WORD;
808 shift = APINT_BITS_PER_WORD - highWordBits;
810 int i = getNumWords() - 1;
811 unsigned Count = countLeadingOnes_64(pVal[i], shift);
812 if (Count == highWordBits) {
813 for (i--; i >= 0; --i) {
814 if (pVal[i] == -1ULL)
815 Count += APINT_BITS_PER_WORD;
817 Count += countLeadingOnes_64(pVal[i], 0);
825 unsigned APInt::countTrailingZeros() const {
827 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
830 for (; i < getNumWords() && pVal[i] == 0; ++i)
831 Count += APINT_BITS_PER_WORD;
832 if (i < getNumWords())
833 Count += CountTrailingZeros_64(pVal[i]);
834 return std::min(Count, BitWidth);
837 unsigned APInt::countTrailingOnesSlowCase() const {
840 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
841 Count += APINT_BITS_PER_WORD;
842 if (i < getNumWords())
843 Count += CountTrailingOnes_64(pVal[i]);
844 return std::min(Count, BitWidth);
847 unsigned APInt::countPopulationSlowCase() const {
849 for (unsigned i = 0; i < getNumWords(); ++i)
850 Count += CountPopulation_64(pVal[i]);
854 APInt APInt::byteSwap() const {
855 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
857 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
858 else if (BitWidth == 32)
859 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
860 else if (BitWidth == 48) {
861 unsigned Tmp1 = unsigned(VAL >> 16);
862 Tmp1 = ByteSwap_32(Tmp1);
863 uint16_t Tmp2 = uint16_t(VAL);
864 Tmp2 = ByteSwap_16(Tmp2);
865 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
866 } else if (BitWidth == 64)
867 return APInt(BitWidth, ByteSwap_64(VAL));
869 APInt Result(BitWidth, 0);
870 char *pByte = (char*)Result.pVal;
871 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
873 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
874 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
880 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
882 APInt A = API1, B = API2;
885 B = APIntOps::urem(A, B);
891 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
898 // Get the sign bit from the highest order bit
899 bool isNeg = T.I >> 63;
901 // Get the 11-bit exponent and adjust for the 1023 bit bias
902 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
904 // If the exponent is negative, the value is < 0 so just return 0.
906 return APInt(width, 0u);
908 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
909 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
911 // If the exponent doesn't shift all bits out of the mantissa
913 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
914 APInt(width, mantissa >> (52 - exp));
916 // If the client didn't provide enough bits for us to shift the mantissa into
917 // then the result is undefined, just return 0
918 if (width <= exp - 52)
919 return APInt(width, 0);
921 // Otherwise, we have to shift the mantissa bits up to the right location
922 APInt Tmp(width, mantissa);
923 Tmp = Tmp.shl((unsigned)exp - 52);
924 return isNeg ? -Tmp : Tmp;
927 /// RoundToDouble - This function converts this APInt to a double.
928 /// The layout for double is as following (IEEE Standard 754):
929 /// --------------------------------------
930 /// | Sign Exponent Fraction Bias |
931 /// |-------------------------------------- |
932 /// | 1[63] 11[62-52] 52[51-00] 1023 |
933 /// --------------------------------------
934 double APInt::roundToDouble(bool isSigned) const {
936 // Handle the simple case where the value is contained in one uint64_t.
937 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
938 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
940 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
943 return double(getWord(0));
946 // Determine if the value is negative.
947 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
949 // Construct the absolute value if we're negative.
950 APInt Tmp(isNeg ? -(*this) : (*this));
952 // Figure out how many bits we're using.
953 unsigned n = Tmp.getActiveBits();
955 // The exponent (without bias normalization) is just the number of bits
956 // we are using. Note that the sign bit is gone since we constructed the
960 // Return infinity for exponent overflow
962 if (!isSigned || !isNeg)
963 return std::numeric_limits<double>::infinity();
965 return -std::numeric_limits<double>::infinity();
967 exp += 1023; // Increment for 1023 bias
969 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
970 // extract the high 52 bits from the correct words in pVal.
972 unsigned hiWord = whichWord(n-1);
974 mantissa = Tmp.pVal[0];
976 mantissa >>= n - 52; // shift down, we want the top 52 bits.
978 assert(hiWord > 0 && "huh?");
979 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
980 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
981 mantissa = hibits | lobits;
984 // The leading bit of mantissa is implicit, so get rid of it.
985 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
990 T.I = sign | (exp << 52) | mantissa;
994 // Truncate to new width.
995 APInt &APInt::trunc(unsigned width) {
996 assert(width < BitWidth && "Invalid APInt Truncate request");
997 assert(width && "Can't truncate to 0 bits");
998 unsigned wordsBefore = getNumWords();
1000 unsigned wordsAfter = getNumWords();
1001 if (wordsBefore != wordsAfter) {
1002 if (wordsAfter == 1) {
1003 uint64_t *tmp = pVal;
1007 uint64_t *newVal = getClearedMemory(wordsAfter);
1008 for (unsigned i = 0; i < wordsAfter; ++i)
1009 newVal[i] = pVal[i];
1014 return clearUnusedBits();
1017 // Sign extend to a new width.
1018 APInt &APInt::sext(unsigned width) {
1019 assert(width > BitWidth && "Invalid APInt SignExtend request");
1020 // If the sign bit isn't set, this is the same as zext.
1021 if (!isNegative()) {
1026 // The sign bit is set. First, get some facts
1027 unsigned wordsBefore = getNumWords();
1028 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
1030 unsigned wordsAfter = getNumWords();
1032 // Mask the high order word appropriately
1033 if (wordsBefore == wordsAfter) {
1034 unsigned newWordBits = width % APINT_BITS_PER_WORD;
1035 // The extension is contained to the wordsBefore-1th word.
1036 uint64_t mask = ~0ULL;
1038 mask >>= APINT_BITS_PER_WORD - newWordBits;
1040 if (wordsBefore == 1)
1043 pVal[wordsBefore-1] |= mask;
1044 return clearUnusedBits();
1047 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1048 uint64_t *newVal = getMemory(wordsAfter);
1049 if (wordsBefore == 1)
1050 newVal[0] = VAL | mask;
1052 for (unsigned i = 0; i < wordsBefore; ++i)
1053 newVal[i] = pVal[i];
1054 newVal[wordsBefore-1] |= mask;
1056 for (unsigned i = wordsBefore; i < wordsAfter; i++)
1058 if (wordsBefore != 1)
1061 return clearUnusedBits();
1064 // Zero extend to a new width.
1065 APInt &APInt::zext(unsigned width) {
1066 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1067 unsigned wordsBefore = getNumWords();
1069 unsigned wordsAfter = getNumWords();
1070 if (wordsBefore != wordsAfter) {
1071 uint64_t *newVal = getClearedMemory(wordsAfter);
1072 if (wordsBefore == 1)
1075 for (unsigned i = 0; i < wordsBefore; ++i)
1076 newVal[i] = pVal[i];
1077 if (wordsBefore != 1)
1084 APInt &APInt::zextOrTrunc(unsigned width) {
1085 if (BitWidth < width)
1087 if (BitWidth > width)
1088 return trunc(width);
1092 APInt &APInt::sextOrTrunc(unsigned width) {
1093 if (BitWidth < width)
1095 if (BitWidth > width)
1096 return trunc(width);
1100 /// Arithmetic right-shift this APInt by shiftAmt.
1101 /// @brief Arithmetic right-shift function.
1102 APInt APInt::ashr(const APInt &shiftAmt) const {
1103 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1106 /// Arithmetic right-shift this APInt by shiftAmt.
1107 /// @brief Arithmetic right-shift function.
1108 APInt APInt::ashr(unsigned shiftAmt) const {
1109 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1110 // Handle a degenerate case
1114 // Handle single word shifts with built-in ashr
1115 if (isSingleWord()) {
1116 if (shiftAmt == BitWidth)
1117 return APInt(BitWidth, 0); // undefined
1119 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1120 return APInt(BitWidth,
1121 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1125 // If all the bits were shifted out, the result is, technically, undefined.
1126 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1127 // issues in the algorithm below.
1128 if (shiftAmt == BitWidth) {
1130 return APInt(BitWidth, -1ULL, true);
1132 return APInt(BitWidth, 0);
1135 // Create some space for the result.
1136 uint64_t * val = new uint64_t[getNumWords()];
1138 // Compute some values needed by the following shift algorithms
1139 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1140 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1141 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1142 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1143 if (bitsInWord == 0)
1144 bitsInWord = APINT_BITS_PER_WORD;
1146 // If we are shifting whole words, just move whole words
1147 if (wordShift == 0) {
1148 // Move the words containing significant bits
1149 for (unsigned i = 0; i <= breakWord; ++i)
1150 val[i] = pVal[i+offset]; // move whole word
1152 // Adjust the top significant word for sign bit fill, if negative
1154 if (bitsInWord < APINT_BITS_PER_WORD)
1155 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1157 // Shift the low order words
1158 for (unsigned i = 0; i < breakWord; ++i) {
1159 // This combines the shifted corresponding word with the low bits from
1160 // the next word (shifted into this word's high bits).
1161 val[i] = (pVal[i+offset] >> wordShift) |
1162 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1165 // Shift the break word. In this case there are no bits from the next word
1166 // to include in this word.
1167 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1169 // Deal with sign extenstion in the break word, and possibly the word before
1172 if (wordShift > bitsInWord) {
1175 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1176 val[breakWord] |= ~0ULL;
1178 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1182 // Remaining words are 0 or -1, just assign them.
1183 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1184 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1186 return APInt(val, BitWidth).clearUnusedBits();
1189 /// Logical right-shift this APInt by shiftAmt.
1190 /// @brief Logical right-shift function.
1191 APInt APInt::lshr(const APInt &shiftAmt) const {
1192 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1195 /// Logical right-shift this APInt by shiftAmt.
1196 /// @brief Logical right-shift function.
1197 APInt APInt::lshr(unsigned shiftAmt) const {
1198 if (isSingleWord()) {
1199 if (shiftAmt == BitWidth)
1200 return APInt(BitWidth, 0);
1202 return APInt(BitWidth, this->VAL >> shiftAmt);
1205 // If all the bits were shifted out, the result is 0. This avoids issues
1206 // with shifting by the size of the integer type, which produces undefined
1207 // results. We define these "undefined results" to always be 0.
1208 if (shiftAmt == BitWidth)
1209 return APInt(BitWidth, 0);
1211 // If none of the bits are shifted out, the result is *this. This avoids
1212 // issues with shifting by the size of the integer type, which produces
1213 // undefined results in the code below. This is also an optimization.
1217 // Create some space for the result.
1218 uint64_t * val = new uint64_t[getNumWords()];
1220 // If we are shifting less than a word, compute the shift with a simple carry
1221 if (shiftAmt < APINT_BITS_PER_WORD) {
1223 for (int i = getNumWords()-1; i >= 0; --i) {
1224 val[i] = (pVal[i] >> shiftAmt) | carry;
1225 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1227 return APInt(val, BitWidth).clearUnusedBits();
1230 // Compute some values needed by the remaining shift algorithms
1231 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1232 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1234 // If we are shifting whole words, just move whole words
1235 if (wordShift == 0) {
1236 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1237 val[i] = pVal[i+offset];
1238 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1240 return APInt(val,BitWidth).clearUnusedBits();
1243 // Shift the low order words
1244 unsigned breakWord = getNumWords() - offset -1;
1245 for (unsigned i = 0; i < breakWord; ++i)
1246 val[i] = (pVal[i+offset] >> wordShift) |
1247 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1248 // Shift the break word.
1249 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1251 // Remaining words are 0
1252 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1254 return APInt(val, BitWidth).clearUnusedBits();
1257 /// Left-shift this APInt by shiftAmt.
1258 /// @brief Left-shift function.
1259 APInt APInt::shl(const APInt &shiftAmt) const {
1260 // It's undefined behavior in C to shift by BitWidth or greater.
1261 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1264 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1265 // If all the bits were shifted out, the result is 0. This avoids issues
1266 // with shifting by the size of the integer type, which produces undefined
1267 // results. We define these "undefined results" to always be 0.
1268 if (shiftAmt == BitWidth)
1269 return APInt(BitWidth, 0);
1271 // If none of the bits are shifted out, the result is *this. This avoids a
1272 // lshr by the words size in the loop below which can produce incorrect
1273 // results. It also avoids the expensive computation below for a common case.
1277 // Create some space for the result.
1278 uint64_t * val = new uint64_t[getNumWords()];
1280 // If we are shifting less than a word, do it the easy way
1281 if (shiftAmt < APINT_BITS_PER_WORD) {
1283 for (unsigned i = 0; i < getNumWords(); i++) {
1284 val[i] = pVal[i] << shiftAmt | carry;
1285 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1287 return APInt(val, BitWidth).clearUnusedBits();
1290 // Compute some values needed by the remaining shift algorithms
1291 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1292 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1294 // If we are shifting whole words, just move whole words
1295 if (wordShift == 0) {
1296 for (unsigned i = 0; i < offset; i++)
1298 for (unsigned i = offset; i < getNumWords(); i++)
1299 val[i] = pVal[i-offset];
1300 return APInt(val,BitWidth).clearUnusedBits();
1303 // Copy whole words from this to Result.
1304 unsigned i = getNumWords() - 1;
1305 for (; i > offset; --i)
1306 val[i] = pVal[i-offset] << wordShift |
1307 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1308 val[offset] = pVal[0] << wordShift;
1309 for (i = 0; i < offset; ++i)
1311 return APInt(val, BitWidth).clearUnusedBits();
1314 APInt APInt::rotl(const APInt &rotateAmt) const {
1315 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1318 APInt APInt::rotl(unsigned rotateAmt) const {
1321 // Don't get too fancy, just use existing shift/or facilities
1325 lo.lshr(BitWidth - rotateAmt);
1329 APInt APInt::rotr(const APInt &rotateAmt) const {
1330 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1333 APInt APInt::rotr(unsigned rotateAmt) const {
1336 // Don't get too fancy, just use existing shift/or facilities
1340 hi.shl(BitWidth - rotateAmt);
1344 // Square Root - this method computes and returns the square root of "this".
1345 // Three mechanisms are used for computation. For small values (<= 5 bits),
1346 // a table lookup is done. This gets some performance for common cases. For
1347 // values using less than 52 bits, the value is converted to double and then
1348 // the libc sqrt function is called. The result is rounded and then converted
1349 // back to a uint64_t which is then used to construct the result. Finally,
1350 // the Babylonian method for computing square roots is used.
1351 APInt APInt::sqrt() const {
1353 // Determine the magnitude of the value.
1354 unsigned magnitude = getActiveBits();
1356 // Use a fast table for some small values. This also gets rid of some
1357 // rounding errors in libc sqrt for small values.
1358 if (magnitude <= 5) {
1359 static const uint8_t results[32] = {
1362 /* 3- 6 */ 2, 2, 2, 2,
1363 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1364 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1365 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1368 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1371 // If the magnitude of the value fits in less than 52 bits (the precision of
1372 // an IEEE double precision floating point value), then we can use the
1373 // libc sqrt function which will probably use a hardware sqrt computation.
1374 // This should be faster than the algorithm below.
1375 if (magnitude < 52) {
1377 // Amazingly, VC++ doesn't have round().
1378 return APInt(BitWidth,
1379 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1381 return APInt(BitWidth,
1382 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1386 // Okay, all the short cuts are exhausted. We must compute it. The following
1387 // is a classical Babylonian method for computing the square root. This code
1388 // was adapted to APINt from a wikipedia article on such computations.
1389 // See http://www.wikipedia.org/ and go to the page named
1390 // Calculate_an_integer_square_root.
1391 unsigned nbits = BitWidth, i = 4;
1392 APInt testy(BitWidth, 16);
1393 APInt x_old(BitWidth, 1);
1394 APInt x_new(BitWidth, 0);
1395 APInt two(BitWidth, 2);
1397 // Select a good starting value using binary logarithms.
1398 for (;; i += 2, testy = testy.shl(2))
1399 if (i >= nbits || this->ule(testy)) {
1400 x_old = x_old.shl(i / 2);
1404 // Use the Babylonian method to arrive at the integer square root:
1406 x_new = (this->udiv(x_old) + x_old).udiv(two);
1407 if (x_old.ule(x_new))
1412 // Make sure we return the closest approximation
1413 // NOTE: The rounding calculation below is correct. It will produce an
1414 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1415 // determined to be a rounding issue with pari/gp as it begins to use a
1416 // floating point representation after 192 bits. There are no discrepancies
1417 // between this algorithm and pari/gp for bit widths < 192 bits.
1418 APInt square(x_old * x_old);
1419 APInt nextSquare((x_old + 1) * (x_old +1));
1420 if (this->ult(square))
1422 else if (this->ule(nextSquare)) {
1423 APInt midpoint((nextSquare - square).udiv(two));
1424 APInt offset(*this - square);
1425 if (offset.ult(midpoint))
1430 llvm_unreachable("Error in APInt::sqrt computation");
1434 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1435 /// iterative extended Euclidean algorithm is used to solve for this value,
1436 /// however we simplify it to speed up calculating only the inverse, and take
1437 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1438 /// (potentially large) APInts around.
1439 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1440 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1442 // Using the properties listed at the following web page (accessed 06/21/08):
1443 // http://www.numbertheory.org/php/euclid.html
1444 // (especially the properties numbered 3, 4 and 9) it can be proved that
1445 // BitWidth bits suffice for all the computations in the algorithm implemented
1446 // below. More precisely, this number of bits suffice if the multiplicative
1447 // inverse exists, but may not suffice for the general extended Euclidean
1450 APInt r[2] = { modulo, *this };
1451 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1452 APInt q(BitWidth, 0);
1455 for (i = 0; r[i^1] != 0; i ^= 1) {
1456 // An overview of the math without the confusing bit-flipping:
1457 // q = r[i-2] / r[i-1]
1458 // r[i] = r[i-2] % r[i-1]
1459 // t[i] = t[i-2] - t[i-1] * q
1460 udivrem(r[i], r[i^1], q, r[i]);
1464 // If this APInt and the modulo are not coprime, there is no multiplicative
1465 // inverse, so return 0. We check this by looking at the next-to-last
1466 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1469 return APInt(BitWidth, 0);
1471 // The next-to-last t is the multiplicative inverse. However, we are
1472 // interested in a positive inverse. Calcuate a positive one from a negative
1473 // one if necessary. A simple addition of the modulo suffices because
1474 // abs(t[i]) is known to be less than *this/2 (see the link above).
1475 return t[i].isNegative() ? t[i] + modulo : t[i];
1478 /// Calculate the magic numbers required to implement a signed integer division
1479 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1480 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1481 /// Warren, Jr., chapter 10.
1482 APInt::ms APInt::magic() const {
1483 const APInt& d = *this;
1485 APInt ad, anc, delta, q1, r1, q2, r2, t;
1486 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1487 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1488 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1492 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1493 anc = t - 1 - t.urem(ad); // absolute value of nc
1494 p = d.getBitWidth() - 1; // initialize p
1495 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1496 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1497 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1498 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1501 q1 = q1<<1; // update q1 = 2p/abs(nc)
1502 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1503 if (r1.uge(anc)) { // must be unsigned comparison
1507 q2 = q2<<1; // update q2 = 2p/abs(d)
1508 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1509 if (r2.uge(ad)) { // must be unsigned comparison
1514 } while (q1.ule(delta) || (q1 == delta && r1 == 0));
1517 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1518 mag.s = p - d.getBitWidth(); // resulting shift
1522 /// Calculate the magic numbers required to implement an unsigned integer
1523 /// division by a constant as a sequence of multiplies, adds and shifts.
1524 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1525 /// S. Warren, Jr., chapter 10.
1526 APInt::mu APInt::magicu() const {
1527 const APInt& d = *this;
1529 APInt nc, delta, q1, r1, q2, r2;
1531 magu.a = 0; // initialize "add" indicator
1532 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1533 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1534 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1536 nc = allOnes - (-d).urem(d);
1537 p = d.getBitWidth() - 1; // initialize p
1538 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1539 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1540 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1541 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1544 if (r1.uge(nc - r1)) {
1545 q1 = q1 + q1 + 1; // update q1
1546 r1 = r1 + r1 - nc; // update r1
1549 q1 = q1+q1; // update q1
1550 r1 = r1+r1; // update r1
1552 if ((r2 + 1).uge(d - r2)) {
1553 if (q2.uge(signedMax)) magu.a = 1;
1554 q2 = q2+q2 + 1; // update q2
1555 r2 = r2+r2 + 1 - d; // update r2
1558 if (q2.uge(signedMin)) magu.a = 1;
1559 q2 = q2+q2; // update q2
1560 r2 = r2+r2 + 1; // update r2
1563 } while (p < d.getBitWidth()*2 &&
1564 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1565 magu.m = q2 + 1; // resulting magic number
1566 magu.s = p - d.getBitWidth(); // resulting shift
1570 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1571 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1572 /// variables here have the same names as in the algorithm. Comments explain
1573 /// the algorithm and any deviation from it.
1574 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1575 unsigned m, unsigned n) {
1576 assert(u && "Must provide dividend");
1577 assert(v && "Must provide divisor");
1578 assert(q && "Must provide quotient");
1579 assert(u != v && u != q && v != q && "Must us different memory");
1580 assert(n>1 && "n must be > 1");
1582 // Knuth uses the value b as the base of the number system. In our case b
1583 // is 2^31 so we just set it to -1u.
1584 uint64_t b = uint64_t(1) << 32;
1587 DEBUG(errs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1588 DEBUG(errs() << "KnuthDiv: original:");
1589 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1590 DEBUG(errs() << " by");
1591 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1592 DEBUG(errs() << '\n');
1594 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1595 // u and v by d. Note that we have taken Knuth's advice here to use a power
1596 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1597 // 2 allows us to shift instead of multiply and it is easy to determine the
1598 // shift amount from the leading zeros. We are basically normalizing the u
1599 // and v so that its high bits are shifted to the top of v's range without
1600 // overflow. Note that this can require an extra word in u so that u must
1601 // be of length m+n+1.
1602 unsigned shift = CountLeadingZeros_32(v[n-1]);
1603 unsigned v_carry = 0;
1604 unsigned u_carry = 0;
1606 for (unsigned i = 0; i < m+n; ++i) {
1607 unsigned u_tmp = u[i] >> (32 - shift);
1608 u[i] = (u[i] << shift) | u_carry;
1611 for (unsigned i = 0; i < n; ++i) {
1612 unsigned v_tmp = v[i] >> (32 - shift);
1613 v[i] = (v[i] << shift) | v_carry;
1619 DEBUG(errs() << "KnuthDiv: normal:");
1620 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1621 DEBUG(errs() << " by");
1622 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1623 DEBUG(errs() << '\n');
1626 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1629 DEBUG(errs() << "KnuthDiv: quotient digit #" << j << '\n');
1630 // D3. [Calculate q'.].
1631 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1632 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1633 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1634 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1635 // on v[n-2] determines at high speed most of the cases in which the trial
1636 // value qp is one too large, and it eliminates all cases where qp is two
1638 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1639 DEBUG(errs() << "KnuthDiv: dividend == " << dividend << '\n');
1640 uint64_t qp = dividend / v[n-1];
1641 uint64_t rp = dividend % v[n-1];
1642 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1645 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1648 DEBUG(errs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1650 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1651 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1652 // consists of a simple multiplication by a one-place number, combined with
1655 for (unsigned i = 0; i < n; ++i) {
1656 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1657 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1658 bool borrow = subtrahend > u_tmp;
1659 DEBUG(errs() << "KnuthDiv: u_tmp == " << u_tmp
1660 << ", subtrahend == " << subtrahend
1661 << ", borrow = " << borrow << '\n');
1663 uint64_t result = u_tmp - subtrahend;
1665 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1666 u[k++] = (unsigned)(result >> 32); // subtract high word
1667 while (borrow && k <= m+n) { // deal with borrow to the left
1673 DEBUG(errs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1676 DEBUG(errs() << "KnuthDiv: after subtraction:");
1677 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1678 DEBUG(errs() << '\n');
1679 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1680 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1681 // true value plus b**(n+1), namely as the b's complement of
1682 // the true value, and a "borrow" to the left should be remembered.
1685 bool carry = true; // true because b's complement is "complement + 1"
1686 for (unsigned i = 0; i <= m+n; ++i) {
1687 u[i] = ~u[i] + carry; // b's complement
1688 carry = carry && u[i] == 0;
1691 DEBUG(errs() << "KnuthDiv: after complement:");
1692 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1693 DEBUG(errs() << '\n');
1695 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1696 // negative, go to step D6; otherwise go on to step D7.
1697 q[j] = (unsigned)qp;
1699 // D6. [Add back]. The probability that this step is necessary is very
1700 // small, on the order of only 2/b. Make sure that test data accounts for
1701 // this possibility. Decrease q[j] by 1
1703 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1704 // A carry will occur to the left of u[j+n], and it should be ignored
1705 // since it cancels with the borrow that occurred in D4.
1707 for (unsigned i = 0; i < n; i++) {
1708 unsigned limit = std::min(u[j+i],v[i]);
1709 u[j+i] += v[i] + carry;
1710 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1714 DEBUG(errs() << "KnuthDiv: after correction:");
1715 DEBUG(for (int i = m+n; i >=0; i--) errs() <<" " << u[i]);
1716 DEBUG(errs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1718 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1721 DEBUG(errs() << "KnuthDiv: quotient:");
1722 DEBUG(for (int i = m; i >=0; i--) errs() <<" " << q[i]);
1723 DEBUG(errs() << '\n');
1725 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1726 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1727 // compute the remainder (urem uses this).
1729 // The value d is expressed by the "shift" value above since we avoided
1730 // multiplication by d by using a shift left. So, all we have to do is
1731 // shift right here. In order to mak
1734 DEBUG(errs() << "KnuthDiv: remainder:");
1735 for (int i = n-1; i >= 0; i--) {
1736 r[i] = (u[i] >> shift) | carry;
1737 carry = u[i] << (32 - shift);
1738 DEBUG(errs() << " " << r[i]);
1741 for (int i = n-1; i >= 0; i--) {
1743 DEBUG(errs() << " " << r[i]);
1746 DEBUG(errs() << '\n');
1749 DEBUG(errs() << '\n');
1753 void APInt::divide(const APInt LHS, unsigned lhsWords,
1754 const APInt &RHS, unsigned rhsWords,
1755 APInt *Quotient, APInt *Remainder)
1757 assert(lhsWords >= rhsWords && "Fractional result");
1759 // First, compose the values into an array of 32-bit words instead of
1760 // 64-bit words. This is a necessity of both the "short division" algorithm
1761 // and the the Knuth "classical algorithm" which requires there to be native
1762 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1763 // can't use 64-bit operands here because we don't have native results of
1764 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1765 // work on large-endian machines.
1766 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1767 unsigned n = rhsWords * 2;
1768 unsigned m = (lhsWords * 2) - n;
1770 // Allocate space for the temporary values we need either on the stack, if
1771 // it will fit, or on the heap if it won't.
1772 unsigned SPACE[128];
1777 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1780 Q = &SPACE[(m+n+1) + n];
1782 R = &SPACE[(m+n+1) + n + (m+n)];
1784 U = new unsigned[m + n + 1];
1785 V = new unsigned[n];
1786 Q = new unsigned[m+n];
1788 R = new unsigned[n];
1791 // Initialize the dividend
1792 memset(U, 0, (m+n+1)*sizeof(unsigned));
1793 for (unsigned i = 0; i < lhsWords; ++i) {
1794 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1795 U[i * 2] = (unsigned)(tmp & mask);
1796 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1798 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1800 // Initialize the divisor
1801 memset(V, 0, (n)*sizeof(unsigned));
1802 for (unsigned i = 0; i < rhsWords; ++i) {
1803 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1804 V[i * 2] = (unsigned)(tmp & mask);
1805 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1808 // initialize the quotient and remainder
1809 memset(Q, 0, (m+n) * sizeof(unsigned));
1811 memset(R, 0, n * sizeof(unsigned));
1813 // Now, adjust m and n for the Knuth division. n is the number of words in
1814 // the divisor. m is the number of words by which the dividend exceeds the
1815 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1816 // contain any zero words or the Knuth algorithm fails.
1817 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1821 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1824 // If we're left with only a single word for the divisor, Knuth doesn't work
1825 // so we implement the short division algorithm here. This is much simpler
1826 // and faster because we are certain that we can divide a 64-bit quantity
1827 // by a 32-bit quantity at hardware speed and short division is simply a
1828 // series of such operations. This is just like doing short division but we
1829 // are using base 2^32 instead of base 10.
1830 assert(n != 0 && "Divide by zero?");
1832 unsigned divisor = V[0];
1833 unsigned remainder = 0;
1834 for (int i = m+n-1; i >= 0; i--) {
1835 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1836 if (partial_dividend == 0) {
1839 } else if (partial_dividend < divisor) {
1841 remainder = (unsigned)partial_dividend;
1842 } else if (partial_dividend == divisor) {
1846 Q[i] = (unsigned)(partial_dividend / divisor);
1847 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1853 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1855 KnuthDiv(U, V, Q, R, m, n);
1858 // If the caller wants the quotient
1860 // Set up the Quotient value's memory.
1861 if (Quotient->BitWidth != LHS.BitWidth) {
1862 if (Quotient->isSingleWord())
1865 delete [] Quotient->pVal;
1866 Quotient->BitWidth = LHS.BitWidth;
1867 if (!Quotient->isSingleWord())
1868 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1872 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1874 if (lhsWords == 1) {
1876 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1877 if (Quotient->isSingleWord())
1878 Quotient->VAL = tmp;
1880 Quotient->pVal[0] = tmp;
1882 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1883 for (unsigned i = 0; i < lhsWords; ++i)
1885 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1889 // If the caller wants the remainder
1891 // Set up the Remainder value's memory.
1892 if (Remainder->BitWidth != RHS.BitWidth) {
1893 if (Remainder->isSingleWord())
1896 delete [] Remainder->pVal;
1897 Remainder->BitWidth = RHS.BitWidth;
1898 if (!Remainder->isSingleWord())
1899 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1903 // The remainder is in R. Reconstitute the remainder into Remainder's low
1905 if (rhsWords == 1) {
1907 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1908 if (Remainder->isSingleWord())
1909 Remainder->VAL = tmp;
1911 Remainder->pVal[0] = tmp;
1913 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1914 for (unsigned i = 0; i < rhsWords; ++i)
1915 Remainder->pVal[i] =
1916 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1920 // Clean up the memory we allocated.
1921 if (U != &SPACE[0]) {
1929 APInt APInt::udiv(const APInt& RHS) const {
1930 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1932 // First, deal with the easy case
1933 if (isSingleWord()) {
1934 assert(RHS.VAL != 0 && "Divide by zero?");
1935 return APInt(BitWidth, VAL / RHS.VAL);
1938 // Get some facts about the LHS and RHS number of bits and words
1939 unsigned rhsBits = RHS.getActiveBits();
1940 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1941 assert(rhsWords && "Divided by zero???");
1942 unsigned lhsBits = this->getActiveBits();
1943 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1945 // Deal with some degenerate cases
1948 return APInt(BitWidth, 0);
1949 else if (lhsWords < rhsWords || this->ult(RHS)) {
1950 // X / Y ===> 0, iff X < Y
1951 return APInt(BitWidth, 0);
1952 } else if (*this == RHS) {
1954 return APInt(BitWidth, 1);
1955 } else if (lhsWords == 1 && rhsWords == 1) {
1956 // All high words are zero, just use native divide
1957 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1960 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1961 APInt Quotient(1,0); // to hold result.
1962 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1966 APInt APInt::urem(const APInt& RHS) const {
1967 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1968 if (isSingleWord()) {
1969 assert(RHS.VAL != 0 && "Remainder by zero?");
1970 return APInt(BitWidth, VAL % RHS.VAL);
1973 // Get some facts about the LHS
1974 unsigned lhsBits = getActiveBits();
1975 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1977 // Get some facts about the RHS
1978 unsigned rhsBits = RHS.getActiveBits();
1979 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1980 assert(rhsWords && "Performing remainder operation by zero ???");
1982 // Check the degenerate cases
1983 if (lhsWords == 0) {
1985 return APInt(BitWidth, 0);
1986 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1987 // X % Y ===> X, iff X < Y
1989 } else if (*this == RHS) {
1991 return APInt(BitWidth, 0);
1992 } else if (lhsWords == 1) {
1993 // All high words are zero, just use native remainder
1994 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1997 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1998 APInt Remainder(1,0);
1999 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2003 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2004 APInt &Quotient, APInt &Remainder) {
2005 // Get some size facts about the dividend and divisor
2006 unsigned lhsBits = LHS.getActiveBits();
2007 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2008 unsigned rhsBits = RHS.getActiveBits();
2009 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2011 // Check the degenerate cases
2012 if (lhsWords == 0) {
2013 Quotient = 0; // 0 / Y ===> 0
2014 Remainder = 0; // 0 % Y ===> 0
2018 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2019 Quotient = 0; // X / Y ===> 0, iff X < Y
2020 Remainder = LHS; // X % Y ===> X, iff X < Y
2025 Quotient = 1; // X / X ===> 1
2026 Remainder = 0; // X % X ===> 0;
2030 if (lhsWords == 1 && rhsWords == 1) {
2031 // There is only one word to consider so use the native versions.
2032 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2033 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2034 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2035 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2039 // Okay, lets do it the long way
2040 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2043 void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) {
2044 // Check our assumptions here
2045 assert(!str.empty() && "Invalid string length");
2046 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2047 "Radix should be 2, 8, 10, or 16!");
2049 StringRef::iterator p = str.begin();
2050 size_t slen = str.size();
2051 bool isNeg = *p == '-';
2052 if (*p == '-' || *p == '+') {
2055 assert(slen && "string is only a minus!");
2057 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2058 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2059 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2060 assert((((slen-1)*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
2063 if (!isSingleWord())
2064 pVal = getClearedMemory(getNumWords());
2066 // Figure out if we can shift instead of multiply
2067 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2069 // Set up an APInt for the digit to add outside the loop so we don't
2070 // constantly construct/destruct it.
2071 APInt apdigit(getBitWidth(), 0);
2072 APInt apradix(getBitWidth(), radix);
2074 // Enter digit traversal loop
2075 for (StringRef::iterator e = str.end(); p != e; ++p) {
2076 unsigned digit = getDigit(*p, radix);
2078 // Shift or multiply the value by the radix
2086 // Add in the digit we just interpreted
2087 if (apdigit.isSingleWord())
2088 apdigit.VAL = digit;
2090 apdigit.pVal[0] = digit;
2093 // If its negative, put it in two's complement form
2100 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2101 bool Signed) const {
2102 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2103 "Radix should be 2, 8, 10, or 16!");
2105 // First, check for a zero value and just short circuit the logic below.
2111 static const char Digits[] = "0123456789ABCDEF";
2113 if (isSingleWord()) {
2115 char *BufPtr = Buffer+65;
2119 int64_t I = getSExtValue();
2130 *--BufPtr = Digits[N % Radix];
2133 Str.append(BufPtr, Buffer+65);
2139 if (Signed && isNegative()) {
2140 // They want to print the signed version and it is a negative value
2141 // Flip the bits and add one to turn it into the equivalent positive
2142 // value and put a '-' in the result.
2148 // We insert the digits backward, then reverse them to get the right order.
2149 unsigned StartDig = Str.size();
2151 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2152 // because the number of bits per digit (1, 3 and 4 respectively) divides
2153 // equaly. We just shift until the value is zero.
2155 // Just shift tmp right for each digit width until it becomes zero
2156 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2157 unsigned MaskAmt = Radix - 1;
2160 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2161 Str.push_back(Digits[Digit]);
2162 Tmp = Tmp.lshr(ShiftAmt);
2165 APInt divisor(4, 10);
2167 APInt APdigit(1, 0);
2168 APInt tmp2(Tmp.getBitWidth(), 0);
2169 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2171 unsigned Digit = (unsigned)APdigit.getZExtValue();
2172 assert(Digit < Radix && "divide failed");
2173 Str.push_back(Digits[Digit]);
2178 // Reverse the digits before returning.
2179 std::reverse(Str.begin()+StartDig, Str.end());
2182 /// toString - This returns the APInt as a std::string. Note that this is an
2183 /// inefficient method. It is better to pass in a SmallVector/SmallString
2184 /// to the methods above.
2185 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2187 toString(S, Radix, Signed);
2192 void APInt::dump() const {
2193 SmallString<40> S, U;
2194 this->toStringUnsigned(U);
2195 this->toStringSigned(S);
2196 errs() << "APInt(" << BitWidth << "b, "
2197 << U.str() << "u " << S.str() << "s)";
2200 void APInt::print(raw_ostream &OS, bool isSigned) const {
2202 this->toString(S, 10, isSigned);
2206 std::ostream &llvm::operator<<(std::ostream &o, const APInt &I) {
2207 raw_os_ostream OS(o);
2212 // This implements a variety of operations on a representation of
2213 // arbitrary precision, two's-complement, bignum integer values.
2215 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2216 and unrestricting assumption. */
2217 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2218 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2220 /* Some handy functions local to this file. */
2223 /* Returns the integer part with the least significant BITS set.
2224 BITS cannot be zero. */
2225 static inline integerPart
2226 lowBitMask(unsigned int bits)
2228 assert (bits != 0 && bits <= integerPartWidth);
2230 return ~(integerPart) 0 >> (integerPartWidth - bits);
2233 /* Returns the value of the lower half of PART. */
2234 static inline integerPart
2235 lowHalf(integerPart part)
2237 return part & lowBitMask(integerPartWidth / 2);
2240 /* Returns the value of the upper half of PART. */
2241 static inline integerPart
2242 highHalf(integerPart part)
2244 return part >> (integerPartWidth / 2);
2247 /* Returns the bit number of the most significant set bit of a part.
2248 If the input number has no bits set -1U is returned. */
2250 partMSB(integerPart value)
2252 unsigned int n, msb;
2257 n = integerPartWidth / 2;
2272 /* Returns the bit number of the least significant set bit of a
2273 part. If the input number has no bits set -1U is returned. */
2275 partLSB(integerPart value)
2277 unsigned int n, lsb;
2282 lsb = integerPartWidth - 1;
2283 n = integerPartWidth / 2;
2298 /* Sets the least significant part of a bignum to the input value, and
2299 zeroes out higher parts. */
2301 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2308 for(i = 1; i < parts; i++)
2312 /* Assign one bignum to another. */
2314 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2318 for(i = 0; i < parts; i++)
2322 /* Returns true if a bignum is zero, false otherwise. */
2324 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2328 for(i = 0; i < parts; i++)
2335 /* Extract the given bit of a bignum; returns 0 or 1. */
2337 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2339 return(parts[bit / integerPartWidth]
2340 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2343 /* Set the given bit of a bignum. */
2345 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2347 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2350 /* Returns the bit number of the least significant set bit of a
2351 number. If the input number has no bits set -1U is returned. */
2353 APInt::tcLSB(const integerPart *parts, unsigned int n)
2355 unsigned int i, lsb;
2357 for(i = 0; i < n; i++) {
2358 if (parts[i] != 0) {
2359 lsb = partLSB(parts[i]);
2361 return lsb + i * integerPartWidth;
2368 /* Returns the bit number of the most significant set bit of a number.
2369 If the input number has no bits set -1U is returned. */
2371 APInt::tcMSB(const integerPart *parts, unsigned int n)
2378 if (parts[n] != 0) {
2379 msb = partMSB(parts[n]);
2381 return msb + n * integerPartWidth;
2388 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2389 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2390 the least significant bit of DST. All high bits above srcBITS in
2391 DST are zero-filled. */
2393 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2394 unsigned int srcBits, unsigned int srcLSB)
2396 unsigned int firstSrcPart, dstParts, shift, n;
2398 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2399 assert (dstParts <= dstCount);
2401 firstSrcPart = srcLSB / integerPartWidth;
2402 tcAssign (dst, src + firstSrcPart, dstParts);
2404 shift = srcLSB % integerPartWidth;
2405 tcShiftRight (dst, dstParts, shift);
2407 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2408 in DST. If this is less that srcBits, append the rest, else
2409 clear the high bits. */
2410 n = dstParts * integerPartWidth - shift;
2412 integerPart mask = lowBitMask (srcBits - n);
2413 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2414 << n % integerPartWidth);
2415 } else if (n > srcBits) {
2416 if (srcBits % integerPartWidth)
2417 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2420 /* Clear high parts. */
2421 while (dstParts < dstCount)
2422 dst[dstParts++] = 0;
2425 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2427 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2428 integerPart c, unsigned int parts)
2434 for(i = 0; i < parts; i++) {
2439 dst[i] += rhs[i] + 1;
2450 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2452 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2453 integerPart c, unsigned int parts)
2459 for(i = 0; i < parts; i++) {
2464 dst[i] -= rhs[i] + 1;
2475 /* Negate a bignum in-place. */
2477 APInt::tcNegate(integerPart *dst, unsigned int parts)
2479 tcComplement(dst, parts);
2480 tcIncrement(dst, parts);
2483 /* DST += SRC * MULTIPLIER + CARRY if add is true
2484 DST = SRC * MULTIPLIER + CARRY if add is false
2486 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2487 they must start at the same point, i.e. DST == SRC.
2489 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2490 returned. Otherwise DST is filled with the least significant
2491 DSTPARTS parts of the result, and if all of the omitted higher
2492 parts were zero return zero, otherwise overflow occurred and
2495 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2496 integerPart multiplier, integerPart carry,
2497 unsigned int srcParts, unsigned int dstParts,
2502 /* Otherwise our writes of DST kill our later reads of SRC. */
2503 assert(dst <= src || dst >= src + srcParts);
2504 assert(dstParts <= srcParts + 1);
2506 /* N loops; minimum of dstParts and srcParts. */
2507 n = dstParts < srcParts ? dstParts: srcParts;
2509 for(i = 0; i < n; i++) {
2510 integerPart low, mid, high, srcPart;
2512 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2514 This cannot overflow, because
2516 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2518 which is less than n^2. */
2522 if (multiplier == 0 || srcPart == 0) {
2526 low = lowHalf(srcPart) * lowHalf(multiplier);
2527 high = highHalf(srcPart) * highHalf(multiplier);
2529 mid = lowHalf(srcPart) * highHalf(multiplier);
2530 high += highHalf(mid);
2531 mid <<= integerPartWidth / 2;
2532 if (low + mid < low)
2536 mid = highHalf(srcPart) * lowHalf(multiplier);
2537 high += highHalf(mid);
2538 mid <<= integerPartWidth / 2;
2539 if (low + mid < low)
2543 /* Now add carry. */
2544 if (low + carry < low)
2550 /* And now DST[i], and store the new low part there. */
2551 if (low + dst[i] < low)
2561 /* Full multiplication, there is no overflow. */
2562 assert(i + 1 == dstParts);
2566 /* We overflowed if there is carry. */
2570 /* We would overflow if any significant unwritten parts would be
2571 non-zero. This is true if any remaining src parts are non-zero
2572 and the multiplier is non-zero. */
2574 for(; i < srcParts; i++)
2578 /* We fitted in the narrow destination. */
2583 /* DST = LHS * RHS, where DST has the same width as the operands and
2584 is filled with the least significant parts of the result. Returns
2585 one if overflow occurred, otherwise zero. DST must be disjoint
2586 from both operands. */
2588 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2589 const integerPart *rhs, unsigned int parts)
2594 assert(dst != lhs && dst != rhs);
2597 tcSet(dst, 0, parts);
2599 for(i = 0; i < parts; i++)
2600 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2606 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2607 operands. No overflow occurs. DST must be disjoint from both
2608 operands. Returns the number of parts required to hold the
2611 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2612 const integerPart *rhs, unsigned int lhsParts,
2613 unsigned int rhsParts)
2615 /* Put the narrower number on the LHS for less loops below. */
2616 if (lhsParts > rhsParts) {
2617 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2621 assert(dst != lhs && dst != rhs);
2623 tcSet(dst, 0, rhsParts);
2625 for(n = 0; n < lhsParts; n++)
2626 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2628 n = lhsParts + rhsParts;
2630 return n - (dst[n - 1] == 0);
2634 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2635 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2636 set REMAINDER to the remainder, return zero. i.e.
2638 OLD_LHS = RHS * LHS + REMAINDER
2640 SCRATCH is a bignum of the same size as the operands and result for
2641 use by the routine; its contents need not be initialized and are
2642 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2645 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2646 integerPart *remainder, integerPart *srhs,
2649 unsigned int n, shiftCount;
2652 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2654 shiftCount = tcMSB(rhs, parts) + 1;
2655 if (shiftCount == 0)
2658 shiftCount = parts * integerPartWidth - shiftCount;
2659 n = shiftCount / integerPartWidth;
2660 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2662 tcAssign(srhs, rhs, parts);
2663 tcShiftLeft(srhs, parts, shiftCount);
2664 tcAssign(remainder, lhs, parts);
2665 tcSet(lhs, 0, parts);
2667 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2672 compare = tcCompare(remainder, srhs, parts);
2674 tcSubtract(remainder, srhs, 0, parts);
2678 if (shiftCount == 0)
2681 tcShiftRight(srhs, parts, 1);
2682 if ((mask >>= 1) == 0)
2683 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2689 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2690 There are no restrictions on COUNT. */
2692 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2695 unsigned int jump, shift;
2697 /* Jump is the inter-part jump; shift is is intra-part shift. */
2698 jump = count / integerPartWidth;
2699 shift = count % integerPartWidth;
2701 while (parts > jump) {
2706 /* dst[i] comes from the two parts src[i - jump] and, if we have
2707 an intra-part shift, src[i - jump - 1]. */
2708 part = dst[parts - jump];
2711 if (parts >= jump + 1)
2712 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2723 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2724 zero. There are no restrictions on COUNT. */
2726 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2729 unsigned int i, jump, shift;
2731 /* Jump is the inter-part jump; shift is is intra-part shift. */
2732 jump = count / integerPartWidth;
2733 shift = count % integerPartWidth;
2735 /* Perform the shift. This leaves the most significant COUNT bits
2736 of the result at zero. */
2737 for(i = 0; i < parts; i++) {
2740 if (i + jump >= parts) {
2743 part = dst[i + jump];
2746 if (i + jump + 1 < parts)
2747 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2756 /* Bitwise and of two bignums. */
2758 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2762 for(i = 0; i < parts; i++)
2766 /* Bitwise inclusive or of two bignums. */
2768 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2772 for(i = 0; i < parts; i++)
2776 /* Bitwise exclusive or of two bignums. */
2778 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2782 for(i = 0; i < parts; i++)
2786 /* Complement a bignum in-place. */
2788 APInt::tcComplement(integerPart *dst, unsigned int parts)
2792 for(i = 0; i < parts; i++)
2796 /* Comparison (unsigned) of two bignums. */
2798 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2803 if (lhs[parts] == rhs[parts])
2806 if (lhs[parts] > rhs[parts])
2815 /* Increment a bignum in-place, return the carry flag. */
2817 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2821 for(i = 0; i < parts; i++)
2828 /* Set the least significant BITS bits of a bignum, clear the
2831 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2837 while (bits > integerPartWidth) {
2838 dst[i++] = ~(integerPart) 0;
2839 bits -= integerPartWidth;
2843 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);