Homework 5  Prime
From now on, we’ll assume that you work on homework by connecting to the CS portal and that you are familiar with the command line environment. If you have not been practicing with the terminal, we strongly encourage reviewing Lab 1.
We will also assume that you ran the setup script from that lab and have all modules (including clang and git) by default.
Introduction
In this assignment you need to write x8664 assembly by hand. This is not something most programmers do often, but when it comes up in the workplace being one of the few there who can do it will help your company and make you shine.
We provide a base file (named prime.s
) that includes the input and output interaction (in main
and printNum
) to test the code you will write. You may copy that file to your home directory (or cso1code directory) by using the cd
command to enter the directory in which you wish to work and then copying the file in:
cp /p/cso1/homework/prime.s .
It will be most helpful to cd
into your cso1code
gitmanaged directory first to work on this assignment.
Once you have a local copy of the file, you can begin to write the functions below. Specifically, write your code where the comments say “TO DO: write this function”.
NOTE: You may NOT use a compiler to write your code. You must write x8664 assembly by hand. Using a compiler will result in a 0 for this assignment.
Writing your code
Thomas Doepper at Brown as created a amazing reference sheet for x8664 assembly instructions. You can find that reference here
We are expecting that you will write your code in a commandline editor (vim, nano, etc) on the portal. If you need to refresh, please review Lab 1.
Why a CLI editor?
It is common to interact with servers that do not have their own monitors. In these cases, you typically attach to the server via
ssh
and have access only to a terminal, not a full windowing environment. The more comfortable you are with doing common programming tasks in the terminal, the better these experiences will be.
Testing your code
We recommend using git
to version and test your code. Each time you make changes, you can git add
, git commit
, and git push
to keep a backup copy of your changes. You can also use git to git pull
your changes to your laptop to submit to Gradescope.
For example:
 Use a git project for this HW and check it out on both your laptop and the server. You can use the same project you made in Lab 6 or a new one for just this HW
 Copy the
prime.s
file into that project directory on the portal (in your home directory) andgit add prime.s
to tellgit
to track it  Edit and test on the portal, and when you want to submit it to Gradescope
 edit with vim or nano
 compile with
clang prime.s
and run with./a.out
 commit your edits (e.g.
git commit a m 'I think I got product working now'
)  push your committed edits (e.g.
git push
)  tell the copy on your laptop to pull (e.g.
git pull
)  submit the copy on your laptop to Gradescope
This way you’ll both (a) have a backup of every version, (b) have a copy on the server in case something happens to your laptop (and vice versa), and (c) know you’re using the same compiler, processor variant, etc, that we are.
Write three functions
In AT&T syntax x8664 assembly, write three routines: one that computes the modulo of two numbers (without using division or multiplication), one that computes the greatest common divisor (GCD) of two numbers (using your modulo function), and one that determines if a number is prime (using your GCD function).
It should be possible to assemble your code by typing clang prime.s
to generate a file, a.out
, that can be run by by typing ./a.out
. When run, it should^{1} ask for two integers and display their modulo, greatest common divisor, and whether each is prime.
Modulo
The first subroutine, modulo
, should compute and return the modulo of the two integer arguments (the first modulo the second). It must not use multiplication or division instructions. It must compute this iteratively, not recursively. You may follow your logic from Homework 3, Homework 4, or the logic given in Lab 6 (repeated in the example below).
Example: There are other correct solutions, but a simple one might follow an approach like the following pseudocode:
function modulo(x, y)
while (x >= 0)
x = y
x += y
return x
end function
You may assume that both of the parameters are nonnegative integers, that \(x \ge y\), and that the result can fit in a single 64bit register. We define modulo(x, 0) to be 0.
GCD
The second subroutine, gcd
, should compute and return the greatest common divisor between its two arguments. It must use the modulo
routine you wrote to do this, not x8664 multiplication or division instructions or other routines you did not write. It must compute this recursively, not iteratively. You may find the logic you used for Homework 4 helpful when writing GCD.
Example: There are other correct solutions, but a simple one might follow an approach like the following pseudocode:
function gcd(x, y)
if x == y then
return y
else if y == 0 then
return x
else
return gcd(y, modulo(x, y))
end if
end function
You may assume that both of the parameters are nonnegative integers, that \(x \ge y\), and that the result can fit in a single 64bit register. We define gcd(x,0) to be x.
Prime
The third subroutine, prime
, should determine if its argument is prime and return 1 if the argument is prime and 0 otherwise. It must use the gcd
routine you wrote to do this, not x8664 multiplication or division instructions or other routines you did not write. It must compute this iteratively.
Example: There are other correct solutions, but a simple one might follow an approach like the following pseudocode:
function prime(x)
for (i = 1; i < x; i++)
if (gcd(x, i) != 1)
return 0
end if
end for
return 1
end function
You may assume that the parameter is a positive integers (i.e., neither zero nor negative) and that the result can fit in a single 64bit register.
Submit
Submit your assembly as prime.s
via Gradescope.
NOTE: You may NOT use a compiler to write your code. You must write x8664 assembly by hand. Using a compiler will result in a 0 for this assignment.

Along the way, you might accidentally write code that runs forever. If the program freezes while running, try pressing Ctrl+C to interrupt it. ↩