diff mbox series

[v4,2/2] eal: provide leading and trailing zero bit count abstraction

Message ID 1673285784-14394-3-git-send-email-roretzla@linux.microsoft.com (mailing list archive)
State Superseded, archived
Delegated to: Thomas Monjalon
Headers
Series eal: provide leading and trailing zero bit count abstraction |

Checks

Context Check Description
ci/checkpatch warning coding style issues
ci/loongarch-compilation success Compilation OK
ci/loongarch-unit-testing success Unit Testing PASS
ci/iol-intel-Functional success Functional Testing PASS
ci/iol-broadcom-Performance success Performance Testing PASS
ci/iol-mellanox-Performance success Performance Testing PASS
ci/iol-intel-Performance success Performance Testing PASS
ci/github-robot: build success github build: passed
ci/iol-aarch64-unit-testing success Testing PASS
ci/iol-testing success Testing PASS
ci/iol-x86_64-unit-testing success Testing PASS
ci/iol-abi-testing success Testing PASS
ci/iol-x86_64-compile-testing success Testing PASS
ci/iol-aarch64-compile-testing success Testing PASS
ci/Intel-compilation success Compilation OK
ci/intel-Testing success Testing PASS

Commit Message

Tyler Retzlaff Jan. 9, 2023, 5:36 p.m. UTC 
  From: Tyler Retzlaff <roretzla@microsoft.com>

Provide an abstraction for leading and trailing zero bit counting
functions to hide compiler specific intrinsics and builtins.

Include basic unit test of following functions added.

    rte_clz32
    rte_clz64
    rte_ctz32
    rte_ctz64

Signed-off-by: Tyler Retzlaff <roretzla@linux.microsoft.com>
---
 app/test/meson.build         |   2 +
 app/test/test_bitcount.c     |  71 ++++++++++++++++++
 lib/eal/include/rte_bitops.h | 168 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 241 insertions(+)
 create mode 100644 app/test/test_bitcount.c

Comments

Ferruh Yigit Jan. 10, 2023, 1:55 p.m. UTC | #1 
On 1/9/2023 5:36 PM, Tyler Retzlaff wrote:
> From: Tyler Retzlaff <roretzla@microsoft.com>
> 
> Provide an abstraction for leading and trailing zero bit counting
> functions to hide compiler specific intrinsics and builtins.
> 
> Include basic unit test of following functions added.
> 
>     rte_clz32
>     rte_clz64
>     rte_ctz32
>     rte_ctz64
> 
> Signed-off-by: Tyler Retzlaff <roretzla@linux.microsoft.com>
> ---
>  app/test/meson.build         |   2 +
>  app/test/test_bitcount.c     |  71 ++++++++++++++++++
>  lib/eal/include/rte_bitops.h | 168 +++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 241 insertions(+)
>  create mode 100644 app/test/test_bitcount.c
> 
> diff --git a/app/test/meson.build b/app/test/meson.build
> index f34d19e..d1277bc 100644
> --- a/app/test/meson.build
> +++ b/app/test/meson.build
> @@ -13,6 +13,7 @@ test_sources = files(
>          'test_alarm.c',
>          'test_atomic.c',
>          'test_barrier.c',
> +        'test_bitcount.c',
>          'test_bitops.c',
>          'test_bitmap.c',
>          'test_bpf.c',
> @@ -160,6 +161,7 @@ test_deps += ['bus_pci', 'bus_vdev']
>  fast_tests = [
>          ['acl_autotest', true, true],
>          ['atomic_autotest', false, true],
> +        ['bitcount_autotest', true, true],
>          ['bitmap_autotest', true, true],
>          ['bpf_autotest', true, true],
>          ['bpf_convert_autotest', true, true],
> diff --git a/app/test/test_bitcount.c b/app/test/test_bitcount.c
> new file mode 100644
> index 0000000..36eb05c
> --- /dev/null
> +++ b/app/test/test_bitcount.c
> @@ -0,0 +1,71 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright (C) 2022 Microsoft Corporation
> + */
> +
> +#include <string.h>
> +
> +#include <rte_bitops.h>
> +#include <rte_debug.h>
> +
> +#include "test.h"
> +
> +RTE_LOG_REGISTER(bitcount_logtype_test, test.bitcount, INFO);
> +
> +static int
> +test_clz32(void)
> +{
> +	uint32_t v = 1;
> +	RTE_TEST_ASSERT(rte_clz32(v) == sizeof(v) * CHAR_BIT - 1,
> +	    "Unexpected count.");
> +
> +	return 0;
> +}
> +
> +static int
> +test_clz64(void)
> +{
> +	uint64_t v = 1;
> +	RTE_TEST_ASSERT(rte_clz64(v) == sizeof(v) * CHAR_BIT - 1,
> +	    "Unexpected count.");
> +
> +	return 0;
> +}
> +
> +static int
> +test_ctz32(void)
> +{
> +	uint32_t v = 2;
> +	RTE_TEST_ASSERT(rte_ctz32(v) == 1, "Unexpected count.");
> +
> +	return 0;
> +}
> +
> +static int
> +test_ctz64(void)
> +{
> +	uint64_t v = 2;
> +	RTE_TEST_ASSERT(rte_ctz64(v) == 1, "Unexpected count.");
> +
> +	return 0;
> +}
> +
> +static struct unit_test_suite bitcount_test_suite = {
> +	.suite_name = "bitcount autotest",
> +	.setup = NULL,
> +	.teardown = NULL,
> +	.unit_test_cases = {
> +		TEST_CASE(test_clz32),
> +		TEST_CASE(test_clz64),
> +		TEST_CASE(test_ctz32),
> +		TEST_CASE(test_ctz64),
> +		TEST_CASES_END()
> +	}
> +};
> +
> +static int
> +test_bitcount(void)
> +{
> +	return unit_test_suite_runner(&bitcount_test_suite);
> +}
> +
> +REGISTER_TEST_COMMAND(bitcount_autotest, test_bitcount);
> diff --git a/lib/eal/include/rte_bitops.h b/lib/eal/include/rte_bitops.h
> index 531479e..387d7aa 100644
> --- a/lib/eal/include/rte_bitops.h
> +++ b/lib/eal/include/rte_bitops.h
> @@ -1,5 +1,7 @@
>  /* SPDX-License-Identifier: BSD-3-Clause
>   * Copyright(c) 2020 Arm Limited
> + * Copyright(c) 2010-2019 Intel Corporation
> + * Copyright(c) 2023 Microsoft Corporation
>   */
>  
>  #ifndef _RTE_BITOPS_H_
> @@ -275,6 +277,172 @@
>  	return val & mask;
>  }
>  
> +#ifdef RTE_TOOLCHAIN_MSVC
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of leading 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of leading zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_clz32(uint32_t v)
> +{
> +	unsigned long rv;
> +
> +	(void)_BitScanReverse(&rv, v);
> +
> +	return (unsigned int)rv;
> +}


OK, this looks wrong to me,


'_BitScanReverse' is [1]:
"Search the mask data from most significant bit (MSB) to least
significant bit (LSB) for a set bit (1)."

As far as I can see index starts from zero and from lsb to msb.

So _BitScanReverse() returns following index values:
0x2 => 1
0xffffffff => 31

If above is correct, above function doesn't return number of leading
zeros, but it should return "31 - (unsigned int)rv".

Please check godbolt experiment for above:
https://godbolt.org/z/znYn54f57


As far as I can see unit test is correct, so above should fail with
windows compiler, and I assume you run unit test with windows compiler,
so probably I am missing something but please help me understand.



[1]
https://learn.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=msvc-170

> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of leading 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of leading zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_clz64(uint64_t v)
> +{
> +	unsigned long rv;
> +
> +	(void)_BitScanReverse64(&rv, v);
> +
> +	return (unsigned int)rv;
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of trailing 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of trailing zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_ctz32(uint32_t v)
> +{
> +	unsigned long rv;
> +
> +	(void)_BitScanForward(&rv, v);
> +
> +	return (unsigned int)rv;
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of trailing 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of trailing zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_ctz64(uint64_t v)
> +{
> +	unsigned long rv;
> +
> +	(void)_BitScanForward64(&rv, v);
> +
> +	return (unsigned int)rv;
> +}
> +
> +#else
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of leading 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of leading zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_clz32(uint32_t v)
> +{
> +	return (unsigned int)__builtin_clz(v);
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of leading 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of leading zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_clz64(uint64_t v)
> +{
> +	return (unsigned int)__builtin_clzll(v);
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of trailing 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of trailing zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_ctz32(uint32_t v)
> +{
> +	return (unsigned int)__builtin_ctz(v);
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> + *
> + * Get the count of trailing 0-bits in v.
> + *
> + * @param v
> + *   The value.
> + * @return
> + *   The count of trailing zero bits.
> + */
> +__rte_experimental
> +static inline unsigned int
> +rte_ctz64(uint64_t v)
> +{
> +	return (unsigned int)__builtin_ctzll(v);
> +}

'rte_ctz32()' & 'rte_ctz64()' are practically exact same with
'rte_bsf32()' & 'rte_bsf64()',

Although I can see description is different, do we need same
functionality with new function name,
why not add 'rte_bsf32()' & 'rte_bsf64()' versions for the Windows?



btw, do you guys know what 'bsf' & 'fls' (rte_fls_u32) stands for?

> +
> +#endif
> +
>  /**
>   * Combines 32b inputs most significant set bits into the least
>   * significant bits to construct a value with the same MSBs as x
Tyler Retzlaff Jan. 10, 2023, 5:34 p.m. UTC | #2 
On Tue, Jan 10, 2023 at 01:55:59PM +0000, Ferruh Yigit wrote:
> On 1/9/2023 5:36 PM, Tyler Retzlaff wrote:
> > From: Tyler Retzlaff <roretzla@microsoft.com>
> > 
> > Provide an abstraction for leading and trailing zero bit counting
> > functions to hide compiler specific intrinsics and builtins.
> > 
> > Include basic unit test of following functions added.
> > 
> >     rte_clz32
> >     rte_clz64
> >     rte_ctz32
> >     rte_ctz64
> > 
> > Signed-off-by: Tyler Retzlaff <roretzla@linux.microsoft.com>
> > ---
> >  app/test/meson.build         |   2 +
> >  app/test/test_bitcount.c     |  71 ++++++++++++++++++
> >  lib/eal/include/rte_bitops.h | 168 +++++++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 241 insertions(+)
> >  create mode 100644 app/test/test_bitcount.c
> > 
> > diff --git a/app/test/meson.build b/app/test/meson.build
> > index f34d19e..d1277bc 100644
> > --- a/app/test/meson.build
> > +++ b/app/test/meson.build
> > @@ -13,6 +13,7 @@ test_sources = files(
> >          'test_alarm.c',
> >          'test_atomic.c',
> >          'test_barrier.c',
> > +        'test_bitcount.c',
> >          'test_bitops.c',
> >          'test_bitmap.c',
> >          'test_bpf.c',
> > @@ -160,6 +161,7 @@ test_deps += ['bus_pci', 'bus_vdev']
> >  fast_tests = [
> >          ['acl_autotest', true, true],
> >          ['atomic_autotest', false, true],
> > +        ['bitcount_autotest', true, true],
> >          ['bitmap_autotest', true, true],
> >          ['bpf_autotest', true, true],
> >          ['bpf_convert_autotest', true, true],
> > diff --git a/app/test/test_bitcount.c b/app/test/test_bitcount.c
> > new file mode 100644
> > index 0000000..36eb05c
> > --- /dev/null
> > +++ b/app/test/test_bitcount.c
> > @@ -0,0 +1,71 @@
> > +/* SPDX-License-Identifier: BSD-3-Clause
> > + * Copyright (C) 2022 Microsoft Corporation
> > + */
> > +
> > +#include <string.h>
> > +
> > +#include <rte_bitops.h>
> > +#include <rte_debug.h>
> > +
> > +#include "test.h"
> > +
> > +RTE_LOG_REGISTER(bitcount_logtype_test, test.bitcount, INFO);
> > +
> > +static int
> > +test_clz32(void)
> > +{
> > +	uint32_t v = 1;
> > +	RTE_TEST_ASSERT(rte_clz32(v) == sizeof(v) * CHAR_BIT - 1,
> > +	    "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_clz64(void)
> > +{
> > +	uint64_t v = 1;
> > +	RTE_TEST_ASSERT(rte_clz64(v) == sizeof(v) * CHAR_BIT - 1,
> > +	    "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_ctz32(void)
> > +{
> > +	uint32_t v = 2;
> > +	RTE_TEST_ASSERT(rte_ctz32(v) == 1, "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_ctz64(void)
> > +{
> > +	uint64_t v = 2;
> > +	RTE_TEST_ASSERT(rte_ctz64(v) == 1, "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static struct unit_test_suite bitcount_test_suite = {
> > +	.suite_name = "bitcount autotest",
> > +	.setup = NULL,
> > +	.teardown = NULL,
> > +	.unit_test_cases = {
> > +		TEST_CASE(test_clz32),
> > +		TEST_CASE(test_clz64),
> > +		TEST_CASE(test_ctz32),
> > +		TEST_CASE(test_ctz64),
> > +		TEST_CASES_END()
> > +	}
> > +};
> > +
> > +static int
> > +test_bitcount(void)
> > +{
> > +	return unit_test_suite_runner(&bitcount_test_suite);
> > +}
> > +
> > +REGISTER_TEST_COMMAND(bitcount_autotest, test_bitcount);
> > diff --git a/lib/eal/include/rte_bitops.h b/lib/eal/include/rte_bitops.h
> > index 531479e..387d7aa 100644
> > --- a/lib/eal/include/rte_bitops.h
> > +++ b/lib/eal/include/rte_bitops.h
> > @@ -1,5 +1,7 @@
> >  /* SPDX-License-Identifier: BSD-3-Clause
> >   * Copyright(c) 2020 Arm Limited
> > + * Copyright(c) 2010-2019 Intel Corporation
> > + * Copyright(c) 2023 Microsoft Corporation
> >   */
> >  
> >  #ifndef _RTE_BITOPS_H_
> > @@ -275,6 +277,172 @@
> >  	return val & mask;
> >  }
> >  
> > +#ifdef RTE_TOOLCHAIN_MSVC
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of leading 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of leading zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_clz32(uint32_t v)
> > +{
> > +	unsigned long rv;
> > +
> > +	(void)_BitScanReverse(&rv, v);
> > +
> > +	return (unsigned int)rv;
> > +}
> 
> 
> OK, this looks wrong to me,
> 
> 
> '_BitScanReverse' is [1]:
> "Search the mask data from most significant bit (MSB) to least
> significant bit (LSB) for a set bit (1)."
> 
> As far as I can see index starts from zero and from lsb to msb.
> 
> So _BitScanReverse() returns following index values:
> 0x2 => 1
> 0xffffffff => 31
> 
> If above is correct, above function doesn't return number of leading
> zeros, but it should return "31 - (unsigned int)rv".
> 
> Please check godbolt experiment for above:
> https://godbolt.org/z/znYn54f57
> 
> 
> As far as I can see unit test is correct, so above should fail with
> windows compiler, and I assume you run unit test with windows compiler,
> so probably I am missing something but please help me understand.
> 
> 
> 
> [1]
> https://learn.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=msvc-170
> 
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of leading 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of leading zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_clz64(uint64_t v)
> > +{
> > +	unsigned long rv;
> > +
> > +	(void)_BitScanReverse64(&rv, v);
> > +
> > +	return (unsigned int)rv;
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz32(uint32_t v)
> > +{
> > +	unsigned long rv;
> > +
> > +	(void)_BitScanForward(&rv, v);
> > +
> > +	return (unsigned int)rv;
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz64(uint64_t v)
> > +{
> > +	unsigned long rv;
> > +
> > +	(void)_BitScanForward64(&rv, v);
> > +
> > +	return (unsigned int)rv;
> > +}
> > +
> > +#else
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of leading 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of leading zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_clz32(uint32_t v)
> > +{
> > +	return (unsigned int)__builtin_clz(v);
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of leading 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of leading zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_clz64(uint64_t v)
> > +{
> > +	return (unsigned int)__builtin_clzll(v);
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz32(uint32_t v)
> > +{
> > +	return (unsigned int)__builtin_ctz(v);
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz64(uint64_t v)
> > +{
> > +	return (unsigned int)__builtin_ctzll(v);
> > +}
> 
> 'rte_ctz32()' & 'rte_ctz64()' are practically exact same with
> 'rte_bsf32()' & 'rte_bsf64()',
> 
> Although I can see description is different, do we need same
> functionality with new function name,
> why not add 'rte_bsf32()' & 'rte_bsf64()' versions for the Windows?

i agree. i need a consensus from reviewers if they think this series
should be changed.

if we do take bsf{32,64} instead then does that mean we ban the use of
__ctz{32,64} in dpdk? keeping in mind the end goal is portability.

> 
> 
> 
> btw, do you guys know what 'bsf' & 'fls' (rte_fls_u32) stands for?

no idea. before my time.

> 
> > +
> > +#endif
> > +
> >  /**
> >   * Combines 32b inputs most significant set bits into the least
> >   * significant bits to construct a value with the same MSBs as x
Tyler Retzlaff Jan. 10, 2023, 6:37 p.m. UTC | #3 
On Tue, Jan 10, 2023 at 01:55:59PM +0000, Ferruh Yigit wrote:
> On 1/9/2023 5:36 PM, Tyler Retzlaff wrote:
> > From: Tyler Retzlaff <roretzla@microsoft.com>
> > 
> > Provide an abstraction for leading and trailing zero bit counting
> > functions to hide compiler specific intrinsics and builtins.
> > 
> > Include basic unit test of following functions added.
> > 
> >     rte_clz32
> >     rte_clz64
> >     rte_ctz32
> >     rte_ctz64
> > 
> > Signed-off-by: Tyler Retzlaff <roretzla@linux.microsoft.com>
> > ---
> >  app/test/meson.build         |   2 +
> >  app/test/test_bitcount.c     |  71 ++++++++++++++++++
> >  lib/eal/include/rte_bitops.h | 168 +++++++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 241 insertions(+)
> >  create mode 100644 app/test/test_bitcount.c
> > 
> > diff --git a/app/test/meson.build b/app/test/meson.build
> > index f34d19e..d1277bc 100644
> > --- a/app/test/meson.build
> > +++ b/app/test/meson.build
> > @@ -13,6 +13,7 @@ test_sources = files(
> >          'test_alarm.c',
> >          'test_atomic.c',
> >          'test_barrier.c',
> > +        'test_bitcount.c',
> >          'test_bitops.c',
> >          'test_bitmap.c',
> >          'test_bpf.c',
> > @@ -160,6 +161,7 @@ test_deps += ['bus_pci', 'bus_vdev']
> >  fast_tests = [
> >          ['acl_autotest', true, true],
> >          ['atomic_autotest', false, true],
> > +        ['bitcount_autotest', true, true],
> >          ['bitmap_autotest', true, true],
> >          ['bpf_autotest', true, true],
> >          ['bpf_convert_autotest', true, true],
> > diff --git a/app/test/test_bitcount.c b/app/test/test_bitcount.c
> > new file mode 100644
> > index 0000000..36eb05c
> > --- /dev/null
> > +++ b/app/test/test_bitcount.c
> > @@ -0,0 +1,71 @@
> > +/* SPDX-License-Identifier: BSD-3-Clause
> > + * Copyright (C) 2022 Microsoft Corporation
> > + */
> > +
> > +#include <string.h>
> > +
> > +#include <rte_bitops.h>
> > +#include <rte_debug.h>
> > +
> > +#include "test.h"
> > +
> > +RTE_LOG_REGISTER(bitcount_logtype_test, test.bitcount, INFO);
> > +
> > +static int
> > +test_clz32(void)
> > +{
> > +	uint32_t v = 1;
> > +	RTE_TEST_ASSERT(rte_clz32(v) == sizeof(v) * CHAR_BIT - 1,
> > +	    "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_clz64(void)
> > +{
> > +	uint64_t v = 1;
> > +	RTE_TEST_ASSERT(rte_clz64(v) == sizeof(v) * CHAR_BIT - 1,
> > +	    "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_ctz32(void)
> > +{
> > +	uint32_t v = 2;
> > +	RTE_TEST_ASSERT(rte_ctz32(v) == 1, "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_ctz64(void)
> > +{
> > +	uint64_t v = 2;
> > +	RTE_TEST_ASSERT(rte_ctz64(v) == 1, "Unexpected count.");
> > +
> > +	return 0;
> > +}
> > +
> > +static struct unit_test_suite bitcount_test_suite = {
> > +	.suite_name = "bitcount autotest",
> > +	.setup = NULL,
> > +	.teardown = NULL,
> > +	.unit_test_cases = {
> > +		TEST_CASE(test_clz32),
> > +		TEST_CASE(test_clz64),
> > +		TEST_CASE(test_ctz32),
> > +		TEST_CASE(test_ctz64),
> > +		TEST_CASES_END()
> > +	}
> > +};
> > +
> > +static int
> > +test_bitcount(void)
> > +{
> > +	return unit_test_suite_runner(&bitcount_test_suite);
> > +}
> > +
> > +REGISTER_TEST_COMMAND(bitcount_autotest, test_bitcount);
> > diff --git a/lib/eal/include/rte_bitops.h b/lib/eal/include/rte_bitops.h
> > index 531479e..387d7aa 100644
> > --- a/lib/eal/include/rte_bitops.h
> > +++ b/lib/eal/include/rte_bitops.h
> > @@ -1,5 +1,7 @@
> >  /* SPDX-License-Identifier: BSD-3-Clause
> >   * Copyright(c) 2020 Arm Limited
> > + * Copyright(c) 2010-2019 Intel Corporation
> > + * Copyright(c) 2023 Microsoft Corporation
> >   */
> >  
> >  #ifndef _RTE_BITOPS_H_
> > @@ -275,6 +277,172 @@
> >  	return val & mask;
> >  }
> >  
> > +#ifdef RTE_TOOLCHAIN_MSVC
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of leading 0-bits in v.
> > + *
> > + * @param v
> > + *   The value.
> > + * @return
> > + *   The count of leading zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_clz32(uint32_t v)
> > +{
> > +	unsigned long rv;
> > +
> > +	(void)_BitScanReverse(&rv, v);
> > +
> > +	return (unsigned int)rv;
> > +}
> 
> 
> OK, this looks wrong to me,
> 
> 
> '_BitScanReverse' is [1]:
> "Search the mask data from most significant bit (MSB) to least
> significant bit (LSB) for a set bit (1)."
> 
> As far as I can see index starts from zero and from lsb to msb.
> 
> So _BitScanReverse() returns following index values:
> 0x2 => 1
> 0xffffffff => 31
> 
> If above is correct, above function doesn't return number of leading
> zeros, but it should return "31 - (unsigned int)rv".
> 
> Please check godbolt experiment for above:
> https://godbolt.org/z/znYn54f57
> 
> 
> As far as I can see unit test is correct, so above should fail with
> windows compiler, and I assume you run unit test with windows compiler,
> so probably I am missing something but please help me understand.

the test is wrong, i will fix both the test and the implementation.

thank you for the careful review.
diff mbox series

Patch

diff --git a/app/test/meson.build b/app/test/meson.build
index f34d19e..d1277bc 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -13,6 +13,7 @@  test_sources = files(
         'test_alarm.c',
         'test_atomic.c',
         'test_barrier.c',
+        'test_bitcount.c',
         'test_bitops.c',
         'test_bitmap.c',
         'test_bpf.c',
@@ -160,6 +161,7 @@  test_deps += ['bus_pci', 'bus_vdev']
 fast_tests = [
         ['acl_autotest', true, true],
         ['atomic_autotest', false, true],
+        ['bitcount_autotest', true, true],
         ['bitmap_autotest', true, true],
         ['bpf_autotest', true, true],
         ['bpf_convert_autotest', true, true],
diff --git a/app/test/test_bitcount.c b/app/test/test_bitcount.c
new file mode 100644
index 0000000..36eb05c
--- /dev/null
+++ b/app/test/test_bitcount.c
@@ -0,0 +1,71 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright (C) 2022 Microsoft Corporation
+ */
+
+#include <string.h>
+
+#include <rte_bitops.h>
+#include <rte_debug.h>
+
+#include "test.h"
+
+RTE_LOG_REGISTER(bitcount_logtype_test, test.bitcount, INFO);
+
+static int
+test_clz32(void)
+{
+	uint32_t v = 1;
+	RTE_TEST_ASSERT(rte_clz32(v) == sizeof(v) * CHAR_BIT - 1,
+	    "Unexpected count.");
+
+	return 0;
+}
+
+static int
+test_clz64(void)
+{
+	uint64_t v = 1;
+	RTE_TEST_ASSERT(rte_clz64(v) == sizeof(v) * CHAR_BIT - 1,
+	    "Unexpected count.");
+
+	return 0;
+}
+
+static int
+test_ctz32(void)
+{
+	uint32_t v = 2;
+	RTE_TEST_ASSERT(rte_ctz32(v) == 1, "Unexpected count.");
+
+	return 0;
+}
+
+static int
+test_ctz64(void)
+{
+	uint64_t v = 2;
+	RTE_TEST_ASSERT(rte_ctz64(v) == 1, "Unexpected count.");
+
+	return 0;
+}
+
+static struct unit_test_suite bitcount_test_suite = {
+	.suite_name = "bitcount autotest",
+	.setup = NULL,
+	.teardown = NULL,
+	.unit_test_cases = {
+		TEST_CASE(test_clz32),
+		TEST_CASE(test_clz64),
+		TEST_CASE(test_ctz32),
+		TEST_CASE(test_ctz64),
+		TEST_CASES_END()
+	}
+};
+
+static int
+test_bitcount(void)
+{
+	return unit_test_suite_runner(&bitcount_test_suite);
+}
+
+REGISTER_TEST_COMMAND(bitcount_autotest, test_bitcount);
diff --git a/lib/eal/include/rte_bitops.h b/lib/eal/include/rte_bitops.h
index 531479e..387d7aa 100644
--- a/lib/eal/include/rte_bitops.h
+++ b/lib/eal/include/rte_bitops.h
@@ -1,5 +1,7 @@ 
 /* SPDX-License-Identifier: BSD-3-Clause
  * Copyright(c) 2020 Arm Limited
+ * Copyright(c) 2010-2019 Intel Corporation
+ * Copyright(c) 2023 Microsoft Corporation
  */
 
 #ifndef _RTE_BITOPS_H_
@@ -275,6 +277,172 @@ 
 	return val & mask;
 }
 
+#ifdef RTE_TOOLCHAIN_MSVC
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of leading 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of leading zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_clz32(uint32_t v)
+{
+	unsigned long rv;
+
+	(void)_BitScanReverse(&rv, v);
+
+	return (unsigned int)rv;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of leading 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of leading zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_clz64(uint64_t v)
+{
+	unsigned long rv;
+
+	(void)_BitScanReverse64(&rv, v);
+
+	return (unsigned int)rv;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of trailing 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of trailing zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_ctz32(uint32_t v)
+{
+	unsigned long rv;
+
+	(void)_BitScanForward(&rv, v);
+
+	return (unsigned int)rv;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of trailing 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of trailing zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_ctz64(uint64_t v)
+{
+	unsigned long rv;
+
+	(void)_BitScanForward64(&rv, v);
+
+	return (unsigned int)rv;
+}
+
+#else
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of leading 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of leading zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_clz32(uint32_t v)
+{
+	return (unsigned int)__builtin_clz(v);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of leading 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of leading zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_clz64(uint64_t v)
+{
+	return (unsigned int)__builtin_clzll(v);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of trailing 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of trailing zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_ctz32(uint32_t v)
+{
+	return (unsigned int)__builtin_ctz(v);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
+ *
+ * Get the count of trailing 0-bits in v.
+ *
+ * @param v
+ *   The value.
+ * @return
+ *   The count of trailing zero bits.
+ */
+__rte_experimental
+static inline unsigned int
+rte_ctz64(uint64_t v)
+{
+	return (unsigned int)__builtin_ctzll(v);
+}
+
+#endif
+
 /**
  * Combines 32b inputs most significant set bits into the least
  * significant bits to construct a value with the same MSBs as x