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 Position
+ 32;
157 else if (BitScanReverse(&Position
, (ULONG
)Value
))
167 RtlFindLeastSignificantBit(ULONGLONG Value
)
171 if (BitScanForward(&Position
, (ULONG
)Value
))
175 else if (BitScanForward(&Position
, Value
>> 32))
177 return Position
+ 32;
186 IN PRTL_BITMAP BitMapHeader
,
187 IN PULONG BitMapBuffer
,
188 IN ULONG SizeOfBitMap
)
190 // FIXME: some bugger here!
191 //ASSERT(SizeOfBitMap > 0);
193 /* Setup the bitmap header */
194 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
195 BitMapHeader
->Buffer
= BitMapBuffer
;
201 IN OUT PRTL_BITMAP BitMapHeader
)
203 ULONG LengthInUlongs
;
205 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
206 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, 0);
212 IN OUT PRTL_BITMAP BitMapHeader
)
214 ULONG LengthInUlongs
;
216 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ 31) >> 5;
217 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
<< 2, ~0);
223 IN PRTL_BITMAP BitMapHeader
,
226 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
227 BitMapHeader
->Buffer
[BitNumber
>> 5] &= ~(1 << (BitNumber
& 31));
233 IN PRTL_BITMAP BitMapHeader
,
236 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
237 BitMapHeader
->Buffer
[BitNumber
>> 5] |= (1 << (BitNumber
& 31));
243 IN PRTL_BITMAP BitMapHeader
,
244 IN ULONG StartingIndex
,
245 IN ULONG NumberToClear
)
250 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
252 /* Calculate buffer start and first bit index */
253 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
254 Bits
= StartingIndex
& 31;
256 /* Are we unaligned? */
259 /* Create an inverse mask by shifting MAXULONG */
260 Mask
= MAXULONG
<< Bits
;
262 /* This is what's left in the first ULONG */
265 /* Even less bits to clear? */
266 if (NumberToClear
< Bits
)
268 /* Calculate how many bits are left */
269 Bits
-= NumberToClear
;
271 /* Fixup the mask on the high side */
272 Mask
= Mask
<< Bits
>> Bits
;
274 /* Clear bits and return */
282 /* Update buffer and left bits */
284 NumberToClear
-= Bits
;
287 /* Clear all full ULONGs */
288 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
289 Buffer
+= NumberToClear
>> 5;
291 /* Clear what's left */
293 Mask
= MAXULONG
<< NumberToClear
;
300 IN PRTL_BITMAP BitMapHeader
,
301 IN ULONG StartingIndex
,
302 IN ULONG NumberToSet
)
307 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
309 /* Calculate buffer start and first bit index */
310 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
>> 5];
311 Bits
= StartingIndex
& 31;
313 /* Are we unaligned? */
316 /* Create a mask by shifting MAXULONG */
317 Mask
= MAXULONG
<< Bits
;
319 /* This is what's left in the first ULONG */
322 /* Even less bits to clear? */
323 if (NumberToSet
< Bits
)
325 /* Calculate how many bits are left */
328 /* Fixup the mask on the high side */
329 Mask
= Mask
<< Bits
>> Bits
;
331 /* Set bits and return */
339 /* Update buffer and left bits */
344 /* Set all full ULONGs */
345 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXULONG
);
346 Buffer
+= NumberToSet
>> 5;
348 /* Set what's left */
350 Mask
= MAXULONG
<< NumberToSet
;
357 IN PRTL_BITMAP BitMapHeader
,
360 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
361 return (BitMapHeader
->Buffer
[BitNumber
>> 5] >> (BitNumber
& 31)) & 1;
367 IN PRTL_BITMAP BitMapHeader
,
368 IN ULONG StartingIndex
,
371 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
377 IN PRTL_BITMAP BitMapHeader
,
378 IN ULONG StartingIndex
,
381 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
387 IN PRTL_BITMAP BitMapHeader
)
389 PUCHAR Byte
, MaxByte
;
392 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
393 MaxByte
= Byte
+ (BitMapHeader
->SizeOfBitMap
+ 7) / 8;
397 BitCount
+= BitCountTable
[*Byte
++];
399 while (Byte
<= MaxByte
);
406 RtlNumberOfClearBits(
407 IN PRTL_BITMAP BitMapHeader
)
410 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
416 IN PRTL_BITMAP BitMapHeader
,
417 IN ULONG NumberToFind
,
420 ULONG CurrentBit
, Margin
, CurrentLength
;
422 /* Check for valid parameters */
423 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
428 /* Check for trivial case */
429 if (NumberToFind
== 0)
434 /* First margin is end of bitmap */
435 Margin
= BitMapHeader
->SizeOfBitMap
;
438 /* Start with hint index, length is 0 */
439 CurrentBit
= HintIndex
;
441 /* Loop until something is found or the end is reached */
442 while (CurrentBit
+ NumberToFind
< Margin
)
444 /* Search for the next clear run, by skipping a set run */
445 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
449 /* Get length of the clear bit run */
450 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
454 /* Is this long enough? */
455 if (CurrentLength
>= NumberToFind
)
461 CurrentBit
+= CurrentLength
;
464 /* Did we start at a hint? */
467 /* Retry at the start */
468 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
480 IN PRTL_BITMAP BitMapHeader
,
481 IN ULONG NumberToFind
,
484 ULONG CurrentBit
, CurrentLength
;
486 /* Check for valid parameters */
487 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
492 /* Check for trivial case */
493 if (NumberToFind
== 0)
498 /* Start with hint index, length is 0 */
499 CurrentBit
= HintIndex
;
502 /* Loop until something is found or the end is reached */
503 while (CurrentBit
+ NumberToFind
<= BitMapHeader
->SizeOfBitMap
)
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
;
531 RtlFindClearBitsAndSet(
532 PRTL_BITMAP BitMapHeader
,
538 /* Try to find clear bits */
539 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
541 /* Did we get something? */
542 if (Position
!= MAXULONG
)
544 /* Yes, set the bits */
545 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
548 /* Return what we found */
554 RtlFindSetBitsAndClear(
555 IN PRTL_BITMAP BitMapHeader
,
556 IN ULONG NumberToFind
,
561 /* Try to find set bits */
562 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
564 /* Did we get something? */
565 if (Position
!= MAXULONG
)
567 /* Yes, clear the bits */
568 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
571 /* Return what we found */
577 RtlFindNextForwardRunClear(
578 IN PRTL_BITMAP BitMapHeader
,
580 IN PULONG StartingRunIndex
)
584 /* Assume a set run first, count it's length */
585 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
586 *StartingRunIndex
= FromIndex
+ Length
;
588 /* Now return the length of the run */
589 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXULONG
);
594 RtlFindNextForwardRunSet(
595 IN PRTL_BITMAP BitMapHeader
,
597 IN PULONG StartingRunIndex
)
601 /* Assume a clear run first, count it's length */
602 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXULONG
);
603 *StartingRunIndex
= FromIndex
+ Length
;
605 /* Now return the length of the run */
606 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
611 RtlFindFirstRunClear(
612 IN PRTL_BITMAP BitMapHeader
,
613 IN PULONG StartingIndex
)
615 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
620 RtlFindLastBackwardRunClear(
621 IN PRTL_BITMAP BitMapHeader
,
623 IN PULONG StartingRunIndex
)
633 IN PRTL_BITMAP BitMapHeader
,
634 IN PRTL_BITMAP_RUN RunArray
,
635 IN ULONG SizeOfRunArray
,
636 IN BOOLEAN LocateLongestRuns
)
638 ULONG StartingIndex
, NumberOfBits
, Run
, FromIndex
= 0, SmallestRun
= 0;
641 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
644 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
648 /* Nothing more found? Quit looping. */
649 if (NumberOfBits
== 0) break;
651 /* Add another run */
652 RunArray
[Run
].StartingIndex
= StartingIndex
;
653 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
655 /* Update smallest run */
656 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
662 FromIndex
= StartingIndex
+ NumberOfBits
;
665 /* Check if we are finished */
666 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
668 /* Return the number of found runs */
675 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
679 /* Nothing more found? Quit looping. */
680 if (NumberOfBits
== 0) break;
682 /* Check if we have something to update */
683 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
685 /* Update smallest run */
686 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
687 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
690 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
692 /*Is this the new smallest run? */
693 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
695 /* Set it as new smallest run */
702 FromIndex
+= NumberOfBits
;
710 RtlFindLongestRunClear(
711 IN PRTL_BITMAP BitMapHeader
,
712 IN PULONG StartingIndex
)
714 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
719 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
723 /* Nothing more found? Quit looping. */
724 if (NumberOfBits
== 0) break;
726 /* Was that the longest run? */
727 if (NumberOfBits
> MaxNumberOfBits
)
730 MaxNumberOfBits
= NumberOfBits
;
731 *StartingIndex
= Index
;
735 FromIndex
+= NumberOfBits
;
738 return MaxNumberOfBits
;
743 RtlFindLongestRunSet(
744 IN PRTL_BITMAP BitMapHeader
,
745 IN PULONG StartingIndex
)
747 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
752 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
756 /* Nothing more found? Quit looping. */
757 if (NumberOfBits
== 0) break;
759 /* Was that the longest run? */
760 if (NumberOfBits
> MaxNumberOfBits
)
763 MaxNumberOfBits
= NumberOfBits
;
764 *StartingIndex
= Index
;
768 FromIndex
+= NumberOfBits
;
771 return MaxNumberOfBits
;