correspondance de bit et remplacement

Question

Je rencontre un problème très délicat avec la manipulation de bits. Pour autant que je sache, la plus petite taille variable pour contenir une valeur est un octet de 8 bits. Les opérations de bits disponibles en C/C++ s'appliquent à une unité entière d'octets. Imaginez que j'ai une carte pour remplacer un schéma binaire 100100 (6 bits) avec un signal de 10000 (5 bits). Si le 1er octet des données d'entrée d'un fichier est 10010001 (8 bits) étant stocké dans une variable char, une partie de celui-ci correspond au modèle 6 bits et est donc remplacé par le signal 5 bits pour donner un résultat de 1000001 (7 bits) .

Je peux utiliser un masque pour manipuler les bits dans un octet pour obtenir un résultat des bits les plus à gauche à 10000 (5 bits), mais les 3 bits les plus à droite deviennent très difficiles à manipuler. Je ne peux pas décaler les 3 bits les plus à droite des données d'origine pour obtenir le résultat correct 1000001 (7 bits) suivi par 1 bit de remplissage dans cette variable char qui doit être rempli par le 1er bit de l'octet d'octet suivant suivi. Je me demande si C/C++ peut réellement faire ce genre de remplacement de modèles de bits de longueur qui ne tiennent pas dans une variable Char (1 octet) ou même Int (4 octets). Est-ce que le C/C++ peut faire l'affaire ou nous devons opter pour d'autres langages d'assemblage qui traitent des manipulations à un seul bit?

J'ai entendu que Power Basic peut être capable de faire la manipulation bit par bit mieux que C/C++.

Answer 1

• << shiftleft
• ^ XOR
• >> décalage vers la droite
• ~ complément à un

L'utilisation de ces opérations, vous pouvez facilement isoler les pièces qui vous intéressent et de les comparer comme entiers.

dire l'octet 001000100 et que vous voulez vérifier si elle contient 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; 
    } 
} 

ce code est très peu précis, juste censé être une démonstration.

Answer 2

Si le temps et l'espace ne sont pas importants, vous pouvez convertir les bits en une représentation sous forme de chaîne et effectuer des remplacements sur la chaîne, puis les convertir au besoin. Pas une solution élégante mais celle qui fonctionne.

Answer 3

Je me demande si C/C++ peut effectivement faire ce genre de remplacement des modèles de bits de longueur qui ne correspondent pas à une variable Char (1 octets) ou même Int (4 octets).

Qu'en est-il de std :: bitset?

Answer 4

Utilisez un vector<bool> si vous pouvez lire vos données dans le vecteur la plupart du temps. Cependant, il peut être plus difficile de trouver et de remplacer des séquences de bits.

Answer 5

Voici une petite classe de lecteur qui peut répondre à vos besoins. Bien sûr, vous voudrez peut-être créer un script pour votre cas d'utilisation.

#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 je comprends bien vos questions correctement, vous avez un flux d'entrée et et flux de sortie et que vous voulez remplacer les 6bits de l'entrée avec 5 dans la sortie - et votre sortie devrait encore être un flux de bits? Par conséquent, la règle de programmation la plus importante peut être appliquée: Divide et impera! Vous devez diviser votre composant en trois parties:

1. entrée convertisseur de flux: Autre chaque motif dans le flux d'entrée dans une mémoire tampon tableau de caractères (anneau). Si je vous ai bien compris, vos "commandes" d'entrée ont une longueur de 8 bits, donc il n'y a rien de spécial à cela. Effectuez le remplacement sur le tampon en anneau de manière à remplacer chaque motif 6 bits correspondant par le filtre 5 bits, mais en "plaçant" le bit 5 avec un zéro non significatif, de sorte que la longueur totale est toujours de 8 bits.

2. Ecrivez un gestionnaire de sortie qui lit à partir du tampon en anneau et laissez ce gestionnaire de sortie écrire uniquement le LSB 7 dans le flux de sortie à partir de chaque octet d'entrée. Bien sûr, une manipulation de bits est nécessaire à nouveau pour cela. Si votre taille de mémoire tampon circulaire peut être divisé par 8 et 7 (= est un multiple de 56), vous aurez un tampon propre à la fin et peut recommencer avec 1.

La façon la plus simple à mettre en œuvre ceci consiste à répéter sur ces 3 étapes tant que les données d'entrée sont disponibles.

Si une performance est vraiment importante et que vous utilisez un processeur multi-cœur, vous pouvez même diviser les étapes et les 3 threads, mais vous devez ensuite synchroniser soigneusement l'accès au tampon circulaire.

Answer 7

Je pense que ce qui suit fait ce que vous voulez.

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

}

Vous pouvez utiliser un commutateur ou d'une boucle au milieu pour vérifier le candidat contre plusieurs modèles. Il pourrait être nécessaire d'effectuer une manipulation spéciale après un remplacement pour s'assurer que le motif de remplacement n'est pas revérifié pour les correspondances.