spim and mips

『クラウドファンディングで資金調達!』(あさ出版)なんて本を読んだ。 クラウドファンディングって近頃よく聞く言葉。時代に遅れないように、どんなものか 手に取ってみた次第。

アイデアはあるけど、資金が無いって人向けの、資金調達手段。資金調達と言うと、真っ先に 浮かぶのは銀行からの借り入れ。あそこは手堅いから、貸した金が回収出来るか一番気にする。 世に渋沢栄一先生が100人ぐらい居ればいいんだけど、図体がでかい割りに肝っ玉は小さい所。

次なる候補は、投資会社。金を持ってる人が投資して大きなリターンを狙う。投資してくれる人を エンジェルなんて言うらしいけど、いつの間にかデビルになって、襲い掛かって来るとも 限らない。

どれも敷居が高い。で、アメリカで生まれたやつが、クラウドファンディング。インターネット 上に、こんなアイデアがあって、実現すればこんないい事が待ってますから、賛同者は 出資してくださいと、公募で資金を集める方法。

あらかじめ、集めたい金額と募集期間を明示して、調達に望む。目標金額に達しなければ、 そのアイデアは認められなかった事で、一銭も手に出来ない。

お金を集める訳だから、出資してくれた人に、リターンが必要。投資してもらった金額に応じて リワードと言うお礼が必要。そのリターンの仕方によって、大きく3種類に分類出来るとか。

寄付型、投資型、借り入れ型。素人が最初にやるなら、寄付型が良いとの事。他のものは、 きっちりと事業計画書を作成する必要があるし、会計監査も求められるので難易度は高いそう。

インターネットにアイデアを公開するって言っても、どうやるんだ? それ専門のサイトが 有るそうだ。国内で有名なのは、

Makuake

GREEN FUNDING

READYFOR?

海外で、大金を集めたいなら

KICKSTARTER

INDIEGOGO

ちょっとしたアイデアでも、みんなが面白がったり、琴線に触れれば、大金も夢ではない。 例として、キャンプなんかで使う、クーラーボックス。冷やすだけじゃつまんない。携帯に 充電出来たりしたら、より便利になるんじゃ? そんなアイデアを持って募集した所、何と 15億円も集まってしまったそうな。面白いね、何か思いついたら募集かけてみよう。

自信がある人は、Y Combinatorみたいな所で、勝負 してみるのも手かもね。Lispで財を成した親分が率いる所だから、ロボットなんか良いぞ。 鉄腕アトム作ってみせますとか、不気味な谷を乗り越えて癒しのロボット作りますとか、どうだろう。

spim

前回xspimが動かないってんで、ウブを新しくしたけど、基本はspimでしょって事で、ソースを 観賞してみる事にした。一式ソースを落としてきて展開してみると、QtSpimとかPCSpimとかXspimが有って、 これらに混じってspimが入ってた。後はmipsの石って事でCPUですかね。

spimに下りて行ったらMakefileが有ったのでmakeしたよ。そしたら、bison必要、flex必要って喚かれてしまった。 そして、生意気にもg++も必要との事。Changelogの底に

Mon May 14 13:35:27 1990  James Larus  (larus at primost)

        * scanner.l
        Remove typo in string.  Also, change call on strtol to sscanf
        since the first function doesn't appear to be standard BSD. [From:
        Brian R Murphy <hindmost@ATHENA.MIT.EDU>]

が記録されてて、生誕25周年になりました。そんな昔にg++なんて有ったっけ? ああ、きっと コードが寄贈されてQtspimを入れる時に、必要になったんだな。

走らせてみると、/usr/share/spim/exceptions.sが必要だってさ。ウブのデフォでは、/usr/lib/spimに 入っているんで、ポリシーの違いですかね。

名前から例外を扱っている事は想像出来るけど、一見してみたぞ。カーネル領域に置かれる コードなのね。そして、最後に、ユーザーアプリを呼び出すコードが置かれていた。

# Standard startup code.  Invoke the routine "main" with arguments:
#       main(argc, argv, envp)
#
        .text
        .globl __start
__start:
        lw $a0 0($sp)           # argc
        addiu $a1 $sp 4         # argv
        addiu $a2 $a1 4         # envp
        sll $v0 $a0 2
        addu $a2 $a2 $v0
        jal main
        nop

        li $v0 10
        syscall                 # syscall 10 (exit)

        .globl __eoth
__eoth:

ハロワが当たり前のように付いていたので、儀式を行ってみる。

        .data
msg:   .asciiz "Hello MIPS\n"
        .extern foobar 4

        .text
        .globl main
main:   li $v0, 4       # syscall 4 (print_str)
        la $a0, msg     # argument: string
        syscall         # print the string
        lw $t1, foobar

        jr $ra          # retrun to caller

前回書いたMakefileにちょっと追加したいたので、面倒な無いな。

make -k spim
spim -file hello-mips.s
Loaded: /usr/share/spim/exceptions.s
Hello MIPS

以上、試験終わり。続いて、ソース探検の為の地図作り。emacsの中から、gdbを立ち上げると、 spimからのコンソール画面が出てきて、面倒なので、立ち上げたspimにgdbをアタッチするのが吉。

以下、spimがアイドル状態の時の図。

(gdb) bt
#0  0xb77b6be0 in __kernel_vsyscall ()
#1  0xb755e733 in __read_nocancel () at ../sysdeps/unix/syscall-template.S:81
#2  0xb74f1b17 in _IO_new_file_underflow (fp=0xb763c600 <_IO_2_1_stdin_>) at fileops.c:580
#3  0xb74f2aa7 in __GI__IO_default_uflow (fp=0xb763c600 <_IO_2_1_stdin_>) at genops.c:435
#4  0xb74f28bc in __GI___uflow (fp=0xb763c600 <_IO_2_1_stdin_>) at genops.c:389
#5  0xb74ed8e1 in _IO_getc (fp=0xb763c600 <_IO_2_1_stdin_>) at getc.c:39
#6  0x080557d1 in yy_get_next_buffer () at lex.yy.c:1346
#7  0x08056a89 in yylex () at lex.yy.c:1188
#8  0x08049276 in read_token () at spim.c:1208
#9  0x08049491 in read_assembly_command () at spim.c:746
#10 parse_spim_command (redo=false) at spim.c:433
#11 top_level () at spim.c:378
#12 0x0804ab28 in main (argc=1, argv=0xbfbd29c4) at spim.c:319

こちらは、syscall命令を実行しようとした時。

(gdb) bt
#0  do_syscall () at ../CPU/syscall.c:111
#1  0x0804d6e0 in run_spim (initial_PC=4194304, steps_to_run=2147483647, display=false) at ../CPU/run.c:1104
#2  0x0804b7bc in run_program (pc=4194304, steps=2147483647, display=false, cont_bkpt=false, continuable=0xbfd640c5) at ../CPU/spim-utils.c:359
#3  0x08049799 in parse_spim_command (redo=<optimized out>) at spim.c:477
#4  top_level () at spim.c:378
#5  0x0804ab28 in main (argc=1, argv=0xbfd64254) at spim.c:319

道しるべが出来たわい。それにしても、Windowsとコードが混在してると、桁数はビローンと 増えるは、#ifdef _WIN32 なんてのが、やたら出てくるわ、うっとうしいな。

つらつらとコードを見てる。run.cに

/* Multiply two 32-bit numbers, V1 and V2, to produce a 64 bit result in
   the HI/LO registers.  The algorithm is high-school math:

         A B
       x C D
       ------
       AD || BD
 AC || CB || 0

 where A and B are the high and low short words of V1, C and D are the short
 words of V2, AD is the product of A and D, and X || Y is (X << 16) + Y.
 Since the algorithm is programmed in C, we need to be careful not to
 overflow. */

こういう掛け算って、あちらでは高校で習うんですかね? run_spimって関数は、例の RISCの元となった、ヘネパタ本の再現なのかな。 ヘネパタと言えば、落としてきたソース一式中にあったドキュメントの中に、ヘネパタ本の 付録部分が収録されてた。なかなか見ごたえあるぞ。

最近では、東大名物のCPU実験とか、信州大学の講座 シンプルなCPUを作ってみよう なんてのも有るし、ruby用とかGauche用とか、俺々コンピュータが溢れていますよ。

ここら辺で、MIPSな石の資料と、SPIMな資料を挙げておく。

はじめて読む MIPS(リローデッド)

演習で使用する主な MIPS 命令

SPIM - MIPS 2000/3000 シミュレータ アセンブラの偽命令表が有って、参考になる

例外発生

例外処理のソースが無くて、最初走らなかったという難癖がついたので、この例外ルーチンが ちゃんと呼ばれるか調べてみた。spimにアセンブラのソースをロードして、BPをmainに 置いてからステップ実行させる

(spim) s
[0x00400034]    0x3c017fff  lui $1, 32767         ; 13: li $t0 0x7fffffff
(spim)
[0x00400038]    0x3428ffff  ori $8, $1, -1
(spim)
[0x0040003c]    0x01084820  add $9, $8, $8         ; 14: add $t1, $t0, $t0
Exception occurred at PC=0x0040003c
  Arithmetic overflow
  Exception 12  [Arithmetic overflow]  occurred and ignored

MaxInt同士の足し算で、算術オーバーフローが発生した。この時の各レジスタの 値を確認。えと、print_all_regs hexな。

 PC      = 80000180   EPC     = 0040003c   Cause   = 00000030   BadVAddr= 00000000
 Status  = 3000ff13   HI      = 00000000   LO      = 00000000
                                 General Registers
R0  (r0) = 00000000  R8  (t0) = 7fffffff  R16 (s0) = 00000000  R24 (t8) = 00000000
R1  (at) = 7fff0000  R9  (t1) = 00000000  R17 (s1) = 00000000  R25 (t9) = 00000000
R2  (v0) = 00000004  R10 (t2) = 00000000  R18 (s2) = 00000000  R26 (k0) = 3000ff13
R3  (v1) = 00000000  R11 (t3) = 00000000  R19 (s3) = 00000000  R27 (k1) = 7fff0000
R4  (a0) = 10010000  R12 (t4) = 00000000  R20 (s4) = 00000000  R28 (gp) = 10008000
R5  (a1) = 7ffff184  R13 (t5) = 00000000  R21 (s5) = 00000000  R29 (sp) = 7ffff180
R6  (a2) = 7ffff188  R14 (t6) = 00000000  R22 (s6) = 00000000  R30 (s8) = 00000000
R7  (a3) = 00000000  R15 (t7) = 00000000  R23 (s7) = 00000000  R31 (ra) = 00400018
 :

よく使いそうなコマンド名が長いな。改造にチャレンジしてみるかな。spim.c 内を探検。 そして手がかりを得た。

sakae@uB:~/src/spimsimulator-code-658/spim$ diff -u org.spim.c spim.c
--- org.spim.c  2015-02-19 00:13:55.000000000 +0900
+++ spim.c      2015-06-16 15:09:51.304296292 +0900
@@ -624,11 +624,11 @@
       write_output (message_out,
                    "print ADDR -- Print contents of memory at ADDRESS\n");
       write_output (message_out,
-                   "print_symbols -- Print all global symbols\n");
+                   "ps -- Print all global symbols\n");
       write_output (message_out,
-                   "print_all_regs -- Print all MIPS registers\n");
+                   "pa -- Print all MIPS registers\n");
       write_output (message_out,
-                   "print_all_regs hex -- Print all MIPS registers in hex\n");
+                   "pa hex -- Print all MIPS registers in hex\n");
       write_output (message_out,
                    "reinitialize -- Clear the memory and registers\n");
       write_output (message_out,
@@ -645,7 +645,7 @@

       write_output (message_out,
                    "\nMost commands can be abbreviated to their unique prefix\n");
-      write_output (message_out, "e.g., ex(it), re(ad), l(oad), ru(n), s(tep), p(rint)\n\n");
+      write_output (message_out, "e.g., ex(it), re(ad), lo(ad), ru(n), s(tep), p(rint)\n\n");
       prev_cmd = HELP_CMD;
       return (0);

@@ -755,9 +755,9 @@
     return (EXIT_CMD);
   else if (str_prefix ((char *) yylval.p, "print", 1))
     return (PRINT_CMD);
-  else if (str_prefix ((char *) yylval.p, "print_symbols", 7))
+  else if (str_prefix ((char *) yylval.p, "ps", 2))
     return (PRINT_SYM_CMD);
-  else if (str_prefix ((char *) yylval.p, "print_all_regs", 7))
+  else if (str_prefix ((char *) yylval.p, "pa", 2))
     return (PRINT_ALL_REGS_CMD);
   else if (str_prefix ((char *) yylval.p, "run", 2))
     return (RUN_CMD);

他にも改造するなら、 MIPS32エミュレータspim例外ハンドラ拡張 とか SPIMの改造 が参考になりそう。

それはそうと、例外要因の中に、ZEROで割り算したってのが無いけど、どうなってるんで しょうか? ヘネシーとパターソン教授殿。

例外が上がった時のメッセージで最初の2行は、syscall.c内で出している。最後の行は、 exception.s内の実行結果だな。

Divide by zero

ZEROで割ったらエラーだぞ、ごりゃ! ってのが無いかCPUの作りの中を探してみた。そしたら parser.yに見つかった。

        |       DIV_POPS        DEST    SRC1    IMM32
                {
                  if (is_zero_imm ((imm_expr *)$4.p))
                    yyerror ("Divide by zero");
                  else
                    {
                      /* Use $at */
                      i_type_inst_free (Y_ORI_OP, 1, 0, (imm_expr *)$4.p);
                      div_inst ($1.i, $2.i, $3.i, 1, 1);
                    }
                }

DIV_POPSってのは、引数(って表現で良いのかな)の形式でにより3種類になるけど、その うちの一つ。DIV_POPSってのは、DIV族の集合と言うが正規表現で言うグループだ。なお、 Y_INST_OPってのが石が持ってる命令を表し、Y_INST_POPってなってるのは、偽命令だ。 こういう区別をしてくれているとコードを追う時に良い道しるべになる。

DIV_POPS:       Y_DIV_OP
        |       Y_DIVU_OP
        |       Y_REM_POP
        |       Y_REMU_POP
        ;

どんな風に使われているか見てみる。

sakae@uB:~/src/spimsimulator-code-658/spim$ spim -file div.s
Loaded: /usr/share/spim/exceptions.s
spim: (parser) Divide by zero on line 6 of file div.s
          div $t0, $t2, 0

                         ^

即値で悪(ワル)数がZEROだと、コンパイル中に確認出来るから、エラーに落とせるんだな。 そんじゃ、どういう経路で呼ばれるか見てみる。

(gdb) b div_inst
Breakpoint 1 at 0x8052665: file ../CPU/parser.y, line 2771.
(gdb) c
Continuing.

Breakpoint 1, div_inst (op=382, rd=8, rs=9, rt=1, const_divisor=1) at ../CPU/parser.y:2771
2771    {
(gdb) bt
#0  div_inst (op=382, rd=8, rs=9, rt=1, const_divisor=1) at ../CPU/parser.y:2771
#1  0x0805384f in yyparse () at ../CPU/parser.y:1108
#2  0x0804b13a in read_assembly_file (name=0x81e3c80 "div.s") at ../CPU/spim-utils.c:205
#3  0x080496b8 in parse_spim_command (redo=false) at spim.c:446
#4  top_level () at spim.c:378
#5  0x0804ab28 in main (argc=1, argv=0xbf83b204) at spim.c:319

それじゃ、エラーの無いようにしてやってみる。

(spim) load "div.s"
(spim) br main
(spim) run
Breakpoint encountered at 0x00400024
(spim) s 5
[0x00400024]    0x3401007b  ori $1, $0, 123     ; 4: div $t0, $t1, 123
[0x00400028]    0x0121001a  div $9, $1
[0x0040002c]    0x00004012  mflo $8
[0x00400030]    0x03e00008  jr $31               ; 7: jr $ra  # retrun to caller
[0x00400018]    0x00000000  nop                  ; 189: nop

div $t0, $t1, 123 ってのが、石の3命令に展開されてる。即値をアセンブラ用Reg1に入れて、 Reg9($t1)と演算。結果は特殊レジスタのHi,Loに得られるので、商が入ってるLoから$8($t0)に 移動させてる。

即値をロードするのも、$0レジスタ(常にZEROが読み出される)と、即値をORして、結果を$1に 入れてる。アセンブラ賢い事をやってるな。その賢さがparser.yに凝縮されてるんだな。

で、どのぐらいのコマンドが定義されてるか、op.h内を検索してみた。

[sakae@fedora CPU]$ grep _INST op.h | wc
    316    1879   18833
[sakae@fedora CPU]$ grep _POP op.h | wc
     49     196    1850
[sakae@fedora CPU]$ grep _DIR op.h | wc
     42     166    1641

RISCな石は命令数が少ないなんて嘘じゃん。いっぱいあるぞ。違った、R2000とかの古い石と、 mips32とかの新しい石の定義が混じってた。そして、コプロセッサー用の命令も 入っていたぞ。

_POPとつくのは、アセンブラの偽命令と言うか、超ミニ関数と言うか、 マクロって言っても良いかな。_DIRは、アセンブラへの指示命令です。いっぱいあるな。

これらが、先に挙げたパーサーで処理されるんだけど、その文法がbisonとflexで処理される。 昔Rubyのやつを見て、びっくりして撤退したな。もう一度spimで再挑戦するか。

資料が有ったはずと、書棚を調べてみると、昔懐かしいユニマガの記事を抜粋した本があった。 プログラミング・テクニックってムック本。久しぶりに紐解いてみよう。

再度例外

例外処理中に例外が発生する事を、ダブルフォルトとか言うんだっけな。あれは、68K用語 だったかな。もう少し例外を。

そうそう、悪数がZEROの場合、例外を挙げないのは、RISCを名乗った石だからです、と、ヘネシー、 パターソン教授は考えたんだな。

ユーザーが用意した悪数はどんな数かユーザーが知ってるはず。それをハードでチェックして あげるなんてゲートの無駄以外の何物でもない。必要なら、一命令で悪数かチェック出来る んだから、ハードでは用意しないよ、きっぱり。

じゃ、他に有る例外は、教授のお眼鏡にかなったやつだな。ちょいと再現。

(spim) s 4
[0x00400024]    0x3c041001  lui $4, 4097 [msg]         ; 8: la $a0, msg     # argument: string
[0x00400028]    0x8c890000  lw $9, 0($4)               ; 9: lw $t1, 0($a0)
[0x0040002c]    0x8c890002  lw $9, 2($4)               ; 10: lw $t1, 2($a0)
Exception occurred at PC=0x0040002c
  Unaligned address in inst/data fetch: 0x10010002
[0x80000180]    0x0001d821  addu $27, $0, $1           ; 90: move $k1 $at # Save $at

ワード(32Bit)の読み出しは、命令/データにかかわらず、4の倍数アドレスじゃなきゃ駄目という ハードの制約が有る。プログラムのミスや暴走を早めに検知してOSに知らせるために設けた 機能では無いので、これに頼っちゃ駄目よ。

[0x00400024]    0x00000000  nop                        ; 8: nop
[0x00400028]    0x3c018000  lui $1, -32768             ; 9: la $a0, 0x80000180
[0x0040002c]    0x34240180  ori $4, $1, 384
[0x00400030]    0x8c890000  lw $9, 0($4)               ; 10: lw $t1, 0($a0)
Exception occurred at PC=0x00400030
  Bad address in data/stack read: 0x80000180

0x80000180 なんて言うカーネル領域が出てきたので、一般ユーザーが、そこに アクセス出来るか確かめる。そして、拒絶された。

後は、起きそうな例外として、4の倍数じゃ無い所に書き込もうとしたりするエラーかな。 いろいろやってくうちに、わけわかめなやつにも出くわすだろうね。

[sakae@fedora spim]$ ./spim -file ex.s
Loaded: /usr/share/spim/exceptions.s
Exception occurred at PC=0x00400030
  Exception 9  [Breakpoint]  occurred and ignored
(spim) s 2
[0x00400024]    0x01080034  teq $8, $8              ; 4: teq $t0, $t0
Exception occurred at PC=0x00400024
  Trap
[0x80000180]    0x0001d821  addu $27, $0, $1        ; 90: move $k1 $at # Save $at

breakとかtrapは虫の検出に使えるな。特にtrap系は色々な条件でtrapを発生出来るんで、 C語で言うアサートの変わりになる。

NAME
       assert - abort the program if assertion is false

SYNOPSIS
       #include <assert.h>

       void assert(scalar expression);

DESCRIPTION
       If  the  macro  NDEBUG  was  defined  at the moment <assert.h> was last
       included, the macro assert() generates no code, and hence does  nothing
       at all.  Otherwise, the macro assert() prints an error message to stan‐
       dard error and terminates the program by calling abort(3) if expression
       is false (i.e., compares equal to zero).

       The  purpose  of  this  macro is to help programmers find bugs in their
       programs.  The  message  "assertion  failed  in  file  foo.c,  function
       do_bar(), line 1287" is of no help at all to a user.

ああ、そうだ、bisonの使い方って事で、 bisonとflexの使い方 を見て、実験してみたんだった。とんでもなく長いコードをbisonが用意してくれていて、 これはもう中身はブラックボックスって事で宜しいかな。それよりbison語を理解する方が重要。