【CS50x(2022)】ProblemSet4 - Recover 題解

前言

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

題目說明

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

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

0xff 0xd8 0xff

而第 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)。

解題開始

• 流程

  int main(int argc, char *argv[])
  {
    // 確認 argc 是否等於 2
    // 打開記憶卡，確認是否可以正常讀取
    // 開始讀取檔案，讀取 512 B
        // 如果找到 JPEG 開頭，開始寫入新檔案
    // 關閉檔案並釋放記憶體
    return 0;
  }

• 確認 argc 是否等於二?

  #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。

• 打開記憶卡，確認是否可以正常讀啟

  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;
    }
  }

• 變數宣告

  #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

  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) == 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 要記得先關閉前一個檔案，並開啟新檔案來寫入資料。

• 釋放記憶體

  free(filename);
  fclose(output_file);
  fclose(input_file);

完整程式碼

程式碼連結(Gist)

小結

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

文章內容如有錯誤，歡迎留言討論！