From owner-freebsd-hackers@FreeBSD.ORG Fri Jun 12 13:32:06 2015 Return-Path: Delivered-To: freebsd-hackers@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id A4054621; Fri, 12 Jun 2015 13:32:06 +0000 (UTC) (envelope-from ryao@gentoo.org) Received: from smtp.gentoo.org (dev.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 853121AEE; Fri, 12 Jun 2015 13:32:06 +0000 (UTC) (envelope-from ryao@gentoo.org) Received: from [192.168.1.2] (pool-72-89-250-199.nycmny.fios.verizon.net [72.89.250.199]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: ryao) by smtp.gentoo.org (Postfix) with ESMTPSA id E1BD3340A35; Fri, 12 Jun 2015 13:32:02 +0000 (UTC) Message-ID: <557ADF46.6030004@gentoo.org> Date: Fri, 12 Jun 2015 09:31:50 -0400 From: Richard Yao User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 MIME-Version: 1.0 To: Hans Petter Selasky , Ian Lepore CC: "freebsd-hackers@freebsd.org" , Erich Dollansky Subject: Re: allow ffs & co. a binary search References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5579A016.4040800@gentoo.org> <1434034373.1415.3.camel@freebsd.org> <5579A235.80609@gentoo.org> <557A3CF3.3050603@selasky.org> <557AD8B0.6000600@gentoo.org> In-Reply-To: <557AD8B0.6000600@gentoo.org> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="hhTGpjioERfbEjcS17L2fhVuxFmwKm8nX" X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 12 Jun 2015 13:32:06 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --hhTGpjioERfbEjcS17L2fhVuxFmwKm8nX Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable On 06/12/2015 09:03 AM, Richard Yao wrote: > On 06/11/2015 09:59 PM, Hans Petter Selasky wrote: >> On 06/11/15 16:59, Richard Yao wrote: >>> On 06/11/2015 10:52 AM, Ian Lepore wrote: >>>> On Thu, 2015-06-11 at 10:49 -0400, Richard Yao wrote: >>>>> On 06/06/2015 08:13 PM, Erich Dollansky wrote: >>>> [...] >>>>> >>>>> The fastest portable way of calculating highest bit set is to use a= >>>>> debrujin sequence: >>>>> >>>>> https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBr= uijn >>>>> >>>>> The binary approach is inferior, especially on Pentium 4 processors= =2E >>>> >>>> And of course it's crucial that we optimize for Pentium 4 processors= in >>>> 2015. >>> >>> The debrujin approach is fast regardless of the architecture. Anyway,= >>> this is a solved problem. There is no need to reinvent the wheel when= >>> the portable solutions are listed on that page at Stanford. >>> >> >> Hi Richard, >> >> ffs() can be implemented like this simply: >> >> int ffs_A(uint32_t v) >> { >> static const int MultiplyDeBruijnBitPosition[32] =3D >> { >> 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, >> 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 >> }; >> v =3D ~(v - 1) & v; >> return (MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]= ); >> } >=20 > There is a way to do that on the stanford page too: >=20 > https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLo= okup My apologies. I inadvertently linked to the wrong variant of that in my initial email. It has been a while since I visited that page and I was juggling a few things when I wrote that email, so it was easy to confuse the two. Anyway, it would be possible to do something like: #if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_ffs)) # define ffs(n) __builtin_ffs(n) #else /* * From Sean Eron Anderson's Bit Twiddling Hacks * https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLook= up */ static inline int ffs(uint32_t v) { static const int MultiplyDeBruijnBitPosition[32] =3D { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v =3D ~(v - 1) & v; return (MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]); } #endif If there were an autotools-like check for `__has_builtin()`, then an explicit list of compilers known to support `__builtin_ffs()` would not be necessary, although a list of compilers that lack support for `__has_builtin()` (such as GCC) would still be necessary. Those building with compilers that do not support `__builtin_ffs()` could fallback to the DeBrujin approach. --hhTGpjioERfbEjcS17L2fhVuxFmwKm8nX Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBAgAGBQJVet9MAAoJECDuEZm+6ExkQYAQAJ/GHDJsSYXTjykmGCHP7K1A EcgXjS3FO4KLc97ArzS5JQ9zB+btAIwshbaUFqxINivkvRHPSHhLktiv/QUODL/l fVp6Pr43/rU6W7KTx1FO3WcJyr5/TYS0RSqH3VltZvneuXonuwyQTJNhggVhS8JW GxCV7Jtw2UrW/i1MwN1lCRbWdPmCQse18wWAhCwdUAuSI/8tluOOZUjiQ+iYMRuT 4MFutG0SrSHP6DToPWFcXFcf1v+/vrC0ROykugtbXqHFty/StthBFg1rsT668B15 3P+u7G+jYj+xaRekFFp8exi8II8il9179S+hsl5M3noVE58sL++HLPelDVLyTMzB BgyMhWEGV2b7S1Or0o5Vxa2eVLKIFI5ud4zY2OjGIR3kiYeuq+kn8R6AGlw2y5pR ushjLXunYm11uY8rCIZEeuP20RIyCs0nFksonOPqQi/B8b3qQ0YQuiCkf0vWlfbP uRt6svVn9jOBailAk4sxKWEoFD4k10r0qO2G2pHOHV8HeCtwbF4n44HR/NjbTq6E HxxAJpOeLuu8tSuKcPAvxCJ5mAfPW+RtegvY4ZvYyNNS9y0pm6APpN7pW/z57PC6 E1vxkMOX3U82mjTW26cTU2hFkU0rdSGu4arcLtQMZhFHK8Da6KkMZTSSCcCr0/iJ 6wVQg4wQp0OcmLTiX2Xk =Zv3N -----END PGP SIGNATURE----- --hhTGpjioERfbEjcS17L2fhVuxFmwKm8nX--