Описание: Разбор алгоритма LZSS |
Поиск в теме | Версия для печати |
TrickZter |
Отправлено: 03 Февраля, 2016 - 06:03:34
|
Покинул форум
Сообщений всего: 560
Дата рег-ции: Июнь 2015
|
TrickZter
Алгоритм LZ сжатия легко определяется "на глаз" - достаточно сравнить несжатое изображение со сжатым. Например в LZ77 на ГБА алгоритм такой:
Заголовок из 4-х байт
1 флаговый байт
8 блоков
1 флаговый байт
8 блоков
1 флаговый байт
8 блоков
и т.д.
Заголовок представляет из себя 4-ку байт, первый из которых обязательно равен h10, три других байта - это размер запакованных данных.
Биты флагового байта указывают нам какого типа блоки идут после него, если бит равен 0, значит идёт 1 не пожатый байт, если же равен 1, то идёт пара байт сжатия.
Допустим флаговый байт равен h44, представим его в двоичном виде: 01000100
Это значит что сначала идёт 1 несжатый байт, потом идёт пара байт сжатия, потом идёт 3 несжатых байта, потом опять пара сжатия, потом ещё два несжатых байта.
Что представляет из себя пара сжатия? Это количество копируемых байтов и смещение (отсылка назад) - указатель с какого байта начинать копирование. Рассмотрим пример, допустим пара байт сжатия у нас такая: 80 01, представим её в двоичном виде:
10000000 00000001
Подчёркнутые биты - это длина отрезка, остальные - это смещение.
1000 в десятичном виде - это 8, добавляем к нему 3 и получаем длину копируемого отрезка - 11 байт. 000000000001 в десятичном виде - это 1, добавляем к нему 1 и получаем величину смещения 2, то есть копировать байты нужно начиная с 2-го байта с конца. |
|
|
alex_231 |
Отправлено: 03 Февраля, 2016 - 06:04:34
|
Chief-Net
Покинул форум
Сообщений всего: 4688
Дата рег-ции: Окт. 2014
|
alex_231
Что-то тут странное сжатие - пакеты без заголовков идут, судя по всему.
Цитата:1 флаговый байт
8 блоков
1 флаговый байт
8 блоков
1 флаговый байт
8 блоков
и т.д.
1-й байт - флаговый в обратном порядке (1-байт,0-код), например:
по байту FD (11111101) блоки идут так:
11111101
87654321
обработка блоков:
1-й блок - 1байт копируется без каких-либо операций
2-й блок - 2байта - код отправляющий копировать определенное число байт из указанного места
3-й блок - 1байт копируется без каких-либо операций
4-й блок - 1байт копируется без каких-либо операций
5-й блок - 1байт копируется без каких-либо операций
6-й блок - 1байт копируется без каких-либо операций
7-й блок - 1байт копируется без каких-либо операций
8-й блок - 1байт копируется без каких-либо операций
затем опять читается флаговый байт и всё по-новой.
Обработка кода:
2 байта:
0000|1010|0000|0001
0123 4567 89AB CDEF
биты BCDEF - количество копируемых байт из исходника, для копирования увеличивается на 2 (в примере будет скопировано 3 байта)
биты 01234567 - указатель на исходник для копирования
однако к значению 0123 (в примере: 0) нужно прибавить 2, и к значению 4567 (в примере: 10) тоже нужно прибавить 2, таким образом в примере получается, что будет скопировано 3 байта начиная с h2С от начала пакета.
Назначение бит 89A мне пока не ясно.
Однако:
вариант E261
1110|0000|0110|0001
0123 4567 89AB CDEF
ссылается на 2-й байт от начала пакета:
1110 = hE + h2 = h10, 0000 = 0 + 2 = 2, а так как
_1__0____2
_1|0000|0010
-1|0123|4567
то, значение десятков отбрасывается.
Причём, я заметил, что когда биты 012 = 111, то биты 89A = 011.
----- Делая выбор, отбрось простое решение и выбери правильное...
|
|
|
alex_231 |
Отправлено: 03 Февраля, 2016 - 06:05:11
|
Chief-Net
Покинул форум
Сообщений всего: 4688
Дата рег-ции: Окт. 2014
|
alex_231
Я же сказал: посмотреть в памяти эмулятора как выглядит графика заставки в незапакованном виде и попробовать найти часть последовательности в роме.
Я искал так:
1. запустил игру,
2. дождался заставки,
3. открыл окно Tile Viewer, чтобы узнать в каком месте памяти лежит искомая графика (0x8800),
4. открыл окно Memory viewer, перешел по найденному адресу
5. открыл ром в Translhextion,
6. задал HEX-поиск: 0F103020 (идущие подряд четыре уникальных неповторяющихся байта недалеко от адреса 0x8800 из видеопамяти)
7. нашел искомую комбинацию по адресу 0x28C53,
а дальше - откатился по рому назад, до начала пакета, сопоставляя ром и содержимое видеопамяти.
Кстати графика заставки побита на две части. вторую сможешь сам найти по описанной методике?
----- Делая выбор, отбрось простое решение и выбери правильное...
|
|
|
Ace Lightning |
Отправлено: 03 Февраля, 2016 - 06:07:45
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Ace Lightning
Вот не сжатая последовательность байт (в памяти эмулятора):
03 02 01 01 00 00 00 00 00 00 01 01 0F 0F 10 30
курсивом обозначил байты, которые были сжаты
Вот сжатая последовательность (в самом роме):
03 02 03 02 01 01 00 E4 62 FF 01 01 0F 0F 10
А вот эти байты, которые я выдели жирным, видимо отвечают за сжатие.
Запишем их так:
1110 0100 0110 0010
E+2=10
4+2=6
00010=2
2+2=4
Получается, что копируется 4 байта с адреса h06 от начала пакета. Но Что-то как-то не вяжется, т.к мне нужно скопировать 5 байт.. или я чего-то не понимаю?
P.S. Да, и ещё меня напрягают некоторые байты, которые находятся в изначальной последовательности, но их нет, когда я просматриваю уже разжатую последовательность в эмуляторе. Вот как раз в данном примере в последовательности откуда-то взялся байт FF:
03 02 03 02 01 01 00 E4 62 FF 01 01 0F 0F 10
Я посмотрел чуть ниже, там ещё встречался байт FB.. |
|
|
TrickZter |
Отправлено: 03 Февраля, 2016 - 06:08:30
|
Покинул форум
Сообщений всего: 560
Дата рег-ции: Июнь 2015
|
TrickZter
Цитата:Вот сжатая последовательность (в самом роме):
03 02 03 02 01 01 00 E4 62 FF 01 01 0F 0F 10 Ты забыл ещё флаговый байт, который стоит перед первым байтом пожатой картинки. И кстати почему в разжатой картинке у тебя 03 02, а не 03 02 03 02? Разжатую ты, похоже, тоже не с начала смотришь.
Цитата:Вот как раз в данном примере в последовательности откуда-то взялся байт FF:
03 02 03 02 01 01 00 E4 62 FF 01 01 0F 0F 10 FF - как раз флаговый байт. В нём бит равный единице означает, что идёт несжатый байт, а 0 - пара байт сжатия. То есть, если стоит FF, значит последующие 8 байт не сжаты. Затем идёт ещё один флаговый байт и т.д.
Цитата:2+2=4
Получается, что копируется 4 байта с адреса h06 от начала пакета. Но Что-то как-то не вяжется, т.к мне нужно скопировать 5 байт.. или я чего-то не понимаю? Значит нужно добавлять не 2, а 3. И это было бы разумнее с точки зрения эффективности алгоритма сжатия. Сам посуди, какой смысл сжимать 2 байта двумя же байтами? Никакого. С точки зрения эффективности лучше всего за 0 принять длину в три байта. На ГБА, кстати, как раз и прибавляется 3. |
|
|
Ace Lightning |
Отправлено: 03 Февраля, 2016 - 06:09:04
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Ace Lightning
Цитата:Ты забыл ещё флаговый байт, который стоит перед первым байтом пожатой картинки.
Перед всей последовательностью стоит 7F=01111111, т.е. теперь понятно, что последний байт сжимается.
Цитата:И кстати почему в разжатой картинке у тебя 03 02, а не 03 02 03 02? Разжатую ты, похоже, тоже не с начала смотришь.
Ой.. тут я просто опечатался) правильнее, конечно, будет 03 02 03 02..
Вообще занятная вещь эти алгоритмы сжатия.. теперь мне в принципе всё понятно. А дальше для удобства нужно написать программу для разжатия? Давно я программ не писал, которые работают с файлами.. думаю Visual Basic подойдёт для этих целей? |
|
|
Ace Lightning |
Отправлено: 03 Февраля, 2016 - 06:11:07
|
VIP
Покинул форум
Сообщений всего: 480
Дата рег-ции: Июнь 2015
|
Ace Lightning
Обнаружил вот такой отрывок кода в памяти приставки:
AA 55 55 AA AA 55 55 AA AA 55 55 AA AA 55 55 AA
В роме же эта последовательность сжата следующим образом:
AA 55 55 AA 94 7E
То есть здесь скопировали не один байт, как в разобранных выше примерах, а 4 байта.
1001 0100 0111 1110
С байтом 94 всё понятно, он действительно указывает на байт AA, а вот глядя на последние 5 бит становится уже не понятно:
11110=30
Прибавив 3, получаем 33.
Т.е. процесс копирования мне нужно повторить 33 раза (вместо положенных 3-х раз) =) Возможно немного неверно предположение, что последние 5 бит - это биты, отвечающие за кол-во циклов копирования..
И, исходя из того, что тут копируется сразу 4 байта, где-то здесь должно быть указание на кол-во копируемых байтов.
На написание распаковщика кол-во копируемых байт никак не повлияет, нужно лишь добавить некоторые условия. А вот написать запаковщик я пока затрудняюсь, т.к. чисто визуально-то видно что можно сжать представленную выше последовательность, но как это определить программно, я сказать затрудняюсь. Ведь в процессе запаковки я делаю проверку в цикле
пока[b] [/i]последующий бит равен предыдущему[/i] [b]начало
считаю кол-во одинаковых байт, увеличивая счётчик на 1.
конец цикла
если кол-во одинаковых байт больше 3 то
сжимаю данные
иначе
записываю их без изменения
конец условия
Можно попробовать реализовать проверку ещё и на наличие одинаковых байт через определённый интервал, но что-то я не понимаю как это реализовать...
p.s. Здесь начинает посещать мысль о том, что легче распаковать и запаковать все нужные данные вручную.. Причём распаковка - это просто копирование байт из памяти эмулятора. |
|
|
TrickZter |
Отправлено: 03 Февраля, 2016 - 06:11:39
|
Покинул форум
Сообщений всего: 560
Дата рег-ции: Июнь 2015
|
TrickZter
Цитата:Обнаружил вот такой отрывок кода в памяти приставки:
AA 55 55 AA AA 55 55 AA AA 55 55 AA AA 55 55 AA
В роме же эта последовательность сжата следующим образом:
AA 55 55 AA 94 7E
То есть здесь скопировали не один байт, как в разобранных выше примерах, а 4 байта.
1001 0100 0111 1110
С байтом 94 всё понятно, он действительно указывает на байт AA, а вот глядя на последние 5 бит становится уже не понятно:
11110=30
Прибавив 3, получаем 33.
В разобранных примерах копировался как раз таки не один байт, а много (больше двух) и никаких циклов тут нет, идёт простое копирование определённого количество байт, начиная с определённого.
Рассмотрим этот пример:
AA 55 55 AA AA 55 55 AA AA 55 55 AA AA 55 55 AA
AA 55 55 AA 94 7E
94 указывает на AA, и начиная с него копируем 33 байта.
Вот смотри как это происходит, подчёркнутый байт - это откуда копируем, жирный байт - это куда копируем.
Копируется первый байт:
AA 55 55 AA AA
Потом второй:
AA 55 55 AA AA 55
Потом третий:
AA 55 55 AA AA 55 55
Потом четвёртый:
AA 55 55 AA AA 55 55 AA
Потом пятый:
AA 55 55 AA AA 55 55 AA AA
Потом шестой:
AA 55 55 AA AA 55 55 AA AA 55
и так всего 33 раза.
И неважно, что начиная с пятого байта у нас началось самокопирование. Кстати благодаря такому самокопированию в рамках LZ отлично реализуется и RLE. Пример:
Допустим у нас ссылка на последний из уже распакованных байтов, а скопировать нужно пять байт, тогда копирование будет выглядеть так:
Копируется первый байт:
11 22 33 44 44
Потом второй:
11 22 33 44 44 44
Потом третий:
11 22 33 44 44 44 44
И наконец четвёртый:
11 22 33 44 44 44 44 44
Разумеется самокопированием LZ не ограничивается. Обычно просто копируется определённый участок байтов из ранее распакованных. Рассмотрим пример. Допустим у нас есть уже такая последовательность байт:
11 22 33 44 55 66 77 88 99 AA BB CC DD
Ссылка идёт на байт 22, а скопировать нужно 5 байт. Тогда процесс копирования будет выглядеть так:
Копируется первый байт:
11 22 33 44 55 66 77 88 99 AA BB CC DD 22
Потом второй:
11 22 33 44 55 66 77 88 99 AA BB CC DD 22 33
Потом третий:
11 22 33 44 55 66 77 88 99 AA BB CC DD 22 33 44
Потом четвёртый:
11 22 33 44 55 66 77 88 99 AA BB CC DD 22 33 44 55
И наконец пятый:
11 22 33 44 55 66 77 88 99 AA BB CC DD 22 33 44 55 66 |
|
|
TrickZter |
Отправлено: 03 Февраля, 2016 - 06:12:41
|
Покинул форум
Сообщений всего: 560
Дата рег-ции: Июнь 2015
|
TrickZter
Ну, хз, по-моему ничего проще делфей нету
Вот так выглядит моя функция запаковки GBAшного LZ77:
CODE:Function BINtoLZ(Src,Res: PArr; Size: Longword; Mode:byte):LongWord;
Var
ResP,SrcP,Back,MaskP,MaskN: Longword;
Max,Cur,MaxB:Word;
Begin
SetLength(Res^,6);
Res^[0]:=$10;
Res^[1]:=Size and $FF;
Res^[2]:=(Size shr 8) and $FF;
Res^[3]:=(Size shr 16) and $FF;
Res^[4]:=0;
Res^[5]:=SRC^[0];
MaskP:=4; //Позиция маски
ResP:=6; //Позиция в результирующем массиве
SrcP:=1; //Позиция в исходном массиве
MaskN:=7; //Позиция в маске
Repeat
If MaskN=0 then begin //Смена маски
MaskP:=ResP;
Inc(ResP);
SetLength(Res^,ResP);
MaskN:=8;
End;
Back:=Mode+1;
Max:=0; //Максимальный размер копируемых данных
MaxB:=0;
While (Back<=$1000) and (Back<=SrcP) and (Max < $F+3) and (SrcP+Max<Size) do Begin //Поиск самого длинного повторяющегося отрезка
Cur:=0; //Текущий размер
While (Src^[SrcP+Cur]=Src^[SrcP-Back+Cur]) and (SrcP+Cur<Size) and (Cur<$F+3) do Inc(Cur);
If (Cur>=3) and (Cur>Max) then begin
Max:=Cur;
MaxB:=Back;
End;
Inc(Back);
End;
If Max=0 then begin //Если подходящий отрезок не найден
SetLength(Res^,ResP+1);
Res^[ResP]:=Src^[SrcP];
Dec(MaskN);
Inc(ResP);
Inc(SrcP);
End
Else begin //Если найден
SetLength(Res^,ResP+2);
Res^[ResP]:=((Max-3) shl 4)+((MaxB-1) shr 8);
Res^[ResP+1]:=(MaxB-1) and $FF;
Inc(ResP,2);
Inc(SrcP,Max);
Dec(MaskN);
Inc(Res^[MaskP],1 shl MaskN);
end;
Until SrcP>=Size;
Result:=ResP;
End;
Src - это исходный (не пожатый) массив байтов, Res - массив, в который вносятся сжимаемые данные. А сама функция возвращает размер пожатых данных. |
|
|
TrickZter |
Отправлено: 03 Февраля, 2016 - 06:13:32
|
Покинул форум
Сообщений всего: 560
Дата рег-ции: Июнь 2015
|
TrickZter
Цитата:мм.. класс, что ещё сказать))
Мне можно, в принципе, перебраться и на Делфи (т.к. в университете писали на Turbo Pascal, а его синтасис чем-то похож). Только он хорошо работает в Windows 7? и какую лучше версию ставить? ))
Разумеется похож, Делфи - это прямой потомок паскаля Самой популярной версией делфи до сих пор является Borland Delphi 7. Сам я сижу под Windows 7 x64, проблем с делфями нет.
Цитата:И кстати: вот название алгоритма LZ это понятно, а что значат цифры 77?
LZ разный бывает, а LZ77 - одна из его разновидностей. Почитать подробнее можно в википедии:
http://ru.wikipedia.org/wiki/LZ77
Но даже тот же самый LZ77 в разных играх и на разных платформах может реализовываться по-разному. Например, у тебя тоже LZ77, только организован он немного иначе: другой порядок бит во флаговом байте, другие биты используется для смещения и длины, смещение считается иначе. |
|
|
|
Поиск в теме | Версия для печати |
Страниц (3): [1] 2 3 » |
Сейчас эту тему просматривают: 5 (гостей: 5, зарегистрированных: 0) |
« Экстрим хакинг » |
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
|
|
|