S/390の機械語を総当たり調査

[S/390](https://ja.wikipedia.org/wiki/IBM_S/390)は1960年代に開発された[System/360](https://ja.wikipedia.org/wiki/System/360)からバイナリ互換性を保っているアーキテクチャです。S/390の命令を調べるため総当たりで逆アセンブルしてみました。

この記事には姉妹編があります。

* [UNIX/32VによるVAX事始め](http://qiita.com/7shi/items/85c4a43a07152c4322d5) 2015.9.14
* [VAXの機械語を総当たり調査](http://qiita.com/7shi/items/7b24ed23fcbea08c3615) 2015.9.17

# クロスコンパイラ

S/390の機械語を扱うため、S/390をターゲットにしたクロスコンパイラが必要です。以下の手順を参考に`s390-linux-gcc`をビルドしてください。

* [最低限のクロスコンパイラの作り方](http://qiita.com/7shi/items/2d44e040bae930d11088) 2015.01.30

## テスト

先の記事と同じテストをしてみます。

```add.c
int add(int a, int b) {
    return a + b;
}
```

コンパイルします。

```text
$ s390-linux-gcc -nostdlib -g -O add.c
/usr/lib/gcc/../../s390-linux/bin/ld: 警告: エントリシンボル _start が見つかりません。デフォルトとして 0000000000400094 を使用します
```

※ 警告は無視します。

出力されたバイナリ（a.out）を逆アセンブルして、どんな機械語が出力されているかを確認します。

```text
$ s390-linux-objdump -S a.out

a.out:     ファイル形式 elf32-s390


セクション .text の逆アセンブル:

00400094 <add>:
int add(int a, int b) {
    return a + b;
}
  400094:       1a 23                   ar      %r2,%r3
  400096:       07 fe                   br      %r14
```

引数が`%r2`と`%r3`で渡されて、戻り値は`%r2`で返される様子が読み取れます。`%r14`はリンクレジスタのようです。

機械語を見ると、以下の対応関係が見て取れます。

```text
1a 23    ar %r2,%r3
1a    -> ar
   2  ->    %r2
    3 ->        %r3
```
```text
07 fe    br %r14
07 f  -> br
    e ->    %r14
```

どうやら構成要素は[ニブル](https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%96%E3%83%AB)（16進数1桁）単位で、オペコードは2ニブル（1バイト）または3ニブルのようです。

# オペコード

オペコードを総当たりすれば、すべての命令フォーマットが分かるはずです。

## 00

手始めに1バイトのゼロで試します。

```text
$ echo ".byte 0" | s390-linux-as
$ s390-linux-objdump -d a.out
（略）
00000000 <.text>:
   0:   00 07 07 07             .long   0x00070707
```

`.long`は未定義であることを表します。

アラインメントが4バイトらしく、`07`でパディングされています。他のアーキテクチャではデータが足りない時にはエラーになるので、このようにパディングされるのは珍しい挙動です。

## nopr

補完された`07`の正体を確認します。

```text
$ echo ".byte 7" | s390-linux-as
$ s390-linux-objdump -d a.out
（略）
00000000 <.text>:
   0:   07 07                   nopr    %r7
   2:   07 07                   nopr    %r7
```

`nopr`はいわゆるNOPのようです。オペランドは無視されるため何でもよく、`07`で表現できる`%r7`を使っているようです。

## 総当たり(1)

最初の1バイトを総当たりします。命令長が不明なため、後ろは`07`で埋めます。アラインメントを予想して16バイトで揃えます。

アドレスとパディングの`nopr`を取り除いてファイルに保存します。

```text
$ for i in {0..255}; do printf ".byte 0x%02x,7,7,7, 7,7,7,7, 7,7,7,7, 7,7,7,7\n" $i; done > allop.s
$ s390-linux-as -o allop.o allop.s
$ s390-linux-objdump -d allop.o | cut -sf2- | grep -v nopr | tee allop.d
00 07 07 07             .long   0x00070707
01 07                   sckpf
02 07 07 07             .long   0x02070707
（略）
fd 07 07 07 07 07       dp      1799(1,%r0),1799(8,%r0)
fe 07 07 07             .long   0xfe070707
ff 07 07 07             .long   0xff070707
```

## 命令長

未定義の`.long`を取り除いて命令を眺めます。

```text
$ grep -v long allop.d
01 07                   sckpf
05 07                   balr    %r0,%r7
（略）
3e 07                   aur     %f0,%f7
3f 07                   sur     %f0,%f7
40 07 07 07             sth     %r0,1799(%r7,%r0)
41 07 07 07             la      %r0,1799(%r7,%r0)
（略）
be 07 07 07             stcm    %r0,7,1799
bf 07 07 07             icm     %r0,7,1799
c0 07 07 07 07 07       xilf    %r0,117901063
c4 07 07 07 07 07       sthrl   %r0,0xe0e1a4e
（略）
fc 07 07 07 07 07       mp      1799(1,%r0),1799(8,%r0)
fd 07 07 07 07 07       dp      1799(1,%r0),1799(8,%r0)
```

命令長がきれいに分布しています。後の調査結果を見ても例外はないようです。

先頭1ニブル|命令長
-----------|-----:
`0`-`3`    |2
`4`-`b`    |4
`c`-`f`    |6

可変長アーキテクチャではあまりに長い命令のダンプが途中で改行されることがありますが、allop.dをチェックした限りでははみ出していません。

## 総当たり(2)

命令長が分かったので後続のバイトも総当たりします。ただし完全な総当たりでは時間が掛かり過ぎるため、以下の方針で間引きます。

* 2バイト命令は完全な総当たり (64*256=16,384通り)
* それ以外は最初の2バイトと最後の1バイトを総当たり (192*256*256=12,582,912通り)

記事を書く前の予備調査でオペランドと機械語の対応関係を調べた際、最終バイトにオペランドが来ないパターンを見付けたため、総当たりの対象としています。

```text
$ for i in {0..63}; do for j in {0..255}; do printf ".byte 0x%02x,0x%02x,7,7\n" $i $j; done; done > allop2.s
$ for i in {0..255}; do for j in {0..255}; do printf ".byte X,0x%02x,Y,0x%02xZ\n" $i $j; done; done > allop-template.s
$ for i in {64..191}; do hex=`printf "%02x" $i`; sed "s/X/0x$hex/" allop-template.s | sed "s/Y/0x12/" | sed "s/Z//"; done > allop4.s
$ for i in {192..255}; do hex=`printf "%02x" $i`; sed "s/X/0x$hex/" allop-template.s | sed "s/Y/0x12,0x34,0x56/" | sed "s/Z/,7,7/"; done > allop6.s
$ for i in 2 4 6; do s390-linux-as -o allop$i.o allop$i.s; s390-linux-objdump -d allop$i.o | grep -v long | cut -f2- | grep -v "^07 07" > allop$i.d; done
$ (cat allop[24].d; grep -v "^56" allop6.d) > allop-2.d
```

出力されたallop-2.dをスクリプトで分析します。

```allop-2.pl
#!/usr/bin/env perl

%mne = ();
$cur = "";

sub output {
    my %tmp = ();
    while (my ($m, $o) = each %mne) {
        $o =~ s/^(.. ..) 12/$1 --/;
        $o =~ s/^(.. .. ..) 34 56/$1 -- --/;
        $tmp{$o} = $m;
    }
    foreach $o(sort keys %tmp) {
        print "$o\t$tmp{$o}\n";
    }
}

while (<>) {
    chop while substr($_, -1) le " ";
    @f = split(/\t/);
    $o = $f[0];
    $m = $f[1];
    $o1 = substr($o, 0, 2);
    if ($cur ne $o1) {
        output();
        %mne = ();
        $cur = $o1;
    }
    $t = $mne{$m};
    if ($t eq "") {
        $mne{$m} = $o;
    } else {
        $oo = "";
        for ($i = 0; $i < length($t); ++$i) {
            $ch = substr($t, $i, 1);
            $oo .= $ch eq substr($o, $i, 1) ? $ch : "-";
        }
        $mne{$m} = $oo;
    }
}
output();
```

ソースを標準入力で渡して実行結果をファイルに出力します。

```text
$ ./allop-2.pl < allop-2.d | tee allop-2.txt
01 01             	pr
01 02             	upt
01 04             	ptff
（略）
fb -- -- -- -- -- 	sp
fc -- -- -- -- -- 	mp
fd -- -- -- -- -- 	dp
```

ニーモニックごとに機械語の変化を調べます。16進数は変化しないオペコードの部分で、`-`は変化するオペランドの部分です。

全部で777命令です。

```text
$ wc -l allop-2.txt
777 allop-2.txt
```

オペコードのタイプは13種類です。飛び地になっているのが確認できます。

```text
$ cut -f1 allop-2.txt | sed s/[0-9a-f]/X/g | sort | uniq -c | nl
     1       33 XX -- -- -- -- --
     2       79 XX -- -- --
     3       56 XX --
     4      189 XX -- -- -- -- XX
     5       60 XX -X -- -- -- --
     6       16 XX X- -- --
     7       39 XX -X -- --
     8       16 XX X-
     9        1 XX -X
    10       92 XX -X -- -- -- XX
    11       32 XX XX -- -- -- --
    12      154 XX XX -- --
    13       10 XX XX
```

# オペランド

スクリプトでオペランドの部分に適当な値を埋め込んで、テスト用アセンブリを生成します。

```allop-3.pl
#!/usr/bin/env perl

while (<>) {
    @f = split(/\t/);
    $o = $f[0];
    chop $o while substr($o, -1) le " ";
    $o =~ s/^(..) -/$1 1/;
    $o =~ s/^(.. .)-/$1.2/e;
    $o =~ s/^(.. ..) -- --/$1 34 56/;
    $o =~ s/^(.. .. .. ..) --/$1 78/;
    $o =~ s/^(.. .. .. .. ..) --/$1 9a/;
    print ".byte 0x", join(", 0x", split(/ /, $o)), "\n";
}
```

ソースを標準入力で渡して実行結果をファイルに出力します。

```text
$ ./allop-3.pl < allop-2.txt | tee allop-3.s
.byte 0x01, 0x01
.byte 0x01, 0x02
.byte 0x01, 0x04
（略）
.byte 0xfb, 0x12, 0x34, 0x56, 0x78, 0x9a
.byte 0xfc, 0x12, 0x34, 0x56, 0x78, 0x9a
.byte 0xfd, 0x12, 0x34, 0x56, 0x78, 0x9a
```

## 組み合わせ

アセンブルして逆アセンブルします。

```text
$ s390-linux-as -o allop-3.o allop-3.s
$ s390-linux-objdump -d allop-3.o | cut -sf2- | grep -v "^07 07" | tee allop-3.d
01 01                   pr
01 02                   upt
01 04                   ptff
（略）
fb 12 34 56 78 9a       sp      1110(2,%r3),2202(3,%r7)
fc 12 34 56 78 9a       mp      1110(2,%r3),2202(3,%r7)
fd 12 34 56 78 9a       dp      1110(2,%r3),2202(3,%r7)
```

オペランドの組み合わせを確認すると、相対アドレスが別カウントされてしまいます。

```text
$ cut -f3 allop-3.d | sort | uniq -c | nl
     1       10
     2        2 %a1,%a2,1110(%r3)
     3        2 %a1,%a2,492630(%r3)
（略）
    29        1 %r1,0x68acf65a
    30        1 %r1,0x68acf666
    31        1 %r1,0x68acf750
（略）
   123        9 1110(2,%r3),2202(3,%r7)
   124        1 18
   125       10 492630(%r3),18
```

## 分割調査

相対アドレスを揃えるため、一行ずつ分けて処理します。

```text
$ while read line; do echo $line | s390-linux-as; s390-linux-objdump -d a.out | head -n8 | tail -n1 | cut -f2-; done < allop-3.s | tee allopr.d
01 01                   pr
01 02                   upt
01 04                   ptff
（略）
fb 12 34 56 78 9a       sp      1110(2,%r3),2202(3,%r7)
fc 12 34 56 78 9a       mp      1110(2,%r3),2202(3,%r7)
fd 12 34 56 78 9a       dp      1110(2,%r3),2202(3,%r7)
```

オペランドの組み合わせは62種類です。

```text
$ cut -f3 allopr.d | sort | uniq -c | nl
     1       10
     2        2 %a1,%a2,1110(%r3)
     3        2 %a1,%a2,492630(%r3)
（略）
    60        9 1110(2,%r3),2202(3,%r7)
    61        1 18
    62       10 492630(%r3),18
```

## 対応関係

オペランドはニブル単位で区切られます。ビット演算が不要でダンプから視認できるので便利です。

例を示します。括弧の中の即値は`+1`されていることに注意します。

```text
fd 12 34 56 78 9a    dp 1110(2,%r3),2202(3,%r7)
fd                -> dp
   1              ->         2=1+1
    2             ->                     3=2+1
      3           ->           %r3
       4 56       ->    1110=0x456
            7     ->                       %r7
             8 9a ->                2202=0x89a
```

レジスタはニブルがそのままレジスタ番号になるので、対応関係が簡単に分かります。

## 分析

オペランドを1つずつ取り出して種類を調べます。括弧の中で区切られないように、一旦セミコロンに置き換えて分割してから元に戻します。

```text
$ cut -f2- allopr.d | cut -sf2 | sed 's/(\([^)]*\),\([^)]*\))/(\1;\2)/g' | sed 's/,/\n/g' | sed 's/;/,/g' | sort | uniq > allopr.txt
```

この結果を手作業で分析して、対応する機械語を推定します。

種類|オペランド|機械語|備考
----|----------|------|----
レジスタ|`%a1`|`-- 1`|
レジスタ|`%a2`|`-- -2`|
レジスタ|`%c1`|`-- 1`|
レジスタ|`%c2`|`-- -2`|
レジスタ|`%f1`|`-- 1`|
レジスタ|`%f2`|`-- -2`|
レジスタ|`%f3`|`-- -- 3`|
レジスタ|`%f5`|`-- -- -- 5`|
レジスタ|`%f6`|`-- -- -- -6`|
レジスタ|`%f7`|`-- -- -- -- 7`|
レジスタ|`%r1`|`-- 1`|
レジスタ|`%r2`|`-- -2`|
レジスタ|`%r3`|`-- -- 3`|
レジスタ|`%r5`|`-- -- -- 5`|
レジスタ|`%r6`|`-- -- -- -6`|
メモリ|`1110(%r1,%r3)`|`-- 1- 34 56`|0x456=1110
メモリ|`1110(%r2,%r3)`|`-- -2 34 56`|
メモリ|`1110(%r3)`|`-- -- 34 56`|
メモリ|`1110(19,%r3)`|`-- 12 34 56`|0x12+1=19
メモリ|`1110(2,%r3)`|`-- 1- 34 56`|1+1=2
メモリ|`2202(%r7)`|`-- -- -- -- 78 9a`|0x89a=2202
メモリ|`2202(19,%r7)`|`-- 12 -- -- 78 9a`|0x12+1=19
メモリ|`2202(3,%r7)`|`-- -2 -- -- 78 9a`|1+1=2
メモリ|`492630(%r2,%r3)`|`-- -2 34 56 78`|0x78456=492630
メモリ|`492630(%r3)`|`-- -- 34 56 78`|
即値|`0`|`-- 0`|オペコードの一部？
即値|`1`|`-- 1`|
即値|`2`|`-- -2`|
即値|`3`|`-- -- 3`|
即値|`4`|`-- -- -4`|
即値|`7`|`-- -- -- -- 7`|
即値|`8`|`-- -- -- -- -8`|
即値|`18`|`-- 12`|0x12=18
即値|`52`|`-- -- 34`|0x34=52
即値|`86`|`-- -- -- 56`|0x56=86
即値|`120`|`-- -- -- -- 78`|0x78=120
即値|`13398`|`-- -- 34 56`|0x3456=13398
即値|`30874`|`-- -- -- -- 78 9a`|0x789a=30874
即値|`878082202`|`-- -- 34 56 78 9a`|0x3456789a=878082202
相対アドレス|`0x468`|`-- -2 34`|0+2*0x234=0x468
相対アドレス|`0x68ac`|`-- -- 34 56`|0+2*0x3456=0x68ac
相対アドレス|`0x68acf134`|`-- -- 34 56 78 9a`|0+2*0x3456789a=0x68acf134
相対アドレス|`0xacf134`|`-- -- -- 56 78 9a`|0+2*0x56789a=0xacf134
相対アドレス|`0xf134`|`-- -- -- -- 78 9a`|0+2*0x789a=0xf134

相対アドレスの基点は今の命令です（この例では0番地）。命令長は偶数のためオペランドを2倍しています。大抵のアーキテクチャでは次の命令が基点になっているのと異なるため、注意が必要です。

## 命令フォーマット一覧

調査結果を基にスクリプトで命令フォーマット一覧を生成します。

```format.pl
#!/usr/bin/env perl

%opt = (
    "%a1"             => ["%aS"        , "-- S"             ],
    "%a2"             => ["%aT"        , "-- -T"            ],
    "%c1"             => ["%cS"        , "-- S"             ],
    "%c2"             => ["%cT"        , "-- -T"            ],
    "%f1"             => ["%fS"        , "-- S"             ],
    "%f2"             => ["%fT"        , "-- -T"            ],
    "%f3"             => ["%fU"        , "-- -- U"          ],
    "%f5"             => ["%fW"        , "-- -- -- W"       ],
    "%f6"             => ["%fX"        , "-- -- -- -X"      ],
    "%f7"             => ["%fY"        , "-- -- -- -- Y"    ],
    "%r1"             => ["%rS"        , "-- S"             ],
    "%r2"             => ["%rT"        , "-- -T"            ],
    "%r3"             => ["%rU"        , "-- -- U"          ],
    "%r5"             => ["%rW"        , "-- -- -- W"       ],
    "%r6"             => ["%rX"        , "-- -- -- -X"      ],
    "1110(%r1,%r3)"   => ["V(%rS,%rU)" , "-- S- UV VV"      ],
    "1110(%r2,%r3)"   => ["V(%rT,%rU)" , "-- -T UV VV"      ],
    "1110(%r3)"       => ["V(%rU)"     , "-- -- UV VV"      ],
    "1110(19,%r3)"    => ["V(S,%rU)"   , "-- SS UV VV"      ],
    "1110(2,%r3)"     => ["V(S,%rU)"   , "-- S- UV VV"      ],
    "2202(%r7)"       => ["Z(%rY)"     , "-- -- -- -- YZ ZZ"],
    "2202(19,%r7)"    => ["Z(S,%rY)"   , "-- SS -- -- YZ ZZ"],
    "2202(3,%r7)"     => ["Z(T,%rY)"   , "-- -T -- -- YZ ZZ"],
    "492630(%r2,%r3)" => ["YV(%rT,%rU)", "-- -T UV VV YY"   ],
    "492630(%r3)"     => ["YV(%rU)"    , "-- -- UV VV YY"   ],
    "0"               => ["S"          , "-- S"             ],
    "1"               => ["S"          , "-- S"             ],
    "2"               => ["T"          , "-- -T"            ],
    "3"               => ["U"          , "-- -- U"          ],
    "4"               => ["U"          , "-- -- -U"         ],
    "7"               => ["Y"          , "-- -- -- -- Y"    ],
    "8"               => ["Z"          , "-- -- -- -- -Z"   ],
    "18"              => ["S"          , "-- SS"            ],
    "52"              => ["U"          , "-- -- UU"         ],
    "86"              => ["W"          , "-- -- -- WW"      ],
    "120"             => ["Y"          , "-- -- -- -- YY"   ],
    "13398"           => ["U"          , "-- -- UU UU"      ],
    "30874"           => ["Y"          , "-- -- -- -- YY YY"],
    "878082202"       => ["U"          , "-- -- UU UU UU UU"],
    "0x468"           => ["0xT"        , "-- -T TT"         ],
    "0x68ac"          => ["0xU"        , "-- -- UU UU"      ],
    "0x68acf134"      => ["0xU"        , "-- -- UU UU UU UU"],
    "0xacf134"        => ["0xW"        , "-- -- -- WW WW WW"],
    "0xf134"          => ["0xY"        , "-- -- -- -- YY YY"]
);

while (<>) {
    chop while substr($_, -1) le " ";
    ($bin, $mne, $opr) = split(/\t/);
    $opr =~ s/\(([^)]+),([^)]+)\)/($1;$2)/g;
    @oprs = ();
    foreach $o(split(",", $opr)) {
        $o =~ s/;/,/g;
        ($o1, $b1) = @{$opt{$o}};
        for ($j = 0; $j < length($b1); ++$j) {
            $ch = substr($b1, $j, 1);
            if ($ch ge "S") {
                $bin = substr($bin, 0, $j) . $ch . substr($bin, $j + 1);
            }
        }
        push(@oprs, $o1);
    }
    print "$bin\t$mne\t", join(",", @oprs), "\n";
}
```

ソースを標準入力で渡して実行結果をファイルに出力します。

```text
$ ./format.pl < allopr.d | tee format.txt
01 01                   pr
01 02                   upt
01 04                   ptff
（略）
fb ST UV VV YZ ZZ       sp      V(S,%rU),Z(T,%rY)
fc ST UV VV YZ ZZ       mp      V(S,%rU),Z(T,%rY)
fd ST UV VV YZ ZZ       dp      V(S,%rU),Z(T,%rY)
```

以上で総当たりによる調査は完了しました。

# まとめ

今回のスクリプトや出力結果は以下に置いてあります。

* https://bitbucket.org/7shi/s390/src