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
