Підготовка до роботи
Як завжди, спочатку відкрийте вікно терміналу та виконайте команду.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. На зображенні в крайньому лівому стовпці ви бачите адресаи у файлі, які еквівалентні зміщенню від першого байта файлу. Усі вони наведені у шістнадцятковій системі числення. Якщо перевести шістнадцяткове 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 пікселя. Якщо ви відкриєте його у програмі перегляду зображень, ви побачите, що вона нагадує картинку, показану нижче, лише меншою за розміром. Кожен рядок в 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. Для контрасту скористаємося xxd для файлу large.bmp . Він виглядає так само, як small.bmp, Тільки його роздільна здатність - 12х12 пікселів, тобто в чотири рази більше. Виконайте команду нижче. Можливо, вам доведеться розширити вікно, щоб уникнути перенесення. xxd -c 36 -g 3 -s 54 large.bmp
Ви побачите щось таке: Зверніть увагу, в цьому 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 використовували ці типи. Цей файл також визначає структуру структури, яка називається RGBTRIPLE. Вона "інкапсулює" три байти: один синій, один зелений і один червоний (саме в такому порядку ми шукатимемо RGB-трійки на диску). Чим корисні ці структури структур? Нагадаємо, файл є просто послідовністю байтів (або, зрештою, бітів) на диску. Однак ці байти, як правило, упорядковані так, що перші з них є чимось, потім наступні дещо представляють щось ще, і так далі. "Формати" файлів існують тому, що ми маємо стандарти, або правила, за якими визначається, які байти що означають. Тепер ми можемо просто прочитати файл з диска в оперативній пам'яті як один великий масив байтів. І ми пам'ятаємо, що байт у позиції [i] є однією річ, тоді як байт у точці [j] є чимось іншим. Але чому б не дати деяким цих байтів імена, то ми могли б легше витягувати їх з пам'яті? Це саме те, в чому нам допомагають структури bmp.h. Замість того, щоб думати про файл як про одну довгу послідовність байтів, ми бачимо його розбитим на більш зрозумілі блоки — послідовності структур. Нагадаємо, smiley.bmp з роздільною здатністю 8х8 пікселів, тому займає 14+40+(8×8)×3=246 байт на диску (перевірити це можна за допомогою команди ls). Ось як це виглядає на диску відповідно до Microsoft: Бачимо, що порядок має значення, коли справа доходить до членів структур 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/.
-
Встановіть точку зупинки (брейкпойнт) у 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 (подумайте, що робить кожна команда). Якщо ви використовували
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, і ми змінюємо його розмір, нам потрібно записати заголовок нового файлу з новими розмірами. Що зміниться? Розмір файлу, а також розмір зображення – його ширина та висота.
-
Читаємо вихідний файл, рядок за рядком, піксель за пікселем. Для цього ми знову звертаємось до нашої бібліотеки файлового вводу/виводу та функції 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, 0xe, 0xe, 0xe0. Іншими словами, перші чотири біти четвертого байта JPEG-файлу -1110. Швидше за все, якщо ви знайдете один із цих шаблонів на диску, на якому зберігалися фотографії (наприклад, моя картка пам'яті), це і буде початок JPEG-файлу. Звичайно, ви можете зіткнутися з цим на якому диску суто випадково, відновлення даних не можна назвати точною наукою.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ