Approach for reading arbitrary number of bits in fast

Question

I am trying to parse a binary file in swift, and although everything works for me, I have a situation where I have variable fields.

I have all my parsing working in the default case

I grab

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) 

Most data uses only a certain set of options, so I went ahead and started writing classes to process this data. My general approach is to create a pointer structure, and then build an array of bytes from this:

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

So, I am finishing work with the [UInt8] array, and I can do the parsing in the same way as:

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

Therefore, when I encounter problems, these are optional fields, because my data is not specifically related to byte boundaries, everything becomes more complicated. In an ideal world, I would probably just work directly with the pointer and advance it by bytes as needed, however, I don’t know how to advance the pointer to 3 bits, which brings me to my question.

What is the best approach to handle my situation?

One of the ideas that I thought was to create different structures reflecting optional fields, except that I'm not sure about the quick creation of bit-aligned packed structures.

What is my best approach here? For clarification, the initial 1-bit fields determine which of the optional fields are set.

Answer 1

If the fields do not lie on byte boundaries, you will have to track both the current byte and the current bit position in the byte.

Here is a possible solution that allows you to read an arbitrary number of bits from a data array and does all the bookkeeping. The only limitation is that the result of nextBits() must fit into UInt (32 or 64 bits, depending on the platform).

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

Usage example:

 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 ... 

---

And here is another possible implementation, which is a bit simpler and possibly more efficient. It collects bytes in UInt and then extracts the result in one step. The limitation here is that numBits + 7 must be less than or equal to the number of bits in UInt (32 or 64). (Of course, UInt can be replaced with UInt64 to make it platform independent.)

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