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 (CCHAR)(Position + 32);
 156     }
 157     else if (BitScanReverse(&Position, (ULONG)Value))
 158     {
 159         return (CCHAR)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 (CCHAR)Position;
 174     }
 175     else if (BitScanForward(&Position, Value >> 32))
 176     {
 177         return (CCHAR)(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     /* Setup the bitmap header */
 191     BitMapHeader->SizeOfBitMap = SizeOfBitMap;
 192     BitMapHeader->Buffer = BitMapBuffer;
 193 }
 194
 195 VOID
 196 NTAPI
 197 RtlClearAllBits(
 198     IN OUT PRTL_BITMAP BitMapHeader)
 199 {
 200     ULONG LengthInUlongs;
 201
 202     LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
 203     RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, 0);
 204 }
 205
 206 VOID
 207 NTAPI
 208 RtlSetAllBits(
 209     IN OUT PRTL_BITMAP BitMapHeader)
 210 {
 211     ULONG LengthInUlongs;
 212
 213     LengthInUlongs = (BitMapHeader->SizeOfBitMap + 31) >> 5;
 214     RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs << 2, ~0);
 215 }
 216
 217 VOID
 218 NTAPI
 219 RtlClearBit(
 220     IN PRTL_BITMAP BitMapHeader,
 221     IN ULONG BitNumber)
 222 {
 223     ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
 224     BitMapHeader->Buffer[BitNumber >> 5] &= ~(1 << (BitNumber & 31));
 225 }
 226
 227 VOID
 228 NTAPI
 229 RtlSetBit(
 230     IN PRTL_BITMAP BitMapHeader,
 231     IN ULONG BitNumber)
 232 {
 233     ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
 234     BitMapHeader->Buffer[BitNumber >> 5] |= (1 << (BitNumber & 31));
 235 }
 236
 237 VOID
 238 NTAPI
 239 RtlClearBits(
 240     IN PRTL_BITMAP BitMapHeader,
 241     IN ULONG StartingIndex,
 242     IN ULONG NumberToClear)
 243 {
 244     ULONG Bits, Mask;
 245     PULONG Buffer;
 246
 247     ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
 248
 249     /* Calculate buffer start and first bit index */
 250     Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
 251     Bits = StartingIndex & 31;
 252
 253     /* Are we unaligned? */
 254     if (Bits)
 255     {
 256         /* Create an inverse mask by shifting MAXULONG */
 257         Mask = MAXULONG << Bits;
 258
 259         /* This is what's left in the first ULONG */
 260         Bits = 32 - Bits;
 261
 262         /* Even less bits to clear? */
 263         if (NumberToClear < Bits)
 264         {
 265             /* Calculate how many bits are left */
 266             Bits -= NumberToClear;
 267
 268             /* Fixup the mask on the high side */
 269             Mask = Mask << Bits >> Bits;
 270
 271             /* Clear bits and return */
 272             *Buffer &= ~Mask;
 273             return;
 274         }
 275
 276         /* Clear bits */
 277         *Buffer &= ~Mask;
 278
 279         /* Update buffer and left bits */
 280         Buffer++;
 281         NumberToClear -= Bits;
 282     }
 283
 284     /* Clear all full ULONGs */
 285     RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
 286     Buffer += NumberToClear >> 5;
 287
 288     /* Clear what's left */
 289     NumberToClear &= 31;
 290     Mask = MAXULONG << NumberToClear;
 291     *Buffer &= Mask;
 292 }
 293
 294 VOID
 295 NTAPI
 296 RtlSetBits(
 297     IN PRTL_BITMAP BitMapHeader,
 298     IN ULONG StartingIndex,
 299     IN ULONG NumberToSet)
 300 {
 301     ULONG Bits, Mask;
 302     PULONG Buffer;
 303
 304     ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
 305
 306     /* Calculate buffer start and first bit index */
 307     Buffer = &BitMapHeader->Buffer[StartingIndex >> 5];
 308     Bits = StartingIndex & 31;
 309
 310     /* Are we unaligned? */
 311     if (Bits)
 312     {
 313         /* Create a mask by shifting MAXULONG */
 314         Mask = MAXULONG << Bits;
 315
 316         /* This is what's left in the first ULONG */
 317         Bits = 32 - Bits;
 318
 319         /* Even less bits to clear? */
 320         if (NumberToSet < Bits)
 321         {
 322             /* Calculate how many bits are left */
 323             Bits -= NumberToSet;
 324
 325             /* Fixup the mask on the high side */
 326             Mask = Mask << Bits >> Bits;
 327
 328             /* Set bits and return */
 329             *Buffer |= Mask;
 330             return;
 331         }
 332
 333         /* Set bits */
 334         *Buffer |= Mask;
 335
 336         /* Update buffer and left bits */
 337         Buffer++;
 338         NumberToSet -= Bits;
 339     }
 340
 341     /* Set all full ULONGs */
 342     RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXULONG);
 343     Buffer += NumberToSet >> 5;
 344
 345     /* Set what's left */
 346     NumberToSet &= 31;
 347     Mask = MAXULONG << NumberToSet;
 348     *Buffer |= ~Mask;
 349 }
 350
 351 BOOLEAN
 352 NTAPI
 353 RtlTestBit(
 354     IN PRTL_BITMAP BitMapHeader,
 355     IN ULONG BitNumber)
 356 {
 357     ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
 358     return (BitMapHeader->Buffer[BitNumber >> 5] >> (BitNumber & 31)) & 1;
 359 }
 360
 361 BOOLEAN
 362 NTAPI
 363 RtlAreBitsClear(
 364     IN PRTL_BITMAP BitMapHeader,
 365     IN ULONG StartingIndex,
 366     IN ULONG Length)
 367 {
 368     return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
 369 }
 370
 371 BOOLEAN
 372 NTAPI
 373 RtlAreBitsSet(
 374     IN PRTL_BITMAP BitMapHeader,
 375     IN ULONG StartingIndex,
 376     IN ULONG Length)
 377 {
 378     return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
 379 }
 380
 381 ULONG
 382 NTAPI
 383 RtlNumberOfSetBits(
 384     IN PRTL_BITMAP BitMapHeader)
 385 {
 386     PUCHAR Byte, MaxByte;
 387     ULONG BitCount = 0;
 388
 389     Byte = (PUCHAR)BitMapHeader->Buffer;
 390     MaxByte = Byte + (BitMapHeader->SizeOfBitMap + 7) / 8;
 391
 392     do
 393     {
 394         BitCount += BitCountTable[*Byte++];
 395     }
 396     while (Byte <= MaxByte);
 397
 398     return BitCount;
 399 }
 400
 401 ULONG
 402 NTAPI
 403 RtlNumberOfClearBits(
 404     IN PRTL_BITMAP BitMapHeader)
 405 {
 406     /* Do some math */
 407     return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
 408 }
 409
 410 ULONG
 411 NTAPI
 412 RtlFindClearBits(
 413     IN PRTL_BITMAP BitMapHeader,
 414     IN ULONG NumberToFind,
 415     IN ULONG HintIndex)
 416 {
 417     ULONG CurrentBit, Margin, CurrentLength;
 418
 419     /* Check for valid parameters */
 420     if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
 421     {
 422         return MAXULONG;
 423     }
 424
 425     /* Check for trivial case */
 426     if (NumberToFind == 0)
 427     {
 428         return HintIndex;
 429     }
 430
 431     /* First margin is end of bitmap */
 432     Margin = BitMapHeader->SizeOfBitMap;
 433
 434 retry:
 435     /* Start with hint index, length is 0 */
 436     CurrentBit = HintIndex;
 437
 438     /* Loop until something is found or the end is reached */
 439     while (CurrentBit + NumberToFind < Margin)
 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     /* Did we start at a hint? */
 462     if (HintIndex)
 463     {
 464         /* Retry at the start */
 465         Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
 466         HintIndex = 0;
 467         goto retry;
 468     }
 469
 470     /* Nothing found */
 471     return MAXULONG;
 472 }
 473
 474 ULONG
 475 NTAPI
 476 RtlFindSetBits(
 477     IN PRTL_BITMAP BitMapHeader,
 478     IN ULONG NumberToFind,
 479     IN ULONG HintIndex)
 480 {
 481     ULONG CurrentBit, Margin, CurrentLength;
 482
 483     /* Check for valid parameters */
 484     if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
 485     {
 486         return MAXULONG;
 487     }
 488
 489     /* Check for trivial case */
 490     if (NumberToFind == 0)
 491     {
 492         return HintIndex;
 493     }
 494
 495     /* First margin is end of bitmap */
 496     Margin = BitMapHeader->SizeOfBitMap;
 497
 498 retry:
 499     /* Start with hint index, length is 0 */
 500     CurrentBit = HintIndex;
 501
 502     /* Loop until something is found or the end is reached */
 503     while (CurrentBit + NumberToFind <= Margin)
 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     /* Did we start at a hint? */
 526     if (HintIndex)
 527     {
 528         /* Retry at the start */
 529         Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
 530         HintIndex = 0;
 531         goto retry;
 532     }
 533
 534     /* Nothing found */
 535     return MAXULONG;
 536 }
 537
 538 ULONG
 539 NTAPI
 540 RtlFindClearBitsAndSet(
 541     PRTL_BITMAP BitMapHeader,
 542     ULONG NumberToFind,
 543     ULONG HintIndex)
 544 {
 545     ULONG Position;
 546
 547     /* Try to find clear bits */
 548     Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
 549
 550     /* Did we get something? */
 551     if (Position != MAXULONG)
 552     {
 553         /* Yes, set the bits */
 554         RtlSetBits(BitMapHeader, Position, NumberToFind);
 555     }
 556
 557     /* Return what we found */
 558     return Position;
 559 }
 560
 561 ULONG
 562 NTAPI
 563 RtlFindSetBitsAndClear(
 564     IN PRTL_BITMAP BitMapHeader,
 565     IN ULONG NumberToFind,
 566     IN ULONG HintIndex)
 567 {
 568     ULONG Position;
 569
 570     /* Try to find set bits */
 571     Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
 572
 573     /* Did we get something? */
 574     if (Position != MAXULONG)
 575     {
 576         /* Yes, clear the bits */
 577         RtlClearBits(BitMapHeader, Position, NumberToFind);
 578     }
 579
 580     /* Return what we found */
 581     return Position;
 582 }
 583
 584 ULONG
 585 NTAPI
 586 RtlFindNextForwardRunClear(
 587     IN PRTL_BITMAP BitMapHeader,
 588     IN ULONG FromIndex,
 589     IN PULONG StartingRunIndex)
 590 {
 591     ULONG Length;
 592
 593     /* Assume a set run first, count it's length */
 594     Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 595     *StartingRunIndex = FromIndex + Length;
 596
 597     /* Now return the length of the run */
 598     return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXULONG);
 599 }
 600
 601 ULONG
 602 NTAPI
 603 RtlFindNextForwardRunSet(
 604     IN PRTL_BITMAP BitMapHeader,
 605     IN ULONG FromIndex,
 606     IN PULONG StartingRunIndex)
 607 {
 608     ULONG Length;
 609
 610     /* Assume a clear run first, count it's length */
 611     Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXULONG);
 612     *StartingRunIndex = FromIndex + Length;
 613
 614     /* Now return the length of the run */
 615     return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXULONG);
 616 }
 617
 618 ULONG
 619 NTAPI
 620 RtlFindFirstRunClear(
 621     IN PRTL_BITMAP BitMapHeader,
 622     IN PULONG StartingIndex)
 623 {
 624     return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
 625 }
 626
 627 ULONG
 628 NTAPI
 629 RtlFindLastBackwardRunClear(
 630     IN PRTL_BITMAP BitMapHeader,
 631     IN ULONG FromIndex,
 632     IN PULONG StartingRunIndex)
 633 {
 634     UNIMPLEMENTED;
 635     return 0;
 636 }
 637
 638
 639 ULONG
 640 NTAPI
 641 RtlFindClearRuns(
 642     IN PRTL_BITMAP BitMapHeader,
 643     IN PRTL_BITMAP_RUN RunArray,
 644     IN ULONG SizeOfRunArray,
 645     IN BOOLEAN LocateLongestRuns)
 646 {
 647     ULONG StartingIndex, NumberOfBits, Run, FromIndex = 0, SmallestRun = 0;
 648
 649     /* Loop the runs */
 650     for (Run = 0; Run < SizeOfRunArray; Run++)
 651     {
 652         /* Look for a run */
 653         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 654                                                   FromIndex,
 655                                                   &StartingIndex);
 656
 657         /* Nothing more found? Quit looping. */
 658         if (NumberOfBits == 0) break;
 659
 660         /* Add another run */
 661         RunArray[Run].StartingIndex = StartingIndex;
 662         RunArray[Run].NumberOfBits = NumberOfBits;
 663
 664         /* Update smallest run */
 665         if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 666         {
 667             SmallestRun = Run;
 668         }
 669
 670         /* Advance bits */
 671         FromIndex = StartingIndex + NumberOfBits;
 672     }
 673
 674     /* Check if we are finished */
 675     if (Run < SizeOfRunArray || !LocateLongestRuns)
 676     {
 677         /* Return the number of found runs */
 678         return Run;
 679     }
 680
 681     while (1)
 682     {
 683         /* Look for a run */
 684         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 685                                                   FromIndex,
 686                                                   &StartingIndex);
 687
 688         /* Nothing more found? Quit looping. */
 689         if (NumberOfBits == 0) break;
 690
 691         /* Check if we have something to update */
 692         if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
 693         {
 694             /* Update smallest run */
 695             RunArray[SmallestRun].StartingIndex = StartingIndex;
 696             RunArray[SmallestRun].NumberOfBits = NumberOfBits;
 697
 698             /* Loop all runs */
 699             for (Run = 0; Run < SizeOfRunArray; Run++)
 700             {
 701                 /*Is this the new smallest run? */
 702                 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
 703                 {
 704                     /* Set it as new smallest run */
 705                     SmallestRun = Run;
 706                 }
 707             }
 708         }
 709
 710         /* Advance bits */
 711         FromIndex += NumberOfBits;
 712     }
 713
 714     return Run;
 715 }
 716
 717 ULONG
 718 NTAPI
 719 RtlFindLongestRunClear(
 720     IN PRTL_BITMAP BitMapHeader,
 721     IN PULONG StartingIndex)
 722 {
 723     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 724
 725     while (1)
 726     {
 727         /* Look for a run */
 728         NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
 729                                                   FromIndex,
 730                                                   &Index);
 731
 732         /* Nothing more found? Quit looping. */
 733         if (NumberOfBits == 0) break;
 734
 735         /* Was that the longest run? */
 736         if (NumberOfBits > MaxNumberOfBits)
 737         {
 738             /* Update values */
 739             MaxNumberOfBits = NumberOfBits;
 740             *StartingIndex = Index;
 741         }
 742
 743         /* Advance bits */
 744         FromIndex += NumberOfBits;
 745     }
 746
 747     return MaxNumberOfBits;
 748 }
 749
 750 ULONG
 751 NTAPI
 752 RtlFindLongestRunSet(
 753     IN PRTL_BITMAP BitMapHeader,
 754     IN PULONG StartingIndex)
 755 {
 756     ULONG NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
 757
 758     while (1)
 759     {
 760         /* Look for a run */
 761         NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
 762                                                 FromIndex,
 763                                                 &Index);
 764
 765         /* Nothing more found? Quit looping. */
 766         if (NumberOfBits == 0) break;
 767
 768         /* Was that the longest run? */
 769         if (NumberOfBits > MaxNumberOfBits)
 770         {
 771             /* Update values */
 772             MaxNumberOfBits = NumberOfBits;
 773             *StartingIndex = Index;
 774         }
 775
 776         /* Advance bits */
 777         FromIndex += NumberOfBits;
 778     }
 779
 780     return MaxNumberOfBits;
 781 }
 782