xref: /openbmc/qemu/include/qemu/host-utils.h (revision 47de6c4c)
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 
26 /* Portions of this work are licensed under the terms of the GNU GPL,
27  * version 2 or later. See the COPYING file in the top-level directory.
28  */
29 
30 #ifndef HOST_UTILS_H
31 #define HOST_UTILS_H
32 
33 #include "qemu/bswap.h"
34 #include "qemu/int128.h"
35 
36 #ifdef CONFIG_INT128
mulu64(uint64_t * plow,uint64_t * phigh,uint64_t a,uint64_t b)37 static 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 
muls64(uint64_t * plow,uint64_t * phigh,int64_t a,int64_t b)45 static 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 /* compute with 96 bit intermediate result: (a*b)/c */
muldiv64(uint64_t a,uint32_t b,uint32_t c)54 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
55 {
56     return (__int128_t)a * b / c;
57 }
58 
muldiv64_round_up(uint64_t a,uint32_t b,uint32_t c)59 static inline uint64_t muldiv64_round_up(uint64_t a, uint32_t b, uint32_t c)
60 {
61     return ((__int128_t)a * b + c - 1) / c;
62 }
63 
divu128(uint64_t * plow,uint64_t * phigh,uint64_t divisor)64 static inline uint64_t divu128(uint64_t *plow, uint64_t *phigh,
65                                uint64_t divisor)
66 {
67     __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
68     __uint128_t result = dividend / divisor;
69 
70     *plow = result;
71     *phigh = result >> 64;
72     return dividend % divisor;
73 }
74 
divs128(uint64_t * plow,int64_t * phigh,int64_t divisor)75 static inline int64_t divs128(uint64_t *plow, int64_t *phigh,
76                               int64_t divisor)
77 {
78     __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
79     __int128_t result = dividend / divisor;
80 
81     *plow = result;
82     *phigh = result >> 64;
83     return dividend % divisor;
84 }
85 #else
86 void muls64(uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b);
87 void mulu64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b);
88 uint64_t divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
89 int64_t divs128(uint64_t *plow, int64_t *phigh, int64_t divisor);
90 
muldiv64_rounding(uint64_t a,uint32_t b,uint32_t c,bool round_up)91 static inline uint64_t muldiv64_rounding(uint64_t a, uint32_t b, uint32_t c,
92                                   bool round_up)
93 {
94     union {
95         uint64_t ll;
96         struct {
97 #if HOST_BIG_ENDIAN
98             uint32_t high, low;
99 #else
100             uint32_t low, high;
101 #endif
102         } l;
103     } u, res;
104     uint64_t rl, rh;
105 
106     u.ll = a;
107     rl = (uint64_t)u.l.low * (uint64_t)b;
108     if (round_up) {
109         rl += c - 1;
110     }
111     rh = (uint64_t)u.l.high * (uint64_t)b;
112     rh += (rl >> 32);
113     res.l.high = rh / c;
114     res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c;
115     return res.ll;
116 }
117 
muldiv64(uint64_t a,uint32_t b,uint32_t c)118 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
119 {
120     return muldiv64_rounding(a, b, c, false);
121 }
122 
muldiv64_round_up(uint64_t a,uint32_t b,uint32_t c)123 static inline uint64_t muldiv64_round_up(uint64_t a, uint32_t b, uint32_t c)
124 {
125     return muldiv64_rounding(a, b, c, true);
126 }
127 #endif
128 
129 /**
130  * clz8 - count leading zeros in a 8-bit value.
131  * @val: The value to search
132  *
133  * Returns 8 if the value is zero.  Note that the GCC builtin is
134  * undefined if the value is zero.
135  *
136  * Note that the GCC builtin will upcast its argument to an `unsigned int`
137  * so this function subtracts off the number of prepended zeroes.
138  */
clz8(uint8_t val)139 static inline int clz8(uint8_t val)
140 {
141     return val ? __builtin_clz(val) - 24 : 8;
142 }
143 
144 /**
145  * clz16 - count leading zeros in a 16-bit value.
146  * @val: The value to search
147  *
148  * Returns 16 if the value is zero.  Note that the GCC builtin is
149  * undefined if the value is zero.
150  *
151  * Note that the GCC builtin will upcast its argument to an `unsigned int`
152  * so this function subtracts off the number of prepended zeroes.
153  */
clz16(uint16_t val)154 static inline int clz16(uint16_t val)
155 {
156     return val ? __builtin_clz(val) - 16 : 16;
157 }
158 
159 /**
160  * clz32 - count leading zeros in a 32-bit value.
161  * @val: The value to search
162  *
163  * Returns 32 if the value is zero.  Note that the GCC builtin is
164  * undefined if the value is zero.
165  */
clz32(uint32_t val)166 static inline int clz32(uint32_t val)
167 {
168     return val ? __builtin_clz(val) : 32;
169 }
170 
171 /**
172  * clo32 - count leading ones in a 32-bit value.
173  * @val: The value to search
174  *
175  * Returns 32 if the value is -1.
176  */
clo32(uint32_t val)177 static inline int clo32(uint32_t val)
178 {
179     return clz32(~val);
180 }
181 
182 /**
183  * clz64 - count leading zeros in a 64-bit value.
184  * @val: The value to search
185  *
186  * Returns 64 if the value is zero.  Note that the GCC builtin is
187  * undefined if the value is zero.
188  */
clz64(uint64_t val)189 static inline int clz64(uint64_t val)
190 {
191     return val ? __builtin_clzll(val) : 64;
192 }
193 
194 /**
195  * clo64 - count leading ones in a 64-bit value.
196  * @val: The value to search
197  *
198  * Returns 64 if the value is -1.
199  */
clo64(uint64_t val)200 static inline int clo64(uint64_t val)
201 {
202     return clz64(~val);
203 }
204 
205 /**
206  * ctz8 - count trailing zeros in a 8-bit value.
207  * @val: The value to search
208  *
209  * Returns 8 if the value is zero.  Note that the GCC builtin is
210  * undefined if the value is zero.
211  */
ctz8(uint8_t val)212 static inline int ctz8(uint8_t val)
213 {
214     return val ? __builtin_ctz(val) : 8;
215 }
216 
217 /**
218  * ctz16 - count trailing zeros in a 16-bit value.
219  * @val: The value to search
220  *
221  * Returns 16 if the value is zero.  Note that the GCC builtin is
222  * undefined if the value is zero.
223  */
ctz16(uint16_t val)224 static inline int ctz16(uint16_t val)
225 {
226     return val ? __builtin_ctz(val) : 16;
227 }
228 
229 /**
230  * ctz32 - count trailing zeros in a 32-bit value.
231  * @val: The value to search
232  *
233  * Returns 32 if the value is zero.  Note that the GCC builtin is
234  * undefined if the value is zero.
235  */
ctz32(uint32_t val)236 static inline int ctz32(uint32_t val)
237 {
238     return val ? __builtin_ctz(val) : 32;
239 }
240 
241 /**
242  * cto32 - count trailing ones in a 32-bit value.
243  * @val: The value to search
244  *
245  * Returns 32 if the value is -1.
246  */
cto32(uint32_t val)247 static inline int cto32(uint32_t val)
248 {
249     return ctz32(~val);
250 }
251 
252 /**
253  * ctz64 - count trailing zeros in a 64-bit value.
254  * @val: The value to search
255  *
256  * Returns 64 if the value is zero.  Note that the GCC builtin is
257  * undefined if the value is zero.
258  */
ctz64(uint64_t val)259 static inline int ctz64(uint64_t val)
260 {
261     return val ? __builtin_ctzll(val) : 64;
262 }
263 
264 /**
265  * cto64 - count trailing ones in a 64-bit value.
266  * @val: The value to search
267  *
268  * Returns 64 if the value is -1.
269  */
cto64(uint64_t val)270 static inline int cto64(uint64_t val)
271 {
272     return ctz64(~val);
273 }
274 
275 /**
276  * clrsb32 - count leading redundant sign bits in a 32-bit value.
277  * @val: The value to search
278  *
279  * Returns the number of bits following the sign bit that are equal to it.
280  * No special cases; output range is [0-31].
281  */
clrsb32(uint32_t val)282 static inline int clrsb32(uint32_t val)
283 {
284 #if __has_builtin(__builtin_clrsb) || !defined(__clang__)
285     return __builtin_clrsb(val);
286 #else
287     return clz32(val ^ ((int32_t)val >> 1)) - 1;
288 #endif
289 }
290 
291 /**
292  * clrsb64 - count leading redundant sign bits in a 64-bit value.
293  * @val: The value to search
294  *
295  * Returns the number of bits following the sign bit that are equal to it.
296  * No special cases; output range is [0-63].
297  */
clrsb64(uint64_t val)298 static inline int clrsb64(uint64_t val)
299 {
300 #if __has_builtin(__builtin_clrsbll) || !defined(__clang__)
301     return __builtin_clrsbll(val);
302 #else
303     return clz64(val ^ ((int64_t)val >> 1)) - 1;
304 #endif
305 }
306 
307 /**
308  * ctpop8 - count the population of one bits in an 8-bit value.
309  * @val: The value to search
310  */
ctpop8(uint8_t val)311 static inline int ctpop8(uint8_t val)
312 {
313     return __builtin_popcount(val);
314 }
315 
316 /**
317  * ctpop16 - count the population of one bits in a 16-bit value.
318  * @val: The value to search
319  */
ctpop16(uint16_t val)320 static inline int ctpop16(uint16_t val)
321 {
322     return __builtin_popcount(val);
323 }
324 
325 /**
326  * ctpop32 - count the population of one bits in a 32-bit value.
327  * @val: The value to search
328  */
ctpop32(uint32_t val)329 static inline int ctpop32(uint32_t val)
330 {
331     return __builtin_popcount(val);
332 }
333 
334 /**
335  * ctpop64 - count the population of one bits in a 64-bit value.
336  * @val: The value to search
337  */
ctpop64(uint64_t val)338 static inline int ctpop64(uint64_t val)
339 {
340     return __builtin_popcountll(val);
341 }
342 
343 /**
344  * revbit8 - reverse the bits in an 8-bit value.
345  * @x: The value to modify.
346  */
revbit8(uint8_t x)347 static inline uint8_t revbit8(uint8_t x)
348 {
349 #if __has_builtin(__builtin_bitreverse8)
350     return __builtin_bitreverse8(x);
351 #else
352     /* Assign the correct nibble position.  */
353     x = ((x & 0xf0) >> 4)
354       | ((x & 0x0f) << 4);
355     /* Assign the correct bit position.  */
356     x = ((x & 0x88) >> 3)
357       | ((x & 0x44) >> 1)
358       | ((x & 0x22) << 1)
359       | ((x & 0x11) << 3);
360     return x;
361 #endif
362 }
363 
364 /**
365  * revbit16 - reverse the bits in a 16-bit value.
366  * @x: The value to modify.
367  */
revbit16(uint16_t x)368 static inline uint16_t revbit16(uint16_t x)
369 {
370 #if __has_builtin(__builtin_bitreverse16)
371     return __builtin_bitreverse16(x);
372 #else
373     /* Assign the correct byte position.  */
374     x = bswap16(x);
375     /* Assign the correct nibble position.  */
376     x = ((x & 0xf0f0) >> 4)
377       | ((x & 0x0f0f) << 4);
378     /* Assign the correct bit position.  */
379     x = ((x & 0x8888) >> 3)
380       | ((x & 0x4444) >> 1)
381       | ((x & 0x2222) << 1)
382       | ((x & 0x1111) << 3);
383     return x;
384 #endif
385 }
386 
387 /**
388  * revbit32 - reverse the bits in a 32-bit value.
389  * @x: The value to modify.
390  */
revbit32(uint32_t x)391 static inline uint32_t revbit32(uint32_t x)
392 {
393 #if __has_builtin(__builtin_bitreverse32)
394     return __builtin_bitreverse32(x);
395 #else
396     /* Assign the correct byte position.  */
397     x = bswap32(x);
398     /* Assign the correct nibble position.  */
399     x = ((x & 0xf0f0f0f0u) >> 4)
400       | ((x & 0x0f0f0f0fu) << 4);
401     /* Assign the correct bit position.  */
402     x = ((x & 0x88888888u) >> 3)
403       | ((x & 0x44444444u) >> 1)
404       | ((x & 0x22222222u) << 1)
405       | ((x & 0x11111111u) << 3);
406     return x;
407 #endif
408 }
409 
410 /**
411  * revbit64 - reverse the bits in a 64-bit value.
412  * @x: The value to modify.
413  */
revbit64(uint64_t x)414 static inline uint64_t revbit64(uint64_t x)
415 {
416 #if __has_builtin(__builtin_bitreverse64)
417     return __builtin_bitreverse64(x);
418 #else
419     /* Assign the correct byte position.  */
420     x = bswap64(x);
421     /* Assign the correct nibble position.  */
422     x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
423       | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
424     /* Assign the correct bit position.  */
425     x = ((x & 0x8888888888888888ull) >> 3)
426       | ((x & 0x4444444444444444ull) >> 1)
427       | ((x & 0x2222222222222222ull) << 1)
428       | ((x & 0x1111111111111111ull) << 3);
429     return x;
430 #endif
431 }
432 
433 /**
434  * Return the absolute value of a 64-bit integer as an unsigned 64-bit value
435  */
uabs64(int64_t v)436 static inline uint64_t uabs64(int64_t v)
437 {
438     return v < 0 ? -v : v;
439 }
440 
441 /**
442  * sadd32_overflow - addition with overflow indication
443  * @x, @y: addends
444  * @ret: Output for sum
445  *
446  * Computes *@ret = @x + @y, and returns true if and only if that
447  * value has been truncated.
448  */
sadd32_overflow(int32_t x,int32_t y,int32_t * ret)449 static inline bool sadd32_overflow(int32_t x, int32_t y, int32_t *ret)
450 {
451     return __builtin_add_overflow(x, y, ret);
452 }
453 
454 /**
455  * sadd64_overflow - addition with overflow indication
456  * @x, @y: addends
457  * @ret: Output for sum
458  *
459  * Computes *@ret = @x + @y, and returns true if and only if that
460  * value has been truncated.
461  */
sadd64_overflow(int64_t x,int64_t y,int64_t * ret)462 static inline bool sadd64_overflow(int64_t x, int64_t y, int64_t *ret)
463 {
464     return __builtin_add_overflow(x, y, ret);
465 }
466 
467 /**
468  * uadd32_overflow - addition with overflow indication
469  * @x, @y: addends
470  * @ret: Output for sum
471  *
472  * Computes *@ret = @x + @y, and returns true if and only if that
473  * value has been truncated.
474  */
uadd32_overflow(uint32_t x,uint32_t y,uint32_t * ret)475 static inline bool uadd32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
476 {
477     return __builtin_add_overflow(x, y, ret);
478 }
479 
480 /**
481  * uadd64_overflow - addition with overflow indication
482  * @x, @y: addends
483  * @ret: Output for sum
484  *
485  * Computes *@ret = @x + @y, and returns true if and only if that
486  * value has been truncated.
487  */
uadd64_overflow(uint64_t x,uint64_t y,uint64_t * ret)488 static inline bool uadd64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
489 {
490     return __builtin_add_overflow(x, y, ret);
491 }
492 
493 /**
494  * ssub32_overflow - subtraction with overflow indication
495  * @x: Minuend
496  * @y: Subtrahend
497  * @ret: Output for difference
498  *
499  * Computes *@ret = @x - @y, and returns true if and only if that
500  * value has been truncated.
501  */
ssub32_overflow(int32_t x,int32_t y,int32_t * ret)502 static inline bool ssub32_overflow(int32_t x, int32_t y, int32_t *ret)
503 {
504     return __builtin_sub_overflow(x, y, ret);
505 }
506 
507 /**
508  * ssub64_overflow - subtraction with overflow indication
509  * @x: Minuend
510  * @y: Subtrahend
511  * @ret: Output for sum
512  *
513  * Computes *@ret = @x - @y, and returns true if and only if that
514  * value has been truncated.
515  */
ssub64_overflow(int64_t x,int64_t y,int64_t * ret)516 static inline bool ssub64_overflow(int64_t x, int64_t y, int64_t *ret)
517 {
518     return __builtin_sub_overflow(x, y, ret);
519 }
520 
521 /**
522  * usub32_overflow - subtraction with overflow indication
523  * @x: Minuend
524  * @y: Subtrahend
525  * @ret: Output for sum
526  *
527  * Computes *@ret = @x - @y, and returns true if and only if that
528  * value has been truncated.
529  */
usub32_overflow(uint32_t x,uint32_t y,uint32_t * ret)530 static inline bool usub32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
531 {
532     return __builtin_sub_overflow(x, y, ret);
533 }
534 
535 /**
536  * usub64_overflow - subtraction with overflow indication
537  * @x: Minuend
538  * @y: Subtrahend
539  * @ret: Output for sum
540  *
541  * Computes *@ret = @x - @y, and returns true if and only if that
542  * value has been truncated.
543  */
usub64_overflow(uint64_t x,uint64_t y,uint64_t * ret)544 static inline bool usub64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
545 {
546     return __builtin_sub_overflow(x, y, ret);
547 }
548 
549 /**
550  * smul32_overflow - multiplication with overflow indication
551  * @x, @y: Input multipliers
552  * @ret: Output for product
553  *
554  * Computes *@ret = @x * @y, and returns true if and only if that
555  * value has been truncated.
556  */
smul32_overflow(int32_t x,int32_t y,int32_t * ret)557 static inline bool smul32_overflow(int32_t x, int32_t y, int32_t *ret)
558 {
559     return __builtin_mul_overflow(x, y, ret);
560 }
561 
562 /**
563  * smul64_overflow - multiplication with overflow indication
564  * @x, @y: Input multipliers
565  * @ret: Output for product
566  *
567  * Computes *@ret = @x * @y, and returns true if and only if that
568  * value has been truncated.
569  */
smul64_overflow(int64_t x,int64_t y,int64_t * ret)570 static inline bool smul64_overflow(int64_t x, int64_t y, int64_t *ret)
571 {
572     return __builtin_mul_overflow(x, y, ret);
573 }
574 
575 /**
576  * umul32_overflow - multiplication with overflow indication
577  * @x, @y: Input multipliers
578  * @ret: Output for product
579  *
580  * Computes *@ret = @x * @y, and returns true if and only if that
581  * value has been truncated.
582  */
umul32_overflow(uint32_t x,uint32_t y,uint32_t * ret)583 static inline bool umul32_overflow(uint32_t x, uint32_t y, uint32_t *ret)
584 {
585     return __builtin_mul_overflow(x, y, ret);
586 }
587 
588 /**
589  * umul64_overflow - multiplication with overflow indication
590  * @x, @y: Input multipliers
591  * @ret: Output for product
592  *
593  * Computes *@ret = @x * @y, and returns true if and only if that
594  * value has been truncated.
595  */
umul64_overflow(uint64_t x,uint64_t y,uint64_t * ret)596 static inline bool umul64_overflow(uint64_t x, uint64_t y, uint64_t *ret)
597 {
598     return __builtin_mul_overflow(x, y, ret);
599 }
600 
601 /*
602  * Unsigned 128x64 multiplication.
603  * Returns true if the result got truncated to 128 bits.
604  * Otherwise, returns false and the multiplication result via plow and phigh.
605  */
mulu128(uint64_t * plow,uint64_t * phigh,uint64_t factor)606 static inline bool mulu128(uint64_t *plow, uint64_t *phigh, uint64_t factor)
607 {
608 #if defined(CONFIG_INT128)
609     bool res;
610     __uint128_t r;
611     __uint128_t f = ((__uint128_t)*phigh << 64) | *plow;
612     res = __builtin_mul_overflow(f, factor, &r);
613 
614     *plow = r;
615     *phigh = r >> 64;
616 
617     return res;
618 #else
619     uint64_t dhi = *phigh;
620     uint64_t dlo = *plow;
621     uint64_t ahi;
622     uint64_t blo, bhi;
623 
624     if (dhi == 0) {
625         mulu64(plow, phigh, dlo, factor);
626         return false;
627     }
628 
629     mulu64(plow, &ahi, dlo, factor);
630     mulu64(&blo, &bhi, dhi, factor);
631 
632     return uadd64_overflow(ahi, blo, phigh) || bhi != 0;
633 #endif
634 }
635 
636 /**
637  * uadd64_carry - addition with carry-in and carry-out
638  * @x, @y: addends
639  * @pcarry: in-out carry value
640  *
641  * Computes @x + @y + *@pcarry, placing the carry-out back
642  * into *@pcarry and returning the 64-bit sum.
643  */
uadd64_carry(uint64_t x,uint64_t y,bool * pcarry)644 static inline uint64_t uadd64_carry(uint64_t x, uint64_t y, bool *pcarry)
645 {
646 #if __has_builtin(__builtin_addcll)
647     unsigned long long c = *pcarry;
648     x = __builtin_addcll(x, y, c, &c);
649     *pcarry = c & 1;
650     return x;
651 #else
652     bool c = *pcarry;
653     /* This is clang's internal expansion of __builtin_addc. */
654     c = uadd64_overflow(x, c, &x);
655     c |= uadd64_overflow(x, y, &x);
656     *pcarry = c;
657     return x;
658 #endif
659 }
660 
661 /**
662  * usub64_borrow - subtraction with borrow-in and borrow-out
663  * @x, @y: addends
664  * @pborrow: in-out borrow value
665  *
666  * Computes @x - @y - *@pborrow, placing the borrow-out back
667  * into *@pborrow and returning the 64-bit sum.
668  */
usub64_borrow(uint64_t x,uint64_t y,bool * pborrow)669 static inline uint64_t usub64_borrow(uint64_t x, uint64_t y, bool *pborrow)
670 {
671 #if __has_builtin(__builtin_subcll) && !defined(BUILTIN_SUBCLL_BROKEN)
672     unsigned long long b = *pborrow;
673     x = __builtin_subcll(x, y, b, &b);
674     *pborrow = b & 1;
675     return x;
676 #else
677     bool b = *pborrow;
678     b = usub64_overflow(x, b, &x);
679     b |= usub64_overflow(x, y, &x);
680     *pborrow = b;
681     return x;
682 #endif
683 }
684 
685 /* Host type specific sizes of these routines.  */
686 
687 #if ULONG_MAX == UINT32_MAX
688 # define clzl   clz32
689 # define ctzl   ctz32
690 # define clol   clo32
691 # define ctol   cto32
692 # define ctpopl ctpop32
693 # define revbitl revbit32
694 #elif ULONG_MAX == UINT64_MAX
695 # define clzl   clz64
696 # define ctzl   ctz64
697 # define clol   clo64
698 # define ctol   cto64
699 # define ctpopl ctpop64
700 # define revbitl revbit64
701 #else
702 # error Unknown sizeof long
703 #endif
704 
is_power_of_2(uint64_t value)705 static inline bool is_power_of_2(uint64_t value)
706 {
707     if (!value) {
708         return false;
709     }
710 
711     return !(value & (value - 1));
712 }
713 
714 /**
715  * Return @value rounded down to the nearest power of two or zero.
716  */
pow2floor(uint64_t value)717 static inline uint64_t pow2floor(uint64_t value)
718 {
719     if (!value) {
720         /* Avoid undefined shift by 64 */
721         return 0;
722     }
723     return 0x8000000000000000ull >> clz64(value);
724 }
725 
726 /*
727  * Return @value rounded up to the nearest power of two modulo 2^64.
728  * This is *zero* for @value > 2^63, so be careful.
729  */
pow2ceil(uint64_t value)730 static inline uint64_t pow2ceil(uint64_t value)
731 {
732     int n = clz64(value - 1);
733 
734     if (!n) {
735         /*
736          * @value - 1 has no leading zeroes, thus @value - 1 >= 2^63
737          * Therefore, either @value == 0 or @value > 2^63.
738          * If it's 0, return 1, else return 0.
739          */
740         return !value;
741     }
742     return 0x8000000000000000ull >> (n - 1);
743 }
744 
pow2roundup32(uint32_t x)745 static inline uint32_t pow2roundup32(uint32_t x)
746 {
747     x |= (x >> 1);
748     x |= (x >> 2);
749     x |= (x >> 4);
750     x |= (x >> 8);
751     x |= (x >> 16);
752     return x + 1;
753 }
754 
755 /**
756  * urshift - 128-bit Unsigned Right Shift.
757  * @plow: in/out - lower 64-bit integer.
758  * @phigh: in/out - higher 64-bit integer.
759  * @shift: in - bytes to shift, between 0 and 127.
760  *
761  * Result is zero-extended and stored in plow/phigh, which are
762  * input/output variables. Shift values outside the range will
763  * be mod to 128. In other words, the caller is responsible to
764  * verify/assert both the shift range and plow/phigh pointers.
765  */
766 void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift);
767 
768 /**
769  * ulshift - 128-bit Unsigned Left Shift.
770  * @plow: in/out - lower 64-bit integer.
771  * @phigh: in/out - higher 64-bit integer.
772  * @shift: in - bytes to shift, between 0 and 127.
773  * @overflow: out - true if any 1-bit is shifted out.
774  *
775  * Result is zero-extended and stored in plow/phigh, which are
776  * input/output variables. Shift values outside the range will
777  * be mod to 128. In other words, the caller is responsible to
778  * verify/assert both the shift range and plow/phigh pointers.
779  */
780 void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow);
781 
782 /* From the GNU Multi Precision Library - longlong.h __udiv_qrnnd
783  * (https://gmplib.org/repo/gmp/file/tip/longlong.h)
784  *
785  * Licensed under the GPLv2/LGPLv3
786  */
udiv_qrnnd(uint64_t * r,uint64_t n1,uint64_t n0,uint64_t d)787 static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t n1,
788                                   uint64_t n0, uint64_t d)
789 {
790 #if defined(__x86_64__)
791     uint64_t q;
792     asm("divq %4" : "=a"(q), "=d"(*r) : "0"(n0), "1"(n1), "rm"(d));
793     return q;
794 #elif defined(__s390x__) && !defined(__clang__)
795     /* Need to use a TImode type to get an even register pair for DLGR.  */
796     unsigned __int128 n = (unsigned __int128)n1 << 64 | n0;
797     asm("dlgr %0, %1" : "+r"(n) : "r"(d));
798     *r = n >> 64;
799     return n;
800 #elif defined(_ARCH_PPC64) && defined(_ARCH_PWR7)
801     /* From Power ISA 2.06, programming note for divdeu.  */
802     uint64_t q1, q2, Q, r1, r2, R;
803     asm("divdeu %0,%2,%4; divdu %1,%3,%4"
804         : "=&r"(q1), "=r"(q2)
805         : "r"(n1), "r"(n0), "r"(d));
806     r1 = -(q1 * d);         /* low part of (n1<<64) - (q1 * d) */
807     r2 = n0 - (q2 * d);
808     Q = q1 + q2;
809     R = r1 + r2;
810     if (R >= d || R < r2) { /* overflow implies R > d */
811         Q += 1;
812         R -= d;
813     }
814     *r = R;
815     return Q;
816 #else
817     uint64_t d0, d1, q0, q1, r1, r0, m;
818 
819     d0 = (uint32_t)d;
820     d1 = d >> 32;
821 
822     r1 = n1 % d1;
823     q1 = n1 / d1;
824     m = q1 * d0;
825     r1 = (r1 << 32) | (n0 >> 32);
826     if (r1 < m) {
827         q1 -= 1;
828         r1 += d;
829         if (r1 >= d) {
830             if (r1 < m) {
831                 q1 -= 1;
832                 r1 += d;
833             }
834         }
835     }
836     r1 -= m;
837 
838     r0 = r1 % d1;
839     q0 = r1 / d1;
840     m = q0 * d0;
841     r0 = (r0 << 32) | (uint32_t)n0;
842     if (r0 < m) {
843         q0 -= 1;
844         r0 += d;
845         if (r0 >= d) {
846             if (r0 < m) {
847                 q0 -= 1;
848                 r0 += d;
849             }
850         }
851     }
852     r0 -= m;
853 
854     *r = r0;
855     return (q1 << 32) | q0;
856 #endif
857 }
858 
859 Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor);
860 Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor);
861 #endif
862