changeset 15390:25fd80a52583

ffs: new module 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 <eblake@redhat.com>
author Eric Blake <eblake@redhat.com>
date Mon, 11 Jul 2011 17:05:34 -0600
parents 8c0f49d5e806
children af02f1770a6a
files ChangeLog MODULES.html.sh doc/posix-functions/ffs.texi lib/ffs.c lib/strings.in.h m4/ffs.m4 m4/strings_h.m4 modules/ffs modules/ffs-tests modules/strings tests/test-ffs.c
diffstat 11 files changed, 187 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -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
+++ b/MODULES.html.sh
@@ -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
+++ b/doc/posix-functions/ffs.texi
@@ -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
new file mode 100644
--- /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
+}
--- a/lib/strings.in.h
+++ b/lib/strings.in.h
@@ -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.
new file mode 100644
--- /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
+])
--- 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 @@
   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])
 ])
new file mode 100644
--- /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
new file mode 100644
--- /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
--- a/modules/strings
+++ b/modules/strings
@@ -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; \
new file mode 100644
--- /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;
+}