From: Ben Pfaff Date: Mon, 18 Nov 2013 19:30:38 +0000 (-0800) Subject: util: Make raw_ctz() accept 64-bit integers. X-Git-Tag: sliver-openvswitch-2.0.90-1~5^2~8 X-Git-Url: http://git.onelab.eu/?p=sliver-openvswitch.git;a=commitdiff_plain;h=d43d314e62b9791d1b9c13595a13fd6a851f856e 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 Acked-by: Jarno Rajahalme --- diff --git a/lib/flow.c b/lib/flow.c index 137ce696d..1e31982ee 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 35356c120..f2229bb57 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 9b79c2559..19abada81 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 374c09478..91dc0a58d 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'