битовое сопоставление и замена

Question

Я сталкиваюсь с очень сложной проблемой с манипулированием битами.

Насколько я знаю, наименьший размер переменной для хранения значения составляет один байт из 8 бит. Битовые операции, доступные в C / C ++, применяются ко всей единице байтов.

Представьте, что у меня есть карта для замены двоичного шаблона 100100 (6 бит) на сигнал 10000 (5 бит). Если 1-й байт входных данных из файла равен 10010001 (8 бит), сохраняемых в переменной типа char, его часть соответствует 6-битному шаблону и поэтому заменяется 5-битным сигналом для получения результата 1000001 (7 бит) ,

Я могу использовать маску для манипулирования битами в байте, чтобы получить результат от самых левых битов до 10000 (5 бит), но самые правые 3 бита очень сложно манипулировать. Я не могу сдвинуть самые правильные 3 бита исходных данных, чтобы получить правильный результат 1000001 (7 бит), за которым следует 1 бит заполнения в этой переменной char, которая должна быть заполнена 1-м битом следующего, за которым следует байта ввода.

Интересно, может ли C / C ++ действительно выполнять такую ​​замену битовых шаблонов длины, которые не вписываются в переменную Char (1 байт) или даже в Int (4 байта). Может ли C / C ++ добиться цели, или мы должны пойти на другие языки ассемблера, которые имеют дело с однобитными манипуляциями?

Я слышал, что Power Basic может выполнять побитовые манипуляции лучше, чем C / C ++.

Answer 1

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

#include <iostream>
#include <sstream>
#include <cassert>

class BitReader {
    public:
        typedef unsigned char BitBuffer;

        BitReader(std::istream &input) :
            input(input), bufferedBits(8) {
        }

        BitBuffer peekBits(int numBits) {
            assert(numBits <= 8);
            assert(numBits > 0);

            skipBits(0);    // Make sure we have a non-empty buffer

            return (((input.peek() << 8) | buffer) >> bufferedBits) & ((1 << numBits) - 1);
        }

        void skipBits(int numBits) {
            assert(numBits >= 0);

            numBits += bufferedBits;

            while (numBits > 8) {
                buffer = input.get();
                numBits -= 8;
            }

            bufferedBits = numBits;
        }

        BitBuffer readBits(int numBits) {
            assert(numBits <= 8);
            assert(numBits > 0);

            BitBuffer ret = peekBits(numBits);

            skipBits(numBits);

            return ret;
        }

        bool eof() const {
            return input.eof();
        }

    private:
        std::istream &input;
        BitBuffer buffer;
        int bufferedBits;   // How many bits are buffered into 'buffer' (0 = empty)
};

Answer 2

Интересно, может ли C / C ++ действительно сделать это? своего рода замена битовых структур длина, которая не вписывается в Char (1 byte) переменная или даже Int (4 байта).

А как насчет std :: bitset?

Answer 3

Если время и пространство не важны, вы можете преобразовать биты в строковое представление и выполнить замену в строке, а затем преобразовать обратно при необходимости. Не элегантное решение, но работающее.

Answer 4

• << смещение
• ^ XOR
• >> сдвиг вправо
• ~ дополнение

Используя эти операции, вы можете легко выделить интересующие вас фрагменты и сравнить их как целые числа.

произнесите байт 001000100, и вы хотите проверить, содержит ли он 1000:

char k = (char)68;
char c = (char)8;
int i = 0;
while(i<5){
    if((k<<i)>>(8-3-i) == c){
        //do stuff
        break;
    }
}

Это очень схематичный код, просто предназначенный для демонстрации.

Answer 5

Я думаю, что следующее делает то, что вы хотите.

PATTERN_LEN = 6
PATTERNMASK = 0x3F //6 bits
PATTERN     = 0x24 //b100100
REPLACE_LEN = 5
REPLACEMENT = 0x10  //b10000


void compress(uint8* inbits, uint8* outbits, int len)
{
  uint16 accumulator=0;
  int nbits=0;
  uint8 candidate; 

  while (len--) //for all input bytes
  {
    //for each bit (msb first)
    for (i=7;i<=0;i--)
    {
      //add 1 bit to accumulator
      accumulator<<=1;
      accumulator|=(*inbits&(1<<i));  
      nbits++;
      //check for pattern
      candidate = accumulator&PATTERNMASK;
      if (candidate==PATTERN)
      {
        //remove pattern
        accumulator>>=PATTERN_LEN; 
        //add replacement
        accumulator<<=REPLACE_LEN; 
        accumulator|=REPLACMENT;
        nbits+= (REPLACE_LEN - PATTERN_LEN);
      }
    }
    inbits++;
    //move accumulator to output to prevent overflow
    while (nbits>8)
    {
      //copy the highest 8 bits
      nbits-=8;      
      *outbits++ = (accumulator>>nbits)&0xFF;
      //clear them from accumulator
      accumulator&= ~(0xFF<<nbits);
    }
  }
  //copy remainder of accumulator  to output
  while (nbits>0)
  {
    nbits-=8;
    *outbits++ = (accumulator>>nbits)&0xFF;
    accumulator&= ~(0xFF<<nbits);
  }

}

Вы можете использовать переключатель или цикл в середине, чтобы проверить кандидата на наличие нескольких шаблонов. После выполнения замены может потребоваться специальная обработка, чтобы убедиться, что шаблон замены не перепроверяется на совпадения.

Answer 6

Если я правильно понял ваши вопросы, у вас есть входной поток и выходной поток, и вы хотите заменить 6 битов ввода на 5 на выходе - и ваш вывод все еще должен быть битовым потоком?

Итак, самое важное правило программиста может быть применено: Divide et impera! Вы должны разделить ваш компонент на три части:

1. Преобразователь входного потока: преобразуйте каждый шаблон во входном потоке в буфер массива символов (кольца). Если я правильно вас понял, ваши входные «команды» имеют длину 8 бит, поэтому в этом нет ничего особенного.

2. Выполните замену в кольцевом буфере таким образом, чтобы вы заменяли каждый соответствующий 6-битный шаблон на 5-битный, но «дополняли» 5-бит начальным нулем, поэтому общая длина по-прежнему составляет 8 бит.

3. Написать обработчик вывода, который читает из кольцевого буфера, и позволить этому обработчику вывода записывать только 7 LSB в выходной поток из каждого входного байта. Конечно, некоторые манипуляции снова необходимы для этого. Если ваш размер кольцевого буфера можно разделить на 8 и 7 (= кратно 56), у вас будет чистый буфер в конце, и вы можете начать снова с 1.

Самый простой способ реализовать это - выполнить эти 3 шага, пока доступны входные данные.

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

Answer 7

Используйте vector<bool>, если вы можете прочитать свои данные в вектор в основном за один раз. Однако может быть сложнее найти и заменить последовательности битов.