Эксперимент - сжатие 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 байт, вот попробуем подойти к этому значению.

Изменено Четверг в 11:35 пользователем 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... Маловато будет!!! Маловато!!! (С)

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