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 if (NumberToClear
!= 0)
367 Mask
= MAXINDEX
<< NumberToClear
;
375 _In_ PRTL_BITMAP BitMapHeader
,
376 _In_range_(0, BitMapHeader
->SizeOfBitMap
- NumberToSet
) BITMAP_INDEX StartingIndex
,
377 _In_range_(0, BitMapHeader
->SizeOfBitMap
- StartingIndex
) BITMAP_INDEX NumberToSet
)
379 BITMAP_INDEX Bits
, Mask
;
380 PBITMAP_BUFFER Buffer
;
382 ASSERT(StartingIndex
+ NumberToSet
<= BitMapHeader
->SizeOfBitMap
);
384 /* Calculate buffer start and first bit index */
385 Buffer
= &BitMapHeader
->Buffer
[StartingIndex
/ _BITCOUNT
];
386 Bits
= StartingIndex
& (_BITCOUNT
- 1);
388 /* Are we unaligned? */
391 /* Create a mask by shifting MAXINDEX */
392 Mask
= MAXINDEX
<< Bits
;
394 /* This is what's left in the first ULONG */
395 Bits
= _BITCOUNT
- Bits
;
397 /* Even less bits to clear? */
398 if (NumberToSet
< Bits
)
400 /* Calculate how many bits are left */
403 /* Fixup the mask on the high side */
404 Mask
= Mask
<< Bits
>> Bits
;
406 /* Set bits and return */
414 /* Update buffer and left bits */
419 /* Set all full ULONGs */
420 RtlFillMemoryUlong(Buffer
, NumberToSet
>> 3, MAXINDEX
);
421 Buffer
+= NumberToSet
/ _BITCOUNT
;
423 /* Set what's left */
424 NumberToSet
&= (_BITCOUNT
- 1);
425 if (NumberToSet
!= 0)
427 Mask
= MAXINDEX
<< NumberToSet
;
435 _In_ PRTL_BITMAP BitMapHeader
,
436 _In_range_(<, BitMapHeader
->SizeOfBitMap
) BITMAP_INDEX BitNumber
)
438 ASSERT(BitNumber
< BitMapHeader
->SizeOfBitMap
);
439 return (BitMapHeader
->Buffer
[BitNumber
/ _BITCOUNT
] >> (BitNumber
& (_BITCOUNT
- 1))) & 1;
445 _In_ PRTL_BITMAP BitMapHeader
,
446 _In_ BITMAP_INDEX StartingIndex
,
447 _In_ BITMAP_INDEX Length
)
449 /* Verify parameters */
450 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
451 (StartingIndex
+ Length
<= StartingIndex
))
454 return RtlpGetLengthOfRunClear(BitMapHeader
, StartingIndex
, Length
) >= Length
;
460 _In_ PRTL_BITMAP BitMapHeader
,
461 _In_ BITMAP_INDEX StartingIndex
,
462 _In_ BITMAP_INDEX Length
)
464 /* Verify parameters */
465 if ((StartingIndex
+ Length
> BitMapHeader
->SizeOfBitMap
) ||
466 (StartingIndex
+ Length
<= StartingIndex
))
469 return RtlpGetLengthOfRunSet(BitMapHeader
, StartingIndex
, Length
) >= Length
;
475 _In_ PRTL_BITMAP BitMapHeader
)
477 PUCHAR Byte
, MaxByte
;
478 BITMAP_INDEX BitCount
= 0;
481 Byte
= (PUCHAR
)BitMapHeader
->Buffer
;
482 MaxByte
= Byte
+ BitMapHeader
->SizeOfBitMap
/ 8;
484 while (Byte
< MaxByte
)
486 BitCount
+= BitCountTable
[*Byte
++];
489 if (BitMapHeader
->SizeOfBitMap
& 7)
491 Shift
= 8 - (BitMapHeader
->SizeOfBitMap
& 7);
492 BitCount
+= BitCountTable
[((*Byte
) << Shift
) & 0xFF];
500 RtlNumberOfClearBits(
501 _In_ PRTL_BITMAP BitMapHeader
)
504 return BitMapHeader
->SizeOfBitMap
- RtlNumberOfSetBits(BitMapHeader
);
510 _In_ PRTL_BITMAP BitMapHeader
,
511 _In_ BITMAP_INDEX NumberToFind
,
512 _In_ BITMAP_INDEX HintIndex
)
514 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
516 /* Check for valid parameters */
517 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
522 /* Check if the hint is outside the bitmap */
523 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
525 /* Check for trivial case */
526 if (NumberToFind
== 0)
528 /* Return hint rounded down to byte margin */
529 return HintIndex
& ~7;
532 /* First margin is end of bitmap */
533 Margin
= BitMapHeader
->SizeOfBitMap
;
536 /* Start with hint index, length is 0 */
537 CurrentBit
= HintIndex
;
539 /* Loop until something is found or the end is reached */
540 while (CurrentBit
+ NumberToFind
< Margin
)
542 /* Search for the next clear run, by skipping a set run */
543 CurrentBit
+= RtlpGetLengthOfRunSet(BitMapHeader
,
547 /* Get length of the clear bit run */
548 CurrentLength
= RtlpGetLengthOfRunClear(BitMapHeader
,
552 /* Is this long enough? */
553 if (CurrentLength
>= NumberToFind
)
559 CurrentBit
+= CurrentLength
;
562 /* Did we start at a hint? */
565 /* Retry at the start */
566 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
578 _In_ PRTL_BITMAP BitMapHeader
,
579 _In_ BITMAP_INDEX NumberToFind
,
580 _In_ BITMAP_INDEX HintIndex
)
582 BITMAP_INDEX CurrentBit
, Margin
, CurrentLength
;
584 /* Check for valid parameters */
585 if (!BitMapHeader
|| NumberToFind
> BitMapHeader
->SizeOfBitMap
)
590 /* Check if the hint is outside the bitmap */
591 if (HintIndex
>= BitMapHeader
->SizeOfBitMap
) HintIndex
= 0;
593 /* Check for trivial case */
594 if (NumberToFind
== 0)
596 /* Return hint rounded down to byte margin */
597 return HintIndex
& ~7;
600 /* First margin is end of bitmap */
601 Margin
= BitMapHeader
->SizeOfBitMap
;
604 /* Start with hint index, length is 0 */
605 CurrentBit
= HintIndex
;
607 /* Loop until something is found or the end is reached */
608 while (CurrentBit
+ NumberToFind
<= Margin
)
610 /* Search for the next set run, by skipping a clear run */
611 CurrentBit
+= RtlpGetLengthOfRunClear(BitMapHeader
,
615 /* Get length of the set bit run */
616 CurrentLength
= RtlpGetLengthOfRunSet(BitMapHeader
,
620 /* Is this long enough? */
621 if (CurrentLength
>= NumberToFind
)
627 CurrentBit
+= CurrentLength
;
630 /* Did we start at a hint? */
633 /* Retry at the start */
634 Margin
= min(HintIndex
+ NumberToFind
, BitMapHeader
->SizeOfBitMap
);
645 RtlFindClearBitsAndSet(
646 _In_ PRTL_BITMAP BitMapHeader
,
647 _In_ BITMAP_INDEX NumberToFind
,
648 _In_ BITMAP_INDEX HintIndex
)
650 BITMAP_INDEX Position
;
652 /* Try to find clear bits */
653 Position
= RtlFindClearBits(BitMapHeader
, NumberToFind
, HintIndex
);
655 /* Did we get something? */
656 if (Position
!= MAXINDEX
)
658 /* Yes, set the bits */
659 RtlSetBits(BitMapHeader
, Position
, NumberToFind
);
662 /* Return what we found */
668 RtlFindSetBitsAndClear(
669 _In_ PRTL_BITMAP BitMapHeader
,
670 _In_ BITMAP_INDEX NumberToFind
,
671 _In_ BITMAP_INDEX HintIndex
)
673 BITMAP_INDEX Position
;
675 /* Try to find set bits */
676 Position
= RtlFindSetBits(BitMapHeader
, NumberToFind
, HintIndex
);
678 /* Did we get something? */
679 if (Position
!= MAXINDEX
)
681 /* Yes, clear the bits */
682 RtlClearBits(BitMapHeader
, Position
, NumberToFind
);
685 /* Return what we found */
691 RtlFindNextForwardRunClear(
692 _In_ PRTL_BITMAP BitMapHeader
,
693 _In_ BITMAP_INDEX FromIndex
,
694 _Out_ PBITMAP_INDEX StartingRunIndex
)
698 /* Check for buffer overrun */
699 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
701 *StartingRunIndex
= FromIndex
;
705 /* Assume a set run first, count it's length */
706 Length
= RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
, MAXINDEX
);
707 *StartingRunIndex
= FromIndex
+ Length
;
709 /* Now return the length of the run */
710 return RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
715 RtlFindNextForwardRunSet(
716 _In_ PRTL_BITMAP BitMapHeader
,
717 _In_ BITMAP_INDEX FromIndex
,
718 _Out_ PBITMAP_INDEX StartingRunIndex
)
722 /* Check for buffer overrun */
723 if (FromIndex
>= BitMapHeader
->SizeOfBitMap
)
725 *StartingRunIndex
= FromIndex
;
729 /* Assume a clear run first, count it's length */
730 Length
= RtlpGetLengthOfRunClear(BitMapHeader
, FromIndex
, MAXINDEX
);
731 *StartingRunIndex
= FromIndex
+ Length
;
733 /* Now return the length of the run */
734 return RtlpGetLengthOfRunSet(BitMapHeader
, FromIndex
+ Length
, MAXINDEX
);
739 RtlFindFirstRunClear(
740 _In_ PRTL_BITMAP BitMapHeader
,
741 _Out_ PBITMAP_INDEX StartingIndex
)
743 return RtlFindNextForwardRunClear(BitMapHeader
, 0, StartingIndex
);
748 RtlFindLastBackwardRunClear(
749 _In_ PRTL_BITMAP BitMapHeader
,
750 _In_ BITMAP_INDEX FromIndex
,
751 _Out_ PBITMAP_INDEX StartingRunIndex
)
753 BITMAP_INDEX Value
, InvValue
, BitPos
;
754 PBITMAP_BUFFER Buffer
;
756 /* Make sure we don't go past the end */
757 FromIndex
= min(FromIndex
, BitMapHeader
->SizeOfBitMap
- 1);
759 /* Calculate positions */
760 Buffer
= BitMapHeader
->Buffer
+ FromIndex
/ _BITCOUNT
;
761 BitPos
= (_BITCOUNT
- 1) - (FromIndex
& (_BITCOUNT
- 1));
763 /* Get the inversed value, clear bits that don't belong to the run */
764 InvValue
= ~(*Buffer
--) << BitPos
>> BitPos
;
766 /* Skip all set ULONGs */
767 while (InvValue
== 0)
769 /* Did we already reach past the first ULONG? */
770 if (Buffer
< BitMapHeader
->Buffer
)
772 /* Yes, nothing found */
776 InvValue
= ~(*Buffer
--);
779 /* We hit a clear bit, check how many set bits are left */
780 BitScanReverse(&BitPos
, InvValue
);
782 /* Calculate last bit position */
783 FromIndex
= (BITMAP_INDEX
)((Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
);
785 Value
= ~InvValue
<< ((_BITCOUNT
- 1) - BitPos
) >> ((_BITCOUNT
- 1) - BitPos
);
787 /* Skip all clear ULONGs */
788 while (Value
== 0 && Buffer
>= BitMapHeader
->Buffer
)
795 /* We hit a set bit, check how many clear bits are left */
796 BitScanReverse(&BitPos
, Value
);
798 /* Calculate Starting Index */
799 *StartingRunIndex
= (BITMAP_INDEX
)((Buffer
+ 1 - BitMapHeader
->Buffer
) * _BITCOUNT
+ BitPos
+ 1);
803 /* We reached the start of the bitmap */
804 *StartingRunIndex
= 0;
807 /* Return length of the run */
808 return (FromIndex
- *StartingRunIndex
);
815 _In_ PRTL_BITMAP BitMapHeader
,
816 _In_ PRTL_BITMAP_RUN RunArray
,
817 _In_ ULONG SizeOfRunArray
,
818 _In_ BOOLEAN LocateLongestRuns
)
820 BITMAP_INDEX StartingIndex
, NumberOfBits
, FromIndex
= 0, SmallestRun
= 0;
824 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
827 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
831 /* Nothing more found? Quit looping. */
832 if (NumberOfBits
== 0) break;
834 /* Add another run */
835 RunArray
[Run
].StartingIndex
= StartingIndex
;
836 RunArray
[Run
].NumberOfBits
= NumberOfBits
;
838 /* Update smallest run */
839 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
845 FromIndex
= StartingIndex
+ NumberOfBits
;
848 /* Check if we are finished */
849 if (Run
< SizeOfRunArray
|| !LocateLongestRuns
)
851 /* Return the number of found runs */
858 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
862 /* Nothing more found? Quit looping. */
863 if (NumberOfBits
== 0) break;
865 /* Check if we have something to update */
866 if (NumberOfBits
> RunArray
[SmallestRun
].NumberOfBits
)
868 /* Update smallest run */
869 RunArray
[SmallestRun
].StartingIndex
= StartingIndex
;
870 RunArray
[SmallestRun
].NumberOfBits
= NumberOfBits
;
873 for (Run
= 0; Run
< SizeOfRunArray
; Run
++)
875 /*Is this the new smallest run? */
876 if (NumberOfBits
< RunArray
[SmallestRun
].NumberOfBits
)
878 /* Set it as new smallest run */
885 FromIndex
+= NumberOfBits
;
893 RtlFindLongestRunClear(
894 IN PRTL_BITMAP BitMapHeader
,
895 IN PBITMAP_INDEX StartingIndex
)
897 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
902 NumberOfBits
= RtlFindNextForwardRunClear(BitMapHeader
,
906 /* Nothing more found? Quit looping. */
907 if (NumberOfBits
== 0) break;
909 /* Was that the longest run? */
910 if (NumberOfBits
> MaxNumberOfBits
)
913 MaxNumberOfBits
= NumberOfBits
;
914 *StartingIndex
= Index
;
918 FromIndex
+= NumberOfBits
;
921 return MaxNumberOfBits
;
926 RtlFindLongestRunSet(
927 IN PRTL_BITMAP BitMapHeader
,
928 IN PBITMAP_INDEX StartingIndex
)
930 BITMAP_INDEX NumberOfBits
, Index
, MaxNumberOfBits
= 0, FromIndex
= 0;
935 NumberOfBits
= RtlFindNextForwardRunSet(BitMapHeader
,
939 /* Nothing more found? Quit looping. */
940 if (NumberOfBits
== 0) break;
942 /* Was that the longest run? */
943 if (NumberOfBits
> MaxNumberOfBits
)
946 MaxNumberOfBits
= NumberOfBits
;
947 *StartingIndex
= Index
;
951 FromIndex
+= NumberOfBits
;
954 return MaxNumberOfBits
;