Page 1 of 2
Searching for a string of set (or unset) bits in a bitmap
Posted: Sun Jun 22, 2008 10:30 pm
by 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..
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Mon Jun 23, 2008 1:20 am
by Combuster
it looks just like how I'd solve it...
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Mon Jun 23, 2008 10:22 am
by earlz
guess I'll continue with it then... lol...
I hate writing it though... it's so complicated and confusing to me...
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Mon Jun 23, 2008 10:56 am
by 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.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Mon Jun 23, 2008 1:09 pm
by 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...
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Wed Jul 30, 2008 7:56 pm
by 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
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 3:07 am
by Combuster
You could also hard code a switch statement that handles every 256 cases.
*cough*lookuptable*cough*
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 12:15 pm
by Brendan
Hi,
hckr83 wrote: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
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 12:23 pm
by Combuster
Or negate the byte you're looking at before BSF/BSRing
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 3:34 pm
by AJ
Combuster wrote: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
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 3:44 pm
by JamesM
AJ wrote:Combuster wrote: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.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 6:17 pm
by 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.
Brendan wrote:
I'd be tempted to start with "REPNE CMPSD"
Except that CMPSx is microcoded, of course.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Thu Jul 31, 2008 9:27 pm
by Brendan
Hi,
bewing wrote:Brendan wrote:
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
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 12:54 am
by 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
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?
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 1:47 am
by AJ
Thank you, "Code-Myth-Buster"!
Note for posterity: I didn't say "don't use a lookup table"
Cheers,
Adam