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)
34 #define BitScanReverse(Index, Mask) \
35 do { unsigned long tmp; BitScanReverse64(&tmp, Mask); *Index = tmp; } while (0)
36 #define RtlFillMemoryUlong RtlFillMemoryUlonglong
38 #define RtlInitializeBitMap RtlInitializeBitMap64
39 #define RtlClearAllBits RtlClearAllBits64
40 #define RtlSetAllBits RtlSetAllBits64
41 #define RtlClearBit RtlClearBit64
42 #define RtlSetBit RtlSetBit64
43 #define RtlClearBits RtlClearBits64
44 #define RtlSetBits RtlSetBits64
45 #define RtlTestBit RtlTestBit64
46 #define RtlAreBitsClear RtlAreBitsClear64
47 #define RtlAreBitsSet RtlAreBitsSet64
48 #define RtlNumberOfSetBits RtlNumberOfSetBits64
49 #define RtlNumberOfClearBits RtlNumberOfClearBits64
50 #define RtlFindClearBits RtlFindClearBits64
51 #define RtlFindSetBits RtlFindSetBits64
52 #define RtlFindClearBitsAndSet RtlFindClearBitsAndSet64
53 #define RtlFindSetBitsAndClear RtlFindSetBitsAndClear64
54 #define RtlFindNextForwardRunClear RtlFindNextForwardRunClear64
55 #define RtlFindNextForwardRunSet RtlFindNextForwardRunSet64
56 #define RtlFindFirstRunClear RtlFindFirstRunClear64
57 #define RtlFindLastBackwardRunClear RtlFindLastBackwardRunClear64
58 #define RtlFindClearRuns RtlFindClearRuns64
59 #define RtlFindLongestRunClear RtlFindLongestRunClear64
60 #define RtlFindLongestRunSet RtlFindLongestRunSet64
63 #define MAXINDEX 0xFFFFFFFF
64 typedef ULONG BITMAP_INDEX
, *PBITMAP_INDEX
;
65 typedef ULONG BITMAP_BUFFER
, *PBITMAP_BUFFER
;
68 /* DATA *********************************************************************/
70 /* Number of set bits per byte value */
75 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
76 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
77 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
78 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
79 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
80 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
81 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
82 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
83 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
84 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
85 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
86 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
87 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
88 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
89 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
90 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
91 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
95 /* PRIVATE FUNCTIONS ********************************************************/
99 RtlpGetLengthOfRunClear(
100 _In_ PRTL_BITMAP BitMapHeader
,
101 _In_ BITMAP_INDEX StartingIndex
,
102 _In_ BITMAP_INDEX MaxLength
)
104 BITMAP_INDEX Value
, BitPos
, Length
;
105 PBITMAP_BUFFER Buffer
, MaxBuffer
;
107 /* If we are already at the end, the length of the run is zero */
108 ASSERT(StartingIndex
<= BitMapHeader
->SizeOfBitMap
);
109 if (StartingIndex
>= BitMapHeader
->SizeOfBitMap
)
112 /* Calculate positions */
113 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
114 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
116 /* Calculate the maximum length */
117 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
118 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
120 /* Clear the bits that don't belong to this run */
121 Value
= *Buffer
++ >> BitPos
<< BitPos
;
123 /* Skip all clear ULONGs */
124 while (Value
== 0 && Buffer
< MaxBuffer
)
129 /* Did we reach the end? */
132 /* Return maximum length */
136 /* We hit a set bit, check how many clear bits are left */
137 BitScanForward(&BitPos
, Value
);
139 /* Calculate length up to where we read */
140 Length
= (BITMAP_INDEX
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
141 Length
+= BitPos
- _BITCOUNT
;
143 /* Make sure we don't go past the last bit */
144 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
145 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
147 /* Return the result */
153 RtlpGetLengthOfRunSet(
154 _In_ PRTL_BITMAP BitMapHeader
,
155 _In_ BITMAP_INDEX StartingIndex
,
156 _In_ BITMAP_INDEX MaxLength
)
158 BITMAP_INDEX InvValue
, BitPos
, Length
;
159 PBITMAP_BUFFER Buffer
, MaxBuffer
;
161 /* If we are already at the end, the length of the run is zero */
162 ASSERT(StartingIndex
<= BitMapHeader
->SizeOfBitMap
);
163 if (StartingIndex
>= BitMapHeader
->SizeOfBitMap
)
166 /* Calculate positions */
167 Buffer
= BitMapHeader
->Buffer
+ StartingIndex
/ _BITCOUNT
;
168 BitPos
= StartingIndex
& (_BITCOUNT
- 1);
170 /* Calculate the maximum length */
171 MaxLength
= min(MaxLength
, BitMapHeader
->SizeOfBitMap
- StartingIndex
);
172 MaxBuffer
= Buffer
+ (BitPos
+ MaxLength
+ _BITCOUNT
- 1) / _BITCOUNT
;
174 /* Get the inversed value, clear bits that don't belong to the run */
175 InvValue
= ~(*Buffer
++) >> BitPos
<< BitPos
;
177 /* Skip all set ULONGs */
178 while (InvValue
== 0 && Buffer
< MaxBuffer
)
180 InvValue
= ~(*Buffer
++);
183 /* Did we reach the end? */
186 /* Yes, return maximum */
190 /* We hit a clear bit, check how many set bits are left */
191 BitScanForward(&BitPos
, InvValue
);
193 /* Calculate length up to where we read */
194 Length
= (ULONG
)(Buffer
- BitMapHeader
->Buffer
) * _BITCOUNT
- StartingIndex
;
195 Length
+= BitPos
- _BITCOUNT
;
197 /* Make sure we don't go past the last bit */
198 if (Length
> BitMapHeader
->SizeOfBitMap
- StartingIndex
)
199 Length
= BitMapHeader
->SizeOfBitMap
- StartingIndex
;
201 /* Return the result */
206 /* PUBLIC FUNCTIONS **********************************************************/
208 #ifndef USE_RTL_BITMAP64
211 RtlFindMostSignificantBit(ULONGLONG Value
)
216 if (BitScanReverse64(&Position
, Value
))
218 return (CCHAR
)Position
;
221 if (BitScanReverse(&Position
, Value
>> _BITCOUNT
))
223 return (CCHAR
)(Position
+ _BITCOUNT
);
225 else if (BitScanReverse(&Position
, (ULONG
)Value
))
227 return (CCHAR
)Position
;
235 RtlFindLeastSignificantBit(ULONGLONG Value
)
240 if (BitScanForward64(&Position
, Value
))
242 return (CCHAR
)Position
;
245 if (BitScanForward(&Position
, (ULONG
)Value
))
247 return (CCHAR
)Position
;
249 else if (BitScanForward(&Position
, Value
>> _BITCOUNT
))
251 return (CCHAR
)(Position
+ _BITCOUNT
);
256 #endif /* !USE_RTL_BITMAP64 */
261 _Out_ PRTL_BITMAP BitMapHeader
,
262 _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer
,
263 _In_opt_ ULONG SizeOfBitMap
)
265 /* Setup the bitmap header */
266 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
267 BitMapHeader
->Buffer
= BitMapBuffer
;
273 _In_ PRTL_BITMAP BitMapHeader
)
275 BITMAP_INDEX LengthInUlongs
;
277 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
278 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), 0);
284 _In_ PRTL_BITMAP BitMapHeader
)
286 BITMAP_INDEX LengthInUlongs
;
288 LengthInUlongs
= (BitMapHeader
->SizeOfBitMap
+ _BITCOUNT
- 1) / _BITCOUNT
;
289 RtlFillMemoryUlong(BitMapHeader
->Buffer
, LengthInUlongs
* sizeof(BITMAP_INDEX
), ~0);
295 _In_ PRTL_BITMAP BitMapHeader
,
296 _In_ BITMAP_INDEX BitNumber
)
298 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
299 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] &= ~(1 << (BitNumber
& (_BITCOUNT
- 1)));
305 _In_ PRTL_BITMAP BitMapHeader
,
306 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
308 ASSERT(BitNumber
<= BitMapHeader
->SizeOfBitMap
);
309 BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] |= ((BITMAP_INDEX
)1 << (BitNumber
& (_BITCOUNT
- 1)));
315 _In_ PRTL_BITMAP BitMapHeader
,
316 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToClear
) BITMAP_INDEX StartingIndex
,
317 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToClear
)
319 BITMAP_INDEX Bits
, Mask
;
320 PBITMAP_BUFFER Buffer
;
322 ASSERT(StartingIndex
+ NumberToClear
<= BitMapHeader
->SizeOfBitMap
);
324 /* Calculate buffer start and first bit index */
325 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
326 Bits
= StartingIndex
& (_BITCOUNT
- 1);
328 /* Are we unaligned? */
331 /* Create an inverse mask by shifting MAXINDEX */
332 Mask
= MAXINDEX
<< Bits
;
334 /* This is what's left in the first ULONG */
335 Bits
= _BITCOUNT
- Bits
;
337 /* Even less bits to clear? */
338 if (NumberToClear
< Bits
)
340 /* Calculate how many bits are left */
341 Bits
-= NumberToClear
;
343 /* Fixup the mask on the high side */
344 Mask
= Mask
<< Bits
>> Bits
;
346 /* Clear bits and return */
354 /* Update buffer and left bits */
356 NumberToClear
-= Bits
;
359 /* Clear all full ULONGs */
360 RtlFillMemoryUlong(Buffer
, NumberToClear
>> 3, 0);
361 Buffer
+= NumberToClear
/ _BITCOUNT
;
363 /* Clear what's left */
364 NumberToClear
&= (_BITCOUNT
- 1);
365 Mask
= MAXINDEX
<< NumberToClear
;
372 _In_ PRTL_BITMAP BitMapHeader
,
373 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToSet
) BITMAP_INDEX StartingIndex
,
374 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToSet
)
376 BITMAP_INDEX Bits
, Mask
;
377 PBITMAP_BUFFER Buffer
;
379 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
381 /* Calculate buffer start and first bit index */
382 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
383 Bits
= StartingIndex
& (_BITCOUNT
- 1);
385 /* Are we unaligned? */
388 /* Create a mask by shifting MAXINDEX */
389 Mask
= MAXINDEX
<< Bits
;
391 /* This is what's left in the first ULONG */
392 Bits
= _BITCOUNT
- Bits
;
394 /* Even less bits to clear? */
395 if (NumberToSet
< Bits
)
397 /* Calculate how many bits are left */
400 /* Fixup the mask on the high side */
401 Mask
= Mask
<< Bits
>> Bits
;
403 /* Set bits and return */
411 /* Update buffer and left bits */
416 /* Set all full ULONGs */
417 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXINDEX
);
418 Buffer
+= NumberToSet
/ _BITCOUNT
;
420 /* Set what's left */
421 NumberToSet
&= (_BITCOUNT
- 1);
422 Mask
= MAXINDEX
<< NumberToSet
;
429 _In_ PRTL_BITMAP BitMapHeader
,
430 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
432 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
433 return (BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] >> (BitNumber
& (_BITCOUNT
- 1))) & 1;
439 _In_ PRTL_BITMAP BitMapHeader
,
440 _In_ BITMAP_INDEX StartingIndex
,
441 _In_ BITMAP_INDEX Length
)
443 /* Verify parameters */
444 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
445 (StartingIndex
+ Length
<= StartingIndex
))
448 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
454 _In_ PRTL_BITMAP BitMapHeader
,
455 _In_ BITMAP_INDEX StartingIndex
,
456 _In_ BITMAP_INDEX Length
)
458 /* Verify parameters */
459 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
460 (StartingIndex
+ Length
<= StartingIndex
))
463 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
469 _In_ PRTL_BITMAP BitMapHeader
)
471 PUCHAR Byte
, MaxByte
;
472 BITMAP_INDEX BitCount
= 0;
475 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
476 MaxByte
= Byte
+ BitMapHeader
->SizeOfBitMap
/ 8;
478 while (Byte
< MaxByte
)
480 BitCount
+= BitCountTable
[*Byte
++];
483 if (BitMapHeader
->SizeOfBitMap
& 7)
485 Shift
= 8 - (BitMapHeader
->SizeOfBitMap
& 7);
486 BitCount
+= BitCountTable
[((*Byte
) << Shift
) & 0xFF];
494 RtlNumberOfClearBits(
495 _In_ PRTL_BITMAP BitMapHeader
)
498 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
504 _In_ PRTL_BITMAP BitMapHeader
,
505 _In_ BITMAP_INDEX NumberToFind
,
506 _In_ BITMAP_INDEX HintIndex
)
508 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
510 /* Check for valid parameters */
511 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
516 /* Check if the hint is outside the bitmap */
517 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
519 /* Check for trivial case */
520 if (NumberToFind
== 0)
522 /* Return hint rounded down to byte margin */
523 return HintIndex
& ~7;
526 /* First margin is end of bitmap */
527 Margin
= BitMapHeader
->SizeOfBitMap
;
530 /* Start with hint index, length is 0 */
531 CurrentBit
= HintIndex
;
533 /* Loop until something is found or the end is reached */
534 while (CurrentBit
+ NumberToFind
< Margin
)
536 /* Search for the next clear run, by skipping a set run */
537 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
541 /* Get length of the clear bit run */
542 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
546 /* Is this long enough? */
547 if (CurrentLength
>= NumberToFind
)
553 CurrentBit
+= CurrentLength
;
556 /* Did we start at a hint? */
559 /* Retry at the start */
560 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
572 _In_ PRTL_BITMAP BitMapHeader
,
573 _In_ BITMAP_INDEX NumberToFind
,
574 _In_ BITMAP_INDEX HintIndex
)
576 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
578 /* Check for valid parameters */
579 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
584 /* Check if the hint is outside the bitmap */
585 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
587 /* Check for trivial case */
588 if (NumberToFind
== 0)
590 /* Return hint rounded down to byte margin */
591 return HintIndex
& ~7;
594 /* First margin is end of bitmap */
595 Margin
= BitMapHeader
->SizeOfBitMap
;
598 /* Start with hint index, length is 0 */
599 CurrentBit
= HintIndex
;
601 /* Loop until something is found or the end is reached */
602 while (CurrentBit
+ NumberToFind
<= Margin
)
604 /* Search for the next set run, by skipping a clear run */
605 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
609 /* Get length of the set bit run */
610 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
614 /* Is this long enough? */
615 if (CurrentLength
>= NumberToFind
)
621 CurrentBit
+= CurrentLength
;
624 /* Did we start at a hint? */
627 /* Retry at the start */
628 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
639 RtlFindClearBitsAndSet(
640 _In_ PRTL_BITMAP BitMapHeader
,
641 _In_ BITMAP_INDEX NumberToFind
,
642 _In_ BITMAP_INDEX HintIndex
)
644 BITMAP_INDEX Position
;
646 /* Try to find clear bits */
647 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
649 /* Did we get something? */
650 if (Position
!= MAXINDEX
)
652 /* Yes, set the bits */
653 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
656 /* Return what we found */
662 RtlFindSetBitsAndClear(
663 _In_ PRTL_BITMAP BitMapHeader
,
664 _In_ BITMAP_INDEX NumberToFind
,
665 _In_ BITMAP_INDEX HintIndex
)
667 BITMAP_INDEX Position
;
669 /* Try to find set bits */
670 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
672 /* Did we get something? */
673 if (Position
!= MAXINDEX
)
675 /* Yes, clear the bits */
676 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
679 /* Return what we found */
685 RtlFindNextForwardRunClear(
686 _In_ PRTL_BITMAP BitMapHeader
,
687 _In_ BITMAP_INDEX FromIndex
,
688 _Out_ PBITMAP_INDEX StartingRunIndex
)
692 /* Check for buffer overrun */
693 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
695 *StartingRunIndex
= FromIndex
;
699 /* Assume a set run first, count it's length */
700 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXINDEX
);
701 *StartingRunIndex
= FromIndex
+ Length
;
703 /* Now return the length of the run */
704 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
709 RtlFindNextForwardRunSet(
710 _In_ PRTL_BITMAP BitMapHeader
,
711 _In_ BITMAP_INDEX FromIndex
,
712 _Out_ PBITMAP_INDEX StartingRunIndex
)
716 /* Check for buffer overrun */
717 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
719 *StartingRunIndex
= FromIndex
;
723 /* Assume a clear run first, count it's length */
724 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXINDEX
);
725 *StartingRunIndex
= FromIndex
+ Length
;
727 /* Now return the length of the run */
728 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
733 RtlFindFirstRunClear(
734 _In_ PRTL_BITMAP BitMapHeader
,
735 _Out_ PBITMAP_INDEX StartingIndex
)
737 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
742 RtlFindLastBackwardRunClear(
743 _In_ PRTL_BITMAP BitMapHeader
,
744 _In_ BITMAP_INDEX FromIndex
,
745 _Out_ PBITMAP_INDEX StartingRunIndex
)
747 BITMAP_INDEX Value
, InvValue
, BitPos
;
748 PBITMAP_BUFFER Buffer
;
750 /* Make sure we don't go past the end */
751 FromIndex
= min(FromIndex
, BitMapHeader
->SizeOfBitMap
- 1);
753 /* Calculate positions */
754 Buffer
= BitMapHeader
->Buffer
+ FromIndex
/ _BITCOUNT
;
755 BitPos
= (_BITCOUNT
- 1) - (FromIndex
& (_BITCOUNT
- 1));
757 /* Get the inversed value, clear bits that don't belong to the run */
758 InvValue
= ~(*Buffer
--) << BitPos
>> BitPos
;
760 /* Skip all set ULONGs */
761 while (InvValue
== 0)
763 /* Did we already reach past the first ULONG? */
764 if (Buffer
< BitMapHeader
->Buffer
)
766 /* Yes, nothing found */
770 InvValue
= ~(*Buffer
--);
773 /* We hit a clear bit, check how many set bits are left */
774 BitScanReverse(&BitPos
, InvValue
);
776 /* Calculate last bit position */
777 FromIndex
= (BITMAP_INDEX
)((Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
);
779 Value
= ~InvValue
<< ((_BITCOUNT
- 1) - BitPos
) >> ((_BITCOUNT
- 1) - BitPos
);
781 /* Skip all clear ULONGs */
782 while (Value
== 0 && Buffer
>= BitMapHeader
->Buffer
)
789 /* We hit a set bit, check how many clear bits are left */
790 BitScanReverse(&BitPos
, Value
);
792 /* Calculate Starting Index */
793 *StartingRunIndex
= (BITMAP_INDEX
)((Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
+ 1);
797 /* We reached the start of the bitmap */
798 *StartingRunIndex
= 0;
801 /* Return length of the run */
802 return (FromIndex
- *StartingRunIndex
);
809 _In_ PRTL_BITMAP BitMapHeader
,
810 _In_ PRTL_BITMAP_RUN RunArray
,
811 _In_ ULONG SizeOfRunArray
,
812 _In_ BOOLEAN LocateLongestRuns
)
814 BITMAP_INDEX StartingIndex
, NumberOfBits
, FromIndex
= 0, SmallestRun
= 0;
818 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
821 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
825 /* Nothing more found? Quit looping. */
826 if (NumberOfBits
== 0) break;
828 /* Add another run */
829 RunArray
[Run
].StartingIndex
= StartingIndex
;
830 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
832 /* Update smallest run */
833 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
839 FromIndex
= StartingIndex
+ NumberOfBits
;
842 /* Check if we are finished */
843 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
845 /* Return the number of found runs */
852 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
856 /* Nothing more found? Quit looping. */
857 if (NumberOfBits
== 0) break;
859 /* Check if we have something to update */
860 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
862 /* Update smallest run */
863 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
864 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
867 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
869 /*Is this the new smallest run? */
870 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
872 /* Set it as new smallest run */
879 FromIndex
+= NumberOfBits
;
887 RtlFindLongestRunClear(
888 IN PRTL_BITMAP BitMapHeader
,
889 IN PBITMAP_INDEX StartingIndex
)
891 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
896 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
900 /* Nothing more found? Quit looping. */
901 if (NumberOfBits
== 0) break;
903 /* Was that the longest run? */
904 if (NumberOfBits
> MaxNumberOfBits
)
907 MaxNumberOfBits
= NumberOfBits
;
908 *StartingIndex
= Index
;
912 FromIndex
+= NumberOfBits
;
915 return MaxNumberOfBits
;
920 RtlFindLongestRunSet(
921 IN PRTL_BITMAP BitMapHeader
,
922 IN PBITMAP_INDEX StartingIndex
)
924 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
929 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
933 /* Nothing more found? Quit looping. */
934 if (NumberOfBits
== 0) break;
936 /* Was that the longest run? */
937 if (NumberOfBits
> MaxNumberOfBits
)
940 MaxNumberOfBits
= NumberOfBits
;
941 *StartingIndex
= Index
;
945 FromIndex
+= NumberOfBits
;
948 return MaxNumberOfBits
;