En kort introduktion till datakomprimering.

Det finns två typer av datakomprimering; destruktiv (eng. lossy) och icke-destruktiv (eng. lossless). Destruktiv komprimering används bl.a i mp3, ogg, mpeg, jpeg och andra filformat för att minska deras, annars smått enorma, storlek. I den här artikeln ska jag introducera en icke-destruktiv algoritm och hur man kan använda den får att krympa exekverbara filer.
Det är viktigt att uppmärksamma att komprimering endast fungerar på de former av data som inte är optimalt lagrade i grundutförandet, eller som redan tidigare komprimerats. Man kan alltså inte "komprimera bort" en fil.

Packade exekverbara filer
Eftersom det endast är filformats headers, dekomprimeringskod och komprimerad data som ska finnas med i en packad exekverbar fil så kan man s'ga att filen ser ut på följande vis:

Exempel - Packad exekverbar fil
[ Filformats headers ][ Dekomprimeringskod ][ Komprimerad data ]

Eftersom filformats headers inte går att modifiera nämnvärt (se davve's PE-artikel), så kan vi anta att dessa är ett konstant antal bytes. Det man sedan har att variera är dekomprimeringskodens och den komprimerade datans storlek.
Har man en stor mängd komprimerad data så kan man tjäna på att använda en mer avancerad dekomprimeringsfunktion, som tar mer plats, men gör att den komprimerade datan blir mindre.

En komprimeringsalgoritm - LZSS
LZSS är en komprimeringsalgoritm baserad på LZ77 från 1977 skapad av Lempel och Ziv. Som sedan vidareutvecklats.

Det LZSS gör är att leta efter upprepningar i data och sedan hänvisa till dessa, så att "alla" upprepningar försvinner i datan. För detta används markeringar i den komprimerade datan för att ange om man matar ut data eller om man har hittat en upprepning.

Exempel på komprimering:
DATA IN: "ABCDABCE"
DATA UT: 0 'A' 0 'B' 0 'C' 0 'D' 1 4 3 0 'E'

0 anger att det är en vanlig byte som finns efteråt. 1 anger att man hittat en upprepning av tidigare data. Det innebär att följande tal anger hur många steg bakåt i datan man ska gå, och talet efter det är det antal tecken som ska hämtas.

Exempel dekomprimering steg för steg.
DATA IN: 0 'A' 0 'B' 0 'C' 0 'D' 1 4 3 0 'E'

1. DATA UT: "A", inget konstigt
2. DATA UT: "AB", ...
3. DATA UT: "ABC", ...
4. DATA UT: "ABCD", ...
5. DATA UT: "ABCDABC", Hittar en upprepning 4 steg bakåt och 3 lång ("ABC"), den sätter vi här.
6. DATA UT: "ABCDABCE", inget konstigt

Fördelen med LZSS är att dekomprimeringskoden är väldigt liten och lämpar sig därför väl till att packa upp exekverbara filer. Dekomprimeringsalgoritmen kan sammanfattas med följande pseudokod: