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 }
1104
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.