そこで私たちは課題に直面しました：「平らな猫を絞る方法」？ なんで猫？ はい、彼らはシールでテストしたので、他に何を白黒写真をチェックしますか。 ドル札ではありません。
最初の答えは、猫RLEを絞ってみましょう。 猫は平らです...それは、平らな色-ちょうど4つの色合いです。 画面には多くの空の場所があります。 繰り返しピクセルは地獄になります。 縮小する必要があります。
縮小する必要があります-縮小します。 唯一の難しさは、圧縮方法を気にせず、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も同様に行うと判断しました。中間ストレージを使用せずにストリーミング方式でデータを圧縮解除する方法を見つける必要があります。 思い付く。 次のようになりました。
埋め込み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; }
特に、圧縮解除のフットプリントが約150バイト（アルゴリズムの「ウィンドウ」が127バイトの場合）に満足しています。 当初、Lempel-Zivアルゴリズムでは、辞書にメモリを割り当てる必要性に非常に戸惑っていました。 RLEは完全に不要な辞書です...しかし、150バイトは私たちを怖がらせません。
別のことは私たちを驚かせました：LZ77はRLEの一般化であるという理論から知られているにもかかわらず、2番目を1番目に置き換えると統計誤差の限界の結果が改善されました： 。
彼らはエントロピー法について考え始めました：ハフマン、算術コーディングは、いくつかのプロトタイプを書きました...彼らは思いつきませんでした。 すべての圧縮解除プログラムには、かなりまともなテーブルが必要です。私たちの基準では、それはかなり下品です。
それから...そして、RLE経由でスキャンバック圧縮を開始しました。 そして、見よ、3〜4の圧縮率は、「猫の流ffiさ」、つまり画像の平坦な色の度合いとグラデーション領域の数に応じて7〜10に跳ね上がりました。 あなたは生きることができます。 そして、最も重要なことは、RLE + SBは1回のパスでストリームコンプレッサーによって完全に解凍されます。
このように：
Stream Decompressor RLE +スキャンバック
/****************************************************************************/ /* 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ライセンスに従います）。 突然、壊滅的なメモリ不足とプロセッサリソースの状態で何かを解く必要もあります。