diff options
author | Ben Pfaff <blp@nicira.com> | 2012-07-20 12:38:59 -0700 |
---|---|---|
committer | Ben Pfaff <blp@nicira.com> | 2012-09-04 11:19:17 -0700 |
commit | a656cb7736fd9f5926c2b1bdd6f50dafc3aa796a (patch) | |
tree | 57774895cd499c78fb803dcd526689ff091c6fec /lib/util.h | |
parent | 8472a3cecc6c370e227dd477470e4a8cf760ddb5 (diff) |
util: New function popcount().
This is the fastest portable implementation among the ones below, as
measured with GCC 4.4 on a Xeon X3430. The measeured times were, in
seconds:
popcount1 25.6
popcount2 6.9 (but is not portable)
popcount3 31.4
popcount4 25.6
popcount5 61.6 (and is buggy)
popcount6 64.6
popcount7 32.3
popcount8 11.2
int
popcount1(unsigned int x)
{
return __builtin_popcount(x);
}
int
popcount2(unsigned int x)
{
unsigned int y;
asm("popcnt %1, %0" : "=r" (y) : "g" (x));
return y;
}
int
popcount3(unsigned int x)
{
unsigned int n;
n = (x >> 1) & 033333333333;
x -= n;
n = (n >> 1) & 033333333333;
x -= n;
x = (x + (x >> 3)) & 030707070707;
return x % 63;
}
int
popcount4(unsigned int x)
{
x -= (x >> 1) & 0x55555555;
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return x & 0x3f;
}
int
popcount5(unsigned int x)
{
int n;
n = 0;
while (x) {
if (x & 0xf) {
n += ((0xe9949440 >> (x & 0xf)) & 3) + 1;
}
x >>= 4;
}
return n;
}
int
popcount6(unsigned int x)
{
int n;
n = 0;
while (x) {
n += (0xe994 >> (x & 7)) & 3;
x >>= 3;
}
return n;
}
int
popcount7(unsigned int x)
{
static const int table[16] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
return (table[x & 0xf]
+ table[(x >> 4) & 0xf]
+ table[(x >> 8) & 0xf]
+ table[(x >> 12) & 0xf]
+ table[(x >> 16) & 0xf]
+ table[(x >> 20) & 0xf]
+ table[(x >> 24) & 0xf]
+ table[x >> 28]);
}
static int
popcount8(unsigned int x)
{
((((X) & (1 << 0)) != 0) + \
(((X) & (1 << 1)) != 0) + \
(((X) & (1 << 2)) != 0) + \
(((X) & (1 << 3)) != 0) + \
(((X) & (1 << 4)) != 0) + \
(((X) & (1 << 5)) != 0) + \
(((X) & (1 << 6)) != 0) + \
(((X) & (1 << 7)) != 0))
static const uint8_t popcount8[256] = {
INIT64(0), INIT64(64), INIT64(128), INIT64(192)
};
return (popcount8[x & 0xff] +
popcount8[(x >> 8) & 0xff] +
popcount8[(x >> 16) & 0xff] +
popcount8[x >> 24]);
}
int
main(void)
{
unsigned long long int x;
int n;
n = 0;
for (x = 0; x <= UINT32_MAX; x++) {
n += popcount8(x);
}
printf("%d\n", n);
return 0;
}
Signed-off-by: Ben Pfaff <blp@nicira.com>
Diffstat (limited to 'lib/util.h')
-rw-r--r-- | lib/util.h | 2 |
1 files changed, 2 insertions, 0 deletions
@@ -17,6 +17,7 @@ #ifndef UTIL_H #define UTIL_H 1 +#include <limits.h> #include <stdarg.h> #include <stdbool.h> #include <stddef.h> @@ -244,6 +245,7 @@ void ignore(bool x OVS_UNUSED); int log_2_floor(uint32_t); int log_2_ceil(uint32_t); int ctz(uint32_t); +int popcount(uint32_t); bool is_all_zeros(const uint8_t *, size_t); bool is_all_ones(const uint8_t *, size_t); |