Bruno Haible <[EMAIL PROTECTED]> writes:
> OK, then we have to do the review after it's already in CVS.
I hope that is not a problem. After all, the code works, and
even if it didn't work, there are currently no programs that
depend on it for them to break.
Bruno Haible <[EMAIL PROTECTED]> writes:
> 'popcount' is not a particularly good name. When I first stumbled on a
> function of this name in the sources of GNU gettext, it took me some time
> to understand what it meant.
>
> The ANSI Common Lisp name for this function is 'logcount', where the
> prefix 'log' means a "logical" interpretation of integers. This is not
> mainstream understandable either.
>
> So, how about renaming it to 'bitcount'?
"James Youngman" <[EMAIL PROTECTED]> adds:
> hamming_weight would correspond to the formal definition of the
> quantity, I think.
The name 'popcount' is not perfect, but it is a well-known name
for this function. That is what it is called by, e.g., GCC,
Wikipedia, and _Hacker's Delight_.
I don't see why anyone would have trouble understanding
population count, unless an opaque, uncommented implementation
made it necessary to reverse-engineer the calculation. That is
why I added an explanatory comment at the top of each function
definition:
/* Compute and return the population count of X, that is, the
number of 1-bits set in X. */
I agree that 'logcount' is not an improvement. But I don't think
that 'bitcount' is a significant improvement. To me, it has a
much less specific name than 'popcount', which is a well-known
name.
I do agree that 'hamming_weight' is a precise name for this
function. But it is not a descriptive name: one must know by
rote what a Hamming weight is. I think that "population count"
is far more logical.
Bruno Haible <[EMAIL PROTECTED]> continues:
>> +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
>> +#define POPCOUNT_CALCULATION(NAME) \
>> + return __builtin_##NAME (x);
>
> This will not work with CC="gcc -fno-builtin". Better use an autoconf test.
GCC documentation explicitly condones usage of __builtin
functions with -fno-builtin:
`-fno-builtin'
`-fno-builtin-FUNCTION'
Don't recognize built-in functions that do not begin
with `__builtin_' as prefix. ...
...if you wish to enable built-in functions selectively
when using `-fno-builtin' or `-ffreestanding', you may
define macros such as:
#define abs(n) __builtin_abs ((n))
#define strcpy(d, s) __builtin_strcpy ((d), (s))
Actual testing with GCC bears this out:
[EMAIL PROTECTED]:~/gnulib/gnulib(1)$ cat test.c
#include <stdio.h>
int
main (void)
{
printf ("%d\n", __builtin_popcount (5));
return 0;
}
[EMAIL PROTECTED]:~/gnulib/gnulib(0)$ gcc -Wall -Wextra -fno-builtin test.c
[EMAIL PROTECTED]:~/gnulib/gnulib(0)$ ./a.out
2
[EMAIL PROTECTED]:~/gnulib/gnulib(0)$ gcc -v
[...]
gcc version 4.1.3 20070518 (prerelease) (Debian 4.1.2-8)
[EMAIL PROTECTED]:~/gnulib/gnulib(0)$
>> x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
>> x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
>> x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f);
>> x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
>> return (x >> 16) + (x & 0xff);
>
> You can reduce the size of some of the constants somewhat, allowing more
> efficient code, and eliminate one & operation, like this:
>
> x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
> x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
> x = (x >> 16) + (x & 0xffff);
> x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
> return (x >> 8) + (x & 0x00ff);
>
> Also, to avoid compiler warnings, can you add an 'U' suffix to the constants?
Thank you for these improvements. I installed this:
2007-07-23 Ben Pfaff <[EMAIL PROTECTED]>
* lib/popcount.h (popcount32): Reduce size of constants, to allow
better code generation, and add U to large constants to avoid
warnings, in non-GCC case.
Suggested by Bruno Haible.
diff -u -p -r1.3 popcount.h
--- lib/popcount.h 24 Jul 2007 02:13:15 -0000 1.3
+++ lib/popcount.h 24 Jul 2007 02:33:48 -0000
@@ -41,11 +41,11 @@
static inline int
popcount32 (unsigned int x)
{
- x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
- x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
- x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f);
- x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
- return (x >> 16) + (x & 0xff);
+ x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
+ x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
+ x = (x >> 16) + (x & 0xffff);
+ x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
+ return (x >> 8) + (x & 0x00ff);
}
#endif
--
Ben Pfaff
[EMAIL PROTECTED]
