# Lab Exercise 4

Provided code: lab4.zip.

For this exercise, you will write several assembly functions in `lab4.S`

. The provided `lab4.h`

gives details of the type signatures of the functions, and `tests.c`

contains some reasonably-complete test cases.

## Is A Number Prime?

Write a function `is_prime`

that takes a single (unsigned integer) argument (which you can assume is >1), and returns 1 if it's a prime number, and 0 otherwise. We aren't going to worry about a clever algorithm here: we will simply check every number from 2 to *n*-1 to see if it divides *n*:

```
def is_prime(n):
i = 2
while i < n:
if n % i == 0:
return 0
i += 1
return 1
```

The `div`

instruction divides unsigned integers and calculates their remainder, but it's unusual. It always divides the value `%rdx:%rax`

(i.e. a 128 bit value with the high bits stored in `%rdx`

and the lower bits in `%rax`

) by its single operand. It always leaves the quotient in `%rax`

**and** remainder in `%rdx`

.

You can get `%rdi`

divided by `%r8`

in `%rax`

and remainder in `%rdx`

like this. The first two instructions set `%rdx:%rax`

to the value from `%rdi`

(by putting bunch of leading zeros in `%rdx`

).

```
mov $0, %rdx
mov %rdi, %rax
div %r8
```

## Unsigned Overflow

Write an assembly function `largest_power_unsigned`

that takes an unsigned integer as its argument and returns the **largest power** of that number that's representable as a 64-bit unsigned integer.

In order to find that value, you need to repeatedly multiply by \(n\) until you see an unsigned overflow and return the value *before* you saw the overflow.

The value you return \(p\) should be a power of \(n\), so \(n^i=p\) for some \(i\), such that \(p<2^{64}\) and \(np\ge 2^{64}\). (But you can't detect it with math: you need to calculate and watch the carry flag.)

## Signed Overflow

Write a function `overflowing_subtract(a, b)`

that take two **signed** integer arguments. It should usually return `a-b`

, unless that calculation is a signed overflow then it should return zero.

## Recursion

Write an assembly function `dumb(a, b)`

that takes two unsigned integer arguments and implements this recursive calculation (that's called "dumb" because it does a dumb calculation that makes no sense, but that's the task):

```
def dumb(a, b):
if a == 0:
return b
elif b == 0:
return a
else:
return a + b + b + dumb(a - 1, b - 1)
```

You must use the stack to store the `a`

and `b`

values across the recursive call.

## Submit

Submit your work to Lab 4 in CourSys.