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

Ben Pfaff blp at nicira.com
Mon Nov 18 21:19:09 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().)

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




More information about the dev mailing list