Reviewed-by: Lucas Mateus Castro <lucas.araujo@eldorado.org.br>From: Marc-André Lureau <marcandre.lureau@redhat.com> Break a cyclic dependency between int128 and host-utils.
Signed-off-by: Marc-André Lureau <marcandre.lureau@redhat.com> --- include/qemu/host-utils.h | 3 - include/qemu/int128.h | 3 + util/host-utils.c | 180 -------------------------------------- util/int128.c | 180 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 183 insertions(+), 183 deletions(-) diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h index 29f3a9987880..fa228a4a86e2 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -32,7 +32,6 @@ #include "qemu/compiler.h" #include "qemu/bswap.h" -#include "qemu/int128.h" #ifdef CONFIG_INT128 static inline void mulu64(uint64_t *plow, uint64_t *phigh, @@ -785,6 +784,4 @@ static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t n1, #endif } -Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor); -Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor); #endif diff --git a/include/qemu/int128.h b/include/qemu/int128.h index d2b76ca6acdc..823c61edb0fd 100644 --- a/include/qemu/int128.h +++ b/include/qemu/int128.h @@ -472,4 +472,7 @@ static inline void bswap128s(Int128 *s) #define INT128_MAX int128_make128(UINT64_MAX, INT64_MAX) #define INT128_MIN int128_make128(0, INT64_MIN) +Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor); +Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor); + #endif /* INT128_H */ diff --git a/util/host-utils.c b/util/host-utils.c index fb91bcba823d..96d5dc0bed25 100644 --- a/util/host-utils.c +++ b/util/host-utils.c @@ -266,183 +266,3 @@ void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow) *plow = *plow << shift; } } - -/* - * Unsigned 256-by-128 division. - * Returns the remainder via r. - * Returns lower 128 bit of quotient. - * Needs a normalized divisor (most significant bit set to 1). - * - * Adapted from include/qemu/host-utils.h udiv_qrnnd, - * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd - * (https://gmplib.org/repo/gmp/file/tip/longlong.h) - * - * Licensed under the GPLv2/LGPLv3 - */ -static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d) -{ - Int128 d0, d1, q0, q1, r1, r0, m; - uint64_t mp0, mp1; - - d0 = int128_make64(int128_getlo(d)); - d1 = int128_make64(int128_gethi(d)); - - r1 = int128_remu(n1, d1); - q1 = int128_divu(n1, d1); - mp0 = int128_getlo(q1); - mp1 = int128_gethi(q1); - mulu128(&mp0, &mp1, int128_getlo(d0)); - m = int128_make128(mp0, mp1); - r1 = int128_make128(int128_gethi(n0), int128_getlo(r1)); - if (int128_ult(r1, m)) { - q1 = int128_sub(q1, int128_one()); - r1 = int128_add(r1, d); - if (int128_uge(r1, d)) { - if (int128_ult(r1, m)) { - q1 = int128_sub(q1, int128_one()); - r1 = int128_add(r1, d); - } - } - } - r1 = int128_sub(r1, m); - - r0 = int128_remu(r1, d1); - q0 = int128_divu(r1, d1); - mp0 = int128_getlo(q0); - mp1 = int128_gethi(q0); - mulu128(&mp0, &mp1, int128_getlo(d0)); - m = int128_make128(mp0, mp1); - r0 = int128_make128(int128_getlo(n0), int128_getlo(r0)); - if (int128_ult(r0, m)) { - q0 = int128_sub(q0, int128_one()); - r0 = int128_add(r0, d); - if (int128_uge(r0, d)) { - if (int128_ult(r0, m)) { - q0 = int128_sub(q0, int128_one()); - r0 = int128_add(r0, d); - } - } - } - r0 = int128_sub(r0, m); - - *r = r0; - return int128_or(int128_lshift(q1, 64), q0); -} - -/* - * Unsigned 256-by-128 division. - * Returns the remainder. - * Returns quotient via plow and phigh. - * Also returns the remainder via the function return value. - */ -Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor) -{ - Int128 dhi = *phigh; - Int128 dlo = *plow; - Int128 rem, dhighest; - int sh; - - if (!int128_nz(divisor) || !int128_nz(dhi)) { - *plow = int128_divu(dlo, divisor); - *phigh = int128_zero(); - return int128_remu(dlo, divisor); - } else { - sh = clz128(divisor); - - if (int128_ult(dhi, divisor)) { - if (sh != 0) { - /* normalize the divisor, shifting the dividend accordingly */ - divisor = int128_lshift(divisor, sh); - dhi = int128_or(int128_lshift(dhi, sh), - int128_urshift(dlo, (128 - sh))); - dlo = int128_lshift(dlo, sh); - } - - *phigh = int128_zero(); - *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); - } else { - if (sh != 0) { - /* normalize the divisor, shifting the dividend accordingly */ - divisor = int128_lshift(divisor, sh); - dhighest = int128_rshift(dhi, (128 - sh)); - dhi = int128_or(int128_lshift(dhi, sh), - int128_urshift(dlo, (128 - sh))); - dlo = int128_lshift(dlo, sh); - - *phigh = udiv256_qrnnd(&dhi, dhighest, dhi, divisor); - } else { - /* - * dhi >= divisor - * Since the MSB of divisor is set (sh == 0), - * (dhi - divisor) < divisor - * - * Thus, the high part of the quotient is 1, and we can - * calculate the low part with a single call to udiv_qrnnd - * after subtracting divisor from dhi - */ - dhi = int128_sub(dhi, divisor); - *phigh = int128_one(); - } - - *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); - } - - /* - * since the dividend/divisor might have been normalized, - * the remainder might also have to be shifted back - */ - rem = int128_urshift(rem, sh); - return rem; - } -} - -/* - * Signed 256-by-128 division. - * Returns quotient via plow and phigh. - * Also returns the remainder via the function return value. - */ -Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor) -{ - bool neg_quotient = false, neg_remainder = false; - Int128 unsig_hi = *phigh, unsig_lo = *plow; - Int128 rem; - - if (!int128_nonneg(*phigh)) { - neg_quotient = !neg_quotient; - neg_remainder = !neg_remainder; - - if (!int128_nz(unsig_lo)) { - unsig_hi = int128_neg(unsig_hi); - } else { - unsig_hi = int128_not(unsig_hi); - unsig_lo = int128_neg(unsig_lo); - } - } - - if (!int128_nonneg(divisor)) { - neg_quotient = !neg_quotient; - - divisor = int128_neg(divisor); - } - - rem = divu256(&unsig_lo, &unsig_hi, divisor); - - if (neg_quotient) { - if (!int128_nz(unsig_lo)) { - *phigh = int128_neg(unsig_hi); - *plow = int128_zero(); - } else { - *phigh = int128_not(unsig_hi); - *plow = int128_neg(unsig_lo); - } - } else { - *phigh = unsig_hi; - *plow = unsig_lo; - } - - if (neg_remainder) { - return int128_neg(rem); - } else { - return rem; - } -} diff --git a/util/int128.c b/util/int128.c index ed8f25fef161..482c63b6551e 100644 --- a/util/int128.c +++ b/util/int128.c @@ -145,3 +145,183 @@ Int128 int128_rems(Int128 a, Int128 b) } #endif + +/* + * Unsigned 256-by-128 division. + * Returns the remainder via r. + * Returns lower 128 bit of quotient. + * Needs a normalized divisor (most significant bit set to 1). + * + * Adapted from include/qemu/host-utils.h udiv_qrnnd, + * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd + * (https://gmplib.org/repo/gmp/file/tip/longlong.h) + * + * Licensed under the GPLv2/LGPLv3 + */ +static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d) +{ + Int128 d0, d1, q0, q1, r1, r0, m; + uint64_t mp0, mp1; + + d0 = int128_make64(int128_getlo(d)); + d1 = int128_make64(int128_gethi(d)); + + r1 = int128_remu(n1, d1); + q1 = int128_divu(n1, d1); + mp0 = int128_getlo(q1); + mp1 = int128_gethi(q1); + mulu128(&mp0, &mp1, int128_getlo(d0)); + m = int128_make128(mp0, mp1); + r1 = int128_make128(int128_gethi(n0), int128_getlo(r1)); + if (int128_ult(r1, m)) { + q1 = int128_sub(q1, int128_one()); + r1 = int128_add(r1, d); + if (int128_uge(r1, d)) { + if (int128_ult(r1, m)) { + q1 = int128_sub(q1, int128_one()); + r1 = int128_add(r1, d); + } + } + } + r1 = int128_sub(r1, m); + + r0 = int128_remu(r1, d1); + q0 = int128_divu(r1, d1); + mp0 = int128_getlo(q0); + mp1 = int128_gethi(q0); + mulu128(&mp0, &mp1, int128_getlo(d0)); + m = int128_make128(mp0, mp1); + r0 = int128_make128(int128_getlo(n0), int128_getlo(r0)); + if (int128_ult(r0, m)) { + q0 = int128_sub(q0, int128_one()); + r0 = int128_add(r0, d); + if (int128_uge(r0, d)) { + if (int128_ult(r0, m)) { + q0 = int128_sub(q0, int128_one()); + r0 = int128_add(r0, d); + } + } + } + r0 = int128_sub(r0, m); + + *r = r0; + return int128_or(int128_lshift(q1, 64), q0); +} + +/* + * Unsigned 256-by-128 division. + * Returns the remainder. + * Returns quotient via plow and phigh. + * Also returns the remainder via the function return value. + */ +Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor) +{ + Int128 dhi = *phigh; + Int128 dlo = *plow; + Int128 rem, dhighest; + int sh; + + if (!int128_nz(divisor) || !int128_nz(dhi)) { + *plow = int128_divu(dlo, divisor); + *phigh = int128_zero(); + return int128_remu(dlo, divisor); + } else { + sh = clz128(divisor); + + if (int128_ult(dhi, divisor)) { + if (sh != 0) { + /* normalize the divisor, shifting the dividend accordingly */ + divisor = int128_lshift(divisor, sh); + dhi = int128_or(int128_lshift(dhi, sh), + int128_urshift(dlo, (128 - sh))); + dlo = int128_lshift(dlo, sh); + } + + *phigh = int128_zero(); + *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); + } else { + if (sh != 0) { + /* normalize the divisor, shifting the dividend accordingly */ + divisor = int128_lshift(divisor, sh); + dhighest = int128_rshift(dhi, (128 - sh)); + dhi = int128_or(int128_lshift(dhi, sh), + int128_urshift(dlo, (128 - sh))); + dlo = int128_lshift(dlo, sh); + + *phigh = udiv256_qrnnd(&dhi, dhighest, dhi, divisor); + } else { + /* + * dhi >= divisor + * Since the MSB of divisor is set (sh == 0), + * (dhi - divisor) < divisor + * + * Thus, the high part of the quotient is 1, and we can + * calculate the low part with a single call to udiv_qrnnd + * after subtracting divisor from dhi + */ + dhi = int128_sub(dhi, divisor); + *phigh = int128_one(); + } + + *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); + } + + /* + * since the dividend/divisor might have been normalized, + * the remainder might also have to be shifted back + */ + rem = int128_urshift(rem, sh); + return rem; + } +} + +/* + * Signed 256-by-128 division. + * Returns quotient via plow and phigh. + * Also returns the remainder via the function return value. + */ +Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor) +{ + bool neg_quotient = false, neg_remainder = false; + Int128 unsig_hi = *phigh, unsig_lo = *plow; + Int128 rem; + + if (!int128_nonneg(*phigh)) { + neg_quotient = !neg_quotient; + neg_remainder = !neg_remainder; + + if (!int128_nz(unsig_lo)) { + unsig_hi = int128_neg(unsig_hi); + } else { + unsig_hi = int128_not(unsig_hi); + unsig_lo = int128_neg(unsig_lo); + } + } + + if (!int128_nonneg(divisor)) { + neg_quotient = !neg_quotient; + + divisor = int128_neg(divisor); + } + + rem = divu256(&unsig_lo, &unsig_hi, divisor); + + if (neg_quotient) { + if (!int128_nz(unsig_lo)) { + *phigh = int128_neg(unsig_hi); + *plow = int128_zero(); + } else { + *phigh = int128_not(unsig_hi); + *plow = int128_neg(unsig_lo); + } + } else { + *phigh = unsig_hi; + *plow = unsig_lo; + } + + if (neg_remainder) { + return int128_neg(rem); + } else { + return rem; + } +} -- 2.37.0.rc0