2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * FILE: lib/rtl/bitmap.c
5 * PURPOSE: Bitmap functions
6 * PROGRAMMER: Timo Kreuzer (timo.kreuzer@reactos.org)
9 /* INCLUDES *****************************************************************/
17 /* DATA *********************************************************************/
19 /* Number of set bits per byte value */
24 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
25 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
26 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
27 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
28 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
29 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
30 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
31 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
32 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
33 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
34 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
35 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
36 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
37 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
38 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
39 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
40 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
44 /* PRIVATE FUNCTIONS ********************************************************/
48 RtlpGetLengthOfRunClear(
49 IN PRTL_BITMAP BitMapHeader
,
50 IN ULONG StartingIndex
,
53 ULONG Value
, BitPos
, Length
;
54 PULONG Buffer
, MaxBuffer
;
56 /* Calculate positions */
57 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ 32;
58 BitPos
= StartingIndex
& 31;
60 /* Calculate the maximum length */
61 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
62 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ 31) / 32;
64 /* Clear the bits that don't belong to this run */
65 Value
= *Buffer
++ >> BitPos
<< BitPos
;
67 /* Skip all clear ULONGs */
68 while (Value
== 0 && Buffer
< MaxBuffer
)
73 /* Did we reach the end? */
76 /* Return maximum length */
80 /* We hit a set bit, check how many clear bits are left */
81 BitScanForward(&BitPos
, Value
);
83 /* Calculate length up to where we read */
84 Length
= (Buffer
- BitMapHeader
->Buffer
) * 32 - StartingIndex
;
85 Length
+= BitPos
- 32;
87 /* Make sure we don't go past the last bit */
88 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
89 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
91 /* Return the result */
97 RtlpGetLengthOfRunSet(
98 IN PRTL_BITMAP BitMapHeader
,
99 IN ULONG StartingIndex
,
102 ULONG InvValue
, BitPos
, Length
;
103 PULONG Buffer
, MaxBuffer
;
105 /* Calculate positions */
106 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ 32;
107 BitPos
= StartingIndex
& 31;
109 /* Calculate the maximum length */
110 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
111 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ 31) / 32;
113 /* Get the inversed value, clear bits that don't belong to the run */
114 InvValue
= ~(*Buffer
++) >> BitPos
<< BitPos
;
116 /* Skip all set ULONGs */
117 while (InvValue
== 0 && Buffer
< MaxBuffer
)
119 InvValue
= ~(*Buffer
++);
122 /* Did we reach the end? */
125 /* Yes, return maximum */
129 /* We hit a clear bit, check how many set bits are left */
130 BitScanForward(&BitPos
, InvValue
);
132 /* Calculate length up to where we read */
133 Length
= (Buffer
- BitMapHeader
->Buffer
) * 32 - StartingIndex
;
134 Length
+= BitPos
- 32;
136 /* Make sure we don't go past the last bit */
137 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
138 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
140 /* Return the result */
145 /* PUBLIC FUNCTIONS **********************************************************/
149 RtlFindMostSignificantBit(ULONGLONG Value
)
153 if (BitScanReverse(&Position
, Value
>> 32))
155 return (CCHAR
)(Position
+ 32);
157 else if (BitScanReverse(&Position
, (ULONG
)Value
))
159 return (CCHAR
)Position
;
167 RtlFindLeastSignificantBit(ULONGLONG Value
)
171 if (BitScanForward(&Position
, (ULONG
)Value
))
173 return (CCHAR
)Position
;
175 else if (BitScanForward(&Position
, Value
>> 32))
177 return (CCHAR
)(Position
+ 32);
186 IN PRTL_BITMAP BitMapHeader
,
187 IN PULONG BitMapBuffer
,
188 IN ULONG SizeOfBitMap
)
190 /* Setup the bitmap header */
191 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
192 BitMapHeader
->Buffer
= BitMapBuffer
;
198 IN OUT PRTL_BITMAP BitMapHeader
)
200 ULONG LengthInUlongs
;
202 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
203 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, 0);
209 IN OUT PRTL_BITMAP BitMapHeader
)
211 ULONG LengthInUlongs
;
213 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
214 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, ~0);
220 IN PRTL_BITMAP BitMapHeader
,
223 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
224 BitMapHeader
->Buffer
[BitNumber
>> 5] &= ~(1 << (BitNumber
& 31));
230 IN PRTL_BITMAP BitMapHeader
,
233 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
234 BitMapHeader
->Buffer
[BitNumber
>> 5] |= (1 << (BitNumber
& 31));
240 IN PRTL_BITMAP BitMapHeader
,
241 IN ULONG StartingIndex
,
242 IN ULONG NumberToClear
)
247 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
249 /* Calculate buffer start and first bit index */
250 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
251 Bits
= StartingIndex
& 31;
253 /* Are we unaligned? */
256 /* Create an inverse mask by shifting MAXULONG */
257 Mask
= MAXULONG
<< Bits
;
259 /* This is what's left in the first ULONG */
262 /* Even less bits to clear? */
263 if (NumberToClear
< Bits
)
265 /* Calculate how many bits are left */
266 Bits
-= NumberToClear
;
268 /* Fixup the mask on the high side */
269 Mask
= Mask
<< Bits
>> Bits
;
271 /* Clear bits and return */
279 /* Update buffer and left bits */
281 NumberToClear
-= Bits
;
284 /* Clear all full ULONGs */
285 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
286 Buffer
+= NumberToClear
>> 5;
288 /* Clear what's left */
290 Mask
= MAXULONG
<< NumberToClear
;
297 IN PRTL_BITMAP BitMapHeader
,
298 IN ULONG StartingIndex
,
299 IN ULONG NumberToSet
)
304 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
306 /* Calculate buffer start and first bit index */
307 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
308 Bits
= StartingIndex
& 31;
310 /* Are we unaligned? */
313 /* Create a mask by shifting MAXULONG */
314 Mask
= MAXULONG
<< Bits
;
316 /* This is what's left in the first ULONG */
319 /* Even less bits to clear? */
320 if (NumberToSet
< Bits
)
322 /* Calculate how many bits are left */
325 /* Fixup the mask on the high side */
326 Mask
= Mask
<< Bits
>> Bits
;
328 /* Set bits and return */
336 /* Update buffer and left bits */
341 /* Set all full ULONGs */
342 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXULONG
);
343 Buffer
+= NumberToSet
>> 5;
345 /* Set what's left */
347 Mask
= MAXULONG
<< NumberToSet
;
354 IN PRTL_BITMAP BitMapHeader
,
357 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
358 return (BitMapHeader
->Buffer
[BitNumber
>> 5] >> (BitNumber
& 31)) & 1;
364 IN PRTL_BITMAP BitMapHeader
,
365 IN ULONG StartingIndex
,
368 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
374 IN PRTL_BITMAP BitMapHeader
,
375 IN ULONG StartingIndex
,
378 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
384 IN PRTL_BITMAP BitMapHeader
)
386 PUCHAR Byte
, MaxByte
;
389 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
390 MaxByte
= Byte
+ (BitMapHeader
->SizeOfBitMap
+ 7) / 8;
394 BitCount
+= BitCountTable
[*Byte
++];
396 while (Byte
<= MaxByte
);
403 RtlNumberOfClearBits(
404 IN PRTL_BITMAP BitMapHeader
)
407 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
413 IN PRTL_BITMAP BitMapHeader
,
414 IN ULONG NumberToFind
,
417 ULONG CurrentBit
, Margin
, CurrentLength
;
419 /* Check for valid parameters */
420 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
425 /* Check for trivial case */
426 if (NumberToFind
== 0)
431 /* First margin is end of bitmap */
432 Margin
= BitMapHeader
->SizeOfBitMap
;
435 /* Start with hint index, length is 0 */
436 CurrentBit
= HintIndex
;
438 /* Loop until something is found or the end is reached */
439 while (CurrentBit
+ NumberToFind
< Margin
)
441 /* Search for the next clear run, by skipping a set run */
442 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
446 /* Get length of the clear bit run */
447 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
451 /* Is this long enough? */
452 if (CurrentLength
>= NumberToFind
)
458 CurrentBit
+= CurrentLength
;
461 /* Did we start at a hint? */
464 /* Retry at the start */
465 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
477 IN PRTL_BITMAP BitMapHeader
,
478 IN ULONG NumberToFind
,
481 ULONG CurrentBit
, Margin
, CurrentLength
;
483 /* Check for valid parameters */
484 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
489 /* Check for trivial case */
490 if (NumberToFind
== 0)
495 /* First margin is end of bitmap */
496 Margin
= BitMapHeader
->SizeOfBitMap
;
499 /* Start with hint index, length is 0 */
500 CurrentBit
= HintIndex
;
502 /* Loop until something is found or the end is reached */
503 while (CurrentBit
+ NumberToFind
<= Margin
)
505 /* Search for the next set run, by skipping a clear run */
506 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
510 /* Get length of the set bit run */
511 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
515 /* Is this long enough? */
516 if (CurrentLength
>= NumberToFind
)
522 CurrentBit
+= CurrentLength
;
525 /* Did we start at a hint? */
528 /* Retry at the start */
529 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
540 RtlFindClearBitsAndSet(
541 PRTL_BITMAP BitMapHeader
,
547 /* Try to find clear bits */
548 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
550 /* Did we get something? */
551 if (Position
!= MAXULONG
)
553 /* Yes, set the bits */
554 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
557 /* Return what we found */
563 RtlFindSetBitsAndClear(
564 IN PRTL_BITMAP BitMapHeader
,
565 IN ULONG NumberToFind
,
570 /* Try to find set bits */
571 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
573 /* Did we get something? */
574 if (Position
!= MAXULONG
)
576 /* Yes, clear the bits */
577 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
580 /* Return what we found */
586 RtlFindNextForwardRunClear(
587 IN PRTL_BITMAP BitMapHeader
,
589 IN PULONG StartingRunIndex
)
593 /* Assume a set run first, count it's length */
594 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
595 *StartingRunIndex
= FromIndex
+ Length
;
597 /* Now return the length of the run */
598 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXULONG
);
603 RtlFindNextForwardRunSet(
604 IN PRTL_BITMAP BitMapHeader
,
606 IN PULONG StartingRunIndex
)
610 /* Assume a clear run first, count it's length */
611 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXULONG
);
612 *StartingRunIndex
= FromIndex
+ Length
;
614 /* Now return the length of the run */
615 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
620 RtlFindFirstRunClear(
621 IN PRTL_BITMAP BitMapHeader
,
622 IN PULONG StartingIndex
)
624 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
629 RtlFindLastBackwardRunClear(
630 IN PRTL_BITMAP BitMapHeader
,
632 IN PULONG StartingRunIndex
)
642 IN PRTL_BITMAP BitMapHeader
,
643 IN PRTL_BITMAP_RUN RunArray
,
644 IN ULONG SizeOfRunArray
,
645 IN BOOLEAN LocateLongestRuns
)
647 ULONG StartingIndex
, NumberOfBits
, Run
, FromIndex
= 0, SmallestRun
= 0;
650 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
653 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
657 /* Nothing more found? Quit looping. */
658 if (NumberOfBits
== 0) break;
660 /* Add another run */
661 RunArray
[Run
].StartingIndex
= StartingIndex
;
662 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
664 /* Update smallest run */
665 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
671 FromIndex
= StartingIndex
+ NumberOfBits
;
674 /* Check if we are finished */
675 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
677 /* Return the number of found runs */
684 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
688 /* Nothing more found? Quit looping. */
689 if (NumberOfBits
== 0) break;
691 /* Check if we have something to update */
692 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
694 /* Update smallest run */
695 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
696 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
699 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
701 /*Is this the new smallest run? */
702 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
704 /* Set it as new smallest run */
711 FromIndex
+= NumberOfBits
;
719 RtlFindLongestRunClear(
720 IN PRTL_BITMAP BitMapHeader
,
721 IN PULONG StartingIndex
)
723 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
728 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
732 /* Nothing more found? Quit looping. */
733 if (NumberOfBits
== 0) break;
735 /* Was that the longest run? */
736 if (NumberOfBits
> MaxNumberOfBits
)
739 MaxNumberOfBits
= NumberOfBits
;
740 *StartingIndex
= Index
;
744 FromIndex
+= NumberOfBits
;
747 return MaxNumberOfBits
;
752 RtlFindLongestRunSet(
753 IN PRTL_BITMAP BitMapHeader
,
754 IN PULONG StartingIndex
)
756 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
761 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
765 /* Nothing more found? Quit looping. */
766 if (NumberOfBits
== 0) break;
768 /* Was that the longest run? */
769 if (NumberOfBits
> MaxNumberOfBits
)
772 MaxNumberOfBits
= NumberOfBits
;
773 *StartingIndex
= Index
;
777 FromIndex
+= NumberOfBits
;
780 return MaxNumberOfBits
;