Skip site navigation (1)Skip section navigation (2) 
Date:      Sun, 7 Jun 2015 08:13:15 +0800
From:      Erich Dollansky <erichsfreebsdlist@alogt.com>
To:        "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org>
Subject:   allow ffs & co. a binary search
Message-ID:  <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com>
next in thread | raw e-mail | index | archive | help 
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.

Erich

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20150607081315.7c0f09fb>