LZSS: Lempel–Ziv–Storer–Szymanski

  • 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

  • Schön erklärt, manakoAT


    :thumbup:


    Ma schaun wann ich mir sone kompression selber Bastel ;D


    Du könntest ja noch was dazumachen. Dann nennst du das Ganze "LZSSC" Lempel–Ziv–Storer–Szymanski-Ciller3k. Und bringst das so auf den Markt.
    Allein das neuere Veröffenlichungsdatum (2012) würde implizieren, dass es eine bedeutende Weiterentwicklung ist. Dann wirst du reich ...

  • ... wenn schon, dann mir, das ist schon seit 2006 in SnesEdit eingebaut ...


    Ich habe mir mal die Müche gemacht das ganze abzutippen und in der LZxx Anzeige eingestellt:


    Das Ergebniss könnt Ihr mit dem Bild oben vergleichen:


    Die Einstellungen, wie oben beschrieben, damit es genauso angezeigt wird:


    Schönes Wochenende, Ich mach jetzt ein paar Monate Urlaub.

    • Offizieller Beitrag

    So zurück zum Thema, erstmal ganz klasse gemacht von manako. Dieses TuT ist sehr wertvoll für Leute di gar kein Plan haben und damit haben sie zumindest die Richtung bekommen und genau das ist es doch was man braucht ich kann es gut verstehen was manako hier erklärt hat! Und dafür ein Fettes DANKE. Ich bin überzeugt das es auch andere User gibt denen es weiter hilft ^^


    (Wer genau hinschaut entdeckt vielleicht sogar ein Ester Egg ^^ hier im Thread)