Sync with trunk r63502.
[reactos.git] / lib / rtl / bitmap.c
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
24 typedef ULONG64 BITMAP_INDEX, *PBITMAP_INDEX;
25 typedef ULONG64 BITMAP_BUFFER, *PBITMAP_BUFFER;
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
64 typedef ULONG BITMAP_INDEX, *PBITMAP_INDEX;
65 typedef ULONG BITMAP_BUFFER, *PBITMAP_BUFFER;
66 #endif
67
68 /* DATA *********************************************************************/
69
70 /* Number of set bits per byte value */
71 static const
72 UCHAR
73 BitCountTable[256] =
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
97 static __inline
98 BITMAP_INDEX
99 RtlpGetLengthOfRunClear(
100 _In_ PRTL_BITMAP BitMapHeader,
101 _In_ BITMAP_INDEX StartingIndex,
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
151 static __inline
152 BITMAP_INDEX
153 RtlpGetLengthOfRunSet(
154 _In_ PRTL_BITMAP BitMapHeader,
155 _In_ BITMAP_INDEX StartingIndex,
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
209 CCHAR
210 NTAPI
211 RtlFindMostSignificantBit(ULONGLONG Value)
212 {
213 ULONG Position;
214
215 #ifdef _M_AMD64
216 if (BitScanReverse64(&Position, Value))
217 {
218 return (CCHAR)Position;
219 }
220 #else
221 if (BitScanReverse(&Position, Value >> _BITCOUNT))
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
233 CCHAR
234 NTAPI
235 RtlFindLeastSignificantBit(ULONGLONG Value)
236 {
237 ULONG Position;
238
239 #ifdef _M_AMD64
240 if (BitScanForward64(&Position, Value))
241 {
242 return (CCHAR)Position;
243 }
244 #else
245 if (BitScanForward(&Position, (ULONG)Value))
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
258 VOID
259 NTAPI
260 RtlInitializeBitMap(
261 _Out_ PRTL_BITMAP BitMapHeader,
262 _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer,
263 _In_opt_ ULONG SizeOfBitMap)
264 {
265 /* Setup the bitmap header */
266 BitMapHeader->SizeOfBitMap = SizeOfBitMap;
267 BitMapHeader->Buffer = BitMapBuffer;
268 }
269
270 VOID
271 NTAPI
272 RtlClearAllBits(
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
281 VOID
282 NTAPI
283 RtlSetAllBits(
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
292 VOID
293 NTAPI
294 RtlClearBit(
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
302 VOID
303 NTAPI
304 RtlSetBit(
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
312 VOID
313 NTAPI
314 RtlClearBits(
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;
320 PBITMAP_BUFFER Buffer;
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 Mask = MAXINDEX << NumberToClear;
366 *Buffer &= Mask;
367 }
368
369 VOID
370 NTAPI
371 RtlSetBits(
372 _In_ PRTL_BITMAP BitMapHeader,
373 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) BITMAP_INDEX StartingIndex,
374 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) BITMAP_INDEX NumberToSet)
375 {
376 BITMAP_INDEX Bits, Mask;
377 PBITMAP_BUFFER Buffer;
378
379 ASSERT(StartingIndex + NumberToSet <= BitMapHeader->SizeOfBitMap);
380
381 /* Calculate buffer start and first bit index */
382 Buffer = &BitMapHeader->Buffer[StartingIndex / _BITCOUNT];
383 Bits = StartingIndex & (_BITCOUNT - 1);
384
385 /* Are we unaligned? */
386 if (Bits)
387 {
388 /* Create a mask by shifting MAXINDEX */
389 Mask = MAXINDEX << Bits;
390
391 /* This is what's left in the first ULONG */
392 Bits = _BITCOUNT - Bits;
393
394 /* Even less bits to clear? */
395 if (NumberToSet < Bits)
396 {
397 /* Calculate how many bits are left */
398 Bits -= NumberToSet;
399
400 /* Fixup the mask on the high side */
401 Mask = Mask << Bits >> Bits;
402
403 /* Set bits and return */
404 *Buffer |= Mask;
405 return;
406 }
407
408 /* Set bits */
409 *Buffer |= Mask;
410
411 /* Update buffer and left bits */
412 Buffer++;
413 NumberToSet -= Bits;
414 }
415
416 /* Set all full ULONGs */
417 RtlFillMemoryUlong(Buffer, NumberToSet >> 3, MAXINDEX);
418 Buffer += NumberToSet / _BITCOUNT;
419
420 /* Set what's left */
421 NumberToSet &= (_BITCOUNT - 1);
422 Mask = MAXINDEX << NumberToSet;
423 *Buffer |= ~Mask;
424 }
425
426 BOOLEAN
427 NTAPI
428 RtlTestBit(
429 _In_ PRTL_BITMAP BitMapHeader,
430 _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
431 {
432 ASSERT(BitNumber < BitMapHeader->SizeOfBitMap);
433 return (BitMapHeader->Buffer[BitNumber / _BITCOUNT] >> (BitNumber & (_BITCOUNT - 1))) & 1;
434 }
435
436 BOOLEAN
437 NTAPI
438 RtlAreBitsClear(
439 _In_ PRTL_BITMAP BitMapHeader,
440 _In_ BITMAP_INDEX StartingIndex,
441 _In_ BITMAP_INDEX Length)
442 {
443 /* Verify parameters */
444 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
445 (StartingIndex + Length <= StartingIndex))
446 return FALSE;
447
448 return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
449 }
450
451 BOOLEAN
452 NTAPI
453 RtlAreBitsSet(
454 _In_ PRTL_BITMAP BitMapHeader,
455 _In_ BITMAP_INDEX StartingIndex,
456 _In_ BITMAP_INDEX Length)
457 {
458 /* Verify parameters */
459 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
460 (StartingIndex + Length <= StartingIndex))
461 return FALSE;
462
463 return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
464 }
465
466 BITMAP_INDEX
467 NTAPI
468 RtlNumberOfSetBits(
469 _In_ PRTL_BITMAP BitMapHeader)
470 {
471 PUCHAR Byte, MaxByte;
472 BITMAP_INDEX BitCount = 0;
473 ULONG Shift;
474
475 Byte = (PUCHAR)BitMapHeader->Buffer;
476 MaxByte = Byte + BitMapHeader->SizeOfBitMap / 8;
477
478 while (Byte < MaxByte)
479 {
480 BitCount += BitCountTable[*Byte++];
481 }
482
483 if (BitMapHeader->SizeOfBitMap & 7)
484 {
485 Shift = 8 - (BitMapHeader->SizeOfBitMap & 7);
486 BitCount += BitCountTable[((*Byte) << Shift) & 0xFF];
487 }
488
489 return BitCount;
490 }
491
492 BITMAP_INDEX
493 NTAPI
494 RtlNumberOfClearBits(
495 _In_ PRTL_BITMAP BitMapHeader)
496 {
497 /* Do some math */
498 return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
499 }
500
501 BITMAP_INDEX
502 NTAPI
503 RtlFindClearBits(
504 _In_ PRTL_BITMAP BitMapHeader,
505 _In_ BITMAP_INDEX NumberToFind,
506 _In_ BITMAP_INDEX HintIndex)
507 {
508 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
509
510 /* Check for valid parameters */
511 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
512 {
513 return MAXINDEX;
514 }
515
516 /* Check if the hint is outside the bitmap */
517 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
518
519 /* Check for trivial case */
520 if (NumberToFind == 0)
521 {
522 /* Return hint rounded down to byte margin */
523 return HintIndex & ~7;
524 }
525
526 /* First margin is end of bitmap */
527 Margin = BitMapHeader->SizeOfBitMap;
528
529 retry:
530 /* Start with hint index, length is 0 */
531 CurrentBit = HintIndex;
532
533 /* Loop until something is found or the end is reached */
534 while (CurrentBit + NumberToFind < Margin)
535 {
536 /* Search for the next clear run, by skipping a set run */
537 CurrentBit += RtlpGetLengthOfRunSet(BitMapHeader,
538 CurrentBit,
539 MAXINDEX);
540
541 /* Get length of the clear bit run */
542 CurrentLength = RtlpGetLengthOfRunClear(BitMapHeader,
543 CurrentBit,
544 NumberToFind);
545
546 /* Is this long enough? */
547 if (CurrentLength >= NumberToFind)
548 {
549 /* It is */
550 return CurrentBit;
551 }
552
553 CurrentBit += CurrentLength;
554 }
555
556 /* Did we start at a hint? */
557 if (HintIndex)
558 {
559 /* Retry at the start */
560 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
561 HintIndex = 0;
562 goto retry;
563 }
564
565 /* Nothing found */
566 return MAXINDEX;
567 }
568
569 BITMAP_INDEX
570 NTAPI
571 RtlFindSetBits(
572 _In_ PRTL_BITMAP BitMapHeader,
573 _In_ BITMAP_INDEX NumberToFind,
574 _In_ BITMAP_INDEX HintIndex)
575 {
576 BITMAP_INDEX CurrentBit, Margin, CurrentLength;
577
578 /* Check for valid parameters */
579 if (!BitMapHeader || NumberToFind > BitMapHeader->SizeOfBitMap)
580 {
581 return MAXINDEX;
582 }
583
584 /* Check if the hint is outside the bitmap */
585 if (HintIndex >= BitMapHeader->SizeOfBitMap) HintIndex = 0;
586
587 /* Check for trivial case */
588 if (NumberToFind == 0)
589 {
590 /* Return hint rounded down to byte margin */
591 return HintIndex & ~7;
592 }
593
594 /* First margin is end of bitmap */
595 Margin = BitMapHeader->SizeOfBitMap;
596
597 retry:
598 /* Start with hint index, length is 0 */
599 CurrentBit = HintIndex;
600
601 /* Loop until something is found or the end is reached */
602 while (CurrentBit + NumberToFind <= Margin)
603 {
604 /* Search for the next set run, by skipping a clear run */
605 CurrentBit += RtlpGetLengthOfRunClear(BitMapHeader,
606 CurrentBit,
607 MAXINDEX);
608
609 /* Get length of the set bit run */
610 CurrentLength = RtlpGetLengthOfRunSet(BitMapHeader,
611 CurrentBit,
612 NumberToFind);
613
614 /* Is this long enough? */
615 if (CurrentLength >= NumberToFind)
616 {
617 /* It is */
618 return CurrentBit;
619 }
620
621 CurrentBit += CurrentLength;
622 }
623
624 /* Did we start at a hint? */
625 if (HintIndex)
626 {
627 /* Retry at the start */
628 Margin = min(HintIndex + NumberToFind, BitMapHeader->SizeOfBitMap);
629 HintIndex = 0;
630 goto retry;
631 }
632
633 /* Nothing found */
634 return MAXINDEX;
635 }
636
637 BITMAP_INDEX
638 NTAPI
639 RtlFindClearBitsAndSet(
640 _In_ PRTL_BITMAP BitMapHeader,
641 _In_ BITMAP_INDEX NumberToFind,
642 _In_ BITMAP_INDEX HintIndex)
643 {
644 BITMAP_INDEX Position;
645
646 /* Try to find clear bits */
647 Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
648
649 /* Did we get something? */
650 if (Position != MAXINDEX)
651 {
652 /* Yes, set the bits */
653 RtlSetBits(BitMapHeader, Position, NumberToFind);
654 }
655
656 /* Return what we found */
657 return Position;
658 }
659
660 BITMAP_INDEX
661 NTAPI
662 RtlFindSetBitsAndClear(
663 _In_ PRTL_BITMAP BitMapHeader,
664 _In_ BITMAP_INDEX NumberToFind,
665 _In_ BITMAP_INDEX HintIndex)
666 {
667 BITMAP_INDEX Position;
668
669 /* Try to find set bits */
670 Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
671
672 /* Did we get something? */
673 if (Position != MAXINDEX)
674 {
675 /* Yes, clear the bits */
676 RtlClearBits(BitMapHeader, Position, NumberToFind);
677 }
678
679 /* Return what we found */
680 return Position;
681 }
682
683 BITMAP_INDEX
684 NTAPI
685 RtlFindNextForwardRunClear(
686 _In_ PRTL_BITMAP BitMapHeader,
687 _In_ BITMAP_INDEX FromIndex,
688 _Out_ PBITMAP_INDEX StartingRunIndex)
689 {
690 BITMAP_INDEX Length;
691
692 /* Check for buffer overrun */
693 if (FromIndex >= BitMapHeader->SizeOfBitMap)
694 {
695 *StartingRunIndex = FromIndex;
696 return 0;
697 }
698
699 /* Assume a set run first, count it's length */
700 Length = RtlpGetLengthOfRunSet(BitMapHeader, FromIndex, MAXINDEX);
701 *StartingRunIndex = FromIndex + Length;
702
703 /* Now return the length of the run */
704 return RtlpGetLengthOfRunClear(BitMapHeader, FromIndex + Length, MAXINDEX);
705 }
706
707 BITMAP_INDEX
708 NTAPI
709 RtlFindNextForwardRunSet(
710 _In_ PRTL_BITMAP BitMapHeader,
711 _In_ BITMAP_INDEX FromIndex,
712 _Out_ PBITMAP_INDEX StartingRunIndex)
713 {
714 BITMAP_INDEX Length;
715
716 /* Check for buffer overrun */
717 if (FromIndex >= BitMapHeader->SizeOfBitMap)
718 {
719 *StartingRunIndex = FromIndex;
720 return 0;
721 }
722
723 /* Assume a clear run first, count it's length */
724 Length = RtlpGetLengthOfRunClear(BitMapHeader, FromIndex, MAXINDEX);
725 *StartingRunIndex = FromIndex + Length;
726
727 /* Now return the length of the run */
728 return RtlpGetLengthOfRunSet(BitMapHeader, FromIndex + Length, MAXINDEX);
729 }
730
731 BITMAP_INDEX
732 NTAPI
733 RtlFindFirstRunClear(
734 _In_ PRTL_BITMAP BitMapHeader,
735 _Out_ PBITMAP_INDEX StartingIndex)
736 {
737 return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
738 }
739
740 BITMAP_INDEX
741 NTAPI
742 RtlFindLastBackwardRunClear(
743 _In_ PRTL_BITMAP BitMapHeader,
744 _In_ BITMAP_INDEX FromIndex,
745 _Out_ PBITMAP_INDEX StartingRunIndex)
746 {
747 BITMAP_INDEX Value, InvValue, BitPos;
748 PBITMAP_BUFFER Buffer;
749
750 /* Make sure we don't go past the end */
751 FromIndex = min(FromIndex, BitMapHeader->SizeOfBitMap - 1);
752
753 /* Calculate positions */
754 Buffer = BitMapHeader->Buffer + FromIndex / _BITCOUNT;
755 BitPos = (_BITCOUNT - 1) - (FromIndex & (_BITCOUNT - 1));
756
757 /* Get the inversed value, clear bits that don't belong to the run */
758 InvValue = ~(*Buffer--) << BitPos >> BitPos;
759
760 /* Skip all set ULONGs */
761 while (InvValue == 0)
762 {
763 /* Did we already reach past the first ULONG? */
764 if (Buffer < BitMapHeader->Buffer)
765 {
766 /* Yes, nothing found */
767 return 0;
768 }
769
770 InvValue = ~(*Buffer--);
771 }
772
773 /* We hit a clear bit, check how many set bits are left */
774 BitScanReverse(&BitPos, InvValue);
775
776 /* Calculate last bit position */
777 FromIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos);
778
779 Value = ~InvValue << ((_BITCOUNT - 1) - BitPos) >> ((_BITCOUNT - 1) - BitPos);
780
781 /* Skip all clear ULONGs */
782 while (Value == 0 && Buffer >= BitMapHeader->Buffer)
783 {
784 Value = *Buffer--;
785 }
786
787 if (Value != 0)
788 {
789 /* We hit a set bit, check how many clear bits are left */
790 BitScanReverse(&BitPos, Value);
791
792 /* Calculate Starting Index */
793 *StartingRunIndex = (BITMAP_INDEX)((Buffer + 1 - BitMapHeader->Buffer) * _BITCOUNT + BitPos + 1);
794 }
795 else
796 {
797 /* We reached the start of the bitmap */
798 *StartingRunIndex = 0;
799 }
800
801 /* Return length of the run */
802 return (FromIndex - *StartingRunIndex);
803 }
804
805
806 ULONG
807 NTAPI
808 RtlFindClearRuns(
809 _In_ PRTL_BITMAP BitMapHeader,
810 _In_ PRTL_BITMAP_RUN RunArray,
811 _In_ ULONG SizeOfRunArray,
812 _In_ BOOLEAN LocateLongestRuns)
813 {
814 BITMAP_INDEX StartingIndex, NumberOfBits, FromIndex = 0, SmallestRun = 0;
815 ULONG Run;
816
817 /* Loop the runs */
818 for (Run = 0; Run < SizeOfRunArray; Run++)
819 {
820 /* Look for a run */
821 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
822 FromIndex,
823 &StartingIndex);
824
825 /* Nothing more found? Quit looping. */
826 if (NumberOfBits == 0) break;
827
828 /* Add another run */
829 RunArray[Run].StartingIndex = StartingIndex;
830 RunArray[Run].NumberOfBits = NumberOfBits;
831
832 /* Update smallest run */
833 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
834 {
835 SmallestRun = Run;
836 }
837
838 /* Advance bits */
839 FromIndex = StartingIndex + NumberOfBits;
840 }
841
842 /* Check if we are finished */
843 if (Run < SizeOfRunArray || !LocateLongestRuns)
844 {
845 /* Return the number of found runs */
846 return Run;
847 }
848
849 while (1)
850 {
851 /* Look for a run */
852 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
853 FromIndex,
854 &StartingIndex);
855
856 /* Nothing more found? Quit looping. */
857 if (NumberOfBits == 0) break;
858
859 /* Check if we have something to update */
860 if (NumberOfBits > RunArray[SmallestRun].NumberOfBits)
861 {
862 /* Update smallest run */
863 RunArray[SmallestRun].StartingIndex = StartingIndex;
864 RunArray[SmallestRun].NumberOfBits = NumberOfBits;
865
866 /* Loop all runs */
867 for (Run = 0; Run < SizeOfRunArray; Run++)
868 {
869 /*Is this the new smallest run? */
870 if (NumberOfBits < RunArray[SmallestRun].NumberOfBits)
871 {
872 /* Set it as new smallest run */
873 SmallestRun = Run;
874 }
875 }
876 }
877
878 /* Advance bits */
879 FromIndex += NumberOfBits;
880 }
881
882 return Run;
883 }
884
885 BITMAP_INDEX
886 NTAPI
887 RtlFindLongestRunClear(
888 IN PRTL_BITMAP BitMapHeader,
889 IN PBITMAP_INDEX StartingIndex)
890 {
891 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
892
893 while (1)
894 {
895 /* Look for a run */
896 NumberOfBits = RtlFindNextForwardRunClear(BitMapHeader,
897 FromIndex,
898 &Index);
899
900 /* Nothing more found? Quit looping. */
901 if (NumberOfBits == 0) break;
902
903 /* Was that the longest run? */
904 if (NumberOfBits > MaxNumberOfBits)
905 {
906 /* Update values */
907 MaxNumberOfBits = NumberOfBits;
908 *StartingIndex = Index;
909 }
910
911 /* Advance bits */
912 FromIndex += NumberOfBits;
913 }
914
915 return MaxNumberOfBits;
916 }
917
918 BITMAP_INDEX
919 NTAPI
920 RtlFindLongestRunSet(
921 IN PRTL_BITMAP BitMapHeader,
922 IN PBITMAP_INDEX StartingIndex)
923 {
924 BITMAP_INDEX NumberOfBits, Index, MaxNumberOfBits = 0, FromIndex = 0;
925
926 while (1)
927 {
928 /* Look for a run */
929 NumberOfBits = RtlFindNextForwardRunSet(BitMapHeader,
930 FromIndex,
931 &Index);
932
933 /* Nothing more found? Quit looping. */
934 if (NumberOfBits == 0) break;
935
936 /* Was that the longest run? */
937 if (NumberOfBits > MaxNumberOfBits)
938 {
939 /* Update values */
940 MaxNumberOfBits = NumberOfBits;
941 *StartingIndex = Index;
942 }
943
944 /* Advance bits */
945 FromIndex += NumberOfBits;
946 }
947
948 return MaxNumberOfBits;
949 }
950