ReactOS  0.4.14-dev-41-g31d7680
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 */
71 static const
72 UCHAR
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
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 
151 static __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
209 CCHAR
210 NTAPI
212 {
213  ULONG Position;
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 
233 CCHAR
234 NTAPI
236 {
237  ULONG Position;
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 
258 VOID
259 NTAPI
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 
270 VOID
271 NTAPI
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
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
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
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
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 
372 VOID
373 NTAPI
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 
432 BOOLEAN
433 NTAPI
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
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 
457 BOOLEAN
458 NTAPI
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 
473 NTAPI
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 
499 NTAPI
501  _In_ PRTL_BITMAP BitMapHeader)
502 {
503  /* Do some math */
504  return BitMapHeader->SizeOfBitMap - RtlNumberOfSetBits(BitMapHeader);
505 }
506 
508 NTAPI
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 
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 
576 NTAPI
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 
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 
644 NTAPI
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 
667 NTAPI
669  _In_ PRTL_BITMAP BitMapHeader,
672 {
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 
690 NTAPI
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 
714 NTAPI
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 
738 NTAPI
740  _In_ PRTL_BITMAP BitMapHeader,
742 {
743  return RtlFindNextForwardRunClear(BitMapHeader, 0, StartingIndex);
744 }
745 
747 NTAPI
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? */
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
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 
892 NTAPI
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;
914  *StartingIndex = Index;
915  }
916 
917  /* Advance bits */
918  FromIndex += NumberOfBits;
919  }
920 
921  return MaxNumberOfBits;
922 }
923 
925 NTAPI
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;
947  *StartingIndex = Index;
948  }
949 
950  /* Advance bits */
951  FromIndex += NumberOfBits;
952  }
953 
954  return MaxNumberOfBits;
955 }
956 
_In_opt_ ULONG _Out_ PULONG Value
Definition: rtlfuncs.h:2343
BITMAP_INDEX NTAPI RtlFindFirstRunClear(_In_ PRTL_BITMAP BitMapHeader, _Out_ PBITMAP_INDEX StartingIndex)
Definition: bitmap.c:739
BOOLEAN NTAPI RtlAreBitsSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
Definition: bitmap.c:459
Definition: bidi.c:477
ULONG * PBITMAP_INDEX
Definition: bitmap.c:64
#define IN
Definition: typedefs.h:38
#define BitScanForward
Definition: interlocked.h:5
unsigned char Byte
Definition: zconf.h:391
VOID NTAPI RtlSetAllBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:283
static COORD Position
Definition: mouse.c:34
unsigned char * PUCHAR
Definition: retypes.h:3
BITMAP_INDEX NTAPI RtlFindClearBits(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:509
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 RtlFindNextForwardRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:715
#define _In_opt_
Definition: no_sal2.h:213
_In_ ULONG _In_ ULONG HintIndex
Definition: rtlfuncs.h:609
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
while(1)
Definition: macro.lex.yy.c:740
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
_In_ ULONG NumberToFind
Definition: rtlfuncs.h:609
static TRIVERTEX ULONG
Definition: bitmap.c:45
BOOLEAN NTAPI RtlAreBitsClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX Length)
Definition: bitmap.c:444
ULONG NTAPI RtlFindClearRuns(_In_ PRTL_BITMAP BitMapHeader, _In_ PRTL_BITMAP_RUN RunArray, _In_ ULONG SizeOfRunArray, _In_ BOOLEAN LocateLongestRuns)
Definition: bitmap.c:814
static __inline BITMAP_INDEX RtlpGetLengthOfRunSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:153
#define __drv_aliasesMem
Definition: btrfs_drv.h:183
BITMAP_INDEX NTAPI RtlFindLastBackwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:748
unsigned char BOOLEAN
#define _Out_
Definition: no_sal2.h:323
struct tagRun Run
Definition: bufpool.h:45
#define RtlFillMemoryUlong(dst, len, val)
Definition: mkhive.h:55
CCHAR NTAPI RtlFindLeastSignificantBit(ULONGLONG Value)
Definition: bitmap.c:235
#define ASSERT(...)
Definition: bitmap.c:19
char CCHAR
Definition: typedefs.h:50
BITMAP_INDEX NTAPI RtlNumberOfClearBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:500
uint64_t ULONGLONG
Definition: typedefs.h:65
#define MAXINDEX
Definition: bitmap.c:63
static const UCHAR Index[8]
Definition: usbohci.c:18
VOID NTAPI RtlClearBit(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX BitNumber)
Definition: bitmap.c:294
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:101
VOID NTAPI RtlInitializeBitMap(_Out_ PRTL_BITMAP BitMapHeader, _In_opt_ __drv_aliasesMem PBITMAP_BUFFER BitMapBuffer, _In_opt_ ULONG SizeOfBitMap)
Definition: bitmap.c:260
unsigned __int64 ULONG64
Definition: imports.h:198
unsigned char UCHAR
Definition: xmlstorage.h:181
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
CCHAR NTAPI RtlFindMostSignificantBit(ULONGLONG Value)
Definition: bitmap.c:211
#define BitScanReverse
Definition: interlocked.h:6
BITMAP_INDEX NTAPI RtlFindClearBitsAndSet(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:645
BOOLEAN NTAPI RtlTestBit(_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
Definition: bitmap.c:434
ULONG BITMAP_BUFFER
Definition: bitmap.c:65
ULONG BITMAP_INDEX
Definition: bitmap.c:64
_In_ ULONG StartingIndex
Definition: rtlfuncs.h:395
VOID NTAPI RtlClearAllBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:272
BITMAP_INDEX NTAPI RtlFindSetBitsAndClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX NumberToFind, _In_ BITMAP_INDEX HintIndex)
Definition: bitmap.c:668
#define _In_
Definition: no_sal2.h:204
ULONG * PBITMAP_BUFFER
Definition: bitmap.c:65
_In_ ULONG Shift
Definition: rtlfuncs.h:2683
#define min(a, b)
Definition: monoChain.cc:55
VOID NTAPI RtlSetBit(_In_ PRTL_BITMAP BitMapHeader, _In_range_(<, BitMapHeader->SizeOfBitMap) BITMAP_INDEX BitNumber)
Definition: bitmap.c:304
BITMAP_INDEX NTAPI RtlNumberOfSetBits(_In_ PRTL_BITMAP BitMapHeader)
Definition: bitmap.c:474
static __inline BITMAP_INDEX RtlpGetLengthOfRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX StartingIndex, _In_ BITMAP_INDEX MaxLength)
Definition: bitmap.c:99
BITMAP_INDEX NTAPI RtlFindLongestRunSet(IN PRTL_BITMAP BitMapHeader, IN PBITMAP_INDEX StartingIndex)
Definition: bitmap.c:926
unsigned int ULONG
Definition: retypes.h:1
#define _BITCOUNT
Definition: bitmap.c:62
static const UCHAR BitCountTable[256]
Definition: bitmap.c:73
#define _In_range_(lb, ub)
Definition: no_sal2.h:227
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34
BITMAP_INDEX NTAPI RtlFindNextForwardRunClear(_In_ PRTL_BITMAP BitMapHeader, _In_ BITMAP_INDEX FromIndex, _Out_ PBITMAP_INDEX StartingRunIndex)
Definition: bitmap.c:691