# 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.

Updated Thu June 01 2023, 11:23 by ggbaker.