/* Operations on HOST_WIDE_INT.
   Copyright (C) 1987-2018 Free Software Foundation, Inc.

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"

#if GCC_VERSION < 3004

/* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
   and exact_log2 are defined as inline functions in hwint.h
   if GCC_VERSION >= 3004.
   The definitions here are used for older versions of GCC and
   non-GCC bootstrap compilers.  */

/* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
   If X is 0, return -1.  */

int
floor_log2 (unsigned HOST_WIDE_INT x)
{
  int t = 0;

  if (x == 0)
    return -1;

  if (HOST_BITS_PER_WIDE_INT > 64)
    if (x >= HOST_WIDE_INT_1U << (t + 64))
      t += 64;
  if (HOST_BITS_PER_WIDE_INT > 32)
    if (x >= HOST_WIDE_INT_1U << (t + 32))
      t += 32;
  if (x >= HOST_WIDE_INT_1U << (t + 16))
    t += 16;
  if (x >= HOST_WIDE_INT_1U << (t + 8))
    t += 8;
  if (x >= HOST_WIDE_INT_1U << (t + 4))
    t += 4;
  if (x >= HOST_WIDE_INT_1U << (t + 2))
    t += 2;
  if (x >= HOST_WIDE_INT_1U << (t + 1))
    t += 1;

  return t;
}

/* Given X, an unsigned number, return the least Y such that 2**Y >= X.  */

int
ceil_log2 (unsigned HOST_WIDE_INT x)
{
  return x == 0 ? 0 : floor_log2 (x - 1) + 1;
}

/* Return the logarithm of X, base 2, considering X unsigned,
   if X is a power of 2.  Otherwise, returns -1.  */

int
exact_log2 (unsigned HOST_WIDE_INT x)
{
  if (!pow2p_hwi (x))
    return -1;
  return floor_log2 (x);
}

/* Given X, an unsigned number, return the number of least significant bits
   that are zero.  When X == 0, the result is the word size.  */

int
ctz_hwi (unsigned HOST_WIDE_INT x)
{
  return x ? floor_log2 (least_bit_hwi (x)) : HOST_BITS_PER_WIDE_INT;
}

/* Similarly for most significant bits.  */

int
clz_hwi (unsigned HOST_WIDE_INT x)
{
  return HOST_BITS_PER_WIDE_INT - 1 - floor_log2 (x);
}

/* Similar to ctz_hwi, except that the least significant bit is numbered
   starting from 1, and X == 0 yields 0.  */

int
ffs_hwi (unsigned HOST_WIDE_INT x)
{
  return 1 + floor_log2 (least_bit_hwi (x));
}

/* Return the number of set bits in X.  */

int
popcount_hwi (unsigned HOST_WIDE_INT x)
{
  int i, ret = 0;
  size_t bits = sizeof (x) * CHAR_BIT;

  for (i = 0; i < bits; i += 1)
    {
      ret += x & 1;
      x >>= 1;
    }

  return ret;
}

#endif /* GCC_VERSION < 3004 */


/* Compute the greatest common divisor of two numbers A and B using
   Euclid's algorithm.  */

HOST_WIDE_INT
gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
{
  HOST_WIDE_INT x, y, z;

  x = abs_hwi (a);
  y = abs_hwi (b);

  while (x > 0)
    {
      z = y % x;
      y = x;
      x = z;
    }

  return y;
}

/* For X and Y positive integers, return X multiplied by Y and check
   that the result does not overflow.  */

HOST_WIDE_INT
pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
{
  if (x != 0)
    gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);

  return x * y;
}

/* Return X multiplied by Y and check that the result does not
   overflow.  */

HOST_WIDE_INT
mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
{
  gcc_checking_assert (x != HOST_WIDE_INT_MIN
		       && y != HOST_WIDE_INT_MIN);

  if (x >= 0)
    {
      if (y >= 0)
	return pos_mul_hwi (x, y);

      return -pos_mul_hwi (x, -y);
    }

  if (y >= 0)
    return -pos_mul_hwi (-x, y);

  return pos_mul_hwi (-x, -y);
}

/* Compute the least common multiple of two numbers A and B .  */

HOST_WIDE_INT
least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
{
  return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
}