Date: Thu, 15 Nov 2012 20:35:10 -0500 From: Jung-uk Kim <jkim@FreeBSD.org> To: freebsd-arch@freebsd.org Subject: Re: [RFC] Generic population count function Message-ID: <50A5984E.8030305@FreeBSD.org> In-Reply-To: <50A43B52.8030102@FreeBSD.org> References: <50A43B52.8030102@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
This is a multi-part message in MIME format. --------------090401070006080406090307 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 2012-11-14 19:46:10 -0500, Jung-uk Kim wrote: > I implemented generic population count function. Please see the > attachment. It is also available from here: > > http://people.freebsd.org/~jkim/bitcount.diff > > The idea is to make use of CPU-supported population count > instructions if available and the compiler supports them (i.e., > clang), especially for larger than 32-bit data. The patch also has > use cases for the new function (i.e., counting number of bits in > IPv6 address[*]). Now the patch is updated with a style fix (i.e., removed <sys/cdefs.h> from bitcount.h): http://people.freebsd.org/~jkim/bitcount2.diff Also, I added another use case, i.e., CPU_COUNT() to count the number of bits in cpuset_t. If nobody objects, I am going to commit it around next Monday. Thanks, Jung-uk Kim -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.19 (FreeBSD) Comment: Using GnuPG with Mozilla - http://www.enigmail.net/ iEYEARECAAYFAlClmE4ACgkQmlay1b9qnVPoagCgp+QVEkAP4PPPlg1Zh4v3K1o0 q2QAoKJG15yB7jz2J091lOAq1gPceeHY =q56J -----END PGP SIGNATURE----- --------------090401070006080406090307 Content-Type: text/plain; charset=UTF-8; name="bitcount2.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="bitcount2.diff" Index: sys/netgraph/netflow/netflow.c =================================================================== --- sys/netgraph/netflow/netflow.c (revision 243111) +++ sys/netgraph/netflow/netflow.c (working copy) @@ -409,12 +409,9 @@ hash_insert(priv_p priv, struct flow_hash_entry *h } #ifdef INET6 -/* XXX: make normal function, instead of.. */ -#define ipv6_masklen(x) bitcount32((x).__u6_addr.__u6_addr32[0]) + \ - bitcount32((x).__u6_addr.__u6_addr32[1]) + \ - bitcount32((x).__u6_addr.__u6_addr32[2]) + \ - bitcount32((x).__u6_addr.__u6_addr32[3]) -#define RT_MASK6(x) (ipv6_masklen(((struct sockaddr_in6 *)rt_mask(x))->sin6_addr)) +#define RT_MASK6(x) \ + bitcount(&((struct sockaddr_in6 *)rt_mask(x))->sin6_addr, \ + sizeof(struct in6_addr)) static int hash6_insert(priv_p priv, struct flow_hash_entry *hsh6, struct flow6_rec *r, int plen, uint8_t flags, uint8_t tcp_flags) @@ -505,7 +502,6 @@ hash6_insert(priv_p priv, struct flow_hash_entry * return (0); } -#undef ipv6_masklen #undef RT_MASK6 #endif Index: sys/netpfil/ipfw/ip_fw_table.c =================================================================== --- sys/netpfil/ipfw/ip_fw_table.c (revision 243111) +++ sys/netpfil/ipfw/ip_fw_table.c (working copy) @@ -706,10 +706,7 @@ dump_table_xentry_extended(struct radix_node *rn, struct table_xentry * const n = (struct table_xentry *)rn; ipfw_xtable * const tbl = arg; ipfw_table_xentry *xent; -#ifdef INET6 - int i; - uint32_t *v; -#endif + /* Out of memory, returning */ if (tbl->cnt == tbl->size) return (1); @@ -720,11 +717,10 @@ dump_table_xentry_extended(struct radix_node *rn, switch (tbl->type) { #ifdef INET6 case IPFW_TABLE_CIDR: - /* Count IPv6 mask */ - v = (uint32_t *)&n->m.mask6.sin6_addr; - for (i = 0; i < sizeof(struct in6_addr) / 4; i++, v++) - xent->masklen += bitcount32(*v); - memcpy(&xent->k, &n->a.addr6.sin6_addr, sizeof(struct in6_addr)); + xent->masklen += bitcount(&n->m.mask6.sin6_addr, + sizeof(struct in6_addr)); + memcpy(&xent->k, &n->a.addr6.sin6_addr, + sizeof(struct in6_addr)); break; #endif case IPFW_TABLE_INTERFACE: Index: sys/sys/bitcount.h =================================================================== --- sys/sys/bitcount.h (revision 0) +++ sys/sys/bitcount.h (working copy) @@ -0,0 +1,105 @@ +/*- + * Copyright (c) 2012 Jung-uk Kim <jkim@FreeBSD.org> + * All rights reserved. + * + * 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 AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +#ifndef _SYS_BITCOUNT_H_ +#define _SYS_BITCOUNT_H_ + +#include <sys/types.h> + +#if __GNUC_PREREQ__(3, 4) +#define __BITCOUNT(x) __builtin_popcountl(x) +#define __BITCOUNT32(x) __builtin_popcount(x) +#define __BITCOUNT_T u_long +#else +#define __BITCOUNT(x) __bitcount32(x) +#define __BITCOUNT32(x) __bitcount32(x) +#define __BITCOUNT_T uint32_t +#endif + +/* + * Population count algorithm using SWAR approach + * - "SIMD Within A Register". + */ +static __inline int +__bitcount32(uint32_t x) +{ + + x += ~((x >> 1) & 0x55555555) + 1; + x = (x & 0x33333333) + ((x >> 2) & 0x33333333); + x = (x + (x >> 4)) & 0x0f0f0f0f; + x += x >> 8; + x += x >> 16; + return (x & 0x3f); +} + +static __inline int +bitcount(void *p, int len) +{ + __BITCOUNT_T x; + u_char *str; + int count; + + /* + * Number of bits must be non-zero and less or equal to INT_MAX. + */ + if (len <= 0 || len >= 0x10000000) + return (-1); + + for (count = 0, str = p; len > 0; len -= sizeof(x)) { + if (len / sizeof(x) > 0) { + x = *(__BITCOUNT_T *)str; + str += sizeof(x); + } else { + /* Byte order is not important here. */ + for (x = 0; len > 0; str++, len--) + x |= *str << (len * 8); + } + count += __BITCOUNT(x); + } + return (count); +} + +static __inline int +bitcount16(uint16_t x) +{ + + return (__BITCOUNT32(x)); +} + +static __inline int +bitcount32(uint32_t x) +{ + + return (__BITCOUNT32(x)); +} + +#undef __BITCOUNT +#undef __BITCOUNT32 +#undef __BITCOUNT_T + +#endif /* !_SYS_BITCOUNT_H_ */ Property changes on: sys/sys/bitcount.h ___________________________________________________________________ Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Index: sys/sys/cpuset.h =================================================================== --- sys/sys/cpuset.h (revision 243111) +++ sys/sys/cpuset.h (working copy) @@ -33,6 +33,7 @@ #define _SYS_CPUSET_H_ #include <sys/_cpuset.h> +#include <sys/bitcount.h> #define CPUSETBUFSIZ ((2 + sizeof(long) * 2) * _NCPUWORDS) @@ -44,6 +45,7 @@ ((long)1 << ((_NCPUWORDS == 1) ? (__size_t)(n) : ((n) % _NCPUBITS))) #define __cpuset_word(n) ((_NCPUWORDS == 1) ? 0 : ((n) / _NCPUBITS)) +#define CPU_COUNT(p) bitcount(p, sizeof(long) * _NCPUWORDS) #define CPU_CLR(n, p) ((p)->__bits[__cpuset_word(n)] &= ~__cpuset_mask(n)) #define CPU_COPY(f, t) (void)(*(t) = *(f)) #define CPU_ISSET(n, p) (((p)->__bits[__cpuset_word(n)] & __cpuset_mask(n)) != 0) Index: sys/sys/systm.h =================================================================== --- sys/sys/systm.h (revision 243111) +++ sys/sys/systm.h (working copy) @@ -40,6 +40,7 @@ #include <machine/atomic.h> #include <machine/cpufunc.h> +#include <sys/bitcount.h> #include <sys/callout.h> #include <sys/cdefs.h> #include <sys/queue.h> @@ -387,31 +388,4 @@ int alloc_unr_specific(struct unrhdr *uh, u_int it int alloc_unrl(struct unrhdr *uh); void free_unr(struct unrhdr *uh, u_int item); -/* - * Population count algorithm using SWAR approach - * - "SIMD Within A Register". - */ -static __inline uint32_t -bitcount32(uint32_t x) -{ - - x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); - x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); - x = (x + (x >> 4)) & 0x0f0f0f0f; - x = (x + (x >> 8)); - x = (x + (x >> 16)) & 0x000000ff; - return (x); -} - -static __inline uint16_t -bitcount16(uint32_t x) -{ - - x = (x & 0x5555) + ((x & 0xaaaa) >> 1); - x = (x & 0x3333) + ((x & 0xcccc) >> 2); - x = (x + (x >> 4)) & 0x0f0f; - x = (x + (x >> 8)) & 0x00ff; - return (x); -} - #endif /* !_SYS_SYSTM_H_ */ --------------090401070006080406090307--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?50A5984E.8030305>