ReactOS 0.4.15-dev-7846-g8ba6c66
bitmap.c
Go to the documentation of this file.
1/*
2 * PROJECT: ReactOS system libraries
3 * LICENSE: GNU GPL - See COPYING in the top level directory
4 * BSD - See COPYING.ARM in the top level directory
5 * FILE: lib/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
7 * PROGRAMMER: Timo Kreuzer (timo.kreuzer@reactos.org)
8 */
9
10/* INCLUDES *****************************************************************/
11
12#include <rtl.h>
13
14#define NDEBUG
15#include <debug.h>
16
17// FIXME: hack
18#undef ASSERT
19#define ASSERT(...)
20
21#ifdef USE_RTL_BITMAP64
22#define _BITCOUNT 64
23#define MAXINDEX 0xFFFFFFFFFFFFFFFF
26#define RTL_BITMAP RTL_BITMAP64
27#define PRTL_BITMAP PRTL_BITMAP64
28#define RTL_BITMAP_RUN RTL_BITMAP_RUN64
29#define PRTL_BITMAP_RUN PRTL_BITMAP_RUN64
30#undef BitScanForward
31#define BitScanForward(Index, Mask) \
32 do { unsigned long tmp; BitScanForward64(&tmp, Mask); *Index = tmp; } while (0)
33#undef BitScanReverse
34#define BitScanReverse(Index, Mask) \
35 do { unsigned long tmp; BitScanReverse64(&tmp, Mask); *Index = tmp; } while (0)
36#define RtlFillMemoryUlong RtlFillMemoryUlonglong
37
38#define RtlInitializeBitMap RtlInitializeBitMap64
39#define RtlClearAllBits RtlClearAllBits64
40#define RtlSetAllBits RtlSetAllBits64
41#define RtlClearBit RtlClearBit64
42#define RtlSetBit RtlSetBit64
43#define RtlClearBits RtlClearBits64
44#define RtlSetBits RtlSetBits64
45#define RtlTestBit RtlTestBit64
46#define RtlAreBitsClear RtlAreBitsClear64
47#define RtlAreBitsSet RtlAreBitsSet64
48#define RtlNumberOfSetBits RtlNumberOfSetBits64
49#define RtlNumberOfClearBits RtlNumberOfClearBits64
50#define RtlFindClearBits RtlFindClearBits64
51#define RtlFindSetBits RtlFindSetBits64
52#define RtlFindClearBitsAndSet RtlFindClearBitsAndSet64
53#define RtlFindSetBitsAndClear RtlFindSetBitsAndClear64
54#define RtlFindNextForwardRunClear RtlFindNextForwardRunClear64
55#define RtlFindNextForwardRunSet RtlFindNextForwardRunSet64
56#define RtlFindFirstRunClear RtlFindFirstRunClear64
57#define RtlFindLastBackwardRunClear RtlFindLastBackwardRunClear64
58#define RtlFindClearRuns RtlFindClearRuns64
59#define RtlFindLongestRunClear RtlFindLongestRunClear64
60#define RtlFindLongestRunSet RtlFindLongestRunSet64
61#else
62#define _BITCOUNT 32
63#define MAXINDEX 0xFFFFFFFF
66#endif
67
68/* DATA *********************************************************************/
69
70/* Number of set bits per byte value */
71static const
74{
75 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
76 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0x */
77 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 1x */
78 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 2x */
79 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 3x */
80 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 4x */
81 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 5x */
82 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 6c */
83 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 7x */
84 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 8x */
85 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 9x */
86 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Ax */
87 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Bx */
88 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* Cx */
89 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Dx */
90 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* Ex */
91 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* Fx */
92};
93
94
95/* PRIVATE FUNCTIONS ********************************************************/
96
97static __inline
100 _In_ PRTL_BITMAP BitMapHeader,
102 _In_ BITMAP_INDEX MaxLength)
103{
104 BITMAP_INDEX Value, BitPos, Length;
105 PBITMAP_BUFFER Buffer, MaxBuffer;
106
107 /* If we are already at the end, the length of the run is zero */
108 ASSERT(StartingIndex <= BitMapHeader->SizeOfBitMap);
109 if (StartingIndex >= BitMapHeader->SizeOfBitMap)
110 return 0;
111
112 /* Calculate positions */
113 Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
114 BitPos = StartingIndex & (_BITCOUNT - 1);
115
116 /* Calculate the maximum length */
117 MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
118 MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
119
120 /* Clear the bits that don't belong to this run */
121 Value = *Buffer++ >> BitPos << BitPos;
122
123 /* Skip all clear ULONGs */
124 while (Value == 0 && Buffer < MaxBuffer)
125 {
126 Value = *Buffer++;
127 }
128
129 /* Did we reach the end? */
130 if (Value == 0)
131 {
132 /* Return maximum length */
133 return MaxLength;
134 }
135
136 /* We hit a set bit, check how many clear bits are left */
137 BitScanForward(&BitPos, Value);
138
139 /* Calculate length up to where we read */
140 Length = (BITMAP_INDEX)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
141 Length += BitPos - _BITCOUNT;
142
143 /* Make sure we don't go past the last bit */
144 if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
145 Length = BitMapHeader->SizeOfBitMap - StartingIndex;
146
147 /* Return the result */
148 return Length;
149}
150
151static __inline
154 _In_ PRTL_BITMAP BitMapHeader,
156 _In_ BITMAP_INDEX MaxLength)
157{
158 BITMAP_INDEX InvValue, BitPos, Length;
159 PBITMAP_BUFFER Buffer, MaxBuffer;
160
161 /* If we are already at the end, the length of the run is zero */
162 ASSERT(StartingIndex <= BitMapHeader->SizeOfBitMap);
163 if (StartingIndex >= BitMapHeader->SizeOfBitMap)
164 return 0;
165
166 /* Calculate positions */
167 Buffer = BitMapHeader->Buffer + StartingIndex / _BITCOUNT;
168 BitPos = StartingIndex & (_BITCOUNT - 1);
169
170 /* Calculate the maximum length */
171 MaxLength = min(MaxLength, BitMapHeader->SizeOfBitMap - StartingIndex);
172 MaxBuffer = Buffer + (BitPos + MaxLength + _BITCOUNT - 1) / _BITCOUNT;
173
174 /* Get the inversed value, clear bits that don't belong to the run */
175 InvValue = ~(*Buffer++) >> BitPos << BitPos;
176
177 /* Skip all set ULONGs */
178 while (InvValue == 0 && Buffer < MaxBuffer)
179 {
180 InvValue = ~(*Buffer++);
181 }
182
183 /* Did we reach the end? */
184 if (InvValue == 0)
185 {
186 /* Yes, return maximum */
187 return MaxLength;
188 }
189
190 /* We hit a clear bit, check how many set bits are left */
191 BitScanForward(&BitPos, InvValue);
192
193 /* Calculate length up to where we read */
194 Length = (ULONG)(Buffer - BitMapHeader->Buffer) * _BITCOUNT - StartingIndex;
195 Length += BitPos - _BITCOUNT;
196
197 /* Make sure we don't go past the last bit */
198 if (Length > BitMapHeader->SizeOfBitMap - StartingIndex)
199 Length = BitMapHeader->SizeOfBitMap - StartingIndex;
200
201 /* Return the result */
202 return Length;
203}
204
205
206/* PUBLIC FUNCTIONS **********************************************************/
207
208#ifndef USE_RTL_BITMAP64
209CCHAR
210NTAPI
212{
214
215#ifdef _M_AMD64
216 if (BitScanReverse64(&Position, Value))
217 {
218 return (CCHAR)Position;
219 }
220#else
222 {
223 return (CCHAR)(Position + _BITCOUNT);
224 }
225 else if (BitScanReverse(&Position, (ULONG)Value))
226 {
227 return (CCHAR)Position;
228 }
229#endif
230 return -1;
231}
232
233CCHAR
234NTAPI
236{
238
239#ifdef _M_AMD64
240 if (BitScanForward64(&Position, Value))
241 {
242 return (CCHAR)Position;
243 }
244#else
246 {
247 return (CCHAR)Position;
248 }
249 else if (BitScanForward(&Position, Value >> _BITCOUNT))
250 {
251 return (CCHAR)(Position + _BITCOUNT);
252 }
253#endif
254 return -1;
255}
256#endif /* !USE_RTL_BITMAP64 */
257
258VOID
259NTAPI
261 _Out_ PRTL_BITMAP BitMapHeader,
263 _In_opt_ ULONG SizeOfBitMap)
264{
265 /* Setup the bitmap header */
266 BitMapHeader->SizeOfBitMap = SizeOfBitMap;
267 BitMapHeader->Buffer = BitMapBuffer;
268}
269
270VOID
271NTAPI
273 _In_ PRTL_BITMAP BitMapHeader)
274{
275 BITMAP_INDEX LengthInUlongs;
276
277 LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
278 RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), 0);
279}
280
281VOID
282NTAPI
284 _In_ PRTL_BITMAP BitMapHeader)
285{
286 BITMAP_INDEX LengthInUlongs;
287
288 LengthInUlongs = (BitMapHeader->SizeOfBitMap + _BITCOUNT - 1) / _BITCOUNT;
289 RtlFillMemoryUlong(BitMapHeader->Buffer, LengthInUlongs * sizeof(BITMAP_INDEX), ~0);
290}
291
292VOID
293NTAPI
295 _In_ PRTL_BITMAP BitMapHeader,
296 _In_ BITMAP_INDEX BitNumber)
297{
298 ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
299 BitMapHeader->Buffer[BitNumber / _BITCOUNT] &= ~(1 << (BitNumber & (_BITCOUNT - 1)));
300}
301
302VOID
303NTAPI
305 _In_ PRTL_BITMAP BitMapHeader,
306 _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
307{
308 ASSERT(BitNumber <= BitMapHeader->SizeOfBitMap);
309 BitMapHeader->Buffer[BitNumber / _BITCOUNT] |= ((BITMAP_INDEX)1 << (BitNumber & (_BITCOUNT - 1)));
310}
311
312VOID
313NTAPI
315 _In_ PRTL_BITMAP BitMapHeader,
316 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX StartingIndex,
317 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToClear)
318{
319 BITMAP_INDEX Bits, Mask;
321
322 ASSERT(StartingIndex + NumberToClear <= BitMapHeader->SizeOfBitMap);
323
324 /* Calculate buffer start and first bit index */
325 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
326 Bits = StartingIndex & (_BITCOUNT - 1);
327
328 /* Are we unaligned? */
329 if (Bits)
330 {
331 /* Create an inverse mask by shifting MAXINDEX */
332 Mask = MAXINDEX << Bits;
333
334 /* This is what's left in the first ULONG */
335 Bits = _BITCOUNT - Bits;
336
337 /* Even less bits to clear? */
338 if (NumberToClear < Bits)
339 {
340 /* Calculate how many bits are left */
341 Bits -= NumberToClear;
342
343 /* Fixup the mask on the high side */
344 Mask = Mask << Bits >> Bits;
345
346 /* Clear bits and return */
347 *Buffer &= ~Mask;
348 return;
349 }
350
351 /* Clear bits */
352 *Buffer &= ~Mask;
353
354 /* Update buffer and left bits */
355 Buffer++;
356 NumberToClear -= Bits;
357 }
358
359 /* Clear all full ULONGs */
360 RtlFillMemoryUlong(Buffer, NumberToClear >> 3, 0);
361 Buffer += NumberToClear / _BITCOUNT;
362
363 /* Clear what's left */
364 NumberToClear &= (_BITCOUNT - 1);
365 if (NumberToClear != 0)
366 {
367 Mask = MAXINDEX << NumberToClear;
368 *Buffer &= Mask;
369 }
370}
371
372VOID
373NTAPI
375 _In_ PRTL_BITMAP BitMapHeader,
376 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex,
377 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
378{
379 BITMAP_INDEX Bits, Mask;
381
382 ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
383
384 /* Calculate buffer start and first bit index */
385 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
386 Bits = StartingIndex & (_BITCOUNT - 1);
387
388 /* Are we unaligned? */
389 if (Bits)
390 {
391 /* Create a mask by shifting MAXINDEX */
392 Mask = MAXINDEX << Bits;
393
394 /* This is what's left in the first ULONG */
395 Bits = _BITCOUNT - Bits;
396
397 /* Even less bits to clear? */
398 if (NumberToSet < Bits)
399 {
400 /* Calculate how many bits are left */
401 Bits -= NumberToSet;
402
403 /* Fixup the mask on the high side */
404 Mask = Mask << Bits >> Bits;
405
406 /* Set bits and return */
407 *Buffer |= Mask;
408 return;
409 }
410
411 /* Set bits */
412 *Buffer |= Mask;
413
414 /* Update buffer and left bits */
415 Buffer++;
416 NumberToSet -= Bits;
417 }
418
419 /* Set all full ULONGs */
420 RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXINDEX);
421 Buffer += NumberToSet / _BITCOUNT;
422
423 /* Set what's left */
424 NumberToSet &= (_BITCOUNT - 1);
425 if (NumberToSet != 0)
426 {
427 Mask = MAXINDEX << NumberToSet;
428 *Buffer |= ~Mask;
429 }
430}
431
433NTAPI
435 _In_ PRTL_BITMAP BitMapHeader,
436 _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
437{
438 ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
439 return (BitMapHeader->Buffer[BitNumber / _BITCOUNT] >> (BitNumber & (_BITCOUNT - 1))) & 1;
440}
441
443NTAPI
445 _In_ PRTL_BITMAP BitMapHeader,
448{
449 /* Verify parameters */
450 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
452 return FALSE;
453
454 return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
455}
456
458NTAPI
460 _In_ PRTL_BITMAP BitMapHeader,
463{
464 /* Verify parameters */
465 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
467 return FALSE;
468
469 return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
470}
471
473NTAPI
475 _In_ PRTL_BITMAP BitMapHeader)
476{
477 PUCHAR Byte, MaxByte;
478 BITMAP_INDEX BitCount = 0;
479 ULONG Shift;
480
481 Byte = (PUCHAR)BitMapHeader->Buffer;
482 MaxByte = Byte + BitMapHeader->SizeOfBitMap / 8;
483
484 while (Byte < MaxByte)
485 {
486 BitCount += BitCountTable[*Byte++];
487 }
488
489 if (BitMapHeader->SizeOfBitMap & 7)
490 {
491 Shift = 8 - (BitMapHeader->SizeOfBitMap & 7);
492 BitCount += BitCountTable[((*Byte) << Shift) & 0xFF];
493 }
494
495 return BitCount;
496}
497
499NTAPI
501 _In_ PRTL_BITMAP BitMapHeader)
502{
503 /* Do some math */
504 return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
505}
506
508NTAPI
510 _In_ PRTL_BITMAP BitMapHeader,
513{
514 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
515
516 /* Check for valid parameters */
517 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
518 {
519 return MAXINDEX;
520 }
521
522 /* Check if the hint is outside the bitmap */
523 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
524
525 /* Check for trivial case */
526 if (NumberToFind == 0)
527 {
528 /* Return hint rounded down to byte margin */
529 return HintIndex & ~7;
530 }
531
532 /* First margin is end of bitmap */
533 Margin = BitMapHeader->SizeOfBitMap;
534
535retry:
536 /* Start with hint index, length is 0 */
537 CurrentBit = HintIndex;
538
539 /* Loop until something is found or the end is reached */
540 while (CurrentBit + NumberToFind < Margin)
541 {
542 /* Search for the next clear run, by skipping a set run */
543 CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
544 CurrentBit,
545 MAXINDEX);
546
547 /* Get length of the clear bit run */
548 CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
549 CurrentBit,
551
552 /* Is this long enough? */
553 if (CurrentLength >= NumberToFind)
554 {
555 /* It is */
556 return CurrentBit;
557 }
558
559 CurrentBit += CurrentLength;
560 }
561
562 /* Did we start at a hint? */
563 if (HintIndex)
564 {
565 /* Retry at the start */
566 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
567 HintIndex = 0;
568 goto retry;
569 }
570
571 /* Nothing found */
572 return MAXINDEX;
573}
574
576NTAPI
578 _In_ PRTL_BITMAP BitMapHeader,
581{
582 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
583
584 /* Check for valid parameters */
585 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
586 {
587 return MAXINDEX;
588 }
589
590 /* Check if the hint is outside the bitmap */
591 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
592
593 /* Check for trivial case */
594 if (NumberToFind == 0)
595 {
596 /* Return hint rounded down to byte margin */
597 return HintIndex & ~7;
598 }
599
600 /* First margin is end of bitmap */
601 Margin = BitMapHeader->SizeOfBitMap;
602
603retry:
604 /* Start with hint index, length is 0 */
605 CurrentBit = HintIndex;
606
607 /* Loop until something is found or the end is reached */
608 while (CurrentBit + NumberToFind <= Margin)
609 {
610 /* Search for the next set run, by skipping a clear run */
611 CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
612 CurrentBit,
613 MAXINDEX);
614
615 /* Get length of the set bit run */
616 CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
617 CurrentBit,
619
620 /* Is this long enough? */
621 if (CurrentLength >= NumberToFind)
622 {
623 /* It is */
624 return CurrentBit;
625 }
626
627 CurrentBit += CurrentLength;
628 }
629
630 /* Did we start at a hint? */
631 if (HintIndex)
632 {
633 /* Retry at the start */
634 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
635 HintIndex = 0;
636 goto retry;
637 }
638
639 /* Nothing found */
640 return MAXINDEX;
641}
642
644NTAPI
646 _In_ PRTL_BITMAP BitMapHeader,
649{
651
652 /* Try to find clear bits */
654
655 /* Did we get something? */
656 if (Position != MAXINDEX)
657 {
658 /* Yes, set the bits */
659 RtlSetBits(BitMapHeader, Position, NumberToFind);
660 }
661
662 /* Return what we found */
663 return Position;
664}
665
667NTAPI
669 _In_ PRTL_BITMAP BitMapHeader,
672{
674
675 /* Try to find set bits */
677
678 /* Did we get something? */
679 if (Position != MAXINDEX)
680 {
681 /* Yes, clear the bits */
682 RtlClearBits(BitMapHeader, Position, NumberToFind);
683 }
684
685 /* Return what we found */
686 return Position;
687}
688
690NTAPI
692 _In_ PRTL_BITMAP BitMapHeader,
693 _In_ BITMAP_INDEX FromIndex,
694 _Out_ PBITMAP_INDEX StartingRunIndex)
695{
697
698 /* Check for buffer overrun */
699 if (FromIndex >= BitMapHeader->SizeOfBitMap)
700 {
701 *StartingRunIndex = FromIndex;
702 return 0;
703 }
704
705 /* Assume a set run first, count it's length */
706 Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXINDEX);
707 *StartingRunIndex = FromIndex + Length;
708
709 /* Now return the length of the run */
710 return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXINDEX);
711}
712
714NTAPI
716 _In_ PRTL_BITMAP BitMapHeader,
717 _In_ BITMAP_INDEX FromIndex,
718 _Out_ PBITMAP_INDEX StartingRunIndex)
719{
721
722 /* Check for buffer overrun */
723 if (FromIndex >= BitMapHeader->SizeOfBitMap)
724 {
725 *StartingRunIndex = FromIndex;
726 return 0;
727 }
728
729 /* Assume a clear run first, count it's length */
730 Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXINDEX);
731 *StartingRunIndex = FromIndex + Length;
732
733 /* Now return the length of the run */
734 return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex + Length, MAXINDEX);
735}
736
738NTAPI
740 _In_ PRTL_BITMAP BitMapHeader,
742{
743 return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
744}
745
747NTAPI
749 _In_ PRTL_BITMAP BitMapHeader,
750 _In_ BITMAP_INDEX FromIndex,
751 _Out_ PBITMAP_INDEX StartingRunIndex)
752{
753 BITMAP_INDEX Value, InvValue, BitPos;
755
756 /* Make sure we don't go past the end */
757 FromIndex = min(FromIndex, BitMapHeader->SizeOfBitMap - 1);
758
759 /* Calculate positions */
760 Buffer = BitMapHeader->Buffer + FromIndex / _BITCOUNT;
761 BitPos = (_BITCOUNT - 1) - (FromIndex & (_BITCOUNT - 1));
762
763 /* Get the inversed value, clear bits that don't belong to the run */
764 InvValue = ~(*Buffer--) << BitPos >> BitPos;
765
766 /* Skip all set ULONGs */
767 while (InvValue == 0)
768 {
769 /* Did we already reach past the first ULONG? */
770 if (Buffer < BitMapHeader->Buffer)
771 {
772 /* Yes, nothing found */
773 return 0;
774 }
775
776 InvValue = ~(*Buffer--);
777 }
778
779 /* We hit a clear bit, check how many set bits are left */
780 BitScanReverse(&BitPos, InvValue);
781
782 /* Calculate last bit position */
783 FromIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos);
784
785 Value = ~InvValue << ((_BITCOUNT - 1) - BitPos) >> ((_BITCOUNT - 1) - BitPos);
786
787 /* Skip all clear ULONGs */
788 while (Value == 0 && Buffer >= BitMapHeader->Buffer)
789 {
790 Value = *Buffer--;
791 }
792
793 if (Value != 0)
794 {
795 /* We hit a set bit, check how many clear bits are left */
796 BitScanReverse(&BitPos, Value);
797
798 /* Calculate Starting Index */
799 *StartingRunIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos + 1);
800 }
801 else
802 {
803 /* We reached the start of the bitmap */
804 *StartingRunIndex = 0;
805 }
806
807 /* Return length of the run */
808 return (FromIndex - *StartingRunIndex);
809}
810
811
812ULONG
813NTAPI
815 _In_ PRTL_BITMAP BitMapHeader,
816 _In_ PRTL_BITMAP_RUN RunArray,
817 _In_ ULONG SizeOfRunArray,
818 _In_ BOOLEAN LocateLongestRuns)
819{
820 BITMAP_INDEX StartingIndex, NumberOfBits, FromIndex = 0, SmallestRun = 0;
821 ULONG Run;
822
823 /* Loop the runs */
824 for (Run = 0; Run < SizeOfRunArray; Run++)
825 {
826 /* Look for a run */
827 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
828 FromIndex,
830
831 /* Nothing more found? Quit looping. */
832 if (NumberOfBits == 0) break;
833
834 /* Add another run */
835 RunArray[Run].StartingIndex = StartingIndex;
836 RunArray[Run].NumberOfBits = NumberOfBits;
837
838 /* Update smallest run */
839 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
840 {
841 SmallestRun = Run;
842 }
843
844 /* Advance bits */
845 FromIndex = StartingIndex + NumberOfBits;
846 }
847
848 /* Check if we are finished */
849 if (Run < SizeOfRunArray || !LocateLongestRuns)
850 {
851 /* Return the number of found runs */
852 return Run;
853 }
854
855 while (1)
856 {
857 /* Look for a run */
858 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
859 FromIndex,
861
862 /* Nothing more found? Quit looping. */
863 if (NumberOfBits == 0) break;
864
865 /* Check if we have something to update */
866 if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
867 {
868 /* Update smallest run */
869 RunArray[SmallestRun].StartingIndex = StartingIndex;
870 RunArray[SmallestRun].NumberOfBits = NumberOfBits;
871
872 /* Loop all runs */
873 for (Run = 0; Run < SizeOfRunArray; Run++)
874 {
875 /*Is this the new smallest run? */
876 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
877 {
878 /* Set it as new smallest run */
879 SmallestRun = Run;
880 }
881 }
882 }
883
884 /* Advance bits */
885 FromIndex += NumberOfBits;
886 }
887
888 return Run;
889}
890
892NTAPI
894 IN PRTL_BITMAP BitMapHeader,
896{
897 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
898
899 while (1)
900 {
901 /* Look for a run */
902 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
903 FromIndex,
904 &Index);
905
906 /* Nothing more found? Quit looping. */
907 if (NumberOfBits == 0) break;
908
909 /* Was that the longest run? */
910 if (NumberOfBits > MaxNumberOfBits)
911 {
912 /* Update values */
913 MaxNumberOfBits = NumberOfBits;
915 }
916
917 /* Advance bits */
918 FromIndex += NumberOfBits;
919 }
920
921 return MaxNumberOfBits;
922}
923
925NTAPI
927 IN PRTL_BITMAP BitMapHeader,
929{
930 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
931
932 while (1)
933 {
934 /* Look for a run */
935 NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
936 FromIndex,
937 &Index);
938
939 /* Nothing more found? Quit looping. */
940 if (NumberOfBits == 0) break;
941
942 /* Was that the longest run? */
943 if (NumberOfBits > MaxNumberOfBits)
944 {
945 /* Update values */
946 MaxNumberOfBits = NumberOfBits;
948 }
949
950 /* Advance bits */
951 FromIndex += NumberOfBits;
952 }
953
954 return MaxNumberOfBits;
955}
956
unsigned char BOOLEAN
#define __drv_aliasesMem
Definition: btrfs_drv.h:203
while(CdLookupNextInitialFileDirent(IrpContext, Fcb, FileContext))
Definition: bufpool.h:45
#define FALSE
Definition: types.h:117
unsigned char Byte
Definition: zlib.h:37
unsigned int Mask
Definition: fpcontrol.c:82
#define BitScanReverse
Definition: interlocked.h:6
#define BitScanForward
Definition: interlocked.h:5
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
unsigned __int64 ULONG64
Definition: imports.h:198
static TRIVERTEX ULONG
Definition: bitmap.c:45
#define min(a, b)
Definition: monoChain.cc:55
#define _Out_
Definition: ms_sal.h:345
#define _In_
Definition: ms_sal.h:308
#define _In_opt_
Definition: ms_sal.h:309
#define _In_range_(lb, ub)
Definition: ms_sal.h:571
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
ULONG NTAPI RtlFindClearRuns(_In_ PRTL_BITMAP BitMapHeader, _In_ PRTL_BITMAP_RUN RunArray, _In_ ULONG SizeOfRunArray, _In_ BOOLEAN LocateLongestRuns)
Definition: bitmap.c:814
BITMAP_INDEX NTAPI RtlFindClearBitsAndSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:645
VOID NTAPI RtlClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToClear)
Definition: bitmap.c:314
VOID NTAPI RtlSetBits(_In_ PRTL_BITMAP BitMapHeader, _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex, _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
Definition: bitmap.c:374
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:691
BITMAP_INDEX NTAPI RtlFindSetBitsAndClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:668
BOOLEAN NTAPI RtlAreBitsClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
Definition: bitmap.c:444
VOID NTAPI RtlClearAllBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:272
BITMAP_INDEX NTAPI RtlFindLongestRunSet(IN PRTL_BITMAP BitMapHeader, IN PBITMAP_INDEX StartingIndex)
Definition: bitmap.c:926
ULONG * PBITMAP_INDEX
Definition: bitmap.c:64
#define _BITCOUNT
Definition: bitmap.c:62
static const UCHAR BitCountTable[256]
Definition: bitmap.c:73
BOOLEAN NTAPI RtlAreBitsSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
Definition: bitmap.c:459
BITMAP_INDEX NTAPI RtlNumberOfClearBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:500
VOID NTAPI RtlClearBit(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX BitNumber)
Definition: bitmap.c:294
BITMAP_INDEX NTAPI RtlFindNextForwardRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:715
BITMAP_INDEX NTAPI RtlFindLongestRunClear(IN PRTL_BITMAP BitMapHeader, IN PBITMAP_INDEX StartingIndex)
Definition: bitmap.c:893
BITMAP_INDEX NTAPI RtlFindSetBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:577
BITMAP_INDEX NTAPI RtlNumberOfSetBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:474
VOID NTAPI RtlInitializeBitMap(_Out_ PRTL_BITMAP BitMapHeader, _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer, _In_opt_ ULONG SizeOfBitMap)
Definition: bitmap.c:260
ULONG BITMAP_INDEX
Definition: bitmap.c:64
VOID NTAPI RtlSetBit(_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
Definition: bitmap.c:304
BITMAP_INDEX NTAPI RtlFindLastBackwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:748
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
#define ASSERT(...)
Definition: bitmap.c:19
#define MAXINDEX
Definition: bitmap.c:63
BOOLEAN NTAPI RtlTestBit(_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
Definition: bitmap.c:434
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
BITMAP_INDEX NTAPI RtlFindClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:509
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99
CCHAR NTAPI RtlFindLeastSignificantBit(ULONGLONG Value)
Definition: bitmap.c:235
CCHAR NTAPI RtlFindMostSignificantBit(ULONGLONG Value)
Definition: bitmap.c:211
ULONG BITMAP_BUFFER
Definition: bitmap.c:65
BITMAP_INDEX NTAPI RtlFindFirstRunClear(_In_ PRTL_BITMAP BitMapHeader, _Out_ PBITMAP_INDEX StartingIndex)
Definition: bitmap.c:739
VOID NTAPI RtlSetAllBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:283
Definition: bidi.c:434
static COORD Position
Definition: mouse.c:34
#define NTAPI
Definition: typedefs.h:36
#define IN
Definition: typedefs.h:39
unsigned char * PUCHAR
Definition: typedefs.h:53
uint32_t ULONG
Definition: typedefs.h:59
uint64_t ULONGLONG
Definition: typedefs.h:67
char CCHAR
Definition: typedefs.h:51
struct tagRun Run
_In_ WDFCOLLECTION _In_ ULONG Index
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:413
_In_ ULONG Shift
Definition: rtlfuncs.h:2681
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:610
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
unsigned char UCHAR
Definition: xmlstorage.h:181