reactos/lib/ntdll/rtl/bitmap.c

   1 /* $Id: bitmap.c,v 1.7 2004/02/02 13:34:01 ekohl Exp $
   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 /*
 269  * @unimplemented
 270  */
 271 ULONG STDCALL
 272 RtlFindClearRuns (PRTL_BITMAP BitMapHeader,
 273                   PRTL_BITMAP_RUN RunArray,
 274                   ULONG SizeOfRunArray,
 275                   BOOLEAN LocateLongestRuns)
 276 {
 277   return (ULONG)-1;
 278 }
 279
 280
 281 ULONG
 282 STDCALL
 283 RtlFindFirstRunClear (
 284         PRTL_BITMAP     BitMapHeader,
 285         PULONG          StartingIndex
 286         )
 287 {
 288         ULONG Size = BitMapHeader->SizeOfBitMap;
 289         ULONG Index;
 290         ULONG Count;
 291         PCHAR Ptr;
 292         CHAR  Mask;
 293
 294         if (*StartingIndex > Size)
 295         {
 296                 *StartingIndex = (ULONG)-1;
 297                 return 0;
 298         }
 299
 300         Index = *StartingIndex;
 301         Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
 302         Mask = 1 << (Index & 7);
 303
 304         /* skip set bits */
 305         for (; Index < Size && *Ptr & Mask; Index++)
 306         {
 307                 Mask <<= 1;
 308                 if (Mask == 0)
 309                 {
 310                         Mask = 1;
 311                         Ptr++;
 312                 }
 313         }
 314
 315         /* return index of first clear bit */
 316         if (Index >= Size)
 317         {
 318                 *StartingIndex = (ULONG)-1;
 319                 return 0;
 320         }
 321         else
 322                 *StartingIndex = Index;
 323
 324         /* count clear bits */
 325         for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 326         {
 327                 Count++;
 328                 Mask <<= 1;
 329                 if (Mask == 0)
 330                 {
 331                         Mask = 1;
 332                         Ptr++;
 333                 }
 334         }
 335
 336         return Count;
 337 }
 338
 339
 340 ULONG
 341 STDCALL
 342 RtlFindFirstRunSet (
 343         PRTL_BITMAP     BitMapHeader,
 344         PULONG          StartingIndex
 345         )
 346 {
 347         ULONG Size = BitMapHeader->SizeOfBitMap;
 348         ULONG Index;
 349         ULONG Count;
 350         PCHAR Ptr;
 351         CHAR  Mask;
 352
 353         if (*StartingIndex > Size)
 354         {
 355                 *StartingIndex = (ULONG)-1;
 356                 return 0;
 357         }
 358
 359         Index = *StartingIndex;
 360         Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
 361         Mask = 1 << (Index & 7);
 362
 363         /* skip clear bits */
 364         for (; Index < Size && ~*Ptr & Mask; Index++)
 365         {
 366                 Mask <<= 1;
 367                 if (Mask == 0)
 368                 {
 369                         Mask = 1;
 370                         Ptr++;
 371                 }
 372         }
 373
 374         /* return index of first set bit */
 375         if (Index >= Size)
 376         {
 377                 *StartingIndex = (ULONG)-1;
 378                 return 0;
 379         }
 380         else
 381                 *StartingIndex = Index;
 382
 383         /* count set bits */
 384         for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 385         {
 386                 Count++;
 387                 Mask <<= 1;
 388                 if (Mask == 0)
 389                 {
 390                         Mask = 1;
 391                         Ptr++;
 392                 }
 393         }
 394
 395         return Count;
 396 }
 397
 398
 399 /*
 400  * @unimplemented
 401  */
 402 ULONG STDCALL
 403 RtlFindLastBackwardRunClear (IN PRTL_BITMAP BitMapHeader,
 404                              IN ULONG FromIndex,
 405                              IN PULONG StartingRunIndex)
 406 {
 407   return (ULONG)-1;
 408 }
 409
 410
 411 /*
 412  * @implemented
 413  */
 414 ULONG
 415 STDCALL
 416 RtlFindLongestRunClear (
 417         PRTL_BITMAP     BitMapHeader,
 418         PULONG          StartingIndex
 419         )
 420 {
 421         ULONG Size = BitMapHeader->SizeOfBitMap;
 422         PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
 423         ULONG Index = 0;
 424         ULONG Count;
 425         ULONG Max = 0;
 426         ULONG Start;
 427         ULONG Maxstart = 0;
 428         CHAR  Mask = 1;
 429
 430         while (Index < Size)
 431         {
 432                 Start = Index;
 433
 434                 /* count clear bits */
 435                 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
 436                 {
 437                         Count++;
 438                         Mask <<= 1;
 439                         if (Mask == 0)
 440                         {
 441                                 Mask = 1;
 442                                 Ptr++;
 443                         }
 444                 }
 445
 446                 /* skip set bits */
 447                 for (; Index < Size && *Ptr & Mask; Index++)
 448                 {
 449                         Mask <<= 1;
 450                         if (Mask == 0)
 451                         {
 452                                 Mask = 1;
 453                                 Ptr++;
 454                         }
 455                 }
 456
 457                 if (Count > Max)
 458                 {
 459                         Max = Count;
 460                         Maxstart = Start;
 461                 }
 462         }
 463
 464         if (StartingIndex)
 465                 *StartingIndex = Maxstart;
 466
 467         return Max;
 468 }
 469
 470
 471 /*
 472  * @implemented
 473  */
 474 ULONG
 475 STDCALL
 476 RtlFindLongestRunSet (
 477         PRTL_BITMAP     BitMapHeader,
 478         PULONG          StartingIndex
 479         )
 480 {
 481         ULONG Size = BitMapHeader->SizeOfBitMap;
 482         PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
 483         ULONG Index = 0;
 484         ULONG Count;
 485         ULONG Max = 0;
 486         ULONG Start;
 487         ULONG Maxstart = 0;
 488         CHAR  Mask = 1;
 489
 490         while (Index < Size)
 491         {
 492                 Start = Index;
 493
 494                 /* count set bits */
 495                 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 496                 {
 497                         Count++;
 498                         Mask <<= 1;
 499                         if (Mask == 0)
 500                         {
 501                                 Mask = 1;
 502                                 Ptr++;
 503                         }
 504                 }
 505
 506                 /* skip clear bits */
 507                 for (; Index < Size && ~*Ptr & Mask; Index++)
 508                 {
 509                         Mask <<= 1;
 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)
 525                 *StartingIndex = Maxstart;
 526
 527         return Max;
 528 }
 529
 530
 531 /*
 532  * @unimplemented
 533  */
 534 ULONG STDCALL
 535 RtlFindNextForwardRunClear (IN PRTL_BITMAP BitMapHeader,
 536                             IN ULONG FromIndex,
 537                             IN PULONG StartingRunIndex)
 538 {
 539   return (ULONG)-1;
 540 }
 541
 542
 543 /*
 544  * @implemented
 545  */
 546 ULONG
 547 STDCALL
 548 RtlFindSetBits (
 549         PRTL_BITMAP     BitMapHeader,
 550         ULONG           NumberToFind,
 551         ULONG           HintIndex
 552         )
 553 {
 554         ULONG Size = BitMapHeader->SizeOfBitMap;
 555         ULONG Index;
 556         ULONG Count;
 557         PCHAR Ptr;
 558         CHAR  Mask;
 559
 560         if (NumberToFind > Size || NumberToFind == 0)
 561                 return (ULONG)-1;
 562
 563         if (HintIndex >= Size)
 564                 HintIndex = 0;
 565
 566         Index = HintIndex;
 567         Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
 568         Mask = 1 << (Index & 7);
 569
 570         while (HintIndex < Size)
 571         {
 572                 /* count set bits */
 573                 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 574                 {
 575                         if (++Count >= NumberToFind)
 576                                 return HintIndex;
 577                         Mask <<= 1;
 578                         if (Mask == 0)
 579                         {
 580                                 Mask = 1;
 581                                 Ptr++;
 582                         }
 583                 }
 584
 585                 /* skip clear bits */
 586                 for (; Index < Size && ~*Ptr & Mask; Index++)
 587                 {
 588                         Mask <<= 1;
 589                         if (Mask == 0)
 590                         {
 591                                 Mask = 1;
 592                                 Ptr++;
 593                         }
 594                 }
 595                 HintIndex = Index;
 596         }
 597
 598         return (ULONG)-1;
 599 }
 600
 601
 602 /*
 603  * @implemented
 604  */
 605 ULONG
 606 STDCALL
 607 RtlFindSetBitsAndClear (
 608         PRTL_BITMAP     BitMapHeader,
 609         ULONG           NumberToFind,
 610         ULONG           HintIndex
 611         )
 612 {
 613         ULONG Index;
 614
 615         Index = RtlFindSetBits (BitMapHeader,
 616                                 NumberToFind,
 617                                 HintIndex);
 618         if (Index != (ULONG)-1)
 619                 RtlClearBits (BitMapHeader,
 620                               Index,
 621                               NumberToFind);
 622
 623         return Index;
 624 }
 625
 626
 627 /*
 628  * @implemented
 629  */
 630 ULONG
 631 STDCALL
 632 RtlNumberOfClearBits (
 633         PRTL_BITMAP     BitMapHeader
 634         )
 635 {
 636         PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
 637         ULONG Size = BitMapHeader->SizeOfBitMap;
 638         ULONG Index;
 639         ULONG Count;
 640         CHAR Mask;
 641
 642         for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 643         {
 644                 if (~*Ptr & Mask)
 645                         Count++;
 646
 647                 Mask <<= 1;
 648                 if (Mask == 0)
 649                 {
 650                         Mask = 1;
 651                         Ptr++;
 652                 }
 653         }
 654
 655         return Count;
 656 }
 657
 658
 659 /*
 660  * @implemented
 661  */
 662 ULONG
 663 STDCALL
 664 RtlNumberOfSetBits (
 665         PRTL_BITMAP     BitMapHeader
 666         )
 667 {
 668         PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
 669         ULONG Size = BitMapHeader->SizeOfBitMap;
 670         ULONG Index;
 671         ULONG Count;
 672         CHAR Mask;
 673
 674         for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
 675         {
 676                 if (*Ptr & Mask)
 677                         Count++;
 678
 679                 Mask <<= 1;
 680                 if (Mask == 0)
 681                 {
 682                         Mask = 1;
 683                         Ptr++;
 684                 }
 685         }
 686
 687         return Count;
 688 }
 689
 690
 691 /*
 692  * @implemented
 693  */
 694 VOID
 695 STDCALL
 696 RtlSetAllBits (
 697         IN OUT  PRTL_BITMAP     BitMapHeader
 698         )
 699 {
 700         memset (BitMapHeader->Buffer,
 701                 0xFF,
 702                 ALIGN(BitMapHeader->SizeOfBitMap, 8));
 703 }
 704
 705
 706 /*
 707  * @implemented
 708  */
 709 VOID
 710 STDCALL
 711 RtlSetBits (
 712         PRTL_BITMAP     BitMapHeader,
 713         ULONG           StartingIndex,
 714         ULONG           NumberToSet
 715         )
 716 {
 717         ULONG Size = BitMapHeader->SizeOfBitMap;
 718         ULONG Count;
 719         ULONG Shift;
 720         PCHAR Ptr;
 721
 722         if (StartingIndex >= Size || NumberToSet == 0)
 723                 return;
 724
 725         if (StartingIndex + NumberToSet > Size)
 726                 NumberToSet = Size - StartingIndex;
 727
 728         Ptr = (PCHAR)BitMapHeader->Buffer + (StartingIndex / 8);
 729         while (NumberToSet)
 730         {
 731                 /* bit shift in current byte */
 732                 Shift = StartingIndex & 7;
 733
 734                 /* number of bits to change in current byte */
 735                 Count = (NumberToSet > 8 - Shift) ? 8 - Shift : NumberToSet;
 736
 737                 /* adjust byte */
 738                 *Ptr |= ~(0xFF << Count) << Shift;
 739
 740                 Ptr++;
 741                 NumberToSet -= Count;
 742                 StartingIndex += Count;
 743         }
 744 }
 745
 746
 747 /*
 748  * @implemented
 749  */
 750 CCHAR STDCALL
 751 RtlFindLeastSignificantBit (IN ULONGLONG Set)
 752 {
 753   int i;
 754
 755   if (Set == 0ULL)
 756     return -1;
 757
 758   for (i = 0; i < 64; i++)
 759     {
 760       if (Set & (1 << i))
 761         return (CCHAR)i;
 762     }
 763
 764   return -1;
 765 }
 766
 767
 768 /*
 769  * @implemented
 770  */
 771 CCHAR STDCALL
 772 RtlFindMostSignificantBit (IN ULONGLONG Set)
 773 {
 774   int i;
 775
 776   if (Set == 0ULL)
 777     return -1;
 778
 779   for (i = 63; i >= 0; i--)
 780     {
 781       if (Set & (1 << i))
 782         return (CCHAR)i;
 783     }
 784
 785   return -1;
 786 }
 787
 788 /* EOF */