From owner-freebsd-current@FreeBSD.ORG Sat May 7 09:58:14 2011 Return-Path: Delivered-To: current@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CEA79106564A for ; Sat, 7 May 2011 09:58:14 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from citadel.icyb.net.ua (citadel.icyb.net.ua [212.40.38.140]) by mx1.freebsd.org (Postfix) with ESMTP id 21C078FC08 for ; Sat, 7 May 2011 09:58:13 +0000 (UTC) Received: from porto.topspin.kiev.ua (porto-e.starpoint.kiev.ua [212.40.38.100]) by citadel.icyb.net.ua (8.8.8p3/ICyb-2.3exp) with ESMTP id MAA06091 for ; Sat, 07 May 2011 12:58:12 +0300 (EEST) (envelope-from avg@FreeBSD.org) Received: from localhost.topspin.kiev.ua ([127.0.0.1]) by porto.topspin.kiev.ua with esmtp (Exim 4.34 (FreeBSD)) id 1QIeH6-0004Bq-Bg for current@FreeBSD.org; Sat, 07 May 2011 12:58:12 +0300 Message-ID: <4DC517B3.8050502@FreeBSD.org> Date: Sat, 07 May 2011 12:58:11 +0300 From: Andriy Gapon User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.9.2.17) Gecko/20110503 Lightning/1.0b2 Thunderbird/3.1.10 MIME-Version: 1.0 To: current@FreeBSD.org X-Enigmail-Version: 1.1.2 Content-Type: text/plain; charset=X-VIET-VPS Content-Transfer-Encoding: 7bit Cc: Subject: bitcount32: replace lengthy comment with SWAR reference X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 07 May 2011 09:58:14 -0000 I think that the SWAR reference should be more concise and should lead an interested reader to more information on the topic (and more up-to-date as well). bitcount32: replace lengthy comment with SWAR reference diff --git a/sys/sys/systm.h b/sys/sys/systm.h index 48bb33c..5218988 100644 --- a/sys/sys/systm.h +++ b/sys/sys/systm.h @@ -383,44 +383,8 @@ int alloc_unrl(struct unrhdr *uh); void free_unr(struct unrhdr *uh, u_int item); /* - * This is about as magic as it gets. fortune(1) has got similar code - * for reversing bits in a word. Who thinks up this stuff?? - * - * Yes, it does appear to be consistently faster than: - * while (i = ffs(m)) { - * m >>= i; - * bits++; - * } - * and - * while (lsb = (m & -m)) { // This is magic too - * m &= ~lsb; // or: m ^= lsb - * bits++; - * } - * Both of these latter forms do some very strange things on gcc-3.1 with - * -mcpu=pentiumpro and/or -march=pentiumpro and/or -O or -O2. - * There is probably an SSE or MMX popcnt instruction. - * - * I wonder if this should be in libkern? - * - * XXX Stop the presses! Another one: - * static __inline u_int32_t - * popcnt1(u_int32_t v) - * { - * v -= ((v >> 1) & 0x55555555); - * v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - * v = (v + (v >> 4)) & 0x0F0F0F0F; - * return (v * 0x01010101) >> 24; - * } - * The downside is that it has a multiply. With a pentium3 with - * -mcpu=pentiumpro and -march=pentiumpro then gcc-3.1 will use - * an imull, and in that case it is faster. In most other cases - * it appears slightly slower. - * - * Another variant (also from fortune): - * #define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) - * #define BX_(x) ((x) - (((x)>>1)&0x77777777) \ - * - (((x)>>2)&0x33333333) \ - * - (((x)>>3)&0x11111111)) + * Population count algorithm using SWAR approach + * - "SIMD Within A Register". */ static __inline uint32_t bitcount32(uint32_t x) -- Andriy Gapon