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 | */ |
25 | |
26 | #ifndef HOST_UTILS_H |
27 | #define HOST_UTILS_H |
28 | |
29 | #include "qemu/bswap.h" |
30 | |
31 | #ifdef CONFIG_INT128 |
32 | static inline void mulu64(uint64_t *plow, uint64_t *phigh, |
33 | uint64_t a, uint64_t b) |
34 | { |
35 | __uint128_t r = (__uint128_t)a * b; |
36 | *plow = r; |
37 | *phigh = r >> 64; |
38 | } |
39 | |
40 | static inline void muls64(uint64_t *plow, uint64_t *phigh, |
41 | int64_t a, int64_t b) |
42 | { |
43 | __int128_t r = (__int128_t)a * b; |
44 | *plow = r; |
45 | *phigh = r >> 64; |
46 | } |
47 | |
48 | /* compute with 96 bit intermediate result: (a*b)/c */ |
49 | static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) |
50 | { |
51 | return (__int128_t)a * b / c; |
52 | } |
53 | |
54 | static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) |
55 | { |
56 | if (divisor == 0) { |
57 | return 1; |
58 | } else { |
59 | __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow; |
60 | __uint128_t result = dividend / divisor; |
61 | *plow = result; |
62 | *phigh = dividend % divisor; |
63 | return result > UINT64_MAX; |
64 | } |
65 | } |
66 | |
67 | static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) |
68 | { |
69 | if (divisor == 0) { |
70 | return 1; |
71 | } else { |
72 | __int128_t dividend = ((__int128_t)*phigh << 64) | *plow; |
73 | __int128_t result = dividend / divisor; |
74 | *plow = result; |
75 | *phigh = dividend % divisor; |
76 | return result != *plow; |
77 | } |
78 | } |
79 | #else |
80 | void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b); |
81 | void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); |
82 | int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor); |
83 | int divs128(int64_t *plow, int64_t *phigh, int64_t divisor); |
84 | |
85 | static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) |
86 | { |
87 | union { |
88 | uint64_t ll; |
89 | struct { |
90 | #ifdef HOST_WORDS_BIGENDIAN |
91 | uint32_t high, low; |
92 | #else |
93 | uint32_t low, high; |
94 | #endif |
95 | } l; |
96 | } u, res; |
97 | uint64_t rl, rh; |
98 | |
99 | u.ll = a; |
100 | rl = (uint64_t)u.l.low * (uint64_t)b; |
101 | rh = (uint64_t)u.l.high * (uint64_t)b; |
102 | rh += (rl >> 32); |
103 | res.l.high = rh / c; |
104 | res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c; |
105 | return res.ll; |
106 | } |
107 | #endif |
108 | |
109 | /** |
110 | * clz32 - count leading zeros in a 32-bit value. |
111 | * @val: The value to search |
112 | * |
113 | * Returns 32 if the value is zero. Note that the GCC builtin is |
114 | * undefined if the value is zero. |
115 | */ |
116 | static inline int clz32(uint32_t val) |
117 | { |
118 | return val ? __builtin_clz(val) : 32; |
119 | } |
120 | |
121 | /** |
122 | * clo32 - count leading ones in a 32-bit value. |
123 | * @val: The value to search |
124 | * |
125 | * Returns 32 if the value is -1. |
126 | */ |
127 | static inline int clo32(uint32_t val) |
128 | { |
129 | return clz32(~val); |
130 | } |
131 | |
132 | /** |
133 | * clz64 - count leading zeros in a 64-bit value. |
134 | * @val: The value to search |
135 | * |
136 | * Returns 64 if the value is zero. Note that the GCC builtin is |
137 | * undefined if the value is zero. |
138 | */ |
139 | static inline int clz64(uint64_t val) |
140 | { |
141 | return val ? __builtin_clzll(val) : 64; |
142 | } |
143 | |
144 | /** |
145 | * clo64 - count leading ones in a 64-bit value. |
146 | * @val: The value to search |
147 | * |
148 | * Returns 64 if the value is -1. |
149 | */ |
150 | static inline int clo64(uint64_t val) |
151 | { |
152 | return clz64(~val); |
153 | } |
154 | |
155 | /** |
156 | * ctz32 - count trailing zeros in a 32-bit value. |
157 | * @val: The value to search |
158 | * |
159 | * Returns 32 if the value is zero. Note that the GCC builtin is |
160 | * undefined if the value is zero. |
161 | */ |
162 | static inline int ctz32(uint32_t val) |
163 | { |
164 | return val ? __builtin_ctz(val) : 32; |
165 | } |
166 | |
167 | /** |
168 | * cto32 - count trailing ones in a 32-bit value. |
169 | * @val: The value to search |
170 | * |
171 | * Returns 32 if the value is -1. |
172 | */ |
173 | static inline int cto32(uint32_t val) |
174 | { |
175 | return ctz32(~val); |
176 | } |
177 | |
178 | /** |
179 | * ctz64 - count trailing zeros in a 64-bit value. |
180 | * @val: The value to search |
181 | * |
182 | * Returns 64 if the value is zero. Note that the GCC builtin is |
183 | * undefined if the value is zero. |
184 | */ |
185 | static inline int ctz64(uint64_t val) |
186 | { |
187 | return val ? __builtin_ctzll(val) : 64; |
188 | } |
189 | |
190 | /** |
191 | * cto64 - count trailing ones in a 64-bit value. |
192 | * @val: The value to search |
193 | * |
194 | * Returns 64 if the value is -1. |
195 | */ |
196 | static inline int cto64(uint64_t val) |
197 | { |
198 | return ctz64(~val); |
199 | } |
200 | |
201 | /** |
202 | * clrsb32 - count leading redundant sign bits in a 32-bit value. |
203 | * @val: The value to search |
204 | * |
205 | * Returns the number of bits following the sign bit that are equal to it. |
206 | * No special cases; output range is [0-31]. |
207 | */ |
208 | static inline int clrsb32(uint32_t val) |
209 | { |
210 | #if __has_builtin(__builtin_clrsb) || !defined(__clang__) |
211 | return __builtin_clrsb(val); |
212 | #else |
213 | return clz32(val ^ ((int32_t)val >> 1)) - 1; |
214 | #endif |
215 | } |
216 | |
217 | /** |
218 | * clrsb64 - count leading redundant sign bits in a 64-bit value. |
219 | * @val: The value to search |
220 | * |
221 | * Returns the number of bits following the sign bit that are equal to it. |
222 | * No special cases; output range is [0-63]. |
223 | */ |
224 | static inline int clrsb64(uint64_t val) |
225 | { |
226 | #if __has_builtin(__builtin_clrsbll) || !defined(__clang__) |
227 | return __builtin_clrsbll(val); |
228 | #else |
229 | return clz64(val ^ ((int64_t)val >> 1)) - 1; |
230 | #endif |
231 | } |
232 | |
233 | /** |
234 | * ctpop8 - count the population of one bits in an 8-bit value. |
235 | * @val: The value to search |
236 | */ |
237 | static inline int ctpop8(uint8_t val) |
238 | { |
239 | return __builtin_popcount(val); |
240 | } |
241 | |
242 | /** |
243 | * ctpop16 - count the population of one bits in a 16-bit value. |
244 | * @val: The value to search |
245 | */ |
246 | static inline int ctpop16(uint16_t val) |
247 | { |
248 | return __builtin_popcount(val); |
249 | } |
250 | |
251 | /** |
252 | * ctpop32 - count the population of one bits in a 32-bit value. |
253 | * @val: The value to search |
254 | */ |
255 | static inline int ctpop32(uint32_t val) |
256 | { |
257 | return __builtin_popcount(val); |
258 | } |
259 | |
260 | /** |
261 | * ctpop64 - count the population of one bits in a 64-bit value. |
262 | * @val: The value to search |
263 | */ |
264 | static inline int ctpop64(uint64_t val) |
265 | { |
266 | return __builtin_popcountll(val); |
267 | } |
268 | |
269 | /** |
270 | * revbit8 - reverse the bits in an 8-bit value. |
271 | * @x: The value to modify. |
272 | */ |
273 | static inline uint8_t revbit8(uint8_t x) |
274 | { |
275 | /* Assign the correct nibble position. */ |
276 | x = ((x & 0xf0) >> 4) |
277 | | ((x & 0x0f) << 4); |
278 | /* Assign the correct bit position. */ |
279 | x = ((x & 0x88) >> 3) |
280 | | ((x & 0x44) >> 1) |
281 | | ((x & 0x22) << 1) |
282 | | ((x & 0x11) << 3); |
283 | return x; |
284 | } |
285 | |
286 | /** |
287 | * revbit16 - reverse the bits in a 16-bit value. |
288 | * @x: The value to modify. |
289 | */ |
290 | static inline uint16_t revbit16(uint16_t x) |
291 | { |
292 | /* Assign the correct byte position. */ |
293 | x = bswap16(x); |
294 | /* Assign the correct nibble position. */ |
295 | x = ((x & 0xf0f0) >> 4) |
296 | | ((x & 0x0f0f) << 4); |
297 | /* Assign the correct bit position. */ |
298 | x = ((x & 0x8888) >> 3) |
299 | | ((x & 0x4444) >> 1) |
300 | | ((x & 0x2222) << 1) |
301 | | ((x & 0x1111) << 3); |
302 | return x; |
303 | } |
304 | |
305 | /** |
306 | * revbit32 - reverse the bits in a 32-bit value. |
307 | * @x: The value to modify. |
308 | */ |
309 | static inline uint32_t revbit32(uint32_t x) |
310 | { |
311 | /* Assign the correct byte position. */ |
312 | x = bswap32(x); |
313 | /* Assign the correct nibble position. */ |
314 | x = ((x & 0xf0f0f0f0u) >> 4) |
315 | | ((x & 0x0f0f0f0fu) << 4); |
316 | /* Assign the correct bit position. */ |
317 | x = ((x & 0x88888888u) >> 3) |
318 | | ((x & 0x44444444u) >> 1) |
319 | | ((x & 0x22222222u) << 1) |
320 | | ((x & 0x11111111u) << 3); |
321 | return x; |
322 | } |
323 | |
324 | /** |
325 | * revbit64 - reverse the bits in a 64-bit value. |
326 | * @x: The value to modify. |
327 | */ |
328 | static inline uint64_t revbit64(uint64_t x) |
329 | { |
330 | /* Assign the correct byte position. */ |
331 | x = bswap64(x); |
332 | /* Assign the correct nibble position. */ |
333 | x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4) |
334 | | ((x & 0x0f0f0f0f0f0f0f0full) << 4); |
335 | /* Assign the correct bit position. */ |
336 | x = ((x & 0x8888888888888888ull) >> 3) |
337 | | ((x & 0x4444444444444444ull) >> 1) |
338 | | ((x & 0x2222222222222222ull) << 1) |
339 | | ((x & 0x1111111111111111ull) << 3); |
340 | return x; |
341 | } |
342 | |
343 | /* Host type specific sizes of these routines. */ |
344 | |
345 | #if ULONG_MAX == UINT32_MAX |
346 | # define clzl clz32 |
347 | # define ctzl ctz32 |
348 | # define clol clo32 |
349 | # define ctol cto32 |
350 | # define ctpopl ctpop32 |
351 | # define revbitl revbit32 |
352 | #elif ULONG_MAX == UINT64_MAX |
353 | # define clzl clz64 |
354 | # define ctzl ctz64 |
355 | # define clol clo64 |
356 | # define ctol cto64 |
357 | # define ctpopl ctpop64 |
358 | # define revbitl revbit64 |
359 | #else |
360 | # error Unknown sizeof long |
361 | #endif |
362 | |
363 | static inline bool is_power_of_2(uint64_t value) |
364 | { |
365 | if (!value) { |
366 | return false; |
367 | } |
368 | |
369 | return !(value & (value - 1)); |
370 | } |
371 | |
372 | /** |
373 | * Return @value rounded down to the nearest power of two or zero. |
374 | */ |
375 | static inline uint64_t pow2floor(uint64_t value) |
376 | { |
377 | if (!value) { |
378 | /* Avoid undefined shift by 64 */ |
379 | return 0; |
380 | } |
381 | return 0x8000000000000000ull >> clz64(value); |
382 | } |
383 | |
384 | /* |
385 | * Return @value rounded up to the nearest power of two modulo 2^64. |
386 | * This is *zero* for @value > 2^63, so be careful. |
387 | */ |
388 | static inline uint64_t pow2ceil(uint64_t value) |
389 | { |
390 | int n = clz64(value - 1); |
391 | |
392 | if (!n) { |
393 | /* |
394 | * @value - 1 has no leading zeroes, thus @value - 1 >= 2^63 |
395 | * Therefore, either @value == 0 or @value > 2^63. |
396 | * If it's 0, return 1, else return 0. |
397 | */ |
398 | return !value; |
399 | } |
400 | return 0x8000000000000000ull >> (n - 1); |
401 | } |
402 | |
403 | static inline uint32_t pow2roundup32(uint32_t x) |
404 | { |
405 | x |= (x >> 1); |
406 | x |= (x >> 2); |
407 | x |= (x >> 4); |
408 | x |= (x >> 8); |
409 | x |= (x >> 16); |
410 | return x + 1; |
411 | } |
412 | |
413 | /** |
414 | * urshift - 128-bit Unsigned Right Shift. |
415 | * @plow: in/out - lower 64-bit integer. |
416 | * @phigh: in/out - higher 64-bit integer. |
417 | * @shift: in - bytes to shift, between 0 and 127. |
418 | * |
419 | * Result is zero-extended and stored in plow/phigh, which are |
420 | * input/output variables. Shift values outside the range will |
421 | * be mod to 128. In other words, the caller is responsible to |
422 | * verify/assert both the shift range and plow/phigh pointers. |
423 | */ |
424 | void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift); |
425 | |
426 | /** |
427 | * ulshift - 128-bit Unsigned Left Shift. |
428 | * @plow: in/out - lower 64-bit integer. |
429 | * @phigh: in/out - higher 64-bit integer. |
430 | * @shift: in - bytes to shift, between 0 and 127. |
431 | * @overflow: out - true if any 1-bit is shifted out. |
432 | * |
433 | * Result is zero-extended and stored in plow/phigh, which are |
434 | * input/output variables. Shift values outside the range will |
435 | * be mod to 128. In other words, the caller is responsible to |
436 | * verify/assert both the shift range and plow/phigh pointers. |
437 | */ |
438 | void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow); |
439 | |
440 | #endif |
441 | |