Mercurial > hg > octave-nkf > gnulib-hg
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; +}