深さ優先探索によるトポロジカルソート

トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。

入力辺がないノードをキュー q に入れる
while (q に要素が含まれる):
  node = q.pop()
  print(node)  
  nodeの出力辺を全て削除する
  入力辺がないノードをキュー q に入れる(ただし、printしたnodeは除く)

トポロジカルソート - Wikipedia をみますと、上記アルゴリズムの他に、深さ優先探索による方法でトポロジカルソートを行うアルゴリズムが書かれてあります。

深さ優先探索によるトポロジカルソートのプログラムを Lua で書いてみました。

入力ファイルとして、Problem 79 - Project Eulerのkeylog.txtを使います。

tsort コマンド

tsort (Unix) - Wikipedia, the free encyclopedia というトポロジカルソートを行うコマンドがあるようです。この tsort コマンドをつかって、トポロジカルソートしてみました。

% awk '{ split($1, a, ""); print a[1], a[2], a[2], a[3] }' < keylog.txt | tsort
7
3
1
6
2
8
9
0

参考

池袋バイナリ勉強会(9)に参加しました

12月2日(日)に開催された池袋バイナリ勉強会(9)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outの逆アセンブル、およびインタプリタの作成に取り組んでいます。

目標: hello.c を実行するインタプリタの作成

% cat hello.c
main() {
  write(1, "hello\n", 6);
}
% v6cc hello.c
% v6run a.out
hello

mov 命令の実装

mov 命令は、前回の勉強会で勉強したことを、そのまま素直に実装しました。

jsr 命令の実装(実装途中)

jsr 命令は、『pdp40/11 processor handbook』(pdp11-40.pdf)を読んでもさっぱり分かりませんでした。そこで、まずは以下のサンプルで jsr の仕組みを見ていきました。

% cat jsr.s
.globl _printf
.globl _exit

mov $10, r2
mov r2, -(sp)
mov $format, -(sp)
jsr pc, _printf
add $4, sp

mov $0, -(sp)
jsr pc, _exit

format: <value:%d\n\0>

v6asでアセンブルして、v6runで実行します。

% v6as jsr.s
% v6run a.out
000c,0000,0008,0000,0000,0000,sp=0004,pc=0006: invalid operand

エラー(invalid operand)が出ました。何かがおかしいです。逆アセンブルしてみます。

% v6as jsr.s
% v6strip a.out
% pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	15c2 0008      	mov	$10, r2
   4:	10a6           	mov	r2, -(sp)
   6:	15e6 001a      	mov	$32, -(sp)
   a:	09f7 fff2      	jsr	pc, 0x0     # <---- 0x0 は、おかしい
   e:	65c6 0004      	add	$4, sp
  12:	15e6 0000      	mov	$0, -(sp)
  16:	09f7 ffe6      	jsr	pc, 0x0
  1a:	6176 756c      	add	r5, 72554(sp)
  1e:	3a65           	bit	*-(r1), -(r5)
  20:	6425           	add	(r0)+, -(r5)
  22:	000a           	.word	12

_printfのアドレスが 0x0 になっているのがおかしいようです。この場合、v6ld a.out /lib/libc.a を実行します。

% v6as jsr.s
% v6ld a.out /lib/libc.a
% v6run a.out
value:8

今度はうまく行きました!ちなみに、このa.outに対して再び逆アセンブルを行うと、先ほどの_printfのアドレスが0x0から0x24に置き換わっており、さらに0x24以降の命令列を眺めると、それは v6src/s5/printf.s ファイルの中身がそのまま格納されているのが確認出来ます。

jsr.s における jsr 命令を見る限り、どうやら jsr 命令では _printf を呼び出しているようです。DEC PDP-11 Subroutines には、jsr 命令について、次のように解説されています。

        jsr  register,target   - push register; register <- PC; PC <- target
        rts  register          - PC <- register; pop register

If the specified register is r7 (the PC), then the PC is pushed and popped.

先ほどの jsr.s をもう一度見てみます。

% cat jsr.s
.globl _printf
.globl _exit

mov $10, r2
mov r2, -(sp)
mov $format, -(sp)
jsr pc, _printf
add $4, sp

mov $0, -(sp)
jsr pc, _exit

format: <value:%d\n\0>

つまり、jsr pc, _printf が行っていることは、

  • pc をプッシュ
  • pc に pc の値を代入
  • pc に _printf の値を代入

となります。プログラムカウンタ(pc)にはジャンプ先(_printf)を格納して、処理が終わると(ジャンプ前に保存しておいた)元の場所に戻る仕組みのようです。

jsr 命令の対として rts 命令があり、rts 命令が元の位置に戻るための命令になります。C言語のreturnのイメージです。

(補足): ちなみに、v6strip後にv6ldを実行すると以下のエラーが表示されました。

% v6as jsr.s
% v6strip a.out
% v6ld a.out /lib/libc.a
a.out: No relocation bits
a.out: Relocation error

bne 命令を用いたサンプル: loop.s

% cat loop.s 
.globl _printf
.globl _exit

    mov $10, r2
loop:
    mov r2, -(sp)
    mov $format, -(sp)
    jsr pc, _printf
    add $4, sp
    dec r2
    bne loop

    mov $0, -(sp)
    jsr pc, _exit

format: <%d\n\0>

実行結果です。

% v6as loop.s && v6ld a.out /lib/libc.a
% v6run a.out
8
7
6
5
4
3
2
1

v6runのverbose modeとsyscall mode

v6runコマンドは、-v, -s オプションをとるようになっていて、それぞれのオプションを指定するとsyscallと逆アセンブル結果を出力してくれるようになります。

% v6run
usage: v6run [-r V6ROOT] [-v/-s] cmd [args ...]
    -v: verbose mode (output syscall and disassemble)
    -s: syscall mode (output syscall)

実行例です。

% v6as jsr.s && v6ld a.out /lib/libc.a   
% v6run -s a.out
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
v0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
a0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
l0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
u0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
e0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,0008,0000,fff4,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001
:0001,0000,ff6d,ffff,0001,ff60,sp=ff5e,pc=0226: sys indir; 029c
0001,0000,ff6d,ffff,0001,ff60,sp=ff5e,pc=0226: sys write; 02b2; 0001
80001,0000,ff6d,ffff,fff6,ff64,sp=ff62,pc=0226: sys indir; 029c
0001,0000,ff6d,ffff,fff6,ff64,sp=ff62,pc=0226: sys write; 02b2; 0001

0000,ffe8,0008,0000,0000,fff0,sp=fff0,pc=024e: sys exit

ところどころに、v a l u e : 8 の文字が出力されているのが確認できます。sys writeが文字を出力しているようです。

N, Z, V, C フラグ

『pdp11/40 processor handbook』(pdp11-40.dpf)を読むと、たとえば mov の説明には、N, Z, V, C フラグに関する記述があります。

Condition Codes: N: set if (src) < 0; cleared otherwise
                 Z: set if (src) = 0; cleared otherwise
                 V: cleard
                 C: not affected

mov 命令を実行した後、その処理結果に応じて N, Z, V, C の値が変わります。これらのフラグの値がどのように変更されるかは、それぞれ命令ごとに異なります。たとえば、上記の mov 命令の場合、V フラグは必ずクリアされることになります。

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)』が出版されます。

以下の本が出版されることを勉強会で教えていただきました。とても楽しみです。

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

勉強会後にやったこと

7shiさんのv6runソースをGNU GLOBALで読む。

id:n7shiさんのv6runGNU GLOBALで読めるようにしました。

% gtags -v 
[Sat Dec 15 21:02:15 JST 2012] Gtags started.
 Using default configuration.
[Sat Dec 15 21:02:15 JST 2012] Creating 'GTAGS' and 'GRTAGS'.
 [1] extracting tags of AOut.cpp
 [2] extracting tags of AOut.h
 [3] extracting tags of main.cpp
 [4] extracting tags of Operand.cpp
 [5] extracting tags of Operand.h
 [6] extracting tags of utils.cpp
 [7] extracting tags of utils.h
 [8] extracting tags of VM.cpp
 [9] extracting tags of VM.h
 [10] extracting tags of VM.inst.cpp
 [11] extracting tags of VM.signal.cpp
 [12] extracting tags of VM.sys.cpp
[Sat Dec 15 21:02:15 JST 2012] Done.
% htags -ansx

参考:

v6runのverbose modeでN, Z, V, Cフラグの値を出力する

v6runのソースを改造して、N, Z, V, Cの値を出力するようにしました。VM.cppのdebug()メソッドを書き換えます。

void VM::debug(const std::string &msg)
{
    fprintf(stderr,
            "%04x,%04x,%04x,%04x,%04x,%04x,sp=%04x,pc=%04x: %s\n",
            r[0], r[1], r[2], r[3], r[4], r[5], r[6], prevPC, msg.c_str());

    fprintf(stderr, "N:%d Z:%d V:%d C:%d\n", N, Z, V, C); 
}

さきほどの loop.s プログラムを用いて、N, Z, V, C のフラグの変化を確認してみます。注目ポイントは、bne 命令を実行するときの Z フラグの値です。

サンプルプログラム(ループ回数を3回に変更しました):

% cat loop.s
.globl _printf
.globl _exit

    mov $3, r2
loop:
    mov r2, -(sp)
    mov $format, -(sp)
    jsr pc, _printf
    add $4, sp
    dec r2
    bne loop

    mov $0, -(sp)
    jsr pc, _exit

format: <%d\n\0>

アセンブル結果です。(先頭一部のみ)

% v6as loop.s && v6ld a.out /lib/libc.a 
% v6strip a.out
% pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	15c2 0003      	mov	$3, r2
   4:	10a6           	mov	r2, -(sp)
   6:	15e6 001e      	mov	$36, -(sp)
   a:	09f7 0014      	jsr	pc, 0x22
   e:	65c6 0004      	add	$4, sp
  12:	0ac2           	dec	r2
  14:	02f7           	bne	0x4       # <--- ここに注目
  16:	15e6 0000      	mov	$0, -(sp)
  1a:	09f7 0226      	jsr	pc, 0x244
<以降省略>

実行結果です。

% v6run2 -v a.out
...<省略>...
0000,ffe8,0002,0000,0000,0000,sp=fff6,pc=0014: bne
N:0 Z:0 V:0 C:0
...<省略>...
0000,ffe8,0001,0000,0000,0000,sp=fff6,pc=0014: bne
N:0 Z:0 V:0 C:0
...<省略>...
0000,ffe8,0000,0000,0000,0000,sp=fff6,pc=0014: bne
N:0 Z:1 V:0 C:0
...<省略>...

『pdp11/40 processor handbook』(pdp11-40.pdf)によると、bne 命令は Z = 0 の場合に pc の値を書き換えるとあります。上のv6run2による実行結果をみると、pc=0014 の bne 命令が 3 回実行されており、最初の 2 回は Z = 0 でループを繰り返しているのが確認出来ました。

Githubにプロジェクトを登録しました

https://github.com/noriok/pdp11

更新履歴

(2012-12-23) Githubのプロジェクトへのリンクを追加しました。

SRM563 div2 easy FoxAndHandleEasy

文字列Sがあり、その文字列Sの任意の位置に同じ文字列Sを挿入する。そうして作られる文字列をSのexpansionと呼ぶとする。文字列S, Tが与えられたとき、TがSのexpansionかどうかを求める問題。

コンテスト中に書いたコードは以下。std::stringの文字列の削除のやり方がすぐに分からず、Dashで調べながら小さなプログラムを書いて確認しようかなと思ったけど逆に時間がかかりそうだったので止めました。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class FoxAndHandleEasy {
public:
    string isPossible( string S, string T ) {
        const int n = S.length();
        if (n*2 != T.length()) return "No";

        for (int i = 0; i < (int)T.length(); i++) {
            if (i+n >= T.length()) break;

            bool ok = true;
            for (int j = 0; j < n; j++) {
                if (S[j] != T[j+i]) {
                    ok = false;
                    break;
                }
            }

            if (!ok) continue;
            int p = 0;
            for (int j = 0; j < (int)T.length(); j++) {
                if (i <= j && j < i+n) continue;

                if (S[p++] != T[j]) {
                    ok = false;
                    break;
                }
            }

            if (ok) return "Yes";
        }
        return "No";
    }
};

Challenge phaseで他の人のコードを読むと、単純に文字列Sを検索して、見つかったらそれを削除して残りがSに等しいかを確認しているコードが殆どでした。ミスしてそうなコードは見当たらず、そのままChallenge phaseは終わりました。System Testが始まり、多くの人がこの問題を落としていて何事かと思ったら、以下のようなケースで引っかかっていました。

S = aba
T = ababaa

最初に見つかる aba を削除すると残る文字列は baa になり、Sと一致しませんが、2番目に見つかる aba を削除すると残る文字列は aba となり、Sと等しくなります。つまり、削除する文字列の位置が重要なんですね。これは気づきませんでした(気づかずに、Tに含まれる全てのSを検索するようなコードを書いていました)。

コンテスト後に書き直したコード:

class FoxAndHandleEasy {
public:
    string isPossible( string S, string T ) {
        string::size_type p = 0;
        while (string::npos != (p = T.find(S, p))) {
            string x = T.substr(0, p) + T.substr(p+S.length());
            if (x == S) return "Yes";
            p++;
        }
        return "No";
    }
};

池袋バイナリ勉強会(8)に参加しました

11月25日(日)に開催された池袋バイナリ勉強会(8)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outを逆アセンブルする自作スクリプトを作成しながら、平行してそれを実行するインタプリタを作ろうとしている段階です。

アセンブラの作成

以下のhello.cを逆アセンブルするプログラムの作成に取り組んでいます。

$ cat hello.c
main() {
  write(0, "hello\n", 6);
}

たったこれだけのコードですが、hello.cから生成されるa.outをpdp11-aout-objdumpで逆アセンブルしてみると、いろんな処理が行われているのが分かります。逆アセンブル結果が以下になります。

$ v6cc hello.c                # コンパイル
$ v6strip a.out               # シンボルテーブル削除
$ pdp11-aout-objdump -d a.out # 逆アセンブル

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	f009           	setd
   2:	1180           	mov	sp, r0
   4:	1226           	mov	(r0), -(sp)
   6:	0bd0           	tst	(r0)+
   8:	1036 0002      	mov	r0, 2(sp)
   c:	09f7 0008      	jsr	pc, 0x18
  10:	100e           	mov	r0, (sp)
  12:	09df 0052      	jsr	pc, *$122
  16:	8901           	sys	1
  18:	0977 0040      	jsr	r5, 0x5c
  1c:	15ce 0006      	mov	$6, (sp)
  20:	15e6 0086      	mov	$206, -(sp)
  24:	0a26           	clr	-(sp)
  26:	09df 0030      	jsr	pc, *$60
  2a:	2596           	cmp	(sp)+, (sp)+
  2c:	0077 003a      	jmp	0x6a
  30:	1166           	mov	r5, -(sp)
  32:	1185           	mov	sp, r5
  34:	1d40 0004      	mov	4(r5), r0
  38:	1d77 0006 0052 	mov	6(r5), $0x90
  3e:	1d77 0008 004e 	mov	10(r5), $0x92
  44:	8900           	sys	0
  46:	008e           	.word	216
  48:	8602           	bcc	0x4e
  4a:	0077 002a      	jmp	0x78
  4e:	1585           	mov	(sp)+, r5
  50:	0087           	rts	pc
  52:	1166           	mov	r5, -(sp)
  54:	1185           	mov	sp, r5
  56:	1d40 0004      	mov	4(r5), r0
  5a:	8901           	sys	1
  5c:	1140           	mov	r5, r0
  5e:	1185           	mov	sp, r5
  60:	1126           	mov	r4, -(sp)
  62:	10e6           	mov	r3, -(sp)
  64:	10a6           	mov	r2, -(sp)
  66:	0be6           	tst	-(sp)
  68:	0048           	jmp	(r0)
  6a:	1141           	mov	r5, r1
  6c:	1844           	mov	-(r1), r4
  6e:	1843           	mov	-(r1), r3
  70:	1842           	mov	-(r1), r2
  72:	1146           	mov	r5, sp
  74:	1585           	mov	(sp)+, r5
  76:	0087           	rts	pc
  78:	1037 0018      	mov	r0, $0x94
  7c:	15c0 ffff      	mov	$-1, r0
  80:	1146           	mov	r5, sp
  82:	1585           	mov	(sp)+, r5
  84:	0087           	rts	pc

自作の逆アセンブラによる出力は以下になります。Pythonで作成しています。

$ python ./script/dump.py a.out
text size: 134
data size: 14
   0: f009           setd                 170011
   2: 1180           mov sp, r0           010600
   4: 1226           mov (r0), -(sp)      011046
   6: 0bd0           tst (r0)+            005720
   8: 1036 0002      mov r0, 0o2(sp)      010066 000002
   c: 09f7 0008      jsr pc, 0o10(pc) => $0x18 004767 000010
  10: 100e           mov r0, (sp)         010016
  12: 09df 0052      jsr pc, @(pc)+ => 82(0o122 0x52) 004737 000122
  16: 8901           sys 1                104401
  18: 0977 0040      jsr r5, 0o100(pc) => $0x5c 004567 000100
  1c: 15ce 0006      mov $6, (sp)         012716 000006
  20: 15e6 0086      mov $206, -(sp)      012746 000206
  24: 0a26           clr -(sp)            005046
  26: 09df 0030      jsr pc, @(pc)+ => 48(0o60 0x30) 004737 000060
  2a: 2596           cmp (sp)+, (sp)+     022626
  2c: 0077 003a      jmp 0o72(pc) => $0x6a 000167 000072
  30: 1166           mov r5, -(sp)        010546
  32: 1185           mov sp, r5           010605
  34: 1d40 0004      mov 0o4(r5), r0      016500 000004
  38: 1d77 0006 0052 mov 0o6(r5), 0o122(pc) => $0x90 016567 000006 000122
  3e: 1d77 0008 004e mov 0o10(r5), 0o116(pc) => $0x92 016567 000010 000116
  44: 8900           sys 0                104400
  46: 008e           .word 0o216          000216
  48: 8602           bcc 0x4e             103002
  4a: 0077 002a      jmp 0o52(pc) => $0x78 000167 000052
  4e: 1585           mov (sp)+, r5        012605
  50: 0087           rts pc               000207
  52: 1166           mov r5, -(sp)        010546
  54: 1185           mov sp, r5           010605
  56: 1d40 0004      mov 0o4(r5), r0      016500 000004
  5a: 8901           sys 1                104401
  5c: 1140           mov r5, r0           010500
  5e: 1185           mov sp, r5           010605
  60: 1126           mov r4, -(sp)        010446
  62: 10e6           mov r3, -(sp)        010346
  64: 10a6           mov r2, -(sp)        010246
  66: 0be6           tst -(sp)            005746
  68: 0048           jmp (r0)             000110
  6a: 1141           mov r5, r1           010501
  6c: 1844           mov -(r1), r4        014104
  6e: 1843           mov -(r1), r3        014103
  70: 1842           mov -(r1), r2        014102
  72: 1146           mov r5, sp           010506
  74: 1585           mov (sp)+, r5        012605
  76: 0087           rts pc               000207
  78: 1037 0018      mov r0, 0o30(pc) => $0x94 010067 000030
  7c: 15c0 ffff      mov $177777, r0      012700 177777
  80: 1146           mov r5, sp           010506
  82: 1585           mov (sp)+, r5        012605
  84: 0087           rts pc               000207

mov の引数のパターン

Mode Name Symbolic Description
0 register R Rの値
1 register deferred (R) Rの値をアドレスと見なし、そのアドレスの値
2 auto-increment (R)+ Rの値をアドレスと見なし、そのアドレスの値; R+=2
3 auto-incr deferred @(R)+ Rの値をアドレスと見なし、そのアドレスの値をさらにアドレスとみなし、そのアドレスの値; R+=2
4 auto-decrement -(R) R-=2; Rの値をアドレスと見なし、そのアドレスの値
5 auto-decr deferred @-(R) R-=2; Rの値をアドレスと見なし、そのアドレスの値をさらにアドレスと見なし、そのアドレスの値
6 index X(R) R+Xの値をアドレスと見なし、そのアドレスの値
7 index deferred @X(R) R+Xの値をアドレスと見なし、そのアドレスの値をさらにアドレスと見なし、そのアドレスの値

表のSymbolicの括弧の意味は、C言語のポインタのデリファレンスと同じと捉えて良いようです。また、@ も同様でポインタのデリファレンスと同じ意味になります。ですから、@ ( R )+ は、( ( R ) )+ のように括弧が2重になったものと解釈すると良いと教えていただきました。C言語のポインタのポインタですね。

(今後の課題)条件式と符号なし整数

Lions’ Commentary on UNIX (Ascii books)』の278ページには以下の記述があります。

Cでは条件式を使うことができる。aとbが整数変数ならば、

 (a > b ? a : b)
はaとbの大きなほうを値として持つ式である。

ただし、これはaとbが符号なし整数とみなされる場合には機能しない。したがって、次の手続きを使用する。

 6326 max (a, b)
      char *a, *b;
      {
        if (a > b)
          return (a);
        return (b);
      }
ここでのトリックは、文字へのポインタとして宣言されたaとbが比較のために符号なし整数として扱われるということである。

aとbが符号なしの場合、条件式がなぜ機能しないのか疑問に思いました。その理由を勉強会で教えていただいたのですが、よく理解出来ませんでした……。まだまだ学ぶべきことが沢山あるので、今後の課題となります。理解できたら改めてブログに書くつもりです。

池袋バイナリ勉強会(5)に参加しました

10月21日(日)に開催された池袋バイナリ勉強会(5)に参加しました。PDP-11の実行ファイル(a.out形式)の解析に取り組んでいます。

以下、取り組んだ内容のメモです(書かれている内容には間違いがあるかも知れません)。

前回までの復習

前回までの勉強会で学んだことの復習をしました。

write.sファイルからa.outを作成します。

mov $1, r0
sys write
hello
6

mov $0, r0
sys exit

.data
hello: <hello\n>

v6asでa.outが作られます(アセンブル、リンク)。v6runでa.outを実行します。実行するとhelloと出力されます。

$ v6as write.s
$ v6run a.out
hello

v6stripでシンボル情報を削除します。

$ v6strip a.out

pdp11-aout-objdump -d a.outで逆アセンブルします(v6stripでa.outに含まれるシンボル情報を削除しないと正しく逆アセンブルできません)。

~/etc/pdp-11 $ pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	15c0 0001      	mov	$1, r0
   4:	8904           	sys	4
   6:	0010           	.word	20
   8:	0006           	rtt
   a:	15c0 0000      	mov	$0, r0
   e:	8901           	sys	1
  • 定義されていない命令は、.word として表示されるようです。
  • .word 20の20は8進表記です。

アセンブル/実行を行うスクリプトの作成

先ほどのwrite.sから出力されたa.outに対して、pdp11-aout-objdumpを実行すると逆アセンブル結果が出力されますが、pdp11-aout-objdumpを使わずに、逆アセンブルを行うスクリプトの作成に取り組みました(write.sで使用している命令のみ)。

a.outをバイナリエディタで開いて、pdp11-aout-objdumpでの逆アセンブル結果と見比べます。

$ xxd a.out
0000000: 0701 1000 0600 0000 0000 0000 0000 0100  ................
0000010: c015 0100 0489 1000 0600 c015 0000 0189  ................
0000020: 6865 6c6c 6f0a                           hello.

a.outの先頭16バイトはヘッダになっています。ここにテキストサイズ、データサイズ、シンボル情報のサイズなどが書き込まれているようです。17バイト目から命令が始まっています。

アセンブルすることが出来たら、次はa.outを実行するスクリプト("hello"と出力するスクリプト)を作成しました。実際には、mov,sysの正しい振る舞いは理解していないので、それっぽく動作するスクリプトを書いただけです。

v6nmでシンボルテーブル出力

v6nmでシンボルテーブルが出力されます。

$ v6as write.s
$ v6nm a.out
000020d hello

v6stripでシンボルテーブルを削除してから、v6nmを再度実行すると、今度は「no name list」を表示されます。

$ v6strip a.out
$ v6nm a.out
no name list

strip前後のa.outを見比べてみます。

$ v6as write.s
$ xxd a.out
0000000: 0701 1000 0600 0000 0c00 0000 0000 0000  ................
0000010: c015 0100 0489 1000 0600 c015 0000 0189  ................
0000020: 6865 6c6c 6f0a 0000 0000 0000 0400 0000  hello...........
0000030: 0000 0000 0000 0000 0000 0000 6865 6c6c  ............hell
0000040: 6f00 0000 0300 1000                      o.......
$ v6strip a.out
$ xxd a.out
0000000: 0701 1000 0600 0000 0000 0000 0000 0100  ................
0000010: c015 0100 0489 1000 0600 c015 0000 0189  ................
0000020: 6865 6c6c 6f0a                           hello.                                   

strip前のa.outの9, 10バイト目には0c00とありますが、リトルエンディアンなのでひっくり返して000c(10進数で12)がシンボルテーブルのサイズとなります。strip後ではこの部分の値が0になっているのが確認出来ます。v6strip実行すると、a.outのファイルサイズが72バイトから38バイトになり、34バイト削られていますから、v6stripはシンボルテーブル以外にも削っている情報があるということでしょうか(よく分かっていません)。

ちなみに、オフセット0000020には、helloっぽいものがありますが、先ほどv6nmにて表示されたものがこれに対応しているような感じです。

v6arでlibc.aを展開

v6arでlibc.aを展開すると、.oファイルが出てきます。

$ ls
libc.a
$ v6ar x libc.a
$ ls
abort.o     dup.o       getpid.o    mcount.o    ptrace.o    stat.o
abs.o       errlst.o    getpw.o     mdate.o     putc.o      stime.o
alloc.o     execl.o     getuid.o    mknod.o     putchr.o    stty.o
atof.o      execv.o     gtty.o      mon.o       qsort.o     sync.o
atoi.o      exit.o      hmul.o      mount.o     read.o      time.o
cerror.o    ffltpr.o    kill.o      nargs.o     reset.o     times.o
chdir.o     fltpr.o     ladd.o      nice.o      rin.o       umount.o
chmod.o     fork.o      ldfps.o     nlist.o     sbrk.o      unlink.o
chown.o     fstat.o     libc.a      open.o      seek.o      wait.o
close.o     getc.o      link.o      perror.o    setgid.o    write.o
creat.o     getchr.o    locv.o      pipe.o      setuid.o
csv.o       getcsw.o    ltod.o      printf.o    signal.o
ctime.o     getgid.o    makdir.o    prof.o      sleep.o

v6cc -Sで*.s出力

v6cc -SでCプログラムからアセンブリコードを出力できます。

$ cat wr.c
main() {
  write(1, "hello\n", 6);
}
$ v6cc -S wr.c
$ cat wr.s
.globl	_main
.text
_main:
~~main:
jsr	r5,csv
mov	$6,(sp)
mov	$L2,-(sp)
mov	$1,-(sp)
jsr	pc,*$_write
cmp	(sp)+,(sp)+
L1:jmp	cret
.globl
.data
L2:.byte 150,145,154,154,157,12,0

write()の第1引数の整数

  • 0を渡すと、stdin
  • 1を渡すと、stdout
  • 2を渡すと、stderr
$ cat wr.c
main() {
  write(1, "hello\n", 6);
}
$ v6cc wr.c
$ v6run a.out
hello

a.outにはcrt0.sがそのまま含まれている

main() {}

test.cをコンパイルして逆アセンブルした結果を見ると、v6src/s4/crt0.sのコードがそのまま含まれているのが確認できます。

/ C runtime startoff

.globl	savr5
.globl	_exit

.globl	_main

start:
	setd
	mov	sp,r0
	mov	(r0),-(sp)
	tst	(r0)+
	mov	r0,2(sp)
	jsr	pc,_main
	mov	r0,(sp)
	jsr	pc,*$_exit
	sys	exit

.bss
savr5:	.=.+2

以下がa.outの逆アセンブル結果です。

$ pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	f009           	setd
   ↓↓↓↓↓↓ crt0.s ↓↓↓↓↓↓
   2:	1180           	mov	sp, r0
   4:	1226           	mov	(r0), -(sp)
   6:	0bd0           	tst	(r0)+
   8:	1036 0002      	mov	r0, 2(sp)
   c:	09f7 0008      	jsr	pc, 0x18
  10:	100e           	mov	r0, (sp)
  12:	09df 0020      	jsr	pc, *$40
  16:	8901           	sys	1
  ↑↑↑↑↑↑ crt0.s ↑↑↑↑↑↑
  18:	0977 000e      	jsr	r5, 0x2a
  1c:	0077 0018      	jmp	0x38
  20:	1166           	mov	r5, -(sp)
  22:	1185           	mov	sp, r5
  24:	1d40 0004      	mov	4(r5), r0
  28:	8901           	sys	1
  2a:	1140           	mov	r5, r0
  2c:	1185           	mov	sp, r5
  2e:	1126           	mov	r4, -(sp)
  30:	10e6           	mov	r3, -(sp)
  32:	10a6           	mov	r2, -(sp)
  34:	0be6           	tst	-(sp)
  36:	0048           	jmp	(r0)
  38:	1141           	mov	r5, r1
  3a:	1844           	mov	-(r1), r4
  3c:	1843           	mov	-(r1), r3
  3e:	1842           	mov	-(r1), r2
  40:	1146           	mov	r5, sp
  42:	1585           	mov	(sp)+, r5
  44:	0087           	rts	pc

その他、学んだこと

  • mov命令でのPC(プログラムカウンタ)について学びました(ここに書けるほどには理解していませんが……)。

  • 以下の2冊の本を紹介していただきました。

Linkers & Loaders

Linkers & Loaders

Lions’ Commentary on UNIX (Ascii books)

Lions’ Commentary on UNIX (Ascii books)

Lions’ Commentary on UNIX (Ascii books)』は、さっそく購入しました。

池袋バイナリ勉強会(2)に参加してきました

9月23日(日)に池袋バイナリ勉強会(2)に参加してきました。

MonoDevelopHello world!

MonoDevelopとGTK#を用いて、ボタンをクリックしたらメッセージダイアログを表示するGUIプログラムを書きました。

  • MonoDevelopをインストールします。MonoDevelopからダウンロード出来ます。
  • Gtk# 2.0プロジェクト新規作成。
  • ウィンドウにボタンを配置して、イベントハンドラに"World!"とメッセージダイアログを表示するコードを記述します。
protected void OnButton3Clicked (object sender, EventArgs e)
{
    var md = new MessageDialog(this,
   	                            DialogFlags.Modal, MessageType.Info,
	                            ButtonsType.Ok, "World!");
    md.Run ();
    md.Destroy ();
}

ボタンを押すと、以下のようにメッセージダイアログが表示されます。

f:id:noriok:20120929195503p:plain

躓いたところ:

  • なぜかぼくのMacBook(OS X 10.8.2)では、MonoDevelop(バージョン 3.0.4.7)上で縦棒「|」を入力すると、MonoDevelop上では閉じ括弧「}」が入力されてしまう問題が発生しました。別のMacを使っている方は問題ないようでした。原因わからず……。

GUI Brainf*ckインタプリタの作成

次にMonoDevelopGUI Brainfckのインタプリタを作りました。Brainfckのコマンド(> < + - . , [ ])をそれぞれボタンに割り当てて、ボタンを押すとそのコマンドが実行されるGUIプログラムです。

  • 資料にしたがってGTK#でGUIを組み立てていきます。手順ごとの説明が分かりやすく、最後までつまることなく出来ました。ウィジェットを配置するたびに、その都度テストして動作確認する仕組みになっているので、もし間違っていればその段階で気づくことが出来るようになっています。

GUIが完成したら、次の命令を実行して動作確認しました。

+++++++++[>++++++++<-]>.

ボタンをポチポチ押して、上のプログラムを実行すると H が出力されたらOKです。

f:id:noriok:20120929195603p:plain

PythonでBrainf*ck

次にPythonでBrainf*ckインタプリタを作りました。

プログラム完成後、Hello world!と出力するbrainf*ckプログラムを実行して動作確認。それから勉強会に参加している方からサンプルコードをいただいてその動作確認もしました(ファイルを下さった方のお名前が分かりません。すみません)。

作成したスクリプトは以下です。

PDP-11にチャレンジ

次にPDP-11のバイナリ解析に取り組みました。

などを行いました。

はじめに id:n7shi さんのブログのコマンドライン版インタプリタから開発環境をインストールします。

Cソースを作成します。

main()
{
  printf("hello\n");
}

v6ccでコンパイルすると、a.outが生成されます。fileコマンドでa.outを調べると、PDP-11のバイナリであることが確認できます。

$ v6cc hello.c
$ file a.out
a.out: PDP-11 executable not stripped

実行するには、v6runコマンドを使います。

$ v6run a.out
hello

pdp11-aout-objdumpコマンドで逆アセンブルします。

$ pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11

pdp11-aout-objdump: a.out: ファイルが途切れています

実行すると、上のように「ファイルが途切れています」と表示されます。これは、a.outに含まれるデバッグ情報、シンボル情報の形式が、pdp11-aout-objdumpで扱えないためです。そのため、v6stripでこれらの情報を削除します。

$ v6strip a.out

再びpdp11-aout-objdumpを実行すると、今度は逆アセンブル結果が表示されます。

$ pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	f009           	setd
   2:	1180           	mov	sp, r0
   4:	1226           	mov	(r0), -(sp)
   6:	0bd0           	tst	(r0)+
   8:	1036 0002      	mov	r0, 2(sp)
   c:	09f7 0008      	jsr	pc, 0x18
  10:	100e           	mov	r0, (sp)
  12:	09df 024a      	jsr	pc, *$1112
  16:	8901           	sys	1
  18:	0977 0238      	jsr	r5, 0x254
  1c:	15ce 0270      	mov	$1160, (sp)
  20:	09df 0028      	jsr	pc, *$50
  24:	0077 023a      	jmp	0x262
  28:	0977 0228      	jsr	r5, 0x254
  2c:	e5c6 007e      	sub	$176, sp
  30:	1d77 0004 027c 	mov	4(r5), $0x2b2
  36:	1144           	mov	r5, r4
  38:	65c4 0006      	add	$6, r4
  3c:	9fc0 0272      	movb	*$0x2b2, r0
  40:	0309           	beq	0x54
  42:	0ab7 026c      	inc	$0x2b2
  46:	2017 0025      	cmp	r0, $45
  4a:	0306           	beq	0x58
  4c:	100e           	mov	r0, (sp)
  4e:	09df 01da      	jsr	pc, *$732
  52:	01f4           	br	0x3c
  54:	0077 020a      	jmp	0x262
  58:	0a37 0258      	clr	$0x2b4
  5c:	0a37 0258      	clr	$0x2b8
  60:	afd7 024e 002d 	cmpb	*$0x2b2, $55
  66:	0204           	bne	0x70
  68:	0ab7 0246      	inc	$0x2b2
  6c:	0ab7 0244      	inc	$0x2b4
  70:	08f7 0128      	jsr	r3, 0x19c
  74:	1077 0238      	mov	r1, $0x2b0
  78:	0a37 023a      	clr	$0x2b6
  7c:	2017 002e      	cmp	r0, $56
  80:	0204           	bne	0x8a
  82:	08f7 0116      	jsr	r3, 0x19c
  86:	1077 022e      	mov	r1, $0x2b8
  8a:	1183           	mov	sp, r3
  8c:	65c3 0004      	add	$4, r3
  90:	15c1 0278      	mov	$1170, r1
  94:	1442           	mov	(r1)+, r2
  96:	03da           	beq	0x4c
  98:	2011           	cmp	r0, (r1)+
  9a:	02fc           	bne	0x94
  9c:	004a           	jmp	(r2)
  9e:	1501           	mov	(r4)+, r1
  a0:	0405           	bge	0xac
  a2:	0b01           	neg	r1
  a4:	95d3 002d      	movb	$55, (r3)+
  a8:	0101           	br	0xac
  aa:	1501           	mov	(r4)+, r1
  ac:	09f7 0002      	jsr	pc, 0xb2
  b0:	0152           	br	0x156
  b2:	0a00           	clr	r0
  b4:	7217 000a      	div	$12, r0
  b8:	1066           	mov	r1, -(sp)
  ba:	1001           	mov	r0, r1
  bc:	0302           	beq	0xc2
  be:	09f7 fff0      	jsr	pc, 0xb2
  c2:	1580           	mov	(sp)+, r0
  c4:	65c0 0030      	add	$60, r0
  c8:	9013           	movb	r0, (r3)+
  ca:	0087           	rts	pc
  cc:	9513           	movb	(r4)+, (r3)+
  ce:	0201           	bne	0xd2
  d0:	0ac3           	dec	r3
  d2:	9513           	movb	(r4)+, (r3)+
  d4:	0240           	bne	0x156
  d6:	0ac3           	dec	r3
  d8:	013e           	br	0x156
  da:	1dc1 01da      	mov	$0x2b8, r1
  de:	0a03           	clr	r3
  e0:	1302           	mov	(r4), r2
  e2:	8bd2           	tstb	(r2)+
  e4:	0302           	beq	0xea
  e6:	0a83           	inc	r3
  e8:	7e44           	sob	r1, 0xe2
  ea:	1502           	mov	(r4)+, r2
  ec:	0138           	br	0x15e
  ee:	15c2 02a0      	mov	$1240, r2
  f2:	0102           	br	0xf8
  f4:	15c2 02a4      	mov	$1244, r2
  f8:	1501           	mov	(r4)+, r1
  fa:	0305           	beq	0x106
  fc:	0bf7 01b8      	tst	$0x2b8
 100:	0302           	beq	0x106
 102:	95d3 0030      	movb	$60, (r3)+
 106:	0a00           	clr	r0
 108:	09f7 0002      	jsr	pc, 0x10e
 10c:	0124           	br	0x156
 10e:	1066           	mov	r1, -(sp)
 110:	760a           	ashc	(r2), r0
 112:	0302           	beq	0x118
 114:	09f7 fff6      	jsr	pc, 0x10e
 118:	1580           	mov	(sp)+, r0
 11a:	4c80 0002      	bic	2(r2), r0
 11e:	65c0 0030      	add	$60, r0
 122:	2017 0039      	cmp	r0, $71
 126:	0702           	ble	0x12c
 128:	65c0 0007      	add	$7, r0
 12c:	9013           	movb	r0, (r3)+
 12e:	0087           	rts	pc
 130:	1dc0 0184      	mov	$0x2b8, r0
 134:	1dc2 017e      	mov	$0x2b6, r2
 138:	09f7 0094      	jsr	pc, 0x1d0
 13c:	010c           	br	0x156
 13e:	1dc0 0176      	mov	$0x2b8, r0
 142:	1dc2 0170      	mov	$0x2b6, r2
 146:	09f7 0086      	jsr	pc, 0x1d0
 14a:	0105           	br	0x156
 14c:	1504           	mov	(r4)+, r4
 14e:	1537 0160      	mov	(r4)+, $0x2b2
 152:	0077 fee6      	jmp	0x3c
 156:	1182           	mov	sp, r2
 158:	65c2 0004      	add	$4, r2
 15c:	e083           	sub	r2, r3
 15e:	1126           	mov	r4, -(sp)
 160:	15e6 0020      	mov	$40, -(sp)
 164:	10c4           	mov	r3, r4
 166:	0b03           	neg	r3
 168:	6dc3 0144      	add	$0x2b0, r3
 16c:	0706           	ble	0x17a
 16e:	0bf7 0142      	tst	$0x2b4
 172:	0203           	bne	0x17a
 174:	09df 01da      	jsr	pc, *$732
 178:	7ec3           	sob	r3, 0x174
 17a:	0bc4           	tst	r4
 17c:	0304           	beq	0x186
 17e:	948e           	movb	(r2)+, (sp)
 180:	09df 01da      	jsr	pc, *$732
 184:	7f04           	sob	r4, 0x17e
 186:	0bc3           	tst	r3
 188:	0705           	ble	0x194
 18a:	15ce 0020      	mov	$40, (sp)
 18e:	09df 01da      	jsr	pc, *$732
 192:	7ec3           	sob	r3, 0x18e
 194:	0bd6           	tst	(sp)+
 196:	1584           	mov	(sp)+, r4
 198:	0077 fea0      	jmp	0x3c
 19c:	0a37 0116      	clr	$0x2b6
 1a0:	0a01           	clr	r1
 1a2:	9fc0 010c      	movb	*$0x2b2, r0
 1a6:	0ab7 0108      	inc	$0x2b2
 1aa:	e5c0 0030      	sub	$60, r0
 1ae:	2017 fffa      	cmp	r0, $-6
 1b2:	0202           	bne	0x1b8
 1b4:	1500           	mov	(r4)+, r0
 1b6:	0103           	br	0x1be
 1b8:	2017 0009      	cmp	r0, $11
 1bc:	8206           	bhi	0x1ca
 1be:	0ab7 00f4      	inc	$0x2b6
 1c2:	7057 000a      	mul	$12, r1
 1c6:	6001           	add	r0, r1
 1c8:	01ec           	br	0x1a2
 1ca:	65c0 0030      	add	$60, r0
 1ce:	0083           	rts	r3
 1d0:	65c4 0008      	add	$10, r4
 1d4:	95d3 003f      	movb	$77, (r3)+
 1d8:	0087           	rts	pc
 1da:	1166           	mov	r5, -(sp)
 1dc:	1185           	mov	sp, r5
 1de:	1dc0 00dc      	mov	$0x2be, r0
 1e2:	0204           	bne	0x1ec
 1e4:	09f7 002c      	jsr	pc, 0x214
 1e8:	1dc0 00d2      	mov	$0x2be, r0
 1ec:	9d50 0004      	movb	4(r5), (r0)+
 1f0:	0307           	beq	0x200
 1f2:	0ab7 00c8      	inc	$0x2be
 1f6:	0af7 00c2      	dec	$0x2bc
 1fa:	0602           	bgt	0x200
 1fc:	09f7 0014      	jsr	pc, 0x214
 200:	1d40 0004      	mov	4(r5), r0
 204:	1585           	mov	(sp)+, r5
 206:	0087           	rts	pc
 208:	1166           	mov	r5, -(sp)
 20a:	1185           	mov	sp, r5
 20c:	09f7 0004      	jsr	pc, 0x214
 210:	1585           	mov	(sp)+, r5
 212:	0087           	rts	pc
 214:	1dc0 00a6      	mov	$0x2be, r0
 218:	030a           	beq	0x22e
 21a:	e5c0 02c0      	sub	$1300, r0
 21e:	1037 008a      	mov	r0, $0x2ac
 222:	1dc0 0094      	mov	$0x2ba, r0
 226:	0201           	bne	0x22a
 228:	0a80           	inc	r0
 22a:	8900           	sys	0
 22c:	02a8           	bne	0x17e
 22e:	15f7 02c0 008a 	mov	$1300, $0x2be
 234:	15f7 0200 0082 	mov	$1000, $0x2bc
 23a:	2dd7 007c 0002 	cmp	$0x2ba, $2
 240:	8203           	bhi	0x248
 242:	15f7 0001 0074 	mov	$1, $0x2bc
 248:	0087           	rts	pc
 24a:	1166           	mov	r5, -(sp)
 24c:	1185           	mov	sp, r5
 24e:	1d40 0004      	mov	4(r5), r0
 252:	8901           	sys	1
 254:	1140           	mov	r5, r0
 256:	1185           	mov	sp, r5
 258:	1126           	mov	r4, -(sp)
 25a:	10e6           	mov	r3, -(sp)
 25c:	10a6           	mov	r2, -(sp)
 25e:	0be6           	tst	-(sp)
 260:	0048           	jmp	(r0)
 262:	1141           	mov	r5, r1
 264:	1844           	mov	-(r1), r4
 266:	1843           	mov	-(r1), r3
 268:	1842           	mov	-(r1), r2
 26a:	1146           	mov	r5, sp
 26c:	1585           	mov	(sp)+, r5
 26e:	0087           	rts	pc

helloだけでこれだけの長さ……。printfを使うと引数解析などの処理が必要でコードが長くなるそうです。いきなりこれを理解するのは難しいので、最初は以下のアセンブリコードから取り組みました。

mov $1, r0
sys write
hello
6
mov $0, r0
sys exit

hello: <hello\n\0>

v6asアセンブルすると、a.outが生成されます。

$ v6as hello.s
$ v6run a.out
hello

アセンブルします。

$ v6strip a.out
$ pdp11-aout-objdump -d a.out

a.out:     ファイル形式 a.out-pdp11


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

00000000 <.text>:
   0:	15c0 0000      	mov	$1, r0
   4:	8904           	sys	4
   6:	0010           	.word	20
   8:	0006           	rtt
   a:	15c0 0000      	mov	$0, r0
   e:	8901           	sys	1
  10:	6568           	add	(r5)+, *-(r0)
  12:	6c6c 0a6f      	add	5157(r1), *-(r4)
	…

hello.sには含まれない命令(addなど)が表示されていますが、これは文字列データ(hello)が命令と見なされるため、上のように表示されるのだそうです。

オペコード、レジスタなど他にもいろいろ教えていただきました。自分の中であまり整理と理解が出来ていないので、箇条書きでメモしておきます。

バイナリ形式

  • PDP-11は、a.out形式
  • MacOSXは、Mach-O(マークオー)
  • Windowsは、PE
  • Linuxは、ELF

a.outが出来るまで

.cファイル(C言語) --> .sファイル(アセンブリ言語) --> .o(オブジェクトファイル) --> a.out
              コンパイル                   アセンブル(as)             リンク(ld)

.sから逆アセンブリまでのコマンドを一気に実行

v6as hello.s && v6strip a.out && pdp11-aout-objdump -d a.out

v6src/s5/write.sのソース

/ C library -- write

/ nwritten = write(file, buffer, count);
/
/ nwritten == -1 means error

.globl	_write, cerror

_write:
	mov	r5,-(sp)
	mov	sp,r5
	mov	4(r5),r0
	mov	6(r5),0f
	mov	8(r5),0f+2
	sys	0; 9f
	bec	1f
	jmp	cerror
1:
	mov	(sp)+,r5
	rts	pc
.data
9:
	sys	write; 0:..; ..

更新履歴:

  • (2012-10-28): hello.sのコードを修正しました。
  • (2012-12-02): gistを貼り付けました(bf.py)

Codeforces 110B - B. Lucky String

110B - B. Lucky String

calc :: Int -> String
calc n = take n $ cycle "abcd"

main = do s <- getLine
          putStrLn $ calc $ read s