[arty] 24265: Add missing file from the branch. Preparing to move build hosts.

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.…
==============================================================================
--- 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 */