From patchwork Mon May 9 17:29:28 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Maydell X-Patchwork-Id: 620018 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)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3r3V2g61mrz9s9n for ; Tue, 10 May 2016 03:37:47 +1000 (AEST) Received: from localhost ([::1]:42558 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1azp7p-00020u-Oq for incoming@patchwork.ozlabs.org; Mon, 09 May 2016 13:37:45 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38355) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1azp0t-0004Uy-Bo for qemu-devel@nongnu.org; Mon, 09 May 2016 13:30:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1azp0q-0000PT-MB for qemu-devel@nongnu.org; Mon, 09 May 2016 13:30:34 -0400 Received: from orth.archaic.org.uk ([2001:8b0:1d0::2]:56751) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1azp0k-00005k-Hc; Mon, 09 May 2016 13:30:26 -0400 Received: from pm215 by orth.archaic.org.uk with local (Exim 4.84_2) (envelope-from ) id 1azp0B-0001Qz-Kj; Mon, 09 May 2016 18:29:51 +0100 From: Peter Maydell To: qemu-arm@nongnu.org, qemu-devel@nongnu.org Date: Mon, 9 May 2016 18:29:28 +0100 Message-Id: <1462814989-24360-3-git-send-email-peter.maydell@linaro.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1462814989-24360-1-git-send-email-peter.maydell@linaro.org> References: <1462814989-24360-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 02/23] 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" 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 --- include/qemu/bitops.h | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test-bitops.c | 68 +++++++++++++++++++++++++++++++ 2 files changed, 176 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 5050950..353fc98 100644 --- a/tests/test-bitops.c +++ b/tests/test-bitops.c @@ -66,10 +66,78 @@ 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(); }