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