Release 1.1.37.
[wine/gsoc-2012-control.git] / dlls / ntdll / rtlbitmap.c
blob806e0e80da58d6b4f7b2cdd8584f6bd8d205ca2f
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,%d)\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,%d,%d)\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 *lpOut |= (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,%d,%d)\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 *lpOut &= (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,%d,%d)\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,%d,%d)\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,%d,%d)\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,%d,%d)\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,%d,%d)\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,%d,%d)\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 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 /* Count blocks of 8 set bits */
735 while (*lpOut == 0xff)
737 ulCount += 8;
738 ulStart += 8;
739 if (ulStart >= lpBits->SizeOfBitMap)
741 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
742 return ulFoundAt;
744 lpOut++;
747 /* Count remaining contiguous bits, if any */
748 if (*lpOut & 1)
750 ULONG ulOffset = 0;
752 for (;ulOffset < 7u; ulOffset++)
754 if (!(*lpOut & (1 << ulOffset)))
755 break;
756 ulCount++;
759 *lpSize = ulCount;
760 return ulFoundAt;
763 /*************************************************************************
764 * NTDLL_FindClearRun
766 * Internal helper: Find the next run of set bits in a bitmap.
768 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
770 LPBYTE lpOut;
771 ULONG ulFoundAt = 0, ulCount = 0;
773 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
774 * at a time. But beware of the pointer arithmetics...
776 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
778 while (1)
780 /* Check bits in first byte */
781 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
782 const BYTE bFirst = (~*lpOut) & bMask;
784 if (bFirst)
786 /* Have a clear bit in first byte */
787 if (bFirst != bMask)
789 /* Not every bit is clear */
790 ULONG ulOffset;
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++)
800 if (!(bFirst & (1 << ulOffset)))
802 *lpSize = ulCount;
803 return ulFoundAt; /* Clear from start, but not until the end */
805 ulCount++;
806 ulStart++;
808 /* Clear to the end - go on to count further bits */
809 lpOut++;
810 break;
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;
819 ulStart = (ulStart & ~7u) + 8;
820 lpOut++;
821 if (ulStart >= lpBits->SizeOfBitMap)
822 return ~0U;
825 /* Count blocks of 8 clear bits */
826 while (!*lpOut)
828 ulCount += 8;
829 ulStart += 8;
830 if (ulStart >= lpBits->SizeOfBitMap)
832 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
833 return ulFoundAt;
835 lpOut++;
838 /* Count remaining contiguous bits, if any */
839 if (!(*lpOut & 1))
841 ULONG ulOffset = 0;
843 for (;ulOffset < 7u; ulOffset++)
845 if (*lpOut & (1 << ulOffset))
846 break;
847 ulCount++;
850 *lpSize = ulCount;
851 return ulFoundAt;
854 /*************************************************************************
855 * RtlFindNextForwardRunSet [NTDLL.@]
857 * Find the next run of set bits in a bitmap.
859 * PARAMS
860 * lpBits [I] Bitmap pointer
861 * ulStart [I] Bit position to start searching from
862 * lpPos [O] Start of run
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.
869 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
871 ULONG ulSize = 0;
873 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
875 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
876 *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
878 return ulSize;
881 /*************************************************************************
882 * RtlFindNextForwardRunClear [NTDLL.@]
884 * Find the next run of clear bits in a bitmap.
886 * PARAMS
887 * lpBits [I] Bitmap pointer
888 * ulStart [I] Bit position to start searching from
889 * lpPos [O] Start of run
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.
896 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
898 ULONG ulSize = 0;
900 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
902 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
903 *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
905 return ulSize;
908 /*************************************************************************
909 * RtlFindLastBackwardRunSet [NTDLL.@]
911 * Find a previous run of set bits in a bitmap.
913 * PARAMS
914 * lpBits [I] Bitmap pointer
915 * ulStart [I] Bit position to start searching from
916 * lpPos [O] Start of run
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.
923 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
925 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
926 return 0;
929 /*************************************************************************
930 * RtlFindLastBackwardRunClear [NTDLL.@]
932 * Find a previous run of clear bits in a bitmap.
934 * PARAMS
935 * lpBits [I] Bitmap pointer
936 * ulStart [I] Bit position to start searching from
937 * lpPos [O] Start of run
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.
944 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
946 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
947 return 0;
950 /*************************************************************************
951 * NTDLL_FindRuns
953 * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
955 static ULONG NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
956 ULONG ulCount, BOOLEAN bLongest,
957 ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
959 BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
960 ULONG ulPos = 0, ulRuns = 0;
962 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
964 if (!ulCount)
965 return ~0U;
967 while (ulPos < lpBits->SizeOfBitMap)
969 /* Find next set/clear run */
970 ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
972 if (ulNextPos == ~0U)
973 break;
975 if (bLongest && ulRuns == ulCount)
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);
981 /* Replace last run if this one is bigger */
982 if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
984 lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
985 lpSeries[ulRuns - 1].NumberOfBits = ulSize;
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;
992 else
994 /* Append to found runs */
995 lpSeries[ulRuns].StartingIndex = ulNextPos;
996 lpSeries[ulRuns].NumberOfBits = ulSize;
997 ulRuns++;
999 if (!bLongest && ulRuns == ulCount)
1000 break;
1002 ulPos = ulNextPos + ulSize;
1004 return ulRuns;
1007 /*************************************************************************
1008 * RtlFindSetRuns [NTDLL.@]
1010 * Find a series of set runs in a bitmap.
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
1018 * RETURNS
1019 * The number of set runs found.
1021 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1022 ULONG ulCount, BOOLEAN bLongest)
1024 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1026 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1029 /*************************************************************************
1030 * RtlFindClearRuns [NTDLL.@]
1032 * Find a series of clear runs in a bitmap.
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
1040 * RETURNS
1041 * The number of clear runs found.
1043 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1044 ULONG ulCount, BOOLEAN bLongest)
1046 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1048 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1051 /*************************************************************************
1052 * RtlFindLongestRunSet [NTDLL.@]
1054 * Find the longest set run in a bitmap.
1056 * PARAMS
1057 * lpBits [I] Bitmap pointer
1058 * pulStart [O] Destination for start of run
1060 * RETURNS
1061 * The length of the run found, or 0 if no run is found.
1063 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1065 RTL_BITMAP_RUN br;
1067 TRACE("(%p,%p)\n", lpBits, pulStart);
1069 if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1071 if (pulStart)
1072 *pulStart = br.StartingIndex;
1073 return br.NumberOfBits;
1075 return 0;
1078 /*************************************************************************
1079 * RtlFindLongestRunClear [NTDLL.@]
1081 * Find the longest clear run in a bitmap.
1083 * PARAMS
1084 * lpBits [I] Bitmap pointer
1085 * pulStart [O] Destination for start of run
1087 * RETURNS
1088 * The length of the run found, or 0 if no run is found.
1090 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1092 RTL_BITMAP_RUN br;
1094 TRACE("(%p,%p)\n", lpBits, pulStart);
1096 if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1098 if (pulStart)
1099 *pulStart = br.StartingIndex;
1100 return br.NumberOfBits;
1102 return 0;