1 /* Operations on HOST_WIDE_INT.
2 Copyright (C) 1987-2013 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along 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
35 int
floor_log2(unsigned HOST_WIDE_INT x)36 floor_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
65 int
ceil_log2(unsigned HOST_WIDE_INT x)66 ceil_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
74 int
exact_log2(unsigned HOST_WIDE_INT x)75 exact_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
85 int
ctz_hwi(unsigned HOST_WIDE_INT x)86 ctz_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
93 int
clz_hwi(unsigned HOST_WIDE_INT x)94 clz_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
102 int
ffs_hwi(unsigned HOST_WIDE_INT x)103 ffs_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
110 int
popcount_hwi(unsigned HOST_WIDE_INT x)111 popcount_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 /* Compute the absolute value of X. */
128
129 HOST_WIDE_INT
abs_hwi(HOST_WIDE_INT x)130 abs_hwi (HOST_WIDE_INT x)
131 {
132 gcc_checking_assert (x != HOST_WIDE_INT_MIN);
133 return x >= 0 ? x : -x;
134 }
135
136 /* Compute the absolute value of X as an unsigned type. */
137
138 unsigned HOST_WIDE_INT
absu_hwi(HOST_WIDE_INT x)139 absu_hwi (HOST_WIDE_INT x)
140 {
141 return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
142 }
143
144 /* Compute the greatest common divisor of two numbers A and B using
145 Euclid's algorithm. */
146
147 HOST_WIDE_INT
gcd(HOST_WIDE_INT a,HOST_WIDE_INT b)148 gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
149 {
150 HOST_WIDE_INT x, y, z;
151
152 x = abs_hwi (a);
153 y = abs_hwi (b);
154
155 while (x > 0)
156 {
157 z = y % x;
158 y = x;
159 x = z;
160 }
161
162 return y;
163 }
164
165 /* For X and Y positive integers, return X multiplied by Y and check
166 that the result does not overflow. */
167
168 HOST_WIDE_INT
pos_mul_hwi(HOST_WIDE_INT x,HOST_WIDE_INT y)169 pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
170 {
171 if (x != 0)
172 gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
173
174 return x * y;
175 }
176
177 /* Return X multiplied by Y and check that the result does not
178 overflow. */
179
180 HOST_WIDE_INT
mul_hwi(HOST_WIDE_INT x,HOST_WIDE_INT y)181 mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
182 {
183 gcc_checking_assert (x != HOST_WIDE_INT_MIN
184 && y != HOST_WIDE_INT_MIN);
185
186 if (x >= 0)
187 {
188 if (y >= 0)
189 return pos_mul_hwi (x, y);
190
191 return -pos_mul_hwi (x, -y);
192 }
193
194 if (y >= 0)
195 return -pos_mul_hwi (-x, y);
196
197 return pos_mul_hwi (-x, -y);
198 }
199
200 /* Compute the least common multiple of two numbers A and B . */
201
202 HOST_WIDE_INT
least_common_multiple(HOST_WIDE_INT a,HOST_WIDE_INT b)203 least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
204 {
205 return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
206 }
207