dlls/ntdll/rtlbitmap.c

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