lib/rtl/bitmap.c

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