Homework 9

22C:122, Fall 1998

Here is code to compute the reciprocal of an unsigned integer on a binary computer. This uses unsigned long int arithmetic and returns the reciprocal of an unsigned int as an unsigned int, with the point implicitly at the left end of the word.

	unsigned int recip(x)
	unsigned int x;
	/* binary search for reciprocal of x */
	{
		unsigned long int r = 0; /* approximation of reciprocal */
		int i;
		for (i = sizeof( int )-1; i>=0; i--) {
			unsigned long int t = r | (1 << i); /* trial */
			if (((t * x) >> sizeof( int )) == 0) {
				r = t;
			}
		}
		return (unsigned int) r;
	}

The following calling sequence on the PDP-11 makes effective use of the MARK instruction:
```
    MOV R5,(-SP)	; push old value of R5

      ... 		;  code to push n parameters

    MOVE #(MARK n),R5	; put mark on stack
    JSR R5,PROC		; call proc.
```
The corresponding receiving and return sequences are:
```
PROC:

      ...		; code for body of procedure

    JMP (SP)		; jump to mark instruction on stack
```
The mark instruction (sitting on the top word of the stack) takes care of popping the parameters off the stack and finishing the return from the procedure.
Here is an appropriate calling sequence for a machine where the hardware has only a basic branch and link instruction and no designated stack pointer register. The instruction mnemonics used are inventions, but the register transfer notation in the comments indicates the intended meaning.
```
    BAL	 R1,PROC	; R1 = PC; PC = PROC
    W	 ARS		; size of caller's AR
```
Here is the corresponding receiving and return sequence:
```
PROC:
    ADDS R2,R1		; R2 = R2 + M[R1] -- add size of caller's AR
    STS  R1,R2		; M[R2] = R1 -- store return address

      ...		;   body of proc

    LDS  R1,R2		; R1 = M[R2] -- recover return addr
    SUBS R2,R1		; R2 = R2 - M[R1] -- restore the AR pointer
    INC	 R1		; bump return address over inline param
    JR   R1		; PC = R1
```
The above code assumes that, within the body of each procedure, R2 points to the base of the activation record for that code. The first location in each activation record is used to store the return address, and the size of each function's activation record is passed as an inline parameter on the call. There are no push or pop operations for individual words here!
There are, of course, many alternatives to the above suggested calling sequence.