[Top][All Lists]
[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