Branch data Line data Source code
1 : : /* Operations on HOST_WIDE_INT.
2 : : Copyright (C) 1987-2024 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 : 17750119 : gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
133 : : {
134 : 17750119 : HOST_WIDE_INT x, y, z;
135 : :
136 : 17750119 : x = abs_hwi (a);
137 : 17750119 : y = abs_hwi (b);
138 : :
139 : 53547068 : while (x > 0)
140 : : {
141 : 18046830 : z = y % x;
142 : 18046830 : y = x;
143 : 18046830 : x = z;
144 : : }
145 : :
146 : 17750119 : 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 : 17704113 : pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
154 : : {
155 : 17704113 : if (x != 0)
156 : 17704113 : gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
157 : :
158 : 17704113 : 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 : 17704113 : mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
166 : : {
167 : 17704113 : gcc_checking_assert (x != HOST_WIDE_INT_MIN
168 : : && y != HOST_WIDE_INT_MIN);
169 : :
170 : 17704113 : if (x >= 0)
171 : : {
172 : 17704113 : if (y >= 0)
173 : 17704113 : 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 : 17704113 : least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
188 : : {
189 : 17704113 : return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
190 : : }
|
