Tue Jul 21 13:18:44 2009 UTC ()
Add popcount(3) and the long and long long version. Name is inspired by
gnulib, the implementation goes back to the AMD Software Optimizer
guide. A number of platforms will want to replace the C version with
assembler code using native instructions.
(joerg)
diff -r1.1284 -r1.1285 src/distrib/sets/lists/comp/mi
diff -r1.44 -r1.45 src/distrib/sets/lists/tests/mi
diff -r1.406 -r1.407 src/etc/mtree/NetBSD.dist
diff -r1.13 -r1.14 src/include/strings.h
diff -r1.72 -r1.73 src/lib/libc/string/Makefile.inc
diff -r0 -r1.1 src/lib/libc/string/popcount.3
diff -r0 -r1.1 src/lib/libc/string/popcount.c
diff -r0 -r1.1 src/lib/libc/string/popcountl.c
diff -r0 -r1.1 src/lib/libc/string/popcountll.c
diff -r1.1 -r1.2 src/tests/lib/libc/Atffile
diff -r1.1 -r1.2 src/tests/lib/libc/Makefile
diff -r0 -r1.1 src/tests/lib/libc/string/Atffile
diff -r0 -r1.1 src/tests/lib/libc/string/Makefile
diff -r0 -r1.1 src/tests/lib/libc/string/t_popcount.c
--- src/distrib/sets/lists/comp/mi 2009/07/20 17:03:36 1.1284
+++ src/distrib/sets/lists/comp/mi 2009/07/21 13:18:43 1.1285
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1284 2009/07/20 17:03:36 joerg Exp $
+# $NetBSD: mi,v 1.1285 2009/07/21 13:18:43 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -6942,6 +6942,9 @@
./usr/share/man/cat3/pmap_unset.0 comp-c-catman .cat
./usr/share/man/cat3/pmc.0 comp-c-catman .cat
./usr/share/man/cat3/pnoutrefresh.0 comp-c-catman .cat
+./usr/share/man/cat3/popcount.0 comp-c-catman .cat
+./usr/share/man/cat3/popcountl.0 comp-c-catman .cat
+./usr/share/man/cat3/popcountll.0 comp-c-catman .cat
./usr/share/man/cat3/popen.0 comp-c-catman .cat
./usr/share/man/cat3/pos_form_cursor.0 comp-c-catman .cat
./usr/share/man/cat3/posix_memalign.0 comp-c-catman .cat
@@ -12399,6 +12402,9 @@
./usr/share/man/html3/pmap_unset.html comp-c-htmlman html
./usr/share/man/html3/pmc.html comp-c-htmlman html
./usr/share/man/html3/pnoutrefresh.html comp-c-htmlman html
+./usr/share/man/html3/popcount.html comp-c-htmlman html
+./usr/share/man/html3/popcountl.html comp-c-htmlman html
+./usr/share/man/html3/popcountll.html comp-c-htmlman html
./usr/share/man/html3/popen.html comp-c-htmlman html
./usr/share/man/html3/pos_form_cursor.html comp-c-htmlman html
./usr/share/man/html3/posix_memalign.html comp-c-htmlman html
@@ -17850,6 +17856,9 @@
./usr/share/man/man3/pmap_unset.3 comp-c-man .man
./usr/share/man/man3/pmc.3 comp-c-man .man
./usr/share/man/man3/pnoutrefresh.3 comp-c-man .man
+./usr/share/man/man3/popcount.3 comp-c-man .man
+./usr/share/man/man3/popcountl.3 comp-c-man .man
+./usr/share/man/man3/popcountll.3 comp-c-man .man
./usr/share/man/man3/popen.3 comp-c-man .man
./usr/share/man/man3/pos_form_cursor.3 comp-c-man .man
./usr/share/man/man3/posix_memalign.3 comp-c-man .man
--- src/distrib/sets/lists/tests/mi 2009/07/20 17:03:36 1.44
+++ src/distrib/sets/lists/tests/mi 2009/07/21 13:18:43 1.45
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.44 2009/07/20 17:03:36 joerg Exp $
+# $NetBSD: mi,v 1.45 2009/07/21 13:18:43 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -136,6 +136,8 @@
./usr/libdata/debug/usr/tests/lib/libc tests-lib-debug
./usr/libdata/debug/usr/tests/lib/libc/stdlib tests-lib-debug
./usr/libdata/debug/usr/tests/lib/libc/stdlib/t_mi_vector_hash.debug tests-lib-debug debug
+./usr/libdata/debug/usr/tests/lib/libc/string tests-lib-debug debug
+./usr/libdata/debug/usr/tests/lib/libc/string/t_popcount.debug tests-lib-debug debug
./usr/libdata/debug/usr/tests/modules tests-sys-debug
./usr/libdata/debug/usr/tests/modules/t_modctl.debug tests-sys-debug debug
./usr/libdata/debug/usr/tests/net tests-net-debug
@@ -847,6 +849,9 @@
./usr/tests/lib/libc/stdlib tests-lib-tests
./usr/tests/lib/libc/stdlib/Atffile tests-lib-tests
./usr/tests/lib/libc/stdlib/t_mi_vector_hash tests-lib-tests
+./usr/tests/lib/libc/string tests-lib-tests
+./usr/tests/lib/libc/string/Atffile tests-lib-tests
+./usr/tests/lib/libc/string/t_popcount tests-lib-tests
./usr/tests/modules tests-sys-tests
./usr/tests/modules/Atffile tests-sys-tests
./usr/tests/net tests-net-tests
--- src/etc/mtree/Attic/NetBSD.dist 2009/07/20 17:03:37 1.406
+++ src/etc/mtree/Attic/NetBSD.dist 2009/07/21 13:18:43 1.407
@@ -1,4 +1,4 @@
-# $NetBSD: NetBSD.dist,v 1.406 2009/07/20 17:03:37 joerg Exp $
+# $NetBSD: NetBSD.dist,v 1.407 2009/07/21 13:18:43 joerg Exp $
# @(#)4.4BSD.dist 8.1 (Berkeley) 6/13/93
# Do not customize this file as it may be overwritten on upgrades.
@@ -1437,6 +1437,7 @@
./usr/tests/lib
./usr/tests/lib/libc
./usr/tests/lib/libc/stdlib
+./usr/tests/lib/libc/string
./usr/tests/modules
./usr/tests/net
./usr/tests/net/sys
--- src/include/strings.h 2008/04/28 20:22:54 1.13
+++ src/include/strings.h 2009/07/21 13:18:43 1.14
@@ -1,4 +1,4 @@
-/* $NetBSD: strings.h,v 1.13 2008/04/28 20:22:54 martin Exp $ */
+/* $NetBSD: strings.h,v 1.14 2009/07/21 13:18:43 joerg Exp $ */
/*-
* Copyright (c) 1998 The NetBSD Foundation, Inc.
@@ -52,6 +52,9 @@
void bzero(void *, size_t);
int ffs(int);
char *index(const char *, int);
+unsigned int popcount(unsigned int) __constfunc;
+unsigned int popcountl(unsigned long) __constfunc;
+unsigned int popcountll(unsigned long long) __constfunc;
char *rindex(const char *, int);
int strcasecmp(const char *, const char *);
int strncasecmp(const char *, const char *, size_t);
--- src/lib/libc/string/Makefile.inc 2009/07/18 09:41:23 1.72
+++ src/lib/libc/string/Makefile.inc 2009/07/21 13:18:43 1.73
@@ -1,10 +1,10 @@
# from: @(#)Makefile.inc 8.1 (Berkeley) 6/4/93
-# $NetBSD: Makefile.inc,v 1.72 2009/07/18 09:41:23 dsl Exp $
+# $NetBSD: Makefile.inc,v 1.73 2009/07/21 13:18:43 joerg Exp $
# string sources
.PATH: ${ARCHDIR}/string ${.CURDIR}/string
-SRCS+= bm.c stpcpy.c stpncpy.c \
+SRCS+= bm.c popcountl.c stpcpy.c stpncpy.c \
strcasecmp.c strncasecmp.c strcasestr.c strcoll.c strdup.c \
strerror.c strlcat.c strlcpy.c strnlen.c \
strmode.c strsignal.c strtok.c \
@@ -55,9 +55,16 @@
.if empty(SRCS:Mstrrchr.S)
SRCS+= strrchr.c
.endif
+.if empty(SRCS:Mpopcount.S)
+SRCS+= popcount.c
+.endif
+.if empty(SRCS:Mpopcountll.S)
+SRCS+= popcountll.c
+.endif
MAN+= bm.3 bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 index.3 \
memccpy.3 memchr.3 memcmp.3 memcpy.3 memmem.3 memmove.3 memset.3 \
+ popcount.3 \
rindex.3 strcasecmp.3 strcat.3 strchr.3 strcmp.3 strcoll.3 \
strcpy.3 strcspn.3 strdup.3 strerror.3 string.3 strings.3 strlcpy.3 \
strlen.3 strmode.3 strpbrk.3 strrchr.3 strsep.3 \
@@ -65,6 +72,8 @@
swab.3 wcstok.3 wcswidth.3 wmemchr.3 wcsdup.3 wcscasecmp.3
MLINKS+=bm.3 bm_comp.3 bm.3 bm_exec.3 bm.3 bm_free.3
+MLINKS+=popcount.3 popcountl.3
+MLINKS+=popcount.3 popcountll.3
MLINKS+=strcasecmp.3 strncasecmp.3
MLINKS+=strcat.3 strncat.3
MLINKS+=strcmp.3 strncmp.3
.\" $NetBSD: popcount.3,v 1.1 2009/07/21 13:18:44 joerg Exp $
.\"
.\" Copyright (c) 2009 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Joerg Sonnenberger.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\" notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\" notice, this list of conditions and the following disclaimer in the
.\" documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd July 13, 2009
.Dt POPCOUNT 3
.Os
.Sh NAME
.Nm popcount ,
.Nm popcountl ,
.Nm popcountll
.Nd count number of bits set in a bit string
.Sh LIBRARY
.Lb libc
.Sh SYNOPSIS
.In strings.h
.Ft unsigned int
.Fn popcount "unsigned int value"
.Ft unsigned int
.Fn popcountl "unsigned long value"
.Ft unsigned int
.Fn popcountl "unsigned long long value"
.Sh DESCRIPTION
The
.Nm
functions returns the number of bits set in
.Fa value .
.Sh SEE ALSO
.Xr ffs 3
.Sh HISTORY
The
.Fn popcount ,
.Fn popcountl
and
.Fn popcountll
functions appeared in
.Nx 6.0 .
/* $NetBSD: popcount.c,v 1.1 2009/07/21 13:18:44 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Joerg Sonnenberger.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: popcount.c,v 1.1 2009/07/21 13:18:44 joerg Exp $");
#include <limits.h>
#include <strings.h>
#if UINT_MAX > 0xffffffffUL
#error "Unsupported architecture"
#endif
/*
* This a hybrid algorithm for bit counting between parallel counting and
* using multiplication. The idea is to sum up the bits in each Byte, so
* that the final accumulation can be done with a single multiplication.
* If the platform has a slow multiplication instruction, it can be replaced
* by the commented out version below.
*/
unsigned int
popcount(unsigned int v)
{
unsigned int c;
v = v - ((v >> 1) & 0x55555555U);
v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
v = ((v + (v >> 4)) & 0x0f0f0f0fU;
c = (v * 0x01010101U) >> 24;
/*
* v = (v >> 16) + v;
* v = (v >> 8) + v;
* c = v & 255;
*/
return c;
}
/* $NetBSD: popcountl.c,v 1.1 2009/07/21 13:18:44 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Joerg Sonnenberger.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: popcountl.c,v 1.1 2009/07/21 13:18:44 joerg Exp $");
#include <limits.h>
#include <strings.h>
#if ULONG_MAX == UINT_MAX
__strong_alias(popcountl, popcount);
#elif ULONG_MAX == ULLONG_MAX
__strong_alias(popcountll, popcount);
#else
#error "Unsupporting architecture"
#endif
/* $NetBSD: popcountll.c,v 1.1 2009/07/21 13:18:44 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Joerg Sonnenberger.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: popcountll.c,v 1.1 2009/07/21 13:18:44 joerg Exp $");
#include <strings.h>
#if ULONGLONG_MAX > 0xffffffffffffffffULL
#error "Unsupported architecture"
#endif
/*
* If unsigned long long is larger than size_t, the follow assumes that
* splitting into 32bit halfes is faster.
*
* The native pocountll version is based on the same ideas as popcount(3),
* see popcount.c for comments.
*/
#if ULONGLONG_MAX > SIZE_MAX
unsigned int
popcountll(unsigned long long v)
{
return popcount(v >> 32) + popcount(v & 0xffffffffU);
}
#else
unsigned int
popcountll(unsigned long long v)
{
unsigned int c;
v = v - ((v >> 1) & 0x5555555555555555ULL);
v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
v = ((v + (v >> 4)) & 0x0f0f0f0f0f0f0f0fULL) * 0x0101010101010101ULL;
c = v >> 56;
return c;
}
#endif
--- src/tests/lib/libc/Attic/Atffile 2009/07/20 17:03:38 1.1
+++ src/tests/lib/libc/Attic/Atffile 2009/07/21 13:18:44 1.2
@@ -3,3 +3,4 @@
prop: test-suite = "NetBSD"
tp: stdlib
+tp: string
--- src/tests/lib/libc/Makefile 2009/07/20 17:03:38 1.1
+++ src/tests/lib/libc/Makefile 2009/07/21 13:18:44 1.2
@@ -1,8 +1,8 @@
-# $NetBSD: Makefile,v 1.1 2009/07/20 17:03:38 joerg Exp $
+# $NetBSD: Makefile,v 1.2 2009/07/21 13:18:44 joerg Exp $
.include <bsd.own.mk>
-SUBDIR+= stdlib
+SUBDIR+= stdlib string
TESTSDIR= ${TESTSBASE}/lib/libc
Content-Type: application/X-atf-atffile; version="1"
X-NetBSD-Id: "$NetBSD: Atffile,v 1.1 2009/07/21 13:18:44 joerg Exp $"
prop: test-suite = "NetBSD"
tp: t_popcount
# $NetBSD: Makefile,v 1.1 2009/07/21 13:18:44 joerg Exp $
.include <bsd.own.mk>
TESTSDIR= ${TESTSBASE}/lib/libc/string
TESTS_C+= t_popcount
.include <bsd.test.mk>
/* $NetBSD: t_popcount.c,v 1.1 2009/07/21 13:18:44 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Joerg Sonnenberger.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: t_popcount.c,v 1.1 2009/07/21 13:18:44 joerg Exp $");
#include <atf-c.h>
#include <strings.h>
static unsigned int byte_count[256];
static void
popcount_init(void)
{
unsigned int i, j;
for (i = 0; i < 256; ++i) {
byte_count[i] = 0;
for (j = i; j != 0; j >>= 1) {
if (j & 1)
++byte_count[i];
}
}
}
unsigned int test_parts[256] = {
0x318e53e6U, 0x11710316U, 0x62608ffaU, 0x67e0f562U,
0xe432e82cU, 0x9862e8b2U, 0x7d96a627U, 0x3f74ad31U,
0x3cecf906U, 0xcdc0dcb4U, 0x241dab64U, 0x31e6133eU,
0x23086ad4U, 0x721d5a91U, 0xc483da53U, 0x6a62af52U,
0xf3f5c386U, 0xe0de3f77U, 0x65afe528U, 0xf4816485U,
0x40ccbf08U, 0x25df49c1U, 0xae5a6ee0U, 0xab36ccadU,
0x87e1ec29U, 0x60ca2407U, 0x49d62e47U, 0xa09f2df5U,
0xaf4c1c68U, 0x8ef08d50U, 0x624cfd2fU, 0xa6a36f20U,
0x68aaf879U, 0x0fe9deabU, 0x5c9a4060U, 0x215d8f08U,
0x55e84712U, 0xea1f1681U, 0x3a10b8a1U, 0x08e06632U,
0xcbc875e2U, 0x31e53258U, 0xcd3807a4U, 0xb9d17516U,
0x8fbfd9abU, 0x6651b555U, 0x550fb381U, 0x05061b9dU,
0x35aef3f2U, 0x9175078cU, 0xae0f14daU, 0x92a2d5f8U,
0x70d968feU, 0xe86f41c5U, 0x5cfaf39fU, 0x8499b18dU,
0xb33f879aU, 0x0a68ad3dU, 0x9323ecc1U, 0x060037ddU,
0xb91a5051U, 0xa0dbebf6U, 0x3e6aa6f1U, 0x7b422b5bU,
0x599e811eU, 0x199f7594U, 0xca453365U, 0x1cda6f48U,
0xe9c75d2cU, 0x6a873217U, 0x79c45d72U, 0x143b8e37U,
0xa11df26eU, 0xaf31f80aU, 0x311bf759U, 0x2378563cU,
0x9ab95fa5U, 0xfcf4d47cU, 0x1f7db268U, 0xd64b09e1U,
0xad7936daU, 0x7a59005cU, 0x45b173d3U, 0xc1a71b32U,
0x7d9f0de2U, 0xa9ac3792U, 0x9e7f9966U, 0x7f0b8080U,
0xece6c06fU, 0x78d92a3cU, 0x6d5f8f6cU, 0xc50ca544U,
0x5d8ded27U, 0xd27a8462U, 0x4bcd13ccU, 0xd49075f2U,
0xa8d52acfU, 0x41915d97U, 0x564f7062U, 0xefb046e2U,
0xe296277aU, 0x605b0ea3U, 0x10b2c3a1U, 0x4e8e5c66U,
0x4bd8ec04U, 0x29935be9U, 0x381839f3U, 0x555d8824U,
0xd6befddbU, 0x5d8d6d6eU, 0xb2fdb7b4U, 0xb471c8fcU,
0xc2fd325bU, 0x932d2487U, 0xbdbbadefU, 0x66c8895dU,
0x5d77857aU, 0x259f1cc0U, 0x302037faU, 0xda9aa7a8U,
0xb112c6aaU, 0x78f74192U, 0xfd4da741U, 0xfa5765c1U,
0x6ea1bc5cU, 0xd283f39cU, 0x268ae67dU, 0xdedcd134U,
0xbbf92410U, 0x6b45fb55U, 0x2f75ac71U, 0x64bf2ca5U,
0x8b99675aU, 0x3f4923b6U, 0x7e610550U, 0x04b1c06dU,
0x8f92e7c6U, 0x45cb608bU, 0x2d06d1f2U, 0x79cf387aU,
0xfd3ed225U, 0x243eee20U, 0x2cbefc6fU, 0x8286cbaaU,
0x70d4c182U, 0x054e3cc6U, 0xb66c5362U, 0x0c73fa5dU,
0x539948feU, 0xec638563U, 0x0cf04ab6U, 0xec7b52f4U,
0x58eeffceU, 0x6fe8049aU, 0xb3b33332U, 0x2e33bfdbU,
0xcc817567U, 0x71ac57c8U, 0x4bab3ac7U, 0x327c558bU,
0x82a6d279U, 0x5adf71daU, 0x1074a656U, 0x3c533c1fU,
0x82fdbe69U, 0x21b4f6afU, 0xd59580e8U, 0x0de824ebU,
0xa510941bU, 0x7cd91144U, 0xa8c10631U, 0x4c839267U,
0x5d503c2fU, 0xe1567d55U, 0x23910cc7U, 0xdb1bdc34U,
0x2a866704U, 0x33e21f0cU, 0x5c7681b4U, 0x818651caU,
0xb1d18162U, 0x225ad014U, 0xadf7d6baU, 0xac548d9bU,
0xe94736e5U, 0x2279c5f1U, 0x33215d2cU, 0xdc8ab90eU,
0xf5e3d7f2U, 0xedcb15cfU, 0xc9a43c4cU, 0xfc678fc6U,
0x43796b95U, 0x3f8b700cU, 0x867bbc72U, 0x81f71fecU,
0xd00cad7dU, 0x302c458fU, 0x8ae21accU, 0x05850ce8U,
0x7764d8e8U, 0x8a36cd68U, 0x40b44bd7U, 0x1cffaeb7U,
0x2b248f34U, 0x1eefdbafU, 0x574d7437U, 0xe86cd935U,
0xf53dd1c8U, 0x1b022513U, 0xef2d249bU, 0x94fb2b08U,
0x15d3eff8U, 0x14245e1bU, 0x82aa8425U, 0x53959028U,
0x9c5f9b80U, 0x325e0c82U, 0x3e236c24U, 0x74e1dd36U,
0x9890df3fU, 0xaf9701a2U, 0x023b3413U, 0x7634c67eU,
0x55cf5e45U, 0x56d2a95bU, 0xb6db869bU, 0xac19e260U,
0xdd310740U, 0x26d68f84U, 0x45bebf17U, 0xe4a7728fU,
0xf082e66eU, 0xb2fe3c10U, 0x2db1fa2cU, 0x4b3dfcfaU,
0xc7b3a672U, 0xaeadc67bU, 0x6cce6f2bU, 0x8263dbbfU,
0xd9724d5bU, 0xbcc767b5U, 0x8d563798U, 0x2db764b4U,
0x76e0cee7U, 0xd34f9a67U, 0x035c810aU, 0x3f56bdc1U,
0x5b3f2c84U, 0x0baca8c0U, 0xfe979a77U, 0x484ca775U,
0xbdc7f104U, 0xc06c3efbU, 0xdbc5f32cU, 0x44b017e7U,
};
ATF_TC(t_popcount);
ATF_TC(t_popcountll);
ATF_TC_HEAD(t_popcount, tc)
{
atf_tc_set_md_var(tc, "descr", "Test popcount results");
atf_tc_set_md_var(tc, "timeout", "0");
}
ATF_TC_HEAD(t_popcountll, tc)
{
atf_tc_set_md_var(tc, "descr", "Test popcountll results");
atf_tc_set_md_var(tc, "timeout", "0");
}
ATF_TC_BODY(t_popcount, tc)
{
unsigned int i, r;
popcount_init();
for (i = 0; i < 0xffffffff; ++i) {
r = byte_count[i & 255] + byte_count[(i >> 8) & 255]
+ byte_count[(i >> 16) & 255]
+ byte_count[(i >> 24) & 255];
ATF_CHECK_EQ(r, popcount(i));
}
ATF_CHECK_EQ(popcount(0xffffffff), 32);
}
ATF_TC_BODY(t_popcountll, tc)
{
unsigned int i, j, r, r2, p;
unsigned long long v;
popcount_init();
for (j = 0; j < 256; ++j) {
p = test_parts[j];
r2 = byte_count[p & 255] + byte_count[(p >> 8) & 255]
+ byte_count[(p >> 16) & 255]
+ byte_count[(p >> 24) & 255];
for (i = 0; i < 0xffffffff; ++i) {
r = byte_count[i & 255] + byte_count[(i >> 8) & 255]
+ byte_count[(i >> 16) & 255]
+ byte_count[(i >> 24) & 255] + r2;
v = (((unsigned long long)i) << 32) + p;
ATF_CHECK_EQ(r, popcountll(v));
v = (((unsigned long long)p) << 32) + i;
ATF_CHECK_EQ(r, popcountll(v));
}
}
ATF_CHECK_EQ(popcountll(0xffffffffffffffff), 64);
}
ATF_TP_ADD_TCS(tp)
{
ATF_TP_ADD_TC(tp, t_popcount);
ATF_TP_ADD_TC(tp, t_popcountll);
return atf_no_error();
}