wined3d: Pass a wined3d_device_context to wined3d_cs_emit_blt_sub_resource().
[wine/zf.git] / dlls / ntdll / rtlbitmap.c
blob16761f3449d0917c512fa83b23f058a7bc409a7a
1 /*
2 * NTDLL bitmap functions
4 * Copyright 2002 Jon Griffiths
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.
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.
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
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.
25 * Bits are set LSB to MSB in each consecutive byte, making this implementation
26 * binary compatible with Win32.
28 * Note that to avoid unexpected behaviour, the size of a bitmap should be set
29 * to a multiple of 32.
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"
38 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
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 };
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
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
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
58 /*************************************************************************
59 * RtlInitializeBitMap [NTDLL.@]
61 * Initialise a new bitmap.
63 * PARAMS
64 * lpBits [I] Bitmap pointer
65 * lpBuff [I] Memory for the bitmap
66 * ulSize [I] Size of lpBuff in bits
68 * RETURNS
69 * Nothing.
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).
75 VOID WINAPI RtlInitializeBitMap(PRTL_BITMAP lpBits, PULONG lpBuff, ULONG ulSize)
77 TRACE("(%p,%p,%u)\n", lpBits,lpBuff,ulSize);
78 lpBits->SizeOfBitMap = ulSize;
79 lpBits->Buffer = lpBuff;
82 /*************************************************************************
83 * RtlSetAllBits [NTDLL.@]
85 * Set all bits in a bitmap.
87 * PARAMS
88 * lpBits [I] Bitmap pointer
90 * RETURNS
91 * Nothing.
93 VOID WINAPI RtlSetAllBits(PRTL_BITMAP lpBits)
95 TRACE("(%p)\n", lpBits);
96 memset(lpBits->Buffer, 0xff, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
99 /*************************************************************************
100 * RtlClearAllBits [NTDLL.@]
102 * Clear all bits in a bitmap.
104 * PARAMS
105 * lpBit [I] Bitmap pointer
107 * RETURNS
108 * Nothing.
110 VOID WINAPI RtlClearAllBits(PRTL_BITMAP lpBits)
112 TRACE("(%p)\n", lpBits);
113 memset(lpBits->Buffer, 0, ((lpBits->SizeOfBitMap + 31) & ~31) >> 3);
116 /*************************************************************************
117 * RtlSetBits [NTDLL.@]
119 * Set a range of bits in a bitmap.
121 * PARAMS
122 * lpBits [I] Bitmap pointer
123 * ulStart [I] First bit to set
124 * ulCount [I] Number of consecutive bits to set
126 * RETURNS
127 * Nothing.
129 VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
131 LPBYTE lpOut;
133 TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
135 if (!lpBits || !ulCount ||
136 ulStart >= lpBits->SizeOfBitMap ||
137 ulCount > lpBits->SizeOfBitMap - ulStart)
138 return;
140 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
141 * at a time. But beware of the pointer arithmetics...
143 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
145 /* Set bits in first byte, if ulStart isn't a byte boundary */
146 if (ulStart & 7)
148 if (ulCount > 7)
150 /* Set from start bit to the end of the byte */
151 *lpOut++ |= 0xff << (ulStart & 7);
152 ulCount -= (8 - (ulStart & 7));
154 else
156 /* Set from the start bit, possibly into the next byte also */
157 USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
159 *lpOut |= (initialWord & 0xff);
160 if (initialWord >> 8) lpOut[1] |= (initialWord >> 8);
161 return;
165 /* Set bits up to complete byte count */
166 if (ulCount >> 3)
168 memset(lpOut, 0xff, ulCount >> 3);
169 lpOut = lpOut + (ulCount >> 3);
172 /* Set remaining bits, if any */
173 if (ulCount & 0x7)
174 *lpOut |= NTDLL_maskBits[ulCount & 0x7];
177 /*************************************************************************
178 * RtlClearBits [NTDLL.@]
180 * Clear bits in a bitmap.
182 * PARAMS
183 * lpBits [I] Bitmap pointer
184 * ulStart [I] First bit to set
185 * ulCount [I] Number of consecutive bits to clear
187 * RETURNS
188 * Nothing.
190 VOID WINAPI RtlClearBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
192 LPBYTE lpOut;
194 TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
196 if (!lpBits || !ulCount ||
197 ulStart >= lpBits->SizeOfBitMap ||
198 ulCount > lpBits->SizeOfBitMap - ulStart)
199 return;
201 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
202 * at a time. But beware of the pointer arithmetics...
204 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
206 /* Clear bits in first byte, if ulStart isn't a byte boundary */
207 if (ulStart & 7)
209 if (ulCount > 7)
211 /* Clear from start bit to the end of the byte */
212 *lpOut++ &= ~(0xff << (ulStart & 7));
213 ulCount -= (8 - (ulStart & 7));
215 else
217 /* Clear from the start bit, possibly into the next byte also */
218 USHORT initialWord = ~(NTDLL_maskBits[ulCount] << (ulStart & 7));
220 *lpOut &= (initialWord & 0xff);
221 if ((initialWord >> 8) != 0xff) lpOut[1] &= (initialWord >> 8);
222 return;
226 /* Clear bits (in blocks of 8) on whole byte boundaries */
227 if (ulCount >> 3)
229 memset(lpOut, 0, ulCount >> 3);
230 lpOut = lpOut + (ulCount >> 3);
233 /* Clear remaining bits, if any */
234 if (ulCount & 0x7)
235 *lpOut &= ~NTDLL_maskBits[ulCount & 0x7];
238 /*************************************************************************
239 * RtlAreBitsSet [NTDLL.@]
241 * Determine if part of a bitmap is set.
243 * PARAMS
244 * lpBits [I] Bitmap pointer
245 * ulStart [I] First bit to check from
246 * ulCount [I] Number of consecutive bits to check
248 * RETURNS
249 * TRUE, If ulCount bits from ulStart are set.
250 * FALSE, Otherwise.
252 BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
254 LPBYTE lpOut;
255 ULONG ulRemainder;
257 TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
259 if (!lpBits || !ulCount ||
260 ulStart >= lpBits->SizeOfBitMap ||
261 ulCount > lpBits->SizeOfBitMap - ulStart)
262 return FALSE;
264 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
265 * at a time. But beware of the pointer arithmetics...
267 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
269 /* Check bits in first byte, if ulStart isn't a byte boundary */
270 if (ulStart & 7)
272 if (ulCount > 7)
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));
281 else
283 /* Check from the start bit, possibly into the next byte also */
284 USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
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;
295 /* Check bits in blocks of 8 bytes */
296 ulRemainder = ulCount & 7;
297 ulCount >>= 3;
298 while (ulCount--)
300 if (*lpOut++ != 0xff)
301 return FALSE;
304 /* Check remaining bits, if any */
305 if (ulRemainder &&
306 (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
307 return FALSE;
308 return TRUE;
311 /*************************************************************************
312 * RtlAreBitsClear [NTDLL.@]
314 * Determine if part of a bitmap is clear.
316 * PARAMS
317 * lpBits [I] Bitmap pointer
318 * ulStart [I] First bit to check from
319 * ulCount [I] Number of consecutive bits to check
321 * RETURNS
322 * TRUE, If ulCount bits from ulStart are clear.
323 * FALSE, Otherwise.
325 BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
327 LPBYTE lpOut;
328 ULONG ulRemainder;
330 TRACE("(%p,%u,%u)\n", lpBits, ulStart, ulCount);
332 if (!lpBits || !ulCount ||
333 ulStart >= lpBits->SizeOfBitMap ||
334 ulCount > lpBits->SizeOfBitMap - ulStart)
335 return FALSE;
337 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
338 * at a time. But beware of the pointer arithmetics...
340 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
342 /* Check bits in first byte, if ulStart isn't a byte boundary */
343 if (ulStart & 7)
345 if (ulCount > 7)
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));
353 else
355 /* Check from the start bit, possibly into the next byte also */
356 USHORT initialWord = NTDLL_maskBits[ulCount] << (ulStart & 7);
358 if (*lpOut & (initialWord & 0xff))
359 return FALSE;
360 if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
361 return FALSE;
362 return TRUE;
366 /* Check bits in blocks of 8 bytes */
367 ulRemainder = ulCount & 7;
368 ulCount >>= 3;
369 while (ulCount--)
371 if (*lpOut++)
372 return FALSE;
375 /* Check remaining bits, if any */
376 if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
377 return FALSE;
378 return TRUE;
381 /*************************************************************************
382 * RtlFindSetBits [NTDLL.@]
384 * Find a block of set bits in a bitmap.
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
391 * RETURNS
392 * The bit at which the match was found, or -1 if no match was found.
394 ULONG WINAPI RtlFindSetBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
396 ULONG ulPos, ulEnd;
398 TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
400 if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
401 return ~0U;
403 ulEnd = lpBits->SizeOfBitMap;
405 if (ulHint + ulCount > lpBits->SizeOfBitMap)
406 ulHint = 0;
408 ulPos = ulHint;
410 while (ulPos < ulEnd)
412 /* FIXME: This could be made a _lot_ more efficient */
413 if (RtlAreBitsSet(lpBits, ulPos, ulCount))
414 return ulPos;
416 /* Start from the beginning if we hit the end and had a hint */
417 if (ulPos == ulEnd - 1 && ulHint)
419 ulEnd = ulHint;
420 ulPos = ulHint = 0;
422 else
423 ulPos++;
425 return ~0U;
428 /*************************************************************************
429 * RtlFindClearBits [NTDLL.@]
431 * Find a block of clear bits in a bitmap.
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
438 * RETURNS
439 * The bit at which the match was found, or -1 if no match was found.
441 ULONG WINAPI RtlFindClearBits(PCRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
443 ULONG ulPos, ulEnd;
445 TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
447 if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
448 return ~0U;
450 ulEnd = lpBits->SizeOfBitMap;
452 if (ulHint + ulCount > lpBits->SizeOfBitMap)
453 ulHint = 0;
455 ulPos = ulHint;
457 while (ulPos < ulEnd)
459 /* FIXME: This could be made a _lot_ more efficient */
460 if (RtlAreBitsClear(lpBits, ulPos, ulCount))
461 return ulPos;
463 /* Start from the beginning if we hit the end and started from ulHint */
464 if (ulPos == ulEnd - 1 && ulHint)
466 ulEnd = ulHint;
467 ulPos = ulHint = 0;
469 else
470 ulPos++;
472 return ~0U;
475 /*************************************************************************
476 * RtlFindSetBitsAndClear [NTDLL.@]
478 * Find a block of set bits in a bitmap, and clear them if found.
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
485 * RETURNS
486 * The bit at which the match was found, or -1 if no match was found.
488 ULONG WINAPI RtlFindSetBitsAndClear(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
490 ULONG ulPos;
492 TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
494 ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
495 if (ulPos != ~0U)
496 RtlClearBits(lpBits, ulPos, ulCount);
497 return ulPos;
500 /*************************************************************************
501 * RtlFindClearBitsAndSet [NTDLL.@]
503 * Find a block of clear bits in a bitmap, and set them if found.
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
510 * RETURNS
511 * The bit at which the match was found, or -1 if no match was found.
513 ULONG WINAPI RtlFindClearBitsAndSet(PRTL_BITMAP lpBits, ULONG ulCount, ULONG ulHint)
515 ULONG ulPos;
517 TRACE("(%p,%u,%u)\n", lpBits, ulCount, ulHint);
519 ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
520 if (ulPos != ~0U)
521 RtlSetBits(lpBits, ulPos, ulCount);
522 return ulPos;
525 /*************************************************************************
526 * RtlNumberOfSetBits [NTDLL.@]
528 * Find the number of set bits in a bitmap.
530 * PARAMS
531 * lpBits [I] Bitmap pointer
533 * RETURNS
534 * The number of set bits.
536 ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP lpBits)
538 ULONG ulSet = 0;
540 TRACE("(%p)\n", lpBits);
542 if (lpBits)
544 LPBYTE lpOut = (BYTE *)lpBits->Buffer;
545 ULONG ulCount, ulRemainder;
546 BYTE bMasked;
548 ulCount = lpBits->SizeOfBitMap >> 3;
549 ulRemainder = lpBits->SizeOfBitMap & 0x7;
551 while (ulCount--)
553 ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
554 ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
555 lpOut++;
558 if (ulRemainder)
560 bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
561 ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
562 ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
565 return ulSet;
568 /*************************************************************************
569 * RtlNumberOfClearBits [NTDLL.@]
571 * Find the number of clear bits in a bitmap.
573 * PARAMS
574 * lpBits [I] Bitmap pointer
576 * RETURNS
577 * The number of clear bits.
579 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
581 TRACE("(%p)\n", lpBits);
583 if (lpBits)
584 return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
585 return 0;
588 /*************************************************************************
589 * RtlFindMostSignificantBit [NTDLL.@]
591 * Find the most significant bit in a 64 bit integer.
593 * RETURNS
594 * The position of the most significant bit.
596 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
598 signed char ret = 32;
599 DWORD dw;
601 if (!(dw = (ulLong >> 32)))
603 ret = 0;
604 dw = (DWORD)ulLong;
606 if (dw & 0xffff0000)
608 dw >>= 16;
609 ret += 16;
611 if (dw & 0xff00)
613 dw >>= 8;
614 ret += 8;
616 if (dw & 0xf0)
618 dw >>= 4;
619 ret += 4;
621 return ret + NTDLL_mostSignificant[dw];
624 /*************************************************************************
625 * RtlFindLeastSignificantBit [NTDLL.@]
627 * Find the least significant bit in a 64 bit integer.
629 * RETURNS
630 * The position of the least significant bit.
632 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
634 signed char ret = 0;
635 DWORD dw;
637 if (!(dw = (DWORD)ulLong))
639 ret = 32;
640 if (!(dw = ulLong >> 32)) return -1;
642 if (!(dw & 0xffff))
644 dw >>= 16;
645 ret += 16;
647 if (!(dw & 0xff))
649 dw >>= 8;
650 ret += 8;
652 if (!(dw & 0x0f))
654 dw >>= 4;
655 ret += 4;
657 return ret + NTDLL_leastSignificant[dw & 0x0f];
660 /*************************************************************************
661 * NTDLL_RunSortFn
663 * Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
665 static int __cdecl NTDLL_RunSortFn(const void *lhs, const void *rhs)
667 if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
668 return -1;
669 return 1;
672 /*************************************************************************
673 * NTDLL_FindSetRun
675 * Internal helper: Find the next run of set bits in a bitmap.
677 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
679 LPBYTE lpOut;
680 ULONG ulFoundAt = 0, ulCount = 0;
682 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
683 * at a time. But beware of the pointer arithmetics...
685 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
687 while (1)
689 /* Check bits in first byte */
690 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
691 const BYTE bFirst = *lpOut & bMask;
693 if (bFirst)
695 /* Have a set bit in first byte */
696 if (bFirst != bMask)
698 /* Not every bit is set */
699 ULONG ulOffset;
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++)
709 if (!(bFirst & (1 << ulOffset)))
711 *lpSize = ulCount;
712 return ulFoundAt; /* Set from start, but not until the end */
714 ulCount++;
715 ulStart++;
717 /* Set to the end - go on to count further bits */
718 lpOut++;
719 break;
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;
728 ulStart = (ulStart & ~7u) + 8;
729 lpOut++;
730 if (ulStart >= lpBits->SizeOfBitMap)
731 return ~0U;
734 /* Check if reached the end of bitmap */
735 if (ulStart >= lpBits->SizeOfBitMap) {
736 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
737 return ulFoundAt;
740 /* Count blocks of 8 set bits */
741 while (*lpOut == 0xff)
743 ulCount += 8;
744 ulStart += 8;
745 if (ulStart >= lpBits->SizeOfBitMap)
747 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
748 return ulFoundAt;
750 lpOut++;
753 /* Count remaining contiguous bits, if any */
754 if (*lpOut & 1)
756 ULONG ulOffset = 0;
758 for (;ulOffset < 7u; ulOffset++)
760 if (!(*lpOut & (1 << ulOffset)))
761 break;
762 ulCount++;
765 *lpSize = ulCount;
766 return ulFoundAt;
769 /*************************************************************************
770 * NTDLL_FindClearRun
772 * Internal helper: Find the next run of set bits in a bitmap.
774 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
776 LPBYTE lpOut;
777 ULONG ulFoundAt = 0, ulCount = 0;
779 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
780 * at a time. But beware of the pointer arithmetics...
782 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
784 while (1)
786 /* Check bits in first byte */
787 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
788 const BYTE bFirst = (~*lpOut) & bMask;
790 if (bFirst)
792 /* Have a clear bit in first byte */
793 if (bFirst != bMask)
795 /* Not every bit is clear */
796 ULONG ulOffset;
798 if (bFirst & 0x0f)
799 ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
800 else
801 ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
802 ulStart += ulOffset;
803 ulFoundAt = ulStart;
804 for (;ulOffset < 8; ulOffset++)
806 if (!(bFirst & (1 << ulOffset)))
808 *lpSize = ulCount;
809 return ulFoundAt; /* Clear from start, but not until the end */
811 ulCount++;
812 ulStart++;
814 /* Clear to the end - go on to count further bits */
815 lpOut++;
816 break;
818 /* Every bit from start until the end of the byte is clear */
819 ulFoundAt = ulStart;
820 ulCount = 8 - (ulStart & 7);
821 ulStart = (ulStart & ~7u) + 8;
822 lpOut++;
823 break;
825 ulStart = (ulStart & ~7u) + 8;
826 lpOut++;
827 if (ulStart >= lpBits->SizeOfBitMap)
828 return ~0U;
831 /* Check if reached the end of bitmap */
832 if (ulStart >= lpBits->SizeOfBitMap) {
833 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
834 return ulFoundAt;
837 /* Count blocks of 8 clear bits */
838 while (!*lpOut)
840 ulCount += 8;
841 ulStart += 8;
842 if (ulStart >= lpBits->SizeOfBitMap)
844 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
845 return ulFoundAt;
847 lpOut++;
850 /* Count remaining contiguous bits, if any */
851 if (!(*lpOut & 1))
853 ULONG ulOffset = 0;
855 for (;ulOffset < 7u; ulOffset++)
857 if (*lpOut & (1 << ulOffset))
858 break;
859 ulCount++;
862 *lpSize = ulCount;
863 return ulFoundAt;
866 /*************************************************************************
867 * RtlFindNextForwardRunSet [NTDLL.@]
869 * Find the next run of set bits in a bitmap.
871 * PARAMS
872 * lpBits [I] Bitmap pointer
873 * ulStart [I] Bit position to start searching from
874 * lpPos [O] Start of run
876 * RETURNS
877 * Success: The length of the next set run in the bitmap. lpPos is set to
878 * the start of the run.
879 * Failure: 0, if no run is found or any parameters are invalid.
881 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
883 ULONG ulSize = 0;
885 TRACE("(%p,%u,%p)\n", lpBits, ulStart, lpPos);
887 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
888 *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
890 return ulSize;
893 /*************************************************************************
894 * RtlFindNextForwardRunClear [NTDLL.@]
896 * Find the next run of clear bits in a bitmap.
898 * PARAMS
899 * lpBits [I] Bitmap pointer
900 * ulStart [I] Bit position to start searching from
901 * lpPos [O] Start of run
903 * RETURNS
904 * Success: The length of the next clear run in the bitmap. lpPos is set to
905 * the start of the run.
906 * Failure: 0, if no run is found or any parameters are invalid.
908 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
910 ULONG ulSize = 0;
912 TRACE("(%p,%u,%p)\n", lpBits, ulStart, lpPos);
914 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
915 *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
917 return ulSize;
920 /*************************************************************************
921 * RtlFindLastBackwardRunSet [NTDLL.@]
923 * Find a previous run of set bits in a bitmap.
925 * PARAMS
926 * lpBits [I] Bitmap pointer
927 * ulStart [I] Bit position to start searching from
928 * lpPos [O] Start of run
930 * RETURNS
931 * Success: The length of the previous set run in the bitmap. lpPos is set to
932 * the start of the run.
933 * Failure: 0, if no run is found or any parameters are invalid.
935 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
937 FIXME("(%p,%u,%p)-stub!\n", lpBits, ulStart, lpPos);
938 return 0;
941 /*************************************************************************
942 * RtlFindLastBackwardRunClear [NTDLL.@]
944 * Find a previous run of clear bits in a bitmap.
946 * PARAMS
947 * lpBits [I] Bitmap pointer
948 * ulStart [I] Bit position to start searching from
949 * lpPos [O] Start of run
951 * RETURNS
952 * Success: The length of the previous clear run in the bitmap. lpPos is set
953 * to the start of the run.
954 * Failure: 0, if no run is found or any parameters are invalid.
956 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
958 FIXME("(%p,%u,%p)-stub!\n", lpBits, ulStart, lpPos);
959 return 0;
962 /*************************************************************************
963 * NTDLL_FindRuns
965 * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
967 static ULONG NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
968 ULONG ulCount, BOOLEAN bLongest,
969 ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
971 BOOL bNeedSort = ulCount > 1;
972 ULONG ulPos = 0, ulRuns = 0;
974 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
976 if (!ulCount)
977 return ~0U;
979 while (ulPos < lpBits->SizeOfBitMap)
981 /* Find next set/clear run */
982 ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
984 if (ulNextPos == ~0U)
985 break;
987 if (bLongest && ulRuns == ulCount)
989 /* Sort runs with shortest at end, if they are out of order */
990 if (bNeedSort)
991 qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
993 /* Replace last run if this one is bigger */
994 if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
996 lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
997 lpSeries[ulRuns - 1].NumberOfBits = ulSize;
999 /* We need to re-sort the array, _if_ we didn't leave it sorted */
1000 if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
1001 bNeedSort = TRUE;
1004 else
1006 /* Append to found runs */
1007 lpSeries[ulRuns].StartingIndex = ulNextPos;
1008 lpSeries[ulRuns].NumberOfBits = ulSize;
1009 ulRuns++;
1011 if (!bLongest && ulRuns == ulCount)
1012 break;
1014 ulPos = ulNextPos + ulSize;
1016 return ulRuns;
1019 /*************************************************************************
1020 * RtlFindSetRuns [NTDLL.@]
1022 * Find a series of set runs in a bitmap.
1024 * PARAMS
1025 * lpBits [I] Bitmap pointer
1026 * lpSeries [O] Array for each run found
1027 * ulCount [I] Number of runs to find
1028 * bLongest [I] Whether to find the very longest runs or not
1030 * RETURNS
1031 * The number of set runs found.
1033 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1034 ULONG ulCount, BOOLEAN bLongest)
1036 TRACE("(%p,%p,%u,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1038 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1041 /*************************************************************************
1042 * RtlFindClearRuns [NTDLL.@]
1044 * Find a series of clear runs in a bitmap.
1046 * PARAMS
1047 * lpBits [I] Bitmap pointer
1048 * ulSeries [O] Array for each run found
1049 * ulCount [I] Number of runs to find
1050 * bLongest [I] Whether to find the very longest runs or not
1052 * RETURNS
1053 * The number of clear runs found.
1055 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1056 ULONG ulCount, BOOLEAN bLongest)
1058 TRACE("(%p,%p,%u,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1060 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1063 /*************************************************************************
1064 * RtlFindLongestRunSet [NTDLL.@]
1066 * Find the longest set run in a bitmap.
1068 * PARAMS
1069 * lpBits [I] Bitmap pointer
1070 * pulStart [O] Destination for start of run
1072 * RETURNS
1073 * The length of the run found, or 0 if no run is found.
1075 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1077 RTL_BITMAP_RUN br;
1079 TRACE("(%p,%p)\n", lpBits, pulStart);
1081 if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1083 if (pulStart)
1084 *pulStart = br.StartingIndex;
1085 return br.NumberOfBits;
1087 return 0;
1090 /*************************************************************************
1091 * RtlFindLongestRunClear [NTDLL.@]
1093 * Find the longest clear run in a bitmap.
1095 * PARAMS
1096 * lpBits [I] Bitmap pointer
1097 * pulStart [O] Destination for start of run
1099 * RETURNS
1100 * The length of the run found, or 0 if no run is found.
1102 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1104 RTL_BITMAP_RUN br;
1106 TRACE("(%p,%p)\n", lpBits, pulStart);
1108 if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1110 if (pulStart)
1111 *pulStart = br.StartingIndex;
1112 return br.NumberOfBits;
1114 return 0;