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 <stdlib.h>
  32 #include <string.h>
  33 #include "windef.h"
  34 #include "winternl.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 signed char NTDLL_mostSignificant[16] = {
  54   -1, 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  * RETURNS
 572  *  The position of the most significant bit.
 573  */
 574 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
 575 {
 576     signed char ret = 32;
 577     DWORD dw;
 578
 579     if (!(dw = (ulLong >> 32)))
 580     {
 581         ret = 0;
 582         dw = (DWORD)ulLong;
 583     }
 584     if (dw & 0xffff0000)
 585     {
 586         dw >>= 16;
 587         ret += 16;
 588     }
 589     if (dw & 0xff00)
 590     {
 591         dw >>= 8;
 592         ret += 8;
 593     }
 594     if (dw & 0xf0)
 595     {
 596         dw >>= 4;
 597         ret += 4;
 598     }
 599     return ret + NTDLL_mostSignificant[dw];
 600 }
 601
 602 /*************************************************************************
 603  * RtlFindLeastSignificantBit   [NTDLL.@]
 604  *
 605  * Find the least significant bit in a 64 bit integer.
 606  *
 607  * RETURNS
 608  *  The position of the least significant bit.
 609  */
 610 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
 611 {
 612     signed char ret = 0;
 613     DWORD dw;
 614
 615     if (!(dw = (DWORD)ulLong))
 616     {
 617         ret = 32;
 618         if (!(dw = ulLong >> 32)) return -1;
 619     }
 620     if (!(dw & 0xffff))
 621     {
 622         dw >>= 16;
 623         ret += 16;
 624     }
 625     if (!(dw & 0xff))
 626     {
 627         dw >>= 8;
 628         ret += 8;
 629     }
 630     if (!(dw & 0x0f))
 631     {
 632         dw >>= 4;
 633         ret += 4;
 634     }
 635     return ret + NTDLL_leastSignificant[dw & 0x0f];
 636 }
 637
 638 /*************************************************************************
 639  * NTDLL_RunSortFn
 640  *
 641  * Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
 642  */
 643 static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
 644 {
 645   if (((PCRTL_BITMAP_RUN)lhs)->SizeOfRun > ((PRTL_BITMAP_RUN)rhs)->SizeOfRun)
 646     return -1;
 647   return 1;
 648 }
 649
 650 /*************************************************************************
 651  * NTDLL_FindSetRun
 652  *
 653  * Internal helper: Find the next run of set bits in a bitmap.
 654  */
 655 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 656 {
 657   LPBYTE lpOut;
 658   ULONG ulFoundAt = 0, ulCount = 0;
 659
 660   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 661
 662   while (1)
 663   {
 664     /* Check bits in first byte */
 665     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 666     const BYTE bFirst = *lpOut & bMask;
 667
 668     if (bFirst)
 669     {
 670       /* Have a set bit in first byte */
 671       if (bFirst != bMask)
 672       {
 673         /* Not every bit is set */
 674         ULONG ulOffset;
 675
 676         if (bFirst & 0x0f)
 677           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 678         else
 679           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 680         ulStart += ulOffset;
 681         ulFoundAt = ulStart;
 682         for (;ulOffset < 8; ulOffset++)
 683         {
 684           if (!(bFirst & (1 << ulOffset)))
 685           {
 686             *lpSize = ulCount;
 687             return ulFoundAt; /* Set from start, but not until the end */
 688           }
 689           ulCount++;
 690           ulStart++;
 691         }
 692         /* Set to the end - go on to count further bits */
 693         lpOut++;
 694         break;
 695       }
 696       /* every bit from start until the end of the byte is set */
 697       ulFoundAt = ulStart;
 698       ulCount = 8 - (ulStart & 7);
 699       ulStart = (ulStart & ~7u) + 8;
 700       lpOut++;
 701       break;
 702     }
 703     ulStart = (ulStart & ~7u) + 8;
 704     lpOut++;
 705     if (ulStart >= lpBits->SizeOfBitMap)
 706       return -1u;
 707   }
 708
 709   /* Count blocks of 8 set bits */
 710   while (*lpOut == 0xff)
 711   {
 712     ulCount += 8;
 713     ulStart += 8;
 714     if (ulStart >= lpBits->SizeOfBitMap)
 715     {
 716       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 717       return ulFoundAt;
 718     }
 719     lpOut++;
 720   }
 721
 722   /* Count remaining contigious bits, if any */
 723   if (*lpOut & 1)
 724   {
 725     ULONG ulOffset = 0;
 726
 727     for (;ulOffset < 7u; ulOffset++)
 728     {
 729       if (!(*lpOut & (1 << ulOffset)))
 730         break;
 731       ulCount++;
 732     }
 733   }
 734   *lpSize = ulCount;
 735   return ulFoundAt;
 736 }
 737
 738 /*************************************************************************
 739  * NTDLL_FindClearRun
 740  *
 741  * Internal helper: Find the next run of set bits in a bitmap.
 742  */
 743 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 744 {
 745   LPBYTE lpOut;
 746   ULONG ulFoundAt = 0, ulCount = 0;
 747
 748   lpOut = lpBits->BitMapBuffer + (ulStart >> 3u);
 749
 750   while (1)
 751   {
 752     /* Check bits in first byte */
 753     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 754     const BYTE bFirst = (~*lpOut) & bMask;
 755
 756     if (bFirst)
 757     {
 758       /* Have a clear bit in first byte */
 759       if (bFirst != bMask)
 760       {
 761         /* Not every bit is clear */
 762         ULONG ulOffset;
 763
 764         if (bFirst & 0x0f)
 765           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 766         else
 767           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 768         ulStart += ulOffset;
 769         ulFoundAt = ulStart;
 770         for (;ulOffset < 8; ulOffset++)
 771         {
 772           if (!(bFirst & (1 << ulOffset)))
 773           {
 774             *lpSize = ulCount;
 775             return ulFoundAt; /* Clear from start, but not until the end */
 776           }
 777           ulCount++;
 778           ulStart++;
 779         }
 780         /* Clear to the end - go on to count further bits */
 781         lpOut++;
 782         break;
 783       }
 784       /* Every bit from start until the end of the byte is clear */
 785       ulFoundAt = ulStart;
 786       ulCount = 8 - (ulStart & 7);
 787       ulStart = (ulStart & ~7u) + 8;
 788       lpOut++;
 789       break;
 790     }
 791     ulStart = (ulStart & ~7u) + 8;
 792     lpOut++;
 793     if (ulStart >= lpBits->SizeOfBitMap)
 794       return -1u;
 795   }
 796
 797   /* Count blocks of 8 clear bits */
 798   while (!*lpOut)
 799   {
 800     ulCount += 8;
 801     ulStart += 8;
 802     if (ulStart >= lpBits->SizeOfBitMap)
 803     {
 804       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 805       return ulFoundAt;
 806     }
 807     lpOut++;
 808   }
 809
 810   /* Count remaining contigious bits, if any */
 811   if (!(*lpOut & 1))
 812   {
 813     ULONG ulOffset = 0;
 814
 815     for (;ulOffset < 7u; ulOffset++)
 816     {
 817       if (*lpOut & (1 << ulOffset))
 818         break;
 819       ulCount++;
 820     }
 821   }
 822   *lpSize = ulCount;
 823   return ulFoundAt;
 824 }
 825
 826 /*************************************************************************
 827  * RtlFindNextForwardRunSet     [NTDLL.@]
 828  *
 829  * Find the next run of set bits in a bitmap.
 830  *
 831  * PARAMS
 832  *  lpBits  [I] Bitmap pointer
 833  *  ulStart [I] Bit position to start searching from
 834  *  lpPos   [O] Start of run
 835  *
 836  * RETURNS
 837  *  Success: The length of the next set run in the bitmap. lpPos is set to
 838  *           the start of the run.
 839  *  Failure: 0, if no run is found or any parameters are invalid.
 840  */
 841 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 842 {
 843   ULONG ulSize = 0;
 844
 845   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 846
 847   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 848     *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
 849
 850   return ulSize;
 851 }
 852
 853 /*************************************************************************
 854  * RtlFindNextForwardRunClear   [NTDLL.@]
 855  *
 856  * Find the next run of clear bits in a bitmap.
 857  *
 858  * PARAMS
 859  *  lpBits  [I] Bitmap pointer
 860  *  ulStart [I] Bit position to start searching from
 861  *  lpPos   [O] Start of run
 862  *
 863  * RETURNS
 864  *  Success: The length of the next clear run in the bitmap. lpPos is set to
 865  *           the start of the run.
 866  *  Failure: 0, if no run is found or any parameters are invalid.
 867  */
 868 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 869 {
 870   ULONG ulSize = 0;
 871
 872   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 873
 874   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 875     *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
 876
 877   return ulSize;
 878 }
 879
 880 /*************************************************************************
 881  * RtlFindLastBackwardRunSet    [NTDLL.@]
 882  *
 883  * Find a previous run of set bits in a bitmap.
 884  *
 885  * PARAMS
 886  *  lpBits  [I] Bitmap pointer
 887  *  ulStart [I] Bit position to start searching from
 888  *  lpPos   [O] Start of run
 889  *
 890  * RETURNS
 891  *  Success: The length of the previous set run in the bitmap. lpPos is set to
 892  *           the start of the run.
 893  *  Failure: 0, if no run is found or any parameters are invalid.
 894  */
 895 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 896 {
 897   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 898   return 0;
 899 }
 900
 901 /*************************************************************************
 902  * RtlFindLastBackwardRunClear  [NTDLL.@]
 903  *
 904  * Find a previous run of clear bits in a bitmap.
 905  *
 906  * PARAMS
 907  *  lpBits  [I] Bitmap pointer
 908  *  ulStart [I] Bit position to start searching from
 909  *  lpPos   [O] Start of run
 910  *
 911  * RETURNS
 912  *  Success: The length of the previous clear run in the bitmap. lpPos is set
 913  *           to the start of the run.
 914  *  Failure: 0, if no run is found or any parameters are invalid.
 915  */
 916 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 917 {
 918   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 919   return 0;
 920 }
 921
 922 /*************************************************************************
 923  * NTDLL_FindRuns
 924  *
 925  * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
 926  */
 927 static ULONG WINAPI NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
 928                                    ULONG ulCount, BOOLEAN bLongest,
 929                                    ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
 930 {
 931   BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
 932   ULONG ulPos = 0, ulRuns = 0;
 933
 934   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
 935
 936   if (!ulCount)
 937     return -1u;
 938
 939   while (ulPos < lpBits->SizeOfBitMap)
 940   {
 941     /* Find next set/clear run */
 942     ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
 943
 944     if (ulNextPos == -1u)
 945       break;
 946
 947     if (bLongest && ulRuns == ulCount)
 948     {
 949       /* Sort runs with shortest at end, if they are out of order */
 950       if (bNeedSort)
 951         qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
 952
 953       /* Replace last run if this one is bigger */
 954       if (ulSize > lpSeries[ulRuns - 1].SizeOfRun)
 955       {
 956         lpSeries[ulRuns - 1].StartOfRun = ulNextPos;
 957         lpSeries[ulRuns - 1].SizeOfRun = ulSize;
 958
 959         /* We need to re-sort the array, _if_ we didn't leave it sorted */
 960         if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].SizeOfRun)
 961           bNeedSort = TRUE;
 962       }
 963     }
 964     else
 965     {
 966       /* Append to found runs */
 967       lpSeries[ulRuns].StartOfRun = ulNextPos;
 968       lpSeries[ulRuns].SizeOfRun = ulSize;
 969       ulRuns++;
 970
 971       if (!bLongest && ulRuns == ulCount)
 972         break;
 973     }
 974     ulPos = ulNextPos + ulSize;
 975   }
 976   return ulRuns;
 977 }
 978
 979 /*************************************************************************
 980  * RtlFindSetRuns       [NTDLL.@]
 981  *
 982  * Find a series of set runs in a bitmap.
 983  *
 984  * PARAMS
 985  *  lpBits   [I] Bitmap pointer
 986  *  ulSeries [O] Array for each run found
 987  *  ulCount  [I] Number of runs to find
 988  *  bLongest [I] Whether to find the very longest runs or not
 989  *
 990  * RETURNS
 991  *  The number of set runs found.
 992  */
 993 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
 994                             ULONG ulCount, BOOLEAN bLongest)
 995 {
 996   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
 997
 998   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
 999 }
1000
1001 /*************************************************************************
1002  * RtlFindClearRuns     [NTDLL.@]
1003  *
1004  * Find a series of clear runs in a bitmap.
1005  *
1006  * PARAMS
1007  *  lpBits   [I] Bitmap pointer
1008  *  ulSeries [O] Array for each run found
1009  *  ulCount  [I] Number of runs to find
1010  *  bLongest [I] Whether to find the very longest runs or not
1011  *
1012  * RETURNS
1013  *  The number of clear runs found.
1014  */
1015 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1016                               ULONG ulCount, BOOLEAN bLongest)
1017 {
1018   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1019
1020   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1021 }
1022
1023 /*************************************************************************
1024  * RtlFindLongestRunSet [NTDLL.@]
1025  *
1026  * Find the longest set run in a bitmap.
1027  *
1028  * PARAMS
1029  *  lpBits   [I] Bitmap pointer
1030  *  pulStart [O] Destination for start of run
1031  *
1032  * RETURNS
1033  *  The length of the run found, or 0 if no run is found.
1034  */
1035 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1036 {
1037   RTL_BITMAP_RUN br;
1038
1039   TRACE("(%p,%p)\n", lpBits, pulStart);
1040
1041   if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1042   {
1043     if (pulStart)
1044       *pulStart = br.StartOfRun;
1045     return br.SizeOfRun;
1046   }
1047   return 0;
1048 }
1049
1050 /*************************************************************************
1051  * RtlFindLongestRunClear       [NTDLL.@]
1052  *
1053  * Find the longest clear run in a bitmap.
1054  *
1055  * PARAMS
1056  *  lpBits   [I] Bitmap pointer
1057  *  pulStart [O] Destination for start of run
1058  *
1059  * RETURNS
1060  *  The length of the run found, or 0 if no run is found.
1061  */
1062 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1063 {
1064   RTL_BITMAP_RUN br;
1065
1066   TRACE("(%p,%p)\n", lpBits, pulStart);
1067
1068   if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1069   {
1070     if (pulStart)
1071       *pulStart = br.StartOfRun;
1072     return br.SizeOfRun;
1073   }
1074   return 0;
1075 }