2 * PROJECT: ReactOS system libraries
3 * LICENSE: GNU GPL - See COPYING in the top level directory
4 * BSD - See COPYING.ARM in the top level directory
5 * FILE: lib/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
7 * PROGRAMMER: Timo Kreuzer (timo.kreuzer@reactos.org)
10 /* INCLUDES *****************************************************************/
21 /* DATA *********************************************************************/
23 /* Number of set bits per byte value */
28 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
29 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
30 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
31 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
32 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
33 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
34 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
35 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
36 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
37 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
38 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
39 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
40 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
41 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
42 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
43 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
44 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
48 /* PRIVATE FUNCTIONS ********************************************************/
52 RtlpGetLengthOfRunClear(
53 IN PRTL_BITMAP BitMapHeader
,
54 IN ULONG StartingIndex
,
57 ULONG Value
, BitPos
, Length
;
58 PULONG Buffer
, MaxBuffer
;
60 /* Calculate positions */
61 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ 32;
62 BitPos
= StartingIndex
& 31;
64 /* Calculate the maximum length */
65 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
66 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ 31) / 32;
68 /* Clear the bits that don't belong to this run */
69 Value
= *Buffer
++ >> BitPos
<< BitPos
;
71 /* Skip all clear ULONGs */
72 while (Value
== 0 && Buffer
< MaxBuffer
)
77 /* Did we reach the end? */
80 /* Return maximum length */
84 /* We hit a set bit, check how many clear bits are left */
85 BitScanForward(&BitPos
, Value
);
87 /* Calculate length up to where we read */
88 Length
= (ULONG
)(Buffer
- BitMapHeader
->Buffer
) * 32 - StartingIndex
;
89 Length
+= BitPos
- 32;
91 /* Make sure we don't go past the last bit */
92 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
93 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
95 /* Return the result */
101 RtlpGetLengthOfRunSet(
102 IN PRTL_BITMAP BitMapHeader
,
103 IN ULONG StartingIndex
,
106 ULONG InvValue
, BitPos
, Length
;
107 PULONG Buffer
, MaxBuffer
;
109 /* Calculate positions */
110 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ 32;
111 BitPos
= StartingIndex
& 31;
113 /* Calculate the maximum length */
114 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
115 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ 31) / 32;
117 /* Get the inversed value, clear bits that don't belong to the run */
118 InvValue
= ~(*Buffer
++) >> BitPos
<< BitPos
;
120 /* Skip all set ULONGs */
121 while (InvValue
== 0 && Buffer
< MaxBuffer
)
123 InvValue
= ~(*Buffer
++);
126 /* Did we reach the end? */
129 /* Yes, return maximum */
133 /* We hit a clear bit, check how many set bits are left */
134 BitScanForward(&BitPos
, InvValue
);
136 /* Calculate length up to where we read */
137 Length
= (ULONG
)(Buffer
- BitMapHeader
->Buffer
) * 32 - StartingIndex
;
138 Length
+= BitPos
- 32;
140 /* Make sure we don't go past the last bit */
141 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
142 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
144 /* Return the result */
149 /* PUBLIC FUNCTIONS **********************************************************/
153 RtlFindMostSignificantBit(ULONGLONG Value
)
158 if (BitScanReverse64(&Position
, Value
))
160 return (CCHAR
)Position
;
163 if (BitScanReverse(&Position
, Value
>> 32))
165 return (CCHAR
)(Position
+ 32);
167 else if (BitScanReverse(&Position
, (ULONG
)Value
))
169 return (CCHAR
)Position
;
177 RtlFindLeastSignificantBit(ULONGLONG Value
)
182 if (BitScanForward64(&Position
, Value
))
184 return (CCHAR
)Position
;
187 if (BitScanForward(&Position
, (ULONG
)Value
))
189 return (CCHAR
)Position
;
191 else if (BitScanForward(&Position
, Value
>> 32))
193 return (CCHAR
)(Position
+ 32);
202 IN PRTL_BITMAP BitMapHeader
,
203 IN PULONG BitMapBuffer
,
204 IN ULONG SizeOfBitMap
)
206 /* Setup the bitmap header */
207 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
208 BitMapHeader
->Buffer
= BitMapBuffer
;
214 IN OUT PRTL_BITMAP BitMapHeader
)
216 ULONG LengthInUlongs
;
218 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
219 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, 0);
225 IN OUT PRTL_BITMAP BitMapHeader
)
227 ULONG LengthInUlongs
;
229 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
230 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, ~0);
236 IN PRTL_BITMAP BitMapHeader
,
239 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
240 BitMapHeader
->Buffer
[BitNumber
>> 5] &= ~(1 << (BitNumber
& 31));
246 IN PRTL_BITMAP BitMapHeader
,
249 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
250 BitMapHeader
->Buffer
[BitNumber
>> 5] |= (1 << (BitNumber
& 31));
256 IN PRTL_BITMAP BitMapHeader
,
257 IN ULONG StartingIndex
,
258 IN ULONG NumberToClear
)
263 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
265 /* Calculate buffer start and first bit index */
266 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
267 Bits
= StartingIndex
& 31;
269 /* Are we unaligned? */
272 /* Create an inverse mask by shifting MAXULONG */
273 Mask
= MAXULONG
<< Bits
;
275 /* This is what's left in the first ULONG */
278 /* Even less bits to clear? */
279 if (NumberToClear
< Bits
)
281 /* Calculate how many bits are left */
282 Bits
-= NumberToClear
;
284 /* Fixup the mask on the high side */
285 Mask
= Mask
<< Bits
>> Bits
;
287 /* Clear bits and return */
295 /* Update buffer and left bits */
297 NumberToClear
-= Bits
;
300 /* Clear all full ULONGs */
301 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
302 Buffer
+= NumberToClear
>> 5;
304 /* Clear what's left */
306 Mask
= MAXULONG
<< NumberToClear
;
313 IN PRTL_BITMAP BitMapHeader
,
314 IN ULONG StartingIndex
,
315 IN ULONG NumberToSet
)
320 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
322 /* Calculate buffer start and first bit index */
323 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
324 Bits
= StartingIndex
& 31;
326 /* Are we unaligned? */
329 /* Create a mask by shifting MAXULONG */
330 Mask
= MAXULONG
<< Bits
;
332 /* This is what's left in the first ULONG */
335 /* Even less bits to clear? */
336 if (NumberToSet
< Bits
)
338 /* Calculate how many bits are left */
341 /* Fixup the mask on the high side */
342 Mask
= Mask
<< Bits
>> Bits
;
344 /* Set bits and return */
352 /* Update buffer and left bits */
357 /* Set all full ULONGs */
358 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXULONG
);
359 Buffer
+= NumberToSet
>> 5;
361 /* Set what's left */
363 Mask
= MAXULONG
<< NumberToSet
;
370 IN PRTL_BITMAP BitMapHeader
,
373 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
374 return (BitMapHeader
->Buffer
[BitNumber
>> 5] >> (BitNumber
& 31)) & 1;
380 IN PRTL_BITMAP BitMapHeader
,
381 IN ULONG StartingIndex
,
384 /* Verify parameters */
385 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
386 (StartingIndex
+ Length
<= StartingIndex
))
389 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
395 IN PRTL_BITMAP BitMapHeader
,
396 IN ULONG StartingIndex
,
399 /* Verify parameters */
400 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
401 (StartingIndex
+ Length
<= StartingIndex
))
404 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
410 IN PRTL_BITMAP BitMapHeader
)
412 PUCHAR Byte
, MaxByte
;
413 ULONG BitCount
= 0, Shift
;
415 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
416 MaxByte
= Byte
+ BitMapHeader
->SizeOfBitMap
/ 8;
418 while (Byte
< MaxByte
)
420 BitCount
+= BitCountTable
[*Byte
++];
423 Shift
= 8 - (BitMapHeader
->SizeOfBitMap
& 7);
424 BitCount
+= BitCountTable
[((*Byte
) << Shift
) & 0xFF];
431 RtlNumberOfClearBits(
432 IN PRTL_BITMAP BitMapHeader
)
435 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
441 IN PRTL_BITMAP BitMapHeader
,
442 IN ULONG NumberToFind
,
445 ULONG CurrentBit
, Margin
, CurrentLength
;
447 /* Check for valid parameters */
448 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
453 /* Check if the hint is outside the bitmap */
454 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
456 /* Check for trivial case */
457 if (NumberToFind
== 0)
459 /* Return hint rounded down to byte margin */
460 return HintIndex
& ~7;
463 /* First margin is end of bitmap */
464 Margin
= BitMapHeader
->SizeOfBitMap
;
467 /* Start with hint index, length is 0 */
468 CurrentBit
= HintIndex
;
470 /* Loop until something is found or the end is reached */
471 while (CurrentBit
+ NumberToFind
< Margin
)
473 /* Search for the next clear run, by skipping a set run */
474 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
478 /* Get length of the clear bit run */
479 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
483 /* Is this long enough? */
484 if (CurrentLength
>= NumberToFind
)
490 CurrentBit
+= CurrentLength
;
493 /* Did we start at a hint? */
496 /* Retry at the start */
497 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
509 IN PRTL_BITMAP BitMapHeader
,
510 IN ULONG NumberToFind
,
513 ULONG CurrentBit
, Margin
, CurrentLength
;
515 /* Check for valid parameters */
516 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
521 /* Check if the hint is outside the bitmap */
522 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
524 /* Check for trivial case */
525 if (NumberToFind
== 0)
527 /* Return hint rounded down to byte margin */
528 return HintIndex
& ~7;
531 /* First margin is end of bitmap */
532 Margin
= BitMapHeader
->SizeOfBitMap
;
535 /* Start with hint index, length is 0 */
536 CurrentBit
= HintIndex
;
538 /* Loop until something is found or the end is reached */
539 while (CurrentBit
+ NumberToFind
<= Margin
)
541 /* Search for the next set run, by skipping a clear run */
542 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
546 /* Get length of the set bit run */
547 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
551 /* Is this long enough? */
552 if (CurrentLength
>= NumberToFind
)
558 CurrentBit
+= CurrentLength
;
561 /* Did we start at a hint? */
564 /* Retry at the start */
565 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
576 RtlFindClearBitsAndSet(
577 PRTL_BITMAP BitMapHeader
,
583 /* Try to find clear bits */
584 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
586 /* Did we get something? */
587 if (Position
!= MAXULONG
)
589 /* Yes, set the bits */
590 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
593 /* Return what we found */
599 RtlFindSetBitsAndClear(
600 IN PRTL_BITMAP BitMapHeader
,
601 IN ULONG NumberToFind
,
606 /* Try to find set bits */
607 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
609 /* Did we get something? */
610 if (Position
!= MAXULONG
)
612 /* Yes, clear the bits */
613 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
616 /* Return what we found */
622 RtlFindNextForwardRunClear(
623 IN PRTL_BITMAP BitMapHeader
,
625 IN PULONG StartingRunIndex
)
629 /* Check for buffer overrun */
630 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
632 *StartingRunIndex
= FromIndex
;
636 /* Assume a set run first, count it's length */
637 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
638 *StartingRunIndex
= FromIndex
+ Length
;
640 /* Now return the length of the run */
641 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXULONG
);
646 RtlFindNextForwardRunSet(
647 IN PRTL_BITMAP BitMapHeader
,
649 IN PULONG StartingRunIndex
)
653 /* Check for buffer overrun */
654 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
656 *StartingRunIndex
= FromIndex
;
660 /* Assume a clear run first, count it's length */
661 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXULONG
);
662 *StartingRunIndex
= FromIndex
+ Length
;
664 /* Now return the length of the run */
665 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
670 RtlFindFirstRunClear(
671 IN PRTL_BITMAP BitMapHeader
,
672 IN PULONG StartingIndex
)
674 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
679 RtlFindLastBackwardRunClear(
680 IN PRTL_BITMAP BitMapHeader
,
682 IN PULONG StartingRunIndex
)
692 IN PRTL_BITMAP BitMapHeader
,
693 IN PRTL_BITMAP_RUN RunArray
,
694 IN ULONG SizeOfRunArray
,
695 IN BOOLEAN LocateLongestRuns
)
697 ULONG StartingIndex
, NumberOfBits
, Run
, FromIndex
= 0, SmallestRun
= 0;
700 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
703 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
707 /* Nothing more found? Quit looping. */
708 if (NumberOfBits
== 0) break;
710 /* Add another run */
711 RunArray
[Run
].StartingIndex
= StartingIndex
;
712 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
714 /* Update smallest run */
715 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
721 FromIndex
= StartingIndex
+ NumberOfBits
;
724 /* Check if we are finished */
725 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
727 /* Return the number of found runs */
734 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
738 /* Nothing more found? Quit looping. */
739 if (NumberOfBits
== 0) break;
741 /* Check if we have something to update */
742 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
744 /* Update smallest run */
745 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
746 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
749 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
751 /*Is this the new smallest run? */
752 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
754 /* Set it as new smallest run */
761 FromIndex
+= NumberOfBits
;
769 RtlFindLongestRunClear(
770 IN PRTL_BITMAP BitMapHeader
,
771 IN PULONG StartingIndex
)
773 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
778 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
782 /* Nothing more found? Quit looping. */
783 if (NumberOfBits
== 0) break;
785 /* Was that the longest run? */
786 if (NumberOfBits
> MaxNumberOfBits
)
789 MaxNumberOfBits
= NumberOfBits
;
790 *StartingIndex
= Index
;
794 FromIndex
+= NumberOfBits
;
797 return MaxNumberOfBits
;
802 RtlFindLongestRunSet(
803 IN PRTL_BITMAP BitMapHeader
,
804 IN PULONG StartingIndex
)
806 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
811 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
815 /* Nothing more found? Quit looping. */
816 if (NumberOfBits
== 0) break;
818 /* Was that the longest run? */
819 if (NumberOfBits
> MaxNumberOfBits
)
822 MaxNumberOfBits
= NumberOfBits
;
823 *StartingIndex
= Index
;
827 FromIndex
+= NumberOfBits
;
830 return MaxNumberOfBits
;