]>
Commit | Line | Data |
---|---|---|
c59ffc41 JM |
1 | /* Operations on HOST_WIDE_INT. |
2 | Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
3 | 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 | |
4 | Free Software Foundation, Inc. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under | |
9 | the terms of the GNU General Public License as published by the Free | |
10 | Software Foundation; either version 3, or (at your option) any later | |
11 | version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
3c67fd9c | 24 | #include "diagnostic-core.h" |
c59ffc41 JM |
25 | |
26 | #if GCC_VERSION < 3004 | |
27 | ||
46d33ae9 SB |
28 | /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2, |
29 | and exact_log2 are defined as inline functions in hwint.h | |
30 | if GCC_VERSION >= 3004. | |
31 | The definitions here are used for older versions of GCC and | |
32 | non-GCC bootstrap compilers. */ | |
c59ffc41 JM |
33 | |
34 | /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X. | |
35 | If X is 0, return -1. */ | |
36 | ||
37 | int | |
38 | floor_log2 (unsigned HOST_WIDE_INT x) | |
39 | { | |
40 | int t = 0; | |
41 | ||
42 | if (x == 0) | |
43 | return -1; | |
44 | ||
45 | if (HOST_BITS_PER_WIDE_INT > 64) | |
46 | if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64)) | |
47 | t += 64; | |
48 | if (HOST_BITS_PER_WIDE_INT > 32) | |
49 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32)) | |
50 | t += 32; | |
51 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16)) | |
52 | t += 16; | |
53 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8)) | |
54 | t += 8; | |
55 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4)) | |
56 | t += 4; | |
57 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2)) | |
58 | t += 2; | |
59 | if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1)) | |
60 | t += 1; | |
61 | ||
62 | return t; | |
63 | } | |
64 | ||
46d33ae9 SB |
65 | /* Given X, an unsigned number, return the largest Y such that 2**Y >= X. */ |
66 | ||
67 | int | |
68 | ceil_log2 (unsigned HOST_WIDE_INT x) | |
69 | { | |
70 | return floor_log2 (x - 1) + 1; | |
71 | } | |
72 | ||
c59ffc41 JM |
73 | /* Return the logarithm of X, base 2, considering X unsigned, |
74 | if X is a power of 2. Otherwise, returns -1. */ | |
75 | ||
76 | int | |
77 | exact_log2 (unsigned HOST_WIDE_INT x) | |
78 | { | |
79 | if (x != (x & -x)) | |
80 | return -1; | |
81 | return floor_log2 (x); | |
82 | } | |
83 | ||
84 | /* Given X, an unsigned number, return the number of least significant bits | |
85 | that are zero. When X == 0, the result is the word size. */ | |
86 | ||
87 | int | |
88 | ctz_hwi (unsigned HOST_WIDE_INT x) | |
89 | { | |
90 | return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT; | |
91 | } | |
92 | ||
93 | /* Similarly for most significant bits. */ | |
94 | ||
95 | int | |
96 | clz_hwi (unsigned HOST_WIDE_INT x) | |
97 | { | |
98 | return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x); | |
99 | } | |
100 | ||
101 | /* Similar to ctz_hwi, except that the least significant bit is numbered | |
102 | starting from 1, and X == 0 yields 0. */ | |
103 | ||
104 | int | |
105 | ffs_hwi (unsigned HOST_WIDE_INT x) | |
106 | { | |
107 | return 1 + floor_log2 (x & -x); | |
108 | } | |
109 | ||
440b6d59 TV |
110 | /* Return the number of set bits in X. */ |
111 | ||
112 | int | |
113 | popcount_hwi (unsigned HOST_WIDE_INT x) | |
114 | { | |
115 | int i, ret = 0; | |
7cb151c0 | 116 | size_t bits = sizeof (x) * CHAR_BIT; |
440b6d59 | 117 | |
7cb151c0 | 118 | for (i = 0; i < bits; i += 1) |
440b6d59 TV |
119 | { |
120 | ret += x & 1; | |
121 | x >>= 1; | |
122 | } | |
123 | ||
124 | return ret; | |
125 | } | |
126 | ||
c59ffc41 | 127 | #endif /* GCC_VERSION < 3004 */ |
3c67fd9c SP |
128 | |
129 | /* Compute the absolute value of X. */ | |
130 | ||
131 | HOST_WIDE_INT | |
132 | abs_hwi (HOST_WIDE_INT x) | |
133 | { | |
134 | gcc_checking_assert (x != HOST_WIDE_INT_MIN); | |
135 | return x >= 0 ? x : -x; | |
136 | } | |
137 | ||
4c9cf7af PC |
138 | /* Compute the absolute value of X as an unsigned type. */ |
139 | ||
140 | unsigned HOST_WIDE_INT | |
141 | absu_hwi (HOST_WIDE_INT x) | |
142 | { | |
143 | return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x; | |
144 | } | |
145 | ||
3c67fd9c SP |
146 | /* Compute the greatest common divisor of two numbers A and B using |
147 | Euclid's algorithm. */ | |
148 | ||
149 | HOST_WIDE_INT | |
150 | gcd (HOST_WIDE_INT a, HOST_WIDE_INT b) | |
151 | { | |
152 | HOST_WIDE_INT x, y, z; | |
153 | ||
154 | x = abs_hwi (a); | |
155 | y = abs_hwi (b); | |
156 | ||
157 | while (x > 0) | |
158 | { | |
159 | z = y % x; | |
160 | y = x; | |
161 | x = z; | |
162 | } | |
163 | ||
164 | return y; | |
165 | } | |
166 | ||
167 | /* For X and Y positive integers, return X multiplied by Y and check | |
168 | that the result does not overflow. */ | |
169 | ||
170 | HOST_WIDE_INT | |
171 | pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) | |
172 | { | |
173 | if (x != 0) | |
174 | gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y); | |
175 | ||
176 | return x * y; | |
177 | } | |
178 | ||
179 | /* Return X multiplied by Y and check that the result does not | |
180 | overflow. */ | |
181 | ||
182 | HOST_WIDE_INT | |
183 | mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) | |
184 | { | |
185 | gcc_checking_assert (x != HOST_WIDE_INT_MIN | |
186 | && y != HOST_WIDE_INT_MIN); | |
187 | ||
188 | if (x >= 0) | |
189 | { | |
190 | if (y >= 0) | |
191 | return pos_mul_hwi (x, y); | |
192 | ||
193 | return -pos_mul_hwi (x, -y); | |
194 | } | |
195 | ||
196 | if (y >= 0) | |
197 | return -pos_mul_hwi (-x, y); | |
198 | ||
199 | return pos_mul_hwi (-x, -y); | |
200 | } | |
201 | ||
202 | /* Compute the least common multiple of two numbers A and B . */ | |
203 | ||
204 | HOST_WIDE_INT | |
205 | least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b) | |
206 | { | |
207 | return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b)); | |
208 | } |