diff mbox series

[v6,03/18] qemu/int128: addition of div/rem 128-bit operations

Message ID 20211128135719.50444-4-frederic.petrot@univ-grenoble-alpes.fr (mailing list archive)
State New, archived
Headers show
Series Adding partial support for 128-bit riscv target | expand

Commit Message

Frédéric Pétrot Nov. 28, 2021, 1:57 p.m. UTC 
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>
---
 include/qemu/int128.h |   6 ++
 util/int128.c         | 145 ++++++++++++++++++++++++++++++++++++++++++
 util/meson.build      |   1 +
 3 files changed, 152 insertions(+)
 create mode 100644 util/int128.c

Comments

Richard Henderson Nov. 29, 2021, 10:07 a.m. UTC | #1 
On 11/28/21 2:57 PM, Frédéric Pétrot wrote:
> --- /dev/null
> +++ b/util/int128.c
> @@ -0,0 +1,145 @@
> +#include "qemu/osdep.h"
> +#include "qemu/host-utils.h"
> +#include "qemu/int128.h"

Missing file header and copyright boilerplate.

> +#ifdef CONFIG_INT128
> +
> +Int128 int128_divu(Int128 a, Int128 b)
> +{
> +    return (__uint128_t)a / (__uint128_t)b;
> +}
> +
> +Int128 int128_remu(Int128 a, Int128 b)
> +{
> +    return (__uint128_t)a % (__uint128_t)b;
> +}
> +
> +Int128 int128_divs(Int128 a, Int128 b)
> +{
> +    return a / b;
> +}
> +
> +Int128 int128_rems(Int128 a, Int128 b)
> +{
> +    return a % b;
> +}

I think we should simply expose these inline, and let the compiler call its runtime 
function directly.


r~
Frédéric Pétrot Nov. 29, 2021, 2:27 p.m. UTC | #2 
On 29/11/2021 11:07, Richard Henderson wrote:
> On 11/28/21 2:57 PM, Frédéric Pétrot wrote:
>> --- /dev/null
>> +++ b/util/int128.c
>> @@ -0,0 +1,145 @@
>> +#include "qemu/osdep.h"
>> +#include "qemu/host-utils.h"
>> +#include "qemu/int128.h"
> 
> Missing file header and copyright boilerplate.
> 
>> +#ifdef CONFIG_INT128
>> +
>> +Int128 int128_divu(Int128 a, Int128 b)
>> +{
>> +    return (__uint128_t)a / (__uint128_t)b;
>> +}
>> +
>> +Int128 int128_remu(Int128 a, Int128 b)
>> +{
>> +    return (__uint128_t)a % (__uint128_t)b;
>> +}
>> +
>> +Int128 int128_divs(Int128 a, Int128 b)
>> +{
>> +    return a / b;
>> +}
>> +
>> +Int128 int128_rems(Int128 a, Int128 b)
>> +{
>> +    return a % b;
>> +}
> 
> I think we should simply expose these inline, and let the compiler call its 
> runtime function directly.

   Thanks.
   Ok, I'll drop that and handle the CONFIG_INT128 directly in the rv128
   div/rem helpers then.
   Frédéric
> 
> 
> r~
Richard Henderson Nov. 29, 2021, 2:32 p.m. UTC | #3 
On 11/29/21 3:27 PM, Frédéric Pétrot wrote:
> On 29/11/2021 11:07, Richard Henderson wrote:
>> On 11/28/21 2:57 PM, Frédéric Pétrot wrote:
>>> --- /dev/null
>>> +++ b/util/int128.c
>>> @@ -0,0 +1,145 @@
>>> +#include "qemu/osdep.h"
>>> +#include "qemu/host-utils.h"
>>> +#include "qemu/int128.h"
>>
>> Missing file header and copyright boilerplate.
>>
>>> +#ifdef CONFIG_INT128
>>> +
>>> +Int128 int128_divu(Int128 a, Int128 b)
>>> +{
>>> +    return (__uint128_t)a / (__uint128_t)b;
>>> +}
>>> +
>>> +Int128 int128_remu(Int128 a, Int128 b)
>>> +{
>>> +    return (__uint128_t)a % (__uint128_t)b;
>>> +}
>>> +
>>> +Int128 int128_divs(Int128 a, Int128 b)
>>> +{
>>> +    return a / b;
>>> +}
>>> +
>>> +Int128 int128_rems(Int128 a, Int128 b)
>>> +{
>>> +    return a % b;
>>> +}
>>
>> I think we should simply expose these inline, and let the compiler call its runtime 
>> function directly.
> 
>    Thanks.
>    Ok, I'll drop that and handle the CONFIG_INT128 directly in the rv128
>    div/rem helpers then.

No, that's not what I meant.  Copy these directly into include/qemu/int128.h and add 
static inline, within the existing CONFIG_INT128 block.


r~
diff mbox series

Patch

diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index b6d517aea4..ef41892dac 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -386,4 +386,10 @@  static inline void bswap128s(Int128 *s)
     *s = bswap128(*s);
 }
 
+#define UINT128_MAX int128_make128(~0LL, ~0LL)
+Int128 int128_divu(Int128, Int128);
+Int128 int128_remu(Int128, Int128);
+Int128 int128_divs(Int128, Int128);
+Int128 int128_rems(Int128, Int128);
+
 #endif /* INT128_H */
diff --git a/util/int128.c b/util/int128.c
new file mode 100644
index 0000000000..62c56c8b7c
--- /dev/null
+++ b/util/int128.c
@@ -0,0 +1,145 @@ 
+#include "qemu/osdep.h"
+#include "qemu/host-utils.h"
+#include "qemu/int128.h"
+
+#ifdef CONFIG_INT128
+
+Int128 int128_divu(Int128 a, Int128 b)
+{
+    return (__uint128_t)a / (__uint128_t)b;
+}
+
+Int128 int128_remu(Int128 a, Int128 b)
+{
+    return (__uint128_t)a % (__uint128_t)b;
+}
+
+Int128 int128_divs(Int128 a, Int128 b)
+{
+    return a / b;
+}
+
+Int128 int128_rems(Int128 a, Int128 b)
+{
+    return a % b;
+}
+
+#else
+
+/*
+ * 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'))