大学の課題用 (再 履 修)
メモリ解放の仕方が分からなかったので確保したスペース放置してる
こんな感じで 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