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