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