Гарвард CS50: задания четвертой недели (лекции 9 и 10)

Подготовка к работе

Как всегда, сначала откройте окно терминала и выполните команду. update50 чтобы убедиться, что ваше приложение уже обновлено. Прежде, чем приступить к работе, выполните cd ~ / workspace wget http://cdn.cs50.net/2015/fall/psets/4/pset4/pset4.zip чтобы загрузить ZIP-архив этой задачи. Теперь, если вы выполните ls, то увидите, что у вас появился файл с именем pset4.zip в директории ~ / workspace. Извлеките его с помощью команды: unzip pset4.zip Если вы еще раз выполните команду ls, то увидите, что появился ещё один каталог. Теперь можно удалить ZIP-файл, как показано ниже: rm -f pset4.zip Давайте откроем директорию pset4 cd pset4 выполните ls, и убедитесь, что директория содержит bmp / jpg / questions.txt

whodunit или «Кто это сделал?»

Если вы когда-нибудь видели рабочий стол Windows XP (https://en.wikipedia.org/wiki/Bliss_(image)) по умолчанию (холмы и голубое небо), то вы видели BMP. На веб-страницах, вы, вероятнее всего, видели GIF. Просматривали цифровые фотографии? Значит, имели радость видеть JPEG. Если вы когда-нибудь делали скриншот на Mac, вы, скорее всего, видели PNG. Прочитайте в интернете о форматах BMP, GIF, JPEG, PNG и ответьте на эти вопросы:

Какое количество цветов поддерживает каждый формат?
Какой из форматов поддерживает анимацию?
Какая разница между сжатием с потерями и без потерь?
Какой из этих форматов использует сжатие с потерями?

Те, кто владеют английским, советуем обратиться к статье от МИТ. Если её изучить (или найти в интернете другие ресурсы о хранении файлов на дисках и файловых системах), можно ответить на следующие вопросы:

Что происходит с технической точки зрения, когда файл будет удален в файловой системе FAT?
Что можно сделать, чтобы обеспечить (с высокой вероятностью) невозможность восстановления удаленных файлов?

А теперь — к нашей истории, плавно перетекающей в первое задание четвертой недели. Добро пожаловать в Tudor Mansion! Хозяин поместья, мистер Джон Бодди, скоропостижно ушёл от нас, пав жертвой неясной игры. Чтобы выяснить, что произошло, вы должны определить whodunit. К сожалению, для вас (хотя еще большему сожалению для господина Бодди), единственное доказательство, которое у вас есть — 24-битный BMP файл clue.bmp. Именно его содержимое вы видите ниже. Мистер Бодди успел сделать и сохранить на своем компьютере в свои последние минуты. В файле есть скрытое среди красного "шума" изображения whodunit ("ктоэтосделал"). Теперь необходимо поработать над решением как настоящий технический специалист. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 2

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 2

Но, для начала, некоторая информация. Вероятно, проще всего представить изображение в виде сетки пикселей (в смысле, точек), каждая из которых может быть определенного цвета. Чтобы задать цвет точки черно-белого изображения нам нужен 1 бит. 0 может представлять черный, а 1 — белый цвет, как показано на картинке ниже. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 3

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 3

Таким образом, изображения, представленные таким образом, — это просто карта битов (bitmap или битмап, так говорят по-английски или на сленге). С черно-белыми всё максимально просто, а для получения цветных изображений нам просто понадобится больше битов на пиксель. Формат файла (например, GIF), который поддерживает "8-битный цвет" использует 8 битов на пиксель. Формат файла (например, BMP, JPG, PNG) с поддержкой "24-битного цвета" использует 24 бита на пиксель (BMP фактически поддерживает 1-, 4-, 8-, 16-, 24- и 32-битную передачу цвета). В 24-битном BMP, который использует мистер Бодди, для обозначения количества красного цвета уходит 8 бит, столько же — на зеленый, и снова 8 бит для обозначения количества синего в каждом пикселе. Если вы когда-нибудь слышали о цветах RGB, то это оно и есть (R = red = красный, G = green = зеленый, B = blue = синий). Если значение R, G, и B некоторого пикселя в BMP, скажем, 0xff, 0x00 и 0x00 в шестнадцатеричной системе счисления, то пиксель будет чисто красным, поскольку 0xff (иначе известное как 255 в десятичной системе) означает "много красного" в тот время как 0x00 и 0x00 означают «зеленого нет» и «синего тоже по нулям» соответственно. учитывая насколько красным нам кажется BMP-изображение мистера Бодди, интуитивно ясно, что в «отсеке» для красных значение явно больше, чем в «отсеках» красного с синим. Однако не все пиксели красные, некоторые явно другого цвета. К слову, в HTML и CSS (языка разметки и помогающих ему таблиц стилей, с помощью которых создают веб-страницы) модели цветов устроены таким же образом. Если интересно, изучите ссылку: https://ru.wikipedia.org/wiki/Цвета_HTML для получения более подробной информации. Теперь давайте подойдем к проблеме более технически. Вспомним о том, что файл — это просто последовательность битов, расположенных в некотором порядке. 24-битный BMP-файл — последовательность битов, каждые 24 из которых (ну, почти) определяют цвет какого пикселя. Помимо данных о цвете, BMP-файл также содержит метаданные — информацию о ширине и высоте изображения. Эти метаданные хранятся в начале файла в виде двух структур данных, обычно называемых "заголовками" (не путать с заглавными файлами языка C). Первым из этих заголовков является BITMAPFILEHEADER, его длина составляет 14 байтов (или 14*8 бит). Второй заголовок — BITMAPINFOHEADER (длиной 40 байтов). После этих заголовков идет следует карта битов: массив байтов, тройки из которых представляют цвет пикселя (1, 4 и 16-бит в BMP, но не 24-или 32, у них есть дополнительный заголовок сразу после BITMAPINFOHEADER. Он называется RGBQUAD, массив, определяющий «значение интенсивности» для каждого из цветов в палитре). Однако BMP сохраняет эти тройки в обратном направлении (можем, сказать, как BGR), с 8 битами на синий, 8 битами на зеленый и 8 битами на красный цвета. К слову, некоторые ВМР также сохраняют весь битовый массив в обратном направлении, начиная с верхней строки изображения в конце файла BMP. В нашей задаче мы сохранили ВМР так, как описано здесь, сначала верхнюю строку изображения, затем нижние. Другими словами, мы превратили однобитный смайлик в 24-битный, заменяя черное красным. 24-битный BMP будет хранить этот битовый массив, где 0000ff обозначает красный, а ffffff — белый; мы выделили красным цветом все экземпляры 0000ff. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 4

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 4

Поскольку мы представили эти биты слева направо, сверху вниз, вы сможете увидеть в этих буковках красный смайлик, если немного отойдете от монитора. Напомним, цифра в 16-ричной системе счисления представляет 4 бита. Соответственно, ffffff в шестнадцатеричном варианте фактически означает 111111111111111111111111 в двоичной системе. Ну а теперь притормозите, и не идите дальше до тех пор, пока не будете уверены, что понимаете, почему 0000ff обозначает красный пиксель в 24-битном BMP файле. В окне CS50 IDE раскройте (например, нажатием на маленький треугольник) папку pset4, а в ней — bmp. В этой папке вы найдете smiley.bmp, кликните по файлу дважды, и вы обнаружите там маленький смайлик размером 8х8 пикселей. В выпадающем меню измените масштаб изображения, скажем со 100% до 400%, это позволит вам увидеть увеличенную, но при этом более «замыленную» версию смайлика. Хотя на деле это самое изображение не должно быть замыленным даже при увеличении. Просто CS50 IDE пытается сослужить вам службу (в стиле сериала ЦРУ) тем, что сглаживает картинку (визуально размывая края). Вот как будет выглядеть наш смайлик, если его увеличить без сглаживания: Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 5

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 5

Пиксели превратились в большие квадраты. Продолжим. В терминале переходим в ~/workspace/pset4/bmp. Думаем, вы уже запомнили, как это делать. Давайте изучим выделенные байты в smiley.bmp. Это можно сделать с помощью шестнадцатеричного редактора командной строки, программы xxd. Чтобы его запустить, выполните команду: xxd -c 24 -g 3 -s 54 smiley.bmp Вы должны увидеть то, что приведено ниже; мы снова выделены красным цветом все экземпляры 0000ff. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 6

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 6

На изображении в крайнем левом столбце вы видите адреса в файле, которые эквивалентны смещению от первого байта файла. Все они приведены в шестнадцатеричной системе счисления. Если перевести шестнадцатеричное 00000036 в десятичную систему, получим 54. Таким образом, вы смотрите на 54й байт из smiley.bmp. Напомним, в 24-битных BMP-файлах первые 14 + 40 = 54 байта заполняются метаданными. Так что, если вы хотите увидеть метаданные, выполните следующую команду: xxd -c 24 -g 3 smiley.bmp Если smiley.bmp содержит ASCII-символы, мы их увидим в крайнем правом столбце в xxd вместо всех этих точек. Итак, smiley — 24-битный BMP (каждый из пикселей представлен с помощью 24 ÷ 8 = 3 байт) размером (разрешением) 8х8 пикселей. Каждая строка (или как её называют "Scanline"), таким образом, занимает (8 пикселей)×(3 байта на пиксель) = 24 байта. Это число кратно четырём, и это важно, поскольку файл ВМР хранится немного по-другому, если число байтов в строке не кратно четырём. Так, в small.bmp, еще одном 24-битном BMP-файле в нашей папке, вы можете видеть зеленое поле размером 3х3 пикселя. Если вы откроете его в программе просмотра изображений, вы увидите, что она напоминает картинку, показанную ниже, только поменьше размером. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 7

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 7

Каждая строка в small.bmp, таким образом, занимает (3 пикселя)×(3 байта на пиксель) = 9 байт, что не кратно 4. Чтобы получить длину строки, кратную 4, её забивают дополнительными нулями: между 0 и 3 байтами заполняем каждую строки в 24-битном формате BMP (догадались, почему так?). Для small.bmp, необходимо 3 байта нулей, так как (3 пикселя)×(3 байта на пиксель) + (3 байта заполнения) = 12 байт, которые действительно кратны 4. Чтобы "увидеть" это заполнение, выполните следующее. xxd -c 12 -g 3 -s 54 small.bmp Обратите внимание, мы используем другое значение для -c, чем в случае со smiley.bmp, так что xxd выводит только 4 колонки на этот раз (3 для зеленого квадрата и 1 для заполнения). Для наглядности мы выделили зеленым цветом все экземпляры 00ff00. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 8

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 8

Для контраста воспользуемся xxd для файла large.bmp. Он выглядит точно так же, как small.bmp, только его разрешение — 12х12 пикселей, то есть в четыре раза больше. Выполните команду ниже. Возможно, вам понадобится расширить окно, чтобы избежать переноса. xxd -c 36 -g 3 -s 54 large.bmp Вы увидите что-то в этом роде: Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 9

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 9

Обратите внимание, в этом BMP нет отступлений! Ведь (12 точек)×(3 байта на пиксель) = 36 байт, и это кратно 4. 16-ричный редактор 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, включают в себя хвостовые нули на концах некоторых ВМP. Наша версия copy отбрасывает их, так что не беспокойтесь, если в случае копирования других BMP, которые вы скачали или создали для проверки, копия будет на несколько байт меньше, чем оригинал). Вы можете открыть оба файла в программе Ristretto для просмотра изображений (с помощью двойного щелчка), чтобы подтвердить это визуально. Только вот diff делает это сравнение побайтово, поэтому её зрение острее вашего! Каким образом была создана эта копия? Оказывается, что copy.c связан с bmp.h. Убедимся: открываем bmp.h. Там вы увидите фактические определения этих заголовков, которые мы уже упоминали, адаптированные из собственных реализаций Microsoft. Кроме того, этот файл определяет типы данных BYTE, DWORD, LONG, и WORD, то есть те типы данных, которые, как правило, встречаются в мире Win32 (то есть Windows) программирования. Обратите внимание, они по сути являются псевдонимами для примитивов, с которыми вы (надеемся) уже знакомы. Оказывается, BITMAPFILEHEADER и BITMAPINFOHEADER использовали эти типы. Этот файл также определяет структуру struct, которая называется RGBTRIPLE. Она "инкапсулирует" три байта: один синий, один зеленый и один красный (именно в таком порядке мы будем искать RGB-тройки на диске). Чем полезны эти структуры struct? Напомним, файл представляет собой просто последовательность байтов (или, в конечном итоге, битов) на диске. Однако эти байты, как правило, упорядочены так, что первые из них представляют собой нечто, затем следующие несколько представляют что-то еще, и так далее. "Форматы" файлов существуют потому, что у нас есть стандарты, или правила, по которым определяется, какие байты что означают. Теперь, мы можем просто прочитать файл с диска в оперативной памяти как один большой массив байтов. И мы помним, что байт в позиции [i] представляет собой одну вещь, в то время как байт в точке [j] является чем-то другим. Но почему бы не дать некоторым этих байтов имена, так что мы могли бы легче извлекать их из памяти? Это именно то, в чем нам помогают структуры в bmp.h. Вместо того, чтобы думать о файле, как об одной длинной последовательности байтов, мы видим его разбитым на более понятные блоки — последовательности структур. Напомним, smiley.bmp с разрешением 8х8 пикселей, поэтому занимает 14 + 40 + (8 × 8) × 3 = 246 байт на диске (проверить это можно с помощью команды ls). Вот как это выглядит на диске в соответствии с Microsoft: Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 10

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 10

Видим, что порядок имеет значение, когда дело доходит до членов структур struct. Байт 57 является rgbtBlue (а не, скажем, rgbtRed), потому что rgbtBlue определен в RGBTRIPLE первым. К слову, использование нами атрибута packed гарантирует, что clang не попытается "выравнивать по слову" члены (при этом адрес первого байта каждого члена кратен 4), чтобы мы не получили в наших структурах дыры, которые вовсе не существуют на диске. Двигаемся дальше. Найдите URL, которые соответствуют BITMAPFILEHEADER и BITMAPINFOHEADER, согласно комментариям в bmp.h. Внимание, торжественный момент: вы начинаете использовать MSDN (Microsoft Developer Network)! Вместо того, чтобы дальше скроллить copy.c, лучше ответьте на несколько вопросов, чтобы разобраться, как в нем работает код. Как всегда, команда man — ваш верный друг, а теперь еще и MSDN. Если вы не знаете ответов на вопросы, погуглите и поразмышляйте. Вы также можете обратиться к файлу stdio.h в https://reference.cs50.net/. Также вы можете запустить copy в debug50 и проделать следующее:

Установите точку останова (брейкпойнт) в main (кликнув слева от линейки с номерами строк main).
В терминале tab, перейдите по ссылке ~/workspace/pset4/bmp, и откомпиллируйте copy.c в программу copy с помощью make.
Выполните 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-битную архитектуру)?
Чем (в ASCII, в десятичной или шестнадцатеричной системе счисления) должны быть первые два байта BMP файла? (ведущие байты, которые используются для идентификации формата файла (с высокой вероятностью) часто называют «магическими числами»).
Какая разница между bfSize и biSize?
Что означает отрицательное значение biHeight?
Какое поле в BITMAPINFOHEADER определяет глубину цвета в BMP (то есть бит на пиксель)?
Почему функция fopen может вернуть NULL в copy.c 37?
Почему третий аргумент в fread в нашем коде равен 1?
Какое значение в copy.c 70 определяет padding, если bi.biWidth равно 3?
Какие действия выполняет fseek?
Что такое SEEK_CUR?

Возвращаемся к мистеру Бодди. Задание:

Напишите программу под названием whodunit в файле с именем whodunit.c, которая показывает рисунок мистера Бодди. Хмммм, что? Как и copy, программа должна принять ровно два аргумента командной строки, и если вы выполните вашу программу как показано ниже, то результат сохранится в verdict.bmp, в котором рисунок мистера Бодди не будет зашумлен. ./whodunit clue.bmp verdict.b Позвольте нам предположить, что вы начнете решать эту тайну, выполнив команду ниже. cp copy.c whodunit.c Вы можете быть поражены тем, как много строк кода нужно вам написать, чтобы помочь мистеру Бодди. В smiley.bmp ничего лишнего не скрыто, так что не стесняйтесь проверить программу на этом файле. Он небольшой, и вы можете сравнить вывод вашей программы и вывод xxd в процессе разработки (а, может, всё-таки в smiley.bmp что-то спрятано? На самом деле нет). Кстати, решить эту задачку можно по-разному. Как только вы идентифицируете рисунок мистера Бодди, он упокоится в мире. Поскольку whodunit может быть реализован несколькими способами, вы не сможете проверить правильность реализаций с check50. И пусть это вам испортит удовольствие, но решение ассистентов также недоступно для задачи whodunit. Наконец, в файле In ~/workspace/pset4/questions.txt, ответьте на следующий вопрос: Whodunit? //ктоэтосделал?

resize

Ну а теперь — следующее испытание! Давайте напишем в файле resize.c программу, называемую resize. Она будет менять размеры несжатого 24-битного изображения BMP с шагом в n. Ваше приложение должно принимать ровно три аргумента командной строки, причем первый (n) должен быть целым числом не более 100, второй - именем файла, который будет изменен, а третий - названием сохраненной версии измененного файла. Usage: ./resize n infile outfile С помощью такой программы мы могли бы создать large.bmp из файла small.bmp путем изменения размера последнего на 4 (т.е. путем умножения и ширины, и высоты на 4), как показано ниже. ./resize 4 small.bmp large.bmp Для простоты можно начать задание скопировав еще раз copy.c и назвав копию resize.c. Но сначала задайте себе вопросы и ответьте на них: что значит изменить размер BMP (можно предположить, что n помноженное на размер файла infile не будет превышать 232 - 1). Определите, какие поля в BITMAPFILEHEADER и BITMAPINFOHEADER вам нужно изменить. Подумайте, нужно ли вам добавить или удалить поля scanlines. И, да, скажите спасибо, что мы не предлагаем вам рассмотреть все возможные значения 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 Еще лучше, если вы захотите сравнить свои заголовки с заголовками файлов ассистентов CS50. Вы можете выполнить команды внутри вашей директории ~/workspace/pset4/bmp (подумайте, что делает каждая команда).

./resize 4 small.bmp student.bmp

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

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

Если вы использовали malloc, не забудьте использовать free, чтобы предотвратить утечку памяти. Попробуйте использовать valgrind чтобы проверить наличие утечек.

Как решать?

Открыть файл, который нам нужно увеличить, а также создать и открыть новый файл, в котором будет записано увеличенное изображение;
обновить информацию заголовка для выходного файла. Поскольку наше изображение в формате BMP и мы меняем его размер, нам нужно записать заголовок нового файла с новыми размерами. Что поменяется? Размер файла, а также размер изображения — его ширина и высота.

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 11

Если мы заглянем в описание заголовка, то увидите переменную biSizeImage. Она указывает на общий размер изображения в байтах, biWidth — ширина изображения минус выравнивание, biHeight — высота. Эти переменные находятся в структурах BITMAPFILEHEADER и BITMAPINFOHEADER. Вы можете найти их, если откроете файл bmp.h. Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 12

Гарвард CS50: задания четвертой недели (лекции 9 и 10) - 12

В описании структуры BITMAPINFOHEADER есть список переменных. Для записи заголовка выходного файла нужно будет поменять значение высоты и ширины. Но есть также вероятность, что позднее вам понадобятся и оригинальные высота и ширина исходного файла. Поэтому лучше сохранить и то, и другое. Будьте внимательны к названиям переменных, чтобы случайно не записать ошибочные данные в заголовок выходного файла.

Читаем исходящий файл, строка за строкой, пиксель за пикселем. Для этого мы снова обращаемся к нашей библиотеке файлового ввода/вывода и функции fread. Она принимает указатель на структуру, которая будет содержать прочитанные байты, размер одного элемента, который мы собираемся прочитать, количество таких элементов и указатель на файл, из которого мы будем читать.
Увеличиваем каждую строку по горизонтали согласно заданному масштабу, записываем результат в выходной файл.

Как мы записываем файлы? У нас есть функция fwrite, которой мы передаем показатель на структуру, где находятся данные для записи в файл, размер элемента, их количество и указатель на выходной файл. Для организации цикла можем воспользоваться уже привычным нам циклом for.
Заполнить пробелы! Если количество пикселей в строке не кратно четырем, мы должны добавить «выравнивание» – нулевые байты. Нам понадобится формула для расчета размера выравнивания. Для записи нулевых байтов в выходной файл вы можете использовать функцию fputc, передав ей символ, который вы хотите записать и указатель на выходной файл.

Теперь, когда мы растянули строку по горизонтали и добавили выравнивание в выходной файл, нам нужно переместить текущую позицию в исходящем файле, поскольку нам нужно перескочить через выравнивание.
Увеличить размер по вертикали. Это сложнее, но мы можем использовать пример кода из файла copy.c (copy.c открывает исходящий файл, записывает заголовок в выходной файл, читает изображение из исходного файла по строкам, пиксель за пикселем, и записывает их в файл выхода). Исходя из этого, первым делом можно выполнить такую команду: cp copy.c resize.c

Растянуть изображение по вертикали означает скопировать каждую строку несколько раз. Есть несколько разных способов это сделать. Например, с помощью перезаписи, когда мы сохраняем все пиксели одной строки в памяти и в цикле записываем эту строку в выходной файл столько раз, сколько это нужно. Другой метод – перекопирование: после чтения строки исходящего файла, записи его в выходной файл и выравнивания вернуться функцией fseek назад в начало строки в исходящем файле и повторить все заново несколько раз.