Разработка и ромхакинг > Ромхакинг и программирование

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

<< < (2/3) > >>

sergi: К сожалению обнаружено что бывает и больше 512 разнообразие сборок по 2 байта их бывает и 1500, но редко поэтому 1024 т.е. 10 бит еще можно както использовать - хоть немножко пожать, а вот 2048 уже нет смысла, файл только больше будет зато бывает всего 1 разнообразие, т.е. только одна сборка 2 байта которая повторяется, значит собственно только 1 бит и нужен что очень выгодно получается в общем смысл жать палюбому есть ;) использовать алгоритмы которые будут распределять по частоте встречаемости разделять сборки а потом более часто повторяющиеся обозначать меньшим количеством бит, а редкие большим конечно тоже можно теоретически, но практически написать такой алгоритм сложновато будет, да и еще не известно успеет ли все это дело распаковаться в установленное время, т.к. распаковывать нужно фактически каждое обновление кадра

GManiac: Почему-то я ожидал, что ты запостишь кусок сюда ;) Мог бы аттачем архив выложить. Пример посмотрю, потом отпишу. Добавлено позже: Ты дал кусок размером 8064 байта в текстовом виде. Я перевёл его в двоичный вид и для интереса сравнил: двоичный файл сжимается сильнее хексового, т.е. внутрибайтные связи слабее внешних. Но увы, больше чем в два раза (до 4032 байт) этот кусок сжимается только сильными архиваторами, причём ППМдшными (раром и 7-зипом). LZ-схемы в архиваторах его толком не берут (Zip, LZMA), правда, LZMA сжимает, но почти впритык, а если кусок был бы хуже, он бы его не сжал.... Про простые схемы, которые можно пихнуть на 68k, и говорить нечего - RNC сжимает кусок до 4613 байт - это много. Тебе обязательно сжимать отдельно куски по 8 кб или можно больше? Добавлено позже: --- Цитата ---Ну больше, так больше 9 бит может быть кратным 8 при числе 72 т.е. берем 9 байт и там будет 8 наших уникальных идетнификаторов сцепок т.е. брать нужно по 9 байт из этих 8 килобайт последовательно и вытягивать потихоньку --- Конец цитаты --- Насчёт 9 бит ты наверно не так понял. Ты говорил, что есть не более 512 разных слов (2 байта), правда, я подумал, что ВООБЩЕ не больше 512 разных слов во всех двух Мбайтах. Поэтому решил, что можно составить ОБЩУЮ таблицу этих слов (512*2), перекодировать 8кбайтные куски из 16-битного кода в 9-битный, НО... тебе надо сжать в 2 раза, т.е. в среднем по 8 бит на слово, а не по 16 и не по 9. Поэтому я и сказал, что раз 9 бит больше 8, то сжимать перекодированный кусок всё равно надо. А позже ты сказал, что последовательности разные для всех кусков. Это сильно усложняет дело, потому что таблица займёт 1 кб, и 3 кб останется для архива - это очень мало. В любом случае можно обойтись без хранения таблицы. Объясню, почему. Нам известно, что весь кусок разбит на слова. Всего разных слов пусть будет 512. Если бы ты закодировал их в таблицу и использовал 9-битные коды слов и пытался бы сжимать их последовательность LZ-схемой, ты бы использовал указатели назад от 0 до 4095 слова (или 4.7 кбайта), т.е. указатели всё равно по 12-13 бит. А раз слова выровнены по 2 байта, то исходную последовательность можно сжать, используя чётные указатели. В общем, я всё это к тому говорю, что сжатие перекодированного (по 9 бит) куска можно свести к сжатию исходного куска, зная его особенности, а поэтому таблица будет лишней. Это всё равно что сводимость словарных методов к статистическим. Словарные методы выделили в отдельный класс только из-за удобства.

sergi: Ну я жал зипом и раром эти 8 килобайтные куски и получал гдето +- 4 кб в зависимости от типа сжатия самым крутым раром то вообще 3,15 это код в хексе, собственно запостил и жал его также на счет сложности - пока сложности не вижу, как и поинтеры на таблицы пока тоже собственно у меня да таблица 512 или больше уникальных 2-х байтовых слов тогда это 1 килобайт весит 9 бит как поинтер на конкретную спарку дают компактную запись всей 8 килобайтной последовательности в виде (9*4032)/8=4536 байт но при этом там будут 0, которые я не буду указывать, т.к. они только в конце появляются и всеравно в памяти по умолчанию лежат и так, поэтому достаточно обозначить только следующую 32 байтную последовательность которая всегда начинается с 0000 поэтому это позволит съэкономить ну 15-20% как я оценял вот и будет гдето 4 килобайта вместо 8, ну больше, ну меньше, всеравно и не ровно 512 там, и бывает всего 200 и даже еще меньше, бывает правда и больше, в среднем гдето на 4 кило выходит но сложнее алгоритм конечно же M68K просто так не исполнит т.е. данные специфичные, повторяющиеся, похожие друг на друга и закон у них общий, что дает возможность сжатия ^_^ а что там на счет четных указателей? т.е. это как можно использовать?

GManiac: --- Цитата ---у меня да таблица 512 или больше уникальных 2-х байтовых слов тогда это 1 килобайт весит 9 бит как поинтер на конкретную спарку дают компактную запись всей 8 килобайтной последовательности в виде (9*4032)/8=4536 байт --- Конец цитаты --- Так таблица для каждого 8-кбайтного куска своя, т.е. 1 килобайт уже забит под таблицу, а под архив остаётся 3 кб. Обязательно сжимать куски по 8 кб или можно больше? --- Цитата ---самым крутым раром то вообще 3,15 --- Конец цитаты --- Ты не смотри на рар, смотри на чистые LZ-схемы вроде LZMA или Zip. Они этот кусок из примера толком не могли сжать. А сеговский архиватор тем более не сможет.

sergi: Ну потому что общая разновидность этих сборок вообще существующих 32768+1 поэтому общую таблицу возможно конечно тоже можно сделать, но в реале это будет 15 бит если 0 не учитывать вместо 16 и сомнительно что это уменьшит размер даже если умножить на миллион поэтому каждый 8 килобайтный кусок, складывающийся из 256 сборок по 32 байта, где первый всегда 0000 - нужно ужать до 4 килобайт, ну гдето в этот размер, т.к. бывает и легко пожать т.к. разнообразия там нет или сложно это более 1000 разновидностей Зип гдето обычно жмет до 4,20 килобайт, ну это потому что там алгоритм сложнее, скорее всего идет учет повторяемости спарок и прочее жать куски большего размера может будет и эффективнее, но проблема в том что нужно четко разжимать в установленное время несложным алгоритмом именно по 8 килобайт в определенное место памяти, чтобы из нее потом взять этот разжатый кусок да и место в памяти мало хотя пачкой жать конечно еще круче, вытягивать сложно будет - машинных циклов понадобится больше чтобы распаковать - собственно время распаковки зависит от размера файла ну и так то было бы неплохо иметь универсальный архиватор для M68K на любой случай жизни - думаю любому пригодится - я выложу если сделаю в асме его ;) в сущности не суть важно сколько именно килобайт кусок, важно зажать гдето в 2 раза несложно и недорого, собственно этот алгоритм вроде подходит то что таблица нужна будет - ну что делать - нужна значит будет :-\

GManiac: --- Цитата ---в сущности не суть важно сколько именно килобайт кусок, важно зажать гдето в 2 раза несложно и недорого, собственно этот алгоритм вроде подходит --- Конец цитаты --- Ты же сам видишь, что в 2 раза даже мощные LZ-архиваторы сжать не могут, что говорить о простом алгоритме для 68к? Самый лучший универсальный пакер, годный для 68к, - RNC. Для декодирования указателя, сжатого Хаффманом, он делает в самом худшем случае не больше 16 простых сравнений, побитовая реализация окажется хуже. LZ-часть тоже простая - обычное копирование байт. LZ без Хаффмана будет чуть быстрее, но сжимать будет хуже. К тому же для RNC есть готовый пакер. Поэтому остаётся один выход: если циклов достаточно, надо увеличить кусок. Если нет, то придётся бросить это дело. Сколько точно циклов имеется?

sergi: Ну 1000 точно имеется а непосредственно его алгоритм можно расписать применительно к M68K, а то я так и не понял что там как конкретно делается :?

GManiac: 1000 тактов на 68к - это 100-120 средних команд. Это ОЧЕНЬ мало. Исходник анпакера есть в архиве Propack.zip или как его там, в инете он есть. Хотя... ладно, вот мои комментарии. Может, поймёшь что-нибудь :)

sergi: А сколько тактов нужно? в принципе может пару тысяч наберется

GManiac: Простое побайтовое копирование move.b (An)+,(Am)+ dbra dn занимает 22 такта на байт. На 8 кб - 176 тыщ тактов. Учитывая сжатие, нужно время на чтение указателей, чтение битов, итого в лучшем случае тактов надо в 2-3 раза больше. А с декодированием указателей в RNC - раз этак в 5. Добавлено позже: Вон в Аладдине для пояснительного экрана разжимается кусок в 32 кб. И на это уходит около секунды (7.5 млн тактов).

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: --- Цитата: sergi от 31 Май 2009, 09:51:42 ---возможно можно будет сделать пересчет картинки чтобы поворачивало изображение и в тайлы изображение перекладывало, но там вроде синус и косинус нужно считать и довольно быстро - посмотрим короче --- Конец цитаты --- 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 для распаковки

Навигация

 Главная страница сообщений

Следующая страница

Предыдущая страница

Перейти к полной версии