Update RTL_BITMAP and RTL_BITMAP_RUN
Francois Gouget
fgouget at free.fr
Sun Aug 22 14:23:02 CDT 2004
I found these types in ddk/ntddk.h in the 2000 DDK. Our types are
correct except for slight name differences and for BitMapBuffer/Buffer
which should be a PULONG. So I updated these types in winternl.h and the
next step will be to move them to ddk/ntddk.h (it just seemed better to
do it in two steps). When these types are moved there we will be able to
compile dlls/shell32/tests/rtlbitmap.c on Windows (I used a hack to test
that and it works).
The switch from LPBYTE to PULONG for BitMapBuffer/Buffer impacs our
algorithms because we use pointer arithmetic. One solution would be to
modify them to handle 4 bytes at a time instead of just one byte like
they do now. However that seemed too risky so I just cast the pointer as
a BYTE* before using it. If someone feels up to it, the algorithms
can be updated after this patch is applied.
Changelog:
* include/winternl.h
dlls/ntdll/rtlbitmap.c
dlls/ntdll/tests/rtlbitmap.c
Update RTL_BITMAP and RTL_BITMAP_RUN to match the 2000 DDK.
--
Francois Gouget fgouget at free.fr http://fgouget.free.fr/
Cahn's Axiom: When all else fails, read the instructions.
-------------- next part --------------
Index: include/winternl.h
===================================================================
RCS file: /var/cvs/wine/include/winternl.h,v
retrieving revision 1.88
diff -u -r1.88 winternl.h
--- include/winternl.h 20 Aug 2004 19:24:33 -0000 1.88
+++ include/winternl.h 21 Aug 2004 17:44:09 -0000
@@ -83,14 +83,14 @@
typedef struct tagRTL_BITMAP {
ULONG SizeOfBitMap; /* Number of bits in the bitmap */
- LPBYTE BitMapBuffer; /* Bitmap data, assumed sized to a DWORD boundary */
+ PULONG Buffer; /* Bitmap data, assumed sized to a DWORD boundary */
} RTL_BITMAP, *PRTL_BITMAP;
typedef const RTL_BITMAP *PCRTL_BITMAP;
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? */
+ ULONG StartingIndex; /* Bit position at which run starts */
+ ULONG NumberOfBits; /* Size of the run in bits */
} RTL_BITMAP_RUN, *PRTL_BITMAP_RUN;
typedef const RTL_BITMAP_RUN *PCRTL_BITMAP_RUN;
@@ -1462,7 +1462,7 @@
NTSTATUS WINAPI RtlInitUnicodeStringEx(PUNICODE_STRING,PCWSTR);
NTSTATUS WINAPI RtlInitializeCriticalSection(RTL_CRITICAL_SECTION *);
NTSTATUS WINAPI RtlInitializeCriticalSectionAndSpinCount(RTL_CRITICAL_SECTION *,DWORD);
-void WINAPI RtlInitializeBitMap(PRTL_BITMAP,LPBYTE,ULONG);
+void WINAPI RtlInitializeBitMap(PRTL_BITMAP,PULONG,ULONG);
void WINAPI RtlInitializeResource(LPRTL_RWLOCK);
BOOL WINAPI RtlInitializeSid(PSID,PSID_IDENTIFIER_AUTHORITY,BYTE);
@@ -1618,7 +1618,7 @@
inline static BOOLEAN RtlCheckBit(PCRTL_BITMAP lpBits, ULONG ulBit)
{
if (lpBits && ulBit < lpBits->SizeOfBitMap &&
- lpBits->BitMapBuffer[ulBit >> 3] & (1 << (ulBit & 7)))
+ lpBits->Buffer[ulBit >> 5] & (1 << (ulBit & 31)))
return TRUE;
return FALSE;
}
@@ -1626,20 +1626,20 @@
#define RtlClearAllBits(p) \
do { \
PRTL_BITMAP _p = (p); \
- memset(_p->BitMapBuffer,0,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \
+ memset(_p->Buffer,0,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \
} while (0)
#define RtlInitializeBitMap(p,b,s) \
do { \
PRTL_BITMAP _p = (p); \
_p->SizeOfBitMap = (s); \
- _p->BitMapBuffer = (b); \
+ _p->Buffer = (b); \
} while (0)
#define RtlSetAllBits(p) \
do { \
PRTL_BITMAP _p = (p); \
- memset(_p->BitMapBuffer,0xff,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \
+ memset(_p->Buffer,0xff,((_p->SizeOfBitMap + 31) & 0xffffffe0) >> 3); \
} while (0)
/* These are implemented as __fastcall, so we can't let Winelib apps link with them */
Index: dlls/ntdll/rtlbitmap.c
===================================================================
RCS file: /var/cvs/wine/dlls/ntdll/rtlbitmap.c,v
retrieving revision 1.9
diff -u -r1.9 rtlbitmap.c
--- dlls/ntdll/rtlbitmap.c 15 Jun 2004 00:47:00 -0000 1.9
+++ dlls/ntdll/rtlbitmap.c 21 Aug 2004 17:52:14 -0000
@@ -76,11 +76,11 @@
* in size (irrespective of ulSize given).
*/
#undef RtlInitializeBitMap
-VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, LPBYTE lpBuff, ULONG ulSize)
+VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, PULONG lpBuff, ULONG ulSize)
{
TRACE("(%p,%p,%ld)\n", lpBits,lpBuff,ulSize);
lpBits->SizeOfBitMap = ulSize;
- lpBits->BitMapBuffer = lpBuff;
+ lpBits->Buffer = lpBuff;
}
/*************************************************************************
@@ -98,7 +98,7 @@
VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
{
TRACE("(%p)\n", lpBits);
- memset(lpBits->BitMapBuffer, 0xff, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
+ memset(lpBits->Buffer, 0xff, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
}
/*************************************************************************
@@ -116,7 +116,7 @@
VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
{
TRACE("(%p)\n", lpBits);
- memset(lpBits->BitMapBuffer, 0, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
+ memset(lpBits->Buffer, 0, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
}
/*************************************************************************
@@ -143,7 +143,7 @@
ulCount > lpBits->SizeOfBitMap - ulStart)
return;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
/* Set bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
@@ -200,7 +200,7 @@
ulCount > lpBits->SizeOfBitMap - ulStart)
return;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
/* Clear bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
@@ -260,7 +260,7 @@
ulCount > lpBits->SizeOfBitMap - ulStart)
return FALSE;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
/* Check bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
@@ -330,7 +330,7 @@
ulCount > lpBits->SizeOfBitMap - ulStart)
return FALSE;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
/* Check bits in first byte, if ulStart isn't a byte boundary */
if (ulStart & 7)
@@ -534,7 +534,7 @@
if (lpBits)
{
- LPBYTE lpOut = lpBits->BitMapBuffer;
+ LPBYTE lpOut = lpBits->Buffer;
ULONG ulCount, ulRemainder;
BYTE bMasked;
@@ -654,7 +654,7 @@
*/
static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
{
- if (((const RTL_BITMAP_RUN*)lhs)->SizeOfRun > ((const RTL_BITMAP_RUN*)rhs)->SizeOfRun)
+ if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
return -1;
return 1;
}
@@ -669,7 +669,7 @@
LPBYTE lpOut;
ULONG ulFoundAt = 0, ulCount = 0;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
while (1)
{
@@ -757,7 +757,7 @@
LPBYTE lpOut;
ULONG ulFoundAt = 0, ulCount = 0;
- lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
while (1)
{
@@ -963,21 +963,21 @@
qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
/* Replace last run if this one is bigger */
- if (ulSize > lpSeries[ulRuns - 1].SizeOfRun)
+ if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
{
- lpSeries[ulRuns - 1].StartOfRun = ulNextPos;
- lpSeries[ulRuns - 1].SizeOfRun = ulSize;
+ 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].SizeOfRun)
+ if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
bNeedSort = TRUE;
}
}
else
{
/* Append to found runs */
- lpSeries[ulRuns].StartOfRun = ulNextPos;
- lpSeries[ulRuns].SizeOfRun = ulSize;
+ lpSeries[ulRuns].StartingIndex = ulNextPos;
+ lpSeries[ulRuns].NumberOfBits = ulSize;
ulRuns++;
if (!bLongest && ulRuns == ulCount)
@@ -1053,8 +1053,8 @@
if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
{
if (pulStart)
- *pulStart = br.StartOfRun;
- return br.SizeOfRun;
+ *pulStart = br.StartingIndex;
+ return br.NumberOfBits;
}
return 0;
}
@@ -1080,8 +1080,8 @@
if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
{
if (pulStart)
- *pulStart = br.StartOfRun;
- return br.SizeOfRun;
+ *pulStart = br.StartingIndex;
+ return br.NumberOfBits;
}
return 0;
}
Index: dlls/ntdll/tests/rtlbitmap.c
===================================================================
RCS file: /var/cvs/wine/dlls/ntdll/tests/rtlbitmap.c,v
retrieving revision 1.7
diff -u -r1.7 rtlbitmap.c
--- dlls/ntdll/tests/rtlbitmap.c 14 Aug 2004 00:42:12 -0000 1.7
+++ dlls/ntdll/tests/rtlbitmap.c 21 Aug 2004 18:26:54 -0000
@@ -75,7 +98,7 @@
static void test_RtlInitializeBitMap(void)
{
bm.SizeOfBitMap = 0;
- bm.BitMapBuffer = 0;
+ bm.Buffer = 0;
memset(buff, 0, sizeof(buff));
buff[0] = 77; /* Check buffer is not written to during init */
@@ -83,14 +106,16 @@
pRtlInitializeBitMap(&bm, buff, 800);
ok(bm.SizeOfBitMap == 800, "size uninitialised\n");
- ok(bm.BitMapBuffer == buff,"buffer uninitialised\n");
+ ok(bm.Buffer == (PULONG)buff,"buffer uninitialised\n");
ok(buff[0] == 77 && buff[79] == 77, "wrote to buffer\n");
- /* Test inlined version */
+#ifdef RtlInitializeBitMap
+ /* Test macro version */
RtlInitializeBitMap(&bm, buff, 800);
ok(bm.SizeOfBitMap == 800, "size uninitialised\n");
- ok(bm.BitMapBuffer == buff,"buffer uninitialised\n");
+ ok(bm.Buffer == (PULONG)buff,"buffer uninitialised\n");
ok(buff[0] == 77 && buff[79] == 77, "wrote to buffer\n");
+#endif
}
static void test_RtlSetAllBits(void)
@@ -106,12 +131,14 @@
buff[3] == 0xff, "didn't round up size\n");
ok(buff[4] == 0, "set more than rounded size\n");
- /* Test inlined version */
+#ifdef RtlSetAllBits
+ /* Test macro version */
memset(buff, 0 , sizeof(buff));
RtlSetAllBits(&bm);
ok(buff[0] == 0xff && buff[1] == 0xff && buff[2] == 0xff &&
buff[3] == 0xff, "didn't round up size\n");
ok(buff[4] == 0, "set more than rounded size\n");
+#endif
}
static void test_RtlClearAllBits()
@@ -126,11 +153,13 @@
ok(!buff[0] && !buff[1] && !buff[2] && !buff[3], "didn't round up size\n");
ok(buff[4] == 0xff, "cleared more than rounded size\n");
- /* Test inlined version */
+#ifdef RtlSetAllBits
+ /* Test macro version */
memset(buff, 0xff , sizeof(buff));
RtlClearAllBits(&bm);
ok(!buff[0] && !buff[1] && !buff[2] && !buff[3] , "didn't round up size\n");
ok(buff[4] == 0xff, "cleared more than rounded size\n");
+#endif
}
static void test_RtlSetBits()
@@ -498,8 +527,8 @@
memset(buff, 0xff, sizeof(buff));
ulCount = pRtlFindSetRuns(&bm, runs, 16, TRUE);
ok (ulCount == 1, "didn't find set bits\n");
- ok (runs[0].StartOfRun == 0,"bad start\n");
- ok (runs[0].SizeOfRun == sizeof(buff)*8,"bad size\n");
+ ok (runs[0].StartingIndex == 0,"bad start\n");
+ ok (runs[0].NumberOfBits == sizeof(buff)*8,"bad size\n");
/* Set up 3 runs */
memset(runs, 0, sizeof(runs));
@@ -510,35 +539,35 @@
/* Get first 2 */
ulCount = pRtlFindSetRuns(&bm, runs, 2, FALSE);
- ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101,"bad find\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 19 + 3,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[2].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 19 + 3,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[2].StartingIndex == 0,"found extra run\n");
/* 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\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 1877,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 33 + 19,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[2].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 1877,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 1877,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 33 + 19,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[2].StartingIndex == 0,"found extra run\n");
/* 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\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101 ||
- runs[1].StartOfRun == 1877,"bad find\n");
- ok (runs[2].StartOfRun == 7 || runs[2].StartOfRun == 101 ||
- runs[2].StartOfRun == 1877,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun
- + runs[2].SizeOfRun == 19 + 3 + 33,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[1].StartOfRun != runs[2].StartOfRun,"found run twice\n");
- ok (runs[3].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101 ||
+ runs[0].StartingIndex == 1877,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101 ||
+ runs[1].StartingIndex == 1877,"bad find\n");
+ ok (runs[2].StartingIndex == 7 || runs[2].StartingIndex == 101 ||
+ runs[2].StartingIndex == 1877,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits
+ + runs[2].NumberOfBits == 19 + 3 + 33,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[1].StartingIndex != runs[2].StartingIndex,"found run twice\n");
+ ok (runs[3].StartingIndex == 0,"found extra run\n");
if (pRtlFindLongestRunSet)
{
@@ -572,8 +601,8 @@
memset(buff, 0, sizeof(buff));
ulCount = pRtlFindClearRuns(&bm, runs, 16, TRUE);
ok (ulCount == 1, "didn't find clear bits\n");
- ok (runs[0].StartOfRun == 0,"bad start\n");
- ok (runs[0].SizeOfRun == sizeof(buff)*8,"bad size\n");
+ ok (runs[0].StartingIndex == 0,"bad start\n");
+ ok (runs[0].NumberOfBits == sizeof(buff)*8,"bad size\n");
/* Set up 3 runs */
memset(runs, 0, sizeof(runs));
@@ -584,35 +613,35 @@
/* Get first 2 */
ulCount = pRtlFindClearRuns(&bm, runs, 2, FALSE);
- ok (runs[0].StartOfRun == 7 || runs[0].StartOfRun == 101,"bad find\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 19 + 3,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[2].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 19 + 3,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[2].StartingIndex == 0,"found extra run\n");
/* 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\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 1877,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun == 33 + 19,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[2].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 1877,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 1877,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 33 + 19,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[2].StartingIndex == 0,"found extra run\n");
/* 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\n");
- ok (runs[1].StartOfRun == 7 || runs[1].StartOfRun == 101 ||
- runs[1].StartOfRun == 1877,"bad find\n");
- ok (runs[2].StartOfRun == 7 || runs[2].StartOfRun == 101 ||
- runs[2].StartOfRun == 1877,"bad find\n");
- ok (runs[0].SizeOfRun + runs[1].SizeOfRun
- + runs[2].SizeOfRun == 19 + 3 + 33,"bad size\n");
- ok (runs[0].StartOfRun != runs[1].StartOfRun,"found run twice\n");
- ok (runs[1].StartOfRun != runs[2].StartOfRun,"found run twice\n");
- ok (runs[3].StartOfRun == 0,"found extra run\n");
+ ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101 ||
+ runs[0].StartingIndex == 1877,"bad find\n");
+ ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101 ||
+ runs[1].StartingIndex == 1877,"bad find\n");
+ ok (runs[2].StartingIndex == 7 || runs[2].StartingIndex == 101 ||
+ runs[2].StartingIndex == 1877,"bad find\n");
+ ok (runs[0].NumberOfBits + runs[1].NumberOfBits
+ + runs[2].NumberOfBits == 19 + 3 + 33,"bad size\n");
+ ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
+ ok (runs[1].StartingIndex != runs[2].StartingIndex,"found run twice\n");
+ ok (runs[3].StartingIndex == 0,"found extra run\n");
if (pRtlFindLongestRunClear)
{
More information about the wine-patches
mailing list