From a918da4d61d28be61a12605c9d35e2cf3966d866 Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Mon, 11 Jul 2011 17:05:34 -0600 Subject: [PATCH] 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 --- ChangeLog | 13 +++++++++ MODULES.html.sh | 1 + doc/posix-functions/ffs.texi | 8 +++--- lib/ffs.c | 38 ++++++++++++++++++++++++++ lib/strings.in.h | 16 +++++++++++ m4/ffs.m4 | 13 +++++++++ m4/strings_h.m4 | 8 +++--- modules/ffs | 27 +++++++++++++++++++ modules/ffs-tests | 12 +++++++++ modules/strings | 6 ++++- tests/test-ffs.c | 52 ++++++++++++++++++++++++++++++++++++ 11 files changed, 186 insertions(+), 8 deletions(-) create mode 100644 lib/ffs.c create mode 100644 m4/ffs.m4 create mode 100644 modules/ffs create mode 100644 modules/ffs-tests create mode 100644 tests/test-ffs.c diff --git a/ChangeLog b/ChangeLog index e1e12f60d0..471ce43be3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,18 @@ 2011-07-11 Eric Blake + 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 , for use of strcasecmp in regcomp.c. diff --git a/MODULES.html.sh b/MODULES.html.sh index f46cc56a26..923fba52f9 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1736,6 +1736,7 @@ func_all_modules () func_begin_table func_module count-one-bits + func_module ffs func_module gcd func_module minmax func_end_table diff --git a/doc/posix-functions/ffs.texi b/doc/posix-functions/ffs.texi index b401c3049e..a79b9ad7ae 100644 --- 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 +@item +This function is missing on some platforms: +mingw. @end itemize Portability problems not fixed by Gnulib: @itemize -@item -This function is missing on some platforms: -mingw. @end itemize diff --git a/lib/ffs.c b/lib/ffs.c new file mode 100644 index 0000000000..b23210be13 --- /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 . */ + +/* Written by Eric Blake. */ + +#include + +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 +} diff --git a/lib/strings.in.h b/lib/strings.in.h index ba5a1d8943..647903ad6a 100644 --- 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 @@ extern "C" { #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. diff --git a/m4/ffs.m4 b/m4/ffs.m4 new file mode 100644 index 0000000000..2a350784a6 --- /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 +]) diff --git a/m4/strings_h.m4 b/m4/strings_h.m4 index 71d284b633..512cb9baf0 100644 --- a/m4/strings_h.m4 +++ b/m4/strings_h.m4 @@ -1,5 +1,5 @@ -# Configure a replacement for . -# serial 3 +# Configure a replacement for . +# serial 4 # Copyright (C) 2007, 2009-2011 Free Software Foundation, Inc. # This file is free software; the Free Software Foundation @@ -21,7 +21,7 @@ AC_DEFUN([gl_HEADER_STRINGS_H_BODY], 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 - ]], [strcasecmp strncasecmp]) + ]], [ffs strcasecmp strncasecmp]) ]) AC_DEFUN([gl_STRINGS_MODULE_INDICATOR], @@ -33,7 +33,9 @@ AC_DEFUN([gl_STRINGS_MODULE_INDICATOR], 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]) ]) diff --git a/modules/ffs b/modules/ffs new file mode 100644 index 0000000000..7d032b02a8 --- /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: + + +License: +LGPLv2+ + +Maintainer: +Eric Blake diff --git a/modules/ffs-tests b/modules/ffs-tests new file mode 100644 index 0000000000..78a3973f31 --- /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 diff --git a/modules/strings b/modules/strings index 30d2a3976d..87bccc46cb 100644 --- a/modules/strings +++ b/modules/strings @@ -7,6 +7,7 @@ m4/strings_h.m4 Depends-on: arg-nonnull +c++defs include_next warn-on-use @@ -18,7 +19,7 @@ BUILT_SOURCES += strings.h # We need the following in order to create 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 @@ strings.h: strings.in.h $(top_builddir)/config.status $(WARN_ON_USE_H) $(ARG_NON -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; \ diff --git a/tests/test-ffs.c b/tests/test-ffs.c new file mode 100644 index 0000000000..a7c615e1cf --- /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 . */ + +/* Written by Eric Blake. */ +#include + +#include + +#include "signature.h" +SIGNATURE_CHECK (ffs, int, (int)); + +#include + +#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; +} -- 2.30.2