1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Liana Hadarean, Aina Niemetz, Tim King |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 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 |
|
* Implementation of bitblasting functions for various operators. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "cvc5_private.h" |
17 |
|
|
18 |
|
#ifndef CVC5__THEORY__BV__BITBLAST__BITBLAST_STRATEGIES_TEMPLATE_H |
19 |
|
#define CVC5__THEORY__BV__BITBLAST__BITBLAST_STRATEGIES_TEMPLATE_H |
20 |
|
|
21 |
|
#include <cmath> |
22 |
|
#include <ostream> |
23 |
|
|
24 |
|
#include "expr/node.h" |
25 |
|
#include "theory/bv/bitblast/bitblast_utils.h" |
26 |
|
#include "theory/bv/theory_bv_utils.h" |
27 |
|
#include "util/bitvector.h" |
28 |
|
|
29 |
|
namespace cvc5 { |
30 |
|
|
31 |
|
namespace theory { |
32 |
|
namespace bv { |
33 |
|
|
34 |
|
/** |
35 |
|
* Default Atom Bitblasting strategies: |
36 |
|
* |
37 |
|
* @param node the atom to be bitblasted |
38 |
|
* @param bb the bitblaster |
39 |
|
*/ |
40 |
|
|
41 |
|
template <class T> |
42 |
|
T UndefinedAtomBBStrategy(TNode node, TBitblaster<T>* bb) { |
43 |
|
Debug("bitvector") << "TheoryBV::Bitblaster Undefined bitblasting strategy for kind: " |
44 |
|
<< node.getKind() << "\n"; |
45 |
|
Unreachable(); |
46 |
|
} |
47 |
|
|
48 |
|
|
49 |
|
template <class T> |
50 |
40028 |
T DefaultEqBB(TNode node, TBitblaster<T>* bb) { |
51 |
40028 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
52 |
|
|
53 |
40028 |
Assert(node.getKind() == kind::EQUAL); |
54 |
80056 |
std::vector<T> lhs, rhs; |
55 |
40028 |
bb->bbTerm(node[0], lhs); |
56 |
40028 |
bb->bbTerm(node[1], rhs); |
57 |
|
|
58 |
40028 |
Assert(lhs.size() == rhs.size()); |
59 |
|
|
60 |
80056 |
std::vector<T> bits_eq; |
61 |
479671 |
for (unsigned i = 0; i < lhs.size(); i++) { |
62 |
879286 |
T bit_eq = mkIff(lhs[i], rhs[i]); |
63 |
439643 |
bits_eq.push_back(bit_eq); |
64 |
|
} |
65 |
40028 |
T bv_eq = mkAnd(bits_eq); |
66 |
80056 |
return bv_eq; |
67 |
|
} |
68 |
|
|
69 |
|
template <class T> |
70 |
|
T AdderUltBB(TNode node, TBitblaster<T>* bb) { |
71 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
72 |
|
Assert(node.getKind() == kind::BITVECTOR_ULT); |
73 |
|
std::vector<T> a, b; |
74 |
|
bb->bbTerm(node[0], a); |
75 |
|
bb->bbTerm(node[1], b); |
76 |
|
Assert(a.size() == b.size()); |
77 |
|
|
78 |
|
// a < b <=> ~ (add(a, ~b, 1).carry_out) |
79 |
|
std::vector<T> not_b; |
80 |
|
negateBits(b, not_b); |
81 |
|
T carry = mkTrue<T>(); |
82 |
|
|
83 |
|
for (unsigned i = 0 ; i < a.size(); ++i) { |
84 |
|
carry = mkOr( mkAnd(a[i], not_b[i]), |
85 |
|
mkAnd( mkXor(a[i], not_b[i]), |
86 |
|
carry)); |
87 |
|
} |
88 |
|
return mkNot(carry); |
89 |
|
} |
90 |
|
|
91 |
|
|
92 |
|
template <class T> |
93 |
6613 |
T DefaultUltBB(TNode node, TBitblaster<T>* bb) { |
94 |
6613 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
95 |
6613 |
Assert(node.getKind() == kind::BITVECTOR_ULT); |
96 |
13226 |
std::vector<T> a, b; |
97 |
6613 |
bb->bbTerm(node[0], a); |
98 |
6613 |
bb->bbTerm(node[1], b); |
99 |
6613 |
Assert(a.size() == b.size()); |
100 |
|
|
101 |
|
// construct bitwise comparison |
102 |
6613 |
T res = uLessThanBB(a, b, false); |
103 |
13226 |
return res; |
104 |
|
} |
105 |
|
|
106 |
|
template <class T> |
107 |
|
T DefaultUleBB(TNode node, TBitblaster<T>* bb){ |
108 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
109 |
|
Assert(node.getKind() == kind::BITVECTOR_ULE); |
110 |
|
std::vector<T> a, b; |
111 |
|
|
112 |
|
bb->bbTerm(node[0], a); |
113 |
|
bb->bbTerm(node[1], b); |
114 |
|
Assert(a.size() == b.size()); |
115 |
|
// construct bitwise comparison |
116 |
|
T res = uLessThanBB(a, b, true); |
117 |
|
return res; |
118 |
|
} |
119 |
|
|
120 |
|
template <class T> |
121 |
|
T DefaultUgtBB(TNode node, TBitblaster<T>* bb){ |
122 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
123 |
|
// should be rewritten |
124 |
|
Unimplemented(); |
125 |
|
} |
126 |
|
template <class T> |
127 |
|
T DefaultUgeBB(TNode node, TBitblaster<T>* bb){ |
128 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
129 |
|
// should be rewritten |
130 |
|
Unimplemented(); |
131 |
|
} |
132 |
|
|
133 |
|
template <class T> |
134 |
6730 |
T DefaultSltBB(TNode node, TBitblaster<T>* bb){ |
135 |
6730 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
136 |
|
|
137 |
13460 |
std::vector<T> a, b; |
138 |
6730 |
bb->bbTerm(node[0], a); |
139 |
6730 |
bb->bbTerm(node[1], b); |
140 |
6730 |
Assert(a.size() == b.size()); |
141 |
|
|
142 |
6730 |
T res = sLessThanBB(a, b, false); |
143 |
13460 |
return res; |
144 |
|
} |
145 |
|
|
146 |
|
template <class T> |
147 |
|
T DefaultSleBB(TNode node, TBitblaster<T>* bb){ |
148 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
149 |
|
|
150 |
|
std::vector<T> a, b; |
151 |
|
bb->bbTerm(node[0], a); |
152 |
|
bb->bbTerm(node[1], b); |
153 |
|
Assert(a.size() == b.size()); |
154 |
|
|
155 |
|
T res = sLessThanBB(a, b, true); |
156 |
|
return res; |
157 |
|
} |
158 |
|
|
159 |
|
template <class T> |
160 |
|
T DefaultSgtBB(TNode node, TBitblaster<T>* bb){ |
161 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
162 |
|
// should be rewritten |
163 |
|
Unimplemented(); |
164 |
|
} |
165 |
|
|
166 |
|
template <class T> |
167 |
|
T DefaultSgeBB(TNode node, TBitblaster<T>* bb){ |
168 |
|
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
169 |
|
// should be rewritten |
170 |
|
Unimplemented(); |
171 |
|
} |
172 |
|
|
173 |
|
|
174 |
|
/// Term bitblasting strategies |
175 |
|
|
176 |
|
/** |
177 |
|
* Default Term Bitblasting strategies |
178 |
|
* |
179 |
|
* @param node the term to be bitblasted |
180 |
|
* @param bits [output parameter] bits representing the new term |
181 |
|
* @param bb the bitblaster in which the clauses are added |
182 |
|
*/ |
183 |
|
template <class T> |
184 |
|
void UndefinedTermBBStrategy(TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
185 |
|
Debug("bitvector") << "theory::bv:: Undefined bitblasting strategy for kind: " |
186 |
|
<< node.getKind() << "\n"; |
187 |
|
Unreachable(); |
188 |
|
} |
189 |
|
|
190 |
|
template <class T> |
191 |
19990 |
void DefaultVarBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
192 |
19990 |
Assert(bits.size() == 0); |
193 |
19990 |
bb->makeVariable(node, bits); |
194 |
|
|
195 |
19990 |
if(Debug.isOn("bitvector-bb")) { |
196 |
|
Debug("bitvector-bb") << "theory::bv::DefaultVarBB bitblasting " << node << "\n"; |
197 |
|
Debug("bitvector-bb") << " with bits " << toString(bits); |
198 |
|
} |
199 |
19990 |
} |
200 |
|
|
201 |
|
template <class T> |
202 |
15628 |
void DefaultConstBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
203 |
15628 |
Debug("bitvector-bb") << "theory::bv::DefaultConstBB bitblasting " << node << "\n"; |
204 |
15628 |
Assert(node.getKind() == kind::CONST_BITVECTOR); |
205 |
15628 |
Assert(bits.size() == 0); |
206 |
|
|
207 |
193112 |
for (unsigned i = 0; i < utils::getSize(node); ++i) { |
208 |
354968 |
Integer bit = node.getConst<BitVector>().extract(i, i).getValue(); |
209 |
177484 |
if(bit == Integer(0)){ |
210 |
119028 |
bits.push_back(mkFalse<T>()); |
211 |
|
} else { |
212 |
58456 |
Assert(bit == Integer(1)); |
213 |
58456 |
bits.push_back(mkTrue<T>()); |
214 |
|
} |
215 |
|
} |
216 |
15628 |
if(Debug.isOn("bitvector-bb")) { |
217 |
|
Debug("bitvector-bb") << "with bits: " << toString(bits) << "\n"; |
218 |
|
} |
219 |
15628 |
} |
220 |
|
|
221 |
|
|
222 |
|
template <class T> |
223 |
5629 |
void DefaultNotBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
224 |
5629 |
Debug("bitvector-bb") << "theory::bv::DefaultNotBB bitblasting " << node << "\n"; |
225 |
5629 |
Assert(node.getKind() == kind::BITVECTOR_NOT); |
226 |
5629 |
Assert(bits.size() == 0); |
227 |
11258 |
std::vector<T> bv; |
228 |
5629 |
bb->bbTerm(node[0], bv); |
229 |
5629 |
negateBits(bv, bits); |
230 |
5629 |
} |
231 |
|
|
232 |
|
template <class T> |
233 |
9452 |
void DefaultConcatBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
234 |
9452 |
Debug("bitvector-bb") << "theory::bv::DefaultConcatBB bitblasting " << node << "\n"; |
235 |
9452 |
Assert(bits.size() == 0); |
236 |
|
|
237 |
9452 |
Assert(node.getKind() == kind::BITVECTOR_CONCAT); |
238 |
35353 |
for (int i = node.getNumChildren() -1 ; i >= 0; --i ) { |
239 |
51802 |
TNode current = node[i]; |
240 |
51802 |
std::vector<T> current_bits; |
241 |
25901 |
bb->bbTerm(current, current_bits); |
242 |
|
|
243 |
154978 |
for(unsigned j = 0; j < utils::getSize(current); ++j) { |
244 |
129077 |
bits.push_back(current_bits[j]); |
245 |
|
} |
246 |
|
} |
247 |
9452 |
Assert(bits.size() == utils::getSize(node)); |
248 |
9452 |
if(Debug.isOn("bitvector-bb")) { |
249 |
|
Debug("bitvector-bb") << "with bits: " << toString(bits) << "\n"; |
250 |
|
} |
251 |
9452 |
} |
252 |
|
|
253 |
|
template <class T> |
254 |
5099 |
void DefaultAndBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
255 |
5099 |
Debug("bitvector-bb") << "theory::bv::DefaultAndBB bitblasting " << node << "\n"; |
256 |
|
|
257 |
5099 |
Assert(node.getKind() == kind::BITVECTOR_AND && bits.size() == 0); |
258 |
|
|
259 |
5099 |
bb->bbTerm(node[0], bits); |
260 |
10198 |
std::vector<T> current; |
261 |
14190 |
for(unsigned j = 1; j < node.getNumChildren(); ++j) { |
262 |
9091 |
bb->bbTerm(node[j], current); |
263 |
29043 |
for (unsigned i = 0; i < utils::getSize(node); ++i) { |
264 |
19952 |
bits[i] = mkAnd(bits[i], current[i]); |
265 |
|
} |
266 |
9091 |
current.clear(); |
267 |
|
} |
268 |
5099 |
Assert(bits.size() == utils::getSize(node)); |
269 |
5099 |
} |
270 |
|
|
271 |
|
template <class T> |
272 |
6989 |
void DefaultOrBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
273 |
6989 |
Debug("bitvector-bb") << "theory::bv::DefaultOrBB bitblasting " << node << "\n"; |
274 |
|
|
275 |
6989 |
Assert(node.getKind() == kind::BITVECTOR_OR && bits.size() == 0); |
276 |
|
|
277 |
6989 |
bb->bbTerm(node[0], bits); |
278 |
13978 |
std::vector<T> current; |
279 |
74144 |
for(unsigned j = 1; j < node.getNumChildren(); ++j) { |
280 |
67155 |
bb->bbTerm(node[j], current); |
281 |
138034 |
for (unsigned i = 0; i < utils::getSize(node); ++i) { |
282 |
70879 |
bits[i] = mkOr(bits[i], current[i]); |
283 |
|
} |
284 |
67155 |
current.clear(); |
285 |
|
} |
286 |
6989 |
Assert(bits.size() == utils::getSize(node)); |
287 |
6989 |
} |
288 |
|
|
289 |
|
template <class T> |
290 |
520 |
void DefaultXorBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
291 |
520 |
Debug("bitvector-bb") << "theory::bv::DefaultXorBB bitblasting " << node << "\n"; |
292 |
|
|
293 |
520 |
Assert(node.getKind() == kind::BITVECTOR_XOR && bits.size() == 0); |
294 |
|
|
295 |
520 |
bb->bbTerm(node[0], bits); |
296 |
1040 |
std::vector<T> current; |
297 |
1047 |
for(unsigned j = 1; j < node.getNumChildren(); ++j) { |
298 |
527 |
bb->bbTerm(node[j], current); |
299 |
2867 |
for (unsigned i = 0; i < utils::getSize(node); ++i) { |
300 |
2340 |
bits[i] = mkXor(bits[i], current[i]); |
301 |
|
} |
302 |
527 |
current.clear(); |
303 |
|
} |
304 |
520 |
Assert(bits.size() == utils::getSize(node)); |
305 |
520 |
} |
306 |
|
|
307 |
|
template <class T> |
308 |
|
void DefaultXnorBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
309 |
|
Debug("bitvector-bb") << "theory::bv::DefaultXnorBB bitblasting " << node << "\n"; |
310 |
|
|
311 |
|
Assert(node.getNumChildren() == 2 && node.getKind() == kind::BITVECTOR_XNOR |
312 |
|
&& bits.size() == 0); |
313 |
|
std::vector<T> lhs, rhs; |
314 |
|
bb->bbTerm(node[0], lhs); |
315 |
|
bb->bbTerm(node[1], rhs); |
316 |
|
Assert(lhs.size() == rhs.size()); |
317 |
|
|
318 |
|
for (unsigned i = 0; i < lhs.size(); ++i) { |
319 |
|
bits.push_back(mkIff(lhs[i], rhs[i])); |
320 |
|
} |
321 |
|
} |
322 |
|
|
323 |
|
|
324 |
|
template <class T> |
325 |
|
void DefaultNandBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
326 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
327 |
|
<< node.getKind() << "\n"; |
328 |
|
Unimplemented(); |
329 |
|
} |
330 |
|
template <class T> |
331 |
|
void DefaultNorBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
332 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
333 |
|
<< node.getKind() << "\n"; |
334 |
|
Unimplemented(); |
335 |
|
} |
336 |
|
template <class T> |
337 |
8095 |
void DefaultCompBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
338 |
8095 |
Debug("bitvector") << "theory::bv:: DefaultCompBB bitblasting "<< node << "\n"; |
339 |
|
|
340 |
8095 |
Assert(utils::getSize(node) == 1 && bits.size() == 0 |
341 |
|
&& node.getKind() == kind::BITVECTOR_COMP); |
342 |
16190 |
std::vector<T> a, b; |
343 |
8095 |
bb->bbTerm(node[0], a); |
344 |
8095 |
bb->bbTerm(node[1], b); |
345 |
|
|
346 |
16190 |
std::vector<T> bit_eqs; |
347 |
87166 |
for (unsigned i = 0; i < a.size(); ++i) { |
348 |
158142 |
T eq = mkIff(a[i], b[i]); |
349 |
79071 |
bit_eqs.push_back(eq); |
350 |
|
} |
351 |
16190 |
T a_eq_b = mkAnd(bit_eqs); |
352 |
8095 |
bits.push_back(a_eq_b); |
353 |
8095 |
} |
354 |
|
|
355 |
|
template <class T> |
356 |
1209 |
void DefaultMultBB (TNode node, std::vector<T>& res, TBitblaster<T>* bb) { |
357 |
1209 |
Debug("bitvector") << "theory::bv:: DefaultMultBB bitblasting "<< node << "\n"; |
358 |
1209 |
Assert(res.size() == 0 && node.getKind() == kind::BITVECTOR_MULT); |
359 |
|
|
360 |
|
// if (node.getNumChildren() == 2) { |
361 |
|
// std::vector<T> a; |
362 |
|
// std::vector<T> b; |
363 |
|
// bb->bbTerm(node[0], a); |
364 |
|
// bb->bbTerm(node[1], b); |
365 |
|
// unsigned bw = utils::getSize(node); |
366 |
|
// unsigned thresh = bw % 2 ? bw/2 : bw/2 - 1; |
367 |
|
// bool no_overflow = true; |
368 |
|
// for (unsigned i = thresh; i < bw; ++i) { |
369 |
|
// if (a[i] != mkFalse<T> || b[i] != mkFalse<T> ) { |
370 |
|
// no_overflow = false; |
371 |
|
// } |
372 |
|
// } |
373 |
|
// if (no_overflow) { |
374 |
|
// shiftAddMultiplier(); |
375 |
|
// return; |
376 |
|
// } |
377 |
|
|
378 |
|
// } |
379 |
|
|
380 |
2418 |
std::vector<T> newres; |
381 |
1209 |
bb->bbTerm(node[0], res); |
382 |
2454 |
for(unsigned i = 1; i < node.getNumChildren(); ++i) { |
383 |
2490 |
std::vector<T> current; |
384 |
1245 |
bb->bbTerm(node[i], current); |
385 |
1245 |
newres.clear(); |
386 |
|
// constructs a simple shift and add multiplier building the result |
387 |
|
// in res |
388 |
1245 |
shiftAddMultiplier(res, current, newres); |
389 |
1245 |
res = newres; |
390 |
|
} |
391 |
1209 |
if(Debug.isOn("bitvector-bb")) { |
392 |
|
Debug("bitvector-bb") << "with bits: " << toString(res) << "\n"; |
393 |
|
} |
394 |
1209 |
} |
395 |
|
|
396 |
|
template <class T> |
397 |
2928 |
void DefaultAddBB(TNode node, std::vector<T>& res, TBitblaster<T>* bb) |
398 |
|
{ |
399 |
2928 |
Debug("bitvector-bb") << "theory::bv::DefaultAddBB bitblasting " << node |
400 |
|
<< "\n"; |
401 |
2928 |
Assert(node.getKind() == kind::BITVECTOR_ADD && res.size() == 0); |
402 |
|
|
403 |
2928 |
bb->bbTerm(node[0], res); |
404 |
|
|
405 |
5856 |
std::vector<T> newres; |
406 |
|
|
407 |
6021 |
for(unsigned i = 1; i < node.getNumChildren(); ++i) { |
408 |
6186 |
std::vector<T> current; |
409 |
3093 |
bb->bbTerm(node[i], current); |
410 |
3093 |
newres.clear(); |
411 |
3093 |
rippleCarryAdder(res, current, newres, mkFalse<T>()); |
412 |
3093 |
res = newres; |
413 |
|
} |
414 |
|
|
415 |
2928 |
Assert(res.size() == utils::getSize(node)); |
416 |
2928 |
} |
417 |
|
|
418 |
|
template <class T> |
419 |
|
void DefaultSubBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
420 |
|
Debug("bitvector-bb") << "theory::bv::DefaultSubBB bitblasting " << node << "\n"; |
421 |
|
Assert(node.getKind() == kind::BITVECTOR_SUB && node.getNumChildren() == 2 |
422 |
|
&& bits.size() == 0); |
423 |
|
|
424 |
|
std::vector<T> a, b; |
425 |
|
bb->bbTerm(node[0], a); |
426 |
|
bb->bbTerm(node[1], b); |
427 |
|
Assert(a.size() == b.size() && utils::getSize(node) == a.size()); |
428 |
|
|
429 |
|
// bvsub a b = adder(a, ~b, 1) |
430 |
|
std::vector<T> not_b; |
431 |
|
negateBits(b, not_b); |
432 |
|
rippleCarryAdder(a, not_b, bits, mkTrue<T>()); |
433 |
|
} |
434 |
|
|
435 |
|
template <class T> |
436 |
1568 |
void DefaultNegBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
437 |
1568 |
Debug("bitvector-bb") << "theory::bv::DefaultNegBB bitblasting " << node << "\n"; |
438 |
1568 |
Assert(node.getKind() == kind::BITVECTOR_NEG); |
439 |
|
|
440 |
3136 |
std::vector<T> a; |
441 |
1568 |
bb->bbTerm(node[0], a); |
442 |
1568 |
Assert(utils::getSize(node) == a.size()); |
443 |
|
|
444 |
|
// -a = add(~a, 0, 1). |
445 |
3136 |
std::vector<T> not_a; |
446 |
1568 |
negateBits(a, not_a); |
447 |
3136 |
std::vector<T> zero; |
448 |
1568 |
makeZero(zero, utils::getSize(node)); |
449 |
|
|
450 |
1568 |
rippleCarryAdder(not_a, zero, bits, mkTrue<T>()); |
451 |
1568 |
} |
452 |
|
|
453 |
|
template <class T> |
454 |
5560 |
void uDivModRec(const std::vector<T>& a, const std::vector<T>& b, std::vector<T>& q, std::vector<T>& r, unsigned rec_width) { |
455 |
5560 |
Assert(q.size() == 0 && r.size() == 0); |
456 |
|
|
457 |
5560 |
if(rec_width == 0 || isZero(a)) { |
458 |
711 |
makeZero(q, a.size()); |
459 |
711 |
makeZero(r, a.size()); |
460 |
711 |
return; |
461 |
|
} |
462 |
|
|
463 |
9698 |
std::vector<T> q1, r1; |
464 |
9698 |
std::vector<T> a1 = a; |
465 |
4849 |
rshift(a1, 1); |
466 |
|
|
467 |
4849 |
uDivModRec(a1, b, q1, r1, rec_width - 1); |
468 |
|
// shift the quotient and remainder (i.e. multiply by two) and add 1 to remainder if a is odd |
469 |
4849 |
lshift(q1, 1); |
470 |
4849 |
lshift(r1, 1); |
471 |
|
|
472 |
|
|
473 |
9698 |
T is_odd = mkIff(a[0], mkTrue<T>()); |
474 |
9698 |
T one_if_odd = mkIte(is_odd, mkTrue<T>(), mkFalse<T>()); |
475 |
|
|
476 |
9698 |
std::vector<T> zero; |
477 |
4849 |
makeZero(zero, b.size()); |
478 |
|
|
479 |
9698 |
std::vector<T> r1_shift_add; |
480 |
|
// account for a being odd |
481 |
4849 |
rippleCarryAdder(r1, zero, r1_shift_add, one_if_odd); |
482 |
|
// now check if the remainder is greater than b |
483 |
9698 |
std::vector<T> not_b; |
484 |
4849 |
negateBits(b, not_b); |
485 |
9698 |
std::vector<T> r_minus_b; |
486 |
9698 |
T co1; |
487 |
|
// use adder because we need r_minus_b anyway |
488 |
4849 |
co1 = rippleCarryAdder(r1_shift_add, not_b, r_minus_b, mkTrue<T>()); |
489 |
|
// sign is true if r1 < b |
490 |
9698 |
T sign = mkNot(co1); |
491 |
|
|
492 |
4849 |
q1[0] = mkIte(sign, q1[0], mkTrue<T>()); |
493 |
|
|
494 |
|
// would be nice to have a high level ITE instead of bitwise |
495 |
76028 |
for(unsigned i = 0; i < a.size(); ++i) { |
496 |
71179 |
r1_shift_add[i] = mkIte(sign, r1_shift_add[i], r_minus_b[i]); |
497 |
|
} |
498 |
|
|
499 |
|
// check if a < b |
500 |
|
|
501 |
9698 |
std::vector<T> a_minus_b; |
502 |
9698 |
T co2 = rippleCarryAdder(a, not_b, a_minus_b, mkTrue<T>()); |
503 |
|
// Node a_lt_b = a_minus_b.back(); |
504 |
9698 |
T a_lt_b = mkNot(co2); |
505 |
|
|
506 |
76028 |
for(unsigned i = 0; i < a.size(); ++i) { |
507 |
142358 |
T qval = mkIte(a_lt_b, mkFalse<T>(), q1[i]); |
508 |
142358 |
T rval = mkIte(a_lt_b, a[i], r1_shift_add[i]); |
509 |
71179 |
q.push_back(qval); |
510 |
71179 |
r.push_back(rval); |
511 |
|
} |
512 |
|
|
513 |
|
} |
514 |
|
|
515 |
|
template <class T> |
516 |
711 |
void UdivUremBB(TNode node, |
517 |
|
std::vector<T>& quot, |
518 |
|
std::vector<T>& rem, |
519 |
|
TBitblaster<T>* bb) |
520 |
|
{ |
521 |
711 |
Debug("bitvector-bb") << "theory::bv::DefaultUdivBB bitblasting " << node |
522 |
|
<< "\n"; |
523 |
711 |
Assert(quot.empty()); |
524 |
711 |
Assert(rem.empty()); |
525 |
711 |
Assert(node.getKind() == kind::BITVECTOR_UDIV |
526 |
|
|| node.getKind() == kind::BITVECTOR_UREM); |
527 |
|
|
528 |
1422 |
std::vector<T> a, b; |
529 |
711 |
bb->bbTerm(node[0], a); |
530 |
711 |
bb->bbTerm(node[1], b); |
531 |
|
|
532 |
711 |
uDivModRec(a, b, quot, rem, utils::getSize(node)); |
533 |
|
// adding a special case for division by 0 |
534 |
1422 |
std::vector<T> iszero; |
535 |
6218 |
for (size_t i = 0, size = b.size(); i < size; ++i) |
536 |
|
{ |
537 |
5507 |
iszero.push_back(mkIff(b[i], mkFalse<T>())); |
538 |
|
} |
539 |
1422 |
T b_is_0 = mkAnd(iszero); |
540 |
|
|
541 |
6218 |
for (size_t i = 0, size = quot.size(); i < size; ++i) |
542 |
|
{ |
543 |
5507 |
quot[i] = mkIte(b_is_0, mkTrue<T>(), quot[i]); // a udiv 0 is 11..11 |
544 |
5507 |
rem[i] = mkIte(b_is_0, a[i], rem[i]); // a urem 0 is a |
545 |
|
} |
546 |
711 |
} |
547 |
|
|
548 |
|
template <class T> |
549 |
400 |
void DefaultUdivBB(TNode node, std::vector<T>& quot, TBitblaster<T>* bb) |
550 |
|
{ |
551 |
400 |
Debug("bitvector-bb") << "theory::bv::DefaultUdivBB bitblasting " << node |
552 |
|
<< "\n"; |
553 |
400 |
Assert(quot.empty()); |
554 |
400 |
Assert(node.getKind() == kind::BITVECTOR_UDIV); |
555 |
|
|
556 |
800 |
std::vector<T> r; |
557 |
400 |
UdivUremBB(node, quot, r, bb); |
558 |
400 |
} |
559 |
|
|
560 |
|
template <class T> |
561 |
311 |
void DefaultUremBB(TNode node, std::vector<T>& rem, TBitblaster<T>* bb) |
562 |
|
{ |
563 |
311 |
Debug("bitvector-bb") << "theory::bv::DefaultUremBB bitblasting " << node |
564 |
|
<< "\n"; |
565 |
311 |
Assert(rem.empty()); |
566 |
311 |
Assert(node.getKind() == kind::BITVECTOR_UREM); |
567 |
|
|
568 |
622 |
std::vector<T> q; |
569 |
311 |
UdivUremBB(node, q, rem, bb); |
570 |
311 |
} |
571 |
|
|
572 |
|
template <class T> |
573 |
|
void DefaultSdivBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
574 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
575 |
|
<< node.getKind() << "\n"; |
576 |
|
Unimplemented(); |
577 |
|
} |
578 |
|
template <class T> |
579 |
|
void DefaultSremBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
580 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
581 |
|
<< node.getKind() << "\n"; |
582 |
|
Unimplemented(); |
583 |
|
} |
584 |
|
template <class T> |
585 |
|
void DefaultSmodBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
586 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
587 |
|
<< node.getKind() << "\n"; |
588 |
|
Unimplemented(); |
589 |
|
} |
590 |
|
|
591 |
|
template <class T> |
592 |
704 |
void DefaultShlBB(TNode node, std::vector<T>& res, TBitblaster<T>* bb) |
593 |
|
{ |
594 |
704 |
Debug("bitvector-bb") << "theory::bv::DefaultShlBB bitblasting " << node |
595 |
|
<< "\n"; |
596 |
704 |
Assert(node.getKind() == kind::BITVECTOR_SHL && res.size() == 0); |
597 |
1408 |
std::vector<T> a, b; |
598 |
704 |
bb->bbTerm(node[0], a); |
599 |
704 |
bb->bbTerm(node[1], b); |
600 |
|
|
601 |
|
// check for b < log2(n) |
602 |
704 |
unsigned size = utils::getSize(node); |
603 |
704 |
unsigned log2_size = std::ceil(log2((double)size)); |
604 |
1408 |
Node a_size = utils::mkConst(size, size); |
605 |
|
|
606 |
1408 |
std::vector<T> a_size_bits; |
607 |
704 |
DefaultConstBB(a_size, a_size_bits, bb); |
608 |
1408 |
T b_ult_a_size = uLessThanBB(b, a_size_bits, false); |
609 |
|
|
610 |
1408 |
std::vector<T> prev_res; |
611 |
704 |
res = a; |
612 |
|
// we only need to look at the bits bellow log2_a_size |
613 |
2321 |
for (unsigned s = 0; s < log2_size; ++s) |
614 |
|
{ |
615 |
|
// barrel shift stage: at each stage you can either shift by 2^s bits |
616 |
|
// or leave the previous stage untouched |
617 |
1617 |
prev_res = res; |
618 |
1617 |
unsigned threshold = pow(2, s); |
619 |
15915 |
for (unsigned i = 0; i < a.size(); ++i) |
620 |
|
{ |
621 |
14298 |
if (i < threshold) |
622 |
|
{ |
623 |
|
// if b[s] is true then we must have shifted by at least 2^b bits so |
624 |
|
// all bits bellow 2^s will be 0, otherwise just use previous shift |
625 |
|
// value |
626 |
4347 |
res[i] = mkIte(b[s], mkFalse<T>(), prev_res[i]); |
627 |
|
} |
628 |
|
else |
629 |
|
{ |
630 |
|
// if b[s]= 0, use previous value, otherwise shift by threshold bits |
631 |
9951 |
Assert(i >= threshold); |
632 |
9951 |
res[i] = mkIte(b[s], prev_res[i - threshold], prev_res[i]); |
633 |
|
} |
634 |
|
} |
635 |
|
} |
636 |
704 |
prev_res = res; |
637 |
5041 |
for (unsigned i = 0; i < b.size(); ++i) |
638 |
|
{ |
639 |
|
// this is fine because b_ult_a_size has been bit-blasted |
640 |
4337 |
res[i] = mkIte(b_ult_a_size, prev_res[i], mkFalse<T>()); |
641 |
|
} |
642 |
|
|
643 |
704 |
if (Debug.isOn("bitvector-bb")) |
644 |
|
{ |
645 |
|
Debug("bitvector-bb") << "with bits: " << toString(res) << "\n"; |
646 |
|
} |
647 |
704 |
} |
648 |
|
|
649 |
|
template <class T> |
650 |
861 |
void DefaultLshrBB(TNode node, std::vector<T>& res, TBitblaster<T>* bb) |
651 |
|
{ |
652 |
861 |
Debug("bitvector-bb") << "theory::bv::DefaultLshrBB bitblasting " << node |
653 |
|
<< "\n"; |
654 |
861 |
Assert(node.getKind() == kind::BITVECTOR_LSHR && res.size() == 0); |
655 |
1722 |
std::vector<T> a, b; |
656 |
861 |
bb->bbTerm(node[0], a); |
657 |
861 |
bb->bbTerm(node[1], b); |
658 |
|
|
659 |
|
// check for b < log2(n) |
660 |
861 |
unsigned size = utils::getSize(node); |
661 |
861 |
unsigned log2_size = std::ceil(log2((double)size)); |
662 |
1722 |
Node a_size = utils::mkConst(size, size); |
663 |
|
|
664 |
1722 |
std::vector<T> a_size_bits; |
665 |
861 |
DefaultConstBB(a_size, a_size_bits, bb); |
666 |
1722 |
T b_ult_a_size = uLessThanBB(b, a_size_bits, false); |
667 |
|
|
668 |
861 |
res = a; |
669 |
1722 |
std::vector<T> prev_res; |
670 |
|
|
671 |
2952 |
for (unsigned s = 0; s < log2_size; ++s) |
672 |
|
{ |
673 |
|
// barrel shift stage: at each stage you can either shift by 2^s bits |
674 |
|
// or leave the previous stage untouched |
675 |
2091 |
prev_res = res; |
676 |
2091 |
int threshold = pow(2, s); |
677 |
23107 |
for (unsigned i = 0; i < a.size(); ++i) |
678 |
|
{ |
679 |
21016 |
if (i + threshold >= a.size()) |
680 |
|
{ |
681 |
|
// if b[s] is true then we must have shifted by at least 2^b bits so |
682 |
|
// all bits above 2^s will be 0, otherwise just use previous shift value |
683 |
5584 |
res[i] = mkIte(b[s], mkFalse<T>(), prev_res[i]); |
684 |
|
} |
685 |
|
else |
686 |
|
{ |
687 |
|
// if b[s]= 0, use previous value, otherwise shift by threshold bits |
688 |
15432 |
Assert(i + threshold < a.size()); |
689 |
15432 |
res[i] = mkIte(mkNot(b[s]), prev_res[i], prev_res[i + threshold]); |
690 |
|
} |
691 |
|
} |
692 |
|
} |
693 |
|
|
694 |
861 |
prev_res = res; |
695 |
7087 |
for (unsigned i = 0; i < b.size(); ++i) |
696 |
|
{ |
697 |
|
// this is fine because b_ult_a_size has been bit-blasted |
698 |
6226 |
res[i] = mkIte(b_ult_a_size, prev_res[i], mkFalse<T>()); |
699 |
|
} |
700 |
|
|
701 |
861 |
if (Debug.isOn("bitvector-bb")) |
702 |
|
{ |
703 |
|
Debug("bitvector-bb") << "with bits: " << toString(res) << "\n"; |
704 |
|
} |
705 |
861 |
} |
706 |
|
|
707 |
|
template <class T> |
708 |
620 |
void DefaultAshrBB(TNode node, std::vector<T>& res, TBitblaster<T>* bb) |
709 |
|
{ |
710 |
620 |
Debug("bitvector-bb") << "theory::bv::DefaultAshrBB bitblasting " << node |
711 |
|
<< "\n"; |
712 |
620 |
Assert(node.getKind() == kind::BITVECTOR_ASHR && res.size() == 0); |
713 |
1240 |
std::vector<T> a, b; |
714 |
620 |
bb->bbTerm(node[0], a); |
715 |
620 |
bb->bbTerm(node[1], b); |
716 |
|
|
717 |
|
// check for b < n |
718 |
620 |
unsigned size = utils::getSize(node); |
719 |
620 |
unsigned log2_size = std::ceil(log2((double)size)); |
720 |
1240 |
Node a_size = utils::mkConst(size, size); |
721 |
|
|
722 |
1240 |
std::vector<T> a_size_bits; |
723 |
620 |
DefaultConstBB(a_size, a_size_bits, bb); |
724 |
1240 |
T b_ult_a_size = uLessThanBB(b, a_size_bits, false); |
725 |
|
|
726 |
620 |
res = a; |
727 |
1240 |
T sign_bit = a.back(); |
728 |
1240 |
std::vector<T> prev_res; |
729 |
|
|
730 |
1917 |
for (unsigned s = 0; s < log2_size; ++s) |
731 |
|
{ |
732 |
|
// barrel shift stage: at each stage you can either shift by 2^s bits |
733 |
|
// or leave the previous stage untouched |
734 |
1297 |
prev_res = res; |
735 |
1297 |
int threshold = pow(2, s); |
736 |
11348 |
for (unsigned i = 0; i < a.size(); ++i) |
737 |
|
{ |
738 |
10051 |
if (i + threshold >= a.size()) |
739 |
|
{ |
740 |
|
// if b[s] is true then we must have shifted by at least 2^b bits so |
741 |
|
// all bits above 2^s will be the sign bit, otherwise just use previous |
742 |
|
// shift value |
743 |
3021 |
res[i] = mkIte(b[s], sign_bit, prev_res[i]); |
744 |
|
} |
745 |
|
else |
746 |
|
{ |
747 |
|
// if b[s]= 0, use previous value, otherwise shift by threshold bits |
748 |
7030 |
Assert(i + threshold < a.size()); |
749 |
7030 |
res[i] = mkIte(mkNot(b[s]), prev_res[i], prev_res[i + threshold]); |
750 |
|
} |
751 |
|
} |
752 |
|
} |
753 |
|
|
754 |
620 |
prev_res = res; |
755 |
3989 |
for (unsigned i = 0; i < b.size(); ++i) |
756 |
|
{ |
757 |
|
// this is fine because b_ult_a_size has been bit-blasted |
758 |
3369 |
res[i] = mkIte(b_ult_a_size, prev_res[i], sign_bit); |
759 |
|
} |
760 |
|
|
761 |
620 |
if (Debug.isOn("bitvector-bb")) |
762 |
|
{ |
763 |
|
Debug("bitvector-bb") << "with bits: " << toString(res) << "\n"; |
764 |
|
} |
765 |
620 |
} |
766 |
|
|
767 |
|
template <class T> |
768 |
718 |
void DefaultUltbvBB (TNode node, std::vector<T>& res, TBitblaster<T>* bb) { |
769 |
718 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
770 |
718 |
Assert(node.getKind() == kind::BITVECTOR_ULTBV); |
771 |
1436 |
std::vector<T> a, b; |
772 |
718 |
bb->bbTerm(node[0], a); |
773 |
718 |
bb->bbTerm(node[1], b); |
774 |
718 |
Assert(a.size() == b.size()); |
775 |
|
|
776 |
|
// construct bitwise comparison |
777 |
718 |
res.push_back(uLessThanBB(a, b, false)); |
778 |
718 |
} |
779 |
|
|
780 |
|
template <class T> |
781 |
1401 |
void DefaultSltbvBB (TNode node, std::vector<T>& res, TBitblaster<T>* bb) { |
782 |
1401 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
783 |
1401 |
Assert(node.getKind() == kind::BITVECTOR_SLTBV); |
784 |
2802 |
std::vector<T> a, b; |
785 |
1401 |
bb->bbTerm(node[0], a); |
786 |
1401 |
bb->bbTerm(node[1], b); |
787 |
1401 |
Assert(a.size() == b.size()); |
788 |
|
|
789 |
|
// construct bitwise comparison |
790 |
1401 |
res.push_back(sLessThanBB(a, b, false)); |
791 |
1401 |
} |
792 |
|
|
793 |
|
template <class T> |
794 |
4117 |
void DefaultIteBB (TNode node, std::vector<T>& res, TBitblaster<T>* bb) { |
795 |
4117 |
Debug("bitvector-bb") << "Bitblasting node " << node << "\n"; |
796 |
4117 |
Assert(node.getKind() == kind::BITVECTOR_ITE); |
797 |
8234 |
std::vector<T> cond, thenpart, elsepart; |
798 |
4117 |
bb->bbTerm(node[0], cond); |
799 |
4117 |
bb->bbTerm(node[1], thenpart); |
800 |
4117 |
bb->bbTerm(node[2], elsepart); |
801 |
|
|
802 |
4117 |
Assert(cond.size() == 1); |
803 |
4117 |
Assert(thenpart.size() == elsepart.size()); |
804 |
|
|
805 |
60327 |
for (unsigned i = 0; i < thenpart.size(); ++i) { |
806 |
|
// (~cond OR thenpart) AND (cond OR elsepart) |
807 |
56210 |
res.push_back(mkAnd(mkOr(mkNot(cond[0]),thenpart[i]),mkOr(cond[0],elsepart[i]))); |
808 |
|
} |
809 |
4117 |
} |
810 |
|
|
811 |
|
template <class T> |
812 |
9460 |
void DefaultExtractBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
813 |
9460 |
Assert(node.getKind() == kind::BITVECTOR_EXTRACT); |
814 |
9460 |
Assert(bits.size() == 0); |
815 |
|
|
816 |
18920 |
std::vector<T> base_bits; |
817 |
9460 |
bb->bbTerm(node[0], base_bits); |
818 |
9460 |
unsigned high = utils::getExtractHigh(node); |
819 |
9460 |
unsigned low = utils::getExtractLow(node); |
820 |
|
|
821 |
72332 |
for (unsigned i = low; i <= high; ++i) { |
822 |
62872 |
bits.push_back(base_bits[i]); |
823 |
|
} |
824 |
9460 |
Assert(bits.size() == high - low + 1); |
825 |
|
|
826 |
9460 |
if(Debug.isOn("bitvector-bb")) { |
827 |
|
Debug("bitvector-bb") << "theory::bv::DefaultExtractBB bitblasting " << node << "\n"; |
828 |
|
Debug("bitvector-bb") << " with bits " << toString(bits); |
829 |
|
} |
830 |
9460 |
} |
831 |
|
|
832 |
|
|
833 |
|
template <class T> |
834 |
|
void DefaultRepeatBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
835 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
836 |
|
<< node.getKind() << "\n"; |
837 |
|
// this should be rewritten |
838 |
|
Unimplemented(); |
839 |
|
} |
840 |
|
|
841 |
|
template <class T> |
842 |
|
void DefaultZeroExtendBB (TNode node, std::vector<T>& res_bits, TBitblaster<T>* bb) { |
843 |
|
|
844 |
|
Debug("bitvector-bb") << "theory::bv::DefaultZeroExtendBB bitblasting " << node << "\n"; |
845 |
|
|
846 |
|
// this should be rewritten |
847 |
|
Unimplemented(); |
848 |
|
|
849 |
|
} |
850 |
|
|
851 |
|
template <class T> |
852 |
4079 |
void DefaultSignExtendBB (TNode node, std::vector<T>& res_bits, TBitblaster<T>* bb) { |
853 |
4079 |
Debug("bitvector-bb") << "theory::bv::DefaultSignExtendBB bitblasting " << node << "\n"; |
854 |
|
|
855 |
4079 |
Assert(node.getKind() == kind::BITVECTOR_SIGN_EXTEND && res_bits.size() == 0); |
856 |
|
|
857 |
8158 |
std::vector<T> bits; |
858 |
4079 |
bb->bbTerm(node[0], bits); |
859 |
|
|
860 |
8158 |
T sign_bit = bits.back(); |
861 |
4079 |
unsigned amount = |
862 |
8158 |
node.getOperator().getConst<BitVectorSignExtend>().d_signExtendAmount; |
863 |
|
|
864 |
15554 |
for (unsigned i = 0; i < bits.size(); ++i ) { |
865 |
11475 |
res_bits.push_back(bits[i]); |
866 |
|
} |
867 |
|
|
868 |
23397 |
for (unsigned i = 0 ; i < amount ; ++i ) { |
869 |
19318 |
res_bits.push_back(sign_bit); |
870 |
|
} |
871 |
|
|
872 |
4079 |
Assert(res_bits.size() == amount + bits.size()); |
873 |
4079 |
} |
874 |
|
|
875 |
|
template <class T> |
876 |
|
void DefaultRotateRightBB (TNode node, std::vector<T>& res, TBitblaster<T>* bb) { |
877 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
878 |
|
<< node.getKind() << "\n"; |
879 |
|
|
880 |
|
Unimplemented(); |
881 |
|
} |
882 |
|
|
883 |
|
template <class T> |
884 |
|
void DefaultRotateLeftBB (TNode node, std::vector<T>& bits, TBitblaster<T>* bb) { |
885 |
|
Debug("bitvector") << "theory::bv:: Unimplemented kind " |
886 |
|
<< node.getKind() << "\n"; |
887 |
|
Unimplemented(); |
888 |
|
} |
889 |
|
|
890 |
|
|
891 |
|
} |
892 |
|
} |
893 |
|
} // namespace cvc5 |
894 |
|
|
895 |
|
#endif |