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
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.
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.
64 * lpBits [I] Bitmap pointer
65 * lpBuff [I] Memory for the bitmap
66 * ulSize [I] Size of lpBuff in bits
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.
88 * lpBits [I] Bitmap pointer
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.
105 * lpBit [I] Bitmap pointer
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.
122 * lpBits [I] Bitmap pointer
123 * ulStart [I] First bit to set
124 * ulCount [I] Number of consecutive bits to set
129 VOID WINAPI RtlSetBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
133 TRACE("(%p,%d,%d)\n", lpBits, ulStart, ulCount);
135 if (!lpBits || !ulCount ||
136 ulStart >= lpBits->SizeOfBitMap ||
137 ulCount > lpBits->SizeOfBitMap - ulStart)
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 */
150 /* Set from start bit to the end of the byte */
151 *lpOut++ |= 0xff << (ulStart & 7);
152 ulCount -= (8 - (ulStart & 7));
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);
165 /* Set bits up to complete byte count */
168 memset(lpOut, 0xff, ulCount >> 3);
169 lpOut = lpOut + (ulCount >> 3);
172 /* Set remaining bits, if any */
174 *lpOut |= NTDLL_maskBits[ulCount & 0x7];
177 /*************************************************************************
178 * RtlClearBits [NTDLL.@]
180 * Clear bits in a bitmap.
183 * lpBits [I] Bitmap pointer
184 * ulStart [I] First bit to set
185 * ulCount [I] Number of consecutive bits to clear
190 VOID WINAPI RtlClearBits(PRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
194 TRACE("(%p,%d,%d)\n", lpBits, ulStart, ulCount);
196 if (!lpBits || !ulCount ||
197 ulStart >= lpBits->SizeOfBitMap ||
198 ulCount > lpBits->SizeOfBitMap - ulStart)
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 */
211 /* Clear from start bit to the end of the byte */
212 *lpOut++ &= ~(0xff << (ulStart & 7));
213 ulCount -= (8 - (ulStart & 7));
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);
226 /* Clear bits (in blocks of 8) on whole byte boundaries */
229 memset(lpOut, 0, ulCount >> 3);
230 lpOut = lpOut + (ulCount >> 3);
233 /* Clear remaining bits, if any */
235 *lpOut &= ~NTDLL_maskBits[ulCount & 0x7];
238 /*************************************************************************
239 * RtlAreBitsSet [NTDLL.@]
241 * Determine if part of a bitmap is set.
244 * lpBits [I] Bitmap pointer
245 * ulStart [I] First bit to check from
246 * ulCount [I] Number of consecutive bits to check
249 * TRUE, If ulCount bits from ulStart are set.
252 BOOLEAN WINAPI RtlAreBitsSet(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
257 TRACE("(%p,%d,%d)\n", lpBits, ulStart, ulCount);
259 if (!lpBits || !ulCount ||
260 ulStart >= lpBits->SizeOfBitMap ||
261 ulCount > lpBits->SizeOfBitMap - ulStart)
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 */
274 /* Check from start bit to the end of the byte */
276 ((0xff << (ulStart & 7))) & 0xff) != ((0xff << (ulStart & 7) & 0xff)))
279 ulCount -= (8 - (ulStart & 7));
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))
288 if ((initialWord & 0xff00) &&
289 ((lpOut[1] & (initialWord >> 8)) != (initialWord >> 8)))
295 /* Check bits in blocks of 8 bytes */
296 ulRemainder = ulCount & 7;
300 if (*lpOut++ != 0xff)
304 /* Check remaining bits, if any */
306 (*lpOut & NTDLL_maskBits[ulRemainder]) != NTDLL_maskBits[ulRemainder])
311 /*************************************************************************
312 * RtlAreBitsClear [NTDLL.@]
314 * Determine if part of a bitmap is clear.
317 * lpBits [I] Bitmap pointer
318 * ulStart [I] First bit to check from
319 * ulCount [I] Number of consecutive bits to check
322 * TRUE, If ulCount bits from ulStart are clear.
325 BOOLEAN WINAPI RtlAreBitsClear(PCRTL_BITMAP lpBits, ULONG ulStart, ULONG ulCount)
330 TRACE("(%p,%d,%d)\n", lpBits, ulStart, ulCount);
332 if (!lpBits || !ulCount ||
333 ulStart >= lpBits->SizeOfBitMap ||
334 ulCount > lpBits->SizeOfBitMap - ulStart)
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 */
347 /* Check from start bit to the end of the byte */
348 if (*lpOut & ((0xff << (ulStart & 7)) & 0xff))
351 ulCount -= (8 - (ulStart & 7));
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))
360 if ((initialWord & 0xff00) && (lpOut[1] & (initialWord >> 8)))
366 /* Check bits in blocks of 8 bytes */
367 ulRemainder = ulCount & 7;
375 /* Check remaining bits, if any */
376 if (ulRemainder && *lpOut & NTDLL_maskBits[ulRemainder])
381 /*************************************************************************
382 * RtlFindSetBits [NTDLL.@]
384 * Find a block of set bits in a bitmap.
387 * lpBits [I] Bitmap pointer
388 * ulCount [I] Number of consecutive set bits to find
389 * ulHint [I] Suggested starting position for set bits
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)
398 TRACE("(%p,%d,%d)\n", lpBits, ulCount, ulHint);
400 if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
403 ulEnd = lpBits->SizeOfBitMap;
405 if (ulHint + ulCount > lpBits->SizeOfBitMap)
410 while (ulPos < ulEnd)
412 /* FIXME: This could be made a _lot_ more efficient */
413 if (RtlAreBitsSet(lpBits, ulPos, ulCount))
416 /* Start from the beginning if we hit the end and had a hint */
417 if (ulPos == ulEnd - 1 && ulHint)
428 /*************************************************************************
429 * RtlFindClearBits [NTDLL.@]
431 * Find a block of clear bits in a bitmap.
434 * lpBits [I] Bitmap pointer
435 * ulCount [I] Number of consecutive clear bits to find
436 * ulHint [I] Suggested starting position for clear bits
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)
445 TRACE("(%p,%d,%d)\n", lpBits, ulCount, ulHint);
447 if (!lpBits || !ulCount || ulCount > lpBits->SizeOfBitMap)
450 ulEnd = lpBits->SizeOfBitMap;
452 if (ulHint + ulCount > lpBits->SizeOfBitMap)
457 while (ulPos < ulEnd)
459 /* FIXME: This could be made a _lot_ more efficient */
460 if (RtlAreBitsClear(lpBits, ulPos, ulCount))
463 /* Start from the beginning if we hit the end and started from ulHint */
464 if (ulPos == ulEnd - 1 && ulHint)
475 /*************************************************************************
476 * RtlFindSetBitsAndClear [NTDLL.@]
478 * Find a block of set bits in a bitmap, and clear them if found.
481 * lpBits [I] Bitmap pointer
482 * ulCount [I] Number of consecutive set bits to find
483 * ulHint [I] Suggested starting position for set bits
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)
492 TRACE("(%p,%d,%d)\n", lpBits, ulCount, ulHint);
494 ulPos = RtlFindSetBits(lpBits, ulCount, ulHint);
496 RtlClearBits(lpBits, ulPos, ulCount);
500 /*************************************************************************
501 * RtlFindClearBitsAndSet [NTDLL.@]
503 * Find a block of clear bits in a bitmap, and set them if found.
506 * lpBits [I] Bitmap pointer
507 * ulCount [I] Number of consecutive clear bits to find
508 * ulHint [I] Suggested starting position for clear bits
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)
517 TRACE("(%p,%d,%d)\n", lpBits, ulCount, ulHint);
519 ulPos = RtlFindClearBits(lpBits, ulCount, ulHint);
521 RtlSetBits(lpBits, ulPos, ulCount);
525 /*************************************************************************
526 * RtlNumberOfSetBits [NTDLL.@]
528 * Find the number of set bits in a bitmap.
531 * lpBits [I] Bitmap pointer
534 * The number of set bits.
536 ULONG WINAPI RtlNumberOfSetBits(PCRTL_BITMAP lpBits)
540 TRACE("(%p)\n", lpBits);
544 LPBYTE lpOut = (BYTE *)lpBits->Buffer;
545 ULONG ulCount, ulRemainder;
548 ulCount = lpBits->SizeOfBitMap >> 3;
549 ulRemainder = lpBits->SizeOfBitMap & 0x7;
553 ulSet += NTDLL_nibbleBitCount[*lpOut >> 4];
554 ulSet += NTDLL_nibbleBitCount[*lpOut & 0xf];
558 bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
559 ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
560 ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
565 /*************************************************************************
566 * RtlNumberOfClearBits [NTDLL.@]
568 * Find the number of clear bits in a bitmap.
571 * lpBits [I] Bitmap pointer
574 * The number of clear bits.
576 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
578 TRACE("(%p)\n", lpBits);
581 return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
585 /*************************************************************************
586 * RtlFindMostSignificantBit [NTDLL.@]
588 * Find the most significant bit in a 64 bit integer.
591 * The position of the most significant bit.
593 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
595 signed char ret = 32;
598 if (!(dw = (ulLong >> 32)))
618 return ret + NTDLL_mostSignificant[dw];
621 /*************************************************************************
622 * RtlFindLeastSignificantBit [NTDLL.@]
624 * Find the least significant bit in a 64 bit integer.
627 * The position of the least significant bit.
629 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
634 if (!(dw = (DWORD)ulLong))
637 if (!(dw = ulLong >> 32)) return -1;
654 return ret + NTDLL_leastSignificant[dw & 0x0f];
657 /*************************************************************************
660 * Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
662 static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
664 if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
669 /*************************************************************************
672 * Internal helper: Find the next run of set bits in a bitmap.
674 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
677 ULONG ulFoundAt = 0, ulCount = 0;
679 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
680 * at a time. But beware of the pointer arithmetics...
682 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
686 /* Check bits in first byte */
687 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
688 const BYTE bFirst = *lpOut & bMask;
692 /* Have a set bit in first byte */
695 /* Not every bit is set */
699 ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
701 ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
704 for (;ulOffset < 8; ulOffset++)
706 if (!(bFirst & (1 << ulOffset)))
709 return ulFoundAt; /* Set from start, but not until the end */
714 /* Set to the end - go on to count further bits */
718 /* every bit from start until the end of the byte is set */
720 ulCount = 8 - (ulStart & 7);
721 ulStart = (ulStart & ~7u) + 8;
725 ulStart = (ulStart & ~7u) + 8;
727 if (ulStart >= lpBits->SizeOfBitMap)
731 /* Count blocks of 8 set bits */
732 while (*lpOut == 0xff)
736 if (ulStart >= lpBits->SizeOfBitMap)
738 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
744 /* Count remaining contiguous bits, if any */
749 for (;ulOffset < 7u; ulOffset++)
751 if (!(*lpOut & (1 << ulOffset)))
760 /*************************************************************************
763 * Internal helper: Find the next run of set bits in a bitmap.
765 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
768 ULONG ulFoundAt = 0, ulCount = 0;
770 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
771 * at a time. But beware of the pointer arithmetics...
773 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
777 /* Check bits in first byte */
778 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
779 const BYTE bFirst = (~*lpOut) & bMask;
783 /* Have a clear bit in first byte */
786 /* Not every bit is clear */
790 ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
792 ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
795 for (;ulOffset < 8; ulOffset++)
797 if (!(bFirst & (1 << ulOffset)))
800 return ulFoundAt; /* Clear from start, but not until the end */
805 /* Clear to the end - go on to count further bits */
809 /* Every bit from start until the end of the byte is clear */
811 ulCount = 8 - (ulStart & 7);
812 ulStart = (ulStart & ~7u) + 8;
816 ulStart = (ulStart & ~7u) + 8;
818 if (ulStart >= lpBits->SizeOfBitMap)
822 /* Count blocks of 8 clear bits */
827 if (ulStart >= lpBits->SizeOfBitMap)
829 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
835 /* Count remaining contiguous bits, if any */
840 for (;ulOffset < 7u; ulOffset++)
842 if (*lpOut & (1 << ulOffset))
851 /*************************************************************************
852 * RtlFindNextForwardRunSet [NTDLL.@]
854 * Find the next run of set bits in a bitmap.
857 * lpBits [I] Bitmap pointer
858 * ulStart [I] Bit position to start searching from
859 * lpPos [O] Start of run
862 * Success: The length of the next set run in the bitmap. lpPos is set to
863 * the start of the run.
864 * Failure: 0, if no run is found or any parameters are invalid.
866 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
870 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
872 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
873 *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
878 /*************************************************************************
879 * RtlFindNextForwardRunClear [NTDLL.@]
881 * Find the next run of clear bits in a bitmap.
884 * lpBits [I] Bitmap pointer
885 * ulStart [I] Bit position to start searching from
886 * lpPos [O] Start of run
889 * Success: The length of the next clear run in the bitmap. lpPos is set to
890 * the start of the run.
891 * Failure: 0, if no run is found or any parameters are invalid.
893 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
897 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
899 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
900 *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
905 /*************************************************************************
906 * RtlFindLastBackwardRunSet [NTDLL.@]
908 * Find a previous run of set bits in a bitmap.
911 * lpBits [I] Bitmap pointer
912 * ulStart [I] Bit position to start searching from
913 * lpPos [O] Start of run
916 * Success: The length of the previous set run in the bitmap. lpPos is set to
917 * the start of the run.
918 * Failure: 0, if no run is found or any parameters are invalid.
920 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
922 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
926 /*************************************************************************
927 * RtlFindLastBackwardRunClear [NTDLL.@]
929 * Find a previous run of clear bits in a bitmap.
932 * lpBits [I] Bitmap pointer
933 * ulStart [I] Bit position to start searching from
934 * lpPos [O] Start of run
937 * Success: The length of the previous clear run in the bitmap. lpPos is set
938 * to the start of the run.
939 * Failure: 0, if no run is found or any parameters are invalid.
941 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
943 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
947 /*************************************************************************
950 * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
952 static ULONG NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
953 ULONG ulCount, BOOLEAN bLongest,
954 ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
956 BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
957 ULONG ulPos = 0, ulRuns = 0;
959 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
964 while (ulPos < lpBits->SizeOfBitMap)
966 /* Find next set/clear run */
967 ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
969 if (ulNextPos == ~0U)
972 if (bLongest && ulRuns == ulCount)
974 /* Sort runs with shortest at end, if they are out of order */
976 qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
978 /* Replace last run if this one is bigger */
979 if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
981 lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
982 lpSeries[ulRuns - 1].NumberOfBits = ulSize;
984 /* We need to re-sort the array, _if_ we didn't leave it sorted */
985 if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
991 /* Append to found runs */
992 lpSeries[ulRuns].StartingIndex = ulNextPos;
993 lpSeries[ulRuns].NumberOfBits = ulSize;
996 if (!bLongest && ulRuns == ulCount)
999 ulPos = ulNextPos + ulSize;
1004 /*************************************************************************
1005 * RtlFindSetRuns [NTDLL.@]
1007 * Find a series of set runs in a bitmap.
1010 * lpBits [I] Bitmap pointer
1011 * lpSeries [O] Array for each run found
1012 * ulCount [I] Number of runs to find
1013 * bLongest [I] Whether to find the very longest runs or not
1016 * The number of set runs found.
1018 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1019 ULONG ulCount, BOOLEAN bLongest)
1021 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1023 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1026 /*************************************************************************
1027 * RtlFindClearRuns [NTDLL.@]
1029 * Find a series of clear runs in a bitmap.
1032 * lpBits [I] Bitmap pointer
1033 * ulSeries [O] Array for each run found
1034 * ulCount [I] Number of runs to find
1035 * bLongest [I] Whether to find the very longest runs or not
1038 * The number of clear runs found.
1040 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1041 ULONG ulCount, BOOLEAN bLongest)
1043 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1045 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1048 /*************************************************************************
1049 * RtlFindLongestRunSet [NTDLL.@]
1051 * Find the longest set run in a bitmap.
1054 * lpBits [I] Bitmap pointer
1055 * pulStart [O] Destination for start of run
1058 * The length of the run found, or 0 if no run is found.
1060 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1064 TRACE("(%p,%p)\n", lpBits, pulStart);
1066 if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1069 *pulStart = br.StartingIndex;
1070 return br.NumberOfBits;
1075 /*************************************************************************
1076 * RtlFindLongestRunClear [NTDLL.@]
1078 * Find the longest clear run in a bitmap.
1081 * lpBits [I] Bitmap pointer
1082 * pulStart [O] Destination for start of run
1085 * The length of the run found, or 0 if no run is found.
1087 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1091 TRACE("(%p,%p)\n", lpBits, pulStart);
1093 if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1096 *pulStart = br.StartingIndex;
1097 return br.NumberOfBits;