This assignment has two parts, and an optional extra credit part.
The text presents on page 5 an implementation of the classic Euclidean algorithm for computing the greatest common denominator (GCD) (also known sometimes as the greatest common factor (GCF)). The implementation is for a 32bit x86 processor using GAS syntax, and is optimized from code compiled in classic C compiler fashion (which you can find on page 35) which originally used the stack extensively for temporary variables.
I have re-implemented the code for an x86_64 processor using NASM / YASM syntax. I changed the algorithm from the original Euclidean subtraction method to the more common algorithm using the modulo operator, since the modulo operator has hardware support on the x86 family. I also added the necessary code to make this a complete x86_64 program on a Linux machine:
The code for my implementation can be found on this page. You will need to download the code to work on this assignment; the easiest way to get the code is to download the tar file.
Copy the file "gcd.yasm" to a new file called "gcd-euclid.yasm". Change the algorithm in your new file back from my modulo version to the subtraction algorithm as presented in the book. Your new code must not use a DIV (or IDIV) instruction; it must use a version of the SUB instruction.
(Note that you cannot just cut and paste; the new code is in a different assembly syntax (YASM rather than GAS), the new code is for the wider 64bit registers in the x86_64 family, and I use somewhat different registers than the page 5 implementation.)
Modify the "Makefile" to use your new module "gcd-euclid.yasm" rather than my "gcd.yasm".
Currently, when you give an argument of zero for either of the numbers, you get an "floating exception":
(linprog3:~/gcd-x86) langley% ./gcd 27 0
Floating exception
(linprog3:~/gcd-x86) langley% strace ./gcd 27 0
strace ./gcd 27 0
execve("./gcd", ["./gcd", "27", "0"], [/* 49 vars */]) = 0
--- SIGFPE {si_signo=SIGFPE, si_code=FPE_INTDIV, si_addr=0x4000c6} ---
+++ killed by SIGFPE +++
Floating exception
Since any number divides zero, it would be more correct to return the larger number if one of the supplied integers is zero. Please change the appropriate code to make this the case: if either (but not both) of the supplied integers is a zero, then have the program immediately return the non-zero number rather than try to compute an answer.
If both numbers are zero, then return a zero.
For instance, your program should now return:
(linprog3:~/gcd-x86) langley% ./gcd 27 0 27 (linprog3:~/gcd-x86) langley% ./gcd 0 13 13 (linprog3:~/gcd-x86) langley% ./gcd 196434253 1951006397 10427 (linprog3:~/gcd-x86) langley% ./gcd 0 0 0
Please add comments with your initials to the lines that you add or modify; if you remove a line, then comment it out and add a note with your initials.
There are a number of algorithms for computing the GCD of two integers; a version by Stein is called the "Binary GCD" algorithm. It is a bit more amenable to general computer implementation than either the original Euclidean version or the modulo version since it uses only shifts and comparisons. You can find a good discussion of this algorithm here.
For this step, please copy my "gcd.yasm" to a new file called "gcd-binary.yasm". Modify that file with your reimplementation of Stein's binary GCD algorithm. Modify the "Makefile" so that it now makes two binaries: a "gcd" (which should have your part 1 and part 2 code), and a "bgcd" version that also uses your new "gcd-binary.yasm" rather than "gcd-euclid.yasm" (and should of course incorporate your part 2 code.)
Tar everything back together ("tar cf gcd-x86.tar gcd-86"), and submit the tar file on Canvas.