CS2208b Lab No. 6 Solved

30.00 \$ 15.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

Description

5/5 - (1 vote)

===RecursionÂ

Recursion is the process of repeating items in a self-similar way. Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method.

In this lab, we will study a recursive subroutine that computes the factorial of a number, using the stack for temporary data storage. Recursion is not the best way to compute the factorial of a number. The intention is to illustrate the use of subroutines and the stack.

The factorial of an integer n (i.e., n!) is the product of all integers from 1 up to n. The factorial is meaningless for negative numbers. The factorial can be expressed recursively, where n! = n Ã— (n â€“ 1)! The basis case which stops the recursion is that 1! = 1. The following C function recursively computes n!,

int fact(unsigned int n)

{

if(n <= 1)Â Â Â Â Â Â Â Â Â  return 1;Â Â Â Â Â Â  else

return n * fact(n-1);

}

For the sake of experimentation only, we will add two local variables to the above function so that we can also experiment with handling local variables. Hence, the function will be as follow:

int fact(unsigned int n)

{

int x,y;Â  Â Â Â Â Â  //useless, just for the sake of experimentations

x = n + 10;Â Â Â Â  //useless, just for the sake of experimentationsÂ Â Â Â Â Â  y = x – 10;Â Â Â Â  //useless, just for the sake of experimentations

if(n <= 1)Â Â Â Â Â Â Â Â Â  return 1;Â Â Â Â Â Â  else

return n * fact(n-1);

}

In ARM assembly, you can convert the algorithm, as well as the caller main function, as follows:

;——————————————————————————–

AREA factorial, CODE, READONLY nÂ Â Â  EQU 3Â Â Â Â Â  ENTRY

Main ADRÂ Â  sp,stackÂ Â Â Â Â  ;define the stack

MOVÂ Â  r0, #nÂ Â Â Â Â Â Â  ;prepare the parameter

STRÂ Â  r0,[sp,#-4]!Â  ;push the parameter on the stack

SUBÂ Â  sp,sp,#4Â Â Â Â Â  ;reserve a place in the stack for the return value

BLÂ Â Â  FactÂ Â Â Â Â Â Â Â Â  ;call the Fact subroutine

LDRÂ Â  r0,[sp],#4Â Â Â  ;load the result in r0 and pop it from the stack

ADDÂ Â  sp,sp,#4Â Â Â Â Â  ;also remove the parameter from the stack

ADRÂ Â  r1,resultÂ Â Â Â  ;get the address of the result variable

STRÂ Â  r0,[r1]Â Â Â Â Â Â  ;store the final result in the result variable

Loop BÂ Â Â Â  LoopÂ Â Â Â Â Â Â Â Â  ;infinite loop

;——————————————————————————–Â Â Â Â Â  AREA factorial, CODE, READONLY

Fact STMFD sp!,{r0,r1,r2,fp,lr} ;push general registers, as well as fp and lr

MOVÂ Â  fp,spÂ Â Â Â Â Â Â Â  ;set the fp for this call

SUBÂ Â  sp,sp,#8Â Â Â Â Â  ;create space for the x and y local variables

LDRÂ Â  r0,[fp,#0x18] ;get the parameter from the stack

ADDÂ Â  r1,r0,#10Â Â Â Â  ;calculate the x value

STRÂ Â  r1,[fp,#-0x8] ;update the value of the local variable x

SUBÂ Â  r1,r0,#10Â Â Â Â  ;calculate the y value

STRÂ Â  r1,[fp,#-0x4] ;update the value of the local variable y

CMPÂ Â  r0,#1Â Â Â Â Â Â Â Â  ;if (n <= 1)

MOVLE r0,#1Â Â Â Â Â Â Â Â  ;{ prepare the value to be returned

STRLE r0,[fp,0x14]Â  ;Â  store the returned value in the stack

BLEÂ Â  retÂ Â Â Â Â Â Â Â Â Â  ;Â  branch to the return section

;}

SUBÂ Â  r1,r0,#1Â Â Â Â Â  ;{ prepare the new parameter value

STRÂ Â  r1,[sp,#-4]!Â  ;Â  push the parameter on the stack

SUBÂ Â  sp,sp,#4Â Â Â Â Â  ;Â  reserve a place in the stack for the return value

BLÂ Â Â  FactÂ Â Â Â Â Â Â Â Â  ;Â  call the Fact subroutine

LDR r1,[sp],#4Â Â Â Â Â  ;Â  load the result in r0 and pop it from the stack

ADD sp,sp,#4Â Â Â Â Â Â Â  ;Â  remove also the parameter from the stack

MULÂ Â  r2,r0,r1Â Â Â Â Â  ;Â  prepare the value to be returned

STRÂ Â  r2,[fp,#0x14] ;Â  store the returned value in the stack

;}

retÂ  MOVÂ Â  sp,fpÂ Â Â Â Â Â Â Â  ;collapse all working spaces for this function callÂ Â Â Â Â  LDMFD sp!,{r0,r1,r2,fp,pc} ;load all registers and return to the caller

;——————————————————————————–Â Â Â Â Â  AREA factorial, DATA, READWRITE result DCDÂ Â  0x00Â Â Â Â Â Â Â  ;the final result

SPACE 0xB4Â Â Â Â Â Â Â  ;declare the space for stack stackÂ  DCDÂ Â  0x00Â Â Â Â Â Â Â  ;initial stack position (FD model)

;——————————————————————————–Â Â Â Â Â Â Â  END

PROBLEM SET

Before you start practicing this lab, you need to review and fully understand how to use the Keil ARM Simulator, Â Â Â Â  as Â Â Â Â Â Â  well Â Â Â  as Â Â Â Â Â Â  tutorial Â Â Â Â Â Â Â Â Â  9 Â Â Â Â Â Â Â Â  (Tutorial_09_ARM_Block_Move.pdf) Â Â Â Â  and Â Â Â Â Â Â Â Â Â Â Â  tutorial Â Â Â Â Â Â Â Â Â  10 (Tutorial_10_ARM_Stack_Frames.pdf).

1. Fully understand the code above. Definitely, you MUST do more effort than just quickly scanning the code.
2. How many stack bytes does the Fact subroutine need in each time it is called?
3. Sketch what a stack frame looks like. Include in your drawing the pushed parameter, the pushed returning value, the location of the current FP pointer, and the offset of each item in the stack relative to the current FP
4. How many function calls will be performed to calculate Fact(3)?
5. Sketch the content of the stack at its maximum occupancy when Fact(3) is called?

• the name of the stack element content (e.g., local variable x, local variable y, pushed r0 register, returning value, passed parameter),
• the value of each stack element, and o the part of the code that pushed this value.
1. Verify your answer in Q5 by running the program and comparing the actual stack values with the sketched stack values.
2. The length of the current stack is 0xB4. What is the maximum factorial that can be calculated using this stack?
3. Verify your answer in Q7 by running the program and examining the generated values for n! and (n+1)!, where n is your answer in Q7.
4. What is the minimum stack size that you need to use to be able to correctly calculate Fact(12)?
5. Verify your answer in Q9 by changing the stack size as suggested in your answer in Q9, then run the program, and examine the generated value for 12!.
6. If you managed to increase the stack size to accommodate all the required pushes when calling Fact(13), will you get the correct result of 13!?