[RFC] Generic population count function
Jung-uk Kim
jkim at FreeBSD.org
Thu Nov 15 00:47:02 UTC 2012
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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[*]).
Any objection?
Jung-uk Kim
* PS: BTW, I am not sure whether this is correct:
- --- sys/netpfil/ipfw/ip_fw_table.c
+++ sys/netpfil/ipfw/ip_fw_table.c
@@ -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:
Is xent->masklen initialized to a non-zero value somewhere, i.e.,
shouldn't we just use '=' instead of '+=' here?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.19 (FreeBSD)
Comment: Using GnuPG with Mozilla - http://www.enigmail.net/
iEYEARECAAYFAlCkO1IACgkQmlay1b9qnVNzggCfW+Fri0Aj4TDDXcAoPc4SaATB
clQAnikNhO6JVJ+Ez71cbdQV5Qy4uHam
=r4nt
-----END PGP SIGNATURE-----
-------------- next part --------------
Index: sys/netgraph/netflow/netflow.c
===================================================================
--- sys/netgraph/netflow/netflow.c (revision 243042)
+++ 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 243042)
+++ 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,106 @@
+/*-
+ * Copyright (c) 2012 Jung-uk Kim <jkim at 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/cdefs.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:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
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
Index: sys/sys/systm.h
===================================================================
--- sys/sys/systm.h (revision 243042)
+++ 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_ */
More information about the freebsd-arch
mailing list