static int
miniflow_n_values(const struct miniflow *flow)
{
- return popcount64(flow->map);
+ return popcount(flow->map);
}
static uint32_t *
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'
#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
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)
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
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)
}
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)
{
}
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;
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);
}