* [Qemu-devel] [PATCH v2] int128: optimize and add test cases
@ 2013-06-21 7:48 Paolo Bonzini
2013-06-21 15:10 ` Richard Henderson
0 siblings, 1 reply; 3+ messages in thread
From: Paolo Bonzini @ 2013-06-21 7:48 UTC (permalink / raw)
To: qemu-devel; +Cc: peter.maydell, rth
For add, the carry only requires checking one of the arguments.
For sub and neg, we can similarly optimize computation of the
carry.
For ge, we can just do lexicographic order.
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
include/qemu/int128.h | 25 ++++--
tests/Makefile | 6 +-
tests/test-int128.c | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 234 insertions(+), 9 deletions(-)
create mode 100644 tests/test-int128.c
diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index bfe7678..9ed47aa 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -1,6 +1,10 @@
#ifndef INT128_H
#define INT128_H
+#include <assert.h>
+#include <stdint.h>
+#include <stdbool.h>
+
typedef struct Int128 Int128;
struct Int128 {
@@ -55,21 +59,26 @@ static inline Int128 int128_rshift(Int128 a, int n)
static inline Int128 int128_add(Int128 a, Int128 b)
{
- Int128 r = { a.lo + b.lo, a.hi + b.hi };
- r.hi += (r.lo < a.lo) || (r.lo < b.lo);
- return r;
+ uint64_t lo = a.lo + b.lo;
+
+ /* a.lo <= a.lo + b.lo < a.lo + k (k is the base, 2^64). Hence,
+ * a.lo + b.lo >= k implies 0 <= lo = a.lo + b.lo - k < a.lo.
+ * Similarly, a.lo + b.lo < k implies a.lo <= lo = a.lo + b.lo < k.
+ *
+ * So the carry is lo < a.lo.
+ */
+ return (Int128) { lo, (uint64_t)a.hi + b.hi + (lo < a.lo) };
}
static inline Int128 int128_neg(Int128 a)
{
- a.lo = ~a.lo;
- a.hi = ~a.hi;
- return int128_add(a, int128_one());
+ uint64_t lo = -a.lo;
+ return (Int128) { lo, ~(uint64_t)a.hi + !lo };
}
static inline Int128 int128_sub(Int128 a, Int128 b)
{
- return int128_add(a, int128_neg(b));
+ return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
}
static inline bool int128_nonneg(Int128 a)
@@ -89,7 +98,7 @@ static inline bool int128_ne(Int128 a, Int128 b)
static inline bool int128_ge(Int128 a, Int128 b)
{
- return int128_nonneg(int128_sub(a, b));
+ return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo);
}
static inline bool int128_lt(Int128 a, Int128 b)
diff --git a/tests/Makefile b/tests/Makefile
index c107489..279d5f8 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -44,6 +44,9 @@ check-unit-y += tests/test-cutils$(EXESUF)
gcov-files-test-cutils-y += util/cutils.c
check-unit-y += tests/test-mul64$(EXESUF)
gcov-files-test-mul64-y = util/host-utils.c
+check-unit-y += tests/test-int128$(EXESUF)
+# all code tested by test-int128 is inside int128.h
+gcov-files-test-int128-y =
check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
@@ -75,7 +78,7 @@ test-obj-y = tests/check-qint.o tests/check-qstring.o tests/check-qdict.o \
tests/test-string-input-visitor.o tests/test-qmp-output-visitor.o \
tests/test-qmp-input-visitor.o tests/test-qmp-input-strict.o \
tests/test-qmp-commands.o tests/test-visitor-serialization.o \
- tests/test-x86-cpuid.o tests/test-mul64.o
+ tests/test-x86-cpuid.o tests/test-mul64.o tests/test-int128.o
test-qapi-obj-y = tests/test-qapi-visit.o tests/test-qapi-types.o
@@ -98,6 +101,7 @@ tests/test-hbitmap$(EXESUF): tests/test-hbitmap.o libqemuutil.a libqemustub.a
tests/test-x86-cpuid$(EXESUF): tests/test-x86-cpuid.o
tests/test-xbzrle$(EXESUF): tests/test-xbzrle.o xbzrle.o page_cache.o libqemuutil.a
tests/test-cutils$(EXESUF): tests/test-cutils.o util/cutils.o
+tests/test-int128$(EXESUF): tests/test-int128.o
tests/test-qapi-types.c tests/test-qapi-types.h :\
$(SRC_PATH)/qapi-schema-test.json $(SRC_PATH)/scripts/qapi-types.py
diff --git a/tests/test-int128.c b/tests/test-int128.c
new file mode 100644
index 0000000..c2ec740
--- /dev/null
+++ b/tests/test-int128.c
@@ -0,0 +1,212 @@
+/*
+ * Test 64x64 -> 128 multiply subroutines
+ *
+ * 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 <glib.h>
+#include <stdio.h>
+#include "qemu/int128.h"
+#include "qemu/osdep.h"
+
+static uint32_t tests[8] = {
+ 0x00000000, 0x00000001, 0x7FFFFFFE, 0x7FFFFFFF,
+ 0x80000000, 0x80000001, 0xFFFFFFFE, 0xFFFFFFFF,
+};
+
+#define LOW 3ULL
+#define HIGH (1ULL << 63)
+#define MIDDLE (-1ULL & ~LOW & ~HIGH)
+
+static uint64_t expand16(unsigned x)
+{
+ return (x & LOW) | ((x & 4) ? MIDDLE : 0) | (x & 0x8000 ? HIGH : 0);
+}
+
+static Int128 expand(uint32_t x)
+{
+ uint64_t l, h;
+ l = expand16(x & 65535);
+ h = expand16(x >> 16);
+ return (Int128) {l, h};
+};
+
+static void test_and(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ Int128 a = expand(tests[i]);
+ Int128 b = expand(tests[j]);
+ Int128 r = expand(tests[i] & tests[j]);
+ Int128 s = int128_and(a, b);
+ g_assert_cmpuint(r.lo, ==, s.lo);
+ g_assert_cmpuint(r.hi, ==, s.hi);
+ }
+ }
+}
+
+static void test_add(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ Int128 a = expand(tests[i]);
+ Int128 b = expand(tests[j]);
+ Int128 r = expand(tests[i] + tests[j]);
+ Int128 s = int128_add(a, b);
+ g_assert_cmpuint(r.lo, ==, s.lo);
+ g_assert_cmpuint(r.hi, ==, s.hi);
+ }
+ }
+}
+
+static void test_sub(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ Int128 a = expand(tests[i]);
+ Int128 b = expand(tests[j]);
+ Int128 r = expand(tests[i] - tests[j]);
+ Int128 s = int128_sub(a, b);
+ g_assert_cmpuint(r.lo, ==, s.lo);
+ g_assert_cmpuint(r.hi, ==, s.hi);
+ }
+ }
+}
+
+static void test_neg(void)
+{
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ Int128 a = expand(tests[i]);
+ Int128 r = expand(-tests[i]);
+ Int128 s = int128_neg(a);
+ g_assert_cmpuint(r.lo, ==, s.lo);
+ g_assert_cmpuint(r.hi, ==, s.hi);
+ }
+}
+
+static void test_nz(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ Int128 a = expand(tests[i]);
+ g_assert_cmpuint(int128_nz(a), ==, tests[i] != 0);
+ }
+ }
+}
+
+static void test_le(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ /* Signed comparison */
+ int32_t a = (int32_t) tests[i];
+ int32_t b = (int32_t) tests[j];
+ g_assert_cmpuint(int128_le(expand(a), expand(b)), ==, a <= b);
+ }
+ }
+}
+
+static void test_lt(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ /* Signed comparison */
+ int32_t a = (int32_t) tests[i];
+ int32_t b = (int32_t) tests[j];
+ g_assert_cmpuint(int128_lt(expand(a), expand(b)), ==, a < b);
+ }
+ }
+}
+
+static void test_ge(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ /* Signed comparison */
+ int32_t a = (int32_t) tests[i];
+ int32_t b = (int32_t) tests[j];
+ g_assert_cmpuint(int128_ge(expand(a), expand(b)), ==, a >= b);
+ }
+ }
+}
+
+static void test_gt(void)
+{
+ int i, j;
+
+ for (i = 0; i < ARRAY_SIZE(tests); ++i) {
+ for (j = 0; j < ARRAY_SIZE(tests); ++j) {
+ /* Signed comparison */
+ int32_t a = (int32_t) tests[i];
+ int32_t b = (int32_t) tests[j];
+ g_assert_cmpuint(int128_gt(expand(a), expand(b)), ==, a > b);
+ }
+ }
+}
+
+/* Make sure to test undefined behavior at runtime! */
+
+static void __attribute__((__noinline__, __noclone__))
+test_rshift_one(uint32_t x, int n, uint64_t h, uint64_t l)
+{
+ Int128 a = expand(x);
+ Int128 r = int128_rshift(a, n);
+ g_assert_cmpuint(r.lo, ==, l);
+ g_assert_cmpuint(r.hi, ==, h);
+}
+
+static void test_rshift(void)
+{
+ test_rshift_one(0x00010000U, 64, 0x0000000000000000ULL, 0x0000000000000001ULL);
+ test_rshift_one(0x80010000U, 64, 0xFFFFFFFFFFFFFFFFULL, 0x8000000000000001ULL);
+ test_rshift_one(0x7FFE0000U, 64, 0x0000000000000000ULL, 0x7FFFFFFFFFFFFFFEULL);
+ test_rshift_one(0xFFFE0000U, 64, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL);
+ test_rshift_one(0x00010000U, 60, 0x0000000000000000ULL, 0x0000000000000010ULL);
+ test_rshift_one(0x80010000U, 60, 0xFFFFFFFFFFFFFFF8ULL, 0x0000000000000010ULL);
+ test_rshift_one(0x00018000U, 60, 0x0000000000000000ULL, 0x0000000000000018ULL);
+ test_rshift_one(0x80018000U, 60, 0xFFFFFFFFFFFFFFF8ULL, 0x0000000000000018ULL);
+ test_rshift_one(0x7FFE0000U, 60, 0x0000000000000007ULL, 0xFFFFFFFFFFFFFFE0ULL);
+ test_rshift_one(0xFFFE0000U, 60, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFE0ULL);
+ test_rshift_one(0x7FFE8000U, 60, 0x0000000000000007ULL, 0xFFFFFFFFFFFFFFE8ULL);
+ test_rshift_one(0xFFFE8000U, 60, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFE8ULL);
+ test_rshift_one(0x00018000U, 0, 0x0000000000000001ULL, 0x8000000000000000ULL);
+ test_rshift_one(0x80018000U, 0, 0x8000000000000001ULL, 0x8000000000000000ULL);
+ test_rshift_one(0x7FFE0000U, 0, 0x7FFFFFFFFFFFFFFEULL, 0x0000000000000000ULL);
+ test_rshift_one(0xFFFE0000U, 0, 0xFFFFFFFFFFFFFFFEULL, 0x0000000000000000ULL);
+ test_rshift_one(0x7FFE8000U, 0, 0x7FFFFFFFFFFFFFFEULL, 0x8000000000000000ULL);
+ test_rshift_one(0xFFFE8000U, 0, 0xFFFFFFFFFFFFFFFEULL, 0x8000000000000000ULL);
+}
+
+int main(int argc, char **argv)
+{
+ g_test_init(&argc, &argv, NULL);
+ g_test_add_func("/int128/int128_and", test_and);
+ g_test_add_func("/int128/int128_add", test_add);
+ g_test_add_func("/int128/int128_sub", test_sub);
+ g_test_add_func("/int128/int128_neg", test_neg);
+ g_test_add_func("/int128/int128_nz", test_nz);
+ g_test_add_func("/int128/int128_le", test_le);
+ g_test_add_func("/int128/int128_lt", test_lt);
+ g_test_add_func("/int128/int128_ge", test_ge);
+ g_test_add_func("/int128/int128_gt", test_gt);
+ g_test_add_func("/int128/int128_rshift", test_rshift);
+ return g_test_run();
+}
--
1.8.1.4
^ permalink raw reply related [flat|nested] 3+ messages in thread* Re: [Qemu-devel] [PATCH v2] int128: optimize and add test cases
2013-06-21 7:48 [Qemu-devel] [PATCH v2] int128: optimize and add test cases Paolo Bonzini
@ 2013-06-21 15:10 ` Richard Henderson
2013-06-21 21:59 ` Paolo Bonzini
0 siblings, 1 reply; 3+ messages in thread
From: Richard Henderson @ 2013-06-21 15:10 UTC (permalink / raw)
To: Paolo Bonzini; +Cc: peter.maydell, qemu-devel
On 06/21/2013 12:48 AM, Paolo Bonzini wrote:
> --- /dev/null
> +++ b/tests/test-int128.c
> @@ -0,0 +1,212 @@
> +/*
> + * Test 64x64 -> 128 multiply subroutines
Cutnpaste test description. Otherwise,
Reviewed-by: Richard Henderson <rth@twiddle.net>
r~
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [Qemu-devel] [PATCH v2] int128: optimize and add test cases
2013-06-21 15:10 ` Richard Henderson
@ 2013-06-21 21:59 ` Paolo Bonzini
0 siblings, 0 replies; 3+ messages in thread
From: Paolo Bonzini @ 2013-06-21 21:59 UTC (permalink / raw)
To: Richard Henderson; +Cc: peter.maydell, qemu-devel
Il 21/06/2013 17:10, Richard Henderson ha scritto:
> On 06/21/2013 12:48 AM, Paolo Bonzini wrote:
>> --- /dev/null
>> +++ b/tests/test-int128.c
>> @@ -0,0 +1,212 @@
>> +/*
>> + * Test 64x64 -> 128 multiply subroutines
>
> Cutnpaste test description. Otherwise,
>
> Reviewed-by: Richard Henderson <rth@twiddle.net>
Ok, I'll fix it and add it to my queue.
Paolo
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2013-06-21 21:59 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-06-21 7:48 [Qemu-devel] [PATCH v2] int128: optimize and add test cases Paolo Bonzini
2013-06-21 15:10 ` Richard Henderson
2013-06-21 21:59 ` Paolo Bonzini
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).