util: Make raw_ctz() accept 64-bit integers.

Having a single function that can do raw_ctz() on any integer type is
easier for callers to get right, and there is no real downside in the
implementation.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jarno Rajahalme <jrajahalme@nicira.com>

diff --git a/lib/flow.c b/lib/flow.c
index 137ce69..1e31982 100644 (file)
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -666,7 +666,7 @@ flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
     uint64_t map;
 
     for (map = src->map; map; map = zero_rightmost_1bit(map)) {
-        dst_u32[raw_ctz64(map)] |= src->values[ofs++];
+        dst_u32[raw_ctz(map)] |= src->values[ofs++];
     }
 }
 
@@ -1133,7 +1133,7 @@ miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
     dst->values = miniflow_alloc_values(dst, n);
     ofs = 0;
     for (map = dst->map; map; map = zero_rightmost_1bit(map)) {
-        dst->values[ofs++] = src_u32[raw_ctz64(map)];
+        dst->values[ofs++] = src_u32[raw_ctz(map)];
     }
 }
 
@@ -1295,7 +1295,7 @@ miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
     p = mask->masks.values;
 
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz64(map);
+        int ofs = raw_ctz(map);
 
         if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
             return false;
@@ -1319,7 +1319,7 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
     p = mask->masks.values;
 
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz64(map);
+        int ofs = raw_ctz(map);
 
         if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
             return false;
@@ -1369,7 +1369,7 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
 
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
         if (*p) {
-            int ofs = raw_ctz64(map);
+            int ofs = raw_ctz(map);
             hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
         }
         p++;
@@ -1395,7 +1395,7 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
     hash = basis;
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
         if (*p) {
-            hash = mhash_add(hash, flow_u32[raw_ctz64(map)] & *p);
+            hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p);
         }
         p++;
     }
@@ -1446,7 +1446,7 @@ minimask_combine(struct minimask *dst_,
 
     dst->map = 0;
     for (map = a->map & b->map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz64(map);
+        int ofs = raw_ctz(map);
         uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
 
         if (mask) {
@@ -1511,7 +1511,7 @@ minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
     uint64_t map;
 
     for (map = a->map | b->map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz64(map);
+        int ofs = raw_ctz(map);
         uint32_t a_u32 = miniflow_get(a, ofs);
         uint32_t b_u32 = miniflow_get(b, ofs);
 

diff --git a/lib/match.c b/lib/match.c
index 35356c1..f2229bb 100644 (file)
--- a/lib/match.c
+++ b/lib/match.c
@@ -1176,7 +1176,7 @@ minimatch_matches_flow(const struct minimatch *match,
     uint64_t map;
 
     for (map = match->flow.map; map; map = zero_rightmost_1bit(map)) {
-        if ((*flowp++ ^ target_u32[raw_ctz64(map)]) & *maskp++) {
+        if ((*flowp++ ^ target_u32[raw_ctz(map)]) & *maskp++) {
             return false;
         }
     }

diff --git a/lib/util.c b/lib/util.c
index 9b79c25..19abada 100644 (file)
--- a/lib/util.c
+++ b/lib/util.c
@@ -889,16 +889,14 @@ log_2_ceil(uint32_t n)
 }
 
 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
-#if !defined(UINT_MAX) || !defined(UINT32_MAX)
-#error "Someone screwed up the #includes."
-#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+#if __GNUC__ >= 4
 /* Defined inline in util.h. */
 #else
 int
-raw_ctz(uint32_t n)
+raw_ctz(uint64_t n)
 {
-    unsigned int k;
-    int count = 31;
+    uint64_t k;
+    int count = 63;
 
 #define CTZ_STEP(X)                             \
     k = n << (X);                               \
@@ -906,6 +904,7 @@ raw_ctz(uint32_t n)
         count -= X;                             \
         n = k;                                  \
     }
+    CTZ_STEP(32);
     CTZ_STEP(16);
     CTZ_STEP(8);
     CTZ_STEP(4);

diff --git a/lib/util.h b/lib/util.h
index 374c094..91dc0a5 100644 (file)
--- a/lib/util.h
+++ b/lib/util.h
@@ -289,29 +289,25 @@ int log_2_floor(uint32_t);
 int log_2_ceil(uint32_t);
 unsigned int popcount(uint32_t);
 
-/* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0.
- *
- * This compiles to a single machine instruction ("bsf") with GCC on x86. */
-#if !defined(UINT_MAX) || !defined(UINT32_MAX)
-#error "Someone screwed up the #includes."
-#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+/* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
+#if __GNUC__ >= 4
 static inline int
-raw_ctz(uint32_t n)
+raw_ctz(uint64_t n)
 {
-    return __builtin_ctz(n);
+    /* With GCC 4.7 on 32-bit x86, if a 32-bit integer is passed as 'n', using
+     * a plain __builtin_ctzll() here always generates an out-of-line function
+     * call.  The test below helps it to emit a single 'bsf' instruction. */
+    return (__builtin_constant_p(n <= UINT32_MAX) && n <= UINT32_MAX
+            ? __builtin_ctz(n)
+            : __builtin_ctzll(n));
 }
 #else
 /* Defined in util.c. */
-int raw_ctz(uint32_t n);
+int raw_ctz(uint64_t n);
 #endif
 
 #if __GNUC__ >= 4
 static inline int
-raw_ctz64(uint64_t n)
-{
-    return __builtin_ctzll(n);
-}
-static inline int
 popcount64(uint64_t n)
 {
     return __builtin_popcountll(n);
@@ -319,11 +315,6 @@ popcount64(uint64_t n)
 #else
 /* Defined using the 32-bit counterparts. */
 static inline int
-raw_ctz64(uint64_t n)
-{
-    return (uint32_t)n ? raw_ctz(n) : 32 + raw_ctz(n >> 32);
-}
-static inline int
 popcount64(uint64_t n)
 {
     return popcount(n) + popcount(n >> 32);
@@ -341,7 +332,7 @@ ctz(uint32_t n)
 static inline int
 ctz64(uint64_t n)
 {
-    return n ? raw_ctz64(n) : 64;
+    return n ? raw_ctz(n) : 64;
 }
 
 /* Returns the rightmost 1-bit in 'x' (e.g. 01011000 => 00001000), or 0 if 'x'