アセンブリ言語(MIPS)でソート

大学の課題用 (再　履　修)
メモリ解放の仕方が分からなかったので確保したスペース放置してる

こんな感じで SPIM コンソール上で動いてくれます

.data セクション

文字列の定義

bracket_start: .asciiz "["
bracket_end: .asciiz "]: "
input_message_0: .asciiz "Number of integers: "
input_message_1: .asciiz "Input"
output_message_0: .asciiz "Sorted results: "
output_message_1: .asciiz "Output"
error_message: .asciiz "Number of integers must be positive"
eol: .asciiz "\n"

固定的に使うレジスタの定義

• $s0
  → 配列
• $s1
  → 配列のサイズ

.text セクション

main ルーチン

「入力」→「ソート」→「出力」を繰り返す

バブルソート用の実装

main:

    jal read
    jal sort
    jal print
    j main

クイックソート用の実装

main:

    jal read

    # sort(0, N - 1);
    move $a0, $zero
    move $a1, $s1
    addi $a1, $a1, -1
    jal sort

    jal print
    j main

read ルーチン

ユーザー入力を受け付けて配列 $s0 に格納する

read:

    # "Number of integers:"　と表示する
    li $v0, 4
    la $a0, input_message_0
    syscall

    # 生成する配列のサイズを$v0に受け取る
    li $v0, 5
    syscall

    # 正の数であればread_prepareにジャンプする
    bgt $v0, $zero, read_prepare

    # "Number of integers must be positive\n" と表示する
    li $v0, 4
    la $a0, error_message
    syscall
    la $a0, eol
    syscall

    # リトライさせる
    j read

    read_prepare:

    # 生成する配列のサイズを$s1に保存する
    move $s1, $v0

    # 配列を生成して先頭アドレスを$v0に受け取る
    sll $a0, $v0, 2
    li $v0, 9
    syscall

    # 生成した配列の先頭アドレスを$s0に保存する
    move $s0, $v0

    # 配列のオフセット用レジスタとして$t0を初期化する
    move $t0, $zero

    read_loop:

    # "Input[{$t0}]:" と表示する
    li $v0, 4
    la $a0, input_message_1
    syscall
    la $a0, bracket_start
    syscall
    li $v0, 1
    move $a0, $t0
    syscall
    li $v0, 4
    la $a0, bracket_end
    syscall

    # 設定する配列要素の値を$v0に受け取る
    li $v0, 5
    syscall

    # 実際に保存する
    sll $t1, $t0, 2
    add $t1, $t1, $s0
    sw $v0, 0($t1)

    # オフセットをインクリメントする
    addi $t0, $t0, 1

    # 作成した配列にまだ空きがあればread_loopにジャンプする
    bne $t0, $s1, read_loop

    # "\n" と表示する
    li $v0, 4
    la $a0, eol
    syscall

    # 復帰する
    jr $ra

print ルーチン

配列 $s0 の値を出力する

print:

    # 配列のオフセット用レジスタとして$t0を初期化する
    move $t0, $zero

    # "Sorting results:" と表示する
    li $v0, 4
    la $a0, output_message_0
    syscall
    la $a0, eol
    syscall

    print_loop:

    # "Output[{$t0}]:" と表示する
    li $v0, 4
    la $a0, output_message_1
    syscall
    la $a0, bracket_start
    syscall
    li $v0, 1
    move $a0, $t0
    syscall
    li $v0, 4
    la $a0, bracket_end
    syscall

    # 格納されている値を取り出して表示する
    sll $t1, $t0, 2
    add $t1, $t1, $s0
    li $v0, 1
    lw $a0, 0($t1)
    syscall

    # "\n" と表示する
    li $v0, 4
    la $a0, eol
    syscall

    # オフセットをインクリメントさせる
    addi $t0, $t0, 1

    # 配列要素の巡回がまだ済んでいなければprint_loopにジャンプする
    bne $t0, $s1, print_loop

    # "\n" と表示する
    li $v0, 4
    la $a0, eol
    syscall

    # 復帰する
    jr $ra

sort ルーチン

バブルソート用の実装

sort:

    # i = 0;
    move $s2, $zero;

    # while (i < N) {
    loop_i_start:
    bge $s2, $s1, loop_i_end

    # j = N - 1;
    add $s3, $s1, -1

    # while (j > i) {
    loop_j_start:
    ble $s3, $s2, loop_j_end

    # if (x[j] < x[j - 1]) swap(&x[j], &x[j - 1]);
    add $t1, $s3, -1
    sll $t0, $s3, 2
    sll $t1, $t1, 2
    add $t0, $t0, $s0
    add $t1, $t1, $s0
    lw $t2, 0($t0)
    lw $t3, 0($t1)
    bge $t2, $t3, skip_swap
    sw $t2, 0($t1)
    sw $t3, 0($t0)
    skip_swap:

    # --j;
    addi $s3, $s3, -1

    # }
    j loop_j_start
    loop_j_end:

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

    # }
    j loop_i_start
    loop_i_end:

    # return;
    jr $ra

クイックソート用の実装

sort:

    # スタックへの退避
    addi $sp, $sp, -20
    sw $ra, 16($sp)
    sw $s5, 12($sp)
    sw $s4, 8($sp)
    sw $s3, 4($sp)
    sw $s2, 0($sp)
    move $s2, $a0
    move $s3, $a1

    # i = left;
    move $s4, $s2

    # j = right;
    move $s5, $s3

    # pivot = x[(left + right) / 2];
    add $t0, $s2, $s3
    li $t1, 2 
    div $t0, $t1
    mflo $t0
    sll $t0, $t0, 2
    add $t0, $t0, $s0
    lw $t0, 0($t0)

    # while (1) {
    loop_start:

    # while (x[i] < pivot) ++i;
    loop_i_start:
    move $t1, $s4
    sll $t1, $t1, 2
    add $t1, $t1, $s0
    lw $t1, 0($t1)
    bge $t1, $t0, loop_i_end
    addi $s4, $s4, 1

    # }
    j loop_i_start
    loop_i_end:

    # while (pivot < x[j]) --j;
    loop_j_start:
    move $t1, $s5
    sll $t1, $t1, 2
    add $t1, $t1, $s0
    lw $t1, 0($t1)
    bge $t0, $t1, loop_j_end
    addi $s5, $s5, -1

    # }
    j loop_j_start
    loop_j_end:

    # if (i >= j) break;
    bge $s4, $s5, loop_end

    # swap(&x[i], &x[j]);
    move $t1, $s4
    move $t2, $s5
    sll $t1, $t1, 2
    sll $t2, $t2, 2
    add $t1, $t1, $s0
    add $t2, $t2, $s0
    lw $t3, 0($t1)
    lw $t4, 0($t2)
    sw $t3, 0($t2)
    sw $t4, 0($t1)

    # ++i
    addi $s4, $s4, 1

    # --j
    addi $s5, $s5, -1

    # }
    j loop_start;
    loop_end:

    # if (left < i - 1) sort(left, i - 1);
    move $t0, $s4
    addi $t0, $t0, -1
    bge $s2, $t0, skip_left_sort
    move $a0, $s2
    move $a1, $t0
    jal sort
    skip_left_sort:

    # if (j + 1 < right) sort(j + 1, right);
    move $t0, $s5
    addi $t0, $t0, 1
    bge $t0, $s3, skip_right_sort
    move $a0, $t0
    move $a1, $s3
    jal sort
    skip_right_sort:

    # スタックからの復元
    lw $s2, 0($sp)
    lw $s3, 4($sp)
    lw $s4, 8($sp)
    lw $s5, 12($sp)
    lw $ra, 16($sp)
    addi $sp, $sp, 20

    # return;
    jr $ra