From 1da297178ab3999c369c0e10ba97d42ff6c44510 Mon Sep 17 00:00:00 2001 From: Jon Griffiths Date: Thu, 15 Aug 2002 22:08:40 +0000 Subject: [PATCH] Implement and test rtl bitmap functions. Add a couple of other misc rtl functions. --- configure | 3 +- configure.ac | 1 + dlls/ntdll/Makefile.in | 3 + dlls/ntdll/ntdll.spec | 42 +- dlls/ntdll/rtl.c | 78 ++- dlls/ntdll/rtlbitmap.c | 1079 ++++++++++++++++++++++++++++++++++++++++++ dlls/ntdll/tests/.cvsignore | 4 + dlls/ntdll/tests/Makefile.in | 13 + dlls/ntdll/tests/rtlbitmap.c | 646 +++++++++++++++++++++++++ include/ntddk.h | 80 ++++ 10 files changed, 1891 insertions(+), 58 deletions(-) create mode 100644 dlls/ntdll/rtlbitmap.c create mode 100644 dlls/ntdll/tests/.cvsignore create mode 100644 dlls/ntdll/tests/Makefile.in create mode 100644 dlls/ntdll/tests/rtlbitmap.c diff --git a/configure b/configure index 0dd4cb6297f..8cd653f05e0 100755 --- a/configure +++ b/configure @@ -14096,7 +14096,7 @@ MAKE_TEST_RULES=dlls/Maketest.rules MAKE_PROG_RULES=programs/Makeprog.rules -ac_config_files="$ac_config_files Make.rules dlls/Makedll.rules dlls/Maketest.rules programs/Makeprog.rules Makefile debugger/Makefile dlls/Makefile dlls/advapi32/Makefile dlls/advapi32/tests/Makefile dlls/avicap32/Makefile dlls/avifil32/Makefile dlls/comcat/Makefile dlls/comctl32/Makefile dlls/commdlg/Makefile dlls/crtdll/Makefile dlls/crypt32/Makefile dlls/d3d8/Makefile dlls/dciman32/Makefile dlls/ddraw/Makefile dlls/devenum/Makefile dlls/dinput/Makefile dlls/dinput8/Makefile dlls/dplay/Makefile dlls/dplayx/Makefile dlls/dsound/Makefile dlls/gdi/Makefile dlls/glu32/Makefile dlls/icmp/Makefile dlls/imagehlp/Makefile dlls/imm32/Makefile dlls/kernel/Makefile dlls/kernel/tests/Makefile dlls/lzexpand/Makefile dlls/mapi32/Makefile dlls/mpr/Makefile dlls/msacm/Makefile dlls/msacm/imaadp32/Makefile dlls/msacm/msadp32/Makefile dlls/msacm/msg711/Makefile dlls/msacm/winemp3/Makefile dlls/msdmo/Makefile dlls/msimg32/Makefile dlls/msisys/Makefile dlls/msnet32/Makefile dlls/msrle32/Makefile dlls/msvcrt/Makefile dlls/msvcrt20/Makefile dlls/msvideo/Makefile dlls/netapi32/Makefile dlls/ntdll/Makefile dlls/odbc32/Makefile dlls/ole32/Makefile dlls/oleaut32/Makefile dlls/oleaut32/tests/Makefile dlls/olecli/Makefile dlls/oledlg/Makefile dlls/olepro32/Makefile dlls/olesvr/Makefile dlls/opengl32/Makefile dlls/psapi/Makefile dlls/qcap/Makefile dlls/quartz/Makefile dlls/rasapi32/Makefile dlls/richedit/Makefile dlls/rpcrt4/Makefile dlls/serialui/Makefile dlls/setupapi/Makefile dlls/shdocvw/Makefile dlls/shell32/Makefile dlls/shfolder/Makefile dlls/shlwapi/Makefile dlls/shlwapi/tests/Makefile dlls/snmpapi/Makefile dlls/sti/Makefile dlls/tapi32/Makefile dlls/ttydrv/Makefile dlls/twain/Makefile dlls/url/Makefile dlls/urlmon/Makefile dlls/user/Makefile dlls/user/tests/Makefile dlls/version/Makefile dlls/win32s/Makefile dlls/winaspi/Makefile dlls/winedos/Makefile dlls/wineps/Makefile dlls/wininet/Makefile dlls/wininet/tests/Makefile dlls/winmm/Makefile dlls/winmm/joystick/Makefile dlls/winmm/mcianim/Makefile dlls/winmm/mciavi/Makefile dlls/winmm/mcicda/Makefile dlls/winmm/mciseq/Makefile dlls/winmm/mciwave/Makefile dlls/winmm/midimap/Makefile dlls/winmm/wavemap/Makefile dlls/winmm/winealsa/Makefile dlls/winmm/winearts/Makefile dlls/winmm/wineaudioio/Makefile dlls/winmm/winenas/Makefile dlls/winmm/wineoss/Makefile dlls/winnls/Makefile dlls/winsock/Makefile dlls/winsock/tests/Makefile dlls/winspool/Makefile dlls/wintrust/Makefile dlls/wow32/Makefile dlls/wsock32/Makefile dlls/x11drv/Makefile documentation/Makefile include/Makefile library/Makefile miscemu/Makefile ole/Makefile programs/Makefile programs/avitools/Makefile programs/clock/Makefile programs/cmdlgtst/Makefile programs/control/Makefile programs/expand/Makefile programs/notepad/Makefile programs/osversioncheck/Makefile programs/progman/Makefile programs/regapi/Makefile programs/regedit/Makefile programs/regsvr32/Makefile programs/regtest/Makefile programs/uninstaller/Makefile programs/view/Makefile programs/wcmd/Makefile programs/wineconsole/Makefile programs/winefile/Makefile programs/winemine/Makefile programs/winepath/Makefile programs/winetest/Makefile programs/winhelp/Makefile programs/winver/Makefile server/Makefile tools/Makefile tools/widl/Makefile tools/winapi/Makefile tools/winebuild/Makefile tools/winedump/Makefile tools/wmc/Makefile tools/wpp/Makefile tools/wrc/Makefile tsx11/Makefile unicode/Makefile" +ac_config_files="$ac_config_files Make.rules dlls/Makedll.rules dlls/Maketest.rules programs/Makeprog.rules Makefile debugger/Makefile dlls/Makefile dlls/advapi32/Makefile dlls/advapi32/tests/Makefile dlls/avicap32/Makefile dlls/avifil32/Makefile dlls/comcat/Makefile dlls/comctl32/Makefile dlls/commdlg/Makefile dlls/crtdll/Makefile dlls/crypt32/Makefile dlls/d3d8/Makefile dlls/dciman32/Makefile dlls/ddraw/Makefile dlls/devenum/Makefile dlls/dinput/Makefile dlls/dinput8/Makefile dlls/dplay/Makefile dlls/dplayx/Makefile dlls/dsound/Makefile dlls/gdi/Makefile dlls/glu32/Makefile dlls/icmp/Makefile dlls/imagehlp/Makefile dlls/imm32/Makefile dlls/kernel/Makefile dlls/kernel/tests/Makefile dlls/lzexpand/Makefile dlls/mapi32/Makefile dlls/mpr/Makefile dlls/msacm/Makefile dlls/msacm/imaadp32/Makefile dlls/msacm/msadp32/Makefile dlls/msacm/msg711/Makefile dlls/msacm/winemp3/Makefile dlls/msdmo/Makefile dlls/msimg32/Makefile dlls/msisys/Makefile dlls/msnet32/Makefile dlls/msrle32/Makefile dlls/msvcrt/Makefile dlls/msvcrt20/Makefile dlls/msvideo/Makefile dlls/netapi32/Makefile dlls/ntdll/Makefile dlls/ntdll/tests/Makefile dlls/odbc32/Makefile dlls/ole32/Makefile dlls/oleaut32/Makefile dlls/oleaut32/tests/Makefile dlls/olecli/Makefile dlls/oledlg/Makefile dlls/olepro32/Makefile dlls/olesvr/Makefile dlls/opengl32/Makefile dlls/psapi/Makefile dlls/qcap/Makefile dlls/quartz/Makefile dlls/rasapi32/Makefile dlls/richedit/Makefile dlls/rpcrt4/Makefile dlls/serialui/Makefile dlls/setupapi/Makefile dlls/shdocvw/Makefile dlls/shell32/Makefile dlls/shfolder/Makefile dlls/shlwapi/Makefile dlls/shlwapi/tests/Makefile dlls/snmpapi/Makefile dlls/sti/Makefile dlls/tapi32/Makefile dlls/ttydrv/Makefile dlls/twain/Makefile dlls/url/Makefile dlls/urlmon/Makefile dlls/user/Makefile dlls/user/tests/Makefile dlls/version/Makefile dlls/win32s/Makefile dlls/winaspi/Makefile dlls/winedos/Makefile dlls/wineps/Makefile dlls/wininet/Makefile dlls/wininet/tests/Makefile dlls/winmm/Makefile dlls/winmm/joystick/Makefile dlls/winmm/mcianim/Makefile dlls/winmm/mciavi/Makefile dlls/winmm/mcicda/Makefile dlls/winmm/mciseq/Makefile dlls/winmm/mciwave/Makefile dlls/winmm/midimap/Makefile dlls/winmm/wavemap/Makefile dlls/winmm/winealsa/Makefile dlls/winmm/winearts/Makefile dlls/winmm/wineaudioio/Makefile dlls/winmm/winenas/Makefile dlls/winmm/wineoss/Makefile dlls/winnls/Makefile dlls/winsock/Makefile dlls/winsock/tests/Makefile dlls/winspool/Makefile dlls/wintrust/Makefile dlls/wow32/Makefile dlls/wsock32/Makefile dlls/x11drv/Makefile documentation/Makefile include/Makefile library/Makefile miscemu/Makefile ole/Makefile programs/Makefile programs/avitools/Makefile programs/clock/Makefile programs/cmdlgtst/Makefile programs/control/Makefile programs/expand/Makefile programs/notepad/Makefile programs/osversioncheck/Makefile programs/progman/Makefile programs/regapi/Makefile programs/regedit/Makefile programs/regsvr32/Makefile programs/regtest/Makefile programs/uninstaller/Makefile programs/view/Makefile programs/wcmd/Makefile programs/wineconsole/Makefile programs/winefile/Makefile programs/winemine/Makefile programs/winepath/Makefile programs/winetest/Makefile programs/winhelp/Makefile programs/winver/Makefile server/Makefile tools/Makefile tools/widl/Makefile tools/winapi/Makefile tools/winebuild/Makefile tools/winedump/Makefile tools/wmc/Makefile tools/wpp/Makefile tools/wrc/Makefile tsx11/Makefile unicode/Makefile" cat >confcache <<\_ACEOF @@ -14623,6 +14623,7 @@ do "dlls/msvideo/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/msvideo/Makefile" ;; "dlls/netapi32/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/netapi32/Makefile" ;; "dlls/ntdll/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/ntdll/Makefile" ;; + "dlls/ntdll/tests/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/ntdll/tests/Makefile" ;; "dlls/odbc32/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/odbc32/Makefile" ;; "dlls/ole32/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/ole32/Makefile" ;; "dlls/oleaut32/Makefile" ) CONFIG_FILES="$CONFIG_FILES dlls/oleaut32/Makefile" ;; diff --git a/configure.ac b/configure.ac index 37aeb2ec216..315ddc79126 100644 --- a/configure.ac +++ b/configure.ac @@ -1397,6 +1397,7 @@ dlls/msvcrt20/Makefile dlls/msvideo/Makefile dlls/netapi32/Makefile dlls/ntdll/Makefile +dlls/ntdll/tests/Makefile dlls/odbc32/Makefile dlls/ole32/Makefile dlls/oleaut32/Makefile diff --git a/dlls/ntdll/Makefile.in b/dlls/ntdll/Makefile.in index d7f6ed45da0..1f6e8ea964e 100644 --- a/dlls/ntdll/Makefile.in +++ b/dlls/ntdll/Makefile.in @@ -106,6 +106,7 @@ C_SRCS = \ reg.c \ rtl.c \ rtlstr.c \ + rtlbitmap.c \ string.c \ sec.c \ signal_i386.c \ @@ -120,6 +121,8 @@ GEN_ASM_SRCS = \ EXTRA_OBJS = $(MODULE).glue.o +SUBDIRS = tests + EXTRASUBDIRS = \ $(TOPOBJDIR)/files \ $(TOPOBJDIR)/if1632 \ diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index 1f97e81f5c2..c46237119e0 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -283,14 +283,14 @@ @ stub RtlApplyRXactNoFlush @ stub RtlAreAllAccessesGranted @ stub RtlAreAnyAccessesGranted -@ stub RtlAreBitsClear -@ stub RtlAreBitsSet +@ stdcall RtlAreBitsClear(ptr long long) RtlAreBitsClear +@ stdcall RtlAreBitsSet(ptr long long) RtlAreBitsSet @ stdcall RtlAssert(ptr ptr long long) RtlAssert @ stub RtlCaptureStackBackTrace @ stub RtlCharToInteger @ stub RtlCheckRegistryKey -@ stub RtlClearAllBits -@ stdcall RtlClearBits(long long long) RtlClearBits +@ stdcall RtlClearAllBits(ptr) RtlClearAllBits +@ stdcall RtlClearBits(ptr long long) RtlClearBits @ stdcall RtlCompactHeap(long long) RtlCompactHeap @ stdcall RtlCompareMemory(ptr ptr long) RtlCompareMemory @ stub RtlCompareMemoryUlong @@ -367,14 +367,22 @@ @ stdcall -ret64 RtlExtendedLargeIntegerDivide(long long long ptr) RtlExtendedLargeIntegerDivide @ stub RtlExtendedMagicDivide @ stdcall RtlFillMemory(ptr long long) RtlFillMemory -@ stub RtlFillMemoryUlong -@ stdcall RtlFindClearBits(long long long) RtlFindClearBits -@ stub RtlFindClearBitsAndSet -@ stub RtlFindLongestRunClear -@ stub RtlFindLongestRunSet +@ stdcall RtlFillMemoryUlong(ptr long long) RtlFillMemoryUlong +@ stdcall RtlFindClearBits(ptr long long) RtlFindClearBits +@ stdcall RtlFindClearBitsAndSet(ptr long long) RtlFindClearBitsAndSet +@ stdcall RtlFindClearRuns(ptr ptr long long) RtlFindClearRuns +@ stdcall RtlFindLastBackwardRunClear(ptr long ptr) RtlFindLastBackwardRunClear +@ stdcall RtlFindLastBackwardRunSet(ptr long ptr) RtlFindLastBackwardRunSet +@ stdcall RtlFindLeastSignificantBit(ptr long long) RtlFindLeastSignificantBit +@ stdcall RtlFindLongestRunClear(ptr long) RtlFindLongestRunClear +@ stdcall RtlFindLongestRunSet(ptr long) RtlFindLongestRunSet @ stub RtlFindMessage -@ stub RtlFindSetBits -@ stub RtlFindSetBitsAndClear +@ stdcall RtlFindMostSignificantBit(ptr long long) RtlFindMostSignificantBit +@ stdcall RtlFindNextForwardRunClear(ptr long ptr) RtlFindNextForwardRunClear +@ stdcall RtlFindNextForwardRunSet(ptr long ptr) RtlFindNextForwardRunSet +@ stdcall RtlFindSetBits(ptr long long) RtlFindSetBits +@ stdcall RtlFindSetBitsAndClear(ptr long long) RtlFindSetBitsAndClear +@ stdcall RtlFindSetRuns(ptr ptr long long) RtlFindSetRuns @ stdcall RtlFirstFreeAce(ptr ptr) RtlFirstFreeAce @ stdcall RtlFormatCurrentUserKeyPath(ptr) RtlFormatCurrentUserKeyPath @ stub RtlFormatMessage @@ -395,7 +403,7 @@ @ stub RtlGetElementGenericTable @ stub RtlGetFullPathName_U @ stdcall RtlGetGroupSecurityDescriptor(ptr ptr ptr) RtlGetGroupSecurityDescriptor -@ stub RtlGetLongestNtPathLength +@ stdcall RtlGetLongestNtPathLength() RtlGetLongestNtPathLength @ stub RtlGetNtGlobalFlags @ stdcall RtlGetNtProductType(ptr) RtlGetNtProductType @ stdcall RtlGetOwnerSecurityDescriptor(ptr ptr ptr) RtlGetOwnerSecurityDescriptor @@ -413,7 +421,7 @@ @ stub RtlInitNlsTables @ stdcall RtlInitString(ptr str) RtlInitString @ stdcall RtlInitUnicodeString(ptr wstr) RtlInitUnicodeString -@ stdcall RtlInitializeBitMap(long long long) RtlInitializeBitMap +@ stdcall RtlInitializeBitMap(ptr long long) RtlInitializeBitMap @ stub RtlInitializeContext @ stdcall RtlInitializeCriticalSection(ptr) RtlInitializeCriticalSection @ stdcall RtlInitializeCriticalSectionAndSpinCount(ptr long) RtlInitializeCriticalSectionAndSpinCount @@ -454,8 +462,8 @@ @ stdcall RtlNormalizeProcessParams(ptr) RtlNormalizeProcessParams @ stdcall RtlNtStatusToDosError(long) RtlNtStatusToDosError @ stub RtlNumberGenericTableElements -@ stub RtlNumberOfClearBits -@ stub RtlNumberOfSetBits +@ stdcall RtlNumberOfClearBits(ptr) RtlNumberOfClearBits +@ stdcall RtlNumberOfSetBits(ptr) RtlNumberOfSetBits @ stdcall RtlOemStringToUnicodeSize(ptr) RtlOemStringToUnicodeSize @ stdcall RtlOemStringToUnicodeString(ptr ptr long) RtlOemStringToUnicodeString @ stdcall RtlOemToUnicodeN(ptr long ptr ptr long) RtlOemToUnicodeN @@ -489,8 +497,8 @@ @ stdcall RtlSecondsSince1970ToTime(long ptr) RtlSecondsSince1970ToTime @ stdcall RtlSecondsSince1980ToTime(long ptr) RtlSecondsSince1980ToTime @ stub RtlSelfRelativeToAbsoluteSD -@ stub RtlSetAllBits -@ stdcall RtlSetBits(long long long) RtlSetBits +@ stdcall RtlSetAllBits(ptr) RtlSetAllBits +@ stdcall RtlSetBits(ptr long long) RtlSetBits @ stub RtlSetCurrentDirectory_U @ stub RtlSetCurrentEnvironment @ stdcall RtlSetDaclSecurityDescriptor(ptr long ptr long) RtlSetDaclSecurityDescriptor diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index b07b25d1658..4b3ac8102c4 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -380,46 +380,6 @@ DWORD WINAPI RtlInitializeGenericTable(void) } /****************************************************************************** - * RtlInitializeBitMap [NTDLL.@] - * - */ -NTSTATUS WINAPI RtlInitializeBitMap(DWORD x1,DWORD x2,DWORD x3) -{ - FIXME("(0x%08lx,0x%08lx,0x%08lx),stub\n",x1,x2,x3); - return 0; -} - -/****************************************************************************** - * RtlSetBits [NTDLL.@] - * - */ -NTSTATUS WINAPI RtlSetBits(DWORD x1,DWORD x2,DWORD x3) -{ - FIXME("(0x%08lx,0x%08lx,0x%08lx),stub\n",x1,x2,x3); - return 0; -} - -/****************************************************************************** - * RtlFindClearBits [NTDLL.@] - * - */ -NTSTATUS WINAPI RtlFindClearBits(DWORD x1,DWORD x2,DWORD x3) -{ - FIXME("(0x%08lx,0x%08lx,0x%08lx),stub\n",x1,x2,x3); - return 0; -} - -/****************************************************************************** - * RtlClearBits [NTDLL.@] - * - */ -NTSTATUS WINAPI RtlClearBits(DWORD x1,DWORD x2,DWORD x3) -{ - FIXME("(0x%08lx,0x%08lx,0x%08lx),stub\n",x1,x2,x3); - return 0; -} - -/****************************************************************************** * RtlCopyMemory [NTDLL] * */ @@ -503,3 +463,41 @@ void WINAPI RtlGetNtVersionNumbers(LPDWORD major, LPDWORD minor, LPDWORD build) *build = (0xF0000000 | versionInfo.dwBuildNumber); } } + +/************************************************************************* + * RtlFillMemoryUlong [NTDLL.@] + * + * Fill memory with a 32 bit (dword) value. + * + * PARAMS + * lpDest [I] Bitmap pointer + * ulCount [I] Number of dwords to write + * ulValue [I] Value to fill with + * + * RETURNS + * Nothing. + */ +VOID WINAPI RtlFillMemoryUlong(ULONG* lpDest, ULONG ulCount, ULONG ulValue) +{ + TRACE("(%p,%ld,%ld)\n", lpDest, ulCount, ulValue); + + while(ulCount--) + *lpDest++ = ulValue; +} + +/************************************************************************* + * RtlGetLongestNtPathLength [NTDLL.@] + * + * Get the longest allowed path length + * + * PARAMS + * None. + * + * RETURNS + * The longest allowed path length (277 characters under Win2k). + */ +DWORD WINAPI RtlGetLongestNtPathLength(void) +{ + TRACE("()\n"); + return 277; +} diff --git a/dlls/ntdll/rtlbitmap.c b/dlls/ntdll/rtlbitmap.c new file mode 100644 index 00000000000..acc7d201510 --- /dev/null +++ b/dlls/ntdll/rtlbitmap.c @@ -0,0 +1,1079 @@ +/* + * 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 compatable with Win32. + * + * Note that to avoid unexpected behaviour, the size of a bitmap should be set + * to a multiple of 32. + */ +#include +#include +#include "windef.h" +#include "ntddk.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 BYTE NTDLL_mostSignificant[16] = { + 0, 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). + */ +#undef RtlInitializeBitMap +VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, LPBYTE lpBuff, ULONG ulSize) +{ + TRACE("(%p,%p,%ld)\n", lpBits,lpBuff,ulSize); + lpBits->SizeOfBitMap = ulSize; + lpBits->BitMapBuffer = lpBuff; +} + +/************************************************************************* + * RtlSetAllBits [NTDLL.@] + * + * Set all bits in a bitmap. + * + * PARAMS + * lpBits [I] Bitmap pointer + * + * RETURNS + * Nothing. + */ +#undef RtlSetAllBits +VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits) +{ + TRACE("(%p)\n", lpBits); + memset(lpBits->BitMapBuffer, 0xff, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 3); +} + +/************************************************************************* + * RtlClearAllBits [NTDLL.@] + * + * Clear all bits in a bitmap. + * + * PARAMS + * lpBit [I] Bitmap pointer + * + * RETURNS + * Nothing. + */ +#undef RtlClearAllBits +VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits) +{ + TRACE("(%p)\n", lpBits); + memset(lpBits->BitMapBuffer, 0, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 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,%ld,%ld)\n", lpBits, ulStart, ulCount); + + if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap) + return; + + lpOut = lpBits->BitMapBuffer + (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); + *lpOut |= (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 */ + *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,%ld,%ld)\n", lpBits, ulStart, ulCount); + + if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap) + return; + + lpOut = lpBits->BitMapBuffer + (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); + *lpOut &= (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,%ld,%ld)\n", lpBits, ulStart, ulCount); + + if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap) + return FALSE; + + lpOut = lpBits->BitMapBuffer + (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,%ld,%ld)\n", lpBits, ulStart, ulCount); + + if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap) + return FALSE; + + lpOut = lpBits->BitMapBuffer + (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,%ld,%ld)\n", lpBits, ulCount, ulHint); + + if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap) + return -1u; + + 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 -1u; +} + +/************************************************************************* + * 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,%ld,%ld)\n", lpBits, ulCount, ulHint); + + if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap) + return -1u; + + 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 -1u; +} + +/************************************************************************* + * 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,%ld,%ld)\n", lpBits, ulCount, ulHint); + + ulPos = RtlFindSetBits(lpBits, ulCount, ulHint); + if (ulPos != -1u) + 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,%ld,%ld)\n", lpBits, ulCount, ulHint); + + ulPos = RtlFindClearBits(lpBits, ulCount, ulHint); + if (ulPos != -1u) + 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 = lpBits->BitMapBuffer; + 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++; + } + + 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. + * + * PARAMS + * lpBits [I] Bitmap pointer + * ulStart [I] First bit to search from + * + * RETURNS + * The position of the most significant bit. + */ +CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong) +{ + LONG lCount = 64; + LPBYTE lpOut = (LPBYTE)&ulLong + 7; + + TRACE("(%lld)\n", ulLong); + + if (!(ulLong & 0xffffffff00000000ul)) + { + lpOut -= 4; + lCount -= 32; + } + + for (; lCount > 0; lCount -= 8) + { + if (*lpOut) + { + if (*lpOut & 0x0f) + return lCount - 8 + NTDLL_mostSignificant[*lpOut & 0x0f]; + return lCount - 4 + NTDLL_mostSignificant[*lpOut >> 4]; + } + lpOut--; + } + return -1; +} + +/************************************************************************* + * RtlFindLeastSignificantBit [NTDLL.@] + * + * Find the least significant bit in a 64 bit integer. + * + * PARAMS + * lpBits [I] Bitmap pointer + * ulStart [I] First bit to search from + * + * RETURNS + * The position of the least significant bit. + */ +CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong) +{ + ULONG ulCount = 0; + LPBYTE lpOut = (LPBYTE)&ulLong; + + TRACE("(%lld)\n", ulLong); + + if (!(ulLong & 0xffffffff)) + { + lpOut += 4; + ulCount = 32; + } + + for (; ulCount < 64; ulCount += 8) + { + if (*lpOut) + { + if (*lpOut & 0x0f) + return ulCount + NTDLL_leastSignificant[*lpOut & 0x0f]; + return ulCount + 4 + NTDLL_leastSignificant[*lpOut >> 4]; + } + lpOut++; + } + return -1; +} + +/************************************************************************* + * NTDLL_RunSortFn + * + * Internal helper: qsort comparason function for RTL_BITMAP_RUN arrays + */ +static int NTDLL_RunSortFn(const void *lhs, const void *rhs) +{ + if (((PCRTL_BITMAP_RUN)lhs)->SizeOfRun > ((PRTL_BITMAP_RUN)rhs)->SizeOfRun) + 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; + + lpOut = lpBits->BitMapBuffer + (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 -1u; + } + + /* 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 contigious 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; + + lpOut = lpBits->BitMapBuffer + (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 -1u; + } + + /* 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 contigious 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,%ld,%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,%ld,%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,%ld,%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,%ld,%p)-stub!\n", lpBits, ulStart, lpPos); + return 0; +} + +/************************************************************************* + * NTDLL_FindRuns + * + * Internal implementation of RtlFindSetRuns/RtlFindClearRuns. + */ +static ULONG WINAPI NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries, + ULONG ulCount, BOOLEAN bLongest, + ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG)) +{ + BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE; + ULONG ulPos = 0, ulRuns = 0; + + TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest); + + if (!ulCount) + return -1u; + + while (ulPos < lpBits->SizeOfBitMap) + { + /* Find next set/clear run */ + ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize); + + if (ulNextPos == -1u) + 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].SizeOfRun) + { + lpSeries[ulRuns - 1].StartOfRun = ulNextPos; + lpSeries[ulRuns - 1].SizeOfRun = ulSize; + + /* We need to re-sort the array, _if_ we didn't leave it sorted */ + if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].SizeOfRun) + bNeedSort = TRUE; + } + } + else + { + /* Append to found runs */ + lpSeries[ulRuns].StartOfRun = ulNextPos; + lpSeries[ulRuns].SizeOfRun = 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 + * 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 set runs found. + */ +ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries, + ULONG ulCount, BOOLEAN bLongest) +{ + TRACE("(%p,%p,%ld,%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,%ld,%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.StartOfRun; + return br.SizeOfRun; + } + 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.StartOfRun; + return br.SizeOfRun; + } + return 0; +} diff --git a/dlls/ntdll/tests/.cvsignore b/dlls/ntdll/tests/.cvsignore new file mode 100644 index 00000000000..80f291756e1 --- /dev/null +++ b/dlls/ntdll/tests/.cvsignore @@ -0,0 +1,4 @@ +Makefile +ntdll_test.exe.spec.c +rtlbitmap.ok +testlist.c diff --git a/dlls/ntdll/tests/Makefile.in b/dlls/ntdll/tests/Makefile.in new file mode 100644 index 00000000000..a5bd3ed328c --- /dev/null +++ b/dlls/ntdll/tests/Makefile.in @@ -0,0 +1,13 @@ +TOPSRCDIR = @top_srcdir@ +TOPOBJDIR = ../../.. +SRCDIR = @srcdir@ +VPATH = @srcdir@ +TESTDLL = ntdll.dll +IMPORTS = ntdll + +CTESTS = \ + rtlbitmap.c + +@MAKE_TEST_RULES@ + +### Dependencies: diff --git a/dlls/ntdll/tests/rtlbitmap.c b/dlls/ntdll/tests/rtlbitmap.c new file mode 100644 index 00000000000..271f0525e39 --- /dev/null +++ b/dlls/ntdll/tests/rtlbitmap.c @@ -0,0 +1,646 @@ +/* Unit test suite for Rtl 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * NOTES + * We use function pointers here as some of the bitmap functions exist only + * in later versions of ntdll. + */ +#include "wine/test.h" +#include "winbase.h" +#include "winnt.h" +#include "ntddk.h" + +/* Function ptrs for ordinal calls */ +static HMODULE hntdll = 0; +static VOID (WINAPI *pRtlInitializeBitMap)(PRTL_BITMAP,LPBYTE,ULONG); +static VOID (WINAPI *pRtlSetAllBits)(PRTL_BITMAP); +static VOID (WINAPI *pRtlClearAllBits)(PRTL_BITMAP); +static VOID (WINAPI *pRtlSetBits)(PRTL_BITMAP,ULONG,ULONG); +static VOID (WINAPI *pRtlClearBits)(PRTL_BITMAP,ULONG,ULONG); +static BOOLEAN (WINAPI *pRtlAreBitsSet)(PRTL_BITMAP,ULONG,ULONG); +static BOOLEAN (WINAPI *pRtlAreBitsClear)(PRTL_BITMAP,ULONG,ULONG); +static ULONG (WINAPI *pRtlFindSetBitsAndClear)(PRTL_BITMAP,ULONG,ULONG); +static ULONG (WINAPI *pRtlFindClearBitsAndSet)(PRTL_BITMAP,ULONG,ULONG); +static CCHAR (WINAPI *pRtlFindMostSignificantBit)(ULONGLONG); +static CCHAR (WINAPI *pRtlFindLeastSignificantBit)(ULONGLONG); +static ULONG (WINAPI *pRtlFindSetRuns)(PRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN); +static ULONG (WINAPI *pRtlFindClearRuns)(PRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN); +static ULONG (WINAPI *pRtlNumberOfSetBits)(PRTL_BITMAP); +static ULONG (WINAPI *pRtlNumberOfClearBits)(PRTL_BITMAP); +static ULONG (WINAPI *pRtlFindLongestRunSet)(PRTL_BITMAP,PULONG); +static ULONG (WINAPI *pRtlFindLongestRunClear)(PRTL_BITMAP,PULONG); + +static BYTE buff[256]; +static RTL_BITMAP bm; + +static void InitFunctionPtrs() +{ + hntdll = LoadLibraryA("ntdll.dll"); + ok(hntdll != 0, "LoadLibrary failed"); + if (hntdll) + { + pRtlInitializeBitMap = (void *)GetProcAddress(hntdll, "RtlInitializeBitMap"); + pRtlSetAllBits = (void *)GetProcAddress(hntdll, "RtlSetAllBits"); + pRtlClearAllBits = (void *)GetProcAddress(hntdll, "RtlClearAllBits"); + pRtlSetBits = (void *)GetProcAddress(hntdll, "RtlSetBits"); + pRtlClearBits = (void *)GetProcAddress(hntdll, "RtlClearBits"); + pRtlAreBitsSet = (void *)GetProcAddress(hntdll, "RtlAreBitsSet"); + pRtlAreBitsClear = (void *)GetProcAddress(hntdll, "RtlAreBitsClear"); + pRtlNumberOfSetBits = (void *)GetProcAddress(hntdll, "RtlNumberOfSetBits"); + pRtlNumberOfClearBits = (void *)GetProcAddress(hntdll, "RtlNumberOfClearBits"); + pRtlFindSetBitsAndClear = (void *)GetProcAddress(hntdll, "RtlFindSetBitsAndClear"); + pRtlFindClearBitsAndSet = (void *)GetProcAddress(hntdll, "RtlFindClearBitsAndSet"); + pRtlFindMostSignificantBit = (void *)GetProcAddress(hntdll, "RtlFindMostSignificantBit"); + pRtlFindLeastSignificantBit = (void *)GetProcAddress(hntdll, "RtlFindLeastSignificantBit"); + pRtlFindSetRuns = (void *)GetProcAddress(hntdll, "RtlFindSetRuns"); + pRtlFindClearRuns = (void *)GetProcAddress(hntdll, "RtlFindClearRuns"); + pRtlFindLongestRunSet = (void *)GetProcAddress(hntdll, "RtlFindLongestRunSet"); + pRtlFindLongestRunClear = (void *)GetProcAddress(hntdll, "RtlFindLongestRunClear"); + } +} + +static void test_RtlInitializeBitMap(void) +{ + bm.SizeOfBitMap = 0; + bm.BitMapBuffer = 0; + + memset(buff, 0, sizeof(buff)); + buff[0] = 77; /* Check buffer is not written to during init */ + buff[79] = 77; + + pRtlInitializeBitMap(&bm, buff, 800); + ok(bm.SizeOfBitMap == 800, "size uninitialised"); + ok(bm.BitMapBuffer == buff,"buffer uninitialised"); + ok(buff[0] == 77 && buff[79] == 77, "wrote to buffer"); + + /* Test inlined version */ + RtlInitializeBitMap(&bm, buff, 800); + ok(bm.SizeOfBitMap == 800, "size uninitialised"); + ok(bm.BitMapBuffer == buff,"buffer uninitialised"); + ok(buff[0] == 77 && buff[79] == 77, "wrote to buffer"); +} + +static void test_RtlSetAllBits(void) +{ + if (!pRtlSetAllBits) + return; + + memset(buff, 0 , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, 1); + + pRtlSetAllBits(&bm); + ok(buff[0] == 0xff && buff[1] == 0xff && buff[2] == 0xff && + buff[3] == 0xff, "didnt round up size"); + ok(buff[4] == 0, "set more than rounded size"); + + /* Test inlined version */ + memset(buff, 0 , sizeof(buff)); + RtlSetAllBits(&bm); + ok(buff[0] == 0xff && buff[1] == 0xff && buff[2] == 0xff && + buff[3] == 0xff, "didnt round up size"); + ok(buff[4] == 0, "set more than rounded size"); +} + +static void test_RtlClearAllBits() +{ + if (!pRtlClearAllBits) + return; + + memset(buff, 0xff , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, 1); + + pRtlClearAllBits(&bm); + ok(!buff[0] && !buff[1] && !buff[2] && !buff[3], "didnt round up size"); + ok(buff[4] == 0xff, "cleared more than rounded size"); + + /* Test inlined version */ + memset(buff, 0xff , sizeof(buff)); + RtlClearAllBits(&bm); + ok(!buff[0] && !buff[1] && !buff[2] && !buff[3] , "didnt round up size"); + ok(buff[4] == 0xff, "cleared more than rounded size"); +} + +static void test_RtlSetBits() +{ + if (!pRtlSetBits) + return; + + memset(buff, 0 , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + pRtlSetBits(&bm, 0, 1); + ok(buff[0] == 1, "didnt set 1st bit"); + + buff[0] = 0; + pRtlSetBits(&bm, 7, 2); + ok(buff[0] == 0x80 && buff[1] == 1, "didnt span w/len < 8"); + + buff[0] = buff[1] = 0; + pRtlSetBits(&bm, 7, 10); + ok(buff[0] == 0x80 && buff[1] == 0xff && buff[2] == 1, "didnt span w/len > 8"); + + buff[0] = buff[1] = buff[2] = 0; + pRtlSetBits(&bm, 0, 8); /* 1st byte */ + ok(buff[0] == 0xff, "didnt set all bits"); + ok(!buff[1], "set too many bits"); + + pRtlSetBits(&bm, sizeof(buff)*8-1, 1); /* last bit */ + ok(buff[sizeof(buff)-1] == 0x80, "didnt set last bit"); +} + +static void test_RtlClearBits() +{ + if (!pRtlClearBits) + return; + + memset(buff, 0xff , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + pRtlClearBits(&bm, 0, 1); + ok(buff[0] == 0xfe, "didnt clear 1st bit"); + + buff[0] = 0xff; + pRtlClearBits(&bm, 7, 2); + ok(buff[0] == 0x7f && buff[1] == 0xfe, "didnt span w/len < 8"); + + buff[0] = buff[1] = 0xff; + pRtlClearBits(&bm, 7, 10); + ok(buff[0] == 0x7f && buff[1] == 0 && buff[2] == 0xfe, "didnt span w/len > 8"); + + buff[0] = buff[1] = buff[2] = 0xff; + pRtlClearBits(&bm, 0, 8); /* 1st byte */ + ok(!buff[0], "didnt clear all bits"); + ok(buff[1] == 0xff, "cleared too many bits"); + + pRtlClearBits(&bm, sizeof(buff)*8-1, 1); + ok(buff[sizeof(buff)-1] == 0x7f, "didnt set last bit"); +} + +static void test_RtlCheckBit() +{ + BOOLEAN bRet; + + memset(buff, 0 , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + pRtlSetBits(&bm, 0, 1); + pRtlSetBits(&bm, 7, 2); + pRtlSetBits(&bm, sizeof(buff)*8-1, 1); + + bRet = RtlCheckBit(&bm, 0); + ok (bRet, "didnt find set bit"); + bRet = RtlCheckBit(&bm, 7); + ok (bRet, "didnt find set bit"); + bRet = RtlCheckBit(&bm, 8); + ok (bRet, "didnt find set bit"); + bRet = RtlCheckBit(&bm, sizeof(buff)*8-1); + ok (bRet, "didnt find set bit"); + bRet = RtlCheckBit(&bm, 1); + ok (!bRet, "found non set bit"); + bRet = RtlCheckBit(&bm, sizeof(buff)*8-2); + ok (!bRet, "found non set bit"); +} + +static void test_RtlAreBitsSet() +{ + BOOLEAN bRet; + + if (!pRtlAreBitsSet) + return; + + memset(buff, 0 , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + bRet = pRtlAreBitsSet(&bm, 0, 1); + ok (!bRet, "found set bits after init"); + + pRtlSetBits(&bm, 0, 1); + bRet = pRtlAreBitsSet(&bm, 0, 1); + ok (bRet, "didnt find set bits"); + + buff[0] = 0; + pRtlSetBits(&bm, 7, 2); + bRet = pRtlAreBitsSet(&bm, 7, 2); + ok(bRet, "didnt find w/len < 8"); + bRet = pRtlAreBitsSet(&bm, 6, 3); + ok(!bRet, "found non set bit"); + bRet = pRtlAreBitsSet(&bm, 7, 3); + ok(!bRet, "found non set bit"); + + buff[0] = buff[1] = 0; + pRtlSetBits(&bm, 7, 10); + bRet = pRtlAreBitsSet(&bm, 7, 10); + ok(bRet, "didnt find w/len < 8"); + bRet = pRtlAreBitsSet(&bm, 6, 11); + ok(!bRet, "found non set bit"); + bRet = pRtlAreBitsSet(&bm, 7, 11); + ok(!bRet, "found non set bit"); + + buff[0] = buff[1] = buff[2] = 0; + pRtlSetBits(&bm, 0, 8); /* 1st byte */ + bRet = pRtlAreBitsSet(&bm, 0, 8); + ok(bRet, "didn't find whole byte"); + + pRtlSetBits(&bm, sizeof(buff)*8-1, 1); + bRet = pRtlAreBitsSet(&bm, sizeof(buff)*8-1, 1); + ok(bRet, "didn't find last bit"); +} + +static void test_RtlAreBitsClear() +{ + BOOLEAN bRet; + + if (!pRtlAreBitsClear) + return; + + memset(buff, 0xff , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + bRet = pRtlAreBitsClear(&bm, 0, 1); + ok (!bRet, "found clear bits after init"); + + pRtlClearBits(&bm, 0, 1); + bRet = pRtlAreBitsClear(&bm, 0, 1); + ok (bRet, "didnt find set bits"); + + buff[0] = 0xff; + pRtlClearBits(&bm, 7, 2); + bRet = pRtlAreBitsClear(&bm, 7, 2); + ok(bRet, "didnt find w/len < 8"); + bRet = pRtlAreBitsClear(&bm, 6, 3); + ok(!bRet, "found non clear bit"); + bRet = pRtlAreBitsClear(&bm, 7, 3); + ok(!bRet, "found non clear bit"); + + buff[0] = buff[1] = 0xff; + pRtlClearBits(&bm, 7, 10); + bRet = pRtlAreBitsClear(&bm, 7, 10); + ok(bRet, "didnt find w/len < 8"); + bRet = pRtlAreBitsClear(&bm, 6, 11); + ok(!bRet, "found non clear bit"); + bRet = pRtlAreBitsClear(&bm, 7, 11); + ok(!bRet, "found non clear bit"); + + buff[0] = buff[1] = buff[2] = 0xff; + pRtlClearBits(&bm, 0, 8); /* 1st byte */ + bRet = pRtlAreBitsClear(&bm, 0, 8); + ok(bRet, "didn't find whole byte"); + + pRtlClearBits(&bm, sizeof(buff)*8-1, 1); + bRet = pRtlAreBitsClear(&bm, sizeof(buff)*8-1, 1); + ok(bRet, "didn't find last bit"); +} + +static void test_RtlNumberOfSetBits() +{ + ULONG ulCount; + + if (!pRtlNumberOfSetBits) + return; + + memset(buff, 0 , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + ulCount = pRtlNumberOfSetBits(&bm); + ok(ulCount == 0, "set bits after init"); + + pRtlSetBits(&bm, 0, 1); /* Set 1st bit */ + ulCount = pRtlNumberOfSetBits(&bm); + ok(ulCount == 1, "count wrong"); + + pRtlSetBits(&bm, 7, 8); /* 8 more, spanning bytes 1-2 */ + ulCount = pRtlNumberOfSetBits(&bm); + ok(ulCount == 8+1, "count wrong"); + + pRtlSetBits(&bm, 17, 33); /* 33 more crossing ULONG boundary */ + ulCount = pRtlNumberOfSetBits(&bm); + ok(ulCount == 8+1+33, "count wrong"); + + pRtlSetBits(&bm, sizeof(buff)*8-1, 1); /* Set last bit */ + ulCount = pRtlNumberOfSetBits(&bm); + ok(ulCount == 8+1+33+1, "count wrong"); +} + +static void test_RtlNumberOfClearBits() +{ + ULONG ulCount; + + if (!pRtlNumberOfClearBits) + return; + + memset(buff, 0xff , sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + ulCount = pRtlNumberOfClearBits(&bm); + ok(ulCount == 0, "cleared bits after init"); + + pRtlClearBits(&bm, 0, 1); /* Set 1st bit */ + ulCount = pRtlNumberOfClearBits(&bm); + ok(ulCount == 1, "count wrong"); + + pRtlClearBits(&bm, 7, 8); /* 8 more, spanning bytes 1-2 */ + ulCount = pRtlNumberOfClearBits(&bm); + ok(ulCount == 8+1, "count wrong"); + + pRtlClearBits(&bm, 17, 33); /* 33 more crossing ULONG boundary */ + ulCount = pRtlNumberOfClearBits(&bm); + ok(ulCount == 8+1+33, "count wrong"); + + pRtlClearBits(&bm, sizeof(buff)*8-1, 1); /* Set last bit */ + ulCount = pRtlNumberOfClearBits(&bm); + ok(ulCount == 8+1+33+1, "count wrong"); +} + +/* Note: this tests RtlFindSetBits also */ +static void test_RtlFindSetBitsAndClear() +{ + BOOLEAN bRet; + ULONG ulPos; + + if (!pRtlFindSetBitsAndClear) + return; + + memset(buff, 0, sizeof(buff)); + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + pRtlSetBits(&bm, 0, 32); + ulPos = pRtlFindSetBitsAndClear(&bm, 32, 0); + ok (ulPos == 0, "didnt find bits"); + if(ulPos == 0) + { + bRet = pRtlAreBitsClear(&bm, 0, 32); + ok (bRet, "found but didnt clear"); + } + + memset(buff, 0 , sizeof(buff)); + pRtlSetBits(&bm, 40, 77); + ulPos = pRtlFindSetBitsAndClear(&bm, 77, 0); + ok (ulPos == 40, "didnt find bits"); + if(ulPos == 40) + { + bRet = pRtlAreBitsClear(&bm, 40, 77); + ok (bRet, "found but didnt clear"); + } +} + +/* Note: this tests RtlFindClearBits also */ +static void test_RtlFindClearBitsAndSet() +{ + BOOLEAN bRet; + ULONG ulPos; + + if (!pRtlFindClearBitsAndSet) + return; + + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + memset(buff, 0xff, sizeof(buff)); + pRtlSetBits(&bm, 0, 32); + ulPos = pRtlFindSetBitsAndClear(&bm, 32, 0); + ok (ulPos == 0, "didnt find bits"); + if(ulPos == 0) + { + bRet = pRtlAreBitsClear(&bm, 0, 32); + ok (bRet, "found but didnt clear"); + } + + memset(buff, 0xff , sizeof(buff)); + pRtlClearBits(&bm, 40, 77); + ulPos = pRtlFindClearBitsAndSet(&bm, 77, 50); + ok (ulPos == 40, "didnt find bits"); + if(ulPos == 40) + { + bRet = pRtlAreBitsSet(&bm, 40, 77); + ok (bRet, "found but didnt set"); + } +} + +static void test_RtlFindMostSignificantBit() +{ + int i; + CCHAR cPos; + ULONGLONG ulLong; + + if (!pRtlFindMostSignificantBit) + return; + + for (i = 0; i < 64; i++) + { + ulLong = 1ul; + ulLong <<= i; + + cPos = pRtlFindMostSignificantBit(ulLong); + ok (cPos == i, "didnt find MSB %lld %d %d", ulLong, i, cPos); + } + cPos = pRtlFindMostSignificantBit(0); + ok (cPos == -1, "found bit when not set"); +} + +static void test_RtlFindLeastSignificantBit() +{ + int i; + CCHAR cPos; + ULONGLONG ulLong; + + if (!pRtlFindLeastSignificantBit) + return; + + for (i = 0; i < 64; i++) + { + ulLong = 1ul; + ulLong <<= i; + + cPos = pRtlFindLeastSignificantBit(ulLong); + ok (cPos == i, "didnt find LSB at %d", cPos); + } + cPos = pRtlFindLeastSignificantBit(0); + ok (cPos == -1, "found bit when not set"); +} + +/* Note: Also tests RtlFindLongestRunSet() */ +static void test_RtlFindSetRuns() +{ + RTL_BITMAP_RUN runs[16]; + ULONG ulCount; + + if (!pRtlFindSetRuns) + return; + + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + memset(buff, 0, sizeof(buff)); + ulCount = pRtlFindSetRuns(&bm, runs, 16, TRUE); + ok (ulCount == 0, "found set bits in empty bitmap"); + + memset(runs, 0, sizeof(runs)); + memset(buff, 0xff, sizeof(buff)); + ulCount = pRtlFindSetRuns(&bm, runs, 16, TRUE); + ok (ulCount == 1, "didnt find set bits"); + ok (runs[0].StartOfRun == 0,"bad start"); + ok (runs[0].SizeOfRun == sizeof(buff)*8,"bad size"); + + /* Set up 3 runs */ + memset(runs, 0, sizeof(runs)); + memset(buff, 0, sizeof(buff)); + pRtlSetBits(&bm, 7, 19); + pRtlSetBits(&bm, 101, 3); + pRtlSetBits(&bm, 1877, 33); + + /* Get first 2 */ + ulCount = pRtlFindSetRuns(&bm, runs, 2, FALSE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 19 + 3,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[2].StartOfRun == 0,"found extra run"); + + /* Get longest 3 */ + memset(runs, 0, sizeof(runs)); + ulCount = pRtlFindSetRuns(&bm, runs, 2, TRUE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 1877,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 1877,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 33 + 19,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[2].StartOfRun == 0,"found extra run"); + + /* Get all 3 */ + memset(runs, 0, sizeof(runs)); + ulCount = pRtlFindSetRuns(&bm, runs, 3, TRUE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101 || + runs[0].StartOfRun == 1877,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101 || + runs[1].StartOfRun == 1877,"bad find"); + ok (runs[2].StartOfRun == 7 || runs[2].StartOfRun == 101 || + runs[2].StartOfRun == 1877,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun + + runs[2].SizeOfRun == 19 + 3 + 33,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[1].StartOfRun != runs[2].StartOfRun,"found run twice"); + ok (runs[3].StartOfRun == 0,"found extra run"); + + if (pRtlFindLongestRunSet) + { + ULONG ulStart = 0; + + ulCount = pRtlFindLongestRunSet(&bm, &ulStart); + ok(ulCount == 33 && ulStart == 1877,"didn't find longest %ld %ld",ulCount,ulStart); + + memset(buff, 0, sizeof(buff)); + ulCount = pRtlFindLongestRunSet(&bm, &ulStart); + ok(ulCount == 0,"found longest when none set"); + } +} + +/* Note: Also tests RtlFindLongestRunClear() */ +static void test_RtlFindClearRuns() +{ + RTL_BITMAP_RUN runs[16]; + ULONG ulCount; + + if (!pRtlFindClearRuns) + return; + + pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8); + + memset(buff, 0xff, sizeof(buff)); + ulCount = pRtlFindClearRuns(&bm, runs, 16, TRUE); + ok (ulCount == 0, "found clear bits in full bitmap"); + + memset(runs, 0, sizeof(runs)); + memset(buff, 0, sizeof(buff)); + ulCount = pRtlFindClearRuns(&bm, runs, 16, TRUE); + ok (ulCount == 1, "didnt find clear bits"); + ok (runs[0].StartOfRun == 0,"bad start"); + ok (runs[0].SizeOfRun == sizeof(buff)*8,"bad size"); + + /* Set up 3 runs */ + memset(runs, 0, sizeof(runs)); + memset(buff, 0xff, sizeof(buff)); + pRtlClearBits(&bm, 7, 19); + pRtlClearBits(&bm, 101, 3); + pRtlClearBits(&bm, 1877, 33); + + /* Get first 2 */ + ulCount = pRtlFindClearRuns(&bm, runs, 2, FALSE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 19 + 3,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[2].StartOfRun == 0,"found extra run"); + + /* Get longest 3 */ + memset(runs, 0, sizeof(runs)); + ulCount = pRtlFindClearRuns(&bm, runs, 2, TRUE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 1877,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 1877,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 33 + 19,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[2].StartOfRun == 0,"found extra run"); + + /* Get all 3 */ + memset(runs, 0, sizeof(runs)); + ulCount = pRtlFindClearRuns(&bm, runs, 3, TRUE); + ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101 || + runs[0].StartOfRun == 1877,"bad find"); + ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101 || + runs[1].StartOfRun == 1877,"bad find"); + ok (runs[2].StartOfRun == 7 || runs[2].StartOfRun == 101 || + runs[2].StartOfRun == 1877,"bad find"); + ok (runs[0].SizeOfRun + runs[1].SizeOfRun + + runs[2].SizeOfRun == 19 + 3 + 33,"bad size"); + ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice"); + ok (runs[1].StartOfRun != runs[2].StartOfRun,"found run twice"); + ok (runs[3].StartOfRun == 0,"found extra run"); + + if (pRtlFindLongestRunClear) + { + ULONG ulStart = 0; + + ulCount = pRtlFindLongestRunClear(&bm, &ulStart); + ok(ulCount == 33 && ulStart == 1877,"didn't find longest"); + + memset(buff, 0xff, sizeof(buff)); + ulCount = pRtlFindLongestRunClear(&bm, &ulStart); + ok(ulCount == 0,"found longest when none clear"); + } + +} + +START_TEST(rtlbitmap) +{ + InitFunctionPtrs(); + + if (pRtlInitializeBitMap) + { + test_RtlInitializeBitMap(); + test_RtlSetAllBits(); + test_RtlClearAllBits(); + test_RtlSetBits(); + test_RtlClearBits(); + test_RtlCheckBit(); + test_RtlAreBitsSet(); + test_RtlAreBitsClear(); + test_RtlNumberOfSetBits(); + test_RtlNumberOfClearBits(); + test_RtlFindSetBitsAndClear(); + test_RtlFindClearBitsAndSet(); + test_RtlFindMostSignificantBit(); + test_RtlFindLeastSignificantBit(); + test_RtlFindSetRuns(); + test_RtlFindClearRuns(); + } +} diff --git a/include/ntddk.h b/include/ntddk.h index 0bf93db57f7..58f4bb818c9 100644 --- a/include/ntddk.h +++ b/include/ntddk.h @@ -1095,6 +1095,86 @@ NtAccessCheck( OUT PULONG GrantedAccess, OUT PBOOLEAN AccessStatus); +/* bitmap functions */ + +/* Bitmap data type */ +typedef struct tagRTL_BITMAP +{ + ULONG SizeOfBitMap; /* Number of bits in the bitmap */ + LPBYTE BitMapBuffer; /* Bitmap data, assumed sized to a DWORD boundary */ +} RTL_BITMAP, *PRTL_BITMAP; + +typedef const RTL_BITMAP* PCRTL_BITMAP; + +/* Bit run data type */ +typedef struct tagRTL_BITMAP_RUN +{ + ULONG StartOfRun; /* Bit position at which run starts - FIXME: Name? */ + ULONG SizeOfRun; /* Size of the run in bits - FIXME: Name? */ +} RTL_BITMAP_RUN, *PRTL_BITMAP_RUN; + +typedef const RTL_BITMAP_RUN* PCRTL_BITMAP_RUN; + +/* Bitmap functions */ +VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP,LPBYTE,ULONG); +VOID WINAPI RtlSetAllBits(PRTL_BITMAP); +VOID WINAPI RtlClearAllBits(PRTL_BITMAP); +VOID WINAPI RtlSetBits(PRTL_BITMAP,ULONG,ULONG); +VOID WINAPI RtlClearBits(PRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlFindSetBits(PCRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlFindClearBits(PCRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlFindSetBitsAndClear(PRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlFindClearBitsAndSet(PRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP); +ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP); +ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN); +ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN); +ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP,PULONG); +ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP,PULONG); +BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP,ULONG,ULONG); +BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP,ULONG,ULONG); +ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP,ULONG,PULONG); +ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP,ULONG,PULONG); +ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP,ULONG,PULONG); +ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP,ULONG,PULONG); +CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG); +CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG); + +/* Inline the trivial calls */ +#define RtlInitializeBitMap(p,b,s) \ + do { \ + PRTL_BITMAP _p = (p); \ + _p->SizeOfBitMap = (s); \ + _p->BitMapBuffer = (b); \ + } while(0) + +#define RtlSetAllBits(p) \ + do { \ + PRTL_BITMAP _p = (p); \ + memset(_p->BitMapBuffer,0xff,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \ + } while(0) + +#define RtlClearAllBits(p) \ + do {\ + PRTL_BITMAP _p = (p);\ + memset(_p->BitMapBuffer,0,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \ + } while(0) + +inline static BOOLEAN RtlCheckBit(PCRTL_BITMAP lpBits, ULONG ulBit) +{ + if (lpBits && ulBit < lpBits->SizeOfBitMap && + lpBits->BitMapBuffer[ulBit >> 3] & (1 << (ulBit & 7))) + return TRUE; + return FALSE; +} + +/* Endianness */ +#define RtlStoreUlong(p,v) do { ULONG _v = (v); memcpy((p), &_v, sizeof(_v)); } while (0) +#define RtlRetrieveUlong(p,s) memcpy((p), (s), sizeof(ULONG)) + +#define RtlStoreUlonglong(p,v) do { ULONGLONG _v = (v); memcpy((p), &_v, sizeof(_v)); } while (0) +#define RtlRetrieveUlonglong(p,s) memcpy((p), (s), sizeof(ULONGLONG)) + #ifdef __cplusplus } #endif -- 2.11.4.GIT