Date: Sun, 07 Jun 2015 08:53:18 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Erich Dollansky <erichsfreebsdlist@alogt.com>, "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org> Subject: Re: allow ffs & co. a binary search Message-ID: <5573EA5E.40806@selasky.org> In-Reply-To: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 06/07/15 02:13, Erich Dollansky wrote:
> Hi,
>
> I stumbled these days over the functions to find the first or last bit
> set. They are currently written like this:
>
> /*
> * Find First Set bit
> */
> int
> ffs(int mask)
> {
> int bit;
>
> if (mask == 0)
> return (0);
> for (bit = 1; !(mask & 1); bit++)
> mask = (unsigned int)mask >> 1;
> return (bit);
> }
>
> With other words, the program loops until it finds what it searches for.
>
> Why not do it the binary way?
>
> int res;
>
> res = 0;
> IF (Number != 0) THEN
> res = 1;
> IF ((Number & 0xFFFFFFFF00000000) != 0) THEN
> Number = Number & 0xFFFFFFFF00000000;
> res = res + 32;
> END;
> IF ((Number & 0xFFFF0000FFFF0000) != 0) THEN
> Number = Number & 0xFFFF0000FFFF0000;
> res = res + 16;
> END;
> IF ((Number & 0xFF00FF00FF00FF00) != 0) THEN
> Number = Number & 0xFF00FF00FF00FF00;
> res = res + 8;
> END;
> IF ((Number & 0xF0F0F0F0F0F0F0F0) != 0) THEN
> Number = Number & 0xF0F0F0F0F0F0F0F0;
> res = res + 4;
> END;
> IF ((Number & 0xCCCCCCCCCCCCCCCC) != 0) THEN
> Number = Number & 0xCCCCCCCCCCCCCCCC;
> res = res + 2;
> END;
> IF ((Number & 0xAAAAAAAAAAAAAAAA) != 0) THEN
> Number = Number & 0xAAAAAAAAAAAAAAAA;
> res = res + 1;
> END;
> END;
> return res;
>
> If you like the binary way I could give you the sources for the
> complete family following your style to replace the older functions.
>
Hi Erich,
I think this is not the fastest way to do it. You first find the LSB,
then you do a sumbits, which doesn't have any conditionals IF/ELSE and
performs better with the CPU pipeline. I think the software ffs() is
only used for platforms which doesn't have a hardware version btw:
From my libmbin:
> uint8_t
> mbin_sumbits32(uint32_t val)
> {
> #if 0
> uint8_t t = 0;
>
> while (val) {
> if (val & 1)
> t++;
> val >>= 1;
> }
> return (t);
> #else
> val = ((val & (1U * 0xAAAAAAAAU)) / 2U) + (val & (1U * 0x55555555U));
> val = ((val & (3U * 0x44444444U)) / 4U) + (val & (3U * 0x11111111U));
> val = ((val & (15U * 0x10101010U)) / 16U) + (val & (15U * 0x01010101U));
> val = ((val & (255U * 0x01000100U)) / 256U) + (val & (255U * 0x00010001U));
> val = ((val & (65535U * 0x00010000U)) / 65536U) + (val & (65535U * 0x00000001U));
> return (val);
> #endif
> }
> uint32_t
> mbin_lsb32(uint32_t val)
> {
> return ((~(val - 1)) & val);
> }
int ffs(int value)
{
int retval = mbin_sumbits32(mbin_lsb32(value) - 1);
if (retval == 32)
retval = 0;
else
retval++;
return (retval);
}
--HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?5573EA5E.40806>