Message ID | 20211112145902.205131-4-frederic.petrot@univ-grenoble-alpes.fr |
---|---|
State | New |
Headers | show |
Series | Adding partial support for 128-bit riscv target | expand |
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 > >
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'))
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> --- include/qemu/int128.h | 6 ++ util/int128.c | 145 ++++++++++++++++++++++++++++++++++++++++++ util/meson.build | 1 + 3 files changed, 152 insertions(+) create mode 100644 util/int128.c