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 : /* This file is compiled twice: once for the generator programs
21 : once for the compiler. */
22 : #ifdef GENERATOR_FILE
23 : #include "bconfig.h"
24 : #else
25 : #include "config.h"
26 : #endif
27 :
28 : #include "system.h"
29 : #include "coretypes.h"
30 :
31 : #if GCC_VERSION < 3004
32 :
33 : /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
34 : and exact_log2 are defined as inline functions in hwint.h
35 : if GCC_VERSION >= 3004.
36 : The definitions here are used for older versions of GCC and
37 : non-GCC bootstrap compilers. */
38 :
39 : /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
40 : If X is 0, return -1. */
41 :
42 : int
43 : floor_log2 (unsigned HOST_WIDE_INT x)
44 : {
45 : int t = 0;
46 :
47 : if (x == 0)
48 : return -1;
49 :
50 : if (HOST_BITS_PER_WIDE_INT > 64)
51 : if (x >= HOST_WIDE_INT_1U << (t + 64))
52 : t += 64;
53 : if (HOST_BITS_PER_WIDE_INT > 32)
54 : if (x >= HOST_WIDE_INT_1U << (t + 32))
55 : t += 32;
56 : if (x >= HOST_WIDE_INT_1U << (t + 16))
57 : t += 16;
58 : if (x >= HOST_WIDE_INT_1U << (t + 8))
59 : t += 8;
60 : if (x >= HOST_WIDE_INT_1U << (t + 4))
61 : t += 4;
62 : if (x >= HOST_WIDE_INT_1U << (t + 2))
63 : t += 2;
64 : if (x >= HOST_WIDE_INT_1U << (t + 1))
65 : t += 1;
66 :
67 : return t;
68 : }
69 :
70 : /* Given X, an unsigned number, return the least Y such that 2**Y >= X. */
71 :
72 : int
73 : ceil_log2 (unsigned HOST_WIDE_INT x)
74 : {
75 : return x == 0 ? 0 : floor_log2 (x - 1) + 1;
76 : }
77 :
78 : /* Return the logarithm of X, base 2, considering X unsigned,
79 : if X is a power of 2. Otherwise, returns -1. */
80 :
81 : int
82 : exact_log2 (unsigned HOST_WIDE_INT x)
83 : {
84 : if (!pow2p_hwi (x))
85 : return -1;
86 : return floor_log2 (x);
87 : }
88 :
89 : /* Given X, an unsigned number, return the number of least significant bits
90 : that are zero. When X == 0, the result is the word size. */
91 :
92 : int
93 : ctz_hwi (unsigned HOST_WIDE_INT x)
94 : {
95 : return x ? floor_log2 (least_bit_hwi (x)) : HOST_BITS_PER_WIDE_INT;
96 : }
97 :
98 : /* Similarly for most significant bits. */
99 :
100 : int
101 : clz_hwi (unsigned HOST_WIDE_INT x)
102 : {
103 : return HOST_BITS_PER_WIDE_INT - 1 - floor_log2 (x);
104 : }
105 :
106 : /* Similar to ctz_hwi, except that the least significant bit is numbered
107 : starting from 1, and X == 0 yields 0. */
108 :
109 : int
110 : ffs_hwi (unsigned HOST_WIDE_INT x)
111 : {
112 : return 1 + floor_log2 (least_bit_hwi (x));
113 : }
114 :
115 : /* Return the number of set bits in X. */
116 :
117 : int
118 : popcount_hwi (unsigned HOST_WIDE_INT x)
119 : {
120 : int i, ret = 0;
121 : size_t bits = sizeof (x) * CHAR_BIT;
122 :
123 : for (i = 0; i < bits; i += 1)
124 : {
125 : ret += x & 1;
126 : x >>= 1;
127 : }
128 :
129 : return ret;
130 : }
131 :
132 : #endif /* GCC_VERSION < 3004 */
133 :
134 :
135 : /* Compute the greatest common divisor of two numbers A and B using
136 : Euclid's algorithm. */
137 :
138 : HOST_WIDE_INT
139 8045872 : gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
140 : {
141 8045872 : HOST_WIDE_INT x, y, z;
142 :
143 8045872 : x = abs_hwi (a);
144 8045872 : y = abs_hwi (b);
145 :
146 27194955 : while (x > 0)
147 : {
148 11103211 : z = y % x;
149 11103211 : y = x;
150 11103211 : x = z;
151 : }
152 :
153 8045872 : return y;
154 : }
155 :
156 : /* For X and Y positive integers, return X multiplied by Y and check
157 : that the result does not overflow. */
158 :
159 : HOST_WIDE_INT
160 7951945 : pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
161 : {
162 7951945 : if (x != 0)
163 7951945 : gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
164 :
165 7951945 : return x * y;
166 : }
167 :
168 : /* Return X multiplied by Y and check that the result does not
169 : overflow. */
170 :
171 : HOST_WIDE_INT
172 7951945 : mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
173 : {
174 7951945 : gcc_checking_assert (x != HOST_WIDE_INT_MIN
175 : && y != HOST_WIDE_INT_MIN);
176 :
177 7951945 : if (x >= 0)
178 : {
179 7951945 : if (y >= 0)
180 7951945 : return pos_mul_hwi (x, y);
181 :
182 0 : return -pos_mul_hwi (x, -y);
183 : }
184 :
185 0 : if (y >= 0)
186 0 : return -pos_mul_hwi (-x, y);
187 :
188 0 : return pos_mul_hwi (-x, -y);
189 : }
190 :
191 : /* Compute the least common multiple of two numbers A and B . */
192 :
193 : HOST_WIDE_INT
194 7951945 : least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
195 : {
196 7951945 : return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
197 : }
198 :
199 : /* Reflect (reverse) the bits of a given VALUE within a specified BITWIDTH <= 64. */
200 :
201 : unsigned HOST_WIDE_INT
202 44636 : reflect_hwi (unsigned HOST_WIDE_INT value, unsigned bitwidth)
203 : {
204 44636 : if (bitwidth == 0)
205 : return 0;
206 :
207 44636 : gcc_checking_assert (bitwidth <= 64);
208 :
209 : #if STAGE0_CXX_HAS_BUILTIN (bitreverse64)
210 : return __builtin_bitreverse64 (value) >> (64 - bitwidth);
211 : #else
212 : unsigned HOST_WIDE_INT reflected_value = 0;
213 :
214 : /* Loop through each bit in the specified BITWIDTH. */
215 1632044 : for (size_t i = 0; i < bitwidth; i++)
216 : {
217 1587408 : reflected_value <<= 1;
218 : /* Add the least significant bit of the current value to the
219 : reflected value. */
220 1587408 : reflected_value |= (value & 1);
221 1587408 : value >>= 1;
222 : }
223 :
224 : return reflected_value;
225 : #endif
226 : }
227 :
228 : /* Calculate CRC for the initial CRC, DATA and given POLYNOMIAL.
229 : CRC_BITS is CRC size and DATA_BITS is the data size. */
230 :
231 : unsigned HOST_WIDE_INT
232 46099 : calculate_crc (unsigned HOST_WIDE_INT crc,
233 : unsigned HOST_WIDE_INT data,
234 : unsigned HOST_WIDE_INT polynomial,
235 : unsigned short crc_bits,
236 : unsigned short data_bits)
237 : {
238 46099 : if (data_bits == 0)
239 : return crc;
240 :
241 46099 : gcc_checking_assert (crc_bits <= 64);
242 46099 : gcc_checking_assert (data_bits <= 64);
243 46099 : gcc_checking_assert (crc_bits >= data_bits);
244 :
245 46099 : unsigned HOST_WIDE_INT msb = HOST_WIDE_INT_1U << (crc_bits - 1);
246 46099 : crc ^= (data << (crc_bits - data_bits));
247 415107 : for (short i = data_bits; i > 0; --i)
248 : {
249 369008 : if (crc & msb)
250 184481 : crc = (crc << 1) ^ polynomial;
251 : else
252 184527 : crc <<= 1;
253 : }
254 : /* Zero out bits in crc beyond the specified number of crc_bits. */
255 46099 : if (crc_bits < HOST_BITS_PER_WIDE_INT)
256 38927 : crc &= (HOST_WIDE_INT_1U << crc_bits) - 1;
257 : return crc;
258 : }
259 :
260 : /* Calculate CRC for the initial CRC, DATA and given POLYNOMIAL.
261 : CRC_BITS is CRC size and DATA_BITS is the DATA size. */
262 :
263 : unsigned HOST_WIDE_INT
264 44600 : calculate_reversed_crc (unsigned HOST_WIDE_INT crc,
265 : unsigned HOST_WIDE_INT data,
266 : unsigned HOST_WIDE_INT polynomial,
267 : unsigned short crc_bits,
268 : unsigned short data_bits)
269 : {
270 44600 : if (data_bits == 0)
271 : return crc;
272 :
273 44600 : gcc_checking_assert (crc_bits <= 64);
274 44600 : gcc_checking_assert (data_bits <= 64);
275 : /* allow data_bits > crc_bits for folding _mm_crc32_u64. */
276 :
277 44600 : unsigned HOST_WIDE_INT rev_polynom = reflect_hwi (polynomial, crc_bits);
278 44600 : crc ^= data;
279 403064 : for (int j = 0; j < data_bits; j++)
280 : {
281 358464 : if (crc & 1)
282 179073 : crc = (crc >> 1) ^ rev_polynom;
283 : else
284 179391 : crc >>= 1;
285 : }
286 : /* Zero out bits in crc beyond the specified number of crc_bits. */
287 44600 : if (crc_bits < HOST_BITS_PER_WIDE_INT)
288 31010 : crc &= (HOST_WIDE_INT_1U << crc_bits) - 1;
289 : return crc;
290 : }
|