форум группы Chief-Net форум группы Chief-Net
Перевод приставочных игр и не только!
drako site Перейти на сайт группы     Наш чат      Помощь      Поиск      Пользователи


 Страниц (1): [1]   

> Описание: Утилита для работы со сжатой графикой
Марат Супермодератор
Отправлено: 27 Июля, 2021 - 21:46:22
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Пару месяцев назад товарищ Dr. MefistO подкинул мне исходный код декомпрессора из игры Fantastic Dizzy на smd и попросил разобрать сжатие и написать код компрессора/декомпрессора. По сообщениям некоего Derek Leigh-Gilchrist это компрессор превосходил сжатие LZSS на 30%. А так как я люблю разбирать различные кодеры, то сразу согласился.
Надо сказать, что алгоритм достаточно сложный. Раньше подобных алгоритмов мне не попадалось. Комментарии к исходникам особо не помогали. Так что пришлось по старинке дебажить и пытаться понять, что есть что. Это был самый долгий реверс декомпрессора.
Так долго я не разбирал ни один метод сжатия. Но в результате мы имеем самый лучший компрессор. Dr.MefistO провел сравнения с другими компрессорами:
Спойлер (Отобразить)


Также здесь https://github.com/lab313ru/megapack-megadrive он выложил сишную версию компрессора/декомпрессора в консольном варианте.
Также он провёл поиск по GoodGens и нашёл игры, в которых используется этот метод сжатия. Кроме вышесказанного Fantastic Dizzy сжатие используется также в играх
- Psycho Pinball
- Yogi Bear's Cartoon Capers



Скачать файл: MEGAPACK_GUI_with_source.zip
Скачан раз: 13
 
 Top
Марат Супермодератор
Отправлено: 27 Июля, 2021 - 21:55:36
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Хочу также сюда выложить версию, которую я адаптировал под nes графику.
По степени сжатия компрессор превзошёл даже кодемастеросовский с марковским алгоритмом предсказания.
Скачать файл: MEGAPACK_NES.zip
Скачан раз: 14
 
 Top
Griever Пользователь
Отправлено: 30 Июля, 2021 - 20:30:55
Post Id


VIP


Покинул форум
Сообщений всего: 433
Дата рег-ции: Июнь 2015  





Интересно!
Марат пишет:
Хочу также сюда выложить версию, которую я адаптировал под nes графику.

А драйвер для распаковки на железе есть?
Есть ли словесное описание алгоритма в каком-нибудь виде?
 
 Top
Марат Супермодератор
Отправлено: 30 Июля, 2021 - 20:45:13
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Griever пишет:
Есть ли словесное описание алгоритма в каком-нибудь виде?

Пока есть только исходник с комментариями.
Вроде, Dr.MefistO хотел писать статью на это сжатие.
Если интересно могу описать алгоритм декомпрессии по шагам.

Griever пишет:
А драйвер для распаковки на железе есть?

Нет, драйвера нет.
Но при желании всегда можно написать или адаптировать алгоритм megadrive версии.
 
 Top
Griever Пользователь
Отправлено: 31 Июля, 2021 - 13:32:57
Post Id


VIP


Покинул форум
Сообщений всего: 433
Дата рег-ции: Июнь 2015  





Марат пишет:
Если интересно могу описать алгоритм декомпрессии по шагам.

Да, черкни, если не сложно. Идея, конечно, была адаптировать это под 6502, т.к. на nesdev тоже полно таких же помешанных на сжатии, как и мы и, насколько я понимаю , цепи маркова пока лидер по степени сжатия графики.
 
 Top
Марат Супермодератор
Отправлено: 01 Августа, 2021 - 18:13:27
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Как-то так. Выглядит не очень струтурировано. Если что-то непонятно, пиши.

Цитата:
Не секрет, что в одном отдельном тайле используются не все цвета из палитры.
И, наверно, редко можно встретить тайл, в котором используюся все цвета из палитры.
Это, значит, что мы можем для каждого тайла создать свой алфавит символов, который будет содержать от 1 до 16 символов (цветов).
Для того чтобы хранить информацию об алфавите будем использовать такой тип, как множество, размером в два байта,
где каждый бит множества будет говорить нам о том есть ли во множестве тот или иной цвет пикселя.
Например число 0х8080 в бинарном виде 10000000 10000000, говорит нам о том, что во множестве имеются цвета с индексами 7 и 15,
что в свою очередь означает, что в тайле присутствуют цвета с индексмаи 7 и 15, т.е. всего два цвета. А для того, чтобы
их закодировать достаточно 1 бита, '0' - для цвета 7 и '1' для цвета 15.
Это то, что касается пикселей. Мы также можем повторять идентичные тайлы, можем повторять тайлы, которые отличаются частично,
заменяя те пиксели, которые непохожи, декодируя их из сжатого потока.
Также мы можем повторять строки внутри тайла, если они полностью или частично похожи, также заменяя непохожие пиксели декодированными из потока.
Для повторения строк используются такой параметр как hmap размерностью в 1 байт, где каждый бит соответствует 1 строке.
Если бит = 1, то повторить строку, если = 0, то пиксели строк надо декодировать из потока.

Для повторения пикселей в строке используется параметр vmap размерностью в 1 байт.
При чём параметр vmap общий для всех строк. Если бит = 0, то надо считать 1 бит (персональный бит) из потока и тестировать этот бит, если он равен 0, то
надо декодировать пиксель из потока. Если бит равен 1, то повторяем последний(левый) пиксель.

Почти все значения сжаты методом усечённой бинарной кодировки.
Усечённая кодировка имеет конечный алфавит. Т.е. для кодирования/декодирования
мы должны заранее знать о количестве символов в алфавите. В зависимости от количества
символов меняется длина кода символа.

В алгоритме используются различные методы оптимизации и хитрости.
Например, зная значения последнего пикселя(левого) мы можем удалить его из множества тем самым мы уменьшим кол-во символов
во множестве, а значит сократим длину кодов для оставшихся символов, зная значения двух символов, левого и верхнего, можем удалить из множества
уже два символа и ещё более сократим длины кодов для оставшихся символов во множестве. При определённых условиях, когда во множестве всего 1 символ
длина кода символа составляет 0 бит.
На рисунке ниже представлен пример тайла. Множество для такого тайла [0, 1, 2, 3, 4, 5]. Всего 6 элементов. Очевидно,
для такого множества максимальная длина кода символа будет равна 3, а минимальная 2.
Коды этих символов:
0 - 00
1 - 01
2 - 100
3 - 101
4 - 110
5 - 111
Предположим, что мы сейчас должны декодировать второй пиксель второй строки.
Нам известен верхний пиксель 01 и левый пиксель 03. И мы точно знаем, что искомый пиксель неравен
этим двум пикселям. Тогда мы исключаем эти два пикселя из множества и оно приобретает такой вид [0, 2, 4, 5].
Соответственно, длина кодов этих символов тоже меняется:
0 - 00
2 - 01
4 - 10
5 - 11
таким образом максимальная длина кодов для символов уменьшилась на 1 бит.

В алгоритме используется два способа сжатия:
Первый основан на принципе повторения строк пикселей. 1 строка - 8 пикселей по горизонтали.
Всего 8 строк по 8 пикселей итого 64 пикселя.

Второй - основан на повторении тайлов с частичной заменой пикселей.



Алгоритм декомпрессии по шагам.

1. Сначала идёт 10 бит - кол-во тайлов в архиве.
2. Далее мы должны декодировать количество множеств пикселей, которое закодировано
методом усечённой бинарной кодировки. Количество множеств не может быть больше количества тайлов, но не должно превышать 512.
3. После того как декодировали количество множеств, надо декодировать сами множества.
Каждое множество либо кодируется 16 битами, либо как дельта между предыдущим множеством и декодируемым.
4. Дальше начинается цикл декодирования тайлов.
В цикле сперва декодируется индекс множества в списке множеств, который принадлежит декодируемому тайлу.
Далее читается бит, из которого ясно каким из методов закодирован тайл (методом повторения тайлов или методом повторения строк).
Первый тайл всегда закодирован методом повторения строк.
Дальше, я думаю, всё ясно из кода исходника.

 
 Top
Марат Супермодератор
Отправлено: 05 Августа, 2021 - 17:48:36
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Я оказывается не выложил исходник nes версии.
Прикладываю.
Скачать файл: Megapacker_UTF8.rar
Скачан раз: 12
 
 Top
Griever Пользователь
Отправлено: 05 Августа, 2021 - 19:45:48
Post Id


VIP


Покинул форум
Сообщений всего: 433
Дата рег-ции: Июнь 2015  





Блин, ну сложно! Пару вечеров уже прикидываю что к чему Улыбка
Представляю, насколько тяжело написать оптимальный пакер под такое.
 
 Top
Марат Супермодератор
Отправлено: 05 Августа, 2021 - 21:27:49
Post Id



Chief-Net


Покинул форум
Сообщений всего: 1755
Дата рег-ции: Окт. 2014  
Откуда: Казахстан





Griever пишет:
Блин, ну сложно! Пару вечеров уже прикидываю что к чему

Когда поймёшь суть, покажется что достаточно просто Улыбка

Griever пишет:
Представляю, насколько тяжело написать оптимальный пакер под такое.

Там настолько оптимизировано, что я и не знаю что ещё можно оптить.
Автор там реально заморочился.
 
 Top
Страниц (1): [1]
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Экстрим хакинг »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



> Похожие темы: Jon Menzies' Megapacker
Темы Форум Информация о теме Обновление
Плагины для Map Editor of Dreams
...
Программирование Ответов: 3
Автор темы: Марат
16 Ноября, 2020 - 01:46:07
Автор: ZetpeR
MTE DTE Finder
Инструмент для поиска mte и dte "слов"
Программирование Ответов: 1
Автор темы: Марат
02 Октября, 2021 - 09:18:29
Автор: Mefistotel
Beam Software CODEC
Экстрим хакинг Ответов: 5
Автор темы: Марат
28 Февраля, 2016 - 03:16:35
Автор: Mefistotel
Comix Zone LZSS Coder
АРХИВНАЯ ТЕМА 2013 года
Экстрим хакинг Ответов: 13
Автор темы: Марат
22 Февраля, 2016 - 12:30:55
Автор: Mefistotel
Djinn Tile Mapper v2.0
Новая переработанная версия известного редактора
Программирование Ответов: 87
Автор темы: Марат
03 Апреля, 2021 - 17:44:43
Автор: R-K
 

Powered by ExBB
ExBB FM 1.0 RC1 by TvoyWeb.ru
InvisionExBB Style converted by Markus®