lib/ntdll/rtl/bitmap.c

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