[ovs-dev] [PATCH 2/2] util: Make popcount() handle 64-bit integers, not separate popcount64().
Jarno Rajahalme
jrajahalme at nicira.com
Mon Nov 18 22:18:37 UTC 2013
Acked-by: Jarno Rajahalme <jrajahalme at nicira.com>
On Nov 18, 2013, at 1:19 PM, Ben Pfaff <blp at nicira.com> wrote:
> Having a single function that can do popcount() on any integer type is
> easier for callers to get right. The implementation is probably slower
> if the caller actually provides a 32-bit (or shorter) integer, but the
> only existing callers always provide a full 64-bit integer so this seems
> unimportant for now.
>
> This also restores use, in practice, of the optimized implementation of
> population count. (As the comment on popcount32() says, this version is
> 2x faster than __builtin_popcount().)
>
> Signed-off-by: Ben Pfaff <blp at nicira.com>
> ---
> lib/flow.c | 5 ++---
> lib/util.c | 11 +++++++++--
> lib/util.h | 17 +----------------
> tests/test-util.c | 38 ++++----------------------------------
> 4 files changed, 16 insertions(+), 55 deletions(-)
>
> diff --git a/lib/flow.c b/lib/flow.c
> index 1e31982..63c6ef8 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -1101,7 +1101,7 @@ flow_compose(struct ofpbuf *b, const struct flow *flow)
> static int
> miniflow_n_values(const struct miniflow *flow)
> {
> - return popcount64(flow->map);
> + return popcount(flow->map);
> }
>
> static uint32_t *
> @@ -1221,8 +1221,7 @@ miniflow_get__(const struct miniflow *flow, unsigned int u32_ofs)
> static const uint32_t zero = 0;
> return &zero;
> }
> - return flow->values
> - + popcount64(flow->map & ((UINT64_C(1) << u32_ofs) - 1));
> + return flow->values + popcount(flow->map & ((UINT64_C(1) << u32_ofs) - 1));
> }
>
> /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'flow'
> diff --git a/lib/util.c b/lib/util.c
> index 19abada..eb8beca 100644
> --- a/lib/util.c
> +++ b/lib/util.c
> @@ -917,8 +917,8 @@ raw_ctz(uint64_t n)
> #endif
>
> /* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */
> -unsigned int
> -popcount(uint32_t x)
> +static unsigned int
> +popcount32(uint32_t x)
> {
> /* In my testing, this implementation is over twice as fast as any other
> * portable implementation that I tried, including GCC 4.4
> @@ -950,6 +950,13 @@ popcount(uint32_t x)
> popcount8[x >> 24]);
> }
>
> +/* Returns the number of 1-bits in 'x', between 0 and 64 inclusive. */
> +unsigned int
> +popcount(uint64_t x)
> +{
> + return popcount32(x) + popcount32(x >> 32);
> +}
> +
> /* Returns true if the 'n' bytes starting at 'p' are zeros. */
> bool
> is_all_zeros(const uint8_t *p, size_t n)
> diff --git a/lib/util.h b/lib/util.h
> index 91dc0a5..4e2b2a7 100644
> --- a/lib/util.h
> +++ b/lib/util.h
> @@ -287,7 +287,7 @@ void ignore(bool x OVS_UNUSED);
>
> int log_2_floor(uint32_t);
> int log_2_ceil(uint32_t);
> -unsigned int popcount(uint32_t);
> +unsigned int popcount(uint64_t);
>
> /* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0. */
> #if __GNUC__ >= 4
> @@ -306,21 +306,6 @@ raw_ctz(uint64_t n)
> int raw_ctz(uint64_t n);
> #endif
>
> -#if __GNUC__ >= 4
> -static inline int
> -popcount64(uint64_t n)
> -{
> - return __builtin_popcountll(n);
> -}
> -#else
> -/* Defined using the 32-bit counterparts. */
> -static inline int
> -popcount64(uint64_t n)
> -{
> - return popcount(n) + popcount(n >> 32);
> -}
> -#endif
> -
> /* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
> static inline int
> ctz(uint32_t n)
> diff --git a/tests/test-util.c b/tests/test-util.c
> index e59adf7..e66987d 100644
> --- a/tests/test-util.c
> +++ b/tests/test-util.c
> @@ -188,26 +188,16 @@ shuffle(uint64_t *p, size_t n)
> }
>
> static void
> -check_popcount(uint32_t x, int n)
> +check_popcount(uint64_t x, int n)
> {
> if (popcount(x) != n) {
> - fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n",
> + fprintf(stderr, "popcount(%#"PRIx64") is %d but should be %d\n",
> x, popcount(x), n);
> abort();
> }
> }
>
> static void
> -check_popcount64(uint64_t x, int n)
> -{
> - if (popcount64(x) != n) {
> - fprintf(stderr, "popcount64(%#"PRIx64") is %d but should be %d\n",
> - x, popcount64(x), n);
> - abort();
> - }
> -}
> -
> -static void
> test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
> {
> uint64_t bits[64];
> @@ -218,26 +208,6 @@ test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
> }
>
> check_popcount(0, 0);
> - check_popcount64(0, 0);
> -
> - for (i = 0; i < 1000; i++) {
> - uint32_t x = 0;
> - int j;
> -
> - shuffle(bits, ARRAY_SIZE(bits)/2);
> - for (j = 0; j < 32; j++) {
> - x |= bits[j];
> - check_popcount(x, j + 1);
> - }
> - assert(x == UINT32_MAX);
> -
> - shuffle(bits, ARRAY_SIZE(bits)/2);
> - for (j = 31; j >= 0; j--) {
> - x &= ~bits[j];
> - check_popcount(x, j);
> - }
> - assert(x == 0);
> - }
>
> for (i = 0; i < 1000; i++) {
> uint64_t x = 0;
> @@ -246,14 +216,14 @@ test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
> shuffle(bits, ARRAY_SIZE(bits));
> for (j = 0; j < 64; j++) {
> x |= bits[j];
> - check_popcount64(x, j + 1);
> + check_popcount(x, j + 1);
> }
> assert(x == UINT64_MAX);
>
> shuffle(bits, ARRAY_SIZE(bits));
> for (j = 63; j >= 0; j--) {
> x &= ~bits[j];
> - check_popcount64(x, j);
> + check_popcount(x, j);
> }
> assert(x == 0);
> }
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
More information about the dev
mailing list