changeset 15428:4e3a37b1ceae

ffsl, ffsll: new modules * modules/ffsl: New file. * modules/ffsll: Likewise. * m4/ffsl.m4: Likewise. * m4/ffsll.m4: Likewise. * lib/ffsl.c: Likewise. * lib/ffsl.h: Likewise. * lib/ffsll.c: Likewise. * m4/string_h.m4 (gl_HEADER_STRING_H_BODY) (gl_HEADER_STRING_H_DEFAULTS): Add defaults. * modules/string (Makefile.am): Substitute witnesses. * lib/strings.in.h (ffsl, ffsll): Declare. * modules/ffsl-tests: New test file. * modules/ffsll-tests: Likewise. * tests/test-ffsl.c: Likewise. * tests/test-ffsll.c: Likewise. * MODULES.html.sh (Integer arithmetic functions): Mention it. * doc/glibc-functions/ffsl.texi (ffsl): Likewise. * doc/glibc-functions/ffsll.texi (ffsll): Likewise. Signed-off-by: Eric Blake <eblake@redhat.com>
author Eric Blake <eblake@redhat.com>
date Fri, 15 Jul 2011 15:08:34 -0600
parents 2379b7a3f117
children cb1d00b41a66
files ChangeLog MODULES.html.sh doc/glibc-functions/ffsl.texi doc/glibc-functions/ffsll.texi lib/ffsl.c lib/ffsl.h lib/ffsll.c lib/string.in.h m4/ffsl.m4 m4/ffsll.m4 m4/string_h.m4 modules/ffsl modules/ffsl-tests modules/ffsll modules/ffsll-tests modules/string tests/test-ffsl.c tests/test-ffsll.c
diffstat 18 files changed, 352 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,25 @@
 2011-07-15  Eric Blake  <eblake@redhat.com>
 
+	ffsl, ffsll: new modules
+	* modules/ffsl: New file.
+	* modules/ffsll: Likewise.
+	* m4/ffsl.m4: Likewise.
+	* m4/ffsll.m4: Likewise.
+	* lib/ffsl.c: Likewise.
+	* lib/ffsl.h: Likewise.
+	* lib/ffsll.c: Likewise.
+	* m4/string_h.m4 (gl_HEADER_STRING_H_BODY)
+	(gl_HEADER_STRING_H_DEFAULTS): Add defaults.
+	* modules/string (Makefile.am): Substitute witnesses.
+	* lib/strings.in.h (ffsl, ffsll): Declare.
+	* modules/ffsl-tests: New test file.
+	* modules/ffsll-tests: Likewise.
+	* tests/test-ffsl.c: Likewise.
+	* tests/test-ffsll.c: Likewise.
+	* MODULES.html.sh (Integer arithmetic functions): Mention it.
+	* doc/glibc-functions/ffsl.texi (ffsl): Likewise.
+	* doc/glibc-functions/ffsll.texi (ffsll): Likewise.
+
 	ffs: fix m4 prerequisite
 	* m4/ffs.m4 (gl_FUNC_FFS): Require strings.h defaults.
 
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1737,6 +1737,8 @@
   func_begin_table
   func_module count-one-bits
   func_module ffs
+  func_module ffsl
+  func_module ffsll
   func_module gcd
   func_module minmax
   func_end_table
--- a/doc/glibc-functions/ffsl.texi
+++ b/doc/glibc-functions/ffsl.texi
@@ -2,15 +2,15 @@
 @subsection @code{ffsl}
 @findex ffsl
 
-Gnulib module: ---
+Gnulib module: ffsl
 
 Portability problems fixed by Gnulib:
 @itemize
-@end itemize
-
-Portability problems not fixed by Gnulib:
-@itemize
 @item
 This function is missing on some platforms:
 MacOS X 10.4, FreeBSD 5.2.1, NetBSD 5.0, OpenBSD 3.8, AIX 5.1, HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin, mingw, Interix 3.5, BeOS.
 @end itemize
+
+Portability problems not fixed by Gnulib:
+@itemize
+@end itemize
--- a/doc/glibc-functions/ffsll.texi
+++ b/doc/glibc-functions/ffsll.texi
@@ -2,15 +2,15 @@
 @subsection @code{ffsll}
 @findex ffsll
 
-Gnulib module: ---
+Gnulib module: ffsll
 
 Portability problems fixed by Gnulib:
 @itemize
-@end itemize
-
-Portability problems not fixed by Gnulib:
-@itemize
 @item
 This function is missing on all non-glibc platforms:
 MacOS X 10.5, FreeBSD 6.0, NetBSD 5.0, OpenBSD 3.8, AIX 5.1, HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin, mingw, Interix 3.5, BeOS.
 @end itemize
+
+Portability problems not fixed by Gnulib:
+@itemize
+@end itemize
new file mode 100644
--- /dev/null
+++ b/lib/ffsl.c
@@ -0,0 +1,3 @@
+#define FUNC ffsl
+#define TYPE long int
+#include "ffsl.h"
new file mode 100644
--- /dev/null
+++ b/lib/ffsl.h
@@ -0,0 +1,47 @@
+/* ffsl.h -- 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.  */
+
+/* This file is meant to be included by ffsl.c and ffsll.c, after
+   they have defined FUNC and TYPE.  */
+
+#include <string.h>
+
+#include <limits.h>
+#include <strings.h>
+
+#if !defined FUNC || !defined TYPE
+# error
+#endif
+
+int
+FUNC (TYPE i)
+{
+  int result = 0;
+  unsigned TYPE j = i;
+
+  /* GCC has __builtin_ffs, but it is limited to int.  */
+  if (!i)
+    return 0;
+  while (1)
+    {
+      if ((int) j)
+        return result + ffs (j);
+      j >>= CHAR_BIT * sizeof (int);
+      result += CHAR_BIT * sizeof (int);
+    }
+}
new file mode 100644
--- /dev/null
+++ b/lib/ffsll.c
@@ -0,0 +1,3 @@
+#define FUNC ffsll
+#define TYPE long long int
+#include "ffsl.h"
--- a/lib/string.in.h
+++ b/lib/string.in.h
@@ -59,6 +59,36 @@
 /* The definition of _GL_WARN_ON_USE is copied here.  */
 
 
+/* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFSL@
+# if !@HAVE_FFSL@
+_GL_FUNCDECL_SYS (ffsl, int, (long int i));
+# endif
+_GL_CXXALIAS_SYS (ffsl, int, (long int i));
+_GL_CXXALIASWARN (ffsl);
+#elif defined GNULIB_POSIXCHECK
+# undef ffsl
+# if HAVE_RAW_DECL_FFSL
+_GL_WARN_ON_USE (ffsl, "ffsl is not portable - use the ffsl module");
+# endif
+#endif
+
+
+/* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFSLL@
+# if !@HAVE_FFSLL@
+_GL_FUNCDECL_SYS (ffsll, int, (long long int i));
+# endif
+_GL_CXXALIAS_SYS (ffsll, int, (long long int i));
+_GL_CXXALIASWARN (ffsll);
+#elif defined GNULIB_POSIXCHECK
+# undef ffsll
+# if HAVE_RAW_DECL_FFSLL
+_GL_WARN_ON_USE (ffsll, "ffsll is not portable - use the ffsll module");
+# endif
+#endif
+
+
 /* Return the first instance of C within N bytes of S, or NULL.  */
 #if @GNULIB_MEMCHR@
 # if @REPLACE_MEMCHR@
new file mode 100644
--- /dev/null
+++ b/m4/ffsl.m4
@@ -0,0 +1,18 @@
+# ffsl.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_FFSL],
+[
+  AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
+
+  dnl Persuade glibc <string.h> to declare ffsl().
+  AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
+
+  AC_CHECK_FUNCS_ONCE([ffsl])
+  if test $ac_cv_func_ffsl = no; then
+    HAVE_FFSL=0
+  fi
+])
new file mode 100644
--- /dev/null
+++ b/m4/ffsll.m4
@@ -0,0 +1,18 @@
+# ffsll.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_FFSLL],
+[
+  AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
+
+  dnl Persuade glibc <string.h> to declare ffsll().
+  AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
+
+  AC_CHECK_FUNCS_ONCE([ffsll])
+  if test $ac_cv_func_ffsll = no; then
+    HAVE_FFSLL=0
+  fi
+])
--- a/m4/string_h.m4
+++ b/m4/string_h.m4
@@ -5,7 +5,7 @@
 # gives unlimited permission to copy and/or distribute it,
 # with or without modifications, as long as this notice is preserved.
 
-# serial 20
+# serial 21
 
 # Written by Paul Eggert.
 
@@ -27,9 +27,9 @@
   dnl guaranteed by C89.
   gl_WARN_ON_USE_PREPARE([[#include <string.h>
     ]],
-    [memmem mempcpy memrchr rawmemchr stpcpy stpncpy strchrnul strdup
-     strncat strndup strnlen strpbrk strsep strcasestr strtok_r strerror_r
-     strsignal strverscmp])
+    [ffsl ffsll memmem mempcpy memrchr rawmemchr stpcpy stpncpy strchrnul
+     strdup strncat strndup strnlen strpbrk strsep strcasestr strtok_r
+     strerror_r strsignal strverscmp])
 ])
 
 AC_DEFUN([gl_STRING_MODULE_INDICATOR],
@@ -43,6 +43,8 @@
 
 AC_DEFUN([gl_HEADER_STRING_H_DEFAULTS],
 [
+  GNULIB_FFSL=0;        AC_SUBST([GNULIB_FFSL])
+  GNULIB_FFSLL=0;       AC_SUBST([GNULIB_FFSLL])
   GNULIB_MEMCHR=0;      AC_SUBST([GNULIB_MEMCHR])
   GNULIB_MEMMEM=0;      AC_SUBST([GNULIB_MEMMEM])
   GNULIB_MEMPCPY=0;     AC_SUBST([GNULIB_MEMPCPY])
@@ -80,6 +82,8 @@
   GNULIB_STRVERSCMP=0;  AC_SUBST([GNULIB_STRVERSCMP])
   HAVE_MBSLEN=0;        AC_SUBST([HAVE_MBSLEN])
   dnl Assume proper GNU behavior unless another module says otherwise.
+  HAVE_FFSL=1;                  AC_SUBST([HAVE_FFSL])
+  HAVE_FFSLL=1;                 AC_SUBST([HAVE_FFSLL])
   HAVE_MEMCHR=1;                AC_SUBST([HAVE_MEMCHR])
   HAVE_DECL_MEMMEM=1;           AC_SUBST([HAVE_DECL_MEMMEM])
   HAVE_MEMPCPY=1;               AC_SUBST([HAVE_MEMPCPY])
new file mode 100644
--- /dev/null
+++ b/modules/ffsl
@@ -0,0 +1,30 @@
+Description:
+Finds the index of the least-significant set bit.
+
+Files:
+lib/ffsl.h
+lib/ffsl.c
+m4/ffsl.m4
+
+Depends-on:
+extensions
+string
+ffs             [test $HAVE_FFSL = 0]
+
+configure.ac:
+gl_FUNC_FFSL
+if test $HAVE_FFSL = 0; then
+  AC_LIBOBJ([ffsl])
+fi
+gl_STRING_MODULE_INDICATOR([ffsl])
+
+Makefile.am:
+
+Include:
+<string.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Eric Blake
new file mode 100644
--- /dev/null
+++ b/modules/ffsl-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-ffsl.c
+tests/macros.h
+tests/signature.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-ffsl
+check_PROGRAMS += test-ffsl
new file mode 100644
--- /dev/null
+++ b/modules/ffsll
@@ -0,0 +1,30 @@
+Description:
+Finds the index of the least-significant set bit.
+
+Files:
+lib/ffsl.h
+lib/ffsll.c
+m4/ffsll.m4
+
+Depends-on:
+extensions
+string
+ffs             [test $HAVE_FFSLL = 0]
+
+configure.ac:
+gl_FUNC_FFSLL
+if test $HAVE_FFSLL = 0; then
+  AC_LIBOBJ([ffsll])
+fi
+gl_STRING_MODULE_INDICATOR([ffsl])
+
+Makefile.am:
+
+Include:
+<string.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Eric Blake
new file mode 100644
--- /dev/null
+++ b/modules/ffsll-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-ffsll.c
+tests/macros.h
+tests/signature.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-ffsll
+check_PROGRAMS += test-ffsll
--- a/modules/string
+++ b/modules/string
@@ -29,6 +29,8 @@
 	      -e 's|@''PRAGMA_SYSTEM_HEADER''@|@PRAGMA_SYSTEM_HEADER@|g' \
 	      -e 's|@''PRAGMA_COLUMNS''@|@PRAGMA_COLUMNS@|g' \
 	      -e 's|@''NEXT_STRING_H''@|$(NEXT_STRING_H)|g' \
+	      -e 's/@''GNULIB_FFSL''@/$(GNULIB_FFSL)/g' \
+	      -e 's/@''GNULIB_FFSLL''@/$(GNULIB_FFSLL)/g' \
 	      -e 's/@''GNULIB_MBSLEN''@/$(GNULIB_MBSLEN)/g' \
 	      -e 's/@''GNULIB_MBSNLEN''@/$(GNULIB_MBSNLEN)/g' \
 	      -e 's/@''GNULIB_MBSCHR''@/$(GNULIB_MBSCHR)/g' \
@@ -65,7 +67,9 @@
 	      -e 's/@''GNULIB_STRSIGNAL''@/$(GNULIB_STRSIGNAL)/g' \
 	      -e 's/@''GNULIB_STRVERSCMP''@/$(GNULIB_STRVERSCMP)/g' \
 	      < $(srcdir)/string.in.h | \
-	  sed -e 's|@''HAVE_MBSLEN''@|$(HAVE_MBSLEN)|g' \
+	  sed -e 's|@''HAVE_FFSL''@|$(HAVE_FFSL)|g' \
+	      -e 's|@''HAVE_FFSLL''@|$(HAVE_FFSLL)|g' \
+	      -e 's|@''HAVE_MBSLEN''@|$(HAVE_MBSLEN)|g' \
 	      -e 's|@''HAVE_MEMCHR''@|$(HAVE_MEMCHR)|g' \
 	      -e 's|@''HAVE_DECL_MEMMEM''@|$(HAVE_DECL_MEMMEM)|g' \
 	      -e 's|@''HAVE_MEMPCPY''@|$(HAVE_MEMPCPY)|g' \
new file mode 100644
--- /dev/null
+++ b/tests/test-ffsl.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 <string.h>
+
+#include "signature.h"
+SIGNATURE_CHECK (ffsl, int, (long int));
+
+#include <limits.h>
+
+#include "macros.h"
+
+static int
+naive (long int i)
+{
+  unsigned long int j;
+  for (j = 0; j < CHAR_BIT * sizeof i; j++)
+    if (i & (1UL << j))
+      return j + 1;
+  return 0;
+}
+
+int
+main (int argc, char *argv[])
+{
+  long int i;
+
+  for (i = -128; i <= 128; i++)
+    ASSERT (ffsl (i) == naive (i));
+  for (i = 0; i < CHAR_BIT * sizeof i; i++)
+    {
+      ASSERT (ffsl (1UL << i) == naive (1UL << i));
+      ASSERT (ffsl (1UL << i) == i + 1);
+    }
+  return 0;
+}
new file mode 100644
--- /dev/null
+++ b/tests/test-ffsll.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 <string.h>
+
+#include "signature.h"
+SIGNATURE_CHECK (ffsll, int, (long long int));
+
+#include <limits.h>
+
+#include "macros.h"
+
+static int
+naive (long long int i)
+{
+  unsigned long long int j;
+  for (j = 0; j < CHAR_BIT * sizeof i; j++)
+    if (i & (1ULL << j))
+      return j + 1;
+  return 0;
+}
+
+int
+main (int argc, char *argv[])
+{
+  long long int i;
+
+  for (i = -128; i <= 128; i++)
+    ASSERT (ffsll (i) == naive (i));
+  for (i = 0; i < CHAR_BIT * sizeof i; i++)
+    {
+      ASSERT (ffsll (1ULL << i) == naive (1ULL << i));
+      ASSERT (ffsll (1ULL << i) == i + 1);
+    }
+  return 0;
+}