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: 67358 Delivered-To: patches@linaro.org Received: by 10.140.92.199 with SMTP id b65csp1708502qge; Mon, 9 May 2016 10:30:18 -0700 (PDT) X-Received: by 10.194.93.2 with SMTP id cq2mr37140867wjb.151.1462815000185; Mon, 09 May 2016 10:30:00 -0700 (PDT) Return-Path: Received: from orth.archaic.org.uk (orth.archaic.org.uk. [2001:8b0:1d0::2]) by mx.google.com with ESMTPS id h201si27055111wme.86.2016.05.09.10.29.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 09 May 2016 10:30:00 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of pm215@archaic.org.uk designates 2001:8b0:1d0::2 as permitted sender) client-ip=2001:8b0:1d0::2; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of pm215@archaic.org.uk designates 2001:8b0:1d0::2 as permitted sender) smtp.mailfrom=pm215@archaic.org.uk; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org 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 Cc: patches@linaro.org, Pavel Fedin , Shlomo Pongratz , Shlomo Pongratz , Christoffer Dall , Shannon Zhao Subject: [PATCH 02/23] bitops.h: Implement half-shuffle and half-unshuffle ops 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> 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(+) -- 1.9.1 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(); }