Задача

Задание подразумевает написание программы на языке C++, которая парсит контейнер, который внутри себя содержит директории и файлы. В репозитории лежит файл с названием image1.img для тестов и отладки. Задача: написать две функции

1. На вход в функцию поступает название директории, функция должна вывести список поддиректорий и файлов, которые в ней содержатся. (Обычный вывод содержимого директории)
2. На вход в функцию поступает название файла, функция должна вывести в файл или в консоль содержимое файла. (Извлечение файла из контейнера)

Написанная программа не должна падать при любых некорректных данных.

Инструмент для исследования контейнера

Для формата, который будет описан здесь будут представлены описатели и скриншоты для Web Kaitai, который может помочь Вам разобраться с форматом. Полный описательный файл контейнера для данного ресурса лежит в репозитории и называется image.ksy. Вы можете загрузить на ресурс Web Kaitai описатель image.ksy и контейнер image1.img, чтобы сверяться, что вы верно парсите файл в своей программе.

Замечание: загрузка файлов вторая кнопка в левом нижнем углу

Заголовок и общие сведения о формате

В первых 512 байт контейнера расположен заголовок. Нас будут интересовать всего лишь несколько полей из него, которые описаны здесь. В image.ksy описаны все поля данного заголовка (type: mbr), но большая часть из них нам не пригодится.

Замечание: порядок байт little-endian

Обозначение поля	Смещение от начала файла	Длина байт	Название в image.ksy
Количестве байт в секторе	11	2	bytes_per_sector
Количество секторов в кластере	13	1	sectors_per_cluster
Количество зарезервированных секторов	14	2	number_of_reserved_sectors
Количество таблиц распределения	16	1	number_of_fats
Максимальное количество файлов в корневой директории	17	2	max_num_of_root_dir_entries
Секторов на таблицу распределения	22	2	sectors_per_fat

Весь контейнер состоит из секторов, размер которого указан в bytes_per_sector. (То есть размер контейнера кратен этому числу). В целом базовую структуру контейнера можно расписать так:

• Заголовок (Тип mbr в image.ksy)
• Зарезервированное пространство
• Таблицы распределения (которые в неповрежденном контейнере одинаковы, в нашей задаче будет использоваться только первая)
• Корневой каталог (тип root_directory в image.ksy)
• Данные (разбиты на кластеры, в одном кластере может содержаться несколько секторов)

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

• Сколько байт зарезервировано после заголовка: (number_of_reserved_sectors - 1) * bytes_per_sector
• Сколько байт занимает таблица распределения: sectors_per_fat * bytes_per_sector
• Размер кластера (тот, что состоит из секторов): sectors_per_cluster * bytes_per_sector
• Размер корневой директории: 32 * max_num_of_root_dir_entries Забегая вперед, 32 байта будет занимать структура, содержащиеся в корневой директории, то есть формально 32 байта это sizeof(root_directory_entry))

Таблица распределения

Так как контейнер внутри себя содержит файлы, содержимое этих файлов лежит в разделе данных. Весь раздел данных побит на кластеры и кратен размеру кластера. Так как данные файла в контейнере могут не поместиться в один кластер, содержимое этого файла может быть в произвольном порядке раскидано по кластерам. Для того, чтобы получить цепочку кластеров, представляющую из себя содержимое файла служит таблица распределения. Размер каждого элемента этой таблицы 12 бит

Замечение: с точки зрения программирование это массив, а не таблица, порядок бит: little-endian

Элемент по индексу номера кластера указывает номер следующего кластера. Так и образуется цепочка кластеров. Значение элемента в этой таблице 0x00 означает, что этот кластер не использован. Диапазон значений 0xFF8-0xFFF указывает на то, что это последний кластер файла, 0xFF0-0xFF6 зарезервированные кластеры, 0xFF7 плохой и неиспользуемый кластер. Таким образом, зная первый кластер файла, можно используя эту таблицу получить всю цепочку кластеров файла и извлечь его содержимое. На псевдокоде поиск номера следующие кластера будет выглядеть так: nextClusterNum = table[currentClusterNum] Напоминаю, что таких таблиц может быть несколько (в image1.img их две), используйте первую, не забудьте пропустить вторую (но в программе вы должны использовать number_of_fats для определения количества таблиц)

Раздел данных

Подведем итоги раздела данных

• раздел данных идет после раздела корневой директории
• состоит из кластеров, которые в свою очередь состоят из секторов по n байт, где n указано в заголовке в поле sectors_per_cluster
• нумерация первого кластера начинается с 2, не с 0, то есть первый байт данного раздела принадлежит кластеру под номером 2

Корневая директория

В описателе image.ksy это тип root_directory Содержит в себе max_num_of_root_dir_entries записей по 32 байта.

Некоторые правила считывания записей в директории (не только корневой, но и всех поддиректорий)

• если запись начинается с 0x00, то ее и все следующие можно не читать (записей дальше не существует)
• если запись начинается с 0xE5, то ее пропускает, читаем следующие записи (0xE5 значение обозначает, что запись удалена)

В описателе image.ksy формат записи в корневой директории имеет тип directory_entry

Обозначение поля	Смещение от начала записи	Длина	Название в image.ksy
Имя файла	0	11	file_name
Атрибуты	11	1	attribute
Зарезервировано	12	10	reserved
Время создания	22	2	time
Дата создания	24	2	date
Номер первого кластера	26	2	start_cluster
Размер файла	28	4	file_size

• Имя файла состоит из 11 байт, где 8 байт это имя файла, 3 байта его расширение. Имя файла всегда лежит в первых 8 байтах, расширение в последних 3. Неиспользуемые символы представлены в виде «пробела» 0x20.

• Атрибуты: установленный четвертый бит (0x10 маска) – это директория; записи с установленным 3 битом не рассматриваем (0x8 маска), т.е пропускаем записи, если установлен этот бит, все остальные аттрибуты относятся к файлу и обозначают файл. Более подробно на скриншоте.

• Номер первого кластера – это номер кластера в котором лежит либо содержимое файла, либо содержимое поддиректории (не забываем, что от начала сегмента данных нумерация кластеров идет начиная с 2)

• Размер файла – суммарное количество байт файла, которые могут находится в нескольких кластерах. Если выставлен атрибут директории, то размер будет 0.

Итого, если мы имеем запись файла (не директории), для того чтобы его прочитать полностью, мы должны достать информацию из кластера start_cluster и потом, с помощью таблицы распределения переходить в следующие кластеры (если, конечно, содержимое не поместилось в один кластер). Содержимое последнего кластера может не целиком принадлежать файлу, надо ориентироваться на file_size.

Поддиректория

Как было описано выше, если в атрибутах записи установлен четвертый бит (0x10 маска), то содержать файл описание поддиректории. То есть, чтобы прочитать какие файлы содержатся в поддиректории, необходимо прочитать содержимое (так же как содержимое файла, перейдя по start_cluster), а дальше в содержимом будут такие же записи по 32 байта, как описаны выше

Заключение.

Под конец хотелось бы сказать, что здесь были описаны все моменты необходимые для решения этой задачи, для примера предоставлен ресурс и описатель для него, с помощью которого достаточно легко разобраться с форматом, но на самом деле этот контейнер представляет из себя образ файловой системы FAT12. На самом деле, после записи directry_entry может быть расширения запись LFN (Long file name), но в данном задании мы ее не рассматриваем. Если вам будет что-то непонятно, можете воспользоваться этим, этим или этим, либо сами в поиске найти нужную вам информацию.