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