Re: 64-bit masks

[Sad Clouds <cryintothebluesky%googlemail.com@localhost>]

On Fri, 27 Nov 2009 16:00:43 -0000, Robert Elz <kre%munnari.oz.au@localhost> 
wrote:

> Whether this is really an appropriate algorithm depends on just what you
> need to know all the free objects for - if you just want to find the  
> first
> free object, there are easier (faster) ways, but if you really need to
> find all of them, this might be OK.

Hi, well I really need to find the first free object, not all the free  
objects at once. The faster I can do it, the better. I looked at ffs()  
function to find first set bit, but it operates on integers, which I think  
might be problematic because:

1. On different platforms integer could be 16, 32, or even 64-bits wide
2. If I need to keep track of 64 or more objects, I would need an array of  
integers. Calling ffs() function several times might slow things down. But  
if ffs() is implemented via fast assembly instruction, I guess it should  
be OK.

It also needs to be portable to at least BSD, Linux and Solaris.

My code assumes bit 1 is busy, and bit 0 is free. So I came up with the  
following function (attached) to look for the first unset (0) bit. If  
anyone knows faster algorithms, I'd be interested to know.

PS. I ran a quick benchmark on Sparc Solaris, a loop of 10_000_000  
iterations calling ffs() on 32-bit int, and a loop for my function on  
64-bit int.

/opt/SUNWspro/bin/cc -xO3 find_bit.c

This is my function:
rom@ultra10 ptime ./a.out

real        0.561
user        0.542
sys         0.009

This is Solaris ffs():
rom@ultra10 ptime ./a.out

real        0.680
user        0.626
sys         0.009


I suppose it's a good start.

/*
ffu_bit - find first unset bit

Return:
 index of first unset bit (0 to 63)
 -1 if there were no unset bits

Pre:
 bit_str is a 64-bit unsigned integer

Post:
 none

The function uses binary search algorithm to find 8-bit byte inside a 64-bit
integer, which contains an unset bit.

The function divides 64-bit integer into two 32-bit halves. It then divides
each 32-bit half into two 16-bit halves. Each of the 16-bit halves is then
divided into two 8-bit halves.

aaaaaaaaaaaaaaaaaaaaaaa -> 1 64-bit
bbbbbbbbbbb bbbbbbbbbbb -> 2 32-bit segments
ccccc ccccc ccccc ccccc -> 4 16-bit segments
dd dd dd dd dd dd dd dd -> 8 8-bit segments
-----------------------
 7  6  5  4  3  2  1  0 -> 8-bit index
*/
int ffu_bit(uint64_t bit_str)
{

        int index, i;   
        uint64_t tmp;
        const uint64_t mask64 = UINT64_C(0xffffffffffffffff);
        const uint64_t mask32 = UINT64_C(0x00000000ffffffff);
        const uint64_t mask16 = UINT64_C(0x000000000000ffff);
        const uint64_t mask8  = UINT64_C(0x00000000000000ff);

        /* If all bits are 1, return -1 */
        if(bit_str == mask64)
                return -1;

        /* If bits 0-31 are not all 1s */
        if((bit_str & mask32) != mask32)
        {
                /* If bits 0-15 are not all 1s */
                if((bit_str & mask16) != mask16)
                {
                        /* If bits 0-7 are not all 1s */
                        if((bit_str & mask8) != mask8)
                                index = 0;
                        else /* bits 8-15 */
                                index = 1;
                }
                else /* Must be bits 16-31 */
                {
                        /* If bits 16-23 are not all 1s */
                        if(((bit_str >> 16) & mask8) != mask8)
                                index = 2;
                        else /* bits 24-32 */
                                index = 3;
                }
        }
        /* Must be bits 32-63 */
        else
        {
                /* If bits 32-47 are not all 1s */
                if(((bit_str >> 32) & mask16) != mask16)
                {
                        /* If bits 32-39 are not all 1s */
                        if(((bit_str >> 32) & mask8) != mask8)
                                index = 4;
                        else /* bits 40-47 */
                                index = 5;
                }
                else /* Must be bits 48-63 */
                {
                        /* If bits 48-55 are not all 1s */
                        if(((bit_str >> 48) & mask8) != mask8)
                                index = 6;
                        else /* bits 56-63 */
                                index = 7;
                }
        }

        index *= 8; /* scale index by 8-bits in a byte */

        /*
        Shift the 8-bit byte containing first unset bit to the far right so we 
can
        find out the exact bit index within the byte.
        */
        tmp = bit_str >> index;

        for(i = 0; i < 8; i++)
        {
                if(((tmp >> i) & 0x1) == 0)
                        break; /* found first bit set to 0 */
        }
        index += i;
        return index;
}