Repräsentation von Bitströmen in einem Bytestrom

Question

Ich experimentiere mit einigen Ideen, bei denen Algorithmen als kleinste Informationseinheit an Bits arbeiten müssen. Dies ist eine modulare Anwendung, bei der der Benutzer Teile der "Pipeline" wie eine Unix -Shell -Pipeline neu ordnen kann. Diese Algorithmen machen verschiedene Dinge wie Framing, Komprimierung, Dekompression, Fehlerprüfung und Korrektur; Einführung, Erfassen und Entfernen von Rauschen usw.

Da sie auf der Bitpegel arbeiten, können die Algorithmen beispielsweise 5 Eingangsbits aufnehmen und 19 Bit Ausgang produzieren. Der Eingang und die Ausgabe sind selten mehrfach Bytes.

Die Arbeit mit Bit -Streams im Speicher und zwischen Threads ist mit Hilfe von in Ordnung std::vector<bool>, Aber ich muss diesen Strom von Bits von/bis irgendwo abrufen und speichern, und vorzugsweise sollte es möglich sein, tatsächliche Befehlszeilenpipelines durchzuführen, wie:

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

Oder auch:

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

Das Problem ist, wie diese Bits seit den Standardströmen effizient serialisieren können (stdin und stdout) sind byteorientiert. Ich muss Situationen bewältigen, in denen die Anzahl der Bits im Eingang und die Ausgabe kein Vielfaches eines Byte ist.

Derzeit habe ich einen funktionierenden Proof-of-Concept, der es tut, indem ich jedes Bit auf ein Byte erweitert, das entweder 0x30 oder 0x31 ("0" oder "1") ist. Dies erhöht eindeutig die Datengröße um den Faktor von acht und verbraucht 8 × mehr Raum und Bandbreite als nötig. Ich möchte, dass diese Teile effizienter gepackt werden.

Eine Alternative, die ich nachdenke, ist ein Protokoll, das die Bits im Ausgang puffern und Blöcke erzeugt, die aus a bestehen Länge Header gefolgt von Decke (Länge/8) Datenbytes, die Ausgabe nach Bedarf spülen.

Aber anstatt ein erfundenes Protokoll zu erstellen, möchte ich wissen, ob jemand diese Anforderungen bereits hatte, welche Erfahrungen sind und ob es bereits ein Standardprotokoll dafür gibt (Serialisierung einer willkürlichen Anzahl von Bits), die ich könnte verwenden. Vielleicht hatte jemand dieses Problem bereits und verwendet bereits eine Form von Codierung, die auch in dieser Anwendung verwendet werden könnte, um die Verbreitung von inkompatiblen Formaten zu vermeiden.

Answer 1

Protokoll, das die Bits in der Ausgabe puffern und Blöcke erzeugt, die aus einem Längenheader bestehen, gefolgt von der Decke (Länge/8) Bytes von Daten, wobei die Ausgabe bei Bedarf spülen.

Dies ist typisch. Es gibt keine wirklich einfachen Alternativen.

Die Serialisierung von Bits - als Bits - ist selten. Bitmap -Indizes handelt von dem einzigen Beispiel, das mir in den Sinn kommt.

Die Pascal -Programmiersprache kodierte alle Zeichenfolgen mit einer Länge, gefolgt von den Bytes der Zeichenfolge. Du machst etwas Ähnliches, außer es sind Teile, keine Bytes.

Dies ähnelt der "Langlänge-Codierung", bei der die laufenden Läufe identischer Werte durch einen Header und die Bytes ersetzt werden. Der Packbits -Algorithmus ist beispielsweise eine einfache RLE, die Header Plus -Daten liefert. Es funktioniert auf der Byte -Ebene (nicht auf der Bitstufe), aber es ist im Wesentlichen dasselbe Designmuster.