Сжатие LZX / LZSS, старые игры от Blizzard |
Добро пожаловать, гость ( Вход | Регистрация )
Сжатие LZX / LZSS, старые игры от Blizzard |
-=CHE@TER=- |
Jun 20 2010, 13:46
Сообщение
#1
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
Тут интересную тему подняли на 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=- |
Jul 1 2010, 09:09
Сообщение
#2
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
Если кто-то захочет помочь, могу на Delphi переделать...
|
-=CHE@TER=- |
Mar 12 2011, 12:47
Сообщение
#3
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
Всё ещё нужна помощь.
Код распаковщика на 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 |
Mar 13 2011, 22:45
Сообщение
#4
|
Advanced Member Группа: CTPAX-X Сообщений: 121 Регистрация: 6-February 08 Пользователь №: 374 Спасибо сказали: 149 раз(а) |
Всё ещё нужна помощь. если я верно понял асм листинг, то там во входном сегменте данных первые 4096 байт выделяются под временный буфер ("окно" в твоей терминологии), потом 4 байта - размер распакованных данных, потом идут запакованные данные. так вот в этот временный буфер заносятся данные по мере распаковки, и как только размер распакованных данных превышает размер буфера (4096 б) - он начинает затираться с начала. иными словами там хранятся последние 4096 распакованных байта. а смещение считается всегда относительно начала буфера. попробуй реализовать через второй буфер (один выходной и один временный), вместо высчитывания смещения в выходном буфере будешь брать данные из временного по прочитанному в word'е смещению. имхо так проще для понимания. Спасибо сказали:
|
-=CHE@TER=- |
Mar 14 2011, 07:55
Сообщение
#5
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
Спасибо большое!
Изменил на вот такое - всё равно в 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 |
Mar 14 2011, 16:28
Сообщение
#6
|
Advanced Member Группа: CTPAX-X Сообщений: 121 Регистрация: 6-February 08 Пользователь №: 374 Спасибо сказали: 149 раз(а) |
по идее в этом блоке
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=- |
Mar 15 2011, 03:32
Сообщение
#7
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
QUOTE Сравнение файлов 1.xmi и DUMP FC: различия не найдены Axsis! Ты мозг! Спасибо громадное! Просто я уже в нескольких старых игрушках натыкался на это сжатие и подумал, что было бы неплохо иметь программу для распаковки. Добавлено: Исправляюсь - может и не во многих, но в некоторых что-то похожее. Спасибо сказали:
|
-=CHE@TER=- |
Nov 23 2016, 15:10
Сообщение
#8
|
Walter Sullivan Группа: Root Admin Сообщений: 1,361 Регистрация: 4-February 08 Пользователь №: 3 Спасибо сказали: 314 раз(а) |
Таки решил дожать это дело.
Ещё раз прочитав то что написал Axsis взглянул на алгоритм и вспомнил, что где-то я его уже видел. Так и вышло. Тему можно считать закрытой. (*улыбается*) Мои ошибки: 1) Сейчас глядя на ассемблреный код дошло, что там не 1024 байта в массиве для кольцевого буфера (loopback), а 1024 по 4 байта (eax для зануления используется) - т.е. 4096 байта! 2) Весьма неожиданно, что начальный счётчик в кольцевом буфере должен быть равен 0, а не ($FFF + 1) - 16. 3) То что у смещения и длинны полубайты хранятся наоборот (в отличие от классического алгоритма) выжрало мне мозг основательно, пока я не начал вручную выписывать последовательности и не увидел что к чему. |
Упрощённая версия | Сейчас: 30th October 2024 - 19:17 |