What about BitScanForward / BitScanReverse?
Alex Ionescu wrote: > What about bsr and bsl? > > On 2009-12-07, at 8:02 PM, [email protected] 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 ([email protected]) >> */ >> >> /* 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 > [email protected] > http://www.reactos.org/mailman/listinfo/ros-dev > > _______________________________________________ Ros-dev mailing list [email protected] http://www.reactos.org/mailman/listinfo/ros-dev
