Name: LZSS
Typ: LZ77-Erweiterung
Verlustfrei: Ja
Beispiel: Clock Tower II - The Struggle Within (PSX)
Link: Wikipedia
Hier beschreibe ich an einem kleinen Beispiel wie LZSS funktioniert...
Auf die Herkunft und wie es entstanden ist gehe ich nicht weiter ein, dafür lest bitte den Wikipedia Artikel :o)
Ein Screen von den Daten die wir dekodieren möchten:
Rauskommen soll dabei das hier:
Unser erstem 4 Bytes sind nur ein Header ("EXS") gefolgt von einer Nummer, die wahrscheinlich den Typ der Kompression angibt, bisher habe ich aber nur die ID 1 gefunden.
Die nächsten 4 Bytes geben die dekomprimierte Größe an, also 0x674D4 (423124 Bytes).
Danach startet unser LZSS Stream bei Offset 0x8.
Ein LZSS-"Frame" besteht aus 3 Komponenten:
1.) das "Flag Byte"
2.) Unkomprimierte Einträge
3.) Komprimierte Einträge
Das erste Byte (Flag Byte) wird immer dazu genutzt um anzuzeigen wie die nachfolgenden Daten abgespeichert wurden, unser erstes Byte hier ist 0xBB, dieses müssen wir in seine Bits zerlegen, was 10111011 binär ergibt, in diesem Fall müssen wir die Bits noch umdrehen, da sie von hinten nach vorne gelesen werden, also: 11011101.
In unserem Beispiel wird die 1 für einen Unkomprimierten Eintrag verwendet, ein sogenanntes "Literal"-Byte (^Müllbyte^) und die 0 für Komprimierte Einträge.
Wie schon gesagt, das Literal ist nur 1 Byte, ein Komprimierter Eintrag besteht hier immer aus 2 Byte.
Zerlegen wir mal unsere Bits:
1 - Literal - 1 Byte
1 - Literal - 1 Byte
0 - Komprimiert - 2 Byte
1 - Literal - 1 Byte
1 - Literal - 1 Byte
1 - Literal - 1 Byte
0 - Komprimiert - 2 Byte
1 - Literal - 1 Byte
Wir wissen nun, dass die ersten beiden Bytes nach dem Flag Byte unkomprimiert sind, also haben wir schonmal einen Output von: "05 00"
Jetzt kommt ein Komprimierter Eintrag, den wir wiederum zerlegen müssen, 0x0200
Komprimierte Einträge bestehen in unserem Fall aus 16 Bits, diese 16 Bits werden für Längen- und Positionsangaben verwendet, in unserem Beispiel 4 Bits für die Länge und 12 Bits für die Position, das macht 2^4 = 16 Bytes die mit diesen 4 Bits dekomprimiert werden können und 2^12 = 4096 Bytes für die Position wo sich diese Bytes befinden.
Wie diese Bits angeordnet sind, kann je nach Kompression variieren (Jenachdem was sich der Entwickler einfallen lässt), es gibt auch Kombinationen von 11 Bits für die Position mit 5 Bits für die Länge, oder 13 Bits für die Position und 3 Bits für die Länge, und es gibt sogar Spiele die verwenden nur 1 Byte für Komprimierte Einträge, wie Grandia 2 (6 Bits für die Position und 2 Bits für die Länge)
Wir drehen unseren Komprimierten EIntrag jetzt um, weil wir ja von rechts nach links lesen: 0x0002
Zerlegen ihn in Bits: 0000000000000010
Wir wissen das unsere Position 12 Bits hat und unser Länge 4 Bits:
0000 000000000010
LLLL PPPPPPPPPPPP
Wenn wir das jetzt wieder in normale Zahlen umwandeln, erhalten wir 0x02 als Positionsangabe und 0x00 als Längenangabe,
wir dekomprimieren also von Offset 0x02 0 Bytes....
0 Bytes??? Da sgeht schlecht, wir zählen 2 dazu, so etwas wird meist gemacht, weil es Blödsinn ist zum Beispiel 1 Byte oder 2 Byte mit einem 16 Bit Eintrag zu kodieren (wobei letzteres doch hier gemacht wird),
desweiteren müssen wir den Offset -1 rechnen (Keine Ahnung warum das hier so ist)
Also: 0x01 Position, 0x02 Länge, Dekomprimiere 2 Bytes ab Offset 0x1
Unser Derzeitiger Output ist "05 00",
Jetzt nehmen wir ein Byte von Offset 0x1 und packen es hinten ran: "05 00 00",
nehmen noch ein Byte von Offset 0x1 und packen es wieder hinten ran: "05 00 00 00".
Die nächsten 3 Bytes sind Unkomprimiert, wir fügen sie einfach an den Output mit an und erhalten: "05 00 00 00 1D E6 20"
Jetzt kommt wieder ein Komprimierter Eintrag: 0x0710, einmal drehen = 0x1007
0001 000000000111
LLLL PPPPPPPPPPPP
1 Länge, 0x7 Position
Länge = Länge + 2 = 3
Position = Position - 1 = 0x6
Wir kopieren 3 Bytes ab Position 0x6
Einmal: "05 00 00 00 1D E6 20 20"
Zweimal: "05 00 00 00 1D E6 20 20 20"
Dreimal: "05 00 00 00 1D E6 20 20 20 20"
Das nächste Byte ist wieder ein Literal und wird einfach an den Output angehängt, also: "05 00 00 00 1D E6 20 20 20 20 4D"
Somit haben wir 11 Bytes insgesamt dekomprimiert, damit ist die Dekodierung dieses Frames abgeschlossen und der nächste Frame wird dekodiert, dieser beginnt diesmal mit 0xFF