Laplace-Filter als Beispiel

Ein zweifellos sehr einfaches Filterprogramm zur Bildverarbeitung besteht in dem Laplace-Filter, das näherungsweise die zweite Ableitung eines zweidimensionalen Feldes bildet und dadurch die Kantendetektierung ermöglicht.

Der Algorithmus basiert darauf, dass für jeden neu zu berechnenden Punkt in einem Kantenbild der Wert aus dem ursprünglichen Bild für diesen Punkt genommen wird, mit dem Gewichtsfaktor 4 (im Fall eines 2-dimensionalen Filters) multipliziert wird, und von diesem Wert dann die unmittelbaren Nachbarn (keine Diagonalen) subtrahiert werden.

Bildergalerie

Bildergalerie mit 12 Bildern

Um die Darstellung des Übersetzungsvorgangs möglichst einfach zu halten, wird hier die eindimensionale Variante gewählt (Bild 7). Dieser Code wird nun entsprechend dem Lance2-Compilers in einen Zwischencode, wie zuvor beschrieben, übersetzt.

Konkret werden im Zwischencode nur wenige Operationen benötigt, so z.B.:

• Wertzuweisungen an Variable, hierbei rechtsseitig einfache Rechnungen mit maximale zwei Operanden und einer Operation; dies wird auch für Adressrechnung bei indizierten Variablen benötigt.

• Vergleiche mit Zuweisung des Booleschen Werts an eine Variable

• if-Konstrukt mit einer Variablen, auf deren Wahrheitswert verglichen wird, mit anschließendem (Compiler-berechnetem) goto.

Generierung des Zwischencodes

Diese Form des Zwischencodes bedeutet aber auch, dass voraussichtlich eine Vielzahl von temporären Variablen benötigt wird, da viele Zwischenrechnungen zu machen sind. Im Zwischencode – hier werden die Zeilen ab 101 durchnummeriert – in Listing in Bild 8 fällt sofort die Vielzahl der Variablen auf, die hier zusätzlich zum Originalcode deklariert werden. Die Zeilen 101-102 entsprechen der Deklaration der Arrays in C, sie werden die Größe 100 haben. Die in der Funktion laplace_filter_1d (Bild 7) deklarierte Variable taucht in Zeile 105 wieder auf, sie werden lediglich zusätzlich mit einem ’_’ versehen und durchnummeriert, ansonsten entspricht diese Deklaration der von C.

Die nun folgenden Variablen sind alles vom Compiler erzeugte temporäre Variablen. Man erkennt sie gut an dem fehlenden Unterstrich im Namen. Diese Variablen werden für Berechnungen gebraucht, die im C-Code noch ohne Zwischenschritte auskamen, und sind eine Folge der Übersetzung in der 3-Adresscode. Da der Compiler temporäre Variabelen nicht wieder verwendet, legt er erst einmal für jede dieser Berechnungen eine neue temporäre Variable an. Etwaige Optimierungen sind Aufgabe des nachfolgenden Codegenerators.

Bild 9 zeigt den entstehenden Zwischencode bei den gegebenen Voraussetzung. Die einzelnen Berechnungen erscheinen recht komplex, etwa für den Zugriff auf bild[x+1] (Zeile 150-155), sie sind aber notwendig, und in jeder Zeile wird das 3-Adressformat eingehalten. Der Zugriff auf bild[x+1] bedeutet nicht anderes, als dass die Adresse &bild[0] + (x+1)*sizeof(bild[0]) gebildet und dann auf den Inhalt lesend oder schreibend zugegriffen wird. Diese Berechnung der Zugriffsadresse ist in den Zeilen 150 (Basisadresse als char *) sowie 151-154 (Index- und Adressberechnung) codiert und steht dann in der Variablen t22 zur Verfügung. Die Operation sizeof(bild[0]) liefert dabei den 2 für short.

Das Setzen der Basisadresse &bild[0] findet offenbar mehrfach in den Zeilen 137, 143 und 150 statt. Dies kann eventuell optimiert werden, wobei der Compiler exakt prüfen muss, ob nicht durch externe Programmteile – eine Interrupt Service Routine etwa – die Adresse verändert werden könnte, da bild[] global definiert wurde. In diesem Fall kann aber die Adresse selbst nicht verändert werden – sie ist konstant, nur die Inhalte sind variabel – so dass die Zeilen 143 und 150 entfallen können ( nächsten Abschnitt).

Die Zeilen 134 bis 136 stellen die Auswertung der Schleifenendebedingung dar. Zunächst wird der aktuelle Wert von x_3 mit 99 (X_DIM-1) verglichen, und das Vergleichsergebnis wird der Compiler-generierten Variablen t1 zugewiesen. Diese Variable fungiert als Boole’sche Variable, d.h., sie soll nur Werte für true und false speichern. Die Zuweisung des negierten Wahrheitswerts an t24 in Zeile 135 und die Auswertung durch einen bedingten Sprung (Zeile 136) komplettieren diesen Abschnitt.

Vom Zwischencode zum Assemblercode

Die Übersetzung des Zwischencodes in einen Assemblercode soll anhand einer Modell-CPU erfolgen. Diese wird als MPM3, Mikroprozessormodell #3, bezeich-net und stellt einen RISC-Prozessor mit einer intrinsischen Verarbeitungsbreite von 16 bit dar. Dieses Modell wurde gewählt, weil die typischen Vorgänge daran sehr gut gezeigt werden können, ohne auf die Spezialitäten einer marktgängigen Architektur eingehen zu müssen.

Die spontane Übersetzung des Zwischencodes wird durch einen weiteren Vorgang, die Abbildung der Variablen auf Register oder Speicher betreffend, gebremst. Die Abbildung auf den Maschinencode ist tatsächlich nicht besonders schwierig, hingegen sind die Anforderungen an die Daten schon schwieriger erfüllbar. Bei diesem Vorgang müssen insbesondere Randbedingungen wie Laufzeitminimierung erfüllt werden.

Die Übersetzung des ersten Teils des Zwischencodes (siehe Bild 8) fällt überraschend klein aus. Die gesamte Abbildung der doch eher großen Menge an Variablen erfolgt so, dass lediglich die Variablen bild[] und kanten[] im Speicher angelegt und mit Werten initialisiert wird. Die Initialisierung erfolgt dem Datentyp short gemäß mit 16 bit (DW, define word). Die übrigen Variablen werden auf 7 der vorhandenen 8 Datenregister R0 bis R7 abgebildet (siehe Tabelle 1).

Bild 11 zeigt die Übersetzung des Zwischencodes in den Assemblercode und hierbei auch einige Optimierungsmöglichkeiten (die keineswegs immer im Backendgenerator vorhanden sein werden). Wie bereits dargestellt können die Zeilen 143 und 150 durch Optimierung entfallen (im Übrigen bereits im Zwischencode).

Die Optimierung kann sogar noch weitergehen: Das Programm läuft ein Weile in der Schleife von LL1 (Zeile 133) bis goto LL1 (Zeile 164), und in der gesamten Schleife werden der Wert für short *bild (in R1) und short *kanten (ebenfalls in R1) drei- bzw. einmal im Register geschrieben und dann lesend benutzt. Wenn man also den Wert für short *kanten in einem anderen Register speichern kann (z.B. in R7), dann könnten die Zeilen 310/311 und 326/327 im Assemblercode nach oben, also zwischen Zeile 307 und 308 geschoben werden. Dieses Verfahren, Instruction Scheduling genannt, bewirkt in diesem Fall, dass die Zeilen nur einmal für alle Schleifen durchlaufen werden und spart somit Rechenzeit.

Noch kurz ein Wort zu den vielleicht ungewöhnlich ausschauenden Zeilen 310/311 bzw. 326/327. In diesen Assemblercodezeilen wird ein Register mit einer 16-bit-Konstanten geladen. Die zugrunde liegende Architektur ist (angenommen) eben-falls mit 16-bit-Datenstrukturen (Register, ALU) und 16-bit Adressen versehen, und hierbei kommt es zum Problem. Bei RISC-Prozessoren ist es sozusagen Pflicht, dass ein Befehl in einem Takt bearbeitet wird, und wenn nun ein Befehl eine Breite von 16 bit im Speicher hat, dann passen keine Konstanten mit 16 bit Breite dort hinein (weil ja die Operation auch noch beschrieben werden muss).

Die Lösung besteht in dem Befehlspaar MOV/MOVH (Move und Move High Byte). Der erste Teil kopiert den Operanden – der untere Teil der Adresse für bild bzw. kanten – in die entsprechenden Bits des Registers, meist mit Belegung auch der oberen Bits (auf 0 oder mit Vorzeichenerweiterung), und MOVH kopiert dann den Operanden, dem oberen Teil der Adresse entsprechend, in die oberen Bits des Registers.

Letztes Augenmerk soll noch auf die Übersetzung der bedingten Sprünge gelegt werden (Zeile 134-136). Der Zwischencode bestand hier aus drei Anweisungen: die Bedingung wird auf ihren Wahrheitswert berechnet, der Wert wird invertiert, und unter Auswertung dieses entstehenden booleschen Wertes wird dann gesprun-gen (oder nicht). Im Assemblercode treten hiervon nur noch zwei Anweisungen auf: Die Auswertung der Bedingung wird auf das Setzen von Flags abgebildet (Zeile 309), und diese Flags werden – mit logischer Invertierung, denn BGE bedeutet branch if greater or equal, was die umgekehrte Bedingung zu kleiner (less than) ist – dann in Zeile 310 ausgewertet.

C-Compiler: Optimierungsmöglichkeiten

Im vorangegangenen Beispiel wurden die Zeilen 143 und 150 wegoptimiert, weil es sich offensichtlich immer um die gleiche Zuweisung handelt. Im Allgemeinen gilt, dass derartige Optimierung der mehrfachen Wertzuweisung durchgeführt werden können, wenn sichergestellt ist, dass Wertänderungen – auch durch externe Routinen wie ISR – ausgeschlossen sind.

Diese Optimierung, die bereits im Zwischencode erfolgen kann, ist immer dann möglich, wenn die entsprechende Variable lokal angelegt ist oder bei globaler Speicherklasse konstant ist.

Im Fall der Beispiels des eindimensionalen Laplace-Filters (Bild 7) galt die zweite Voraussetzung, da die Adresse des Arrays bild[], also &(bild[0]), konstant angelegt wird.

Mit diesem Beispiel wollen wir die Grundlagen zur C-Programmierung vorerst abschließen. Damit sich keine Fehler beim Coden einschleichen empfiehlt es sich allerdings, einige Leitlinien zu beachten. In einem Abschließenden Artikel zum Programmieren mit C wollen daher – beispielhaft – auf Codierungsregeln (Coding Rules) eingehen, die gerade für Softwareentwicklung in sicherheitskritischen Bereichen gelten und anerkannt sind.

C programmieren: lexikalische Grundlagen

C programmieren: Datentypen, Deklarationen, Operatoren und Ausdrücke

C programmieren: Präprozessor und Standardbibliothek

Dieser Beitrag findet sich im Handbuch „Embedded Systems Engineering“ im Kapitel "Einführung in die Sprache C". Das Handbuch ist auch als kostenlose PDF-Version in voller Länge auf ELEKTRONIKPRAXIS.de verfügbar.

* Prof. Dr. Christian Siemers lehrt an der Technische Universität Clausthal und arbeitet dort am Institut für Elektrische Informationstechnik (IEI).

(ID:45439187)