--- a/ChangeLog	Mon Jul 11 08:16:12 2011 -0600
+++ b/ChangeLog	Mon Jul 11 17:05:34 2011 -0600
@@ -1,5 +1,18 @@
 2011-07-11  Eric Blake  <eblake@redhat.com>
 
+	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.

--- a/MODULES.html.sh	Mon Jul 11 08:16:12 2011 -0600
+++ b/MODULES.html.sh	Mon Jul 11 17:05:34 2011 -0600
@@ -1736,6 +1736,7 @@
 
   func_begin_table
   func_module count-one-bits
+  func_module ffs
   func_module gcd
   func_module minmax
   func_end_table

--- a/doc/posix-functions/ffs.texi	Mon Jul 11 08:16:12 2011 -0600
+++ b/doc/posix-functions/ffs.texi	Mon Jul 11 17:05:34 2011 -0600
@@ -4,15 +4,15 @@
 
 POSIX specification:@* @url{http://www.opengroup.org/onlinepubs/9699919799/functions/ffs.html}
 
-Gnulib module: ---
+Gnulib module: ffs
 
 Portability problems fixed by Gnulib:
 @itemize
-@end itemize
-
-Portability problems not fixed by Gnulib:
-@itemize
 @item
 This function is missing on some platforms:
 mingw.
 @end itemize
+
+Portability problems not fixed by Gnulib:
+@itemize
+@end itemize

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lib/ffs.c	Mon Jul 11 17:05:34 2011 -0600
@@ -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
+}

--- a/lib/strings.in.h	Mon Jul 11 08:16:12 2011 -0600
+++ b/lib/strings.in.h	Mon Jul 11 17:05:34 2011 -0600
@@ -30,6 +30,8 @@
 #define _@GUARD_PREFIX@_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 @@
 #endif
 
 
+  /* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFS@
+# if !@HAVE_FFS@
+_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.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/m4/ffs.m4	Mon Jul 11 17:05:34 2011 -0600
@@ -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
+])

--- a/m4/strings_h.m4	Mon Jul 11 08:16:12 2011 -0600
+++ b/m4/strings_h.m4	Mon Jul 11 17:05:34 2011 -0600
@@ -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 @@
   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_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])
 ])

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/ffs	Mon Jul 11 17:05:34 2011 -0600
@@ -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

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/ffs-tests	Mon Jul 11 17:05:34 2011 -0600
@@ -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

--- a/modules/strings	Mon Jul 11 08:16:12 2011 -0600
+++ b/modules/strings	Mon Jul 11 17:05:34 2011 -0600
@@ -7,6 +7,7 @@
 
 Depends-on:
 arg-nonnull
+c++defs
 include_next
 warn-on-use
 
@@ -18,7 +19,7 @@
 
 # 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 $@-t $@ && \
 	{ echo '/* DO NOT EDIT! GENERATED AUTOMATICALLY! */' && \
 	  sed -e 's|@''GUARD_PREFIX''@|${gl_include_guard_prefix}|g' \
@@ -26,8 +27,11 @@
 	      -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; \

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-ffs.c	Mon Jul 11 17:05:34 2011 -0600
@@ -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;
+}