coincidencia de patrón de bits y sustitución

Question

Me encuentro con un problema muy complicado con la manipulación de bits.

Hasta donde yo sé, el tamaño variable más pequeño para mantener un valor es de un byte de 8 bits. Las operaciones de bit disponibles en C/C++ se aplican a una unidad completa de bytes.

Imagine que tengo un mapa para reemplazar un patrón binario 100100 (6 bits) con una señal 10000 (5 bits). Si el 1er byte de los datos de entrada de un archivo es 10010001 (8 bits) almacenado en una variable char, parte de él coincide con el patrón de 6 bits y, por lo tanto, será reemplazado por la señal de 5 bits para dar un resultado de 1000001 (7 bits) .

Puedo usar una máscara para manipular los bits dentro de un byte para obtener un resultado de los bits más a la izquierda en 10000 (5 bits) pero los 3 bits más a la derecha se vuelven muy difíciles de manipular. No puedo desplazar los 3 bits más a la derecha de los datos originales para obtener el resultado correcto 1000001 (7 bit) seguido de 1 bit de relleno en esa variable char que se debe completar con el 1er bit del siguiente byte seguido de la entrada.

Me pregunto si C/C++ realmente puede hacer este tipo de reemplazo de patrones de bits de longitud que no encajan en una variable Char (1 byte) o incluso Int (4 bytes). ¿Puede C/C++ hacer el truco o tenemos que buscar otros lenguajes de ensamblaje que se ocupen de manipulaciones de bits individuales?

Escuché que Power Basic puede realizar la manipulación bit por bit mejor que C/C++.

Answer 1

• << shiftleft
• ^ XOR
• >> desplazamiento a la derecha
• ~ el complemento a uno

El uso de estas operaciones, fácilmente se podría aislar las piezas que le interesan y compararlos como enteros.

dicen que el byte 001000100 y usted quiere comprobar si contiene 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; 
    } 
} 

Este es un código muy vaga, simplemente pretende ser una demostración.

Answer 2

Si el tiempo y el espacio no son importantes, puede convertir los bits en una representación de cadena y realizar sustituciones en la cadena, luego volver a convertir cuando sea necesario. No una solución elegante pero que funciona.

Answer 3

Me pregunto si C/C++ en realidad puede hacer esto especie de sustitución de patrones de bits de longitud que no encajan en un Char (1 byte) variable o incluso Int (4 bytes).

¿Qué pasa con std :: bitset?

Answer 4

Utilice vector<bool> si puede leer sus datos en el vector principalmente a la vez. Sin embargo, puede ser más difícil encontrar y reemplazar secuencias de bits.

Answer 5

Aquí hay una pequeña clase de lector que puede satisfacer sus necesidades. Por supuesto, es posible que desee crear un escritor de bits para su caso de uso.

#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 6

Si entendí sus preguntas correctamente, tienen un flujo de entrada y de salida y corriente y que desea reemplazar los 6bits de la entrada con 5 en la salida - y su salida aún debe haber un flujo de bits?

Por lo tanto, se puede aplicar la regla más importante del programador: ¡Divide et impera! Usted debe dividir su componente en tres partes: convertidor de corriente

1. de entrada: Convertir todos los patrones en el flujo de entrada a una matriz de caracteres búfer (anillo). Si te entendí correctamente, tus "comandos" de entrada tienen una longitud de 8 bits, por lo que no hay nada de especial en esto.

2. Realice la sustitución en el buffer anular de forma que reemplace todos los patrones de 6 bits con el de 5 bits, pero "rellene" los 5 bits con un cero inicial, de modo que la longitud total sea de 8 bits.

3. Escriba un controlador de salida que lea desde el búfer de anillo y permita que este controlador de salida solo escriba los 7 LSB en el flujo de salida de cada byte de entrada. Por supuesto, un poco de manipulación es necesaria de nuevo para esto. Si el tamaño de búfer de anillo se puede dividir por 8 y 7 (= es un múltiplo de 56) tendrá un buffer limpia al final y puede comenzar de nuevo con 1.

La forma más sencilla de implementar esto es para iterar sobre estos 3 pasos siempre que los datos de entrada estén disponibles.

Si un rendimiento realmente importa y está ejecutando en una CPU multi-core, incluso podría dividir los pasos y 3 hilos, pero luego debe sincronizar cuidadosamente el acceso al buffer de anillo.

Answer 7

Creo que lo siguiente hace lo que quiere.

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); 
    } 

}

Se puede usar un interruptor o un bucle en el medio para comprobar el candidato contra múltiples patrones. Puede que tenga que haber un manejo especial después de hacer una sustitución para garantizar que el patrón de reemplazo no se vuelva a verificar para buscar coincidencias.