From 0da76a94c8668319c68af5e8c2e71c80528db5de Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Fri, 10 Aug 2012 16:51:08 -0600 Subject: [PATCH] count-leading-zeros: new module I needed gcc's clz to determine the most significant bit of a number (useful for things like truncating to a power of 2), and was surprised it is not a standardized function (the opposite direction of finding the least significant bit is given by ffs). This borrows heavily from the design of the count-one-bits module. * modules/count-leading-zeros: New module. * m4/count-leading-zeros.m4: New file. * lib/count-leading-zeros.h: Likewise. * modules/count-leading-zeros-tests: New test. * tests/test-count-leading-zeros.c: New file. * MODULES.html.sh (Integer arithmetic functions): Document it. Signed-off-by: Eric Blake --- ChangeLog | 10 ++++ MODULES.html.sh | 1 + lib/count-leading-zeros.h | 100 ++++++++++++++++++++++++++++++++++++++ m4/count-leading-zeros.m4 | 15 ++++++ modules/count-leading-zeros | 23 +++++++++ modules/count-leading-zeros-tests | 11 +++++ tests/test-count-leading-zeros.c | 71 +++++++++++++++++++++++++++ 7 files changed, 231 insertions(+) create mode 100644 lib/count-leading-zeros.h create mode 100644 m4/count-leading-zeros.m4 create mode 100644 modules/count-leading-zeros create mode 100644 modules/count-leading-zeros-tests create mode 100644 tests/test-count-leading-zeros.c diff --git a/ChangeLog b/ChangeLog index 4c318b912..80d1b6104 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2012-08-10 Eric Blake + + count-leading-zeros: new module + * modules/count-leading-zeros: New module. + * m4/count-leading-zeros.m4: New file. + * lib/count-leading-zeros.h: Likewise. + * modules/count-leading-zeros-tests: New test. + * tests/test-count-leading-zeros.c: New file. + * MODULES.html.sh (Integer arithmetic functions): Document it. + 2012-08-07 Simon Josefsson Jim Meyering diff --git a/MODULES.html.sh b/MODULES.html.sh index f4c823f31..d67c41ddc 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1755,6 +1755,7 @@ func_all_modules () func_echo "$element" func_begin_table + func_module count-leading-zeros func_module count-one-bits func_module ffs func_module ffsl diff --git a/lib/count-leading-zeros.h b/lib/count-leading-zeros.h new file mode 100644 index 000000000..4d7c291cf --- /dev/null +++ b/lib/count-leading-zeros.h @@ -0,0 +1,100 @@ +/* count-leading-zeros.h -- counts the number of leading 0 bits in a word. + Copyright (C) 2012 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. */ + +#ifndef COUNT_LEADING_ZEROS_H +# define COUNT_LEADING_ZEROS_H 1 + +#include +#include +#include "verify.h" + +/* Expand the code which computes the number of leading zeros of the local + variable 'x' of type TYPE (an unsigned integer type) and returns it + from the current function. */ +#if 0 && __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) +# define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \ + return x ? BUILTIN (x) : CHAR_BIT * sizeof x; +#else +# define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \ + /* This condition is written so as to avoid shifting by more than \ + 31 bits at once, and also avoids a random HP-UX cc bug. */ \ + verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* TYPE has at most 64 bits */ \ + int count = 0; \ + if (1 < (TYPE) -1 >> 31) { /* TYPE has more than 32 bits? */ \ + count = count_leading_zeros_32 (x >> 31 >> 1); \ + if (count < 32) \ + return count; \ + } \ + return count + count_leading_zeros_32 (x); + +/* Compute and return the number of leading zeros in the least + significant 32 bits of X. */ +static inline int +count_leading_zeros_32 (unsigned int x) +{ + int count = 0; + if (x & 0xffff0000U) + x >>= 16; + else + count += 16; + if (x & 0xff00) + x >>= 8; + else + count += 8; + if (x & 0xf0) + x >>= 4; + else + count += 4; + if (x & 0xc) + x >>= 2; + else + count += 2; + if (x & 2) + x >>= 1; + else + count++; + if (!(x & 1)) + count++; + return count; +} +#endif + +/* Compute and return the number of leading zeros in X. */ +static inline int +count_leading_zeros (unsigned int x) +{ + COUNT_LEADING_ZEROS (__builtin_clz, unsigned int); +} + +/* Compute and return the number of leading zeros in X. */ +static inline int +count_leading_zeros_l (unsigned long int x) +{ + COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int); +} + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Compute and return the number of leading zeros in X. */ +static inline int +count_leading_zeros_ll (unsigned long long int x) +{ + COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int); +} +#endif + +#endif /* COUNT_LEADING_ZEROS_H */ diff --git a/m4/count-leading-zeros.m4 b/m4/count-leading-zeros.m4 new file mode 100644 index 000000000..1efb9414e --- /dev/null +++ b/m4/count-leading-zeros.m4 @@ -0,0 +1,15 @@ +# count-leading-zeros.m4 serial 1 +dnl Copyright (C) 2012 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_LEADING_ZEROS], +[ + dnl We don't need (and can't compile) count_leading_zeros_ll + dnl unless the type 'unsigned long long int' exists. + AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) + + dnl Prerequisites of lib/count-leading-zeros.h. + AC_REQUIRE([AC_C_INLINE]) +]) diff --git a/modules/count-leading-zeros b/modules/count-leading-zeros new file mode 100644 index 000000000..60ec930a3 --- /dev/null +++ b/modules/count-leading-zeros @@ -0,0 +1,23 @@ +Description: +Counts the number of leading 0-bits in a word. + +Files: +lib/count-leading-zeros.h +m4/count-leading-zeros.m4 + +Depends-on: +verify + +configure.ac: +gl_COUNT_LEADING_ZEROS + +Makefile.am: + +Include: +"count-leading-zeros.h" + +License: +LGPLv2+ + +Maintainer: +Eric Blake diff --git a/modules/count-leading-zeros-tests b/modules/count-leading-zeros-tests new file mode 100644 index 000000000..1aff87bed --- /dev/null +++ b/modules/count-leading-zeros-tests @@ -0,0 +1,11 @@ +Files: +tests/test-count-leading-zeros.c +tests/macros.h + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-count-leading-zeros +check_PROGRAMS += test-count-leading-zeros diff --git a/tests/test-count-leading-zeros.c b/tests/test-count-leading-zeros.c new file mode 100644 index 000000000..8dadd2ce3 --- /dev/null +++ b/tests/test-count-leading-zeros.c @@ -0,0 +1,71 @@ +/* + * Copyright (C) 2012 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 "count-leading-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_LEADING_ZEROS(FUNC, TYPE, BITS, MAX, ONE) \ + ASSERT (FUNC (0) == BITS); \ + for (i = 0; i < BITS; i++) \ + { \ + ASSERT (FUNC (ONE << i) == BITS - i - 1); \ + for (j = 0; j < i; j++) \ + ASSERT (FUNC ((ONE << i) | (ONE << j)) == BITS - i - 1);\ + } \ + for (i = 0; i < 1000; i++) \ + { \ + TYPE value = rand () ^ (rand () << 31 << 1); \ + int count = 0; \ + for (j = 0; j < BITS; j++) \ + if (value & (ONE << j)) \ + count = BITS - j - 1; \ + ASSERT (count == FUNC (value)); \ + } \ + ASSERT (FUNC (MAX) == 0); + + TEST_COUNT_LEADING_ZEROS (count_leading_zeros, unsigned int, + UINT_BIT, UINT_MAX, 1U); + TEST_COUNT_LEADING_ZEROS (count_leading_zeros_l, unsigned long int, + ULONG_BIT, ULONG_MAX, 1UL); +#ifdef HAVE_UNSIGNED_LONG_LONG_INT + TEST_COUNT_LEADING_ZEROS (count_leading_zeros_ll, unsigned long long int, + ULLONG_BIT, ULLONG_MAX, 1ULL); +#endif + + return 0; +} -- 2.11.0