bitmaps

[alberich]

Hi!

I'm trying to make some simple memory manager to my OS, and then a found a litlle trouble about how to implement bitmap blocks.

I'm posting this here, becouse it's more a programing question than an OS question..

How can i work with those blocks of bitmaps with c? I know how to set bit 1, but not the bit 4, or a range of 3 bits starting on bit 1 eficiently, nor how to search across the bitmap.

can anyone pointme to any where?

thanks!

[stephenj]

I'm not sure if you meant bit 1 as in the first bit or the second. I'll assume you meant bit 0 (the first bit).

Code: Select all

int i = 0;

i | (1 << 0);  //Set Bit 0
i | (1 << 1);  //Set Bit 1
...
i | (1 << 4);  //Set Bit 4

Range of three bits? Consider n bits:

Code: Select all

(1 << n) - 1

Then shift that into place using the technique above.

The later works on a simple principle, consider n = 3. 1 << 3 == 8, 8 - 1 == 7, 7 in binary is 111.

As for searching, say you want to determine what bit 5 is. Like above, (1 << 5) will turn on only bit 5. ((1 << 5) & i) will test bit 5 of int i. I suppose you could also shift i the other way then and it with a 1. Whichever way makes more sense to you.

[Hangin10]

Basically, just do what stephenj said in loop through the bitmap. (which is just an array, or a pointer to an array allocated
in some fashion).

Originally this code would have appeared in all my functions that search a bitmap, but that would have been silly. REFACTOR! While I considered writing the function in assembly using the bit scan instructions, the following
is probably easier to read:

u32 is a typedef to a 32bit unsigned long (I've seen things like uint32_t, but I'd rather know how
my compiler uses short, int, long, and long long, and typedef accordingly). Size is in 32bit values.
It returns the index into the map and bit of the found bit in the two pointers, if a bit was found it
returns 1, else zero and index and bit are not modified.

Code: Select all

u32 search_bitmap(u32* map, u32 size, u32* index, u32* bit)
{
	for(u32 i = 0; i != size; ++i)
	{
		if( map[i] == 0 )
			continue;
		for(u32 b = 0; b != 32; ++b)
		{
			if( map[i] & (1<<b) )
			{
				map[i] ^= (1<<b);
				*index = i;
				*bit = b;
				return 1;
			}
		}
	}

	return 0;
}

EDIT: Well, this made me want to try to write an asm version. So I came up with the following:

Code: Select all

search_bitmap:
	push ebp
	mov ebp, esp
	cld
	xor eax, eax
	mov ecx, [ebp+16]  ; load ecx with the size
	mov edi, [ebp+20]  ; map pointer
	repz scasd
	jz .end_search
	add ecx, byte 1    ; even though REP ends, ecx is one too low
	mov edx, [ebp+12]  ; pointer to index
	mov eax, [ebp+16]
	sub eax, ecx        ; ECX is the size. so index is size - target.
	mov [edx], eax
	mov edx, [ebp+8]   ; pointer to bit
	bsr eax, [edi-4]   ; the last SCASD puts EDI past the target
	mov [edx], eax
	mov eax, 1
.end_search:
	leave
	ret

[alberich]

Wow! thank you men!

great info, thanks!!

[JohnnyTheDon]

If you're going to use assembly, take a look at the 'bt, 'btr', and 'bts' instructions. They allow you to manipulate bit strings directly. All they require is the address of the bit string and the index you want to test/change.