MIPS programming assignment #3

Qtspim에서 동작하는 Assembly 프로그램 작성하기

 

1. syscall을 사용하여 사용자로부터 자연수를 입력받고, 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 출력하는 프로그램을 작성하시오.
(EX. 5를 입력받을 시 다음과 같은 모양이 콘솔창에 출력되어야 함)

// C++로 구현
void star(int input) {
    for (int n = 1; n < input+1; n++) {
        for (int i = 0; i < n; i++) cout << "*";
    }
}

 

.data
    n: .word 1
    i: .word 0
    star: .asciiz "*"
    nline: .asciiz "\n"
.text

main:
    lw $s1, n
    lw $s2, i

    # 자연수 입력 받기
    li $v0, 5
    syscall

    # loop 반복횟수 맞추기 위해 입력받은 수에 1 더해주기
    addi $v0, $v0, 1

    move $s0, $v0

# 행별로 갯수 맞춰 별 출력
loop:
    beq $s2, $s1, print

    # * 출력 n회 반복
    la $a0, star
    li $v0, 4
    syscall

    addi $s2, $s2, 1    # i = i + 1

    j loop

# 행 단위 출력
print:
    # newline
    la $a0, nline
    li $v0, 4
    syscall

    li $s2, 0            # i 초기화
    addi $s1, $s1, 1     # n = n + 1
    bne $s1, $s0, loop   # $s1 != $s0 이면 루프 다시 시작

    # $s1 == $s0 되면 종료
    li $v0, 10
    syscall

 

 

2. syscall을 사용하여 사용자로부터 자연수를 입력받고, stack과 recursion을 통해 피보나치 수를 계산하는 프로그램을 작성하시오. (아래 코드 참조) 반드시 SP와 RA를 사용하라.
(EX. 입력: 11 / 출력: 89 )

// 참조용 코드
int fibo(int n) {
    if (n > 1) return fibo(n-1) + fibo(n-2);
    else return n;
}

 

.data
    in_msg: .asciiz "입력: "
    out_msg: .asciiz "출력: "
    nline: .asciiz "\n"
.text

main:
    la $a0, in_msg
    li $v0, 4
    syscall

    # 자연수 입력 받기
    li $v0, 5
    syscall

    # fibo(n) 호출
    move $a0, $v0
    jal fibo
    move $t0, $v1       # fibo 연산 결과값 t0에 저장

    la $a0, out_msg
    li $v0, 4
    syscall

    # 연산결과 출력
    move $a0, $t0
    li $v0, 1
    syscall

    # newline
    la $a0, nline
    li $v0, 4
    syscall

    # 종료
    li $v0, 10
    syscall

fibo:
    # n <= 1
    beqz $a0, zero
    beq $a0, 1, one

    # fibo(n-1) 호출하기
    addi $sp, $sp, -4   # 스택 한칸 할당
    sw $ra, 0($sp)      # 할당된 메모리에 return address 저장

    sub $a0, $a0, 1     # n - 1
    jal fibo            # fibo(n-1)
    add $a0, $a0, 1     # n 원래대로

    lw $ra, 0($sp)      # 저장된 return address 불러오기
    add $sp, $sp, 4     # ra 저장해놨던 공간 시스템에 반환

    addi $sp, $sp, -4
    sw $v1, 0($sp)      # return할 값을 스택에 push

    # fibo(n-2) 호출하기
    addi $sp, $sp, -4
    sw $ra,0($sp)

    sub $a0, $a0, 2     # n - 2
    jal fibo            # fibo(n-2)
    add $a0, $a0, 2

    lw $ra, 0($sp)
    add $sp, $sp, 4


    lw $s0, 0($sp)      # 저장해놨던 return할 값을 pop
    add $sp, $sp, 4     # return값 저장해놨던 공간 시스템에 반환

    add $v1, $v1, $s0   # fibo(n-2) + fibo(n-1)
    jr $ra

zero:
    li $v1, 0
    jr $ra

one:
    li $v1, 1
    jr $ra

 

 

3. 크기 5를 가진 배열 arr = [7, 5, 6, 1, 4] 을 bubble sort하는 프로그램을 작성하시오. 단, 프로그램 작성 시 두 개의 정수를 받아 그 값을 서로 교체하는 swap() 함수를 반드시 포함하시오.

.data
    arr: .word 7, 5, 6, 1, 4
    space: .asciiz " "
.text

#s1 = arr
#s2 = length of arr
#t0 = main_loop loop counter
#t1 = bubble_sort loop counter
#t2 = copy arr address

main:
    la $s1, arr     # arr의 start address
    li $s2, 5       # arr length

    move $t0, $s2

main_loop:
    beqz $t0, print     # arr length만큼 반복

    li $t1, 0           # bubble sort 카운터 초기화
    move $t2, $s1       # bubble sort 후 arr의 start address를 $t2에 복사

    jal bubble_sort

    sub $t0, $t0, 1     # 남은 main_loop 반복횟수 - 1
    j main_loop

bubble_sort:
    beq $t1, $t0, jumpra    # 

    lw $t3, 0($t2)          # load t2[0]
    lw $t4, 4($t2)          # load t2[1]

    slt $t5, $t4, $t3       # t5 <= (t4 < t3) ? 1 : 0

    bnez $t5, swap          # if (t5 != 0) jump to swap

    addi $t2, $t2, 4        # t2의 첫 메모리블록 반환
    addi $t1, $t1, 1        # 다음 칸으로 이동

    j bubble_sort

jumpra:
    jr $ra

swap:
    sw $t3, 4($t2)          # t3에 t2[1] 값 덮어씌우기
    sw $t4, 0($t2)          # t4에 t2[0] 값 덮어씌우기

    addi $t2, $t2, 4
    addi $t1, $t1, 1

    j bubble_sort

print:
    # s1[0]와 space를 출력해준 뒤
    # s1의 첫 메모리블록 1개 반환, s2--를
    # s2 == 0 될때까지 반복해준다.
    
    beqz $s2, exit
    lw $t0, 0($s1)

    move $a0, $t0
    li $v0, 1
    syscall

    la $a0, space
    li $v0, 4
    syscall

    addi $s1, $s1, 4
    sub $s2, $s2, 1

    j print

exit:
    li $v0, 10
    syscall