atpg-ls/circuit.cpp

#include "circuit.h"

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include "assert.h"


ll Circuit::stem_total_cost;
int Circuit::stem_falsified_cnt;

ll Circuit::propagate_total_cost;
int Circuit::propagate_falsified_cnt;

ll Circuit::fault_total_cost;
int Circuit::fault_falsified_cnt;

void Circuit::init_stems() {
    
    for(auto& gate: gates) {
        if(gate->outputs.size() >= 2) {
            gate->stem = true;   
        }
        if(gate->stem) {
            stems.push_back(gate);
        }
    }

    for(Gate *g : gates) {
        if(g->pi) continue;
        std::queue<Gate*> q;
        std::unordered_map<Gate*, bool> used;
        q.push(g);

        while(!q.empty()) {
            Gate* now = q.front();
            q.pop();
            for(Gate* in : now->inputs) {
                if(in->stem) {
                    g->pre_stems.push_back(in);
                } else if(!used[in]) {
                    used[in] = true;
                    q.push(in);
                }
            }
        }
        //printf("pre: %s %d\n", g->name.c_str(), g->pre_stems.size());
    }

    for(Gate *g : gates) {
        if(g->po) continue;
        std::queue<Gate*> q;
        std::unordered_map<Gate*, bool> used;
        q.push(g);

        while(!q.empty()) {
            Gate* now = q.front();
            q.pop();
            for(Gate* out : now->outputs) {
                if(out->stem) {
                    g->suc_stems.push_back(out);
                } else if(!used[out]) {
                    used[out] = true;
                    q.push(out);
                }
            }
        }
        //printf("pre: %s %d\n", g->name.c_str(), g->pre_stems.size());
    }
}


void Circuit::init_topo_index() {
    int topo = 1;
    std::queue<Gate*> q;

    std::unordered_map<Gate*, int> ins;
    for(Gate* gate : gates) {
        ins[gate] = gate->inputs.size();
    }

    for(auto in : PIs) {
        in->id = topo++;
        q.push(in);
    }

    while(!q.empty()) {
        Gate* g = q.front(); q.pop();
        for(Gate* out : g->outputs) {
            ins[out]--;
            if(ins[out] == 0) {
                out->id = topo++;
                q.push(out);
            }
        }
    }
}

void Circuit::print_gates() {
    static const char* type2name[9] = {"AND", "NAND", "OR", "NOR", "XOR", "XNOR", "NOT", "BUF", "IN"};
    for(Gate* gate : gates) {
        printf("Gate: %3s (t:%4s v:%d pi:%d po:%d s:%d p:%d s0:%d s1:%d)  Inputs:", gate->name.c_str(), type2name[gate->type], gate->value, gate->pi, gate->po, gate->stem, gate->propagate, gate->fault_satisfied[0], gate->fault_satisfied[1]);
        for(Gate* in : gate->inputs) {
            printf(" %s", in->name.c_str());
        }
        printf("\n");
    }
}

bool Circuit::is_valid_circuit() {

    ll stem_total_cost = 0;
    int stem_falsified_cnt = 0;

    ll propagate_total_cost = 0;
    int propagate_falsified_cnt = 0;

    ll fault_total_cost = 0;
    int fault_falsified_cnt = 0;

    //printf("propagate: %d, stem: %d, fault:%d\n", propagate_total_cost, stem_total_cost, fault_total_cost);

    for(Gate* g : gates) {

        if(g->stem && !g->propagate_satisfied) {
            propagate_total_cost += g->propagate_cost;
            propagate_falsified_cnt += 1;
        }

        bool pro_sat = (g->cal_sa(0) == g->fault_satisfied[0] && g->cal_sa(1) == g->fault_satisfied[1]);

        if(g->stem && g->propagate_satisfied != pro_sat) {
            printf("WRONG-fault_satisfied: %s \n", g->name.c_str());
            return false;
        }

        if(g->stem && g->stem_satisified != (g->cal_value() == g->value)) {
            printf("WRONG-STEM_SATIS: %s \n", g->name.c_str());
            return false;
        }

        if(g->stem && g->cal_value() != g->value) {
            stem_total_cost += g->stem_cost;
            stem_falsified_cnt += 1;
        }

        if(!g->fault_satisfied[0]) {
            fault_total_cost += g->fault_cost[0];
            fault_falsified_cnt += 1;
        }

        if(!g->fault_satisfied[1]) {
            fault_total_cost += g->fault_cost[1];
            fault_falsified_cnt += 1;
        }

        // 检查门的赋值情况
        if(!g->stem && g->cal_value() != g->value) {
            printf("WRONG-ASSGIN: %s \n", g->name.c_str());
            return false;
        }

        // 检查 fault_satified 和 value propagate 的关系

        int sa0 = g->propagate && g->value;
        int sa1 = g->propagate && !g->value;
        assert(g->fault_satisfied[0] == sa0);
        assert(g->fault_satisfied[1] == sa1);
        
        // 检查 PO 的传播设定是否正确
        if(g->po) {
            if(g->fault_satisfied[g->value] || !g->fault_satisfied[!g->value] || !g->propagate) {
                printf("WRONG-PO: %s \n", g->name.c_str());
            }
            continue;
        }

        // 非 PO 情况下检查故障传播是否正确

        if(!g->stem && (g->cal_sa(0) != g->fault_satisfied[0] || g->cal_sa(1) != g->fault_satisfied[1])) {
            printf("WRONG-SA: %s \n", g->name.c_str());
            return false;
        }
    }

    if(Circuit::propagate_total_cost != propagate_total_cost || Circuit::stem_total_cost != stem_total_cost || Circuit::fault_total_cost != fault_total_cost) {
        printf("CIRCUIT CHECK FAILED!\n");
        printf("[wrong] propagate: %lld, stem: %lld, fault:%lld\n", Circuit::propagate_total_cost, Circuit::stem_total_cost, Circuit::fault_total_cost);
        printf("[right] propagate: %lld, stem: %lld, fault:%lld\n", propagate_total_cost, stem_total_cost, fault_total_cost);
        return false;
    }

    if(Circuit::propagate_falsified_cnt != propagate_falsified_cnt || Circuit::stem_falsified_cnt != stem_falsified_cnt || Circuit::fault_falsified_cnt != fault_falsified_cnt) {
        printf("CIRCUIT CHECK FAILED!\n");
        printf("[wrong] propagate_cnt: %d, stem_cnt: %d, fault_cnt:%d\n", Circuit::propagate_falsified_cnt, Circuit::stem_falsified_cnt, Circuit::fault_falsified_cnt);
        printf("[right] propagate_cnt: %d, stem_cnt: %d, fault_cnt:%d\n", propagate_falsified_cnt, stem_falsified_cnt, fault_falsified_cnt);
        return false;
    }

    return true;
}