====================== Doing something useful [TOC] ====================== You probably are tired of writing programs for computing the factorial. So I wrote one for you that uses functions. Your job will be to write a program that computes the _greatest common divisor (gcd)_. Calling conventions for Quiz06 ============================== ---- BOX ----------------------------------------------------------------------- This is what caller and callee have to know about each other in this Quiz: The symbols `RET`, `CALLEE0`, ..., `CALLEE3` are defined and are used for functions calls as follows: - The caller uses `%RET` for the return address (so a callee can return with `jmp %RET, %0`). - Functions can receive at most four arguments. The callee expects to receive them as follows: - First argument in `%CALLEE0` - ... - Forth argument `%CALLEE3` If a function returns a value the callee will store it in `%CALLEE0` before returning. The callee is only allowed to use the register `%CALLEE0`, ..., `%CALLEE3`. These registers are consecutive (which is important to know for using instructions like `divq` that operate on register pairs and register triplets). -------------------------------------------------------------------------------- Quiz06: Computing the greatest common divisor ============================================= Write a program `gcd.s` that computes for two 64-bit unsigned integers the greatest common divisor (gcd). Provide the user a nice experience, i.e. using the program looks like this: ---- CODE (type=txt) ----------------------------------------------------------- theon$ ulm gcd a = 18 b = 12 gcd(18, 12) = 6 theon$ ulm gcd a = 350982 b = 822647 gcd(350982, 822647) = 527 -------------------------------------------------------------------------------- Use the following algorithm for your implementation: --- TIKZ --------------------------------------------------------------------- \begin{adjustbox}{} \textcolor{white}{.} \begin{varwidth}{10cm} \begin{algorithmic} \Function{gcd}{$a, b$} \If{$a = 0 \;\lor\ b=0$} \State \textbf{return} $0$ \EndIf \While{$a\not=b$} \If{$a > b$} \State $a\gets a - b$ \Else \State $b\gets b - a$ \EndIf \EndWhile \State \textbf{return} $b$ \EndFunction \end{algorithmic} \end{varwidth} \end{adjustbox} ------------------------------------------------------------------------------ Submit your program with ---- CODE (type=txt) ----- submit hpc quiz06 gcd.s -------------------------- Conditional jumps for equalities and inequalities ================================================= So far we only have covered the conditional jumps `__jz__` and `__jnz__`. These can be used for realizing conditions like $x = y$ or $x \neq y$: - Jump if $y = x$ is realized by the pattern: compute $y-x$ and check if the zero flag is set: ---- CODE (type=s) ----------------------------------------------------------- subq %X, %Y, %0 jz some_label ------------------------------------------------------------------------------ - Jump if $y \neq x$ is realized by the pattern: compute $y-x$ and check if the zero flag is not set: ---- CODE (type=s) ----------------------------------------------------------- subq %X, %Y, %0 jnz some_label ------------------------------------------------------------------------------ For inequalities we proceed accordingly. But we have to distinguish whether the bit pattern are used for signed or unsigned integers: - For unsigned integers instructions `ja` (jump above), `jae` (jump above equal), `jb` (jump below), `jbe` (jump below equal) can be used. In all these cases first compute $y-x$ and then choose what condition should cause a jump: - `ja` jumps if $y-x > 0$. - `jae` jumps if $y-x \geq 0$. - `jb` jumps if $y-x < 0$. - `jbe` jumps if $y-x \leq 0$. - For signed integers instructions `jg` (jump greater), `jge` (jump greater equal), `jl` (jump less), `jle` (jump less equal) can be used. In all these cases first compute $y-x$ and then choose what condition should cause a jump: - `jg` jumps if $y-x > 0$. - `jge` jumps if $y-x \geq 0$. - `jl` jumps if $y-x < 0$. - `jle` jumps if $y-x \leq 0$. Example for computing the factorial =================================== This is actually the program for computing the factorial that I showed in a video before. If you use it interactively it looks and feels like that: ---- CODE (type) --------------------------------------------------------------- theon$ ulm factorial n = 20 20! = 2432902008176640000 theon$ ulm factorial n = 0 0! = 1 theon$ ulm factorial n = 3 3! = 6 theon$ ulm factorial n = 10 10! = 3628800 -------------------------------------------------------------------------------- Here the output when it is used non-interactive (by piping an `echo` output): ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o factorial factorial.s echo 20 | ulm factorial echo 0 | ulm factorial echo 1 | ulm factorial echo 10 | ulm factorial -------------------------------------------------------------------------------- For $n>20$ we get $n! \bmod 2^{64}$ as result (of course the ULM would provide instructions for computing that with 128 bits or more): ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o factorial factorial.s echo 21 | ulm factorial -------------------------------------------------------------------------------- Have a good look at it! Not just because it is nice but also because you can use ideas for the assignment ;-) :import: session09/func/factorial.s Skeleton for `quiz06` ===================== ---- SHELL (path=session09/func) ----------------------------------------------- ulmas -o gcd gcd_skeleton.s (echo 350982; echo 822647) | ulm gcd -------------------------------------------------------------------------------- :import: session09/func/gcd_skeleton.s :links: jz -> http://www.mathematik.uni-ulm.de/numerik/hpc/ss20/hpc0/ulm.pdf#page=20 jnz -> http://www.mathematik.uni-ulm.de/numerik/hpc/ss20/hpc0/ulm.pdf#page=26 :navigate: up -> doc:index back -> doc:session09/page02 next -> doc:session09/page04