CSCE 614 Fall 2019, Homework 1

1. Circuits from Truth Table

   Suppose the last three digits of your Texas A&N UIN are XXX. Use them to form a URL like this:

   
   http://taco.cse.tamu.edu/classes/614/hw1/problems/XXX-truth-table.txt
   
   

   There you will find your truth table.

   Construct two circuits that compute the function in four variables given by your truth table. One circuit may use only two-input NAND gates. The other circuit may use two-input NAND, NOR, AND, OR, and XOR gates as well as NOT gates.

   Circuit Syntax

   The circuits should be specified with as many lines as there are gates. Each line should contain the following elements:
   1. A gate number followed immediately by a colon. Gate numbers start at 0 and proceed in ascending order.
   2. A two-character gate symbol, one of the following:
      • && for AND
      • || for OR
      • !! for NOT
      • ^^ for XOR (exclusive-OR)
      • !& for NAND
      • !| for NOR
   3. Two integers representing the input to this gate. Negative integers represent variables (-1, -2, -3, or -4) while non-negative integers represent the output of the gate with the corresponding number. For a NOT gate, the output is the complement of the first input (although note that NOT gates are not really needed; you can just use the NAND or NOR of a variable with itself).
   For instance, the following is a valid circuit description:

   0: ^^ -1 -3
   1: ^^ -3 -4
   2: !| 0 -4
   3: ^^ 1 -2
   4: !& 1 0
   5: || 3 2
   6: !& 5 4
   

   Gate #0 computes the XOR of variables -1 and -3. Gate #5 computes the OR of the outputs of gates number 3 and 2. This circuit computes the following truth table:

   -4 -3 -2 -1   | output
   ------------  |
    0  0  0  0   |  0
    0  0  0  1   |  1
    0  0  1  0   |  0
    0  0  1  1   |  0
    0  1  0  0   |  1
    0  1  0  1   |  0
    0  1  1  0   |  1
    0  1  1  1   |  0
    1  0  0  0   |  0
    1  0  0  1   |  1
    1  0  1  0   |  1
    1  0  1  1   |  1
    1  1  0  0   |  1
    1  1  0  1   |  1
    1  1  1  0   |  0
    1  1  1  1   |  0
   

   Requirements

   You are required to make two circuits: one using only NAND gates, and one using any combintion of NAND, NOR, NOT, AND, OR, or XOR. For every truth table distributed with the assignment, the corresponding NAND circuit requires only 11 gates and the corresponding NAND, NOR, NOT, AND, OR, and XOR circuit requires only seven gates. You should strive to use only the minimum number of gates necessary; we will take points off for excessive gates. No points will be rewarded for incorrect circuits.

   Validation

   We will use the validate.c program to validate your solution. You should verify that your circuit actually computes the truth table you were given using this program. If foo.txt contains your truth table and bar.txt contains your solution as a list of gates, then typing validate foo.txt bar.txt will evaluate your circuit for each line of the truth table. If it prints success! then your circuit is correct. Otherwise, use the output of the program as debugging information and keep trying. Try out validate.c with the truth table and circuit given above. Note that validate.c is not very smart; any extraneous spaces or other information in the input files can cause it to fail.

2. Machine Language Understanding

   Let XX be the decimal value of your TAMU UIN modulo 64 + 1, i.e., a number between 1 and 64. Form a URL with this number in place of the XX in the following:

   http://taco.cse.tamu.edu/classes/614/hw1/files/XX.txt
   

   For instance, if your UIN is 1234, then 1234 mod 64 is 18, 18 + 1 is 19, so you should get http://taco.cse.tamu.edu/classes/614/hw1/files/19.txt. This file contains a sequence of hexadecimal bytes representing a C function in either x86 (32-bit) or x86_64 (64-bit) machine language. The file will also contain a type signature, i.e., a C declaration of the function giving its return type and the type(s) of its parameter(s), as well as a line giving the instruction set used for this function.

   Requirements

   1. Provide a commented disassembly of the function. That is, for each instruction in the function, give the equivalent line in x86 assembly language and a comment on the same line giving the meaning of the instruction.
   2. Write a function in C that carries out the same computation done by the function.
   3. Your function is a well-known simple algorithm. Write a short sentence describing the algorithm, giving the name of the algorithm if possible.

      Note: It is expected that many students are not familiar with x86 and x86_64 machine language. You are expected to be resourceful. Find information and possibly tools on our systems or on the Internet to help you with this problem. There is more than one right way to do this assignment.

   You may not work together on this assignment with other classmates or receive assistance from any person other than your professor or teaching assistant. You may consult literature or the Internet for assistance; if you do, indicate the source in your writeup. Again, do not collaborate with others on this assignment; this assignment is to be done individually.

   Do the assignment you are assigned. Everyone has a different circuit and a different sequence of bytes to disassemble. You will receive no credit for turning in a solution to the wrong problem.

   Your assignment should be nicely typed or word-processed. Turn in this assignment at the beginning of class on September 13, 2019. You must turn in the assignment on paper at the beginning of class. You must also send your two circuit files and your C function to our teaching assistant as three attachments to one email message before 10:20pm on September 13. Make sure to put your name on your paper assignment. Make sure the circuits you turn in validate correctly. Make sure your C function compiles correctly.

   Note: This assignment is designed to be simple for students who are well-prepared to take CSCE 614 and difficult or impossible for students who are not well-prepared. If you find that you don't know where to start or how to do this assignment, you are strongly encouraged not to continue in this class.

   Late assignments will not be accepted.