060 ファイル復活にトライ（５日目）
●060 ファイル復活にトライ（５日目）
ときは平成Ｙ＋１年、チャレンジの５日目、今日も研究室には誰もいない。寂しくはないぞ。
削除してしまった ZIP ファイルの残骸が見つかった。断片化されていない限り PK34 を含むブロックから PK56（...から 22 バイト目）までを含むブロックが ZIP ファイルのはずだ。ZIP ファイルなら全てがそうだ、という訳ではないけれど。
ZIP のシグネチャーの探索結果を一覧する。PK34, PK12, PK56, ...沢山見つかった。なお、使用中のアロケーションブロックは対象外として、未使用のブロックで先頭４バイトが PK34 であるブロックは、0000h 〜 1601h の範囲では見つからず、1602h 〜 1D1Eh の範囲でのみ見つかった。探索の対象はやはり 1602h 〜 1D1Eh で間違いないだろう。
試しに１つをシグネチャを頼りにブロックを読み出して内蔵ＨＤＤに保存する。UNZIP したら復元できた。あっさりと、エラーなく。いきなり成功してしまって、気持ちがついてこない。というか信じられない。
でも 2 つ目の ZIP ファイルを試すと、エラーとなる。
私「よかった、安心した、簡単には行かないはず、これが現実だ、ファイル復活はそんなに簡単には終わらない〜♪」
エラーとなった原因はファイルが分断化してエクステントが複数個になっている為だろう。
ブロック番号順にシグネチャを表示すると、PK34 → PK56, PK34 → PK56 という順番で並ぶところが、PK34 → PK34 → PK56 → PK56 と入れ子になっているものもある。それに PK34 から PK56 までのブロック数とファイルサイズを比較すると一致しないことからも途中でギャップが入っていると分かる。
多分、ＨＤＤに書き込む際にファイルを１ずつコピーしていれば一つのエクステント（連続するブロック）として書き込まれるが、2 つ以上のファイルを同時に書き込むと断片化するのではないか。あるいは余りに大きなファイルを書き込むと、書き込み途中でＯＳがディスクアクセスして何かライトしたのかも知れない。DS_Store とか怪しいよね。
＊＊＊
エラーとなった ZIP ファイルのシグネチャを示す。
[["PK34", (0x1c05, 2404, 1), 0],
["PK12", (0x1c1a, 1773, 2), 2831],
["PK66", (0x1c1a, 1773, 2), 2937],
["PK67", (0x1c1a, 1773, 2), 2993],
["PK56", (0x1c1a, 1773, 2), 3013]]
PK56 は「アロケーションファイルの 1C1Ah ブロックの 1773 バイト目の 7 - 2 ビット目に対応するブロックの 3013 バイト目にある」と読んで欲しい。あるいは、アロケーションブロック番号「(1C1Ah*4096 + 1773)*8 + 2」のブロックの 3013 バイト目と計算してもよい。アロケーションファイルの 1 バイトがアロケーションブロックの 8 個に対応し、最上位ビット（7 ビット目）が 8 個のうちの最初のブロックになります。
それと、PK66 と PK67 の 2 つは、ZIP64 という 4GB 以上のファイルを扱える ZIP 拡張版で使われるシグネチャだ。PK34 に格納されているファイルサイズは FFFFFFFFh となっていて本当のサイズは PK66 を参照する必要がある。
PK34 から PK56 までで、アロケーションブロックは 683,081 個ある。ZIP ファイルのサイズと比べると 16 ブロックの差異がある。
16 個のギャップを探そう。
ZIP ファイルは圧縮されたバイナリーな感じになっている。ギャップに入っているのがテキストファイルだったら目視でも区別できるだろう。もしも間に入っているのが別の ZIP ファイルだったら違いは分からないかも。だけれども、この ZIP ファイルの場合は PK34 → PK56 が入れ子にはなっていない。
私「探せるかもしれない、やってみるべきだな」
PK34 から PK56 までのブロックを調べてみよう。ブロック内のデータの出現頻度と分散を適当に定義してみる。
スクリプトをＲＵＮする。
私「結果はグラフにしてみようか」
グラフ化の用意を始める。スクリプトが終了するのが待てないので、というよりも空いていた手が自然と次のスクリプトを作り出して、出力されたデータを取り込んで逐次グラフ表示させてしまう（...全体としては処理速度が落ちるのに）。
ブロックの調査が進むと、グラフが段々と長くなって、ブロックの様子が目に見える。するとグラフに異変が！
(1C05h, 2660, 1) からと、次には (1C07h, 356, 5) から、他よりも目立って 00h の連続が多いブロックが見つかる（Fig.K1）。
スクリプトを止めて、怪しい部分を目視確認する。前後のブロックと比べて、ここだけ ZIP ファイルとは考えられないブロックだ。
(1C05h,2660,1)
+00h: 00000001 42756431 00002000 00000800
+10h: 00002000 0000100c 00000000 00000000
+20h: 00000000 00000000 00000000 00000800
+30h: 00000800 00000000 00000000 00000000
+40h: 00000000 00000002 00000000 0000003a
+50h: 00000001 00001000 005f0030 0034005f
+60h: 00310039 00000000 00000000 00000000
+70h: 00000000 00000000 00000000 00000000
私「これは？、1h, "Bud1", 2000h, 800h, ... これは怪しいよ、有罪だ。それに "Bud1" って何だろう？」
＊＊＊
結果として 3 個のエスクステントに断片化していたことが分かった。
エスクステント 1 は、(0x1c05, 2404, 1) から (0x1c05, 2660, 0) まで、
＜4 ブロックのギャップ＞
エスクステント 2 は、(0x1c05, 2660, 5) から (0x1c07, 356, 4) まで、
＜12 ブロックのギャップ＞
エスクステント 3 は、(0x1c07, 358, 1) から (0x1c1a, 1773, 2) まで。
エスクステント 1 と 2 の間には 4 ブロックのギャップ、エスクステント 2 と 3 の間には 12 ブロックのギャップがあった。合計 16 ブロックで計算も合う。そして、ギャップ部分を除いて 3 個のエスクステントをファイルに出力すると、UNZIP でエラーなく展開できた。
＊＊＊
私「ほほう。うまく行ったな。だがしかし、ファイルの断片化はそんなに綺麗に解決するものだろうか、いやそんなことはないはずだ」
それで、止む得なく、3 つ目の ZIP ファイルも確認した（...結局は全部のファイルを試すのでしょ）。
[["PK34", (0x19bb, 1357, 1), 0],
["PK12", (0x19fd, 1008, 0), 2851],
["PK66", (0x19fd, 1008, 0), 2963],
["PK67", (0x19fd, 1008, 0), 3019],
["PK56", (0x19fd, 1008, 0), 3039]]
まずはギャップ数の確認。
PK34 から PK56 まで 2,159,896 ブロックあり、ファイルサイズとの差は、1,464,501 ブロック分だった。146 万ブロックのギャップがある。
私「これは厳しい。けれど、これは現実だ」
＊＊＊
データの出現頻度を分析してみると、ZIP ファイルのデータではなさそうなブロックが大量にみつかり、その中にバイナリなデータが入ったブロックも挟まっていて、どれが ZIP ファイルのブロックなのか分からない。
ただ、(0x19bb, 1613, 1)からの 4 ブロック分はアロケーションファイルでビットが立っていて使用中のブロックだった。使用中のブロックは、今特定したい ZIP ファイルのブロックではない。(0x19bb, 1629, 6) から (0x19bb, 1638, 1) も使用中だ。
私「19BBh に何があったんだ？、19BBh に何かした覚えはないけど」（...パソコン利用中に 19BBh かと意識する人はいないよ）
多少の使用中のブロックがあってもギャップは大量に残っている。単なる頻度分析ではなく、やはり、もっと確定的な分析が必要だ。分析の観点を求めて APPNOTE を読み込む。
ZIP ファイルは、概ね、最初に PK34 を先頭とするヘッダーがあり、その後ろにデータストリーム（ビット列）が続く。データストリームの終わりには PK78 があることもあるらしい。ZIP ファイルに格納されたファイル数分だけ PK34 とデータストリーム（と PK78）が繰り返されて、その後、PK12 がファイル数分あり、PK56 で終わる。
PK34 と PK12 のヘッダーの内容は似ていて、ファイルサイズやファイル名、更新時刻、ＣＲＣ３２、圧縮法などが格納されている。PK12 のみにある内容として PK34 へのオフセット情報がある。それと PK56 には PK12 へのオフセット情報が含まれている。ZIP ファイル内に複数個のファイルが収納されている場合には、これらのオフセット情報を利用してギャップがどの範囲に（どの格納ファイルに）あるのかを切り分けできたようだ。ファイルが１個の場合は役に立たない。とても暗い感じがしてきた。駄目かもしれない。でもまだ諦めるのは早いと努めてみる。
＊＊＊
（削除）
＊＊＊
私「しょうがないよ、PK34 と PK12 の間にあるデータストリームについて調べよう」
ZIP ファイルの圧縮法は圧倒的に「Deflate」が多いらしい。このファイルも PK34 のヘッダーを調べると、圧縮法は「8」で Deflate だと分かる。
Deflate とは、PKZIP の開発者が PKZIP のために設計した圧縮形式だ。ＬＺ７７アルゴリズムとハフマン符号を使用している。1991年にアルファ版がでた後、1993年1月になって PKZIP2 として公開された（...1992年の年末にも出ていたけれど）。その仕様はとりあえず RFC1951 で読める。和訳を見て大まかな流れを把握することはよいけれど必ず原文を確認すべきだ。Web の解説ページは間違っていないか注意深く読もう（...Wiki の Deflate のページは、修正されたけれど、疑問を感じることが書かれていた時期もありました）。
Deflate のデータストリームは複数個のブロックからなり（...「ブロック」だと紛らわしいので「データブロック」としよう）、データブロックの先頭 3 ビットで後続ブロックの有無と圧縮法を示す。この圧縮法は「非圧縮」か「固定ハフマン符号による圧縮」、「動的ハフマン符号による圧縮」のどれかである。なお「動的ハフマン符号（dynamic Huffman codes）」は ZIP での用語だ。ZIP の方式とは異なる本来の「動的ハフマン符号」と呼ばれる方式がある。ここでは「ｄｙｎａｍｉｃ」なので「動的」としたが、様々な訳語が当てられている。皆好きにしたら良い。
データブロックのサイズは可変長で上限はないが（非圧縮の場合は 64KB まで）、32KB 前後のようだ。アロケーションブロックの 8 個分になる。
＊＊＊
ある特定の 4KB のブロックが「Deflate のデータストリームの一部か否か」を判定することは可能だろうか、と考えようとしたが、考えるまでもなく、非圧縮の場合は任意のデータがあり得るので無理ですねー、という結論に。
固定ハフマン符号の場合も、ハフマン符号なら任意のビット列を受け入れそうだ。動的ハフマン符号の場合は、符号語の表の展開時にデコードエラーが発生する余地がありそうな気がする。でも仕様をしっかり理解しないとはっきりしない。
ＬＺ７７アルゴリズムの部分は理解し易いけれど、ハフマン符号は険しい感じがする。RFC1951 をじっとりと読んでも理解が進まない。どの１文も必然性をもって、そのような記述になっているはずなのに。そう思って読んでも、それが読み取れない。
そう言えば、符号理論の講義でハフマン符号が出てきたか覚えがない。ハミング符号からターボ符号まで色々あったけど、どれも誤り訂正符号だった気がする（...ハフマン符号とハミング符号とを言い間違えることって良くあるよね）。
教科書を読み直すと、誤り訂正と情報圧縮は対立的な概念で、前者は「通信路符号化」、後者は「情報源符号化」と区別されていた。
そう、その通りだ。とても納得する。専門外とは言え無知すぎるな。
基本的なところを勉強し直そう。教科書を探しに行こう。異世界に転生したら現地の人にハフマン符号を布教するときに役に立つはず（...ふつー、算術符号を使うでしょと言われたりして、ションボリ(´・ω・`)と、したりしてみたい）。
なお、通信路符号化は符号理論で扱い、情報源符号化は情報理論かと思ったら、そうでもなさそう（...符号理論は情報理論に含まれる、情報源符号化を符号理論で扱うこともある、情報理論でも通信路符号化を扱っているとか）。今、知りたいのはどの教科書で扱われているかで、あまりその他のことを気にしてはいけない。
今日はここまでにして、帰って寝よう。ご飯どうしよう。
＊＊＊
