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/compiler.h"
30#include "qemu/bswap.h"
31
32#ifdef CONFIG_INT128
33static inline void mulu64(uint64_t *plow, uint64_t *phigh,
34 uint64_t a, uint64_t b)
35{
36 __uint128_t r = (__uint128_t)a * b;
37 *plow = r;
38 *phigh = r >> 64;
39}
40
41static inline void muls64(uint64_t *plow, uint64_t *phigh,
42 int64_t a, int64_t b)
43{
44 __int128_t r = (__int128_t)a * b;
45 *plow = r;
46 *phigh = r >> 64;
47}
48
49
50static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
51{
52 return (__int128_t)a * b / c;
53}
54
55static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
56{
57 if (divisor == 0) {
58 return 1;
59 } else {
60 __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
61 __uint128_t result = dividend / divisor;
62 *plow = result;
63 *phigh = dividend % divisor;
64 return result > UINT64_MAX;
65 }
66}
67
68static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
69{
70 if (divisor == 0) {
71 return 1;
72 } else {
73 __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
74 __int128_t result = dividend / divisor;
75 *plow = result;
76 *phigh = dividend % divisor;
77 return result != *plow;
78 }
79}
80#else
81void muls64(uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b);
82void mulu64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b);
83int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
84int divs128(int64_t *plow, int64_t *phigh, int64_t divisor);
85
86static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
87{
88 union {
89 uint64_t ll;
90 struct {
91#ifdef HOST_WORDS_BIGENDIAN
92 uint32_t high, low;
93#else
94 uint32_t low, high;
95#endif
96 } l;
97 } u, res;
98 uint64_t rl, rh;
99
100 u.ll = a;
101 rl = (uint64_t)u.l.low * (uint64_t)b;
102 rh = (uint64_t)u.l.high * (uint64_t)b;
103 rh += (rl >> 32);
104 res.l.high = rh / c;
105 res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c;
106 return res.ll;
107}
108#endif
109
110
111
112
113
114
115
116
117static inline int clz32(uint32_t val)
118{
119 return val ? __builtin_clz(val) : 32;
120}
121
122
123
124
125
126
127
128static inline int clo32(uint32_t val)
129{
130 return clz32(~val);
131}
132
133
134
135
136
137
138
139
140static inline int clz64(uint64_t val)
141{
142 return val ? __builtin_clzll(val) : 64;
143}
144
145
146
147
148
149
150
151static inline int clo64(uint64_t val)
152{
153 return clz64(~val);
154}
155
156
157
158
159
160
161
162
163static inline int ctz32(uint32_t val)
164{
165 return val ? __builtin_ctz(val) : 32;
166}
167
168
169
170
171
172
173
174static inline int cto32(uint32_t val)
175{
176 return ctz32(~val);
177}
178
179
180
181
182
183
184
185
186static inline int ctz64(uint64_t val)
187{
188 return val ? __builtin_ctzll(val) : 64;
189}
190
191
192
193
194
195
196
197static inline int cto64(uint64_t val)
198{
199 return ctz64(~val);
200}
201
202
203
204
205
206
207
208
209static inline int clrsb32(uint32_t val)
210{
211#if __has_builtin(__builtin_clrsb) || !defined(__clang__)
212 return __builtin_clrsb(val);
213#else
214 return clz32(val ^ ((int32_t)val >> 1)) - 1;
215#endif
216}
217
218
219
220
221
222
223
224
225static inline int clrsb64(uint64_t val)
226{
227#if __has_builtin(__builtin_clrsbll) || !defined(__clang__)
228 return __builtin_clrsbll(val);
229#else
230 return clz64(val ^ ((int64_t)val >> 1)) - 1;
231#endif
232}
233
234
235
236
237
238static inline int ctpop8(uint8_t val)
239{
240 return __builtin_popcount(val);
241}
242
243
244
245
246
247static inline int ctpop16(uint16_t val)
248{
249 return __builtin_popcount(val);
250}
251
252
253
254
255
256static inline int ctpop32(uint32_t val)
257{
258 return __builtin_popcount(val);
259}
260
261
262
263
264
265static inline int ctpop64(uint64_t val)
266{
267 return __builtin_popcountll(val);
268}
269
270
271
272
273
274static inline uint8_t revbit8(uint8_t x)
275{
276#if __has_builtin(__builtin_bitreverse8)
277 return __builtin_bitreverse8(x);
278#else
279
280 x = ((x & 0xf0) >> 4)
281 | ((x & 0x0f) << 4);
282
283 x = ((x & 0x88) >> 3)
284 | ((x & 0x44) >> 1)
285 | ((x & 0x22) << 1)
286 | ((x & 0x11) << 3);
287 return x;
288#endif
289}
290
291
292
293
294
295static inline uint16_t revbit16(uint16_t x)
296{
297#if __has_builtin(__builtin_bitreverse16)
298 return __builtin_bitreverse16(x);
299#else
300
301 x = bswap16(x);
302
303 x = ((x & 0xf0f0) >> 4)
304 | ((x & 0x0f0f) << 4);
305
306 x = ((x & 0x8888) >> 3)
307 | ((x & 0x4444) >> 1)
308 | ((x & 0x2222) << 1)
309 | ((x & 0x1111) << 3);
310 return x;
311#endif
312}
313
314
315
316
317
318static inline uint32_t revbit32(uint32_t x)
319{
320#if __has_builtin(__builtin_bitreverse32)
321 return __builtin_bitreverse32(x);
322#else
323
324 x = bswap32(x);
325
326 x = ((x & 0xf0f0f0f0u) >> 4)
327 | ((x & 0x0f0f0f0fu) << 4);
328
329 x = ((x & 0x88888888u) >> 3)
330 | ((x & 0x44444444u) >> 1)
331 | ((x & 0x22222222u) << 1)
332 | ((x & 0x11111111u) << 3);
333 return x;
334#endif
335}
336
337
338
339
340
341static inline uint64_t revbit64(uint64_t x)
342{
343#if __has_builtin(__builtin_bitreverse64)
344 return __builtin_bitreverse64(x);
345#else
346
347 x = bswap64(x);
348
349 x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
350 | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
351
352 x = ((x & 0x8888888888888888ull) >> 3)
353 | ((x & 0x4444444444444444ull) >> 1)
354 | ((x & 0x2222222222222222ull) << 1)
355 | ((x & 0x1111111111111111ull) << 3);
356 return x;
357#endif
358}
359
360
361
362
363
364
365
366
367
368static inline bool sadd32_overflow(int32_t x, int32_t y, int32_t *ret)
369{
370#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
371 return __builtin_add_overflow(x, y, ret);
372#else
373 *ret = x + y;
374 return ((*ret ^ x) & ~(x ^ y)) < 0;
375#endif
376}
377
378
379
380
381
382
383
384
385
386static inline bool sadd64_overflow(int64_t x, int64_t y, int64_t *ret)
387{
388#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
389 return __builtin_add_overflow(x, y, ret);
390#else
391 *ret = x + y;
392 return ((*ret ^ x) & ~(x ^ y)) < 0;
393#endif
394}
395
396
397
398
399
400
401
402
403
404static inline bool uadd32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
405{
406#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
407 return __builtin_add_overflow(x, y, ret);
408#else
409 *ret = x + y;
410 return *ret < x;
411#endif
412}
413
414
415
416
417
418
419
420
421
422static inline bool uadd64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
423{
424#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
425 return __builtin_add_overflow(x, y, ret);
426#else
427 *ret = x + y;
428 return *ret < x;
429#endif
430}
431
432
433
434
435
436
437
438
439
440
441static inline bool ssub32_overflow(int32_t x, int32_t y, int32_t *ret)
442{
443#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
444 return __builtin_sub_overflow(x, y, ret);
445#else
446 *ret = x - y;
447 return ((*ret ^ x) & (x ^ y)) < 0;
448#endif
449}
450
451
452
453
454
455
456
457
458
459
460static inline bool ssub64_overflow(int64_t x, int64_t y, int64_t *ret)
461{
462#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
463 return __builtin_sub_overflow(x, y, ret);
464#else
465 *ret = x - y;
466 return ((*ret ^ x) & (x ^ y)) < 0;
467#endif
468}
469
470
471
472
473
474
475
476
477
478
479static inline bool usub32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
480{
481#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
482 return __builtin_sub_overflow(x, y, ret);
483#else
484 *ret = x - y;
485 return x < y;
486#endif
487}
488
489
490
491
492
493
494
495
496
497
498static inline bool usub64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
499{
500#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
501 return __builtin_sub_overflow(x, y, ret);
502#else
503 *ret = x - y;
504 return x < y;
505#endif
506}
507
508
509
510
511
512
513
514
515
516static inline bool smul32_overflow(int32_t x, int32_t y, int32_t *ret)
517{
518#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
519 return __builtin_mul_overflow(x, y, ret);
520#else
521 int64_t z = (int64_t)x * y;
522 *ret = z;
523 return *ret != z;
524#endif
525}
526
527
528
529
530
531
532
533
534
535static inline bool smul64_overflow(int64_t x, int64_t y, int64_t *ret)
536{
537#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
538 return __builtin_mul_overflow(x, y, ret);
539#else
540 uint64_t hi, lo;
541 muls64(&lo, &hi, x, y);
542 *ret = lo;
543 return hi != ((int64_t)lo >> 63);
544#endif
545}
546
547
548
549
550
551
552
553
554
555static inline bool umul32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
556{
557#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
558 return __builtin_mul_overflow(x, y, ret);
559#else
560 uint64_t z = (uint64_t)x * y;
561 *ret = z;
562 return z > UINT32_MAX;
563#endif
564}
565
566
567
568
569
570
571
572
573
574static inline bool umul64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
575{
576#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
577 return __builtin_mul_overflow(x, y, ret);
578#else
579 uint64_t hi;
580 mulu64(ret, &hi, x, y);
581 return hi != 0;
582#endif
583}
584
585
586
587
588
589
590
591
592
593static inline uint64_t uadd64_carry(uint64_t x, uint64_t y, bool *pcarry)
594{
595#if __has_builtin(__builtin_addcll)
596 unsigned long long c = *pcarry;
597 x = __builtin_addcll(x, y, c, &c);
598 *pcarry = c & 1;
599 return x;
600#else
601 bool c = *pcarry;
602
603 c = uadd64_overflow(x, c, &x);
604 c |= uadd64_overflow(x, y, &x);
605 *pcarry = c;
606 return x;
607#endif
608}
609
610
611
612
613
614
615
616
617
618static inline uint64_t usub64_borrow(uint64_t x, uint64_t y, bool *pborrow)
619{
620#if __has_builtin(__builtin_subcll)
621 unsigned long long b = *pborrow;
622 x = __builtin_subcll(x, y, b, &b);
623 *pborrow = b & 1;
624 return x;
625#else
626 bool b = *pborrow;
627 b = usub64_overflow(x, b, &x);
628 b |= usub64_overflow(x, y, &x);
629 *pborrow = b;
630 return x;
631#endif
632}
633
634
635
636#if ULONG_MAX == UINT32_MAX
637# define clzl clz32
638# define ctzl ctz32
639# define clol clo32
640# define ctol cto32
641# define ctpopl ctpop32
642# define revbitl revbit32
643#elif ULONG_MAX == UINT64_MAX
644# define clzl clz64
645# define ctzl ctz64
646# define clol clo64
647# define ctol cto64
648# define ctpopl ctpop64
649# define revbitl revbit64
650#else
651# error Unknown sizeof long
652#endif
653
654static inline bool is_power_of_2(uint64_t value)
655{
656 if (!value) {
657 return false;
658 }
659
660 return !(value & (value - 1));
661}
662
663
664
665
666static inline uint64_t pow2floor(uint64_t value)
667{
668 if (!value) {
669
670 return 0;
671 }
672 return 0x8000000000000000ull >> clz64(value);
673}
674
675
676
677
678
679static inline uint64_t pow2ceil(uint64_t value)
680{
681 int n = clz64(value - 1);
682
683 if (!n) {
684
685
686
687
688
689 return !value;
690 }
691 return 0x8000000000000000ull >> (n - 1);
692}
693
694static inline uint32_t pow2roundup32(uint32_t x)
695{
696 x |= (x >> 1);
697 x |= (x >> 2);
698 x |= (x >> 4);
699 x |= (x >> 8);
700 x |= (x >> 16);
701 return x + 1;
702}
703
704
705
706
707
708
709
710
711
712
713
714
715void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift);
716
717
718
719
720
721
722
723
724
725
726
727
728
729void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow);
730
731#endif
732