Recover

次の手順に従って、フォレンジックイメージからJPEGを回復するプログラムを実装します。

$ ./recover card.raw

背景

この問題を予期して、私たちはこの数日間、知り合いの写真を撮影し、そのすべてをメモリーカードにJPEGとしてデジタルカメラに保存しました (正直に言えば、ここ数日はFacebookで時間を過ごしました)。残念ながら、全て削除してしまいました！ありがたいことに、コンピュータの世界では、 「削除された」 というのは 「消去された」 という意味ではなく、 「忘れられた」 という意味になる傾向があります。カメラはカードが空になったと主張していますが、それが真実ではないことは間違いないでしょう。実際、あなたが写真を復元するプログラムを書いてくれることを期待しています！

JPEGはBMPよりも複雑ですが、ほかのファイル形式と区別できるバイトパターンである 「署名」 があります。具体的には、JPEGの最初の3バイト (1バイト目から3バイト目まで、左から右へ) は次のとおりです。

0xff 0xd8 0xff

一方、4番目のバイトは0xe0、0xe1、0xe2、0xe3、0xe4、0xe5、0xe6、0xe7、0xe8、0xe9、0xea、0xeb、0xec、0xed、0xee、0xefのいずれかです。言い換えると、4番目のバイトの最初の4ビットは1110です。

写真を保存できるメディア (例えば私のメモリカード) でこの4バイトのパターンを見つけた場合、それはJPEGの始まりを示しています。公平を期すために、これらのパターンは偶然に一部のディスクで見つかる場合があります。したがって、データリカバリは厳密な科学ではありません。

幸いなことに、デジタルカメラは写真をメモリカードに連続して保存する傾向があり、各写真は前に撮影された写真の直後に保存されます。したがって、JPEGの開始は通常、別のJPEGの終了を意味します。しかしながら、デジタルカメラは、 「ブロックサイズ」 が512バイト (B) であるFATファイルシステムでカードを初期化することが多いです。つまり、これらのカメラは512 B単位でしかカードに書き込むことができません。1 MB (すなわち、1,048,576 B) の写真は、メモリカード上で1048576÷512=2048のブロックを消費します。しかし、たとえば1バイト小さい写真 (すなわち、1,048,575 B) も同じです。ディスク上の無駄な領域を 「スラック領域」 と呼びます。フォレンジックの研究者は、疑わしいデータの残骸がないかどうかを調べることがよくあります。

これら詳細の意味するところは、調査員であるあなたはおそらく、JPEGの署名を探して私のメモリカードのコピーを作成するプログラムを書くことができるということです。署名が見つかるたびに、新しいファイルを開いて書き込みを行い、そのファイルにメモリカードのバイトを書き込み、別の署名が見つかった場合にのみそのファイルを閉じることができます。さらに、メモリカードのバイトを一度に読み込むのではなく、効率のために一度に512バイトをバッファに読み込むことができます。FATのおかげで、JPEGの署名は 「ブロック整列」 されていると信頼できます。つまり、ブロックの最初の4バイトの署名のみを検索する必要があります。

もちろん、JPEGは連続したブロックにまたがることができます。そうしないと、512 Bを超えるJPEGは作成できません。ただし、JPEGの最後のバイトはブロックの最後に配置されない場合があります。スラック領域がある可能性を思い出してください。でも心配しないでください。このメモリカードは私が写真を撮り始めたときには新品だったので、メーカーによって「初期化」 (つまり、0の列で埋められています) されていたでしょう。これらの末尾の0が、リカバリするJPEGに含まれていても問題ありません。JPEGは問題なく表示されるはずです。

今、メモリーカードは1枚しか持っていませんが、あなたがやることはたくさんあります！そこで、カードの 「フォレンジックイメージ」 を作成し、その内容を1バイトずつcard.rawというファイルに保存しました。不必要に何百万もの0を繰り返し処理する時間を無駄にしないために、メモリカードの最初の数メガバイトだけをイメージしました。最終的にはイメージとして50個のJPEGが含まれていることがわかります。

始め方

ここでは、この問題の配布コード (スターターコード) をCS50 IDEにダウンロードする方法を説明します。CS50 IDEにログインし、ターミナルウィンドウで次の各コマンドを実行します。

  1. すでに存在しているpset4ディレクトリに移動します。
  2. wget http://cdn.cs50.net/2020/fall/psets/4/recover/recover.zipを実行して、この問題の配布ファイルを含む (圧縮された) ZIPファイルをダウンロードします。
  3. unzip recover.zipを実行して、そのファイルを解凍します。
  4. rm recover.zipを実行し、その後でyesまたはyを実行してZIPファイルを削除します。
  5. lsを実行します。ZIPファイルの中にrecoverというディレクトリがあるはずです。
  6. cd recoverを実行して、そのディレクトリに移動します。
  7. lsを実行します。card.rawとrecover.cを含む、この問題のディストリビューションが表示されます。

仕様

フォレンジックイメージからJPEGをリカバリするrecoverというプログラムを実装します。

  • recoverというディレクトリにあるrecover.cというファイルにプログラムを実装します。
  • プログラムは、JPEGを復元するフォレンジックイメージの名前であるコマンド行引数を1つだけ受け入れる必要があります。
  • プログラムが正確に1つのコマンドライン引数で実行されていない場合は、ユーザに正しい使い方を知らせ、mainは1を返します。
  • フォレンジックイメージを開いて読み取ることができない場合、プログラムはユーザにその旨を通知し、mainは1を返します。
  • 生成するファイルには、それぞれ###.jpgという名前を付ける必要があります。ここで、###は3桁の10進数で、最初のイメージは000で始まり、上に向かって増えていきます。
  • mallocを使用する場合、メモリーをリークしてはなりません

ウォークスルー

使い方

プログラムは、次の例に従って動作する必要があります。

$ ./recover
Usage: ./recover image
$ ./recover card.raw

ヒント

以下のように、argv[1]が存在する場合は、fopenを使用してcard.rawをプログラムで開くことができます。

FILE *file = fopen(argv[1], "r");

プログラムを実行すると、card.rawからすべてのJPEGがリカバリされ、カレントディレクトリに個別のファイルとして保存されます。プログラムでは、出力するファイルにそれぞれ###.jpgという名前を付けて番号を付ける必要があります。###は、000から始まる3桁の10進数です (sprintfに慣れましょう) 。 JPEGの元の名前を復元する必要はありません。プログラムが吐き出したJPEGが正しいかどうかを確認するには、ダブルクリックして見てください。各写真が正常に表示される場合は、プログラムは成功しているでしょう。

ですが、最初のコードが出力するJPEGはおそらく正しくないでしょう (開いても何も表示されない場合は、おそらく正しくありません) 。次のコマンドを実行して、カレントディレクトリにあるすべてのJPEGを削除します。

$ rm *.jpg

削除を確認するメッセージが表示されないようにするには、次のコマンドを実行します。

$ rm -f *.jpg

-fスイッチはプロンプトを出さずに削除を 「強制 (force)」 するので、注意してください。

1バイトのデータを格納する新しいタイプを作成する場合は、下のコマンドを使用します。これにより、BYTEという新しいタイプがuint8_t (8ビット符号なし整数を表す、stdint.hで定義された型) に定義されます。

typedef uint8_t BYTE;

また、freadを使用してファイルからデータを読み取ることもできます。freadを使用すると、ファイルからメモリ内の場所にデータが読み取られ、ファイルから正常に読み取られた項目数が返されます。

テスト

check50を使用して以下を実行し、コードの正確さを評価してください。ただし、コンパイルとテストは必ず自分で行ってください。

check50 cs50/problems/2021/x/recover

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 recover.c

提出方法

次のコマンドを実行し、GitHubのユーザ名とパスワードを入力してログインします。セキュリティのため、パスワードには実際の文字ではなくアスタリスク (*) が表示されます。

submit50 cs50/problems/2021/x/recover