読者です 読者をやめる 読者になる 読者になる

【アセンブリ】100番目までの素数を求めるプログラムを作ってみる【MIPS】

手順

素数を最初から100番目まで求めてプリントするMIPSアセンブリ言語プログラムを作ってみる。

素数を求めるために、2つのルーチンを作る

  • prim(n) - nが素数であれば1を返し、そうでなければ0を返す
  • main() - 整数を順々に繰り返し調べて、素数であるかどうかを判定する。得られた素数を最初から100個まで出力する

C言語のサンプル

Cのサンプルに沿って考えながらアセンブリに人力で翻訳してみる。

int prime(int n)
{
  int i;
  for (i = 2; i < n; i++){
    if (n % i == 0)
      return 0;
  }
  return 1;
}

int main()
{
  int match = 0, n = 2;
  while (match < 100){
    if (prime(n) == 1){
      printf("%d",n);
      printf(" ");
      match++;
    }
    n++;
  }
  printf("\n");
}

実行結果は以下

$ gcc prime.c
$ ./a.out
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

これを目指して人力コンパイル。。。よし。。。笑

翻訳していく - main編

まずはmain()関数(ルーチン)から作った。

前のwhileの練習で作ったソースコードをベースにしながら作ってみる。

        .data
space:  .asciiz " "        
        .text
        .align 2
main:   li    $s0, 100        # set maximum number 
        li    $s1, 0          # number of loop
        li    $s3, 2          # number to check and print (n)
        li    $s7, 1          # for comparing
Loop:   beq   $s0, $s1, Exit  # break if $s1==100
        jal   prime           # $v0 = prime
        bne   $v0, $s7, Else  # go to Else if prime(n)!=1
        li    $v0, 1          # for syscall of print_int
        li    $a0, $s3        # put the prime number
        syscall               # print the prime number
        li    $v0, 4          # for syscall of print_string
        li    $a0, space      # " "
        syscall               # print " "
        addi  $s0, $s0, 1     # increase the number of prime number
Else:   
        addi  $s3, $s3, 1     # n = n + 1 
        j     Loop            # go to Loop
Exit:   j     $ra

こんな感じになった。うん、アセンブリなんか、原始的でいいな笑 ただ、Loopとかif分岐とかは概念としてしか表せないので、そこの書き方とかはかなりプログラマー次第な感じがする。

書くときに意識したことは最後にまとめようと思う。

Cで13行だったmain関数の部分はだいたい27行になった。約2倍。(この比率の名前なんて言うんだっけ笑)

prime関数を作る前に、なんかテストしてみよう。

prime()は常に1を返す、つまり全ての数は素数だという結果が返ってくるって感じに設定して、かつ繰り返す回数を10にしてステップ実行しながら挙動を確かめてみる。

バグをいくつか発見。まず、レジスタ同士の値をコピーする時もliを使ってた。あと、ループを抜ける設定がなんかおかしい。これだと無限ループになる。。。

ということで修正して、さらにテストバージョンに改変したのが以下。

        .data
space:  .asciiz " "        
        .text
        .align 2
main:   li    $s0, 10         # set maximum number (match number)
        li    $s1, 0          # number of loop
        li    $s3, 2          # number to check and print (n)
        li    $s7, 1          # for comparing
Loop:   beq   $s0, $s1, Exit  # break if $s1==100
        # jal   prime           # $v0 = prime
        # bne   $v0, $s7, Else  # go to Else if prime(n)!=1
        li    $v0, 1          # for syscall of print_int
        move  $a0, $s3        # put the prime number
        syscall               # print the prime number
        li    $v0, 4          # for syscall of print_string
        la    $a0, space      # " "
        syscall               # print " "
        addi  $s1, $s1, 1     # increase the number of prime number
Else:   
        addi  $s3, $s3, 1     # n = n + 1 
        j     Loop            # go to Loop
Exit:   j     $ra

出力は以下のようになった。

2 3 4 5 6 7 8 9 11

思惑通り2を先頭に10個出力された。

とりあえずmainの部分はできた!!!よっしゃ!!!!

翻訳していく - prime関数編

ということで次は素数かどうかを判定するprime関数を作っていくことにする。

prime関数はCではこんな感じだった。

int prime(int n)
{
  int i;
  for (i = 2; i < n; i++){
    if (n % i == 0)
      return 0;
  }
  return 1;
}

ひたすらiを1ずつ増やしながら全部で割っていくという肉弾戦(笑)

ここのアルゴリズムはもうちょっとうまいこといく気もするけど、とりあえずこの方法に従って実装を進めてみよう。

とりあえず第一弾はこんな感じ。エラーは出なかったので実行してみる。

            .text
            .align 2
prime:      li    $t0, 2          # number to loop and divide (i)
Loop_prime: beq   $t0, $s3, Exit_prime # break the loop if i == n
            rem   $t1, $s3, $t0   # $t1 = n % i
            beqz  $t1, Exit_prime # goto Exit_prime if $t1 == 0
            j     Loop_prime
            li    $v0, 0          
            j     $ra             # return 0 
Exit_prime: li    $v0, 1         
            j     $ra             # return 1

# ここまで追加

            .data
space:      .asciiz " "        
            .text
            .align 2
main:       li    $s0, 10         # set maximum number (match number)

# 
# こっからmainなので省略
#

2が表示されてから、無限ループ笑

ということでステップ実行してエラーを確かめて該当箇所をなおしていく。

いろいろと間違いはあったけど、主な原因はiをインクリメントしてなかったっぽい。for文を読んで翻訳するときの落とし穴。。。笑

ということで、最終盤のソースコードをあげておきます。

*以下の記事を参考にしながらきちんと呼び出し手続き規約に従って書き直してみた(2014/11/25)

【アセンブリ】再帰で10の階乗を求めるプログラムを通して手続き呼び出し規約を理解する学習ノート【MIPS】 - 凸ろぐ

100までの素数を求めて表示するプログラム(アセンブリ言語)

行数は36行。もともとのC言語が23行なのでprime()部分はそんなに行数かからなかったらしい。

ん!なかなかいいんじゃないかな!!笑

学んだことまとめ

学んだことを箇条書きでメモしておく

  • jal primeとかでラベルに飛べて、そのときの返り値は$v0に格納する。$v0と$v1を「式の評価と関数の結果」に使う
  • レジスタ内同士の値はmoveで代入しないといけない(liとかlaじゃだめ!アドレスなので!)

自分の書き方の思想

  • ifで分岐した部分からElseに飛んだとき「Elseのときだけしたい処理」ってのがないから改行してる
  • labelの後ろは改行しない。改行すると「関数」もろ関数みたいでやだ。アセンブリで関数なんて使えないので。
  • 3つの引数の間には空白いれてみやすく
  • コメントはできるだけ全部入れる
  • もとのC言語での変数名がわかるようにコメントを入れる(これは場面によるかな...笑)

疑問点

  • $sと$tの使い分けについて。ラベルでジャンプした時に保持しておくということだろうか。。。

次回は、講義中に提示されたプログラムを読んでみて自分プログラムとの違いを比較してみる。

優れた部分があれば取り入れる的なこともしたいなぁなんて。。