Сжатие LZX / LZSS, старые игры от Blizzard Опции

[-=CHE@TER=-]

Тут интересную тему подняли на Extractor.ru:
_ttp://www.extractor.ru/ipb/index.php?showtopic=2111

Нашёл описание Microsoft LZX - он ближе всех походит:
_ttp://www.nf-team.org/drmad/zf/zf5/zf5_025.htm

Занятный алгоритм. Я практически разобрал формат архивов и сжатия. Там используется какая-то модификация LZX - см. ссылку, которую я дал. Всё бы хорошо, но вот отчего-то у меня после распаковки в 64 байтах файл расходится с тем, что должно быть (там человек выкладывал файл сграбленный из памяти). А расходится из-за того, что окно (window) при распаковке ездит взад и вперёд.
В общем, за 2 дня интенсивного mindfuck'а я уже совсем отупел, хотя 90% разобрал как работает...

Формат сжатых данных:

BYTE - байт-маска, указывающие какие идут данные за ним (обрабатывать нужно задом наперёд!). Если в байте бит зажжён - значит нужно прочитать из входного файла 1 байт и переместить его в выходной поток. Если бит не зажжён, то нужно прочитать из входного файла 2 байта (WORD), которые потом интерпретируются как отсылка к уже распакованным данным (см. ниже).
Пусть наш байт будет такой: 10010111 - это значит из файл мы должны прочитать (обрабатывать нужно задом наперёд!):
BYTE BYTE BYTE WORD BYTE WORD WORD BYTE
Причём, все прочитанные байты мы сразу складываем в выходной файл, а когда читаем WORD, то делаем следующее:

Предположим мы прочитали значение типа WORD и оно равно $0FFD - первые 4 бита - количество байт, которые нужно переслать минус 3 (т.е. нужно всегда добавлять 3, чтобы получить количество для пересылки!). Оставшиеся 12 бит (вот тут засада) это адрес в уже распакованном потоке, откуда эти данные нужно читать в выходной.
Дело в том, что при распаковке выходной поток используется и как входной тоже.
В общем, для $0FFD количество байт для чтения равно 3 (0 + 3), а смещение 0xFFD от начала (?) потока.

Но, т.к. поток делится на окна по 4096 ($1000) байт, то тут возникает проблема. Дело в том, что окно смещается вместе с распакованным потоком, но как получить его точное расположение, я не понял. Пока размер распакованного потока менее 4096 - всё ок, как только стал больше, так начинаю брать смещение уже не оттуда. Что самое смешное, так это то что, похоже, экно ездит то вперёд, то назад, потому что я что только не делал и как только его сдвиг не считал - в зависимости от кувырканий, то одни, то другие байты не совпадают.

Вот исходные коды распаковщика LZX:
lzxfiles.zip (~37 Kb)

Что там внутри:
1.zlx - упакованная музыка
1.xmi - дамп распакованной
unlzx.c - исходные коды
unlzx.exe - программа
BTHORNE.EXE - исполняемый файл игры Black Thorne, в исходных кодах я оставил адреса процедуры распаковки
z.bat - после его запуска будет произведена попытка распаковать файл и появятся ещё 3 файла:
dump - распакованный поток
l - сравнение распакованного потока с оригиналом
list - это я делал вывод программы для удобства отладки

Уф...
Кто-нибудь хочет / может помочь? Я просто где-то долблюсь в стенку лбом и не вижу двери.
Наставьте, пожалуйста, на путь истинный! (*улыбается*)

[-=CHE@TER=-]

Если кто-то захочет помочь, могу на Delphi переделать...

[-=CHE@TER=-]

Всё ещё нужна помощь.
Код распаковщика на Asm'е (DOS) выдранный из игры (с моими комментариями):

CODE

; si - input buffer
;es:[di] - output buffer
;[bx] - window buffer?
;edx - uncompressed size?
; -----------------------
; DS - сегмент данных.
; SI, DI - индекс.
; DS и SI/DI связаны.
; [ds:si]=[si]
; [ds:di]=[di]
sub_10349 proc near
push ds
push si
; initialization - nothing interesting
xor eax, eax
mov cx, 400h
xor si, si
mov ds, word ptr ds:2A1Ch
@label1_01:
; $400 * 4 => 4096 fill buffer with zero (eax=0) -> memset()?
mov [si], eax
add si, 4
dec cx
jnz label1_01
xor bx, bx
xor cx, cx
mov edx, [si]
add si, 4
@start_decode:
;start decode routine
shr cx, 1
or ch, ch ; see above (*)
jnz label1_04
mov cl, [si] ; get next byte
inc si
jnz label1_03 ; check si overflow
call buffer_overflow ; error handling?..
@label1_03:
mov ch, 0FFh ; (*) it's a trick: check if we run first time, or get from loop above
@label1_04:
test cx, 1
jz label1_07 ; "read-byte" bit is not set
mov al, [si]
inc si
jnz label1_05 ; check si overflow
call buffer_overflow
@label1_05:
mov [bx], al
inc bx
and bx, 0FFFh
mov es:[di], al
inc di
jnz label1_06
mov ax, es
add ax, 1000h
mov es, ax
@label1_06:
; edx =0 - end of stream
dec edx
jz exit_from_proc
jmp start_decode
; ---------------------------------------------------------------------------
@label1_07:
push cx
mov cl, [si]
inc si
jnz label1_08 ; check si overflow
call buffer_overflow
@label1_08:
mov ch, [si]
inc si
jnz label1_09 ; check si overflow
call buffer_overflow
@label1_09:
push si
; label1_07 to label1_09 - read WORD from input stream
mov si, cx
and si, 0FFFh
; si = (cx & 0xfff)
; si - addr
and cx, 0F000h
rol cx, 4
add cx, 3
; cx = (cx >> 12) + 3
; cx - size
@slide_window_decode:
mov al, [si]
inc si
and si, 0FFFh

mov [bx], al
inc bx
and bx, 0FFFh

mov es:[di], al
inc di

jnz label1_11
mov ax, es
add ax, 1000h
mov es, ax
@label1_11:
; edx =0 - end of stream
dec edx
jz exit_from_proc_clear_stack
; while cx != 0 - copy next byte
dec cx
jnz slide_window_decode
pop si
pop cx
jmp start_decode
; ---------------------------------------------------------------------------
@exit_from_proc_clear_stack:
add sp, 4 ; remove si and cx from stack
@exit_from_proc:
pop si
pop ds
retn
sub_10349 endp

Он же на Delphi (не работает как надо):

CODE

Program unlzx;
{$APPTYPE CONSOLE}

Var
Fl: File;
B: Byte;
buff: Array[0..(1024*6)-1] Of Byte;
i, p, o, l, s, x: Integer;

Begin
FillChar(buff, 1024*6, 0);
AssignFile(Fl, '1.zlx');
FileMode:=0;
Reset(Fl, 1);
FileMode:=2;

p := 0;
s := 0;
While Not EOF(Fl) Do
Begin
b := 0;
BlockRead(Fl, B, 1);
If b = 0 Then Break;
For I := 1 To 8 Do
Begin
// if bit is set - read byte to output buffer
If (b And 1 <> 0) Then
Begin
BlockRead(Fl, buff[p], 1, x);
p := p+1;
End
Else
Begin
// else - read word, size&offs
// buffer shift value
o := 0;
BlockRead(Fl, o, 2, x);
l := (o ShR 12) + 3; // length
o := o And $fff; // addr
// not sure about this
if p > $1000 Then
s := p - $1000
else
s := 0;
While l > 0 Do
Begin
buff[p] := buff[s + o];
o := ((o + 1) And $fff);
p:=p+1;
l:=l-1;
End;
End;
// go to next bit
b := b ShR 1;
End;
End;
CloseFile(Fl);

p := 4969;
buff[p-1] := 0;

AssignFile(Fl, 'dump');
ReWrite(Fl, 1);
BlockWrite(Fl, buff, p);
CloseFile(Fl);
End.

[Axsis]

Всё ещё нужна помощь.

если я верно понял асм листинг, то там во входном сегменте данных первые 4096 байт выделяются под временный буфер ("окно" в твоей терминологии), потом 4 байта - размер распакованных данных, потом идут запакованные данные. так вот в этот временный буфер заносятся данные по мере распаковки, и как только размер распакованных данных превышает размер буфера (4096 б) - он начинает затираться с начала. иными словами там хранятся последние 4096 распакованных байта. а смещение считается всегда относительно начала буфера. попробуй реализовать через второй буфер (один выходной и один временный), вместо высчитывания смещения в выходном буфере будешь брать данные из временного по прочитанному в word'е смещению. имхо так проще для понимания.

[-=CHE@TER=-]

Спасибо большое!
Изменил на вот такое - всё равно в 64 байтах различие.
Что я забыл?

CODE

Program unlzx;
{$APPTYPE CONSOLE}

Var
Fl: File;
B: Byte;
buff: Array[0..(1024*6)-1] Of Byte;
loop: Array[0..$fff] Of Byte;
lidx: Integer;
i, p, o, l, x: Integer;

Begin
FillChar(buff, 1024*6, 0);
AssignFile(Fl, '1.zlx');
FileMode:=0;
Reset(Fl, 1);
FileMode:=2;

p := 0;
lidx:=0;
FillChar(loop, $fff + 1, 0);
While Not EOF(Fl) Do
Begin
b := 0;
BlockRead(Fl, B, 1);
If b = 0 Then Break;
For I := 1 To 8 Do
Begin
// if bit is set - read byte to output buffer
If (b And 1 <> 0) Then
Begin
BlockRead(Fl, buff[p], 1, x);
loop[lidx]:=buff[p];
lidx:=(lidx + 1) And $fff;
p := p + 1;
End
Else
Begin
// else - read word, size&offs
// buffer shift value
o := 0;
BlockRead(Fl, o, 2, x);
l := (o ShR 12) + 3; // length
o := o And $fff; // addr
// loop
While l > 0 Do
Begin
buff[p] := buff[o];
p:=p + 1;
loop[lidx] := buff[o];
lidx:=(lidx + 1) And $fff;
o := ((o + 1) And $fff);
l:=l - 1;
End;
End;
// go to next bit
b := b ShR 1;
End;
End;
CloseFile(Fl);

p := 4969;
buff[p-1] := 0;

AssignFile(Fl, 'dump');
ReWrite(Fl, 1);
BlockWrite(Fl, buff, p);
CloseFile(Fl);
End.

[Axsis]

по идее в этом блоке

CODE

        While l > 0 Do
        Begin
          buff[p] := buff[o];
          p:=p + 1;
          loop[lidx] := buff[o];
          lidx:=(lidx + 1) And $fff;
          o := ((o + 1) And $fff);
          l:=l - 1;
        End;

вместо buff[o] надо брать байт loop[o] (в обоих местах)

CODE

        While l > 0 Do
        Begin
          buff[p] := loop[o];
          p:=p + 1;
          loop[lidx] := loop[o];
          lidx:=(lidx + 1) And $fff;
          o := (o + 1) And $fff;
          l:=l - 1;
        End;

по идее так дожно быть.
для того этот второй буфер и нужен был, потому что смещение 'o' отсчитывается от его начала, а данные в буфере "плавают" - lidx (указатель на байт в который мы сейчас запишем новые распакованные данные) циклически увеличивается.

[-=CHE@TER=-]

Сравнение файлов 1.xmi и DUMP
FC: различия не найдены

Axsis! Ты мозг! Спасибо громадное!
Просто я уже в нескольких старых игрушках натыкался на это сжатие и подумал, что было бы неплохо иметь программу для распаковки.

Добавлено:
Исправляюсь - может и не во многих, но в некоторых что-то похожее.

[-=CHE@TER=-]

Таки решил дожать это дело.
Ещё раз прочитав то что написал Axsis взглянул на алгоритм и вспомнил, что где-то я его уже видел.
Так и вышло.
Тему можно считать закрытой. (*улыбается*)

Мои ошибки:
1) Сейчас глядя на ассемблреный код дошло, что там не 1024 байта в массиве для кольцевого буфера (loopback), а 1024 по 4 байта (eax для зануления используется) - т.е. 4096 байта!
2) Весьма неожиданно, что начальный счётчик в кольцевом буфере должен быть равен 0, а не ($FFF + 1) - 16.
3) То что у смещения и длинны полубайты хранятся наоборот (в отличие от классического алгоритма) выжрало мне мозг основательно, пока я не начал вручную выписывать последовательности и не увидел что к чему.