|
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 |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
Добавлено: Ср Ноя 07, 2007 12:36 pm Заголовок сообщения: |
|
|
Если често, не совсем понял, почему число бит должно равняться именно четырём? Ведь это будет уже не сжатие, а оптимизация
А вообще Хаффман до этого мне встречался только один раз (STR-видео не всёт ), поэтому пишу как знаю _________________ Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
Вернуться к началу |
|
|
LG.BALUKATION
Зарегистрирован: 05.08.2006 Сообщения: 141 Откуда: Saint-Patersburg
|
Добавлено: Ср Ноя 07, 2007 5:32 pm Заголовок сообщения: |
|
|
Прошёлся по линкам с википедии (кстати там есть и ссылка на простое описание построения дерева), моё дерево не верно - с ним не совсем Хаффман выйдет =) Твой пример ближе к оригиналу.
4 бита у моего дерева, потому как до любого символа получилось 4 узла. _________________ Zwei Drachen betrachten einander |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
|
Вернуться к началу |
|
|
BlueHairLady RRC2008
Зарегистрирован: 12.05.2007 Сообщения: 158 Откуда: Гонолулу
|
Добавлено: Сб Мар 15, 2008 11:31 pm Заголовок сообщения: |
|
|
Прочитала. Заодно перечитала все статьи. По сравнению с первой версией стало несравнимо понятнее и лучше. От имени всех новичков большое спасибо, очень нужная вещь. Сейчас вышлю замечания (куда без них ). _________________ Надеюсь на возвращение, но сейчас меня нет. |
|
Вернуться к началу |
|
|
TTTT
Зарегистрирован: 26.04.2008 Сообщения: 2
|
Добавлено: Сб Апр 26, 2008 8:01 pm Заголовок сообщения: |
|
|
Все довольно полезно, но очень мало примеров.
Подскажите например, что за алгоритм шифрования текста в РОМе Battletoads_Double_Dragon_(U) ? |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
Добавлено: Сб Апр 26, 2008 9:05 pm Заголовок сообщения: |
|
|
Ну, сперва надо увидеть сам архив. И речь о какой платформе? На NES если и будет что-нибудь пожатое, то максимум какой-нибудь навороченный RLE. А вот на Сеге уже всё, что угодно быть может... _________________ Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
Вернуться к началу |
|
|
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? На С\С++, желательно попонятнее. Распаковщик написан, а вот запаковщик, даже представления не имею, с чего начинать... Или хотя бы статейки какие-нибудь. |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
|
Вернуться к началу |
|
|
CaH4e3
Зарегистрирован: 21.01.2004 Сообщения: 195
|
Добавлено: Сб Май 17, 2008 6:14 pm Заголовок сообщения: |
|
|
Для гба полно готовых зап-распаковщиков. Есть сырцы MIO0 для N64. |
|
Вернуться к началу |
|
|
Гость
|
Добавлено: Сб Май 17, 2008 6:45 pm Заголовок сообщения: |
|
|
Цитата: | У Джинна вроде был, правда на Дельфях, но чё-то он пропал куда-то... | Джинн говорил, что сам в нём ничего не понимает.
Цитата: | Для гба полно готовых зап-распаковщиков. | Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Вот где своё и нужно.
Ладно, будем искать. |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
Добавлено: Сб Май 17, 2008 6:48 pm Заголовок сообщения: |
|
|
Цитата: | Джинн говорил, что сам в нём ничего не понимает. |
Пишет, и не понимает, что пишет? :)
Цитата: | Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Вот где своё и нужно.
Ладно, будем искать. |
Ммм... А где это вы работаете с таким количеством файлов? NDS? Что за проекты? _________________ Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
Вернуться к началу |
|
|
Макс Гость
|
Добавлено: Сб Май 17, 2008 7:05 pm Заголовок сообщения: |
|
|
Цитата: | Ммм... А где это вы работаете с таким количеством файлов? NDS? Что за проекты? | Phoenix Wright на NDS, там более 1000 вчера насчитал точно. Может, больше. Да и скрипты там в псевдо архивах, по 10-20 штук на архив + каждый скрипт пожат lz77. Каждый раз отдельно пережимать все скрипты вручную очень трудоёмко, гораздо легче было бы всё автоматом, собственно, затем исходники и понадобились. |
|
Вернуться к началу |
|
|
HoRRoR 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 |
|
Вернуться к началу |
|
|
Гость
|
Добавлено: Сб Май 17, 2008 11:22 pm Заголовок сообщения: |
|
|
HoRRoR, спасибо большое. Хоть я в Дельфи и не соображаю, постараюсь с помощью друзей перевести на С++. |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
Добавлено: Сб Май 17, 2008 11:47 pm Заголовок сообщения: |
|
|
Эм... Это общий пример, к GBA отношения не имеет) Я просто рассказал общий принцип, который подходит под все разновидности LZ)) _________________ Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
Вернуться к началу |
|
|
Гость
|
Добавлено: Вс Май 18, 2008 4:08 am Заголовок сообщения: |
|
|
Anonymous писал(а): | Вот, ими только и пользуемся. Но если нужно запаковать более 100 файлов, да ещё и при определённых условиях... Вот где своё и нужно.
Ладно, будем искать. |
Хз, чем вы пользуетесь, но древнющщий GBACrusher умеет паковать-распаковывать файлы пачкой по списку, в каких хочешь количествах. |
|
Вернуться к началу |
|
|
Shiru
Зарегистрирован: 25.10.2006 Сообщения: 295 Откуда: Russia, Moscow
|
Добавлено: Вс Май 18, 2008 4:20 am Заголовок сообщения: |
|
|
Вообще, для автоматизации подобных вещей существуют bat-файлы. А если очень хитроумный процесс сборки - можно написать программу, которая будет выполнять нужные действия, пользуясь внешним пакером/депакером. |
|
Вернуться к началу |
|
|
Djinn RRC2008
Зарегистрирован: 16.03.2004 Сообщения: 633 Откуда: Москва
|
Добавлено: Чт Май 22, 2008 1:36 pm Заголовок сообщения: |
|
|
В алгоритме LZ сжатия я действительно ничего не понимаю. У меня просто есть код мною же переписанный с C++ на Delphi.
А Макс - это Zalbard похоже? Понятней исходников gbalz.exe и разнообразных эмуляторов GBA ты ничего не найдёшь. |
|
Вернуться к началу |
|
|
Макс Гость
|
Добавлено: Чт Май 22, 2008 3:27 pm Заголовок сообщения: |
|
|
Цитата: | А Макс - это Zalbard похоже? Понятней исходников gbalz.exe и разнообразных эмуляторов GBA ты ничего не найдёшь. | Я. А до эмуляторных исходников мне ещё далеко. Поэтому и просил, чтобы какой-нибудь фан-кракен показал что-то своё. |
|
Вернуться к началу |
|
|
wl
Зарегистрирован: 20.12.2005 Сообщения: 76 Откуда: Россия
|
|
Вернуться к началу |
|
|
Марат
Зарегистрирован: 08.01.2008 Сообщения: 211 Откуда: Казахстан, Астана
|
Добавлено: Пт Окт 17, 2008 9:11 pm Заголовок сообщения: |
|
|
Как дополнение к документации HoRRoR'a, ссылка на сайт с визуализаторами алгоритмов LZ, LZW, адаптивный Huffman и статический Huffman - Методы сжатия |
|
Вернуться к началу |
|
|
HoRRoR RRC2008
Зарегистрирован: 21.06.2006 Сообщения: 2341 Откуда: Ростов-на-Дону
|
Добавлено: Сб Окт 18, 2008 9:40 am Заголовок сообщения: |
|
|
Эти визуализаторы вряд ли помогут, я в своё время по ним нифига не понял Всё-таки в играх всё проще обычно. _________________ Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
Вернуться к началу |
|
|
|
|
Вы не можете начинать темы Вы можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах
|
Powered by phpBB © 2001, 2005 phpBB Group
|