Description
This assignment will provide more practice programming in C and working with circuits and
digital logic. It has two parts. In the first part, you will design several circuits using a simple
specification language. In the second part, you will write a program that generates a truth table
given such a circuit specification.
Advice Start working early. Before you do any coding, make sure you can run the auto-grader,
create a Tar archive, and submit that archive to Sakai. You don’t want to discover on the last day
that scp doesn’t work on your personal machine.
Decide your data structures and algorithms first. Section 4 describes one method for implementing
the program that performs well, but you are free to design your own. Writing out pseudocode is not
required, but it may be a good idea.
Start working early. You will almost certainly encounter problems you did not anticipate while
writing this project. It’s much better if you find them in the first week.
1 Overview
You will write a program truthtable that reads a file containing a description of a circuit, and
prints that circuit’s truth table. The files specify (1) the number and names of each input to the
circuit, (2) the number and names of each output from the circuit, and (3) the logic gates and
components that make up the circuit. In order to indicate the connections between gates, each
connection is also given a name.
For example, this is a description for a circuit that implements a 3-argument AND gate:
INPUT 3 a b c
OUTPUT 1 d
AND a b x
AND c x d
Note that it contains three inputs (a, b, and c), a single output (d), and two AND gates, each of
which has two inputs and one output. The variable x indicates an internal connection between the
first AND gate and the second. See section 3 for details on the specification language.
When given this file, truthtable should print:
1
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1
The three columns on the left correspond to the three inputs, and the column to the right corresponds
to the output.
This assignment has two parts:
Part 1 (100 points) For this part, the circuit descriptions will be sorted so that each temporary
variable appears as an output parameter before any appearances as an input variable.
Part 2 (Extra Credit) For this part, the circuit descriptions will not be sorted, meaning that a
temporary variable may be used as an input parameter before its use as an output parameter.
2 Program
truthtable takes a single argument, which is the name of a file containing a circuit description.
The behavior of truthtable is unspecified if it receives no arguments or more than one argument,
but you should still check that the number of arguments is correct. (One possibility is to have
truthtable read from standard input if no file argument is given.)
Usage
$ ./truthtable my-cool-circuit.txt
0 0 | 0 0
0 1 | 0 1
1 0 | 0 1
1 1 | 1 0
Input The input to your program will be a single circuit description using the language described
in section 3. The first argument to truthtable will identify a file containing this circuit description.
You MAY assume that the input is correctly formatted and that no variable depends on its own
output.
Output The output of truthtable is a truth table showing each combination of inputs and the
corresponding output for the specified circuit. Each column in the table corresponds to a specific
input or output variable, which are given in the same order as their declaration in the INPUT and
OUTPUT directives. Columns are separated by a single space, and a vertical bar (|) occurs between
the input and output variables.
Note that no white space follows the final column.
2
3 Specification Language
In this language, circuits are specified with a series of directives. These directives refer to various
named variables, which correspond to wires in a circuit diagram. Many of the directives describe a
logic gate or similar building block, indicating which varibles correspond to its input and output.
Each directive has the form of a name followed by one or more parameters, separated by
whitespace. The name indicates which directive and determines the number of parameters. Some
directives take a variable number of parameters; their first parameter will always be an integer which
is used to determine the number of parameters. Depending on the directive, some parameters will
be inputs and some will be outputs.
Variables in a circuit can be classified into three non-overlapping sets. Input variables must be
declared by the INPUT directive, and may only occur as input parameters. Output variables must be
declared by the OUTPUT directive and may occur exactly once in an output parameter. All other
variables are temporary variables and must occur exactly once as an output parameter and zero or
more times as an input parameter.
A variable name consists of a letter followed by zero or more letters or digits. You may assume
that variable names are no longer than 16 characters.
In addition to variables, the constant inputs 0 and 1 may be used as input parameters. These
are always false and always true, respectively.
Finally, _ may be used as the output of a gate, indicating that the output of a gate is discarded.
Note that whitespace may include one or more spaces, tabs, or newline characters. It is
recommended to use fscanf to read the files, and to use a format code such as ” %16s” to skip
whitespace before reading the next variable or directive name.
By convention, we will use multiple spaces to separate the inputs and outputs of a gate, but this
is not required and has no special meaning. It is purely for readability. Similarly, we will often put
a blank line between OUTPUT and the first gate, but this is also done purely for readability. Your
program should treat repeated newlines the same as single newlines (or, ideally, the same as any
whitespace).
Use of fgets is not recommended and will only make your life harder. Remember that fscanf
is not limited to reading an entire line at once.
3.1 Directives
This section describes each of the directives used to describe a circuit. Each directive is followed by
several parameters. A parameter n is always an integer and has a special meaning. Input parameters
are indicated as i and output parameters are indicated as o. Ellipses (· · ·) are used to indicate a
variable number of parameters.
• INPUT n i1 · · ·in
Declares n input variables. This directive must always occur first in a circuit description.
• OUTPUT n o1 · · · on
Declares n output variables. This directive must always occur second in a circuit description.
• NOT i o
Represents a not gate in logic design. Computes o = i.
3
• AND i1 i2 o
Represents an and gate in logic design. Computes o = i1i2.
• OR i1 i2 o
Represents an or gate in logic design. Computes o = i1 + i2.
• NAND i1 i2 o
Represents a nand gate in logic design. Computes o = i1i2
• NOR i1 i2 o
Represents a nor gate in logic design. Computes o = i1 + i2
• XOR i1 i2 o
Represents an xor gate in logic design. Computes o = i1 ⊕ i2, where ⊕ indicates exclusive or.
• DECODER n i1 · · ·in o0 · · · o2n−1
Represents an n : 2n decoder gate in logic design. The first argument gives the number of
inputs, n. The next n parameters are the inputs, followed by 2
n parameters indicating the
outputs.
The inputs are interpreted as an n-bit binary number s in the range 0, · · · , 2
n − 1, where i1
is the most significant bit and in is the least significant bit. The output os will be 1 and all
others will be 0.
• MULTIPLEXER n i0 · · ·i2n−1 i
0
1
· · ·i
0
n
o
Represents a 2
n : 1 multiplexer gate in logic design. The inputs to a multiplexer are either
regular inputs or selectors, indicated by i and i
0
, respectively. The first parameter, n, gives the
number of selectors. The next 2
n parameters give the regular inputs, followed by n selector
inputs, and finally the output.
The selector inputs are interpreted as an n-bit binary number s in the range 0, · · · , 2
n − 1.
The output is o = is.
• PASS i o
Represents the absence of a gate. Computes o = i. This may be used to convert a temporary
variable into an output variable.
3.2 Examples
This circuit describes a half-adder, where s is the sum and c is the carry.
INPUT 2 A B
OUTPUT 2 C S
AND A B C
XOR A B S
This circuit computes z = ab + ac:
INPUT 3 a b c
OUTPUT 1 z
4
AND a b x
AND a c y
OR x y z
Note that x and y are temporary variables, since they were not declared in INPUT or OUTPUT.
This circuit description is invalid, becuase it uses an output variable as an input parameter:
INPUT 3 IN1 IN2 IN3
OUTPUT 2 OUT1 OUT2
AND IN1 IN2 OUT1
OR IN3 OUT1 OUT2
This can be rewritten using PASS:
INPUT 3 IN1 IN2 IN3
OUTPUT 2 OUT1 OUT2
AND IN1 IN2 temp1
PASS temp1 OUT1
OR IN3 temp1 OUT2
This circuit demonstrates the user of MULTIPLEXER:
INPUT 3 A B C
OUTPUT 1 Z
MULTIPLEXER 3 0 0 0 1 1 0 1 1 A B C Z
As shown in class, this can be re-written to use a 4:1 multiplexer:
INPUT 3 A B C
OUTPUT 1 Z
NOT C NC
MULTIPLEXER 2 0 C NC 1 A B Z
An equivalent circuit can be made using a 3:8 decoder:
INPUT 3 A B C
OUTPUT 1 Z
DECODER 3 A B C _ _ _ p q _ r s
OR p q t
OR r s u
OR t u Z
Note the use of _ for discarded outputs from the decoder.
5
typedef enum { AND, OR, NAND, NOR, XOR, NOT, PASS, DECODER, MULTIPLEXER } kind_t;
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
};
Figure 1: One possible data structure representing a logic gate
4 Implementation suggestions
There are many ways to design truthtable, but the most efficient way is to create a data structure
that represents a circuit. Your program will read the circuit description file, create the corresponding
data structure, and then use that structure to determine the output values for each combination of
inputs.
Students commonly try to build the entire truth table before printing it. This is not the best
strategy, because the truth tables grow exponentially with the number of inputs. (For example, test
1.10 will produce a truth table with 2
20 = 1 048 576 rows.) A better design is to generate and print
the table one row at a time.
A few tips for creating fast implementations of truthtable.
• When reading the circuit description file, assign a number to each new variable name and use
a linked list or other structure to maintain a table that you can use to look up the number
assigned to previously seen variables. Internally, refer to variables by number rather than name:
integer comparisons are faster than string comparisons, and you can use variable numbers as
array indices.
• Carefully consider what information you need to represent a circuit. This will likely include
the circuit’s input and outputs and the gates making up the circuit.
• Carefully consider what data is needed to represent a gate. Design a structure that is general
enough to represent any gate, and then write code that can handle any of the gates. This will
likely include a code that indicates the type of gate and the input and output variables. See
fig. 1 for one possibility.
• In order to handle DECODER and MULTIPLEXER, your gates will need to work with a
variable number of inputs and outputs. One possibility is to use an array of variable numbers
representing the inputs and outputs along with a field indicating the size of the gate. For
fixed-sized gates, such as AND, this number can simply be ignored and the array can be
assumed to contain the correct number of inputs and outputs. For MULTIPLEXER and
DECODER, one number is sufficient to determine how many inputs and outputs there are.
• To generate a single row of the truth table, first assign values to the circuit inputs. Then, for
each gate, determine the values for its outputs based on the values of its inputs. Once every
gate has been handled, you will know the values for the outputs and can print the table row.
6
If you have assigned a unique number to each variable, then you can use an array to hold the
values of all the variables.
• For each row of the truth table, note that every input value will be followed by a space, and
every output value will be preceded by a space.
• When reading the circuit description, you may assume that the file is correctly formatted.
Thus, after reading a directive name, you may assume that it will be followed by the correct
number of parameters. Thus, it is acceptable to use the whitespace-skipping tokenizer and
ignore line breaks.
• When using a formatting string such as ” %16s”, the corresponding variable must be the
address of an array containing a sufficient number of characters (17, in this case). While it is
fine to use local variable to hold the result from fscanf, be sure to make a copy of the string
if you intend to hold onto it.
• There are several methods for dealing with circuit descriptions where the gates are not given
in order. One way is easy to write, but slow. Another is more complicated, but fast. (Hint:
the circuit can be thought of as a directed, acyclic graph, and you have learned an algorithm
for ordering the nodes in a DAG.)
5 Submission
Your solution to the assignment will be submitted through Sakai. You will submit a Tar archive
file containing the source code and makefiles for your project. Your archive should not include any
compiled code or object files.
The remainder of this section describes the directory structure, the requirements for your
makefiles, how to create the archive, how to use the provided auto-grader, and how to create your
own test files to supplement the auto-grader.
5.1 Directory structure
Your project should be stored in a directory named src, which will contain (1) a makefile, and (2)
any source files needed to compile your program. Typically, you will provide a single C file named
for the program (truthtable.c).
This diagram shows the layout of a typical project:
src
+- Makefile
+- truthtable.c
Note that your code and makefile go directly in src, without any subdirectories.
You may use the provided makefile to create this directory:
pa4$ make tree
7
5.2 Makefiles
We will use make to manage compilation. Your src directory will contain a file named Makefile
that describes at least two targets. The first target must compile the program. An additional
target, clean, must delete any files created when compiling the program (typically just the compiled
program).
For reference, this makefile is provided with the auto-grader in the file data/template.mk:
TARGET = estimate
CC = clang
SANITIZERS = -fsanitize=address $(if $(findstring clang,$(CC)),-fsanitize=undefined)
OPT =
CFLAGS = -g -std=c99 -Wall -Wvla -Werror $(SANITIZERS) $(OPT)
$(TARGET): $(TARGET).c
$(CC) $(CFLAGS) $^ -o $@
clean:
rm -f $(TARGET) *.o *.a *.dylib *.dSYM
You may copy this file to your source directory and rename it Makefile, or use the project
makefile to create the source directory for you.
Note that the command for compiling truthtable uses warnings and the address sanitizer, and
includes the undefined behavior sanitizer when the compiler is clang. Your score may be reduced if
your makefile does not include these options.
Use of -g is recommended, but not required.
This makefile can be adapted to work with multiple source files. Contact the professor for
directions if that interests you.
Note that the makefile format requires that lines be indented using a single tab,
not spaces. Be aware that copying and pasting text from this document will “helpfully” convert
the indentation to spaces. You will need to replace them with tabs (literal tab characters), or simply
type the makefile yourself. You are advised to use make when compiling your program, as this
will ensure (1) that your makefile works, and (2) that you are testing your program with the same
compiler options that the auto-grader will use.
Working with GDB The default makefile includes -g, which instructs the compiler to include
source information for the debugger. Depending on your program, clang may optimize too aggressively
and remove variables whose values you would like to examine. In that case, you may want to
recompile with gcc. This can be done without modifying your makefile by including CC=gcc in your
arguments to make. Similarly, you may use OPT=-O0 (the letter ‘O’ followed by the number zero) to
disable optimization.
pa4/src$ make CC=gcc OPT=-O0
gcc -g -std=c99 -Wall -Wvla -Werror -fsanitize=address -O0 truthtable.c -o truthtable
If you have not changed your source code, you can give make the option -B to force recompilation,
or use make clean before recompiling.
Note that clang is still the recommended compiler for normal usage, because it provides the
undefined behavior sanitizer and its version of AddressSanitizer has better error messages.
8
5.3 Creating the archive
We will use tar to create the archive file. The included project-level Makefile will create an archive
for you:
pa4$ make pa4.tar
By default, this assumes that your project consists of Makefile and truthtable.c, both located in
src. This can be adjusted as necessary.
If you prefer to create your archive yourself, move to the directory containing src and execute
this command:
pa4$ tar -czvf pa4.tar src/Makefile src/truthtable.c
tar will create a file pa4.tar that contains your makefile and source code. (If you are using multiple
source files, or have re-named your source code, you will need to adjust this command accordingly.)
This file can now be submitted through Sakai.
To verify that the archive contains the necessary files, you can print a list of the files contained
in the archive with this command:
pa4$ tar -tf pa4.tar
You should also use the auto-grader to confirm that your archive is correctly structured.
pa4$ ./grader.py -a pa4.tar
The project Makefile includes a target archive, which will create pa4.tar and test it with the
auto-grader.
5.4 Using the auto-grader
We have provided a tool for checking the correctness of your project. The auto-grader will compile
your programs and execute them several times with different arguments, comparing the results
against the expected results.
Setup The auto-grader is distributed as an archive file pa4_grader.tar. To unpack the archive,
move the archive to a directory and use this command:
$ tar -xf pa4_grader.tar
This will create a directory pa4 containing the auto-grader itself, grader.py, a library autograde.py,
abd a directory of test cases data.
Do not modify any of the files provided by the auto-grader. Doing so may prevent the auto-grader
from correctly assessing your program.
Usage The project makefile provides a few targets that run the auto-grader: make or make testall
will run all tests for both parts. To run only the normal-credit tests, use make normal. For only the
extra credit tests, use make extra. To run all tests, but stop at the first failure, use make 1.
You can also invoke the auto-grader directly. While in the same directory as grader.py and
src, use this command:
9
pa4$ ./grader.py
The auto-grader will compile and execute the program in the directory src, assuming src has the
structure described in section 5.1. The compiled program will be in a directory build, which is
created by the auto-grader.
During development, you may prefer to use the –stop or -1 option, which produces more
program output but stops after the first failed test case.
pa4$ ./grader.py -1
The tests for this assignment come in two groups, for normal and extra credit. To test only a
single part, include an argument truthtable:1 or truthtable:2.
To obtain usage information, use the -h option.
Program output By default, the auto-grader will not print the output from your programs,
except for lines that are incorrect. To see all program output for all unsuccessful tests, use the
–verbose or -v option:
pa4$ ./grader.py -v
To see program output for all tests, use -vv. To see no program output, use -q.
Checking your archive We recommend that you use the auto-grader to check an archive
before submitting. To do this, use the –archive or -a option with the archive file name. For
example,
pa4$ ./grader.py -a pa4.tar
This will unpack the archive into a temporary directory, grade the programs, and then delete the
temporary directory.
Specifying source directory If your src directory is not located in the same directory as
grader.py, you may specify it using the –src or -s option. For example,
pa4$ ./grader.py -s ../path/to/src
10