Line data Source code
1 : /* Operations on HOST_WIDE_INT.
2 : Copyright (C) 1987-2026 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 "coretypes.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
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 >= HOST_WIDE_INT_1U << (t + 64))
45 : t += 64;
46 : if (HOST_BITS_PER_WIDE_INT > 32)
47 : if (x >= HOST_WIDE_INT_1U << (t + 32))
48 : t += 32;
49 : if (x >= HOST_WIDE_INT_1U << (t + 16))
50 : t += 16;
51 : if (x >= HOST_WIDE_INT_1U << (t + 8))
52 : t += 8;
53 : if (x >= HOST_WIDE_INT_1U << (t + 4))
54 : t += 4;
55 : if (x >= HOST_WIDE_INT_1U << (t + 2))
56 : t += 2;
57 : if (x >= HOST_WIDE_INT_1U << (t + 1))
58 : t += 1;
59 :
60 : return t;
61 : }
62 :
63 : /* Given X, an unsigned number, return the least Y such that 2**Y >= X. */
64 :
65 : int
66 : ceil_log2 (unsigned HOST_WIDE_INT x)
67 : {
68 : return x == 0 ? 0 : 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
75 : exact_log2 (unsigned HOST_WIDE_INT x)
76 : {
77 : if (!pow2p_hwi (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
86 : ctz_hwi (unsigned HOST_WIDE_INT x)
87 : {
88 : return x ? floor_log2 (least_bit_hwi (x)) : HOST_BITS_PER_WIDE_INT;
89 : }
90 :
91 : /* Similarly for most significant bits. */
92 :
93 : int
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
103 : ffs_hwi (unsigned HOST_WIDE_INT x)
104 : {
105 : return 1 + floor_log2 (least_bit_hwi (x));
106 : }
107 :
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;
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 :
131 : HOST_WIDE_INT
132 7808973 : gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
133 : {
134 7808973 : HOST_WIDE_INT x, y, z;
135 :
136 7808973 : x = abs_hwi (a);
137 7808973 : y = abs_hwi (b);
138 :
139 26381462 : while (x > 0)
140 : {
141 10763516 : z = y % x;
142 10763516 : y = x;
143 10763516 : x = z;
144 : }
145 :
146 7808973 : 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 7715892 : pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
154 : {
155 7715892 : if (x != 0)
156 7715892 : gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
157 :
158 7715892 : 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 7715892 : mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
166 : {
167 7715892 : gcc_checking_assert (x != HOST_WIDE_INT_MIN
168 : && y != HOST_WIDE_INT_MIN);
169 :
170 7715892 : if (x >= 0)
171 : {
172 7715892 : if (y >= 0)
173 7715892 : return pos_mul_hwi (x, y);
174 :
175 0 : return -pos_mul_hwi (x, -y);
176 : }
177 :
178 0 : if (y >= 0)
179 0 : return -pos_mul_hwi (-x, y);
180 :
181 0 : 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 7715892 : least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
188 : {
189 7715892 : return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
190 : }
191 :
192 : /* Reflect (reverse) the bits of a given VALUE within a specified BITWIDTH <= 64. */
193 :
194 : unsigned HOST_WIDE_INT
195 34834 : reflect_hwi (unsigned HOST_WIDE_INT value, unsigned bitwidth)
196 : {
197 34834 : if (bitwidth == 0)
198 : return 0;
199 :
200 34834 : gcc_checking_assert (bitwidth <= 64);
201 :
202 : #if STAGE0_CXX_HAS_BUILTIN (bitreverse64)
203 : return __builtin_bitreverse64 (value) >> (64 - bitwidth);
204 : #else
205 : unsigned HOST_WIDE_INT reflected_value = 0;
206 :
207 : /* Loop through each bit in the specified BITWIDTH. */
208 1073762 : for (size_t i = 0; i < bitwidth; i++)
209 : {
210 1038928 : reflected_value <<= 1;
211 : /* Add the least significant bit of the current value to the
212 : reflected value. */
213 1038928 : reflected_value |= (value & 1);
214 1038928 : value >>= 1;
215 : }
216 :
217 : return reflected_value;
218 : #endif
219 : }
220 :
221 : /* Calculate CRC for the initial CRC, DATA and given POLYNOMIAL.
222 : CRC_BITS is CRC size and DATA_BITS is the data size. */
223 :
224 : unsigned HOST_WIDE_INT
225 36883 : calculate_crc (unsigned HOST_WIDE_INT crc,
226 : unsigned HOST_WIDE_INT data,
227 : unsigned HOST_WIDE_INT polynomial,
228 : unsigned short crc_bits,
229 : unsigned short data_bits)
230 : {
231 36883 : if (data_bits == 0)
232 : return crc;
233 :
234 36883 : gcc_checking_assert (crc_bits <= 64);
235 36883 : gcc_checking_assert (data_bits <= 64);
236 36883 : gcc_checking_assert (crc_bits >= data_bits);
237 :
238 36883 : unsigned HOST_WIDE_INT msb = HOST_WIDE_INT_1U << (crc_bits - 1);
239 36883 : crc ^= (data << (crc_bits - data_bits));
240 332163 : for (short i = data_bits; i > 0; --i)
241 : {
242 295280 : if (crc & msb)
243 147617 : crc = (crc << 1) ^ polynomial;
244 : else
245 147663 : crc <<= 1;
246 : }
247 : /* Zero out bits in crc beyond the specified number of crc_bits. */
248 36883 : if (crc_bits < HOST_BITS_PER_WIDE_INT)
249 33807 : crc &= (HOST_WIDE_INT_1U << crc_bits) - 1;
250 : return crc;
251 : }
252 :
253 : /* Calculate CRC for the initial CRC, DATA and given POLYNOMIAL.
254 : CRC_BITS is CRC size and DATA_BITS is the DATA size. */
255 :
256 : unsigned HOST_WIDE_INT
257 34834 : calculate_reversed_crc (unsigned HOST_WIDE_INT crc,
258 : unsigned HOST_WIDE_INT data,
259 : unsigned HOST_WIDE_INT polynomial,
260 : unsigned short crc_bits,
261 : unsigned short data_bits)
262 : {
263 34834 : if (data_bits == 0)
264 : return crc;
265 :
266 34834 : gcc_checking_assert (crc_bits <= 64);
267 34834 : gcc_checking_assert (data_bits <= 64);
268 34834 : gcc_checking_assert (crc_bits >= data_bits);
269 :
270 34834 : unsigned HOST_WIDE_INT rev_polynom = reflect_hwi (polynomial, crc_bits);
271 34834 : crc ^= data;
272 313722 : for (int j = 0; j < data_bits; j++)
273 : {
274 278888 : if (crc & 1)
275 139389 : crc = (crc >> 1) ^ rev_polynom;
276 : else
277 139499 : crc >>= 1;
278 : }
279 : /* Zero out bits in crc beyond the specified number of crc_bits. */
280 34834 : if (crc_bits < HOST_BITS_PER_WIDE_INT)
281 29454 : crc &= (HOST_WIDE_INT_1U << crc_bits) - 1;
282 : return crc;
283 : }
|
