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
RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX StartingIndex,_In_ BITMAP_INDEX MaxLength)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
RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX StartingIndex,_In_ BITMAP_INDEX MaxLength)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
RtlFindMostSignificantBit(ULONGLONG Value)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
RtlFindLeastSignificantBit(ULONGLONG Value)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
RtlInitializeBitMap(_Out_ PRTL_BITMAP BitMapHeader,_In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer,_In_opt_ ULONG SizeOfBitMap)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
RtlClearAllBits(_In_ PRTL_BITMAP BitMapHeader)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
RtlSetAllBits(_In_ PRTL_BITMAP BitMapHeader)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
RtlClearBit(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX BitNumber)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 if (NumberToClear != 0)
366 {
367 Mask = MAXINDEX << NumberToClear;
368 *Buffer &= Mask;
369 }
370 }
371
372 VOID
373 NTAPI
374 RtlSetBits(
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;
380 PBITMAP_BUFFER Buffer;
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
432 BOOLEAN
433 NTAPI
434 RtlTestBit(
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
442 BOOLEAN
443 NTAPI
RtlAreBitsClear(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX StartingIndex,_In_ BITMAP_INDEX Length)444 RtlAreBitsClear(
445 _In_ PRTL_BITMAP BitMapHeader,
446 _In_ BITMAP_INDEX StartingIndex,
447 _In_ BITMAP_INDEX Length)
448 {
449 /* Verify parameters */
450 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
451 (StartingIndex + Length <= StartingIndex))
452 return FALSE;
453
454 return RtlpGetLengthOfRunClear(BitMapHeader, StartingIndex, Length) >= Length;
455 }
456
457 BOOLEAN
458 NTAPI
RtlAreBitsSet(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX StartingIndex,_In_ BITMAP_INDEX Length)459 RtlAreBitsSet(
460 _In_ PRTL_BITMAP BitMapHeader,
461 _In_ BITMAP_INDEX StartingIndex,
462 _In_ BITMAP_INDEX Length)
463 {
464 /* Verify parameters */
465 if ((StartingIndex + Length > BitMapHeader->SizeOfBitMap) ||
466 (StartingIndex + Length <= StartingIndex))
467 return FALSE;
468
469 return RtlpGetLengthOfRunSet(BitMapHeader, StartingIndex, Length) >= Length;
470 }
471
472 BITMAP_INDEX
473 NTAPI
RtlNumberOfSetBits(_In_ PRTL_BITMAP BitMapHeader)474 RtlNumberOfSetBits(
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
498 BITMAP_INDEX
499 NTAPI
RtlNumberOfClearBits(_In_ PRTL_BITMAP BitMapHeader)500 RtlNumberOfClearBits(
501 _In_ PRTL_BITMAP BitMapHeader)
502 {
503 /* Do some math */
504 return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
505 }
506
507 BITMAP_INDEX
508 NTAPI
RtlFindClearBits(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX NumberToFind,_In_ BITMAP_INDEX HintIndex)509 RtlFindClearBits(
510 _In_ PRTL_BITMAP BitMapHeader,
511 _In_ BITMAP_INDEX NumberToFind,
512 _In_ BITMAP_INDEX HintIndex)
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
535 retry:
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,
550 NumberToFind);
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
575 BITMAP_INDEX
576 NTAPI
RtlFindSetBits(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX NumberToFind,_In_ BITMAP_INDEX HintIndex)577 RtlFindSetBits(
578 _In_ PRTL_BITMAP BitMapHeader,
579 _In_ BITMAP_INDEX NumberToFind,
580 _In_ BITMAP_INDEX HintIndex)
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
603 retry:
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,
618 NumberToFind);
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
643 BITMAP_INDEX
644 NTAPI
RtlFindClearBitsAndSet(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX NumberToFind,_In_ BITMAP_INDEX HintIndex)645 RtlFindClearBitsAndSet(
646 _In_ PRTL_BITMAP BitMapHeader,
647 _In_ BITMAP_INDEX NumberToFind,
648 _In_ BITMAP_INDEX HintIndex)
649 {
650 BITMAP_INDEX Position;
651
652 /* Try to find clear bits */
653 Position = RtlFindClearBits(BitMapHeader, NumberToFind, HintIndex);
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
666 BITMAP_INDEX
667 NTAPI
RtlFindSetBitsAndClear(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX NumberToFind,_In_ BITMAP_INDEX HintIndex)668 RtlFindSetBitsAndClear(
669 _In_ PRTL_BITMAP BitMapHeader,
670 _In_ BITMAP_INDEX NumberToFind,
671 _In_ BITMAP_INDEX HintIndex)
672 {
673 BITMAP_INDEX Position;
674
675 /* Try to find set bits */
676 Position = RtlFindSetBits(BitMapHeader, NumberToFind, HintIndex);
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
689 BITMAP_INDEX
690 NTAPI
RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX FromIndex,_Out_ PBITMAP_INDEX StartingRunIndex)691 RtlFindNextForwardRunClear(
692 _In_ PRTL_BITMAP BitMapHeader,
693 _In_ BITMAP_INDEX FromIndex,
694 _Out_ PBITMAP_INDEX StartingRunIndex)
695 {
696 BITMAP_INDEX Length;
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
713 BITMAP_INDEX
714 NTAPI
RtlFindNextForwardRunSet(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX FromIndex,_Out_ PBITMAP_INDEX StartingRunIndex)715 RtlFindNextForwardRunSet(
716 _In_ PRTL_BITMAP BitMapHeader,
717 _In_ BITMAP_INDEX FromIndex,
718 _Out_ PBITMAP_INDEX StartingRunIndex)
719 {
720 BITMAP_INDEX Length;
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
737 BITMAP_INDEX
738 NTAPI
RtlFindFirstRunClear(_In_ PRTL_BITMAP BitMapHeader,_Out_ PBITMAP_INDEX StartingIndex)739 RtlFindFirstRunClear(
740 _In_ PRTL_BITMAP BitMapHeader,
741 _Out_ PBITMAP_INDEX StartingIndex)
742 {
743 return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
744 }
745
746 BITMAP_INDEX
747 NTAPI
RtlFindLastBackwardRunClear(_In_ PRTL_BITMAP BitMapHeader,_In_ BITMAP_INDEX FromIndex,_Out_ PBITMAP_INDEX StartingRunIndex)748 RtlFindLastBackwardRunClear(
749 _In_ PRTL_BITMAP BitMapHeader,
750 _In_ BITMAP_INDEX FromIndex,
751 _Out_ PBITMAP_INDEX StartingRunIndex)
752 {
753 BITMAP_INDEX Value, InvValue, BitPos;
754 PBITMAP_BUFFER Buffer;
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
812 ULONG
813 NTAPI
RtlFindClearRuns(_In_ PRTL_BITMAP BitMapHeader,_In_ PRTL_BITMAP_RUN RunArray,_In_ ULONG SizeOfRunArray,_In_ BOOLEAN LocateLongestRuns)814 RtlFindClearRuns(
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,
829 &StartingIndex);
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,
860 &StartingIndex);
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
891 BITMAP_INDEX
892 NTAPI
RtlFindLongestRunClear(IN PRTL_BITMAP BitMapHeader,IN PBITMAP_INDEX StartingIndex)893 RtlFindLongestRunClear(
894 IN PRTL_BITMAP BitMapHeader,
895 IN PBITMAP_INDEX StartingIndex)
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;
914 *StartingIndex = Index;
915 }
916
917 /* Advance bits */
918 FromIndex += NumberOfBits;
919 }
920
921 return MaxNumberOfBits;
922 }
923
924 BITMAP_INDEX
925 NTAPI
RtlFindLongestRunSet(IN PRTL_BITMAP BitMapHeader,IN PBITMAP_INDEX StartingIndex)926 RtlFindLongestRunSet(
927 IN PRTL_BITMAP BitMapHeader,
928 IN PBITMAP_INDEX StartingIndex)
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;
947 *StartingIndex = Index;
948 }
949
950 /* Advance bits */
951 FromIndex += NumberOfBits;
952 }
953
954 return MaxNumberOfBits;
955 }
956
957