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