Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 16МГц (да-да, во встраиваемой электронике, особенно сверхнизкого энергопотребления, встречаются и такие) и совсем нет памяти. Ну, т.е. килобайтов 8 RAM и 256 Flash. Килобайтов, Карл. И в эти унылые килобайты необходимо запихнуть несколько изображений 800х600 в четырех оттенках серого. Быстро перемножив в уме 800 на 600 и на 2 бита на пиксель получаем 120 тысяч байтов. Несколько не влезает. Надо сжимать.
Так перед нами появилась задача: «как сжать плоского кота»? Почему кота? Да потому, что на котиках тестировали, на чем же еще черно-белые картинки проверять. Не на долларовых банкнотах же.
Первый ответ звучал так: давайте сожмем кота RLE. Кот-то плоский… То есть плоскоцветный — всего четыре оттенка. Пустых мест на экране полно, т.е. повторяющихся пикселей будет до черта. Должно сжиматься.
Должно сжиматься — сжалось. С единственным затруднением: сжимать-то нам все равно как, сжимаем мы на PC, а то и вовсе на сервере. А вот разжимать нам надо последовательно, потоковым образом: байт вытащили — байт вывели. Видеобуфера-то у нас нету на 8 килобайтах RAM, разжатого кота хранить негде.
Справились. Сжимается кот.
/****************************************************************************/ /* Common Utilities Library * (C) Componentality Oy, 2015 */ /****************************************************************************/ /* RLE compression implementation */ /****************************************************************************/ #include "rle.h" #include <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). Вдруг и вам придется что-нибудь разжимать в условиях катастрофической нехватки памяти и процессорного ресурса.
ссылка на оригинал статьи http://habrahabr.ru/post/273047/
Добавить комментарий