Axis Graphic Software
axgc.com

Компонентные файлы

  • Введение
  • Основные определения
  • Запись и чтение в компонентном файле

Введение

Имеется многочисленный ряд задач, при которых существует необходимость сохранять данные в единый файл с возможностью их перезаписи или удаления. Такое требование легко осуществляется в случае постоянного размера записываемых данных, при переменной длине данных размещение внутри файла может быть реализовано через внутренние смещения по принципу связанного списка, т.е. помещением в начало данных заголовка (header) в котором бы указывалась относительное смещение (offset) или абсолютный адрес следующего блока. Запись или перезапись данных не требует перезаписи всего файла, а прохождение по всей цепочке указателей даст положение и размер всех данных в файле. При всей простоте реализации такого подхода, такой формат хранения имеет серьезный недостаток, который будет проявляться в операциях вставки и удаления данных. Организованный по этому алгоритму файл со временем начнет приобретать дырки, явление при котором новые данные будут писаться в конец файла, а не на место удаленных ранее данных, вызывая разбухание всего файла. Причиной этого служит то, что размер новых данных начнет превосходить максимальный размер дырки из списка свободного пространства файла и запись пойдет в конец файла. Удаление дырок со временем потребует частичную или полную перезапись файла. Такие проблемы легко разрешимы в случае небольших файлов, перезапись файлов размеров в несколько сот мегабайт и выше потребуют дополнительных временных затрат. Решением этой проблемы могло бы стать создание такого механизма, при котором записываемые данные могли бы быть разрезаны на отдельные куски с возможностью размещения этих кусков в свободное пространство файла и с возможностью последующих операций чтения, перезаписи и удаления этих данных. Один из механизмов такой записи реализован в алгоритме FAT. Далее будет приведена только алгоритмическая часть FAT размещения данных без обсуждения других вопросов и версий этого формата размещения данных.

В целях устранения возможной путаницы в терминах, данные в таком файле в дальнейшем будут называться файлами, а сам исходный файл структурированным хранилищем, компонентным файлом или Storage.

Основные определения

 

  • Секторы
  • Заголовок Storage
  • Каталоги и файлы
  • FAT и FAT2

Секторы

В качестве внутренней адресации внутри Storage используются номера секторов. Сектор представляет собой блок или пространство определенной длины внутри компонентного файла. Сектор, в свою очередь, имеет постоянную длину, нумерация секторов начинается с первого блока, идущего сразу за заголовком Storage. Сектора имеют непрерывную нумерацию, идущую от 0. Сектора могут быть свободными для записи, а могут быть заняты данными - данными файла, секторами FAT и FAT2, каталогами.

Заголовок в компонентном файле

В заголовке задается информация о размере сектора, о позиции сектора в котором находится корневой каталог и о позиции первого блока FAT2 и другая информация.

Каталоги и файлы

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

FAT и FAT2

Всё управление записью и чтением данных ведется только через таблицу размещения файлов или FAT. Все данные размещаются по секторам, для этого определяется цепочка свободных секторов, в которые может быть записаны данные, после этого цепочка секторов записывается в сектор FAT, при заполнении сектора FAT происходит выделение нового блока под FAT, номер сектора нового FAT блока размещается в секторе FAT2 или в другой терминологии DiFAT. В итоге, в секторах FAT размещаются цепочки секторов данных, тогда как в FAT2 размещаются цепочки секторов FAT. Такая адресация позволяет экономить дисковое пространство и память при работе с большими файлами. Адресуемое пространство при таком алгоритме будет пропорционально квадрату числа всех секторов FAT, что для больших файлов становится существенным фактором.

Адресация в FAT и FAT2

Один адрес FAT адресует один сектор данных, один записанный блок FAT-адресов адресует пространство размером равное произведению числа адресов в блоке на размер блока. То есть, если принять, к примеру, размер блока равным 512 байт при 4 байтах приходящихся на запись одного адреса, то число адресов будет равно 128, а общий адресуемый размер одного FAT блока будет равен 65536 байтам, при размере блока в 4096 байт, адресуемое пространство будет равно 4 MB. При заполнении одного FAT блока происходит выделение нового FAT блока, адрес нового блока записывается в блоке FAT2 по смещению, которое будет определено ниже.Таким образом, при размере блока 512 байт, один блок FAT2 адресует пространство равное 8323072 байтам или 128*128*(128-1), при блоке 4KB, адресуемое пространство равно 1.072.693.248 байтам.
 

Запись и чтение в компонентном файле

Запись и чтение цепочки адресов в FAT и FAT2

Данные размещаются в секторах, последовательность или цепочка адресов может иметь произвольный порядок следования. Это объясняется тем, что список свободных секторов, куда может быть записан файл, могут быть расположены в различных местах компонентного файла. Для процедуры прочтения всей цепочки записанного файла из компонентного хранилища, необходимо знать положение первого сектора, с которого начинается файл. Значение сектора однозначно определяет положение позиции последующего адреса в блоке FAT, обрыв цепочки происходит тогда, когда прочитанное значение адреса оказывается равным 0xFFFFFFFE как в случае MS Compound File или другому определенному значению.

Операции чтения и записи данных

Все операции связанные с чтением и записью файлов или других данных (объявления каталогов и файлов) требуют обязательного прочтения цепочки FAT2, в которой хранятся адреса блоков FAT. Для этого необходимо сделать следующее
  • Прочитать адрес первого сектора FAT2.
  • Перейти на адрес первого блока FAT2
  • Последовательно прочитать все адреса в блоке до завершающего значения ( в MS Storage Compound таким значением служит величина 0xFFFFFFFF). Если завершающего символа в последовательности значений FAT2 не обнаружено, то последнее прочтенное значение в секторе будет указывать на начало следующего блока. Перейдя к следующему блоку, указанные операции должны быть повторены до тех пор пока не будет обнаружен завершающий символ.
Адрес первого сектора FAT2 записывается или в заголовке компонентного файла или определяется заранее по умолчанию или размещается в месте, которое задается спецификацией формата файла. В MS Storage этот адрес записывается в заголовке хранилища. Операцию чтения FAT2 имеет смысл делать только при открытии хранилища, в дальнейшем вся цепочка FAT2 хранится в памяти и по мере добавления или удаления новых секторов операция чтения с диска не используется. Аналогичным образом, для прочтения файла необходимо иметь первый сектор, с которого записываются данные. Имея список секторов, можно получить доступ ко всем данным файла. Список секторов может иметь любой порядок, следовательно, нужно обеспечить простой алгоритм чтения и записи секторов. При размещении цепочки адресов в блоке FAT используется следующий принцип- значение текущего адреса определяет положение следующей записи в блоке FAT. Следующая позиция определяется делением по модулю текущего значения на число адресов в секторе. Число адресов в секторе величина постоянная и равна отношению размера блока на размер типа, которым представлен адрес, так, если число является длинным целым в 4 байта, а размер блока равен 512 байтом, то число адресов в одном FAT блоке окажется равным 128. Кроме относительной позиции адреса в блоке нужно знать еще номер FAT блока, в котором записан адрес.

Номер FAT блока определятся отношением:
N = sec/(adr_per_sec*( adr_per_sec-1))

Смещение определятся отношением:_per_sec

Абсолютный адрес для чтения:
adr = FAT2[N]* SIZEBLOCK + offset*sizeof(long) + header

Где header равно начальному смещению в компонентном файле от начала файла до первого сегмента.
Зная номер блока и значение смещения в блоке, легко прочитать следующий адрес. Процедура чтения завершается при чтении завершающего символа.

Объявление каталогов и файлов

Размещение списка каталогов и файлов происходит по тому же принципу, что и размещения данных из файла. В первую очередь формируется список каталогов. По своей сути этот список является точно таким же файлом. Для доступа к списку нужно знать начальный сегмент, в котором начинается список, после чего, имея начальный сектор списка каталогов, можно развернуть всю FAT цепочку, как описано ранее. В MS Compound Storage номер сегмента записан в заголовке хранилища. Размер одного заголовка файла в MS Compound Storage равен 128 байтам, а размер сегмента может быть установлен 512 байтам или 4096 байтам, соответственно, количество файловых заголовков в одном блоке можно записать или 4 или 32. Для размещения заголовков внутри сегментов Microsoft использует следующий алгоритм. Определятся сегмент, в который будет записан заголовок по формуле:

num = (id * SIZEDIRS) / SIZEBLOCK

Где id есть целочисленный идентификатор, SIZEDIRS размер файлового заголовка, SIZEBLOCK размер сегмента, номер FAT сектора в цепочке каталогов. Позиция (смещение) внутри сектора, куда записывается заголовок, определяется по формуле

Абсолютное положение определяется так:

adr = DIR[num]* SIZEBLOCK + offset + header

Где это DIR это FAT цепочка каталогов.