CS232, Spring 2008

Extra Credit Wombat5 - 3, 4, 5, 6, & 7 Assignments

Due: Friday, May 9 (last day of classes) at class time

General notes:

• You can do any of these assignments you want for extra credit.
• They are to be done individually, not in teams.
• The extra credit points you earn are equivalent to exam points.
• The number of points of extra credit points you get will depend on the difficulty of the problem and the readability of your solution.
• Little or no credit will be given for half-hearted attempts at a project. That is, I expect significant progress to be made before I give any extra credit.
• No late extra credit assignments will be accepted.

Exercise W5-3 Macros

Redo project W5-1 using macros instead of subroutines.

Details

• Create a macro called "mod" that takes two (not necessarily distinct) A register indices i and j as arguments and computes A[i] % A[j] and puts the result in A[i].
• Here is the documentation header for the mod macro:

  	; Macro mod
  	; usage:  mod i j
  	; Computes A[i] % A[j] and puts the result in A[i].
  	; It assumes i and j are (not necessarily distinct)
  	; integers in the range 0 to 7 and that
  	; A[i] and A[j] contain positive integers.
  	; It does not use any other registers or RAM.

  You don't need to worry about what happens in the case where A[i] and/or A[j] contain zero or negative integers.
• The advantage of macros over subroutines is that the user gets to treat mod as if it were a built-in machine instruction. That is, the user can include instructions such as

  	mod A0 A1

  anywhere in his or her code just as if mod were a machine instruction.
• Store the mod macro in a file called "modMacro.i".
• Create a program to test the mod macro that just reads in two integers n and m, computes n % m, and outputs the result. Save this program in a file named "W5-3EC.a" in the same directory as your modMacro.i file. In your main program, you will need to include a line at the top reading:

  	.include "modMacro.i"

  so that the assembler will assemble and load the modMacro.i file as part of your program.
• Note that the macro is not allowed to use any other registers or RAM. Furthermore, the only register it changes is A[i].
• For even more extra credit, implement mod so that it works like Java for all integers, not just positive integers.
• Hand in a hard copy of your assembly code files W5-3EC.a and modMacro.i and attach electronic copies of both files to an email message to me.

Exercise W5-4 Searching arrays

Write a Wombat5 program "W5-4.a" that reads in a positive integer n followed by n more integers.  It stores the n integers in an "array" on the stack.  The main program then calls a subroutine "indexOfMax" to find the index of the largest integer in the array.  Finally the main program prints that largest integer. 

Details

• To initialize the array, first increment A[7] by 2n to set aside space for the array on the stack. Then use a loop that repeatedly reads in an integer and puts it in the next available slot in the array on the stack.  Note that you are supposed to load all n integers into the array before you call indexOfMax to start checking for the largest.  Do not find the largest as you are reading in the integers.
• I don't care what happens if n <= 0 (for example, it is okay for your program to crash).
• The indexOfMax subroutine should be a function that takes two parameters:  n and the starting address of the array. It returns an integer from 0 to n-1 (the index of the largest value in the array).
• Your main program should look something like this:

   load A0 IO ; read n into A0
   ; increment A7 by 2*n
   ...
   ;loop n times reading and inserting array values
   ...
   loadc A1 0 ; load starting address of the array into A1
   push A0 ; push n onto the Stack (first param)
   push A1 ; push starting address of the array (second param)
   call indexOfMax ; call the indexOfMax function
   pop A2 ; pop result into A2
   ; find max value using the index in A2 and put max value in A3
   ...
   store A3 IO; output the max value
   exit ; end of main program

• The indexOfMax function should not assume that the array's starting address is always 0, even though it happens to be 0 in this example.
• Hand in a hard copy of your assembly language program W5-4.a and also attach an electronic copy to an email message to me.

Exercise W5-5 Sorting Arrays

Write a Wombat5 program "W5-5.a" that reads in an integer n followed by n more integers. Your program stores the n integers in an array of size n in the stack, as was done in Exercise W5-4.  It then sorts the n integers in place in the array using the indexOfMax function from Exercise W5-4 and a Selection Sort subroutine. After it is done sorting, your program writes out the n integers from smallest to largest. You may assume that n>=1. 

Details

• The SelectionSort subroutine should take two parameters:  the value n and the starting address of the array on the stack. It should not assume that the starting address of the array is address 0 in the stack.
• Do not sort the data as you are reading it in. Instead, read everything in and then do the sorting.
• You must use the indexOfMax function from Exercise W5-4 without modification.
• To help you with sorting, here is the Java code for one version of selection sort:

     public void selectionSort(int[] B)
     {  //sorts array B in place using Selection Sort
       int temp; //used for swapping values
       int indexOfMax; //the index of the largest value found so far
       for (int i = B.length-1; i >=1; i--) {
           // find the largest int in B[0]..B[i]
           indexOfMax = 0;
           for (int j = 1; j <= i; j++) {
              if (B[j] > B[indexOfMax])
                indexOfMax = j;
           }
           // swap the largest int into position i
           temp = B[i];
           B[i] = B[indexOfMax];
           B[indexOfMax] = temp;
       }
     }

• Keep in mind that there are lots of short cuts that can be taken in your code to optimize it. That's what an optimizing compiler does. However, this optimization process also usually makes code completely unreadable. Since I have to read (and grade) your code, I want you to make it as readable as possible instead of as fast as possible, and so I want you to avoid the temptation of trying any optimizations. Instead, I would recommend that you just convert each statement of the Java source code given above into the corresponding Wombat5 assembly code. Also, make sure your code is well documented. The harder it is for me to read and understand your code, the fewer points you will get for it, even if it works correctly!
• One part of making your code readable is using EQUs to create symbols for each local variable.
• Another part of making your code more readable is creating a subroutine that handles reading in the n values into the array and creating a subroutine that handles printing the values in the sorted array.
• Feel free to enlarge Main memory and the Stack if you need more space.
• It might be helpful to put the array size and the array data in a text file and then get your input from that file instead of from the console. To do so, enter your data in a text file with each integer separated by spaces, tabs, or carriage returns. Then choose "Options|IO connections…" from the Execute menu in CPU Sim. In the dialog box that appears, click in the "connection" column for the "input-int->buf1" microinstruction and choose "File…" from the popup menu. In the file dialog that appears, select your text file.
• Hand in a hard copy of your assembly language program W5-5.a and also attach an electronic copy to an email to me.

Exercise W5-6 Recursively Sorting Arrays

Redo exercise W5-5 using a different sorting algorithm.

Details

• The sorting algorithm must be a recursive sort, such as quick sort or merge sort.
• You do not need to use the indexOfMax function from exercise W5-4.
• Put your program is a file named "W5-6.a".
• Hand in a hard copy of your W5-6.a program and attach an electronic copy of it to an email to me.

Exercise W5-7 Adding boolean operators to the Wombat5

Add shifta, shiftl, and shiftc machine instructions and boolean bitwise and, xor, not and or machine instructions to the Wombat5, and then write a program to test some of them.

Details

• Create an arithmetic shift instruction "shifta", a logical shift instruction "shiftl", and a cyclic shift instruction "shiftc" that shift the bits in a register zero or more bits to the left or right.  Bits 8-10 of the instructions give the index of the A register whose bits are to be shifted.  Bits 5-7 give the index of the A register where the shifted value is to be placed. In the last 5 bits of the instructions is stored a 5-bit 2's complement number that indicates how far to shift.  A positive number indicates a left shift and a negative number indicates a right shift. 
• For example, the command "shiftl A0 A1 3" should cause the bit values in register A[1] to be shifted to the left logically by three bits (and so filling the three right-most vacated bits with 0's) and the result placed in A[0].  The value in A[1] is left unchanged. It is okay for the two indices to be the same, in which case the shifting is done in place. That is, the command "shiftl A0 A0 3" should cause the bits of register A[0] to be shifted to the left 3 bits in place.
• Create "and", "or" and "xor" machine instructions that behave like the add, subtract, multiply, and divide instructions in that the computation involves two registers, with the first register storing the result of the computation. These instructions work bit-wise on the selected registers. So, for example, if A[1] contains all 0 bits, then the command "and A0 A1" effectively clears A[0]. Similarly, if A[1] contains all 1 bits, then the command "and A0 A1" will leave A[0] (and A[1]) unchanged.
• Create a "not" machine instruction that just complements all the bits of the value in the A register whose index is specified in bits 8-10 of the instruction and puts the result in the A register whose index is specified in bits 5-7 of the instruction.
• The shift and logical microinstructions in CPU Sim should come in handy as you implement these new machine instructions.
• Test your new instructions by writing a program "W5-7.a" that reads in a positive integer (between 0 and 99 inclusive) and stores the number in the rightmost 8 bits of a 16-bit word on the stack in BCD (binary-coded decimal) format.
• Recall that BCD is an encoding scheme in which an n-digit decimal number is stored using 4n bits.  Each digit is stored in binary (not 2's complement) using 4 bits.  So, for example, the number 94 (base 10) would be stored using 8 bits in the following form:  10010100.  We won't worry about negative numbers in BCD.
• Your program should use the LSHIFT and OR machine instructions.  Once the number has been stored in BCD format, your program can quit.  There isn't any output.  (You didn't expect your Wombat programs to do anything useful, did you?)  No subprograms need be used, but you are welcome to use them if you wish.
• Hand in a hard copy of your assembly program W5-7.a and attach an electronic copy of the assembly program and your new Wombat5.cpu file to an email message to me.