From 0a47086e94a3077e6f49a6df8cd0a03e0ac88b56 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 6 Oct 2013 23:58:00 -0700 Subject: [PATCH] New module 'count-trailing-zeros'. * MODULES.html.sh: Mention it. * lib/count-trailing-zeros.c, lib/count-trailing-zeros.h: * m4/count-trailing-zeros.m4, modules/count-trailing-zeros: * modules/count-trailing-zeros-tests: * tests/test-count-trailing-zeros.c: New files. --- ChangeLog | 8 +++ MODULES.html.sh | 1 + lib/count-trailing-zeros.c | 3 ++ lib/count-trailing-zeros.h | 106 +++++++++++++++++++++++++++++++++++++ m4/count-trailing-zeros.m4 | 12 +++++ modules/count-trailing-zeros | 25 +++++++++ modules/count-trailing-zeros-tests | 11 ++++ tests/test-count-trailing-zeros.c | 71 +++++++++++++++++++++++++ 8 files changed, 237 insertions(+) create mode 100644 lib/count-trailing-zeros.c create mode 100644 lib/count-trailing-zeros.h create mode 100644 m4/count-trailing-zeros.m4 create mode 100644 modules/count-trailing-zeros create mode 100644 modules/count-trailing-zeros-tests create mode 100644 tests/test-count-trailing-zeros.c diff --git a/ChangeLog b/ChangeLog index 9e80e0735..01dca102a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,13 @@ 2013-10-06 Paul Eggert + New module 'count-trailing-zeros'. + * MODULES.html.sh: Mention it. + * lib/count-trailing-zeros.c, lib/count-trailing-zeros.h: + * m4/count-trailing-zeros.m4, modules/count-trailing-zeros: + * modules/count-trailing-zeros-tests: + * tests/test-count-trailing-zeros.c: + New files. + count-leading-zeros: port to MSC; support types wider than 64 bits The ideas behind the MSC port are stolen from Emacs. * lib/count-leading-zeros.h: diff --git a/MODULES.html.sh b/MODULES.html.sh index 5a563d4cb..5a0405c87 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1757,6 +1757,7 @@ func_all_modules () func_begin_table func_module count-leading-zeros func_module count-one-bits + func_module count-trailing-zeros func_module ffs func_module ffsl func_module ffsll diff --git a/lib/count-trailing-zeros.c b/lib/count-trailing-zeros.c new file mode 100644 index 000000000..f3da88674 --- /dev/null +++ b/lib/count-trailing-zeros.c @@ -0,0 +1,3 @@ +#include +#define COUNT_TRAILING_ZEROS_INLINE _GL_EXTERN_INLINE +#include "count-trailing-zeros.h" diff --git a/lib/count-trailing-zeros.h b/lib/count-trailing-zeros.h new file mode 100644 index 000000000..1dab45dc1 --- /dev/null +++ b/lib/count-trailing-zeros.h @@ -0,0 +1,106 @@ +/* count-trailing-zeros.h -- counts the number of trailing 0 bits in a word. + Copyright 2013 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 Paul Eggert. */ + +#ifndef COUNT_TRAILING_ZEROS_H +#define COUNT_TRAILING_ZEROS_H 1 + +#include +#include + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef COUNT_TRAILING_ZEROS_INLINE +# define COUNT_TRAILING_ZEROS_INLINE _GL_INLINE +#endif + +/* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN, + expand to code that computes the number of trailing zeros of the local + variable 'x' of type TYPE (an unsigned integer type) and return it + from the current function. */ +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ + return x ? BUILTIN (x) : CHAR_BIT * sizeof x; +#elif _MSC_VER +# pragma intrinsic _BitScanForward +# pragma intrinsic _BitScanForward64 +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ + do \ + { \ + unsigned long result; \ + return MSC_BUILTIN (&result, x) ? result : CHAR_BIT * sizeof x; \ + } \ + while (0) +#else +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ + do \ + { \ + int count = 0; \ + if (! x) \ + return CHAR_BIT * sizeof x; \ + for (count = 0; \ + (count < CHAR_BIT * sizeof x - 32 \ + && ! (x & 0xffffffffU)); \ + count += 32) \ + x = x >> 31 >> 1; \ + return count + count_trailing_zeros_32 (x); \ + } \ + while (0) + +/* Compute and return the number of trailing zeros in the least + significant 32 bits of X. One of these bits must be nonzero. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_32 (unsigned int x) +{ + /* http://graphics.stanford.edu/~seander/bithacks.html */ + static const char de_Bruijn_lookup[32] = { + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 + }; + return de_Bruijn_lookup[(((x & -x) * 0x077cb531U) & 0xffffffffU) >> 27]; +} +#endif + +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros (unsigned int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctz, _BitScanForward, unsigned int); +} + +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_l (unsigned long int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctzl, _BitScanForward, unsigned long int); +} + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_ll (unsigned long long int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctzll, _BitScanForward64, + unsigned long long int); +} +#endif + +_GL_INLINE_HEADER_END + +#endif diff --git a/m4/count-trailing-zeros.m4 b/m4/count-trailing-zeros.m4 new file mode 100644 index 000000000..b4a13c143 --- /dev/null +++ b/m4/count-trailing-zeros.m4 @@ -0,0 +1,12 @@ +# count-trailing-zeros.m4 +dnl Copyright (C) 2013 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_COUNT_TRAILING_ZEROS], +[ + dnl We don't need (and can't compile) count_trailing_zeros_ll + dnl unless the type 'unsigned long long int' exists. + AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) +]) diff --git a/modules/count-trailing-zeros b/modules/count-trailing-zeros new file mode 100644 index 000000000..841cfda58 --- /dev/null +++ b/modules/count-trailing-zeros @@ -0,0 +1,25 @@ +Description: +Counts the number of trailing 0-bits in a word. + +Files: +lib/count-trailing-zeros.c +lib/count-trailing-zeros.h +m4/count-trailing-zeros.m4 + +Depends-on: +extern-inline + +configure.ac: +gl_COUNT_TRAILING_ZEROS + +Makefile.am: +lib_SOURCES += count-trailing-zeros.c + +Include: +"count-trailing-zeros.h" + +License: +LGPLv2+ + +Maintainer: +all diff --git a/modules/count-trailing-zeros-tests b/modules/count-trailing-zeros-tests new file mode 100644 index 000000000..88b2d0a4e --- /dev/null +++ b/modules/count-trailing-zeros-tests @@ -0,0 +1,11 @@ +Files: +tests/test-count-trailing-zeros.c +tests/macros.h + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-count-trailing-zeros +check_PROGRAMS += test-count-trailing-zeros diff --git a/tests/test-count-trailing-zeros.c b/tests/test-count-trailing-zeros.c new file mode 100644 index 000000000..98a5f87f3 --- /dev/null +++ b/tests/test-count-trailing-zeros.c @@ -0,0 +1,71 @@ +/* Test counting of trailing zeros. + Copyright (C) 2013 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 Paul Eggert. */ + +#include + +#include "count-trailing-zeros.h" + +#include +#include + +#include "macros.h" + +#define UINT_BIT (sizeof (unsigned int) * CHAR_BIT) +#define ULONG_BIT (sizeof (unsigned long int) * CHAR_BIT) +#define ULLONG_BIT (sizeof (unsigned long long int) * CHAR_BIT) + +#ifndef ULLONG_MAX +# define HALF (1ULL << (sizeof (unsigned long long int) * CHAR_BIT - 1)) +# define ULLONG_MAX (HALF - 1 + HALF) +#endif + +int +main (int argc, char *argv[]) +{ + int i, j; + +#define TEST_COUNT_TRAILING_ZEROS(FUNC, TYPE, BITS, MAX, ONE) \ + ASSERT (FUNC (0) == BITS); \ + for (i = 0; i < BITS; i++) \ + { \ + ASSERT (FUNC (ONE << i) == i); \ + for (j = 0; j < i; j++) \ + ASSERT (FUNC ((ONE << i) | (ONE << j)) == j); \ + } \ + for (i = 0; i < 1000; i++) \ + { \ + TYPE value = rand () ^ (rand () << 31 << 1); \ + int count = 0; \ + for (j = BITS - 1; 0 <= j; j--) \ + if (value & (ONE << j)) \ + count = j; \ + ASSERT (count == FUNC (value)); \ + } \ + ASSERT (FUNC (MAX) == 0); + + TEST_COUNT_TRAILING_ZEROS (count_trailing_zeros, unsigned int, + UINT_BIT, UINT_MAX, 1U); + TEST_COUNT_TRAILING_ZEROS (count_trailing_zeros_l, unsigned long int, + ULONG_BIT, ULONG_MAX, 1UL); +#ifdef HAVE_UNSIGNED_LONG_LONG_INT + TEST_COUNT_TRAILING_ZEROS (count_trailing_zeros_ll, unsigned long long int, + ULLONG_BIT, ULLONG_MAX, 1ULL); +#endif + + return 0; +} -- 2.11.0