ntoskrnl/rtl/bitmap.c

   1 /* $Id$
   2  *
   3  * COPYRIGHT:       See COPYING in the top level directory
   4  * PROJECT:         ReactOS kernel
   5  * FILE:            ntoskrnl/rtl/bitmap.c
   6  * PURPOSE:         Bitmap functions
   7  * UPDATE HISTORY:
   8  *                  20/08/99 Created by Eric Kohl
   9  */
  10
  11 #include <ddk/ntddk.h>
  12
  13
  14 #define ALIGN(x,align)  (((x)+(align)-1) / (align))
  15
  16 #define MASK(Count, Shift) ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift))
  17
  18
  19 /*
  20  * @implemented
  21  */
  22 VOID
  23 STDCALL
  24 RtlInitializeBitMap (
  25         PRTL_BITMAP     BitMapHeader,
  26         PULONG          BitMapBuffer,
  27         ULONG           SizeOfBitMap
  28         )
  29 {
  30         BitMapHeader->SizeOfBitMap = SizeOfBitMap;
  31         BitMapHeader->Buffer = BitMapBuffer;
  32 }
  33
  34
  35 /*
  36  * @implemented
  37  */
  38 BOOLEAN
  39 STDCALL
  40 RtlAreBitsClear (
  41         PRTL_BITMAP     BitMapHeader,
  42         ULONG           StartingIndex,
  43         ULONG           Length
  44         )
  45 {
  46         ULONG Size = BitMapHeader->SizeOfBitMap;
  47         ULONG Shift;
  48         ULONG Count;
  49         PULONG Ptr;
  50
  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 dword */
  60                 Shift = StartingIndex & 0x1F;
  61
  62                 /* get number of bits to check in current dword */
  63                 Count = (Length > 32 - Shift) ? 32 - Shift : Length;
  64
  65                 /* check dword */
  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
  81 STDCALL
  82 RtlAreBitsSet (
  83         PRTL_BITMAP     BitMapHeader,
  84         ULONG           StartingIndex,
  85         ULONG           Length
  86         )
  87 {
  88         ULONG Size = BitMapHeader->SizeOfBitMap;
  89         ULONG Shift;
  90         ULONG Count;
  91         PULONG Ptr;
  92
  93         if (StartingIndex >= Size ||
  94             !Length ||
  95             (StartingIndex + Length > Size))
  96                 return FALSE;
  97
  98         Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
  99         while (Length)
 100         {
 101                 /* get bit shift in current dword */
 102                 Shift = StartingIndex & 0x1F;
 103
 104                 /* get number of bits to check in current dword */
 105                 Count = (Length > 32 - Shift) ? 32 - Shift : Length;
 106
 107                 /* check dword */
 108                 if (~*Ptr++ & MASK(Count, Shift))
 109                         return FALSE;
 110
 111                 Length -= Count;
 112                 StartingIndex += Count;
 113         }
 114
 115         return TRUE;
 116 }
 117
 118
 119 /*
 120  * @implemented
 121  */
 122 VOID
 123 STDCALL
 124 RtlClearAllBits (
 125         IN OUT  PRTL_BITMAP     BitMapHeader
 126         )
 127 {
 128         memset (BitMapHeader->Buffer,
 129                 0x00,
 130                 ALIGN(BitMapHeader->SizeOfBitMap, 8));
 131 }
 132
 133
 134 /*
 135  * @implemented
 136  */
 137 VOID
 138 STDCALL
 139 RtlClearBits (
 140         PRTL_BITMAP     BitMapHeader,
 141         ULONG           StartingIndex,
 142         ULONG           NumberToClear
 143         )
 144 {
 145         ULONG Size = BitMapHeader->SizeOfBitMap;
 146         ULONG Count;
 147         ULONG Shift;
 148         PULONG Ptr;
 149
 150         if (StartingIndex >= Size || NumberToClear == 0)
 151                 return;
 152
 153         if (StartingIndex + NumberToClear > Size)
 154                 NumberToClear = Size - StartingIndex;
 155
 156         Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
 157         while (NumberToClear)
 158         {
 159                 /* bit shift in current dword */
 160                 Shift = StartingIndex & 0x1F;
 161
 162                 /* number of bits to change in current dword */
 163                 Count = (NumberToClear > 32 - Shift ) ? 32 - Shift : NumberToClear;
 164
 165                 /* adjust dword */
 166                 *Ptr++ &= ~MASK(Count, Shift);
 167                 NumberToClear -= Count;
 168                 StartingIndex += Count;
 169         }
 170 }
 171
 172
 173 /*
 174  * @implemented
 175  */
 176 ULONG
 177 STDCALL
 178 RtlFindClearBits (
 179         PRTL_BITMAP     BitMapHeader,
 180         ULONG           NumberToFind,
 181         ULONG           HintIndex
 182         )
 183 {
 184         ULONG Size = BitMapHeader->SizeOfBitMap;
 185         ULONG Index;
 186         ULONG Count;
 187         PULONG Ptr;
 188         ULONG  Mask;
 189
 190         if (NumberToFind > Size || NumberToFind == 0)
 191                 return -1;
 192
 193         if (HintIndex >= Size)
 194                 HintIndex = 0;
 195
 196         Index = HintIndex;
 197         Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 198         Mask  = 1 << (Index & 0x1F);
 199
 200         while (HintIndex < Size)
 201         {
 202                 /* count clear bits */
 203                 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 204                 {
 205                         if (++Count >= NumberToFind)
 206                                 return HintIndex;
 207                         Mask <<= 1;
 208                         if (Mask == 0)
 209                         {
 210                                 Mask = 1;
 211                                 Ptr++;
 212                         }
 213                 }
 214
 215                 /* skip set bits */
 216                 for (; Index < Size && *Ptr & Mask; Index++)
 217                 {
 218                         Mask <<= 1;
 219                         if (Mask == 0)
 220                         {
 221                                 Mask = 1;
 222                                 Ptr++;
 223                         }
 224                 }
 225                 HintIndex = Index;
 226         }
 227
 228         return -1;
 229 }
 230
 231
 232 /*
 233  * @implemented
 234  */
 235 ULONG
 236 STDCALL
 237 RtlFindClearBitsAndSet (
 238         PRTL_BITMAP     BitMapHeader,
 239         ULONG           NumberToFind,
 240         ULONG           HintIndex
 241         )
 242 {
 243         ULONG Index;
 244
 245         Index = RtlFindClearBits (BitMapHeader,
 246                                   NumberToFind,
 247                                   HintIndex);
 248         if (Index != (ULONG)-1)
 249                 RtlSetBits (BitMapHeader,
 250                             Index,
 251                             NumberToFind);
 252
 253         return Index;
 254 }
 255
 256
 257 /*
 258  * @implemented
 259  */
 260 ULONG
 261 STDCALL
 262 RtlFindFirstRunClear (
 263         PRTL_BITMAP     BitMapHeader,
 264         PULONG          StartingIndex
 265         )
 266 {
 267         ULONG Size = BitMapHeader->SizeOfBitMap;
 268         ULONG Index;
 269         ULONG Count;
 270         PULONG Ptr;
 271         ULONG  Mask;
 272
 273         if (*StartingIndex > Size)
 274         {
 275                 *StartingIndex = (ULONG)-1;
 276                 return 0;
 277         }
 278
 279         Index = *StartingIndex;
 280         Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 281         Mask = 1 << (Index & 0x1F);
 282
 283         /* skip set bits */
 284         for (; Index < Size && *Ptr & Mask; Index++)
 285         {
 286                 Mask <<= 1;
 287                 if (Mask == 0)
 288                 {
 289                         Mask = 1;
 290                         Ptr++;
 291                 }
 292         }
 293
 294         /* return index of first clear bit */
 295         if (Index >= Size)
 296         {
 297                 *StartingIndex = (ULONG)-1;
 298                 return 0;
 299         }
 300         else
 301                 *StartingIndex = Index;
 302
 303         /* count clear bits */
 304         for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 305         {
 306                 Count++;
 307                 Mask <<= 1;
 308                 if (Mask == 0)
 309                 {
 310                         Mask = 1;
 311                         Ptr++;
 312                 }
 313         }
 314
 315         return Count;
 316 }
 317
 318
 319 ULONG
 320 STDCALL
 321 RtlFindFirstRunSet (
 322         PRTL_BITMAP     BitMapHeader,
 323         PULONG          StartingIndex
 324         )
 325 {
 326         ULONG Size = BitMapHeader->SizeOfBitMap;
 327         ULONG Index;
 328         ULONG Count;
 329         PULONG Ptr;
 330         ULONG  Mask;
 331
 332         if (*StartingIndex > Size)
 333         {
 334                 *StartingIndex = (ULONG)-1;
 335                 return 0;
 336         }
 337
 338         Index = *StartingIndex;
 339         Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 340         Mask = 1 << (Index & 0x1F);
 341
 342         /* skip clear bits */
 343         for (; Index < Size && ~*Ptr & Mask; Index++)
 344         {
 345                 Mask <<= 1;
 346                 if (Mask == 0)
 347                 {
 348                         Mask = 1;
 349                         Ptr++;
 350                 }
 351         }
 352
 353         /* return index of first set bit */
 354         if (Index >= Size)
 355         {
 356                 *StartingIndex = (ULONG)-1;
 357                 return 0;
 358         }
 359         else
 360                 *StartingIndex = Index;
 361
 362         /* count set bits */
 363         for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 364         {
 365                 Count++;
 366                 Mask <<= 1;
 367                 if (Mask == 0)
 368                 {
 369                         Mask = 1;
 370                         Ptr++;
 371                 }
 372         }
 373
 374         return Count;
 375 }
 376
 377
 378 /*
 379  * @implemented
 380  */
 381 ULONG
 382 STDCALL
 383 RtlFindLongestRunClear (
 384         PRTL_BITMAP     BitMapHeader,
 385         PULONG          StartingIndex
 386         )
 387 {
 388         ULONG Size = BitMapHeader->SizeOfBitMap;
 389         PULONG Ptr = (PULONG)BitMapHeader->Buffer;
 390         ULONG Index = 0;
 391         ULONG Count;
 392         ULONG Max = 0;
 393         ULONG Start;
 394         ULONG Maxstart = 0;
 395         ULONG  Mask = 1;
 396
 397         while (Index < Size)
 398         {
 399                 Start = Index;
 400
 401                 /* count clear bits */
 402                 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 403                 {
 404                         Count++;
 405                         Mask <<= 1;
 406                         if (Mask == 0)
 407                         {
 408                                 Mask = 1;
 409                                 Ptr++;
 410                         }
 411                 }
 412
 413                 /* skip set bits */
 414                 for (; Index < Size && *Ptr & Mask; Index++)
 415                 {
 416                         Mask <<= 1;
 417                         if (Mask == 0)
 418                         {
 419                                 Mask = 1;
 420                                 Ptr++;
 421                         }
 422                 }
 423
 424                 if (Count > Max)
 425                 {
 426                         Max = Count;
 427                         Maxstart = Start;
 428                 }
 429         }
 430
 431         if (StartingIndex)
 432                 *StartingIndex = Maxstart;
 433
 434         return Max;
 435 }
 436
 437
 438 ULONG
 439 STDCALL
 440 RtlFindLongestRunSet (
 441         PRTL_BITMAP     BitMapHeader,
 442         PULONG          StartingIndex
 443         )
 444 {
 445         ULONG Size = BitMapHeader->SizeOfBitMap;
 446         PULONG Ptr = (PULONG)BitMapHeader->Buffer;
 447         ULONG Index = 0;
 448         ULONG Count;
 449         ULONG Max = 0;
 450         ULONG Start;
 451         ULONG Maxstart = 0;
 452         ULONG Mask = 1;
 453
 454         while (Index < Size)
 455         {
 456                 Start = Index;
 457
 458                 /* count set bits */
 459                 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 460                 {
 461                         Count++;
 462                         Mask <<= 1;
 463                         if (Mask == 0)
 464                         {
 465                                 Mask = 1;
 466                                 Ptr++;
 467                         }
 468                 }
 469
 470                 /* skip clear bits */
 471                 for (; Index < Size && ~*Ptr & Mask; Index++)
 472                 {
 473                         Mask <<= 1;
 474                         if (Mask == 0)
 475                         {
 476                                 Mask = 1;
 477                                 Ptr++;
 478                         }
 479                 }
 480
 481                 if (Count > Max)
 482                 {
 483                         Max = Count;
 484                         Maxstart = Start;
 485                 }
 486         }
 487
 488         if (StartingIndex)
 489                 *StartingIndex = Maxstart;
 490
 491         return Max;
 492 }
 493
 494
 495 /*
 496  * @implemented
 497  */
 498 ULONG
 499 STDCALL
 500 RtlFindSetBits (
 501         PRTL_BITMAP     BitMapHeader,
 502         ULONG           NumberToFind,
 503         ULONG           HintIndex
 504         )
 505 {
 506         ULONG Size = BitMapHeader->SizeOfBitMap;
 507         ULONG Index;
 508         ULONG Count;
 509         PULONG Ptr;
 510         ULONG Mask;
 511
 512         if (NumberToFind > Size || NumberToFind == 0)
 513                 return (ULONG)-1;
 514
 515         if (HintIndex >= Size)
 516                 HintIndex = 0;
 517
 518         Index = HintIndex;
 519         Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 520         Mask = 1 << (Index & 0x1F);
 521
 522         while (HintIndex < Size)
 523         {
 524                 /* count set bits */
 525                 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 526                 {
 527                         if (++Count >= NumberToFind)
 528                                 return HintIndex;
 529                         Mask <<= 1;
 530                         if (Mask == 0)
 531                         {
 532                                 Mask = 1;
 533                                 Ptr++;
 534                         }
 535                 }
 536
 537                 /* skip clear bits */
 538                 for (; Index < Size && ~*Ptr & Mask; Index++)
 539                 {
 540                         Mask <<= 1;
 541                         if (Mask == 0)
 542                         {
 543                                 Mask = 1;
 544                                 Ptr++;
 545                         }
 546                 }
 547                 HintIndex = Index;
 548         }
 549
 550         return (ULONG)-1;
 551 }
 552
 553
 554 /*
 555  * @implemented
 556  */
 557 ULONG
 558 STDCALL
 559 RtlFindSetBitsAndClear (
 560         PRTL_BITMAP     BitMapHeader,
 561         ULONG           NumberToFind,
 562         ULONG           HintIndex
 563         )
 564 {
 565         ULONG Index;
 566
 567         Index = RtlFindSetBits (BitMapHeader,
 568                                 NumberToFind,
 569                                 HintIndex);
 570         if (Index != (ULONG)-1)
 571                 RtlClearBits (BitMapHeader,
 572                               Index,
 573                               NumberToFind);
 574
 575         return Index;
 576 }
 577
 578
 579 /*
 580  * @implemented
 581  */
 582 ULONG
 583 STDCALL
 584 RtlNumberOfClearBits (
 585         PRTL_BITMAP     BitMapHeader
 586         )
 587 {
 588         PULONG Ptr = (PULONG)BitMapHeader->Buffer;
 589         ULONG Size = BitMapHeader->SizeOfBitMap;
 590         ULONG Index;
 591         ULONG Count;
 592         ULONG Mask;
 593
 594         for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 595         {
 596                 if (~*Ptr & Mask)
 597                         Count++;
 598
 599                 Mask <<= 1;
 600                 if (Mask == 0)
 601                 {
 602                         Mask = 1;
 603                         Ptr++;
 604                 }
 605         }
 606
 607         return Count;
 608 }
 609
 610
 611 /*
 612  * @implemented
 613  */
 614 ULONG
 615 STDCALL
 616 RtlNumberOfSetBits (
 617         PRTL_BITMAP     BitMapHeader
 618         )
 619 {
 620         PULONG Ptr = (PULONG)BitMapHeader->Buffer;
 621         ULONG Size = BitMapHeader->SizeOfBitMap;
 622         ULONG Index;
 623         ULONG Count;
 624         ULONG Mask;
 625
 626         for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 627         {
 628                 if (*Ptr & Mask)
 629                         Count++;
 630
 631                 Mask <<= 1;
 632                 if (Mask == 0)
 633                 {
 634                         Mask = 1;
 635                         Ptr++;
 636                 }
 637         }
 638
 639         return Count;
 640 }
 641
 642
 643 /*
 644  * @implemented
 645  */
 646 VOID
 647 STDCALL
 648 RtlSetAllBits (
 649         IN OUT  PRTL_BITMAP     BitMapHeader
 650         )
 651 {
 652         memset (BitMapHeader->Buffer,
 653                 0xFF,
 654                 ALIGN(BitMapHeader->SizeOfBitMap, 8));
 655 }
 656
 657
 658 /*
 659  * @implemented
 660  */
 661 VOID
 662 STDCALL
 663 RtlSetBits (
 664         PRTL_BITMAP     BitMapHeader,
 665         ULONG           StartingIndex,
 666         ULONG           NumberToSet
 667         )
 668 {
 669         ULONG Size = BitMapHeader->SizeOfBitMap;
 670         ULONG Count;
 671         ULONG Shift;
 672         PULONG Ptr;
 673
 674         if (StartingIndex >= Size || NumberToSet == 0)
 675                 return;
 676
 677         if (StartingIndex + NumberToSet > Size)
 678                 NumberToSet = Size - StartingIndex;
 679
 680         Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
 681         while (NumberToSet)
 682         {
 683                 /* bit shift in current dword */
 684                 Shift = StartingIndex & 0x1F;
 685
 686                 /* number of bits to change in current dword */
 687                 Count = (NumberToSet > 32 - Shift) ? 32 - Shift : NumberToSet;
 688
 689                 /* adjust dword */
 690                 *Ptr++ |= MASK(Count, Shift);
 691                 NumberToSet -= Count;
 692                 StartingIndex += Count;
 693         }
 694 }
 695
 696 /* EOF */