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 x86-64 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 cso1-code 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 cso1-code git-managed 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 x86-64 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 x86-64 assembly instructions. You can find that reference here

We are expecting that you will write your code in a command-line 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:

1. 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
2. Copy the prime.s file into that project directory on the portal (in your home directory) and git add prime.s to tell git to track it
3. Edit and test on the portal, and when you want to submit it to Gradescope
   1. edit with vim or nano
   2. compile with clang prime.s and run with ./a.out
   3. commit your edits (e.g. git commit -a -m 'I think I got product working now')
   4. push your committed edits (e.g. git push)
   5. tell the copy on your laptop to pull (e.g. git pull)
   6. 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 x86-64 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¹ 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 pseudo-code:

function modulo(x, y)    
    while (x >= 0)
        x -= y
    x += y
    return x
end function

You may assume that both of the parameters are non-negative integers, that \(x \ge y\), and that the result can fit in a single 64-bit 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 x86-64 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 pseudo-code:

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 non-negative integers, that \(x \ge y\), and that the result can fit in a single 64-bit 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 x86-64 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 pseudo-code:

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 64-bit register.

Submit

Submit your assembly as prime.s via Gradescope.

NOTE: You may NOT use a compiler to write your code. You must write x86-64 assembly by hand. Using a compiler will result in a 0 for this assignment.

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