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 compatible 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 <stdarg.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include "ntstatus.h"
  35 #include "windef.h"
  36 #include "winbase.h"
  37 #include "winreg.h"
  38 #include "winternl.h"
  39 #include "wine/debug.h"
  40
  41 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
  42
  43 /* Bits set from LSB to MSB; used as mask for runs < 8 bits */
  44 static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
  45
  46 /* Number of set bits for each value of a nibble; used for counting */
  47 static const BYTE NTDLL_nibbleBitCount[16] = {
  48   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  49 };
  50
  51 /* First set bit in a nibble; used for determining least significant bit */
  52 static const BYTE NTDLL_leastSignificant[16] = {
  53   0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  54 };
  55
  56 /* Last set bit in a nibble; used for determining most significant bit */
  57 static const signed char NTDLL_mostSignificant[16] = {
  58   -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
  59 };
  60
  61 /*************************************************************************
  62  * RtlInitializeBitMap  [NTDLL.@]
  63  *
  64  * Initialise a new bitmap.
  65  *
  66  * PARAMS
  67  *  lpBits [I] Bitmap pointer
  68  *  lpBuff [I] Memory for the bitmap
  69  *  ulSize [I] Size of lpBuff in bits
  70  *
  71  * RETURNS
  72  *  Nothing.
  73  *
  74  * NOTES
  75  *  lpBuff must be aligned on a ULONG suitable boundary, to a multiple of 32 bytes
  76  *  in size (irrespective of ulSize given).
  77  */
  78 #undef RtlInitializeBitMap
  79 VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, LPBYTE lpBuff, ULONG ulSize)
  80 {
  81   TRACE("(%p,%p,%ld)\n", lpBits,lpBuff,ulSize);
  82   lpBits->SizeOfBitMap = ulSize;
  83   lpBits->BitMapBuffer = lpBuff;
  84 }
  85
  86 /*************************************************************************
  87  * RtlSetAllBits        [NTDLL.@]
  88  *
  89  * Set all bits in a bitmap.
  90  *
  91  * PARAMS
  92  *  lpBits [I] Bitmap pointer
  93  *
  94  * RETURNS
  95  *  Nothing.
  96  */
  97 #undef RtlSetAllBits
  98 VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
  99 {
 100   TRACE("(%p)\n", lpBits);
 101   memset(lpBits->BitMapBuffer, 0xff, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 3);
 102 }
 103
 104 /*************************************************************************
 105  * RtlClearAllBits      [NTDLL.@]
 106  *
 107  * Clear all bits in a bitmap.
 108  *
 109  * PARAMS
 110  *  lpBit [I] Bitmap pointer
 111  *
 112  * RETURNS
 113  *  Nothing.
 114  */
 115 #undef RtlClearAllBits
 116 VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
 117 {
 118   TRACE("(%p)\n", lpBits);
 119   memset(lpBits->BitMapBuffer, 0, ((lpBits->SizeOfBitMap + 31) & 0xffffffe0) >> 3);
 120 }
 121
 122 /*************************************************************************
 123  * RtlSetBits   [NTDLL.@]
 124  *
 125  * Set a range of bits in a bitmap.
 126  *
 127  * PARAMS
 128  *  lpBits  [I] Bitmap pointer
 129  *  ulStart [I] First bit to set
 130  *  ulCount [I] Number of consecutive bits to set
 131  *
 132  * RETURNS
 133  *  Nothing.
 134  */
 135 VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 136 {
 137   LPBYTE lpOut;
 138
 139   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 140
 141   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 142     return;
 143
 144   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 145
 146   /* Set bits in first byte, if ulStart isn't a byte boundary */
 147   if (ulStart & 7)
 148   {
 149     if (ulCount > 7)
 150     {
 151       /* Set from start bit to the end of the byte */
 152       *lpOut++ |= 0xff << (ulStart & 7);
 153       ulCount -= (8 - (ulStart & 7));
 154     }
 155     else
 156     {
 157       /* Set from the start bit, possibly into the next byte also */
 158       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 159
 160       *lpOut++ |= (initialWord & 0xff);
 161       *lpOut |= (initialWord >> 8);
 162       return;
 163     }
 164   }
 165
 166   /* Set bits up to complete byte count */
 167   if (ulCount >> 3)
 168   {
 169     memset(lpOut, 0xff, ulCount >> 3);
 170     lpOut = lpOut + (ulCount >> 3);
 171   }
 172
 173   /* Set remaining bits, if any */
 174   *lpOut |= NTDLL_maskBits[ulCount & 0x7];
 175 }
 176
 177 /*************************************************************************
 178  * RtlClearBits [NTDLL.@]
 179  *
 180  * Clear bits in a bitmap.
 181  *
 182  * PARAMS
 183  *  lpBits  [I] Bitmap pointer
 184  *  ulStart [I] First bit to set
 185  *  ulCount [I] Number of consecutive bits to clear
 186  *
 187  * RETURNS
 188  *  Nothing.
 189  */
 190 VOID WINAPI RtlClearBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 191 {
 192   LPBYTE lpOut;
 193
 194   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 195
 196   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 197     return;
 198
 199   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 200
 201   /* Clear bits in first byte, if ulStart isn't a byte boundary */
 202   if (ulStart & 7)
 203   {
 204     if (ulCount > 7)
 205     {
 206       /* Clear from start bit to the end of the byte */
 207       *lpOut++ &= ~(0xff << (ulStart & 7));
 208       ulCount -= (8 - (ulStart & 7));
 209     }
 210     else
 211     {
 212       /* Clear from the start bit, possibly into the next byte also */
 213       USHORT initialWord = ~(NTDLL_maskBits[ulCount] << (ulStart & 7));
 214
 215       *lpOut++ &= (initialWord & 0xff);
 216       *lpOut &= (initialWord >> 8);
 217       return;
 218     }
 219   }
 220
 221   /* Clear bits (in blocks of 8) on whole byte boundaries */
 222   if (ulCount >> 3)
 223   {
 224     memset(lpOut, 0, ulCount >> 3);
 225     lpOut = lpOut + (ulCount >> 3);
 226   }
 227
 228   /* Clear remaining bits, if any */
 229   if (ulCount & 0x7)
 230     *lpOut &= ~NTDLL_maskBits[ulCount & 0x7];
 231 }
 232
 233 /*************************************************************************
 234  * RtlAreBitsSet        [NTDLL.@]
 235  *
 236  * Determine if part of a bitmap is set.
 237  *
 238  * PARAMS
 239  *  lpBits  [I] Bitmap pointer
 240  *  ulStart [I] First bit to check from
 241  *  ulCount [I] Number of consecutive bits to check
 242  *
 243  * RETURNS
 244  *  TRUE,  If ulCount bits from ulStart are set.
 245  *  FALSE, Otherwise.
 246  */
 247 BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 248 {
 249   LPBYTE lpOut;
 250   ULONG ulRemainder;
 251
 252   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 253
 254   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 255     return FALSE;
 256
 257   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 258
 259   /* Check bits in first byte, if ulStart isn't a byte boundary */
 260   if (ulStart & 7)
 261   {
 262     if (ulCount > 7)
 263     {
 264       /* Check from start bit to the end of the byte */
 265       if ((*lpOut &
 266           ((0xff << (ulStart & 7))) & 0xff) != ((0xff << (ulStart & 7) & 0xff)))
 267         return FALSE;
 268       lpOut++;
 269       ulCount -= (8 - (ulStart & 7));
 270     }
 271     else
 272     {
 273       /* Check from the start bit, possibly into the next byte also */
 274       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 275
 276       if ((*lpOut & (initialWord & 0xff)) != (initialWord & 0xff))
 277         return FALSE;
 278       if ((initialWord & 0xff00) &&
 279           ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
 280         return FALSE;
 281       return TRUE;
 282     }
 283   }
 284
 285   /* Check bits in blocks of 8 bytes */
 286   ulRemainder = ulCount & 7;
 287   ulCount >>= 3;
 288   while (ulCount--)
 289   {
 290     if (*lpOut++ != 0xff)
 291       return FALSE;
 292   }
 293
 294   /* Check remaining bits, if any */
 295   if (ulRemainder &&
 296       (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
 297     return FALSE;
 298   return TRUE;
 299 }
 300
 301 /*************************************************************************
 302  * RtlAreBitsClear      [NTDLL.@]
 303  *
 304  * Determine if part of a bitmap is clear.
 305  *
 306  * PARAMS
 307  *  lpBits  [I] Bitmap pointer
 308  *  ulStart [I] First bit to check from
 309  *  ulCount [I] Number of consecutive bits to check
 310  *
 311  * RETURNS
 312  *  TRUE,  If ulCount bits from ulStart are clear.
 313  *  FALSE, Otherwise.
 314  */
 315 BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 316 {
 317   LPBYTE lpOut;
 318   ULONG ulRemainder;
 319
 320   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 321
 322   if (!lpBits || !ulCount || ulStart + ulCount > lpBits->SizeOfBitMap)
 323     return FALSE;
 324
 325   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 326
 327   /* Check bits in first byte, if ulStart isn't a byte boundary */
 328   if (ulStart & 7)
 329   {
 330     if (ulCount > 7)
 331     {
 332       /* Check from start bit to the end of the byte */
 333       if (*lpOut & ((0xff << (ulStart & 7)) & 0xff))
 334         return FALSE;
 335       lpOut++;
 336       ulCount -= (8 - (ulStart & 7));
 337     }
 338     else
 339     {
 340       /* Check from the start bit, possibly into the next byte also */
 341       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 342
 343       if (*lpOut & (initialWord & 0xff))
 344         return FALSE;
 345       if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
 346         return FALSE;
 347       return TRUE;
 348     }
 349   }
 350
 351   /* Check bits in blocks of 8 bytes */
 352   ulRemainder = ulCount & 7;
 353   ulCount >>= 3;
 354   while (ulCount--)
 355   {
 356     if (*lpOut++)
 357       return FALSE;
 358   }
 359
 360   /* Check remaining bits, if any */
 361   if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
 362     return FALSE;
 363   return TRUE;
 364 }
 365
 366 /*************************************************************************
 367  * RtlFindSetBits       [NTDLL.@]
 368  *
 369  * Find a block of set bits in a bitmap.
 370  *
 371  * PARAMS
 372  *  lpBits  [I] Bitmap pointer
 373  *  ulCount [I] Number of consecutive set bits to find
 374  *  ulHint  [I] Suggested starting position for set bits
 375  *
 376  * RETURNS
 377  *  The bit at which the match was found, or -1 if no match was found.
 378  */
 379 ULONG WINAPI RtlFindSetBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 380 {
 381   ULONG ulPos, ulEnd;
 382
 383   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 384
 385   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 386     return -1u;
 387
 388   ulEnd = lpBits->SizeOfBitMap;
 389
 390   if (ulHint + ulCount > lpBits->SizeOfBitMap)
 391     ulHint = 0;
 392
 393   ulPos = ulHint;
 394
 395   while (ulPos < ulEnd)
 396   {
 397     /* FIXME: This could be made a _lot_ more efficient */
 398     if (RtlAreBitsSet(lpBits, ulPos, ulCount))
 399       return ulPos;
 400
 401     /* Start from the beginning if we hit the end and had a hint */
 402     if (ulPos == ulEnd - 1 && ulHint)
 403     {
 404       ulEnd = ulHint;
 405       ulPos = ulHint = 0;
 406     }
 407     else
 408       ulPos++;
 409   }
 410   return -1u;
 411 }
 412
 413 /*************************************************************************
 414  * RtlFindClearBits     [NTDLL.@]
 415  *
 416  * Find a block of clear bits in a bitmap.
 417  *
 418  * PARAMS
 419  *  lpBits  [I] Bitmap pointer
 420  *  ulCount [I] Number of consecutive clear bits to find
 421  *  ulHint  [I] Suggested starting position for clear bits
 422  *
 423  * RETURNS
 424  *  The bit at which the match was found, or -1 if no match was found.
 425  */
 426 ULONG WINAPI RtlFindClearBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 427 {
 428   ULONG ulPos, ulEnd;
 429
 430   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 431
 432   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 433     return -1u;
 434
 435   ulEnd = lpBits->SizeOfBitMap;
 436
 437   if (ulHint + ulCount > lpBits->SizeOfBitMap)
 438     ulHint = 0;
 439
 440   ulPos = ulHint;
 441
 442   while (ulPos < ulEnd)
 443   {
 444     /* FIXME: This could be made a _lot_ more efficient */
 445     if (RtlAreBitsClear(lpBits, ulPos, ulCount))
 446       return ulPos;
 447
 448     /* Start from the beginning if we hit the end and started from ulHint */
 449     if (ulPos == ulEnd - 1 && ulHint)
 450     {
 451       ulEnd = ulHint;
 452       ulPos = ulHint = 0;
 453     }
 454     else
 455       ulPos++;
 456   }
 457   return -1u;
 458 }
 459
 460 /*************************************************************************
 461  * RtlFindSetBitsAndClear       [NTDLL.@]
 462  *
 463  * Find a block of set bits in a bitmap, and clear them if found.
 464  *
 465  * PARAMS
 466  *  lpBits  [I] Bitmap pointer
 467  *  ulCount [I] Number of consecutive set bits to find
 468  *  ulHint  [I] Suggested starting position for set bits
 469  *
 470  * RETURNS
 471  *  The bit at which the match was found, or -1 if no match was found.
 472  */
 473 ULONG WINAPI RtlFindSetBitsAndClear(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 474 {
 475   ULONG ulPos;
 476
 477   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 478
 479   ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
 480   if (ulPos != -1u)
 481     RtlClearBits(lpBits, ulPos, ulCount);
 482   return ulPos;
 483 }
 484
 485 /*************************************************************************
 486  * RtlFindClearBitsAndSet       [NTDLL.@]
 487  *
 488  * Find a block of clear bits in a bitmap, and set them if found.
 489  *
 490  * PARAMS
 491  *  lpBits  [I] Bitmap pointer
 492  *  ulCount [I] Number of consecutive clear bits to find
 493  *  ulHint  [I] Suggested starting position for clear bits
 494  *
 495  * RETURNS
 496  *  The bit at which the match was found, or -1 if no match was found.
 497  */
 498 ULONG WINAPI RtlFindClearBitsAndSet(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
 499 {
 500   ULONG ulPos;
 501
 502   TRACE("(%p,%ld,%ld)\n", lpBits, ulCount, ulHint);
 503
 504   ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
 505   if (ulPos != -1u)
 506     RtlSetBits(lpBits, ulPos, ulCount);
 507   return ulPos;
 508 }
 509
 510 /*************************************************************************
 511  * RtlNumberOfSetBits   [NTDLL.@]
 512  *
 513  * Find the number of set bits in a bitmap.
 514  *
 515  * PARAMS
 516  *  lpBits [I] Bitmap pointer
 517  *
 518  * RETURNS
 519  *  The number of set bits.
 520  */
 521 ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP lpBits)
 522 {
 523   ULONG ulSet = 0;
 524
 525   TRACE("(%p)\n", lpBits);
 526
 527   if (lpBits)
 528   {
 529     LPBYTE lpOut = lpBits->BitMapBuffer;
 530     ULONG ulCount, ulRemainder;
 531     BYTE bMasked;
 532
 533     ulCount = lpBits->SizeOfBitMap >> 3;
 534     ulRemainder = lpBits->SizeOfBitMap & 0x7;
 535
 536     while (ulCount--)
 537     {
 538       ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
 539       ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
 540       lpOut++;
 541     }
 542
 543     bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
 544     ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
 545     ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
 546   }
 547   return ulSet;
 548 }
 549
 550 /*************************************************************************
 551  * RtlNumberOfClearBits [NTDLL.@]
 552  *
 553  * Find the number of clear bits in a bitmap.
 554  *
 555  * PARAMS
 556  *  lpBits [I] Bitmap pointer
 557  *
 558  * RETURNS
 559  *  The number of clear bits.
 560  */
 561 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
 562 {
 563   TRACE("(%p)\n", lpBits);
 564
 565   if (lpBits)
 566     return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
 567   return 0;
 568 }
 569
 570 /*************************************************************************
 571  * RtlFindMostSignificantBit    [NTDLL.@]
 572  *
 573  * Find the most significant bit in a 64 bit integer.
 574  *
 575  * RETURNS
 576  *  The position of the most significant bit.
 577  */
 578 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
 579 {
 580     signed char ret = 32;
 581     DWORD dw;
 582
 583     if (!(dw = (ulLong >> 32)))
 584     {
 585         ret = 0;
 586         dw = (DWORD)ulLong;
 587     }
 588     if (dw & 0xffff0000)
 589     {
 590         dw >>= 16;
 591         ret += 16;
 592     }
 593     if (dw & 0xff00)
 594     {
 595         dw >>= 8;
 596         ret += 8;
 597     }
 598     if (dw & 0xf0)
 599     {
 600         dw >>= 4;
 601         ret += 4;
 602     }
 603     return ret + NTDLL_mostSignificant[dw];
 604 }
 605
 606 /*************************************************************************
 607  * RtlFindLeastSignificantBit   [NTDLL.@]
 608  *
 609  * Find the least significant bit in a 64 bit integer.
 610  *
 611  * RETURNS
 612  *  The position of the least significant bit.
 613  */
 614 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
 615 {
 616     signed char ret = 0;
 617     DWORD dw;
 618
 619     if (!(dw = (DWORD)ulLong))
 620     {
 621         ret = 32;
 622         if (!(dw = ulLong >> 32)) return -1;
 623     }
 624     if (!(dw & 0xffff))
 625     {
 626         dw >>= 16;
 627         ret += 16;
 628     }
 629     if (!(dw & 0xff))
 630     {
 631         dw >>= 8;
 632         ret += 8;
 633     }
 634     if (!(dw & 0x0f))
 635     {
 636         dw >>= 4;
 637         ret += 4;
 638     }
 639     return ret + NTDLL_leastSignificant[dw & 0x0f];
 640 }
 641
 642 /*************************************************************************
 643  * NTDLL_RunSortFn
 644  *
 645  * Internal helper: qsort comparison 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 }