reactos/lib/rtl/bitmap.c

   1 /* COPYRIGHT:       See COPYING in the top level directory
   2  * PROJECT:         ReactOS system libraries
   3  * FILE:            lib/rtl/bitmap.c
   4  * PURPOSE:         Bitmap functions
   5  * PROGRAMMER:      Eric Kohl
   6  */
   7
   8 /* INCLUDES *****************************************************************/
   9
  10 #include <rtl.h>
  11
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15
  16 /* MACROS *******************************************************************/
  17
  18 #define MASK(Count, Shift) \
  19   ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift))
  20
  21
  22 /* FUNCTIONS ****************************************************************/
  23
  24 /*
  25  * @implemented
  26  */
  27 VOID NTAPI
  28 RtlInitializeBitMap(PRTL_BITMAP BitMapHeader,
  29                     PULONG BitMapBuffer,
  30                     ULONG SizeOfBitMap)
  31 {
  32   BitMapHeader->SizeOfBitMap = SizeOfBitMap;
  33   BitMapHeader->Buffer = BitMapBuffer;
  34 }
  35
  36
  37 /*
  38  * @implemented
  39  */
  40 BOOLEAN NTAPI
  41 RtlAreBitsClear(PRTL_BITMAP BitMapHeader,
  42                 ULONG StartingIndex,
  43                 ULONG Length)
  44 {
  45   ULONG Size;
  46   ULONG Shift;
  47   ULONG Count;
  48   PULONG Ptr;
  49
  50   Size = BitMapHeader->SizeOfBitMap;
  51   if (StartingIndex >= Size ||
  52       !Length ||
  53       (StartingIndex + Length > Size))
  54      return FALSE;
  55
  56   Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
  57   while (Length)
  58   {
  59     /* Get bit shift in current ulong */
  60     Shift = StartingIndex & 0x1F;
  61
  62     /* Get number of bits to check in current ulong */
  63     Count = (Length > 32 - Shift) ? 32 - Shift : Length;
  64
  65     /* Check ulong */
  66     if (*Ptr++ & MASK(Count, Shift))
  67       return FALSE;
  68
  69     Length -= Count;
  70     StartingIndex += Count;
  71   }
  72
  73   return TRUE;
  74 }
  75
  76
  77 /*
  78  * @implemented
  79  */
  80 BOOLEAN NTAPI
  81 RtlAreBitsSet(PRTL_BITMAP BitMapHeader,
  82               ULONG StartingIndex,
  83               ULONG Length)
  84 {
  85   ULONG Size;
  86   ULONG Shift;
  87   ULONG Count;
  88   PULONG Ptr;
  89
  90   Size = BitMapHeader->SizeOfBitMap;
  91   if (StartingIndex >= Size ||
  92       Length == 0 ||
  93       (StartingIndex + Length > Size))
  94     return FALSE;
  95
  96   Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
  97   while (Length)
  98   {
  99     /* Get bit shift in current ulong */
 100     Shift = StartingIndex & 0x1F;
 101
 102     /* Get number of bits to check in current ulong */
 103     Count = (Length > 32 - Shift) ? 32 - Shift : Length;
 104
 105     /* Check ulong */
 106     if (~*Ptr++ & MASK(Count, Shift))
 107       return FALSE;
 108
 109     Length -= Count;
 110     StartingIndex += Count;
 111   }
 112
 113   return TRUE;
 114 }
 115
 116
 117 /*
 118  * @implemented
 119  *
 120  * Note: According to the documentation, SizeOfBitmap is in bits, so the
 121  * ROUND_UP(...) must be divided by the number of bits per byte here.
 122  * This function is exercised by the whole page allocator in npool.c
 123  * which is how i came across this error.
 124  */
 125 VOID NTAPI
 126 RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
 127 {
 128    if (BitMapHeader != NULL)
 129    {
 130      if (BitMapHeader->Buffer != NULL)
 131      {
 132         memset(BitMapHeader->Buffer,
 133                    0x00,
 134                    ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8);
 135      }
 136    }
 137 }
 138
 139
 140 /*
 141  * @implemented
 142  */
 143 VOID NTAPI
 144 RtlClearBit(PRTL_BITMAP BitMapHeader,
 145             ULONG BitNumber)
 146 {
 147   PULONG Ptr;
 148
 149   if (BitNumber >= BitMapHeader->SizeOfBitMap)
 150     return;
 151
 152   Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 153
 154   *Ptr &= ~(1 << (BitNumber % 32));
 155 }
 156
 157
 158 /*
 159  * @implemented
 160  */
 161 VOID NTAPI
 162 RtlClearBits(PRTL_BITMAP BitMapHeader,
 163              ULONG StartingIndex,
 164              ULONG NumberToClear)
 165 {
 166   ULONG Size;
 167   ULONG Count;
 168   ULONG Shift;
 169   PULONG Ptr;
 170
 171   Size = BitMapHeader->SizeOfBitMap;
 172   if (StartingIndex >= Size || NumberToClear == 0)
 173     return;
 174
 175   ASSERT(StartingIndex + NumberToClear <= Size);
 176
 177   Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
 178   while (NumberToClear)
 179   {
 180     /* Bit shift in current ulong */
 181     Shift = StartingIndex & 0x1F;
 182
 183     /* Number of bits to change in current ulong */
 184     Count = (NumberToClear > 32 - Shift ) ? 32 - Shift : NumberToClear;
 185
 186     /* Adjust ulong */
 187     *Ptr++ &= ~MASK(Count, Shift);
 188     NumberToClear -= Count;
 189     StartingIndex += Count;
 190   }
 191 }
 192
 193
 194 /*
 195  * @implemented
 196  */
 197 ULONG NTAPI
 198 RtlFindClearBits(PRTL_BITMAP BitMapHeader,
 199                  ULONG NumberToFind,
 200                  ULONG HintIndex)
 201 {
 202   ULONG Size;
 203   ULONG Index;
 204   ULONG Count;
 205   PULONG Ptr;
 206   ULONG Mask;
 207   ULONG Loop;
 208   ULONG End;
 209   ULONG OriginalHint = HintIndex;
 210
 211   Size = BitMapHeader->SizeOfBitMap;
 212   if (NumberToFind > Size || NumberToFind == 0)
 213     return -1;
 214
 215   if (HintIndex >= Size)
 216     HintIndex = 0;
 217
 218   /* Initialize the values to the hint location. */
 219   Index = HintIndex;
 220   Ptr = BitMapHeader->Buffer + (Index / 32);
 221   Mask = 1 << (Index & 0x1F);
 222   End = Size;
 223
 224   /* The outer loop does the magic of first searching from the
 225    * hint to the bitmap end and then going again from beginning
 226    * of the bitmap to the hint location.
 227    */
 228   for (Loop = 0; Loop < 2; Loop++)
 229   {
 230     while (HintIndex < End)
 231     {
 232       /* Count clear bits */
 233       for (Count = 0; Index < End && ~*Ptr & Mask; Index++)
 234       {
 235         if (++Count >= NumberToFind)
 236           return HintIndex;
 237
 238         Mask <<= 1;
 239
 240         if (Mask == 0)
 241         {
 242           Mask = 1;
 243           Ptr++;
 244         }
 245       }
 246
 247       /* Skip set bits */
 248       for (; Index < End && *Ptr & Mask; Index++)
 249       {
 250         Mask <<= 1;
 251
 252         if (Mask == 0)
 253         {
 254           Mask = 1;
 255           Ptr++;
 256         }
 257       }
 258       HintIndex = Index;
 259     }
 260
 261     /* Optimalization */
 262     if (OriginalHint == 0)
 263       break;
 264
 265     /* Initialize the values for the beginning -> hint loop. */
 266     HintIndex = Index = 0;
 267     End = OriginalHint + NumberToFind - 1;
 268     End = End > Size ? Size : End;
 269     Ptr = BitMapHeader->Buffer;
 270     Mask = 1;
 271   }
 272
 273   return (ULONG)-1;
 274 }
 275
 276
 277 /*
 278  * @implemented
 279  */
 280 ULONG NTAPI
 281 RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
 282                        ULONG NumberToFind,
 283                        ULONG HintIndex)
 284 {
 285   ULONG Index;
 286
 287   Index = RtlFindClearBits(BitMapHeader,
 288                            NumberToFind,
 289                            HintIndex);
 290   if (Index != (ULONG)-1)
 291   {
 292     RtlSetBits(BitMapHeader,
 293                Index,
 294                NumberToFind);
 295   }
 296
 297   return Index;
 298 }
 299
 300
 301 /*
 302  * @implemented
 303  */
 304 ULONG NTAPI
 305 RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
 306                      PULONG StartingIndex)
 307 {
 308   ULONG Size;
 309   ULONG Index;
 310   ULONG Count;
 311   PULONG Ptr;
 312   ULONG Mask;
 313
 314   Size = BitMapHeader->SizeOfBitMap;
 315   if (*StartingIndex > Size)
 316   {
 317     *StartingIndex = (ULONG)-1;
 318     return 0;
 319   }
 320
 321   Index = *StartingIndex;
 322   Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 323   Mask = 1 << (Index & 0x1F);
 324
 325   /* Skip set bits */
 326   for (; Index < Size && *Ptr & Mask; Index++)
 327   {
 328     Mask <<= 1;
 329
 330     if (Mask == 0)
 331     {
 332       Mask = 1;
 333       Ptr++;
 334     }
 335   }
 336
 337   /* Return index of first clear bit */
 338   if (Index >= Size)
 339   {
 340     *StartingIndex = (ULONG)-1;
 341     return 0;
 342   }
 343   else
 344   {
 345     *StartingIndex = Index;
 346   }
 347
 348   /* Count clear bits */
 349   for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 350   {
 351     Count++;
 352     Mask <<= 1;
 353
 354     if (Mask == 0)
 355     {
 356       Mask = 1;
 357       Ptr++;
 358     }
 359   }
 360
 361   return Count;
 362 }
 363
 364
 365 /*
 366  * @unimplemented
 367  */
 368 ULONG NTAPI
 369 RtlFindClearRuns(PRTL_BITMAP BitMapHeader,
 370                  PRTL_BITMAP_RUN RunArray,
 371                  ULONG SizeOfRunArray,
 372                  BOOLEAN LocateLongestRuns)
 373 {
 374   UNIMPLEMENTED;
 375   return 0;
 376 }
 377
 378
 379 /*
 380  * @unimplemented
 381  */
 382 ULONG NTAPI
 383 RtlFindLastBackwardRunClear(IN PRTL_BITMAP BitMapHeader,
 384                             IN ULONG FromIndex,
 385                             IN PULONG StartingRunIndex)
 386 {
 387   UNIMPLEMENTED;
 388   return 0;
 389 }
 390
 391
 392 /*
 393  * @unimplemented
 394  */
 395 ULONG NTAPI
 396 RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
 397                            IN ULONG FromIndex,
 398                            IN PULONG StartingRunIndex)
 399 {
 400   UNIMPLEMENTED;
 401   return 0;
 402 }
 403
 404
 405 /*
 406  * @implemented
 407  */
 408 ULONG NTAPI
 409 RtlFindFirstRunSet(IN PRTL_BITMAP BitMapHeader,
 410                    IN PULONG StartingIndex)
 411 {
 412   ULONG Size;
 413   ULONG Index;
 414   ULONG Count;
 415   PULONG Ptr;
 416   ULONG  Mask;
 417
 418   Size = BitMapHeader->SizeOfBitMap;
 419   if (*StartingIndex > Size)
 420   {
 421     *StartingIndex = (ULONG)-1;
 422     return 0;
 423   }
 424
 425   Index = *StartingIndex;
 426   Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 427   Mask = 1 << (Index & 0x1F);
 428
 429   /* Skip clear bits */
 430   for (; Index < Size && ~*Ptr & Mask; Index++)
 431   {
 432     Mask <<= 1;
 433
 434     if (Mask == 0)
 435     {
 436       Mask = 1;
 437       Ptr++;
 438     }
 439   }
 440
 441   /* Return index of first set bit */
 442   if (Index >= Size)
 443   {
 444     *StartingIndex = (ULONG)-1;
 445     return 0;
 446   }
 447   else
 448   {
 449     *StartingIndex = Index;
 450   }
 451
 452   /* Count set bits */
 453   for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 454   {
 455     Count++;
 456     Mask <<= 1;
 457
 458     if (Mask == 0)
 459     {
 460       Mask = 1;
 461       Ptr++;
 462     }
 463   }
 464
 465   return Count;
 466 }
 467
 468
 469 /*
 470  * @implemented
 471  */
 472 ULONG NTAPI
 473 RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
 474                        PULONG StartingIndex)
 475 {
 476   ULONG Size;
 477   PULONG Ptr;
 478   ULONG Index = 0;
 479   ULONG Count;
 480   ULONG Max = 0;
 481   ULONG Start;
 482   ULONG Maxstart = 0;
 483   ULONG  Mask = 1;
 484
 485   Size = BitMapHeader->SizeOfBitMap;
 486   Ptr = (PULONG)BitMapHeader->Buffer;
 487
 488   while (Index < Size)
 489   {
 490     Start = Index;
 491
 492     /* Count clear bits */
 493     for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 494     {
 495       Count++;
 496       Mask <<= 1;
 497
 498       if (Mask == 0)
 499       {
 500         Mask = 1;
 501         Ptr++;
 502       }
 503     }
 504
 505     /* Skip set bits */
 506     for (; Index < Size && *Ptr & Mask; Index++)
 507     {
 508       Mask <<= 1;
 509
 510       if (Mask == 0)
 511       {
 512         Mask = 1;
 513         Ptr++;
 514       }
 515     }
 516
 517     if (Count > Max)
 518     {
 519       Max = Count;
 520       Maxstart = Start;
 521     }
 522   }
 523
 524   if (StartingIndex != NULL)
 525   {
 526     *StartingIndex = Maxstart;
 527   }
 528
 529   return Max;
 530 }
 531
 532
 533 /*
 534  * @implemented
 535  */
 536 ULONG NTAPI
 537 RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
 538                      PULONG StartingIndex)
 539 {
 540   ULONG Size;
 541   PULONG Ptr;
 542   ULONG Index = 0;
 543   ULONG Count;
 544   ULONG Max = 0;
 545   ULONG Start;
 546   ULONG Maxstart = 0;
 547   ULONG Mask = 1;
 548
 549   Size = BitMapHeader->SizeOfBitMap;
 550   Ptr = (PULONG)BitMapHeader->Buffer;
 551
 552   while (Index < Size)
 553   {
 554     Start = Index;
 555
 556     /* Count set bits */
 557     for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 558     {
 559       Count++;
 560       Mask <<= 1;
 561
 562       if (Mask == 0)
 563       {
 564         Mask = 1;
 565         Ptr++;
 566       }
 567     }
 568
 569     /* Skip clear bits */
 570     for (; Index < Size && ~*Ptr & Mask; Index++)
 571     {
 572       Mask <<= 1;
 573
 574       if (Mask == 0)
 575       {
 576         Mask = 1;
 577         Ptr++;
 578       }
 579     }
 580
 581     if (Count > Max)
 582     {
 583       Max = Count;
 584       Maxstart = Start;
 585     }
 586   }
 587
 588   if (StartingIndex != NULL)
 589   {
 590     *StartingIndex = Maxstart;
 591   }
 592
 593   return Max;
 594 }
 595
 596
 597 /*
 598  * @implemented
 599  */
 600 ULONG NTAPI
 601 RtlFindSetBits(PRTL_BITMAP BitMapHeader,
 602                ULONG NumberToFind,
 603                ULONG HintIndex)
 604 {
 605   ULONG Size;
 606   ULONG Index;
 607   ULONG Count;
 608   PULONG Ptr;
 609   ULONG Mask;
 610   ULONG Loop;
 611   ULONG End;
 612   ULONG OriginalHint = HintIndex;
 613
 614   Size = BitMapHeader->SizeOfBitMap;
 615   if (NumberToFind > Size || NumberToFind == 0)
 616     return (ULONG)-1;
 617
 618   if (HintIndex >= Size)
 619     HintIndex = 0;
 620
 621   /* Initialize the values to the hint location. */
 622   Index = HintIndex;
 623   Ptr = BitMapHeader->Buffer + (Index / 32);
 624   Mask = 1 << (Index & 0x1F);
 625   End = Size;
 626
 627   /* The outer loop does the magic of first searching from the
 628    * hint to the bitmap end and then going again from beginning
 629    * of the bitmap to the hint location.
 630    */
 631   for (Loop = 0; Loop < 2; Loop++)
 632   {
 633     while (HintIndex < End)
 634     {
 635       /* Count set bits */
 636       for (Count = 0; Index < End && *Ptr & Mask; Index++)
 637       {
 638         if (++Count >= NumberToFind)
 639           return HintIndex;
 640
 641         Mask <<= 1;
 642
 643         if (Mask == 0)
 644         {
 645           Mask = 1;
 646           Ptr++;
 647         }
 648       }
 649
 650       /* Skip clear bits */
 651       for (; Index < End && ~*Ptr & Mask; Index++)
 652       {
 653         Mask <<= 1;
 654
 655         if (Mask == 0)
 656         {
 657           Mask = 1;
 658           Ptr++;
 659         }
 660       }
 661
 662       HintIndex = Index;
 663     }
 664
 665     /* Optimalization */
 666     if (OriginalHint == 0)
 667       break;
 668
 669     /* Initialize the values for the beginning -> hint loop. */
 670     HintIndex = Index = 0;
 671     End = OriginalHint + NumberToFind - 1;
 672     End = End > Size ? Size : End;
 673     Ptr = BitMapHeader->Buffer;
 674     Mask = 1;
 675   }
 676
 677   return (ULONG)-1;
 678 }
 679
 680
 681 /*
 682  * @implemented
 683  */
 684 ULONG NTAPI
 685 RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
 686                        ULONG NumberToFind,
 687                        ULONG HintIndex)
 688 {
 689   ULONG Index;
 690
 691   Index = RtlFindSetBits(BitMapHeader,
 692                          NumberToFind,
 693                          HintIndex);
 694   if (Index != (ULONG)-1)
 695   {
 696     RtlClearBits(BitMapHeader,
 697                  Index,
 698                  NumberToFind);
 699   }
 700
 701   return Index;
 702 }
 703
 704
 705 /*
 706  * @implemented
 707  */
 708 ULONG NTAPI
 709 RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
 710 {
 711   PULONG Ptr;
 712   ULONG Size;
 713   ULONG Index;
 714   ULONG Count;
 715   ULONG Mask;
 716
 717   Size = BitMapHeader->SizeOfBitMap;
 718   Ptr = (PULONG)BitMapHeader->Buffer;
 719
 720   for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 721   {
 722     if (~*Ptr & Mask)
 723       Count++;
 724
 725     Mask <<= 1;
 726     if (Mask == 0)
 727     {
 728       Mask = 1;
 729       Ptr++;
 730     }
 731   }
 732
 733   return Count;
 734 }
 735
 736
 737 /*
 738  * @implemented
 739  */
 740 ULONG NTAPI
 741 RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
 742 {
 743   PULONG Ptr;
 744   ULONG Size;
 745   ULONG Index;
 746   ULONG Count;
 747   ULONG Mask;
 748
 749   Ptr = (PULONG)BitMapHeader->Buffer;
 750   Size = BitMapHeader->SizeOfBitMap;
 751   for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 752   {
 753     if (*Ptr & Mask)
 754       Count++;
 755
 756     Mask <<= 1;
 757
 758     if (Mask == 0)
 759     {
 760       Mask = 1;
 761       Ptr++;
 762     }
 763   }
 764
 765   return Count;
 766 }
 767
 768
 769 /*
 770  * @implemented
 771  *
 772  * Note: According to the documentation, SizeOfBitmap is in bits, so the
 773  * ROUND_UP(...) must be divided by the number of bits per byte here.
 774  * The companion function, RtlClearAllBits, is exercised by the whole page
 775  * allocator in npool.c which is how i came across this error.
 776  */
 777 VOID NTAPI
 778 RtlSetAllBits(IN OUT PRTL_BITMAP BitMapHeader)
 779 {
 780   memset(BitMapHeader->Buffer,
 781          0xFF,
 782          ROUND_UP(BitMapHeader->SizeOfBitMap, 8) / 8);
 783 }
 784
 785
 786 /*
 787  * @implemented
 788  */
 789 VOID NTAPI
 790 RtlSetBit(PRTL_BITMAP BitMapHeader,
 791           ULONG BitNumber)
 792 {
 793   PULONG Ptr;
 794
 795   if (BitNumber >= BitMapHeader->SizeOfBitMap)
 796     return;
 797
 798   Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 799
 800   *Ptr |= (1 << (BitNumber % 32));
 801 }
 802
 803
 804 /*
 805  * @implemented
 806  */
 807 VOID NTAPI
 808 RtlSetBits(PRTL_BITMAP BitMapHeader,
 809            ULONG StartingIndex,
 810            ULONG NumberToSet)
 811 {
 812   ULONG Size;
 813   ULONG Count;
 814   ULONG Shift;
 815   PULONG Ptr;
 816
 817   Size = BitMapHeader->SizeOfBitMap;
 818   if (StartingIndex >= Size || NumberToSet == 0)
 819     return;
 820
 821   ASSERT(StartingIndex + NumberToSet <= Size);
 822
 823   Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
 824   while (NumberToSet)
 825   {
 826     /* Bit shift in current ulong */
 827     Shift = StartingIndex & 0x1F;
 828
 829     /* Number of bits to change in current ulong */
 830     Count = (NumberToSet > 32 - Shift) ? 32 - Shift : NumberToSet;
 831
 832     /* Adjust ulong */
 833     *Ptr++ |= MASK(Count, Shift);
 834     NumberToSet -= Count;
 835     StartingIndex += Count;
 836   }
 837 }
 838
 839
 840 /*
 841  * @implemented
 842  */
 843 BOOLEAN NTAPI
 844 RtlTestBit(PRTL_BITMAP BitMapHeader,
 845            ULONG BitNumber)
 846 {
 847   PULONG Ptr;
 848
 849   if (BitNumber >= BitMapHeader->SizeOfBitMap)
 850     return FALSE;
 851
 852   Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 853
 854   return (*Ptr & (1 << (BitNumber % 32)));
 855 }
 856
 857 /* EOF */