...

понедельник, 14 декабря 2015 г.

[Из песочницы] Как сжать плоского кота

Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 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). Вдруг и вам придется что-нибудь разжимать в условиях катастрофической нехватки памяти и процессорного ресурса.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий