Podejście do odczytywania dowolnej liczby bitów w szybkim tempie

Question

Próbuję wykonać parsowanie pliku binarnego w szybkim tempie, i chociaż mam działające rzeczy, mam sytuację, w której mam zmienne pola.

mam wszystkie moje analizowania pracy w przypadku domyślnym

łapię

1-bit field 
1-bit field 
1-bit field 
11-bits field 
1-bit field 
(optional) 4-bit field 
(optional) 4-bit field 
1-bit field 
2-bit field 
(optional) 4-bit field 
5-bit field 
6-bit field 
(optional) 6-bit field 
(optional) 24-bit field 
(junk data - up until byte buffer 0 - 7 bits as needed) 

Większość danych używa tylko pewien zbiór optionals więc Poszedłem do przodu i zaczął pisać klasy do obsługi te dane. Moje ogólne podejście jest stworzenie struktury wskaźnika, a następnie skonstruować tablicę bajtów, które:

let rawData: NSMutableData = NSMutableData(data: input_nsdata) 
var ptr: UnsafeMutablePointer<UInt8> = UnsafeMutablePointer<UInt8(rawData.mutableBytes) 
bytes = UnsafeMutableBufferPointer<UInt8>(start: ptr, count: rawData.length - offset) 

więc skończyć pracę z tablicą [UInt8] i mogę wykonywać moją analizowania w sposób podobny do:

let b1 = (bytes[3] & 0x01) << 5 
let b2 = (bytes[4] & 0xF8) >> 3 
    return Int(b1 | b2) 

A więc, gdy napotkam problem, to z opcjonalnymi polami, ponieważ moje dane nie leżą szczególnie na granicach bajtów, wszystko staje się skomplikowane. W idealnym świecie prawdopodobnie po prostu pracowałbym bezpośrednio ze wskaźnikiem i przesuwałbym go o bajty w razie potrzeby, jednak nie ma sposobu, aby zdać sobie sprawę z przesunięcia wskaźnika o 3 bity - co sprowadza mnie do mojego pytania

Jakie jest najlepsze podejście do radzenia sobie z moją sytuacją?

Jedną z idei, o której pomyślałem, było wymyślenie różnych struktur, które odzwierciedlają opcjonalne pola, z tym, że nie jestem pewien, jak szybko utworzyć spasowane struktury bitowe.

Jakie jest moje najlepsze podejście tutaj? W celu wyjaśnienia - początkowe pola 1-bit określają, które z opcjonalnych pól są ustawione.

Answer 1

Jeśli pola nie leżą na granicach bajtów, musisz zachować ścieżkę zarówno bieżącego bajtu, jak i bieżącej pozycji bitu w bajcie.

Oto możliwe rozwiązanie, które pozwala odczytywać arbitralny numer bitów z tablicy danych i wykonuje całą księgowość. Jedynym ograniczeniem jest to, że wynik nextBits() musi zmieścić się w UInt (32 lub 64 bity, w zależności od platformy).

struct BitReader { 

    private let data : [UInt8] 
    private var byteOffset : Int 
    private var bitOffset : Int 

    init(data : [UInt8]) { 
     self.data = data 
     self.byteOffset = 0 
     self.bitOffset = 0 
    } 

    func remainingBits() -> Int { 
     return 8 * (data.count - byteOffset) - bitOffset 
    } 

    mutating func nextBits(numBits : Int) -> UInt { 
     precondition(numBits <= remainingBits(), "attempt to read more bits than available") 

     var bits = numBits  // remaining bits to read 
     var result : UInt = 0 // result accumulator 

     // Read remaining bits from current byte: 
     if bitOffset > 0 { 
      if bitOffset + bits < 8 { 
       result = (UInt(data[byteOffset]) & UInt(0xFF >> bitOffset)) >> UInt(8 - bitOffset - bits) 
       bitOffset += bits 
       return result 
      } else { 
       result = UInt(data[byteOffset]) & UInt(0xFF >> bitOffset) 
       bits = bits - (8 - bitOffset) 
       bitOffset = 0 
       byteOffset = byteOffset + 1 
      } 
     } 

     // Read entire bytes: 
     while bits >= 8 { 
      result = (result << UInt(8)) + UInt(data[byteOffset]) 
      byteOffset = byteOffset + 1 
      bits = bits - 8 
     } 

     // Read remaining bits: 
     if bits > 0 { 
      result = (result << UInt(bits)) + (UInt(data[byteOffset]) >> UInt(8 - bits)) 
      bitOffset = bits 
     } 

     return result 
    } 
} 

Przykład użycia:

let data : [UInt8] = ... your data ... 
var bitReader = BitReader(data: data) 

let b1 = bitReader.nextBits(1) 
let b2 = bitReader.nextBits(1) 
let b3 = bitReader.nextBits(1) 
let b4 = bitReader.nextBits(11) 
let b5 = bitReader.nextBits(1) 
if b1 > 0 { 
    let b6 = bitReader.nextBits(4) 
    let b7 = bitReader.nextBits(4) 
} 
// ... and so on ... 

---

A oto inna możliwa implementacja, która jest nieco prostsze , a być może bardziej skuteczne. Pobiera bajty do UInt i , a następnie wyodrębnia wynik w jednym kroku. Tutaj ograniczenie polega na tym, że numBits + 7 musi być mniejszy lub równy na liczbę bitów w UInt (32 lub 64). (Oczywiście UInt można zastąpić przez UInt64 aby to niezależny od platformy).

struct BitReader { 
    private let data : [UInt8] 
    private var byteOffset = 0 
    private var currentValue : UInt = 0 // Bits which still have to be consumed 
    private var currentBits = 0   // Number of valid bits in `currentValue` 

    init(data : [UInt8]) { 
     self.data = data 
    } 

    func remainingBits() -> Int { 
     return 8 * (data.count - byteOffset) + currentBits 
    } 

    mutating func nextBits(numBits : Int) -> UInt { 
     precondition(numBits <= remainingBits(), "attempt to read more bits than available") 

     // Collect bytes until we have enough bits: 
     while currentBits < numBits { 
      currentValue = (currentValue << 8) + UInt(data[byteOffset]) 
      currentBits = currentBits + 8 
      byteOffset = byteOffset + 1 
     } 

     // Extract result: 
     let remaining = currentBits - numBits 
     let result = currentValue >> UInt(remaining) 

     // Update remaining bits: 
     currentValue = currentValue & UInt(1 << remaining - 1) 
     currentBits = remaining 
     return result 
    } 

}