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 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
48 pVal = getClearedMemory(getNumWords());
50 if (isSigned && int64_t(val) < 0)
51 for (unsigned i = 1; i < getNumWords(); ++i)
55 void APInt::initSlowCase(const APInt& that) {
56 pVal = getMemory(getNumWords());
57 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
61 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
62 : BitWidth(numBits), VAL(0) {
63 assert(BitWidth && "Bitwidth too small");
64 assert(bigVal && "Null pointer detected!");
68 // Get memory, cleared to 0
69 pVal = getClearedMemory(getNumWords());
70 // Calculate the number of words to copy
71 unsigned words = std::min<unsigned>(numWords, getNumWords());
72 // Copy the words from bigVal to pVal
73 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
75 // Make sure unused high bits are cleared
79 APInt::APInt(unsigned numbits, const StringRef& Str, uint8_t radix)
80 : BitWidth(numbits), VAL(0) {
81 assert(BitWidth && "Bitwidth too small");
82 fromString(numbits, Str, radix);
85 APInt& APInt::AssignSlowCase(const APInt& RHS) {
86 // Don't do anything for X = X
90 if (BitWidth == RHS.getBitWidth()) {
91 // assume same bit-width single-word case is already handled
92 assert(!isSingleWord());
93 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
98 // assume case where both are single words is already handled
99 assert(!RHS.isSingleWord());
101 pVal = getMemory(RHS.getNumWords());
102 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
103 } else if (getNumWords() == RHS.getNumWords())
104 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
105 else if (RHS.isSingleWord()) {
110 pVal = getMemory(RHS.getNumWords());
111 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
113 BitWidth = RHS.BitWidth;
114 return clearUnusedBits();
117 APInt& APInt::operator=(uint64_t RHS) {
122 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
124 return clearUnusedBits();
127 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
128 void APInt::Profile(FoldingSetNodeID& ID) const {
129 ID.AddInteger(BitWidth);
131 if (isSingleWord()) {
136 unsigned NumWords = getNumWords();
137 for (unsigned i = 0; i < NumWords; ++i)
138 ID.AddInteger(pVal[i]);
141 /// add_1 - This function adds a single "digit" integer, y, to the multiple
142 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
143 /// 1 is returned if there is a carry out, otherwise 0 is returned.
144 /// @returns the carry of the addition.
145 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
146 for (unsigned i = 0; i < len; ++i) {
149 y = 1; // Carry one to next digit.
151 y = 0; // No need to carry so exit early
158 /// @brief Prefix increment operator. Increments the APInt by one.
159 APInt& APInt::operator++() {
163 add_1(pVal, pVal, getNumWords(), 1);
164 return clearUnusedBits();
167 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
168 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
169 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
170 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
171 /// In other words, if y > x then this function returns 1, otherwise 0.
172 /// @returns the borrow out of the subtraction
173 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
174 for (unsigned i = 0; i < len; ++i) {
178 y = 1; // We have to "borrow 1" from next "digit"
180 y = 0; // No need to borrow
181 break; // Remaining digits are unchanged so exit early
187 /// @brief Prefix decrement operator. Decrements the APInt by one.
188 APInt& APInt::operator--() {
192 sub_1(pVal, getNumWords(), 1);
193 return clearUnusedBits();
196 /// add - This function adds the integer array x to the integer array Y and
197 /// places the result in dest.
198 /// @returns the carry out from the addition
199 /// @brief General addition of 64-bit integer arrays
200 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
203 for (unsigned i = 0; i< len; ++i) {
204 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
205 dest[i] = x[i] + y[i] + carry;
206 carry = dest[i] < limit || (carry && dest[i] == limit);
211 /// Adds the RHS APint to this APInt.
212 /// @returns this, after addition of RHS.
213 /// @brief Addition assignment operator.
214 APInt& APInt::operator+=(const APInt& RHS) {
215 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
219 add(pVal, pVal, RHS.pVal, getNumWords());
221 return clearUnusedBits();
224 /// Subtracts the integer array y from the integer array x
225 /// @returns returns the borrow out.
226 /// @brief Generalized subtraction of 64-bit integer arrays.
227 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
230 for (unsigned i = 0; i < len; ++i) {
231 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
232 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
233 dest[i] = x_tmp - y[i];
238 /// Subtracts the RHS APInt from this APInt
239 /// @returns this, after subtraction
240 /// @brief Subtraction assignment operator.
241 APInt& APInt::operator-=(const APInt& RHS) {
242 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
246 sub(pVal, pVal, RHS.pVal, getNumWords());
247 return clearUnusedBits();
250 /// Multiplies an integer array, x by a a uint64_t integer and places the result
252 /// @returns the carry out of the multiplication.
253 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
254 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
255 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
256 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
259 // For each digit of x.
260 for (unsigned i = 0; i < len; ++i) {
261 // Split x into high and low words
262 uint64_t lx = x[i] & 0xffffffffULL;
263 uint64_t hx = x[i] >> 32;
264 // hasCarry - A flag to indicate if there is a carry to the next digit.
265 // hasCarry == 0, no carry
266 // hasCarry == 1, has carry
267 // hasCarry == 2, no carry and the calculation result == 0.
268 uint8_t hasCarry = 0;
269 dest[i] = carry + lx * ly;
270 // Determine if the add above introduces carry.
271 hasCarry = (dest[i] < carry) ? 1 : 0;
272 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
273 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
274 // (2^32 - 1) + 2^32 = 2^64.
275 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
277 carry += (lx * hy) & 0xffffffffULL;
278 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
279 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
280 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
285 /// Multiplies integer array x by integer array y and stores the result into
286 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
287 /// @brief Generalized multiplicate of integer arrays.
288 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
290 dest[xlen] = mul_1(dest, x, xlen, y[0]);
291 for (unsigned i = 1; i < ylen; ++i) {
292 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
293 uint64_t carry = 0, lx = 0, hx = 0;
294 for (unsigned j = 0; j < xlen; ++j) {
295 lx = x[j] & 0xffffffffULL;
297 // hasCarry - A flag to indicate if has carry.
298 // hasCarry == 0, no carry
299 // hasCarry == 1, has carry
300 // hasCarry == 2, no carry and the calculation result == 0.
301 uint8_t hasCarry = 0;
302 uint64_t resul = carry + lx * ly;
303 hasCarry = (resul < carry) ? 1 : 0;
304 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
305 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
307 carry += (lx * hy) & 0xffffffffULL;
308 resul = (carry << 32) | (resul & 0xffffffffULL);
310 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
311 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
312 ((lx * hy) >> 32) + hx * hy;
314 dest[i+xlen] = carry;
318 APInt& APInt::operator*=(const APInt& RHS) {
319 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
320 if (isSingleWord()) {
326 // Get some bit facts about LHS and check for zero
327 unsigned lhsBits = getActiveBits();
328 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
333 // Get some bit facts about RHS and check for zero
334 unsigned rhsBits = RHS.getActiveBits();
335 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
342 // Allocate space for the result
343 unsigned destWords = rhsWords + lhsWords;
344 uint64_t *dest = getMemory(destWords);
346 // Perform the long multiply
347 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
349 // Copy result back into *this
351 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
352 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
354 // delete dest array and return
359 APInt& APInt::operator&=(const APInt& RHS) {
360 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
361 if (isSingleWord()) {
365 unsigned numWords = getNumWords();
366 for (unsigned i = 0; i < numWords; ++i)
367 pVal[i] &= RHS.pVal[i];
371 APInt& APInt::operator|=(const APInt& RHS) {
372 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
373 if (isSingleWord()) {
377 unsigned numWords = getNumWords();
378 for (unsigned i = 0; i < numWords; ++i)
379 pVal[i] |= RHS.pVal[i];
383 APInt& APInt::operator^=(const APInt& RHS) {
384 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
385 if (isSingleWord()) {
387 this->clearUnusedBits();
390 unsigned numWords = getNumWords();
391 for (unsigned i = 0; i < numWords; ++i)
392 pVal[i] ^= RHS.pVal[i];
393 return clearUnusedBits();
396 APInt APInt::AndSlowCase(const APInt& RHS) const {
397 unsigned numWords = getNumWords();
398 uint64_t* val = getMemory(numWords);
399 for (unsigned i = 0; i < numWords; ++i)
400 val[i] = pVal[i] & RHS.pVal[i];
401 return APInt(val, getBitWidth());
404 APInt APInt::OrSlowCase(const APInt& RHS) const {
405 unsigned numWords = getNumWords();
406 uint64_t *val = getMemory(numWords);
407 for (unsigned i = 0; i < numWords; ++i)
408 val[i] = pVal[i] | RHS.pVal[i];
409 return APInt(val, getBitWidth());
412 APInt APInt::XorSlowCase(const APInt& RHS) const {
413 unsigned numWords = getNumWords();
414 uint64_t *val = getMemory(numWords);
415 for (unsigned i = 0; i < numWords; ++i)
416 val[i] = pVal[i] ^ RHS.pVal[i];
418 // 0^0==1 so clear the high bits in case they got set.
419 return APInt(val, getBitWidth()).clearUnusedBits();
422 bool APInt::operator !() const {
426 for (unsigned i = 0; i < getNumWords(); ++i)
432 APInt APInt::operator*(const APInt& RHS) const {
433 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
435 return APInt(BitWidth, VAL * RHS.VAL);
438 return Result.clearUnusedBits();
441 APInt APInt::operator+(const APInt& RHS) const {
442 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
444 return APInt(BitWidth, VAL + RHS.VAL);
445 APInt Result(BitWidth, 0);
446 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
447 return Result.clearUnusedBits();
450 APInt APInt::operator-(const APInt& RHS) const {
451 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
453 return APInt(BitWidth, VAL - RHS.VAL);
454 APInt Result(BitWidth, 0);
455 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
456 return Result.clearUnusedBits();
459 bool APInt::operator[](unsigned bitPosition) const {
460 return (maskBit(bitPosition) &
461 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
464 bool APInt::EqualSlowCase(const APInt& RHS) const {
465 // Get some facts about the number of bits used in the two operands.
466 unsigned n1 = getActiveBits();
467 unsigned n2 = RHS.getActiveBits();
469 // If the number of bits isn't the same, they aren't equal
473 // If the number of bits fits in a word, we only need to compare the low word.
474 if (n1 <= APINT_BITS_PER_WORD)
475 return pVal[0] == RHS.pVal[0];
477 // Otherwise, compare everything
478 for (int i = whichWord(n1 - 1); i >= 0; --i)
479 if (pVal[i] != RHS.pVal[i])
484 bool APInt::EqualSlowCase(uint64_t Val) const {
485 unsigned n = getActiveBits();
486 if (n <= APINT_BITS_PER_WORD)
487 return pVal[0] == Val;
492 bool APInt::ult(const APInt& RHS) const {
493 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
495 return VAL < RHS.VAL;
497 // Get active bit length of both operands
498 unsigned n1 = getActiveBits();
499 unsigned n2 = RHS.getActiveBits();
501 // If magnitude of LHS is less than RHS, return true.
505 // If magnitude of RHS is greather than LHS, return false.
509 // If they bot fit in a word, just compare the low order word
510 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
511 return pVal[0] < RHS.pVal[0];
513 // Otherwise, compare all words
514 unsigned topWord = whichWord(std::max(n1,n2)-1);
515 for (int i = topWord; i >= 0; --i) {
516 if (pVal[i] > RHS.pVal[i])
518 if (pVal[i] < RHS.pVal[i])
524 bool APInt::slt(const APInt& RHS) const {
525 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
526 if (isSingleWord()) {
527 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
528 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
529 return lhsSext < rhsSext;
534 bool lhsNeg = isNegative();
535 bool rhsNeg = rhs.isNegative();
537 // Sign bit is set so perform two's complement to make it positive
542 // Sign bit is set so perform two's complement to make it positive
547 // Now we have unsigned values to compare so do the comparison if necessary
548 // based on the negativeness of the values.
560 APInt& APInt::set(unsigned bitPosition) {
562 VAL |= maskBit(bitPosition);
564 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
568 /// Set the given bit to 0 whose position is given as "bitPosition".
569 /// @brief Set a given bit to 0.
570 APInt& APInt::clear(unsigned bitPosition) {
572 VAL &= ~maskBit(bitPosition);
574 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
578 /// @brief Toggle every bit to its opposite value.
580 /// Toggle a given bit to its opposite value whose position is given
581 /// as "bitPosition".
582 /// @brief Toggles a given bit to its opposite value.
583 APInt& APInt::flip(unsigned bitPosition) {
584 assert(bitPosition < BitWidth && "Out of the bit-width range!");
585 if ((*this)[bitPosition]) clear(bitPosition);
586 else set(bitPosition);
590 unsigned APInt::getBitsNeeded(const StringRef& str, uint8_t radix) {
591 assert(!str.empty() && "Invalid string length");
592 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
593 "Radix should be 2, 8, 10, or 16!");
595 size_t slen = str.size();
597 // Each computation below needs to know if its negative
598 StringRef::iterator p = str.begin();
599 unsigned isNegative = str.front() == '-';
600 if (*p == '-' || *p == '+') {
603 assert(slen && "string is only a minus!");
605 // For radixes of power-of-two values, the bits required is accurately and
608 return slen + isNegative;
610 return slen * 3 + isNegative;
612 return slen * 4 + isNegative;
614 // Otherwise it must be radix == 10, the hard case
615 assert(radix == 10 && "Invalid radix");
617 // This is grossly inefficient but accurate. We could probably do something
618 // with a computation of roughly slen*64/20 and then adjust by the value of
619 // the first few digits. But, I'm not sure how accurate that could be.
621 // Compute a sufficient number of bits that is always large enough but might
622 // be too large. This avoids the assertion in the constructor.
623 unsigned sufficient = slen*64/18;
625 // Convert to the actual binary value.
626 APInt tmp(sufficient, StringRef(p, slen), radix);
628 // Compute how many bits are required.
629 return isNegative + tmp.logBase2() + 1;
632 // From http://www.burtleburtle.net, byBob Jenkins.
633 // When targeting x86, both GCC and LLVM seem to recognize this as a
634 // rotate instruction.
635 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
637 // From http://www.burtleburtle.net, by Bob Jenkins.
640 a -= c; a ^= rot(c, 4); c += b; \
641 b -= a; b ^= rot(a, 6); a += c; \
642 c -= b; c ^= rot(b, 8); b += a; \
643 a -= c; a ^= rot(c,16); c += b; \
644 b -= a; b ^= rot(a,19); a += c; \
645 c -= b; c ^= rot(b, 4); b += a; \
648 // From http://www.burtleburtle.net, by Bob Jenkins.
649 #define final(a,b,c) \
651 c ^= b; c -= rot(b,14); \
652 a ^= c; a -= rot(c,11); \
653 b ^= a; b -= rot(a,25); \
654 c ^= b; c -= rot(b,16); \
655 a ^= c; a -= rot(c,4); \
656 b ^= a; b -= rot(a,14); \
657 c ^= b; c -= rot(b,24); \
660 // hashword() was adapted from http://www.burtleburtle.net, by Bob
661 // Jenkins. k is a pointer to an array of uint32_t values; length is
662 // the length of the key, in 32-bit chunks. This version only handles
663 // keys that are a multiple of 32 bits in size.
664 static inline uint32_t hashword(const uint64_t *k64, size_t length)
666 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
669 /* Set up the internal state */
670 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
672 /*------------------------------------------------- handle most of the key */
683 /*------------------------------------------- handle the last 3 uint32_t's */
684 switch (length) { /* all the case statements fall through */
689 case 0: /* case 0: nothing left to add */
692 /*------------------------------------------------------ report the result */
696 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
697 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
698 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
699 // function into about 35 instructions when inlined.
700 static inline uint32_t hashword8(const uint64_t k64)
703 a = b = c = 0xdeadbeef + 4;
705 a += k64 & 0xffffffff;
713 uint64_t APInt::getHashValue() const {
716 hash = hashword8(VAL);
718 hash = hashword(pVal, getNumWords()*2);
722 /// HiBits - This function returns the high "numBits" bits of this APInt.
723 APInt APInt::getHiBits(unsigned numBits) const {
724 return APIntOps::lshr(*this, BitWidth - numBits);
727 /// LoBits - This function returns the low "numBits" bits of this APInt.
728 APInt APInt::getLoBits(unsigned numBits) const {
729 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
733 bool APInt::isPowerOf2() const {
734 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
737 unsigned APInt::countLeadingZerosSlowCase() const {
739 for (unsigned i = getNumWords(); i > 0u; --i) {
741 Count += APINT_BITS_PER_WORD;
743 Count += CountLeadingZeros_64(pVal[i-1]);
747 unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
749 Count -= APINT_BITS_PER_WORD - remainder;
750 return std::min(Count, BitWidth);
753 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
757 while (V && (V & (1ULL << 63))) {
764 unsigned APInt::countLeadingOnes() const {
766 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
768 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
771 highWordBits = APINT_BITS_PER_WORD;
774 shift = APINT_BITS_PER_WORD - highWordBits;
776 int i = getNumWords() - 1;
777 unsigned Count = countLeadingOnes_64(pVal[i], shift);
778 if (Count == highWordBits) {
779 for (i--; i >= 0; --i) {
780 if (pVal[i] == -1ULL)
781 Count += APINT_BITS_PER_WORD;
783 Count += countLeadingOnes_64(pVal[i], 0);
791 unsigned APInt::countTrailingZeros() const {
793 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
796 for (; i < getNumWords() && pVal[i] == 0; ++i)
797 Count += APINT_BITS_PER_WORD;
798 if (i < getNumWords())
799 Count += CountTrailingZeros_64(pVal[i]);
800 return std::min(Count, BitWidth);
803 unsigned APInt::countTrailingOnesSlowCase() const {
806 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
807 Count += APINT_BITS_PER_WORD;
808 if (i < getNumWords())
809 Count += CountTrailingOnes_64(pVal[i]);
810 return std::min(Count, BitWidth);
813 unsigned APInt::countPopulationSlowCase() const {
815 for (unsigned i = 0; i < getNumWords(); ++i)
816 Count += CountPopulation_64(pVal[i]);
820 APInt APInt::byteSwap() const {
821 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
823 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
824 else if (BitWidth == 32)
825 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
826 else if (BitWidth == 48) {
827 unsigned Tmp1 = unsigned(VAL >> 16);
828 Tmp1 = ByteSwap_32(Tmp1);
829 uint16_t Tmp2 = uint16_t(VAL);
830 Tmp2 = ByteSwap_16(Tmp2);
831 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
832 } else if (BitWidth == 64)
833 return APInt(BitWidth, ByteSwap_64(VAL));
835 APInt Result(BitWidth, 0);
836 char *pByte = (char*)Result.pVal;
837 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
839 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
840 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
846 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
848 APInt A = API1, B = API2;
851 B = APIntOps::urem(A, B);
857 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
864 // Get the sign bit from the highest order bit
865 bool isNeg = T.I >> 63;
867 // Get the 11-bit exponent and adjust for the 1023 bit bias
868 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
870 // If the exponent is negative, the value is < 0 so just return 0.
872 return APInt(width, 0u);
874 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
875 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
877 // If the exponent doesn't shift all bits out of the mantissa
879 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
880 APInt(width, mantissa >> (52 - exp));
882 // If the client didn't provide enough bits for us to shift the mantissa into
883 // then the result is undefined, just return 0
884 if (width <= exp - 52)
885 return APInt(width, 0);
887 // Otherwise, we have to shift the mantissa bits up to the right location
888 APInt Tmp(width, mantissa);
889 Tmp = Tmp.shl((unsigned)exp - 52);
890 return isNeg ? -Tmp : Tmp;
893 /// RoundToDouble - This function converts this APInt to a double.
894 /// The layout for double is as following (IEEE Standard 754):
895 /// --------------------------------------
896 /// | Sign Exponent Fraction Bias |
897 /// |-------------------------------------- |
898 /// | 1[63] 11[62-52] 52[51-00] 1023 |
899 /// --------------------------------------
900 double APInt::roundToDouble(bool isSigned) const {
902 // Handle the simple case where the value is contained in one uint64_t.
903 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
904 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
906 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
909 return double(getWord(0));
912 // Determine if the value is negative.
913 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
915 // Construct the absolute value if we're negative.
916 APInt Tmp(isNeg ? -(*this) : (*this));
918 // Figure out how many bits we're using.
919 unsigned n = Tmp.getActiveBits();
921 // The exponent (without bias normalization) is just the number of bits
922 // we are using. Note that the sign bit is gone since we constructed the
926 // Return infinity for exponent overflow
928 if (!isSigned || !isNeg)
929 return std::numeric_limits<double>::infinity();
931 return -std::numeric_limits<double>::infinity();
933 exp += 1023; // Increment for 1023 bias
935 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
936 // extract the high 52 bits from the correct words in pVal.
938 unsigned hiWord = whichWord(n-1);
940 mantissa = Tmp.pVal[0];
942 mantissa >>= n - 52; // shift down, we want the top 52 bits.
944 assert(hiWord > 0 && "huh?");
945 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
946 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
947 mantissa = hibits | lobits;
950 // The leading bit of mantissa is implicit, so get rid of it.
951 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
956 T.I = sign | (exp << 52) | mantissa;
960 // Truncate to new width.
961 APInt &APInt::trunc(unsigned width) {
962 assert(width < BitWidth && "Invalid APInt Truncate request");
963 assert(width && "Can't truncate to 0 bits");
964 unsigned wordsBefore = getNumWords();
966 unsigned wordsAfter = getNumWords();
967 if (wordsBefore != wordsAfter) {
968 if (wordsAfter == 1) {
969 uint64_t *tmp = pVal;
973 uint64_t *newVal = getClearedMemory(wordsAfter);
974 for (unsigned i = 0; i < wordsAfter; ++i)
980 return clearUnusedBits();
983 // Sign extend to a new width.
984 APInt &APInt::sext(unsigned width) {
985 assert(width > BitWidth && "Invalid APInt SignExtend request");
986 // If the sign bit isn't set, this is the same as zext.
992 // The sign bit is set. First, get some facts
993 unsigned wordsBefore = getNumWords();
994 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
996 unsigned wordsAfter = getNumWords();
998 // Mask the high order word appropriately
999 if (wordsBefore == wordsAfter) {
1000 unsigned newWordBits = width % APINT_BITS_PER_WORD;
1001 // The extension is contained to the wordsBefore-1th word.
1002 uint64_t mask = ~0ULL;
1004 mask >>= APINT_BITS_PER_WORD - newWordBits;
1006 if (wordsBefore == 1)
1009 pVal[wordsBefore-1] |= mask;
1010 return clearUnusedBits();
1013 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1014 uint64_t *newVal = getMemory(wordsAfter);
1015 if (wordsBefore == 1)
1016 newVal[0] = VAL | mask;
1018 for (unsigned i = 0; i < wordsBefore; ++i)
1019 newVal[i] = pVal[i];
1020 newVal[wordsBefore-1] |= mask;
1022 for (unsigned i = wordsBefore; i < wordsAfter; i++)
1024 if (wordsBefore != 1)
1027 return clearUnusedBits();
1030 // Zero extend to a new width.
1031 APInt &APInt::zext(unsigned width) {
1032 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1033 unsigned wordsBefore = getNumWords();
1035 unsigned wordsAfter = getNumWords();
1036 if (wordsBefore != wordsAfter) {
1037 uint64_t *newVal = getClearedMemory(wordsAfter);
1038 if (wordsBefore == 1)
1041 for (unsigned i = 0; i < wordsBefore; ++i)
1042 newVal[i] = pVal[i];
1043 if (wordsBefore != 1)
1050 APInt &APInt::zextOrTrunc(unsigned width) {
1051 if (BitWidth < width)
1053 if (BitWidth > width)
1054 return trunc(width);
1058 APInt &APInt::sextOrTrunc(unsigned width) {
1059 if (BitWidth < width)
1061 if (BitWidth > width)
1062 return trunc(width);
1066 /// Arithmetic right-shift this APInt by shiftAmt.
1067 /// @brief Arithmetic right-shift function.
1068 APInt APInt::ashr(const APInt &shiftAmt) const {
1069 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1072 /// Arithmetic right-shift this APInt by shiftAmt.
1073 /// @brief Arithmetic right-shift function.
1074 APInt APInt::ashr(unsigned shiftAmt) const {
1075 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1076 // Handle a degenerate case
1080 // Handle single word shifts with built-in ashr
1081 if (isSingleWord()) {
1082 if (shiftAmt == BitWidth)
1083 return APInt(BitWidth, 0); // undefined
1085 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1086 return APInt(BitWidth,
1087 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1091 // If all the bits were shifted out, the result is, technically, undefined.
1092 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1093 // issues in the algorithm below.
1094 if (shiftAmt == BitWidth) {
1096 return APInt(BitWidth, -1ULL, true);
1098 return APInt(BitWidth, 0);
1101 // Create some space for the result.
1102 uint64_t * val = new uint64_t[getNumWords()];
1104 // Compute some values needed by the following shift algorithms
1105 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1106 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1107 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1108 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1109 if (bitsInWord == 0)
1110 bitsInWord = APINT_BITS_PER_WORD;
1112 // If we are shifting whole words, just move whole words
1113 if (wordShift == 0) {
1114 // Move the words containing significant bits
1115 for (unsigned i = 0; i <= breakWord; ++i)
1116 val[i] = pVal[i+offset]; // move whole word
1118 // Adjust the top significant word for sign bit fill, if negative
1120 if (bitsInWord < APINT_BITS_PER_WORD)
1121 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1123 // Shift the low order words
1124 for (unsigned i = 0; i < breakWord; ++i) {
1125 // This combines the shifted corresponding word with the low bits from
1126 // the next word (shifted into this word's high bits).
1127 val[i] = (pVal[i+offset] >> wordShift) |
1128 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1131 // Shift the break word. In this case there are no bits from the next word
1132 // to include in this word.
1133 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1135 // Deal with sign extenstion in the break word, and possibly the word before
1138 if (wordShift > bitsInWord) {
1141 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1142 val[breakWord] |= ~0ULL;
1144 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1148 // Remaining words are 0 or -1, just assign them.
1149 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1150 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1152 return APInt(val, BitWidth).clearUnusedBits();
1155 /// Logical right-shift this APInt by shiftAmt.
1156 /// @brief Logical right-shift function.
1157 APInt APInt::lshr(const APInt &shiftAmt) const {
1158 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1161 /// Logical right-shift this APInt by shiftAmt.
1162 /// @brief Logical right-shift function.
1163 APInt APInt::lshr(unsigned shiftAmt) const {
1164 if (isSingleWord()) {
1165 if (shiftAmt == BitWidth)
1166 return APInt(BitWidth, 0);
1168 return APInt(BitWidth, this->VAL >> shiftAmt);
1171 // If all the bits were shifted out, the result is 0. This avoids issues
1172 // with shifting by the size of the integer type, which produces undefined
1173 // results. We define these "undefined results" to always be 0.
1174 if (shiftAmt == BitWidth)
1175 return APInt(BitWidth, 0);
1177 // If none of the bits are shifted out, the result is *this. This avoids
1178 // issues with shifting by the size of the integer type, which produces
1179 // undefined results in the code below. This is also an optimization.
1183 // Create some space for the result.
1184 uint64_t * val = new uint64_t[getNumWords()];
1186 // If we are shifting less than a word, compute the shift with a simple carry
1187 if (shiftAmt < APINT_BITS_PER_WORD) {
1189 for (int i = getNumWords()-1; i >= 0; --i) {
1190 val[i] = (pVal[i] >> shiftAmt) | carry;
1191 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1193 return APInt(val, BitWidth).clearUnusedBits();
1196 // Compute some values needed by the remaining shift algorithms
1197 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1198 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1200 // If we are shifting whole words, just move whole words
1201 if (wordShift == 0) {
1202 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1203 val[i] = pVal[i+offset];
1204 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1206 return APInt(val,BitWidth).clearUnusedBits();
1209 // Shift the low order words
1210 unsigned breakWord = getNumWords() - offset -1;
1211 for (unsigned i = 0; i < breakWord; ++i)
1212 val[i] = (pVal[i+offset] >> wordShift) |
1213 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1214 // Shift the break word.
1215 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1217 // Remaining words are 0
1218 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1220 return APInt(val, BitWidth).clearUnusedBits();
1223 /// Left-shift this APInt by shiftAmt.
1224 /// @brief Left-shift function.
1225 APInt APInt::shl(const APInt &shiftAmt) const {
1226 // It's undefined behavior in C to shift by BitWidth or greater.
1227 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1230 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1231 // If all the bits were shifted out, the result is 0. This avoids issues
1232 // with shifting by the size of the integer type, which produces undefined
1233 // results. We define these "undefined results" to always be 0.
1234 if (shiftAmt == BitWidth)
1235 return APInt(BitWidth, 0);
1237 // If none of the bits are shifted out, the result is *this. This avoids a
1238 // lshr by the words size in the loop below which can produce incorrect
1239 // results. It also avoids the expensive computation below for a common case.
1243 // Create some space for the result.
1244 uint64_t * val = new uint64_t[getNumWords()];
1246 // If we are shifting less than a word, do it the easy way
1247 if (shiftAmt < APINT_BITS_PER_WORD) {
1249 for (unsigned i = 0; i < getNumWords(); i++) {
1250 val[i] = pVal[i] << shiftAmt | carry;
1251 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1253 return APInt(val, BitWidth).clearUnusedBits();
1256 // Compute some values needed by the remaining shift algorithms
1257 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1258 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1260 // If we are shifting whole words, just move whole words
1261 if (wordShift == 0) {
1262 for (unsigned i = 0; i < offset; i++)
1264 for (unsigned i = offset; i < getNumWords(); i++)
1265 val[i] = pVal[i-offset];
1266 return APInt(val,BitWidth).clearUnusedBits();
1269 // Copy whole words from this to Result.
1270 unsigned i = getNumWords() - 1;
1271 for (; i > offset; --i)
1272 val[i] = pVal[i-offset] << wordShift |
1273 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1274 val[offset] = pVal[0] << wordShift;
1275 for (i = 0; i < offset; ++i)
1277 return APInt(val, BitWidth).clearUnusedBits();
1280 APInt APInt::rotl(const APInt &rotateAmt) const {
1281 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1284 APInt APInt::rotl(unsigned rotateAmt) const {
1287 // Don't get too fancy, just use existing shift/or facilities
1291 lo.lshr(BitWidth - rotateAmt);
1295 APInt APInt::rotr(const APInt &rotateAmt) const {
1296 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1299 APInt APInt::rotr(unsigned rotateAmt) const {
1302 // Don't get too fancy, just use existing shift/or facilities
1306 hi.shl(BitWidth - rotateAmt);
1310 // Square Root - this method computes and returns the square root of "this".
1311 // Three mechanisms are used for computation. For small values (<= 5 bits),
1312 // a table lookup is done. This gets some performance for common cases. For
1313 // values using less than 52 bits, the value is converted to double and then
1314 // the libc sqrt function is called. The result is rounded and then converted
1315 // back to a uint64_t which is then used to construct the result. Finally,
1316 // the Babylonian method for computing square roots is used.
1317 APInt APInt::sqrt() const {
1319 // Determine the magnitude of the value.
1320 unsigned magnitude = getActiveBits();
1322 // Use a fast table for some small values. This also gets rid of some
1323 // rounding errors in libc sqrt for small values.
1324 if (magnitude <= 5) {
1325 static const uint8_t results[32] = {
1328 /* 3- 6 */ 2, 2, 2, 2,
1329 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1330 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1331 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1334 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1337 // If the magnitude of the value fits in less than 52 bits (the precision of
1338 // an IEEE double precision floating point value), then we can use the
1339 // libc sqrt function which will probably use a hardware sqrt computation.
1340 // This should be faster than the algorithm below.
1341 if (magnitude < 52) {
1343 // Amazingly, VC++ doesn't have round().
1344 return APInt(BitWidth,
1345 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1347 return APInt(BitWidth,
1348 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1352 // Okay, all the short cuts are exhausted. We must compute it. The following
1353 // is a classical Babylonian method for computing the square root. This code
1354 // was adapted to APINt from a wikipedia article on such computations.
1355 // See http://www.wikipedia.org/ and go to the page named
1356 // Calculate_an_integer_square_root.
1357 unsigned nbits = BitWidth, i = 4;
1358 APInt testy(BitWidth, 16);
1359 APInt x_old(BitWidth, 1);
1360 APInt x_new(BitWidth, 0);
1361 APInt two(BitWidth, 2);
1363 // Select a good starting value using binary logarithms.
1364 for (;; i += 2, testy = testy.shl(2))
1365 if (i >= nbits || this->ule(testy)) {
1366 x_old = x_old.shl(i / 2);
1370 // Use the Babylonian method to arrive at the integer square root:
1372 x_new = (this->udiv(x_old) + x_old).udiv(two);
1373 if (x_old.ule(x_new))
1378 // Make sure we return the closest approximation
1379 // NOTE: The rounding calculation below is correct. It will produce an
1380 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1381 // determined to be a rounding issue with pari/gp as it begins to use a
1382 // floating point representation after 192 bits. There are no discrepancies
1383 // between this algorithm and pari/gp for bit widths < 192 bits.
1384 APInt square(x_old * x_old);
1385 APInt nextSquare((x_old + 1) * (x_old +1));
1386 if (this->ult(square))
1388 else if (this->ule(nextSquare)) {
1389 APInt midpoint((nextSquare - square).udiv(two));
1390 APInt offset(*this - square);
1391 if (offset.ult(midpoint))
1396 llvm_unreachable("Error in APInt::sqrt computation");
1400 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1401 /// iterative extended Euclidean algorithm is used to solve for this value,
1402 /// however we simplify it to speed up calculating only the inverse, and take
1403 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1404 /// (potentially large) APInts around.
1405 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1406 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1408 // Using the properties listed at the following web page (accessed 06/21/08):
1409 // http://www.numbertheory.org/php/euclid.html
1410 // (especially the properties numbered 3, 4 and 9) it can be proved that
1411 // BitWidth bits suffice for all the computations in the algorithm implemented
1412 // below. More precisely, this number of bits suffice if the multiplicative
1413 // inverse exists, but may not suffice for the general extended Euclidean
1416 APInt r[2] = { modulo, *this };
1417 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1418 APInt q(BitWidth, 0);
1421 for (i = 0; r[i^1] != 0; i ^= 1) {
1422 // An overview of the math without the confusing bit-flipping:
1423 // q = r[i-2] / r[i-1]
1424 // r[i] = r[i-2] % r[i-1]
1425 // t[i] = t[i-2] - t[i-1] * q
1426 udivrem(r[i], r[i^1], q, r[i]);
1430 // If this APInt and the modulo are not coprime, there is no multiplicative
1431 // inverse, so return 0. We check this by looking at the next-to-last
1432 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1435 return APInt(BitWidth, 0);
1437 // The next-to-last t is the multiplicative inverse. However, we are
1438 // interested in a positive inverse. Calcuate a positive one from a negative
1439 // one if necessary. A simple addition of the modulo suffices because
1440 // abs(t[i]) is known to be less than *this/2 (see the link above).
1441 return t[i].isNegative() ? t[i] + modulo : t[i];
1444 /// Calculate the magic numbers required to implement a signed integer division
1445 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1446 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1447 /// Warren, Jr., chapter 10.
1448 APInt::ms APInt::magic() const {
1449 const APInt& d = *this;
1451 APInt ad, anc, delta, q1, r1, q2, r2, t;
1452 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1453 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1454 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1458 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1459 anc = t - 1 - t.urem(ad); // absolute value of nc
1460 p = d.getBitWidth() - 1; // initialize p
1461 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1462 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1463 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1464 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1467 q1 = q1<<1; // update q1 = 2p/abs(nc)
1468 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1469 if (r1.uge(anc)) { // must be unsigned comparison
1473 q2 = q2<<1; // update q2 = 2p/abs(d)
1474 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1475 if (r2.uge(ad)) { // must be unsigned comparison
1480 } while (q1.ule(delta) || (q1 == delta && r1 == 0));
1483 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1484 mag.s = p - d.getBitWidth(); // resulting shift
1488 /// Calculate the magic numbers required to implement an unsigned integer
1489 /// division by a constant as a sequence of multiplies, adds and shifts.
1490 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1491 /// S. Warren, Jr., chapter 10.
1492 APInt::mu APInt::magicu() const {
1493 const APInt& d = *this;
1495 APInt nc, delta, q1, r1, q2, r2;
1497 magu.a = 0; // initialize "add" indicator
1498 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth());
1499 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1500 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1502 nc = allOnes - (-d).urem(d);
1503 p = d.getBitWidth() - 1; // initialize p
1504 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1505 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1506 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1507 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1510 if (r1.uge(nc - r1)) {
1511 q1 = q1 + q1 + 1; // update q1
1512 r1 = r1 + r1 - nc; // update r1
1515 q1 = q1+q1; // update q1
1516 r1 = r1+r1; // update r1
1518 if ((r2 + 1).uge(d - r2)) {
1519 if (q2.uge(signedMax)) magu.a = 1;
1520 q2 = q2+q2 + 1; // update q2
1521 r2 = r2+r2 + 1 - d; // update r2
1524 if (q2.uge(signedMin)) magu.a = 1;
1525 q2 = q2+q2; // update q2
1526 r2 = r2+r2 + 1; // update r2
1529 } while (p < d.getBitWidth()*2 &&
1530 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1531 magu.m = q2 + 1; // resulting magic number
1532 magu.s = p - d.getBitWidth(); // resulting shift
1536 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1537 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1538 /// variables here have the same names as in the algorithm. Comments explain
1539 /// the algorithm and any deviation from it.
1540 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1541 unsigned m, unsigned n) {
1542 assert(u && "Must provide dividend");
1543 assert(v && "Must provide divisor");
1544 assert(q && "Must provide quotient");
1545 assert(u != v && u != q && v != q && "Must us different memory");
1546 assert(n>1 && "n must be > 1");
1548 // Knuth uses the value b as the base of the number system. In our case b
1549 // is 2^31 so we just set it to -1u.
1550 uint64_t b = uint64_t(1) << 32;
1553 DEBUG(errs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1554 DEBUG(errs() << "KnuthDiv: original:");
1555 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1556 DEBUG(errs() << " by");
1557 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1558 DEBUG(errs() << '\n');
1560 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1561 // u and v by d. Note that we have taken Knuth's advice here to use a power
1562 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1563 // 2 allows us to shift instead of multiply and it is easy to determine the
1564 // shift amount from the leading zeros. We are basically normalizing the u
1565 // and v so that its high bits are shifted to the top of v's range without
1566 // overflow. Note that this can require an extra word in u so that u must
1567 // be of length m+n+1.
1568 unsigned shift = CountLeadingZeros_32(v[n-1]);
1569 unsigned v_carry = 0;
1570 unsigned u_carry = 0;
1572 for (unsigned i = 0; i < m+n; ++i) {
1573 unsigned u_tmp = u[i] >> (32 - shift);
1574 u[i] = (u[i] << shift) | u_carry;
1577 for (unsigned i = 0; i < n; ++i) {
1578 unsigned v_tmp = v[i] >> (32 - shift);
1579 v[i] = (v[i] << shift) | v_carry;
1585 DEBUG(errs() << "KnuthDiv: normal:");
1586 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1587 DEBUG(errs() << " by");
1588 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]);
1589 DEBUG(errs() << '\n');
1592 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1595 DEBUG(errs() << "KnuthDiv: quotient digit #" << j << '\n');
1596 // D3. [Calculate q'.].
1597 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1598 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1599 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1600 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1601 // on v[n-2] determines at high speed most of the cases in which the trial
1602 // value qp is one too large, and it eliminates all cases where qp is two
1604 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1605 DEBUG(errs() << "KnuthDiv: dividend == " << dividend << '\n');
1606 uint64_t qp = dividend / v[n-1];
1607 uint64_t rp = dividend % v[n-1];
1608 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1611 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1614 DEBUG(errs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1616 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1617 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1618 // consists of a simple multiplication by a one-place number, combined with
1621 for (unsigned i = 0; i < n; ++i) {
1622 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1623 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1624 bool borrow = subtrahend > u_tmp;
1625 DEBUG(errs() << "KnuthDiv: u_tmp == " << u_tmp
1626 << ", subtrahend == " << subtrahend
1627 << ", borrow = " << borrow << '\n');
1629 uint64_t result = u_tmp - subtrahend;
1631 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1632 u[k++] = (unsigned)(result >> 32); // subtract high word
1633 while (borrow && k <= m+n) { // deal with borrow to the left
1639 DEBUG(errs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1642 DEBUG(errs() << "KnuthDiv: after subtraction:");
1643 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1644 DEBUG(errs() << '\n');
1645 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1646 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1647 // true value plus b**(n+1), namely as the b's complement of
1648 // the true value, and a "borrow" to the left should be remembered.
1651 bool carry = true; // true because b's complement is "complement + 1"
1652 for (unsigned i = 0; i <= m+n; ++i) {
1653 u[i] = ~u[i] + carry; // b's complement
1654 carry = carry && u[i] == 0;
1657 DEBUG(errs() << "KnuthDiv: after complement:");
1658 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]);
1659 DEBUG(errs() << '\n');
1661 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1662 // negative, go to step D6; otherwise go on to step D7.
1663 q[j] = (unsigned)qp;
1665 // D6. [Add back]. The probability that this step is necessary is very
1666 // small, on the order of only 2/b. Make sure that test data accounts for
1667 // this possibility. Decrease q[j] by 1
1669 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1670 // A carry will occur to the left of u[j+n], and it should be ignored
1671 // since it cancels with the borrow that occurred in D4.
1673 for (unsigned i = 0; i < n; i++) {
1674 unsigned limit = std::min(u[j+i],v[i]);
1675 u[j+i] += v[i] + carry;
1676 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1680 DEBUG(errs() << "KnuthDiv: after correction:");
1681 DEBUG(for (int i = m+n; i >=0; i--) errs() <<" " << u[i]);
1682 DEBUG(errs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1684 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1687 DEBUG(errs() << "KnuthDiv: quotient:");
1688 DEBUG(for (int i = m; i >=0; i--) errs() <<" " << q[i]);
1689 DEBUG(errs() << '\n');
1691 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1692 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1693 // compute the remainder (urem uses this).
1695 // The value d is expressed by the "shift" value above since we avoided
1696 // multiplication by d by using a shift left. So, all we have to do is
1697 // shift right here. In order to mak
1700 DEBUG(errs() << "KnuthDiv: remainder:");
1701 for (int i = n-1; i >= 0; i--) {
1702 r[i] = (u[i] >> shift) | carry;
1703 carry = u[i] << (32 - shift);
1704 DEBUG(errs() << " " << r[i]);
1707 for (int i = n-1; i >= 0; i--) {
1709 DEBUG(errs() << " " << r[i]);
1712 DEBUG(errs() << '\n');
1715 DEBUG(errs() << '\n');
1719 void APInt::divide(const APInt LHS, unsigned lhsWords,
1720 const APInt &RHS, unsigned rhsWords,
1721 APInt *Quotient, APInt *Remainder)
1723 assert(lhsWords >= rhsWords && "Fractional result");
1725 // First, compose the values into an array of 32-bit words instead of
1726 // 64-bit words. This is a necessity of both the "short division" algorithm
1727 // and the the Knuth "classical algorithm" which requires there to be native
1728 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1729 // can't use 64-bit operands here because we don't have native results of
1730 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1731 // work on large-endian machines.
1732 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1733 unsigned n = rhsWords * 2;
1734 unsigned m = (lhsWords * 2) - n;
1736 // Allocate space for the temporary values we need either on the stack, if
1737 // it will fit, or on the heap if it won't.
1738 unsigned SPACE[128];
1743 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1746 Q = &SPACE[(m+n+1) + n];
1748 R = &SPACE[(m+n+1) + n + (m+n)];
1750 U = new unsigned[m + n + 1];
1751 V = new unsigned[n];
1752 Q = new unsigned[m+n];
1754 R = new unsigned[n];
1757 // Initialize the dividend
1758 memset(U, 0, (m+n+1)*sizeof(unsigned));
1759 for (unsigned i = 0; i < lhsWords; ++i) {
1760 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1761 U[i * 2] = (unsigned)(tmp & mask);
1762 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1764 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1766 // Initialize the divisor
1767 memset(V, 0, (n)*sizeof(unsigned));
1768 for (unsigned i = 0; i < rhsWords; ++i) {
1769 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1770 V[i * 2] = (unsigned)(tmp & mask);
1771 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1774 // initialize the quotient and remainder
1775 memset(Q, 0, (m+n) * sizeof(unsigned));
1777 memset(R, 0, n * sizeof(unsigned));
1779 // Now, adjust m and n for the Knuth division. n is the number of words in
1780 // the divisor. m is the number of words by which the dividend exceeds the
1781 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1782 // contain any zero words or the Knuth algorithm fails.
1783 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1787 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1790 // If we're left with only a single word for the divisor, Knuth doesn't work
1791 // so we implement the short division algorithm here. This is much simpler
1792 // and faster because we are certain that we can divide a 64-bit quantity
1793 // by a 32-bit quantity at hardware speed and short division is simply a
1794 // series of such operations. This is just like doing short division but we
1795 // are using base 2^32 instead of base 10.
1796 assert(n != 0 && "Divide by zero?");
1798 unsigned divisor = V[0];
1799 unsigned remainder = 0;
1800 for (int i = m+n-1; i >= 0; i--) {
1801 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1802 if (partial_dividend == 0) {
1805 } else if (partial_dividend < divisor) {
1807 remainder = (unsigned)partial_dividend;
1808 } else if (partial_dividend == divisor) {
1812 Q[i] = (unsigned)(partial_dividend / divisor);
1813 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1819 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1821 KnuthDiv(U, V, Q, R, m, n);
1824 // If the caller wants the quotient
1826 // Set up the Quotient value's memory.
1827 if (Quotient->BitWidth != LHS.BitWidth) {
1828 if (Quotient->isSingleWord())
1831 delete [] Quotient->pVal;
1832 Quotient->BitWidth = LHS.BitWidth;
1833 if (!Quotient->isSingleWord())
1834 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1838 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1840 if (lhsWords == 1) {
1842 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1843 if (Quotient->isSingleWord())
1844 Quotient->VAL = tmp;
1846 Quotient->pVal[0] = tmp;
1848 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1849 for (unsigned i = 0; i < lhsWords; ++i)
1851 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1855 // If the caller wants the remainder
1857 // Set up the Remainder value's memory.
1858 if (Remainder->BitWidth != RHS.BitWidth) {
1859 if (Remainder->isSingleWord())
1862 delete [] Remainder->pVal;
1863 Remainder->BitWidth = RHS.BitWidth;
1864 if (!Remainder->isSingleWord())
1865 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1869 // The remainder is in R. Reconstitute the remainder into Remainder's low
1871 if (rhsWords == 1) {
1873 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1874 if (Remainder->isSingleWord())
1875 Remainder->VAL = tmp;
1877 Remainder->pVal[0] = tmp;
1879 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1880 for (unsigned i = 0; i < rhsWords; ++i)
1881 Remainder->pVal[i] =
1882 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1886 // Clean up the memory we allocated.
1887 if (U != &SPACE[0]) {
1895 APInt APInt::udiv(const APInt& RHS) const {
1896 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1898 // First, deal with the easy case
1899 if (isSingleWord()) {
1900 assert(RHS.VAL != 0 && "Divide by zero?");
1901 return APInt(BitWidth, VAL / RHS.VAL);
1904 // Get some facts about the LHS and RHS number of bits and words
1905 unsigned rhsBits = RHS.getActiveBits();
1906 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1907 assert(rhsWords && "Divided by zero???");
1908 unsigned lhsBits = this->getActiveBits();
1909 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1911 // Deal with some degenerate cases
1914 return APInt(BitWidth, 0);
1915 else if (lhsWords < rhsWords || this->ult(RHS)) {
1916 // X / Y ===> 0, iff X < Y
1917 return APInt(BitWidth, 0);
1918 } else if (*this == RHS) {
1920 return APInt(BitWidth, 1);
1921 } else if (lhsWords == 1 && rhsWords == 1) {
1922 // All high words are zero, just use native divide
1923 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1926 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1927 APInt Quotient(1,0); // to hold result.
1928 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1932 APInt APInt::urem(const APInt& RHS) const {
1933 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1934 if (isSingleWord()) {
1935 assert(RHS.VAL != 0 && "Remainder by zero?");
1936 return APInt(BitWidth, VAL % RHS.VAL);
1939 // Get some facts about the LHS
1940 unsigned lhsBits = getActiveBits();
1941 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1943 // Get some facts about the RHS
1944 unsigned rhsBits = RHS.getActiveBits();
1945 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1946 assert(rhsWords && "Performing remainder operation by zero ???");
1948 // Check the degenerate cases
1949 if (lhsWords == 0) {
1951 return APInt(BitWidth, 0);
1952 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1953 // X % Y ===> X, iff X < Y
1955 } else if (*this == RHS) {
1957 return APInt(BitWidth, 0);
1958 } else if (lhsWords == 1) {
1959 // All high words are zero, just use native remainder
1960 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1963 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1964 APInt Remainder(1,0);
1965 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1969 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1970 APInt &Quotient, APInt &Remainder) {
1971 // Get some size facts about the dividend and divisor
1972 unsigned lhsBits = LHS.getActiveBits();
1973 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1974 unsigned rhsBits = RHS.getActiveBits();
1975 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1977 // Check the degenerate cases
1978 if (lhsWords == 0) {
1979 Quotient = 0; // 0 / Y ===> 0
1980 Remainder = 0; // 0 % Y ===> 0
1984 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1985 Quotient = 0; // X / Y ===> 0, iff X < Y
1986 Remainder = LHS; // X % Y ===> X, iff X < Y
1991 Quotient = 1; // X / X ===> 1
1992 Remainder = 0; // X % X ===> 0;
1996 if (lhsWords == 1 && rhsWords == 1) {
1997 // There is only one word to consider so use the native versions.
1998 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1999 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2000 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2001 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2005 // Okay, lets do it the long way
2006 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2009 void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) {
2010 // Check our assumptions here
2011 assert(!str.empty() && "Invalid string length");
2012 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2013 "Radix should be 2, 8, 10, or 16!");
2015 StringRef::iterator p = str.begin();
2016 size_t slen = str.size();
2017 bool isNeg = *p == '-';
2018 if (*p == '-' || *p == '+') {
2021 assert(slen && "string is only a minus!");
2023 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2024 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2025 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2026 assert((((slen-1)*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
2029 if (!isSingleWord())
2030 pVal = getClearedMemory(getNumWords());
2032 // Figure out if we can shift instead of multiply
2033 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2035 // Set up an APInt for the digit to add outside the loop so we don't
2036 // constantly construct/destruct it.
2037 APInt apdigit(getBitWidth(), 0);
2038 APInt apradix(getBitWidth(), radix);
2040 // Enter digit traversal loop
2041 for (StringRef::iterator e = str.end(); p != e; ++p) {
2046 if (!isxdigit(cdigit))
2047 llvm_unreachable("Invalid hex digit in string");
2048 if (isdigit(cdigit))
2049 digit = cdigit - '0';
2050 else if (cdigit >= 'a')
2051 digit = cdigit - 'a' + 10;
2052 else if (cdigit >= 'A')
2053 digit = cdigit - 'A' + 10;
2055 llvm_unreachable("huh? we shouldn't get here");
2056 } else if (isdigit(cdigit)) {
2057 digit = cdigit - '0';
2058 assert((radix == 10 ||
2059 (radix == 8 && digit != 8 && digit != 9) ||
2060 (radix == 2 && (digit == 0 || digit == 1))) &&
2061 "Invalid digit in string for given radix");
2063 llvm_unreachable("Invalid character in digit string");
2066 // Shift or multiply the value by the radix
2074 // Add in the digit we just interpreted
2075 if (apdigit.isSingleWord())
2076 apdigit.VAL = digit;
2078 apdigit.pVal[0] = digit;
2081 // If its negative, put it in two's complement form
2088 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2089 bool Signed) const {
2090 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2091 "Radix should be 2, 8, 10, or 16!");
2093 // First, check for a zero value and just short circuit the logic below.
2099 static const char Digits[] = "0123456789ABCDEF";
2101 if (isSingleWord()) {
2103 char *BufPtr = Buffer+65;
2107 int64_t I = getSExtValue();
2118 *--BufPtr = Digits[N % Radix];
2121 Str.append(BufPtr, Buffer+65);
2127 if (Signed && isNegative()) {
2128 // They want to print the signed version and it is a negative value
2129 // Flip the bits and add one to turn it into the equivalent positive
2130 // value and put a '-' in the result.
2136 // We insert the digits backward, then reverse them to get the right order.
2137 unsigned StartDig = Str.size();
2139 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2140 // because the number of bits per digit (1, 3 and 4 respectively) divides
2141 // equaly. We just shift until the value is zero.
2143 // Just shift tmp right for each digit width until it becomes zero
2144 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2145 unsigned MaskAmt = Radix - 1;
2148 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2149 Str.push_back(Digits[Digit]);
2150 Tmp = Tmp.lshr(ShiftAmt);
2153 APInt divisor(4, 10);
2155 APInt APdigit(1, 0);
2156 APInt tmp2(Tmp.getBitWidth(), 0);
2157 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2159 unsigned Digit = (unsigned)APdigit.getZExtValue();
2160 assert(Digit < Radix && "divide failed");
2161 Str.push_back(Digits[Digit]);
2166 // Reverse the digits before returning.
2167 std::reverse(Str.begin()+StartDig, Str.end());
2170 /// toString - This returns the APInt as a std::string. Note that this is an
2171 /// inefficient method. It is better to pass in a SmallVector/SmallString
2172 /// to the methods above.
2173 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2175 toString(S, Radix, Signed);
2180 void APInt::dump() const {
2181 SmallString<40> S, U;
2182 this->toStringUnsigned(U);
2183 this->toStringSigned(S);
2184 errs() << "APInt(" << BitWidth << "b, "
2185 << U.str() << "u " << S.str() << "s)";
2188 void APInt::print(raw_ostream &OS, bool isSigned) const {
2190 this->toString(S, 10, isSigned);
2194 std::ostream &llvm::operator<<(std::ostream &o, const APInt &I) {
2195 raw_os_ostream OS(o);
2200 // This implements a variety of operations on a representation of
2201 // arbitrary precision, two's-complement, bignum integer values.
2203 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2204 and unrestricting assumption. */
2205 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2206 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2208 /* Some handy functions local to this file. */
2211 /* Returns the integer part with the least significant BITS set.
2212 BITS cannot be zero. */
2213 static inline integerPart
2214 lowBitMask(unsigned int bits)
2216 assert (bits != 0 && bits <= integerPartWidth);
2218 return ~(integerPart) 0 >> (integerPartWidth - bits);
2221 /* Returns the value of the lower half of PART. */
2222 static inline integerPart
2223 lowHalf(integerPart part)
2225 return part & lowBitMask(integerPartWidth / 2);
2228 /* Returns the value of the upper half of PART. */
2229 static inline integerPart
2230 highHalf(integerPart part)
2232 return part >> (integerPartWidth / 2);
2235 /* Returns the bit number of the most significant set bit of a part.
2236 If the input number has no bits set -1U is returned. */
2238 partMSB(integerPart value)
2240 unsigned int n, msb;
2245 n = integerPartWidth / 2;
2260 /* Returns the bit number of the least significant set bit of a
2261 part. If the input number has no bits set -1U is returned. */
2263 partLSB(integerPart value)
2265 unsigned int n, lsb;
2270 lsb = integerPartWidth - 1;
2271 n = integerPartWidth / 2;
2286 /* Sets the least significant part of a bignum to the input value, and
2287 zeroes out higher parts. */
2289 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2296 for(i = 1; i < parts; i++)
2300 /* Assign one bignum to another. */
2302 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2306 for(i = 0; i < parts; i++)
2310 /* Returns true if a bignum is zero, false otherwise. */
2312 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2316 for(i = 0; i < parts; i++)
2323 /* Extract the given bit of a bignum; returns 0 or 1. */
2325 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2327 return(parts[bit / integerPartWidth]
2328 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2331 /* Set the given bit of a bignum. */
2333 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2335 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2338 /* Returns the bit number of the least significant set bit of a
2339 number. If the input number has no bits set -1U is returned. */
2341 APInt::tcLSB(const integerPart *parts, unsigned int n)
2343 unsigned int i, lsb;
2345 for(i = 0; i < n; i++) {
2346 if (parts[i] != 0) {
2347 lsb = partLSB(parts[i]);
2349 return lsb + i * integerPartWidth;
2356 /* Returns the bit number of the most significant set bit of a number.
2357 If the input number has no bits set -1U is returned. */
2359 APInt::tcMSB(const integerPart *parts, unsigned int n)
2366 if (parts[n] != 0) {
2367 msb = partMSB(parts[n]);
2369 return msb + n * integerPartWidth;
2376 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2377 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2378 the least significant bit of DST. All high bits above srcBITS in
2379 DST are zero-filled. */
2381 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2382 unsigned int srcBits, unsigned int srcLSB)
2384 unsigned int firstSrcPart, dstParts, shift, n;
2386 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2387 assert (dstParts <= dstCount);
2389 firstSrcPart = srcLSB / integerPartWidth;
2390 tcAssign (dst, src + firstSrcPart, dstParts);
2392 shift = srcLSB % integerPartWidth;
2393 tcShiftRight (dst, dstParts, shift);
2395 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2396 in DST. If this is less that srcBits, append the rest, else
2397 clear the high bits. */
2398 n = dstParts * integerPartWidth - shift;
2400 integerPart mask = lowBitMask (srcBits - n);
2401 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2402 << n % integerPartWidth);
2403 } else if (n > srcBits) {
2404 if (srcBits % integerPartWidth)
2405 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2408 /* Clear high parts. */
2409 while (dstParts < dstCount)
2410 dst[dstParts++] = 0;
2413 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2415 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2416 integerPart c, unsigned int parts)
2422 for(i = 0; i < parts; i++) {
2427 dst[i] += rhs[i] + 1;
2438 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2440 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2441 integerPart c, unsigned int parts)
2447 for(i = 0; i < parts; i++) {
2452 dst[i] -= rhs[i] + 1;
2463 /* Negate a bignum in-place. */
2465 APInt::tcNegate(integerPart *dst, unsigned int parts)
2467 tcComplement(dst, parts);
2468 tcIncrement(dst, parts);
2471 /* DST += SRC * MULTIPLIER + CARRY if add is true
2472 DST = SRC * MULTIPLIER + CARRY if add is false
2474 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2475 they must start at the same point, i.e. DST == SRC.
2477 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2478 returned. Otherwise DST is filled with the least significant
2479 DSTPARTS parts of the result, and if all of the omitted higher
2480 parts were zero return zero, otherwise overflow occurred and
2483 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2484 integerPart multiplier, integerPart carry,
2485 unsigned int srcParts, unsigned int dstParts,
2490 /* Otherwise our writes of DST kill our later reads of SRC. */
2491 assert(dst <= src || dst >= src + srcParts);
2492 assert(dstParts <= srcParts + 1);
2494 /* N loops; minimum of dstParts and srcParts. */
2495 n = dstParts < srcParts ? dstParts: srcParts;
2497 for(i = 0; i < n; i++) {
2498 integerPart low, mid, high, srcPart;
2500 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2502 This cannot overflow, because
2504 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2506 which is less than n^2. */
2510 if (multiplier == 0 || srcPart == 0) {
2514 low = lowHalf(srcPart) * lowHalf(multiplier);
2515 high = highHalf(srcPart) * highHalf(multiplier);
2517 mid = lowHalf(srcPart) * highHalf(multiplier);
2518 high += highHalf(mid);
2519 mid <<= integerPartWidth / 2;
2520 if (low + mid < low)
2524 mid = highHalf(srcPart) * lowHalf(multiplier);
2525 high += highHalf(mid);
2526 mid <<= integerPartWidth / 2;
2527 if (low + mid < low)
2531 /* Now add carry. */
2532 if (low + carry < low)
2538 /* And now DST[i], and store the new low part there. */
2539 if (low + dst[i] < low)
2549 /* Full multiplication, there is no overflow. */
2550 assert(i + 1 == dstParts);
2554 /* We overflowed if there is carry. */
2558 /* We would overflow if any significant unwritten parts would be
2559 non-zero. This is true if any remaining src parts are non-zero
2560 and the multiplier is non-zero. */
2562 for(; i < srcParts; i++)
2566 /* We fitted in the narrow destination. */
2571 /* DST = LHS * RHS, where DST has the same width as the operands and
2572 is filled with the least significant parts of the result. Returns
2573 one if overflow occurred, otherwise zero. DST must be disjoint
2574 from both operands. */
2576 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2577 const integerPart *rhs, unsigned int parts)
2582 assert(dst != lhs && dst != rhs);
2585 tcSet(dst, 0, parts);
2587 for(i = 0; i < parts; i++)
2588 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2594 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2595 operands. No overflow occurs. DST must be disjoint from both
2596 operands. Returns the number of parts required to hold the
2599 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2600 const integerPart *rhs, unsigned int lhsParts,
2601 unsigned int rhsParts)
2603 /* Put the narrower number on the LHS for less loops below. */
2604 if (lhsParts > rhsParts) {
2605 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2609 assert(dst != lhs && dst != rhs);
2611 tcSet(dst, 0, rhsParts);
2613 for(n = 0; n < lhsParts; n++)
2614 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2616 n = lhsParts + rhsParts;
2618 return n - (dst[n - 1] == 0);
2622 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2623 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2624 set REMAINDER to the remainder, return zero. i.e.
2626 OLD_LHS = RHS * LHS + REMAINDER
2628 SCRATCH is a bignum of the same size as the operands and result for
2629 use by the routine; its contents need not be initialized and are
2630 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2633 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2634 integerPart *remainder, integerPart *srhs,
2637 unsigned int n, shiftCount;
2640 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2642 shiftCount = tcMSB(rhs, parts) + 1;
2643 if (shiftCount == 0)
2646 shiftCount = parts * integerPartWidth - shiftCount;
2647 n = shiftCount / integerPartWidth;
2648 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2650 tcAssign(srhs, rhs, parts);
2651 tcShiftLeft(srhs, parts, shiftCount);
2652 tcAssign(remainder, lhs, parts);
2653 tcSet(lhs, 0, parts);
2655 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2660 compare = tcCompare(remainder, srhs, parts);
2662 tcSubtract(remainder, srhs, 0, parts);
2666 if (shiftCount == 0)
2669 tcShiftRight(srhs, parts, 1);
2670 if ((mask >>= 1) == 0)
2671 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2677 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2678 There are no restrictions on COUNT. */
2680 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2683 unsigned int jump, shift;
2685 /* Jump is the inter-part jump; shift is is intra-part shift. */
2686 jump = count / integerPartWidth;
2687 shift = count % integerPartWidth;
2689 while (parts > jump) {
2694 /* dst[i] comes from the two parts src[i - jump] and, if we have
2695 an intra-part shift, src[i - jump - 1]. */
2696 part = dst[parts - jump];
2699 if (parts >= jump + 1)
2700 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2711 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2712 zero. There are no restrictions on COUNT. */
2714 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2717 unsigned int i, jump, shift;
2719 /* Jump is the inter-part jump; shift is is intra-part shift. */
2720 jump = count / integerPartWidth;
2721 shift = count % integerPartWidth;
2723 /* Perform the shift. This leaves the most significant COUNT bits
2724 of the result at zero. */
2725 for(i = 0; i < parts; i++) {
2728 if (i + jump >= parts) {
2731 part = dst[i + jump];
2734 if (i + jump + 1 < parts)
2735 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2744 /* Bitwise and of two bignums. */
2746 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2750 for(i = 0; i < parts; i++)
2754 /* Bitwise inclusive or of two bignums. */
2756 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2760 for(i = 0; i < parts; i++)
2764 /* Bitwise exclusive or of two bignums. */
2766 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2770 for(i = 0; i < parts; i++)
2774 /* Complement a bignum in-place. */
2776 APInt::tcComplement(integerPart *dst, unsigned int parts)
2780 for(i = 0; i < parts; i++)
2784 /* Comparison (unsigned) of two bignums. */
2786 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2791 if (lhs[parts] == rhs[parts])
2794 if (lhs[parts] > rhs[parts])
2803 /* Increment a bignum in-place, return the carry flag. */
2805 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2809 for(i = 0; i < parts; i++)
2816 /* Set the least significant BITS bits of a bignum, clear the
2819 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2825 while (bits > integerPartWidth) {
2826 dst[i++] = ~(integerPart) 0;
2827 bits -= integerPartWidth;
2831 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);