[ros-dev] [ros-diffs] [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.
Timo Kreuzer
timo.kreuzer at web.de
Tue Dec 8 02:43:53 CET 2009
What about BitScanForward / BitScanReverse?
Alex Ionescu wrote:
> What about bsr and bsl?
>
> On 2009-12-07, at 8:02 PM, tkreuzer at svn.reactos.org wrote:
>
>
>> 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&r1=44463&r2=44464&view=diff
>> ==============================================================================
>> --- 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 at 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=44464&r1=44463&r2=44464&view=diff
>> ==============================================================================
>> --- 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=44464&r1=44463&r2=44464&view=diff
>> ==============================================================================
>> --- 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;
>> +}
>>
>>
>>
>
> Best regards,
> Alex Ionescu
>
>
> _______________________________________________
> Ros-dev mailing list
> Ros-dev at reactos.org
> http://www.reactos.org/mailman/listinfo/ros-dev
>
>
More information about the Ros-dev
mailing list