[ovs-dev] [PATCH 2/2] util: Make popcount() handle 64-bit integers, not separate popcount64().

YAMAMOTO Takashi yamamoto at valinux.co.jp
Tue Nov 19 02:20:44 UTC 2013


> 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().)

this breaks NetBSD builds.

gcc -DHAVE_CONFIG_H -I.   -I ./include -I ./lib -I ./lib   -Wstrict-prototypes -Wall -Wextra -Wno-sign-compare -Wpointer-arith -Wdeclaration-after-statement -Wno-format-zero-length -Wswitch-enum -Wunused-parameter -Wstrict-aliasing -Wbad-function-cast -Wcast-align -Wmissing-prototypes -Wmissing-field-initializers  -g -O2 -MT lib/aes128.o -MD -MP -MF $depbase.Tpo -c -o lib/aes128.o lib/aes128.c &&\
mv -f $depbase.Tpo $depbase.Po
In file included from lib/aes128.c:29:0:
lib/util.h:290:14: error: conflicting types for 'popcount'
/usr/include/strings.h:57:14: note: previous declaration of 'popcount' was here
gmake[2]: *** [lib/aes128.o] Error 1

FYI, NetBSD's strings.h and libc have the following functions.

SYNOPSIS
     #include <strings.h>

     unsigned int
     popcount(unsigned int value);

     unsigned int
     popcountl(unsigned long value);

     unsigned int
     popcountll(unsigned long long value);

     #include <stdint.h>

     unsigned int
     popcount32(uint32_t value);

     unsigned int
     popcount64(uint64_t value);

DESCRIPTION
     The popcount functions returns the number of bits set in value.

YAMAMOTO Takashi

> 
> 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