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