[ros-diffs] [arty] 24265: Add missing file from the branch. Preparing to move build hosts.
arty at svn.reactos.org
arty at svn.reactos.org
Mon Sep 25 03:43:48 CEST 2006
Author: arty
Date: Mon Sep 25 05:43:46 2006
New Revision: 24265
URL: http://svn.reactos.org/svn/reactos?rev=24265&view=rev
Log:
Add missing file from the branch. Preparing to move build hosts.
Added:
branches/powerpc/reactos/lib/rtl/bitmap.c
Added: branches/powerpc/reactos/lib/rtl/bitmap.c
URL: http://svn.reactos.org/svn/reactos/branches/powerpc/reactos/lib/rtl/bitmap.c?rev=24265&view=auto
==============================================================================
--- branches/powerpc/reactos/lib/rtl/bitmap.c (added)
+++ branches/powerpc/reactos/lib/rtl/bitmap.c Mon Sep 25 05:43:46 2006
@@ -1,0 +1,979 @@
+/* COPYRIGHT: See COPYING in the top level directory
+ * PROJECT: ReactOS system libraries
+ * FILE: lib/rtl/bitmap.c
+ * PURPOSE: Bitmap functions
+ * PROGRAMMER: Eric Kohl
+ */
+
+/* INCLUDES *****************************************************************/
+
+#include <rtl.h>
+
+#define NDEBUG
+#include <debug.h>
+
+/* MACROS *******************************************************************/
+
+/* Bits set from LSB to MSB; used as mask for runs < 8 bits */
+static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
+
+/* Number of set bits for each value of a nibble; used for counting */
+static const BYTE NTDLL_nibbleBitCount[16] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
+};
+
+/* First set bit in a nibble; used for determining least significant bit */
+static const BYTE NTDLL_leastSignificant[16] = {
+ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
+};
+
+/* Last set bit in a nibble; used for determining most significant bit */
+static const signed char NTDLL_mostSignificant[16] = {
+ -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
+};
+
+/* PRIVATE FUNCTIONS *********************************************************/
+
+static
+int
+NTDLL_RunSortFn(const void *lhs,
+ const void *rhs)
+{
+ if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
+ return -1;
+ return 1;
+}
+
+static
+ULONG
+WINAPI
+NTDLL_FindRuns(PRTL_BITMAP lpBits,
+ PRTL_BITMAP_RUN lpSeries,
+ ULONG ulCount,
+ BOOLEAN bLongest,
+ ULONG (*fn)(PRTL_BITMAP,ULONG,PULONG))
+{
+ BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
+ ULONG ulPos = 0, ulRuns = 0;
+
+ if (!ulCount)
+ return ~0U;
+
+ while (ulPos < lpBits->SizeOfBitMap)
+ {
+ /* Find next set/clear run */
+ ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
+
+ if (ulNextPos == ~0U)
+ break;
+
+ if (bLongest && ulRuns == ulCount)
+ {
+ /* Sort runs with shortest at end, if they are out of order */
+ if (bNeedSort)
+ qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
+
+ /* Replace last run if this one is bigger */
+ if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
+ {
+ lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
+ lpSeries[ulRuns - 1].NumberOfBits = ulSize;
+
+ /* We need to re-sort the array, _if_ we didn't leave it sorted */
+ if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
+ bNeedSort = TRUE;
+ }
+ }
+ else
+ {
+ /* Append to found runs */
+ lpSeries[ulRuns].StartingIndex = ulNextPos;
+ lpSeries[ulRuns].NumberOfBits = ulSize;
+ ulRuns++;
+
+ if (!bLongest && ulRuns == ulCount)
+ break;
+ }
+ ulPos = ulNextPos + ulSize;
+ }
+ return ulRuns;
+}
+
+static
+ULONG
+NTDLL_FindSetRun(PRTL_BITMAP lpBits,
+ ULONG ulStart,
+ PULONG lpSize)
+{
+ LPBYTE lpOut;
+ ULONG ulFoundAt = 0, ulCount = 0;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
+
+ while (1)
+ {
+ /* Check bits in first byte */
+ const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
+ const BYTE bFirst = *lpOut & bMask;
+
+ if (bFirst)
+ {
+ /* Have a set bit in first byte */
+ if (bFirst != bMask)
+ {
+ /* Not every bit is set */
+ ULONG ulOffset;
+
+ if (bFirst & 0x0f)
+ ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
+ else
+ ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
+ ulStart += ulOffset;
+ ulFoundAt = ulStart;
+ for (;ulOffset < 8; ulOffset++)
+ {
+ if (!(bFirst & (1 << ulOffset)))
+ {
+ *lpSize = ulCount;
+ return ulFoundAt; /* Set from start, but not until the end */
+ }
+ ulCount++;
+ ulStart++;
+ }
+ /* Set to the end - go on to count further bits */
+ lpOut++;
+ break;
+ }
+ /* every bit from start until the end of the byte is set */
+ ulFoundAt = ulStart;
+ ulCount = 8 - (ulStart & 7);
+ ulStart = (ulStart & ~7u) + 8;
+ lpOut++;
+ break;
+ }
+ ulStart = (ulStart & ~7u) + 8;
+ lpOut++;
+ if (ulStart >= lpBits->SizeOfBitMap)
+ return ~0U;
+ }
+
+ /* Count blocks of 8 set bits */
+ while (*lpOut == 0xff)
+ {
+ ulCount += 8;
+ ulStart += 8;
+ if (ulStart >= lpBits->SizeOfBitMap)
+ {
+ *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
+ return ulFoundAt;
+ }
+ lpOut++;
+ }
+
+ /* Count remaining contiguous bits, if any */
+ if (*lpOut & 1)
+ {
+ ULONG ulOffset = 0;
+
+ for (;ulOffset < 7u; ulOffset++)
+ {
+ if (!(*lpOut & (1 << ulOffset)))
+ break;
+ ulCount++;
+ }
+ }
+ *lpSize = ulCount;
+ return ulFoundAt;
+}
+
+static
+ULONG
+NTDLL_FindClearRun(PRTL_BITMAP lpBits,
+ ULONG ulStart,
+ PULONG lpSize)
+{
+ LPBYTE lpOut;
+ ULONG ulFoundAt = 0, ulCount = 0;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
+
+ while (1)
+ {
+ /* Check bits in first byte */
+ const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
+ const BYTE bFirst = (~*lpOut) & bMask;
+
+ if (bFirst)
+ {
+ /* Have a clear bit in first byte */
+ if (bFirst != bMask)
+ {
+ /* Not every bit is clear */
+ ULONG ulOffset;
+
+ if (bFirst & 0x0f)
+ ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
+ else
+ ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
+ ulStart += ulOffset;
+ ulFoundAt = ulStart;
+ for (;ulOffset < 8; ulOffset++)
+ {
+ if (!(bFirst & (1 << ulOffset)))
+ {
+ *lpSize = ulCount;
+ return ulFoundAt; /* Clear from start, but not until the end */
+ }
+ ulCount++;
+ ulStart++;
+ }
+ /* Clear to the end - go on to count further bits */
+ lpOut++;
+ break;
+ }
+ /* Every bit from start until the end of the byte is clear */
+ ulFoundAt = ulStart;
+ ulCount = 8 - (ulStart & 7);
+ ulStart = (ulStart & ~7u) + 8;
+ lpOut++;
+ break;
+ }
+ ulStart = (ulStart & ~7u) + 8;
+ lpOut++;
+ if (ulStart >= lpBits->SizeOfBitMap)
+ return ~0U;
+ }
+
+ /* Count blocks of 8 clear bits */
+ while (!*lpOut)
+ {
+ ulCount += 8;
+ ulStart += 8;
+ if (ulStart >= lpBits->SizeOfBitMap)
+ {
+ *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
+ return ulFoundAt;
+ }
+ lpOut++;
+ }
+
+ /* Count remaining contiguous bits, if any */
+ if (!(*lpOut & 1))
+ {
+ ULONG ulOffset = 0;
+
+ for (;ulOffset < 7u; ulOffset++)
+ {
+ if (*lpOut & (1 << ulOffset))
+ break;
+ ulCount++;
+ }
+ }
+ *lpSize = ulCount;
+ return ulFoundAt;
+}
+
+/* FUNCTIONS ****************************************************************/
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
+RtlInitializeBitMap(IN PRTL_BITMAP BitMapHeader,
+ IN PULONG BitMapBuffer,
+ IN ULONG SizeOfBitMap)
+{
+ /* Setup the bitmap header */
+ BitMapHeader->SizeOfBitMap = SizeOfBitMap;
+ BitMapHeader->Buffer = BitMapBuffer;
+}
+
+/*
+ * @implemented
+ */
+BOOLEAN
+NTAPI
+RtlAreBitsClear(IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG Length)
+{
+ LPBYTE lpOut;
+ ULONG ulRemainder;
+
+ if (!BitMapHeader || !Length ||
+ StartingIndex >= BitMapHeader->SizeOfBitMap ||
+ Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+ return FALSE;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
+
+ /* Check bits in first byte, if StartingIndex isn't a byte boundary */
+ if (StartingIndex & 7)
+ {
+ if (Length > 7)
+ {
+ /* Check from start bit to the end of the byte */
+ if (*lpOut & ((0xff << (StartingIndex & 7)) & 0xff))
+ return FALSE;
+ lpOut++;
+ Length -= (8 - (StartingIndex & 7));
+ }
+ else
+ {
+ /* Check from the start bit, possibly into the next byte also */
+ USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
+
+ if (*lpOut & (initialWord & 0xff))
+ return FALSE;
+ if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
+ return FALSE;
+ return TRUE;
+ }
+ }
+
+ /* Check bits in blocks of 8 bytes */
+ ulRemainder = Length & 7;
+ Length >>= 3;
+ while (Length--)
+ {
+ if (*lpOut++)
+ return FALSE;
+ }
+
+ /* Check remaining bits, if any */
+ if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
+ return FALSE;
+ return TRUE;
+}
+
+
+/*
+ * @implemented
+ */
+BOOLEAN NTAPI
+RtlAreBitsSet(PRTL_BITMAP BitMapHeader,
+ ULONG StartingIndex,
+ ULONG Length)
+{
+ LPBYTE lpOut;
+ ULONG ulRemainder;
+
+
+ if (!BitMapHeader || !Length ||
+ StartingIndex >= BitMapHeader->SizeOfBitMap ||
+ Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+ return FALSE;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
+
+ /* Check bits in first byte, if StartingIndex isn't a byte boundary */
+ if (StartingIndex & 7)
+ {
+ if (Length > 7)
+ {
+ /* Check from start bit to the end of the byte */
+ if ((*lpOut &
+ ((0xff << (StartingIndex & 7))) & 0xff) != ((0xff << (StartingIndex & 7) & 0xff)))
+ return FALSE;
+ lpOut++;
+ Length -= (8 - (StartingIndex & 7));
+ }
+ else
+ {
+ /* Check from the start bit, possibly into the next byte also */
+ USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
+
+ if ((*lpOut & (initialWord & 0xff)) != (initialWord & 0xff))
+ return FALSE;
+ if ((initialWord & 0xff00) &&
+ ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
+ return FALSE;
+ return TRUE;
+ }
+ }
+
+ /* Check bits in blocks of 8 bytes */
+ ulRemainder = Length & 7;
+ Length >>= 3;
+ while (Length--)
+ {
+ if (*lpOut++ != 0xff)
+ return FALSE;
+ }
+
+ /* Check remaining bits, if any */
+ if (ulRemainder &&
+ (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
+ return FALSE;
+ return TRUE;
+}
+
+
+/*
+ * @implemented
+ */
+VOID NTAPI
+RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
+{
+ memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
+}
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
+RtlClearBit(PRTL_BITMAP BitMapHeader,
+ ULONG BitNumber)
+{
+ PULONG Ptr;
+
+ if (BitNumber >= BitMapHeader->SizeOfBitMap) return;
+
+ Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
+ *Ptr &= ~(1 << (BitNumber % 32));
+}
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
+RtlClearBits(IN PRTL_BITMAP BitMapHeader,
+ IN ULONG StartingIndex,
+ IN ULONG NumberToClear)
+{
+ LPBYTE lpOut;
+
+ if (!BitMapHeader || !NumberToClear ||
+ StartingIndex >= BitMapHeader->SizeOfBitMap ||
+ NumberToClear > BitMapHeader->SizeOfBitMap - StartingIndex)
+ return;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
+
+ /* Clear bits in first byte, if StartingIndex isn't a byte boundary */
+ if (StartingIndex & 7)
+ {
+ if (NumberToClear > 7)
+ {
+ /* Clear from start bit to the end of the byte */
+ *lpOut++ &= ~(0xff << (StartingIndex & 7));
+ NumberToClear -= (8 - (StartingIndex & 7));
+ }
+ else
+ {
+ /* Clear from the start bit, possibly into the next byte also */
+ USHORT initialWord = ~(NTDLL_maskBits[NumberToClear] << (StartingIndex & 7));
+
+ *lpOut++ &= (initialWord & 0xff);
+ *lpOut &= (initialWord >> 8);
+ return;
+ }
+ }
+
+ /* Clear bits (in blocks of 8) on whole byte boundaries */
+ if (NumberToClear >> 3)
+ {
+ memset(lpOut, 0, NumberToClear >> 3);
+ lpOut = lpOut + (NumberToClear >> 3);
+ }
+
+ /* Clear remaining bits, if any */
+ if (NumberToClear & 0x7)
+ *lpOut &= ~NTDLL_maskBits[NumberToClear & 0x7];
+}
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindClearBits(PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
+{
+ ULONG ulPos, ulEnd;
+
+ if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
+ return ~0U;
+
+ ulEnd = BitMapHeader->SizeOfBitMap;
+
+ if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
+ HintIndex = 0;
+
+ ulPos = HintIndex;
+
+ while (ulPos < ulEnd)
+ {
+ /* FIXME: This could be made a _lot_ more efficient */
+ if (RtlAreBitsClear(BitMapHeader, ulPos, NumberToFind))
+ return ulPos;
+
+ /* Start from the beginning if we hit the end and started from HintIndex */
+ if (ulPos == ulEnd - 1 && HintIndex)
+ {
+ ulEnd = HintIndex;
+ ulPos = HintIndex = 0;
+ }
+ else
+ ulPos++;
+ }
+ return ~0U;
+}
+
+
+
+
+
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindClearRuns(PRTL_BITMAP BitMapHeader,
+ PRTL_BITMAP_RUN RunArray,
+ ULONG SizeOfRunArray,
+ BOOLEAN LocateLongestRuns)
+{
+ return NTDLL_FindRuns(BitMapHeader, RunArray, SizeOfRunArray, LocateLongestRuns, NTDLL_FindClearRun);
+}
+
+
+/*
+ * @unimplemented
+ */
+ULONG NTAPI
+RtlFindLastBackwardRunClear(IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ UNIMPLEMENTED;
+ return 0;
+}
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
+ IN ULONG FromIndex,
+ IN PULONG StartingRunIndex)
+{
+ ULONG ulSize = 0;
+
+ if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap && StartingRunIndex)
+ *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize);
+
+ return ulSize;
+}
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindFirstRunSet(IN PRTL_BITMAP BitMapHeader,
+ IN PULONG StartingIndex)
+{
+ ULONG Size;
+ ULONG Index;
+ ULONG Count;
+ PULONG Ptr;
+ ULONG Mask;
+
+ Size = BitMapHeader->SizeOfBitMap;
+ if (*StartingIndex > Size)
+ {
+ *StartingIndex = (ULONG)-1;
+ return 0;
+ }
+
+ Index = *StartingIndex;
+ Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
+ Mask = 1 << (Index & 0x1F);
+
+ /* Skip clear bits */
+ for (; Index < Size && ~*Ptr & Mask; Index++)
+ {
+ Mask <<= 1;
+
+ if (Mask == 0)
+ {
+ Mask = 1;
+ Ptr++;
+ }
+ }
+
+ /* Return index of first set bit */
+ if (Index >= Size)
+ {
+ *StartingIndex = (ULONG)-1;
+ return 0;
+ }
+ else
+ {
+ *StartingIndex = Index;
+ }
+
+ /* Count set bits */
+ for (Count = 0; Index < Size && *Ptr & Mask; Index++)
+ {
+ Count++;
+ Mask <<= 1;
+
+ if (Mask == 0)
+ {
+ Mask = 1;
+ Ptr++;
+ }
+ }
+
+ return Count;
+}
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
+ PULONG StartingIndex)
+{
+ RTL_BITMAP_RUN br;
+
+ if (RtlFindClearRuns(BitMapHeader, &br, 1, TRUE) == 1)
+ {
+ if (StartingIndex)
+ *StartingIndex = br.StartingIndex;
+ return br.NumberOfBits;
+ }
+ return 0;
+}
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
+ PULONG StartingIndex)
+{
+ RTL_BITMAP_RUN br;
+
+ if (NTDLL_FindRuns(BitMapHeader, &br, 1, TRUE, NTDLL_FindSetRun) == 1)
+ {
+ if (StartingIndex)
+ *StartingIndex = br.StartingIndex;
+ return br.NumberOfBits;
+ }
+ return 0;
+}
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindSetBits(PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
+{
+ ULONG ulPos, ulEnd;
+
+ if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
+ return ~0U;
+
+ ulEnd = BitMapHeader->SizeOfBitMap;
+
+ if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
+ HintIndex = 0;
+
+ ulPos = HintIndex;
+
+ while (ulPos < ulEnd)
+ {
+ /* FIXME: This could be made a _lot_ more efficient */
+ if (RtlAreBitsSet(BitMapHeader, ulPos, NumberToFind))
+ return ulPos;
+
+ /* Start from the beginning if we hit the end and had a hint */
+ if (ulPos == ulEnd - 1 && HintIndex)
+ {
+ ulEnd = HintIndex;
+ ulPos = HintIndex = 0;
+ }
+ else
+ ulPos++;
+ }
+ return ~0U;
+}
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
+{
+ ULONG ulPos;
+
+ ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
+ if (ulPos != ~0U)
+ RtlClearBits(BitMapHeader, ulPos, NumberToFind);
+ return ulPos;
+}
+
+
+
+
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
+{
+ ULONG ulSet = 0;
+
+ if (BitMapHeader)
+ {
+ LPBYTE lpOut = (BYTE *)BitMapHeader->Buffer;
+ ULONG Length, ulRemainder;
+ BYTE bMasked;
+
+ Length = BitMapHeader->SizeOfBitMap >> 3;
+ ulRemainder = BitMapHeader->SizeOfBitMap & 0x7;
+
+ while (Length--)
+ {
+ ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
+ ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
+ lpOut++;
+ }
+
+ bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
+ ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
+ ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
+ }
+ return ulSet;
+}
+
+
+/*
+ * @implemented
+ */
+VOID NTAPI
+RtlSetAllBits(IN OUT PRTL_BITMAP BitMapHeader)
+{
+ memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
+}
+
+
+/*
+ * @implemented
+ */
+VOID NTAPI
+RtlSetBit(PRTL_BITMAP BitMapHeader,
+ ULONG BitNumber)
+{
+ PULONG Ptr;
+
+ if (BitNumber >= BitMapHeader->SizeOfBitMap)
+ return;
+
+ Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
+
+ *Ptr |= (1 << (BitNumber % 32));
+}
+
+
+/*
+ * @implemented
+ */
+VOID NTAPI
+RtlSetBits(PRTL_BITMAP BitMapHeader,
+ ULONG StartingIndex,
+ ULONG NumberToSet)
+{
+ LPBYTE lpOut;
+
+ if (!BitMapHeader || !NumberToSet ||
+ StartingIndex >= BitMapHeader->SizeOfBitMap ||
+ NumberToSet > BitMapHeader->SizeOfBitMap - StartingIndex)
+ return;
+
+ /* FIXME: It might be more efficient/cleaner to manipulate four bytes
+ * at a time. But beware of the pointer arithmetics...
+ */
+ lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
+
+ /* Set bits in first byte, if StartingIndex isn't a byte boundary */
+ if (StartingIndex & 7)
+ {
+ if (NumberToSet > 7)
+ {
+ /* Set from start bit to the end of the byte */
+ *lpOut++ |= 0xff << (StartingIndex & 7);
+ NumberToSet -= (8 - (StartingIndex & 7));
+ }
+ else
+ {
+ /* Set from the start bit, possibly into the next byte also */
+ USHORT initialWord = NTDLL_maskBits[NumberToSet] << (StartingIndex & 7);
+
+ *lpOut++ |= (initialWord & 0xff);
+ *lpOut |= (initialWord >> 8);
+ return;
+ }
+ }
+
+ /* Set bits up to complete byte count */
+ if (NumberToSet >> 3)
+ {
+ memset(lpOut, 0xff, NumberToSet >> 3);
+ lpOut = lpOut + (NumberToSet >> 3);
+ }
+
+ /* Set remaining bits, if any */
+ *lpOut |= NTDLL_maskBits[NumberToSet & 0x7];
+}
+
+
+/*
+ * @implemented
+ */
+BOOLEAN NTAPI
+RtlTestBit(PRTL_BITMAP BitMapHeader,
+ ULONG BitNumber)
+{
+ PULONG Ptr;
+
+ if (BitNumber >= BitMapHeader->SizeOfBitMap)
+ return FALSE;
+
+ Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
+
+ return (*Ptr & (1 << (BitNumber % 32)));
+}
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
+ PULONG StartingIndex)
+{
+ return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
+}
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
+{
+
+ if (BitMapHeader)
+ return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
+ return 0;
+}
+
+/*
+ * @implemented
+ */
+ULONG NTAPI
+RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
+ ULONG NumberToFind,
+ ULONG HintIndex)
+{
+ ULONG ulPos;
+
+ ulPos = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
+ if (ulPos != ~0U)
+ RtlSetBits(BitMapHeader, ulPos, NumberToFind);
+ return ulPos;
+}
+
+/*
+ * @implemented
+ */
+CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
+{
+ signed char ret = 32;
+ DWORD dw;
+
+ if (!(dw = (ulLong >> 32)))
+ {
+ ret = 0;
+ dw = (DWORD)ulLong;
+ }
+ if (dw & 0xffff0000)
+ {
+ dw >>= 16;
+ ret += 16;
+ }
+ if (dw & 0xff00)
+ {
+ dw >>= 8;
+ ret += 8;
+ }
+ if (dw & 0xf0)
+ {
+ dw >>= 4;
+ ret += 4;
+ }
+ return ret + NTDLL_mostSignificant[dw];
+}
+
+/*
+ * @implemented
+ */
+CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
+{
+ signed char ret = 0;
+ DWORD dw;
+
+ if (!(dw = (DWORD)ulLong))
+ {
+ ret = 32;
+ if (!(dw = ulLong >> 32)) return -1;
+ }
+ if (!(dw & 0xffff))
+ {
+ dw >>= 16;
+ ret += 16;
+ }
+ if (!(dw & 0xff))
+ {
+ dw >>= 8;
+ ret += 8;
+ }
+ if (!(dw & 0x0f))
+ {
+ dw >>= 4;
+ ret += 4;
+ }
+ return ret + NTDLL_leastSignificant[dw & 0x0f];
+}
+
+/* EOF */
More information about the Ros-diffs
mailing list