ntdll: Correct trace message stating NtAccessCheck is a stub.
[wine] / 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 WINAPI 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 }