哈佛 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函数返回到传出文件中的行的开头，然后将所有内容重复几次。