qemu-arm
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Qemu-arm] [Qemu-devel] [PATCH v2 02/22] bitops.h: Implement half-sh


From: Shannon Zhao
Subject: Re: [Qemu-arm] [Qemu-devel] [PATCH v2 02/22] bitops.h: Implement half-shuffle and half-unshuffle ops
Date: Tue, 7 Jun 2016 14:35:29 +0800
User-agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.4.0


On 2016/5/26 22:55, Peter Maydell wrote:
> 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;blank line
> +
> +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;
Miss blank line here and below.
Otherwise,
Reviewed-by: Shannon Zhao <address@hidden>

> +    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();
>  }
> 

-- 
Shannon




reply via email to

[Prev in Thread] Current Thread [Next in Thread]