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