Finding a bit pattern in a binary file using Python and memory map

Viewed 1919

I am processing a binary file that is not byte aligned at the start. Shortly in the file there is a 24 bit pattern 0xfaf330 that is a sync marker that marks subsequent byte aligned data. I am using Python mmap on the file and desire to use Python memoryview once the marker is found to process the remaining part of the file. So, how do I find the 24 bit pattern and then use mmap and memoryview from that point forward?

2 Answers

If you do not need random access, you can use open to stream the file. Using file.read, you can get consecutive bytes from the file. If your file were byte-aligned, you could directly search through it:

in_stream = open('/dev/urandom', 'rb')
# discard individual bytes until first marker byte
while in_stream.peek(1) != b'\xfa\xf3\x30':
    in_stream.read(1)
# in_stream is now positioned directly after the marker
print(in_stream.tell())

By default, open uses a small read buffer but never loads the entire file. You can stream through the file using further in_stream.read calls.

Alternatively, you can use the result of in_stream.tell() to jump to the correct position in an mmap'ed file.


Searching non-aligned bits

To manage non-byte aligned data, you must sift through bytes manually: bit-shifting allows to inspect sub-ranges of bytes. Note that Python only allows bit-shifting int, not bytes.

>>> pattern = 0xfaf330
>>> bin((pattern << 4) + 0b1011)  # pattern shifted by 4 plus garbage
0b1111101011110011001100001011

You can use this to scan a window of bytes:

def find_bits(pattern: int, window: int, n: int):
    """Find an n-byte bit pattern in an n+1-byte window and return the offset"""
    for offset in range(8):
        window_slice = (window >> offset) & (2 ** (n*8) -1)
        if pattern == window_slice:
            return offset
    raise IndexError('pattern not in window')

You can again use this to scan the file stream:

in_stream = open('/dev/urandom', 'rb')
# discard individual bytes until first marker byte
while True:
    try:
        offset = find_bits(
            0xfaf330,
            int.from_bytes(in_stream.peek(3)[:4], 'big'),
            3
        )
    except IndexError:
        in_stream.read(1)
    else:
        break
# in_stream is now positioned directly after the marker
print('byte-offset:', in_stream.tell(), 'bit-offset:', offset)

Alternatively, you can use binary representation to literally find the pattern in the window. Note that you have to mind padding of zero bits, so it is about the same work.


Reading non-aligned bits

Once you have the bit-offset, you can read-and-align data from the file. Basically, read one byte more than you need, then shift as needed:

def align_read(file, num_bytes: int, bit_offset: int):
    if bit_offset == 0:
        return file.read(num_bytes)
    window = file.peek(num_bytes + 1)[:num_bytes + 1]
    file.read(num_bytes)
    data = (int.from_bytes(window, 'big') >> bit_offset) & (2 ** (num_bytes*8) - 1)
    return data.to_bytes(num_bytes, 'big')

MisterMiyagi's answer is a good solution. Another solution uses the bitstring module.

aFile = open(someFilePath, 'rb')
aBinaryStream = bitstring.ConstBitStream(aFile)
aTuple = aBinaryStream.find('0b111110101111001100100000') #the sync marker

If found, the position in the file is moved to the found location. Then you can read byte aligned data.

aBuffer = aBinaryStream.read('bytes:1024') # to read 1024 bytes
Related