• 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