Module Name: src
Committed By: joerg
Date: Tue Jul 21 14:55:33 UTC 2009
Modified Files:
src/distrib/sets/lists/comp: mi
src/include: strings.h
src/lib/libc/string: Makefile.inc popcount.3
src/sys/lib/libkern: Makefile.libkern libkern.h
Added Files:
src/common/lib/libc/string: popcount32.c popcount64.c
Removed Files:
src/lib/libc/string: popcount.c popcountl.c popcountll.c
Log Message:
Move popcount et al to src/common and add popcount32/popcount64.
Requested by rm...@. MD should now override popcount32/popcount64 and
provide the aliases as fitting.
To generate a diff of this commit:
cvs rdiff -u -r0 -r1.1 src/common/lib/libc/string/popcount32.c \
src/common/lib/libc/string/popcount64.c
cvs rdiff -u -r1.1286 -r1.1287 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.14 -r1.15 src/include/strings.h
cvs rdiff -u -r1.73 -r1.74 src/lib/libc/string/Makefile.inc
cvs rdiff -u -r1.2 -r1.3 src/lib/libc/string/popcount.3
cvs rdiff -u -r1.1 -r0 src/lib/libc/string/popcount.c \
src/lib/libc/string/popcountl.c src/lib/libc/string/popcountll.c
cvs rdiff -u -r1.2 -r1.3 src/sys/lib/libkern/Makefile.libkern
cvs rdiff -u -r1.91 -r1.92 src/sys/lib/libkern/libkern.h
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.1286 src/distrib/sets/lists/comp/mi:1.1287
--- src/distrib/sets/lists/comp/mi:1.1286 Tue Jul 21 14:18:50 2009
+++ src/distrib/sets/lists/comp/mi Tue Jul 21 14:55:32 2009
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1286 2009/07/21 14:18:50 njoly Exp $
+# $NetBSD: mi,v 1.1287 2009/07/21 14:55:32 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -6946,6 +6946,8 @@
./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/popcount32.0 comp-c-catman .cat
+./usr/share/man/cat3/popcount64.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
@@ -12406,6 +12408,8 @@
./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/popcount32.html comp-c-htmlman html
+./usr/share/man/html3/popcount64.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
@@ -17860,6 +17864,8 @@
./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/popcount32.3 comp-c-man .man
+./usr/share/man/man3/popcount64.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/include/strings.h
diff -u src/include/strings.h:1.14 src/include/strings.h:1.15
--- src/include/strings.h:1.14 Tue Jul 21 13:18:43 2009
+++ src/include/strings.h Tue Jul 21 14:55:33 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: strings.h,v 1.14 2009/07/21 13:18:43 joerg Exp $ */
+/* $NetBSD: strings.h,v 1.15 2009/07/21 14:55:33 joerg Exp $ */
/*-
* Copyright (c) 1998 The NetBSD Foundation, Inc.
@@ -46,6 +46,8 @@
#include <sys/cdefs.h>
+#include <sys/inttypes.h>
+
__BEGIN_DECLS
int bcmp(const void *, const void *, size_t);
void bcopy(const void *, void *, size_t);
@@ -55,6 +57,8 @@
unsigned int popcount(unsigned int) __constfunc;
unsigned int popcountl(unsigned long) __constfunc;
unsigned int popcountll(unsigned long long) __constfunc;
+unsigned int popcount32(uint32_t) __constfunc;
+unsigned int popcount64(uint64_t) __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.73 src/lib/libc/string/Makefile.inc:1.74
--- src/lib/libc/string/Makefile.inc:1.73 Tue Jul 21 13:18:43 2009
+++ src/lib/libc/string/Makefile.inc Tue Jul 21 14:55:33 2009
@@ -1,10 +1,10 @@
# from: @(#)Makefile.inc 8.1 (Berkeley) 6/4/93
-# $NetBSD: Makefile.inc,v 1.73 2009/07/21 13:18:43 joerg Exp $
+# $NetBSD: Makefile.inc,v 1.74 2009/07/21 14:55:33 joerg Exp $
# string sources
.PATH: ${ARCHDIR}/string ${.CURDIR}/string
-SRCS+= bm.c popcountl.c stpcpy.c stpncpy.c \
+SRCS+= bm.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,11 +55,11 @@
.if empty(SRCS:Mstrrchr.S)
SRCS+= strrchr.c
.endif
-.if empty(SRCS:Mpopcount.S)
-SRCS+= popcount.c
+.if empty(SRCS:Mpopcount32.S)
+SRCS+= popcount32.c
.endif
-.if empty(SRCS:Mpopcountll.S)
-SRCS+= popcountll.c
+.if empty(SRCS:Mpopcount64.S)
+SRCS+= popcount64.c
.endif
MAN+= bm.3 bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 index.3 \
@@ -74,6 +74,8 @@
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+=popcount.3 popcount32.3
+MLINKS+=popcount.3 popcount64.3
MLINKS+=strcasecmp.3 strncasecmp.3
MLINKS+=strcat.3 strncat.3
MLINKS+=strcmp.3 strncmp.3
Index: src/lib/libc/string/popcount.3
diff -u src/lib/libc/string/popcount.3:1.2 src/lib/libc/string/popcount.3:1.3
--- src/lib/libc/string/popcount.3:1.2 Tue Jul 21 13:21:41 2009
+++ src/lib/libc/string/popcount.3 Tue Jul 21 14:55:33 2009
@@ -1,4 +1,4 @@
-.\" $NetBSD: popcount.3,v 1.2 2009/07/21 13:21:41 wiz Exp $
+.\" $NetBSD: popcount.3,v 1.3 2009/07/21 14:55:33 joerg Exp $
.\"
.\" Copyright (c) 2009 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -33,7 +33,9 @@
.Sh NAME
.Nm popcount ,
.Nm popcountl ,
-.Nm popcountll
+.Nm popcountll ,
+.Nm popcount32 ,
+.Nm popcount64
.Nd count number of bits set in a bit string
.Sh LIBRARY
.Lb libc
@@ -45,6 +47,10 @@
.Fn popcountl "unsigned long value"
.Ft unsigned int
.Fn popcountll "unsigned long long value"
+.Ft unsigned int
+.Fn popcount32 "uint32_t value"
+.Ft unsigned int
+.Fn popcount64 "uint64_t value"
.Sh DESCRIPTION
The
.Nm
@@ -56,7 +62,9 @@
The
.Fn popcount ,
.Fn popcountl ,
+.Fn popcountll ,
+.Fn popcount32
and
-.Fn popcountll
+.Fn popcount64
functions appeared in
.Nx 6.0 .
Index: src/sys/lib/libkern/Makefile.libkern
diff -u src/sys/lib/libkern/Makefile.libkern:1.2 src/sys/lib/libkern/Makefile.libkern:1.3
--- src/sys/lib/libkern/Makefile.libkern:1.2 Wed Mar 25 01:26:13 2009
+++ src/sys/lib/libkern/Makefile.libkern Tue Jul 21 14:55:33 2009
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.libkern,v 1.2 2009/03/25 01:26:13 darran Exp $
+# $NetBSD: Makefile.libkern,v 1.3 2009/07/21 14:55:33 joerg Exp $
#
# Variable definitions for libkern.
@@ -86,3 +86,13 @@
.if empty(SRCS:Mstrrchr.S)
SRCS+= strrchr.c
.endif
+
+# if no machine specific popcount32(3), build generic version
+.if empty(SRCS:Mpopcount32.S)
+SRCS+= popcount32.c
+.endif
+
+# if no machine specific popcount64(3), build generic version
+.if empty(SRCS:Mpopcount64.S)
+SRCS+= popcount64.c
+.endif
Index: src/sys/lib/libkern/libkern.h
diff -u src/sys/lib/libkern/libkern.h:1.91 src/sys/lib/libkern/libkern.h:1.92
--- src/sys/lib/libkern/libkern.h:1.91 Wed May 13 02:50:32 2009
+++ src/sys/lib/libkern/libkern.h Tue Jul 21 14:55:33 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: libkern.h,v 1.91 2009/05/13 02:50:32 pgoyette Exp $ */
+/* $NetBSD: libkern.h,v 1.92 2009/07/21 14:55:33 joerg Exp $ */
/*-
* Copyright (c) 1992, 1993
@@ -339,4 +339,9 @@
int kheapsort(void *, size_t, size_t, int (*)(const void *, const void *),
void *);
uint32_t crc32(uint32_t, const uint8_t *, size_t);
+unsigned int popcount(unsigned int) __constfunc;
+unsigned int popcountl(unsigned long) __constfunc;
+unsigned int popcountll(unsigned long long) __constfunc;
+unsigned int popcount32(uint32_t) __constfunc;
+unsigned int popcount64(uint64_t) __constfunc;
#endif /* !_LIB_LIBKERN_LIBKERN_H_ */
Added files:
Index: src/common/lib/libc/string/popcount32.c
diff -u /dev/null src/common/lib/libc/string/popcount32.c:1.1
--- /dev/null Tue Jul 21 14:55:33 2009
+++ src/common/lib/libc/string/popcount32.c Tue Jul 21 14:55:32 2009
@@ -0,0 +1,75 @@
+/* $NetBSD: popcount32.c,v 1.1 2009/07/21 14:55:32 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: popcount32.c,v 1.1 2009/07/21 14:55:32 joerg Exp $");
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#include <strings.h>
+#else
+#include <lib/libkern/libkern.h>
+#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
+popcount32(uint32_t 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;
+}
+
+#if UINT_MAX == 0xffffffffUL
+__strong_alias(popcount, popcount32);
+#endif
+
+#if ULONG_MAX == 0xffffffffU
+__strong_alias(popcountl, popcount32);
+#endif
Index: src/common/lib/libc/string/popcount64.c
diff -u /dev/null src/common/lib/libc/string/popcount64.c:1.1
--- /dev/null Tue Jul 21 14:55:33 2009
+++ src/common/lib/libc/string/popcount64.c Tue Jul 21 14:55:32 2009
@@ -0,0 +1,81 @@
+/* $NetBSD: popcount64.c,v 1.1 2009/07/21 14:55:32 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: popcount64.c,v 1.1 2009/07/21 14:55:32 joerg Exp $");
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#include <limits.h>
+#include <strings.h>
+#else
+#include <lib/libkern/libkern.h>
+#include <machine/limits.h>
+#endif
+
+/*
+ * If uint64_t is larger than size_t, the follow assumes that
+ * splitting into 32bit halfes is faster.
+ *
+ * The native pocount64 version is based on the same ideas as popcount64(3),
+ * see popcount64.c for comments.
+ */
+
+#if SIZE_MAX < 0xffffffffffffffffULL
+unsigned int
+popcount64(uint64_t v)
+{
+ return popcount32(v >> 32) + popcount32(v & 0xffffffffU);
+}
+#else
+unsigned int
+popcount64(uint64_t 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
+
+#if ULONG_MAX == 0xffffffffffffffffULL
+__strong_alias(popcountl, popcount64);
+#endif
+
+#if ULLONG_MAX == 0xffffffffffffffffULL
+__strong_alias(popcountll, popcount64);
+#endif
+
