%% LyX 1.4.0pre3 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[ngerman]{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{geometry} %\geometry{verbose,a4paper,tmargin=2cm,bmargin=2cm,lmargin=1cm,rmargin=2cm,headheight=0cm,headsep=1cm,footskip=1cm} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. %% Bold symbol macro for standard LaTeX users \providecommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \usepackage{multicol} \usepackage{babel} \makeatother \begin{document} \title{Forth Metaprogramming: Regexps} \author{Bernd Paysan} \maketitle \begin{multicols}{2} \begin{abstract} Der Artikel beschreibt einen Regexp--Compiler in Forth. Es kann gezeigt werden, dass die Umsetzung eines solchen Compilers nicht nur relativ einfach ist, sondern dass das Ergebnis auch weit performanter ist als vergleichbare Libraries für C, da die Regexps direkt in Maschinensprache umgesetzt werden. Der Quelltext zeigt auch, wie man in Forth ,,Metaprogramming{}`` macht, also dem Compiler neue Tricks beibringt. Zentrales Wort ist hier \texttt{POSTPONE}, in der Form \texttt{]] {[}{[}}, um mehrere Wörter hintereinander zu compilieren. \end{abstract} \section*{Einleitung} \subsection*{Was sind Regexps?} Reguläre Ausdrücke (Regexps) sind aus der Unix--Welt bekannt. Programmiersprachen wie Perl, Python oder Ruby verwenden reguläre Ausdrücke an vielen Stellen; und die Programme \texttt{sed}, \texttt{grep} und \texttt{awk} sind sogar fast nur damit beschäftigt, reguläre Ausdrücke zu verarbeiten. In der Theorie sind reguläre Ausdrücke endliche, nichtdeterministische Automaten. Man kann sie also entsprechend behandeln: \begin{description} \item [{Theoretisch:}] Durch die Transformation des nichtdeterministischen Automaten in einen deterministischen. \item [{Praktisch:}] Durch Backtracking. \end{description} Die praktische Behandlung besteht dabei in erster Linie aus einer Umfornung des Regexp--Pattern in einen Byte--Code, der stückweise ausgeführt werden kann. Schlägt ein Teilpattern fehl, wird zum letzten erfolgreichen Punkt zurückgesprungen, und ein alternatives Teilpattern ausprobiert. \subsection*{Beispiele} Ein paar Regexps in PCRE--Syntax: \begin{itemize} \item \texttt{M{[}ae]{[}ijy]er} (Namen suchen) \item \texttt{\textbackslash{}d\textbackslash{}d:\textbackslash{}d\textbackslash{}d:\textbackslash{}d\textbackslash{}d} (Uhrzeit) \item \texttt{\textbackslash{}(\textbackslash{}d{*}\textbackslash{})\textbackslash{}d{*}/\textbackslash{}d{*}} (Telefon) \end{itemize} Dasselbe in meiner Syntax \begin{itemize} \item \texttt{charclass {[}ae] 'a +char 'e +char}~\\ \texttt{charclass {[}ijy] 'i +char 'j +char 'y +char}~\\ \texttt{: name ( addr u -{}- flag )}~\\ \texttt{\strut~ (( ` M {[}ae] c? {[}ijy] c? ` e ` r )) ;} \item \texttt{: time (( \textbackslash{}d \textbackslash{}d ` : \textbackslash{}d \textbackslash{}d ` : \textbackslash{}d \textbackslash{}d )) ;} \item \texttt{: phone ( addr u -{}- flag ) }~\\ \texttt{\strut~ (( ` ( \{{*}{*} \textbackslash{}d {*}{*}\} ` ) \{{*}{*} \textbackslash{}d {*}{*}\} }~\\ \texttt{\strut~~~~ ` / \{{*}{*} \textbackslash{}d {*}{*}\} )) ; } \end{itemize} \subsection*{Elemente regulärer Ausdrücke} Ein regulärer Ausdruck besteht aus folgenden Elementen: \begin{description} \item [{Zeichen,~Zeichengruppen}] Hier werden einzelne Zeichen gematcht \begin{description} \item [{\texttt{`}~$\langle\mathit{char}\rangle$}] für Zeichenkonstanten, \item [{$\langle\mathit{class}\rangle$~\texttt{c?}}] für Zeichenklassen und \item [{\texttt{=\char`\"{}}~$\langle\mathit{string}\rangle$\char`\"{}}] für String (mehere Zeichenkonstanten hintereinander) \end{description} \item [{Wiederholungen}] Hier werden Pattern mehrmals wiederholt \begin{description} \item [{\texttt{\{{*}{*}~$\langle\mathit{pattern}\rangle$~{*}{*}\}}}] Gierige Schleife, mindestens kein mal~ \item [{\texttt{\{++~$\langle\mathit{pattern}\rangle$~++\}}}] Gierige Schleife, mindestens einmal \item [{\texttt{\{{*}~$\langle\mathit{pattern}\rangle$~{*}\}}}] Genügsame Schleife, mindestens kein mal \item [{\texttt{\{+~$\langle\mathit{pattern}\rangle$~+\}}}] Genügsame Schleife, mindestens einmal \end{description} \item [{Alternativen}] Hier werden verschiedene Pattern angeboten, von denen eines matchen muss \begin{description} \item [{\texttt{\{\{}~$\langle\mathit{pattern}\rangle$~\texttt{||}~$\langle\mathit{pattern}\rangle$~\ldots{}~\texttt{\}\}}}] Pattern--Auswahl \end{description} \end{description} Um den Pattern--Compiler einzuschalten setzt man das ganze Pattern in doppelte runde Klammern: \texttt{((} $\langle\mathit{pattern}\rangle$ \texttt{))} \section{Basis} \subsection{Hilfswörter} Implementiert werden die Regexp üblicherweise als threaded code. In Forth können wir also den vorhandenen Compiler verwenden. Da die einzelnen Elemente einen Entscheidungsbaum aufbauen, also Sprünge machen, müssen wir sie als Macro inlinen. Dazu verwene ich \texttt{]]} und \texttt{{[}{[}}, alles dazwischen wird mit \texttt{POSTPONE} compiliert. \texttt{: {[}{[} ; \textbackslash{} token to end bulk-postponing}~\\ \texttt{: ]] BEGIN >in @ ' {[}'] {[}{[} <> WHILE}~\\ \texttt{\strut~~~~~~~~~~~>in ! postpone postpone}~\\ \texttt{\strut~~REPEAT drop ; immediate } \subsubsection*{FORK JOIN} Eine neue Kontrollstruktur brauchen wir: \texttt{FORK} .. \texttt{JOIN}. Das entspricht \texttt{AHEAD} .. \texttt{THEN}, mit dem Unterschied, dass \texttt{FORK} einen Unterprogrammaufruf macht, der zum \texttt{JOIN} springt. Und eine Möglichkeit, \texttt{LEAVE} auch ausserhalb einer Zählschleife zu verwenden: \texttt{BEGIN} .. \texttt{LEAVE} .. \texttt{DONE} Damit bauen wir dann unsere Kontrollstrukturen auf. \subsection{Zeichenklassen} Zeichenklassen werden als Bitmaps realisiert. Ist das Bit an der Zeichenposition gesetzt, ist es in der Zeichenklasse. Zeichenklassen können mit einzelnen Zeichen, Zeichengruppen und anderen Klassen aufgefüllt werden; auch können Zeichenklassen subtrahiert werden (etwa: Alle druckbaren Zeichen außer den Interpunktionszeichen). \texttt{0 Value cur-class}~\\ \texttt{: charclass ( -{}- )}~\\ \texttt{\strut~ Create here dup to cur-class}~\\ \texttt{\strut~~\$20 dup allot erase ;}~\\ \texttt{: +char ( char -{}- )~ cur-class swap +bit ;}~\\ \texttt{: -char ( char -{}- )~ cur-class swap -bit ;}~\\ \texttt{: ..char ( a b -{}- ) }~\\ \texttt{\strut~ 1+ swap ?DO~ I +char~ LOOP ;}~\\ \texttt{: or! ( n addr -{}- )~ dup @ rot or swap ! ;}~\\ \texttt{: +class ( class -{}- )}~\\ \texttt{\strut~ \$20 0 ?DO @+ swap}~\\ \texttt{\strut~~~~~~~~cur-class I + or!~ cell +LOOP~ drop ;}~\\ \texttt{: and! ( n addr -{}- )~ dup @ rot and swap ! ;}~\\ \texttt{: -class ( class -{}- )}~\\ \texttt{\strut~ \$20 0 ?DO~ @+ swap invert}~\\ \texttt{\strut~~~~~~~~cur-class I + and!~ cell +LOOP~ drop ;} \subsubsection{Zeichenklassen abfragen} Zeichen abfragen muss schnell gehen (Performance!). Deshalb ist hier auch etwas Assembler angebracht. Wir lesen das Zeichen an der aktuellen Position aus, erhöhen diese Adresse um eins, und gucken, ob das Zeichen auch in der Zeichenklasse zu finden ist --- wenn ja, wird \emph{true} zurückgegeben. \texttt{Code char? ( addr class -{}- addr' flag )}~\\ \texttt{\strut~~~~~DX pop}~\\ \texttt{\strut~~~~~.b DX ) CX movsx~ DX inc~ DX push}~\\ \texttt{\strut~~~~~CX AX ) bt~ b makeflag}~\\ \texttt{\strut~~~~~Next end-code macro :dx :f T\&P} Wird das Zeichen nicht als Teil der Klasse erkannt, springt der Code aus dem aktuellen Block und startet das Backtracking. Die Zeichenabfrage muss alos wie folgt generiert werden: \texttt{: c? ( addr class -{}- )}~\\ \texttt{\strut~ ]] char? 0= ?LEAVE {[}{[} ; immediate}~\\ \texttt{: -c? ( addr class -{}- )}~\\ \texttt{\strut~ ]] char? ?LEAVE {[}{[} ; immediate} Alle Wörter zwischen \texttt{]]} und \texttt{{[}{[}} werden mit \texttt{POSTPONE} compiliert. Man kann sich das auch als Makro--Expansion vorstellen. Ein paar Standard--Zeichenklassen definieren wir uns noch, damit der Nutzer es einfacher hat: \texttt{charclass digit '0 '9 ..char}~\\ \texttt{charclass blanks 0 bl ..char}~\\ \texttt{charclass letter 'a 'z ..char 'A 'Z ..char}~\\ \texttt{charclass any 0 \$FF ..char \#lf -char} Und hier die Makros, um die Standard--Zeichenklassen abzufragen: \texttt{: \textbackslash{}d ( a -{}- a' ) ]] digit c? {[}{[} ; immediate}~\\ \texttt{: \textbackslash{}s ( a -{}- a' ) ]] blanks c? {[}{[} ; immediate}~\\ \texttt{: .? ( a -{}- a' ) ]] any c? {[}{[} ; immediate}~\\ \texttt{: -\textbackslash{}d ( a -{}- a' ) ]] digit -c? {[}{[} ; immediate}~\\ \texttt{: -\textbackslash{}s ( a -{}- a' ) ]] blanks -c? {[}{[} ; immediate} \subsection{Zeichen und Strings} Einzelne Zeichen werden mit \texttt{`} $\langle\mathit{char}\rangle$ abgefragt: \texttt{: ` ( -{}- )}~\\ \texttt{\strut~~]] count {[}{[} char ]] Literal <> ?LEAVE {[}{[} ;}~\\ \texttt{\strut~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~immediate} Strings vergleicht man mit \texttt{=\char`\"{}} \texttt{: \$= ( addr1 addr2 u -{}- f ) tuck compare ;}~\\ \texttt{: ,=\char`\"{} ( addr u -{}- ) tuck }~\\ \texttt{\strut~~]] dup SLiteral \$= ?LEAVE Literal + noop {[}{[} ;}~\\ \texttt{: =\char`\"{} ( \char`\"{} -{}- ) '\char`\"{} parse ,=\char`\"{} ; immediate} \subsection{Stacks} Der Loop--Stack dient dazu, die Unterblöcke aufzunehmen (\texttt{BEGIN} .. \texttt{DONE}). Diese Daten liegen zunächst auf dem normalen Stack herum, wo sie uns beim weiteren Arbeiten aber stören. Dieser Teil muss je nach Forth--System angepasst werden; in bigFORTH wird eine Zelle belegt, in Gforth drei. \texttt{Variable loops ~\$40 cells allot}~\\ \texttt{: loops> ( -{}- addr ) }~\\ \texttt{\strut~~-1 loops +! loops @+ swap cells + @ ;}~\\ \texttt{: >loops ( addr -{}- )}~\\ \texttt{\strut~~loops @+ swap cells + ! 1 loops +! ;}~\\ \texttt{: BEGIN, ( -{}- ) ]] BEGIN {[}{[} >loops ;}~\\ \texttt{: DONE, ( -{}- )}~\\ \texttt{\strut~~loops @ IF loops> ]] DONE {[}{[} THEN ]] noop {[}{[} ;} Der Variablen--Stack nimmt die Variablen auf, die auf geparste Substrings zeigen. Solche Substrings werden mit runden Klammern eingeschlossen, dadurch ergibt sich ein Stack als natürliche Repräsentation des aktuellen Zustands während des Parsens. \texttt{Variable vars ~~\&18 cells allot}~\\ \texttt{Variable varstack 9 cells allot}~\\ \texttt{Variable varsmax}~\\ \texttt{: >var ( -{}- addr ) vars @+ swap 2{*} cells +}~\\ \texttt{\strut~~vars @ varstack @+ swap cells + !}~\\ \texttt{\strut~~1 vars +! 1 varstack +! ;}~\\ \texttt{: var> ( -{}- addr ) -1 varstack +!}~\\ \texttt{\strut~~varstack @+ swap cells + @}~\\ \texttt{\strut~~1+ 2{*} cells vars + ;} Der Datenstack wird auch zur Laufzeit benutzt, und zwar für die Stringadressen. Ganz oben liegt die Adresse, die gerade untersucht wird, darunter Adressen, zu denen per Backtracking zurückgesprungen werden kann. Auf dem Returnstack liegen die Adressen für's Backtracking. Wird \texttt{TRUE} zurückgeliefert, war die Sucher bis hierher erfolgreich, bei \texttt{FALSE} muss eine andere Alternative durchsucht werden. \subsection{Start und Ende} Diese Wörter behandeln Start und Ende des Strings. Diese Adressen werden als globale Variablen gehalten, damit während der Auswertung der Regexp nur ein Wert (die aktuelle Position) auf dem Stack herumgeschoben wird. \texttt{0 Value end\$}~\\ \texttt{0 Value start\$}~\\ \texttt{: !end ( addr u -{}- addr )~ over + to end\$}~\\ \texttt{\strut~~~~~~~~~~~~~~~~~~~~~~~~~~~dup to start\$ ;}~\\ \texttt{: \$? ( addr -{}- addr flag )}~\\ \texttt{\strut~ dup end\$ u< ; macro}~\\ \texttt{: \textasciicircum{}? ( addr -{}- addr flag )}~\\ \texttt{\strut~ dup start\$ u> ; macro}~\\ \texttt{: ?end ( addr -{}- addr )}~\\ \texttt{\strut~~]] dup end\$ u> ?LEAVE {[}{[} ; immediate}~\\ \texttt{: \textbackslash{}\textasciicircum{} ( addr -{}- addr )}~\\ \texttt{\strut~~]] \textasciicircum{}? ?LEAVE {[}{[} ; immediate}~\\ \texttt{: \textbackslash{}\$ ( addr -{}- addr )}~\\ \texttt{\strut~~]] \$? ?LEAVE {[}{[} ; immediate} \section{High--Level} \subsection{Regexp Block} Der ganze Reguläre Ausdruck wird in einen \texttt{FORK} .. \texttt{JOIN} Block geklammert --- wenn der mit \texttt{EXIT} beendet wird, springt \texttt{AHEAD} heraus. \texttt{: (( ( addr u -{}- )}~\\ \texttt{\strut~ vars off varsmax off loops off}~\\ \texttt{\strut~~]] FORK AHEAD BUT JOIN !end {[}{[} BEGIN, ; }~\\ \texttt{\strut~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~immediate}~\\ \texttt{: )) ( -{}- addr f )}~\\ \texttt{\strut~~]] ?end drop true EXIT {[}{[}}~\\ \texttt{\strut~~DONE, ]] drop false EXIT THEN {[}{[} ; immediate} \subsection{Gierige Schleifen} Der Algorithmus für die sogenannten ,,greedy loops{}`` ist ziemlich einfach: \begin{enumerate} \item Bis zum Ende des Strings scannen \item Den Rest des Pattern ausprobieren \item Beim ersten Erfolg aufhören \end{enumerate} Wir können die minimale Anzahl, die das Pattern vorkommen muss, fest einstellen; üblicherweise ist das entweder 0 oder 1 mal. Vor jedem Parsen des wiederholten Patterns kopieren wir die Laufadresse mit \texttt{DUP}, und nehmen sie hinterher mit \texttt{DROP} wieder weg, wenn der Rest des Pattern nicht passt. \texttt{: drops ( n -{}- ) 1+ cells sp@ + sp! ;}~\\ \texttt{~}~\\ \texttt{: \{{*}{*} ( addr -{}- addr addr )}~\\ \texttt{\strut~~0 ]] Literal >r BEGIN dup {[}{[} BEGIN, ; immediate}~\\ \texttt{' \{{*}{*} Alias \{++ ( addr -{}- addr addr ) immediate}~\\ \texttt{: n{*}\} ( sys n -{}- )}~\\ \texttt{\strut~~>r ]] r> 1+ >r \$? 0= UNTIL dup {[}{[}}~\\ \texttt{\strut~~DONE, ]] drop {[}{[}}~\\ \texttt{\strut~~r@ IF ~r@ ]] r@ Literal u< {[}{[}}~\\ \texttt{\strut~~~~~~~~~]] IF r> 1+ drops false EXIT THEN {[}{[} }~\\ \texttt{\strut~ THEN}~\\ \texttt{\strut~~r@ ]] r> 1+ Literal U+DO FORK BUT {[}{[}}~\\ \texttt{\strut~~]] IF I' I - {[}{[} r@ 1-}~\\ \texttt{\strut~~]]~~~ Literal + drops true UNLOOP EXIT {[}{[}}~\\ \texttt{\strut~~]] ~~~THEN~~LOOP {[}{[}}~\\ \texttt{\strut~~r@ IF ~r@ ]] Literal drops {[}{[} THEN}~\\ \texttt{\strut~~rdrop ]] false EXIT JOIN {[}{[} ; immediate}~\\ \texttt{: {*}{*}\} 0 postpone n{*}\} ; immediate}~\\ \texttt{: ++\} 1 postpone n{*}\} ; immediate} \subsection{Genügsame Schleifen} Hier testen wir zuerst den Rest der Regexp, und nur, wenn das fehlschlägt, das Pattern in der Schleife (bei \texttt{\{+} gehört dieses Pattern zum ,,Rest{}``). \texttt{: \{+ ( addr -{}- addr addr )}~\\ \texttt{\strut~~]] BEGIN {[}{[} BEGIN, ; immediate}~\\ \texttt{: +\} ( addr addr' -{}- addr' )}~\\ \texttt{\strut~~]] dup FORK BUT IF drop true EXIT {[}{[}}~\\ \texttt{\strut~~DONE, ]] drop false EXIT THEN {*}\} {[}{[} ; immediate}~\\ \texttt{: \{{*} ( addr -{}- addr addr )}~\\ \texttt{\strut~~]] \{+ dup FORK BUT IF drop true EXIT THEN {[}{[} ;}~\\ \texttt{\strut~~~~~~~~~~~~~~~~~~~~~~~immediate}~\\ \texttt{: {*}\} ( addr addr' -{}- addr' )}~\\ \texttt{\strut~~]] dup end\$ u> UNTIL {[}{[}}~\\ \texttt{\strut~~DONE, ]] drop false EXIT JOIN {[}{[} ; immediate} Der Such--Prefix macht aus dem Pattern--Matchen eine Pattern--Suche. Statt eine Klasse abzufragen, in der alle Zeichen drin sind (die also ohnehin nie springt), erledigt \texttt{1+} den Job schneller. \texttt{: // ( -{}- ) ]] \{{*} 1+ {*}\} {[}{[} ; immediate} \subsection{Alternativen} Eine Alternative nach der anderen testen wir ab, indem wir zunächst die erste Variante ausprobieren, und beim Fehlschlag die nächste. Haben wir bei einem Pattern Erfolg, springen wir gleich an's Ende der Alternativen. Unterwegs müssen wir uns noch um die gerade gescannten Variablen kümmern --- es könnten ja in einem Zweig welche verwendet werden, und im anderen nicht. \texttt{: \{\{ ( addr -{}- addr addr )}~\\ \texttt{\strut~~0 ]] dup BEGIN {[}{[} vars @ ; immediate}~\\ \texttt{: || ( addr addr -{}- addr addr )}~\\ \texttt{\strut~~vars @ varsmax @ max varsmax !}~\\ \texttt{\strut~~]] nip AHEAD {[}{[} >r vars !}~\\ \texttt{\strut~~]] DONE drop dup {[}{[} r> ]] BEGIN {[}{[} vars @ ;}~\\ \texttt{\strut~~~~~~~~~~~~~~~~~~~~~~~~~~~~~immediate}~\\ \texttt{: THENs ( sys -{}- )}~\\ \texttt{\strut~~BEGIN dup WHILE ]] THEN {[}{[} REPEAT drop ;}~\\ \texttt{\strut~}~\\ \texttt{: \}\} ( addr addr -{}- addr addr )}~\\ \texttt{\strut~~vars @ varsmax @ max vars !}~\\ \texttt{\strut~~]] nip AHEAD {[}{[} >r drop}~\\ \texttt{\strut~~]] DONE drop LEAVE {[}{[} r> THENs ; immediate} \subsection{Variablen} Beim Scannen interessieren immer wieder Teilstrings, die nachher verarbeitet werden. Wir speichern Anfangs-- und End--Position in globalen Variablen. \texttt{: \textbackslash{}( ( addr -{}- addr ) ~]] dup {[}{[}}~\\ \texttt{\strut~~>var ]] ALiteral ! {[}{[} ; immediate}~\\ \texttt{: \textbackslash{}) ( addr -{}- addr ) ~]] dup {[}{[}}~\\ \texttt{\strut~~var> ]] ALiteral ! {[}{[} ; immediate}~\\ \texttt{: \textbackslash{}0 ( -{}- addr u ) ~start\$ end\$ over - ;}~\\ \texttt{: \textbackslash{}: ( i -{}- )}~\\ \texttt{\strut~~Create 2{*} 1+ cells vars + ,}~\\ \texttt{DOES> ( -{}- addr u ) @ 2@ tuck - ;}~\\ \texttt{: \textbackslash{}:s ( n -{}- ) 0 ?DO~ I \textbackslash{}:~ LOOP ;}~\\ \texttt{9 \textbackslash{}:s \textbackslash{}1 \textbackslash{}2 \textbackslash{}3 \textbackslash{}4 \textbackslash{}5 \textbackslash{}6 \textbackslash{}7 \textbackslash{}8 \textbackslash{}9} \section{Zusammenfassung} \subsection{Performance} Ein Vergleich mit PCRE, aus dem Shootout Benchmark (12000 Iterationen, 2GHz Athlon64, beides 32--Bit--Programme), ergibt: \begin{itemize} \item GCC, mit PCRE: 1.483s \item bigFORTH: 0.147s \end{itemize} Das ist ein bequemer Faktor 10. Dazu ist die Datei nur 171 Zeilen lang, während PCRE etwa mit 5000 Zeilen zu Buche schlägt. Der Quelltext ist Teil von bigFORTH, und dort in der Datei \texttt{regexp.fs} zu finden. \subsection{Ausblick} Was könnte man noch machen? \begin{itemize} \item Eine automatische Umsetzung der PCRE--Syntax ist denkbar Syntaxvorschlag \texttt{: phone ( addr u -{}- f ) \textasciitilde{}\char`\"{}} \texttt{$\langle regexp\rangle$\char`\"{} ;} \item Die bigFORTH--Teilname am Shootout könnte wieder belebt werden. Gforth ist dort auf einem guten Platz, obwohl das verwendete Debian--Packet nicht optimal übersetzt worden ist. \item Ein Gforth--Port existiert schon; die Bitmaps werden durch Bytemaps ersetzt. \end{itemize} \end{multicols} \end{document}