From: Alistair Francis <alistair.francis@opensource.wdc.com>
To: qemu-devel@nongnu.org
Cc: alistair23@gmail.com,
"Frédéric Pétrot" <frederic.petrot@univ-grenoble-alpes.fr>,
"Fabien Portas" <fabien.portas@grenoble-inp.org>,
"Alistair Francis" <alistair.francis@wdc.com>
Subject: [PULL 19/37] qemu/int128: addition of div/rem 128-bit operations
Date: Sat, 8 Jan 2022 15:50:30 +1000 [thread overview]
Message-ID: <20220108055048.3512645-20-alistair.francis@opensource.wdc.com> (raw)
In-Reply-To: <20220108055048.3512645-1-alistair.francis@opensource.wdc.com>
From: Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr>
Addition of div and rem on 128-bit integers, using the 128/64->128 divu and
64x64->128 mulu in host-utils.
These operations will be used within div/rem helpers in the 128-bit riscv
target.
Signed-off-by: Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr>
Co-authored-by: Fabien Portas <fabien.portas@grenoble-inp.org>
Reviewed-by: Alistair Francis <alistair.francis@wdc.com>
Message-id: 20220106210108.138226-4-frederic.petrot@univ-grenoble-alpes.fr
Signed-off-by: Alistair Francis <alistair.francis@wdc.com>
---
include/qemu/int128.h | 27 ++++++++
util/int128.c | 147 ++++++++++++++++++++++++++++++++++++++++++
util/meson.build | 1 +
3 files changed, 175 insertions(+)
create mode 100644 util/int128.c
diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index b6d517aea4..2c4064256c 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -172,6 +172,26 @@ static inline Int128 bswap128(Int128 a)
#endif
}
+static inline Int128 int128_divu(Int128 a, Int128 b)
+{
+ return (__uint128_t)a / (__uint128_t)b;
+}
+
+static inline Int128 int128_remu(Int128 a, Int128 b)
+{
+ return (__uint128_t)a % (__uint128_t)b;
+}
+
+static inline Int128 int128_divs(Int128 a, Int128 b)
+{
+ return a / b;
+}
+
+static inline Int128 int128_rems(Int128 a, Int128 b)
+{
+ return a % b;
+}
+
#else /* !CONFIG_INT128 */
typedef struct Int128 Int128;
@@ -379,6 +399,11 @@ static inline Int128 bswap128(Int128 a)
return int128_make128(bswap64(a.hi), bswap64(a.lo));
}
+Int128 int128_divu(Int128, Int128);
+Int128 int128_remu(Int128, Int128);
+Int128 int128_divs(Int128, Int128);
+Int128 int128_rems(Int128, Int128);
+
#endif /* CONFIG_INT128 */
static inline void bswap128s(Int128 *s)
@@ -386,4 +411,6 @@ static inline void bswap128s(Int128 *s)
*s = bswap128(*s);
}
+#define UINT128_MAX int128_make128(~0LL, ~0LL)
+
#endif /* INT128_H */
diff --git a/util/int128.c b/util/int128.c
new file mode 100644
index 0000000000..ed8f25fef1
--- /dev/null
+++ b/util/int128.c
@@ -0,0 +1,147 @@
+/*
+ * 128-bit division and remainder for compilers not supporting __int128
+ *
+ * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/host-utils.h"
+#include "qemu/int128.h"
+
+#ifndef CONFIG_INT128
+
+/*
+ * Division and remainder algorithms for 128-bit due to Stefan Kanthak,
+ * https://skanthak.homepage.t-online.de/integer.html#udivmodti4
+ * Preconditions:
+ * - function should never be called with v equals to 0, it has to
+ * be dealt with beforehand
+ * - quotien pointer must be valid
+ */
+static Int128 divrem128(Int128 u, Int128 v, Int128 *q)
+{
+ Int128 qq;
+ uint64_t hi, lo, tmp;
+ int s = clz64(v.hi);
+
+ if (s == 64) {
+ /* we have uu÷0v => let's use divu128 */
+ hi = u.hi;
+ lo = u.lo;
+ tmp = divu128(&lo, &hi, v.lo);
+ *q = int128_make128(lo, hi);
+ return int128_make128(tmp, 0);
+ } else {
+ hi = int128_gethi(int128_lshift(v, s));
+
+ if (hi > u.hi) {
+ lo = u.lo;
+ tmp = u.hi;
+ divu128(&lo, &tmp, hi);
+ lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s));
+ } else { /* prevent overflow */
+ lo = u.lo;
+ tmp = u.hi - hi;
+ divu128(&lo, &tmp, hi);
+ lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s));
+ }
+
+ qq = int128_make64(lo);
+
+ tmp = lo * v.hi;
+ mulu64(&lo, &hi, lo, v.lo);
+ hi += tmp;
+
+ if (hi < tmp /* quotient * divisor >= 2**128 > dividend */
+ || hi > u.hi /* quotient * divisor > dividend */
+ || (hi == u.hi && lo > u.lo)) {
+ qq.lo -= 1;
+ mulu64(&lo, &hi, qq.lo, v.lo);
+ hi += qq.lo * v.hi;
+ }
+
+ *q = qq;
+ u.hi -= hi + (u.lo < lo);
+ u.lo -= lo;
+ return u;
+ }
+}
+
+Int128 int128_divu(Int128 a, Int128 b)
+{
+ Int128 q;
+ divrem128(a, b, &q);
+ return q;
+}
+
+Int128 int128_remu(Int128 a, Int128 b)
+{
+ Int128 q;
+ return divrem128(a, b, &q);
+}
+
+Int128 int128_divs(Int128 a, Int128 b)
+{
+ Int128 q;
+ bool sgna = !int128_nonneg(a);
+ bool sgnb = !int128_nonneg(b);
+
+ if (sgna) {
+ a = int128_neg(a);
+ }
+
+ if (sgnb) {
+ b = int128_neg(b);
+ }
+
+ divrem128(a, b, &q);
+
+ if (sgna != sgnb) {
+ q = int128_neg(q);
+ }
+
+ return q;
+}
+
+Int128 int128_rems(Int128 a, Int128 b)
+{
+ Int128 q, r;
+ bool sgna = !int128_nonneg(a);
+ bool sgnb = !int128_nonneg(b);
+
+ if (sgna) {
+ a = int128_neg(a);
+ }
+
+ if (sgnb) {
+ b = int128_neg(b);
+ }
+
+ r = divrem128(a, b, &q);
+
+ if (sgna) {
+ r = int128_neg(r);
+ }
+
+ return r;
+}
+
+#endif
diff --git a/util/meson.build b/util/meson.build
index 05b593055a..e676b2f6c6 100644
--- a/util/meson.build
+++ b/util/meson.build
@@ -48,6 +48,7 @@ util_ss.add(files('transactions.c'))
util_ss.add(when: 'CONFIG_POSIX', if_true: files('drm.c'))
util_ss.add(files('guest-random.c'))
util_ss.add(files('yank.c'))
+util_ss.add(files('int128.c'))
if have_user
util_ss.add(files('selfmap.c'))
--
2.31.1
next prev parent reply other threads:[~2022-01-08 6:09 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-01-08 5:50 [PULL 00/37] riscv-to-apply queue Alistair Francis
2022-01-08 5:50 ` [PULL 01/37] target/riscv/pmp: fix no pmp illegal intrs Alistair Francis
2022-01-08 5:50 ` [PULL 02/37] hw/dma: sifive_pdma: support high 32-bit access of 64-bit register Alistair Francis
2022-01-08 5:50 ` [PULL 03/37] hw/dma: sifive_pdma: permit 4/8-byte access size of PDMA registers Alistair Francis
2022-01-08 5:50 ` [PULL 04/37] hw/intc: sifive_plic: Add a reset function Alistair Francis
2022-01-08 5:50 ` [PULL 05/37] hw/intc: sifive_plic: Cleanup the write function Alistair Francis
2022-01-08 5:50 ` [PULL 06/37] hw/intc: sifive_plic: Cleanup the read function Alistair Francis
2022-01-08 5:50 ` [PULL 07/37] hw/intc: sifive_plic: Cleanup remaining functions Alistair Francis
2022-01-08 5:50 ` [PULL 08/37] target/riscv: Mark the Hypervisor extension as non experimental Alistair Francis
2022-01-08 5:50 ` [PULL 09/37] target/riscv: Enable the Hypervisor extension by default Alistair Francis
2022-01-08 5:50 ` [PULL 10/37] hw/riscv: Use error_fatal for SoC realisation Alistair Francis
2022-01-08 5:50 ` [PULL 11/37] hw/riscv: virt: Allow support for 32 cores Alistair Francis
2022-01-08 5:50 ` [PULL 12/37] roms/opensbi: Upgrade from v0.9 to v1.0 Alistair Francis
2022-01-08 5:50 ` [PULL 13/37] target/riscv: rvv-1.0: Call the correct RVF/RVD check function for widening fp insns Alistair Francis
2022-01-08 5:50 ` [PULL 14/37] target/riscv: rvv-1.0: Call the correct RVF/RVD check function for widening fp/int type-convert insns Alistair Francis
2022-01-08 5:50 ` [PULL 15/37] target/riscv: rvv-1.0: Call the correct RVF/RVD check function for narrowing " Alistair Francis
2022-01-08 5:50 ` [PULL 16/37] target/riscv: Fix position of 'experimental' comment Alistair Francis
2022-01-08 5:50 ` [PULL 17/37] exec/memop: Adding signedness to quad definitions Alistair Francis
2022-01-08 5:50 ` [PULL 18/37] exec/memop: Adding signed quad and octo defines Alistair Francis
2022-01-08 5:50 ` Alistair Francis [this message]
2022-01-08 5:50 ` [PULL 20/37] target/riscv: additional macros to check instruction support Alistair Francis
2022-01-08 5:50 ` [PULL 21/37] target/riscv: separation of bitwise logic and arithmetic helpers Alistair Francis
2022-01-08 5:50 ` [PULL 22/37] target/riscv: array for the 64 upper bits of 128-bit registers Alistair Francis
2022-01-08 5:50 ` [PULL 23/37] target/riscv: setup everything for rv64 to support rv128 execution Alistair Francis
2022-01-08 5:50 ` [PULL 24/37] target/riscv: moving some insns close to similar insns Alistair Francis
2022-01-08 5:50 ` [PULL 25/37] target/riscv: accessors to registers upper part and 128-bit load/store Alistair Francis
2022-01-08 5:50 ` [PULL 26/37] target/riscv: support for 128-bit bitwise instructions Alistair Francis
2022-01-08 5:50 ` [PULL 27/37] target/riscv: support for 128-bit U-type instructions Alistair Francis
2022-01-08 5:50 ` [PULL 28/37] target/riscv: support for 128-bit shift instructions Alistair Francis
2022-01-08 5:50 ` [PULL 29/37] target/riscv: support for 128-bit arithmetic instructions Alistair Francis
2022-01-08 5:50 ` [PULL 30/37] target/riscv: support for 128-bit M extension Alistair Francis
2022-01-08 5:50 ` [PULL 31/37] target/riscv: adding high part of some csrs Alistair Francis
2022-01-08 5:50 ` [PULL 32/37] target/riscv: helper functions to wrap calls to 128-bit csr insns Alistair Francis
2022-01-08 5:50 ` [PULL 33/37] target/riscv: modification of the trans_csrxx for 128-bit support Alistair Francis
2022-01-08 5:50 ` [PULL 34/37] target/riscv: actual functions to realize crs 128-bit insns Alistair Francis
2022-01-08 5:50 ` [PULL 35/37] target/riscv: Set the opcode in DisasContext Alistair Francis
2022-01-08 5:50 ` [PULL 36/37] target/riscv: Fixup setting GVA Alistair Francis
2022-01-08 5:50 ` [PULL 37/37] target/riscv: Implement the stval/mtval illegal instruction Alistair Francis
2022-01-08 17:37 ` [PULL 00/37] riscv-to-apply queue Richard Henderson
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=20220108055048.3512645-20-alistair.francis@opensource.wdc.com \
--to=alistair.francis@opensource.wdc.com \
--cc=alistair.francis@wdc.com \
--cc=alistair23@gmail.com \
--cc=fabien.portas@grenoble-inp.org \
--cc=frederic.petrot@univ-grenoble-alpes.fr \
--cc=qemu-devel@nongnu.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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).