어셈블리 언어(MIPS)로 정렬

14395 단어 assemblyMIPS
대학 과제용(재수리)
메모리 방출 방법을 몰라서 확보한 공간을

이런 느낌.콘솔에서 이동 가능

데이터 섹션


문자열 정의

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:
    
        # 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
    

    좋은 웹페이지 즐겨찾기