Module Name: src
Committed By: joerg
Date: Tue Jul 21 13:18:44 UTC 2009
Modified Files:
src/distrib/sets/lists/comp: mi
src/distrib/sets/lists/tests: mi
src/etc/mtree: NetBSD.dist
src/include: strings.h
src/lib/libc/string: Makefile.inc
src/tests/lib/libc: Atffile Makefile
Added Files:
src/lib/libc/string: popcount.3 popcount.c popcountl.c popcountll.c
src/tests/lib/libc/string: Atffile Makefile t_popcount.c
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.1284 -r1.1285 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.44 -r1.45 src/distrib/sets/lists/tests/mi
cvs rdiff -u -r1.406 -r1.407 src/etc/mtree/NetBSD.dist
cvs rdiff -u -r1.13 -r1.14 src/include/strings.h
cvs rdiff -u -r1.72 -r1.73 src/lib/libc/string/Makefile.inc
cvs rdiff -u -r0 -r1.1 src/lib/libc/string/popcount.3 \
src/lib/libc/string/popcount.c src/lib/libc/string/popcountl.c \
src/lib/libc/string/popcountll.c
cvs rdiff -u -r1.1 -r1.2 src/tests/lib/libc/Atffile \
src/tests/lib/libc/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/lib/libc/string/Atffile \
src/tests/lib/libc/string/Makefile src/tests/lib/libc/string/t_popcount.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.1284 src/distrib/sets/lists/comp/mi:1.1285
--- src/distrib/sets/lists/comp/mi:1.1284 Mon Jul 20 17:03:36 2009
+++ src/distrib/sets/lists/comp/mi Tue Jul 21 13:18:43 2009
@@ -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
Index: src/distrib/sets/lists/tests/mi
diff -u src/distrib/sets/lists/tests/mi:1.44 src/distrib/sets/lists/tests/mi:1.45
--- src/distrib/sets/lists/tests/mi:1.44 Mon Jul 20 17:03:36 2009
+++ src/distrib/sets/lists/tests/mi Tue Jul 21 13:18:43 2009
@@ -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
Index: src/etc/mtree/NetBSD.dist
diff -u src/etc/mtree/NetBSD.dist:1.406 src/etc/mtree/NetBSD.dist:1.407
--- src/etc/mtree/NetBSD.dist:1.406 Mon Jul 20 17:03:37 2009
+++ src/etc/mtree/NetBSD.dist Tue Jul 21 13:18:43 2009
@@ -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
Index: src/include/strings.h
diff -u src/include/strings.h:1.13 src/include/strings.h:1.14
--- src/include/strings.h:1.13 Mon Apr 28 20:22:54 2008
+++ src/include/strings.h Tue Jul 21 13:18:43 2009
@@ -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);
Index: src/lib/libc/string/Makefile.inc
diff -u src/lib/libc/string/Makefile.inc:1.72 src/lib/libc/string/Makefile.inc:1.73
--- src/lib/libc/string/Makefile.inc:1.72 Sat Jul 18 09:41:23 2009
+++ src/lib/libc/string/Makefile.inc Tue Jul 21 13:18:43 2009
@@ -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
Index: src/tests/lib/libc/Atffile
diff -u src/tests/lib/libc/Atffile:1.1 src/tests/lib/libc/Atffile:1.2
--- src/tests/lib/libc/Atffile:1.1 Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/Atffile Tue Jul 21 13:18:44 2009
@@ -3,3 +3,4 @@
prop: test-suite = "NetBSD"
tp: stdlib
+tp: string
Index: src/tests/lib/libc/Makefile
diff -u src/tests/lib/libc/Makefile:1.1 src/tests/lib/libc/Makefile:1.2
--- src/tests/lib/libc/Makefile:1.1 Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/Makefile Tue Jul 21 13:18:44 2009
@@ -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
Added files:
Index: src/lib/libc/string/popcount.3
diff -u /dev/null src/lib/libc/string/popcount.3:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/lib/libc/string/popcount.3 Tue Jul 21 13:18:44 2009
@@ -0,0 +1,62 @@
+.\" $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 .
Index: src/lib/libc/string/popcount.c
diff -u /dev/null src/lib/libc/string/popcount.c:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/lib/libc/string/popcount.c Tue Jul 21 13:18:44 2009
@@ -0,0 +1,68 @@
+/* $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;
+}
Index: src/lib/libc/string/popcountl.c
diff -u /dev/null src/lib/libc/string/popcountl.c:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/lib/libc/string/popcountl.c Tue Jul 21 13:18:44 2009
@@ -0,0 +1,46 @@
+/* $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
Index: src/lib/libc/string/popcountll.c
diff -u /dev/null src/lib/libc/string/popcountll.c:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/lib/libc/string/popcountll.c Tue Jul 21 13:18:44 2009
@@ -0,0 +1,70 @@
+/* $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
Index: src/tests/lib/libc/string/Atffile
diff -u /dev/null src/tests/lib/libc/string/Atffile:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/tests/lib/libc/string/Atffile Tue Jul 21 13:18:44 2009
@@ -0,0 +1,6 @@
+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
Index: src/tests/lib/libc/string/Makefile
diff -u /dev/null src/tests/lib/libc/string/Makefile:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/tests/lib/libc/string/Makefile Tue Jul 21 13:18:44 2009
@@ -0,0 +1,9 @@
+# $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>
Index: src/tests/lib/libc/string/t_popcount.c
diff -u /dev/null src/tests/lib/libc/string/t_popcount.c:1.1
--- /dev/null Tue Jul 21 13:18:44 2009
+++ src/tests/lib/libc/string/t_popcount.c Tue Jul 21 13:18:44 2009
@@ -0,0 +1,188 @@
+/* $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();
+}
