Parse WAP-230 "variable length unsigned integers"

Question

I am working on a program to decode an MMS PDU file. In the file, the "content-length" is represented in a unique way. According to the MMS spec WAP-230 Section 8.1.2, it is encoded as a "Variable Length Unsigned Integer".

Basically for each byte, the 1st bit is the "continue bit" and the other 7 are the "payload". We keep reading bytes while the "continue bit" is 1. When it's 0, we take the "payloads" and combine them together into a value.

Here's an example, let's say I have the following bytes:

82 E5 04

or in binary:

1000 0010 1110 0101 0000 0100

Then we split them into their continue bit/payload:

1 | 0000010
1 | 1100101
0 | 0000100

Now, we start from the beginning, append the bits and move on until the continue bit is 0. Thus we get the value:

000001011001010000100

or broken into bytes (and left padded with zeroes):

0000 0000 1011 0010 1000 0100

This can be read (in hex) as:

00 B2 84

which converts to 45700 (0xB284).

I tried to implement this in python as I was reading through an MMS PDU file byte by byte. Here is what I came up with:

cont_bit = True
remaining_bits = []

while cont_bit:
    variable_length = self.data[curr_index]
    curr_index += 1

    # There's obviously a better way to do this, but I don't really know what it is
    binary_length = bin(variable_length).lstrip('0b').zfill(8)

    # Check the "continue bit"
    cont_bit = (binary_length[0] == '1')
    remaining_bits.append(binary_length[1:])

# Put the values together and read it as an int
content_length = int(''.join(remaining_bits), 2)

_{Note: self.data is the binary file I am reading and curr_index is my current position in the file.}

This does work and content_length does contain the right value, I just think there's gotta be a better way to do this than to convert each byte into a string (representing its binary representation), reading the 1st character of this string, then appending the rest of the string into an array (which I parse as a base-2 integer).

Answer 1

To get the bits out of a byte without converting to a string and back again, use Python's bitwise operations and shift operations. To get the high bit of a byte, shift it right by 7 bits:

>>> data = open('/dev/urandom', 'rb').read(128)
>>> data[0]
193
>>> data[0] >> 7
1

To get the low seven bits of a byte, mask against 0b1111111 (that is, 127):

>>> data[0] & 127
65

Finally, if we maintain a running value for content_length, we can extend it with these seven bits of payload by taking the running value, shifting it left by 7 bits and or-ing with the payload. In summary:

content_length = 0
while True:
    byte = self.data[curr_index]
    curr_index += 1
    content_length = (content_length << 7) | (byte & 127)
    if byte >> 7 == 0:
        break

Answer 2

I'm Ignoring the bitwise operations in my answer. Even though they're probably better.

You can change the line that changes an int to a binary string to use format. The Format Specification Mini-Language allows you to convert integers into binary with the b format option, which doesn't add the annoying 0b prefix. It also allows you to pad the string to a specific length as well, this means you can use something like 0>8, to pad the string with 0s on the left of the input. Adding these together you can get:

binary_length = format(self.data[curr_index], '0>8b')

---

I'd personally change this function a couple of more ways. I know you probably know what you're doing, but you can have my 2c anyway.

Rather than manually slicing and indexing the data you can tuple unpack the data straight from the format. This means you can change the above line to:

continue_bit, *payload = format(self.data[curr_index], '0>8b')

From this you can change the while loop to while continue_bit == '1'. And you would need to change append to extend with the argument payload.

I'd also change the input to the function to be an iterable, rather than a class method with a starting index. This can allow you to more easily test the function. As creating an entire class seems a bit much to test this function. To do this efficiently you can use itertools.islice, e.g. fn_name(itertools.islice(self.data, curr_index, None)). This returns roughly the same as self.data[curr_index:], but it's lazy, and so it only uses \$O(1)\$ memory.
Which can change your function to:

from itertools import islice

def get_content_length(data):
    remaining_bits = []
    for char in data:
        continue_bit, *payload = format(char, '0>8b')
        remaining_bits.extend(payload)
        if continue_bit != '1':
            break
    return int(''.join(remaining_bits), 2)

get_content_length(islice(self.data, curr_index))