/* Operations on HOST_WIDE_INT.
|
/* Operations on HOST_WIDE_INT.
|
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
|
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
|
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "diagnostic-core.h"
|
#include "diagnostic-core.h"
|
|
|
#if GCC_VERSION < 3004
|
#if GCC_VERSION < 3004
|
|
|
/* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2 and exact_log2
|
/* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2 and exact_log2
|
are defined as inline functions in hwint.h if GCC_VERSION >= 3004.
|
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
|
The definitions here are used for older versions of GCC and non-GCC
|
bootstrap compilers. */
|
bootstrap compilers. */
|
|
|
/* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
|
/* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
|
If X is 0, return -1. */
|
If X is 0, return -1. */
|
|
|
int
|
int
|
floor_log2 (unsigned HOST_WIDE_INT x)
|
floor_log2 (unsigned HOST_WIDE_INT x)
|
{
|
{
|
int t = 0;
|
int t = 0;
|
|
|
if (x == 0)
|
if (x == 0)
|
return -1;
|
return -1;
|
|
|
if (HOST_BITS_PER_WIDE_INT > 64)
|
if (HOST_BITS_PER_WIDE_INT > 64)
|
if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
|
if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
|
t += 64;
|
t += 64;
|
if (HOST_BITS_PER_WIDE_INT > 32)
|
if (HOST_BITS_PER_WIDE_INT > 32)
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
|
t += 32;
|
t += 32;
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
|
t += 16;
|
t += 16;
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
|
t += 8;
|
t += 8;
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
|
t += 4;
|
t += 4;
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
|
t += 2;
|
t += 2;
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
|
if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
|
t += 1;
|
t += 1;
|
|
|
return t;
|
return t;
|
}
|
}
|
|
|
/* Return the logarithm of X, base 2, considering X unsigned,
|
/* Return the logarithm of X, base 2, considering X unsigned,
|
if X is a power of 2. Otherwise, returns -1. */
|
if X is a power of 2. Otherwise, returns -1. */
|
|
|
int
|
int
|
exact_log2 (unsigned HOST_WIDE_INT x)
|
exact_log2 (unsigned HOST_WIDE_INT x)
|
{
|
{
|
if (x != (x & -x))
|
if (x != (x & -x))
|
return -1;
|
return -1;
|
return floor_log2 (x);
|
return floor_log2 (x);
|
}
|
}
|
|
|
/* Given X, an unsigned number, return the number of least significant bits
|
/* Given X, an unsigned number, return the number of least significant bits
|
that are zero. When X == 0, the result is the word size. */
|
that are zero. When X == 0, the result is the word size. */
|
|
|
int
|
int
|
ctz_hwi (unsigned HOST_WIDE_INT x)
|
ctz_hwi (unsigned HOST_WIDE_INT x)
|
{
|
{
|
return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
|
return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
|
}
|
}
|
|
|
/* Similarly for most significant bits. */
|
/* Similarly for most significant bits. */
|
|
|
int
|
int
|
clz_hwi (unsigned HOST_WIDE_INT x)
|
clz_hwi (unsigned HOST_WIDE_INT x)
|
{
|
{
|
return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x);
|
return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x);
|
}
|
}
|
|
|
/* Similar to ctz_hwi, except that the least significant bit is numbered
|
/* Similar to ctz_hwi, except that the least significant bit is numbered
|
starting from 1, and X == 0 yields 0. */
|
starting from 1, and X == 0 yields 0. */
|
|
|
int
|
int
|
ffs_hwi (unsigned HOST_WIDE_INT x)
|
ffs_hwi (unsigned HOST_WIDE_INT x)
|
{
|
{
|
return 1 + floor_log2 (x & -x);
|
return 1 + floor_log2 (x & -x);
|
}
|
}
|
|
|
#endif /* GCC_VERSION < 3004 */
|
#endif /* GCC_VERSION < 3004 */
|
|
|
/* Compute the absolute value of X. */
|
/* Compute the absolute value of X. */
|
|
|
HOST_WIDE_INT
|
HOST_WIDE_INT
|
abs_hwi (HOST_WIDE_INT x)
|
abs_hwi (HOST_WIDE_INT x)
|
{
|
{
|
gcc_checking_assert (x != HOST_WIDE_INT_MIN);
|
gcc_checking_assert (x != HOST_WIDE_INT_MIN);
|
return x >= 0 ? x : -x;
|
return x >= 0 ? x : -x;
|
}
|
}
|
|
|
/* Compute the absolute value of X as an unsigned type. */
|
/* Compute the absolute value of X as an unsigned type. */
|
|
|
unsigned HOST_WIDE_INT
|
unsigned HOST_WIDE_INT
|
absu_hwi (HOST_WIDE_INT x)
|
absu_hwi (HOST_WIDE_INT x)
|
{
|
{
|
return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
|
return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
|
}
|
}
|
|
|
/* Compute the greatest common divisor of two numbers A and B using
|
/* Compute the greatest common divisor of two numbers A and B using
|
Euclid's algorithm. */
|
Euclid's algorithm. */
|
|
|
HOST_WIDE_INT
|
HOST_WIDE_INT
|
gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
|
gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
|
{
|
{
|
HOST_WIDE_INT x, y, z;
|
HOST_WIDE_INT x, y, z;
|
|
|
x = abs_hwi (a);
|
x = abs_hwi (a);
|
y = abs_hwi (b);
|
y = abs_hwi (b);
|
|
|
while (x > 0)
|
while (x > 0)
|
{
|
{
|
z = y % x;
|
z = y % x;
|
y = x;
|
y = x;
|
x = z;
|
x = z;
|
}
|
}
|
|
|
return y;
|
return y;
|
}
|
}
|
|
|
/* For X and Y positive integers, return X multiplied by Y and check
|
/* For X and Y positive integers, return X multiplied by Y and check
|
that the result does not overflow. */
|
that the result does not overflow. */
|
|
|
HOST_WIDE_INT
|
HOST_WIDE_INT
|
pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
|
pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
|
{
|
{
|
if (x != 0)
|
if (x != 0)
|
gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
|
gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
|
|
|
return x * y;
|
return x * y;
|
}
|
}
|
|
|
/* Return X multiplied by Y and check that the result does not
|
/* Return X multiplied by Y and check that the result does not
|
overflow. */
|
overflow. */
|
|
|
HOST_WIDE_INT
|
HOST_WIDE_INT
|
mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
|
mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
|
{
|
{
|
gcc_checking_assert (x != HOST_WIDE_INT_MIN
|
gcc_checking_assert (x != HOST_WIDE_INT_MIN
|
&& y != HOST_WIDE_INT_MIN);
|
&& y != HOST_WIDE_INT_MIN);
|
|
|
if (x >= 0)
|
if (x >= 0)
|
{
|
{
|
if (y >= 0)
|
if (y >= 0)
|
return pos_mul_hwi (x, y);
|
return pos_mul_hwi (x, y);
|
|
|
return -pos_mul_hwi (x, -y);
|
return -pos_mul_hwi (x, -y);
|
}
|
}
|
|
|
if (y >= 0)
|
if (y >= 0)
|
return -pos_mul_hwi (-x, y);
|
return -pos_mul_hwi (-x, y);
|
|
|
return pos_mul_hwi (-x, -y);
|
return pos_mul_hwi (-x, -y);
|
}
|
}
|
|
|
/* Compute the least common multiple of two numbers A and B . */
|
/* Compute the least common multiple of two numbers A and B . */
|
|
|
HOST_WIDE_INT
|
HOST_WIDE_INT
|
least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
|
least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
|
{
|
{
|
return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
|
return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
|
}
|
}
|
|
|
