1 /* Operations with very long integers. 2 Copyright (C) 2012-2024 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck (at) naturalbridge.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3, or (at your option) any 10 later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "selftest.h" 27 28 29 #define HOST_BITS_PER_HALF_WIDE_INT 32 30 #if HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_LONG 31 # define HOST_HALF_WIDE_INT long 32 #elif HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_INT 33 # define HOST_HALF_WIDE_INT int 34 #else 35 #error Please add support for HOST_HALF_WIDE_INT 36 #endif 37 38 #define W_TYPE_SIZE HOST_BITS_PER_WIDE_INT 39 /* Do not include longlong.h when compiler is clang-based. See PR61146. */ 40 #if GCC_VERSION >= 3000 && (W_TYPE_SIZE == 32 || defined (__SIZEOF_INT128__)) && !defined(__clang__) 41 typedef unsigned HOST_HALF_WIDE_INT UHWtype; 42 typedef unsigned HOST_WIDE_INT UWtype; 43 typedef unsigned int UQItype __attribute__ ((mode (QI))); 44 typedef unsigned int USItype __attribute__ ((mode (SI))); 45 typedef unsigned int UDItype __attribute__ ((mode (DI))); 46 #if W_TYPE_SIZE == 32 47 typedef unsigned int UDWtype __attribute__ ((mode (DI))); 48 #else 49 typedef unsigned int UDWtype __attribute__ ((mode (TI))); 50 #endif 51 #include "longlong.h" 52 #endif 53 54 static const HOST_WIDE_INT zeros[1] = {}; 55 56 /* 57 * Internal utilities. 58 */ 59 60 /* Quantities to deal with values that hold half of a wide int. Used 61 in multiply and divide. */ 62 #define HALF_INT_MASK ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1) 63 64 #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT) 65 #define BLOCKS_NEEDED(PREC) (PREC ? CEIL (PREC, HOST_BITS_PER_WIDE_INT) : 1) 66 #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0) 67 68 /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1 69 based on the top existing bit of VAL. */ 70 71 static unsigned HOST_WIDE_INT 72 safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i) 73 { 74 return i < len ? val[i] : val[len - 1] < 0 ? HOST_WIDE_INT_M1 : 0; 75 } 76 77 /* Convert the integer in VAL to canonical form, returning its new length. 78 LEN is the number of blocks currently in VAL and PRECISION is the number 79 of bits in the integer it represents. 80 81 This function only changes the representation, not the value. */ 82 static unsigned int 83 canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision) 84 { 85 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 86 HOST_WIDE_INT top; 87 int i; 88 89 if (len > blocks_needed) 90 len = blocks_needed; 91 92 if (len == 1) 93 return len; 94 95 top = val[len - 1]; 96 if (len * HOST_BITS_PER_WIDE_INT > precision) 97 val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT); 98 if (top != 0 && top != HOST_WIDE_INT_M1) 99 return len; 100 101 /* At this point we know that the top is either 0 or -1. Find the 102 first block that is not a copy of this. */ 103 for (i = len - 2; i >= 0; i--) 104 { 105 HOST_WIDE_INT x = val[i]; 106 if (x != top) 107 { 108 if (SIGN_MASK (x) == top) 109 return i + 1; 110 111 /* We need an extra block because the top bit block i does 112 not match the extension. */ 113 return i + 2; 114 } 115 } 116 117 /* The number is 0 or -1. */ 118 return 1; 119 } 120 121 /* VAL[0] is the unsigned result of an operation. Canonize it by adding 122 another 0 block if needed, and return number of blocks needed. */ 123 124 static inline unsigned int 125 canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision) 126 { 127 if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT) 128 { 129 val[1] = 0; 130 return 2; 131 } 132 return 1; 133 } 134 135 /* 136 * Conversion routines in and out of wide_int. 137 */ 138 139 /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the 140 result for an integer with precision PRECISION. Return the length 141 of VAL (after any canonization). */ 142 unsigned int 143 wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 144 unsigned int xlen, unsigned int precision, bool need_canon) 145 { 146 for (unsigned i = 0; i < xlen; i++) 147 val[i] = xval[i]; 148 return need_canon ? canonize (val, xlen, precision) : xlen; 149 } 150 151 /* Construct a wide int from a buffer of length LEN. BUFFER will be 152 read according to byte endianness and word endianness of the target. 153 Only the lower BUFFER_LEN bytes of the result are set; the remaining 154 high bytes are cleared. */ 155 wide_int 156 wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len) 157 { 158 unsigned int precision = buffer_len * BITS_PER_UNIT; 159 wide_int result = wide_int::create (precision); 160 unsigned int words = buffer_len / UNITS_PER_WORD; 161 162 /* We have to clear all the bits ourself, as we merely or in values 163 below. */ 164 unsigned int len = BLOCKS_NEEDED (precision); 165 HOST_WIDE_INT *val = result.write_val (0); 166 for (unsigned int i = 0; i < len; ++i) 167 val[i] = 0; 168 169 for (unsigned int byte = 0; byte < buffer_len; byte++) 170 { 171 unsigned int offset; 172 unsigned int index; 173 unsigned int bitpos = byte * BITS_PER_UNIT; 174 unsigned HOST_WIDE_INT value; 175 176 if (buffer_len > UNITS_PER_WORD) 177 { 178 unsigned int word = byte / UNITS_PER_WORD; 179 180 if (WORDS_BIG_ENDIAN) 181 word = (words - 1) - word; 182 183 offset = word * UNITS_PER_WORD; 184 185 if (BYTES_BIG_ENDIAN) 186 offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD); 187 else 188 offset += byte % UNITS_PER_WORD; 189 } 190 else 191 offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte; 192 193 value = (unsigned HOST_WIDE_INT) buffer[offset]; 194 195 index = bitpos / HOST_BITS_PER_WIDE_INT; 196 val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT); 197 } 198 199 result.set_len (canonize (val, len, precision)); 200 201 return result; 202 } 203 204 /* Sets RESULT from X, the sign is taken according to SGN. */ 205 void 206 wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn) 207 { 208 int len = x.get_len (); 209 const HOST_WIDE_INT *v = x.get_val (); 210 int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision (); 211 212 if (wi::neg_p (x, sgn)) 213 { 214 /* We use ones complement to avoid -x80..0 edge case that - 215 won't work on. */ 216 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len); 217 for (int i = 0; i < len; i++) 218 t[i] = ~v[i]; 219 if (excess > 0) 220 t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess; 221 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t); 222 mpz_com (result, result); 223 } 224 else if (excess > 0) 225 { 226 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len); 227 for (int i = 0; i < len - 1; i++) 228 t[i] = v[i]; 229 t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess; 230 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t); 231 } 232 else if (excess < 0 && wi::neg_p (x)) 233 { 234 int extra = CEIL (-excess, HOST_BITS_PER_WIDE_INT); 235 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len + extra); 236 for (int i = 0; i < len; i++) 237 t[i] = v[i]; 238 for (int i = 0; i < extra; i++) 239 t[len + i] = -1; 240 excess = (-excess) % HOST_BITS_PER_WIDE_INT; 241 if (excess) 242 t[len + extra - 1] = (HOST_WIDE_INT_1U << excess) - 1; 243 mpz_import (result, len + extra, -1, sizeof (HOST_WIDE_INT), 0, 0, t); 244 } 245 else 246 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v); 247 } 248 249 /* Returns X converted to TYPE. If WRAP is true, then out-of-range 250 values of VAL will be wrapped; otherwise, they will be set to the 251 appropriate minimum or maximum TYPE bound. */ 252 wide_int 253 wi::from_mpz (const_tree type, mpz_t x, bool wrap) 254 { 255 size_t count, numb; 256 unsigned int prec = TYPE_PRECISION (type); 257 wide_int res = wide_int::create (prec); 258 259 if (!wrap) 260 { 261 mpz_t min, max; 262 263 mpz_init (min); 264 mpz_init (max); 265 get_type_static_bounds (type, min, max); 266 267 if (mpz_cmp (x, min) < 0) 268 mpz_set (x, min); 269 else if (mpz_cmp (x, max) > 0) 270 mpz_set (x, max); 271 272 mpz_clear (min); 273 mpz_clear (max); 274 } 275 276 /* Determine the number of unsigned HOST_WIDE_INTs that are required 277 for representing the absolute value. The code to calculate count is 278 extracted from the GMP manual, section "Integer Import and Export": 279 http://gmplib.org/manual/Integer-Import-and-Export.html */ 280 numb = CHAR_BIT * sizeof (HOST_WIDE_INT); 281 count = CEIL (mpz_sizeinbase (x, 2), numb); 282 HOST_WIDE_INT *val = res.write_val (0); 283 /* Read the absolute value. 284 285 Write directly to the wide_int storage if possible, otherwise leave 286 GMP to allocate the memory for us. It might be slightly more efficient 287 to use mpz_tdiv_r_2exp for the latter case, but the situation is 288 pathological and it seems safer to operate on the original mpz value 289 in all cases. */ 290 void *valres = mpz_export (count <= WIDE_INT_MAX_INL_ELTS ? val : 0, 291 &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x); 292 if (count < 1) 293 { 294 val[0] = 0; 295 count = 1; 296 } 297 count = MIN (count, BLOCKS_NEEDED (prec)); 298 if (valres != val) 299 { 300 memcpy (val, valres, count * sizeof (HOST_WIDE_INT)); 301 free (valres); 302 } 303 /* Zero-extend the absolute value to PREC bits. */ 304 if (count < BLOCKS_NEEDED (prec) && val[count - 1] < 0) 305 val[count++] = 0; 306 else 307 count = canonize (val, count, prec); 308 res.set_len (count); 309 310 if (mpz_sgn (x) < 0) 311 res = -res; 312 313 return res; 314 } 315 316 /* 317 * Largest and smallest values in a mode. 318 */ 319 320 /* Return the largest SGNed number that is representable in PRECISION bits. 321 322 TODO: There is still code from the double_int era that trys to 323 make up for the fact that double int's could not represent the 324 min and max values of all types. This code should be removed 325 because the min and max values can always be represented in 326 wide_ints and int-csts. */ 327 wide_int 328 wi::max_value (unsigned int precision, signop sgn) 329 { 330 gcc_checking_assert (precision != 0); 331 if (sgn == UNSIGNED) 332 /* The unsigned max is just all ones. */ 333 return shwi (-1, precision); 334 else 335 /* The signed max is all ones except the top bit. This must be 336 explicitly represented. */ 337 return mask (precision - 1, false, precision); 338 } 339 340 /* Return the largest SGNed number that is representable in PRECISION bits. */ 341 wide_int 342 wi::min_value (unsigned int precision, signop sgn) 343 { 344 gcc_checking_assert (precision != 0); 345 if (sgn == UNSIGNED) 346 return uhwi (0, precision); 347 else 348 /* The signed min is all zeros except the top bit. This must be 349 explicitly represented. */ 350 return wi::set_bit_in_zero (precision - 1, precision); 351 } 352 353 /* 354 * Public utilities. 355 */ 356 357 /* Convert the number represented by XVAL, XLEN and XPRECISION, which has 358 signedness SGN, to an integer that has PRECISION bits. Store the blocks 359 in VAL and return the number of blocks used. 360 361 This function can handle both extension (PRECISION > XPRECISION) 362 and truncation (PRECISION < XPRECISION). */ 363 unsigned int 364 wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 365 unsigned int xlen, unsigned int xprecision, 366 unsigned int precision, signop sgn) 367 { 368 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 369 unsigned int len = blocks_needed < xlen ? blocks_needed : xlen; 370 for (unsigned i = 0; i < len; i++) 371 val[i] = xval[i]; 372 373 if (precision > xprecision) 374 { 375 unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT; 376 377 /* Expanding. */ 378 if (sgn == UNSIGNED) 379 { 380 if (small_xprecision && len == BLOCKS_NEEDED (xprecision)) 381 val[len - 1] = zext_hwi (val[len - 1], small_xprecision); 382 else if (val[len - 1] < 0) 383 { 384 while (len < BLOCKS_NEEDED (xprecision)) 385 val[len++] = -1; 386 if (small_xprecision) 387 val[len - 1] = zext_hwi (val[len - 1], small_xprecision); 388 else 389 val[len++] = 0; 390 } 391 } 392 else 393 { 394 if (small_xprecision && len == BLOCKS_NEEDED (xprecision)) 395 val[len - 1] = sext_hwi (val[len - 1], small_xprecision); 396 } 397 } 398 len = canonize (val, len, precision); 399 400 return len; 401 } 402 403 /* This function hides the fact that we cannot rely on the bits beyond 404 the precision. This issue comes up in the relational comparisions 405 where we do allow comparisons of values of different precisions. */ 406 static inline HOST_WIDE_INT 407 selt (const HOST_WIDE_INT *a, unsigned int len, 408 unsigned int blocks_needed, unsigned int small_prec, 409 unsigned int index, signop sgn) 410 { 411 HOST_WIDE_INT val; 412 if (index < len) 413 val = a[index]; 414 else if (index < blocks_needed || sgn == SIGNED) 415 /* Signed or within the precision. */ 416 val = SIGN_MASK (a[len - 1]); 417 else 418 /* Unsigned extension beyond the precision. */ 419 val = 0; 420 421 if (small_prec && index == blocks_needed - 1) 422 return (sgn == SIGNED 423 ? sext_hwi (val, small_prec) 424 : zext_hwi (val, small_prec)); 425 else 426 return val; 427 } 428 429 /* Find the highest bit represented in a wide int. This will in 430 general have the same value as the sign bit. */ 431 static inline HOST_WIDE_INT 432 top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec) 433 { 434 int excess = len * HOST_BITS_PER_WIDE_INT - prec; 435 unsigned HOST_WIDE_INT val = a[len - 1]; 436 if (excess > 0) 437 val <<= excess; 438 return val >> (HOST_BITS_PER_WIDE_INT - 1); 439 } 440 441 /* 442 * Comparisons, note that only equality is an operator. The other 443 * comparisons cannot be operators since they are inherently signed or 444 * unsigned and C++ has no such operators. 445 */ 446 447 /* Return true if OP0 == OP1. */ 448 bool 449 wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, 450 const HOST_WIDE_INT *op1, unsigned int op1len, 451 unsigned int prec) 452 { 453 int l0 = op0len - 1; 454 unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1); 455 456 if (op0len != op1len) 457 return false; 458 459 if (op0len == BLOCKS_NEEDED (prec) && small_prec) 460 { 461 /* It does not matter if we zext or sext here, we just have to 462 do both the same way. */ 463 if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec)) 464 return false; 465 l0--; 466 } 467 468 while (l0 >= 0) 469 if (op0[l0] != op1[l0]) 470 return false; 471 else 472 l0--; 473 474 return true; 475 } 476 477 /* Return true if OP0 < OP1 using signed comparisons. */ 478 bool 479 wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, 480 unsigned int precision, 481 const HOST_WIDE_INT *op1, unsigned int op1len) 482 { 483 HOST_WIDE_INT s0, s1; 484 unsigned HOST_WIDE_INT u0, u1; 485 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 486 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); 487 int l = MAX (op0len - 1, op1len - 1); 488 489 /* Only the top block is compared as signed. The rest are unsigned 490 comparisons. */ 491 s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); 492 s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); 493 if (s0 < s1) 494 return true; 495 if (s0 > s1) 496 return false; 497 498 l--; 499 while (l >= 0) 500 { 501 u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); 502 u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); 503 504 if (u0 < u1) 505 return true; 506 if (u0 > u1) 507 return false; 508 l--; 509 } 510 511 return false; 512 } 513 514 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using 515 signed compares. */ 516 int 517 wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len, 518 unsigned int precision, 519 const HOST_WIDE_INT *op1, unsigned int op1len) 520 { 521 HOST_WIDE_INT s0, s1; 522 unsigned HOST_WIDE_INT u0, u1; 523 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 524 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); 525 int l = MAX (op0len - 1, op1len - 1); 526 527 /* Only the top block is compared as signed. The rest are unsigned 528 comparisons. */ 529 s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); 530 s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); 531 if (s0 < s1) 532 return -1; 533 if (s0 > s1) 534 return 1; 535 536 l--; 537 while (l >= 0) 538 { 539 u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); 540 u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); 541 542 if (u0 < u1) 543 return -1; 544 if (u0 > u1) 545 return 1; 546 l--; 547 } 548 549 return 0; 550 } 551 552 /* Return true if OP0 < OP1 using unsigned comparisons. */ 553 bool 554 wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, 555 unsigned int precision, 556 const HOST_WIDE_INT *op1, unsigned int op1len) 557 { 558 unsigned HOST_WIDE_INT x0; 559 unsigned HOST_WIDE_INT x1; 560 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 561 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); 562 int l = MAX (op0len - 1, op1len - 1); 563 564 while (l >= 0) 565 { 566 x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED); 567 x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED); 568 if (x0 < x1) 569 return true; 570 if (x0 > x1) 571 return false; 572 l--; 573 } 574 575 return false; 576 } 577 578 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using 579 unsigned compares. */ 580 int 581 wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len, 582 unsigned int precision, 583 const HOST_WIDE_INT *op1, unsigned int op1len) 584 { 585 unsigned HOST_WIDE_INT x0; 586 unsigned HOST_WIDE_INT x1; 587 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 588 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); 589 int l = MAX (op0len - 1, op1len - 1); 590 591 while (l >= 0) 592 { 593 x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED); 594 x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED); 595 if (x0 < x1) 596 return -1; 597 if (x0 > x1) 598 return 1; 599 l--; 600 } 601 602 return 0; 603 } 604 605 /* 606 * Extension. 607 */ 608 609 /* Sign-extend the number represented by XVAL and XLEN into VAL, 610 starting at OFFSET. Return the number of blocks in VAL. Both XVAL 611 and VAL have PRECISION bits. */ 612 unsigned int 613 wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 614 unsigned int xlen, unsigned int precision, unsigned int offset) 615 { 616 unsigned int len = offset / HOST_BITS_PER_WIDE_INT; 617 /* Extending beyond the precision is a no-op. If we have only stored 618 OFFSET bits or fewer, the rest are already signs. */ 619 if (offset >= precision || len >= xlen) 620 { 621 for (unsigned i = 0; i < xlen; ++i) 622 val[i] = xval[i]; 623 return xlen; 624 } 625 unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT; 626 for (unsigned int i = 0; i < len; i++) 627 val[i] = xval[i]; 628 if (suboffset > 0) 629 { 630 val[len] = sext_hwi (xval[len], suboffset); 631 len += 1; 632 } 633 return canonize (val, len, precision); 634 } 635 636 /* Zero-extend the number represented by XVAL and XLEN into VAL, 637 starting at OFFSET. Return the number of blocks in VAL. Both XVAL 638 and VAL have PRECISION bits. */ 639 unsigned int 640 wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 641 unsigned int xlen, unsigned int precision, unsigned int offset) 642 { 643 unsigned int len = offset / HOST_BITS_PER_WIDE_INT; 644 /* Extending beyond the precision is a no-op. If we have only stored 645 OFFSET bits or fewer, and the upper stored bit is zero, then there 646 is nothing to do. */ 647 if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0)) 648 { 649 for (unsigned i = 0; i < xlen; ++i) 650 val[i] = xval[i]; 651 return xlen; 652 } 653 unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT; 654 for (unsigned int i = 0; i < len; i++) 655 val[i] = i < xlen ? xval[i] : -1; 656 if (suboffset > 0) 657 val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset); 658 else 659 val[len] = 0; 660 return canonize (val, len + 1, precision); 661 } 662 663 /* 664 * Masking, inserting, shifting, rotating. 665 */ 666 667 /* Insert WIDTH bits from Y into X starting at START. */ 668 wide_int 669 wi::insert (const wide_int &x, const wide_int &y, unsigned int start, 670 unsigned int width) 671 { 672 wide_int result; 673 wide_int mask; 674 wide_int tmp; 675 676 unsigned int precision = x.get_precision (); 677 if (start >= precision) 678 return x; 679 680 gcc_checking_assert (precision >= width); 681 682 if (start + width >= precision) 683 width = precision - start; 684 685 mask = wi::shifted_mask (start, width, false, precision); 686 tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start); 687 result = tmp & mask; 688 689 tmp = wi::bit_and_not (x, mask); 690 result = result | tmp; 691 692 return result; 693 } 694 695 /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT. 696 Return the number of blocks in VAL. Both XVAL and VAL have PRECISION 697 bits. */ 698 unsigned int 699 wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 700 unsigned int xlen, unsigned int precision, unsigned int bit) 701 { 702 unsigned int block = bit / HOST_BITS_PER_WIDE_INT; 703 unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT; 704 705 if (block + 1 >= xlen) 706 { 707 /* The operation either affects the last current block or needs 708 a new block. */ 709 unsigned int len = block + 1; 710 for (unsigned int i = 0; i < len; i++) 711 val[i] = safe_uhwi (xval, xlen, i); 712 val[block] |= HOST_WIDE_INT_1U << subbit; 713 714 /* If the bit we just set is at the msb of the block, make sure 715 that any higher bits are zeros. */ 716 if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1) 717 { 718 val[len++] = 0; 719 return len; 720 } 721 return canonize (val, len, precision); 722 } 723 else 724 { 725 for (unsigned int i = 0; i < xlen; i++) 726 val[i] = xval[i]; 727 val[block] |= HOST_WIDE_INT_1U << subbit; 728 return canonize (val, xlen, precision); 729 } 730 } 731 732 /* Byte swap the integer represented by XVAL and XLEN into VAL. Return 733 the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */ 734 unsigned int 735 wi::bswap_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 736 unsigned int xlen, unsigned int precision) 737 { 738 unsigned int s, len = BLOCKS_NEEDED (precision); 739 740 /* This is not a well defined operation if the precision is not a 741 multiple of 8. */ 742 gcc_assert ((precision & 0x7) == 0); 743 744 memset (val, 0, sizeof (unsigned HOST_WIDE_INT) * len); 745 746 /* Only swap the bytes that are not the padding. */ 747 for (s = 0; s < precision; s += 8) 748 { 749 unsigned int d = precision - s - 8; 750 unsigned HOST_WIDE_INT byte; 751 752 unsigned int block = s / HOST_BITS_PER_WIDE_INT; 753 unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1); 754 755 byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff; 756 757 block = d / HOST_BITS_PER_WIDE_INT; 758 offset = d & (HOST_BITS_PER_WIDE_INT - 1); 759 760 val[block] |= byte << offset; 761 } 762 763 return canonize (val, len, precision); 764 } 765 766 /* Bitreverse the integer represented by XVAL and LEN into VAL. Return 767 the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */ 768 unsigned int 769 wi::bitreverse_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 770 unsigned int len, unsigned int precision) 771 { 772 unsigned int i, s; 773 774 for (i = 0; i < len; i++) 775 val[i] = 0; 776 777 for (s = 0; s < precision; s++) 778 { 779 unsigned int block = s / HOST_BITS_PER_WIDE_INT; 780 unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1); 781 if (((safe_uhwi (xval, len, block) >> offset) & 1) != 0) 782 { 783 unsigned int d = (precision - 1) - s; 784 block = d / HOST_BITS_PER_WIDE_INT; 785 offset = d & (HOST_BITS_PER_WIDE_INT - 1); 786 val[block] |= HOST_WIDE_INT_1U << offset; 787 } 788 } 789 790 return canonize (val, len, precision); 791 } 792 793 /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits 794 above that up to PREC are zeros. The result is inverted if NEGATE 795 is true. Return the number of blocks in VAL. */ 796 unsigned int 797 wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate, 798 unsigned int prec) 799 { 800 if (width >= prec) 801 { 802 val[0] = negate ? 0 : -1; 803 return 1; 804 } 805 else if (width == 0) 806 { 807 val[0] = negate ? -1 : 0; 808 return 1; 809 } 810 811 unsigned int i = 0; 812 while (i < width / HOST_BITS_PER_WIDE_INT) 813 val[i++] = negate ? 0 : -1; 814 815 unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1); 816 if (shift != 0) 817 { 818 HOST_WIDE_INT last = (HOST_WIDE_INT_1U << shift) - 1; 819 val[i++] = negate ? ~last : last; 820 } 821 else 822 val[i++] = negate ? -1 : 0; 823 824 return i; 825 } 826 827 /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH 828 bits are ones, and the bits above that up to PREC are zeros. The result 829 is inverted if NEGATE is true. Return the number of blocks in VAL. */ 830 unsigned int 831 wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width, 832 bool negate, unsigned int prec) 833 { 834 if (start >= prec || width == 0) 835 { 836 val[0] = negate ? -1 : 0; 837 return 1; 838 } 839 840 if (width > prec - start) 841 width = prec - start; 842 unsigned int end = start + width; 843 844 unsigned int i = 0; 845 while (i < start / HOST_BITS_PER_WIDE_INT) 846 val[i++] = negate ? -1 : 0; 847 848 unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1); 849 if (shift) 850 { 851 HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1; 852 shift += width; 853 if (shift < HOST_BITS_PER_WIDE_INT) 854 { 855 /* case 000111000 */ 856 block = (HOST_WIDE_INT_1U << shift) - block - 1; 857 val[i++] = negate ? ~block : block; 858 return i; 859 } 860 else 861 /* ...111000 */ 862 val[i++] = negate ? block : ~block; 863 } 864 865 if (end >= prec) 866 { 867 if (!shift) 868 val[i++] = negate ? 0 : -1; 869 return i; 870 } 871 872 while (i < end / HOST_BITS_PER_WIDE_INT) 873 /* 1111111 */ 874 val[i++] = negate ? 0 : -1; 875 876 shift = end & (HOST_BITS_PER_WIDE_INT - 1); 877 if (shift != 0) 878 { 879 /* 000011111 */ 880 HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1; 881 val[i++] = negate ? ~block : block; 882 } 883 else 884 val[i++] = negate ? -1 : 0; 885 886 return i; 887 } 888 889 /* 890 * logical operations. 891 */ 892 893 /* Set VAL to OP0 & OP1. Return the number of blocks used. */ 894 unsigned int 895 wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 896 unsigned int op0len, const HOST_WIDE_INT *op1, 897 unsigned int op1len, unsigned int prec) 898 { 899 int l0 = op0len - 1; 900 int l1 = op1len - 1; 901 bool need_canon = true; 902 903 unsigned int len = MAX (op0len, op1len); 904 if (l0 > l1) 905 { 906 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); 907 if (op1mask == 0) 908 { 909 l0 = l1; 910 len = l1 + 1; 911 } 912 else 913 { 914 need_canon = false; 915 while (l0 > l1) 916 { 917 val[l0] = op0[l0]; 918 l0--; 919 } 920 } 921 } 922 else if (l1 > l0) 923 { 924 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); 925 if (op0mask == 0) 926 len = l0 + 1; 927 else 928 { 929 need_canon = false; 930 while (l1 > l0) 931 { 932 val[l1] = op1[l1]; 933 l1--; 934 } 935 } 936 } 937 938 while (l0 >= 0) 939 { 940 val[l0] = op0[l0] & op1[l0]; 941 l0--; 942 } 943 944 if (need_canon) 945 len = canonize (val, len, prec); 946 947 return len; 948 } 949 950 /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */ 951 unsigned int 952 wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 953 unsigned int op0len, const HOST_WIDE_INT *op1, 954 unsigned int op1len, unsigned int prec) 955 { 956 wide_int result; 957 int l0 = op0len - 1; 958 int l1 = op1len - 1; 959 bool need_canon = true; 960 961 unsigned int len = MAX (op0len, op1len); 962 if (l0 > l1) 963 { 964 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); 965 if (op1mask != 0) 966 { 967 l0 = l1; 968 len = l1 + 1; 969 } 970 else 971 { 972 need_canon = false; 973 while (l0 > l1) 974 { 975 val[l0] = op0[l0]; 976 l0--; 977 } 978 } 979 } 980 else if (l1 > l0) 981 { 982 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); 983 if (op0mask == 0) 984 len = l0 + 1; 985 else 986 { 987 need_canon = false; 988 while (l1 > l0) 989 { 990 val[l1] = ~op1[l1]; 991 l1--; 992 } 993 } 994 } 995 996 while (l0 >= 0) 997 { 998 val[l0] = op0[l0] & ~op1[l0]; 999 l0--; 1000 } 1001 1002 if (need_canon) 1003 len = canonize (val, len, prec); 1004 1005 return len; 1006 } 1007 1008 /* Set VAL to OP0 | OP1. Return the number of blocks used. */ 1009 unsigned int 1010 wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 1011 unsigned int op0len, const HOST_WIDE_INT *op1, 1012 unsigned int op1len, unsigned int prec) 1013 { 1014 wide_int result; 1015 int l0 = op0len - 1; 1016 int l1 = op1len - 1; 1017 bool need_canon = true; 1018 1019 unsigned int len = MAX (op0len, op1len); 1020 if (l0 > l1) 1021 { 1022 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); 1023 if (op1mask != 0) 1024 { 1025 l0 = l1; 1026 len = l1 + 1; 1027 } 1028 else 1029 { 1030 need_canon = false; 1031 while (l0 > l1) 1032 { 1033 val[l0] = op0[l0]; 1034 l0--; 1035 } 1036 } 1037 } 1038 else if (l1 > l0) 1039 { 1040 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); 1041 if (op0mask != 0) 1042 len = l0 + 1; 1043 else 1044 { 1045 need_canon = false; 1046 while (l1 > l0) 1047 { 1048 val[l1] = op1[l1]; 1049 l1--; 1050 } 1051 } 1052 } 1053 1054 while (l0 >= 0) 1055 { 1056 val[l0] = op0[l0] | op1[l0]; 1057 l0--; 1058 } 1059 1060 if (need_canon) 1061 len = canonize (val, len, prec); 1062 1063 return len; 1064 } 1065 1066 /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */ 1067 unsigned int 1068 wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 1069 unsigned int op0len, const HOST_WIDE_INT *op1, 1070 unsigned int op1len, unsigned int prec) 1071 { 1072 wide_int result; 1073 int l0 = op0len - 1; 1074 int l1 = op1len - 1; 1075 bool need_canon = true; 1076 1077 unsigned int len = MAX (op0len, op1len); 1078 if (l0 > l1) 1079 { 1080 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); 1081 if (op1mask == 0) 1082 { 1083 l0 = l1; 1084 len = l1 + 1; 1085 } 1086 else 1087 { 1088 need_canon = false; 1089 while (l0 > l1) 1090 { 1091 val[l0] = op0[l0]; 1092 l0--; 1093 } 1094 } 1095 } 1096 else if (l1 > l0) 1097 { 1098 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); 1099 if (op0mask != 0) 1100 len = l0 + 1; 1101 else 1102 { 1103 need_canon = false; 1104 while (l1 > l0) 1105 { 1106 val[l1] = ~op1[l1]; 1107 l1--; 1108 } 1109 } 1110 } 1111 1112 while (l0 >= 0) 1113 { 1114 val[l0] = op0[l0] | ~op1[l0]; 1115 l0--; 1116 } 1117 1118 if (need_canon) 1119 len = canonize (val, len, prec); 1120 1121 return len; 1122 } 1123 1124 /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */ 1125 unsigned int 1126 wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 1127 unsigned int op0len, const HOST_WIDE_INT *op1, 1128 unsigned int op1len, unsigned int prec) 1129 { 1130 wide_int result; 1131 int l0 = op0len - 1; 1132 int l1 = op1len - 1; 1133 1134 unsigned int len = MAX (op0len, op1len); 1135 if (l0 > l1) 1136 { 1137 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); 1138 while (l0 > l1) 1139 { 1140 val[l0] = op0[l0] ^ op1mask; 1141 l0--; 1142 } 1143 } 1144 1145 if (l1 > l0) 1146 { 1147 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); 1148 while (l1 > l0) 1149 { 1150 val[l1] = op0mask ^ op1[l1]; 1151 l1--; 1152 } 1153 } 1154 1155 while (l0 >= 0) 1156 { 1157 val[l0] = op0[l0] ^ op1[l0]; 1158 l0--; 1159 } 1160 1161 return canonize (val, len, prec); 1162 } 1163 1164 /* 1165 * math 1166 */ 1167 1168 /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW 1169 whether the result overflows when OP0 and OP1 are treated as having 1170 signedness SGN. Return the number of blocks in VAL. */ 1171 unsigned int 1172 wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 1173 unsigned int op0len, const HOST_WIDE_INT *op1, 1174 unsigned int op1len, unsigned int prec, 1175 signop sgn, wi::overflow_type *overflow) 1176 { 1177 unsigned HOST_WIDE_INT o0 = 0; 1178 unsigned HOST_WIDE_INT o1 = 0; 1179 unsigned HOST_WIDE_INT x = 0; 1180 unsigned HOST_WIDE_INT carry = 0; 1181 unsigned HOST_WIDE_INT old_carry = 0; 1182 unsigned HOST_WIDE_INT mask0, mask1; 1183 unsigned int i; 1184 1185 unsigned int len = MAX (op0len, op1len); 1186 mask0 = -top_bit_of (op0, op0len, prec); 1187 mask1 = -top_bit_of (op1, op1len, prec); 1188 /* Add all of the explicitly defined elements. */ 1189 1190 for (i = 0; i < len; i++) 1191 { 1192 o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0; 1193 o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1; 1194 x = o0 + o1 + carry; 1195 val[i] = x; 1196 old_carry = carry; 1197 carry = carry == 0 ? x < o0 : x <= o0; 1198 } 1199 1200 if (len * HOST_BITS_PER_WIDE_INT < prec) 1201 { 1202 val[len] = mask0 + mask1 + carry; 1203 len++; 1204 if (overflow) 1205 *overflow 1206 = (sgn == UNSIGNED && carry) ? wi::OVF_OVERFLOW : wi::OVF_NONE; 1207 } 1208 else if (overflow) 1209 { 1210 unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT; 1211 if (sgn == SIGNED) 1212 { 1213 unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1); 1214 if ((HOST_WIDE_INT) (x << shift) < 0) 1215 { 1216 if (o0 > (unsigned HOST_WIDE_INT) val[len - 1]) 1217 *overflow = wi::OVF_UNDERFLOW; 1218 else if (o0 < (unsigned HOST_WIDE_INT) val[len - 1]) 1219 *overflow = wi::OVF_OVERFLOW; 1220 else 1221 *overflow = wi::OVF_NONE; 1222 } 1223 else 1224 *overflow = wi::OVF_NONE; 1225 } 1226 else 1227 { 1228 /* Put the MSB of X and O0 and in the top of the HWI. */ 1229 x <<= shift; 1230 o0 <<= shift; 1231 if (old_carry) 1232 *overflow = (x <= o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE; 1233 else 1234 *overflow = (x < o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE; 1235 } 1236 } 1237 1238 return canonize (val, len, prec); 1239 } 1240 1241 /* Subroutines of the multiplication and division operations. Unpack 1242 the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN 1243 HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by 1244 uncompressing the top bit of INPUT[IN_LEN - 1]. */ 1245 static void 1246 wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input, 1247 unsigned int in_len, unsigned int out_len, 1248 unsigned int prec, signop sgn) 1249 { 1250 unsigned int i; 1251 unsigned int j = 0; 1252 unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1); 1253 unsigned int blocks_needed = BLOCKS_NEEDED (prec); 1254 HOST_WIDE_INT mask; 1255 1256 if (sgn == SIGNED) 1257 { 1258 mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec); 1259 mask &= HALF_INT_MASK; 1260 } 1261 else 1262 mask = 0; 1263 1264 for (i = 0; i < blocks_needed - 1; i++) 1265 { 1266 HOST_WIDE_INT x = safe_uhwi (input, in_len, i); 1267 result[j++] = x; 1268 result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT; 1269 } 1270 1271 HOST_WIDE_INT x = safe_uhwi (input, in_len, i); 1272 if (small_prec) 1273 { 1274 if (sgn == SIGNED) 1275 x = sext_hwi (x, small_prec); 1276 else 1277 x = zext_hwi (x, small_prec); 1278 } 1279 result[j++] = x; 1280 result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT; 1281 1282 /* Smear the sign bit. */ 1283 while (j < out_len) 1284 result[j++] = mask; 1285 } 1286 1287 /* The inverse of wi_unpack. IN_LEN is the number of input 1288 blocks and PRECISION is the precision of the result. Return the 1289 number of blocks in the canonicalized result. */ 1290 static unsigned int 1291 wi_pack (HOST_WIDE_INT *result, 1292 const unsigned HOST_HALF_WIDE_INT *input, 1293 unsigned int in_len, unsigned int precision) 1294 { 1295 unsigned int i = 0; 1296 unsigned int j = 0; 1297 unsigned int blocks_needed = BLOCKS_NEEDED (precision); 1298 1299 while (i + 1 < in_len) 1300 { 1301 result[j++] = ((unsigned HOST_WIDE_INT) input[i] 1302 | ((unsigned HOST_WIDE_INT) input[i + 1] 1303 << HOST_BITS_PER_HALF_WIDE_INT)); 1304 i += 2; 1305 } 1306 1307 /* Handle the case where in_len is odd. For this we zero extend. */ 1308 if (in_len & 1) 1309 result[j++] = (unsigned HOST_WIDE_INT) input[i]; 1310 else if (j < blocks_needed) 1311 result[j++] = 0; 1312 return canonize (result, j, precision); 1313 } 1314 1315 /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the 1316 result is returned. 1317 1318 If HIGH is not set, throw away the upper half after the check is 1319 made to see if it overflows. Unfortunately there is no better way 1320 to check for overflow than to do this. If OVERFLOW is nonnull, 1321 record in *OVERFLOW whether the result overflowed. SGN controls 1322 the signedness and is used to check overflow or if HIGH is set. 1323 1324 NOTE: Overflow type for signed overflow is not yet implemented. */ 1325 unsigned int 1326 wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val, 1327 unsigned int op1len, const HOST_WIDE_INT *op2val, 1328 unsigned int op2len, unsigned int prec, signop sgn, 1329 wi::overflow_type *overflow, bool high) 1330 { 1331 unsigned HOST_WIDE_INT o0, o1, k, t; 1332 unsigned int i; 1333 unsigned int j; 1334 1335 /* If the top level routine did not really pass in an overflow, then 1336 just make sure that we never attempt to set it. */ 1337 bool needs_overflow = (overflow != 0); 1338 if (needs_overflow) 1339 *overflow = wi::OVF_NONE; 1340 1341 wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec); 1342 wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec); 1343 1344 /* This is a surprisingly common case, so do it first. */ 1345 if (op1 == 0 || op2 == 0) 1346 { 1347 val[0] = 0; 1348 return 1; 1349 } 1350 1351 #ifdef umul_ppmm 1352 if (sgn == UNSIGNED) 1353 { 1354 /* If the inputs are single HWIs and the output has room for at 1355 least two HWIs, we can use umul_ppmm directly. */ 1356 if (prec >= HOST_BITS_PER_WIDE_INT * 2 1357 && wi::fits_uhwi_p (op1) 1358 && wi::fits_uhwi_p (op2)) 1359 { 1360 /* This case never overflows. */ 1361 if (high) 1362 { 1363 val[0] = 0; 1364 return 1; 1365 } 1366 umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ()); 1367 if (val[1] < 0 && prec > HOST_BITS_PER_WIDE_INT * 2) 1368 { 1369 val[2] = 0; 1370 return 3; 1371 } 1372 return 1 + (val[1] != 0 || val[0] < 0); 1373 } 1374 /* Likewise if the output is a full single HWI, except that the 1375 upper HWI of the result is only used for determining overflow. 1376 (We handle this case inline when overflow isn't needed.) */ 1377 else if (prec == HOST_BITS_PER_WIDE_INT) 1378 { 1379 unsigned HOST_WIDE_INT upper; 1380 umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ()); 1381 if (needs_overflow) 1382 /* Unsigned overflow can only be +OVERFLOW. */ 1383 *overflow = (upper != 0) ? wi::OVF_OVERFLOW : wi::OVF_NONE; 1384 if (high) 1385 val[0] = upper; 1386 return 1; 1387 } 1388 } 1389 #endif 1390 1391 /* Handle multiplications by 1. */ 1392 if (op1 == 1) 1393 { 1394 if (high) 1395 { 1396 val[0] = wi::neg_p (op2, sgn) ? -1 : 0; 1397 return 1; 1398 } 1399 for (i = 0; i < op2len; i++) 1400 val[i] = op2val[i]; 1401 return op2len; 1402 } 1403 if (op2 == 1) 1404 { 1405 if (high) 1406 { 1407 val[0] = wi::neg_p (op1, sgn) ? -1 : 0; 1408 return 1; 1409 } 1410 for (i = 0; i < op1len; i++) 1411 val[i] = op1val[i]; 1412 return op1len; 1413 } 1414 1415 /* If we need to check for overflow, we can only do half wide 1416 multiplies quickly because we need to look at the top bits to 1417 check for the overflow. */ 1418 if ((high || needs_overflow) 1419 && (prec <= HOST_BITS_PER_HALF_WIDE_INT)) 1420 { 1421 unsigned HOST_WIDE_INT r; 1422 1423 if (sgn == SIGNED) 1424 { 1425 o0 = op1.to_shwi (); 1426 o1 = op2.to_shwi (); 1427 } 1428 else 1429 { 1430 o0 = op1.to_uhwi (); 1431 o1 = op2.to_uhwi (); 1432 } 1433 1434 r = o0 * o1; 1435 if (needs_overflow) 1436 { 1437 if (sgn == SIGNED) 1438 { 1439 if ((HOST_WIDE_INT) r != sext_hwi (r, prec)) 1440 /* FIXME: Signed overflow type is not implemented yet. */ 1441 *overflow = OVF_UNKNOWN; 1442 } 1443 else 1444 { 1445 if ((r >> prec) != 0) 1446 /* Unsigned overflow can only be +OVERFLOW. */ 1447 *overflow = OVF_OVERFLOW; 1448 } 1449 } 1450 val[0] = high ? r >> prec : r; 1451 return 1; 1452 } 1453 1454 /* The sizes here are scaled to support a 2x WIDE_INT_MAX_INL_PRECISION by 2x 1455 WIDE_INT_MAX_INL_PRECISION yielding a 4x WIDE_INT_MAX_INL_PRECISION 1456 result. */ 1457 1458 unsigned HOST_HALF_WIDE_INT 1459 ubuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT]; 1460 unsigned HOST_HALF_WIDE_INT 1461 vbuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT]; 1462 /* The '2' in 'R' is because we are internally doing a full 1463 multiply. */ 1464 unsigned HOST_HALF_WIDE_INT 1465 rbuf[2 * 4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT]; 1466 const HOST_WIDE_INT mask 1467 = (HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1; 1468 unsigned HOST_HALF_WIDE_INT *u = ubuf; 1469 unsigned HOST_HALF_WIDE_INT *v = vbuf; 1470 unsigned HOST_HALF_WIDE_INT *r = rbuf; 1471 1472 if (!high) 1473 prec = MIN ((op1len + op2len + 1) * HOST_BITS_PER_WIDE_INT, prec); 1474 unsigned int blocks_needed = BLOCKS_NEEDED (prec); 1475 unsigned int half_blocks_needed = blocks_needed * 2; 1476 if (UNLIKELY (prec > WIDE_INT_MAX_INL_PRECISION)) 1477 { 1478 unsigned HOST_HALF_WIDE_INT *buf 1479 = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT, 4 * half_blocks_needed); 1480 u = buf; 1481 v = u + half_blocks_needed; 1482 r = v + half_blocks_needed; 1483 } 1484 1485 /* We do unsigned mul and then correct it. */ 1486 wi_unpack (u, op1val, op1len, half_blocks_needed, prec, UNSIGNED); 1487 wi_unpack (v, op2val, op2len, half_blocks_needed, prec, UNSIGNED); 1488 1489 /* The 2 is for a full mult. */ 1490 memset (r, 0, half_blocks_needed * 2 1491 * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT); 1492 1493 for (j = 0; j < half_blocks_needed; j++) 1494 { 1495 k = 0; 1496 for (i = 0; i < half_blocks_needed; i++) 1497 { 1498 t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j] 1499 + r[i + j] + k); 1500 r[i + j] = t & HALF_INT_MASK; 1501 k = t >> HOST_BITS_PER_HALF_WIDE_INT; 1502 } 1503 r[j + half_blocks_needed] = k; 1504 } 1505 1506 unsigned int shift; 1507 if ((high || needs_overflow) && (shift = prec % HOST_BITS_PER_WIDE_INT) != 0) 1508 { 1509 /* The high or needs_overflow code assumes that the high bits 1510 only appear from r[half_blocks_needed] up to 1511 r[half_blocks_needed * 2 - 1]. If prec is not a multiple 1512 of HOST_BITS_PER_WIDE_INT, shift the bits above prec up 1513 to make that code simple. */ 1514 if (shift == HOST_BITS_PER_HALF_WIDE_INT) 1515 memmove (&r[half_blocks_needed], &r[half_blocks_needed - 1], 1516 sizeof (r[0]) * half_blocks_needed); 1517 else 1518 { 1519 unsigned int skip = shift < HOST_BITS_PER_HALF_WIDE_INT; 1520 if (!skip) 1521 shift -= HOST_BITS_PER_HALF_WIDE_INT; 1522 for (i = 2 * half_blocks_needed - 1; i >= half_blocks_needed; i--) 1523 r[i] = ((r[i - skip] << (-shift % HOST_BITS_PER_HALF_WIDE_INT)) 1524 | (r[i - skip - 1] >> shift)); 1525 } 1526 } 1527 1528 /* We did unsigned math above. For signed we must adjust the 1529 product (assuming we need to see that). */ 1530 if (sgn == SIGNED && (high || needs_overflow)) 1531 { 1532 unsigned HOST_WIDE_INT b; 1533 if (wi::neg_p (op1)) 1534 { 1535 b = 0; 1536 for (i = 0; i < half_blocks_needed; i++) 1537 { 1538 t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed] 1539 - (unsigned HOST_WIDE_INT)v[i] - b; 1540 r[i + half_blocks_needed] = t & HALF_INT_MASK; 1541 b = t >> (HOST_BITS_PER_WIDE_INT - 1); 1542 } 1543 } 1544 if (wi::neg_p (op2)) 1545 { 1546 b = 0; 1547 for (i = 0; i < half_blocks_needed; i++) 1548 { 1549 t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed] 1550 - (unsigned HOST_WIDE_INT)u[i] - b; 1551 r[i + half_blocks_needed] = t & HALF_INT_MASK; 1552 b = t >> (HOST_BITS_PER_WIDE_INT - 1); 1553 } 1554 } 1555 } 1556 1557 if (needs_overflow) 1558 { 1559 HOST_WIDE_INT top; 1560 1561 /* For unsigned, overflow is true if any of the top bits are set. 1562 For signed, overflow is true if any of the top bits are not equal 1563 to the sign bit. */ 1564 if (sgn == UNSIGNED) 1565 top = 0; 1566 else 1567 { 1568 top = r[half_blocks_needed - 1 1569 - ((-prec % HOST_BITS_PER_WIDE_INT) 1570 >= HOST_BITS_PER_HALF_WIDE_INT)]; 1571 top = SIGN_MASK (((unsigned HOST_WIDE_INT) top) 1572 << (HOST_BITS_PER_WIDE_INT / 2 1573 + (-prec % HOST_BITS_PER_HALF_WIDE_INT))); 1574 top &= mask; 1575 } 1576 1577 unsigned int end = half_blocks_needed * 2; 1578 shift = prec % HOST_BITS_PER_WIDE_INT; 1579 if (shift) 1580 { 1581 /* For overflow checking only look at the first prec bits 1582 starting with r[half_blocks_needed]. */ 1583 if (shift <= HOST_BITS_PER_HALF_WIDE_INT) 1584 --end; 1585 shift %= HOST_BITS_PER_HALF_WIDE_INT; 1586 if (shift) 1587 { 1588 if (top) 1589 r[end - 1] |= ((~(unsigned HOST_HALF_WIDE_INT) 0) << shift); 1590 else 1591 r[end - 1] &= (((unsigned HOST_HALF_WIDE_INT) 1) << shift) - 1; 1592 } 1593 } 1594 for (i = half_blocks_needed; i < end; i++) 1595 if (((HOST_WIDE_INT)(r[i] & mask)) != top) 1596 /* FIXME: Signed overflow type is not implemented yet. */ 1597 *overflow = (sgn == UNSIGNED) ? wi::OVF_OVERFLOW : wi::OVF_UNKNOWN; 1598 } 1599 1600 int r_offset = high ? half_blocks_needed : 0; 1601 return wi_pack (val, &r[r_offset], half_blocks_needed, prec); 1602 } 1603 1604 /* Compute the population count of X. */ 1605 int 1606 wi::popcount (const wide_int_ref &x) 1607 { 1608 unsigned int i; 1609 int count; 1610 1611 /* The high order block is special if it is the last block and the 1612 precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We 1613 have to clear out any ones above the precision before doing 1614 popcount on this block. */ 1615 count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; 1616 unsigned int stop = x.len; 1617 if (count < 0) 1618 { 1619 count = popcount_hwi (x.uhigh () << -count); 1620 stop -= 1; 1621 } 1622 else 1623 { 1624 if (x.sign_mask () >= 0) 1625 count = 0; 1626 } 1627 1628 for (i = 0; i < stop; ++i) 1629 count += popcount_hwi (x.val[i]); 1630 1631 return count; 1632 } 1633 1634 /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW 1635 whether the result overflows when OP0 and OP1 are treated as having 1636 signedness SGN. Return the number of blocks in VAL. */ 1637 unsigned int 1638 wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, 1639 unsigned int op0len, const HOST_WIDE_INT *op1, 1640 unsigned int op1len, unsigned int prec, 1641 signop sgn, wi::overflow_type *overflow) 1642 { 1643 unsigned HOST_WIDE_INT o0 = 0; 1644 unsigned HOST_WIDE_INT o1 = 0; 1645 unsigned HOST_WIDE_INT x = 0; 1646 /* We implement subtraction as an in place negate and add. Negation 1647 is just inversion and add 1, so we can do the add of 1 by just 1648 starting the borrow in of the first element at 1. */ 1649 unsigned HOST_WIDE_INT borrow = 0; 1650 unsigned HOST_WIDE_INT old_borrow = 0; 1651 1652 unsigned HOST_WIDE_INT mask0, mask1; 1653 unsigned int i; 1654 1655 unsigned int len = MAX (op0len, op1len); 1656 mask0 = -top_bit_of (op0, op0len, prec); 1657 mask1 = -top_bit_of (op1, op1len, prec); 1658 1659 /* Subtract all of the explicitly defined elements. */ 1660 for (i = 0; i < len; i++) 1661 { 1662 o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0; 1663 o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1; 1664 x = o0 - o1 - borrow; 1665 val[i] = x; 1666 old_borrow = borrow; 1667 borrow = borrow == 0 ? o0 < o1 : o0 <= o1; 1668 } 1669 1670 if (len * HOST_BITS_PER_WIDE_INT < prec) 1671 { 1672 val[len] = mask0 - mask1 - borrow; 1673 len++; 1674 if (overflow) 1675 *overflow = (sgn == UNSIGNED && borrow) ? OVF_UNDERFLOW : OVF_NONE; 1676 } 1677 else if (overflow) 1678 { 1679 unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT; 1680 if (sgn == SIGNED) 1681 { 1682 unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0); 1683 if ((HOST_WIDE_INT) (x << shift) < 0) 1684 { 1685 if (o0 > o1) 1686 *overflow = OVF_UNDERFLOW; 1687 else if (o0 < o1) 1688 *overflow = OVF_OVERFLOW; 1689 else 1690 *overflow = OVF_NONE; 1691 } 1692 else 1693 *overflow = OVF_NONE; 1694 } 1695 else 1696 { 1697 /* Put the MSB of X and O0 and in the top of the HWI. */ 1698 x <<= shift; 1699 o0 <<= shift; 1700 if (old_borrow) 1701 *overflow = (x >= o0) ? OVF_UNDERFLOW : OVF_NONE; 1702 else 1703 *overflow = (x > o0) ? OVF_UNDERFLOW : OVF_NONE; 1704 } 1705 } 1706 1707 return canonize (val, len, prec); 1708 } 1709 1710 1711 /* 1712 * Division and Mod 1713 */ 1714 1715 /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The 1716 algorithm is a small modification of the algorithm in Hacker's 1717 Delight by Warren, which itself is a small modification of Knuth's 1718 algorithm. M is the number of significant elements of U however 1719 there needs to be at least one extra element of B_DIVIDEND 1720 allocated, N is the number of elements of B_DIVISOR. 1721 Return new value for N. */ 1722 static int 1723 divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient, 1724 unsigned HOST_HALF_WIDE_INT *b_remainder, 1725 unsigned HOST_HALF_WIDE_INT *b_dividend, 1726 unsigned HOST_HALF_WIDE_INT *b_divisor, 1727 int m, int n) 1728 { 1729 /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a 1730 HOST_WIDE_INT and stored in the lower bits of each word. This 1731 algorithm should work properly on both 32 and 64 bit 1732 machines. */ 1733 unsigned HOST_WIDE_INT b = HOST_WIDE_INT_1U << HOST_BITS_PER_HALF_WIDE_INT; 1734 unsigned HOST_WIDE_INT qhat; /* Estimate of quotient digit. */ 1735 unsigned HOST_WIDE_INT rhat; /* A remainder. */ 1736 unsigned HOST_WIDE_INT p; /* Product of two digits. */ 1737 HOST_WIDE_INT t, k; 1738 int i, j, s; 1739 1740 /* Single digit divisor. */ 1741 if (n == 1) 1742 { 1743 k = 0; 1744 for (j = m - 1; j >= 0; j--) 1745 { 1746 b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0]; 1747 k = ((k * b + b_dividend[j]) 1748 - ((unsigned HOST_WIDE_INT)b_quotient[j] 1749 * (unsigned HOST_WIDE_INT)b_divisor[0])); 1750 } 1751 b_remainder[0] = k; 1752 return 1; 1753 } 1754 1755 s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */ 1756 1757 if (s) 1758 { 1759 /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published 1760 algorithm, we can overwrite b_dividend and b_divisor, so we do 1761 that. */ 1762 for (i = n - 1; i > 0; i--) 1763 b_divisor[i] = (b_divisor[i] << s) 1764 | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s)); 1765 b_divisor[0] = b_divisor[0] << s; 1766 1767 b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s); 1768 for (i = m - 1; i > 0; i--) 1769 b_dividend[i] = (b_dividend[i] << s) 1770 | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s)); 1771 b_dividend[0] = b_dividend[0] << s; 1772 } 1773 1774 /* Main loop. */ 1775 for (j = m - n; j >= 0; j--) 1776 { 1777 qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1]; 1778 rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1]; 1779 again: 1780 if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2]) 1781 { 1782 qhat -= 1; 1783 rhat += b_divisor[n-1]; 1784 if (rhat < b) 1785 goto again; 1786 } 1787 1788 /* Multiply and subtract. */ 1789 k = 0; 1790 for (i = 0; i < n; i++) 1791 { 1792 p = qhat * b_divisor[i]; 1793 t = b_dividend[i+j] - k - (p & HALF_INT_MASK); 1794 b_dividend[i + j] = t; 1795 k = ((p >> HOST_BITS_PER_HALF_WIDE_INT) 1796 - (t >> HOST_BITS_PER_HALF_WIDE_INT)); 1797 } 1798 t = b_dividend[j+n] - k; 1799 b_dividend[j+n] = t; 1800 1801 b_quotient[j] = qhat; 1802 if (t < 0) 1803 { 1804 b_quotient[j] -= 1; 1805 k = 0; 1806 for (i = 0; i < n; i++) 1807 { 1808 t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k; 1809 b_dividend[i+j] = t; 1810 k = t >> HOST_BITS_PER_HALF_WIDE_INT; 1811 } 1812 b_dividend[j+n] += k; 1813 } 1814 } 1815 /* If N > M, the main loop was skipped, quotient will be 0 and 1816 we can't copy more than M half-limbs into the remainder, as they 1817 aren't present in b_dividend (which has . */ 1818 n = MIN (n, m); 1819 if (s) 1820 for (i = 0; i < n; i++) 1821 b_remainder[i] = (b_dividend[i] >> s) 1822 | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s)); 1823 else 1824 for (i = 0; i < n; i++) 1825 b_remainder[i] = b_dividend[i]; 1826 return n; 1827 } 1828 1829 1830 /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate 1831 the result. If QUOTIENT is nonnull, store the value of the quotient 1832 there and return the number of blocks in it. The return value is 1833 not defined otherwise. If REMAINDER is nonnull, store the value 1834 of the remainder there and store the number of blocks in 1835 *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether 1836 the division overflowed. */ 1837 unsigned int 1838 wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len, 1839 HOST_WIDE_INT *remainder, 1840 const HOST_WIDE_INT *dividend_val, 1841 unsigned int dividend_len, unsigned int dividend_prec, 1842 const HOST_WIDE_INT *divisor_val, unsigned int divisor_len, 1843 unsigned int divisor_prec, signop sgn, 1844 wi::overflow_type *oflow) 1845 { 1846 unsigned int m, n; 1847 bool dividend_neg = false; 1848 bool divisor_neg = false; 1849 bool overflow = false; 1850 wide_int neg_dividend, neg_divisor; 1851 1852 wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len, 1853 dividend_prec); 1854 wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len, 1855 divisor_prec); 1856 if (divisor == 0) 1857 overflow = true; 1858 1859 /* The smallest signed number / -1 causes overflow. The dividend_len 1860 check is for speed rather than correctness. */ 1861 if (sgn == SIGNED 1862 && dividend_len == BLOCKS_NEEDED (dividend_prec) 1863 && divisor == -1 1864 && wi::only_sign_bit_p (dividend)) 1865 overflow = true; 1866 1867 /* Handle the overflow cases. Viewed as unsigned value, the quotient of 1868 (signed min / -1) has the same representation as the orignal dividend. 1869 We have traditionally made division by zero act as division by one, 1870 so there too we use the original dividend. */ 1871 if (overflow) 1872 { 1873 if (remainder) 1874 { 1875 *remainder_len = 1; 1876 remainder[0] = 0; 1877 } 1878 if (oflow) 1879 *oflow = OVF_OVERFLOW; 1880 if (quotient) 1881 for (unsigned int i = 0; i < dividend_len; ++i) 1882 quotient[i] = dividend_val[i]; 1883 return dividend_len; 1884 } 1885 1886 if (oflow) 1887 *oflow = OVF_NONE; 1888 1889 /* Do it on the host if you can. */ 1890 if (sgn == SIGNED 1891 && wi::fits_shwi_p (dividend) 1892 && wi::fits_shwi_p (divisor)) 1893 { 1894 HOST_WIDE_INT o0 = dividend.to_shwi (); 1895 HOST_WIDE_INT o1 = divisor.to_shwi (); 1896 1897 if (o0 == HOST_WIDE_INT_MIN && o1 == -1) 1898 { 1899 gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT); 1900 if (quotient) 1901 { 1902 quotient[0] = HOST_WIDE_INT_MIN; 1903 quotient[1] = 0; 1904 } 1905 if (remainder) 1906 { 1907 remainder[0] = 0; 1908 *remainder_len = 1; 1909 } 1910 return 2; 1911 } 1912 else 1913 { 1914 if (quotient) 1915 quotient[0] = o0 / o1; 1916 if (remainder) 1917 { 1918 remainder[0] = o0 % o1; 1919 *remainder_len = 1; 1920 } 1921 return 1; 1922 } 1923 } 1924 1925 if (sgn == UNSIGNED 1926 && wi::fits_uhwi_p (dividend) 1927 && wi::fits_uhwi_p (divisor)) 1928 { 1929 unsigned HOST_WIDE_INT o0 = dividend.to_uhwi (); 1930 unsigned HOST_WIDE_INT o1 = divisor.to_uhwi (); 1931 unsigned int quotient_len = 1; 1932 1933 if (quotient) 1934 { 1935 quotient[0] = o0 / o1; 1936 quotient_len = canonize_uhwi (quotient, dividend_prec); 1937 } 1938 if (remainder) 1939 { 1940 remainder[0] = o0 % o1; 1941 *remainder_len = canonize_uhwi (remainder, dividend_prec); 1942 } 1943 return quotient_len; 1944 } 1945 1946 /* Make the divisor and dividend positive and remember what we 1947 did. */ 1948 if (sgn == SIGNED) 1949 { 1950 if (wi::neg_p (dividend)) 1951 { 1952 neg_dividend = -dividend; 1953 dividend = neg_dividend; 1954 dividend_neg = true; 1955 } 1956 if (wi::neg_p (divisor)) 1957 { 1958 neg_divisor = -divisor; 1959 divisor = neg_divisor; 1960 divisor_neg = true; 1961 } 1962 } 1963 1964 unsigned HOST_HALF_WIDE_INT 1965 b_quotient_buf[4 * WIDE_INT_MAX_INL_PRECISION 1966 / HOST_BITS_PER_HALF_WIDE_INT]; 1967 unsigned HOST_HALF_WIDE_INT 1968 b_remainder_buf[4 * WIDE_INT_MAX_INL_PRECISION 1969 / HOST_BITS_PER_HALF_WIDE_INT]; 1970 unsigned HOST_HALF_WIDE_INT 1971 b_dividend_buf[(4 * WIDE_INT_MAX_INL_PRECISION 1972 / HOST_BITS_PER_HALF_WIDE_INT) + 1]; 1973 unsigned HOST_HALF_WIDE_INT 1974 b_divisor_buf[4 * WIDE_INT_MAX_INL_PRECISION 1975 / HOST_BITS_PER_HALF_WIDE_INT]; 1976 unsigned HOST_HALF_WIDE_INT *b_quotient = b_quotient_buf; 1977 unsigned HOST_HALF_WIDE_INT *b_remainder = b_remainder_buf; 1978 unsigned HOST_HALF_WIDE_INT *b_dividend = b_dividend_buf; 1979 unsigned HOST_HALF_WIDE_INT *b_divisor = b_divisor_buf; 1980 1981 if (sgn == SIGNED || dividend_val[dividend_len - 1] >= 0) 1982 dividend_prec = MIN ((dividend_len + 1) * HOST_BITS_PER_WIDE_INT, 1983 dividend_prec); 1984 if (sgn == SIGNED || divisor_val[divisor_len - 1] >= 0) 1985 divisor_prec = MIN (divisor_len * HOST_BITS_PER_WIDE_INT, divisor_prec); 1986 unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec); 1987 unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec); 1988 if (UNLIKELY (dividend_prec > WIDE_INT_MAX_INL_PRECISION) 1989 || UNLIKELY (divisor_prec > WIDE_INT_MAX_INL_PRECISION)) 1990 { 1991 unsigned HOST_HALF_WIDE_INT *buf 1992 = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT, 1993 3 * dividend_blocks_needed + 1 1994 + divisor_blocks_needed); 1995 b_quotient = buf; 1996 b_remainder = b_quotient + dividend_blocks_needed; 1997 b_dividend = b_remainder + dividend_blocks_needed; 1998 b_divisor = b_dividend + dividend_blocks_needed + 1; 1999 memset (b_quotient, 0, 2000 dividend_blocks_needed * sizeof (HOST_HALF_WIDE_INT)); 2001 } 2002 wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (), 2003 dividend_blocks_needed, dividend_prec, UNSIGNED); 2004 wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (), 2005 divisor_blocks_needed, divisor_prec, UNSIGNED); 2006 2007 m = dividend_blocks_needed; 2008 b_dividend[m] = 0; 2009 while (m > 1 && b_dividend[m - 1] == 0) 2010 m--; 2011 2012 n = divisor_blocks_needed; 2013 while (n > 1 && b_divisor[n - 1] == 0) 2014 n--; 2015 2016 if (b_quotient == b_quotient_buf) 2017 memset (b_quotient_buf, 0, sizeof (b_quotient_buf)); 2018 2019 n = divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n); 2020 2021 unsigned int quotient_len = 0; 2022 if (quotient) 2023 { 2024 quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec); 2025 /* The quotient is neg if exactly one of the divisor or dividend is 2026 neg. */ 2027 if (dividend_neg != divisor_neg) 2028 quotient_len = wi::sub_large (quotient, zeros, 1, quotient, 2029 quotient_len, dividend_prec, 2030 UNSIGNED, 0); 2031 } 2032 2033 if (remainder) 2034 { 2035 *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec); 2036 /* The remainder is always the same sign as the dividend. */ 2037 if (dividend_neg) 2038 *remainder_len = wi::sub_large (remainder, zeros, 1, remainder, 2039 *remainder_len, dividend_prec, 2040 UNSIGNED, 0); 2041 } 2042 2043 return quotient_len; 2044 } 2045 2046 /* 2047 * Shifting, rotating and extraction. 2048 */ 2049 2050 /* Left shift XVAL by SHIFT and store the result in VAL. Return the 2051 number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */ 2052 unsigned int 2053 wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 2054 unsigned int xlen, unsigned int precision, 2055 unsigned int shift) 2056 { 2057 /* Split the shift into a whole-block shift and a subblock shift. */ 2058 unsigned int skip = shift / HOST_BITS_PER_WIDE_INT; 2059 unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT; 2060 2061 /* The whole-block shift fills with zeros. */ 2062 unsigned int len = BLOCKS_NEEDED (precision); 2063 len = MIN (xlen + skip + 1, len); 2064 for (unsigned int i = 0; i < skip; ++i) 2065 val[i] = 0; 2066 2067 /* It's easier to handle the simple block case specially. */ 2068 if (small_shift == 0) 2069 for (unsigned int i = skip; i < len; ++i) 2070 val[i] = safe_uhwi (xval, xlen, i - skip); 2071 else 2072 { 2073 /* The first unfilled output block is a left shift of the first 2074 block in XVAL. The other output blocks contain bits from two 2075 consecutive input blocks. */ 2076 unsigned HOST_WIDE_INT carry = 0; 2077 for (unsigned int i = skip; i < len; ++i) 2078 { 2079 unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip); 2080 val[i] = (x << small_shift) | carry; 2081 carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT); 2082 } 2083 } 2084 return canonize (val, len, precision); 2085 } 2086 2087 /* Right shift XVAL by SHIFT and store the result in VAL. LEN is the 2088 number of blocks in VAL. The input has XPRECISION bits and the 2089 output has XPRECISION - SHIFT bits. */ 2090 static void 2091 rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 2092 unsigned int xlen, unsigned int shift, unsigned int len) 2093 { 2094 /* Split the shift into a whole-block shift and a subblock shift. */ 2095 unsigned int skip = shift / HOST_BITS_PER_WIDE_INT; 2096 unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT; 2097 2098 /* It's easier to handle the simple block case specially. */ 2099 if (small_shift == 0) 2100 for (unsigned int i = 0; i < len; ++i) 2101 val[i] = safe_uhwi (xval, xlen, i + skip); 2102 else 2103 { 2104 /* Each output block but the last is a combination of two input blocks. 2105 The last block is a right shift of the last block in XVAL. */ 2106 unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip); 2107 for (unsigned int i = 0; i < len; ++i) 2108 { 2109 val[i] = curr >> small_shift; 2110 curr = safe_uhwi (xval, xlen, i + skip + 1); 2111 val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT); 2112 } 2113 } 2114 } 2115 2116 /* Logically right shift XVAL by SHIFT and store the result in VAL. 2117 Return the number of blocks in VAL. XVAL has XPRECISION bits and 2118 VAL has PRECISION bits. */ 2119 unsigned int 2120 wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 2121 unsigned int xlen, unsigned int xprecision, 2122 unsigned int precision, unsigned int shift) 2123 { 2124 /* Work out how many blocks are needed to store the significant bits 2125 (excluding the upper zeros or signs). */ 2126 unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift); 2127 unsigned int len = blocks_needed; 2128 if (len > xlen && xval[xlen - 1] >= 0) 2129 len = xlen; 2130 2131 rshift_large_common (val, xval, xlen, shift, len); 2132 2133 /* The value we just created has precision XPRECISION - SHIFT. 2134 Zero-extend it to wider precisions. */ 2135 if (precision > xprecision - shift && len == blocks_needed) 2136 { 2137 unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT; 2138 if (small_prec) 2139 val[len - 1] = zext_hwi (val[len - 1], small_prec); 2140 else if (val[len - 1] < 0) 2141 { 2142 /* Add a new block with a zero. */ 2143 val[len++] = 0; 2144 return len; 2145 } 2146 } 2147 return canonize (val, len, precision); 2148 } 2149 2150 /* Arithmetically right shift XVAL by SHIFT and store the result in VAL. 2151 Return the number of blocks in VAL. XVAL has XPRECISION bits and 2152 VAL has PRECISION bits. */ 2153 unsigned int 2154 wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, 2155 unsigned int xlen, unsigned int xprecision, 2156 unsigned int precision, unsigned int shift) 2157 { 2158 /* Work out how many blocks are needed to store the significant bits 2159 (excluding the upper zeros or signs). */ 2160 unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift); 2161 unsigned int len = MIN (xlen, blocks_needed); 2162 2163 rshift_large_common (val, xval, xlen, shift, len); 2164 2165 /* The value we just created has precision XPRECISION - SHIFT. 2166 Sign-extend it to wider types. */ 2167 if (precision > xprecision - shift && len == blocks_needed) 2168 { 2169 unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT; 2170 if (small_prec) 2171 val[len - 1] = sext_hwi (val[len - 1], small_prec); 2172 } 2173 return canonize (val, len, precision); 2174 } 2175 2176 /* Return the number of leading (upper) zeros in X. */ 2177 int 2178 wi::clz (const wide_int_ref &x) 2179 { 2180 if (x.sign_mask () < 0) 2181 /* The upper bit is set, so there are no leading zeros. */ 2182 return 0; 2183 2184 /* Calculate how many bits there above the highest represented block. */ 2185 int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; 2186 2187 unsigned HOST_WIDE_INT high = x.uhigh (); 2188 if (count < 0) 2189 /* The upper -COUNT bits of HIGH are not part of the value. 2190 Clear them out. */ 2191 high = (high << -count) >> -count; 2192 2193 /* We don't need to look below HIGH. Either HIGH is nonzero, 2194 or the top bit of the block below is nonzero; clz_hwi is 2195 HOST_BITS_PER_WIDE_INT in the latter case. */ 2196 return count + clz_hwi (high); 2197 } 2198 2199 /* Return the number of redundant sign bits in X. (That is, the number 2200 of bits immediately below the sign bit that have the same value as 2201 the sign bit.) */ 2202 int 2203 wi::clrsb (const wide_int_ref &x) 2204 { 2205 /* Calculate how many bits there above the highest represented block. */ 2206 int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; 2207 2208 unsigned HOST_WIDE_INT high = x.uhigh (); 2209 unsigned HOST_WIDE_INT mask = -1; 2210 if (count < 0) 2211 { 2212 /* The upper -COUNT bits of HIGH are not part of the value. 2213 Clear them from both MASK and HIGH. */ 2214 mask >>= -count; 2215 high &= mask; 2216 } 2217 2218 /* If the top bit is 1, count the number of leading 1s. If the top 2219 bit is zero, count the number of leading zeros. */ 2220 if (high > mask / 2) 2221 high ^= mask; 2222 2223 /* There are no sign bits below the top block, so we don't need to look 2224 beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when 2225 HIGH is 0. */ 2226 return count + clz_hwi (high) - 1; 2227 } 2228 2229 /* Return the number of trailing (lower) zeros in X. */ 2230 int 2231 wi::ctz (const wide_int_ref &x) 2232 { 2233 if (x.len == 1 && x.ulow () == 0) 2234 return x.precision; 2235 2236 /* Having dealt with the zero case, there must be a block with a 2237 nonzero bit. We don't care about the bits above the first 1. */ 2238 unsigned int i = 0; 2239 while (x.val[i] == 0) 2240 ++i; 2241 return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]); 2242 } 2243 2244 /* If X is an exact power of 2, return the base-2 logarithm, otherwise 2245 return -1. */ 2246 int 2247 wi::exact_log2 (const wide_int_ref &x) 2248 { 2249 /* Reject cases where there are implicit -1 blocks above HIGH. */ 2250 if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0) 2251 return -1; 2252 2253 /* Set CRUX to the index of the entry that should be nonzero. 2254 If the top block is zero then the next lowest block (if any) 2255 must have the high bit set. */ 2256 unsigned int crux = x.len - 1; 2257 if (crux > 0 && x.val[crux] == 0) 2258 crux -= 1; 2259 2260 /* Check that all lower blocks are zero. */ 2261 for (unsigned int i = 0; i < crux; ++i) 2262 if (x.val[i] != 0) 2263 return -1; 2264 2265 /* Get a zero-extended form of block CRUX. */ 2266 unsigned HOST_WIDE_INT hwi = x.val[crux]; 2267 if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision) 2268 hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT); 2269 2270 /* Now it's down to whether HWI is a power of 2. */ 2271 int res = ::exact_log2 (hwi); 2272 if (res >= 0) 2273 res += crux * HOST_BITS_PER_WIDE_INT; 2274 return res; 2275 } 2276 2277 /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */ 2278 int 2279 wi::floor_log2 (const wide_int_ref &x) 2280 { 2281 return x.precision - 1 - clz (x); 2282 } 2283 2284 /* Return the index of the first (lowest) set bit in X, counting from 1. 2285 Return 0 if X is 0. */ 2286 int 2287 wi::ffs (const wide_int_ref &x) 2288 { 2289 return eq_p (x, 0) ? 0 : ctz (x) + 1; 2290 } 2291 2292 /* Return true if sign-extending X to have precision PRECISION would give 2293 the minimum signed value at that precision. */ 2294 bool 2295 wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision) 2296 { 2297 return ctz (x) + 1 == int (precision); 2298 } 2299 2300 /* Return true if X represents the minimum signed value. */ 2301 bool 2302 wi::only_sign_bit_p (const wide_int_ref &x) 2303 { 2304 return only_sign_bit_p (x, x.precision); 2305 } 2306 2307 /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL 2308 down to the previous value that has no bits set outside MASK. 2309 This rounding wraps for signed values if VAL is negative and 2310 the top bit of MASK is clear. 2311 2312 For example, round_down_for_mask (6, 0xf1) would give 1 and 2313 round_down_for_mask (24, 0xf1) would give 17. */ 2314 2315 wide_int 2316 wi::round_down_for_mask (const wide_int &val, const wide_int &mask) 2317 { 2318 /* Get the bits in VAL that are outside the mask. */ 2319 wide_int extra_bits = wi::bit_and_not (val, mask); 2320 if (extra_bits == 0) 2321 return val; 2322 2323 /* Get a mask that includes the top bit in EXTRA_BITS and is all 1s 2324 below that bit. */ 2325 unsigned int precision = val.get_precision (); 2326 wide_int lower_mask = wi::mask (precision - wi::clz (extra_bits), 2327 false, precision); 2328 2329 /* Clear the bits that aren't in MASK, but ensure that all bits 2330 in MASK below the top cleared bit are set. */ 2331 return (val & mask) | (mask & lower_mask); 2332 } 2333 2334 /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL 2335 up to the next value that has no bits set outside MASK. The rounding 2336 wraps if there are no suitable values greater than VAL. 2337 2338 For example, round_up_for_mask (6, 0xf1) would give 16 and 2339 round_up_for_mask (24, 0xf1) would give 32. */ 2340 2341 wide_int 2342 wi::round_up_for_mask (const wide_int &val, const wide_int &mask) 2343 { 2344 /* Get the bits in VAL that are outside the mask. */ 2345 wide_int extra_bits = wi::bit_and_not (val, mask); 2346 if (extra_bits == 0) 2347 return val; 2348 2349 /* Get a mask that is all 1s above the top bit in EXTRA_BITS. */ 2350 unsigned int precision = val.get_precision (); 2351 wide_int upper_mask = wi::mask (precision - wi::clz (extra_bits), 2352 true, precision); 2353 2354 /* Get the bits of the mask that are above the top bit in EXTRA_BITS. */ 2355 upper_mask &= mask; 2356 2357 /* Conceptually we need to: 2358 2359 - clear bits of VAL outside UPPER_MASK 2360 - add the lowest bit in UPPER_MASK to VAL (or add 0 if UPPER_MASK is 0) 2361 - propagate the carry through the bits of VAL in UPPER_MASK 2362 2363 If (~VAL & UPPER_MASK) is nonzero, the carry eventually 2364 reaches that bit and the process leaves all lower bits clear. 2365 If (~VAL & UPPER_MASK) is zero then the result is also zero. */ 2366 wide_int tmp = wi::bit_and_not (upper_mask, val); 2367 2368 return (val | tmp) & -tmp; 2369 } 2370 2371 /* Compute the modular multiplicative inverse of A modulo B 2372 using extended Euclid's algorithm. Assumes A and B are coprime, 2373 and that A and B have the same precision. */ 2374 wide_int 2375 wi::mod_inv (const wide_int &a, const wide_int &b) 2376 { 2377 /* Verify the assumption. */ 2378 gcc_checking_assert (wi::eq_p (wi::gcd (a, b), 1)); 2379 2380 unsigned int p = a.get_precision () + 1; 2381 gcc_checking_assert (b.get_precision () + 1 == p); 2382 wide_int c = wide_int::from (a, p, UNSIGNED); 2383 wide_int d = wide_int::from (b, p, UNSIGNED); 2384 wide_int x0 = wide_int::from (0, p, UNSIGNED); 2385 wide_int x1 = wide_int::from (1, p, UNSIGNED); 2386 2387 if (wi::eq_p (b, 1)) 2388 return wide_int::from (1, p, UNSIGNED); 2389 2390 while (wi::gt_p (c, 1, UNSIGNED)) 2391 { 2392 wide_int t = d; 2393 wide_int q = wi::divmod_trunc (c, d, UNSIGNED, &d); 2394 c = t; 2395 wide_int s = x0; 2396 x0 = wi::sub (x1, wi::mul (q, x0)); 2397 x1 = s; 2398 } 2399 if (wi::lt_p (x1, 0, SIGNED)) 2400 x1 += d; 2401 return x1; 2402 } 2403 2404 /* 2405 * Private utilities. 2406 */ 2407 2408 void gt_ggc_mx (widest_int *) { } 2409 void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { } 2410 void gt_pch_nx (widest_int *) { } 2411 2412 template void wide_int::dump () const; 2413 template void generic_wide_int <wide_int_ref_storage <false> >::dump () const; 2414 template void generic_wide_int <wide_int_ref_storage <true> >::dump () const; 2415 template void offset_int::dump () const; 2416 template void widest_int::dump () const; 2417 2418 /* We could add all the above ::dump variants here, but wide_int and 2419 widest_int should handle the common cases. Besides, you can always 2420 call the dump method directly. */ 2421 2422 DEBUG_FUNCTION void 2423 debug (const wide_int &ref) 2424 { 2425 ref.dump (); 2426 } 2427 2428 DEBUG_FUNCTION void 2429 debug (const wide_int *ptr) 2430 { 2431 if (ptr) 2432 debug (*ptr); 2433 else 2434 fprintf (stderr, "<nil>\n"); 2435 } 2436 2437 DEBUG_FUNCTION void 2438 debug (const widest_int &ref) 2439 { 2440 ref.dump (); 2441 } 2442 2443 DEBUG_FUNCTION void 2444 debug (const widest_int *ptr) 2445 { 2446 if (ptr) 2447 debug (*ptr); 2448 else 2449 fprintf (stderr, "<nil>\n"); 2450 } 2451 2452 #if CHECKING_P 2453 2454 namespace selftest { 2455 2456 /* Selftests for wide ints. We run these multiple times, once per type. */ 2457 2458 /* Helper function for building a test value. */ 2459 2460 template <class VALUE_TYPE> 2461 static VALUE_TYPE 2462 from_int (int i); 2463 2464 /* Specializations of the fixture for each wide-int type. */ 2465 2466 /* Specialization for VALUE_TYPE == wide_int. */ 2467 2468 template <> 2469 wide_int 2470 from_int (int i) 2471 { 2472 return wi::shwi (i, 32); 2473 } 2474 2475 /* Specialization for VALUE_TYPE == offset_int. */ 2476 2477 template <> 2478 offset_int 2479 from_int (int i) 2480 { 2481 return offset_int (i); 2482 } 2483 2484 /* Specialization for VALUE_TYPE == widest_int. */ 2485 2486 template <> 2487 widest_int 2488 from_int (int i) 2489 { 2490 return widest_int (i); 2491 } 2492 2493 /* Verify that print_dec (WI, ..., SGN) gives the expected string 2494 representation (using base 10). */ 2495 2496 static void 2497 assert_deceq (const char *expected, const wide_int_ref &wi, signop sgn) 2498 { 2499 char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf; 2500 unsigned len; 2501 if (print_dec_buf_size (wi, sgn, &len)) 2502 p = XALLOCAVEC (char, len); 2503 print_dec (wi, p, sgn); 2504 ASSERT_STREQ (expected, p); 2505 } 2506 2507 /* Likewise for base 16. */ 2508 2509 static void 2510 assert_hexeq (const char *expected, const wide_int_ref &wi) 2511 { 2512 char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf; 2513 unsigned len; 2514 if (print_hex_buf_size (wi, &len)) 2515 p = XALLOCAVEC (char, len); 2516 print_hex (wi, p); 2517 ASSERT_STREQ (expected, p); 2518 } 2519 2520 /* Test cases. */ 2521 2522 /* Verify that print_dec and print_hex work for VALUE_TYPE. */ 2523 2524 template <class VALUE_TYPE> 2525 static void 2526 test_printing () 2527 { 2528 VALUE_TYPE a = from_int<VALUE_TYPE> (42); 2529 assert_deceq ("42", a, SIGNED); 2530 assert_hexeq ("0x2a", a); 2531 assert_hexeq ("0x1fffffffffffffffff", wi::shwi (-1, 69)); 2532 assert_hexeq ("0xffffffffffffffff", wi::mask (64, false, 69)); 2533 assert_hexeq ("0xffffffffffffffff", wi::mask <widest_int> (64, false)); 2534 if (WIDE_INT_MAX_INL_PRECISION > 128) 2535 { 2536 assert_hexeq ("0x20000000000000000fffffffffffffffe", 2537 wi::lshift (1, 129) + wi::lshift (1, 64) - 2); 2538 assert_hexeq ("0x200000000000004000123456789abcdef", 2539 wi::lshift (1, 129) + wi::lshift (1, 74) 2540 + wi::lshift (0x1234567, 32) + 0x89abcdef); 2541 } 2542 } 2543 2544 /* Verify that various operations work correctly for VALUE_TYPE, 2545 unary and binary, using both function syntax, and 2546 overloaded-operators. */ 2547 2548 template <class VALUE_TYPE> 2549 static void 2550 test_ops () 2551 { 2552 VALUE_TYPE a = from_int<VALUE_TYPE> (7); 2553 VALUE_TYPE b = from_int<VALUE_TYPE> (3); 2554 2555 /* Using functions. */ 2556 assert_deceq ("-7", wi::neg (a), SIGNED); 2557 assert_deceq ("10", wi::add (a, b), SIGNED); 2558 assert_deceq ("4", wi::sub (a, b), SIGNED); 2559 assert_deceq ("-4", wi::sub (b, a), SIGNED); 2560 assert_deceq ("21", wi::mul (a, b), SIGNED); 2561 2562 /* Using operators. */ 2563 assert_deceq ("-7", -a, SIGNED); 2564 assert_deceq ("10", a + b, SIGNED); 2565 assert_deceq ("4", a - b, SIGNED); 2566 assert_deceq ("-4", b - a, SIGNED); 2567 assert_deceq ("21", a * b, SIGNED); 2568 } 2569 2570 /* Verify that various comparisons work correctly for VALUE_TYPE. */ 2571 2572 template <class VALUE_TYPE> 2573 static void 2574 test_comparisons () 2575 { 2576 VALUE_TYPE a = from_int<VALUE_TYPE> (7); 2577 VALUE_TYPE b = from_int<VALUE_TYPE> (3); 2578 2579 /* == */ 2580 ASSERT_TRUE (wi::eq_p (a, a)); 2581 ASSERT_FALSE (wi::eq_p (a, b)); 2582 2583 /* != */ 2584 ASSERT_TRUE (wi::ne_p (a, b)); 2585 ASSERT_FALSE (wi::ne_p (a, a)); 2586 2587 /* < */ 2588 ASSERT_FALSE (wi::lts_p (a, a)); 2589 ASSERT_FALSE (wi::lts_p (a, b)); 2590 ASSERT_TRUE (wi::lts_p (b, a)); 2591 2592 /* <= */ 2593 ASSERT_TRUE (wi::les_p (a, a)); 2594 ASSERT_FALSE (wi::les_p (a, b)); 2595 ASSERT_TRUE (wi::les_p (b, a)); 2596 2597 /* > */ 2598 ASSERT_FALSE (wi::gts_p (a, a)); 2599 ASSERT_TRUE (wi::gts_p (a, b)); 2600 ASSERT_FALSE (wi::gts_p (b, a)); 2601 2602 /* >= */ 2603 ASSERT_TRUE (wi::ges_p (a, a)); 2604 ASSERT_TRUE (wi::ges_p (a, b)); 2605 ASSERT_FALSE (wi::ges_p (b, a)); 2606 2607 /* comparison */ 2608 ASSERT_EQ (-1, wi::cmps (b, a)); 2609 ASSERT_EQ (0, wi::cmps (a, a)); 2610 ASSERT_EQ (1, wi::cmps (a, b)); 2611 } 2612 2613 /* Run all of the selftests, using the given VALUE_TYPE. */ 2614 2615 template <class VALUE_TYPE> 2616 static void run_all_wide_int_tests () 2617 { 2618 test_printing <VALUE_TYPE> (); 2619 test_ops <VALUE_TYPE> (); 2620 test_comparisons <VALUE_TYPE> (); 2621 } 2622 2623 /* Test overflow conditions. */ 2624 2625 static void 2626 test_overflow () 2627 { 2628 static int precs[] = { 31, 32, 33, 63, 64, 65, 127, 128 }; 2629 static int offsets[] = { 16, 1, 0 }; 2630 for (unsigned int i = 0; i < ARRAY_SIZE (precs); ++i) 2631 for (unsigned int j = 0; j < ARRAY_SIZE (offsets); ++j) 2632 { 2633 int prec = precs[i]; 2634 int offset = offsets[j]; 2635 wi::overflow_type overflow; 2636 wide_int sum, diff; 2637 2638 sum = wi::add (wi::max_value (prec, UNSIGNED) - offset, 1, 2639 UNSIGNED, &overflow); 2640 ASSERT_EQ (sum, -offset); 2641 ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0); 2642 2643 sum = wi::add (1, wi::max_value (prec, UNSIGNED) - offset, 2644 UNSIGNED, &overflow); 2645 ASSERT_EQ (sum, -offset); 2646 ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0); 2647 2648 diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset, 2649 wi::max_value (prec, UNSIGNED), 2650 UNSIGNED, &overflow); 2651 ASSERT_EQ (diff, -offset); 2652 ASSERT_EQ (overflow != wi::OVF_NONE, offset != 0); 2653 2654 diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset, 2655 wi::max_value (prec, UNSIGNED) - 1, 2656 UNSIGNED, &overflow); 2657 ASSERT_EQ (diff, 1 - offset); 2658 ASSERT_EQ (overflow != wi::OVF_NONE, offset > 1); 2659 } 2660 } 2661 2662 /* Test the round_{down,up}_for_mask functions. */ 2663 2664 static void 2665 test_round_for_mask () 2666 { 2667 unsigned int prec = 18; 2668 ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (17, prec), 2669 wi::shwi (0xf1, prec))); 2670 ASSERT_EQ (17, wi::round_up_for_mask (wi::shwi (17, prec), 2671 wi::shwi (0xf1, prec))); 2672 2673 ASSERT_EQ (1, wi::round_down_for_mask (wi::shwi (6, prec), 2674 wi::shwi (0xf1, prec))); 2675 ASSERT_EQ (16, wi::round_up_for_mask (wi::shwi (6, prec), 2676 wi::shwi (0xf1, prec))); 2677 2678 ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (24, prec), 2679 wi::shwi (0xf1, prec))); 2680 ASSERT_EQ (32, wi::round_up_for_mask (wi::shwi (24, prec), 2681 wi::shwi (0xf1, prec))); 2682 2683 ASSERT_EQ (0x011, wi::round_down_for_mask (wi::shwi (0x22, prec), 2684 wi::shwi (0x111, prec))); 2685 ASSERT_EQ (0x100, wi::round_up_for_mask (wi::shwi (0x22, prec), 2686 wi::shwi (0x111, prec))); 2687 2688 ASSERT_EQ (100, wi::round_down_for_mask (wi::shwi (101, prec), 2689 wi::shwi (0xfc, prec))); 2690 ASSERT_EQ (104, wi::round_up_for_mask (wi::shwi (101, prec), 2691 wi::shwi (0xfc, prec))); 2692 2693 ASSERT_EQ (0x2bc, wi::round_down_for_mask (wi::shwi (0x2c2, prec), 2694 wi::shwi (0xabc, prec))); 2695 ASSERT_EQ (0x800, wi::round_up_for_mask (wi::shwi (0x2c2, prec), 2696 wi::shwi (0xabc, prec))); 2697 2698 ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0xabd, prec), 2699 wi::shwi (0xabc, prec))); 2700 ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0xabd, prec), 2701 wi::shwi (0xabc, prec))); 2702 2703 ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0x1000, prec), 2704 wi::shwi (0xabc, prec))); 2705 ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0x1000, prec), 2706 wi::shwi (0xabc, prec))); 2707 } 2708 2709 /* Run all of the selftests within this file, for all value types. */ 2710 2711 void 2712 wide_int_cc_tests () 2713 { 2714 run_all_wide_int_tests <wide_int> (); 2715 run_all_wide_int_tests <offset_int> (); 2716 run_all_wide_int_tests <widest_int> (); 2717 test_overflow (); 2718 test_round_for_mask (); 2719 ASSERT_EQ (wi::mask (128, false, 128), 2720 wi::shifted_mask (0, 128, false, 128)); 2721 ASSERT_EQ (wi::mask (128, true, 128), 2722 wi::shifted_mask (0, 128, true, 128)); 2723 ASSERT_EQ (wi::multiple_of_p (from_int <widest_int> (1), 2724 from_int <widest_int> (-128), UNSIGNED), 2725 false); 2726 } 2727 2728 } // namespace selftest 2729 #endif /* CHECKING_P */ 2730
Indexes created Thu Oct 22 00:27:13 UTC 2026