From cc4c738e120a82dda70fe10c1619531a9f0b1249 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Mon, 18 Nov 2013 09:28:44 -0800 Subject: [PATCH] lib/util: Add ctz64() and popcount64(). Add raw_ctz64(), ctz64(), and popcount64() using builtins when available. Signed-off By: Jarno Rajahalme Acked-by: Ben Pfaff --- lib/util.h | 38 ++++++++++++++++++++++++--- tests/test-util.c | 67 ++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 95 insertions(+), 10 deletions(-) diff --git a/lib/util.h b/lib/util.h index fd686d622..374c09478 100644 --- a/lib/util.h +++ b/lib/util.h @@ -285,6 +285,10 @@ void ignore(bool x OVS_UNUSED); /* Bitwise tests. */ +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. */ @@ -301,6 +305,31 @@ raw_ctz(uint32_t n) int raw_ctz(uint32_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); +} +#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); +} +#endif + /* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */ static inline int ctz(uint32_t n) @@ -308,9 +337,12 @@ ctz(uint32_t n) return n ? raw_ctz(n) : 32; } -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', or 64 if 'n' is 0. */ +static inline int +ctz64(uint64_t n) +{ + return n ? raw_ctz64(n) : 64; +} /* Returns the rightmost 1-bit in 'x' (e.g. 01011000 => 00001000), or 0 if 'x' * is 0. */ diff --git a/tests/test-util.c b/tests/test-util.c index 42565091b..e59adf74e 100644 --- a/tests/test-util.c +++ b/tests/test-util.c @@ -70,6 +70,16 @@ check_ctz(uint32_t x, int n) } } +static void +check_ctz64(uint64_t x, int n) +{ + if (ctz64(x) != n) { + fprintf(stderr, "ctz64(%"PRIu64") is %d but should be %d\n", + x, ctz64(x), n); + abort(); + } +} + static void test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) { @@ -86,8 +96,21 @@ test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) check_ctz((random_uint32() | 1) << n, n); } + + for (n = 0; n < 64; n++) { + /* Check minimum x such that f(x) == n. */ + check_ctz64(UINT64_C(1) << n, n); + + /* Check maximum x such that f(x) == n. */ + check_ctz64(UINT64_MAX << n, n); + + /* Check a random value in the middle. */ + check_ctz64((random_uint64() | UINT64_C(1)) << n, n); + } + /* Check ctz(0). */ check_ctz(0, 32); + check_ctz64(0, 64); } /* Returns a random number in the range 'min'...'max' inclusive. */ @@ -154,11 +177,11 @@ test_round_down_pow2(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) } static void -shuffle(unsigned int *p, size_t n) +shuffle(uint64_t *p, size_t n) { for (; n > 1; n--, p++) { - unsigned int *q = &p[random_range(n)]; - unsigned int tmp = *p; + uint64_t *q = &p[random_range(n)]; + uint64_t tmp = *p; *p = *q; *q = tmp; } @@ -174,36 +197,66 @@ check_popcount(uint32_t x, int n) } } +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) { - unsigned int bits[32]; + uint64_t bits[64]; int i; for (i = 0; i < ARRAY_SIZE(bits); i++) { - bits[i] = 1u << i; + bits[i] = UINT64_C(1) << i; } 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)); + 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)); + 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; + int j; + + shuffle(bits, ARRAY_SIZE(bits)); + for (j = 0; j < 64; j++) { + x |= bits[j]; + check_popcount64(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); + } + assert(x == 0); + } } /* Returns the sum of the squares of the first 'n' positive integers. */ -- 2.47.0