host-utils: Implement unsigned quadword left/right shift and unit tests
Implements 128-bit left shift and right shift as well as their
testcases. By design, shift silently mods by 128, so the caller is
responsible to assert the shift range if necessary.
Left shift sets the overflow flag if any non-zero digit is shifted out.
Examples:
ulshift(&low, &high, 250, &overflow);
equivalent: n << 122
urshift(&low, &high, -2);
equivalent: n << 126
Signed-off-by: Jose Ricardo Ziviani <joserz@linux.vnet.ibm.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
[dwg: Added test-shift128 to .gitignore]
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
diff --git a/tests/.gitignore b/tests/.gitignore
index 7357d0a..dc37519 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -69,6 +69,7 @@
test-qobject-output-visitor
test-rcu-list
test-replication
+test-shift128
test-string-input-visitor
test-string-output-visitor
test-thread-pool
diff --git a/tests/Makefile.include b/tests/Makefile.include
index c35fa75..1f6b732 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -65,6 +65,8 @@
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)
@@ -487,7 +489,7 @@
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
@@ -596,6 +598,7 @@
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-bitcnt$(EXESUF): tests/test-bitcnt.o $(test-util-obj-y)
diff --git a/tests/test-shift128.c b/tests/test-shift128.c
new file mode 100644
index 0000000..f3ff736
--- /dev/null
+++ b/tests/test-shift128.c
@@ -0,0 +1,139 @@
+/*
+ * 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[] = {
+ { 0x4C7ULL, 0x0ULL, 0x00000000000004C7ULL,
+ 0x0000000000000000ULL, 0, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000002ULL,
+ 0x0000000000000000ULL, 1, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000004ULL,
+ 0x0000000000000000ULL, 2, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000010ULL,
+ 0x0000000000000000ULL, 4, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000100ULL,
+ 0x0000000000000000ULL, 8, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000010000ULL,
+ 0x0000000000000000ULL, 16, false },
+ { 0x001ULL, 0x0ULL, 0x0000000080000000ULL,
+ 0x0000000000000000ULL, 31, false },
+ { 0x001ULL, 0x0ULL, 0x0000200000000000ULL,
+ 0x0000000000000000ULL, 45, false },
+ { 0x001ULL, 0x0ULL, 0x1000000000000000ULL,
+ 0x0000000000000000ULL, 60, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x0000000000000001ULL, 64, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x0000000000010000ULL, 80, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x8000000000000000ULL, 127, false },
+ { 0x000ULL, 0x1ULL, 0x0000000000000000ULL,
+ 0x0000000000000000ULL, 64, true },
+ { 0x008ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x0000000000000008ULL, 64, false },
+ { 0x008ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x8000000000000000ULL, 124, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x4000000000000000ULL, 126, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x8000000000000000ULL, 127, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000001ULL,
+ 0x0000000000000000ULL, 128, false },
+ { 0x000ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x0000000000000000ULL, 200, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x0000000000000100ULL, 200, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x8000000000000000ULL, -1, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x8000000000000000ULL, INT32_MAX, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x4000000000000000ULL, -2, false },
+ { 0x001ULL, 0x0ULL, 0x0000000000000000ULL,
+ 0x4000000000000000ULL, INT32_MAX - 1, false },
+ { 0x8888888888888888ULL, 0x9999999999999999ULL,
+ 0x8000000000000000ULL, 0x9888888888888888ULL, 60, true },
+ { 0x8888888888888888ULL, 0x9999999999999999ULL,
+ 0x0000000000000000ULL, 0x8888888888888888ULL, 64, true },
+};
+
+static const test_data test_rtable[] = {
+ { 0x00000000000004C7ULL, 0x0ULL, 0x00000000000004C7ULL, 0x0ULL, 0, false },
+ { 0x0800000000000000ULL, 0x0ULL, 0x0400000000000000ULL, 0x0ULL, 1, false },
+ { 0x0800000000000000ULL, 0x0ULL, 0x0200000000000000ULL, 0x0ULL, 2, false },
+ { 0x0800000000000000ULL, 0x0ULL, 0x0008000000000000ULL, 0x0ULL, 8, false },
+ { 0x0800000000000000ULL, 0x0ULL, 0x0000080000000000ULL, 0x0ULL, 16, false },
+ { 0x0800000000000000ULL, 0x0ULL, 0x0000000008000000ULL, 0x0ULL, 32, false },
+ { 0x8000000000000000ULL, 0x0ULL, 0x0000000000000001ULL, 0x0ULL, 63, false },
+ { 0x8000000000000000ULL, 0x0ULL, 0x0000000000000000ULL, 0x0ULL, 64, false },
+ { 0x0000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000000000000ULL, 0x8000000000000000ULL, 128, false },
+ { 0x0000000000000000ULL, 0x8000000000000000ULL,
+ 0x0080000000000000ULL, 0x0000000000000000ULL, 200, false },
+ { 0x0000000000000000ULL, 0x0000000000000000ULL,
+ 0x0000000000000000ULL, 0x0000000000000000ULL, 200, false },
+ { 0x0000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000000000000ULL, 0x0000000000000080ULL, -200, false },
+ { 0x8000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000080000000ULL, 0x0000000080000000ULL, 32, false },
+ { 0x0800000000000000ULL, 0x0800000000000000ULL,
+ 0x0800000000000000ULL, 0x0000000000000000ULL, 64, false },
+ { 0x0800000000000000ULL, 0x0800000000000000ULL,
+ 0x0008000000000000ULL, 0x0000000000000000ULL, 72, false },
+ { 0x8000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000000000001ULL, 0x0000000000000000ULL, 127, false },
+ { 0x0000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000000000001ULL, 0x0000000000000000ULL, -1, false },
+ { 0x0000000000000000ULL, 0x8000000000000000ULL,
+ 0x0000000000000002ULL, 0x0000000000000000ULL, -2, 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();
+}
