gcc/testsuite/

[official-gcc.git] / gcc / wide-int.cc

/* Operations with very long integers.
   Copyright (C) 2012-2013 Free Software Foundation, Inc.
   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.

GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "hwint.h"
#include "wide-int.h"
#include "tree.h"
#include "dumpfile.h"

#define W_TYPE_SIZE HOST_BITS_PER_WIDE_INT
#if GCC_VERSION >= 3000 && (W_TYPE_SIZE == 32 || defined (__SIZEOF_INT128__))
typedef unsigned HOST_HALF_WIDE_INT UHWtype;
typedef unsigned HOST_WIDE_INT UWtype;
typedef unsigned int UQItype __attribute__ ((mode (QI)));
typedef unsigned int USItype __attribute__ ((mode (SI)));
typedef unsigned int UDItype __attribute__ ((mode (DI)));
#if W_TYPE_SIZE == 32
typedef unsigned int UDWtype __attribute__ ((mode (DI)));
#else
typedef unsigned int UDWtype __attribute__ ((mode (TI)));
#endif
#include "longlong.h"
#endif

static const HOST_WIDE_INT zeros[WIDE_INT_MAX_ELTS] = {};

/*
 * Internal utilities.
 */

/* Quantities to deal with values that hold half of a wide int.  Used
   in multiply and divide.  */
#define HALF_INT_MASK (((HOST_WIDE_INT) 1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)

#define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
#define BLOCKS_NEEDED(PREC) \
  (PREC ? (((PREC) + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT) : 1)
#define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0)

/* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
   based on the top existing bit of VAL. */

static unsigned HOST_WIDE_INT
safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i)
{
  return i < len ? val[i] : val[len - 1] < 0 ? (HOST_WIDE_INT) -1 : 0;
}

/* Convert the integer in VAL to canonical form, returning its new length.
   LEN is the number of blocks currently in VAL and PRECISION is the number
   of bits in the integer it represents.

   This function only changes the representation, not the value.  */
static unsigned int
canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision)
{
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  HOST_WIDE_INT top;
  int i;

  if (len > blocks_needed)
    len = blocks_needed;

  if (len == 1)
    return len;

  top = val[len - 1];
  if (len * HOST_BITS_PER_WIDE_INT > precision)
    val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT);
  if (top != 0 && top != (HOST_WIDE_INT)-1)
    return len;

  /* At this point we know that the top is either 0 or -1.  Find the
     first block that is not a copy of this.  */
  for (i = len - 2; i >= 0; i--)
    {
      HOST_WIDE_INT x = val[i];
      if (x != top)
        {
          if (SIGN_MASK (x) == top)
            return i + 1;

          /* We need an extra block because the top bit block i does
             not match the extension.  */
          return i + 2;
        }
    }

  /* The number is 0 or -1.  */
  return 1;
}

/*
 * Conversion routines in and out of wide_int.
 */

/* Copy XLEN elements from XVAL to VAL.  If NEED_CANON, canonize the
   result for an integer with precision PRECISION.  Return the length
   of VAL (after any canonization.  */
unsigned int
wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                unsigned int xlen, unsigned int precision, bool need_canon)
{
  for (unsigned i = 0; i < xlen; i++)
    val[i] = xval[i];
  return need_canon ? canonize (val, xlen, precision) : xlen;
}

/* Construct a wide int from a buffer of length LEN.  BUFFER will be
   read according to byte endianess and word endianess of the target.
   Only the lower BUFFER_LEN bytes of the result are set; the remaining
   high bytes are cleared.  */
wide_int
wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len)
{
  unsigned int precision = buffer_len * BITS_PER_UNIT;
  wide_int result = wide_int::create (precision);
  unsigned int words = buffer_len / UNITS_PER_WORD;

  /* We have to clear all the bits ourself, as we merely or in values
     below.  */
  unsigned int len = BLOCKS_NEEDED (precision);
  HOST_WIDE_INT *val = result.write_val ();
  for (unsigned int i = 0; i < len; ++i)
    val[i] = 0;

  for (unsigned int byte = 0; byte < buffer_len; byte++)
    {
      unsigned int offset;
      unsigned int index;
      unsigned int bitpos = byte * BITS_PER_UNIT;
      unsigned HOST_WIDE_INT value;

      if (buffer_len > UNITS_PER_WORD)
        {
          unsigned int word = byte / UNITS_PER_WORD;

          if (WORDS_BIG_ENDIAN)
            word = (words - 1) - word;

          offset = word * UNITS_PER_WORD;

          if (BYTES_BIG_ENDIAN)
            offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
          else
            offset += byte % UNITS_PER_WORD;
        }
      else
        offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte;

      value = (unsigned HOST_WIDE_INT) buffer[offset];

      index = bitpos / HOST_BITS_PER_WIDE_INT;
      val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT);
    }

  result.set_len (canonize (val, len, precision));

  return result;
}

/* Sets RESULT from X, the sign is taken according to SGN.  */
void
wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn)
{
  int len = x.get_len ();
  const HOST_WIDE_INT *v = x.get_val ();
  int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision ();

  if (wi::neg_p (x, sgn))
    {
      /* We use ones complement to avoid -x80..0 edge case that -
         won't work on.  */
      HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
      for (int i = 0; i < len; i++)
        t[i] = ~v[i];
      if (excess > 0)
        t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess;
      mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
      mpz_com (result, result);
    }
  else if (excess > 0)
    {
      HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
      for (int i = 0; i < len - 1; i++)
        t[i] = v[i];
      t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess;
      mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
    }
  else
    mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v);
}

/* Returns X converted to TYPE.  If WRAP is true, then out-of-range
   values of VAL will be wrapped; otherwise, they will be set to the
   appropriate minimum or maximum TYPE bound.  */
wide_int
wi::from_mpz (const_tree type, mpz_t x, bool wrap)
{
  size_t count, numb;
  int prec = TYPE_PRECISION (type);
  wide_int res = wide_int::create (prec);

  if (!wrap)
    {
      mpz_t min, max;

      mpz_init (min);
      mpz_init (max);
      get_type_static_bounds (type, min, max);

      if (mpz_cmp (x, min) < 0)
        mpz_set (x, min);
      else if (mpz_cmp (x, max) > 0)
        mpz_set (x, max);

      mpz_clear (min);
      mpz_clear (max);
    }

  /* Determine the number of unsigned HOST_WIDE_INTs that are required
     for representing the value.  The code to calculate count is
     extracted from the GMP manual, section "Integer Import and Export":
     http://gmplib.org/manual/Integer-Import-and-Export.html  */
  numb = 8 * sizeof(HOST_WIDE_INT);
  count = (mpz_sizeinbase (x, 2) + numb - 1) / numb;
  HOST_WIDE_INT *val = res.write_val ();
  mpz_export (val, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x);
  if (count < 1)
    {
      val[0] = 0;
      count = 1;
    }
  res.set_len (count);

  if (mpz_sgn (x) < 0)
    res = -res;

  return res;
}

/*
 * Largest and smallest values in a mode.
 */

/* Return the largest SGNed number that is representable in PRECISION bits.

   TODO: There is still code from the double_int era that trys to
   make up for the fact that double int's could not represent the
   min and max values of all types.  This code should be removed
   because the min and max values can always be represented in
   wide_ints and int-csts.  */
wide_int
wi::max_value (unsigned int precision, signop sgn)
{
  gcc_checking_assert (precision != 0);
  if (sgn == UNSIGNED)
    /* The unsigned max is just all ones.  */
    return shwi (-1, precision);
  else
    /* The signed max is all ones except the top bit.  This must be
       explicitly represented.  */
    return mask (precision - 1, false, precision);
}

/* Return the largest SGNed number that is representable in PRECISION bits.  */
wide_int
wi::min_value (unsigned int precision, signop sgn)
{
  gcc_checking_assert (precision != 0);
  if (sgn == UNSIGNED)
    return uhwi (0, precision);
  else
    /* The signed min is all zeros except the top bit.  This must be
       explicitly represented.  */
    return wi::set_bit_in_zero (precision - 1, precision);
}

/*
 * Public utilities.
 */

/* Convert the number represented by XVAL, XLEN and XPRECISION, which has
   signedness SGN, to an integer that has PRECISION bits.  Store the blocks
   in VAL and return the number of blocks used.

   This function can handle both extension (PRECISION > XPRECISION)
   and truncation (PRECISION < XPRECISION).  */
unsigned int
wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                   unsigned int xlen, unsigned int xprecision,
                   unsigned int precision, signop sgn)
{
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  unsigned int len = blocks_needed < xlen ? blocks_needed : xlen;
  for (unsigned i = 0; i < len; i++)
    val[i] = xval[i];

  if (precision > xprecision)
    {
      unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT;

      /* Expanding.  */
      if (sgn == UNSIGNED)
        {
          if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
            val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
          else if (val[len - 1] < 0)
            {
              while (len < BLOCKS_NEEDED (xprecision))
                val[len++] = -1;
              if (small_xprecision)
                val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
              else
                val[len++] = 0;
            }
        }
      else
        {
          if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
            val[len - 1] = sext_hwi (val[len - 1], small_xprecision);
        }
    }
  len = canonize (val, len, precision);

  return len;
}

/* This function hides the fact that we cannot rely on the bits beyond
   the precision.  This issue comes up in the relational comparisions
   where we do allow comparisons of values of different precisions.  */
static inline HOST_WIDE_INT
selt (const HOST_WIDE_INT *a, unsigned int len,
      unsigned int blocks_needed, unsigned int small_prec,
      unsigned int index, signop sgn)
{
  HOST_WIDE_INT val;
  if (index < len)
    val = a[index];
  else if (index < blocks_needed || sgn == SIGNED)
    /* Signed or within the precision.  */
    val = SIGN_MASK (a[len - 1]);
  else
    /* Unsigned extension beyond the precision. */
    val = 0;

  if (small_prec && index == blocks_needed - 1)
    return (sgn == SIGNED
            ? sext_hwi (val, small_prec)
            : zext_hwi (val, small_prec));
  else
    return val;
}

/* Find the highest bit represented in a wide int.  This will in
   general have the same value as the sign bit.  */
static inline HOST_WIDE_INT
top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec)
{
  int excess = len * HOST_BITS_PER_WIDE_INT - prec;
  unsigned HOST_WIDE_INT val = a[len - 1];
  if (excess > 0)
    val <<= excess;
  return val >> (HOST_BITS_PER_WIDE_INT - 1);
}

/*
 * Comparisons, note that only equality is an operator.  The other
 * comparisons cannot be operators since they are inherently signed or
 * unsigned and C++ has no such operators.
 */

/* Return true if OP0 == OP1.  */
bool
wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
                const HOST_WIDE_INT *op1, unsigned int op1len,
                unsigned int prec)
{
  int l0 = op0len - 1;
  unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);

  if (op0len != op1len)
    return false;

  if (op0len == BLOCKS_NEEDED (prec) && small_prec)
    {
      /* It does not matter if we zext or sext here, we just have to
         do both the same way.  */
      if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec))
        return false;
      l0--;
    }

  while (l0 >= 0)
    if (op0[l0] != op1[l0])
      return false;
    else
      l0--;

  return true;
}

/* Return true if OP0 < OP1 using signed comparisons.  */
bool
wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
                 unsigned int precision,
                 const HOST_WIDE_INT *op1, unsigned int op1len)
{
  HOST_WIDE_INT s0, s1;
  unsigned HOST_WIDE_INT u0, u1;
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
  int l = MAX (op0len - 1, op1len - 1);

  /* Only the top block is compared as signed.  The rest are unsigned
     comparisons.  */
  s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
  s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
  if (s0 < s1)
    return true;
  if (s0 > s1)
    return false;

  l--;
  while (l >= 0)
    {
      u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
      u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);

      if (u0 < u1)
        return true;
      if (u0 > u1)
        return false;
      l--;
    }

  return false;
}

/* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
   signed compares.  */
int
wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len,
                unsigned int precision,
                const HOST_WIDE_INT *op1, unsigned int op1len)
{
  HOST_WIDE_INT s0, s1;
  unsigned HOST_WIDE_INT u0, u1;
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
  int l = MAX (op0len - 1, op1len - 1);

  /* Only the top block is compared as signed.  The rest are unsigned
     comparisons.  */
  s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
  s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
  if (s0 < s1)
    return -1;
  if (s0 > s1)
    return 1;

  l--;
  while (l >= 0)
    {
      u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
      u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);

      if (u0 < u1)
        return -1;
      if (u0 > u1)
        return 1;
      l--;
    }

  return 0;
}

/* Return true if OP0 < OP1 using unsigned comparisons.  */
bool
wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
                 unsigned int precision,
                 const HOST_WIDE_INT *op1, unsigned int op1len)
{
  unsigned HOST_WIDE_INT x0;
  unsigned HOST_WIDE_INT x1;
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
  int l = MAX (op0len - 1, op1len - 1);

  while (l >= 0)
    {
      x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
      x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
      if (x0 < x1)
        return true;
      if (x0 > x1)
        return false;
      l--;
    }

  return false;
}

/* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
   unsigned compares.  */
int
wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len,
                unsigned int precision,
                const HOST_WIDE_INT *op1, unsigned int op1len)
{
  unsigned HOST_WIDE_INT x0;
  unsigned HOST_WIDE_INT x1;
  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
  unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
  int l = MAX (op0len - 1, op1len - 1);

  while (l >= 0)
    {
      x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
      x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
      if (x0 < x1)
        return -1;
      if (x0 > x1)
        return 1;
      l--;
    }

  return 0;
}

/*
 * Extension.
 */

/* Sign-extend the number represented by XVAL and XLEN into VAL,
   starting at OFFSET.  Return the number of blocks in VAL.  Both XVAL
   and VAL have PRECISION bits.  */
unsigned int
wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                unsigned int xlen, unsigned int precision, unsigned int offset)
{
  unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
  /* Extending beyond the precision is a no-op.  If we have only stored
     OFFSET bits or fewer, the rest are already signs.  */
  if (offset >= precision || len >= xlen)
    {
      for (unsigned i = 0; i < xlen; ++i)
        val[i] = xval[i];
      return xlen;
    }
  unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
  for (unsigned int i = 0; i < len; i++)
    val[i] = xval[i];
  if (suboffset > 0)
    {
      val[len] = sext_hwi (xval[len], suboffset);
      len += 1;
    }
  return canonize (val, len, precision);
}

/* Zero-extend the number represented by XVAL and XLEN into VAL,
   starting at OFFSET.  Return the number of blocks in VAL.  Both XVAL
   and VAL have PRECISION bits.  */
unsigned int
wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                unsigned int xlen, unsigned int precision, unsigned int offset)
{
  unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
  /* Extending beyond the precision is a no-op.  If we have only stored
     OFFSET bits or fewer, and the upper stored bit is zero, then there
     is nothing to do.  */
  if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0))
    {
      for (unsigned i = 0; i < xlen; ++i)
        val[i] = xval[i];
      return xlen;
    }
  unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
  for (unsigned int i = 0; i < len; i++)
    val[i] = i < xlen ? xval[i] : -1;
  if (suboffset > 0)
    val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset);
  else
    val[len] = 0;
  return canonize (val, len + 1, precision);
}

/*
 * Masking, inserting, shifting, rotating.
 */

/* Insert WIDTH bits from Y into X starting at START.  */
wide_int
wi::insert (const wide_int &x, const wide_int &y, unsigned int start,
            unsigned int width)
{
  wide_int result;
  wide_int mask;
  wide_int tmp;

  unsigned int precision = x.get_precision ();
  if (start >= precision)
    return x;

  gcc_checking_assert (precision >= width);

  if (start + width >= precision)
    width = precision - start;

  mask = wi::shifted_mask (start, width, false, precision);
  tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start);
  result = tmp & mask;

  tmp = wi::bit_and_not (x, mask);
  result = result | tmp;

  return result;
}

/* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT.
   Return the number of blocks in VAL.  Both XVAL and VAL have PRECISION
   bits.  */
unsigned int
wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                   unsigned int xlen, unsigned int precision, unsigned int bit)
{
  unsigned int block = bit / HOST_BITS_PER_WIDE_INT;
  unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT;

  if (block + 1 >= xlen)
    {
      /* The operation either affects the last current block or needs
         a new block.  */
      unsigned int len = block + 1;
      for (unsigned int i = 0; i < len; i++)
        val[i] = safe_uhwi (xval, xlen, i);
      val[block] |= (unsigned HOST_WIDE_INT) 1 << subbit;

      /* If the bit we just set is at the msb of the block, make sure
         that any higher bits are zeros.  */
      if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1)
        val[len++] = 0;
      return len;
    }
  else
    {
      for (unsigned int i = 0; i < xlen; i++)
        val[i] = xval[i];
      val[block] |= (unsigned HOST_WIDE_INT) 1 << subbit;
      return canonize (val, xlen, precision);
    }
}

/* bswap THIS.  */
wide_int
wide_int_storage::bswap () const
{
  wide_int result = wide_int::create (precision);
  unsigned int i, s;
  unsigned int len = BLOCKS_NEEDED (precision);
  unsigned int xlen = get_len ();
  const HOST_WIDE_INT *xval = get_val ();
  HOST_WIDE_INT *val = result.write_val ();

  /* This is not a well defined operation if the precision is not a
     multiple of 8.  */
  gcc_assert ((precision & 0x7) == 0);

  for (i = 0; i < len; i++)
    val[i] = 0;

  /* Only swap the bytes that are not the padding.  */
  for (s = 0; s < precision; s += 8)
    {
      unsigned int d = precision - s - 8;
      unsigned HOST_WIDE_INT byte;

      unsigned int block = s / HOST_BITS_PER_WIDE_INT;
      unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);

      byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff;

      block = d / HOST_BITS_PER_WIDE_INT;
      offset = d & (HOST_BITS_PER_WIDE_INT - 1);

      val[block] |= byte << offset;
    }

  result.set_len (canonize (val, len, precision));
  return result;
}

/* Fill VAL with a mask where the lower WIDTH bits are ones and the bits
   above that up to PREC are zeros.  The result is inverted if NEGATE
   is true.  Return the number of blocks in VAL.  */
unsigned int
wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate,
          unsigned int prec)
{
  if (width >= prec)
    {
      val[0] = negate ? 0 : -1;
      return 1;
    }
  else if (width == 0)
    {
      val[0] = negate ? -1 : 0;
      return 1;
    }

  unsigned int i = 0;
  while (i < width / HOST_BITS_PER_WIDE_INT)
    val[i++] = negate ? 0 : -1;

  unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1);
  if (shift != 0)
    {
      HOST_WIDE_INT last = ((unsigned HOST_WIDE_INT) 1 << shift) - 1;
      val[i++] = negate ? ~last : last;
    }
  else
    val[i++] = negate ? -1 : 0;

  return i;
}

/* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH
   bits are ones, and the bits above that up to PREC are zeros.  The result
   is inverted if NEGATE is true.  Return the number of blocks in VAL.  */
unsigned int
wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width,
                  bool negate, unsigned int prec)
{
  if (start >= prec || width == 0)
    {
      val[0] = negate ? -1 : 0;
      return 1;
    }

  if (width > prec - start)
    width = prec - start;
  unsigned int end = start + width;

  unsigned int i = 0;
  while (i < start / HOST_BITS_PER_WIDE_INT)
    val[i++] = negate ? -1 : 0;

  unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1);
  if (shift)
    {
      HOST_WIDE_INT block = ((unsigned HOST_WIDE_INT) 1 << shift) - 1;
      shift += width;
      if (shift < HOST_BITS_PER_WIDE_INT)
        {
          /* case 000111000 */
          block = ((unsigned HOST_WIDE_INT) 1 << shift) - block - 1;
          val[i++] = negate ? ~block : block;
          return i;
        }
      else
        /* ...111000 */
        val[i++] = negate ? block : ~block;
    }

  while (i < end / HOST_BITS_PER_WIDE_INT)
    /* 1111111 */
    val[i++] = negate ? 0 : -1;

  shift = end & (HOST_BITS_PER_WIDE_INT - 1);
  if (shift != 0)
    {
      /* 000011111 */
      HOST_WIDE_INT block = ((unsigned HOST_WIDE_INT) 1 << shift) - 1;
      val[i++] = negate ? ~block : block;
    }
  else if (end < prec)
    val[i++] = negate ? -1 : 0;

  return i;
}

/*
 * logical operations.
 */

/* Set VAL to OP0 & OP1.  Return the number of blocks used.  */
unsigned int
wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
               unsigned int op0len, const HOST_WIDE_INT *op1,
               unsigned int op1len, unsigned int prec)
{
  int l0 = op0len - 1;
  int l1 = op1len - 1;
  bool need_canon = true;

  unsigned int len = MAX (op0len, op1len);
  if (l0 > l1)
    {
      HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
      if (op1mask == 0)
        {
          l0 = l1;
          len = l1 + 1;
        }
      else
        {
          need_canon = false;
          while (l0 > l1)
            {
              val[l0] = op0[l0];
              l0--;
            }
        }
    }
  else if (l1 > l0)
    {
      HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
      if (op0mask == 0)
        len = l0 + 1;
      else
        {
          need_canon = false;
          while (l1 > l0)
            {
              val[l1] = op1[l1];
              l1--;
            }
        }
    }

  while (l0 >= 0)
    {
      val[l0] = op0[l0] & op1[l0];
      l0--;
    }

  if (need_canon)
    len = canonize (val, len, prec);

  return len;
}

/* Set VAL to OP0 & ~OP1.  Return the number of blocks used.  */
unsigned int
wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
                   unsigned int op0len, const HOST_WIDE_INT *op1,
                   unsigned int op1len, unsigned int prec)
{
  wide_int result;
  int l0 = op0len - 1;
  int l1 = op1len - 1;
  bool need_canon = true;

  unsigned int len = MAX (op0len, op1len);
  if (l0 > l1)
    {
      HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
      if (op1mask != 0)
        {
          l0 = l1;
          len = l1 + 1;
        }
      else
        {
          need_canon = false;
          while (l0 > l1)
            {
              val[l0] = op0[l0];
              l0--;
            }
        }
    }
  else if (l1 > l0)
    {
      HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
      if (op0mask == 0)
        len = l0 + 1;
      else
        {
          need_canon = false;
          while (l1 > l0)
            {
              val[l1] = ~op1[l1];
              l1--;
            }
        }
    }

  while (l0 >= 0)
    {
      val[l0] = op0[l0] & ~op1[l0];
      l0--;
    }

  if (need_canon)
    len = canonize (val, len, prec);

  return len;
}

/* Set VAL to OP0 | OP1.  Return the number of blocks used.  */
unsigned int
wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
              unsigned int op0len, const HOST_WIDE_INT *op1,
              unsigned int op1len, unsigned int prec)
{
  wide_int result;
  int l0 = op0len - 1;
  int l1 = op1len - 1;
  bool need_canon = true;

  unsigned int len = MAX (op0len, op1len);
  if (l0 > l1)
    {
      HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
      if (op1mask != 0)
        {
          l0 = l1;
          len = l1 + 1;
        }
      else
        {
          need_canon = false;
          while (l0 > l1)
            {
              val[l0] = op0[l0];
              l0--;
            }
        }
    }
  else if (l1 > l0)
    {
      HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
      if (op0mask != 0)
        len = l0 + 1;
      else
        {
          need_canon = false;
          while (l1 > l0)
            {
              val[l1] = op1[l1];
              l1--;
            }
        }
    }

  while (l0 >= 0)
    {
      val[l0] = op0[l0] | op1[l0];
      l0--;
    }

  if (need_canon)
    len = canonize (val, len, prec);

  return len;
}

/* Set VAL to OP0 | ~OP1.  Return the number of blocks used.  */
unsigned int
wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
                  unsigned int op0len, const HOST_WIDE_INT *op1,
                  unsigned int op1len, unsigned int prec)
{
  wide_int result;
  int l0 = op0len - 1;
  int l1 = op1len - 1;
  bool need_canon = true;

  unsigned int len = MAX (op0len, op1len);
  if (l0 > l1)
    {
      HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
      if (op1mask == 0)
        {
          l0 = l1;
          len = l1 + 1;
        }
      else
        {
          need_canon = false;
          while (l0 > l1)
            {
              val[l0] = op0[l0];
              l0--;
            }
        }
    }
  else if (l1 > l0)
    {
      HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
      if (op0mask != 0)
        len = l0 + 1;
      else
        {
          need_canon = false;
          while (l1 > l0)
            {
              val[l1] = ~op1[l1];
              l1--;
            }
        }
    }

  while (l0 >= 0)
    {
      val[l0] = op0[l0] | ~op1[l0];
      l0--;
    }

  if (need_canon)
    len = canonize (val, len, prec);

  return len;
}

/* Set VAL to OP0 ^ OP1.  Return the number of blocks used.  */
unsigned int
wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
               unsigned int op0len, const HOST_WIDE_INT *op1,
               unsigned int op1len, unsigned int prec)
{
  wide_int result;
  int l0 = op0len - 1;
  int l1 = op1len - 1;

  unsigned int len = MAX (op0len, op1len);
  if (l0 > l1)
    {
      HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
      while (l0 > l1)
        {
          val[l0] = op0[l0] ^ op1mask;
          l0--;
        }
    }

  if (l1 > l0)
    {
      HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
      while (l1 > l0)
        {
          val[l1] = op0mask ^ op1[l1];
          l1--;
        }
    }

  while (l0 >= 0)
    {
      val[l0] = op0[l0] ^ op1[l0];
      l0--;
    }

  return canonize (val, len, prec);
}

/*
 * math
 */

/* Set VAL to OP0 + OP1.  If OVERFLOW is nonnull, record in *OVERFLOW
   whether the result overflows when OP0 and OP1 are treated as having
   signedness SGN.  Return the number of blocks in VAL.  */
unsigned int
wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
               unsigned int op0len, const HOST_WIDE_INT *op1,
               unsigned int op1len, unsigned int prec,
               signop sgn, bool *overflow)
{
  unsigned HOST_WIDE_INT o0 = 0;
  unsigned HOST_WIDE_INT o1 = 0;
  unsigned HOST_WIDE_INT x = 0;
  unsigned HOST_WIDE_INT carry = 0;
  unsigned HOST_WIDE_INT old_carry = 0;
  unsigned HOST_WIDE_INT mask0, mask1;
  unsigned int i;

  unsigned int len = MAX (op0len, op1len);
  mask0 = -top_bit_of (op0, op0len, prec);
  mask1 = -top_bit_of (op1, op1len, prec);
  /* Add all of the explicitly defined elements.  */

  for (i = 0; i < len; i++)
    {
      o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0;
      o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1;
      x = o0 + o1 + carry;
      val[i] = x;
      old_carry = carry;
      carry = carry == 0 ? x < o0 : x <= o0;
    }

  if (len * HOST_BITS_PER_WIDE_INT < prec)
    {
      val[len] = mask0 + mask1 + carry;
      len++;
      if (overflow)
        *overflow = false;
    }
  else if (overflow)
    {
      unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
      if (sgn == SIGNED)
        {
          unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1);
          *overflow = (HOST_WIDE_INT) (x << shift) < 0;
        }
      else
        {
          /* Put the MSB of X and O0 and in the top of the HWI.  */
          x <<= shift;
          o0 <<= shift;
          if (old_carry)
            *overflow = (x <= o0);
          else
            *overflow = (x < o0);
        }
    }

  return canonize (val, len, prec);
}

/* Subroutines of the multiplication and division operations.  Unpack
   the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
   HOST_HALF_WIDE_INTs of RESULT.  The rest of RESULT is filled by
   uncompressing the top bit of INPUT[IN_LEN - 1].  */
static void
wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
           unsigned int in_len, unsigned int out_len,
           unsigned int prec, signop sgn)
{
  unsigned int i;
  unsigned int j = 0;
  unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
  unsigned int blocks_needed = BLOCKS_NEEDED (prec);
  HOST_WIDE_INT mask;

  if (sgn == SIGNED)
    {
      mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec);
      mask &= HALF_INT_MASK;
    }
  else
    mask = 0;

  for (i = 0; i < blocks_needed - 1; i++)
    {
      HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
      result[j++] = x;
      result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
    }

  HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
  if (small_prec)
    {
      if (sgn == SIGNED)
        x = sext_hwi (x, small_prec);
      else
        x = zext_hwi (x, small_prec);
    }
  result[j++] = x;
  result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;

  /* Smear the sign bit.  */
  while (j < out_len)
    result[j++] = mask;
}

/* The inverse of wi_unpack.  IN_LEN is the the number of input
   blocks.  The number of output blocks will be half this amount.  */
static void
wi_pack (unsigned HOST_WIDE_INT *result,
         const unsigned HOST_HALF_WIDE_INT *input,
         unsigned int in_len)
{
  unsigned int i = 0;
  unsigned int j = 0;

  while (i + 2 < in_len)
    {
      result[j++] = (unsigned HOST_WIDE_INT)input[i]
        | ((unsigned HOST_WIDE_INT)input[i + 1]
           << HOST_BITS_PER_HALF_WIDE_INT);
      i += 2;
    }

  /* Handle the case where in_len is odd.   For this we zero extend.  */
  if (in_len & 1)
    result[j++] = (unsigned HOST_WIDE_INT)input[i];
  else
    result[j++] = (unsigned HOST_WIDE_INT)input[i]
      | ((unsigned HOST_WIDE_INT)input[i + 1] << HOST_BITS_PER_HALF_WIDE_INT);
}

/* Multiply Op1 by Op2.  If HIGH is set, only the upper half of the
   result is returned.  

   If HIGH is not set, throw away the upper half after the check is
   made to see if it overflows.  Unfortunately there is no better way
   to check for overflow than to do this.  If OVERFLOW is nonnull,
   record in *OVERFLOW whether the result overflowed.  SGN controls
   the signedness and is used to check overflow or if HIGH is set.  */
unsigned int
wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val,
                  unsigned int op1len, const HOST_WIDE_INT *op2val,
                  unsigned int op2len, unsigned int prec, signop sgn,
                  bool *overflow, bool high)
{
  unsigned HOST_WIDE_INT o0, o1, k, t;
  unsigned int i;
  unsigned int j;
  unsigned int blocks_needed = BLOCKS_NEEDED (prec);
  unsigned int half_blocks_needed = blocks_needed * 2;
  /* The sizes here are scaled to support a 2x largest mode by 2x
     largest mode yielding a 4x largest mode result.  This is what is
     needed by vpn.  */

  unsigned HOST_HALF_WIDE_INT
    u[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  unsigned HOST_HALF_WIDE_INT
    v[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  /* The '2' in 'R' is because we are internally doing a full
     multiply.  */
  unsigned HOST_HALF_WIDE_INT
    r[2 * 4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  HOST_WIDE_INT mask = ((HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT) - 1;

  /* If the top level routine did not really pass in an overflow, then
     just make sure that we never attempt to set it.  */
  bool needs_overflow = (overflow != 0);
  if (needs_overflow)
    *overflow = false;

  wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec);
  wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec);

  /* This is a surprisingly common case, so do it first.  */
  if (op1 == 0 || op2 == 0)
    {
      val[0] = 0;
      return 1;
    }

#ifdef umul_ppmm
  if (sgn == UNSIGNED)
    {
      /* If the inputs are single HWIs and the output has room for at
         least two HWIs, we can use umul_ppmm directly.  */
      if (prec >= HOST_BITS_PER_WIDE_INT * 2
          && wi::fits_uhwi_p (op1)
          && wi::fits_uhwi_p (op2))
        {
          umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ());
          return 1 + (val[1] != 0 || val[0] < 0);
        }
      /* Likewise if the output is a full single HWI, except that the
         upper HWI of the result is only used for determining overflow.
         (We handle this case inline when overflow isn't needed.)  */
      else if (prec == HOST_BITS_PER_WIDE_INT)
        {
          unsigned HOST_WIDE_INT upper;
          umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ());
          if (needs_overflow)
            *overflow = (upper != 0);
          return 1;
        }
    }
#endif

  /* Handle multiplications by 1.  */
  if (op1 == 1)
    {
      for (i = 0; i < op2len; i++)
        val[i] = op2val[i];
      return op2len;
    }
  if (op2 == 1)
    {
      for (i = 0; i < op1len; i++)
        val[i] = op1val[i];
      return op1len;
    }

  /* If we need to check for overflow, we can only do half wide
     multiplies quickly because we need to look at the top bits to
     check for the overflow.  */
  if ((high || needs_overflow)
      && (prec <= HOST_BITS_PER_HALF_WIDE_INT))
    {
      unsigned HOST_WIDE_INT r;

      if (sgn == SIGNED)
        {
          o0 = op1.to_shwi ();
          o1 = op2.to_shwi ();
        }
      else
        {
          o0 = op1.to_uhwi ();
          o1 = op2.to_uhwi ();
        }

      r = o0 * o1;
      if (needs_overflow)
        {
          if (sgn == SIGNED)
            {
              if ((HOST_WIDE_INT) r != sext_hwi (r, prec))
                *overflow = true;
            }
          else
            {
              if ((r >> prec) != 0)
                *overflow = true;
            }
        }
      val[0] = high ? r >> prec : r;
      return 1;
    }

  /* We do unsigned mul and then correct it.  */
  wi_unpack (u, op1val, op1len, half_blocks_needed, prec, SIGNED);
  wi_unpack (v, op2val, op2len, half_blocks_needed, prec, SIGNED);

  /* The 2 is for a full mult.  */
  memset (r, 0, half_blocks_needed * 2
          * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT);

  for (j = 0; j < half_blocks_needed; j++)
    {
      k = 0;
      for (i = 0; i < half_blocks_needed; i++)
        {
          t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j]
               + r[i + j] + k);
          r[i + j] = t & HALF_INT_MASK;
          k = t >> HOST_BITS_PER_HALF_WIDE_INT;
        }
      r[j + half_blocks_needed] = k;
    }

  /* We did unsigned math above.  For signed we must adjust the
     product (assuming we need to see that).  */
  if (sgn == SIGNED && (high || needs_overflow))
    {
      unsigned HOST_WIDE_INT b;
      if (wi::neg_p (op1))
        {
          b = 0;
          for (i = 0; i < half_blocks_needed; i++)
            {
              t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
                - (unsigned HOST_WIDE_INT)v[i] - b;
              r[i + half_blocks_needed] = t & HALF_INT_MASK;
              b = t >> (HOST_BITS_PER_WIDE_INT - 1);
            }
        }
      if (wi::neg_p (op2))
        {
          b = 0;
          for (i = 0; i < half_blocks_needed; i++)
            {
              t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
                - (unsigned HOST_WIDE_INT)u[i] - b;
              r[i + half_blocks_needed] = t & HALF_INT_MASK;
              b = t >> (HOST_BITS_PER_WIDE_INT - 1);
            }
        }
    }

  if (needs_overflow)
    {
      HOST_WIDE_INT top;

      /* For unsigned, overflow is true if any of the top bits are set.
         For signed, overflow is true if any of the top bits are not equal
         to the sign bit.  */
      if (sgn == UNSIGNED)
        top = 0;
      else
        {
          top = r[(half_blocks_needed) - 1];
          top = SIGN_MASK (top << (HOST_BITS_PER_WIDE_INT / 2));
          top &= mask;
        }

      for (i = half_blocks_needed; i < half_blocks_needed * 2; i++)
        if (((HOST_WIDE_INT)(r[i] & mask)) != top)
          *overflow = true;
    }

  if (high)
    {
      /* compute [prec] <- ([prec] * [prec]) >> [prec] */
      wi_pack ((unsigned HOST_WIDE_INT *) val,
               &r[half_blocks_needed], half_blocks_needed);
      return canonize (val, blocks_needed, prec);
    }
  else
    {
      /* compute [prec] <- ([prec] * [prec]) && ((1 << [prec]) - 1) */
      wi_pack ((unsigned HOST_WIDE_INT *) val, r, half_blocks_needed);
      return canonize (val, blocks_needed, prec);
    }
}

/* Compute the population count of X.  */
int
wi::popcount (const wide_int_ref &x)
{
  unsigned int i;
  int count;

  /* The high order block is special if it is the last block and the
     precision is not an even multiple of HOST_BITS_PER_WIDE_INT.  We
     have to clear out any ones above the precision before doing
     popcount on this block.  */
  count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
  unsigned int stop = x.len;
  if (count < 0)
    {
      count = popcount_hwi (x.uhigh () << -count);
      stop -= 1;
    }
  else
    {
      if (x.sign_mask () >= 0)
        count = 0;
    }

  for (i = 0; i < stop; ++i)
    count += popcount_hwi (x.val[i]);

  return count;
}

/* Set VAL to OP0 - OP1.  If OVERFLOW is nonnull, record in *OVERFLOW
   whether the result overflows when OP0 and OP1 are treated as having
   signedness SGN.  Return the number of blocks in VAL.  */
unsigned int
wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
               unsigned int op0len, const HOST_WIDE_INT *op1,
               unsigned int op1len, unsigned int prec,
               signop sgn, bool *overflow)
{
  unsigned HOST_WIDE_INT o0 = 0;
  unsigned HOST_WIDE_INT o1 = 0;
  unsigned HOST_WIDE_INT x = 0;
  /* We implement subtraction as an in place negate and add.  Negation
     is just inversion and add 1, so we can do the add of 1 by just
     starting the borrow in of the first element at 1.  */
  unsigned HOST_WIDE_INT borrow = 0;
  unsigned HOST_WIDE_INT old_borrow = 0;

  unsigned HOST_WIDE_INT mask0, mask1;
  unsigned int i;

  unsigned int len = MAX (op0len, op1len);
  mask0 = -top_bit_of (op0, op0len, prec);
  mask1 = -top_bit_of (op1, op1len, prec);

  /* Subtract all of the explicitly defined elements.  */
  for (i = 0; i < len; i++)
    {
      o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0;
      o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1;
      x = o0 - o1 - borrow;
      val[i] = x;
      old_borrow = borrow;
      borrow = borrow == 0 ? o0 < o1 : o0 <= o1;
    }

  if (len * HOST_BITS_PER_WIDE_INT < prec)
    {
      val[len] = mask0 - mask1 - borrow;
      len++;
      if (overflow)
        *overflow = false;
    }
  else if (overflow)
    {
      unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
      if (sgn == SIGNED)
        {
          unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0);
          *overflow = (HOST_WIDE_INT) (x << shift) < 0;
        }
      else
        {
          /* Put the MSB of X and O0 and in the top of the HWI.  */
          x <<= shift;
          o0 <<= shift;
          if (old_borrow)
            *overflow = (x >= o0);
          else
            *overflow = (x > o0);
        }
    }

  return canonize (val, len, prec);
}


/*
 * Division and Mod
 */

/* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR.  The
   algorithm is a small modification of the algorithm in Hacker's
   Delight by Warren, which itself is a small modification of Knuth's
   algorithm.  M is the number of significant elements of U however
   there needs to be at least one extra element of B_DIVIDEND
   allocated, N is the number of elements of B_DIVISOR.  */
static void
divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient,
                   unsigned HOST_HALF_WIDE_INT *b_remainder,
                   unsigned HOST_HALF_WIDE_INT *b_dividend,
                   unsigned HOST_HALF_WIDE_INT *b_divisor,
                   int m, int n)
{
  /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
     HOST_WIDE_INT and stored in the lower bits of each word.  This
     algorithm should work properly on both 32 and 64 bit
     machines.  */
  unsigned HOST_WIDE_INT b
    = (unsigned HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT;
  unsigned HOST_WIDE_INT qhat;   /* Estimate of quotient digit.  */
  unsigned HOST_WIDE_INT rhat;   /* A remainder.  */
  unsigned HOST_WIDE_INT p;      /* Product of two digits.  */
  HOST_WIDE_INT t, k;
  int i, j, s;

  /* Single digit divisor.  */
  if (n == 1)
    {
      k = 0;
      for (j = m - 1; j >= 0; j--)
        {
          b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0];
          k = ((k * b + b_dividend[j])
               - ((unsigned HOST_WIDE_INT)b_quotient[j]
                  * (unsigned HOST_WIDE_INT)b_divisor[0]));
        }
      b_remainder[0] = k;
      return;
    }

  s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */

  if (s)
    {
      /* Normalize B_DIVIDEND and B_DIVISOR.  Unlike the published
         algorithm, we can overwrite b_dividend and b_divisor, so we do
         that.  */
      for (i = n - 1; i > 0; i--)
        b_divisor[i] = (b_divisor[i] << s)
          | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
      b_divisor[0] = b_divisor[0] << s;

      b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s);
      for (i = m - 1; i > 0; i--)
        b_dividend[i] = (b_dividend[i] << s)
          | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
      b_dividend[0] = b_dividend[0] << s;
    }

  /* Main loop.  */
  for (j = m - n; j >= 0; j--)
    {
      qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1];
      rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1];
    again:
      if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2])
        {
          qhat -= 1;
          rhat += b_divisor[n-1];
          if (rhat < b)
            goto again;
        }

      /* Multiply and subtract.  */
      k = 0;
      for (i = 0; i < n; i++)
        {
          p = qhat * b_divisor[i];
          t = b_dividend[i+j] - k - (p & HALF_INT_MASK);
          b_dividend[i + j] = t;
          k = ((p >> HOST_BITS_PER_HALF_WIDE_INT)
               - (t >> HOST_BITS_PER_HALF_WIDE_INT));
        }
      t = b_dividend[j+n] - k;
      b_dividend[j+n] = t;

      b_quotient[j] = qhat;
      if (t < 0)
        {
          b_quotient[j] -= 1;
          k = 0;
          for (i = 0; i < n; i++)
            {
              t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k;
              b_dividend[i+j] = t;
              k = t >> HOST_BITS_PER_HALF_WIDE_INT;
            }
          b_dividend[j+n] += k;
        }
    }
  if (s)
    for (i = 0; i < n; i++)
      b_remainder[i] = (b_dividend[i] >> s)
        | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
  else
    for (i = 0; i < n; i++)
      b_remainder[i] = b_dividend[i];
}


/* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate
   the result.  If QUOTIENT is nonnull, store the value of the quotient
   there and return the number of blocks in it.  The return value is
   not defined otherwise.  If REMAINDER is nonnull, store the value
   of the remainder there and store the number of blocks in
   *REMAINDER_LEN.  If OFLOW is not null, store in *OFLOW whether
   the division overflowed.  */
unsigned int
wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
                     HOST_WIDE_INT *remainder,
                     const HOST_WIDE_INT *dividend_val,
                     unsigned int dividend_len, unsigned int dividend_prec,
                     const HOST_WIDE_INT *divisor_val, unsigned int divisor_len,
                     unsigned int divisor_prec, signop sgn,
                     bool *oflow)
{
  unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec);
  unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec);
  unsigned HOST_HALF_WIDE_INT
    b_quotient[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  unsigned HOST_HALF_WIDE_INT
    b_remainder[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  unsigned HOST_HALF_WIDE_INT
    b_dividend[(4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT) + 1];
  unsigned HOST_HALF_WIDE_INT
    b_divisor[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
  unsigned int m, n;
  bool dividend_neg = false;
  bool divisor_neg = false;
  bool overflow = false;
  wide_int neg_dividend, neg_divisor;

  wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len,
                                           dividend_prec);
  wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len,
                                          divisor_prec);
  if (divisor == 0)
    overflow = true;

  /* The smallest signed number / -1 causes overflow.  The dividend_len
     check is for speed rather than correctness.  */
  if (sgn == SIGNED
      && dividend_len == BLOCKS_NEEDED (dividend_prec)
      && divisor == -1
      && wi::only_sign_bit_p (dividend))
    overflow = true;

  /* Handle the overflow cases.  Viewed as unsigned value, the quotient of
     (signed min / -1) has the same representation as the orignal dividend.
     We have traditionally made division by zero act as division by one,
     so there too we use the original dividend.  */
  if (overflow)
    {
      if (remainder)
        {
          *remainder_len = 1;
          remainder[0] = 0;
        }
      if (oflow != 0)
        *oflow = true;
      if (quotient)
        for (unsigned int i = 0; i < dividend_len; ++i)
          quotient[i] = dividend_val[i];
      return dividend_len;
    }

  if (oflow)
    *oflow = false;

  /* Do it on the host if you can.  */
  if (sgn == SIGNED
      && wi::fits_shwi_p (dividend)
      && wi::fits_shwi_p (divisor))
    {
      HOST_WIDE_INT o0 = dividend.to_shwi ();
      HOST_WIDE_INT o1 = divisor.to_shwi ();

      if (o0 == HOST_WIDE_INT_MIN && o1 == -1)
        {
          gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT);
          if (quotient)
            {
              quotient[0] = HOST_WIDE_INT_MIN;
              quotient[1] = 0;
            }
          if (remainder)
            {
              remainder[0] = 0;
              *remainder_len = 1;
            }
          return 2;
        }
      else
        {
          if (quotient)
            quotient[0] = o0 / o1;
          if (remainder)
            {
              remainder[0] = o0 % o1;
              *remainder_len = 1;
            }
          return 1;
        }
    }

  if (sgn == UNSIGNED
      && wi::fits_uhwi_p (dividend)
      && wi::fits_uhwi_p (divisor))
    {
      unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
      unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();

      if (quotient)
        quotient[0] = o0 / o1;
      if (remainder)
        {
          remainder[0] = o0 % o1;
          *remainder_len = 1;
        }
      return 1;
    }

  /* Make the divisor and dividend positive and remember what we
     did.  */
  if (sgn == SIGNED)
    {
      if (wi::neg_p (dividend))
        {
          neg_dividend = -dividend;
          dividend = neg_dividend;
          dividend_neg = true;
        }
      if (wi::neg_p (divisor))
        {
          neg_divisor = -divisor;
          divisor = neg_divisor;
          divisor_neg = true;
        }
    }

  wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
             dividend_blocks_needed, dividend_prec, sgn);
  wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
             divisor_blocks_needed, divisor_prec, sgn);

  m = dividend_blocks_needed;
  while (m > 1 && b_dividend[m - 1] == 0)
    m--;

  n = divisor_blocks_needed;
  while (n > 1 && b_divisor[n - 1] == 0)
    n--;

  memset (b_quotient, 0, sizeof (b_quotient));

  divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n);

  unsigned int quotient_len = 0;
  if (quotient)
    {
      wi_pack ((unsigned HOST_WIDE_INT *) quotient, b_quotient, m);
      quotient_len = canonize (quotient, (m + 1) / 2, dividend_prec);
      /* The quotient is neg if exactly one of the divisor or dividend is
         neg.  */
      if (dividend_neg != divisor_neg)
        quotient_len = wi::sub_large (quotient, zeros, 1, quotient,
                                      quotient_len, dividend_prec,
                                      UNSIGNED, 0);
    }

  if (remainder)
    {
      wi_pack ((unsigned HOST_WIDE_INT *) remainder, b_remainder, n);
      *remainder_len = canonize (remainder, (n + 1) / 2, dividend_prec);
      /* The remainder is always the same sign as the dividend.  */
      if (dividend_neg)
        *remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
                                        *remainder_len, dividend_prec,
                                        UNSIGNED, 0);
    }

  return quotient_len;
}

/*
 * Shifting, rotating and extraction.
 */

/* Left shift XVAL by SHIFT and store the result in VAL.  Return the
   number of blocks in VAL.  Both XVAL and VAL have PRECISION bits.  */
unsigned int
wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                  unsigned int xlen, unsigned int precision,
                  unsigned int shift)
{
  /* Split the shift into a whole-block shift and a subblock shift.  */
  unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
  unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;

  /* The whole-block shift fills with zeros.  */
  unsigned int len = BLOCKS_NEEDED (precision);
  for (unsigned int i = 0; i < skip; ++i)
    val[i] = 0;

  /* It's easier to handle the simple block case specially.  */
  if (small_shift == 0)
    for (unsigned int i = skip; i < len; ++i)
      val[i] = safe_uhwi (xval, xlen, i - skip);
  else
    {
      /* The first unfilled output block is a left shift of the first
         block in XVAL.  The other output blocks contain bits from two
         consecutive input blocks.  */
      unsigned HOST_WIDE_INT carry = 0;
      for (unsigned int i = skip; i < len; ++i)
        {
          unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip);
          val[i] = (x << small_shift) | carry;
          carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT);
        }
    }
  return canonize (val, len, precision);
}

/* Right shift XVAL by SHIFT and store the result in VAL.  Return the
   number of blocks in VAL.  The input has XPRECISION bits and the
   output has XPRECISION - SHIFT bits.  */
static unsigned int
rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                     unsigned int xlen, unsigned int xprecision,
                     unsigned int shift)
{
  /* Split the shift into a whole-block shift and a subblock shift.  */
  unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
  unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;

  /* Work out how many blocks are needed to store the significant bits
     (excluding the upper zeros or signs).  */
  unsigned int len = BLOCKS_NEEDED (xprecision - shift);

  /* It's easier to handle the simple block case specially.  */
  if (small_shift == 0)
    for (unsigned int i = 0; i < len; ++i)
      val[i] = safe_uhwi (xval, xlen, i + skip);
  else
    {
      /* Each output block but the last is a combination of two input blocks.
         The last block is a right shift of the last block in XVAL.  */
      unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip);
      for (unsigned int i = 0; i < len; ++i)
        {
          val[i] = curr >> small_shift;
          curr = safe_uhwi (xval, xlen, i + skip + 1);
          val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT);
        }
    }
  return len;
}

/* Logically right shift XVAL by SHIFT and store the result in VAL.
   Return the number of blocks in VAL.  XVAL has XPRECISION bits and
   VAL has PRECISION bits.  */
unsigned int
wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                   unsigned int xlen, unsigned int xprecision,
                   unsigned int precision, unsigned int shift)
{
  unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift);

  /* The value we just created has precision XPRECISION - SHIFT.
     Zero-extend it to wider precisions.  */
  if (precision > xprecision - shift)
    {
      unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
      if (small_prec)
        val[len - 1] = zext_hwi (val[len - 1], small_prec);
      else if (val[len - 1] < 0)
        {
          /* Add a new block with a zero. */
          val[len++] = 0;
          return len;
        }
    }
  return canonize (val, len, precision);
}

/* Arithmetically right shift XVAL by SHIFT and store the result in VAL.
   Return the number of blocks in VAL.  XVAL has XPRECISION bits and
   VAL has PRECISION bits.  */
unsigned int
wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
                   unsigned int xlen, unsigned int xprecision,
                   unsigned int precision, unsigned int shift)
{
  unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift);

  /* The value we just created has precision XPRECISION - SHIFT.
     Sign-extend it to wider types.  */
  if (precision > xprecision - shift)
    {
      unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
      if (small_prec)
        val[len - 1] = sext_hwi (val[len - 1], small_prec);
    }
  return canonize (val, len, precision);
}

/* Return the number of leading (upper) zeros in X.  */
int
wi::clz (const wide_int_ref &x)
{
  /* Calculate how many bits there above the highest represented block.  */
  int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;

  unsigned HOST_WIDE_INT high = x.uhigh ();
  if (count < 0)
    /* The upper -COUNT bits of HIGH are not part of the value.
       Clear them out.  */
    high = (high << -count) >> -count;
  else if (x.sign_mask () < 0)
    /* The upper bit is set, so there are no leading zeros.  */
    return 0;

  /* We don't need to look below HIGH.  Either HIGH is nonzero,
     or the top bit of the block below is nonzero; clz_hwi is
     HOST_BITS_PER_WIDE_INT in the latter case.  */
  return count + clz_hwi (high);
}

/* Return the number of redundant sign bits in X.  (That is, the number
   of bits immediately below the sign bit that have the same value as
   the sign bit.)  */
int
wi::clrsb (const wide_int_ref &x)
{
  /* Calculate how many bits there above the highest represented block.  */
  int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;

  unsigned HOST_WIDE_INT high = x.uhigh ();
  unsigned HOST_WIDE_INT mask = -1;
  if (count < 0)
    {
      /* The upper -COUNT bits of HIGH are not part of the value.
         Clear them from both MASK and HIGH.  */
      mask >>= -count;
      high &= mask;
    }

  /* If the top bit is 1, count the number of leading 1s.  If the top
     bit is zero, count the number of leading zeros.  */
  if (high > mask / 2)
    high ^= mask;

  /* There are no sign bits below the top block, so we don't need to look
     beyond HIGH.  Note that clz_hwi is HOST_BITS_PER_WIDE_INT when
     HIGH is 0.  */
  return count + clz_hwi (high) - 1;
}

/* Return the number of trailing (lower) zeros in X.  */
int
wi::ctz (const wide_int_ref &x)
{
  if (x.len == 1 && x.ulow () == 0)
    return x.precision;

  /* Having dealt with the zero case, there must be a block with a
     nonzero bit.  We don't care about the bits above the first 1.  */
  unsigned int i = 0;
  while (x.val[i] == 0)
    ++i;
  return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]);
}

/* If X is an exact power of 2, return the base-2 logarithm, otherwise
   return -1.  */
int
wi::exact_log2 (const wide_int_ref &x)
{
  /* Reject cases where there are implicit -1 blocks above HIGH.  */
  if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0)
    return -1;

  /* Set CRUX to the index of the entry that should be nonzero.
     If the top block is zero then the next lowest block (if any)
     must have the high bit set.  */
  unsigned int crux = x.len - 1;
  if (crux > 0 && x.val[crux] == 0)
    crux -= 1;

  /* Check that all lower blocks are zero.  */
  for (unsigned int i = 0; i < crux; ++i)
    if (x.val[i] != 0)
      return -1;

  /* Get a zero-extended form of block CRUX.  */
  unsigned HOST_WIDE_INT hwi = x.val[crux];
  if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision)
    hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT);

  /* Now it's down to whether HWI is a power of 2.  */
  int res = ::exact_log2 (hwi);
  if (res >= 0)
    res += crux * HOST_BITS_PER_WIDE_INT;
  return res;
}

/* Return the base-2 logarithm of X, rounding down.  Return -1 if X is 0.  */
int
wi::floor_log2 (const wide_int_ref &x)
{
  return x.precision - 1 - clz (x);
}

/* Return the index of the first (lowest) set bit in X, counting from 1.
   Return 0 if X is 0.  */
int
wi::ffs (const wide_int_ref &x)
{
  return eq_p (x, 0) ? 0 : ctz (x) + 1;
}

/* Return true if sign-extending X to have precision PRECISION would give
   the minimum signed value at that precision.  */
bool
wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision)
{
  return ctz (x) + 1 == int (precision);
}

/* Return true if X represents the minimum signed value.  */
bool
wi::only_sign_bit_p (const wide_int_ref &x)
{
  return only_sign_bit_p (x, x.precision);
}

/*
 * Private utilities.
 */

void gt_ggc_mx (widest_int *) { }
void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { }
void gt_pch_nx (widest_int *) { }

template void wide_int::dump () const;
template void generic_wide_int <wide_int_ref_storage <false> >::dump () const;
template void generic_wide_int <wide_int_ref_storage <true> >::dump () const;
template void offset_int::dump () const;
template void widest_int::dump () const;