1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#ifndef HOST_UTILS_H
26#define HOST_UTILS_H 1
27
28#include "qemu/bswap.h"
29
30#ifdef CONFIG_INT128
31static inline void mulu64(uint64_t *plow, uint64_t *phigh,
32 uint64_t a, uint64_t b)
33{
34 __uint128_t r = (__uint128_t)a * b;
35 *plow = r;
36 *phigh = r >> 64;
37}
38
39static inline void muls64(uint64_t *plow, uint64_t *phigh,
40 int64_t a, int64_t b)
41{
42 __int128_t r = (__int128_t)a * b;
43 *plow = r;
44 *phigh = r >> 64;
45}
46
47
48static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
49{
50 return (__int128_t)a * b / c;
51}
52
53static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
54{
55 if (divisor == 0) {
56 return 1;
57 } else {
58 __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
59 __uint128_t result = dividend / divisor;
60 *plow = result;
61 *phigh = dividend % divisor;
62 return result > UINT64_MAX;
63 }
64}
65
66static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
67{
68 if (divisor == 0) {
69 return 1;
70 } else {
71 __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
72 __int128_t result = dividend / divisor;
73 *plow = result;
74 *phigh = dividend % divisor;
75 return result != *plow;
76 }
77}
78#else
79void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
80void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
81int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
82int divs128(int64_t *plow, int64_t *phigh, int64_t divisor);
83
84static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
85{
86 union {
87 uint64_t ll;
88 struct {
89#ifdef HOST_WORDS_BIGENDIAN
90 uint32_t high, low;
91#else
92 uint32_t low, high;
93#endif
94 } l;
95 } u, res;
96 uint64_t rl, rh;
97
98 u.ll = a;
99 rl = (uint64_t)u.l.low * (uint64_t)b;
100 rh = (uint64_t)u.l.high * (uint64_t)b;
101 rh += (rl >> 32);
102 res.l.high = rh / c;
103 res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c;
104 return res.ll;
105}
106#endif
107
108
109
110
111
112
113
114
115static inline int clz32(uint32_t val)
116{
117#if QEMU_GNUC_PREREQ(3, 4)
118 return val ? __builtin_clz(val) : 32;
119#else
120
121 int cnt = 0;
122
123 if (!(val & 0xFFFF0000U)) {
124 cnt += 16;
125 val <<= 16;
126 }
127 if (!(val & 0xFF000000U)) {
128 cnt += 8;
129 val <<= 8;
130 }
131 if (!(val & 0xF0000000U)) {
132 cnt += 4;
133 val <<= 4;
134 }
135 if (!(val & 0xC0000000U)) {
136 cnt += 2;
137 val <<= 2;
138 }
139 if (!(val & 0x80000000U)) {
140 cnt++;
141 val <<= 1;
142 }
143 if (!(val & 0x80000000U)) {
144 cnt++;
145 }
146 return cnt;
147#endif
148}
149
150
151
152
153
154
155
156static inline int clo32(uint32_t val)
157{
158 return clz32(~val);
159}
160
161
162
163
164
165
166
167
168static inline int clz64(uint64_t val)
169{
170#if QEMU_GNUC_PREREQ(3, 4)
171 return val ? __builtin_clzll(val) : 64;
172#else
173 int cnt = 0;
174
175 if (!(val >> 32)) {
176 cnt += 32;
177 } else {
178 val >>= 32;
179 }
180
181 return cnt + clz32(val);
182#endif
183}
184
185
186
187
188
189
190
191static inline int clo64(uint64_t val)
192{
193 return clz64(~val);
194}
195
196
197
198
199
200
201
202
203static inline int ctz32(uint32_t val)
204{
205#if QEMU_GNUC_PREREQ(3, 4)
206 return val ? __builtin_ctz(val) : 32;
207#else
208
209 int cnt;
210
211 cnt = 0;
212 if (!(val & 0x0000FFFFUL)) {
213 cnt += 16;
214 val >>= 16;
215 }
216 if (!(val & 0x000000FFUL)) {
217 cnt += 8;
218 val >>= 8;
219 }
220 if (!(val & 0x0000000FUL)) {
221 cnt += 4;
222 val >>= 4;
223 }
224 if (!(val & 0x00000003UL)) {
225 cnt += 2;
226 val >>= 2;
227 }
228 if (!(val & 0x00000001UL)) {
229 cnt++;
230 val >>= 1;
231 }
232 if (!(val & 0x00000001UL)) {
233 cnt++;
234 }
235
236 return cnt;
237#endif
238}
239
240
241
242
243
244
245
246static inline int cto32(uint32_t val)
247{
248 return ctz32(~val);
249}
250
251
252
253
254
255
256
257
258static inline int ctz64(uint64_t val)
259{
260#if QEMU_GNUC_PREREQ(3, 4)
261 return val ? __builtin_ctzll(val) : 64;
262#else
263 int cnt;
264
265 cnt = 0;
266 if (!((uint32_t)val)) {
267 cnt += 32;
268 val >>= 32;
269 }
270
271 return cnt + ctz32(val);
272#endif
273}
274
275
276
277
278
279
280
281static inline int cto64(uint64_t val)
282{
283 return ctz64(~val);
284}
285
286
287
288
289
290
291
292
293static inline int clrsb32(uint32_t val)
294{
295#if QEMU_GNUC_PREREQ(4, 7)
296 return __builtin_clrsb(val);
297#else
298 return clz32(val ^ ((int32_t)val >> 1)) - 1;
299#endif
300}
301
302
303
304
305
306
307
308
309static inline int clrsb64(uint64_t val)
310{
311#if QEMU_GNUC_PREREQ(4, 7)
312 return __builtin_clrsbll(val);
313#else
314 return clz64(val ^ ((int64_t)val >> 1)) - 1;
315#endif
316}
317
318
319
320
321
322static inline int ctpop8(uint8_t val)
323{
324#if QEMU_GNUC_PREREQ(3, 4)
325 return __builtin_popcount(val);
326#else
327 val = (val & 0x55) + ((val >> 1) & 0x55);
328 val = (val & 0x33) + ((val >> 2) & 0x33);
329 val = (val & 0x0f) + ((val >> 4) & 0x0f);
330
331 return val;
332#endif
333}
334
335
336
337
338
339static inline int ctpop16(uint16_t val)
340{
341#if QEMU_GNUC_PREREQ(3, 4)
342 return __builtin_popcount(val);
343#else
344 val = (val & 0x5555) + ((val >> 1) & 0x5555);
345 val = (val & 0x3333) + ((val >> 2) & 0x3333);
346 val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
347 val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
348
349 return val;
350#endif
351}
352
353
354
355
356
357static inline int ctpop32(uint32_t val)
358{
359#if QEMU_GNUC_PREREQ(3, 4)
360 return __builtin_popcount(val);
361#else
362 val = (val & 0x55555555) + ((val >> 1) & 0x55555555);
363 val = (val & 0x33333333) + ((val >> 2) & 0x33333333);
364 val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f);
365 val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff);
366 val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff);
367
368 return val;
369#endif
370}
371
372
373
374
375
376static inline int ctpop64(uint64_t val)
377{
378#if QEMU_GNUC_PREREQ(3, 4)
379 return __builtin_popcountll(val);
380#else
381 val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL);
382 val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL);
383 val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL);
384 val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL);
385 val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL);
386 val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL);
387
388 return val;
389#endif
390}
391
392
393
394
395
396static inline uint8_t revbit8(uint8_t x)
397{
398
399 x = ((x & 0xf0) >> 4)
400 | ((x & 0x0f) << 4);
401
402 x = ((x & 0x88) >> 3)
403 | ((x & 0x44) >> 1)
404 | ((x & 0x22) << 1)
405 | ((x & 0x11) << 3);
406 return x;
407}
408
409
410
411
412
413static inline uint16_t revbit16(uint16_t x)
414{
415
416 x = bswap16(x);
417
418 x = ((x & 0xf0f0) >> 4)
419 | ((x & 0x0f0f) << 4);
420
421 x = ((x & 0x8888) >> 3)
422 | ((x & 0x4444) >> 1)
423 | ((x & 0x2222) << 1)
424 | ((x & 0x1111) << 3);
425 return x;
426}
427
428
429
430
431
432static inline uint32_t revbit32(uint32_t x)
433{
434
435 x = bswap32(x);
436
437 x = ((x & 0xf0f0f0f0u) >> 4)
438 | ((x & 0x0f0f0f0fu) << 4);
439
440 x = ((x & 0x88888888u) >> 3)
441 | ((x & 0x44444444u) >> 1)
442 | ((x & 0x22222222u) << 1)
443 | ((x & 0x11111111u) << 3);
444 return x;
445}
446
447
448
449
450
451static inline uint64_t revbit64(uint64_t x)
452{
453
454 x = bswap64(x);
455
456 x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
457 | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
458
459 x = ((x & 0x8888888888888888ull) >> 3)
460 | ((x & 0x4444444444444444ull) >> 1)
461 | ((x & 0x2222222222222222ull) << 1)
462 | ((x & 0x1111111111111111ull) << 3);
463 return x;
464}
465
466
467
468#if ULONG_MAX == UINT32_MAX
469# define clzl clz32
470# define ctzl ctz32
471# define clol clo32
472# define ctol cto32
473# define ctpopl ctpop32
474# define revbitl revbit32
475#elif ULONG_MAX == UINT64_MAX
476# define clzl clz64
477# define ctzl ctz64
478# define clol clo64
479# define ctol cto64
480# define ctpopl ctpop64
481# define revbitl revbit64
482#else
483# error Unknown sizeof long
484#endif
485
486static inline bool is_power_of_2(uint64_t value)
487{
488 if (!value) {
489 return 0;
490 }
491
492 return !(value & (value - 1));
493}
494
495
496static inline int64_t pow2floor(int64_t value)
497{
498 if (!is_power_of_2(value)) {
499 value = 0x8000000000000000ULL >> clz64(value);
500 }
501 return value;
502}
503
504
505static inline uint64_t pow2ceil(uint64_t value)
506{
507 uint8_t nlz = clz64(value);
508
509 if (is_power_of_2(value)) {
510 return value;
511 }
512 if (!nlz) {
513 return 0;
514 }
515 return 1ULL << (64 - nlz);
516}
517
518#endif
519