150 lines
3.6 KiB
C++
150 lines
3.6 KiB
C++
#include "circuit.h"
|
|
|
|
#include <assert.h>
|
|
#include <unordered_map>
|
|
|
|
int cal_value(Gate *g, int *value) {
|
|
int res;
|
|
|
|
switch(g->type) {
|
|
case Gate::NOT:
|
|
res = !value[g->inputs[0]->id];
|
|
break;
|
|
case Gate::BUF:
|
|
res = value[g->inputs[0]->id];
|
|
break;
|
|
case Gate::AND:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res &= value[g->inputs[i]->id];
|
|
}
|
|
break;
|
|
case Gate::NAND:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res &= value[g->inputs[i]->id];
|
|
}
|
|
res = !res;
|
|
break;
|
|
case Gate::OR:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res |= value[g->inputs[i]->id];
|
|
}
|
|
break;
|
|
case Gate::NOR:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res |= value[g->inputs[i]->id];
|
|
}
|
|
res = !res;
|
|
break;
|
|
case Gate::XOR:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res ^= value[g->inputs[i]->id];
|
|
}
|
|
break;
|
|
case Gate::XNOR:
|
|
res = value[g->inputs[0]->id];
|
|
for(int i=1; i<g->inputs.size(); i++) {
|
|
res ^= value[g->inputs[i]->id];
|
|
}
|
|
res = !res;
|
|
break;
|
|
case Gate::INPUT:
|
|
res = value[g->id];
|
|
break;
|
|
default:
|
|
assert(false);
|
|
break;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
bool cal_sa(Gate* g, bool x, int** sa, int *value) {
|
|
if(g->po) {
|
|
if(x == 0) return value[g->id];
|
|
else return !value[g->id];
|
|
}
|
|
|
|
bool sa0 = 0;
|
|
bool sa1 = 0;
|
|
|
|
for(Gate* out : g->outputs) {
|
|
if(!sa[out->id][0] && !sa[out->id][1]) continue;
|
|
|
|
if(cal_value(out, value) != value[out->id]) continue;
|
|
|
|
value[g->id] = !value[g->id];
|
|
bool detect = cal_value(out, value) != value[out->id];
|
|
value[g->id] = !value[g->id];
|
|
if(!detect) continue;
|
|
|
|
sa0 |= value[g->id];
|
|
sa1 |= !value[g->id];
|
|
}
|
|
if(x == 0) return sa0;
|
|
else return sa1;
|
|
}
|
|
|
|
|
|
int** Circuit::simulate() {
|
|
|
|
static bool init = false;
|
|
static int** sa = nullptr;
|
|
static int* value = nullptr;
|
|
|
|
if(!init) {
|
|
const int MAXN = gates.size() + 1;
|
|
init = true;
|
|
sa = new int*[MAXN];
|
|
for(int i=0; i<MAXN; i++) {
|
|
sa[i] = new int[2];
|
|
}
|
|
value = new int[MAXN];
|
|
}
|
|
|
|
// init PI
|
|
for(Gate* pi : PIs) {
|
|
value[pi->id] = pi->value;
|
|
}
|
|
|
|
for(Gate *g : gates) {
|
|
if(g->pi) continue;
|
|
value[g->id] = cal_value(g, value);
|
|
}
|
|
|
|
for(Gate *g : gates) {
|
|
assert(value[g->id] == cal_value(g, value));
|
|
}
|
|
|
|
std::queue<Gate*> q;
|
|
std::unordered_map<Gate*, int> topo;
|
|
|
|
// init PO
|
|
for(Gate* po : POs) {
|
|
sa[po->id][!value[po->id]] = 1;
|
|
sa[po->id][value[po->id]] = 0;
|
|
q.push(po);
|
|
}
|
|
|
|
while(!q.empty()) {
|
|
Gate* g = q.front();
|
|
q.pop();
|
|
for(Gate* in : g->inputs) {
|
|
if(++topo[in] == in->outputs.size()) {
|
|
sa[in->id][0] = cal_sa(in, 0, sa, value);
|
|
sa[in->id][1] = cal_sa(in, 1, sa, value);
|
|
q.push(in);
|
|
}
|
|
}
|
|
}
|
|
|
|
for(Gate* g : gates) {
|
|
assert(sa[g->id][0] == cal_sa(g, 0, sa, value));
|
|
assert(sa[g->id][1] == cal_sa(g, 1, sa, value));
|
|
}
|
|
|
|
return sa;
|
|
} |