]>
Commit | Line | Data |
---|---|---|
c59ffc41 | 1 | /* Operations on HOST_WIDE_INT. |
a945c346 | 2 | Copyright (C) 1987-2024 Free Software Foundation, Inc. |
c59ffc41 JM |
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" | |
abb226c9 | 22 | #include "coretypes.h" |
c59ffc41 JM |
23 | |
24 | #if GCC_VERSION < 3004 | |
25 | ||
46d33ae9 SB |
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. */ | |
c59ffc41 JM |
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 | |
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) | |
fecfbfa4 | 44 | if (x >= HOST_WIDE_INT_1U << (t + 64)) |
c59ffc41 JM |
45 | t += 64; |
46 | if (HOST_BITS_PER_WIDE_INT > 32) | |
fecfbfa4 | 47 | if (x >= HOST_WIDE_INT_1U << (t + 32)) |
c59ffc41 | 48 | t += 32; |
fecfbfa4 | 49 | if (x >= HOST_WIDE_INT_1U << (t + 16)) |
c59ffc41 | 50 | t += 16; |
fecfbfa4 | 51 | if (x >= HOST_WIDE_INT_1U << (t + 8)) |
c59ffc41 | 52 | t += 8; |
fecfbfa4 | 53 | if (x >= HOST_WIDE_INT_1U << (t + 4)) |
c59ffc41 | 54 | t += 4; |
fecfbfa4 | 55 | if (x >= HOST_WIDE_INT_1U << (t + 2)) |
c59ffc41 | 56 | t += 2; |
fecfbfa4 | 57 | if (x >= HOST_WIDE_INT_1U << (t + 1)) |
c59ffc41 JM |
58 | t += 1; |
59 | ||
60 | return t; | |
61 | } | |
62 | ||
e8dce850 | 63 | /* Given X, an unsigned number, return the least Y such that 2**Y >= X. */ |
46d33ae9 SB |
64 | |
65 | int | |
66 | ceil_log2 (unsigned HOST_WIDE_INT x) | |
67 | { | |
e8dce850 | 68 | return x == 0 ? 0 : floor_log2 (x - 1) + 1; |
46d33ae9 SB |
69 | } |
70 | ||
c59ffc41 JM |
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 | |
75 | exact_log2 (unsigned HOST_WIDE_INT x) | |
76 | { | |
146ec50f | 77 | if (!pow2p_hwi (x)) |
c59ffc41 JM |
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 | |
86 | ctz_hwi (unsigned HOST_WIDE_INT x) | |
87 | { | |
146ec50f | 88 | return x ? floor_log2 (least_bit_hwi (x)) : HOST_BITS_PER_WIDE_INT; |
c59ffc41 JM |
89 | } |
90 | ||
91 | /* Similarly for most significant bits. */ | |
92 | ||
93 | int | |
94 | clz_hwi (unsigned HOST_WIDE_INT x) | |
95 | { | |
c3284718 | 96 | return HOST_BITS_PER_WIDE_INT - 1 - floor_log2 (x); |
c59ffc41 JM |
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 | |
103 | ffs_hwi (unsigned HOST_WIDE_INT x) | |
104 | { | |
146ec50f | 105 | return 1 + floor_log2 (least_bit_hwi (x)); |
c59ffc41 JM |
106 | } |
107 | ||
440b6d59 TV |
108 | /* Return the number of set bits in X. */ |
109 | ||
110 | int | |
111 | popcount_hwi (unsigned HOST_WIDE_INT x) | |
112 | { | |
113 | int i, ret = 0; | |
7cb151c0 | 114 | size_t bits = sizeof (x) * CHAR_BIT; |
440b6d59 | 115 | |
7cb151c0 | 116 | for (i = 0; i < bits; i += 1) |
440b6d59 TV |
117 | { |
118 | ret += x & 1; | |
119 | x >>= 1; | |
120 | } | |
121 | ||
122 | return ret; | |
123 | } | |
124 | ||
c59ffc41 | 125 | #endif /* GCC_VERSION < 3004 */ |
3c67fd9c | 126 | |
4c9cf7af | 127 | |
3c67fd9c SP |
128 | /* Compute the greatest common divisor of two numbers A and B using |
129 | Euclid's algorithm. */ | |
130 | ||
131 | HOST_WIDE_INT | |
132 | gcd (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 | ||
152 | HOST_WIDE_INT | |
153 | pos_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 | ||
164 | HOST_WIDE_INT | |
165 | mul_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 | ||
186 | HOST_WIDE_INT | |
187 | least_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 | } |