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 if (NumberToClear != 0) 366 { 367 Mask = MAXINDEX << NumberToClear; 368 *Buffer &= Mask; 369 } 370 } 371 372 VOID 373 NTAPI 374 RtlSetBits( 375 _In_ PRTL_BITMAP BitMapHeader, 376 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex, 377 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet) 378 { 379 BITMAP_INDEX Bits, Mask; 380 PBITMAP_BUFFER Buffer; 381 382 ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap); 383 384 /* Calculate buffer start and first bit index */ 385 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT]; 386 Bits = StartingIndex & (_BITCOUNT - 1); 387 388 /* Are we unaligned? */ 389 if (Bits) 390 { 391 /* Create a mask by shifting MAXINDEX */ 392 Mask = MAXINDEX << Bits; 393 394 /* This is what's left in the first ULONG */ 395 Bits = _BITCOUNT - Bits; 396 397 /* Even less bits to clear? */ 398 if (NumberToSet < Bits) 399 { 400 /* Calculate how many bits are left */ 401 Bits -= NumberToSet; 402 403 /* Fixup the mask on the high side */ 404 Mask = Mask << Bits >> Bits; 405 406 /* Set bits and return */ 407 *Buffer |= Mask; 408 return; 409 } 410 411 /* Set bits */ 412 *Buffer |= Mask; 413 414 /* Update buffer and left bits */ 415 Buffer++; 416 NumberToSet -= Bits; 417 } 418 419 /* Set all full ULONGs */ 420 RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXINDEX); 421 Buffer += NumberToSet / _BITCOUNT; 422 423 /* Set what's left */ 424 NumberToSet &= (_BITCOUNT - 1); 425 if (NumberToSet != 0) 426 { 427 Mask = MAXINDEX << NumberToSet; 428 *Buffer |= ~Mask; 429 } 430 } 431 432 BOOLEAN 433 NTAPI 434 RtlTestBit( 435 _In_ PRTL_BITMAP BitMapHeader, 436 _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber) 437 { 438 ASSERT(BitNumber < BitMapHeader->SizeOfBitMap); 439 return (BitMapHeader->Buffer[BitNumber / _BITCOUNT] >> (BitNumber & (_BITCOUNT - 1))) & 1; 440 } 441 442 BOOLEAN 443 NTAPI 444 RtlAreBitsClear( 445 _In_ PRTL_BITMAP BitMapHeader, 446 _In_ BITMAP_INDEX StartingIndex, 447 _In_ BITMAP_INDEX Length) 448 { 449 /* Verify parameters */ 450 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) || 451 (StartingIndex + Length <= StartingIndex)) 452 return FALSE; 453 454 return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length; 455 } 456 457 BOOLEAN 458 NTAPI 459 RtlAreBitsSet( 460 _In_ PRTL_BITMAP BitMapHeader, 461 _In_ BITMAP_INDEX StartingIndex, 462 _In_ BITMAP_INDEX Length) 463 { 464 /* Verify parameters */ 465 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) || 466 (StartingIndex + Length <= StartingIndex)) 467 return FALSE; 468 469 return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length; 470 } 471 472 BITMAP_INDEX 473 NTAPI 474 RtlNumberOfSetBits( 475 _In_ PRTL_BITMAP BitMapHeader) 476 { 477 PUCHAR Byte, MaxByte; 478 BITMAP_INDEX BitCount = 0; 479 ULONG Shift; 480 481 Byte = (PUCHAR)BitMapHeader->Buffer; 482 MaxByte = Byte + BitMapHeader->SizeOfBitMap / 8; 483 484 while (Byte < MaxByte) 485 { 486 BitCount += BitCountTable[*Byte++]; 487 } 488 489 if (BitMapHeader->SizeOfBitMap & 7) 490 { 491 Shift = 8 - (BitMapHeader->SizeOfBitMap & 7); 492 BitCount += BitCountTable[((*Byte) << Shift) & 0xFF]; 493 } 494 495 return BitCount; 496 } 497 498 BITMAP_INDEX 499 NTAPI 500 RtlNumberOfClearBits( 501 _In_ PRTL_BITMAP BitMapHeader) 502 { 503 /* Do some math */ 504 return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader); 505 } 506 507 BITMAP_INDEX 508 NTAPI 509 RtlFindClearBits( 510 _In_ PRTL_BITMAP BitMapHeader, 511 _In_ BITMAP_INDEX NumberToFind, 512 _In_ BITMAP_INDEX HintIndex) 513 { 514 BITMAP_INDEX CurrentBit, Margin, CurrentLength; 515 516 /* Check for valid parameters */ 517 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap) 518 { 519 return MAXINDEX; 520 } 521 522 /* Check if the hint is outside the bitmap */ 523 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0; 524 525 /* Check for trivial case */ 526 if (NumberToFind == 0) 527 { 528 /* Return hint rounded down to byte margin */ 529 return HintIndex & ~7; 530 } 531 532 /* First margin is end of bitmap */ 533 Margin = BitMapHeader->SizeOfBitMap; 534 535 retry: 536 /* Start with hint index, length is 0 */ 537 CurrentBit = HintIndex; 538 539 /* Loop until something is found or the end is reached */ 540 while (CurrentBit + NumberToFind < Margin) 541 { 542 /* Search for the next clear run, by skipping a set run */ 543 CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader, 544 CurrentBit, 545 MAXINDEX); 546 547 /* Get length of the clear bit run */ 548 CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader, 549 CurrentBit, 550 NumberToFind); 551 552 /* Is this long enough? */ 553 if (CurrentLength >= NumberToFind) 554 { 555 /* It is */ 556 return CurrentBit; 557 } 558 559 CurrentBit += CurrentLength; 560 } 561 562 /* Did we start at a hint? */ 563 if (HintIndex) 564 { 565 /* Retry at the start */ 566 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap); 567 HintIndex = 0; 568 goto retry; 569 } 570 571 /* Nothing found */ 572 return MAXINDEX; 573 } 574 575 BITMAP_INDEX 576 NTAPI 577 RtlFindSetBits( 578 _In_ PRTL_BITMAP BitMapHeader, 579 _In_ BITMAP_INDEX NumberToFind, 580 _In_ BITMAP_INDEX HintIndex) 581 { 582 BITMAP_INDEX CurrentBit, Margin, CurrentLength; 583 584 /* Check for valid parameters */ 585 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap) 586 { 587 return MAXINDEX; 588 } 589 590 /* Check if the hint is outside the bitmap */ 591 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0; 592 593 /* Check for trivial case */ 594 if (NumberToFind == 0) 595 { 596 /* Return hint rounded down to byte margin */ 597 return HintIndex & ~7; 598 } 599 600 /* First margin is end of bitmap */ 601 Margin = BitMapHeader->SizeOfBitMap; 602 603 retry: 604 /* Start with hint index, length is 0 */ 605 CurrentBit = HintIndex; 606 607 /* Loop until something is found or the end is reached */ 608 while (CurrentBit + NumberToFind <= Margin) 609 { 610 /* Search for the next set run, by skipping a clear run */ 611 CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader, 612 CurrentBit, 613 MAXINDEX); 614 615 /* Get length of the set bit run */ 616 CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader, 617 CurrentBit, 618 NumberToFind); 619 620 /* Is this long enough? */ 621 if (CurrentLength >= NumberToFind) 622 { 623 /* It is */ 624 return CurrentBit; 625 } 626 627 CurrentBit += CurrentLength; 628 } 629 630 /* Did we start at a hint? */ 631 if (HintIndex) 632 { 633 /* Retry at the start */ 634 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap); 635 HintIndex = 0; 636 goto retry; 637 } 638 639 /* Nothing found */ 640 return MAXINDEX; 641 } 642 643 BITMAP_INDEX 644 NTAPI 645 RtlFindClearBitsAndSet( 646 _In_ PRTL_BITMAP BitMapHeader, 647 _In_ BITMAP_INDEX NumberToFind, 648 _In_ BITMAP_INDEX HintIndex) 649 { 650 BITMAP_INDEX Position; 651 652 /* Try to find clear bits */ 653 Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex); 654 655 /* Did we get something? */ 656 if (Position != MAXINDEX) 657 { 658 /* Yes, set the bits */ 659 RtlSetBits(BitMapHeader, Position, NumberToFind); 660 } 661 662 /* Return what we found */ 663 return Position; 664 } 665 666 BITMAP_INDEX 667 NTAPI 668 RtlFindSetBitsAndClear( 669 _In_ PRTL_BITMAP BitMapHeader, 670 _In_ BITMAP_INDEX NumberToFind, 671 _In_ BITMAP_INDEX HintIndex) 672 { 673 BITMAP_INDEX Position; 674 675 /* Try to find set bits */ 676 Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex); 677 678 /* Did we get something? */ 679 if (Position != MAXINDEX) 680 { 681 /* Yes, clear the bits */ 682 RtlClearBits(BitMapHeader, Position, NumberToFind); 683 } 684 685 /* Return what we found */ 686 return Position; 687 } 688 689 BITMAP_INDEX 690 NTAPI 691 RtlFindNextForwardRunClear( 692 _In_ PRTL_BITMAP BitMapHeader, 693 _In_ BITMAP_INDEX FromIndex, 694 _Out_ PBITMAP_INDEX StartingRunIndex) 695 { 696 BITMAP_INDEX Length; 697 698 /* Check for buffer overrun */ 699 if (FromIndex >= BitMapHeader->SizeOfBitMap) 700 { 701 *StartingRunIndex = FromIndex; 702 return 0; 703 } 704 705 /* Assume a set run first, count it's length */ 706 Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXINDEX); 707 *StartingRunIndex = FromIndex + Length; 708 709 /* Now return the length of the run */ 710 return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXINDEX); 711 } 712 713 BITMAP_INDEX 714 NTAPI 715 RtlFindNextForwardRunSet( 716 _In_ PRTL_BITMAP BitMapHeader, 717 _In_ BITMAP_INDEX FromIndex, 718 _Out_ PBITMAP_INDEX StartingRunIndex) 719 { 720 BITMAP_INDEX Length; 721 722 /* Check for buffer overrun */ 723 if (FromIndex >= BitMapHeader->SizeOfBitMap) 724 { 725 *StartingRunIndex = FromIndex; 726 return 0; 727 } 728 729 /* Assume a clear run first, count it's length */ 730 Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXINDEX); 731 *StartingRunIndex = FromIndex + Length; 732 733 /* Now return the length of the run */ 734 return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex + Length, MAXINDEX); 735 } 736 737 BITMAP_INDEX 738 NTAPI 739 RtlFindFirstRunClear( 740 _In_ PRTL_BITMAP BitMapHeader, 741 _Out_ PBITMAP_INDEX StartingIndex) 742 { 743 return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex); 744 } 745 746 BITMAP_INDEX 747 NTAPI 748 RtlFindLastBackwardRunClear( 749 _In_ PRTL_BITMAP BitMapHeader, 750 _In_ BITMAP_INDEX FromIndex, 751 _Out_ PBITMAP_INDEX StartingRunIndex) 752 { 753 BITMAP_INDEX Value, InvValue, BitPos; 754 PBITMAP_BUFFER Buffer; 755 756 /* Make sure we don't go past the end */ 757 FromIndex = min(FromIndex, BitMapHeader->SizeOfBitMap - 1); 758 759 /* Calculate positions */ 760 Buffer = BitMapHeader->Buffer + FromIndex / _BITCOUNT; 761 BitPos = (_BITCOUNT - 1) - (FromIndex & (_BITCOUNT - 1)); 762 763 /* Get the inversed value, clear bits that don't belong to the run */ 764 InvValue = ~(*Buffer--) << BitPos >> BitPos; 765 766 /* Skip all set ULONGs */ 767 while (InvValue == 0) 768 { 769 /* Did we already reach past the first ULONG? */ 770 if (Buffer < BitMapHeader->Buffer) 771 { 772 /* Yes, nothing found */ 773 return 0; 774 } 775 776 InvValue = ~(*Buffer--); 777 } 778 779 /* We hit a clear bit, check how many set bits are left */ 780 BitScanReverse(&BitPos, InvValue); 781 782 /* Calculate last bit position */ 783 FromIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos); 784 785 Value = ~InvValue << ((_BITCOUNT - 1) - BitPos) >> ((_BITCOUNT - 1) - BitPos); 786 787 /* Skip all clear ULONGs */ 788 while (Value == 0 && Buffer >= BitMapHeader->Buffer) 789 { 790 Value = *Buffer--; 791 } 792 793 if (Value != 0) 794 { 795 /* We hit a set bit, check how many clear bits are left */ 796 BitScanReverse(&BitPos, Value); 797 798 /* Calculate Starting Index */ 799 *StartingRunIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos + 1); 800 } 801 else 802 { 803 /* We reached the start of the bitmap */ 804 *StartingRunIndex = 0; 805 } 806 807 /* Return length of the run */ 808 return (FromIndex - *StartingRunIndex); 809 } 810 811 812 ULONG 813 NTAPI 814 RtlFindClearRuns( 815 _In_ PRTL_BITMAP BitMapHeader, 816 _In_ PRTL_BITMAP_RUN RunArray, 817 _In_ ULONG SizeOfRunArray, 818 _In_ BOOLEAN LocateLongestRuns) 819 { 820 BITMAP_INDEX StartingIndex, NumberOfBits, FromIndex = 0, SmallestRun = 0; 821 ULONG Run; 822 823 /* Loop the runs */ 824 for (Run = 0; Run < SizeOfRunArray; Run++) 825 { 826 /* Look for a run */ 827 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 828 FromIndex, 829 &StartingIndex); 830 831 /* Nothing more found? Quit looping. */ 832 if (NumberOfBits == 0) break; 833 834 /* Add another run */ 835 RunArray[Run].StartingIndex = StartingIndex; 836 RunArray[Run].NumberOfBits = NumberOfBits; 837 838 /* Update smallest run */ 839 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits) 840 { 841 SmallestRun = Run; 842 } 843 844 /* Advance bits */ 845 FromIndex = StartingIndex + NumberOfBits; 846 } 847 848 /* Check if we are finished */ 849 if (Run < SizeOfRunArray || !LocateLongestRuns) 850 { 851 /* Return the number of found runs */ 852 return Run; 853 } 854 855 while (1) 856 { 857 /* Look for a run */ 858 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 859 FromIndex, 860 &StartingIndex); 861 862 /* Nothing more found? Quit looping. */ 863 if (NumberOfBits == 0) break; 864 865 /* Check if we have something to update */ 866 if (NumberOfBits > RunArray[SmallestRun].NumberOfBits) 867 { 868 /* Update smallest run */ 869 RunArray[SmallestRun].StartingIndex = StartingIndex; 870 RunArray[SmallestRun].NumberOfBits = NumberOfBits; 871 872 /* Loop all runs */ 873 for (Run = 0; Run < SizeOfRunArray; Run++) 874 { 875 /*Is this the new smallest run? */ 876 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits) 877 { 878 /* Set it as new smallest run */ 879 SmallestRun = Run; 880 } 881 } 882 } 883 884 /* Advance bits */ 885 FromIndex += NumberOfBits; 886 } 887 888 return Run; 889 } 890 891 BITMAP_INDEX 892 NTAPI 893 RtlFindLongestRunClear( 894 IN PRTL_BITMAP BitMapHeader, 895 IN PBITMAP_INDEX StartingIndex) 896 { 897 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0; 898 899 while (1) 900 { 901 /* Look for a run */ 902 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader, 903 FromIndex, 904 &Index); 905 906 /* Nothing more found? Quit looping. */ 907 if (NumberOfBits == 0) break; 908 909 /* Was that the longest run? */ 910 if (NumberOfBits > MaxNumberOfBits) 911 { 912 /* Update values */ 913 MaxNumberOfBits = NumberOfBits; 914 *StartingIndex = Index; 915 } 916 917 /* Advance bits */ 918 FromIndex += NumberOfBits; 919 } 920 921 return MaxNumberOfBits; 922 } 923 924 BITMAP_INDEX 925 NTAPI 926 RtlFindLongestRunSet( 927 IN PRTL_BITMAP BitMapHeader, 928 IN PBITMAP_INDEX StartingIndex) 929 { 930 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0; 931 932 while (1) 933 { 934 /* Look for a run */ 935 NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader, 936 FromIndex, 937 &Index); 938 939 /* Nothing more found? Quit looping. */ 940 if (NumberOfBits == 0) break; 941 942 /* Was that the longest run? */ 943 if (NumberOfBits > MaxNumberOfBits) 944 { 945 /* Update values */ 946 MaxNumberOfBits = NumberOfBits; 947 *StartingIndex = Index; 948 } 949 950 /* Advance bits */ 951 FromIndex += NumberOfBits; 952 } 953 954 return MaxNumberOfBits; 955 } 956 957