Архиваторы — это страшно! Огромные и ужасные алгоритмы, которые обычному человеку никогда в жизни не понять! Rar, zip, gzip, tar — современные стандарты де-факто, а значит крайне сложные и навороченные штуки, которые и пытаться понять не стоит. Ну, tar выглядит попроще, может там всё не так сложно? Смотрим git с исходниками. Видим десятки файлов, многие на десятки килобайт. Мда. Видимо, тупик.
__________________| |____________________________________________
,--. ,--. ,--. ,--.
|oo | _ \ `. | oo | | oo|
o o|~~ |(_) / ; | ~~ | | ~~|o o o o o o o o o o o
|/\/\| '._,' |/\/\| |/\/\|
__________________ ____________________________________________
| |dwbНа самом деле всё не так сложно. В документации было описано, что tar — просто способ записи нескольких файлов на ленту. Т.е. всё должно быть просто. По факту — набор вспомогательной информации для каждого файла и непосредственно его содержимое. Именно понимание этого факта и позволило сделать читатель tar-файлов в 26 строк.
Зачем вообще может быть нужен tar во времена тотального засилья zip? Для меня вопрос использования tar встаёт тогда, когда хочу получить в своих миниатюрных Си-приложениях архиватор "на халяву" — т.е. с минимальным ростом исполняемого файла и без лишних зависимостей. Например, утилита dxPmdxConverter умеет читать BMP и конвертировать в PNG с помощью LodePNG. Т.е. в приложении уже есть функционал, который "архивирует" массив пикселей в сжатый PNG формат. А сжимается PNG по алгоритму Deflate, который используется в zip и gzip. Причём, в gzip он используется напрямую — записывается заголовок gzip, поток данных от Deflate, crc-сумма. И на выходе получается готовый .gz-файл, который можно открыть любым архиватором. Однако gzip может сжать только один файл. Т.е. до сжатия несколько файлов нужно каким-то образом объединить в один. Наиболее распространённый для этого способ — tar.
____ _ _ ____ __ ____ __ _ _ __ ____ ______
| _ \| \ | |/ ___| / / | _ \ ___ / _| | __ _| |_ ___ / / / ___|__ (_)_ __
| |_) | \| | | _ / / | | | |/ _ \ |_| |/ _` | __/ _ \ / / | | _ / /| | '_ \
| __/| |\ | |_| | / / | |_| | __/ _| | (_| | || __/ / / | |_| |/ /_| | |_) |
|_| |_| \_|\____| /_/ |____/ \___|_| |_|\__,_|\__\___| /_/ \____/____|_| .__/
|_| В следующий раз tar пригодился мне в похожей ситуации. Чтобы не хранить ресурсы игры Wordlase в открытом виде было решено их архивировать. Да, паковать можно как угодно долго, на машине разработчика. Но распаковываться ресурсы будут при каждом запуске игры. Т.е. решение должно работать быстро. Public domain реализация алгоритма сжатия была найдена на просторах интернета, но она так же умеет паковать только один файл. Так и был рождён герой данной публикации — dxTarRead.
Преимущества dxTarRead:
- не требует дополнительной памяти, работает только с переданным массивом
- легко встраиваем, всего 1 функция
- не зависит ни от каких библиотек (не используется даже stdlibc)
- C89, т.е. теоретически корректно скомпилируется даже на микроволновке с помощью Visual Studio
- Public Domain
Основным недостатком является то, что tar-файл должен быть предварительно считан в память полностью. С другой стороны — ресурсы же всё-равно будут использованы, т.е. будут загружаться. Тогда почему бы не загрузить их с диска сразу, а уже по надобности брать их из массива с tar-данными.
Итак, tar. Основную информацию по стандарту можно прочитать на GNU.org. В основном мне пригодилось только описание структуры "struct posix_header". Именно оттуда взяты константы:
const int NAME_OFFSET = 0, SIZE_OFFSET = 124, MAGIC_OFFSET = 257;
const int BLOCK_SIZE = 512, NAME_SIZE = 100, SZ_SIZE = 12, MAGIC_SIZE = 5;По сути эти константы можно читать примерно так: если сместиться от начала блока tar на 124 байта (SIZE_OFFSET), то в следующих 12 байтах (SZ_SIZE) у нас будет храниться размер файла внутри tar.
Не забываем читать документацию и дальше. Там можно узнать, что размер хранится в восьмеричной системе счисления ;-) Т.е. если читать байты с конца SZ_SIZE и прибавлять цифру, умноженную на 8, то получим размер в привычном десятичном виде.
Если записать вышеописанное на языке Си, то получим:
const char* sz = tar + SIZE_OFFSET + currentBlockStart;
long size = 0;
for(i=SZ_SIZE-2, mul=1; i>=0; mul*=8, i--) /* Octal str to int */
if( (sz[i]>='1') && (sz[i] <= '9') ) size += (sz[i] - '0') * mul;Вплотную подошли к теме tar-блоков. Это просто 512 байт с данными — или заголовок tar, или непосредственно байты файла, записанные подряд. Если последний блок файла занимает меньше 512 байт, то всё равно резервируется 512 байт. Т.е. каждый tar-архив выглядит примерно так:
+-------+-------+-------+-------+-------+-------+
| tar 1 | file1 | ... | file1 | tar 2 | file2 | ...
+-------+-------+-------+-------+-------+-------+Идёт блок с заголовком tar, в котором указан размер хранимого файла. Далее идут N блоков с содержимым файла. Т.е. чтобы перейти к следующему файлу в tar нужно сместиться на (N+1)*512 байт. Код:
newOffset = (1 + size/BLOCK_SIZE) * BLOCK_SIZE; /* trim by block size */
if( (size % BLOCK_SIZE) > 0 ) newOffset += BLOCK_SIZE;Алгоритм выглядит следующим образом:
- Читаем из блока имя файла и его размер.
- Если имя файла совпадает с тем, что ищем, то возвращаем ссылку пользователю.
- Иначе прыгаем на следующий блок и повторяем с шага 1.
Чтобы сравнить имя файла пришлось реализовать свой аналог strncmp на цикле:
i = 0;
while((i<NAME_SIZE) && (fileName[i]!=0) && (name[i]==fileName[i])) i++;
if( (i > 0) && (name[i] == 0) && (fileName[i] == 0) ) found = 1;Всё. Весь исходный код рассмотрен. Полный код функции:
const char* dxTarRead(const void* tarData, const long tarSize,
const char* fileName, long* fileSize)
{
const int NAME_OFFSET = 0, SIZE_OFFSET = 124, MAGIC_OFFSET = 257;
const int BLOCK_SIZE = 512, NAME_SIZE = 100, SZ_SIZE = 12, MAGIC_SIZE = 5;
const char MAGIC[] = "ustar"; /* Modern GNU tar's magic const */
const char* tar = (const char*) tarData; /* From "void*" to "char*" */
long size, mul, i, p = 0, found = 0, newOffset = 0;
*fileSize = 0; /* will be zero if TAR wrong or there is no such file */
do { /* "Load" data from tar - just point to passed memory*/
const char* name = tar + NAME_OFFSET + p + newOffset;
const char* sz = tar + SIZE_OFFSET + p + newOffset; /* size string */
p += newOffset; /* pointer to current file's data in TAR */
for(i=0; i<MAGIC_SIZE; i++) /* Check for supported TAR version */
if( tar[i + MAGIC_OFFSET + p] != MAGIC[i] ) return 0; /* = NULL */
size = 0; /* Convert file size from string into integer */
for(i=SZ_SIZE-2, mul=1; i>=0; mul*=8, i--) /* Octal str to int */
if( (sz[i]>='1') && (sz[i] <= '9') ) size += (sz[i] - '0') * mul;
/* Offset size in bytes. Depends on file size and TAR's block size */
newOffset = (1 + size/BLOCK_SIZE) * BLOCK_SIZE; /* trim by block */
if( (size % BLOCK_SIZE) > 0 ) newOffset += BLOCK_SIZE;
i = 0; /* strncmp - compare file's name with that a user wants */
while((i<NAME_SIZE) && (fileName[i]!=0) && (name[i]==fileName[i])) i++;
if( (i > 0) && (name[i] == 0) && (fileName[i] == 0) ) found = 1;
} while( !found && (p + newOffset + BLOCK_SIZE <= tarSize) );
if( found ){
*fileSize = size;
return tar + p + BLOCK_SIZE; /* skip header, point to data */
} else return 0; /* No file found in TAR - return NULL */
}Вывод
tar не сжимает данные, а хранит в открытом виде. Именно это и позволяет не выделять новую память, а просто возвращать указатель на существующую.
Размер tar-блока равен 512 байт. Кроме того на каждый файл необходимо хранить tar-заголовок. Т.е. файл размером несколько байт будет занимать 1 килобайт в tar-архиве. Если нужно хранить много мелких файлов и при этом не сжимать файл, то tar — плохой выбор.
P.S. Хаб "Я пиарюсь!" я видел. А где хаб "Я ищу работу"? :)
Комментарии (34)
ammaaim
11.02.2017 23:07+6tar — не совсем архив в широко распространённом смысле этого слова. Данные в нём не сжимаются, а хранятся в открытом виде
Ну архив сам по себе не подразумевает обязательное сжатие — сжатием архива занимается компрессор. А задача архиватора — получить архив — то есть множество файлов упаковать в один
DeXPeriX
11.02.2017 23:11+1Именно! Это и пытался описать. Лично меня когда-то очень удивило, что архив — это не обязательно сжатие. Попытаюсь как-нибудь перефразировать, спасибо за замечание.
Shtucer
12.02.2017 01:33+1Боюсь, придётся много чего перефразировать. Rar, zip, gzip — компрессоры. Архиватор в этой статье пока один — tar. У архива задача не просто собрать кучу файлов в один, а ещё и сохранить у этих файлов атрибуты доступа, флаг исполнения и прочие интересные вещи.
Lsh
11.02.2017 23:58А заголовок tar ограничен 512-ю байтами или может быть больше?
Например, как там убирается очень длинный путь к файлу?DeXPeriX
12.02.2017 00:21По стандарту GNU tar — 512 байт ровно. Очень длинный путь внутри tar не учитывается. Точнее, если будет больше 100 символов — то всё сломается. Если где-то такой вариант и учли в реализации, я об этом не в курсе.
funca
12.02.2017 00:02+1Правильно-ли я понимаю, что основная задача это архивирование? Возможно, для ваших кейсов больше подойдет обычный ar:
ar -cq out.ar file1.txt file2.txt
tar оптимизирован для бэкапов блочных устройств на летны (tape). Отсюда блоки по 512 байт, что соответствует популярному размеру сектора дисков. Но если основной кейс это распаковка в память, то фича скорее не нужна.DeXPeriX
12.02.2017 00:52Спасибо! Вроде бы формат не сильно отличается от tar. Позже попробую добавить и этот формат в свой "архиватор" на гитхаб.
DeXPeriX
12.02.2017 17:03Покрутил немножко. Я не вижу поддержки директорий, а без них совсем грустно.
И длина имени файла всего 16 символов.
funca
12.02.2017 19:15Зачем в файле с ресурсами для игры директории и имена файлов, кто там на них будет смотреть? Blizzard в своем известном формате заменяет все это многобуквенное великолепие просто на хеши (логика разработчиков вполне понятна, хоть и бесит чисто по-человечески). ^)
DeXPeriX
12.02.2017 19:47Чтобы избежать хэшей и редактировать эти ресурсы напрямую? В JSON у меня ссылки вида "effects/snow.png", "sprites/girl.png". Загрузчик смотрит файлы в открытом виде, если нет, то пытается грузить из архива. В котором лежат по этому же пути.
ivan386
12.02.2017 02:31+5P.S. Хаб "Я пиарюсь!" я видел. А где хаб "Я ищу работу"? :)
На верху страницы ссылка: Мой круг
zagayevskiy
12.02.2017 22:40Первая четверть XXI века близилась к завершению… С89 всё ещё подавался как преимущество.
DeXPeriX
12.02.2017 23:08+1А почему не преимущество? Да, в таком стандарте не очень комфортно писать. Но C89 почти гарантирует, что проект успешно скомпилируется в любом современном компиляторе, начиная от Clang и заканчивая восьмибитными микроконтроллерами. Писать свой проект можно на чём угодно, хоть на "Super-mega-boosted-python-java#". Но если есть желание использовать чужую библиотеку, и при этом она написана на C89, то есть приличная вероятность, что она без проблем подключится.
Кроме того, Си есть Си. Т.е. отличная производительность за счёт низкоуровневости языка.zagayevskiy
13.02.2017 12:31Есть ведь новые стандарты языка.
DeXPeriX
13.02.2017 15:11+2Есть. Но какова вероятность, что компилятор для микроволновки будет поддерживать свежие стандарты? Или какие-нибудь KolibriOS/MenuetOS? В которых основным компилятором TCC, да ещё и лохматых годов выпуска, да ещё и сурово допиленный напильником. А С89 будет работать везде. Потому, что стандарт относительно простой, и при создании компиляторов Си в первую очередь стремятся к нему.
mwizard
DeXPeriX
Я один раз читаю cжатый файл. Затем распаковываю архив. Это и есть пик, когда загружены и архив и его распакованная версия. Далее сжатый файл удаляется из памяти, во время работы приложения занято памяти ровно на распакованные tar-данные. Пример: data.tar 1000kb, data.tar.gz 250kb. Итого на диске хранится 250kb, пиковое потребление памяти 1250kb, потребление памяти в рабочем режиме — 1000kb. Другое дело, что если tar-файл будет большим, то грузить его весь в оперативку не рационально. Для таких случаев лучше присмотреть другое решение, а не dxTarRead.
mwizard
Хорошо, я понял вас, и я с вами согласен — но вы не уловили мой момент. Допустим, у нас в архиве хранятся текстуры. Эти текстуры ведь не представляют для нас интереса в виде блобов — с ними нужно что-то делать, верно? Загружать в тот же OpenGL, например. Ну или, скажем, не текстуры, а JSON-строки, которые нужно распарсить и превратить в дерево объектов. Итого, выходит, хронология использования памяти за время жизни приложения:
0MiB — запустились
+40 MiB — прочитали сжатый файл (итого 40 MiB)
+1000 MiB — распаковали сжатый файл в память (итого 1040 MiB)
-40 MiB — выгрузили сжатый файл (итого 1000 MiB)
+200 MiB — загрузили текстуру 1/5 из файла (итого 1200 MiB)
+200 MiB — загрузили текстуру 2/5 из файла (итого 1400 MiB)
+200 MiB — загрузили текстуру 3/5 из файла (итого 1600 MiB)
+200 MiB — загрузили текстуру 4/5 из файла (итого 1800 MiB)
+200 MiB — загрузили текстуру 5/5 из файла (итого 2000 MiB)
-1000 MiB — выгрузили распакованный архив (итого 1000 MiB)
Пиковая загрузка, выходит, 2 GiB, рабочий режим — 1 GiB. Если бы библиотека позволяла итерироваться по файлу, то загрузка была бы следующей:
0MiB — запустились
+240 MiB — распаковали одну текстуру и скопировали в память (итого 240 MiB)
+200 MiB — загрузили текстуру 1/5 из памяти (итого 440 MiB)
-240 MiB — освободили память из-под текстуры и контекста распаковки (итого 200 MiB)
+240 MiB — распаковали одну текстуру и скопировали в память (итого 440 MiB)
+200 MiB — загрузили текстуру 2/5 из памяти (итого 640 MiB)
-240 MiB — освободили память из-под текстуры и контекста распаковки (итого 400 MiB)
+240 MiB — распаковали одну текстуру и скопировали в память (итого 640 MiB)
+200 MiB — загрузили текстуру 3/5 из памяти (итого 840 MiB)
-240 MiB — освободили память из-под текстуры и контекста распаковки (итого 600 MiB)
+240 MiB — распаковали одну текстуру и скопировали в память (итого 840 MiB)
+200 MiB — загрузили текстуру 4/5 из памяти (итого 1040 MiB)
-240 MiB — освободили память из-под текстуры и контекста распаковки (итого 800 MiB)
+240 MiB — распаковали одну текстуру и скопировали в память (итого 1040 MiB)
+200 MiB — загрузили текстуру 5/5 из памяти (итого 1240 MiB)
-240 MiB — освободили память из-под текстуры и контекста распаковки (итого 1000 MiB)
Итого в таком случае мы бы тратили память только на хранение контекста распаковки и сырых данных.
DeXPeriX
Да, здесь согласен. Получается, что у меня в оперативке хранятся лишние картинки в виде сырых данных. Так получилось, что JSON-строки сразу конвертирую в дерево объектов, а память после tar и gzip освобождаю. Но это только из-за того, что JSON нужен весь и сразу. Попробую в своём проекте переделать логику менеджера спрайтов, чтобы сразу при инициализации грузил все картинки в формат текстуры, тогда tar-архив можно будет сразу освободить.
kekekeks
Ну так не грузите файл, а используйте отображение в память. Там ОС сама разберётся, что и когда нужно.
DeXPeriX
Ниже отписали, что отображение в память будет проблемно использовать с компрессором. Мне же нужно сначала распаковать gzip, а потом уже из результата читать tar.
funca
Какие-то готовые решения уже рассматривали? В практическом смысле, задачи эффективного доступа к ресурсам в играх появились давно и многие вопросы уже решены, но там совсем другой порядок компромиссов и сложности.
DeXPeriX
Если честно, не особо. Tar мне был просто интересен для исследования. А готовое решение надеялся что в комментах на хабре подскажут толковое.
MikalaiR
Погодите-погодите, а зачем считывать архив в память целиком? Почему бы не использовать mmap? (это если не менять предложенный автором код, а вообще в данном случае лучше читать файл блоками фиксированного размера)
mwizard
Если бы речь шла о .tar-файле на диске — никаких проблем, mmap туда просится естественным образом. Но как натравить mmap на результат распаковки какого-нибудь gzip?
MikalaiR
Ну mmap тут, естественно, в пролете. Но ведь gzip это потоковый компрессор, можно разжимать файл по кусочкам и распаковывать tar. Тоже не нужно читать файл в память целиком, но да, это уже не 26 строчек.
mwizard
Да, и ко всему вышеуказанному — реализация автора статьи однопроходная. Ты указываешь имя файла, которое нужно извлечь, а оно ищет его и извлекает. Это хороший подход, когда весь архив уже в памяти, но если его нужно для каждого файла переизвлекать из gzip, то лучше переписать эту часть логики на "встретил файл — спросил коллбэк, что с ним делать".
splav_asv
Так есть же zlib. Зачем внешнюю программу дёргать, если уж так на всём хочется экономить?
mwizard
Ну так никто и не предлагает дергать внешнюю компанию — под "gzip" имеется в виду формат архива, а не исполняемый файл, оный архив извлекающий.