1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
12 //
13 //===----------------------------------------------------------------------===//
14
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"
24 #include <cmath>
25 #include <limits>
26 #include <cstring>
27 #include <cstdlib>
28 using namespace llvm;
29
30 /// A utility function for allocating memory, checking for allocation failures,
31 /// and ensuring the contents are zeroed.
getClearedMemory(unsigned numWords)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));
36 return result;
37 }
38
39 /// A utility function for allocating memory and checking for allocation
40 /// failure. The content is not zeroed.
getMemory(unsigned numWords)41 inline static uint64_t* getMemory(unsigned numWords) {
42 uint64_t * result = new uint64_t[numWords];
43 assert(result && "APInt memory allocation fails!");
44 return result;
45 }
46
47 /// A utility function that converts a character to a digit.
getDigit(char cdigit,uint8_t radix)48 inline static unsigned getDigit(char cdigit, uint8_t radix) {
49 unsigned r;
50
51 if (radix == 16) {
52 r = cdigit - '0';
53 if (r <= 9)
54 return r;
55
56 r = cdigit - 'A';
57 if (r <= 5)
58 return r + 10;
59
60 r = cdigit - 'a';
61 if (r <= 5)
62 return r + 10;
63 }
64
65 r = cdigit - '0';
66 if (r < radix)
67 return r;
68
69 return -1U;
70 }
71
72
initSlowCase(unsigned numBits,uint64_t val,bool isSigned)73 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
74 pVal = getClearedMemory(getNumWords());
75 pVal[0] = val;
76 if (isSigned && int64_t(val) < 0)
77 for (unsigned i = 1; i < getNumWords(); ++i)
78 pVal[i] = -1ULL;
79 }
80
initSlowCase(const APInt & that)81 void APInt::initSlowCase(const APInt& that) {
82 pVal = getMemory(getNumWords());
83 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
84 }
85
initFromArray(ArrayRef<uint64_t> bigVal)86 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
87 assert(BitWidth && "Bitwidth too small");
88 assert(bigVal.data() && "Null pointer detected!");
89 if (isSingleWord())
90 VAL = bigVal[0];
91 else {
92 // Get memory, cleared to 0
93 pVal = getClearedMemory(getNumWords());
94 // Calculate the number of words to copy
95 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
96 // Copy the words from bigVal to pVal
97 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
98 }
99 // Make sure unused high bits are cleared
100 clearUnusedBits();
101 }
102
APInt(unsigned numBits,ArrayRef<uint64_t> bigVal)103 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
104 : BitWidth(numBits), VAL(0) {
105 initFromArray(bigVal);
106 }
107
APInt(unsigned numBits,unsigned numWords,const uint64_t bigVal[])108 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
109 : BitWidth(numBits), VAL(0) {
110 initFromArray(makeArrayRef(bigVal, numWords));
111 }
112
APInt(unsigned numbits,StringRef Str,uint8_t radix)113 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
114 : BitWidth(numbits), VAL(0) {
115 assert(BitWidth && "Bitwidth too small");
116 fromString(numbits, Str, radix);
117 }
118
AssignSlowCase(const APInt & RHS)119 APInt& APInt::AssignSlowCase(const APInt& RHS) {
120 // Don't do anything for X = X
121 if (this == &RHS)
122 return *this;
123
124 if (BitWidth == RHS.getBitWidth()) {
125 // assume same bit-width single-word case is already handled
126 assert(!isSingleWord());
127 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
128 return *this;
129 }
130
131 if (isSingleWord()) {
132 // assume case where both are single words is already handled
133 assert(!RHS.isSingleWord());
134 VAL = 0;
135 pVal = getMemory(RHS.getNumWords());
136 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
137 } else if (getNumWords() == RHS.getNumWords())
138 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
139 else if (RHS.isSingleWord()) {
140 delete [] pVal;
141 VAL = RHS.VAL;
142 } else {
143 delete [] pVal;
144 pVal = getMemory(RHS.getNumWords());
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
146 }
147 BitWidth = RHS.BitWidth;
148 return clearUnusedBits();
149 }
150
operator =(uint64_t RHS)151 APInt& APInt::operator=(uint64_t RHS) {
152 if (isSingleWord())
153 VAL = RHS;
154 else {
155 pVal[0] = RHS;
156 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
157 }
158 return clearUnusedBits();
159 }
160
161 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
Profile(FoldingSetNodeID & ID) const162 void APInt::Profile(FoldingSetNodeID& ID) const {
163 ID.AddInteger(BitWidth);
164
165 if (isSingleWord()) {
166 ID.AddInteger(VAL);
167 return;
168 }
169
170 unsigned NumWords = getNumWords();
171 for (unsigned i = 0; i < NumWords; ++i)
172 ID.AddInteger(pVal[i]);
173 }
174
175 /// add_1 - This function adds a single "digit" integer, y, to the multiple
176 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
177 /// 1 is returned if there is a carry out, otherwise 0 is returned.
178 /// @returns the carry of the addition.
add_1(uint64_t dest[],uint64_t x[],unsigned len,uint64_t y)179 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
180 for (unsigned i = 0; i < len; ++i) {
181 dest[i] = y + x[i];
182 if (dest[i] < y)
183 y = 1; // Carry one to next digit.
184 else {
185 y = 0; // No need to carry so exit early
186 break;
187 }
188 }
189 return y;
190 }
191
192 /// @brief Prefix increment operator. Increments the APInt by one.
operator ++()193 APInt& APInt::operator++() {
194 if (isSingleWord())
195 ++VAL;
196 else
197 add_1(pVal, pVal, getNumWords(), 1);
198 return clearUnusedBits();
199 }
200
201 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
202 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
203 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
204 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
205 /// In other words, if y > x then this function returns 1, otherwise 0.
206 /// @returns the borrow out of the subtraction
sub_1(uint64_t x[],unsigned len,uint64_t y)207 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
208 for (unsigned i = 0; i < len; ++i) {
209 uint64_t X = x[i];
210 x[i] -= y;
211 if (y > X)
212 y = 1; // We have to "borrow 1" from next "digit"
213 else {
214 y = 0; // No need to borrow
215 break; // Remaining digits are unchanged so exit early
216 }
217 }
218 return bool(y);
219 }
220
221 /// @brief Prefix decrement operator. Decrements the APInt by one.
operator --()222 APInt& APInt::operator--() {
223 if (isSingleWord())
224 --VAL;
225 else
226 sub_1(pVal, getNumWords(), 1);
227 return clearUnusedBits();
228 }
229
230 /// add - This function adds the integer array x to the integer array Y and
231 /// places the result in dest.
232 /// @returns the carry out from the addition
233 /// @brief General addition of 64-bit integer arrays
add(uint64_t * dest,const uint64_t * x,const uint64_t * y,unsigned len)234 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
235 unsigned len) {
236 bool carry = false;
237 for (unsigned i = 0; i< len; ++i) {
238 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
239 dest[i] = x[i] + y[i] + carry;
240 carry = dest[i] < limit || (carry && dest[i] == limit);
241 }
242 return carry;
243 }
244
245 /// Adds the RHS APint to this APInt.
246 /// @returns this, after addition of RHS.
247 /// @brief Addition assignment operator.
operator +=(const APInt & RHS)248 APInt& APInt::operator+=(const APInt& RHS) {
249 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
250 if (isSingleWord())
251 VAL += RHS.VAL;
252 else {
253 add(pVal, pVal, RHS.pVal, getNumWords());
254 }
255 return clearUnusedBits();
256 }
257
258 /// Subtracts the integer array y from the integer array x
259 /// @returns returns the borrow out.
260 /// @brief Generalized subtraction of 64-bit integer arrays.
sub(uint64_t * dest,const uint64_t * x,const uint64_t * y,unsigned len)261 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
262 unsigned len) {
263 bool borrow = false;
264 for (unsigned i = 0; i < len; ++i) {
265 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
266 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
267 dest[i] = x_tmp - y[i];
268 }
269 return borrow;
270 }
271
272 /// Subtracts the RHS APInt from this APInt
273 /// @returns this, after subtraction
274 /// @brief Subtraction assignment operator.
operator -=(const APInt & RHS)275 APInt& APInt::operator-=(const APInt& RHS) {
276 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
277 if (isSingleWord())
278 VAL -= RHS.VAL;
279 else
280 sub(pVal, pVal, RHS.pVal, getNumWords());
281 return clearUnusedBits();
282 }
283
284 /// Multiplies an integer array, x, by a uint64_t integer and places the result
285 /// into dest.
286 /// @returns the carry out of the multiplication.
287 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
mul_1(uint64_t dest[],uint64_t x[],unsigned len,uint64_t y)288 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
289 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
290 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
291 uint64_t carry = 0;
292
293 // For each digit of x.
294 for (unsigned i = 0; i < len; ++i) {
295 // Split x into high and low words
296 uint64_t lx = x[i] & 0xffffffffULL;
297 uint64_t hx = x[i] >> 32;
298 // hasCarry - A flag to indicate if there is a carry to the next digit.
299 // hasCarry == 0, no carry
300 // hasCarry == 1, has carry
301 // hasCarry == 2, no carry and the calculation result == 0.
302 uint8_t hasCarry = 0;
303 dest[i] = carry + lx * ly;
304 // Determine if the add above introduces carry.
305 hasCarry = (dest[i] < carry) ? 1 : 0;
306 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
307 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
308 // (2^32 - 1) + 2^32 = 2^64.
309 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
310
311 carry += (lx * hy) & 0xffffffffULL;
312 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
313 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
314 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
315 }
316 return carry;
317 }
318
319 /// Multiplies integer array x by integer array y and stores the result into
320 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
321 /// @brief Generalized multiplicate of integer arrays.
mul(uint64_t dest[],uint64_t x[],unsigned xlen,uint64_t y[],unsigned ylen)322 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
323 unsigned ylen) {
324 dest[xlen] = mul_1(dest, x, xlen, y[0]);
325 for (unsigned i = 1; i < ylen; ++i) {
326 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
327 uint64_t carry = 0, lx = 0, hx = 0;
328 for (unsigned j = 0; j < xlen; ++j) {
329 lx = x[j] & 0xffffffffULL;
330 hx = x[j] >> 32;
331 // hasCarry - A flag to indicate if has carry.
332 // hasCarry == 0, no carry
333 // hasCarry == 1, has carry
334 // hasCarry == 2, no carry and the calculation result == 0.
335 uint8_t hasCarry = 0;
336 uint64_t resul = carry + lx * ly;
337 hasCarry = (resul < carry) ? 1 : 0;
338 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
339 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
340
341 carry += (lx * hy) & 0xffffffffULL;
342 resul = (carry << 32) | (resul & 0xffffffffULL);
343 dest[i+j] += resul;
344 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
345 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
346 ((lx * hy) >> 32) + hx * hy;
347 }
348 dest[i+xlen] = carry;
349 }
350 }
351
operator *=(const APInt & RHS)352 APInt& APInt::operator*=(const APInt& RHS) {
353 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
354 if (isSingleWord()) {
355 VAL *= RHS.VAL;
356 clearUnusedBits();
357 return *this;
358 }
359
360 // Get some bit facts about LHS and check for zero
361 unsigned lhsBits = getActiveBits();
362 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
363 if (!lhsWords)
364 // 0 * X ===> 0
365 return *this;
366
367 // Get some bit facts about RHS and check for zero
368 unsigned rhsBits = RHS.getActiveBits();
369 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
370 if (!rhsWords) {
371 // X * 0 ===> 0
372 clearAllBits();
373 return *this;
374 }
375
376 // Allocate space for the result
377 unsigned destWords = rhsWords + lhsWords;
378 uint64_t *dest = getMemory(destWords);
379
380 // Perform the long multiply
381 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
382
383 // Copy result back into *this
384 clearAllBits();
385 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
386 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
387
388 // delete dest array and return
389 delete[] dest;
390 return *this;
391 }
392
operator &=(const APInt & RHS)393 APInt& APInt::operator&=(const APInt& RHS) {
394 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
395 if (isSingleWord()) {
396 VAL &= RHS.VAL;
397 return *this;
398 }
399 unsigned numWords = getNumWords();
400 for (unsigned i = 0; i < numWords; ++i)
401 pVal[i] &= RHS.pVal[i];
402 return *this;
403 }
404
operator |=(const APInt & RHS)405 APInt& APInt::operator|=(const APInt& RHS) {
406 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
407 if (isSingleWord()) {
408 VAL |= RHS.VAL;
409 return *this;
410 }
411 unsigned numWords = getNumWords();
412 for (unsigned i = 0; i < numWords; ++i)
413 pVal[i] |= RHS.pVal[i];
414 return *this;
415 }
416
operator ^=(const APInt & RHS)417 APInt& APInt::operator^=(const APInt& RHS) {
418 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
419 if (isSingleWord()) {
420 VAL ^= RHS.VAL;
421 this->clearUnusedBits();
422 return *this;
423 }
424 unsigned numWords = getNumWords();
425 for (unsigned i = 0; i < numWords; ++i)
426 pVal[i] ^= RHS.pVal[i];
427 return clearUnusedBits();
428 }
429
AndSlowCase(const APInt & RHS) const430 APInt APInt::AndSlowCase(const APInt& RHS) const {
431 unsigned numWords = getNumWords();
432 uint64_t* val = getMemory(numWords);
433 for (unsigned i = 0; i < numWords; ++i)
434 val[i] = pVal[i] & RHS.pVal[i];
435 return APInt(val, getBitWidth());
436 }
437
OrSlowCase(const APInt & RHS) const438 APInt APInt::OrSlowCase(const APInt& RHS) const {
439 unsigned numWords = getNumWords();
440 uint64_t *val = getMemory(numWords);
441 for (unsigned i = 0; i < numWords; ++i)
442 val[i] = pVal[i] | RHS.pVal[i];
443 return APInt(val, getBitWidth());
444 }
445
XorSlowCase(const APInt & RHS) const446 APInt APInt::XorSlowCase(const APInt& RHS) const {
447 unsigned numWords = getNumWords();
448 uint64_t *val = getMemory(numWords);
449 for (unsigned i = 0; i < numWords; ++i)
450 val[i] = pVal[i] ^ RHS.pVal[i];
451
452 // 0^0==1 so clear the high bits in case they got set.
453 return APInt(val, getBitWidth()).clearUnusedBits();
454 }
455
operator !() const456 bool APInt::operator !() const {
457 if (isSingleWord())
458 return !VAL;
459
460 for (unsigned i = 0; i < getNumWords(); ++i)
461 if (pVal[i])
462 return false;
463 return true;
464 }
465
operator *(const APInt & RHS) const466 APInt APInt::operator*(const APInt& RHS) const {
467 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
468 if (isSingleWord())
469 return APInt(BitWidth, VAL * RHS.VAL);
470 APInt Result(*this);
471 Result *= RHS;
472 return Result.clearUnusedBits();
473 }
474
operator +(const APInt & RHS) const475 APInt APInt::operator+(const APInt& RHS) const {
476 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
477 if (isSingleWord())
478 return APInt(BitWidth, VAL + RHS.VAL);
479 APInt Result(BitWidth, 0);
480 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
481 return Result.clearUnusedBits();
482 }
483
operator -(const APInt & RHS) const484 APInt APInt::operator-(const APInt& RHS) const {
485 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
486 if (isSingleWord())
487 return APInt(BitWidth, VAL - RHS.VAL);
488 APInt Result(BitWidth, 0);
489 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
490 return Result.clearUnusedBits();
491 }
492
operator [](unsigned bitPosition) const493 bool APInt::operator[](unsigned bitPosition) const {
494 assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
495 return (maskBit(bitPosition) &
496 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
497 }
498
EqualSlowCase(const APInt & RHS) const499 bool APInt::EqualSlowCase(const APInt& RHS) const {
500 // Get some facts about the number of bits used in the two operands.
501 unsigned n1 = getActiveBits();
502 unsigned n2 = RHS.getActiveBits();
503
504 // If the number of bits isn't the same, they aren't equal
505 if (n1 != n2)
506 return false;
507
508 // If the number of bits fits in a word, we only need to compare the low word.
509 if (n1 <= APINT_BITS_PER_WORD)
510 return pVal[0] == RHS.pVal[0];
511
512 // Otherwise, compare everything
513 for (int i = whichWord(n1 - 1); i >= 0; --i)
514 if (pVal[i] != RHS.pVal[i])
515 return false;
516 return true;
517 }
518
EqualSlowCase(uint64_t Val) const519 bool APInt::EqualSlowCase(uint64_t Val) const {
520 unsigned n = getActiveBits();
521 if (n <= APINT_BITS_PER_WORD)
522 return pVal[0] == Val;
523 else
524 return false;
525 }
526
ult(const APInt & RHS) const527 bool APInt::ult(const APInt& RHS) const {
528 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
529 if (isSingleWord())
530 return VAL < RHS.VAL;
531
532 // Get active bit length of both operands
533 unsigned n1 = getActiveBits();
534 unsigned n2 = RHS.getActiveBits();
535
536 // If magnitude of LHS is less than RHS, return true.
537 if (n1 < n2)
538 return true;
539
540 // If magnitude of RHS is greather than LHS, return false.
541 if (n2 < n1)
542 return false;
543
544 // If they bot fit in a word, just compare the low order word
545 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
546 return pVal[0] < RHS.pVal[0];
547
548 // Otherwise, compare all words
549 unsigned topWord = whichWord(std::max(n1,n2)-1);
550 for (int i = topWord; i >= 0; --i) {
551 if (pVal[i] > RHS.pVal[i])
552 return false;
553 if (pVal[i] < RHS.pVal[i])
554 return true;
555 }
556 return false;
557 }
558
slt(const APInt & RHS) const559 bool APInt::slt(const APInt& RHS) const {
560 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
561 if (isSingleWord()) {
562 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
563 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
564 return lhsSext < rhsSext;
565 }
566
567 APInt lhs(*this);
568 APInt rhs(RHS);
569 bool lhsNeg = isNegative();
570 bool rhsNeg = rhs.isNegative();
571 if (lhsNeg) {
572 // Sign bit is set so perform two's complement to make it positive
573 lhs.flipAllBits();
574 lhs++;
575 }
576 if (rhsNeg) {
577 // Sign bit is set so perform two's complement to make it positive
578 rhs.flipAllBits();
579 rhs++;
580 }
581
582 // Now we have unsigned values to compare so do the comparison if necessary
583 // based on the negativeness of the values.
584 if (lhsNeg)
585 if (rhsNeg)
586 return lhs.ugt(rhs);
587 else
588 return true;
589 else if (rhsNeg)
590 return false;
591 else
592 return lhs.ult(rhs);
593 }
594
setBit(unsigned bitPosition)595 void APInt::setBit(unsigned bitPosition) {
596 if (isSingleWord())
597 VAL |= maskBit(bitPosition);
598 else
599 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
600 }
601
602 /// Set the given bit to 0 whose position is given as "bitPosition".
603 /// @brief Set a given bit to 0.
clearBit(unsigned bitPosition)604 void APInt::clearBit(unsigned bitPosition) {
605 if (isSingleWord())
606 VAL &= ~maskBit(bitPosition);
607 else
608 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
609 }
610
611 /// @brief Toggle every bit to its opposite value.
612
613 /// Toggle a given bit to its opposite value whose position is given
614 /// as "bitPosition".
615 /// @brief Toggles a given bit to its opposite value.
flipBit(unsigned bitPosition)616 void APInt::flipBit(unsigned bitPosition) {
617 assert(bitPosition < BitWidth && "Out of the bit-width range!");
618 if ((*this)[bitPosition]) clearBit(bitPosition);
619 else setBit(bitPosition);
620 }
621
getBitsNeeded(StringRef str,uint8_t radix)622 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
623 assert(!str.empty() && "Invalid string length");
624 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
625 "Radix should be 2, 8, 10, or 16!");
626
627 size_t slen = str.size();
628
629 // Each computation below needs to know if it's negative.
630 StringRef::iterator p = str.begin();
631 unsigned isNegative = *p == '-';
632 if (*p == '-' || *p == '+') {
633 p++;
634 slen--;
635 assert(slen && "String is only a sign, needs a value.");
636 }
637
638 // For radixes of power-of-two values, the bits required is accurately and
639 // easily computed
640 if (radix == 2)
641 return slen + isNegative;
642 if (radix == 8)
643 return slen * 3 + isNegative;
644 if (radix == 16)
645 return slen * 4 + isNegative;
646
647 // This is grossly inefficient but accurate. We could probably do something
648 // with a computation of roughly slen*64/20 and then adjust by the value of
649 // the first few digits. But, I'm not sure how accurate that could be.
650
651 // Compute a sufficient number of bits that is always large enough but might
652 // be too large. This avoids the assertion in the constructor. This
653 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
654 // bits in that case.
655 unsigned sufficient = slen == 1 ? 4 : slen * 64/18;
656
657 // Convert to the actual binary value.
658 APInt tmp(sufficient, StringRef(p, slen), radix);
659
660 // Compute how many bits are required. If the log is infinite, assume we need
661 // just bit.
662 unsigned log = tmp.logBase2();
663 if (log == (unsigned)-1) {
664 return isNegative + 1;
665 } else {
666 return isNegative + log + 1;
667 }
668 }
669
670 // From http://www.burtleburtle.net, byBob Jenkins.
671 // When targeting x86, both GCC and LLVM seem to recognize this as a
672 // rotate instruction.
673 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
674
675 // From http://www.burtleburtle.net, by Bob Jenkins.
676 #define mix(a,b,c) \
677 { \
678 a -= c; a ^= rot(c, 4); c += b; \
679 b -= a; b ^= rot(a, 6); a += c; \
680 c -= b; c ^= rot(b, 8); b += a; \
681 a -= c; a ^= rot(c,16); c += b; \
682 b -= a; b ^= rot(a,19); a += c; \
683 c -= b; c ^= rot(b, 4); b += a; \
684 }
685
686 // From http://www.burtleburtle.net, by Bob Jenkins.
687 #define final(a,b,c) \
688 { \
689 c ^= b; c -= rot(b,14); \
690 a ^= c; a -= rot(c,11); \
691 b ^= a; b -= rot(a,25); \
692 c ^= b; c -= rot(b,16); \
693 a ^= c; a -= rot(c,4); \
694 b ^= a; b -= rot(a,14); \
695 c ^= b; c -= rot(b,24); \
696 }
697
698 // hashword() was adapted from http://www.burtleburtle.net, by Bob
699 // Jenkins. k is a pointer to an array of uint32_t values; length is
700 // the length of the key, in 32-bit chunks. This version only handles
701 // keys that are a multiple of 32 bits in size.
hashword(const uint64_t * k64,size_t length)702 static inline uint32_t hashword(const uint64_t *k64, size_t length)
703 {
704 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
705 uint32_t a,b,c;
706
707 /* Set up the internal state */
708 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
709
710 /*------------------------------------------------- handle most of the key */
711 while (length > 3) {
712 a += k[0];
713 b += k[1];
714 c += k[2];
715 mix(a,b,c);
716 length -= 3;
717 k += 3;
718 }
719
720 /*------------------------------------------- handle the last 3 uint32_t's */
721 switch (length) { /* all the case statements fall through */
722 case 3 : c+=k[2];
723 case 2 : b+=k[1];
724 case 1 : a+=k[0];
725 final(a,b,c);
726 case 0: /* case 0: nothing left to add */
727 break;
728 }
729 /*------------------------------------------------------ report the result */
730 return c;
731 }
732
733 // hashword8() was adapted from http://www.burtleburtle.net, by Bob
734 // Jenkins. This computes a 32-bit hash from one 64-bit word. When
735 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this
736 // function into about 35 instructions when inlined.
hashword8(const uint64_t k64)737 static inline uint32_t hashword8(const uint64_t k64)
738 {
739 uint32_t a,b,c;
740 a = b = c = 0xdeadbeef + 4;
741 b += k64 >> 32;
742 a += k64 & 0xffffffff;
743 final(a,b,c);
744 return c;
745 }
746 #undef final
747 #undef mix
748 #undef rot
749
getHashValue() const750 uint64_t APInt::getHashValue() const {
751 uint64_t hash;
752 if (isSingleWord())
753 hash = hashword8(VAL);
754 else
755 hash = hashword(pVal, getNumWords()*2);
756 return hash;
757 }
758
759 /// HiBits - This function returns the high "numBits" bits of this APInt.
getHiBits(unsigned numBits) const760 APInt APInt::getHiBits(unsigned numBits) const {
761 return APIntOps::lshr(*this, BitWidth - numBits);
762 }
763
764 /// LoBits - This function returns the low "numBits" bits of this APInt.
getLoBits(unsigned numBits) const765 APInt APInt::getLoBits(unsigned numBits) const {
766 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
767 BitWidth - numBits);
768 }
769
countLeadingZerosSlowCase() const770 unsigned APInt::countLeadingZerosSlowCase() const {
771 // Treat the most significand word differently because it might have
772 // meaningless bits set beyond the precision.
773 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
774 integerPart MSWMask;
775 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
776 else {
777 MSWMask = ~integerPart(0);
778 BitsInMSW = APINT_BITS_PER_WORD;
779 }
780
781 unsigned i = getNumWords();
782 integerPart MSW = pVal[i-1] & MSWMask;
783 if (MSW)
784 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
785
786 unsigned Count = BitsInMSW;
787 for (--i; i > 0u; --i) {
788 if (pVal[i-1] == 0)
789 Count += APINT_BITS_PER_WORD;
790 else {
791 Count += CountLeadingZeros_64(pVal[i-1]);
792 break;
793 }
794 }
795 return Count;
796 }
797
countLeadingOnes_64(uint64_t V,unsigned skip)798 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
799 unsigned Count = 0;
800 if (skip)
801 V <<= skip;
802 while (V && (V & (1ULL << 63))) {
803 Count++;
804 V <<= 1;
805 }
806 return Count;
807 }
808
countLeadingOnes() const809 unsigned APInt::countLeadingOnes() const {
810 if (isSingleWord())
811 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
812
813 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
814 unsigned shift;
815 if (!highWordBits) {
816 highWordBits = APINT_BITS_PER_WORD;
817 shift = 0;
818 } else {
819 shift = APINT_BITS_PER_WORD - highWordBits;
820 }
821 int i = getNumWords() - 1;
822 unsigned Count = countLeadingOnes_64(pVal[i], shift);
823 if (Count == highWordBits) {
824 for (i--; i >= 0; --i) {
825 if (pVal[i] == -1ULL)
826 Count += APINT_BITS_PER_WORD;
827 else {
828 Count += countLeadingOnes_64(pVal[i], 0);
829 break;
830 }
831 }
832 }
833 return Count;
834 }
835
countTrailingZeros() const836 unsigned APInt::countTrailingZeros() const {
837 if (isSingleWord())
838 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
839 unsigned Count = 0;
840 unsigned i = 0;
841 for (; i < getNumWords() && pVal[i] == 0; ++i)
842 Count += APINT_BITS_PER_WORD;
843 if (i < getNumWords())
844 Count += CountTrailingZeros_64(pVal[i]);
845 return std::min(Count, BitWidth);
846 }
847
countTrailingOnesSlowCase() const848 unsigned APInt::countTrailingOnesSlowCase() const {
849 unsigned Count = 0;
850 unsigned i = 0;
851 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
852 Count += APINT_BITS_PER_WORD;
853 if (i < getNumWords())
854 Count += CountTrailingOnes_64(pVal[i]);
855 return std::min(Count, BitWidth);
856 }
857
countPopulationSlowCase() const858 unsigned APInt::countPopulationSlowCase() const {
859 unsigned Count = 0;
860 for (unsigned i = 0; i < getNumWords(); ++i)
861 Count += CountPopulation_64(pVal[i]);
862 return Count;
863 }
864
byteSwap() const865 APInt APInt::byteSwap() const {
866 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
867 if (BitWidth == 16)
868 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
869 else if (BitWidth == 32)
870 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
871 else if (BitWidth == 48) {
872 unsigned Tmp1 = unsigned(VAL >> 16);
873 Tmp1 = ByteSwap_32(Tmp1);
874 uint16_t Tmp2 = uint16_t(VAL);
875 Tmp2 = ByteSwap_16(Tmp2);
876 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
877 } else if (BitWidth == 64)
878 return APInt(BitWidth, ByteSwap_64(VAL));
879 else {
880 APInt Result(BitWidth, 0);
881 char *pByte = (char*)Result.pVal;
882 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
883 char Tmp = pByte[i];
884 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
885 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
886 }
887 return Result;
888 }
889 }
890
GreatestCommonDivisor(const APInt & API1,const APInt & API2)891 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
892 const APInt& API2) {
893 APInt A = API1, B = API2;
894 while (!!B) {
895 APInt T = B;
896 B = APIntOps::urem(A, B);
897 A = T;
898 }
899 return A;
900 }
901
RoundDoubleToAPInt(double Double,unsigned width)902 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
903 union {
904 double D;
905 uint64_t I;
906 } T;
907 T.D = Double;
908
909 // Get the sign bit from the highest order bit
910 bool isNeg = T.I >> 63;
911
912 // Get the 11-bit exponent and adjust for the 1023 bit bias
913 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
914
915 // If the exponent is negative, the value is < 0 so just return 0.
916 if (exp < 0)
917 return APInt(width, 0u);
918
919 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
920 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
921
922 // If the exponent doesn't shift all bits out of the mantissa
923 if (exp < 52)
924 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
925 APInt(width, mantissa >> (52 - exp));
926
927 // If the client didn't provide enough bits for us to shift the mantissa into
928 // then the result is undefined, just return 0
929 if (width <= exp - 52)
930 return APInt(width, 0);
931
932 // Otherwise, we have to shift the mantissa bits up to the right location
933 APInt Tmp(width, mantissa);
934 Tmp = Tmp.shl((unsigned)exp - 52);
935 return isNeg ? -Tmp : Tmp;
936 }
937
938 /// RoundToDouble - This function converts this APInt to a double.
939 /// The layout for double is as following (IEEE Standard 754):
940 /// --------------------------------------
941 /// | Sign Exponent Fraction Bias |
942 /// |-------------------------------------- |
943 /// | 1[63] 11[62-52] 52[51-00] 1023 |
944 /// --------------------------------------
roundToDouble(bool isSigned) const945 double APInt::roundToDouble(bool isSigned) const {
946
947 // Handle the simple case where the value is contained in one uint64_t.
948 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
949 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
950 if (isSigned) {
951 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
952 return double(sext);
953 } else
954 return double(getWord(0));
955 }
956
957 // Determine if the value is negative.
958 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
959
960 // Construct the absolute value if we're negative.
961 APInt Tmp(isNeg ? -(*this) : (*this));
962
963 // Figure out how many bits we're using.
964 unsigned n = Tmp.getActiveBits();
965
966 // The exponent (without bias normalization) is just the number of bits
967 // we are using. Note that the sign bit is gone since we constructed the
968 // absolute value.
969 uint64_t exp = n;
970
971 // Return infinity for exponent overflow
972 if (exp > 1023) {
973 if (!isSigned || !isNeg)
974 return std::numeric_limits<double>::infinity();
975 else
976 return -std::numeric_limits<double>::infinity();
977 }
978 exp += 1023; // Increment for 1023 bias
979
980 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
981 // extract the high 52 bits from the correct words in pVal.
982 uint64_t mantissa;
983 unsigned hiWord = whichWord(n-1);
984 if (hiWord == 0) {
985 mantissa = Tmp.pVal[0];
986 if (n > 52)
987 mantissa >>= n - 52; // shift down, we want the top 52 bits.
988 } else {
989 assert(hiWord > 0 && "huh?");
990 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
991 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
992 mantissa = hibits | lobits;
993 }
994
995 // The leading bit of mantissa is implicit, so get rid of it.
996 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
997 union {
998 double D;
999 uint64_t I;
1000 } T;
1001 T.I = sign | (exp << 52) | mantissa;
1002 return T.D;
1003 }
1004
1005 // Truncate to new width.
trunc(unsigned width) const1006 APInt APInt::trunc(unsigned width) const {
1007 assert(width < BitWidth && "Invalid APInt Truncate request");
1008 assert(width && "Can't truncate to 0 bits");
1009
1010 if (width <= APINT_BITS_PER_WORD)
1011 return APInt(width, getRawData()[0]);
1012
1013 APInt Result(getMemory(getNumWords(width)), width);
1014
1015 // Copy full words.
1016 unsigned i;
1017 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
1018 Result.pVal[i] = pVal[i];
1019
1020 // Truncate and copy any partial word.
1021 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
1022 if (bits != 0)
1023 Result.pVal[i] = pVal[i] << bits >> bits;
1024
1025 return Result;
1026 }
1027
1028 // Sign extend to a new width.
sext(unsigned width) const1029 APInt APInt::sext(unsigned width) const {
1030 assert(width > BitWidth && "Invalid APInt SignExtend request");
1031
1032 if (width <= APINT_BITS_PER_WORD) {
1033 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
1034 val = (int64_t)val >> (width - BitWidth);
1035 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
1036 }
1037
1038 APInt Result(getMemory(getNumWords(width)), width);
1039
1040 // Copy full words.
1041 unsigned i;
1042 uint64_t word = 0;
1043 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
1044 word = getRawData()[i];
1045 Result.pVal[i] = word;
1046 }
1047
1048 // Read and sign-extend any partial word.
1049 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
1050 if (bits != 0)
1051 word = (int64_t)getRawData()[i] << bits >> bits;
1052 else
1053 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1054
1055 // Write remaining full words.
1056 for (; i != width / APINT_BITS_PER_WORD; i++) {
1057 Result.pVal[i] = word;
1058 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
1059 }
1060
1061 // Write any partial word.
1062 bits = (0 - width) % APINT_BITS_PER_WORD;
1063 if (bits != 0)
1064 Result.pVal[i] = word << bits >> bits;
1065
1066 return Result;
1067 }
1068
1069 // Zero extend to a new width.
zext(unsigned width) const1070 APInt APInt::zext(unsigned width) const {
1071 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1072
1073 if (width <= APINT_BITS_PER_WORD)
1074 return APInt(width, VAL);
1075
1076 APInt Result(getMemory(getNumWords(width)), width);
1077
1078 // Copy words.
1079 unsigned i;
1080 for (i = 0; i != getNumWords(); i++)
1081 Result.pVal[i] = getRawData()[i];
1082
1083 // Zero remaining words.
1084 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
1085
1086 return Result;
1087 }
1088
zextOrTrunc(unsigned width) const1089 APInt APInt::zextOrTrunc(unsigned width) const {
1090 if (BitWidth < width)
1091 return zext(width);
1092 if (BitWidth > width)
1093 return trunc(width);
1094 return *this;
1095 }
1096
sextOrTrunc(unsigned width) const1097 APInt APInt::sextOrTrunc(unsigned width) const {
1098 if (BitWidth < width)
1099 return sext(width);
1100 if (BitWidth > width)
1101 return trunc(width);
1102 return *this;
1103 }
1104
1105 /// Arithmetic right-shift this APInt by shiftAmt.
1106 /// @brief Arithmetic right-shift function.
ashr(const APInt & shiftAmt) const1107 APInt APInt::ashr(const APInt &shiftAmt) const {
1108 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1109 }
1110
1111 /// Arithmetic right-shift this APInt by shiftAmt.
1112 /// @brief Arithmetic right-shift function.
ashr(unsigned shiftAmt) const1113 APInt APInt::ashr(unsigned shiftAmt) const {
1114 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1115 // Handle a degenerate case
1116 if (shiftAmt == 0)
1117 return *this;
1118
1119 // Handle single word shifts with built-in ashr
1120 if (isSingleWord()) {
1121 if (shiftAmt == BitWidth)
1122 return APInt(BitWidth, 0); // undefined
1123 else {
1124 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1125 return APInt(BitWidth,
1126 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1127 }
1128 }
1129
1130 // If all the bits were shifted out, the result is, technically, undefined.
1131 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1132 // issues in the algorithm below.
1133 if (shiftAmt == BitWidth) {
1134 if (isNegative())
1135 return APInt(BitWidth, -1ULL, true);
1136 else
1137 return APInt(BitWidth, 0);
1138 }
1139
1140 // Create some space for the result.
1141 uint64_t * val = new uint64_t[getNumWords()];
1142
1143 // Compute some values needed by the following shift algorithms
1144 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1145 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1146 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1147 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1148 if (bitsInWord == 0)
1149 bitsInWord = APINT_BITS_PER_WORD;
1150
1151 // If we are shifting whole words, just move whole words
1152 if (wordShift == 0) {
1153 // Move the words containing significant bits
1154 for (unsigned i = 0; i <= breakWord; ++i)
1155 val[i] = pVal[i+offset]; // move whole word
1156
1157 // Adjust the top significant word for sign bit fill, if negative
1158 if (isNegative())
1159 if (bitsInWord < APINT_BITS_PER_WORD)
1160 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1161 } else {
1162 // Shift the low order words
1163 for (unsigned i = 0; i < breakWord; ++i) {
1164 // This combines the shifted corresponding word with the low bits from
1165 // the next word (shifted into this word's high bits).
1166 val[i] = (pVal[i+offset] >> wordShift) |
1167 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1168 }
1169
1170 // Shift the break word. In this case there are no bits from the next word
1171 // to include in this word.
1172 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1173
1174 // Deal with sign extenstion in the break word, and possibly the word before
1175 // it.
1176 if (isNegative()) {
1177 if (wordShift > bitsInWord) {
1178 if (breakWord > 0)
1179 val[breakWord-1] |=
1180 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1181 val[breakWord] |= ~0ULL;
1182 } else
1183 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1184 }
1185 }
1186
1187 // Remaining words are 0 or -1, just assign them.
1188 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1189 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1190 val[i] = fillValue;
1191 return APInt(val, BitWidth).clearUnusedBits();
1192 }
1193
1194 /// Logical right-shift this APInt by shiftAmt.
1195 /// @brief Logical right-shift function.
lshr(const APInt & shiftAmt) const1196 APInt APInt::lshr(const APInt &shiftAmt) const {
1197 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1198 }
1199
1200 /// Logical right-shift this APInt by shiftAmt.
1201 /// @brief Logical right-shift function.
lshr(unsigned shiftAmt) const1202 APInt APInt::lshr(unsigned shiftAmt) const {
1203 if (isSingleWord()) {
1204 if (shiftAmt == BitWidth)
1205 return APInt(BitWidth, 0);
1206 else
1207 return APInt(BitWidth, this->VAL >> shiftAmt);
1208 }
1209
1210 // If all the bits were shifted out, the result is 0. This avoids issues
1211 // with shifting by the size of the integer type, which produces undefined
1212 // results. We define these "undefined results" to always be 0.
1213 if (shiftAmt == BitWidth)
1214 return APInt(BitWidth, 0);
1215
1216 // If none of the bits are shifted out, the result is *this. This avoids
1217 // issues with shifting by the size of the integer type, which produces
1218 // undefined results in the code below. This is also an optimization.
1219 if (shiftAmt == 0)
1220 return *this;
1221
1222 // Create some space for the result.
1223 uint64_t * val = new uint64_t[getNumWords()];
1224
1225 // If we are shifting less than a word, compute the shift with a simple carry
1226 if (shiftAmt < APINT_BITS_PER_WORD) {
1227 uint64_t carry = 0;
1228 for (int i = getNumWords()-1; i >= 0; --i) {
1229 val[i] = (pVal[i] >> shiftAmt) | carry;
1230 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1231 }
1232 return APInt(val, BitWidth).clearUnusedBits();
1233 }
1234
1235 // Compute some values needed by the remaining shift algorithms
1236 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1237 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1238
1239 // If we are shifting whole words, just move whole words
1240 if (wordShift == 0) {
1241 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1242 val[i] = pVal[i+offset];
1243 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1244 val[i] = 0;
1245 return APInt(val,BitWidth).clearUnusedBits();
1246 }
1247
1248 // Shift the low order words
1249 unsigned breakWord = getNumWords() - offset -1;
1250 for (unsigned i = 0; i < breakWord; ++i)
1251 val[i] = (pVal[i+offset] >> wordShift) |
1252 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1253 // Shift the break word.
1254 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1255
1256 // Remaining words are 0
1257 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1258 val[i] = 0;
1259 return APInt(val, BitWidth).clearUnusedBits();
1260 }
1261
1262 /// Left-shift this APInt by shiftAmt.
1263 /// @brief Left-shift function.
shl(const APInt & shiftAmt) const1264 APInt APInt::shl(const APInt &shiftAmt) const {
1265 // It's undefined behavior in C to shift by BitWidth or greater.
1266 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1267 }
1268
shlSlowCase(unsigned shiftAmt) const1269 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1270 // If all the bits were shifted out, the result is 0. This avoids issues
1271 // with shifting by the size of the integer type, which produces undefined
1272 // results. We define these "undefined results" to always be 0.
1273 if (shiftAmt == BitWidth)
1274 return APInt(BitWidth, 0);
1275
1276 // If none of the bits are shifted out, the result is *this. This avoids a
1277 // lshr by the words size in the loop below which can produce incorrect
1278 // results. It also avoids the expensive computation below for a common case.
1279 if (shiftAmt == 0)
1280 return *this;
1281
1282 // Create some space for the result.
1283 uint64_t * val = new uint64_t[getNumWords()];
1284
1285 // If we are shifting less than a word, do it the easy way
1286 if (shiftAmt < APINT_BITS_PER_WORD) {
1287 uint64_t carry = 0;
1288 for (unsigned i = 0; i < getNumWords(); i++) {
1289 val[i] = pVal[i] << shiftAmt | carry;
1290 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1291 }
1292 return APInt(val, BitWidth).clearUnusedBits();
1293 }
1294
1295 // Compute some values needed by the remaining shift algorithms
1296 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1297 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1298
1299 // If we are shifting whole words, just move whole words
1300 if (wordShift == 0) {
1301 for (unsigned i = 0; i < offset; i++)
1302 val[i] = 0;
1303 for (unsigned i = offset; i < getNumWords(); i++)
1304 val[i] = pVal[i-offset];
1305 return APInt(val,BitWidth).clearUnusedBits();
1306 }
1307
1308 // Copy whole words from this to Result.
1309 unsigned i = getNumWords() - 1;
1310 for (; i > offset; --i)
1311 val[i] = pVal[i-offset] << wordShift |
1312 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1313 val[offset] = pVal[0] << wordShift;
1314 for (i = 0; i < offset; ++i)
1315 val[i] = 0;
1316 return APInt(val, BitWidth).clearUnusedBits();
1317 }
1318
rotl(const APInt & rotateAmt) const1319 APInt APInt::rotl(const APInt &rotateAmt) const {
1320 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1321 }
1322
rotl(unsigned rotateAmt) const1323 APInt APInt::rotl(unsigned rotateAmt) const {
1324 if (rotateAmt == 0)
1325 return *this;
1326 // Don't get too fancy, just use existing shift/or facilities
1327 APInt hi(*this);
1328 APInt lo(*this);
1329 hi.shl(rotateAmt);
1330 lo.lshr(BitWidth - rotateAmt);
1331 return hi | lo;
1332 }
1333
rotr(const APInt & rotateAmt) const1334 APInt APInt::rotr(const APInt &rotateAmt) const {
1335 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1336 }
1337
rotr(unsigned rotateAmt) const1338 APInt APInt::rotr(unsigned rotateAmt) const {
1339 if (rotateAmt == 0)
1340 return *this;
1341 // Don't get too fancy, just use existing shift/or facilities
1342 APInt hi(*this);
1343 APInt lo(*this);
1344 lo.lshr(rotateAmt);
1345 hi.shl(BitWidth - rotateAmt);
1346 return hi | lo;
1347 }
1348
1349 // Square Root - this method computes and returns the square root of "this".
1350 // Three mechanisms are used for computation. For small values (<= 5 bits),
1351 // a table lookup is done. This gets some performance for common cases. For
1352 // values using less than 52 bits, the value is converted to double and then
1353 // the libc sqrt function is called. The result is rounded and then converted
1354 // back to a uint64_t which is then used to construct the result. Finally,
1355 // the Babylonian method for computing square roots is used.
sqrt() const1356 APInt APInt::sqrt() const {
1357
1358 // Determine the magnitude of the value.
1359 unsigned magnitude = getActiveBits();
1360
1361 // Use a fast table for some small values. This also gets rid of some
1362 // rounding errors in libc sqrt for small values.
1363 if (magnitude <= 5) {
1364 static const uint8_t results[32] = {
1365 /* 0 */ 0,
1366 /* 1- 2 */ 1, 1,
1367 /* 3- 6 */ 2, 2, 2, 2,
1368 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1369 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1370 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1371 /* 31 */ 6
1372 };
1373 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1374 }
1375
1376 // If the magnitude of the value fits in less than 52 bits (the precision of
1377 // an IEEE double precision floating point value), then we can use the
1378 // libc sqrt function which will probably use a hardware sqrt computation.
1379 // This should be faster than the algorithm below.
1380 if (magnitude < 52) {
1381 #if HAVE_ROUND
1382 return APInt(BitWidth,
1383 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1384 #else
1385 return APInt(BitWidth,
1386 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1387 #endif
1388 }
1389
1390 // Okay, all the short cuts are exhausted. We must compute it. The following
1391 // is a classical Babylonian method for computing the square root. This code
1392 // was adapted to APINt from a wikipedia article on such computations.
1393 // See http://www.wikipedia.org/ and go to the page named
1394 // Calculate_an_integer_square_root.
1395 unsigned nbits = BitWidth, i = 4;
1396 APInt testy(BitWidth, 16);
1397 APInt x_old(BitWidth, 1);
1398 APInt x_new(BitWidth, 0);
1399 APInt two(BitWidth, 2);
1400
1401 // Select a good starting value using binary logarithms.
1402 for (;; i += 2, testy = testy.shl(2))
1403 if (i >= nbits || this->ule(testy)) {
1404 x_old = x_old.shl(i / 2);
1405 break;
1406 }
1407
1408 // Use the Babylonian method to arrive at the integer square root:
1409 for (;;) {
1410 x_new = (this->udiv(x_old) + x_old).udiv(two);
1411 if (x_old.ule(x_new))
1412 break;
1413 x_old = x_new;
1414 }
1415
1416 // Make sure we return the closest approximation
1417 // NOTE: The rounding calculation below is correct. It will produce an
1418 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1419 // determined to be a rounding issue with pari/gp as it begins to use a
1420 // floating point representation after 192 bits. There are no discrepancies
1421 // between this algorithm and pari/gp for bit widths < 192 bits.
1422 APInt square(x_old * x_old);
1423 APInt nextSquare((x_old + 1) * (x_old +1));
1424 if (this->ult(square))
1425 return x_old;
1426 else if (this->ule(nextSquare)) {
1427 APInt midpoint((nextSquare - square).udiv(two));
1428 APInt offset(*this - square);
1429 if (offset.ult(midpoint))
1430 return x_old;
1431 else
1432 return x_old + 1;
1433 } else
1434 llvm_unreachable("Error in APInt::sqrt computation");
1435 return x_old + 1;
1436 }
1437
1438 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1439 /// iterative extended Euclidean algorithm is used to solve for this value,
1440 /// however we simplify it to speed up calculating only the inverse, and take
1441 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1442 /// (potentially large) APInts around.
multiplicativeInverse(const APInt & modulo) const1443 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1444 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1445
1446 // Using the properties listed at the following web page (accessed 06/21/08):
1447 // http://www.numbertheory.org/php/euclid.html
1448 // (especially the properties numbered 3, 4 and 9) it can be proved that
1449 // BitWidth bits suffice for all the computations in the algorithm implemented
1450 // below. More precisely, this number of bits suffice if the multiplicative
1451 // inverse exists, but may not suffice for the general extended Euclidean
1452 // algorithm.
1453
1454 APInt r[2] = { modulo, *this };
1455 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1456 APInt q(BitWidth, 0);
1457
1458 unsigned i;
1459 for (i = 0; r[i^1] != 0; i ^= 1) {
1460 // An overview of the math without the confusing bit-flipping:
1461 // q = r[i-2] / r[i-1]
1462 // r[i] = r[i-2] % r[i-1]
1463 // t[i] = t[i-2] - t[i-1] * q
1464 udivrem(r[i], r[i^1], q, r[i]);
1465 t[i] -= t[i^1] * q;
1466 }
1467
1468 // If this APInt and the modulo are not coprime, there is no multiplicative
1469 // inverse, so return 0. We check this by looking at the next-to-last
1470 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1471 // algorithm.
1472 if (r[i] != 1)
1473 return APInt(BitWidth, 0);
1474
1475 // The next-to-last t is the multiplicative inverse. However, we are
1476 // interested in a positive inverse. Calcuate a positive one from a negative
1477 // one if necessary. A simple addition of the modulo suffices because
1478 // abs(t[i]) is known to be less than *this/2 (see the link above).
1479 return t[i].isNegative() ? t[i] + modulo : t[i];
1480 }
1481
1482 /// Calculate the magic numbers required to implement a signed integer division
1483 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1484 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1485 /// Warren, Jr., chapter 10.
magic() const1486 APInt::ms APInt::magic() const {
1487 const APInt& d = *this;
1488 unsigned p;
1489 APInt ad, anc, delta, q1, r1, q2, r2, t;
1490 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1491 struct ms mag;
1492
1493 ad = d.abs();
1494 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1495 anc = t - 1 - t.urem(ad); // absolute value of nc
1496 p = d.getBitWidth() - 1; // initialize p
1497 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1498 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1499 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1500 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1501 do {
1502 p = p + 1;
1503 q1 = q1<<1; // update q1 = 2p/abs(nc)
1504 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1505 if (r1.uge(anc)) { // must be unsigned comparison
1506 q1 = q1 + 1;
1507 r1 = r1 - anc;
1508 }
1509 q2 = q2<<1; // update q2 = 2p/abs(d)
1510 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1511 if (r2.uge(ad)) { // must be unsigned comparison
1512 q2 = q2 + 1;
1513 r2 = r2 - ad;
1514 }
1515 delta = ad - r2;
1516 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1517
1518 mag.m = q2 + 1;
1519 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1520 mag.s = p - d.getBitWidth(); // resulting shift
1521 return mag;
1522 }
1523
1524 /// Calculate the magic numbers required to implement an unsigned integer
1525 /// division by a constant as a sequence of multiplies, adds and shifts.
1526 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1527 /// S. Warren, Jr., chapter 10.
1528 /// LeadingZeros can be used to simplify the calculation if the upper bits
1529 /// of the divided value are known zero.
magicu(unsigned LeadingZeros) const1530 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1531 const APInt& d = *this;
1532 unsigned p;
1533 APInt nc, delta, q1, r1, q2, r2;
1534 struct mu magu;
1535 magu.a = 0; // initialize "add" indicator
1536 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1537 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1538 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1539
1540 nc = allOnes - (-d).urem(d);
1541 p = d.getBitWidth() - 1; // initialize p
1542 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1543 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1544 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1545 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1546 do {
1547 p = p + 1;
1548 if (r1.uge(nc - r1)) {
1549 q1 = q1 + q1 + 1; // update q1
1550 r1 = r1 + r1 - nc; // update r1
1551 }
1552 else {
1553 q1 = q1+q1; // update q1
1554 r1 = r1+r1; // update r1
1555 }
1556 if ((r2 + 1).uge(d - r2)) {
1557 if (q2.uge(signedMax)) magu.a = 1;
1558 q2 = q2+q2 + 1; // update q2
1559 r2 = r2+r2 + 1 - d; // update r2
1560 }
1561 else {
1562 if (q2.uge(signedMin)) magu.a = 1;
1563 q2 = q2+q2; // update q2
1564 r2 = r2+r2 + 1; // update r2
1565 }
1566 delta = d - 1 - r2;
1567 } while (p < d.getBitWidth()*2 &&
1568 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1569 magu.m = q2 + 1; // resulting magic number
1570 magu.s = p - d.getBitWidth(); // resulting shift
1571 return magu;
1572 }
1573
1574 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1575 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1576 /// variables here have the same names as in the algorithm. Comments explain
1577 /// the algorithm and any deviation from it.
KnuthDiv(unsigned * u,unsigned * v,unsigned * q,unsigned * r,unsigned m,unsigned n)1578 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1579 unsigned m, unsigned n) {
1580 assert(u && "Must provide dividend");
1581 assert(v && "Must provide divisor");
1582 assert(q && "Must provide quotient");
1583 assert(u != v && u != q && v != q && "Must us different memory");
1584 assert(n>1 && "n must be > 1");
1585
1586 // Knuth uses the value b as the base of the number system. In our case b
1587 // is 2^31 so we just set it to -1u.
1588 uint64_t b = uint64_t(1) << 32;
1589
1590 #if 0
1591 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1592 DEBUG(dbgs() << "KnuthDiv: original:");
1593 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1594 DEBUG(dbgs() << " by");
1595 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1596 DEBUG(dbgs() << '\n');
1597 #endif
1598 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1599 // u and v by d. Note that we have taken Knuth's advice here to use a power
1600 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1601 // 2 allows us to shift instead of multiply and it is easy to determine the
1602 // shift amount from the leading zeros. We are basically normalizing the u
1603 // and v so that its high bits are shifted to the top of v's range without
1604 // overflow. Note that this can require an extra word in u so that u must
1605 // be of length m+n+1.
1606 unsigned shift = CountLeadingZeros_32(v[n-1]);
1607 unsigned v_carry = 0;
1608 unsigned u_carry = 0;
1609 if (shift) {
1610 for (unsigned i = 0; i < m+n; ++i) {
1611 unsigned u_tmp = u[i] >> (32 - shift);
1612 u[i] = (u[i] << shift) | u_carry;
1613 u_carry = u_tmp;
1614 }
1615 for (unsigned i = 0; i < n; ++i) {
1616 unsigned v_tmp = v[i] >> (32 - shift);
1617 v[i] = (v[i] << shift) | v_carry;
1618 v_carry = v_tmp;
1619 }
1620 }
1621 u[m+n] = u_carry;
1622 #if 0
1623 DEBUG(dbgs() << "KnuthDiv: normal:");
1624 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1625 DEBUG(dbgs() << " by");
1626 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1627 DEBUG(dbgs() << '\n');
1628 #endif
1629
1630 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1631 int j = m;
1632 do {
1633 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1634 // D3. [Calculate q'.].
1635 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1636 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1637 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1638 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1639 // on v[n-2] determines at high speed most of the cases in which the trial
1640 // value qp is one too large, and it eliminates all cases where qp is two
1641 // too large.
1642 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1643 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1644 uint64_t qp = dividend / v[n-1];
1645 uint64_t rp = dividend % v[n-1];
1646 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1647 qp--;
1648 rp += v[n-1];
1649 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1650 qp--;
1651 }
1652 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1653
1654 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1655 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1656 // consists of a simple multiplication by a one-place number, combined with
1657 // a subtraction.
1658 bool isNeg = false;
1659 for (unsigned i = 0; i < n; ++i) {
1660 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1661 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1662 bool borrow = subtrahend > u_tmp;
1663 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1664 << ", subtrahend == " << subtrahend
1665 << ", borrow = " << borrow << '\n');
1666
1667 uint64_t result = u_tmp - subtrahend;
1668 unsigned k = j + i;
1669 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1670 u[k++] = (unsigned)(result >> 32); // subtract high word
1671 while (borrow && k <= m+n) { // deal with borrow to the left
1672 borrow = u[k] == 0;
1673 u[k]--;
1674 k++;
1675 }
1676 isNeg |= borrow;
1677 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1678 u[j+i+1] << '\n');
1679 }
1680 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1681 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1682 DEBUG(dbgs() << '\n');
1683 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1684 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1685 // true value plus b**(n+1), namely as the b's complement of
1686 // the true value, and a "borrow" to the left should be remembered.
1687 //
1688 if (isNeg) {
1689 bool carry = true; // true because b's complement is "complement + 1"
1690 for (unsigned i = 0; i <= m+n; ++i) {
1691 u[i] = ~u[i] + carry; // b's complement
1692 carry = carry && u[i] == 0;
1693 }
1694 }
1695 DEBUG(dbgs() << "KnuthDiv: after complement:");
1696 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1697 DEBUG(dbgs() << '\n');
1698
1699 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1700 // negative, go to step D6; otherwise go on to step D7.
1701 q[j] = (unsigned)qp;
1702 if (isNeg) {
1703 // D6. [Add back]. The probability that this step is necessary is very
1704 // small, on the order of only 2/b. Make sure that test data accounts for
1705 // this possibility. Decrease q[j] by 1
1706 q[j]--;
1707 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1708 // A carry will occur to the left of u[j+n], and it should be ignored
1709 // since it cancels with the borrow that occurred in D4.
1710 bool carry = false;
1711 for (unsigned i = 0; i < n; i++) {
1712 unsigned limit = std::min(u[j+i],v[i]);
1713 u[j+i] += v[i] + carry;
1714 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1715 }
1716 u[j+n] += carry;
1717 }
1718 DEBUG(dbgs() << "KnuthDiv: after correction:");
1719 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1720 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1721
1722 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1723 } while (--j >= 0);
1724
1725 DEBUG(dbgs() << "KnuthDiv: quotient:");
1726 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1727 DEBUG(dbgs() << '\n');
1728
1729 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1730 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1731 // compute the remainder (urem uses this).
1732 if (r) {
1733 // The value d is expressed by the "shift" value above since we avoided
1734 // multiplication by d by using a shift left. So, all we have to do is
1735 // shift right here. In order to mak
1736 if (shift) {
1737 unsigned carry = 0;
1738 DEBUG(dbgs() << "KnuthDiv: remainder:");
1739 for (int i = n-1; i >= 0; i--) {
1740 r[i] = (u[i] >> shift) | carry;
1741 carry = u[i] << (32 - shift);
1742 DEBUG(dbgs() << " " << r[i]);
1743 }
1744 } else {
1745 for (int i = n-1; i >= 0; i--) {
1746 r[i] = u[i];
1747 DEBUG(dbgs() << " " << r[i]);
1748 }
1749 }
1750 DEBUG(dbgs() << '\n');
1751 }
1752 #if 0
1753 DEBUG(dbgs() << '\n');
1754 #endif
1755 }
1756
divide(const APInt LHS,unsigned lhsWords,const APInt & RHS,unsigned rhsWords,APInt * Quotient,APInt * Remainder)1757 void APInt::divide(const APInt LHS, unsigned lhsWords,
1758 const APInt &RHS, unsigned rhsWords,
1759 APInt *Quotient, APInt *Remainder)
1760 {
1761 assert(lhsWords >= rhsWords && "Fractional result");
1762
1763 // First, compose the values into an array of 32-bit words instead of
1764 // 64-bit words. This is a necessity of both the "short division" algorithm
1765 // and the Knuth "classical algorithm" which requires there to be native
1766 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1767 // can't use 64-bit operands here because we don't have native results of
1768 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1769 // work on large-endian machines.
1770 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1771 unsigned n = rhsWords * 2;
1772 unsigned m = (lhsWords * 2) - n;
1773
1774 // Allocate space for the temporary values we need either on the stack, if
1775 // it will fit, or on the heap if it won't.
1776 unsigned SPACE[128];
1777 unsigned *U = 0;
1778 unsigned *V = 0;
1779 unsigned *Q = 0;
1780 unsigned *R = 0;
1781 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1782 U = &SPACE[0];
1783 V = &SPACE[m+n+1];
1784 Q = &SPACE[(m+n+1) + n];
1785 if (Remainder)
1786 R = &SPACE[(m+n+1) + n + (m+n)];
1787 } else {
1788 U = new unsigned[m + n + 1];
1789 V = new unsigned[n];
1790 Q = new unsigned[m+n];
1791 if (Remainder)
1792 R = new unsigned[n];
1793 }
1794
1795 // Initialize the dividend
1796 memset(U, 0, (m+n+1)*sizeof(unsigned));
1797 for (unsigned i = 0; i < lhsWords; ++i) {
1798 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1799 U[i * 2] = (unsigned)(tmp & mask);
1800 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1801 }
1802 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1803
1804 // Initialize the divisor
1805 memset(V, 0, (n)*sizeof(unsigned));
1806 for (unsigned i = 0; i < rhsWords; ++i) {
1807 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1808 V[i * 2] = (unsigned)(tmp & mask);
1809 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1810 }
1811
1812 // initialize the quotient and remainder
1813 memset(Q, 0, (m+n) * sizeof(unsigned));
1814 if (Remainder)
1815 memset(R, 0, n * sizeof(unsigned));
1816
1817 // Now, adjust m and n for the Knuth division. n is the number of words in
1818 // the divisor. m is the number of words by which the dividend exceeds the
1819 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1820 // contain any zero words or the Knuth algorithm fails.
1821 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1822 n--;
1823 m++;
1824 }
1825 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1826 m--;
1827
1828 // If we're left with only a single word for the divisor, Knuth doesn't work
1829 // so we implement the short division algorithm here. This is much simpler
1830 // and faster because we are certain that we can divide a 64-bit quantity
1831 // by a 32-bit quantity at hardware speed and short division is simply a
1832 // series of such operations. This is just like doing short division but we
1833 // are using base 2^32 instead of base 10.
1834 assert(n != 0 && "Divide by zero?");
1835 if (n == 1) {
1836 unsigned divisor = V[0];
1837 unsigned remainder = 0;
1838 for (int i = m+n-1; i >= 0; i--) {
1839 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1840 if (partial_dividend == 0) {
1841 Q[i] = 0;
1842 remainder = 0;
1843 } else if (partial_dividend < divisor) {
1844 Q[i] = 0;
1845 remainder = (unsigned)partial_dividend;
1846 } else if (partial_dividend == divisor) {
1847 Q[i] = 1;
1848 remainder = 0;
1849 } else {
1850 Q[i] = (unsigned)(partial_dividend / divisor);
1851 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1852 }
1853 }
1854 if (R)
1855 R[0] = remainder;
1856 } else {
1857 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1858 // case n > 1.
1859 KnuthDiv(U, V, Q, R, m, n);
1860 }
1861
1862 // If the caller wants the quotient
1863 if (Quotient) {
1864 // Set up the Quotient value's memory.
1865 if (Quotient->BitWidth != LHS.BitWidth) {
1866 if (Quotient->isSingleWord())
1867 Quotient->VAL = 0;
1868 else
1869 delete [] Quotient->pVal;
1870 Quotient->BitWidth = LHS.BitWidth;
1871 if (!Quotient->isSingleWord())
1872 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1873 } else
1874 Quotient->clearAllBits();
1875
1876 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1877 // order words.
1878 if (lhsWords == 1) {
1879 uint64_t tmp =
1880 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1881 if (Quotient->isSingleWord())
1882 Quotient->VAL = tmp;
1883 else
1884 Quotient->pVal[0] = tmp;
1885 } else {
1886 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1887 for (unsigned i = 0; i < lhsWords; ++i)
1888 Quotient->pVal[i] =
1889 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1890 }
1891 }
1892
1893 // If the caller wants the remainder
1894 if (Remainder) {
1895 // Set up the Remainder value's memory.
1896 if (Remainder->BitWidth != RHS.BitWidth) {
1897 if (Remainder->isSingleWord())
1898 Remainder->VAL = 0;
1899 else
1900 delete [] Remainder->pVal;
1901 Remainder->BitWidth = RHS.BitWidth;
1902 if (!Remainder->isSingleWord())
1903 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1904 } else
1905 Remainder->clearAllBits();
1906
1907 // The remainder is in R. Reconstitute the remainder into Remainder's low
1908 // order words.
1909 if (rhsWords == 1) {
1910 uint64_t tmp =
1911 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1912 if (Remainder->isSingleWord())
1913 Remainder->VAL = tmp;
1914 else
1915 Remainder->pVal[0] = tmp;
1916 } else {
1917 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1918 for (unsigned i = 0; i < rhsWords; ++i)
1919 Remainder->pVal[i] =
1920 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1921 }
1922 }
1923
1924 // Clean up the memory we allocated.
1925 if (U != &SPACE[0]) {
1926 delete [] U;
1927 delete [] V;
1928 delete [] Q;
1929 delete [] R;
1930 }
1931 }
1932
udiv(const APInt & RHS) const1933 APInt APInt::udiv(const APInt& RHS) const {
1934 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1935
1936 // First, deal with the easy case
1937 if (isSingleWord()) {
1938 assert(RHS.VAL != 0 && "Divide by zero?");
1939 return APInt(BitWidth, VAL / RHS.VAL);
1940 }
1941
1942 // Get some facts about the LHS and RHS number of bits and words
1943 unsigned rhsBits = RHS.getActiveBits();
1944 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1945 assert(rhsWords && "Divided by zero???");
1946 unsigned lhsBits = this->getActiveBits();
1947 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1948
1949 // Deal with some degenerate cases
1950 if (!lhsWords)
1951 // 0 / X ===> 0
1952 return APInt(BitWidth, 0);
1953 else if (lhsWords < rhsWords || this->ult(RHS)) {
1954 // X / Y ===> 0, iff X < Y
1955 return APInt(BitWidth, 0);
1956 } else if (*this == RHS) {
1957 // X / X ===> 1
1958 return APInt(BitWidth, 1);
1959 } else if (lhsWords == 1 && rhsWords == 1) {
1960 // All high words are zero, just use native divide
1961 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1962 }
1963
1964 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1965 APInt Quotient(1,0); // to hold result.
1966 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1967 return Quotient;
1968 }
1969
urem(const APInt & RHS) const1970 APInt APInt::urem(const APInt& RHS) const {
1971 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1972 if (isSingleWord()) {
1973 assert(RHS.VAL != 0 && "Remainder by zero?");
1974 return APInt(BitWidth, VAL % RHS.VAL);
1975 }
1976
1977 // Get some facts about the LHS
1978 unsigned lhsBits = getActiveBits();
1979 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1980
1981 // Get some facts about the RHS
1982 unsigned rhsBits = RHS.getActiveBits();
1983 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1984 assert(rhsWords && "Performing remainder operation by zero ???");
1985
1986 // Check the degenerate cases
1987 if (lhsWords == 0) {
1988 // 0 % Y ===> 0
1989 return APInt(BitWidth, 0);
1990 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1991 // X % Y ===> X, iff X < Y
1992 return *this;
1993 } else if (*this == RHS) {
1994 // X % X == 0;
1995 return APInt(BitWidth, 0);
1996 } else if (lhsWords == 1) {
1997 // All high words are zero, just use native remainder
1998 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1999 }
2000
2001 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
2002 APInt Remainder(1,0);
2003 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
2004 return Remainder;
2005 }
2006
udivrem(const APInt & LHS,const APInt & RHS,APInt & Quotient,APInt & Remainder)2007 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
2008 APInt &Quotient, APInt &Remainder) {
2009 // Get some size facts about the dividend and divisor
2010 unsigned lhsBits = LHS.getActiveBits();
2011 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
2012 unsigned rhsBits = RHS.getActiveBits();
2013 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
2014
2015 // Check the degenerate cases
2016 if (lhsWords == 0) {
2017 Quotient = 0; // 0 / Y ===> 0
2018 Remainder = 0; // 0 % Y ===> 0
2019 return;
2020 }
2021
2022 if (lhsWords < rhsWords || LHS.ult(RHS)) {
2023 Remainder = LHS; // X % Y ===> X, iff X < Y
2024 Quotient = 0; // X / Y ===> 0, iff X < Y
2025 return;
2026 }
2027
2028 if (LHS == RHS) {
2029 Quotient = 1; // X / X ===> 1
2030 Remainder = 0; // X % X ===> 0;
2031 return;
2032 }
2033
2034 if (lhsWords == 1 && rhsWords == 1) {
2035 // There is only one word to consider so use the native versions.
2036 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
2037 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
2038 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
2039 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
2040 return;
2041 }
2042
2043 // Okay, lets do it the long way
2044 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
2045 }
2046
sadd_ov(const APInt & RHS,bool & Overflow) const2047 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
2048 APInt Res = *this+RHS;
2049 Overflow = isNonNegative() == RHS.isNonNegative() &&
2050 Res.isNonNegative() != isNonNegative();
2051 return Res;
2052 }
2053
uadd_ov(const APInt & RHS,bool & Overflow) const2054 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2055 APInt Res = *this+RHS;
2056 Overflow = Res.ult(RHS);
2057 return Res;
2058 }
2059
ssub_ov(const APInt & RHS,bool & Overflow) const2060 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2061 APInt Res = *this - RHS;
2062 Overflow = isNonNegative() != RHS.isNonNegative() &&
2063 Res.isNonNegative() != isNonNegative();
2064 return Res;
2065 }
2066
usub_ov(const APInt & RHS,bool & Overflow) const2067 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2068 APInt Res = *this-RHS;
2069 Overflow = Res.ugt(*this);
2070 return Res;
2071 }
2072
sdiv_ov(const APInt & RHS,bool & Overflow) const2073 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2074 // MININT/-1 --> overflow.
2075 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2076 return sdiv(RHS);
2077 }
2078
smul_ov(const APInt & RHS,bool & Overflow) const2079 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2080 APInt Res = *this * RHS;
2081
2082 if (*this != 0 && RHS != 0)
2083 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2084 else
2085 Overflow = false;
2086 return Res;
2087 }
2088
umul_ov(const APInt & RHS,bool & Overflow) const2089 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2090 APInt Res = *this * RHS;
2091
2092 if (*this != 0 && RHS != 0)
2093 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2094 else
2095 Overflow = false;
2096 return Res;
2097 }
2098
sshl_ov(unsigned ShAmt,bool & Overflow) const2099 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2100 Overflow = ShAmt >= getBitWidth();
2101 if (Overflow)
2102 ShAmt = getBitWidth()-1;
2103
2104 if (isNonNegative()) // Don't allow sign change.
2105 Overflow = ShAmt >= countLeadingZeros();
2106 else
2107 Overflow = ShAmt >= countLeadingOnes();
2108
2109 return *this << ShAmt;
2110 }
2111
2112
2113
2114
fromString(unsigned numbits,StringRef str,uint8_t radix)2115 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2116 // Check our assumptions here
2117 assert(!str.empty() && "Invalid string length");
2118 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2119 "Radix should be 2, 8, 10, or 16!");
2120
2121 StringRef::iterator p = str.begin();
2122 size_t slen = str.size();
2123 bool isNeg = *p == '-';
2124 if (*p == '-' || *p == '+') {
2125 p++;
2126 slen--;
2127 assert(slen && "String is only a sign, needs a value.");
2128 }
2129 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2130 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2131 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2132 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2133 "Insufficient bit width");
2134
2135 // Allocate memory
2136 if (!isSingleWord())
2137 pVal = getClearedMemory(getNumWords());
2138
2139 // Figure out if we can shift instead of multiply
2140 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2141
2142 // Set up an APInt for the digit to add outside the loop so we don't
2143 // constantly construct/destruct it.
2144 APInt apdigit(getBitWidth(), 0);
2145 APInt apradix(getBitWidth(), radix);
2146
2147 // Enter digit traversal loop
2148 for (StringRef::iterator e = str.end(); p != e; ++p) {
2149 unsigned digit = getDigit(*p, radix);
2150 assert(digit < radix && "Invalid character in digit string");
2151
2152 // Shift or multiply the value by the radix
2153 if (slen > 1) {
2154 if (shift)
2155 *this <<= shift;
2156 else
2157 *this *= apradix;
2158 }
2159
2160 // Add in the digit we just interpreted
2161 if (apdigit.isSingleWord())
2162 apdigit.VAL = digit;
2163 else
2164 apdigit.pVal[0] = digit;
2165 *this += apdigit;
2166 }
2167 // If its negative, put it in two's complement form
2168 if (isNeg) {
2169 (*this)--;
2170 this->flipAllBits();
2171 }
2172 }
2173
toString(SmallVectorImpl<char> & Str,unsigned Radix,bool Signed,bool formatAsCLiteral) const2174 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2175 bool Signed, bool formatAsCLiteral) const {
2176 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
2177 "Radix should be 2, 8, 10, or 16!");
2178
2179 const char *Prefix = "";
2180 if (formatAsCLiteral) {
2181 switch (Radix) {
2182 case 2:
2183 // Binary literals are a non-standard extension added in gcc 4.3:
2184 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2185 Prefix = "0b";
2186 break;
2187 case 8:
2188 Prefix = "0";
2189 break;
2190 case 16:
2191 Prefix = "0x";
2192 break;
2193 }
2194 }
2195
2196 // First, check for a zero value and just short circuit the logic below.
2197 if (*this == 0) {
2198 while (*Prefix) {
2199 Str.push_back(*Prefix);
2200 ++Prefix;
2201 };
2202 Str.push_back('0');
2203 return;
2204 }
2205
2206 static const char Digits[] = "0123456789ABCDEF";
2207
2208 if (isSingleWord()) {
2209 char Buffer[65];
2210 char *BufPtr = Buffer+65;
2211
2212 uint64_t N;
2213 if (!Signed) {
2214 N = getZExtValue();
2215 } else {
2216 int64_t I = getSExtValue();
2217 if (I >= 0) {
2218 N = I;
2219 } else {
2220 Str.push_back('-');
2221 N = -(uint64_t)I;
2222 }
2223 }
2224
2225 while (*Prefix) {
2226 Str.push_back(*Prefix);
2227 ++Prefix;
2228 };
2229
2230 while (N) {
2231 *--BufPtr = Digits[N % Radix];
2232 N /= Radix;
2233 }
2234 Str.append(BufPtr, Buffer+65);
2235 return;
2236 }
2237
2238 APInt Tmp(*this);
2239
2240 if (Signed && isNegative()) {
2241 // They want to print the signed version and it is a negative value
2242 // Flip the bits and add one to turn it into the equivalent positive
2243 // value and put a '-' in the result.
2244 Tmp.flipAllBits();
2245 Tmp++;
2246 Str.push_back('-');
2247 }
2248
2249 while (*Prefix) {
2250 Str.push_back(*Prefix);
2251 ++Prefix;
2252 };
2253
2254 // We insert the digits backward, then reverse them to get the right order.
2255 unsigned StartDig = Str.size();
2256
2257 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2258 // because the number of bits per digit (1, 3 and 4 respectively) divides
2259 // equaly. We just shift until the value is zero.
2260 if (Radix != 10) {
2261 // Just shift tmp right for each digit width until it becomes zero
2262 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2263 unsigned MaskAmt = Radix - 1;
2264
2265 while (Tmp != 0) {
2266 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2267 Str.push_back(Digits[Digit]);
2268 Tmp = Tmp.lshr(ShiftAmt);
2269 }
2270 } else {
2271 APInt divisor(4, 10);
2272 while (Tmp != 0) {
2273 APInt APdigit(1, 0);
2274 APInt tmp2(Tmp.getBitWidth(), 0);
2275 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2276 &APdigit);
2277 unsigned Digit = (unsigned)APdigit.getZExtValue();
2278 assert(Digit < Radix && "divide failed");
2279 Str.push_back(Digits[Digit]);
2280 Tmp = tmp2;
2281 }
2282 }
2283
2284 // Reverse the digits before returning.
2285 std::reverse(Str.begin()+StartDig, Str.end());
2286 }
2287
2288 /// toString - This returns the APInt as a std::string. Note that this is an
2289 /// inefficient method. It is better to pass in a SmallVector/SmallString
2290 /// to the methods above.
toString(unsigned Radix=10,bool Signed=true) const2291 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2292 SmallString<40> S;
2293 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2294 return S.str();
2295 }
2296
2297
dump() const2298 void APInt::dump() const {
2299 SmallString<40> S, U;
2300 this->toStringUnsigned(U);
2301 this->toStringSigned(S);
2302 dbgs() << "APInt(" << BitWidth << "b, "
2303 << U.str() << "u " << S.str() << "s)";
2304 }
2305
print(raw_ostream & OS,bool isSigned) const2306 void APInt::print(raw_ostream &OS, bool isSigned) const {
2307 SmallString<40> S;
2308 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2309 OS << S.str();
2310 }
2311
2312 // This implements a variety of operations on a representation of
2313 // arbitrary precision, two's-complement, bignum integer values.
2314
2315 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2316 // and unrestricting assumption.
2317 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2318 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2319
2320 /* Some handy functions local to this file. */
2321 namespace {
2322
2323 /* Returns the integer part with the least significant BITS set.
2324 BITS cannot be zero. */
2325 static inline integerPart
lowBitMask(unsigned int bits)2326 lowBitMask(unsigned int bits)
2327 {
2328 assert(bits != 0 && bits <= integerPartWidth);
2329
2330 return ~(integerPart) 0 >> (integerPartWidth - bits);
2331 }
2332
2333 /* Returns the value of the lower half of PART. */
2334 static inline integerPart
lowHalf(integerPart part)2335 lowHalf(integerPart part)
2336 {
2337 return part & lowBitMask(integerPartWidth / 2);
2338 }
2339
2340 /* Returns the value of the upper half of PART. */
2341 static inline integerPart
highHalf(integerPart part)2342 highHalf(integerPart part)
2343 {
2344 return part >> (integerPartWidth / 2);
2345 }
2346
2347 /* Returns the bit number of the most significant set bit of a part.
2348 If the input number has no bits set -1U is returned. */
2349 static unsigned int
partMSB(integerPart value)2350 partMSB(integerPart value)
2351 {
2352 unsigned int n, msb;
2353
2354 if (value == 0)
2355 return -1U;
2356
2357 n = integerPartWidth / 2;
2358
2359 msb = 0;
2360 do {
2361 if (value >> n) {
2362 value >>= n;
2363 msb += n;
2364 }
2365
2366 n >>= 1;
2367 } while (n);
2368
2369 return msb;
2370 }
2371
2372 /* Returns the bit number of the least significant set bit of a
2373 part. If the input number has no bits set -1U is returned. */
2374 static unsigned int
partLSB(integerPart value)2375 partLSB(integerPart value)
2376 {
2377 unsigned int n, lsb;
2378
2379 if (value == 0)
2380 return -1U;
2381
2382 lsb = integerPartWidth - 1;
2383 n = integerPartWidth / 2;
2384
2385 do {
2386 if (value << n) {
2387 value <<= n;
2388 lsb -= n;
2389 }
2390
2391 n >>= 1;
2392 } while (n);
2393
2394 return lsb;
2395 }
2396 }
2397
2398 /* Sets the least significant part of a bignum to the input value, and
2399 zeroes out higher parts. */
2400 void
tcSet(integerPart * dst,integerPart part,unsigned int parts)2401 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2402 {
2403 unsigned int i;
2404
2405 assert(parts > 0);
2406
2407 dst[0] = part;
2408 for (i = 1; i < parts; i++)
2409 dst[i] = 0;
2410 }
2411
2412 /* Assign one bignum to another. */
2413 void
tcAssign(integerPart * dst,const integerPart * src,unsigned int parts)2414 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2415 {
2416 unsigned int i;
2417
2418 for (i = 0; i < parts; i++)
2419 dst[i] = src[i];
2420 }
2421
2422 /* Returns true if a bignum is zero, false otherwise. */
2423 bool
tcIsZero(const integerPart * src,unsigned int parts)2424 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2425 {
2426 unsigned int i;
2427
2428 for (i = 0; i < parts; i++)
2429 if (src[i])
2430 return false;
2431
2432 return true;
2433 }
2434
2435 /* Extract the given bit of a bignum; returns 0 or 1. */
2436 int
tcExtractBit(const integerPart * parts,unsigned int bit)2437 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2438 {
2439 return (parts[bit / integerPartWidth] &
2440 ((integerPart) 1 << bit % integerPartWidth)) != 0;
2441 }
2442
2443 /* Set the given bit of a bignum. */
2444 void
tcSetBit(integerPart * parts,unsigned int bit)2445 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2446 {
2447 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2448 }
2449
2450 /* Clears the given bit of a bignum. */
2451 void
tcClearBit(integerPart * parts,unsigned int bit)2452 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2453 {
2454 parts[bit / integerPartWidth] &=
2455 ~((integerPart) 1 << (bit % integerPartWidth));
2456 }
2457
2458 /* Returns the bit number of the least significant set bit of a
2459 number. If the input number has no bits set -1U is returned. */
2460 unsigned int
tcLSB(const integerPart * parts,unsigned int n)2461 APInt::tcLSB(const integerPart *parts, unsigned int n)
2462 {
2463 unsigned int i, lsb;
2464
2465 for (i = 0; i < n; i++) {
2466 if (parts[i] != 0) {
2467 lsb = partLSB(parts[i]);
2468
2469 return lsb + i * integerPartWidth;
2470 }
2471 }
2472
2473 return -1U;
2474 }
2475
2476 /* Returns the bit number of the most significant set bit of a number.
2477 If the input number has no bits set -1U is returned. */
2478 unsigned int
tcMSB(const integerPart * parts,unsigned int n)2479 APInt::tcMSB(const integerPart *parts, unsigned int n)
2480 {
2481 unsigned int msb;
2482
2483 do {
2484 --n;
2485
2486 if (parts[n] != 0) {
2487 msb = partMSB(parts[n]);
2488
2489 return msb + n * integerPartWidth;
2490 }
2491 } while (n);
2492
2493 return -1U;
2494 }
2495
2496 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2497 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2498 the least significant bit of DST. All high bits above srcBITS in
2499 DST are zero-filled. */
2500 void
tcExtract(integerPart * dst,unsigned int dstCount,const integerPart * src,unsigned int srcBits,unsigned int srcLSB)2501 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2502 unsigned int srcBits, unsigned int srcLSB)
2503 {
2504 unsigned int firstSrcPart, dstParts, shift, n;
2505
2506 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2507 assert(dstParts <= dstCount);
2508
2509 firstSrcPart = srcLSB / integerPartWidth;
2510 tcAssign (dst, src + firstSrcPart, dstParts);
2511
2512 shift = srcLSB % integerPartWidth;
2513 tcShiftRight (dst, dstParts, shift);
2514
2515 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2516 in DST. If this is less that srcBits, append the rest, else
2517 clear the high bits. */
2518 n = dstParts * integerPartWidth - shift;
2519 if (n < srcBits) {
2520 integerPart mask = lowBitMask (srcBits - n);
2521 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2522 << n % integerPartWidth);
2523 } else if (n > srcBits) {
2524 if (srcBits % integerPartWidth)
2525 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2526 }
2527
2528 /* Clear high parts. */
2529 while (dstParts < dstCount)
2530 dst[dstParts++] = 0;
2531 }
2532
2533 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2534 integerPart
tcAdd(integerPart * dst,const integerPart * rhs,integerPart c,unsigned int parts)2535 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2536 integerPart c, unsigned int parts)
2537 {
2538 unsigned int i;
2539
2540 assert(c <= 1);
2541
2542 for (i = 0; i < parts; i++) {
2543 integerPart l;
2544
2545 l = dst[i];
2546 if (c) {
2547 dst[i] += rhs[i] + 1;
2548 c = (dst[i] <= l);
2549 } else {
2550 dst[i] += rhs[i];
2551 c = (dst[i] < l);
2552 }
2553 }
2554
2555 return c;
2556 }
2557
2558 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2559 integerPart
tcSubtract(integerPart * dst,const integerPart * rhs,integerPart c,unsigned int parts)2560 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2561 integerPart c, unsigned int parts)
2562 {
2563 unsigned int i;
2564
2565 assert(c <= 1);
2566
2567 for (i = 0; i < parts; i++) {
2568 integerPart l;
2569
2570 l = dst[i];
2571 if (c) {
2572 dst[i] -= rhs[i] + 1;
2573 c = (dst[i] >= l);
2574 } else {
2575 dst[i] -= rhs[i];
2576 c = (dst[i] > l);
2577 }
2578 }
2579
2580 return c;
2581 }
2582
2583 /* Negate a bignum in-place. */
2584 void
tcNegate(integerPart * dst,unsigned int parts)2585 APInt::tcNegate(integerPart *dst, unsigned int parts)
2586 {
2587 tcComplement(dst, parts);
2588 tcIncrement(dst, parts);
2589 }
2590
2591 /* DST += SRC * MULTIPLIER + CARRY if add is true
2592 DST = SRC * MULTIPLIER + CARRY if add is false
2593
2594 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2595 they must start at the same point, i.e. DST == SRC.
2596
2597 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2598 returned. Otherwise DST is filled with the least significant
2599 DSTPARTS parts of the result, and if all of the omitted higher
2600 parts were zero return zero, otherwise overflow occurred and
2601 return one. */
2602 int
tcMultiplyPart(integerPart * dst,const integerPart * src,integerPart multiplier,integerPart carry,unsigned int srcParts,unsigned int dstParts,bool add)2603 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2604 integerPart multiplier, integerPart carry,
2605 unsigned int srcParts, unsigned int dstParts,
2606 bool add)
2607 {
2608 unsigned int i, n;
2609
2610 /* Otherwise our writes of DST kill our later reads of SRC. */
2611 assert(dst <= src || dst >= src + srcParts);
2612 assert(dstParts <= srcParts + 1);
2613
2614 /* N loops; minimum of dstParts and srcParts. */
2615 n = dstParts < srcParts ? dstParts: srcParts;
2616
2617 for (i = 0; i < n; i++) {
2618 integerPart low, mid, high, srcPart;
2619
2620 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2621
2622 This cannot overflow, because
2623
2624 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2625
2626 which is less than n^2. */
2627
2628 srcPart = src[i];
2629
2630 if (multiplier == 0 || srcPart == 0) {
2631 low = carry;
2632 high = 0;
2633 } else {
2634 low = lowHalf(srcPart) * lowHalf(multiplier);
2635 high = highHalf(srcPart) * highHalf(multiplier);
2636
2637 mid = lowHalf(srcPart) * highHalf(multiplier);
2638 high += highHalf(mid);
2639 mid <<= integerPartWidth / 2;
2640 if (low + mid < low)
2641 high++;
2642 low += mid;
2643
2644 mid = highHalf(srcPart) * lowHalf(multiplier);
2645 high += highHalf(mid);
2646 mid <<= integerPartWidth / 2;
2647 if (low + mid < low)
2648 high++;
2649 low += mid;
2650
2651 /* Now add carry. */
2652 if (low + carry < low)
2653 high++;
2654 low += carry;
2655 }
2656
2657 if (add) {
2658 /* And now DST[i], and store the new low part there. */
2659 if (low + dst[i] < low)
2660 high++;
2661 dst[i] += low;
2662 } else
2663 dst[i] = low;
2664
2665 carry = high;
2666 }
2667
2668 if (i < dstParts) {
2669 /* Full multiplication, there is no overflow. */
2670 assert(i + 1 == dstParts);
2671 dst[i] = carry;
2672 return 0;
2673 } else {
2674 /* We overflowed if there is carry. */
2675 if (carry)
2676 return 1;
2677
2678 /* We would overflow if any significant unwritten parts would be
2679 non-zero. This is true if any remaining src parts are non-zero
2680 and the multiplier is non-zero. */
2681 if (multiplier)
2682 for (; i < srcParts; i++)
2683 if (src[i])
2684 return 1;
2685
2686 /* We fitted in the narrow destination. */
2687 return 0;
2688 }
2689 }
2690
2691 /* DST = LHS * RHS, where DST has the same width as the operands and
2692 is filled with the least significant parts of the result. Returns
2693 one if overflow occurred, otherwise zero. DST must be disjoint
2694 from both operands. */
2695 int
tcMultiply(integerPart * dst,const integerPart * lhs,const integerPart * rhs,unsigned int parts)2696 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2697 const integerPart *rhs, unsigned int parts)
2698 {
2699 unsigned int i;
2700 int overflow;
2701
2702 assert(dst != lhs && dst != rhs);
2703
2704 overflow = 0;
2705 tcSet(dst, 0, parts);
2706
2707 for (i = 0; i < parts; i++)
2708 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2709 parts - i, true);
2710
2711 return overflow;
2712 }
2713
2714 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2715 operands. No overflow occurs. DST must be disjoint from both
2716 operands. Returns the number of parts required to hold the
2717 result. */
2718 unsigned int
tcFullMultiply(integerPart * dst,const integerPart * lhs,const integerPart * rhs,unsigned int lhsParts,unsigned int rhsParts)2719 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2720 const integerPart *rhs, unsigned int lhsParts,
2721 unsigned int rhsParts)
2722 {
2723 /* Put the narrower number on the LHS for less loops below. */
2724 if (lhsParts > rhsParts) {
2725 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2726 } else {
2727 unsigned int n;
2728
2729 assert(dst != lhs && dst != rhs);
2730
2731 tcSet(dst, 0, rhsParts);
2732
2733 for (n = 0; n < lhsParts; n++)
2734 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2735
2736 n = lhsParts + rhsParts;
2737
2738 return n - (dst[n - 1] == 0);
2739 }
2740 }
2741
2742 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2743 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2744 set REMAINDER to the remainder, return zero. i.e.
2745
2746 OLD_LHS = RHS * LHS + REMAINDER
2747
2748 SCRATCH is a bignum of the same size as the operands and result for
2749 use by the routine; its contents need not be initialized and are
2750 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2751 */
2752 int
tcDivide(integerPart * lhs,const integerPart * rhs,integerPart * remainder,integerPart * srhs,unsigned int parts)2753 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2754 integerPart *remainder, integerPart *srhs,
2755 unsigned int parts)
2756 {
2757 unsigned int n, shiftCount;
2758 integerPart mask;
2759
2760 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2761
2762 shiftCount = tcMSB(rhs, parts) + 1;
2763 if (shiftCount == 0)
2764 return true;
2765
2766 shiftCount = parts * integerPartWidth - shiftCount;
2767 n = shiftCount / integerPartWidth;
2768 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2769
2770 tcAssign(srhs, rhs, parts);
2771 tcShiftLeft(srhs, parts, shiftCount);
2772 tcAssign(remainder, lhs, parts);
2773 tcSet(lhs, 0, parts);
2774
2775 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2776 the total. */
2777 for (;;) {
2778 int compare;
2779
2780 compare = tcCompare(remainder, srhs, parts);
2781 if (compare >= 0) {
2782 tcSubtract(remainder, srhs, 0, parts);
2783 lhs[n] |= mask;
2784 }
2785
2786 if (shiftCount == 0)
2787 break;
2788 shiftCount--;
2789 tcShiftRight(srhs, parts, 1);
2790 if ((mask >>= 1) == 0)
2791 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2792 }
2793
2794 return false;
2795 }
2796
2797 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2798 There are no restrictions on COUNT. */
2799 void
tcShiftLeft(integerPart * dst,unsigned int parts,unsigned int count)2800 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2801 {
2802 if (count) {
2803 unsigned int jump, shift;
2804
2805 /* Jump is the inter-part jump; shift is is intra-part shift. */
2806 jump = count / integerPartWidth;
2807 shift = count % integerPartWidth;
2808
2809 while (parts > jump) {
2810 integerPart part;
2811
2812 parts--;
2813
2814 /* dst[i] comes from the two parts src[i - jump] and, if we have
2815 an intra-part shift, src[i - jump - 1]. */
2816 part = dst[parts - jump];
2817 if (shift) {
2818 part <<= shift;
2819 if (parts >= jump + 1)
2820 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2821 }
2822
2823 dst[parts] = part;
2824 }
2825
2826 while (parts > 0)
2827 dst[--parts] = 0;
2828 }
2829 }
2830
2831 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2832 zero. There are no restrictions on COUNT. */
2833 void
tcShiftRight(integerPart * dst,unsigned int parts,unsigned int count)2834 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2835 {
2836 if (count) {
2837 unsigned int i, jump, shift;
2838
2839 /* Jump is the inter-part jump; shift is is intra-part shift. */
2840 jump = count / integerPartWidth;
2841 shift = count % integerPartWidth;
2842
2843 /* Perform the shift. This leaves the most significant COUNT bits
2844 of the result at zero. */
2845 for (i = 0; i < parts; i++) {
2846 integerPart part;
2847
2848 if (i + jump >= parts) {
2849 part = 0;
2850 } else {
2851 part = dst[i + jump];
2852 if (shift) {
2853 part >>= shift;
2854 if (i + jump + 1 < parts)
2855 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2856 }
2857 }
2858
2859 dst[i] = part;
2860 }
2861 }
2862 }
2863
2864 /* Bitwise and of two bignums. */
2865 void
tcAnd(integerPart * dst,const integerPart * rhs,unsigned int parts)2866 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2867 {
2868 unsigned int i;
2869
2870 for (i = 0; i < parts; i++)
2871 dst[i] &= rhs[i];
2872 }
2873
2874 /* Bitwise inclusive or of two bignums. */
2875 void
tcOr(integerPart * dst,const integerPart * rhs,unsigned int parts)2876 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2877 {
2878 unsigned int i;
2879
2880 for (i = 0; i < parts; i++)
2881 dst[i] |= rhs[i];
2882 }
2883
2884 /* Bitwise exclusive or of two bignums. */
2885 void
tcXor(integerPart * dst,const integerPart * rhs,unsigned int parts)2886 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2887 {
2888 unsigned int i;
2889
2890 for (i = 0; i < parts; i++)
2891 dst[i] ^= rhs[i];
2892 }
2893
2894 /* Complement a bignum in-place. */
2895 void
tcComplement(integerPart * dst,unsigned int parts)2896 APInt::tcComplement(integerPart *dst, unsigned int parts)
2897 {
2898 unsigned int i;
2899
2900 for (i = 0; i < parts; i++)
2901 dst[i] = ~dst[i];
2902 }
2903
2904 /* Comparison (unsigned) of two bignums. */
2905 int
tcCompare(const integerPart * lhs,const integerPart * rhs,unsigned int parts)2906 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2907 unsigned int parts)
2908 {
2909 while (parts) {
2910 parts--;
2911 if (lhs[parts] == rhs[parts])
2912 continue;
2913
2914 if (lhs[parts] > rhs[parts])
2915 return 1;
2916 else
2917 return -1;
2918 }
2919
2920 return 0;
2921 }
2922
2923 /* Increment a bignum in-place, return the carry flag. */
2924 integerPart
tcIncrement(integerPart * dst,unsigned int parts)2925 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2926 {
2927 unsigned int i;
2928
2929 for (i = 0; i < parts; i++)
2930 if (++dst[i] != 0)
2931 break;
2932
2933 return i == parts;
2934 }
2935
2936 /* Set the least significant BITS bits of a bignum, clear the
2937 rest. */
2938 void
tcSetLeastSignificantBits(integerPart * dst,unsigned int parts,unsigned int bits)2939 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2940 unsigned int bits)
2941 {
2942 unsigned int i;
2943
2944 i = 0;
2945 while (bits > integerPartWidth) {
2946 dst[i++] = ~(integerPart) 0;
2947 bits -= integerPartWidth;
2948 }
2949
2950 if (bits)
2951 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
2952
2953 while (i < parts)
2954 dst[i++] = 0;
2955 }
2956