Guten Tag meine lieben Mithacker und Mithackerinnen
ich hab noch mal rausgearbeitet wie die LZ77 Grafikkompression
innerhalb einer GBA Rom für die Gfx Grafiken funktioniert.
LZ77 ist ein s.g. Verschlüsselungsalgorithmus, der dazu benutzt wird
Grafiken zu Komprimieren. Um diese Komprimierten Daten wieder zu
entschlüsseln und sie in die 4bpp - 4 Bits pro Pixel - Form zu bringen
muss man folgendes machen.
Wo &H vorsteht bedeutet, dass es sich um einen Hexadezimalwert handelt
Die erste Zahl verrät wie viele Farben die Grafik hat, wobei es
die Varianten &H10 für 16 Farben und &HFF für 256 Farben gibt.
Die zweite bis vierte Zahl geben an, wie groß das Bild ist bzw. wie viele
Bytes das Dekomprimierte Format lang ist.
dabei muss man die Reihenfolge wie bei den Pointern vertauschen.
Sprich man muss aus:
AB CD EF
EF CD AB
machen, damit die Größenangabe stimmt.
Nach den ersten 4 Zahlen fängt dann das eigentliche Bild an.
Das is so aufgebaut, dass erst immer ein Decodierbyte steht und
dann 8 weitere Angaben, worauf wieder ein Decodierbyte und wieder 8 weiter Angaben folgen usw.
Dieses Decodierbyte verrät, welche der nächsten 8 Angaben codiert,
beziehungsweise nicht codiert sind. Dafür wandelt man das Byte in die
Binarform um, sodass ein 8-stelliger Wert herauskommt aus 0en und 1en.
Eine 0 bedeutet, dass der Wert uncodiert ist, eine 1 bedeutet, dass
der Wert codiert ist.
Ein uncodierter Wert ist genau ein Byte lang, das heißt man kann das
Byte direkt übernehmen in den Output.
Der Output ist das Ergebnis, der decodierte Text.
Ein codierter Wert besteht aus genau 2 Bytes, diese 2 Bytes geben
an, wie weit man in seinem Output zurückgreifen muss und wie viele
Bytes ab der zurückgegriffenen Stelle übernommen werden. Dabei setzt
sich das ganze wie folgt zusammen. Diese 2 Bytes bestehen aus 4 Hexadezimalzahlen, die letzten drei Hexwerte +1 geben an, wie weit man
in seinem Output zurückgreift und der erste Hexwert gibt an, wie viele
Bytes + 3 ab der zurückgegriffenen Stelle übernommen werden.
Hier das ganze an einem Bespiel:
codierter Wert: &HF1 &H32
die letzten drei Werte +1 sind die Rückgrifflänge:
&H132+1
der erste Werte +3 ist die Übernehmlänge:
&HF+3
Man geht also &H132+1 = 307 Bytes in seinem Output von hinten
gezählt zurück und übernimmt ab da &HF+3 = 18 Bytes
ein anderes Bespiel:
codierter Wert: &HF0 &H01
die letzten drei Werte +1 sind die Rückgrifflänge:
&H001+1
der erste Wert +3 ist die Übernehmlänge:
&HF+3
Man greift also &H001+1 = 2 Bytes in seinem Output von hinten
gezählt zurück und übernimmt ab da &HF+3 = 18 Bytes
Aber was macht man, da das Output, ab der zurückgegeriffenen Stelle
nur 2 Bytes lang ist und nicht wie vorgegeben 18. Die Lösung ist, dass
man die erhaltene Länge einfach so oft wiederholt bis die 18 erreicht ist.
Also wiederholt man die 2 Bytes die im Output stehen 9 mal und hat
somit seine 18.
Wenn man nur 2 erhält und 17 das Ziel ist, dann wiederholt man die 2 Bytes 8 mal und wiederholt die Bytes dann so lange, bis die 17 voll sind.
Also würden die 2 Bytes 8,5 mal wiederholt.
Das verbirgt sich hinter dieser Kompression.
Hier noch mal das ganze an einem Beispiel:
ab hier Hexwerte:
10 90 01 00 20 00 00 F0 01 33 34 56 78 87 07
Die 10 sagt uns, dass es sich um ein Bild mit 16 Farben handelt.
90 01 00 wird umgestellt zu 00 01 90 = 400 Bytes langes Bild
&H20 ist in Binar = 00100000
Heißt für die nächsten 8 Angaben, die ersten beiden sind uncodiert
00 = 00
Output = 00
00 = 00
Output = 00 00
der nächste Wert ist codiert:
F0 01
man greift 1+1 Bytes zurück und wiederholt das erhaltene bis F+3 erreicht ist
also 9 x [00 00]
Output = 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
die nächsten 5 Werte sind wieder uncodiert
33 34 56 78 87
33 = 33
Output:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 33
34 = 34
Output:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 33 34
56 = 56
Output:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 33 34 56
78 = 78
Output:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 33 34 56 78
87 = 87
Output:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 33 34 56 78 87
Da jetzt die 8 Angaben verbraucht sind erfolgt wieder ein Decodierbyte 07
was in Binar = 00000111 ist und bedeutet, dass erst 5 uncodiert und dann wieder 3 codierte Werte folgen.
Das war der ganze Zauber der LZ77 Kompression.
Viel Spaß mit dem Tutorial euer Aeonmaster
Copyright 2007 by Aeonmaster
