APInt.cpp revision 879dfe1c9c563d05bc210bde6ac948f6b2980206
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 14. 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 = -1ULL; 759 else 760 for (unsigned i = 0; i < getNumWords(); ++i) 761 pVal[i] = -1ULL; 762 return *this; 763} 764 765/// Set the given bit to 0 whose position is given as "bitPosition". 766/// @brief Set a given bit to 0. 767APInt& APInt::clear(unsigned bitPosition) { 768 if (isSingleWord()) VAL &= ~maskBit(bitPosition); 769 else pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 770 return *this; 771} 772 773/// @brief Set every bit to 0. 774APInt& APInt::clear() { 775 if (isSingleWord()) VAL = 0; 776 else 777 memset(pVal, 0, getNumWords() * 8); 778 return *this; 779} 780 781/// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on 782/// this APInt. 783APInt APInt::operator~() const { 784 APInt API(*this); 785 API.flip(); 786 return API; 787} 788 789/// @brief Toggle every bit to its opposite value. 790APInt& APInt::flip() { 791 if (isSingleWord()) VAL = (~(VAL << (64 - BitsNum))) >> (64 - BitsNum); 792 else { 793 unsigned i = 0; 794 for (; i < getNumWords() - 1; ++i) 795 pVal[i] = ~pVal[i]; 796 unsigned offset = 64 - (BitsNum - 64 * (i - 1)); 797 pVal[i] = (~(pVal[i] << offset)) >> offset; 798 } 799 return *this; 800} 801 802/// Toggle a given bit to its opposite value whose position is given 803/// as "bitPosition". 804/// @brief Toggles a given bit to its opposite value. 805APInt& APInt::flip(unsigned bitPosition) { 806 assert(bitPosition < BitsNum && "Out of the bit-width range!"); 807 if ((*this)[bitPosition]) clear(bitPosition); 808 else set(bitPosition); 809 return *this; 810} 811 812/// to_string - This function translates the APInt into a string. 813std::string APInt::to_string(uint8_t radix) const { 814 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 815 "Radix should be 2, 8, 10, or 16!"); 816 static const char *digits[] = { 817 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F" 818 }; 819 std::string result; 820 unsigned bits_used = getNumWords() * 64 - CountLeadingZeros(); 821 if (isSingleWord()) { 822 char buf[65]; 823 const char *format = (radix == 10 ? "%llu" : 824 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0))); 825 if (format) { 826 sprintf(buf, format, VAL); 827 } else { 828 memset(buf, 0, 65); 829 uint64_t v = VAL; 830 while (bits_used) { 831 unsigned bit = v & 1; 832 bits_used--; 833 buf[bits_used] = digits[bit][0]; 834 v >>=1; 835 } 836 } 837 result = buf; 838 return result; 839 } 840 841 APInt tmp(*this); 842 APInt divisor(radix,64); 843 if (tmp == 0) 844 result = "0"; 845 else while (tmp != 0) { 846 APInt APdigit = APIntOps::URem(tmp,divisor); 847 unsigned digit = APdigit.getValue(); 848 assert(digit < radix && "URem failed"); 849 result.insert(0,digits[digit]); 850 tmp = APIntOps::UDiv(tmp, divisor); 851 } 852 853 return result; 854} 855 856/// getMaxValue - This function returns the largest value 857/// for an APInt of the specified bit-width and if isSign == true, 858/// it should be largest signed value, otherwise unsigned value. 859APInt APInt::getMaxValue(unsigned numBits, bool isSign) { 860 APInt APIVal(numBits, 1); 861 APIVal.set(); 862 return isSign ? APIVal.clear(numBits) : APIVal; 863} 864 865/// getMinValue - This function returns the smallest value for 866/// an APInt of the given bit-width and if isSign == true, 867/// it should be smallest signed value, otherwise zero. 868APInt APInt::getMinValue(unsigned numBits, bool isSign) { 869 APInt APIVal(0, numBits); 870 return isSign ? APIVal : APIVal.set(numBits); 871} 872 873/// getAllOnesValue - This function returns an all-ones value for 874/// an APInt of the specified bit-width. 875APInt APInt::getAllOnesValue(unsigned numBits) { 876 return getMaxValue(numBits, false); 877} 878 879/// getNullValue - This function creates an '0' value for an 880/// APInt of the specified bit-width. 881APInt APInt::getNullValue(unsigned numBits) { 882 return getMinValue(numBits, true); 883} 884 885/// HiBits - This function returns the high "numBits" bits of this APInt. 886APInt APInt::HiBits(unsigned numBits) const { 887 return APIntOps::LShr(*this, BitsNum - numBits); 888} 889 890/// LoBits - This function returns the low "numBits" bits of this APInt. 891APInt APInt::LoBits(unsigned numBits) const { 892 return APIntOps::LShr(APIntOps::Shl(*this, BitsNum - numBits), 893 BitsNum - numBits); 894} 895 896/// CountLeadingZeros - This function is a APInt version corresponding to 897/// llvm/include/llvm/Support/MathExtras.h's function 898/// CountLeadingZeros_{32, 64}. It performs platform optimal form of counting 899/// the number of zeros from the most significant bit to the first one bit. 900/// @returns numWord() * 64 if the value is zero. 901unsigned APInt::CountLeadingZeros() const { 902 if (isSingleWord()) 903 return CountLeadingZeros_64(VAL); 904 unsigned Count = 0; 905 for (int i = getNumWords() - 1; i >= 0; --i) { 906 unsigned tmp = CountLeadingZeros_64(pVal[i]); 907 Count += tmp; 908 if (tmp != 64) 909 break; 910 } 911 return Count; 912} 913 914/// CountTrailingZero - This function is a APInt version corresponding to 915/// llvm/include/llvm/Support/MathExtras.h's function 916/// CountTrailingZeros_{32, 64}. It performs platform optimal form of counting 917/// the number of zeros from the least significant bit to the first one bit. 918/// @returns numWord() * 64 if the value is zero. 919unsigned APInt::CountTrailingZeros() const { 920 if (isSingleWord()) 921 return CountTrailingZeros_64(~VAL & (VAL - 1)); 922 APInt Tmp = ~(*this) & ((*this) - 1); 923 return getNumWords() * 64 - Tmp.CountLeadingZeros(); 924} 925 926/// CountPopulation - This function is a APInt version corresponding to 927/// llvm/include/llvm/Support/MathExtras.h's function 928/// CountPopulation_{32, 64}. It counts the number of set bits in a value. 929/// @returns 0 if the value is zero. 930unsigned APInt::CountPopulation() const { 931 if (isSingleWord()) 932 return CountPopulation_64(VAL); 933 unsigned Count = 0; 934 for (unsigned i = 0; i < getNumWords(); ++i) 935 Count += CountPopulation_64(pVal[i]); 936 return Count; 937} 938 939 940/// ByteSwap - This function returns a byte-swapped representation of the 941/// this APInt. 942APInt APInt::ByteSwap() const { 943 if (BitsNum <= 32) 944 return APInt(BitsNum, ByteSwap_32(unsigned(VAL))); 945 else if (BitsNum <= 64) 946 return APInt(BitsNum, ByteSwap_64(VAL)); 947 else 948 return *this; 949} 950 951/// GreatestCommonDivisor - This function returns the greatest common 952/// divisor of the two APInt values using Enclid's algorithm. 953APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 954 const APInt& API2) { 955 APInt A = API1, B = API2; 956 while (!!B) { 957 APInt T = B; 958 B = APIntOps::URem(A, B); 959 A = T; 960 } 961 return A; 962} 963 964/// DoubleRoundToAPInt - This function convert a double value to 965/// a APInt value. 966APInt llvm::APIntOps::DoubleRoundToAPInt(double Double) { 967 union { 968 double D; 969 uint64_t I; 970 } T; 971 T.D = Double; 972 bool isNeg = T.I >> 63; 973 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 974 if (exp < 0) 975 return APInt(0); 976 uint64_t mantissa = ((T.I << 12) >> 12) | (1ULL << 52); 977 if (exp < 52) 978 return isNeg ? -APInt(mantissa >> (52 - exp)) : 979 APInt(mantissa >> (52 - exp)); 980 APInt Tmp(mantissa, exp + 1); 981 Tmp = Tmp.Shl(exp - 52); 982 return isNeg ? -Tmp : Tmp; 983} 984 985/// RoundToDouble - This function convert this APInt to a double. 986/// The layout for double is as following (IEEE Standard 754): 987/// -------------------------------------- 988/// | Sign Exponent Fraction Bias | 989/// |-------------------------------------- | 990/// | 1[63] 11[62-52] 52[51-00] 1023 | 991/// -------------------------------------- 992double APInt::RoundToDouble(bool isSigned) const { 993 bool isNeg = isSigned ? (*this)[BitsNum-1] : false; 994 APInt Tmp(isNeg ? -(*this) : (*this)); 995 if (Tmp.isSingleWord()) 996 return isSigned ? double(int64_t(Tmp.VAL)) : double(Tmp.VAL); 997 unsigned n = Tmp.getNumWords() * 64 - Tmp.CountLeadingZeros(); 998 if (n <= 64) 999 return isSigned ? double(int64_t(Tmp.pVal[0])) : double(Tmp.pVal[0]); 1000 // Exponent when normalized to have decimal point directly after 1001 // leading one. This is stored excess 1023 in the exponent bit field. 1002 uint64_t exp = n - 1; 1003 1004 // Gross overflow. 1005 assert(exp <= 1023 && "Infinity value!"); 1006 1007 // Number of bits in mantissa including the leading one 1008 // equals to 53. 1009 uint64_t mantissa; 1010 if (n % 64 >= 53) 1011 mantissa = Tmp.pVal[whichWord(n - 1)] >> (n % 64 - 53); 1012 else 1013 mantissa = (Tmp.pVal[whichWord(n - 1)] << (53 - n % 64)) | 1014 (Tmp.pVal[whichWord(n - 1) - 1] >> (11 + n % 64)); 1015 // The leading bit of mantissa is implicit, so get rid of it. 1016 mantissa &= ~(1ULL << 52); 1017 uint64_t sign = isNeg ? (1ULL << 63) : 0; 1018 exp += 1023; 1019 union { 1020 double D; 1021 uint64_t I; 1022 } T; 1023 T.I = sign | (exp << 52) | mantissa; 1024 return T.D; 1025} 1026 1027/// Arithmetic right-shift this APInt by shiftAmt. 1028/// @brief Arithmetic right-shift function. 1029APInt APInt::AShr(unsigned shiftAmt) const { 1030 APInt API(*this); 1031 if (API.isSingleWord()) 1032 API.VAL = (((int64_t(API.VAL) << (64 - API.BitsNum)) >> (64 - API.BitsNum)) 1033 >> shiftAmt) & (~uint64_t(0UL) >> (64 - API.BitsNum)); 1034 else { 1035 if (shiftAmt >= API.BitsNum) { 1036 memset(API.pVal, API[API.BitsNum-1] ? 1 : 0, (API.getNumWords()-1) * 8); 1037 API.pVal[API.getNumWords() - 1] = ~uint64_t(0UL) >> 1038 (64 - API.BitsNum % 64); 1039 } else { 1040 unsigned i = 0; 1041 for (; i < API.BitsNum - shiftAmt; ++i) 1042 if (API[i+shiftAmt]) 1043 API.set(i); 1044 else 1045 API.clear(i); 1046 for (; i < API.BitsNum; ++i) 1047 API[API.BitsNum-1] ? API.set(i) : API.clear(i); 1048 } 1049 } 1050 return API; 1051} 1052 1053/// Logical right-shift this APInt by shiftAmt. 1054/// @brief Logical right-shift function. 1055APInt APInt::LShr(unsigned shiftAmt) const { 1056 APInt API(*this); 1057 if (API.isSingleWord()) 1058 API.VAL >>= shiftAmt; 1059 else { 1060 if (shiftAmt >= API.BitsNum) 1061 memset(API.pVal, 0, API.getNumWords() * 8); 1062 unsigned i = 0; 1063 for (i = 0; i < API.BitsNum - shiftAmt; ++i) 1064 if (API[i+shiftAmt]) API.set(i); 1065 else API.clear(i); 1066 for (; i < API.BitsNum; ++i) 1067 API.clear(i); 1068 } 1069 return API; 1070} 1071 1072/// Left-shift this APInt by shiftAmt. 1073/// @brief Left-shift function. 1074APInt APInt::Shl(unsigned shiftAmt) const { 1075 APInt API(*this); 1076 if (API.isSingleWord()) 1077 API.VAL <<= shiftAmt; 1078 else if (shiftAmt >= API.BitsNum) 1079 memset(API.pVal, 0, API.getNumWords() * 8); 1080 else { 1081 if (unsigned offset = shiftAmt / 64) { 1082 for (unsigned i = API.getNumWords() - 1; i > offset - 1; --i) 1083 API.pVal[i] = API.pVal[i-offset]; 1084 memset(API.pVal, 0, offset * 8); 1085 } 1086 shiftAmt %= 64; 1087 unsigned i; 1088 for (i = API.getNumWords() - 1; i > 0; --i) 1089 API.pVal[i] = (API.pVal[i] << shiftAmt) | 1090 (API.pVal[i-1] >> (64-shiftAmt)); 1091 API.pVal[i] <<= shiftAmt; 1092 } 1093 return API; 1094} 1095 1096/// Unsigned divide this APInt by APInt RHS. 1097/// @brief Unsigned division function for APInt. 1098APInt APInt::UDiv(const APInt& RHS) const { 1099 APInt API(*this); 1100 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1101 RHS.CountLeadingZeros(); 1102 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1103 assert(ylen && "Divided by zero???"); 1104 if (API.isSingleWord()) { 1105 API.VAL = RHS.isSingleWord() ? (API.VAL / RHS.VAL) : 1106 (ylen > 1 ? 0 : API.VAL / RHS.pVal[0]); 1107 } else { 1108 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1109 API.CountLeadingZeros(); 1110 unsigned xlen = !first2 ? 0 : APInt::whichWord(first2 - 1) + 1; 1111 if (!xlen) 1112 return API; 1113 else if (API < RHS) 1114 memset(API.pVal, 0, API.getNumWords() * 8); 1115 else if (API == RHS) { 1116 memset(API.pVal, 0, API.getNumWords() * 8); 1117 API.pVal[0] = 1; 1118 } else if (xlen == 1) 1119 API.pVal[0] /= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1120 else { 1121 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen]; 1122 assert(xwords && ywords && "Memory Allocation Failed!"); 1123 memcpy(xwords, API.pVal, xlen * 8); 1124 xwords[xlen] = 0; 1125 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8); 1126 if (unsigned nshift = 63 - (first - 1) % 64) { 1127 lshift(ywords, 0, ywords, ylen, nshift); 1128 unsigned xlentmp = xlen; 1129 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift); 1130 } 1131 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2); 1132 memset(API.pVal, 0, API.getNumWords() * 8); 1133 memcpy(API.pVal, xwords + ylen, (xlen - ylen) * 8); 1134 delete[] xwords; 1135 delete[] ywords; 1136 } 1137 } 1138 return API; 1139} 1140 1141/// Unsigned remainder operation on APInt. 1142/// @brief Function for unsigned remainder operation. 1143APInt APInt::URem(const APInt& RHS) const { 1144 APInt API(*this); 1145 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1146 RHS.CountLeadingZeros(); 1147 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1148 assert(ylen && "Performing remainder operation by zero ???"); 1149 if (API.isSingleWord()) { 1150 API.VAL = RHS.isSingleWord() ? (API.VAL % RHS.VAL) : 1151 (ylen > 1 ? API.VAL : API.VAL % RHS.pVal[0]); 1152 } else { 1153 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1154 API.CountLeadingZeros(); 1155 unsigned xlen = !first2 ? 0 : API.whichWord(first2 - 1) + 1; 1156 if (!xlen || API < RHS) 1157 return API; 1158 else if (API == RHS) 1159 memset(API.pVal, 0, API.getNumWords() * 8); 1160 else if (xlen == 1) 1161 API.pVal[0] %= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1162 else { 1163 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen]; 1164 assert(xwords && ywords && "Memory Allocation Failed!"); 1165 memcpy(xwords, API.pVal, xlen * 8); 1166 xwords[xlen] = 0; 1167 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8); 1168 unsigned nshift = 63 - (first - 1) % 64; 1169 if (nshift) { 1170 lshift(ywords, 0, ywords, ylen, nshift); 1171 unsigned xlentmp = xlen; 1172 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift); 1173 } 1174 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2); 1175 memset(API.pVal, 0, API.getNumWords() * 8); 1176 for (unsigned i = 0; i < ylen-1; ++i) 1177 API.pVal[i] = (xwords[i] >> nshift) | (xwords[i+1] << (64 - nshift)); 1178 API.pVal[ylen-1] = xwords[ylen-1] >> nshift; 1179 delete[] xwords; 1180 delete[] ywords; 1181 } 1182 } 1183 return API; 1184} 1185