Special instruction challenge チュートリアル

(他アーキテクチャの解析)

■ 他のアーキテクチャの解析

ここまでで Blackfin に実装された特殊命令の仕様はわかりました.

他のアーキテクチャに関しても,同様に調べて特殊命令の仕様を知ることができます.

乱数アルゴリズムにはM系列とxorshiftが使われていますが, 特殊命令を呼び出すための関数を見れば,パラメータのビット数などから 仕様を推定できるはずです.
たとえばxorshiftでは3つのパラメータを5ビットや6ビットでマスクしてレジスタに 設定しているので,xorshift32/xorshift64であることが判断できます.

Blackfinではパラメータやシードにゼロを指定するとデフォルト値が使われる という仕様でしたが,他アーキテクチャもそのようになっています.
(これは,各アーキテクチャの実行ファイルの逆アセンブル結果から, XXX_default()のような関数を調べることでわかります)

xorshiftでは,シフト量に1を指定したり,シードを1やオール1(0xFFFFFFFF)に 指定して乱数取得をすることで,シフト順(LRL/RLR/LLR/RRL)やシフト量の デフォルト値が推定できます.
また逆計算が可能であるため,シードのデフォルト値も推定できます.

M系列は,シードに1,シフト量に1を指定して乱数取得することで, LSBが左シフトされて 2, 4, 8,... となっていく値が取得できるので, 左に1ビットずつシフトしていくアルゴリズムだということが推定できます.

ただし中にはGDBの通信量がシビアなアーキテクチャ(とくにV850)があるので, 試すときには size-connect.txt による通信量リミットを解除しておく といいでしょう.
(でないと,GDBでのリモートデバッグ中にぶちぶち通信が切れます)

以下,試すときのポイントです.

アーキテクチャ特殊命令のアドレス使用するレジスタ備考
パラメータ設定シード設定乱数取得引数渡し結果の取得
MSP430 0x15ee0x15f20x15f6 R12R12 random_value()にある乱数取得命令は,「(繰り返し回数)−1」の値をR13(random_value()の第2引数)で与える
MN10300 0x158a0x158f0x1594 D0D0 xorshift32
V850 0x17f00x17f80x1800 R6R10 xorshift32
MIPS64 0x10022c0x10023c0x10024c R4(a0)R2(v0) xorshift64

■ MSP430の解析

例えばMSP430で試してみましょう.

MSP430での注意点として,乱数取得時に乱数命令の実行回数の指定ができます.
これはMSP430がプレフィックス命令を持っていて,後続の命令を繰り返し実行 できるのですが,それを利用しています.

実行ファイルを以下で逆アセンブルしてみます.

$ /usr/local/cross-gcc494/bin/msp430-elf-objdump -d msp430-elf.x
逆アセンブル結果は,以下です.
000015ee <random_param>:
    15ee:       cc 12           .word   0x12cc; ????
    15f0:       10 01           reta                    ;

000015f2 <random_seed>:
    15f2:       cc 11           .word   0x11cc; ????
    15f4:       10 01           reta                    ;

000015f6 <random_value>:
    15f6:       8d 19 cc 10     .word   0x198d, 0x10cc; ????
    15fa:       10 01           reta                    ;
random_value()にある特殊命令だけ,4バイトになっています.
これは「cc 10」という2バイト命令に「8d 19」というプレフィックスが ついています(リトルエンディアンなので,プレフィックスとしては 0x198d という値です).
プレフィックスの「d」の位置がレジスタ番号を指していて, ここでは「0xd」なので10進数で13ですから,R13を指しています.
MSP430はこのプレフィックスにより,後続の命令を「R13 + 1」の回数だけ 繰り返し実行します.

MSP430は関数の第1引数をR12,第2引数をR13で受け取ります. つまりrandom_value()は第2引数で,乱数取得命令の繰り返し回数を指定できます.

random_value()の呼び出し元は,以下のようになっています.

0000161c <random_get_value>:
    161c:       0d 4c           mov     r12,    r13     ;
    161e:       3d 53           add     #-1,    r13     ;r3 As==11
    1620:       0c 43           clr     r12             ;
    1622:       b0 13 f6 15     calla   #5622           ;0x015f6
    1626:       10 01           reta                    ;
R12をR13にコピーしてからデクリメントしています.
またR12はゼロクリアしています.
つまり,random_get_value()は引数に繰り返し回数を指定できるようになって いるわけです.
(繰り返し回数が R13 + 1 であるため,デクリメントした値を渡しています)

さてここまでわかったところで,パラメータ1,シード1,繰り返し回数1で 乱数を取得してみます.
R13には,「(繰り返し回数)−1」の値を設定することに注意してください.

$ /usr/local/cross-gcc494/bin/msp430-elf-gdb msp430-elf.x
GNU gdb (GDB) 7.12.1
...
(gdb) target remote 127.0.0.1:10001
Remote debugging using 127.0.0.1:10001
0x00001400 in _start ()
(gdb) print $pc = 0x15ee
(gdb) print $r12 = 1
(gdb) stepi

(gdb) print $pc = 0x15f2
(gdb) print $r12 = 1
(gdb) stepi

(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 0
(gdb) stepi
(gdb) print/x $r12
$8 = 0x2
(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 0
(gdb) stepi
(gdb) print/x $r12
$12 = 0x4
(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 0
(gdb) stepi
(gdb) print/x $r12
$16 = 0x8
乱数が2,4,8,...と1ビットずつシフトしていくことが確認できます. パラメータを様々に変更して試すことで,繰り返し回数の指定や, アルゴリズムがM系列であることが推測できます.

MSP430はM系列なので,その乱数パラメータはおそらくM系列のマスク値だと 思われます.
デフォルトのマスク値を調べてみましょう.

$ /usr/local/cross-gcc494/bin/msp430-elf-gdb msp430-elf.x
(gdb) target remote 127.0.0.1:10001

(gdb) print $pc = 0x15ee
(gdb) print $r12 = 0 (デフォルト値を指定)
(gdb) stepi

(gdb) print $pc = 0x15f2
(gdb) print $r12 = 1
(gdb) stepi

(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 7 (8ビットシフトぶん繰り返す)
(gdb) stepi
(gdb) print/x $r12
$8 = 0x100
(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 6 (7ビットシフトぶん繰り返す)
(gdb) stepi
(gdb) print/x $r12
$12 = 0x8000
(gdb) print $pc = 0x15f6
(gdb) print $r12 = 0
(gdb) print $r13 = 0 (1ビットシフトぶん繰り返す)
(gdb) stepi
(gdb) print/x $r12
$16 = 0x2241
M系列のマスク値のデフォルトは,0x2240 のようです.
(0x2241の最下位ビットを落として考えています)

■ V850の解析

他にも,V850で解析してみましょう.

V850は実はxorshift(32ビット)なのですが, xorshiftには4つのパラメータがあります.

xorshiftについて調べるとわかるのですが,シフト量を表す a,b,c という3つの 値と,シフト順(LRL/RLR/LLR/RRL)です.

V850の逆アセンブル結果を見て,パラメータの設定方法を探ってみましょう.

$ /usr/local/cross-gcc494/bin/v850-elf-objdump -d v850-elf.x
パラメータ設定の特殊命令を呼び出しているだけのxorshift_param()という関数が あります.
000017ee <_xorshift_param>:
    17ee:       06 50           mov     r6, r10
    17f0:       e0 37 74 53     .long   0x537437e0
    17f4:       7f 00           jmp     [lp]
しかしxorshift_param()は,以下のようにして xorshift_set_param()から呼び出されています.
00001806 <_xorshift_set_param>:
    1806:       bf 57 46 fd     jarl    154c <__save_r31>, r10
    180a:       c8 46 1f 00     andi    31, r8, r8
    180e:       c7 42           shl     7, r8
    1810:       c7 3e 1f 00     andi    31, r7, r7
    1814:       c2 3a           shl     2, r7
    1816:       08 39           or      r8, r7
    1818:       c6 36 03 00     andi    3, r6, r6
    181c:       07 31           or      r7, r6
    181e:       c9 4e 1f 00     andi    31, r9, r9
    1822:       cc 4a           shl     12, r9
    1824:       09 31           or      r9, r6
    1826:       bf ff c8 ff     jarl    17ee <_xorshift_param>, lp
    182a:       bf 07 3a fe     jr      1664 <__return_r31>
V850はR6以降で関数の引数を渡しますが,xorshift_set_param()では R6〜R9までをなにやら加工して,R6に設定して xorshift_param() を 呼び出しているようです.

andiは即値を使ってのAND命令,shlは左シフト,orは単なるOR命令でしょうか.
そんな感じでR6〜R9の加工内容を追うと,以下のようなことをやっているようです.

00001806 <_xorshift_set_param>:                                    ; xorshift_set_param(int R6, int R7, int R8, int R9)
    1806:       bf 57 46 fd     jarl    154c <__save_r31>, r10
    180a:       c8 46 1f 00     andi    31, r8, r8                 ; R8 = R8 & 31;
    180e:       c7 42           shl     7, r8                      ; R8 <<= 7;
    1810:       c7 3e 1f 00     andi    31, r7, r7                 ; R7 = R7 & 31;
    1814:       c2 3a           shl     2, r7                      ; R7 <<= 2;
    1816:       08 39           or      r8, r7                     ; R7 |= R8;
    1818:       c6 36 03 00     andi    3, r6, r6                  ; R6 = R6 & 3;
    181c:       07 31           or      r7, r6                     ; R6 |= R7;
    181e:       c9 4e 1f 00     andi    31, r9, r9                 ; R9 = R9 & 31;
    1822:       cc 4a           shl     12, r9                     ; R9 <<= 12;
    1824:       09 31           or      r9, r6                     ; R6 |= R9;
    1826:       bf ff c8 ff     jarl    17ee <_xorshift_param>, lp ; R10 = xorshift_param(R6);
    182a:       bf 07 3a fe     jr      1664 <__return_r31>        ; return R10;
C言語っぽく書くと,要するに以下のようなことをやっています.
xorshift_set_param(int R6, int R7, int R8, int R9)
{
  int R10;
  R8 = R8 & 31;
  R8 <<= 7;
  R7 = R7 & 31;
  R7 <<= 2;
  R7 |= R8;
  R6 = R6 & 3;
  R6 |= R7;
  R9 = R9 & 31;
  R9 <<= 12;
  R6 |= R9;
  R10 = xorshift_param(R6);
  return R10;
}
複数の式をまとめて簡略化すると,以下のようになります.
xorshift_set_param(int R6, int R7, int R8, int R9)
{
  R6 = (R6 & 3) | ((R7 & 31) << 2) | ((R8 & 31) << 7) | ((R9 & 31) << 12);
  return xorshift_param(R6);
}
R6を2ビットで,R7〜R9を5ビットでマスクしているのが気になります.

xorshiftのパラメータはシフト順(LRL/RLR/LLR/RRLの4種類), シフト量(a,b,cの3つ)ですが,32ビットのxorshiftではシフト量は31までです.

ということはR6がシフト順,R7,R8,R9がそれぞれa,b,cに相当するのでは ないでしょうか.

そのように考えて xorshift_set_param() を書き直すと,以下のようになります.

xorshift_set_param(int seq, int a, int b, int c)
{
  int reg;
  reg = (seq & 3) | ((a & 31) << 2) | ((b & 31) << 7) | ((c & 31) << 12);
  return xorshift_param(reg);
}
ということは xorshift_param() にある特殊命令は,パラメータを上のように 加工してレジスタ経由で渡してやればいいことになります.
もしくは xorshift_set_param() を通すことで加工してもいいでしょう.

ということで,シフト順はゼロ,a,b,cには1,1,1,シードは1を指定して, 乱数取得をしてみましょう.
※ V850ではGDBの通信量のリミット解除をしておかないと,以下はほぼ確実にリミットを越えて実行できません.size-connect.txt のリミット解除をしておいてください.

$ /usr/local/cross-gcc494/bin/v850-elf-gdb v850-elf.x
(gdb) target remote 127.0.0.1:10003

(gdb) print $pc = 0x180a  (xorshift_set_param()内の,パラメータ加工の先頭)
(gdb) print $r6 = 0  (シフト順に0を指定)
(gdb) print $r7 = 1  (a = 1 を指定)
(gdb) print $r8 = 1  (b = 1 を指定)
(gdb) print $r9 = 1  (c = 1 を指定)

(gdb) stepi  (パラメータ加工を行う)
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi
(gdb) stepi

(gdb) print $pc = 0x17f0  (加工したパラメータの設定)
(gdb) stepi

(gdb) print $pc = 0x17f8  (シードの設定)
(gdb) print $r6 = 1       (シードに1を指定)
(gdb) stepi

(gdb) print $pc = 0x1800  (乱数の取得)
(gdb) print $r6 = 0
(gdb) stepi
(gdb) print/x $r10
$11 = 0x6
6という結果が得られました.

xorshift(32bit)のアルゴリズムは以下です.

uint32_t v;
int a, b, c;
(LRL) v = v ^ (v<<a); v = v ^ (v>>b); v = v ^ (v<<c);
(RLR) v = v ^ (v>>a); v = v ^ (v<<b); v = v ^ (v>>c);
(LLR) v = v ^ (v<<a); v = v ^ (v<<c); v = v ^ (v>>b);
(RRL) v = v ^ (v>>a); v = v ^ (v>>c); v = v ^ (v<<b);
a=1,b=1,c=1,シード1でこれらを計算して結果が6になるのは,LRLの場合です.

つまりシフト順として0を指定した場合には,LRLが採用されるようです.

このようにしてパラメータやシードを様々に変化させて調べることで, デフォルトのパラメータを調べることが可能です.
具体的には,パラメータをデフォルト,シードを1,0x80000000,0xFFFFFFFFとして 調べることで,推定可能です.
またシードのデフォルト値は,xorshiftの逆計算をすることで推定可能です.

■ おしまい