git.oblomov.eu Git - wine/blob - 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 "winternl.h"
  37 #include "wine/debug.h"
  38
  39 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
  40
  41 /* Bits set from LSB to MSB; used as mask for runs < 8 bits */
  42 static const BYTE NTDLL_maskBits[8] = { 0, 1, 3, 7, 15, 31, 63, 127 };
  43
  44 /* Number of set bits for each value of a nibble; used for counting */
  45 static const BYTE NTDLL_nibbleBitCount[16] = {
  46   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  47 };
  48
  49 /* First set bit in a nibble; used for determining least significant bit */
  50 static const BYTE NTDLL_leastSignificant[16] = {
  51   0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  52 };
  53
  54 /* Last set bit in a nibble; used for determining most significant bit */
  55 static const signed char NTDLL_mostSignificant[16] = {
  56   -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3
  57 };
  58
  59 /*************************************************************************
  60  * RtlInitializeBitMap  [NTDLL.@]
  61  *
  62  * Initialise a new bitmap.
  63  *
  64  * PARAMS
  65  *  lpBits [I] Bitmap pointer
  66  *  lpBuff [I] Memory for the bitmap
  67  *  ulSize [I] Size of lpBuff in bits
  68  *
  69  * RETURNS
  70  *  Nothing.
  71  *
  72  * NOTES
  73  *  lpBuff must be aligned on a ULONG suitable boundary, to a multiple of 32 bytes
  74  *  in size (irrespective of ulSize given).
  75  */
  76 VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, PULONG lpBuff, ULONG ulSize)
  77 {
  78   TRACE("(%p,%p,%ld)\n", lpBits,lpBuff,ulSize);
  79   lpBits->SizeOfBitMap = ulSize;
  80   lpBits->Buffer = lpBuff;
  81 }
  82
  83 /*************************************************************************
  84  * RtlSetAllBits        [NTDLL.@]
  85  *
  86  * Set all bits in a bitmap.
  87  *
  88  * PARAMS
  89  *  lpBits [I] Bitmap pointer
  90  *
  91  * RETURNS
  92  *  Nothing.
  93  */
  94 VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
  95 {
  96   TRACE("(%p)\n", lpBits);
  97   memset(lpBits->Buffer, 0xff, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
  98 }
  99
 100 /*************************************************************************
 101  * RtlClearAllBits      [NTDLL.@]
 102  *
 103  * Clear all bits in a bitmap.
 104  *
 105  * PARAMS
 106  *  lpBit [I] Bitmap pointer
 107  *
 108  * RETURNS
 109  *  Nothing.
 110  */
 111 VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
 112 {
 113   TRACE("(%p)\n", lpBits);
 114   memset(lpBits->Buffer, 0, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
 115 }
 116
 117 /*************************************************************************
 118  * RtlSetBits   [NTDLL.@]
 119  *
 120  * Set a range of bits in a bitmap.
 121  *
 122  * PARAMS
 123  *  lpBits  [I] Bitmap pointer
 124  *  ulStart [I] First bit to set
 125  *  ulCount [I] Number of consecutive bits to set
 126  *
 127  * RETURNS
 128  *  Nothing.
 129  */
 130 VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
 131 {
 132   LPBYTE lpOut;
 133
 134   TRACE("(%p,%ld,%ld)\n", lpBits, ulStart, ulCount);
 135
 136   if (!lpBits || !ulCount ||
 137       ulStart >= lpBits->SizeOfBitMap ||
 138       ulCount > lpBits->SizeOfBitMap - ulStart)
 139     return;
 140
 141   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 142    * at a time. But beware of the pointer arithmetics...
 143    */
 144   lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
 145
 146   /* Set bits in first byte, if ulStart isn't a byte boundary */
 147   if (ulStart & 7)
 148   {
 149     if (ulCount > 7)
 150     {
 151       /* Set from start bit to the end of the byte */
 152       *lpOut++ |= 0xff << (ulStart & 7);
 153       ulCount -= (8 - (ulStart & 7));
 154     }
 155     else
 156     {
 157       /* Set from the start bit, possibly into the next byte also */
 158       USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
 159
 160       *lpOut++ |= (initialWord & 0xff);
 161       *lpOut |= (initialWord >> 8);
 162       return;
 163     }
 164   }
 165
 166   /* Set bits up to complete byte count */
 167   if (ulCount >> 3)
 168   {
 169     memset(lpOut, 0xff, ulCount >> 3);
 170     lpOut = lpOut + (ulCount >> 3);
 171   }
 172
 173   /* Set remaining bits, if any */
 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,%ld,%ld)\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,%ld,%ld)\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,%ld,%ld)\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,%ld,%ld)\n", lpBits, ulCount, ulHint);
 399
 400   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 401     return ~0UL;
 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 ~0UL;
 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,%ld,%ld)\n", lpBits, ulCount, ulHint);
 446
 447   if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
 448     return ~0UL;
 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 ~0UL;
 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,%ld,%ld)\n", lpBits, ulCount, ulHint);
 493
 494   ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
 495   if (ulPos != ~0UL)
 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,%ld,%ld)\n", lpBits, ulCount, ulHint);
 518
 519   ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
 520   if (ulPos != ~0UL)
 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     bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
 559     ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
 560     ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
 561   }
 562   return ulSet;
 563 }
 564
 565 /*************************************************************************
 566  * RtlNumberOfClearBits [NTDLL.@]
 567  *
 568  * Find the number of clear bits in a bitmap.
 569  *
 570  * PARAMS
 571  *  lpBits [I] Bitmap pointer
 572  *
 573  * RETURNS
 574  *  The number of clear bits.
 575  */
 576 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
 577 {
 578   TRACE("(%p)\n", lpBits);
 579
 580   if (lpBits)
 581     return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
 582   return 0;
 583 }
 584
 585 /*************************************************************************
 586  * RtlFindMostSignificantBit    [NTDLL.@]
 587  *
 588  * Find the most significant bit in a 64 bit integer.
 589  *
 590  * RETURNS
 591  *  The position of the most significant bit.
 592  */
 593 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
 594 {
 595     signed char ret = 32;
 596     DWORD dw;
 597
 598     if (!(dw = (ulLong >> 32)))
 599     {
 600         ret = 0;
 601         dw = (DWORD)ulLong;
 602     }
 603     if (dw & 0xffff0000)
 604     {
 605         dw >>= 16;
 606         ret += 16;
 607     }
 608     if (dw & 0xff00)
 609     {
 610         dw >>= 8;
 611         ret += 8;
 612     }
 613     if (dw & 0xf0)
 614     {
 615         dw >>= 4;
 616         ret += 4;
 617     }
 618     return ret + NTDLL_mostSignificant[dw];
 619 }
 620
 621 /*************************************************************************
 622  * RtlFindLeastSignificantBit   [NTDLL.@]
 623  *
 624  * Find the least significant bit in a 64 bit integer.
 625  *
 626  * RETURNS
 627  *  The position of the least significant bit.
 628  */
 629 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
 630 {
 631     signed char ret = 0;
 632     DWORD dw;
 633
 634     if (!(dw = (DWORD)ulLong))
 635     {
 636         ret = 32;
 637         if (!(dw = ulLong >> 32)) return -1;
 638     }
 639     if (!(dw & 0xffff))
 640     {
 641         dw >>= 16;
 642         ret += 16;
 643     }
 644     if (!(dw & 0xff))
 645     {
 646         dw >>= 8;
 647         ret += 8;
 648     }
 649     if (!(dw & 0x0f))
 650     {
 651         dw >>= 4;
 652         ret += 4;
 653     }
 654     return ret + NTDLL_leastSignificant[dw & 0x0f];
 655 }
 656
 657 /*************************************************************************
 658  * NTDLL_RunSortFn
 659  *
 660  * Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
 661  */
 662 static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
 663 {
 664   if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
 665     return -1;
 666   return 1;
 667 }
 668
 669 /*************************************************************************
 670  * NTDLL_FindSetRun
 671  *
 672  * Internal helper: Find the next run of set bits in a bitmap.
 673  */
 674 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 675 {
 676   LPBYTE lpOut;
 677   ULONG ulFoundAt = 0, ulCount = 0;
 678
 679   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 680    * at a time. But beware of the pointer arithmetics...
 681    */
 682   lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
 683
 684   while (1)
 685   {
 686     /* Check bits in first byte */
 687     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 688     const BYTE bFirst = *lpOut & bMask;
 689
 690     if (bFirst)
 691     {
 692       /* Have a set bit in first byte */
 693       if (bFirst != bMask)
 694       {
 695         /* Not every bit is set */
 696         ULONG ulOffset;
 697
 698         if (bFirst & 0x0f)
 699           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 700         else
 701           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 702         ulStart += ulOffset;
 703         ulFoundAt = ulStart;
 704         for (;ulOffset < 8; ulOffset++)
 705         {
 706           if (!(bFirst & (1 << ulOffset)))
 707           {
 708             *lpSize = ulCount;
 709             return ulFoundAt; /* Set from start, but not until the end */
 710           }
 711           ulCount++;
 712           ulStart++;
 713         }
 714         /* Set to the end - go on to count further bits */
 715         lpOut++;
 716         break;
 717       }
 718       /* every bit from start until the end of the byte is set */
 719       ulFoundAt = ulStart;
 720       ulCount = 8 - (ulStart & 7);
 721       ulStart = (ulStart & ~7u) + 8;
 722       lpOut++;
 723       break;
 724     }
 725     ulStart = (ulStart & ~7u) + 8;
 726     lpOut++;
 727     if (ulStart >= lpBits->SizeOfBitMap)
 728       return ~0UL;
 729   }
 730
 731   /* Count blocks of 8 set bits */
 732   while (*lpOut == 0xff)
 733   {
 734     ulCount += 8;
 735     ulStart += 8;
 736     if (ulStart >= lpBits->SizeOfBitMap)
 737     {
 738       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 739       return ulFoundAt;
 740     }
 741     lpOut++;
 742   }
 743
 744   /* Count remaining contiguous bits, if any */
 745   if (*lpOut & 1)
 746   {
 747     ULONG ulOffset = 0;
 748
 749     for (;ulOffset < 7u; ulOffset++)
 750     {
 751       if (!(*lpOut & (1 << ulOffset)))
 752         break;
 753       ulCount++;
 754     }
 755   }
 756   *lpSize = ulCount;
 757   return ulFoundAt;
 758 }
 759
 760 /*************************************************************************
 761  * NTDLL_FindClearRun
 762  *
 763  * Internal helper: Find the next run of set bits in a bitmap.
 764  */
 765 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
 766 {
 767   LPBYTE lpOut;
 768   ULONG ulFoundAt = 0, ulCount = 0;
 769
 770   /* FIXME: It might be more efficient/cleaner to manipulate four bytes
 771    * at a time. But beware of the pointer arithmetics...
 772    */
 773   lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
 774
 775   while (1)
 776   {
 777     /* Check bits in first byte */
 778     const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
 779     const BYTE bFirst = (~*lpOut) & bMask;
 780
 781     if (bFirst)
 782     {
 783       /* Have a clear bit in first byte */
 784       if (bFirst != bMask)
 785       {
 786         /* Not every bit is clear */
 787         ULONG ulOffset;
 788
 789         if (bFirst & 0x0f)
 790           ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
 791         else
 792           ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
 793         ulStart += ulOffset;
 794         ulFoundAt = ulStart;
 795         for (;ulOffset < 8; ulOffset++)
 796         {
 797           if (!(bFirst & (1 << ulOffset)))
 798           {
 799             *lpSize = ulCount;
 800             return ulFoundAt; /* Clear from start, but not until the end */
 801           }
 802           ulCount++;
 803           ulStart++;
 804         }
 805         /* Clear to the end - go on to count further bits */
 806         lpOut++;
 807         break;
 808       }
 809       /* Every bit from start until the end of the byte is clear */
 810       ulFoundAt = ulStart;
 811       ulCount = 8 - (ulStart & 7);
 812       ulStart = (ulStart & ~7u) + 8;
 813       lpOut++;
 814       break;
 815     }
 816     ulStart = (ulStart & ~7u) + 8;
 817     lpOut++;
 818     if (ulStart >= lpBits->SizeOfBitMap)
 819       return ~0UL;
 820   }
 821
 822   /* Count blocks of 8 clear bits */
 823   while (!*lpOut)
 824   {
 825     ulCount += 8;
 826     ulStart += 8;
 827     if (ulStart >= lpBits->SizeOfBitMap)
 828     {
 829       *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
 830       return ulFoundAt;
 831     }
 832     lpOut++;
 833   }
 834
 835   /* Count remaining contiguous bits, if any */
 836   if (!(*lpOut & 1))
 837   {
 838     ULONG ulOffset = 0;
 839
 840     for (;ulOffset < 7u; ulOffset++)
 841     {
 842       if (*lpOut & (1 << ulOffset))
 843         break;
 844       ulCount++;
 845     }
 846   }
 847   *lpSize = ulCount;
 848   return ulFoundAt;
 849 }
 850
 851 /*************************************************************************
 852  * RtlFindNextForwardRunSet     [NTDLL.@]
 853  *
 854  * Find the next run of set bits in a bitmap.
 855  *
 856  * PARAMS
 857  *  lpBits  [I] Bitmap pointer
 858  *  ulStart [I] Bit position to start searching from
 859  *  lpPos   [O] Start of run
 860  *
 861  * RETURNS
 862  *  Success: The length of the next set run in the bitmap. lpPos is set to
 863  *           the start of the run.
 864  *  Failure: 0, if no run is found or any parameters are invalid.
 865  */
 866 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 867 {
 868   ULONG ulSize = 0;
 869
 870   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 871
 872   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 873     *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
 874
 875   return ulSize;
 876 }
 877
 878 /*************************************************************************
 879  * RtlFindNextForwardRunClear   [NTDLL.@]
 880  *
 881  * Find the next run of clear bits in a bitmap.
 882  *
 883  * PARAMS
 884  *  lpBits  [I] Bitmap pointer
 885  *  ulStart [I] Bit position to start searching from
 886  *  lpPos   [O] Start of run
 887  *
 888  * RETURNS
 889  *  Success: The length of the next clear run in the bitmap. lpPos is set to
 890  *           the start of the run.
 891  *  Failure: 0, if no run is found or any parameters are invalid.
 892  */
 893 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 894 {
 895   ULONG ulSize = 0;
 896
 897   TRACE("(%p,%ld,%p)\n", lpBits, ulStart, lpPos);
 898
 899   if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
 900     *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
 901
 902   return ulSize;
 903 }
 904
 905 /*************************************************************************
 906  * RtlFindLastBackwardRunSet    [NTDLL.@]
 907  *
 908  * Find a previous run of set bits in a bitmap.
 909  *
 910  * PARAMS
 911  *  lpBits  [I] Bitmap pointer
 912  *  ulStart [I] Bit position to start searching from
 913  *  lpPos   [O] Start of run
 914  *
 915  * RETURNS
 916  *  Success: The length of the previous set run in the bitmap. lpPos is set to
 917  *           the start of the run.
 918  *  Failure: 0, if no run is found or any parameters are invalid.
 919  */
 920 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 921 {
 922   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 923   return 0;
 924 }
 925
 926 /*************************************************************************
 927  * RtlFindLastBackwardRunClear  [NTDLL.@]
 928  *
 929  * Find a previous run of clear bits in a bitmap.
 930  *
 931  * PARAMS
 932  *  lpBits  [I] Bitmap pointer
 933  *  ulStart [I] Bit position to start searching from
 934  *  lpPos   [O] Start of run
 935  *
 936  * RETURNS
 937  *  Success: The length of the previous clear run in the bitmap. lpPos is set
 938  *           to the start of the run.
 939  *  Failure: 0, if no run is found or any parameters are invalid.
 940  */
 941 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
 942 {
 943   FIXME("(%p,%ld,%p)-stub!\n", lpBits, ulStart, lpPos);
 944   return 0;
 945 }
 946
 947 /*************************************************************************
 948  * NTDLL_FindRuns
 949  *
 950  * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
 951  */
 952 static ULONG WINAPI NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
 953                                    ULONG ulCount, BOOLEAN bLongest,
 954                                    ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
 955 {
 956   BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
 957   ULONG ulPos = 0, ulRuns = 0;
 958
 959   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
 960
 961   if (!ulCount)
 962     return ~0UL;
 963
 964   while (ulPos < lpBits->SizeOfBitMap)
 965   {
 966     /* Find next set/clear run */
 967     ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
 968
 969     if (ulNextPos == ~0UL)
 970       break;
 971
 972     if (bLongest && ulRuns == ulCount)
 973     {
 974       /* Sort runs with shortest at end, if they are out of order */
 975       if (bNeedSort)
 976         qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
 977
 978       /* Replace last run if this one is bigger */
 979       if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
 980       {
 981         lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
 982         lpSeries[ulRuns - 1].NumberOfBits = ulSize;
 983
 984         /* We need to re-sort the array, _if_ we didn't leave it sorted */
 985         if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
 986           bNeedSort = TRUE;
 987       }
 988     }
 989     else
 990     {
 991       /* Append to found runs */
 992       lpSeries[ulRuns].StartingIndex = ulNextPos;
 993       lpSeries[ulRuns].NumberOfBits = ulSize;
 994       ulRuns++;
 995
 996       if (!bLongest && ulRuns == ulCount)
 997         break;
 998     }
 999     ulPos = ulNextPos + ulSize;
1000   }
1001   return ulRuns;
1002 }
1003
1004 /*************************************************************************
1005  * RtlFindSetRuns       [NTDLL.@]
1006  *
1007  * Find a series of set runs in a bitmap.
1008  *
1009  * PARAMS
1010  *  lpBits   [I] Bitmap pointer
1011  *  lpSeries [O] Array for each run found
1012  *  ulCount  [I] Number of runs to find
1013  *  bLongest [I] Whether to find the very longest runs or not
1014  *
1015  * RETURNS
1016  *  The number of set runs found.
1017  */
1018 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1019                             ULONG ulCount, BOOLEAN bLongest)
1020 {
1021   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1022
1023   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1024 }
1025
1026 /*************************************************************************
1027  * RtlFindClearRuns     [NTDLL.@]
1028  *
1029  * Find a series of clear runs in a bitmap.
1030  *
1031  * PARAMS
1032  *  lpBits   [I] Bitmap pointer
1033  *  ulSeries [O] Array for each run found
1034  *  ulCount  [I] Number of runs to find
1035  *  bLongest [I] Whether to find the very longest runs or not
1036  *
1037  * RETURNS
1038  *  The number of clear runs found.
1039  */
1040 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1041                               ULONG ulCount, BOOLEAN bLongest)
1042 {
1043   TRACE("(%p,%p,%ld,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1044
1045   return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1046 }
1047
1048 /*************************************************************************
1049  * RtlFindLongestRunSet [NTDLL.@]
1050  *
1051  * Find the longest set run in a bitmap.
1052  *
1053  * PARAMS
1054  *  lpBits   [I] Bitmap pointer
1055  *  pulStart [O] Destination for start of run
1056  *
1057  * RETURNS
1058  *  The length of the run found, or 0 if no run is found.
1059  */
1060 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1061 {
1062   RTL_BITMAP_RUN br;
1063
1064   TRACE("(%p,%p)\n", lpBits, pulStart);
1065
1066   if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1067   {
1068     if (pulStart)
1069       *pulStart = br.StartingIndex;
1070     return br.NumberOfBits;
1071   }
1072   return 0;
1073 }
1074
1075 /*************************************************************************
1076  * RtlFindLongestRunClear       [NTDLL.@]
1077  *
1078  * Find the longest clear run in a bitmap.
1079  *
1080  * PARAMS
1081  *  lpBits   [I] Bitmap pointer
1082  *  pulStart [O] Destination for start of run
1083  *
1084  * RETURNS
1085  *  The length of the run found, or 0 if no run is found.
1086  */
1087 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1088 {
1089   RTL_BITMAP_RUN br;
1090
1091   TRACE("(%p,%p)\n", lpBits, pulStart);
1092
1093   if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1094   {
1095     if (pulStart)
1096       *pulStart = br.StartingIndex;
1097     return br.NumberOfBits;
1098   }
1099   return 0;
1100 }