1// tBitArray.h 
2// 
3// A tBitArray is a holder for an arbitrary number of bits and allows individual access to each bit, the ability to 
4// clear or set all bits, and some simple binary bitwise operators such as 'and', 'xor', and 'or'. It currently does 
5// not support dynamic growing or shrinking. 
6// 
7// Comparisons 
8// tBitArray - Use when you want to store a large number of bits and you don't know how many at compile-time. 
9// This type os primatily for storage and access to a large number of bits. Not many bitwise or 
10// mathematical operators. 
11// tBitArray8 - Similar to a tBitArray but uses bytes as the elements. Slightly less efficient but the order of the 
12// bits in memory exactly matches what is being represented in the array. Also less padding needed at end. 
13// tBitField - Use when know how many bits at compile-time and you want bitwise logic opertors like and, or, xor, 
14// shift, not, etc. Good for storing a fixed number of flags or channels etc. 
15// tFixInt - Use when you want full mathematical operations like any built-in integral type. Size must be known at 
16// compile time and must be a multiple of 32 bits. You get + - / * etc as well as all bitwise logic ops. 
17// 
18// Copyright (c) 2004-2006, 2015, 2017, 2019, 2021-2023 Tristan Grimmer. 
19// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
20// granted, provided that the above copyright notice and this permission notice appear in all copies. 
21// 
22// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
24// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
25// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
26// PERFORMANCE OF THIS SOFTWARE. 
27 
28#pragma once 
29#include "Foundation/tPlatform.h" 
30#include "Foundation/tStandard.h" 
31 
32 
33// This class uses 32-bit elements to store the bit array for efficiency. The bits are ordered from the LSB to the MSB so 
34// that the 0th bit (on the right) is the first one, 1st bit is the second, and so on. For example, with 35-bits: 
35// 1 35 
36// 10101111 11110000 10000010 11100011 011 The array we want to represent. 
37// 11000111 01000001 00001111 11110101 00000000 00000000 00000000 00000110 As 2 32-bit elements. 
38// 11110101 00001111 01000001 11000111 00000110 00000000 00000000 00000000 In memory on a little-endian machine. 
39// 
40class tBitArray 
41{ 
42public: 
43 tBitArray() /* Creates an invalid bit array. Call Set before using. */ { } 
44 tBitArray(int numBits) /* All bit values guaranteed to be 0 after this. */ { Set(numBits); } 
45 tBitArray(uint32* data, int numBits, bool ext = false) /* Copies numBits from data. If ext data is external.*/ { Set(data, numBits, ext); } 
46 tBitArray(const tBitArray& src) { Set(src); } 
47 ~tBitArray() { if (!ExternalData) delete[] ElemData; } 
48 
49 void Set(int numBits); // All bit values guaranteed to be 0 after this. 
50 void Set(uint32* data, int numBits, bool ext = false); // Copies numBits from data. If ext is true data is external. 
51 void Set(const tBitArray& src); 
52 void Clear() /* Invalidates. Use ClearAll if you want all bits clear. */ { if (!ExternalData) delete[] ElemData; ElemData = nullptr; NumBits = 0; } 
53 bool IsValid() const { return ElemData ? true : false; } 
54 
55 bool GetBit(int n) const; // Gets the n-th bit. 0-based and n must be E [0, NumBits). 
56 uint8 GetBitInt(int n) const; // Gets the n-th bit. 0-based and n must be E [0, NumBits). 
57 // n is the start bit (inclusive) and c is the count. You can get from 1 to 8 bits using this function c E [1, 8]. 
58 // Return value undefined if c <= 0 or c > 8 or n >= GetNumBits. If it goes off the end no more bits are returned, 
59 // for example, if the bit array has 11101 and you call with (2,6) you'll get 101. 
60 uint8 GetBits(int n, int c) const; 
61  
62 void SetBit(int n, bool v); 
63 void SetBitInt(int n, int v); // If v non-zero, sets the bit. Otherwise clears it. 
64 void SetBits(int n, int c, uint8 v); // Similar to GetBits but sets from 1 to 8 bits from v. 
65 
66 void SetAll(bool v = true); 
67 void ClearAll(); 
68 void InvertAll(); 
69 bool AreAll(bool v) const; 
70 int GetNumBits() const { return NumBits; } 
71 int CountBits(bool = true) const; // Counts how many bits are set to supplied value. 
72 
73 // These deal with the internal uint32 elements that store the bit array. The elements are always least-significant 
74 // at the beginning, regardless of machine endianness. 
75 int GetNumElements() const { return ((NumBits + 31) / 32); } 
76 
77 // Ensure array is valid and i is in range before calling these. That part is up to you. 
78 uint32 GetElement(int i) const { tAssert(IsValid()); return ElemData[i]; } 
79 void SetElement(int i, uint32 val) { tAssert(IsValid()); ElemData[i] = val; } 
80 
81 void GetElements(uint32* dest) const /* Least significant at the beginning. */ { tAssert(dest); tStd::tMemcpy(dest, src: ElemData, numBytes: GetNumElements()*4); } 
82 void SetElements(const uint32* src) /* Least sig at the beginning. Clears unused bits. */ { tAssert(src); tStd::tMemcpy(dest: ElemData, src, numBytes: GetNumElements()*4); ClearPadBits(); } 
83 
84 uint32& Element(int i) { return ElemData[i]; } 
85 uint32* Elements() const { return ElemData; } 
86 
87 // Returns index of first bit that is 0. Returns -1 if no bits are clear. 
88 int FindFirstClearBit() const; 
89 
90 // Binary operators must operate on arrays with the same number of bits. 
91 tBitArray& operator=(const tBitArray& src) { Set(src); return *this; } 
92 tBitArray& operator&=(const tBitArray&); 
93 tBitArray& operator|=(const tBitArray&); 
94 tBitArray& operator^=(const tBitArray&); 
95 
96 const tBitArray operator~() const { tBitArray r(*this); r.InvertAll(); return r; } 
97 bool operator[](int n) const { return GetBit(n); } 
98 bool operator==(const tBitArray&) const; 
99 bool operator!=(const tBitArray&) const; 
100 
101private: 
102 void ClearPadBits(); 
103 
104 int NumBits = 0; // Number of bits. Not number of fields. 
105 bool ExternalData = false; // If true this object doesn't own the ElemData. 
106 uint32* ElemData = nullptr; // If there are padding bits, they must be set to 0. 
107}; 
108 
109 
110// This class uses 8-bit elements to store the bit array for efficiency. Unlike tBitArray the bits are ordered from MSB 
111// to LSB so that the 7th bit (on the left) is the first one, 6th bit is the second, and so on down to the 0th bit which 
112// is the eighth. For example, with 19-bits: 
113// 1 19 
114// 10101111 11110000 101 The array we want to represent. 
115// 10101111 11110000 10100000 As 3 8-bit elements. 
116// 10101111 11110000 10100000 In memory regardless of endianness. 
117// 
118class tBitArray8 
119{ 
120public: 
121 tBitArray8() /* Creates an invalid bit array. Call Set before using. */ { } 
122 tBitArray8(int numBits) /* All bit values guaranteed to be 0 after this. */ { Set(numBits); } 
123 tBitArray8(uint8* data, int numBits, bool ext = false) /* Copies numBits from data. If ext data is external.*/ { Set(data, numBits, ext); } 
124 tBitArray8(const tBitArray8& src) { Set(src); } 
125 ~tBitArray8() { if (!ExternalData) delete[] ElemData; } 
126 
127 void Set(int numBits); // All bit values guaranteed to be 0 after this. 
128 void Set(uint8* data, int numBits, bool ext = false); // Copies numBits from data. If ext is true data is external. 
129 void Set(const tBitArray8& src); 
130 void Clear() /* Invalidates. Use ClearAll if you want all bits clear. */ { if (!ExternalData) delete[] ElemData; ElemData = nullptr; NumBits = 0; } 
131 bool IsValid() const { return ElemData ? true : false; } 
132 
133 bool GetBit(int n) const; // Gets the n-th bit. 0-based and n must be E [0, NumBits). 
134 uint8 GetBitInt(int n) const; // Gets the n-th bit. 0-based and n must be E [0, NumBits). 
135 // n is the start bit (inclusive) and c is the count. You can get from 1 to 8 bits using this function c E [1, 8]. 
136 // Return value undefined if c <= 0 or c > 8 or n >= GetNumBits. If it goes off the end no more bits are returned, 
137 // for example, if the bit array has 11101 and you call with (2,6) you'll get 101. 
138 uint8 GetBits(int n, int c) const; 
139 
140 void SetBit(int n, bool v); 
141 void SetBitInt(int n, int v); // If v non-zero, sets the bit. Otherwise clears it. 
142 void SetBits(int n, int c, uint8 v); // Similar to GetBits but sets from 1 to 8 bits from v. 
143 
144 void SetAll(bool v = true); 
145 void ClearAll(); 
146 void InvertAll(); 
147 bool AreAll(bool v) const; 
148 int GetNumBits() const { return NumBits; } 
149 int CountBits(bool = true) const; // Counts how many bits are set to supplied value. 
150 
151 // These deal with the internal uint8 elements that store the bit array. 
152 int GetNumElements() const { return ((NumBits + 7) / 8); } 
153 
154 // Ensure array is valid and i is in range before calling these. That part is up to you. 
155 uint8 GetElement(int i) const { tAssert(IsValid()); return ElemData[i]; } 
156 void SetElement(int i, uint8 val) { tAssert(IsValid()); ElemData[i] = val; } 
157 
158 void GetElements(uint8* dest) const { tAssert(dest); tStd::tMemcpy(dest, src: ElemData, numBytes: GetNumElements()); } 
159 void SetElements(const uint8* src) /* Clears unused bits. */ { tAssert(src); tStd::tMemcpy(dest: ElemData, src, numBytes: GetNumElements()); ClearPadBits(); } 
160 
161 uint8& Element(int i) { return ElemData[i]; } 
162 uint8* Elements() const { return ElemData; } 
163 
164 // Returns index of first bit that is 0. Returns -1 if no bits are clear. 
165 int FindFirstClearBit() const; 
166 
167 // Binary operators must operate on arrays with the same number of bits. 
168 tBitArray8& operator=(const tBitArray8& src) { Set(src); return *this; } 
169 tBitArray8& operator&=(const tBitArray8&); 
170 tBitArray8& operator|=(const tBitArray8&); 
171 tBitArray8& operator^=(const tBitArray8&); 
172 
173 const tBitArray8 operator~() const { tBitArray8 r(*this); r.InvertAll(); return r; } 
174 bool operator[](int n) const { return GetBit(n); } 
175 bool operator==(const tBitArray8&) const; 
176 bool operator!=(const tBitArray8&) const; 
177 
178private: 
179 void ClearPadBits(); 
180 
181 int NumBits = 0; // Number of bits. Not number of fields. 
182 bool ExternalData = false; // If true this object doesn't own the ElemData. 
183 uint8* ElemData = nullptr; // If there are padding bits, they must be set to 0. 
184}; 
185 
186 
187// Implementation below this line. 
188 
189// 
190// tBitArray inlines. 
191// 
192inline bool tBitArray::GetBit(int index) const 
193{ 
194 return GetBitInt(n: index) ? true : false; 
195} 
196 
197 
198inline uint8 tBitArray::GetBitInt(int index) const 
199{ 
200 tAssert(index < NumBits); 
201 int fieldIndex = index >> 5; 
202 int offset = index & 0x1F; 
203 uint32 mask = 1 << offset; 
204 
205 return (ElemData[fieldIndex] & mask) ? 1 : 0; 
206} 
207 
208 
209inline uint8 tBitArray::GetBits(int n, int c) const 
210{ 
211 if ((c <= 0) || (c > 8) || (n >= NumBits)) 
212 return 0; 
213 
214 // Reduce count if it goes off end. 
215 if ((n + c) > NumBits) 
216 c = NumBits - n; 
217 
218 // @todo This could be made more efficient by grabbing the one or two 32-bit elements and 
219 // doing bit ops on each to capture more than one bit at a time. 
220 uint8 result = 0; 
221 for (int i = 0; i < c; i++) 
222 result |= GetBitInt(index: n+i) << (c-i-1); 
223 
224 return result; 
225} 
226 
227 
228inline void tBitArray::SetBit(int index, bool v) 
229{ 
230 SetBitInt(n: index, v: v ? 1 : 0); 
231} 
232 
233 
234inline void tBitArray::SetBitInt(int index, int v) 
235{ 
236 tAssert(index < NumBits); 
237 int fieldIndex = index >> 5; 
238 int offset = index & 0x1F; 
239 uint32 mask = 1 << offset; 
240 if (v) 
241 ElemData[fieldIndex] |= mask; 
242 else 
243 ElemData[fieldIndex] &= ~mask; 
244} 
245 
246 
247inline void tBitArray::SetBits(int n, int c, uint8 v) 
248{ 
249 if ((c <= 0) || (c > 8) || (n >= NumBits)) 
250 return; 
251 
252 // Reduce count if it goes off end. 
253 if ((n + c) > NumBits) 
254 c = NumBits - n; 
255 
256 // @todo This could be made more efficient by grabbing the one or two 8-bit elements and 
257 // doing bit ops on each to set more than one bit at a time. 
258 for (int i = 0; i < c; i++) 
259 { 
260 uint8 bit = v & (1<<(c-i-1)); 
261 SetBitInt(index: n+i, v: bit); 
262 } 
263} 
264 
265 
266inline void tBitArray::SetAll(bool v) 
267{ 
268 int n = GetNumElements(); 
269 tStd::tMemset(dest: ElemData, val: v ? 0xFF : 0, numBytes: n*sizeof(uint32)); 
270 if (v) 
271 ClearPadBits(); 
272} 
273 
274 
275inline void tBitArray::ClearAll() 
276{ 
277 tAssert(ElemData); 
278 int n = GetNumElements(); 
279 tStd::tMemset(dest: ElemData, val: 0, numBytes: n*sizeof(uint32)); 
280} 
281 
282 
283inline void tBitArray::InvertAll() 
284{ 
285 int n = GetNumElements(); 
286 for (int i = 0; i < n; i++) 
287 ElemData[i] = ~ElemData[i]; 
288 
289 ClearPadBits(); 
290} 
291 
292 
293inline tBitArray& tBitArray::operator&=(const tBitArray& s) 
294{ 
295 tAssert(NumBits == s.NumBits); 
296 int n = GetNumElements(); 
297 for (int i = 0; i < n; i++) 
298 ElemData[i] &= s.ElemData[i]; 
299 
300 return *this; // No need to ensure pad bits are cleared because 0 & 0 = 0. 
301} 
302 
303 
304inline tBitArray& tBitArray::operator|=(const tBitArray& s) 
305{ 
306 tAssert(NumBits == s.NumBits); 
307 int n = GetNumElements(); 
308 for (int i = 0; i < n; i++) 
309 ElemData[i] |= s.ElemData[i]; 
310 
311 return *this; // No need to ensure pad bits are cleared because 0 | 0 = 0. 
312} 
313 
314 
315inline tBitArray& tBitArray::operator^=(const tBitArray& s) 
316{ 
317 tAssert(NumBits == s.NumBits); 
318 int n = GetNumElements(); 
319 for (int i = 0; i < n; i++) 
320 ElemData[i] ^= s.ElemData[i]; 
321 
322 return *this; // No need to ensure pad bits are cleared because 0 ^ 0 = 0. 
323} 
324 
325 
326inline bool tBitArray::operator==(const tBitArray& s) const 
327{ 
328 tAssert(GetNumBits() == s.GetNumBits()); 
329 int n = GetNumElements(); 
330 
331 // Padding bits are guaranteed 0 so we can coompare elements. 
332 for (int i = 0; i < n; i++) 
333 if (ElemData[i] != s.ElemData[i]) 
334 return false; 
335 
336 return true; 
337} 
338 
339 
340inline void tBitArray::ClearPadBits() 
341{ 
342 tAssert(ElemData); 
343 int n = GetNumElements(); 
344 int last = NumBits & 0x1F; 
345 uint32 maxFull = (last ? (1 << last) : 0) - 1; 
346 ElemData[n-1] &= maxFull; 
347} 
348 
349 
350// 
351// tBitArray8 inlines. 
352// 
353inline bool tBitArray8::GetBit(int index) const 
354{ 
355 return GetBitInt(n: index) ? true : false; 
356} 
357 
358 
359inline uint8 tBitArray8::GetBitInt(int index) const 
360{ 
361 tAssert(index < NumBits); 
362 int fieldIndex = index >> 3; 
363 int offset = 7-(index & 0x07); 
364 uint8 mask = 1 << offset; 
365 
366 return (ElemData[fieldIndex] & mask) ? 1 : 0; 
367} 
368 
369 
370inline uint8 tBitArray8::GetBits(int n, int c) const 
371{ 
372 if ((c <= 0) || (c > 8) || (n >= NumBits)) 
373 return 0; 
374 
375 // Reduce count if it goes off end. 
376 if ((n + c) > NumBits) 
377 c = NumBits - n; 
378 
379 // @todo This could be made more efficient by grabbing the one or two 8-bit elements and 
380 // doing bit ops on each to capture more than one bit at a time. 
381 uint8 result = 0; 
382 for (int i = 0; i < c; i++) 
383 result |= GetBitInt(index: n+i) << (c-i-1); 
384 
385 return result; 
386} 
387 
388 
389inline void tBitArray8::SetBit(int index, bool v) 
390{ 
391 SetBitInt(n: index, v: v ? 1 : 0); 
392} 
393 
394 
395inline void tBitArray8::SetBitInt(int index, int v) 
396{ 
397 tAssert(index < NumBits); 
398 int fieldIndex = index >> 3; 
399 int offset = 7-(index & 0x07); 
400 uint8 mask = 1 << offset; 
401 if (v) 
402 ElemData[fieldIndex] |= mask; 
403 else 
404 ElemData[fieldIndex] &= ~mask; 
405} 
406 
407 
408inline void tBitArray8::SetBits(int n, int c, uint8 v) 
409{ 
410 if ((c <= 0) || (c > 8) || (n >= NumBits)) 
411 return; 
412 
413 // Reduce count if it goes off end. 
414 if ((n + c) > NumBits) 
415 c = NumBits - n; 
416 
417 // @todo This could be made more efficient by grabbing the one or two 8-bit elements and 
418 // doing bit ops on each to set more than one bit at a time. 
419 for (int i = 0; i < c; i++) 
420 { 
421 uint8 bit = v & (1<<(c-i-1)); 
422 SetBitInt(index: n+i, v: bit); 
423 } 
424} 
425 
426 
427inline void tBitArray8::SetAll(bool v) 
428{ 
429 int n = GetNumElements(); 
430 tStd::tMemset(dest: ElemData, val: v ? 0xFF : 0x00, numBytes: n*sizeof(uint8)); 
431 if (v) 
432 ClearPadBits(); 
433} 
434 
435 
436inline void tBitArray8::ClearAll() 
437{ 
438 tAssert(ElemData); 
439 int n = GetNumElements(); 
440 tStd::tMemset(dest: ElemData, val: 0, numBytes: n*sizeof(uint8)); 
441} 
442 
443 
444inline void tBitArray8::InvertAll() 
445{ 
446 int n = GetNumElements(); 
447 for (int i = 0; i < n; i++) 
448 ElemData[i] = ~ElemData[i]; 
449 
450 ClearPadBits(); 
451} 
452 
453 
454inline tBitArray8& tBitArray8::operator&=(const tBitArray8& s) 
455{ 
456 tAssert(NumBits == s.NumBits); 
457 int n = GetNumElements(); 
458 for (int i = 0; i < n; i++) 
459 ElemData[i] &= s.ElemData[i]; 
460 
461 return *this; // No need to ensure pad bits are cleared because 0 & 0 = 0. 
462} 
463 
464 
465inline tBitArray8& tBitArray8::operator|=(const tBitArray8& s) 
466{ 
467 tAssert(NumBits == s.NumBits); 
468 int n = GetNumElements(); 
469 for (int i = 0; i < n; i++) 
470 ElemData[i] |= s.ElemData[i]; 
471 
472 return *this; // No need to ensure pad bits are cleared because 0 | 0 = 0. 
473} 
474 
475 
476inline tBitArray8& tBitArray8::operator^=(const tBitArray8& s) 
477{ 
478 tAssert(NumBits == s.NumBits); 
479 int n = GetNumElements(); 
480 for (int i = 0; i < n; i++) 
481 ElemData[i] ^= s.ElemData[i]; 
482 
483 return *this; // No need to ensure pad bits are cleared because 0 ^ 0 = 0. 
484} 
485 
486 
487inline bool tBitArray8::operator==(const tBitArray8& s) const 
488{ 
489 tAssert(GetNumBits() == s.GetNumBits()); 
490 int n = GetNumElements(); 
491 
492 // Padding bits are guaranteed 0 so we can coompare elements. 
493 for (int i = 0; i < n; i++) 
494 if (ElemData[i] != s.ElemData[i]) 
495 return false; 
496 
497 return true; 
498} 
499 
500 
501inline void tBitArray8::ClearPadBits() 
502{ 
503 tAssert(ElemData); 
504 int n = GetNumElements(); 
505 int last = NumBits & 0x07; 
506 if (last) 
507 { 
508 uint8 maxFull = ((1 << last) - 1) << (8-last); 
509 ElemData[n-1] &= maxFull; 
510 } 
511} 
512