【CS50x(2022)】ProblemSet4 - Recover 題解

前言

第四週主要在講解 pointer 的概念,所以這個題目主要就是進行 pointer 的應用練習。

題目說明

相機記憶卡裡的照片被不小心誤刪了,幸好電腦世界裡的「刪除」並不是真的刪除,而是變成某種我們無法正常讀取的存在。為了把照片搶救回來,所以要寫一個程式來把照片復原。

首先,我們已知記憶卡中的照片是以 JPEG 形式保存。JPEG 檔案有固定的格式,因為這個特性讓我們可以在零散資料中辨認出原始的 JPEG 檔案。檔案的前 3 個 bytes 固定如下:

1
0xff 0xd8 0xff

而第 4 個 bytes 則會是下列其中一種: 0xe00xe10xe20xe30xe40xe50xe60xe70xe80xe90xea0xeb0xec0xed0xee0xef。簡單來說,第 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
    9
    int 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
    12
    int 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
    31
    int 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) == 0xe00xf0 用兩個字符來代表前後 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
    3
    free(filename);
    fclose(output_file);
    fclose(input_file);

完整程式碼

程式碼連結(Gist)

小結

pointer 對我來說是個很抽象的概念。之前主要是學習 JavaScript,雖然物件(Object)會碰到 pass by reference 這種類似概念,但和 C 語言中的 pointer 還是有點差別,目前還沒有碰過「直接操作記憶體」的狀況。這題實在卡關好久,又參考了網路上的一些解題思路,終於成功寫出來了!

文章內容如有錯誤,歡迎留言討論!


本 Blog 上的所有文章除特别聲明外,均採用 CC BY-SA 4.0 協議 ,轉載請註明出處!