Special instruction challenge チュートリアル

(特殊命令の解析)

■ 乱数を取得してみる

次に乱数命令を実行して，乱数を取得してみましょう．
乱数取得の命令は，random_value() で利用されています．

まず Blackfin での，random_value() の呼び出されかたを見てみます．
Blackfin の逆アセンブル結果を見ると，random_get_value()という関数から 以下のようにして呼び出されています． 

000015b0 <_random_get_value>:
    15b0:       67 01           [--SP] = RETS;
    15b2:       a6 6f           SP += -0xc;             /* (-12) */
    15b4:       00 60           R0 = 0x0 (X);           /*              R0=0x0( 0) */
    15b6:       ff e3 dd ff     CALL 0x1570 <_random_value>;
    15ba:       66 6c           SP += 0xc;              /* ( 12) */
    15bc:       27 01           RETS = [SP++];
    15be:       10 00           RTS;
レジスタR0にゼロを設定してから CALL 命令で random_value() を 呼び出しています．
また呼び出し時には，レジスタR0にゼロを設定して呼び出すようです．

さらに動的解析で，乱数取得の命令の出力を見てみましょう．

乱数取得のための乱数命令は，random_value()という関数内の 0x1578 というアドレスにある「0e c6 00 00」という命令だということが すでにわかっています．

これを，強制的に実行してみます．
まず最初からやりなおすためにGDBを一旦終了し，再接続します． 

(gdb) quit
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote 127.0.0.1:10000
Remote debugging using 127.0.0.1:10000
0x00001400 in start ()
(gdb)
乱数取得用の乱数命令にブレークポイントを設定して実行開始します．
乱数取得は乱数命令の初期化後に呼び出されているので， random_XXX_default()による初期化処理も実行されるはずです． 
(gdb) break *0x1578
Breakpoint 1 at 0x1578
(gdb) continue
Continuing.

Breakpoint 1, 0x00001578 in random_value ()
(gdb) layout asm
いったんブレークポイントを解除します．
これをやっておかないと，ステップ実行直後にまたブレークしたりして， どこまで実行されたかよくわからないことになります． 
(gdb) disable
レジスタR0はゼロに設定されて呼び出されるようですので， (すでになっているはずですが)いちおうゼロ設定します． 
(gdb) print $r0 = 0
$1 = 0
ステップ実行で乱数取得命令を実行し，レジスタの状態を見てみます． 
(gdb) stepi
0x0000157c in random_value ()
(gdb) info registers
r0             0x41c67ea6       1103527590
r1             0x1800   6144
r2             0x24     36
r3             0x0      0
...
乱数はなんらかのレジスタに格納されて返されるのだと思われますが， どのレジスタに格納されているのでしょうか．
レジスタの値を見る限り，レジスタR0が乱数っぽいです．
また random_value() は乱数命令の実行後はRTS命令でそのまま戻る ようになっています．
ということは戻り値を返すレジスタR0に乱数が格納されてくれないと， 関数の戻り値として正常に返すことができません．
ということでおそらくレジスタR0に乱数が格納されているのでしょう．

Blackfinは第１引数も戻り値もレジスタR0で渡すことがわかっています．
この乱数命令はレジスタR0から引数(必ずゼロですが)を受け取り， さらにレジスタR0で乱数を返しています．
なので，関数内で乱数命令をただ呼び出せば，自然と関数の第１引数が引数として与えられ， 乱数が戻り値として返されるようになっているわけです．

つまりrandom_value()は，Ｃ言語では以下のように書くことができるわけです． (server.zip の server/exec-sim/rnd-bfin-elf.c 参照)
非常にシンプルですね． 

unsigned int random_value(unsigned int value)
{
  asm volatile (".short 0xc60e");
  asm volatile (".short 0x0000");
  return value;
}

乱数命令を繰り返し実行し，乱数系列を取得してみましょう．
プログラムカウンタを強制書き換えすることで，実行位置を強制指定して 繰り返し実行します．
※ サーバのリミットが競技時の状態のままの場合，(とくにレジスタへの 代入が多い場合には)うまく実行できないかもしれません． うまくいかない場合には，サーバのリミットを解除して試してください． 実際の競技時は，そうしたリミットをうまく回避しつつ操作することが求められます 

(gdb) print $pc = 0x1578
$2 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$3 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$4 = 0x967eb0e7
(gdb) print $pc = 0x1578
$5 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$6 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$7 = 0x2781e494
(gdb) print $pc = 0x1578
$8 = (void (*)()) 0x1578 <random_value+8>
(gdb) print $r0 = 0
$9 = 0
(gdb) stepi
0x0000157c in random_value ()
(gdb) print/x $r0
$10 = 0xc46b9b3d
(gdb)
このようにして得られた乱数系列は，以下です． 
0x41c67ea6
0x967eb0e7
0x2781e494
0xc46b9b3d
0xf94bdf32
0x95fb7483
0xd9e2b600
0x9cfbae39

■ 乱数命令の仕様を推定する

パラメータやシードを様々に変えて乱数取得してみることで， 乱数命令の仕様を推定してみましょう．

まずパラメータ０をデフォルト値に設定している random_set_param0_default()の逆アセンブル結果を見てみましょう． 

00001580 <_random_set_param0_default>:
    1580:       67 01           [--SP] = RETS;
    1582:       a6 6f           SP += -0xc;             /* (-12) */
    1584:       00 60           R0 = 0x0 (X);           /*              R0=0x0( 0) */
    1586:       ff e3 dd ff     CALL 0x1540 <_random_param0>;
    158a:       66 6c           SP += 0xc;              /* ( 12) */
    158c:       27 01           RETS = [SP++];
    158e:       10 00           RTS;
レジスタR0にゼロを設定し，random_param0()を呼んでいます．
random_param0()では，パラメータ０を設定する特殊命令を呼び出すだけです．
ということはこの特殊命令はレジスタR0でパラメータ０を受け取るが， レジスタR0がゼロになっているときはデフォルト値が使われる， という仕様のようです．

実はパラメータ１とシードも同様になっています．

パラメータ０に１，パラメータ１に１，シードに１を指定して， 乱数取得をしてみましょう．
gdbを一旦終了し，以下のように最初からやりなおしてみます． 

$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ０の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ１の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
(gdb) print $pc = 0x1578
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
(gdb) print $pc = 0x1578
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
...
このようにすると，以下のような乱数系列が得られます． (全然乱数になっていませんが) 
2, 3, 4, 5, ...
パラメータ０を１，パラメータ１を２，シードを１にすると以下のようになります． 
3, 5, 7, 9, ...
等差数列になっていますね．
差分は２です．パラメータ１がそのまま差分になっているようです．

パラメータ０を２，パラメータ１を１，シードを１にすると以下のようになります． 

3, 7, 15, 31, ...

パラメータ１が加算されることを考えると，前の数を２倍してパラメータ１が 加算されている，と考えるとつじつまが合います．
パラメータ０の値が２ですから，パラメータ０をかけ算して，パラメータ１を 加算しているのでしょうか．

その他にも，パラメータやシードをいろいろ変更して試してみてください．
これらを考えると，どうやら以下のような計算式で乱数が得られているようです． 

value = value * param0 + param1;
ここまででわかった特殊命令の仕様を，まとめてみましょう．
(実際の実装内容は微妙に異なるのですが，以下のような動作がおおまかに推定され， これらがわかれば攻略できます)

特殊命令 機械語コードやること(推定)
パラメータ０の設定0e c6 00 80 param0 = r0 ? r0 : default_param0;
パラメータ１の設定0e c6 00 c0 param1 = r0 ? r0 : default_param1;
シードの設定 0e c6 00 40 value = r0 ? r0 : default_seed;
乱数の取得 0e c6 00 00 value = value * param0 + param1; r0 = value;

■ パラメータやシードのデフォルト値の推定

ここまでわかれば，パラメータやシードのデフォルト値も推定できます．
乱数の計算式は，以下のようになっています． 

value = value * param0 + param1;
まずパラメータ０を１，シードを１，パラメータ１はデフォルト値指定として 乱数を取得してみましょう．
(パラメータ０とシードにゼロを設定したいところですが， ゼロを指定するとデフォルト値が使われてしまうため，１を指定します)

パラメータやシードにデフォルト値を使うためには，レジスタR0にゼロを 設定して特殊命令を呼び出します．やってみましょう． 

$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ０の設定)
(gdb) print $r0 = 1       (1を指定)
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ１の設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1       (1を指定)
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x303a
このようにして得られた値は 0x303a です．10進数だと 12346 です．
パラメータ０とシードに１を指定しているので，以下のような計算が行われていると 推測できます．
パラメータ１のデフォルト値は 12345 のようです． 
1 * 1 + 12345 → 12346
次にパラメータ０のデフォルト値を推定してみましょう．
パラメータ０をデフォルト値指定，パラメータ１を１，シードを１として 乱数を取得します． 
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ０の設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ１の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x41c64e6e
得られた値は 0x41c64e6e で，10進数だと1103515246です．
ということはパラメータ０のデフォルト値は1103515245で， 以下のような計算が行われているのでしょう． 
1 * 1103515245 + 1 → 1103515246
最後にシードのデフォルト値の推定です．
パラメータ０とパラメータ１に１を指定して， シードはデフォルト値として乱数取得してみます． 
$ /usr/local/cross-gcc494/bin/bfin-elf-gdb bfin-elf.x
(gdb) target remote localhost:10000

(gdb) print $pc = 0x1548  (パラメータ０の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1558  (パラメータ１の設定)
(gdb) print $r0 = 1
(gdb) stepi

(gdb) print $pc = 0x1568  (シードの設定)
(gdb) print $r0 = 0       (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x1578  (乱数を繰り返し取得)
(gdb) print $r0 = 0
(gdb) stepi
(gdb) print/x $r0
$9 = 0x2
得られた値は２です．
ということはシードのデフォルト値は１で， 以下のような計算が行われているのでしょう． 
1 * 1 + 1 → 2

デフォルト値がわかったのでその部分を追加してまとめると， 以下のようになります．

特殊命令 機械語コードやること(推定)
パラメータ０の設定0e c6 00 80 param0 = r0 ? r0 : 1103515245;
パラメータ１の設定0e c6 00 c0 param1 = r0 ? r0 : 12345;
シードの設定 0e c6 00 40 value = r0 ? r0 : 1;
乱数の取得 0e c6 00 00 value = value * param0 + param1; r0 = value;

■ おしまい