Homework 8

22C:18, Fall 1996

Due Tuesday Oct. 29, 1996 in discussion

1. Write a SMAL Hawk procedure to add two binary numbers of arbitrarily large precision. In C, this might be documented as follows:

   	add(sum,addend,augend,length)
   	unsigned long int sum[],addend[],augend[];
   	int length;
   

   That is, the procedure takes three arrays of 32 bit integers as parameters and a 4th parameter giving the lengths of the arrays. Each array holds a single binary integer, with the least significant 32 bits in the first word (index 0), followed by more significant bits. The length parameter gives the number of 32 bit words used to represent each integer.

   For the Hawk version of this procedure, pass pointers to the first words of each array in R3, R4, R5, and pass the length in R6. Your procedure will have to use the ADDC instruction to propagate carries from one 32 bit chunk to the next, and you will have to save the carry bit before decrementing and testing the length to see if the loop is done.

2. Write an efficient SMAL Hawk procedure to clear a block of memory. Here is an inefficient version:

   	;-----------------------
   	clear:			; clear a block of memory
   				; given R3 - pointer to block
   				; given R4 - length of block
   	clelp:
   		ADDIS	R4,-1	; count bytes
   		BLT	cleqt	;   quit if none left
   		LOADS	R5,R3
   		STUFFB	R5,0,R3	; stuff a zero into the byte
   		STORES	R5,R3
   		ADDIS	R3,1	; bump the byte pointer
   		BR	clelp	; iterate
   	cleqt:
   		JUMPS	R1	; return
   

   This version is inefficient because it addresses memory one byte at a time, when it would be possible to clear blocks of 4 words at a time.

3. There are two common ways of representing a stack. A stack can be represented as a linked list of nodes, where the first node in the stack is the top of the stack, and its successor pointer points to the rest of the stack. The alternate representation uses an array and a stack pointer.

   Consider a program where objects of type stack must sometimes be represented with one method and sometimes with the other. We could do this in C++ with a class called stack and two subclasses, array stack and list stack. The methods push and pop would be implemented differently in each.

   Give appropriately commented SMAL Hawk code describing the record data structure for a stack, for an array stack and for a list stack. Do not actually write the code for push and pop for any of these.