]>
Commit | Line | Data |
---|---|---|
05f778c8 TS |
1 | /* |
2 | * Utility compute operations used by translated code. | |
3 | * | |
4 | * Copyright (c) 2007 Thiemo Seufer | |
5 | * Copyright (c) 2007 Jocelyn Mayer | |
6 | * | |
7 | * Permission is hereby granted, free of charge, to any person obtaining a copy | |
8 | * of this software and associated documentation files (the "Software"), to deal | |
9 | * in the Software without restriction, including without limitation the rights | |
10 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
11 | * copies of the Software, and to permit persons to whom the Software is | |
12 | * furnished to do so, subject to the following conditions: | |
13 | * | |
14 | * The above copyright notice and this permission notice shall be included in | |
15 | * all copies or substantial portions of the Software. | |
16 | * | |
17 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
18 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
19 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
20 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
21 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
22 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
23 | * THE SOFTWARE. | |
24 | */ | |
cb9c377f PB |
25 | #ifndef HOST_UTILS_H |
26 | #define HOST_UTILS_H 1 | |
05f778c8 | 27 | |
1de7afc9 | 28 | #include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */ |
01654373 | 29 | #include <limits.h> |
cebdff77 | 30 | |
f540166b | 31 | #ifdef CONFIG_INT128 |
facd2857 BS |
32 | static inline void mulu64(uint64_t *plow, uint64_t *phigh, |
33 | uint64_t a, uint64_t b) | |
7a51ad82 | 34 | { |
f540166b RH |
35 | __uint128_t r = (__uint128_t)a * b; |
36 | *plow = r; | |
37 | *phigh = r >> 64; | |
7a51ad82 | 38 | } |
f540166b | 39 | |
facd2857 BS |
40 | static inline void muls64(uint64_t *plow, uint64_t *phigh, |
41 | int64_t a, int64_t b) | |
7a51ad82 | 42 | { |
f540166b RH |
43 | __int128_t r = (__int128_t)a * b; |
44 | *plow = r; | |
45 | *phigh = r >> 64; | |
7a51ad82 | 46 | } |
98d1eb27 TM |
47 | |
48 | static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) | |
49 | { | |
50 | if (divisor == 0) { | |
51 | return 1; | |
52 | } else { | |
53 | __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow; | |
54 | __uint128_t result = dividend / divisor; | |
55 | *plow = result; | |
56 | *phigh = dividend % divisor; | |
57 | return result > UINT64_MAX; | |
58 | } | |
59 | } | |
e44259b6 TM |
60 | |
61 | static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) | |
62 | { | |
63 | if (divisor == 0) { | |
64 | return 1; | |
65 | } else { | |
66 | __int128_t dividend = ((__int128_t)*phigh << 64) | *plow; | |
67 | __int128_t result = dividend / divisor; | |
68 | *plow = result; | |
69 | *phigh = dividend % divisor; | |
70 | return result != *plow; | |
71 | } | |
72 | } | |
7a51ad82 | 73 | #else |
05e1d830 | 74 | void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b); |
7a51ad82 | 75 | void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); |
98d1eb27 | 76 | int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor); |
e44259b6 | 77 | int divs128(int64_t *plow, int64_t *phigh, int64_t divisor); |
7a51ad82 JM |
78 | #endif |
79 | ||
72d81155 RH |
80 | /** |
81 | * clz32 - count leading zeros in a 32-bit value. | |
82 | * @val: The value to search | |
83 | * | |
84 | * Returns 32 if the value is zero. Note that the GCC builtin is | |
85 | * undefined if the value is zero. | |
86 | */ | |
facd2857 | 87 | static inline int clz32(uint32_t val) |
05f778c8 | 88 | { |
bad5b1ec | 89 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 90 | return val ? __builtin_clz(val) : 32; |
7d019980 | 91 | #else |
72d81155 | 92 | /* Binary search for the leading one bit. */ |
05f778c8 TS |
93 | int cnt = 0; |
94 | ||
95 | if (!(val & 0xFFFF0000U)) { | |
96 | cnt += 16; | |
97 | val <<= 16; | |
98 | } | |
99 | if (!(val & 0xFF000000U)) { | |
100 | cnt += 8; | |
101 | val <<= 8; | |
102 | } | |
103 | if (!(val & 0xF0000000U)) { | |
104 | cnt += 4; | |
105 | val <<= 4; | |
106 | } | |
107 | if (!(val & 0xC0000000U)) { | |
108 | cnt += 2; | |
109 | val <<= 2; | |
110 | } | |
111 | if (!(val & 0x80000000U)) { | |
112 | cnt++; | |
113 | val <<= 1; | |
114 | } | |
115 | if (!(val & 0x80000000U)) { | |
116 | cnt++; | |
117 | } | |
118 | return cnt; | |
7d019980 | 119 | #endif |
05f778c8 TS |
120 | } |
121 | ||
72d81155 RH |
122 | /** |
123 | * clo32 - count leading ones in a 32-bit value. | |
124 | * @val: The value to search | |
125 | * | |
126 | * Returns 32 if the value is -1. | |
127 | */ | |
facd2857 | 128 | static inline int clo32(uint32_t val) |
05f778c8 TS |
129 | { |
130 | return clz32(~val); | |
131 | } | |
132 | ||
72d81155 RH |
133 | /** |
134 | * clz64 - count leading zeros in a 64-bit value. | |
135 | * @val: The value to search | |
136 | * | |
137 | * Returns 64 if the value is zero. Note that the GCC builtin is | |
138 | * undefined if the value is zero. | |
139 | */ | |
facd2857 | 140 | static inline int clz64(uint64_t val) |
05f778c8 | 141 | { |
bad5b1ec | 142 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 143 | return val ? __builtin_clzll(val) : 64; |
7d019980 | 144 | #else |
05f778c8 TS |
145 | int cnt = 0; |
146 | ||
7a51ad82 | 147 | if (!(val >> 32)) { |
05f778c8 | 148 | cnt += 32; |
7a51ad82 JM |
149 | } else { |
150 | val >>= 32; | |
05f778c8 | 151 | } |
7a51ad82 JM |
152 | |
153 | return cnt + clz32(val); | |
7d019980 | 154 | #endif |
05f778c8 TS |
155 | } |
156 | ||
72d81155 RH |
157 | /** |
158 | * clo64 - count leading ones in a 64-bit value. | |
159 | * @val: The value to search | |
160 | * | |
161 | * Returns 64 if the value is -1. | |
162 | */ | |
facd2857 | 163 | static inline int clo64(uint64_t val) |
05f778c8 TS |
164 | { |
165 | return clz64(~val); | |
166 | } | |
b9ef45ff | 167 | |
72d81155 RH |
168 | /** |
169 | * ctz32 - count trailing zeros in a 32-bit value. | |
170 | * @val: The value to search | |
171 | * | |
172 | * Returns 32 if the value is zero. Note that the GCC builtin is | |
173 | * undefined if the value is zero. | |
174 | */ | |
facd2857 | 175 | static inline int ctz32(uint32_t val) |
b9ef45ff | 176 | { |
bad5b1ec | 177 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 178 | return val ? __builtin_ctz(val) : 32; |
7d019980 | 179 | #else |
72d81155 | 180 | /* Binary search for the trailing one bit. */ |
b9ef45ff JM |
181 | int cnt; |
182 | ||
183 | cnt = 0; | |
184 | if (!(val & 0x0000FFFFUL)) { | |
c8906845 | 185 | cnt += 16; |
b9ef45ff | 186 | val >>= 16; |
c8906845 | 187 | } |
b9ef45ff | 188 | if (!(val & 0x000000FFUL)) { |
c8906845 | 189 | cnt += 8; |
b9ef45ff | 190 | val >>= 8; |
c8906845 | 191 | } |
b9ef45ff | 192 | if (!(val & 0x0000000FUL)) { |
c8906845 | 193 | cnt += 4; |
b9ef45ff | 194 | val >>= 4; |
c8906845 | 195 | } |
b9ef45ff | 196 | if (!(val & 0x00000003UL)) { |
c8906845 | 197 | cnt += 2; |
b9ef45ff | 198 | val >>= 2; |
c8906845 | 199 | } |
b9ef45ff | 200 | if (!(val & 0x00000001UL)) { |
c8906845 | 201 | cnt++; |
b9ef45ff | 202 | val >>= 1; |
c8906845 | 203 | } |
b9ef45ff | 204 | if (!(val & 0x00000001UL)) { |
c8906845 AZ |
205 | cnt++; |
206 | } | |
b9ef45ff | 207 | |
c8906845 | 208 | return cnt; |
7d019980 | 209 | #endif |
c8906845 AZ |
210 | } |
211 | ||
72d81155 RH |
212 | /** |
213 | * cto32 - count trailing ones in a 32-bit value. | |
214 | * @val: The value to search | |
215 | * | |
216 | * Returns 32 if the value is -1. | |
217 | */ | |
facd2857 | 218 | static inline int cto32(uint32_t val) |
c8906845 | 219 | { |
b9ef45ff JM |
220 | return ctz32(~val); |
221 | } | |
222 | ||
72d81155 RH |
223 | /** |
224 | * ctz64 - count trailing zeros in a 64-bit value. | |
225 | * @val: The value to search | |
226 | * | |
227 | * Returns 64 if the value is zero. Note that the GCC builtin is | |
228 | * undefined if the value is zero. | |
229 | */ | |
facd2857 | 230 | static inline int ctz64(uint64_t val) |
b9ef45ff | 231 | { |
bad5b1ec | 232 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 233 | return val ? __builtin_ctzll(val) : 64; |
7d019980 | 234 | #else |
b9ef45ff JM |
235 | int cnt; |
236 | ||
237 | cnt = 0; | |
238 | if (!((uint32_t)val)) { | |
239 | cnt += 32; | |
240 | val >>= 32; | |
241 | } | |
242 | ||
243 | return cnt + ctz32(val); | |
7d019980 | 244 | #endif |
b9ef45ff JM |
245 | } |
246 | ||
72d81155 | 247 | /** |
1c884abe | 248 | * cto64 - count trailing ones in a 64-bit value. |
72d81155 RH |
249 | * @val: The value to search |
250 | * | |
251 | * Returns 64 if the value is -1. | |
252 | */ | |
facd2857 | 253 | static inline int cto64(uint64_t val) |
b9ef45ff JM |
254 | { |
255 | return ctz64(~val); | |
256 | } | |
257 | ||
afd3fe4c CF |
258 | /** |
259 | * clrsb32 - count leading redundant sign bits in a 32-bit value. | |
260 | * @val: The value to search | |
261 | * | |
262 | * Returns the number of bits following the sign bit that are equal to it. | |
263 | * No special cases; output range is [0-31]. | |
264 | */ | |
265 | static inline int clrsb32(uint32_t val) | |
266 | { | |
267 | #if QEMU_GNUC_PREREQ(4, 7) | |
268 | return __builtin_clrsb(val); | |
269 | #else | |
270 | return clz32(val ^ ((int32_t)val >> 1)) - 1; | |
271 | #endif | |
272 | } | |
273 | ||
274 | /** | |
275 | * clrsb64 - count leading redundant sign bits in a 64-bit value. | |
276 | * @val: The value to search | |
277 | * | |
278 | * Returns the number of bits following the sign bit that are equal to it. | |
279 | * No special cases; output range is [0-63]. | |
280 | */ | |
281 | static inline int clrsb64(uint64_t val) | |
282 | { | |
283 | #if QEMU_GNUC_PREREQ(4, 7) | |
284 | return __builtin_clrsbll(val); | |
285 | #else | |
286 | return clz64(val ^ ((int64_t)val >> 1)) - 1; | |
287 | #endif | |
288 | } | |
289 | ||
72d81155 RH |
290 | /** |
291 | * ctpop8 - count the population of one bits in an 8-bit value. | |
292 | * @val: The value to search | |
293 | */ | |
facd2857 | 294 | static inline int ctpop8(uint8_t val) |
b9ef45ff | 295 | { |
72d81155 RH |
296 | #if QEMU_GNUC_PREREQ(3, 4) |
297 | return __builtin_popcount(val); | |
298 | #else | |
b9ef45ff JM |
299 | val = (val & 0x55) + ((val >> 1) & 0x55); |
300 | val = (val & 0x33) + ((val >> 2) & 0x33); | |
301 | val = (val & 0x0f) + ((val >> 4) & 0x0f); | |
302 | ||
303 | return val; | |
72d81155 | 304 | #endif |
b9ef45ff JM |
305 | } |
306 | ||
72d81155 RH |
307 | /** |
308 | * ctpop16 - count the population of one bits in a 16-bit value. | |
309 | * @val: The value to search | |
310 | */ | |
facd2857 | 311 | static inline int ctpop16(uint16_t val) |
b9ef45ff | 312 | { |
72d81155 RH |
313 | #if QEMU_GNUC_PREREQ(3, 4) |
314 | return __builtin_popcount(val); | |
315 | #else | |
b9ef45ff JM |
316 | val = (val & 0x5555) + ((val >> 1) & 0x5555); |
317 | val = (val & 0x3333) + ((val >> 2) & 0x3333); | |
318 | val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f); | |
319 | val = (val & 0x00ff) + ((val >> 8) & 0x00ff); | |
320 | ||
321 | return val; | |
72d81155 | 322 | #endif |
b9ef45ff JM |
323 | } |
324 | ||
72d81155 RH |
325 | /** |
326 | * ctpop32 - count the population of one bits in a 32-bit value. | |
327 | * @val: The value to search | |
328 | */ | |
facd2857 | 329 | static inline int ctpop32(uint32_t val) |
b9ef45ff | 330 | { |
bad5b1ec | 331 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
332 | return __builtin_popcount(val); |
333 | #else | |
b9ef45ff JM |
334 | val = (val & 0x55555555) + ((val >> 1) & 0x55555555); |
335 | val = (val & 0x33333333) + ((val >> 2) & 0x33333333); | |
336 | val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f); | |
337 | val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff); | |
338 | val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff); | |
339 | ||
340 | return val; | |
7d019980 | 341 | #endif |
b9ef45ff JM |
342 | } |
343 | ||
72d81155 RH |
344 | /** |
345 | * ctpop64 - count the population of one bits in a 64-bit value. | |
346 | * @val: The value to search | |
347 | */ | |
facd2857 | 348 | static inline int ctpop64(uint64_t val) |
b9ef45ff | 349 | { |
bad5b1ec | 350 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
351 | return __builtin_popcountll(val); |
352 | #else | |
b9ef45ff JM |
353 | val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL); |
354 | val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL); | |
355 | val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL); | |
356 | val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL); | |
357 | val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL); | |
358 | val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL); | |
359 | ||
360 | return val; | |
7d019980 | 361 | #endif |
3800af9e | 362 | } |
cb9c377f | 363 | |
01654373 RH |
364 | /* Host type specific sizes of these routines. */ |
365 | ||
366 | #if ULONG_MAX == UINT32_MAX | |
367 | # define clzl clz32 | |
368 | # define ctzl ctz32 | |
369 | # define clol clo32 | |
370 | # define ctol cto32 | |
371 | # define ctpopl ctpop32 | |
372 | #elif ULONG_MAX == UINT64_MAX | |
373 | # define clzl clz64 | |
374 | # define ctzl ctz64 | |
375 | # define clol clo64 | |
376 | # define ctol cto64 | |
377 | # define ctpopl ctpop64 | |
378 | #else | |
379 | # error Unknown sizeof long | |
380 | #endif | |
381 | ||
cb9c377f | 382 | #endif |