LCOV - code coverage report
Current view: top level - gcc - wide-int.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 94.1 % 1251 1177
Test Date: 2026-11-14 16:39:50 Functions: 90.0 % 80 72
Legend: Lines:     hit not hit

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

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.