深さ優先探索によるトポロジカルソート
トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。
入力辺がないノードをキュー 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)
- 作者: 青柳隆宏
- 出版社/メーカー: 技術評論社
- 発売日: 2013/01/08
- メディア: 単行本（ソフトカバー）
- クリック: 1,072回
- この商品を含むブログ (1件) を見る
勉強会後にやったこと
7shiさんのv6runソースをGNU GLOBALで読む。
id:n7shiさんのv6runをGNU 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
pdp11-aout-objdumpの出力結果は、8, 10, 16進数が混ざっていて混乱するので、自作の逆アセンブラでは、8, 10, 16進数にはプレフィックス(0x, 0o)を付けました。- オペコードはPDP-11の資料を見ながら一つ一つ解析しています。
- PDP-11の資料は、UNIXv6 ハードウェア資料 - 驟雨のカーネル探検隊（只今遭難中ｗ で紹介されているものを参考にしています。
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冊の本を紹介していただきました。
- 作者: John R. Levine,榊原一矢,ポジティブエッジ
- 出版社/メーカー: オーム社
- 発売日: 2001/09
- メディア: 単行本
- 購入: 7人 クリック: 171回
- この商品を含むブログ (54件) を見る
Lions’ Commentary on UNIX (Ascii books)
- 作者: ジョンライオンズ,John Lions,岩本信一
- 出版社/メーカー: アスキー
- 発売日: 1998/07
- メディア: 単行本
- 購入: 12人 クリック: 627回
- この商品を含むブログ (27件) を見る
『Lions’ Commentary on UNIX (Ascii books)』は、さっそく購入しました。
池袋バイナリ勉強会(2)に参加してきました
9月23日(日)に池袋バイナリ勉強会(2)に参加してきました。
MonoDevelopでHello 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 ();
}
ボタンを押すと、以下のようにメッセージダイアログが表示されます。
躓いたところ:
- なぜかぼくのMacBook(OS X 10.8.2)では、MonoDevelop(バージョン 3.0.4.7)上で縦棒「|」を入力すると、MonoDevelop上では閉じ括弧「}」が入力されてしまう問題が発生しました。別のMacを使っている方は問題ないようでした。原因わからず……。
GUI Brainf*ckインタプリタの作成
次にMonoDevelopでGUI Brainfckのインタプリタを作りました。Brainfckのコマンド(> < + - . , [ ])をそれぞれボタンに割り当てて、ボタンを押すとそのコマンドが実行されるGUIプログラムです。
- 資料にしたがってGTK#でGUIを組み立てていきます。手順ごとの説明が分かりやすく、最後までつまることなく出来ました。ウィジェットを配置するたびに、その都度テストして動作確認する仕組みになっているので、もし間違っていればその段階で気づくことが出来るようになっています。
GUIが完成したら、次の命令を実行して動作確認しました。
+++++++++[>++++++++<-]>.
ボタンをポチポチ押して、上のプログラムを実行すると H が出力されたらOKです。
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)が命令と見なされるため、上のように表示されるのだそうです。
オペコード、レジスタなど他にもいろいろ教えていただきました。自分の中であまり整理と理解が出来ていないので、箇条書きでメモしておきます。
バイナリ形式
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
calc :: Int -> String calc n = take n $ cycle "abcd" main = do s <- getLine putStrLn $ calc $ read s
