Как стать автором
Обновить
72.42

Главное — скорость. Новый графический формат QOI в 20−50 раз быстрее PNG

Время на прочтение10 мин
Количество просмотров9.7K


Современные форматы кодирования изображений — это настоящая магия, в которой не разобраться без нескольких лет погружения в специфические алгоритмы. Даже опенсорсные форматы содержат настоящее спагетти навороченных и хитроумных методов типа алгоритма Хаффмана и дискретно-косинусного преобразования — результат нескольких десятилетий развития компьютерной науки.

Поскольку польский разработчик Доминик Шаблевски вообще не разбирается в кодировании изображений, то он написал примитивный метод сжатия изображений без потери качества всего в 300 строчек кода, на базовой математике. Результат его очень удивил.

Оказалось, что этот простой метод по скорости на порядок превосходит популярные кодеки libpng и stbi.

Доминик Шаблевски назвал формат Quite OK (Quite OK Image), то есть «вполне достаточное» качество и размер. Другими словами, он конкретно заточен именно на скорость. Во многих случаях — при пакетной обработке большого количества файлов, в автоматических конвейерах — скорость является ключевым фактором.

Автор считает свой алгоритм до глупости простым. Он берёт изображения RGB и RGBA — и кодирует их в формат QOI размером с обычный PNG, но гораздо быстрее. Всё в один поток, без SIMD.

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

  1. Если пиксель равен предыдущему, увеличивается счётчик по типу кодирования повторов (RLE). Если нет, то применяется метод 2, и так далее
  2. Пиксель из массива 64 последних по «хешу» r^g^b^a
  3. Разница с предыдущим пикселем, если она небольшая
  4. Полное значение 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_IMPLEMENTATION

P. S. В первый день после анонса в формате файлов обнаружились незначительные баги. Автор обещает представить финальную версию 20 декабря 2021 года.
Теги:
Хабы:
Всего голосов 47: ↑45 и ↓2+56
Комментарии16

Другие новости

Информация

Сайт
mtech.mvideoeldorado.ru
Дата регистрации
Дата основания
Численность
свыше 10 000 человек
Местоположение
Россия