[ion] 22679: - Sync RtlBitmap* implementation with WINE: Fixes 278 regression failures (for a total of 0 now). - Also adds implementations for RtlFindMostSignificantBit , RtlFindLeastSignificantBit, RtlFindNextForwardRunClear, RtlFindClearRuns. - The RtlBitmap* package is essential for compatibility with NTFS.SYS and other File System Drivers, but these fixes should not really improve user-mode app. compat.

Author: ion
Date: Thu Jun 29 00:51:51 2006
New Revision: 22679

URL: http://svn.reactos.org/svn/reactos?rev=22679&view=rev
Log:
- Sync RtlBitmap* implementation with WINE: Fixes 278 regression failures (for a total of
0 now).
- Also adds implementations for RtlFindMostSignificantBit , RtlFindLeastSignificantBit,
RtlFindNextForwardRunClear, RtlFindClearRuns.
- The RtlBitmap* package is essential for compatibility with NTFS.SYS and other File
System Drivers, but these fixes should not really improve user-mode app. compat.

Modified:
    trunk/reactos/lib/rtl/bitmap.c

Modified: trunk/reactos/lib/rtl/bitmap.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/bitmap.c?rev=22679…
==============================================================================
--- trunk/reactos/lib/rtl/bitmap.c (original)
+++ trunk/reactos/lib/rtl/bitmap.c Thu Jun 29 00:51:51 2006
@@ -12,64 +12,347 @@
 #define NDEBUG
 #include <debug.h>
 
-
 /* MACROS *******************************************************************/
 
-#define MASK(Count, Shift) \
-  ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift))
-
+/* 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(PRTL_BITMAP BitMapHeader,
-		    PULONG BitMapBuffer,
-		    ULONG SizeOfBitMap)
-{
-  BitMapHeader->SizeOfBitMap = SizeOfBitMap;
-  BitMapHeader->Buffer = BitMapBuffer;
-}
-
-
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlAreBitsClear(PRTL_BITMAP BitMapHeader,
-		ULONG StartingIndex,
-		ULONG Length)
-{
-  ULONG Size;
-  ULONG Shift;
-  ULONG Count;
-  PULONG Ptr;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (StartingIndex >= Size ||
-      !Length ||
-      (StartingIndex + Length > Size))
-     return FALSE;
-
-  Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
-  while (Length)
-  {
-    /* Get bit shift in current ulong */
-    Shift = StartingIndex & 0x1F;
-
-    /* Get number of bits to check in current ulong */
-    Count = (Length > 32 - Shift) ? 32 - Shift : Length;
-
-    /* Check ulong */
-    if (*Ptr++ & MASK(Count, Shift))
+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;
-
-    Length -= Count;
-    StartingIndex += Count;
-  }
-
+  }
+
+  /* Check remaining bits, if any */
+  if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
+    return FALSE;
   return TRUE;
 }
 
@@ -82,107 +365,139 @@
 	      ULONG StartingIndex,
 	      ULONG Length)
 {
-  ULONG Size;
-  ULONG Shift;
-  ULONG Count;
-  PULONG Ptr;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (StartingIndex >= Size ||
-      Length == 0 ||
-      (StartingIndex + Length > Size))
+  LPBYTE lpOut;
+  ULONG ulRemainder;
+
+
+  if (!BitMapHeader || !Length ||
+      StartingIndex >= BitMapHeader->SizeOfBitMap ||
+      Length > BitMapHeader->SizeOfBitMap - StartingIndex)
     return FALSE;
 
-  Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
-  while (Length)
-  {
-    /* Get bit shift in current ulong */
-    Shift = StartingIndex & 0x1F;
-
-    /* Get number of bits to check in current ulong */
-    Count = (Length > 32 - Shift) ? 32 - Shift : Length;
-
-    /* Check ulong */
-    if (~*Ptr++ & MASK(Count, Shift))
+  /* 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;
-
-    Length -= Count;
-    StartingIndex += Count;
-  }
-
+  }
+
+  /* Check remaining bits, if any */
+  if (ulRemainder &&
+      (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
+    return FALSE;
   return TRUE;
 }
 
 
 /*
  * @implemented
- *
- * Note: According to the documentation, SizeOfBitmap is in bits, so the
- * ROUND_UP(...) must be divided by the number of bits per byte here.
- * This function is exercised by the whole page allocator in npool.c
- * which is how i came across this error.
  */
 VOID NTAPI
 RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
 {
-     memset(BitMapHeader->Buffer,
-	         0x00,
-	         ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8);
- 
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
+    memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31)
>> 3);
+}
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
 RtlClearBit(PRTL_BITMAP BitMapHeader,
-	    ULONG BitNumber)
-{
-  PULONG Ptr;
-
-  if (BitNumber >= BitMapHeader->SizeOfBitMap)
+            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;
 
-  Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
-
-  *Ptr &= ~(1 << (BitNumber % 32));
-}
-
-
-/*
- * @implemented
- */
-VOID NTAPI
-RtlClearBits(PRTL_BITMAP BitMapHeader,
-	     ULONG StartingIndex,
-	     ULONG NumberToClear)
-{
-  ULONG Size;
-  ULONG Count;
-  ULONG Shift;
-  PULONG Ptr;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (StartingIndex >= Size || NumberToClear == 0)
-    return;
-
-  ASSERT(StartingIndex + NumberToClear <= Size);
-
-  Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
-  while (NumberToClear)
-  {
-    /* Bit shift in current ulong */
-    Shift = StartingIndex & 0x1F;
-
-    /* Number of bits to change in current ulong */
-    Count = (NumberToClear > 32 - Shift ) ? 32 - Shift : NumberToClear;
-
-    /* Adjust ulong */
-    *Ptr++ &= ~MASK(Count, Shift);
-    NumberToClear -= Count;
-    StartingIndex += Count;
-  }
+  /* 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];
 }
 
 
@@ -194,171 +509,44 @@
 		 ULONG NumberToFind,
 		 ULONG HintIndex)
 {
-  ULONG Size;
-  ULONG Index;
-  ULONG Count;
-  PULONG Ptr;
-  ULONG Mask;
-  ULONG Loop;
-  ULONG End;
-  ULONG OriginalHint = HintIndex;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (NumberToFind > Size || NumberToFind == 0)
-    return -1;
-
-  if (HintIndex >= Size)
+  ULONG ulPos, ulEnd;
+
+  if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
+    return ~0U;
+
+  ulEnd = BitMapHeader->SizeOfBitMap;
+
+  if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
     HintIndex = 0;
 
-  /* Initialize the values to the hint location. */
-  Index = HintIndex;
-  Ptr = BitMapHeader->Buffer + (Index / 32);
-  Mask = 1 << (Index & 0x1F);
-  End = Size;
-
-  /* The outer loop does the magic of first searching from the
-   * hint to the bitmap end and then going again from beginning
-   * of the bitmap to the hint location.
-   */
-  for (Loop = 0; Loop < 2; Loop++)
-  {
-    while (HintIndex < End)
-    {
-      /* Count clear bits */
-      for (Count = 0; Index < End && ~*Ptr & Mask; Index++)
-      {
-        if (++Count >= NumberToFind)
-          return HintIndex;
-
-        Mask <<= 1;
-
-        if (Mask == 0)
-        {
-          Mask = 1;
-          Ptr++;
-        }
-      }
-
-      /* Skip set bits */
-      for (; Index < End && *Ptr & Mask; Index++)
-      {
-        Mask <<= 1;
-
-        if (Mask == 0)
-        {
-          Mask = 1;
-          Ptr++;
-        }
-      }
-      HintIndex = Index;
-    }
-
-    /* Optimalization */
-    if (OriginalHint == 0)
-      break;
-
-    /* Initialize the values for the beginning -> hint loop. */
-    HintIndex = Index = 0;
-    End = OriginalHint + NumberToFind - 1;
-    End = End > Size ? Size : End;
-    Ptr = BitMapHeader->Buffer;
-    Mask = 1;
-  }
-
-  return (ULONG)-1;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
-		       ULONG NumberToFind,
-		       ULONG HintIndex)
-{
-  ULONG Index;
-
-  Index = RtlFindClearBits(BitMapHeader,
-			   NumberToFind,
-			   HintIndex);
-  if (Index != (ULONG)-1)
-  {
-    RtlSetBits(BitMapHeader,
-	       Index,
-	       NumberToFind);
-  }
-
-  return Index;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
-		     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 set bits */
-  for (; Index < Size && *Ptr & Mask; Index++)
-  {
-    Mask <<= 1;
-
-    if (Mask == 0)
-    {
-      Mask = 1;
-      Ptr++;
-    }
-  }
-
-  /* Return index of first clear bit */
-  if (Index >= Size)
-  {
-    *StartingIndex = (ULONG)-1;
-    return 0;
-  }
-  else
-  {
-    *StartingIndex = Index;
-  }
-
-  /* Count clear bits */
-  for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
-  {
-    Count++;
-    Mask <<= 1;
-
-    if (Mask == 0)
-    {
-      Mask = 1;
-      Ptr++;
-    }
-  }
-
-  return Count;
-}
-
-
-/*
- * @unimplemented
+  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,
@@ -366,8 +554,7 @@
 		 ULONG SizeOfRunArray,
 		 BOOLEAN LocateLongestRuns)
 {
-  UNIMPLEMENTED;
-  return 0;
+    return NTDLL_FindRuns(BitMapHeader, RunArray, SizeOfRunArray, LocateLongestRuns,
NTDLL_FindClearRun);
 }
 
 
@@ -383,19 +570,21 @@
   return 0;
 }
 
-
-/*
- * @unimplemented
+/*
+ * @implemented
  */
 ULONG NTAPI
 RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
 			   IN ULONG FromIndex,
 			   IN PULONG StartingRunIndex)
 {
-  UNIMPLEMENTED;
-  return 0;
-}
-
+  ULONG ulSize = 0;
+
+  if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap &&
StartingRunIndex)
+    *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize);
+
+  return ulSize;
+}
 
 /*
  * @implemented
@@ -468,60 +657,15 @@
 RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
 		       PULONG StartingIndex)
 {
-  ULONG Size;
-  PULONG Ptr;
-  ULONG Index = 0;
-  ULONG Count;
-  ULONG Max = 0;
-  ULONG Start;
-  ULONG Maxstart = 0;
-  ULONG  Mask = 1;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  Ptr = (PULONG)BitMapHeader->Buffer;
-
-  while (Index < Size)
-  {
-    Start = Index;
-
-    /* Count clear bits */
-    for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
-    {
-      Count++;
-      Mask <<= 1;
-
-      if (Mask == 0)
-      {
-	Mask = 1;
-	Ptr++;
-      }
-    }
-
-    /* Skip set bits */
-    for (; Index < Size && *Ptr & Mask; Index++)
-    {
-      Mask <<= 1;
-
-      if (Mask == 0)
-      {
-	Mask = 1;
-	Ptr++;
-      }
-    }
-
-    if (Count > Max)
-    {
-      Max = Count;
-      Maxstart = Start;
-    }
-  }
-
-  if (StartingIndex != NULL)
-  {
-    *StartingIndex = Maxstart;
-  }
-
-  return Max;
+  RTL_BITMAP_RUN br;
+
+  if (RtlFindClearRuns(BitMapHeader, &br, 1, TRUE) == 1)
+  {
+    if (StartingIndex)
+      *StartingIndex = br.StartingIndex;
+    return br.NumberOfBits;
+  }
+  return 0;
 }
 
 
@@ -532,60 +676,15 @@
 RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
 		     PULONG StartingIndex)
 {
-  ULONG Size;
-  PULONG Ptr;
-  ULONG Index = 0;
-  ULONG Count;
-  ULONG Max = 0;
-  ULONG Start;
-  ULONG Maxstart = 0;
-  ULONG Mask = 1;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  Ptr = (PULONG)BitMapHeader->Buffer;
-
-  while (Index < Size)
-  {
-    Start = Index;
-
-    /* Count set bits */
-    for (Count = 0; Index < Size && *Ptr & Mask; Index++)
-    {
-      Count++;
-      Mask <<= 1;
-
-      if (Mask == 0)
-      {
-	Mask = 1;
-	Ptr++;
-      }
-    }
-
-    /* Skip clear bits */
-    for (; Index < Size && ~*Ptr & Mask; Index++)
-    {
-      Mask <<= 1;
-
-      if (Mask == 0)
-      {
-	Mask = 1;
-	Ptr++;
-      }
-    }
-
-    if (Count > Max)
-    {
-      Max = Count;
-      Maxstart = Start;
-    }
-  }
-
-  if (StartingIndex != NULL)
-  {
-    *StartingIndex = Maxstart;
-  }
-
-  return Max;
+  RTL_BITMAP_RUN br;
+
+  if (NTDLL_FindRuns(BitMapHeader, &br, 1, TRUE, NTDLL_FindSetRun) == 1)
+  {
+    if (StartingIndex)
+      *StartingIndex = br.StartingIndex;
+    return br.NumberOfBits;
+  }
+  return 0;
 }
 
 
@@ -597,79 +696,34 @@
 	       ULONG NumberToFind,
 	       ULONG HintIndex)
 {
-  ULONG Size;
-  ULONG Index;
-  ULONG Count;
-  PULONG Ptr;
-  ULONG Mask;
-  ULONG Loop;
-  ULONG End;
-  ULONG OriginalHint = HintIndex;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (NumberToFind > Size || NumberToFind == 0)
-    return (ULONG)-1;
-
-  if (HintIndex >= Size)
+  ULONG ulPos, ulEnd;
+
+  if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
+    return ~0U;
+
+  ulEnd = BitMapHeader->SizeOfBitMap;
+
+  if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
     HintIndex = 0;
 
-  /* Initialize the values to the hint location. */
-  Index = HintIndex;
-  Ptr = BitMapHeader->Buffer + (Index / 32);
-  Mask = 1 << (Index & 0x1F);
-  End = Size;
-
-  /* The outer loop does the magic of first searching from the
-   * hint to the bitmap end and then going again from beginning
-   * of the bitmap to the hint location.
-   */
-  for (Loop = 0; Loop < 2; Loop++)
-  {
-    while (HintIndex < End)
-    {
-      /* Count set bits */
-      for (Count = 0; Index < End && *Ptr & Mask; Index++)
-      {
-        if (++Count >= NumberToFind)
-          return HintIndex;
-
-        Mask <<= 1;
-
-        if (Mask == 0)
-        {
-          Mask = 1;
-          Ptr++;
-        }
-      }
-
-      /* Skip clear bits */
-      for (; Index < End && ~*Ptr & Mask; Index++)
-      {
-        Mask <<= 1;
-
-        if (Mask == 0)
-        {
-          Mask = 1;
-          Ptr++;
-        }
-      }
-
-      HintIndex = Index;
-    }
-
-    /* Optimalization */
-    if (OriginalHint == 0)
-      break;
-
-    /* Initialize the values for the beginning -> hint loop. */
-    HintIndex = Index = 0;
-    End = OriginalHint + NumberToFind - 1;
-    End = End > Size ? Size : End;
-    Ptr = BitMapHeader->Buffer;
-    Mask = 1;
-  }
-
-  return (ULONG)-1;
+  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;
 }
 
 
@@ -681,52 +735,16 @@
 		       ULONG NumberToFind,
 		       ULONG HintIndex)
 {
-  ULONG Index;
-
-  Index = RtlFindSetBits(BitMapHeader,
-			 NumberToFind,
-			 HintIndex);
-  if (Index != (ULONG)-1)
-  {
-    RtlClearBits(BitMapHeader,
-		 Index,
-		 NumberToFind);
-  }
-
-  return Index;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
-{
-  PULONG Ptr;
-  ULONG Size;
-  ULONG Index;
-  ULONG Count;
-  ULONG Mask;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  Ptr = (PULONG)BitMapHeader->Buffer;
-
-  for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
-  {
-    if (~*Ptr & Mask)
-      Count++;
-
-    Mask <<= 1;
-    if (Mask == 0)
-    {
-      Mask = 1;
-      Ptr++;
-    }
-  }
-
-  return Count;
-}
+  ULONG ulPos;
+
+  ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
+  if (ulPos != ~0U)
+    RtlClearBits(BitMapHeader, ulPos, NumberToFind);
+  return ulPos;
+}
+
+
+
 
 
 /*
@@ -735,46 +753,39 @@
 ULONG NTAPI
 RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
 {
-  PULONG Ptr;
-  ULONG Size;
-  ULONG Index;
-  ULONG Count;
-  ULONG Mask;
-
-  Ptr = (PULONG)BitMapHeader->Buffer;
-  Size = BitMapHeader->SizeOfBitMap;
-  for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
-  {
-    if (*Ptr & Mask)
-      Count++;
-
-    Mask <<= 1;
-
-    if (Mask == 0)
-    {
-      Mask = 1;
-      Ptr++;
-    }
-  }
-
-  return Count;
-}
-
-
-/*
- * @implemented
- *
- * Note: According to the documentation, SizeOfBitmap is in bits, so the
- * ROUND_UP(...) must be divided by the number of bits per byte here.
- * The companion function, RtlClearAllBits, is exercised by the whole page
- * allocator in npool.c which is how i came across this error.
+  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,
-	 ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8);
+  memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31)
>> 3);
 }
 
 
@@ -804,31 +815,47 @@
 	   ULONG StartingIndex,
 	   ULONG NumberToSet)
 {
-  ULONG Size;
-  ULONG Count;
-  ULONG Shift;
-  PULONG Ptr;
-
-  Size = BitMapHeader->SizeOfBitMap;
-  if (StartingIndex >= Size || NumberToSet == 0)
+  LPBYTE lpOut;
+
+  if (!BitMapHeader || !NumberToSet ||
+      StartingIndex >= BitMapHeader->SizeOfBitMap ||
+      NumberToSet > BitMapHeader->SizeOfBitMap - StartingIndex)
     return;
 
-  ASSERT(StartingIndex + NumberToSet <= Size);
-
-  Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
-  while (NumberToSet)
-  {
-    /* Bit shift in current ulong */
-    Shift = StartingIndex & 0x1F;
-
-    /* Number of bits to change in current ulong */
-    Count = (NumberToSet > 32 - Shift) ? 32 - Shift : NumberToSet;
-
-    /* Adjust ulong */
-    *Ptr++ |= MASK(Count, Shift);
-    NumberToSet -= Count;
-    StartingIndex += Count;
-  }
+  /* 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];
 }
 
 
@@ -849,4 +876,104 @@
   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 */