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 /* If we are already at the end, the length of the run is zero */
105 ASSERT(StartingIndex
<= BitMapHeader
->SizeOfBitMap
);
106 if (StartingIndex
>= BitMapHeader
->SizeOfBitMap
)
109 /* Calculate positions */
110 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
111 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
113 /* Calculate the maximum length */
114 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
115 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
117 /* Clear the bits that don't belong to this run */
118 Value
= *Buffer
++ >> BitPos
<< BitPos
;
120 /* Skip all clear ULONGs */
121 while (Value
== 0 && Buffer
< MaxBuffer
)
126 /* Did we reach the end? */
129 /* Return maximum length */
133 /* We hit a set bit, check how many clear bits are left */
134 BitScanForward(&BitPos
, Value
);
136 /* Calculate length up to where we read */
137 Length
= (BITMAP_INDEX
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
138 Length
+= BitPos
- _BITCOUNT
;
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 */
150 RtlpGetLengthOfRunSet(
151 _In_ PRTL_BITMAP BitMapHeader
,
152 _In_ BITMAP_INDEX StartingIndex
,
153 _In_ BITMAP_INDEX MaxLength
)
155 BITMAP_INDEX InvValue
, BitPos
, Length
;
156 PBITMAP_BUFFER Buffer
, MaxBuffer
;
158 /* If we are already at the end, the length of the run is zero */
159 ASSERT(StartingIndex
<= BitMapHeader
->SizeOfBitMap
);
160 if (StartingIndex
>= BitMapHeader
->SizeOfBitMap
)
163 /* Calculate positions */
164 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
165 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
167 /* Calculate the maximum length */
168 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
169 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
171 /* Get the inversed value, clear bits that don't belong to the run */
172 InvValue
= ~(*Buffer
++) >> BitPos
<< BitPos
;
174 /* Skip all set ULONGs */
175 while (InvValue
== 0 && Buffer
< MaxBuffer
)
177 InvValue
= ~(*Buffer
++);
180 /* Did we reach the end? */
183 /* Yes, return maximum */
187 /* We hit a clear bit, check how many set bits are left */
188 BitScanForward(&BitPos
, InvValue
);
190 /* Calculate length up to where we read */
191 Length
= (ULONG
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
192 Length
+= BitPos
- _BITCOUNT
;
194 /* Make sure we don't go past the last bit */
195 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
196 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
198 /* Return the result */
203 /* PUBLIC FUNCTIONS **********************************************************/
205 #ifndef USE_RTL_BITMAP64
208 RtlFindMostSignificantBit(ULONGLONG Value
)
213 if (BitScanReverse64(&Position
, Value
))
215 return (CCHAR
)Position
;
218 if (BitScanReverse(&Position
, Value
>> _BITCOUNT
))
220 return (CCHAR
)(Position
+ _BITCOUNT
);
222 else if (BitScanReverse(&Position
, (ULONG
)Value
))
224 return (CCHAR
)Position
;
232 RtlFindLeastSignificantBit(ULONGLONG Value
)
237 if (BitScanForward64(&Position
, Value
))
239 return (CCHAR
)Position
;
242 if (BitScanForward(&Position
, (ULONG
)Value
))
244 return (CCHAR
)Position
;
246 else if (BitScanForward(&Position
, Value
>> _BITCOUNT
))
248 return (CCHAR
)(Position
+ _BITCOUNT
);
253 #endif /* !USE_RTL_BITMAP64 */
258 _Out_ PRTL_BITMAP BitMapHeader
,
259 _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer
,
260 _In_opt_ ULONG SizeOfBitMap
)
262 /* Setup the bitmap header */
263 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
264 BitMapHeader
->Buffer
= BitMapBuffer
;
270 _In_ PRTL_BITMAP BitMapHeader
)
272 BITMAP_INDEX LengthInUlongs
;
274 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
275 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), 0);
281 _In_ PRTL_BITMAP BitMapHeader
)
283 BITMAP_INDEX LengthInUlongs
;
285 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
286 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), ~0);
292 _In_ PRTL_BITMAP BitMapHeader
,
293 _In_ BITMAP_INDEX BitNumber
)
295 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
296 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] &= ~(1 << (BitNumber
& (_BITCOUNT
- 1)));
302 _In_ PRTL_BITMAP BitMapHeader
,
303 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
305 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
306 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] |= ((BITMAP_INDEX
)1 << (BitNumber
& (_BITCOUNT
- 1)));
312 _In_ PRTL_BITMAP BitMapHeader
,
313 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToClear
) BITMAP_INDEX StartingIndex
,
314 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToClear
)
316 BITMAP_INDEX Bits
, Mask
;
317 PBITMAP_BUFFER Buffer
;
319 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
321 /* Calculate buffer start and first bit index */
322 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
323 Bits
= StartingIndex
& (_BITCOUNT
- 1);
325 /* Are we unaligned? */
328 /* Create an inverse mask by shifting MAXINDEX */
329 Mask
= MAXINDEX
<< Bits
;
331 /* This is what's left in the first ULONG */
332 Bits
= _BITCOUNT
- Bits
;
334 /* Even less bits to clear? */
335 if (NumberToClear
< Bits
)
337 /* Calculate how many bits are left */
338 Bits
-= NumberToClear
;
340 /* Fixup the mask on the high side */
341 Mask
= Mask
<< Bits
>> Bits
;
343 /* Clear bits and return */
351 /* Update buffer and left bits */
353 NumberToClear
-= Bits
;
356 /* Clear all full ULONGs */
357 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
358 Buffer
+= NumberToClear
/ _BITCOUNT
;
360 /* Clear what's left */
361 NumberToClear
&= (_BITCOUNT
- 1);
362 Mask
= MAXINDEX
<< NumberToClear
;
369 _In_ PRTL_BITMAP BitMapHeader
,
370 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToSet
) BITMAP_INDEX StartingIndex
,
371 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToSet
)
373 BITMAP_INDEX Bits
, Mask
;
374 PBITMAP_BUFFER Buffer
;
376 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
378 /* Calculate buffer start and first bit index */
379 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
380 Bits
= StartingIndex
& (_BITCOUNT
- 1);
382 /* Are we unaligned? */
385 /* Create a mask by shifting MAXINDEX */
386 Mask
= MAXINDEX
<< Bits
;
388 /* This is what's left in the first ULONG */
389 Bits
= _BITCOUNT
- Bits
;
391 /* Even less bits to clear? */
392 if (NumberToSet
< Bits
)
394 /* Calculate how many bits are left */
397 /* Fixup the mask on the high side */
398 Mask
= Mask
<< Bits
>> Bits
;
400 /* Set bits and return */
408 /* Update buffer and left bits */
413 /* Set all full ULONGs */
414 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXINDEX
);
415 Buffer
+= NumberToSet
/ _BITCOUNT
;
417 /* Set what's left */
418 NumberToSet
&= (_BITCOUNT
- 1);
419 Mask
= MAXINDEX
<< NumberToSet
;
426 _In_ PRTL_BITMAP BitMapHeader
,
427 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
429 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
430 return (BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] >> (BitNumber
& (_BITCOUNT
- 1))) & 1;
436 _In_ PRTL_BITMAP BitMapHeader
,
437 _In_ BITMAP_INDEX StartingIndex
,
438 _In_ BITMAP_INDEX Length
)
440 /* Verify parameters */
441 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
442 (StartingIndex
+ Length
<= StartingIndex
))
445 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
451 _In_ PRTL_BITMAP BitMapHeader
,
452 _In_ BITMAP_INDEX StartingIndex
,
453 _In_ BITMAP_INDEX Length
)
455 /* Verify parameters */
456 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
457 (StartingIndex
+ Length
<= StartingIndex
))
460 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
466 _In_ PRTL_BITMAP BitMapHeader
)
468 PUCHAR Byte
, MaxByte
;
469 BITMAP_INDEX BitCount
= 0;
472 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
473 MaxByte
= Byte
+ BitMapHeader
->SizeOfBitMap
/ 8;
475 while (Byte
< MaxByte
)
477 BitCount
+= BitCountTable
[*Byte
++];
480 if (BitMapHeader
->SizeOfBitMap
& 7)
482 Shift
= 8 - (BitMapHeader
->SizeOfBitMap
& 7);
483 BitCount
+= BitCountTable
[((*Byte
) << Shift
) & 0xFF];
491 RtlNumberOfClearBits(
492 _In_ PRTL_BITMAP BitMapHeader
)
495 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
501 _In_ PRTL_BITMAP BitMapHeader
,
502 _In_ BITMAP_INDEX NumberToFind
,
503 _In_ BITMAP_INDEX HintIndex
)
505 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
507 /* Check for valid parameters */
508 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
513 /* Check if the hint is outside the bitmap */
514 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
516 /* Check for trivial case */
517 if (NumberToFind
== 0)
519 /* Return hint rounded down to byte margin */
520 return HintIndex
& ~7;
523 /* First margin is end of bitmap */
524 Margin
= BitMapHeader
->SizeOfBitMap
;
527 /* Start with hint index, length is 0 */
528 CurrentBit
= HintIndex
;
530 /* Loop until something is found or the end is reached */
531 while (CurrentBit
+ NumberToFind
< Margin
)
533 /* Search for the next clear run, by skipping a set run */
534 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
538 /* Get length of the clear bit run */
539 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
543 /* Is this long enough? */
544 if (CurrentLength
>= NumberToFind
)
550 CurrentBit
+= CurrentLength
;
553 /* Did we start at a hint? */
556 /* Retry at the start */
557 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
569 _In_ PRTL_BITMAP BitMapHeader
,
570 _In_ BITMAP_INDEX NumberToFind
,
571 _In_ BITMAP_INDEX HintIndex
)
573 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
575 /* Check for valid parameters */
576 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
581 /* Check if the hint is outside the bitmap */
582 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
584 /* Check for trivial case */
585 if (NumberToFind
== 0)
587 /* Return hint rounded down to byte margin */
588 return HintIndex
& ~7;
591 /* First margin is end of bitmap */
592 Margin
= BitMapHeader
->SizeOfBitMap
;
595 /* Start with hint index, length is 0 */
596 CurrentBit
= HintIndex
;
598 /* Loop until something is found or the end is reached */
599 while (CurrentBit
+ NumberToFind
<= Margin
)
601 /* Search for the next set run, by skipping a clear run */
602 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
606 /* Get length of the set bit run */
607 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
611 /* Is this long enough? */
612 if (CurrentLength
>= NumberToFind
)
618 CurrentBit
+= CurrentLength
;
621 /* Did we start at a hint? */
624 /* Retry at the start */
625 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
636 RtlFindClearBitsAndSet(
637 _In_ PRTL_BITMAP BitMapHeader
,
638 _In_ BITMAP_INDEX NumberToFind
,
639 _In_ BITMAP_INDEX HintIndex
)
641 BITMAP_INDEX Position
;
643 /* Try to find clear bits */
644 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
646 /* Did we get something? */
647 if (Position
!= MAXINDEX
)
649 /* Yes, set the bits */
650 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
653 /* Return what we found */
659 RtlFindSetBitsAndClear(
660 _In_ PRTL_BITMAP BitMapHeader
,
661 _In_ BITMAP_INDEX NumberToFind
,
662 _In_ BITMAP_INDEX HintIndex
)
664 BITMAP_INDEX Position
;
666 /* Try to find set bits */
667 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
669 /* Did we get something? */
670 if (Position
!= MAXINDEX
)
672 /* Yes, clear the bits */
673 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
676 /* Return what we found */
682 RtlFindNextForwardRunClear(
683 _In_ PRTL_BITMAP BitMapHeader
,
684 _In_ BITMAP_INDEX FromIndex
,
685 _Out_ PBITMAP_INDEX StartingRunIndex
)
689 /* Check for buffer overrun */
690 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
692 *StartingRunIndex
= FromIndex
;
696 /* Assume a set run first, count it's length */
697 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXINDEX
);
698 *StartingRunIndex
= FromIndex
+ Length
;
700 /* Now return the length of the run */
701 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
706 RtlFindNextForwardRunSet(
707 _In_ PRTL_BITMAP BitMapHeader
,
708 _In_ BITMAP_INDEX FromIndex
,
709 _Out_ PBITMAP_INDEX StartingRunIndex
)
713 /* Check for buffer overrun */
714 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
716 *StartingRunIndex
= FromIndex
;
720 /* Assume a clear run first, count it's length */
721 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXINDEX
);
722 *StartingRunIndex
= FromIndex
+ Length
;
724 /* Now return the length of the run */
725 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
730 RtlFindFirstRunClear(
731 _In_ PRTL_BITMAP BitMapHeader
,
732 _Out_ PBITMAP_INDEX StartingIndex
)
734 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
739 RtlFindLastBackwardRunClear(
740 _In_ PRTL_BITMAP BitMapHeader
,
741 _In_ BITMAP_INDEX FromIndex
,
742 _Out_ PBITMAP_INDEX StartingRunIndex
)
744 BITMAP_INDEX Value
, InvValue
, BitPos
;
745 PBITMAP_BUFFER Buffer
;
747 /* Make sure we don't go past the end */
748 FromIndex
= min(FromIndex
, BitMapHeader
->SizeOfBitMap
- 1);
750 /* Calculate positions */
751 Buffer
= BitMapHeader
->Buffer
+ FromIndex
/ _BITCOUNT
;
752 BitPos
= (_BITCOUNT
- 1) - (FromIndex
& (_BITCOUNT
- 1));
754 /* Get the inversed value, clear bits that don't belong to the run */
755 InvValue
= ~(*Buffer
--) << BitPos
>> BitPos
;
757 /* Skip all set ULONGs */
758 while (InvValue
== 0)
760 /* Did we already reach past the first ULONG? */
761 if (Buffer
< BitMapHeader
->Buffer
)
763 /* Yes, nothing found */
767 InvValue
= ~(*Buffer
--);
770 /* We hit a clear bit, check how many set bits are left */
771 BitScanReverse(&BitPos
, InvValue
);
773 /* Calculate last bit position */
774 FromIndex
= (Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
;
776 Value
= ~InvValue
<< ((_BITCOUNT
- 1) - BitPos
) >> ((_BITCOUNT
- 1) - BitPos
);
778 /* Skip all clear ULONGs */
779 while (Value
== 0 && Buffer
>= BitMapHeader
->Buffer
)
786 /* We hit a set bit, check how many clear bits are left */
787 BitScanReverse(&BitPos
, Value
);
789 /* Calculate Starting Index */
790 *StartingRunIndex
= (Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
+ 1;
794 /* We reached the start of the bitmap */
795 *StartingRunIndex
= 0;
798 /* Return length of the run */
799 return FromIndex
- *StartingRunIndex
;
806 _In_ PRTL_BITMAP BitMapHeader
,
807 _In_ PRTL_BITMAP_RUN RunArray
,
808 _In_ ULONG SizeOfRunArray
,
809 _In_ BOOLEAN LocateLongestRuns
)
811 BITMAP_INDEX StartingIndex
, NumberOfBits
, FromIndex
= 0, SmallestRun
= 0;
815 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
818 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
822 /* Nothing more found? Quit looping. */
823 if (NumberOfBits
== 0) break;
825 /* Add another run */
826 RunArray
[Run
].StartingIndex
= StartingIndex
;
827 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
829 /* Update smallest run */
830 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
836 FromIndex
= StartingIndex
+ NumberOfBits
;
839 /* Check if we are finished */
840 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
842 /* Return the number of found runs */
849 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
853 /* Nothing more found? Quit looping. */
854 if (NumberOfBits
== 0) break;
856 /* Check if we have something to update */
857 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
859 /* Update smallest run */
860 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
861 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
864 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
866 /*Is this the new smallest run? */
867 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
869 /* Set it as new smallest run */
876 FromIndex
+= NumberOfBits
;
884 RtlFindLongestRunClear(
885 IN PRTL_BITMAP BitMapHeader
,
886 IN PBITMAP_INDEX StartingIndex
)
888 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
893 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
897 /* Nothing more found? Quit looping. */
898 if (NumberOfBits
== 0) break;
900 /* Was that the longest run? */
901 if (NumberOfBits
> MaxNumberOfBits
)
904 MaxNumberOfBits
= NumberOfBits
;
905 *StartingIndex
= Index
;
909 FromIndex
+= NumberOfBits
;
912 return MaxNumberOfBits
;
917 RtlFindLongestRunSet(
918 IN PRTL_BITMAP BitMapHeader
,
919 IN PBITMAP_INDEX StartingIndex
)
921 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
926 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
930 /* Nothing more found? Quit looping. */
931 if (NumberOfBits
== 0) break;
933 /* Was that the longest run? */
934 if (NumberOfBits
> MaxNumberOfBits
)
937 MaxNumberOfBits
= NumberOfBits
;
938 *StartingIndex
= Index
;
942 FromIndex
+= NumberOfBits
;
945 return MaxNumberOfBits
;