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