From patchwork Tue Jun 14 14:38:14 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Maydell X-Patchwork-Id: 9176067 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id AE09F60573 for ; Tue, 14 Jun 2016 15:01:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9F9862656B for ; Tue, 14 Jun 2016 15:01:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9458427E78; Tue, 14 Jun 2016 15:01:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id CB4652656B for ; Tue, 14 Jun 2016 15:01:51 +0000 (UTC) Received: from localhost ([::1]:35900 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bCpqg-0007zE-Vw for patchwork-qemu-devel@patchwork.kernel.org; Tue, 14 Jun 2016 11:01:51 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49655) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bCpUK-0002Tw-1f for qemu-devel@nongnu.org; Tue, 14 Jun 2016 10:38:45 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bCpUI-0005XN-GK for qemu-devel@nongnu.org; Tue, 14 Jun 2016 10:38:43 -0400 Received: from orth.archaic.org.uk ([2001:8b0:1d0::2]:57720) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bCpUH-0005W3-JO for qemu-devel@nongnu.org; Tue, 14 Jun 2016 10:38:42 -0400 Received: from pm215 by orth.archaic.org.uk with local (Exim 4.84_2) (envelope-from ) id 1bCpUA-0006KJ-B0; Tue, 14 Jun 2016 15:38:34 +0100 From: Peter Maydell To: qemu-devel@nongnu.org Date: Tue, 14 Jun 2016 15:38:14 +0100 Message-Id: <1465915112-29272-3-git-send-email-peter.maydell@linaro.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1465915112-29272-1-git-send-email-peter.maydell@linaro.org> References: <1465915112-29272-1-git-send-email-peter.maydell@linaro.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:8b0:1d0::2 Subject: [Qemu-devel] [PATCH v3 02/20] bitops.h: Implement half-shuffle and half-unshuffle ops X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: patches@linaro.org, Shlomo Pongratz , Shlomo Pongratz , Pavel Fedin , Shannon Zhao , Christoffer Dall Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP A half-shuffle operation takes a word with zeros in the high half: 0000 0000 0000 0000 ABCD EFGH IJKL MNOP and spreads the bits out so they are in every other bit of the word: 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N 0O0P A half-unshuffle performs the reverse operation. Provide functions in bitops.h which implement these operations for 32-bit and 64-bit inputs, and add tests for them. Signed-off-by: Peter Maydell Reviewed-by: Shannon Zhao --- include/qemu/bitops.h | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test-bitops.c | 72 +++++++++++++++++++++++++++++++++ 2 files changed, 180 insertions(+) diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h index 755fdd1..15418a8 100644 --- a/include/qemu/bitops.h +++ b/include/qemu/bitops.h @@ -428,4 +428,112 @@ static inline uint64_t deposit64(uint64_t value, int start, int length, return (value & ~mask) | ((fieldval << start) & mask); } +/** + * half_shuffle32: + * @value: 32-bit value (of which only the bottom 16 bits are of interest) + * + * Given an input value: + * xxxx xxxx xxxx xxxx ABCD EFGH IJKL MNOP + * return the value where the bottom 16 bits are spread out into + * the odd bits in the word, and the even bits are zeroed: + * 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N 0O0P + * + * Any bits set in the top half of the input are ignored. + * + * Returns: the shuffled bits. + */ +static inline uint32_t half_shuffle32(uint32_t x) +{ + /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". + * It ignores any bits set in the top half of the input. + */ + x = ((x & 0xFF00) << 8) | (x & 0x00FF); + x = ((x << 4) | x) & 0x0F0F0F0F; + x = ((x << 2) | x) & 0x33333333; + x = ((x << 1) | x) & 0x55555555; + return x; +} + +/** + * half_shuffle64: + * @value: 64-bit value (of which only the bottom 32 bits are of interest) + * + * Given an input value: + * xxxx xxxx xxxx .... xxxx xxxx ABCD EFGH IJKL MNOP QRST UVWX YZab cdef + * return the value where the bottom 32 bits are spread out into + * the odd bits in the word, and the even bits are zeroed: + * 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N .... 0U0V 0W0X 0Y0Z 0a0b 0c0d 0e0f + * + * Any bits set in the top half of the input are ignored. + * + * Returns: the shuffled bits. + */ +static inline uint64_t half_shuffle64(uint64_t x) +{ + /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". + * It ignores any bits set in the top half of the input. + */ + x = ((x & 0xFFFF0000ULL) << 16) | (x & 0xFFFF); + x = ((x << 8) | x) & 0x00FF00FF00FF00FFULL; + x = ((x << 4) | x) & 0x0F0F0F0F0F0F0F0FULL; + x = ((x << 2) | x) & 0x3333333333333333ULL; + x = ((x << 1) | x) & 0x5555555555555555ULL; + return x; +} + +/** + * half_unshuffle32: + * @value: 32-bit value (of which only the odd bits are of interest) + * + * Given an input value: + * xAxB xCxD xExF xGxH xIxJ xKxL xMxN xOxP + * return the value where all the odd bits are compressed down + * into the low half of the word, and the high half is zeroed: + * 0000 0000 0000 0000 ABCD EFGH IJKL MNOP + * + * Any even bits set in the input are ignored. + * + * Returns: the unshuffled bits. + */ +static inline uint32_t half_unshuffle32(uint32_t x) +{ + /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". + * where it is called an inverse half shuffle. + */ + x &= 0x55555555; + x = ((x >> 1) | x) & 0x33333333; + x = ((x >> 2) | x) & 0x0F0F0F0F; + x = ((x >> 4) | x) & 0x00FF00FF; + x = ((x >> 8) | x) & 0x0000FFFF; + return x; +} + +/** + * half_unshuffle64: + * @value: 64-bit value (of which only the odd bits are of interest) + * + * Given an input value: + * xAxB xCxD xExF xGxH xIxJ xKxL xMxN .... xUxV xWxX xYxZ xaxb xcxd xexf + * return the value where all the odd bits are compressed down + * into the low half of the word, and the high half is zeroed: + * 0000 0000 0000 .... 0000 0000 ABCD EFGH IJKL MNOP QRST UVWX YZab cdef + * + * Any even bits set in the input are ignored. + * + * Returns: the unshuffled bits. + */ +static inline uint64_t half_unshuffle64(uint64_t x) +{ + /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". + * where it is called an inverse half shuffle. + */ + x &= 0x5555555555555555ULL; + x = ((x >> 1) | x) & 0x3333333333333333ULL; + x = ((x >> 2) | x) & 0x0F0F0F0F0F0F0F0FULL; + x = ((x >> 4) | x) & 0x00FF00FF00FF00FFULL; + x = ((x >> 8) | x) & 0x0000FFFF0000FFFFULL; + x = ((x >> 16) | x) & 0x00000000FFFFFFFFULL; + return x; +} + #endif diff --git a/tests/test-bitops.c b/tests/test-bitops.c index eb19a36..5a791d2 100644 --- a/tests/test-bitops.c +++ b/tests/test-bitops.c @@ -65,10 +65,82 @@ static void test_sextract64(void) } } +typedef struct { + uint32_t unshuffled; + uint32_t shuffled; +} Shuffle32Test; + +typedef struct { + uint64_t unshuffled; + uint64_t shuffled; +} Shuffle64Test; + +static const Shuffle32Test test_shuffle32_data[] = { + { 0x0000FFFF, 0x55555555 }, + { 0x000081C5, 0x40015011 }, +}; + +static const Shuffle64Test test_shuffle64_data[] = { + { 0x00000000FFFFFFFFULL, 0x5555555555555555ULL }, + { 0x00000000493AB02CULL, 0x1041054445000450ULL }, +}; + +static void test_half_shuffle32(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_shuffle32_data); i++) { + const Shuffle32Test *test = &test_shuffle32_data[i]; + uint32_t r = half_shuffle32(test->unshuffled); + + g_assert_cmpint(r, ==, test->shuffled); + } +} + +static void test_half_shuffle64(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_shuffle64_data); i++) { + const Shuffle64Test *test = &test_shuffle64_data[i]; + uint64_t r = half_shuffle64(test->unshuffled); + + g_assert_cmpint(r, ==, test->shuffled); + } +} + +static void test_half_unshuffle32(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_shuffle32_data); i++) { + const Shuffle32Test *test = &test_shuffle32_data[i]; + uint32_t r = half_unshuffle32(test->shuffled); + + g_assert_cmpint(r, ==, test->unshuffled); + } +} + +static void test_half_unshuffle64(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(test_shuffle64_data); i++) { + const Shuffle64Test *test = &test_shuffle64_data[i]; + uint64_t r = half_unshuffle64(test->shuffled); + + g_assert_cmpint(r, ==, test->unshuffled); + } +} + int main(int argc, char **argv) { g_test_init(&argc, &argv, NULL); g_test_add_func("/bitops/sextract32", test_sextract32); g_test_add_func("/bitops/sextract64", test_sextract64); + g_test_add_func("/bitops/half_shuffle32", test_half_shuffle32); + g_test_add_func("/bitops/half_shuffle64", test_half_shuffle64); + g_test_add_func("/bitops/half_unshuffle32", test_half_unshuffle32); + g_test_add_func("/bitops/half_unshuffle64", test_half_unshuffle64); return g_test_run(); }