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