Re: new module 'popcount'

[Ben Pfaff]

Bruno Haible <address@hidden> 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 <address@hidden> 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" <address@hidden> 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 <address@hidden> 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:

    address@hidden:~/gnulib/gnulib(1)$ cat test.c
    #include <stdio.h>
    int
    main (void)
    {
        printf ("%d\n", __builtin_popcount (5));
        return 0;
    }
    address@hidden:~/gnulib/gnulib(0)$ gcc -Wall -Wextra -fno-builtin test.c
    address@hidden:~/gnulib/gnulib(0)$ ./a.out 
    2
    address@hidden:~/gnulib/gnulib(0)$ gcc -v
[...]
    gcc version 4.1.3 20070518 (prerelease) (Debian 4.1.2-8)
    address@hidden:~/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  <address@hidden>

        * 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
address@hidden