Hi
On Tue, Jul 12, 2022 at 1:49 PM <marcandre.lur...@redhat.com> wrote: > From: Marc-André Lureau <marcandre.lur...@redhat.com> > > Break a cyclic dependency between int128 and host-utils. > Anyone to approve that change? (This will allow us to more easily move host-utils & int128 units to a subproject) thanks > > Signed-off-by: Marc-André Lureau <marcandre.lur...@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 > > > -- Marc-André Lureau
