Komprimierung
aus RHWiki, der freien Romhacking-Enzyklopädie
| Inhaltsverzeichnis |
Definition
Als Komprimierung wird allgemein eine Codierung bezeichnet, die bewirkt dass bestimmte Daten weniger Speicher verbrauchen (als sie unkomprimiert verbrauchen würden). Es gibt ganz unterschiedliche Komprimierungsmethoden und es ist fast unmöglich alle aufzuzählen.
Verwendung
In Konsolenspielen (Roms) sind Komprimierungen sehr wichtig, da eine Cartridge nur begrenzt Platz bietet und ein ganzes Spiel mit allen Grafiken und Musik darauf passen soll. Auch im Desktop-Bereich sind Komprimierungen trotz immer größerer Festplatten sehr verbreitet, da man einerseits noch mehr Platz hat und andererseits die Übertragung von Daten über das Internet/Netzwerk immernoch sehr langsam ist und durch Komprimierung die Übertragung beschleunigt werden kann. (bzw. kann auch teure Bandbreite gespart werden.)
Wir wollen hier nur die Komprimierungen wie sie in Roms vorkommen betrachten (obwohl das theoretisch auch alle möglichen sein können).
Komprimierungen können eigentlich für fast jede Art von Daten verwendet werden. Allerdings sind sie dort unterschiedlich effizient, da sich manche Daten besser/schlechter als andere komprimieren lassen.
Hauptsächlich finden Komprimierungen im Grafikbereich Anwendung, dazu noch in manchen Spielen bei Texten und Musik oder auch sogar für Header.
Methoden zur Komprimierung
Man unterscheidet zwischen zwei grundlegenden Methoden zur Komprimierung:
1. Wiederverwendung von Daten (Beispiel: lz77)
Bei dieser Art von Komprimierung macht man sich zunutze, dass viele Daten in einem Datenblock mehrfach (redundant) vorkommen. Beim zweiten Auftreten einer bestimmten Zeichenfolge kann dann einfach gesagt werden "nehme das was 38 Bytes weiter hinten bereits ausgegeben wurde".
Beispiel: ABCxABCDyABCDEz Wird zu: ABCx<Gehe 4 Bytes zurück und nehme 3>Dy<gehe 5 Bytes zurück und nehme 4>Ez (wobei <> einen Wiederverwendungs-Befehl kennzeichnet.)
2. Optimale Codierung (z.B. Huffman)
Hier macht man sich zum Vorteil, dass in einem Datenblock manche Zeichen häufiger vorkommen als andere und einige überhaupt nicht. Die am häufigsten auftretenden Zeichen werden dann mit den kürzesten Bitfolgen codiert, und die seltenen mit den längsten. Auf diese Weise kann eine optimale Codierung erzielt werden (die evtl. durch Kombination mit anderen Komprimierungsmethoden, z.B. lz77 noch verstärkt werden kann).
Beispiel: ABCC (Hier verbraucht zunächst jedes Zeichen ein Byte) Komprimierung: 1. Es kommen nur die Zeichen A, B und C vor. 2. C kommt genauso häufig vor, wie A und B zusammen. 3. Daher bekommt C zur Codierung einen 1-Bit-Code und A und B zusammen ebenfalls 1 Bit. 4. Der Code für A/B muss nun noch um ein weiteres Bit erweitert werden, damit zwischen A und B unterschieden werden kann. Es folgt: 0 = C 10 = A 11 = B (Dass hier C=0 ist, ist rein willkürlich. Man könnte es auch andersrum machen.) Der Text ändert sich dann komprimiert zu: 10110 je nach Codierung kann die Reihenfolge der Bits von links nach rechts oder umgekehrt sein. Das soll hier aber nicht Thema sein.
An dem Beispiel sieht man die Mächtigkeit der Komprimierung: aus 32 Bits wurden 5 Bit. Dabei ist anzumerken, dass man selten nur 4 Byte komprimiert und dass in größeren Datenmengen mehr Zeichen mit gleichmäßigerer Verteilung auftreten, die Komprimierung also nicht mehr ganz so viel bringt, aber immernoch effektiv sein kann.
Qualität
Obige Beispiele zeigen bereits, dass Komprimierungen grundverschieden sein können. Man misst daher die Qualität einer Komprimierung einerseits an dem Faktor um den die Daten durchschnittlich kleiner werden, und andererseits an der Zeit die ein implementierter Algorithmus zur Komprimierung bzw. Dekomprimierung benötigt. Auch noch wichtig sein kann der Speicherverbrauch.
Letztere beiden Eigenschaften (Geschwindigkeit und Speicherverbrauch) sind auf Konsolensystemen besonders wichtig, da man von beiden nur verhältnismäßig wenig hat. Ist z.B. eine Sound(de)komprimierung zu langsam, kann der Sound knacken, was natürlich nicht sein darf.
Komprimierung hacken
Um Komprimierungen hacken zu können, muss man schon ein sehr erfahrener Hacker sein.
Entweder schaut man sich dann die komprimierten Daten an und erkennt mit etwas Glück eine Regelmäßigkeit (Ausnahme), oder man versucht mit einem Debugger einen Breakpoint in die Dekomprimierungsroutine zu legen und dann zu verstehen was diese macht. Dazu sind jedoch umfangreiche Assembler-Kenntnisse unerlässlich.
Tools
Da Komprimierungen sehr komplex sein können, wird von kaum jemandem verlangt, dass er Daten per Hand (Hexeditor) komprimieren kann. Stattdessen sind Tools unerläßlich, welche die Arbeit erledigen, die bei großen Datenmengen schonmal sehr umfangreich sein kann.
Einfache Tools erledigen wirklich nur die Dekomprimierung und (Re)komprimierung. Umfangreichere Programme können dazu dies direkt mit einem Rom, noch zusätzliche Konvertierungen durchführen und auch die Pointer auf die Daten automatisch ändern. Das ist aber keineswegs selbstverständlich.
Dokumentation zu bekannten Formaten
Für Gameboy Advance (BIOS-Funktionen):
Allgemein:
