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
, CurrentLength
;
422 /* Check for valid parameters */
423 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
428 /* Check for trivial case */
429 if (NumberToFind
== 0)
434 /* Start with hint index, length is 0 */
435 CurrentBit
= HintIndex
;
438 /* Loop until something is found or the end is reached */
439 while (CurrentBit
+ NumberToFind
< BitMapHeader
->SizeOfBitMap
)
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
;
468 IN PRTL_BITMAP BitMapHeader
,
469 IN ULONG NumberToFind
,
472 ULONG CurrentBit
, CurrentLength
;
474 /* Check for valid parameters */
475 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
480 /* Check for trivial case */
481 if (NumberToFind
== 0)
486 /* Start with hint index, length is 0 */
487 CurrentBit
= HintIndex
;
490 /* Loop until something is found or the end is reached */
491 while (CurrentBit
+ NumberToFind
<= BitMapHeader
->SizeOfBitMap
)
493 /* Search for the next set run, by skipping a clear run */
494 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
498 /* Get length of the set bit run */
499 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
503 /* Is this long enough? */
504 if (CurrentLength
>= NumberToFind
)
510 CurrentBit
+= CurrentLength
;
519 RtlFindClearBitsAndSet(
520 PRTL_BITMAP BitMapHeader
,
526 /* Try to find clear bits */
527 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
529 /* Did we get something? */
530 if (Position
!= MAXULONG
)
532 /* Yes, set the bits */
533 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
536 /* Return what we found */
542 RtlFindSetBitsAndClear(
543 IN PRTL_BITMAP BitMapHeader
,
544 IN ULONG NumberToFind
,
549 /* Try to find set bits */
550 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
552 /* Did we get something? */
553 if (Position
!= MAXULONG
)
555 /* Yes, clear the bits */
556 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
559 /* Return what we found */
565 RtlFindNextForwardRunClear(
566 IN PRTL_BITMAP BitMapHeader
,
568 IN PULONG StartingRunIndex
)
572 /* Assume a set run first, count it's length */
573 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
574 *StartingRunIndex
= FromIndex
;
576 /* Now return the length of the run */
577 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXULONG
);
582 RtlFindNextForwardRunSet(
583 IN PRTL_BITMAP BitMapHeader
,
585 IN PULONG StartingRunIndex
)
589 /* Assume a clear run first, count it's length */
590 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXULONG
);
591 *StartingRunIndex
= FromIndex
;
593 /* Now return the length of the run */
594 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXULONG
);
599 RtlFindFirstRunClear(
600 IN PRTL_BITMAP BitMapHeader
,
601 IN PULONG StartingIndex
)
603 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
608 RtlFindLastBackwardRunClear(
609 IN PRTL_BITMAP BitMapHeader
,
611 IN PULONG StartingRunIndex
)
621 IN PRTL_BITMAP BitMapHeader
,
622 IN PRTL_BITMAP_RUN RunArray
,
623 IN ULONG SizeOfRunArray
,
624 IN BOOLEAN LocateLongestRuns
)
626 ULONG StartingIndex
, NumberOfBits
, Run
, FromIndex
= 0, SmallestRun
= 0;
629 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
632 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
636 /* Nothing more found? Quit looping. */
637 if (NumberOfBits
== 0) break;
639 /* Add another run */
640 RunArray
[Run
].StartingIndex
= StartingIndex
;
641 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
643 /* Update smallest run */
644 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
650 FromIndex
+= NumberOfBits
;
653 /* Check if we are finished */
654 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
656 /* Return the number of found runs */
663 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
667 /* Nothing more found? Quit looping. */
668 if (NumberOfBits
== 0) break;
670 /* Check if we have something to update */
671 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
673 /* Update smallest run */
674 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
675 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
678 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
680 /*Is this the new smallest run? */
681 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
683 /* Set it as new smallest run */
690 FromIndex
+= NumberOfBits
;
698 RtlFindLongestRunClear(
699 IN PRTL_BITMAP BitMapHeader
,
700 IN PULONG StartingIndex
)
702 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
707 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
711 /* Nothing more found? Quit looping. */
712 if (NumberOfBits
== 0) break;
714 /* Was that the longest run? */
715 if (NumberOfBits
> MaxNumberOfBits
)
718 MaxNumberOfBits
= NumberOfBits
;
719 *StartingIndex
= Index
;
723 FromIndex
+= NumberOfBits
;
726 return MaxNumberOfBits
;
731 RtlFindLongestRunSet(
732 IN PRTL_BITMAP BitMapHeader
,
733 IN PULONG StartingIndex
)
735 ULONG NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
740 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
744 /* Nothing more found? Quit looping. */
745 if (NumberOfBits
== 0) break;
747 /* Was that the longest run? */
748 if (NumberOfBits
> MaxNumberOfBits
)
751 MaxNumberOfBits
= NumberOfBits
;
752 *StartingIndex
= Index
;
756 FromIndex
+= NumberOfBits
;
759 return MaxNumberOfBits
;