Задание №3: recover

Harvard CS50

4 уровень , 7 лекция

Открыта

В ожидании задачника четвертого уровня я несколько дней просматривал фотографии, сохраненные моей цифровой камерой на карту памяти объемом 1 GB CompactFlash (CF). Фотки записаны в формате JPEG. Только не говорите мне, пожалуйста, что на самом деле я провел последние несколько дней на 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-файла. Конечно, вы можете столкнуться с такой комбинацией на диске случайно… Восстановление данных нельзя назвать точной наукой.

Как решать

Открыть файл с содержимым карты памяти
Найти начало JPEG-файла. Все файлы на этой карте являются картинками в JPEG-формате.

О маркерах JPEG вы уже знаете:

Важно (и приятно) осознавать, что каждый JPEG-файл сохраняется в памяти единым блоком, а сами файлы следуют один за другим. Изобразим схематическую карту памяти. Каждый прямоугольник — блок длиной 512 байт. Серые прямоугольники — области, где файлы JPEG отсутствуют, звездочками обозначено начало JPEG-файла. Полагаем, что серых блоков между файлами у нас нет.

Как нам прочитать эти данные, эти 512 байтов, чтобы сравнить их начало с заголовком JPEG? Можно воспользоваться уже знакомой нам функцией fread, которая принимает указатель на структуру данных, куда будут записаны прочитанные байты, а также размер элемента, который прочитывается, количество таких элементов и указатель на файл, из которого мы читаем данные.

Мы хотим прочитать 512 байт и сохранить их в буфере. Им будет служить указатель &data, а указатель inptr будет указывать на открытый файл с содержимым карты памяти. Итак, вернемся к структуре нашего файла, в котором сохранено содержимое карты памяти. Мы собираемся читать блоки по 512 байт и сохранять их в буфер, пока не будем знать, что с этим буфером делать. Сначала буфер пуст. Мы читаем первый блок данных, сравниваем его с маркером JPEG и идем дальше.

Как только вы находите начало JPEG, вы создаете новый файл на диске. Это можно сделать с помощью функции sprint, в которую передается шаблон и аргумент.

…и записываете в него порциями по 512 байт, пока не найдете начало следующего JPEG с помощью функции fwrite.

«Порции» можно записывать, пока исходный файл карты памяти не закончится. fread возвращает количество элементов размера size, которые были успешно прочитаны. В идеале size должно совпасть c number. Нам нужно организовать условный оператор, который позволит посчитать, сколько элементов на самом деле было прочитано.

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (43)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Anonymous #3114188 Уровень 2

23 октября 2022

Всё оказалось куда проще, чем кажется. С самого начала завернул не туда, неправильно построил алгоритм и все пошло по известному месту. Потом подсмотрел чужую версию на гитхабе (https://gist.github.com/CraigRodrigues/8f831e9ea1003d9ad14f608d24cc1ba3), забросил программирование на сутки и начал писать все заново, запомнив из чужой версии лишь поверхностный алгоритм. Далее пошло уже куда проще, пусть и были некоторые проблемы. Код будет в ответах.

Александр # Уровень 0

17 апреля 2021

Снова нашлась досадная ошибка при переводе с английского: «Порции» можно записывать, пока исходный файл карты памяти не закончится. fread возвращает количество элементов размера size, которые были успешно прочитаны. В идеале size должно совпасть c number. Конечно же значение fread должно совпадать с number

Александр Уровень 25

30 марта 2021

Задача оказалась, как бы это странно не показалось, легче для понимания, чем две предыдущие...

045.jpeg

Андрей Уровень 0

20 июля 2020

048.jpeg

Даниил Уровень 41 Master

14 февраля 2020

Конечно же решил не без копирования частей кода из предыдущих заданий и подглядываний в готовый код что бы убедиться что двигаюсь в правильном направлении, но минут 20 убил на то что не мог понять почему то ни востанавливает ничего, то сохраняется только одна фотография (как выяснилось потом это была последняя из всех фотография). Всего их 50 штук. В общем ошибка была в том что процессе изменения кода забыл добавлять единичку к каждому новому названию файла, в итоге они доблесно перезаписывались. Подсказка: не стоит перебирать по одному байту весь файл страхуясь от того что пропустите начало новой картинки. Это учебное задание и всё сделано ровно так что если вы будете считывать ровно по 512 байт, то вы не пропустите ни одной фотографии. Просто в начале идут "пустые байты" (вроде как 2 раза по 512 нужно прочитать таких пустых), а далее начинаються картинки. В общем считываете по 512 байт за раз, когда первый раз встретите необходимую последовательность байт которые указывают на начало jpg файла, то записывайте всё подряд аж до тех пор пока снова не встретите эту же последовательность. При этом старый файл нужно закрыть, создать новый и повторять так пока не закончаться байты в исходном файле.

PinGantar Уровень 0

9 февраля 2019

Сначала задача показалась сложной , но на деле она намного проще двух предыдущих . Главное не бояться ))

Дмитрий Шакаримов Уровень 0

26 января 2019

Объясните идиоту. Если я правильно понял, мы делим карту на сегменты размером 512 байт. Мы находим jpeg файл по первым 3 байтам сегмента. Решение делением на сегменты мы упрощаем работу, чтобы не смотреть карту по байтово, следовательно выполнять поиск по сегменту -- глупо. Но как мы можем быть уверенны в том, что нужные нам 3 байта будут в начале сегмента, а не в середине или в конце? Алгоритм ниже сработает только для card.raw из задачника или оно подойдёт и для поиска на случайном носителе памяти?

enot_00 Уровень 1

7 ноября 2018

Только на основании лекций, решить эту задачу нереально. В решении внизу достаточно "читерства": использование материала, которого доселе не было в лекциях. А ниже вообще вы*боны: задача действительно сложная, даже если предыдущие задачи давались достаточно легко. Предыдущие 2 задачи - элементарщина, по сравнению с этой. Так что без паники)

eight-bit-samurai Уровень 17

22 сентября 2018

Мой вариант решения. Кстати, при просмотре raw-файла обнаружил ссылку на довольно интересный сайт.


#include <stdio.h>

#define BUF_SIZE 512

int main()
{
    FILE *rawFile = fopen("card.raw", "r");
    if (!rawFile) {
        printf("Could not open \"card.raw\".\n");
        return 1;
    }

    FILE *jpgFile = NULL;
    char jpgName[8];
    unsigned char jpgID = 0;
    unsigned char buf[BUF_SIZE];

    while (fread(buf, BUF_SIZE, 1, rawFile)) {
        if (buf[0] == 0xFF && buf[1] == 0xD8 && buf[2] == 0xFF) {
            if (jpgFile)
                fclose(jpgFile);

            sprintf(jpgName, "%03d.jpg", jpgID++);
            jpgFile = fopen(jpgName, "w");
            if (!jpgFile) {
                printf("Could not create \"%s\".\n", jpgName);
                fclose(rawFile);
                return 2;
            }
        }

        if (jpgFile)
            fwrite(buf, BUF_SIZE, 1, jpgFile);
    }

    fclose(jpgFile);
    fclose(rawFile);
    return 0;
}

Евгений Уровень 1

23 июня 2018

Одно из самых легких заданий курса. У всех получилось 49 фото?