1 /*
2 * PROJECT: ReactOS SDK
3 * LICENSE: MIT (https://spdx.org/licenses/MIT)
4 * PURPOSE: Helper functions to debug RTL_BITMAP
5 * COPYRIGHT: Copyright 2024 Timo Kreuzer <timo.kreuzer@reactos.org>
6 */
7
8 #pragma once
9
10 #include <ndk/rtlfuncs.h>
11
12 typedef struct _RTL_BITMAP_DBG
13 {
14 union
15 {
16 struct
17 {
18 ULONG SizeOfBitMap;
19 PULONG Buffer;
20 };
21 RTL_BITMAP BitMap;
22 };
23 ULONG NumberOfSetBits;
24 ULONG BitmapHash;
25 } RTL_BITMAP_DBG, *PRTL_BITMAP_DBG;
26
27 static inline
fnv1a_hash(ULONG * data,size_t length)28 ULONG fnv1a_hash(ULONG *data, size_t length)
29 {
30 ULONG hash = 2166136261u; // FNV offset basis (a large prime number)
31 for (size_t i = 0; i < length; ++i)
32 {
33 hash ^= data[i];
34 hash *= 16777619u; // FNV prime
35 }
36 return hash;
37 }
38
39 static inline
40 ULONG
RtlComputeBitmapHashDbg(_In_ PRTL_BITMAP_DBG BitMapHeader)41 RtlComputeBitmapHashDbg(
42 _In_ PRTL_BITMAP_DBG BitMapHeader)
43 {
44 ULONG SizeInBytes = ALIGN_UP_BY(BitMapHeader->BitMap.SizeOfBitMap, 32) / 32;
45 return fnv1a_hash(BitMapHeader->BitMap.Buffer, SizeInBytes / sizeof(ULONG));
46 }
47
48 static inline
49 VOID
RtlValidateBitmapDbg(_Inout_ PRTL_BITMAP_DBG BitMapHeader)50 RtlValidateBitmapDbg(
51 _Inout_ PRTL_BITMAP_DBG BitMapHeader)
52 {
53 ULONG NumberOfSetBits = RtlNumberOfSetBits(&BitMapHeader->BitMap);
54 ASSERT(BitMapHeader->NumberOfSetBits == NumberOfSetBits);
55 ULONG BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
56 ASSERT(BitMapHeader->BitmapHash == BitmapHash);
57 }
58
59 _At_(BitMapHeader->SizeOfBitMap, _Post_equal_to_(SizeOfBitMap))
60 _At_(BitMapHeader->Buffer, _Post_equal_to_(BitMapBuffer))
61 static inline
62 VOID
RtlInitializeBitMapDbg(_Out_ PRTL_BITMAP_DBG BitMapHeader,_In_opt_ __drv_aliasesMem PULONG BitMapBuffer,_In_opt_ ULONG SizeOfBitMap)63 RtlInitializeBitMapDbg(
64 _Out_ PRTL_BITMAP_DBG BitMapHeader,
65 _In_opt_ __drv_aliasesMem PULONG BitMapBuffer,
66 _In_opt_ ULONG SizeOfBitMap)
67 {
68 RtlInitializeBitMap(&BitMapHeader->BitMap, BitMapBuffer, SizeOfBitMap);
69 BitMapHeader->NumberOfSetBits = RtlNumberOfSetBits(&BitMapHeader->BitMap);
70 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
71 }
72
73 static inline
74 BOOLEAN
RtlAreBitsClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG StartingIndex,_In_ ULONG Length)75 RtlAreBitsClearDbg(
76 _In_ PRTL_BITMAP_DBG BitMapHeader,
77 _In_ ULONG StartingIndex,
78 _In_ ULONG Length)
79 {
80 RtlValidateBitmapDbg(BitMapHeader);
81 return RtlAreBitsClear(&BitMapHeader->BitMap, StartingIndex, Length);
82 }
83
84 static inline
85 BOOLEAN
RtlAreBitsSetDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG StartingIndex,_In_ ULONG Length)86 RtlAreBitsSetDbg(
87 _In_ PRTL_BITMAP_DBG BitMapHeader,
88 _In_ ULONG StartingIndex,
89 _In_ ULONG Length)
90 {
91 RtlValidateBitmapDbg(BitMapHeader);
92 return RtlAreBitsSet(&BitMapHeader->BitMap, StartingIndex, Length);
93 }
94
95 static inline
96 VOID
RtlClearAllBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader)97 RtlClearAllBitsDbg(
98 _In_ PRTL_BITMAP_DBG BitMapHeader)
99 {
100 RtlValidateBitmapDbg(BitMapHeader);
101 RtlClearAllBits(&BitMapHeader->BitMap);
102 BitMapHeader->NumberOfSetBits = 0;
103 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
104 }
105
106 static inline
107 VOID
108 RtlClearBitDbg(
109 _In_ PRTL_BITMAP_DBG BitMapHeader,
110 _In_range_(<, BitMapHeader->SizeOfBitMap) ULONG BitNumber)
111 {
112 RtlValidateBitmapDbg(BitMapHeader);
113 if (RtlCheckBit(&BitMapHeader->BitMap, BitNumber) == FALSE)
114 {
115 BitMapHeader->NumberOfSetBits--;
116 }
117 RtlClearBit(&BitMapHeader->BitMap, BitNumber);
118 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
119 }
120
121 static inline
122 VOID
123 RtlClearBitsDbg(
124 _In_ PRTL_BITMAP_DBG BitMapHeader,
125 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToClear) ULONG StartingIndex,
126 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) ULONG NumberToClear)
127 {
128 RtlValidateBitmapDbg(BitMapHeader);
129 RtlClearBits(&BitMapHeader->BitMap, StartingIndex, NumberToClear);
130 BitMapHeader->NumberOfSetBits = RtlNumberOfSetBits(&BitMapHeader->BitMap);
131 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
132 }
133
134 static inline
135 ULONG
RtlFindClearBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG NumberToFind,_In_ ULONG HintIndex)136 RtlFindClearBitsDbg(
137 _In_ PRTL_BITMAP_DBG BitMapHeader,
138 _In_ ULONG NumberToFind,
139 _In_ ULONG HintIndex)
140 {
141 RtlValidateBitmapDbg(BitMapHeader);
142 return RtlFindClearBits(&BitMapHeader->BitMap, NumberToFind, HintIndex);
143 }
144
145 static inline
146 ULONG
RtlFindClearBitsAndSetDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG NumberToFind,_In_ ULONG HintIndex)147 RtlFindClearBitsAndSetDbg(
148 _In_ PRTL_BITMAP_DBG BitMapHeader,
149 _In_ ULONG NumberToFind,
150 _In_ ULONG HintIndex)
151 {
152 RtlValidateBitmapDbg(BitMapHeader);
153 return RtlFindClearBitsAndSet(&BitMapHeader->BitMap, NumberToFind, HintIndex);
154 }
155
156 static inline
157 ULONG
RtlFindFirstRunClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_Out_ PULONG StartingIndex)158 RtlFindFirstRunClearDbg(
159 _In_ PRTL_BITMAP_DBG BitMapHeader,
160 _Out_ PULONG StartingIndex)
161 {
162 RtlValidateBitmapDbg(BitMapHeader);
163 return RtlFindFirstRunClear(&BitMapHeader->BitMap, StartingIndex);
164 }
165
166 static inline
167 ULONG
168 RtlFindClearRunsDbg(
169 _In_ PRTL_BITMAP_DBG BitMapHeader,
170 _Out_writes_to_(SizeOfRunArray, return) PRTL_BITMAP_RUN RunArray,
171 _In_range_(>, 0) ULONG SizeOfRunArray,
172 _In_ BOOLEAN LocateLongestRuns)
173 {
174 RtlValidateBitmapDbg(BitMapHeader);
175 return RtlFindClearRuns(&BitMapHeader->BitMap, RunArray, SizeOfRunArray, LocateLongestRuns);
176 }
177
178 static inline
179 ULONG
RtlFindLastBackwardRunClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG FromIndex,_Out_ PULONG StartingRunIndex)180 RtlFindLastBackwardRunClearDbg(
181 _In_ PRTL_BITMAP_DBG BitMapHeader,
182 _In_ ULONG FromIndex,
183 _Out_ PULONG StartingRunIndex)
184 {
185 RtlValidateBitmapDbg(BitMapHeader);
186 return RtlFindLastBackwardRunClear(&BitMapHeader->BitMap, FromIndex, StartingRunIndex);
187 }
188
189 static inline
190 ULONG
RtlFindLongestRunClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_Out_ PULONG StartingIndex)191 RtlFindLongestRunClearDbg(
192 _In_ PRTL_BITMAP_DBG BitMapHeader,
193 _Out_ PULONG StartingIndex)
194 {
195 RtlValidateBitmapDbg(BitMapHeader);
196 return RtlFindLongestRunClear(&BitMapHeader->BitMap, StartingIndex);
197 }
198
199 static inline
200 ULONG
RtlFindNextForwardRunClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG FromIndex,_Out_ PULONG StartingRunIndex)201 RtlFindNextForwardRunClearDbg(
202 _In_ PRTL_BITMAP_DBG BitMapHeader,
203 _In_ ULONG FromIndex,
204 _Out_ PULONG StartingRunIndex)
205 {
206 RtlValidateBitmapDbg(BitMapHeader);
207 return RtlFindNextForwardRunClear(&BitMapHeader->BitMap, FromIndex, StartingRunIndex);
208 }
209
210 static inline
211 ULONG
RtlFindNextForwardRunSetDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG FromIndex,_Out_ PULONG StartingRunIndex)212 RtlFindNextForwardRunSetDbg(
213 _In_ PRTL_BITMAP_DBG BitMapHeader,
214 _In_ ULONG FromIndex,
215 _Out_ PULONG StartingRunIndex)
216 {
217 RtlValidateBitmapDbg(BitMapHeader);
218 return RtlFindNextForwardRunSet(&BitMapHeader->BitMap, FromIndex, StartingRunIndex);
219 }
220
221 static inline
222 ULONG
RtlFindSetBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG NumberToFind,_In_ ULONG HintIndex)223 RtlFindSetBitsDbg(
224 _In_ PRTL_BITMAP_DBG BitMapHeader,
225 _In_ ULONG NumberToFind,
226 _In_ ULONG HintIndex)
227 {
228 RtlValidateBitmapDbg(BitMapHeader);
229 return RtlFindSetBits(&BitMapHeader->BitMap, NumberToFind, HintIndex);
230 }
231
232 static inline
233 ULONG
RtlFindSetBitsAndClearDbg(_In_ PRTL_BITMAP_DBG BitMapHeader,_In_ ULONG NumberToFind,_In_ ULONG HintIndex)234 RtlFindSetBitsAndClearDbg(
235 _In_ PRTL_BITMAP_DBG BitMapHeader,
236 _In_ ULONG NumberToFind,
237 _In_ ULONG HintIndex)
238 {
239 RtlValidateBitmapDbg(BitMapHeader);
240 return RtlFindSetBitsAndClear(&BitMapHeader->BitMap, NumberToFind, HintIndex);
241 }
242
243 static inline
244 ULONG
RtlNumberOfClearBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader)245 RtlNumberOfClearBitsDbg(
246 _In_ PRTL_BITMAP_DBG BitMapHeader)
247 {
248 RtlValidateBitmapDbg(BitMapHeader);
249 return RtlNumberOfClearBits(&BitMapHeader->BitMap);
250 }
251
252 static inline
253 ULONG
RtlNumberOfSetBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader)254 RtlNumberOfSetBitsDbg(
255 _In_ PRTL_BITMAP_DBG BitMapHeader)
256 {
257 RtlValidateBitmapDbg(BitMapHeader);
258 return RtlNumberOfSetBits(&BitMapHeader->BitMap);
259 }
260
261 static inline
262 VOID
263 RtlSetBitDbg(
264 _In_ PRTL_BITMAP_DBG BitMapHeader,
265 _In_range_(<, BitMapHeader->SizeOfBitMap) ULONG BitNumber)
266 {
267 RtlValidateBitmapDbg(BitMapHeader);
268 if (RtlCheckBit(&BitMapHeader->BitMap, BitNumber) == FALSE)
269 {
270 BitMapHeader->NumberOfSetBits++;
271 }
272 RtlSetBit(&BitMapHeader->BitMap, BitNumber);
273 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
274 }
275
276 static inline
277 VOID
278 RtlSetBitsDbg(
279 _In_ PRTL_BITMAP_DBG BitMapHeader,
280 _In_range_(0, BitMapHeader->SizeOfBitMap - NumberToSet) ULONG StartingIndex,
281 _In_range_(0, BitMapHeader->SizeOfBitMap - StartingIndex) ULONG NumberToSet)
282 {
283 RtlValidateBitmapDbg(BitMapHeader);
284 RtlSetBits(&BitMapHeader->BitMap, StartingIndex, NumberToSet);
285 BitMapHeader->NumberOfSetBits = RtlNumberOfSetBits(&BitMapHeader->BitMap);
286 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
287 }
288
289 static inline
290 VOID
RtlSetAllBitsDbg(_In_ PRTL_BITMAP_DBG BitMapHeader)291 RtlSetAllBitsDbg(
292 _In_ PRTL_BITMAP_DBG BitMapHeader)
293 {
294 RtlValidateBitmapDbg(BitMapHeader);
295 RtlSetAllBits(&BitMapHeader->BitMap);
296 BitMapHeader->NumberOfSetBits = BitMapHeader->BitMap.SizeOfBitMap;
297 BitMapHeader->BitmapHash = RtlComputeBitmapHashDbg(BitMapHeader);
298 }
299
300 _Must_inspect_result_
301 static inline
302 BOOLEAN
303 RtlTestBitDbg(
304 _In_ PRTL_BITMAP_DBG BitMapHeader,
305 _In_range_(<, BitMapHeader->SizeOfBitMap) ULONG BitNumber)
306 {
307 RtlValidateBitmapDbg(BitMapHeader);
308 return RtlTestBit(&BitMapHeader->BitMap, BitNumber);
309 }
310
311 _Must_inspect_result_
312 static inline
313 BOOLEAN
314 RtlCheckBitDbg(
315 _In_ PRTL_BITMAP_DBG BitMapHeader,
316 _In_range_(<, BitMapHeader->SizeOfBitMap) ULONG BitPosition)
317 {
318 RtlValidateBitmapDbg(BitMapHeader);
319 return RtlCheckBit(&BitMapHeader->BitMap, BitPosition);
320 }
321
322 #define _RTL_BITMAP _RTL_BITMAP_DBG
323 #define RTL_BITMAP RTL_BITMAP_DBG
324 #define PRTL_BITMAP PRTL_BITMAP_DBG
325
326 #define RtlInitializeBitMap RtlInitializeBitMapDbg
327 #define RtlAreBitsClear RtlAreBitsClearDbg
328 #define RtlAreBitsSet RtlAreBitsSetDbg
329 #define RtlClearAllBits RtlClearAllBitsDbg
330 #define RtlClearBit RtlClearBitDbg
331 #define RtlClearBits RtlClearBitsDbg
332 #define RtlFindClearBits RtlFindClearBitsDbg
333 #define RtlFindClearBitsAndSet RtlFindClearBitsAndSetDbg
334 #define RtlFindFirstRunClear RtlFindFirstRunClearDbg
335 #define RtlFindClearRuns RtlFindClearRunsDbg
336 #define RtlFindLastBackwardRunClear RtlFindLastBackwardRunClearDbg
337 #define RtlFindLongestRunClear RtlFindLongestRunClearDbg
338 #define RtlFindNextForwardRunClear RtlFindNextForwardRunClearDbg
339 #define RtlFindNextForwardRunSet RtlFindNextForwardRunSetDbg
340 #define RtlFindSetBits RtlFindSetBitsDbg
341 #define RtlFindSetBitsAndClear RtlFindSetBitsAndClearDbg
342 #define RtlNumberOfClearBits RtlNumberOfClearBitsDbg
343 #define RtlNumberOfSetBits RtlNumberOfSetBitsDbg
344 #define RtlSetBit RtlSetBitDbg
345 #define RtlSetBits RtlSetBitsDbg
346 #define RtlSetAllBits RtlSetAllBitsDbg
347 #define RtlTestBit RtlTestBitDbg
348 #undef RtlCheckBit
349 #define RtlCheckBit RtlCheckBitDbg
350