Анализ недокументированных растровых форматов с алгоритмами RLE сжатия.

Всем известно, что в старых играх графика часто зажата простыми и быстрыми алгоритмами. Наиболее простым являются алгоритмы RLE.
Как «глазами» распознать RLE сжатие. Это отсутствие какой-либо таблицы упорядоченных байтов в заголовке изображения. Часто краевые одноцветные участки растра выглядят как двухбайтовые с ярко выраженным чередованием значений байтов.

В своих экспериментах по изучению недокументированных графических форматов я постепенно пришел к мысли о создании простого анализатора сжатия RLE с гибкой настройкой вариантов распаковки и компрессии изображения. Какие же наиболее универсальные и надежные настройки вариантов реализации возможны.
НАСТРОЙКИ РАСПАКОВКИ
1) Задание значения границы RepCode признака повторителя (для простоты примем классические 128 или 192, хотя может быть любой) (тип BYTE)
2) Что считать повторителем значения больше или меньше RepCode (тип параметра настройки – BOOLEAN, повторитель-неповторитель)
3) Вычисление значения байта-повторителя, как минимум учет ПРЯМОГО или ОБРАТНОГО порядка прочитанных значений (тип параметра настройки - BOOLEAN).
4) Вычисление значения байта-неповторителя, как минимум учет ПРЯМОГО или ОБРАТНОГО порядка прочитанных значений (тип параметра настройки - BOOLEAN).
5) Учет необходимости двухбайтового выравнивания при совпадении момента окончания цепочки байтов и окончании растровой строки (Пример: Alpha Storm – BIF формат)
6) Обмен байтов повторитель-цвет при особом значении прочитанного байта (это относится только к повторителю) (Пример: Alpha Storm – LIF, BIF)
7) Особая ситуация, когда читаемый байт равен RepCode, обычно его нужно просто пропускать. Но тут возможна масса падлянок. Я например сделал бы так. Если встречаем B=RepCode, то читаем следующий, интерпретируем его как цвет и добиваем до конца строки, и здесь таких примеров – масса, на сколько фантазия позволит.
8) Вариант не совсем оптимальной PCX реализации алгоритма RLE, когда то, что попало в класс неповторителя фактически является просто одиночным цветом.
9) Сканирование строки (КЛАССИЧЕСКОЕ/ЗМЕЙКА)

НАСТРОЙКИ СЖАТИЯ
1) Сжатие не непрерывного потока байтов, а построчного потока с учетом обрыва (окончания) каждой растровой строки (Colonia Project HUP –формат).

Даже принимая два состояния по каждому из перечисленных пунктов видно, что больше сотни (не менее 2^7) вариантов RLE такой подход перекрывает.
Анализатор будет работать очень просто. На входе файл Compressed image с заголовком по два байта – ширина и высота (часто их удается узнать), после идут сжатые байты. На выходе разжатые байты, получаются с переключением настроек и визуальным анализом по принципу «получилось-не получилось». Также проверка корректно разжатых байтов уже настраиваемым сжатием по тому же алгоритму с визуальным анализом результата. А отсутствие результата это тоже результат. По крайне мере резко сузит круг возможных кандидатов – алгоритмов, подобных RLE. Т.е задача – сделать гибко настраиваемый анализатор RLE сжатия с максимально обобщенным всевозможным охватом вариантов.
Мне нужна информация, подобного тому, что я описал, не было ранее создано, а то у меня ощущение, что изобретаю велосипед. Если такое приложение есть, то оно будет просто незаменимо при переводе старых игр. Я повторяю нужно приложение-просмотрщик не полных разжатых растров с различной глубиной представлением цвета, а сжатых растровых данных алгоритмами RLE.

 

RLE analizer v.0.1

Судя по отсутствию ответов на предыдущее сообщение, такого приложения действительно нет. Поэтому я уперся и сегодня сделал то, что пригодится очень многим, кто изучает растровые форматы старых игр. Пока приложение только анализирует и читает. В дальнейшем я добавлю дополнительные особые случаи при чтении и настройки компрессии для получения снова сжатых файлов. И конечно надо будет сделать импорт несжатых растров, тогда получится универсальный конвертер (туда-обратно) с очень гибкими и расширенными настройками компрессии-декопресии изображения.
Вот скриншот

Архив с приложением и файлами прилагается. Там все просто нажимай и смотри. Заранее благодарен за тестирование, отзывы и замечания

 

Думаю, это очень пригодится, когда руки дойдут до намеченного перевода Privateer 2. Так что заранее огромная благодарность за такой труд.

 

Постараюсь максимально нарастить настройки. Для этого нужно обмениваться разгаданными форматами. Но только, чтобы это были генетически RLE алгоритмы сжатия. Никаких хидеров из таблиц цветов. Только RLE.

 

WERTA, Это надо спросить Steel Rat-a, он уже начинал копаться в формате Приватера. RLE, но чем-то еще дополнительно сжатый.

 

RLE analizer v.0.2

За сегодня многое сделал новые настройки и динамическую генерацию кода декодирующей процедуры на паскале по одному нажатию кнопки. Процедуру можно вставлять сразу в свой код. Планирую еще вывод сишного кода. Прилагаю файл.

 

Спасибо, у меня давно валяется ряд игровых ресурсов в непонятных мне форматах, буду отписываться если что-то программкой удастся прожевать =)

 

Обновил приложение. Убрал баг со сменой ШИРИНА\ВЫСОТА. Добавил небольшой файл ARAB BARRACKS_S.bin из TZAR. Для него ничего не удалось подобрать. Но это даже к лучшему.

 

RLE analizer v.0.3

Обновляю приложение. Добавил гистограмму значений для сжатых байтов. Очень помогает понять загадки формата. Выкладываю.

 

Helmut, в Приватёре 2 алгоритмы декомпрессии уже все известны. Сжатие ресурсов либо zip, либо тем же способом, что аудио файлы. А вся графика сжата RLE алгоритмом, который почти не изменился со времён первого Wing Commander (изменения были сделаны для работы с данными больше 64К).

Лирическое отступление. У меня тупо нет возможности доделывать. Помнится после рождения первого сына я на сайте почти не появлялся целый год. Сейчас с появлением на сайте проще, а вот с написанием прог не ради денег тяжелее.

WERTA, кстати, тоже думал подобный анализатор делать в GBS. Но... В общем лирическое отступление уже было.

 

Рискну предложить выкладывать здесь по определенным правилам форматы с учетом следующих требований
1. Цветность 1 байт.
2. Отсуствие необходимости в таблице и самой таблицы перекодировки цветов в заголовке.
3. Происхождение от принципов алгоритма RLE
И лучше выкладывать листинг такой же процедуры (С++, Pascal, и др.), что выводит RLE analizer.
Это поможет мне быстрее понять алгоритм, и по возможности систематизировать его для вставки в программу. Хотя че-то я сник, поскольку все алгоритмы в рамках своего подхода я не смогу объять.

 

Жуткий код, писал год назад. Страшно смотреть. Мне стыдно перед самим собой. =)
Вот.

Код:

void ShpDlg::Unpack(unsigned char *dest, unsigned char *src, unsigned int *maxx, unsigned int *maxy, unsigned char back)
{
    unsigned int offset=0, pos=0;
    unsigned short x, y, xx, yy;
    signed short code, length;
    signed short cx, cy;
    unsigned char repeat, color;
    switch (mType)
    {
        //case ShapeType::IFFChunk:
        case ShapeType::PAKFile:
        offset+=8;
        break;
    }
    memcpy(&x, src + offset, 2);
    memcpy(&xx, src+2 + offset, 2);
    memcpy(&yy, src+4 + offset, 2);
    memcpy(&y, src+6 + offset, 2);
    *maxx = x + xx + 1;
    *maxy = y + yy + 1;
    mainX = x;
    mainY = y;
    corrX = xx;
    corrY = yy;
    currentChanged = false;
    //wxMessageBox(wxString::Format("Main X: %d, Y: %d; corrections: XX: %d, YY: %d; Width: %d, Height: %d", x, y, xx, yy, width, height));
    color = back;
    memset(dest+pos, color, *maxy**maxx);
    offset += 8;
    while ((signed short *) (src+offset) !=0)
    {
        memcpy(&code, src+offset, 2);
        if (code==0) break;
        offset+=2;
        memcpy(&cx, src+offset, 2);
        offset+=2;
        memcpy(&cy, src+offset, 2);
        offset+=2;
        cx += xx;
        cy += yy;
        pos=(cy * (*maxx)) + cx;
        length=code >> 1;
        //if (code>127) wxMessageBox(wxString::Format("%X, %d, %d, length: %d, pos: %d", code, cx, cy, length, pos));
        //
        if (!(code & 1))
        {
            memcpy(dest + pos, src + offset, length);
            offset+=length;
            pos+=length;
            continue;
        };
        while (length>0)
        {

            memcpy(&repeat, src+offset, 1);
            ++offset;
            if (repeat & 1)
            {
                repeat>>=1;
                memcpy(&color, src+offset, 1);
                ++offset;
                memset(dest+pos, color, repeat);
            }
            else
            {
                repeat >>= 1;
                memcpy(dest+pos, src+offset, repeat);
                //wxMessageBox(wxString::Format("Long repeat: %d", repeat));
                offset+=repeat;
            }
            pos+=repeat;
            length-=repeat;
        }
        // WHILE LENGTH > 0
    }
    SetLabel(wxString::Format("Main X: %d, Y: %d; corrections: XX: %d, YY: %d; Width: %d, Height: %d, size: %d", mainX, mainY, corrX, corrY, width, height, offset));
    // WHILE NOT DONE
}

 

Ну а мне тяжело признаться, что я только недавно начал осваивать C, и моих крайне скудных знаний не хватает вообще чтобы понять что в листинге от Sreel Rat написано. Может как-то по-другому можно объяснить, блок-диаграммой что-ли. Если это обычный RLE, то он уже есть по умолчанию в программе.

 

WERTA, ща напишу.

Первые 8 байт - это четыре 16-битных целых со знаком, shortint т.е.

Там может быть X: 319 CX: 0 CY: 0 Y: 199 - это 320х200 с началом отсчёта в верхнем левом углу, а может 15 16 16 15 - 32х32 с началом отсчёта в середине.

width = X + CX
height = Y + CY

:цикл1
Далее берём "код" - 16 бит
Потом ещё два шортинта _X, и _Y.
Переходи в буфере картинки к координате _X + CX, _Y + CY

Если "код" равен 0 - конец данных.
Длина строки в этом блоке, len, равна "код" shr 1.
если младший бит "кода" равен 1 (641, например)
{
копируем len байт из источника в буфер картинки
goto цикл1
}
:цикл2
берём из источника "код2" - 8 бит
len2 = "код2" shr 1
если младший бит "код2" равен 1
{
берём из источника "цвет"
копируем "цвет" в буфер картинки len2 раз
}
иначе
{
копируем из источника len2 байт в буфер картинки
}
len = len - len2
если len не равна 0 goto цикл2
goto цикл1

 

Добавил информацию в статус баре. Обновленную версию прилагаю

 

Специально добавил случай отсуствия сжатия. Обновляю.
For Steel rat

Скелет главного цикла алгоритма чтения RLE в этой программе такой

Код:

[FONT="Courier New"]   
repeat
      B:=CompressedBytes[ByteIndex];

      {СПЕЦИАЛЬНЫЙ СЛУЧАЙ}
      if B=SpecialCode then begin
          {ТУТ ХИМИЧИМ}
          goto L1;  
      end;

      {СЛУЧАЙ ПОВТОРИТЕЛЕЙ}
      if B>RepeatCode then begin
          {ТУТ ХИМИЧИМ}
          goto L1;  
      end;

      {СЛУЧАЙ СЧЕТЧИКОВ НЕПОВТОРЯЮЩИХСЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ}
      if B<RepeatCode then begin
          {ТУТ ХИМИЧИМ}
         goto L1;  
      end;

      {ОСОБЫЙ СЛУЧАЙ РАВЕНСТВА КОДУ ПРИЗНАКУ ПОВТОРИТЕЛЕЙ}
      if B=RepeatCode then begin
          {ТУТ ХИМИЧИМ}
         goto L1;
      end;
   L1:            
   inc(ByteIndex);
until (ByteIndex>NCompressedBytes-1) or (PixelCounter>=W*H);[/FONT]

Другой алгоритм, если он выпадает из этой схемы (а это классическая схема RLE) получается не реализуемым. Я так и не понял твой код. Можно ли твой алгоритм представить в такой архитектуре ?

 

Разжать файл не забыл предварительно?

 

Не разжимал, а нашел предположтельное начало байтов и нашел также предположительные ширину и высоту, привел к виду WIDTH(2Bt),HEIGHT(2Bt),BYTES...., но ничего не получил. Так быстро этого не сделать. Нужно четко знать место начала байтов, четко знать хотя бы ширину изображения ну и в конечном итоге знать что же мы долны увидеть, а вдруг что-то совсем иное .

 

Это, конечно, сумашествие, но в RLE можно сжимать и картинки не 8-ми или 4-х битные. "Среднестатистическая" картинка не содержит чересчур много разных чередующихся пикселей. Особенно, если это края картинки. Поэтому, эффективно (по скорости) сжимать, например, 24-х, или 32-х битные картинки можно - группируя байты пикселей. Для 24-х битного, например: берём строку, разделяем одинаковые цветовые байты каждого пикселя, получаем 3 8-ми битных массива, которые и сжимаем, как обычно.
Техника чёкнутая, сказать ничего больше не могу , как и о её применении где-либо.

---------- Сообщение добавлено в 09:22 ---------- Предыдущее сообщение размещено в 09:18 ----------

Э-э-э, точнее, не могу сказать применяется ли *в играх*. А так, я когда-то её использовал чуть-чуть, но, думаю, это было изобретение очередного колеса.

 

Там файлы пожаты LZSS.