バイトストリーム内のビットストリームを表現する

Question

私は、アルゴリズムが情報の最小単位としてビットを処理する必要があるといういくつかのアイデアを実験しています。これは、ユーザーが Unix シェル パイプラインのように「パイプライン」の一部を再配置できるモジュール式アプリケーションです。これらのアルゴリズムは、フレーム化、圧縮、解凍、エラー チェックと修正などのさまざまな処理を実行します。ノイズの導入、検出、除去など。

アルゴリズムはビット レベルで動作するため、たとえば 5 ビットの入力を受け取り、19 ビットの出力を生成します。入力と出力がバイトの倍数になることはほとんどありません。

メモリ内およびスレッド間のビット ストリームの操作は、次の助けを借りて問題なく実行できます。 std::vector<bool>, ただし、このビットストリームをどこかから取得して保存する必要があり、できれば次のような実際のコマンドラインパイプラインを実行できる必要があります。

prog1 < bitsource.dat | prog2 -opts | prog3 -opts > bitsink.dat

あるいは：

prog1 | prog2 | ssh user@host /bin/sh -c "prog3 | prog4 > /dev/dsp"

問題は、標準ストリーム (stdin そして stdout) はバイト指向です。入力と出力のビット数がバイトの倍数ではない状況に対処する必要があります。

現在、私は各ビットを 0x30 または 0x31 (「0」または「1」) のバイトに拡張することで動作する概念実証を行っています。明らかに、これによりデータのサイズが 8 倍に増加し、必要なスペースと帯域幅の 8 倍が消費されます。これらのビットをより効率的な方法で詰め込みたいと考えています。

私が検討している代替手段の 1 つは、出力内のビットをバッファリングし、次の要素からなるブロックを生成するプロトコルです。 長さ ヘッダーに続いて 天井(長さ/8) 必要に応じて出力をフラッシュします。

しかし、でっち上げのプロトコルを作成するのではなく、誰かがすでにこれらの要件を満たしているかどうか、あなたの経験は何ですか、また、このための標準プロトコル (任意の数のビットのシリアル化) が既に存在するかどうかを知りたいのです。使用。おそらく誰かがすでにこの問題を抱えており、互換性のない形式の蔓延を避けるために、このアプリケーションでも使用できる何らかの形式のエンコーディングを使用している可能性があります。

Answer 1

出力内のビットをバッファリングし、長さヘッダーとそれに続く天井(長さ/8) バイトのデータで構成されるブロックを生成し、適切な場合にはいつでも出力をフラッシュするプロトコルです。

これは典型的なものです。適切にシンプルな代替手段は実際にはありません。

ビットをビットとしてシリアル化することはまれです。ビットマップ インデックスは、思い浮かぶ唯一の例です。

Pascal プログラミング言語は、すべての文字列を長さの後に文字列のバイトを続けてエンコードしました。バイトではなくビットである点を除いて、同様のことを行っています。

これは、同じ値の連続がヘッダーとバイトに置き換えられる「ランレングス エンコーディング」に似ています。たとえば、Pac​​kBits アルゴリズムは、ヘッダーとデータを提供する単純な RLE です。これは (ビット レベルではなく) バイト レベルで機能しますが、本質的には同じ設計パターンです。