COS 126 Digital Circuit Simulator Assignment Hints

Part 0: Preparation

The hints for this assignment are fairly extensive, so if you want to really challenge yourself, stop reading here.

We provide a detailed skeleton of the finished program, and the underlying data structures. We also supply the code for input/output, since this can be a tedious and un-gratifying task. In doing so, we hope you can concentrate your efforts on the fun and exciting part - the event driven simulation! Your main challenge will be to understand the code we provide, and write the guts of the event-driven simulation code.

Copy the files in the directory /u/cs126/files/circuit/ to an empty directory, and compile with the command.

gcc126 simulator.c circuit.c boolean.c queuearray.c

To make sure everything is working properly, test out the code with the command

a.out and8way.txt

The program should print out a description of the circuit to the screen.

Part 1: Driver program

The program simulator.c is the main program.

The program call various functions (that will be described later) to: read in the circuit from a file, prompt the user for circuit inputs, and simulate the circuit. To simulate combinational circuits, you will not need to change this file at all.

For sequential circuits, you will later add in a loop to allow the user to enter new circuit inputs upon completion of each simulation. But for now, just leave as is. When you do change it, consider using the following to read in a single character:

scanf(" %c", x);

Pay careful attention to the leading space. It eats up any whitespace, thereby preventing x from storing a whitespace character. (Note, the space is not needed when it precedes %d. Yes, scanf() is a nasty little function.)

The argc and argv[] stuff are needed to process the command-line input. Can you think of a good reason why everything isn't just read in from standard input (with Unix redirection from a file) as usual?

The rest of the code should be pretty self-explanatory.

Part 2: Queue data type

The Queue ADT is copied directly from the lecture notes: QUEUE.h, and queuearray.c. There is no need to modify either of these files.

Part 3: Boolean data type

You may use the following Boolean interface and implementation files as a starting point: BOOLEAN.h, boolean.c. It defines the type Boolean.

typedef enum { FALSE, TRUE, UNKNOWN } Boolean;

You may wish to review declaring types with enum. See King 16.5.

You will need to write the functions BOOLEANand(), BOOLEANor(), and BOOLEANnot() to handle the extended Boolean logic { FALSE, TRUE, UNKNOWN }. Throughly test your code before proceeding.

Part 4: Gate and Circuit data types

The interface and implementation files described below are: CIRCUIT.h, circuit.c.

To implement a Gate, we use the following data structures:

typedef enum { AND, OR, NOT, INPUT, OUTPUT } Gatetype;

typedef struct {
   int in1, in2;                       // two input gates
   int out[MAX_OUTPUTS+1];             // output gates
   Gatetype type;                      // type of gate
   Boolean value;                      // gate output value
} Gate;

The array out[] stores MAX_OUTPUTS + 1 values to accommodate up to MAX_OUTPUTS output wires plus the terminating 0. The functions GATETYPEshow() and GATEshow() are used to print out the contents of one gate to the screen.

A Circuit is an array of Gates. For convenience, we also maintain the number of gates.

typedef struct {
   Gate gates[MAX_GATES+1];
   int n;
} Circuit;

The array gates[] stores MAX_GATES+1 values to accommodate up to MAX_GATES gates plus the dummy gate 0. The functions CIRCUITshow() prints out the contents of a Circuit to standard output. The functions CIRCUITread() reads in the description of a circuit from an input file, and initializes a Circuit variable.

Your first task is to implement CIRCUITgetinputs(). It takes as input a Circuit, and returns the modified Circuit (with the updated input gate values). This function prompts the user to enter values (0 or 1) for each of the circuit input gates (and only these), and sets the value of each gate accordingly. This code should be fairly straightforward.

Your main task is to implement CIRCUITsimulate(). This function performs the event-driven simulation. It takes as input a Circuit, and returns the modified Circuit (with the updated gate values).

The first step is to determine all of the gates that are directly connected to a circuit input. These gates are put onto the queue. Make sure that you get this working before proceeding. You may wish to use QUEUEshow() to display all of the items currently on the queue.

The next step is to delete (get) a gate from the queue. Then, determine the input values for this gate, and use them to compute the new output value. Of course, this will depend on what type of gate you are dealing with.

Finally, if this gate's new output value is different from its old one, you need to determine all of the gates that are directly affected by this change, and insert (put) those gates onto the queue.

Possible gotcha: consider the following code fragment where g is a Gate and c is a Circuit.

g = c.gates[i];
g.value = TRUE;

This does not change the output value of gate i in the circuit; instead it changes the copy g of gate i. To change the gate itself, you could do the following:

c.gates[i].value = TRUE;

but if you are accessing c.gates[i] a lot, this uglifies your code. Instead, you can continue to use g, but assign c.gates[i] the value g when you are done changing it:

c.gates[i] = g;

Kevin Wayne