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