TOP MAP UP

PS2 いちご100%

解析手法の実際 〜何故そう考え、何故そうしたのか〜

※ソフトの使い方はこのページの一番下※

 今回の解析はmixi上で随時細かい記録等を採りながら行った事と、割と難度の高い解析であったので、解決にたどり着くまでに、どう考えどう行動したのかをまとめる事とした。実際に解析する者にとって、一般的な解法などは到底ありえないが、考え方などを参考にしてもらえれば幸いである

 まず参考となる解析元のファイルを示す(このファイルは解析に対する学習用途としてアップしているので、他の用途目的で使用してはならない)
 余談だが、以前にステルヴィアのコンバータでADPCM>WAVコンバータを作っていたので、大きいパッキングファイルから、それぞれの細かいファイルに切り出す機能と、ADPCM>WAVコンバート機能を付けた物を051128に作成した。作業時間はタラタラしながら、まぁ4時間程度だったような気がする

 で、問題となる*.mlhファイルである。以前にざっとファイルの中を見てた限りでは明らかに圧縮がかかっていたので(同時期にステルヴィアを買っていたが)圧縮のかかってない(厳密に言うとかかっているが、簡単な物であった)ステルヴィアの方を先に解析を行った。

 問題はその圧縮方式である。とりあえず拡張子からすると、lhaの派生っぽいような感じなので、zipで圧縮してみた。これはzipでファイルを圧縮し、圧縮率を見ることで、データのコヒーレンシ(?)が高いか低いかをみる事で、huffman符号化が適用されているかを判別しようとしたものである。ちなみにhuffman符号化はデータの出現頻度的に最適化されるので、再度huffman符号化を行ってもほとんど効果がない。で、結果はほとんど圧縮できなかったので、やはりhuffman符号化ではないか?と予測した

 mlh中に更にnbpファイルが(複数)入っており、その中にはフォントファイルだが、無圧縮のnbpファイルもあった。こういった無圧縮ファイルがあれば(同じフォーマットであれば)圧縮方法を考察する上で非常に重要なヒントになる場合がある。全てのファイルに目を通す事は結構重要である。

 それではそろそろ実際にmlhファイルの中身を見てみよう(ただし話のターゲットは以降、その中のnbpファイルについて話すので、特にアドレス関連はnbpの先頭をゼロとする前提なので注意)

 如何に圧縮されたファイルと言えども、ファイルの先頭はベタデータが来る事が多い(これは経験上から来るヒントである。確固たる確証は無い)
 であるので、たまに出てくる0xffが圧縮に関するコントロールコードで、無圧縮の印であり、その後に8byteのベタデータがある事はほぼ間違いないと考えた。

 しかしこの段階ではデータを眺めてもあまりピンと来なかったので、ROM内にあるPS2のプログラムを逆汗して解析するしかないかなと考えた(逆汗も探せばあるのだろうが、自作派なので逆汗も書くつもりだったwww)
 もっとも本当にそんな工数の多い物を書く前に、バイナリを見るのが手っ取り早いので、バイナリを見て見る。みるポイントは、バイナリ内に残る関数名、特徴的な定数リテラル(マジックナンバー)等のデータ、である。
 見てわかったのは、コンシューマ向けなので(変なファイルを扱う必要が無いので)ヘッダチェックとか無さそう、デコード部分はstaticでバインドなので関数名を入れておく必要が無い、0xffみたいなのはマジックナンバーだとしてもあまりに出現頻度が高いためバイナリ中から特定するのは無理、と言う事である(滝汗
 ということでコード方面からの解析は早々にあきらめた。もっとも既にターゲットの逆汗とかあれば、コードを解析したほうが確実な結果を得られるので(少なくともコードをそのまま解釈すれば良いだけで、妙な推測を延々繰り返す必要は無い)そちらの方がお勧めである

 話をnbpに戻そう。先ほどわかったのは、無圧縮データが8byte続いている事だ。つまりひとかたまりが8byteなのである。
 何故8byteなのか?最初は(圧縮が辞書式である場合)履歴となるデータが無いのであるから、表現できる最大の幅でベタデータを表現したいはずである。それが8byteなのである。ということは、かたまりの長さ表現が3bitなのだろうか?
 しかし長さ表現は圧縮性能に大きく影響を与えるはずなので、俺が設計者であれば最低4bitは与えたい。しかしそれが与えられてない。つまりひとかたまりが8byteなのは長さ表現から来る理由ではなく、もっと他の理由から来ているのだ

 とりあえずわかりやすいサンプルを探すために、サイズの大きいファイル=圧縮の係り具合が悪い=ベタデータが沢山のはず、というファイルを眺めてみる事にした(前述のように沢山のファイルに目を通す事は大事である)

 沢山ファイルを見ればピンと来る事もある。ピンと来てわかった事は、コントロールコードはビットで圧縮/無圧縮を表現している、どうもビットが0の場合に圧縮されている、圧縮コードは2byteであるということ(これらはデータを眺めていて直感で想像した事であるので、やはり確証は無い)

 更にデータを眺めていてわかった事は、コントロールコードをビットシフトで判定して、若いアドレス=小さいビット(終り←1111,1111←先頭) という順番である事だ。これでやっと圧縮コードと、ベタコードの区別が付くようになった。

 次は圧縮方式が何なのか?圧縮コードが何を表現しているか?という部分が問題になってくる。
 圧縮方式はまぁいろいろあるが、基本的に圧縮コードは、圧縮してあるので2byteで2byte以上を表現できないとおかしい(当たり前か)
 しかし現段階では基本となる辞書らしき部分は無い(huffmanであるにせよ、ないにせよ)ということは、圧縮コードが参照するデータは、確実にbackward(アドレスが小さい方に向かっての)参照しか無いという事だ(これはデータを見た上での確からしいと思われる類推である。この類推を行うにはある程度圧縮について知識がある必要がある)

 圧縮方式として辞書式・run length式等があるが、この時点で簡単にrun length方式を試してみた。おかしい・おかしくないの判定はnbpファイルの先頭4byteが解凍後の長さであるようなので、この数値を利用してある程度判定できる(もちろんこの時点ではおかしいという判定しか無いw)
 ここで算術的なアプローチとして、src(圧縮データの事)の長さと、dst(展開後)の長さ、圧縮ビットの回数から、大体の圧縮率が算出できる。そういった指標を元に類推を進めていく事となる

 まずは圧縮コードが何を表現してるのかを推測してみる必要がある。そこで、各ニブル(4bit単位)毎に累計等を取って見た(これも算術的アプローチの一つである)
 すると、先頭から順に0000D2D9、0000D78E、0000D37D、00010C90という結果であり、明らかに4番目の性情が違う。また1-3についても圧縮ビット数で割ると大体7になり、これは0-fが偏り無く出現した場合においての平均値と同じである事から、1-3は出現頻度に偏りの無い数値(つまりアドレスを表現しているのではないのか?)であると類推する事ができる。また4番目も消去法で長さを表現しているのではないのか?と類推できる

 次は長さ表現と思われる第4ニブルの各数値の出現頻度をチェックしてみると
 圧縮率の低い物 0:00007F94、1:00000919、2:0000009D、3:00000006、4:00000001、5:00000001、6:00000001、7:00000002、8:00000000、9:00000000、a:00000000、b:00000001、c:00000000、d:00000003、e:00000000、f:00000000
 圧縮率の高い物  0:00000951、1:000003C7、2:00000266、3:000001EC、4:0000013E、5:0000010E、6:000000FC、7:000000EA、8:000000C9、9:000000A8、a:00000091、b:0000008E、c:0000006F、d:00000069、e:00000058、f:00000D2A
 というような結果であった。

  まぁ当たり前と言えば、当たり前であるが、長さ表現である以上、数値が小さい表現が多いほど圧縮が効いてない。逆はその逆である。
 この時点で、srcとdstのサイズはわかっているので、エクセル等でサイズ計算のシート等を作ってみる。理由はこの長さ表現が数値的にリニアである可能性は特に画像系において少ない為(かつてのMAGやPIフォーマットがそうである)いろいろ試行錯誤する為である。
 で、このシート等を活用し、展開されるべき長さを予想しながら、試行錯誤をいろいろ繰り返し実装すると、以下のような画像が出た(mixiは自分のページはjpgでしかアップ出来ないので、リサイズされたjpgとなる。見づらくてスマソ)

 幸いにも、ここで長さ表現については早期に確定出来た(こうもうまく行く事はあまり無いと思う:汗)後は1-3ニブルのアドレスが何をどう表現しているのか?!という解析を行うのみである

 で、アドレス部分もやはりデータを眺めてみるが、どうも3-1-2というニブルの並びで表現されているらしいと言う事以外はピンとは来ない。なので先ほどの長さ部分と同じように算術的アプローチを試みた。

グラフは3-1-2ニブル並びでのそれぞれの数値(つまり0x000-0xfffまで)の出現頻度を数値化したもの。見てわかるように偏りは無い。つまりアドレスはリラティブではなくアブソリュート表現ではないか?という類推が出来る。
 ちなみにこの時点では辞書型の展開であろうと推定して、アドレスをもちいてそれらしい実装をして、いろいろ試行錯誤していた。次の画像はその時の辞書展開を無くした(つまりベタデータのみの展開)画像である

 このあたりから、ファイル先頭においてアドレスが0xfefである参照等があり(要するに見る所が遠すぎて有り得ない)それらは一体どういう意味があるのか?ひょっとするとそれはbackward参照では無いのではないのか?もしかするとnbpファイルの前にあらかじめ辞書のようなファイルをロードしておいて、それを参照しているのではないか?というような泥沼の仮定に基づく試行錯誤が繰り返される(汗

 で、一体何処を参照しているのか?!というのを視覚化する為に作ったのが次の画像

 これは12bitのアドレス表現を>>4して8bitにして、それをグレースケール化したものである。
 注目して欲しいのは、西野の肌あたり(恐らくベタであろうと思われる部分)で周期的な縞模様が出来ている。つまり縞模様=0x000-0xfffまでの周期が繰り返し現れるということであり、縞の境界部分はアドレス表現がそれ以上表現できないが故に切り替わる部分である、というのは類推できる。またそういう数値の部分が、延々データのコピーを行っている部分であるというのも類推できる
 と、まぁそういった類推を重ねるが、それが「何処を見ているのか」の答えにはたどり着かず、ここで更に「forward参照を後で処理する2passデコードではないか」というような泥沼にはまっていくのであった(滝汗
 ちなみにこのあたりで「俺では解けないのかもしれない」とくじけかけている。がんばれ!!俺www

 そして困った時の算術アプローチである(今回はこれが非常に効いた)

 これは「(展開先アドレス-参照アドレス)&0xfff」の各数値の出現頻度表である(ここで参照アドレスと言っているが、何をどう参照しているのかは全くわかってない)
 以前に「アドレスの出現頻度は偏りが無く、アブソリュート表現ではないか?」と推測した。しかし数値をいじる事で(まぁいじり方にもよるわけだが)偏りが発見できた。つまりリラティブな数値であると言えるわけだ。
 しかし一方、グラフの下にべったりと張り付く黒い部分。これはアブソリュートの特性を示している。この相反する二つの特性をどう扱うべきか?
 ここで自分は、辞書式圧縮におけるいわゆる参照ウィンドウが移動する事で、これらの数値の特性が出てくるのではないかと思った(参照ウィンドウが動かない場合、特定ポイントを参照し続けるとどんどん遠くを見ることになり、結果的に前述のような縞模様が出来る)この想定は少なくとも今まで行ってきた類推からすると、とてももっともらしく思える。
 しかしそうであるとするならば、そのウィンドウが動くタイミングはなんなのか?どういうトリガで動くのか?今度はそこが問題になる(とりあえず考えられるのは、アドレス表現が尽きた時、であるが、そんな単純でないのはすぐにわかった:泣)

 愛の力は偉大である。やはり俺のマイフェイバリットキャラであるさつきをターゲットに解析せねば、解ける物も解けないに違いない。と思い、以下の画像(これはPS2のキャプチャ画像で完成予想図)を解析することにした。

 まぁしかし現状は全く改善する気配は見られなかった(滝汗

 この辺りから、かなりまじめに展開のログを取る事にした。
F:00 
c P:00000ED3 X:21B Y:005 D:EC0 L:12 S:00000013 
c P:00000EE5 X:22D Y:005 D:ED2 L:12 S:00000013 
c P:00000EF7 X:23F Y:005 D:EE4 L:12 S:00000013 
c P:00000F09 X:251 Y:005 D:EF6 L:12 S:00000013 
c P:00000F1B X:263 Y:005 D:C91 L:12 S:0000028A 
c P:00000F2D X:275 Y:005 D:F1A L:12 S:00000013 
c P:00000F3F X:00F Y:006 D:F2C L:12 S:00000013 
c P:00000F51 X:021 Y:006 D:F3E L:12 S:00000013 
F:00 
c P:00000F63 X:033 Y:006 D:F50 L:12 S:00000013 
c P:00000F75 X:045 Y:006 D:F62 L:12 S:00000013 
c P:00000F87 X:057 Y:006 D:F74 L:12 S:00000013 
c P:00000F99 X:069 Y:006 D:F86 L:12 S:00000013 
c P:00000FAB X:07B Y:006 D:F98 L:12 S:00000013 
c P:00000FBD X:08D Y:006 D:FAA L:12 S:00000013 
c P:00000FCF X:09F Y:006 D:FBC L:12 S:00000013 
c P:00000FE1 X:0B1 Y:006 D:FCE L:12 S:00000013 
F:00 
c P:00000FF3 X:0C3 Y:006 D:FE0 L:12 S:00000013 
c P:00001005 X:0D5 Y:006 D:FF2 L:12 S:00000013 
c P:00001017 X:0E7 Y:006 D:004 L:12 S:00001013 
c P:00001029 X:0F9 Y:006 D:016 L:12 S:00001013 
c P:0000103B X:10B Y:006 D:028 L:12 S:00001013 
c P:0000104D X:11D Y:006 D:03A L:12 S:00001013 
c P:0000105F X:12F Y:006 D:04C L:12 S:00001013 
c P:00001071 X:141 Y:006 D:406 L:0A S:00000C6B 
F:9D 
u P:0000107B X:14B Y:006 V:42 
c P:0000107C X:14C Y:006 D:6CE L:03 S:000009AE 
u P:0000107F X:14F Y:006 V:36 
u P:00001080 X:150 Y:006 V:50 
u P:00001081 X:151 Y:006 V:77 
c P:00001082 X:152 Y:006 D:19F L:04 S:00000EE3 
c P:00001086 X:156 Y:006 D:68C L:05 S:000009FA 
u P:0000108B X:15B Y:006 V:91 

c/u = compress/uncompress 
P = 処理中のアドレス 
X/Y = 処理中のX/Y dot 
V = uncompressにおけるイミディエイト 
D = compressにおける(多分)distance 
L = compressにおける(多分)length 
S = P-D = compressにおけるコピー元(妄想) 

 注目すべき部分は、Sが常に0x13を参照している、と言う部分で、これは恐らく0x12個続く0であると思われる。P-Dは0x13あるが、実際に何処を見てるのかは依然として不明であるが、とにかくP-D=0x13というのは同じ値のコピーである、というのは画像から見て明白であった(画像系であると、こういう視覚からの類推も非常に重要となる)
 またDが増加するに従い、Sが0x13>0x1013に変化している。しかしこれは恐らく流れから言って同じ所を見ていると判断してよい。またDの増加も、FF2>004と特に造作も無く0x12を足している事から、アドレスの扱いがラップアラウンドではないか?という想定が出来る。つまりなんらかのリングバッファ的な物を使っている可能性がある。

F:1E 
 c P:0001E260 X:098 Y:0C3 D:24D L:12 S:0001E013 
 u P:0001E272 X:0AA Y:0C3 V:00 
 u P:0001E273 X:0AB Y:0C3 V:00 
 u P:0001E274 X:0AC Y:0C3 V:1A 
 u P:0001E275 X:0AD Y:0C3 V:2E 
 c P:0001E276 X:0AE Y:0C3 D:000 L:12 S:0001E276 
 c P:0001E288 X:0C0 Y:0C3 D:275 L:12 S:0001E013 
 c P:0001E29A X:0D2 Y:0C3 D:00F L:04 S:0001E28B 

 D:000となる部分にも注目してみた(参照先のアドレス演算がP-DであるならD=000は有り得ないので、なんらかのヒントとなる可能性があるので)
 リングバッファも実装してみたが、参照してるのは0x12個の0であったりするので、イミディエイトだけをびしびし追加していくリングバッファでは、そのような数列はそもそも発生しない(そんなデータがあったら圧縮する)なので、リングバッファという発想はともかく、プッシュされるのはイミディエイトだけ、というのは明らかにおかしい・・・という事になり、この時点でリングバッファは保留・・・となった。

 またログを眺めている過程で、D:000は存在するが、S:00000012以下は存在しない(エスケープ、あるいは表現上からの制約)、D+L=0xfeeの物がいくつかある(エスケープコードの可能性)ということを発見。何故か? アドレス演算の重要なヒントである事は間違いないと思い、いろいろ考えた
 特に「S=0x13は同じ値のコピーである」という事が重要に思い(それまでは、それが辞書式の圧縮で達成される物と思っていたが)試しにrun圧縮実装してみた。

 (本来はこの画像の一つ前に、もう少し汚い画像があるが、それを見て)どうもrun圧縮じゃないのか?!という思いを強める事となった。
 ちなみに結果から言うと、ここまで綺麗な画像が出たのはかなりの偶然である。だが繰り返す試行錯誤の多大な回数が、その偶然を掴んだ事は必然であるという事は、解析を行うにおいてとても重要な事である。

 ということで偶然ではあるが、S=0x13は直前のデータのrun lengthである、ということまでは、かなりの確信を持てた。となると以前に出てきたS=0x1013とかも結果的には直前のデータを参照しているはずである、という類推が出来る。その類推を実現するにはどういうアドレス演算が必要なのか?
F:00 
c P:00000FF3 X:0C3 Y:006 D:FE0 L:12 S:00000013 
c P:00001005 X:0D5 Y:006 D:FF2 L:12 S:00000013 
c P:00001017 X:0E7 Y:006 D:004 L:12 S:00001013 
c P:00001029 X:0F9 Y:006 D:016 L:12 S:00001013 
c P:0000103B X:10B Y:006 D:028 L:12 S:00001013 
c P:0000104D X:11D Y:006 D:03A L:12 S:00001013 
c P:0000105F X:12F Y:006 D:04C L:12 S:00001013 
c P:00001071 X:141 Y:006 D:406 L:0A S:00000C6B 

 問題部分である(リアルでこの部分を何時間眺めた事か:汗)
 ざっくりわかるのが、上記類推どおりであるならば、DはPの下3ニブルを切り出して表現しているに過ぎない。であるが故に、Dその物はアブソリュートで、かつラップアラウンドな性質を示すわけだ。ということで、P-Dの上位5ニブルを切り出し、Dの下3ニブルと足す事で表現したアドレスでrun圧縮を実装してみた。

 こういうアドレス表現ならば「ファイル先頭においてアドレスが0xfefである参照」も、zero fillする為に敢えてforward参照を行っているのだと、合理的な説明が付く(やっと何処を見てるんだ?!問題が解決)
 しかし、run圧縮のみであると、ファイルのヘッダ部における各種パラメータ(x/yサイズ等)の圧縮の説明が付かない。
 また画像の最初は黒なので恐らく0になる。つまり c P:0000005D X:0CD Y:67B23A D:035 L:09 S:00000028 はゼロを指し示す必要があり、c P:00000066 X:006 Y:000 D:053 L:12 S:00000013 は直前のデータをrunで表現してるのはほぼ間違いないはずである。
 ただ、ここで問題なのは、最初の c P:0000005D X:0CD Y:67B23A D:035 L:09 S:00000028 は、何故長さ9で圧縮をやめる必要があったのか?!ということだ。単なるrun圧縮なら、この圧縮コードの後にも0は続くわけで、わざわざ9で打ち切る必要は無い。 つまり、この圧縮はrun length/辞書圧縮だったのだ!まさか並列で方法を使うとは思っても見なかった。
 そういう確信が持てながらも、やはりrun/辞書の切り替えをどうやって行うのか?は依然として問題となる。であるので、とりあえずわかっている、S=0x13はrun圧縮という部分から、S=0x13かどうかで切り替えてみた。

 良い感じなのだが、画像を良くみるとわかるが、単一色の中が、途切れ途切れになっている部分がある。これはrun圧縮のつもりが、辞書圧縮判定となっているのと、辞書参照先が「まだ描かれていない所を参照している」からである。
 もちろん、run圧縮なら、先頭のみ書かれていれば良い訳で・・・・・。という事は、まだ描かれていない部分を参照する、というのが、run/辞書圧縮の判定の区分けか?!と、ぴこーん!と来て実装すると・・・・。

 やっと来た!キタコレ!長かった!本当に良くがんばった!俺!今は060108だから一月ちょい解析にかかった事になる(もちろんそれを専業にしてるわけじゃないが)
 まぁ残りはPS2の変な配列のパレットを並び替えるのと、PS2はアルファブレンディングの情報もテクスチャに持てるので、ステルヴィアと同じようにアルファ付きBMPとして出力してやればOKである。


 いやー、めがね東城も良いよね!はぁはぁ・・・・・(汗

肝心のソフトの使い方

PS2 いちご100% コンバータはここ
 コンバータはコマンドラインで動くので、まずはDOSプロンプトを起動。
 次に十分に空き容量(GB単位で)のあるディスクに、作業用のフォルダを作成する。ここにコンバータを入れて、このフォルダをカレントディレクトリにする。(コンバータは大体カレントディレクトリにファイルを出力する)

NFPファイルを展開
 コマンドラインで「satuki d:\NCHR.NFP」といった具合に、ゲームのディスクのNFPファイルを指定して実行する(この時結構な数のファイルが出力されるので注意!)展開した後はNFPファイルはいりません

MLHファイルを展開
 コマンドラインで「satuki d:\xxxx.MLH」といった具合に(以下略:w)
 この作業を簡略化する為に、batファイルを同梱しているので、活用して下さい(*1.bat)

NBPファイルをコンバート
 コマンドラインで「satuki ほにゃらら.NBP」といった具合に、NBPファイルをBMPに変換する。(一つのNBPから複数のファイルが出力される場合もあります)展開した後はNBPファイルはいりません。また、この作業を簡略化する為に、batファイルを同梱しているので、活用して下さい(*2.bat)
 ちなみにこのBMPファイルは普通に閲覧可能だが、実はPS2固有の透過ビット情報を含むBMPファイルである。この後の合成作業を完了する前にグラフィックエディタ等でいじると、この透過ビット情報が失われ合成不可になる可能性があるので注意する事。
 またNETC.NFPファイル内のNBPについてはデコードが失敗して、エラーが出るものがあるが、それはこのソフトの仕様なのであきらめる事w

BMPファイル同士をレイヤー合成する
 コマンドラインで「satuki /x右にずらすドット数 /y下にずらすドット数 /b上になるBMPファイル 下になるBMPファイル」といった具合に、BMPファイルを合成する。
 /x,/y共に全く指定がない場合、左下をゼロ点とするポイントに上レイヤーの絵がセットされる(左上でないのはBMPの仕様)
 このコマンドラインのオプションの指定は順番は厳守する事。またオプションとパラメータの間にスペースは入れない。理由はコマンドラインのチェックを手を抜いている為(汗
 上下レイヤーの合成が終わったら、各画像(上下等)の結合はその他のグラフィックエディタ等を使って行う(このソフトでは未サポート)


VASファイルをコンバート
 コマンドラインで「satuki ほにゃらら.VAS」といった具合に、VASファイルをWAVに変換する。(以下略:w)




070509追記
 PS2 ひぐらしのなく頃に 祭の解析結果より圧縮解凍ルーチンの改善を行った結果、以前のバージョンでは正常に解凍できなかった画像についても解凍出来る様になりました(ただし唯一COMPASS.NBPは失敗しますが、これは元のデータが悪いようです)