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, Margin, 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     /* First margin is end of bitmap */
 435     Margin = BitMapHeader->SizeOfBitMap;
 436
 437 retry:
 438     /* Start with hint index, length is 0 */
 439     CurrentBit = HintIndex;
 440
 441     /* Loop until something is found or the end is reached */
 442     while (CurrentBit + NumberToFind < Margin)
 443     {
 444         /* Search for the next clear run, by skipping a set run */
 445         CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
 446                                             CurrentBit,
 447                                             MAXULONG);
 448
 449         /* Get length of the clear bit run */
 450         CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
 451                                                 CurrentBit,
 452                                                 NumberToFind);
 453
 454         /* Is this long enough? */
 455         if (CurrentLength >= NumberToFind)
 456         {
 457             /* It is */
 458             return CurrentBit;
 459         }
 460
 461         CurrentBit += CurrentLength;
 462     }
 463
 464     /* Did we start at a hint? */
 465     if (HintIndex)
 466     {
 467         /* Retry at the start */
 468         Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
 469         HintIndex = 0;
 470         goto retry;
 471     }
 472
 473     /* Nothing found */
 474     return MAXULONG;
 475 }
 476
 477 ULONG
 478 NTAPI
 479 RtlFindSetBits(
 480     IN PRTL_BITMAP BitMapHeader,
 481     IN ULONG NumberToFind,
 482     IN ULONG HintIndex)
 483 {
 484     ULONG CurrentBit, CurrentLength;
 485
 486     /* Check for valid parameters */
 487     if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
 488     {
 489         return MAXULONG;
 490     }
 491
 492     /* Check for trivial case */
 493     if (NumberToFind == 0)
 494     {
 495         return HintIndex;
 496     }
 497
 498     /* Start with hint index, length is 0 */
 499     CurrentBit = HintIndex;
 500     CurrentLength = 0;
 501
 502     /* Loop until something is found or the end is reached */
 503     while (CurrentBit + NumberToFind <= BitMapHeader->SizeOfBitMap)
 504     {
 505         /* Search for the next set run, by skipping a clear run */
 506         CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
 507                                               CurrentBit,
 508                                               MAXULONG);
 509
 510         /* Get length of the set bit run */
 511         CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
 512                                               CurrentBit,
 513                                               NumberToFind);
 514
 515         /* Is this long enough? */
 516         if (CurrentLength >= NumberToFind)
 517         {
 518             /* It is */
 519             return CurrentBit;
 520         }
 521
 522         CurrentBit += CurrentLength;
 523     }
 524
 525     /* Nothing found */
 526     return MAXULONG;
 527 }
 528
 529 ULONG
 530 NTAPI
 531 RtlFindClearBitsAndSet(
 532     PRTL_BITMAP BitMapHeader,
 533     ULONG NumberToFind,
 534     ULONG HintIndex)
 535 {
 536     ULONG Position;
 537
 538     /* Try to find clear bits */
 539     Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
 540
 541     /* Did we get something? */
 542     if (Position != MAXULONG)
 543     {
 544         /* Yes, set the bits */
 545         RtlSetBits(BitMapHeader, Position, NumberToFind);
 546     }
 547
 548     /* Return what we found */
 549     return Position;
 550 }
 551
 552 ULONG
 553 NTAPI
 554 RtlFindSetBitsAndClear(
 555     IN PRTL_BITMAP BitMapHeader,
 556     IN ULONG NumberToFind,
 557     IN ULONG HintIndex)
 558 {
 559     ULONG Position;
 560
 561     /* Try to find set bits */
 562     Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
 563
 564     /* Did we get something? */
 565     if (Position != MAXULONG)
 566     {
 567         /* Yes, clear the bits */
 568         RtlClearBits(BitMapHeader, Position, NumberToFind);
 569     }
 570
 571     /* Return what we found */
 572     return Position;
 573 }
 574
 575 ULONG
 576 NTAPI
 577 RtlFindNextForwardRunClear(
 578     IN PRTL_BITMAP BitMapHeader,
 579     IN ULONG FromIndex,
 580     IN PULONG StartingRunIndex)
 581 {
 582     ULONG Length;
 583
 584     /* Assume a set run first, count it's length */
 585     Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 586     *StartingRunIndex = FromIndex + Length;
 587
 588     /* Now return the length of the run */
 589     return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXULONG);
 590 }
 591
 592 ULONG
 593 NTAPI
 594 RtlFindNextForwardRunSet(
 595     IN PRTL_BITMAP BitMapHeader,
 596     IN ULONG FromIndex,
 597     IN PULONG StartingRunIndex)
 598 {
 599     ULONG Length;
 600
 601     /* Assume a clear run first, count it's length */
 602     Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
 603     *StartingRunIndex = FromIndex + Length;
 604
 605     /* Now return the length of the run */
 606     return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 607 }
 608
 609 ULONG
 610 NTAPI
 611 RtlFindFirstRunClear(
 612     IN PRTL_BITMAP BitMapHeader,
 613     IN PULONG StartingIndex)
 614 {
 615     return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
 616 }
 617
 618 ULONG
 619 NTAPI
 620 RtlFindLastBackwardRunClear(
 621     IN PRTL_BITMAP BitMapHeader,
 622     IN ULONG FromIndex,
 623     IN PULONG StartingRunIndex)
 624 {
 625     UNIMPLEMENTED;
 626     return 0;
 627 }
 628
 629
 630 ULONG
 631 NTAPI
 632 RtlFindClearRuns(
 633     IN PRTL_BITMAP BitMapHeader,
 634     IN PRTL_BITMAP_RUN RunArray,
 635     IN ULONG SizeOfRunArray,
 636     IN BOOLEAN LocateLongestRuns)
 637 {
 638     ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
 639
 640     /* Loop the runs */
 641     for (Run = 0; Run < SizeOfRunArray; Run++)
 642     {
 643         /* Look for a run */
 644         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 645                                                   FromIndex,
 646                                                   &StartingIndex);
 647
 648         /* Nothing more found? Quit looping. */
 649         if (NumberOfBits == 0) break;
 650
 651         /* Add another run */
 652         RunArray[Run].StartingIndex = StartingIndex;
 653         RunArray[Run].NumberOfBits = NumberOfBits;
 654
 655         /* Update smallest run */
 656         if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 657         {
 658             SmallestRun = Run;
 659         }
 660
 661         /* Advance bits */
 662         FromIndex = StartingIndex + NumberOfBits;
 663     }
 664
 665     /* Check if we are finished */
 666     if (Run < SizeOfRunArray || !LocateLongestRuns)
 667     {
 668         /* Return the number of found runs */
 669         return Run;
 670     }
 671
 672     while (1)
 673     {
 674         /* Look for a run */
 675         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 676                                                   FromIndex,
 677                                                   &StartingIndex);
 678
 679         /* Nothing more found? Quit looping. */
 680         if (NumberOfBits == 0) break;
 681
 682         /* Check if we have something to update */
 683         if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
 684         {
 685             /* Update smallest run */
 686             RunArray[SmallestRun].StartingIndex = StartingIndex;
 687             RunArray[SmallestRun].NumberOfBits = NumberOfBits;
 688
 689             /* Loop all runs */
 690             for (Run = 0; Run < SizeOfRunArray; Run++)
 691             {
 692                 /*Is this the new smallest run? */
 693                 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 694                 {
 695                     /* Set it as new smallest run */
 696                     SmallestRun = Run;
 697                 }
 698             }
 699         }
 700
 701         /* Advance bits */
 702         FromIndex += NumberOfBits;
 703     }
 704
 705     return Run;
 706 }
 707
 708 ULONG
 709 NTAPI
 710 RtlFindLongestRunClear(
 711     IN PRTL_BITMAP BitMapHeader,
 712     IN PULONG StartingIndex)
 713 {
 714     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 715
 716     while (1)
 717     {
 718         /* Look for a run */
 719         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 720                                                   FromIndex,
 721                                                   &Index);
 722
 723         /* Nothing more found? Quit looping. */
 724         if (NumberOfBits == 0) break;
 725
 726         /* Was that the longest run? */
 727         if (NumberOfBits > MaxNumberOfBits)
 728         {
 729             /* Update values */
 730             MaxNumberOfBits = NumberOfBits;
 731             *StartingIndex = Index;
 732         }
 733
 734         /* Advance bits */
 735         FromIndex += NumberOfBits;
 736     }
 737
 738     return MaxNumberOfBits;
 739 }
 740
 741 ULONG
 742 NTAPI
 743 RtlFindLongestRunSet(
 744     IN PRTL_BITMAP BitMapHeader,
 745     IN PULONG StartingIndex)
 746 {
 747     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 748
 749     while (1)
 750     {
 751         /* Look for a run */
 752         NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
 753                                                 FromIndex,
 754                                                 &Index);
 755
 756         /* Nothing more found? Quit looping. */
 757         if (NumberOfBits == 0) break;
 758
 759         /* Was that the longest run? */
 760         if (NumberOfBits > MaxNumberOfBits)
 761         {
 762             /* Update values */
 763             MaxNumberOfBits = NumberOfBits;
 764             *StartingIndex = Index;
 765         }
 766
 767         /* Advance bits */
 768         FromIndex += NumberOfBits;
 769     }
 770
 771     return MaxNumberOfBits;
 772 }
 773