Как сжать плоского кота

в 8:32, , рубрики: C, Алгоритмы, встраиваемые системы, обработка изображений, сжатие без потерь, сжатие данных

Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 16МГц (да-да, во встраиваемой электронике, особенно сверхнизкого энергопотребления, встречаются и такие) и совсем нет памяти. Ну, т.е. килобайтов 8 RAM и 256 Flash. Килобайтов, Карл. И в эти унылые килобайты необходимо запихнуть несколько изображений 800х600 в четырех оттенках серого. Быстро перемножив в уме 800 на 600 и на 2 бита на пиксель получаем 120 тысяч байтов. Несколько не влезает. Надо сжимать.

Так перед нами появилась задача: «как сжать плоского кота»? Почему кота? Да потому, что на котиках тестировали, на чем же еще черно-белые картинки проверять. Не на долларовых банкнотах же.

Первый ответ звучал так: давайте сожмем кота RLE. Кот-то плоский… То есть плоскоцветный — всего четыре оттенка. Пустых мест на экране полно, т.е. повторяющихся пикселей будет до черта. Должно сжиматься.

Должно сжиматься — сжалось. С единственным затруднением: сжимать-то нам все равно как, сжимаем мы на PC, а то и вовсе на сервере. А вот разжимать нам надо последовательно, потоковым образом: байт вытащили — байт вывели. Видеобуфера-то у нас нету на 8 килобайтах RAM, разжатого кота хранить негде.

Справились. Сжимается кот.

Сжатие RLE

/****************************************************************************/
/* Common Utilities Library        *            (C) Componentality Oy, 2015 */
/****************************************************************************/
/* RLE compression implementation                                           */
/****************************************************************************/
#include "rle.h"
#include <memory.h>

using namespace Componentality::Common;

// Do 8-bit RLE encoding
void Componentality::Common::RLE_Encode(unsigned char* source, size_t source_size, unsigned char* target, size_t& target_size)
{
	target_size = 0;
	unsigned char previous_character = source[0];
	unsigned char series_counter = 1;
	bool same = false;
	size_t i;
	for (i = 1; i < source_size; i++)
	{
		// If current byte is equal to previous
		if (source[i] == previous_character)
		{
			// If we process sequence of the same characters
			if (same)
			{
				if (series_counter < 127)
					series_counter++;
				else
				{
					target[target_size++] = 0x80 | series_counter;
					target[target_size++] = previous_character;
					series_counter = 1;
				}
			}
			else
			{
				if (series_counter > 1)
				{
					target[target_size++] = series_counter - 1;
					memcpy(target + target_size, source + i - series_counter, series_counter - 1);
					target_size += series_counter - 1;
				}
				series_counter = 2;
				same = true;
			}
		}
		else
		{
			if (same)
			{
				if (series_counter > 1)
				{
					target[target_size++] = 0x80 | series_counter;
					target[target_size++] = previous_character;
					series_counter = 1;
				}
				else
					series_counter += 1;
				same = false;
			}
			else
			{
				if (series_counter > 127)
				{
					target[target_size++] = series_counter - 1;
					memcpy(target + target_size, source + i - (series_counter - 1), series_counter - 1);
					target_size += series_counter - 1;
					series_counter = 1;
				}
				else
					series_counter++;
			}
		}
		previous_character = source[i];
	}
	if (same)
	{
		target[target_size++] = 0x80 | series_counter;
		target[target_size++] = previous_character;
	}
	else
	{
		target[target_size++] = series_counter;
		memcpy(target + target_size, source + i - (series_counter), series_counter);
		target_size += series_counter;
	}
}

// Do buffered RLE decoding
void Componentality::Common::RLE_Decode(unsigned char* source, size_t source_size, unsigned char* target, size_t& target_size)
{
	target_size = 0;
	for (size_t i = 0; i < source_size;)
	{
		unsigned char size = source[i] & ~0x80;
		if (source[i] & 0x80)
		{
			memset(target + target_size, source[i + 1], size);
			i += 2;
		}
		else
		{
			memcpy(target + target_size, source + i + 1, size);
			i += size + 1;
		}
		target_size += size;
	}
}

// Check where two buffers are different
size_t Componentality::Common::isDiff(unsigned char* left, unsigned char* right, size_t size)
{
	for (size_t i = 0; i < size; i++)
	{
		if (left[i] != right[i])
			return i;
	}
	return (size_t)-1;
}

// Incremental decoding initialization
void Componentality::Common::RLE_InitDecoder(RLE_DECODE* handler, unsigned char* source)
{
	handler->mDecodedPortion = 0;
	handler->mPtr = 0;
	handler->mOffset = 0;
	handler->mSource = source;
}

// Decode next byte incrementally
unsigned char Componentality::Common::RLE_Fetch(RLE_DECODE* handler)
{
	if (handler->mDecodedPortion > handler->mPtr)
	{
		handler->mPtr += 1;
		if (handler->mMode == 0x00)
			handler->mOffset += 1;
		return handler->mSource[handler->mOffset - 1];
	}
	handler->mDecodedPortion = handler->mSource[handler->mOffset] & ~0x80;
	handler->mMode = handler->mSource[handler->mOffset] & 0x80;
	handler->mOffset += 2;
	handler->mPtr = 1;
	return handler->mSource[handler->mOffset - 1];
}

Хорошо кот сжимается. В среднем по больнице раза в 4. Но мы жадные, нам бы поплотнее. Мало у нас памяти, совсем мало, и нужна она не для одних только котиков, нам еще нужно строить одноранговую сеть, маршруты хранить и прочую всякую ерунду.

Подумали еще раз. Так подумали, сяк подумали, решили, что LZ77 тоже подойдет, надо только придумать, как разжимать данные потоковым образом без промежуточного хранения. Придумали. Получилось вот так:

Сжатие embedded-модификацией LZ77 (алгоритм Scanback)

/****************************************************************************/
/* Common Utilities Library        *       (C) Componentality Oy, 2014-2015 */
/****************************************************************************/
/* Scanback compression implementation                                      */
/****************************************************************************/
/* Scanback - LZ77 for embedded systems                                     */
/* Designed and developed by Konstantin Khait                               */
/****************************************************************************/

#include "scanback.h"
extern "C"
{
#include "bitmem.h"
}

using namespace Componentality::Common;

// Scan buffer (buf) back from position <index> - 1 for byte <wtf> from <minfind> to <maxfind> index
static unsigned char _sb__findback(unsigned char* buf, unsigned long index, unsigned char wtf, unsigned char minfind, unsigned char maxfind)
{
	unsigned char i;
	for (i = minfind; i < maxfind; i++)
	{
		if (buf[index - i] == wtf)
			return i;
	}
	return 0;
}

// Compare <buf1> and <buf2> for maximum length of <size> and return length of identical fragment
static unsigned char _sb__match(unsigned char* buf1, unsigned char* buf2, unsigned char size)
{
	unsigned char i;
	for (i = 0; i < size; i++)
	{
		if (buf1[i] != buf2[i])
			break;
	}
	return i;
}

// Find maximum matching sequence in buffer <buf> to sequence starting from <index>
// <winsize> - size of window to be scanned in bytes, <matchlen> - maximum length of matching area in bytes, <bufsize> - size of <buf>
SB_PTR _sb_scanback(unsigned char* buf, unsigned long index, unsigned char winsize, unsigned char matchlen, unsigned long bufsize)
{
	SB_PTR result = { 0, 0 };
	unsigned char i;
	if (winsize > index)
		winsize = (unsigned char)index;
	if (matchlen > winsize)
		matchlen = winsize;
	for (i = 1; i < winsize; i++)
	{
		register unsigned char offset = _sb__findback(buf, index, buf[index], i, winsize);
		if (offset)
		{
			register unsigned char matchsize = (unsigned char)(matchlen < (bufsize - index) ? matchlen : bufsize - index);
			if (matchsize > offset)
				matchsize = offset;
			register unsigned char len = _sb__match(buf + index, buf + index - offset, matchsize);
			if (len > result.length)
			{
				result.offset = offset;
				result.length = len;
			}
			i = offset;
		}
	}
	return result;
}

// Do compression of buffer <buf> of size <size> to bitwise memory <mem>. Returns number of produced bits
unsigned long Componentality::Common::SB_Compress(unsigned char* mem, unsigned char* buf, unsigned long size)
{
	unsigned long bitcount = 0, i;
	SB_PTR cptr;

	for (i = 0; i < (1 << LENGTH_BITS); i++)
		mem[i] = buf[i];
	bitcount += (1 << LENGTH_BITS) * 8;

	for (i = 1 << LENGTH_BITS; i < size;)
	{
		cptr = _sb_scanback(buf, i, 1 << WINDOW_BITS, 1 << LENGTH_BITS, size);
		if (!cptr.offset)
		{
			bitmem_put1(mem, bitcount++, 0);
			bitmem_put(mem, bitcount, buf[i], 8);
			bitcount += 8;
			i += 1;
		}
		else
		{
			bitmem_put1(mem, bitcount++, 1);
			bitmem_put(mem, bitcount, cptr.offset - 1, WINDOW_BITS);
			bitcount += WINDOW_BITS;
			bitmem_put(mem, bitcount, cptr.length - 1, LENGTH_BITS);
			bitcount += LENGTH_BITS;
			i += cptr.length;
		}
	}
	return bitcount;
}

// Initialize decoder context
void Componentality::Common::SB_InitDecoder(SB_DECODER* decoder, unsigned char* mem)
{
	decoder->bitindex = 0;
	decoder->mem = mem;
	decoder->total_decoded = 0;
	decoder->index = 0;
	decoder->brb = 0;
}

// Initialize decoder with ringbuffer
void SB_InitDecoderRB(SB_DECODER* decoder, void* ringbuffer)
{
	decoder->bitindex = 0;
	decoder->mem = 0;
	decoder->total_decoded = 0;
	decoder->index = 0;
	decoder->brb = ringbuffer;
}

// Unpack next byte from the packed stream
unsigned char Componentality::Common::SB_Fetch(SB_DECODER* decoder)
{
	register unsigned char result;
	if (decoder->index < (1 << LENGTH_BITS))
	{
		if (!decoder->brb)
			result = decoder->decoded_buf[decoder->index % (1 << WINDOW_BITS)] = decoder->mem[decoder->index];
		else
			result = decoder->decoded_buf[decoder->index % (1 << WINDOW_BITS)] = (unsigned char)bitmem_read_ringbuf((BIT_RINGBUF*)decoder->brb, 8);
		decoder->index += 1;
		decoder->bitindex += 8;
		decoder->total_decoded += 1;
		return result;
	}
	if (decoder->index >= decoder->total_decoded)
	{
		bit isref = bitmem_get1(decoder->mem, decoder->bitindex++);
		if (!isref)
		{
			if (!decoder->brb)
				decoder->decoded_buf[decoder->total_decoded % (1 << WINDOW_BITS)] = (unsigned char)bitmem_get(decoder->mem, decoder->bitindex, 8);
			else
				decoder->decoded_buf[decoder->total_decoded % (1 << WINDOW_BITS)] = (unsigned char)bitmem_read_ringbuf((BIT_RINGBUF*)decoder->brb, 8);;
			decoder->bitindex += 8;
			decoder->total_decoded += 1;
		}
		else
		{
			register SB_PTR ptr;
			register unsigned char i;
			if (!decoder->brb)
				ptr.offset = (unsigned char)bitmem_get(decoder->mem, decoder->bitindex, WINDOW_BITS) + 1;
			else
				ptr.offset = (unsigned char) bitmem_read_ringbuf((BIT_RINGBUF*)decoder->brb, WINDOW_BITS) + 1;
			decoder->bitindex += WINDOW_BITS;
			if (!decoder->brb)
				ptr.length = (unsigned char)bitmem_get(decoder->mem, decoder->bitindex, LENGTH_BITS) + 1;
			else
				ptr.length = (unsigned char) bitmem_read_ringbuf((BIT_RINGBUF*)decoder->brb, LENGTH_BITS) + 1;
			decoder->bitindex += LENGTH_BITS;
			for (i = 0; i < ptr.length; i++)
			{
				register unsigned long srcptr = decoder->total_decoded - ptr.offset;
				decoder->decoded_buf[decoder->total_decoded % (1 << WINDOW_BITS)] = decoder->decoded_buf[srcptr % (1 << WINDOW_BITS)];
				decoder->total_decoded += 1;
			}
		}
	}
	result = decoder->decoded_buf[decoder->index % (1 << WINDOW_BITS)];
	decoder->index += 1;
	return result;
}

Особенно нас порадовал footprint для декомпрессии, приблизительно равный 150 байтам (при «окне» алгоритма в 127 байтов). Первоначально в алгоритмах Лемпеля-Зива нас сильно смущала необходимость выделения памяти под словарь. RLE-то словарь вовсе без надобности… Но 150 байтами нас не напугаешь.

Напугало нас другое — несмотря на то, что из теории известно, что LZ77 — это обобщение RLE, замена второго на первый давала улучшение результата на грани статистической погрешности: иногда лучше, иногда хуже, но в целом та же степень сжатия, какие параметры не задавай.

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

А потом… А потом мы запустили сжатие scanback'ом поверх RLE. И, о чудо, степень сжатия с 3-4 подскочила до 7-10 в зависимости от «пушистости кота», то бишь от степени плоскоцветности картинки и количества градиентных областей. Можно жить. И, самое главное, RLE + SB прекрасным образом разжимается потоковым декомпрессором в один проход.

Вот так:

Потоковый декомпрессор RLE + Scanback

/****************************************************************************/
/* Common Utilities Library        *            (C) Componentality Oy, 2015 */
/****************************************************************************/
/* Combined RLE + Scanback implementation (compression is to be done        */
/* sequentially, decompression is optimized                                 */
/****************************************************************************/
#include "rlesbc.h"

using namespace Componentality::Common;

// Decode next byte incrementally for stream compressed by both RLE and Scanback
unsigned char Componentality::Common::RLESB_Fetch(RLE_DECODE* handler, SB_DECODER* sb_handler, unsigned char* repeating_value)
{
	if (handler->mDecodedPortion > handler->mPtr)
	{
		handler->mPtr += 1;
		if (handler->mMode == 0x00)
			*repeating_value = SB_Fetch(sb_handler);
		return *repeating_value;
	}
	*repeating_value = SB_Fetch(sb_handler);
	handler->mDecodedPortion = *repeating_value & ~0x80;
	handler->mMode = *repeating_value & 0x80;
	*repeating_value = SB_Fetch(sb_handler);
	handler->mPtr = 1;
	return *repeating_value;
}

Вот уже год, как наши котики прекрасно живут почти «в полном беспамятстве», назло всяким ZLIB'ам. Которые, разумеется, жмут куда плотнее, но и ресурсов потребляют несравнимо больше. А мы тем временем обнаружили, что наш RLE + SB великолепно подходит для многих других задач, например, им великолепно сжимаются растровые шрифты, даже с прозрачностью и антиалиасингом, а также всякий сетевой текстовый трафик. Естественно, степень компрессии составляет смешные 2.5-6, зато и ресурсов почти не потребляется, особенно на разжатие, которое, как правило, выполняется чаще, и к скорости-памяти куда критичнее.

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

Автор: akk025

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js