alogrothim for getting if there are N bytes 0 in dword [FIXE

[earlz]

I am rewriting my page allocator but am having problems; I can not figure out a practical way to get if there are N bits in a row that are cleared so maybe someone here could help me

[paulbarker]

You are better arranging the bitmap so you search for set bits, this allows you to use the bsf and bsr instructions to search for individual set bits very quickly. Searching for longer runs is horribly inefficient, you may want to have a look at buddy bitmaps if you haven't already done. You may find something useful in these 2 files:

bitmap.c (generic)
bitops.h (for x86)

[Candy]

Just a small FYI, if you search for "algorithm" you'll get more hits.

You can optimize it to do some bits faster:

If you store the bit series in integers, check whether the entire int contains any cleared bit before deciding to search in it. This optimizes when you regularly search through full bitmaps.

If you just want to know the amount of bits cleared, invert it and use a bit counting algorithm (of which there are multiple known).

If you actually need a consecutive stretch of a given number, you'll have to use some slower method since that's not optimized. You can try skipping ahead until you find an empty spot, but you won't get much faster than that.

[B.E]

you could just make a "mask" for the value, AND the dword and test if it is zero. if it is then all are free.

An otherway you could do is NOT it and test if it is zero. if it isn't then you have some bits free.

An otherway is to find a more efficient memory management algorithm. A bitmap is simple but not practical for an Operating System.

[paulbarker]

A bitmap is very practical if you only allocate one unit of memory (ie. a page) at a time. Add to that a small fixed size cache (which works as a stack of free pages) and you get a fast, memory-efficient allocator.

[earlz]

hmmm sorry for wasting everyones time I got it done, even if its not all that optimized it is reliable enough for me(or at least to the extent i tested it)

this is my memory manager code(for only alloc) if anyone wants to know

well its attached, its too big

[FlashBurn]

If you have some time you could have a look at my bitmap allocator. It is optimized, but I don?t know if this algo also uses some things I?m using in my asm version which make it better. You have to know that this file is old and is from a try to convert my asm code to c.