Читаємо tar за 26 рядків ANSI C коду

Архіватори — це страшно! Величезні і жахливі алгоритми, які звичайній людині ніколи в житті не зрозуміти! 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( (s[i]>='1') && (s[i] < = '9') ) size += (s[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. Читаємо з блоку ім'я файлу і його розмір.
  2. Якщо ім'я файлу збігається з тим, що шукаємо, то повертаємо посилання користувачеві.
  3. Інакше стрибаємо на наступний блок і повторюємо з кроку 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 passed to 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 from file size string into integer */
for(i=SZ_SIZE-2, mul=1; i>=0; mul*=8, i--) /* Octal str to int */
if( (s[i]>='1') && (s[i] < = '9') ) size += (s[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 — поганий вибір.
dxTarRead на GitHub
P. S. Хаб "Я піарюсь!" я бачив. А де хаб "Я шукаю роботу"? :-)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.