В Castlevania: Legends никак не могу найти титульный экран в тайловом редакторе... это признак того, что графика сжата?

TrickZter

Либо сжата, либо не в том формате ищешь.
Если есть проблемы с нахождением картинки, можно поискать Поганкой или аналогичным корруптером.

alex_231
Самый простой способ - посмотреть содержимое видеопамяти во время заставки и найти такую же последовательность байт в РОМЕ.

TrickZter


Если графика пожата, то там совсем другая последовательность

alex_231
Смотря чем она пожата, если LZ, то первые уникальные идущие подряд 3-4 байта будут совпадать - проверено.
А какая платформа-то, GB?

alex_231
Нашел - графика пожата, данные начинаются с 0x28C47, начало пакета - ориентировочно 0x28C46, но некогда разбираться, алгоритм - разновидность LZ, не очень сложный.

TrickZter
LZ тоже бывает разный. Если LZ78, то может и не быть, а с LZ77, конечно, будут совпадать - это особенность алгоритма.

Ace Lightning
Вы не могли бы пояснить немного как вы смогли определить метод сжатия?
И ещё, как я понимаю, чтобы разжать графику нужно написать распаковщик? Но как именно узнать алгоритм сжатия? Из дебаггера? Тогда ещё один вопрос: как в самом отладчике поймать эту самую процедуру разжатия графики?

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-го байта с конца.

Ace Lightning
Неясным для меня остаётся то, как alex_231 нашёл точное расположение титульного экрана в роме?

alex_231
Что-то тут странное сжатие - пакеты без заголовков идут, судя по всему.

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

Я же сказал: посмотреть в памяти эмулятора как выглядит графика заставки в незапакованном виде и попробовать найти часть последовательности в роме.
Я искал так:
1. запустил игру,
2. дождался заставки,
3. открыл окно Tile Viewer, чтобы узнать в каком месте памяти лежит искомая графика (0x8800),
4. открыл окно Memory viewer, перешел по найденному адресу
5. открыл ром в Translhextion,
6. задал HEX-поиск: 0F103020 (идущие подряд четыре уникальных неповторяющихся байта недалеко от адреса 0x8800 из видеопамяти)
7. нашел искомую комбинацию по адресу 0x28C53,
а дальше - откатился по рому назад, до начала пакета, сопоставляя ром и содержимое видеопамяти.
Кстати графика заставки побита на две части. вторую сможешь сам найти по описанной методике?

Ace Lightning
Да, сумел найти. Вторая часть располагается с адреса 0x2869D. Чтож, теперь осталось разобраться с алгоритмом сжатия.. а то я не сильно въезжаю пока в то, что вы написали про него выше :wacko:

TrickZter


В мой пост можешь особо не вникать, там про другой алгоритм сказано. А если когда и надо будет его распаковать (LZ в GBA и NDS играх) - обращайся ко мне, дам тулзу, которая сама находит все пожатые данные. Я её пока не публикую, так как ещё не все задуманные фишки доделал :rolleyes:

Ace Lightning
Обязательно обращусь

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 02, а не 03 02 03 02? Разжатую ты, похоже, тоже не с начала смотришь.

FF - как раз флаговый байт. В нём бит равный единице означает, что идёт несжатый байт, а 0 - пара байт сжатия. То есть, если стоит FF, значит последующие 8 байт не сжаты. Затем идёт ещё один флаговый байт и т.д.

Значит нужно добавлять не 2, а 3. И это было бы разумнее с точки зрения эффективности алгоритма сжатия. Сам посуди, какой смысл сжимать 2 байта двумя же байтами? Никакого. С точки зрения эффективности лучше всего за 0 принять длину в три байта. На ГБА, кстати, как раз и прибавляется 3.

Ace Lightning


Перед всей последовательностью стоит 7F=01111111, т.е. теперь понятно, что последний байт сжимается.


Ой.. тут я просто опечатался) правильнее, конечно, будет 03 02 03 02..
Вообще занятная вещь эти алгоритмы сжатия.. теперь мне в принципе всё понятно. А дальше для удобства нужно написать программу для разжатия? Давно я программ не писал, которые работают с файлами.. думаю Visual Basic подойдёт для этих целей?

TrickZter

Да, для разжатия и для сжатия.

Подойдёт любой язык программирования

alex_231


Правильно, это мой пронос, там нужно 3 прибавлять.

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

В разобранных примерах копировался как раз таки не один байт, а много (больше двух) и никаких циклов тут нет, идёт простое копирование определённого количество байт, начиная с определённого.

Рассмотрим этот пример:
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


Нужно проводить поиск максимально длинного идентичного отрезка, если таковой не найден или найден, но длина его меньше 3-х, то записать 1 байт в незапакованном виде. И дальше проводить поиск для другого байта. Ты не на делфях, случаем, программиш? Могу дать код похожей функции.

Ace Lightning
Понятно, эх.. вот сессию сдам и доделаю программу.
Программирую я на Visual Basic, т.к. не знаю где лучше писать программы и выбрал там, где попроще))

TrickZter
Ну, хз, по-моему ничего проще делфей нету

Вот так выглядит моя функция запаковки GBAшного LZ77:

Src - это исходный (не пожатый) массив байтов, Res - массив, в который вносятся сжимаемые данные. А сама функция возвращает размер пожатых данных.

Ace Lightning
мм.. класс, что ещё сказать))
Мне можно, в принципе, перебраться и на Делфи (т.к. в университете писали на Turbo Pascal, а его синтасис чем-то похож). Только он хорошо работает в Windows 7? и какую лучше версию ставить? ))
И кстати: вот название алгоритма LZ это понятно, а что значат цифры 77?

TrickZter

Разумеется похож, Делфи - это прямой потомок паскаля Самой популярной версией делфи до сих пор является Borland Delphi 7. Сам я сижу под Windows 7 x64, проблем с делфями нет.

LZ разный бывает, а LZ77 - одна из его разновидностей. Почитать подробнее можно в википедии:
http://ru.wikipedia.org/wiki/LZ77
Но даже тот же самый LZ77 в разных играх и на разных платформах может реализовываться по-разному. Например, у тебя тоже LZ77, только организован он немного иначе: другой порядок бит во флаговом байте, другие биты используется для смещения и длины, смещение считается иначе.

Ace Lightning


Хм, может и в самом деле пересесть на Делфи. В университете постоянно приходится работать с паскалем, да ещё первокурсникам каждый год задачи решаю. Подумаю... во всяком случае это будет не раньше, чем у меня закончатся экзамены

TrickZter

Джин подсказывает, что правильно этот алгоритм называется LZSS, хотя в документации по тем же GBA и NDS этот алгоритм ошибочно обзывают LZ77 (это другой тип LZ).
Добавлено:

Ace Lightning

Вот ещё что хотел спросить: для распаковщика входными данными является путь к рому, начало блока графика и конец блока графики. Правильно ли это? или можно как-то программно определять алгоритм сжатия и не задавать начального и конечного значений блоков графики?