[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH v5 03/18] qemu/int128: addition of div/rem 128-bit operations
From: |
Alistair Francis |
Subject: |
Re: [PATCH v5 03/18] qemu/int128: addition of div/rem 128-bit operations |
Date: |
Tue, 23 Nov 2021 16:04:55 +1000 |
On Sat, Nov 13, 2021 at 1:06 AM Frédéric Pétrot
<frederic.petrot@univ-grenoble-alpes.fr> wrote:
>
> 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>
Alistair
> ---
> include/qemu/int128.h | 6 ++
> util/int128.c | 145 ++++++++++++++++++++++++++++++++++++++++++
> util/meson.build | 1 +
> 3 files changed, 152 insertions(+)
> create mode 100644 util/int128.c
>
> 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..c2ddf197e1
> --- /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;
> +
> + if ((s = clz64(v.hi)) == 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.33.1
>
>