ReactOS 0.4.15-dev-5664-g3bf4ef6
bitmap.c File Reference
#include <rtl.h>
#include <debug.h>
Include dependency graph for bitmap.c:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define NDEBUG
 
#define ASSERT(...)
 
#define _BITCOUNT   32
 
#define MAXINDEX   0xFFFFFFFF
 

Typedefs

typedef ULONG BITMAP_INDEX
 
typedef ULONGPBITMAP_INDEX
 
typedef ULONG BITMAP_BUFFER
 
typedef ULONGPBITMAP_BUFFER
 

Functions

static __inline BITMAP_INDEX RtlpGetLengthOfRunClear (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
 
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
 
CCHAR NTAPI RtlFindMostSignificantBit (ULONGLONG Value)
 
CCHAR NTAPI RtlFindLeastSignificantBit (ULONGLONG Value)
 
VOID NTAPI RtlInitializeBitMap (_Out_ PRTL_BITMAP BitMapHeader, _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer, _In_opt_ ULONG SizeOfBitMap)
 
VOID NTAPI RtlClearAllBits (_In_ PRTL_BITMAP BitMapHeader)
 
VOID NTAPI RtlSetAllBits (_In_ PRTL_BITMAP BitMapHeader)
 
VOID NTAPI RtlClearBit (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX BitNumber)
 
VOID NTAPI RtlSetBit (_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
 
VOID NTAPI RtlClearBits (_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToClear)
 
VOID NTAPI RtlSetBits (_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
 
BOOLEAN NTAPI RtlTestBit (_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
 
BOOLEAN NTAPI RtlAreBitsClear (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
 
BOOLEAN NTAPI RtlAreBitsSet (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
 
BITMAP_INDEX NTAPI RtlNumberOfSetBits (_In_ PRTL_BITMAP BitMapHeader)
 
BITMAP_INDEX NTAPI RtlNumberOfClearBits (_In_ PRTL_BITMAP BitMapHeader)
 
BITMAP_INDEX NTAPI RtlFindClearBits (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
 
BITMAP_INDEX NTAPI RtlFindSetBits (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
 
BITMAP_INDEX NTAPI RtlFindClearBitsAndSet (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
 
BITMAP_INDEX NTAPI RtlFindSetBitsAndClear (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
 
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
 
BITMAP_INDEX NTAPI RtlFindNextForwardRunSet (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
 
BITMAP_INDEX NTAPI RtlFindFirstRunClear (_In_ PRTL_BITMAP BitMapHeader, _Out_ PBITMAP_INDEX StartingIndex)
 
BITMAP_INDEX NTAPI RtlFindLastBackwardRunClear (_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
 
ULONG NTAPI RtlFindClearRuns (_In_ PRTL_BITMAP BitMapHeader, _In_ PRTL_BITMAP_RUN RunArray, _In_ ULONG SizeOfRunArray, _In_ BOOLEAN LocateLongestRuns)
 
BITMAP_INDEX NTAPI RtlFindLongestRunClear (IN PRTL_BITMAP BitMapHeader, IN PBITMAP_INDEX StartingIndex)
 
BITMAP_INDEX NTAPI RtlFindLongestRunSet (IN PRTL_BITMAP BitMapHeader, IN PBITMAP_INDEX StartingIndex)
 

Variables

static const UCHAR BitCountTable [256]
 

Macro Definition Documentation

◆ _BITCOUNT

#define _BITCOUNT   32

Definition at line 62 of file bitmap.c.

◆ ASSERT

#define ASSERT (   ...)

Definition at line 19 of file bitmap.c.

◆ MAXINDEX

#define MAXINDEX   0xFFFFFFFF

Definition at line 63 of file bitmap.c.

◆ NDEBUG

#define NDEBUG

Definition at line 14 of file bitmap.c.

Typedef Documentation

◆ BITMAP_BUFFER

Definition at line 65 of file bitmap.c.

◆ BITMAP_INDEX

Definition at line 64 of file bitmap.c.

◆ PBITMAP_BUFFER

typedef ULONG * PBITMAP_BUFFER

Definition at line 65 of file bitmap.c.

◆ PBITMAP_INDEX

typedef ULONG * PBITMAP_INDEX

Definition at line 64 of file bitmap.c.

Function Documentation

◆ RtlAreBitsClear()

BOOLEAN NTAPI RtlAreBitsClear ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  StartingIndex,
_In_ BITMAP_INDEX  Length 
)

Definition at line 444 of file bitmap.c.

448{
449 /* Verify parameters */
450 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
452 return FALSE;
453
454 return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
455}
#define FALSE
Definition: types.h:117
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395

◆ RtlAreBitsSet()

BOOLEAN NTAPI RtlAreBitsSet ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  StartingIndex,
_In_ BITMAP_INDEX  Length 
)

Definition at line 459 of file bitmap.c.

463{
464 /* Verify parameters */
465 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
467 return FALSE;
468
469 return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
470}
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153

◆ RtlClearAllBits()

VOID NTAPI RtlClearAllBits ( _In_ PRTL_BITMAP  BitMapHeader)

Definition at line 272 of file bitmap.c.

274{
275 BITMAP_INDEX LengthInUlongs;
276
277 LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
278 RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), 0);
279}
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
#define _BITCOUNT
Definition: bitmap.c:62
ULONG BITMAP_INDEX
Definition: bitmap.c:64

◆ RtlClearBit()

VOID NTAPI RtlClearBit ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  BitNumber 
)

Definition at line 294 of file bitmap.c.

297{
298 ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
299 BitMapHeader->Buffer[BitNumber / _BITCOUNT] &= ~(1 << (BitNumber & (_BITCOUNT - 1)));
300}
#define ASSERT(...)
Definition: bitmap.c:19

Referenced by CcpMapData(), CcpUnpinData(), GdiPoolFree(), HalpGrowMapBuffers(), MiFreePoolPages(), MiReleaseProcessReferenceToSessionDataPage(), MmFreeSwapPage(), RemoveTimer(), and RtlpRemoveFreeBlock().

◆ RtlClearBits()

VOID NTAPI RtlClearBits ( _In_ PRTL_BITMAP  BitMapHeader,
_In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX  StartingIndex,
_In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX  NumberToClear 
)

Definition at line 314 of file bitmap.c.

318{
319 BITMAP_INDEX Bits, Mask;
321
322 ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
323
324 /* Calculate buffer start and first bit index */
325 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
326 Bits = StartingIndex & (_BITCOUNT - 1);
327
328 /* Are we unaligned? */
329 if (Bits)
330 {
331 /* Create an inverse mask by shifting MAXINDEX */
332 Mask = MAXINDEX << Bits;
333
334 /* This is what's left in the first ULONG */
335 Bits = _BITCOUNT - Bits;
336
337 /* Even less bits to clear? */
338 if (NumberToClear < Bits)
339 {
340 /* Calculate how many bits are left */
341 Bits -= NumberToClear;
342
343 /* Fixup the mask on the high side */
344 Mask = Mask << Bits >> Bits;
345
346 /* Clear bits and return */
347 *Buffer &= ~Mask;
348 return;
349 }
350
351 /* Clear bits */
352 *Buffer &= ~Mask;
353
354 /* Update buffer and left bits */
355 Buffer++;
356 NumberToClear -= Bits;
357 }
358
359 /* Clear all full ULONGs */
360 RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
361 Buffer += NumberToClear / _BITCOUNT;
362
363 /* Clear what's left */
364 NumberToClear &= (_BITCOUNT - 1);
365 if (NumberToClear != 0)
366 {
367 Mask = MAXINDEX << NumberToClear;
368 *Buffer &= Mask;
369 }
370}
Definition: bufpool.h:45
unsigned int Mask
Definition: fpcontrol.c:82
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define MAXINDEX
Definition: bitmap.c:63

Referenced by RtlFindSetBitsAndClear().

◆ RtlFindClearBits()

BITMAP_INDEX NTAPI RtlFindClearBits ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  NumberToFind,
_In_ BITMAP_INDEX  HintIndex 
)

Definition at line 509 of file bitmap.c.

513{
514 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
515
516 /* Check for valid parameters */
517 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
518 {
519 return MAXINDEX;
520 }
521
522 /* Check if the hint is outside the bitmap */
523 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
524
525 /* Check for trivial case */
526 if (NumberToFind == 0)
527 {
528 /* Return hint rounded down to byte margin */
529 return HintIndex & ~7;
530 }
531
532 /* First margin is end of bitmap */
533 Margin = BitMapHeader->SizeOfBitMap;
534
535retry:
536 /* Start with hint index, length is 0 */
537 CurrentBit = HintIndex;
538
539 /* Loop until something is found or the end is reached */
540 while (CurrentBit + NumberToFind < Margin)
541 {
542 /* Search for the next clear run, by skipping a set run */
543 CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
544 CurrentBit,
545 MAXINDEX);
546
547 /* Get length of the clear bit run */
548 CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
549 CurrentBit,
551
552 /* Is this long enough? */
553 if (CurrentLength >= NumberToFind)
554 {
555 /* It is */
556 return CurrentBit;
557 }
558
559 CurrentBit += CurrentLength;
560 }
561
562 /* Did we start at a hint? */
563 if (HintIndex)
564 {
565 /* Retry at the start */
566 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
567 HintIndex = 0;
568 goto retry;
569 }
570
571 /* Nothing found */
572 return MAXINDEX;
573}
#define min(a, b)
Definition: monoChain.cc:55
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:610

Referenced by RtlFindClearBitsAndSet().

◆ RtlFindClearBitsAndSet()

BITMAP_INDEX NTAPI RtlFindClearBitsAndSet ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  NumberToFind,
_In_ BITMAP_INDEX  HintIndex 
)

Definition at line 645 of file bitmap.c.

649{
651
652 /* Try to find clear bits */
654
655 /* Did we get something? */
656 if (Position != MAXINDEX)
657 {
658 /* Yes, set the bits */
659 RtlSetBits(BitMapHeader, Position, NumberToFind);
660 }
661
662 /* Return what we found */
663 return Position;
664}
VOID NTAPI RtlSetBits(_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
Definition: bitmap.c:374
BITMAP_INDEX NTAPI RtlFindClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:509
static COORD Position
Definition: mouse.c:34

◆ RtlFindClearRuns()

ULONG NTAPI RtlFindClearRuns ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ PRTL_BITMAP_RUN  RunArray,
_In_ ULONG  SizeOfRunArray,
_In_ BOOLEAN  LocateLongestRuns 
)

Definition at line 814 of file bitmap.c.

819{
820 BITMAP_INDEX StartingIndex, NumberOfBits, FromIndex = 0, SmallestRun = 0;
821 ULONG Run;
822
823 /* Loop the runs */
824 for (Run = 0; Run < SizeOfRunArray; Run++)
825 {
826 /* Look for a run */
827 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
828 FromIndex,
830
831 /* Nothing more found? Quit looping. */
832 if (NumberOfBits == 0) break;
833
834 /* Add another run */
835 RunArray[Run].StartingIndex = StartingIndex;
836 RunArray[Run].NumberOfBits = NumberOfBits;
837
838 /* Update smallest run */
839 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
840 {
841 SmallestRun = Run;
842 }
843
844 /* Advance bits */
845 FromIndex = StartingIndex + NumberOfBits;
846 }
847
848 /* Check if we are finished */
849 if (Run < SizeOfRunArray || !LocateLongestRuns)
850 {
851 /* Return the number of found runs */
852 return Run;
853 }
854
855 while (1)
856 {
857 /* Look for a run */
858 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
859 FromIndex,
861
862 /* Nothing more found? Quit looping. */
863 if (NumberOfBits == 0) break;
864
865 /* Check if we have something to update */
866 if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
867 {
868 /* Update smallest run */
869 RunArray[SmallestRun].StartingIndex = StartingIndex;
870 RunArray[SmallestRun].NumberOfBits = NumberOfBits;
871
872 /* Loop all runs */
873 for (Run = 0; Run < SizeOfRunArray; Run++)
874 {
875 /*Is this the new smallest run? */
876 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
877 {
878 /* Set it as new smallest run */
879 SmallestRun = Run;
880 }
881 }
882 }
883
884 /* Advance bits */
885 FromIndex += NumberOfBits;
886 }
887
888 return Run;
889}
unsigned int ULONG
Definition: retypes.h:1
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:691
Definition: bidi.c:434
struct tagRun Run

◆ RtlFindFirstRunClear()

BITMAP_INDEX NTAPI RtlFindFirstRunClear ( _In_ PRTL_BITMAP  BitMapHeader,
_Out_ PBITMAP_INDEX  StartingIndex 
)

Definition at line 739 of file bitmap.c.

742{
743 return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
744}

◆ RtlFindLastBackwardRunClear()

BITMAP_INDEX NTAPI RtlFindLastBackwardRunClear ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  FromIndex,
_Out_ PBITMAP_INDEX  StartingRunIndex 
)

Definition at line 748 of file bitmap.c.

752{
753 BITMAP_INDEX Value, InvValue, BitPos;
755
756 /* Make sure we don't go past the end */
757 FromIndex = min(FromIndex, BitMapHeader->SizeOfBitMap - 1);
758
759 /* Calculate positions */
760 Buffer = BitMapHeader->Buffer + FromIndex / _BITCOUNT;
761 BitPos = (_BITCOUNT - 1) - (FromIndex & (_BITCOUNT - 1));
762
763 /* Get the inversed value, clear bits that don't belong to the run */
764 InvValue = ~(*Buffer--) << BitPos >> BitPos;
765
766 /* Skip all set ULONGs */
767 while (InvValue == 0)
768 {
769 /* Did we already reach past the first ULONG? */
770 if (Buffer < BitMapHeader->Buffer)
771 {
772 /* Yes, nothing found */
773 return 0;
774 }
775
776 InvValue = ~(*Buffer--);
777 }
778
779 /* We hit a clear bit, check how many set bits are left */
780 BitScanReverse(&BitPos, InvValue);
781
782 /* Calculate last bit position */
783 FromIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos);
784
785 Value = ~InvValue << ((_BITCOUNT - 1) - BitPos) >> ((_BITCOUNT - 1) - BitPos);
786
787 /* Skip all clear ULONGs */
788 while (Value == 0 && Buffer >= BitMapHeader->Buffer)
789 {
790 Value = *Buffer--;
791 }
792
793 if (Value != 0)
794 {
795 /* We hit a set bit, check how many clear bits are left */
796 BitScanReverse(&BitPos, Value);
797
798 /* Calculate Starting Index */
799 *StartingRunIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos + 1);
800 }
801 else
802 {
803 /* We reached the start of the bitmap */
804 *StartingRunIndex = 0;
805 }
806
807 /* Return length of the run */
808 return (FromIndex - *StartingRunIndex);
809}
#define BitScanReverse
Definition: interlocked.h:6
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:413

◆ RtlFindLeastSignificantBit()

CCHAR NTAPI RtlFindLeastSignificantBit ( ULONGLONG  Value)

Definition at line 235 of file bitmap.c.

236{
238
239#ifdef _M_AMD64
240 if (BitScanForward64(&Position, Value))
241 {
242 return (CCHAR)Position;
243 }
244#else
246 {
247 return (CCHAR)Position;
248 }
249 else if (BitScanForward(&Position, Value >> _BITCOUNT))
250 {
251 return (CCHAR)(Position + _BITCOUNT);
252 }
253#endif
254 return -1;
255}
#define BitScanForward
Definition: interlocked.h:5
char CCHAR
Definition: typedefs.h:51

Referenced by Test_RtlFindLeastSignificantBit().

◆ RtlFindLongestRunClear()

BITMAP_INDEX NTAPI RtlFindLongestRunClear ( IN PRTL_BITMAP  BitMapHeader,
IN PBITMAP_INDEX  StartingIndex 
)

Definition at line 893 of file bitmap.c.

896{
897 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
898
899 while (1)
900 {
901 /* Look for a run */
902 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
903 FromIndex,
904 &Index);
905
906 /* Nothing more found? Quit looping. */
907 if (NumberOfBits == 0) break;
908
909 /* Was that the longest run? */
910 if (NumberOfBits > MaxNumberOfBits)
911 {
912 /* Update values */
913 MaxNumberOfBits = NumberOfBits;
915 }
916
917 /* Advance bits */
918 FromIndex += NumberOfBits;
919 }
920
921 return MaxNumberOfBits;
922}
_In_ WDFCOLLECTION _In_ ULONG Index

◆ RtlFindLongestRunSet()

BITMAP_INDEX NTAPI RtlFindLongestRunSet ( IN PRTL_BITMAP  BitMapHeader,
IN PBITMAP_INDEX  StartingIndex 
)

Definition at line 926 of file bitmap.c.

929{
930 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
931
932 while (1)
933 {
934 /* Look for a run */
935 NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
936 FromIndex,
937 &Index);
938
939 /* Nothing more found? Quit looping. */
940 if (NumberOfBits == 0) break;
941
942 /* Was that the longest run? */
943 if (NumberOfBits > MaxNumberOfBits)
944 {
945 /* Update values */
946 MaxNumberOfBits = NumberOfBits;
948 }
949
950 /* Advance bits */
951 FromIndex += NumberOfBits;
952 }
953
954 return MaxNumberOfBits;
955}
BITMAP_INDEX NTAPI RtlFindNextForwardRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:715

◆ RtlFindMostSignificantBit()

CCHAR NTAPI RtlFindMostSignificantBit ( ULONGLONG  Value)

Definition at line 211 of file bitmap.c.

212{
214
215#ifdef _M_AMD64
216 if (BitScanReverse64(&Position, Value))
217 {
218 return (CCHAR)Position;
219 }
220#else
222 {
223 return (CCHAR)(Position + _BITCOUNT);
224 }
225 else if (BitScanReverse(&Position, (ULONG)Value))
226 {
227 return (CCHAR)Position;
228 }
229#endif
230 return -1;
231}

Referenced by Test_RtlFindMostSignificantBit().

◆ RtlFindNextForwardRunClear()

BITMAP_INDEX NTAPI RtlFindNextForwardRunClear ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  FromIndex,
_Out_ PBITMAP_INDEX  StartingRunIndex 
)

Definition at line 691 of file bitmap.c.

695{
697
698 /* Check for buffer overrun */
699 if (FromIndex >= BitMapHeader->SizeOfBitMap)
700 {
701 *StartingRunIndex = FromIndex;
702 return 0;
703 }
704
705 /* Assume a set run first, count it's length */
706 Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXINDEX);
707 *StartingRunIndex = FromIndex + Length;
708
709 /* Now return the length of the run */
710 return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXINDEX);
711}

Referenced by RtlFindClearRuns(), RtlFindFirstRunClear(), and RtlFindLongestRunClear().

◆ RtlFindNextForwardRunSet()

BITMAP_INDEX NTAPI RtlFindNextForwardRunSet ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  FromIndex,
_Out_ PBITMAP_INDEX  StartingRunIndex 
)

Definition at line 715 of file bitmap.c.

719{
721
722 /* Check for buffer overrun */
723 if (FromIndex >= BitMapHeader->SizeOfBitMap)
724 {
725 *StartingRunIndex = FromIndex;
726 return 0;
727 }
728
729 /* Assume a clear run first, count it's length */
730 Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXINDEX);
731 *StartingRunIndex = FromIndex + Length;
732
733 /* Now return the length of the run */
734 return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex + Length, MAXINDEX);
735}

Referenced by RtlFindLongestRunSet().

◆ RtlFindSetBits()

BITMAP_INDEX NTAPI RtlFindSetBits ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  NumberToFind,
_In_ BITMAP_INDEX  HintIndex 
)

Definition at line 577 of file bitmap.c.

581{
582 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
583
584 /* Check for valid parameters */
585 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
586 {
587 return MAXINDEX;
588 }
589
590 /* Check if the hint is outside the bitmap */
591 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
592
593 /* Check for trivial case */
594 if (NumberToFind == 0)
595 {
596 /* Return hint rounded down to byte margin */
597 return HintIndex & ~7;
598 }
599
600 /* First margin is end of bitmap */
601 Margin = BitMapHeader->SizeOfBitMap;
602
603retry:
604 /* Start with hint index, length is 0 */
605 CurrentBit = HintIndex;
606
607 /* Loop until something is found or the end is reached */
608 while (CurrentBit + NumberToFind <= Margin)
609 {
610 /* Search for the next set run, by skipping a clear run */
611 CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
612 CurrentBit,
613 MAXINDEX);
614
615 /* Get length of the set bit run */
616 CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
617 CurrentBit,
619
620 /* Is this long enough? */
621 if (CurrentLength >= NumberToFind)
622 {
623 /* It is */
624 return CurrentBit;
625 }
626
627 CurrentBit += CurrentLength;
628 }
629
630 /* Did we start at a hint? */
631 if (HintIndex)
632 {
633 /* Retry at the start */
634 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
635 HintIndex = 0;
636 goto retry;
637 }
638
639 /* Nothing found */
640 return MAXINDEX;
641}

Referenced by RtlFindSetBitsAndClear().

◆ RtlFindSetBitsAndClear()

BITMAP_INDEX NTAPI RtlFindSetBitsAndClear ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  NumberToFind,
_In_ BITMAP_INDEX  HintIndex 
)

Definition at line 668 of file bitmap.c.

672{
674
675 /* Try to find set bits */
677
678 /* Did we get something? */
679 if (Position != MAXINDEX)
680 {
681 /* Yes, clear the bits */
682 RtlClearBits(BitMapHeader, Position, NumberToFind);
683 }
684
685 /* Return what we found */
686 return Position;
687}
VOID NTAPI RtlClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToClear)
Definition: bitmap.c:314
BITMAP_INDEX NTAPI RtlFindSetBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:577

◆ RtlInitializeBitMap()

VOID NTAPI RtlInitializeBitMap ( _Out_ PRTL_BITMAP  BitMapHeader,
_In_opt_ __drv_aliasesMem PBITMAP_BUFFER  BitMapBuffer,
_In_opt_ ULONG  SizeOfBitMap 
)

Definition at line 260 of file bitmap.c.

264{
265 /* Setup the bitmap header */
266 BitMapHeader->SizeOfBitMap = SizeOfBitMap;
267 BitMapHeader->Buffer = BitMapBuffer;
268}

◆ RtlNumberOfClearBits()

BITMAP_INDEX NTAPI RtlNumberOfClearBits ( _In_ PRTL_BITMAP  BitMapHeader)

Definition at line 500 of file bitmap.c.

502{
503 /* Do some math */
504 return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
505}
BITMAP_INDEX NTAPI RtlNumberOfSetBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:474

◆ RtlNumberOfSetBits()

BITMAP_INDEX NTAPI RtlNumberOfSetBits ( _In_ PRTL_BITMAP  BitMapHeader)

Definition at line 474 of file bitmap.c.

476{
477 PUCHAR Byte, MaxByte;
478 BITMAP_INDEX BitCount = 0;
479 ULONG Shift;
480
481 Byte = (PUCHAR)BitMapHeader->Buffer;
482 MaxByte = Byte + BitMapHeader->SizeOfBitMap / 8;
483
484 while (Byte < MaxByte)
485 {
486 BitCount += BitCountTable[*Byte++];
487 }
488
489 if (BitMapHeader->SizeOfBitMap & 7)
490 {
491 Shift = 8 - (BitMapHeader->SizeOfBitMap & 7);
492 BitCount += BitCountTable[((*Byte) << Shift) & 0xFF];
493 }
494
495 return BitCount;
496}
while(CdLookupNextInitialFileDirent(IrpContext, Fcb, FileContext))
unsigned char Byte
Definition: zlib.h:37
unsigned char * PUCHAR
Definition: retypes.h:3
static const UCHAR BitCountTable[256]
Definition: bitmap.c:73
_In_ ULONG Shift
Definition: rtlfuncs.h:2681

Referenced by RtlNumberOfClearBits().

◆ RtlpGetLengthOfRunClear()

static __inline BITMAP_INDEX RtlpGetLengthOfRunClear ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  StartingIndex,
_In_ BITMAP_INDEX  MaxLength 
)
static

Definition at line 99 of file bitmap.c.

103{
104 BITMAP_INDEX Value, BitPos, Length;
105 PBITMAP_BUFFER Buffer, MaxBuffer;
106
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)
110 return 0;
111
112 /* Calculate positions */
113 Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
114 BitPos = StartingIndex & (_BITCOUNT - 1);
115
116 /* Calculate the maximum length */
117 MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
118 MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
119
120 /* Clear the bits that don't belong to this run */
121 Value = *Buffer++ >> BitPos << BitPos;
122
123 /* Skip all clear ULONGs */
124 while (Value == 0 && Buffer < MaxBuffer)
125 {
126 Value = *Buffer++;
127 }
128
129 /* Did we reach the end? */
130 if (Value == 0)
131 {
132 /* Return maximum length */
133 return MaxLength;
134 }
135
136 /* We hit a set bit, check how many clear bits are left */
137 BitScanForward(&BitPos, Value);
138
139 /* Calculate length up to where we read */
140 Length = (BITMAP_INDEX)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
141 Length += BitPos - _BITCOUNT;
142
143 /* Make sure we don't go past the last bit */
144 if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
145 Length = BitMapHeader->SizeOfBitMap - StartingIndex;
146
147 /* Return the result */
148 return Length;
149}

Referenced by RtlAreBitsClear(), RtlFindClearBits(), RtlFindNextForwardRunClear(), RtlFindNextForwardRunSet(), and RtlFindSetBits().

◆ RtlpGetLengthOfRunSet()

static __inline BITMAP_INDEX RtlpGetLengthOfRunSet ( _In_ PRTL_BITMAP  BitMapHeader,
_In_ BITMAP_INDEX  StartingIndex,
_In_ BITMAP_INDEX  MaxLength 
)
static

Definition at line 153 of file bitmap.c.

157{
158 BITMAP_INDEX InvValue, BitPos, Length;
159 PBITMAP_BUFFER Buffer, MaxBuffer;
160
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)
164 return 0;
165
166 /* Calculate positions */
167 Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
168 BitPos = StartingIndex & (_BITCOUNT - 1);
169
170 /* Calculate the maximum length */
171 MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
172 MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
173
174 /* Get the inversed value, clear bits that don't belong to the run */
175 InvValue = ~(*Buffer++) >> BitPos << BitPos;
176
177 /* Skip all set ULONGs */
178 while (InvValue == 0 && Buffer < MaxBuffer)
179 {
180 InvValue = ~(*Buffer++);
181 }
182
183 /* Did we reach the end? */
184 if (InvValue == 0)
185 {
186 /* Yes, return maximum */
187 return MaxLength;
188 }
189
190 /* We hit a clear bit, check how many set bits are left */
191 BitScanForward(&BitPos, InvValue);
192
193 /* Calculate length up to where we read */
194 Length = (ULONG)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
195 Length += BitPos - _BITCOUNT;
196
197 /* Make sure we don't go past the last bit */
198 if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
199 Length = BitMapHeader->SizeOfBitMap - StartingIndex;
200
201 /* Return the result */
202 return Length;
203}

Referenced by RtlAreBitsSet(), RtlFindClearBits(), RtlFindNextForwardRunClear(), RtlFindNextForwardRunSet(), and RtlFindSetBits().

◆ RtlSetAllBits()

VOID NTAPI RtlSetAllBits ( _In_ PRTL_BITMAP  BitMapHeader)

Definition at line 283 of file bitmap.c.

285{
286 BITMAP_INDEX LengthInUlongs;
287
288 LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
289 RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), ~0);
290}

◆ RtlSetBit()

VOID NTAPI RtlSetBit ( _In_ PRTL_BITMAP  BitMapHeader,
_In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX  BitNumber 
)

Definition at line 304 of file bitmap.c.

307{
308 ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
309 BitMapHeader->Buffer[BitNumber / _BITCOUNT] |= ((BITMAP_INDEX)1 << (BitNumber & (_BITCOUNT - 1)));
310}

Referenced by AllocateAnyPort(), AllocatePortFromRange(), CcpReferenceCache(), CcpReferenceCacheExclusive(), LdrpInitializeProcess(), MiAllocatePoolPages(), RtlpInsertFreeBlockHelper(), scrub_raid5_stripe(), and scrub_raid6_stripe().

◆ RtlSetBits()

VOID NTAPI RtlSetBits ( _In_ PRTL_BITMAP  BitMapHeader,
_In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX  StartingIndex,
_In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX  NumberToSet 
)

Definition at line 374 of file bitmap.c.

378{
379 BITMAP_INDEX Bits, Mask;
381
382 ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
383
384 /* Calculate buffer start and first bit index */
385 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
386 Bits = StartingIndex & (_BITCOUNT - 1);
387
388 /* Are we unaligned? */
389 if (Bits)
390 {
391 /* Create a mask by shifting MAXINDEX */
392 Mask = MAXINDEX << Bits;
393
394 /* This is what's left in the first ULONG */
395 Bits = _BITCOUNT - Bits;
396
397 /* Even less bits to clear? */
398 if (NumberToSet < Bits)
399 {
400 /* Calculate how many bits are left */
401 Bits -= NumberToSet;
402
403 /* Fixup the mask on the high side */
404 Mask = Mask << Bits >> Bits;
405
406 /* Set bits and return */
407 *Buffer |= Mask;
408 return;
409 }
410
411 /* Set bits */
412 *Buffer |= Mask;
413
414 /* Update buffer and left bits */
415 Buffer++;
416 NumberToSet -= Bits;
417 }
418
419 /* Set all full ULONGs */
420 RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXINDEX);
421 Buffer += NumberToSet / _BITCOUNT;
422
423 /* Set what's left */
424 NumberToSet &= (_BITCOUNT - 1);
425 if (NumberToSet != 0)
426 {
427 Mask = MAXINDEX << NumberToSet;
428 *Buffer |= ~Mask;
429 }
430}

Referenced by RtlFindClearBitsAndSet().

◆ RtlTestBit()

BOOLEAN NTAPI RtlTestBit ( _In_ PRTL_BITMAP  BitMapHeader,
_In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX  BitNumber 
)

Definition at line 434 of file bitmap.c.

437{
438 ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
439 return (BitMapHeader->Buffer[BitNumber / _BITCOUNT] >> (BitNumber & (_BITCOUNT - 1))) & 1;
440}

Referenced by CcpAllocateCacheSections(), CcpMapData(), CcRemapBcb(), CcRepinBcb(), GdiPoolFree(), MiFreePoolPages(), MiGetPfnEntry(), RtlpInsertFreeBlockHelper(), RtlpRemoveFreeBlock(), and RtlpValidateHeap().

Variable Documentation

◆ BitCountTable

const UCHAR BitCountTable[256]
static
Initial value:
=
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 73 of file bitmap.c.

Referenced by RtlNumberOfSetBits().