undefined

Задание №1: whodunit или «Кто это сделал?»

Harvard CS50
4 уровень , 5 лекция
Открыта

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

  1. Какое количество цветов поддерживает каждый формат?
  2. Какой из форматов поддерживает анимацию?
  3. В чём разница между сжатием с потерями и без потерь?
  4. Какой из перечисленных форматов использует сжатие с потерями?

    Тем, кто владеют английским, советуем обратиться к статье от МИТ.

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

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

А теперь — к нашей истории, плавно перетекающей в первое задание четвертого уровня.

Добро пожаловать в Tudor Mansion! Хозяин поместья, мистер Джон Бодди, скоропостижно ушёл от нас, пав жертвой загадочной игры. Чтобы выяснить, что произошло, вы должны определить whodunit (от искажённого английского Who’d done it? — «Кто это сделал?»).

К вашему сожалению (и еще большему сожалению для мистера Бодди), единственное доказательство, которое у вас есть, — 24-битный BMP-файл clue.bmp. Именно его содержимое вы видите ниже. Мистер Бодди успел сделать и сохранить на своем компьютере в свои последние минуты. В файле есть скрытое среди красного «шума» изображения whodunit («ктоэтосделал»). Теперь необходимо поработать над решением как настоящий технический специалист.

Задание №1: whodunit или «Кто это сделал?» - 1

Но, для начала, некоторая информация.

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

Задание №1: whodunit или «Кто это сделал?» - 2

Изображения, представленные таким образом — это просто карта битов (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 (языка разметки и помогающих ему таблиц стилей, с помощью которых создают веб-страницы) модели цветов устроены таким же образом. Если интересно, изучите ссылку для получения более подробной информации.

Теперь давайте подойдем к проблеме более технически. Вспомним о том, что файл — это просто последовательность битов, расположенных в некотором порядке. 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.

Задание №1: whodunit или «Кто это сделал?» - 3

Поскольку мы представили эти биты слева направо, сверху вниз, вы сможете увидеть в этих буковках красный смайлик, если немного отойдете от монитора.

Напомним, одна цифра в 16-ричной системе счисления — это 4 бита. Соответственно, ffffff в шестнадцатеричном варианте фактически означает 111111111111111111111111 в двоичной системе.

Ну а теперь притормозите, и не идите дальше до тех пор, пока не будете уверены, что понимаете, почему 0000ff обозначает красный пиксель в 24-битном BMP файле.

В окне CS50 IDE (или в «Виртуальной лаборатории») раскройте папку pset4, а в ней — bmp. Там вы найдете smiley.bmp. Кликните по файлу дважды, и вы обнаружите маленький смайлик размером 8х8 пикселей. В выпадающем меню измените масштаб изображения, скажем с 100% до 400%. Это позволит вам увидеть увеличенную, но при этом более «замыленную» версию смайлика. Хотя на деле это самое изображение не должно быть замыленным даже при увеличении. Просто CS50 IDE пытается сослужить вам службу (в стиле сериала ЦРУ) тем, что сглаживает картинку (визуально размывая края). Вот как будет выглядеть наш смайлик, если его увеличить без сглаживания:

Задание №1: whodunit или «Кто это сделал?» - 4

Пиксели превратились в большие квадраты.

Продолжим. В терминале переходим в папку pset4/bmp. Думаем, вы уже запомнили, как это делать. Давайте изучим выделенные байты в smiley.bmp. Это можно сделать с помощью шестнадцатеричного редактора командной строки, программы xxd. Чтобы его запустить, выполните команду:

xxd -c 24 -g 3 -s 54 smiley.bmp

Вы должны увидеть то, что приведено ниже; мы снова выделены красным цветом все экземпляры 0000ff.

Задание №1: whodunit или «Кто это сделал?» - 5

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

Задание №1: whodunit или «Кто это сделал?» - 6

Каждая строка в 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.

Задание №1: whodunit или «Кто это сделал?» - 7

Для контраста воспользуемся xxd для файла large.bmp. Он выглядит точно так же, как small.bmp, только его разрешение — 12х12 пикселей, то есть в четыре раза больше. Выполните команду ниже. Возможно, вам понадобится расширить окно, чтобы избежать переноса.

xxd -c 36 -g 3 -s 54 large.bmp

Вы увидите что-то в этом роде:

Задание №1: whodunit или «Кто это сделал?» - 8

Обратите внимание, в этом 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:

Задание №1: whodunit или «Кто это сделал?» - 9

Видим, что порядок имеет значение, когда дело доходит до членов структур struct. Байт 57 является rgbtBlue (а не, скажем, rgbtRed), потому что rgbtBlue определен в RGBTRIPLE первым. К слову, использование нами атрибута packed гарантирует, что clang не попытается «выравнивать по слову» члены (при этом адрес первого байта каждого члена кратен 4), чтобы мы не получили в наших структурах дыры, которые вовсе не существуют на диске.

Двигаемся дальше. Найдите URL, которые соответствуют BITMAPFILEHEADER и BITMAPINFOHEADER, согласно комментариям в bmp.h. Внимание, торжественный момент: вы начинаете использовать MSDN (Microsoft Developer Network)!

Вместо того, чтобы дальше скроллить copy.c, лучше ответьте на несколько вопросов, чтобы разобраться, как в нем работает код. Как всегда, команда man — ваш верный друг, а теперь еще и MSDN. Если вы не знаете ответов на вопросы, погуглите и поразмышляйте. Вы также можете обратиться к файлу stdio.h в reference.cs50.net/.

Также вы можете запустить copy в debug50 и проделать следующее:

  1. Установите точку останова (брейкпойнт) в main (кликнув слева от линейки с номерами строк main).
  2. В терминале tab, перейдите по ссылке ~/workspace/pset4/bmp, и откомпилируйте copy.c в программу copy с помощью make.
  3. Выполните debug50 copy smiley.bmp copy.bmp, это откроет панель дебагера справа.
  4. Пройдитесь пошагово по программе, используя панель справа. Обратите внимание на 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, ответьте на следующий вопрос:

18. Whodunit? //ктоэтосделал?

Комментарии (43)
Чтобы просмотреть все комментарии или оставить свой,
перейдите в полную версию
Александр # 0 уровень
9 апреля 2021
Задание из разряда "облазь интернет, чтобы понять, про что тут" :) Посоветую статью на русском: Википедия - формат BMP. После неё гораздо легче понять Microsoft Docs - те ссылки в файле bmp.h, которые рекомендуют прочитать в задании. А ещё простое объяснение, что за Padding в коде: Padding structure
Anonymous #2562337 1 уровень
30 марта 2021
можно весь "чисто" красный поменять на цвет предыдущего пикселя. и в серый все, что не белый )
Yulee 4 уровень, Barcelona
23 марта 2021
А у меня вот это почему-то выводит: ~/pset4/bmp/ $ ./copy smiley.bmp copy.bmp bash: ./copy: No such file or directory ~/pset4/bmp/ $ diff smiley.bmp copy.bmp diff: copy.bmp: No such file or directory
Александр 23 уровень, Москва
18 марта 2021
Специально для тех кто не силен в английском поможет разобраться вот это видео - Объяснение с переводом А вообще точите скилл английского - потому что без него никак...
Samurai 10 уровень
7 марта 2021
Советую это видео к просмотру - https://www.youtube.com/watch?v=P1K0ZNGczsk
NirgranthaPranesh 0 уровень
4 декабря 2020
Rick Astley
Ихтияр Кадыров 1 уровень, Шымкент
4 ноября 2020
Ярослав 0 уровень, Киев
10 сентября 2020
Вот что удалось вытянуть по максимуму. Код не универсальный, но смысл его универсальный. Тоесть просто меняя параметры if и powerOfColor доходим до лучшего результата. Если надо универсальный код, то используем одни оператор if и общий показатель powerOfColor. Использовал подряд просто операторы if для точной работы со всеми тенями. Главный по сути там цвет красный, остальные просто должны следовать за ним. 1 - Сначала убираем красный шум, это бесполезные для нас пиксели RGB 255.0.0 2 - Для того что бы увидеть картинку хватило бы и одного | двух оператора if, но если хочется пообрабативать картинку в коде(как мне хотелось), то можно использовать больше операторов if для каждого диапазона красного цвета. Помог понять всё фотошоп, когда там подробно посидел с пипеткой и посмотрел какие цвета где как смешиваются. П,С, Кстати у меня картинка созданная программой не открывается в фотошопе. Возможно из-за порядка заполнения массива в Си... Мой кусок кода с самого глубокого цикла, где ничего не менял просто вставил свой код с операторами. Там я добавил только переменную для удобства и операторы if (здесь 3, в оригинале у меня их 5):
Ярослав 0 уровень, Киев
8 сентября 2020
Там везде в тексте ошибка на счет кратности 4-оьм (из-за перевода наверное). 🕵 Правильно так: Ряды, независимо от размера ячеек, обязательно должны дополняться нулями до кратного четырём байтам размера[7]. Из-за этого, при некратной ширине изображения, в конце рядов могут оказываться неиспользуемые биты или целые байты. Но благодаря гарантированной кратности размера ряда, обработку можно производить 8-, 16- или 32-битными машинными словами, по выбору. BMP Wikipedia
АМ 2 уровень, Kubinka
7 марта 2020
решение оказалось проще чем кажется, код кидать не буду, на ютубе можно найти решение