Современные форматы кодирования изображений — это настоящая магия, в которой не разобраться без нескольких лет погружения в специфические алгоритмы. Даже опенсорсные форматы содержат настоящее спагетти навороченных и хитроумных методов типа алгоритма Хаффмана и дискретно-косинусного преобразования — результат нескольких десятилетий развития компьютерной науки.
Поскольку польский разработчик Доминик Шаблевски вообще не разбирается в кодировании изображений, то он написал примитивный метод сжатия изображений без потери качества всего в 300 строчек кода, на базовой математике. Результат его очень удивил.
Оказалось, что этот простой метод по скорости на порядок превосходит популярные кодеки libpng и stbi.
Доминик Шаблевски назвал формат Quite OK (Quite OK Image), то есть «вполне достаточное» качество и размер. Другими словами, он конкретно заточен именно на скорость. Во многих случаях — при пакетной обработке большого количества файлов, в автоматических конвейерах — скорость является ключевым фактором.
Автор считает свой алгоритм до глупости простым. Он берёт изображения RGB и RGBA — и кодирует их в формат QOI размером с обычный PNG, но гораздо быстрее. Всё в один поток, без SIMD.
В своём блоге Доминик описывает нехитрую технику сжатия. Изображение кодируется в один проход, каждый пиксель считывается только один раз и кодируется одним из четырёх методов, по порядку:
- Если пиксель равен предыдущему, увеличивается счётчик по типу кодирования повторов (RLE). Если нет, то применяется метод 2, и так далее
- Пиксель из массива 64 последних по «хешу»
r^g^b^a
- Разница с предыдущим пикселем, если она небольшая
- Полное значение RGBA
Результирующие значения записываются в группы с указанием сначала тега (метод кодирования), после которого идут биты. Все группы выровнены по байтам для ускорения доступа в памяти.
Вот и всё.
Для сравнения, ниже результаты сжатия скриншотов нескольких сайтов. Использовались библиотеки libpng, stbi и qoi. Указан размер каждого скриншота, время кодирования, время декодирования, скорость кодирования/декодирования в мегапикселях в секунду и размеры итоговых файлов. Тесты проводились на процессоре Intel i7-6700K.
Бенчмарки
/screenshots/news.ycombinator.com.png: 1325x1450 decode ms encode ms decode mpps encode mpps size kb libpng: 8.6 79.9 223.22 24.03 289 stbi: 6.0 157.4 319.14 12.21 333 qoi: 3.0 3.8 649.95 502.49 288 /screenshots/reddit.com.png: 1313x8008 decode ms encode ms decode mpps encode mpps size kb libpng: 72.4 754.0 145.23 13.95 2821 stbi: 43.3 990.1 243.06 10.62 3927 qoi: 25.2 31.8 417.56 330.15 3083 /screenshots/nytimes.com.png</a>: 1313x5780 decode ms encode ms decode mpps encode mpps size kb libpng: 53.2 575.6 142.75 13.18 2672 stbi: 36.5 700.7 207.79 10.83 3377 qoi: 17.4 23.1 436.58 327.94 2820 /screenshots/phoboslab.org.png</a>: 1313x20667 decode ms encode ms decode mpps encode mpps size kb libpng: 116.4 1452.2 233.03 18.69 6199 stbi: 80.8 1861.0 335.93 14.58 7421 qoi: 57.7 79.2 470.43 342.82 8337 /screenshots/microsoft.com.png</a>: 1313x3328 decode ms encode ms decode mpps encode mpps size kb libpng: 28.7 356.7 152.36 12.25 1518 stbi: 20.8 413.0 210.03 10.58 2030 qoi: 10.2 14.3 429.00 306.57 1701 /screenshots/cnn.com.png</a>: 1313x5241 decode ms encode ms decode mpps encode mpps size kb libpng: 36.2 457.2 189.96 15.05 2246 stbi: 30.7 613.9 224.44 11.21 2729 qoi: 14.4 20.2 478.56 340.84 2449 /screenshots/sublime.png</a>: 1008x9513 decode ms encode ms decode mpps encode mpps size kb libpng: 38.4 405.6 249.44 23.64 1579 stbi: 29.5 761.8 325.20 12.59 1858 qoi: 16.9 20.5 568.14 468.58 1538 /screenshots/amazon.com.png</a>: 1313x6097 decode ms encode ms decode mpps encode mpps size kb libpng: 67.3 843.0 118.97 9.50 4589 stbi: 58.1 841.4 137.84 9.51 6014 qoi: 24.7 36.3 323.62 220.51 5382 /screenshots/imdb.com.png</a>: 1313x6441 decode ms encode ms decode mpps encode mpps size kb libpng: 43.3 535.0 195.43 15.81 2264 stbi: 37.3 761.0 226.62 11.11 3053 qoi: 17.9 23.0 472.10 367.12 2541 /screenshots/duckduckgo.com.png</a>: 1313x2874 decode ms encode ms decode mpps encode mpps size kb libpng: 12.7 146.3 297.73 25.80 333 stbi: 8.8 300.3 427.03 12.57 436 qoi: 5.0 6.8 755.00 558.83 330 /screenshots/en.wikipedia.org.png</a>: 1313x2936 decode ms encode ms decode mpps encode mpps size kb libpng: 21.7 227.7 177.59 16.93 1342 stbi: 15.2 317.3 253.86 12.15 1497 qoi: 8.4 11.9 460.19 325.07 1547 /screenshots/apple.com.png</a>: 1313x4755 decode ms encode ms decode mpps encode mpps size kb libpng: 33.1 427.8 188.47 14.59 1941 stbi: 27.5 556.7 227.34 11.21 2575 qoi: 13.2 18.6 474.51 335.93 2157 /screenshots/stripe.com.png</a>: 1313x6603 decode ms encode ms decode mpps encode mpps size kb libpng: 40.8 411.5 212.45 21.07 1054 stbi: 24.4 691.6 354.68 12.54 1428 qoi: 16.2 19.4 535.20 447.23 1386
Как видим, размер итоговых файлов QOI обычно между libpng и stbi, а скорость намного выше. Разница в сжатии составляет 20−50 раз, в декомпрессии — 3−4 раза.
В среднем по всем скриншотам:
decode ms encode ms decode mpps encode mpps size kb libpng: 44.1 513.3 186.80 16.04 2219 stbi: 32.2 689.7 255.47 11.93 2821 qoi: 17.7 23.8 465.18 346.52 2582
Результаты остальных бенчмарков см. здесь. Набор тестовых изображений для проверки: images.tar, ~308 МБ.
Разумеется, QOI можно рекомендовать только для внутреннего использования во внутренних конвейерах обработки изображений, потому что никакие браузеры, да и вообще никто его ещё не поддерживает. Но он отлично подходит для внутреннего хранения картинок без потери качества, если главным фактором является скорость.
Доминик Шаблевски считает, что разработчики форматов сжатия в основном думают об уровне сжатия, размере файлов. Мало кто ставит на первое место именно скорость и простоту кодека. Поэтому в сообществе есть некоторая потребность в суперпростом и быстром кодеке. Может, он кому-то пригодится.
Теоретически, кодек можно приспособить для супербыстрого сжатия видео (без потерь) на примитивных микросхемах.
Код qoi.h
// Header - Public functions
#ifndef QOI_H
#define QOI_H
#ifdef __cplusplus
extern "C" {
#endif
// A pointer to qoi_desc struct has to be supplied to all of qoi's functions. It
// describes either the input format (for qoi_write, qoi_encode), or is filled
// with the description read from the file header (for qoi_read, qoi_decode).
// The colorspace in this qoi_desc is a bitmap with 0000rgba where a 0-bit
// indicates sRGB and a 1-bit indicates linear colorspace for each channel. You
// may use one of the predefined constants: QOI_SRGB, QOI_SRGB_LINEAR_ALPHA or
// QOI_LINEAR. The colorspace is purely informative. It will be saved to the
// file header, but does not affect en-/decoding in any way.
#define QOI_SRGB 0x00
#define QOI_SRGB_LINEAR_ALPHA 0x01
#define QOI_LINEAR 0x0f
typedef struct {
unsigned int width;
unsigned int height;
unsigned char channels;
unsigned char colorspace;
} qoi_desc;
#ifndef QOI_NO_STDIO
// Encode raw RGB or RGBA pixels into a QOI image and write it to the file
// system. The qoi_desc struct must be filled with the image width, height,
// number of channels (3 = RGB, 4 = RGBA) and the colorspace.
// The function returns 0 on failure (invalid parameters, or fopen or malloc
// failed) or the number of bytes written on success.
int qoi_write(const char *filename, const void *data, const qoi_desc *desc);
// Read and decode a QOI image from the file system. If channels is 0, the
// number of channels from the file header is used. If channels is 3 or 4 the
// output format will be forced into this number of channels.
// The function either returns NULL on failure (invalid data, or malloc or fopen
// failed) or a pointer to the decoded pixels. On success, the qoi_desc struct
// will be filled with the description from the file header.
// The returned pixel data should be free()d after use.
void *qoi_read(const char *filename, qoi_desc *desc, int channels);
#endif // QOI_NO_STDIO
// Encode raw RGB or RGBA pixels into a QOI image in memory.
// The function either returns NULL on failure (invalid parameters or malloc
// failed) or a pointer to the encoded data on success. On success the out_len
// is set to the size in bytes of the encoded data.
// The returned qoi data should be free()d after use.
void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len);
// Decode a QOI image from memory.
// The function either returns NULL on failure (invalid parameters or malloc
// failed) or a pointer to the decoded pixels. On success, the qoi_desc struct
// is filled with the description from the file header.
// The returned pixel data should be free()d after use.
void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels);
#ifdef __cplusplus
}
#endif
#endif // QOI_H
// -----------------------------------------------------------------------------
// Implementation
#ifdef QOI_IMPLEMENTATION
#include <stdlib.h>
#ifndef QOI_MALLOC
#define QOI_MALLOC(sz) malloc(sz)
#define QOI_FREE(p) free(p)
#endif
#define QOI_INDEX 0x00 // 00xxxxxx
#define QOI_RUN_8 0x40 // 010xxxxx
#define QOI_RUN_16 0x60 // 011xxxxx
#define QOI_DIFF_8 0x80 // 10xxxxxx
#define QOI_DIFF_16 0xc0 // 110xxxxx
#define QOI_DIFF_24 0xe0 // 1110xxxx
#define QOI_COLOR 0xf0 // 1111xxxx
#define QOI_MASK_2 0xc0 // 11000000
#define QOI_MASK_3 0xe0 // 11100000
#define QOI_MASK_4 0xf0 // 11110000
#define QOI_COLOR_HASH(C) (C.rgba.r ^ C.rgba.g ^ C.rgba.b ^ C.rgba.a)
#define QOI_MAGIC \
(((unsigned int)'q') << 24 | ((unsigned int)'o') << 16 | \
((unsigned int)'i') << 8 | ((unsigned int)'f'))
#define QOI_HEADER_SIZE 14
#define QOI_PADDING 4
typedef union {
struct { unsigned char r, g, b, a; } rgba;
unsigned int v;
} qoi_rgba_t;
void qoi_write_32(unsigned char *bytes, int *p, unsigned int v) {
bytes[(*p)++] = (0xff000000 & v) >> 24;
bytes[(*p)++] = (0x00ff0000 & v) >> 16;
bytes[(*p)++] = (0x0000ff00 & v) >> 8;
bytes[(*p)++] = (0x000000ff & v);
}
unsigned int qoi_read_32(const unsigned char *bytes, int *p) {
unsigned int a = bytes[(*p)++];
unsigned int b = bytes[(*p)++];
unsigned int c = bytes[(*p)++];
unsigned int d = bytes[(*p)++];
return (a << 24) | (b << 16) | (c << 8) | d;
}
void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len) {
if (
data == NULL || out_len == NULL || desc == NULL ||
desc->width == 0 || desc->height == 0 ||
desc->channels < 3 || desc->channels > 4 ||
(desc->colorspace & 0xf0) != 0
) {
return NULL;
}
int max_size =
desc->width * desc->height * (desc->channels + 1) +
QOI_HEADER_SIZE + QOI_PADDING;
int p = 0;
unsigned char *bytes = QOI_MALLOC(max_size);
if (!bytes) {
return NULL;
}
qoi_write_32(bytes, &p, QOI_MAGIC);
qoi_write_32(bytes, &p, desc->width);
qoi_write_32(bytes, &p, desc->height);
bytes[p++] = desc->channels;
bytes[p++] = desc->colorspace;
const unsigned char *pixels = (const unsigned char *)data;
qoi_rgba_t index[64] = {0};
int run = 0;
qoi_rgba_t px_prev = {.rgba = {.r = 0, .g = 0, .b = 0, .a = 255}};
qoi_rgba_t px = px_prev;
int px_len = desc->width * desc->height * desc->channels;
int px_end = px_len - desc->channels;
int channels = desc->channels;
for (int px_pos = 0; px_pos < px_len; px_pos += channels) {
if (channels == 4) {
px = *(qoi_rgba_t *)(pixels + px_pos);
}
else {
px.rgba.r = pixels[px_pos];
px.rgba.g = pixels[px_pos+1];
px.rgba.b = pixels[px_pos+2];
}
if (px.v == px_prev.v) {
run++;
}
if (
run > 0 &&
(run == 0x2020 || px.v != px_prev.v || px_pos == px_end)
) {
if (run < 33) {
run -= 1;
bytes[p++] = QOI_RUN_8 | run;
}
else {
run -= 33;
bytes[p++] = QOI_RUN_16 | run >> 8;
bytes[p++] = run;
}
run = 0;
}
if (px.v != px_prev.v) {
int index_pos = QOI_COLOR_HASH(px) % 64;
if (index[index_pos].v == px.v) {
bytes[p++] = QOI_INDEX | index_pos;
}
else {
index[index_pos] = px;
int vr = px.rgba.r - px_prev.rgba.r;
int vg = px.rgba.g - px_prev.rgba.g;
int vb = px.rgba.b - px_prev.rgba.b;
int va = px.rgba.a - px_prev.rgba.a;
if (
vr > -17 && vr < 16 &&
vg > -17 && vg < 16 &&
vb > -17 && vb < 16 &&
va > -17 && va < 16
) {
if (
va == 0 &&
vr > -3 && vr < 2 &&
vg > -3 && vg < 2 &&
vb > -3 && vb < 2
) {
bytes[p++] = QOI_DIFF_8 | ((vr + 2) << 4) | (vg + 2) << 2 | (vb + 2);
}
else if (
va == 0 &&
vr > -17 && vr < 16 &&
vg > -9 && vg < 8 &&
vb > -9 && vb < 8
) {
bytes[p++] = QOI_DIFF_16 | (vr + 16);
bytes[p++] = (vg + 8) << 4 | (vb + 8);
}
else {
bytes[p++] = QOI_DIFF_24 | (vr + 16) >> 1;
bytes[p++] = (vr + 16) << 7 | (vg + 16) << 2 | (vb + 16) >> 3;
bytes[p++] = (vb + 16) << 5 | (va + 16);
}
}
else {
bytes[p++] = QOI_COLOR | (vr ? 8 : 0) | (vg ? 4 : 0) | (vb ? 2 : 0) | (va ? 1 : 0);
if (vr) { bytes[p++] = px.rgba.r; }
if (vg) { bytes[p++] = px.rgba.g; }
if (vb) { bytes[p++] = px.rgba.b; }
if (va) { bytes[p++] = px.rgba.a; }
}
}
}
px_prev = px;
}
for (int i = 0; i < QOI_PADDING; i++) {
bytes[p++] = 0;
}
*out_len = p;
return bytes;
}
void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels) {
if (
data == NULL || desc == NULL ||
(channels != 0 && channels != 3 && channels != 4) ||
size < QOI_HEADER_SIZE + QOI_PADDING
) {
return NULL;
}
const unsigned char *bytes = (const unsigned char *)data;
int p = 0;
unsigned int header_magic = qoi_read_32(bytes, &p);
desc->width = qoi_read_32(bytes, &p);
desc->height = qoi_read_32(bytes, &p);
desc->channels = bytes[p++];
desc->colorspace = bytes[p++];
if (
desc->width == 0 || desc->height == 0 ||
desc->channels < 3 || desc->channels > 4 ||
header_magic != QOI_MAGIC
) {
return NULL;
}
if (channels == 0) {
channels = desc->channels;
}
int px_len = desc->width * desc->height * channels;
unsigned char *pixels = QOI_MALLOC(px_len);
if (!pixels) {
return NULL;
}
qoi_rgba_t px = {.rgba = {.r = 0, .g = 0, .b = 0, .a = 255}};
qoi_rgba_t index[64] = {0};
int run = 0;
int chunks_len = size - QOI_PADDING;
for (int px_pos = 0; px_pos < px_len; px_pos += channels) {
if (run > 0) {
run--;
}
else if (p < chunks_len) {
int b1 = bytes[p++];
if ((b1 & QOI_MASK_2) == QOI_INDEX) {
px = index[b1 ^ QOI_INDEX];
}
else if ((b1 & QOI_MASK_3) == QOI_RUN_8) {
run = (b1 & 0x1f);
}
else if ((b1 & QOI_MASK_3) == QOI_RUN_16) {
int b2 = bytes[p++];
run = (((b1 & 0x1f) << 8) | (b2)) + 32;
}
else if ((b1 & QOI_MASK_2) == QOI_DIFF_8) {
px.rgba.r += ((b1 >> 4) & 0x03) - 2;
px.rgba.g += ((b1 >> 2) & 0x03) - 2;
px.rgba.b += ( b1 & 0x03) - 2;
}
else if ((b1 & QOI_MASK_3) == QOI_DIFF_16) {
int b2 = bytes[p++];
px.rgba.r += (b1 & 0x1f) - 16;
px.rgba.g += (b2 >> 4) - 8;
px.rgba.b += (b2 & 0x0f) - 8;
}
else if ((b1 & QOI_MASK_4) == QOI_DIFF_24) {
int b2 = bytes[p++];
int b3 = bytes[p++];
px.rgba.r += (((b1 & 0x0f) << 1) | (b2 >> 7)) - 16;
px.rgba.g += ((b2 & 0x7c) >> 2) - 16;
px.rgba.b += (((b2 & 0x03) << 3) | ((b3 & 0xe0) >> 5)) - 16;
px.rgba.a += (b3 & 0x1f) - 16;
}
else if ((b1 & QOI_MASK_4) == QOI_COLOR) {
if (b1 & 8) { px.rgba.r = bytes[p++]; }
if (b1 & 4) { px.rgba.g = bytes[p++]; }
if (b1 & 2) { px.rgba.b = bytes[p++]; }
if (b1 & 1) { px.rgba.a = bytes[p++]; }
}
index[QOI_COLOR_HASH(px) % 64] = px;
}
if (channels == 4) {
*(qoi_rgba_t*)(pixels + px_pos) = px;
}
else {
pixels[px_pos] = px.rgba.r;
pixels[px_pos+1] = px.rgba.g;
pixels[px_pos+2] = px.rgba.b;
}
}
return pixels;
}
#ifndef QOI_NO_STDIO
#include <stdio.h>
int qoi_write(const char *filename, const void *data, const qoi_desc *desc) {
FILE *f = fopen(filename, "wb");
if (!f) {
return 0;
}
int size;
void *encoded = qoi_encode(data, desc, &size);
if (!encoded) {
fclose(f);
return 0;
}
fwrite(encoded, 1, size, f);
fclose(f);
QOI_FREE(encoded);
return size;
}
void *qoi_read(const char *filename, qoi_desc *desc, int channels) {
FILE *f = fopen(filename, "rb");
if (!f) {
return NULL;
}
fseek(f, 0, SEEK_END);
int size = ftell(f);
fseek(f, 0, SEEK_SET);
void *data = QOI_MALLOC(size);
if (!data) {
fclose(f);
return NULL;
}
int bytes_read = fread(data, 1, size, f);
fclose(f);
void *pixels = qoi_decode(data, bytes_read, desc, channels);
QOI_FREE(data);
return pixels;
}
#endif // QOI_NO_STDIO
#endif // QOI_IMPLEMENTATIONP. S. В первый день после анонса в формате файлов обнаружились незначительные баги. Автор обещает представить финальную версию 20 декабря 2021 года.
