УКНЦ форматы архивов

Данный материал защищён авторскими правами! Использование материала заявлено как добросовестное, исключительно для образовательных некоммерческих целей.

LZS/LZA

Программы:

• LZ.SAV - упаковщик LZS
• UZ.SAV - распаковщик LZS

программы с правками от EmeSoft:

• LZA.SAV - упаковщик LZA
• UZA.SAV - распаковщик LZA

Правки:

1. для упаковщика уменьшен буфер в 2 раза, соответственно памяти требуется сильно меньше.
2. сжатые данные инвертированы, но КС считается по неинвертированным данным
3. изменён текст, сделаны незначительные оптимизации.

формат Архива:

struct ArchHeader {             // заголовок архива
    word    archID = EmeSoft ? ^R<LZA> : ^R<LZS>; // сигнатура
    word    version = "21";     // версия архива
    word    N;                  // размер кольцевого буфера в байтах 010000 или 04000 для EmeSoft
    word    date;               // дата создания архива
    word    password;           // зашифрованный пароль для распаковки, 0, если нету.
            /* пароль шифруется так:
               password = comb(swab(^R<nnn> xor archID)),
               где nnn - открытый пароль, заданный в ключе /P */
    word    0;                  // зарезервировано
    word    archCatSize;        // размер каталога архива в байтах, 0 - если нет каталога
    word    archCatBlk;         // номер блока начала каталога, относительно начала файла архива,
                                // 0 - если нет каталога
                                // каталог архива выравнивается по границе блока.
};

struct FileHeader {             // заголовок файла
    dword   .rad50 "FILNAM";    // имя файла в RADIX-50
    word    .rad50 "EXT"        // расширение файла в RADIX-50
    word    unpSizeBlk;         // размер файла в блоках до архивации
    word    date;               // дата создания файла
    word    CS;                 // контрольная сумма упакованного массива
    dword   pckSize;            // размер упакованного массива в байтах
}

struct ArchCatRecord {  // запись о файле в каталоге архива
    word    blkNum;     // номер блока относительно начала файла архива, с которого начинается файл в архиве
    word    offset;     // смещение в блоке, с которого начинается массив упакованных данных файла
    FileHeader file;    // структура заголовка файла
}

// формат Архива
Archive {
    ArchHeader header;      // заголовок архива
    {
        FileHeader fh;      // заголовок файла
        byte[fh.pckSize];   // упакованный массив
        .wordeven           // выравнивание по слову
    } по количеству файлов в архиве;

    .blockeven                  // выравнивание по блоку
    // каталог архива, опционально
    {
       ArchCatRecord    fileRecord; // запись о файле в каталоге архива
    } по количеству файлов в архиве;
};

FCU

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

Заголовок: 7 слов = 14 байт

• три слова: Имя + расширение файла в RADIX-50
• слово: Длина исходного файла, в блоках
• слово: Дата файла; старший бит означает что файл был защищён от записи (PROTECTED)
• два слова: Длина файла в архиве (с точностью до слова)
  • Первое слово
    • младший байт это количество слов
    • старший байт это признак заголовка (0xBE = 0276 oct)
  • Второе слово: количество блоков

После заголовка следует собственно сжатый поток. Длина этого блока в байтах определяется так: (седьмое слово) * 512 + (младший байт 6-го слова) * 2 В эту длину входят также два слова контрольных сумм.

В самом конце блока со сжатым потоком бит лежат два слова:

• предпоследнее слово: контрольная сумма исходного файла
• последнее слово: контрольная сумма сжатого потока

Контрольная сумма считается простым сложением слов.

Собственно сжатие выполняется алгоритмом Huffman, за основу была взята известная реализация lzhuf.c от Haruyasu Yoshizaki и Hurahiko Okumura. Параметры алгоритма:

// LZSS compression

#define N               4096        // buffer size
#define F               60          // lookahead buffer size
#define THRESHOLD       2
const uint16_t NIL =    0xFFFE;    // leaf of tree

// Huffman coding

#define N_CHAR          (256 - THRESHOLD + F)
// kinds of characters (character code = 0..N_CHAR-1)
#define T               (N_CHAR * 2 - 1)        // size of table
#define R               (T - 1)     // position of root
#define MAX_FREQ        0x8000      // updates tree when the root frequency comes to this value.

Существенное отличие от оригинала, это кодирование потока бит. В Huffman мы имеем дело с потоком бит, поэтому важно как они укладываются в байты и слова. Обычно это просто "берём байты друг за другом" и для каждого байта либо "MSB first" (от старших бит к младшим) либо "LSB first" (от младших бит к старшим). Но в FCU всё сложнее, потому что энкодер сохраняет словами, плюс little endian для байт в слове. Поэтому, получается так:

• во-первых, используем MSB, поэтому для слова `0xABCD` порядок выдачи бит в исходящем потоке будет A B C D.
• во-вторых, little endian, поэтому в виде байт это сохраняется в порядке: [CD] [AB].