GLIFT Simulation

glift.cpp

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string.h>
#include <fstream>
#include <queue>
#include <ctime> 
#include <algorithm>

using namespace std;

#define pii pair<int,int>

pii AND(pii x, pii y) {
  pii Output;
  Output.first = (x.first & y.first);
  Output.second = ((x.second & y.second) | (x.first & (1-x.second) & y.second) | (y.first & x.second & (1-y.second)));
  return Output;
}

pii OR(pii x, pii y) {
  pii Output;
  Output.first = (x.first | y.first);
  Output.second = ((x.second & y.second) | (x.second & (1-y.second) & (1-y.first)));
  return Output;
}

pii NOT(pii x) {
  pii Output;
  Output.first = 1-x.first;
  Output.second = x.second;
  return Output;
}

pii XOR(pii x, pii y) {
  pii Output;
  Output.first = (x.first ^ y.first);
  Output.second = (x.second & y.second);
  return Output;
}

typedef struct { 
  int in1Type, in2Type; // input can come from input wires or gates
  int in1Index, in2Index; // index of input wires or gates
  pii outValue; // output value of a gate
}gateValue;

typedef struct {
  int in1, in2; // input 1's id, input 2's id
  int out; // output id
  int type; // 0 for AND, 1 for OR, 2 for NOT, 3 for XOR
  int level;
  int count;
  gateValue *gV;
}gate;

gate* newGate(int in1, int in2, int out, int type) {
  gate *newG = (gate*) malloc(sizeof(gate));
  newG->in1 = in1;
  newG->in2 = in2;
  newG->out = out;
  newG->type = type;
  gateValue *gV = (gateValue*) malloc(sizeof(gateValue));
  gV->outValue = make_pair(-1,1);
  newG->gV = gV;
  return newG;
}

void simulate(vector< pii > &InputVector, vector< vector<int> > &Level, vector<gate*> &Gates) {
  for (int i = 0; i < Level.size(); i++) {
    for (int j = 0; j < Level[i].size(); j++) {
      pii x,y;
      if (Gates[Level[i][j]]->gV->in1Type == 1)
	x = InputVector[Gates[Level[i][j]]->gV->in1Index];
      else 
	x = Gates[Gates[Level[i][j]]->gV->in1Index]->gV->outValue;
      if (Gates[Level[i][j]]->type != 2) {
	if (Gates[Level[i][j]]->gV->in2Type == 1) 
	  y = InputVector[Gates[Level[i][j]]->gV->in2Index];
	else
	  y = Gates[Gates[Level[i][j]]->gV->in2Index]->gV->outValue;
      }
      // actual computing of values of respective gates
      if (Gates[Level[i][j]]->type == 0) 
	Gates[Level[i][j]]->gV->outValue = AND(x,y);
      if (Gates[Level[i][j]]->type == 1)
	Gates[Level[i][j]]->gV->outValue = OR(x,y);
      if (Gates[Level[i][j]]->type == 2)
	Gates[Level[i][j]]->gV->outValue = NOT(x);
      if (Gates[Level[i][j]]->type == 3)
	Gates[Level[i][j]]->gV->outValue = XOR(x,y);
    }
  }
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    cout << "Usage: ./a.out <cktFile.txt>" << endl;
    exit(-1);
  }
  ifstream cktFile;
  cktFile.open(argv[1]);

  int inN, outN, gN; // number of inputs, outputs, and gates respectively
  cktFile >> inN >> outN >> gN;

  vector<int> Input(inN), Output(outN); // array(vector) of inputs and outputs
  vector<gate*> Gates(gN); // array of pointers to gates
  vector< vector<int> > AdjList(gN); // adjacency list of gates

  char ch;
  //input INPUTS
  for (int i = 0; i < inN; i++) 
    cktFile >> Input[i];

  //input OUTPUTs
  for (int i = 0; i < outN; i++) 
    cktFile >> Output[i];

  // input Gates
  int in1, in2, out;
  char c[4];
  int type;
  for (int i = 0; i < gN; i++) {
    cktFile >> out;
    cktFile >> ch;
    cktFile >> c[0] >> c[1] >> c[2];
    c[3] = '\0';
    if (strcmp(c,"AND") == 0) {
      cktFile >> ch;
      cktFile >> in1;
      cktFile >> ch;
      cktFile >> in2;
      cktFile >> ch;
      Gates[i] = newGate(in1, in2, out, 0);
    }
    else if (c[0] == 'O') {
      cktFile >> in1;
      cktFile >> ch;
      cktFile >> in2;
      cktFile >> ch;
      Gates[i] = newGate(in1, in2, out, 1);
    }
    else if (strcmp(c,"NOT") == 0) {
      cktFile >> ch;
      cktFile >> in1;
      cktFile >> ch;
      Gates[i] = newGate(in1, -1, out, 2);
    }
    else {
      cktFile >> ch;
      cktFile >> in1;
      cktFile >> ch;
      cktFile >> in2;
      cktFile >> ch;
      Gates[i] = newGate(in1, in2, out, 3);
    }
  }

  //output gates
  vector<int> OutputGates(outN);
  for (int i = 0; i < outN; i++) {
    for (int j = 0; j < gN; j++) {
      if (Gates[j]->out == Output[i]) {
	OutputGates[i] = j;
	break;
      }
    }
  }

  // creating adjacency list of gates..
  for (int i = 0; i < gN; i++) 
    for (int j = 0; j < gN; j++)
      if (Gates[i]->out == Gates[j]->in1 || Gates[i]->out == Gates[j]->in2)
	AdjList[i].push_back(j);
  
  vector<int> rootGates;
  //vector< pii > rootGatesinput;
  int input1, input2;
  for (int i = 0; i < gN; i++) {
    for (int j = 0; j < inN; j++) {
      if (Gates[i]->type == 2 && Gates[i]->in1 == Input[j]) {
	Gates[i]->count = 1;
	Gates[i]->gV->in1Type = 1;
	Gates[i]->gV->in1Index = j;
	rootGates.push_back(i);
	Gates[i]->level = 1;
	//rootGatesinput.push_back(make_pair(j,-1));
	break;
      }
      if (Input[j] == Gates[i]->in1) {
	Gates[i]->gV->in1Type = 1;
	Gates[i]->gV->in1Index = j;
	input1 = j;
	Gates[i]->count += 1;
      }
      if (Input[j] == Gates[i]->in2) {
	Gates[i]->gV->in2Type = 1;
	Gates[i]->gV->in2Index = j;
	input2 = j;
	Gates[i]->count += 1;
      }
    }
    if (Gates[i]->count == 2) {
      rootGates.push_back(i);
      Gates[i]->level = 1;
      //rootGatesinput.push_back(make_pair(input1,input2));
    }
  }

    queue<int> currentGates;
    for (int i = 0; i < rootGates.size(); i++) 
      currentGates.push(rootGates[i]);

    int g;
    // Breadth First Search, where rootGates are the roots
    while (currentGates.size() != 0) {
      g = currentGates.front();
      for (int i = 0; i < AdjList[g].size(); i++) {
	if (Gates[AdjList[g][i]]->type == 2) {
	  Gates[AdjList[g][i]]->gV->in1Type = 2;
	  Gates[AdjList[g][i]]->gV->in1Index = g;
	  Gates[AdjList[g][i]]->level = Gates[g]->level + 1;
	  currentGates.push(AdjList[g][i]);
	}
	else {
	  if (Gates[g]->out == Gates[AdjList[g][i]]->in1 && Gates[g]->out == Gates[AdjList[g][i]]->in2) {
	    Gates[AdjList[g][i]]->count += 2;
	    Gates[AdjList[g][i]]->gV->in1Type = 2;
	    Gates[AdjList[g][i]]->gV->in2Type = 2;
	    Gates[AdjList[g][i]]->gV->in1Index = Gates[AdjList[g][i]]->gV->in2Index = g;
	  }
	  else {
	    Gates[AdjList[g][i]]->count += 1;
	    if (Gates[g]->out == Gates[AdjList[g][i]]->in1) {
	      Gates[AdjList[g][i]]->gV->in1Type = 2;
	      Gates[AdjList[g][i]]->gV->in1Index = g;
	    }
	    else {
	      Gates[AdjList[g][i]]->gV->in2Type = 2;
	      Gates[AdjList[g][i]]->gV->in2Index = g;
	    }
	  }
	  if (Gates[AdjList[g][i]]->count == 2) {
	    Gates[AdjList[g][i]]->level = Gates[g]->level + 1;
	    currentGates.push(AdjList[g][i]);
	  }	
	}
      }
      currentGates.pop();
    }
    
    int maxLevel = 0; 
    for (int i = 0; i < Gates.size(); i++) 
      if (Gates[i]->level > maxLevel)
	maxLevel = Gates[i]->level;
    
    vector< vector<int> > Level(maxLevel);
    
    for (int i = 0; i < Gates.size(); i++) 
      Level[Gates[i]->level-1].push_back(i);

   
    srand((unsigned)time(NULL));
    vector< pii > IV(Input.size());
    for (int i = 0; i < IV.size(); i++)
      IV[i] = make_pair(rand()%2,0);

    simulate(IV,Level,Gates);

    for (int i = 0; i < IV.size(); i++)
      cout << IV[i].first << " ";
    cout << endl;

    for (int i = 0; i < OutputGates.size(); i++)
      cout << "(" << Gates[OutputGates[i]]->gV->outValue.first << "," << Gates[OutputGates[i]]->gV->outValue.second << ")" << " ";
    cout << endl;
  
}