Branch data Line data Source code
1 : : /******************************************************************************
2 : : * Top contributors (to current version):
3 : : * Aina Niemetz, Liana Hadarean, Christopher L. Conway
4 : : *
5 : : * This file is part of the cvc5 project.
6 : : *
7 : : * Copyright (c) 2009-2024 by the authors listed in the file AUTHORS
8 : : * in the top-level source directory and their institutional affiliations.
9 : : * All rights reserved. See the file COPYING in the top-level source
10 : : * directory for licensing information.
11 : : * ****************************************************************************
12 : : *
13 : : * A fixed-size bit-vector, implemented as a wrapper around Integer.
14 : : */
15 : :
16 : : #include "util/bitvector.h"
17 : :
18 : : #include "base/check.h"
19 : : #include "util/hash.h"
20 : :
21 : : namespace cvc5::internal {
22 : :
23 : 272705 : BitVector::BitVector(const std::string& num, uint32_t base)
24 : : {
25 [ + + ][ + + ]: 272705 : Assert(base == 2 || base == 10 || base == 16);
[ - + ][ - + ]
[ - - ]
26 [ - + ][ - + ]: 272705 : Assert(num[0] != '-');
[ - - ]
27 : 272705 : d_value = Integer(num, base);
28 [ - + ][ - + ]: 272705 : Assert(d_value == d_value.abs());
[ - - ]
29 : : // Compute the length, *without* any negative sign.
30 [ + + ][ + ]: 272705 : switch (base)
31 : : {
32 : 1 : case 10: d_size = d_value.length(); break;
33 : 2 : case 16: d_size = num.size() * 4; break;
34 : 272702 : default: d_size = num.size();
35 : : }
36 : 272705 : }
37 : :
38 : 182271000 : unsigned BitVector::getSize() const { return d_size; }
39 : :
40 : 112125000 : const Integer& BitVector::getValue() const { return d_value; }
41 : :
42 : 71455 : Integer BitVector::toInteger() const { return d_value; }
43 : :
44 : 11389700 : Integer BitVector::toSignedInteger() const
45 : : {
46 : 11389700 : unsigned size = d_size;
47 : 22779400 : Integer sign_bit = d_value.extractBitRange(1, size - 1);
48 : 22779400 : Integer val = d_value.extractBitRange(size - 1, 0);
49 : 22779400 : Integer res = Integer(-1) * sign_bit.multiplyByPow2(size - 1) + val;
50 : 22779400 : return res;
51 : : }
52 : :
53 : 405176 : std::string BitVector::toString(unsigned int base) const
54 : : {
55 : 810352 : std::string str = d_value.toString(base);
56 [ + + ][ + + ]: 405176 : if (base == 2 && d_size > str.size())
[ + + ]
57 : : {
58 : 501058 : std::string zeroes;
59 [ + + ]: 1344820 : for (unsigned int i = 0; i < d_size - str.size(); ++i)
60 : : {
61 : 1094290 : zeroes.append("0");
62 : : }
63 : 250529 : return zeroes + str;
64 : : }
65 : : else
66 : : {
67 : 154647 : return str;
68 : : }
69 : : }
70 : :
71 : 4836640 : size_t BitVector::hash() const
72 : : {
73 : : PairHashFunction<size_t, size_t> h;
74 : 4836640 : return h(std::make_pair(d_value.hash(), d_size));
75 : : }
76 : :
77 : 2319 : BitVector& BitVector::setBit(uint32_t i, bool value)
78 : : {
79 [ - + ][ - + ]: 2319 : Assert(i < d_size);
[ - - ]
80 : 2319 : d_value.setBit(i, value);
81 : 2319 : return *this;
82 : : }
83 : :
84 : 108339 : bool BitVector::isBitSet(uint32_t i) const
85 : : {
86 [ - + ][ - + ]: 108339 : Assert(i < d_size);
[ - - ]
87 : 108339 : return d_value.isBitSet(i);
88 : : }
89 : :
90 : 657633 : unsigned BitVector::isPow2() const
91 : : {
92 : 657633 : return d_value.isPow2();
93 : : }
94 : :
95 : : /* -----------------------------------------------------------------------
96 : : * Operators
97 : : * ----------------------------------------------------------------------- */
98 : :
99 : : /* String Operations ----------------------------------------------------- */
100 : :
101 : 773871 : BitVector BitVector::concat(const BitVector& other) const
102 : : {
103 : 773871 : return BitVector(d_size + other.d_size,
104 : 1547740 : (d_value.multiplyByPow2(other.d_size)) + other.d_value);
105 : : }
106 : :
107 : 2143800 : BitVector BitVector::extract(unsigned high, unsigned low) const
108 : : {
109 [ - + ][ - + ]: 2143800 : Assert(high < d_size);
[ - - ]
110 [ - + ][ - + ]: 2143800 : Assert(low <= high);
[ - - ]
111 : 2143800 : return BitVector(high - low + 1,
112 : 4287610 : d_value.extractBitRange(high - low + 1, low));
113 : : }
114 : :
115 : : /* (Dis)Equality --------------------------------------------------------- */
116 : :
117 : 21477500 : bool operator==(const BitVector& a, const BitVector& b)
118 : : {
119 [ - + ]: 21477500 : if (a.getSize() != b.getSize()) return false;
120 : 21477500 : return a.getValue() == b.getValue();
121 : : }
122 : :
123 : 1032410 : bool operator!=(const BitVector& a, const BitVector& b)
124 : : {
125 [ - + ]: 1032410 : if (a.getSize() != b.getSize()) return true;
126 : 1032410 : return a.getValue() != b.getValue();
127 : : }
128 : :
129 : : /* Unsigned Inequality --------------------------------------------------- */
130 : :
131 : 1263 : bool operator<(const BitVector& a, const BitVector& b)
132 : : {
133 : 1263 : return a.getValue() < b.getValue();
134 : : }
135 : :
136 : 2553 : bool operator<=(const BitVector& a, const BitVector& b)
137 : : {
138 : 2553 : return a.getValue() <= b.getValue();
139 : : }
140 : :
141 : 493 : bool operator>(const BitVector& a, const BitVector& b)
142 : : {
143 : 493 : return a.getValue() > b.getValue();
144 : : }
145 : :
146 : 993 : bool operator>=(const BitVector& a, const BitVector& b)
147 : : {
148 : 993 : return a.getValue() >= b.getValue();
149 : : }
150 : :
151 : 156429 : bool BitVector::unsignedLessThan(const BitVector& y) const
152 : : {
153 [ - + ][ - + ]: 156429 : Assert(d_size == y.d_size);
[ - - ]
154 [ - + ][ - + ]: 156429 : Assert(d_value >= 0);
[ - - ]
155 [ - + ][ - + ]: 156429 : Assert(y.d_value >= 0);
[ - - ]
156 : 156429 : return d_value < y.d_value;
157 : : }
158 : :
159 : 40403 : bool BitVector::unsignedLessThanEq(const BitVector& y) const
160 : : {
161 [ - + ][ - + ]: 40403 : Assert(d_size == y.d_size);
[ - - ]
162 [ - + ][ - + ]: 40403 : Assert(d_value >= 0);
[ - - ]
163 [ - + ][ - + ]: 40403 : Assert(y.d_value >= 0);
[ - - ]
164 : 40403 : return d_value <= y.d_value;
165 : : }
166 : :
167 : : /* Signed Inequality ----------------------------------------------------- */
168 : :
169 : 241313 : bool BitVector::signedLessThan(const BitVector& y) const
170 : : {
171 [ - + ][ - + ]: 241313 : Assert(d_size == y.d_size);
[ - - ]
172 [ - + ][ - + ]: 241313 : Assert(d_value >= 0);
[ - - ]
173 [ - + ][ - + ]: 241313 : Assert(y.d_value >= 0);
[ - - ]
174 : 482626 : Integer a = (*this).toSignedInteger();
175 : 482626 : Integer b = y.toSignedInteger();
176 : :
177 : 482626 : return a < b;
178 : : }
179 : :
180 : 5453520 : bool BitVector::signedLessThanEq(const BitVector& y) const
181 : : {
182 [ - + ][ - + ]: 5453520 : Assert(d_size == y.d_size);
[ - - ]
183 [ - + ][ - + ]: 5453520 : Assert(d_value >= 0);
[ - - ]
184 [ - + ][ - + ]: 5453520 : Assert(y.d_value >= 0);
[ - - ]
185 : 10907000 : Integer a = (*this).toSignedInteger();
186 : 10907000 : Integer b = y.toSignedInteger();
187 : :
188 : 10907000 : return a <= b;
189 : : }
190 : :
191 : : /* Bit-wise operations --------------------------------------------------- */
192 : :
193 : 3409 : BitVector operator^(const BitVector& a, const BitVector& b)
194 : : {
195 [ - + ][ - + ]: 3409 : Assert(a.getSize() == b.getSize());
[ - - ]
196 : 6818 : return BitVector(a.getSize(), a.getValue().bitwiseXor(b.getValue()));
197 : : }
198 : :
199 : 509939 : BitVector operator|(const BitVector& a, const BitVector& b)
200 : : {
201 [ - + ][ - + ]: 509939 : Assert(a.getSize() == b.getSize());
[ - - ]
202 : 1019880 : return BitVector(a.getSize(), a.getValue().bitwiseOr(b.getValue()));
203 : : }
204 : :
205 : 1724950 : BitVector operator&(const BitVector& a, const BitVector& b)
206 : : {
207 [ - + ][ - + ]: 1724950 : Assert(a.getSize() == b.getSize());
[ - - ]
208 : 3449900 : return BitVector(a.getSize(), a.getValue().bitwiseAnd(b.getValue()));
209 : : }
210 : :
211 : 14579100 : BitVector operator~(const BitVector& a)
212 : : {
213 : 29158300 : return BitVector(a.getSize(), a.getValue().bitwiseNot());
214 : : }
215 : :
216 : : /* Arithmetic operations ------------------------------------------------- */
217 : :
218 : 23365600 : BitVector operator+(const BitVector& a, const BitVector& b)
219 : : {
220 [ - + ][ - + ]: 23365600 : Assert(a.getSize() == b.getSize());
[ - - ]
221 : 46731100 : Integer sum = a.getValue() + b.getValue();
222 : 46731100 : return BitVector(a.getSize(), sum);
223 : : }
224 : :
225 : 9234110 : BitVector operator-(const BitVector& a, const BitVector& b)
226 : : {
227 [ - + ][ - + ]: 9234110 : Assert(a.getSize() == b.getSize());
[ - - ]
228 : : // to maintain the invariant that we are only adding BitVectors of the
229 : : // same size
230 : 9234110 : BitVector one(a.getSize(), Integer(1));
231 : 27702300 : return a + ~b + one;
232 : : }
233 : :
234 : 4417800 : BitVector operator-(const BitVector& a)
235 : : {
236 : 4417800 : BitVector one(a.getSize(), Integer(1));
237 : 13253400 : return ~a + one;
238 : : }
239 : :
240 : 490668 : BitVector operator*(const BitVector& a, const BitVector& b)
241 : : {
242 [ - + ][ - + ]: 490668 : Assert(a.getSize() == b.getSize());
[ - - ]
243 : 981336 : Integer prod = a.getValue() * b.getValue();
244 : 981336 : return BitVector(a.getSize(), prod);
245 : : }
246 : :
247 : 68991 : BitVector BitVector::unsignedDivTotal(const BitVector& y) const
248 : : {
249 [ - + ][ - + ]: 68991 : Assert(d_size == y.d_size);
[ - - ]
250 : : /* d_value / 0 = -1 = 2^d_size - 1 */
251 [ + + ]: 68991 : if (y.d_value == 0)
252 : : {
253 : 16126 : return BitVector(d_size, Integer(1).oneExtend(1, d_size - 1));
254 : : }
255 [ - + ][ - + ]: 60928 : Assert(d_value >= 0);
[ - - ]
256 [ - + ][ - + ]: 60928 : Assert(y.d_value > 0);
[ - - ]
257 : 121856 : return BitVector(d_size, d_value.floorDivideQuotient(y.d_value));
258 : : }
259 : :
260 : 73964 : BitVector BitVector::unsignedRemTotal(const BitVector& y) const
261 : : {
262 [ - + ][ - + ]: 73964 : Assert(d_size == y.d_size);
[ - - ]
263 [ + + ]: 73964 : if (y.d_value == 0)
264 : : {
265 : 8104 : return BitVector(d_size, d_value);
266 : : }
267 [ - + ][ - + ]: 65860 : Assert(d_value >= 0);
[ - - ]
268 [ - + ][ - + ]: 65860 : Assert(y.d_value > 0);
[ - - ]
269 : 131720 : return BitVector(d_size, d_value.floorDivideRemainder(y.d_value));
270 : : }
271 : :
272 : : /* Extend operations ----------------------------------------------------- */
273 : :
274 : 1896810 : BitVector BitVector::zeroExtend(unsigned n) const
275 : : {
276 : 1896810 : return BitVector(d_size + n, d_value);
277 : : }
278 : :
279 : 1693190 : BitVector BitVector::signExtend(unsigned n) const
280 : : {
281 : 3386380 : Integer sign_bit = d_value.extractBitRange(1, d_size - 1);
282 [ + + ]: 1693190 : if (sign_bit == Integer(0))
283 : : {
284 : 277179 : return BitVector(d_size + n, d_value);
285 : : }
286 : 2832020 : Integer val = d_value.oneExtend(d_size, n);
287 : 1416010 : return BitVector(d_size + n, val);
288 : : }
289 : :
290 : : /* Shift operations ------------------------------------------------------ */
291 : :
292 : 7484620 : BitVector BitVector::leftShift(const BitVector& y) const
293 : : {
294 [ + + ]: 7484620 : if (y.d_value > Integer(d_size))
295 : : {
296 : 74732 : return BitVector(d_size, Integer(0));
297 : : }
298 [ + + ]: 7447250 : if (y.d_value == 0)
299 : : {
300 : 604488 : return *this;
301 : : }
302 : : // making sure we don't lose information casting
303 [ - + ][ - + ]: 6842770 : Assert(y.d_value < Integer(1).multiplyByPow2(32));
[ - - ]
304 : 6842770 : uint32_t amount = y.d_value.toUnsignedInt();
305 : 13685500 : Integer res = d_value.multiplyByPow2(amount);
306 : 6842770 : return BitVector(d_size, res);
307 : : }
308 : :
309 : 169671 : BitVector BitVector::logicalRightShift(const BitVector& y) const
310 : : {
311 [ + + ]: 169671 : if (y.d_value > Integer(d_size))
312 : : {
313 : 2 : return BitVector(d_size, Integer(0));
314 : : }
315 : : // making sure we don't lose information casting
316 [ - + ][ - + ]: 169670 : Assert(y.d_value < Integer(1).multiplyByPow2(32));
[ - - ]
317 : 169670 : uint32_t amount = y.d_value.toUnsignedInt();
318 : 339340 : Integer res = d_value.divByPow2(amount);
319 : 169670 : return BitVector(d_size, res);
320 : : }
321 : :
322 : 60343 : BitVector BitVector::arithRightShift(const BitVector& y) const
323 : : {
324 : 120686 : Integer sign_bit = d_value.extractBitRange(1, d_size - 1);
325 [ + + ]: 60343 : if (y.d_value > Integer(d_size))
326 : : {
327 [ + + ]: 2224 : if (sign_bit == Integer(0))
328 : : {
329 : 2378 : return BitVector(d_size, Integer(0));
330 : : }
331 : : else
332 : : {
333 : 2070 : return BitVector(d_size, Integer(d_size).multiplyByPow2(d_size) - 1);
334 : : }
335 : : }
336 : :
337 [ + + ]: 58119 : if (y.d_value == 0)
338 : : {
339 : 1675 : return *this;
340 : : }
341 : :
342 : : // making sure we don't lose information casting
343 [ - + ][ - + ]: 56444 : Assert(y.d_value < Integer(1).multiplyByPow2(32));
[ - - ]
344 : :
345 : 56444 : uint32_t amount = y.d_value.toUnsignedInt();
346 : 112888 : Integer rest = d_value.divByPow2(amount);
347 : :
348 [ + + ]: 56444 : if (sign_bit == Integer(0))
349 : : {
350 : 39033 : return BitVector(d_size, rest);
351 : : }
352 : 34822 : Integer res = rest.oneExtend(d_size - amount, amount);
353 : 17411 : return BitVector(d_size, res);
354 : : }
355 : :
356 : : /* -----------------------------------------------------------------------
357 : : * Static helpers.
358 : : * ----------------------------------------------------------------------- */
359 : :
360 : 41 : BitVector BitVector::mkZero(unsigned size)
361 : : {
362 [ - + ][ - + ]: 41 : Assert(size > 0);
[ - - ]
363 : 41 : return BitVector(size);
364 : : }
365 : :
366 : 939 : BitVector BitVector::mkOne(unsigned size)
367 : : {
368 [ - + ][ - + ]: 939 : Assert(size > 0);
[ - - ]
369 : 939 : return BitVector(size, 1u);
370 : : }
371 : :
372 : 1068170 : BitVector BitVector::mkOnes(unsigned size)
373 : : {
374 [ - + ][ - + ]: 1068170 : Assert(size > 0);
[ - - ]
375 : 2136330 : return BitVector(1, Integer(1)).signExtend(size - 1);
376 : : }
377 : :
378 : 123 : BitVector BitVector::mkMinSigned(unsigned size)
379 : : {
380 [ - + ][ - + ]: 123 : Assert(size > 0);
[ - - ]
381 : 123 : BitVector res(size);
382 : 123 : res.setBit(size - 1, true);
383 : 123 : return res;
384 : : }
385 : :
386 : 40 : BitVector BitVector::mkMaxSigned(unsigned size)
387 : : {
388 [ - + ][ - + ]: 40 : Assert(size > 0);
[ - - ]
389 : 80 : return ~BitVector::mkMinSigned(size);
390 : : }
391 : :
392 : : } // namespace cvc5::internal
|
