reactos/lib/rtl/bitmap.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PROJECT:         ReactOS system libraries
   4  * FILE:            lib/rtl/bitmap.c
   5  * PURPOSE:         Bitmap functions
   6  * PROGRAMMER:      Timo Kreuzer (timo.kreuzer@reactos.org)
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #include <rtl.h>
  12
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16
  17 /* DATA *********************************************************************/
  18
  19 /* Number of set bits per byte value */
  20 static const
  21 UCHAR
  22 BitCountTable[256] =
  23 {
  24     /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
  25        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
  26        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
  27        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
  28        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
  29        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
  30        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
  31        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
  32        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
  33        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
  34        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
  35        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
  36        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
  37        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
  38        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
  39        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
  40        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8  /* Fx */
  41 };
  42
  43
  44 /* PRIVATE FUNCTIONS ********************************************************/
  45
  46 static __inline__
  47 ULONG
  48 RtlpGetLengthOfRunClear(
  49     IN PRTL_BITMAP BitMapHeader,
  50     IN ULONG StartingIndex,
  51     IN ULONG MaxLength)
  52 {
  53     ULONG Value, BitPos, Length;
  54     PULONG Buffer, MaxBuffer;
  55
  56     /* Calculate positions */
  57     Buffer = BitMapHeader->Buffer + StartingIndex / 32;
  58     BitPos = StartingIndex & 31;
  59
  60     /* Calculate the maximum length */
  61     MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
  62     MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
  63
  64     /* Clear the bits that don't belong to this run */
  65     Value = *Buffer++ >> BitPos << BitPos;
  66
  67     /* Skip all clear ULONGs */
  68     while (Value == 0 && Buffer < MaxBuffer)
  69     {
  70         Value = *Buffer++;
  71     }
  72
  73     /* Did we reach the end? */
  74     if (Value == 0)
  75     {
  76         /* Return maximum length */
  77         return MaxLength;
  78     }
  79
  80     /* We hit a set bit, check how many clear bits are left */
  81     BitScanForward(&BitPos, Value);
  82
  83     /* Calculate length up to where we read */
  84     Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
  85     Length += BitPos - 32;
  86
  87     /* Make sure we don't go past the last bit */
  88     if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
  89         Length = BitMapHeader->SizeOfBitMap - StartingIndex;
  90
  91     /* Return the result */
  92     return Length;
  93 }
  94
  95 static __inline__
  96 ULONG
  97 RtlpGetLengthOfRunSet(
  98     IN PRTL_BITMAP BitMapHeader,
  99     IN ULONG StartingIndex,
 100     IN ULONG MaxLength)
 101 {
 102     ULONG InvValue, BitPos, Length;
 103     PULONG Buffer, MaxBuffer;
 104
 105     /* Calculate positions */
 106     Buffer = BitMapHeader->Buffer + StartingIndex / 32;
 107     BitPos = StartingIndex & 31;
 108
 109     /* Calculate the maximum length */
 110     MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
 111     MaxBuffer = Buffer + (BitPos + MaxLength + 31) / 32;
 112
 113     /* Get the inversed value, clear bits that don't belong to the run */
 114     InvValue = ~(*Buffer++) >> BitPos << BitPos;
 115
 116     /* Skip all set ULONGs */
 117     while (InvValue == 0 && Buffer < MaxBuffer)
 118     {
 119         InvValue = ~(*Buffer++);
 120     }
 121
 122     /* Did we reach the end? */
 123     if (InvValue == 0)
 124     {
 125         /* Yes, return maximum */
 126         return MaxLength;
 127     }
 128
 129     /* We hit a clear bit, check how many set bits are left */
 130     BitScanForward(&BitPos, InvValue);
 131
 132     /* Calculate length up to where we read */
 133     Length = (Buffer - BitMapHeader->Buffer) * 32 - StartingIndex;
 134     Length += BitPos - 32;
 135
 136     /* Make sure we don't go past the last bit */
 137     if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
 138         Length = BitMapHeader->SizeOfBitMap - StartingIndex;
 139
 140     /* Return the result */
 141     return Length;
 142 }
 143
 144
 145 /* PUBLIC FUNCTIONS **********************************************************/
 146
 147 CCHAR
 148 NTAPI
 149 RtlFindMostSignificantBit(ULONGLONG Value)
 150 {
 151     ULONG Position;
 152
 153     if (BitScanReverse(&Position, Value >> 32))
 154     {
 155         return Position + 32;
 156     }
 157     else if (BitScanReverse(&Position, (ULONG)Value))
 158     {
 159         return Position;
 160     }
 161
 162     return -1;
 163 }
 164
 165 CCHAR
 166 NTAPI
 167 RtlFindLeastSignificantBit(ULONGLONG Value)
 168 {
 169     ULONG Position;
 170
 171     if (BitScanForward(&Position, (ULONG)Value))
 172     {
 173         return Position;
 174     }
 175     else if (BitScanForward(&Position, Value >> 32))
 176     {
 177         return Position + 32;
 178     }
 179
 180     return -1;
 181 }
 182
 183 VOID
 184 NTAPI
 185 RtlInitializeBitMap(
 186     IN PRTL_BITMAP BitMapHeader,
 187     IN PULONG BitMapBuffer,
 188     IN ULONG SizeOfBitMap)
 189 {
 190     // FIXME: some bugger here!
 191     //ASSERT(SizeOfBitMap > 0);
 192
 193     /* Setup the bitmap header */
 194     BitMapHeader->SizeOfBitMap = SizeOfBitMap;
 195     BitMapHeader->Buffer = BitMapBuffer;
 196 }
 197
 198 VOID
 199 NTAPI
 200 RtlClearAllBits(
 201     IN OUT PRTL_BITMAP BitMapHeader)
 202 {
 203     ULONG LengthInUlongs;
 204
 205     LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
 206     RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
 207 }
 208
 209 VOID
 210 NTAPI
 211 RtlSetAllBits(
 212     IN OUT PRTL_BITMAP BitMapHeader)
 213 {
 214     ULONG LengthInUlongs;
 215
 216     LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
 217     RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
 218 }
 219
 220 VOID
 221 NTAPI
 222 RtlClearBit(
 223     IN PRTL_BITMAP BitMapHeader,
 224     IN ULONG BitNumber)
 225 {
 226     ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
 227     BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber & 31));
 228 }
 229
 230 VOID
 231 NTAPI
 232 RtlSetBit(
 233     IN PRTL_BITMAP BitMapHeader,
 234     IN ULONG BitNumber)
 235 {
 236     ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
 237     BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
 238 }
 239
 240 VOID
 241 NTAPI
 242 RtlClearBits(
 243     IN PRTL_BITMAP BitMapHeader,
 244     IN ULONG StartingIndex,
 245     IN ULONG NumberToClear)
 246 {
 247     ULONG Bits, Mask;
 248     PULONG Buffer;
 249
 250     ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
 251
 252     /* Calculate buffer start and first bit index */
 253     Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
 254     Bits = StartingIndex & 31;
 255
 256     /* Are we unaligned? */
 257     if (Bits)
 258     {
 259         /* Create an inverse mask by shifting MAXULONG */
 260         Mask = MAXULONG << Bits;
 261
 262         /* This is what's left in the first ULONG */
 263         Bits = 32 - Bits;
 264
 265         /* Even less bits to clear? */
 266         if (NumberToClear < Bits)
 267         {
 268             /* Calculate how many bits are left */
 269             Bits -= NumberToClear;
 270
 271             /* Fixup the mask on the high side */
 272             Mask = Mask << Bits >> Bits;
 273
 274             /* Clear bits and return */
 275             *Buffer &= ~Mask;
 276             return;
 277         }
 278
 279         /* Clear bits */
 280         *Buffer &= ~Mask;
 281
 282         /* Update buffer and left bits */
 283         Buffer++;
 284         NumberToClear -= Bits;
 285     }
 286
 287     /* Clear all full ULONGs */
 288     RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
 289     Buffer += NumberToClear >> 5;
 290
 291     /* Clear what's left */
 292     NumberToClear &= 31;
 293     Mask = MAXULONG << NumberToClear;
 294     *Buffer &= Mask;
 295 }
 296
 297 VOID
 298 NTAPI
 299 RtlSetBits(
 300     IN PRTL_BITMAP BitMapHeader,
 301     IN ULONG StartingIndex,
 302     IN ULONG NumberToSet)
 303 {
 304     ULONG Bits, Mask;
 305     PULONG Buffer;
 306
 307     ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
 308
 309     /* Calculate buffer start and first bit index */
 310     Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
 311     Bits = StartingIndex & 31;
 312
 313     /* Are we unaligned? */
 314     if (Bits)
 315     {
 316         /* Create a mask by shifting MAXULONG */
 317         Mask = MAXULONG << Bits;
 318
 319         /* This is what's left in the first ULONG */
 320         Bits = 32 - Bits;
 321
 322         /* Even less bits to clear? */
 323         if (NumberToSet < Bits)
 324         {
 325             /* Calculate how many bits are left */
 326             Bits -= NumberToSet;
 327
 328             /* Fixup the mask on the high side */
 329             Mask = Mask << Bits >> Bits;
 330
 331             /* Set bits and return */
 332             *Buffer |= Mask;
 333             return;
 334         }
 335
 336         /* Set bits */
 337         *Buffer |= Mask;
 338
 339         /* Update buffer and left bits */
 340         Buffer++;
 341         NumberToSet -= Bits;
 342     }
 343
 344     /* Set all full ULONGs */
 345     RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
 346     Buffer += NumberToSet >> 5;
 347
 348     /* Set what's left */
 349     NumberToSet &= 31;
 350     Mask = MAXULONG << NumberToSet;
 351     *Buffer |= ~Mask;
 352 }
 353
 354 BOOLEAN
 355 NTAPI
 356 RtlTestBit(
 357     IN PRTL_BITMAP BitMapHeader,
 358     IN ULONG BitNumber)
 359 {
 360     ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
 361     return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31)) & 1;
 362 }
 363
 364 BOOLEAN
 365 NTAPI
 366 RtlAreBitsClear(
 367     IN PRTL_BITMAP BitMapHeader,
 368     IN ULONG StartingIndex,
 369     IN ULONG Length)
 370 {
 371     return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
 372 }
 373
 374 BOOLEAN
 375 NTAPI
 376 RtlAreBitsSet(
 377     IN PRTL_BITMAP BitMapHeader,
 378     IN ULONG StartingIndex,
 379     IN ULONG Length)
 380 {
 381     return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
 382 }
 383
 384 ULONG
 385 NTAPI
 386 RtlNumberOfSetBits(
 387     IN PRTL_BITMAP BitMapHeader)
 388 {
 389     PUCHAR Byte, MaxByte;
 390     ULONG BitCount = 0;
 391
 392     Byte = (PUCHAR)BitMapHeader->Buffer;
 393     MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
 394
 395     do
 396     {
 397         BitCount += BitCountTable[*Byte++];
 398     }
 399     while (Byte <= MaxByte);
 400
 401     return BitCount;
 402 }
 403
 404 ULONG
 405 NTAPI
 406 RtlNumberOfClearBits(
 407     IN PRTL_BITMAP BitMapHeader)
 408 {
 409     /* Do some math */
 410     return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
 411 }
 412
 413 ULONG
 414 NTAPI
 415 RtlFindClearBits(
 416     IN PRTL_BITMAP BitMapHeader,
 417     IN ULONG NumberToFind,
 418     IN ULONG HintIndex)
 419 {
 420     ULONG CurrentBit, CurrentLength;
 421
 422     /* Check for valid parameters */
 423     if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
 424     {
 425         return MAXULONG;
 426     }
 427
 428     /* Check for trivial case */
 429     if (NumberToFind == 0)
 430     {
 431         return HintIndex;
 432     }
 433
 434     /* Start with hint index, length is 0 */
 435     CurrentBit = HintIndex;
 436     CurrentLength = 0;
 437
 438     /* Loop until something is found or the end is reached */
 439     while (CurrentBit + NumberToFind < BitMapHeader->SizeOfBitMap)
 440     {
 441         /* Search for the next clear run, by skipping a set run */
 442         CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
 443                                             CurrentBit,
 444                                             MAXULONG);
 445
 446         /* Get length of the clear bit run */
 447         CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
 448                                                 CurrentBit,
 449                                                 NumberToFind);
 450
 451         /* Is this long enough? */
 452         if (CurrentLength >= NumberToFind)
 453         {
 454             /* It is */
 455             return CurrentBit;
 456         }
 457
 458         CurrentBit += CurrentLength;
 459     }
 460
 461     /* Nothing found */
 462     return MAXULONG;
 463 }
 464
 465 ULONG
 466 NTAPI
 467 RtlFindSetBits(
 468     IN PRTL_BITMAP BitMapHeader,
 469     IN ULONG NumberToFind,
 470     IN ULONG HintIndex)
 471 {
 472     ULONG CurrentBit, CurrentLength;
 473
 474     /* Check for valid parameters */
 475     if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
 476     {
 477         return MAXULONG;
 478     }
 479
 480     /* Check for trivial case */
 481     if (NumberToFind == 0)
 482     {
 483         return HintIndex;
 484     }
 485
 486     /* Start with hint index, length is 0 */
 487     CurrentBit = HintIndex;
 488     CurrentLength = 0;
 489
 490     /* Loop until something is found or the end is reached */
 491     while (CurrentBit + NumberToFind <= BitMapHeader->SizeOfBitMap)
 492     {
 493         /* Search for the next set run, by skipping a clear run */
 494         CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
 495                                               CurrentBit,
 496                                               MAXULONG);
 497
 498         /* Get length of the set bit run */
 499         CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
 500                                               CurrentBit,
 501                                               NumberToFind);
 502
 503         /* Is this long enough? */
 504         if (CurrentLength >= NumberToFind)
 505         {
 506             /* It is */
 507             return CurrentBit;
 508         }
 509
 510         CurrentBit += CurrentLength;
 511     }
 512
 513     /* Nothing found */
 514     return MAXULONG;
 515 }
 516
 517 ULONG
 518 NTAPI
 519 RtlFindClearBitsAndSet(
 520     PRTL_BITMAP BitMapHeader,
 521     ULONG NumberToFind,
 522     ULONG HintIndex)
 523 {
 524     ULONG Position;
 525
 526     /* Try to find clear bits */
 527     Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
 528
 529     /* Did we get something? */
 530     if (Position != MAXULONG)
 531     {
 532         /* Yes, set the bits */
 533         RtlSetBits(BitMapHeader, Position, NumberToFind);
 534     }
 535
 536     /* Return what we found */
 537     return Position;
 538 }
 539
 540 ULONG
 541 NTAPI
 542 RtlFindSetBitsAndClear(
 543     IN PRTL_BITMAP BitMapHeader,
 544     IN ULONG NumberToFind,
 545     IN ULONG HintIndex)
 546 {
 547     ULONG Position;
 548
 549     /* Try to find set bits */
 550     Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
 551
 552     /* Did we get something? */
 553     if (Position != MAXULONG)
 554     {
 555         /* Yes, clear the bits */
 556         RtlClearBits(BitMapHeader, Position, NumberToFind);
 557     }
 558
 559     /* Return what we found */
 560     return Position;
 561 }
 562
 563 ULONG
 564 NTAPI
 565 RtlFindNextForwardRunClear(
 566     IN PRTL_BITMAP BitMapHeader,
 567     IN ULONG FromIndex,
 568     IN PULONG StartingRunIndex)
 569 {
 570     ULONG Length;
 571
 572     /* Assume a set run first, count it's length */
 573     Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 574     *StartingRunIndex = FromIndex;
 575
 576     /* Now return the length of the run */
 577     return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
 578 }
 579
 580 ULONG
 581 NTAPI
 582 RtlFindNextForwardRunSet(
 583     IN PRTL_BITMAP BitMapHeader,
 584     IN ULONG FromIndex,
 585     IN PULONG StartingRunIndex)
 586 {
 587     ULONG Length;
 588
 589     /* Assume a clear run first, count it's length */
 590     Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
 591     *StartingRunIndex = FromIndex;
 592
 593     /* Now return the length of the run */
 594     return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 595 }
 596
 597 ULONG
 598 NTAPI
 599 RtlFindFirstRunClear(
 600     IN PRTL_BITMAP BitMapHeader,
 601     IN PULONG StartingIndex)
 602 {
 603     return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
 604 }
 605
 606 ULONG
 607 NTAPI
 608 RtlFindLastBackwardRunClear(
 609     IN PRTL_BITMAP BitMapHeader,
 610     IN ULONG FromIndex,
 611     IN PULONG StartingRunIndex)
 612 {
 613     UNIMPLEMENTED;
 614     return 0;
 615 }
 616
 617
 618 ULONG
 619 NTAPI
 620 RtlFindClearRuns(
 621     IN PRTL_BITMAP BitMapHeader,
 622     IN PRTL_BITMAP_RUN RunArray,
 623     IN ULONG SizeOfRunArray,
 624     IN BOOLEAN LocateLongestRuns)
 625 {
 626     ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
 627
 628     /* Loop the runs */
 629     for (Run = 0; Run < SizeOfRunArray; Run++)
 630     {
 631         /* Look for a run */
 632         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 633                                                   FromIndex,
 634                                                   &StartingIndex);
 635
 636         /* Nothing more found? Quit looping. */
 637         if (NumberOfBits == 0) break;
 638
 639         /* Add another run */
 640         RunArray[Run].StartingIndex = StartingIndex;
 641         RunArray[Run].NumberOfBits = NumberOfBits;
 642
 643         /* Update smallest run */
 644         if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 645         {
 646             SmallestRun = Run;
 647         }
 648
 649         /* Advance bits */
 650         FromIndex += NumberOfBits;
 651     }
 652
 653     /* Check if we are finished */
 654     if (Run < SizeOfRunArray || !LocateLongestRuns)
 655     {
 656         /* Return the number of found runs */
 657         return Run;
 658     }
 659
 660     while (1)
 661     {
 662         /* Look for a run */
 663         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 664                                                   FromIndex,
 665                                                   &StartingIndex);
 666
 667         /* Nothing more found? Quit looping. */
 668         if (NumberOfBits == 0) break;
 669
 670         /* Check if we have something to update */
 671         if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
 672         {
 673             /* Update smallest run */
 674             RunArray[SmallestRun].StartingIndex = StartingIndex;
 675             RunArray[SmallestRun].NumberOfBits = NumberOfBits;
 676
 677             /* Loop all runs */
 678             for (Run = 0; Run < SizeOfRunArray; Run++)
 679             {
 680                 /*Is this the new smallest run? */
 681                 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 682                 {
 683                     /* Set it as new smallest run */
 684                     SmallestRun = Run;
 685                 }
 686             }
 687         }
 688
 689         /* Advance bits */
 690         FromIndex += NumberOfBits;
 691     }
 692
 693     return Run;
 694 }
 695
 696 ULONG
 697 NTAPI
 698 RtlFindLongestRunClear(
 699     IN PRTL_BITMAP BitMapHeader,
 700     IN PULONG StartingIndex)
 701 {
 702     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 703
 704     while (1)
 705     {
 706         /* Look for a run */
 707         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 708                                                   FromIndex,
 709                                                   &Index);
 710
 711         /* Nothing more found? Quit looping. */
 712         if (NumberOfBits == 0) break;
 713
 714         /* Was that the longest run? */
 715         if (NumberOfBits > MaxNumberOfBits)
 716         {
 717             /* Update values */
 718             MaxNumberOfBits = NumberOfBits;
 719             *StartingIndex = Index;
 720         }
 721
 722         /* Advance bits */
 723         FromIndex += NumberOfBits;
 724     }
 725
 726     return MaxNumberOfBits;
 727 }
 728
 729 ULONG
 730 NTAPI
 731 RtlFindLongestRunSet(
 732     IN PRTL_BITMAP BitMapHeader,
 733     IN PULONG StartingIndex)
 734 {
 735     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 736
 737     while (1)
 738     {
 739         /* Look for a run */
 740         NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
 741                                                 FromIndex,
 742                                                 &Index);
 743
 744         /* Nothing more found? Quit looping. */
 745         if (NumberOfBits == 0) break;
 746
 747         /* Was that the longest run? */
 748         if (NumberOfBits > MaxNumberOfBits)
 749         {
 750             /* Update values */
 751             MaxNumberOfBits = NumberOfBits;
 752             *StartingIndex = Index;
 753         }
 754
 755         /* Advance bits */
 756         FromIndex += NumberOfBits;
 757     }
 758
 759     return MaxNumberOfBits;
 760 }
 761