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 #ifdef USE_RTL_BITMAP64
23 #define MAXINDEX 0xFFFFFFFFFFFFFFFF
24 typedef ULONG64 BITMAP_INDEX
, *PBITMAP_INDEX
;
25 typedef ULONG64 BITMAP_BUFFER
, *PBITMAP_BUFFER
;
26 #define RTL_BITMAP RTL_BITMAP64
27 #define PRTL_BITMAP PRTL_BITMAP64
28 #define RTL_BITMAP_RUN RTL_BITMAP_RUN64
29 #define PRTL_BITMAP_RUN PRTL_BITMAP_RUN64
31 #define BitScanForward(Index, Mask) \
32 do { unsigned long tmp; BitScanForward64(&tmp, Mask); *Index = tmp; } while (0)
33 #define RtlFillMemoryUlong RtlFillMemoryUlonglong
35 #define RtlInitializeBitMap RtlInitializeBitMap64
36 #define RtlClearAllBits RtlClearAllBits64
37 #define RtlSetAllBits RtlSetAllBits64
38 #define RtlClearBit RtlClearBit64
39 #define RtlSetBit RtlSetBit64
40 #define RtlClearBits RtlClearBits64
41 #define RtlSetBits RtlSetBits64
42 #define RtlTestBit RtlTestBit64
43 #define RtlAreBitsClear RtlAreBitsClear64
44 #define RtlAreBitsSet RtlAreBitsSet64
45 #define RtlNumberOfSetBits RtlNumberOfSetBits64
46 #define RtlNumberOfClearBits RtlNumberOfClearBits64
47 #define RtlFindClearBits RtlFindClearBits64
48 #define RtlFindSetBits RtlFindSetBits64
49 #define RtlFindClearBitsAndSet RtlFindClearBitsAndSet64
50 #define RtlFindSetBitsAndClear RtlFindSetBitsAndClear64
51 #define RtlFindNextForwardRunClear RtlFindNextForwardRunClear64
52 #define RtlFindNextForwardRunSet RtlFindNextForwardRunSet64
53 #define RtlFindFirstRunClear RtlFindFirstRunClear64
54 #define RtlFindLastBackwardRunClear RtlFindLastBackwardRunClear64
55 #define RtlFindClearRuns RtlFindClearRuns64
56 #define RtlFindLongestRunClear RtlFindLongestRunClear64
57 #define RtlFindLongestRunSet RtlFindLongestRunSet64
60 #define MAXINDEX 0xFFFFFFFF
61 typedef ULONG BITMAP_INDEX
, *PBITMAP_INDEX
;
62 typedef ULONG BITMAP_BUFFER
, *PBITMAP_BUFFER
;
65 /* DATA *********************************************************************/
67 /* Number of set bits per byte value */
72 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
73 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
74 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
75 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
76 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
77 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
78 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
79 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
80 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
81 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
82 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
83 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
84 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
85 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
86 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
87 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
88 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
92 /* PRIVATE FUNCTIONS ********************************************************/
96 RtlpGetLengthOfRunClear(
97 _In_ PRTL_BITMAP BitMapHeader
,
98 _In_ BITMAP_INDEX StartingIndex
,
99 _In_ BITMAP_INDEX MaxLength
)
101 BITMAP_INDEX Value
, BitPos
, Length
;
102 PBITMAP_BUFFER Buffer
, MaxBuffer
;
104 /* Calculate positions */
105 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
106 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
108 /* Calculate the maximum length */
109 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
110 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
112 /* Clear the bits that don't belong to this run */
113 Value
= *Buffer
++ >> BitPos
<< BitPos
;
115 /* Skip all clear ULONGs */
116 while (Value
== 0 && Buffer
< MaxBuffer
)
121 /* Did we reach the end? */
124 /* Return maximum length */
128 /* We hit a set bit, check how many clear bits are left */
129 BitScanForward(&BitPos
, Value
);
131 /* Calculate length up to where we read */
132 Length
= (BITMAP_INDEX
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
133 Length
+= BitPos
- _BITCOUNT
;
135 /* Make sure we don't go past the last bit */
136 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
137 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
139 /* Return the result */
145 RtlpGetLengthOfRunSet(
146 _In_ PRTL_BITMAP BitMapHeader
,
147 _In_ BITMAP_INDEX StartingIndex
,
148 _In_ BITMAP_INDEX MaxLength
)
150 BITMAP_INDEX InvValue
, BitPos
, Length
;
151 PBITMAP_BUFFER Buffer
, MaxBuffer
;
153 /* Calculate positions */
154 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
155 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
157 /* Calculate the maximum length */
158 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
159 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
161 /* Get the inversed value, clear bits that don't belong to the run */
162 InvValue
= ~(*Buffer
++) >> BitPos
<< BitPos
;
164 /* Skip all set ULONGs */
165 while (InvValue
== 0 && Buffer
< MaxBuffer
)
167 InvValue
= ~(*Buffer
++);
170 /* Did we reach the end? */
173 /* Yes, return maximum */
177 /* We hit a clear bit, check how many set bits are left */
178 BitScanForward(&BitPos
, InvValue
);
180 /* Calculate length up to where we read */
181 Length
= (ULONG
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
182 Length
+= BitPos
- _BITCOUNT
;
184 /* Make sure we don't go past the last bit */
185 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
186 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
188 /* Return the result */
193 /* PUBLIC FUNCTIONS **********************************************************/
195 #ifndef USE_RTL_BITMAP64
198 RtlFindMostSignificantBit(ULONGLONG Value
)
203 if (BitScanReverse64(&Position
, Value
))
205 return (CCHAR
)Position
;
208 if (BitScanReverse(&Position
, Value
>> _BITCOUNT
))
210 return (CCHAR
)(Position
+ _BITCOUNT
);
212 else if (BitScanReverse(&Position
, (ULONG
)Value
))
214 return (CCHAR
)Position
;
222 RtlFindLeastSignificantBit(ULONGLONG Value
)
227 if (BitScanForward64(&Position
, Value
))
229 return (CCHAR
)Position
;
232 if (BitScanForward(&Position
, (ULONG
)Value
))
234 return (CCHAR
)Position
;
236 else if (BitScanForward(&Position
, Value
>> _BITCOUNT
))
238 return (CCHAR
)(Position
+ _BITCOUNT
);
243 #endif /* !USE_RTL_BITMAP64 */
248 _Out_ PRTL_BITMAP BitMapHeader
,
249 _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer
,
250 _In_opt_ ULONG SizeOfBitMap
)
252 /* Setup the bitmap header */
253 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
254 BitMapHeader
->Buffer
= BitMapBuffer
;
260 _In_ PRTL_BITMAP BitMapHeader
)
262 BITMAP_INDEX LengthInUlongs
;
264 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
265 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), 0);
271 _In_ PRTL_BITMAP BitMapHeader
)
273 BITMAP_INDEX LengthInUlongs
;
275 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
276 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), ~0);
282 _In_ PRTL_BITMAP BitMapHeader
,
283 _In_ BITMAP_INDEX BitNumber
)
285 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
286 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] &= ~(1 << (BitNumber
& (_BITCOUNT
- 1)));
292 _In_ PRTL_BITMAP BitMapHeader
,
293 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
295 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
296 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] |= ((BITMAP_INDEX
)1 << (BitNumber
& (_BITCOUNT
- 1)));
302 _In_ PRTL_BITMAP BitMapHeader
,
303 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToClear
) BITMAP_INDEX StartingIndex
,
304 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToClear
)
306 BITMAP_INDEX Bits
, Mask
;
307 PBITMAP_BUFFER Buffer
;
309 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
311 /* Calculate buffer start and first bit index */
312 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
313 Bits
= StartingIndex
& (_BITCOUNT
- 1);
315 /* Are we unaligned? */
318 /* Create an inverse mask by shifting MAXINDEX */
319 Mask
= MAXINDEX
<< Bits
;
321 /* This is what's left in the first ULONG */
322 Bits
= _BITCOUNT
- Bits
;
324 /* Even less bits to clear? */
325 if (NumberToClear
< Bits
)
327 /* Calculate how many bits are left */
328 Bits
-= NumberToClear
;
330 /* Fixup the mask on the high side */
331 Mask
= Mask
<< Bits
>> Bits
;
333 /* Clear bits and return */
341 /* Update buffer and left bits */
343 NumberToClear
-= Bits
;
346 /* Clear all full ULONGs */
347 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
348 Buffer
+= NumberToClear
/ _BITCOUNT
;
350 /* Clear what's left */
351 NumberToClear
&= (_BITCOUNT
- 1);
352 Mask
= MAXINDEX
<< NumberToClear
;
359 _In_ PRTL_BITMAP BitMapHeader
,
360 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToSet
) BITMAP_INDEX StartingIndex
,
361 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToSet
)
363 BITMAP_INDEX Bits
, Mask
;
364 PBITMAP_BUFFER Buffer
;
366 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
368 /* Calculate buffer start and first bit index */
369 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
370 Bits
= StartingIndex
& (_BITCOUNT
- 1);
372 /* Are we unaligned? */
375 /* Create a mask by shifting MAXINDEX */
376 Mask
= MAXINDEX
<< Bits
;
378 /* This is what's left in the first ULONG */
379 Bits
= _BITCOUNT
- Bits
;
381 /* Even less bits to clear? */
382 if (NumberToSet
< Bits
)
384 /* Calculate how many bits are left */
387 /* Fixup the mask on the high side */
388 Mask
= Mask
<< Bits
>> Bits
;
390 /* Set bits and return */
398 /* Update buffer and left bits */
403 /* Set all full ULONGs */
404 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXINDEX
);
405 Buffer
+= NumberToSet
/ _BITCOUNT
;
407 /* Set what's left */
408 NumberToSet
&= (_BITCOUNT
- 1);
409 Mask
= MAXINDEX
<< NumberToSet
;
416 _In_ PRTL_BITMAP BitMapHeader
,
417 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
419 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
420 return (BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] >> (BitNumber
& (_BITCOUNT
- 1))) & 1;
426 _In_ PRTL_BITMAP BitMapHeader
,
427 _In_ BITMAP_INDEX StartingIndex
,
428 _In_ BITMAP_INDEX Length
)
430 /* Verify parameters */
431 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
432 (StartingIndex
+ Length
<= StartingIndex
))
435 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
441 _In_ PRTL_BITMAP BitMapHeader
,
442 _In_ BITMAP_INDEX StartingIndex
,
443 _In_ BITMAP_INDEX Length
)
445 /* Verify parameters */
446 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
447 (StartingIndex
+ Length
<= StartingIndex
))
450 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
456 _In_ PRTL_BITMAP BitMapHeader
)
458 PUCHAR Byte
, MaxByte
;
459 BITMAP_INDEX BitCount
= 0;
462 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
463 MaxByte
= Byte
+ BitMapHeader
->SizeOfBitMap
/ 8;
465 while (Byte
< MaxByte
)
467 BitCount
+= BitCountTable
[*Byte
++];
470 Shift
= 8 - (BitMapHeader
->SizeOfBitMap
& 7);
471 BitCount
+= BitCountTable
[((*Byte
) << Shift
) & 0xFF];
478 RtlNumberOfClearBits(
479 _In_ PRTL_BITMAP BitMapHeader
)
482 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
488 _In_ PRTL_BITMAP BitMapHeader
,
489 _In_ BITMAP_INDEX NumberToFind
,
490 _In_ BITMAP_INDEX HintIndex
)
492 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
494 /* Check for valid parameters */
495 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
500 /* Check if the hint is outside the bitmap */
501 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
503 /* Check for trivial case */
504 if (NumberToFind
== 0)
506 /* Return hint rounded down to byte margin */
507 return HintIndex
& ~7;
510 /* First margin is end of bitmap */
511 Margin
= BitMapHeader
->SizeOfBitMap
;
514 /* Start with hint index, length is 0 */
515 CurrentBit
= HintIndex
;
517 /* Loop until something is found or the end is reached */
518 while (CurrentBit
+ NumberToFind
< Margin
)
520 /* Search for the next clear run, by skipping a set run */
521 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
525 /* Get length of the clear bit run */
526 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
530 /* Is this long enough? */
531 if (CurrentLength
>= NumberToFind
)
537 CurrentBit
+= CurrentLength
;
540 /* Did we start at a hint? */
543 /* Retry at the start */
544 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
556 _In_ PRTL_BITMAP BitMapHeader
,
557 _In_ BITMAP_INDEX NumberToFind
,
558 _In_ BITMAP_INDEX HintIndex
)
560 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
562 /* Check for valid parameters */
563 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
568 /* Check if the hint is outside the bitmap */
569 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
571 /* Check for trivial case */
572 if (NumberToFind
== 0)
574 /* Return hint rounded down to byte margin */
575 return HintIndex
& ~7;
578 /* First margin is end of bitmap */
579 Margin
= BitMapHeader
->SizeOfBitMap
;
582 /* Start with hint index, length is 0 */
583 CurrentBit
= HintIndex
;
585 /* Loop until something is found or the end is reached */
586 while (CurrentBit
+ NumberToFind
<= Margin
)
588 /* Search for the next set run, by skipping a clear run */
589 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
593 /* Get length of the set bit run */
594 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
598 /* Is this long enough? */
599 if (CurrentLength
>= NumberToFind
)
605 CurrentBit
+= CurrentLength
;
608 /* Did we start at a hint? */
611 /* Retry at the start */
612 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
623 RtlFindClearBitsAndSet(
624 _In_ PRTL_BITMAP BitMapHeader
,
625 _In_ BITMAP_INDEX NumberToFind
,
626 _In_ BITMAP_INDEX HintIndex
)
628 BITMAP_INDEX Position
;
630 /* Try to find clear bits */
631 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
633 /* Did we get something? */
634 if (Position
!= MAXINDEX
)
636 /* Yes, set the bits */
637 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
640 /* Return what we found */
646 RtlFindSetBitsAndClear(
647 _In_ PRTL_BITMAP BitMapHeader
,
648 _In_ BITMAP_INDEX NumberToFind
,
649 _In_ BITMAP_INDEX HintIndex
)
651 BITMAP_INDEX Position
;
653 /* Try to find set bits */
654 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
656 /* Did we get something? */
657 if (Position
!= MAXINDEX
)
659 /* Yes, clear the bits */
660 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
663 /* Return what we found */
669 RtlFindNextForwardRunClear(
670 _In_ PRTL_BITMAP BitMapHeader
,
671 _In_ BITMAP_INDEX FromIndex
,
672 _Out_ PBITMAP_INDEX StartingRunIndex
)
676 /* Check for buffer overrun */
677 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
679 *StartingRunIndex
= FromIndex
;
683 /* Assume a set run first, count it's length */
684 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXINDEX
);
685 *StartingRunIndex
= FromIndex
+ Length
;
687 /* Now return the length of the run */
688 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
693 RtlFindNextForwardRunSet(
694 _In_ PRTL_BITMAP BitMapHeader
,
695 _In_ BITMAP_INDEX FromIndex
,
696 _Out_ PBITMAP_INDEX StartingRunIndex
)
700 /* Check for buffer overrun */
701 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
703 *StartingRunIndex
= FromIndex
;
707 /* Assume a clear run first, count it's length */
708 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXINDEX
);
709 *StartingRunIndex
= FromIndex
+ Length
;
711 /* Now return the length of the run */
712 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
717 RtlFindFirstRunClear(
718 _In_ PRTL_BITMAP BitMapHeader
,
719 _Out_ PBITMAP_INDEX StartingIndex
)
721 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
726 RtlFindLastBackwardRunClear(
727 _In_ PRTL_BITMAP BitMapHeader
,
728 _In_ BITMAP_INDEX FromIndex
,
729 _Out_ PBITMAP_INDEX StartingRunIndex
)
731 BITMAP_INDEX Value
, InvValue
, BitPos
;
732 PBITMAP_BUFFER Buffer
;
734 /* Make sure we don't go past the end */
735 FromIndex
= min(FromIndex
, BitMapHeader
->SizeOfBitMap
- 1);
737 /* Calculate positions */
738 Buffer
= BitMapHeader
->Buffer
+ FromIndex
/ _BITCOUNT
;
739 BitPos
= (_BITCOUNT
- 1) - (FromIndex
& (_BITCOUNT
- 1));
741 /* Get the inversed value, clear bits that don't belong to the run */
742 InvValue
= ~(*Buffer
--) << BitPos
>> BitPos
;
744 /* Skip all set ULONGs */
745 while (InvValue
== 0)
747 /* Did we already reach past the first ULONG? */
748 if (Buffer
< BitMapHeader
->Buffer
)
750 /* Yes, nothing found */
754 InvValue
= ~(*Buffer
--);
757 /* We hit a clear bit, check how many set bits are left */
758 BitScanReverse(&BitPos
, InvValue
);
760 /* Calculate last bit position */
761 FromIndex
= (Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
;
763 Value
= ~InvValue
<< ((_BITCOUNT
- 1) - BitPos
) >> ((_BITCOUNT
- 1) - BitPos
);
765 /* Skip all clear ULONGs */
766 while (Value
== 0 && Buffer
>= BitMapHeader
->Buffer
)
773 /* We hit a set bit, check how many clear bits are left */
774 BitScanReverse(&BitPos
, Value
);
776 /* Calculate Starting Index */
777 *StartingRunIndex
= (Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
+ 1;
781 /* We reached the start of the bitmap */
782 *StartingRunIndex
= 0;
785 /* Return length of the run */
786 return FromIndex
- *StartingRunIndex
;
793 _In_ PRTL_BITMAP BitMapHeader
,
794 _In_ PRTL_BITMAP_RUN RunArray
,
795 _In_ ULONG SizeOfRunArray
,
796 _In_ BOOLEAN LocateLongestRuns
)
798 BITMAP_INDEX StartingIndex
, NumberOfBits
, FromIndex
= 0, SmallestRun
= 0;
802 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
805 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
809 /* Nothing more found? Quit looping. */
810 if (NumberOfBits
== 0) break;
812 /* Add another run */
813 RunArray
[Run
].StartingIndex
= StartingIndex
;
814 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
816 /* Update smallest run */
817 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
823 FromIndex
= StartingIndex
+ NumberOfBits
;
826 /* Check if we are finished */
827 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
829 /* Return the number of found runs */
836 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
840 /* Nothing more found? Quit looping. */
841 if (NumberOfBits
== 0) break;
843 /* Check if we have something to update */
844 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
846 /* Update smallest run */
847 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
848 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
851 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
853 /*Is this the new smallest run? */
854 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
856 /* Set it as new smallest run */
863 FromIndex
+= NumberOfBits
;
871 RtlFindLongestRunClear(
872 IN PRTL_BITMAP BitMapHeader
,
873 IN PBITMAP_INDEX StartingIndex
)
875 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
880 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
884 /* Nothing more found? Quit looping. */
885 if (NumberOfBits
== 0) break;
887 /* Was that the longest run? */
888 if (NumberOfBits
> MaxNumberOfBits
)
891 MaxNumberOfBits
= NumberOfBits
;
892 *StartingIndex
= Index
;
896 FromIndex
+= NumberOfBits
;
899 return MaxNumberOfBits
;
904 RtlFindLongestRunSet(
905 IN PRTL_BITMAP BitMapHeader
,
906 IN PBITMAP_INDEX StartingIndex
)
908 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
913 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
917 /* Nothing more found? Quit looping. */
918 if (NumberOfBits
== 0) break;
920 /* Was that the longest run? */
921 if (NumberOfBits
> MaxNumberOfBits
)
924 MaxNumberOfBits
= NumberOfBits
;
925 *StartingIndex
= Index
;
929 FromIndex
+= NumberOfBits
;
932 return MaxNumberOfBits
;