APInt.cpp revision b04973edfaffb12905f58379d632f0d7e4bb5d9b
1//===-- APInt.cpp - Implement APInt class ---------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Sheng Zhou and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a class to represent arbitrary precision integral 11// constant values. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/APInt.h" 16#include "llvm/DerivedTypes.h" 17#include "llvm/Support/MathExtras.h" 18#include <cstring> 19#include <cstdlib> 20using namespace llvm; 21 22/// mul_1 - This function performs the multiplication operation on a 23/// large integer (represented as an integer array) and a uint64_t integer. 24/// @returns the carry of the multiplication. 25static uint64_t mul_1(uint64_t dest[], uint64_t x[], 26 unsigned len, uint64_t y) { 27 // Split y into high 32-bit part and low 32-bit part. 28 uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 29 uint64_t carry = 0, lx, hx; 30 for (unsigned i = 0; i < len; ++i) { 31 lx = x[i] & 0xffffffffULL; 32 hx = x[i] >> 32; 33 // hasCarry - A flag to indicate if has carry. 34 // hasCarry == 0, no carry 35 // hasCarry == 1, has carry 36 // hasCarry == 2, no carry and the calculation result == 0. 37 uint8_t hasCarry = 0; 38 dest[i] = carry + lx * ly; 39 // Determine if the add above introduces carry. 40 hasCarry = (dest[i] < carry) ? 1 : 0; 41 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 42 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 43 // (2^32 - 1) + 2^32 = 2^64. 44 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 45 46 carry += (lx * hy) & 0xffffffffULL; 47 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 48 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 49 (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 50 } 51 52 return carry; 53} 54 55/// mul - This function multiplies integer array x[] by integer array y[] and 56/// stores the result into integer array dest[]. 57/// Note the array dest[]'s size should no less than xlen + ylen. 58static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, 59 uint64_t y[], unsigned ylen) { 60 dest[xlen] = mul_1(dest, x, xlen, y[0]); 61 62 for (unsigned i = 1; i < ylen; ++i) { 63 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 64 uint64_t carry = 0, lx, hx; 65 for (unsigned j = 0; j < xlen; ++j) { 66 lx = x[j] & 0xffffffffULL; 67 hx = x[j] >> 32; 68 // hasCarry - A flag to indicate if has carry. 69 // hasCarry == 0, no carry 70 // hasCarry == 1, has carry 71 // hasCarry == 2, no carry and the calculation result == 0. 72 uint8_t hasCarry = 0; 73 uint64_t resul = carry + lx * ly; 74 hasCarry = (resul < carry) ? 1 : 0; 75 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 76 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 77 78 carry += (lx * hy) & 0xffffffffULL; 79 resul = (carry << 32) | (resul & 0xffffffffULL); 80 dest[i+j] += resul; 81 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 82 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 83 ((lx * hy) >> 32) + hx * hy; 84 } 85 dest[i+xlen] = carry; 86 } 87} 88 89/// add_1 - This function adds the integer array x[] by integer y and 90/// returns the carry. 91/// @returns the carry of the addition. 92static uint64_t add_1(uint64_t dest[], uint64_t x[], 93 unsigned len, uint64_t y) { 94 uint64_t carry = y; 95 96 for (unsigned i = 0; i < len; ++i) { 97 dest[i] = carry + x[i]; 98 carry = (dest[i] < carry) ? 1 : 0; 99 } 100 return carry; 101} 102 103/// add - This function adds the integer array x[] by integer array 104/// y[] and returns the carry. 105static uint64_t add(uint64_t dest[], uint64_t x[], 106 uint64_t y[], unsigned len) { 107 unsigned carry = 0; 108 109 for (unsigned i = 0; i< len; ++i) { 110 carry += x[i]; 111 dest[i] = carry + y[i]; 112 carry = carry < x[i] ? 1 : (dest[i] < carry ? 1 : 0); 113 } 114 return carry; 115} 116 117/// sub_1 - This function subtracts the integer array x[] by 118/// integer y and returns the borrow-out carry. 119static uint64_t sub_1(uint64_t x[], unsigned len, uint64_t y) { 120 uint64_t cy = y; 121 122 for (unsigned i = 0; i < len; ++i) { 123 uint64_t X = x[i]; 124 x[i] -= cy; 125 if (cy > X) 126 cy = 1; 127 else { 128 cy = 0; 129 break; 130 } 131 } 132 133 return cy; 134} 135 136/// sub - This function subtracts the integer array x[] by 137/// integer array y[], and returns the borrow-out carry. 138static uint64_t sub(uint64_t dest[], uint64_t x[], 139 uint64_t y[], unsigned len) { 140 // Carry indicator. 141 uint64_t cy = 0; 142 143 for (unsigned i = 0; i < len; ++i) { 144 uint64_t Y = y[i], X = x[i]; 145 Y += cy; 146 147 cy = Y < cy ? 1 : 0; 148 Y = X - Y; 149 cy += Y > X ? 1 : 0; 150 dest[i] = Y; 151 } 152 return cy; 153} 154 155/// UnitDiv - This function divides N by D, 156/// and returns (remainder << 32) | quotient. 157/// Assumes (N >> 32) < D. 158static uint64_t unitDiv(uint64_t N, unsigned D) { 159 uint64_t q, r; // q: quotient, r: remainder. 160 uint64_t a1 = N >> 32; // a1: high 32-bit part of N. 161 uint64_t a0 = N & 0xffffffffL; // a0: low 32-bit part of N 162 if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL)) { 163 q = N / D; 164 r = N % D; 165 } 166 else { 167 // Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d 168 uint64_t c = N - ((uint64_t) D << 31); 169 // Divide (c1*2^32 + c0) by d 170 q = c / D; 171 r = c % D; 172 // Add 2^31 to quotient 173 q += 1 << 31; 174 } 175 176 return (r << 32) | (q & 0xFFFFFFFFl); 177} 178 179/// subMul - This function substracts x[len-1:0] * y from 180/// dest[offset+len-1:offset], and returns the most significant 181/// word of the product, minus the borrow-out from the subtraction. 182static unsigned subMul(unsigned dest[], unsigned offset, 183 unsigned x[], unsigned len, unsigned y) { 184 uint64_t yl = (uint64_t) y & 0xffffffffL; 185 unsigned carry = 0; 186 unsigned j = 0; 187 do { 188 uint64_t prod = ((uint64_t) x[j] & 0xffffffffL) * yl; 189 unsigned prod_low = (unsigned) prod; 190 unsigned prod_high = (unsigned) (prod >> 32); 191 prod_low += carry; 192 carry = (prod_low < carry ? 1 : 0) + prod_high; 193 unsigned x_j = dest[offset+j]; 194 prod_low = x_j - prod_low; 195 if (prod_low > x_j) ++carry; 196 dest[offset+j] = prod_low; 197 } while (++j < len); 198 return carry; 199} 200 201/// div - This is basically Knuth's formulation of the classical algorithm. 202/// Correspondance with Knuth's notation: 203/// Knuth's u[0:m+n] == zds[nx:0]. 204/// Knuth's v[1:n] == y[ny-1:0] 205/// Knuth's n == ny. 206/// Knuth's m == nx-ny. 207/// Our nx == Knuth's m+n. 208/// Could be re-implemented using gmp's mpn_divrem: 209/// zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny). 210static void div(unsigned zds[], unsigned nx, unsigned y[], unsigned ny) { 211 unsigned j = nx; 212 do { // loop over digits of quotient 213 // Knuth's j == our nx-j. 214 // Knuth's u[j:j+n] == our zds[j:j-ny]. 215 unsigned qhat; // treated as unsigned 216 if (zds[j] == y[ny-1]) qhat = -1U; // 0xffffffff 217 else { 218 uint64_t w = (((uint64_t)(zds[j])) << 32) + 219 ((uint64_t)zds[j-1] & 0xffffffffL); 220 qhat = (unsigned) unitDiv(w, y[ny-1]); 221 } 222 if (qhat) { 223 unsigned borrow = subMul(zds, j - ny, y, ny, qhat); 224 unsigned save = zds[j]; 225 uint64_t num = ((uint64_t)save&0xffffffffL) - 226 ((uint64_t)borrow&0xffffffffL); 227 while (num) { 228 qhat--; 229 uint64_t carry = 0; 230 for (unsigned i = 0; i < ny; i++) { 231 carry += ((uint64_t) zds[j-ny+i] & 0xffffffffL) 232 + ((uint64_t) y[i] & 0xffffffffL); 233 zds[j-ny+i] = (unsigned) carry; 234 carry >>= 32; 235 } 236 zds[j] += carry; 237 num = carry - 1; 238 } 239 } 240 zds[j] = qhat; 241 } while (--j >= ny); 242} 243 244/// lshift - This function shift x[0:len-1] left by shiftAmt bits, and 245/// store the len least significant words of the result in 246/// dest[d_offset:d_offset+len-1]. It returns the bits shifted out from 247/// the most significant digit. 248static uint64_t lshift(uint64_t dest[], unsigned d_offset, 249 uint64_t x[], unsigned len, unsigned shiftAmt) { 250 unsigned count = 64 - shiftAmt; 251 int i = len - 1; 252 uint64_t high_word = x[i], retVal = high_word >> count; 253 ++d_offset; 254 while (--i >= 0) { 255 uint64_t low_word = x[i]; 256 dest[d_offset+i] = (high_word << shiftAmt) | (low_word >> count); 257 high_word = low_word; 258 } 259 dest[d_offset+i] = high_word << shiftAmt; 260 return retVal; 261} 262 263APInt::APInt(uint64_t val, unsigned numBits) 264 : BitsNum(numBits) { 265 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small"); 266 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large"); 267 if (isSingleWord()) 268 VAL = val & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum)); 269 else { 270 // Memory allocation and check if successful. 271 assert((pVal = new uint64_t[getNumWords()]) && 272 "APInt memory allocation fails!"); 273 memset(pVal, 0, getNumWords() * 8); 274 pVal[0] = val; 275 } 276} 277 278APInt::APInt(unsigned numBits, uint64_t bigVal[]) 279 : BitsNum(numBits) { 280 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small"); 281 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large"); 282 assert(bigVal && "Null pointer detected!"); 283 if (isSingleWord()) 284 VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum)); 285 else { 286 // Memory allocation and check if successful. 287 assert((pVal = new uint64_t[getNumWords()]) && 288 "APInt memory allocation fails!"); 289 // Calculate the actual length of bigVal[]. 290 unsigned n = sizeof(*bigVal) / sizeof(bigVal[0]); 291 unsigned maxN = std::max<unsigned>(n, getNumWords()); 292 unsigned minN = std::min<unsigned>(n, getNumWords()); 293 memcpy(pVal, bigVal, (minN - 1) * 8); 294 pVal[minN-1] = bigVal[minN-1] & (~uint64_t(0ULL) >> (64 - BitsNum % 64)); 295 if (maxN == getNumWords()) 296 memset(pVal+n, 0, (getNumWords() - n) * 8); 297 } 298} 299 300/// @brief Create a new APInt by translating the char array represented 301/// integer value. 302APInt::APInt(const char StrStart[], unsigned slen, uint8_t radix) { 303 StrToAPInt(StrStart, slen, radix); 304} 305 306/// @brief Create a new APInt by translating the string represented 307/// integer value. 308APInt::APInt(const std::string& Val, uint8_t radix) { 309 assert(!Val.empty() && "String empty?"); 310 StrToAPInt(Val.c_str(), Val.size(), radix); 311} 312 313/// @brief Converts a char array into an integer. 314void APInt::StrToAPInt(const char *StrStart, unsigned slen, uint8_t radix) { 315 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 316 "Radix should be 2, 8, 10, or 16!"); 317 assert(StrStart && "String empty?"); 318 unsigned size = 0; 319 // If the radix is a power of 2, read the input 320 // from most significant to least significant. 321 if ((radix & (radix - 1)) == 0) { 322 unsigned nextBitPos = 0, bits_per_digit = radix / 8 + 2; 323 uint64_t resDigit = 0; 324 BitsNum = slen * bits_per_digit; 325 if (getNumWords() > 1) 326 assert((pVal = new uint64_t[getNumWords()]) && 327 "APInt memory allocation fails!"); 328 for (int i = slen - 1; i >= 0; --i) { 329 uint64_t digit = StrStart[i] - 48; // '0' == 48. 330 resDigit |= digit << nextBitPos; 331 nextBitPos += bits_per_digit; 332 if (nextBitPos >= 64) { 333 if (isSingleWord()) { 334 VAL = resDigit; 335 break; 336 } 337 pVal[size++] = resDigit; 338 nextBitPos -= 64; 339 resDigit = digit >> (bits_per_digit - nextBitPos); 340 } 341 } 342 if (!isSingleWord() && size <= getNumWords()) 343 pVal[size] = resDigit; 344 } else { // General case. The radix is not a power of 2. 345 // For 10-radix, the max value of 64-bit integer is 18446744073709551615, 346 // and its digits number is 20. 347 const unsigned chars_per_word = 20; 348 if (slen < chars_per_word || 349 (slen == chars_per_word && // In case the value <= 2^64 - 1 350 strcmp(StrStart, "18446744073709551615") <= 0)) { 351 BitsNum = 64; 352 VAL = strtoull(StrStart, 0, 10); 353 } else { // In case the value > 2^64 - 1 354 BitsNum = (slen / chars_per_word + 1) * 64; 355 assert((pVal = new uint64_t[getNumWords()]) && 356 "APInt memory allocation fails!"); 357 memset(pVal, 0, getNumWords() * 8); 358 unsigned str_pos = 0; 359 while (str_pos < slen) { 360 unsigned chunk = slen - str_pos; 361 if (chunk > chars_per_word - 1) 362 chunk = chars_per_word - 1; 363 uint64_t resDigit = StrStart[str_pos++] - 48; // 48 == '0'. 364 uint64_t big_base = radix; 365 while (--chunk > 0) { 366 resDigit = resDigit * radix + StrStart[str_pos++] - 48; 367 big_base *= radix; 368 } 369 370 uint64_t carry; 371 if (!size) 372 carry = resDigit; 373 else { 374 carry = mul_1(pVal, pVal, size, big_base); 375 carry += add_1(pVal, pVal, size, resDigit); 376 } 377 378 if (carry) pVal[size++] = carry; 379 } 380 } 381 } 382} 383 384APInt::APInt(const APInt& APIVal) 385 : BitsNum(APIVal.BitsNum) { 386 if (isSingleWord()) VAL = APIVal.VAL; 387 else { 388 // Memory allocation and check if successful. 389 assert((pVal = new uint64_t[getNumWords()]) && 390 "APInt memory allocation fails!"); 391 memcpy(pVal, APIVal.pVal, getNumWords() * 8); 392 } 393} 394 395APInt::~APInt() { 396 if (!isSingleWord() && pVal) delete[] pVal; 397} 398 399/// @brief Copy assignment operator. Create a new object from the given 400/// APInt one by initialization. 401APInt& APInt::operator=(const APInt& RHS) { 402 if (isSingleWord()) VAL = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 403 else { 404 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 405 memcpy(pVal, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, minN * 8); 406 if (getNumWords() != minN) 407 memset(pVal + minN, 0, (getNumWords() - minN) * 8); 408 } 409 return *this; 410} 411 412/// @brief Assignment operator. Assigns a common case integer value to 413/// the APInt. 414APInt& APInt::operator=(uint64_t RHS) { 415 if (isSingleWord()) VAL = RHS; 416 else { 417 pVal[0] = RHS; 418 memset(pVal, 0, (getNumWords() - 1) * 8); 419 } 420 TruncToBits(); 421 return *this; 422} 423 424/// @brief Prefix increment operator. Increments the APInt by one. 425APInt& APInt::operator++() { 426 if (isSingleWord()) ++VAL; 427 else 428 add_1(pVal, pVal, getNumWords(), 1); 429 TruncToBits(); 430 return *this; 431} 432 433/// @brief Prefix decrement operator. Decrements the APInt by one. 434APInt& APInt::operator--() { 435 if (isSingleWord()) --VAL; 436 else 437 sub_1(pVal, getNumWords(), 1); 438 TruncToBits(); 439 return *this; 440} 441 442/// @brief Addition assignment operator. Adds this APInt by the given APInt& 443/// RHS and assigns the result to this APInt. 444APInt& APInt::operator+=(const APInt& RHS) { 445 if (isSingleWord()) VAL += RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 446 else { 447 if (RHS.isSingleWord()) add_1(pVal, pVal, getNumWords(), RHS.VAL); 448 else { 449 if (getNumWords() <= RHS.getNumWords()) 450 add(pVal, pVal, RHS.pVal, getNumWords()); 451 else { 452 uint64_t carry = add(pVal, pVal, RHS.pVal, RHS.getNumWords()); 453 add_1(pVal + RHS.getNumWords(), pVal + RHS.getNumWords(), 454 getNumWords() - RHS.getNumWords(), carry); 455 } 456 } 457 } 458 TruncToBits(); 459 return *this; 460} 461 462/// @brief Subtraction assignment operator. Subtracts this APInt by the given 463/// APInt &RHS and assigns the result to this APInt. 464APInt& APInt::operator-=(const APInt& RHS) { 465 if (isSingleWord()) 466 VAL -= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 467 else { 468 if (RHS.isSingleWord()) 469 sub_1(pVal, getNumWords(), RHS.VAL); 470 else { 471 if (RHS.getNumWords() < getNumWords()) { 472 uint64_t carry = sub(pVal, pVal, RHS.pVal, RHS.getNumWords()); 473 sub_1(pVal + RHS.getNumWords(), getNumWords() - RHS.getNumWords(), carry); 474 } 475 else 476 sub(pVal, pVal, RHS.pVal, getNumWords()); 477 } 478 } 479 TruncToBits(); 480 return *this; 481} 482 483/// @brief Multiplication assignment operator. Multiplies this APInt by the 484/// given APInt& RHS and assigns the result to this APInt. 485APInt& APInt::operator*=(const APInt& RHS) { 486 if (isSingleWord()) VAL *= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 487 else { 488 // one-based first non-zero bit position. 489 unsigned first = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(); 490 unsigned xlen = !first ? 0 : whichWord(first - 1) + 1; 491 if (!xlen) 492 return *this; 493 else if (RHS.isSingleWord()) 494 mul_1(pVal, pVal, xlen, RHS.VAL); 495 else { 496 first = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros(); 497 unsigned ylen = !first ? 0 : whichWord(first - 1) + 1; 498 if (!ylen) { 499 memset(pVal, 0, getNumWords() * 8); 500 return *this; 501 } 502 uint64_t *dest = new uint64_t[xlen+ylen]; 503 assert(dest && "Memory Allocation Failed!"); 504 mul(dest, pVal, xlen, RHS.pVal, ylen); 505 memcpy(pVal, dest, ((xlen + ylen >= getNumWords()) ? 506 getNumWords() : xlen + ylen) * 8); 507 delete[] dest; 508 } 509 } 510 TruncToBits(); 511 return *this; 512} 513 514/// @brief Bitwise AND assignment operator. Performs bitwise AND operation on 515/// this APInt and the given APInt& RHS, assigns the result to this APInt. 516APInt& APInt::operator&=(const APInt& RHS) { 517 if (isSingleWord()) { 518 if (RHS.isSingleWord()) VAL &= RHS.VAL; 519 else VAL &= RHS.pVal[0]; 520 } else { 521 if (RHS.isSingleWord()) { 522 memset(pVal, 0, (getNumWords() - 1) * 8); 523 pVal[0] &= RHS.VAL; 524 } else { 525 unsigned minwords = getNumWords() < RHS.getNumWords() ? 526 getNumWords() : RHS.getNumWords(); 527 for (unsigned i = 0; i < minwords; ++i) 528 pVal[i] &= RHS.pVal[i]; 529 if (getNumWords() > minwords) 530 memset(pVal+minwords, 0, (getNumWords() - minwords) * 8); 531 } 532 } 533 return *this; 534} 535 536/// @brief Bitwise OR assignment operator. Performs bitwise OR operation on 537/// this APInt and the given APInt& RHS, assigns the result to this APInt. 538APInt& APInt::operator|=(const APInt& RHS) { 539 if (isSingleWord()) { 540 if (RHS.isSingleWord()) VAL |= RHS.VAL; 541 else VAL |= RHS.pVal[0]; 542 } else { 543 if (RHS.isSingleWord()) { 544 pVal[0] |= RHS.VAL; 545 } else { 546 unsigned minwords = getNumWords() < RHS.getNumWords() ? 547 getNumWords() : RHS.getNumWords(); 548 for (unsigned i = 0; i < minwords; ++i) 549 pVal[i] |= RHS.pVal[i]; 550 } 551 } 552 TruncToBits(); 553 return *this; 554} 555 556/// @brief Bitwise XOR assignment operator. Performs bitwise XOR operation on 557/// this APInt and the given APInt& RHS, assigns the result to this APInt. 558APInt& APInt::operator^=(const APInt& RHS) { 559 if (isSingleWord()) { 560 if (RHS.isSingleWord()) VAL ^= RHS.VAL; 561 else VAL ^= RHS.pVal[0]; 562 } else { 563 if (RHS.isSingleWord()) { 564 for (unsigned i = 0; i < getNumWords(); ++i) 565 pVal[i] ^= RHS.VAL; 566 } else { 567 unsigned minwords = getNumWords() < RHS.getNumWords() ? 568 getNumWords() : RHS.getNumWords(); 569 for (unsigned i = 0; i < minwords; ++i) 570 pVal[i] ^= RHS.pVal[i]; 571 if (getNumWords() > minwords) 572 for (unsigned i = minwords; i < getNumWords(); ++i) 573 pVal[i] ^= 0; 574 } 575 } 576 TruncToBits(); 577 return *this; 578} 579 580/// @brief Bitwise AND operator. Performs bitwise AND operation on this APInt 581/// and the given APInt& RHS. 582APInt APInt::operator&(const APInt& RHS) const { 583 APInt API(RHS); 584 return API &= *this; 585} 586 587/// @brief Bitwise OR operator. Performs bitwise OR operation on this APInt 588/// and the given APInt& RHS. 589APInt APInt::operator|(const APInt& RHS) const { 590 APInt API(RHS); 591 API |= *this; 592 API.TruncToBits(); 593 return API; 594} 595 596/// @brief Bitwise XOR operator. Performs bitwise XOR operation on this APInt 597/// and the given APInt& RHS. 598APInt APInt::operator^(const APInt& RHS) const { 599 APInt API(RHS); 600 API ^= *this; 601 API.TruncToBits(); 602 return API; 603} 604 605/// @brief Logical AND operator. Performs logical AND operation on this APInt 606/// and the given APInt& RHS. 607bool APInt::operator&&(const APInt& RHS) const { 608 if (isSingleWord()) 609 return RHS.isSingleWord() ? VAL && RHS.VAL : VAL && RHS.pVal[0]; 610 else if (RHS.isSingleWord()) 611 return RHS.VAL && pVal[0]; 612 else { 613 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 614 for (unsigned i = 0; i < minN; ++i) 615 if (pVal[i] && RHS.pVal[i]) 616 return true; 617 } 618 return false; 619} 620 621/// @brief Logical OR operator. Performs logical OR operation on this APInt 622/// and the given APInt& RHS. 623bool APInt::operator||(const APInt& RHS) const { 624 if (isSingleWord()) 625 return RHS.isSingleWord() ? VAL || RHS.VAL : VAL || RHS.pVal[0]; 626 else if (RHS.isSingleWord()) 627 return RHS.VAL || pVal[0]; 628 else { 629 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 630 for (unsigned i = 0; i < minN; ++i) 631 if (pVal[i] || RHS.pVal[i]) 632 return true; 633 } 634 return false; 635} 636 637/// @brief Logical negation operator. Performs logical negation operation on 638/// this APInt. 639bool APInt::operator !() const { 640 if (isSingleWord()) 641 return !VAL; 642 else 643 for (unsigned i = 0; i < getNumWords(); ++i) 644 if (pVal[i]) 645 return false; 646 return true; 647} 648 649/// @brief Multiplication operator. Multiplies this APInt by the given APInt& 650/// RHS. 651APInt APInt::operator*(const APInt& RHS) const { 652 APInt API(RHS); 653 API *= *this; 654 API.TruncToBits(); 655 return API; 656} 657 658/// @brief Addition operator. Adds this APInt by the given APInt& RHS. 659APInt APInt::operator+(const APInt& RHS) const { 660 APInt API(*this); 661 API += RHS; 662 API.TruncToBits(); 663 return API; 664} 665 666/// @brief Subtraction operator. Subtracts this APInt by the given APInt& RHS 667APInt APInt::operator-(const APInt& RHS) const { 668 APInt API(*this); 669 API -= RHS; 670 return API; 671} 672 673/// @brief Array-indexing support. 674bool APInt::operator[](unsigned bitPosition) const { 675 return (maskBit(bitPosition) & (isSingleWord() ? 676 VAL : pVal[whichWord(bitPosition)])) != 0; 677} 678 679/// @brief Equality operator. Compare this APInt with the given APInt& RHS 680/// for the validity of the equality relationship. 681bool APInt::operator==(const APInt& RHS) const { 682 unsigned n1 = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(), 683 n2 = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros(); 684 if (n1 != n2) return false; 685 else if (isSingleWord()) 686 return VAL == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 687 else { 688 if (n1 <= 64) 689 return pVal[0] == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 690 for (int i = whichWord(n1 - 1); i >= 0; --i) 691 if (pVal[i] != RHS.pVal[i]) return false; 692 } 693 return true; 694} 695 696/// @brief Equality operator. Compare this APInt with the given uint64_t value 697/// for the validity of the equality relationship. 698bool APInt::operator==(uint64_t Val) const { 699 if (isSingleWord()) 700 return VAL == Val; 701 else { 702 unsigned n = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(); 703 if (n <= 64) 704 return pVal[0] == Val; 705 else 706 return false; 707 } 708} 709 710/// @brief Less-than operator. Compare this APInt with the given APInt& RHS 711/// for the validity of the less-than relationship. 712bool APInt::operator <(const APInt& RHS) const { 713 unsigned n1 = getNumWords() * 64 - CountLeadingZeros(), 714 n2 = RHS.getNumWords() * 64 - RHS.CountLeadingZeros(); 715 if (n1 < n2) return true; 716 else if (n1 > n2) return false; 717 else if (isSingleWord()) 718 return VAL < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 719 else { 720 if (n1 <= 64) 721 return pVal[0] < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 722 for (int i = whichWord(n1 - 1); i >= 0; --i) { 723 if (pVal[i] > RHS.pVal[i]) return false; 724 else if (pVal[i] < RHS.pVal[i]) return true; 725 } 726 } 727 return false; 728} 729 730/// @brief Less-than-or-equal operator. Compare this APInt with the given 731/// APInt& RHS for the validity of the less-than-or-equal relationship. 732bool APInt::operator<=(const APInt& RHS) const { 733 return (*this) == RHS || (*this) < RHS; 734} 735 736/// @brief Greater-than operator. Compare this APInt with the given APInt& RHS 737/// for the validity of the greater-than relationship. 738bool APInt::operator >(const APInt& RHS) const { 739 return !((*this) <= RHS); 740} 741 742/// @brief Greater-than-or-equal operator. Compare this APInt with the given 743/// APInt& RHS for the validity of the greater-than-or-equal relationship. 744bool APInt::operator>=(const APInt& RHS) const { 745 return !((*this) < RHS); 746} 747 748/// Set the given bit to 1 whose poition is given as "bitPosition". 749/// @brief Set a given bit to 1. 750APInt& APInt::set(unsigned bitPosition) { 751 if (isSingleWord()) VAL |= maskBit(bitPosition); 752 else pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 753 return *this; 754} 755 756/// @brief Set every bit to 1. 757APInt& APInt::set() { 758 if (isSingleWord()) VAL = ~0ULL >> (64 - BitsNum); 759 else { 760 for (unsigned i = 0; i < getNumWords() - 1; ++i) 761 pVal[i] = -1ULL; 762 pVal[getNumWords() - 1] = ~0ULL >> (64 - BitsNum % 64); 763 } 764 return *this; 765} 766 767/// Set the given bit to 0 whose position is given as "bitPosition". 768/// @brief Set a given bit to 0. 769APInt& APInt::clear(unsigned bitPosition) { 770 if (isSingleWord()) VAL &= ~maskBit(bitPosition); 771 else pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 772 return *this; 773} 774 775/// @brief Set every bit to 0. 776APInt& APInt::clear() { 777 if (isSingleWord()) VAL = 0; 778 else 779 memset(pVal, 0, getNumWords() * 8); 780 return *this; 781} 782 783/// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on 784/// this APInt. 785APInt APInt::operator~() const { 786 APInt API(*this); 787 API.flip(); 788 return API; 789} 790 791/// @brief Toggle every bit to its opposite value. 792APInt& APInt::flip() { 793 if (isSingleWord()) VAL = (~(VAL << (64 - BitsNum))) >> (64 - BitsNum); 794 else { 795 unsigned i = 0; 796 for (; i < getNumWords() - 1; ++i) 797 pVal[i] = ~pVal[i]; 798 unsigned offset = 64 - (BitsNum - 64 * (i - 1)); 799 pVal[i] = (~(pVal[i] << offset)) >> offset; 800 } 801 return *this; 802} 803 804/// Toggle a given bit to its opposite value whose position is given 805/// as "bitPosition". 806/// @brief Toggles a given bit to its opposite value. 807APInt& APInt::flip(unsigned bitPosition) { 808 assert(bitPosition < BitsNum && "Out of the bit-width range!"); 809 if ((*this)[bitPosition]) clear(bitPosition); 810 else set(bitPosition); 811 return *this; 812} 813 814/// to_string - This function translates the APInt into a string. 815std::string APInt::to_string(uint8_t radix) const { 816 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 817 "Radix should be 2, 8, 10, or 16!"); 818 static const char *digits[] = { 819 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F" 820 }; 821 std::string result; 822 unsigned bits_used = getNumWords() * 64 - CountLeadingZeros(); 823 if (isSingleWord()) { 824 char buf[65]; 825 const char *format = (radix == 10 ? "%llu" : 826 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0))); 827 if (format) { 828 sprintf(buf, format, VAL); 829 } else { 830 memset(buf, 0, 65); 831 uint64_t v = VAL; 832 while (bits_used) { 833 unsigned bit = v & 1; 834 bits_used--; 835 buf[bits_used] = digits[bit][0]; 836 v >>=1; 837 } 838 } 839 result = buf; 840 return result; 841 } 842 843 APInt tmp(*this); 844 APInt divisor(radix,64); 845 if (tmp == 0) 846 result = "0"; 847 else while (tmp != 0) { 848 APInt APdigit = APIntOps::URem(tmp,divisor); 849 unsigned digit = APdigit.getValue(); 850 assert(digit < radix && "URem failed"); 851 result.insert(0,digits[digit]); 852 tmp = APIntOps::UDiv(tmp, divisor); 853 } 854 855 return result; 856} 857 858/// getMaxValue - This function returns the largest value 859/// for an APInt of the specified bit-width and if isSign == true, 860/// it should be largest signed value, otherwise unsigned value. 861APInt APInt::getMaxValue(unsigned numBits, bool isSign) { 862 APInt APIVal(0, numBits); 863 APIVal.set(); 864 if (isSign) APIVal.clear(numBits - 1); 865 return APIVal; 866} 867 868/// getMinValue - This function returns the smallest value for 869/// an APInt of the given bit-width and if isSign == true, 870/// it should be smallest signed value, otherwise zero. 871APInt APInt::getMinValue(unsigned numBits, bool isSign) { 872 APInt APIVal(0, numBits); 873 if (isSign) APIVal.set(numBits - 1); 874 return APIVal; 875} 876 877/// getAllOnesValue - This function returns an all-ones value for 878/// an APInt of the specified bit-width. 879APInt APInt::getAllOnesValue(unsigned numBits) { 880 return getMaxValue(numBits, false); 881} 882 883/// getNullValue - This function creates an '0' value for an 884/// APInt of the specified bit-width. 885APInt APInt::getNullValue(unsigned numBits) { 886 return getMinValue(numBits, false); 887} 888 889/// HiBits - This function returns the high "numBits" bits of this APInt. 890APInt APInt::HiBits(unsigned numBits) const { 891 return APIntOps::LShr(*this, BitsNum - numBits); 892} 893 894/// LoBits - This function returns the low "numBits" bits of this APInt. 895APInt APInt::LoBits(unsigned numBits) const { 896 return APIntOps::LShr(APIntOps::Shl(*this, BitsNum - numBits), 897 BitsNum - numBits); 898} 899 900/// CountLeadingZeros - This function is a APInt version corresponding to 901/// llvm/include/llvm/Support/MathExtras.h's function 902/// CountLeadingZeros_{32, 64}. It performs platform optimal form of counting 903/// the number of zeros from the most significant bit to the first one bit. 904/// @returns numWord() * 64 if the value is zero. 905unsigned APInt::CountLeadingZeros() const { 906 if (isSingleWord()) 907 return CountLeadingZeros_64(VAL); 908 unsigned Count = 0; 909 for (int i = getNumWords() - 1; i >= 0; --i) { 910 unsigned tmp = CountLeadingZeros_64(pVal[i]); 911 Count += tmp; 912 if (tmp != 64) 913 break; 914 } 915 return Count; 916} 917 918/// CountTrailingZero - This function is a APInt version corresponding to 919/// llvm/include/llvm/Support/MathExtras.h's function 920/// CountTrailingZeros_{32, 64}. It performs platform optimal form of counting 921/// the number of zeros from the least significant bit to the first one bit. 922/// @returns numWord() * 64 if the value is zero. 923unsigned APInt::CountTrailingZeros() const { 924 if (isSingleWord()) 925 return CountTrailingZeros_64(~VAL & (VAL - 1)); 926 APInt Tmp = ~(*this) & ((*this) - 1); 927 return getNumWords() * 64 - Tmp.CountLeadingZeros(); 928} 929 930/// CountPopulation - This function is a APInt version corresponding to 931/// llvm/include/llvm/Support/MathExtras.h's function 932/// CountPopulation_{32, 64}. It counts the number of set bits in a value. 933/// @returns 0 if the value is zero. 934unsigned APInt::CountPopulation() const { 935 if (isSingleWord()) 936 return CountPopulation_64(VAL); 937 unsigned Count = 0; 938 for (unsigned i = 0; i < getNumWords(); ++i) 939 Count += CountPopulation_64(pVal[i]); 940 return Count; 941} 942 943 944/// ByteSwap - This function returns a byte-swapped representation of the 945/// this APInt. 946APInt APInt::ByteSwap() const { 947 assert(BitsNum >= 16 && BitsNum % 16 == 0 && "Cannot byteswap!"); 948 if (BitsNum == 16) 949 return APInt(ByteSwap_16(VAL), BitsNum); 950 else if (BitsNum == 32) 951 return APInt(ByteSwap_32(VAL), BitsNum); 952 else if (BitsNum == 48) { 953 uint64_t Tmp1 = ((VAL >> 32) << 16) | (VAL & 0xFFFF); 954 Tmp1 = ByteSwap_32(Tmp1); 955 uint64_t Tmp2 = (VAL >> 16) & 0xFFFF; 956 Tmp2 = ByteSwap_16(Tmp2); 957 return 958 APInt((Tmp1 & 0xff) | ((Tmp1<<16) & 0xffff00000000ULL) | (Tmp2 << 16), 959 BitsNum); 960 } else if (BitsNum == 64) 961 return APInt(ByteSwap_64(VAL), BitsNum); 962 else { 963 APInt Result(0, BitsNum); 964 char *pByte = (char*)Result.pVal; 965 for (unsigned i = 0; i < BitsNum / 8 / 2; ++i) { 966 char Tmp = pByte[i]; 967 pByte[i] = pByte[BitsNum / 8 - 1 - i]; 968 pByte[BitsNum / 8 - i - 1] = Tmp; 969 } 970 return Result; 971 } 972} 973 974/// GreatestCommonDivisor - This function returns the greatest common 975/// divisor of the two APInt values using Enclid's algorithm. 976APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 977 const APInt& API2) { 978 APInt A = API1, B = API2; 979 while (!!B) { 980 APInt T = B; 981 B = APIntOps::URem(A, B); 982 A = T; 983 } 984 return A; 985} 986 987/// DoubleRoundToAPInt - This function convert a double value to 988/// a APInt value. 989APInt llvm::APIntOps::DoubleRoundToAPInt(double Double) { 990 union { 991 double D; 992 uint64_t I; 993 } T; 994 T.D = Double; 995 bool isNeg = T.I >> 63; 996 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 997 if (exp < 0) 998 return APInt(0); 999 uint64_t mantissa = ((T.I << 12) >> 12) | (1ULL << 52); 1000 if (exp < 52) 1001 return isNeg ? -APInt(mantissa >> (52 - exp)) : 1002 APInt(mantissa >> (52 - exp)); 1003 APInt Tmp(mantissa, exp + 1); 1004 Tmp = Tmp.Shl(exp - 52); 1005 return isNeg ? -Tmp : Tmp; 1006} 1007 1008/// RoundToDouble - This function convert this APInt to a double. 1009/// The layout for double is as following (IEEE Standard 754): 1010/// -------------------------------------- 1011/// | Sign Exponent Fraction Bias | 1012/// |-------------------------------------- | 1013/// | 1[63] 11[62-52] 52[51-00] 1023 | 1014/// -------------------------------------- 1015double APInt::RoundToDouble(bool isSigned) const { 1016 bool isNeg = isSigned ? (*this)[BitsNum-1] : false; 1017 APInt Tmp(isNeg ? -(*this) : (*this)); 1018 if (Tmp.isSingleWord()) 1019 return isSigned ? double(int64_t(Tmp.VAL)) : double(Tmp.VAL); 1020 unsigned n = Tmp.getNumWords() * 64 - Tmp.CountLeadingZeros(); 1021 if (n <= 64) 1022 return isSigned ? double(int64_t(Tmp.pVal[0])) : double(Tmp.pVal[0]); 1023 // Exponent when normalized to have decimal point directly after 1024 // leading one. This is stored excess 1023 in the exponent bit field. 1025 uint64_t exp = n - 1; 1026 1027 // Gross overflow. 1028 assert(exp <= 1023 && "Infinity value!"); 1029 1030 // Number of bits in mantissa including the leading one 1031 // equals to 53. 1032 uint64_t mantissa; 1033 if (n % 64 >= 53) 1034 mantissa = Tmp.pVal[whichWord(n - 1)] >> (n % 64 - 53); 1035 else 1036 mantissa = (Tmp.pVal[whichWord(n - 1)] << (53 - n % 64)) | 1037 (Tmp.pVal[whichWord(n - 1) - 1] >> (11 + n % 64)); 1038 // The leading bit of mantissa is implicit, so get rid of it. 1039 mantissa &= ~(1ULL << 52); 1040 uint64_t sign = isNeg ? (1ULL << 63) : 0; 1041 exp += 1023; 1042 union { 1043 double D; 1044 uint64_t I; 1045 } T; 1046 T.I = sign | (exp << 52) | mantissa; 1047 return T.D; 1048} 1049 1050/// Arithmetic right-shift this APInt by shiftAmt. 1051/// @brief Arithmetic right-shift function. 1052APInt APInt::AShr(unsigned shiftAmt) const { 1053 APInt API(*this); 1054 if (API.isSingleWord()) 1055 API.VAL = (((int64_t(API.VAL) << (64 - API.BitsNum)) >> (64 - API.BitsNum)) 1056 >> shiftAmt) & (~uint64_t(0UL) >> (64 - API.BitsNum)); 1057 else { 1058 if (shiftAmt >= API.BitsNum) { 1059 memset(API.pVal, API[API.BitsNum-1] ? 1 : 0, (API.getNumWords()-1) * 8); 1060 API.pVal[API.getNumWords() - 1] = ~uint64_t(0UL) >> 1061 (64 - API.BitsNum % 64); 1062 } else { 1063 unsigned i = 0; 1064 for (; i < API.BitsNum - shiftAmt; ++i) 1065 if (API[i+shiftAmt]) 1066 API.set(i); 1067 else 1068 API.clear(i); 1069 for (; i < API.BitsNum; ++i) 1070 if (API[API.BitsNum-1]) 1071 API.set(i); 1072 else API.clear(i); 1073 } 1074 } 1075 return API; 1076} 1077 1078/// Logical right-shift this APInt by shiftAmt. 1079/// @brief Logical right-shift function. 1080APInt APInt::LShr(unsigned shiftAmt) const { 1081 APInt API(*this); 1082 if (API.isSingleWord()) 1083 API.VAL >>= shiftAmt; 1084 else { 1085 if (shiftAmt >= API.BitsNum) 1086 memset(API.pVal, 0, API.getNumWords() * 8); 1087 unsigned i = 0; 1088 for (i = 0; i < API.BitsNum - shiftAmt; ++i) 1089 if (API[i+shiftAmt]) API.set(i); 1090 else API.clear(i); 1091 for (; i < API.BitsNum; ++i) 1092 API.clear(i); 1093 } 1094 return API; 1095} 1096 1097/// Left-shift this APInt by shiftAmt. 1098/// @brief Left-shift function. 1099APInt APInt::Shl(unsigned shiftAmt) const { 1100 APInt API(*this); 1101 if (API.isSingleWord()) 1102 API.VAL <<= shiftAmt; 1103 else if (shiftAmt >= API.BitsNum) 1104 memset(API.pVal, 0, API.getNumWords() * 8); 1105 else { 1106 if (unsigned offset = shiftAmt / 64) { 1107 for (unsigned i = API.getNumWords() - 1; i > offset - 1; --i) 1108 API.pVal[i] = API.pVal[i-offset]; 1109 memset(API.pVal, 0, offset * 8); 1110 } 1111 shiftAmt %= 64; 1112 unsigned i; 1113 for (i = API.getNumWords() - 1; i > 0; --i) 1114 API.pVal[i] = (API.pVal[i] << shiftAmt) | 1115 (API.pVal[i-1] >> (64-shiftAmt)); 1116 API.pVal[i] <<= shiftAmt; 1117 } 1118 API.TruncToBits(); 1119 return API; 1120} 1121 1122/// Unsigned divide this APInt by APInt RHS. 1123/// @brief Unsigned division function for APInt. 1124APInt APInt::UDiv(const APInt& RHS) const { 1125 APInt API(*this); 1126 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1127 RHS.CountLeadingZeros(); 1128 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1129 assert(ylen && "Divided by zero???"); 1130 if (API.isSingleWord()) { 1131 API.VAL = RHS.isSingleWord() ? (API.VAL / RHS.VAL) : 1132 (ylen > 1 ? 0 : API.VAL / RHS.pVal[0]); 1133 } else { 1134 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1135 API.CountLeadingZeros(); 1136 unsigned xlen = !first2 ? 0 : APInt::whichWord(first2 - 1) + 1; 1137 if (!xlen) 1138 return API; 1139 else if (xlen < ylen || API < RHS) 1140 memset(API.pVal, 0, API.getNumWords() * 8); 1141 else if (API == RHS) { 1142 memset(API.pVal, 0, API.getNumWords() * 8); 1143 API.pVal[0] = 1; 1144 } else if (xlen == 1) 1145 API.pVal[0] /= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1146 else { 1147 APInt X(0, (xlen+1)*64), Y(0, ylen*64); 1148 if (unsigned nshift = 63 - (first - 1) % 64) { 1149 Y = APIntOps::Shl(RHS, nshift); 1150 X = APIntOps::Shl(API, nshift); 1151 ++xlen; 1152 } 1153 div((unsigned*)X.pVal, xlen*2-1, 1154 (unsigned*)(Y.isSingleWord() ? &Y.VAL : Y.pVal), ylen*2); 1155 memset(API.pVal, 0, API.getNumWords() * 8); 1156 memcpy(API.pVal, X.pVal + ylen, (xlen - ylen) * 8); 1157 } 1158 } 1159 return API; 1160} 1161 1162/// Unsigned remainder operation on APInt. 1163/// @brief Function for unsigned remainder operation. 1164APInt APInt::URem(const APInt& RHS) const { 1165 APInt API(*this); 1166 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1167 RHS.CountLeadingZeros(); 1168 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1169 assert(ylen && "Performing remainder operation by zero ???"); 1170 if (API.isSingleWord()) { 1171 API.VAL = RHS.isSingleWord() ? (API.VAL % RHS.VAL) : 1172 (ylen > 1 ? API.VAL : API.VAL % RHS.pVal[0]); 1173 } else { 1174 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1175 API.CountLeadingZeros(); 1176 unsigned xlen = !first2 ? 0 : API.whichWord(first2 - 1) + 1; 1177 if (!xlen || xlen < ylen || API < RHS) 1178 return API; 1179 else if (API == RHS) 1180 memset(API.pVal, 0, API.getNumWords() * 8); 1181 else if (xlen == 1) 1182 API.pVal[0] %= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1183 else { 1184 APInt X(0, (xlen+1)*64), Y(0, ylen*64); 1185 unsigned nshift = 63 - (first - 1) % 64; 1186 if (nshift) { 1187 APIntOps::Shl(Y, nshift); 1188 APIntOps::Shl(X, nshift); 1189 } 1190 div((unsigned*)X.pVal, xlen*2-1, 1191 (unsigned*)(Y.isSingleWord() ? &Y.VAL : Y.pVal), ylen*2); 1192 memset(API.pVal, 0, API.getNumWords() * 8); 1193 for (unsigned i = 0; i < ylen-1; ++i) 1194 API.pVal[i] = (X.pVal[i] >> nshift) | (X.pVal[i+1] << (64 - nshift)); 1195 API.pVal[ylen-1] = X.pVal[ylen-1] >> nshift; 1196 } 1197 } 1198 return API; 1199} 1200