Vérifiez bit spécifique de QByteArray

Question

J'ai un QByteArray de 8 octets et j'ai besoin de vérifier un bit spécifique dans ce tableau, mais pas le même bit à chaque fois. Ce pourrait être n'importe lequel des 64 bits qui composent ce tableau de 8 octets. La performance est prioritaire!

Ma méthode actuelle le saisit un octet spécifique de ce tableau, puis obtient un demi-octet spécifique (ou grignotage), et convertit ensuite à un autre QByteArray avec une représentation binaire en utilisant QByteArray::number(x, 2), puis finalement je vérifier le bit. Cela craint et je veux un meilleur moyen.

J'ai choisi de le charger dans un QBitArray afin que je puisse récupérer rapidement et facilement un bit spécifique. J'ai supposé que sa représentation dans la mémoire est la même que QByteArray ou quint64, donc la conversion serait acceptée, mais la conversion n'est pas autorisée.

Comment vérifier si un bit spécifique (0 à 63) dans un QByteArray est 1 ou 0, rapidement?

Answer 1

QBitArray n'a pas été conçu pour être convertible en autre chose; sa représentation interne est en effet interne. Hélas, la vérification des bits est plutôt facile. Les architectures modernes utilisent des shifters à barillet, donc le changement de vitesse est bon marché.

Il existe plusieurs mappages bit à octet possibles. Nous allons couvrir tous:

 byte 0  byte 1  byte n-1 byte n 
LL - [] [89ABCDEF] ... 
LB - [] [FEDCBA98] ... 
BL -      ... [89ABCDEF] [] 
BB -      ... [FEDCBA98] [] 

Ainsi:

enum class BitMapping { LL, LB, BL, BB }; 

bool getBit1(const QByteArray & arr, int bit, BitMapping m) { 
    Q_ASSERT(arr.size() >= 8); 
    auto byte = (m == BitMapping::LL || m == BitMapping::LB) ? 
       bit/8 : (7 - bit/8); 
    bit = (m == BitMapping::LB || m == BitMapping::BB) ? 
     (bit%8) : (7 - (bit%8)); 
    return arr.at(byte) & (1<<bit); 
} 

Si nous supposons que la plate-forme a un support raisonnable pour les entiers 64 bits, nous pouvons tirer parti de ceux-ci:

bool getBit2(const QByteArray & arr, int bit, BitMapping m) { 
    Q_ASSERT(arr.size() >= 8); 
    auto value = *reinterpret_cast<const quint64 *>(arr.data()); 
    if (m == BitMapping::LL || m == BitMapping::BL) 
     bit = (bit & 0x38) + 7 - (bit & 0x07); // reorder bits 
    if ((Q_BYTE_ORDER == Q_LITTLE_ENDIAN && (m == BitMapping::BL || m == BitMapping::BB)) || 
     (Q_BYTE_ORDER == Q_BIG_ENDIAN && (m == BitMapping::LL || m == BitMapping::LB))) 
     bit = (bit & 0x07) + 0x38 - (bit & 0x38); // reorder bytes 
    return value & (1<<bit); 
} 

Tous compilateur décent sera en ligne soit la mise en œuvre ci-dessus lorsque spécialisé, par exemple

bool getBit(const QByteArray & arr, int bit) { 
    return getBit2(arr, bit, BitMapping::LB); 
} 

Vous pouvez également spécialiser la main pour le cas LB:

bool getBit1(const QByteArray & arr, int bit) { 
    Q_ASSERT(arr.size() >= 8); 
    auto byte = bit/8; 
    bit = bit%8; 
    return arr.at(byte) & (1<<bit); 
} 

bool getBit2(const QByteArray & arr, int bit) { 
    Q_ASSERT(arr.size() >= 8); 
    auto value = *reinterpret_cast<const quint64 *>(arr.data()); 
    if (Q_BYTE_ORDER == Q_BIG_ENDIAN) 
     bit = (bit & 0x07) + 0x38 - (bit & 0x38); // reorder bytes 
    return value & (1<<bit); 
} 

Notez que le Q_BYTE_ORDER chèque est une constante de compilation et encourt pas de frais généraux d'exécution.

getBit1 et getBit2 sont portables sur toutes les plates-formes Qt fonctionne sur et getBit2 génère un peu mieux que le code getBit1. Sur x86-64, le bit de code de tripotant getBit2 montants à 5 instructions:

mov $0x1,%eax 
shl %cl,%eax 
cltq 
test %rax,(%rdi) 
setne %al 
retq