En representación de las corrientes de bits en un flujo de bytes

Question

estoy experimentando con algunas ideas en las que los algoritmos tienen que trabajar en bits como su unidad más pequeña de información. Esta es una aplicación modular, donde el usuario puede reorganizar partes de la "pipeline" como una tubería UNIX shell. Estos algoritmos hacen varias cosas como el encuadre, la compresión, descompresión, la comprobación de errores y corrección; la introducción, detección y eliminación de ruido, etc.

Puesto que trabajan en el nivel de bit, los algoritmos puede ser, por ejemplo, tomar 5 bits de entrada y producir 19 bits de salida. La entrada y la salida rara vez son múltiplos de bytes.

Trabajar con flujos de bits en la memoria y entre los hilos está muy bien con la ayuda de std::vector<bool>, pero tengo que recuperar y almacenar esta corriente de bits desde / a en alguna parte, y preferiblemente debería ser posible hacer tuberías de línea de comandos reales como :

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

O incluso:

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

El problema es cómo serializar estos bits de manera eficiente, ya que los flujos estándares (stdin y stdout) están orientados a byte. Tengo a situaciones de mango, donde el número de bits en la entrada y salida no son múltiplo de un byte.

Actualmente, tengo una prueba de concepto de trabajo que lo hace mediante la expansión de cada bit de un byte que es o bien 0x30 o 0x31 ( "0" o "1"). Claramente, esto aumenta el tamaño de los datos por un factor de ocho, consumiendo 8 × más espacio y ancho de banda de lo necesario. Me gustaría tener estos bits empaquetados de una manera más eficiente.

Una alternativa que estoy considerando es un protocolo que tampones los bits en la salida y produce bloques que consisten en un Longitud cabecera seguida por techo (Longitud / 8) bytes de datos, rubor la salida siempre que sea apropiado.

Sin embargo, en lugar de crear un protocolo maquillada, me gustaría saber si alguien ya tenía estos requisitos, ¿cuáles son sus experiencias, y si ya existe algún protocolo estándar para este (serialización de un número arbitrario de bits) que podría utilizar. Tal vez alguien ya tenía este problema y ya está utilizando alguna forma de codificación, que también podría ser utilizado en esta aplicación, para evitar la proliferación de formatos incompatibles.

Answer 1

protocolo que tampones los bits en la salida y produce bloques que constan de una cabecera de longitud seguida por el techo (Longitud / 8) bytes de datos, rubor la salida siempre que sea apropiado.

Esto es típico. En realidad no hay ninguna alternativa que serían adecuadamente sencilla.

serialización de bits - como bits - es raro. índices de mapa de bits son el único ejemplo que me viene a la mente.

El lenguaje de programación Pascal codifica todas las cadenas con una longitud seguido de los bytes de la cadena. Usted está haciendo una cosa similar, excepto que es pedacitos, no bytes.

Esto es similar a "run-length encoding" donde se ejecuta de valores idénticos son sustituidos por una cabecera y los bytes. El algoritmo PackBits, por ejemplo, es un RLE simple que proporciona cabecera más datos. Funciona a nivel de byte (no el nivel de bit), pero es esencialmente el mismo patrón de diseño.