哈佛 CS50：第 4 週作業（第 9 課和第 10 課）

準備工作

與往常一樣，首先打開終端機視窗並運行命令。 update50 確保您的應用程式已經是最新的。開始之前，請按照此 cd ~ / workspace wget http://cdn.cs50.net/2015/fall/psets/4/pset4/pset4.zip 步驟下載此任務的 ZIP 檔案。現在，如果執行ls ，您將看到~/workspace目錄中有一個名為pset4.zip的檔案。使用以下命令解壓縮：如果再次執行ls命令，您將看到另一個目錄出現了。現在您可以刪除 zip 文件，如下所示：讓我們打開pset4目錄，運行ls，並確保該目錄包含 unzip pset4.ziprm -f pset4.zip cd pset4bmp / jpg / questions.txt

whodunit 或“誰幹的？”

如果您曾經看過預設的 Windows XP 桌面 (https://en.wikipedia.org/wiki/Bliss_(image))（山丘和藍天），那麼您就見過 BMP。在網頁上，您很可能看過 GIF。你看過數位照片嗎？所以，我們很高興看到 JPEG。如果您曾經在 Mac 上截取過螢幕截圖，那麼您很可能見過 PNG。在 Internet 上閱讀有關 BMP、GIF、JPEG、PNG 格式的資訊並回答以下問題：

每種格式支援多少種顏色？
哪種格式支援動畫？
有損壓縮和無損壓縮有什麼差別？
下列哪一種格式使用有損壓縮？

建議說英語的人參考MIT的文章。如果您研究它（或在 Internet 上尋找有關在磁碟和檔案系統上儲存檔案的其他資源），您可以回答以下問題：

從技術角度來看，當 FAT 檔案系統中的檔案被刪除時會發生什麼？
可以採取什麼措施來確保（很有可能）已刪除的檔案無法恢復？

現在 - 我們的故事，順利地進入第四週的第一個任務。歡迎來到都鐸大廈！莊園的主人約翰·博迪先生突然離開了我們，成為一場不起眼的遊戲的受害者。要查明發生了什麼，您必須定義whodunit。對您來說不幸的是（對於 Boddy 先生來說更不幸），您擁有的唯一證據是 24 位元 BMP 檔案clue.bmp。您在下面看到的就是它的內容。博迪先生在生命的最後一刻成功製作並保存在他的電腦上。該檔案包含隱藏在紅噪音中的偵探影像。現在您需要像真正的技術專家一樣研究解決方案。哈佛 CS50：第四週作業（講座 9 和 10）- 2

但首先，一些資訊。最簡單的方法可能是將影像視為像素網格（即點），每個像素都可以是特定的顏色。要設定黑白影像中某一點的顏色，我們需要 1 位。0可以代表黑色，1可以代表白色，如下圖所示。哈佛 CS50：第四週作業（講座 9 和 10）- 3

因此，以這種方式表示的圖像只是點陣圖（點陣圖或點陣圖，正如英語或俚語中所說的那樣）。對於黑白，一切都盡可能簡單，但要獲得彩色影像，我們只需要每個像素更多的位數。支援「8 位元顏色」的檔案格式（例如 GIF）使用每個像素 8 位元。支援「24 位元顏色」的檔案格式（例如 BMP、JPG、PNG）使用每像素 24 位元（BMP 實際上支援 1、4、8、16、24 和 32 位元顏色）。在 Boddy 先生使用的 24 位元 BMP 中，需要 8 位元來指示每個像素中紅色的量，相同的量指示綠色，並且同樣需要 8 位元來指示藍色的量。如果你聽過RGB顏色，那就是它（R=紅色，G=綠色，B=藍色）。如果 BMP 中某個像素的 R、G 和 B 值為十六進制的 0xff、0x00 和 0x00，則該像素將是純紅色，因為 0xff（也稱為十進制的 255）意味著“大量紅色” ”當時0x00 和0x00 分別表示「沒有綠色」和「藍色也為零」。考慮到博迪先生的 BMP 影像對我們來說是多麼紅色，直觀地說紅色「隔間」的值明顯大於紅色和藍色「隔間」的值。然而，並非所有像素都是紅色的；有些像素顯然具有不同的顏色。順便說一句，在 HTML 和 CSS（標記語言和幫助它的樣式表，用於建立網頁）中，顏色模型以相同的方式排列。如果您有興趣，請查看連結： https: //ru.wikipedia.org/wiki/Colors_HTML更多細節。現在讓我們從技術上更深入地解決這個問題。回想一下，檔案只是按某種順序排列的位元序列。24 位元 BMP 檔案是一個位元序列，其中每 24 位元（好吧，幾乎）決定了哪個像素的顏色。除了顏色資料之外，BMP 檔案還包含元資料 - 有關影像寬度和高度的資訊。該元資料以兩種通常稱為「頭」的資料結構的形式儲存在檔案的開頭（不要與 C 頭檔案混淆）。這些標頭中的第一個是 BITMAPFILEHEADER，其長度為 14 個位元組（或 14*8 位元）。第二個標頭是 BITMAPINFOHEADER（40 位元組長）。這些標頭之後是位圖：一個位元組數組，其中的三元組表示像素的顏色（BMP 中的1、4 和16 位，但不是24 或32，它們在BITMAPINFOHEADER 之後有一個附加標頭。它稱為RGBQUAD 數組，定義調色板中每種顏色的「強度值」）。然而，BMP 以相反的方式儲存這些三元組（我們可以說像 BGR），其中 8 位元表示藍色，8 位元表示綠色，8 位元表示紅色。順便說一下，一些 BMP 還從 BMP 檔案末尾圖像的頂行開始向後儲存整個點陣圖。在我們的任務中，我們按照此處所述保存了 VMR，首先是圖像的頂行，然後是底部行。換句話說，我們透過用紅色取代黑色，將 1 位表情符號變成了 24 位表情符號。24位元BMP會儲存這個點陣圖，其中0000ff代表紅色，ffffff代表白色；我們用紅色突出顯示了所有 0000ff 的實例。哈佛 CS50：第四週作業（講座 9 和 10）- 4

由於我們從左到右、從上到下呈現這些位，因此如果您稍微遠離顯示器，您可以看到這些字母中的紅色笑臉。回想一下，十六進制數字系統中的一個數字代表 4 位。因此，十六進制的 ffffff 實際上意味著二進制的 1111111111111111111111111。現在，放慢速度，不要再繼續，直到您確定理解為什麼 0000ff 代表 24 位元 BMP 檔案中的紅色像素。在 CS50 IDE 視窗中，展開（例如，透過點擊小三角形）pset4資料夾，然後在其中找到bmp。在此資料夾中，您將找到smiley.bmp，雙擊該文件，您將在其中找到一個小的 8x8 像素笑臉。在下拉式選單中，更改圖像比例，例如從 100% 更改為 400%，這將允許您看到更大但同時更「模糊」版本的表情符號。儘管實際上，即使放大，同一張圖像也不應該模糊。只是CS50 IDE試圖透過平滑圖片（視覺上模糊邊緣）來幫你一個忙（以CIA系列的風格）。如果我們放大而不平滑的話，這就是我們的笑臉的樣子：哈佛 CS50：第四週作業（講座 9 和 10）- 5

像素變成了大方塊。我們繼續吧。在終端機中，前往~/workspace/pset4/bmp。我們認為您已經記住瞭如何執行此操作。讓我們檢查smiley.bmp中分配的位元組。這可以使用命令列十六進位編輯器xxd程式來完成。要運行它，請運行命令： xxd -c 24 -g 3 -s 54 smiley.bmp 您應該看到如下所示的內容；我們再次用紅色突出顯示所有 0000ff 的實例。哈佛 CS50：第四周作業（第 9 和 10 講）- 6

在最左邊一列的影像中，您可以看到檔案中的位址，這些位址相當於距離檔案第一位元組的偏移量。所有這些都以十六進制數字系統給出。如果我們將十六進制 00000036 轉換為十進制，我們會得到 54。所以您正在查看smiley.bmp中的第 54 個位元組。回想一下，在 24 位元 BMP 檔案中，前 14 + 40 = 54 位元組填入有元資料。因此，如果您想查看元數據，請執行以下命令： xxd -c 24 -g 3 smiley.bmp 如果smiley.bmp包含ASCII 字符，我們將在 xxd 的最右列中看到它們，而不是所有這些點。因此，笑臉是一個 24 位元 BMP（每個像素由 24 ÷ 8 = 3 位元組表示），大小（解析度）為 8x8 像素。因此，每條線（或稱為「掃描線」）佔用 (8 像素) x (每像素 3 位元組) = 24 位元組。該數字是四的倍數，這很重要，因為如果行中的位元組數不是四的倍數，BMP 檔案的儲存方式會略有不同。因此，在我們資料夾中的另一個 24 位元 BMP 檔案small.bmp 中，您可以看到一個綠色的 3x3 像素框。如果您在圖像檢視器中打開它，您將看到它類似於下圖所示，只是尺寸較小。 因此， small.bmp 哈佛 CS50：第四周作業（第 9 講和第 10 講）- 7

中的每一行佔用(3 個像素) × (每個像素3 個位元組) = 9 個位元組，這不是4 的倍數。為了獲得4 倍數的行長度，需要額外的零進行填充：在 0 到 3 個位元組之間，我們以 24 位元 BMP 格式填充每一行（你能猜出這是為什麼嗎？）。對於Small.bmp，需要3 個位元組的零，因為(3 個像素) x (每個像素3 個位元組) + (3 個填充位元組) = 12 個位元組，這實際上是4 的倍數。若要「檢視」此填充，請執行下列操作。請注意，我們對-c使用的值與smiley.bmp 的值不同，因此 xxd 這次僅輸出 4 列（3 列用於綠色方塊，1 列用於填充）。為了清楚起見，我們用綠色突出顯示了 00ff00 的所有實例。作為對比，我們使用 xxd 作為大型 .bmp檔案。看起來和small.bmp一模一樣xxd -c 12 -g 3 -s 54 small.bmp 哈佛 CS50：第四週作業（講座 9 和 10）- 8

，只不過它的解析度是12x12像素，也就是大了四倍。運行以下命令。您可能需要擴大視窗以避免轉移。 xxd -c 36 -g 3 -s 54 large.bmp 您將看到類似這樣的內容：哈佛 CS50：第 4 週作業（第 9 課和第 10 課）- 9

請注意，此 BMP 中沒有任何離題內容！畢竟，(12 像素) × (每像素 3 位元組) = 36 位元組，這是 4 的倍數。 xxd 十六進位編輯器向我們顯示了 BMP 檔案中的位元組。我們如何以程式設計方式取得它們？在copy.c中，有一個程序，其生命的唯一目的是逐塊創建 BMP 的副本。是的，您可以使用cp來實現此目的。然而，cp將無法幫助博迪先生。讓我們希望copy.c能做到這一點，所以我們開始吧： ./copy smiley.bmp copy.bmp 如果您現在運行ls（帶有適當的標誌），您將看到smiley.bmp和copy.bmp確實具有相同的大小。讓我們再驗證一下這是否屬實？ diff smiley.bmp copy.bmp 如果此命令在螢幕上沒有顯示任何內容，則表示檔案確實相同（重要：某些程序，如 Photoshop，在某些 VMP 末尾包含尾隨零。我們的副本版本會丟棄它們，因此不要這樣做擔心如果複製您為測試下載或建立的其他BMP，副本將比原始檔案小幾個位元組）。您可以在 Ristretto 的圖像檢視器中開啟這兩個檔案（雙擊）以直觀地確認這一點。但 diff 是逐字節比較的，所以她的眼光比你更敏銳！這個副本是如何創建的？事實證明copy.c與bmp.h相關。讓我們確保：打開bmp.h。在那裡您將看到我們已經提到的那些標頭的實際定義，這些定義改編自 Microsoft 自己的實作。此外，該檔案定義了 BYTE、DWORD、LONG 和 WORD 資料類型，這些資料類型通常出現在 Win32（即 Windows）程式設計領域。請注意，這些本質上是您（希望）已經熟悉的原語的別名。事實證明，BITMAPFILEHEADER 和 BITMAPINFOHEADER 正在使用這些類型。該檔案還定義了一個名為 RGBTRIPLE 的結構。它「封裝」了三個位元組：一個藍色、一個綠色和一個紅色（這是我們在磁碟上尋找 RGB 三元組的順序）。這些結構有什麼用？回顧一下，檔案只是磁碟上的位元組（或最終位）序列。然而，這些位元組通常是有序的，以便前幾個位元組代表某些內容，然後接下來的幾個位元組代表其他內容，依此類推。文件“格式”的存在是因為我們有標準或規則來定義位元組的含義。現在，我們可以簡單地將檔案作為一個大位元組數組從磁碟讀入 RAM。我們記得位置 [i] 處的位元組代表一件事，而位置 [j] 處的位元組代表另一件事。但是為什麼不給其中一些位元組命名，以便我們可以更輕鬆地從記憶體中檢索它們呢？這正是 bmp.h 中的結構可以幫助我們的。我們不再將檔案視為一長串字節，而是將其分解為更容易理解的區塊——結構序列。回想smiley.bmp的解析度為 8x8 像素，因此它在磁碟上佔用 14 + 40 + (8 × 8) × 3 = 246 位元組（您可以使用 ls 指令檢查）。根據 Microsoft 的說法，它在磁碟上的樣子如下：哈佛 CS50：第四週作業（講座 9 和 10）- 10

我們可以看到，當涉及結構成員時，順序很重要。位元組 57 是 rgbtBlue（不是 rgbtRed），因為 rgbtBlue 首先在 RGBTRIPLE 中定義。順便說一句，我們使用的 Packed 屬性確保 clang 不會嘗試「字對齊」成員（每個成員的第一個位元組的位址是 4 的倍數），這樣我們就不會在我們的程式碼中出現漏洞。磁碟上根本不存在的結構。讓我們繼續。根據 bmp.h 中的註釋，找到與 BITMAPFILEHEADER 和 BITMAPINFOHEADER 相符的 URL。注意，偉大的時刻：您開始使用 MSDN（微軟開發者網路）！不要進一步滾動copy.c，而是回答幾個問題來了解程式碼的工作原理。像往常一樣，man 命令是您真正的朋友，現在 MSDN 也是如此。如果您不知道答案，請谷歌搜尋並思考。您也可以參考 https://reference.cs50.net/ 上的 stdio.h 檔案。

在 main 中設定斷點（透過點選帶有主線編號的標尺左側）。
在終端選項卡中，轉到~/workspace/pset4/bmp，然後使用 make 將 copy.c 編譯為複製程式。
運行debug50 copy smiley.bmp copy.bmp，這將打開右側的調試器面板。
使用右側的面板逐步完成程序。注意bf和bi。在~/workspace/pset4/questions.txt中，回答問題：

什麼是stdint.h？
在程式中使用uint8_t、uint32_t、int32_t和uint16_t有什麼意義？
BYTE、DWORD、LONG和WORD分別包含多少個位元組（假設 32 位元架構）？
BMP 檔案的前兩個位元組應該是什麼（ASCII、十進位或十六進位）？（用於識別檔案格式（很有可能）的前導位元組通常稱為“幻數”）。
bfSize 和 biSize 有什麼差別？
負 biHeight 是什麼意思？
BITMAPINFOHEADER 中的哪個欄位定義 BMP 中的顏色深度（即每像素位數）？
為什麼copy.c 37中的fopen函數可以回傳NULL？
為什麼我們程式碼中 fread 的第三個參數等於 1？
如果 bi.biWidth 為 3，copy.c 70 中的什麼值定義填入？
fseek 有什麼作用？
什麼是 SEEK_CUR？

回到博迪先生。鍛鍊：

在名為whodunit.c的檔案中編寫一個名為whodunit的程序，該檔案顯示博迪先生的圖畫。嗯嗯，什麼？與copy一樣，程式必須恰好接受兩個命令列參數，如果您如下所示運行程序，結果將儲存在verdict.bmp中，其中Mr. Boddy的繪圖不會有雜訊。我們建議您透過執行以下命令來開始解開這個謎團。您可能會驚訝於您需要編寫多少行程式碼來幫助博迪先生。smiley.bmp中沒有隱藏任何不必要的內容，因此請隨意在此文件上測試程式。它很小，你可以在開發過程中比較你的程式的輸出和xxd的輸出（或者也許smiley.bmp中隱藏著一些東西？實際上，沒有）。順便說一句，這個問題可以用不同的方式解決。一旦你認出了博迪先生的畫，他就會安息了。由於whodunit可以透過多種方式實現，因此您將無法使用check50檢查實現的正確性。讓它破壞你的樂趣，但助手的解決方案也不適用於偵探問題。最後，在檔案~/workspace/pset4/questions.txt 中，回答下列問題： ./whodunit clue.bmp verdict.bcp copy.c whodunit.cWhodunit? //ктоэтосделал?

調整大小

好吧，現在 - 下一個測試！讓我們在 resize.c 中寫一個名為resize的程式。它將以 n 為步長調整未壓縮的 24 位元 BMP 影像的大小。您的應用程式必須接受三個命令列參數，第一個 (n) 是不大於 100 的整數，第二個是要修改的檔案的名稱，第三個是修改後的儲存版本的名稱檔案。 Usage: ./resize n infile outfile 使用這樣的程序，我們可以透過將small.bmp的大小調整4（即寬度和高度都乘以4）來從small.bmp建立large.bmp，如下所示。 ./resize 4 small.bmp large.bmp 為簡單起見，您可以再次複製copy.c並將副本命名為resize.c來啟動任務。但首先，先問自己並回答這些問題：改變 BMP 大小意味著什麼（可以假設 n 倍 infile 大小不會超過 232 - 1）。決定需要更改 BITMAPFILEHEADER 和 BITMAPINFOHEADER 中的哪些欄位。考慮是否需要新增或刪除掃描線欄位。而且，是的，值得慶幸的是我們沒有要求您考慮 n 從 0 到 1 的所有可能值！（不過，如果您有興趣，這是黑客書中的一個問題；））。但是，我們假設當 n = 1 時，程式將正常工作，並且輸出檔案outfile將與原始 infile 大小相同。您想使用 check50 檢查程式嗎？鍵入以下命令： check50 2015.fall.pset4.resize bmp.h resize.c 你想玩一下CS50助手製作的應用程式實作嗎？執行以下命令： ~cs50/pset4/resize 嗯，如果您想查看，例如， large.bmp標頭（以比 xxd 允許的更用戶友好的形式），您需要運行以下命令： ~cs50/pset4/peek large.bmp 更好的是，如果您想比較您的headers 與CS50 助手文件的標題。 您可以在~/workspace/pset4/bmp目錄中執行命令（考慮每個命令的作用）。如果您使用了 malloc，請務必使用 free以防止記憶體洩漏。嘗試使用 valgrind檢查是否有洩漏。

./resize 4 small.bmp student.bmp

   ~cs50/pset4/resize 4 small.bmp staff.bmp

   ~cs50/pset4/peek student.bmp staff.bmp

如何決定？

打開我們需要放大的文件，同時創建並打開一個新文件，其中將記錄放大的圖像；
更新輸出檔案的標頭資訊。由於我們的圖像是 BMP 格式並且我們正在更改其大小，因此我們需要使用新尺寸寫入新檔案的標題。會發生什麼變化？檔案大小以及圖像大小 - 它的寬度和高度。

如果我們查看標題描述，我們將看到 biSizeImage變數。它表示圖像的總大小（以位元組為單位）， biWidth是圖像的寬度減去對齊方式， biHeight是高度。這些變數位於 BITMAPFILEHEADER 和 BITMAPINFOHEADER 結構中。 如果您打開bmp.h文件，您可以找到它們。哈佛 CS50：第四周作業（第 9 講和第 10 講）- 12

BITMAPINFOHEADER 結構的描述包含變數清單。要寫入輸出檔案的標題，您需要變更高度和寬度值。但也有可能稍後您將需要原始文件的原始高度和寬度。因此，最好兩者都保留。請小心變數名稱，以免意外在輸出檔案的標頭中寫入錯誤的資料。

我們逐行、逐像素讀取輸出檔。為此，我們再次求助於檔案 I/O 函式庫和 fread 函數。它需要一個指向結構的指針，該結構將包含讀取的位元組、我們要讀取的單個元素的大小、此類元素的數量以及指向我們將從中讀取的文件的指針。
我們按照指定的比例水平增加每一行，並將結果寫入輸出檔。

我們如何寫入文件？我們有一個函數 fwrite，我們向該函數傳遞一個指示符，該指示符指向要寫入檔案的資料所在的結構、元素的大小、元素的數量以及指向輸出檔案的指標。為了組織循環，我們可以使用我們已經熟悉的for迴圈。
填補差距！如果一行中的像素數不是四的倍數，我們必須加上「對齊」 - 零位元組。我們需要一個公式來計算對齊大小。要將空位元組寫入輸出文件，可以使用 fputc 函數，向其傳遞要寫入的字元和指向輸出檔案的指標。

現在我們已經水平拉伸了字串並向輸出檔案添加了對齊方式，我們需要移動輸出檔案中的當前位置，因為我們需要跳過對齊方式。
增加垂直尺寸。它更複雜，但我們可以使用copy.c中的範例程式碼（copy.c打開輸出文件，將標頭寫入輸出文件，逐行、逐像素地從源文件中讀取圖像，然後將它們寫入到輸出檔）。基於此，您可以做的第一件事就是執行以下指令： cp copy.c resize.c

垂直拉伸影像意味著將每行複製多次。有幾種不同的方法可以做到這一點。例如，使用重寫，當我們將一行的所有像素保存在記憶體中，並根據需要多次循環地將這一行寫入輸出檔案。另一種方法是重新複製：從傳出檔案中讀取一行，將其寫入輸出檔案並對齊後，將 fseek函數返回到傳出檔案中的行的開頭，然後將所有內容重複幾次。