View Javadoc

1   /*
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2006 Daniel Le Berre
3    * 
4    * Based on the original minisat specification from:
5    * 
6    * An extensible SAT solver. Niklas E?n and Niklas S?rensson. Proceedings of the
7    * Sixth International Conference on Theory and Applications of Satisfiability
8    * Testing, LNCS 2919, pp 502-518, 2003.
9    * 
10   * This library is free software; you can redistribute it and/or modify it under
11   * the terms of the GNU Lesser General Public License as published by the Free
12   * Software Foundation; either version 2.1 of the License, or (at your option)
13   * any later version.
14   * 
15   * This library is distributed in the hope that it will be useful, but WITHOUT
16   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17   * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18   * details.
19   * 
20   * You should have received a copy of the GNU Lesser General Public License
21   * along with this library; if not, write to the Free Software Foundation, Inc.,
22   * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23   * 
24   */
25  package org.sat4j.reader;
26  
27  import java.io.IOException;
28  import java.io.InputStream;
29  import java.io.PrintWriter;
30  
31  import org.sat4j.specs.ContradictionException;
32  import org.sat4j.specs.IProblem;
33  import org.sat4j.specs.ISolver;
34  import org.sat4j.tools.GateTranslator;
35  
36  public class AIGReader extends Reader {
37  
38      private final static int FALSE = 0;
39  
40      private final static int TRUE = 1;
41  
42      private final GateTranslator solver;
43  
44      private int maxvarid;
45  
46      private int nbinputs;
47  
48      AIGReader(ISolver s) {
49          solver = new GateTranslator(s);
50      }
51  
52      @Override
53      public String decode(int[] model) {
54          StringBuffer stb = new StringBuffer();
55          for (int i = 0; i < nbinputs; i++) {
56              stb.append(model[i]>0?1:0);
57          }
58          return stb.toString();
59      }
60  
61      @Override
62      public void decode(int[] model, PrintWriter out) {
63          for (int i = 0; i < nbinputs; i++) {
64              out.print(model[i]>0?1:0);
65          }
66      }
67  
68      int parseInt(InputStream in, char expected) throws IOException,
69              ParseFormatException {
70          int res, ch;
71          ch = in.read();
72  
73          if (ch < '0' || ch > '9')
74              throw new ParseFormatException("expected digit");
75          res = ch - '0';
76  
77          while ((ch = in.read()) >= '0' && ch <= '9')
78              res = 10 * res + (ch - '0');
79  
80          if (ch != expected)
81              throw new ParseFormatException("unexpected character");
82  
83          return res;
84      }
85  
86      /*
87       * (non-Javadoc)
88       * 
89       * @see org.sat4j.reader.Reader#parseInstance(java.io.InputStream)
90       */
91      @Override
92      public IProblem parseInstance(InputStream in) throws ParseFormatException,
93              ContradictionException, IOException {
94          if (in.read() != 'a' || in.read() != 'i' || in.read() != 'g'
95                  || in.read() != ' ') {
96              throw new ParseFormatException("AIG format only!");
97          }
98          maxvarid = parseInt(in, ' ');
99          nbinputs = parseInt(in, ' ');
100         int nblatches = parseInt(in, ' ');
101         if (nblatches > 0) {
102             throw new ParseFormatException(
103                     "CNF conversion cannot handle latches!");
104         }
105         int nboutputs = parseInt(in, ' ');
106         if (nboutputs > 1) {
107             throw new ParseFormatException(
108                     "CNF conversion allowed for single output circuit only!");
109         }
110         int nbands = parseInt(in, '\n');
111         solver.newVar(maxvarid + 1);
112         solver.setExpectedNumberOfClauses(3 * nbands + 2);
113         if (nboutputs > 0) {
114             assert nboutputs == 1;
115             int output0 = parseInt(in, '\n');
116             readAnd(nbands, output0, in, 2 * (nbinputs + 1));
117         }
118         return solver;
119     }
120 
121     static int safeGet(InputStream in) throws IOException, ParseFormatException {
122         int ch = in.read();
123         if (ch == -1) {
124             throw new ParseFormatException("AIG Error, EOF met too early");
125         }
126         return ch;
127     }
128 
129     static int decode(InputStream in) throws IOException, ParseFormatException {
130         int x = 0, i = 0;
131         int ch;
132 
133         while (((ch = safeGet(in)) & 0x80) > 0) {
134             System.out.println("=>" + ch);
135             x |= (ch & 0x7f) << (7 * i++);
136         }
137         return x | (ch << (7 * i));
138     }
139 
140     private void readAnd(int nbands, int output0, InputStream in, int startid)
141             throws ContradictionException, IOException, ParseFormatException {
142         int lhs = startid;
143         for (int i = 0; i < nbands; i++) {
144             int delta0 = decode(in);
145             int delta1 = decode(in);
146             int rhs0 = lhs - delta0;
147             int rhs1 = rhs0 - delta1;
148             solver.and(toDimacs(lhs), toDimacs(rhs0), toDimacs(rhs1));
149             lhs += 2;
150         }
151         solver.gateTrue(maxvarid + 1);
152         solver.gateTrue(toDimacs(output0));
153     }
154 
155     private int toDimacs(int v) {
156         if (v == FALSE) {
157             return -(maxvarid + 1);
158         }
159         if (v == TRUE) {
160             return maxvarid + 1;
161         }
162         int var = v >> 1;
163         if ((v & 1) == 0) {
164             return var;
165         }
166         return -var;
167     }
168 
169     @Override
170     public IProblem parseInstance(java.io.Reader in)
171             throws ParseFormatException, ContradictionException, IOException {
172         throw new UnsupportedOperationException();
173     }
174 
175 }