dlls/ntdll/rtlbitmap.c

   1 /*
   2  * NTDLL bitmap functions
   3  *
   4  * Copyright 2002 Jon Griffiths
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  * NOTES
  21  *  Bitmaps are an efficient type for manipulating large arrays of bits. They
  22  *  are commonly used by device drivers (e.g. For holding dirty/free blocks),
  23  *  but are also available to applications that need this functionality.
  24  *
  25  *  Bits are set LSB to MSB in each consecutive byte, making this implementation
  26  *  binary compatable with Win32.
  27  *
  28  *  Note that to avoid unexpected behaviour, the size of a bitmap should be set
  29  *  to a multiple of 32.
  30  */
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include "windef.h"
  34 #include "ntddk.h"
  35 #include "wine/debug.h"
  36
  37 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
  38
  39 /* Bits set from LSB to MSB; used as mask for runs < 8 bits */
  40 static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
  41
  42 /* Number of set bits for each value of a nibble; used for counting */
  43 static const BYTE NTDLL_nibbleBitCount[16] = {
  44   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  45 };
  46
  47 /* First set bit in a nibble; used for determining least significant bit */
  48 static const BYTE NTDLL_leastSignificant[16] = {
  49   0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  50 };
  51
  52 /* Last set bit in a nibble; used for determining most significant bit */
  53 static const BYTE NTDLL_mostSignificant[16] = {
  54   0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
  55 };
  56
  57 /*************************************************************************
  58  * RtlInitializeBitMap  [NTDLL.@]
  59  *
  60  * Initialise a new bitmap.
  61  *
  62  * PARAMS
  63  *  lpBits [I] Bitmap pointer
  64  *  lpBuff [I] Memory for the bitmap
  65  *  ulSize [I] Size of lpBuff in bits
  66  *
  67  * RETURNS
  68  *  Nothing.
  69  *
  70  * NOTES
  71  *  lpBuff must be aligned on a ULONG suitable boundary, to a multiple of 32 bytes
  72  *  in size (irrespective of ulSize given).
  73  */
  74 #undef RtlInitializeBitMap
  75 VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, LPBYTE lpBuff, ULONG ulSize)
  76 {
  77   TRACE("(%p,%p,%ld)\n", lpBits,lpBuff,ulSize);
  78   lpBits->SizeOfBitMap = ulSize;
  79   lpBits->BitMapBuffer = lpBuff;
  80 }
  81
  82 /*************************************************************************
  83  * RtlSetAllBits        [NTDLL.@]
  84  *
  85  * Set all bits in a bitmap.
  86  *
  87  * PARAMS
  88  *  lpBits [I] Bitmap pointer
  89  *
  90  * RETURNS
  91  *  Nothing.
  92  */
  93 #undef RtlSetAllBits
  94 VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
  95 {
  96   TRACE("(%p)\n", lpBits);
  97   memset(lpBits->BitMapBuffer, 0xff, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 3);
  98 }
  99
 100 /*************************************************************************
 101  * RtlClearAllBits      [NTDLL.@]
 102  *
 103  * Clear all bits in a bitmap.
 104  *
 105  * PARAMS
 106  *  lpBit [I] Bitmap pointer
 107  *
 108  * RETURNS
 109  *  Nothing.
 110  */
 111 #undef RtlClearAllBits
 112 VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
 113 {
 114   TRACE("(%p)\n", lpBits);
 115   memset(lpBits->BitMapBuffer, 0, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 3);
 116 }
 117
 118 /*************************************************************************
 119  * RtlSetBits   [NTDLL.@]
 120  *
 121  * Set a range of bits in a bitmap.
 122  *
 123  * PARAMS
 124  *  lpBits  [I] Bitmap pointer
 125  *  ulStart [I] First bit to set
 126  *  ulCount [I] Number of consecutive bits to set
 127  *
 128  * RETURNS
 129  *  Nothing.
 130  */
 131 VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 132 {
 133   LPBYTE lpOut;
 134
 135   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 136
 137   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 138     return;
 139
 140   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 141
 142   /* Set bits in first byte, if ulStart isn't a byte boundary */
 143   if (ulStart & 7)
 144   {
 145     if (ulCount > 7)
 146     {
 147       /* Set from start bit to the end of the byte */
 148       *lpOut++ |= 0xff << (ulStart & 7);
 149       ulCount -= (8 - (ulStart & 7));
 150     }
 151     else
 152     {
 153       /* Set from the start bit, possibly into the next byte also */
 154       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 155
 156       *lpOut++ |= (initialWord & 0xff);
 157       *lpOut |= (initialWord >> 8);
 158       return;
 159     }
 160   }
 161
 162   /* Set bits up to complete byte count */
 163   if (ulCount >> 3)
 164   {
 165     memset(lpOut, 0xff, ulCount >> 3);
 166     lpOut = lpOut + (ulCount >> 3);
 167   }
 168
 169   /* Set remaining bits, if any */
 170   *lpOut |= NTDLL_maskBits[ulCount & 0x7];
 171 }
 172
 173 /*************************************************************************
 174  * RtlClearBits [NTDLL.@]
 175  *
 176  * Clear bits in a bitmap.
 177  *
 178  * PARAMS
 179  *  lpBits  [I] Bitmap pointer
 180  *  ulStart [I] First bit to set
 181  *  ulCount [I] Number of consecutive bits to clear
 182  *
 183  * RETURNS
 184  *  Nothing.
 185  */
 186 VOID WINAPI RtlClearBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 187 {
 188   LPBYTE lpOut;
 189
 190   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 191
 192   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 193     return;
 194
 195   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 196
 197   /* Clear bits in first byte, if ulStart isn't a byte boundary */
 198   if (ulStart & 7)
 199   {
 200     if (ulCount > 7)
 201     {
 202       /* Clear from start bit to the end of the byte */
 203       *lpOut++ &= ~(0xff << (ulStart & 7));
 204       ulCount -= (8 - (ulStart & 7));
 205     }
 206     else
 207     {
 208       /* Clear from the start bit, possibly into the next byte also */
 209       USHORT initialWord = ~(NTDLL_maskBits[ulCount] << (ulStart & 7));
 210
 211       *lpOut++ &= (initialWord & 0xff);
 212       *lpOut &= (initialWord >> 8);
 213       return;
 214     }
 215   }
 216
 217   /* Clear bits (in blocks of 8) on whole byte boundaries */
 218   if (ulCount >> 3)
 219   {
 220     memset(lpOut, 0, ulCount >> 3);
 221     lpOut = lpOut + (ulCount >> 3);
 222   }
 223
 224   /* Clear remaining bits, if any */
 225   if (ulCount & 0x7)
 226     *lpOut &= ~NTDLL_maskBits[ulCount & 0x7];
 227 }
 228
 229 /*************************************************************************
 230  * RtlAreBitsSet        [NTDLL.@]
 231  *
 232  * Determine if part of a bitmap is set.
 233  *
 234  * PARAMS
 235  *  lpBits  [I] Bitmap pointer
 236  *  ulStart [I] First bit to check from
 237  *  ulCount [I] Number of consecutive bits to check
 238  *
 239  * RETURNS
 240  *  TRUE,  If ulCount bits from ulStart are set.
 241  *  FALSE, Otherwise.
 242  */
 243 BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 244 {
 245   LPBYTE lpOut;
 246   ULONG ulRemainder;
 247
 248   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 249
 250   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 251     return FALSE;
 252
 253   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 254
 255   /* Check bits in first byte, if ulStart isn't a byte boundary */
 256   if (ulStart & 7)
 257   {
 258     if (ulCount > 7)
 259     {
 260       /* Check from start bit to the end of the byte */
 261       if ((*lpOut &
 262           ((0xff << (ulStart & 7))) & 0xff) != ((0xff << (ulStart & 7) & 0xff)))
 263         return FALSE;
 264       lpOut++;
 265       ulCount -= (8 - (ulStart & 7));
 266     }
 267     else
 268     {
 269       /* Check from the start bit, possibly into the next byte also */
 270       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 271
 272       if ((*lpOut & (initialWord & 0xff)) != (initialWord & 0xff))
 273         return FALSE;
 274       if ((initialWord & 0xff00) &&
 275           ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
 276         return FALSE;
 277       return TRUE;
 278     }
 279   }
 280
 281   /* Check bits in blocks of 8 bytes */
 282   ulRemainder = ulCount & 7;
 283   ulCount >>= 3;
 284   while (ulCount--)
 285   {
 286     if (*lpOut++ != 0xff)
 287       return FALSE;
 288   }
 289
 290   /* Check remaining bits, if any */
 291   if (ulRemainder &&
 292       (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
 293     return FALSE;
 294   return TRUE;
 295 }
 296
 297 /*************************************************************************
 298  * RtlAreBitsClear      [NTDLL.@]
 299  *
 300  * Determine if part of a bitmap is clear.
 301  *
 302  * PARAMS
 303  *  lpBits  [I] Bitmap pointer
 304  *  ulStart [I] First bit to check from
 305  *  ulCount [I] Number of consecutive bits to check
 306  *
 307  * RETURNS
 308  *  TRUE,  If ulCount bits from ulStart are clear.
 309  *  FALSE, Otherwise.
 310  */
 311 BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 312 {
 313   LPBYTE lpOut;
 314   ULONG ulRemainder;
 315
 316   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 317
 318   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 319     return FALSE;
 320
 321   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 322
 323   /* Check bits in first byte, if ulStart isn't a byte boundary */
 324   if (ulStart & 7)
 325   {
 326     if (ulCount > 7)
 327     {
 328       /* Check from start bit to the end of the byte */
 329       if (*lpOut & ((0xff << (ulStart & 7)) & 0xff))
 330         return FALSE;
 331       lpOut++;
 332       ulCount -= (8 - (ulStart & 7));
 333     }
 334     else
 335     {
 336       /* Check from the start bit, possibly into the next byte also */
 337       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 338
 339       if (*lpOut & (initialWord & 0xff))
 340         return FALSE;
 341       if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
 342         return FALSE;
 343       return TRUE;
 344     }
 345   }
 346
 347   /* Check bits in blocks of 8 bytes */
 348   ulRemainder = ulCount & 7;
 349   ulCount >>= 3;
 350   while (ulCount--)
 351   {
 352     if (*lpOut++)
 353       return FALSE;
 354   }
 355
 356   /* Check remaining bits, if any */
 357   if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
 358     return FALSE;
 359   return TRUE;
 360 }
 361
 362 /*************************************************************************
 363  * RtlFindSetBits       [NTDLL.@]
 364  *
 365  * Find a block of set bits in a bitmap.
 366  *
 367  * PARAMS
 368  *  lpBits  [I] Bitmap pointer
 369  *  ulCount [I] Number of consecutive set bits to find
 370  *  ulHint  [I] Suggested starting position for set bits
 371  *
 372  * RETURNS
 373  *  The bit at which the match was found, or -1 if no match was found.
 374  */
 375 ULONG WINAPI RtlFindSetBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 376 {
 377   ULONG ulPos, ulEnd;
 378
 379   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 380
 381   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 382     return -1u;
 383
 384   ulEnd = lpBits->SizeOfBitMap;
 385
 386   if (ulHint + ulCount > lpBits->SizeOfBitMap)
 387     ulHint = 0;
 388
 389   ulPos = ulHint;
 390
 391   while (ulPos < ulEnd)
 392   {
 393     /* FIXME: This could be made a _lot_ more efficient */
 394     if (RtlAreBitsSet(lpBits, ulPos, ulCount))
 395       return ulPos;
 396
 397     /* Start from the beginning if we hit the end and had a hint */
 398     if (ulPos == ulEnd - 1 && ulHint)
 399     {
 400       ulEnd = ulHint;
 401       ulPos = ulHint = 0;
 402     }
 403     else
 404       ulPos++;
 405   }
 406   return -1u;
 407 }
 408
 409 /*************************************************************************
 410  * RtlFindClearBits     [NTDLL.@]
 411  *
 412  * Find a block of clear bits in a bitmap.
 413  *
 414  * PARAMS
 415  *  lpBits  [I] Bitmap pointer
 416  *  ulCount [I] Number of consecutive clear bits to find
 417  *  ulHint  [I] Suggested starting position for clear bits
 418  *
 419  * RETURNS
 420  *  The bit at which the match was found, or -1 if no match was found.
 421  */
 422 ULONG WINAPI RtlFindClearBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 423 {
 424   ULONG ulPos, ulEnd;
 425
 426   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 427
 428   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 429     return -1u;
 430
 431   ulEnd = lpBits->SizeOfBitMap;
 432
 433   if (ulHint + ulCount > lpBits->SizeOfBitMap)
 434     ulHint = 0;
 435
 436   ulPos = ulHint;
 437
 438   while (ulPos < ulEnd)
 439   {
 440     /* FIXME: This could be made a _lot_ more efficient */
 441     if (RtlAreBitsClear(lpBits, ulPos, ulCount))
 442       return ulPos;
 443
 444     /* Start from the beginning if we hit the end and started from ulHint */
 445     if (ulPos == ulEnd - 1 && ulHint)
 446     {
 447       ulEnd = ulHint;
 448       ulPos = ulHint = 0;
 449     }
 450     else
 451       ulPos++;
 452   }
 453   return -1u;
 454 }
 455
 456 /*************************************************************************
 457  * RtlFindSetBitsAndClear       [NTDLL.@]
 458  *
 459  * Find a block of set bits in a bitmap, and clear them if found.
 460  *
 461  * PARAMS
 462  *  lpBits  [I] Bitmap pointer
 463  *  ulCount [I] Number of consecutive set bits to find
 464  *  ulHint  [I] Suggested starting position for set bits
 465  *
 466  * RETURNS
 467  *  The bit at which the match was found, or -1 if no match was found.
 468  */
 469 ULONG WINAPI RtlFindSetBitsAndClear(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 470 {
 471   ULONG ulPos;
 472
 473   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 474
 475   ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
 476   if (ulPos != -1u)
 477     RtlClearBits(lpBits, ulPos, ulCount);
 478   return ulPos;
 479 }
 480
 481 /*************************************************************************
 482  * RtlFindClearBitsAndSet       [NTDLL.@]
 483  *
 484  * Find a block of clear bits in a bitmap, and set them if found.
 485  *
 486  * PARAMS
 487  *  lpBits  [I] Bitmap pointer
 488  *  ulCount [I] Number of consecutive clear bits to find
 489  *  ulHint  [I] Suggested starting position for clear bits
 490  *
 491  * RETURNS
 492  *  The bit at which the match was found, or -1 if no match was found.
 493  */
 494 ULONG WINAPI RtlFindClearBitsAndSet(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 495 {
 496   ULONG ulPos;
 497
 498   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 499
 500   ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
 501   if (ulPos != -1u)
 502     RtlSetBits(lpBits, ulPos, ulCount);
 503   return ulPos;
 504 }
 505
 506 /*************************************************************************
 507  * RtlNumberOfSetBits   [NTDLL.@]
 508  *
 509  * Find the number of set bits in a bitmap.
 510  *
 511  * PARAMS
 512  *  lpBits [I] Bitmap pointer
 513  *
 514  * RETURNS
 515  *  The number of set bits.
 516  */
 517 ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP lpBits)
 518 {
 519   ULONG ulSet = 0;
 520
 521   TRACE("(%p)\n", lpBits);
 522
 523   if (lpBits)
 524   {
 525     LPBYTE lpOut = lpBits->BitMapBuffer;
 526     ULONG ulCount, ulRemainder;
 527     BYTE bMasked;
 528
 529     ulCount = lpBits->SizeOfBitMap >> 3;
 530     ulRemainder = lpBits->SizeOfBitMap & 0x7;
 531
 532     while (ulCount--)
 533     {
 534       ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
 535       ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
 536       lpOut++;
 537     }
 538
 539     bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
 540     ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
 541     ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
 542   }
 543   return ulSet;
 544 }
 545
 546 /*************************************************************************
 547  * RtlNumberOfClearBits [NTDLL.@]
 548  *
 549  * Find the number of clear bits in a bitmap.
 550  *
 551  * PARAMS
 552  *  lpBits [I] Bitmap pointer
 553  *
 554  * RETURNS
 555  *  The number of clear bits.
 556  */
 557 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
 558 {
 559   TRACE("(%p)\n", lpBits);
 560
 561   if (lpBits)
 562     return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
 563   return 0;
 564 }
 565
 566 /*************************************************************************
 567  * RtlFindMostSignificantBit    [NTDLL.@]
 568  *
 569  * Find the most significant bit in a 64 bit integer.
 570  *
 571  * PARAMS
 572  *  lpBits  [I] Bitmap pointer
 573  *  ulStart [I] First bit to search from
 574  *
 575  * RETURNS
 576  *  The position of the most significant bit.
 577  */
 578 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
 579 {
 580   LONG lCount = 64;
 581   LPBYTE lpOut = (LPBYTE)&ulLong + 7;
 582
 583   TRACE("(%lld)\n", ulLong);
 584
 585   if (!(ulLong & 0xffffffff00000000ul))
 586   {
 587     lpOut -= 4;
 588     lCount -= 32;
 589   }
 590
 591   for (; lCount > 0; lCount -= 8)
 592   {
 593     if (*lpOut)
 594     {
 595       if (*lpOut & 0x0f)
 596         return lCount - 8 + NTDLL_mostSignificant[*lpOut & 0x0f];
 597       return lCount - 4 + NTDLL_mostSignificant[*lpOut >> 4];
 598     }
 599     lpOut--;
 600   }
 601   return -1;
 602 }
 603
 604 /*************************************************************************
 605  * RtlFindLeastSignificantBit   [NTDLL.@]
 606  *
 607  * Find the least significant bit in a 64 bit integer.
 608  *
 609  * PARAMS
 610  *  lpBits  [I] Bitmap pointer
 611  *  ulStart [I] First bit to search from
 612  *
 613  * RETURNS
 614  *  The position of the least significant bit.
 615  */
 616 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
 617 {
 618   ULONG ulCount = 0;
 619   LPBYTE lpOut = (LPBYTE)&ulLong;
 620
 621   TRACE("(%lld)\n", ulLong);
 622
 623   if (!(ulLong & 0xffffffff))
 624   {
 625     lpOut += 4;
 626     ulCount = 32;
 627   }
 628
 629   for (; ulCount < 64; ulCount += 8)
 630   {
 631     if (*lpOut)
 632     {
 633       if (*lpOut & 0x0f)
 634         return ulCount + NTDLL_leastSignificant[*lpOut & 0x0f];
 635       return ulCount + 4 + NTDLL_leastSignificant[*lpOut >> 4];
 636     }
 637     lpOut++;
 638   }
 639   return -1;
 640 }
 641
 642 /*************************************************************************
 643  * NTDLL_RunSortFn
 644  *
 645  * Internal helper: qsort comparason function for RTL_BITMAP_RUN arrays
 646  */
 647 static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
 648 {
 649   if (((PCRTL_BITMAP_RUN)lhs)->SizeOfRun > ((PRTL_BITMAP_RUN)rhs)->SizeOfRun)
 650     return -1;
 651   return 1;
 652 }
 653
 654 /*************************************************************************
 655  * NTDLL_FindSetRun
 656  *
 657  * Internal helper: Find the next run of set bits in a bitmap.
 658  */
 659 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 660 {
 661   LPBYTE lpOut;
 662   ULONG ulFoundAt = 0, ulCount = 0;
 663
 664   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 665
 666   while (1)
 667   {
 668     /* Check bits in first byte */
 669     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 670     const BYTE bFirst = *lpOut & bMask;
 671
 672     if (bFirst)
 673     {
 674       /* Have a set bit in first byte */
 675       if (bFirst != bMask)
 676       {
 677         /* Not every bit is set */
 678         ULONG ulOffset;
 679
 680         if (bFirst & 0x0f)
 681           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 682         else
 683           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 684         ulStart += ulOffset;
 685         ulFoundAt = ulStart;
 686         for (;ulOffset < 8; ulOffset++)
 687         {
 688           if (!(bFirst & (1 << ulOffset)))
 689           {
 690             *lpSize = ulCount;
 691             return ulFoundAt; /* Set from start, but not until the end */
 692           }
 693           ulCount++;
 694           ulStart++;
 695         }
 696         /* Set to the end - go on to count further bits */
 697         lpOut++;
 698         break;
 699       }
 700       /* every bit from start until the end of the byte is set */
 701       ulFoundAt = ulStart;
 702       ulCount = 8 - (ulStart & 7);
 703       ulStart = (ulStart & ~7u) + 8;
 704       lpOut++;
 705       break;
 706     }
 707     ulStart = (ulStart & ~7u) + 8;
 708     lpOut++;
 709     if (ulStart >= lpBits->SizeOfBitMap)
 710       return -1u;
 711   }
 712
 713   /* Count blocks of 8 set bits */
 714   while (*lpOut == 0xff)
 715   {
 716     ulCount += 8;
 717     ulStart += 8;
 718     if (ulStart >= lpBits->SizeOfBitMap)
 719     {
 720       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 721       return ulFoundAt;
 722     }
 723     lpOut++;
 724   }
 725
 726   /* Count remaining contigious bits, if any */
 727   if (*lpOut & 1)
 728   {
 729     ULONG ulOffset = 0;
 730
 731     for (;ulOffset < 7u; ulOffset++)
 732     {
 733       if (!(*lpOut & (1 << ulOffset)))
 734         break;
 735       ulCount++;
 736     }
 737   }
 738   *lpSize = ulCount;
 739   return ulFoundAt;
 740 }
 741
 742 /*************************************************************************
 743  * NTDLL_FindClearRun
 744  *
 745  * Internal helper: Find the next run of set bits in a bitmap.
 746  */
 747 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 748 {
 749   LPBYTE lpOut;
 750   ULONG ulFoundAt = 0, ulCount = 0;
 751
 752   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 753
 754   while (1)
 755   {
 756     /* Check bits in first byte */
 757     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 758     const BYTE bFirst = (~*lpOut) & bMask;
 759
 760     if (bFirst)
 761     {
 762       /* Have a clear bit in first byte */
 763       if (bFirst != bMask)
 764       {
 765         /* Not every bit is clear */
 766         ULONG ulOffset;
 767
 768         if (bFirst & 0x0f)
 769           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 770         else
 771           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 772         ulStart += ulOffset;
 773         ulFoundAt = ulStart;
 774         for (;ulOffset < 8; ulOffset++)
 775         {
 776           if (!(bFirst & (1 << ulOffset)))
 777           {
 778             *lpSize = ulCount;
 779             return ulFoundAt; /* Clear from start, but not until the end */
 780           }
 781           ulCount++;
 782           ulStart++;
 783         }
 784         /* Clear to the end - go on to count further bits */
 785         lpOut++;
 786         break;
 787       }
 788       /* Every bit from start until the end of the byte is clear */
 789       ulFoundAt = ulStart;
 790       ulCount = 8 - (ulStart & 7);
 791       ulStart = (ulStart & ~7u) + 8;
 792       lpOut++;
 793       break;
 794     }
 795     ulStart = (ulStart & ~7u) + 8;
 796     lpOut++;
 797     if (ulStart >= lpBits->SizeOfBitMap)
 798       return -1u;
 799   }
 800
 801   /* Count blocks of 8 clear bits */
 802   while (!*lpOut)
 803   {
 804     ulCount += 8;
 805     ulStart += 8;
 806     if (ulStart >= lpBits->SizeOfBitMap)
 807     {
 808       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 809       return ulFoundAt;
 810     }
 811     lpOut++;
 812   }
 813
 814   /* Count remaining contigious bits, if any */
 815   if (!(*lpOut & 1))
 816   {
 817     ULONG ulOffset = 0;
 818
 819     for (;ulOffset < 7u; ulOffset++)
 820     {
 821       if (*lpOut & (1 << ulOffset))
 822         break;
 823       ulCount++;
 824     }
 825   }
 826   *lpSize = ulCount;
 827   return ulFoundAt;
 828 }
 829
 830 /*************************************************************************
 831  * RtlFindNextForwardRunSet     [NTDLL.@]
 832  *
 833  * Find the next run of set bits in a bitmap.
 834  *
 835  * PARAMS
 836  *  lpBits  [I] Bitmap pointer
 837  *  ulStart [I] Bit position to start searching from
 838  *  lpPos   [O] Start of run
 839  *
 840  * RETURNS
 841  *  Success: The length of the next set run in the bitmap. lpPos is set to
 842  *           the start of the run.
 843  *  Failure: 0, if no run is found or any parameters are invalid.
 844  */
 845 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 846 {
 847   ULONG ulSize = 0;
 848
 849   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 850
 851   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 852     *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
 853
 854   return ulSize;
 855 }
 856
 857 /*************************************************************************
 858  * RtlFindNextForwardRunClear   [NTDLL.@]
 859  *
 860  * Find the next run of clear bits in a bitmap.
 861  *
 862  * PARAMS
 863  *  lpBits  [I] Bitmap pointer
 864  *  ulStart [I] Bit position to start searching from
 865  *  lpPos   [O] Start of run
 866  *
 867  * RETURNS
 868  *  Success: The length of the next clear run in the bitmap. lpPos is set to
 869  *           the start of the run.
 870  *  Failure: 0, if no run is found or any parameters are invalid.
 871  */
 872 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 873 {
 874   ULONG ulSize = 0;
 875
 876   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 877
 878   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 879     *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
 880
 881   return ulSize;
 882 }
 883
 884 /*************************************************************************
 885  * RtlFindLastBackwardRunSet    [NTDLL.@]
 886  *
 887  * Find a previous run of set bits in a bitmap.
 888  *
 889  * PARAMS
 890  *  lpBits  [I] Bitmap pointer
 891  *  ulStart [I] Bit position to start searching from
 892  *  lpPos   [O] Start of run
 893  *
 894  * RETURNS
 895  *  Success: The length of the previous set run in the bitmap. lpPos is set to
 896  *           the start of the run.
 897  *  Failure: 0, if no run is found or any parameters are invalid.
 898  */
 899 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 900 {
 901   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 902   return 0;
 903 }
 904
 905 /*************************************************************************
 906  * RtlFindLastBackwardRunClear  [NTDLL.@]
 907  *
 908  * Find a previous run of clear bits in a bitmap.
 909  *
 910  * PARAMS
 911  *  lpBits  [I] Bitmap pointer
 912  *  ulStart [I] Bit position to start searching from
 913  *  lpPos   [O] Start of run
 914  *
 915  * RETURNS
 916  *  Success: The length of the previous clear run in the bitmap. lpPos is set
 917  *           to the start of the run.
 918  *  Failure: 0, if no run is found or any parameters are invalid.
 919  */
 920 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 921 {
 922   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 923   return 0;
 924 }
 925
 926 /*************************************************************************
 927  * NTDLL_FindRuns
 928  *
 929  * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
 930  */
 931 static ULONG WINAPI NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
 932                                    ULONG ulCount, BOOLEAN bLongest,
 933                                    ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
 934 {
 935   BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
 936   ULONG ulPos = 0, ulRuns = 0;
 937
 938   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
 939
 940   if (!ulCount)
 941     return -1u;
 942
 943   while (ulPos < lpBits->SizeOfBitMap)
 944   {
 945     /* Find next set/clear run */
 946     ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
 947
 948     if (ulNextPos == -1u)
 949       break;
 950
 951     if (bLongest && ulRuns == ulCount)
 952     {
 953       /* Sort runs with shortest at end, if they are out of order */
 954       if (bNeedSort)
 955         qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
 956
 957       /* Replace last run if this one is bigger */
 958       if (ulSize > lpSeries[ulRuns - 1].SizeOfRun)
 959       {
 960         lpSeries[ulRuns - 1].StartOfRun = ulNextPos;
 961         lpSeries[ulRuns - 1].SizeOfRun = ulSize;
 962
 963         /* We need to re-sort the array, _if_ we didn't leave it sorted */
 964         if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].SizeOfRun)
 965           bNeedSort = TRUE;
 966       }
 967     }
 968     else
 969     {
 970       /* Append to found runs */
 971       lpSeries[ulRuns].StartOfRun = ulNextPos;
 972       lpSeries[ulRuns].SizeOfRun = ulSize;
 973       ulRuns++;
 974
 975       if (!bLongest && ulRuns == ulCount)
 976         break;
 977     }
 978     ulPos = ulNextPos + ulSize;
 979   }
 980   return ulRuns;
 981 }
 982
 983 /*************************************************************************
 984  * RtlFindSetRuns       [NTDLL.@]
 985  *
 986  * Find a series of set runs in a bitmap.
 987  *
 988  * PARAMS
 989  *  lpBits   [I] Bitmap pointer
 990  *  ulSeries [O] Array for each run found
 991  *  ulCount  [I] Number of runs to find
 992  *  bLongest [I] Whether to find the very longest runs or not
 993  *
 994  * RETURNS
 995  *  The number of set runs found.
 996  */
 997 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
 998                             ULONG ulCount, BOOLEAN bLongest)
 999 {
1000   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1001
1002   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1003 }
1004
1005 /*************************************************************************
1006  * RtlFindClearRuns     [NTDLL.@]
1007  *
1008  * Find a series of clear runs in a bitmap.
1009  *
1010  * PARAMS
1011  *  lpBits   [I] Bitmap pointer
1012  *  ulSeries [O] Array for each run found
1013  *  ulCount  [I] Number of runs to find
1014  *  bLongest [I] Whether to find the very longest runs or not
1015  *
1016  * RETURNS
1017  *  The number of clear runs found.
1018  */
1019 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1020                               ULONG ulCount, BOOLEAN bLongest)
1021 {
1022   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1023
1024   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1025 }
1026
1027 /*************************************************************************
1028  * RtlFindLongestRunSet [NTDLL.@]
1029  *
1030  * Find the longest set run in a bitmap.
1031  *
1032  * PARAMS
1033  *  lpBits   [I] Bitmap pointer
1034  *  pulStart [O] Destination for start of run
1035  *
1036  * RETURNS
1037  *  The length of the run found, or 0 if no run is found.
1038  */
1039 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1040 {
1041   RTL_BITMAP_RUN br;
1042
1043   TRACE("(%p,%p)\n", lpBits, pulStart);
1044
1045   if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1046   {
1047     if (pulStart)
1048       *pulStart = br.StartOfRun;
1049     return br.SizeOfRun;
1050   }
1051   return 0;
1052 }
1053
1054 /*************************************************************************
1055  * RtlFindLongestRunClear       [NTDLL.@]
1056  *
1057  * Find the longest clear run in a bitmap.
1058  *
1059  * PARAMS
1060  *  lpBits   [I] Bitmap pointer
1061  *  pulStart [O] Destination for start of run
1062  *
1063  * RETURNS
1064  *  The length of the run found, or 0 if no run is found.
1065  */
1066 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1067 {
1068   RTL_BITMAP_RUN br;
1069
1070   TRACE("(%p,%p)\n", lpBits, pulStart);
1071
1072   if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1073   {
1074     if (pulStart)
1075       *pulStart = br.StartOfRun;
1076     return br.SizeOfRun;
1077   }
1078   return 0;
1079 }