[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
new module 'popcount'
From: |
Ben Pfaff |
Subject: |
new module 'popcount' |
Date: |
Sun, 22 Jul 2007 17:22:35 -0700 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.1 (gnu/linux) |
I checked this in.
2007-07-22 Ben Pfaff <address@hidden>
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.
Index: gnulib/MODULES.html.sh
===================================================================
--- gnulib.orig/MODULES.html.sh 2007-07-22 16:37:24.000000000 -0700
+++ gnulib/MODULES.html.sh 2007-07-22 16:37:32.000000000 -0700
@@ -1611,6 +1611,7 @@
func_begin_table
func_module gcd
func_module minmax
+ func_module popcount
func_end_table
element="Environment variables <stdlib.h>"
Index: gnulib/lib/popcount.h
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/lib/popcount.h 2007-07-22 17:20:45.000000000 -0700
@@ -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 */
Index: gnulib/m4/popcount.m4
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/m4/popcount.m4 2007-07-22 16:50:23.000000000 -0700
@@ -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])
+])
Index: gnulib/modules/popcount
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/modules/popcount 2007-07-22 16:39:52.000000000 -0700
@@ -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
Index: gnulib/modules/popcount-tests
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/modules/popcount-tests 2007-07-22 16:58:24.000000000 -0700
@@ -0,0 +1,10 @@
+Files:
+tests/test-popcount.c
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-popcount
+check_PROGRAMS += test-popcount
Index: gnulib/tests/test-popcount.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gnulib/tests/test-popcount.c 2007-07-22 17:13:16.000000000 -0700
@@ -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 <config.h>
+
+#include "popcount.h"
+
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#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;
+}
--
Ben Pfaff
address@hidden