Так перед нами появилась задача: «как сжать плоского кота»? Почему кота? Да потому, что на котиках тестировали, на чем же еще черно-белые картинки проверять. Не на долларовых банкнотах же.
Первый ответ звучал так: давайте сожмем кота RLE. Кот-то плоский… То есть плоскоцветный — всего четыре оттенка. Пустых мест на экране полно, т.е. повторяющихся пикселей будет до черта. Должно сжиматься.
Должно сжиматься — сжалось. С единственным затруднением: сжимать-то нам все равно как, сжимаем мы на PC, а то и вовсе на сервере. А вот разжимать нам надо последовательно, потоковым образом: байт вытащили — байт вывели. Видеобуфера-то у нас нету на 8 килобайтах RAM, разжатого кота хранить негде.
Справились. Сжимается кот.
/****************************************************************************/
/* 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 тоже подойдет, надо только придумать, как разжимать данные потоковым образом без промежуточного хранения. Придумали. Получилось вот так:
/****************************************************************************/
/* 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 прекрасным образом разжимается потоковым декомпрессором в один проход.
Вот так:
/****************************************************************************/
/* 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). Вдруг и вам придется что-нибудь разжимать в условиях катастрофической нехватки памяти и процессорного ресурса.
Комментарии (64)
Indemsys
14.12.2015 11:53+9Мда, что-то не убедительно без исходных файлов картинок.
Для работы с 8 кб RAM можно на раз найти в инете пачку алгоритмов: LZSS, S-LZW, FastLZ…
Для малопотребляющего устройства наверно имеет значение скорость работы, так что не хватает еще сравнительной оценки энергопотребления.tbl
14.12.2015 14:12lzss требует доступ к последнему расжатому блоку (2KB), который используется в качестве словаря. А тут видеобуфера нет.
akk025
14.12.2015 16:03… и 8 килобайтов на все. Вообще на все, не только на вывод картинки.
Indemsys
14.12.2015 18:56-1FastLZ вообще не требует памяти на декомпрессию.
akk025
14.12.2015 20:39+1Не существует словарных алгоритмов сжатия, не требующих «вообще» памяти на декомпрессию. Словарь, увы, необходимо где-то хранить.
github.com/ariya/FastLZ/blob/master/6unpack.c — посмотрите сами реализацию.
И не забывайте, пожалуйста, главное — необходимость потоковой распаковки.Indemsys
14.12.2015 21:04Это не та ссылка.
Алгоритм/* 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; /*akk025
14.12.2015 22:35Неважно выделяется память, или указатель на нее передается снаружи. Важно, что она должна быть. У нас физически нет места под распакованные данные.
Mrrl
15.12.2015 07:51А что происходит с распакованными данными? Они сразу отправляются на вывод? Если да — в каком порядке и формате?
akk025
15.12.2015 14:49Распаковка происходит в процессе вывода на экран, точнее заполнения сдвигового регистра, управляющего подачей напряжения на затворы транзисторов матрицы дисплея. Формат управляющей команды зависит от типа экрана.
akk025
14.12.2015 23:15Убедили. Реализации очень близкие. Разница в том, что вместо хранения ссылки и кода операции мы сразу распаковываем ее результат в RAM. Аргументация — удобство каскадирования с RLE и снижение числа обращений к флэшу. В остальном то же самое, код короче.
tbl
15.12.2015 18:05+1В качестве словаря используется (как и в LZSS) разжатый выходной поток:
... flzuint8 *op = (flzuint8 *)output; ... do { const flzuint8 *ref = op; //тут шаманство с ref ... //Ну и под конец при определенных условиях используем словарь for (; len; --len) *op++ = *ref++; ... }
для алгоритма fastlz1 размер окна, как я понял, 8191 байт.akk025
15.12.2015 23:35Да-да… Разжатый выходной поток означает необходимость его хранения.
Спасибо.
Я вчера к вечеру утратил ясность мышления.
CAJAX
14.12.2015 16:20А ещё UCL
tbl
15.12.2015 18:26+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); }
tbl
15.12.2015 18:19Про 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
Т.е. все три алгоритма, предложенных вами, жрут непомерно много памяти для данного устройства. Заносите следующую тройку.
withoutuniverse
14.12.2015 12:34+2Нечто похожее можно было наблюдать для проекта «Казаки». Можно почитать ТУТ.
Были некоторые проблемы и в графическом департаменте. Огромные объемы двумерной графики, которыми приходилось оперировать, привели нас к созданию собственного формата: каждый кадр паковался отдельно, используя алгоритм LZ с общим словарем. За счет этого достигалась хорошая степень сжатия, а доступ к каждому кадру не требовал распаковки предыдущих.
WeslomPo
14.12.2015 15:14А что за железка? Под что писали-то? Где купить?
akk025
14.12.2015 16:09Nordic NRF51822 (Cortex M0 + Bluetooth LE). Купить можно на Диджике, на Маузере, у нас тоже можно в форме платформ для разработки с электронной бумагой и радиопротоколами (но реклама вроде запрещена, поэтому без подробностей, чтобы не забанили, тем более, что цель поста другая).
PavelMSTU
14.12.2015 15:41+1Спасибо за пост!
Может быть кому-нибудь поможет и мой опыт.
Когда-то на позапрошлой работе я писал GIF под UEFI.
Так вот, в GIF'е картинку можно порезать на слои, + есть «прозрачный» цвет.
Я сжимал так: нарезал на слои один цвет + прозрачный цвет и все сжимал Лемпелем-Зивом-Велчем.
То есть если у меня N цветов, я разрезал на N слоев, в каждом из которых по 2 цвета. При цветах не более 14-18 (большинство картинок били именно в этой гамме) сжималось на ура!
Вообще GIF забавный формат… Есть масса способов упаковать картинку…
safari2012
14.12.2015 16:54а нельзя было прицепить какой-нибудь EEPROM через SPI?
akk025
14.12.2015 17:12Можно. Но у нас миллионная партия — считаем каждый цент.
safari2012
14.12.2015 17:31ого. интересно было бы узнать подробнее про проект. если только не секретная военка…
akk025
14.12.2015 17:37Не секретная военка. Ценники для супермаркетов.
WeslomPo
14.12.2015 17:57Как раз думал об этом, когда читал о том что нужно отображать картинки с сервера.
safari2012
14.12.2015 18:54для наших или зарубежных? мне кажется, в наших такую игрушку быстро сопрут)))
akk025
14.12.2015 19:11Сопрут, так сопрут — она копеечная и как ее использовать мимо основного назначения — неочевидно.
Lebets_VI
14.12.2015 19:21Скажите пожалуйста, а ПО стека не влияет на производительность алгоритмов, не свойственных предназначеню чипа?
akk025
14.12.2015 19:34Влияет. Пришлось сделать маленькую RTOS, чтобы честно делить время между задачами… Об этом в одной из следующих серий.
(Вывод данных на экран в отсутствие видеобуфера и в присутствие крайней критичности к задержкам, оказался существенно более сильно лимитирующей задачей. Зато сжимая данные мы экономим на чтении и, особенно, записи в медленный флэш).Lebets_VI
14.12.2015 19:48Буду ждать продолжение! Как раз стою перед выбором ртос именно для нордика, а заодно прикидываю справится ли ртос при работе совместно со стеком.
akk025
14.12.2015 20:41Справится. Если у Вас нет экстремистских запросов по памяти и энергопотреблению, берите RTX, для работы со стеком ее достаточно. В нашем случае они были (мы работаем с собственным high speed протоколом), но, возможно, мы переоценили их жесткость.
akk025
14.12.2015 19:12+2
Mrrl
15.12.2015 13:25Этот котик довольно легко упаковался в 329000 бит, и с большим трудом — в 306000. Выигрыш по сравнению с сырыми данными — от 3 до 3.2 раза, До 7 раз очень далеко :(
akk025
15.12.2015 13:59Ну, я ж не утверждаю, что в 7 раз сжимается любой произвольно взятый кот… Более того, в 7 раз сжимается не кот, а типовой ценник типового магазина, причем это — среднее значение по целевой выборке. Некоторые сжимаются в 20 раз, некоторые на 20%. Увы.
masai
14.12.2015 21:36несмотря на то, что из теории известно, что LZ77 — это обобщение RLE
Поясните, пожалуйста. Всё же эти методы очень сильно отличаются.akk025
14.12.2015 22:02Да не особо. RLE — это оконное сжатие с размером окна, равным единице и кодированием количества повторений вхождения, вместо длины совпадения (поскольку длина совпадения либо 0, либо 1).
masai
14.12.2015 22:18Мы, наверное, по-разному понимаем похожесть. В RLE нет словаря, а это важная отличительная особенность алгоритмов LZ*. И обратно, в LZ77 нет счётчика повторений.
Непонятна роль единичного окна, если всё равно мы кодируем длины цепочек, выходящих за его пределы. А когда мы заменяем длину совпадения количеством повторений, мы выбрасываем последний оставшийся элемент LZ77.
Впрочем, это не так уже и важно всё. Просто глаз за фразу зацепился.akk025
14.12.2015 22:41+2Я тоже так думал еще со студенческих времен. А теперь попробуйте посмотреть по-другому. Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности. RLE копирует последовательность из одного символа много раз, LZ77 — последовательность многих символов один раз. Можно даже написать общий код, так, чтобы выбор алгоритма свелся к заданию параметров.
masai
15.12.2015 16:14Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности.
А, ну если так классифицировать, то согласен.
Chulup
15.12.2015 11:29Ткнулся в код, а там…
return (size_t)-1;
Вы серьёзно?
fse
15.12.2015 11:52+1Что случилось, где пожар?
Так, пожалуй, смотрелось бы лучше:
return ~(size_t)0;Chulup
15.12.2015 12:09Да, можно и так. Или вообще сделать константу отдельную…
Но это не особо важно — работает, значит, нормально.
Я другое хотел спросить: где прочитать про 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; }akk025
15.12.2015 23:38Могу выслать архив с исходниками. Мы пока не придумали, как вычленить из проприетарного гита конкретно этот модуль так, чтобы не менять систему сборки всех зависимых от него проектов. Если останутся вопросы — прокомментирую. На выходе появится статья в журнал.
knagaev
15.12.2015 16:09По названию статьи вспомнился сериал «Альф», где одноимённый главный герой рассказывал рецепт котиного сока.
«Берёшь кота и соковыжималку...», дальше на него махали руками и окончание рецепта неизвестно.
P.S. В сериале ни один кот не пострадал.
Hydro
А где же картинка с котом?
DrPass
Ещё в процессе разжатия, видимо.
radiolok
Кот, да не тот.
Кстати спасибо за интересный метод. У меня изображения были сильно меньше, но большим количеством. Приходилось использовать внешнюю flash — на контроллер оно и так и так не влезло бы, а с 1Мб флешкой смысла сжимать и не было.