Архиваторы — это страшно! Огромные и ужасные алгоритмы, которые обычному человеку никогда в жизни не понять! 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. Хаб "Я пиарюсь!" я видел. А где хаб "Я ищу работу"? :)
