Gegeben ein Array von uint8_t, wie lässt sich eine Unterfolge von Bits als uint32_t extrahieren?

Question

Ich bin in letzter Zeit auf ein interessantes Problem gestoßen:

Sagen wir mal, ich habe ein Array von Bytes (uint8_t genau genommen) der Länge mindestens eins. Jetzt brauche ich eine Funktion, die eine Teilfolge von Bits aus diesem Array abruft, beginnend mit Bit X (nullbasiert indexiert, inklusive) und einer Länge L, und dies als uint32_t zurückgibt. Wenn L kleiner als 32 ist, sollten die übrigen hohen Bits null sein.

Auch wenn dies nicht sehr schwer zu lösen ist, erscheinen mir meine aktuellen Gedanken darüber etwas umständlich. Ich denke an eine Tabelle aller möglichen Masken für ein bestimmtes Byte (beginne mit Bit 0-7, nimm 1-8 Bits) und konstruiere dann die Zahl Byte für Byte mit dieser Tabelle.

Kann jemand eine elegantere Lösung finden? Beachten Sie, dass ich dafür Boost oder STL nicht verwenden kann - und nein, es handelt sich nicht um eine Hausaufgabe, sondern um ein Problem, dem ich bei der Arbeit begegnet bin und wir verwenden Boost oder STL nicht im Code, in dem dieses Ding erscheint. Sie können davon ausgehen, dass: 0 < L <= 32 und dass das Byte-Array groß genug ist, um die Teilfolge aufzunehmen.

Ein Beispiel für korrekte Eingabe/Ausgabe:

Array: 00110011 1010 1010 11110011 01 101100
Teilfolge: X = 12 (nullbasiertes Index), L = 14
resultierendes uint32_t = 00000000 00000000 00 101011 11001101

Answer 1

Nur die ersten und letzten Bytes in der Teilfolge werden etwas Bit-Slicing erfordern, um die erforderlichen Bits zu erhalten, während die Zwischenbytes als Ganzes in das Ergebnis verschoben werden können. Hier ist ein Beispielcode, absolut nicht getestet - er tut, was ich beschrieben habe, aber einige der Bit-Indizes könnten um eins daneben liegen:

uint8_t bytes[];
int X, L;

uint32_t result;

int startByte  = X / 8,  /* Startbyte-Nummer */
    startBit   = 7 - X % 8,  /* Bitindex im Startbyte, vom LSB */
    endByte    = (X + L) / 8, /* Endbyte-Nummer */
    endBit     = 7 - (X + L) % 8; /* Bitindex im Endbyte, vom LSB */

/* Spezialfall, wenn Start und Ende im selben Byte liegen:
   nur Bits von startBit bis endBit abrufen */
if (startByte == endByte) {
  uint8_t byte = bytes[startByte];
  result = (byte >> endBit) & ((1 << (startBit - endBit)) - 1);
}
/* Alle anderen Fälle: Endbits des Startbytes holen,
                    alle anderen Bytes dazwischen,
                    Startbits des Endbytes */
else {
  uint8_t byte = bytes[startByte];
  result = byte & ((1 << startBit) - 1);

  for (int i = startByte + 1; i < endByte; i++)
    result = (result << 8) | bytes[i];

  byte = bytes[endByte];
  result = (result << (8 - endBit)) | (byte >> endBit);
}

Answer 2

Werfen Sie einen Blick auf std::bitset und boost::dynamic_bitset.

Answer 3

Ich würde etwas in der Art denken, wie das Laden eines uint64_t mit einem Cast und dann Links- und Rechtsshiften, um die uninteressanten Bits zu verlieren.

uint32_t extract_bits(uint8_t* bytes, int start, int count)
{
    int shiftleft =  32+start;
    int shiftright = 64-count;
    uint64_t *ptr = (uint64_t*)(bytes);
    uint64_t hold = *ptr;
    hold <<= shiftleft;
    hold >>= shiftright;
    return (uint32_t)hold;
}

Answer 4

Zur Vollständigkeit füge ich meine Lösung inspiriert von den Kommentaren und Antworten hier hinzu. Vielen Dank an alle, die sich die Mühe gemacht haben, über das Problem nachzudenken.

static const uint8_t firstByteMasks[8] = { 0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };

uint32_t getBits( const uint8_t *buf, const uint32_t bitoff, const uint32_t len, const uint32_t bitcount )
{
    uint64_t result = 0;

    int32_t startByte = bitoff / 8; // Startbyte-Nummer
    int32_t endByte = ((bitoff + bitcount) - 1) / 8; // Endbyte-Nummer
    int32_t rightShift = 16 - ((bitoff + bitcount) % 8 );

    if ( endByte >= len ) return -1;

    if ( rightShift == 16 ) rightShift = 8; 

    result = buf[startByte] & firstByteMasks[bitoff % 8];
    result = result << 8;

    for ( int32_t i = startByte + 1; i <= endByte; i++ )
    {
        result |= buf[i];
        result = result << 8;
    }
    result = result >> rightShift;
    return (uint32_t)result;
}

Ein paar Anmerkungen: Ich habe den Code getestet und er scheint einwandfrei zu funktionieren, jedoch können Fehler vorhanden sein. Wenn ich welche finde, werde ich den Code hier aktualisieren. Außerdem gibt es wahrscheinlich bessere Lösungen!