COSC 065 Hardware Systems

Fall 2007

Homework Assignment #10

Final x86 Assembly Language

Due: Wednesday, Dec 5, 2:00PM CST
Submit: E-mail electronic copy to professor, with a subject header "COSC 065 HW#10".
Work may be completed in pairs. Each team should submit only once. Be certain to put both team member names on work submitted. It would be courteous to carbon-copy your partner when e-mailing the final submission.

Background

Intel x86 assignments are to be compiled and run natively on our Linux workstations in the systems lab. You will not require the MIPS Playground or the mipcon tool for this assignment. Instead, compose your program in an empty file, perhaps starting with the Intel x86 demo as a template.

Your work must be compiled on a machine with the proper tools, such as the dual-head Linux boxen in the Systems Lab (CU 310). Consult the professor for advice on connecting remotely if the lab is full or you must work from elsewhere. Intel x86 machines can be identified by running the command uname -p; look for machines that identify themselves as i386, i586, or i686. Your x86 programms will not compile or run on the PowerPC and MIPS hardware we have in the lab, and I do not recommend compiling with the 64-bit AMD machines for these assignments. The current list of x86 boxes in the systems lab includes: Argolis, Calufrax, Gallifrey, Kastria, Skaro, Telos, Traken, and Zanak. All of these machines are remotely accessible by secure shell. (E.g. ssh argolis.mscs.mu.edu, etc.)

In order to assemble your program, use the command "gcc". In order to run your program, use the command "./a.out". If you do not want your compiled program to be called "./a.out", you may use the "-o" option to gcc to alter the outputed program.

Few rules govern the format of assembly language programs. Make an effort to keep your programs readable and well-documented; sometimes the professor gives partial credit if he can tell what you were trying to do, even if it doesn't quite make it.

Pascal's Triangle

Write an assembler program that reads in a single integer from the user and outputs a properly spaced and centered Pascal Triangle of the requested size.

Pascal's triangle is a triangular array of numbers (these numbers correspond to the binomial coefficients) whose left and right hand borders are all 1's and where each number is the sum of the two immediately above it. That is:

                                1

                              1 + 1
                               \ /
                            1 + 2 + 1
                             \ / \ /
                          1 + 3 + 3 + 1
                           \ / \ / \ /
                        1   4   6   4   1
                                :
                                :

The first 7 rows of the Pascal triangle are the following:

                        1                  n=0

                      1   1                n=1

                    1   2   1              n=2
                     
                  1   3   3   1            n=3

                1   4   6   4   1          n=4

              1   5  10   10  5   1        n=5

            1   6   15  20  15  6   1      n=6

It turns out that you can find interesting patterns in the above sequence of numbers. If you draw the Pascal's triangle as a grid of squares, and color every square that corresponds to an odd number black and every square that corresponds to an even number white, you get the following pattern:

You do NOT need to compute the numbers in order to decide which one is even and which odd.

Let n and k be the indices of the row and column respectively of a number in Pascal's triangle. Consider n and k in their binary representation. If every bit of n is greater than or equal to every bit of k, then the number in the position (n,k) is odd, otherwise the number is even.

For example, consider the position (4,2) (all indices start from 0). The binary representation of 4 is 100 and the binary representation of 2 is 010.

    1 0 0  (n = 4)
    0 1 0  (k = 2)
      ^
      |
    1 > 0

You can see that there is a digit of k that is greater than the corresponding digit of n. Therefore, the number in the position (4,2) is even, which is indeed the case since this number is 6.

The professor has provided an example program for your reference, runnable on x86 machines in the lab as ~brylow/cosc065/bin/hw10-pascal.