From: marcandre.lureau@redhat.com
To: qemu-devel@nongnu.org
Cc: "Eric Blake" <eblake@redhat.com>,
"Cleber Rosa" <crosa@redhat.com>,
qemu-block@nongnu.org, "Paolo Bonzini" <pbonzini@redhat.com>,
"Xie Yongji" <xieyongji@bytedance.com>,
"Kyle Evans" <kevans@freebsd.org>,
"Peter Maydell" <peter.maydell@linaro.org>,
"John Snow" <jsnow@redhat.com>,
"Michael Roth" <michael.roth@amd.com>,
"Warner Losh" <imp@bsdimp.com>, "Kevin Wolf" <kwolf@redhat.com>,
"Dr. David Alan Gilbert" <dgilbert@redhat.com>,
"Markus Armbruster" <armbru@redhat.com>,
"Vladimir Sementsov-Ogievskiy" <vsementsov@yandex-team.ru>,
"Laurent Vivier" <laurent@vivier.eu>,
"Fam Zheng" <fam@euphon.net>, "Hanna Reitz" <hreitz@redhat.com>,
"Marc-André Lureau" <marcandre.lureau@redhat.com>
Subject: [PATCH v2 09/15] util: move 256-by-128 division helpers to int128
Date: Tue, 12 Jul 2022 13:35:22 +0400 [thread overview]
Message-ID: <20220712093528.4144184-10-marcandre.lureau@redhat.com> (raw)
In-Reply-To: <20220712093528.4144184-1-marcandre.lureau@redhat.com>
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
next prev parent reply other threads:[~2022-07-12 9:49 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 ` marcandre.lureau [this message]
2022-08-04 16:17 ` [PATCH v2 09/15] util: move 256-by-128 division helpers to int128 Marc-André Lureau
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=20220712093528.4144184-10-marcandre.lureau@redhat.com \
--to=marcandre.lureau@redhat.com \
--cc=armbru@redhat.com \
--cc=crosa@redhat.com \
--cc=dgilbert@redhat.com \
--cc=eblake@redhat.com \
--cc=fam@euphon.net \
--cc=hreitz@redhat.com \
--cc=imp@bsdimp.com \
--cc=jsnow@redhat.com \
--cc=kevans@freebsd.org \
--cc=kwolf@redhat.com \
--cc=laurent@vivier.eu \
--cc=michael.roth@amd.com \
--cc=pbonzini@redhat.com \
--cc=peter.maydell@linaro.org \
--cc=qemu-block@nongnu.org \
--cc=qemu-devel@nongnu.org \
--cc=vsementsov@yandex-team.ru \
--cc=xieyongji@bytedance.com \
/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.