-/* COPYRIGHT: See COPYING in the top level directory
+/*
+ * COPYRIGHT: See COPYING in the top level directory
* PROJECT: ReactOS system libraries
* FILE: lib/rtl/bitmap.c
* PURPOSE: Bitmap functions
- * PROGRAMMER: Eric Kohl
+ * PROGRAMMER: Timo Kreuzer (timo.kreuzer@reactos.org)
*/
/* INCLUDES *****************************************************************/
#define NDEBUG
#include <debug.h>
-/* MACROS *******************************************************************/
-
-/* Bits set from LSB to MSB; used as mask for runs < 8 bits */
-static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
-/* Number of set bits for each value of a nibble; used for counting */
-static const BYTE NTDLL_nibbleBitCount[16] = {
- 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
-};
-
-/* First set bit in a nibble; used for determining least significant bit */
-static const BYTE NTDLL_leastSignificant[16] = {
- 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
-};
+/* DATA *********************************************************************/
-/* Last set bit in a nibble; used for determining most significant bit */
-static const signed char NTDLL_mostSignificant[16] = {
- -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
+/* Number of set bits per byte value */
+static const
+UCHAR
+BitCountTable[256] =
+{
+ /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
+ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
};
-/* PRIVATE FUNCTIONS *********************************************************/
-static
-int
-__cdecl
-NTDLL_RunSortFn(const void *lhs,
- const void *rhs)
-{
- if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
- return -1;
- return 1;
-}
+/* PRIVATE FUNCTIONS ********************************************************/
-static
+static __inline__
ULONG
-WINAPI
-NTDLL_FindRuns(PRTL_BITMAP lpBits,
- PRTL_BITMAP_RUN lpSeries,
- ULONG ulCount,
- BOOLEAN bLongest,
- ULONG (*fn)(PRTL_BITMAP,ULONG,PULONG))
+RtlpGetLengthOfRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG MaxLength)
{
- BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
- ULONG ulPos = 0, ulRuns = 0;
+ ULONG Value, BitPos, Length;
+ PULONG Buffer, MaxBuffer;
- if (!ulCount)
- return MAXULONG;
+ /* Calculate positions */
+ Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+ BitPos = StartingIndex & 31;
- while (ulPos < lpBits->SizeOfBitMap)
- {
- /* Find next set/clear run */
- ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
+ /* Calculate the maximum length */
+ MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+ MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
- if (ulNextPos == MAXULONG)
- break;
+ /* Clear the bits that don't belong to this run */
+ Value = *Buffer++ >> BitPos << BitPos;
- if (bLongest && ulRuns == ulCount)
+ /* Skip all clear ULONGs */
+ while (Value == 0 && Buffer < MaxBuffer)
{
- /* Sort runs with shortest at end, if they are out of order */
- if (bNeedSort)
- qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
-
- /* Replace last run if this one is bigger */
- if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
- {
- lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
- lpSeries[ulRuns - 1].NumberOfBits = ulSize;
-
- /* We need to re-sort the array, _if_ we didn't leave it sorted */
- if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
- bNeedSort = TRUE;
- }
+ Value = *Buffer++;
}
- else
- {
- /* Append to found runs */
- lpSeries[ulRuns].StartingIndex = ulNextPos;
- lpSeries[ulRuns].NumberOfBits = ulSize;
- ulRuns++;
- if (!bLongest && ulRuns == ulCount)
- break;
+ /* Did we reach the end? */
+ if (Value == 0)
+ {
+ /* Return maximum length */
+ return MaxLength;
}
- ulPos = ulNextPos + ulSize;
- }
- return ulRuns;
+
+ /* We hit a set bit, check how many clear bits are left */
+ BitScanForward(&BitPos, Value);
+
+ /* Calculate length up to where we read */
+ Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
+ Length += BitPos - 32;
+
+ if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+ Length = BitMapHeader->SizeOfBitMap - StartingIndex;
+
+ /* The result is guaranteed to be < BitMapHeader->SizeOfBitMap */
+ return Length;
}
-static
+static __inline__
ULONG
-NTDLL_FindSetRun(PRTL_BITMAP lpBits,
- ULONG ulStart,
- PULONG lpSize)
+RtlpGetLengthOfRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG MaxLength)
{
- LPBYTE lpOut;
- ULONG ulFoundAt = 0, ulCount = 0;
+ ULONG InvValue, BitPos, Length;
+ PULONG Buffer, MaxBuffer;
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
+ /* Calculate positions */
+ Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+ BitPos = StartingIndex & 31;
- while (1)
- {
- /* Check bits in first byte */
- const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
- const BYTE bFirst = *lpOut & bMask;
+ /* Calculate the maximum length */
+ MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+ MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
- if (bFirst)
+ /* Get the inversed value, clear bits that don't belong to the run */
+ InvValue = ~(*Buffer++) >> BitPos << BitPos;
+
+ /* Skip all set ULONGs */
+ while (InvValue == 0 && Buffer < MaxBuffer)
{
- /* Have a set bit in first byte */
- if (bFirst != bMask)
- {
- /* Not every bit is set */
- ULONG ulOffset;
-
- if (bFirst & 0x0f)
- ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
- else
- ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
- ulStart += ulOffset;
- ulFoundAt = ulStart;
- for (;ulOffset < 8; ulOffset++)
- {
- if (!(bFirst & (1 << ulOffset)))
- {
- *lpSize = ulCount;
- return ulFoundAt; /* Set from start, but not until the end */
- }
- ulCount++;
- ulStart++;
- }
- /* Set to the end - go on to count further bits */
- lpOut++;
- break;
- }
- /* every bit from start until the end of the byte is set */
- ulFoundAt = ulStart;
- ulCount = 8 - (ulStart & 7);
- ulStart = (ulStart & ~7u) + 8;
- lpOut++;
- break;
+ InvValue = ~(*Buffer++);
}
- ulStart = (ulStart & ~7u) + 8;
- lpOut++;
- if (ulStart >= lpBits->SizeOfBitMap)
- return MAXULONG;
- }
-
- /* Count blocks of 8 set bits */
- while (*lpOut == 0xff)
- {
- ulCount += 8;
- ulStart += 8;
- if (ulStart >= lpBits->SizeOfBitMap)
+
+ /* Did we reach the end? */
+ if (InvValue == 0)
{
- *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
- return ulFoundAt;
+ /* Yes, return maximum */
+ return MaxLength;
}
- lpOut++;
- }
- /* Count remaining contiguous bits, if any */
- if (*lpOut & 1)
- {
- ULONG ulOffset = 0;
+ /* We hit a clear bit, check how many set bits are left */
+ BitScanForward(&BitPos, InvValue);
- for (;ulOffset < 7u; ulOffset++)
- {
- if (!(*lpOut & (1 << ulOffset)))
- break;
- ulCount++;
- }
- }
- *lpSize = ulCount;
- return ulFoundAt;
+ /* Calculate length up to where we read */
+ Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
+ Length += BitPos - 32;
+
+ if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+ Length = BitMapHeader->SizeOfBitMap - StartingIndex;
+
+ /* The result is guaranteed to be < BitMapHeader->SizeOfBitMap */
+ return Length;
}
-static
-ULONG
-NTDLL_FindClearRun(PRTL_BITMAP lpBits,
- ULONG ulStart,
- PULONG lpSize)
-{
- LPBYTE lpOut;
- ULONG ulFoundAt = 0, ulCount = 0;
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
+/* PUBLIC FUNCTIONS **********************************************************/
- while (1)
- {
- /* Check bits in first byte */
- const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
- const BYTE bFirst = (~*lpOut) & bMask;
+CCHAR
+NTAPI
+RtlFindMostSignificantBit(ULONGLONG Value)
+{
+ ULONG Position;
- if (bFirst)
+ if (BitScanReverse(&Position, Value >> 32))
{
- /* Have a clear bit in first byte */
- if (bFirst != bMask)
- {
- /* Not every bit is clear */
- ULONG ulOffset;
-
- if (bFirst & 0x0f)
- ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
- else
- ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
- ulStart += ulOffset;
- ulFoundAt = ulStart;
- for (;ulOffset < 8; ulOffset++)
- {
- if (!(bFirst & (1 << ulOffset)))
- {
- *lpSize = ulCount;
- return ulFoundAt; /* Clear from start, but not until the end */
- }
- ulCount++;
- ulStart++;
- }
- /* Clear to the end - go on to count further bits */
- lpOut++;
- break;
- }
- /* Every bit from start until the end of the byte is clear */
- ulFoundAt = ulStart;
- ulCount = 8 - (ulStart & 7);
- ulStart = (ulStart & ~7u) + 8;
- lpOut++;
- break;
+ return Position + 32;
}
- ulStart = (ulStart & ~7u) + 8;
- lpOut++;
- if (ulStart >= lpBits->SizeOfBitMap)
- return MAXULONG;
- }
-
- /* Count blocks of 8 clear bits */
- while (!*lpOut)
- {
- ulCount += 8;
- ulStart += 8;
- if (ulStart >= lpBits->SizeOfBitMap)
+ else if (BitScanReverse(&Position, (ULONG)Value))
{
- *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
- return ulFoundAt;
+ return Position;
}
- lpOut++;
- }
- /* Count remaining contiguous bits, if any */
- if (!(*lpOut & 1))
- {
- ULONG ulOffset = 0;
+ return -1;
+}
+
+CCHAR
+NTAPI
+RtlFindLeastSignificantBit(ULONGLONG Value)
+{
+ ULONG Position;
- for (;ulOffset < 7u; ulOffset++)
+ if (BitScanForward(&Position, (ULONG)Value))
{
- if (*lpOut & (1 << ulOffset))
- break;
- ulCount++;
+ return Position;
+ }
+ else if (BitScanForward(&Position, Value >> 32))
+ {
+ return Position + 32;
}
- }
- *lpSize = ulCount;
- return ulFoundAt;
-}
-/* FUNCTIONS ****************************************************************/
+ return -1;
+}
-/*
- * @implemented
- */
VOID
NTAPI
-RtlInitializeBitMap(IN PRTL_BITMAP BitMapHeader,
- IN PULONG BitMapBuffer,
- IN ULONG SizeOfBitMap)
+RtlInitializeBitMap(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG BitMapBuffer,
+ IN ULONG SizeOfBitMap)
{
+ // FIXME: some bugger here!
+ //ASSERT(SizeOfBitMap > 0);
+
/* Setup the bitmap header */
BitMapHeader->SizeOfBitMap = SizeOfBitMap;
BitMapHeader->Buffer = BitMapBuffer;
}
-/*
- * @implemented
- */
-BOOLEAN
+VOID
NTAPI
-RtlAreBitsClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG Length)
+RtlClearAllBits(
+ IN OUT PRTL_BITMAP BitMapHeader)
{
- LPBYTE lpOut;
- ULONG ulRemainder;
-
- if (!BitMapHeader || !Length ||
- StartingIndex >= BitMapHeader->SizeOfBitMap ||
- Length > BitMapHeader->SizeOfBitMap - StartingIndex)
- return FALSE;
-
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
-
- /* Check bits in first byte, if StartingIndex isn't a byte boundary */
- if (StartingIndex & 7)
- {
- if (Length > 7)
- {
- /* Check from start bit to the end of the byte */
- if (*lpOut & ((0xff << (StartingIndex & 7)) & 0xff))
- return FALSE;
- lpOut++;
- Length -= (8 - (StartingIndex & 7));
- }
- else
- {
- /* Check from the start bit, possibly into the next byte also */
- USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
-
- if (*lpOut & (initialWord & 0xff))
- return FALSE;
- if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
- return FALSE;
- return TRUE;
- }
- }
-
- /* Check bits in blocks of 8 bytes */
- ulRemainder = Length & 7;
- Length >>= 3;
- while (Length--)
- {
- if (*lpOut++)
- return FALSE;
- }
-
- /* Check remaining bits, if any */
- if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
- return FALSE;
- return TRUE;
-}
+ ULONG LengthInUlongs;
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
+}
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlAreBitsSet(PRTL_BITMAP BitMapHeader,
- ULONG StartingIndex,
- ULONG Length)
+VOID
+NTAPI
+RtlSetAllBits(
+ IN OUT PRTL_BITMAP BitMapHeader)
{
- LPBYTE lpOut;
- ULONG ulRemainder;
-
-
- if (!BitMapHeader || !Length ||
- StartingIndex >= BitMapHeader->SizeOfBitMap ||
- Length > BitMapHeader->SizeOfBitMap - StartingIndex)
- return FALSE;
-
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
-
- /* Check bits in first byte, if StartingIndex isn't a byte boundary */
- if (StartingIndex & 7)
- {
- if (Length > 7)
- {
- /* Check from start bit to the end of the byte */
- if ((*lpOut &
- ((0xff << (StartingIndex & 7))) & 0xff) != ((0xff << (StartingIndex & 7) & 0xff)))
- return FALSE;
- lpOut++;
- Length -= (8 - (StartingIndex & 7));
- }
- else
- {
- /* Check from the start bit, possibly into the next byte also */
- USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
-
- if ((*lpOut & (initialWord & 0xff)) != (initialWord & 0xff))
- return FALSE;
- if ((initialWord & 0xff00) &&
- ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
- return FALSE;
- return TRUE;
- }
- }
-
- /* Check bits in blocks of 8 bytes */
- ulRemainder = Length & 7;
- Length >>= 3;
- while (Length--)
- {
- if (*lpOut++ != 0xff)
- return FALSE;
- }
-
- /* Check remaining bits, if any */
- if (ulRemainder &&
- (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
- return FALSE;
- return TRUE;
+ ULONG LengthInUlongs;
+
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
}
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
+VOID
+NTAPI
+RtlClearBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
{
- memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
+ ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+ BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber & 31));
}
-/*
- * @implemented
- */
VOID
NTAPI
-RtlClearBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
+RtlSetBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
{
- PUCHAR Ptr;
-
- if (BitNumber >= BitMapHeader->SizeOfBitMap) return;
-
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
- *Ptr &= ~(1 << (BitNumber % 8));
+ ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+ BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
}
-/*
- * @implemented
- */
VOID
NTAPI
-RtlClearBits(IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG NumberToClear)
+RtlClearBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG NumberToClear)
{
- LPBYTE lpOut;
-
- if (!BitMapHeader || !NumberToClear ||
- StartingIndex >= BitMapHeader->SizeOfBitMap ||
- NumberToClear > BitMapHeader->SizeOfBitMap - StartingIndex)
- return;
-
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
-
- /* Clear bits in first byte, if StartingIndex isn't a byte boundary */
- if (StartingIndex & 7)
- {
- if (NumberToClear > 7)
- {
- /* Clear from start bit to the end of the byte */
- *lpOut++ &= ~(0xff << (StartingIndex & 7));
- NumberToClear -= (8 - (StartingIndex & 7));
- }
- else
- {
- /* Clear from the start bit, possibly into the next byte also */
- USHORT initialWord = ~(NTDLL_maskBits[NumberToClear] << (StartingIndex & 7));
+ ULONG Bits, Mask;
+ PULONG Buffer;
- *lpOut++ &= (initialWord & 0xff);
- *lpOut &= (initialWord >> 8);
- return;
- }
- }
-
- /* Clear bits (in blocks of 8) on whole byte boundaries */
- if (NumberToClear >> 3)
- {
- memset(lpOut, 0, NumberToClear >> 3);
- lpOut = lpOut + (NumberToClear >> 3);
- }
-
- /* Clear remaining bits, if any */
- if (NumberToClear & 0x7)
- *lpOut &= ~NTDLL_maskBits[NumberToClear & 0x7];
-}
+ ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
+ /* Calculate buffer start and first bit index */
+ Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+ Bits = StartingIndex & 31;
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearBits(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
-{
- ULONG ulPos, ulEnd;
+ /* Are we unaligned? */
+ if (Bits)
+ {
+ /* Create an inverse mask by shifting MAXULONG */
+ Mask = MAXULONG << Bits;
- if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
- return MAXULONG;
+ /* This is what's left in the first ULONG */
+ Bits = 32 - Bits;
- ulEnd = BitMapHeader->SizeOfBitMap;
+ /* Even less bits to clear? */
+ if (NumberToClear < Bits)
+ {
+ /* Calculate how many bits are left */
+ Bits -= NumberToClear;
- if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
- HintIndex = 0;
+ /* Fixup the mask on the high side */
+ Mask = Mask << Bits >> Bits;
- ulPos = HintIndex;
+ /* Clear bits and return */
+ *Buffer &= ~Mask;
+ return;
+ }
- while (ulPos < ulEnd)
- {
- /* FIXME: This could be made a _lot_ more efficient */
- if (RtlAreBitsClear(BitMapHeader, ulPos, NumberToFind))
- return ulPos;
+ /* Clear bits */
+ *Buffer &= ~Mask;
- /* Start from the beginning if we hit the end and started from HintIndex */
- if (ulPos == ulEnd - 1 && HintIndex)
- {
- ulEnd = HintIndex;
- ulPos = HintIndex = 0;
+ /* Update buffer and left bits */
+ Buffer++;
+ NumberToClear -= Bits;
}
- else
- ulPos++;
- }
- return MAXULONG;
-}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearRuns(PRTL_BITMAP BitMapHeader,
- PRTL_BITMAP_RUN RunArray,
- ULONG SizeOfRunArray,
- BOOLEAN LocateLongestRuns)
-{
- return NTDLL_FindRuns(BitMapHeader, RunArray, SizeOfRunArray, LocateLongestRuns, NTDLL_FindClearRun);
-}
+ /* Clear all full ULONGs */
+ RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
+ Buffer += NumberToClear >> 5;
-/*
- * @unimplemented
- */
-ULONG NTAPI
-RtlFindLastBackwardRunClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
-{
- UNIMPLEMENTED;
- return 0;
+ /* Clear what's left */
+ NumberToClear &= 31;
+ Mask = MAXULONG << NumberToClear;
+ *Buffer &= Mask;
}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
+VOID
+NTAPI
+RtlSetBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG NumberToSet)
{
- ULONG ulSize = 0;
+ ULONG Bits, Mask;
+ PULONG Buffer;
- if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap && StartingRunIndex)
- *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize);
+ ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
- return ulSize;
-}
+ /* Calculate buffer start and first bit index */
+ Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+ Bits = StartingIndex & 31;
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindFirstRunSet(IN PRTL_BITMAP BitMapHeader,
- IN PULONG StartingIndex)
-{
- ULONG Size;
- ULONG Index;
- ULONG Count;
- PULONG Ptr;
- ULONG Mask;
-
- Size = BitMapHeader->SizeOfBitMap;
- if (*StartingIndex > Size)
- {
- *StartingIndex = MAXULONG;
- return 0;
- }
+ /* Are we unaligned? */
+ if (Bits)
+ {
+ /* Create a mask by shifting MAXULONG */
+ Mask = MAXULONG << Bits;
- Index = *StartingIndex;
- Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
- Mask = 1 << (Index & 0x1F);
+ /* This is what's left in the first ULONG */
+ Bits = 32 - Bits;
- /* Skip clear bits */
- for (; Index < Size && ~*Ptr & Mask; Index++)
- {
- Mask <<= 1;
+ /* Even less bits to clear? */
+ if (NumberToSet < Bits)
+ {
+ /* Calculate how many bits are left */
+ Bits -= NumberToSet;
- if (Mask == 0)
- {
- Mask = 1;
- Ptr++;
- }
- }
+ /* Fixup the mask on the high side */
+ Mask = Mask << Bits >> Bits;
- /* Return index of first set bit */
- if (Index >= Size)
- {
- *StartingIndex = MAXULONG;
- return 0;
- }
- else
- {
- *StartingIndex = Index;
- }
-
- /* Count set bits */
- for (Count = 0; Index < Size && *Ptr & Mask; Index++)
- {
- Count++;
- Mask <<= 1;
-
- if (Mask == 0)
- {
- Mask = 1;
- Ptr++;
+ /* Set bits and return */
+ *Buffer |= Mask;
+ return;
+ }
+
+ /* Set bits */
+ *Buffer |= Mask;
+
+ /* Update buffer and left bits */
+ Buffer++;
+ NumberToSet -= Bits;
}
- }
- return Count;
-}
+ /* Set all full ULONGs */
+ RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
+ Buffer += NumberToSet >> 5;
+ /* Set what's left */
+ NumberToSet &= 31;
+ Mask = MAXULONG << NumberToSet;
+ *Buffer |= ~Mask;
+}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
+BOOLEAN
+NTAPI
+RtlTestBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
{
- /* GCC complaints that it may be used uninitialized */
- RTL_BITMAP_RUN br = { 0, 0 };
-
- if (RtlFindClearRuns(BitMapHeader, &br, 1, TRUE) == 1)
- {
- if (StartingIndex)
- *StartingIndex = br.StartingIndex;
- return br.NumberOfBits;
- }
- return 0;
+ ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
+ return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31)) & 1;
}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
+BOOLEAN
+NTAPI
+RtlAreBitsClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG Length)
{
- /* GCC complaints that it may be used uninitialized */
- RTL_BITMAP_RUN br = { 0, 0 };
-
- if (NTDLL_FindRuns(BitMapHeader, &br, 1, TRUE, NTDLL_FindSetRun) == 1)
- {
- if (StartingIndex)
- *StartingIndex = br.StartingIndex;
- return br.NumberOfBits;
- }
- return 0;
+ return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindSetBits(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
+BOOLEAN
+NTAPI
+RtlAreBitsSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG Length)
{
- ULONG ulPos, ulEnd;
-
- if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
- return MAXULONG;
-
- ulEnd = BitMapHeader->SizeOfBitMap;
-
- if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
- HintIndex = 0;
+ return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
+}
- ulPos = HintIndex;
+ULONG
+NTAPI
+RtlNumberOfSetBits(
+ IN PRTL_BITMAP BitMapHeader)
+{
+ PUCHAR Byte, MaxByte;
+ ULONG BitCount = 0;
- while (ulPos < ulEnd)
- {
- /* FIXME: This could be made a _lot_ more efficient */
- if (RtlAreBitsSet(BitMapHeader, ulPos, NumberToFind))
- return ulPos;
+ Byte = (PUCHAR)BitMapHeader->Buffer;
+ MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
- /* Start from the beginning if we hit the end and had a hint */
- if (ulPos == ulEnd - 1 && HintIndex)
+ do
{
- ulEnd = HintIndex;
- ulPos = HintIndex = 0;
+ BitCount += BitCountTable[*Byte++];
}
- else
- ulPos++;
- }
- return MAXULONG;
-}
+ while (Byte <= MaxByte);
+ return BitCount;
+}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
+ULONG
+NTAPI
+RtlNumberOfClearBits(
+ IN PRTL_BITMAP BitMapHeader)
{
- ULONG ulPos;
-
- ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
- if (ulPos != MAXULONG)
- RtlClearBits(BitMapHeader, ulPos, NumberToFind);
- return ulPos;
+ /* Do some math */
+ return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
+ULONG
+NTAPI
+RtlFindClearBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
{
- ULONG ulSet = 0;
-
- if (BitMapHeader)
- {
- LPBYTE lpOut = (BYTE *)BitMapHeader->Buffer;
- ULONG Length, ulRemainder;
- BYTE bMasked;
+ ULONG CurrentBit, CurrentLength;
- Length = BitMapHeader->SizeOfBitMap >> 3;
- ulRemainder = BitMapHeader->SizeOfBitMap & 0x7;
+ /* Check for valid parameters */
+ if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+ {
+ return MAXULONG;
+ }
- while (Length--)
+ /* Check for trivial case */
+ if (NumberToFind == 0)
{
- ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
- ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
- lpOut++;
+ return HintIndex;
}
- if (ulRemainder)
+ /* Start with hint index, length is 0 */
+ CurrentBit = HintIndex;
+ CurrentLength = 0;
+
+ /* Loop until something is found or the end is reached */
+ while (CurrentBit + NumberToFind < BitMapHeader->SizeOfBitMap)
{
- bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
- ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
- ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
+ ULONG test;
+ /* Search for the next clear run, by skipping a set run */
+ test = RtlpGetLengthOfRunSet(BitMapHeader,
+ CurrentBit,
+ MAXULONG);
+ CurrentBit += test;
+
+ /* Get length of the clear bit run */
+ CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
+ CurrentBit,
+ NumberToFind);
+
+ /* Is this long enough? */
+ if (CurrentLength >= NumberToFind)
+ {
+ /* It is */
+ return CurrentBit;
+ }
+
+ CurrentBit += CurrentLength;
}
- }
- return ulSet;
-}
+ /* Nothing found */
+ return MAXULONG;
+}
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetAllBits(IN OUT PRTL_BITMAP BitMapHeader)
+ULONG
+NTAPI
+RtlFindSetBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
{
- memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
-}
+ ULONG CurrentBit, CurrentLength;
+ /* Check for valid parameters */
+ if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+ {
+ return MAXULONG;
+ }
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
-{
- PUCHAR Ptr;
+ /* Check for trivial case */
+ if (NumberToFind == 0)
+ {
+ return HintIndex;
+ }
- if (BitNumber >= BitMapHeader->SizeOfBitMap)
- return;
+ /* Start with hint index, length is 0 */
+ CurrentBit = HintIndex;
+ CurrentLength = 0;
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
+ /* Loop until something is found or the end is reached */
+ while (CurrentBit + NumberToFind <= BitMapHeader->SizeOfBitMap)
+ {
+ /* Search for the next set run, by skipping a clear run */
+ CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
+ CurrentBit,
+ MAXULONG);
+
+ /* Get length of the set bit run */
+ CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
+ CurrentBit,
+ NumberToFind);
+
+ /* Is this long enough? */
+ if (CurrentLength >= NumberToFind)
+ {
+ /* It is */
+ return CurrentBit;
+ }
- *Ptr |= (1 << (BitNumber % 8));
-}
+ CurrentBit += CurrentLength;
+ }
+ /* Nothing found */
+ return MAXULONG;
+}
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetBits(PRTL_BITMAP BitMapHeader,
- ULONG StartingIndex,
- ULONG NumberToSet)
+ULONG
+NTAPI
+RtlFindClearBitsAndSet(
+ PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
{
- LPBYTE lpOut;
-
- if (!BitMapHeader || !NumberToSet ||
- StartingIndex >= BitMapHeader->SizeOfBitMap ||
- NumberToSet > BitMapHeader->SizeOfBitMap - StartingIndex)
- return;
-
- /* FIXME: It might be more efficient/cleaner to manipulate four bytes
- * at a time. But beware of the pointer arithmetics...
- */
- lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
-
- /* Set bits in first byte, if StartingIndex isn't a byte boundary */
- if (StartingIndex & 7)
- {
- if (NumberToSet > 7)
+ ULONG Position;
+
+ /* Try to find clear bits */
+ Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
+
+ /* Did we get something? */
+ if (Position != MAXULONG)
{
- /* Set from start bit to the end of the byte */
- *lpOut++ |= 0xff << (StartingIndex & 7);
- NumberToSet -= (8 - (StartingIndex & 7));
+ /* Yes, set the bits */
+ RtlSetBits(BitMapHeader, Position, NumberToFind);
}
- else
- {
- /* Set from the start bit, possibly into the next byte also */
- USHORT initialWord = NTDLL_maskBits[NumberToSet] << (StartingIndex & 7);
- *lpOut++ |= (initialWord & 0xff);
- *lpOut |= (initialWord >> 8);
- return;
- }
- }
-
- /* Set bits up to complete byte count */
- if (NumberToSet >> 3)
- {
- memset(lpOut, 0xff, NumberToSet >> 3);
- lpOut = lpOut + (NumberToSet >> 3);
- }
-
- /* Set remaining bits, if any */
- if (NumberToSet & 0x7)
- *lpOut |= NTDLL_maskBits[NumberToSet & 0x7];
+ /* Return what we found */
+ return Position;
}
-
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlTestBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
+ULONG
+NTAPI
+RtlFindSetBitsAndClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
{
- PUCHAR Ptr;
+ ULONG Position;
- if (BitNumber >= BitMapHeader->SizeOfBitMap)
- return FALSE;
+ /* Try to find set bits */
+ Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
+ /* Did we get something? */
+ if (Position != MAXULONG)
+ {
+ /* Yes, clear the bits */
+ RtlClearBits(BitMapHeader, Position, NumberToFind);
+ }
- return (BOOLEAN)(*Ptr & (1 << (BitNumber % 8)));
+ /* Return what we found */
+ return Position;
}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
+ULONG
+NTAPI
+RtlFindNextForwardRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
{
- return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
+ ULONG Length;
+
+ /* Assume a set run first, count it's length */
+ Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
+ *StartingRunIndex = FromIndex;
+
+ /* Now return the length of the run */
+ return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
+ULONG
+NTAPI
+RtlFindNextForwardRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
{
+ ULONG Length;
- if (BitMapHeader)
- return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
- return 0;
+ /* Assume a clear run first, count it's length */
+ Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
+ *StartingRunIndex = FromIndex;
+
+ /* Now return the length of the run */
+ return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
}
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
+ULONG
+NTAPI
+RtlFindFirstRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
{
- ULONG ulPos;
+ return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
+}
- ulPos = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
- if (ulPos != MAXULONG)
- RtlSetBits(BitMapHeader, ulPos, NumberToFind);
- return ulPos;
+ULONG
+NTAPI
+RtlFindLastBackwardRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ UNIMPLEMENTED;
+ return 0;
}
-/*
- * @implemented
- */
-CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
+
+ULONG
+NTAPI
+RtlFindClearRuns(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PRTL_BITMAP_RUN RunArray,
+ IN ULONG SizeOfRunArray,
+ IN BOOLEAN LocateLongestRuns)
{
- signed char ret = 32;
- DWORD dw;
+ ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
- if (!(dw = (DWORD)(ulLong >> 32)))
- {
- ret = 0;
- dw = (DWORD)ulLong;
- }
- if (dw & 0xffff0000)
+ /* Loop the runs */
+ for (Run = 0; Run < SizeOfRunArray; Run++)
{
- dw >>= 16;
- ret += 16;
+ /* Look for a run */
+ NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
+ FromIndex,
+ &StartingIndex);
+
+ /* Nothing more found? Quit looping. */
+ if (NumberOfBits == 0) break;
+
+ /* Add another run */
+ RunArray[Run].StartingIndex = StartingIndex;
+ RunArray[Run].NumberOfBits = NumberOfBits;
+
+ /* Update smallest run */
+ if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
+ {
+ SmallestRun = Run;
+ }
+
+ /* Advance bits */
+ FromIndex += NumberOfBits;
}
- if (dw & 0xff00)
+
+ /* Check if we are finished */
+ if (Run < SizeOfRunArray || !LocateLongestRuns)
{
- dw >>= 8;
- ret += 8;
+ /* Return the number of found runs */
+ return Run;
}
- if (dw & 0xf0)
+
+ while (1)
{
- dw >>= 4;
- ret += 4;
+ /* Look for a run */
+ NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
+ FromIndex,
+ &StartingIndex);
+
+ /* Nothing more found? Quit looping. */
+ if (NumberOfBits == 0) break;
+
+ /* Check if we have something to update */
+ if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
+ {
+ /* Update smallest run */
+ RunArray[SmallestRun].StartingIndex = StartingIndex;
+ RunArray[SmallestRun].NumberOfBits = NumberOfBits;
+
+ /* Loop all runs */
+ for (Run = 0; Run < SizeOfRunArray; Run++)
+ {
+ /*Is this the new smallest run? */
+ if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
+ {
+ /* Set it as new smallest run */
+ SmallestRun = Run;
+ }
+ }
+ }
+
+ /* Advance bits */
+ FromIndex += NumberOfBits;
}
- return ret + NTDLL_mostSignificant[dw];
+
+ return Run;
}
-/*
- * @implemented
- */
-CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
+ULONG
+NTAPI
+RtlFindLongestRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
{
- signed char ret = 0;
- DWORD dw;
+ ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
- if (!(dw = (DWORD)ulLong))
- {
- ret = 32;
- if (!(dw = (DWORD)(ulLong >> 32))) return -1;
- }
- if (!(dw & 0xffff))
+ while (1)
{
- dw >>= 16;
- ret += 16;
- }
- if (!(dw & 0xff))
- {
- dw >>= 8;
- ret += 8;
+ /* Look for a run */
+ NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
+ FromIndex,
+ &Index);
+
+ /* Nothing more found? Quit looping. */
+ if (NumberOfBits == 0) break;
+
+ /* Was that the longest run? */
+ if (NumberOfBits > MaxNumberOfBits)
+ {
+ /* Update values */
+ MaxNumberOfBits = NumberOfBits;
+ *StartingIndex = Index;
+ }
+
+ /* Advance bits */
+ FromIndex += NumberOfBits;
}
- if (!(dw & 0x0f))
+
+ return MaxNumberOfBits;
+}
+
+ULONG
+NTAPI
+RtlFindLongestRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
+{
+ ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+
+ while (1)
{
- dw >>= 4;
- ret += 4;
+ /* Look for a run */
+ NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
+ FromIndex,
+ &Index);
+
+ /* Nothing more found? Quit looping. */
+ if (NumberOfBits == 0) break;
+
+ /* Was that the longest run? */
+ if (NumberOfBits > MaxNumberOfBits)
+ {
+ /* Update values */
+ MaxNumberOfBits = NumberOfBits;
+ *StartingIndex = Index;
+ }
+
+ /* Advance bits */
+ FromIndex += NumberOfBits;
}
- return ret + NTDLL_leastSignificant[dw & 0x0f];
+
+ return MaxNumberOfBits;
}
-/* EOF */
projects / reactos.git / commitdiff