Instructions
Requirements and Specifications
Source Code
#include
#include
#include
typedef enum { AND, OR, NAND, NOR, XOR, NOT, PASS, DECODER, MULTIPLEXER } kind_t;
char *gate_name[9] =
{"AND", "OR", "NAND", "NOR", "XOR", "NOT", "PASS", "DECODER", "MULTIPLEXER"};
typedef struct gate {
kind_t kind;
int size; // indicates size of DECODER and MULTIPLEXER
int *params; // length determined by kind and size;
// includes inputs and outputs, indicated by variable numbers
}Gate;
typedef struct variable {
char *name; // variable name
int value; // current value
int out; // flag to indicate if it's an output for a gate or the circuit
}Variable;
typedef struct circuit {
int ninputs; // number of inputs
int *inputs; // input variable positions
int noutputs; // number of outputs
int *outputs; // output variable positions
int ngates; // number of gates
Gate **gates; // list of gates
int nvars; // number of variables
Variable **vars; // variables
}Circuit;
/* Free all the memory allocated by a variable */
void free_variable(Variable *var)
{
if (var != NULL)
{
if (var->name != NULL)
free(var->name);
free(var);
}
}
/* Free all the memory allocated by a gate */
void free_gate(Gate *gate)
{
if (gate != NULL)
{
if (gate->params != NULL)
free(gate->params);
free(gate);
}
}
/* Free all the memory allocated by the circuit */
void free_circuit(Circuit *circ)
{
int i;
if (circ != NULL)
{
if (circ->ninputs && circ->inputs != NULL)
free(circ->inputs);
if (circ->noutputs && circ->outputs != NULL)
free(circ->outputs);
if (circ->vars != NULL)
{
for (i = 0; i < circ->nvars; i++)
free_variable(circ->vars[i]);
free(circ->vars);
}
if (circ->gates != NULL)
{
for (i = 0; i < circ->ngates; i++)
free_gate(circ->gates[i]);
free(circ->gates);
}
free(circ);
}
}
/* Searches a variable in the variable list for the circuit, returns its position
or -1 if not found
*/
int search_variable(char *var, Circuit *circ)
{
int i, index = -1;
for (i = 0; i < circ->nvars && index == -1; i++)
{
if (!strcmp(var, circ->vars[i]->name))
index = i;
}
return index;
}
/* Create a new variable */
Variable *new_variable(char *name, Circuit *circ)
{
Variable *var = (Variable *) malloc(sizeof(Variable));
if (var == NULL)
{
printf("ERROR: Out of memory while creating variable\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
var->name = (char *) malloc(strlen(name) + 1);
if (var->name == NULL)
{
printf("ERROR: Out of memory while creating variable\n");
free(var);
free_circuit(circ);
exit(EXIT_FAILURE);
}
strcpy(var->name, name); // save variable name
var->value = -1; // undefined
var->out = 0; // not out
return var;
}
/* Adds a variable to the variable list in the circuit, returns its position.
It avoids adding repeated variable names */
int add_variable(char *var_name, Circuit *circ)
{
int n;
Variable **vars;
n = search_variable(var_name, circ);
if (n == -1) // if new variable
{
n = circ->nvars;
if (n == 0)
vars = (Variable **) malloc(sizeof(Variable *));
else
vars = (Variable **) realloc(circ->vars, (n + 1) * sizeof(Variable *));
if (vars == NULL)
{
printf("ERROR: Out of memory while creating variable\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
circ->vars = vars;
circ->vars[n] = new_variable(var_name, circ);
circ->nvars++; // increment number of variables
}
return n; // return position of variable
}
/* Create a new circuit */
Circuit *new_circuit()
{
int i;
Circuit *circ = (Circuit *) malloc(sizeof(Circuit));
if (circ == NULL)
{
printf("ERROR: Out of memory while creating circuit\n");
exit(EXIT_FAILURE);
}
/* set all entries to zero */
memset(circ, 0, sizeof(Circuit));
i = add_variable("0", circ); // add the zero constant
circ->vars[i]->value = 0; // always zero
i = add_variable("1", circ); // add the one constant
circ->vars[i]->value = 1; // always one
add_variable("_", circ); // add the dummy var
return circ;
}
/* Create a new gate of n parameters and given kind */
Gate *new_gate(kind_t kind, int n, int size, Circuit *circ)
{
Gate *gate = (Gate *) malloc(sizeof(Gate));
if (gate == NULL)
{
printf("ERROR: Out of memory while creating gate\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
gate->kind = kind;
gate->params = (int *) malloc(n *sizeof(int *));
if (gate->params == NULL)
{
printf("ERROR: Out of memory while creating gate\n");
free(gate);
free_circuit(circ);
exit(EXIT_FAILURE);
}
gate->size = size;
return gate;
}
/* Adds a gate to the gate list in the circuit. */
void add_gate(Gate *gate, Circuit *circ)
{
int n;
n = circ->ngates;
Gate **gates;
if (n == 0)
gates = (Gate **) malloc(sizeof(Gate *));
else
gates = (Gate **) realloc(circ->gates, (n + 1) * sizeof(Gate *));
if (gates == NULL)
{
printf("ERROR: Out of memory while creating gate\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
circ->gates = gates;
circ->gates[n] = gate; // save gate
circ->ngates++; // increment number of gates
}
/* Loads a circuit from the given file and returns it */
Circuit *load_circuit(char *filename)
{
FILE *f;
char buffer[20];
int i, j, n, size;
kind_t kind;
Circuit *circ;
Gate *gate;
int outi, nouts;
f = fopen(filename, "rt"); // open file as read only text
if (f == NULL) // if file was not open
{
printf("ERROR: Unable to open file: \"%s\"\n", filename);
exit(EXIT_FAILURE); // terminate program
}
// create new circuit
circ = new_circuit();
// read input variables, it must be at start
fscanf(f, "%16s %d", buffer, &circ->ninputs); // read
if (strcmp(buffer, "INPUT"))
{
printf("ERROR: INPUT was not the first directive in the file\n");
exit(EXIT_FAILURE);
}
circ->inputs = (int *) malloc(circ->ninputs*sizeof(int)); // allocate space for inputs
if (circ->inputs == NULL)
{
printf("ERROR: Out of memory while creating circuit inputs\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
// read inputs
for (i = 0; i < circ->ninputs; i++)
{
if (fscanf(f, "%16s", buffer) != 1) // read variable
{
printf("ERROR: INPUT expected a variable name\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
n = add_variable(buffer, circ);
circ->inputs[i] = n; // save variable position
}
// read output variables, it must be after input
fscanf(f, "%16s %d", buffer, &circ->noutputs); // read
if (strcmp(buffer, "OUTPUT"))
{
printf("ERROR: OUTPUT was not the second directive in the file\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
circ->outputs = (int *) malloc(circ->noutputs*sizeof(int)); // allocate space for outputs
if (circ->outputs == NULL)
{
printf("ERROR: Out of memory while creating circuit outputs\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
// read outputs
for (i = 0; i < circ->noutputs; i++)
{
if (fscanf(f, "%16s", buffer) != 1) // read variable
{
printf("ERROR: OUTPUT expected a variable name\n");
free_circuit(circ);
exit(EXIT_FAILURE);
}
n = add_variable(buffer, circ);
circ->outputs[i] = n; // save variable position
circ->vars[circ->outputs[i]]->out = 1;
}
while (!feof(f)) // read all lines in file
{
if(fscanf(f, "%16s", buffer) == 1) // read directive
{
outi = 2;
nouts = 1;
if (!strcmp(buffer, "NOT"))
{
kind = NOT;
size = 0;
n = 2;
outi = 1;
nouts = 1;
}
if (!strcmp(buffer, "PASS"))
{
kind = PASS;
size = 0;
n = 2;
outi = 1;
nouts = 1;
}
else if (!strcmp(buffer, "AND"))
{
kind = AND;
size = 0;
n = 3;
}
else if (!strcmp(buffer, "OR"))
{
kind = OR;
size = 0;
n = 3;
}
else if (!strcmp(buffer, "NAND"))
{
kind = NAND;
size = 0;
n = 3;
}
else if (!strcmp(buffer, "NOR"))
{
kind = NOR;
size = 0;
n = 3;
}
else if (!strcmp(buffer, "XOR"))
{
kind = XOR;
size = 0;
n = 3;
}
else if (!strcmp(buffer, "DECODER"))
{
kind = DECODER;
fscanf(f, "%d", &size); // read the size
n = size + (1 << size); // n + 2^n parameters
outi = size; // start of outputs
nouts = 1 << size; // size of outputs
}
else if (!strcmp(buffer, "MULTIPLEXER"))
{
kind = MULTIPLEXER;
fscanf(f, "%d", &size); // read the size
n = size + (1 << size) + 1; // n + 2^n + 1 parameters
outi = size + (1 << size); // start of outputs
nouts = 1; // size of outputs
}
// create the gate
gate = new_gate(kind, n, size, circ);
// read parameters
for (i = 0; i < n; i++)
{
if (fscanf(f, "%16s", buffer) != 1) // read variable
{
printf("ERROR: %s expected a variable name\n", gate_name[kind]);
free_gate(gate);
free_circuit(circ);
exit(EXIT_FAILURE);
}
j = add_variable(buffer, circ);
gate->params[i] = j; // save variable position
if (i >= outi && i <= outi + nouts - 1)
circ->vars[j]->out = 1;
}
add_gate(gate, circ); // add gate to circuit
}
}
fclose(f);
return circ;
}
/* get decimal value from a series of consecutive variables in a gate */
int get_dec_value(int start, int end, Gate *gate, Circuit *circ)
{
int i, pow2 = 0;
int val = 0;
for (i = end, pow2 = 0; i >= start && val != -1; i--, pow2++)
{
if (circ->vars[gate->params[i]]->value == -1)
val = -1;
else
val += circ->vars[gate->params[i]]->value << pow2;
}
return val;
}
/* evaluate gate output */
int eval_gate(Gate *gate, Circuit *circ)
{
int a, b;
int i, pos;
int output = -1;
// cache values for 2 input gates
a = circ->vars[gate->params[0]]->value;
b = circ->vars[gate->params[1]]->value;
switch (gate->kind)
{
case AND:
if (a != -1 && b != -1)
output = a & b;
circ->vars[gate->params[2]]->value = output;
break;
case OR:
if (a != -1 && b != -1)
output = a | b;
circ->vars[gate->params[2]]->value = output;
break;
case NAND:
if (a != -1 && b != -1)
output = (~(a & b)) & 1;
circ->vars[gate->params[2]]->value = output;
break;
case NOR:
if (a != -1 && b != -1)
output = (~(a | b)) & 1;
circ->vars[gate->params[2]]->value = output;
break;
case XOR:
if (a != -1 && b != -1)
output = a ^ b;
circ->vars[gate->params[2]]->value = output;
break;
case NOT:
if (a != -1)
output = (~a) & 1;
circ->vars[gate->params[1]]->value = output;
break;
case PASS:
output = a;
circ->vars[gate->params[1]]->value = output;
break;
case DECODER:
pos = get_dec_value(0, gate->size - 1, gate, circ);
if (pos == -1)
{
for (i = 0; i < (1 << gate->size); i++)
circ->vars[gate->params[gate->size + i]]->value = -1;
}
else
{
for (i = 0; i < (1 << gate->size); i++)
circ->vars[gate->params[gate->size + i]]->value = 0;
circ->vars[gate->params[gate->size + pos]]->value = 1;
output = 1;
}
break;
case MULTIPLEXER:
pos = get_dec_value(1 << gate->size, (1 << gate->size) + gate->size - 1, gate, circ);
if (pos == -1)
circ->vars[gate->params[(1 << gate->size) + gate->size]]->value = -1;
else
{
output = circ->vars[gate->params[pos]]->value;
circ->vars[gate->params[(1 << gate->size) + gate->size]]->value = output;
}
break;
}
return output;
}
/* increment input to next value, returns 0 if no error, 1 if all inputs were 1 */
int next_input(Circuit *circ)
{
int i;
int cy = 1;
for (i = circ->ninputs - 1; i >= 0 && cy == 1; i--)
{
if (circ->vars[circ->inputs[i]]->value == 0)
{
circ->vars[circ->inputs[i]]->value = 1;
cy = 0; // don't propagate
}
else
{
circ->vars[circ->inputs[i]]->value = 0;
cy = 1; // propagate to next
}
}
return cy;
}
/* print input values */
void print_inputs(Circuit *circ)
{
int i;
for (i = 0; i < circ->ninputs; i++)
printf("%d ", circ->vars[circ->inputs[i]]->value);
}
/* print output values */
void print_outputs(Circuit *circ)
{
int i;
for (i = 0; i < circ->noutputs; i++)
printf(" %d", circ->vars[circ->outputs[i]]->value);
}
/* returns 1 if all outputs are valid */
int valid_outputs(Circuit *circ)
{
int i;
for (i = 0; i < circ->noutputs; i++)
if (circ->vars[circ->outputs[i]]->value == -1)
return 0;
return 1;
}
/* float all outputs to undefined */
void float_outputs(Circuit *circ)
{
int i;
// float all outputs, ignore the 0, 1 and _ wires
for (i = 3; i < circ->nvars; i++)
if (circ->vars[i]->out)
circ->vars[i]->value = -1;
}
/* evaluate circuit outputs */
void eval_circuit(Circuit *circ)
{
int i;
int cy = 0;
/* set all inputs to zero */
for (i = 0; i < circ->ninputs; i++)
circ->vars[circ->inputs[i]]->value = 0;
while (!cy) // repeat until there's a carry after incrementing input
{
print_inputs(circ);
/* set all outputs to -1 */
float_outputs(circ);
while (!valid_outputs(circ)) // evaluate until all outputs are valid
{
for (i = 0; i < circ->ngates; i++) // evaluate all gates
eval_gate(circ->gates[i], circ); // evaluate gate
}
printf("|");
print_outputs(circ);
printf("\n");
cy = next_input(circ); // get next input state
}
}
int main(int argc, char **argv)
{
Circuit *circ;
if (argc == 1) /* if no input arguments */
{
printf("Usage:\n");
printf(" %s \n", argv[0]);
return EXIT_SUCCESS;
}
else if (argc > 2)
{
printf("Too many arguments\n");
return EXIT_FAILURE;
}
circ = load_circuit(argv[1]); /* load circuit from argument */
eval_circuit(circ);
free_circuit(circ);
return EXIT_SUCCESS;
}