
Подготовка к работе
Как всегда, сначала откройте окно терминала и выполните команду.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?
Что можно сделать, чтобы обеспечить (с высокой вероятностью) невозможность восстановления удаленных файлов?




xxd -c 24 -g 3 -s 54 smiley.bmp
Вы должны увидеть то, что приведено ниже; мы снова выделены красным цветом все экземпляры 0000ff.

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 пикселя. Если вы откроете его в программе просмотра изображений, вы увидите, что она напоминает картинку, показанную ниже, только поменьше размером.

xxd -c 12 -g 3 -s 54 small.bmp
Обратите внимание, мы используем другое значение для -c, чем в случае со smiley.bmp, так что xxd выводит только 4 колонки на этот раз (3 для зеленого квадрата и 1 для заполнения). Для наглядности мы выделили зеленым цветом все экземпляры 00ff00.

xxd -c 36 -g 3 -s 54 large.bmp
Вы увидите что-то в этом роде:

./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:

Установите точку останова (брейкпойнт) в 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? Наберите следующую команду:
~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 и мы меняем его размер, нам нужно записать заголовок нового файла с новыми размерами. Что поменяется? Размер файла, а также размер изображения — его ширина и высота.


Читаем исходящий файл, строка за строкой, пиксель за пикселем. Для этого мы снова обращаемся к нашей библиотеке файлового ввода/вывода и функции fread. Она принимает указатель на структуру, которая будет содержать прочитанные байты, размер одного элемента, который мы собираемся прочитать, количество таких элементов и указатель на файл, из которого мы будем читать.
Увеличиваем каждую строку по горизонтали согласно заданному масштабу, записываем результат в выходной файл.
Как мы записываем файлы? У нас есть функция fwrite, которой мы передаем показатель на структуру, где находятся данные для записи в файл, размер элемента, их количество и указатель на выходной файл. Для организации цикла можем воспользоваться уже привычным нам циклом for.
Заполнить пробелы! Если количество пикселей в строке не кратно четырем, мы должны добавить «выравнивание» – нулевые байты. Нам понадобится формула для расчета размера выравнивания. Для записи нулевых байтов в выходной файл вы можете использовать функцию fputc, передав ей символ, который вы хотите записать и указатель на выходной файл.
Теперь, когда мы растянули строку по горизонтали и добавили выравнивание в выходной файл, нам нужно переместить текущую позицию в исходящем файле, поскольку нам нужно перескочить через выравнивание.
Увеличить размер по вертикали. Это сложнее, но мы можем использовать пример кода из файла copy.c (copy.c открывает исходящий файл, записывает заголовок в выходной файл, читает изображение из исходного файла по строкам, пиксель за пикселем, и записывает их в файл выхода). Исходя из этого, первым делом можно выполнить такую команду: cp copy.c resize.c
Растянуть изображение по вертикали означает скопировать каждую строку несколько раз. Есть несколько разных способов это сделать. Например, с помощью перезаписи, когда мы сохраняем все пиксели одной строки в памяти и в цикле записываем эту строку в выходной файл столько раз, сколько это нужно. Другой метод – перекопирование: после чтения строки исходящего файла, записи его в выходной файл и выравнивания вернуться функцией fseek назад в начало строки в исходящем файле и повторить все заново несколько раз.
Открыть файл с содержимым карты памяти.
Найти начало JPEG-файла. Все файлы на этой карте являются картинками в JPEG-формате.
recover
В ожидании задачника четвертой недели я провел последние несколько дней за просмотром фотографий, сохраненных моей цифровой камерой в формате JPEG на карте памяти объемом 1 GB CompactFlash (CF). Только не говорите мне, пожалуйста, что на самом деле я провел последние несколько дней на Facebook вместо этого. К сожалению, мои навыки владения компьютером оставляют желать лучшего, и я, сам того не ведая, случайно удалил все фоточки! К счастью, мире компьютеров, "удален" как правило, не равняется "убит". Мой компьютер настаивает на том, что карта-памяти теперь пуста, но я-то знаю, что он лжёт. Задание: Напишите в ~/workspace/pset4/jpg/recover.c программу, которая восстановит эти фотографии. Хммм. Ладно, вот еще кое-какое уточнение. Несмотря на то, JPEG-формат сложнее, чем BMP, JPEG имеет "подписи", шаблоны байтов, которые помогут отличить их от других форматов файлов. Большинство JPEG-файлов начинается со следующих трех байтов:0xff 0xd8 0xff
От первого байта до третьего, слева направо. Четвертый байт, скорее всего, будет одной из следующих комбинаций: 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,0xe8, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef. Иными словами, первые четыре бита четвертого байта JPEG-файла —1110.
Скорее всего, если вы найдете один из этих шаблонов на диске, на котором хранились фотографии (например, моя карта памяти), это и будет начало JPEG-файла. Конечно, вы можете столкнуться с этим на каком диске чисто случайно, восстановление данных нельзя назвать является точной наукой.
Как решать



ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Стоит ли ждать переводов материалов к следующим неделям?
з.ы.
Спасибо за перевод!
В чем преимущество кратности 4-м? Оно на уровне проца?
Ряды, независимо от размера ячеек, обязательно должны дополняться нулями до кратного четырём байтам размера[7]. Из-за этого, при некратной ширине изображения, в конце рядов могут оказываться неиспользуемые биты или целые байты. Но благодаря гарантированной кратности размера ряда, обработку можно производить 8-ми, 16-ти или 32-битными машинными словами, по выбору.