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