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 bMasked = *lpOut & NTDLL_maskBits[ulRemainder];
559 ulSet += NTDLL_nibbleBitCount[bMasked >> 4];
560 ulSet += NTDLL_nibbleBitCount[bMasked & 0xf];
561 }
562 return ulSet;
563 }
564
565 /*************************************************************************
566 * RtlNumberOfClearBits [NTDLL.@]
567 *
568 * Find the number of clear bits in a bitmap.
569 *
570 * PARAMS
571 * lpBits [I] Bitmap pointer
572 *
573 * RETURNS
574 * The number of clear bits.
575 */
576 ULONG WINAPI RtlNumberOfClearBits(PCRTL_BITMAP lpBits)
577 {
578 TRACE("(%p)\n", lpBits);
579
580 if (lpBits)
581 return lpBits->SizeOfBitMap - RtlNumberOfSetBits(lpBits);
582 return 0;
583 }
584
585 /*************************************************************************
586 * RtlFindMostSignificantBit [NTDLL.@]
587 *
588 * Find the most significant bit in a 64 bit integer.
589 *
590 * RETURNS
591 * The position of the most significant bit.
592 */
593 CCHAR WINAPI RtlFindMostSignificantBit(ULONGLONG ulLong)
594 {
595 signed char ret = 32;
596 DWORD dw;
597
598 if (!(dw = (ulLong >> 32)))
599 {
600 ret = 0;
601 dw = (DWORD)ulLong;
602 }
603 if (dw & 0xffff0000)
604 {
605 dw >>= 16;
606 ret += 16;
607 }
608 if (dw & 0xff00)
609 {
610 dw >>= 8;
611 ret += 8;
612 }
613 if (dw & 0xf0)
614 {
615 dw >>= 4;
616 ret += 4;
617 }
618 return ret + NTDLL_mostSignificant[dw];
619 }
620
621 /*************************************************************************
622 * RtlFindLeastSignificantBit [NTDLL.@]
623 *
624 * Find the least significant bit in a 64 bit integer.
625 *
626 * RETURNS
627 * The position of the least significant bit.
628 */
629 CCHAR WINAPI RtlFindLeastSignificantBit(ULONGLONG ulLong)
630 {
631 signed char ret = 0;
632 DWORD dw;
633
634 if (!(dw = (DWORD)ulLong))
635 {
636 ret = 32;
637 if (!(dw = ulLong >> 32)) return -1;
638 }
639 if (!(dw & 0xffff))
640 {
641 dw >>= 16;
642 ret += 16;
643 }
644 if (!(dw & 0xff))
645 {
646 dw >>= 8;
647 ret += 8;
648 }
649 if (!(dw & 0x0f))
650 {
651 dw >>= 4;
652 ret += 4;
653 }
654 return ret + NTDLL_leastSignificant[dw & 0x0f];
655 }
656
657 /*************************************************************************
658 * NTDLL_RunSortFn
659 *
660 * Internal helper: qsort comparison function for RTL_BITMAP_RUN arrays
661 */
662 static int NTDLL_RunSortFn(const void *lhs, const void *rhs)
663 {
664 if (((const RTL_BITMAP_RUN*)lhs)->NumberOfBits > ((const RTL_BITMAP_RUN*)rhs)->NumberOfBits)
665 return -1;
666 return 1;
667 }
668
669 /*************************************************************************
670 * NTDLL_FindSetRun
671 *
672 * Internal helper: Find the next run of set bits in a bitmap.
673 */
674 static ULONG NTDLL_FindSetRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
675 {
676 LPBYTE lpOut;
677 ULONG ulFoundAt = 0, ulCount = 0;
678
679 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
680 * at a time. But beware of the pointer arithmetics...
681 */
682 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
683
684 while (1)
685 {
686 /* Check bits in first byte */
687 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
688 const BYTE bFirst = *lpOut & bMask;
689
690 if (bFirst)
691 {
692 /* Have a set bit in first byte */
693 if (bFirst != bMask)
694 {
695 /* Not every bit is set */
696 ULONG ulOffset;
697
698 if (bFirst & 0x0f)
699 ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
700 else
701 ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
702 ulStart += ulOffset;
703 ulFoundAt = ulStart;
704 for (;ulOffset < 8; ulOffset++)
705 {
706 if (!(bFirst & (1 << ulOffset)))
707 {
708 *lpSize = ulCount;
709 return ulFoundAt; /* Set from start, but not until the end */
710 }
711 ulCount++;
712 ulStart++;
713 }
714 /* Set to the end - go on to count further bits */
715 lpOut++;
716 break;
717 }
718 /* every bit from start until the end of the byte is set */
719 ulFoundAt = ulStart;
720 ulCount = 8 - (ulStart & 7);
721 ulStart = (ulStart & ~7u) + 8;
722 lpOut++;
723 break;
724 }
725 ulStart = (ulStart & ~7u) + 8;
726 lpOut++;
727 if (ulStart >= lpBits->SizeOfBitMap)
728 return ~0U;
729 }
730
731 /* Count blocks of 8 set bits */
732 while (*lpOut == 0xff)
733 {
734 ulCount += 8;
735 ulStart += 8;
736 if (ulStart >= lpBits->SizeOfBitMap)
737 {
738 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
739 return ulFoundAt;
740 }
741 lpOut++;
742 }
743
744 /* Count remaining contiguous bits, if any */
745 if (*lpOut & 1)
746 {
747 ULONG ulOffset = 0;
748
749 for (;ulOffset < 7u; ulOffset++)
750 {
751 if (!(*lpOut & (1 << ulOffset)))
752 break;
753 ulCount++;
754 }
755 }
756 *lpSize = ulCount;
757 return ulFoundAt;
758 }
759
760 /*************************************************************************
761 * NTDLL_FindClearRun
762 *
763 * Internal helper: Find the next run of set bits in a bitmap.
764 */
765 static ULONG NTDLL_FindClearRun(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpSize)
766 {
767 LPBYTE lpOut;
768 ULONG ulFoundAt = 0, ulCount = 0;
769
770 /* FIXME: It might be more efficient/cleaner to manipulate four bytes
771 * at a time. But beware of the pointer arithmetics...
772 */
773 lpOut = ((BYTE*)lpBits->Buffer) + (ulStart >> 3u);
774
775 while (1)
776 {
777 /* Check bits in first byte */
778 const BYTE bMask = (0xff << (ulStart & 7)) & 0xff;
779 const BYTE bFirst = (~*lpOut) & bMask;
780
781 if (bFirst)
782 {
783 /* Have a clear bit in first byte */
784 if (bFirst != bMask)
785 {
786 /* Not every bit is clear */
787 ULONG ulOffset;
788
789 if (bFirst & 0x0f)
790 ulOffset = NTDLL_leastSignificant[bFirst & 0x0f];
791 else
792 ulOffset = 4 + NTDLL_leastSignificant[bFirst >> 4];
793 ulStart += ulOffset;
794 ulFoundAt = ulStart;
795 for (;ulOffset < 8; ulOffset++)
796 {
797 if (!(bFirst & (1 << ulOffset)))
798 {
799 *lpSize = ulCount;
800 return ulFoundAt; /* Clear from start, but not until the end */
801 }
802 ulCount++;
803 ulStart++;
804 }
805 /* Clear to the end - go on to count further bits */
806 lpOut++;
807 break;
808 }
809 /* Every bit from start until the end of the byte is clear */
810 ulFoundAt = ulStart;
811 ulCount = 8 - (ulStart & 7);
812 ulStart = (ulStart & ~7u) + 8;
813 lpOut++;
814 break;
815 }
816 ulStart = (ulStart & ~7u) + 8;
817 lpOut++;
818 if (ulStart >= lpBits->SizeOfBitMap)
819 return ~0U;
820 }
821
822 /* Count blocks of 8 clear bits */
823 while (!*lpOut)
824 {
825 ulCount += 8;
826 ulStart += 8;
827 if (ulStart >= lpBits->SizeOfBitMap)
828 {
829 *lpSize = ulCount - (ulStart - lpBits->SizeOfBitMap);
830 return ulFoundAt;
831 }
832 lpOut++;
833 }
834
835 /* Count remaining contiguous bits, if any */
836 if (!(*lpOut & 1))
837 {
838 ULONG ulOffset = 0;
839
840 for (;ulOffset < 7u; ulOffset++)
841 {
842 if (*lpOut & (1 << ulOffset))
843 break;
844 ulCount++;
845 }
846 }
847 *lpSize = ulCount;
848 return ulFoundAt;
849 }
850
851 /*************************************************************************
852 * RtlFindNextForwardRunSet [NTDLL.@]
853 *
854 * Find the next run of set bits in a bitmap.
855 *
856 * PARAMS
857 * lpBits [I] Bitmap pointer
858 * ulStart [I] Bit position to start searching from
859 * lpPos [O] Start of run
860 *
861 * RETURNS
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.
865 */
866 ULONG WINAPI RtlFindNextForwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
867 {
868 ULONG ulSize = 0;
869
870 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
871
872 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
873 *lpPos = NTDLL_FindSetRun(lpBits, ulStart, &ulSize);
874
875 return ulSize;
876 }
877
878 /*************************************************************************
879 * RtlFindNextForwardRunClear [NTDLL.@]
880 *
881 * Find the next run of clear bits in a bitmap.
882 *
883 * PARAMS
884 * lpBits [I] Bitmap pointer
885 * ulStart [I] Bit position to start searching from
886 * lpPos [O] Start of run
887 *
888 * RETURNS
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.
892 */
893 ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
894 {
895 ULONG ulSize = 0;
896
897 TRACE("(%p,%d,%p)\n", lpBits, ulStart, lpPos);
898
899 if (lpBits && ulStart < lpBits->SizeOfBitMap && lpPos)
900 *lpPos = NTDLL_FindClearRun(lpBits, ulStart, &ulSize);
901
902 return ulSize;
903 }
904
905 /*************************************************************************
906 * RtlFindLastBackwardRunSet [NTDLL.@]
907 *
908 * Find a previous run of set bits in a bitmap.
909 *
910 * PARAMS
911 * lpBits [I] Bitmap pointer
912 * ulStart [I] Bit position to start searching from
913 * lpPos [O] Start of run
914 *
915 * RETURNS
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.
919 */
920 ULONG WINAPI RtlFindLastBackwardRunSet(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
921 {
922 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
923 return 0;
924 }
925
926 /*************************************************************************
927 * RtlFindLastBackwardRunClear [NTDLL.@]
928 *
929 * Find a previous run of clear bits in a bitmap.
930 *
931 * PARAMS
932 * lpBits [I] Bitmap pointer
933 * ulStart [I] Bit position to start searching from
934 * lpPos [O] Start of run
935 *
936 * RETURNS
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.
940 */
941 ULONG WINAPI RtlFindLastBackwardRunClear(PCRTL_BITMAP lpBits, ULONG ulStart, PULONG lpPos)
942 {
943 FIXME("(%p,%d,%p)-stub!\n", lpBits, ulStart, lpPos);
944 return 0;
945 }
946
947 /*************************************************************************
948 * NTDLL_FindRuns
949 *
950 * Internal implementation of RtlFindSetRuns/RtlFindClearRuns.
951 */
952 static ULONG NTDLL_FindRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
953 ULONG ulCount, BOOLEAN bLongest,
954 ULONG (*fn)(PCRTL_BITMAP,ULONG,PULONG))
955 {
956 BOOL bNeedSort = ulCount > 1 ? TRUE : FALSE;
957 ULONG ulPos = 0, ulRuns = 0;
958
959 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
960
961 if (!ulCount)
962 return ~0U;
963
964 while (ulPos < lpBits->SizeOfBitMap)
965 {
966 /* Find next set/clear run */
967 ULONG ulSize, ulNextPos = fn(lpBits, ulPos, &ulSize);
968
969 if (ulNextPos == ~0U)
970 break;
971
972 if (bLongest && ulRuns == ulCount)
973 {
974 /* Sort runs with shortest at end, if they are out of order */
975 if (bNeedSort)
976 qsort(lpSeries, ulRuns, sizeof(RTL_BITMAP_RUN), NTDLL_RunSortFn);
977
978 /* Replace last run if this one is bigger */
979 if (ulSize > lpSeries[ulRuns - 1].NumberOfBits)
980 {
981 lpSeries[ulRuns - 1].StartingIndex = ulNextPos;
982 lpSeries[ulRuns - 1].NumberOfBits = ulSize;
983
984 /* We need to re-sort the array, _if_ we didn't leave it sorted */
985 if (ulRuns > 1 && ulSize > lpSeries[ulRuns - 2].NumberOfBits)
986 bNeedSort = TRUE;
987 }
988 }
989 else
990 {
991 /* Append to found runs */
992 lpSeries[ulRuns].StartingIndex = ulNextPos;
993 lpSeries[ulRuns].NumberOfBits = ulSize;
994 ulRuns++;
995
996 if (!bLongest && ulRuns == ulCount)
997 break;
998 }
999 ulPos = ulNextPos + ulSize;
1000 }
1001 return ulRuns;
1002 }
1003
1004 /*************************************************************************
1005 * RtlFindSetRuns [NTDLL.@]
1006 *
1007 * Find a series of set runs in a bitmap.
1008 *
1009 * PARAMS
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
1014 *
1015 * RETURNS
1016 * The number of set runs found.
1017 */
1018 ULONG WINAPI RtlFindSetRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1019 ULONG ulCount, BOOLEAN bLongest)
1020 {
1021 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1022
1023 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindSetRun);
1024 }
1025
1026 /*************************************************************************
1027 * RtlFindClearRuns [NTDLL.@]
1028 *
1029 * Find a series of clear runs in a bitmap.
1030 *
1031 * PARAMS
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
1036 *
1037 * RETURNS
1038 * The number of clear runs found.
1039 */
1040 ULONG WINAPI RtlFindClearRuns(PCRTL_BITMAP lpBits, PRTL_BITMAP_RUN lpSeries,
1041 ULONG ulCount, BOOLEAN bLongest)
1042 {
1043 TRACE("(%p,%p,%d,%d)\n", lpBits, lpSeries, ulCount, bLongest);
1044
1045 return NTDLL_FindRuns(lpBits, lpSeries, ulCount, bLongest, NTDLL_FindClearRun);
1046 }
1047
1048 /*************************************************************************
1049 * RtlFindLongestRunSet [NTDLL.@]
1050 *
1051 * Find the longest set run in a bitmap.
1052 *
1053 * PARAMS
1054 * lpBits [I] Bitmap pointer
1055 * pulStart [O] Destination for start of run
1056 *
1057 * RETURNS
1058 * The length of the run found, or 0 if no run is found.
1059 */
1060 ULONG WINAPI RtlFindLongestRunSet(PCRTL_BITMAP lpBits, PULONG pulStart)
1061 {
1062 RTL_BITMAP_RUN br;
1063
1064 TRACE("(%p,%p)\n", lpBits, pulStart);
1065
1066 if (RtlFindSetRuns(lpBits, &br, 1, TRUE) == 1)
1067 {
1068 if (pulStart)
1069 *pulStart = br.StartingIndex;
1070 return br.NumberOfBits;
1071 }
1072 return 0;
1073 }
1074
1075 /*************************************************************************
1076 * RtlFindLongestRunClear [NTDLL.@]
1077 *
1078 * Find the longest clear run in a bitmap.
1079 *
1080 * PARAMS
1081 * lpBits [I] Bitmap pointer
1082 * pulStart [O] Destination for start of run
1083 *
1084 * RETURNS
1085 * The length of the run found, or 0 if no run is found.
1086 */
1087 ULONG WINAPI RtlFindLongestRunClear(PCRTL_BITMAP lpBits, PULONG pulStart)
1088 {
1089 RTL_BITMAP_RUN br;
1090
1091 TRACE("(%p,%p)\n", lpBits, pulStart);
1092
1093 if (RtlFindClearRuns(lpBits, &br, 1, TRUE) == 1)
1094 {
1095 if (pulStart)
1096 *pulStart = br.StartingIndex;
1097 return br.NumberOfBits;
1098 }
1099 return 0;
1100 }
1101
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.