Assignment 7, due Mar. 9

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: Here is a C subroutine to copy a string from here to there while converting all lower-case letters to upper case:

   void upcase( char * src; char * dst ) {
       char ch;
       do {
           ch = *src;
           if ((ch >= 'a') && (ch <='z')) {
               ch = ch + ('A' - 'a');
           }
           *dst = ch;
   	src = src + 1;
   	dst = dst + 1;
       } while (ch != NULL);
   }
   

   A Problem: Write an equivalent SMAL Hawk subroutine that takes R3 as the source address and R4 as the destination address, and conforms to the standard Hawk calling sequence. (1.0 points)

2. A Problem with two parts: Redraw the schematic for the 4-input multiplexor given in Chapter 8 of the notes so that:

   a) ... it uses explicit inverters instead of bubbles on inputs to gates. (0.4 points)

   b) ... so that, as a result of applying De Morgan's laws, it only uses nand gates and does not use any and or or gates. (0.4 points)

   Note: Neatness counts. Graph paper, rulers and other tools can all help.

3. A problem: An exclusive-or gate can be made from a 2-input multiplexor and an inverter. Compare the implementation of th exclusive-or funtion given at the start of Chapter 8 with the implementation of a 2-input multiplexor given 2/3 of the way through the chapter, and then explain how to construct an exclusive-or gate from a 2-input multiplexor and a small amount of additional logic. (0.4 points)

4. Background: A one-bit stage of a subtractor has inputs s_i, a bit of the subtrahend, m_i, a bit of the minuend, and b_i, the borrow in to that stage of the subtractor. The outputs are d_i, one bit of the difference, and b_i+1, the borrow in to the next higher stage of the subtractor.

   A problem: Give the truth table for a one-bit stage of a subtractor. (0.8 points)

   Note: You may find that the discussion of an adder-subtractor in the section of Chapter 8 on arithmetic logic units provides useful insight.

Machine Problem 4

Due Mar. 26

Consider the following sequence of figures:

[]  [][][]   [][][][][][][][][]
    []  []   []  [][]  [][]  []
    [][][]   [][][][][][][][][]
             [][][]      [][][]
             []  []      []  []
             [][][]      [][][]
             [][][][][][][][][]
             []  [][]  [][]  []
             [][][][][][][][][]

[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  []
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[][][]      [][][][][][]      [][][][][][]      [][][]
[]  []      []  [][]  []      []  [][]  []      []  []
[][][]      [][][][][][]      [][][][][][]      [][][]
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  []
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[][][][][][][][][]                  [][][][][][][][][]
[]  [][]  [][]  []                  []  [][]  [][]  []
[][][][][][][][][]                  [][][][][][][][][]
[][][]      [][][]                  [][][]      [][][]
[]  []      []  []                  []  []      []  []
[][][]      [][][]                  [][][]      [][][]
[][][][][][][][][]                  [][][][][][][][][]
[]  [][]  [][]  []                  []  [][]  [][]  []
[][][][][][][][][]                  [][][][][][][][][]
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  []
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[][][]      [][][][][][]      [][][][][][]      [][][]
[]  []      []  [][]  []      []  [][]  []      []  []
[][][]      [][][][][][]      [][][][][][]      [][][]
[][][][][][][][][][][][][][][][][][][][][][][][][][][]
[]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  [][]  []
[][][][][][][][][][][][][][][][][][][][][][][][][][][]

These are the first 4 Serpinski gaskets. Each successive gasket is formed of 8 of its predecessors arranged in a square, leaving a hollow where the 9th would go. The Serpinski gasket is an example of a fractal figure, since as you zoom in on any part of the gasket, all you see is more gaskets.

Write a program to fill the screen with the largest Serpinski gasket that fits on the screen, centered. This program will, by its nature, be recursive. You will need to compute, in advance, the size of the largest gasket that will fit on the screen, and then follow through with the actual recursive code.

Submission Instructions

Your source file must be named mp4.a all lower case. This file must exist on the departmental linux cluster. Use the division of math-sciences coursework submission tools to submit this file. For instructions, see:

-- http://www.divms.uiowa.edu/help/msstart/submit.html

Grading

The grader will assemble and run your code, and will comment, on your assembly listing, about any deficiencies in your work. You will be penalized for any of the following errors:

• Lack of appropriate header comments.
• Poor use of white space.
• Inadequate comments.
• Excessive comments.
• Appropriate use of subroutines.
  Yes, this program can be written entirely without subroutines, but there are some natural ways to divide the problem that simplify development, debugging and reading.
• Code that does not run.
  The minimum requirement for this assignment is working code. Code that does not assemble and cannot be run is worthless.
• Code that produces the wrong output.
  Of course, the correct output is strongly preferred.

A suggestion: Work incrementally and note that problem 2 on the homework above is closely related to this assignment. First, get your program to prompt repeatedly for y or n and quit when n is typed. Then make it output a value. Then start working on making it translate heptavigintimal to binary. Steal code from the notes.