Rappresentando flussi di bit in un flusso di byte

Question

sto sperimentando con alcune idee in cui gli algoritmi devono lavorare su pezzi come il loro più piccola unità di informazioni. Questa è un'applicazione modulare in cui l'utente può riordinare parti del "pipeline" come una pipeline unix shell. Questi algoritmi varie cose, come framing, compressione, decompressione, controllo di errore e correzione; introdurre, rilevando e rimuovendo il rumore, ecc.

Poiché lavorano sul livello di bit, gli algoritmi possono, per esempio, prendere 5 bit di ingresso e produrre 19 bit di uscita. L'ingresso e l'uscita sono raramente multiplo di byte.

Lavorare con il bit stream in memoria e tra i thread va bene con l'aiuto di std::vector<bool>, ma devo recuperare e conservare questo flusso di bit da / a da qualche parte, e, preferibilmente, dovrebbe essere possibile fare effettive condutture della riga di comando come :

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

O ancora:

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

Il problema è come serializzare questi bit efficiente, poiché i flussi standard (stdin e stdout) sono byte-oriented. Devo situazioni manico in cui il numero di bit in ingresso e uscita non sono più di un byte.

Attualmente, ho un proof-of-concept di lavoro che lo fa ampliando ogni bit a un byte che è o 0x30 o 0x31 ( "0" o "1"). Chiaramente, questo aumenta la dimensione dei dati da un fattore di otto, consumando altri 8 × spazio e banda del necessario. Mi piacerebbe avere questi bit confezionati in modo più efficiente.

Un'alternativa che sto considerando è un protocollo che buffer i bit in uscita e produce blocchi costituiti da un Length intestazione seguiti da soffitto (lunghezza / 8) byte di dati, vampate sull'uscita quando appropriato.

Ma invece di creare un made-up-protocollo, vorrei sapere se qualcuno aveva già questi requisiti, quali sono le tue esperienze, e se c'è già un protocollo standard per questo (la serializzazione di un numero arbitrario di bit) che ho potuto usare. Forse qualcuno già ha avuto questo problema e sta già utilizzando una qualche forma di codifica che potrebbe essere utilizzato anche in questa applicazione, al fine di evitare la proliferazione di formati incompatibili.

Answer 1

protocollo buffer i bit in uscita e produce blocchi costituiti da un Length seguita da soffitto (lunghezza / 8) byte di dati, vampate sull'uscita quando appropriato.

Questo è tipico. Non ci sono davvero alternative che sarebbero adeguatamente semplice.

La serializzazione di bit - come bit - è rara. Gli indici bitmap sono circa l'unico esempio che viene in mente.

Il linguaggio di programmazione Pascal codificato tutte le stringhe di lunghezza seguito dai byte della stringa. Stai facendo una cosa simile, tranne che di bit, non byte.

Questo è simile a "run-length encoding" dove tirature di valori identici sono sostituiti da un'intestazione ei byte. L'algoritmo PackBits, per esempio, è un semplice RLE che fornisce intestazione più dati. Funziona a livello di byte (non il livello di bit), ma è essenzialmente lo stesso modello di progettazione.