1// tBitArray.cpp 
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#include "Foundation/tBitArray.h" 
29#include "Foundation/tStandard.h" 
30#include "Foundation/tFundamentals.h" 
31 
32 
33void tBitArray::Set(int numBits) 
34{ 
35 Clear(); 
36 tAssert(numBits > 0); 
37 
38 NumBits = numBits; 
39 int n = GetNumElements(); 
40 ElemData = new uint32[n]; 
41 tStd::tMemset(dest: ElemData, val: 0, numBytes: n*sizeof(uint32)); 
42} 
43 
44 
45void tBitArray::Set(uint32* data, int numBits, bool external) 
46{ 
47 Clear(); 
48 tAssert(data && numBits); 
49 
50 ExternalData = external; 
51 NumBits = numBits; 
52 int n = GetNumElements(); 
53 
54 if (external) 
55 { 
56 ElemData = data; 
57 } 
58 else 
59 { 
60 ElemData = new uint32[n]; 
61 tStd::tMemcpy(dest: ElemData, src: data, numBytes: n*sizeof(uint32)); 
62 } 
63 ClearPadBits(); 
64} 
65 
66 
67void tBitArray::Set(const tBitArray& src) 
68{ 
69 if (&src == this) 
70 return; 
71 
72 Clear(); 
73 if (!src.IsValid()) 
74 return; 
75 
76 NumBits = src.NumBits; 
77 int n = src.GetNumElements(); 
78 ElemData = new uint32[n]; 
79 tStd::tMemcpy(dest: ElemData, src: src.ElemData, numBytes: n*sizeof(uint32)); 
80} 
81 
82 
83bool tBitArray::AreAll(bool v) const 
84{ 
85 tAssert(ElemData); 
86 int n = GetNumElements(); 
87 uint32 fullField = v ? 0xFFFFFFFF : 0x00000000; 
88 for (int i = 0; i < n-1; i++) 
89 if (ElemData[i] != fullField) 
90 return false; 
91 
92 // Deal with the bits in the last field. 
93 int last = NumBits & 0x1F; 
94 uint32 maxFull = (last ? (1 << last) : 0) - 1; 
95 fullField = v ? maxFull : 0x00000000; 
96 return (ElemData[n-1] & maxFull) == fullField; 
97} 
98 
99 
100int tBitArray::CountBits(bool val) const 
101{ 
102 // Uses technique described here "http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan". 
103 // This is one reason the pad bits must always be cleared. 
104 tAssert(ElemData); 
105 int numFields = GetNumElements(); 
106 
107 int count = 0; 
108 for (int n = 0; n < numFields; n++) 
109 { 
110 uint32 v = ElemData[n]; // Count the number of bits set in v. 
111 uint32 c; // c accumulates the total bits set in v. 
112 for (c = 0; v; c++) 
113 v &= v - 1; // Clear the least significant bit set. 
114 count += c; 
115 } 
116  
117 return val ? count : (NumBits - count); 
118} 
119 
120 
121int tBitArray::FindFirstClearBit() const 
122{ 
123 int n = GetNumElements(); 
124 int index = -1; 
125 for (int i = 0; i < n; i++) 
126 { 
127 uint32 elem = ElemData[i]; 
128 if (elem != 0xFFFFFFFF) 
129 { 
130 index = 32*i + tMath::tFindFirstClearBit(v: elem); 
131 break; 
132 } 
133 } 
134 
135 // If the zero was found in the padding bits, it doesn't count. 
136 if (index >= NumBits) 
137 return -1; 
138 
139 return index; 
140} 
141 
142 
143// 
144// tBitArray8. 
145// 
146void tBitArray8::Set(int numBits) 
147{ 
148 Clear(); 
149 tAssert(numBits > 0); 
150 
151 NumBits = numBits; 
152 int n = GetNumElements(); 
153 ElemData = new uint8[n]; 
154 tStd::tMemset(dest: ElemData, val: 0, numBytes: n); 
155} 
156 
157 
158void tBitArray8::Set(uint8* data, int numBits, bool external) 
159{ 
160 Clear(); 
161 tAssert(data && numBits); 
162 NumBits = numBits; 
163 ExternalData = external; 
164 int n = GetNumElements(); 
165 if (external) 
166 { 
167 ElemData = data; 
168 } 
169 else 
170 { 
171 ElemData = new uint8[n]; 
172 tStd::tMemcpy(dest: ElemData, src: data, numBytes: n); 
173 } 
174 ClearPadBits(); 
175} 
176 
177 
178void tBitArray8::Set(const tBitArray8& src) 
179{ 
180 if (&src == this) 
181 return; 
182 
183 Clear(); 
184 if (!src.IsValid()) 
185 return; 
186 
187 NumBits = src.NumBits; 
188 int n = src.GetNumElements(); 
189 ElemData = new uint8[n]; 
190 tStd::tMemcpy(dest: ElemData, src: src.ElemData, numBytes: n); 
191} 
192 
193 
194bool tBitArray8::AreAll(bool v) const 
195{ 
196 tAssert(ElemData); 
197 int n = GetNumElements(); 
198 uint8 fullField = v ? 0xFF : 0x00; 
199 for (int i = 0; i < n-1; i++) 
200 if (ElemData[i] != fullField) 
201 return false; 
202 
203 // Deal with the bits in the last field. 
204 int last = NumBits & 0x07; 
205 if (!last) 
206 return true; 
207 
208 uint8 maxFull = ((1 << last) - 1) << (8-last); 
209 fullField = v ? maxFull : 0x00; 
210 return (ElemData[n-1] & maxFull) == fullField; 
211} 
212 
213 
214int tBitArray8::CountBits(bool val) const 
215{ 
216 // Uses technique described here "http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan". 
217 // This is one reason the pad bits must always be cleared. 
218 tAssert(ElemData); 
219 int numFields = GetNumElements(); 
220 
221 int count = 0; 
222 for (int n = 0; n < numFields; n++) 
223 { 
224 uint8 v = ElemData[n]; // Count the number of bits set in v. 
225 uint8 c; // c accumulates the total bits set in v. 
226 for (c = 0; v; c++) 
227 v &= v - 1; // Clear the least significant bit set. 
228 count += c; 
229 } 
230  
231 return val ? count : (NumBits - count); 
232} 
233 
234 
235int tBitArray8::FindFirstClearBit() const 
236{ 
237 int n = GetNumElements(); 
238 int index = -1; 
239 for (int i = 0; i < n; i++) 
240 { 
241 uint8 elem = ElemData[i]; 
242 if (elem != 0xFF) 
243 { 
244 tMath::tiReverseBits(v&: elem); 
245 index = 8*i + tMath::tFindFirstClearBit(v: elem); 
246 break; 
247 } 
248 } 
249 
250 // If the zero was found in the padding bits, it doesn't count. 
251 if (index >= NumBits) 
252 return -1; 
253 
254 return index; 
255} 
256