marko10_000
/
wine-wine
forked from Mirrors/wine-wine
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
wine-wine/dlls/ntdll/rtlbitmap.c

1116 lines
28 KiB
C
Raw Permalink Blame History

/*
* NTDLL bitmap functions
*
* Copyright 2002 Jon Griffiths
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
*
* NOTES
* Bitmaps are an efficient type for manipulating large arrays of bits. They
* are commonly used by device drivers (e.g. For holding dirty/free blocks),
* but are also available to applications that need this functionality.
*
* Bits are set LSB to MSB in each consecutive byte, making this implementation
* binary compatible with Win32.
*
* Note that to avoid unexpected behaviour, the size of a bitmap should be set
* to a multiple of 32.
*/
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include "windef.h"
#include "winternl.h"
#include "wine/debug.h"
WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
/* 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
};
/*************************************************************************
* RtlInitializeBitMap [NTDLL.@]
*
* Initialise a new bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* lpBuff [I] Memory for the bitmap
* ulSize [I] Size of lpBuff in bits
*
* RETURNS
* Nothing.
*
* NOTES
* lpBuff must be aligned on a ULONG suitable boundary, to a multiple of 32 bytes
* in size (irrespective of ulSize given).
*/
VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, PULONG lpBuff, ULONG ulSize)
{
TRACE("(%p,%p,%u)\n", lpBits,lpBuff,ulSize);
lpBits->SizeOfBitMap = ulSize;
lpBits->Buffer = lpBuff;
}
/*************************************************************************
* RtlSetAllBits [NTDLL.@]
*
* Set all bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
*
* RETURNS
* Nothing.
*/
VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
{
TRACE("(%p)\n", lpBits);
memset(lpBits->Buffer, 0xff, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
}
/*************************************************************************
* RtlClearAllBits [NTDLL.@]
*
* Clear all bits in a bitmap.
*
* PARAMS
* lpBit [I] Bitmap pointer
*
* RETURNS
* Nothing.
*/
VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
{
TRACE("(%p)\n", lpBits);
memset(lpBits->Buffer, 0, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
}
/*************************************************************************
* RtlSetBits [NTDLL.@]
*
* Set a range of bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] First bit to set
* ulCount [I] Number of consecutive bits to set
*
* RETURNS
* Nothing.
*/
VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
{
LPBYTE lpOut;
TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
if (!lpBits || !ulCount ||
ulStart >= lpBits->SizeOfBitMap ||
ulCount > lpBits->SizeOfBitMap - ulStart)
return;
/* 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);
/* Set bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
{
if (ulCount > 7)
{
/* Set from start bit to the end of the byte */
*lpOut++ |= 0xff << (ulStart & 7);
ulCount -= (8 - (ulStart & 7));
}
else
{
/* Set from the start bit, possibly into the next byte also */
USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
*lpOut |= (initialWord & 0xff);
if (initialWord >> 8) lpOut[1] |= (initialWord >> 8);
return;
}
}
/* Set bits up to complete byte count */
if (ulCount >> 3)
{
memset(lpOut, 0xff, ulCount >> 3);
lpOut = lpOut + (ulCount >> 3);
}
/* Set remaining bits, if any */
if (ulCount & 0x7)
*lpOut |= NTDLL_maskBits[ulCount & 0x7];
}
/*************************************************************************
* RtlClearBits [NTDLL.@]
*
* Clear bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] First bit to set
* ulCount [I] Number of consecutive bits to clear
*
* RETURNS
* Nothing.
*/
VOID WINAPI RtlClearBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
{
LPBYTE lpOut;
TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
if (!lpBits || !ulCount ||
ulStart >= lpBits->SizeOfBitMap ||
ulCount > lpBits->SizeOfBitMap - ulStart)
return;
/* 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);
/* Clear bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
{
if (ulCount > 7)
{
/* Clear from start bit to the end of the byte */
*lpOut++ &= ~(0xff << (ulStart & 7));
ulCount -= (8 - (ulStart & 7));
}
else
{
/* Clear from the start bit, possibly into the next byte also */
USHORT initialWord = ~(NTDLL_maskBits[ulCount] << (ulStart & 7));
*lpOut &= (initialWord & 0xff);
if ((initialWord >> 8) != 0xff) lpOut[1] &= (initialWord >> 8);
return;
}
}
/* Clear bits (in blocks of 8) on whole byte boundaries */
if (ulCount >> 3)
{
memset(lpOut, 0, ulCount >> 3);
lpOut = lpOut + (ulCount >> 3);
}
/* Clear remaining bits, if any */
if (ulCount & 0x7)
*lpOut &= ~NTDLL_maskBits[ulCount & 0x7];
}
/*************************************************************************
* RtlAreBitsSet [NTDLL.@]
*
* Determine if part of a bitmap is set.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] First bit to check from
* ulCount [I] Number of consecutive bits to check
*
* RETURNS
* TRUE, If ulCount bits from ulStart are set.
* FALSE, Otherwise.
*/
BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
{
LPBYTE lpOut;
ULONG ulRemainder;
TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
if (!lpBits || !ulCount ||
ulStart >= lpBits->SizeOfBitMap ||
ulCount > lpBits->SizeOfBitMap - ulStart)
return FALSE;
/* 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);
/* Check bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
{
if (ulCount > 7)
{
/* Check from start bit to the end of the byte */
if ((*lpOut &
((0xff << (ulStart & 7))) & 0xff) != ((0xff << (ulStart & 7) & 0xff)))
return FALSE;
lpOut++;
ulCount -= (8 - (ulStart & 7));
}
else
{
/* Check from the start bit, possibly into the next byte also */
USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 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 = ulCount & 7;
ulCount >>= 3;
while (ulCount--)
{
if (*lpOut++ != 0xff)
return FALSE;
}
/* Check remaining bits, if any */
if (ulRemainder &&
(*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
return FALSE;
return TRUE;
}
/*************************************************************************
* RtlAreBitsClear [NTDLL.@]
*
* Determine if part of a bitmap is clear.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] First bit to check from
* ulCount [I] Number of consecutive bits to check
*
* RETURNS
* TRUE, If ulCount bits from ulStart are clear.
* FALSE, Otherwise.
*/
BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
{
LPBYTE lpOut;
ULONG ulRemainder;
TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
if (!lpBits || !ulCount ||
ulStart >= lpBits->SizeOfBitMap ||
ulCount > lpBits->SizeOfBitMap - ulStart)
return FALSE;
/* 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);
/* Check bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
{
if (ulCount > 7)
{
/* Check from start bit to the end of the byte */
if (*lpOut & ((0xff << (ulStart & 7)) & 0xff))
return FALSE;
lpOut++;
ulCount -= (8 - (ulStart & 7));
}
else
{
/* Check from the start bit, possibly into the next byte also */
USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 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 = ulCount & 7;
ulCount >>= 3;
while (ulCount--)
{
if (*lpOut++)
return FALSE;
}
/* Check remaining bits, if any */
if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
return FALSE;
return TRUE;
}
/*************************************************************************
* RtlFindSetBits [NTDLL.@]
*
* Find a block of set bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulCount [I] Number of consecutive set bits to find
* ulHint [I] Suggested starting position for set bits
*
* RETURNS
* The bit at which the match was found, or -1 if no match was found.
*/
ULONG WINAPI RtlFindSetBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
{
ULONG ulPos, ulEnd;
TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
return ~0U;
ulEnd = lpBits->SizeOfBitMap;
if (ulHint + ulCount > lpBits->SizeOfBitMap)
ulHint = 0;
ulPos = ulHint;
while (ulPos < ulEnd)
{
/* FIXME: This could be made a _lot_ more efficient */
if (RtlAreBitsSet(lpBits, ulPos, ulCount))
return ulPos;
/* Start from the beginning if we hit the end and had a hint */
if (ulPos == ulEnd - 1 && ulHint)
{
ulEnd = ulHint;
ulPos = ulHint = 0;
}
else
ulPos++;
}
return ~0U;
}
/*************************************************************************
* RtlFindClearBits [NTDLL.@]
*
* Find a block of clear bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulCount [I] Number of consecutive clear bits to find
* ulHint [I] Suggested starting position for clear bits
*
* RETURNS
* The bit at which the match was found, or -1 if no match was found.
*/
ULONG WINAPI RtlFindClearBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
{
ULONG ulPos, ulEnd;
TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
return ~0U;
ulEnd = lpBits->SizeOfBitMap;
if (ulHint + ulCount > lpBits->SizeOfBitMap)
ulHint = 0;
ulPos = ulHint;
while (ulPos < ulEnd)
{
/* FIXME: This could be made a _lot_ more efficient */
if (RtlAreBitsClear(lpBits, ulPos, ulCount))
return ulPos;
/* Start from the beginning if we hit the end and started from ulHint */
if (ulPos == ulEnd - 1 && ulHint)
{
ulEnd = ulHint;
ulPos = ulHint = 0;
}
else
ulPos++;
}
return ~0U;
}
/*************************************************************************
* RtlFindSetBitsAndClear [NTDLL.@]
*
* Find a block of set bits in a bitmap, and clear them if found.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulCount [I] Number of consecutive set bits to find
* ulHint [I] Suggested starting position for set bits
*
* RETURNS
* The bit at which the match was found, or -1 if no match was found.
*/
ULONG WINAPI RtlFindSetBitsAndClear(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
{
ULONG ulPos;
TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
if (ulPos != ~0U)
RtlClearBits(lpBits, ulPos, ulCount);
return ulPos;
}
/*************************************************************************
* RtlFindClearBitsAndSet [NTDLL.@]
*
* Find a block of clear bits in a bitmap, and set them if found.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulCount [I] Number of consecutive clear bits to find
* ulHint [I] Suggested starting position for clear bits
*
* RETURNS
* The bit at which the match was found, or -1 if no match was found.
*/
ULONG WINAPI RtlFindClearBitsAndSet(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
{
ULONG ulPos;
TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
if (ulPos != ~0U)
RtlSetBits(lpBits, ulPos, ulCount);
return ulPos;
}
/*************************************************************************
* RtlNumberOfSetBits [NTDLL.@]
*
* Find the number of set bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
*
* RETURNS
* The number of set bits.
*/
ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP lpBits)
{
ULONG ulSet = 0;
TRACE("(%p)\n", lpBits);
if (lpBits)
{
LPBYTE lpOut = (BYTE *)lpBits->Buffer;
ULONG ulCount, ulRemainder;
BYTE bMasked;
ulCount = lpBits->SizeOfBitMap >> 3;
ulRemainder = lpBits->SizeOfBitMap & 0x7;
while (ulCount--)
{
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;
}
/*************************************************************************
* RtlNumberOfClearBits [NTDLL.@]
*
* Find the number of clear bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
*
* RETURNS
* The number of clear bits.
*/
ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
{
TRACE("(%p)\n", lpBits);
if (lpBits)
return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
return 0;
}
/*************************************************************************
* RtlFindMostSignificantBit [NTDLL.@]
*
* Find the most significant bit in a 64 bit integer.
*
* RETURNS
* The position of the most significant bit.
*/
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];
}
/*************************************************************************
* RtlFindLeastSignificantBit [NTDLL.@]
*
* Find the least significant bit in a 64 bit integer.
*
* RETURNS
* The position of the least significant bit.
*/
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];
}
/*************************************************************************
* NTDLL_RunSortFn
*
* Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
*/
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;
}
/*************************************************************************
* NTDLL_FindSetRun
*
* Internal helper: Find the next run of set bits in a bitmap.
*/
static ULONG NTDLL_FindSetRun(PCRTL_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;
}
/* Check if reached the end of bitmap */
if (ulStart >= lpBits->SizeOfBitMap) {
*lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
return ulFoundAt;
}
/* 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;
}
/*************************************************************************
* NTDLL_FindClearRun
*
* Internal helper: Find the next run of set bits in a bitmap.
*/
static ULONG NTDLL_FindClearRun(PCRTL_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;
}
/* Check if reached the end of bitmap */
if (ulStart >= lpBits->SizeOfBitMap) {
*lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
return ulFoundAt;
}
/* 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;
}
/*************************************************************************
* RtlFindNextForwardRunSet [NTDLL.@]
*
* Find the next run of set bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] Bit position to start searching from
* lpPos [O] Start of run
*
* RETURNS
* Success: The length of the next set run in the bitmap. lpPos is set to
* the start of the run.
* Failure: 0, if no run is found or any parameters are invalid.
*/
ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
{
ULONG ulSize = 0;
TRACE("(%p,%u,%p)\n", lpBits, ulStart, lpPos);
if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
*lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
return ulSize;
}
/*************************************************************************
* RtlFindNextForwardRunClear [NTDLL.@]
*
* Find the next run of clear bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] Bit position to start searching from
* lpPos [O] Start of run
*
* RETURNS
* Success: The length of the next clear run in the bitmap. lpPos is set to
* the start of the run.
* Failure: 0, if no run is found or any parameters are invalid.
*/
ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
{
ULONG ulSize = 0;
TRACE("(%p,%u,%p)\n", lpBits, ulStart, lpPos);
if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
*lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
return ulSize;
}
/*************************************************************************
* RtlFindLastBackwardRunSet [NTDLL.@]
*
* Find a previous run of set bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] Bit position to start searching from
* lpPos [O] Start of run
*
* RETURNS
* Success: The length of the previous set run in the bitmap. lpPos is set to
* the start of the run.
* Failure: 0, if no run is found or any parameters are invalid.
*/
ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
{
FIXME("(%p,%u,%p)-stub!\n", lpBits, ulStart, lpPos);
return 0;
}
/*************************************************************************
* RtlFindLastBackwardRunClear [NTDLL.@]
*
* Find a previous run of clear bits in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulStart [I] Bit position to start searching from
* lpPos [O] Start of run
*
* RETURNS
* Success: The length of the previous clear run in the bitmap. lpPos is set
* to the start of the run.
* Failure: 0, if no run is found or any parameters are invalid.
*/
ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
{
FIXME("(%p,%u,%p)-stub!\n", lpBits, ulStart, lpPos);
return 0;
}
/*************************************************************************
* NTDLL_FindRuns
*
* Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
*/
static ULONG NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
ULONG ulCount, BOOLEAN bLongest,
ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
{
BOOL bNeedSort = ulCount > 1;
ULONG ulPos = 0, ulRuns = 0;
TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
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;
}
/*************************************************************************
* RtlFindSetRuns [NTDLL.@]
*
* Find a series of set runs in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* lpSeries [O] Array for each run found
* ulCount [I] Number of runs to find
* bLongest [I] Whether to find the very longest runs or not
*
* RETURNS
* The number of set runs found.
*/
ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
ULONG ulCount, BOOLEAN bLongest)
{
TRACE("(%p,%p,%u,%d)\n", lpBits, lpSeries, ulCount, bLongest);
return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
}
/*************************************************************************
* RtlFindClearRuns [NTDLL.@]
*
* Find a series of clear runs in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* ulSeries [O] Array for each run found
* ulCount [I] Number of runs to find
* bLongest [I] Whether to find the very longest runs or not
*
* RETURNS
* The number of clear runs found.
*/
ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
ULONG ulCount, BOOLEAN bLongest)
{
TRACE("(%p,%p,%u,%d)\n", lpBits, lpSeries, ulCount, bLongest);
return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
}
/*************************************************************************
* RtlFindLongestRunSet [NTDLL.@]
*
* Find the longest set run in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* pulStart [O] Destination for start of run
*
* RETURNS
* The length of the run found, or 0 if no run is found.
*/
ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
{
RTL_BITMAP_RUN br;
TRACE("(%p,%p)\n", lpBits, pulStart);
if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
{
if (pulStart)
*pulStart = br.StartingIndex;
return br.NumberOfBits;
}
return 0;
}
/*************************************************************************
* RtlFindLongestRunClear [NTDLL.@]
*
* Find the longest clear run in a bitmap.
*
* PARAMS
* lpBits [I] Bitmap pointer
* pulStart [O] Destination for start of run
*
* RETURNS
* The length of the run found, or 0 if no run is found.
*/
ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
{
RTL_BITMAP_RUN br;
TRACE("(%p,%p)\n", lpBits, pulStart);
if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
{
if (pulStart)
*pulStart = br.StartingIndex;
return br.NumberOfBits;
}
return 0;
}
Reference in New Issue View Git Blame Copy Permalink