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 #ifdef CONFIG_INT128
mulu64(uint64_t * plow,uint64_t * phigh,uint64_t a,uint64_t b)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
muls64(uint64_t * plow,uint64_t * phigh,int64_t a,int64_t b)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 #else
48 void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
49 void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
50 #endif
51
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 */
clz32(uint32_t val)59 static inline int clz32(uint32_t val)
60 {
61 #if QEMU_GNUC_PREREQ(3, 4)
62 return val ? __builtin_clz(val) : 32;
63 #else
64 /* Binary search for the leading one bit. */
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;
91 #endif
92 }
93
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 */
clo32(uint32_t val)100 static inline int clo32(uint32_t val)
101 {
102 return clz32(~val);
103 }
104
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 */
clz64(uint64_t val)112 static inline int clz64(uint64_t val)
113 {
114 #if QEMU_GNUC_PREREQ(3, 4)
115 return val ? __builtin_clzll(val) : 64;
116 #else
117 int cnt = 0;
118
119 if (!(val >> 32)) {
120 cnt += 32;
121 } else {
122 val >>= 32;
123 }
124
125 return cnt + clz32(val);
126 #endif
127 }
128
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 */
clo64(uint64_t val)135 static inline int clo64(uint64_t val)
136 {
137 return clz64(~val);
138 }
139
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 */
ctz32(uint32_t val)147 static inline int ctz32(uint32_t val)
148 {
149 #if QEMU_GNUC_PREREQ(3, 4)
150 return val ? __builtin_ctz(val) : 32;
151 #else
152 /* Binary search for the trailing one bit. */
153 int cnt;
154
155 cnt = 0;
156 if (!(val & 0x0000FFFFUL)) {
157 cnt += 16;
158 val >>= 16;
159 }
160 if (!(val & 0x000000FFUL)) {
161 cnt += 8;
162 val >>= 8;
163 }
164 if (!(val & 0x0000000FUL)) {
165 cnt += 4;
166 val >>= 4;
167 }
168 if (!(val & 0x00000003UL)) {
169 cnt += 2;
170 val >>= 2;
171 }
172 if (!(val & 0x00000001UL)) {
173 cnt++;
174 val >>= 1;
175 }
176 if (!(val & 0x00000001UL)) {
177 cnt++;
178 }
179
180 return cnt;
181 #endif
182 }
183
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 */
cto32(uint32_t val)190 static inline int cto32(uint32_t val)
191 {
192 return ctz32(~val);
193 }
194
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 */
ctz64(uint64_t val)202 static inline int ctz64(uint64_t val)
203 {
204 #if QEMU_GNUC_PREREQ(3, 4)
205 return val ? __builtin_ctzll(val) : 64;
206 #else
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);
216 #endif
217 }
218
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 */
cto64(uint64_t val)225 static inline int cto64(uint64_t val)
226 {
227 return ctz64(~val);
228 }
229
230 /**
231 * ctpop8 - count the population of one bits in an 8-bit value.
232 * @val: The value to search
233 */
ctpop8(uint8_t val)234 static inline int ctpop8(uint8_t val)
235 {
236 #if QEMU_GNUC_PREREQ(3, 4)
237 return __builtin_popcount(val);
238 #else
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;
244 #endif
245 }
246
247 /**
248 * ctpop16 - count the population of one bits in a 16-bit value.
249 * @val: The value to search
250 */
ctpop16(uint16_t val)251 static inline int ctpop16(uint16_t val)
252 {
253 #if QEMU_GNUC_PREREQ(3, 4)
254 return __builtin_popcount(val);
255 #else
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;
262 #endif
263 }
264
265 /**
266 * ctpop32 - count the population of one bits in a 32-bit value.
267 * @val: The value to search
268 */
ctpop32(uint32_t val)269 static inline int ctpop32(uint32_t val)
270 {
271 #if QEMU_GNUC_PREREQ(3, 4)
272 return __builtin_popcount(val);
273 #else
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;
281 #endif
282 }
283
284 /**
285 * ctpop64 - count the population of one bits in a 64-bit value.
286 * @val: The value to search
287 */
ctpop64(uint64_t val)288 static inline int ctpop64(uint64_t val)
289 {
290 #if QEMU_GNUC_PREREQ(3, 4)
291 return __builtin_popcountll(val);
292 #else
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;
301 #endif
302 }
303
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
322 #endif
323