summaryrefslogtreecommitdiff
path: root/libs/ezsat/ezsat.h
blob: 16f940a1d98d403ced6852cf0483e9f85479a3b6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
/*
 *  ezSAT -- A simple and easy to use CNF generator for SAT solvers
 *
 *  Copyright (C) 2013  Clifford Wolf <clifford@clifford.at>
 *  
 *  Permission to use, copy, modify, and/or distribute this software for any
 *  purpose with or without fee is hereby granted, provided that the above
 *  copyright notice and this permission notice appear in all copies.
 *  
 *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 */

#ifndef EZSAT_H
#define EZSAT_H

#include <set>
#include <map>
#include <vector>
#include <string>
#include <stdio.h>

class ezSAT
{
	// each token (terminal or non-terminal) is represented by an interger number
	//
	// the zero token:
	// the number zero is not used as valid token number and is used to encode
	// unused parameters for the functions.
	//
	// positive numbers are literals, with 1 = TRUE and 2 = FALSE;
	//
	// negative numbers are non-literal expressions. each expression is represented
	// by an operator id and a list of expressions (literals or non-literals).

public:
	enum OpId {
		OpNot, OpAnd, OpOr, OpXor, OpIFF, OpITE
	};

	static const int TRUE;
	static const int FALSE;

private:
	std::map<std::string, int> literalsCache;
	std::vector<std::string> literals;

	std::map<std::pair<OpId, std::vector<int>>, int> expressionsCache;
	std::vector<std::pair<OpId, std::vector<int>>> expressions;

	bool cnfConsumed;
	int cnfVariableCount, cnfClausesCount;
	std::vector<int> cnfLiteralVariables, cnfExpressionVariables;
	std::vector<std::vector<int>> cnfClauses;

	void add_clause(const std::vector<int> &args);
	void add_clause(const std::vector<int> &args, bool argsPolarity, int a = 0, int b = 0, int c = 0);
	void add_clause(int a, int b = 0, int c = 0);

	int bind_cnf_not(const std::vector<int> &args);
	int bind_cnf_and(const std::vector<int> &args);
	int bind_cnf_or(const std::vector<int> &args);

public:
	int solverTimeout;
	bool solverTimoutStatus;

	ezSAT();
	virtual ~ezSAT();

	// manage expressions

	int value(bool val);
	int literal();
	int literal(const std::string &name);
	int expression(OpId op, int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0);
	int expression(OpId op, const std::vector<int> &args);

	void lookup_literal(int id, std::string &name) const;
	const std::string &lookup_literal(int id) const;

	void lookup_expression(int id, OpId &op, std::vector<int> &args) const;
	const std::vector<int> &lookup_expression(int id, OpId &op) const;

	int parse_string(const std::string &text);
	std::string to_string(int id) const;

	int numLiterals() const { return literals.size(); }
	int numExpressions() const { return expressions.size(); }

	int eval(int id, const std::vector<int> &values) const;

	// SAT solver interface
	// If you are planning on using the solver API (and not simply create a CNF) you must use a child class
	// of ezSAT that actually implements a solver backend, such as ezMiniSAT (see ezminisat.h).

	virtual bool solver(const std::vector<int> &modelExpressions, std::vector<bool> &modelValues, const std::vector<int> &assumptions);

	bool solve(const std::vector<int> &modelExpressions, std::vector<bool> &modelValues, const std::vector<int> &assumptions) {
		return solver(modelExpressions, modelValues, assumptions);
	}

	bool solve(const std::vector<int> &modelExpressions, std::vector<bool> &modelValues, int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0) {
		std::vector<int> assumptions;
		if (a != 0) assumptions.push_back(a);
		if (b != 0) assumptions.push_back(b);
		if (c != 0) assumptions.push_back(c);
		if (d != 0) assumptions.push_back(d);
		if (e != 0) assumptions.push_back(e);
		if (f != 0) assumptions.push_back(f);
		return solver(modelExpressions, modelValues, assumptions);
	}

	bool solve(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0) {
		std::vector<int> assumptions, modelExpressions;
		std::vector<bool> modelValues;
		if (a != 0) assumptions.push_back(a);
		if (b != 0) assumptions.push_back(b);
		if (c != 0) assumptions.push_back(c);
		if (d != 0) assumptions.push_back(d);
		if (e != 0) assumptions.push_back(e);
		if (f != 0) assumptions.push_back(f);
		return solver(modelExpressions, modelValues, assumptions);
	}

	void setSolverTimeout(int newTimeoutSeconds) {
		solverTimeout = newTimeoutSeconds;
	}

	bool getSolverTimoutStatus() {
		return solverTimoutStatus;
	}

	// manage CNF (usually only accessed by SAT solvers)

	virtual void clear();
	virtual void freeze(int id);
	virtual bool eliminated(int idx);
	void assume(int id);
	int bind(int id);
	int bound(int id) const;

	int numCnfVariables() const { return cnfVariableCount; }
	int numCnfClauses() const { return cnfClausesCount; }
	const std::vector<std::vector<int>> &cnf() const { return cnfClauses; }

	void consumeCnf();
	void consumeCnf(std::vector<std::vector<int>> &cnf);

	std::string cnfLiteralInfo(int idx) const;

	// simple helpers for build expressions easily

	struct _V {
		int id;
		std::string name;
		_V(int id) : id(id) { }
		_V(const char *name) : id(0), name(name) { }
		_V(const std::string &name) : id(0), name(name) { }
		int get(ezSAT *that) {
			if (name.empty())
				return id;
			return that->literal(name);
		}
	};

	int VAR(_V a) {
		return a.get(this);
	}

	int NOT(_V a) {
		return expression(OpNot, a.get(this));
	}

	int AND(_V a = 0, _V b = 0, _V c = 0, _V d = 0, _V e = 0, _V f = 0) {
		return expression(OpAnd, a.get(this), b.get(this), c.get(this), d.get(this), e.get(this), f.get(this));
	}

	int OR(_V a = 0, _V b = 0, _V c = 0, _V d = 0, _V e = 0, _V f = 0) {
		return expression(OpOr, a.get(this), b.get(this), c.get(this), d.get(this), e.get(this), f.get(this));
	}

	int XOR(_V a = 0, _V b = 0, _V c = 0, _V d = 0, _V e = 0, _V f = 0) {
		return expression(OpXor, a.get(this), b.get(this), c.get(this), d.get(this), e.get(this), f.get(this));
	}

	int IFF(_V a, _V b = 0, _V c = 0, _V d = 0, _V e = 0, _V f = 0) {
		return expression(OpIFF, a.get(this), b.get(this), c.get(this), d.get(this), e.get(this), f.get(this));
	}

	int ITE(_V a, _V b, _V c) {
		return expression(OpITE, a.get(this), b.get(this), c.get(this));
	}

	void SET(_V a, _V b) {
		assume(IFF(a.get(this), b.get(this)));
	}

	// simple helpers for building expressions with bit vectors

	std::vector<int> vec_const(const std::vector<bool> &bits);
	std::vector<int> vec_const_signed(int64_t value, int numBits);
	std::vector<int> vec_const_unsigned(uint64_t value, int numBits);
	std::vector<int> vec_var(int numBits);
	std::vector<int> vec_var(std::string name, int numBits);
	std::vector<int> vec_cast(const std::vector<int> &vec1, int toBits, bool signExtend = false);

	std::vector<int> vec_not(const std::vector<int> &vec1);
	std::vector<int> vec_and(const std::vector<int> &vec1, const std::vector<int> &vec2);
	std::vector<int> vec_or(const std::vector<int> &vec1, const std::vector<int> &vec2);
	std::vector<int> vec_xor(const std::vector<int> &vec1, const std::vector<int> &vec2);

	std::vector<int> vec_iff(const std::vector<int> &vec1, const std::vector<int> &vec2);
	std::vector<int> vec_ite(const std::vector<int> &vec1, const std::vector<int> &vec2, const std::vector<int> &vec3);
	std::vector<int> vec_ite(int sel, const std::vector<int> &vec2, const std::vector<int> &vec3);

	std::vector<int> vec_count(const std::vector<int> &vec, int numBits, bool clip = true);
	std::vector<int> vec_add(const std::vector<int> &vec1, const std::vector<int> &vec2);
	std::vector<int> vec_sub(const std::vector<int> &vec1, const std::vector<int> &vec2);
	std::vector<int> vec_neg(const std::vector<int> &vec);

	void vec_cmp(const std::vector<int> &vec1, const std::vector<int> &vec2, int &carry, int &overflow, int &sign, int &zero);

	int vec_lt_signed(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_le_signed(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_ge_signed(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_gt_signed(const std::vector<int> &vec1, const std::vector<int> &vec2);

	int vec_lt_unsigned(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_le_unsigned(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_ge_unsigned(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_gt_unsigned(const std::vector<int> &vec1, const std::vector<int> &vec2);

	int vec_eq(const std::vector<int> &vec1, const std::vector<int> &vec2);
	int vec_ne(const std::vector<int> &vec1, const std::vector<int> &vec2);

	std::vector<int> vec_shl(const std::vector<int> &vec1, int shift, bool signExtend = false);
	std::vector<int> vec_srl(const std::vector<int> &vec1, int shift);

	std::vector<int> vec_shr(const std::vector<int> &vec1, int shift, bool signExtend = false) { return vec_shl(vec1, -shift, signExtend); }
	std::vector<int> vec_srr(const std::vector<int> &vec1, int shift) { return vec_srl(vec1, -shift); }

	void vec_append(std::vector<int> &vec, const std::vector<int> &vec1) const;
	void vec_append_signed(std::vector<int> &vec, const std::vector<int> &vec1, int64_t value);
	void vec_append_unsigned(std::vector<int> &vec, const std::vector<int> &vec1, uint64_t value);

	int64_t vec_model_get_signed(const std::vector<int> &modelExpressions, const std::vector<bool> &modelValues, const std::vector<int> &vec1) const;
	uint64_t vec_model_get_unsigned(const std::vector<int> &modelExpressions, const std::vector<bool> &modelValues, const std::vector<int> &vec1) const;

	int vec_reduce_and(const std::vector<int> &vec1);
	int vec_reduce_or(const std::vector<int> &vec1);

	void vec_set(const std::vector<int> &vec1, const std::vector<int> &vec2);
	void vec_set_signed(const std::vector<int> &vec1, int64_t value);
	void vec_set_unsigned(const std::vector<int> &vec1, uint64_t value);

	// helpers for generating ezSATbit and ezSATvec objects

	struct ezSATbit bit(_V a);
	struct ezSATvec vec(const std::vector<int> &vec);

	// printing CNF and internal state

	void printDIMACS(FILE *f, bool verbose = false) const;
	void printInternalState(FILE *f) const;

	// more sophisticated constraints (designed to be used directly with assume(..))

	int onehot(const std::vector<int> &vec, bool max_only = false);
	int manyhot(const std::vector<int> &vec, int min_hot, int max_hot = -1);
	int ordered(const std::vector<int> &vec1, const std::vector<int> &vec2, bool allow_equal = true);
};

// helper classes for using operator overloading when generating complex expressions

struct ezSATbit
{
	ezSAT &sat;
	int id;

	ezSATbit(ezSAT &sat, ezSAT::_V a) : sat(sat), id(sat.VAR(a)) { }

	ezSATbit operator ~() { return ezSATbit(sat, sat.NOT(id)); }
	ezSATbit operator &(const ezSATbit &other) { return ezSATbit(sat, sat.AND(id, other.id)); }
	ezSATbit operator |(const ezSATbit &other) { return ezSATbit(sat, sat.OR(id, other.id)); }
	ezSATbit operator ^(const ezSATbit &other) { return ezSATbit(sat, sat.XOR(id, other.id)); }
	ezSATbit operator ==(const ezSATbit &other) { return ezSATbit(sat, sat.IFF(id, other.id)); }
	ezSATbit operator !=(const ezSATbit &other) { return ezSATbit(sat, sat.NOT(sat.IFF(id, other.id))); }

	operator int() const { return id; }
	operator ezSAT::_V() const { return ezSAT::_V(id); }
	operator std::vector<int>() const { return std::vector<int>(1, id); }
};

struct ezSATvec
{
	ezSAT &sat;
	std::vector<int> vec;

	ezSATvec(ezSAT &sat, const std::vector<int> &vec) : sat(sat), vec(vec) { }

	ezSATvec operator ~() { return ezSATvec(sat, sat.vec_not(vec)); }
	ezSATvec operator -() { return ezSATvec(sat, sat.vec_neg(vec)); }

	ezSATvec operator &(const ezSATvec &other) { return ezSATvec(sat, sat.vec_and(vec, other.vec)); }
	ezSATvec operator |(const ezSATvec &other) { return ezSATvec(sat, sat.vec_or(vec, other.vec)); }
	ezSATvec operator ^(const ezSATvec &other) { return ezSATvec(sat, sat.vec_xor(vec, other.vec)); }

	ezSATvec operator +(const ezSATvec &other) { return ezSATvec(sat, sat.vec_add(vec, other.vec)); }
	ezSATvec operator -(const ezSATvec &other) { return ezSATvec(sat, sat.vec_sub(vec, other.vec)); }

	ezSATbit operator < (const ezSATvec &other) { return ezSATbit(sat, sat.vec_lt_unsigned(vec, other.vec)); }
	ezSATbit operator <=(const ezSATvec &other) { return ezSATbit(sat, sat.vec_le_unsigned(vec, other.vec)); }
	ezSATbit operator ==(const ezSATvec &other) { return ezSATbit(sat, sat.vec_eq(vec, other.vec)); }
	ezSATbit operator !=(const ezSATvec &other) { return ezSATbit(sat, sat.vec_ne(vec, other.vec)); }
	ezSATbit operator >=(const ezSATvec &other) { return ezSATbit(sat, sat.vec_ge_unsigned(vec, other.vec)); }
	ezSATbit operator > (const ezSATvec &other) { return ezSATbit(sat, sat.vec_gt_unsigned(vec, other.vec)); }

	ezSATvec operator <<(int shift) { return ezSATvec(sat, sat.vec_shl(vec, shift)); }
	ezSATvec operator >>(int shift) { return ezSATvec(sat, sat.vec_shr(vec, shift)); }

	operator std::vector<int>() const { return vec; }
};

#endif