From 66fe9a07936be00cc41e679b42ced7b84304a85a Mon Sep 17 00:00:00 2001 From: Timo Kreuzer Date: Tue, 8 Dec 2009 01:02:36 +0000 Subject: [PATCH] [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. svn path=/trunk/; revision=44464 --- reactos/lib/rtl/bitmap.c | 1369 ++++++++++++++------------------- reactos/tools/mkhive/mkhive.h | 4 + reactos/tools/mkhive/rtl.c | 22 + 3 files changed, 603 insertions(+), 792 deletions(-) diff --git a/reactos/lib/rtl/bitmap.c b/reactos/lib/rtl/bitmap.c index f4606595e65..b06f446fe03 100644 --- a/reactos/lib/rtl/bitmap.c +++ b/reactos/lib/rtl/bitmap.c @@ -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@reactos.org) */ /* INCLUDES *****************************************************************/ @@ -12,965 +13,749 @@ #define NDEBUG #include -/* 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 */ diff --git a/reactos/tools/mkhive/mkhive.h b/reactos/tools/mkhive/mkhive.h index d1a107021c3..b86687c95ee 100644 --- a/reactos/tools/mkhive/mkhive.h +++ b/reactos/tools/mkhive/mkhive.h @@ -47,6 +47,10 @@ #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( IN OUT PUNICODE_STRING UniDest, diff --git a/reactos/tools/mkhive/rtl.c b/reactos/tools/mkhive/rtl.c index 85fc04b6327..e9ed22b66e0 100644 --- a/reactos/tools/mkhive/rtl.c +++ b/reactos/tools/mkhive/rtl.c @@ -185,3 +185,25 @@ RtlAssert(PVOID FailedAssertion, //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; +} -- 2.17.1