Name your source code file h3-1.s Let lower and upper be two positive integers with 1 lower, upper 103 and lower upper. Let a and b be two positive integers with lower a, b upper and a b. Let x =a b. For all pairs of a and b satisfying the specified conditions, find and print the maximal value of x. For example, suppose lower = 10 and upper = 13. The algorithm will compute x for each a, b pair where 10 a, b 13 and a b,

x = 10 10 = 1010₂ 1010₂ = 0000₂ = 0₁₀

x = 10 11 = 1010₂ 1011₂ = 0001₂ = 1₁₀

x = 10 12 = 1010₂ 1100₂ = 0110₂ = 6₁₀

x = 10 13 = 1010₂ 1101₂ = 0111₂ = 7₁₀

x = 11 11 = 1011₂ 1011₂ = 0000₂ = 0₁₀

x = 11 12 = 1011₂ 1100₂ = 0111₂ = 7₁₀

x = 11 13 = 1011₂ 1101₂ = 0110₂ = 6₁₀

x = 12 12 = 1100₂ 1100₂ = 0000₂ = 0₁₀

x = 12 13 = 1100₂ 1101₂ = 0001₂ = 1₁₀

x = 13 13 = 1101₂ 1101₂ = 0000₂ = 0₁₀

The maximal value of x is 7 when a, b = 10, 13 and a, b = 11, 12. The output from the program should be 7. Here is the pseudocode for the algorithm which solves this problem,

function max_xor (lower : unsigned int, upper : unsigned int) unsigned int

unsigned int a, b, max, x

max 0

for a lower to upper do

for b a to upper do

x a b

if x > max then max x

end for

end for

return max

end function max_xor

function main ()

unsigned int lower, max, upper

SysPrintStr ("Enter lower? ")

lower SysReadInt()

SysPrintStr ("Enter upper? ")

upper SysReadInt ()

max max_xor (lower, upper)

SysPrintInt (max)

SysExit ()

end function main

Complete the following exercises (name your source code file h3-1.s).

a. Rewrite the pseudocode for max_xor() converting the two for loops into functionally-equivalent while loops.

b. Rewrite the max_xor() function from Exercise 5a converting the code using while loops into equivalent code that only uses if statements and goto's. Also, rewrite the if statement inside the loops to be an if statement and a goto (see pp. 2427 of the Ch. 2 lecture notes).

c. The rewritten max_xor() function from 5b should now map directly onto the assembly language version of the function. Write the function in assembly language.

d. Implement main(). Test your max_xor() function by running main() with several test cases.

Miscellaneous notes, hints, and requirements:

1. Study the assembly language source code files listed in the course notes and posted on the course website. Format your code in a similar manner, i.e., an assembly language line containing an instruction consists of four columns of mostly-optional stuff: column 1 is aligned with the left margin and is reserved for an optional label; column 2 is indented from column 1 by around 4-8 spaces and is reserved for instruction mnemonics; column 3 is indented from column 2 and reserved for optional operands; column four is indented from column 3 and is reserved for optional comments. How many spaces or tabs you indent is up to you, the important thing is to line things up in columns and be consistent.

2. See Exercise 18 in the Homework Assignment 2 solution and grading rubric document and note how I wrote a comment for every instruction. In h3-1.s write a meaningful and descriptive comment in column 4 of each line of code containing an instruction.

3. Note that max_xor() is a leaf procedure (because it does not call other procedures) and as long as there are enough registers to store all of the local variables, a leaf procedure does not really need to create a stack frame because it does not need save $ra or any of the $ax argument registers. However, one of the objectives of this exercise is for you to demonstrate that you know how to write a function that creates a stack frame, allocates function parameters and local variables within the stack frame, accesses parameters and local variables in the stack frame, and deallocates the stack frame before returning. Consequently, your solution shall create a stack frame for both main()which is not a leaf procedureand max_xor(). The stack frame for main() shall contain the three local variables lower, max, and upper. main() will pass the arguments to max_xor() in the $a0 and $a1 registers. max_xor() will allocate a stack frame containing space for the two parameter variables lower and upper and the four local variables a, b, max, and x. When a new line of HLL code is reached and the value of a variable is needed, write instructions which will read the value of the variable from memory or write a new value to the variable in memory, i.e., do not just keep the values of the local variables in registers. max_xor() will send the return value back to main() in the $v0 register.

4. All local variables shall be allocated in the function's stack frames. The only data allocated in the data section shall be the string literals.

5. You may not use any non-standard MARS instructions and pseudoinstructions, but you may use the pseudoinstructions we discussed in 2.3.8 of the Ch. 2 lecture notes.

6. Your program must properly terminate by calling the SysExit() system call.