La représentation des flux de bits en un flux d'octets

Question

J'expérimente des idées dont les algorithmes doivent travailler sur les bits que leur plus petite unité d'information. Ceci est une application modulaire où l'utilisateur peut réorganiser les parties du « pipeline » comme un pipeline shell unix. Ces algorithmes font différentes choses comme le cadrage, la compression, la décompression, la vérification des erreurs et la correction; l'introduction, la détection et la suppression du bruit, etc.

Comme ils travaillent au niveau binaire, les algorithmes peuvent, par exemple, prendre 5 bits d'entrée et produire 19 bits de sortie. L'entrée et la sortie sont rarement multiples d'octets.

Travailler avec le bit flux en mémoire et entre les fils est très bien avec l'aide de std::vector<bool>, mais je dois récupérer et stocker ce flux de bits de / à quelque part, et de préférence, il devrait être possible de faire des pipelines de ligne de commande réelle comme :

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

Ou même:

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

Le problème est comment sérialiser ces bits de manière efficace, étant donné que les flux standards (stdin et stdout) sont orienté octet. Je dois situations de poignée lorsque le nombre de bits dans l'entrée et la sortie ne sont pas multiple d'un octet.

À l'heure actuelle, j'ai une preuve de concept de travail qu'il fait en augmentant chaque bit à un octet qui est soit 0x30 ou 0x31 ( « 0 » ou « 1 »). De toute évidence, ce qui augmente la taille des données par un facteur de huit, la consommation de 8 x plus d'espace et de bande passante que nécessaire. Je voudrais avoir ces bits emballés d'une manière plus efficace.

Une alternative que j'envisage est un protocole qui tamponne les bits de la sortie et produit des blocs constitués d'un Longueur en-tête suivi par plafond (Longueur / 8) octets de données, la sortie de rinçage chaque fois que nécessaire.

Mais au lieu de créer un maquillé protocole, je voudrais savoir si quelqu'un avait déjà ces exigences, quelles sont vos expériences, et s'il y a déjà un protocole standard pour ce (sérialisation d'un nombre arbitraire de bits) que je pouvais utiliser. Peut-être que quelqu'un avait déjà ce problème et utilise déjà une certaine forme de codage qui pourrait également être utilisé dans cette application, afin d'éviter la prolifération des formats incompatibles.

Answer 1

  

protocole tampons les bits de la sortie et produit des blocs constitués d'un en-tête de longueur suivie plafond (Longueur / 8) octets de données, la sortie de rinçage chaque fois que nécessaire.

Ceci est typique. Il n'y a pas vraiment de solutions de rechange qui serait convenablement simple.

sérialisation de bits - en tant que bits - est rare. index Bitmap sont sur le seul exemple qui me vient à l'esprit.

Le langage de programmation Pascal codé toutes les chaînes avec une longueur suivie par les octets de la chaîne. Vous faites une chose semblable, sauf les bits de, pas d'octets.

Ceci est similaire à « encodage RLE » où séries de valeurs identiques sont remplacées par un en-tête et les octets. L'algorithme PackBits, par exemple, est un RLE simple qui fournit tête et données. Il fonctionne au niveau de l'octet (et non le niveau du bit), mais il est essentiellement le même modèle de conception.