ICFP2007 (22) 画像修復(1)

ずいぶん間があいてしまいましたが、ICFP2007 (21) 暗号解読(3)の続きです。

ICFP 2007のコンテストの課題は、与えられた画像を修復するパッチ(prefix)を開発することでした。最低でもDNAを解釈してRNAを作るプログラムと、RNAから画像に変換するプログラムを作る必要があります。色々なヒントがDNAの中に隠されていました。

まだ残されているとは思いますが、見つけるのがつらくなってきたので、画像修復をはじめました。今回は現状報告です。

現状の画像です。ターゲットの画像との差分は5799pixelです。prefixは作っていないので長さはわかりません。


ターゲット画像との差分です。


prefixを作るのに主に以下のようなDNAを使います。
- 代入の変更 (!offset)!skip; #0 value;というコードはoffset番地の内容をvalueに書き換える代入文です。skipはvalueのサイズです。このvalueを書き換えると代入する値を書き換えることになります。
- short jump (!skip); ;というコードはプログラムカウンタをskipバイト進めます。
- far jump !gz(!offset(!size))というDNAは他の関数へのjumpになります。gzはGreen Zoneまでのバイト数、offsetは飛び先のGZからのオフセット、sizeは飛び先のサイズ(Red ZoneにロードされたときのGreen Zoneまでのバイト数)です。

mainの中で呼ばれているscenarioという関数が画像表示を行うメイン処理になります。このscenarioの流れに沿って修復箇所を挙げていきます。

(1) sky 空

- night-or-dayをFにする (night_or_dayはGZ+0x50f)。

Pだと夜空になります。night-or-dayをPにするprefixが修復ガイドのpage 1(help_intro)に載っていました。

(9/25 追記 skyから呼び出されるsky-day-bodiesではweatherの値によってcloudsやsunを呼び出すようです。うまくするとprefixの量を削減できそうです。)

(2) surfaceTransform 山

- hillsEnabledをPにする (hillsEnabledはGZ+0x3346a)。
- surfaceTransform()先頭にあるvirusコードをskipします(short jumpを書き込む)。
- 山1のy座標 242 → 218
- 山1のparabolaの第1パラメータ -28 → -21
- 山1のparabolaの第2パラメータ 3348 → 1848
- 山2のy座標 232 → 235
- 山2のparabolaの第1パラメータ -21 → -28
- 山2のparabolaの第2パラメータ 1848 → 3348
- 山3のsineの第2パラメータ 65 → 60

山パラメータの探索には苦労しました。山自体はdrawFunctionBaseという関数で描画しています。drawFunctionBaseのパラメータは関数へのコールバックです。関数は一つ前のy座標との差分を返します。つまり微分されています。山1と山2のコールバック関数はf(x) = a0*x+b0 + sine(a*x+b)*cです。山3はf(x) = sine(a*x+b)*cだけです。実際に描かれるのはf(x)を積分した関数です。関数の仕様はImpDocに書かれています。結果の値は固定小数点になっていて下位12bitが小数部になっています。
山3のパラメータは試行錯誤だけですく見つかりました。山1と山2のパラメータは全然見つかりませんでした。色々試行錯誤しましたが、結局画像を拡大して関数の値を手動で取り出して、結果が一致するようなパラメータを探索するプログラムを書きました。結果としては山1と山2のパラメータが入れ替わっただけでした。探索自体は山1についてしか行っていません。山1のパラメータが分かった時点で山2のパラメータと入れ替わっていることに気づいたからです。描画位置(y座標)だけは自分で調整しました。
virusはDNA全体をscanしてRNAのemptyを書き換えるものです。virusについては修復ガイドのpage 100に書かれています。というか、これ自体は読めませんがvirusの実例が3つもはいっています。

(3) drawGrassPatch 草(川辺を除く)

草は謎が解明しきれていないので力技で描いています。
川沿いの草は別の場所で書いています。drawGrassPatchでは地面の草を描いています。
草単体の描画はgrass1～grass4の4つのルーチンがありますが、drawGrassPatchではgrass1～grass3の3種類のうちのどれかしか描かれません(バグ？)。
草の位置と種類は乱数で決まります。乱数はcryptでも使っているRC4です(initFastRandomとfastRandom)。草の種類を決めるときは乱数の下位2bitをとっているので0～3の値をとりますが、drawGrassPatchの中では1ならgrass1、2ならgrass2、3ならgrass3、4ならgrass4を呼んでいます。乱数が0になったときは何も描かれません。従ってgrass4が呼ばれることはありません。
乱数シードは"El pasto siempre se ve mas verde del otro lado de la cerca."という文字列になっています。さらにdrawGrassPatchの先頭でbioMorphPerturbという配列の内容が要素ごとに加えられてinitFastRandomに渡されています。bioMorphPerturbの中身は最初は0になっています。草の位置と種類の修正には乱数シード(鍵)を見つけるか、bioMorphPerturbに正しい値をセットしてやる必要があります。
怪しいと思っているがbiomorph_adaptationです。これはmainでscenarioが呼ばれる前に呼び出されているadaptationです。adaptationについては修復ガイドのpage 9 (help-adaptive-genes)に、各adaptationの仕様はFuunDocに書かれています。また、help-initial-condにもadaptationのことが書かれていますが、たぶんこれがbiomorph_adaptationのことです。一番最初に呼び出されているadaptationなのでinitial conditionという話に合致しています。調べてみるとbioMul_adaptationは中身がなく乗算するかわりに0を返すだけになっていたりします。このあたりを解明して修復できれば上のbiomorph_perturbという配列の初期化を行ってくれるのではないかと想像していますが、まだできていません。

画像エディタで拡大して一つずつ場所を合わせた草の座標一覧です。何かの影になっていて一部しか見えていないものについては草の種類が間違っているかもしれません。

	grass(3, 444, 332); // 草の種類、x座標、y座標
	grass(1, 496, 402);
	grass(1, 490, 419);
	grass(1, 510, 541);
	grass(1, 470, 554);
	grass(3, 476, 532);
	grass(1, 460, 484);
	grass(1, 426, 373);
	grass(2, 416, 468);
	grass(2, 416, 527);
	grass(1, 386, 365);
	grass(2, 362, 378);
	grass(1, 356, 398);
	grass(2, 346, 355);
	grass(3, 318, 345);
	grass(1, 364, 450);
	grass(2, 338, 546);
	grass(1, 348, 567);
	grass(3, 304, 491);
	grass(2, 286, 531);
	grass(3, 304, 521);
	grass(2, 210, 464);
	grass(2, 222, 479);
	grass(3, 230, 492);
	grass(1, 242, 520);
	grass(1, 118, 381);
	grass(1, 138, 422);
	grass(3, 150, 466);
	grass(3, 222, 396);
	grass(3, 246, 429);
	grass(1,  58, 376);
	grass(2, 134, 323);
	grass(2, 138, 374);
	grass(2, 162, 506);
	grass(1, 114, 563);
	grass(3, 123, 548);
	grass(3,  96, 430);

(4) flowerbed 右下の花

- 花1 (0, 0) <---> 花2 (34, 0)
- 花3 (17, 24) <---> 花4 (58, 12)

座標を入れ替えています。
色はflowerのパラメータなのでパラメータを入れ替えてもいいかもしれません。
このflowerbedの直前にはdead space(実行されないコード)があります。

(5) cargobox 右下の箱

- 8番目のmagentaをyellowに変更 (0x21f12b + 30番地をCFにする)
- 12番目のgreenをblueに変更 (0x21f1ab + 31番地をPにする)

色を修正します。cargoboxはcompressorを使って描画しているのでRNA tableを書き換えます。
色のRNAコードはどれも似ているので書き換える箇所は少ないです。
compressorについては修復ガイドのpage 123456 (help-compression-rna)とpage 1024に書かれています。

(6) motherDuckWithChicks 親子連れのあひる

- 直前のif文でスキップしないようにする (0x4cf3e8番地にIPPを書く)
- 親あひるの描画パラメータ修正 (0x2c932e番地にCを書く)

親あひるを描くmotherDuckという関数はgene tableのintegrity checkにひっかかる(壊れている)関数です。RNAの表示を逐次実行しながらターゲットと比較していくと親あひるの右足がずれているのが分かりました。足はdrawPolygonを使って描画しています。drawPolygonは移動量のx, yをセットにした配列をパラメータとして受け取ります。このパラメータを修正しました。一番最初のx移動量が0になっているのを2にしています。
polygonデータのデータ構造については修復ガイドのpage 8 (help-encodings)に書かれています。polygonデータの最後の2要素は移動量の総和になっているので壊れているデータが分かります。
ちなみに0を2に書き換えるとcheck integrityも通るようになります。

(7) appletree 右のりんごの木

- appletreeからpeartreeへfar jumpする

もしくはappletreeの呼び出しをpeartreeへの呼び出しに書き換えてもいいかもしれません。呼び出しは4箇所あります。appletreeとpeartreeの違いはappleとpearだけなので、appleからpearへfar jumpしてもいいです。どれにするかはprefixのサイズが小さくなるものを選ぶことになるはずです。

(8) chick 右側のひよこ

- skipする
windmill(風車)より後に描かないといけないのでここのコードはskipします。

(9) weeds 左側の枯れた木

- seedを8128にする。

weeds自体はlsystem-weedという関数で描画されています。lsystem-weedでは乱数を使って成長する方向を決めています。seedはrandomInt関数で発生する乱数のシードです。L-Systemについては修復ガイドのpage 5 (help-lsystems)とpage 180878に書かれています。
一番左の木だけを描くプログラムを作って、seedを変えながらターゲットとの差分が最小になるパラメータを探しました。
この8128という数字は4番目の完全数です。修復ガイドのpage 8128 (help-beautiful-numbers)には完全数のことが色々書いてありました。6, 28, 496の最初の3つの完全数も載っていました。実はページ番号自身も4番目の完全数でした。page 8128はlazinessという鍵で暗号化されていました。このページはgoodVibrationsに123を書いても表示されます。
暗号化されているので何か重要な情報が含まれているのではないかと思っていましたが、実は隠していたのはページ番号だったようです。結局、暗号化されているという事実とページ番号だけ分かれば実際に暗号解読する必要はなかったということです。

(10) vmu 中央のcaravan

- vmuCodeを0x1fにする
- vmuRegCodeを"Out_of_Band_II"にする
- 座標を(267, 210)にする

vmuについてはhelp-vmuに書かれています。vmuRegCodeはvmu-codeに書かれていました。vmu-codeは暗号化されていてgiveMeAPresentに暗号鍵OPEを書くことで表示できました。このprefixはalien-lifeformsに描かれています。のりたんさんの情報によるとこのOPEというのは博士の異常な愛情という映画に出てきた暗号キーだそうです。
vmuCodeはvmuを解析して見つけました。0x1f(= 31)だとcaravan、0x33(= 51)だとufo-with-smoke、それ以外だとhelp-vmuが描かれるよいになっています。どこかにヒントがあったのかもしれませんが分かっていません。

(11) windmill 風車

- drawPolylinePolarとmoveToPolarのパラメータ中の角度を全て+5する(いっぱいある)

9/25 追記 ↑のかわりに、polarAngleIncr(0x0c91e0)に5を入れておくだけでいいです。もしくはsetGlobalPolarRotationをパラメータを5にして呼び出してもいいです。setGlobalPolarRotationはpolarAngleIncrにパラメータをセットするだけの関数です。
moveToPolarでは、角度に必ずpolarAngleIncrを加えてから処理をするので、5をセットしておくだけで全ての角度が+5されることになります。polarAngleIncrの初期値は0なので3文字書き込むだけでwindmillが完成することになります。
night-or-dayとpolarAngleIncrの書き換えだけで差分は98904になります。次の76文字のprefixはこの二つを書き換えます。

IIPIPICCCCCIIICICCCPIICICIIPIPIIIICICCIICCIIICIICCPIICCCCIICIPPPPIPPCPFCFIIC
(!3a3e)P(!c8cd0)III; #0F#1CIC;

riskは989116(= 98904*10+76)なのでScoreboardでは25位相当になります。(ここまで追記)

windmillは、羽根の部分の角度だけが違っています。羽根の部分drawPolylinePolarを使って描いています。drawPolylinePolarが受け取るpolygonはdrawPolylineと違って、最初が要素数、2番目以降が(角度、移動量)が並んでいます。角度は相対ではなく絶対なので全ての要素を書き換えてやる必要があります。drawPolylineは5回呼ばれています。順に左上の羽根、右上の羽根、右下の羽根、左下の羽根、軸です。またfillする関係でmoveToPolarで塗りつぶし開始位置に移動していますが、このパラメータの角度も+5してやります。
windmillはcloudyがPのときに変な色になります。cloudyはcloudを呼ぶと(未登場)Pになるのでcloud中の該当箇所をつぶしておく必要があります。他に影響を受けるのは右下の花と、下の文字です。黄色はcolorGermanyYellowという関数の色ですが、この配色はドイツの国旗からきているようです。

cloudy = Pにした画像


windmillより前に描画しなければいけないのは、clouds(雲)です。逆にwindmillより後に描画しなければいけなのはchick(ひよこ)です。

(12) lambda-id 左側の文字

- 不要なのでskipする

長くなってきたので、続きます。