[SMD] Megadrive MEGAPACK source code

[DrMefistO]

Приветствую,

История началась с того, что я взялся реверсить Fantastic Dizzy, и понял, что кроме Imploder (который IMP!) в игре имеется и другой компрессор, с достаточно сложной для понимания логикой. Сразу поняв, что все мои попытки его разреверсить и написать компрессор тщетны, я написал одному из товарищей, которые работали в Codemasters в то время, в частности над Fantastic Dizzy. Спустя продолжительное время дядя вышел на связь, рассказал, что пакер там крутой, потом поделился исходником распаковщика, который (один из немногих) у него имелся. Из исходника стало понятно, что пакер имеет название MEGAPACK.

Имея исходник с комментариями, конечно, проще, но, мне не удалось найти ни время, ни силы его переписать. Поэтому я обратился к Марату. Товарищ, несомненно, голова! Прошёл вроде как месяц, может и больше, как Марат сообщил о том, что анпакер готов. И жмёт он явно круче остальных! Это не могло не радовать. А спустя ещё недельку был готов и пакер. На Delphi.

Конечно, для использования в других проектах, для встраивания в свой софт делфи не очень годится:), поэтому я взялся переписать его исходники на C. Что спустя два дня удалось.

Ещё позже Марат нашёл багу в исходнике, которая проявлялась только на больших файлах, и успешно поправил её, ну а я - поправил у себя.

---
В итоге, Марат и я рады представить вашему вниманию возможно самый мощный компрессор для сеговских тайловых данных - MEGAPACK. В описании репозитория проекта имеется сравнительная таблица, которой можно верить! Единственный минус - распаковывает дольше большинства из списка (например, медленнее APLib (из SGDK) в два раза). Поэтому решайте сами.
---

Ссылки:
- Исходники: https://github.com/lab313ru/megapack-megadrive
- Релизы: https://github.com/lab313ru/megapack-megadrive/releases

[Марат]

Стоит также добавить, что компрессор расчитан на сжатие графики 4bpp linear, т.е. сеговской графики. Вполне вероятно, что он также хорошо будет сжимать графику из gba игр. Также количество сжимаемых тайлов не должно превышать 1024 штук или 32 кб, а размер файла должен быть кратен 32. Сжатие данных, которые не являются графикой, впоследствии, возможно, невозможно будет восстановить.

[Yoti]

Кодировку pas поправьте, пожалуйста. В таком виде комментарии нечитаемы.

[DrMefistO]

Поправлено.

[perfect_genius]

Можете кратко описать за счёт чего сжимает сильнее?
Банально - больше анализирует данные?

[Марат]

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

[perfect_genius]

Спасибо, значит снова сжатие без поворотов/отзеркаливания тайлов
Ещё мне не даёт покоя, что первые цвета на Сеге всегда прозрачные, отчего тоже теряются драгоценные байты. Особенно много палитр в UMK3, в их первых байтах тоже можно что-то хранить же, по идее, раз приставка их игнорирует.
+идея оптимизации из-за наложения двух слоёв друг на друга. Например, на одном слое идут чёрный пиксель, потом белый или прозрачный, потом снова чёрный. Второй слой, накладываемый сверху - прозрачный, красный, прозрачный. Т.е. при наложении будет чёрный-красный-чёрный.
Так вот, если нижний будет из трёх чёрных подряд, то ведь и сожмётся эта полоска лучше с RLE, не так ли? А при наложении слоёв не будет визуальной разницы. В итоге оптимизация и места и производительности распаковки. Правильно?



В Dizzy тоже слои накладываются?

[Марат]

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

Так то оно так, но тайлы хранят не цвет пикселей, а индексы цвета в палитре.
У прозрачного цвета индекс всегда 0, а у твоего чёрного индекс от 1 до 15. В итоге у тебя будет что-то типа 1 0 1.

[perfect_genius]

Не понял - индексы суммируются с нижним что ли? Индекс пикселя верхнего слоя как-то меняется от того, что накладывается на непрозрачный индекс пикселя нижнего слоя?
Если в Пейнте накладываю слои друг на друга, то получается нормальная иконка с нормальными цветами:



И вот тут представь, что его сквозной лоб на нижнем слое (справа) - закрашен:



Цвет из левого слоя, накладываясь на лоб сверху, изменится?



А насчёт нулевого индекса палитры появилась таки идея - две палитры идут друг за другом, у каждого нулевой индекс пустой и бесполезен. Но можно ведь сдвинуть их на байт друг к другу, чтобы 15ый индекс был на месте нулевого у другого? Указатели тоже будут одновременно указывать на нулевой индекс одного и 15ый другого

v                                                          v
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
станет
v                                                      v
N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

В итоге, если палитр штук 20, то вот получим целых двадцать байт экономии, так?

[Марат]

Значит я тебя не так понял.
Разделение на слои идёт таким образом. Имеем изображение с количеством цветом до 31-го.
Разделение на слои идёт таким образом. Пиксели с индексами 0-15 попадают в первый слой, а пиксели с индексами 16-31 во второй.
Таким образом, если средний пиксель попал в другой слой, то значит, в этом палитре для текущего слоя нет цвета, который ему соответствует.

В итоге, если палитр штук 20, то вот получим целых двадцать байт места, так?

Ну, такая себе экономия.

[perfect_genius]

Не совсем понял что за средний пиксель (пиксель спрайта между Планами А и Б?), но обе идеи возможны, получается При этом даже не надо что-то менять, достаточно оптимизировать картинки и указатели.

Ну, такая себе экономия.

Конкретно в UMK3 на каждого бойца не менее пяти палитр - на иконку, на полный рост два варианта, и два варианта на VS-экран. При этом у Нуб-Сейбота лишь один цвет, так что его палитру можно удалить, если вообще есть. Также, некоторые палитры тупо повторяются у тех, кто не перекрашивается.
+палитры уровней, экранов истории...
Я бы не сказал, что экономится мало. Причём, на пустом месте, лишь изменением указателей и вырезанием лишнего.

Ещё подумал - а почему нельзя пойти с палитрами дальше? Не на один пиксель наслаиваются, а больше? Например, половина палитры одного равна половине палитры второго. В итоге они входят друг в друга наполовину. Что-то мешает такому?

Но это уже оффтоп, хотел узнать про Dizzy же - там нет наслоения Планов А и Б?
И этот упаковщик только в этой игре встречается?

[Марат]

чёрный-красный-чёрный.

Вот твой средний пиксель, который из другого слоя. Ты сам же описал этот случай и сам же не поймешь)

[Ti_]

1) некоторые файлы не может сжать.
2) си версия не может сжать ещё и другие файлы.
3) си версия не может расжать правильно ни 1 файл.
4) си версия "32 бит" не является настоящими 32 бит, а видимо win7+.

файлы прилагаю:

[Марат]

Спасибо за багрепорт, Ti_.
В случае с файлом dragon1.smd, выявлена ошибка в типе переменной цикла, которая проявляется когда строка Value длиннее 255 байт.
Лечиться изменением типа Byte на Integer.

Код: [Выделить]

procedure TCODEC.CompressedStreamWriteBits(Value: string);
var
  I: Byte;
begin
  for I := 1 to Length(Value) do
  begin
    if Value[I] = '0' then
      CompressedStreamWriteBit(False)
    else
      CompressedStreamWriteBit(True);
  end;
end;
В случае с файлом leopard.smd - здесь уже проявляется ограничение на количество наборов пикселей для архива: оно равно 512. У файла leopard.smd генерируется 577 наборов. Это ограничение можно увеличить, но тогда пакер не будет соответствовать коду оригинала.

[DrMefistO]

1) некоторые файлы не может сжать.
2) си версия не может сжать ещё и другие файлы.
3) си версия не может расжать правильно ни 1 файл.
4) си версия "32 бит" не является настоящими 32 бит, а видимо win7+.

файлы прилагаю:

Спасибо. Поправил. Попробуй новый релиз: https://github.com/lab313ru/megapack-megadrive/releases/tag/v1.4
Версии для XP не будет, т.к. для этого нужно держать отдельную Visual Studio. Ошибка с leopard.smd не будет исправлена, т.к. код, как уже сказал Марат, не будет соответствовать оригиналу.

Ti_, сообщай, если что не так, желательно без размытых утверждений "ничего не работает", "всё не работает"

[Ti_]

Ti_, сообщай, если что не так, желательно без размытых утверждений "ничего не работает", "всё не работает"

1) Запаковка заработала.  Распаковка так и не пашет.
2) "Ошибка не будет исправлена". И не надо. Тогда почему пакер не пишет ошибку что такой файл сжать нельзя? Почему он не проверяет после сжатия-расжатия что файлы одинаковые?
3) Не знаю про что ты. Я через тини С собрал он 1 мб весит. Только удалил одну фигню на которую ругалось.

[DrMefistO]

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

[Ti_]

С этим файлом ещё проблема в си версии: