1// tBitField.h 
2// 
3// A tBitField is a fixed size array of bits. Similar to STL bitset class. An tBitField needs to know how many bits 
4// will be stored at compile time and there is no possibility to grow or dynamically change that number. All bitwise 
5// operators are overloaded appropriately. This class is perfect for flags where a uint32 or uint64 is not enough. 
6// If you need mathematical operators like subtraction, addition, multiplication, division etc, use the heavier 
7// tFixInt instead. If you need a dynamic number of bits, use a tBitArray instead. If you don't, this will be faster. 
8// 
9// Copyright (c) 2004-2006, 2015, 2017, 2020 Tristan Grimmer. 
10// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
11// granted, provided that the above copyright notice and this permission notice appear in all copies. 
12// 
13// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
14// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
15// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
16// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
17// PERFORMANCE OF THIS SOFTWARE. 
18 
19#pragma once 
20#include "Foundation/tFixInt.h" 
21#include "Foundation/tString.h" 
22 
23 
24// The tBitField class. NumBits represents the number of bits that can be stored by the instance. There are no 
25// conditions on the value of NumBits used and long as it is a whole number. If NumBits is a multiple of 4, the 
26// tBitField will be supported by tPrintf so just call something like: tsPrintf(s, "%032|128X", bitvar128) to convert it 
27// to a string. The memory image size taken up will always be a multiple of 4 bytes. ex: sizeof(tBitField<16>) = 4 and 
28// sizeof(tBitField<33>) = 8. You can still use tPrintf on a 33-bit bit-field, just be aware of the size. Any padding 
29// bits are guaranteed to be clear in the internal representation and when saved to a chunk (disk) format. 
30template<int NumBits> class tBitField 
31{ 
32public: 
33 tBitField() /* All bits cleared. */ { Clear(); } 
34 
35 // Disabled CopyCons so class remains a POD-type. Allows it to be passed to tPrintf for non MSVC compilers. 
36 // tBitField(const tBitField& src) { for (int i = 0; i < NumElements; i++) Elements[i] = src.Elements[i]; } 
37 
38 tBitField(const tString& str, int base = -1) { Set(str); } 
39 tBitField(int val) { Set(val); } 
40 
41 // Power-of-2 constructors from 8 to 256 bits. 
42 tBitField(uint8 val) { Set(val); } 
43 tBitField(uint16 val) { Set(val); } 
44 tBitField(uint32 val) { Set(val); } 
45 tBitField(uint64 val) { Set(val); } 
46 tBitField(uint64 msb, uint64 lsb) { Set(msb, lsb); } 
47 tBitField(uint64 msb, uint64 hb, uint64 lb, uint64 lsb) { Set(msb, hb, lb, lsb); } 
48 
49 // Array constructors. 
50 tBitField(const uint8* src, int len) /* See Set(const uint8*, int) */ { Set(src, len); } 
51 tBitField(const uint16* src, int len) /* See Set(const uint8*, int) */ { Set(src, len); } 
52 tBitField(const uint32* src, int len) /* See Set(const uint8*, int) */ { Set(src, len); } 
53 tBitField(const uint64* src, int len) /* See Set(const uint8*, int) */ { Set(src, len); } 
54 
55 // The supplied string should follow the formatting characteristics of the tStrtoi functions. If the base is -1 (or 
56 // not between 2 and 36) the function looks for the following prefixes to determine the base: 
57 // 
58 // Base 16 prefixes: x X 0x 0X # 
59 // Base 10 prefixes: d D 0d 0D 
60 // Base 8 prefixes: o O 0o 0O @ 
61 // Base 4 prefixes: n N 0n 0N (N for Nibble) 
62 // Base 2 prefixes: b B 0b 0B ! 
63 // 
64 // If the prefix is missing (and base == -1), it assumes base 10. Note the default base is 16. This is because this 
65 // is a bit-field so hex seems more natural. 
66 void Set(const char*, int base = 16); 
67 
68 // Sets the bitfield from the supplied data. Asserts if the bit-field is not big enough. The bitfield is allowed to 
69 // be bigger, in which case zeroes are set in the most-sig bits. 
70 void Set(int val) { Set(uint32(val)); } 
71 void Set(uint8 val); 
72 void Set(uint16 val); 
73 void Set(uint32 val); 
74 void Set(uint64 val); 
75 void Set(uint64 msb, uint64 lsb); 
76 void Set(uint64 msb, uint64 hb, uint64 lb, uint64 lsb); 
77 void Set(const uint8* src, int len); 
78 void Set(const uint16* src, int len); 
79 void Set(const uint32* src, int len); 
80 void Set(const uint64* src, int len); 
81 
82 // Gets the bit-field as a numeric string in the base specified. You can also use tPrintf, if you need leading zeroes 
83 // or more control over formatting. This function handles arbitrary bases, however. base E [2, 36] 
84 tString GetAsString(int base = 16) const; 
85 
86 // Gets the n'th bit as a bool. Zero-based index where zero is the least significant binary digit. 
87 bool GetBit(int n) const; 
88  
89 // Sets the n'th bit to val. Zero-based index where zero is least significant binary digit. 
90 void SetBit(int n, bool val); 
91 
92 void Clear() { for (int i = 0; i < NumElements; i++) Elements[i] = 0x00000000; } 
93 void SetAll(bool val = true); 
94 void InvertAll(); 
95 bool AreAll(bool val) const; /* Checks if all bits are set to val. */ 
96 int GetNumBits() const /* Returns the number of bits stored by the bit-field. */ { return NumBits; } 
97 int Count(bool val) const; /* Returns the number of bits that match val. */ 
98 
99 // These deal with the raw uint32 elements that represent the bit array. 
100 int GetNumElements() const /* Returns how many uint32s are used for the bit array. */ { return NumElements; } 
101 void GetElements(uint32* dest) const /* Least significant at the beginning. */ { tAssert(dest); tMemcpy(dest, Elements, NumElements*4); } 
102 uint32* GetElements() const { return (uint32*)Elements; } 
103 void SetElements(const uint32* src) /* Least sig at the beginning. Clears unused bits. */ { tAssert(src); tMemcpy(Elements, src, NumElements*4); ClearUnusedBits(); } 
104 uint32& GetElement(int i) { return Elements[i]; } 
105 
106 tBitField& operator=(const tBitField& s) { if (this == &s) return *this; tStd::tMemcpy(Elements, s.Elements, sizeof(Elements)); return *this; } 
107 
108 // We ensure and assume any pad bits are clear. Since 0 &|^ 0 = 0, we don't need to bother clearing any pad bits. 
109 tBitField& operator&=(const tBitField& s) { for (int i = 0; i < NumElements; i++) Elements[i] &= s.Elements[i]; return *this; } 
110 tBitField& operator|=(const tBitField& s) { for (int i = 0; i < NumElements; i++) Elements[i] |= s.Elements[i]; return *this; } 
111 tBitField& operator^=(const tBitField& s) { for (int i = 0; i < NumElements; i++) Elements[i] ^= s.Elements[i]; return *this; } 
112 
113 // The pad bits are always zeroed when left shifting. 
114 tBitField& operator<<=(int); 
115 tBitField operator<<(int s) const { tBitField<NumBits> set(*this); set <<= s; return set; } 
116 tBitField& operator>>=(int); 
117 tBitField operator>>(int s) const { tBitField<NumBits> set(*this); set >>= s; return set; } 
118 tBitField operator~() const { tBitField set(*this); set.InvertAll(); return set; } 
119 
120 bool operator[](int n) const { return GetBit(n); } 
121 bool operator==(const tBitField&) const; 
122 bool operator!=(const tBitField&) const; 
123 operator bool() const; 
124 
125private: 
126 // The tBitField guarantees clear bits in the internal representation if the number of bits is not a multiple of 32 
127 // (which is our internal storage type size). This function clears them (and only them). 
128 void ClearUnusedBits(); 
129 
130 const static int NumElements = (NumBits >> 5) + ((NumBits % 32) ? 1 : 0); 
131 
132 // The bit-field is stored in an array of uint32s called elements. Any pad bits are set to 0 at all times. The 
133 // elements at smaller array indexes store less significant digits than the ones at larger indexes. 
134 uint32 Elements[NumElements]; 
135}; 
136 
137 
138// These commutative binary operators belong _outside_ of the tBitField class for good OO reasons. i.e. They are global 
139// operators that act on bit-fields. They belong outside in the same way that operator+ does for regular integral types. 
140template<int NumBits> inline tBitField<NumBits> operator&(const tBitField<NumBits>& a, const tBitField<NumBits>& b) { tBitField<NumBits> set(a); set &= b; return set; } 
141template<int NumBits> inline tBitField<NumBits> operator|(const tBitField<NumBits>& a, const tBitField<NumBits>& b) { tBitField<NumBits> set(a); set |= b; return set; } 
142template<int NumBits> inline tBitField<NumBits> operator^(const tBitField<NumBits>& a, const tBitField<NumBits>& b) { tBitField<NumBits> set(a); set ^= b; return set; } 
143 
144 
145// The tbitNNN types represent convenient bit-field sizes. They can represent large sets of bits and even allow bit 
146// operations. They are a little slower that native 32 or 64 bit integers and do not support many math operations. For 
147// full arithmetic support in a 128-bit or larger integer consider using the tFixInt class. Note that since bit-fields 
148// do not support arithmetic, they should be considered unsigned at all times. For example, the right shift >> operator 
149// does not sign extend. 
150typedef tBitField<128> tbit128; 
151typedef tBitField<256> tbit256; 
152typedef tBitField<512> tbit512; 
153 
154 
155// Implementation below this line. 
156 
157 
158template<int N> inline void tBitField<N>::Set(const char* str, int base) 
159{ 
160 tFixIntU< NumElements*32 > val; 
161 val = tStd::tStrtoiT< tFixIntU< NumElements*32 > >(str, base); 
162 tAssert(NumElements == val.GetRawCount()); 
163 for (int i = 0; i < NumElements; i++) 
164 Elements[i] = val.RawElement(i); 
165 
166 ClearUnusedBits(); 
167} 
168 
169 
170template<int N> inline void tBitField<N>::Set(uint8 val) 
171{ 
172 Clear(); 
173 tAssert(NumElements >= 1); 
174 Elements[0] = uint32(val); 
175 ClearUnusedBits(); 
176} 
177 
178 
179template<int N> inline void tBitField<N>::Set(uint16 val) 
180{ 
181 Clear(); 
182 tAssert(NumElements >= 1); 
183 Elements[0] = uint32(val); 
184 ClearUnusedBits(); 
185} 
186 
187 
188template<int N> inline void tBitField<N>::Set(uint32 val) 
189{ 
190 Clear(); 
191 tAssert(NumElements >= 1); 
192 Elements[0] = val; 
193 ClearUnusedBits(); 
194} 
195 
196 
197template<int N> inline void tBitField<N>::Set(uint64 val) 
198{ 
199 Clear(); 
200 tAssert(NumElements >= 2); 
201 Elements[0] = val & 0x00000000FFFFFFFFull; 
202 Elements[1] = (val >> 32) & 0x00000000FFFFFFFFull; 
203 ClearUnusedBits(); 
204} 
205 
206 
207template<int N> inline void tBitField<N>::Set(uint64 msb, uint64 lsb) 
208{ 
209 Clear(); 
210 tAssert(NumElements >= 4); 
211 Elements[0] = lsb & 0x00000000FFFFFFFFull; 
212 Elements[1] = (lsb >> 32) & 0x00000000FFFFFFFFull; 
213 Elements[2] = msb & 0x00000000FFFFFFFFull; 
214 Elements[3] = (msb >> 32) & 0x00000000FFFFFFFFull; 
215 ClearUnusedBits(); 
216} 
217 
218 
219template<int N> inline void tBitField<N>::Set(uint64 msb, uint64 hb, uint64 lb, uint64 lsb) 
220{ 
221 Clear(); 
222 tAssert(NumElements >= 8); 
223 Elements[0] = lsb & 0x00000000FFFFFFFFull; 
224 Elements[1] = (lsb >> 32) & 0x00000000FFFFFFFFull; 
225 Elements[2] = lb & 0x00000000FFFFFFFFull; 
226 Elements[3] = (lb >> 32) & 0x00000000FFFFFFFFull; 
227 Elements[4] = hb & 0x00000000FFFFFFFFull; 
228 Elements[5] = (hb >> 32) & 0x00000000FFFFFFFFull; 
229 Elements[6] = msb & 0x00000000FFFFFFFFull; 
230 Elements[7] = (msb >> 32) & 0x00000000FFFFFFFFull; 
231 ClearUnusedBits(); 
232} 
233 
234 
235template<int N> inline void tBitField<N>::Set(const uint8* src, int len) 
236{ 
237 Clear(); 
238 tAssert(NumElements*4 >= len); 
239 for (int i = len-1; i >= 0; i--) 
240 { 
241 int j = (len-1) - i; 
242 Elements[j/4] |= src[j] << ((j%4)*8); 
243 } 
244 ClearUnusedBits(); 
245} 
246 
247 
248template<int N> inline void tBitField<N>::Set(const uint16* src, int len) 
249{ 
250 Clear(); 
251 tAssert(NumElements*2 >= len); 
252 for (int i = len-1; i >= 0; i--) 
253 { 
254 int j = (len-1) - i; 
255 Elements[j/2] |= src[j] << ((j%2)*16); 
256 } 
257 ClearUnusedBits(); 
258} 
259 
260 
261template<int N> inline void tBitField<N>::Set(const uint32* src, int len) 
262{ 
263 Clear(); 
264 tAssert(NumElements >= len); 
265 for (int i = len-1; i >= 0; i--) 
266 { 
267 int j = (len-1) - i; 
268 Elements[j] = src[j]; 
269 } 
270 ClearUnusedBits(); 
271} 
272 
273 
274template<int N> inline void tBitField<N>::Set(const uint64* src, int len) 
275{ 
276 Clear(); 
277 tAssert(NumElements >= len*2); 
278 for (int i = len-1; i >= 0; i--) 
279 { 
280 int j = (len-1) - i; 
281 Elements[j*2] = src[j] & 0x00000000FFFFFFFFull; 
282 Elements[j*2+1] = (src[j] >> 32) & 0x00000000FFFFFFFFull; 
283 } 
284 ClearUnusedBits(); 
285} 
286 
287 
288template<int N> inline tString tBitField<N>::GetAsString(int base) const 
289{ 
290 tFixIntU< NumElements*32 > val; 
291 tAssert(NumElements == val.GetRawCount()); 
292 for (int i = 0; i < NumElements; i++) 
293 val.RawElement(i) = Elements[i]; 
294 
295 // Worst case for string length required is base 2, where N characters are needed. 
296 tString str(N); 
297 tStd::tItostrT< tFixInt< NumElements*32 > >(val, str.Text(), N+1, base); 
298 return str; 
299} 
300 
301 
302template<int N> inline bool tBitField<N>::GetBit(int n) const 
303{ 
304 tAssert(n < N); 
305 int i = n >> 5; 
306 int d = n & 0x1F; 
307 uint32 mask = 1 << d; 
308 return (Elements[i] & mask) ? true : false; 
309} 
310 
311 
312template<int N> inline void tBitField<N>::SetBit(int n, bool v) 
313{ 
314 tAssert(n < N); 
315 int i = n >> 5; 
316 int d = n & 0x1F; 
317 uint32 mask = 1 << d; 
318 if (v) 
319 Elements[i] |= mask; 
320 else 
321 Elements[i] &= ~mask; 
322} 
323 
324 
325template<int N> inline void tBitField<N>::SetAll(bool v) 
326{ 
327 for (int i = 0; i < NumElements; i++) 
328 Elements[i] = v ? 0xFFFFFFFF : 0x00000000; 
329 
330 if (v) 
331 ClearUnusedBits(); 
332} 
333 
334 
335template<int N> inline void tBitField<N>::InvertAll() 
336{ 
337 for (int i = 0; i < NumElements; i++) 
338 Elements[i] = ~(Elements[i]); 
339 
340 ClearUnusedBits(); 
341} 
342 
343 
344template<int N> inline bool tBitField<N>::AreAll(bool v) const 
345{ 
346 // To test all clear we rely on any extra bits being cleared as well. 
347 if (!v) 
348 { 
349 for (int i = 0; i < NumElements; i++) 
350 if (Elements[i] != 0x00000000) 
351 return false; 
352 return true; 
353 } 
354 
355 for (int i = 0; i < NumElements-1; i++) 
356 if (Elements[i] != 0xFFFFFFFF) 
357 return false; 
358 
359 // The last slot in the array may not be full. 
360 int last = N & 0x1F; 
361 uint32 maxFull = (last ? (1<<last) : 0) - 1; 
362 
363 return (Elements[NumElements-1] == maxFull) ? true : false; 
364} 
365 
366 
367template<int N> inline int tBitField<N>::Count(bool v) const 
368{ 
369 // First compute the total number set. 
370 int numSet = 0; 
371 for (int i = 0; i < NumElements; ++i) 
372 { 
373 uint32 v = Elements[i]; // Count the number of bits set in v. 
374 uint32 c; // c accumulates the total bits set in v. 
375 for (c = 0; v; c++) 
376 v &= v - 1; // Clear the least significant bit set. 
377 numSet += c; 
378 } 
379 
380 // Now numSet is correct. If that's what we were asked, we're done. If not, we just subtract. 
381 if (v) 
382 return numSet; 
383 
384 return N - numSet; 
385} 
386 
387 
388template<int N> inline tBitField<N>& tBitField<N>::operator<<=(int s) 
389{ 
390 // First, if we are shifting by too much, we end up with all zeroes. 
391 tAssert(s >= 0); 
392 if (s >= N) 
393 { 
394 Clear(); 
395 return *this; 
396 } 
397 
398 // Now lets make an uber-set with zeroes to the right. 
399 uint32 uber[NumElements*2]; 
400 for (int i = 0; i < NumElements; i++) 
401 uber[i] = 0x00000000; 
402 
403 for (int i = 0; i < NumElements; i++) 
404 uber[i+NumElements] = Elements[i]; 
405 
406 int bitIndex = NumElements*32; 
407 bitIndex -= s; 
408 
409 // Finally copy the bits over from the new starting position. This might be a bit slow, but it works. 
410 Clear(); 
411 for (int b = 0; b < N; b++, bitIndex++) 
412 { 
413 // Read. 
414 int i = bitIndex >> 5; 
415 int d = bitIndex & 0x1F; 
416 uint32 mask = 1 << d; 
417 bool val = (uber[i] & mask) ? true : false; 
418 
419 // Write. 
420 SetBit(b, val); 
421 } 
422 
423 return *this; 
424} 
425 
426 
427template<int N> inline tBitField<N>& tBitField<N>::operator>>=(int s) 
428{ 
429 // First, if we are shifting by too much, we end up with all zeroes. 
430 tAssert(s >= 0); 
431 if (s >= N) 
432 { 
433 Clear(); 
434 return *this; 
435 } 
436 
437 // Now lets make an uber-set with zeroes to the left. 
438 uint32 uber[NumElements*2]; 
439 for (int i = 0; i < NumElements; i++) 
440 uber[i+NumElements] = 0x00000000; 
441 
442 for (int i = 0; i < NumElements; i++) 
443 uber[i] = Elements[i]; 
444 
445 int bitIndex = 0; 
446 bitIndex += s; 
447 
448 // Finally copy the bits over from the new starting position. This might be a bit slow, but it works. 
449 Clear(); 
450 for (int b = 0; b < N; b++, bitIndex++) 
451 { 
452 // Read. 
453 int i = bitIndex >> 5; 
454 int d = bitIndex & 0x1F; 
455 uint32 mask = 1 << d; 
456 bool val = (uber[i] & mask) ? true : false; 
457 
458 // Write. 
459 SetBit(b, val); 
460 } 
461 
462 return *this; 
463} 
464 
465 
466template<int N> inline bool tBitField<N>::operator==(const tBitField& s) const 
467{ 
468 // Remember, extra bits MUST be set to zero. This allows easy checking of only the array contents. 
469 for (int i = 0; i < NumElements; i++) 
470 if (Elements[i] != s.Elements[i]) 
471 return false; 
472 
473 return true; 
474} 
475 
476 
477template<int N> inline bool tBitField<N>::operator!=(const tBitField& s) const 
478{ 
479 for (int i = 0; i < NumElements; i++) 
480 if (Elements[i] != s.Elements[i]) 
481 return true; 
482 
483 return false; 
484} 
485 
486 
487template<int N> inline tBitField<N>::operator bool() const 
488{ 
489 for (int i = 0; i < NumElements; i++) 
490 if (Elements[i]) 
491 return true; 
492 
493 return false; 
494} 
495 
496 
497template<int N> inline void tBitField<N>::ClearUnusedBits() 
498{ 
499 int r = N%32; 
500 uint32& e = Elements[NumElements-1]; 
501 e &= r ? ~((0xFFFFFFFF >> r) << r) : 0xFFFFFFFF; 
502} 
503