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

Question

Я экспериментирую с некоторыми идеями, в которых алгоритмы должны работать над битами в качестве самой маленькой единицы информации. Это модульное приложение, в котором пользователь может изменить части «трубопровода», как трубопровод Shell 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, который предоставляет данные заголовка плюс. Он работает на уровне байта (не на уровне битов), но по сути такая же шаблон дизайна.