Façon très rapide de vérifier le bit mis en C

Question

J'utilise une sorte de BitStream dans mon code qui a une fonction read_bit(). Cette fonction est appelée très très souvent (plus d'un milliard de fois dans un seul flux). C'est ce que le Bitstream struct ressemble:

typedef struct BitStream { 
    unsigned char* data; 
    unsigned int size; 
    unsigned int currentByte; 
    unsigned char buffer; 
    unsigned char bitsInBuffer; 
} BitStream; 

Et le read_bit() -fonction est défini comme suit:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) { 
    unsigned int byte = bitPos/8; 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mask = 128 >> (bitPos & 7); 
    if (mask & byteVal) { 
     return 1; 
    } else { 
     return 0; 
    } 
} 

Maintenant, j'ai découvert par essais et erreurs que la ligne unsigned char mask = 128 >> (bitPos & 7); est très lent. Y a-t-il un moyen d'accélérer la vérification? J'ai déjà essayé d'utiliser un tableau qui indexe les 8 différents masques possibles, mais ce n'est pas plus rapide (je pense en raison de l'accès à la mémoire).

EDIT: J'ai essayé beaucoup de réponses au cours de la semaine dernière et j'ai effectué beaucoup de tests de performances, mais il n'y a pas eu beaucoup d'amélioration des performances. J'ai finalement réussi à obtenir une amélioration de 10 secondes en inversant l'ordre des bits dans le bitstream. Ainsi, au lieu d'utiliser le masque 128 >> (bitPos & 7), je la fonction:

unsigned char bitstream_read_bit_2(BitStream* stream, const unsigned long long bitPos) { 
    unsigned int byte = (unsigned int) (bitPos/8); 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mod = bitPos & 7; 
    return (byteVal & (1 << mod)) >> mod; 
} 

J'ai évidemment aussi changé la fonction d'écriture correspondante.

Answer 1

Voilà comment je d'abord votre code optimisé:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) 
{ 
    return !!(stream->data[(bitPos/8)] & (128 >> (bitPos % 8))); 
} 

Mais les frais généraux d'appel de fonction elle-même est probablement plus d'instructions que le code de peaufinage bits à l'intérieur. Donc, si vous voulez vraiment optimiser encore plus loin, nous allons profiter de inline et juste convertir à une macro:

#define bitstream_read_bit(stream, bitPos) (!!((stream)->data[((bitPos)/8)] & (128 >> ((bitPos) % 8)))) 

Answer 2

La première évidente amélioration consiste à déplacer la valeur chargée plutôt que le masque:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) { 
    unsigned int byte = bitPos/8; 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char maskVal = byteVal >> (bitPos & 7); 
    return maskVal & 1; 
} 

Cela supprime la nécessité d'une condition (ou non if! ou ?:).

Si vous pouvez modifier le struct, je vous recommande l'accès par des unités plus grandes que les octets:

#include <stddef.h> 
#include <limits.h> 
#include <stdbool.h> 

typedef struct WBitStream 
{ 
    size_t *data; 
    size_t size; 
} WBitStream; 

bool Wbitstream_read_bit(WBitStream* stream, size_t bitPos) 
{ 
    size_t location = bitPos/(sizeof(size_t)*CHAR_BIT); 
    size_t locval = stream->data[location]; 
    size_t maskval = locval >> (bitPos & (sizeof(size_t)*CHAR_BIT-1)); 
    return maskval & 1; 
} 

Sur certains processeurs (notamment le x86 commun), le masque du décalage montant est un NOP, puisque l'instruction de décalage natif du processeur ne considère que les bits faibles de la quantité de décalage de toute façon. Au moins, gcc le sait.

Answer 3

J'ai testé à optimzed macro par rapport à votre code source initial:

static unsigned char tMask[8] = { 128, 64, 32, 16, 8, 4, 2, 1 }; 

#define BITSTREAM_READ_BIT1(stream, bitPos) (((128 >> (bitPos & 7)) & stream->data[bitPos >> 3])!=0) 
#define BITSTREAM_READ_BIT2(stream, bitPos) (((tMask[(bitPos & 7)]) & stream->data[bitPos >> 3])!=0) 

Remplacer le calcul du masque par le masque dans le tableau n'augmente pas les performances. L'écart principal est entre la fonction et la macro (6 fois plus rapide sur mon ordinateur avec 80.000.000 d'appels).

Et l'utilisation en ligne statique n'est pas loin de la macro.