Алгоритмы сжатия информации

[sergi]

Не, к сожалению нет у меня такого времени - долго слишком
ладно попробую сначала свой, там посмотрим сколько чего
Ну мне нужно не какуюто вешь распаковать и потом ей пользоваться
а распаковать, воспользоваться и еще распаковать и опять и так много-много раз

[sergi]

Короче итоги сжатия

применил я алгоритм и такие результаты

мне нужно было 1 метр ужать до 500 килобайт

я ужал его до 512 килобайт

к сожалению больше нельзя

использовалось 3 разновидности сжатия:
1 - избавление от повторящихся нулей
2 - краткое обозначение повторяющихся цепочек(в моем случае до 8046) и обозначением их FFFF если их больше чем 1 идет подряд
3 - обозначение двухбайтовых спарок(16 бит) уменьшенным числом бит если их количество на 8 килобайт не превышает 2048 иначе нету смысла жать и тогда без уже сжатия бит только без нулей идет - ну там от 1 до 11 бит получалось - варьировалось

в общем скорость распаковки приличная - точно не знаю но не более 2-4 обновлений кадров уходит на распаковку одной порции по 8 килобайт

т.е. результат впосле вменяемый

zip зажал мне этот же метр в 466 килобайт

rar на максималке до 460 килобайт

мои же 512 не так уж плохо смотрятся для M68K

ну конечно же не все что угодно можно паковать, а повторяющиеся данные

в общем запаковывайте если есть возможность

[SPOT]

sergi,
А ты на сегу игру пишешь? Если да то можно посмотреть результат или ещё что-то.

[sergi]

Не на сегу - на нео-гео

результат - да посмотрите, позже только

нео-гео и ягуар тоже M68K машинки, но только помощнее будут чем сега

у сеге цветов нет и скорости тоже + графические возможности ограниченные - мало спрайтов и нет масштабирования и вращения
у нео-гео тоже нет вращения, но масштабирование спрайтов есть аппаратное

ну и размер рома

вообще нео-гео это гибрид сеги и денди - оказывается была машинка которая взяла лучшее из приставки сега и приставки денди и названа - нео-гео

там и скорость и M68K и мапперы и разделение графики от программа - т.е. отдельно данные графики и отдельно программа - можно в принципе думаю поставить оперативу вместо рома графики и из программы расжимать если нужно графику, но пока не нужно

возможно можно будет сделать пересчет картинки чтобы поворачивало изображение и в тайлы изображение перекладывало, но там вроде синус и косинус нужно считать и довольно быстро - посмотрим короче

[SnowWorm]

возможно можно будет сделать пересчет картинки чтобы поворачивало изображение и в тайлы изображение перекладывало, но там вроде синус и косинус нужно считать и довольно быстро - посмотрим короче

x2 = cos(f) * (x1-x0) - sin(f) * (y1 - y0) + x0
y2 = sin(f) * (x1-x0) + cos(f) * (y1 - y0) + y0

f - угол поворота
(x0,y0) - координаты точки вокруг которой надо поворачивать. Это должны быть координаты центрального пикселя в исходном спрайте
(x1,y1) - координаты пикселя спрайта. Сюда надо по очереди подставлять комбинации x и y возможные на исходном спрайте.
(x2,y2) - такие координаты будут у точки после поворота

при подсчёте будет несколько сложностей -
1) надо как-то считать все эти синусы-косинусы. Один из вариантов решения - заранее сосчитать значения синусов и косинусов от 0 до 360 градусов, сделать таблицу и запихнуть эти константные значения в ром

2) при повороте на произвольный угол неизвестно, какой ширины и высоты получится итоговый спрайт. Нужно вспомнить математику, и заранее расчитать. и после получения координаты (x2,y2) - сместить их ещё куда-то. Хотя как вариант - можно обрезать всё что выходит за пределы координат оригинльного спрайта

3) координаты (x2,y2) - получаются не целыми числами. В принципе можно округлять.


http://homepages.inf.ed.ac.uk/rbf/HIPR2/rotate.htm

[sergi]

Это полезная информация - спасибо

ну я тоже склонялся к табличным значениям - помню в школе нас даже учили по таблице Брадиса

а мы все в калькуляторы тыкали

ну вот зачения уже можно готовые взять, чтобы ничего не считать

думаю что изменение на 1 градус нормально уже будет т.е. 360 изменений
хотя можно и по 5 брать - сомневаюсь что особо на глаз будет заметно при разрешении 320х240

ну поэтому заранее будет известен угол поворота

а округлять - ну понятное дело что округлять ну и искажения будут - собственно с другой стороны а как иначе - всегда при поворотах графика искажается
чтобы без искажений было нужно высчитывать будет значения цветов точек и прочее - а это слишком сложно

Без искажений будет только на 90 градусов если поворачивать

кстати спрайты могут зеркалиться поэтому возможно понадобится только осуществлять поворот в пределах 90 градосов

по размеру нужно так подгонять чтобы заранее знать во что будет повернутое изображение вписано

[Марат]

Sergi, ну так на сколько килобайт лучше он у тебя сжал тот массив, что GManiac сжимал архиватором RNC?

[sergi]

Можно посчитать во сколько он бы сжал в принципе

ну именно те 8 килобайт которые я для примера дал - там 8064 байта
он ужал до 4521 байт

просто чем меньше разновидностей этих спарок по 2 байта тем соответственно плотнее сжимает т.к. разрядность их обозначения ниже и собственно само их количество меньше

если всего 2 спарки то жмет 8064 байта до 74 байт
а если 2048 то до 7,5 килобайт

ну а зип я говорю немногим лучше справляется ну на 50 килобайт может плотнее

но там и машина мощнее и алгоритм скорее всего обозначает более часто повторяющиеся спарки меньшим числом бит а редко встречающиеся большим - получается компактнее, но для машины затратнее и для программера тоже - реализовать как я в асме это геморно будет

[Марат]

Это я к чему спрашиваю. Я писал пакер для GenghisKhan 2, так вот он этот массив сжимает до 4494 байт. Это lzss алгоритм с переменным кол-вом бит для словаря и длины совпадения. Максимальный размер словаря ограничен 4096 байтами, а длина совпадения 256 байтами. Правда, я еще не проверил правильно ли он сжал этот массив, но с меньшими размерами все сжималось идеально.

[sergi]

Ну там еще вопрос как быстро это все дело разожмется и размер самого распаковщика тоже имеет место

а так ну гдето там же валяется - даже 100 байт меня особо не спасут к сожалению

если бы он жал до 4 килобайт ровно, тогда можно бы было поинтересоваться как это сделано

я же и зипами и рарами жал - результат был близок, поэтому там особо не выжмешь ничего

Да еще такой показатель для меня важен был как число задействованых для распаковки регистров

мне понадобилось D0-D3 и A0-A3, A5 для распаковки

[Марат]

если всего 2 спарки то жмет 8064 байта до 74 байт
а если 2048 то до 7,5 килобайт

Ну, как-то совсем хреново. По-моему Хафман бы лучше сжал бы. Можешь весь файл мегабайтный приатачить? Только сожми его предварительно, а то не охота лишние 500 кб качать.

[sergi]

Да сжать то может и можно получше, проблема разжать побыстрее с малыми затратами а это важнее - мне скорость главное

http://www.raregame.ru/file/File.zip

[GManiac]

RNC сжал этот кусок до 424117 байт. Как быстро будет разжиматься, я уже описывал.
Так я и не понял, у тебя сжаты куски по 8 кб или как? Почему ты вдруг начал писать про сжатие всего мегабайта и про 1-2 кадра на разжатие, ты же говорил, что свободно всего пара тыщ тактов. Опиши подробнее.

[Марат]

У мемя весь кусок сжимается до 506 кб. А, если сжимать по 8 кб, то, думаю, где-то 700 кб будет. Хафман и того хуже сжимает на 650 кб. Что касается rar и zip, у них, по-моему, словарь не мемьше 64 кб. По крайней мере, так в опциях написано. С таким словарем мой пакер для blades of vengeance сжимает этот мегабайтный кусок до 408 кб.

[sergi]

Ну да, я не говорю что нельзя, мне просто именно по 8 килобайт нужно и вопрос не только с сжатии но и с временем расжатия и размером кода ну и сколько регистров используется
я использовал и сделал свой метод именно для своих целей

то что он жмет ну не в 4 килобайта да это конечно плохо для меня, но боюсь что более лучшие результаты встанут мне неоправдано дорого

можно было еще конечно как уже говорил использовать по весам так сказать - более частые обозначать меньшим количеством бит а более редкие большим, но там сложность в том что алгоритм будет гораздо сложнее

а вообще что за необходимость жать разные сеговские игры  - как понять пакер для blades of vengeance?
а так что она не пожата или ты собственно один из разработчиков этой игры?

[Марат]

а вообще что за необходимость жать разные сеговские игры  - как понять пакер для blades of vengeance?

Ну, тут все просто: если мне нужно перевести на русский какую-нибудь игру, а данные в ней пожаты, то я естественно изучаю алгоритм распаковки, а потом пишу пакер. Обычное дело.

Добавлено позже:

а вообще что за необходимость жать разные сеговские игры  - как понять пакер для blades of vengeance?

Ну, тут все просто: если мне нужно перевести на русский какую-нибудь игру, а данные в ней пожаты, то я естественно изучаю алгоритм распаковки, а потом пишу пакер. Обычное дело.

Ну да, я не говорю что нельзя, мне просто именно по 8 килобайт нужно и вопрос не только с сжатии но и с временем расжатия и размером кода ну и сколько регистров используется
я использовал и сделал свой метод именно для своих целей

то что он жмет ну не в 4 килобайта да это конечно плохо для меня, но боюсь что более лучшие результаты встанут мне неоправдано дорого

можно было еще конечно как уже говорил использовать по весам так сказать - более частые обозначать меньшим количеством бит а более редкие большим, но там сложность в том что алгоритм будет гораздо сложнее

а вообще что за необходимость жать разные сеговские игры  - как понять пакер для blades of vengeance?
а так что она не пожата или ты собственно один из разработчиков этой игры?

Ну да, я не говорю что нельзя, мне просто именно по 8 килобайт нужно и вопрос не только с сжатии но и с временем расжатия и размером кода ну и сколько регистров используется
я использовал и сделал свой метод именно для своих целей

А с регистрами-то какие проблемы? Нужные регисты ведь можно всегда сохранить в стек.

[sergi]

Ну напиши тогда разные алгоритмы запаковки-распаковки данных которые в играх используются - думаю полезная информация - может чего и я использую потом

просто в моем случае там особо разницы нет 50 или даже 100 килобайт будет ли еще лишних

регистры блин и так в стеке все сидят да у меня еще часть регистров которые я использую участвуют в правильном вытягивании данных, я потом по ним ориентируюсь в запакованном роме

[Марат]

Еще раз внимательно изучил алгоритм сжатия в использующийся в игре Genghiskhan, оказалось это LZB. Длина кодируется при помощи гамма-кодов Элиаса, а смещение, как я понял, при помощи кодов старт-шаг-стоп (англ. Start-step-stop) с параметрами 2, 2, 14.
В Blades of Vengeance тоже используется LZB, только там немного другиой гамма-код Элиаса.

[sergi]

Да ты просто распиши в чем суть его, я так то плохо шарю

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

ну от 0 избавится это святое дело конечно это всегда гдето 20-30% сжатия дает

[Марат]

Суть-то проста: это тоже самое, что lzh, только вместо кодов хаффмана используются коды Элиаса.
К примеру, для обычного lzss метода сжатия со словарем 4 кб и макс. длиной 18 байт, для кодирования пары 'длина, смещение' требуется 16 бит (12 на смещение и 4 для длины). Таким образом, не важно какая будет длина 3 байта или 18, все равно будет использоваться 4 бита. Со смещением та же беда. А элиас код позволяет кодировать фразу длиной 3 байта 1 битом, 4 и 5 байтов 3 битами. Ну и смещение точно также, только кодируются другими кодами. Они не так оптимальны как коды хаффмана, но зато не требуют построения дерева и дополнительной памяти, и к тому же, кодируются за один проход.
В Comix Zone, по-моему, неплохой метод сжатия используется, но какой-то сложный.
PS. B blades of vengeance, как оказалось, используются гамма-коды Левенштейна.

[sergi]

Ладно - имен много

всеравно раз словарь, то он место занимает и соответственно машинные циклы по подстановке данных в нужные места, да и оператива не резиновая - я в своем пакере обхожусь оперативой в 16 килобайт

[sergi]

Вот результат работы тут расположен
http://www.emu-land.net/forum/index.php/topic,29056.0.html