1/* Operations on HOST_WIDE_INT.
2   Copyright (C) 1987-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#include "config.h"
21#include "system.h"
22#include "diagnostic-core.h"
23
24#if GCC_VERSION < 3004
25
26/* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
27   and exact_log2 are defined as inline functions in hwint.h
28   if GCC_VERSION >= 3004.
29   The definitions here are used for older versions of GCC and
30   non-GCC bootstrap compilers.  */
31
32/* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
33   If X is 0, return -1.  */
34
35int
36floor_log2 (unsigned HOST_WIDE_INT x)
37{
38  int t = 0;
39
40  if (x == 0)
41    return -1;
42
43  if (HOST_BITS_PER_WIDE_INT > 64)
44    if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
45      t += 64;
46  if (HOST_BITS_PER_WIDE_INT > 32)
47    if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
48      t += 32;
49  if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
50    t += 16;
51  if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
52    t += 8;
53  if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
54    t += 4;
55  if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
56    t += 2;
57  if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
58    t += 1;
59
60  return t;
61}
62
63/* Given X, an unsigned number, return the largest Y such that 2**Y >= X.  */
64
65int
66ceil_log2 (unsigned HOST_WIDE_INT x)
67{
68  return floor_log2 (x - 1) + 1;
69}
70
71/* Return the logarithm of X, base 2, considering X unsigned,
72   if X is a power of 2.  Otherwise, returns -1.  */
73
74int
75exact_log2 (unsigned HOST_WIDE_INT x)
76{
77  if (x != (x & -x))
78    return -1;
79  return floor_log2 (x);
80}
81
82/* Given X, an unsigned number, return the number of least significant bits
83   that are zero.  When X == 0, the result is the word size.  */
84
85int
86ctz_hwi (unsigned HOST_WIDE_INT x)
87{
88  return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
89}
90
91/* Similarly for most significant bits.  */
92
93int
94clz_hwi (unsigned HOST_WIDE_INT x)
95{
96  return HOST_BITS_PER_WIDE_INT - 1 - floor_log2 (x);
97}
98
99/* Similar to ctz_hwi, except that the least significant bit is numbered
100   starting from 1, and X == 0 yields 0.  */
101
102int
103ffs_hwi (unsigned HOST_WIDE_INT x)
104{
105  return 1 + floor_log2 (x & -x);
106}
107
108/* Return the number of set bits in X.  */
109
110int
111popcount_hwi (unsigned HOST_WIDE_INT x)
112{
113  int i, ret = 0;
114  size_t bits = sizeof (x) * CHAR_BIT;
115
116  for (i = 0; i < bits; i += 1)
117    {
118      ret += x & 1;
119      x >>= 1;
120    }
121
122  return ret;
123}
124
125#endif /* GCC_VERSION < 3004 */
126
127
128/* Compute the greatest common divisor of two numbers A and B using
129   Euclid's algorithm.  */
130
131HOST_WIDE_INT
132gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
133{
134  HOST_WIDE_INT x, y, z;
135
136  x = abs_hwi (a);
137  y = abs_hwi (b);
138
139  while (x > 0)
140    {
141      z = y % x;
142      y = x;
143      x = z;
144    }
145
146  return y;
147}
148
149/* For X and Y positive integers, return X multiplied by Y and check
150   that the result does not overflow.  */
151
152HOST_WIDE_INT
153pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
154{
155  if (x != 0)
156    gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
157
158  return x * y;
159}
160
161/* Return X multiplied by Y and check that the result does not
162   overflow.  */
163
164HOST_WIDE_INT
165mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
166{
167  gcc_checking_assert (x != HOST_WIDE_INT_MIN
168		       && y != HOST_WIDE_INT_MIN);
169
170  if (x >= 0)
171    {
172      if (y >= 0)
173	return pos_mul_hwi (x, y);
174
175      return -pos_mul_hwi (x, -y);
176    }
177
178  if (y >= 0)
179    return -pos_mul_hwi (-x, y);
180
181  return pos_mul_hwi (-x, -y);
182}
183
184/* Compute the least common multiple of two numbers A and B .  */
185
186HOST_WIDE_INT
187least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
188{
189  return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
190}
191