Конкатенация бит в C++

Question

Я разрабатываю программное обеспечение для сверточного кодирования и пробивки бит.

Так что в моей программе в каждом цикле генерируется 55-разрядная длина данных. Он хранится в первых 55 битах переменной unsigned long long type. После каждой итерации я должен передать эти 55 бит в буфер unsigned char (буфер довольно большой, скажем, около 500 байтов). Биты должны постоянно храниться в этом буфере. (без пробелов). Есть ли какой-то хитроумный способ, чтобы легко конкатенировать?

Answer 1

EDIT: Мне было правильно указано, что, поскольку я сглаживаю char-buffer через uint64_t*, я нарушаю строгое правило псевдонимов, а также уязвим к ошибкам из-за различий в контенте. Тем не менее, если у вас есть определенные гарантии относительно вашей платформы, это может по-прежнему работать. Его можно решить, имея буфер из 64-битных элементов, хотя вместо одиночных байтов.

Если вам нужен алгоритм barebone, который не зависит от каких-либо внешних библиотек, вы можете использовать нижеприведенный фрагмент. Обратите внимание, что битсет используется только для отображения результата и убедитесь, что он работает.

В качестве теста я определил 55-битный шаблон, состоящий из 54 последовательных 1, а затем 0. Остальные 9 бит в 64-битном значении (x) также являются нулями. Буфер представляет собой 500-байтовый массив символов, который я сгенерировал в uint64_t*. Алгоритм отслеживает текущий 64-разрядный блок (currentBlock) и текущий бит в этом блоке (currentBit). Он выполняет следующие действия:

1. Сдвиньте битпаттерс таким образом, чтобы он начинался с текущего битового положения.
2. ИЛИ результат с текущим 64-битным блоком. Это означает, что первая часть битового шаблона конкатенируется с тем, что осталось от текущего блока. Например, во второй итерации, когда первые 55 бит первого блока заполняются, остальные 9 бит будут заняты.
3. Обновить переменную currentBit.

4. Проверьте, не было ли переполнено currentBlock, если оно переместится на следующий блок и соедините оставшуюся часть 55-битного шаблона.

   #include <iostream> 
   #include <bitset> // only used for testing, not for the algorithm 
   using namespace std; 
   
   int main() 
   { 
       size_t nBits = 55; 
   
       // 54 1's, followed by 10 0's 
       uint64_t x = 0b1111111111111111111111111111111111111111111111111111110000000000; 
   
       // 500 byte buffer: 
       char buf8[500]{}; 
       uint64_t *buf = reinterpret_cast<uint64_t*>(&buf8[0]); 
   
       // This would be better; use this if possible 
       // uint64_t buf[100]; 
   
       int currentBit = 0; 
       int currentBlock = 0; 
   
       // concatenate the 55-bitpattern 10 times 
       for (int i = 0; i != 10; ++i) 
       { 
        buf[currentBlock] |= (x >> currentBit); 
   
        currentBit += nBits; 
        if (currentBit >= 64) 
        { 
         ++currentBlock; 
         currentBit %= 64; 
   
         buf[currentBlock] |= x << (nBits - currentBit); 
        } 
       } 
   
       // TEST 
       for (int i = 0; i != 5; ++i) 
        cout << bitset<64>(buf[i]) << '\n'; 
   } 
   

Вы, вероятно, следует обобщить это и инкапсулировать его в функции. Это зависит от вас. Программа as производит следующие данные:

1111111111111111111111111111111111111111111111111111110111111111 
1111111111111111111111111111111111111111111110111111111111111111 
1111111111111111111111111111111111110111111111111111111111111111 
1111111111111111111111111110111111111111111111111111111111111111 
1111111111111111110111111111111111111111111111111111111111111111 

Обратите внимание на отметку 0 каждого 55-го бита.

Answer 2

Я написал этот класс некоторое время назад, когда мне нужно было разбираться с битами. Это может быть полезно и вам. Вот оно:

#include <deque> 
#include <vector> 
#include <algorithm> 

class bitStream { 
public: 
    bitStream() {} 

    /// Copies the data from another bitStream into this one upon construction 
    bitStream(const bitStream& bStream, bool reverse=false) { 
     this->appendData(bStream, reverse); 
    } 

    /// Copies the data from a vector of booleans upon construction 
    bitStream(const vector<bool>& vec, bool reverse=false) { 
     this->appendData(vec, reverse); 
    } 

    /// Appends data to the stream from a uint64_t type. The lower-n bits will be appended, starting with the highest bit of those by default. 
    void  appendData(uint64_t data, size_t n, bool reverse=false) { 
     deque<bool> _buffer; 
     n = (n>64)?64:n; 
     for (int i=0; i<n; i++) { 
      _oneBit tmp; 
      tmp.data = data; 
      _buffer.push_back(tmp.data); 
      data >>= 0x1; 
     } 
     if (!reverse) std::reverse(_buffer.begin(), _buffer.end()); 
     for (const auto v: _buffer) _data.push_back(v); 
    } 

    /// Appends data to the stream from a C-style array of booleans 
    void  appendData(bool* data, size_t n, bool reverse=false) { 
     if (reverse) { 
      for (int i=0; i<n; i++) this->appendBit(*(data+(n-i-1))); 
     } else { 
      for (int i=0; i<n; i++) this->appendBit(*(data+i)); 
     } 
    } 

    /// Appends data to the stream from a vector of booleans 
    void  appendData(const vector<bool>& vec, bool reverse=false) { 
     if (reverse) { 
      for (auto i = vec.size()-1; vec.size() > i; --i) this->appendBit(vec.at(i)); 
     } else { 
      for (const auto& v : vec) this->appendBit(v); 
     } 
    } 

    /// Appends a single bit 
    void  appendBit(bool bit) { 
     _data.push_back(bit); 
    } 

    /// Appends the bits from another bitStream object to this one 
    void  appendData(const bitStream& bStream, bool reverse=false) { 
     if (!bStream.getSize()) return; 
     if (reverse) { 
      for (int i=0; i<bStream.getSize(); i++) this->appendBit(*(bStream.getData()+(bStream.getSize()-i-1))); 
     } else { 
      for (int i=0; i<bStream.getSize(); i++) this->appendBit(*(bStream.getData()+i)); 
     } 
    } 

    /// Returns a pointer to the begining of the data (read-only!) 
    const bool* getData() const { return &_data.front(); } 

    /// Reference to the bit at a specified position (assignable, but at lest n+1 elements must exist before calling!) 
    bool& operator[] (size_t n) { 
     if (n>_data.size()-1) throw runtime_error("Out of range!"); 
     return _data.at(n); 
    } 

    /// Fills your vector with the data chopped up into "sizeof(T)"-byte pieces. 
    template <typename T> 
    void  getDataAsVector(vector<T>& vec) { 
     vec.clear(); 
     size_t oSize = sizeof(T)*8; 
     T tmp = 0x0; 
     for (int i=0; i<_data.size(); i++) { 
      if (!(i%oSize) && i) { 
       vec.push_back(tmp); 
       tmp = 0x0; 
      } 
      tmp <<= 0x1; 
      tmp |= _data[i]; 
     } 
     vec.push_back(tmp); 
    } 

    /// Returns the number of bits that are stored 
    size_t  getSize() const { return _data.size(); } 

    /// Reverses the stored bits 
    void  reverse() { std::reverse(_data.begin(), _data.end()); } 
private: 
    deque<bool> _data; 
    struct _oneBit { 
     uint8_t data:1; 
    }; 
}; 

Это довольно тривиально использовать, поэтому я не стал писать пример.

Прежде всего, я никогда не использовал его в проекте, поэтому там могут быть некоторые ошибки (я помню только его тестирование очень кратко), плюс он еще не закончен полностью (существует несколько возможных конструкторов что я не реализовал). Кроме того, несмотря на название «поток», он не имеет ничего общего с потоком на C++.

Таким образом, в основном это позволяет хранить бит.Биты, которые вы вставляете в него, будут храниться на смежных адресах памяти (да, это один бит на каждый бит памяти, но что угодно), которые остаются неизменными для времени жизни объекта (это связано с тем, что deque не перераспределяет себя в отличие от vector)! Вы можете добавлять биты к нему различными способами (из разных источников данных, в обратном или обратном порядке) и читать их в разных формах. В вашем случае функция appendData(uint64_t data, size_t n, bool reverse=false) - это та, которую вы можете использовать, чтобы заполнить ее. Чтобы вернуть данные, вы можете получить vector<char> с данными, нарезанными в 1-байтовые фрагменты (символы), если хотите!

Опять же, пожалуйста, не принимайте это за 100% проверенную и работоспособную вещь. Я только проверил его ненадолго, поэтому вы должны попробовать его и посмотреть, работает ли он для вас! Я думал, что поделюсь им с вами, если вы сочтете это полезным.