 |
shedevr.org.ru
Группа перевода приставочных игр "ШЕДЕВР"
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
gottax
Зарегистрирован: 16.11.2003
Сообщения: 588
Откуда: Курск
|
 Добавлено: Вт Мар 27, 2007 7:14 pm Заголовок сообщения: У кого есть исходники запаковщика по RLE-алгоритму? |
 |
|
Нужен сабж, 8-битовый RLE (с двухбайтовым окном). Подойдёт исходник на языках Си, Бейсик или Паскаль. В сети что-то ничего подходящего не нашёл.
Уже третий день бьюсь над своим пакером, но не могу добиться полноценного результата. Он сжимает чуть хуже, чем оригинальный алгоритм.
Да, ещё забыл упомянуть, что это не простой RLE - кроме цепочек из повторяющихся байтов, кодируются и цепочки из последовательных байтов (05h 06h 07h 08h и т. п.).
Может у кого-нибудь есть старые наработки? Буду очень признателен. |
|
| Вернуться к началу |
|
 |
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Вт Мар 27, 2007 7:32 pm Заголовок сообщения: |
|
|
Ну ты приколист, конечно.  А в темпе посмотреть? У Рефреша мой пример уже несколько лет лежит. Хотя у тебя случай более продвинутый, так что вряд ли поможет, надо разбираться (сам знаешь где - в Асе!  )
Последний раз редактировалось: АнС (Ср Мар 28, 2007 12:45 pm), всего редактировалось 1 раз |
|
| Вернуться к началу |
|
|
Djinn
RRC2008
Зарегистрирован: 16.03.2004
Сообщения: 633
Откуда: Москва
|
| Добавлено: Вт Мар 27, 2007 9:49 pm Заголовок сообщения: |
|
|
Код упаковщика для Beetlejuice.
Извиняюсь, комментарии не пишу.
| Код: | Program BJMapCompress;
{$APPTYPE CONSOLE}
uses
SysUtils,
Hexunit;
Type
DWord = LongWord;
PBytes = ^TBytes;
TBytes = Array[Word] of Byte;
Var
ROM: PBytes;
Var
RomSize: Integer; F: File; A1: Byte; X, Y, K, I, J: Integer; VRAM: String;
begin
AssignFile(F, ParamStr(1));
Reset(F, 1);
RomSize := FileSize(F) - 2;
GetMem(ROM, RomSize);
Seek(F, 2);
BlockRead(F, ROM^, RomSize);
CloseFile(F);
A1 := HexVal(ParamStr(3));
I := 0;
Repeat
X := ROM^[I];
Inc(I);
If X = 0 then
begin
J := 1;
While ROM^[I] = X do
begin
Inc(I);
Inc(J);
end;
VRAM := VRAM + Char(X) + Char(J);
end Else
begin
Y := X;
J := 1; K := I;
While ROM^[K] - 1 = Y do
begin
Y := ROM^[K];
Inc(K);
Inc(J);
end;
If J > 3 then
begin
I := K;
VRAM := VRAM + Char($FF) + Char(J) + Char(X + A1);
end Else
VRAM := VRAM + Char(X + A1);
end;
Until I = RomSize;
FreeMem(ROM, RomSize);
AssignFile(F, ParamStr(2));
Rewrite(F, 1);
BlockWrite(F, VRAM[1], Length(VRAM));
CloseFile(F);
end.
|
|
|
| Вернуться к началу |
|
|
Shiru
Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow
|
| Добавлено: Ср Мар 28, 2007 12:12 am Заголовок сообщения: |
|
|
| gottax писал(а): | | 8-битовый RLE (с двухбайтовым окном) |
Что есть 'двухбайтовое окно'?
Вот мой исходник, несколько специфический вариант RLE (последовательные байты жать не умеет, это ты уже сам придумывай).
| Код: | //Формат сжатия: если встретился маркер (0x80), следующий
//байт или байты определяют,сколько раз повторить байт перед маркером.
//Длина повторяемой части хранится в виде числа переменной разрядности:
//каждый байт содержит 7 бит числа; если старший бит установлен - это
//последний байт числа. Если количество повторений = 0, то это
//одиночный байт со значением, совпадающим с маркером.
struct modRleStream {
unsigned char *data;
unsigned char marker;
int prevByte;
int prevCnt;
int size;
int ptr;
};
void mod_rle_init(modRleStream *stream,unsigned char *data,int size)
{
stream->data=data;
stream->size=size;
stream->marker=0x80;
stream->ptr=0;
stream->prevByte=-2;
stream->prevCnt=0;
}
unsigned char mod_rle_get(modRleStream *stream)
{
unsigned char val;
int shift;
if(stream->prevCnt>1)
{
stream->prevCnt--;
return stream->prevByte;
}
val=stream->data[stream->ptr++];
if(val==stream->marker)
{
stream->prevCnt=0;
shift=0;
while(1)
{
val=stream->data[stream->ptr++];
stream->prevCnt|=((val&0x7f)<<shift);
if(val&0x80) break;
shift+=7;
}
if(stream->prevCnt==0) return stream->marker;
stream->prevCnt--;
return stream->prevByte;
}
else
{
stream->prevByte=val;
return val;
}
}
void mod_rle_put(modRleStream *stream,int val)//-1 для flush
{
val&=0xff;
if(val!=stream->prevByte||val<0)
{
if(stream->prevCnt>2)
{
stream->data[stream->ptr++]=stream->marker;
while(stream->prevCnt>0)
{
stream->data[stream->ptr++]=(stream->prevCnt&0x7f)|((stream->prevCnt<128)?0x80:0);
stream->prevCnt>>=7;
}
}
if(stream->prevCnt==2)
{
stream->data[stream->ptr++]=stream->prevByte;
}
if(val<0) return;
stream->prevCnt=1;
stream->data[stream->ptr++]=val;
if(val==stream->marker)
{
stream->data[stream->ptr++]=0x80;
stream->prevByte=-2;
}
else
{
stream->prevByte=val;
}
if(stream->ptr>stream->size-8)
{
stream->size+=16384;
stream->data=(unsigned char*)realloc(stream->data,stream->size);
}
}
else
{
stream->prevCnt++;
}
}
void mod_rle_putstr(modRleStream *stream,unsigned char *str,int len)
{
int aa,slen;
slen=strlen((const char*)str);
for(aa=0;aa<slen;aa++) mod_rle_put(stream,str[aa]);
for(aa=0;aa<len-slen;aa++) mod_rle_put(stream,0);
}
void mod_rle_getstr(modRleStream *stream,unsigned char *str,int len)
{
int aa;
for(aa=0;aa<len;aa++) *str++=mod_rle_get(stream);
}
void mod_rle_putword(modRleStream *stream,int val)
{
mod_rle_put(stream,val);
mod_rle_put(stream,val>>8);
}
int mod_rle_getword(modRleStream *stream)
{
int val;
val=mod_rle_get(stream);
val|=mod_rle_get(stream)<<8;
return val;
}
|
Используется примерно так:
Запись:
| Код: | modRleStream stream;
unsigned char *data;
int size;
size=16384;
data=(unsigned char*)malloc(size);
mod_rle_init(&stream,data,size);
mod_rle_put(&stream,один байт);
mod_rle_putword(&stream,двухбайтовое значение);
mod_rle_putstr(&stream,строка,длина строки);
mod_rle_put(&stream,-1);//завершаем сжатие
fwrite(data,stream.ptr,1,file);//пишем в файл
|
Чтение:
| Код: |
//сначала читаем сжатые данные в data, также имеем размер size
mod_rle_init(&stream,data,size);
байт=mod_rle_get(&stream);
//и т.п.
|
|
|
| Вернуться к началу |
|
|
gottax
Зарегистрирован: 16.11.2003
Сообщения: 588
Откуда: Курск
|
| Добавлено: Ср Мар 28, 2007 6:55 am Заголовок сообщения: |
|
|
| Shiru писал(а): | | Что есть 'двухбайтовое окно'? |
Ну, есть ещё вроде 4-битный RLE, в котором сравниваются не соседние байты, а соседние тетрады, соотвественно "окно" (то есть сравниваемая область) составляет 1 байт (в 8-битном RLE это окно 2 байта).
Спасибо большое за исходники, буду разбираться (с указателями и потоками я никогда не работал, так что разбираться, наверное, придётся долго ). Джинн, а ты не мог бы ещё кинуть мне сжатый и расжатый этим алгоритмом кусок? Или хотя бы вкратце описать особенности алгоритма. Например, в моём случае используется 3 ветки кодирования:
1)если следующий за проверяемым байтом байт равен ему (X2=X1)
2)если следующий за проверяемым байтом байт на единицу больше (X2=X1+1)
3)если предыдущие случаи неверны (прямое копирование).
В первом максимум скопированных байт составляет 64 байта (управляющие коды для распаковщика ($40h-$7Fh).
Во втором случае максимум скопированных байт составляет 16 байт (коды для распаковщика ($80-$8F).
В обоих этих случаях кодируемая цепочка кодируется в 2 байта (управляющий код|X1).
В третьем случае тоже максимум 16 байт (коды для распаковщика $F0-$FF).
В этом случае кодирование происходит так: управляющий код|N1N2N3...Nn, N1,N2,N3..Nn - копируемая цепочка. |
|
| Вернуться к началу |
|
|
Djinn
RRC2008
Зарегистрирован: 16.03.2004
Сообщения: 633
Откуда: Москва
|
| Добавлено: Ср Мар 28, 2007 3:17 pm Заголовок сообщения: |
|
|
| gottax писал(а): |
1)если следующий за проверяемым байтом байт равен ему (X2=X1)
2)если следующий за проверяемым байтом байт на единицу больше (X2=X1+1)
3)если предыдущие случаи неверны (прямое копирование).
В первом максимум скопированных байт составляет 64 байта (управляющие коды для распаковщика ($40h-$7Fh).
Во втором случае максимум скопированных байт составляет 16 байт (коды для распаковщика ($80-$8F).
В обоих этих случаях кодируемая цепочка кодируется в 2 байта (управляющий код|X1).
В третьем случае тоже максимум 16 байт (коды для распаковщика $F0-$FF).
В этом случае кодирование происходит так: управляющий код|N1N2N3...Nn, N1,N2,N3..Nn - копируемая цепочка. |
Здесь тоже три ветки. Но немножко не такие.
Если байт равен нулю, значит нужно повторить значение 00 количеством равным следующему байту раз.
Если равен FF, то после него идёт байт обозначающий, сколько раз нужно увеличить на единицу третий байт.
Остальные байты просто копируются.
Может чего упустил, всего не помню.
http://magicteam.emu-land.net/files/BJMaps.rar
Map - несжатый файл, rmp - сжатый. В map первые 2 байта - ширина и высота карты, при упаковке не учитываются. |
|
| Вернуться к началу |
|
|
gottax
Зарегистрирован: 16.11.2003
Сообщения: 588
Откуда: Курск
|
| Добавлено: Чт Мар 29, 2007 4:42 pm Заголовок сообщения: |
|
|
I did it!  Хотя конечный пакер сжимает хуже оригинального на 1-2%, мне этого более чем достаточно (изменённые данные будут сжиматься лучше). Пришлось здорово поломать голову над реализацией этого чёртового "flexible parsing"  Даже полностью переписал весь код с нуля. Но результат стоит того:)
Что любопытно, этот алгоритм сжимает свои данные (тайловые карты) даже лучше, чем хвалёные RAR и 7z  |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Чт Мар 29, 2007 10:16 pm Заголовок сообщения: |
|
|
| gottax писал(а): | | Что любопытно, этот алгоритм сжимает свои данные (тайловые карты) даже лучше, чем хвалёные RAR и 7z |
Наверное, данные плохо пакуются словарными методами (странно, что это за картинка, у которой мало повторяющихся элементов?) |
|
| Вернуться к началу |
|
|
CaH4e3
Зарегистрирован: 21.01.2004
Сообщения: 195
|
| Добавлено: Сб Мар 31, 2007 8:25 am Заголовок сообщения: |
|
|
Интересно, что же все-таки копает gottax ;))))
На счет "flexible" парсинга (если это можно тут так назвать ;)), тупой алгоритм RLE собирает все повторы и чередует их прямым копированием байтов. Но на участках где короткие серии повторов чередуются с короткими сериями разных байтов, при двухбайтовой схеме кодирования, происходят утечки.
Например, последовательность взятая отбалды:
Если начало каждой последовательности повторяющихся байт обозначить через 1, а последовательности разных байт через 0, то получится последовательность команд, по которым работает тупой пакер:
Пакер подсчитывает количество нулей или единиц, соответственно генерирует коды повторения байта, на который пришлась 1 в количестве равном количеству единиц плюс 1, и коды копирования последовательности тех байт, на которые приходятся нули.
| Код: | | (3) 1 2 3 (2) 2 (2) 3 (2) 2 1 |
В скобках указаны байты кода со счетчиками, таким образом данная последовательность (нетрудно подсчитать) в упакованном виде весит 11 байт (при том, что исходная весила 9). Эта разница, конечно, съедается за счет больших повторяющихся последовательностей. Но если исходные данные содержат много таких участков, размер упакованных данных вырастает довольно сильно.
Проблема, оказывается, разрешима, если пакер перестанет кодировать отдельные короткие последовательности, а будет просто целиком переносить их в упакованные данные. Если теперь в последовательности из нулей и единиц, сгенерированной выше тупым RLE алгоритмом, отметить нулевые коды, идущие сразу за 1 как 2, получим:
И теперь любая последовательность "0 1 2" показывает, что этот участок лучше не кодировать, а перенести как есть. То есть, каждая последовательность "0 1 2" просто заменяется на "0 0 0", причем заметьте, сравнение делается для каждого байта, так что "0 1 2 1 2" тоже превратится в "0 0 0 0 0". Обработанный таким образом массив кодов приобретает вид:
Что кодируется как:
| Код: | | (9) 1 2 3 2 2 3 3 2 1 |
Что весит уже не 11, а всего лишь 10 байт. ;) Иногда эта разница довольно существенна, особенно для ограниченного объема памяти картриджа NES. ;)
Вот, примерно, как может выглядеть код упаковки:
| Код: |
int encode(unsigned char *in_buf, unsigned char *out_buf, int data_size, int buf_size)
{
unsigned char *tmp_buf=malloc(data_size);
unsigned char data_byte, flushed_same=0, flushed_diff=0, last_byte, cur_byte;
unsigned int out_buf_pos=0, in_buf_pos=0, sequence_len, i;
// encode first pass
last_byte=0;
for (i=0; i<data_size; i++)
{
if (in_buf[i]!=in_buf[i+1])
cur_byte=0;
else
cur_byte=1;
if ((cur_byte==0)&&(last_byte==1))
tmp_buf[i]=2;
else
tmp_buf[i]=cur_byte;
last_byte=cur_byte;
}
// remove poor occurences
for (i=0; i<data_size; i++)
{
if ((tmp_buf[i]==0)&&(tmp_buf[i+1]==1)&&(tmp_buf[i+2]==2))
{
tmp_buf[i+1]=0;
tmp_buf[i+2]=0;
}
}
// encode second pass
while (in_buf_pos<data_size)
{
sequence_len=0;
if (tmp_buf[in_buf_pos]==0)
{
while ((tmp_buf[in_buf_pos+sequence_len]==0)&&(sequence_len<0x80)) sequence_len++;
out_buf[out_buf_pos++]=0x80|sequence_len;
for (i=0; i<sequence_len; i++)
out_buf[out_buf_pos++]=in_buf[in_buf_pos++];
}
else
{
while ((tmp_buf[in_buf_pos+sequence_len]!=2)&&(sequence_len<0x7E)) sequence_len++;
if (sequence_len<0x7E)
sequence_len++;
else
sequence_len=0x7E;
out_buf[out_buf_pos++]=sequence_len;
out_buf[out_buf_pos++]=in_buf[in_buf_pos];
in_buf_pos+=sequence_len;
}
}
out_buf[out_buf_pos++]=0xFF;
free(tmp_buf);
return out_buf_pos;
}
|
note: код 0х7F в пакере конами зарезервирован для дополнительного кода смены адреса PPU во время распаковки. Если картинка большая и должна быть распакована в несмежные тайловые окна (при горизонтальном мирроринге: 0x2000 и 0x2800) или просто может состоять из большого количества пустых мест, что, при ограниченной длине последовательности, легче кодировать одной командой переносса, чем несколькоими командами повтора байтов.
Хотя, если как следует разобраться, чем чаще появляются цепочки неодинаковых байт, тем больше добавляется лишних байт за счет команд кодера. Если не давать таким цепочкам плодиться, просто отбрасывая все повторяющиеся цепочки длиной в два байта (которые не увеличивают и не уменьшают размер, но зато рвут последовательность неповторяющихся байт), и считать их как неповторяющиеся байты, то результат бутдет абсолютно таким же и уже как и раньше - однопроходным. ;) |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Сб Мар 31, 2007 2:25 pm Заголовок сообщения: |
|
|
Выходит, в любом виде RLE-алгоритма flexible parsing не нужен?  |
|
| Вернуться к началу |
|
|
gottax
Зарегистрирован: 16.11.2003
Сообщения: 588
Откуда: Курск
|
| Добавлено: Сб Мар 31, 2007 2:51 pm Заголовок сообщения: |
|
|
| CaH4e3 писал(а): | | Интересно, что же все-таки копает gottax ))) |
Вообще-то, уже всё раскопано (а игра для SNES) Японские разработчики обожают оптимизировать то, что можно не оптимизировать (графика и относительно объёмистый текст хранятся в несжатом виде, а вот все тайловые карты пожаты). Причём усложнённым RLE с парсингом. Ну а я решил во что бы то ни стало перерисовать титульный экран
| CaH4e3 писал(а): | | Но на участках где короткие серии повторов чередуются с короткими сериями разных байтов, при двухбайтовой схеме кодирования, происходят утечки. |
Вот именно с такой проблемой я и столкнулся, написав первую версию своего пакера, без подобных проверок.
| CaH4e3 писал(а): | | Вот, примерно, как может выглядеть код упаковки |
Круто! У тебя код пакера гораздо проще и короче получился
Вообще, ты молодец, Санч, что подробно расписал, так как проблема с оптимизацией RLE- и LZ- подобных алгоритмов встречается в ромхакинге довольно часто. Многим эта информация очень пригодится.
| АнС писал(а): | | Выходит, в любом виде RLE-алгоритма flexible parsing не нужен? |
В таком виде, какой попался мне - очень даже нужен |
|
| Вернуться к началу |
|
|
CaH4e3
Зарегистрирован: 21.01.2004
Сообщения: 195
|
| Добавлено: Сб Мар 31, 2007 3:20 pm Заголовок сообщения: |
|
|
| Flexible parsing тут все-таки не совсем применимый термин. Он скорее относится преимущественно к lz77 алгоритмам, где опять же, вместо тупого собирания повторов, кодер перебирает несколько ближайших вариантов длин кодируемого участка данных, тем самым выбирая не всегда очевидные более выгодные последовательности. ;) |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Сб Мар 31, 2007 4:32 pm Заголовок сообщения: |
|
|
| Ну а мы, похоже, называем этим термином все случаи, где необходимо неким образом модифицировать алгоритм упаковки, который сжимает данные "в лоб" - модифицировать так, чтобы он периодически пытался отказаться от сжатия следующего байта/ряда байт, желая в перспективе сжать следующие байты гораздо лучше, чтобы в итоге вышел более выгодный вариант по сравнению со сжатием "в лоб". |
|
| Вернуться к началу |
|
|
|
|
Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
