Überprüfen Sie das spezifische Bit von QByteArray

Question

Ich habe ein 8 Byte QByteArray und ich muss ein bestimmtes Bit in diesem Array, aber nicht das gleiche Bit jedes Mal überprüfen. Es könnte eines der 64 Bits sein, die dieses 8-Byte-Array bilden. Leistung ist Priorität!

My aktuelle Methode greift zuerst ein bestimmtes Byte aus dem Array, erhält dann eine bestimmte Halbbyte (Nibble oder), und wandelt dann zu einem anderen QByteArray mit binärer Darstellung unter Verwendung von QByteArray::number(x, 2), und dann schließlich das Bit I überprüfen. Das ist scheiße und ich will einen besseren Weg.

Ich entschied mich, es in eine QBitArray zu laden, damit ich schnell und einfach ein bestimmtes Bit abrufen kann. Ich nahm an, seine Darstellung im Speicher ist die gleiche wie eine QByteArray oder quint64, so würde die Umwandlung akzeptiert werden, aber die Konvertierung ist nicht erlaubt.

Wie würde ich überprüfen, ob ein bestimmtes Bit (0 bis 63) in einem QByteArray 1 oder 0 ist, schnell?

Answer 1

QBitArray wurde nicht entworfen, um zu etwas anderem umwandelbar zu sein; seine interne Repräsentation ist tatsächlich intern.

Leider ist die Bitprüfung ziemlich einfach. Moderne Architekturen verwenden Barrel Shifter, so dass das Schalten billig ist.

Es gibt mehrere mögliche Bit-zu-Byte-Zuordnungen. Lassen Sie uns decken sie alle:

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

So:

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

Wenn wir davon ausgehen, dass die Plattform sinnvolle Unterstützung für 64-Bit-Integer hat, können wir diejenigen nutzen:

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

Beliebig Anständiger Compiler wird entweder die obige Implementierung inline, wenn spezialisiert, z

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

Sie können es auch von Hand für den LB Fall spezialisieren:

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

Beachten Sie, dass die Q_BYTE_ORDER Prüfung eine Compile-Zeit konstant ist und verursacht keine Overhead-Laufzeit.

getBit1 und getBit2 sind tragbar für alle Plattformen Qt läuft, und getBit2 erzeugt ein wenig besser als Code getBit1. Auf x86-64, twiddling die Bit-Code von getBit2 beträgt 5 Anweisungen:

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