extract strings from a binary file in python

Question

I have a project where I am given a file and i need to extract the strings from the file. Basically think of the "strings" command in linux but i'm doing this in python. The next condition is that the file is given to me as a stream (e.g. string) so the obvious answer of using one of the subprocess functions to run strings isn't an option either.

I wrote this code:

def isStringChar(ch):
    if ord(ch) >= ord('a') and ord(ch) <= ord('z'): return True
    if ord(ch) >= ord('A') and ord(ch) <= ord('Z'): return True
    if ord(ch) >= ord('0') and ord(ch) <= ord('9'): return True

    if ch in ['/', '-', ':', '.', ',', '_', '$', '%', '\'', '(', ')', '[', ']', '<', '>', ' ']: return True

# default out
return False

def process(stream):
dwStreamLen = len(stream)
if dwStreamLen < 4: return None

dwIndex = 0;
strString = ''
for ch in stream:
    if isStringChar(ch) == False:
        if len(strString) > 4:
            #print strString
            strString = ''
    else:
        strString += ch

This technically works but is WAY slow. For instance, I was able to use the strings command on a 500Meg executable and it produced 300k worth of strings in less than 1 second. I ran the same file through the above code and it took 16 minutes.

Is there a library out there that will let me do this without the burden of python's latency?

Thanks!

Rearm

If you can read C, the source code for GNU strings might be helpful. It's only a few hundred lines, so it's not that bad. – Pietra

If you need unicode strings as well, there's that: gist.github.com/williballenthin/… – Claypoole

Answer 1

Of similar speed to David Wolever's, using re, Python's regular expression library. The short story of optimisation is that the less code you write, the faster it is. A library function that loops is often implemented in C and will be faster than you can hope to be. Same goes for the char in set() being faster than checking yourself. Python is the opposite of C in that respect.

import sys
import re

chars = r"A-Za-z0-9/\-:.,_$%'()[\]<> "
shortest_run = 4

regexp = '[%s]{%d,}' % (chars, shortest_run)
pattern = re.compile(regexp)

def process(stream):
    data = stream.read()
    return pattern.findall(data)

if __name__ == "__main__":
    for found_str in process(sys.stdin):
        print found_str

Working in 4k chunks would be clever, but is a bit trickier on edge-cases with re. (where two characters are on the end of the 4k block and the next 2 are at the start of the next block)

Littlefield

Nice suggestion. I agree — for smaller streams (ie, that can fit in memory), this is certainly preferable. I bet you could even chunk the stream, then run this regex across chunks split on nonprintable chars… Hhmm… – Grasso

@dougallj: This is wicked fast. Thanks! Now if you can make it find unicode strings too i will buy you a beer ;-) I would not have (and obviously didnt) thought to use re for this. I was able to process my 500Meg test file in 33 seconds. That is well within my design spec limits. – Rearm

@dougallj: It would be better to use re.escape() than to hard-code backslashes into your chars string. – Amalgamate

Could you overlap the chunks by a set byte amount? – Foreglimpse

Answer 2

At least one of your problems is that you're reading the entire stream into memory (… = len(stream)), and another is that your isStringChar function is very slow (function calls are relatively slow, and you're doing a lot of them).

Better would be something like this:

import sys
import string

printable = set(string.printable)

def process(stream):
    found_str = ""
    while True:
        data = stream.read(1024*4)
        if not data:
            break
        for char in data:
            if char in printable:
                found_str += char
            elif len(found_str) >= 4:
                yield found_str
                found_str = ""
            else:
                found_str = ""

 if __name__ == "__main__":
     for found_str in process(sys.stdin):
        print found_str

This will be much faster because:

• The "is character printable" lookup is performed with one set lookup (and O(1) operation) which calls directly (if I'm not mistaken) into a C function (which will be very fast).
• The stream is processed in 4k chunks, which will improve memory use and runtime on large inputs, as no swapping will be required.

Grasso

You need an else: found_str = "". The code currently prints any 4 printable characters it stumbles upon, regardless of whether they're in a row. – Littlefield

D'oh. Thanks. Fixed now. (if that didn't make it obvious, I haven't actually tested this code…) – Grasso