Date: Fri, 12 Jun 2015 09:31:50 -0400 From: Richard Yao <ryao@gentoo.org> To: Hans Petter Selasky <hps@selasky.org>, Ian Lepore <ian@freebsd.org> Cc: "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org>, Erich Dollansky <erichsfreebsdlist@alogt.com> Subject: Re: allow ffs & co. a binary search Message-ID: <557ADF46.6030004@gentoo.org> In-Reply-To: <557AD8B0.6000600@gentoo.org> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?557ADF46.6030004>