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