1 Отредактировано Voldemar0 (28-04-2019 16:16)

Тема: Архивация в общем и архиватор Lempel Ziv

Привет!

Есть у нас в коллекции архиватор от некоего "Родионов В.А. (c) 1992".
Он не просто пакует файл, уменьшая объём, но ещё и делает self-extractor: прогу, которая при запуске
саму себя распаковывает.

И то тут то там всякие проги проскакивают, которые им запакованы.

Некоторая неприятность состоит в том, что отдельного распаковщика нет.
Между тем, для сравнения/сортировки файлов удобно иметь его незапакованный вариант.

Пока что я понял только, что если после загрузки запакованного файла в память
поставить breakpoint на адрес $203, то сразу за этой остановкой будет вызвана
процедура распаковки, а следом - $206 - вызов счётчика контрольной суммы.
По адресу $209 - сравнение вычисленной суммы с сохранённым оригиналом.

Причем несколько огорчает тот факт, что повреждённая программа просто вызывает RESET (jmp ($FFFC)),
даже не сообщая каким нибудь текстом об ошибке.

В начале сжатых файлов есть сигнатура "LZP".

Если среди нас есть любители архивации, то может быть они могут попробовать
написать распаковщик таких файлов ? Идеальной была бы минимальная прога
на C или Pascal'е.

Такая же задачка стоит для файлов редактора "Документ": с версии 3.0, кажется,
он умеет запаковывать свои тексты. И, к сожалению, в dos33c2 встроенного распаковщика для них
пока нет. Алгоритм сжатия неизвестен, но, возможно, это всё тот же LZ или LZW.

Эти файлы начинаются с сигнатуры "PACKED".

В аттаче архиватор Родионова, сам собой же и запакованный.

Post's attachments

Attachment icon lzp.zip 5.97 kb, 275 downloads since 2019-04-28 

2

Re: Архивация в общем и архиватор Lempel Ziv

Как минимум один любитель архивации есть :)
Похоже, какой-то вариант LZSS. Попробую расковырять.

3

Re: Архивация в общем и архиватор Lempel Ziv

Пример упакованного и распакованного текста

Post's attachments

Attachment icon doc_packed.zip 1.23 kb, 249 downloads since 2019-04-29 

4

Re: Архивация в общем и архиватор Lempel Ziv

Распаковщик LZP сделал. Меня, правда, озадачило, что распакованный файл оказался 8 килобайт в размере (там куча нулей в конце) и с другим начальным адресом (исходник и распакованный файл в аттаче). Возможно, архиватор определяет, что его пытаются заархивировать и как-то по особому себя ведет.

-----------
Пару мыслей по архиватору и формату архива. Это 100% не RLE, не байтовый упаковщик, а точно вариант алгоритма LZSS.

Меня, конечно, любопытство загрызло: насколько это оригинальная разработка? И стоит ли писать распаковщик, может, он давно в интернете лежит :) Все-таки, в 1992-м не так много было информации по этим алгоритмам. Лично я на тот момент знал только про RLE, а что-то почитать по Лемпелю с Зивом удалось только парой лет позже. То есть почитать-то можно было и раньше, но для этого надо было откуда-то узнать эти фамилии.

Я попытался найти какие-то "корни", но все оказалось очень туманно. Вариантов LZSS было написано видимо-невидимо. Известно, что большая их часть создавалась на базе кода, который в 1989 году написал японец Харухико Окумура. В 90-м году под MSX был сделан упаковщик исполняемых файлов PMEXE, но описания его формата архива я не нашел.

Сам алгоритм состоит в том, что берутся байты из входного потока, проверяется, не встречалась ли такая же последовательность байт раньше, и если встречалась, то вместо самих байт пишутся битовый флаг, смещение относительно текущей позиции и длина последовательности. Это называется обратная ссылка или back reference. Если повтор найти не удалось, то пишется другой битовый флаг и исходный байт. Это называется литерал.

В LZP используется тот же формат ссылок, что и в оригинальном LZSS (12 бит - смещение, 4 бита - длина). Но в дополнение к этому формату ссылок добавлено еще два - с 8-битовым смещением и 2-битовой длиной, и с 12-битовым смещением и 8-битной длиной. В общем, схожесть с LZSS прослеживается, но явно добавлено что-то свое.

При распаковке, насколько я понял, упакованные данные переписываются так, чтобы уместиться до адреса $BFFF. Потом распаковщик их читает и распаковывает в нужный адрес.

В коде распаковщика несколько приколов. Сам он переписывается по адресу $200, а потом, путем патчинга инструкций, ему передаются адрес упакованных данных, значение контрольной суммы и адрес для передачи управления.
До смешного доходит - вот как передается адрес упакованных данных:

    LDA STARTADDR
    STA PATCH1 + 1

    LDA STARTADDR + 1
    STA PATCH2 + 1

Ответная часть в распаковщике выглядит так:

PATCH1    LDA #0
    STA $D4
PATCH2    LDA #0
    STA $D5

Казалось бы, почему бы сразу не вписать адрес в ячейки $D4, $D5? Особенно учитывая, что целевой адрес для распаковки прописывается сразу в нулевую страницу, без патчинга :)

Такая же ерунда с адресом выполнения. По умолчанию там захардкожен JMP по адресу $E003. Похоже на адрес входа в Бейсик Apple, кстати :) А потом адрес патчится на правильный. Но, блин, рядышком стоит косвенный JMP по адресу $FFFC! Почему нельзя было сделать два косвенных JMP?

Кстати, идея проверять контрольную сумму после распаковки, мне кажется, не слишком удачная. Потому что, если повреждены упакованные данные, то при распаковке может случиться что угодно. Например, данных распакуется больше, чем нужно и что-то в памяти будет затерто, либо цикл распаковки не остановится вообще.
В распаковщике есть проверка, чтобы текущий адрес распакованных данных не превысил текущий адрес упакованных. Но почему-то только в одной из веток кода.

Post's attachments

Attachment icon AgatLZPUnpack.cpp 4.03 kb, 240 downloads since 2019-05-07 

Attachment icon LZP-UNPACK.FIL 8.04 kb, 267 downloads since 2019-05-07 

5 Отредактировано Voldemar0 (10-05-2019 12:14)

Re: Архивация в общем и архиватор Lempel Ziv

Спасибо!

А подсчёт контрольной суммы не стал делать?

В аттаче ещё примеры.

Post's attachments

Attachment icon lzp-gam.zip 25.52 kb, 263 downloads since 2019-05-10 

6

Re: Архивация в общем и архиватор Lempel Ziv

Voldemar0 пишет:

А подсчёт контрольной суммы не стал делать?

Хотел сделать, но забыл. Сейчас прикрутил (там просто XOR всех байтов) и вылезла такая фигня: у всех файлов из
lzp-gam.zip код, подготавливающий распаковку, более короткий, поэтому значения адресов и контрольной суммы оказались по другому смещению. Надо прикручивать проверку версии распаковщика и заново выяснять, где эти значения находятся.

7 Отредактировано avivanov76 (10-05-2019 22:30)

Re: Архивация в общем и архиватор Lempel Ziv

Новая версия, улучшенная и дополненная :)
Вроде как все адреса привязаны к положению сигнатуры "LZP", так что теперь сначала ищется эта строка (и еще 3 байта), а потом все считается относительно нее.

Post's attachments

Attachment icon AgatLZPUnpack.cpp 5.09 kb, 286 downloads since 2019-05-10 

8 Отредактировано Voldemar0 (11-05-2019 14:58)

Re: Архивация в общем и архиватор Lempel Ziv

PACKER_SIZE - объявлена в начале, но не везде используется

Проверил в эмуле: lzp.generic действительно распаковывает себя с нулями до $39FF.

Но при записи длинна распакованного файла ставиться так, что байт по смещению $39FF уже неопределён (выпадает из файла).
С другими файлами также: последний байт как бы выпадает из распаковки.
Пока не пойму - это ошибка данного распаковщика или что-то в упаковщике ?

Например, когда распаковывается TETRIS из архива, последние байты должны быть такие:
49E0:  C0 AD 00 C0 10 FB A9 4C - 8D 81 9E A9 FD 8D 82 9E
В эмуляторе он распаковывается, но в CPP теряется.

-=-

В главном while(1) я нашел только один break, и что-то мне подсказывает, что в случае мусора в архиве распаковщик может подвиснуть? Там нет контроля выхода за пределы buf_size ?

9

Re: Архивация в общем и архиватор Lempel Ziv

PACKER_SIZE используется в проверке, что длина файла после вычитания всех заголовков окажется не меньше, чем длина собственно распаковщика. Это было правильно, пока я думал, что длина распаковщика не меняется. Но вообще, эту проверку надо бы разбить на две: первая должна проверять, что есть собственно заголовки FIL и Binary, а вторая - проверять, с учетом положения в файле сигнатуры ""LZP", что данных в файле достаточно, чтобы прочитать все адреса и контрольную сумму.

"-1" не нужно, это я длину с адресом попутал.

10 Отредактировано Voldemar0 (11-05-2019 15:05)

Re: Архивация в общем и архиватор Lempel Ziv

Вероятно, должно быть так:
bh.length = write_ptr;
и тут:
fwrite(output_buf, write_ptr, 1, dst);

11

Re: Архивация в общем и архиватор Lempel Ziv

Voldemar0 пишет:

В главном while(1) я нашел только один break, и что-то мне подсказывает, что в случае мусора в архиве распаковщик может подвиснуть? Там нет контроля выхода за пределы buf_size ?

Да, контроля нет, надо добавить в ReadByte.

Voldemar0 пишет:

Вероятно, должно быть так:
bh.length = write_ptr;
и тут:
fwrite(output_buf, write_ptr, 1, dst);

Точно.

12

Re: Архивация в общем и архиватор Lempel Ziv

Интересно, что TETRIS, BOMBER и XONIX у меня в эмуляторе запустились и работали без последнего байта :)

13

Re: Архивация в общем и архиватор Lempel Ziv

> Интересно, что TETRIS, BOMBER и XONIX у меня в эмуляторе запустились и работали без последнего байта :)

99%, что авторы собирали их из нескольких кусков, при этом никакой автоматизации не было. Поэтому
они просто делали что-то вроде BLOAD piece1, BLOAD piece2... BSAVE GAM, A$2000,L$2000.
Последнее число - размер файла, тупо вбивали примерно нужную цифру, в итоге в хвосте файла много или мало мусора. И между piece1 и piece2 тоже. Так же часто поступали и всякие передельщики.

Я про это писал когда-то, ещё в теме про ca65 или линкере.

-=-=

Подправил на чистый C, добавил обход текущего каталога и распаковки всего, что найдётся.
Проверку диапазона тоже добавил, но пока ей срабатывать не на чем.

// Можно запустить следующими способами:
// - без аргументов: распаковка всех, найденных в текущем каталоге, файлов,
//      результат в файле с расширением ".unlz.FIL".
// - специальный аргумент "rm": тоже самое, но с удалением успешно распакованных архивов
// - один аргумент: распаковка указанного архива, результат в файле с расширением ".unlz.FIL"
// - два аргумента: распаковка указанного архива, результат в файле с именем, заданным вторым аргументом
Post's attachments

Attachment icon unlzp.c 7.24 kb, 260 downloads since 2019-05-11 

14 Отредактировано Voldemar0 (11-05-2019 17:02)

Re: Архивация в общем и архиватор Lempel Ziv

Попробовал ковырнуть тексты упакованные в среде Документ - там что-то более сложное.
Я надеялся, что алгоритм тот же, так как автор тот же - Родионов - но нет.

Файл начинается с сигнатуры Packed\0\0\1. А дальше идёт какая-то структура, похожая на словарь: она читается и затем постоянно используется при распаковке.
Удалось выяснить только следующее:

                // Формат:                                                                                          
                D0 61 4B 65 44 00 00 01  - сигнатура                                                                
                1байт                       - размер "словаря"                                                         
                поток байт              - словарь (?)                                                              
                2байта                        - u_int16_t ? размер ? указатель ?
                1байт                       - u_int16_t ? дополняется спереди константой 08 и дальше ? размер ? указатель ?
последующие байты анализируются в главном цикле распаковки.

15

Re: Архивация в общем и архиватор Lempel Ziv

В Документе точно что-то другое. Когда текст сжат LZSS, то его начало можно просто прочитать, он только немного разбавлен управляющими байтами. Потом, когда алгоритм "разгонится" и ему станет где искать повторения, текст уже почти не читается, только отдельные символы.

Здесь не читается ничего, кроме кусочка в самом конце, но я думаю, этот кусочек просто "мусор" и к упакованным данным не относится. Так что алгоритм тут другой.

Вариантов скорее всего два: коды Хаффмана и LZW. К сожалению, без дизассемблирования самого редактора это вряд-ли удастся выяснить.

16

Re: Архивация в общем и архиватор Lempel Ziv

                         Unpack2:
DF06 -   A9 08 ..   ")."    LDA   #08
DF08 -   20 AE 20   "..."   JSR   X               # C8/C9 += A
DF0B -   A5 C8 ..   "%H"    LDA   C8
DF0D -   85 DA ..   ".Z"    STA   InputPTR_L
DF0F -   A5 C9 ..   "%I"    LDA   C9        
DF11 -   85 DB ..   ".["    STA   InputPTR_H
DF13 -   20 C3 DF   ".C_"   JSR   GetByte         # return buf[InputPTR++]
DF16 -   8D 8C 1D   "..."   STA   DictSize
DF19 -   A2 00 ..   ""."    LDX   #00
                         DicLoadLoop:
DF1B -   20 C3 DF   ".C_"   JSR   GetByte         # return buf[InputPTR++]
DF1E -   9D 00 BD   "..="   STA   Dictonary, X
DF21 -   E8 .. ..   "Х"     INX   
DF22 -   EC 8C 1D   "Л.."   CPX   DictSize
DF25 -   D0 F4 ..   "PТ"    BNE   DicLoadLoop
DF27 -   20 C3 DF   ".C_"   JSR   GetByte         # return buf[InputPTR++]
DF2A -   8D 81 1D   "..."   STA   OutSize_H
DF2D -   20 C3 DF   ".C_"   JSR   GetByte         # return buf[InputPTR++]
DF30 -   8D 80 1D   "..."   STA   OutSize_L
DF33 -   A9 30 ..   ")."    LDA   #30
DF35 -   85 D9 ..   ".Y"    STA   OutPTR_H
DF37 -   A9 03 ..   ")."    LDA   #03
DF39 -   85 D8 ..   ".X"    STA   OutPTR_L        # $3003..
DF3B -   20 CE DF   ".N_"   JSR   X_2proc0
                         ExtractLoop:
DF3E -   A9 00 ..   ")."    LDA   #00
DF40 -   8D 87 1D   "..."   STA   Z0     
DF43 -   8D 8B 1D   "..."   STA   Z1
DF46 -   20 D2 DF   ".R_"   JSR   GetBit          # return C= SomeByte.0, SomeByte >> 1
DF49 -   08 .. ..   "."     PHP   
DF4A -   20 D2 DF   ".R_"   JSR   GetBit          # return C= SomeByte.0, SomeByte >> 1
DF4D -   08 .. ..   "."     PHP   
DF4E -   20 D2 DF   ".R_"   JSR   GetBit          # return C= SomeByte.0, SomeByte >> 1
DF51 -   2E 87 1D   "..."   ROL   Z0
DF54 -   28 .. ..   "."     PLP   
DF55 -   2E 87 1D   "..."   ROL   Z0
DF58 -   28 .. ..   "."     PLP   
DF59 -   2E 87 1D   "..."   ROL   Z0
DF5C -   AE 87 1D   "..."   LDX   Z0
DF5F -   E0 07 ..   "Ю."    CPX   #07
DF61 -   D0 02 ..   "P."    BNE   Loop0
DF63 -   A2 00 ..   ""."    LDX   #00
                         Loop0:
DF65 -   20 D2 DF   ".R_"   JSR   GetBit          # return C= SomeByte.0, SomeByte >> 1
DF68 -   6E 8B 1D   "н.."   ROR   Z1
DF6B -   CA .. ..   "J"     DEX   
DF6C -   10 F7 ..   ".В"    BPL   Loop0
DF6E -   A9 07 ..   ")."    LDA   #07
DF70 -   CD 87 1D   "M.."   CMP   Z0
DF73 -   D0 0A ..   "P."    BNE   If0
DF75 -   18 .. ..   "."     CLC   
DF76 -   2E 8B 1D   "..."   ROL   Z1
DF79 -   2E 8B 1D   "..."   ROL   Z1
DF7C -   4C 8A DF   "l._"   JMP   DF8A

                         If0:
DF7F -   38 .. ..   "."     SEC   
DF80 -   ED 87 1D   "М.."   SBC   Z0
DF83 -   AA .. ..   "*"     TAX   
                         Loop1:
DF84 -   4E 8B 1D   "n.."   LSR   Z1
DF87 -   CA .. ..   "J"     DEX   
DF88 -   D0 FA ..   "PЗ"    BNE   Loop1
DF8A -   A9 01 ..   ")."    LDA   #01
DF8C -   AE 87 1D   "..."   LDX   Z0
                         Loop3:
DF8F -   0A .. ..   "."     ASL   A
DF90 -   CA .. ..   "J"     DEX   
DF91 -   10 FC ..   ".Э"    BPL   Loop3
DF93 -   18 .. ..   "."     CLC   
DF94 -   6D 8B 1D   "м.."   ADC   Z1
DF97 -   AA .. ..   "*"     TAX   
DF98 -   BD 00 BD   "=.="   LDA   Dictonary, X
DF9B -   A0 00 ..   " ."    LDY   #00
DF9D -   91 D8 ..   ".X"    STA   (OutPTR_L), Y   # $3003..
DF9F -   E6 D8 ..   "ФX"    INC   OutPTR_L        # $3003..
DFA1 -   D0 05 ..   "P."    BNE   DFA8
DFA3 -   E6 D9 ..   "ФY"    INC   OutPTR_H   
DFA5 -   20 D0 27   ".P."   JSR   Sound      
DFA8 -   CE 80 1D   "N.."   DEC   OutSize_L  
DFAB -   AD 80 1D   "-.."   LDA   OutSize_L
DFAE -   C9 FF ..   "IЪ"    CMP   #FF        
DFB0 -   D0 03 ..   "P."    BNE   DFB5       
DFB2 -   CE 81 1D   "N.."   DEC   OutSize_H
DFB5 -   AD 81 1D   "-.."   LDA   OutSize_H  
DFB8 -   F0 03 ..   "П."    BEQ   DFBD
                         ExtractLoo2:
DFBA -   4C 3E DF   "l._"   JMP   ExtractLoop

DFBD -   AD 80 1D   "-.."   LDA   OutSize_L
DFC0 -   D0 F8 ..   "PЬ"    BNE   ExtractLoo2
DFC2 -   60 .. ..   "ю"     RTS   

                         GetByte:                 # return buf[InputPTR++]
DFC3 -   A0 00 ..   " ."    LDY   #00
DFC5 -   B1 DA ..   "1Z"    LDA   (InputPTR_L), Y
DFC7 -   E6 DA ..   "ФZ"    INC   InputPTR_L 
DFC9 -   D0 02 ..   "P."    BNE   DFCD
DFCB -   E6 DB ..   "Ф["    INC   InputPTR_H
DFCD -   60 .. ..   "ю"     RTS   
                         X_2proc0:
DFCE -   08 .. ..   "."     PHP   
DFCF -   4C DB DF   "l[_"   JMP   DFDB

                         GetBit:                  # return C= SomeByte.0, SomeByte >> 1
DFD2 -   4E 83 1D   "n.."   LSR   SomeByte
DFD5 -   08 .. ..   "."     PHP   
DFD6 -   CE 82 1D   "N.."   DEC   BitCounter 
DFD9 -   D0 0B ..   "P."    BNE   DFE6       
DFDB -   20 C3 DF   ".C_"   JSR   GetByte         # return buf[InputPTR++]
DFDE -   8D 83 1D   "..."   STA   SomeByte   
DFE1 -   A9 08 ..   ")."    LDA   #08        
DFE3 -   8D 82 1D   "..."   STA   BitCounter
DFE6 -   28 .. ..   "."     PLP   
DFE7 -   60 .. ..   "ю"     RTS   

Не то, чтобы процедурка очень простая, но неспешно её можно перевести на C.
Думаю, у меня получится.

17 Отредактировано Voldemar0 (13-05-2019 20:21)

Re: Архивация в общем и архиватор Lempel Ziv

Покамест не совсем, то хотелось бы, но всё же на выходе результат напоминает текст, временами даже читаемый.

        launch_address = 0x3003;
        printf("Pack found offset: $%04X\r\n", lzpstart);
        lzpstart += sizeof(PACKED_ID);
        Dict_len = input_buf[lzpstart++];
        Dictonary = input_buf + lzpstart;
        lzpstart += Dict_len;
        output_size = (input_buf[lzpstart+0] << 8) + input_buf[lzpstart+1];
        input_ptr = lzpstart + 2;
//...........
        byte Z0, Z1, c0, c1, c2, c;
        while ((! out_of_range) && (write_ptr < output_size)) {
            c0 = GetBit(); c1 = GetBit(); c2 = GetBit();
            Z0 = (c2 << 2) | (c1 << 1) | (c0 << 0);
            if (Z0 == 7) Z0 = 0;

            Z1 = 0;
            for (c = Z0 + 1; c > 0; c--) Z1 = (GetBit() << 7) | (Z1 >> 1);

            if (Z0 == 7) {
                Z1 <<= 2;
            } else {
                // for (c = 7 - Z0; c > 0; c--) Z1 >>= 1;
                Z1 >>= (7 - Z0);
            };

            c = 1 << (Z0 + 1);
            c += Z1;
            if (c >= Dict_len) return -1;
            output_buf[write_ptr++] = Dictonary[c];
        }; // loop

18

Re: Архивация в общем и архиватор Lempel Ziv

Я попробовал с текстом doc_packed.zip и у меня распаковался именно тот текст, который был упакован.
Правда не сразу. Вот это место

            if (Z0 == 7) Z0 = 0;

лучше переписать так

        byte bitctr = Z0;
        if (Z0 == 7)
            bitctr = 0;

        Z1 = 0;
        for (c = bitctr + 1; c > 0; c--) Z1 = (GetBit() << 7) | (Z1 >> 1);

потому что исходное значение Z0 потом используется дальше.

19 Отредактировано Voldemar0 (14-05-2019 15:44)

Re: Архивация в общем и архиватор Lempel Ziv

И ещё одна ошибка тут:

Z1 <<= 2;

следует уточнить так:

byte d7 = (Z1 >> 7);
Z1 <<= 2;
Z1 |= d7;

PS Один из аргументов, почему иногда имеет смысл писать что нибудь на ассемблере: а попробуйте такой укуренный код переписать на какой нибудь язык высокого уровня... Так же фигня и в кодировании данных для записи на 140кб флопик. Та же фигня при написании эмуляторов: на сколько statements нужно развернуть какую нибудь команду типа adc, которая есть во всех, наверное, ассемблерах.

20

Re: Архивация в общем и архиватор Lempel Ziv

Вроде бы финальная версия проги.
Файлы опознаёт по сигнатурам, применяет подходящий метод распаковки.

Post's attachments

Attachment icon unlzp.c 9.1 kb, 272 downloads since 2019-05-14