swfの解析備考録

swfとは

スウィッフと読むそうです、そのまま「エスダブリューエフ」と呼んでました。
FlashPlayerで再生できるファイルです、「おもしろフラッシュ総合サイト」 とかで通じる年代の人には馴染みが深いかと思います。

swfを作成するソフトは沢山あるのですが、昔からあり、as2(action script 2.0)のswfを吐き出すソフトとしては
ParaFla(http://parafla.coaworks.jp/)
があります。 今回はそのサンプルを使って解析が正しく行えるかを試しました。

ActionScriptとは

Flashで画像や音声の制御を行うプログラミング言語です。
今回の解析で主に取り扱うものです。

以下がわかりやすいです。
http://www40.atwiki.jp/spellbound/pages/381.html

swf解析に使った資料、ツールまとめ

このサイトを見れば大体わかります

上記4つは作者、著者が同じ方のように見えます

使ったツール

JPEXS Free Flash Decompilerでデコンパイルが終わらない時(or メモリが溢れる時)

解析時に無限再帰に陥ってstackoverflowするのが原因のようです。
該当箇所のコードが見たいときは左上のチェックを外すと良いです(速度は低下するがエラーでフリーズしなくなる)
flash VMのコード(このツールではP-codeと呼んでいます)だけ見たいときは、デコンパイルを無効にすると早くなるかもしれません。

デコンパイル、タグの解析に使えそうなソース

  • SWF_IO(php,C)
    • 上記の資料で出てきてるので、そちらを参照
  • dumpswf.plx(perl)
    • SWF-File-0.20　というものがあるそうです。

tkbctf2 skillanalyzer write-up

まともに解けたのがこれだけだったので、コンテスト中にとった手順を詳しめに書く

96d4e828f611bdd4e3d2bc45bb9e8a40d59763bb というファイルが落ちてくる
Bzで見てみるとMZスタブ _CorExeMainがあるので windowsの.Netだと分かる

exeを実行してみる

分からない ILを読む(ILspyだとC#では正しく表示されない)

akagiさんmgmgくらいしかまともに分からない
読みやすくするために visual studioでデバッグする

開発者コマンドプロンプトで

ildasm 96d4e828f611bdd4e3d2bc45bb9e8a40d59763bb.exe /OUT=sa.il
ilasm sa.il /DEBUG

と実行すると、デバッグ情報付きのsa.exeが作成でき、
これを visual stdio > 適当なcsharpのプロジェクトの作成 > プロパティ > デバッグ > 外部プログラムの開始

F11のステップ実行で実行すると

こんな感じ

読みにくいけどイミディエイトウィンドウでちょっと遊べる様になる、後ブレークポイントが使えて嬉しい
ローカル変数はV_0,V_1,V_2で番号が振られていて、引数はA_0,A_1と振られており、それぞれイミディエイトウィンドウで使える stackの見方は分からなかったので、知ってる人教えて下さい

"S?[1-7]*" が入力として使えるらしい という事が読んでわかる
しかし暗号の解き方は分からない 文字数と横幅は一致してるので、対応させると解ける？と考えた
Sは先頭しか置けないため "S1234567" に対応している？

先頭から順番に

2
246

157
36
47
6
137
4

3
1

3

S157

が答え？と思って入力するも

はずれ

逆順にすると

S157

3

1
3

4
137
6
47
36
157

246
2


なんか出た 7th danってなんだろう と思ったら音ゲーらしい

You're the 7th dan player!

が答え

ARC12 D - Don’t worry. Be Together

http://arc012.contest.atcoder.jp/tasks/arc012_4

二次元平面上の格子点(x,y) にいる人間が、原点(0,0)に移動したい。
この時、Tターン後に原点にいる移動方法の組み合わせを求めることが出来ればよい。

移動が可能な条件

Tターン後に原点へ移動が可能な条件は、x+y <= T かつ、x+yとTの偶奇が一致している事。
x+y <= Tは明らかとして、x+yとTの偶奇についての証明 無駄に丁寧なのでわかってる人は飛ばしてください

まず1次元で考える。 Txターン後に原点へと移動したい
x軸方向と逆方向の2通りの動き方があり、座標xからそれぞれ(a,b)だけ移動したとすると、移動後の座標は x+a-b となる。
ここで x+a-b = 0,a+b = Tx より a = (Tx-x)/2 , b = (Tx+x)/2
a,bが整数なので、Tx-xは偶数。 以上よりTx,xの偶奇は一致する。

同様に2次元で考える。Tx,Tyをそれぞれx軸,y軸の移動に使用したターン数(Tx + Ty = T)と置くと
上記の証明により、Tx,Tyはそれぞれx,yと偶奇が一致する必要がある。
ここでTとx+yの偶奇が一致しているとすると
i)x,yが奇数 ii) x,yのどちらか一方が奇数 iii) x,yが偶数
の3通りがあり、それぞれ x = 2n(+1) y = 2m(+1)などと置くと証明が可能

以上より、原点(0,0)へと移動可能な条件を求められた。

移動可能な組み合わせ

次に(x,y)から(0,0)へと移動する組み合わせが何通りあるか考える
対称性より、(x,y)から移動を始める場合と(|x|,|y|)から移動を始めた場合では組み合わせの個数は変わらないので、 x,y >= 0とする。

まず簡単な場合としてx+y = Tの時を考える。
この時の組み合わせは _TC_x 通りである。
次に x+y < Tの時を考える。x軸方向を右、y軸方向を上とすると
4方向それぞれに(右,左,上,下) = (a,x+a,b,y+b) ターン動けばよいことが分かる。
ここで、合計のターンがTになるようにa,b(>= 0) を調整する必要がある。
x+y+2(a+b) = Tなので、a+b = T-x-y
m = a+b = (T-x-y)/2置くと (右,左,上,下) = (a,x+a,m-a,y+m-a) と書ける。
以上から、(x,y)から(0,0)へ移動する組み合わせは
\sum^{m}_{a=0}\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!}
これを全ての人間N人について計算すれば答えが出せるが、一人につき最大O(T/2)なのでTLEする
この式を変形するとO(1)？になる。もう少し大きいかも

先ほどの式の \sumの中身は {}_nC_kの積の形で表すことができる。

\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!} = {}_TC_a * {}_{T-a}C_{x+a} * {}_{T-2*a-x}C_{m-a}

ようするにTからa個を選び、残りからx+a個を選び、更に残りからm-a個を選択する組み合わせを表している。
aを減らして \sumの外側に出すことを目標とする。
まずT個からm個を選び、集合をA,Bに分ける。(|A| = m,|B| = T-mとなる)
更に集合Aからa個を選び、集合Bからy+m-a個を選ぶ組み合わせを考えれば、 \sumから一つだけ項を外に出せる
\sum^{m}_{a=0}\frac{T!}{a! * (x+a)! * (m-a)! * (y+m-a)!} = {}_TC_m * \sum^{m}_{a=0} {}_mC_a * {}_{T-m}C_{y+m-a}
大分見やすくなったかもしれない？

さらに、{}_mC_a * {}_{T-m}C_{y+m-a} について考える。
{}_mC_a * {}_{T-m}C_{y+m-a}は、集合Aからa個取り出し、集合Bからy+m-a個を取り出す組み合わせを表している。
このaを、a = 0からmまで変化させた時の全ての組み合わせはつまり、
A+Bの全ての集合から、y+m個の要素を取り出した組み合わせと一致する。
つまり、
\sum^{m}_{a=0} {}_mC_a * {}_{T-m}C_{y+m-a} = {}_TC_{y+m}

以上から、ターンTで(x,y)から(0,0)への移動方法が {}_TC_{m} * {}_TC_{y+m} 通りであることが分かった。
y+m = T-x-mなので、 {}_TC_{m} * {}_TC_{y+m} = {}_TC_{m} * {}_TC_{x+m} どちらを使用しても答えは変わらない

後は、modが素数の時にはmod_invを使用して、解がO(T log(modulo))程度で求められる。
満点解法はmodinvをせずに、n!が何回出てきたのかを記憶して、最後に2^p * 3^q * 5^s * 7^r * ... % modulo をする方法となる。 O(N)程度？
この部分はsubmitされているコードを読んだほうがわかりやすいと思う

#include <cstring>
#include <cmath>
#include <iostream>

using namespace std;
typedef long long ll;

int fractors[100000+10];

ll mod_pow(ll x,ll n,ll mod){
	ll ret = 1,p = x;
	while(n){
		if(n&1){
			ret = ret * p % mod;
		}
		p = p * p % mod;
		n /= 2;
	}
	return ret;
}

bool move(int x,int y,int t){
	//条件は x+y <= t and x+yとtの偶奇が一致していること
	if(x+y <= t && (x+y+t) % 2 == 0){

		//m = (t-x-y) / 2と置くと
		//組み合わせは T_C_(x+m) * T_C_m
		// T_C_(x+m) * T_C_m = (t!)^2 / ( (x+m)! * (t-x-m)! * m! * (t-m)! ) 
		int m = (t-x-y) / 2;

		fractors[t] += 2;
		fractors[x+m]--;
		fractors[t-x-m]--;
		fractors[m]--;
		fractors[t-m]--;

		return true;
	}
	return false;
}

int main(){
	int n,t,mod; cin>>n>>t>>mod;

	for(int i = 0; i < n; i++){
		int x,y; cin>>x>>y;
		if(!move(abs(x),abs(y),t)){
			cout << 0 << endl;
			return 0;
		}
	}

	//階乗をべき乗の形に直す
	static int powers[100000+10] = {};
	for(int i = 100000; i >= 0; i--) powers[i] = powers[i+1] + fractors[i];
	
	ll ans = 1;
	//素数のべき乗を計算する。
	//素数に分解して計算しない場合、a^x (x < 0)を計算する必要が出てきて計算が出来ない
	//ex) 4_C_2 = 4! / (2! * 2!) = 4^1 * 3^1 * 2^(-1) * 1^(-1)
	//0!,1! は無視してよい
	static bool prime[100000+10] = {};
	memset(prime,1,sizeof(prime));
	for(int i = 2; i <= 100000; i++) if(prime[i]){
		ll p = 0;
		//int xにすると、 x = 5*10^4 程度で桁あふれする
		for(ll x = i; x <= 100000; x *= i){
			for(ll y = x; y <= 100000; y += x){
				prime[y] = false;
				p += powers[y];
			}
		}
		ans = ans * mod_pow(i,p,mod) % mod; // i^p
	}

	cout << ans << endl;

	return 0;
}

間違ってたら教えてください。

Chromium Embedded Framework を c# から使う

走り書き

http://code.google.com/p/chromiumembedded/

CEF1とCEF3の二種類があるらしい、CEF2は欠番だとか

  • CEF1 シングルスレッドで動作する CEF3よりも軽くて早い(らしい)
  • CEF3 マルチスレッドで動作する

公式によると、CEF1のC#用bindingが2種類と、CEF3用のbindingが1種類あるそうな。
全部落としてコンパイルしてみたものの、ほとんど手を加えずにコンパイルできたのがCEF3用のxilium.cefglueだけという悲惨な状況だったので、これを使用したいと思います。

CEF3をC#から使用するために、下記サイトからC#用のbindingをダウンロードします
https://bitbucket.org/xilium/xilium.cefglue/wiki/Home

<使用したコンパイラと環境>

windows 7 32bit
Visual studio 2012

gitでcloneするか、Downloads > tags > tip からソースをダウンロード、解凍
ソリューションを開く
windowsだとGtkSharpが存在しないので、CefGlue.GtkSharpのプロジェクトはソリューションから削除、するとコンパイルが通る。
とりあえずデモを動かしたい。

CefGlue.ClientかCefGlue.Demo.WinFormsのどちらを動かせばいいのかわからない…ので
CefGlue.Clientをスタートアッププロジェクトに。

このまま動かそうとするとlibcefがないと言われるので落としてくる、ここで数時間無駄にした…
CEFの公式 http://code.google.com/p/chromiumembedded/ からdllもって来ればいいのかなーと思ってdownloadして、releaseあたりに入っているdllを入れても例外が出る。
原因はライブラリのversionが違うことらしい。
ダメ元でバージョンチェックを外してみたが動かない、ぐぬぬ。
CEFの公式を見ていても、そのようなバージョンのbranchは存在しない、ググっても出ない、一体どこにあるのだ…

CefGlueのホームをよく見ると"Current Xilium's CEF3 builds available on project website."とのこと。
コミットメッセージを読むと、そこにあるXilium CEF3 Buildsの最新版とバージョンが一致している、これを落とせばいいのか…

落とした7zを解凍し、Release以下のdllを参照できるようにする。ここにceflib.dll他、必要なdllが全て入っている
参照の設定が面倒だったので以下のようなコードをMainに追加して動かした。

Environment.SetEnvironmentVariable("Path", <releaseまでのパス>);

これでceflib.dllをロード出来るように。

で、コンパイルして動かす。表示された！

プロセスが2個動いている。どうやら中で実際に動いているブラウザと、MainFormは別プロセスらしい。

使い方がわかったのでもしかしたら何か作るかも、今日はこれでおしまい

追記:

releaseビルドすると動かなかったので原因を確かめたところ、vshost.exeが存在すると動かない様です。

Properties > デバッグ >
で、一番下にある 「Visual Studio ホスティング プロセスを有効にする」のチェックを外しましょう

ハル研究所プログラミングコンテスト2012 工夫した点とか

方針とか

  • 10^6回してみたけど、針を踏まない、開始地点以外で待機しなくてもゴールにたどり着けたので、「針を踏まない方向への移動」 + 「アイテム使用」のみを考えるA*で解いた
  • ゴールまでの距離をBFSで計算して、ヒュースティック値にする
  • memo化する際に、[ゲームのターン数][縦][横][アイテムの残り時間] の配列で保存していたが、

- ゲームのマス目は210でループするので、ターン数が210を超えた時は、 -210してあげても問題ない
- [アイテムの残り時間][縦][横][ゲームのターン数]の方が、キャッシュに乗りやすくて早かった

  • ヒュースティック値と、現在の超過コストをkeyとして、priority_queueに入れて回す。

工夫(高速化)したところ

  • classで実装しているもののほとんどをinline関数に書き換える
  • int,shortを控えてcharにする(2倍は変わる)
  • 関数の引数が4つくらいある場合は、引数をstructかclassにして、const &で渡した方が呼び出しが早くなる
  • charの変数を初期化する際、intにキャストして代入することで、初期化が4倍くらい早くなる
char _penalty[5 + 1][24][24][210];

void init(){
	for(int i = 0; i < 725760 / 4; i += 16){
((int*)_penalty)[i+15] = ((int*)_penalty)[i+14] = ... ((int*)_penalty)[i+0] = 0x70707070;
	}
}
  • 現在いる場所のヒュースティック値と現在の超過コストを比較する際、shortに無理矢理キャストすることで比較演算の速度を上げる

priority_queue使ってたので比較演算の速度を上げると1.5倍くらい早くなった気がする
ただし、ビッグエンディアンなのでソースがローカルとサーバー側で変える必要がある。

こんな感じ

#define FORCE_SHORT(x) (((short *)(void *)&(x))[0])

//サーバと自分のPCではエンディアンが違うので、FORCE_SHORTでの比較が可能になるように変更しておく
struct Result{

#ifdef DEBUG
	char heu;
	char penalty;
#else
	char penalty;
	char heu;
#endif

	short item_time;
	short turn;

	Result(){}

	Result(short turn,short item_time,char penalty,char heu) 
		: turn(turn),item_time(item_time),penalty(penalty),heu(heu) {}
	short Point() const{ return _turnbouns - penalty + _nonStopBouns + 10; }

};

...

inline bool Greater(const Result& l,const Result& r) {
	return FORCE_SHORT(l) < FORCE_SHORT(r);
}

inline bool LessThan(const Result& l,const Result& r) {
	return FORCE_SHORT(l) >= FORCE_SHORT(r);
}
  • forループを展開して書く

よく

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
for(int i = 0 ; i < 4; i++){
    int nx = x + dx[i],ny = y + dy[i];
    call_any_functions();
}

みたいなことをするんですが、

Pos next_pos = cur_pos;
//左
next_pos.x -= 1
call_any_function();
//右
next_pos.x += 2
call_any_function();
//下
next_pos.x -= 1
next_pos.y -= 1
call_any_function();
//上
next_pos.y -= 1
call_any_function();

って要領で書くと早くなった


とりあえず思いつく限り書いてみました

Cから.Net4.0のアセンブリを呼び出す

英語の記事ばかりヒットするので日本語で軽くメモを

http://blogs.msdn.com/b/msdnforum/archive/2010/07/09/use-clr4-hosting-api-to-invoke-net-assembly-from-native-c.aspx にあるサンプルを動かしました。

注意点

All-In-One Code Frameworkから落とせるとあったのですが、なぜか私の環境だと正しく落とせなかった(AssemblyInfo.cs,**.vsproj が含まれてない)ので、
http://code.msdn.microsoft.com/CppHostCLR-e6581ee0
から直接落としましょう(2012/10/13時点)


使用したのはVS2012 RCです、ほかの環境で動くかどうかは試してないので悪しからず


以下メモ 面倒なので整形しない

  • COMの嵐
  • bstr_t variant_t SAFEARRAY楽しいですね
  • CLRCreateInstanceは.Net4.0から新しく追加された方法らしい、CorBindToRuntimeExは非推奨に変わっている
  • #pragma region Includes and Imports の部分は本当におまじないだと思ったほうがいい、 #importは自力じゃ書けない


classにちょっとまとめたら追記するかも