Lz77
aus RHWiki, der freien Romhacking-Enzyklopädie
Der LZ77-Algorithmus ist einer der weit verbreitetesten Komprimierungsalgorithmen. LZ77 bietet die Möglichkeit große Daten auf eine kleinere Gesamtgröße zu komprimieren und später wieder zu dekomprimieren. Je öfter sich Bereiche in den zu komprimierenden Daten wiederholen um so besser können die Daten komprimiert werden.
| Inhaltsverzeichnis |
Das Grundkonzept
Der LZ77-Algorithmus sucht in den zu komprimierenden Daten nach sich wiederholenden Texten/Bytefolgen. Am besten lässt sich sowas jedoch an einem Beispiel erklären:
Position: 0 1 2 3 4 5 6 7
1234567890123456789012345678901234567890123456789012345678901234567890
Eingabe: wiederholende wörter wiederholen sich wie wörter die sich wiederholen.
Ausgabe: wiederholende wörter [1:11] sich[21:4] [15:8]die[18:9][4:8].
[offset:größe]
Die Werte in den Eckigen Klammern geben nun einmal den Offset des Datenblockes sowie, dessen Größe an. [15:8] bedeutet nun, dass an diese Stelle 8 Bytes von der Position 15 kopiert werden sollen. So spart man sich die Wiederholung des kompletten Textabschnittes nochmal, da sich Offset+Größe meist auch schon in 2 Bytes speichern lassen.
Details
Zunächst muss Anfangs in die Datei gespeichert werden, wie groß die dekomprimierten Daten ursprünglich waren. Das ist nötig, da es bei dem LZ77-Algorithmus kein ENDE-Signal/Byte gibt.
Nun muss der Algorithmus irgendwoher wissen, welche Bytes nun übernommen werde können und wo Informationen über einen Offset/eine Größe zur Kopie von Daten gespeichert sind. Dazu wird alle 8 Byte (inklusive dem ersten) ein zusätzliches Kontrollbyte gespeichert.
Beispieldarstellung:
Gesamtlänge: 13 Kontrollbyte (dual): 00100010 0 0100010: a -> (a) 0 0 100010: n -> a(n) 00 1 00010: (0,3) -> an(ana) 001 0 0010: s -> anana(s) 0010 0 010: _ -> ananas(_) 00100 0 10: b -> ananas_(b) 001000 1 0: (0,5) -> ananas_b(anana)
Die Position für die Quelldaten werden allerdings meistens relativ zur aktuellen Position angegeben. Das bedeutet, normalerweise würde es heißen: Kopiere 6 Bytes von den Daten, die 8 Bytes vor "hier" liegen. Außerdem wird zu der Größe und dem Offset meist noch ein konstanter Wert addiert. Schließlich ist es wenig sinnvoll einen Datenbereich von 1 Byte zu kopieren, wenn die Information über den Offset und die Größe selber 2 Byte brauchen.
Beispielquellcode
Hier ist ein Beispielquellcode in C++ geschrieben, der das Dekomprimieren der Daten anhand der GBA-LZ77-Komprimierung demonstriert:
//----------------------------------------------------------------------------
// Diese Funktion dekomprimiert die Daten aus 'Source' und gibt die
// dekomprimierten Daten in 'Data' zurück. Der Rückgabewert der
// Funktion ist entweder 0 bei einem Fehler, oder die Größe der
// dekomprimierten Daten
//----------------------------------------------------------------------------
unsigned Decompress( char* Source, char* &Data )
{
unsigned Header, i;
unsigned DataSize, DataLeft;
unsigned char ControlByte, CopyLength;
unsigned short Data, CopyOffset;
char *CurPos, *SrcPnt;
// Überprüfen des Headers und auslesen der Orginalgröße
Header = *((unsigned*)Source); // Header auslesen
DataSize = Header >> 8; // Datengröße auslesen
DataLeft = DataSize; // Datengröße zur Bearbeitung
// Kurze Fehlerüberprüfung
if ( (Header & 0xFF) != 0x10 ) return 0;
// Speicher reservieren
Data = new char[ DataSize ] // Speicher reservieren
CurPos = Data; // Die aktuelle Position an den Anfang
// Schleife durchlaufen bis die Datei vollständig dekomprimiert wurde
while ( DataLeft > 0 )
{
ControlByte = *Source++ // Auslesen des Kontrollbytes
// Gibt es mindestens einen gesetzten Bit im ControlByte?
if ( ControlByte!=0 )
{
// 2 Byte auslesen (umgedreht)
Data = *((unsigned char*)(Source++)) << 8;
Data |= *((unsigned char*)(Source++));
// Kopierlänge und Größe auslesen
CopyLength = ( Data >> 12 ) + 3;
CopyOffset = ( Data & 0x0FFF );
// Länge der zu kopierenden Daten zur Sicherheit überprüfen
if ( CopyLength > DataLeft ) CopyLength = DataLeft;
DataLeft -= CopyLength;
// Die Quellposition ist relativ zur aktuellen Position
SrcPnt = CurPos - CopyOffset - 1;
// Kopieren der Daten
while ( CopyLength-->0 )
*CurPos++ = *SrcPnt++;
}
else
{
// Einfach die folgenden 8 Byte kopieren
for ( i=0; i<8 && DataLeft>0; ++i, --DataLeft )
*CurPos++ = *Source++;
}
}
return DataSize;
}
