Acked-by: Jarno Rajahalme <jrajaha...@nicira.com>
On Nov 18, 2013, at 1:19 PM, Ben Pfaff <b...@nicira.com> wrote:
> Having a single function that can do 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 <b...@nicira.com>
> ---
> lib/flow.c | 16 ++++++++--------
> lib/match.c | 2 +-
> lib/util.c | 11 +++++------
> lib/util.h | 31 +++++++++++--------------------
> 4 files changed, 25 insertions(+), 35 deletions(-)
>
> diff --git a/lib/flow.c b/lib/flow.c
> index 137ce69..1e31982 100644
> --- 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
> --- 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
> --- 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
> --- 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'
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
