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. If the number of bits you need is known at compile time, consider using a 
6// tBitField instead as it is more feature-complete. 
7// 
8// Copyright (c) 2004-2006, 2015, 2017, 2019 Tristan Grimmer. 
9// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
10// granted, provided that the above copyright notice and this permission notice appear in all copies. 
11// 
12// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
13// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
14// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
15// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
16// PERFORMANCE OF THIS SOFTWARE. 
17 
18#include "Foundation/tBitArray.h" 
19#include "Foundation/tStandard.h" 
20 
21 
22void tBitArray::Set(int numBits) 
23{ 
24 Clear(); 
25 tAssert(numBits > 0); 
26 
27 NumBits = numBits; 
28 int numFields = GetNumFields(); 
29 BitFields = new uint32[numFields]; 
30 tStd::tMemset(BitFields, 0, numFields*sizeof(uint32)); 
31} 
32 
33 
34void tBitArray::Set(const uint32* data, int numBits) 
35{ 
36 Clear(); 
37 tAssert(data && numBits); 
38 
39 NumBits = numBits; 
40 int n = GetNumFields(); 
41 BitFields = new uint32[n]; 
42 tStd::tMemcpy(BitFields, data, n*sizeof(uint32)); 
43 ClearPadBits(); 
44} 
45 
46 
47void tBitArray::Set(const tBitArray& src) 
48{ 
49 if (&src == this) 
50 return; 
51 
52 Clear(); 
53 if (!src.IsValid()) 
54 return; 
55 
56 NumBits = src.NumBits; 
57 int n = src.GetNumFields(); 
58 BitFields = new uint32[n]; 
59 tStd::tMemcpy(BitFields, src.BitFields, n*sizeof(uint32)); 
60} 
61 
62 
63void tBitArray::InvertAll() 
64{ 
65 int n = GetNumFields(); 
66 for (int i = 0; i < n; i++) 
67 BitFields[i] = ~BitFields[i]; 
68 
69 ClearPadBits(); 
70} 
71 
72 
73bool tBitArray::AreAll(bool v) const 
74{ 
75 tAssert(BitFields); 
76 int n = GetNumFields(); 
77 uint32 fullField = v ? 0xFFFFFFFF : 0x00000000; 
78 for (int i = 0; i < n-1; i++) 
79 { 
80 if (BitFields[i] != fullField) 
81 return false; 
82 } 
83 
84 // Deal with the bits in the last field. 
85 int last = NumBits & 0x1F; 
86 uint32 maxFull = (last ? (1 << last) : 0) - 1; 
87 fullField = v ? maxFull : 0x00000000; 
88 return (BitFields[n-1] & maxFull) == fullField; 
89} 
90 
91 
92int tBitArray::CountBits(bool val) const 
93{ 
94 // Uses technique described here "http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan". 
95 // This is one reason the pad bits must always be cleared. 
96 tAssert(BitFields); 
97 int numFields = GetNumFields(); 
98 
99 int count = 0; 
100 for (int n = 0; n < numFields; n++) 
101 { 
102 uint32 v = BitFields[n]; // Count the number of bits set in v. 
103 uint32 c; // c accumulates the total bits set in v. 
104 for (c = 0; v; c++) 
105 v &= v - 1; // Clear the least significant bit set. 
106 count += c; 
107 } 
108  
109 return val ? count : (NumBits - count); 
110} 
111 
112 
113int tBitArray::GetClearedBit(int index) const 
114{ 
115 tAssert(BitFields); 
116 
117 // Find the first zero bit. The operation we do is log2((a xor (a+1)) +1) 
118 uint32 field = BitFields[index]; 
119 
120 // This is guaranteed to be a power of two. 
121 uint32 freeBit = (field ^ (field+1)) + 1; 
122 
123 // Wraps around on the last bit. 
124 if (!freeBit) 
125 return 31; 
126 
127 // Now get the log in base 2 of freeBit. See "http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog". 
128 const uint32 b[] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 }; 
129 uint32 c = (freeBit & b[0]) != 0; 
130 
131 c |= ((freeBit & b[4]) != 0) << 4; 
132 c |= ((freeBit & b[3]) != 0) << 3; 
133 c |= ((freeBit & b[2]) != 0) << 2; 
134 c |= ((freeBit & b[1]) != 0) << 1; 
135 
136 // This is the first cleared index in the bit array. 
137 return c-1; 
138} 
139 
140 
141int tBitArray::GetClearedBitPos() const 
142{ 
143 int n = GetNumFields(); 
144 
145 for (int i = 0; i < n-1; i++) 
146 { 
147 if (BitFields[i] < 0xFFFFFFFF) 
148 return 32*i + GetClearedBit(i); 
149 } 
150 
151 int last = NumBits & 0x1F; 
152 uint32 maxFull = (last ? (1 << last) : 0) - 1; 
153 
154 if (BitFields[n-1] < maxFull) 
155 return 32*(n-1) + GetClearedBit(n-1); 
156 
157 // There are no free bits available. 
158 return -1; 
159} 
160 
161 
162tBitArray& tBitArray::operator&=(const tBitArray& s) 
163{ 
164 tAssert(NumBits == s.NumBits); 
165 int n = GetNumFields(); 
166 for (int i = 0; i < n; i++) 
167 BitFields[i] &= s.BitFields[i]; 
168 
169 return *this; // No need to ensure pad bits are cleared because 0 & 0 = 0. 
170} 
171 
172 
173tBitArray& tBitArray::operator|=(const tBitArray& s) 
174{ 
175 tAssert(NumBits == s.NumBits); 
176 int n = GetNumFields(); 
177 for (int i = 0; i < n; i++) 
178 BitFields[i] |= s.BitFields[i]; 
179 
180 return *this; // No need to ensure pad bits are cleared because 0 | 0 = 0. 
181} 
182 
183 
184tBitArray& tBitArray::operator^=(const tBitArray& s) 
185{ 
186 tAssert(NumBits == s.NumBits); 
187 int n = GetNumFields(); 
188 for (int i = 0; i < n; i++) 
189 BitFields[i] ^= s.BitFields[i]; 
190 
191 return *this; // No need to ensure pad bits are cleared because 0 ^ 0 = 0. 
192} 
193