IT/소스코드

[MIPS Assembly] Quicksort

zzun 2003. 7. 10. 06:32
컴퓨터구조 / 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