[ros-diffs] [tkreuzer] 44464: [RTL] Rewrite the rtl bitmap implementation. The old one was a little .... suboptimal. The new one should outperform the old one by several orders of magnitude, especially RtlFindClearBits that was literally searching bit by bit.

Author: tkreuzer
Date: Tue Dec  8 02:02:36 2009
New Revision: 44464

URL: http://svn.reactos.org/svn/reactos?rev=44464&view=rev
Log:
[RTL]
Rewrite the rtl bitmap implementation.
The old one was a little .... suboptimal. The new one should outperform the old one by
several orders of magnitude, especially RtlFindClearBits that was literally searching bit
by bit.

Modified:
    trunk/reactos/lib/rtl/bitmap.c
    trunk/reactos/tools/mkhive/mkhive.h
    trunk/reactos/tools/mkhive/rtl.c

Modified: trunk/reactos/lib/rtl/bitmap.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/bitmap.c?rev=44464…
==============================================================================
--- trunk/reactos/lib/rtl/bitmap.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/bitmap.c [iso-8859-1] Tue Dec  8 02:02:36 2009
@@ -1,8 +1,9 @@
-/* COPYRIGHT:       See COPYING in the top level directory
+/*
+ * COPYRIGHT:       See COPYING in the top level directory
  * PROJECT:         ReactOS system libraries
  * FILE:            lib/rtl/bitmap.c
  * PURPOSE:         Bitmap functions
- * PROGRAMMER:      Eric Kohl
+ * PROGRAMMER:      Timo Kreuzer (timo.kreuzer(a)reactos.org)
  */
 
 /* INCLUDES *****************************************************************/
@@ -12,965 +13,749 @@
 #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
+
+/* DATA *********************************************************************/
+
+/* Number of set bits per byte value */
+static const
+UCHAR
+BitCountTable[256] =
+{
+    /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
+       0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
+       4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8  /* Fx */
 };
 
-/* 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
-__cdecl
-NTDLL_RunSortFn(const void *lhs,
-                const void *rhs)
-{
-  if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const
RTL_BITMAP_RUN*)rhs)->NumberOfBits)
+
+/* PRIVATE FUNCTIONS ********************************************************/
+
+static __inline__
+ULONG
+RtlpGetLengthOfRunClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG MaxLength)
+{
+    ULONG Value, BitPos, Length;
+    PULONG Buffer, MaxBuffer;
+
+    /* Calculate positions */
+    Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+    BitPos = StartingIndex & 31;
+
+    /* Calculate the maximum length */
+    MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+    MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+
+    /* Clear the bits that don't belong to this run */
+    Value = *Buffer++ >> BitPos << BitPos;
+
+    /* Skip all clear ULONGs */
+    while (Value == 0 && Buffer < MaxBuffer)
+    {
+        Value = *Buffer++;
+    }
+
+    /* Did we reach the end? */
+    if (Value == 0)
+    {
+        /* Return maximum length */
+        return MaxLength;
+    }
+
+    /* We hit a set bit, check how many clear bits are left */
+    BitScanForward(&BitPos, Value);
+
+    /* Calculate length up to where we read */
+    Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
+    Length += BitPos - 32;
+    
+    if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+        Length = BitMapHeader->SizeOfBitMap - StartingIndex;
+
+    /* The result is guaranteed to be < BitMapHeader->SizeOfBitMap */
+    return Length;
+}
+
+static __inline__
+ULONG
+RtlpGetLengthOfRunSet(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG MaxLength)
+{
+    ULONG InvValue, BitPos, Length;
+    PULONG Buffer, MaxBuffer;
+
+    /* Calculate positions */
+    Buffer = BitMapHeader->Buffer + StartingIndex / 32;
+    BitPos = StartingIndex & 31;
+
+    /* Calculate the maximum length */
+    MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
+    MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
+
+    /* Get the inversed value, clear bits that don't belong to the run */
+    InvValue = ~(*Buffer++) >> BitPos << BitPos;
+
+    /* Skip all set ULONGs */
+    while (InvValue == 0 && Buffer < MaxBuffer)
+    {
+        InvValue = ~(*Buffer++);
+    }
+
+    /* Did we reach the end? */
+    if (InvValue == 0)
+    {
+        /* Yes, return maximum */
+        return MaxLength;
+    }
+
+    /* We hit a clear bit, check how many set bits are left */
+    BitScanForward(&BitPos, InvValue);
+
+    /* Calculate length up to where we read */
+    Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
+    Length += BitPos - 32;
+
+    if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
+        Length = BitMapHeader->SizeOfBitMap - StartingIndex;
+
+    /* The result is guaranteed to be < BitMapHeader->SizeOfBitMap */
+    return Length;
+}
+
+
+/* PUBLIC FUNCTIONS **********************************************************/
+
+CCHAR
+NTAPI
+RtlFindMostSignificantBit(ULONGLONG Value)
+{
+    ULONG Position;
+
+    if (BitScanReverse(&Position, Value >> 32))
+    {
+        return Position + 32;
+    }
+    else if (BitScanReverse(&Position, (ULONG)Value))
+    {
+        return Position;
+    }
+
     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 MAXULONG;
-
-  while (ulPos < lpBits->SizeOfBitMap)
-  {
-    /* Find next set/clear run */
-    ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
-
-    if (ulNextPos == MAXULONG)
-      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 MAXULONG;
-  }
-
-  /* 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 MAXULONG;
-  }
-
-  /* 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
- */
+}
+
+CCHAR
+NTAPI
+RtlFindLeastSignificantBit(ULONGLONG Value)
+{
+    ULONG Position;
+
+    if (BitScanForward(&Position, (ULONG)Value))
+    {
+        return Position;
+    }
+    else if (BitScanForward(&Position, Value >> 32))
+    {
+        return Position + 32;
+    }
+
+    return -1;
+}
+
 VOID
 NTAPI
-RtlInitializeBitMap(IN PRTL_BITMAP BitMapHeader,
-                    IN PULONG BitMapBuffer,
-                    IN ULONG SizeOfBitMap)
-{
+RtlInitializeBitMap(
+    IN PRTL_BITMAP BitMapHeader,
+    IN PULONG BitMapBuffer,
+    IN ULONG SizeOfBitMap)
+{
+    // FIXME: some bugger here!
+    //ASSERT(SizeOfBitMap > 0);
+
     /* Setup the bitmap header */
     BitMapHeader->SizeOfBitMap = SizeOfBitMap;
     BitMapHeader->Buffer = BitMapBuffer;
 }
 
-/*
- * @implemented
- */
+VOID
+NTAPI
+RtlClearAllBits(
+    IN OUT PRTL_BITMAP BitMapHeader)
+{
+    ULONG LengthInUlongs;
+
+    LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+    RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
+}
+
+VOID
+NTAPI
+RtlSetAllBits(
+    IN OUT PRTL_BITMAP BitMapHeader)
+{
+    ULONG LengthInUlongs;
+    
+    LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
+    RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
+}
+
+VOID
+NTAPI
+RtlClearBit(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG BitNumber)
+{
+    ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+    BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber &
31));
+}
+
+VOID
+NTAPI
+RtlSetBit(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG BitNumber)
+{
+    ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
+    BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
+}
+
+VOID
+NTAPI
+RtlClearBits(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG NumberToClear)
+{
+    ULONG Bits, Mask;
+    PULONG Buffer;
+
+    ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
+
+    /* Calculate buffer start and first bit index */
+    Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+    Bits = StartingIndex & 31;
+
+    /* Are we unaligned? */
+    if (Bits)
+    {
+        /* Create an inverse mask by shifting MAXULONG */
+        Mask = MAXULONG << Bits;
+
+        /* This is what's left in the first ULONG */
+        Bits = 32 - Bits;
+
+        /* Even less bits to clear? */
+        if (NumberToClear < Bits)
+        {
+            /* Calculate how many bits are left */
+            Bits -= NumberToClear;
+
+            /* Fixup the mask on the high side */
+            Mask = Mask << Bits >> Bits;
+
+            /* Clear bits and return */
+            *Buffer &= ~Mask;
+            return;
+        }
+
+        /* Clear bits */
+        *Buffer &= ~Mask;
+
+        /* Update buffer and left bits */
+        Buffer++;
+        NumberToClear -= Bits;
+    }
+
+    /* Clear all full ULONGs */
+    RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
+    Buffer += NumberToClear >> 5;
+
+    /* Clear what's left */
+    NumberToClear &= 31;
+    Mask = MAXULONG << NumberToClear;
+    *Buffer &= Mask;
+}
+
+VOID
+NTAPI
+RtlSetBits(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG NumberToSet)
+{
+    ULONG Bits, Mask;
+    PULONG Buffer;
+
+    ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
+
+    /* Calculate buffer start and first bit index */
+    Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
+    Bits = StartingIndex & 31;
+
+    /* Are we unaligned? */
+    if (Bits)
+    {
+        /* Create a mask by shifting MAXULONG */
+        Mask = MAXULONG << Bits;
+
+        /* This is what's left in the first ULONG */
+        Bits = 32 - Bits;
+
+        /* Even less bits to clear? */
+        if (NumberToSet < Bits)
+        {
+            /* Calculate how many bits are left */
+            Bits -= NumberToSet;
+
+            /* Fixup the mask on the high side */
+            Mask = Mask << Bits >> Bits;
+
+            /* Set bits and return */
+            *Buffer |= Mask;
+            return;
+        }
+
+        /* Set bits */
+        *Buffer |= Mask;
+
+        /* Update buffer and left bits */
+        Buffer++;
+        NumberToSet -= Bits;
+    }
+
+    /* Set all full ULONGs */
+    RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
+    Buffer += NumberToSet >> 5;
+
+    /* Set what's left */
+    NumberToSet &= 31;
+    Mask = MAXULONG << NumberToSet;
+    *Buffer |= ~Mask;
+}
+
 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)
-{
-    PUCHAR Ptr;
-
-    if (BitNumber >= BitMapHeader->SizeOfBitMap) return;
-
-    Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
-    *Ptr &= ~(1 << (BitNumber % 8));
-}
-
-/*
- * @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)
+RtlTestBit(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG BitNumber)
+{
+    ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
+    return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31))
& 1;
+}
+
+BOOLEAN
+NTAPI
+RtlAreBitsClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG Length)
+{
+    return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
+}
+
+BOOLEAN
+NTAPI
+RtlAreBitsSet(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG StartingIndex,
+    IN ULONG Length)
+{
+    return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
+}
+
+ULONG
+NTAPI
+RtlNumberOfSetBits(
+    IN PRTL_BITMAP BitMapHeader)
+{
+    PUCHAR Byte, MaxByte;
+    ULONG BitCount = 0;
+
+    Byte = (PUCHAR)BitMapHeader->Buffer;
+    MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
+
+    do
+    {
+        BitCount += BitCountTable[*Byte++];
+    }
+    while (Byte <= MaxByte);
+
+    return BitCount;
+}
+
+ULONG
+NTAPI
+RtlNumberOfClearBits(
+    IN PRTL_BITMAP BitMapHeader)
+{
+    /* Do some math */
+    return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
+}
+
+ULONG
+NTAPI
+RtlFindClearBits(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG NumberToFind,
+    IN ULONG HintIndex)
+{
+    ULONG CurrentBit, CurrentLength;
+
+    /* Check for valid parameters */
+    if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+    {
+        return MAXULONG;
+    }
+
+    /* Check for trivial case */
+    if (NumberToFind == 0)
+    {
+        return HintIndex;
+    }
+
+    /* Start with hint index, length is 0 */
+    CurrentBit = HintIndex;
+    CurrentLength = 0;
+
+    /* Loop until something is found or the end is reached */
+    while (CurrentBit + NumberToFind < BitMapHeader->SizeOfBitMap)
+    {
+        ULONG test;
+        /* Search for the next clear run, by skipping a set run */
+        test = RtlpGetLengthOfRunSet(BitMapHeader,
+                                            CurrentBit,
+                                            MAXULONG);
+        CurrentBit += test;
+
+        /* Get length of the clear bit run */
+        CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
+                                                CurrentBit,
+                                                NumberToFind);
+
+        /* Is this long enough? */
+        if (CurrentLength >= NumberToFind)
+        {
+            /* It is */
+            return CurrentBit;
+        }
+
+        CurrentBit += CurrentLength;
+    }
+
+    /* Nothing found */
     return MAXULONG;
-
-  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 MAXULONG;
-}
-
-/*
- * @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 = MAXULONG;
+}
+
+ULONG
+NTAPI
+RtlFindSetBits(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG NumberToFind,
+    IN ULONG HintIndex)
+{
+    ULONG CurrentBit, CurrentLength;
+
+    /* Check for valid parameters */
+    if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
+    {
+        return MAXULONG;
+    }
+
+    /* Check for trivial case */
+    if (NumberToFind == 0)
+    {
+        return HintIndex;
+    }
+
+    /* Start with hint index, length is 0 */
+    CurrentBit = HintIndex;
+    CurrentLength = 0;
+
+    /* Loop until something is found or the end is reached */
+    while (CurrentBit + NumberToFind <= BitMapHeader->SizeOfBitMap)
+    {
+        /* Search for the next set run, by skipping a clear run */
+        CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
+                                              CurrentBit,
+                                              MAXULONG);
+
+        /* Get length of the set bit run */
+        CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
+                                              CurrentBit,
+                                              NumberToFind);
+
+        /* Is this long enough? */
+        if (CurrentLength >= NumberToFind)
+        {
+            /* It is */
+            return CurrentBit;
+        }
+
+        CurrentBit += CurrentLength;
+    }
+
+    /* Nothing found */
+    return MAXULONG;
+}
+
+ULONG
+NTAPI
+RtlFindClearBitsAndSet(
+    PRTL_BITMAP BitMapHeader,
+    ULONG NumberToFind,
+    ULONG HintIndex)
+{
+    ULONG Position;
+
+    /* Try to find clear bits */
+    Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
+
+    /* Did we get something? */
+    if (Position != MAXULONG)
+    {
+        /* Yes, set the bits */
+        RtlSetBits(BitMapHeader, Position, NumberToFind);
+    }
+
+    /* Return what we found */
+    return Position;
+}
+
+ULONG
+NTAPI
+RtlFindSetBitsAndClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG NumberToFind,
+    IN ULONG HintIndex)
+{
+    ULONG Position;
+
+    /* Try to find set bits */
+    Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
+
+    /* Did we get something? */
+    if (Position != MAXULONG)
+    {
+        /* Yes, clear the bits */
+        RtlClearBits(BitMapHeader, Position, NumberToFind);
+    }
+
+    /* Return what we found */
+    return Position;
+}
+
+ULONG
+NTAPI
+RtlFindNextForwardRunClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG FromIndex,
+    IN PULONG StartingRunIndex)
+{
+    ULONG Length;
+
+    /* Assume a set run first, count it's length */
+    Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
+    *StartingRunIndex = FromIndex;
+
+    /* Now return the length of the run */
+    return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
+}
+
+ULONG
+NTAPI
+RtlFindNextForwardRunSet(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG FromIndex,
+    IN PULONG StartingRunIndex)
+{
+    ULONG Length;
+
+    /* Assume a clear run first, count it's length */
+    Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
+    *StartingRunIndex = FromIndex;
+
+    /* Now return the length of the run */
+    return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
+}
+
+ULONG
+NTAPI
+RtlFindFirstRunClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN PULONG StartingIndex)
+{
+    return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
+}
+
+ULONG
+NTAPI
+RtlFindLastBackwardRunClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN ULONG FromIndex,
+    IN PULONG StartingRunIndex)
+{
+    UNIMPLEMENTED;
     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 = MAXULONG;
-    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)
-{
-  /* GCC complaints that it may be used uninitialized */
-  RTL_BITMAP_RUN br = { 0, 0 };
-
-  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)
-{
-  /* GCC complaints that it may be used uninitialized */
-  RTL_BITMAP_RUN br = { 0, 0 };
-
-  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 MAXULONG;
-
-  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 MAXULONG;
-}
-
-
-/*
- * @implemented
- */
-ULONG NTAPI
-RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
-		       ULONG NumberToFind,
-		       ULONG HintIndex)
-{
-  ULONG ulPos;
-
-  ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
-  if (ulPos != MAXULONG)
-    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++;
-    }
-
-    if (ulRemainder)
-    {
-      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)
-{
-  PUCHAR Ptr;
-
-  if (BitNumber >= BitMapHeader->SizeOfBitMap)
-    return;
-
-  Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
-
-  *Ptr |= (1 << (BitNumber % 8));
-}
-
-
-/*
- * @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 */
-  if (NumberToSet & 0x7)
-    *lpOut |= NTDLL_maskBits[NumberToSet & 0x7];
-}
-
-
-/*
- * @implemented
- */
-BOOLEAN NTAPI
-RtlTestBit(PRTL_BITMAP BitMapHeader,
-	   ULONG BitNumber)
-{
-  PUCHAR Ptr;
-
-  if (BitNumber >= BitMapHeader->SizeOfBitMap)
-    return FALSE;
-
-  Ptr = (PUCHAR)BitMapHeader->Buffer + (BitNumber / 8);
-
-  return (BOOLEAN)(*Ptr & (1 << (BitNumber % 8)));
-}
-
-/*
- * @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 != MAXULONG)
-    RtlSetBits(BitMapHeader, ulPos, NumberToFind);
-  return ulPos;
-}
-
-/*
- * @implemented
- */
-CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
-{
-    signed char ret = 32;
-    DWORD dw;
-
-    if (!(dw = (DWORD)(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 = (DWORD)(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 */
+}
+
+
+ULONG
+NTAPI
+RtlFindClearRuns(
+    IN PRTL_BITMAP BitMapHeader,
+    IN PRTL_BITMAP_RUN RunArray,
+    IN ULONG SizeOfRunArray,
+    IN BOOLEAN LocateLongestRuns)
+{
+    ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
+
+    /* Loop the runs */
+    for (Run = 0; Run < SizeOfRunArray; Run++)
+    {
+        /* Look for a run */
+        NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 
+                                                  FromIndex,
+                                                  &StartingIndex);
+
+        /* Nothing more found? Quit looping. */
+        if (NumberOfBits == 0) break;
+
+        /* Add another run */
+        RunArray[Run].StartingIndex = StartingIndex;
+        RunArray[Run].NumberOfBits = NumberOfBits;
+
+        /* Update smallest run */
+        if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
+        {
+            SmallestRun = Run;
+        }
+
+        /* Advance bits */
+        FromIndex += NumberOfBits;
+    }
+
+    /* Check if we are finished */
+    if (Run < SizeOfRunArray || !LocateLongestRuns)
+    {
+        /* Return the number of found runs */
+        return Run;
+    }
+
+    while (1)
+    {
+        /* Look for a run */
+        NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 
+                                                  FromIndex,
+                                                  &StartingIndex);
+
+        /* Nothing more found? Quit looping. */
+        if (NumberOfBits == 0) break;
+
+        /* Check if we have something to update */
+        if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
+        {
+            /* Update smallest run */
+            RunArray[SmallestRun].StartingIndex = StartingIndex;
+            RunArray[SmallestRun].NumberOfBits = NumberOfBits;
+
+            /* Loop all runs */
+            for (Run = 0; Run < SizeOfRunArray; Run++)
+            {
+                /*Is this the new smallest run? */
+                if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
+                {
+                    /* Set it as new smallest run */
+                    SmallestRun = Run;
+                }
+            }
+        }
+
+        /* Advance bits */
+        FromIndex += NumberOfBits;
+    }
+
+    return Run;
+}
+
+ULONG
+NTAPI
+RtlFindLongestRunClear(
+    IN PRTL_BITMAP BitMapHeader,
+    IN PULONG StartingIndex)
+{
+    ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+
+    while (1)
+    {
+        /* Look for a run */
+        NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 
+                                                  FromIndex,
+                                                  &Index);
+
+        /* Nothing more found? Quit looping. */
+        if (NumberOfBits == 0) break;
+
+        /* Was that the longest run? */
+        if (NumberOfBits > MaxNumberOfBits)
+        {
+            /* Update values */
+            MaxNumberOfBits = NumberOfBits;
+            *StartingIndex = Index;
+        }
+
+        /* Advance bits */
+        FromIndex += NumberOfBits;
+    }
+
+    return MaxNumberOfBits;
+}
+
+ULONG
+NTAPI
+RtlFindLongestRunSet(
+    IN PRTL_BITMAP BitMapHeader,
+    IN PULONG StartingIndex)
+{
+    ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
+
+    while (1)
+    {
+        /* Look for a run */
+        NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader, 
+                                                FromIndex,
+                                                &Index);
+
+        /* Nothing more found? Quit looping. */
+        if (NumberOfBits == 0) break;
+
+        /* Was that the longest run? */
+        if (NumberOfBits > MaxNumberOfBits)
+        {
+            /* Update values */
+            MaxNumberOfBits = NumberOfBits;
+            *StartingIndex = Index;
+        }
+
+        /* Advance bits */
+        FromIndex += NumberOfBits;
+    }
+
+    return MaxNumberOfBits;
+}
+

Modified: trunk/reactos/tools/mkhive/mkhive.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/tools/mkhive/mkhive.h?rev=…
==============================================================================
--- trunk/reactos/tools/mkhive/mkhive.h [iso-8859-1] (original)
+++ trunk/reactos/tools/mkhive/mkhive.h [iso-8859-1] Tue Dec  8 02:02:36 2009
@@ -46,6 +46,10 @@
 #define STATUS_OBJECT_NAME_NOT_FOUND     ((NTSTATUS)0xC0000034)
 #define STATUS_INVALID_PARAMETER_2       ((NTSTATUS)0xC00000F0)
 #define STATUS_BUFFER_OVERFLOW           ((NTSTATUS)0x80000005)
+
+unsigned char BitScanForward(ULONG * Index, const unsigned long Mask);
+unsigned char BitScanReverse(ULONG * const Index, const unsigned long Mask);
+#define RtlFillMemoryUlong(dst, len, val) memset(dst, val, len)
 
 NTSTATUS NTAPI
 RtlAnsiStringToUnicodeString(

Modified: trunk/reactos/tools/mkhive/rtl.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/tools/mkhive/rtl.c?rev=444…
==============================================================================
--- trunk/reactos/tools/mkhive/rtl.c [iso-8859-1] (original)
+++ trunk/reactos/tools/mkhive/rtl.c [iso-8859-1] Tue Dec  8 02:02:36 2009
@@ -185,3 +185,25 @@
 
    //DbgBreakPoint();
 }
+
+unsigned char BitScanForward(ULONG * Index, unsigned long Mask)
+{
+    *Index = 0;
+    while (Mask && ((Mask & 1) == 0))
+    {
+        Mask >>= 1;
+        ++(*Index);
+    }
+    return Mask ? 1 : 0;
+}
+
+unsigned char BitScanReverse(ULONG * const Index, unsigned long Mask)
+{
+    *Index = 0;
+    while (Mask && ((Mask & (1 << 31)) == 0))
+    {
+        Mask <<= 1;
+        ++(*Index);
+    }
+    return Mask ? 1 : 0;
+}