Mercurial > hg > octave-nkf > gnulib-hg
changeset 17037:abd788a78228
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 <eblake@redhat.com>
author | Eric Blake <eblake@redhat.com> |
---|---|
date | Fri, 10 Aug 2012 16:51:08 -0600 |
parents | 73562b8a8559 |
children | 86928fc41efe |
files | ChangeLog MODULES.html.sh lib/count-leading-zeros.h m4/count-leading-zeros.m4 modules/count-leading-zeros modules/count-leading-zeros-tests tests/test-count-leading-zeros.c |
diffstat | 7 files changed, 231 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2012-08-10 Eric Blake <eblake@redhat.com> + + 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 <simon@josefsson.org> Jim Meyering <meyering@redhat.com>
--- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1755,6 +1755,7 @@ func_echo "$element" func_begin_table + func_module count-leading-zeros func_module count-one-bits func_module ffs func_module ffsl
new file mode 100644 --- /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 <http://www.gnu.org/licenses/>. */ + +/* Written by Eric Blake. */ + +#ifndef COUNT_LEADING_ZEROS_H +# define COUNT_LEADING_ZEROS_H 1 + +#include <limits.h> +#include <stdlib.h> +#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 */
new file mode 100644 --- /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]) +])
new file mode 100644 --- /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
new file mode 100644 --- /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
new file mode 100644 --- /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 <http://www.gnu.org/licenses/>. */ + +/* Written by Eric Blake. */ + +#include <config.h> + +#include "count-leading-zeros.h" + +#include <limits.h> +#include <stdio.h> + +#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; +}