[ion] 22679: - Sync RtlBitmap* implementation with WINE: Fixes 278 regression failures (for a total of 0 now). - Also adds implementations for RtlFindMostSignificantBit , RtlFindLeastSignificantBit, RtlFindNextForwardRunClear, RtlFindClearRuns. - The RtlBitmap* package is essential for compatibility with NTFS.SYS and other File System Drivers, but these fixes should not really improve user-mode app. compat.
Author: ion Date: Thu Jun 29 00:51:51 2006 New Revision: 22679
URL: http://svn.reactos.org/svn/reactos?rev=22679&view=rev Log: - Sync RtlBitmap* implementation with WINE: Fixes 278 regression failures (for a total of 0 now). - Also adds implementations for RtlFindMostSignificantBit , RtlFindLeastSignificantBit, RtlFindNextForwardRunClear, RtlFindClearRuns. - The RtlBitmap* package is essential for compatibility with NTFS.SYS and other File System Drivers, but these fixes should not really improve user-mode app. compat.
Modified: trunk/reactos/lib/rtl/bitmap.c
Modified: trunk/reactos/lib/rtl/bitmap.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/bitmap.c?rev=22679&... ============================================================================== --- trunk/reactos/lib/rtl/bitmap.c (original) +++ trunk/reactos/lib/rtl/bitmap.c Thu Jun 29 00:51:51 2006 @@ -12,64 +12,347 @@ #define NDEBUG #include <debug.h>
- /* MACROS *******************************************************************/
-#define MASK(Count, Shift) \ - ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift)) - +/* Bits set from LSB to MSB; used as mask for runs < 8 bits */ +static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 }; + +/* Number of set bits for each value of a nibble; used for counting */ +static const BYTE NTDLL_nibbleBitCount[16] = { + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 +}; + +/* First set bit in a nibble; used for determining least significant bit */ +static const BYTE NTDLL_leastSignificant[16] = { + 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 +}; + +/* 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 +NTDLL_RunSortFn(const void *lhs, + const void *rhs) +{ + if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits) + return -1; + return 1; +} + +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 ~0U; + + while (ulPos < lpBits->SizeOfBitMap) + { + /* Find next set/clear run */ + ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize); + + if (ulNextPos == ~0U) + 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 ~0U; + } + + /* 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 ~0U; + } + + /* 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 */ -VOID NTAPI -RtlInitializeBitMap(PRTL_BITMAP BitMapHeader, - PULONG BitMapBuffer, - ULONG SizeOfBitMap) -{ - BitMapHeader->SizeOfBitMap = SizeOfBitMap; - BitMapHeader->Buffer = BitMapBuffer; -} - - -/* - * @implemented - */ -BOOLEAN NTAPI -RtlAreBitsClear(PRTL_BITMAP BitMapHeader, - ULONG StartingIndex, - ULONG Length) -{ - ULONG Size; - ULONG Shift; - ULONG Count; - PULONG Ptr; - - Size = BitMapHeader->SizeOfBitMap; - if (StartingIndex >= Size || - !Length || - (StartingIndex + Length > Size)) - return FALSE; - - Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32); - while (Length) - { - /* Get bit shift in current ulong */ - Shift = StartingIndex & 0x1F; - - /* Get number of bits to check in current ulong */ - Count = (Length > 32 - Shift) ? 32 - Shift : Length; - - /* Check ulong */ - if (*Ptr++ & MASK(Count, Shift)) +VOID +NTAPI +RtlInitializeBitMap(IN PRTL_BITMAP BitMapHeader, + IN PULONG BitMapBuffer, + IN ULONG SizeOfBitMap) +{ + /* Setup the bitmap header */ + BitMapHeader->SizeOfBitMap = SizeOfBitMap; + BitMapHeader->Buffer = BitMapBuffer; +} + +/* + * @implemented + */ +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; - - Length -= Count; - StartingIndex += Count; - } - + } + + /* Check remaining bits, if any */ + if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder]) + return FALSE; return TRUE; }
@@ -82,107 +365,139 @@ ULONG StartingIndex, ULONG Length) { - ULONG Size; - ULONG Shift; - ULONG Count; - PULONG Ptr; - - Size = BitMapHeader->SizeOfBitMap; - if (StartingIndex >= Size || - Length == 0 || - (StartingIndex + Length > Size)) + LPBYTE lpOut; + ULONG ulRemainder; + + + if (!BitMapHeader || !Length || + StartingIndex >= BitMapHeader->SizeOfBitMap || + Length > BitMapHeader->SizeOfBitMap - StartingIndex) return FALSE;
- Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32); - while (Length) - { - /* Get bit shift in current ulong */ - Shift = StartingIndex & 0x1F; - - /* Get number of bits to check in current ulong */ - Count = (Length > 32 - Shift) ? 32 - Shift : Length; - - /* Check ulong */ - if (~*Ptr++ & MASK(Count, Shift)) + /* 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; - - Length -= Count; - StartingIndex += Count; - } - + } + + /* Check remaining bits, if any */ + if (ulRemainder && + (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder]) + return FALSE; return TRUE; }
/* * @implemented - * - * Note: According to the documentation, SizeOfBitmap is in bits, so the - * ROUND_UP(...) must be divided by the number of bits per byte here. - * This function is exercised by the whole page allocator in npool.c - * which is how i came across this error. */ VOID NTAPI RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader) { - memset(BitMapHeader->Buffer, - 0x00, - ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8); - -} - - -/* - * @implemented - */ -VOID NTAPI + memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3); +} + +/* + * @implemented + */ +VOID +NTAPI RtlClearBit(PRTL_BITMAP BitMapHeader, - ULONG BitNumber) -{ - PULONG Ptr; - - if (BitNumber >= BitMapHeader->SizeOfBitMap) + ULONG BitNumber) +{ + PULONG Ptr; + + if (BitNumber >= BitMapHeader->SizeOfBitMap) return; + + Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32); + *Ptr &= ~(1 << (BitNumber % 32)); +} + +/* + * @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;
- Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32); - - *Ptr &= ~(1 << (BitNumber % 32)); -} - - -/* - * @implemented - */ -VOID NTAPI -RtlClearBits(PRTL_BITMAP BitMapHeader, - ULONG StartingIndex, - ULONG NumberToClear) -{ - ULONG Size; - ULONG Count; - ULONG Shift; - PULONG Ptr; - - Size = BitMapHeader->SizeOfBitMap; - if (StartingIndex >= Size || NumberToClear == 0) - return; - - ASSERT(StartingIndex + NumberToClear <= Size); - - Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32); - while (NumberToClear) - { - /* Bit shift in current ulong */ - Shift = StartingIndex & 0x1F; - - /* Number of bits to change in current ulong */ - Count = (NumberToClear > 32 - Shift ) ? 32 - Shift : NumberToClear; - - /* Adjust ulong */ - *Ptr++ &= ~MASK(Count, Shift); - NumberToClear -= Count; - StartingIndex += Count; - } + /* 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]; }
@@ -194,171 +509,44 @@ ULONG NumberToFind, ULONG HintIndex) { - ULONG Size; - ULONG Index; - ULONG Count; - PULONG Ptr; - ULONG Mask; - ULONG Loop; - ULONG End; - ULONG OriginalHint = HintIndex; - - Size = BitMapHeader->SizeOfBitMap; - if (NumberToFind > Size || NumberToFind == 0) - return -1; - - if (HintIndex >= Size) + ULONG ulPos, ulEnd; + + if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap) + return ~0U; + + ulEnd = BitMapHeader->SizeOfBitMap; + + if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap) HintIndex = 0;
- /* Initialize the values to the hint location. */ - Index = HintIndex; - Ptr = BitMapHeader->Buffer + (Index / 32); - Mask = 1 << (Index & 0x1F); - End = Size; - - /* The outer loop does the magic of first searching from the - * hint to the bitmap end and then going again from beginning - * of the bitmap to the hint location. - */ - for (Loop = 0; Loop < 2; Loop++) - { - while (HintIndex < End) - { - /* Count clear bits */ - for (Count = 0; Index < End && ~*Ptr & Mask; Index++) - { - if (++Count >= NumberToFind) - return HintIndex; - - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - /* Skip set bits */ - for (; Index < End && *Ptr & Mask; Index++) - { - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - HintIndex = Index; - } - - /* Optimalization */ - if (OriginalHint == 0) - break; - - /* Initialize the values for the beginning -> hint loop. */ - HintIndex = Index = 0; - End = OriginalHint + NumberToFind - 1; - End = End > Size ? Size : End; - Ptr = BitMapHeader->Buffer; - Mask = 1; - } - - return (ULONG)-1; -} - - -/* - * @implemented - */ -ULONG NTAPI -RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader, - ULONG NumberToFind, - ULONG HintIndex) -{ - ULONG Index; - - Index = RtlFindClearBits(BitMapHeader, - NumberToFind, - HintIndex); - if (Index != (ULONG)-1) - { - RtlSetBits(BitMapHeader, - Index, - NumberToFind); - } - - return Index; -} - - -/* - * @implemented - */ -ULONG NTAPI -RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader, - PULONG StartingIndex) -{ - ULONG Size; - ULONG Index; - ULONG Count; - PULONG Ptr; - ULONG Mask; - - Size = BitMapHeader->SizeOfBitMap; - if (*StartingIndex > Size) - { - *StartingIndex = (ULONG)-1; - return 0; - } - - Index = *StartingIndex; - Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32); - Mask = 1 << (Index & 0x1F); - - /* Skip set bits */ - for (; Index < Size && *Ptr & Mask; Index++) - { - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - /* Return index of first clear bit */ - if (Index >= Size) - { - *StartingIndex = (ULONG)-1; - return 0; - } - else - { - *StartingIndex = Index; - } - - /* Count clear bits */ - for (Count = 0; Index < Size && ~*Ptr & Mask; Index++) - { - Count++; - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - return Count; -} - - -/* - * @unimplemented + 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 ~0U; +} + + + + + + + +/* + * @implemented */ ULONG NTAPI RtlFindClearRuns(PRTL_BITMAP BitMapHeader, @@ -366,8 +554,7 @@ ULONG SizeOfRunArray, BOOLEAN LocateLongestRuns) { - UNIMPLEMENTED; - return 0; + return NTDLL_FindRuns(BitMapHeader, RunArray, SizeOfRunArray, LocateLongestRuns, NTDLL_FindClearRun); }
@@ -383,19 +570,21 @@ return 0; }
- -/* - * @unimplemented +/* + * @implemented */ ULONG NTAPI RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader, IN ULONG FromIndex, IN PULONG StartingRunIndex) { - UNIMPLEMENTED; - return 0; -} - + ULONG ulSize = 0; + + if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap && StartingRunIndex) + *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize); + + return ulSize; +}
/* * @implemented @@ -468,60 +657,15 @@ RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader, PULONG StartingIndex) { - ULONG Size; - PULONG Ptr; - ULONG Index = 0; - ULONG Count; - ULONG Max = 0; - ULONG Start; - ULONG Maxstart = 0; - ULONG Mask = 1; - - Size = BitMapHeader->SizeOfBitMap; - Ptr = (PULONG)BitMapHeader->Buffer; - - while (Index < Size) - { - Start = Index; - - /* Count clear bits */ - for (Count = 0; Index < Size && ~*Ptr & Mask; Index++) - { - Count++; - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - /* Skip set bits */ - for (; Index < Size && *Ptr & Mask; Index++) - { - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - if (Count > Max) - { - Max = Count; - Maxstart = Start; - } - } - - if (StartingIndex != NULL) - { - *StartingIndex = Maxstart; - } - - return Max; + RTL_BITMAP_RUN br; + + if (RtlFindClearRuns(BitMapHeader, &br, 1, TRUE) == 1) + { + if (StartingIndex) + *StartingIndex = br.StartingIndex; + return br.NumberOfBits; + } + return 0; }
@@ -532,60 +676,15 @@ RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader, PULONG StartingIndex) { - ULONG Size; - PULONG Ptr; - ULONG Index = 0; - ULONG Count; - ULONG Max = 0; - ULONG Start; - ULONG Maxstart = 0; - ULONG Mask = 1; - - Size = BitMapHeader->SizeOfBitMap; - Ptr = (PULONG)BitMapHeader->Buffer; - - while (Index < Size) - { - Start = Index; - - /* Count set bits */ - for (Count = 0; Index < Size && *Ptr & Mask; Index++) - { - Count++; - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - /* Skip clear bits */ - for (; Index < Size && ~*Ptr & Mask; Index++) - { - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - if (Count > Max) - { - Max = Count; - Maxstart = Start; - } - } - - if (StartingIndex != NULL) - { - *StartingIndex = Maxstart; - } - - return Max; + RTL_BITMAP_RUN br; + + if (NTDLL_FindRuns(BitMapHeader, &br, 1, TRUE, NTDLL_FindSetRun) == 1) + { + if (StartingIndex) + *StartingIndex = br.StartingIndex; + return br.NumberOfBits; + } + return 0; }
@@ -597,79 +696,34 @@ ULONG NumberToFind, ULONG HintIndex) { - ULONG Size; - ULONG Index; - ULONG Count; - PULONG Ptr; - ULONG Mask; - ULONG Loop; - ULONG End; - ULONG OriginalHint = HintIndex; - - Size = BitMapHeader->SizeOfBitMap; - if (NumberToFind > Size || NumberToFind == 0) - return (ULONG)-1; - - if (HintIndex >= Size) + ULONG ulPos, ulEnd; + + if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap) + return ~0U; + + ulEnd = BitMapHeader->SizeOfBitMap; + + if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap) HintIndex = 0;
- /* Initialize the values to the hint location. */ - Index = HintIndex; - Ptr = BitMapHeader->Buffer + (Index / 32); - Mask = 1 << (Index & 0x1F); - End = Size; - - /* The outer loop does the magic of first searching from the - * hint to the bitmap end and then going again from beginning - * of the bitmap to the hint location. - */ - for (Loop = 0; Loop < 2; Loop++) - { - while (HintIndex < End) - { - /* Count set bits */ - for (Count = 0; Index < End && *Ptr & Mask; Index++) - { - if (++Count >= NumberToFind) - return HintIndex; - - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - /* Skip clear bits */ - for (; Index < End && ~*Ptr & Mask; Index++) - { - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - HintIndex = Index; - } - - /* Optimalization */ - if (OriginalHint == 0) - break; - - /* Initialize the values for the beginning -> hint loop. */ - HintIndex = Index = 0; - End = OriginalHint + NumberToFind - 1; - End = End > Size ? Size : End; - Ptr = BitMapHeader->Buffer; - Mask = 1; - } - - return (ULONG)-1; + 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 ~0U; }
@@ -681,52 +735,16 @@ ULONG NumberToFind, ULONG HintIndex) { - ULONG Index; - - Index = RtlFindSetBits(BitMapHeader, - NumberToFind, - HintIndex); - if (Index != (ULONG)-1) - { - RtlClearBits(BitMapHeader, - Index, - NumberToFind); - } - - return Index; -} - - -/* - * @implemented - */ -ULONG NTAPI -RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader) -{ - PULONG Ptr; - ULONG Size; - ULONG Index; - ULONG Count; - ULONG Mask; - - Size = BitMapHeader->SizeOfBitMap; - Ptr = (PULONG)BitMapHeader->Buffer; - - for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++) - { - if (~*Ptr & Mask) - Count++; - - Mask <<= 1; - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - return Count; -} + ULONG ulPos; + + ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex); + if (ulPos != ~0U) + RtlClearBits(BitMapHeader, ulPos, NumberToFind); + return ulPos; +} + + +
/* @@ -735,46 +753,39 @@ ULONG NTAPI RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader) { - PULONG Ptr; - ULONG Size; - ULONG Index; - ULONG Count; - ULONG Mask; - - Ptr = (PULONG)BitMapHeader->Buffer; - Size = BitMapHeader->SizeOfBitMap; - for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++) - { - if (*Ptr & Mask) - Count++; - - Mask <<= 1; - - if (Mask == 0) - { - Mask = 1; - Ptr++; - } - } - - return Count; -} - - -/* - * @implemented - * - * Note: According to the documentation, SizeOfBitmap is in bits, so the - * ROUND_UP(...) must be divided by the number of bits per byte here. - * The companion function, RtlClearAllBits, is exercised by the whole page - * allocator in npool.c which is how i came across this error. + 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++; + } + + 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, - ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8); + memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3); }
@@ -804,31 +815,47 @@ ULONG StartingIndex, ULONG NumberToSet) { - ULONG Size; - ULONG Count; - ULONG Shift; - PULONG Ptr; - - Size = BitMapHeader->SizeOfBitMap; - if (StartingIndex >= Size || NumberToSet == 0) + LPBYTE lpOut; + + if (!BitMapHeader || !NumberToSet || + StartingIndex >= BitMapHeader->SizeOfBitMap || + NumberToSet > BitMapHeader->SizeOfBitMap - StartingIndex) return;
- ASSERT(StartingIndex + NumberToSet <= Size); - - Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32); - while (NumberToSet) - { - /* Bit shift in current ulong */ - Shift = StartingIndex & 0x1F; - - /* Number of bits to change in current ulong */ - Count = (NumberToSet > 32 - Shift) ? 32 - Shift : NumberToSet; - - /* Adjust ulong */ - *Ptr++ |= MASK(Count, Shift); - NumberToSet -= Count; - StartingIndex += Count; - } + /* 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 */ + *lpOut |= NTDLL_maskBits[NumberToSet & 0x7]; }
@@ -849,4 +876,104 @@ return (*Ptr & (1 << (BitNumber % 32))); }
+/* + * @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 != ~0U) + RtlSetBits(BitMapHeader, ulPos, NumberToFind); + return ulPos; +} + +/* + * @implemented + */ +CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong) +{ + signed char ret = 32; + DWORD dw; + + if (!(dw = (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 = 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 */
-
ion＠svn.reactos.org