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