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
27
28
29
30#ifndef HOST_UTILS_H
31#define HOST_UTILS_H
32
33#include "qemu/compiler.h"
34#include "qemu/bswap.h"
35
36#ifdef CONFIG_INT128
37static inline void mulu64(uint64_t *plow, uint64_t *phigh,
38 uint64_t a, uint64_t b)
39{
40 __uint128_t r = (__uint128_t)a * b;
41 *plow = r;
42 *phigh = r >> 64;
43}
44
45static inline void muls64(uint64_t *plow, uint64_t *phigh,
46 int64_t a, int64_t b)
47{
48 __int128_t r = (__int128_t)a * b;
49 *plow = r;
50 *phigh = r >> 64;
51}
52
53
54static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
55{
56 return (__int128_t)a * b / c;
57}
58
59static inline uint64_t divu128(uint64_t *plow, uint64_t *phigh,
60 uint64_t divisor)
61{
62 __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
63 __uint128_t result = dividend / divisor;
64
65 *plow = result;
66 *phigh = result >> 64;
67 return dividend % divisor;
68}
69
70static inline int64_t divs128(uint64_t *plow, int64_t *phigh,
71 int64_t divisor)
72{
73 __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
74 __int128_t result = dividend / divisor;
75
76 *plow = result;
77 *phigh = result >> 64;
78 return dividend % divisor;
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);
83uint64_t divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
84int64_t divs128(uint64_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
363static inline uint64_t uabs64(int64_t v)
364{
365 return v < 0 ? -v : v;
366}
367
368
369
370
371
372
373
374
375
376static inline bool sadd32_overflow(int32_t x, int32_t y, int32_t *ret)
377{
378#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
379 return __builtin_add_overflow(x, y, ret);
380#else
381 *ret = x + y;
382 return ((*ret ^ x) & ~(x ^ y)) < 0;
383#endif
384}
385
386
387
388
389
390
391
392
393
394static inline bool sadd64_overflow(int64_t x, int64_t y, int64_t *ret)
395{
396#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
397 return __builtin_add_overflow(x, y, ret);
398#else
399 *ret = x + y;
400 return ((*ret ^ x) & ~(x ^ y)) < 0;
401#endif
402}
403
404
405
406
407
408
409
410
411
412static inline bool uadd32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
413{
414#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
415 return __builtin_add_overflow(x, y, ret);
416#else
417 *ret = x + y;
418 return *ret < x;
419#endif
420}
421
422
423
424
425
426
427
428
429
430static inline bool uadd64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
431{
432#if __has_builtin(__builtin_add_overflow) || __GNUC__ >= 5
433 return __builtin_add_overflow(x, y, ret);
434#else
435 *ret = x + y;
436 return *ret < x;
437#endif
438}
439
440
441
442
443
444
445
446
447
448
449static inline bool ssub32_overflow(int32_t x, int32_t y, int32_t *ret)
450{
451#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
452 return __builtin_sub_overflow(x, y, ret);
453#else
454 *ret = x - y;
455 return ((*ret ^ x) & (x ^ y)) < 0;
456#endif
457}
458
459
460
461
462
463
464
465
466
467
468static inline bool ssub64_overflow(int64_t x, int64_t y, int64_t *ret)
469{
470#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
471 return __builtin_sub_overflow(x, y, ret);
472#else
473 *ret = x - y;
474 return ((*ret ^ x) & (x ^ y)) < 0;
475#endif
476}
477
478
479
480
481
482
483
484
485
486
487static inline bool usub32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
488{
489#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
490 return __builtin_sub_overflow(x, y, ret);
491#else
492 *ret = x - y;
493 return x < y;
494#endif
495}
496
497
498
499
500
501
502
503
504
505
506static inline bool usub64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
507{
508#if __has_builtin(__builtin_sub_overflow) || __GNUC__ >= 5
509 return __builtin_sub_overflow(x, y, ret);
510#else
511 *ret = x - y;
512 return x < y;
513#endif
514}
515
516
517
518
519
520
521
522
523
524static inline bool smul32_overflow(int32_t x, int32_t y, int32_t *ret)
525{
526#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
527 return __builtin_mul_overflow(x, y, ret);
528#else
529 int64_t z = (int64_t)x * y;
530 *ret = z;
531 return *ret != z;
532#endif
533}
534
535
536
537
538
539
540
541
542
543static inline bool smul64_overflow(int64_t x, int64_t y, int64_t *ret)
544{
545#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
546 return __builtin_mul_overflow(x, y, ret);
547#else
548 uint64_t hi, lo;
549 muls64(&lo, &hi, x, y);
550 *ret = lo;
551 return hi != ((int64_t)lo >> 63);
552#endif
553}
554
555
556
557
558
559
560
561
562
563static inline bool umul32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
564{
565#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
566 return __builtin_mul_overflow(x, y, ret);
567#else
568 uint64_t z = (uint64_t)x * y;
569 *ret = z;
570 return z > UINT32_MAX;
571#endif
572}
573
574
575
576
577
578
579
580
581
582static inline bool umul64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
583{
584#if __has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5
585 return __builtin_mul_overflow(x, y, ret);
586#else
587 uint64_t hi;
588 mulu64(ret, &hi, x, y);
589 return hi != 0;
590#endif
591}
592
593
594
595
596
597
598static inline bool mulu128(uint64_t *plow, uint64_t *phigh, uint64_t factor)
599{
600#if defined(CONFIG_INT128) && \
601 (__has_builtin(__builtin_mul_overflow) || __GNUC__ >= 5)
602 bool res;
603 __uint128_t r;
604 __uint128_t f = ((__uint128_t)*phigh << 64) | *plow;
605 res = __builtin_mul_overflow(f, factor, &r);
606
607 *plow = r;
608 *phigh = r >> 64;
609
610 return res;
611#else
612 uint64_t dhi = *phigh;
613 uint64_t dlo = *plow;
614 uint64_t ahi;
615 uint64_t blo, bhi;
616
617 if (dhi == 0) {
618 mulu64(plow, phigh, dlo, factor);
619 return false;
620 }
621
622 mulu64(plow, &ahi, dlo, factor);
623 mulu64(&blo, &bhi, dhi, factor);
624
625 return uadd64_overflow(ahi, blo, phigh) || bhi != 0;
626#endif
627}
628
629
630
631
632
633
634
635
636
637static inline uint64_t uadd64_carry(uint64_t x, uint64_t y, bool *pcarry)
638{
639#if __has_builtin(__builtin_addcll)
640 unsigned long long c = *pcarry;
641 x = __builtin_addcll(x, y, c, &c);
642 *pcarry = c & 1;
643 return x;
644#else
645 bool c = *pcarry;
646
647 c = uadd64_overflow(x, c, &x);
648 c |= uadd64_overflow(x, y, &x);
649 *pcarry = c;
650 return x;
651#endif
652}
653
654
655
656
657
658
659
660
661
662static inline uint64_t usub64_borrow(uint64_t x, uint64_t y, bool *pborrow)
663{
664#if __has_builtin(__builtin_subcll)
665 unsigned long long b = *pborrow;
666 x = __builtin_subcll(x, y, b, &b);
667 *pborrow = b & 1;
668 return x;
669#else
670 bool b = *pborrow;
671 b = usub64_overflow(x, b, &x);
672 b |= usub64_overflow(x, y, &x);
673 *pborrow = b;
674 return x;
675#endif
676}
677
678
679
680#if ULONG_MAX == UINT32_MAX
681# define clzl clz32
682# define ctzl ctz32
683# define clol clo32
684# define ctol cto32
685# define ctpopl ctpop32
686# define revbitl revbit32
687#elif ULONG_MAX == UINT64_MAX
688# define clzl clz64
689# define ctzl ctz64
690# define clol clo64
691# define ctol cto64
692# define ctpopl ctpop64
693# define revbitl revbit64
694#else
695# error Unknown sizeof long
696#endif
697
698static inline bool is_power_of_2(uint64_t value)
699{
700 if (!value) {
701 return false;
702 }
703
704 return !(value & (value - 1));
705}
706
707
708
709
710static inline uint64_t pow2floor(uint64_t value)
711{
712 if (!value) {
713
714 return 0;
715 }
716 return 0x8000000000000000ull >> clz64(value);
717}
718
719
720
721
722
723static inline uint64_t pow2ceil(uint64_t value)
724{
725 int n = clz64(value - 1);
726
727 if (!n) {
728
729
730
731
732
733 return !value;
734 }
735 return 0x8000000000000000ull >> (n - 1);
736}
737
738static inline uint32_t pow2roundup32(uint32_t x)
739{
740 x |= (x >> 1);
741 x |= (x >> 2);
742 x |= (x >> 4);
743 x |= (x >> 8);
744 x |= (x >> 16);
745 return x + 1;
746}
747
748
749
750
751
752
753
754
755
756
757
758
759void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift);
760
761
762
763
764
765
766
767
768
769
770
771
772
773void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow);
774
775
776
777
778
779
780static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t n1,
781 uint64_t n0, uint64_t d)
782{
783#if defined(__x86_64__)
784 uint64_t q;
785 asm("divq %4" : "=a"(q), "=d"(*r) : "0"(n0), "1"(n1), "rm"(d));
786 return q;
787#elif defined(__s390x__) && !defined(__clang__)
788
789 unsigned __int128 n = (unsigned __int128)n1 << 64 | n0;
790 asm("dlgr %0, %1" : "+r"(n) : "r"(d));
791 *r = n >> 64;
792 return n;
793#elif defined(_ARCH_PPC64) && defined(_ARCH_PWR7)
794
795 uint64_t q1, q2, Q, r1, r2, R;
796 asm("divdeu %0,%2,%4; divdu %1,%3,%4"
797 : "=&r"(q1), "=r"(q2)
798 : "r"(n1), "r"(n0), "r"(d));
799 r1 = -(q1 * d);
800 r2 = n0 - (q2 * d);
801 Q = q1 + q2;
802 R = r1 + r2;
803 if (R >= d || R < r2) {
804 Q += 1;
805 R -= d;
806 }
807 *r = R;
808 return Q;
809#else
810 uint64_t d0, d1, q0, q1, r1, r0, m;
811
812 d0 = (uint32_t)d;
813 d1 = d >> 32;
814
815 r1 = n1 % d1;
816 q1 = n1 / d1;
817 m = q1 * d0;
818 r1 = (r1 << 32) | (n0 >> 32);
819 if (r1 < m) {
820 q1 -= 1;
821 r1 += d;
822 if (r1 >= d) {
823 if (r1 < m) {
824 q1 -= 1;
825 r1 += d;
826 }
827 }
828 }
829 r1 -= m;
830
831 r0 = r1 % d1;
832 q0 = r1 / d1;
833 m = q0 * d0;
834 r0 = (r0 << 32) | (uint32_t)n0;
835 if (r0 < m) {
836 q0 -= 1;
837 r0 += d;
838 if (r0 >= d) {
839 if (r0 < m) {
840 q0 -= 1;
841 r0 += d;
842 }
843 }
844 }
845 r0 -= m;
846
847 *r = r0;
848 return (q1 << 32) | q0;
849#endif
850}
851
852#endif
853