Program $10$: Factorials

The two standard recursion formulas used in teaching programming skills are the Fibonacci series and factorials. We will write a program that calculates $9!$ and prints the number to stdout. In the next program, we will build the Fibonacci program.

An easy recursion method for factorials is to define a reentrant function that has the following behavior. When called, the function saves the count $($or input value$)$ then subtracts one from the count. If the reduced count is greater than $1,$ then call itself again with the reduced count. Otherwise on $1,$ the function returns to the caller function with a result of $1.$ When the callee function returns, take the result and multiply it with the saved count or input value. Return the product value to the caller function.

In the main template, we see that our itoa code and nullwrite code will be used again. We will also need the pow macro. Before we blindly throw these code macros together, let's spend the time to rewrite our macros into proper functions: itoa, pow, and nullwrite, with frames that we can call whenever needed and without worry of loosing register values upon calling. We are basically building a primitive static library and using it in the linking phase.

Before building the final executable file, create a makefile that will automatically assemble the source files and link the object files together.

Below is an additional guide in the form of a chart of recursive calls.

$\_$start $+$ factorial$(9)|+$ factorial$(8)||+$ factorial$(7)|||+$ factorial$(6)||||+$ factorial$(5)|||||+$ factorial$(4)||||||+$ factorial$(3)|||||||+$ factorial$(2)||||||||+$ factorial$(1)|+$ itoa$($ product $)|+$ pow$(10)|+$ pow$(9)|+$ pow$(8)|+$ pow$(7)|+$ pow$(6)|+$ pow$(5)|+$ pow$(4)|+$ pow$(3)|+$ pow$(2)|+$ pow$(1)|+$ pow$(0)+$ nullwrite$($ string $)$Coding Template

main.s

$//$ Program $10$: Factorials $////$ A program that calculates $9!$ and prints the number to stdout. $////$ Suggested Register Usage: $//$ w$0$: total $//$ w$1$: current number $//-----------------------------------------------------------------------------//$ Macros for common stack operations $////$ Examples: using push and pop to preserve the link register and frame pointer $//$ push lr fp $//$ pop lr fp $//$ push operand $.$macro push xn$0,$ xn$1$ stp $\backslash$xn$0,\backslash$xn$1,[$sp$,-16]!.$endm $//$ pop operand $.$macro pop xn$0,$ xn$1$ ldp $\backslash$xn$0,\backslash$xn$1,[$sp$],16.$endm $//-----------------------------------------------------------------------------//$ Factorial main routine $//$ Factorial beginning number $.$equ maxnum, $9.$global $\_$start $.$text $\_$start: $//$ create a frame for main and preserve LR and FP registers on the stack $//$ prepare and call the factorial function with maxnum as argument in X$0//$ call the itoa function to convert the integer result to a char string $//$ call the nullwrite function to write the string to the screen $//$ restore the LR and FP registers from the stack frame $//$ exit back to the operating system $//-----------------------------------------------------------------------------//$ Factorial function subroutine factorial: $//$ create a new frame and preserve the LR and FP registers on the stack $//$ push the caller's argument X$0($recursion value$)$ onto the stack frame $//$ test recursion value for $1$; on $1$ branch to fact$\_$exit $//$ prepare to call factorial function again with value minus $1//$ load the caller's argument $($recursion value$)$ from the stack frame $//$ multiply the called function's returned value X$0$ with the argument fact$\_$exit: $//$ restore the LR and FP registers from the stack frame $//$ return back to the caller function $.$data outstr: $.$fill $16//16$ bytes or character spaces for holding the string buffer

makefile

# Define the object files you need for the final executable OBJS $=$ main.o itoa.o $...$ # The next line uses $\%$ which is a wildcard char to refer to all $.$s and $.$o files $\%.$o : $\%.$s # $$<=$ source file, $@ $=$ output file as $$<-$g $-$o $@ # build the main executable main: $$($OBJS$)$ ld $-$o main $$($OBJS$)$

Expected Output

username@test$1$:~$/$cs$1337/$lab$\_7/$prog$\_10$$ ls itoa.s main.s makefile write.s username@test$1$:~$/$cs$1337/$lab$\_7/$prog$\_10$$ make as $-$o itoa.o itoa.s as $-$o main.o main.s as $-$o write.o write.s ld $-$o main itoa.o main.o write.o username@test$1$:~$/$cs$1337/$lab$\_7/$prog$\_10$$ $./$main $362880$ username@test$1$:~$/$cs$1337/$lab$\_7/$prog$\_10$$ echo $$?0$ username@test$1$:~$/$cs$1337/$lab$\_7/$prog$\_10$$ $\_$