Runtime C++ Editing


x86/x64 最適化勉強会 6 で、実行時 C++ 編集の実装方法について話しました。上はその時の資料です。
私が知ってるいくつかの実装の解説と、DynamicPatcher の実装について解説しています。
あとは最初にこんなもんが必要になるゲーム屋特有の事情についてざっと解説。過去の回で暗号学者の方とかエンコーダを書いてる方の話がすごく興味深かったので、他業種の方がゲーム屋が直面してる問題に興味を持ってもらえたら幸いです。
光成さんによる x86/x64最適化勉強会6 レポート


発表後、shinh さんから SymFromName() の代わりに .map ファイルからシンボル情報を読むアイデアをいただき、実装してみたところ .obj の実行時リンクにかかる時間が大幅に短縮されました。リンクに時間がかかるのが最大の問題だったのが、これでほぼ解決できました。(ありがとうございます)

DynamicPatcher は私自身 atomic 制作で使っていて、boost::serialization で実装した state save/load 機能と組み合わせ、開発モードでゲームを起動すると一定時間置きに自動で state save、改良したい箇所が目についたら遡って一時停止して C++ コードを編集して再開、というサイクルを実現しています。
exception の時は編集するたびにゲームを再起動していたので、当時と比べると大幅な生産力 up です。

raymarching for games

demoscene の世界では近年 raymarching というレンダリング手法がよく用いられています。ポリゴンモデルは使わず、モデルデータは数式の図形としてシェーダコードの中で表現し、pixel shader で図形との距離を求めて可視化していく、というものです。
demoscene (4k/64k intro) の厳しい容量制限の中綺麗な絵を出すために生み出された手法ですが、従来のポリゴンベースの手法では難しい独特の絵を出すことができるという副次的効果があります。

raymarching の代表的な作品群


この手法は PS4 世代以降、小規模ゲーム開発チーム向けの有用なツールになるんじゃないかと考えていて、atomic では試しに背景にこの手法を用いています。以下はその過程や考察です。

まず、raymarching の基本については demoscene.jp の人たちが素晴らしい解説を書いてくれています。
http://www.demoscene.jp/?p=811
raymarching の基本的な図形の式は、iq 氏 (elevated の作者) のサイトにまとめられています。
http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm
上 2 つを知っていればとりあえず raymarching で絵を出すには十分です。
ついでに、folding や fractal など、より高次のテクニックを知りたい人は Mikael H Christensen 氏の記事が役立ちます。
http://blog.hvidtfeldts.net/index.php/2011/06/distance-estimated-3d-fractals-part-i/
また、shadertoy.com や glslsandbox.com には様々な作品が投稿されています。


atomic の背景は非常に単純で、Box の繰り返しと後処理だけで実現されています。順を追って説明すると以下の様な感じです。
atomic_bg0
1. 箱を出す & 距離と ray を march した回数に応じて適当に色を足す (WebGL で実行)
これだけだとよくわからん感じですが、XZ 軸方向の 2 次元 Box です。
ray を march した回数というのは、ray が図形に到達するまで (もしくは打ち切られるまで) にかかった step 数で、オブジェクトの輪郭スレスレを通りつつ交差しなかった場合とかに数が多くなります。この数に応じて色を足すと、4k intro でよく見るオブジェクトの輪郭付近が発光してオーラが出てるようなエフェクトを実現できます。

atomic_bg1
2. 箱を反復させる (WebGL で実行)
平面との and をとって y 方向に空間を作りつつ、折りたたみや mod() で図形を繰り返します。

atomic_bg2
3. もっと反復させる (WebGL で実行)
いい感じに見えるように調整します。

atomic_bg3
4. 箱の位置に乱数を加える (WebGL で実行)
面白く見えるようにします。乱数は位置を hash する方式です。位置をベースにした乱数を使う場合、次の step の正確な距離を予測できなくなるため、ray が図形を突き抜けるケースが出てくることに注意が必要です。(手前のちらついてる部分はそれが原因。誤魔化す方法はありそうな気がしますが、うまくいきませんでした)

atomic_bg4
5. 法線を求め、カメラ->法線の角度が浅いところを光らせる＆輪郭を光らせる (WebGL で実行)
法線は近隣 pixel の位置を求めてその勾配から推測します。普通にライティングしてもいいんですが、かっこよく見えるならそれを最優先です。

atomic_bg6
6. おなじみ光の溝エフェクト＆走査線効果 (WebGL で実行)
あとはなんでもいいのでかっこよく見えるエフェクトをぶちこみましょう


実際にやってみて得られたのは、超人的なプログラムを書かなくても見せ方次第でそれなりに綺麗に見える絵を出すことはできる、という感触でした。
しかし raymarching にも色々デメリットがあります。モデルの形状の融通の効かなさもなかなかツラいですが、一番問題になるのは、重いことだと思われます。pixel shader の中で図形との距離計算を何十回もやることになるため、図形の複雑さと描画面積に比例してすごい勢いで重くなっていきます。

demoscene の場合、容量制限の都合上シェーダレベル以上の最適化はまず行われませんが、ゲームの場合より高次の最適化を行う余地があります。pixel shader が重くなるのは不可避なので、レンダリング解像度を減らす最適化が効果大です。
この手の最適化として代表的なものに adaptive sampling という手法があります。事前に 1/4 とか 1/16 とかの解像度でレンダリングしておき、高解像度でレンダリングする際、低解像度バッファの近隣 pixel が似たような結果であればそれをそのまま使用、そうでなければ真面目に計算する、というものです。
adaptive_sampling1adaptive_sampling2adaptive_sampling3
実際に試してみた図。左: 最適化なし 中央: 最適化あり 右: 1/4 の解像度でレンダリングした領域を赤く表示。品質とのトレードオフになりますが、シーンによっては有用そうな感触です。
他にも、ある程度以上暗いところは低解像度でレンダリングするとか、縦半分の解像度でレンダリングして残り半分は前フレームの結果をインターレースで混ぜて補うとか、ゲーム向けの小細工は色々ありそうな気がします。

また、応用として、deferred 系のレンダリング手法の場合、raymarching で G Buffer だけ書き出してライティングはポリゴンモデルと一括で行う、みたいにすることもできます。raymarching で生成したヘンテコオブジェクトと通常のポリゴンモデルで一貫したライティング処理を行うことができるため、面白い効果を得られるかもしれません。

raymarching のゲームへの応用はまだ前例が少なく、自分も試行錯誤している段階で、成果らしい成果が出せたら今後も経過を書き残していく予定です。

after C84

コミケ参加した方々、お疲れ様でした。

予想外に反響があって、久しぶりにすごく手応えを得られた回になりました。スペースに足を運んでくださった方々、声をかけてくださった方々、ありがとうございました。
ただ、今回マスターデータにソースコード入れ忘れたまま途中まで CD 焼いてしまい、半分くらいはソースコードが入っていないという不手際をやらかしてしまいました。今回パッケージは Web 公開したくない事情があるため、ソースだけここに公開します。(といっても今も github でフルオープン状態なのですが)
https://github.com/i-saint/atomic/archive/C84.zip

今回ので 自機の攻撃行動 (バリア設置とか)、歯車、流体だけ通す/通さない壁、ブラウザから敵キャラ操作 などの基礎ギミックがとりあえず動いたところで、今後はこれらのギミックを応用してステージを作っていきます。
もう少しでレベルエディタなどのコンテンツ量産の仕組みが整うため、冬までにはそこそこ遊べる内容になる予定です。ネットワーク要素にややチャレンジングな内容が含まれるのを考慮すると、完成は冬だとやや厳しくて目標は今年度中、といった感じでしょうか。


exception を出した頃と比べると、同人ゲームでも Unity を使ってマルチプラットフォームの 3D ゲームを出すところが出てきていたり、新興サークルも結構出ていたり、元々開発レベル高かったサークルはますます高くなっていたり、デモ展示を見て「これ iOS でも動きますか？」と聞かれることがあったり (!)、色々な変化が感じ取れます。
しかし、ゲームが好きな人達が、ギリギリまで泥臭い作業を続けて、当日成果を見せ合う、という流れと熱気は今後も変わらないのでしょう。

before C84


またしてもギリギリの告知になってしまいましたが、C84 版 atomic はこんな仕上がりになりました。開発中バージョンにつき 100 円、いつも通りソースコードも同梱です。3日目東ホ-44b primitive。
書き残しておきたい開発記録なんかもいくつかあるのですが、そちらはまた後日。

photo

落雷
雷を撮る、という趣味写真屋としての目標が達成できた一枚。雷雲が接近中だけどまだ雨は降ってきていない、という理想の状況に遭遇し、シャッター時間を限界まで長くして暴風の中雷が落ちそうな方向を 1 時間近く延々撮りまくっていました。
最近 α550 中古で格安で買って、こいつがびっくりするくらい綺麗な絵を出してくれて、近年最も満足度の高い買い物になっている気がします。とはいえ、いい絵を撮るのにもっと重要なのは三脚と根気な気もしなくもないです。

テラス落合
新宿新宿
新宿新宿
夜新宿
新宿
日の出
Nepehthes
紫陽花

function hooking

ここ数ヶ月でいろんな関数 hook を試したのでメモ。Windows でしか試していませんが、x86/64 であれば他のプラットフォームでも同等のことができるはずです。
関数 hook と dll injection は解析/デバッグツールやら動画キャプチャツールの類を作るための基礎技術になります。


・vftable Swapping (sample code)
vftable をすり替えることで virtual 関数を hook する方法。vftable の構造がコンパイラ依存ではあるものの、OS の API などを必要とせずお手軽です。
interface class のみが提供され、実装が dll にある場合 (DirectX とか) この方法が役立ちます。
D3D11 のリソースリークチェッカの実装に用いました。

・vftable Override (sample code)
vftable を直接書き換える方法。vftable Swapping はインスタンス単位で挙動を変えられますが、こちらは class 単位で効果があります。
vftable がある領域は通常 write protect がかかっているため、それを無効化する必要があります。(Windows の VirtualProtect() や POSIX 系 OS の mprotect())

・Import Address Table Override (sample code)
インポートライブラリでリンクされている dll の関数を hook するための方法。
dll から import する関数は実行時までアドレスが決まらないため、exe や dll には import 関数の名前とアドレスを保持する領域 (Import Address Table) があります。この領域にある関数のアドレスを書き換えてやれば任意の関数にリダイレクトさせることができます。
Import Address Table はモジュール (exe,dll) 毎に存在するため、必要なモジュール全てに対して同様の処理をする必要がある点に注意が必要です。
MemoryLeakBuster の実装に用いました。

・Export Address Table Override (sample code)
LoadLibrary() & GetProcAddress() で取得している関数をすり替えるための方法。
dllexport なシンボルがある exe や dll には、export しているシンボルの情報を保持する領域 (Export Address Table) があります。この領域にある関数への相対アドレスを書き換えてやることで、GetProcAddress() の結果を変えることができまs。
WebController の実装に用いました。

・DLL Swapping
dll そのものを入れ替えて関数を入れ替える方法。
Windows は dll の依存を解決する際、カレントディレクトリと環境変数 PATH のディレクトリを見に行きます。このとき同名の dll があればカレントディレクトリのものを優先します。これを利用して、目的の dll と同名の dll を用意して関数を乗っ取るというものです。
例えば opengl32.dll の関数を hook したい場合、元の dll と同じシグネチャの関数を export した opengl32.dll を独自に作成し、exe と同じディレクトリに置くことで、独自 opengl32.dll の方の関数を呼ばせることができます。

・return 1 Override (sample code)
x86 では return で 32 bit 整数 literal を返す処理は 5 byte の命令になります。(例: return 1 -> mov eax, 1 -> B8 01 00 00 00) 5 byte なので任意の関数への call に書き換えることができます。call 先関数が同じ結果を return すれば元の挙動を壊すこともありません。
mov eax, (整数リテラル) を書き換えるというテクニックなので 1 以外にも適用できますが、0 は適応できません。(0 の場合 xor eax, eax になってしまうため)
また、32 bit 未満の整数だと命令も縮んでしまうため適用できません。(組み込み型の bool は 1 byte のため残念ながら適用できません)
WinAPI にはよく BOOL を返す関数がありますが、BOOL は 32 bit 整数であるため、return TRUE してる箇所を hook したい時にこのテクニックが使えるそうです。

・Hotpatch (sample code)
hotpatch という仕組みがあります。これが有効な関数は、先頭に 2 byte の無意味な命令 (mov edi, edi)、関数の前に 5 byte の padding があります。先頭 2 byte を padding 領域への short jmp に書き換え、padding 領域を任意の関数への jmp に書き換えることで、任意の関数へとリダイレクトさせることができます。patch 後も本来のアドレスの 2 byte 先を call すれば元の関数を呼ぶことができます。
VisualC++ ならコンパイルオプション /hotpatch で、gcc や clang だと関数に __attribute__( (ms_hook_prologue) ) をつけることで hotpatch 対応にできます。また、WinAPI は hook したくなるようなものは大抵対応してたりします。
x64 の場合は注意が必要で、x84 と違って先頭 2 byte は無意味な命令にはなりません。つまり、元のアドレスの 2 byte 先を call で patch 前の関数を呼べるようにはなっていません。(関数の先頭が 2 byte 以上の命令であることしか保証されていないそうです) このため、x64 で元の関数を呼べるようにしつつ hook したい場合、後述の MHook style hook を使う必要があります。
hotpatch は w_o さんに存在を教えて頂き、id:NyaRuRu さんに x64 での仕様などの詳細教えて頂きました。感謝。

・MHook style hook (sample code : 説明用。命令の解釈いい加減なので MHook 使った方がいいです)
MHook がやっている方式の hook です。
関数の先頭 5 byte を hook 先への jmp に書き換え、元の 5 byte を含む命令はどこか別の場所に移して後ろに元の場所への jmp を加えておく (=これを call すれば patch 前の関数が実行される)、というものです。
関数先頭の書き換えだけなら簡単で、元の関数を呼ぶ必要がないならそれで事足りるのですが、元の 5 byte を含む命令を移すのはかなりの重労働になります。x86/64 は命令が可変長なので、命令を正しく解釈して必要なサイズを求めないといけません。その命令に相対アドレスが含まれる場合はつなぎ変え処理までやる必要があります。
実装は大変なものの、極めて汎用性が高い方法です。逆に言うと、virtual 関数でも dllimport/export 関数でもなく hotpatch にも対応していない場合はこれ以外選択肢がありません。
DynamicPatcher はこの方法を用いていますが、x86 の命令の解釈は外部ライブラリ tDisasm を用いました。(MHook がそれを使っていたのを真似た)


vftable 書き換え系以外は、x64 の場合に相対アドレスが 32bit に収まらないケースへの対処が必要になります。
具体的には 32bit 範囲内のどこかにトランポリンコードを用意して jmp 先をそこにします。任意のアドレスへのメモリ割り当ては VirtualAlloc() で行い、トランポリンコードは FF 25 00 00 00 00 [hook 先へのポインタ 8byte] の 14 byte でいけます (これも MHook から学びました)。

WebController


WebController

ブラウザからゲームを操作するツールをしばらく前に作りました。主にモバイル機器から Wii U コントローラ的にゲームを操作するのを目的としたものです。
上の動画は Nexus7 から REVOLVER360 RE:ACTOR (C83) を遠隔操作しているところ。見ての通り既存のゲームをソースレベルの変更なしで操作できています。


やってることは、対象ゲームのプロセスに dll を注入して HTTP サーバーを立て、入力 API を乗っ取ってブラウザから送られて来た入力データで結果を差し替える、というものです。
HTTP サーバーはいつも通り Poco のおかげでとても楽に実装できました。
dll の注入については 過去 に書いた CreateRemoteThread() で LoadLibraryA() 呼ばせる方法そのままです。プロセス起動直後に注入する必要があるため、suspend モードでプロセスを起動して dll を注入してから実行を継続させるランチャーを用意する必要がありました。

入力 API を乗っ取る処理が今回面白かったところです。
今回はコントローラだけを扱い、入力 API は XInput、DirectInput、winmm (joyGetPosEx()) の 3 つを想定しています。これらは dll であり、インポートライブラリでリンクされていれば、実行時にメモリにマップされた exe の import address table を書き換えることで簡単に関数を hook できます。(MemoryLeakBuster の時に触れた方法)

しかし、LoadLibrary() & GetProcAddress() で実行時に関数を取得している場合はこれが通用しません。そして入力 API では互換性のためにこの手順が取られることがしばしばあります。(XInput -> DirectInput -> winmm の順で使えるものを試すというもの)
対策は 2 通り考えられます。1 つは入力 API の dll の export address table を書き換える方法。もう 1 つは GetProcAddress() 自体を書き換える方法です。大抵はどっちでも上手くいくと思われますが、GetProcAddress() は使わないケースがありうるため、今回はより抜本的な前者を使いました。
dll や exe には export している関数のリスト (export address table) もあり、これを書き換えれば GetProcAddress() の結果も変わります。このため、LoadLibary を hook して、ロードしようとしてるのが XInput や DirectInput の dll であればロード直後に export address table を書き換える、という手順で乗っ取ることができます。

template<class T>
inline void ForceWrite(T &dst, const T &src)
{
    DWORD old_flag;
    ::VirtualProtect(&dst, sizeof(T), PAGE_EXECUTE_READWRITE, &old_flag);
    dst = src;
    ::VirtualProtect(&dst, sizeof(T), old_flag, &old_flag);
}

// dll が export している関数 (への RVA) を書き換える。これにより GetProcAddress() が返す関数をすり替える。
// すり替え前の関数へのポインタを返す。
inline void* OverrideDLLExport(HMODULE module, const char *funcname, void *replacement)
{
    if(!module) { return nullptr; }

    size_t ImageBase = (size_t)module;
    PIMAGE_DOS_HEADER pDosHeader = (PIMAGE_DOS_HEADER)ImageBase;
    if(pDosHeader->e_magic!=IMAGE_DOS_SIGNATURE) { return nullptr; }

    PIMAGE_NT_HEADERS pNTHeader = (PIMAGE_NT_HEADERS)(ImageBase + pDosHeader->e_lfanew);
    DWORD RVAExports = pNTHeader->OptionalHeader.DataDirectory[IMAGE_DIRECTORY_ENTRY_EXPORT].VirtualAddress;
    if(RVAExports==0) { return nullptr; }

    IMAGE_EXPORT_DIRECTORY *pExportDirectory = (IMAGE_EXPORT_DIRECTORY *)(ImageBase + RVAExports);
    DWORD *RVANames = (DWORD*)(ImageBase+pExportDirectory->AddressOfNames);
    WORD *RVANameOrdinals = (WORD*)(ImageBase+pExportDirectory->AddressOfNameOrdinals);
    DWORD *RVAFunctions = (DWORD*)(ImageBase+pExportDirectory->AddressOfFunctions);
    for(DWORD i=0; i<pExportDirectory->NumberOfFunctions; ++i) {
        char *pName = (char*)(ImageBase+RVANames[i]);
        if(strcmp(pName, funcname)==0) {
            void *before = (void*)(ImageBase+RVAFunctions[RVANameOrdinals[i]]);
            ForceWrite<DWORD>(RVAFunctions[RVANameOrdinals[i]], (DWORD)replacement - ImageBase); // x64 だとトランポリン挟む必要が出てくるかもしれないので注意
            return before;
        }
    }
    return nullptr;
}

void example()
{
    OverrideDLLExport(::GetModuleHandle("xinput1_3.dll"), "XInputGetState", &fake_XInputGetState));
}

余談ですが、C# (というか CLR) の場合、dll は LoadLibrary()&GetProcAddress() 相当の方法でロード＆リンクされるようです。このときロードには LoadLibraryExW() が使われるので注意が必要です。当初非 Ex の A/W を見てて捕捉できず悩みました…。また、LoadLibrary A,W,ExA は全て内部的に ExW を呼ぶようになっているようです。


Wii U コントローラのように画面をストリーミング動画で転送したりもしたかったんですが、当分検証する余裕がなさそうで今回は未実装です。
画面のキャプチャ自体はそこまで難しくないことがわかっていて、画面更新の API (OpenGL の wglSwapBuffers() とか) を hook して更新直後のフレームバッファを取得し、動画用 API (Video for Windows や DirectShow) に流しこめば実現できます。(.kkapture がこれをやっていて、ソースも公開していて参考になります)
それをストリーミングしてブラウザでゲームプレイに耐える遅延で再生できるのかについては未知数です。
PC 同士であれば、描画 API を乗っ取ってクライアント側にリダイレクトさせるようにし、描画処理を全部クライアント側でやらせる、みたいなアプローチも考えられます。このへんは応用範囲が広そうで妄想だけは広がります。