]>
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 JM |
46 | } |
47 | #else | |
05e1d830 | 48 | void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b); |
7a51ad82 JM |
49 | void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); |
50 | #endif | |
51 | ||
72d81155 RH |
52 | /** |
53 | * clz32 - count leading zeros in a 32-bit value. | |
54 | * @val: The value to search | |
55 | * | |
56 | * Returns 32 if the value is zero. Note that the GCC builtin is | |
57 | * undefined if the value is zero. | |
58 | */ | |
facd2857 | 59 | static inline int clz32(uint32_t val) |
05f778c8 | 60 | { |
bad5b1ec | 61 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 62 | return val ? __builtin_clz(val) : 32; |
7d019980 | 63 | #else |
72d81155 | 64 | /* Binary search for the leading one bit. */ |
05f778c8 TS |
65 | int cnt = 0; |
66 | ||
67 | if (!(val & 0xFFFF0000U)) { | |
68 | cnt += 16; | |
69 | val <<= 16; | |
70 | } | |
71 | if (!(val & 0xFF000000U)) { | |
72 | cnt += 8; | |
73 | val <<= 8; | |
74 | } | |
75 | if (!(val & 0xF0000000U)) { | |
76 | cnt += 4; | |
77 | val <<= 4; | |
78 | } | |
79 | if (!(val & 0xC0000000U)) { | |
80 | cnt += 2; | |
81 | val <<= 2; | |
82 | } | |
83 | if (!(val & 0x80000000U)) { | |
84 | cnt++; | |
85 | val <<= 1; | |
86 | } | |
87 | if (!(val & 0x80000000U)) { | |
88 | cnt++; | |
89 | } | |
90 | return cnt; | |
7d019980 | 91 | #endif |
05f778c8 TS |
92 | } |
93 | ||
72d81155 RH |
94 | /** |
95 | * clo32 - count leading ones in a 32-bit value. | |
96 | * @val: The value to search | |
97 | * | |
98 | * Returns 32 if the value is -1. | |
99 | */ | |
facd2857 | 100 | static inline int clo32(uint32_t val) |
05f778c8 TS |
101 | { |
102 | return clz32(~val); | |
103 | } | |
104 | ||
72d81155 RH |
105 | /** |
106 | * clz64 - count leading zeros in a 64-bit value. | |
107 | * @val: The value to search | |
108 | * | |
109 | * Returns 64 if the value is zero. Note that the GCC builtin is | |
110 | * undefined if the value is zero. | |
111 | */ | |
facd2857 | 112 | static inline int clz64(uint64_t val) |
05f778c8 | 113 | { |
bad5b1ec | 114 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 115 | return val ? __builtin_clzll(val) : 64; |
7d019980 | 116 | #else |
05f778c8 TS |
117 | int cnt = 0; |
118 | ||
7a51ad82 | 119 | if (!(val >> 32)) { |
05f778c8 | 120 | cnt += 32; |
7a51ad82 JM |
121 | } else { |
122 | val >>= 32; | |
05f778c8 | 123 | } |
7a51ad82 JM |
124 | |
125 | return cnt + clz32(val); | |
7d019980 | 126 | #endif |
05f778c8 TS |
127 | } |
128 | ||
72d81155 RH |
129 | /** |
130 | * clo64 - count leading ones in a 64-bit value. | |
131 | * @val: The value to search | |
132 | * | |
133 | * Returns 64 if the value is -1. | |
134 | */ | |
facd2857 | 135 | static inline int clo64(uint64_t val) |
05f778c8 TS |
136 | { |
137 | return clz64(~val); | |
138 | } | |
b9ef45ff | 139 | |
72d81155 RH |
140 | /** |
141 | * ctz32 - count trailing zeros in a 32-bit value. | |
142 | * @val: The value to search | |
143 | * | |
144 | * Returns 32 if the value is zero. Note that the GCC builtin is | |
145 | * undefined if the value is zero. | |
146 | */ | |
facd2857 | 147 | static inline int ctz32(uint32_t val) |
b9ef45ff | 148 | { |
bad5b1ec | 149 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 150 | return val ? __builtin_ctz(val) : 32; |
7d019980 | 151 | #else |
72d81155 | 152 | /* Binary search for the trailing one bit. */ |
b9ef45ff JM |
153 | int cnt; |
154 | ||
155 | cnt = 0; | |
156 | if (!(val & 0x0000FFFFUL)) { | |
c8906845 | 157 | cnt += 16; |
b9ef45ff | 158 | val >>= 16; |
c8906845 | 159 | } |
b9ef45ff | 160 | if (!(val & 0x000000FFUL)) { |
c8906845 | 161 | cnt += 8; |
b9ef45ff | 162 | val >>= 8; |
c8906845 | 163 | } |
b9ef45ff | 164 | if (!(val & 0x0000000FUL)) { |
c8906845 | 165 | cnt += 4; |
b9ef45ff | 166 | val >>= 4; |
c8906845 | 167 | } |
b9ef45ff | 168 | if (!(val & 0x00000003UL)) { |
c8906845 | 169 | cnt += 2; |
b9ef45ff | 170 | val >>= 2; |
c8906845 | 171 | } |
b9ef45ff | 172 | if (!(val & 0x00000001UL)) { |
c8906845 | 173 | cnt++; |
b9ef45ff | 174 | val >>= 1; |
c8906845 | 175 | } |
b9ef45ff | 176 | if (!(val & 0x00000001UL)) { |
c8906845 AZ |
177 | cnt++; |
178 | } | |
b9ef45ff | 179 | |
c8906845 | 180 | return cnt; |
7d019980 | 181 | #endif |
c8906845 AZ |
182 | } |
183 | ||
72d81155 RH |
184 | /** |
185 | * cto32 - count trailing ones in a 32-bit value. | |
186 | * @val: The value to search | |
187 | * | |
188 | * Returns 32 if the value is -1. | |
189 | */ | |
facd2857 | 190 | static inline int cto32(uint32_t val) |
c8906845 | 191 | { |
b9ef45ff JM |
192 | return ctz32(~val); |
193 | } | |
194 | ||
72d81155 RH |
195 | /** |
196 | * ctz64 - count trailing zeros in a 64-bit value. | |
197 | * @val: The value to search | |
198 | * | |
199 | * Returns 64 if the value is zero. Note that the GCC builtin is | |
200 | * undefined if the value is zero. | |
201 | */ | |
facd2857 | 202 | static inline int ctz64(uint64_t val) |
b9ef45ff | 203 | { |
bad5b1ec | 204 | #if QEMU_GNUC_PREREQ(3, 4) |
72d81155 | 205 | return val ? __builtin_ctzll(val) : 64; |
7d019980 | 206 | #else |
b9ef45ff JM |
207 | int cnt; |
208 | ||
209 | cnt = 0; | |
210 | if (!((uint32_t)val)) { | |
211 | cnt += 32; | |
212 | val >>= 32; | |
213 | } | |
214 | ||
215 | return cnt + ctz32(val); | |
7d019980 | 216 | #endif |
b9ef45ff JM |
217 | } |
218 | ||
72d81155 RH |
219 | /** |
220 | * ctz64 - count trailing ones in a 64-bit value. | |
221 | * @val: The value to search | |
222 | * | |
223 | * Returns 64 if the value is -1. | |
224 | */ | |
facd2857 | 225 | static inline int cto64(uint64_t val) |
b9ef45ff JM |
226 | { |
227 | return ctz64(~val); | |
228 | } | |
229 | ||
72d81155 RH |
230 | /** |
231 | * ctpop8 - count the population of one bits in an 8-bit value. | |
232 | * @val: The value to search | |
233 | */ | |
facd2857 | 234 | static inline int ctpop8(uint8_t val) |
b9ef45ff | 235 | { |
72d81155 RH |
236 | #if QEMU_GNUC_PREREQ(3, 4) |
237 | return __builtin_popcount(val); | |
238 | #else | |
b9ef45ff JM |
239 | val = (val & 0x55) + ((val >> 1) & 0x55); |
240 | val = (val & 0x33) + ((val >> 2) & 0x33); | |
241 | val = (val & 0x0f) + ((val >> 4) & 0x0f); | |
242 | ||
243 | return val; | |
72d81155 | 244 | #endif |
b9ef45ff JM |
245 | } |
246 | ||
72d81155 RH |
247 | /** |
248 | * ctpop16 - count the population of one bits in a 16-bit value. | |
249 | * @val: The value to search | |
250 | */ | |
facd2857 | 251 | static inline int ctpop16(uint16_t val) |
b9ef45ff | 252 | { |
72d81155 RH |
253 | #if QEMU_GNUC_PREREQ(3, 4) |
254 | return __builtin_popcount(val); | |
255 | #else | |
b9ef45ff JM |
256 | val = (val & 0x5555) + ((val >> 1) & 0x5555); |
257 | val = (val & 0x3333) + ((val >> 2) & 0x3333); | |
258 | val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f); | |
259 | val = (val & 0x00ff) + ((val >> 8) & 0x00ff); | |
260 | ||
261 | return val; | |
72d81155 | 262 | #endif |
b9ef45ff JM |
263 | } |
264 | ||
72d81155 RH |
265 | /** |
266 | * ctpop32 - count the population of one bits in a 32-bit value. | |
267 | * @val: The value to search | |
268 | */ | |
facd2857 | 269 | static inline int ctpop32(uint32_t val) |
b9ef45ff | 270 | { |
bad5b1ec | 271 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
272 | return __builtin_popcount(val); |
273 | #else | |
b9ef45ff JM |
274 | val = (val & 0x55555555) + ((val >> 1) & 0x55555555); |
275 | val = (val & 0x33333333) + ((val >> 2) & 0x33333333); | |
276 | val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f); | |
277 | val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff); | |
278 | val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff); | |
279 | ||
280 | return val; | |
7d019980 | 281 | #endif |
b9ef45ff JM |
282 | } |
283 | ||
72d81155 RH |
284 | /** |
285 | * ctpop64 - count the population of one bits in a 64-bit value. | |
286 | * @val: The value to search | |
287 | */ | |
facd2857 | 288 | static inline int ctpop64(uint64_t val) |
b9ef45ff | 289 | { |
bad5b1ec | 290 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
291 | return __builtin_popcountll(val); |
292 | #else | |
b9ef45ff JM |
293 | val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL); |
294 | val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL); | |
295 | val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL); | |
296 | val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL); | |
297 | val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL); | |
298 | val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL); | |
299 | ||
300 | return val; | |
7d019980 | 301 | #endif |
3800af9e | 302 | } |
cb9c377f | 303 | |
01654373 RH |
304 | /* Host type specific sizes of these routines. */ |
305 | ||
306 | #if ULONG_MAX == UINT32_MAX | |
307 | # define clzl clz32 | |
308 | # define ctzl ctz32 | |
309 | # define clol clo32 | |
310 | # define ctol cto32 | |
311 | # define ctpopl ctpop32 | |
312 | #elif ULONG_MAX == UINT64_MAX | |
313 | # define clzl clz64 | |
314 | # define ctzl ctz64 | |
315 | # define clol clo64 | |
316 | # define ctol cto64 | |
317 | # define ctpopl ctpop64 | |
318 | #else | |
319 | # error Unknown sizeof long | |
320 | #endif | |
321 | ||
cb9c377f | 322 | #endif |