In der Ära der frühen Personal Computer, als Festplattenspeicher knapp und teure Ressourcen waren, spielte die Kompression von Programmdateien eine entscheidende Rolle. Besonders unter MSDOS war es wichtig, ausführbare Dateien so klein wie möglich zu halten, ohne die Benutzerfreundlichkeit zu beeinträchtigen. LZEXE, ein damals revolutionäres Komprimierungsprogramm, bot eine effiziente Lösung für dieses Problem und prägte die Art und Weise, wie EXE-Dateien komprimiert und geladen wurden. LZEXE wurde 1989 und 1990 von Fabrice Bellard entwickelt, einem jungen Programmierer, der später mit Projekten wie FFmpeg und QEMU weltweite Bekanntheit erlangte. Angetrieben durch die Herausforderungen kleiner Festplattenkapazitäten und limitierter Diskettengrößen seines Amstrad PC1512 konzipierte Bellard LZEXE als ein Werkzeug zur Platzersparnis, das zugleich eine beinahe nahtlose Benutzererfahrung bot.
Anders als viele andere Kompressionswerkzeuge der damaligen Zeit konnte LZEXE Programme unmittelbar nach der Dekompression starten, ohne dass der Benutzer einen zusätzlichen Schritt durchführen musste. Dies war möglich durch eine in-place Dekompression, bei der die komprimierten Programmteile direkt im Speicher zu ihrem ausführbaren Zustand entpackt wurden. Die technische Grundlage von LZEXE bildet der Lempel-Ziv-Storer-Szymanski (LZSS) Algorithmus, ein Optimierungsschritt des bekannten Lempel-Ziv-Verfahrens. Dieser Algorithmus nutzt ein Sliding-Window-Verfahren und ersetzt wiederholte Datenabschnitte durch Verweise auf vorherige Sequenzen, was zu einer signifikanten Speicherersparnis führt. Die Besonderheit bei LZEXE war, dass die Dekompression ohne zusätzlichen Speicherbedarf erfolgte.
Das Programm entschied vorher schon, dass kein Teil der zu entpackenden Daten die Quelldaten überschreiben würde, bevor diese gelesen waren. Diese präzise Steuerung der Speicherbereiche machte das Verfahren effizient und extrem platzsparend. Ein zentraler Teil des LZEXE-Kompressions- und -Dekompressionsprozesses ist der sogenannte LZEXE-Header. Dieser kleine Datenblock, der sich am Anfang des geladenen Programms befindet, liefert wichtige Parameter wie Startadresse des eigentlichen Programmes, Speicherbedarf und Stapelgröße. Seine sorgfältige Gestaltung ermöglicht es dem Dekomprimierer, den komprimierten Datenblock an eine neue Speicheradresse zu verschieben, bevor mit der Dekompression gestartet wird.
Diese Verschiebung verhindert, dass die Dekompression vorhandene Daten während des Entpackens überschreibt – ein Problem, das bei fehlender Vorsicht zu Datenverlust oder Programmfehlern führen würde. Das Verschieben des Dekomprimierers und der Daten erfolgt effizient in großen Speicherabschnitten, die in umgekehrter Reihenfolge von höher zu niedriger Adresse kopiert werden. Dabei wird die Kopie des Dekomprimierungscodes mit einem Inter-Segment-Return-Jump aktiviert, um die Ausführung in der neuen Speicherregion fortzusetzen. Anschließend werden die komprimierten Programmteile ebenfalls verlegt, bevor die Dekompression beginnt. Ein besonders faszinierender Aspekt von LZEXE ist die Behandlung der Flagbits zur Steuerung der Art der Datenkomprimierung.
Anders als einfache Kompressionsverfahren setzt LZEXE auf ein komplexes System variabler Codewortlängen, um Literalbytes und Verweise auf bereits entpackte Daten effizient abzubilden. Die Flagbits werden in einem Puffer gesammelt und bieten dem Dekomprimierer feingranulare Steuerungsinformationen, wie die Daten interpretiert werden sollen. So lassen sich Datenbereiche als Rohbytes, kurze oder lange Referenzen oder sogar als sehr lange Wiederholungen codieren. Dieses System ermöglicht nicht nur eine sehr gute Kompressionsrate, sondern passt sich auch der Datenbeschaffenheit flexibel an. Die Run-Length-Encoding-Eigenschaft, die es erlaubt, lange Wiederholungen gleicher Zeichen mit minimalem Speicherbedarf zu komprimieren, ist ein integraler Bestandteil von LZEXE.
Dabei kann das System beispielsweise festlegen, dass eine Folge von 100 gleichen Bytes lediglich mit einem kurzen Verweis kodiert wird. Dieses Vorgehen optimiert den verfügbaren Speicherplatz deutlich und erhöht die Effizienz der Kompression. Neben der eigentlichen Kompression und Dekompression behandelt LZEXE auch die für DOS-executable Applications wichtigen Relokationen. Normalerweise bevorratet die DOS-EXE-Struktur eine Relokationstabelle, die bei Programmstart vom DOS geladen wird, um die Speicheradressen an die tatsächliche Ladeadresse anzupassen. LZEXE hingegen verkleinert diese Tabelle drastisch, indem es Distanzen zwischen Relokationen anstelle kompletter Speicheradressen codiert und so Speicherplatz spart.
Dabei werden Einzel- und Mehrbyte-Codierungen verwendet, die den Abstand zu vorherigen Relokationen darstellen und Übertragungen innerhalb der ausführbaren Datei präzise ermöglichen. Die finale Phase des LZEXE-Prozesses ist die Anpassung der Prozessor-Register, um die Kontrolle nahtlos an das entpackte Programm zu übergeben. Dabei wird der Programm-Segment-Prefix (PSP) ordnungsgemäß eingerichtet, die Stack- und Code-Segmente werden eingestellt, und das Programm beginnt seine Ausführung, als wäre es nie komprimiert worden. Diese zurückhaltende und durchdachte Anpassung bietet eine größtmögliche Kompatibilität zu bestehenden Programmen und Umgebungen. Obwohl LZEXE technisch äußerst effektiv war, stehen hinter seinem Erfolg auch kreative Programmiertricks.
Fabrice Bellard hinterließ in der Dekomprimierungsroutine sogar eine versteckte ASCII-Nachricht – *FAB* als Zeichen für seine Initialen. Seltene Opcode-Kombinationen werden als Daten genutzt, was einige Disassembler verwirren kann, aber gleichzeitig zeigt wie sorgfältig der Code optimiert wurde. Bis heute wird LZEXE als Meilenstein in der Geschichte der Softwarekompression angesehen. Zahlreiche Spiele und Programme der späten 80er und frühen 90er Jahre nutzten diese Technik, um Speicherplatz zu sparen und Ladezeiten positiv zu beeinflussen. Besonders in Zeiten von Diskettenlaufwerken mit 360 KByte und langsamen Festplatten war die Halbierung der Dateigröße ein großer Vorteil.
Darüber hinaus bietet die Analyse der Implementierung interessante Einblicke in niedrige Rechnerarchitektur, Speicherverwaltung und effiziente Maschinencodierung. LZEXE ist somit nicht nur ein praktisches Werkzeug, sondern auch ein Beispiel für elegantes und leistungsfähiges Programmieren in der Welt der frühen Computertechnik. Die Messlatte, die LZEXE setzte, inspirierte später viele weitere Entwicklungen im Bereich der Dateikompression und -archivierung. Auch wenn heutige Systeme viel leistungsfähiger sind und andere Kompressionsmethoden verwenden, bleibt LZEXE ein Beweis dafür, wie cleveres Design und ein tiefes Verständnis für Architektur und Algorithmen Speicher- und Geschwindigkeitsprobleme in der Software lösen können. Fazit: LZEXE hat unter MSDOS einen wichtigen Beitrag zur Optimierung der Ausführung von ausführbaren Dateien geleistet.
Es demonstriert, wie durch innovative Algorithmen und geschicktes Speicher-Management das Komprimieren und Entpacken von Programmen ohne nennenswerte Performance-Einbußen möglich ist. Diese Technologie eröffnete eine neue Welt der Softwareverteilung und bleibt bis heute ein faszinierendes Beispiel für effiziente Programmierung im eingeschränkten Umfeld früher Personal Computer.
