wined3d: Track separate dirty ranges in buffers.
[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   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 ? TRUE : FALSE;
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 }