Эксперимент - сжатие frm файлов алгоритмом RLE

[stratego]

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

Для начала, самый простой вариант, он есть во многих старых играх из девяностых, и даже в начале двухтысячных... Суть. Находим последовательность нулевых байт и вместо них записываем значение, одним байтом. Цветовые пиксели пишутся без изменений (то есть они не сжимаются вовсе). Но это самый простой вариант. Он реализован в игре Рыцари чести и других играх (везде по своему, но суть одна и та же).

Алгоритм выглядит так:

for(size_t t = 0; t < fileSize; )
{
    uint8_t col = inBuffer[t];
    size_t len = 1;

    if(col == 0) // --- ВАРИАНТ 1: ПРОПУСК (только для нулей) ---
    {
        while(t + len < fileSize && inBuffer[t + len] == 0 && len < 127)
            len++;

        outBuffer[out++] = (uint8_t)len; // Пишем только длину (0-127)
    }
    else // для любых цветов
    {
        // Ищем цепочку НЕ нулей (чтобы скопировать их как есть)
        while(t + len < fileSize && inBuffer[t + len] != 0 && len < 127)
            len++;

        outBuffer[out++] = (uint8_t)len | 128; // Флаг 128 + длина
        
        // Копируем сами данные (теперь без опечаток)
        for(size_t i = 0; i < len; i++)
            outBuffer[out++] = inBuffer[t + i];
    }
    t += len; 
}

На сам алгоритм. Взял для теста, случайный файл с персонажами, проверил результат :

Цитата

Open file: nmcmbtaa.frm  134625 b
Size File: 118805 b

Сжали на 12%, это далеко до архиваторов, но мы же пока ничего и не сделали по сути,поджали прозрачность. В добавок у нас не используется значение ноль, в наших командах, а можно выдать ему значение в 255 например, и кодировать нулём последовательность из 255 прозрачных пикселей. Что на некоторых файлах даст значительный выигрыш. 7zip сжал этот же файл до 23773 байт, вот попробуем подойти к этому значению.

Изменено 9 апреля пользователем stratego
Нашёл ошибку в коде

[stratego]

Утром допустил ошибку в коде, исправил. Прогнал тест, вышло после сжатия 87 295 байт , так что выше 30% сжатия получилось на самом деле...

[stratego]

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

Стены, анимация персонажей. Это как правило не очень длинные цепочки цветных пикселей, зажатых между блоками прозрачных. Вот пример:

Цитата

0E 1F CF 0F 0F CA CF CF CF CA 64 CF 1F CF 4E 53 4B 4E 4B 64 CF 1F CC

CF (207 цвет) встречается чаще, но есть одна не прерывная серия из трёх одинаковых пикселей подряд. В нншем пока что текущем варианте, эти 23 байта займут 24 байта, если реализовать заливку. То будет так 1(команда) + 0E 1F CF 0F 0F CA + 1(команда заливки) + CF (Два СF мы удаляем) + 1(команда) + CA 64 CF 1F CF 4E 53 4B 4E 4B 64 CF 1F CC = 24 байта. 

Была мысль, сделать заливку всей последовательности и вставить, в нужные места весь этот разнобой, но такая схема займёт еще больше места...

Родилась третья идея. Сделать команду битовой маски + счётчик сколько бит использовать. Принцип такой для этой строки будет XXXAXXXAAA.... и так далее. Допустим 1 - в бите это будет X, а если 0 то это A. A - CF (всегда 207 цвет), ну а Х это символ  из строки, берутся по очереди. Но есть и плохая новость, нам на строку в 23 байта, надо 23 бита маски, а это еще три байта. Тогда наша строка станет выглядеть так : 1(команда) + 3(маска) + СF(указываем один раз) + 16 (остальные другие байты по порядку) = 21 байт. Сжатие получилось. Но я пока не придумал, как это в код воплотить, ну и 2 байта экономии с 23... Маловато будет!!! Маловато!!! (С)

Еще интересное наблюдение, как правило с такие куски, с преобладанием одного цвета, идут в нескольких кусках подряд. Можно попробовать сделать, чтобы базовый цвет один раз указывался, но это нам всё равно даст не много экономии, в таких строчках...

[stratego]

Я даже не думал, что столько всяких идей у меня возникнет. Что прикрутить, даже не знаю. Что выбрать в процессе сжатия, тоже трудный вопрос, не пробовать же во время сжатия все возможные комбинации )) 

Решил провести тесты, открыл папку Critters, в одном из модов (4 767 объектов).

Общее количество последовательностей из нулей (от 1го и длиннее): 9137876.

Общее количество последовательностей из любого другого цвета (от 3): 3337578.

Причём для прозрачных пикселей самая длинная цепочка составила, аж 25473, это 200 байт надо чтобы закодировать, тем вариантом, что сейчас есть. Думаю, ввести вариант 15 битного счётчика, для нулевых последовательностей.

А для обычных цветов, всё скромнее 2719, самая длинная, это файл mawaspna.frm (чёрно зелёный). Для таких файлав идея появилась, менять цвет прозрачности на чёрный (очень тёмно зелёный 100), там из нулевых последовательностей, только данные в заголовке... Вариант с чередованием двух цветов (шахматка), встречается: 496959 раз, рекорд аж до 57 символов... Еще протестировал цепочки, по два символа, например ААББККММ ... Самая длинная 16 , Двойки встречаются часто, считал от 2 двоек и длиннее: 208778 раз, тоже не плохо. Но чтобы их описать, на каждую двойку надо сохранять 1 символ. Не высокая эффективность...

[stratego]

Реализовал самое простое, при нахождении длинной последовательности нулей, ставим маркер и загоняем длинну этой последовательности в 16 битный счётчкик, для нормальных файлов игры 65 536, можно его увеличить еще на 128 значений, ведь первые 127 значений и 0, мы задействовали в 1 байтовой схеме )) Но это мелочи, которые встретятся один раз на 200 файлов. Но всё равно приятно:

Open file: marobbbl.frm  1662592 b
Size File: 248117 b
 

Понятное дело, для этого теста я взял, файл с длинными кусками прозрачности, и результат в 6,7 раз (правда и тут меня уделал пока что 7zip, он сжал этот файл до 108785 байт). Но мы пока только прозрачность сжали. В этом файле есть еще 13104 последовательностей одинаковых пикселей, от 2 до 82. Но среднее всего пять Значит эту часть сожмем примерно в 4 раза, там еще дубли есть и шахматка. Про битовые маски, я еще и не придумал и не анализировал.

 

Код упаковки:

 for(size_t t = 0; t < inSize; )
    {
        uint8_t col = inBuffer[t];
        size_t len = 1;

        if(col == 0) // --- ВАРИАНТ 1: ПРОПУСК (только для нулей) ---
        {
            for(; (len + t) < inSize; len++)
                if(len == 0xFFFF || inBuffer[len +t] != 0) break;
            if(len < 128)
                workBuffer[workSize++] = (uint8_t)len; // Пишем только длину (1-127)
            else
            {
                // Ставим маркер 16 битного счётчика и упаковываем число
                workBuffer[workSize++] = 0;
                workBuffer[workSize++] = uint8_t(len >> 8);
                workBuffer[workSize++] = uint8_t(len & 0xFF);
            }
        }
        else // для любых цветов
        {
            // Ищем цепочку НЕ нулей (чтобы скопировать их как есть)
            for(; (len + t) < inSize; len++)
                if(len == 127 || inBuffer[len +t] == 0) break;

            workBuffer[workSize++] = (uint8_t)len | 128; // Флаг 128 + длина

            // Копируем сами данные (теперь без опечаток)
            for(size_t i = 0; i < len; i++)
                workBuffer[workSize++] = inBuffer[t + i];
        }
        t += len;
    }

 

Код распаковки:

Спойлер

   size_t inPos = 0;
    size_t len = 0;
    //size_t outPos = 0;
    //while (inPos < workSize)
    while (inPos < workSize)
    {
        uint8_t cmd = workBuffer[inPos++];
        if (cmd < 128)
        {
            len = cmd;
            if(cmd == 0)
                len = (workBuffer[inPos++] << 8) | (workBuffer[inPos++]);

            // Пропуск (нули)
            for (size_t i = 0; i < len; i++)
                outBuffer[outSize++] = 0;
        }
        else
        {
            // Повтор цвета
            int len = cmd & 0x7F;
            //uint8_t color = outBuffer[inPos++];
            for (int i = 0; i < len; i++)
                    outBuffer[outSize++] = workBuffer[inPos++];
        }
    }