Представление потоков битов в потоке байтов

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) байты данных, сбрасывая выходные данные при необходимости.

Но вместо того, чтобы создавать протокол составления, я хотел бы знать, если у кого-то уже были эти требования, каков ваш опыт, и есть ли уже какой-то стандартный протокол для этого (сериализация произвольного числа битов), который я мог бы использовать. Возможно, кто-то уже имел эту проблему и уже использует некую форму кодирования, которая также может использоваться в этом приложении, чтобы избежать распространения несовместимых форматов.

Answer 1

протокол, который буферизует биты на выходе и генерирует блоки, состоящие из заголовка длины, за которым следуют верхние (длина /8) байты данных, сбрасывая выходные данные при необходимости.

Это типично. На самом деле нет никаких альтернатив, которые были бы достаточно простыми.

Сериализация битов - как битов - редка. Растровые индексы - это единственный пример, который приходит на ум.

Язык программирования Pascal кодирует все строки длиной, за которой следуют байты строки. Вы делаете похожую вещь, кроме битов, а не байтов.

Это похоже на "кодирование длин серий", где последовательности идентичных значений заменяются заголовком и байтами. Например, алгоритм PackBits - это простая RLE, которая предоставляет заголовок плюс данные. Он работает на уровне байтов (не на уровне битов), но по сути это тот же шаблон проектирования.