From: "Marc-André Lureau" <marcandre.lureau@gmail.com>
To: qemu-devel@nongnu.org, lucas.araujo@eldorado.org.br,
Richard Henderson <richard.henderson@linaro.org>,
Daniel Henrique Barboza <danielhb413@gmail.com>
Subject: Re: [PATCH v2 09/15] util: move 256-by-128 division helpers to int128
Date: Thu, 4 Aug 2022 20:17:40 +0400 [thread overview]
Message-ID: <CAJ+F1C++5KSWioj9Tq=0phFkY1W7zpa-qyAmD1KsonRhA5Kycw@mail.gmail.com> (raw)
In-Reply-To: <20220712093528.4144184-10-marcandre.lureau@redhat.com>
[-- Attachment #1: Type: text/plain, Size: 14574 bytes --]
Hi
On Tue, Jul 12, 2022 at 1:49 PM <marcandre.lureau@redhat.com> wrote:
> From: Marc-André Lureau <marcandre.lureau@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.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
>
>
>
--
Marc-André Lureau
[-- Attachment #2: Type: text/html, Size: 17646 bytes --]
next prev parent reply other threads:[~2022-08-04 16:22 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-12 9:35 [PATCH v2 00/15] Preliminary patches for subproject split marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 01/15] error-report: misc comment fix marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 02/15] error-report: introduce "detailed" variable marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 03/15] error-report: simplify print_loc() marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 04/15] error-report: introduce overridable error_is_detailed() marcandre.lureau
2022-07-12 15:02 ` Warner Losh
2022-07-19 7:24 ` Markus Armbruster
2022-07-12 9:35 ` [PATCH v2 05/15] stubs: remove needless error_vprintf_unless_qmp() marcandre.lureau
2022-07-19 7:24 ` Markus Armbruster
2022-07-12 9:35 ` [PATCH v2 06/15] qapi: move QEMU-specific dispatch code in monitor marcandre.lureau
2022-08-02 10:58 ` Markus Armbruster
2022-08-02 11:19 ` Marc-André Lureau
2022-08-02 12:21 ` Markus Armbruster
2022-07-12 9:35 ` [PATCH v2 07/15] scripts/qapi-gen: add -i option marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 08/15] scripts/qapi: add required system includes to visitor marcandre.lureau
2022-07-12 15:08 ` Warner Losh
2022-07-12 9:35 ` [PATCH v2 09/15] util: move 256-by-128 division helpers to int128 marcandre.lureau
2022-08-04 16:17 ` Marc-André Lureau [this message]
2022-08-04 17:04 ` Lucas Mateus Martins Araujo e Castro
2022-07-12 9:35 ` [PATCH v2 10/15] qemu-common: introduce a common subproject marcandre.lureau
2022-07-12 14:57 ` Warner Losh
2022-07-15 11:55 ` Marc-André Lureau
2022-07-12 9:35 ` [PATCH v2 11/15] qemu-common: move scripts/qapi marcandre.lureau
2022-08-05 8:02 ` Markus Armbruster
2022-08-05 8:49 ` Marc-André Lureau
2022-08-11 6:52 ` Markus Armbruster
2022-08-11 7:11 ` Marc-André Lureau
2022-08-11 9:05 ` Markus Armbruster
2022-08-11 10:09 ` Marc-André Lureau
2022-08-11 10:22 ` Peter Maydell
2022-08-11 10:50 ` Marc-André Lureau
2022-08-11 12:15 ` Daniel P. Berrangé
2022-08-11 13:35 ` Markus Armbruster
2022-08-22 8:16 ` Marc-André Lureau
2022-09-02 11:15 ` Markus Armbruster
2022-09-02 13:22 ` Marc-André Lureau
2022-08-11 11:46 ` Markus Armbruster
2022-07-12 9:35 ` [PATCH v2 12/15] qemu-common: move glib-compat.h marcandre.lureau
2022-07-12 15:00 ` Warner Losh
2022-07-12 9:35 ` [PATCH v2 13/15] qemu-common: move error-report marcandre.lureau
2022-07-12 9:35 ` [PATCH v2 14/15] mtest2make.py: teach suite name that are just "PROJECT" marcandre.lureau
2022-08-05 10:35 ` Paolo Bonzini
2022-08-05 11:22 ` Marc-André Lureau
2022-07-12 9:35 ` [PATCH v2 15/15] qemu-common: add error-report test marcandre.lureau
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAJ+F1C++5KSWioj9Tq=0phFkY1W7zpa-qyAmD1KsonRhA5Kycw@mail.gmail.com' \
--to=marcandre.lureau@gmail.com \
--cc=danielhb413@gmail.com \
--cc=lucas.araujo@eldorado.org.br \
--cc=qemu-devel@nongnu.org \
--cc=richard.henderson@linaro.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.