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