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

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

Средняя зарплата в IT

120 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 7 453 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 65

    +24
    А где же картинка с котом?
      +13
      Ещё в процессе разжатия, видимо.
        +8
        Кот, да не тот.


        Кстати спасибо за интересный метод. У меня изображения были сильно меньше, но большим количеством. Приходилось использовать внешнюю flash — на контроллер оно и так и так не влезло бы, а с 1Мб флешкой смысла сжимать и не было.
        0
        Зато есть спойлеры с кодом
          +2
          После публикации, читается как «с котом»…
          +9
          Мда, что-то не убедительно без исходных файлов картинок.
          Для работы с 8 кб RAM можно на раз найти в инете пачку алгоритмов: LZSS, S-LZW, FastLZ…

          Для малопотребляющего устройства наверно имеет значение скорость работы, так что не хватает еще сравнительной оценки энергопотребления.
            0
            lzss требует доступ к последнему расжатому блоку (2KB), который используется в качестве словаря. А тут видеобуфера нет.
              0
              … и 8 килобайтов на все. Вообще на все, не только на вывод картинки.
                –1
                FastLZ вообще не требует памяти на декомпрессию.
                  +1
                  Не существует словарных алгоритмов сжатия, не требующих «вообще» памяти на декомпрессию. Словарь, увы, необходимо где-то хранить.

                  github.com/ariya/FastLZ/blob/master/6unpack.c — посмотрите сами реализацию.

                  И не забывайте, пожалуйста, главное — необходимость потоковой распаковки.
                    0
                    Это не та ссылка.

                    Алгоритм
                    /*
                      FastLZ - lightning-fast lossless compression library
                    
                      Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
                      Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
                      Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
                    
                      Permission is hereby granted, free of charge, to any person obtaining a copy
                      of this software and associated documentation files (the "Software"), to deal
                      in the Software without restriction, including without limitation the rights
                      to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
                      copies of the Software, and to permit persons to whom the Software is
                      furnished to do so, subject to the following conditions:
                    
                      The above copyright notice and this permission notice shall be included in
                      all copies or substantial portions of the Software.
                    
                      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
                      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
                      FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
                      AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
                      LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
                      OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
                      THE SOFTWARE.
                    */
                    
                    #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
                    #include "..\app.h"
                    /*
                     * Always check for bound when decompressing.
                     * Generally it is best to leave it defined.
                     */
                       #define FASTLZ_SAFE
                    
                    /*
                     * Give hints to the compiler for branch prediction optimization.
                     */
                       #if defined(__GNUC__) && (__GNUC__ > 2)
                          #define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
                          #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
                       #else
                          #define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
                          #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
                       #endif
                    
                    /*
                     * Use inlined functions for supported systems.
                     */
                       #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
                          #define FASTLZ_INLINE inline
                       #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
                          #define FASTLZ_INLINE __inline
                       #else
                          #define FASTLZ_INLINE
                       #endif
                    
                    /*
                     * Prevent accessing more than 8-bit at once, except on x86 architectures.
                     */
                       #if !defined(FASTLZ_STRICT_ALIGN)
                          #define FASTLZ_STRICT_ALIGN
                          #if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
                             #undef FASTLZ_STRICT_ALIGN
                          #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
                             #undef FASTLZ_STRICT_ALIGN
                          #elif defined(_M_IX86) /* Intel, MSVC */
                             #undef FASTLZ_STRICT_ALIGN
                          #elif defined(__386)
                             #undef FASTLZ_STRICT_ALIGN
                          #elif defined(_X86_) /* MinGW */
                             #undef FASTLZ_STRICT_ALIGN
                          #elif defined(__I86__) /* Digital Mars */
                             #undef FASTLZ_STRICT_ALIGN
                          #endif
                       #endif
                    
                    /*
                     * FIXME: use preprocessor magic to set this on different platforms!
                     */
                    typedef unsigned char  flzuint8;
                    typedef unsigned short flzuint16;
                    typedef unsigned int   flzuint32;
                    
                    /* prototypes */
                    int fastlz_compress(const void *input, int length, void *output);
                    int fastlz_compress_level(int level, const void *input, int length, void *output);
                    int fastlz_decompress(const void *input, int length, void *output, int maxout);
                    
                       #define MAX_COPY       32
                       #define MAX_LEN       264  /* 256 + 8 */
                       #define MAX_DISTANCE 8192
                    
                       #if !defined(FASTLZ_STRICT_ALIGN)
                          #define FASTLZ_READU16(p) *((const flzuint16*)(p))
                       #else
                          #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
                       #endif
                    
                       #define HASH_LOG  13
                       #define HASH_SIZE (1<< HASH_LOG)
                       #define HASH_MASK  (HASH_SIZE-1)
                       #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
                    
                       #undef FASTLZ_LEVEL
                       #define FASTLZ_LEVEL 1
                    
                       #undef FASTLZ_COMPRESSOR
                       #undef FASTLZ_DECOMPRESSOR
                       #define FASTLZ_COMPRESSOR fastlz1_compress
                       #define FASTLZ_DECOMPRESSOR fastlz1_decompress
                    static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output);
                    static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout);
                       #include "fastlz.c"
                    
                       #undef FASTLZ_LEVEL
                       #define FASTLZ_LEVEL 2
                    
                       #undef MAX_DISTANCE
                       #define MAX_DISTANCE 8191
                       #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
                    
                       #undef FASTLZ_COMPRESSOR
                       #undef FASTLZ_DECOMPRESSOR
                       #define FASTLZ_COMPRESSOR fastlz2_compress
                       #define FASTLZ_DECOMPRESSOR fastlz2_decompress
                    static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output);
                    static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout);
                       #include "fastlz.c"
                    
                    int fastlz_compress(const void *input, int length, void *output)
                    {
                       /* for short block, choose fastlz1 */
                       if (length < 65536) return fastlz1_compress(input, length, output);
                    
                       /* else... */
                       return fastlz2_compress(input, length, output);
                    }
                    
                    int fastlz_decompress(const void *input, int length, void *output, int maxout)
                    {
                       /* magic identifier for compression level */
                       int level = ((*(const flzuint8 *)input) >> 5) + 1;
                    
                       if (level == 1) return fastlz1_decompress(input, length, output, maxout);
                       if (level == 2) return fastlz2_decompress(input, length, output, maxout);
                    
                       /* unknown level, trigger error */
                       return 0;
                    }
                    
                    int fastlz_compress_level(int level, const void *input, int length, void *output)
                    {
                       if (level == 1) return fastlz1_compress(input, length, output);
                       if (level == 2) return fastlz2_compress(input, length, output);
                    
                       return 0;
                    }
                    
                    #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
                    
                    static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output)
                    {
                       flzuint8 *ip = (flzuint8 *)input;
                       const flzuint8 *ip_bound = ip + length - 2;
                       const flzuint8 *ip_limit = ip + length - 12;
                       flzuint8 *op = (flzuint8 *)output;
                    
                    
                       flzuint8 **htab;
                       flzuint8 **hslot;
                       flzuint32 hval;
                    
                       flzuint32 copy;
                    
                    
                       htab = umm_malloc(HASH_SIZE*sizeof(flzuint8 *));
                       if (htab == NULL) return 0;
                    
                       /* sanity check */
                       if (FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
                       {
                          if (length)
                          {
                             /* create literal copy only */
                             *op++ = length - 1;
                             ip_bound++;
                             while (ip <= ip_bound) *op++ = *ip++;
                             return length + 1;
                          }
                              else
                              {
                    			      umm_free(htab);
                                      return 0;
                              }
                       }
                    
                    
                       /* initializes hash table */
                       for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
                       {
                       	   *hslot = ip;
                       }
                    
                       /* we start with literal copy */
                       copy = 2;
                       *op++ = MAX_COPY - 1;
                       *op++ = *ip++;
                       *op++ = *ip++;
                    
                       /* main loop */
                       while (FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
                       {
                          const flzuint8 *ref;
                          flzuint32 distance;
                    
                          /* minimum match length */
                          flzuint32 len = 3;
                    
                          /* comparison starting-point */
                          flzuint8 *anchor = ip;
                    
                          /* check for a run */
                       #if FASTLZ_LEVEL==2
                          if (ip[0] == ip[-1] && FASTLZ_READU16(ip - 1) == FASTLZ_READU16(ip + 1))
                          {
                             distance = 1;
                             ip += 3;
                             ref = anchor - 1 + 3;
                             goto match;
                          }
                       #endif
                    
                          /* find potential match */
                          HASH_FUNCTION(hval, ip);
                          hslot = htab + hval;
                          ref = htab[hval];
                    
                          /* calculate distance to the match */
                          distance = anchor - ref;
                    
                          /* update hash table */
                          *hslot = anchor;
                    
                          /* is this a match? check the first 3 bytes */
                          if (distance == 0 ||
                       #if FASTLZ_LEVEL==1
                              (distance >= MAX_DISTANCE) ||
                       #else
                              (distance >= MAX_FARDISTANCE) ||
                       #endif
                              *ref++ != *ip++ || *ref++ != *ip++ || *ref++ != *ip++) goto literal;
                    
                       #if FASTLZ_LEVEL==2
                          /* far, needs at least 5-byte match */
                          if (distance >= MAX_DISTANCE)
                          {
                             if (*ip++ != *ref++ || *ip++ != *ref++) goto literal;
                             len += 2;
                          }
                    
                       match:
                       #endif
                    
                          /* last matched byte */
                          ip = anchor + len;
                    
                          /* distance is biased */
                          distance--;
                    
                          if (!distance)
                          {
                             /* zero distance means a run */
                             flzuint8 x = ip[-1];
                             while (ip < ip_bound) if (*ref++ != x) break;
                                else ip++;
                          }
                          else for (;;)
                             {
                                /* safe because the outer check against ip limit */
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                if (*ref++ != *ip++) break;
                                while (ip < ip_bound) if (*ref++ != *ip++) break;
                                break;
                             }
                    
                          /* if we have copied something, adjust the copy count */
                          if (copy)
                             /* copy is biased, '0' means 1 byte copy */
                             *(op - copy - 1) = copy - 1;
                          else
                             /* back, to overwrite the copy count */
                             op--;
                    
                          /* reset literal counter */
                          copy = 0;
                    
                          /* length is biased, '1' means a match of 3 bytes */
                          ip -= 3;
                          len = ip - anchor;
                    
                          /* encode the match */
                       #if FASTLZ_LEVEL==2
                          if (distance < MAX_DISTANCE)
                          {
                             if (len < 7)
                             {
                                *op++ = (len << 5) + (distance >> 8);
                                *op++ = (distance & 255);
                             }
                             else
                             {
                                *op++ = (7 << 5) + (distance >> 8);
                                for (len -= 7; len >= 255; len -= 255) *op++ = 255;
                                *op++ = len;
                                *op++ = (distance & 255);
                             }
                          }
                          else
                          {
                             /* far away, but not yet in the another galaxy... */
                             if (len < 7)
                             {
                                distance -= MAX_DISTANCE;
                                *op++ = (len << 5) + 31;
                                *op++ = 255;
                                *op++ = distance >> 8;
                                *op++ = distance & 255;
                             }
                             else
                             {
                                distance -= MAX_DISTANCE;
                                *op++ = (7 << 5) + 31;
                                for (len -= 7; len >= 255; len -= 255) *op++ = 255;
                                *op++ = len;
                                *op++ = 255;
                                *op++ = distance >> 8;
                                *op++ = distance & 255;
                             }
                          }
                       #else
                    
                          if (FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN - 2)) while (len > MAX_LEN - 2)
                             {
                                *op++ = (7 << 5) + (distance >> 8);
                                *op++ = MAX_LEN - 2 - 7 - 2;
                                *op++ = (distance & 255);
                                len -= MAX_LEN - 2;
                             }
                    
                          if (len < 7)
                          {
                             *op++ = (len << 5) + (distance >> 8);
                             *op++ = (distance & 255);
                          }
                          else
                          {
                             *op++ = (7 << 5) + (distance >> 8);
                             *op++ = len - 7;
                             *op++ = (distance & 255);
                          }
                       #endif
                    
                          /* update the hash at match boundary */
                          HASH_FUNCTION(hval, ip);
                          htab[hval] = ip++;
                          HASH_FUNCTION(hval, ip);
                          htab[hval] = ip++;
                    
                          /* assuming literal copy */
                          *op++ = MAX_COPY - 1;
                    
                          continue;
                    
                       literal:
                          *op++ = *anchor++;
                          ip = anchor;
                          copy++;
                          if (FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
                          {
                             copy = 0;
                             *op++ = MAX_COPY - 1;
                          }
                       }
                    
                       /* left-over as literal copy */
                       ip_bound++;
                       while (ip <= ip_bound)
                       {
                          *op++ = *ip++;
                          copy++;
                          if (copy == MAX_COPY)
                          {
                             copy = 0;
                             *op++ = MAX_COPY - 1;
                          }
                       }
                    
                       /* if we have copied something, adjust the copy length */
                       if (copy) *(op - copy - 1) = copy - 1;
                       else op--;
                    
                       #if FASTLZ_LEVEL==2
                       /* marker for fastlz2 */
                       *(flzuint8 *)output |= (1 << 5);
                       #endif
                    
                       umm_free(htab);
                       return op - (flzuint8 *)output;
                    }
                    
                    static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout)
                    {
                       const flzuint8 *ip = (const flzuint8 *)input;
                       const flzuint8 *ip_limit  = ip + length;
                       flzuint8 *op = (flzuint8 *)output;
                       flzuint8 *op_limit = op + maxout;
                       flzuint32 ctrl = (*ip++) & 31;
                       int loop = 1;
                    
                       do
                       {
                          const flzuint8 *ref = op;
                          flzuint32 len = ctrl >> 5;
                          flzuint32 ofs = (ctrl & 31) << 8;
                    
                          if (ctrl >= 32)
                          {
                       #if FASTLZ_LEVEL==2
                             flzuint8 code;
                       #endif
                             len--;
                             ref -= ofs;
                             if (len == 7 - 1)
                       #if FASTLZ_LEVEL==1
                                len += *ip++;
                             ref -= *ip++;
                       #else
                                do
                                {
                                   code = *ip++;
                                   len += code;
                                }
                                while (code == 255);
                                code = *ip++;
                                ref -= code;
                    
                                /* match from 16-bit distance */
                                if (FASTLZ_UNEXPECT_CONDITIONAL(code == 255)) if (FASTLZ_EXPECT_CONDITIONAL(ofs == (31 << 8)))
                                   {
                                      ofs = (*ip++) << 8;
                                      ofs += *ip++;
                                      ref = op - ofs - MAX_DISTANCE;
                                   }
                       #endif
                    
                       #ifdef FASTLZ_SAFE
                             if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit)) return 0;
                    
                             if (FASTLZ_UNEXPECT_CONDITIONAL(ref - 1 < (flzuint8 *)output)) return 0;
                       #endif
                    
                             if (FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit)) ctrl = *ip++;
                             else loop = 0;
                    
                             if (ref == op)
                             {
                                /* optimize copy for a run */
                                flzuint8 b = ref[-1];
                                *op++ = b;
                                *op++ = b;
                                *op++ = b;
                                for (; len; --len) *op++ = b;
                             }
                             else
                             {
                       #if !defined(FASTLZ_STRICT_ALIGN)
                                const flzuint16 *p;
                                flzuint16 *q;
                       #endif
                                /* copy from reference */
                                ref--;
                                *op++ = *ref++;
                                *op++ = *ref++;
                                *op++ = *ref++;
                    
                       #if !defined(FASTLZ_STRICT_ALIGN)
                                /* copy a byte, so that now it's word aligned */
                                if (len & 1)
                                {
                                   *op++ = *ref++;
                                   len--;
                                }
                    
                                /* copy 16-bit at once */
                                q = (flzuint16 *)op;
                                op += len;
                                p = (const flzuint16 *)ref;
                                for (len >>= 1; len > 4; len -= 4)
                                {
                                   *q++ = *p++;
                                   *q++ = *p++;
                                   *q++ = *p++;
                                   *q++ = *p++;
                                }
                                for (; len; --len) *q++ = *p++;
                       #else
                                for (; len; --len) *op++ = *ref++;
                       #endif
                             }
                          }
                          else
                          {
                             ctrl++;
                       #ifdef FASTLZ_SAFE
                             if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit)) return 0;
                             if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit)) return 0;
                       #endif
                    
                             *op++ = *ip++;
                             for (--ctrl; ctrl; ctrl--) *op++ = *ip++;
                    
                             loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
                             if (loop) ctrl = *ip++;
                          }
                       }
                       while (FASTLZ_EXPECT_CONDITIONAL(loop));
                    
                       return op - (flzuint8 *)output;
                    }
                    
                    #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
                    



                    Я не вижу в декомпрессоре выделения памяти.
                      0
                      Неважно выделяется память, или указатель на нее передается снаружи. Важно, что она должна быть. У нас физически нет места под распакованные данные.
                        0
                        А что происходит с распакованными данными? Они сразу отправляются на вывод? Если да — в каком порядке и формате?
                          0
                          Распаковка происходит в процессе вывода на экран, точнее заполнения сдвигового регистра, управляющего подачей напряжения на затворы транзисторов матрицы дисплея. Формат управляющей команды зависит от типа экрана.
                        0
                        Убедили. Реализации очень близкие. Разница в том, что вместо хранения ссылки и кода операции мы сразу распаковываем ее результат в RAM. Аргументация — удобство каскадирования с RLE и снижение числа обращений к флэшу. В остальном то же самое, код короче.
                          +1
                          В качестве словаря используется (как и в LZSS) разжатый выходной поток:
                          ...
                          flzuint8 *op = (flzuint8 *)output;
                          ...
                          do {
                            const flzuint8 *ref = op;
                            //тут шаманство с ref
                            ...
                            //Ну и под конец при определенных условиях используем словарь
                            for (; len; --len) *op++ = *ref++;
                          ...
                          }
                          


                          для алгоритма fastlz1 размер окна, как я понял, 8191 байт.
                            0
                            Да-да… Разжатый выходной поток означает необходимость его хранения.
                            Спасибо.
                            Я вчера к вечеру утратил ясность мышления.
                  0
                  А ещё UCL
                    +1
                    Ну вы хоть, прежде чем алгоритмы с потолка предлагать, исходники-то читайте.
                    Здесь тоже нужно где-то хранить разжатые данные:
                    ucl_nrv2b_decompress_*(...)
                            {
                                const ucl_bytep m_pos;
                                m_pos = dst + olen - m_off;
                                dst[olen++] = *m_pos++;
                                do dst[olen++] = *m_pos++; while (--m_len > 0);
                            }
                    
                    0
                    Про S-LZW вот, что нашел:
                    An implementation with a 512 entry dictionary requires
                    2618 bytes (plus four bytes for each additional entry)
                    of RAM and 1262 bytes of ROM

                    Т.е. все три алгоритма, предложенных вами, жрут непомерно много памяти для данного устройства. Заносите следующую тройку.
                    –9
                    Жалко кота а не шакала сжимали… Ну вы поняли)
                      +13
                      КО: Сжатие без потерь.
                      +2
                      Нечто похожее можно было наблюдать для проекта «Казаки». Можно почитать ТУТ.
                      Были некоторые проблемы и в графическом департаменте. Огромные объемы двумерной графики, которыми приходилось оперировать, привели нас к созданию собственного формата: каждый кадр паковался отдельно, используя алгоритм LZ с общим словарем. За счет этого достигалась хорошая степень сжатия, а доступ к каждому кадру не требовал распаковки предыдущих.
                        0
                        А что за железка? Под что писали-то? Где купить?
                          0
                          Nordic NRF51822 (Cortex M0 + Bluetooth LE). Купить можно на Диджике, на Маузере, у нас тоже можно в форме платформ для разработки с электронной бумагой и радиопротоколами (но реклама вроде запрещена, поэтому без подробностей, чтобы не забанили, тем более, что цель поста другая).
                          +1
                          Спасибо за пост!

                          Может быть кому-нибудь поможет и мой опыт.

                          Когда-то на позапрошлой работе я писал GIF под UEFI.
                          Так вот, в GIF'е картинку можно порезать на слои, + есть «прозрачный» цвет.
                          Я сжимал так: нарезал на слои один цвет + прозрачный цвет и все сжимал Лемпелем-Зивом-Велчем.

                          То есть если у меня N цветов, я разрезал на N слоев, в каждом из которых по 2 цвета. При цветах не более 14-18 (большинство картинок били именно в этой гамме) сжималось на ура!

                          Вообще GIF забавный формат… Есть масса способов упаковать картинку…
                            +5
                            image
                              0
                              Котов давайте! Тоже хочется посжимать.
                                +1
                                image
                                image
                                  0
                                  Какой классный кот. Что за порода?
                                    +1
                                    На норвега похож
                                      0
                                      У меня такой был беспородный :)
                                      Из породистых имхо на сибиряка похож
                                      0
                                      cat2.bmp и загрузка снизу.
                                    0
                                    а нельзя было прицепить какой-нибудь EEPROM через SPI?
                                      0
                                      Можно. Но у нас миллионная партия — считаем каждый цент.
                                        0
                                        ого. интересно было бы узнать подробнее про проект. если только не секретная военка…
                                          0
                                          Не секретная военка. Ценники для супермаркетов.
                                            0
                                            Как раз думал об этом, когда читал о том что нужно отображать картинки с сервера.
                                              0
                                              для наших или зарубежных? мне кажется, в наших такую игрушку быстро сопрут)))
                                                0
                                                Сопрут, так сопрут — она копеечная и как ее использовать мимо основного назначения — неочевидно.
                                                0
                                                Скажите пожалуйста, а ПО стека не влияет на производительность алгоритмов, не свойственных предназначеню чипа?
                                                  0
                                                  Влияет. Пришлось сделать маленькую RTOS, чтобы честно делить время между задачами… Об этом в одной из следующих серий.
                                                  (Вывод данных на экран в отсутствие видеобуфера и в присутствие крайней критичности к задержкам, оказался существенно более сильно лимитирующей задачей. Зато сжимая данные мы экономим на чтении и, особенно, записи в медленный флэш).
                                                    0
                                                    Буду ждать продолжение! Как раз стою перед выбором ртос именно для нордика, а заодно прикидываю справится ли ртос при работе совместно со стеком.
                                                      0
                                                      Справится. Если у Вас нет экстремистских запросов по памяти и энергопотреблению, берите RTX, для работы со стеком ее достаточно. В нашем случае они были (мы работаем с собственным high speed протоколом), но, возможно, мы переоценили их жесткость.
                                                        0
                                                        Ваш ответ перевесил чашу весов из rtx и frertos в пользу первой :)
                                                  0
                                                  Хитро! Быстро окупиться :)
                                                  Пока идешь дойдешь до кассы, ценник уже обновился.
                                                    0
                                                    Фотография может немножко снизить подобные риски.
                                            +2
                                            image
                                            image
                                              0
                                              Этот котик довольно легко упаковался в 329000 бит, и с большим трудом — в 306000. Выигрыш по сравнению с сырыми данными — от 3 до 3.2 раза, До 7 раз очень далеко :(
                                                0
                                                Ну, я ж не утверждаю, что в 7 раз сжимается любой произвольно взятый кот… Более того, в 7 раз сжимается не кот, а типовой ценник типового магазина, причем это — среднее значение по целевой выборке. Некоторые сжимаются в 20 раз, некоторые на 20%. Увы.
                                                  0
                                                  Точно бит? А то исходная картинка одну дискету весит.
                                                    0
                                                    Да, 41 килобайт. Исходная картинка — 4-цветная, по 2 бита на пиксель занимает 120 килобайт.
                                                0
                                                несмотря на то, что из теории известно, что LZ77 — это обобщение RLE

                                                Поясните, пожалуйста. Всё же эти методы очень сильно отличаются.
                                                  0
                                                  Да не особо. RLE — это оконное сжатие с размером окна, равным единице и кодированием количества повторений вхождения, вместо длины совпадения (поскольку длина совпадения либо 0, либо 1).
                                                    0
                                                    Мы, наверное, по-разному понимаем похожесть. В RLE нет словаря, а это важная отличительная особенность алгоритмов LZ*. И обратно, в LZ77 нет счётчика повторений.

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

                                                    Впрочем, это не так уже и важно всё. Просто глаз за фразу зацепился.
                                                      +2
                                                      Я тоже так думал еще со студенческих времен. А теперь попробуйте посмотреть по-другому. Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности. RLE копирует последовательность из одного символа много раз, LZ77 — последовательность многих символов один раз. Можно даже написать общий код, так, чтобы выбор алгоритма свелся к заданию параметров.
                                                        0
                                                        Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности.

                                                        А, ну если так классифицировать, то согласен.
                                                  0
                                                  Было бы супер припилить к u8glib.
                                                    0
                                                    Ткнулся в код, а там…
                                                    return (size_t)-1;

                                                    Вы серьёзно?
                                                      +1
                                                      Что случилось, где пожар?
                                                      Так, пожалуй, смотрелось бы лучше:
                                                      return ~(size_t)0;
                                                      
                                                        0
                                                        Да, можно и так. Или вообще сделать константу отдельную…
                                                        Но это не особо важно — работает, значит, нормально.

                                                        Я другое хотел спросить: где прочитать про scanback? Что-то не могу найти описания алгоритма, а из кода вообще ничего не понял. Где тут преобразование происходит?
                                                        	*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;
                                                        }
                                                        
                                                          0
                                                          Могу выслать архив с исходниками. Мы пока не придумали, как вычленить из проприетарного гита конкретно этот модуль так, чтобы не менять систему сборки всех зависимых от него проектов. Если останутся вопросы — прокомментирую. На выходе появится статья в журнал.
                                                      0
                                                      По названию статьи вспомнился сериал «Альф», где одноимённый главный герой рассказывал рецепт котиного сока.
                                                      «Берёшь кота и соковыжималку...», дальше на него махали руками и окончание рецепта неизвестно.
                                                      P.S. В сериале ни один кот не пострадал.
                                                        0
                                                        Кот в процессе сжатия:
                                                          +1
                                                          Код scanback, наконец, полностью в публичном доступе. Правда, пока без примеров.

                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                          Самое читаемое