# Tower Of Hanoi
contributed by < `hanqun0723` >
###### tags: `RISC-V`

## Program

.data
argument: .word 3 #the number of disks
str1: .string " \n Number of disk "
str2: .string " \n Move disk from "
str3: .string " to "

.text
main:   li a0, 4          #print the number of disks
        la a1, str1
        ecall
        li a0, 1
        lw a1, argument
        ecall
	lw a0, argument    #load arguments
	li a1, 1    #a1 = A
	li a2, 2    #a2 = B
	li a3, 3    #a3 = C
	jal ra,hanoi       #Exit program
	li a0, 10
	ecall 
hanoi:  li t4, 1
        bne a0, t4, Else #if(disk == 1)
        mv t0, a0        #else(disk > 1)
        mv t1, a1   
        mv t2, a2       
        mv t3, a3
        li a0, 4   		
        la a1, str2    
        ecall
        li a0, 1       
        mv a1, t1
        ecall
        li a0, 4        
        la a1, str3   
        ecall
        li a0, 1       
        mv a1, t3
        ecall
        jalr ra, ra, 0	
Else:   addi sp, sp, -20  #hanoi(n-1,A,C,B)
        sw ra, 16(sp)
        sw a3, 12(sp)
        sw a2, 8(sp)
        sw a1, 4(sp)
        sw a0, 0(sp)
        add t0, zero, a3  
        mv a3, a2
        mv a2, t0
        addi a0, a0, -1
        jal ra, hanoi  #ra = pc+4
        lw ra, 16(sp)
        lw a3, 12(sp)
        lw a2, 8(sp)
        lw a1, 4(sp)
        lw a0, 0(sp)
        mv t0, a0    #move a disk from A to C
        mv t1, a1    #save a0,a1 values in t0,t1
        li a0, 4   		
        la a1, str2   
        ecall
        li a0, 1       
        mv a1, t1
        ecall
        li a0, 4  
        la a1, str3   
        ecall
        li a0, 1       
        mv a1, a3
        ecall
        mv a0, t0   #hanoi(n-1,B,A,C)
        mv a1, t1
        add t0, zero, a2  
        mv a2, a1
        mv a1, t0
        addi a0, a0, -1
        jal ra, hanoi
        lw ra, 16(sp)
        addi sp, sp, 20
        jalr ra, ra, 0	

## Instruction Memory
根據 assembled code 顯示總共有 79 條 instruction, 所以 instruction memory 從 0x00000000 依序存放至 0x00000000 + (hex(79*4-1=315)=0x13b) = 0x0000013b



第一條執行的指令為

addi x10 x0 4

根據I-type 的instruction format

immediate = 000000000100
rs = 00000
funct = 000
rd = 01010
op code = 0010011
將上述 32 bits 的二進位值轉用十六進位表示
00000000010000000000010100010011 = 0x00400513

* 從PC位址 0x00000000 可以看到指令有被正確存放

## Data Memory
Data 的部分會先儲存於Data memory中, 再利用 lw , sw來讀取與儲存資料


## Stack
在遞迴的過程中需先將原本的 arguments 先儲存至 stack 存放, 由於此函數有 4 個 arguments 和他的 return address, 所以我們需要將 stack 挪出 5 個 32bits 的空間來存放 .


圖為stack pointer的起始位置

sp : 0x7ffffff0
sp-20 (5個32bits空間) : 0x7fffffdc
將需要儲存的值依序存放至stack
ra (return address) -> 0x7fffffec
a3 (C tower)-> 0x7fffffe8
a2 (B tower)-> 0x7fffffe4
a1 (A tower)-> 0x7fffffe0
a0 (number of disks)-> 0x7fffffdc


結果如下圖:
根據第一次call function的argunents做驗證, a0 = 3 ,a1 = 1 , a2 = 2 , a3 = 3 , ra, 顯示有將值正確存放至 stack

* function結束後須將 stack pointer 值還原

    addi sp, sp ,20

## 5-stage pipeline
這裡一樣以程式碼第一行為例子來觀察pipeline如何運作及資料流

addi x10 x0 4

* IF stage
此階段會到 instruction memory 去抓指令

* ID stage
對 instruction 做 decode, 並根據 decode 出來的結果來看要做什麼樣子的運算及到相對應的 register 讀取資料

* EXE stage
將前一階段從 register 讀出來的值與常數部分做相加

* MEM stage
這個階段因為沒有使用到lw, sw指令, 所以不會對data memory做存取

* WB stage
最後在將計算過後的數值write back到 rd 暫存器

## Results
結果會顯示 Input 的 disk 數量及每個步驟移動的過程

## Reference
1. https://riscv.org/specifications/