allow ffs & co. a binary search

[Hans Petter Selasky]

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