Sim's blog

電子工作はじめてみました

ICFP2007 (25) Steganography

2007-09-30 02:13:19 | ICFPプログラミングコンテスト
ICFP2007 (24) 画像修復(3)の続きです。

修復ガイドのpage 3にはsteganographyのことが書かれていました。steganographyは、画像に秘密を埋め込む技術ということのようです。暗号と違うのは鍵に相当するデータがないので隠し方自体が鍵になっていることです。


二つの絵のうち左側が右側に隠されていると書かれています。左側の絵は右側の絵のLSBとして埋め込まれていました。

各RGB値についてLSBが1のとき0xff、0のとき0x00に変換した画像です。


なんか目がチカチカしますが、埋め込まれているのが分かると思います。

他にもないか探してみました。修復ガイドのpage 112です。


同じようにLSBだけ取り出してみました。


ETのいた辺りに何か文字があるのが見えます。拡大してみます。


cow-tailの暗号鍵の9546がこんなところに隠されていました。
ページ番号の112ですが、海外では緊急通報用の電話番号だそうです。日本の110番みたいなものでしょうか。

LSBではありませんが、黄色の文字を読んでいくとprefixになっているものもあります。過去10年間のICFPの紹介です。

[contest-1998] IIP


[contset-1999] IFFCPICPF


[contest-2000] FIICPIIC


[contest-2001] IPPPI


[contest-2002] CIIC


つなげるとhillsEnabled(0x03346a)をFからPに変えるprefixになっています。
IIPIFFCPICPFFIICPIICIPPPICIIC
(?IFPFCC)F; #0P;

prefixが埋め込まれているのは2003までですが、この紹介自体は2007年まであります。ついでなので載せておきます。
[contest-2003]


[contest-2004]


[contest-2005]


[contest-2006]


[contest-2007]


最多優勝はOCaml(1999, 2000, 2002)とHaskell(2001, 2004, 2005)の3回です。さすがにFunctional Programmingの学会ということでしょうか。
コメント

ICFP2007 (24) 画像修復(3)

2007-09-27 00:21:34 | ICFPプログラミングコンテスト
ICFP2007 (23) 画像修復(2)の続きです。

最新の画像です。


差分です。3594ピクセル異なっています。


(17) balloon ふきだし

- 修復方法が不明なのでとりあえずskip

(18) 文字列

- 0x4d6606にgoto 0x4d60fbを書く
- 0x4d6316から"s morphed!xff"を書く

文字列を書くのに微妙にメモリが足りません。直前にドイツ風の"Endo hat gemorpht"を表示するコードがあるので、色をセットし終わったら、そちらに飛ばしてやります。

ここまでで、scenarioに沿った修正はおわりです。足りない部分を追加します。どこにどう追加するとprefixが短くなるのかはよく分かっていません

コードを追加するのに使える隙間は以下です。
- sky-day-bodies
- grassの後からflowerbedまで
- chick (ここまでがwindmillより前)
- lambda-id (ここまでがwhaleより前)
- crater
- 文字列からreturnまで

追加するものは以下です。
- sun(太陽)
- clouds(雲) windmillより前
- chick(ひよこ) windmillより後
- 鯨の噴水 whaleより前
- 鯨のcup whaleより後
- balloon(ふきだし)

(19) sunの修復

- [0x206dce + 855] = I
- [0x207192 + 15] = I
- [0x207192 + 47] = C
- [0x207269 + 87] = I
- [0x207269 + 95] = C
- [0x207269 + 176] = C
- [0x207336 + 7] = I
- [0x207336 + 81] = I
- [0x207336 + 104] = C
- [0x2073cc + 49] = C
- 太陽の座標を(480, 20)にする
- 太陽の色はcolorSoftYellow()
- [0x641878 + 48] = 530 (spirograph5 x)
- [0x6418c4 + 48] = 70 (spirograph5 y)
- [0x641a0a + 48] = 1 (spirograph5 magnify)
- [0x641f81 + 48] = 530 (spirograph6 x)
- [0x641fcd + 48] = 70 (spirograph6 y)
- [0x642113 + 48] = 1 (spirograph6 magnify)
- [0x642694 + 48] = 530 (spirograph7 x)
- [0x6426e0 + 48, 24, 70] (spirograph7 y)
- [0x642826 + 48, 24, 1] (spirograph6 magnify)
- spirograph描画後、適当なreturnへjumpする

前半はsunの修復です。これはダンプリストを見ながら手動でおかしな所を直してみました。修正しては逆アセンブルしなおしを繰り返しました。10箇所修正したところでcheckIntegrityもpassになりました。
後半はspirographのパラメータ修正です。これは修復ガイドのpage 180878の中央のspirographです。太陽の中央にはこのspirographを縮小したものが描かれています。page 180878はmainの一部に埋め込まれています。
太陽の色はcolorSoftYellow()です。この色はflowerbedで使われている色と一緒です。sun()ではYellowなので色を修正する必要があります。sunの直前はimpDoc1なので壊しても構わないので、ここが利用できます。

sun自体はsky-day-bodiesの中で呼ばれています。sky-day-bodiesはおおまかにこんな感じになっています。
void sky-day-bodies()
{
    if(weather == 2){
        if(weather == 2) lightningBolt();
        clouds();
    }
    if(weather == 3) sun();
}

一番最初のifを3と比較することにすればcloudsとsunが呼ばれることになります。weatherの初期値は0なのでweather = 3にするとよいことになります。

(20) clouds

- duolcの逆順をcloudにコピーする
- cloud先頭のcloudy = PをFにする
- [0x5c9164] = 25 (雲1 y座標)
- [0x5c963d] = 10 (雲2 サイズ)
- [0x5c94fa] = 55 (雲2 y座標)
- [0x5c99dd] = 20 (雲2 サイズ)
- [0x5c989a] = 30 (雲3 y座標)

cloudとduolcを連結すると回文になっています。cloudは壊れているのですが、duolcから復元できます。回文に関するヒントはpage 1230321です(修復したpage 1230321)。ページ番号も回文になっています。
cloudのパラメータは雲の大きさです。デフォルトは15になっています。

(21) chick (ひよこ)

- 座標を(171, 410)にする

windmillより後に描画しないといけません。パラメータはcolorDuckYellowとcolorDuckOrangeです。scenarioの中ではchick呼び出しの前後に隙間はないのですが、サブルーチンコールでスタックに戻り番地を積む所を飛ばしたい番地に修正することで呼び出し順序を変えることができます。どのように直すのが最適かはまだ分かっていません。

(22) 噴水

- 座標を(430, 200)にする
- compressorのtableの7番目をturnClockwiseにする([0x29bdda + 26] = FFFFF)
- compressorのtableの9番目をturnCounterClockwiseにする([0x29be1a + 26] = CCCCC)
- 描画しおわったら適当なreturnへjumpする

噴水はprintGeneTableのpage 15以降に隠されていました(右下)。このままでは上下さかさまなのでcompressorのturnClockwiseとturnCounterClockwiseのRNAを入れ替えてやります。
whaleより前に描画する必要があります。

(23) cup (暫定)

- waterの座標を(420, 265)にする
- water(), addbmpのRNA, 完全にopaqueなufo-cup(), clip, 通常のufo-cup()の順に呼び出す
- ufo-cupのpolygonはx座標とy座標を両方とも符号を反転させる
- fillのためのmoveToも座標の符号を反転させる
- ufo-cupの座標は(477, 315)

ターゲットの鯨はcupの中の水に浮いている絵になっています。waterをufo-cupの逆さまでclipした後、半透明なufo-cupを上書きすることで絵が完成します。ufo-cupはx方向にもy方向にも反転しています。一応x座標とy座標を両方とも符号反転することで描画しています。時計回りに2回方向を変えることでも実現できるはずですが、まだ試していません。DNAの中では、現在の描画位置をいくつRNAを出力したかを元に追跡しています。DNAの知らない所で向きを変えたり座標を変えたりすると、追跡している座標と実際の座標が矛盾して、それ以降の描画がずれてしまいます。これはとても危険なので安全策として座標反転をしています。後でダミーのmoveをすることで座標のつじつまを合わせることも可能なはずなので、RNAを直接挿入した方がprefixが短くなるはずです。
ufoの中にはufo-cupと同じpolygonが2つも含まれています。それもwaterを呼び出した直後です。ufoの中身をいじくってやることで今回の絵がうまくつくれそうです。
waterは通常は描画されませんがweaterが1または2のときにだけ描画されるようになっています。waterの存在はweatherをいじくって遊んでいるときに気づきました。というかufoの中に隠されていたということになります。

weather = 2にした画像です。雨や雷、ufo-cupに波模様が見えます。


(24) balloon (ふきだし)

balloonの修正方法は分かっていません。少なくとも単一の白ではなくグラデーションがかかっています。グラデーションはdrawGradientCornerNWを使って描かれています。drawGradientCornerNW自体は四角を書くだけなのでふきだしの形でclipしてやる必要があります。グラデーションのパラメータwとhと描画位置のx, yが未知です。またclip用のふきだしの形も分かりません。力技でpolygonデータを作るしかないのかもしれません。もしかするとどこかにヒントになる図形が隠されているかもしれません。
μの描画方法も分かりません。λはフォントを変えてLを書いています。他の文字に変えると表示されるのかもしれません。
もう残っているのはballoonだけです。

以上で修正箇所のまとめをおわります。宿題として残っているのは以下です。
- 草を描く乱数の修正値biomorphPerturbを決めるbiomorph_adaptationの修正
- 座標を符号反転させないufo-cupの描画方法とufoの修正方法
- balloonのグラデーションパラメータと形状
- 追加描画部分はどこに置くのがよいか考える
- prefixの作成と圧縮(というかアセンブラ作らなきゃ)
- ヒントの探索。例えばcow-tailの暗号化鍵9546

その他に思いつくことはサブルーチンコールの戻り番地の修正でfar jumpを作ることができるので、これを利用できないか考えることです。

ずいぶん長いこと、しつこくやっていましたが、ようやっと終わりが見えてきたという感じです。10月になるとICFPの学会が開催されて上位入賞者の発表があります。もしかするとネタバレもあるかもしれません。どうせなら、その前に片付けておきたいところです。
コメント

PSoC FirstTouch

2007-09-25 20:32:26 | PSoC
PSoC FirstTouchというUSB接続の小型マイコンボードが発売されているようです(日経の記事)。静電容量式タッチ・センサや近接センサ、光センサ、温度センサなんてことが書いてあります。

eZ340やくもちゃんのライバルということになるのでしょうか。センサがあるということだとMSP430入門セミナー2007で配っていた容量センサー付eZ430の方が本当のライバルっぽいです。

パステルマジックさんは4000円ですが売り切れています。

そういえばSTR9-comStickはどうなったんでしょう。

コメント

ICFP2007 (23) 画像修復(2)

2007-09-25 03:15:15 | ICFPプログラミングコンテスト
ICFP2007 (22) 画像修復(1)の続きです。

(13) river 左下の川

- 0x71c897をmkGoldfishR_adaptationにする (a)
- 0x71c9ffをmkGoldfishL_adaptationにする (b)
- 0x71cb67をmkGoldfishR_adaptationにする (c)
- 0x71cc3fを18にする (d)
- 0x71cd17をmkGoldfishL_adaptationにする (e)
- 0x71cec7をmkGoldfishL_adaptationにする (f)
- 0x71cf0fをmkGoldfishR_adaptationにする (g)

川を修正する必要はありませんが川の中の魚を修正します。魚はdrawGoldenFish_adaptationで描かれています。この中のgoldenFish_adaptationを修正することになります。adaptationについては修復ガイドのpage 9に書かれています。各adaptationについてはFuunDocに書かれています。

goldenFish_adaptationを逆アセンブルした結果です。段付けは手動です。パラメータで一段深くしています。最初の方はmkBeforeAbove(mkEmp(0x14, 0x14), mkBeforeAbove(...))のように解釈できます。

goldenFish_adaptation 71c66f 0008d0

71c66f 0008a0
    71c687 activateAdaptationTree
    71c69f mkBeforeAbove_adaptation
    71c6b7 0000c0
        71c6cf activateAdaptationTree
        71c6e7 mkEmp_adaptation
        71c6ff 000030
            71c717 intBox
            71c72f 000014
        71c747 000030
            71c75f intBox
            71c777 000014
    71c78f 000780
        71c7a7 activateAdaptationTree
        71c7bf mkBeforeAbove_adaptation
        71c7d7 000390
            71c7ef activateAdaptationTree
            71c807 mkAbove_adaptation
            71c81f 0001e0
                71c837 activateAdaptationTree
                71c84f mkBeforeAbove_adaptation
                71c867 000030
                    71c87f activateAdaptationTree
                    71c897 mkGoldfishL_adaptation ← (a) mkGoldfishR_adaptation
                71c8af 000150
                    71c8c7 activateAdaptationTree
                    71c8df mkBeforeAbove_adaptation
                    71c8f7 0000c0
                        71c90f activateAdaptationTree
                        71c927 mkEmp_adaptation
                        71c93f 000030
                            71c957 intBox
                            71c96f 7ffffe
                        71c987 000030
                            71c99f intBox
                            71c9b7 7fffff
                    71c9cf 000030
                        71c9e7 activateAdaptationTree
                        71c9ff mkGoldfishR_adaptation ← (b) mkGoldfishL_adaptation
            71ca17 000150
                71ca2f activateAdaptationTree
                71ca47 mkBeforeAbove_adaptation
                71ca5f 0000c0
                    71ca77 activateAdaptationTree
                    71ca8f mkEmp_adaptation
                    71caa7 000030
                        71cabf intBox
                        71cad7 00002d
                    71caef 000030
                        71cb07 intBox
                        71cb1f 000018
                71cb37 000030
                    71cb4f activateAdaptationTree
                    71cb67 mkGoldfishL_adaptation ← (c) mkGoldfishR_adaptation
        71cb7f 000390
            71cb97 activateAdaptationTree
            71cbaf mkBeforeAbove_adaptation
            71cbc7 0000c0
                71cbdf activateAdaptationTree
                71cbf7 mkEmp_adaptation
                71cc0f 000030
                    71cc27 intBox
                    71cc3f 000000 ← (d) 0x12
                71cc57 000030
                    71cc6f intBox
                    71cc87 000018
            71cc9f 000270
                71ccb7 activateAdaptationTree
                71cccf mkAbove_adaptation
                71cce7 000030
                    71ccff activateAdaptationTree
                    71cd17 mkGoldfishR_adaptation ← (e) mkGoldfishL_adaptation
                71cd2f 0001e0
                    71cd47 activateAdaptationTree
                    71cd5f mkBeforeAbove_adaptation
                    71cd77 0000c0
                        71cd8f activateAdaptationTree
                        71cda7 mkEmp_adaptation
                        71cdbf 000030
                            71cdd7 intBox
                            71cdef 000019
                        71ce07 000030
                            71ce1f intBox
                            71ce37 00001d
                    71ce4f 0000c0
                        71ce67 activateAdaptationTree
                        71ce7f threeFish_adaptation
                        71ce97 000030
                            71ceaf activateAdaptationTree
                            71cec7 mkGoldfishR_adaptation ← (f) mkGoldfishL_adaptation
                        71cedf 000030
                            71cef7 activateAdaptationTree
                            71cf0f emptyBox_adaptation ← (g) mkGoldfishR_adaptation
71cf27 00c662

(14) whale 鯨

- if文の条件を反転する (0x266585にIPPを書く)
- 座標を(410, 200)にする

噴水はwhaleより前に描く必要があります。またcupはwhaleより後に描く必要があります。噴水とcupについては後で記します。
whaleのパラメータは2つのboolです。1番目が表情でPで泣き顔、Fで笑顔です。2番目は使用されていません。if文の条件を反転することで笑顔にしています。ifを書き換えるかわりに呼び出し時の第1パラメータを書き換える手も考えられます。

(15) crater

- 不要なのでskipする

(16) bmu endoさん

- enableBiomorphをPにする (enableBiomorphはGZ+0x033963)
- weather判定と変なRNAをskip (0x0dafadにgoto 0x0db0fbを書く)
- 変なrnaとendocowをskip (0x0df476にgoto 0x0df78cを書く)
- cow-spot-middleの誤り訂正 (correctErrors(0x0d985b, 0x000b34, 0x0da3a7))
- cow-tailの復号 (crypt("9546", 0x4aa77d, 0x00145c))
- cow-tailの色修正 addOpaqueを7個、addTransparentを3個追加
- cow-tailのintegrity checkをskip

enableBiomorphはPにしなくても、ifをskipするだけでもいいです。次でweather判定をskipしているので統合した方がprefixが短くなります(0x0daee5にgoto 0x0db0fbを書く)。
cow-tailは復号しただけだと不透明です。0.3だけ透明にします。cow-tailの最初でbucketをemptyにするRNAコードがあるので、これをつぶしてやります。そうするとintegrity checkが通らなくなるので、integrity checkもskipします。今はintegrity checkの所に透明化用のRNA出力を上書きしています。integrity checkはそのままでcow-tailの途中に飛び込む手もありますが、透明化コードを置く場所に困ります。既存のコードで再利用できそうな部分を探すとよいかもしれません。このあたりはもうちょっと考えた方がよさそうです。

暗号化については修復ガイドのpage 4405829に書かれています(このページの復号結果はここです)。cow-tailの暗号鍵9546は力技で発見しました。どこかにヒントがありそうですが見つかっていません。完全数というわけでもなく謎です。もしかすると特徴のない最小の数かもしれません(笑)。
誤り訂正符号については修復ガイドのpage 84に書かれています(このページは暗号化されていて鍵は42でした)。

bmuはおおまかに以下のような流れになっています。
void bmu(void)
{
    if(enableBioMorph == P){
        if(weather == 1 || weather == 2){
            cowを描く
            endocow();
        } else if(ducksShown == P){
            superDuck();
        } else if(ocamlrules == P){
            ocaml();
        } else {
            mlephant();
        }
    } else {
        endo();
    }
}

各変数の初期値は
enableBioMorph(0x033963) = F
weather(0x03394b) = 0
ducksShown(0x033964) = F
ocamlrules(0x0c9228) = P
です。ducksShownはscenarioの中でmotherDuckWithChicksを呼び出す直前でPが代入されています。値を変えると色々な画像が見れます。

endocowにしたときの画像です。


superDuckです。


ocamlです。


mlephantです。


endoです。


長くなってきたので続きます。
コメント

ICFP2007 (22) 画像修復(1)

2007-09-24 16:13:44 | ICFPプログラミングコンテスト
ずいぶん間があいてしまいましたが、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する

長くなってきたので、続きます。
コメント

Microsoft Extension

2007-09-18 23:25:29 | その他
ICFPの方もいよいよ画像の修復に取りかかっていますが、なかなか進みません。

C言語の標準はISOとかJISで決まっています。標準ではないのですが使ってて便利だと思った方言というか、Microsoft独自仕様をいくつか紹介します。

(1) 名前なしのunion(struct)メンバー

正式にはなんというのか知りません。普通unionのメンバーには必ず名前をつけます。
union {
    struct {
        char a, b;
    } x;
    int y;
} u;

例えば、これだとメンバーはu.x.a、u.x.b、u.yの3つです。名前なしの場合はstructのxを省略できます。
union {
    struct {
        char a, b;
    };
    int y;
} u;

この場合、u.a、u.b、u.yのようにアクセスできます。.xを省略できるわけです。structでも、あいまいにならない限りは同じことができます。

あくまで方言なので、あまり使っていいものではないと思いますが、ついつい使ってしまいます。どういう時に使うかというと、最初の3つはメンバーが同じだけど、残りが違うみたいなときに使います。
struct header { ... };

struct type1 {
    struct header;
    残り1
};

struct type2 {
    struct header;
    残り2
};

みたいな感じです。

(2) 長さ0の配列

Cでは長さ0の配列は許されないことになっています。int a[0]みたいなのです。
これは、可変長データを作るときに使っています。
typedef struct {
    int size;
    char s[0];
} header;

例えば、長さの後にcharが可変長続くみたいなデータのヘッダです。データを格納する領域自体はmallocで取りますが、ポインタを一回経由しなくていいので便利です。
メモリ確保はheader *p = (header *)malloc(sizeof(header) + サイズ);みたいなかんじです。データへのアクセスはp->sizeとp->sみたいな感じになります。
javaだと最初からあります。byte a = new byte[サイズ]とすれば、a.lengthでサイズが取れるサイズ可変配列になります。
長さ0配列を使わないとすると
typedef struct {
    int size;
    char *s;
} header;

のように配列側をポインタにします。この場合、ヘッダとデータはメモリとして連続しないことになります。

長さ0にこだわらなくても、とりあえず1ということにしておくのもありですが、実際に長さが0のときに無駄なメモリが必要なことになります。

(3) SEH

これはwindowsの構造化例外ハンドラという仕組みです。__try節の後に必ず__finally節が実行されることが保証されています(たぶん)。リソースの確実な解放を行うために使っています。
FILE *fp = NULL;
char *p = NULL;

__try {
    fp = fopen(ほにゃ);
    if(fp == NULL) __leave;

    p = malloc(うにゃ);
    if(p == NULL) __leave;
}
__finally {
    if(fp != NULL) fclose(fp);
    if(p != NULL) free(p);
}

上の例だと__try節の中でファイルとメモリを確保して、__finally節で解放しています。__try節から脱出するときは必ず__finally節を実行します。例えばreturnしても__finally節は実行されます。
また、普通のCコードだとmallocに失敗したときはfcloseしてからreturnするとかしないといけませんが、エラー処理というかif ~ returnが出てくるたびにリソース解放するのは面倒です。
    if(p != NULL){
        fclose(fp);
        return;
    }

一応、gotoを使えば同じようなことができます。

というわけで、悪の道は甘い蜜の味ということで、ついつい使ってしまう方言を紹介してみました。可変配列については、C99だとmallocを使わなくても作れるということみたいですが、手持ちのコンパイラ(VC++6.0)はもちろん対応していません。
コメント

ICFP2007 (21) 暗号解読(3)

2007-09-13 00:43:58 | ICFPプログラミングコンテスト
ICFP2007 (20) 暗号解読(2)の続きです。

caravanの復号方法が分かりました。これはvmuという関数を読んでいて分かったのですが、caravanはvmuRegCodeを鍵として暗号化されていました。
以前張った画像ですが、このOut_of_Band_IIが鍵でした。最後が読みづらかったのですが、何通りか試してみたところI(アイ)でした。(書きながら思ったのが、vmu-codeは復号できるのだからソースを読めばよかったんですね。)



caravanは修復する画像の真ん中あたりにある車(?)です。画像修復には、鍵による復号は必須ではなくて、各部品は暗号化されていないので自分で並べてやってもいいです。ただし、その分prefixが長くなるので鍵で復号した方がいいです。vmuという関数はvmuMode=1fのときにvmuRegCodeを使ってcaravanを復号して表示するようになっています。



help-activating-genesですが、cryptを使って暗号化しているわけではなく、シーザー暗号でした。ICFPを各々FPICと2文字ずらすと復号できました。page 23になります。



サブルーチンコールの仕組みとかが書かれています。最後に書かれているのはadaptationの話です。dnaの中にはインタプリタみたいなのがあって、コード化されたプログラムを逐次実行するみたいなことができます。具体的にはint24がひたすら並んでいて、各々がコマンドだったりパラメータだったりします。FuunDocに書かれているのがadaptationの各コマンドの概要です。正確に言うとインタプリタとも違うような気もしますが、直接実行されるわけではないところがインタプリタ風です。FuunDoc自体はHaskell風に書いてあります。

最後はcow-tailです。鍵は"9546"でした。javaのプログラムは遅かったので結局Cで書き直してなんとか見つかりました。解読の実行時間は3964.95秒(1時間6分)でした。



プログラムは長くなるので貼りませんが、おおまかに次のような流れです。

- 先頭を2バイト分復号してみる
- 正しく復号できていたら次に進む。だめなら次の鍵にする
- 最後の方まで復号していって、最後の固定パターンが正しく復号できているか調べる。
- 正しく復号されていたら出力しておわり。だめなら次の鍵にして最初に戻る

プログラムの先頭の10文字とプログラムの最後の75文字の平文が既知です。1文字が2ビットなので先頭は2バイトと2ビットしか分かっていないことになります。20ビットくらいだと、偽鍵が大量に発生します。つまり、正しくない鍵でも20ビットくらいならたまたま復号できてしまうこともあります。最初は偽鍵が嫌だったので最後の固定パターンを使って鍵探索していましたが、最後まで復号するのは時間がかかります。しかたないので最初のパターンでふるいにかけたものについてだけ最後まで復号するというように方針を変更しました。

これ以上鍵が長いとさすがにPCでの探索もつらいものがあります。アルゴリズムもそんなに複雑ではないのでFPGAを使って並列探索とかするとよいかもしれません。ブロックRAMを使うとすると24並列とか平気でできそうです。これはおもしろそうなので今後の課題です。
コメント

ICFP2007 (20) 暗号解読(2)

2007-09-10 20:38:20 | ICFPプログラミングコンテスト
ICFP2007 (19) 誤り訂正符号の続きです。

DNAの暗号解読は遅くてたまらないのでjavaでcrypt互換ルーチンを作っていました。
mainの中で配列に初期値として入っている値はhelp-beautiful-numbersを復号する本当の鍵とgoodVibrationsだけずれています。goodVibrationsを0から順に増やして鍵探索を行いました。正しく復号できれば、正解ですが、復号できたかどうかはcheckIntegrityを使って判定しています。

探索部分はこんな感じです。
void crackGoodVibrations(){
    int i, gb;
    byte[] ks = {
        (byte)0xd8, (byte)0xc6, (byte)0xee, (byte)0xce,
        (byte)0xda, (byte)0xca, (byte)0xe7, (byte)0xe7
   };
    boolean found = false;

    for(gb = 0; gb <256; gb++){
結果、123が出力されました(16進だと7b)。さっそくgoodVibrationsに123を入れて動かしてみるとhelp-beautiful-numbersが見れました。カタログのpage 8128になります。このページはページ番号を指定しなくてもgoodVibrationsに正しい値を入れておくだけで自動的に見れます。
本当の鍵はlazinessということになります。



完全数のことなんかが書いてあります。博士の愛した数式に出てきました。ラマヌジャンの名前もあります。1729は自然数の3乗の和として2通りに表せる最小の数だそうです(1729 = 12^3+1^3 = 10^3+9^3)。苦労したわりにはあまり役に立つ情報ではないような気もします。わざわざ赤字で書いてあるところはパスワード候補ということでチェックです。

暗号化されている関数で残っているのはcaravan、cow-tail、help-activating-genesです。今まで分かっている暗号化の鍵では復号できませんでした(含む今回の赤字)。関数の終わりはどれも同じパターンであることを利用すれば解読できそうです。もしくは先頭のパターンも分かっている(RNA出力)ので、そこを利用することもできます。とりあえず解読プログラムをのろのろ書き始めました。
関数以外にもデータの方にまだ暗号化されているものが残されているかもしれません。

javaのbyteは-128~127なのでcastしないと0xd6とかが代入できません。なんか面倒です。javaでもprintfが使えるようになったのは便利です。Eclipseには高級なデバッグ機能があるのに、あいかわらずprintfデバッグをしています。
コメント

ICFP2007 (19) 誤り訂正符号

2007-09-06 21:52:57 | ICFPプログラミングコンテスト
CFP2007 (18) 暗号解読の続きです。

鍵が分かったので復号してみました。


復号に使ったprefixです。
IIPIFFCPICFPPICIICIPCCCPIICIPPPCCFCFCFIICIIPIIPIPCICIICCIIICPIICIPCICCCCIICCCIII
CCICIICCCPIICIICIPPCPCCCFFCFFCFFFCFFCCCCCCCCICFFCCFFFFCCFFCCFFCFCCCCFICCCFCFFCFI
CCFCCFFCFICFFFFFFFFICIPPPIICIPCCCCICIICICICCPIIPIPICCCIIIIICICIICCCCIIICPIIPIPIC
CCIIIIICICPIICIPCICIIIICCIIIIICCICCCIICPIICIICIPPPIPPCPCFFFCFCCFCFFFCCFFCFFCCFIC
CFCCCCCCCCCCFCFCCCCCCCCICFCFCCCFCFCCFFFCCFCFCCCFICCCCCCFCCFFCCCCCCCCCCCCCICIIC

helpScreen = 84;
crypt("42", help-error-correcting-codes, 0x006ed8);
startup();

8-4ハミング符号なんて書いてあります。correctErrorsという関数を調べてみました。impdocには

void correctErros(int24 data, int24 ecc, int24 size)
Correct errors in a DNA region using the Hamming bits in another DNA region.

と書かれています。dataとeccは同じ長さで各々2文字づつ処理します。dataから取り出した2文字とeccから取り出した2文字を連結して下の表を引いた結果の2文字をdataに書き戻します。??になっているのは、誤り訂正能力を超えていて何に戻せばいいのか分からないところです。IIIIからPPPPまでで4^4 = 256通りあります。
IIII→II	IIIC→II	IIIF→II	IIIP→??	IICI→II	IICC→??	IICF→??	IICP→IF
IIFI→II	IIFC→??	IIFF→??	IIFP→CI	IIPI→??	IIPC→FI	IIPF→IC	IIPP→??
ICII→II	ICIC→??	ICIF→??	ICIP→FC	ICCI→??	ICCC→CC	ICCF→IC	ICCP→??
ICFI→??	ICFC→IP	ICFF→IC	ICFP→??	ICPI→IC	ICPC→??	ICPF→IC	ICPP→IC
IFII→II	IFIC→??	IFIF→??	IFIP→IF	IFCI→??	IFCC→IF	IFCF→IF	IFCP→IF
IFFI→??	IFFC→IP	IFFF→FF	IFFP→??	IFPI→CF	IFPC→??	IFPF→??	IFPP→IF
IPII→??	IPIC→IP	IPIF→CP	IPIP→??	IPCI→FP	IPCC→??	IPCF→??	IPCP→IF
IPFI→IP	IPFC→IP	IPFF→??	IPFP→IP	IPPI→??	IPPC→IP	IPPF→IC	IPPP→??
CIII→II	CIIC→??	CIIF→??	CIIP→CI	CICI→??	CICC→CC	CICF→PI	CICP→??
CIFI→??	CIFC→CI	CIFF→CI	CIFP→CI	CIPI→CF	CIPC→??	CIPF→??	CIPP→CI
CCII→??	CCIC→CC	CCIF→CP	CCIP→??	CCCI→CC	CCCC→CC	CCCF→??	CCCP→CC
CCFI→PC	CCFC→??	CCFF→??	CCFP→CI	CCPI→??	CCPC→CC	CCPF→IC	CCPP→??
CFII→??	CFIC→PF	CFIF→CP	CFIP→??	CFCI→CF	CFCC→??	CFCF→??	CFCP→IF
CFFI→CF	CFFC→??	CFFF→??	CFFP→CI	CFPI→CF	CFPC→CF	CFPF→CF	CFPP→??
CPII→CP	CPIC→??	CPIF→CP	CPIP→CP	CPCI→??	CPCC→CC	CPCF→CP	CPCP→??
CPFI→??	CPFC→IP	CPFF→CP	CPFP→??	CPPI→CF	CPPC→??	CPPF→??	CPPP→PP
FIII→II	FIIC→??	FIIF→??	FIIP→FC	FICI→??	FICC→FI	FICF→PI	FICP→??
FIFI→??	FIFC→FI	FIFF→FF	FIFP→??	FIPI→FI	FIPC→FI	FIPF→??	FIPP→FI
FCII→??	FCIC→FC	FCIF→FC	FCIP→FC	FCCI→FP	FCCC→??	FCCF→??	FCCP→FC
FCFI→PC	FCFC→??	FCFF→??	FCFP→FC	FCPI→??	FCPC→FI	FCPF→IC	FCPP→??
FFII→??	FFIC→PF	FFIF→FF	FFIP→??	FFCI→FP	FFCC→??	FFCF→??	FFCP→IF
FFFI→FF	FFFC→??	FFFF→FF	FFFP→FF	FFPI→??	FFPC→FI	FFPF→FF	FFPP→??
FPII→FP	FPIC→??	FPIF→??	FPIP→FC	FPCI→FP	FPCC→FP	FPCF→FP	FPCP→??
FPFI→??	FPFC→IP	FPFF→FF	FPFP→??	FPPI→FP	FPPC→??	FPPF→??	FPPP→PP
PIII→??	PIIC→PF	PIIF→PI	PIIP→??	PICI→PI	PICC→??	PICF→PI	PICP→PI
PIFI→PC	PIFC→??	PIFF→??	PIFP→CI	PIPI→??	PIPC→FI	PIPF→PI	PIPP→??
PCII→PC	PCIC→??	PCIF→??	PCIP→FC	PCCI→??	PCCC→CC	PCCF→PI	PCCP→??
PCFI→PC	PCFC→PC	PCFF→PC	PCFP→??	PCPI→PC	PCPC→??	PCPF→??	PCPP→PP
PFII→PF	PFIC→PF	PFIF→??	PFIP→PF	PFCI→??	PFCC→PF	PFCF→PI	PFCP→??
PFFI→??	PFFC→PF	PFFF→FF	PFFP→??	PFPI→CF	PFPC→??	PFPF→??	PFPP→PP
PPII→??	PPIC→PF	PPIF→CP	PPIP→??	PPCI→FP	PPCC→??	PPCF→??	PPCP→PP
PPFI→PC	PPFC→??	PPFF→??	PPFP→PP	PPPI→??	PPPC→PP	PPPF→PP	PPPP→PP

cow-spot-middleをcow-spot-middle-eccを使って誤り訂正できました。integrity checkはpassになりました。

色々な仕掛けがしてあります。
コメント

ICFP2007 (18) 暗号解読

2007-09-05 22:58:57 | ICFPプログラミングコンテスト
ICFP2007 (17) help-palindromesの修復の続きです。

crackKeyAndPrintという関数にpurchase codeを渡してやると暗号解読して鍵を表示してくれます。purchase codeはint24の0(III・・・IIP)を暗号化したものなので、端から順に試していけば鍵が分かるという仕組みです。purchase codeは3つ分かっています。

一つ目はhelp-error-correcting-codes_purchase_codeを解読したものです。


やたら時間がかかります。たった2桁を解読するのに56122457回(5612万2457回)の繰り返しで157.562秒かかりました。

2つ目はvmu-code_purchase_codeです。これの鍵はICFP2007 (10) gene tableの修復で見つけたOPEです。答えは分かっていますが実行してみます。


これは恐ろしく時間がかかりました。繰り返しが1965822242回(19億6582万2242回)で実行時間は5379.296秒です。ほぼ1時間半です。

最後のhelp-beautiful-numbers_purchase_codeはICFP2007 (9) mainの逆アセンブルの結果からすると8桁なので調べるのは無謀っぽいのでやっていません。暗号アルゴリズムがRC4と分かっているのでgoodVibrationsを00-ffと変える方が速そうです。

ところで、crackKeyAndPrint関数の最初では背景と同じ黒い文字で「Harry Potter and the Orion Slave Girls. Out *now* on Arcturus III.」というメッセージを出力しています。これもまた新たな謎です。どこかに使う鍵なのかもしれません。ハリーポッターシリーズの最新作のタイトルでしょうか。Orion Slave Girlsというのはエンタープライズのオリオンシンジゲートと何か関係があったりするのでしょうか?

crackKeyAndPrintを動かすためのprefixです。
// パラメータをスタックに積む
// (!36f1c(!18)!6f5c6e)
IIPIPIICCCIIICCCCICCICCIIIIIPIIPIPIIICCPIICIPICCCICCIIICCCICICCCCICCPIICIIC
// #1#0
IPPCPIPPPIIC
// サブルーチンコール(init)
// !352f(!23ca0e(!a0e)!4ec185)
IPCCCCICIICICICCPIIPIPICCCIIIIICICIICCCCIIICPIIPIPICCCIIIIICICPIIC
IPCICIIIICCIIIIICCICCCIICPIICIIC
// #0#1
IPPPIPPCP
// CIICICCIIICICIICIICCICCP crackKeyAndPrint番地
// ICCICIIIICCICIIIIIIIIIIP 同サイズ
// CCCCIIIIICCCIICIICIIICIP terminate番地
// ICICIIICCIIIIIIIIIIIIIIP 同サイズ
FCCFCFFCCCFCFCCFCCFFCFFIC
CFFCFCCCCFFCFCCCCCCCCCCIC
FFFFCCCCCFFFCCFCCFCCCFCIC
CFCFCCCFFCCCCCCCCCCCCCCIC
IIC

スタックにパラメータを積んでからinitをcallしています。initの戻り番地としてcrackKeyAndPrint、crackKeyAndPrintの戻り番地としてterminateを積んでいます。戻り番地をどんどん積んでおくことでサブルーチンの連続callを一回のcallで済ませることができます。
コメント

ICFP2007 (17) help-palindromesの修復

2007-09-02 23:30:34 | ICFPプログラミングコンテスト
ICFP2007 (16) トレースRNAのエンコードの続きです。

mainを逆アセンブルしてその存在が分かったpage 1230321です。元の画像は文字がどんどんフェードアウトして先が読めなくなっていました。調べてみると意外と簡単に文字が読めました。



元の画像です。


drawStringは文字の色を外部の関数にまかせます。事前にcharColorCallbackに関数へのポインタをセットしておきます。help-palindromesではfadingColorsという関数をセットしていました。これをcolorWhiteに換えただけです。
実際にcharColorCallbackに設定する命令はGZ+6571dfです。テンプレート中に設定する関数の番地があります。GZ+657210が関数の番地、657229が関数のサイズです。

palindromeというのは回文のことです。「竹やぶ焼けた」みたくさかさまから読んでも同じになる文です。最後のパラグラフが意味深です。誤り訂正をするための冗長部分として回文が利用できるみたいなことが書いてあります。壊れているcloudとduolcを連結すると回文になっているということみたいです。ちょうどサイズも同じです。
9/3 追記 cloudの記述を変更

サイズが同じというとcow-middle-spotとcow-middle-spot-ecc、sunとsunflowerも同じサイズです。
コメント

ICFP2007 (16) トレースRNAのエンコード

2007-09-01 23:04:33 | ICFPプログラミングコンテスト
ICFP2007 (15) Fuun Security Featuresの続きです

ICFP 2007関連が増えてきたのでカテゴリーを新設しました。

8/28に関数の最初でCから始まるユニークな無効RNAを出力していることに気づきました。関連する話は以前載せたpage 2181889 (help-undocumented-rna)にも書いてあります。



このトレース用RNAのエンコードが分かりました。RNAなので全部で7文字、先頭はCに固定です。残りの6文字はCを0、Iを1、Pを2とした3進数になっています。関数はアドレス順に通し番号がついています。以下のようになっています。
0ca6fa 00127e CCCCCCC(0) endo-left-arm
0cb990 000876 CICCCCC(1) cow-right-horn
0cc21e 00ae91 CPCCCCC(2) contest-2005
0d70c7 0021ce CCICCCC(3) smoke
0d92ad 000596 CIICCCC(4) colorDuckBrown
・・・
6f9e01 000ba3 CCPICCI(258) sky-day-bodies

途中で番号が飛んでいることがあります。原因は暗号化されていたり壊れているときか、データのときです。欠番は9個ありました。実際は番号はついていませんが前後の関係から決めてかっこの中に記しました。
0da3a7 000b34 (6)   cow-spot-middle-ecc    (データ?)
0e5d10 007e2d (10)  help-beautiful-numbers (暗号化)
20742f 0006e0 (25)  sunflower              (データ?)
213563 0080f4 (28)  vmu-code               (暗号化)
2bc2cb 00c0eb (80)  help-activating-genes  (暗号化?)
42ccf3 006ed8 (119) help-error-correcting-codes (暗号化)
4aa77d 00145c (144) cow-tail               (暗号化?)
5706a4 001365 (185) caravan                (暗号化?)
61181e 001962 (218) duolc                  (データ?)

gene tableのintegrity checkでfailと表示されるものでもちゃんと番号がついているものもあります。cloud(212), cow-spot-middle(5), help-virus(219), motherDuck(82), sun(24), surfaceTransform(240)です。これらは暗号化されていなくて、先頭は壊れていなくて、途中から壊れているものと思われます。

gene tableに載っていない関数も3つありました。gene tableをアドレスでソースすると隙間が空いていて、関数番号もついていて、最後にchecksumもついています。
453945 000338 CCCCPIC(135)  startup() ???
58ccac 00131f CPCCIPC(191)  drawInt() ???
58faf2 00018a CPICIPC(194)  colorYellow() ???

この表のサイズはchecksumの分も含まれているので実際の関数のサイズは24を引いた値になります。一番上のものは一番最初に実行される関数です。次はprintGeneTableでページ番号を書いています。最後もprintGeneTable内で使われています。charColorCallBackに設定しているので色関係です。impdocに載っていてgene tableには載っていないcolorYellowだと思われます。
コメント