【CS50x(2022)】ProblemSet4 - Recover 題解
前言
第四週主要在講解 pointer 的概念,所以這個題目主要就是進行 pointer 的應用練習。
題目說明
相機記憶卡裡的照片被不小心誤刪了,幸好電腦世界裡的「刪除」並不是真的刪除,而是變成某種我們無法正常讀取的存在。為了把照片搶救回來,所以要寫一個程式來把照片復原。
首先,我們已知記憶卡中的照片是以 JPEG 形式保存。JPEG 檔案有固定的格式,因為這個特性讓我們可以在零散資料中辨認出原始的 JPEG 檔案。檔案的前 3 個 bytes 固定如下:
1 |
|
而第 4 個 bytes 則會是下列其中一種: 0xe0
、0xe1
、0xe2
、0xe3
、0xe4
、0xe5
、0xe6
、0xe7
、0xe8
、0xe9
、0xea
、0xeb
、0xec
、0xed
、0xee
或 0xef
。簡單來說,第 4 個 bytes 的前半部分會是 1110
。
其次,檔案會被分割成更小單位(block)儲存,每個單位是 512 bytes。也就是我們在讀取檔案時不用每個 bytes 逐一讀取,而是能一次處理 512 bytes。而且,這些 block 是以連續方式儲存的,也就是前一個 block 的結尾會直接接續下一個 block 的開頭。
最後,這張被誤刪的記憶卡應該可以經由程式復原 50 張照片。
規格要求
- 執行程式時要帶入 1 個 command-line argument(需要被復原的原始檔案名稱)。
- 如果帶入的 command-line argument 不等於 1,
main
程式需要提供錯誤訊息及return 1
。 - 如果需要被復原的原始檔案無法開啟,
main
程式需要return 1
。 - 被復原的照片需要以
###.jpg
的三碼數字檔名儲存,從000.jpg
開始。 - 如果程式中有用到
malloc
,記得避免記憶體流失(memory leak)。
解題開始
流程
1
2
3
4
5
6
7
8
9int main(int argc, char *argv[])
{
// 確認 argc 是否等於 2
// 打開記憶卡,確認是否可以正常讀取
// 開始讀取檔案,讀取 512 B
// 如果找到 JPEG 開頭,開始寫入新檔案
// 關閉檔案並釋放記憶體
return 0;
}確認
argc
是否等於二?1
2
3
4
5
6
7
8
9
10
11#include <stdio.h> // 因為會用到 printf()
int main(int argc, char *argv[])
{
// 確認 argc 是否等於 2
if (argc != 2)
{
printf("Usage: ./recover IMAGE\n");
return 1;
}
}argc
為 command-line 裡的 argument 總數(含執行檔案本身)。執行檔案時會在終端機輸入./recover card.raw
,也就是總共兩個 arguments。如果argc
不等於 2 ,則印出錯誤訊息及return 1
。打開記憶卡,確認是否可以正常讀啟
1
2
3
4
5
6
7
8
9
10
11
12int main(int argc, char *argv[])
{
// 打開記憶卡
FILE *input_file = fopen(argv[1], "r");
// 如果不能正常讀取則印出錯誤訊息並 return 1
if (input_file == NULL)
{
printf("FileError: Unable to open file.\n");
return 1;
}
}變數宣告
1
2
3
4
5
6
7
8
9
10
11
12#include <stdlib.h> // 因為會用到 malloc() 和 free()
#include <stdint.h> // 因為會用到型別 uint8_t
#define BLOCK_SIZE 512 // 將 BLOCK_SIZE 定義為 512
int main(int argc, char *argv[])
{
uint8_t buffer[BLOCK_SIZE]; // 建立一個 array 用來暫存讀取到的資料
int image_count = 0; // 計算照片數量
FILE *output_file = NULL;
char *filename = malloc(8 * sizeof(char)); // 用來暫存檔名
}uint8_t
是一個定義在<stdlib.h>
裡面的型別,代表著 8-bit(1 Byte) 的 unsigned integer。因為使用了這個型別,所以要在開頭引入<stdlib.h>
。檔案名稱部分指定了
8 * sizeof(char)
來暫存檔案名稱。檔名由###.jpg
組成,總共 7 個字元,之所以使用 8 是因為最後還會加上\0
來代表字串的結束。開始讀取檔案,每次讀取 512 B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31int main(int argc, char *argv[])
{
// 每次讀取 512 B 並寫入 buffer
while (fread(buffer, BLOCK_SIZE, 1, input_file))
{
// 如果找到 header of JPEG
if (buffer[0] == 0xff && buffer[1] == 0xd8 && buffer[2] == 0xff && (buffer[3] & 0xf0) == 0xe0)
{
// 關閉上一個檔案
if (output_file != NULL)
{
fclose(output_file);
}
// write jpeg filename with <image_count>.jpg
sprintf(filename, "%03i.jpg", image_count);
// open new output_file for writing
output_file = fopen(filename, "w");
//
image_count++;
}
if (output_file != NULL)
{
// write into jpeg file
fwrite(buffer, sizeof(buffer), 1, output_file);
}
}
}開始讀取檔案,每次讀取 512 Bytes。用 while 迴圈檢查前 4 個 Bytes 的值來確認是不是 JPEG header。其中在辨識第 4 個 Bytes 時使用了
(buffer[3] & 0xf0) == 0xe0
,0xf0
用兩個字符來代表前後 4-bit。而這邊的&
是位元運算子,用來比較二進位的每個 bit 是否相同。和0xf0(11110000)
的比較,如果前 4-bit 是e(1110)
,後 4-bit 不管是什麼,最後結果一定是0xe0(11100000)
。用這種方法來確認第 4 個 Bytes 是否符合要求。每次檢查會遇到兩種情況:
- 是 header of JPEG。這種情況就可以準備寫入檔案了。
- 不是 header of JPEG。
如果讀取到的 block 不是 header of JPEG 那又可以再細分成兩種狀況:
- 是 JPEG 的一部份,則可以接著寫入目前檔案。
- 是其他零散資料,則不做處理。
在最一開始我們把 pointer
output_file
指定為NULL
,等到找到 header of JPEG 就指派記憶體給它。所以如果output_file != NULL
則表示是JPEG 的一部份;反之則是零散資料。找到 header of JPEG 要記得先關閉前一個檔案,並開啟新檔案來寫入資料。
釋放記憶體
1
2
3free(filename);
fclose(output_file);
fclose(input_file);
完整程式碼
小結
pointer 對我來說是個很抽象的概念。之前主要是學習 JavaScript,雖然物件(Object)會碰到 pass by reference 這種類似概念,但和 C 語言中的 pointer 還是有點差別,目前還沒有碰過「直接操作記憶體」的狀況。這題實在卡關好久,又參考了網路上的一些解題思路,終於成功寫出來了!
文章內容如有錯誤,歡迎留言討論!
本 Blog 上的所有文章除特别聲明外,均採用 CC BY-SA 4.0 協議 ,轉載請註明出處!