You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
3192 lines
82 KiB
3192 lines
82 KiB
/*++
|
|
|
|
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
|
|
VOID
|
|
DumpBitMap (
|
|
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 };
|
|
|
|
|
|
VOID
|
|
RtlInitializeBitMap (
|
|
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;
|
|
}
|
|
|
|
|
|
VOID
|
|
RtlClearBit (
|
|
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;
|
|
}
|
|
|
|
VOID
|
|
RtlSetBit (
|
|
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;
|
|
}
|
|
|
|
BOOLEAN
|
|
RtlTestBit (
|
|
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);
|
|
}
|
|
|
|
VOID
|
|
RtlClearAllBits (
|
|
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;
|
|
}
|
|
|
|
|
|
VOID
|
|
RtlSetAllBits (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindClearBits (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindSetBits (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindClearBitsAndSet (
|
|
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;
|
|
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindSetBitsAndClear (
|
|
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;
|
|
}
|
|
|
|
|
|
VOID
|
|
RtlClearBits (
|
|
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;
|
|
}
|
|
|
|
VOID
|
|
RtlSetBits (
|
|
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
|
|
|
|
ULONG
|
|
RtlFindClearRuns (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindLongestRunClear (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindFirstRunClear (
|
|
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);
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlNumberOfClearBits (
|
|
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;
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlNumberOfSetBits (
|
|
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;
|
|
}
|
|
|
|
|
|
BOOLEAN
|
|
RtlAreBitsClear (
|
|
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;
|
|
}
|
|
|
|
|
|
BOOLEAN
|
|
RtlAreBitsSet (
|
|
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
|
|
};
|
|
|
|
|
|
ULONG
|
|
RtlFindNextForwardRunClear (
|
|
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);
|
|
}
|
|
|
|
|
|
ULONG
|
|
RtlFindLastBackwardRunClear (
|
|
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
|
|
|
|
CCHAR
|
|
RtlFindMostSignificantBit (
|
|
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.
|
|
|
|
--*/
|
|
{
|
|
|
|
#if defined(_AMD64_)
|
|
|
|
ULONG bitOffset;
|
|
|
|
if (BitScanReverse64(&bitOffset, Set)) {
|
|
return (CCHAR)bitOffset;
|
|
|
|
} else {
|
|
return -1;
|
|
}
|
|
|
|
#else
|
|
|
|
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;
|
|
|
|
#endif
|
|
|
|
}
|
|
|
|
CCHAR
|
|
RtlFindLeastSignificantBit (
|
|
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.
|
|
|
|
--*/
|
|
{
|
|
|
|
#if defined(_AMD64_)
|
|
|
|
ULONG bitOffset;
|
|
|
|
if (BitScanForward64(&bitOffset, Set)) {
|
|
return (CCHAR)bitOffset;
|
|
|
|
} else {
|
|
return -1;
|
|
}
|
|
|
|
#else
|
|
|
|
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;
|
|
|
|
#endif
|
|
|
|
}
|