1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2019-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 #pragma once
10
11 namespace iSTD
12 {
13
14 /******************************************************************************\
15
16 CStaticBitSet provides standard bitset operations when the bitset size is
17 known at compile time. The number of bits supported is up to the template
18 parameter MaxBits. This gets rounded up to the next DWORD aligned value.
19 The API is the similar to iSTD::CBitSet, but this class will not grow if you
20 access an index higher than what is allocated. Instead, this class will
21 provided a nice blue screen to alert you of the error. It is the client's
22 responsibility to do any bounds checking.
23
24 Bits indices start at 0. For a CStaticBitSet< 32 >, the size is 32 and the
25 valid range of indicies is 0 through 31.
26
27 Constructor - Initializes all bits to off.
28 Clear - Turns all bits to off.
29 SetAll - Turns all bits to on.
30
31 Set - Turns one or more bits on.
32 Unset - Turns one bit off.
33 IsSet - Returns true if a bit is on, false otherwise.
34
35 \******************************************************************************/
36 template< DWORD MaxBits >
37 class CStaticBitSet
38 {
39 public:
40 CStaticBitSet( void );
41
42 void Clear( void );
43 void SetAll( void );
44
45 void Set( const DWORD index );
46 void Set( const DWORD index, const DWORD count );
47
48 void UnSet( const DWORD index );
49 bool IsSet( const DWORD index ) const;
50
51 DWORD BitCount() const;
52 DWORD BitCount( DWORD limit ) const;
53
54 protected:
55 enum { ArraySize = (MaxBits + sizeof(DWORD)*8 - 1 ) >> 5 };
56
GetArrayIndex(const DWORD bitNum)57 DWORD GetArrayIndex( const DWORD bitNum ) const { return bitNum >> 5; }
GetBitIndex(const DWORD bitNum)58 DWORD GetBitIndex( const DWORD bitNum ) const { return bitNum & 0x1F; }
BitNumber(const DWORD number)59 DWORD BitNumber( const DWORD number ) const { return 1 << number; }
60
61 DWORD m_bits[ ArraySize ];
62 #ifdef _DEBUG
63 bool m_debugBits[ MaxBits ];
64 #endif
65 };
66
67 /******************************************************************************\
68 CStaticBitSet
69 \******************************************************************************/
70 template< DWORD MaxBits >
CStaticBitSet(void)71 CStaticBitSet< MaxBits >::CStaticBitSet( void )
72 {
73 C_ASSERT( MaxBits >= 1 );
74 Clear();
75 }
76
77 /******************************************************************************\
78 CStaticBitSet::Clear
79 \******************************************************************************/
80 template< DWORD MaxBits >
Clear(void)81 void CStaticBitSet< MaxBits >::Clear( void )
82 {
83 SafeMemSet( &m_bits, 0, sizeof( m_bits[ 0 ] ) * ArraySize );
84
85 #ifdef _DEBUG
86 for( DWORD ndx = 0; ndx < MaxBits; ndx++ )
87 {
88 m_debugBits[ ndx ] = false;
89 }
90 #endif
91 }
92
93 /******************************************************************************\
94 CStaticBitSet::SetAll
95 \******************************************************************************/
96 template< DWORD MaxBits >
SetAll(void)97 void CStaticBitSet< MaxBits >::SetAll( void )
98 {
99 SafeMemSet( &m_bits, 0xFF, sizeof( m_bits[ 0 ] ) * ArraySize );
100
101 #ifdef _DEBUG
102 for( DWORD ndx = 0; ndx < MaxBits; ndx++ )
103 {
104 m_debugBits[ ndx ] = true;
105 }
106 #endif
107 }
108
109 /******************************************************************************\
110 CStaticBitSet::Set
111 \******************************************************************************/
112 template< DWORD MaxBits >
Set(const DWORD index)113 void CStaticBitSet< MaxBits >::Set( const DWORD index )
114 {
115 #ifdef _DEBUG
116 ASSERT( IsSet( index ) == m_debugBits[ index ] );
117 #endif
118 ASSERT( GetArrayIndex( index ) <= ArraySize );
119
120 DWORD arrayIndex = GetArrayIndex( index );
121 DWORD bitIndex = GetBitIndex( index );
122
123 m_bits[ arrayIndex ] |= BitNumber( bitIndex );
124
125 #ifdef _DEBUG
126 m_debugBits[ index ] = true;
127 #endif
128 }
129
130 /******************************************************************************\
131
132 CStaticBitSet::Set (contiguous version) - Sets a contiguous number of bits
133 that could span multiple DWORDS. Optimized towards setting a contiguous
134 amount of bits that span many DWORDS.
135
136 This algorithm takes advantage of the property that if you set a contiguous
137 set of bits that span multiple DWORDs, all the DWORDs between the first
138 and last bits can be set to 0xFFFFFFFF. There is not need to calculate
139 which bits need to be set. Only the bits in the first and last DWORDs
140 need to be calculated.
141
142 Notes: This function is specifically coded for m_bits to be DWORDs.
143 If you change the m_bits type, you will need to change this function.
144
145 \******************************************************************************/
146 template< DWORD MaxBits >
Set(const DWORD index,DWORD count)147 void CStaticBitSet< MaxBits >::Set( const DWORD index, DWORD count )
148 {
149 ASSERT( GetArrayIndex( index ) <= ArraySize );
150
151 #ifdef _DEBUG
152 for( DWORD ndx = 0; ndx < count; ndx++)
153 {
154 m_debugBits[ index + ndx ] = true;
155 }
156 #endif
157
158 DWORD arrayIndex = GetArrayIndex( index );
159 DWORD bitIndex = GetBitIndex( index );
160 DWORD mask;
161
162 const DWORD BITS_PER_ELEMENT = 32;
163
164 if( ( bitIndex + count ) <= BITS_PER_ELEMENT ) // Spans only a single DWORD
165 {
166 // Promote to QWORD due to bug when shifting 0x1 by 32 becomes 0x1
167 // instead of our desired 0x0. Seems like it is a rotate shift.
168 mask = (((QWORD)1 << count ) - 1 ) << bitIndex;
169 m_bits[ arrayIndex ] |= mask;
170 }
171 else
172 {
173 // Set the bits in the first DWORD
174 mask = (DWORD) (QWORD) ( ( (DWORD) -1 ) << bitIndex ) ;
175 m_bits[ arrayIndex ] |= mask ;
176 arrayIndex++;
177 count = count - ( BITS_PER_ELEMENT - bitIndex );
178
179 // Set the bits in the middle DWORDs
180 while( count >= BITS_PER_ELEMENT )
181 {
182 m_bits[ arrayIndex ] = 0xFFFFFFFF;
183 arrayIndex++;
184 count -= BITS_PER_ELEMENT;
185 }
186 // Set the bits in the last DWORD
187 mask = ( (QWORD)1 << count ) - 1;
188 m_bits[ arrayIndex ] |= mask;
189 }
190
191 #ifdef _DEBUG
192 for( DWORD ndx = 0; ndx < MaxBits; ndx++)
193 {
194 ASSERT( m_debugBits[ ndx ] == IsSet( ndx ) );
195 }
196 #endif
197 }
198
199 /******************************************************************************\
200 CStaticBitSet::UnSet
201 \******************************************************************************/
202 template< DWORD MaxBits >
UnSet(const DWORD index)203 void CStaticBitSet< MaxBits >::UnSet( const DWORD index )
204 {
205 #ifdef _DEBUG
206 ASSERT( IsSet( index ) == m_debugBits[ index ] );
207 #endif
208 ASSERT( GetArrayIndex( index ) <= ArraySize );
209
210 DWORD arrayIndex = GetArrayIndex( index );
211 DWORD bitIndex = GetBitIndex( index );
212 m_bits[ arrayIndex ] &= ~BitNumber( bitIndex );
213
214 #ifdef _DEBUG
215 m_debugBits[ index ] = false;
216 #endif
217 }
218
219 /******************************************************************************\
220 CStaticBitSet::IsSet
221 \******************************************************************************/
222 template< DWORD MaxBits >
IsSet(const DWORD index)223 bool CStaticBitSet< MaxBits >::IsSet( const DWORD index ) const
224 {
225 ASSERT( GetArrayIndex( index ) <= ArraySize );
226
227 DWORD arrayIndex = GetArrayIndex( index );
228 DWORD bitIndex = GetBitIndex( index );
229
230 bool isSet = ( m_bits[ arrayIndex ] & BitNumber( bitIndex ) ) ? true : false;
231
232 #ifdef _DEBUG
233 ASSERT( isSet == m_debugBits[ index ] );
234 #endif
235 return isSet;
236 }
237
238 /******************************************************************************\
239 CStaticBitSet::BitCount
240 \******************************************************************************/
241 template< DWORD MaxBits >
BitCount()242 DWORD CStaticBitSet< MaxBits >::BitCount() const
243 {
244 DWORD bitCount = 0;
245
246 const DWORD cBitsPerArrayElement = sizeof(m_bits[0]) * 8;
247
248 DWORD index = ArraySize;
249
250 while( index-- )
251 {
252 if( m_bits[ index ] != 0 )
253 {
254 for( DWORD i = 0; i < cBitsPerArrayElement; i++ )
255 {
256 if( m_bits[index] & (1<<i) )
257 {
258 bitCount++;
259 }
260 }
261 }
262 }
263
264 return bitCount;
265 }
266
267
268 /******************************************************************************\
269 CStaticBitSet::BitCount
270 \******************************************************************************/
271 template< DWORD MaxBits >
BitCount(DWORD limit)272 DWORD CStaticBitSet< MaxBits >::BitCount(DWORD limit) const
273 {
274 DWORD bitCount = 0;
275
276 limit = iSTD::Min<DWORD>( limit, ArraySize-1 );
277
278 for( DWORD i=0; i <= limit; i++ )
279 {
280 if( IsSet( i ) )
281 {
282 bitCount++;
283 }
284 }
285
286 return bitCount;
287 }
288
289 }
290