bitmap.c File Reference

#include "ntrtlp.h"

Go to the source code of this file.

Defines
#define	RightShiftUlong(E1, E2)   ((E2) < 32 ? (E1) >> (E2) : 0)
#define	LeftShiftUlong(E1, E2)   ((E2) < 32 ? (E1) << (E2) : 0)
#define	GET_BYTE_DECLARATIONS()   PUCHAR _CURRENT_POSITION;
#define	GET_BYTE_INITIALIZATION(RTL_BITMAP, BYTE_INDEX)
#define	GET_BYTE(THIS_BYTE)
#define	BM_4567   0xFFFFFFFF00000000UI64
#define	BM_67   0xFFFF000000000000UI64
#define	BM_7   0xFF00000000000000UI64
#define	BM_5   0x0000FF0000000000UI64
#define	BM_23   0x00000000FFFF0000UI64
#define	BM_3   0x00000000FF000000UI64
#define	BM_1   0x000000000000FF00UI64
#define	BM_0123   0x00000000FFFFFFFFUI64
#define	BM_01   0x000000000000FFFFUI64
#define	BM_0   0x00000000000000FFUI64
#define	BM_2   0x0000000000FF0000UI64
#define	BM_45   0x0000FFFF00000000UI64
#define	BM_4   0x000000FF00000000UI64
#define	BM_6   0x00FF000000000000UI64
Functions
VOID	RtlInitializeBitMap (IN PRTL_BITMAP BitMapHeader, IN PULONG BitMapBuffer, IN ULONG SizeOfBitMap)
VOID	RtlClearAllBits (IN PRTL_BITMAP BitMapHeader)
VOID	RtlSetAllBits (IN PRTL_BITMAP BitMapHeader)
ULONG	RtlFindClearBits (IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex)
ULONG	RtlFindSetBits (IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex)
ULONG	RtlFindClearBitsAndSet (IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex)
ULONG	RtlFindSetBitsAndClear (IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex)
VOID	RtlClearBits (IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG NumberToClear)
VOID	RtlSetBits (IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG NumberToSet)
ULONG	RtlFindClearRuns (IN PRTL_BITMAP BitMapHeader, PRTL_BITMAP_RUN RunArray, ULONG SizeOfRunArray, BOOLEAN LocateLongestRuns)
ULONG	RtlFindLongestRunClear (IN PRTL_BITMAP BitMapHeader, OUT PULONG StartingIndex)
ULONG	RtlFindFirstRunClear (IN PRTL_BITMAP BitMapHeader, OUT PULONG StartingIndex)
ULONG	RtlNumberOfClearBits (IN PRTL_BITMAP BitMapHeader)
ULONG	RtlNumberOfSetBits (IN PRTL_BITMAP BitMapHeader)
BOOLEAN	RtlAreBitsClear (IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG Length)
BOOLEAN	RtlAreBitsSet (IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG Length)
ULONG	RtlFindNextForwardRunClear (IN PRTL_BITMAP BitMapHeader, IN ULONG FromIndex, IN PULONG StartingRunIndex)
ULONG	RtlFindLastBackwardRunClear (IN PRTL_BITMAP BitMapHeader, IN ULONG FromIndex, IN PULONG StartingRunIndex)
CCHAR	RtlFindMostSignificantBit (IN ULONGLONG Set)
CCHAR	RtlFindLeastSignificantBit (IN ULONGLONG Set)
Variables
CONST CCHAR	RtlpBitsClearAnywhere []
CONST CCHAR	RtlpBitsClearLow []
CONST CCHAR	RtlpBitsClearHigh []
CONST CCHAR	RtlpBitsClearTotal []
CONST UCHAR	FillMask [] = { 0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF }
CONST UCHAR	ZeroMask [] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xf0, 0xe0, 0xc0, 0x80, 0x00 }
CONST ULONG	FillMaskUlong []

---

Define Documentation

#define BM_0   0x00000000000000FFUI64

Definition at line 2916 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_01   0x000000000000FFFFUI64

Definition at line 2915 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_0123   0x00000000FFFFFFFFUI64

Definition at line 2914 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_1   0x000000000000FF00UI64

Definition at line 2912 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_2   0x0000000000FF0000UI64

Definition at line 2917 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_23   0x00000000FFFF0000UI64

Definition at line 2910 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_3   0x00000000FF000000UI64

Definition at line 2911 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_4   0x000000FF00000000UI64

Definition at line 2919 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_45   0x0000FFFF00000000UI64

Definition at line 2918 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_4567   0xFFFFFFFF00000000UI64

Definition at line 2906 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_5   0x0000FF0000000000UI64

Definition at line 2909 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_6   0x00FF000000000000UI64

Definition at line 2920 of file rtl/bitmap.c. Referenced by RtlFindLeastSignificantBit().

#define BM_67   0xFFFF000000000000UI64

Definition at line 2907 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define BM_7   0xFF00000000000000UI64

Definition at line 2908 of file rtl/bitmap.c. Referenced by RtlFindMostSignificantBit().

#define GET_BYTE (  THIS_BYTE   )

Value: ( \ THIS_BYTE = *(_CURRENT_POSITION++) \ ) Definition at line 112 of file rtl/bitmap.c. Referenced by RtlAreBitsClear(), RtlAreBitsSet(), RtlFindClearBits(), RtlFindClearRuns(), RtlFindSetBits(), RtlNumberOfClearBits(), and RtlNumberOfSetBits().

#define GET_BYTE_DECLARATIONS (   )     PUCHAR _CURRENT_POSITION;

Definition at line 105 of file rtl/bitmap.c. Referenced by RtlAreBitsClear(), RtlAreBitsSet(), RtlFindClearBits(), RtlFindClearRuns(), RtlFindSetBits(), RtlNumberOfClearBits(), and RtlNumberOfSetBits().

#define GET_BYTE_INITIALIZATION (  RTL_BITMAP, BYTE_INDEX   )

Value: { \ _CURRENT_POSITION = &((PUCHAR)((RTL_BITMAP)->Buffer))[BYTE_INDEX]; \ } Definition at line 108 of file rtl/bitmap.c. Referenced by RtlAreBitsClear(), RtlAreBitsSet(), RtlFindClearBits(), RtlFindClearRuns(), RtlFindSetBits(), RtlNumberOfClearBits(), and RtlNumberOfSetBits().

#define LeftShiftUlong (  E1, E2   )     ((E2) < 32 ? (E1) << (E2) : 0)

Definition at line 37 of file rtl/bitmap.c. Referenced by RtlClearBits(), and RtlSetBits().

#define RightShiftUlong (  E1, E2   )     ((E2) < 32 ? (E1) >> (E2) : 0)

Definition at line 36 of file rtl/bitmap.c. Referenced by RtlClearBits(), and RtlSetBits().

---

Function Documentation

BOOLEAN RtlAreBitsClear (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  StartingIndex, IN ULONG  Length )

Definition at line 2305 of file rtl/bitmap.c. References BitMapHeader, FALSE, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, TRUE, and ZeroMask. Referenced by CmpInitializeHiveList(), main(), and MiAttemptPageFileReduction(). : This procedure determines if the range of specified bits are all clear. Arguments: BitMapHeader - Supplies a pointer to the previously initialized bitmap. StartingIndex - Supplies the starting bit index to examine Length - Supplies the number of bits to examine Return Value: BOOLEAN - TRUE if the specified bits in the bitmap are all clear, and FALSE if any are set or if the range is outside the bitmap or if Length is zero. --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG EndingIndex; ULONG StartingByte; ULONG EndingByte; ULONG StartingOffset; ULONG EndingOffset; ULONG i; UCHAR Byte; GET_BYTE_DECLARATIONS(); // // To make the loops in our test run faster we'll extract the fields // from the bitmap header // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // First make sure that the specified range is contained within the // bitmap, and the length is not zero. // if ((StartingIndex + Length > SizeOfBitMap) || (Length == 0)) { return FALSE; } // // Compute the ending index, starting and ending byte, and the starting // and ending offset within each byte // EndingIndex = StartingIndex + Length - 1; StartingByte = StartingIndex / 8; EndingByte = EndingIndex / 8; StartingOffset = StartingIndex % 8; EndingOffset = EndingIndex % 8; // // Set ourselves up to get the next byte // GET_BYTE_INITIALIZATION( BitMapHeader, StartingByte ); // // Special case the situation where the starting byte and ending // byte are one in the same // if (StartingByte == EndingByte) { // // Get the single byte we are to look at // GET_BYTE( Byte ); // // Now we compute the mask of bits we're after and then AND it with // the byte. If it is zero then the bits in question are all clear // otherwise at least one of them is set. // if ((ZeroMask[StartingOffset] & FillMask[EndingOffset+1] & Byte) == 0) { return TRUE; } else { return FALSE; } } else { // // Get the first byte that we're after, and then // compute the mask of bits we're after for the first byte then // AND it with the byte itself. // GET_BYTE( Byte ); if ((ZeroMask[StartingOffset] & Byte) != 0) { return FALSE; } // // Now for every whole byte inbetween read in the byte, // and make sure it is all zeros // for (i = StartingByte+1; i < EndingByte; i += 1) { GET_BYTE( Byte ); if (Byte != 0) { return FALSE; } } // // Get the last byte we're after, and then // compute the mask of bits we're after for the last byte then // AND it with the byte itself. // GET_BYTE( Byte ); if ((FillMask[EndingOffset+1] & Byte) != 0) { return FALSE; } } return TRUE; }

BOOLEAN RtlAreBitsSet (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  StartingIndex, IN ULONG  Length )

Definition at line 2464 of file rtl/bitmap.c. References BitMapHeader, FALSE, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, TRUE, and ZeroMask. Referenced by main(). : This procedure determines if the range of specified bits are all set. Arguments: BitMapHeader - Supplies a pointer to the previously initialized bitmap. StartingIndex - Supplies the starting bit index to examine Length - Supplies the number of bits to examine Return Value: BOOLEAN - TRUE if the specified bits in the bitmap are all set, and FALSE if any are clear or if the range is outside the bitmap or if Length is zero. --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG EndingIndex; ULONG StartingByte; ULONG EndingByte; ULONG StartingOffset; ULONG EndingOffset; ULONG i; UCHAR Byte; GET_BYTE_DECLARATIONS(); // // To make the loops in our test run faster we'll extract the fields // from the bitmap header // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // First make sure that the specified range is contained within the // bitmap, and the length is not zero. // if ((StartingIndex + Length > SizeOfBitMap) || (Length == 0)) { return FALSE; } // // Compute the ending index, starting and ending byte, and the starting // and ending offset within each byte // EndingIndex = StartingIndex + Length - 1; StartingByte = StartingIndex / 8; EndingByte = EndingIndex / 8; StartingOffset = StartingIndex % 8; EndingOffset = EndingIndex % 8; // // Set ourselves up to get the next byte // GET_BYTE_INITIALIZATION( BitMapHeader, StartingByte ); // // Special case the situation where the starting byte and ending // byte are one in the same // if (StartingByte == EndingByte) { // // Get the single byte we are to look at // GET_BYTE( Byte ); // // Now we compute the mask of bits we're after and then AND it with // the complement of the byte If it is zero then the bits in question // are all clear otherwise at least one of them is clear. // if ((ZeroMask[StartingOffset] & FillMask[EndingOffset+1] & ~Byte) == 0) { return TRUE; } else { return FALSE; } } else { // // Get the first byte that we're after, and then // compute the mask of bits we're after for the first byte then // AND it with the complement of the byte itself. // GET_BYTE( Byte ); if ((ZeroMask[StartingOffset] & ~Byte) != 0) { return FALSE; } // // Now for every whole byte inbetween read in the byte, // and make sure it is all ones // for (i = StartingByte+1; i < EndingByte; i += 1) { GET_BYTE( Byte ); if (Byte != 0xff) { return FALSE; } } // // Get the last byte we're after, and then // compute the mask of bits we're after for the last byte then // AND it with the complement of the byte itself. // GET_BYTE( Byte ); if ((FillMask[EndingOffset+1] & ~Byte) != 0) { return FALSE; } } return TRUE; }

VOID RtlClearAllBits (  IN PRTL_BITMAP  BitMapHeader  )

Definition at line 266 of file rtl/bitmap.c. References BitMapHeader. Referenced by DoBitMapTest(), HvInitializeHive(), HvRefreshHive(), HvSyncHive(), IopCreateSummaryDump(), main(), MiBuildPagedPool(), MiInitializeSessionIds(), MiInitializeSessionPool(), MiInitializeSystemSpaceMap(), MiInitMachineDependent(), NtAllocateUserPhysicalPages(), and NtAllocateVirtualMemory(). : This procedure clears all bits in the specified Bit Map. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap Return Value: None. --*/ { // // Clear all the bits // RtlZeroMemory( BitMapHeader->Buffer, ((BitMapHeader->SizeOfBitMap + 31) / 32) * 4 ); // // And return to our caller // //DbgPrint("ClearAllBits"); DumpBitMap(BitMapHeader); return; }

VOID RtlClearBits (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  StartingIndex, IN ULONG  NumberToClear )

Definition at line 1508 of file rtl/bitmap.c. References ASSERT, BitMapHeader, LeftShiftUlong, and RightShiftUlong. Referenced by DoBitMapTest(), HvFreeHivePartial(), HvMarkClean(), HvRefreshHive(), IopRemovePageFromPageMap(), main(), MiAllocatePoolPages(), MiAttemptPageFileExtension(), MiAttemptPageFileReduction(), MiBuildPagedPool(), MiDereferenceSession(), MiFreePoolPages(), MiGatherPagefilePages(), MiInitializeSessionPool(), MiMapViewInSystemSpace(), MiReleasePageFileSpace(), MiSessionCreateInternal(), MiUnmapViewInSystemSpace(), NtAllocateUserPhysicalPages(), NtCreatePagingFile(), NtFreeUserPhysicalPages(), RtlFindSetBitsAndClear(), and SetHandleFlag(). 01516 : 01517 01518 This procedure clears the specified range of bits within the 01519 specified bit map. 01520 01521 Arguments: 01522 01523 BitMapHeader - Supplies a pointer to the previously initialized Bit Map. 01524 01525 StartingIndex - Supplies the index (zero based) of the first bit to clear. 01526 01527 NumberToClear - Supplies the number of bits to clear. 01528 01529 Return Value: 01530 01531 None. 01532 01533 --*/ 01534 01535 { 01536 ULONG BitOffset; 01537 PULONG CurrentLong; 01538 01539 //DbgPrint("ClearBits %08lx, ", NumberToClear); 01540 //DbgPrint("%08lx", StartingIndex); 01541 01542 ASSERT( StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap ); 01543 01544 // 01545 // Special case the situation where the number of bits to clear is 01546 // zero. Turn this into a noop. 01547 // 01548 01549 if (NumberToClear == 0) { 01550 01551 return; 01552 } 01553 01554 BitOffset = StartingIndex % 32; 01555 01556 // 01557 // Get a pointer to the first longword that needs to be zeroed out 01558 // 01559 01560 CurrentLong = &BitMapHeader->Buffer[ StartingIndex / 32 ]; 01561 01562 // 01563 // Check if we can only need to clear out one longword. 01564 // 01565 01566 if ((BitOffset + NumberToClear) <= 32) { 01567 01568 // 01569 // To build a mask of bits to clear we shift left to get the number 01570 // of bits we're clearing and then shift right to put it in position. 01571 // We'll typecast the right shift to ULONG to make sure it doesn't 01572 // do a sign extend. 01573 // 01574 01575 *CurrentLong &= ~LeftShiftUlong(RightShiftUlong(((ULONG)0xFFFFFFFF),(32 - NumberToClear)), 01576 BitOffset); 01577 01578 // 01579 // And return to our caller 01580 // 01581 01582 //DumpBitMap(BitMapHeader); 01583 01584 return; 01585 } 01586 01587 // 01588 // We can clear out to the end of the first longword so we'll 01589 // do that right now. 01590 // 01591 01592 *CurrentLong &= ~LeftShiftUlong(0xFFFFFFFF, BitOffset); 01593 01594 // 01595 // And indicate what the next longword to clear is and how many 01596 // bits are left to clear 01597 // 01598 01599 CurrentLong += 1; 01600 NumberToClear -= 32 - BitOffset; 01601 01602 // 01603 // The bit position is now long aligned, so we can continue 01604 // clearing longwords until the number to clear is less than 32 01605 // 01606 01607 while (NumberToClear >= 32) { 01608 01609 *CurrentLong = 0; 01610 CurrentLong += 1; 01611 NumberToClear -= 32; 01612 } 01613 01614 // 01615 // And now we can clear the remaining bits, if there are any, in the 01616 // last longword 01617 // 01618 01619 if (NumberToClear > 0) { 01620 01621 *CurrentLong &= LeftShiftUlong(0xFFFFFFFF, NumberToClear); 01622 } 01623 01624 // 01625 // And return to our caller 01626 // 01627 01628 //DumpBitMap(BitMapHeader); 01629 01630 return; 01631 }

ULONG RtlFindClearBits (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  NumberToFind, IN ULONG  HintIndex )

Definition at line 345 of file rtl/bitmap.c. References BitMapHeader, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, RtlpBitsClearAnywhere, RtlpBitsClearHigh, RtlpBitsClearLow, TRUE, and ZeroMask. Referenced by RtlFindClearBitsAndSet(). : This procedure searches the specified bit map for the specified contiguous region of clear bits. If a run is not found from the hint to the end of the bitmap, we will search again from the beginning of the bitmap. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. NumberToFind - Supplies the size of the contiguous region to find. HintIndex - Supplies the index (zero based) of where we should start the search from within the bitmap. Return Value: ULONG - Receives the starting index (zero based) of the contiguous region of clear bits found. If not such a region cannot be found a -1 (i.e. 0xffffffff) is returned. --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG HintBit; ULONG MainLoopIndex; GET_BYTE_DECLARATIONS(); // // To make the loops in our test run faster we'll extract the // fields from the bitmap header // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // Set any unused bits in the last byte so we won't count them. We do // this by first checking if there is any odd bits in the last byte. // if ((SizeOfBitMap % 8) != 0) { // // The last byte has some odd bits so we'll set the high unused // bits in the last byte to 1's // ((PUCHAR)BitMapHeader->Buffer)[SizeInBytes - 1] |= ZeroMask[SizeOfBitMap % 8]; } // // Calculate from the hint index where the hint byte is and set ourselves // up to read the hint on the next call to GET_BYTE. To make the // algorithm run fast we'll only honor hints down to the byte level of // granularity. There is a possibility that we'll need to execute // our main logic twice. Once to test from the hint byte to the end of // the bitmap and the other to test from the start of the bitmap. First // we need to make sure the Hint Index is within range. // if (HintIndex >= SizeOfBitMap) { HintIndex = 0; } HintBit = HintIndex % 8; for (MainLoopIndex = 0; MainLoopIndex < 2; MainLoopIndex += 1) { ULONG StartByteIndex; ULONG EndByteIndex; UCHAR CurrentByte; // // Check for the first time through the main loop, which indicates // that we are going to start our search at our hint byte // if (MainLoopIndex == 0) { StartByteIndex = HintIndex / 8; EndByteIndex = SizeInBytes; // // This is the second time through the loop, make sure there is // actually something to check before the hint byte // } else if (HintIndex != 0) { // // The end index for the second time around is based on the // number of bits we need to find. We need to use this inorder // to take the case where the preceding byte to the hint byte // is the start of our run, and the run includes the hint byte // and some following bytes, based on the number of bits needed // The computation is to take the number of bits needed minus // 2 divided by 8 and then add 2. This will take in to account // the worst possible case where we have one bit hanging off // of each end byte, and all intervening bytes are all zero. // if (NumberToFind < 2) { EndByteIndex = HintIndex / 8; } else { EndByteIndex = (HintIndex / 8) + ((NumberToFind - 2) / 8) + 2; // // Make sure we don't overrun the end of the bitmap // if (EndByteIndex > SizeInBytes) { EndByteIndex = SizeInBytes; } } HintIndex = 0; HintBit = 0; StartByteIndex = 0; // // Otherwise we already did a complete loop through the bitmap // so we should simply return -1 to say nothing was found // } else { return 0xffffffff; } // // Set ourselves up to get the next byte // GET_BYTE_INITIALIZATION(BitMapHeader, StartByteIndex); // // Get the first byte, and set any bits before the hint bit. // GET_BYTE( CurrentByte ); CurrentByte |= FillMask[HintBit]; // // If the number of bits can only fit in 1 or 2 bytes (i.e., 9 bits or // less) we do the following test case. // if (NumberToFind <= 9) { ULONG CurrentBitIndex; UCHAR PreviousByte; PreviousByte = 0xff; // // Examine all the bytes within our test range searching // for a fit // CurrentBitIndex = StartByteIndex * 8; while (TRUE) { // // If this is the first itteration of the loop, mask Current // byte with the real hint. // // // Check to see if the current byte coupled with the previous // byte will satisfy the requirement. The check uses the high // part of the previous byte and low part of the current byte. // if (((ULONG)RtlpBitsClearHigh[PreviousByte] + (ULONG)RtlpBitsClearLow[CurrentByte]) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these two bytes, so we can compute // the starting index. This is done by taking the // index of the current byte (bit 0) and subtracting the // number of bits its takes to get to the first cleared // high bit. // StartingIndex = CurrentBitIndex - (LONG)RtlpBitsClearHigh[PreviousByte]; // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // The previous byte does not help, so check the current byte. // if ((ULONG)RtlpBitsClearAnywhere[CurrentByte] >= NumberToFind) { UCHAR BitMask; ULONG i; // // It all fits in a single byte, so calculate the bit // number. We do this by taking a mask of the appropriate // size and shifting it over until it fits. It fits when // we can bitwise-and the current byte with the bitmask // and get a zero back. // BitMask = FillMask[ NumberToFind ]; for (i = 0; (BitMask & CurrentByte) != 0; i += 1) { BitMask <<= 1; } // // return to our caller the located bit index, and the // number that we found. // return CurrentBitIndex + i; } // // For the next iteration through our loop we need to make // the current byte into the previous byte, and go to the // top of the loop again. // PreviousByte = CurrentByte; // // Increment our Bit Index, and either exit, or get the // next byte. // CurrentBitIndex += 8; if ( CurrentBitIndex < EndByteIndex * 8 ) { GET_BYTE( CurrentByte ); } else { break; } } // end loop CurrentBitIndex // // The number to find is greater than 9 but if it is less than 15 // then we know it can be satisfied with at most 2 bytes, or 3 bytes // if the middle byte (of the 3) is all zeros. // } else if (NumberToFind < 15) { ULONG CurrentBitIndex; UCHAR PreviousPreviousByte; UCHAR PreviousByte; PreviousByte = 0xff; // // Examine all the bytes within our test range searching // for a fit // CurrentBitIndex = StartByteIndex * 8; while (TRUE) { // // For the next iteration through our loop we need to make // the current byte into the previous byte, the previous // byte into the previous previous byte, and go forward. // PreviousPreviousByte = PreviousByte; PreviousByte = CurrentByte; // // Increment our Bit Index, and either exit, or get the // next byte. // CurrentBitIndex += 8; if ( CurrentBitIndex < EndByteIndex * 8 ) { GET_BYTE( CurrentByte ); } else { break; } // // if the previous byte is all zeros then maybe the // request can be satisfied using the Previous Previous Byte // Previous Byte, and the Current Byte. // if ((PreviousByte == 0) && (((ULONG)RtlpBitsClearHigh[PreviousPreviousByte] + 8 + (ULONG)RtlpBitsClearLow[CurrentByte]) >= NumberToFind)) { ULONG StartingIndex; // // It all fits in these three bytes, so we can compute // the starting index. This is done by taking the // index of the previous byte (bit 0) and subtracting // the number of bits its takes to get to the first // cleared high bit. // StartingIndex = (CurrentBitIndex - 8) - (LONG)RtlpBitsClearHigh[PreviousPreviousByte]; // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // Check to see if the Previous byte and current byte // together satisfy the request. // if (((ULONG)RtlpBitsClearHigh[PreviousByte] + (ULONG)RtlpBitsClearLow[CurrentByte]) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these two bytes, so we can compute // the starting index. This is done by taking the // index of the current byte (bit 0) and subtracting the // number of bits its takes to get to the first cleared // high bit. // StartingIndex = CurrentBitIndex - (LONG)RtlpBitsClearHigh[PreviousByte]; // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } } // end loop CurrentBitIndex // // The number to find is greater than or equal to 15. This request // has to have at least one byte of all zeros to be satisfied // } else { ULONG CurrentByteIndex; ULONG ZeroBytesNeeded; ULONG ZeroBytesFound; UCHAR StartOfRunByte; LONG StartOfRunIndex; // // First precalculate how many zero bytes we're going to need // ZeroBytesNeeded = (NumberToFind - 7) / 8; // // Indicate for the first time through our loop that we haven't // found a zero byte yet, and indicate that the start of the // run is the byte just before the start byte index // ZeroBytesFound = 0; StartOfRunByte = 0xff; StartOfRunIndex = StartByteIndex - 1; // // Examine all the bytes in our test range searching for a fit // CurrentByteIndex = StartByteIndex; while (TRUE) { // // If the number of zero bytes fits our minimum requirements // then we can do the additional test to see if we // actually found a fit // if ((ZeroBytesFound >= ZeroBytesNeeded) && ((ULONG)RtlpBitsClearHigh[StartOfRunByte] + ZeroBytesFound*8 + (ULONG)RtlpBitsClearLow[CurrentByte]) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these bytes, so we can compute // the starting index. This is done by taking the // StartOfRunIndex times 8 and adding the number of bits // it takes to get to the first cleared high bit. // StartingIndex = (StartOfRunIndex * 8) + (8 - (LONG)RtlpBitsClearHigh[StartOfRunByte]); // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // Check to see if the byte is zero and increment // the number of zero bytes found // if (CurrentByte == 0) { ZeroBytesFound += 1; // // The byte isn't a zero so we need to start over again // looking for zero bytes. // } else { ZeroBytesFound = 0; StartOfRunByte = CurrentByte; StartOfRunIndex = CurrentByteIndex; } // // Increment our Byte Index, and either exit, or get the // next byte. // CurrentByteIndex += 1; if ( CurrentByteIndex < EndByteIndex ) { GET_BYTE( CurrentByte ); } else { break; } } // end loop CurrentByteIndex } } // // We never found a fit so we'll return -1 // return 0xffffffff; }

ULONG RtlFindClearBitsAndSet (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  NumberToFind, IN ULONG  HintIndex )

Definition at line 1382 of file rtl/bitmap.c. References BitMapHeader, RtlFindClearBits(), and RtlSetBits(). Referenced by DoBitMapTest(), main(), MiAllocatePoolPages(), MiGatherPagefilePages(), MiInsertInSystemSpace(), and MiSessionCreateInternal(). : This procedure searches the specified bit map for the specified contiguous region of clear bits, sets the bits and returns the number of bits found, and the starting bit number which was clear then set. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. NumberToFind - Supplies the size of the contiguous region to find. HintIndex - Supplies the index (zero based) of where we should start the search from within the bitmap. Return Value: ULONG - Receives the starting index (zero based) of the contiguous region found. If such a region cannot be located a -1 (i.e., 0xffffffff) is returned. --*/ { ULONG StartingIndex; // // First look for a run of clear bits that equals the size requested // StartingIndex = RtlFindClearBits( BitMapHeader, NumberToFind, HintIndex ); //DbgPrint("FindClearBits %08lx, ", NumberToFind); //DbgPrint("%08lx", StartingIndex); //DumpBitMap(BitMapHeader); if (StartingIndex != 0xffffffff) { // // We found a large enough run of clear bits so now set them // RtlSetBits( BitMapHeader, StartingIndex, NumberToFind ); } // // And return to our caller // return StartingIndex; }

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

Definition at line 1764 of file rtl/bitmap.c. References BitMapHeader, DbgPrint, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, RtlpBitsClearAnywhere, RtlpBitsClearHigh, RtlpBitsClearLow, and ZeroMask. Referenced by RtlFindLongestRunClear(). : This procedure finds N contiguous runs of clear bits within the specified bit map. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. RunArray - Receives the bit position, and length of each of the free runs that the procedure locates. The array will be sorted according to length. SizeOfRunArray - Supplies the maximum number of entries the caller wants returned in RunArray LocateLongestRuns - Indicates if this routine is to return the longest runs it can find or just the first N runs. Return Value: ULONG - Receives the number of runs that the procedure has located and returned in RunArray --*/ { ULONG RunIndex; ULONG i; LONG j; ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG CurrentRunSize; ULONG CurrentRunIndex; ULONG CurrentByteIndex; UCHAR CurrentByte; UCHAR BitMask; UCHAR TempNumber; GET_BYTE_DECLARATIONS(); // // Reference the bitmap header to make the loop run faster // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // Set any unused bits in the last byte so we won't count them. We do // this by first checking if there is any odd bits in the last byte. // if ((SizeOfBitMap % 8) != 0) { // // The last byte has some odd bits so we'll set the high unused // bits in the last byte to 1's // ((PUCHAR)BitMapHeader->Buffer)[SizeInBytes - 1] |= ZeroMask[SizeOfBitMap % 8]; } // // Set it up so we can the use GET_BYTE macro // GET_BYTE_INITIALIZATION( BitMapHeader, 0); // // Set our RunIndex and current run variables. Run Index allays is the index // of the next location to fill in or it could be one beyond the end of the // array. // RunIndex = 0; for (i = 0; i < SizeOfRunArray; i += 1) { RunArray[i].NumberOfBits = 0; } CurrentRunSize = 0; CurrentRunIndex = 0; // // Examine every byte in the BitMap // for (CurrentByteIndex = 0; CurrentByteIndex < SizeInBytes; CurrentByteIndex += 1) { GET_BYTE( CurrentByte ); #if DBG if (NtfsDebugIt) { DbgPrint("%d: %08lx %08lx %08lx %08lx %08lx\n",__LINE__,RunIndex,CurrentRunSize,CurrentRunIndex,CurrentByteIndex,CurrentByte); } #endif // // If the current byte is not all zeros we need to (1) check if // the current run is big enough to be inserted in the output // array, and (2) check if the current byte inside of itself can // be inserted, and (3) start a new current run // if (CurrentByte != 0x00) { // // Compute the final size of the current run // CurrentRunSize += RtlpBitsClearLow[CurrentByte]; // // Check if the current run be stored in the output array by either // there being room in the array or the last entry is smaller than // the current entry // if (CurrentRunSize > 0) { if ((RunIndex < SizeOfRunArray) || (RunArray[RunIndex-1].NumberOfBits < CurrentRunSize)) { // // If necessary increment the RunIndex and shift over the output // array until we find the slot where the new run belongs. We only // do the shifting if we're returning longest runs. // if (RunIndex < SizeOfRunArray) { RunIndex += 1; } for (j = RunIndex-2; LocateLongestRuns && (j >= 0) && (RunArray[j].NumberOfBits < CurrentRunSize); j -= 1) { RunArray[j+1] = RunArray[j]; } RunArray[j+1].NumberOfBits = CurrentRunSize; RunArray[j+1].StartingIndex = CurrentRunIndex; #if DBG if (NtfsDebugIt) { DbgPrint("%d: %08lx %08lx %08lx %08lx %08lx %08lx %08lx %08lx\n", __LINE__,RunIndex,CurrentRunSize,CurrentRunIndex,CurrentByteIndex,CurrentByte,j,RunArray[j+1].NumberOfBits,RunArray[j+1].StartingIndex); } #endif // // Now if the array is full and we are not doing longest runs return // to our caller // if (!LocateLongestRuns && (RunIndex >= SizeOfRunArray)) { return RunIndex; } } } // // The next run starts with the remaining clear bits in the // current byte. We set this up before we check inside the // current byte for a longer run, because the latter test // might require extra work. // CurrentRunSize = RtlpBitsClearHigh[ CurrentByte ]; CurrentRunIndex = (CurrentByteIndex * 8) + (8 - CurrentRunSize); // // Set the low and high bits, otherwise we'll wind up thinking that we have a // small run that needs to get added to the array, but these bits have // just been accounting for // CurrentByte |= FillMask[RtlpBitsClearLow[CurrentByte]] | ZeroMask[8-RtlpBitsClearHigh[CurrentByte]]; // // Check if the current byte contains a run inside of it that // should go into the output array. There may be multiple // runs in the byte that we need to insert. // while ((CurrentByte != 0xff) && ((RunIndex < SizeOfRunArray) || (RunArray[RunIndex-1].NumberOfBits < (ULONG)RtlpBitsClearAnywhere[CurrentByte]))) { TempNumber = RtlpBitsClearAnywhere[CurrentByte]; // // Somewhere in the current byte is a run to be inserted of // size TempNumber. All we need to do is find the index for this run. // BitMask = FillMask[ TempNumber ]; for (i = 0; (BitMask & CurrentByte) != 0; i += 1) { BitMask <<= 1; } // // If necessary increment the RunIndex and shift over the output // array until we find the slot where the new run belongs. We only // do the shifting if we're returning longest runs. // if (RunIndex < SizeOfRunArray) { RunIndex += 1; } for (j = RunIndex-2; LocateLongestRuns && (j >= 0) && (RunArray[j].NumberOfBits < TempNumber); j -= 1) { RunArray[j+1] = RunArray[j]; } RunArray[j+1].NumberOfBits = TempNumber; RunArray[j+1].StartingIndex = (CurrentByteIndex * 8) + i; #if DBG if (NtfsDebugIt) { DbgPrint("%d: %08lx %08lx %08lx %08lx %08lx %08lx %08lx %08lx\n", __LINE__,RunIndex,CurrentRunSize,CurrentRunIndex,CurrentByteIndex,CurrentByte,j,RunArray[j+1].NumberOfBits,RunArray[j+1].StartingIndex); } #endif // // Now if the array is full and we are not doing longest runs return // to our caller // if (!LocateLongestRuns && (RunIndex >= SizeOfRunArray)) { return RunIndex; } // // Mask out the bits and look for another run in the current byte // CurrentByte |= BitMask; } // // Otherwise the current byte is all zeros and // we simply continue with the current run // } else { CurrentRunSize += 8; } } #if DBG if (NtfsDebugIt) { DbgPrint("%d: %08lx %08lx %08lx %08lx %08lx\n",__LINE__,RunIndex,CurrentRunSize,CurrentRunIndex,CurrentByteIndex,CurrentByte); } #endif // // See if we finished looking over the bitmap with an open current // run that should be inserted in the output array // if (CurrentRunSize > 0) { if ((RunIndex < SizeOfRunArray) || (RunArray[RunIndex-1].NumberOfBits < CurrentRunSize)) { // // If necessary increment the RunIndex and shift over the output // array until we find the slot where the new run belongs. // if (RunIndex < SizeOfRunArray) { RunIndex += 1; } for (j = RunIndex-2; LocateLongestRuns && (j >= 0) && (RunArray[j].NumberOfBits < CurrentRunSize); j -= 1) { RunArray[j+1] = RunArray[j]; } RunArray[j+1].NumberOfBits = CurrentRunSize; RunArray[j+1].StartingIndex = CurrentRunIndex; #if DBG if (NtfsDebugIt) { DbgPrint("%d: %08lx %08lx %08lx %08lx %08lx %08lx %08lx %08lx\n", __LINE__,RunIndex,CurrentRunSize,CurrentRunIndex,CurrentByteIndex,CurrentByte,j,RunArray[j+1].NumberOfBits,RunArray[j+1].StartingIndex); } #endif } } // // Return to our caller // return RunIndex; }

ULONG RtlFindFirstRunClear (  IN PRTL_BITMAP  BitMapHeader, OUT PULONG  StartingIndex )

Definition at line 2117 of file rtl/bitmap.c. References BitMapHeader, and RtlFindNextForwardRunClear(). : This procedure finds the first contiguous range of clear bits within the specified bit map. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. StartingIndex - Receives the index (zero based) of the first run equal to the longest run of clear bits in the BitMap. Return Value: ULONG - Receives the number of bits contained in the first contiguous run of clear bits. --*/ { return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex); }

ULONG RtlFindLastBackwardRunClear (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  FromIndex, IN PULONG  StartingRunIndex )

Definition at line 2779 of file rtl/bitmap.c. References BitMapHeader, End, FillMaskUlong, RTL_PAGED_CODE, and Start. { ULONG Start; ULONG End; PULONG PHunk; ULONG Hunk; RTL_PAGED_CODE(); // // Take care of the boundary case of the null bitmap // if (BitMapHeader->SizeOfBitMap == 0) { *StartingRunIndex = FromIndex; return 0; } // // Scan backwards for the first clear bit // End = FromIndex; // // Build pointer to the ULONG word in the bitmap // containing the End bit, then read in the bitmap // hunk. Set the rest of the bits in this word, NOT // inclusive of the FromIndex bit. // PHunk = BitMapHeader->Buffer + (End / 32); Hunk = *PHunk | ~FillMaskUlong[(End % 32) + 1]; // // If the first subword is set then we can proceed to // take big steps in the bitmap since we are now ULONG // aligned in the search // if (Hunk == (ULONG)~0) { // // Adjust the pointers backwards // End -= (End % 32) + 1; PHunk--; while ( PHunk > BitMapHeader->Buffer ) { // // Stop at first word with set bits // if (*PHunk != (ULONG)~0) break; PHunk--; End -= 32; } } // // Bitwise search backward for the clear bit // while ((End != MAXULONG) && (RtlCheckBit( BitMapHeader, End ) == 1)) { End -= 1; } // // Scan backwards for the first set bit // Start = End; // // We know that the clear bit was in the last word we looked at, // so continue from there to find the next set bit, clearing the // previous bits in the word. // Hunk = *PHunk & FillMaskUlong[Start % 32]; // // If the subword is unset then we can proceed in big steps // if (Hunk == (ULONG)0) { // // Adjust the pointers backward // Start -= (Start % 32) + 1; PHunk--; while ( PHunk > BitMapHeader->Buffer ) { // // Stop at first word with set bits // if (*PHunk != (ULONG)0) break; PHunk--; Start -= 32; } } // // Bitwise search backward for the set bit // while ((Start != MAXULONG) && (RtlCheckBit( BitMapHeader, Start ) == 0)) { Start -= 1; } // // Compute the index and return the length // *StartingRunIndex = Start + 1; return (End - Start); }

CCHAR RtlFindLeastSignificantBit (  IN ULONGLONG  Set  )

Definition at line 2999 of file rtl/bitmap.c. References BM_0, BM_01, BM_0123, BM_2, BM_4, BM_45, BM_6, and RtlpBitsClearLow. : This procedure finds the least significant non-zero bit in Set and returns it's zero-based position. Arguments: Set - Supplies the 64-bit bitmap. Return Value: Set != 0: Bit position of the least significant non-zero bit in Set. Set == 0: -1. --*/ { UCHAR index; UCHAR bitOffset; UCHAR lookup; if ((Set & BM_0123) != 0) { if ((Set & BM_01) != 0) { if ((Set & BM_0) != 0) { bitOffset = 0 * 8; } else { bitOffset = 1 * 8; } } else { if ((Set & BM_2) != 0) { bitOffset = 2 * 8; } else { bitOffset = 3 * 8; } } } else { if ((Set & BM_45) != 0) { if ((Set & BM_4) != 0) { bitOffset = 4 * 8; } else { bitOffset = 5 * 8; } } else { if ((Set & BM_6) != 0) { bitOffset = 6 * 8; } else { // // The test for Set == 0 is postponed to here, it is expected // to be rare. Note that if we had our own version of // RtlpBitsClearHigh[] we could eliminate this test entirely, // reducing the average number of tests from 3.125 to 3. // if (Set == 0) { return -1; } bitOffset = 7 * 8; } } } lookup = (UCHAR)(Set >> bitOffset); index = RtlpBitsClearLow[lookup] + bitOffset; return index; }

ULONG RtlFindLongestRunClear (  IN PRTL_BITMAP  BitMapHeader, OUT PULONG  StartingIndex )

Definition at line 2071 of file rtl/bitmap.c. References BitMapHeader, RtlFindClearRuns(), and TRUE. : This procedure finds the largest contiguous range of clear bits within the specified bit map. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. StartingIndex - Receives the index (zero based) of the first run equal to the longest run of clear bits in the BitMap. Return Value: ULONG - Receives the number of bits contained in the largest contiguous run of clear bits. --*/ { RTL_BITMAP_RUN RunArray[1]; // // Locate the longest run in the bitmap. If there is one then // return that run otherwise return the error condition. // if (RtlFindClearRuns( BitMapHeader, RunArray, 1, TRUE ) == 1) { *StartingIndex = RunArray[0].StartingIndex; return RunArray[0].NumberOfBits; } *StartingIndex = 0; return 0; }

CCHAR RtlFindMostSignificantBit (  IN ULONGLONG  Set  )

Definition at line 2923 of file rtl/bitmap.c. References BM_1, BM_23, BM_3, BM_4567, BM_5, BM_67, BM_7, and RtlpBitsClearHigh. Referenced by NtAllocateVirtualMemory(), and NtMapViewOfSection(). : This procedure finds the most significant non-zero bit in Set and returns it's zero-based position. Arguments: Set - Supplies the 64-bit bitmap. Return Value: Set != 0: Bit position of the most significant set bit in Set. Set == 0: -1. --*/ { UCHAR index; UCHAR bitOffset; UCHAR lookup; if ((Set & BM_4567) != 0) { if ((Set & BM_67) != 0) { if ((Set & BM_7) != 0) { bitOffset = 7 * 8; } else { bitOffset = 6 * 8; } } else { if ((Set & BM_5) != 0) { bitOffset = 5 * 8; } else { bitOffset = 4 * 8; } } } else { if ((Set & BM_23) != 0) { if ((Set & BM_3) != 0) { bitOffset = 3 * 8; } else { bitOffset = 2 * 8; } } else { if ((Set & BM_1) != 0) { bitOffset = 1 * 8; } else { // // The test for Set == 0 is postponed to here, it is expected // to be rare. Note that if we had our own version of // RtlpBitsClearHigh[] we could eliminate this test entirely, // reducing the average number of tests from 3.125 to 3. // if (Set == 0) { return -1; } bitOffset = 0 * 8; } } } lookup = (UCHAR)(Set >> bitOffset); index = (7 - RtlpBitsClearHigh[lookup]) + bitOffset; return index; }

ULONG RtlFindNextForwardRunClear (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  FromIndex, IN PULONG  StartingRunIndex )

Definition at line 2635 of file rtl/bitmap.c. References BitMapHeader, End, FillMaskUlong, and Start. Referenced by RtlFindFirstRunClear(). { ULONG Start; ULONG End; PULONG PHunk, BitMapEnd; ULONG Hunk; // // Take care of the boundary case of the null bitmap // if (BitMapHeader->SizeOfBitMap == 0) { *StartingRunIndex = FromIndex; return 0; } // // Compute the last word address in the bitmap // BitMapEnd = BitMapHeader->Buffer + ((BitMapHeader->SizeOfBitMap - 1) / 32); // // Scan forward for the first clear bit // Start = FromIndex; // // Build pointer to the ULONG word in the bitmap // containing the Start bit // PHunk = BitMapHeader->Buffer + (Start / 32); // // If the first subword is set then we can proceed to // take big steps in the bitmap since we are now ULONG // aligned in the search. Make sure we aren't improperly // looking at the last word in the bitmap. // if (PHunk != BitMapEnd) { // // Read in the bitmap hunk. Set the previous bits in this word. // Hunk = *PHunk | FillMaskUlong[Start % 32]; if (Hunk == (ULONG)~0) { // // Adjust the pointers forward // Start += 32 - (Start % 32); PHunk++; while ( PHunk < BitMapEnd ) { // // Stop at first word with unset bits // if (*PHunk != (ULONG)~0) break; PHunk++; Start += 32; } } } // // Bitwise search forward for the clear bit // while ((Start < BitMapHeader->SizeOfBitMap) && (RtlCheckBit( BitMapHeader, Start ) == 1)) { Start += 1; } // // Scan forward for the first set bit // End = Start; // // If we aren't in the last word of the bitmap we may be // able to keep taking big steps // if (PHunk != BitMapEnd) { // // We know that the clear bit was in the last word we looked at, // so continue from there to find the next set bit, clearing the // previous bits in the word // Hunk = *PHunk & ~FillMaskUlong[End % 32]; if (Hunk == (ULONG)0) { // // Adjust the pointers forward // End += 32 - (End % 32); PHunk++; while ( PHunk < BitMapEnd ) { // // Stop at first word with set bits // if (*PHunk != (ULONG)0) break; PHunk++; End += 32; } } } // // Bitwise search forward for the set bit // while ((End < BitMapHeader->SizeOfBitMap) && (RtlCheckBit( BitMapHeader, End ) == 0)) { End += 1; } // // Compute the index and return the length // *StartingRunIndex = Start; return (End - Start); }

ULONG RtlFindSetBits (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  NumberToFind, IN ULONG  HintIndex )

Definition at line 866 of file rtl/bitmap.c. References BitMapHeader, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, RtlpBitSetAnywhere, RtlpBitsSetHigh, RtlpBitsSetLow, TRUE, and ZeroMask. Referenced by MiCleanPhysicalProcessPages(), NtAllocateUserPhysicalPages(), and RtlFindSetBitsAndClear(). : This procedure searches the specified bit map for the specified contiguous region of set bits. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. NumberToFind - Supplies the size of the contiguous region to find. HintIndex - Supplies the index (zero based) of where we should start the search from within the bitmap. Return Value: ULONG - Receives the starting index (zero based) of the contiguous region of set bits found. If such a region cannot be found then a -1 (i.e., 0xffffffff) is returned. --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG HintBit; ULONG MainLoopIndex; GET_BYTE_DECLARATIONS(); // // To make the loops in our test run faster we'll extract the // fields from the bitmap header // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // Set any unused bits in the last byte so we won't count them. We do // this by first checking if there is any odd bits in the last byte. // if ((SizeOfBitMap % 8) != 0) { // // The last byte has some odd bits so we'll set the high unused // bits in the last byte to 0's // ((PUCHAR)BitMapHeader->Buffer)[SizeInBytes - 1] &= FillMask[SizeOfBitMap % 8]; } // // Calculate from the hint index where the hint byte is and set ourselves // up to read the hint on the next call to GET_BYTE. To make the // algorithm run fast we'll only honor hints down to the byte level of // granularity. There is a possibility that we'll need to execute // our main logic twice. Once to test from the hint byte to the end of // the bitmap and the other to test from the start of the bitmap. First // we need to make sure the Hint Index is within range. // if (HintIndex >= SizeOfBitMap) { HintIndex = 0; } HintBit = HintIndex % 8; for (MainLoopIndex = 0; MainLoopIndex < 2; MainLoopIndex += 1) { ULONG StartByteIndex; ULONG EndByteIndex; UCHAR CurrentByte; // // Check for the first time through the main loop, which indicates // that we are going to start our search at our hint byte // if (MainLoopIndex == 0) { StartByteIndex = HintIndex / 8; EndByteIndex = SizeInBytes; // // This is the second time through the loop, make sure there is // actually something to check before the hint byte // } else if (HintIndex != 0) { // // The end index for the second time around is based on the // number of bits we need to find. We need to use this inorder // to take the case where the preceding byte to the hint byte // is the start of our run, and the run includes the hint byte // and some following bytes, based on the number of bits needed // The computation is to take the number of bits needed minus // 2 divided by 8 and then add 2. This will take in to account // the worst possible case where we have one bit hanging off // of each end byte, and all intervening bytes are all zero. // We only need to add one in the following equation because // HintByte is already counted. // if (NumberToFind < 2) { EndByteIndex = HintIndex / 8; } else { EndByteIndex = HintIndex / 8 + ((NumberToFind - 2) / 8) + 1; // // Make sure we don't overrun the end of the bitmap // if (EndByteIndex > SizeInBytes) { EndByteIndex = SizeInBytes; } } StartByteIndex = 0; HintIndex = 0; HintBit = 0; // // Otherwise we already did a complete loop through the bitmap // so we should simply return -1 to say nothing was found // } else { return 0xffffffff; } // // Set ourselves up to get the next byte // GET_BYTE_INITIALIZATION(BitMapHeader, StartByteIndex); // // Get the first byte, and clear any bits before the hint bit. // GET_BYTE( CurrentByte ); CurrentByte &= ZeroMask[HintBit]; // // If the number of bits can only fit in 1 or 2 bytes (i.e., 9 bits or // less) we do the following test case. // if (NumberToFind <= 9) { ULONG CurrentBitIndex; UCHAR PreviousByte; PreviousByte = 0x00; // // Examine all the bytes within our test range searching // for a fit // CurrentBitIndex = StartByteIndex * 8; while (TRUE) { // // Check to see if the current byte coupled with the previous // byte will satisfy the requirement. The check uses the high // part of the previous byte and low part of the current byte. // if (((ULONG)RtlpBitsSetHigh(PreviousByte) + (ULONG)RtlpBitsSetLow(CurrentByte)) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these two bytes, so we can compute // the starting index. This is done by taking the // index of the current byte (bit 0) and subtracting the // number of bits its takes to get to the first set // high bit. // StartingIndex = CurrentBitIndex - (LONG)RtlpBitsSetHigh(PreviousByte); // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // The previous byte does not help, so check the current byte. // if ((ULONG)RtlpBitSetAnywhere(CurrentByte) >= NumberToFind) { UCHAR BitMask; ULONG i; // // It all fits in a single byte, so calculate the bit // number. We do this by taking a mask of the appropriate // size and shifting it over until it fits. It fits when // we can bitwise-and the current byte with the bit mask // and get back the bit mask. // BitMask = FillMask[ NumberToFind ]; for (i = 0; (BitMask & CurrentByte) != BitMask; i += 1) { BitMask <<= 1; } // // return to our caller the located bit index, and the // number that we found. // return CurrentBitIndex + i; } // // For the next iteration through our loop we need to make // the current byte into the previous byte, and go to the // top of the loop again. // PreviousByte = CurrentByte; // // Increment our Bit Index, and either exit, or get the // next byte. // CurrentBitIndex += 8; if ( CurrentBitIndex < EndByteIndex * 8 ) { GET_BYTE( CurrentByte ); } else { break; } } // end loop CurrentBitIndex // // The number to find is greater than 9 but if it is less than 15 // then we know it can be satisfied with at most 2 bytes, or 3 bytes // if the middle byte (of the 3) is all ones. // } else if (NumberToFind < 15) { ULONG CurrentBitIndex; UCHAR PreviousPreviousByte; UCHAR PreviousByte; PreviousByte = 0x00; // // Examine all the bytes within our test range searching // for a fit // CurrentBitIndex = StartByteIndex * 8; while (TRUE) { // // For the next iteration through our loop we need to make // the current byte into the previous byte, the previous // byte into the previous previous byte, and go to the // top of the loop again. // PreviousPreviousByte = PreviousByte; PreviousByte = CurrentByte; // // Increment our Bit Index, and either exit, or get the // next byte. // CurrentBitIndex += 8; if ( CurrentBitIndex < EndByteIndex * 8 ) { GET_BYTE( CurrentByte ); } else { break; } // // if the previous byte is all ones then maybe the // request can be satisfied using the Previous Previous Byte // Previous Byte, and the Current Byte. // if ((PreviousByte == 0xff) && (((ULONG)RtlpBitsSetHigh(PreviousPreviousByte) + 8 + (ULONG)RtlpBitsSetLow(CurrentByte)) >= NumberToFind)) { ULONG StartingIndex; // // It all fits in these three bytes, so we can compute // the starting index. This is done by taking the // index of the previous byte (bit 0) and subtracting // the number of bits its takes to get to the first // set high bit. // StartingIndex = (CurrentBitIndex - 8) - (LONG)RtlpBitsSetHigh(PreviousPreviousByte); // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // Check to see if the Previous byte and current byte // together satisfy the request. // if (((ULONG)RtlpBitsSetHigh(PreviousByte) + (ULONG)RtlpBitsSetLow(CurrentByte)) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these two bytes, so we can compute // the starting index. This is done by taking the // index of the current byte (bit 0) and subtracting the // number of bits its takes to get to the first set // high bit. // StartingIndex = CurrentBitIndex - (LONG)RtlpBitsSetHigh(PreviousByte); // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } } // end loop CurrentBitIndex // // The number to find is greater than or equal to 15. This request // has to have at least one byte of all ones to be satisfied // } else { ULONG CurrentByteIndex; ULONG OneBytesNeeded; ULONG OneBytesFound; UCHAR StartOfRunByte; LONG StartOfRunIndex; // // First precalculate how many one bytes we're going to need // OneBytesNeeded = (NumberToFind - 7) / 8; // // Indicate for the first time through our loop that we haven't // found a one byte yet, and indicate that the start of the // run is the byte just before the start byte index // OneBytesFound = 0; StartOfRunByte = 0x00; StartOfRunIndex = StartByteIndex - 1; // // Examine all the bytes in our test range searching for a fit // CurrentByteIndex = StartByteIndex; while (TRUE) { // // If the number of zero bytes fits our minimum requirements // then we can do the additional test to see if we // actually found a fit // if ((OneBytesFound >= OneBytesNeeded) && ((ULONG)RtlpBitsSetHigh(StartOfRunByte) + OneBytesFound*8 + (ULONG)RtlpBitsSetLow(CurrentByte)) >= NumberToFind) { ULONG StartingIndex; // // It all fits in these bytes, so we can compute // the starting index. This is done by taking the // StartOfRunIndex times 8 and adding the number of bits // it takes to get to the first set high bit. // StartingIndex = (StartOfRunIndex * 8) + (8 - (LONG)RtlpBitsSetHigh(StartOfRunByte)); // // Now make sure the total size isn't beyond the bitmap // if ((StartingIndex + NumberToFind) <= SizeOfBitMap) { return StartingIndex; } } // // Check to see if the byte is all ones and increment // the number of one bytes found // if (CurrentByte == 0xff) { OneBytesFound += 1; // // The byte isn't all ones so we need to start over again // looking for one bytes. // } else { OneBytesFound = 0; StartOfRunByte = CurrentByte; StartOfRunIndex = CurrentByteIndex; } // // Increment our Byte Index, and either exit, or get the // next byte. // CurrentByteIndex += 1; if ( CurrentByteIndex < EndByteIndex ) { GET_BYTE( CurrentByte ); } else { break; } } // end loop CurrentByteIndex } } // // We never found a fit so we'll return -1 // return 0xffffffff; }

ULONG RtlFindSetBitsAndClear (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  NumberToFind, IN ULONG  HintIndex )

Definition at line 1448 of file rtl/bitmap.c. References BitMapHeader, RtlClearBits(), and RtlFindSetBits(). Referenced by DoBitMapTest(). : This procedure searches the specified bit map for the specified contiguous region of set bits, clears the bits and returns the number of bits found and the starting bit number which was set then clear. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap. NumberToFind - Supplies the size of the contiguous region to find. HintIndex - Supplies the index (zero based) of where we should start the search from within the bitmap. Return Value: ULONG - Receives the starting index (zero based) of the contiguous region found. If such a region cannot be located a -1 (i.e., 0xffffffff) is returned. --*/ { ULONG StartingIndex; // // First look for a run of set bits that equals the size requested // if ((StartingIndex = RtlFindSetBits( BitMapHeader, NumberToFind, HintIndex )) != 0xffffffff) { // // We found a large enough run of set bits so now clear them // RtlClearBits( BitMapHeader, StartingIndex, NumberToFind ); } // // And return to our caller // return StartingIndex; }

VOID RtlInitializeBitMap (  IN PRTL_BITMAP  BitMapHeader, IN PULONG  BitMapBuffer, IN ULONG  SizeOfBitMap )

Definition at line 219 of file rtl/bitmap.c. References BitMapHeader, and RTL_PAGED_CODE. Referenced by DoBitMapTest(), HvInitializeHive(), HvpAddBin(), HvpBuildMapAndCopy(), HvpInitMap(), HvpRecoverData(), LdrpInitializeProcess(), main(), NtAllocateUserPhysicalPages(), NtAllocateVirtualMemory(), SetHandleFlag(), and UserDeleteW32Process(). : This procedure initializes a bit map. Arguments: BitMapHeader - Supplies a pointer to the BitMap Header to initialize BitMapBuffer - Supplies a pointer to the buffer that is to serve as the BitMap. This must be an a multiple number of longwords in size. SizeOfBitMap - Supplies the number of bits required in the Bit Map. Return Value: None. --*/ { RTL_PAGED_CODE(); // // Initialize the BitMap header. // BitMapHeader->SizeOfBitMap = SizeOfBitMap; BitMapHeader->Buffer = BitMapBuffer; // // And return to our caller // //DbgPrint("InitializeBitMap"); DumpBitMap(BitMapHeader); return; }

ULONG RtlNumberOfClearBits (  IN PRTL_BITMAP  BitMapHeader  )

Definition at line 2149 of file rtl/bitmap.c. References BitMapHeader, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, RtlpBitsClearTotal, and ZeroMask. Referenced by main(). : This procedure counts and returns the number of clears bits within the specified bitmap. Arguments: BitMapHeader - Supplies a pointer to the previously initialized bitmap. Return Value: ULONG - The total number of clear bits in the bitmap --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG i; UCHAR CurrentByte; ULONG TotalClear; GET_BYTE_DECLARATIONS(); // // Reference the bitmap header to make the loop run faster // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // Set any unused bits in the last byte so we don't count them. We // do this by first checking if there are any odd bits in the last byte // if ((SizeOfBitMap % 8) != 0) { // // The last byte has some odd bits so we'll set the high unused // bits in the last byte to 1's // ((PUCHAR)BitMapHeader->Buffer)[SizeInBytes - 1] |= ZeroMask[SizeOfBitMap % 8]; } // // Set if up so we can use the GET_BYTE macro // GET_BYTE_INITIALIZATION( BitMapHeader, 0 ); // // Examine every byte in the bitmap // TotalClear = 0; for (i = 0; i < SizeInBytes; i += 1) { GET_BYTE( CurrentByte ); TotalClear += RtlpBitsClearTotal[CurrentByte]; } return TotalClear; }

ULONG RtlNumberOfSetBits (  IN PRTL_BITMAP  BitMapHeader  )

Definition at line 2227 of file rtl/bitmap.c. References BitMapHeader, FillMask, GET_BYTE, GET_BYTE_DECLARATIONS, GET_BYTE_INITIALIZATION, and RtlpBitsSetTotal. Referenced by CmpInitializeHiveList(), HvFreeHivePartial(), HvMarkCellDirty(), HvMarkClean(), HvMarkDirty(), HvpAddBin(), HvpDoWriteHive(), HvpGrowLog1(), HvpGrowLog2(), HvpRecoverData(), HvpWriteLog(), IopCreateSummaryDump(), IopWriteSummaryDump(), and main(). : This procedure counts and returns the number of set bits within the specified bitmap. Arguments: BitMapHeader - Supplies a pointer to the previously initialized bitmap. Return Value: ULONG - The total number of set bits in the bitmap --*/ { ULONG SizeOfBitMap; ULONG SizeInBytes; ULONG i; UCHAR CurrentByte; ULONG TotalSet; GET_BYTE_DECLARATIONS(); // // Reference the bitmap header to make the loop run faster // SizeOfBitMap = BitMapHeader->SizeOfBitMap; SizeInBytes = (SizeOfBitMap + 7) / 8; // // Clear any unused bits in the last byte so we don't count them. We // do this by first checking if there are any odd bits in the last byte // if ((SizeOfBitMap % 8) != 0) { // // The last byte has some odd bits so we'll set the high unused // bits in the last byte to 0's // ((PUCHAR)BitMapHeader->Buffer)[SizeInBytes - 1] &= FillMask[SizeOfBitMap % 8]; } // // Set if up so we can use the GET_BYTE macro // GET_BYTE_INITIALIZATION( BitMapHeader, 0 ); // // Examine every byte in the bitmap // TotalSet = 0; for (i = 0; i < SizeInBytes; i += 1) { GET_BYTE( CurrentByte ); TotalSet += RtlpBitsSetTotal(CurrentByte); } return TotalSet; }

VOID RtlSetAllBits (  IN PRTL_BITMAP  BitMapHeader  )

Definition at line 305 of file rtl/bitmap.c. References BitMapHeader. Referenced by DoBitMapTest(), HvInitializeHive(), HvWriteHive(), main(), MiBuildPagedPool(), MiExtendPagingFileMaximum(), MiInitializeSessionPool(), and NtCreatePagingFile(). : This procedure sets all bits in the specified Bit Map. Arguments: BitMapHeader - Supplies a pointer to the previously initialized BitMap Return Value: None. --*/ { // // Set all the bits // RtlFillMemoryUlong( BitMapHeader->Buffer, ((BitMapHeader->SizeOfBitMap + 31) / 32) * 4, 0xffffffff ); // // And return to our caller // //DbgPrint("SetAllBits"); DumpBitMap(BitMapHeader); return; }

VOID RtlSetBits (  IN PRTL_BITMAP  BitMapHeader, IN ULONG  StartingIndex, IN ULONG  NumberToSet )

Definition at line 1634 of file rtl/bitmap.c. References ASSERT, BitMapHeader, LeftShiftUlong, and RightShiftUlong. Referenced by CmpInitializeHiveList(), DoBitMapTest(), HvMarkDirty(), IopAddPageToPageMap(), main(), MiAllocatePoolPages(), MiAttemptPageFileReduction(), MiCheckForCrashDump(), NtAllocateUserPhysicalPages(), RtlFindClearBitsAndSet(), and SetHandleFlag(). : This procedure sets the specified range of bits within the specified bit map. Arguments: BitMapHeader - Supplies a pointer to the previously initialied BitMap. StartingIndex - Supplies the index (zero based) of the first bit to set. NumberToSet - Supplies the number of bits to set. Return Value: None. --*/ { ULONG BitOffset; PULONG CurrentLong; //DbgPrint("SetBits %08lx, ", NumberToSet); //DbgPrint("%08lx", StartingIndex); ASSERT( StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap ); // // Special case the situation where the number of bits to set is // zero. Turn this into a noop. // if (NumberToSet == 0) { return; } BitOffset = StartingIndex % 32; // // Get a pointer to the first longword that needs to be set // CurrentLong = &BitMapHeader->Buffer[ StartingIndex / 32 ]; // // Check if we can only need to set one longword. // if ((BitOffset + NumberToSet) <= 32) { // // To build a mask of bits to set we shift left to get the number // of bits we're setting and then shift right to put it in position. // We'll typecast the right shift to ULONG to make sure it doesn't // do a sign extend. // *CurrentLong |= LeftShiftUlong(RightShiftUlong(((ULONG)0xFFFFFFFF),(32 - NumberToSet)), BitOffset); // // And return to our caller // //DumpBitMap(BitMapHeader); return; } // // We can set bits out to the end of the first longword so we'll // do that right now. // *CurrentLong |= LeftShiftUlong(0xFFFFFFFF, BitOffset); // // And indicate what the next longword to set is and how many // bits are left to set // CurrentLong += 1; NumberToSet -= 32 - BitOffset; // // The bit position is now long aligned, so we can continue // setting longwords until the number to set is less than 32 // while (NumberToSet >= 32) { *CurrentLong = 0xffffffff; CurrentLong += 1; NumberToSet -= 32; } // // And now we can set the remaining bits, if there are any, in the // last longword // if (NumberToSet > 0) { *CurrentLong |= ~LeftShiftUlong(0xFFFFFFFF, NumberToSet); } // // And return to our caller // //DumpBitMap(BitMapHeader); return; }

---

Variable Documentation

CONST UCHAR FillMask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF } [static]

Definition at line 213 of file rtl/bitmap.c. Referenced by RtlAreBitsClear(), RtlAreBitsSet(), RtlFindClearBits(), RtlFindClearRuns(), RtlFindSetBits(), and RtlNumberOfSetBits().

CONST ULONG FillMaskUlong[] [static]

Initial value: { 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff } Definition at line 2621 of file rtl/bitmap.c. Referenced by RtlFindLastBackwardRunClear(), and RtlFindNextForwardRunClear().

CONST CCHAR RtlpBitsClearAnywhere[]

Initial value: { 8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4, 4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, 5,4,3,3,2,2,2,2,3,2,2,2,2,2,2,2, 4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2, 6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2, 4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1, 5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1, 4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1, 7,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3, 4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2, 5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1, 4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1, 6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2, 4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1, 5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1, 4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,0 } Definition at line 122 of file rtl/bitmap.c. Referenced by RtlFindClearBits(), and RtlFindClearRuns().

CONST CCHAR RtlpBitsClearHigh[]

Initial value: { 8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4, 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 } Definition at line 168 of file rtl/bitmap.c. Referenced by RtlFindClearBits(), RtlFindClearRuns(), and RtlFindMostSignificantBit().

CONST CCHAR RtlpBitsClearLow[]

Initial value: { 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 } Definition at line 145 of file rtl/bitmap.c. Referenced by RtlFindClearBits(), RtlFindClearRuns(), and RtlFindLeastSignificantBit().

CONST CCHAR RtlpBitsClearTotal[]

Initial value: { 8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4, 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3, 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1, 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1, 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2, 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1, 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1, 4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0 } Definition at line 190 of file rtl/bitmap.c. Referenced by RtlNumberOfClearBits().

CONST UCHAR ZeroMask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xf0, 0xe0, 0xc0, 0x80, 0x00 } [static]

Definition at line 215 of file rtl/bitmap.c. Referenced by RtlAreBitsClear(), RtlAreBitsSet(), RtlFindClearBits(), RtlFindClearRuns(), RtlFindSetBits(), and RtlNumberOfClearBits().

---