Approach for reading arbitrary number of bits in swift

Question

I'm trying to do some binary file parsing in swift, and although i have things working 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 of the data uses only a certain set of optionals so I've gone ahead and started writing classes to handle that data. My general approach is to create a pointer structure and then construct a byte array from that:

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 end up working with an array of [UInt8] and I can do my parsing in a way similar to:

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

So where I run into trouble is with the optional fields, because my data does not lie specifically on byte boundaries everything gets complicated. In the ideal world I would probably just work directly with the pointer and advance it by bytes as needed, however, there is no way that I'm aware of to advance a pointer by 3-bits - which brings me to my question

What is the best approach to handle my situation?

One idea i thought was to come up with various structures that reflect the optional fields, except I'm not sure in swift how to create 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 then you'll have to keep track of both the current byte and the current bit position within a byte.

Here is a possible solution which allows to read an arbitrary number of bits from a data array and does all the bookkeeping. The only restriction is that the result of nextBits() must fit into an 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
    }
}

Example usage:

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 implemention, which is a bit simpler and perhaps more effective. It collects bytes into an UInt, and then extracts the result in a single step. Here the restriction is that numBits + 7 must be less or equal to the number of bits in an UInt (32 or 64). (Of course UInt can be replace by 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
    }

}