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