(他アーキテクチャの解析)
ここまでで 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 | 0x15ee | 0x15f2 | 0x15f6 | R12 | R12 | random_value()にある乱数取得命令は,「(繰り返し回数)−1」の値をR13(random_value()の第2引数)で与える |
MN10300 | 0x158a | 0x158f | 0x1594 | D0 | D0 | xorshift32 |
V850 | 0x17f0 | 0x17f8 | 0x1800 | R6 | R10 | xorshift32 |
MIPS64 | 0x10022c | 0x10023c | 0x10024c | R4(a0) | R2(v0) | xorshift64 |
例えば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バイトになっています.
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にコピーしてからデクリメントしています.
さてここまでわかったところで,パラメータ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 = 0x2241M系列のマスク値のデフォルトは,0x2240 のようです.
他にも,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() にある特殊命令は,パラメータを上のように 加工してレジスタ経由で渡してやればいいことになります.
ということで,シフト順はゼロ,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 = 0x66という結果が得られました.
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の逆計算をすることで推定可能です.