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