2011-03-10

Python parsing

Ich baue grade einen pure Python parser für OpenPGP Messages nach RFC 4880. Dabei ist mir wieder mal was aufgefallen.

Wenn man einen Parser baut, der eine grosse Datenstruktur analysiert und in Pakete zerlegt, hat man in den meisten Sprachen folgendes Muster:


In C würde man es wohl so machen:

void parse_message(char * input) {
    int len = find_packet_len(input);
    handle_packet(make_packet(input, len)); 
    input += len;
}

In Python ist der naive Ansatz:

def parse_message(input):
  while input:
     packet_len = find_length_of_packet(input)
     packet = input[:packet_len]
     handle_packet(input[:packet_len])
     input = input[packet_len:]

In funktionalen Sprachen entsprechend.

Das Problem ist nun, das Python an dieser  Stelle jeweils eine Kopie des Paketes und eine Kopie des restlichen Inputs anlegt. Letzteres ist leider eine O(n^2) Operation ....

Entweder baut man das parsing also um, indem man input als Array behandelt nur nur über Indizes adressiert:

def parse_message(input):
  start = 0
  while len(input) > start:
    pl = find_length_of_packet(input, start)
    handle_packet(input[start:start + pl])
    start += pl

Oder, man verfolgt weiter den Stil aus dem oberen Beispiel, legt aber einen Wrapper um den input, der das Kopieren verhindert:


class ROList(list):
    def __init__(self, l, start = 0):
        self.__l = tuple(l)
        self.__start = start
        self.__end = sys.maxint


    def __getitem__(self, i):
        return self.__l[self.__start + i]


    def __getslice__(self, start, end):
        #print self, start, end, sys.maxint - end
        res =  self.__class__("")
        res.__l = self.__l
        res.__start = self.__start + start
        if end < sys.maxint:
            res.__end = self.__start + end
        return res


    def __len__(self):
        if self.__end == sys.maxint:
            return len(self.__l) - self.__start
        else:
            return self.__end - self.__start


    def __repr__(self):
        return "%s : %d" % (self.__l, self.__start)

def test_performance(list_type):
    l = list_type(range(1024*1024))
    while l:
        l = l[512:]

if __name__ == "__main__":
    for t in list, ROList:
        start_time = time.time()
        test_performance(t)
        print 'test of %s performance: %f seconds' % (t, time.time() - start_time)

2011-02-03

vi - das unbekannte Wesen

Ich benutze unter Unix vi (heutzutage als vim) als einzigen Editor für alles -- und das seit mehr 20 Jahren. Trotzdem (oder grade desshalb) gibt es Ecken im vi, die ich mir noch nie so richtig angesehen haben.

Irgendwann bin ich mal über autocmd gestolpert. autocmd oder 'automatic commands' dienen dazu, bestimmte Kommandos automatisch auszuführen.

Einfache Anwendungen dafür sind
autocmd BufReadPost,FileReadPost Makefile set noexpandtab
wenn ich ein Makefile bearbeite, dann hätte ich gerne richtige Tabs, oder
autocmd BufWritePre *.py :%s/\s\+$//e
wenn ich ein .py file schreibe, dann möchte ich keine Leerzeichen am Zeilenende haben.

Soweit, sogut.

Was aber daran wirklich toll ist, findet sich in der Dokumentation zu autocmd - ein Beispiel, wie man ein gzip Komprimiertes File editieren kann, welches beim lese automatisch ausgepackt und beim schreiben wieder gepackt wird.

Das kann man auch für sinvolleres benutzen, und so finden sich seit ein paar Jahren folgende Zeilen - dich ich irgendwoher aus dem Netz habe - in meiner .vimrc:


augroup encrypted
:au!
" First make sure nothing is written to ~/.viminfo
" while editing an encrypted file.
au BufReadPre,FileReadPre      *.gpg set viminfo=
" We don't want a swap file, as it writes unencrypted data to disk
au BufReadPre,FileReadPre      *.gpg set noswapfile
" Switch to binary mode to read the encrypted file
au BufReadPre,FileReadPre      *.gpg set bin
au BufReadPre,FileReadPre      *.gpg let ch_save = &ch|set ch=2
au BufReadPost,FileReadPost    *.gpg '[,']!gpg --decrypt 2> /dev/null
" Switch to normal mode for editing
au BufReadPost,FileReadPost    *.gpg set nobin
au BufReadPost,FileReadPost    *.gpg let &ch = ch_save|unlet ch_save
au BufReadPost,FileReadPost    *.gpg execute ":doautocmd BufReadPost " . expand("%:r")
" Convert all text to encrypted text before writing
au BufWritePre,FileWritePre    *.gpg   '[,']!gpg --default-key KEYID --default-recipient-self -ae 2>/dev/null
" Undo the encryption so we are back in the normal text, directly
" after the file has been written.
au BufWritePost,FileWritePost    *.gpg   u  
augroup END


Als KEYID ist hier die ID des PGP Keys anzugeben. Einfaches Lesen und schreiben von mit PGP verschlüsselten Textdateien.

$ vi foo.gpg
... editiere foo ....
$ cat foo.gpg
-----BEGIN PGP MESSAGE----- hQQOAx86mItHGziREBAA0EzP6msleRqcYS/2KLmMgNHEn9EukJOSgPahHJtE8Ni5

2011-01-19

Vortrag: Web Application Security / Web Application Firewalls

Gestern war ich an der Uni Passau bei der IEEE SB eingeladen, um einen Vortrag zum Thema "Web Application Firewalls" zu halten. Die Folien zum Vortrag finden sich hier

2011-01-15

Linux gotchas

Ich benutze Linux mittlerweile seit mehr als 17 Jahren. In dieser Zeit hat sich viel getan und Linux ist einfach zu installieren und zu verstehen.

Manchmal wird es aber komisch. Letzte Woche hatte ich wieder so einen Fall. Ich benutze Fedora14 und habe von der 32 Bit auf die 64Bit Version gewechselt. Dann noch schnell mein Home Verzeichnis vom Backup zurückgespielt und los geht's. Alles wunderbar, aber wenn ich ssh aufrufe, stürzt der Gnome-Keyring Daemon ab.

Da ich keine Lust zum debuggen hatte, bin ich wieder auf 32 Bit zurück. Backup eingespielt und wieder crasht der Gnome-Keyring ... das ging doch vor dem update ... WTF ....

Nach einiger Suche stellt sich heraus, das Gnome-Keyring nicht mit Files klarkommt, die als Datum der letzten Änderung der 1.1.1970 ist. Da fliegt dann eine Assertion und das Programm beendet sich ohne sinnvolle Fehlermeldung.

Merke: lege keine Files mit altem timestamp an, einige Softwareentwickler kommen nicht damit klar.