contrib/gcc-8.0/gcc/wide-int.cc

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