zzun.net zzun's blog since 2001

#################################################################
#                                                                #
#        2001-12204 이준희                                        #
#        Problem 3. MAXMIN                                        #
#        bare mode version                                        #
#        there are some no-operation instructions                #
#                        following branch/jump instructions        #
#                        for delayed branch/jump                        #
#        data segement is fixed at 0x10010000                        #
#        tested at junebug by spim bare mode                        #
#                ./spim -bare -file 200112204_P3.s                #
#                                                                #
#        [pseudocode]                                                #
#        MAXMIN(A[], n)                                                #
#                if n < 2                                        #
#                        v0 = A[0]                                #
#                        v1 = A[0]                                #
#                        return;                                        #
#                {v0, v1} = MAXMIN(A[]+1, n-1);                        #
#                if A[0] < v0                                        #
#                        v0 = A[0]                                #
#                if A[0] > v1                                        #
#                        v1 = A[0]                                #
#                return;                                                #
#                                                                #
#################################################################

               .data        0x10010000
msg1:                .asciiz        "MAX : "                        # 4097
msg2:                .asciiz ", MIN : "                        # 4097 + 7
newline:        .asciiz        "\n"                                # 4097 + 16
#input_start
Alength:        .word        13
Aarray:                .word        130, 202, 30, 4440, 530, 532, 33, 204, 8, 524, 8933, 92, 10
#input_end

               .text
MAXMIN:
               ori        $t0, $zero, 2                        # t0 = 2
               slt        $t0, $a1, $t0
               bne        $t0, $zero, sp_case                # if n < 2, branch to sp_case
               ori        $t0, $t0, 0                        # nop

               subu        $sp, $sp, 8
               sw        $ra, 8($sp)                        # save return address
               sw        $a0, 4($sp)                        # save A[]
               addi        $a0, $a0, 4                        # A[] = A[] + 1
               addi        $a1, $a1, -1                        # n = n - 1
               jal        MAXMIN
               ori        $t0, $t0, 0                        # nop

               lw        $a0, 4($sp)                        # restore A[]
               lw        $ra, 8($sp)                        # restore return address
               addu        $sp, $sp, 8

               lw        $t0, 0($a0)                        # load A[0]
               slt        $t1, $t0, $v0
               beq        $t1, $zero, next                # if not A[0] < v0, branch to next
               ori        $t0, $t0, 0                        # nop
               ori        $v0, $t0, 0                        # if A[0] < v0, v0 = A[0] (minimum)

next:                slt        $t1, $v1, $t0
               beq        $t1, $zero, end                        # if not A[0] > v1, branch to end
               ori        $t0, $t0, 0                        # nop
               ori        $v1, $t0, 0                        # if A[0] > v1, v1 = A[0] (maximum)
               bgez        $zero, end                        # branch to end
               ori        $t0, $t0, 0                        # nop

sp_case:        lw        $v0, 0($a0)
               ori        $v1, $v0, 0                        # v0 = v1 = A[0]

end:                jr        $ra


main:
               lui        $a0, 4097
               lw        $a1, 20($a0)                        # load length n
               ori        $a0, $a0, 24                        # address of A[]
               jal        MAXMIN
               ori        $t0, $t0, 0                        # nop
               
               subu        $sp, $sp, 8
               sw        $v1, 8($sp)                        # save maximum value
               sw        $v0, 4($sp)                        # save minimum value

               ori        $v0, $zero, 4
               lui        $a0, 4097                        # address of msg1
               syscall                                        # print string

               lw        $a0, 8($sp)                        # restore maximum
               ori        $v0, $zero, 1
               syscall                                        # print int

               lui        $a0, 4097
               ori        $a0, $a0, 7                        # address of msg2
               ori        $v0, $zero, 4
               syscall                                        # print string

               lw        $a0, 4($sp)                        # restore minimum
               addu        $sp, $sp, 8
               ori        $v0, $zero, 1
               syscall                                        # print int

               lui        $a0, 4097
               ori        $a0, $a0, 16                        # address of newline
               ori        $v0, $zero, 4
               syscall                                        # print string

컴퓨터 구조 / 2003년 1학기 / 김지홍 교수님

#################################################################
#                                                                #
#        2001-12204 이준희                                        #
#        Problem 2. WriteBackwards                                #
#        bare mode version                                        #
#        there are some no-operation instructions                #
#                        following branch/jump instructions        #
#                        for delayed branch/jump                        #
#        data segement is fixed at 0x10010000                        #
#        tested at junebug by spim bare mode                        #
#                ./spim -bare -file 200112204_P2.s                #
#                                                                #
#        [pseudocode]                                                #
#        WriteBackwards(A[])                                        #
#                if A[0] == 0                                        #
#                        return;                                        #
#                WriteBackwards(A[] + 1);                        #
#                print A[0];                                        #
#                return;                                                #
#                                                                #
#################################################################

               .data        0x10010000
msg1:                .asciiz        "Input string is: "                # 4097
msg2:                .asciiz        "The reverse is: "                # 4097 + 18
newline:        .asciiz        "\n"                                # 4097 + 35
#input_start
input_string:        .asciiz        ".sllih hgih no wolb sdniw hgiH"
#input_end

               .text
WriteBackwards:
               lb        $t0, 0($a0)                        # load most left character
               beq        $t0, $zero, WB_end                # if it is null("\0"), branch to WB_end
               ori        $t0, $t0, 0                        # nop
               
               subu        $sp, $sp, 8
               sw        $ra, 4($sp)                        # save return address
               sw        $a0, 8($sp)                        # save A[]
               addi        $a0, $a0, 1                        # A[] = A[] + 1
               jal        WriteBackwards
               ori        $t0, $t0, 0                        # nop
               
               lw        $ra, 4($sp)                        # restore return address
               lw        $a0, 8($sp)                        # restore A[]
               addu        $sp, $sp, 8

               sb        $zero, 1($a0)                        # byte at A[]+1 = 0 to notify the end of string
               ori        $v0, $zero, 4                        # v0 = 4
               syscall                                        # print string (actually print one character)

WB_end:                jr        $ra                                # return

main:
               lui        $a0, 4097                        # address of msg1
               ori        $v0, $zero, 4
               syscall                                        # print string

               ori        $a0, $a0, 37                        # address of input_string
               syscall

               addi        $a0, $a0, -2                        # address of newline
               syscall

               addi        $a0, $a0, -17                        # address of msg2
               syscall

               addi        $a0, $a0, 19                        # address of newline
               jal        WriteBackwards
               ori        $t0, $t0, 0                        # nop

               lui        $a0, 4097
               ori        $a0, $a0, 35                        #address of newline
               syscall

컴퓨터구조 / 2003년 1학기 / 김지홍 교수님

#################################################################
#                                                                #
#        2001-12204 이준희                                        #
#        Problem 1. Quicksort                                        #
#        bare mode version                                        #
#        there are some no-operation instructions                #
#                        following branch/jump instructions        #
#                        for delayed branch/jump                        #
#        data segement is fixed at 0x10010000                        #
#        tested at junebug by spim bare mode                        #
#                ./spim -bare -file 200112204_P1.s                #
#                                                                #
#        pseudo code is omitted                                        #
#                                                                #
#################################################################
               
               .data        0x10010000
blank:                .asciiz        " "                                # 4097
newline:        .asciiz        "\n"                                # 4097 + 2

#input_start
Alength:        .word        13
Aarray:                .word        130, 202, 30, 4440, 530, 532, 33, 204, 8, 524, 8933, 92, 10
#input_end

               .text
Quicksort:        
               slt        $t0, $a1, $a2                        # a1(=p):starting position        a2(=r):ending position
               beq        $t0, $zero, Quicksort_end        # if a1>=a2 branch to Quicksort_end
               ori        $t0, $t0, 0                        # nop

               subu        $sp, $sp, 16
               sw        $ra, 16($sp)                        # save return address
               sw        $a0, 12($sp)                        # a0 is the base address of an array (=A[])
               sw        $a1, 8($sp)
               sw        $a2, 4($sp)                        # save a0, a1, a2 to call sub-procedure
               jal        Partition                        # call Partition(A[], p, r) : same argument as current procedure

               subu        $sp, $sp, 4
               sw        $v0, 4($sp)                        # save return value of Partition (=q)
               lw        $a0, 16($sp)
               lw        $a1, 12($sp)                        # load A[], p
               ori        $a2, $v0, 0                        # move q to a2
               jal        Quicksort                        # call Quicksort(A[], p, q)

               lw        $a0, 16($sp)                        # load A[]
               lw        $t0, 4($sp)                        # load q
               addi        $a1, $t0, 1                        # a1 = q + 1
               lw        $a2, 8($sp)                        # load r
               jal        Quicksort                        # Quicksort(A[], q+1, r)
               ori        $t0, $t0, 0                        # nop

               addu        $sp, $sp, 20                        # pop A[], p, r, q, ra
               lw        $ra, 0($sp)                        # restore reaturn address

Quicksort_end:        jr        $ra                                # return


Partition:
               add        $t0, $a1, $a1
               add        $t0, $t0, $t0                        # t0 = a1 * 4
               add        $t0, $t0, $a0                        # t0 = A[] + t0
               lw        $t0, 0($t0)                        # t0 = A[p]        : x

               addi        $t1, $a1, -1                        # i = p-1
               addi        $t2, $a2, 1                        # j = r+1

               add        $t3, $t1, $t1
               add        $t3, $t3, $t3
               add        $t3, $t3, $a0                        # t3 = address of A[i] to minimize the loop
               add        $t4, $t2, $t2
               add        $t4, $t4, $t4
               add        $t4, $t4, $a0                        # t4 = address of A[j]

Loop1:                addi        $t1, $t1, 1                        # i = i+1
               addi        $t3, $t3, 4                        # t3 = t3 + 4 : reset the address of A[i]
               lw        $t5, 0($t3)
               slt        $t6, $t5, $t0
               bne        $t6, $zero, Loop1                # if A[i] < x, branch to Loop2
               ori        $t0, $t0, 0                        # nop

Loop2:                addi        $t2, $t2, -1                        # j = j-1
               addi        $t4, $t4, -4                        # t4 = t4 - 4 : reset the address of A[j]
               lw        $t5, 0($t4)
               slt        $t6, $t0, $t5
               bne        $t6, $zero, Loop2                # if A[j] > x, branch to Loop1

               slt        $t5, $t1, $t2
               beq        $t5, $zero, Partition_end        # if i >= j, branch to Partition_end

               lw        $t5, 0($t3)
               lw        $t6, 0($t4)
               sw        $t6, 0($t3)
               sw        $t5, 0($t4)                        # swap A[i] and A[j]
               beq        $zero, $zero, Loop1

Partition_end:        addu        $v0, $zero, $t2                        # v0 = j
               jr        $ra                                # return


PrintArray:
               beq        $a1, $zero, PrintArray_end        # if length == 0, branch to PrintArray_end
               addi        $s0, $a0, 0                        # move A[] to s0
               addi        $s1, $a1, 0                        # move length to s1
               addi        $t0, $zero, 0                        # t0 = 0

Loop3:                add        $t1, $s0, $t0                        # t1 = A[] + t0
               lw        $a0, 0($t1)                        # load A[] + t0
               ori        $v0, $zero, 1                        # v0 = 1
               syscall                                        # print int
               ori        $v0, $zero, 4                        # v0 = 4
               lui        $a0, 4097                        # address of blank
               syscall                                        # print string " "
               addi        $s1, $s1, -1                        # s1 = s1 -1
               addi        $t0, $t0, 4                        # t0 = t0 + 4 (next element)
               bne        $s1, $zero, Loop3                # if s1 != 0, branch to Loop3

PrintArray_end:        ori        $v0, $zero, 4                        # v0 = 4
               lui        $a0, 4097
               ori        $a0, $a0, 2                        # address of newline
               syscall                                        # print string "\n"
               jr        $ra                                # return


main:
               lui        $t0, 4097
               ori        $a0, $t0, 8                        # address of A[]
               lw        $a1, 4($t0)                        # load length
               jal        PrintArray

               lui        $t0, 4097
               ori        $a0, $t0, 8                        # address of A[]
               lw        $t0, 4($t0)                        # load length
               addi        $a2, $t0, -1                        # length - 1
               ori        $a1, $zero, 0                        # a1 = 0
               jal        Quicksort
               ori        $t0, $t0, 0                        # nop

               lui        $t0, 4097
               ori        $a0, $t0, 8                        # address of A[]
               lw        $a1, 4($t0)                        # address of length
               jal        PrintArray