diff options
| -rw-r--r-- | include/qemu/bitops.h | 108 | ||||
| -rw-r--r-- | tests/test-bitops.c | 72 |
2 files changed, 180 insertions, 0 deletions
diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h index 755fdd1293..15418a86df 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 eb19a36a36..5a791d2e17 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(); } |