Re: [Qemu-ppc] [PATCH v4 1/6] target-ppc: Implement unsigned quadword left/right shift and unit tests

[joserz]

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 <address@hidden>
> > ---
> >  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