| Message ID | 1482166064-18121-2-git-send-email-joserz@linux.vnet.ibm.com |
|---|---|
| State | New |
| Headers | show |
On Mon, Dec 19, 2016 at 02:47:39PM -0200, Jose Ricardo Ziviani wrote: > This commit implements functions to right and left shifts and the > unittest for them. Such functions is needed due to instructions > that requires them. > > Today, there is already a right shift implementation in int128.h > but it's designed for signed numbers. The subject line is misleading, since this isn't actually local to target-ppc. I'd want an ack from Paolo or Eric Blake before taking this change to host-utils through my tree. > > Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com> > --- > include/qemu/host-utils.h | 3 ++ > tests/Makefile.include | 5 ++- > tests/test-shift128.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++ > util/Makefile.objs | 2 +- > util/host-utils.c | 44 +++++++++++++++++++++ > 5 files changed, 150 insertions(+), 2 deletions(-) > create mode 100644 tests/test-shift128.c > > diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h > index 46187bb..e87de19 100644 > --- a/include/qemu/host-utils.h > +++ b/include/qemu/host-utils.h > @@ -516,4 +516,7 @@ static inline uint64_t pow2ceil(uint64_t value) > return 1ULL << (64 - nlz); > } > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift); > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow); > + > #endif > diff --git a/tests/Makefile.include b/tests/Makefile.include > index b574964..8ccaa3e 100644 > --- a/tests/Makefile.include > +++ b/tests/Makefile.include > @@ -65,6 +65,8 @@ check-unit-$(CONFIG_POSIX) += tests/test-vmstate$(EXESUF) > endif > check-unit-y += tests/test-cutils$(EXESUF) > gcov-files-test-cutils-y += util/cutils.c > +check-unit-y += tests/test-shift128$(EXESUF) > +gcov-files-test-shift128-y = util/host-utils.c > check-unit-y += tests/test-mul64$(EXESUF) > gcov-files-test-mul64-y = util/host-utils.c > check-unit-y += tests/test-int128$(EXESUF) > @@ -464,7 +466,7 @@ test-obj-y = tests/check-qint.o tests/check-qstring.o tests/check-qdict.o \ > tests/test-x86-cpuid.o tests/test-mul64.o tests/test-int128.o \ > tests/test-opts-visitor.o tests/test-qmp-event.o \ > tests/rcutorture.o tests/test-rcu-list.o \ > - tests/test-qdist.o \ > + tests/test-qdist.o tests/test-shift128.o \ > tests/test-qht.o tests/qht-bench.o tests/test-qht-par.o \ > tests/atomic_add-bench.o > > @@ -572,6 +574,7 @@ tests/test-qmp-commands$(EXESUF): tests/test-qmp-commands.o tests/test-qmp-marsh > tests/test-visitor-serialization$(EXESUF): tests/test-visitor-serialization.o $(test-qapi-obj-y) > tests/test-opts-visitor$(EXESUF): tests/test-opts-visitor.o $(test-qapi-obj-y) > > +tests/test-shift128$(EXESUF): tests/test-shift128.o $(test-util-obj-y) > tests/test-mul64$(EXESUF): tests/test-mul64.o $(test-util-obj-y) > tests/test-bitops$(EXESUF): tests/test-bitops.o $(test-util-obj-y) > tests/test-crypto-hash$(EXESUF): tests/test-crypto-hash.o $(test-crypto-obj-y) > diff --git a/tests/test-shift128.c b/tests/test-shift128.c > new file mode 100644 > index 0000000..52be6a2 > --- /dev/null > +++ b/tests/test-shift128.c > @@ -0,0 +1,98 @@ > +/* > + * Test unsigned left and right shift > + * > + * This work is licensed under the terms of the GNU LGPL, version 2 or later. > + * See the COPYING.LIB file in the top-level directory. > + * > + */ > + > +#include "qemu/osdep.h" > +#include "qemu/host-utils.h" > + > +typedef struct { > + uint64_t low; > + uint64_t high; > + uint64_t rlow; > + uint64_t rhigh; > + int32_t shift; > + bool overflow; > +} test_data; > + > +static const test_data test_ltable[] = { > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > + { 1ULL, 0, 2ULL, 0, 1, false } > + { 1ULL, 0, 4ULL, 0, 2, false }, > + { 1ULL, 0, 16ULL, 0, 4, false }, > + { 1ULL, 0, 256ULL, 0, 8, false }, > + { 1ULL, 0, 65536ULL, 0, 16, false }, > + { 1ULL, 0, 2147483648ULL, 0, 31, false }, > + { 1ULL, 0, 35184372088832ULL, 0, 45, false }, > + { 1ULL, 0, 1152921504606846976ULL, 0, 60, false }, These test cases would be much easier to follow in hex , > + { 1ULL, 0, 0, 1ULL, 64, false }, > + { 1ULL, 0, 0, 65536ULL, 80, false }, > + { 1ULL, 0, 0, 9223372036854775808ULL, 127, false }, > + { 0ULL, 1, 0, 0, 64, true }, > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > + 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true }, > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > + 0, 0x8888888888888888ULL, 64, true }, > + { 0x8ULL, 0, 0, 0x8ULL, 64, false }, > + { 0x8ULL, 0, 0, 0x8000000000000000ULL, 124, false }, > + { 0x1ULL, 0, 0, 0x4000000000000000ULL, 126, false }, > + { 0x1ULL, 0, 0, 0x8000000000000000ULL, 127, false }, > + { 0x1ULL, 0, 0x1ULL, 0, 128, true }, > + { 0, 0, 0ULL, 0, 200, false }, > +}; > + > +static const test_data test_rtable[] = { > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > + { 9223372036854775808ULL, 9223372036854775808ULL, > + 2147483648L, 2147483648ULL, 32, false }, > + { 9223372036854775808ULL, 9223372036854775808ULL, > + 9223372036854775808ULL, 0, 64, false }, > + { 9223372036854775808ULL, 9223372036854775808ULL, > + 36028797018963968ULL, 0, 72, false }, > + { 9223372036854775808ULL, 9223372036854775808ULL, > + 1ULL, 0, 127, false }, > + { 9223372036854775808ULL, 0, 4611686018427387904ULL, 0, 1, false }, > + { 9223372036854775808ULL, 0, 2305843009213693952ULL, 0, 2, false }, > + { 9223372036854775808ULL, 0, 36028797018963968ULL, 0, 8, false }, > + { 9223372036854775808ULL, 0, 140737488355328ULL, 0, 16, false }, > + { 9223372036854775808ULL, 0, 2147483648ULL, 0, 32, false }, > + { 9223372036854775808ULL, 0, 1ULL, 0, 63, false }, > + { 9223372036854775808ULL, 0, 0ULL, 0, 64, false }, > +}; > + > +static void test_lshift(void) > +{ > + int i; > + > + for (i = 0; i < ARRAY_SIZE(test_ltable); ++i) { > + bool overflow = false; > + test_data tmp = test_ltable[i]; > + ulshift(&tmp.low, &tmp.high, tmp.shift, &overflow); > + g_assert_cmpuint(tmp.low, ==, tmp.rlow); > + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); > + g_assert_cmpuint(tmp.overflow, ==, overflow); > + } > +} > + > +static void test_rshift(void) > +{ > + int i; > + > + for (i = 0; i < ARRAY_SIZE(test_rtable); ++i) { > + test_data tmp = test_rtable[i]; > + urshift(&tmp.low, &tmp.high, tmp.shift); > + g_assert_cmpuint(tmp.low, ==, tmp.rlow); > + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); > + } > +} > + > +int main(int argc, char **argv) > +{ > + g_test_init(&argc, &argv, NULL); > + g_test_add_func("/host-utils/test_lshift", test_lshift); > + g_test_add_func("/host-utils/test_rshift", test_rshift); > + return g_test_run(); > +} > diff --git a/util/Makefile.objs b/util/Makefile.objs > index ad0f9c7..39ae26e 100644 > --- a/util/Makefile.objs > +++ b/util/Makefile.objs > @@ -11,7 +11,7 @@ util-obj-$(CONFIG_POSIX) += memfd.o > util-obj-$(CONFIG_WIN32) += oslib-win32.o > util-obj-$(CONFIG_WIN32) += qemu-thread-win32.o > util-obj-y += envlist.o path.o module.o > -util-obj-$(call lnot,$(CONFIG_INT128)) += host-utils.o > +util-obj-y += host-utils.o > util-obj-y += bitmap.o bitops.o hbitmap.o > util-obj-y += fifo8.o > util-obj-y += acl.o > diff --git a/util/host-utils.c b/util/host-utils.c > index b166e57..1ee2433 100644 > --- a/util/host-utils.c > +++ b/util/host-utils.c > @@ -26,6 +26,7 @@ > #include "qemu/osdep.h" > #include "qemu/host-utils.h" > > +#ifndef CONFIG_INT128 > /* Long integer helpers */ > static inline void mul64(uint64_t *plow, uint64_t *phigh, > uint64_t a, uint64_t b) > @@ -158,4 +159,47 @@ int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) > > return overflow; > } > +#endif > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift) > +{ > + shift &= 127; > + uint64_t h = *phigh >> (shift & 63); > + if (shift == 0) { > + return; > + } else if (shift >= 64) { > + *plow = h; > + *phigh = 0; > + } else { > + *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); > + *phigh = h; > + } > +} > + > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow) > +{ > + uint64_t low = *plow; > + uint64_t high = *phigh; > + > + if (shift > 127 && (low | high)) { > + *overflow = true; > + } > + shift &= 127; > + > + if (shift == 0) { > + return; > + } > + > + urshift(&low, &high, 128 - shift); > + if (low > 0 || high > 0) { > + *overflow = true; > + } > + > + if (shift >= 64) { > + *phigh = *plow << (shift & 63); > + *plow = 0; > + } else { > + *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); > + *plow = *plow << shift; > + } > +}
On Tue, Jan 03, 2017 at 10:53:33AM +1100, David Gibson wrote: > On Mon, Dec 19, 2016 at 02:47:39PM -0200, Jose Ricardo Ziviani wrote: > > This commit implements functions to right and left shifts and the > > unittest for them. Such functions is needed due to instructions > > that requires them. > > > > Today, there is already a right shift implementation in int128.h > > but it's designed for signed numbers. > > The subject line is misleading, since this isn't actually local to > target-ppc. I'd want an ack from Paolo or Eric Blake before taking > this change to host-utils through my tree. Thanks for reviewing it. Yeah, I didn't find the pattern for host-utils. Old commits have "host-utils:","target-ppc:", "janitor:", but mostly commits have nothing. I'm copying Paolo and Erik here for reviewing it as well. Happy 2017 :) Ziviani > > > > > Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com> > > --- > > include/qemu/host-utils.h | 3 ++ > > tests/Makefile.include | 5 ++- > > tests/test-shift128.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++ > > util/Makefile.objs | 2 +- > > util/host-utils.c | 44 +++++++++++++++++++++ > > 5 files changed, 150 insertions(+), 2 deletions(-) > > create mode 100644 tests/test-shift128.c > > > > diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h > > index 46187bb..e87de19 100644 > > --- a/include/qemu/host-utils.h > > +++ b/include/qemu/host-utils.h > > @@ -516,4 +516,7 @@ static inline uint64_t pow2ceil(uint64_t value) > > return 1ULL << (64 - nlz); > > } > > > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift); > > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow); > > + > > #endif > > diff --git a/tests/Makefile.include b/tests/Makefile.include > > index b574964..8ccaa3e 100644 > > --- a/tests/Makefile.include > > +++ b/tests/Makefile.include > > @@ -65,6 +65,8 @@ check-unit-$(CONFIG_POSIX) += tests/test-vmstate$(EXESUF) > > endif > > check-unit-y += tests/test-cutils$(EXESUF) > > gcov-files-test-cutils-y += util/cutils.c > > +check-unit-y += tests/test-shift128$(EXESUF) > > +gcov-files-test-shift128-y = util/host-utils.c > > check-unit-y += tests/test-mul64$(EXESUF) > > gcov-files-test-mul64-y = util/host-utils.c > > check-unit-y += tests/test-int128$(EXESUF) > > @@ -464,7 +466,7 @@ test-obj-y = tests/check-qint.o tests/check-qstring.o tests/check-qdict.o \ > > tests/test-x86-cpuid.o tests/test-mul64.o tests/test-int128.o \ > > tests/test-opts-visitor.o tests/test-qmp-event.o \ > > tests/rcutorture.o tests/test-rcu-list.o \ > > - tests/test-qdist.o \ > > + tests/test-qdist.o tests/test-shift128.o \ > > tests/test-qht.o tests/qht-bench.o tests/test-qht-par.o \ > > tests/atomic_add-bench.o > > > > @@ -572,6 +574,7 @@ tests/test-qmp-commands$(EXESUF): tests/test-qmp-commands.o tests/test-qmp-marsh > > tests/test-visitor-serialization$(EXESUF): tests/test-visitor-serialization.o $(test-qapi-obj-y) > > tests/test-opts-visitor$(EXESUF): tests/test-opts-visitor.o $(test-qapi-obj-y) > > > > +tests/test-shift128$(EXESUF): tests/test-shift128.o $(test-util-obj-y) > > tests/test-mul64$(EXESUF): tests/test-mul64.o $(test-util-obj-y) > > tests/test-bitops$(EXESUF): tests/test-bitops.o $(test-util-obj-y) > > tests/test-crypto-hash$(EXESUF): tests/test-crypto-hash.o $(test-crypto-obj-y) > > diff --git a/tests/test-shift128.c b/tests/test-shift128.c > > new file mode 100644 > > index 0000000..52be6a2 > > --- /dev/null > > +++ b/tests/test-shift128.c > > @@ -0,0 +1,98 @@ > > +/* > > + * Test unsigned left and right shift > > + * > > + * This work is licensed under the terms of the GNU LGPL, version 2 or later. > > + * See the COPYING.LIB file in the top-level directory. > > + * > > + */ > > + > > +#include "qemu/osdep.h" > > +#include "qemu/host-utils.h" > > + > > +typedef struct { > > + uint64_t low; > > + uint64_t high; > > + uint64_t rlow; > > + uint64_t rhigh; > > + int32_t shift; > > + bool overflow; > > +} test_data; > > + > > +static const test_data test_ltable[] = { > > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > > + { 1ULL, 0, 2ULL, 0, 1, false } > > + { 1ULL, 0, 4ULL, 0, 2, false }, > > + { 1ULL, 0, 16ULL, 0, 4, false }, > > + { 1ULL, 0, 256ULL, 0, 8, false }, > > + { 1ULL, 0, 65536ULL, 0, 16, false }, > > + { 1ULL, 0, 2147483648ULL, 0, 31, false }, > > + { 1ULL, 0, 35184372088832ULL, 0, 45, false }, > > + { 1ULL, 0, 1152921504606846976ULL, 0, 60, false }, > > These test cases would be much easier to follow in hex > , Sure, I'll change them > > + { 1ULL, 0, 0, 1ULL, 64, false }, > > + { 1ULL, 0, 0, 65536ULL, 80, false }, > > + { 1ULL, 0, 0, 9223372036854775808ULL, 127, false }, > > + { 0ULL, 1, 0, 0, 64, true }, > > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > > + 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true }, > > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > > + 0, 0x8888888888888888ULL, 64, true }, > > + { 0x8ULL, 0, 0, 0x8ULL, 64, false }, > > + { 0x8ULL, 0, 0, 0x8000000000000000ULL, 124, false }, > > + { 0x1ULL, 0, 0, 0x4000000000000000ULL, 126, false }, > > + { 0x1ULL, 0, 0, 0x8000000000000000ULL, 127, false }, > > + { 0x1ULL, 0, 0x1ULL, 0, 128, true }, > > + { 0, 0, 0ULL, 0, 200, false }, > > +}; > > + > > +static const test_data test_rtable[] = { > > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > > + { 9223372036854775808ULL, 9223372036854775808ULL, > > + 2147483648L, 2147483648ULL, 32, false }, > > + { 9223372036854775808ULL, 9223372036854775808ULL, > > + 9223372036854775808ULL, 0, 64, false }, > > + { 9223372036854775808ULL, 9223372036854775808ULL, > > + 36028797018963968ULL, 0, 72, false }, > > + { 9223372036854775808ULL, 9223372036854775808ULL, > > + 1ULL, 0, 127, false }, > > + { 9223372036854775808ULL, 0, 4611686018427387904ULL, 0, 1, false }, > > + { 9223372036854775808ULL, 0, 2305843009213693952ULL, 0, 2, false }, > > + { 9223372036854775808ULL, 0, 36028797018963968ULL, 0, 8, false }, > > + { 9223372036854775808ULL, 0, 140737488355328ULL, 0, 16, false }, > > + { 9223372036854775808ULL, 0, 2147483648ULL, 0, 32, false }, > > + { 9223372036854775808ULL, 0, 1ULL, 0, 63, false }, > > + { 9223372036854775808ULL, 0, 0ULL, 0, 64, false }, > > +}; > > + > > +static void test_lshift(void) > > +{ > > + int i; > > + > > + for (i = 0; i < ARRAY_SIZE(test_ltable); ++i) { > > + bool overflow = false; > > + test_data tmp = test_ltable[i]; > > + ulshift(&tmp.low, &tmp.high, tmp.shift, &overflow); > > + g_assert_cmpuint(tmp.low, ==, tmp.rlow); > > + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); > > + g_assert_cmpuint(tmp.overflow, ==, overflow); > > + } > > +} > > + > > +static void test_rshift(void) > > +{ > > + int i; > > + > > + for (i = 0; i < ARRAY_SIZE(test_rtable); ++i) { > > + test_data tmp = test_rtable[i]; > > + urshift(&tmp.low, &tmp.high, tmp.shift); > > + g_assert_cmpuint(tmp.low, ==, tmp.rlow); > > + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); > > + } > > +} > > + > > +int main(int argc, char **argv) > > +{ > > + g_test_init(&argc, &argv, NULL); > > + g_test_add_func("/host-utils/test_lshift", test_lshift); > > + g_test_add_func("/host-utils/test_rshift", test_rshift); > > + return g_test_run(); > > +} > > diff --git a/util/Makefile.objs b/util/Makefile.objs > > index ad0f9c7..39ae26e 100644 > > --- a/util/Makefile.objs > > +++ b/util/Makefile.objs > > @@ -11,7 +11,7 @@ util-obj-$(CONFIG_POSIX) += memfd.o > > util-obj-$(CONFIG_WIN32) += oslib-win32.o > > util-obj-$(CONFIG_WIN32) += qemu-thread-win32.o > > util-obj-y += envlist.o path.o module.o > > -util-obj-$(call lnot,$(CONFIG_INT128)) += host-utils.o > > +util-obj-y += host-utils.o > > util-obj-y += bitmap.o bitops.o hbitmap.o > > util-obj-y += fifo8.o > > util-obj-y += acl.o > > diff --git a/util/host-utils.c b/util/host-utils.c > > index b166e57..1ee2433 100644 > > --- a/util/host-utils.c > > +++ b/util/host-utils.c > > @@ -26,6 +26,7 @@ > > #include "qemu/osdep.h" > > #include "qemu/host-utils.h" > > > > +#ifndef CONFIG_INT128 > > /* Long integer helpers */ > > static inline void mul64(uint64_t *plow, uint64_t *phigh, > > uint64_t a, uint64_t b) > > @@ -158,4 +159,47 @@ int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) > > > > return overflow; > > } > > +#endif > > > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift) > > +{ > > + shift &= 127; > > + uint64_t h = *phigh >> (shift & 63); > > + if (shift == 0) { > > + return; > > + } else if (shift >= 64) { > > + *plow = h; > > + *phigh = 0; > > + } else { > > + *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); > > + *phigh = h; > > + } > > +} > > + > > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow) > > +{ > > + uint64_t low = *plow; > > + uint64_t high = *phigh; > > + > > + if (shift > 127 && (low | high)) { > > + *overflow = true; > > + } > > + shift &= 127; > > + > > + if (shift == 0) { > > + return; > > + } > > + > > + urshift(&low, &high, 128 - shift); > > + if (low > 0 || high > 0) { > > + *overflow = true; > > + } > > + > > + if (shift >= 64) { > > + *phigh = *plow << (shift & 63); > > + *plow = 0; > > + } else { > > + *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); > > + *plow = *plow << shift; > > + } > > +} > > -- > David Gibson | I'll have my music baroque, and my code > david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ > | _way_ _around_! > http://www.ozlabs.org/~dgibson
On 12/19/2016 10:47 AM, Jose Ricardo Ziviani wrote: > This commit implements functions to right and left shifts and the > unittest for them. Such functions is needed due to instructions > that requires them. > > Today, there is already a right shift implementation in int128.h > but it's designed for signed numbers. > > Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com> > --- > +static const test_data test_ltable[] = { > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > + { 1ULL, 0, 2ULL, 0, 1, false }, > + { 1ULL, 0, 4ULL, 0, 2, false }, > + { 1ULL, 0, 16ULL, 0, 4, false }, > + { 1ULL, 0, 256ULL, 0, 8, false }, > + { 1ULL, 0, 65536ULL, 0, 16, false }, > + { 1ULL, 0, 2147483648ULL, 0, 31, false }, > + { 1ULL, 0, 35184372088832ULL, 0, 45, false }, > + { 1ULL, 0, 1152921504606846976ULL, 0, 60, false }, > + { 1ULL, 0, 0, 1ULL, 64, false }, > + { 1ULL, 0, 0, 65536ULL, 80, false }, > + { 1ULL, 0, 0, 9223372036854775808ULL, 127, false }, I concur with the request to write these tests in hex. > + { 0ULL, 1, 0, 0, 64, true }, > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > + 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true }, > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > + 0, 0x8888888888888888ULL, 64, true }, > + { 0x8ULL, 0, 0, 0x8ULL, 64, false }, > + { 0x8ULL, 0, 0, 0x8000000000000000ULL, 124, false }, > + { 0x1ULL, 0, 0, 0x4000000000000000ULL, 126, false }, > + { 0x1ULL, 0, 0, 0x8000000000000000ULL, 127, false }, > + { 0x1ULL, 0, 0x1ULL, 0, 128, true }, Do we really want this to be well-defined behavior? Or would it be better to require shift to be in the bounded range [0,127] and assert() that it is always in range? At least your testsuite ensures that if we want it to be well-defined, we won't go breaking it. > + { 0, 0, 0ULL, 0, 200, false }, If you are going to support shifts larger than 127, your testsuite should include a shift of a non-zero number. Also, if you are going to implicitly truncate the shift value into range, then accepting a signed shift might be nicer (as there are cases where it is easier to code a shift by -1 than it is a shift by 127). > +++ b/util/host-utils.c > @@ -26,6 +26,7 @@ > #include "qemu/osdep.h" > #include "qemu/host-utils.h" > > +#ifndef CONFIG_INT128 > /* Long integer helpers */ > static inline void mul64(uint64_t *plow, uint64_t *phigh, > uint64_t a, uint64_t b) > @@ -158,4 +159,47 @@ int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) > > return overflow; > } > +#endif How is the addition of this #ifndef related to the rest of the patch? I almost wonder if it needs two patches (one to compile the file regardless of 128-bit support, the other to add new 128-bit shifts); if not, mentioning it in the commit message doesn't hurt. > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift) Comments on the function contract would be much appreciated (for example, what range must shift belong to, and the fact that the shift is modifying the value in-place, and that the result is always zero-extended). > +{ > + shift &= 127; This says you allow any shift value (whether negative or beyond 127); either the testsuite must cover this, or you should tighten the contract and assert that the callers pass a value in range. > + uint64_t h = *phigh >> (shift & 63); > + if (shift == 0) { > + return; Depending on the compiler, this may waste the work of computing h; maybe you can float this conditional first. > + } else if (shift >= 64) { > + *plow = h; > + *phigh = 0; > + } else { > + *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); > + *phigh = h; > + } At any rate, the math looks correct. > +} > + > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow) Again, doc comments are useful, including what overflow represents, and a repeat of the question on whether a signed shift amount makes sense if you intend to allow silent truncation of the shift value. > +{ > + uint64_t low = *plow; > + uint64_t high = *phigh; > + > + if (shift > 127 && (low | high)) { > + *overflow = true; > + } > + shift &= 127; > + > + if (shift == 0) { > + return; > + } > + > + urshift(&low, &high, 128 - shift); > + if (low > 0 || high > 0) { Can't this be written 'if (low | high)' as above? > + *overflow = true; > + } > + > + if (shift >= 64) { > + *phigh = *plow << (shift & 63); > + *plow = 0; > + } else { > + *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); > + *plow = *plow << shift; > + } > +} >
Hello Eric, Thank you very much for your review. Please, read my responses and questions below. Happy 2017. On Tue, Jan 03, 2017 at 09:20:37AM -0600, Eric Blake wrote: > On 12/19/2016 10:47 AM, Jose Ricardo Ziviani wrote: > > This commit implements functions to right and left shifts and the > > unittest for them. Such functions is needed due to instructions > > that requires them. > > > > Today, there is already a right shift implementation in int128.h > > but it's designed for signed numbers. > > > > Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com> > > --- > > > +static const test_data test_ltable[] = { > > + { 1223ULL, 0, 1223ULL, 0, 0, false }, > > + { 1ULL, 0, 2ULL, 0, 1, false }, > > + { 1ULL, 0, 4ULL, 0, 2, false }, > > + { 1ULL, 0, 16ULL, 0, 4, false }, > > + { 1ULL, 0, 256ULL, 0, 8, false }, > > + { 1ULL, 0, 65536ULL, 0, 16, false }, > > + { 1ULL, 0, 2147483648ULL, 0, 31, false }, > > + { 1ULL, 0, 35184372088832ULL, 0, 45, false }, > > + { 1ULL, 0, 1152921504606846976ULL, 0, 60, false }, > > + { 1ULL, 0, 0, 1ULL, 64, false }, > > + { 1ULL, 0, 0, 65536ULL, 80, false }, > > + { 1ULL, 0, 0, 9223372036854775808ULL, 127, false }, > > I concur with the request to write these tests in hex. OK > > > + { 0ULL, 1, 0, 0, 64, true }, > > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > > + 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true }, > > + { 0x8888888888888888ULL, 0x9999999999999999ULL, > > + 0, 0x8888888888888888ULL, 64, true }, > > + { 0x8ULL, 0, 0, 0x8ULL, 64, false }, > > + { 0x8ULL, 0, 0, 0x8000000000000000ULL, 124, false }, > > + { 0x1ULL, 0, 0, 0x4000000000000000ULL, 126, false }, > > + { 0x1ULL, 0, 0, 0x8000000000000000ULL, 127, false }, > > + { 0x1ULL, 0, 0x1ULL, 0, 128, true }, > > Do we really want this to be well-defined behavior? Or would it be > better to require shift to be in the bounded range [0,127] and assert() > that it is always in range? At least your testsuite ensures that if we > want it to be well-defined, we won't go breaking it. I prefer to write more testcases and let the functions as is, making the caller responsible to complain about the shift if necessary. > > > + { 0, 0, 0ULL, 0, 200, false }, > > If you are going to support shifts larger than 127, your testsuite > should include a shift of a non-zero number. Also, if you are going to > implicitly truncate the shift value into range, then accepting a signed > shift might be nicer (as there are cases where it is easier to code a > shift by -1 than it is a shift by 127). Correct me if I'm wrong: Actually the caller can use the function like: urshift(low, high, (uint32_t)-1); And I'll get "shift == UINT_MAX", which truncates to 127 after "&= 127". I don't need to use a signed integer necessarily, right? > > > +++ b/util/host-utils.c > > @@ -26,6 +26,7 @@ > > #include "qemu/osdep.h" > > #include "qemu/host-utils.h" > > > > +#ifndef CONFIG_INT128 > > /* Long integer helpers */ > > static inline void mul64(uint64_t *plow, uint64_t *phigh, > > uint64_t a, uint64_t b) > > @@ -158,4 +159,47 @@ int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) > > > > return overflow; > > } > > +#endif > > How is the addition of this #ifndef related to the rest of the patch? I > almost wonder if it needs two patches (one to compile the file > regardless of 128-bit support, the other to add new 128-bit shifts); if > not, mentioning it in the commit message doesn't hurt. > Right, I put this thing in a new patch. It's clearer indeed. > > > > +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift) > > Comments on the function contract would be much appreciated (for > example, what range must shift belong to, and the fact that the shift is > modifying the value in-place, and that the result is always zero-extended). OK > > > +{ > > + shift &= 127; > > This says you allow any shift value (whether negative or beyond 127); > either the testsuite must cover this, or you should tighten the contract > and assert that the callers pass a value in range. I prefer to let this function flexible and let the caller decides whether to assert it or not before calling these functions. But I'm totally open to assert it if you prefer. I'm writing the testcase to cover it. > > > + uint64_t h = *phigh >> (shift & 63); > > + if (shift == 0) { > > + return; > > Depending on the compiler, this may waste the work of computing h; maybe > you can float this conditional first. OK > > > + } else if (shift >= 64) { > > + *plow = h; > > + *phigh = 0; > > + } else { > > + *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); > > + *phigh = h; > > + } > > At any rate, the math looks correct. \o/ :D > > > +} > > + > > +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow) > > Again, doc comments are useful, including what overflow represents, and > a repeat of the question on whether a signed shift amount makes sense if > you intend to allow silent truncation of the shift value. OK. About the signed shift I wrote the question above. > > > +{ > > + uint64_t low = *plow; > > + uint64_t high = *phigh; > > + > > + if (shift > 127 && (low | high)) { > > + *overflow = true; > > + } > > + shift &= 127; > > + > > + if (shift == 0) { > > + return; > > + } > > + > > + urshift(&low, &high, 128 - shift); > > + if (low > 0 || high > 0) { > > Can't this be written 'if (low | high)' as above? Oh yeah > > > + *overflow = true; > > + } > > + > > + if (shift >= 64) { > > + *phigh = *plow << (shift & 63); > > + *plow = 0; > > + } else { > > + *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); > > + *plow = *plow << shift; > > + } > > +} > > > > -- > Eric Blake eblake redhat com +1-919-301-3266 > Libvirt virtualization library http://libvirt.org >
On 01/05/2017 03:45 PM, joserz@linux.vnet.ibm.com wrote: >> >>> + { 0, 0, 0ULL, 0, 200, false }, >> >> If you are going to support shifts larger than 127, your testsuite >> should include a shift of a non-zero number. Also, if you are going to >> implicitly truncate the shift value into range, then accepting a signed >> shift might be nicer (as there are cases where it is easier to code a >> shift by -1 than it is a shift by 127). > > Correct me if I'm wrong: Actually the caller can use the function like: > > urshift(low, high, (uint32_t)-1); > > And I'll get "shift == UINT_MAX", which truncates to 127 after "&= 127". > I don't need to use a signed integer necessarily, right? It's not necessary to make the number signed, and in fact, thanks to C implicit promotion rules and qemu's guarantee that we only compile on hardware with twos-complement signed numbers, urshift(low, high, -1) works the same whether the shift parameter is typed as signed or unsigned (without needing an explicit cast). It's just that making it signed instead of unsigned makes it slightly easier to read code by interpreting shifting by -1 as "shift all but the last bit out" (shifting by -2 is "shift all but the last two bits out", etc.), where there is no ambiguity what was meant on shift values down to -127. In contrast, shifting by UINT_MAX is ambiguous to read without further consulting the documentation (is it "shift modulo bit width" or "shift to infinity so that I'm left with 0"?). Or put another way, making the shift amount signed makes it OBVIOUS that you are implicitly masking the shift amount to the maximum width shift (making it perhaps a bit easier to see that shifting by 128 is a no-op, rather than a synonym for making the result 0), while leaving the shift amount unsigned almost argues that you want to assert that the shift amount is in range. >>> +{ >>> + shift &= 127; >> >> This says you allow any shift value (whether negative or beyond 127); >> either the testsuite must cover this, or you should tighten the contract >> and assert that the callers pass a value in range. > > I prefer to let this function flexible and let the caller decides > whether to assert it or not before calling these functions. But I'm > totally open to assert it if you prefer. > > I'm writing the testcase to cover it. At any rate, I'm fine with your decision to state that it is up to the caller to range-check if truncation was not intended, and that the worker function implicitly truncates rather than noisily asserting a range - as long as the v5 patch also includes the documentation and testsuite coverage of this behavior.
diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h index 46187bb..e87de19 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -516,4 +516,7 @@ static inline uint64_t pow2ceil(uint64_t value) return 1ULL << (64 - nlz); } +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift); +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow); + #endif diff --git a/tests/Makefile.include b/tests/Makefile.include index b574964..8ccaa3e 100644 --- a/tests/Makefile.include +++ b/tests/Makefile.include @@ -65,6 +65,8 @@ check-unit-$(CONFIG_POSIX) += tests/test-vmstate$(EXESUF) endif check-unit-y += tests/test-cutils$(EXESUF) gcov-files-test-cutils-y += util/cutils.c +check-unit-y += tests/test-shift128$(EXESUF) +gcov-files-test-shift128-y = util/host-utils.c check-unit-y += tests/test-mul64$(EXESUF) gcov-files-test-mul64-y = util/host-utils.c check-unit-y += tests/test-int128$(EXESUF) @@ -464,7 +466,7 @@ test-obj-y = tests/check-qint.o tests/check-qstring.o tests/check-qdict.o \ tests/test-x86-cpuid.o tests/test-mul64.o tests/test-int128.o \ tests/test-opts-visitor.o tests/test-qmp-event.o \ tests/rcutorture.o tests/test-rcu-list.o \ - tests/test-qdist.o \ + tests/test-qdist.o tests/test-shift128.o \ tests/test-qht.o tests/qht-bench.o tests/test-qht-par.o \ tests/atomic_add-bench.o @@ -572,6 +574,7 @@ tests/test-qmp-commands$(EXESUF): tests/test-qmp-commands.o tests/test-qmp-marsh tests/test-visitor-serialization$(EXESUF): tests/test-visitor-serialization.o $(test-qapi-obj-y) tests/test-opts-visitor$(EXESUF): tests/test-opts-visitor.o $(test-qapi-obj-y) +tests/test-shift128$(EXESUF): tests/test-shift128.o $(test-util-obj-y) tests/test-mul64$(EXESUF): tests/test-mul64.o $(test-util-obj-y) tests/test-bitops$(EXESUF): tests/test-bitops.o $(test-util-obj-y) tests/test-crypto-hash$(EXESUF): tests/test-crypto-hash.o $(test-crypto-obj-y) diff --git a/tests/test-shift128.c b/tests/test-shift128.c new file mode 100644 index 0000000..52be6a2 --- /dev/null +++ b/tests/test-shift128.c @@ -0,0 +1,98 @@ +/* + * Test unsigned left and right shift + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +#include "qemu/osdep.h" +#include "qemu/host-utils.h" + +typedef struct { + uint64_t low; + uint64_t high; + uint64_t rlow; + uint64_t rhigh; + int32_t shift; + bool overflow; +} test_data; + +static const test_data test_ltable[] = { + { 1223ULL, 0, 1223ULL, 0, 0, false }, + { 1ULL, 0, 2ULL, 0, 1, false }, + { 1ULL, 0, 4ULL, 0, 2, false }, + { 1ULL, 0, 16ULL, 0, 4, false }, + { 1ULL, 0, 256ULL, 0, 8, false }, + { 1ULL, 0, 65536ULL, 0, 16, false }, + { 1ULL, 0, 2147483648ULL, 0, 31, false }, + { 1ULL, 0, 35184372088832ULL, 0, 45, false }, + { 1ULL, 0, 1152921504606846976ULL, 0, 60, false }, + { 1ULL, 0, 0, 1ULL, 64, false }, + { 1ULL, 0, 0, 65536ULL, 80, false }, + { 1ULL, 0, 0, 9223372036854775808ULL, 127, false }, + { 0ULL, 1, 0, 0, 64, true }, + { 0x8888888888888888ULL, 0x9999999999999999ULL, + 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true }, + { 0x8888888888888888ULL, 0x9999999999999999ULL, + 0, 0x8888888888888888ULL, 64, true }, + { 0x8ULL, 0, 0, 0x8ULL, 64, false }, + { 0x8ULL, 0, 0, 0x8000000000000000ULL, 124, false }, + { 0x1ULL, 0, 0, 0x4000000000000000ULL, 126, false }, + { 0x1ULL, 0, 0, 0x8000000000000000ULL, 127, false }, + { 0x1ULL, 0, 0x1ULL, 0, 128, true }, + { 0, 0, 0ULL, 0, 200, false }, +}; + +static const test_data test_rtable[] = { + { 1223ULL, 0, 1223ULL, 0, 0, false }, + { 9223372036854775808ULL, 9223372036854775808ULL, + 2147483648L, 2147483648ULL, 32, false }, + { 9223372036854775808ULL, 9223372036854775808ULL, + 9223372036854775808ULL, 0, 64, false }, + { 9223372036854775808ULL, 9223372036854775808ULL, + 36028797018963968ULL, 0, 72, false }, + { 9223372036854775808ULL, 9223372036854775808ULL, + 1ULL, 0, 127, false }, + { 9223372036854775808ULL, 0, 4611686018427387904ULL, 0, 1, false }, + { 9223372036854775808ULL, 0, 2305843009213693952ULL, 0, 2, false }, + { 9223372036854775808ULL, 0, 36028797018963968ULL, 0, 8, false }, + { 9223372036854775808ULL, 0, 140737488355328ULL, 0, 16, false }, + { 9223372036854775808ULL, 0, 2147483648ULL, 0, 32, false }, + { 9223372036854775808ULL, 0, 1ULL, 0, 63, false }, + { 9223372036854775808ULL, 0, 0ULL, 0, 64, false }, +}; + +static void test_lshift(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_ltable); ++i) { + bool overflow = false; + test_data tmp = test_ltable[i]; + ulshift(&tmp.low, &tmp.high, tmp.shift, &overflow); + g_assert_cmpuint(tmp.low, ==, tmp.rlow); + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); + g_assert_cmpuint(tmp.overflow, ==, overflow); + } +} + +static void test_rshift(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_rtable); ++i) { + test_data tmp = test_rtable[i]; + urshift(&tmp.low, &tmp.high, tmp.shift); + g_assert_cmpuint(tmp.low, ==, tmp.rlow); + g_assert_cmpuint(tmp.high, ==, tmp.rhigh); + } +} + +int main(int argc, char **argv) +{ + g_test_init(&argc, &argv, NULL); + g_test_add_func("/host-utils/test_lshift", test_lshift); + g_test_add_func("/host-utils/test_rshift", test_rshift); + return g_test_run(); +} diff --git a/util/Makefile.objs b/util/Makefile.objs index ad0f9c7..39ae26e 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -11,7 +11,7 @@ util-obj-$(CONFIG_POSIX) += memfd.o util-obj-$(CONFIG_WIN32) += oslib-win32.o util-obj-$(CONFIG_WIN32) += qemu-thread-win32.o util-obj-y += envlist.o path.o module.o -util-obj-$(call lnot,$(CONFIG_INT128)) += host-utils.o +util-obj-y += host-utils.o util-obj-y += bitmap.o bitops.o hbitmap.o util-obj-y += fifo8.o util-obj-y += acl.o diff --git a/util/host-utils.c b/util/host-utils.c index b166e57..1ee2433 100644 --- a/util/host-utils.c +++ b/util/host-utils.c @@ -26,6 +26,7 @@ #include "qemu/osdep.h" #include "qemu/host-utils.h" +#ifndef CONFIG_INT128 /* Long integer helpers */ static inline void mul64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b) @@ -158,4 +159,47 @@ int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) return overflow; } +#endif +void urshift(uint64_t *plow, uint64_t *phigh, uint32_t shift) +{ + shift &= 127; + uint64_t h = *phigh >> (shift & 63); + if (shift == 0) { + return; + } else if (shift >= 64) { + *plow = h; + *phigh = 0; + } else { + *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); + *phigh = h; + } +} + +void ulshift(uint64_t *plow, uint64_t *phigh, uint32_t shift, bool *overflow) +{ + uint64_t low = *plow; + uint64_t high = *phigh; + + if (shift > 127 && (low | high)) { + *overflow = true; + } + shift &= 127; + + if (shift == 0) { + return; + } + + urshift(&low, &high, 128 - shift); + if (low > 0 || high > 0) { + *overflow = true; + } + + if (shift >= 64) { + *phigh = *plow << (shift & 63); + *plow = 0; + } else { + *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); + *plow = *plow << shift; + } +}
This commit implements functions to right and left shifts and the unittest for them. Such functions is needed due to instructions that requires them. Today, there is already a right shift implementation in int128.h but it's designed for signed numbers. Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com> --- include/qemu/host-utils.h | 3 ++ tests/Makefile.include | 5 ++- tests/test-shift128.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++ util/Makefile.objs | 2 +- util/host-utils.c | 44 +++++++++++++++++++++ 5 files changed, 150 insertions(+), 2 deletions(-) create mode 100644 tests/test-shift128.c