2 * ezSAT -- A simple and easy to use CNF generator for SAT solvers
4 * Copyright (C) 2013 Clifford Wolf <clifford@clifford.at>
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
29 const int ezSAT::CONST_TRUE
= 1;
30 const int ezSAT::CONST_FALSE
= 2;
32 static std::string
my_int_to_string(int i
)
36 snprintf(buffer
, 64, "%d", i
);
39 return std::to_string(i
);
47 flag_keep_cnf
= false;
48 flag_non_incremental
= false;
50 non_incremental_solve_used_up
= false;
57 solverTimoutStatus
= false;
59 literal("CONST_TRUE");
60 literal("CONST_FALSE");
62 assert(literal("CONST_TRUE") == CONST_TRUE
);
63 assert(literal("CONST_FALSE") == CONST_FALSE
);
70 void ezSAT::addhash(unsigned int h
)
72 statehash
= ((statehash
<< 5) + statehash
) ^ h
;
75 int ezSAT::value(bool val
)
77 return val
? CONST_TRUE
: CONST_FALSE
;
82 literals
.push_back(std::string());
83 return literals
.size();
86 int ezSAT::literal(const std::string
&name
)
88 if (literalsCache
.count(name
) == 0) {
89 literals
.push_back(name
);
90 literalsCache
[name
] = literals
.size();
92 return literalsCache
.at(name
);
95 int ezSAT::frozen_literal()
102 int ezSAT::frozen_literal(const std::string
&name
)
104 int id
= literal(name
);
109 int ezSAT::expression(OpId op
, int a
, int b
, int c
, int d
, int e
, int f
)
111 std::vector
<int> args(6);
112 args
[0] = a
, args
[1] = b
, args
[2] = c
;
113 args
[3] = d
, args
[4] = e
, args
[5] = f
;
114 return expression(op
, args
);
117 int ezSAT::expression(OpId op
, const std::vector
<int> &args
)
119 std::vector
<int> myArgs
;
120 myArgs
.reserve(args
.size());
121 bool xorRemovedOddTrues
= false;
126 for (auto arg
: args
)
133 if (op
== OpAnd
&& arg
== CONST_TRUE
)
135 if ((op
== OpOr
|| op
== OpXor
) && arg
== CONST_FALSE
)
137 if (op
== OpXor
&& arg
== CONST_TRUE
) {
138 xorRemovedOddTrues
= !xorRemovedOddTrues
;
141 myArgs
.push_back(arg
);
144 if (myArgs
.size() > 0 && (op
== OpAnd
|| op
== OpOr
|| op
== OpXor
|| op
== OpIFF
)) {
145 std::sort(myArgs
.begin(), myArgs
.end());
147 for (int i
= 1; i
< int(myArgs
.size()); i
++)
148 if (j
< 0 || myArgs
[j
] != myArgs
[i
])
149 myArgs
[++j
] = myArgs
[i
];
150 else if (op
== OpXor
)
158 assert(myArgs
.size() == 1);
159 if (myArgs
[0] == CONST_TRUE
)
161 if (myArgs
[0] == CONST_FALSE
)
166 if (myArgs
.size() == 0)
168 if (myArgs
.size() == 1)
173 if (myArgs
.size() == 0)
175 if (myArgs
.size() == 1)
180 if (myArgs
.size() == 0)
181 return xorRemovedOddTrues
? CONST_TRUE
: CONST_FALSE
;
182 if (myArgs
.size() == 1)
183 return xorRemovedOddTrues
? NOT(myArgs
[0]) : myArgs
[0];
187 assert(myArgs
.size() >= 1);
188 if (myArgs
.size() == 1)
190 // FIXME: Add proper const folding
194 assert(myArgs
.size() == 3);
195 if (myArgs
[0] == CONST_TRUE
)
197 if (myArgs
[0] == CONST_FALSE
)
205 std::pair
<OpId
, std::vector
<int>> myExpr(op
, myArgs
);
208 if (expressionsCache
.count(myExpr
) > 0) {
209 id
= expressionsCache
.at(myExpr
);
211 id
= -(int(expressions
.size()) + 1);
212 expressionsCache
[myExpr
] = id
;
213 expressions
.push_back(myExpr
);
216 if (xorRemovedOddTrues
)
225 void ezSAT::lookup_literal(int id
, std::string
&name
) const
227 assert(0 < id
&& id
<= int(literals
.size()));
228 name
= literals
[id
- 1];
231 const std::string
&ezSAT::lookup_literal(int id
) const
233 assert(0 < id
&& id
<= int(literals
.size()));
234 return literals
[id
- 1];
237 void ezSAT::lookup_expression(int id
, OpId
&op
, std::vector
<int> &args
) const
239 assert(0 < -id
&& -id
<= int(expressions
.size()));
240 op
= expressions
[-id
- 1].first
;
241 args
= expressions
[-id
- 1].second
;
244 const std::vector
<int> &ezSAT::lookup_expression(int id
, OpId
&op
) const
246 assert(0 < -id
&& -id
<= int(expressions
.size()));
247 op
= expressions
[-id
- 1].first
;
248 return expressions
[-id
- 1].second
;
251 int ezSAT::parse_string(const std::string
&)
256 std::string
ezSAT::to_string(int id
) const
262 lookup_literal(id
, text
);
267 std::vector
<int> args
;
268 lookup_expression(id
, op
, args
);
300 for (int i
= 0; i
< int(args
.size()); i
++) {
303 text
+= to_string(args
[i
]);
312 int ezSAT::eval(int id
, const std::vector
<int> &values
) const
315 if (id
<= int(values
.size()) && (values
[id
-1] == CONST_TRUE
|| values
[id
-1] == CONST_FALSE
|| values
[id
-1] == 0))
321 const std::vector
<int> &args
= lookup_expression(id
, op
);
327 assert(args
.size() == 1);
328 a
= eval(args
[0], values
);
331 if (a
== CONST_FALSE
)
336 for (auto arg
: args
) {
337 b
= eval(arg
, values
);
338 if (b
!= CONST_TRUE
&& b
!= CONST_FALSE
)
340 if (b
== CONST_FALSE
)
346 for (auto arg
: args
) {
347 b
= eval(arg
, values
);
348 if (b
!= CONST_TRUE
&& b
!= CONST_FALSE
)
356 for (auto arg
: args
) {
357 b
= eval(arg
, values
);
358 if (b
!= CONST_TRUE
&& b
!= CONST_FALSE
)
361 a
= a
== CONST_TRUE
? CONST_FALSE
: CONST_TRUE
;
365 assert(args
.size() > 0);
366 a
= eval(args
[0], values
);
367 for (auto arg
: args
) {
368 b
= eval(arg
, values
);
369 if (b
!= CONST_TRUE
&& b
!= CONST_FALSE
)
376 assert(args
.size() == 3);
377 a
= eval(args
[0], values
);
379 return eval(args
[1], values
);
380 if (a
== CONST_FALSE
)
381 return eval(args
[2], values
);
391 cnfVariableCount
= 0;
393 cnfLiteralVariables
.clear();
394 cnfExpressionVariables
.clear();
398 void ezSAT::freeze(int)
402 bool ezSAT::eliminated(int)
407 void ezSAT::assume(int id
)
414 assert(0 < -id
&& -id
<= int(expressions
.size()));
415 cnfExpressionVariables
.resize(expressions
.size());
417 if (cnfExpressionVariables
[-id
-1] == 0)
420 std::vector
<int> args
;
421 lookup_expression(id
, op
, args
);
424 int idx
= bind(args
[0]);
425 cnfClauses
.push_back(std::vector
<int>(1, -idx
));
430 std::vector
<int> clause
;
432 clause
.push_back(bind(arg
));
433 cnfClauses
.push_back(clause
);
438 for (int arg
: args
) {
439 cnfClauses
.push_back(std::vector
<int>(1, bind(arg
)));
448 cnfClauses
.push_back(std::vector
<int>(1, idx
));
452 void ezSAT::add_clause(const std::vector
<int> &args
)
455 for (auto arg
: args
)
458 cnfClauses
.push_back(args
);
462 void ezSAT::add_clause(const std::vector
<int> &args
, bool argsPolarity
, int a
, int b
, int c
)
464 std::vector
<int> clause
;
465 for (auto arg
: args
)
466 clause
.push_back(argsPolarity
? +arg
: -arg
);
476 void ezSAT::add_clause(int a
, int b
, int c
)
478 std::vector
<int> clause
;
488 int ezSAT::bind_cnf_not(const std::vector
<int> &args
)
490 assert(args
.size() == 1);
494 int ezSAT::bind_cnf_and(const std::vector
<int> &args
)
496 assert(args
.size() >= 2);
498 int idx
= ++cnfVariableCount
;
499 add_clause(args
, false, idx
);
501 for (auto arg
: args
)
502 add_clause(-idx
, arg
);
507 int ezSAT::bind_cnf_or(const std::vector
<int> &args
)
509 assert(args
.size() >= 2);
511 int idx
= ++cnfVariableCount
;
512 add_clause(args
, true, -idx
);
514 for (auto arg
: args
)
515 add_clause(idx
, -arg
);
520 int ezSAT::bound(int id
) const
522 if (id
> 0 && id
<= int(cnfLiteralVariables
.size()))
523 return cnfLiteralVariables
[id
-1];
524 if (-id
> 0 && -id
<= int(cnfExpressionVariables
.size()))
525 return cnfExpressionVariables
[-id
-1];
529 std::string
ezSAT::cnfLiteralInfo(int idx
) const
531 for (int i
= 0; i
< int(cnfLiteralVariables
.size()); i
++) {
532 if (cnfLiteralVariables
[i
] == idx
)
533 return to_string(i
+1);
534 if (cnfLiteralVariables
[i
] == -idx
)
535 return "NOT " + to_string(i
+1);
537 for (int i
= 0; i
< int(cnfExpressionVariables
.size()); i
++) {
538 if (cnfExpressionVariables
[i
] == idx
)
539 return to_string(-i
-1);
540 if (cnfExpressionVariables
[i
] == -idx
)
541 return "NOT " + to_string(-i
-1);
546 int ezSAT::bind(int id
, bool auto_freeze
)
550 addhash(auto_freeze
);
553 assert(0 < id
&& id
<= int(literals
.size()));
554 cnfLiteralVariables
.resize(literals
.size());
555 if (eliminated(cnfLiteralVariables
[id
-1])) {
556 fprintf(stderr
, "ezSAT: Missing freeze on literal `%s'.\n", to_string(id
).c_str());
559 if (cnfLiteralVariables
[id
-1] == 0) {
560 cnfLiteralVariables
[id
-1] = ++cnfVariableCount
;
561 if (id
== CONST_TRUE
)
562 add_clause(+cnfLiteralVariables
[id
-1]);
563 if (id
== CONST_FALSE
)
564 add_clause(-cnfLiteralVariables
[id
-1]);
566 return cnfLiteralVariables
[id
-1];
569 assert(0 < -id
&& -id
<= int(expressions
.size()));
570 cnfExpressionVariables
.resize(expressions
.size());
572 if (eliminated(cnfExpressionVariables
[-id
-1]))
574 cnfExpressionVariables
[-id
-1] = 0;
576 // this will recursively call bind(id). within the recursion
577 // the cnf is pre-set to 0. an idx is allocated there, then it
578 // is frozen, then it returns here with the new idx already set.
583 if (cnfExpressionVariables
[-id
-1] == 0)
586 std::vector
<int> args
;
587 lookup_expression(id
, op
, args
);
591 while (args
.size() > 1) {
592 std::vector
<int> newArgs
;
593 for (int i
= 0; i
< int(args
.size()); i
+= 2)
594 if (i
+1 == int(args
.size())) {
595 newArgs
.push_back(args
[i
]);
597 int sub1
= AND(args
[i
], NOT(args
[i
+1]));
598 int sub2
= AND(NOT(args
[i
]), args
[i
+1]);
599 newArgs
.push_back(OR(sub1
, sub2
));
603 idx
= bind(args
.at(0), false);
608 std::vector
<int> invArgs
;
609 for (auto arg
: args
)
610 invArgs
.push_back(NOT(arg
));
611 int sub1
= expression(OpAnd
, args
);
612 int sub2
= expression(OpAnd
, invArgs
);
613 idx
= bind(OR(sub1
, sub2
), false);
618 int sub1
= AND(args
[0], args
[1]);
619 int sub2
= AND(NOT(args
[0]), args
[2]);
620 idx
= bind(OR(sub1
, sub2
), false);
624 for (int i
= 0; i
< int(args
.size()); i
++)
625 args
[i
] = bind(args
[i
], false);
629 case OpNot
: idx
= bind_cnf_not(args
); break;
630 case OpAnd
: idx
= bind_cnf_and(args
); break;
631 case OpOr
: idx
= bind_cnf_or(args
); break;
637 cnfExpressionVariables
[-id
-1] = idx
;
640 return cnfExpressionVariables
[-id
-1];
643 void ezSAT::consumeCnf()
646 cnfClausesBackup
.insert(cnfClausesBackup
.end(), cnfClauses
.begin(), cnfClauses
.end());
652 void ezSAT::consumeCnf(std::vector
<std::vector
<int>> &cnf
)
655 cnfClausesBackup
.insert(cnfClausesBackup
.end(), cnfClauses
.begin(), cnfClauses
.end());
658 cnf
.swap(cnfClauses
);
662 void ezSAT::getFullCnf(std::vector
<std::vector
<int>> &full_cnf
) const
664 assert(full_cnf
.empty());
665 full_cnf
.insert(full_cnf
.end(), cnfClausesBackup
.begin(), cnfClausesBackup
.end());
666 full_cnf
.insert(full_cnf
.end(), cnfClauses
.begin(), cnfClauses
.end());
669 void ezSAT::preSolverCallback()
671 assert(!non_incremental_solve_used_up
);
672 if (mode_non_incremental())
673 non_incremental_solve_used_up
= true;
676 bool ezSAT::solver(const std::vector
<int>&, std::vector
<bool>&, const std::vector
<int>&)
679 fprintf(stderr
, "************************************************************************\n");
680 fprintf(stderr
, "ERROR: You are trying to use the solve() method of the ezSAT base class!\n");
681 fprintf(stderr
, "Use a dervied class like ezMiniSAT instead.\n");
682 fprintf(stderr
, "************************************************************************\n");
686 std::vector
<int> ezSAT::vec_const(const std::vector
<bool> &bits
)
688 std::vector
<int> vec
;
689 for (auto bit
: bits
)
690 vec
.push_back(bit
? CONST_TRUE
: CONST_FALSE
);
694 std::vector
<int> ezSAT::vec_const_signed(int64_t value
, int numBits
)
696 std::vector
<int> vec
;
697 for (int i
= 0; i
< numBits
; i
++)
698 vec
.push_back(((value
>> i
) & 1) != 0 ? CONST_TRUE
: CONST_FALSE
);
702 std::vector
<int> ezSAT::vec_const_unsigned(uint64_t value
, int numBits
)
704 std::vector
<int> vec
;
705 for (int i
= 0; i
< numBits
; i
++)
706 vec
.push_back(((value
>> i
) & 1) != 0 ? CONST_TRUE
: CONST_FALSE
);
710 std::vector
<int> ezSAT::vec_var(int numBits
)
712 std::vector
<int> vec
;
713 for (int i
= 0; i
< numBits
; i
++)
714 vec
.push_back(literal());
718 std::vector
<int> ezSAT::vec_var(std::string name
, int numBits
)
720 std::vector
<int> vec
;
721 for (int i
= 0; i
< numBits
; i
++) {
722 vec
.push_back(VAR(name
+ my_int_to_string(i
)));
727 std::vector
<int> ezSAT::vec_cast(const std::vector
<int> &vec1
, int toBits
, bool signExtend
)
729 std::vector
<int> vec
;
730 for (int i
= 0; i
< toBits
; i
++)
731 if (i
>= int(vec1
.size()))
732 vec
.push_back(signExtend
? vec1
.back() : CONST_FALSE
);
734 vec
.push_back(vec1
[i
]);
738 std::vector
<int> ezSAT::vec_not(const std::vector
<int> &vec1
)
740 std::vector
<int> vec
;
741 for (auto bit
: vec1
)
742 vec
.push_back(NOT(bit
));
746 std::vector
<int> ezSAT::vec_and(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
748 assert(vec1
.size() == vec2
.size());
749 std::vector
<int> vec(vec1
.size());
750 for (int i
= 0; i
< int(vec1
.size()); i
++)
751 vec
[i
] = AND(vec1
[i
], vec2
[i
]);
755 std::vector
<int> ezSAT::vec_or(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
757 assert(vec1
.size() == vec2
.size());
758 std::vector
<int> vec(vec1
.size());
759 for (int i
= 0; i
< int(vec1
.size()); i
++)
760 vec
[i
] = OR(vec1
[i
], vec2
[i
]);
764 std::vector
<int> ezSAT::vec_xor(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
766 assert(vec1
.size() == vec2
.size());
767 std::vector
<int> vec(vec1
.size());
768 for (int i
= 0; i
< int(vec1
.size()); i
++)
769 vec
[i
] = XOR(vec1
[i
], vec2
[i
]);
773 std::vector
<int> ezSAT::vec_iff(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
775 assert(vec1
.size() == vec2
.size());
776 std::vector
<int> vec(vec1
.size());
777 for (int i
= 0; i
< int(vec1
.size()); i
++)
778 vec
[i
] = IFF(vec1
[i
], vec2
[i
]);
782 std::vector
<int> ezSAT::vec_ite(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
, const std::vector
<int> &vec3
)
784 assert(vec1
.size() == vec2
.size() && vec2
.size() == vec3
.size());
785 std::vector
<int> vec(vec1
.size());
786 for (int i
= 0; i
< int(vec1
.size()); i
++)
787 vec
[i
] = ITE(vec1
[i
], vec2
[i
], vec3
[i
]);
792 std::vector
<int> ezSAT::vec_ite(int sel
, const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
794 assert(vec1
.size() == vec2
.size());
795 std::vector
<int> vec(vec1
.size());
796 for (int i
= 0; i
< int(vec1
.size()); i
++)
797 vec
[i
] = ITE(sel
, vec1
[i
], vec2
[i
]);
801 // 'y' is the MSB (carry) and x the LSB (sum) output
802 static void fulladder(ezSAT
*that
, int a
, int b
, int c
, int &y
, int &x
)
804 int tmp
= that
->XOR(a
, b
);
805 int new_x
= that
->XOR(tmp
, c
);
806 int new_y
= that
->OR(that
->AND(a
, b
), that
->AND(c
, tmp
));
808 printf("FULLADD> a=%s, b=%s, c=%s, carry=%s, sum=%s\n", that
->to_string(a
).c_str(), that
->to_string(b
).c_str(),
809 that
->to_string(c
).c_str(), that
->to_string(new_y
).c_str(), that
->to_string(new_x
).c_str());
811 x
= new_x
, y
= new_y
;
814 // 'y' is the MSB (carry) and x the LSB (sum) output
815 static void halfadder(ezSAT
*that
, int a
, int b
, int &y
, int &x
)
817 int new_x
= that
->XOR(a
, b
);
818 int new_y
= that
->AND(a
, b
);
820 printf("HALFADD> a=%s, b=%s, carry=%s, sum=%s\n", that
->to_string(a
).c_str(), that
->to_string(b
).c_str(),
821 that
->to_string(new_y
).c_str(), that
->to_string(new_x
).c_str());
823 x
= new_x
, y
= new_y
;
826 std::vector
<int> ezSAT::vec_count(const std::vector
<int> &vec
, int numBits
, bool clip
)
828 std::vector
<int> sum
= vec_const_unsigned(0, numBits
);
829 std::vector
<int> carry_vector
;
831 for (auto bit
: vec
) {
833 for (int i
= 0; i
< numBits
; i
++)
834 halfadder(this, carry
, sum
[i
], carry
, sum
[i
]);
835 carry_vector
.push_back(carry
);
839 int overflow
= vec_reduce_or(carry_vector
);
840 sum
= vec_ite(overflow
, vec_const_unsigned(~0, numBits
), sum
);
844 printf("COUNT> vec=[");
845 for (int i
= int(vec
.size())-1; i
>= 0; i
--)
846 printf("%s%s", to_string(vec
[i
]).c_str(), i
? ", " : "");
847 printf("], result=[");
848 for (int i
= int(sum
.size())-1; i
>= 0; i
--)
849 printf("%s%s", to_string(sum
[i
]).c_str(), i
? ", " : "");
856 std::vector
<int> ezSAT::vec_add(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
858 assert(vec1
.size() == vec2
.size());
859 std::vector
<int> vec(vec1
.size());
860 int carry
= CONST_FALSE
;
861 for (int i
= 0; i
< int(vec1
.size()); i
++)
862 fulladder(this, vec1
[i
], vec2
[i
], carry
, carry
, vec
[i
]);
865 printf("ADD> vec1=[");
866 for (int i
= int(vec1
.size())-1; i
>= 0; i
--)
867 printf("%s%s", to_string(vec1
[i
]).c_str(), i
? ", " : "");
869 for (int i
= int(vec2
.size())-1; i
>= 0; i
--)
870 printf("%s%s", to_string(vec2
[i
]).c_str(), i
? ", " : "");
871 printf("], result=[");
872 for (int i
= int(vec
.size())-1; i
>= 0; i
--)
873 printf("%s%s", to_string(vec
[i
]).c_str(), i
? ", " : "");
880 std::vector
<int> ezSAT::vec_sub(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
882 assert(vec1
.size() == vec2
.size());
883 std::vector
<int> vec(vec1
.size());
884 int carry
= CONST_TRUE
;
885 for (int i
= 0; i
< int(vec1
.size()); i
++)
886 fulladder(this, vec1
[i
], NOT(vec2
[i
]), carry
, carry
, vec
[i
]);
889 printf("SUB> vec1=[");
890 for (int i
= int(vec1
.size())-1; i
>= 0; i
--)
891 printf("%s%s", to_string(vec1
[i
]).c_str(), i
? ", " : "");
893 for (int i
= int(vec2
.size())-1; i
>= 0; i
--)
894 printf("%s%s", to_string(vec2
[i
]).c_str(), i
? ", " : "");
895 printf("], result=[");
896 for (int i
= int(vec
.size())-1; i
>= 0; i
--)
897 printf("%s%s", to_string(vec
[i
]).c_str(), i
? ", " : "");
904 std::vector
<int> ezSAT::vec_neg(const std::vector
<int> &vec
)
906 std::vector
<int> zero(vec
.size(), CONST_FALSE
);
907 return vec_sub(zero
, vec
);
910 void ezSAT::vec_cmp(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
, int &carry
, int &overflow
, int &sign
, int &zero
)
912 assert(vec1
.size() == vec2
.size());
915 for (int i
= 0; i
< int(vec1
.size()); i
++) {
917 fulladder(this, vec1
[i
], NOT(vec2
[i
]), carry
, carry
, sign
);
918 zero
= OR(zero
, sign
);
920 overflow
= XOR(overflow
, carry
);
925 printf("CMP> vec1=[");
926 for (int i
= int(vec1
.size())-1; i
>= 0; i
--)
927 printf("%s%s", to_string(vec1
[i
]).c_str(), i
? ", " : "");
929 for (int i
= int(vec2
.size())-1; i
>= 0; i
--)
930 printf("%s%s", to_string(vec2
[i
]).c_str(), i
? ", " : "");
931 printf("], carry=%s, overflow=%s, sign=%s, zero=%s\n", to_string(carry
).c_str(), to_string(overflow
).c_str(), to_string(sign
).c_str(), to_string(zero
).c_str());
935 int ezSAT::vec_lt_signed(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
937 int carry
, overflow
, sign
, zero
;
938 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
939 return OR(AND(NOT(overflow
), sign
), AND(overflow
, NOT(sign
)));
942 int ezSAT::vec_le_signed(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
944 int carry
, overflow
, sign
, zero
;
945 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
946 return OR(AND(NOT(overflow
), sign
), AND(overflow
, NOT(sign
)), zero
);
949 int ezSAT::vec_ge_signed(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
951 int carry
, overflow
, sign
, zero
;
952 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
953 return OR(AND(NOT(overflow
), NOT(sign
)), AND(overflow
, sign
));
956 int ezSAT::vec_gt_signed(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
958 int carry
, overflow
, sign
, zero
;
959 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
960 return AND(OR(AND(NOT(overflow
), NOT(sign
)), AND(overflow
, sign
)), NOT(zero
));
963 int ezSAT::vec_lt_unsigned(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
965 int carry
, overflow
, sign
, zero
;
966 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
970 int ezSAT::vec_le_unsigned(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
972 int carry
, overflow
, sign
, zero
;
973 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
974 return OR(carry
, zero
);
977 int ezSAT::vec_ge_unsigned(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
979 int carry
, overflow
, sign
, zero
;
980 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
984 int ezSAT::vec_gt_unsigned(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
986 int carry
, overflow
, sign
, zero
;
987 vec_cmp(vec1
, vec2
, carry
, overflow
, sign
, zero
);
988 return AND(NOT(carry
), NOT(zero
));
991 int ezSAT::vec_eq(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
993 return vec_reduce_and(vec_iff(vec1
, vec2
));
996 int ezSAT::vec_ne(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
998 return NOT(vec_reduce_and(vec_iff(vec1
, vec2
)));
1001 std::vector
<int> ezSAT::vec_shl(const std::vector
<int> &vec1
, int shift
, bool signExtend
)
1003 std::vector
<int> vec
;
1004 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1006 if (int(vec1
.size()) <= j
)
1007 vec
.push_back(signExtend
? vec1
.back() : CONST_FALSE
);
1009 vec
.push_back(vec1
[j
]);
1011 vec
.push_back(CONST_FALSE
);
1016 std::vector
<int> ezSAT::vec_srl(const std::vector
<int> &vec1
, int shift
)
1018 std::vector
<int> vec
;
1019 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1023 while (j
>= int(vec1
.size()))
1025 vec
.push_back(vec1
[j
]);
1030 std::vector
<int> ezSAT::vec_shift(const std::vector
<int> &vec1
, int shift
, int extend_left
, int extend_right
)
1032 std::vector
<int> vec
;
1033 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1036 vec
.push_back(extend_right
);
1037 else if (j
>= int(vec1
.size()))
1038 vec
.push_back(extend_left
);
1040 vec
.push_back(vec1
[j
]);
1045 static int my_clog2(int x
)
1048 for (x
--; x
> 0; result
++)
1053 std::vector
<int> ezSAT::vec_shift_right(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
, bool vec2_signed
, int extend_left
, int extend_right
)
1055 int vec2_bits
= std::min(my_clog2(vec1
.size()) + (vec2_signed
? 1 : 0), int(vec2
.size()));
1057 std::vector
<int> overflow_bits(vec2
.begin() + vec2_bits
, vec2
.end());
1058 int overflow_left
= CONST_FALSE
, overflow_right
= CONST_FALSE
;
1061 int overflow
= CONST_FALSE
;
1062 for (auto bit
: overflow_bits
)
1063 overflow
= OR(overflow
, XOR(bit
, vec2
[vec2_bits
-1]));
1064 overflow_left
= AND(overflow
, NOT(vec2
.back()));
1065 overflow_right
= AND(overflow
, vec2
.back());
1067 overflow_left
= vec_reduce_or(overflow_bits
);
1069 std::vector
<int> buffer
= vec1
;
1072 while (buffer
.size() < vec1
.size() + (1 << vec2_bits
))
1073 buffer
.push_back(extend_left
);
1075 std::vector
<int> overflow_pattern_left(buffer
.size(), extend_left
);
1076 std::vector
<int> overflow_pattern_right(buffer
.size(), extend_right
);
1078 buffer
= vec_ite(overflow_left
, overflow_pattern_left
, buffer
);
1081 buffer
= vec_ite(overflow_right
, overflow_pattern_left
, buffer
);
1083 for (int i
= vec2_bits
-1; i
>= 0; i
--) {
1084 std::vector
<int> shifted_buffer
;
1085 if (vec2_signed
&& i
== vec2_bits
-1)
1086 shifted_buffer
= vec_shift(buffer
, -(1 << i
), extend_left
, extend_right
);
1088 shifted_buffer
= vec_shift(buffer
, 1 << i
, extend_left
, extend_right
);
1089 buffer
= vec_ite(vec2
[i
], shifted_buffer
, buffer
);
1092 buffer
.resize(vec1
.size());
1096 std::vector
<int> ezSAT::vec_shift_left(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
, bool vec2_signed
, int extend_left
, int extend_right
)
1098 // vec2_signed is not implemented in vec_shift_left() yet
1099 assert(vec2_signed
== false);
1101 int vec2_bits
= std::min(my_clog2(vec1
.size()), int(vec2
.size()));
1103 std::vector
<int> overflow_bits(vec2
.begin() + vec2_bits
, vec2
.end());
1104 int overflow
= vec_reduce_or(overflow_bits
);
1106 std::vector
<int> buffer
= vec1
;
1107 std::vector
<int> overflow_pattern_right(buffer
.size(), extend_right
);
1108 buffer
= vec_ite(overflow
, overflow_pattern_right
, buffer
);
1110 for (int i
= 0; i
< vec2_bits
; i
++) {
1111 std::vector
<int> shifted_buffer
;
1112 shifted_buffer
= vec_shift(buffer
, -(1 << i
), extend_left
, extend_right
);
1113 buffer
= vec_ite(vec2
[i
], shifted_buffer
, buffer
);
1116 buffer
.resize(vec1
.size());
1120 void ezSAT::vec_append(std::vector
<int> &vec
, const std::vector
<int> &vec1
) const
1122 for (auto bit
: vec1
)
1126 void ezSAT::vec_append_signed(std::vector
<int> &vec
, const std::vector
<int> &vec1
, int64_t value
)
1128 assert(int(vec1
.size()) <= 64);
1129 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1130 if (((value
>> i
) & 1) != 0)
1131 vec
.push_back(vec1
[i
]);
1133 vec
.push_back(NOT(vec1
[i
]));
1137 void ezSAT::vec_append_unsigned(std::vector
<int> &vec
, const std::vector
<int> &vec1
, uint64_t value
)
1139 assert(int(vec1
.size()) <= 64);
1140 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1141 if (((value
>> i
) & 1) != 0)
1142 vec
.push_back(vec1
[i
]);
1144 vec
.push_back(NOT(vec1
[i
]));
1148 int64_t ezSAT::vec_model_get_signed(const std::vector
<int> &modelExpressions
, const std::vector
<bool> &modelValues
, const std::vector
<int> &vec1
) const
1151 std::map
<int, bool> modelMap
;
1152 assert(modelExpressions
.size() == modelValues
.size());
1153 for (int i
= 0; i
< int(modelExpressions
.size()); i
++)
1154 modelMap
[modelExpressions
[i
]] = modelValues
[i
];
1155 for (int i
= 0; i
< 64; i
++) {
1156 int j
= i
< int(vec1
.size()) ? i
: vec1
.size()-1;
1157 if (modelMap
.at(vec1
[j
]))
1158 value
|= int64_t(1) << i
;
1163 uint64_t ezSAT::vec_model_get_unsigned(const std::vector
<int> &modelExpressions
, const std::vector
<bool> &modelValues
, const std::vector
<int> &vec1
) const
1166 std::map
<int, bool> modelMap
;
1167 assert(modelExpressions
.size() == modelValues
.size());
1168 for (int i
= 0; i
< int(modelExpressions
.size()); i
++)
1169 modelMap
[modelExpressions
[i
]] = modelValues
[i
];
1170 for (int i
= 0; i
< int(vec1
.size()); i
++)
1171 if (modelMap
.at(vec1
[i
]))
1172 value
|= uint64_t(1) << i
;
1176 int ezSAT::vec_reduce_and(const std::vector
<int> &vec1
)
1178 return expression(OpAnd
, vec1
);
1181 int ezSAT::vec_reduce_or(const std::vector
<int> &vec1
)
1183 return expression(OpOr
, vec1
);
1186 void ezSAT::vec_set(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
)
1188 assert(vec1
.size() == vec2
.size());
1189 for (int i
= 0; i
< int(vec1
.size()); i
++)
1190 SET(vec1
[i
], vec2
[i
]);
1193 void ezSAT::vec_set_signed(const std::vector
<int> &vec1
, int64_t value
)
1195 assert(int(vec1
.size()) <= 64);
1196 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1197 if (((value
>> i
) & 1) != 0)
1200 assume(NOT(vec1
[i
]));
1204 void ezSAT::vec_set_unsigned(const std::vector
<int> &vec1
, uint64_t value
)
1206 assert(int(vec1
.size()) <= 64);
1207 for (int i
= 0; i
< int(vec1
.size()); i
++) {
1208 if (((value
>> i
) & 1) != 0)
1211 assume(NOT(vec1
[i
]));
1215 ezSATbit
ezSAT::bit(_V a
)
1217 return ezSATbit(*this, a
);
1220 ezSATvec
ezSAT::vec(const std::vector
<int> &vec
)
1222 return ezSATvec(*this, vec
);
1225 void ezSAT::printDIMACS(FILE *f
, bool verbose
) const
1228 fprintf(stderr
, "Usage error: printDIMACS() must not be called after cnfConsumed()!");
1232 int digits
= ceil(log10f(cnfVariableCount
)) + 2;
1234 fprintf(f
, "c generated by ezSAT\n");
1239 fprintf(f
, "c mapping of variables to literals:\n");
1240 for (int i
= 0; i
< int(cnfLiteralVariables
.size()); i
++)
1241 if (cnfLiteralVariables
[i
] != 0)
1242 fprintf(f
, "c %*d: %s\n", digits
, cnfLiteralVariables
[i
], literals
[i
].c_str());
1245 fprintf(f
, "c mapping of variables to expressions:\n");
1246 for (int i
= 0; i
< int(cnfExpressionVariables
.size()); i
++)
1247 if (cnfExpressionVariables
[i
] != 0)
1248 fprintf(f
, "c %*d: %d\n", digits
, cnfExpressionVariables
[i
], -i
-1);
1250 if (mode_keep_cnf()) {
1252 fprintf(f
, "c %d clauses from backup, %d from current buffer\n",
1253 int(cnfClausesBackup
.size()), int(cnfClauses
.size()));
1259 std::vector
<std::vector
<int>> all_clauses
;
1260 getFullCnf(all_clauses
);
1261 assert(cnfClausesCount
== int(all_clauses
.size()));
1263 fprintf(f
, "p cnf %d %d\n", cnfVariableCount
, cnfClausesCount
);
1264 int maxClauseLen
= 0;
1265 for (auto &clause
: all_clauses
)
1266 maxClauseLen
= std::max(int(clause
.size()), maxClauseLen
);
1268 maxClauseLen
= std::min(maxClauseLen
, 3);
1269 for (auto &clause
: all_clauses
) {
1270 for (auto idx
: clause
)
1271 fprintf(f
, " %*d", digits
, idx
);
1272 if (maxClauseLen
>= int(clause
.size()))
1273 fprintf(f
, " %*d\n", (digits
+ 1)*int(maxClauseLen
- clause
.size()) + digits
, 0);
1275 fprintf(f
, " %*d\n", digits
, 0);
1279 static std::string
expression2str(const std::pair
<ezSAT::OpId
, std::vector
<int>> &data
)
1282 switch (data
.first
) {
1283 #define X(op) case ezSAT::op: text += #op; break;
1295 for (auto it
: data
.second
)
1296 text
+= " " + my_int_to_string(it
);
1300 void ezSAT::printInternalState(FILE *f
) const
1302 fprintf(f
, "--8<-- snip --8<--\n");
1304 fprintf(f
, "literalsCache:\n");
1305 for (auto &it
: literalsCache
)
1306 fprintf(f
, " `%s' -> %d\n", it
.first
.c_str(), it
.second
);
1308 fprintf(f
, "literals:\n");
1309 for (int i
= 0; i
< int(literals
.size()); i
++)
1310 fprintf(f
, " %d: `%s'\n", i
+1, literals
[i
].c_str());
1312 fprintf(f
, "expressionsCache:\n");
1313 for (auto &it
: expressionsCache
)
1314 fprintf(f
, " `%s' -> %d\n", expression2str(it
.first
).c_str(), it
.second
);
1316 fprintf(f
, "expressions:\n");
1317 for (int i
= 0; i
< int(expressions
.size()); i
++)
1318 fprintf(f
, " %d: `%s'\n", -i
-1, expression2str(expressions
[i
]).c_str());
1320 fprintf(f
, "cnfVariables (count=%d):\n", cnfVariableCount
);
1321 for (int i
= 0; i
< int(cnfLiteralVariables
.size()); i
++)
1322 if (cnfLiteralVariables
[i
] != 0)
1323 fprintf(f
, " literal %d -> %d (%s)\n", i
+1, cnfLiteralVariables
[i
], to_string(i
+1).c_str());
1324 for (int i
= 0; i
< int(cnfExpressionVariables
.size()); i
++)
1325 if (cnfExpressionVariables
[i
] != 0)
1326 fprintf(f
, " expression %d -> %d (%s)\n", -i
-1, cnfExpressionVariables
[i
], to_string(-i
-1).c_str());
1328 fprintf(f
, "cnfClauses:\n");
1329 for (auto &i1
: cnfClauses
) {
1331 fprintf(f
, " %4d", i2
);
1335 fprintf(f
, " *** more clauses consumed via cnfConsume() ***\n");
1337 fprintf(f
, "--8<-- snap --8<--\n");
1340 int ezSAT::onehot(const std::vector
<int> &vec
, bool max_only
)
1342 // Mixed one-hot/binary encoding as described by Claessen in Sec. 4.2 of
1343 // "Successful SAT Encoding Techniques. Magnus Bjiirk. 25th July 2009".
1344 // http://jsat.ewi.tudelft.nl/addendum/Bjork_encoding.pdf
1346 std::vector
<int> formula
;
1348 // add at-leat-one constraint
1349 if (max_only
== false)
1350 formula
.push_back(expression(OpOr
, vec
));
1352 // create binary vector
1353 int num_bits
= ceil(log2(vec
.size()));
1354 std::vector
<int> bits
;
1355 for (int k
= 0; k
< num_bits
; k
++)
1356 bits
.push_back(literal());
1358 // add at-most-one clauses using binary encoding
1359 for (size_t i
= 0; i
< vec
.size(); i
++)
1360 for (int k
= 0; k
< num_bits
; k
++) {
1361 std::vector
<int> clause
;
1362 clause
.push_back(NOT(vec
[i
]));
1363 clause
.push_back((i
& (1 << k
)) != 0 ? bits
[k
] : NOT(bits
[k
]));
1364 formula
.push_back(expression(OpOr
, clause
));
1367 return expression(OpAnd
, formula
);
1370 int ezSAT::manyhot(const std::vector
<int> &vec
, int min_hot
, int max_hot
)
1372 // many-hot encoding using a simple sorting network
1377 std::vector
<int> formula
;
1378 int M
= max_hot
+1, N
= vec
.size();
1379 std::map
<std::pair
<int,int>, int> x
;
1381 for (int i
= -1; i
< N
; i
++)
1382 for (int j
= -1; j
< M
; j
++)
1383 x
[std::pair
<int,int>(i
,j
)] = j
< 0 ? CONST_TRUE
: i
< 0 ? CONST_FALSE
: literal();
1385 for (int i
= 0; i
< N
; i
++)
1386 for (int j
= 0; j
< M
; j
++) {
1387 formula
.push_back(OR(NOT(vec
[i
]), x
[std::pair
<int,int>(i
-1,j
-1)], NOT(x
[std::pair
<int,int>(i
,j
)])));
1388 formula
.push_back(OR(NOT(vec
[i
]), NOT(x
[std::pair
<int,int>(i
-1,j
-1)]), x
[std::pair
<int,int>(i
,j
)]));
1389 formula
.push_back(OR(vec
[i
], x
[std::pair
<int,int>(i
-1,j
)], NOT(x
[std::pair
<int,int>(i
,j
)])));
1390 formula
.push_back(OR(vec
[i
], NOT(x
[std::pair
<int,int>(i
-1,j
)]), x
[std::pair
<int,int>(i
,j
)]));
1392 // explicit resolution clauses -- in tests it was better to let the sat solver figure those out
1393 formula
.push_back(OR(NOT(x
[std::pair
<int,int>(i
-1,j
-1)]), NOT(x
[std::pair
<int,int>(i
-1,j
)]), x
[std::pair
<int,int>(i
,j
)]));
1394 formula
.push_back(OR(x
[std::pair
<int,int>(i
-1,j
-1)], x
[std::pair
<int,int>(i
-1,j
)], NOT(x
[std::pair
<int,int>(i
,j
)])));
1398 for (int j
= 0; j
< M
; j
++) {
1400 formula
.push_back(x
[std::pair
<int,int>(N
-1,j
)]);
1401 else if (j
+1 > max_hot
)
1402 formula
.push_back(NOT(x
[std::pair
<int,int>(N
-1,j
)]));
1405 return expression(OpAnd
, formula
);
1408 int ezSAT::ordered(const std::vector
<int> &vec1
, const std::vector
<int> &vec2
, bool allow_equal
)
1410 std::vector
<int> formula
;
1411 int last_x
= CONST_FALSE
;
1413 assert(vec1
.size() == vec2
.size());
1414 for (size_t i
= 0; i
< vec1
.size(); i
++)
1416 int a
= vec1
[i
], b
= vec2
[i
];
1417 formula
.push_back(OR(NOT(a
), b
, last_x
));
1419 int next_x
= i
+1 < vec1
.size() ? literal() : allow_equal
? CONST_FALSE
: CONST_TRUE
;
1420 formula
.push_back(OR(a
, b
, last_x
, NOT(next_x
)));
1421 formula
.push_back(OR(NOT(a
), NOT(b
), last_x
, NOT(next_x
)));
1425 return expression(OpAnd
, formula
);