From: Ben Pfaff Date: Mon, 23 Jul 2007 00:21:20 +0000 (+0000) Subject: New module: popcount. X-Git-Tag: cvs-readonly~102 X-Git-Url: http://erislabs.net/gitweb/?p=gnulib.git;a=commitdiff_plain;h=da8a3eac76a3f2aaac19fcc51f56f751876f3f41 New module: popcount. * MODULES.html.sh: Add popcount. * modules/popcount: New file. * modules/popcount-tests: New file. * tests/test-popcount.c: New file. * lib/popcount.h: New file. * m4/popcount.m4: New file. --- diff --git a/ChangeLog b/ChangeLog index da8891a49..0094fc8fb 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2007-07-22 Ben Pfaff + + New module: popcount. + * MODULES.html.sh: Add popcount. + * modules/popcount: New file. + * modules/popcount-tests: New file. + * tests/test-popcount.c: New file. + * lib/popcount.h: New file. + * m4/popcount.m4: New file. + 2007-07-22 Paul Eggert * build-aux/announce-gen: Update to GPLv3. diff --git a/MODULES.html.sh b/MODULES.html.sh index 98719ba51..a3a6adbd7 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1611,6 +1611,7 @@ func_all_modules () func_begin_table func_module gcd func_module minmax + func_module popcount func_end_table element="Environment variables " diff --git a/lib/popcount.h b/lib/popcount.h new file mode 100644 index 000000000..a25b81934 --- /dev/null +++ b/lib/popcount.h @@ -0,0 +1,60 @@ +/* popcount.h -- population count + Copyright (C) 2007 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Written by Ben Pfaff. */ + +#ifndef POPCOUNT_H +# define POPCOUNT_H 1 + +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4) +#define POPCOUNT_CALCULATION(NAME) \ + return __builtin_##NAME (x); +#else +#define POPCOUNT_CALCULATION(NAME) \ + int pop; \ + for (pop = 0; x != 0; pop++) \ + x &= x - 1; \ + return pop; +#endif + +/* Compute and return the population count of X, that is, the + number of 1-bits set in X. */ +static inline int +popcount (unsigned int x) +{ + POPCOUNT_CALCULATION (popcount); +} + +/* Compute and return the population count of X, that is, the + number of 1-bits set in X. */ +static inline int +popcountl (unsigned long int x) +{ + POPCOUNT_CALCULATION (popcountl); +} + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Compute and return the population count of X, that is, the + number of 1-bits set in X. */ +static inline int +popcountll (unsigned long long int x) +{ + POPCOUNT_CALCULATION (popcountll); +} +#endif + +#endif /* POPCOUNT_H */ diff --git a/m4/popcount.m4 b/m4/popcount.m4 new file mode 100644 index 000000000..5cec20c3f --- /dev/null +++ b/m4/popcount.m4 @@ -0,0 +1,12 @@ +# popcount.m4 serial 1 +dnl Copyright (C) 2007 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_POPCOUNT], +[ + dnl We don't need (and can't compile) popcountll + dnl unless the type 'unsigned long long int' exists. + AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) +]) diff --git a/modules/popcount b/modules/popcount new file mode 100644 index 000000000..885894d39 --- /dev/null +++ b/modules/popcount @@ -0,0 +1,23 @@ +Description: +Compute population count (number of 1-bits in a word). + +Files: +lib/popcount.h +m4/popcount.m4 + +Depends-on: +inline + +configure.ac: +gl_POPCOUNT + +Makefile.am: + +Include: +"popcount.h" + +License: +GPL + +Maintainer: +Ben Pfaff diff --git a/modules/popcount-tests b/modules/popcount-tests new file mode 100644 index 000000000..7579ee797 --- /dev/null +++ b/modules/popcount-tests @@ -0,0 +1,10 @@ +Files: +tests/test-popcount.c + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-popcount +check_PROGRAMS += test-popcount diff --git a/tests/test-popcount.c b/tests/test-popcount.c new file mode 100644 index 000000000..495b5748d --- /dev/null +++ b/tests/test-popcount.c @@ -0,0 +1,81 @@ +/* + * Copyright (C) 2007 Free Software Foundation + * + * 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 2, 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, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. */ + +/* Written by Ben Pfaff. */ + +#include + +#include "popcount.h" + +#include +#include +#include + +#define ASSERT(expr) \ + do \ + { \ + if (!(expr)) \ + { \ + fprintf (stderr, "%s:%d: assertion \"%s\" failed\n", \ + __FILE__, __LINE__, #expr); \ + abort (); \ + } \ + } \ + while (0) + +#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_POPCOUNT(FUNC, TYPE, BITS, MAX, ONE) \ + ASSERT (FUNC (0) == 0); \ + for (i = 0; i < BITS; i++) \ + { \ + ASSERT (FUNC (ONE << i) == 1); \ + for (j = i + 1; j < BITS; j++) \ + ASSERT (FUNC ((ONE << i) | (ONE << j)) == 2); \ + } \ + for (i = 0; i < 1000; i++) \ + { \ + TYPE value = rand () ^ (rand () << 31 << 1); \ + int count = 0; \ + for (j = 0; j < BITS; j++) \ + count += (value & (ONE << j)) != 0; \ + ASSERT (count == FUNC (value)); \ + } \ + ASSERT (FUNC (MAX) == BITS); + + TEST_POPCOUNT (popcount, unsigned int, UINT_BIT, UINT_MAX, 1U); + TEST_POPCOUNT (popcountl, unsigned long int, ULONG_BIT, ULONG_MAX, 1UL); +#ifdef HAVE_UNSIGNED_LONG_LONG_INT + TEST_POPCOUNT (popcountll, + unsigned long long int, ULLONG_BIT, ULLONG_MAX, 1ULL); +#endif + + return 0; +}