[PATCH] ffs: new module

[Eric Blake]

Libvirt wants to use ffs() to avoid dragging in -lm for log2().

* modules/ffs: New file.
* m4/ffs.m4: Likewise.
* lib/ffs.c: Likewise.
* m4/strings_h.m4 (gl_HEADER_STRINGS_H_DEFAULTS): Add default.
* modules/strings (Makefile.am): Substitute witness.
(Depends-on): Add c++defs.
* lib/strings.in.h (ffs): Declare.
* modules/ffs-tests: New test file.
* tests/test-ffs.c: Test new module.
* MODULES.html.sh (Integer arithmetic functions): Mention it.
* doc/posix-functions/ffs.texi (ffs): Likewise.

Signed-off-by: Eric Blake <address@hidden>
---

The generic glibc implemention is somewhat slower than this.  The
gcc builtin will usually take effect for a single assembly
instruction on x86 platforms.

 ChangeLog                    |   13 ++++++++++
 MODULES.html.sh              |    1 +
 doc/posix-functions/ffs.texi |    8 +++---
 lib/ffs.c                    |   38 ++++++++++++++++++++++++++++++
 lib/strings.in.h             |   16 +++++++++++++
 m4/ffs.m4                    |   13 ++++++++++
 m4/strings_h.m4              |    8 ++++--
 modules/ffs                  |   27 +++++++++++++++++++++
 modules/ffs-tests            |   12 +++++++++
 modules/strings              |    6 ++++-
 tests/test-ffs.c             |   52 ++++++++++++++++++++++++++++++++++++++++++
 11 files changed, 186 insertions(+), 8 deletions(-)
 create mode 100644 lib/ffs.c
 create mode 100644 m4/ffs.m4
 create mode 100644 modules/ffs
 create mode 100644 modules/ffs-tests
 create mode 100644 tests/test-ffs.c

diff --git a/ChangeLog b/ChangeLog
index e1e12f6..471ce43 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,18 @@
 2011-07-11  Eric Blake  <address@hidden>

+       ffs: new module
+       * modules/ffs: New file.
+       * m4/ffs.m4: Likewise.
+       * lib/ffs.c: Likewise.
+       * m4/strings_h.m4 (gl_HEADER_STRINGS_H_DEFAULTS): Add default.
+       * modules/strings (Makefile.am): Substitute witness.
+       (Depends-on): Add c++defs.
+       * lib/strings.in.h (ffs): Declare.
+       * modules/ffs-tests: New test file.
+       * tests/test-ffs.c: Test new module.
+       * MODULES.html.sh (Integer arithmetic functions): Mention it.
+       * doc/posix-functions/ffs.texi (ffs): Likewise.
+
        regex: avoid compiler warning
        * lib/regex.c (includes): Include <strings.h>, for use of
        strcasecmp in regcomp.c.
diff --git a/MODULES.html.sh b/MODULES.html.sh
index f46cc56..923fba5 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1736,6 +1736,7 @@ func_all_modules ()

   func_begin_table
   func_module count-one-bits
+  func_module ffs
   func_module gcd
   func_module minmax
   func_end_table
diff --git a/doc/posix-functions/ffs.texi b/doc/posix-functions/ffs.texi
index b401c30..a79b9ad 100644
--- a/doc/posix-functions/ffs.texi
+++ b/doc/posix-functions/ffs.texi
@@ -4,15 +4,15 @@ ffs

 POSIX specification:@* 
@url{http://www.opengroup.org/onlinepubs/9699919799/functions/ffs.html}

-Gnulib module: ---
+Gnulib module: ffs

 Portability problems fixed by Gnulib:
 @itemize
address@hidden
+This function is missing on some platforms:
+mingw.
 @end itemize

 Portability problems not fixed by Gnulib:
 @itemize
address@hidden
-This function is missing on some platforms:
-mingw.
 @end itemize
diff --git a/lib/ffs.c b/lib/ffs.c
new file mode 100644
index 0000000..b23210b
--- /dev/null
+++ b/lib/ffs.c
@@ -0,0 +1,38 @@
+/* ffs.c -- find the first set bit in a word.
+   Copyright (C) 2011 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 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Eric Blake.  */
+
+#include <strings.h>
+
+int
+ffs (int i)
+{
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+  return __builtin_ffs (i);
+#else
+  /* http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
+     gives this deBruijn constant for a branch-less computation, although
+     that table counted trailing zeros rather than bit position.  */
+  static unsigned int table[] = {
+    1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
+    32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
+  };
+  unsigned int u = i;
+  unsigned int bit = u & -u;
+  return table[(bit * 0x077cb531U) >> 27] - !i;
+#endif
+}
diff --git a/lib/strings.in.h b/lib/strings.in.h
index ba5a1d8..647903a 100644
--- a/lib/strings.in.h
+++ b/lib/strings.in.h
@@ -30,6 +30,8 @@
 #define address@hidden@_STRINGS_H


+/* The definitions of _GL_FUNCDECL_RPL etc. are copied here.  */
+
 /* The definition of _GL_ARG_NONNULL is copied here.  */

 /* The definition of _GL_WARN_ON_USE is copied here.  */
@@ -39,6 +41,20 @@ extern "C" {
 #endif


+  /* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFS@
+# if address@hidden@
+_GL_FUNCDECL_SYS (ffs, int, (int i));
+# endif
+_GL_CXXALIAS_SYS (ffs, int, (int i));
+_GL_CXXALIASWARN (ffs);
+#elif defined GNULIB_POSIXCHECK
+# undef ffs
+# if HAVE_RAW_DECL_FFS
+_GL_WARN_ON_USE (ffs, "ffs is not portable - use the ffs module");
+# endif
+#endif
+
 /* Compare strings S1 and S2, ignoring case, returning less than, equal to or
    greater than zero if S1 is lexicographically less than, equal to or greater
    than S2.
diff --git a/m4/ffs.m4 b/m4/ffs.m4
new file mode 100644
index 0000000..2a35078
--- /dev/null
+++ b/m4/ffs.m4
@@ -0,0 +1,13 @@
+# ffs.m4 serial 1
+dnl Copyright (C) 2011 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_FUNC_FFS],
+[
+  AC_CHECK_FUNCS_ONCE([ffs])
+  if test $ac_cv_func_ffs = no; then
+    HAVE_FFS=0
+  fi
+])
diff --git a/m4/strings_h.m4 b/m4/strings_h.m4
index 71d284b..512cb9b 100644
--- a/m4/strings_h.m4
+++ b/m4/strings_h.m4
@@ -1,5 +1,5 @@
-# Configure a replacement for <string.h>.
-# serial 3
+# Configure a replacement for <strings.h>.
+# serial 4

 # Copyright (C) 2007, 2009-2011 Free Software Foundation, Inc.
 # This file is free software; the Free Software Foundation
@@ -21,7 +21,7 @@ AC_DEFUN([gl_HEADER_STRINGS_H_BODY],
   dnl Check for declarations of anything we want to poison if the
   dnl corresponding gnulib module is not in use.
   gl_WARN_ON_USE_PREPARE([[#include <strings.h>
-    ]], [strcasecmp strncasecmp])
+    ]], [ffs strcasecmp strncasecmp])
 ])

 AC_DEFUN([gl_STRINGS_MODULE_INDICATOR],
@@ -33,7 +33,9 @@ AC_DEFUN([gl_STRINGS_MODULE_INDICATOR],

 AC_DEFUN([gl_HEADER_STRINGS_H_DEFAULTS],
 [
+  GNULIB_FFS=0;            AC_SUBST([GNULIB_FFS])
   dnl Assume proper GNU behavior unless another module says otherwise.
+  HAVE_FFS=1;              AC_SUBST([HAVE_FFS])
   HAVE_STRCASECMP=1;       AC_SUBST([HAVE_STRCASECMP])
   HAVE_DECL_STRNCASECMP=1; AC_SUBST([HAVE_DECL_STRNCASECMP])
 ])
diff --git a/modules/ffs b/modules/ffs
new file mode 100644
index 0000000..7d032b0
--- /dev/null
+++ b/modules/ffs
@@ -0,0 +1,27 @@
+Description:
+Finds the index of the least-significant set bit.
+
+Files:
+lib/ffs.c
+m4/ffs.m4
+
+Depends-on:
+strings
+
+configure.ac:
+gl_FUNC_FFS
+if test $HAVE_FFS = 0; then
+  AC_LIBOBJ([ffs])
+fi
+gl_STRINGS_MODULE_INDICATOR([ffs])
+
+Makefile.am:
+
+Include:
+<strings.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Eric Blake
diff --git a/modules/ffs-tests b/modules/ffs-tests
new file mode 100644
index 0000000..78a3973
--- /dev/null
+++ b/modules/ffs-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-ffs.c
+tests/macros.h
+tests/signature.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-ffs
+check_PROGRAMS += test-ffs
diff --git a/modules/strings b/modules/strings
index 30d2a39..87bccc4 100644
--- a/modules/strings
+++ b/modules/strings
@@ -7,6 +7,7 @@ m4/strings_h.m4

 Depends-on:
 arg-nonnull
+c++defs
 include_next
 warn-on-use

@@ -18,7 +19,7 @@ BUILT_SOURCES += strings.h

 # We need the following in order to create <strings.h> when the system
 # doesn't have one that works with the given compiler.
-strings.h: strings.in.h $(top_builddir)/config.status $(WARN_ON_USE_H) 
$(ARG_NONNULL_H)
+strings.h: strings.in.h $(top_builddir)/config.status $(CXXDEFS_H) 
$(WARN_ON_USE_H) $(ARG_NONNULL_H)
        $(AM_V_GEN)rm -f address@hidden $@ && \
        { echo '/* DO NOT EDIT! GENERATED AUTOMATICALLY! */' && \
          sed -e 's|@''GUARD_PREFIX''@|${gl_include_guard_prefix}|g' \
@@ -26,8 +27,11 @@ strings.h: strings.in.h $(top_builddir)/config.status 
$(WARN_ON_USE_H) $(ARG_NON
              -e 's|@''PRAGMA_SYSTEM_HEADER''@|@PRAGMA_SYSTEM_HEADER@|g' \
              -e 's|@''PRAGMA_COLUMNS''@|@PRAGMA_COLUMNS@|g' \
              -e 's|@''NEXT_STRINGS_H''@|$(NEXT_STRINGS_H)|g' \
+             -e 's|@''GNULIB_FFS''@|$(GNULIB_FFS)|g' \
+             -e 's|@''HAVE_FFS''@|$(HAVE_FFS)|g' \
              -e 's|@''HAVE_STRCASECMP''@|$(HAVE_STRCASECMP)|g' \
              -e 's|@''HAVE_DECL_STRNCASECMP''@|$(HAVE_DECL_STRNCASECMP)|g' \
+             -e '/definitions of _GL_FUNCDECL_RPL/r $(CXXDEFS_H)' \
              -e '/definition of _GL_ARG_NONNULL/r $(ARG_NONNULL_H)' \
              -e '/definition of _GL_WARN_ON_USE/r $(WARN_ON_USE_H)' \
              < $(srcdir)/strings.in.h; \
diff --git a/tests/test-ffs.c b/tests/test-ffs.c
new file mode 100644
index 0000000..a7c615e
--- /dev/null
+++ b/tests/test-ffs.c
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2011 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 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Eric Blake.  */
+#include <config.h>
+
+#include <strings.h>
+
+#include "signature.h"
+SIGNATURE_CHECK (ffs, int, (int));
+
+#include <limits.h>
+
+#include "macros.h"
+
+static int
+naive (int i)
+{
+  int j;
+  for (j = 0; j < CHAR_BIT * sizeof i; j++)
+    if (i & (1 << j))
+      return j + 1;
+  return 0;
+}
+
+int
+main (int argc, char *argv[])
+{
+  int i;
+
+  for (i = -128; i <= 128; i++)
+    ASSERT (ffs (i) == naive (i));
+  for (i = 0; i < CHAR_BIT * sizeof i; i++)
+    {
+      ASSERT (ffs (1 << i) == naive (1 << i));
+      ASSERT (ffs (1 << i) == i + 1);
+    }
+  return 0;
+}
-- 
1.7.4.4