1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5/***************************************************************************/
6/* BitVector.cpp */
7/***************************************************************************/
8// Routines to support a growable bitvector
9/***************************************************************************/
10
11#include "stdafx.h"
12#include <memory.h>
13
14#include "utilcode.h"
15
16#include "bitvector.h"
17
18#if USE_BITVECTOR
19
20int BitVector::NumBits() const
21{
22 CONTRACTL {
23 NOTHROW;
24 GC_NOTRIGGER;
25 SUPPORTS_DAC;
26 } CONTRACTL_END;
27
28 int count = 0;
29 ChunkType hiChunk;
30
31 if (isBig())
32 {
33 unsigned maxNonZero = 0;
34 for (unsigned i=1; (i < m_vals.GetLength()); i++)
35 {
36 if (m_vals.m_chunks[i] != 0)
37 {
38 maxNonZero = i;
39 }
40 }
41 count = (maxNonZero * CHUNK_BITS) - 1;
42 hiChunk = m_vals.m_chunks[maxNonZero];
43 }
44 else
45 {
46 hiChunk = m_val;
47 }
48
49 while (hiChunk > 0)
50 {
51 hiChunk <<= 1;
52 count++;
53 }
54
55 _ASSERTE(count >= 0);
56 return count;
57}
58
59void BitVector::doBigInit(ChunkType arg)
60{
61 WRAPPER_NO_CONTRACT;
62 SUPPORTS_DAC;
63
64 m_vals.m_chunks[0] = arg;
65 m_vals.SetLength(1);
66}
67
68void BitVector::doBigInit(const BitVector& arg)
69{
70 WRAPPER_NO_CONTRACT;
71 SUPPORTS_DAC;
72
73 if (arg.isBig())
74 {
75 memcpy(m_vals.m_chunks, arg.m_vals.m_chunks, (sizeof(ChunkType) * arg.m_vals.GetLength()));
76 m_vals.SetLength(arg.m_vals.GetLength());
77 }
78 else
79 {
80 m_val = arg.m_val;
81 }
82}
83
84void BitVector::doBigLeftShiftAssign(unsigned shift)
85{
86 CONTRACTL {
87 NOTHROW;
88 GC_NOTRIGGER;
89 SUPPORTS_DAC;
90 } CONTRACTL_END;
91
92 if ((m_val == 0) || (shift == 0)) // Zero is a special case, don't need to do anything
93 return;
94
95 unsigned numWords = shift / CHUNK_BITS;
96 unsigned numBits = shift % CHUNK_BITS;
97
98 //
99 // Change to Big representation
100 //
101 toBig();
102
103 int from = m_vals.GetLength()-1;
104 int to = from + numWords;
105 unsigned newlen = to + 1;
106
107 ChunkType topBits = 0;
108 if (numBits > 0)
109 {
110 topBits = m_vals.m_chunks[from] >> (CHUNK_BITS - numBits);
111 }
112
113 if (topBits != 0 || numWords != 0)
114 {
115 if (topBits != 0)
116 {
117 m_vals.m_chunks[newlen] = topBits;
118 newlen++;
119 }
120 m_vals.SetLength(newlen);
121 }
122
123 while (to >= 0)
124 {
125 m_vals.m_chunks[to] = (from >= 0) ? (m_vals.m_chunks[from] << numBits) : 0;
126 from--;
127
128 if ((from >= 0) && (numBits > 0))
129 {
130 m_vals.m_chunks[to] |= m_vals.m_chunks[from] >> (CHUNK_BITS - numBits);
131 }
132 to--;
133 }
134
135 // Convert back to small format if necessary
136 if ((newlen == 1) && (m_vals.m_chunks[0] <= MaxVal))
137 {
138 m_val = ChunkType(m_vals.m_chunks[0] << 1);
139 }
140}
141
142void BitVector::doBigRightShiftAssign(unsigned shift)
143{
144 CONTRACTL {
145 NOTHROW;
146 GC_NOTRIGGER;
147 SUPPORTS_DAC;
148 } CONTRACTL_END;
149
150 if ((m_val == 0) || (shift == 0)) // Zero is a special case, don't need to do anything
151 return;
152
153 unsigned numWords = shift / CHUNK_BITS;
154 unsigned numBits = shift % CHUNK_BITS;
155
156 //
157 // Change to Big representation
158 //
159 toBig();
160
161 unsigned from = numWords;
162 unsigned to = 0;
163 unsigned len = m_vals.GetLength();
164 unsigned newlen = len - numWords;
165
166 if (from >= len)
167 {
168 // we always encode zero in short form
169 m_val = 0;
170 }
171 else
172 {
173 m_vals.m_chunks[to] = (m_vals.m_chunks[from] >> numBits);
174 from++;
175
176 while (from < len)
177 {
178 if (numBits > 0)
179 {
180 m_vals.m_chunks[to] |= m_vals.m_chunks[from] << (CHUNK_BITS - numBits);
181 }
182 to++;
183
184 m_vals.m_chunks[to] = (m_vals.m_chunks[from] >> numBits);
185 from++;
186 }
187
188 if ((newlen > 1) && (m_vals.m_chunks[newlen-1] == 0))
189 {
190 newlen--;
191 }
192
193 m_vals.SetLength(newlen);
194
195 // Convert back to small format if necessary
196 if ((newlen == 1) && (m_vals.m_chunks[0] <= MaxVal))
197 {
198 m_val = ChunkType(m_vals.m_chunks[0] << 1);
199 }
200 }
201}
202
203void BitVector::doBigAndAssign(const BitVector& arg)
204{
205 CONTRACTL {
206 NOTHROW;
207 GC_NOTRIGGER;
208 SUPPORTS_DAC;
209 } CONTRACTL_END;
210
211 //
212 // Change to Big representation
213 //
214 toBig();
215
216 if (arg.isBig())
217 {
218 bool isZero = true; // until proven otherwise
219 unsigned myLen = m_vals.GetLength();
220 unsigned argLen = arg.m_vals.GetLength();
221
222 if (myLen > argLen)
223 {
224 // shrink our length to match argLen
225 m_vals.SetLength(argLen);
226 myLen = argLen;
227 }
228
229 for (unsigned i = 0; (i < myLen); i++)
230 {
231 ChunkType curChunk = m_vals.m_chunks[i] & arg.m_vals.m_chunks[i];
232 m_vals.m_chunks[i] = curChunk;
233 if (curChunk != 0)
234 isZero = false;
235 }
236
237 if (isZero)
238 {
239 // we always encode zero in short form
240 m_val = 0;
241 }
242 }
243 else
244 {
245 m_val = (m_vals.m_chunks[0] << 1) & arg.m_val;
246 }
247}
248
249void BitVector::doBigOrAssign(const BitVector& arg)
250{
251 CONTRACTL {
252 NOTHROW;
253 GC_NOTRIGGER;
254 SUPPORTS_DAC;
255 } CONTRACTL_END;
256
257 //
258 // Change to Big representation
259 //
260 toBig();
261
262 if (arg.isBig())
263 {
264 unsigned myLen = m_vals.GetLength();
265 unsigned argLen = arg.m_vals.GetLength();
266
267 if (myLen < argLen)
268 {
269 // expand our length to match argLen and zero init
270 memset(m_vals.m_chunks + myLen, 0, sizeof(ChunkType) * (argLen - myLen));
271 m_vals.SetLength(argLen);
272 myLen = argLen;
273 }
274
275 for(unsigned i = 0; ((i < myLen) && (i < argLen)); i++)
276 {
277 m_vals.m_chunks[i] |= arg.m_vals.m_chunks[i];
278 }
279 }
280 else
281 {
282 m_vals.m_chunks[0] |= arg.smallBits();
283 }
284}
285
286void BitVector::doBigDiffAssign(const BitVector& arg)
287{
288 CONTRACTL {
289 NOTHROW;
290 GC_NOTRIGGER;
291 SUPPORTS_DAC;
292 } CONTRACTL_END;
293
294 //
295 // Change to Big representation
296 //
297 toBig();
298
299 unsigned myLen = m_vals.GetLength();
300 unsigned argLen = arg.m_vals.GetLength();
301 bool isZero = true; // until proven otherwise
302
303 for (unsigned i = 0; (i < myLen); i++)
304 {
305 ChunkType nextChunk = m_vals.m_chunks[i];
306 if (i < argLen)
307 {
308 nextChunk &= ~arg.m_vals.m_chunks[i];
309 m_vals.m_chunks[i] = nextChunk;
310 }
311 else if (i == 0)
312 {
313 nextChunk &= ~arg.smallBits();
314 m_vals.m_chunks[i] = nextChunk;
315 }
316
317 if (nextChunk != 0)
318 isZero = false;
319 }
320
321 if (isZero)
322 {
323 // we always encode zero in short form
324 m_val = 0;
325 }
326}
327
328BOOL BitVector::doBigEquals(const BitVector& arg) const
329{
330 CONTRACT(BOOL)
331 {
332 NOTHROW;
333 GC_NOTRIGGER;
334 SUPPORTS_DAC;
335 }
336 CONTRACT_END;
337
338 unsigned myLen = m_vals.GetLength();
339 unsigned argLen = arg.m_vals.GetLength();
340 unsigned maxLen = (myLen >= argLen) ? myLen : argLen;
341
342 for (unsigned i=0; (i < maxLen); i++)
343 {
344 ChunkType myVal = 0;
345 ChunkType argVal = 0;
346
347 if (i < myLen)
348 myVal = m_vals.m_chunks[i];
349
350 if (i < argLen)
351 argVal = arg.m_vals.m_chunks[i];
352
353 if (i == 0)
354 {
355 if (myLen == 0)
356 myVal = smallBits();
357 if (argLen == 0)
358 argVal = arg.smallBits();
359 }
360
361 if (myVal != argVal)
362 RETURN false;
363 }
364 RETURN true;
365}
366
367BOOL BitVector::doBigIntersect(const BitVector& arg) const
368{
369 CONTRACT(BOOL)
370 {
371 NOTHROW;
372 GC_NOTRIGGER;
373 SUPPORTS_DAC;
374 }
375 CONTRACT_END;
376
377 unsigned myLen = m_vals.GetLength();
378 unsigned argLen = arg.m_vals.GetLength();
379 unsigned minLen = (myLen <= argLen) ? myLen : argLen;
380
381 for (unsigned i=0; (i <= minLen); i++)
382 {
383 ChunkType myVal = 0;
384 ChunkType argVal = 0;
385
386 if (i < myLen)
387 myVal = m_vals.m_chunks[i];
388
389 if (i < argLen)
390 argVal = arg.m_vals.m_chunks[i];
391
392 if (i == 0)
393 {
394 if (myLen == 0)
395 myVal = smallBits();
396 if (argLen == 0)
397 argVal = arg.smallBits();
398 }
399
400 if ((myVal & argVal) != 0)
401 RETURN true;
402 }
403 RETURN false;
404}
405
406#endif // USE_BITVECTOR
407