reactos/lib/rtl/bitmap.c

   1 /* COPYRIGHT:       See COPYING in the top level directory
   2  * PROJECT:         ReactOS system libraries
   3  * FILE:            lib/rtl/bitmap.c
   4  * PURPOSE:         Bitmap functions
   5  * PROGRAMMER:      Eric Kohl
   6  */
   7
   8 /* INCLUDES *****************************************************************/
   9
  10 #include <rtl.h>
  11
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* MACROS *******************************************************************/
  16
  17 /* Bits set from LSB to MSB; used as mask for runs < 8 bits */
  18 static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
  19
  20 /* Number of set bits for each value of a nibble; used for counting */
  21 static const BYTE NTDLL_nibbleBitCount[16] = {
  22   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  23 };
  24
  25 /* First set bit in a nibble; used for determining least significant bit */
  26 static const BYTE NTDLL_leastSignificant[16] = {
  27   0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  28 };
  29
  30 /* Last set bit in a nibble; used for determining most significant bit */
  31 static const signed char NTDLL_mostSignificant[16] = {
  32   -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
  33 };
  34
  35 /* PRIVATE FUNCTIONS *********************************************************/
  36
  37 static
  38 int
  39 __cdecl
  40 NTDLL_RunSortFn(const void *lhs,
  41                 const void *rhs)
  42 {
  43   if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
  44     return -1;
  45   return 1;
  46 }
  47
  48 static
  49 ULONG
  50 WINAPI
  51 NTDLL_FindRuns(PRTL_BITMAP lpBits,
  52                PRTL_BITMAP_RUN lpSeries,
  53                ULONG ulCount,
  54                BOOLEAN bLongest,
  55                ULONG (*fn)(PRTL_BITMAP,ULONG,PULONG))
  56 {
  57   BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
  58   ULONG ulPos = 0, ulRuns = 0;
  59
  60   if (!ulCount)
  61     return ~0U;
  62
  63   while (ulPos < lpBits->SizeOfBitMap)
  64   {
  65     /* Find next set/clear run */
  66     ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
  67
  68     if (ulNextPos == ~0U)
  69       break;
  70
  71     if (bLongest && ulRuns == ulCount)
  72     {
  73       /* Sort runs with shortest at end, if they are out of order */
  74       if (bNeedSort)
  75         qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
  76
  77       /* Replace last run if this one is bigger */
  78       if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
  79       {
  80         lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
  81         lpSeries[ulRuns - 1].NumberOfBits = ulSize;
  82
  83         /* We need to re-sort the array, _if_ we didn't leave it sorted */
  84         if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
  85           bNeedSort = TRUE;
  86       }
  87     }
  88     else
  89     {
  90       /* Append to found runs */
  91       lpSeries[ulRuns].StartingIndex = ulNextPos;
  92       lpSeries[ulRuns].NumberOfBits = ulSize;
  93       ulRuns++;
  94
  95       if (!bLongest && ulRuns == ulCount)
  96         break;
  97     }
  98     ulPos = ulNextPos + ulSize;
  99   }
 100   return ulRuns;
 101 }
 102
 103 static
 104 ULONG
 105 NTDLL_FindSetRun(PRTL_BITMAP lpBits,
 106                  ULONG ulStart,
 107                  PULONG lpSize)
 108 {
 109   LPBYTE lpOut;
 110   ULONG ulFoundAt = 0, ulCount = 0;
 111
 112   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 113    * at a time. But beware of the pointer arithmetics...
 114    */
 115   lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
 116
 117   while (1)
 118   {
 119     /* Check bits in first byte */
 120     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 121     const BYTE bFirst = *lpOut & bMask;
 122
 123     if (bFirst)
 124     {
 125       /* Have a set bit in first byte */
 126       if (bFirst != bMask)
 127       {
 128         /* Not every bit is set */
 129         ULONG ulOffset;
 130
 131         if (bFirst & 0x0f)
 132           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 133         else
 134           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 135         ulStart += ulOffset;
 136         ulFoundAt = ulStart;
 137         for (;ulOffset < 8; ulOffset++)
 138         {
 139           if (!(bFirst & (1 << ulOffset)))
 140           {
 141             *lpSize = ulCount;
 142             return ulFoundAt; /* Set from start, but not until the end */
 143           }
 144           ulCount++;
 145           ulStart++;
 146         }
 147         /* Set to the end - go on to count further bits */
 148         lpOut++;
 149         break;
 150       }
 151       /* every bit from start until the end of the byte is set */
 152       ulFoundAt = ulStart;
 153       ulCount = 8 - (ulStart & 7);
 154       ulStart = (ulStart & ~7u) + 8;
 155       lpOut++;
 156       break;
 157     }
 158     ulStart = (ulStart & ~7u) + 8;
 159     lpOut++;
 160     if (ulStart >= lpBits->SizeOfBitMap)
 161       return ~0U;
 162   }
 163
 164   /* Count blocks of 8 set bits */
 165   while (*lpOut == 0xff)
 166   {
 167     ulCount += 8;
 168     ulStart += 8;
 169     if (ulStart >= lpBits->SizeOfBitMap)
 170     {
 171       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 172       return ulFoundAt;
 173     }
 174     lpOut++;
 175   }
 176
 177   /* Count remaining contiguous bits, if any */
 178   if (*lpOut & 1)
 179   {
 180     ULONG ulOffset = 0;
 181
 182     for (;ulOffset < 7u; ulOffset++)
 183     {
 184       if (!(*lpOut & (1 << ulOffset)))
 185         break;
 186       ulCount++;
 187     }
 188   }
 189   *lpSize = ulCount;
 190   return ulFoundAt;
 191 }
 192
 193 static
 194 ULONG
 195 NTDLL_FindClearRun(PRTL_BITMAP lpBits,
 196                    ULONG ulStart,
 197                    PULONG lpSize)
 198 {
 199   LPBYTE lpOut;
 200   ULONG ulFoundAt = 0, ulCount = 0;
 201
 202   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 203    * at a time. But beware of the pointer arithmetics...
 204    */
 205   lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
 206
 207   while (1)
 208   {
 209     /* Check bits in first byte */
 210     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 211     const BYTE bFirst = (~*lpOut) & bMask;
 212
 213     if (bFirst)
 214     {
 215       /* Have a clear bit in first byte */
 216       if (bFirst != bMask)
 217       {
 218         /* Not every bit is clear */
 219         ULONG ulOffset;
 220
 221         if (bFirst & 0x0f)
 222           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 223         else
 224           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 225         ulStart += ulOffset;
 226         ulFoundAt = ulStart;
 227         for (;ulOffset < 8; ulOffset++)
 228         {
 229           if (!(bFirst & (1 << ulOffset)))
 230           {
 231             *lpSize = ulCount;
 232             return ulFoundAt; /* Clear from start, but not until the end */
 233           }
 234           ulCount++;
 235           ulStart++;
 236         }
 237         /* Clear to the end - go on to count further bits */
 238         lpOut++;
 239         break;
 240       }
 241       /* Every bit from start until the end of the byte is clear */
 242       ulFoundAt = ulStart;
 243       ulCount = 8 - (ulStart & 7);
 244       ulStart = (ulStart & ~7u) + 8;
 245       lpOut++;
 246       break;
 247     }
 248     ulStart = (ulStart & ~7u) + 8;
 249     lpOut++;
 250     if (ulStart >= lpBits->SizeOfBitMap)
 251       return ~0U;
 252   }
 253
 254   /* Count blocks of 8 clear bits */
 255   while (!*lpOut)
 256   {
 257     ulCount += 8;
 258     ulStart += 8;
 259     if (ulStart >= lpBits->SizeOfBitMap)
 260     {
 261       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 262       return ulFoundAt;
 263     }
 264     lpOut++;
 265   }
 266
 267   /* Count remaining contiguous bits, if any */
 268   if (!(*lpOut & 1))
 269   {
 270     ULONG ulOffset = 0;
 271
 272     for (;ulOffset < 7u; ulOffset++)
 273     {
 274       if (*lpOut & (1 << ulOffset))
 275         break;
 276       ulCount++;
 277     }
 278   }
 279   *lpSize = ulCount;
 280   return ulFoundAt;
 281 }
 282
 283 /* FUNCTIONS ****************************************************************/
 284
 285 /*
 286  * @implemented
 287  */
 288 VOID
 289 NTAPI
 290 RtlInitializeBitMap(IN PRTL_BITMAP BitMapHeader,
 291                     IN PULONG BitMapBuffer,
 292                     IN ULONG SizeOfBitMap)
 293 {
 294     /* Setup the bitmap header */
 295     BitMapHeader->SizeOfBitMap = SizeOfBitMap;
 296     BitMapHeader->Buffer = BitMapBuffer;
 297 }
 298
 299 /*
 300  * @implemented
 301  */
 302 BOOLEAN
 303 NTAPI
 304 RtlAreBitsClear(IN PRTL_BITMAP BitMapHeader,
 305                 IN ULONG StartingIndex,
 306                 IN ULONG Length)
 307 {
 308   LPBYTE lpOut;
 309   ULONG ulRemainder;
 310
 311   if (!BitMapHeader || !Length ||
 312       StartingIndex >= BitMapHeader->SizeOfBitMap ||
 313       Length > BitMapHeader->SizeOfBitMap - StartingIndex)
 314     return FALSE;
 315
 316   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 317    * at a time. But beware of the pointer arithmetics...
 318    */
 319   lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
 320
 321   /* Check bits in first byte, if StartingIndex isn't a byte boundary */
 322   if (StartingIndex & 7)
 323   {
 324     if (Length > 7)
 325     {
 326       /* Check from start bit to the end of the byte */
 327       if (*lpOut & ((0xff << (StartingIndex & 7)) & 0xff))
 328         return FALSE;
 329       lpOut++;
 330       Length -= (8 - (StartingIndex & 7));
 331     }
 332     else
 333     {
 334       /* Check from the start bit, possibly into the next byte also */
 335       USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
 336
 337       if (*lpOut & (initialWord & 0xff))
 338         return FALSE;
 339       if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
 340         return FALSE;
 341       return TRUE;
 342     }
 343   }
 344
 345   /* Check bits in blocks of 8 bytes */
 346   ulRemainder = Length & 7;
 347   Length >>= 3;
 348   while (Length--)
 349   {
 350     if (*lpOut++)
 351       return FALSE;
 352   }
 353
 354   /* Check remaining bits, if any */
 355   if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
 356     return FALSE;
 357   return TRUE;
 358 }
 359
 360
 361 /*
 362  * @implemented
 363  */
 364 BOOLEAN NTAPI
 365 RtlAreBitsSet(PRTL_BITMAP BitMapHeader,
 366               ULONG StartingIndex,
 367               ULONG Length)
 368 {
 369   LPBYTE lpOut;
 370   ULONG ulRemainder;
 371
 372
 373   if (!BitMapHeader || !Length ||
 374       StartingIndex >= BitMapHeader->SizeOfBitMap ||
 375       Length > BitMapHeader->SizeOfBitMap - StartingIndex)
 376     return FALSE;
 377
 378   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 379    * at a time. But beware of the pointer arithmetics...
 380    */
 381   lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
 382
 383   /* Check bits in first byte, if StartingIndex isn't a byte boundary */
 384   if (StartingIndex & 7)
 385   {
 386     if (Length > 7)
 387     {
 388       /* Check from start bit to the end of the byte */
 389       if ((*lpOut &
 390           ((0xff << (StartingIndex & 7))) & 0xff) != ((0xff << (StartingIndex & 7) & 0xff)))
 391         return FALSE;
 392       lpOut++;
 393       Length -= (8 - (StartingIndex & 7));
 394     }
 395     else
 396     {
 397       /* Check from the start bit, possibly into the next byte also */
 398       USHORT initialWord = NTDLL_maskBits[Length] << (StartingIndex & 7);
 399
 400       if ((*lpOut & (initialWord & 0xff)) != (initialWord & 0xff))
 401         return FALSE;
 402       if ((initialWord & 0xff00) &&
 403           ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
 404         return FALSE;
 405       return TRUE;
 406     }
 407   }
 408
 409   /* Check bits in blocks of 8 bytes */
 410   ulRemainder = Length & 7;
 411   Length >>= 3;
 412   while (Length--)
 413   {
 414     if (*lpOut++ != 0xff)
 415       return FALSE;
 416   }
 417
 418   /* Check remaining bits, if any */
 419   if (ulRemainder &&
 420       (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
 421     return FALSE;
 422   return TRUE;
 423 }
 424
 425
 426 /*
 427  * @implemented
 428  */
 429 VOID NTAPI
 430 RtlClearAllBits(IN OUT PRTL_BITMAP BitMapHeader)
 431 {
 432     memset(BitMapHeader->Buffer, 0, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
 433 }
 434
 435 /*
 436  * @implemented
 437  */
 438 VOID
 439 NTAPI
 440 RtlClearBit(PRTL_BITMAP BitMapHeader,
 441             ULONG BitNumber)
 442 {
 443     PULONG Ptr;
 444
 445     if (BitNumber >= BitMapHeader->SizeOfBitMap) return;
 446
 447     Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 448     *Ptr &= ~(1 << (BitNumber % 32));
 449 }
 450
 451 /*
 452  * @implemented
 453  */
 454 VOID
 455 NTAPI
 456 RtlClearBits(IN PRTL_BITMAP BitMapHeader,
 457              IN ULONG StartingIndex,
 458              IN ULONG NumberToClear)
 459 {
 460  LPBYTE lpOut;
 461
 462   if (!BitMapHeader || !NumberToClear ||
 463       StartingIndex >= BitMapHeader->SizeOfBitMap ||
 464       NumberToClear > BitMapHeader->SizeOfBitMap - StartingIndex)
 465     return;
 466
 467   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 468    * at a time. But beware of the pointer arithmetics...
 469    */
 470   lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
 471
 472   /* Clear bits in first byte, if StartingIndex isn't a byte boundary */
 473   if (StartingIndex & 7)
 474   {
 475     if (NumberToClear > 7)
 476     {
 477       /* Clear from start bit to the end of the byte */
 478       *lpOut++ &= ~(0xff << (StartingIndex & 7));
 479       NumberToClear -= (8 - (StartingIndex & 7));
 480     }
 481     else
 482     {
 483       /* Clear from the start bit, possibly into the next byte also */
 484       USHORT initialWord = ~(NTDLL_maskBits[NumberToClear] << (StartingIndex & 7));
 485
 486       *lpOut++ &= (initialWord & 0xff);
 487       *lpOut &= (initialWord >> 8);
 488       return;
 489     }
 490   }
 491
 492   /* Clear bits (in blocks of 8) on whole byte boundaries */
 493   if (NumberToClear >> 3)
 494   {
 495     memset(lpOut, 0, NumberToClear >> 3);
 496     lpOut = lpOut + (NumberToClear >> 3);
 497   }
 498
 499   /* Clear remaining bits, if any */
 500   if (NumberToClear & 0x7)
 501     *lpOut &= ~NTDLL_maskBits[NumberToClear & 0x7];
 502 }
 503
 504
 505 /*
 506  * @implemented
 507  */
 508 ULONG NTAPI
 509 RtlFindClearBits(PRTL_BITMAP BitMapHeader,
 510                  ULONG NumberToFind,
 511                  ULONG HintIndex)
 512 {
 513   ULONG ulPos, ulEnd;
 514
 515   if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
 516     return ~0U;
 517
 518   ulEnd = BitMapHeader->SizeOfBitMap;
 519
 520   if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
 521     HintIndex = 0;
 522
 523   ulPos = HintIndex;
 524
 525   while (ulPos < ulEnd)
 526   {
 527     /* FIXME: This could be made a _lot_ more efficient */
 528     if (RtlAreBitsClear(BitMapHeader, ulPos, NumberToFind))
 529       return ulPos;
 530
 531     /* Start from the beginning if we hit the end and started from HintIndex */
 532     if (ulPos == ulEnd - 1 && HintIndex)
 533     {
 534       ulEnd = HintIndex;
 535       ulPos = HintIndex = 0;
 536     }
 537     else
 538       ulPos++;
 539   }
 540   return ~0U;
 541 }
 542
 543
 544
 545
 546
 547
 548
 549 /*
 550  * @implemented
 551  */
 552 ULONG NTAPI
 553 RtlFindClearRuns(PRTL_BITMAP BitMapHeader,
 554                  PRTL_BITMAP_RUN RunArray,
 555                  ULONG SizeOfRunArray,
 556                  BOOLEAN LocateLongestRuns)
 557 {
 558     return NTDLL_FindRuns(BitMapHeader, RunArray, SizeOfRunArray, LocateLongestRuns, NTDLL_FindClearRun);
 559 }
 560
 561
 562 /*
 563  * @unimplemented
 564  */
 565 ULONG NTAPI
 566 RtlFindLastBackwardRunClear(IN PRTL_BITMAP BitMapHeader,
 567                             IN ULONG FromIndex,
 568                             IN PULONG StartingRunIndex)
 569 {
 570   UNIMPLEMENTED;
 571   return 0;
 572 }
 573
 574 /*
 575  * @implemented
 576  */
 577 ULONG NTAPI
 578 RtlFindNextForwardRunClear(IN PRTL_BITMAP BitMapHeader,
 579                            IN ULONG FromIndex,
 580                            IN PULONG StartingRunIndex)
 581 {
 582   ULONG ulSize = 0;
 583
 584   if (BitMapHeader && FromIndex < BitMapHeader->SizeOfBitMap && StartingRunIndex)
 585     *StartingRunIndex = NTDLL_FindClearRun(BitMapHeader, FromIndex, &ulSize);
 586
 587   return ulSize;
 588 }
 589
 590 /*
 591  * @implemented
 592  */
 593 ULONG NTAPI
 594 RtlFindFirstRunSet(IN PRTL_BITMAP BitMapHeader,
 595                    IN PULONG StartingIndex)
 596 {
 597   ULONG Size;
 598   ULONG Index;
 599   ULONG Count;
 600   PULONG Ptr;
 601   ULONG  Mask;
 602
 603   Size = BitMapHeader->SizeOfBitMap;
 604   if (*StartingIndex > Size)
 605   {
 606     *StartingIndex = (ULONG)-1;
 607     return 0;
 608   }
 609
 610   Index = *StartingIndex;
 611   Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
 612   Mask = 1 << (Index & 0x1F);
 613
 614   /* Skip clear bits */
 615   for (; Index < Size && ~*Ptr & Mask; Index++)
 616   {
 617     Mask <<= 1;
 618
 619     if (Mask == 0)
 620     {
 621       Mask = 1;
 622       Ptr++;
 623     }
 624   }
 625
 626   /* Return index of first set bit */
 627   if (Index >= Size)
 628   {
 629     *StartingIndex = (ULONG)-1;
 630     return 0;
 631   }
 632   else
 633   {
 634     *StartingIndex = Index;
 635   }
 636
 637   /* Count set bits */
 638   for (Count = 0; Index < Size && *Ptr & Mask; Index++)
 639   {
 640     Count++;
 641     Mask <<= 1;
 642
 643     if (Mask == 0)
 644     {
 645       Mask = 1;
 646       Ptr++;
 647     }
 648   }
 649
 650   return Count;
 651 }
 652
 653
 654 /*
 655  * @implemented
 656  */
 657 ULONG NTAPI
 658 RtlFindLongestRunClear(PRTL_BITMAP BitMapHeader,
 659                        PULONG StartingIndex)
 660 {
 661   RTL_BITMAP_RUN br;
 662
 663   if (RtlFindClearRuns(BitMapHeader, &br, 1, TRUE) == 1)
 664   {
 665     if (StartingIndex)
 666       *StartingIndex = br.StartingIndex;
 667     return br.NumberOfBits;
 668   }
 669   return 0;
 670 }
 671
 672
 673 /*
 674  * @implemented
 675  */
 676 ULONG NTAPI
 677 RtlFindLongestRunSet(PRTL_BITMAP BitMapHeader,
 678                      PULONG StartingIndex)
 679 {
 680   RTL_BITMAP_RUN br;
 681
 682   if (NTDLL_FindRuns(BitMapHeader, &br, 1, TRUE, NTDLL_FindSetRun) == 1)
 683   {
 684     if (StartingIndex)
 685       *StartingIndex = br.StartingIndex;
 686     return br.NumberOfBits;
 687   }
 688   return 0;
 689 }
 690
 691
 692 /*
 693  * @implemented
 694  */
 695 ULONG NTAPI
 696 RtlFindSetBits(PRTL_BITMAP BitMapHeader,
 697                ULONG NumberToFind,
 698                ULONG HintIndex)
 699 {
 700   ULONG ulPos, ulEnd;
 701
 702   if (!BitMapHeader || !NumberToFind || NumberToFind > BitMapHeader->SizeOfBitMap)
 703     return ~0U;
 704
 705   ulEnd = BitMapHeader->SizeOfBitMap;
 706
 707   if (HintIndex + NumberToFind > BitMapHeader->SizeOfBitMap)
 708     HintIndex = 0;
 709
 710   ulPos = HintIndex;
 711
 712   while (ulPos < ulEnd)
 713   {
 714     /* FIXME: This could be made a _lot_ more efficient */
 715     if (RtlAreBitsSet(BitMapHeader, ulPos, NumberToFind))
 716       return ulPos;
 717
 718     /* Start from the beginning if we hit the end and had a hint */
 719     if (ulPos == ulEnd - 1 && HintIndex)
 720     {
 721       ulEnd = HintIndex;
 722       ulPos = HintIndex = 0;
 723     }
 724     else
 725       ulPos++;
 726   }
 727   return ~0U;
 728 }
 729
 730
 731 /*
 732  * @implemented
 733  */
 734 ULONG NTAPI
 735 RtlFindSetBitsAndClear(PRTL_BITMAP BitMapHeader,
 736                        ULONG NumberToFind,
 737                        ULONG HintIndex)
 738 {
 739   ULONG ulPos;
 740
 741   ulPos = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
 742   if (ulPos != ~0U)
 743     RtlClearBits(BitMapHeader, ulPos, NumberToFind);
 744   return ulPos;
 745 }
 746
 747
 748
 749
 750
 751 /*
 752  * @implemented
 753  */
 754 ULONG NTAPI
 755 RtlNumberOfSetBits(PRTL_BITMAP BitMapHeader)
 756 {
 757   ULONG ulSet = 0;
 758
 759   if (BitMapHeader)
 760   {
 761     LPBYTE lpOut = (BYTE *)BitMapHeader->Buffer;
 762     ULONG Length, ulRemainder;
 763     BYTE bMasked;
 764
 765     Length = BitMapHeader->SizeOfBitMap >> 3;
 766     ulRemainder = BitMapHeader->SizeOfBitMap & 0x7;
 767
 768     while (Length--)
 769     {
 770       ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
 771       ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
 772       lpOut++;
 773     }
 774
 775     bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
 776     ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
 777     ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
 778   }
 779   return ulSet;
 780 }
 781
 782
 783 /*
 784  * @implemented
 785  */
 786 VOID NTAPI
 787 RtlSetAllBits(IN OUT PRTL_BITMAP BitMapHeader)
 788 {
 789   memset(BitMapHeader->Buffer, 0xff, ((BitMapHeader->SizeOfBitMap + 31) & ~31) >> 3);
 790 }
 791
 792
 793 /*
 794  * @implemented
 795  */
 796 VOID NTAPI
 797 RtlSetBit(PRTL_BITMAP BitMapHeader,
 798           ULONG BitNumber)
 799 {
 800   PULONG Ptr;
 801
 802   if (BitNumber >= BitMapHeader->SizeOfBitMap)
 803     return;
 804
 805   Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 806
 807   *Ptr |= (1 << (BitNumber % 32));
 808 }
 809
 810
 811 /*
 812  * @implemented
 813  */
 814 VOID NTAPI
 815 RtlSetBits(PRTL_BITMAP BitMapHeader,
 816            ULONG StartingIndex,
 817            ULONG NumberToSet)
 818 {
 819   LPBYTE lpOut;
 820
 821   if (!BitMapHeader || !NumberToSet ||
 822       StartingIndex >= BitMapHeader->SizeOfBitMap ||
 823       NumberToSet > BitMapHeader->SizeOfBitMap - StartingIndex)
 824     return;
 825
 826   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 827    * at a time. But beware of the pointer arithmetics...
 828    */
 829   lpOut = ((BYTE*)BitMapHeader->Buffer) + (StartingIndex >> 3u);
 830
 831   /* Set bits in first byte, if StartingIndex isn't a byte boundary */
 832   if (StartingIndex & 7)
 833   {
 834     if (NumberToSet > 7)
 835     {
 836       /* Set from start bit to the end of the byte */
 837       *lpOut++ |= 0xff << (StartingIndex & 7);
 838       NumberToSet -= (8 - (StartingIndex & 7));
 839     }
 840     else
 841     {
 842       /* Set from the start bit, possibly into the next byte also */
 843       USHORT initialWord = NTDLL_maskBits[NumberToSet] << (StartingIndex & 7);
 844
 845       *lpOut++ |= (initialWord & 0xff);
 846       *lpOut |= (initialWord >> 8);
 847       return;
 848     }
 849   }
 850
 851   /* Set bits up to complete byte count */
 852   if (NumberToSet >> 3)
 853   {
 854     memset(lpOut, 0xff, NumberToSet >> 3);
 855     lpOut = lpOut + (NumberToSet >> 3);
 856   }
 857
 858   /* Set remaining bits, if any */
 859   *lpOut |= NTDLL_maskBits[NumberToSet & 0x7];
 860 }
 861
 862
 863 /*
 864  * @implemented
 865  */
 866 BOOLEAN NTAPI
 867 RtlTestBit(PRTL_BITMAP BitMapHeader,
 868            ULONG BitNumber)
 869 {
 870   PULONG Ptr;
 871
 872   if (BitNumber >= BitMapHeader->SizeOfBitMap)
 873     return FALSE;
 874
 875   Ptr = (PULONG)BitMapHeader->Buffer + (BitNumber / 32);
 876
 877   return (BOOLEAN)(*Ptr & (1 << (BitNumber % 32)));
 878 }
 879
 880 /*
 881  * @implemented
 882  */
 883 ULONG NTAPI
 884 RtlFindFirstRunClear(PRTL_BITMAP BitMapHeader,
 885                      PULONG StartingIndex)
 886 {
 887     return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
 888 }
 889
 890 /*
 891  * @implemented
 892  */
 893 ULONG NTAPI
 894 RtlNumberOfClearBits(PRTL_BITMAP BitMapHeader)
 895 {
 896
 897   if (BitMapHeader)
 898     return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
 899   return 0;
 900 }
 901
 902 /*
 903  * @implemented
 904  */
 905 ULONG NTAPI
 906 RtlFindClearBitsAndSet(PRTL_BITMAP BitMapHeader,
 907                        ULONG NumberToFind,
 908                        ULONG HintIndex)
 909 {
 910   ULONG ulPos;
 911
 912   ulPos = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
 913   if (ulPos != ~0U)
 914     RtlSetBits(BitMapHeader, ulPos, NumberToFind);
 915   return ulPos;
 916 }
 917
 918 /*
 919  * @implemented
 920  */
 921 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
 922 {
 923     signed char ret = 32;
 924     DWORD dw;
 925
 926     if (!(dw = (DWORD)(ulLong >> 32)))
 927     {
 928         ret = 0;
 929         dw = (DWORD)ulLong;
 930     }
 931     if (dw & 0xffff0000)
 932     {
 933         dw >>= 16;
 934         ret += 16;
 935     }
 936     if (dw & 0xff00)
 937     {
 938         dw >>= 8;
 939         ret += 8;
 940     }
 941     if (dw & 0xf0)
 942     {
 943         dw >>= 4;
 944         ret += 4;
 945     }
 946     return ret + NTDLL_mostSignificant[dw];
 947 }
 948
 949 /*
 950  * @implemented
 951  */
 952 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
 953 {
 954     signed char ret = 0;
 955     DWORD dw;
 956
 957     if (!(dw = (DWORD)ulLong))
 958     {
 959         ret = 32;
 960         if (!(dw = (DWORD)(ulLong >> 32))) return -1;
 961     }
 962     if (!(dw & 0xffff))
 963     {
 964         dw >>= 16;
 965         ret += 16;
 966     }
 967     if (!(dw & 0xff))
 968     {
 969         dw >>= 8;
 970         ret += 8;
 971     }
 972     if (!(dw & 0x0f))
 973     {
 974         dw >>= 4;
 975         ret += 4;
 976     }
 977     return ret + NTDLL_leastSignificant[dw & 0x0f];
 978 }
 979
 980 /* EOF */