/*
- * COPYRIGHT: See COPYING in the top level directory
* PROJECT: ReactOS system libraries
+ * LICENSE: GNU GPL - See COPYING in the top level directory
+ * BSD - See COPYING.ARM in the top level directory
* FILE: lib/rtl/bitmap.c
* PURPOSE: Bitmap functions
* PROGRAMMER: Timo Kreuzer (timo.kreuzer@reactos.org)
#define NDEBUG
#include <debug.h>
+// FIXME: hack
+#undef ASSERT
+#define ASSERT(...)
+
+#ifdef USE_RTL_BITMAP64
+#define _BITCOUNT 64
+#define MAXINDEX 0xFFFFFFFFFFFFFFFF
+typedef ULONG64 BITMAP_INDEX, *PBITMAP_INDEX;
+typedef ULONG64 BITMAP_BUFFER, *PBITMAP_BUFFER;
+#define RTL_BITMAP RTL_BITMAP64
+#define PRTL_BITMAP PRTL_BITMAP64
+#define RTL_BITMAP_RUN RTL_BITMAP_RUN64
+#define PRTL_BITMAP_RUN PRTL_BITMAP_RUN64
+#undef BitScanForward
+#define BitScanForward(Index, Mask) \
+ do { unsigned long tmp; BitScanForward64(&tmp, Mask); *Index = tmp; } while (0)
+#undef BitScanReverse
+#define BitScanReverse(Index, Mask) \
+ do { unsigned long tmp; BitScanReverse64(&tmp, Mask); *Index = tmp; } while (0)
+#define RtlFillMemoryUlong RtlFillMemoryUlonglong
+
+#define RtlInitializeBitMap RtlInitializeBitMap64
+#define RtlClearAllBits RtlClearAllBits64
+#define RtlSetAllBits RtlSetAllBits64
+#define RtlClearBit RtlClearBit64
+#define RtlSetBit RtlSetBit64
+#define RtlClearBits RtlClearBits64
+#define RtlSetBits RtlSetBits64
+#define RtlTestBit RtlTestBit64
+#define RtlAreBitsClear RtlAreBitsClear64
+#define RtlAreBitsSet RtlAreBitsSet64
+#define RtlNumberOfSetBits RtlNumberOfSetBits64
+#define RtlNumberOfClearBits RtlNumberOfClearBits64
+#define RtlFindClearBits RtlFindClearBits64
+#define RtlFindSetBits RtlFindSetBits64
+#define RtlFindClearBitsAndSet RtlFindClearBitsAndSet64
+#define RtlFindSetBitsAndClear RtlFindSetBitsAndClear64
+#define RtlFindNextForwardRunClear RtlFindNextForwardRunClear64
+#define RtlFindNextForwardRunSet RtlFindNextForwardRunSet64
+#define RtlFindFirstRunClear RtlFindFirstRunClear64
+#define RtlFindLastBackwardRunClear RtlFindLastBackwardRunClear64
+#define RtlFindClearRuns RtlFindClearRuns64
+#define RtlFindLongestRunClear RtlFindLongestRunClear64
+#define RtlFindLongestRunSet RtlFindLongestRunSet64
+#else
+#define _BITCOUNT 32
+#define MAXINDEX 0xFFFFFFFF
+typedef ULONG BITMAP_INDEX, *PBITMAP_INDEX;
+typedef ULONG BITMAP_BUFFER, *PBITMAP_BUFFER;
+#endif
/* DATA *********************************************************************/
/* PRIVATE FUNCTIONS ********************************************************/
static __inline
-ULONG
+BITMAP_INDEX
RtlpGetLengthOfRunClear(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG MaxLength)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX StartingIndex,
+ _In_ BITMAP_INDEX MaxLength)
{
- ULONG Value, BitPos, Length;
- PULONG Buffer, MaxBuffer;
+ BITMAP_INDEX Value, BitPos, Length;
+ PBITMAP_BUFFER Buffer, MaxBuffer;
+
+ /* If we are already at the end, the length of the run is zero */
+ ASSERT(StartingIndex <= BitMapHeader->SizeOfBitMap);
+ if (StartingIndex >= BitMapHeader->SizeOfBitMap)
+ return 0;
/* Calculate positions */
- Buffer = BitMapHeader->Buffer + StartingIndex / 32;
- BitPos = StartingIndex & 31;
+ Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
+ BitPos = StartingIndex & (_BITCOUNT - 1);
/* Calculate the maximum length */
MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
- MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+ MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
/* Clear the bits that don't belong to this run */
Value = *Buffer++ >> BitPos << BitPos;
BitScanForward(&BitPos, Value);
/* Calculate length up to where we read */
- Length = (ULONG)(Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
- Length += BitPos - 32;
+ Length = (BITMAP_INDEX)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
+ Length += BitPos - _BITCOUNT;
/* Make sure we don't go past the last bit */
if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
}
static __inline
-ULONG
+BITMAP_INDEX
RtlpGetLengthOfRunSet(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG MaxLength)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX StartingIndex,
+ _In_ BITMAP_INDEX MaxLength)
{
- ULONG InvValue, BitPos, Length;
- PULONG Buffer, MaxBuffer;
+ BITMAP_INDEX InvValue, BitPos, Length;
+ PBITMAP_BUFFER Buffer, MaxBuffer;
+
+ /* If we are already at the end, the length of the run is zero */
+ ASSERT(StartingIndex <= BitMapHeader->SizeOfBitMap);
+ if (StartingIndex >= BitMapHeader->SizeOfBitMap)
+ return 0;
/* Calculate positions */
- Buffer = BitMapHeader->Buffer + StartingIndex / 32;
- BitPos = StartingIndex & 31;
+ Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
+ BitPos = StartingIndex & (_BITCOUNT - 1);
/* Calculate the maximum length */
MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
- MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+ MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
/* Get the inversed value, clear bits that don't belong to the run */
InvValue = ~(*Buffer++) >> BitPos << BitPos;
BitScanForward(&BitPos, InvValue);
/* Calculate length up to where we read */
- Length = (ULONG)(Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
- Length += BitPos - 32;
+ Length = (ULONG)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
+ Length += BitPos - _BITCOUNT;
/* Make sure we don't go past the last bit */
if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
/* PUBLIC FUNCTIONS **********************************************************/
+#ifndef USE_RTL_BITMAP64
CCHAR
NTAPI
RtlFindMostSignificantBit(ULONGLONG Value)
{
ULONG Position;
- if (BitScanReverse(&Position, Value >> 32))
+#ifdef _M_AMD64
+ if (BitScanReverse64(&Position, Value))
{
- return (CCHAR)(Position + 32);
+ return (CCHAR)Position;
+ }
+#else
+ if (BitScanReverse(&Position, Value >> _BITCOUNT))
+ {
+ return (CCHAR)(Position + _BITCOUNT);
}
else if (BitScanReverse(&Position, (ULONG)Value))
{
return (CCHAR)Position;
}
-
+#endif
return -1;
}
{
ULONG Position;
+#ifdef _M_AMD64
+ if (BitScanForward64(&Position, Value))
+ {
+ return (CCHAR)Position;
+ }
+#else
if (BitScanForward(&Position, (ULONG)Value))
{
return (CCHAR)Position;
}
- else if (BitScanForward(&Position, Value >> 32))
+ else if (BitScanForward(&Position, Value >> _BITCOUNT))
{
- return (CCHAR)(Position + 32);
+ return (CCHAR)(Position + _BITCOUNT);
}
-
+#endif
return -1;
}
+#endif /* !USE_RTL_BITMAP64 */
VOID
NTAPI
RtlInitializeBitMap(
- IN PRTL_BITMAP BitMapHeader,
- IN PULONG BitMapBuffer,
- IN ULONG SizeOfBitMap)
+ _Out_ PRTL_BITMAP BitMapHeader,
+ _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer,
+ _In_opt_ ULONG SizeOfBitMap)
{
/* Setup the bitmap header */
BitMapHeader->SizeOfBitMap = SizeOfBitMap;
VOID
NTAPI
RtlClearAllBits(
- IN OUT PRTL_BITMAP BitMapHeader)
+ _In_ PRTL_BITMAP BitMapHeader)
{
- ULONG LengthInUlongs;
+ BITMAP_INDEX LengthInUlongs;
- LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
- RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), 0);
}
VOID
NTAPI
RtlSetAllBits(
- IN OUT PRTL_BITMAP BitMapHeader)
+ _In_ PRTL_BITMAP BitMapHeader)
{
- ULONG LengthInUlongs;
+ BITMAP_INDEX LengthInUlongs;
- LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
- RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), ~0);
}
VOID
NTAPI
RtlClearBit(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG BitNumber)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX BitNumber)
{
ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
- BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber & 31));
+ BitMapHeader->Buffer[BitNumber / _BITCOUNT] &= ~(1 << (BitNumber & (_BITCOUNT - 1)));
}
VOID
NTAPI
RtlSetBit(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG BitNumber)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
{
ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
- BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
+ BitMapHeader->Buffer[BitNumber / _BITCOUNT] |= ((BITMAP_INDEX)1 << (BitNumber & (_BITCOUNT - 1)));
}
VOID
NTAPI
RtlClearBits(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG NumberToClear)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX StartingIndex,
+ _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToClear)
{
- ULONG Bits, Mask;
- PULONG Buffer;
+ BITMAP_INDEX Bits, Mask;
+ PBITMAP_BUFFER Buffer;
ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
/* Calculate buffer start and first bit index */
- Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
- Bits = StartingIndex & 31;
+ Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
+ Bits = StartingIndex & (_BITCOUNT - 1);
/* Are we unaligned? */
if (Bits)
{
- /* Create an inverse mask by shifting MAXULONG */
- Mask = MAXULONG << Bits;
+ /* Create an inverse mask by shifting MAXINDEX */
+ Mask = MAXINDEX << Bits;
/* This is what's left in the first ULONG */
- Bits = 32 - Bits;
+ Bits = _BITCOUNT - Bits;
/* Even less bits to clear? */
if (NumberToClear < Bits)
/* Clear all full ULONGs */
RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
- Buffer += NumberToClear >> 5;
+ Buffer += NumberToClear / _BITCOUNT;
/* Clear what's left */
- NumberToClear &= 31;
- Mask = MAXULONG << NumberToClear;
- *Buffer &= Mask;
+ NumberToClear &= (_BITCOUNT - 1);
+ if (NumberToClear != 0)
+ {
+ Mask = MAXINDEX << NumberToClear;
+ *Buffer &= Mask;
+ }
}
VOID
NTAPI
RtlSetBits(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG NumberToSet)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex,
+ _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
{
- ULONG Bits, Mask;
- PULONG Buffer;
+ BITMAP_INDEX Bits, Mask;
+ PBITMAP_BUFFER Buffer;
ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
/* Calculate buffer start and first bit index */
- Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
- Bits = StartingIndex & 31;
+ Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
+ Bits = StartingIndex & (_BITCOUNT - 1);
/* Are we unaligned? */
if (Bits)
{
- /* Create a mask by shifting MAXULONG */
- Mask = MAXULONG << Bits;
+ /* Create a mask by shifting MAXINDEX */
+ Mask = MAXINDEX << Bits;
/* This is what's left in the first ULONG */
- Bits = 32 - Bits;
+ Bits = _BITCOUNT - Bits;
/* Even less bits to clear? */
if (NumberToSet < Bits)
}
/* Set all full ULONGs */
- RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
- Buffer += NumberToSet >> 5;
+ RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXINDEX);
+ Buffer += NumberToSet / _BITCOUNT;
/* Set what's left */
- NumberToSet &= 31;
- Mask = MAXULONG << NumberToSet;
- *Buffer |= ~Mask;
+ NumberToSet &= (_BITCOUNT - 1);
+ if (NumberToSet != 0)
+ {
+ Mask = MAXINDEX << NumberToSet;
+ *Buffer |= ~Mask;
+ }
}
BOOLEAN
NTAPI
RtlTestBit(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG BitNumber)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
{
ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
- return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31)) & 1;
+ return (BitMapHeader->Buffer[BitNumber / _BITCOUNT] >> (BitNumber & (_BITCOUNT - 1))) & 1;
}
BOOLEAN
NTAPI
RtlAreBitsClear(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG Length)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX StartingIndex,
+ _In_ BITMAP_INDEX Length)
{
+ /* Verify parameters */
+ if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
+ (StartingIndex + Length <= StartingIndex))
+ return FALSE;
+
return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
}
BOOLEAN
NTAPI
RtlAreBitsSet(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG Length)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX StartingIndex,
+ _In_ BITMAP_INDEX Length)
{
+ /* Verify parameters */
+ if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
+ (StartingIndex + Length <= StartingIndex))
+ return FALSE;
+
return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlNumberOfSetBits(
- IN PRTL_BITMAP BitMapHeader)
+ _In_ PRTL_BITMAP BitMapHeader)
{
PUCHAR Byte, MaxByte;
- ULONG BitCount = 0;
+ BITMAP_INDEX BitCount = 0;
+ ULONG Shift;
Byte = (PUCHAR)BitMapHeader->Buffer;
- MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
+ MaxByte = Byte + BitMapHeader->SizeOfBitMap / 8;
- do
+ while (Byte < MaxByte)
{
BitCount += BitCountTable[*Byte++];
}
- while (Byte <= MaxByte);
+
+ if (BitMapHeader->SizeOfBitMap & 7)
+ {
+ Shift = 8 - (BitMapHeader->SizeOfBitMap & 7);
+ BitCount += BitCountTable[((*Byte) << Shift) & 0xFF];
+ }
return BitCount;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlNumberOfClearBits(
- IN PRTL_BITMAP BitMapHeader)
+ _In_ PRTL_BITMAP BitMapHeader)
{
/* Do some math */
return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindClearBits(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG NumberToFind,
- IN ULONG HintIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX NumberToFind,
+ _In_ BITMAP_INDEX HintIndex)
{
- ULONG CurrentBit, Margin, CurrentLength;
+ BITMAP_INDEX CurrentBit, Margin, CurrentLength;
/* Check for valid parameters */
if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
{
- return MAXULONG;
+ return MAXINDEX;
}
+ /* Check if the hint is outside the bitmap */
+ if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
+
/* Check for trivial case */
if (NumberToFind == 0)
{
- return HintIndex;
+ /* Return hint rounded down to byte margin */
+ return HintIndex & ~7;
}
/* First margin is end of bitmap */
/* Search for the next clear run, by skipping a set run */
CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
CurrentBit,
- MAXULONG);
+ MAXINDEX);
/* Get length of the clear bit run */
CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
}
/* Nothing found */
- return MAXULONG;
+ return MAXINDEX;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindSetBits(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG NumberToFind,
- IN ULONG HintIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX NumberToFind,
+ _In_ BITMAP_INDEX HintIndex)
{
- ULONG CurrentBit, Margin, CurrentLength;
+ BITMAP_INDEX CurrentBit, Margin, CurrentLength;
/* Check for valid parameters */
if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
{
- return MAXULONG;
+ return MAXINDEX;
}
+ /* Check if the hint is outside the bitmap */
+ if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
+
/* Check for trivial case */
if (NumberToFind == 0)
{
- return HintIndex;
+ /* Return hint rounded down to byte margin */
+ return HintIndex & ~7;
}
/* First margin is end of bitmap */
/* Search for the next set run, by skipping a clear run */
CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
CurrentBit,
- MAXULONG);
+ MAXINDEX);
/* Get length of the set bit run */
CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
}
/* Nothing found */
- return MAXULONG;
+ return MAXINDEX;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindClearBitsAndSet(
- PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX NumberToFind,
+ _In_ BITMAP_INDEX HintIndex)
{
- ULONG Position;
+ BITMAP_INDEX Position;
/* Try to find clear bits */
Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
/* Did we get something? */
- if (Position != MAXULONG)
+ if (Position != MAXINDEX)
{
/* Yes, set the bits */
RtlSetBits(BitMapHeader, Position, NumberToFind);
return Position;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindSetBitsAndClear(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG NumberToFind,
- IN ULONG HintIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX NumberToFind,
+ _In_ BITMAP_INDEX HintIndex)
{
- ULONG Position;
+ BITMAP_INDEX Position;
/* Try to find set bits */
Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
/* Did we get something? */
- if (Position != MAXULONG)
+ if (Position != MAXINDEX)
{
/* Yes, clear the bits */
RtlClearBits(BitMapHeader, Position, NumberToFind);
return Position;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindNextForwardRunClear(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX FromIndex,
+ _Out_ PBITMAP_INDEX StartingRunIndex)
{
- ULONG Length;
+ BITMAP_INDEX Length;
+
+ /* Check for buffer overrun */
+ if (FromIndex >= BitMapHeader->SizeOfBitMap)
+ {
+ *StartingRunIndex = FromIndex;
+ return 0;
+ }
/* Assume a set run first, count it's length */
- Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
+ Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXINDEX);
*StartingRunIndex = FromIndex + Length;
/* Now return the length of the run */
- return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXULONG);
+ return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXINDEX);
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindNextForwardRunSet(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX FromIndex,
+ _Out_ PBITMAP_INDEX StartingRunIndex)
{
- ULONG Length;
+ BITMAP_INDEX Length;
+
+ /* Check for buffer overrun */
+ if (FromIndex >= BitMapHeader->SizeOfBitMap)
+ {
+ *StartingRunIndex = FromIndex;
+ return 0;
+ }
/* Assume a clear run first, count it's length */
- Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
+ Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXINDEX);
*StartingRunIndex = FromIndex + Length;
/* Now return the length of the run */
- return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
+ return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex + Length, MAXINDEX);
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindFirstRunClear(
- IN PRTL_BITMAP BitMapHeader,
- IN PULONG StartingIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _Out_ PBITMAP_INDEX StartingIndex)
{
return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindLastBackwardRunClear(
- IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ BITMAP_INDEX FromIndex,
+ _Out_ PBITMAP_INDEX StartingRunIndex)
{
- UNIMPLEMENTED;
- return 0;
+ BITMAP_INDEX Value, InvValue, BitPos;
+ PBITMAP_BUFFER Buffer;
+
+ /* Make sure we don't go past the end */
+ FromIndex = min(FromIndex, BitMapHeader->SizeOfBitMap - 1);
+
+ /* Calculate positions */
+ Buffer = BitMapHeader->Buffer + FromIndex / _BITCOUNT;
+ BitPos = (_BITCOUNT - 1) - (FromIndex & (_BITCOUNT - 1));
+
+ /* Get the inversed value, clear bits that don't belong to the run */
+ InvValue = ~(*Buffer--) << BitPos >> BitPos;
+
+ /* Skip all set ULONGs */
+ while (InvValue == 0)
+ {
+ /* Did we already reach past the first ULONG? */
+ if (Buffer < BitMapHeader->Buffer)
+ {
+ /* Yes, nothing found */
+ return 0;
+ }
+
+ InvValue = ~(*Buffer--);
+ }
+
+ /* We hit a clear bit, check how many set bits are left */
+ BitScanReverse(&BitPos, InvValue);
+
+ /* Calculate last bit position */
+ FromIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos);
+
+ Value = ~InvValue << ((_BITCOUNT - 1) - BitPos) >> ((_BITCOUNT - 1) - BitPos);
+
+ /* Skip all clear ULONGs */
+ while (Value == 0 && Buffer >= BitMapHeader->Buffer)
+ {
+ Value = *Buffer--;
+ }
+
+ if (Value != 0)
+ {
+ /* We hit a set bit, check how many clear bits are left */
+ BitScanReverse(&BitPos, Value);
+
+ /* Calculate Starting Index */
+ *StartingRunIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos + 1);
+ }
+ else
+ {
+ /* We reached the start of the bitmap */
+ *StartingRunIndex = 0;
+ }
+
+ /* Return length of the run */
+ return (FromIndex - *StartingRunIndex);
}
ULONG
NTAPI
RtlFindClearRuns(
- IN PRTL_BITMAP BitMapHeader,
- IN PRTL_BITMAP_RUN RunArray,
- IN ULONG SizeOfRunArray,
- IN BOOLEAN LocateLongestRuns)
+ _In_ PRTL_BITMAP BitMapHeader,
+ _In_ PRTL_BITMAP_RUN RunArray,
+ _In_ ULONG SizeOfRunArray,
+ _In_ BOOLEAN LocateLongestRuns)
{
- ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
+ BITMAP_INDEX StartingIndex, NumberOfBits, FromIndex = 0, SmallestRun = 0;
+ ULONG Run;
/* Loop the runs */
for (Run = 0; Run < SizeOfRunArray; Run++)
return Run;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindLongestRunClear(
IN PRTL_BITMAP BitMapHeader,
- IN PULONG StartingIndex)
+ IN PBITMAP_INDEX StartingIndex)
{
- ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+ BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
while (1)
{
return MaxNumberOfBits;
}
-ULONG
+BITMAP_INDEX
NTAPI
RtlFindLongestRunSet(
IN PRTL_BITMAP BitMapHeader,
- IN PULONG StartingIndex)
+ IN PBITMAP_INDEX StartingIndex)
{
- ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+ BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
while (1)
{
projects / reactos.git / blobdiff