Searching for a string of set (or unset) bits in a bitmap

[earlz]

Hi, I am making support code for my OS's page manager and I am attempting to make a function to find a free area in a bitmap of a certain amount of space...

I have started and got the beginnings of hte function, but I can't help but think there is some better way I'm not realizing...
this is my code so far..

Code: Select all

//returns bit number beginning the free bit string
//map is the bitmap pointer
//count is how many bits need to be set
//size is how big the map is
uint32_t FindSetBits(uint32_t *map, uint32_t count, size_t size){
	uint32_t i,j;
	if((count*32)>(size*32)){ //if there never was enough space
		return NO_BIT;
	}
	for(i=0;i<size;i++){
		if(map[i]!=0xFFFFFFFF){
			if(count==1){
				for(j=0;j<=31;j++){
					if((map[i]&(1<<j))!=0){
						return (i*32)+j;
					}
				}
				return NO_BIT;
			}
			if(count<=32){
				if(map[i]==0){ //if only it was always this easy...
					return i*32;
				}
				
				
				
			}
				
			
			
			
			
		}
		if((count*32)>((size-i)*32)){return 0xFFFFFFFF;} //if not enough space
	}
	
	
	
	return 0;
}

I not neccessarily asking for just code, just some better and easier to implement way to do this..

[Combuster]

it looks just like how I'd solve it...

[earlz]

guess I'll continue with it then... lol...
I hate writing it though... it's so complicated and confusing to me...

[bewing]

Well, it's not how I'd solve it. Is this for physical memory only? Or for virtual memory only? Or are you trying to mush both together?

If it's for vmem, then why the heck do you need contiguous sets of pages?
If it's for physical mem, then why are you subdividing things into pages in the first place?
I'd say that mushing them together is a bad idea.

When you are dealing with physical memory regions, I think it's a better answer just to leave them stored as regions (start + contiguous length), and allocate them that way, too.

[earlz]

Well, I've decided to take a different approach.... I'm using a list based page manager now... it is for physical memory... as no virtual memory is built into my OS now...

[AndrewAPrice]

I think the easiest way would be:

Code: Select all

unsigned int pagesFound = 0;
unsigned int firstPage = 0;

while(pagesFound < pagesNeeded)
{
    // get nextPage

    if(currentPageIsFree)
    {
        if(pagesFound == 0)
              firstPage = currentPage;
        pagesFound++;
    }
    else
        pagesFound = 0;
}

Related to bitmaps, but not this, I thought of a cool optimization using binary searches. e.g.

If a 64bit chunk of the bitmap equals 0xFFFFFFFFFFFFFFFF you know it's full, else split it in to 2 32bit chunks and if they equal 0xFFFFFFFF you know they're full, else split it in to 2 16bit chunks and if they equal 0xFFFF you know they're full, else split it in to 2 8 bit chunks and if they equal 0xFF you know it's full, else...

Code: Select all

if(!(data & 1))
{} // bit 0 is free
else if(!(data & 2))
{} // bit 1 is free
else if(!(data & 4))
{} // bit 2 is free
else if(!(data & 8))
{} // bit 3 is free
else if(!(data & 16))
{} // bit 4 is free
else if(!(data & 32))
{} // bit 5 is free
else if(!(data & 64))
{} // bit 6 is free
else if(!(data & 128))
{} // bit 7 is free

Although the last bit is pretty inefficient. You could also hard code a switch statement that handles every 256 cases. I wouldn't do this by hand - write to write code for you (or upgrade your preprocessor).

And instead of subdividing the data this should be more efficient:

Code: Select all

if(bitmap && 0xFF00000000000000)
{
if(bitmap && 0x00FF000000000000)
{
if(bitmap && 0x0000FF0000000000)
{
if(bitmap && 0x000000FF00000000)
{
if(bitmap && 0x00000000FF000000)
{
if(bitmap && 0x0000000000FF0000)
{
if(bitmap && 0x000000000000FF00)
{
if(bitmap && 0x00000000000000FF)
{
}
else
{} // byte 1 is free
}
else
{} // byte 2 is free
}
else
{} // byte 3 is free
}
else
{} // byte 4 is free
}
else
{} // byte 5 is free
}
else
{} // byte 6 is free
}
else {} // byte 7 is free
}
else {} // byte 8 is free

[Combuster]

You could also hard code a switch statement that handles every 256 cases.

*cough*lookuptable*cough*

[Brendan]

Hi,

Hi, I am making support code for my OS's page manager and I am attempting to make a function to find a free area in a bitmap of a certain amount of space...

I'd be tempted to start with "REPNE CMPSD" (or "REPNE CMPSQ" for 64-bit code) to find the first non-zero dword (or qword), and then use "BSF" to find the least significant set bit in this non-zero dword (or qword).

If you're searching for the first clear bit then it'll be slower - I'd try "REPNE CMPSD" to find the first dword that isn't 0xFFFFFFFF (or REPNE CMPSQ again for 64-bit), and then use "REPNE CMPSB" followed by a lookup table.


Cheers,

Brendan

[Combuster]

Or negate the byte you're looking at before BSF/BSRing

[AJ]

You could also hard code a switch statement that handles every 256 cases.

*cough*lookuptable*cough*

As a point of interest, I asked a question about something similar (a massive switch for handling system calls) before and was informed that any half-decent compiler should generate a lookup table from a large switch statement anyway.

Cheers,
Adam

[JamesM]

You could also hard code a switch statement that handles every 256 cases.

*cough*lookuptable*cough*

As a point of interest, I asked a question about something similar (a massive switch for handling system calls) before and was informed that any half-decent compiler should generate a lookup table from a large switch statement anyway.

Cheers,
Adam

A switch statement IS a lookup table, essentially. The entire point of a switch statement and why it is so efficient (and why it doesn't support operator== in C++) is that one comparison gets made, that comparison's result gets arithmetically changed in some way to form an index or an offset from the current PC, jump, execute code.

[bewing]

It's not all that efficient, actually, unless your comparisons are ALREADY in the form of a 0 to N enumeration. Then it can be coded directly as a lookup table for a jump (absolute on an intel machine).

If your comparison values are "random" in any sense, with large values, then you can do just as well with a nested "if" -- because the switch has to test every single comparison value anyway (assuming the list is sorted properly, at least).

So, I think Combuster is right. When you are faced with 256 cases, code your own lookup table.

I'd be tempted to start with "REPNE CMPSD"

Except that CMPSx is microcoded, of course.

[Brendan]

Hi,

I'd be tempted to start with "REPNE CMPSD"

Except that CMPSx is microcoded, of course.

Mostly it depends on whether you're searching for a needle in a haystack, or if you're searching for one of many needles in a handful of hay...

One micro-coded instruction isn't so bad when performance is limited by RAM bandwidth, and AFAIK "REPNE CMPSD" is optimized to work on cache lines instead of smaller pieces (e.g. dwords) similar to other string instructions, so it's good for "needle in a haystack" situations.

You are right though - if it's likely that "REPNE CMPSD" will stop after checking less than about 20 dwords then the setup costs are too high; and for something like this it *should* be likely that "REPNE CMPSD" will stop on the first byte, because you should start searching from the lowest potentially set/clear bit instead of starting the search from the beginning of the bitmap.


Cheers,

Brendan

[Solar]

Good morning, here's your friendly "Code-Myth-Buster".

The claim is that compilers turn lengthy switch statements into lookup tables automatically.

Test 1: A switch-statement with 0-n case numbering.

Code: Select all

int main( int argc, char * argv[] )
{
    switch ( argc )
    {
        case 0:
            return 254;
        case 1:
            return 125;
        case 2:
            return 42;
        case 3:
            return 23;
        case 4:
            return 7;
        case 5:
            return 1;
        default:
            return 0;
    }
}

Compiled with gcc -O2, and disassembled with objdump:

Code: Select all

0000000000000000 <main>:
   0:   31 c0                   xor    %eax,%eax
   2:   83 ff 05                cmp    $0x5,%edi
   5:   77 0e                   ja     15 <main+0x15>
   7:   89 f8                   mov    %edi,%eax
   9:   ff 24 c5 00 00 00 00    jmpq   *0x0(,%rax,8)
  10:   b8 07 00 00 00          mov    $0x7,%eax
  15:   f3 c3                   repz retq
  17:   b8 fe 00 00 00          mov    $0xfe,%eax
  1c:   c3                      retq
  1d:   b8 01 00 00 00          mov    $0x1,%eax
  22:   c3                      retq
  23:   b8 17 00 00 00          mov    $0x17,%eax
  28:   c3                      retq
  29:   b8 2a 00 00 00          mov    $0x2a,%eax
  2e:   66 90                   xchg   %ax,%ax
  30:   c3                      retq
  31:   b8 7d 00 00 00          mov    $0x7d,%eax
  36:   c3                      retq

Test 2: A switch-statement with random numbering.

Code: Select all

int main( int argc, char * argv[] )
{
    switch ( argc )
    {
        case 5:
            return 254;
        case 18:
            return 125;
        case 22:
            return 42;
        case 31:
            return 23;
        case 34:
            return 7;
        case 51:
            return 1;
        default:
            return 0;
    }
}

Compiled with gcc -O2, and disassembled with objdump:

Code: Select all

0000000000000000 <main>:
   0:   8d 47 fb                lea    -0x5(%rdi),%eax
   3:   83 f8 2e                cmp    $0x2e,%eax
   6:   77 09                   ja     11 <main+0x11>
   8:   89 c0                   mov    %eax,%eax
   a:   ff 24 c5 00 00 00 00    jmpq   *0x0(,%rax,8)
  11:   31 c0                   xor    %eax,%eax
  13:   c3                      retq
  14:   b8 fe 00 00 00          mov    $0xfe,%eax
  19:   c3                      retq
  1a:   b8 01 00 00 00          mov    $0x1,%eax
  1f:   90                      nop
  20:   c3                      retq
  21:   b8 07 00 00 00          mov    $0x7,%eax
  26:   c3                      retq
  27:   b8 17 00 00 00          mov    $0x17,%eax
  2c:   0f 1f 40 00             nopl   0x0(%rax)
  30:   c3                      retq
  31:   b8 2a 00 00 00          mov    $0x2a,%eax
  36:   c3                      retq
  37:   b8 7d 00 00 00          mov    $0x7d,%eax
  3c:   0f 1f 40 00             nopl   0x0(%rax)
  40:   c3                      retq

And now the price question: Given 256 possible values, which code is better readable and better maintainable: A 515-line switch block, or a 10-line lookup table logic?

[AJ]

Thank you, "Code-Myth-Buster"!

Note for posterity: I didn't say "don't use a lookup table"

Cheers,
Adam