LCOV - code coverage report
Current view: top level - gcc - wide-int.cc (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1025 1105 92.8 %
Date: 2020-04-04 11:58:09 Functions: 61 76 80.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.