Формат архива LZA

[nzeemin]

Какой-то LZSS, поксоренный с 0xFF. Исходников не нашел, может, подбором сделаю.

Я прикручивал реализацию LZSS к своей утилите Sav2Cart для УКНЦ, причём брал алгоритм от утилиты LZSAV, за авторством Остапенко Алексей, 1994 год.
Там, в отличие от "классического" LZSS, управляющие биты сгруппированы в байты, биты "ссылок" устроены как 4 бит длина + 12 бит смещение назад = одно слово, окно получается размером 4 КБ. В такой реализации почти не используются побитовые сдвиги, выборка идёт побайтно.
Это я к тому что вдруг у вас что-то похожее.
https://github.com/nzeemin/ukncbtl-u...ridge/LZSS.cpp

[kolk]

Там, в отличие от "классического" LZSS, управляющие биты сгруппированы в байты, биты "ссылок" устроены как 4 бит длина + 12 бит смещение назад = одно слово, окно получается размером 4 КБ. В такой реализации почти не используются побитовые сдвиги, выборка идёт побайтно.
Это я к тому что вдруг у вас что-то похожее.

Да, именно такое, от Haruhiko Okumura. Но все константы надо проверять (вдруг не 4/12, а 5/11?). (Иначе бы я его на глаз не опознал! А у LZA весь сжатый поток зачем-то проинвертирован.) Выше я уже давал ссылки на него. Еще он применяется в Renesas .PAK. Там метод определяется равенством сжатого и несжатого размеров - если равны, то store, иначе LZSS.

- - - Добавлено - - -

https://github.com/nzeemin/ukncbtl-u...ridge/LZSS.cpp

У Вас как минимум 2 отличия: инверсное значение флагов и смещение от текущей позиции вместо смещения от начала буфера.
В LZA больше похоже на версию Haruhiko Okumura.

[nzeemin]

У Вас как минимум 2 отличия: инверсное значение флагов и смещение от текущей позиции вместо смещения от начала буфера.
В LZA больше похоже на версию Haruhiko Okumura.

Так они ВСЕ происходят от кода Haruhiko Okumura, просто потому что он первым выложил свой код в public domain, в 1989 году.
Вот две похожих реализации, которые я использовал:
https://gist.github.com/davidreynolds/3025423
https://github.com/dwelch67/msp430si...ss/lzss_orig.c

[kolk]

Так они ВСЕ происходят от кода Haruhiko Okumura, просто потому что он первым выложил свой код в public domain, в 1989 году.

Я уже убедился, что там Haruhiko Okumura с точностью до инверсии (таки с целью "сокрытия"). Шифрования нет, некоторый хэш пароля в слове по смещению 8 от начала архива. Хвостовые нули несжатого файла честно сжимают. Осталось разобрать хэши, even padding byte (0 или 0xFF?) и особенности центрального каталога (формат указателя на файл в архиве), когда присутствует центральный каталог. На код Haruhiko Okumura есть ссылка выше в теме.

[gid]

Чё-то все увлеклись этими архиваторами и я заодно тоже. Подумал написать кросс упаковщик-распаковщик, чтоб смотреть, что там, в иногда попадающихся архивах. Но пока дизассемблировал - устал и энтузиазм иссяк. Поэтому, пусть кто-нибудь другой напишет.
Во вложении LZA-UNLZA.rar в архиве:
. LZ.asm, UZ.asm - исходники для кросс макро-11, потому что используются длинные метки. Сами исходники в КОИ-8 и русские буквы там тоже в КОИ-8. Чтобы компилировать в родной среде RT-11, нужно творчески переделать многие метки в уникальные 6-ти символьные. Чтобы получить русские буквы из КОИ-8 в КОИ-7, нужно применять какие-то неизвестные мне макросы или др. средства.
Из исходников можно получить как оригинальные LZ/UZ, так и не оригинальные LZA/UZA, где применены только правки от EmeSoft, и то не все.
LZ получается почти бинарно идентичен, разница - два байта текста, где исправлены две опечатки.
UZ получается с небольшими отличиями, в двух макросах, порядок передачи аргументов EMTу отличается (потому что только такую макробиблиотеку я нашёл).
Оригинальные LZA/UZA не получатся, т.к. EmeSoft там увлечённо шифровал код методом ксорения.
. lzss.c - исходник Haruhiko Okumura, который брался за основу архиватора/разархиватора. Просто так, не стал его из директории выкидывать, когда архив паковал.
. Macro11.exe - кроссассемблер макро-11 от Rhialto, с небольшими исправлениями (1.компиляция под RT-11 работает, а то он RSX увлёкся и поломал там RT-11, 2.имена макросов принудительно обрезаются до 6 символов при использовании длинных лексем, чтобы из SYSMAC.SML макросы доставались даже если писать их полное имя. Это не очень полезная фича, просто она осталась в этой сборке, 3. isdigit при парсинге чисел в 16-ричной системе счислении работает.)
. pclink11.exe - кросслинковщик от nzeemin
. батники, чтобы компилировать, две макробиблиотеки, первые попавшиеся, которые я нашёл, для сборки в SAV.
. Формат архива LZA.txt - описание формата архива, чтобы писать кросс упаковщик/распаковщик.

[kolk]

КС - простая пословная сумма сжатого потока без переноса.
В оригинальной версии (не EmeSoft) сжатый поток не инвертирован.

Байт выравнивания на границу слова в двух версиях остался под вопросом. (По идее, его тоже инвертируют?)

[Advertiser]

[nzeemin]

kolk, так что в итоге с кросс-архиватором?
Или хотя бы давайте полное описание формата сделаем.
Так-то конечно хорошо бы иметь хотя бы разархиватор для всех форматов архивов, использовавшихся на советских PDP-like машинах.

[kolk]

Копирую сюда Формат архива LZA.txt от @gid

проги:
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; // запись о файле в каталоге архива
    } по количеству файлов в архиве;
};

[shattered]

хорошо бы иметь хотя бы разархиватор для всех форматов архивов, использовавшихся на советских PDP-like машинах.

или хотя бы их список?

под rt-11:

FCU
LZ/UZ
LZA/UZA
PACK2
PACKER/UNPACR
PK
PRESS

+ на БК есть еще

[nzeemin]

Техническая информация по FCU.

   Итак, как было сказано  в  начале, данный продукт являет собой, по
сути, lzhuf. Если кому-то интересно как построен его алгоритм,  пусть
он  обратится  в  F-Bit  и  попросит  исходные   тексты   архиватора,
написанного Hurahiko Okumura и попробует в них  разобраться.  Я  знаю
лишь как работает lz. Есть, в принципе, из  той  же  серии  архиватор
lzarm, который  тоже основан  на  lz, но архивирует лучше. Я побоялся
его  адаптировать, хотя он был бы и короче, потому, что он работал бы
он раза в два медленнее, а выгадывал бы не более 5%. Вполне возможно,
что я напишу и его, но это будет уже другой  архиватор.  Кроме  того,
алгоритм, реализованный здесь,  имеет  два  неоценимых  качества:  он
достаточно быстр и архивирует лучше чем  PACK,  LZSS  и  ARC.  Других
архиваторов у меня нет и с ними сравнить я не могу. В сравнении с ARJ
на убогой машине  фирмы  IBM  (один  ВЭ  ЭМ  ЭР  ЭС)  он  проигрывает
где-то 3% при архивации, но зато, он может работать в 56 Кб памяти!!! 
   В архиве имеется каталог файлов, которые в нем есть. Этот  каталог
"размазан" по всему архиву. Перед  началом  файла  в  архиве  имеется
заголовок из 7 слов: 3 слова имени  (в  коде  RADIX-50),  изначальная
длина файла в блоках,  системная  дата  (старший  бит  даты  означает
что файл был защищенным и при разархивации он защищается от удаления)
далее следуют два слова, которые имеют смысл  длины  файла  в  архиве
(с точностью до  слова).  В  младшем  байте  первого  слова  хранится
количество слов, старший байт имеет специальный вид это служит ключом
того, что это заголовок. И последнее, 7-е слово содержит  число  бло-
ков, которое файл занимает в архиве. Два  последних  слова  заголовка
имеют важное значение  т.к.  во  время  разархивации  именно  на  них
делается основной опор. Если эти слова испочены, то восстановит  файл
из архива  становится  невозможным,  поэтому  предусмотрен  ключ  /.,
котоный в режиме List выводит содержимое  этих  двух  слов.  Если  Вы
хотите обезопасить свой архив,- после  архивации  сохраните  значения
этих слов в каталоге архива на диске  и  в  случае  необходимости  Вы
сможете с помощью DESS'а восстановить их.
   В след  за  заголовком  архива  расположен  собственно  архив.  Он
заканчивается двумя специальными словами: первое из них - контрольная
сумма файла (исходного), второе - контрольная сумма файла в архиве.
Длина файла в архиве дается без учета этих двух слов.
   Во время тестирования проверяется:
 - Первые три слова. Они должны быть допустимы в радиксе. Если первое
   слово имени файла ноль, архиватор считает это концом архива.
 - Длина исходного файла. Она должна быть отлична от нуля.
 - Ключефой байт в первом слове длины файла в архиве.
Если хотя бы одно из перечисленных  условий  не  соблюдено  выводится
сообщение Format archive error. Также проверяется  контрольная  сумма
файла в архиве.
   При разархивации проверяется контрольная сумма исходного файла.

Параметры сжатия из кода:

NIL	= -2
F	= 60.

;~~~~~~~~~~~~~~~~~~~~~~~~~~~ Huffman coding ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
N	= 4096.
N.char	= <254.+F>
T	= <N.char*2-1>
R	= T-1
Max.fr	= 100000

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