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