Use Gnulib's `count-one-bits' module.

* m4/gnulib-cache.m4 (gl_MODULES): Add `count-one-bits'.

8 files changed, 293 insertions, 2 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index bc994f6e5..272da8f1e 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -9,7 +9,7 @@
 # the same distribution terms as the rest of that program.
 #
 # Generated by gnulib-tool.
-# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --aux-dir=build-aux --lgpl --libtool --macro-prefix=gl alloca extensions strcase strftime
+# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --aux-dir=build-aux --lgpl --libtool --macro-prefix=gl alloca count-one-bits extensions strcase strftime
 
 AUTOMAKE_OPTIONS = 1.5 gnits
 
@@ -63,6 +63,13 @@ EXTRA_DIST += alloca.in.h
 
 ## end   gnulib module alloca-opt
 
+## begin gnulib module count-one-bits
+
+
+EXTRA_DIST += count-one-bits.h
+
+## end   gnulib module count-one-bits
+
 ## begin gnulib module link-warning
 
 LINK_WARNING_H=$(top_srcdir)/build-aux/link-warning.h
@@ -167,6 +174,12 @@ EXTRA_libgnu_la_SOURCES += time_r.c
 
 ## end   gnulib module time_r
 
+## begin gnulib module verify
+
+libgnu_la_SOURCES += verify.h
+
+## end   gnulib module verify
+
 ## begin gnulib module wchar
 
 BUILT_SOURCES += $(WCHAR_H)
diff --git a/lib/count-one-bits.h b/lib/count-one-bits.h
new file mode 100644
index 000000000..7ecae84f0
--- /dev/null
+++ b/lib/count-one-bits.h
@@ -0,0 +1,77 @@
+/* count-one-bits.h -- counts the number of 1-bits in a word.
+   Copyright (C) 2007-2008 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU Lesser General Public License as published by
+   the Free Software Foundation; either version 3 of the License, 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 Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Ben Pfaff.  */
+
+#ifndef COUNT_ONE_BITS_H
+# define COUNT_ONE_BITS_H 1
+
+#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)                                       \
+        /* This condition is written so as to avoid shifting by more than   \
+           31 bits at once, and also avoids a random HP-UX cc bug.  */      \
+        verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* 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
+   significant 32 bits of X. */
+static inline int
+count_one_bits_32 (unsigned int x)
+{
+  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
+
+/* Compute and return the number of 1-bits set in X. */
+static inline int
+count_one_bits (unsigned int x)
+{
+  COUNT_ONE_BITS (__builtin_popcount, unsigned int);
+}
+
+/* Compute and return the number of 1-bits set in X. */
+static inline int
+count_one_bits_l (unsigned long int x)
+{
+  COUNT_ONE_BITS (__builtin_popcountl, unsigned long int);
+}
+
+#if HAVE_UNSIGNED_LONG_LONG_INT
+/* Compute and return the number of 1-bits set in X. */
+static inline int
+count_one_bits_ll (unsigned long long int x)
+{
+  COUNT_ONE_BITS (__builtin_popcountll, unsigned long long int);
+}
+#endif
+
+#endif /* COUNT_ONE_BITS_H */
diff --git a/lib/verify.h b/lib/verify.h
new file mode 100644
index 000000000..e82fa02d9
--- /dev/null
+++ b/lib/verify.h
@@ -0,0 +1,140 @@
+/* Compile-time assert-like macros.
+
+   Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU Lesser General Public License as published by
+   the Free Software Foundation; either version 3 of the License, 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 Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Paul Eggert, Bruno Haible, and Jim Meyering.  */
+
+#ifndef VERIFY_H
+# define VERIFY_H 1
+
+/* Each of these macros verifies that its argument R is nonzero.  To
+   be portable, R should be an integer constant expression.  Unlike
+   assert (R), there is no run-time overhead.
+
+   There are two macros, since no single macro can be used in all
+   contexts in C.  verify_true (R) is for scalar contexts, including
+   integer constant expression contexts.  verify (R) is for declaration
+   contexts, e.g., the top level.
+
+   Symbols ending in "__" are private to this header.
+
+   The code below uses several ideas.
+
+   * The first step is ((R) ? 1 : -1).  Given an expression R, of
+     integral or boolean or floating-point type, this yields an
+     expression of integral type, whose value is later verified to be
+     constant and nonnegative.
+
+   * Next this expression W is wrapped in a type
+     struct verify_type__ { unsigned int verify_error_if_negative_size__: W; }.
+     If W is negative, this yields a compile-time error.  No compiler can
+     deal with a bit-field of negative size.
+
+     One might think that an array size check would have the same
+     effect, that is, that the type struct { unsigned int dummy[W]; }
+     would work as well.  However, inside a function, some compilers
+     (such as C++ compilers and GNU C) allow local parameters and
+     variables inside array size expressions.  With these compilers,
+     an array size check would not properly diagnose this misuse of
+     the verify macro:
+
+       void function (int n) { verify (n < 0); }
+
+   * For the verify macro, the struct verify_type__ will need to
+     somehow be embedded into a declaration.  To be portable, this
+     declaration must declare an object, a constant, a function, or a
+     typedef name.  If the declared entity uses the type directly,
+     such as in
+
+       struct dummy {...};
+       typedef struct {...} dummy;
+       extern struct {...} *dummy;
+       extern void dummy (struct {...} *);
+       extern struct {...} *dummy (void);
+
+     two uses of the verify macro would yield colliding declarations
+     if the entity names are not disambiguated.  A workaround is to
+     attach the current line number to the entity name:
+
+       #define GL_CONCAT0(x, y) x##y
+       #define GL_CONCAT(x, y) GL_CONCAT0 (x, y)
+       extern struct {...} * GL_CONCAT(dummy,__LINE__);
+
+     But this has the problem that two invocations of verify from
+     within the same macro would collide, since the __LINE__ value
+     would be the same for both invocations.
+
+     A solution is to use the sizeof operator.  It yields a number,
+     getting rid of the identity of the type.  Declarations like
+
+       extern int dummy [sizeof (struct {...})];
+       extern void dummy (int [sizeof (struct {...})]);
+       extern int (*dummy (void)) [sizeof (struct {...})];
+
+     can be repeated.
+
+   * Should the implementation use a named struct or an unnamed struct?
+     Which of the following alternatives can be used?
+
+       extern int dummy [sizeof (struct {...})];
+       extern int dummy [sizeof (struct verify_type__ {...})];
+       extern void dummy (int [sizeof (struct {...})]);
+       extern void dummy (int [sizeof (struct verify_type__ {...})]);
+       extern int (*dummy (void)) [sizeof (struct {...})];
+       extern int (*dummy (void)) [sizeof (struct verify_type__ {...})];
+
+     In the second and sixth case, the struct type is exported to the
+     outer scope; two such declarations therefore collide.  GCC warns
+     about the first, third, and fourth cases.  So the only remaining
+     possibility is the fifth case:
+
+       extern int (*dummy (void)) [sizeof (struct {...})];
+
+   * This implementation exploits the fact that GCC does not warn about
+     the last declaration mentioned above.  If a future version of GCC
+     introduces a warning for this, the problem could be worked around
+     by using code specialized to GCC, e.g.,:
+
+       #if 4 <= __GNUC__
+       # define verify(R) \
+	   extern int (* verify_function__ (void)) \
+		      [__builtin_constant_p (R) && (R) ? 1 : -1]
+       #endif
+
+   * In C++, any struct definition inside sizeof is invalid.
+     Use a template type to work around the problem.  */
+
+
+/* Verify requirement R at compile-time, as an integer constant expression.
+   Return 1.  */
+
+# ifdef __cplusplus
+template <int w>
+  struct verify_type__ { unsigned int verify_error_if_negative_size__: w; };
+#  define verify_true(R) \
+     (!!sizeof (verify_type__<(R) ? 1 : -1>))
+# else
+#  define verify_true(R) \
+     (!!sizeof \
+      (struct { unsigned int verify_error_if_negative_size__: (R) ? 1 : -1; }))
+# endif
+
+/* Verify requirement R at compile-time, as a declaration without a
+   trailing ';'.  */
+
+# define verify(R) extern int (* verify_function__ (void)) [verify_true (R)]
+
+#endif
diff --git a/m4/.cvsignore b/m4/.cvsignore
index 57f7f3171..50f1b259d 100644
--- a/m4/.cvsignore
+++ b/m4/.cvsignore
@@ -18,3 +18,5 @@ time_h.m4
 time_r.m4
 tm_gmtoff.m4
 wchar.m4
+count-one-bits.m4
+inline.m4
diff --git a/m4/count-one-bits.m4 b/m4/count-one-bits.m4
new file mode 100644
index 000000000..8d1410a57
--- /dev/null
+++ b/m4/count-one-bits.m4
@@ -0,0 +1,12 @@
+# count-one-bits.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_COUNT_ONE_BITS],
+[
+  dnl We don't need (and can't compile) count_one_bits_ll
+  dnl unless the type 'unsigned long long int' exists.
+  AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT])
+])
diff --git a/m4/gnulib-cache.m4 b/m4/gnulib-cache.m4
index 11af0bc4d..1c0308109 100644
--- a/m4/gnulib-cache.m4
+++ b/m4/gnulib-cache.m4
@@ -15,12 +15,13 @@
 
 
 # Specification in the form of a command-line invocation:
-#   gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --aux-dir=build-aux --lgpl --libtool --macro-prefix=gl alloca extensions strcase strftime
+#   gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --aux-dir=build-aux --lgpl --libtool --macro-prefix=gl alloca count-one-bits extensions strcase strftime
 
 # Specification in the form of a few gnulib-tool.m4 macro invocations:
 gl_LOCAL_DIR([])
 gl_MODULES([
   alloca
+  count-one-bits
   extensions
   strcase
   strftime
diff --git a/m4/gnulib-comp.m4 b/m4/gnulib-comp.m4
index 614e07a06..cc9923d90 100644
--- a/m4/gnulib-comp.m4
+++ b/m4/gnulib-comp.m4
@@ -46,6 +46,8 @@ LTALLOCA=`echo "$ALLOCA" | sed 's/\.[^.]* /.lo /g;s/\.[^.]*$/.lo/'`
 changequote([, ])dnl
 AC_SUBST([LTALLOCA])
   gl_FUNC_ALLOCA
+  gl_COUNT_ONE_BITS
+  gl_INLINE
   AM_STDBOOL_H
   gl_STRCASE
   gl_FUNC_GNU_STRFTIME
@@ -184,6 +186,7 @@ AC_DEFUN([gl_FILE_LIST], [
   build-aux/link-warning.h
   lib/alloca.c
   lib/alloca.in.h
+  lib/count-one-bits.h
   lib/dummy.c
   lib/stdbool.in.h
   lib/strcasecmp.c
@@ -193,11 +196,14 @@ AC_DEFUN([gl_FILE_LIST], [
   lib/strncasecmp.c
   lib/time.in.h
   lib/time_r.c
+  lib/verify.h
   lib/wchar.in.h
   m4/alloca.m4
+  m4/count-one-bits.m4
   m4/extensions.m4
   m4/gnulib-common.m4
   m4/include_next.m4
+  m4/inline.m4
   m4/mbstate_t.m4
   m4/stdbool.m4
   m4/strcase.m4
diff --git a/m4/inline.m4 b/m4/inline.m4
new file mode 100644
index 000000000..a07076cd6
--- /dev/null
+++ b/m4/inline.m4
@@ -0,0 +1,40 @@
+# inline.m4 serial 3
+dnl Copyright (C) 2006 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.
+
+dnl Test for the 'inline' keyword or equivalent.
+dnl Define 'inline' to a supported equivalent, or to nothing if not supported,
+dnl like AC_C_INLINE does.  Also, define HAVE_INLINE if 'inline' or an
+dnl equivalent is effectively supported, i.e. if the compiler is likely to
+dnl drop unused 'static inline' functions.
+AC_DEFUN([gl_INLINE],
+[
+  AC_REQUIRE([AC_C_INLINE])
+  AC_CACHE_CHECK([whether the compiler generally respects inline],
+    [gl_cv_c_inline_effective],
+    [if test $ac_cv_c_inline = no; then
+       gl_cv_c_inline_effective=no
+     else
+       dnl GCC defines __NO_INLINE__ if not optimizing or if -fno-inline is
+       dnl specified.
+       dnl Use AC_COMPILE_IFELSE here, not AC_EGREP_CPP, because the result
+       dnl depends on optimization flags, which can be in CFLAGS.
+       dnl (AC_EGREP_CPP looks only at the CPPFLAGS.)
+       AC_COMPILE_IFELSE(
+         [AC_LANG_PROGRAM([[]],
+           [[#ifdef __NO_INLINE__
+               #error "inline is not effective"
+             #endif]])],
+         [gl_cv_c_inline_effective=yes],
+         [gl_cv_c_inline_effective=no])
+     fi
+    ])
+  if test $gl_cv_c_inline_effective = yes; then
+    AC_DEFINE([HAVE_INLINE], 1,
+      [Define to 1 if the compiler supports one of the keywords
+       'inline', '__inline__', '__inline' and effectively inlines
+       functions marked as such.])
+  fi
+])