bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH 2/2] ffsl, ffsll: new modules


From: Eric Blake
Subject: [PATCH 2/2] ffsl, ffsll: new modules
Date: Fri, 15 Jul 2011 15:18:29 -0600

* 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 <address@hidden>
---
 ChangeLog                      |   20 +++++++++++++++
 MODULES.html.sh                |    2 +
 doc/glibc-functions/ffsl.texi  |    8 +++---
 doc/glibc-functions/ffsll.texi |    8 +++---
 lib/ffsl.c                     |    3 ++
 lib/ffsl.h                     |   47 ++++++++++++++++++++++++++++++++++++
 lib/ffsll.c                    |    3 ++
 lib/string.in.h                |   30 +++++++++++++++++++++++
 m4/ffsl.m4                     |   18 ++++++++++++++
 m4/ffsll.m4                    |   18 ++++++++++++++
 m4/string_h.m4                 |   12 ++++++---
 modules/ffsl                   |   30 +++++++++++++++++++++++
 modules/ffsl-tests             |   12 +++++++++
 modules/ffsll                  |   30 +++++++++++++++++++++++
 modules/ffsll-tests            |   12 +++++++++
 modules/string                 |    6 ++++-
 tests/test-ffsl.c              |   52 ++++++++++++++++++++++++++++++++++++++++
 tests/test-ffsll.c             |   52 ++++++++++++++++++++++++++++++++++++++++
 18 files changed, 350 insertions(+), 13 deletions(-)
 create mode 100644 lib/ffsl.c
 create mode 100644 lib/ffsl.h
 create mode 100644 lib/ffsll.c
 create mode 100644 m4/ffsl.m4
 create mode 100644 m4/ffsll.m4
 create mode 100644 modules/ffsl
 create mode 100644 modules/ffsl-tests
 create mode 100644 modules/ffsll
 create mode 100644 modules/ffsll-tests
 create mode 100644 tests/test-ffsl.c
 create mode 100644 tests/test-ffsll.c

diff --git a/ChangeLog b/ChangeLog
index 49dcd7f..8104469 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,25 @@
 2011-07-15  Eric Blake  <address@hidden>

+       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.

diff --git a/MODULES.html.sh b/MODULES.html.sh
index 6bfaf66..99de344 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1737,6 +1737,8 @@ func_all_modules ()
   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
diff --git a/doc/glibc-functions/ffsl.texi b/doc/glibc-functions/ffsl.texi
index a3fa8c6..8721b65 100644
--- a/doc/glibc-functions/ffsl.texi
+++ b/doc/glibc-functions/ffsl.texi
@@ -2,15 +2,15 @@ ffsl
 @subsection @code{ffsl}
 @findex ffsl

-Gnulib module: ---
+Gnulib module: ffsl

 Portability problems fixed by Gnulib:
 @itemize
address@hidden
+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
address@hidden
-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
diff --git a/doc/glibc-functions/ffsll.texi b/doc/glibc-functions/ffsll.texi
index b7ceeeb..ad2faf1 100644
--- a/doc/glibc-functions/ffsll.texi
+++ b/doc/glibc-functions/ffsll.texi
@@ -2,15 +2,15 @@ ffsll
 @subsection @code{ffsll}
 @findex ffsll

-Gnulib module: ---
+Gnulib module: ffsll

 Portability problems fixed by Gnulib:
 @itemize
address@hidden
+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
address@hidden
-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
diff --git a/lib/ffsl.c b/lib/ffsl.c
new file mode 100644
index 0000000..0b93796
--- /dev/null
+++ b/lib/ffsl.c
@@ -0,0 +1,3 @@
+#define FUNC ffsl
+#define TYPE long int
+#include "ffsl.h"
diff --git a/lib/ffsl.h b/lib/ffsl.h
new file mode 100644
index 0000000..673b0aa
--- /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);
+    }
+}
diff --git a/lib/ffsll.c b/lib/ffsll.c
new file mode 100644
index 0000000..d056d7c
--- /dev/null
+++ b/lib/ffsll.c
@@ -0,0 +1,3 @@
+#define FUNC ffsll
+#define TYPE long long int
+#include "ffsl.h"
diff --git a/lib/string.in.h b/lib/string.in.h
index 3b3993d..d8b753d 100644
--- 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 address@hidden@
+_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 address@hidden@
+_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@
diff --git a/m4/ffsl.m4 b/m4/ffsl.m4
new file mode 100644
index 0000000..ef3dc28
--- /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
+])
diff --git a/m4/ffsll.m4 b/m4/ffsll.m4
new file mode 100644
index 0000000..e599cac
--- /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
+])
diff --git a/m4/string_h.m4 b/m4/string_h.m4
index df8c403..4f9f511 100644
--- 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 @@ AC_DEFUN([gl_HEADER_STRING_H_BODY],
   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_STRING_MODULE_INDICATOR],

 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 @@ AC_DEFUN([gl_HEADER_STRING_H_DEFAULTS],
   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])
diff --git a/modules/ffsl b/modules/ffsl
new file mode 100644
index 0000000..a3217ec
--- /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
diff --git a/modules/ffsl-tests b/modules/ffsl-tests
new file mode 100644
index 0000000..25154af
--- /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
diff --git a/modules/ffsll b/modules/ffsll
new file mode 100644
index 0000000..7caf100
--- /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
diff --git a/modules/ffsll-tests b/modules/ffsll-tests
new file mode 100644
index 0000000..759f382
--- /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
diff --git a/modules/string b/modules/string
index a78508c..2f5471b 100644
--- a/modules/string
+++ b/modules/string
@@ -29,6 +29,8 @@ string.h: string.in.h $(top_builddir)/config.status 
$(CXXDEFS_H) $(ARG_NONNULL_H
              -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 @@ string.h: string.in.h $(top_builddir)/config.status 
$(CXXDEFS_H) $(ARG_NONNULL_H
              -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' \
diff --git a/tests/test-ffsl.c b/tests/test-ffsl.c
new file mode 100644
index 0000000..2da2f5c
--- /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;
+}
diff --git a/tests/test-ffsll.c b/tests/test-ffsll.c
new file mode 100644
index 0000000..c0fd426
--- /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;
+}
-- 
1.7.1




reply via email to

[Prev in Thread] Current Thread [Next in Thread]