|
|
/*++
Copyright (c) 1989 Microsoft Corporation
Module Name:
BitMap.c
Abstract:
Implementation of the bit map routines for the NT rtl.
Bit numbers within the bit map are zero based. The first is numbered zero.
The bit map routines keep track of the number of bits clear or set by subtracting or adding the number of bits operated on as bit ranges are cleared or set; individual bit states are not tested. This means that if a range of bits is set, it is assumed that the total range is currently clear.
Author:
Gary Kimura (GaryKi) & Lou Perazzoli (LouP) 29-Jan-1990
Revision History:
--*/
#include "ntrtlp.h"
#if defined(ALLOC_PRAGMA) && defined(NTOS_KERNEL_RUNTIME)
#pragma alloc_text(PAGE,RtlInitializeBitMap)
#endif
#define RightShiftUlong(E1,E2) ((E2) < 32 ? (E1) >> (E2) : 0)
#define LeftShiftUlong(E1,E2) ((E2) < 32 ? (E1) << (E2) : 0)
#if DBG
VOIDDumpBitMap ( PRTL_BITMAP BitMap ){ ULONG i; BOOLEAN AllZeros, AllOnes;
DbgPrint(" BitMap:%08lx", BitMap);
DbgPrint(" (%08x)", BitMap->SizeOfBitMap); DbgPrint(" %08lx\n", BitMap->Buffer);
AllZeros = FALSE; AllOnes = FALSE;
for (i = 0; i < ((BitMap->SizeOfBitMap + 31) / 32); i += 1) {
if (BitMap->Buffer[i] == 0) {
if (AllZeros) {
NOTHING;
} else {
DbgPrint("%4d:", i); DbgPrint(" %08lx\n", BitMap->Buffer[i]); }
AllZeros = TRUE; AllOnes = FALSE;
} else if (BitMap->Buffer[i] == 0xFFFFFFFF) {
if (AllOnes) {
NOTHING;
} else {
DbgPrint("%4d:", i); DbgPrint(" %08lx\n", BitMap->Buffer[i]); }
AllZeros = FALSE; AllOnes = TRUE;
} else {
AllZeros = FALSE; AllOnes = FALSE;
DbgPrint("%4d:", i); DbgPrint(" %08lx\n", BitMap->Buffer[i]); } }}#endif
//
// There are three macros to make reading the bytes in a bitmap easier.
//
#define GET_BYTE_DECLARATIONS() \
PUCHAR _CURRENT_POSITION;
#define GET_BYTE_INITIALIZATION(RTL_BITMAP,BYTE_INDEX) { \
_CURRENT_POSITION = &((PUCHAR)((RTL_BITMAP)->Buffer))[BYTE_INDEX]; \}
#define GET_BYTE(THIS_BYTE) ( \
THIS_BYTE = *(_CURRENT_POSITION++) \)
//
// Lookup table that tells how many contiguous bits are clear (i.e., 0) in
// a byte
//
CONST CCHAR RtlpBitsClearAnywhere[] = { 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 };
//
// Lookup table that tells how many contiguous LOW order bits are clear
// (i.e., 0) in a byte
//
CONST CCHAR RtlpBitsClearLow[] = { 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 };
//
// Lookup table that tells how many contiguous HIGH order bits are clear
// (i.e., 0) in a byte
//
CONST CCHAR RtlpBitsClearHigh[] = { 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 };
//
// Lookup table that tells how many clear bits (i.e., 0) there are in a byte
//
CONST CCHAR RtlpBitsClearTotal[] = { 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 };
//
// Bit Mask for clearing and setting bits within bytes. FillMask[i] has the first
// i bits set to 1. ZeroMask[i] has the first i bits set to zero.
//
static CONST UCHAR FillMask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF };
static CONST UCHAR ZeroMask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xf0, 0xe0, 0xc0, 0x80, 0x00 };
VOIDRtlInitializeBitMap ( IN PRTL_BITMAP BitMapHeader, IN PULONG BitMapBuffer, IN ULONG SizeOfBitMap )
/*++
Routine Description:
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;}
VOIDRtlClearBit ( IN PRTL_BITMAP BitMapHeader, IN ULONG BitNumber )
/*++
Routine Description:
This procedure clears a single bit in the specified bit map.
Arguments:
BitMapHeader - Supplies a pointer to the previously initialized bit map.
BitNumber - Supplies the number of the bit to be cleared in the bit map.
Return Value:
None.
--*/
{
PCHAR ByteAddress; ULONG ShiftCount;
ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
ByteAddress = (PCHAR)BitMapHeader->Buffer + (BitNumber >> 3); ShiftCount = BitNumber & 0x7; *ByteAddress &= (CHAR)(~(1 << ShiftCount)); return;} VOIDRtlSetBit ( IN PRTL_BITMAP BitMapHeader, IN ULONG BitNumber )
/*++
Routine Description:
This procedure sets a single bit in the specified bit map.
Arguments:
BitMapHeader - Supplies a pointer to the previously initialized bit map.
BitNumber - Supplies the number of the bit to be set in the bit map.
Return Value:
None.
--*/
{
PCHAR ByteAddress; ULONG ShiftCount;
ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
ByteAddress = (PCHAR)BitMapHeader->Buffer + (BitNumber >> 3); ShiftCount = BitNumber & 0x7; *ByteAddress |= (CHAR)(1 << ShiftCount); return;} BOOLEANRtlTestBit ( IN PRTL_BITMAP BitMapHeader, IN ULONG BitNumber )
/*++
Routine Description:
This procedure tests the state of a single bit in the specified bit map.
Arguments:
BitMapHeader - Supplies a pointer to the previously initialized bit map.
BitNumber - Supplies the number of the bit to be tested in the bit map.
Return Value:
The state of the specified bit is returned as the function value.
--*/
{
PCHAR ByteAddress; ULONG ShiftCount;
ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
ByteAddress = (PCHAR)BitMapHeader->Buffer + (BitNumber >> 3); ShiftCount = BitNumber & 0x7; return (BOOLEAN)((*ByteAddress >> ShiftCount) & 1);} VOIDRtlClearAllBits ( IN PRTL_BITMAP BitMapHeader )
/*++
Routine Description:
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;}
VOIDRtlSetAllBits ( IN PRTL_BITMAP BitMapHeader )
/*++
Routine Description:
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;}
ULONGRtlFindClearBits ( IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex )
/*++
Routine Description:
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 + 7) / 8;
} else {
EndByteIndex = (HintIndex + 7) / 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 - 1)
&&
((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;}
ULONGRtlFindSetBits ( IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex )
/*++
Routine Description:
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 + 7) / 8;
} else {
EndByteIndex = (HintIndex + 7) / 8 + ((NumberToFind - 2) / 8) + 2;
//
// 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 - 1)
&&
((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;}
ULONGRtlFindClearBitsAndSet ( IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex )
/*++
Routine Description:
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;
}
ULONGRtlFindSetBitsAndClear ( IN PRTL_BITMAP BitMapHeader, IN ULONG NumberToFind, IN ULONG HintIndex )
/*++
Routine Description:
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;}
VOIDRtlClearBits ( IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG NumberToClear )
/*++
Routine Description:
This procedure clears the specified range of bits within the specified bit map.
Arguments:
BitMapHeader - Supplies a pointer to the previously initialized Bit Map.
StartingIndex - Supplies the index (zero based) of the first bit to clear.
NumberToClear - Supplies the number of bits to clear.
Return Value:
None.
--*/
{ PCHAR CurrentByte; ULONG BitOffset;
//DbgPrint("ClearBits %08lx, ", NumberToClear);
//DbgPrint("%08lx", StartingIndex);
ASSERT( StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap );
//
// Special case the situation where the number of bits to clear is
// zero. Turn this into a noop.
//
if (NumberToClear == 0) {
return; }
//
// Get a pointer to the first byte that needs to be cleared.
//
CurrentByte = ((PCHAR) BitMapHeader->Buffer) + (StartingIndex / 8);
//
// If all the bit's we're setting are in the same byte just do it and
// get out.
//
BitOffset = StartingIndex % 8; if ((BitOffset + NumberToClear) <= 8) {
*CurrentByte &= ~(FillMask[ NumberToClear ] << BitOffset);
} else {
//
// Do the first byte manually because the first bit may not be byte aligned.
//
// Note: The first longword will always be cleared byte wise to simplify the
// logic of checking for short copies (<32 bits).
//
if (BitOffset > 0) {
*CurrentByte &= FillMask[ BitOffset ]; CurrentByte += 1; NumberToClear -= 8 - BitOffset;
}
//
// Fill the full bytes in the middle. Use the RtlZeroMemory() because its
// going to be hand tuned asm code spit out by the compiler.
//
if (NumberToClear > 8) {
RtlZeroMemory( CurrentByte, NumberToClear / 8 ); CurrentByte += NumberToClear / 8; NumberToClear %= 8;
}
//
// Clear the remaining bits, if there are any, in the last byte.
//
if (NumberToClear > 0) {
*CurrentByte &= ZeroMask[ NumberToClear ];
}
}
//
// And return to our caller
//
//DumpBitMap(BitMapHeader);
return;} VOIDRtlSetBits ( IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG NumberToSet )
/*++
Routine Description:
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.
--*/{ PCHAR CurrentByte; ULONG BitOffset;
//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; }
//
// Get a pointer to the first byte that needs to be set.
//
CurrentByte = ((PCHAR) BitMapHeader->Buffer) + (StartingIndex / 8);
//
// If all the bit's we're setting are in the same byte just do it and
// get out.
//
BitOffset = StartingIndex % 8; if ((BitOffset + NumberToSet) <= 8) {
*CurrentByte |= (FillMask[ NumberToSet ] << BitOffset);
} else {
//
// Do the first byte manually because the first bit may not be byte aligned.
//
// Note: The first longword will always be set byte wise to simplify the
// logic of checking for short copies (<32 bits).
//
if (BitOffset > 0) {
*CurrentByte |= ZeroMask[ BitOffset ]; CurrentByte += 1; NumberToSet -= 8 - BitOffset;
}
//
// Fill the full bytes in the middle. Use the RtlFillMemory() because its
// going to be hand tuned asm code spit out by the compiler.
//
if (NumberToSet > 8) {
RtlFillMemory( CurrentByte, NumberToSet / 8, 0xff ); CurrentByte += NumberToSet / 8; NumberToSet %= 8;
}
//
// Set the remaining bits, if there are any, in the last byte.
//
if (NumberToSet > 0) {
*CurrentByte |= FillMask[ NumberToSet ];
}
}
//
// And return to our caller
//
//DumpBitMap(BitMapHeader);
return;}
#if DBG
BOOLEAN NtfsDebugIt = FALSE;#endif
ULONGRtlFindClearRuns ( IN PRTL_BITMAP BitMapHeader, PRTL_BITMAP_RUN RunArray, ULONG SizeOfRunArray, BOOLEAN LocateLongestRuns )
/*++
Routine Description:
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;}
ULONGRtlFindLongestRunClear ( IN PRTL_BITMAP BitMapHeader, OUT PULONG StartingIndex )
/*++
Routine Description:
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;}
ULONGRtlFindFirstRunClear ( IN PRTL_BITMAP BitMapHeader, OUT PULONG StartingIndex )
/*++
Routine Description:
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);}
ULONGRtlNumberOfClearBits ( IN PRTL_BITMAP BitMapHeader )
/*++
Routine Description:
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;}
ULONGRtlNumberOfSetBits ( IN PRTL_BITMAP BitMapHeader )
/*++
Routine Description:
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;}
BOOLEANRtlAreBitsClear ( IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG Length )
/*++
Routine Description:
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;}
BOOLEANRtlAreBitsSet ( IN PRTL_BITMAP BitMapHeader, IN ULONG StartingIndex, IN ULONG Length )
/*++
Routine Description:
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;}
static CONST ULONG FillMaskUlong[] = { 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};
ULONGRtlFindNextForwardRunClear ( IN PRTL_BITMAP BitMapHeader, IN ULONG FromIndex, IN PULONG StartingRunIndex ){ 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);}
ULONGRtlFindLastBackwardRunClear ( IN PRTL_BITMAP BitMapHeader, IN ULONG FromIndex, IN PULONG StartingRunIndex ){ 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);}
#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
CCHARRtlFindMostSignificantBit ( IN ULONGLONG Set )/*++
Routine Description:
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;}
CCHARRtlFindLeastSignificantBit ( IN ULONGLONG Set )/*++
Routine Description:
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;}
|
