[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.
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@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=4... ============================================================================== --- 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=4446... ============================================================================== --- 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; +}
-
tkreuzer＠svn.reactos.org