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
26#ifndef HOST_UTILS_H
27#define HOST_UTILS_H
28
29#include "qemu/bswap.h"
30
31#ifdef CONFIG_INT128
32static 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
40static 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
49static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
50{
51 return (__int128_t)a * b / c;
52}
53
54static 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
67static 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
80void muls64(uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b);
81void mulu64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b);
82int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
83int divs128(int64_t *plow, int64_t *phigh, int64_t divisor);
84
85static 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
111
112
113
114
115
116static inline int clz32(uint32_t val)
117{
118 return val ? __builtin_clz(val) : 32;
119}
120
121
122
123
124
125
126
127static inline int clo32(uint32_t val)
128{
129 return clz32(~val);
130}
131
132
133
134
135
136
137
138
139static inline int clz64(uint64_t val)
140{
141 return val ? __builtin_clzll(val) : 64;
142}
143
144
145
146
147
148
149
150static inline int clo64(uint64_t val)
151{
152 return clz64(~val);
153}
154
155
156
157
158
159
160
161
162static inline int ctz32(uint32_t val)
163{
164 return val ? __builtin_ctz(val) : 32;
165}
166
167
168
169
170
171
172
173static inline int cto32(uint32_t val)
174{
175 return ctz32(~val);
176}
177
178
179
180
181
182
183
184
185static inline int ctz64(uint64_t val)
186{
187 return val ? __builtin_ctzll(val) : 64;
188}
189
190
191
192
193
194
195
196static inline int cto64(uint64_t val)
197{
198 return ctz64(~val);
199}
200
201
202
203
204
205
206
207
208static 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
219
220
221
222
223
224static 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
235
236
237static inline int ctpop8(uint8_t val)
238{
239 return __builtin_popcount(val);
240}
241
242
243
244
245
246static inline int ctpop16(uint16_t val)
247{
248 return __builtin_popcount(val);
249}
250
251
252
253
254
255static inline int ctpop32(uint32_t val)
256{
257 return __builtin_popcount(val);
258}
259
260
261
262
263
264static inline int ctpop64(uint64_t val)
265{
266 return __builtin_popcountll(val);
267}
268
269
270
271
272
273static inline uint8_t revbit8(uint8_t x)
274{
275
276 x = ((x & 0xf0) >> 4)
277 | ((x & 0x0f) << 4);
278
279 x = ((x & 0x88) >> 3)
280 | ((x & 0x44) >> 1)
281 | ((x & 0x22) << 1)
282 | ((x & 0x11) << 3);
283 return x;
284}
285
286
287
288
289
290static inline uint16_t revbit16(uint16_t x)
291{
292
293 x = bswap16(x);
294
295 x = ((x & 0xf0f0) >> 4)
296 | ((x & 0x0f0f) << 4);
297
298 x = ((x & 0x8888) >> 3)
299 | ((x & 0x4444) >> 1)
300 | ((x & 0x2222) << 1)
301 | ((x & 0x1111) << 3);
302 return x;
303}
304
305
306
307
308
309static inline uint32_t revbit32(uint32_t x)
310{
311
312 x = bswap32(x);
313
314 x = ((x & 0xf0f0f0f0u) >> 4)
315 | ((x & 0x0f0f0f0fu) << 4);
316
317 x = ((x & 0x88888888u) >> 3)
318 | ((x & 0x44444444u) >> 1)
319 | ((x & 0x22222222u) << 1)
320 | ((x & 0x11111111u) << 3);
321 return x;
322}
323
324
325
326
327
328static inline uint64_t revbit64(uint64_t x)
329{
330
331 x = bswap64(x);
332
333 x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
334 | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
335
336 x = ((x & 0x8888888888888888ull) >> 3)
337 | ((x & 0x4444444444444444ull) >> 1)
338 | ((x & 0x2222222222222222ull) << 1)
339 | ((x & 0x1111111111111111ull) << 3);
340 return x;
341}
342
343
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
363static 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
374
375static inline uint64_t pow2floor(uint64_t value)
376{
377 if (!value) {
378
379 return 0;
380 }
381 return 0x8000000000000000ull >> clz64(value);
382}
383
384
385
386
387
388static inline uint64_t pow2ceil(uint64_t value)
389{
390 int n = clz64(value - 1);
391
392 if (!n) {
393
394
395
396
397
398 return !value;
399 }
400 return 0x8000000000000000ull >> (n - 1);
401}
402
403static 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
415
416
417
418
419
420
421
422
423
424void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift);
425
426
427
428
429
430
431
432
433
434
435
436
437
438void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow);
439
440#endif
441