[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v2 02/22] bitops.h: Implement half-shuffle and half-
From: |
Peter Maydell |
Subject: |
[Qemu-devel] [PATCH v2 02/22] bitops.h: Implement half-shuffle and half-unshuffle ops |
Date: |
Thu, 26 May 2016 15:55:20 +0100 |
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 <address@hidden>
---
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();
}
--
1.9.1
- [Qemu-devel] [PATCH v2 19/22] target-arm/machine.c: Allow user to request GICv3 emulation, (continued)
- [Qemu-devel] [PATCH v2 19/22] target-arm/machine.c: Allow user to request GICv3 emulation, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 11/22] hw/intc/arm_gicv3: Implement GICv3 distributor registers, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 21/22] NOT-FOR-UPSTREAM: kernel: Add definitions for GICv3 attributes, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 16/22] hw/intc/arm_gicv3: Implement gicv3_cpuif_update(), Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 07/22] hw/intc/arm_gicv3: Move irq lines into GICv3CPUState structure, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 04/22] target-arm: Provide hook to tell GICv3 about changes of security state, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 01/22] migration: Define VMSTATE_UINT64_2DARRAY, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 09/22] hw/intc/arm_gicv3: ARM GICv3 device framework, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 03/22] target-arm: Define new arm_is_el3_or_mon() function, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 08/22] hw/intc/arm_gicv3: Add vmstate descriptors, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 02/22] bitops.h: Implement half-shuffle and half-unshuffle ops,
Peter Maydell <=
- [Qemu-devel] [PATCH v2 10/22] hw/intc/arm_gicv3: Implement functions to identify next pending irq, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 05/22] target-arm: Add mp-affinity property for ARM CPU class, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 06/22] hw/intc/arm_gicv3: Add state information, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 18/22] hw/intc/arm_gicv3: Add IRQ handling CPU interface registers, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 12/22] hw/intc/arm_gicv3: Implement GICv3 redistributor registers, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 22/22] RFC: hw/intc/arm_gicv3_kvm: Implement get/put functions, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 15/22] hw/intc/arm_gicv3: Implement GICv3 CPU interface registers, Peter Maydell, 2016/05/26
- [Qemu-devel] [PATCH v2 20/22] target-arm/monitor.c: Advertise emulated GICv3 in capabilities, Peter Maydell, 2016/05/26
- Re: [Qemu-devel] [PATCH v2 00/22] GICv3 emulation, Andrew Jones, 2016/05/30