# RISC-V Toolchain 2
###### tags: `Computer Architecture 2020`
## [GCD (Greatest Common Divisor)](https://hackmd.io/@cccccs100203/lab1-RISC-V)
The following assembly program was implemented by 洪邵澤同學.
### RISC-V asm with recursion

.data
in1: .word 24
in2: .word 16

.text
main:
	lw a0, in1
	lw a1, in2
	jal GCD
	li a7,1
	ecall
	j end

GCD:
	beqz a1,return      # if(a1 = 0)  t0 = 0;
	#blt a0, a1, swap   # if(a0 > a1) goto SWAP;
	rem a0, a0, a1      # a0 = a0 % a1;
swap:
	mv t1, a0
	mv a0, a1
	mv a1, t1
	j GCD
return:
	jr ra
end:

### Rewrite in C
int main() was replaced by void _start() and mod was added manually, and print the result on console in binary.

int gcd(int u, int v);
unsigned int mod(unsigned int a, unsigned int b);

void _start() {
    volatile int n = gcd(1840564, 836620);
    volatile char *tx = (volatile char *)0x40002000;
    unsigned int i;
    for (i = 0x80000000; i; i >>= 1) {
        *tx = ('0' + ((i & n) ? 1 : 0));
    }
}

int gcd(int u, int v){
    int tmp;
    while (v) {
    	tmp = v;
	v = mod(u, v);
	u = tmp;
    }
    return u;
}

unsigned int mod(unsigned int a, unsigned int b){
    unsigned long long rem = 0x00000000ffffffff & a;
    signed long long bHigh = (signed long long)b << 32;
    int count = 32;
    rem <<= 1;
    while (count--) {
        if ((signed long long)rem - bHigh >= 0) {
            rem -= bHigh;
        }
        rem <<= 1;
    }
    return rem >> 33;
}

### Run with rv32emu emulator

#### Check the answer with no optimization and all optimization
- O0

    00000000000000101000110110011100
    >>> Execution time: 192807 ns
    >>> Instruction count: 2330 (IPS=12084623)
    >>> Jumps: 202 (8.67%) - 100 forwards, 102 backwards
    >>> Branching T=182 (91.92%) F=16 (8.08%)

- O1

    00000000000000101000110110011100
    >>> Execution time: 107683 ns
    >>> Instruction count: 1025 (IPS=9518679)
    >>> Jumps: 108 (10.54%) - 8 forwards, 100 backwards
    >>> Branching T=96 (58.90%) F=67 (41.10%)

- O2

    00000000000000101000110110011100
    >>> Execution time: 116926 ns
    >>> Instruction count: 797 (IPS=6816276)
    >>> Jumps: 157 (19.70%) - 62 forwards, 95 backwards
    >>> Branching T=155 (95.68%) F=7 (4.32%)

- O3

    00000000000000101000110110011100
    >>> Execution time: 86595 ns
    >>> Instruction count: 767 (IPS=8857324)
    >>> Jumps: 181 (23.60%) - 85 forwards, 96 backwards
    >>> Branching T=179 (92.27%) F=15 (7.73%)

- Os

    00000000000000101000110110011100
    >>> Execution time: 93393 ns
    >>> Instruction count: 889 (IPS=9518914)
    >>> Jumps: 231 (25.98%) - 130 forwards, 101 backwards
    >>> Branching T=158 (95.76%) F=7 (4.24%)

**gcd(1840564, 836620) = 167324**

The answer is all equal to `00000000000000101000110110011100`, which is `167324` in binary, and is all correct.