JavaRush /Курсы /Harvard CS50 /Задание №3: recover

Задание №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 вы уже знаете:

Задание №3: recover - 1

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

Задание №3: recover - 2

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

Задание №3: recover - 3

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

  • Как только вы находите начало JPEG, вы создаете новый файл на диске. Это можно сделать с помощью функции sprint, в которую передается шаблон и аргумент.
  • …и записываете в него порциями по 512 байт, пока не найдете начало следующего JPEG с помощью функции fwrite.
  • Задание №3: recover - 4
  • «Порции» можно записывать, пока исходный файл карты памяти не закончится. fread возвращает количество элементов размера size, которые были успешно прочитаны. В идеале size должно совпасть c number. Нам нужно организовать условный оператор, который позволит посчитать, сколько элементов на самом деле было прочитано.
  • Задание №3: recover - 5
    Комментарии (41)
    ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
    ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
    FeatHonnar Уровень 16
    23 октября 2022
    Всё оказалось куда проще, чем кажется. С самого начала завернул не туда, неправильно построил алгоритм и все пошло по известному месту. Потом подсмотрел чужую версию на гитхабе (https://gist.github.com/CraigRodrigues/8f831e9ea1003d9ad14f608d24cc1ba3), забросил программирование на сутки и начал писать все заново, запомнив из чужой версии лишь поверхностный алгоритм. Далее пошло уже куда проще, пусть и были некоторые проблемы. Код будет в ответах.
    FeatHonnar Уровень 16
    23 октября 2022
    
    /**
     * recover.c
     *
     * Computer Science 50
     * Problem Set 4
     *
     * Recovers JPEGs from a forensic image.
     */
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    
    #define BUF 512
    
    typedef uint8_t BYTE;
    
    int main(int argc, char* argv[])
    {
        // Проверка на аргумент
        if (argc != 2) {
            printf("Введите названия входного файла");
            return 1;
        }
    
        // Открываем карту памяти (вернее ее файл)
        char* infile = argv[1];
        FILE* card = fopen(infile, "r");
        if (card == NULL)
        {
            printf("Не удалось открыть %s.\n", infile);
            return 2;
        }
    
        // Создаем файл для изображения
        FILE* jpg;
    
        // Создаем буффер
        BYTE buf[BUF];
    
        // Создаем счетчик файлов
        int fcount = 0;
    
        while (fread(&buf, BUF, 1, card) == 1) // Сохраняем блок в буффер, параллельно проверяя файл на конец
        {
            if (buf[0] == 0xff && buf[1] == 0xd8 && buf[2] == 0xff && (buf[3] > 0xdf && buf[3] < 0xf0)) // Проверяем блок на jpg заголовок
            {
                if (fcount > 0) {
                    // Закрываем действующий jpg файл
                    fclose(jpg);
                }
    
                // Прибавляем счетчик файлов
                fcount++;
    
                // Создаем новый jpg файл
                char outfile[7];
                sprintf(outfile, "%i.jpg", fcount);
                jpg = fopen(outfile, "w");
    
                // Переписываем буффер в новый jpg файл
                fwrite(&buf, BUF, 1, jpg);
            }
            else if (fcount > 0) // Если у нас уже открыт какой-то файл
            {
                // Переписываем буффер в действующий jpg файл
                fwrite(&buf, BUF, 1, jpg);
            }
        }
        // Цикл кончается и, соответственно, файл тоже
        fclose(card);
        fclose(jpg);
    }
    
    FeatHonnar Уровень 16
    23 октября 2022
    Подмечу, ибо сам это не мог понять сначала. В цикле while мы работаем ТОЛЬКО с теми блоками, которые относятся к файлу. Т.е., либо мы создаем новое изображение (перед этим закрыв прошлое, если нужно), либо вписываем в уже открытое. Иначе в цикле не происходит ровным счётом ничего.
    Александр # Уровень 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 файла, то записывайте всё подряд аж до тех пор пока снова не встретите эту же последовательность. При этом старый файл нужно закрыть, создать новый и повторять так пока не закончаться байты в исходном файле.
    Jakov Уровень 1
    28 мая 2021
    Эта задачка действительно попроще предыдущих, я больше времени убил на генерирование имен файлов, чем на сам алгоритм перезаписи. Невнимательно прочитал текст лекции, поэтому подсказку про sprintf не увидел. Стандартные вещи типа strcat почему-то не заработали.
    PinGantar Уровень 0
    9 февраля 2019
    Сначала задача показалась сложной , но на деле она намного проще двух предыдущих . Главное не бояться ))
    26 января 2019
    Объясните идиоту. Если я правильно понял, мы делим карту на сегменты размером 512 байт. Мы находим jpeg файл по первым 3 байтам сегмента. Решение делением на сегменты мы упрощаем работу, чтобы не смотреть карту по байтово, следовательно выполнять поиск по сегменту -- глупо. Но как мы можем быть уверенны в том, что нужные нам 3 байта будут в начале сегмента, а не в середине или в конце? Алгоритм ниже сработает только для card.raw из задачника или оно подойдёт и для поиска на случайном носителе памяти?
    eight-bit-samurai Уровень 17
    26 января 2019
    В задаче ясно сказано, что картинки следуют друг за другом блоками по 512 байт без промежутков между ними. Естественно, алгоритм ниже сработает только для card.raw из задачника. Можно было бы написать более универсальный и медленный алгоритм, побайтово считывающий и записывающий данные, но зачем, когда цель этой задачи дать начальные представления о работе с файлами и указателями?
    enot_00 Уровень 1
    7 ноября 2018
    Только на основании лекций, решить эту задачу нереально. В решении внизу достаточно "читерства": использование материала, которого доселе не было в лекциях. А ниже вообще вы*боны: задача действительно сложная, даже если предыдущие задачи давались достаточно легко. Предыдущие 2 задачи - элементарщина, по сравнению с этой. Так что без паники)
    eight-bit-samurai Уровень 17
    12 ноября 2018
    О каком читерстве вы говорите, позвольте узнать? Авторы курса открытым текстом намекают о необходимости самостоятельного изучения возможностей языка и библиотечных функций. Вас никто не ограничивает в выборе средств, только лишь задается направление. Сложного ничего нет, если прикладывать достаточно усилий к самостоятельному поиску и применению знаний. В программировании нет места самооправданию: или тебе это действительно интересно и ты всё делаешь для решения задачи, или лучше заняться чем-то другим.
    enot_00 Уровень 1
    15 ноября 2018
    Я не сказал, что "читерство" - в данном случае плохо. Я имел ввиду то, что вами использована пара приемчиков, которых не было в лекциях, в частности объявление неотрицательной переменной unsigned и условие конца файла feof, и вот такая конструкция булевая, насколько я понимаю: if (!jpgPtr). Просто на первый взгляд после предыдущей задачи эта задача выглядит типа "а сейчас мы напишем тетрис". И даже на второй. Это, скажем так, пожелание не паниковать тем, кому все предыдущее далось легко и тщательно разобраться в функциях работы с файлами, потому как в лекциях это пролетело галопом, в предыдущих задачах все решалось добавлением пары строчек, а тут может возникнуть затуп.
    eight-bit-samurai Уровень 17
    15 ноября 2018
    То, что вы перечислили, это не читерство, т.к. оно подразумевает обман. А если в языке Си есть возможности для перечисленного вами, то какой же это обман? И про эти приёмчики я узнал как раз в ходе решения этой и следующей задачи, т.е. обошелся без лекций и матералов курса, пользуясь другими источниками. Они позволяют писать более лаконичный и читаемый код, но вам никто не мешает поступать так же или писать по своему, используя signed char, собственную реализацию feof и if (rawPtr == NULL) вместо if (!rawPtr). Это лишь вопрос привычек и чистого творчества. Читерством было бы, например, использование сторонней пользовательской библиотеки, которая решала бы эту задачу за вас. Вы, видимо, еще не открывали следующий уровень, вот где действительно непростая задача и бОльшая разница по сложности, чем между этой задачей и предыдущими. Мне хоть и пришлось попотеть над ней, зато я хорошо усвоил указатели, составные типы данных, алгоритмы хэширования и пробирования и даже CRC-кодирование, хотя это и не пригодилось. Сам, без чьей-либо помощи, пользуясь в основном Корменом и Керниганом с Ритчи. Усвоенный материал не уместить в лекциях - тупо времени не хватит у лектора, да и всех вопросов не охватишь. Но зато какое интеллектуальное и моральное удовлетворение получаешь, когда понимаешь, что справился сам, еще и разными способами. Если у меня получилось, значит и у других получится. Если бы по ложечке пихали что надо делать, разжевывая каждый шаг, вряд ли был бы кайф в этом. Это как раз и было бы читерством. Пользуйтесь разными источниками информации, концентрируйтесь, прилагайте усилия и всё у вас получится. Как говорится "глаза боятся, а руки делают". Да пребудут с вами Керниган и Ритчи! =)
    enot_00 Уровень 1
    15 ноября 2018
    Вот вы завелись. Я имел ввиду как раз обратное: не пугаться трудностей и не думать "это не моё".
    Александр Уровень 3
    9 октября 2022
    Объявление unsigned char фактически равно объявлению некоторых значений в задании с BITMAP. Мне удалось объявить подобным способом: typedef uint8_t BYTE; BYTE* picture; picture = malloc(512*sizeof(BYTE)); При объявлении знакового типа данных в переменную не записывается информация из читаемого файла. Видимо, связано с тем, что диапазон не позволяет вписать значения, которые в десятичной системе выше 128, а, например, 0хff - это 255 в десятичной.
    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;
    }
    
    Alexander Levin Уровень 4
    14 октября 2018
    Segmentation fault
    eight-bit-samurai Уровень 17
    14 октября 2018
    Странно, а у меня все запускается, картинки извлекаются и код проходит проверку
    Alexander Levin Уровень 4
    16 октября 2018
    У меня просто было очень похожее решение, но получал Segmentation Fault, поэтому решил проверить копипастнуть этот код, но не сработало. Возможно, где-то утечка памяти, хотя вроде Cloud 9 должен её сам освобождать.
    eight-bit-samurai Уровень 17
    16 октября 2018
    Может вы копипастнули, сохранили, но забыли сделать make, тогда все равно запустится предыдущая сборка. Утечку памяти можно проверить с помощью valgrind, об этом как раз на следующем уровне, но вряд ли дело в этом.
    12 февраля 2019
    А почему надо отделять fwrite от if проверяющего буфер(19 строка) или отдельно закрывать файл, а не сразу после записи?
    eight-bit-samurai Уровень 17
    12 февраля 2019
    Потому что нельзя писать в самый первый еще не открытый файл. Сначала его надо создать. Если файл есть, то закрываем текущий и создаем новый, иначе переходим к следующей порции данных. С закрытием примерно то же самое, только наоборот. Попробуйте запустить программу на отладку, расставив брэкпойнты в каждой строчке, и сами поймете.
    Евгений Уровень 1
    23 июня 2018
    Одно из самых легких заданий курса. У всех получилось 49 фото?
    eight-bit-samurai Уровень 17
    22 сентября 2018
    Переделывай, там 50 должно быть
    Ivan Уровень 34 Expert
    14 марта 2019
    49, программисты же с 0 считают))