undefined

Задание №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
    Комментарии (38)
    Чтобы просмотреть все комментарии или оставить свой,
    перейдите в полную версию
    Александр # 0 уровень
    17 апреля 2021
    Снова нашлась досадная ошибка при переводе с английского: «Порции» можно записывать, пока исходный файл карты памяти не закончится. fread возвращает количество элементов размера size, которые были успешно прочитаны. В идеале size должно совпасть c number. Конечно же значение fread должно совпадать с number
    Александр 23 уровень, Москва
    30 марта 2021
    Задача оказалась, как бы это странно не показалось, легче для понимания, чем две предыдущие... 045.jpeg
    Андрей 0 уровень
    20 июля 2020
    048.jpeg
    Даниил 41 уровень Master
    14 февраля 2020
    Конечно же решил не без копирования частей кода из предыдущих заданий и подглядываний в готовый код что бы убедиться что двигаюсь в правильном направлении, но минут 20 убил на то что не мог понять почему то ни востанавливает ничего, то сохраняется только одна фотография (как выяснилось потом это была последняя из всех фотография). Всего их 50 штук. В общем ошибка была в том что процессе изменения кода забыл добавлять единичку к каждому новому названию файла, в итоге они доблесно перезаписывались. Подсказка: не стоит перебирать по одному байту весь файл страхуясь от того что пропустите начало новой картинки. Это учебное задание и всё сделано ровно так что если вы будете считывать ровно по 512 байт, то вы не пропустите ни одной фотографии. Просто в начале идут "пустые байты" (вроде как 2 раза по 512 нужно прочитать таких пустых), а далее начинаються картинки. В общем считываете по 512 байт за раз, когда первый раз встретите необходимую последовательность байт которые указывают на начало jpg файла, то записывайте всё подряд аж до тех пор пока снова не встретите эту же последовательность. При этом старый файл нужно закрыть, создать новый и повторять так пока не закончаться байты в исходном файле.
    PinGantar 0 уровень
    9 февраля 2019
    Сначала задача показалась сложной , но на деле она намного проще двух предыдущих . Главное не бояться ))
    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 фото?
    null 0 уровень
    1 июня 2018
    Давайте еще задания с фотками барышни с 024! А вообще самое сложное задание для меня (((