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