[tkreuzer] 44464: [RTL] Rewrite the rtl bitmap implementation. The old one was a little .... suboptimal. The new one should outperform the old one by several orders of magnitude, especially RtlFindClearBits that was literally searching bit by bit.
8 Dec
2009
8 Dec
'09
1:02 a.m.
Author: tkreuzer
Date: Tue Dec 8 02:02:36 2009
New Revision: 44464
URL: http://svn.reactos.org/svn/reactos?rev=44464&view=rev
Log:
[RTL]
Rewrite the rtl bitmap implementation.
The old one was a little .... suboptimal. The new one should outperform the old one by
several orders of magnitude, especially RtlFindClearBits that was literally searching bit
by bit.
Modified:
trunk/reactos/lib/rtl/bitmap.c
trunk/reactos/tools/mkhive/mkhive.h
trunk/reactos/tools/mkhive/rtl.c
Modified: trunk/reactos/lib/rtl/bitmap.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/bitmap.c?rev=44464…
==============================================================================
--- trunk/reactos/lib/rtl/bitmap.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/bitmap.c [iso-8859-1] Tue Dec 8 02:02:36 2009
@@ -1,8 +1,9 @@
-/* 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(a)reactos.org)
*/
/* INCLUDES *****************************************************************/
@@ -12,965 +13,749 @@
#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
+
+/* DATA *********************************************************************/
+
+/* 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 */
};
-/* 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
-};
-
-/* 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
-};
-
-/* 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)
+
+/* PRIVATE FUNCTIONS ********************************************************/
+
+static __inline__
+ULONG
+RtlpGetLengthOfRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG MaxLength)
+{
+ ULONG Value, BitPos, Length;
+ PULONG Buffer, MaxBuffer;
+
+ /* Calculate positions */
+ Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+ BitPos = StartingIndex & 31;
+
+ /* Calculate the maximum length */
+ MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+ MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+
+ /* Clear the bits that don't belong to this run */
+ Value = *Buffer++ >> BitPos << BitPos;
+
+ /* Skip all clear ULONGs */
+ while (Value == 0 && Buffer < MaxBuffer)
+ {
+ Value = *Buffer++;
+ }
+
+ /* Did we reach the end? */
+ if (Value == 0)
+ {
+ /* Return maximum length */
+ return MaxLength;
+ }
+
+ /* 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 __inline__
+ULONG
+RtlpGetLengthOfRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG MaxLength)
+{
+ ULONG InvValue, BitPos, Length;
+ PULONG Buffer, MaxBuffer;
+
+ /* Calculate positions */
+ Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+ BitPos = StartingIndex & 31;
+
+ /* Calculate the maximum length */
+ MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+ MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+
+ /* 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)
+ {
+ InvValue = ~(*Buffer++);
+ }
+
+ /* Did we reach the end? */
+ if (InvValue == 0)
+ {
+ /* Yes, return maximum */
+ return MaxLength;
+ }
+
+ /* We hit a clear bit, check how many set bits are left */
+ BitScanForward(&BitPos, InvValue);
+
+ /* 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;
+}
+
+
+/* PUBLIC FUNCTIONS **********************************************************/
+
+CCHAR
+NTAPI
+RtlFindMostSignificantBit(ULONGLONG Value)
+{
+ ULONG Position;
+
+ if (BitScanReverse(&Position, Value >> 32))
+ {
+ return Position + 32;
+ }
+ else if (BitScanReverse(&Position, (ULONG)Value))
+ {
+ return Position;
+ }
+
return -1;
- return 1;
-}
-
-static
-ULONG
-WINAPI
-NTDLL_FindRuns(PRTL_BITMAP lpBits,
- PRTL_BITMAP_RUN lpSeries,
- ULONG ulCount,
- BOOLEAN bLongest,
- ULONG (*fn)(PRTL_BITMAP,ULONG,PULONG))
-{
- BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
- ULONG ulPos = 0, ulRuns = 0;
-
- if (!ulCount)
- return MAXULONG;
-
- while (ulPos < lpBits->SizeOfBitMap)
- {
- /* Find next set/clear run */
- ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
-
- if (ulNextPos == MAXULONG)
- break;
-
- if (bLongest && ulRuns == ulCount)
- {
- /* 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;
- }
- }
- else
- {
- /* Append to found runs */
- lpSeries[ulRuns].StartingIndex = ulNextPos;
- lpSeries[ulRuns].NumberOfBits = ulSize;
- ulRuns++;
-
- if (!bLongest && ulRuns == ulCount)
- break;
- }
- ulPos = ulNextPos + ulSize;
- }
- return ulRuns;
-}
-
-static
-ULONG
-NTDLL_FindSetRun(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);
-
- while (1)
- {
- /* Check bits in first byte */
- const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
- const BYTE bFirst = *lpOut & bMask;
-
- if (bFirst)
- {
- /* 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;
- }
- 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)
- {
- *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
- return ulFoundAt;
- }
- lpOut++;
- }
-
- /* Count remaining contiguous bits, if any */
- if (*lpOut & 1)
- {
- ULONG ulOffset = 0;
-
- for (;ulOffset < 7u; ulOffset++)
- {
- if (!(*lpOut & (1 << ulOffset)))
- break;
- ulCount++;
- }
- }
- *lpSize = ulCount;
- return ulFoundAt;
-}
-
-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);
-
- while (1)
- {
- /* Check bits in first byte */
- const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
- const BYTE bFirst = (~*lpOut) & bMask;
-
- if (bFirst)
- {
- /* 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;
- }
- 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)
- {
- *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
- return ulFoundAt;
- }
- lpOut++;
- }
-
- /* Count remaining contiguous bits, if any */
- if (!(*lpOut & 1))
- {
- ULONG ulOffset = 0;
-
- for (;ulOffset < 7u; ulOffset++)
- {
- if (*lpOut & (1 << ulOffset))
- break;
- ulCount++;
- }
- }
- *lpSize = ulCount;
- return ulFoundAt;
-}
-
-/* FUNCTIONS ****************************************************************/
-
-/*
- * @implemented
- */
+}
+
+CCHAR
+NTAPI
+RtlFindLeastSignificantBit(ULONGLONG Value)
+{
+ ULONG Position;
+
+ if (BitScanForward(&Position, (ULONG)Value))
+ {
+ return Position;
+ }
+ else if (BitScanForward(&Position, Value >> 32))
+ {
+ return Position + 32;
+ }
+
+ return -1;
+}
+
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
- */
+VOID
+NTAPI
+RtlClearAllBits(
+ IN OUT PRTL_BITMAP BitMapHeader)
+{
+ ULONG LengthInUlongs;
+
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
+}
+
+VOID
+NTAPI
+RtlSetAllBits(
+ IN OUT PRTL_BITMAP BitMapHeader)
+{
+ ULONG LengthInUlongs;
+
+ LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+ RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
+}
+
+VOID
+NTAPI
+RtlClearBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
+{
+ ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+ BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber &
31));
+}
+
+VOID
+NTAPI
+RtlSetBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
+{
+ ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+ BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
+}
+
+VOID
+NTAPI
+RtlClearBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG NumberToClear)
+{
+ ULONG Bits, Mask;
+ PULONG Buffer;
+
+ ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
+
+ /* Calculate buffer start and first bit index */
+ Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+ Bits = StartingIndex & 31;
+
+ /* Are we unaligned? */
+ if (Bits)
+ {
+ /* Create an inverse mask by shifting MAXULONG */
+ Mask = MAXULONG << Bits;
+
+ /* This is what's left in the first ULONG */
+ Bits = 32 - Bits;
+
+ /* Even less bits to clear? */
+ if (NumberToClear < Bits)
+ {
+ /* Calculate how many bits are left */
+ Bits -= NumberToClear;
+
+ /* Fixup the mask on the high side */
+ Mask = Mask << Bits >> Bits;
+
+ /* Clear bits and return */
+ *Buffer &= ~Mask;
+ return;
+ }
+
+ /* Clear bits */
+ *Buffer &= ~Mask;
+
+ /* Update buffer and left bits */
+ Buffer++;
+ NumberToClear -= Bits;
+ }
+
+ /* Clear all full ULONGs */
+ RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
+ Buffer += NumberToClear >> 5;
+
+ /* Clear what's left */
+ NumberToClear &= 31;
+ Mask = MAXULONG << NumberToClear;
+ *Buffer &= Mask;
+}
+
+VOID
+NTAPI
+RtlSetBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG NumberToSet)
+{
+ ULONG Bits, Mask;
+ PULONG Buffer;
+
+ ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
+
+ /* Calculate buffer start and first bit index */
+ Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+ Bits = StartingIndex & 31;
+
+ /* Are we unaligned? */
+ if (Bits)
+ {
+ /* Create a mask by shifting MAXULONG */
+ Mask = MAXULONG << Bits;
+
+ /* This is what's left in the first ULONG */
+ Bits = 32 - Bits;
+
+ /* Even less bits to clear? */
+ if (NumberToSet < Bits)
+ {
+ /* Calculate how many bits are left */
+ Bits -= NumberToSet;
+
+ /* Fixup the mask on the high side */
+ Mask = Mask << Bits >> Bits;
+
+ /* Set bits and return */
+ *Buffer |= Mask;
+ return;
+ }
+
+ /* Set bits */
+ *Buffer |= Mask;
+
+ /* Update buffer and left bits */
+ Buffer++;
+ NumberToSet -= Bits;
+ }
+
+ /* Set all full ULONGs */
+ RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
+ Buffer += NumberToSet >> 5;
+
+ /* Set what's left */
+ NumberToSet &= 31;
+ Mask = MAXULONG << NumberToSet;
+ *Buffer |= ~Mask;
+}
+
BOOLEAN
NTAPI
-RtlAreBitsClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG StartingIndex,
- IN ULONG Length)
-{
- 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;
-}
-
-
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlAreBitsSet(PRTL_BITMAP BitMapHeader,
- ULONG StartingIndex,
- ULONG Length)
-{
- 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;
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
-{
- memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31)
>> 3);
-}
-
-/*
- * @implemented
- */
-VOID
-NTAPI
-RtlClearBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
-{
- PUCHAR Ptr;
-
- if (BitNumber >= BitMapHeader->SizeOfBitMap) return;
-
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
- *Ptr &= ~(1 << (BitNumber % 8));
-}
-
-/*
- * @implemented
- */
-VOID
-NTAPI
-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));
-
- *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];
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearBits(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
-{
- ULONG ulPos, ulEnd;
-
- if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
+RtlTestBit(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG BitNumber)
+{
+ ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
+ return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31))
& 1;
+}
+
+BOOLEAN
+NTAPI
+RtlAreBitsClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG Length)
+{
+ return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
+}
+
+BOOLEAN
+NTAPI
+RtlAreBitsSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG Length)
+{
+ return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
+}
+
+ULONG
+NTAPI
+RtlNumberOfSetBits(
+ IN PRTL_BITMAP BitMapHeader)
+{
+ PUCHAR Byte, MaxByte;
+ ULONG BitCount = 0;
+
+ Byte = (PUCHAR)BitMapHeader->Buffer;
+ MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
+
+ do
+ {
+ BitCount += BitCountTable[*Byte++];
+ }
+ while (Byte <= MaxByte);
+
+ return BitCount;
+}
+
+ULONG
+NTAPI
+RtlNumberOfClearBits(
+ IN PRTL_BITMAP BitMapHeader)
+{
+ /* Do some math */
+ return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
+}
+
+ULONG
+NTAPI
+RtlFindClearBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
+{
+ ULONG CurrentBit, CurrentLength;
+
+ /* Check for valid parameters */
+ if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+ {
+ return MAXULONG;
+ }
+
+ /* Check for trivial case */
+ if (NumberToFind == 0)
+ {
+ return HintIndex;
+ }
+
+ /* 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)
+ {
+ 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;
+ }
+
+ /* Nothing found */
return MAXULONG;
-
- ulEnd = BitMapHeader->SizeOfBitMap;
-
- if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
- HintIndex = 0;
-
- ulPos = HintIndex;
-
- while (ulPos < ulEnd)
- {
- /* FIXME: This could be made a _lot_ more efficient */
- if (RtlAreBitsClear(BitMapHeader, ulPos, NumberToFind))
- return ulPos;
-
- /* Start from the beginning if we hit the end and started from HintIndex */
- if (ulPos == ulEnd - 1 && HintIndex)
- {
- ulEnd = HintIndex;
- ulPos = HintIndex = 0;
- }
- 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);
-}
-
-/*
- * @unimplemented
- */
-ULONG NTAPI
-RtlFindLastBackwardRunClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
-{
- UNIMPLEMENTED;
- return 0;
-}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
- IN ULONG FromIndex,
- IN PULONG StartingRunIndex)
-{
- ULONG ulSize = 0;
-
- if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap &&
StartingRunIndex)
- *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize);
-
- return ulSize;
-}
-
-/*
- * @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;
+}
+
+ULONG
+NTAPI
+RtlFindSetBits(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
+{
+ ULONG CurrentBit, CurrentLength;
+
+ /* Check for valid parameters */
+ if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+ {
+ return MAXULONG;
+ }
+
+ /* Check for trivial case */
+ if (NumberToFind == 0)
+ {
+ return HintIndex;
+ }
+
+ /* 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)
+ {
+ /* 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;
+ }
+
+ CurrentBit += CurrentLength;
+ }
+
+ /* Nothing found */
+ return MAXULONG;
+}
+
+ULONG
+NTAPI
+RtlFindClearBitsAndSet(
+ PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
+{
+ ULONG Position;
+
+ /* Try to find clear bits */
+ Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
+
+ /* Did we get something? */
+ if (Position != MAXULONG)
+ {
+ /* Yes, set the bits */
+ RtlSetBits(BitMapHeader, Position, NumberToFind);
+ }
+
+ /* Return what we found */
+ return Position;
+}
+
+ULONG
+NTAPI
+RtlFindSetBitsAndClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG NumberToFind,
+ IN ULONG HintIndex)
+{
+ ULONG Position;
+
+ /* Try to find set bits */
+ Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
+
+ /* Did we get something? */
+ if (Position != MAXULONG)
+ {
+ /* Yes, clear the bits */
+ RtlClearBits(BitMapHeader, Position, NumberToFind);
+ }
+
+ /* Return what we found */
+ return Position;
+}
+
+ULONG
+NTAPI
+RtlFindNextForwardRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ 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);
+}
+
+ULONG
+NTAPI
+RtlFindNextForwardRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ ULONG Length;
+
+ /* 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);
+}
+
+ULONG
+NTAPI
+RtlFindFirstRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
+{
+ return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
+}
+
+ULONG
+NTAPI
+RtlFindLastBackwardRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ UNIMPLEMENTED;
return 0;
- }
-
- Index = *StartingIndex;
- Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
- Mask = 1 << (Index & 0x1F);
-
- /* Skip clear bits */
- for (; Index < Size && ~*Ptr & Mask; Index++)
- {
- Mask <<= 1;
-
- if (Mask == 0)
- {
- Mask = 1;
- Ptr++;
- }
- }
-
- /* 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++;
- }
- }
-
- return Count;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
-{
- /* 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;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
-{
- /* 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;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindSetBits(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
-{
- ULONG ulPos, ulEnd;
-
- if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
- return MAXULONG;
-
- ulEnd = BitMapHeader->SizeOfBitMap;
-
- if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
- HintIndex = 0;
-
- ulPos = HintIndex;
-
- while (ulPos < ulEnd)
- {
- /* FIXME: This could be made a _lot_ more efficient */
- if (RtlAreBitsSet(BitMapHeader, ulPos, NumberToFind))
- return ulPos;
-
- /* Start from the beginning if we hit the end and had a hint */
- if (ulPos == ulEnd - 1 && HintIndex)
- {
- ulEnd = HintIndex;
- ulPos = HintIndex = 0;
- }
- else
- ulPos++;
- }
- return MAXULONG;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
-{
- ULONG ulPos;
-
- ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
- if (ulPos != MAXULONG)
- RtlClearBits(BitMapHeader, ulPos, NumberToFind);
- return ulPos;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
-{
- ULONG ulSet = 0;
-
- if (BitMapHeader)
- {
- LPBYTE lpOut = (BYTE *)BitMapHeader->Buffer;
- ULONG Length, ulRemainder;
- BYTE bMasked;
-
- Length = BitMapHeader->SizeOfBitMap >> 3;
- ulRemainder = BitMapHeader->SizeOfBitMap & 0x7;
-
- while (Length--)
- {
- ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
- ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
- lpOut++;
- }
-
- if (ulRemainder)
- {
- bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
- ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
- ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
- }
- }
- return ulSet;
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetAllBits(IN OUT PRTL_BITMAP BitMapHeader)
-{
- memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31)
>> 3);
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
-{
- PUCHAR Ptr;
-
- if (BitNumber >= BitMapHeader->SizeOfBitMap)
- return;
-
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
-
- *Ptr |= (1 << (BitNumber % 8));
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlSetBits(PRTL_BITMAP BitMapHeader,
- ULONG StartingIndex,
- ULONG NumberToSet)
-{
- 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)
- {
- /* Set from start bit to the end of the byte */
- *lpOut++ |= 0xff << (StartingIndex & 7);
- NumberToSet -= (8 - (StartingIndex & 7));
- }
- 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];
-}
-
-
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlTestBit(PRTL_BITMAP BitMapHeader,
- ULONG BitNumber)
-{
- PUCHAR Ptr;
-
- if (BitNumber >= BitMapHeader->SizeOfBitMap)
- return FALSE;
-
- Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
-
- return (BOOLEAN)(*Ptr & (1 << (BitNumber % 8)));
-}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
- PULONG StartingIndex)
-{
- return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
-}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
-{
-
- if (BitMapHeader)
- return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
- return 0;
-}
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
- ULONG NumberToFind,
- ULONG HintIndex)
-{
- ULONG ulPos;
-
- ulPos = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
- if (ulPos != MAXULONG)
- RtlSetBits(BitMapHeader, ulPos, NumberToFind);
- return ulPos;
-}
-
-/*
- * @implemented
- */
-CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
-{
- signed char ret = 32;
- DWORD dw;
-
- if (!(dw = (DWORD)(ulLong >> 32)))
- {
- ret = 0;
- dw = (DWORD)ulLong;
- }
- if (dw & 0xffff0000)
- {
- dw >>= 16;
- ret += 16;
- }
- if (dw & 0xff00)
- {
- dw >>= 8;
- ret += 8;
- }
- if (dw & 0xf0)
- {
- dw >>= 4;
- ret += 4;
- }
- return ret + NTDLL_mostSignificant[dw];
-}
-
-/*
- * @implemented
- */
-CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
-{
- signed char ret = 0;
- DWORD dw;
-
- if (!(dw = (DWORD)ulLong))
- {
- ret = 32;
- if (!(dw = (DWORD)(ulLong >> 32))) return -1;
- }
- if (!(dw & 0xffff))
- {
- dw >>= 16;
- ret += 16;
- }
- if (!(dw & 0xff))
- {
- dw >>= 8;
- ret += 8;
- }
- if (!(dw & 0x0f))
- {
- dw >>= 4;
- ret += 4;
- }
- return ret + NTDLL_leastSignificant[dw & 0x0f];
-}
-
-/* EOF */
+}
+
+
+ULONG
+NTAPI
+RtlFindClearRuns(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PRTL_BITMAP_RUN RunArray,
+ IN ULONG SizeOfRunArray,
+ IN BOOLEAN LocateLongestRuns)
+{
+ ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
+
+ /* Loop the runs */
+ for (Run = 0; Run < SizeOfRunArray; Run++)
+ {
+ /* 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;
+ }
+
+ /* Check if we are finished */
+ if (Run < SizeOfRunArray || !LocateLongestRuns)
+ {
+ /* Return the number of found runs */
+ return Run;
+ }
+
+ while (1)
+ {
+ /* 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 Run;
+}
+
+ULONG
+NTAPI
+RtlFindLongestRunClear(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
+{
+ ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+
+ while (1)
+ {
+ /* 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;
+ }
+
+ return MaxNumberOfBits;
+}
+
+ULONG
+NTAPI
+RtlFindLongestRunSet(
+ IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
+{
+ ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+
+ while (1)
+ {
+ /* 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 MaxNumberOfBits;
+}
+
Modified: trunk/reactos/tools/mkhive/mkhive.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/tools/mkhive/mkhive.h?rev=…
==============================================================================
--- trunk/reactos/tools/mkhive/mkhive.h [iso-8859-1] (original)
+++ trunk/reactos/tools/mkhive/mkhive.h [iso-8859-1] Tue Dec 8 02:02:36 2009
@@ -46,6 +46,10 @@
#define STATUS_OBJECT_NAME_NOT_FOUND ((NTSTATUS)0xC0000034)
#define STATUS_INVALID_PARAMETER_2 ((NTSTATUS)0xC00000F0)
#define STATUS_BUFFER_OVERFLOW ((NTSTATUS)0x80000005)
+
+unsigned char BitScanForward(ULONG * Index, const unsigned long Mask);
+unsigned char BitScanReverse(ULONG * const Index, const unsigned long Mask);
+#define RtlFillMemoryUlong(dst, len, val) memset(dst, val, len)
NTSTATUS NTAPI
RtlAnsiStringToUnicodeString(
Modified: trunk/reactos/tools/mkhive/rtl.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/tools/mkhive/rtl.c?rev=444…
==============================================================================
--- trunk/reactos/tools/mkhive/rtl.c [iso-8859-1] (original)
+++ trunk/reactos/tools/mkhive/rtl.c [iso-8859-1] Tue Dec 8 02:02:36 2009
@@ -185,3 +185,25 @@
//DbgBreakPoint();
}
+
+unsigned char BitScanForward(ULONG * Index, unsigned long Mask)
+{
+ *Index = 0;
+ while (Mask && ((Mask & 1) == 0))
+ {
+ Mask >>= 1;
+ ++(*Index);
+ }
+ return Mask ? 1 : 0;
+}
+
+unsigned char BitScanReverse(ULONG * const Index, unsigned long Mask)
+{
+ *Index = 0;
+ while (Mask && ((Mask & (1 << 31)) == 0))
+ {
+ Mask <<= 1;
+ ++(*Index);
+ }
+ return Mask ? 1 : 0;
+}
5499
days inactive
5499
days old
0 comments
1 participants
participants (1)
-
tkreuzer＠svn.reactos.org