Assignment 6, due Oct 3

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper Homework is due on paper at the start of class on the day indicated (usually Friday). 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. A Problem: Consider this SMAL Hawk code for a subroutine:

   ;RETAD  =       0
   X       =       4
   Y       =       8
   V       =       16
   ARSIZE  =       20
   
   SUBR:
           STORES  R1,R2
           STORE   R3,R2,X
           STORE   R4,R2,Y
   
           LOADCC  R0,R2,X
           BZS     SUBELS
   
           LOAD    R3,R2,Y
           LOAD    R4,R2,X
           ADDSI   R4,-1
   	ADDI    R2,R2,ARSIZE
           JSR     R1,SUBR
   	ADDI    R2,R2,-ARSIZE
           STORE   R3,R2,V
   
           LOAD    R3,R2,V
           LOAD    R4,R2,Y
           ADD     R3,R3,R4
           STORE   R3,R2,V
   
           BR      SUBEND
   SUBELS:
   
           LIS	R3,0
           STORE   R3,R2,V
   
   SUBEND:
   
           LOAD    R3,R2,V
           LOADS   R1,R2
           JUMPS   R1
   

   Note that this code is "as dumb as cement" with no optimization, a boiler-plate receiving sequence, boiler-plate return sequence, and all variables stored in RAM between what could be high-level-language statements.

   Also note that this is just a subroutine. There is no main program. You cannot test it without writing a main program to call it, passing the appropriate parameters wherever this code expects parameters. In the process, you will have to add all the material from the skeleton of a main program, including things like USE "hawk.h" and things like that. Of course, the assignment does not require testing it.

   a) Reverse engineer this subroutine and give equivalent high-level language code, for example, as a C or C++ function or a Java or Python method. Use the letters x, y, z and v as parameter and variable names, and to the extent possible, write your code using appropriate high-level control structures. (0.5 points)

   b) Write optimal code for this subroutine. You will find, in doing this, that you can eliminate many load and store instructions and entire fields of the activation record. (Your optimization should not change the algorithm! It should just make the algorithm run as fast as you can.) (1.0 point)

   c) What does it do? If you ignore English grammar, there are some good one and two word answers. (0.5 points)

2. Background: Study Machine Problem 3. The following small programming problems are not necessarily part of the solution to MP3, but they are inspired by it and should help you work your way toward a solution.

   a) Write a function that a C programmer might call twotothe() that, given a value of i as a parameter, returns 2ⁱ as its value. Use the standard Hawk rules for parameter passing and function return values. You can use iterated multiplication by two to do this. (0.5 points)

   Note: The optimal solution uses just 8 halfword instructions, but appropriate comments might expand this to as much as 15 lines of code.

   b) If each little triangle making up the entire Serpinski triangle is plotted as follows:

   __
   \/
   

   That is, composed of two underscores atop a V made of a backslash and slash. In what orders can you plot the left, right and bottom triangles in order to guarantee that the horizontal lines plot correctly, avoiding outcomes like this (among others):

   ________________
   \__/\__/\__/\__/
    \____/  \____/
     \__/    \__/
      \________/
       \__/\__/
        \____/
         \__/
          \/
   

   And yes, you really can get this output from your program if you plot the subsidiary triangles in the wrong order. (0.5 points)

   Note: There are three subsidiary triangles. Three things can be done in 6 possible orders. Only some of these orders avoid messed up results (and there are several ways to mess things up.