ReactOS  0.4.15-dev-1150-g593bcce
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:101
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99

◆ 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 }
#define FALSE
Definition: types.h:117
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395

◆ 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
ULONG BITMAP_INDEX
Definition: bitmap.c:64
#define _BITCOUNT
Definition: bitmap.c:62

◆ 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
#define _BITCOUNT
Definition: bitmap.c:62

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

◆ 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
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
#define ASSERT(...)
Definition: bitmap.c:19
#define MAXINDEX
Definition: bitmap.c:63
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define _BITCOUNT
Definition: bitmap.c:62
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34

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 
535 retry:
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,
550  NumberToFind);
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 }
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:609
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
#define MAXINDEX
Definition: bitmap.c:63
ULONG BITMAP_INDEX
Definition: bitmap.c:64
#define min(a, b)
Definition: monoChain.cc:55
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99

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 }
static COORD Position
Definition: mouse.c:34
BITMAP_INDEX NTAPI RtlFindClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:509
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
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:609
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
#define MAXINDEX
Definition: bitmap.c:63
ULONG BITMAP_INDEX
Definition: bitmap.c:64

◆ 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,
829  &StartingIndex);
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,
860  &StartingIndex);
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 }
Definition: bidi.c:433
struct tagRun Run
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
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

◆ 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 }
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:691

◆ 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? */
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 }
IN UCHAR Value
Definition: halp.h:394
Definition: bufpool.h:45
#define BitScanReverse
Definition: interlocked.h:6
ULONG BITMAP_INDEX
Definition: bitmap.c:64
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define min(a, b)
Definition: monoChain.cc:55
#define _BITCOUNT
Definition: bitmap.c:62
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34

◆ RtlFindLeastSignificantBit()

CCHAR NTAPI RtlFindLeastSignificantBit ( ULONGLONG  Value)

Definition at line 235 of file bitmap.c.

236 {
237  ULONG Position;
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
static COORD Position
Definition: mouse.c:34
IN UCHAR Value
Definition: halp.h:394
char CCHAR
Definition: typedefs.h:51
unsigned int ULONG
Definition: retypes.h:1
#define _BITCOUNT
Definition: bitmap.c:62

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;
914  *StartingIndex = Index;
915  }
916 
917  /* Advance bits */
918  FromIndex += NumberOfBits;
919  }
920 
921  return MaxNumberOfBits;
922 }
static const UCHAR Index[8]
Definition: usbohci.c:18
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:691

◆ 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;
947  *StartingIndex = Index;
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
static const UCHAR Index[8]
Definition: usbohci.c:18
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395

◆ RtlFindMostSignificantBit()

CCHAR NTAPI RtlFindMostSignificantBit ( ULONGLONG  Value)

Definition at line 211 of file bitmap.c.

212 {
213  ULONG Position;
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 }
static COORD Position
Definition: mouse.c:34
IN UCHAR Value
Definition: halp.h:394
char CCHAR
Definition: typedefs.h:51
#define BitScanReverse
Definition: interlocked.h:6
unsigned int ULONG
Definition: retypes.h:1
#define _BITCOUNT
Definition: bitmap.c:62

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 }
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
#define MAXINDEX
Definition: bitmap.c:63
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
ULONG BITMAP_INDEX
Definition: bitmap.c:64
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99

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 }
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
#define MAXINDEX
Definition: bitmap.c:63
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
ULONG BITMAP_INDEX
Definition: bitmap.c:64
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99

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 
603 retry:
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,
618  NumberToFind);
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 }
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:609
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
#define MAXINDEX
Definition: bitmap.c:63
ULONG BITMAP_INDEX
Definition: bitmap.c:64
#define min(a, b)
Definition: monoChain.cc:55
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99

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 */
676  Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
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 }
static COORD Position
Definition: mouse.c:34
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:609
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
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
#define MAXINDEX
Definition: bitmap.c:63
BITMAP_INDEX NTAPI RtlFindSetBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:577
ULONG BITMAP_INDEX
Definition: bitmap.c:64

◆ 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 }
unsigned char * PUCHAR
Definition: retypes.h:3
while(1)
Definition: macro.lex.yy.c:740
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG Shift
Definition: rtlfuncs.h:2683
unsigned char Byte
Definition: zlib.h:37
unsigned int ULONG
Definition: retypes.h:1
static const UCHAR BitCountTable[256]
Definition: bitmap.c:73

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 }
#define BitScanForward
Definition: interlocked.h:5
IN UCHAR Value
Definition: halp.h:394
Definition: bufpool.h:45
#define ASSERT(...)
Definition: bitmap.c:19
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define min(a, b)
Definition: monoChain.cc:55
#define _BITCOUNT
Definition: bitmap.c:62
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34

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 }
#define BitScanForward
Definition: interlocked.h:5
static TRIVERTEX ULONG
Definition: bitmap.c:45
Definition: bufpool.h:45
#define ASSERT(...)
Definition: bitmap.c:19
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define min(a, b)
Definition: monoChain.cc:55
#define _BITCOUNT
Definition: bitmap.c:62
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34

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 }
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
ULONG BITMAP_INDEX
Definition: bitmap.c:64
#define _BITCOUNT
Definition: bitmap.c:62

◆ 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 }
#define ASSERT(...)
Definition: bitmap.c:19
ULONG BITMAP_INDEX
Definition: bitmap.c:64
#define _BITCOUNT
Definition: bitmap.c:62

Referenced by AllocateAnyPort(), AllocatePortFromRange(), CcpReferenceCache(), CcpReferenceCacheExclusive(), LdrpInitializeProcess(), MiAllocatePoolPages(), MmInsertLRULastUserPage(), 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 }
Definition: bufpool.h:45
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
#define ASSERT(...)
Definition: bitmap.c:19
#define MAXINDEX
Definition: bitmap.c:63
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define _BITCOUNT
Definition: bitmap.c:62
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34

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 }
#define ASSERT(...)
Definition: bitmap.c:19
#define _BITCOUNT
Definition: bitmap.c:62

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

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().