凍えるような冬の季節に…ちょうど一年前、私たちは簡単な仕事をしました。 電子インクの画面があり、16 MHzのプロセッサがあります（はい、組み込み電子機器、特に超低消費電力、そういったものもあります）。メモリはまったくありません。 まあ、つまり キロバイトの8 RAMおよび256フラッシュ。 キロバイト、カール。 そして、これらの退屈なキロバイトでは、800 x 600の画像を4つのグレーの濃淡で押し出す必要があります。 頭の中で800×600と2ビット/ピクセルをすばやく乗算すると、12万バイトになります。 何かが合わない。 圧縮する必要があります。
そこで私たちは課題に直面しました：「平らな猫を絞る方法」？ なんで猫？ はい、彼らはシールでテストしたので、他に何を白黒写真をチェックしますか。 ドル札ではありません。
最初の答えは、猫
RLEを絞ってみましょう。 猫は平らです...それは、平らな色-ちょうど4つの色合いです。 画面には多くの空の場所があります。 繰り返しピクセルは地獄になります。 縮小する必要があります。
縮小する必要があります-縮小します。 唯一の難しさは、圧縮方法を気にせず、PCまたはサーバーで圧縮することです。 しかし、ストリーミング方式で順次アンロックする必要があります。バイトを引き出し、バイトを削除しました。 8キロバイトのRAMにはビデオバッファがありません。解凍された猫を保存する場所はありません。
管理されています。 猫は縮んでいます。
RLE圧縮 #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変更による圧縮（スキャンバックアルゴリズム） #include "scanback.h" extern "C" { #include "bitmem.h" } using namespace Componentality::Common;
特に、圧縮解除のフットプリントが約150バイト（アルゴリズムの「ウィンドウ」が127バイトの場合）に満足しています。 当初、Lempel-Zivアルゴリズムでは、辞書にメモリを割り当てる必要性に非常に戸惑っていました。 RLEは完全に不要な辞書です...しかし、150バイトは私たちを怖がらせません。
別のことは私たちを驚かせました：LZ77はRLEの一般化であるという理論から知られているにもかかわらず、2番目を1番目に置き換えると統計誤差の限界の結果が改善されました： 。
彼らはエントロピー法について考え始めました：ハフマン、算術コーディングは、いくつかのプロトタイプを書きました...彼らは思いつきませんでした。 すべての圧縮解除プログラムには、かなりまともなテーブルが必要です。私たちの基準では、それはかなり下品です。
それから...そして、RLE経由でスキャンバック圧縮を開始しました。 そして、見よ、3〜4の圧縮率は、「猫の流ffiさ」、つまり画像の平坦な色の度合いとグラデーション領域の数に応じて7〜10に跳ね上がりました。 あなたは生きることができます。 そして、最も重要なことは、RLE + SBは1回のパスでストリームコンプレッサーによって完全に解凍されます。
このように：
Stream Decompressor RLE +スキャンバック #include "rlesbc.h" using namespace Componentality::Common;
今から一年、私たちの猫は、すべてのZLIBにもかかわらず、完全に「ほぼ完全に無意識」に生きています。 もちろん、これはより厳しく迫られていますが、消費するリソースは比類なきものです。 それまでの間、RLE + SBは他の多くのタスクに最適であることがわかりました。たとえば、透明度やアンチエイリアス、ネットワークテキストトラフィックなど、ビットマップフォントを完全に圧縮します。 当然のことながら、圧縮率は2.5〜6ですが、特に圧縮解除のためにリソースはほとんど消費されません。これは、通常、より頻繁に実行され、メモリ速度にとって非常に重要です。
そこで私たちは、コードをパブリックドメインに配置しないことを決定しました（
MITライセンスに従います）。 突然、壊滅的なメモリ不足とプロセッサリソースの状態で何かを解く必要もあります。