1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Sheng Zhou and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integral
13 //===----------------------------------------------------------------------===//
15 #include "llvm/ADT/APInt.h"
18 #include "llvm/DerivedTypes.h"
19 #include "llvm/Support/MathExtras.h"
24 /// mul_1 - This function performs the multiplication operation on a
25 /// large integer (represented as an integer array) and a uint64_t integer.
26 /// @returns the carry of the multiplication.
27 static uint64_t mul_1(uint64_t dest[], uint64_t x[],
28 unsigned len, uint64_t y) {
29 // Split y into high 32-bit part and low 32-bit part.
30 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
31 uint64_t carry = 0, lx, hx;
32 for (unsigned i = 0; i < len; ++i) {
33 lx = x[i] & 0xffffffffULL;
35 // hasCarry - A flag to indicate if has carry.
36 // hasCarry == 0, no carry
37 // hasCarry == 1, has carry
38 // hasCarry == 2, no carry and the calculation result == 0.
40 dest[i] = carry + lx * ly;
41 // Determine if the add above introduces carry.
42 hasCarry = (dest[i] < carry) ? 1 : 0;
43 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
44 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
45 // (2^32 - 1) + 2^32 = 2^64.
46 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
48 carry += (lx * hy) & 0xffffffffULL;
49 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
50 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
51 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
57 /// mul - This function multiplies integer array x[] by integer array y[] and
58 /// stores the result into integer array dest[].
59 /// Note the array dest[]'s size should no less than xlen + ylen.
60 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen,
61 uint64_t y[], unsigned ylen) {
62 dest[xlen] = mul_1(dest, x, xlen, y[0]);
64 for (unsigned i = 1; i < ylen; ++i) {
65 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
66 uint64_t carry = 0, lx, hx;
67 for (unsigned j = 0; j < xlen; ++j) {
68 lx = x[j] & 0xffffffffULL;
70 // hasCarry - A flag to indicate if has carry.
71 // hasCarry == 0, no carry
72 // hasCarry == 1, has carry
73 // hasCarry == 2, no carry and the calculation result == 0.
75 uint64_t resul = carry + lx * ly;
76 hasCarry = (resul < carry) ? 1 : 0;
77 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
78 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
80 carry += (lx * hy) & 0xffffffffULL;
81 resul = (carry << 32) | (resul & 0xffffffffULL);
83 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
84 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
85 ((lx * hy) >> 32) + hx * hy;
91 /// add_1 - This function adds the integer array x[] by integer y and
92 /// returns the carry.
93 /// @returns the carry of the addition.
94 static uint64_t add_1(uint64_t dest[], uint64_t x[],
95 unsigned len, uint64_t y) {
98 for (unsigned i = 0; i < len; ++i) {
99 dest[i] = carry + x[i];
100 carry = (dest[i] < carry) ? 1 : 0;
105 /// add - This function adds the integer array x[] by integer array
106 /// y[] and returns the carry.
107 static uint64_t add(uint64_t dest[], uint64_t x[],
108 uint64_t y[], unsigned len) {
111 for (unsigned i = 0; i< len; ++i) {
113 dest[i] = carry + y[i];
114 carry = carry < x[i] ? 1 : (dest[i] < carry ? 1 : 0);
119 /// sub_1 - This function subtracts the integer array x[] by
120 /// integer y and returns the borrow-out carry.
121 static uint64_t sub_1(uint64_t x[], unsigned len, uint64_t y) {
124 for (unsigned i = 0; i < len; ++i) {
138 /// sub - This function subtracts the integer array x[] by
139 /// integer array y[], and returns the borrow-out carry.
140 static uint64_t sub(uint64_t dest[], uint64_t x[],
141 uint64_t y[], unsigned len) {
145 for (unsigned i = 0; i < len; ++i) {
146 uint64_t Y = y[i], X = x[i];
157 /// UnitDiv - This function divides N by D,
158 /// and returns (remainder << 32) | quotient.
159 /// Assumes (N >> 32) < D.
160 static uint64_t unitDiv(uint64_t N, unsigned D) {
161 uint64_t q, r; // q: quotient, r: remainder.
162 uint64_t a1 = N >> 32; // a1: high 32-bit part of N.
163 uint64_t a0 = N & 0xffffffffL; // a0: low 32-bit part of N
164 if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL)) {
169 // Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d
170 uint64_t c = N - ((uint64_t) D << 31);
171 // Divide (c1*2^32 + c0) by d
174 // Add 2^31 to quotient
178 return (r << 32) | (q & 0xFFFFFFFFl);
181 /// subMul - This function substracts x[len-1:0] * y from
182 /// dest[offset+len-1:offset], and returns the most significant
183 /// word of the product, minus the borrow-out from the subtraction.
184 static unsigned subMul(unsigned dest[], unsigned offset,
185 unsigned x[], unsigned len, unsigned y) {
186 uint64_t yl = (uint64_t) y & 0xffffffffL;
190 uint64_t prod = ((uint64_t) x[j] & 0xffffffffL) * yl;
191 unsigned prod_low = (unsigned) prod;
192 unsigned prod_high = (unsigned) (prod >> 32);
194 carry = (prod_low < carry ? 1 : 0) + prod_high;
195 unsigned x_j = dest[offset+j];
196 prod_low = x_j - prod_low;
197 if (prod_low > x_j) ++carry;
198 dest[offset+j] = prod_low;
203 /// div - This is basically Knuth's formulation of the classical algorithm.
204 /// Correspondance with Knuth's notation:
205 /// Knuth's u[0:m+n] == zds[nx:0].
206 /// Knuth's v[1:n] == y[ny-1:0]
208 /// Knuth's m == nx-ny.
209 /// Our nx == Knuth's m+n.
210 /// Could be re-implemented using gmp's mpn_divrem:
211 /// zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny).
212 static void div(unsigned zds[], unsigned nx, unsigned y[], unsigned ny) {
214 do { // loop over digits of quotient
215 // Knuth's j == our nx-j.
216 // Knuth's u[j:j+n] == our zds[j:j-ny].
217 unsigned qhat; // treated as unsigned
218 if (zds[j] == y[ny-1]) qhat = -1U; // 0xffffffff
220 uint64_t w = (((uint64_t)(zds[j])) << 32) +
221 ((uint64_t)zds[j-1] & 0xffffffffL);
222 qhat = (unsigned) unitDiv(w, y[ny-1]);
225 unsigned borrow = subMul(zds, j - ny, y, ny, qhat);
226 unsigned save = zds[j];
227 uint64_t num = ((uint64_t)save&0xffffffffL) -
228 ((uint64_t)borrow&0xffffffffL);
232 for (unsigned i = 0; i < ny; i++) {
233 carry += ((uint64_t) zds[j-ny+i] & 0xffffffffL)
234 + ((uint64_t) y[i] & 0xffffffffL);
235 zds[j-ny+i] = (unsigned) carry;
246 /// lshift - This function shift x[0:len-1] left by shiftAmt bits, and
247 /// store the len least significant words of the result in
248 /// dest[d_offset:d_offset+len-1]. It returns the bits shifted out from
249 /// the most significant digit.
250 static uint64_t lshift(uint64_t dest[], unsigned d_offset,
251 uint64_t x[], unsigned len, unsigned shiftAmt) {
252 unsigned count = 64 - shiftAmt;
254 uint64_t high_word = x[i], retVal = high_word >> count;
257 uint64_t low_word = x[i];
258 dest[d_offset+i] = (high_word << shiftAmt) | (low_word >> count);
259 high_word = low_word;
261 dest[d_offset+i] = high_word << shiftAmt;
265 APInt::APInt(uint64_t val, unsigned numBits)
267 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small");
268 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large");
270 VAL = val & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum));
272 // Memory allocation and check if successful.
273 assert((pVal = new uint64_t[getNumWords()]) &&
274 "APInt memory allocation fails!");
275 memset(pVal, 0, getNumWords() * 8);
280 APInt::APInt(unsigned numBits, uint64_t bigVal[])
282 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small");
283 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large");
284 assert(bigVal && "Null pointer detected!");
286 VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum));
288 // Memory allocation and check if successful.
289 assert((pVal = new uint64_t[getNumWords()]) &&
290 "APInt memory allocation fails!");
291 // Calculate the actual length of bigVal[].
292 unsigned n = sizeof(*bigVal) / sizeof(bigVal[0]);
293 unsigned maxN = std::max<unsigned>(n, getNumWords());
294 unsigned minN = std::min<unsigned>(n, getNumWords());
295 memcpy(pVal, bigVal, (minN - 1) * 8);
296 pVal[minN-1] = bigVal[minN-1] & (~uint64_t(0ULL) >> (64 - BitsNum % 64));
297 if (maxN == getNumWords())
298 memset(pVal+n, 0, (getNumWords() - n) * 8);
302 /// @brief Create a new APInt by translating the char array represented
304 APInt::APInt(const char StrStart[], unsigned slen, uint8_t radix) {
305 StrToAPInt(StrStart, slen, radix);
308 /// @brief Create a new APInt by translating the string represented
310 APInt::APInt(const std::string& Val, uint8_t radix) {
311 assert(!Val.empty() && "String empty?");
312 StrToAPInt(Val.c_str(), Val.size(), radix);
315 /// @brief Converts a char array into an integer.
316 void APInt::StrToAPInt(const char *StrStart, unsigned slen, uint8_t radix) {
317 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
318 "Radix should be 2, 8, 10, or 16!");
319 assert(StrStart && "String empty?");
321 // If the radix is a power of 2, read the input
322 // from most significant to least significant.
323 if ((radix & (radix - 1)) == 0) {
324 unsigned nextBitPos = 0, bits_per_digit = radix / 8 + 2;
325 uint64_t resDigit = 0;
326 BitsNum = slen * bits_per_digit;
327 if (getNumWords() > 1)
328 assert((pVal = new uint64_t[getNumWords()]) &&
329 "APInt memory allocation fails!");
330 for (int i = slen - 1; i >= 0; --i) {
331 uint64_t digit = StrStart[i] - 48; // '0' == 48.
332 resDigit |= digit << nextBitPos;
333 nextBitPos += bits_per_digit;
334 if (nextBitPos >= 64) {
335 if (isSingleWord()) {
339 pVal[size++] = resDigit;
341 resDigit = digit >> (bits_per_digit - nextBitPos);
344 if (!isSingleWord() && size <= getNumWords())
345 pVal[size] = resDigit;
346 } else { // General case. The radix is not a power of 2.
347 // For 10-radix, the max value of 64-bit integer is 18446744073709551615,
348 // and its digits number is 14.
349 const unsigned chars_per_word = 20;
350 if (slen < chars_per_word ||
351 (slen == chars_per_word && // In case the value <= 2^64 - 1
352 strcmp(StrStart, "18446744073709551615") <= 0)) {
354 VAL = strtoull(StrStart, 0, 10);
355 } else { // In case the value > 2^64 - 1
356 BitsNum = (slen / chars_per_word + 1) * 64;
357 assert((pVal = new uint64_t[getNumWords()]) &&
358 "APInt memory allocation fails!");
359 memset(pVal, 0, getNumWords() * 8);
360 unsigned str_pos = 0;
361 while (str_pos < slen) {
362 unsigned chunk = slen - str_pos;
363 if (chunk > chars_per_word - 1)
364 chunk = chars_per_word - 1;
365 uint64_t resDigit = StrStart[str_pos++] - 48; // 48 == '0'.
366 uint64_t big_base = radix;
367 while (--chunk > 0) {
368 resDigit = resDigit * radix + StrStart[str_pos++] - 48;
376 carry = mul_1(pVal, pVal, size, big_base);
377 carry += add_1(pVal, pVal, size, resDigit);
380 if (carry) pVal[size++] = carry;
386 APInt::APInt(const APInt& APIVal)
387 : BitsNum(APIVal.BitsNum) {
388 if (isSingleWord()) VAL = APIVal.VAL;
390 // Memory allocation and check if successful.
391 assert((pVal = new uint64_t[getNumWords()]) &&
392 "APInt memory allocation fails!");
393 memcpy(pVal, APIVal.pVal, getNumWords() * 8);
398 if (!isSingleWord() && pVal) delete[] pVal;
401 /// @brief Copy assignment operator. Create a new object from the given
402 /// APInt one by initialization.
403 APInt& APInt::operator=(const APInt& RHS) {
404 if (isSingleWord()) VAL = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
406 unsigned minN = std::min(getNumWords(), RHS.getNumWords());
407 memcpy(pVal, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, minN * 8);
408 if (getNumWords() != minN)
409 memset(pVal + minN, 0, (getNumWords() - minN) * 8);
414 /// @brief Assignment operator. Assigns a common case integer value to
416 APInt& APInt::operator=(uint64_t RHS) {
417 if (isSingleWord()) VAL = RHS;
420 memset(pVal, 0, (getNumWords() - 1) * 8);
426 /// @brief Prefix increment operator. Increments the APInt by one.
427 APInt& APInt::operator++() {
428 if (isSingleWord()) ++VAL;
430 add_1(pVal, pVal, getNumWords(), 1);
435 /// @brief Prefix decrement operator. Decrements the APInt by one.
436 APInt& APInt::operator--() {
437 if (isSingleWord()) --VAL;
439 sub_1(pVal, getNumWords(), 1);
444 /// @brief Addition assignment operator. Adds this APInt by the given APInt&
445 /// RHS and assigns the result to this APInt.
446 APInt& APInt::operator+=(const APInt& RHS) {
447 if (isSingleWord()) VAL += RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
449 if (RHS.isSingleWord()) add_1(pVal, pVal, getNumWords(), RHS.VAL);
451 if (getNumWords() <= RHS.getNumWords())
452 add(pVal, pVal, RHS.pVal, getNumWords());
454 uint64_t carry = add(pVal, pVal, RHS.pVal, RHS.getNumWords());
455 add_1(pVal + RHS.getNumWords(), pVal + RHS.getNumWords(),
456 getNumWords() - RHS.getNumWords(), carry);
464 /// @brief Subtraction assignment operator. Subtracts this APInt by the given
465 /// APInt &RHS and assigns the result to this APInt.
466 APInt& APInt::operator-=(const APInt& RHS) {
468 VAL -= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
470 if (RHS.isSingleWord())
471 sub_1(pVal, getNumWords(), RHS.VAL);
473 if (RHS.getNumWords() < getNumWords()) {
474 uint64_t carry = sub(pVal, pVal, RHS.pVal, RHS.getNumWords());
475 sub_1(pVal + RHS.getNumWords(), getNumWords() - RHS.getNumWords(), carry);
478 sub(pVal, pVal, RHS.pVal, getNumWords());
485 /// @brief Multiplication assignment operator. Multiplies this APInt by the
486 /// given APInt& RHS and assigns the result to this APInt.
487 APInt& APInt::operator*=(const APInt& RHS) {
488 if (isSingleWord()) VAL *= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
490 // one-based first non-zero bit position.
491 unsigned first = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros();
492 unsigned xlen = !first ? 0 : whichWord(first - 1) + 1;
495 else if (RHS.isSingleWord())
496 mul_1(pVal, pVal, xlen, RHS.VAL);
498 first = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros();
499 unsigned ylen = !first ? 0 : whichWord(first - 1) + 1;
501 memset(pVal, 0, getNumWords() * 8);
504 uint64_t *dest = new uint64_t[xlen+ylen];
505 assert(dest && "Memory Allocation Failed!");
506 mul(dest, pVal, xlen, RHS.pVal, ylen);
507 memcpy(pVal, dest, ((xlen + ylen >= getNumWords()) ?
508 getNumWords() : xlen + ylen) * 8);
516 /// @brief Bitwise AND assignment operator. Performs bitwise AND operation on
517 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
518 APInt& APInt::operator&=(const APInt& RHS) {
519 if (isSingleWord()) {
520 if (RHS.isSingleWord()) VAL &= RHS.VAL;
521 else VAL &= RHS.pVal[0];
523 if (RHS.isSingleWord()) {
524 memset(pVal, 0, (getNumWords() - 1) * 8);
527 unsigned minwords = getNumWords() < RHS.getNumWords() ?
528 getNumWords() : RHS.getNumWords();
529 for (unsigned i = 0; i < minwords; ++i)
530 pVal[i] &= RHS.pVal[i];
531 if (getNumWords() > minwords)
532 memset(pVal+minwords, 0, (getNumWords() - minwords) * 8);
538 /// @brief Bitwise OR assignment operator. Performs bitwise OR operation on
539 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
540 APInt& APInt::operator|=(const APInt& RHS) {
541 if (isSingleWord()) {
542 if (RHS.isSingleWord()) VAL |= RHS.VAL;
543 else VAL |= RHS.pVal[0];
545 if (RHS.isSingleWord()) {
548 unsigned minwords = getNumWords() < RHS.getNumWords() ?
549 getNumWords() : RHS.getNumWords();
550 for (unsigned i = 0; i < minwords; ++i)
551 pVal[i] |= RHS.pVal[i];
558 /// @brief Bitwise XOR assignment operator. Performs bitwise XOR operation on
559 /// this APInt and the given APInt& RHS, assigns the result to this APInt.
560 APInt& APInt::operator^=(const APInt& RHS) {
561 if (isSingleWord()) {
562 if (RHS.isSingleWord()) VAL ^= RHS.VAL;
563 else VAL ^= RHS.pVal[0];
565 if (RHS.isSingleWord()) {
566 for (unsigned i = 0; i < getNumWords(); ++i)
569 unsigned minwords = getNumWords() < RHS.getNumWords() ?
570 getNumWords() : RHS.getNumWords();
571 for (unsigned i = 0; i < minwords; ++i)
572 pVal[i] ^= RHS.pVal[i];
573 if (getNumWords() > minwords)
574 for (unsigned i = minwords; i < getNumWords(); ++i)
582 /// @brief Bitwise AND operator. Performs bitwise AND operation on this APInt
583 /// and the given APInt& RHS.
584 APInt APInt::operator&(const APInt& RHS) const {
589 /// @brief Bitwise OR operator. Performs bitwise OR operation on this APInt
590 /// and the given APInt& RHS.
591 APInt APInt::operator|(const APInt& RHS) const {
598 /// @brief Bitwise XOR operator. Performs bitwise XOR operation on this APInt
599 /// and the given APInt& RHS.
600 APInt APInt::operator^(const APInt& RHS) const {
607 /// @brief Logical AND operator. Performs logical AND operation on this APInt
608 /// and the given APInt& RHS.
609 bool APInt::operator&&(const APInt& RHS) const {
611 return RHS.isSingleWord() ? VAL && RHS.VAL : VAL && RHS.pVal[0];
612 else if (RHS.isSingleWord())
613 return RHS.VAL && pVal[0];
615 unsigned minN = std::min(getNumWords(), RHS.getNumWords());
616 for (unsigned i = 0; i < minN; ++i)
617 if (pVal[i] && RHS.pVal[i])
623 /// @brief Logical OR operator. Performs logical OR operation on this APInt
624 /// and the given APInt& RHS.
625 bool APInt::operator||(const APInt& RHS) const {
627 return RHS.isSingleWord() ? VAL || RHS.VAL : VAL || RHS.pVal[0];
628 else if (RHS.isSingleWord())
629 return RHS.VAL || pVal[0];
631 unsigned minN = std::min(getNumWords(), RHS.getNumWords());
632 for (unsigned i = 0; i < minN; ++i)
633 if (pVal[i] || RHS.pVal[i])
639 /// @brief Logical negation operator. Performs logical negation operation on
641 bool APInt::operator !() const {
645 for (unsigned i = 0; i < getNumWords(); ++i)
651 /// @brief Multiplication operator. Multiplies this APInt by the given APInt&
653 APInt APInt::operator*(const APInt& RHS) const {
660 /// @brief Addition operator. Adds this APInt by the given APInt& RHS.
661 APInt APInt::operator+(const APInt& RHS) const {
668 /// @brief Subtraction operator. Subtracts this APInt by the given APInt& RHS
669 APInt APInt::operator-(const APInt& RHS) const {
675 /// @brief Array-indexing support.
676 bool APInt::operator[](unsigned bitPosition) const {
677 return (maskBit(bitPosition) & (isSingleWord() ?
678 VAL : pVal[whichWord(bitPosition)])) != 0;
681 /// @brief Equality operator. Compare this APInt with the given APInt& RHS
682 /// for the validity of the equality relationship.
683 bool APInt::operator==(const APInt& RHS) const {
684 unsigned n1 = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(),
685 n2 = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros();
686 if (n1 != n2) return false;
687 else if (isSingleWord())
688 return VAL == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
691 return pVal[0] == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
692 for (int i = whichWord(n1 - 1); i >= 0; --i)
693 if (pVal[i] != RHS.pVal[i]) return false;
698 /// @brief Equality operator. Compare this APInt with the given uint64_t value
699 /// for the validity of the equality relationship.
700 bool APInt::operator==(uint64_t Val) const {
704 unsigned n = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros();
706 return pVal[0] == Val;
712 /// @brief Less-than operator. Compare this APInt with the given APInt& RHS
713 /// for the validity of the less-than relationship.
714 bool APInt::operator <(const APInt& RHS) const {
715 unsigned n1 = getNumWords() * 64 - CountLeadingZeros(),
716 n2 = RHS.getNumWords() * 64 - RHS.CountLeadingZeros();
717 if (n1 < n2) return true;
718 else if (n1 > n2) return false;
719 else if (isSingleWord())
720 return VAL < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
723 return pVal[0] < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]);
724 for (int i = whichWord(n1 - 1); i >= 0; --i) {
725 if (pVal[i] > RHS.pVal[i]) return false;
726 else if (pVal[i] < RHS.pVal[i]) return true;
732 /// @brief Less-than-or-equal operator. Compare this APInt with the given
733 /// APInt& RHS for the validity of the less-than-or-equal relationship.
734 bool APInt::operator<=(const APInt& RHS) const {
735 return (*this) == RHS || (*this) < RHS;
738 /// @brief Greater-than operator. Compare this APInt with the given APInt& RHS
739 /// for the validity of the greater-than relationship.
740 bool APInt::operator >(const APInt& RHS) const {
741 return !((*this) <= RHS);
744 /// @brief Greater-than-or-equal operator. Compare this APInt with the given
745 /// APInt& RHS for the validity of the greater-than-or-equal relationship.
746 bool APInt::operator>=(const APInt& RHS) const {
747 return !((*this) < RHS);
750 /// Set the given bit to 1 whose poition is given as "bitPosition".
751 /// @brief Set a given bit to 1.
752 APInt& APInt::set(unsigned bitPosition) {
753 if (isSingleWord()) VAL |= maskBit(bitPosition);
754 else pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
758 /// @brief Set every bit to 1.
759 APInt& APInt::set() {
760 if (isSingleWord()) VAL = -1ULL;
762 for (unsigned i = 0; i < getNumWords(); ++i)
767 /// Set the given bit to 0 whose position is given as "bitPosition".
768 /// @brief Set a given bit to 0.
769 APInt& APInt::clear(unsigned bitPosition) {
770 if (isSingleWord()) VAL &= ~maskBit(bitPosition);
771 else pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
775 /// @brief Set every bit to 0.
776 APInt& APInt::clear() {
777 if (isSingleWord()) VAL = 0;
779 memset(pVal, 0, getNumWords() * 8);
783 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
785 APInt APInt::operator~() const {
791 /// @brief Toggle every bit to its opposite value.
792 APInt& APInt::flip() {
793 if (isSingleWord()) VAL = (~(VAL << (64 - BitsNum))) >> (64 - BitsNum);
796 for (; i < getNumWords() - 1; ++i)
798 unsigned offset = 64 - (BitsNum - 64 * (i - 1));
799 pVal[i] = (~(pVal[i] << offset)) >> offset;
804 /// Toggle a given bit to its opposite value whose position is given
805 /// as "bitPosition".
806 /// @brief Toggles a given bit to its opposite value.
807 APInt& APInt::flip(unsigned bitPosition) {
808 assert(bitPosition < BitsNum && "Out of the bit-width range!");
809 if ((*this)[bitPosition]) clear(bitPosition);
810 else set(bitPosition);
814 /// to_string - This function translates the APInt into a string.
815 std::string APInt::to_string(uint8_t radix) const {
816 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
817 "Radix should be 2, 8, 10, or 16!");
819 unsigned n = getNumWords() * 64 - CountLeadingZeros();
820 std::string format = radix == 8 ?
821 "%0*llo" : (radix == 10 ? "%0*llu" : "%0*llx");
822 // If the radix is a power of 2, set the format of ostringstream,
823 // and output the value into buf.
824 if ((radix & (radix - 1)) == 0) {
825 assert((buf = new char[n / Log2_32(radix) + 2]) &&
826 "Memory allocation failed");
828 sprintf(buf, format.c_str(), 0, VAL);
830 unsigned offset = sprintf(buf, format.c_str(), 0, pVal[whichWord(n-1)]);
831 for (int i = whichWord(n-1) - 1; i >= 0; --i)
832 offset += sprintf(buf + offset, format.c_str(),
833 64 / Log2_32(radix) + (64 % Log2_32(radix) ? 1 : 0), pVal[i]);
836 else { // If the radix = 10, need to translate the value into a
838 assert((buf = new char[(n / 64 + 1) * 20]) && "Memory allocation failed");
840 sprintf(buf, format.c_str(), 0, VAL);
842 // FIXME: To be supported.
845 std::string retStr(buf);
850 /// getMaxValue - This function returns the largest value
851 /// for an APInt of the specified bit-width and if isSign == true,
852 /// it should be largest signed value, otherwise unsigned value.
853 APInt APInt::getMaxValue(unsigned numBits, bool isSign) {
854 APInt APIVal(numBits, 1);
856 return isSign ? APIVal.clear(numBits) : APIVal;
859 /// getMinValue - This function returns the smallest value for
860 /// an APInt of the given bit-width and if isSign == true,
861 /// it should be smallest signed value, otherwise zero.
862 APInt APInt::getMinValue(unsigned numBits, bool isSign) {
863 APInt APIVal(0, numBits);
864 return isSign ? APIVal : APIVal.set(numBits);
867 /// getAllOnesValue - This function returns an all-ones value for
868 /// an APInt of the specified bit-width.
869 APInt APInt::getAllOnesValue(unsigned numBits) {
870 return getMaxValue(numBits, false);
873 /// getNullValue - This function creates an '0' value for an
874 /// APInt of the specified bit-width.
875 APInt APInt::getNullValue(unsigned numBits) {
876 return getMinValue(numBits, true);
879 /// HiBits - This function returns the high "numBits" bits of this APInt.
880 APInt APInt::HiBits(unsigned numBits) const {
881 return APIntOps::lshr(*this, BitsNum - numBits);
884 /// LoBits - This function returns the low "numBits" bits of this APInt.
885 APInt APInt::LoBits(unsigned numBits) const {
886 return APIntOps::lshr(APIntOps::shl(*this, BitsNum - numBits),
890 /// CountLeadingZeros - This function is a APInt version corresponding to
891 /// llvm/include/llvm/Support/MathExtras.h's function
892 /// CountLeadingZeros_{32, 64}. It performs platform optimal form of counting
893 /// the number of zeros from the most significant bit to the first one bit.
894 /// @returns numWord() * 64 if the value is zero.
895 unsigned APInt::CountLeadingZeros() const {
897 return CountLeadingZeros_64(VAL);
899 for (int i = getNumWords() - 1; i >= 0; --i) {
900 unsigned tmp = CountLeadingZeros_64(pVal[i]);
908 /// CountTrailingZero - This function is a APInt version corresponding to
909 /// llvm/include/llvm/Support/MathExtras.h's function
910 /// CountTrailingZeros_{32, 64}. It performs platform optimal form of counting
911 /// the number of zeros from the least significant bit to the first one bit.
912 /// @returns numWord() * 64 if the value is zero.
913 unsigned APInt::CountTrailingZeros() const {
915 return CountTrailingZeros_64(~VAL & (VAL - 1));
916 APInt Tmp = ~(*this) & ((*this) - 1);
917 return getNumWords() * 64 - Tmp.CountLeadingZeros();
920 /// CountPopulation - This function is a APInt version corresponding to
921 /// llvm/include/llvm/Support/MathExtras.h's function
922 /// CountPopulation_{32, 64}. It counts the number of set bits in a value.
923 /// @returns 0 if the value is zero.
924 unsigned APInt::CountPopulation() const {
926 return CountPopulation_64(VAL);
928 for (unsigned i = 0; i < getNumWords(); ++i)
929 Count += CountPopulation_64(pVal[i]);
934 /// ByteSwap - This function returns a byte-swapped representation of the
936 APInt APInt::ByteSwap() const {
938 return APInt(BitsNum, ByteSwap_32(unsigned(VAL)));
939 else if (BitsNum <= 64)
940 return APInt(BitsNum, ByteSwap_64(VAL));
945 /// GreatestCommonDivisor - This function returns the greatest common
946 /// divisor of the two APInt values using Enclid's algorithm.
947 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
949 APInt A = API1, B = API2;
952 B = APIntOps::urem(A, B);
958 /// DoubleRoundToAPInt - This function convert a double value to
960 APInt llvm::APIntOps::DoubleRoundToAPInt(double Double) {
966 bool isNeg = T.I >> 63;
967 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
970 uint64_t mantissa = ((T.I << 12) >> 12) | (1ULL << 52);
972 return isNeg ? -APInt(mantissa >> (52 - exp)) :
973 APInt(mantissa >> (52 - exp));
974 APInt Tmp(mantissa, exp + 1);
975 Tmp = Tmp.shl(exp - 52);
976 return isNeg ? -Tmp : Tmp;
979 /// APIntRoundToDouble - This function convert this APInt to a double.
980 /// The layout for double is as following (IEEE Standard 754):
981 /// --------------------------------------
982 /// | Sign Exponent Fraction Bias |
983 /// |-------------------------------------- |
984 /// | 1[63] 11[62-52] 52[51-00] 1023 |
985 /// --------------------------------------
986 double APInt::APIntRoundToDouble(bool isSigned) const {
987 bool isNeg = isSigned ? (*this)[BitsNum-1] : false;
988 APInt Tmp(isNeg ? -(*this) : (*this));
989 if (Tmp.isSingleWord())
990 return isSigned ? double(int64_t(Tmp.VAL)) : double(Tmp.VAL);
991 unsigned n = Tmp.getNumWords() * 64 - Tmp.CountLeadingZeros();
993 return isSigned ? double(int64_t(Tmp.pVal[0])) : double(Tmp.pVal[0]);
994 // Exponent when normalized to have decimal point directly after
995 // leading one. This is stored excess 1023 in the exponent bit field.
996 uint64_t exp = n - 1;
999 assert(exp <= 1023 && "Infinity value!");
1001 // Number of bits in mantissa including the leading one
1005 mantissa = Tmp.pVal[whichWord(n - 1)] >> (n % 64 - 53);
1007 mantissa = (Tmp.pVal[whichWord(n - 1)] << (53 - n % 64)) |
1008 (Tmp.pVal[whichWord(n - 1) - 1] >> (11 + n % 64));
1009 // The leading bit of mantissa is implicit, so get rid of it.
1010 mantissa &= ~(1ULL << 52);
1011 uint64_t sign = isNeg ? (1ULL << 63) : 0;
1017 T.I = sign | (exp << 52) | mantissa;
1021 /// Arithmetic right-shift this APInt by shiftAmt.
1022 /// @brief Arithmetic right-shift function.
1023 APInt APInt::ashr(unsigned shiftAmt) const {
1025 if (API.isSingleWord())
1026 API.VAL = (((int64_t(API.VAL) << (64 - API.BitsNum)) >> (64 - API.BitsNum))
1027 >> shiftAmt) & (~uint64_t(0UL) >> (64 - API.BitsNum));
1029 if (shiftAmt >= API.BitsNum) {
1030 memset(API.pVal, API[API.BitsNum-1] ? 1 : 0, (API.getNumWords()-1) * 8);
1031 API.pVal[API.getNumWords() - 1] = ~uint64_t(0UL) >>
1032 (64 - API.BitsNum % 64);
1035 for (; i < API.BitsNum - shiftAmt; ++i)
1036 if (API[i+shiftAmt])
1040 for (; i < API.BitsNum; ++i)
1041 API[API.BitsNum-1] ? API.set(i) : API.clear(i);
1047 /// Logical right-shift this APInt by shiftAmt.
1048 /// @brief Logical right-shift function.
1049 APInt APInt::lshr(unsigned shiftAmt) const {
1051 if (API.isSingleWord())
1052 API.VAL >>= shiftAmt;
1054 if (shiftAmt >= API.BitsNum)
1055 memset(API.pVal, 0, API.getNumWords() * 8);
1057 for (i = 0; i < API.BitsNum - shiftAmt; ++i)
1058 if (API[i+shiftAmt]) API.set(i);
1060 for (; i < API.BitsNum; ++i)
1066 /// Left-shift this APInt by shiftAmt.
1067 /// @brief Left-shift function.
1068 APInt APInt::shl(unsigned shiftAmt) const {
1070 if (API.isSingleWord())
1071 API.VAL <<= shiftAmt;
1072 else if (shiftAmt >= API.BitsNum)
1073 memset(API.pVal, 0, API.getNumWords() * 8);
1075 if (unsigned offset = shiftAmt / 64) {
1076 for (unsigned i = API.getNumWords() - 1; i > offset - 1; --i)
1077 API.pVal[i] = API.pVal[i-offset];
1078 memset(API.pVal, 0, offset * 8);
1082 for (i = API.getNumWords() - 1; i > 0; --i)
1083 API.pVal[i] = (API.pVal[i] << shiftAmt) |
1084 (API.pVal[i-1] >> (64-shiftAmt));
1085 API.pVal[i] <<= shiftAmt;
1090 /// Unsigned divide this APInt by APInt RHS.
1091 /// @brief Unsigned division function for APInt.
1092 APInt APInt::udiv(const APInt& RHS) const {
1094 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD -
1095 RHS.CountLeadingZeros();
1096 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1;
1097 assert(ylen && "Divided by zero???");
1098 if (API.isSingleWord()) {
1099 API.VAL = RHS.isSingleWord() ? (API.VAL / RHS.VAL) :
1100 (ylen > 1 ? 0 : API.VAL / RHS.pVal[0]);
1102 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD -
1103 API.CountLeadingZeros();
1104 unsigned xlen = !first2 ? 0 : APInt::whichWord(first2 - 1) + 1;
1108 memset(API.pVal, 0, API.getNumWords() * 8);
1109 else if (API == RHS) {
1110 memset(API.pVal, 0, API.getNumWords() * 8);
1112 } else if (xlen == 1)
1113 API.pVal[0] /= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1115 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen];
1116 assert(xwords && ywords && "Memory Allocation Failed!");
1117 memcpy(xwords, API.pVal, xlen * 8);
1119 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8);
1120 if (unsigned nshift = 63 - (first - 1) % 64) {
1121 lshift(ywords, 0, ywords, ylen, nshift);
1122 unsigned xlentmp = xlen;
1123 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift);
1125 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2);
1126 memset(API.pVal, 0, API.getNumWords() * 8);
1127 memcpy(API.pVal, xwords + ylen, (xlen - ylen) * 8);
1135 /// Unsigned remainder operation on APInt.
1136 /// @brief Function for unsigned remainder operation.
1137 APInt APInt::urem(const APInt& RHS) const {
1139 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD -
1140 RHS.CountLeadingZeros();
1141 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1;
1142 assert(ylen && "Performing remainder operation by zero ???");
1143 if (API.isSingleWord()) {
1144 API.VAL = RHS.isSingleWord() ? (API.VAL % RHS.VAL) :
1145 (ylen > 1 ? API.VAL : API.VAL % RHS.pVal[0]);
1147 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD -
1148 API.CountLeadingZeros();
1149 unsigned xlen = !first2 ? 0 : API.whichWord(first2 - 1) + 1;
1150 if (!xlen || API < RHS)
1152 else if (API == RHS)
1153 memset(API.pVal, 0, API.getNumWords() * 8);
1155 API.pVal[0] %= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1157 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen];
1158 assert(xwords && ywords && "Memory Allocation Failed!");
1159 memcpy(xwords, API.pVal, xlen * 8);
1161 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8);
1162 unsigned nshift = 63 - (first - 1) % 64;
1164 lshift(ywords, 0, ywords, ylen, nshift);
1165 unsigned xlentmp = xlen;
1166 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift);
1168 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2);
1169 memset(API.pVal, 0, API.getNumWords() * 8);
1170 for (unsigned i = 0; i < ylen-1; ++i)
1171 API.pVal[i] = (xwords[i] >> nshift) | (xwords[i+1] << (64 - nshift));
1172 API.pVal[ylen-1] = xwords[ylen-1] >> nshift;