Сегодня я хочу рассказать о замечательной библиотеке zlib.

Мне, как программисту игрушек, раньше приходилось решать проблему быстрой распаковки ресурсов при загрузке игровых уровней. Самое неприятное, что может принести игра пользователю, кроме падения и ошибок, это заставить его долго ожидать загрузки уровня (хотя 10-15 лет назад загрузка одного уровня по 5-10 минут было совершенно нормальным явлением).

Впервые в жизни мне пришлось столкнуться с компрессией данных в игре «Петрович и все, все, все», которую мы делали в Trickster Games для Андрея Бильжо.

Все изображения в игре используют от двух до десяти цветов (а музыка восемь нот, ага). Вот пример:

На этом скриншоте присутствуют: Петрович (два цвета), Инопланетянин aka «логотип Trickster Games» (2 цвета), фон (4 цвета). Каждое изображение может занимать от 256 килобайт до 4-х мегабайт (потому что DDS). Загрузка одного уровня, состоявшего из 50-200 таких изображений, занимала от 10 до 45 секунд. Разумеется, это нас в корне не устраивало.

После мозгового штурма на эту тему было найдено решение — использовать алгоритм RLE. Этот алгоритм позволяет очень эффективно сжимать длинную цепочку одинаковых бит, что наглядно показано в википедии: блок данных «AAAAAAAAAAAAAAABBBBBC» мы записываем вот так «15A5BC». Экономия, как говорится, налицо.

Интерфейс для работы с этим алгоритмом был выбран очень простой. Как оказалось впоследствии, такой интерфейс с мелкими различиями предоставляют практически все библиотеки сжатия без потерь.

/* Сжимает данные из буфера src в dst.
 * src - входной буфер
 * srcSize - размер входного буфера в байтах
 * dst - выходной буфер
 * dstSize - перед вызовом должен быть установлен в размер буфера dst, 
 *     после вызова туда записывается реальное количество сжатых байт
 *
 * Функция возвращает true, если данные были сжаты успешно 
 * (это значит, что уровень сжатия меньше или равен единице)
 */
bool compressRLE( void *dst, int *dstSize, const void *src, int srcSize);
 
/* Расжимает данные из буфера src в dst.
 * src - входной буфер
 * srcSize - размер входного буфера в байтах
 * dst - выходной буфер
 * dstSize - перед вызовом должен быть установлен в размер буфера dst, 
 *     после вызова туда записывается реальное количество распакованных байт
 *
 * Функция возвращает true, если данные были расжаты успешно 
 */
bool uncompressRLE( void *dst, int *dstSize, const void *src, int dstSize);

Разумеется, я не могу показать нашу реализацию алгоритма без разрешения начальства, но, думаю, вы справитесь сами. Коэффициент сжатия на наших данных составлял где-то 0.01 процента (то есть тысяча байт сжимались в десять).

..И тут мы плавно переходим к zlib.

Библиотека zlib используется практически везде, где есть CPU: мобильные телефоны, компьютеры, микроволновки, современные автомобили, телевизоры — список можно продолжать бесконечно. Кто знает, может она сейчас трудится на Марсе внутри ровера Curiosity, сжимая, передаваемые на Землю, данные.

Библиотека может сжимать блок данных или поток. Рассмотрим вкратце сжатие блока данных. Описание метода вот такое:

// Сжимает данные методом deflate из буфера src в dst
// dest - выходной буфер
// destLen - размер выходного буфера (после удачного сжатия 
//     сюда сохраняется размер сжатых данных)
// source - входной буфер
// sourceLen - размер входного буфера
// Возвращает Z_OK в случае удачи, записывает размер сжатых данных в destLen
ZEXTERN int ZEXPORT compress OF((Bytef *dest,   uLongf *destLen,
                                 const Bytef *source, uLong sourceLen));

Пример вызова этой функции. Он ничего полезного не делает, просто для наглядности.

#include <zlib.h>
#include <memory.h>
#include <stdio.h>
 
#define SRC_SIZE 512
#define DST_SIZE 512
 
int main()
{
    // Входной буфер размером SRC_SIZE
    unsigned char source[SRC_SIZE];
    // Тут мы будем хранить размер входного буфера 
    // (переменная просто для наглядности)
    const unsigned long sourceLen = SRC_SIZE;
    // Выходной буфер
    unsigned char dest[DST_SIZE];
    // Размер выходного буфера
    unsigned long destLen = DST_SIZE;
 
    // Будем сжимать буфер забитый нулями
    memset(source, 0, SRC_SIZE * sizeof(source[0]));
 
    if (Z_OK == compress(dest, &destLen, source, sourceLen))
    {
        // Все успешно
        printf("Compress ratio: %.2f\n", destLen/(float) sourceLen);
    }
    else
    {
        // Тут можете разобрать код ошибки и вывести более подробную информацию
        printf("Compress failed\n");
    }
 
    return 0;
}

Пример сжатия потока данных вы можете посмотреть в маленькой утилитке zpipe.

Есть вопросы? Спрашивайте, не стесняйтесь.

P.S. Если вы дочитали досюда, рекомендую изучить libdeflate.