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 it's negative.
627 StringRef::iterator p = str.begin();
628 unsigned isNegative = *p == '-';
629 if (*p == '-' || *p == '+') {
632 assert(slen && "String is only a sign, needs a value.");
635 // For radixes of power-of-two values, the bits required is accurately and
638 return slen + isNegative;
640 return slen * 3 + isNegative;
642 return slen * 4 + isNegative;
644 // This is grossly inefficient but accurate. We could probably do something
645 // with a computation of roughly slen*64/20 and then adjust by the value of
646 // the first few digits. But, I'm not sure how accurate that could be.
648 // Compute a sufficient number of bits that is always large enough but might
649 // be too large. This avoids the assertion in the constructor. This
650 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
651 // bits in that case.
652 unsigned sufficient = slen == 1 ? 4 : slen * 64/18;
654 // Convert to the actual binary value.
655 APInt tmp(sufficient, StringRef(p, slen), radix);
657 // Compute how many bits are required. If the log is infinite, assume we need
659 unsigned log = tmp.logBase2();
660 if (log == (unsigned)-1) {
661 return isNegative + 1;
663 return isNegative + log + 1;
667 // From http://www.burtleburtle.net, byBob Jenkins.
668 // When targeting x86, both GCC and LLVM seem to recognize this as a
669 // rotate instruction.
670 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
672 // From http://www.burtleburtle.net, by Bob Jenkins.
675 a -= c; a ^= rot(c, 4); c += b; \
676 b -= a; b ^= rot(a, 6); a += c; \
677 c -= b; c ^= rot(b, 8); b += a; \
678 a -= c; a ^= rot(c,16); c += b; \
679 b -= a; b ^= rot(a,19); a += c; \
680 c -= b; c ^= rot(b, 4); b += a; \
683 // From http://www.burtleburtle.net, by Bob Jenkins.
684 #define final(a,b,c) \
686 c ^= b; c -= rot(b,14); \
687 a ^= c; a -= rot(c,11); \
688 b ^= a; b -= rot(a,25); \
689 c ^= b; c -= rot(b,16); \
690 a ^= c; a -= rot(c,4); \
691 b ^= a; b -= rot(a,14); \
692 c ^= b; c -= rot(b,24); \
695 // hashword() was adapted from http://www.burtleburtle.net, by Bob
696 // Jenkins. k is a pointer to an array of uint32_t values; length is
697 // the length of the key, in 32-bit chunks. This version only handles
698 // keys that are a multiple of 32 bits in size.
699 static inline uint32_t hashword(const uint64_t *k64, size_t length)
701 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
704 /* Set up the internal state */
705 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
707 /*------------------------------------------------- handle most of the key */
718 /*------------------------------------------- handle the last 3 uint32_t's */
719 switch (length) { /* all the case statements fall through */
724 case 0: /* case 0: nothing left to add */
727 /*------------------------------------------------------ report the result */
731 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
732 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
733 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
734 // function into about 35 instructions when inlined.
735 static inline uint32_t hashword8(const uint64_t k64)
738 a = b = c = 0xdeadbeef + 4;
740 a += k64 & 0xffffffff;
748 uint64_t APInt::getHashValue() const {
751 hash = hashword8(VAL);
753 hash = hashword(pVal, getNumWords()*2);
757 /// HiBits - This function returns the high "numBits" bits of this APInt.
758 APInt APInt::getHiBits(unsigned numBits) const {
759 return APIntOps::lshr(*this, BitWidth - numBits);
762 /// LoBits - This function returns the low "numBits" bits of this APInt.
763 APInt APInt::getLoBits(unsigned numBits) const {
764 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
768 bool APInt::isPowerOf2() const {
769 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
772 unsigned APInt::countLeadingZerosSlowCase() const {
774 for (unsigned i = getNumWords(); i > 0u; --i) {
776 Count += APINT_BITS_PER_WORD;
778 Count += CountLeadingZeros_64(pVal[i-1]);
782 unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
784 Count -= APINT_BITS_PER_WORD - remainder;
785 return std::min(Count, BitWidth);
788 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
792 while (V && (V & (1ULL << 63))) {
799 unsigned APInt::countLeadingOnes() const {
801 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
803 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
806 highWordBits = APINT_BITS_PER_WORD;
809 shift = APINT_BITS_PER_WORD - highWordBits;
811 int i = getNumWords() - 1;
812 unsigned Count = countLeadingOnes_64(pVal[i], shift);
813 if (Count == highWordBits) {
814 for (i--; i >= 0; --i) {
815 if (pVal[i] == -1ULL)
816 Count += APINT_BITS_PER_WORD;
818 Count += countLeadingOnes_64(pVal[i], 0);
826 unsigned APInt::countTrailingZeros() const {
828 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
831 for (; i < getNumWords() && pVal[i] == 0; ++i)
832 Count += APINT_BITS_PER_WORD;
833 if (i < getNumWords())
834 Count += CountTrailingZeros_64(pVal[i]);
835 return std::min(Count, BitWidth);
838 unsigned APInt::countTrailingOnesSlowCase() const {
841 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
842 Count += APINT_BITS_PER_WORD;
843 if (i < getNumWords())
844 Count += CountTrailingOnes_64(pVal[i]);
845 return std::min(Count, BitWidth);
848 unsigned APInt::countPopulationSlowCase() const {
850 for (unsigned i = 0; i < getNumWords(); ++i)
851 Count += CountPopulation_64(pVal[i]);
855 APInt APInt::byteSwap() const {
856 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
858 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
859 else if (BitWidth == 32)
860 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
861 else if (BitWidth == 48) {
862 unsigned Tmp1 = unsigned(VAL >> 16);
863 Tmp1 = ByteSwap_32(Tmp1);
864 uint16_t Tmp2 = uint16_t(VAL);
865 Tmp2 = ByteSwap_16(Tmp2);
866 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
867 } else if (BitWidth == 64)
868 return APInt(BitWidth, ByteSwap_64(VAL));
870 APInt Result(BitWidth, 0);
871 char *pByte = (char*)Result.pVal;
872 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
874 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
875 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
881 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
883 APInt A = API1, B = API2;
886 B = APIntOps::urem(A, B);
892 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
899 // Get the sign bit from the highest order bit
900 bool isNeg = T.I >> 63;
902 // Get the 11-bit exponent and adjust for the 1023 bit bias
903 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
905 // If the exponent is negative, the value is < 0 so just return 0.
907 return APInt(width, 0u);
909 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
910 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
912 // If the exponent doesn't shift all bits out of the mantissa
914 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
915 APInt(width, mantissa >> (52 - exp));
917 // If the client didn't provide enough bits for us to shift the mantissa into
918 // then the result is undefined, just return 0
919 if (width <= exp - 52)
920 return APInt(width, 0);
922 // Otherwise, we have to shift the mantissa bits up to the right location
923 APInt Tmp(width, mantissa);
924 Tmp = Tmp.shl((unsigned)exp - 52);
925 return isNeg ? -Tmp : Tmp;
928 /// RoundToDouble - This function converts this APInt to a double.
929 /// The layout for double is as following (IEEE Standard 754):
930 /// --------------------------------------
931 /// | Sign Exponent Fraction Bias |
932 /// |-------------------------------------- |
933 /// | 1[63] 11[62-52] 52[51-00] 1023 |
934 /// --------------------------------------
935 double APInt::roundToDouble(bool isSigned) const {
937 // Handle the simple case where the value is contained in one uint64_t.
938 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
939 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
941 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
944 return double(getWord(0));
947 // Determine if the value is negative.
948 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
950 // Construct the absolute value if we're negative.
951 APInt Tmp(isNeg ? -(*this) : (*this));
953 // Figure out how many bits we're using.
954 unsigned n = Tmp.getActiveBits();
956 // The exponent (without bias normalization) is just the number of bits
957 // we are using. Note that the sign bit is gone since we constructed the
961 // Return infinity for exponent overflow
963 if (!isSigned || !isNeg)
964 return std::numeric_limits<double>::infinity();
966 return -std::numeric_limits<double>::infinity();
968 exp += 1023; // Increment for 1023 bias
970 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
971 // extract the high 52 bits from the correct words in pVal.
973 unsigned hiWord = whichWord(n-1);
975 mantissa = Tmp.pVal[0];
977 mantissa >>= n - 52; // shift down, we want the top 52 bits.
979 assert(hiWord > 0 && "huh?");
980 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
981 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
982 mantissa = hibits | lobits;
985 // The leading bit of mantissa is implicit, so get rid of it.
986 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
991 T.I = sign | (exp << 52) | mantissa;
995 // Truncate to new width.
996 APInt &APInt::trunc(unsigned width) {
997 assert(width < BitWidth && "Invalid APInt Truncate request");
998 assert(width && "Can't truncate to 0 bits");
999 unsigned wordsBefore = getNumWords();
1001 unsigned wordsAfter = getNumWords();
1002 if (wordsBefore != wordsAfter) {
1003 if (wordsAfter == 1) {
1004 uint64_t *tmp = pVal;
1008 uint64_t *newVal = getClearedMemory(wordsAfter);
1009 for (unsigned i = 0; i < wordsAfter; ++i)
1010 newVal[i] = pVal[i];
1015 return clearUnusedBits();
1018 // Sign extend to a new width.
1019 APInt &APInt::sext(unsigned width) {
1020 assert(width > BitWidth && "Invalid APInt SignExtend request");
1021 // If the sign bit isn't set, this is the same as zext.
1022 if (!isNegative()) {
1027 // The sign bit is set. First, get some facts
1028 unsigned wordsBefore = getNumWords();
1029 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
1031 unsigned wordsAfter = getNumWords();
1033 // Mask the high order word appropriately
1034 if (wordsBefore == wordsAfter) {
1035 unsigned newWordBits = width % APINT_BITS_PER_WORD;
1036 // The extension is contained to the wordsBefore-1th word.
1037 uint64_t mask = ~0ULL;
1039 mask >>= APINT_BITS_PER_WORD - newWordBits;
1041 if (wordsBefore == 1)
1044 pVal[wordsBefore-1] |= mask;
1045 return clearUnusedBits();
1048 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1049 uint64_t *newVal = getMemory(wordsAfter);
1050 if (wordsBefore == 1)
1051 newVal[0] = VAL | mask;
1053 for (unsigned i = 0; i < wordsBefore; ++i)
1054 newVal[i] = pVal[i];
1055 newVal[wordsBefore-1] |= mask;
1057 for (unsigned i = wordsBefore; i < wordsAfter; i++)
1059 if (wordsBefore != 1)
1062 return clearUnusedBits();
1065 // Zero extend to a new width.
1066 APInt &APInt::zext(unsigned width) {
1067 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1068 unsigned wordsBefore = getNumWords();
1070 unsigned wordsAfter = getNumWords();
1071 if (wordsBefore != wordsAfter) {
1072 uint64_t *newVal = getClearedMemory(wordsAfter);
1073 if (wordsBefore == 1)
1076 for (unsigned i = 0; i < wordsBefore; ++i)
1077 newVal[i] = pVal[i];
1078 if (wordsBefore != 1)
1085 APInt &APInt::zextOrTrunc(unsigned width) {
1086 if (BitWidth < width)
1088 if (BitWidth > width)
1089 return trunc(width);
1093 APInt &APInt::sextOrTrunc(unsigned width) {
1094 if (BitWidth < width)
1096 if (BitWidth > width)
1097 return trunc(width);
1101 /// Arithmetic right-shift this APInt by shiftAmt.
1102 /// @brief Arithmetic right-shift function.
1103 APInt APInt::ashr(const APInt &shiftAmt) const {
1104 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1107 /// Arithmetic right-shift this APInt by shiftAmt.
1108 /// @brief Arithmetic right-shift function.
1109 APInt APInt::ashr(unsigned shiftAmt) const {
1110 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1111 // Handle a degenerate case
1115 // Handle single word shifts with built-in ashr
1116 if (isSingleWord()) {
1117 if (shiftAmt == BitWidth)
1118 return APInt(BitWidth, 0); // undefined
1120 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1121 return APInt(BitWidth,
1122 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1126 // If all the bits were shifted out, the result is, technically, undefined.
1127 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1128 // issues in the algorithm below.
1129 if (shiftAmt == BitWidth) {
1131 return APInt(BitWidth, -1ULL, true);
1133 return APInt(BitWidth, 0);
1136 // Create some space for the result.
1137 uint64_t * val = new uint64_t[getNumWords()];
1139 // Compute some values needed by the following shift algorithms
1140 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1141 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1142 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1143 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1144 if (bitsInWord == 0)
1145 bitsInWord = APINT_BITS_PER_WORD;
1147 // If we are shifting whole words, just move whole words
1148 if (wordShift == 0) {
1149 // Move the words containing significant bits
1150 for (unsigned i = 0; i <= breakWord; ++i)
1151 val[i] = pVal[i+offset]; // move whole word
1153 // Adjust the top significant word for sign bit fill, if negative
1155 if (bitsInWord < APINT_BITS_PER_WORD)
1156 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1158 // Shift the low order words
1159 for (unsigned i = 0; i < breakWord; ++i) {
1160 // This combines the shifted corresponding word with the low bits from
1161 // the next word (shifted into this word's high bits).
1162 val[i] = (pVal[i+offset] >> wordShift) |
1163 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1166 // Shift the break word. In this case there are no bits from the next word
1167 // to include in this word.
1168 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1170 // Deal with sign extenstion in the break word, and possibly the word before
1173 if (wordShift > bitsInWord) {
1176 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1177 val[breakWord] |= ~0ULL;
1179 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1183 // Remaining words are 0 or -1, just assign them.
1184 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1185 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1187 return APInt(val, BitWidth).clearUnusedBits();
1190 /// Logical right-shift this APInt by shiftAmt.
1191 /// @brief Logical right-shift function.
1192 APInt APInt::lshr(const APInt &shiftAmt) const {
1193 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1196 /// Logical right-shift this APInt by shiftAmt.
1197 /// @brief Logical right-shift function.
1198 APInt APInt::lshr(unsigned shiftAmt) const {
1199 if (isSingleWord()) {
1200 if (shiftAmt == BitWidth)
1201 return APInt(BitWidth, 0);
1203 return APInt(BitWidth, this->VAL >> shiftAmt);
1206 // If all the bits were shifted out, the result is 0. This avoids issues
1207 // with shifting by the size of the integer type, which produces undefined
1208 // results. We define these "undefined results" to always be 0.
1209 if (shiftAmt == BitWidth)
1210 return APInt(BitWidth, 0);
1212 // If none of the bits are shifted out, the result is *this. This avoids
1213 // issues with shifting by the size of the integer type, which produces
1214 // undefined results in the code below. This is also an optimization.
1218 // Create some space for the result.
1219 uint64_t * val = new uint64_t[getNumWords()];
1221 // If we are shifting less than a word, compute the shift with a simple carry
1222 if (shiftAmt < APINT_BITS_PER_WORD) {
1224 for (int i = getNumWords()-1; i >= 0; --i) {
1225 val[i] = (pVal[i] >> shiftAmt) | carry;
1226 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1228 return APInt(val, BitWidth).clearUnusedBits();
1231 // Compute some values needed by the remaining shift algorithms
1232 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1233 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1235 // If we are shifting whole words, just move whole words
1236 if (wordShift == 0) {
1237 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1238 val[i] = pVal[i+offset];
1239 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1241 return APInt(val,BitWidth).clearUnusedBits();
1244 // Shift the low order words
1245 unsigned breakWord = getNumWords() - offset -1;
1246 for (unsigned i = 0; i < breakWord; ++i)
1247 val[i] = (pVal[i+offset] >> wordShift) |
1248 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1249 // Shift the break word.
1250 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1252 // Remaining words are 0
1253 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1255 return APInt(val, BitWidth).clearUnusedBits();
1258 /// Left-shift this APInt by shiftAmt.
1259 /// @brief Left-shift function.
1260 APInt APInt::shl(const APInt &shiftAmt) const {
1261 // It's undefined behavior in C to shift by BitWidth or greater.
1262 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1265 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1266 // If all the bits were shifted out, the result is 0. This avoids issues
1267 // with shifting by the size of the integer type, which produces undefined
1268 // results. We define these "undefined results" to always be 0.
1269 if (shiftAmt == BitWidth)
1270 return APInt(BitWidth, 0);
1272 // If none of the bits are shifted out, the result is *this. This avoids a
1273 // lshr by the words size in the loop below which can produce incorrect
1274 // results. It also avoids the expensive computation below for a common case.
1278 // Create some space for the result.
1279 uint64_t * val = new uint64_t[getNumWords()];
1281 // If we are shifting less than a word, do it the easy way
1282 if (shiftAmt < APINT_BITS_PER_WORD) {
1284 for (unsigned i = 0; i < getNumWords(); i++) {
1285 val[i] = pVal[i] << shiftAmt | carry;
1286 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1288 return APInt(val, BitWidth).clearUnusedBits();
1291 // Compute some values needed by the remaining shift algorithms
1292 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1293 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1295 // If we are shifting whole words, just move whole words
1296 if (wordShift == 0) {
1297 for (unsigned i = 0; i < offset; i++)
1299 for (unsigned i = offset; i < getNumWords(); i++)
1300 val[i] = pVal[i-offset];
1301 return APInt(val,BitWidth).clearUnusedBits();
1304 // Copy whole words from this to Result.
1305 unsigned i = getNumWords() - 1;
1306 for (; i > offset; --i)
1307 val[i] = pVal[i-offset] << wordShift |
1308 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1309 val[offset] = pVal[0] << wordShift;
1310 for (i = 0; i < offset; ++i)
1312 return APInt(val, BitWidth).clearUnusedBits();
1315 APInt APInt::rotl(const APInt &rotateAmt) const {
1316 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1319 APInt APInt::rotl(unsigned rotateAmt) const {
1322 // Don't get too fancy, just use existing shift/or facilities
1326 lo.lshr(BitWidth - rotateAmt);
1330 APInt APInt::rotr(const APInt &rotateAmt) const {
1331 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1334 APInt APInt::rotr(unsigned rotateAmt) const {
1337 // Don't get too fancy, just use existing shift/or facilities
1341 hi.shl(BitWidth - rotateAmt);
1345 // Square Root - this method computes and returns the square root of "this".
1346 // Three mechanisms are used for computation. For small values (<= 5 bits),
1347 // a table lookup is done. This gets some performance for common cases. For
1348 // values using less than 52 bits, the value is converted to double and then
1349 // the libc sqrt function is called. The result is rounded and then converted
1350 // back to a uint64_t which is then used to construct the result. Finally,
1351 // the Babylonian method for computing square roots is used.
1352 APInt APInt::sqrt() const {
1354 // Determine the magnitude of the value.
1355 unsigned magnitude = getActiveBits();
1357 // Use a fast table for some small values. This also gets rid of some
1358 // rounding errors in libc sqrt for small values.
1359 if (magnitude <= 5) {
1360 static const uint8_t results[32] = {
1363 /* 3- 6 */ 2, 2, 2, 2,
1364 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1365 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1366 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1369 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1372 // If the magnitude of the value fits in less than 52 bits (the precision of
1373 // an IEEE double precision floating point value), then we can use the
1374 // libc sqrt function which will probably use a hardware sqrt computation.
1375 // This should be faster than the algorithm below.
1376 if (magnitude < 52) {
1378 // Amazingly, VC++ doesn't have round().
1379 return APInt(BitWidth,
1380 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1382 return APInt(BitWidth,
1383 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1387 // Okay, all the short cuts are exhausted. We must compute it. The following
1388 // is a classical Babylonian method for computing the square root. This code
1389 // was adapted to APINt from a wikipedia article on such computations.
1390 // See http://www.wikipedia.org/ and go to the page named
1391 // Calculate_an_integer_square_root.
1392 unsigned nbits = BitWidth, i = 4;
1393 APInt testy(BitWidth, 16);
1394 APInt x_old(BitWidth, 1);
1395 APInt x_new(BitWidth, 0);
1396 APInt two(BitWidth, 2);
1398 // Select a good starting value using binary logarithms.
1399 for (;; i += 2, testy = testy.shl(2))
1400 if (i >= nbits || this->ule(testy)) {
1401 x_old = x_old.shl(i / 2);
1405 // Use the Babylonian method to arrive at the integer square root:
1407 x_new = (this->udiv(x_old) + x_old).udiv(two);
1408 if (x_old.ule(x_new))
1413 // Make sure we return the closest approximation
1414 // NOTE: The rounding calculation below is correct. It will produce an
1415 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1416 // determined to be a rounding issue with pari/gp as it begins to use a
1417 // floating point representation after 192 bits. There are no discrepancies
1418 // between this algorithm and pari/gp for bit widths < 192 bits.
1419 APInt square(x_old * x_old);
1420 APInt nextSquare((x_old + 1) * (x_old +1));
1421 if (this->ult(square))
1423 else if (this->ule(nextSquare)) {
1424 APInt midpoint((nextSquare - square).udiv(two));
1425 APInt offset(*this - square);
1426 if (offset.ult(midpoint))
1431 llvm_unreachable("Error in APInt::sqrt computation");
1435 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1436 /// iterative extended Euclidean algorithm is used to solve for this value,
1437 /// however we simplify it to speed up calculating only the inverse, and take
1438 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1439 /// (potentially large) APInts around.
1440 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1441 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1443 // Using the properties listed at the following web page (accessed 06/21/08):
1444 // http://www.numbertheory.org/php/euclid.html
1445 // (especially the properties numbered 3, 4 and 9) it can be proved that
1446 // BitWidth bits suffice for all the computations in the algorithm implemented
1447 // below. More precisely, this number of bits suffice if the multiplicative
1448 // inverse exists, but may not suffice for the general extended Euclidean
1451 APInt r[2] = { modulo, *this };
1452 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1453 APInt q(BitWidth, 0);
1456 for (i = 0; r[i^1] != 0; i ^= 1) {
1457 // An overview of the math without the confusing bit-flipping:
1458 // q = r[i-2] / r[i-1]
1459 // r[i] = r[i-2] % r[i-1]
1460 // t[i] = t[i-2] - t[i-1] * q
1461 udivrem(r[i], r[i^1], q, r[i]);
1465 // If this APInt and the modulo are not coprime, there is no multiplicative
1466 // inverse, so return 0. We check this by looking at the next-to-last
1467 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1470 return APInt(BitWidth, 0);
1472 // The next-to-last t is the multiplicative inverse. However, we are
1473 // interested in a positive inverse. Calcuate a positive one from a negative
1474 // one if necessary. A simple addition of the modulo suffices because
1475 // abs(t[i]) is known to be less than *this/2 (see the link above).
1476 return t[i].isNegative() ? t[i] + modulo : t[i];
1479 /// Calculate the magic numbers required to implement a signed integer division
1480 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1481 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1482 /// Warren, Jr., chapter 10.
1483 APInt::ms APInt::magic() const {
1484 const APInt& d = *this;
1486 APInt ad, anc, delta, q1, r1, q2, r2, t;
1487 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1488 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1489 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1493 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1494 anc = t - 1 - t.urem(ad); // absolute value of nc
1495 p = d.getBitWidth() - 1; // initialize p
1496 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1497 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1498 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1499 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1502 q1 = q1<<1; // update q1 = 2p/abs(nc)
1503 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1504 if (r1.uge(anc)) { // must be unsigned comparison
1508 q2 = q2<<1; // update q2 = 2p/abs(d)
1509 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1510 if (r2.uge(ad)) { // must be unsigned comparison
1515 } while (q1.ule(delta) || (q1 == delta && r1 == 0));
1518 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1519 mag.s = p - d.getBitWidth(); // resulting shift
1523 /// Calculate the magic numbers required to implement an unsigned integer
1524 /// division by a constant as a sequence of multiplies, adds and shifts.
1525 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1526 /// S. Warren, Jr., chapter 10.
1527 APInt::mu APInt::magicu() const {
1528 const APInt& d = *this;
1530 APInt nc, delta, q1, r1, q2, r2;
1532 magu.a = 0; // initialize "add" indicator
1533 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1534 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1535 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1537 nc = allOnes - (-d).urem(d);
1538 p = d.getBitWidth() - 1; // initialize p
1539 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1540 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1541 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1542 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1545 if (r1.uge(nc - r1)) {
1546 q1 = q1 + q1 + 1; // update q1
1547 r1 = r1 + r1 - nc; // update r1
1550 q1 = q1+q1; // update q1
1551 r1 = r1+r1; // update r1
1553 if ((r2 + 1).uge(d - r2)) {
1554 if (q2.uge(signedMax)) magu.a = 1;
1555 q2 = q2+q2 + 1; // update q2
1556 r2 = r2+r2 + 1 - d; // update r2
1559 if (q2.uge(signedMin)) magu.a = 1;
1560 q2 = q2+q2; // update q2
1561 r2 = r2+r2 + 1; // update r2
1564 } while (p < d.getBitWidth()*2 &&
1565 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1566 magu.m = q2 + 1; // resulting magic number
1567 magu.s = p - d.getBitWidth(); // resulting shift
1571 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1572 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1573 /// variables here have the same names as in the algorithm. Comments explain
1574 /// the algorithm and any deviation from it.
1575 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1576 unsigned m, unsigned n) {
1577 assert(u && "Must provide dividend");
1578 assert(v && "Must provide divisor");
1579 assert(q && "Must provide quotient");
1580 assert(u != v && u != q && v != q && "Must us different memory");
1581 assert(n>1 && "n must be > 1");
1583 // Knuth uses the value b as the base of the number system. In our case b
1584 // is 2^31 so we just set it to -1u.
1585 uint64_t b = uint64_t(1) << 32;
1588 DEBUG(errs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1589 DEBUG(errs() << "KnuthDiv: original:");
1590 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1591 DEBUG(errs() << " by");
1592 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1593 DEBUG(errs() << '\n');
1595 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1596 // u and v by d. Note that we have taken Knuth's advice here to use a power
1597 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1598 // 2 allows us to shift instead of multiply and it is easy to determine the
1599 // shift amount from the leading zeros. We are basically normalizing the u
1600 // and v so that its high bits are shifted to the top of v's range without
1601 // overflow. Note that this can require an extra word in u so that u must
1602 // be of length m+n+1.
1603 unsigned shift = CountLeadingZeros_32(v[n-1]);
1604 unsigned v_carry = 0;
1605 unsigned u_carry = 0;
1607 for (unsigned i = 0; i < m+n; ++i) {
1608 unsigned u_tmp = u[i] >> (32 - shift);
1609 u[i] = (u[i] << shift) | u_carry;
1612 for (unsigned i = 0; i < n; ++i) {
1613 unsigned v_tmp = v[i] >> (32 - shift);
1614 v[i] = (v[i] << shift) | v_carry;
1620 DEBUG(errs() << "KnuthDiv: normal:");
1621 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1622 DEBUG(errs() << " by");
1623 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1624 DEBUG(errs() << '\n');
1627 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1630 DEBUG(errs() << "KnuthDiv: quotient digit #" << j << '\n');
1631 // D3. [Calculate q'.].
1632 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1633 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1634 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1635 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1636 // on v[n-2] determines at high speed most of the cases in which the trial
1637 // value qp is one too large, and it eliminates all cases where qp is two
1639 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1640 DEBUG(errs() << "KnuthDiv: dividend == " << dividend << '\n');
1641 uint64_t qp = dividend / v[n-1];
1642 uint64_t rp = dividend % v[n-1];
1643 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1646 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1649 DEBUG(errs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1651 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1652 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1653 // consists of a simple multiplication by a one-place number, combined with
1656 for (unsigned i = 0; i < n; ++i) {
1657 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1658 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1659 bool borrow = subtrahend > u_tmp;
1660 DEBUG(errs() << "KnuthDiv: u_tmp == " << u_tmp
1661 << ", subtrahend == " << subtrahend
1662 << ", borrow = " << borrow << '\n');
1664 uint64_t result = u_tmp - subtrahend;
1666 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1667 u[k++] = (unsigned)(result >> 32); // subtract high word
1668 while (borrow && k <= m+n) { // deal with borrow to the left
1674 DEBUG(errs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1677 DEBUG(errs() << "KnuthDiv: after subtraction:");
1678 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1679 DEBUG(errs() << '\n');
1680 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1681 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1682 // true value plus b**(n+1), namely as the b's complement of
1683 // the true value, and a "borrow" to the left should be remembered.
1686 bool carry = true; // true because b's complement is "complement + 1"
1687 for (unsigned i = 0; i <= m+n; ++i) {
1688 u[i] = ~u[i] + carry; // b's complement
1689 carry = carry && u[i] == 0;
1692 DEBUG(errs() << "KnuthDiv: after complement:");
1693 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1694 DEBUG(errs() << '\n');
1696 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1697 // negative, go to step D6; otherwise go on to step D7.
1698 q[j] = (unsigned)qp;
1700 // D6. [Add back]. The probability that this step is necessary is very
1701 // small, on the order of only 2/b. Make sure that test data accounts for
1702 // this possibility. Decrease q[j] by 1
1704 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1705 // A carry will occur to the left of u[j+n], and it should be ignored
1706 // since it cancels with the borrow that occurred in D4.
1708 for (unsigned i = 0; i < n; i++) {
1709 unsigned limit = std::min(u[j+i],v[i]);
1710 u[j+i] += v[i] + carry;
1711 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1715 DEBUG(errs() << "KnuthDiv: after correction:");
1716 DEBUG(for (int i = m+n; i >=0; i--) errs() <<" " << u[i]);
1717 DEBUG(errs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1719 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1722 DEBUG(errs() << "KnuthDiv: quotient:");
1723 DEBUG(for (int i = m; i >=0; i--) errs() <<" " << q[i]);
1724 DEBUG(errs() << '\n');
1726 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1727 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1728 // compute the remainder (urem uses this).
1730 // The value d is expressed by the "shift" value above since we avoided
1731 // multiplication by d by using a shift left. So, all we have to do is
1732 // shift right here. In order to mak
1735 DEBUG(errs() << "KnuthDiv: remainder:");
1736 for (int i = n-1; i >= 0; i--) {
1737 r[i] = (u[i] >> shift) | carry;
1738 carry = u[i] << (32 - shift);
1739 DEBUG(errs() << " " << r[i]);
1742 for (int i = n-1; i >= 0; i--) {
1744 DEBUG(errs() << " " << r[i]);
1747 DEBUG(errs() << '\n');
1750 DEBUG(errs() << '\n');
1754 void APInt::divide(const APInt LHS, unsigned lhsWords,
1755 const APInt &RHS, unsigned rhsWords,
1756 APInt *Quotient, APInt *Remainder)
1758 assert(lhsWords >= rhsWords && "Fractional result");
1760 // First, compose the values into an array of 32-bit words instead of
1761 // 64-bit words. This is a necessity of both the "short division" algorithm
1762 // and the the Knuth "classical algorithm" which requires there to be native
1763 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1764 // can't use 64-bit operands here because we don't have native results of
1765 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1766 // work on large-endian machines.
1767 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1768 unsigned n = rhsWords * 2;
1769 unsigned m = (lhsWords * 2) - n;
1771 // Allocate space for the temporary values we need either on the stack, if
1772 // it will fit, or on the heap if it won't.
1773 unsigned SPACE[128];
1778 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1781 Q = &SPACE[(m+n+1) + n];
1783 R = &SPACE[(m+n+1) + n + (m+n)];
1785 U = new unsigned[m + n + 1];
1786 V = new unsigned[n];
1787 Q = new unsigned[m+n];
1789 R = new unsigned[n];
1792 // Initialize the dividend
1793 memset(U, 0, (m+n+1)*sizeof(unsigned));
1794 for (unsigned i = 0; i < lhsWords; ++i) {
1795 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1796 U[i * 2] = (unsigned)(tmp & mask);
1797 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1799 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1801 // Initialize the divisor
1802 memset(V, 0, (n)*sizeof(unsigned));
1803 for (unsigned i = 0; i < rhsWords; ++i) {
1804 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1805 V[i * 2] = (unsigned)(tmp & mask);
1806 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1809 // initialize the quotient and remainder
1810 memset(Q, 0, (m+n) * sizeof(unsigned));
1812 memset(R, 0, n * sizeof(unsigned));
1814 // Now, adjust m and n for the Knuth division. n is the number of words in
1815 // the divisor. m is the number of words by which the dividend exceeds the
1816 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1817 // contain any zero words or the Knuth algorithm fails.
1818 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1822 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1825 // If we're left with only a single word for the divisor, Knuth doesn't work
1826 // so we implement the short division algorithm here. This is much simpler
1827 // and faster because we are certain that we can divide a 64-bit quantity
1828 // by a 32-bit quantity at hardware speed and short division is simply a
1829 // series of such operations. This is just like doing short division but we
1830 // are using base 2^32 instead of base 10.
1831 assert(n != 0 && "Divide by zero?");
1833 unsigned divisor = V[0];
1834 unsigned remainder = 0;
1835 for (int i = m+n-1; i >= 0; i--) {
1836 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1837 if (partial_dividend == 0) {
1840 } else if (partial_dividend < divisor) {
1842 remainder = (unsigned)partial_dividend;
1843 } else if (partial_dividend == divisor) {
1847 Q[i] = (unsigned)(partial_dividend / divisor);
1848 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1854 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1856 KnuthDiv(U, V, Q, R, m, n);
1859 // If the caller wants the quotient
1861 // Set up the Quotient value's memory.
1862 if (Quotient->BitWidth != LHS.BitWidth) {
1863 if (Quotient->isSingleWord())
1866 delete [] Quotient->pVal;
1867 Quotient->BitWidth = LHS.BitWidth;
1868 if (!Quotient->isSingleWord())
1869 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1873 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1875 if (lhsWords == 1) {
1877 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1878 if (Quotient->isSingleWord())
1879 Quotient->VAL = tmp;
1881 Quotient->pVal[0] = tmp;
1883 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1884 for (unsigned i = 0; i < lhsWords; ++i)
1886 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1890 // If the caller wants the remainder
1892 // Set up the Remainder value's memory.
1893 if (Remainder->BitWidth != RHS.BitWidth) {
1894 if (Remainder->isSingleWord())
1897 delete [] Remainder->pVal;
1898 Remainder->BitWidth = RHS.BitWidth;
1899 if (!Remainder->isSingleWord())
1900 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1904 // The remainder is in R. Reconstitute the remainder into Remainder's low
1906 if (rhsWords == 1) {
1908 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1909 if (Remainder->isSingleWord())
1910 Remainder->VAL = tmp;
1912 Remainder->pVal[0] = tmp;
1914 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1915 for (unsigned i = 0; i < rhsWords; ++i)
1916 Remainder->pVal[i] =
1917 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1921 // Clean up the memory we allocated.
1922 if (U != &SPACE[0]) {
1930 APInt APInt::udiv(const APInt& RHS) const {
1931 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1933 // First, deal with the easy case
1934 if (isSingleWord()) {
1935 assert(RHS.VAL != 0 && "Divide by zero?");
1936 return APInt(BitWidth, VAL / RHS.VAL);
1939 // Get some facts about the LHS and RHS number of bits and words
1940 unsigned rhsBits = RHS.getActiveBits();
1941 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1942 assert(rhsWords && "Divided by zero???");
1943 unsigned lhsBits = this->getActiveBits();
1944 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1946 // Deal with some degenerate cases
1949 return APInt(BitWidth, 0);
1950 else if (lhsWords < rhsWords || this->ult(RHS)) {
1951 // X / Y ===> 0, iff X < Y
1952 return APInt(BitWidth, 0);
1953 } else if (*this == RHS) {
1955 return APInt(BitWidth, 1);
1956 } else if (lhsWords == 1 && rhsWords == 1) {
1957 // All high words are zero, just use native divide
1958 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1961 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1962 APInt Quotient(1,0); // to hold result.
1963 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1967 APInt APInt::urem(const APInt& RHS) const {
1968 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1969 if (isSingleWord()) {
1970 assert(RHS.VAL != 0 && "Remainder by zero?");
1971 return APInt(BitWidth, VAL % RHS.VAL);
1974 // Get some facts about the LHS
1975 unsigned lhsBits = getActiveBits();
1976 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1978 // Get some facts about the RHS
1979 unsigned rhsBits = RHS.getActiveBits();
1980 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1981 assert(rhsWords && "Performing remainder operation by zero ???");
1983 // Check the degenerate cases
1984 if (lhsWords == 0) {
1986 return APInt(BitWidth, 0);
1987 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1988 // X % Y ===> X, iff X < Y
1990 } else if (*this == RHS) {
1992 return APInt(BitWidth, 0);
1993 } else if (lhsWords == 1) {
1994 // All high words are zero, just use native remainder
1995 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1998 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1999 APInt Remainder(1,0);
2000 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2004 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2005 APInt &Quotient, APInt &Remainder) {
2006 // Get some size facts about the dividend and divisor
2007 unsigned lhsBits = LHS.getActiveBits();
2008 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2009 unsigned rhsBits = RHS.getActiveBits();
2010 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2012 // Check the degenerate cases
2013 if (lhsWords == 0) {
2014 Quotient = 0; // 0 / Y ===> 0
2015 Remainder = 0; // 0 % Y ===> 0
2019 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2020 Quotient = 0; // X / Y ===> 0, iff X < Y
2021 Remainder = LHS; // X % Y ===> X, iff X < Y
2026 Quotient = 1; // X / X ===> 1
2027 Remainder = 0; // X % X ===> 0;
2031 if (lhsWords == 1 && rhsWords == 1) {
2032 // There is only one word to consider so use the native versions.
2033 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2034 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2035 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2036 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2040 // Okay, lets do it the long way
2041 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2044 void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) {
2045 // Check our assumptions here
2046 assert(!str.empty() && "Invalid string length");
2047 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2048 "Radix should be 2, 8, 10, or 16!");
2050 StringRef::iterator p = str.begin();
2051 size_t slen = str.size();
2052 bool isNeg = *p == '-';
2053 if (*p == '-' || *p == '+') {
2056 assert(slen && "String is only a sign, needs a value.");
2058 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2059 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2060 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2061 assert((((slen-1)*64)/22 <= numbits || radix != 10)
2062 && "Insufficient bit width");
2065 if (!isSingleWord())
2066 pVal = getClearedMemory(getNumWords());
2068 // Figure out if we can shift instead of multiply
2069 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2071 // Set up an APInt for the digit to add outside the loop so we don't
2072 // constantly construct/destruct it.
2073 APInt apdigit(getBitWidth(), 0);
2074 APInt apradix(getBitWidth(), radix);
2076 // Enter digit traversal loop
2077 for (StringRef::iterator e = str.end(); p != e; ++p) {
2078 unsigned digit = getDigit(*p, radix);
2080 // Shift or multiply the value by the radix
2088 // Add in the digit we just interpreted
2089 if (apdigit.isSingleWord())
2090 apdigit.VAL = digit;
2092 apdigit.pVal[0] = digit;
2095 // If its negative, put it in two's complement form
2102 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2103 bool Signed) const {
2104 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2105 "Radix should be 2, 8, 10, or 16!");
2107 // First, check for a zero value and just short circuit the logic below.
2113 static const char Digits[] = "0123456789ABCDEF";
2115 if (isSingleWord()) {
2117 char *BufPtr = Buffer+65;
2121 int64_t I = getSExtValue();
2132 *--BufPtr = Digits[N % Radix];
2135 Str.append(BufPtr, Buffer+65);
2141 if (Signed && isNegative()) {
2142 // They want to print the signed version and it is a negative value
2143 // Flip the bits and add one to turn it into the equivalent positive
2144 // value and put a '-' in the result.
2150 // We insert the digits backward, then reverse them to get the right order.
2151 unsigned StartDig = Str.size();
2153 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2154 // because the number of bits per digit (1, 3 and 4 respectively) divides
2155 // equaly. We just shift until the value is zero.
2157 // Just shift tmp right for each digit width until it becomes zero
2158 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2159 unsigned MaskAmt = Radix - 1;
2162 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2163 Str.push_back(Digits[Digit]);
2164 Tmp = Tmp.lshr(ShiftAmt);
2167 APInt divisor(4, 10);
2169 APInt APdigit(1, 0);
2170 APInt tmp2(Tmp.getBitWidth(), 0);
2171 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2173 unsigned Digit = (unsigned)APdigit.getZExtValue();
2174 assert(Digit < Radix && "divide failed");
2175 Str.push_back(Digits[Digit]);
2180 // Reverse the digits before returning.
2181 std::reverse(Str.begin()+StartDig, Str.end());
2184 /// toString - This returns the APInt as a std::string. Note that this is an
2185 /// inefficient method. It is better to pass in a SmallVector/SmallString
2186 /// to the methods above.
2187 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2189 toString(S, Radix, Signed);
2194 void APInt::dump() const {
2195 SmallString<40> S, U;
2196 this->toStringUnsigned(U);
2197 this->toStringSigned(S);
2198 errs() << "APInt(" << BitWidth << "b, "
2199 << U.str() << "u " << S.str() << "s)";
2202 void APInt::print(raw_ostream &OS, bool isSigned) const {
2204 this->toString(S, 10, isSigned);
2208 std::ostream &llvm::operator<<(std::ostream &o, const APInt &I) {
2209 raw_os_ostream OS(o);
2214 // This implements a variety of operations on a representation of
2215 // arbitrary precision, two's-complement, bignum integer values.
2217 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2218 and unrestricting assumption. */
2219 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2220 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2222 /* Some handy functions local to this file. */
2225 /* Returns the integer part with the least significant BITS set.
2226 BITS cannot be zero. */
2227 static inline integerPart
2228 lowBitMask(unsigned int bits)
2230 assert (bits != 0 && bits <= integerPartWidth);
2232 return ~(integerPart) 0 >> (integerPartWidth - bits);
2235 /* Returns the value of the lower half of PART. */
2236 static inline integerPart
2237 lowHalf(integerPart part)
2239 return part & lowBitMask(integerPartWidth / 2);
2242 /* Returns the value of the upper half of PART. */
2243 static inline integerPart
2244 highHalf(integerPart part)
2246 return part >> (integerPartWidth / 2);
2249 /* Returns the bit number of the most significant set bit of a part.
2250 If the input number has no bits set -1U is returned. */
2252 partMSB(integerPart value)
2254 unsigned int n, msb;
2259 n = integerPartWidth / 2;
2274 /* Returns the bit number of the least significant set bit of a
2275 part. If the input number has no bits set -1U is returned. */
2277 partLSB(integerPart value)
2279 unsigned int n, lsb;
2284 lsb = integerPartWidth - 1;
2285 n = integerPartWidth / 2;
2300 /* Sets the least significant part of a bignum to the input value, and
2301 zeroes out higher parts. */
2303 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2310 for(i = 1; i < parts; i++)
2314 /* Assign one bignum to another. */
2316 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2320 for(i = 0; i < parts; i++)
2324 /* Returns true if a bignum is zero, false otherwise. */
2326 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2330 for(i = 0; i < parts; i++)
2337 /* Extract the given bit of a bignum; returns 0 or 1. */
2339 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2341 return(parts[bit / integerPartWidth]
2342 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2345 /* Set the given bit of a bignum. */
2347 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2349 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2352 /* Returns the bit number of the least significant set bit of a
2353 number. If the input number has no bits set -1U is returned. */
2355 APInt::tcLSB(const integerPart *parts, unsigned int n)
2357 unsigned int i, lsb;
2359 for(i = 0; i < n; i++) {
2360 if (parts[i] != 0) {
2361 lsb = partLSB(parts[i]);
2363 return lsb + i * integerPartWidth;
2370 /* Returns the bit number of the most significant set bit of a number.
2371 If the input number has no bits set -1U is returned. */
2373 APInt::tcMSB(const integerPart *parts, unsigned int n)
2380 if (parts[n] != 0) {
2381 msb = partMSB(parts[n]);
2383 return msb + n * integerPartWidth;
2390 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2391 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2392 the least significant bit of DST. All high bits above srcBITS in
2393 DST are zero-filled. */
2395 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2396 unsigned int srcBits, unsigned int srcLSB)
2398 unsigned int firstSrcPart, dstParts, shift, n;
2400 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2401 assert (dstParts <= dstCount);
2403 firstSrcPart = srcLSB / integerPartWidth;
2404 tcAssign (dst, src + firstSrcPart, dstParts);
2406 shift = srcLSB % integerPartWidth;
2407 tcShiftRight (dst, dstParts, shift);
2409 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2410 in DST. If this is less that srcBits, append the rest, else
2411 clear the high bits. */
2412 n = dstParts * integerPartWidth - shift;
2414 integerPart mask = lowBitMask (srcBits - n);
2415 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2416 << n % integerPartWidth);
2417 } else if (n > srcBits) {
2418 if (srcBits % integerPartWidth)
2419 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2422 /* Clear high parts. */
2423 while (dstParts < dstCount)
2424 dst[dstParts++] = 0;
2427 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2429 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2430 integerPart c, unsigned int parts)
2436 for(i = 0; i < parts; i++) {
2441 dst[i] += rhs[i] + 1;
2452 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2454 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2455 integerPart c, unsigned int parts)
2461 for(i = 0; i < parts; i++) {
2466 dst[i] -= rhs[i] + 1;
2477 /* Negate a bignum in-place. */
2479 APInt::tcNegate(integerPart *dst, unsigned int parts)
2481 tcComplement(dst, parts);
2482 tcIncrement(dst, parts);
2485 /* DST += SRC * MULTIPLIER + CARRY if add is true
2486 DST = SRC * MULTIPLIER + CARRY if add is false
2488 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2489 they must start at the same point, i.e. DST == SRC.
2491 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2492 returned. Otherwise DST is filled with the least significant
2493 DSTPARTS parts of the result, and if all of the omitted higher
2494 parts were zero return zero, otherwise overflow occurred and
2497 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2498 integerPart multiplier, integerPart carry,
2499 unsigned int srcParts, unsigned int dstParts,
2504 /* Otherwise our writes of DST kill our later reads of SRC. */
2505 assert(dst <= src || dst >= src + srcParts);
2506 assert(dstParts <= srcParts + 1);
2508 /* N loops; minimum of dstParts and srcParts. */
2509 n = dstParts < srcParts ? dstParts: srcParts;
2511 for(i = 0; i < n; i++) {
2512 integerPart low, mid, high, srcPart;
2514 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2516 This cannot overflow, because
2518 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2520 which is less than n^2. */
2524 if (multiplier == 0 || srcPart == 0) {
2528 low = lowHalf(srcPart) * lowHalf(multiplier);
2529 high = highHalf(srcPart) * highHalf(multiplier);
2531 mid = lowHalf(srcPart) * highHalf(multiplier);
2532 high += highHalf(mid);
2533 mid <<= integerPartWidth / 2;
2534 if (low + mid < low)
2538 mid = highHalf(srcPart) * lowHalf(multiplier);
2539 high += highHalf(mid);
2540 mid <<= integerPartWidth / 2;
2541 if (low + mid < low)
2545 /* Now add carry. */
2546 if (low + carry < low)
2552 /* And now DST[i], and store the new low part there. */
2553 if (low + dst[i] < low)
2563 /* Full multiplication, there is no overflow. */
2564 assert(i + 1 == dstParts);
2568 /* We overflowed if there is carry. */
2572 /* We would overflow if any significant unwritten parts would be
2573 non-zero. This is true if any remaining src parts are non-zero
2574 and the multiplier is non-zero. */
2576 for(; i < srcParts; i++)
2580 /* We fitted in the narrow destination. */
2585 /* DST = LHS * RHS, where DST has the same width as the operands and
2586 is filled with the least significant parts of the result. Returns
2587 one if overflow occurred, otherwise zero. DST must be disjoint
2588 from both operands. */
2590 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2591 const integerPart *rhs, unsigned int parts)
2596 assert(dst != lhs && dst != rhs);
2599 tcSet(dst, 0, parts);
2601 for(i = 0; i < parts; i++)
2602 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2608 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2609 operands. No overflow occurs. DST must be disjoint from both
2610 operands. Returns the number of parts required to hold the
2613 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2614 const integerPart *rhs, unsigned int lhsParts,
2615 unsigned int rhsParts)
2617 /* Put the narrower number on the LHS for less loops below. */
2618 if (lhsParts > rhsParts) {
2619 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2623 assert(dst != lhs && dst != rhs);
2625 tcSet(dst, 0, rhsParts);
2627 for(n = 0; n < lhsParts; n++)
2628 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2630 n = lhsParts + rhsParts;
2632 return n - (dst[n - 1] == 0);
2636 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2637 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2638 set REMAINDER to the remainder, return zero. i.e.
2640 OLD_LHS = RHS * LHS + REMAINDER
2642 SCRATCH is a bignum of the same size as the operands and result for
2643 use by the routine; its contents need not be initialized and are
2644 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2647 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2648 integerPart *remainder, integerPart *srhs,
2651 unsigned int n, shiftCount;
2654 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2656 shiftCount = tcMSB(rhs, parts) + 1;
2657 if (shiftCount == 0)
2660 shiftCount = parts * integerPartWidth - shiftCount;
2661 n = shiftCount / integerPartWidth;
2662 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2664 tcAssign(srhs, rhs, parts);
2665 tcShiftLeft(srhs, parts, shiftCount);
2666 tcAssign(remainder, lhs, parts);
2667 tcSet(lhs, 0, parts);
2669 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2674 compare = tcCompare(remainder, srhs, parts);
2676 tcSubtract(remainder, srhs, 0, parts);
2680 if (shiftCount == 0)
2683 tcShiftRight(srhs, parts, 1);
2684 if ((mask >>= 1) == 0)
2685 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2691 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2692 There are no restrictions on COUNT. */
2694 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2697 unsigned int jump, shift;
2699 /* Jump is the inter-part jump; shift is is intra-part shift. */
2700 jump = count / integerPartWidth;
2701 shift = count % integerPartWidth;
2703 while (parts > jump) {
2708 /* dst[i] comes from the two parts src[i - jump] and, if we have
2709 an intra-part shift, src[i - jump - 1]. */
2710 part = dst[parts - jump];
2713 if (parts >= jump + 1)
2714 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2725 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2726 zero. There are no restrictions on COUNT. */
2728 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2731 unsigned int i, jump, shift;
2733 /* Jump is the inter-part jump; shift is is intra-part shift. */
2734 jump = count / integerPartWidth;
2735 shift = count % integerPartWidth;
2737 /* Perform the shift. This leaves the most significant COUNT bits
2738 of the result at zero. */
2739 for(i = 0; i < parts; i++) {
2742 if (i + jump >= parts) {
2745 part = dst[i + jump];
2748 if (i + jump + 1 < parts)
2749 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2758 /* Bitwise and of two bignums. */
2760 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2764 for(i = 0; i < parts; i++)
2768 /* Bitwise inclusive or of two bignums. */
2770 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2774 for(i = 0; i < parts; i++)
2778 /* Bitwise exclusive or of two bignums. */
2780 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2784 for(i = 0; i < parts; i++)
2788 /* Complement a bignum in-place. */
2790 APInt::tcComplement(integerPart *dst, unsigned int parts)
2794 for(i = 0; i < parts; i++)
2798 /* Comparison (unsigned) of two bignums. */
2800 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2805 if (lhs[parts] == rhs[parts])
2808 if (lhs[parts] > rhs[parts])
2817 /* Increment a bignum in-place, return the carry flag. */
2819 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2823 for(i = 0; i < parts; i++)
2830 /* Set the least significant BITS bits of a bignum, clear the
2833 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2839 while (bits > integerPartWidth) {
2840 dst[i++] = ~(integerPart) 0;
2841 bits -= integerPartWidth;
2845 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);