From patchwork Thu Jul 4 15:12:57 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 256967 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 118F42C0095 for ; Fri, 5 Jul 2013 02:26:29 +1000 (EST) Received: from localhost ([::1]:43844 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UulGp-0002PP-5z for incoming@patchwork.ozlabs.org; Thu, 04 Jul 2013 11:16:31 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:44231) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UulEc-0007f5-Ty for qemu-devel@nongnu.org; Thu, 04 Jul 2013 11:14:19 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UulEa-0004p8-QC for qemu-devel@nongnu.org; Thu, 04 Jul 2013 11:14:14 -0400 Received: from mail-wg0-x234.google.com ([2a00:1450:400c:c00::234]:45838) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UulEa-0004oo-Gx for qemu-devel@nongnu.org; Thu, 04 Jul 2013 11:14:12 -0400 Received: by mail-wg0-f52.google.com with SMTP id b12so1236708wgh.19 for ; Thu, 04 Jul 2013 08:14:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:subject:date:message-id:x-mailer:in-reply-to :references; bh=lTOqDXrmy/lS3UvfQTAapdWf/YGKVoWcIthCz66c6hw=; b=t4xyR3NMAb3kh3v9g2/V/9ql17m379oZXGniCgqaslpN5VcQa8zgSlEAz0GQ5Ej4ES hH11h7X/gmQFhkYFCW8PjuHQ+lzhyeIbqi9M+pDuqSf6m19U0llTQM4pTyItU46iAPvn 9zcv5c+a89oMF5hZcKDSzaDhEVkFWJfhbJJRzaNNn2XmmcVXE2gykZNi33hx2vbslGiG nLKqjDH+MJxxlV7pHzV5Uf8hd0w+XpO1Gi3kAn0O3b6Syfqog78nsv5TYTAPJCY0Lb7X hjzpkxIhmHVQVhWETa7a7wGrl+gix04aAUau9LQNb/j7tuj2B0tQu0SU2jFgRrk0Y212 7SZA== X-Received: by 10.194.63.46 with SMTP id d14mr3859957wjs.81.1372950851832; Thu, 04 Jul 2013 08:14:11 -0700 (PDT) Received: from playground.station (net-37-117-148-210.cust.dsl.vodafone.it. [37.117.148.210]) by mx.google.com with ESMTPSA id d8sm4212546wiz.0.2013.07.04.08.14.09 for (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Thu, 04 Jul 2013 08:14:10 -0700 (PDT) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Thu, 4 Jul 2013 17:12:57 +0200 Message-Id: <1372950842-32422-2-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.1.4 In-Reply-To: <1372950842-32422-1-git-send-email-pbonzini@redhat.com> References: <1372950842-32422-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c00::234 Subject: [Qemu-devel] [PATCH 01/66] int128: optimize and add test cases X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org 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 --- 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 +#include +#include + 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..5aca032 --- /dev/null +++ b/tests/test-int128.c @@ -0,0 +1,212 @@ +/* + * Test Int128 arithmetic + * + * 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 +#include +#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(); +}