Список форумов shedevr.org.ru shedevr.org.ru
Группа перевода приставочных игр "ШЕДЕВР"
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 

[Документация] Архивы и алгоритмы сжатия
На страницу Пред.  1, 2, 3, 4  След.
 
Начать новую тему   Ответить на тему    Список форумов shedevr.org.ru -> Экстремальный ромхакинг
Предыдущая тема :: Следующая тема  
Автор Сообщение
LG.BALUKATION



Зарегистрирован: 05.08.2006
Сообщения: 141
Откуда: Saint-Patersburg

СообщениеДобавлено: Ср Ноя 07, 2007 5:55 am    Заголовок сообщения: Ответить с цитатой

Всёж насчёт дерева в Хоффмане...

Мы когда проходили это дело, строили дереаья по-другому. Там тож ищешь скока раз кадый элемент повторяется, сортируешь, а потом просто обьединяешь парами, пока не останется одно значение самого верхнего уровня. Ну, например та же фраза, тока в транслите (Gruppa_perevodov_"Shedevr".) и хранящаяся в text.txt. Вообще дальше пойдёт примерчег, рассчитанный на UNIX-системы, так что "./test" - просто название проги в текущем каталоге (в винде будет что-нить типа test.exe, хотя это уж как назовёте =), "$" - т.н. приглашение командной строки (в винде обычно "диск:\путь>" )

Считать мне самомы было лень, да и вспоминал я методику по более увесистому примеру, так что вот прога на чистом Си, которая подсчитывает байты (ВНИМАНИ!!! Прога не обрабатывает ошибки, так что в случае невозможности открыть файл, переданный ей параметром или в ещё какой ошибке всё просто молча рухнет - это очень упрощённая версия без заделки на реальную пригодность):
Код:
#include <stdio.h>
#include <stdlib.h>

unsigned long vals[256];

int main(int argc, char** argv)
{
        int c = 0x00;
        int i;

        FILE *f = fopen(argv[1], "r");

        do {
                c = fgetc(f);
                vals[c]++;
        } while (c != EOF);
        fclose(f);
        for (i = 0; i < 256; i++)
                if (vals[i] != 0)
                        printf("%d\t%4.2p (%3d, \'%c\')\n", vals[i], i, i, i);
        return 0;
}

Вызываем прогу для обработки текста и сохраняем результат в vals.txt
Код:
$ ./test text.txt > vals.txt
. Получаем несортированный файл, где в каждой строке будет указано - количенство повторений, hex-значение байта, dec-начение байта и соответствующий символ.

Сортируем (параметры n - для нормальной обработки чисел, r - изменить порядок на противоположный, т. е. чтоб было по-убыванию):
Код:
sort -nr vals.txt > sorted_vals.txt

Это даст файл такого же содержания, но уже отсортированный. Теперь соединяем попарно значения, строя такое дерево (я там сумму подписывал в каждом узле):
Код:
4 0x65 (101, 'e') \
3 0x76 (118, 'v') - 7 +
3 0x72 (114, 'r') \    \
3 0x70 (112, 'p') - 6 -- 13 +
2 0x6f (111, 'o') \          \
2 0x64 (100, 'd') - 4 +       \
2 0x5f ( 95, '_') \    \       \
2 0x22 ( 34, '"') - 4 -- 08 ---- 21 +
1 0x75 (117, 'u') \                  \
1 0x68 (104, 'h') - 2 +               \
1 0x61 ( 97, 'a') \    \               \
1 0x53 ( 83, 'S') - 2 -- 02 +           \
1 0x47 ( 71, 'G') \          \           \
1 0x2e ( 46, '.') - 2 -- 02 -- 04 -------- 25

Итого, получаем по 4 бита на любой символ.

В варианте же HoRRoR'а каждое значение кодируется переменным числом бит, но мне не совсем ясно построение дерева. Например, почему "п" = 000 а не 001? Ведь с таким же успехом можно сделать другое распределение символов по дереву (напремер, не чередуя их между "0" и "1" от уровня к уровню) и коды пойдут другие (но той же длинны). Как в играх обычно хранят дерево - в виде пар "кол-во повторений = значение" или уже готовым деревом?

ЗЫ: мой вариант для этой строки в транслите выйдёт на пол-байта длиннее =)
_________________
Zwei Drachen betrachten einander
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Ср Ноя 07, 2007 12:36 pm    Заголовок сообщения: Ответить с цитатой

Если често, не совсем понял, почему число бит должно равняться именно четырём? Ведь это будет уже не сжатие, а оптимизация Smile
А вообще Хаффман до этого мне встречался только один раз (STR-видео не всёт Smile ), поэтому пишу как знаю Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
LG.BALUKATION



Зарегистрирован: 05.08.2006
Сообщения: 141
Откуда: Saint-Patersburg

СообщениеДобавлено: Ср Ноя 07, 2007 5:32 pm    Заголовок сообщения: Ответить с цитатой

Прошёлся по линкам с википедии (кстати там есть и ссылка на простое описание построения дерева), моё дерево не верно - с ним не совсем Хаффман выйдет =) Твой пример ближе к оригиналу.

4 бита у моего дерева, потому как до любого символа получилось 4 узла.
_________________
Zwei Drachen betrachten einander
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Мар 15, 2008 5:45 pm    Заголовок сообщения: Ответить с цитатой

Добавил пример Хаффмана. Как и обещал Razz
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
BlueHairLady
RRC2008
RRC2008


Зарегистрирован: 12.05.2007
Сообщения: 158
Откуда: Гонолулу

СообщениеДобавлено: Сб Мар 15, 2008 11:31 pm    Заголовок сообщения: Ответить с цитатой

Прочитала. Заодно перечитала все статьи. По сравнению с первой версией стало несравнимо понятнее и лучше. От имени всех новичков большое спасибо, очень нужная вещь. Сейчас вышлю замечания (куда без них Smile ).
_________________
Надеюсь на возвращение, но сейчас меня нет.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
TTTT



Зарегистрирован: 26.04.2008
Сообщения: 2

СообщениеДобавлено: Сб Апр 26, 2008 8:01 pm    Заголовок сообщения: Ответить с цитатой

Все довольно полезно, но очень мало примеров.

Подскажите например, что за алгоритм шифрования текста в РОМе Battletoads_Double_Dragon_(U) ?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Апр 26, 2008 9:05 pm    Заголовок сообщения: Ответить с цитатой

Ну, сперва надо увидеть сам архив. И речь о какой платформе? На NES если и будет что-нибудь пожатое, то максимум какой-нибудь навороченный RLE. А вот на Сеге уже всё, что угодно быть может...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
TTTT



Зарегистрирован: 26.04.2008
Сообщения: 2

СообщениеДобавлено: Сб Апр 26, 2008 11:46 pm    Заголовок сообщения: Ответить с цитатой

NES
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
CaH4e3



Зарегистрирован: 21.01.2004
Сообщения: 195

СообщениеДобавлено: Вт Май 13, 2008 10:30 am    Заголовок сообщения: Ответить с цитатой

На денди однотипный алгоритм упаковки типа RLE использует в основном только Konami, все остальные пользуют свои совершенно разные алгоритмы и они могут быть "какие угодно". Хотя текст вообще упаковывается достаточно редко чем-нибудь серьезнее MTE.

В конкретном случае алгоритм чистый хафман со сбалансированным деревом. Правда, самые дальние его ветки кодируются более чем 8 битами - чаще 12, так что сжатие здесь все равно не идеальное. Битовый поток начинается от смещения 0x1b644 в ines файле. Бит 0 - левая ветка от узла, бит 1 - правая. Самая короткая ветка - у пробела, в три бита 110. У второй по частоте буквы Е - четыре бита, 0000 и тд. Деревья соответственно лежат по адресам 0x1B5BA, 0x1B5FF. Таблица символов, отсортированных по частоте употребления, по адресу 0x1B644.

0x1B68A - адрес таблицы ресурсов, по которым рассчитывается смещение нужного блока строк, так как битовый поток уплотнен, следующая строка текста может начинаться кодироваться с любого бита очередного байта потока. Каждый блок, на который указывает один указатель, содержит четыре строки текста, оканчивающиеся 0xFD. Распаковываться может любая по выбору, в зависимости от заданного входного параметра.

Унпакер: скормить кусок данных от вышеуказанного адреса до примерно 0x1C030.
Код:
unsigned char tree_left[69] = {
         0x43,0xC5,0xC3,0xC1,0xBF,0xBD,0xBB,0xB9,0xB7,0xB5,0xB3,0xB1,0xAF,0xAD,0xAB,0xA9,
         0x0B,0x09,0x07,0x05,0x03,0x01,0xA7,0x14,0x12,0x10,0x0E,0xA5,0x15,0xA2,0x19,0x17,
         0x1B,0xA1,0x1E,0xA0,0x9E,0x9C,0x21,0x22,0x9A,0x98,0x97,0x25,0x26,0x93,0x27,0x28,
         0x8F,0x8D,0x8C,0x2B,0x2C,0x8A,0x2E,0x87,0x86,0x31,0x32,0x84,0x83,0x35,0x81,0x38,
         0x3A,0x3C,0x80,0x3F,0x41
         };

unsigned char tree_right[69] = {
         0x44,0xC4,0xC2,0xC0,0xBE,0xBC,0xBA,0xB8,0xB6,0xB4,0xB2,0xB0,0xAE,0xAC,0xAA,0x0C,
         0x0A,0x08,0x06,0x04,0x02,0xA8,0xA6,0x13,0x11,0x0F,0x0D,0xA4,0xA3,0x1A,0x18,0x16,
         0x1C,0x1F,0x1D,0x9F,0x9D,0x20,0x9B,0x23,0x99,0x24,0x96,0x95,0x94,0x92,0x91,0x90,
         0x8E,0x29,0x2A,0x8B,0x2D,0x89,0x88,0x2F,0x30,0x85,0x33,0x34,0x82,0x36,0x37,0x39,
         0x3B,0x3D,0x3E,0x40,0x42
         };
         
unsigned char tree_lookup[70] = {
         0x20,0x45,0x54,0x41,0x4F,0x53,0x49,0x4E,0x52,0x48,0x4C,0xA0,0x55,0x4D,0x44,0x42,
         0x59,0x43,0x27,0x21,0x47,0x57,0x50,0xFD,0x46,0x4B,0x2C,0x2E,0x5A,0x2D,0x56,0x2A,
         0x80,0xFF,0x82,0x4A,0x51,0x3F,0x92,0x81,0x58,0x09,0x06,0xA9,0xC0,0x39,0xC8,0x85,
         0xA3,0xA1,0x31,0xA5,0x40,0xE0,0xA8,0xA4,0x14,0x22,0xCC,0x33,0xD0,0x0B,0xD9,0x08,
         0xD2,0xC7,0xC5,0xCD,0xCE,0x03
         };

int           bit_counter, byte_counter;
unsigned char cur_byte;
unsigned char get_next_bit(char *b)
{
   if (bit_counter==0)
   {
       bit_counter=7;
       cur_byte=b[byte_counter++];
   }
   else
   {
       bit_counter--;
       cur_byte<<=1;
   }
   return cur_byte & 0x80;
}


int decode(char *in_buf, char *out_buf, int pack_size, int buf_size)
{
    int out_byte = 0;
    unsigned char data_byte;
   
    bit_counter=0;
    byte_counter=0;

    while (byte_counter<=pack_size)
    {
        data_byte = 0; 
        while (!(data_byte&0x80))
        {
           if(get_next_bit(in_buf))
             data_byte = tree_right[data_byte];
           else
             data_byte = tree_left[data_byte];
        }
        data_byte = tree_lookup[data_byte&0x7F];
        out_buf[out_byte++] = data_byte;
    }
    return out_byte;
}


Собственно, что должно получиться.
http://cah4e3.shedevr.org.ru/misc/RES_DATA.BIN.unp
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Макс
Гость





СообщениеДобавлено: Сб Май 17, 2008 5:35 pm    Заголовок сообщения: Ответить с цитатой

Извеняюсь, что поднимаю тему. Нет ли у кого-нибудь исходного кода запаковки GBA lz77? На С\С++, желательно попонятнее. Распаковщик написан, а вот запаковщик, даже представления не имею, с чего начинать... Embarassed Или хотя бы статейки какие-нибудь.
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Май 17, 2008 5:59 pm    Заголовок сообщения: Ответить с цитатой

У Джинна вроде был, правда на Дельфях, но чё-то он пропал куда-то...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
CaH4e3



Зарегистрирован: 21.01.2004
Сообщения: 195

СообщениеДобавлено: Сб Май 17, 2008 6:14 pm    Заголовок сообщения: Ответить с цитатой

Для гба полно готовых зап-распаковщиков. Есть сырцы MIO0 для N64.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Гость






СообщениеДобавлено: Сб Май 17, 2008 6:45 pm    Заголовок сообщения: Ответить с цитатой

Цитата:
У Джинна вроде был, правда на Дельфях, но чё-то он пропал куда-то...
Джинн говорил, что сам в нём ничего не понимает. Sad
Цитата:
Для гба полно готовых зап-распаковщиков.
Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Rolling Eyes Вот где своё и нужно.
Ладно, будем искать. Sad
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Май 17, 2008 6:48 pm    Заголовок сообщения: Ответить с цитатой

Цитата:
Джинн говорил, что сам в нём ничего не понимает.

Пишет, и не понимает, что пишет? :)

Цитата:
Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Вот где своё и нужно.
Ладно, будем искать.

Ммм... А где это вы работаете с таким количеством файлов? NDS? Что за проекты?
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Макс
Гость





СообщениеДобавлено: Сб Май 17, 2008 7:05 pm    Заголовок сообщения: Ответить с цитатой

Цитата:
Ммм... А где это вы работаете с таким количеством файлов? NDS? Что за проекты?
Phoenix Wright на NDS, там более 1000 вчера насчитал точно. Может, больше. Да и скрипты там в псевдо архивах, по 10-20 штук на архив + каждый скрипт пожат lz77. Каждый раз отдельно пережимать все скрипты вручную очень трудоёмко, гораздо легче было бы всё автоматом, собственно, затем исходники и понадобились.
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Май 17, 2008 8:47 pm    Заголовок сообщения: Ответить с цитатой

Вот самый мой короткий и простой код LZ-сжатия:

Код:
function CBlockLZ(var P,WP: Pointer; MaxLink,MaxSize: Integer; Test: Boolean): Integer;
var  nRB,nB,B,WB: ^Byte;
Best,bLink,n,m,Count: Integer;
begin
 Result:=-15;
 If MaxLink<2 Then Exit; // Если осталось 2 байта - паковать нет смысла
 If MaxSize>16 Then MaxSize:=16;  // Максимальная цепочка - 16 байт (особенности алгоритма)
 B:=P; WB:=WP; Best:=-1; // Присваиваем поинтеры. Лучшый результат - -1 сжатых байт.
 If MaxLink>1024 Then MaxLink:=1024; Устанавливаем максимально возможный диапазон поиска цепочек, поддающихся сжатию.
 For m:=MaxLink downto 1 do // Цикл внутри этого диапазона. От его первого, до последнего байта (ну кроме двух последних байт).
 begin
  Count:=0; nRB:=B; Inc(nRB,-m);  nB:=B;
  For n:=0 To MaxSize do // В этом цикле сравниваем цепочку на позиции чтения с цепочкой внутри диапазона
   begin
    If nRB=B Then Inc(nRB,-m);
    If nB^<>nRB^ Then Break;
    Inc(nB); Inc(nRB); Inc(Count);
   end;
  If Count>Best Then begin Best:=Count; bLink:=m; End; // Если количество совпадающих байт больше лучшего результата - то новый лучший результат становится текущим.
   If Count=16 Then break; Если лучшего результата уже не добьёмся - нет смысла искать дальше.
 end;
 // Далее сохраняем информацию о сжатой цепочках в соответствии с особенностями алгоритма.
 WB^:=$80+(((Best-2) SHL 2) AND $3C)+(((bLink-1) SHR 8) AND $3);
 Inc(WB);
 WB^:=(bLink-1) AND $FF;
 Inc(WB);
 Inc(B,Best);
 If not Test Then begin P:=B; WP:=WB; end;
 Result:=Best-2;
end;

В принципе, на подобной основе я пишу все LZ-пакеры.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Гость






СообщениеДобавлено: Сб Май 17, 2008 11:22 pm    Заголовок сообщения: Ответить с цитатой

HoRRoR, спасибо большое. Smile Хоть я в Дельфи и не соображаю, постараюсь с помощью друзей перевести на С++.
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Май 17, 2008 11:47 pm    Заголовок сообщения: Ответить с цитатой

Эм... Это общий пример, к GBA отношения не имеет) Я просто рассказал общий принцип, который подходит под все разновидности LZ))
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Гость






СообщениеДобавлено: Вс Май 18, 2008 4:08 am    Заголовок сообщения: Ответить с цитатой

Anonymous писал(а):
Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Rolling Eyes Вот где своё и нужно.
Ладно, будем искать. Sad

Хз, чем вы пользуетесь, но древнющщий GBACrusher умеет паковать-распаковывать файлы пачкой по списку, в каких хочешь количествах.
Вернуться к началу
Shiru



Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow

СообщениеДобавлено: Вс Май 18, 2008 4:20 am    Заголовок сообщения: Ответить с цитатой

Вообще, для автоматизации подобных вещей существуют bat-файлы. А если очень хитроумный процесс сборки - можно написать программу, которая будет выполнять нужные действия, пользуясь внешним пакером/депакером.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Djinn
RRC2008
RRC2008


Зарегистрирован: 16.03.2004
Сообщения: 633
Откуда: Москва

СообщениеДобавлено: Чт Май 22, 2008 1:36 pm    Заголовок сообщения: Ответить с цитатой

В алгоритме LZ сжатия я действительно ничего не понимаю. У меня просто есть код мною же переписанный с C++ на Delphi.
А Макс - это Zalbard похоже? Smile Понятней исходников gbalz.exe и разнообразных эмуляторов GBA ты ничего не найдёшь.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Макс
Гость





СообщениеДобавлено: Чт Май 22, 2008 3:27 pm    Заголовок сообщения: Ответить с цитатой

Цитата:
А Макс - это Zalbard похоже? Понятней исходников gbalz.exe и разнообразных эмуляторов GBA ты ничего не найдёшь.
Я. Very Happy А до эмуляторных исходников мне ещё далеко. Sad Поэтому и просил, чтобы какой-нибудь фан-кракен показал что-то своё.
Вернуться к началу
wl



Зарегистрирован: 20.12.2005
Сообщения: 76
Откуда: Россия

СообщениеДобавлено: Пн Сен 15, 2008 2:30 pm    Заголовок сообщения: Ответить с цитатой

если еще актуально, то исходники распаковки запаковки (rle, lz77, huffman и какой-то Differential filter) есть в NitroSDK
http://narod.ru/disk/2607127000/ntrcomp.zip.html
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Марат



Зарегистрирован: 08.01.2008
Сообщения: 211
Откуда: Казахстан, Астана

СообщениеДобавлено: Пт Окт 17, 2008 9:11 pm    Заголовок сообщения: Ответить с цитатой

Как дополнение к документации HoRRoR'a, ссылка на сайт с визуализаторами алгоритмов LZ, LZW, адаптивный Huffman и статический Huffman - Методы сжатия
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Сб Окт 18, 2008 9:40 am    Заголовок сообщения: Ответить с цитатой

Эти визуализаторы вряд ли помогут, я в своё время по ним нифига не понял Smile Всё-таки в играх всё проще обычно.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов shedevr.org.ru -> Экстремальный ромхакинг Часовой пояс: GMT + 3
На страницу Пред.  1, 2, 3, 4  След.
Страница 2 из 4

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


Powered by phpBB © 2001, 2005 phpBB Group