new module 'popcount'

[Ben Pfaff-2]

I checked this in.

2007-07-22  Ben Pfaff  <blp@...>

        New module: popcount.
        * MODULES.html.sh: Add popcount.
        * modules/popcount: New file.
        * modules/popcount-tests: New file.
        * tests/test-popcount.c: New file.
        * lib/popcount.h: New file.
        * m4/popcount.m4: New file.


Index: gnulib/MODULES.html.sh
===================================================================
--- gnulib.orig/MODULES.html.sh 2007-07-22 16:37:24.000000000 -0700
+++ gnulib/MODULES.html.sh 2007-07-22 16:37:32.000000000 -0700
@@ -1611,6 +1611,7 @@
   func_begin_table
   func_module gcd
   func_module minmax
+  func_module popcount
   func_end_table
 
   element="Environment variables <stdlib.h>"
Index: gnulib/lib/popcount.h
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/lib/popcount.h 2007-07-22 17:20:45.000000000 -0700
@@ -0,0 +1,60 @@
+/* popcount.h -- population count
+   Copyright (C) 2007 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Written by Ben Pfaff.  */
+
+#ifndef POPCOUNT_H
+# define POPCOUNT_H 1
+
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
+#define POPCOUNT_CALCULATION(NAME)              \
+        return __builtin_##NAME (x);
+#else
+#define POPCOUNT_CALCULATION(NAME)              \
+        int pop;                                \
+        for (pop = 0; x != 0; pop++)            \
+          x &= x - 1;                           \
+        return pop;
+#endif
+
+/* Compute and return the population count of X, that is, the
+   number of 1-bits set in X. */
+static inline int
+popcount (unsigned int x)
+{
+  POPCOUNT_CALCULATION (popcount);
+}
+
+/* Compute and return the population count of X, that is, the
+   number of 1-bits set in X. */
+static inline int
+popcountl (unsigned long int x)
+{
+  POPCOUNT_CALCULATION (popcountl);
+}
+
+#if HAVE_UNSIGNED_LONG_LONG_INT
+/* Compute and return the population count of X, that is, the
+   number of 1-bits set in X. */
+static inline int
+popcountll (unsigned long long int x)
+{
+  POPCOUNT_CALCULATION (popcountll);
+}
+#endif
+
+#endif /* POPCOUNT_H */
Index: gnulib/m4/popcount.m4
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/m4/popcount.m4 2007-07-22 16:50:23.000000000 -0700
@@ -0,0 +1,12 @@
+# popcount.m4 serial 1
+dnl Copyright (C) 2007 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_POPCOUNT],
+[
+  dnl We don't need (and can't compile) popcountll
+  dnl unless the type 'unsigned long long int' exists.
+  AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT])
+])
Index: gnulib/modules/popcount
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/modules/popcount 2007-07-22 16:39:52.000000000 -0700
@@ -0,0 +1,23 @@
+Description:
+Compute population count (number of 1-bits in a word).
+
+Files:
+lib/popcount.h
+m4/popcount.m4
+
+Depends-on:
+inline
+
+configure.ac:
+gl_POPCOUNT
+
+Makefile.am:
+
+Include:
+"popcount.h"
+
+License:
+GPL
+
+Maintainer:
+Ben Pfaff
Index: gnulib/modules/popcount-tests
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/modules/popcount-tests 2007-07-22 16:58:24.000000000 -0700
@@ -0,0 +1,10 @@
+Files:
+tests/test-popcount.c
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-popcount
+check_PROGRAMS += test-popcount
Index: gnulib/tests/test-popcount.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/tests/test-popcount.c 2007-07-22 17:13:16.000000000 -0700
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2007 Free Software Foundation
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.  */
+
+/* Written by Ben Pfaff.  */
+
+#include <config.h>
+
+#include "popcount.h"
+
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define ASSERT(expr)                                            \
+  do                                                            \
+    {                                                           \
+      if (!(expr))                                              \
+        {                                                       \
+          fprintf (stderr, "%s:%d: assertion \"%s\" failed\n",  \
+                   __FILE__, __LINE__, #expr);                  \
+          abort ();                                             \
+        }                                                       \
+    }                                                           \
+  while (0)
+
+#define UINT_BIT (sizeof (unsigned int) * CHAR_BIT)
+#define ULONG_BIT (sizeof (unsigned long int) * CHAR_BIT)
+#define ULLONG_BIT (sizeof (unsigned long long int) * CHAR_BIT)
+
+#ifndef ULLONG_MAX
+# define HALF (1ULL << (sizeof (unsigned long long int) * CHAR_BIT - 1))
+# define ULLONG_MAX (HALF - 1 + HALF)
+#endif
+
+int
+main (int argc, char *argv[])
+{
+  int i, j;
+
+#define TEST_POPCOUNT(FUNC, TYPE, BITS, MAX, ONE)       \
+  ASSERT (FUNC (0) == 0);                               \
+  for (i = 0; i < BITS; i++)                            \
+    {                                                   \
+      ASSERT (FUNC (ONE << i) == 1);                    \
+      for (j = i + 1; j < BITS; j++)                    \
+        ASSERT (FUNC ((ONE << i) | (ONE << j)) == 2);   \
+    }                                                   \
+  for (i = 0; i < 1000; i++)                            \
+    {                                                   \
+      TYPE value = rand () ^ (rand () << 31 << 1);      \
+      int count = 0;                                    \
+      for (j = 0; j < BITS; j++)                        \
+        count += (value & (ONE << j)) != 0;             \
+      ASSERT (count == FUNC (value));                   \
+    }                                                   \
+  ASSERT (FUNC (MAX) == BITS);
+
+  TEST_POPCOUNT (popcount, unsigned int, UINT_BIT, UINT_MAX, 1U);
+  TEST_POPCOUNT (popcountl, unsigned long int, ULONG_BIT, ULONG_MAX, 1UL);
+#ifdef HAVE_UNSIGNED_LONG_LONG_INT
+  TEST_POPCOUNT (popcountll,
+                 unsigned long long int, ULLONG_BIT, ULLONG_MAX, 1ULL);
+#endif
+
+  return 0;
+}

--
Ben Pfaff
blp@...

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Ben Pfaff on 7/22/2007 6:22 PM:
> +#define POPCOUNT_CALCULATION(NAME)              \
> +        int pop;                                \
> +        for (pop = 0; x != 0; pop++)            \
> +          x &= x - 1;                           \
> +        return pop;

You know, an O(log n) solution with no branches beats an O(n) loop any
day.  In the example below, I'm assuming sizeof(unsigned int)*CHAR_BIT ==
32, but this can be generalized to other sizes:

int
popcount (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);
}

- --
Don't work too hard, make some time for fun as well!

Eric Blake             ebb9@...
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGpAW184KuGfSFAYARAsTDAJ433J25LKKUq5E2VgHvzRmWCP1QMgCdHawU
zt2i9AkRgtF2Rnu+twAnPMs=
=Ea+C
-----END PGP SIGNATURE-----

[Ben Pfaff]

Eric Blake <ebb9@...> writes:

> You know, an O(log n) solution with no branches beats an O(n) loop any
> day.

You're right of course.  I installed the following.

I wanted to use verify_true instead of if...abort, but GCC -Wall
gave an annoying "statement with no effect" warning.

Does GNU run on anything with "unsigned long long int" wider than
64 bits?

        * lib/popcount.h: Use faster, branchless algorithm for non-GCC
        case.
        Suggested by Eric Blake.

Index: gnulib/lib/popcount.h
===================================================================
--- gnulib.orig/lib/popcount.h 2007-07-22 20:44:04.000000000 -0700
+++ gnulib/lib/popcount.h 2007-07-22 21:15:44.000000000 -0700
@@ -20,15 +20,33 @@
 #ifndef POPCOUNT_H
 # define POPCOUNT_H 1
 
+#include <limits.h>
+#include <stdlib.h>
+
 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
-#define POPCOUNT_CALCULATION(NAME)              \
+#define POPCOUNT_CALCULATION(NAME, TYPE)        \
         return __builtin_##NAME (x);
 #else
-#define POPCOUNT_CALCULATION(NAME)              \
-        int pop;                                \
-        for (pop = 0; x != 0; pop++)            \
-          x &= x - 1;                           \
+#define POPCOUNT_CALCULATION(NAME, TYPE)        \
+        int pop = popcount32 (x);               \
+        if (CHAR_BIT * sizeof (TYPE) > 32)      \
+          pop += popcount32 (x >> 31 >> 1);     \
+        if (CHAR_BIT * sizeof (TYPE) > 64)      \
+          abort ();                             \
         return pop;
+
+/* Compute and return the population count of the low 32 bits of
+   X, that is, the number of 1-bits set in its least significant
+   32 bits. */
+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);
+}
 #endif
 
 /* Compute and return the population count of X, that is, the
@@ -36,7 +54,7 @@
 static inline int
 popcount (unsigned int x)
 {
-  POPCOUNT_CALCULATION (popcount);
+  POPCOUNT_CALCULATION (popcount, unsigned int);
 }
 
 /* Compute and return the population count of X, that is, the
@@ -44,7 +62,7 @@
 static inline int
 popcountl (unsigned long int x)
 {
-  POPCOUNT_CALCULATION (popcountl);
+  POPCOUNT_CALCULATION (popcountl, unsigned long int);
 }
 
 #if HAVE_UNSIGNED_LONG_LONG_INT
@@ -53,7 +71,7 @@
 static inline int
 popcountll (unsigned long long int x)
 {
-  POPCOUNT_CALCULATION (popcountll);
+  POPCOUNT_CALCULATION (popcountll, unsigned long long int);
 }
 #endif
 

--
"Now I have to go wash my mind out with soap."
--Derick Siddoway

[Jim Meyering]

Ben Pfaff <blp@...> wrote:

> Eric Blake <ebb9@...> writes:
>
>> You know, an O(log n) solution with no branches beats an O(n) loop any
>> day.
>
> You're right of course.  I installed the following.
>
> I wanted to use verify_true instead of if...abort, but GCC -Wall
> gave an annoying "statement with no effect" warning.

You can use (void) verify_true (...).

[Bruno Haible]

Hello Ben,

> I checked this in.

OK, then we have to do the review after it's already in CVS.

> 2007-07-22  Ben Pfaff  <blp@...>
>
> New module: popcount.

'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'?

> +#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.

>   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?

Bruno

[Bruno Haible]

Ben Pfaff wrote:
> I wanted to use verify_true instead of if...abort, but GCC -Wall
> gave an annoying "statement with no effect" warning.

verify_true() is meant to be used in an expression context. In a declaration
context (e.g. at the beginning of a function or of a compound statement)
you can use verify().

Bruno

[James Youngman-5]

On 7/23/07, Bruno Haible <bruno@...> wrote:
> '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.

hamming_weight would correspond to the formal definition of the
quantity, I think.

James.

[Ben Pfaff]

Jim Meyering <jim@...> writes:
> Ben Pfaff <blp@...> wrote:
>> I wanted to use verify_true instead of if...abort, but GCC -Wall
>> gave an annoying "statement with no effect" warning.
> You can use (void) verify_true (...).

Thank you.  I don't know why that didn't occur to me.  I
installed the appended patch.

Bruno Haible <bruno@...> writes:
> verify_true() is meant to be used in an expression context. In a declaration
> context (e.g. at the beginning of a function or of a compound statement)
> you can use verify().

That's true, of course.  I wanted to put the call to it in the
middle of the block, though, because that is where it seems most
natural to me, especially if any more calls to popcount32 were to
become necessary.

2007-07-23  Ben Pfaff  <blp@...>

        * lib/popcount.h: Use verify_true instead of if...abort.
        * modules/popcount: Depend on verify module.
        Suggested by Jim Meyering.

Index: lib/popcount.h
===================================================================
RCS file: /sources/gnulib/gnulib/lib/popcount.h,v
retrieving revision 1.2
diff -u -p -r1.2 popcount.h
--- lib/popcount.h 23 Jul 2007 04:17:50 -0000 1.2
+++ lib/popcount.h 24 Jul 2007 02:11:32 -0000
@@ -22,17 +22,17 @@
 
 #include <limits.h>
 #include <stdlib.h>
+#include "verify.h"
 
 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
 #define POPCOUNT_CALCULATION(NAME, TYPE)        \
         return __builtin_##NAME (x);
 #else
-#define POPCOUNT_CALCULATION(NAME, TYPE)        \
-        int pop = popcount32 (x);               \
-        if (CHAR_BIT * sizeof (TYPE) > 32)      \
-          pop += popcount32 (x >> 31 >> 1);     \
-        if (CHAR_BIT * sizeof (TYPE) > 64)      \
-          abort ();                             \
+#define POPCOUNT_CALCULATION(NAME, TYPE)                        \
+        int pop = popcount32 (x);                               \
+        if (CHAR_BIT * sizeof (TYPE) > 32)                      \
+          pop += popcount32 (x >> 31 >> 1);                     \
+        (void) verify_true (CHAR_BIT * sizeof (TYPE) <= 64);    \
         return pop;
 
 /* Compute and return the population count of the low 32 bits of
Index: modules/popcount
===================================================================
RCS file: /sources/gnulib/gnulib/modules/popcount,v
retrieving revision 1.1
diff -u -p -r1.1 popcount
--- modules/popcount 23 Jul 2007 00:21:20 -0000 1.1
+++ modules/popcount 24 Jul 2007 02:11:33 -0000
@@ -7,6 +7,7 @@ m4/popcount.m4
 
 Depends-on:
 inline
+verify
 
 configure.ac:
 gl_POPCOUNT

--
Ben Pfaff
http://benpfaff.org

[Ben Pfaff-2]

Bruno Haible <bruno@...> 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 <bruno@...> 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" <jay@...> 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 <bruno@...> 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:

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

        * 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
blp@...

[Bruno Haible]

Ben Pfaff wrote:
> 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.

Yes, 'hamming_weight' does not help the understanding unless you are
already familiar with it.

> Bruno Haible <bruno@...> 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.
>
> Actual testing with GCC bears this out:
>
>     blp@blp:~/gnulib/gnulib(1)$ cat test.c
>     #include <stdio.h>
>     int
>     main (void)
>     {
>         printf ("%d\n", __builtin_popcount (5));
>         return 0;
>     }
>     blp@blp:~/gnulib/gnulib(0)$ gcc -Wall -Wextra -fno-builtin test.c
>     blp@blp:~/gnulib/gnulib(0)$ ./a.out
>     2

You're right. Sorry, my mistake.

Bruno

Ben Pfaff wrote:
> 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_.

Actually Wikipedia "popcount" and "population count" redirect to
"Hamming weight" :-).

> 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.

My first reaction to "popcount" is 'something to do with stacks'. My
first reaction to "population count" is 'ytf do we have census code in
gnulib?!'.

My first reaction to "Hamming weight" is 'hmm, sounds familiar and
useful, like something with a legitimate place in gnulib'.

Obviously I'm not very familiar with use of such a function, but should
that be relevant? The name "popcount" is only meaningful if you already
are familiar with the function, otherwise it leaves you wondering what
it is and why it's in gnulib. The name "Hamming weight" seems more
likely to be recognized, if only in the 'feels like I heard about that
once' sense, by average programmers.

> 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.

I probably learned what a "Hamming weight" was at some point (sure seems
like I did, anyway). However, I can't say I'd ever heard of "population
count" until this thread. Therefore I think the above argument is
invalid, "population count" is no less obscure than "Hamming weight" in
my opinion (i.e. I would say "one must know by rote" about both).

Here's another exercise: ;-)
http://www.google.com/search?hl=en&q=%22population+count%22&btnG=Search
http://www.google.com/search?hl=en&q=%22hamming+weight%22&btnG=Search

I would have to say that gcc using the name is the biggest (and possibly
only) argument for "popcount".

--
Matthew
This .sig is false

[Ben Pfaff-2]

It seems that many people do not like the name 'popcount'.
How about the name 'count_one_bits'?  It is a little longer, but
it should be possible for many people to guess what it does
without resorting to jargon.
--
Ben Pfaff
blp@...

[Ben Pfaff]

Ben Pfaff <blp@...> writes:

> It seems that many people do not like the name 'popcount'.
> How about the name 'count_one_bits'?  It is a little longer, but
> it should be possible for many people to guess what it does
> without resorting to jargon.

Having received one private vote in favor, and none against, I
checked in this change.  The patch is not interesting, but here
is the ChangeLog entry:

2007-07-24  Ben Pfaff  <blp@...>

        Improve name: "count-one-bits" is better than "popcount".
        * MODULES.html.sh: Update name.
        * lib/popcount.h: Renamed lib/count-one-bits.h.
        (popcount): Renamed count_one_bits.
        (popcountl): Renamed count_one_bits_l.
        (popcountll): Renamed count_one_bits_ll.
        * m4/popcount.m4: Renamed m4/count-one-bits.m4.
        * modules/popcount: Renamed module/count-one-bits.
        * modules/popcount-tests: Renamed module/count-one-bits-tests.
        * tests/test-popcount.c: Renamed tests/test-count-one-bits.c.
--
Ben Pfaff
http://benpfaff.org

[Paul Eggert]

I got around to reviewing this and noticed one minor problem: the code
will mistakenly reject an implementation that (say) has a 72-bit word
but where 8 bits are padding bits, i.e., they do not contribute to the
value.  This sort of trick used to be played (and perhaps still is
played; I don't know) on Unisys mainframes, and C99 allows such
implementations.  For this code, it's easy to be portable even to
these weird systems so we might as well do it that way.

Here's an (untested) patch to do this.  This patch also implement's
Bruno's suggestion to use 'verify' rather than 'verify_true'.

2007-08-14  Paul Eggert  <eggert@...>

        * lib/count-one-bits.h: Don't include <limits.h>; no longer needed
        given the changes below.
        (COUNT_ONE_BITS): Use 'verify' rather than 'verify_true'.  Work
        even on hosts that have padding bits beyond the supported 64.

--- lib/count-one-bits.h 24 Jul 2007 20:13:20 -0700 1.1
+++ lib/count-one-bits.h 14 Aug 2007 11:43:59 -0700
@@ -20,7 +20,6 @@
 #ifndef COUNT_ONE_BITS_H
 # define COUNT_ONE_BITS_H 1
 
-#include <limits.h>
 #include <stdlib.h>
 #include "verify.h"
 
@@ -29,10 +28,10 @@
         return BUILTIN (x);
 #else
 #define COUNT_ONE_BITS(BUILTIN, TYPE)                           \
+        verify ((TYPE) -1 >> 31 >> 31 <= 3);                    \
         int count = count_one_bits_32 (x);                      \
-        if (CHAR_BIT * sizeof (TYPE) > 32)                      \
+        if (1 < (TYPE) -1 >> 31)                                \
           count += count_one_bits_32 (x >> 31 >> 1);            \
-        (void) verify_true (CHAR_BIT * sizeof (TYPE) <= 64);    \
         return count;
 
 /* Compute and return the the number of 1-bits set in the least

[Bruno Haible]

Paul Eggert wrote:
>  #define COUNT_ONE_BITS(BUILTIN, TYPE)                           \
> +        verify ((TYPE) -1 >> 31 >> 31 <= 3);                    \
>          int count = count_one_bits_32 (x);                      \
> -        if (CHAR_BIT * sizeof (TYPE) > 32)                      \
> +        if (1 < (TYPE) -1 >> 31)                                \
>            count += count_one_bits_32 (x >> 31 >> 1);            \

At this point, IMO, it would be useful to add comments:

--- lib/count-one-bits.h 25 Jul 2007 03:13:20 -0000 1.1
+++ lib/count-one-bits.h 14 Aug 2007 21:50:36 -0000
@@ -20,19 +20,21 @@
 #ifndef COUNT_ONE_BITS_H
 # define COUNT_ONE_BITS_H 1
 
-#include <limits.h>
 #include <stdlib.h>
 #include "verify.h"
 
+/* Expand the code which computes the number of 1-bits of the local
+   variable 'x' of type TYPE (an unsigned integer type) and returns it
+   from the current function.  */
 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
 #define COUNT_ONE_BITS(BUILTIN, TYPE)              \
         return BUILTIN (x);
 #else
-#define COUNT_ONE_BITS(BUILTIN, TYPE)                           \
-        int count = count_one_bits_32 (x);                      \
-        if (CHAR_BIT * sizeof (TYPE) > 32)                      \
-          count += count_one_bits_32 (x >> 31 >> 1);            \
-        (void) verify_true (CHAR_BIT * sizeof (TYPE) <= 64);    \
+#define COUNT_ONE_BITS(BUILTIN, TYPE)                                       \
+        verify ((TYPE) -1 >> 31 >> 31 <= 3); /* TYPE has at most 64 bits */ \
+        int count = count_one_bits_32 (x);                                  \
+        if (1 < (TYPE) -1 >> 31) /* TYPE has more than 32 bits? */          \
+          count += count_one_bits_32 (x >> 31 >> 1);                        \
         return count;
 
 /* Compute and return the the number of 1-bits set in the least

[Ben Pfaff]

Paul Eggert <eggert@...> writes:

> I got around to reviewing this and noticed one minor problem:
> the code will mistakenly reject an implementation that (say)
> has a 72-bit word but where 8 bits are padding bits, i.e., they
> do not contribute to the value.  [...]

Bruno Haible <bruno@...> writes:

> At this point, IMO, it would be useful to add comments:

Many thanks to you both.  I committed these improvements.
--
"Implementation details are beyond the scope of the Java virtual
 machine specification.  One should not assume that every virtual
 machine implementation contains a giant squid."
--"Mr. Bunny's Big Cup o' Java"