include the right files
[reactos.git] / reactos / lib / ntdll / rtl / bitmap.c
1 /* $Id: bitmap.c,v 1.7 2004/02/02 13:34:01 ekohl Exp $
2 *
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: lib/ntdll/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
7 * UPDATE HISTORY:
8 * 20/08/99 Created by Eric Kohl
9 */
10
11 #include <ddk/ntddk.h>
12
13
14 #define NDEBUG
15 #include <ntdll/ntdll.h>
16
17 #define ALIGN(x,align) (((x)+(align)-1) / (align))
18
19
20 /* FUNCTIONS *****************************************************************/
21
22 /*
23 * @implemented
24 */
25 VOID
26 STDCALL
27 RtlInitializeBitMap (
28 PRTL_BITMAP BitMapHeader,
29 PULONG BitMapBuffer,
30 ULONG SizeOfBitMap
31 )
32 {
33 BitMapHeader->SizeOfBitMap = SizeOfBitMap;
34 BitMapHeader->Buffer = BitMapBuffer;
35 }
36
37
38 /*
39 * @implemented
40 */
41 BOOLEAN
42 STDCALL
43 RtlAreBitsClear (
44 PRTL_BITMAP BitMapHeader,
45 ULONG StartingIndex,
46 ULONG Length
47 )
48 {
49 ULONG Size = BitMapHeader->SizeOfBitMap;
50 ULONG Shift;
51 ULONG Count;
52 PUCHAR Ptr;
53
54 if (StartingIndex >= Size ||
55 !Length ||
56 (StartingIndex + Length > Size))
57 return FALSE;
58
59 Ptr = (PUCHAR)BitMapHeader->Buffer + (StartingIndex / 8);
60 while (Length)
61 {
62 /* get bit shift in current byte */
63 Shift = StartingIndex & 7;
64
65 /* get number of bits to check in current byte */
66 Count = (Length > 8 - Shift) ? 8 - Shift : Length;
67
68 /* check byte */
69 if (*Ptr & (~(0xFF << Count) << Shift))
70 return FALSE;
71
72 Ptr++;
73 Length -= Count;
74 StartingIndex += Count;
75 }
76
77 return TRUE;
78 }
79
80
81 /*
82 * @implemented
83 */
84 BOOLEAN
85 STDCALL
86 RtlAreBitsSet (
87 PRTL_BITMAP BitMapHeader,
88 ULONG StartingIndex,
89 ULONG Length
90 )
91 {
92 ULONG Size = BitMapHeader->SizeOfBitMap;
93 ULONG Shift;
94 ULONG Count;
95 PUCHAR Ptr;
96 UCHAR Check;
97
98 if (StartingIndex >= Size ||
99 !Length ||
100 (StartingIndex + Length > Size))
101 return FALSE;
102
103 Ptr = (PUCHAR)BitMapHeader->Buffer + (StartingIndex / 8);
104 while (Length)
105 {
106 /* get bit shift in current byte */
107 Shift = StartingIndex & 7;
108
109 /* get number of bits to check in current byte */
110 Count = (Length > 8 - Shift) ? 8 - Shift : Length;
111
112 /* bulid check byte */
113 Check = ~(0xFF << Count) << Shift;
114
115 /* check byte */
116 if ((*Ptr & Check) != Check)
117 return FALSE;
118
119 Ptr++;
120 Length -= Count;
121 StartingIndex += Count;
122 }
123
124 return TRUE;
125 }
126
127
128 /*
129 * @implemented
130 */
131 VOID
132 STDCALL
133 RtlClearAllBits (
134 IN OUT PRTL_BITMAP BitMapHeader
135 )
136 {
137 memset (BitMapHeader->Buffer,
138 0x00,
139 ALIGN(BitMapHeader->SizeOfBitMap, 8));
140 }
141
142
143 /*
144 * @implemented
145 */
146 VOID
147 STDCALL
148 RtlClearBits (
149 PRTL_BITMAP BitMapHeader,
150 ULONG StartingIndex,
151 ULONG NumberToClear
152 )
153 {
154 ULONG Size = BitMapHeader->SizeOfBitMap;
155 ULONG Count;
156 ULONG Shift;
157 PCHAR Ptr;
158
159 if (StartingIndex >= Size || NumberToClear == 0)
160 return;
161
162 if (StartingIndex + NumberToClear > Size)
163 NumberToClear = Size - StartingIndex;
164
165 Ptr = (PCHAR)(BitMapHeader->Buffer + (StartingIndex / 8));
166 while (NumberToClear)
167 {
168 /* bit shift in current byte */
169 Shift = StartingIndex & 7;
170
171 /* number of bits to change in current byte */
172 Count = (NumberToClear > 8 - Shift ) ? 8 - Shift : NumberToClear;
173
174 /* adjust byte */
175 *Ptr &= ~(~(0xFF << Count) << Shift);
176
177 Ptr++;
178 NumberToClear -= Count;
179 StartingIndex += Count;
180 }
181 }
182
183
184 /*
185 * @implemented
186 */
187 ULONG
188 STDCALL
189 RtlFindClearBits (
190 PRTL_BITMAP BitMapHeader,
191 ULONG NumberToFind,
192 ULONG HintIndex
193 )
194 {
195 ULONG Size = BitMapHeader->SizeOfBitMap;
196 ULONG Index;
197 ULONG Count;
198 PCHAR Ptr;
199 CHAR Mask;
200
201 if (NumberToFind > Size || NumberToFind == 0)
202 return -1;
203
204 if (HintIndex >= Size)
205 HintIndex = 0;
206
207 Index = HintIndex;
208 Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
209 Mask = 1 << (Index & 7);
210
211 while (HintIndex < Size)
212 {
213 /* count clear bits */
214 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
215 {
216 if (++Count >= NumberToFind)
217 return HintIndex;
218 Mask <<= 1;
219 if (Mask == 0)
220 {
221 Mask = 1;
222 Ptr++;
223 }
224 }
225
226 /* skip set bits */
227 for (; Index < Size && *Ptr & Mask; Index++)
228 {
229 Mask <<= 1;
230 if (Mask == 0)
231 {
232 Mask = 1;
233 Ptr++;
234 }
235 }
236 HintIndex = Index;
237 }
238
239 return -1;
240 }
241
242
243 /*
244 * @implemented
245 */
246 ULONG
247 STDCALL
248 RtlFindClearBitsAndSet (
249 PRTL_BITMAP BitMapHeader,
250 ULONG NumberToFind,
251 ULONG HintIndex
252 )
253 {
254 ULONG Index;
255
256 Index = RtlFindClearBits (BitMapHeader,
257 NumberToFind,
258 HintIndex);
259 if (Index != (ULONG)-1)
260 RtlSetBits (BitMapHeader,
261 Index,
262 NumberToFind);
263
264 return Index;
265 }
266
267
268 /*
269 * @unimplemented
270 */
271 ULONG STDCALL
272 RtlFindClearRuns (PRTL_BITMAP BitMapHeader,
273 PRTL_BITMAP_RUN RunArray,
274 ULONG SizeOfRunArray,
275 BOOLEAN LocateLongestRuns)
276 {
277 return (ULONG)-1;
278 }
279
280
281 ULONG
282 STDCALL
283 RtlFindFirstRunClear (
284 PRTL_BITMAP BitMapHeader,
285 PULONG StartingIndex
286 )
287 {
288 ULONG Size = BitMapHeader->SizeOfBitMap;
289 ULONG Index;
290 ULONG Count;
291 PCHAR Ptr;
292 CHAR Mask;
293
294 if (*StartingIndex > Size)
295 {
296 *StartingIndex = (ULONG)-1;
297 return 0;
298 }
299
300 Index = *StartingIndex;
301 Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
302 Mask = 1 << (Index & 7);
303
304 /* skip set bits */
305 for (; Index < Size && *Ptr & Mask; Index++)
306 {
307 Mask <<= 1;
308 if (Mask == 0)
309 {
310 Mask = 1;
311 Ptr++;
312 }
313 }
314
315 /* return index of first clear bit */
316 if (Index >= Size)
317 {
318 *StartingIndex = (ULONG)-1;
319 return 0;
320 }
321 else
322 *StartingIndex = Index;
323
324 /* count clear bits */
325 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
326 {
327 Count++;
328 Mask <<= 1;
329 if (Mask == 0)
330 {
331 Mask = 1;
332 Ptr++;
333 }
334 }
335
336 return Count;
337 }
338
339
340 ULONG
341 STDCALL
342 RtlFindFirstRunSet (
343 PRTL_BITMAP BitMapHeader,
344 PULONG StartingIndex
345 )
346 {
347 ULONG Size = BitMapHeader->SizeOfBitMap;
348 ULONG Index;
349 ULONG Count;
350 PCHAR Ptr;
351 CHAR Mask;
352
353 if (*StartingIndex > Size)
354 {
355 *StartingIndex = (ULONG)-1;
356 return 0;
357 }
358
359 Index = *StartingIndex;
360 Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
361 Mask = 1 << (Index & 7);
362
363 /* skip clear bits */
364 for (; Index < Size && ~*Ptr & Mask; Index++)
365 {
366 Mask <<= 1;
367 if (Mask == 0)
368 {
369 Mask = 1;
370 Ptr++;
371 }
372 }
373
374 /* return index of first set bit */
375 if (Index >= Size)
376 {
377 *StartingIndex = (ULONG)-1;
378 return 0;
379 }
380 else
381 *StartingIndex = Index;
382
383 /* count set bits */
384 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
385 {
386 Count++;
387 Mask <<= 1;
388 if (Mask == 0)
389 {
390 Mask = 1;
391 Ptr++;
392 }
393 }
394
395 return Count;
396 }
397
398
399 /*
400 * @unimplemented
401 */
402 ULONG STDCALL
403 RtlFindLastBackwardRunClear (IN PRTL_BITMAP BitMapHeader,
404 IN ULONG FromIndex,
405 IN PULONG StartingRunIndex)
406 {
407 return (ULONG)-1;
408 }
409
410
411 /*
412 * @implemented
413 */
414 ULONG
415 STDCALL
416 RtlFindLongestRunClear (
417 PRTL_BITMAP BitMapHeader,
418 PULONG StartingIndex
419 )
420 {
421 ULONG Size = BitMapHeader->SizeOfBitMap;
422 PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
423 ULONG Index = 0;
424 ULONG Count;
425 ULONG Max = 0;
426 ULONG Start;
427 ULONG Maxstart = 0;
428 CHAR Mask = 1;
429
430 while (Index < Size)
431 {
432 Start = Index;
433
434 /* count clear bits */
435 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
436 {
437 Count++;
438 Mask <<= 1;
439 if (Mask == 0)
440 {
441 Mask = 1;
442 Ptr++;
443 }
444 }
445
446 /* skip set bits */
447 for (; Index < Size && *Ptr & Mask; Index++)
448 {
449 Mask <<= 1;
450 if (Mask == 0)
451 {
452 Mask = 1;
453 Ptr++;
454 }
455 }
456
457 if (Count > Max)
458 {
459 Max = Count;
460 Maxstart = Start;
461 }
462 }
463
464 if (StartingIndex)
465 *StartingIndex = Maxstart;
466
467 return Max;
468 }
469
470
471 /*
472 * @implemented
473 */
474 ULONG
475 STDCALL
476 RtlFindLongestRunSet (
477 PRTL_BITMAP BitMapHeader,
478 PULONG StartingIndex
479 )
480 {
481 ULONG Size = BitMapHeader->SizeOfBitMap;
482 PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
483 ULONG Index = 0;
484 ULONG Count;
485 ULONG Max = 0;
486 ULONG Start;
487 ULONG Maxstart = 0;
488 CHAR Mask = 1;
489
490 while (Index < Size)
491 {
492 Start = Index;
493
494 /* count set bits */
495 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
496 {
497 Count++;
498 Mask <<= 1;
499 if (Mask == 0)
500 {
501 Mask = 1;
502 Ptr++;
503 }
504 }
505
506 /* skip clear bits */
507 for (; Index < Size && ~*Ptr & Mask; Index++)
508 {
509 Mask <<= 1;
510 if (Mask == 0)
511 {
512 Mask = 1;
513 Ptr++;
514 }
515 }
516
517 if (Count > Max)
518 {
519 Max = Count;
520 Maxstart = Start;
521 }
522 }
523
524 if (StartingIndex)
525 *StartingIndex = Maxstart;
526
527 return Max;
528 }
529
530
531 /*
532 * @unimplemented
533 */
534 ULONG STDCALL
535 RtlFindNextForwardRunClear (IN PRTL_BITMAP BitMapHeader,
536 IN ULONG FromIndex,
537 IN PULONG StartingRunIndex)
538 {
539 return (ULONG)-1;
540 }
541
542
543 /*
544 * @implemented
545 */
546 ULONG
547 STDCALL
548 RtlFindSetBits (
549 PRTL_BITMAP BitMapHeader,
550 ULONG NumberToFind,
551 ULONG HintIndex
552 )
553 {
554 ULONG Size = BitMapHeader->SizeOfBitMap;
555 ULONG Index;
556 ULONG Count;
557 PCHAR Ptr;
558 CHAR Mask;
559
560 if (NumberToFind > Size || NumberToFind == 0)
561 return (ULONG)-1;
562
563 if (HintIndex >= Size)
564 HintIndex = 0;
565
566 Index = HintIndex;
567 Ptr = (PCHAR)BitMapHeader->Buffer + (Index / 8);
568 Mask = 1 << (Index & 7);
569
570 while (HintIndex < Size)
571 {
572 /* count set bits */
573 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
574 {
575 if (++Count >= NumberToFind)
576 return HintIndex;
577 Mask <<= 1;
578 if (Mask == 0)
579 {
580 Mask = 1;
581 Ptr++;
582 }
583 }
584
585 /* skip clear bits */
586 for (; Index < Size && ~*Ptr & Mask; Index++)
587 {
588 Mask <<= 1;
589 if (Mask == 0)
590 {
591 Mask = 1;
592 Ptr++;
593 }
594 }
595 HintIndex = Index;
596 }
597
598 return (ULONG)-1;
599 }
600
601
602 /*
603 * @implemented
604 */
605 ULONG
606 STDCALL
607 RtlFindSetBitsAndClear (
608 PRTL_BITMAP BitMapHeader,
609 ULONG NumberToFind,
610 ULONG HintIndex
611 )
612 {
613 ULONG Index;
614
615 Index = RtlFindSetBits (BitMapHeader,
616 NumberToFind,
617 HintIndex);
618 if (Index != (ULONG)-1)
619 RtlClearBits (BitMapHeader,
620 Index,
621 NumberToFind);
622
623 return Index;
624 }
625
626
627 /*
628 * @implemented
629 */
630 ULONG
631 STDCALL
632 RtlNumberOfClearBits (
633 PRTL_BITMAP BitMapHeader
634 )
635 {
636 PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
637 ULONG Size = BitMapHeader->SizeOfBitMap;
638 ULONG Index;
639 ULONG Count;
640 CHAR Mask;
641
642 for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
643 {
644 if (~*Ptr & Mask)
645 Count++;
646
647 Mask <<= 1;
648 if (Mask == 0)
649 {
650 Mask = 1;
651 Ptr++;
652 }
653 }
654
655 return Count;
656 }
657
658
659 /*
660 * @implemented
661 */
662 ULONG
663 STDCALL
664 RtlNumberOfSetBits (
665 PRTL_BITMAP BitMapHeader
666 )
667 {
668 PCHAR Ptr = (PCHAR)BitMapHeader->Buffer;
669 ULONG Size = BitMapHeader->SizeOfBitMap;
670 ULONG Index;
671 ULONG Count;
672 CHAR Mask;
673
674 for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
675 {
676 if (*Ptr & Mask)
677 Count++;
678
679 Mask <<= 1;
680 if (Mask == 0)
681 {
682 Mask = 1;
683 Ptr++;
684 }
685 }
686
687 return Count;
688 }
689
690
691 /*
692 * @implemented
693 */
694 VOID
695 STDCALL
696 RtlSetAllBits (
697 IN OUT PRTL_BITMAP BitMapHeader
698 )
699 {
700 memset (BitMapHeader->Buffer,
701 0xFF,
702 ALIGN(BitMapHeader->SizeOfBitMap, 8));
703 }
704
705
706 /*
707 * @implemented
708 */
709 VOID
710 STDCALL
711 RtlSetBits (
712 PRTL_BITMAP BitMapHeader,
713 ULONG StartingIndex,
714 ULONG NumberToSet
715 )
716 {
717 ULONG Size = BitMapHeader->SizeOfBitMap;
718 ULONG Count;
719 ULONG Shift;
720 PCHAR Ptr;
721
722 if (StartingIndex >= Size || NumberToSet == 0)
723 return;
724
725 if (StartingIndex + NumberToSet > Size)
726 NumberToSet = Size - StartingIndex;
727
728 Ptr = (PCHAR)BitMapHeader->Buffer + (StartingIndex / 8);
729 while (NumberToSet)
730 {
731 /* bit shift in current byte */
732 Shift = StartingIndex & 7;
733
734 /* number of bits to change in current byte */
735 Count = (NumberToSet > 8 - Shift) ? 8 - Shift : NumberToSet;
736
737 /* adjust byte */
738 *Ptr |= ~(0xFF << Count) << Shift;
739
740 Ptr++;
741 NumberToSet -= Count;
742 StartingIndex += Count;
743 }
744 }
745
746
747 /*
748 * @implemented
749 */
750 CCHAR STDCALL
751 RtlFindLeastSignificantBit (IN ULONGLONG Set)
752 {
753 int i;
754
755 if (Set == 0ULL)
756 return -1;
757
758 for (i = 0; i < 64; i++)
759 {
760 if (Set & (1 << i))
761 return (CCHAR)i;
762 }
763
764 return -1;
765 }
766
767
768 /*
769 * @implemented
770 */
771 CCHAR STDCALL
772 RtlFindMostSignificantBit (IN ULONGLONG Set)
773 {
774 int i;
775
776 if (Set == 0ULL)
777 return -1;
778
779 for (i = 63; i >= 0; i--)
780 {
781 if (Set & (1 << i))
782 return (CCHAR)i;
783 }
784
785 return -1;
786 }
787
788 /* EOF */