[Из песочницы] Как сжать плоского кота
Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 16МГц (да-да, во встраиваемой электронике, особенно сверхнизкого энергопотребления, встречаются и такие) и совсем нет памяти. Ну, т.е. килобайтов 8 RAM и 256 Flash. Килобайтов, Карл. И в эти унылые килобайты необходимо запихнуть несколько изображений 800×600 в четырех оттенках серого. Быстро перемножив в уме 800 на 600 и на 2 бита на пиксель получаем 120 тысяч байтов. Несколько не влезает. Надо сжимать.
Так перед нами появилась задача: «как сжать плоского кота»? Почему кота? Да потому, что на котиках тестировали, на чем же еще черно-белые картинки проверять. Не на долларовых банкнотах же.
Первый ответ звучал так: давайте сожмем кота RLE. Кот-то плоский… То есть плоскоцветный — всего четыре оттенка. Пустых мест на экране полно, т.е. повторяющихся пикселей будет до черта. Должно сжиматься.
Должно сжиматься — сжалось. С единственным затруднением: сжимать-то нам все равно как, сжимаем мы на PC, а то и вовсе на сервере. А вот разжимать нам надо последовательно, потоковым образом: байт вытащили — байт вывели. Видеобуфера-то у нас нету на 8 килобайтах RAM, разжатого кота хранить негде.
Справились. Сжимается кот.
/****************************************************************************/
/* Common Utilities Library * (C) Componentality Oy, 2015 */
/****************************************************************************/
/* RLE compression implementation */
/****************************************************************************/
#include "rle.h"
#include
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 тоже подойдет, надо только придумать, как разжимать данные потоковым образом без промежуточного хранения. Придумали. Получилось вот так:
/****************************************************************************/
/* 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 - 1 for byte from to 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 and for maximum length of 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 to sequence starting from
// - size of window to be scanned in bytes, - maximum length of matching area in bytes, - size of
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 of size to bitwise memory . 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 прекрасным образом разжимается потоковым декомпрессором в один проход.
Вот так:
/****************************************************************************/
/* 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). Вдруг и вам придется что-нибудь разжимать в условиях катастрофической нехватки памяти и процессорного ресурса.
