11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
Project 3: Rollin with Stack pointers
Due Saturday by 11:59pm Points 10 Submitting a file upload
File Types asm, s, and a
Submit Assignment
Task
For your third project, you will be tasked with writing a procedure that solves this formula given a user input
for the missing paramater (n).
Unlike the previous project, you are required to use procedures and recursion here. Notice that the equation
has the same format as factorial. So let us consider the recursive implementation of factorial in C. When
solving a problem recursively you are usually given two approaches. The bad way which is what you
probably have learned in your introductory class and tail call recursion.
Derpy recursion:
int factorial(int n) {
return n<0 ? -1 : n == 0 ? 1 : n * factorial(n - 1);
}
Tail call recursion:
int fac_aux(int n, int acc) {
return n < 1 ? acc : fac_aux(n - 1, acc * n);
}
int factorial(int n)
{
return fac_aux(n, 1);
}
As we have discussed before, the tail call recursive function can be optimized by the compiler to run in a
loop instead of being recursive. However, even if we are not optimizing our code, it is still much easier to
visualize tail call recursion instead of regular recursion, since it has the structure of a loop.
Approach:
11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
First, you want to plan ahead. Convert the equation into a C function. The one thing to keep an eye on is
that division requires precision, therefore you will have to either use double or float for the answe
double myFunction(int n) {
return n == 1 ? 5.0 : ((4.0/n) + n*n*n) * myFunction(n - 1);
}
or alternatively
double myFunc_aux(int n, double acc) {
return n < 1 ? acc : myFunc_aux(n - 1, acc * ((4.0/n) + n*n*n));
}
double myFunction(int n)
{
return myFunc_aux(n, 5.0);
}
Like Project 2, your first step should be to
eak up the C function into modular components, translate them
into assembly instructions and then reconstruct them in either MIPS or ARM
MIPS
Unlike before you will have to actually follow the register convention function calls in MIPS
$0 $zero Hard-wired to 0
$1 $at Reserved for pseudo-instructions
$2 - $3 $v0, $v1 Return values from functions
$4 - $7 $a0 - $a3 Arguments to functions - not preserved by subprograms
$8 - $15 $t0 - $t7 Temporary data, not preserved by subprograms
$16 - $23 $s0 - $s7 Saved registers, preserved by subprograms
$24 - $25 $t8 - $t9 More temporary registers, not preserved by subprograms
$26 - $27 $k0 - $k1 Reserved for kernel for the inte
upt/trap handler. Do not use!
$28 $gp Global Area Pointer (base of global data segment)
11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
$29 $sp Stack Pointe
$30 $fp Frame Pointe
$31 $ra Return Address
$f0 - $f3 - Floating point return values
$f4 - $f10 - Temporary registers, not preserved by subprograms
$f12 - $f14 - First two arguments to subprograms, not preserved by subprograms
$f16 - $f18 - More temporary registers, not preserved by subprograms
$f20 - $f31 - Saved registers, preserved by subprograms
You will also have to use the FPU. In some cases, you will need to send numbers from and to the CPU and
the FPU.
FP instructions available in MIPS:
add.s fd, fs, ft #FP add single
cvt.s.w fd, fs #Convert to single precision FP from integer
cvt.w.s fd, fs #Convert to integer from single precision FP
div.s fd, fs, ft #FP divide single
mfc1 rd, fs #move from coprocessor 1 (FP)
mov.s fd, fs #move FP single precision FP
mtc1 rs, fd #move to coprocessor 1 (FP)
mul.s fd, fs, ft #FP multiply single
sub.s fd, fs, ft #FP subtract single
The structure of your function should have the following structure
# Comment information about the name of program and description of the function
# double myFunction(int n) {
# return n == 0 ? 5.0 : (((double)1/n) + 4*nn) * myFunction(n - 1);
# }
myRecFunc: # Procedure Entry
addi $sp, $sp, -8 #allocate space on the stack for:
sw $a0, 0($sp) #argument
sw $ra, 4($sp) #return address
11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
# < -8 if you have local variables you need to sstore
#
anch to either a recursivecall or the base condition
#Restore the registers, "recursive anchor"
lw $ra, 4($sp)
lw $a0, 0($sp)
## whichever you didn't
anch to
jr $ra #return to calle
ecursiveCall: addi $a0, $a0, -1 # decrement n by 1
jal myRecFunc
# Procedure Exit
lw $ra, 4($sp) # Restore the registers
lw $a0, 0($sp) # Restore the registers
addi $sp, $sp, 8 # Restore the stack pointe
# calculate (((double)1/n) + 4*n*n) * myFunction(n - 1);
jr $ra #return to calle
# End of program, leave a blank line afterward
If you wish, you can wrap a main function around your assembly instruction for testing purposes;
# Comment information about the name of program and description of the function
# main()
# {
# int n;
# printf("Enter a value for n \n")
# scanf("%d",&n);
# printf("f(%d) = %lf",n,myFunction(n));
# return 0;
# }
# double myFunction(int n) {
# return n == 0 ? 5.0 : (((double)1/n) + 4*n*n) * myFunction(n - 1);
# }
11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
XXXXXXXXXXdata # variable declarations follow this line
msg: XXXXXXXXXXasciiz "Enter a value for n \n"
esult1: .asciiz "f("
esult2: .asciiz ") = "
newline: .asciiz "\n"
XXXXXXXXXXtext # instructions follow this line
main: # indicates start of code (first instruction to execute)
# Prompt the user for the value of n
XXXXXXXXXXli $v0, 4
XXXXXXXXXXla $a0, msg
XXXXXXXXXXsyscall
# get user input
XXXXXXXXXXli $v0, 5
XXXXXXXXXXsyscall
# store user input in a registe
XXXXXXXXXXadd $t0, $0, $v0
XXXXXXXXXXli $v0, 4
XXXXXXXXXXla $a0, result1
XXXXXXXXXXsyscall
XXXXXXXXXXadd $a0, $0, $t0
XXXXXXXXXXli $v0, 1
XXXXXXXXXXli $t0, 5 # $integer to print
XXXXXXXXXXsyscall
# pass n as an argument to the recusive function
XXXXXXXXXXjal myRecFunc
#Print result
XXXXXXXXXXli $v0, 4
XXXXXXXXXXla $a0, result2
XXXXXXXXXXsyscall
#result is cu
ently stored in #$v0 if integer, or $f0-$f3 if flaot/double
XXXXXXXXXXmov.d $f12, $f0 # Move contents of register $f4 to register $f12 to print
XXXXXXXXXXli $v0, 3
XXXXXXXXXXsyscall
#end of main
XXXXXXXXXXli $v0, 10
XXXXXXXXXXsyscall
ARM:
ARM should be the same as the MIPS instruction except you will be using the VFP Coprocesso
(http:
infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0133c/index.html) for floating point
http:
infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0133c/index.html
11/28/2019 Project 3: Rollin with Stack pointers
https:
canvas.csun.edu/courses/63658/assignments/ XXXXXXXXXX/6
arithmetics.