Assignment 6, due July 6

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated, and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

1. Chapter 7 of the notes includes code for a string copy routine called STRNCPY. Following the presentation of this code, the notes include several suggestions for optimizations to make it run faster. Rewrite this code to incorporate all of these optimizations (this is exercise h in that chapter).

    
    

2. Background: Suppose you had to write a HAWK program that had 6 special cases, identified by the labels on the first instruction of each case: CASEQ, CASEU, CASEH, CASEK CASEM, and CASED. Register 3 contains an ASCII character (guaranteed to be one byte, from 0 to 255). If this character is 'q' or 'Q', you want to transfer control to CASEQ. If it is 'u' or 'U', you want to transfer control to CASEU, and similarly for CASEH, CASEK and CASEM after the corresponding letters. For all other letters, you want control to go to CASED.

   a) Solve this problem with a sequence of CMPI instructions followed by appropriate conditional branch instructions, with a single unconditional branch at the end. (1/2 point)

   b) Write SMAL code to construct a jump table (of 256 words) that associates the correct case with each of the ASCII characters. This is not code. Words correspond to ASCII characters and have, as values, CASEQ, CASEU, CASEH, CASEK CASEM, or CASED. Organizing this table as 32 lines by 8 words per line is convenient. Comments to help you relate the lines to the ASCII character set would also help. Label word zero of this jump table with JUMPTABLE (1/2 point)

   c) Write the code to transfer control through your jump table to the correct case, using register 3 to load the correct jump table entry and then jumping to the indicated case. You must load the jump table entry into a register before you use it to jump! (1/2 point)

    
    

3. Background: Consider this system of logic equations:

   c = not( a and b )
   d = not( a and c )
   e = not( b and c )
   f = not( d and e )

   a) Write this out as a logic diagram giving f as a function of a and b, with all intermediate points labeled. (1/2 point)

   b) Give a truth table showing c, d, e and f as functions of a and b. (1/2 point)

    
    

4. Problem: Show how to make an 8-input multiplexor from 7 2-input multiplexors. Give your answer in the form of a schematic logic diagram. Hint: Think in terms of binary trees. (1/2 point)

Machine Problem 3, Due July 8

Take your solution to Machine Problem 2 and add code to do the following: Randomly plot "#" marks on the screen, so that ten percent of the spaces on the screen contain hash marks. (Later, you will need to make it so moving your asterisk will behave differently depending on whether it moves into a hash mark.)

There are two algorithms you could use: Either figure out how many spaces there are on the screen and then divide by 10 to get the right number of hash marks, then plot that many hash marks at random coordinates on the screen, or draw a random number from zero to nine for each space on the screen and plot a hash mark if that number comes up zero. For the purposes of this assignment, either of these algorithms will suffice.

The real problem here is to write a little routine you can call to compute random numbers. Genuine randomness is difficult to get on a computer, but you can make a pseudo-random number generator by using a sequence of values x₀, x₁, x₂, x₃ computed from the following formula:

x_i+1 = (16807 x_i) mod (2³¹ - 1)
x₀ = any integer between 1 and 2³¹ - 1 2³¹ - 1

(The above pseudo-random number generator is called the minimal standard pseudo-random number generator or the Park and Miller generator after the authors of the most widely read paper on the subject.)

Unfortunately, this needs 46-bit arithmetic. On a 32-bit machine, the following code will work:

h_i+1 = x_i / 127773       (note that 127773 = (2³¹ - 1) / 16807)
l_i+1 = x_i mod 127773
t_i+1 = 16807 l_i+1 - 2836 h_i+1     (note that 2836 = (2³¹ - 1) mod 16807)
if t_i+1 > 0
  then x_i+1 = t_i+1
  else x_i+1 = t_i+1 + 2147483647   (note that 2147483647 = 2³¹ - 1)

This lovely computation produces exactly the same sequence of values of x_i+1 as the first version given above, but with the guarantee that none of the intermediate values will be out of bounds on a 32-bit machine.

Finally, of course, if you want random numbers from 0 to n-1 and you have random numbers in a much larger range, take the larger number mod n.

Submitting your result: Usee the submit command on the department linux cluster to submit your solution. Your program must be in a file named mp2.a, submit it for the course c060 and in the directory mp2. See the assignment for MP1 for details.

Grading: Failure to include an appropriate TITLE directive will be penalized as in MP1. Up to half credit will be deducted for each of the following, depending on severity: Assembly errors, illegible or badly formatted code, poorly thought out logic of the solution, or failure of your program to perform as required. Poorly thought out commentary that belabors the obvious or fails to explain the obscure will cost at most one point. Failure to properly use global variables for the sequence of pseudo-random values will be penalized 1/2 point.